0x01 简介

1978年,MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman用数论构造双钥密码的方法，称作MIT体制，后被广泛称为RSA体制，易懂且易于实现，是目前仍然安全并且应用最广泛的公钥密码算法。

RSA的安全性基于数论中大整数分解的困难性。

0x02 原理

1. 密钥的产生

选择两个素数p和q，计算：
- N = p * q
- φ ( N ) = φ (p) * φ (q) = (p-1) * (q-1)
质数(prime number)：又称素数，为在大于1的自然数中，除了1和它本身以外不再有其他因数。

互质关系：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。

φ(N)：叫做欧拉函数，是指任意给定正整数N，在小于等于N的正整数之中，有多少个与N构成互质关系。
- 如果n是质数，则 φ(n)=n-1。
- 如果n可以分解成两个互质的整数之积， φ(n) = φ(p1p2) = φ(p1)φ(p2)。即积的欧拉函数等于各个因子的欧拉函数之积。
选择整数e，满足以下条件：
- e 和 φ(N)互质，即 gcd(Φ(n),e)=1
- 1< e < φ(N)
常使用65537=2¹⁶+1。用二进制表示：10000000000000001，只有两个1，代码只有两次需要执行if语句的乘法，很大限度地提高了运算使用公钥的运算速度。但实际应用实现中参数的选择需要仔细斟酌。
计算整数d，使d满足以下方程：

d=e^-1mod Φ(n)
密钥
- 公钥：(N, e)
- 私钥：(N, d)

2. 加密过程

明文： M < N

密文： C = M^e mod N

3. 解密过程

密文： C

明文： M = C^d mod N

4. RSA填充方式

PKCS全称Public Key Cryptography Standers, 是RSA信息安全公司与其合作伙伴共同制定的，被信息界的产业广泛认同。

RSA加密常用的填充模式有三种：

填充方式	待填充长度	填充后长度
RSA_NO_PADDING	不填充	和公钥等长
RSA_PKCS1_PADDING	至少RSA_size(rsa) - 11	和公钥等长
RSA_PKCS1_OAEP_PADDING	RSA_size(rsa) - 41	和公钥等长

RSA_NO_PADDING

当用户选择RSA_NO_PADDING填充模式时，如果明文不够128字节，加密的时候会在明文前面填充若干数据0，直至达到128字节。

解密后的明文也会包括前面填充的零，用户需要注意把解密后的字段前向填充的零去掉，才是真正的明文。

RSA_PKCS1_PADDING

当你选择RSA_PKCS1_PADDING填充模式时，如果明文不够128字节，加密的时候会在明文中随机填充一些数据，所以会导致对同样的明文每次加密后的结果都不一样。

这种方式是Java库中默认采用的填充方式，格式

EB = 00 || BT || PS || 00 || D

第一部分默认为00

第二部分BT（The block type块类型）：00 表示签名， 01 表示加解密

第三部分PS（The padding string填充字符串）：

BT=00，PS由00组成；
BT=01，PS由FF组成；
BT=02，PS由伪随机生成，且非零；
PS长度为Len(EB) - 3 - Len(D)，最少是8字节。

不同公钥大小能加密的明文最大长度：

1024: (1024 - 11 * 8) / 8 = 117
2048: (2048 - 11 * 8) / 8 = 245
4096: (4096 - 11 * 8) / 8 = 501

RSA_PKCS1_OAEP_PADDING

最优非对称加密填充（Optimal Asymmetric Encrypt Padding）简称OAEP。

RSA_PKCS1_OAEP_PADDING填充模式是PKCS#1推出的新填充方式，安全性最高，和前面RSA_PKCS1_PADDING的区别就是加密前的编码方式不一样。

5. RSA安全性

RSA算法有以下攻击方式（其实不只是RSA，其他密钥体系也可能有）：

穷举攻击
数学攻击
计时攻击
基于硬件故障分析
选择密文攻击

穷举攻击

通过穷举所有的可能数据来猜测密钥或者密文。
当然RSA参数比较小的时候，可以使用该方法奏效。
例如用户公钥n = 35, e = 5 密文C = 10 被截获后，由于C=M**e mod n=M5 mod 35=10, 计算循环1到35，很容易破解原始消息M = 5.

抵抗该种攻击的方式是使用大密钥空间，公私钥均为很长比特位，如2048位等

数学攻击

数学攻击的方法实质是试图分解两个素数的乘积，根据RSA原理? = ? × ?，找到素数对用的p,q, 进而计算出?(?)和私钥d。

因式分解法：试除法、二次筛因子分解法、数域筛法

工具：

yafu

factordb.com

针对参数选择的攻击：共模攻击、低指数攻击、p-1和q-1都应有大的素数因子

共模攻击：

公钥为（N,e¹)，(N,e²), e¹,e²互质这两个实例的特点是模n是相同的，这样的情况叫做共模。

因为gcd(e1,e2)=1

根据贝祖定理re1+se2=1

可以求出一组解( r, s )，且一正一负，假设r为正，s为负

所以

C1 = M^e1 mod N

C2 = M^e2 mod N

C1^r * C2^s mod N

=(( M^e1 mod N ) * ( M^e2 mod N )) mod N

=((M^{( e1 * r + e2 * s )} mod N )

=M
低指数攻击

低指数攻击是当选取的e比较小的时候容易受到的攻击。利用中国剩余定理，即使三个模不互素使用也可以求出。参数的选取越小越不安全。

填充提示攻击

Padding Oracle Attack

Padding Oracle Attack是比较早的一种漏洞利用方式了，在2011年的Pwnie Rewards中被评为”最具有价值的服务器漏洞“。该漏洞主要是由于设计使用的场景不当，导致可以利用密码算法通过”旁路攻击“被破解，并不是对算法的破解。

利用该漏洞可以破解出密文的明文以及将明文加密成密文，该漏洞存在条件如下：

1、攻击者能够获取到密文（基于分组密码模式），以及IV向量（通常附带在密文前面，初始化向量）；

2、攻击者能够修改密文触发解密过程，解密成功和解密失败存在差异性。

计时攻击

攻击者通过记录计算机解密消息所需要的时间，来确定私钥的信息。该攻击方法不是基于实现的算法本身的弱点。时间信息、功耗、电磁泄漏甚至声音可以提供额外的信息来源，可以加以利用。

基于硬件故障分析

这种攻击的目标是对产生签名的处理器，通过减少处理器的输入电功率，以在签名计算中引入故障。故障导致软件产生无效签名，然后攻击者通过分析恢复出私钥。这种攻击并未对RSA造成严重威胁，因为它需要攻击者能够物理接触到目标机器并且能够控制处理器的输入电功耗。

0x03 例子：

1. 手工计算

p=7
q=17
n=p*q=119
φ(n)=(p-1)*(q-1)=96
e=5                 e<φ(n)且gcd(e,φ(n))=1
d*5=1 mod 96        且d<96
77 * 5 = 385 = 4 * 96 + 1
d=77

公钥为{5,119}
私钥为{77,119}

2. python

python语言使用gmpy2库举例操作

gmpy2库安装

pip install wheel
# 进入以下链接，下载python对应版本的gmpy2所需要的whl文件
https://www.lfd.uci.edu/~gohlke/pythonlibs/

pip3 install whl文件路径
pip3 install gmpy2

import binascii
import gmpy2

N=0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9f

e=0x10001

c=0x3dbf00a02f924a70f44bdd69e73c46241e9f036bfa49a0c92659d8eb0fe47e42068eaf156a9b3ee81651bc0576a91ffed48610c158dc8d2fb1719c7242704f0d965f8798304925a322c121904b91e5fc5eb3dc960b03eb8635be53b995217d4c317126e0ec6e9a9acfd5d915265634a22a612de962cfaa2e0443b78bdf841ff901423ef765e3d98b38bcce114fede1f13e223b9bd8155e913c8670d8b85b1f3bcb99353053cdb4aef1bf16fa74fd81e42325209c0953a694636c0ce0a19949f343dc229b2b7d80c3c43ebe80e89cbe3a3f7c867fd7cee06943886b0718a4a3584c9d9f9a66c9de29fda7cfee30ad3db061981855555eeac01940b1924eb4c301

p=57970027

q=518629368090170828331048663550229634444384299751272939077168648935075604180676006392464524953128293842996441022771890719731811852948684950388211907532651941639114462313594608747413310447500790775078081191686616804987790818396104388332734677935684723647108960882771460341293023764117182393730838418468480006985768382115446225422781116531906323045161803441960506496275763429558238732127362521949515590606221409745127192859630468854653290302491063292735496286233738504010613373838035073995140744724948933839238851600638652315655508861728439180988253324943039367876070687033249730660337593825389358874152757864093

# 求mod φ(n) 的逆元
d = gmpy2.invert(int(str(e)),(p-1)*(q-1))
# c^d mod N 
m = pow(c,d,N)
print(binascii.unhexlify(hex(m)[2:]).decode('utf-8'))

0x04. CTF

2017第二届广东省强网杯线上赛

下载打开txt文件，内容：

n is 966808932627497190635859236054960349099463975227350564265384373280336699853387254070662881265937565163000758606154308757944030571837175048514574473061401566330836334647176655282619268592560172726526643074499534129878217409046045533656897050117438496357231575999185527675071002803951800635220029015932007465117818739948903750200830856115668691007706836952244842719419452946259275251773298338162389930518838272704908887016474007051397194588396039111216708866214614779627566959335170676055025850932631053641576566165694121420546081043285806783239296799795655191121966377590175780618944910532816988143056757054052679968538901460893571204904394975714081055455240523895653305315517745729334114549756695334171142876080477105070409544777981602152762154610738540163796164295222810243309051503090866674634440359226192530724635477051576515179864461174911975667162597286769079380660782647952944808596310476973939156187472076952935728249061137481887589103973591082872988641958270285169650803792395556363304056290077801453980822097583574309682935697260204862756923865556397686696854239564541407185709940107806536773160263764483443859425726953142964148216209968437587044617613518058779287167853349364533716458676066734216877566181514607693882375533
e is 65537
c is 168502910088858295634315070244377409556567637139736308082186369003227771936407321783557795624279162162305200436446903976385948677897665466290852769877562167487142385308027341639816401055081820497002018908896202860342391029082581621987305533097386652183849657065952062433988387640990383623264405525144003500286531262674315900537001845043225363148359766771033899680111076181672797077410584747509581932045540801777738548872747597899965366950827505529432483779821158152928899947837196391555666165486441878183288008753561108995715961920472927844877569855940505148843530998878113722830427807926679324241141182238903567682042410145345551889442158895157875798990903715105782682083886461661307063583447696168828687126956147955886493383805513557604179029050981678755054945607866353195793654108403939242723861651919152369923904002966873994811826391080318146260416978499377182540684409790357257490816203138499369634490897553227763563553981246891677613446390134477832143175248992161641698011195968792105201847976082322786623390242470226740685822218140263182024226228692159380557661591633072091945077334191987860262448385123599459647228562137369178069072804498049463136233856337817385977990145571042231795332995523988174895432819872832170029690848

使用工具对n进行因式分解得

p=31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221

q=31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473

n能成功分解，就直接写脚本解出密文c

import gmpy2
import binascii

p = gmpy2.mpz(
    31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928997877221)
q = gmpy2.mpz(
    31093551302922880999883020803665536616272147022877428745314830867519351013248914244880101094365815998050115415308439610066700139164376274980650005150267949853671653233491784289493988946869396093730966325659249796545878080119206283512342980854475734097108975670778836003822789405498941374798016753689377992355122774401780930185598458240894362246194248623911382284169677595864501475308194644140602272961699230282993020507668939980205079239221924230430230318076991507619960330144745307022538024878444458717587446601559546292026245318907293584609320115374632235270795633933755350928537598242214216674496409625928797450473)
e = gmpy2.mpz(65537)
# 计算d
phi_n = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_n)
print("private key:")
print(d)

# 解密
c = gmpy2.mpz(
    168502910088858295634315070244377409556567637139736308082186369003227771936407321783557795624279162162305200436446903976385948677897665466290852769877562167487142385308027341639816401055081820497002018908896202860342391029082581621987305533097386652183849657065952062433988387640990383623264405525144003500286531262674315900537001845043225363148359766771033899680111076181672797077410584747509581932045540801777738548872747597899965366950827505529432483779821158152928899947837196391555666165486441878183288008753561108995715961920472927844877569855940505148843530998878113722830427807926679324241141182238903567682042410145345551889442158895157875798990903715105782682083886461661307063583447696168828687126956147955886493383805513557604179029050981678755054945607866353195793654108403939242723861651919152369923904002966873994811826391080318146260416978499377182540684409790357257490816203138499369634490897553227763563553981246891677613446390134477832143175248992161641698011195968792105201847976082322786623390242470226740685822218140263182024226228692159380557661591633072091945077334191987860262448385123599459647228562137369178069072804498049463136233856337817385977990145571042231795332995523988174895432819872832170029690848)
print("plaintext:")
M = pow(c, d, p * q)
print('[10进制]' + str(M))
flag = str(hex(M))[2:]
print('[16进制]' + flag)
print(binascii.unhexlify(flag).decode('utf-8'))

i春秋第二届春秋欢乐赛

下载文件，打开压缩包，发现如下内容

encrypted.message1
encrypted.message2
encrypted.message3
public.key

以文本形式打开public.key

发现是PEM格式的密钥

-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhANmelSKWptlg38JQSrpUW5RC1gp7npMK
/0UceOxV1VXrAgMBAAE=
-----END PUBLIC KEY-----

一种方式是直接base64解码再进行hex编码，再以ASN.1进行解析得出n和e

一种方式是使用linux的openssl得出n和e

openssl rsa -pubin -text -modulus -in warmup -in  /home/kali/Desktop/public.key

然后看n位数比较少，直接放工具里跑

得出p和q

写脚本，利用rsa库，生成私钥再解密

import gmpy2
import rsa

n = 98432079271513130981267919056149161631892822707167177858831841699521774310891
e = 65537
p = 302825536744096741518546212761194311477
q = 325045504186436346209877301320131277983
d = int(gmpy2.invert(e, (p-1)*(q-1)))
key = rsa.PrivateKey(n,e,d,p,q)
with open("encrypted.message1","rb") as f:
    print(rsa.decrypt(f.read(),key).decode())
with open("encrypted.message2","rb") as f:
    print(rsa.decrypt(f.read(),key).decode())
with open("encrypted.message3","rb") as f:
    print(rsa.decrypt(f.read(),key).decode())

ISC2016训练赛——phrackCTF

题干：前几题因为N太小，都被你攻破了，出题人这次来了个RSA4096，是否接受挑战就看你了。

打开压缩包

flag.enc1
flag.enc2
veryhardRSA.py

#!/usr/bin/env python

import random

N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L

def pad_even(x):
	return ('', '0')[len(x)%2] + x

e1 = 17
e2 = 65537


fi = open('flag.txt','rb')
fo1 = open('flag.enc1','wb')
fo2 = open('flag.enc2','wb')


data = fi.read()
fi.close()

while (len(data)<512-11):
	data  =  chr(random.randint(0,255))+data

data_num = int(data.encode('hex'),16)

encrypt1 = pow(data_num,e1,N)
encrypt2 = pow(data_num,e2,N)


fo1.write(pad_even(format(encrypt1,'x')).decode('hex'))
fo2.write(pad_even(format(encrypt2,'x')).decode('hex'))

fo1.close()
fo2.close()

从给出的代码可以分析出，2个互质的e，使用了共同的n，所以考虑使用共模攻击求解

"""
共模攻击
"""
import binascii
import gmpy2


n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
e1 = 17
e2 = 65537
# 使用扩展欧几里得求出一组s1,s2。其中一正一负  (mpz(1), mpz(30841), mpz(-8))
s = gmpy2.gcdext(e1, e2)
s1 = s[1]
s2 = s[2]
file1 = open("./veryhardRSA/flag.enc1", 'rb').read()
c1 = int(binascii.hexlify(file1), 16)
file2 = open("./veryhardRSA/flag.enc2", 'rb').read()
c2 = int(binascii.hexlify(file2), 16)
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
print(binascii.unhexlify(hex(m)[2:]))

0xFF 补充

1. 模运算规则

(1)(a + b) % p = (a % p + b % p) % p  
(2)(a - b) % p = (a % p - b % p) % p  
(3)(a * b) % p = (a % p * b % p) % p  
(4)(a^b) % p = ((a % p)^b) % p  
(5)结合率： ((a+b) % p + c) % p = (a + (b+c) % p) % p  
(6)((a*b) % p * c)% p = (a * (b*c) % p) % p  
(7)交换率： (a + b) % p = (b+a) % p  
(8)(a * b) % p = (b * a) % p  
(9)分配率： ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p