RSA 笔记

RSA 算法描述

  1. 任意选取两个不同的大素数pq计算乘积n=pq,使用欧拉函数得到φ(n)=(p1)(q1)

  2. 任意选取一个大整数e,满足gcd(e,φ(n))=1,整数e用作加密密钥

  3. 确定的解密密钥d,满足(de) mod φ(n)=1,即de=kφ(n)+1k1是一个任意的整数 (求逆元)

  4. 公开整数ne,秘密保存d

  5. 将明文m加密成密文c,加密算法为: (1)c=E(m)=me mod n

  6. 将密文c解密为明文m,解密算法为: (2)m=D(c)=cd mod n

RSA 必要算法

拓展欧几里得算法

1
2
3
4
5
6
7
8
9
def extendedGCD(a, b):
# a*xi + b*yi = ri
if b == 0:
return 1, 0, a
else:
x, y, q = extendedGCD(b, a % b)
# q = gcd(a, b) = gcd(b, a%b)
x, y = y, (x - (a // b) * y)
return x, y, q

可以使用 gmpy2.gcdext(a, b) 替代,返回三元元组 (g,s,t)

其中g=gcd(a,b)=sa+tb

存在相关性的定理:裴蜀定理。

裴蜀定理说明了对任意整数 a,b 和它们的最大公约数 gcd(a,b)=d,那么对任意整数 x,y 都有 ax+byd 的倍数,即 (3)ax+by=0(modd) 特别地,一定存在整数使得 ax+by=d 成立。

一个重要推论为,a,b 互质的充分必要条件为存在整数 x,y 使得 ax+by=1

可以证明的是,求出的可行解必有 |s|b,|t|a

求逆元

1
2
3
4
5
6
def invert(e, phi):
(x, y, r) = extendedGCD(e, phi)
# y maybe < 0, so convert it
if y < 0:
return phi + y
return y

可以使用 gmpy2.invert(e, phi) 替代

快速幂

1
2
3
4
5
6
7
8
def fastExpMod(b,e,c):
result = 1
while e != 0:
if (e & 1) == 1:
result = (result * b) % c
e >>= 1
b = (b * b) % c
return result

可以直接使用 python 自带的 pow(b, e, c)

数论模运算

除法

(4)c=m×a mod n

对于上式,已知c,a,nm,不能直接求c÷a,需要将其转换为 (5)m=c×invert(a,n) mod nc乘以an的逆元

负数次幂

若要求 (6)k=cs mod n 其中s<0,则需要将其转换为 (7)k=invert(c,n)scn的模反元素的s次幂

欧拉函数

  • 如果p是素数且k1,则 (8)ϕ(pk)=pkpk1 特别地,当k=1时,表达式即为 (9)ϕ(p)=p1

  • 如果gcd(m,n)=1,即m,n互质,则 (10)ϕ(mn)=ϕ(m)ϕ(n)

其中与之相关的有欧拉公式:

对任意两个互素整数 a,n,有 (11)aφ(n)=1(modn)

中国剩余定理

mn是整数,gcd(m,n)=1bc是任意整数,则同余式组 (12)xb (mod m)  xc (mod n) 恰有一个解 0xmn

详细内容可以在这里了解

威尔逊定理

威尔逊定理给出了判定一个自然数是否为素数的充分必要条件:

当且仅当 p 为素数时,有 (13)(p1)!1(modp) 或推论 (14)(p1)!+1=0(modp)(p1)!+1p 的倍数。

一般用于辅助推导,相关的有伽马函数 (15)Γ(n)=(n1)!

费马小定理

如果 p 是一个素数,取任意的非 p 整数 a,有 (16)ap11(modp) 推论有: (17)nap1n(modp),nZ(18)ap2a1(modp)(19)abab(modp1)(modp),bZ

RSA&python 实现

加密

1
2
3
4
5
6
p=447685307
q=2037
e=17
m = 904332399012
n = p * q
c = pow(m, e, n)

解密

1
2
3
4
5
6
7
8
9
10
11
p=447685307
q=2037
e=17
c=704796792
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
# 旧版本python需要使用gmpy2库求解逆元
# import gmpy2
# d = gmpy2.invert(e, phi)
m = pow(c, d, n)

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long

def gen(pbits: int, ebits: int):
"""
生成公钥(n,e)和私钥(p,q,d)

参数:
pbits - 素数p,q的位数

ebits - 公钥e的位数

返回值:
公钥(n,e), 私钥(p,q,d)
"""
p, q = getPrime(pbits), getPrime(pbits)
n = p * q
phi = (p - 1) * (q - 1)
# 如果e和phi公因数不为1,两个不同的素数一定是互质的,则无法找到唯一逆元
e = getPrime(ebits)
d = pow(e, -1, phi)
return (n, e), (p, q, d)

def encrypt(m: int, pubkey: tuple[int, int]):
n, e = pubkey
# 切记不能是math.pow
return pow(m, e, n)

def decrypt(c: int, privkey: tuple[int, int, int]):
p, q, d = privkey
# 切记不能是math.pow
return pow(c, d, p * q)

pbits = 1024
ebits = 32
# 获取公钥私钥
pubkey, privkey = gen(pbits, ebits)
msg = b'Aurora{qsdzyyds!!!qsdzyyds!!!}'
m = bytes_to_long(msg)
# 加密
c = encrypt(m, pubkey)
# 解密
mbar = decrypt(c, privkey)
msgbar = long_to_bytes(mbar)
print(msgbar)

读取参数

工具

1
2
3
4
5
from Crypto.PublicKey import RSA
with open('./tmp/pubkey.pem', 'r') as f:
key = RSA.importKey(f)
N = key.n
e = key.e

也可以使用在线网站:http://www.hiencode.com/pub_asys.html

或者使用 openssl 的 rsa 工具,例如:

1
openssl rsa -in pub.key -text

手读

实际上 PEM 文件是遵循 ASN.1 格式的文件。

尝试生成一个密钥文件

1
openssl genpkey -algorithm rsa -out private_key.pem -pkeyopt rsa_keygen_bits:1024

得到文件 private_key.pem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
-----BEGIN PRIVATE KEY-----
MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBAOwGgqETvFHiR8Dg
GBXtvWt/PxpyxUPcLCw06qaMctQ75ooqsSmEn95TlsHypN7ZxI9NUMRrRMo22ffl
jZrPBfseJ81igemIYbThQg90miIU/FYd2G952zk4CX/clSszWeONDwSYDm6RfzOJ
TnwUXyC41yoOoeIpo0v20kxKlAFVAgMBAAECgYEA2iFKKMOsj6Co38A7gkitfuOi
1jaryQN6b4CYPEQg+7RAZAEAqnY/qaFm+ufdJ3frCOVTd7QLZzc6SriEHkamJqBf
1ylfevyjHL9FhSprkqMMUF2qrGG6ZEzxMQ1rltymN4xpR0zagyvbKpBOIK5reyIk
4aCsu/mu4+etOctq1CECQQD4T1lmKxp8tQoRKrzbHT0GYEO+zBCBDNe68i8qT9Ox
4dXYWwrzLtA0R8XSmKlyr+kbT7ukOxnN29JgtRR6SFVPAkEA81XEUiEG/TXgIFIA
8NuviVsrc8v7X5HdC4XkmfCFJxCROm5N4XWL4AwE4MVfaSGRKa9QovGzmpeSYKaP
qGBeGwJBAIA62fv8/mywQUakP2sYKk+EnveFAnDiZPXR47GCD9yot3pHadwzrKmS
9wHOfJMRbNwBzPD+5FB+2KHAYZbUi9kCQEBi2FCW9p93aveCW0dgCcGBgyzfs4Ll
OKT857En6EOe6Z6ZYzgd/0XoSD4lW4qY3C04e1CyPcDRDGVQjUCTRzMCQGfuop7q
2zfXztkIfLOxXkiYogjxJGTRRTCF48gyF/WKLhUbR76Gzd6VfDtaoDdpz3hGfy82
VEu5qg9fzchFlEw=
-----END PRIVATE KEY-----

对于参数每 48 个字节用一行 64 字符的 base64 表示,直接解码可以得到十六进制下参数

1
30820277020100300d06092a864886f70d0101010500048202613082025d02010002818100ec0682a113bc51e247c0e01815edbd6b7f3f1a72c543dc2c2c34eaa68c72d43be68a2ab129849fde5396c1f2a4ded9c48f4d50c46b44ca36d9f7e58d9acf05fb1e27cd6281e98861b4e1420f749a2214fc561dd86f79db3938097fdc952b3359e38d0f04980e6e917f33894e7c145f20b8d72a0ea1e229a34bf6d24c4a940155020301000102818100da214a28c3ac8fa0a8dfc03b8248ad7ee3a2d636abc9037a6f80983c4420fbb440640100aa763fa9a166fae7dd2777eb08e55377b40b67373a4ab8841e46a626a05fd7295f7afca31cbf45852a6b92a30c505daaac61ba644cf1310d6b96dca6378c69474cda832bdb2a904e20ae6b7b2224e1a0acbbf9aee3e7ad39cb6ad421024100f84f59662b1a7cb50a112abcdb1d3d066043becc10810cd7baf22f2a4fd3b1e1d5d85b0af32ed03447c5d298a972afe91b4fbba43b19cddbd260b5147a48554f024100f355c4522106fd35e0205200f0dbaf895b2b73cbfb5f91dd0b85e499f0852710913a6e4de1758be00c04e0c55f69219129af50a2f1b39a979260a68fa8605e1b024100803ad9fbfcfe6cb04146a43f6b182a4f849ef7850270e264f5d1e3b1820fdca8b77a4769dc33aca992f701ce7c93116cdc01ccf0fee4507ed8a1c06196d48bd902404062d85096f69f776af7825b476009c181832cdfb382e538a4fce7b127e8439ee99e9963381dff45e8483e255b8a98dc2d387b50b23dc0d10c65508d40934733024067eea29eeadb37d7ced9087cb3b15e4898a208f12464d1453085e3c83217f58a2e151b47be86cdde957c3b5aa03769cf78467f2f36544bb9aa0f5fcdc845944c

使用在线 ASN.1 解码网站:https://lapo.it/asn1js

RSA参数解码结果

如果是损坏的或者是人为混淆过的 PEM,可以用上面这段标准字节流一一对照分析。

Poly-RSA

加密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
flag = list(b'watevr{RSA_from_ikea_is_fun_but_insecure#k20944uehdjfnjd335uro}')
p = 43753
## Univariate Polynomial Ring in y over Finite Field of size p
R.<y> = GF(p)[]

## Analogous to the primes in Z
def gen_irreducable_poly(deg):
while True:
out = R.random_element(degree=deg)
if out.is_irreducible():
return out


## Polynomial "primes"
P = gen_irreducable_poly(ZZ.random_element(length, 2*length))
Q = gen_irreducable_poly(ZZ.random_element(length, 2*length))

## Public exponent key
e = 65537

## Modulus
N = P*Q

## Univariate Quotient Polynomial Ring in x over Finite Field of size 659 with modulus N(x)
S.<x> = R.quotient(N)

## Encrypt
m = S(flag)
c = m^e

输出

1
2
3
4
P=y^65 + 39688*y^64 + 22199*y^63 + 41942*y^62 + 7803*y^61 + 19710*y^60 + 14794*y^59 + 41388*y^58 + 2418*y^57 + 19208*y^56 + 39941*y^55 + 36392*y^54 + 19813*y^53 + 33864*y^52 + 29099*y^51 + 15484*y^50 + 27185*y^49 + 27721*y^48 + 31508*y^47 + 19404*y^46 + 10134*y^45 + 43481*y^44 + 3899*y^43 + 32849*y^42 + 3534*y^41 + 32086*y^40 + 14221*y^39 + 42982*y^38 + 1403*y^37 + 1619*y^36 + 36054*y^35 + 33615*y^34 + 6628*y^33 + 31709*y^32 + 6968*y^31 + 28517*y^30 + 12938*y^29 + 21124*y^28 + 10400*y^27 + 28889*y^26 + 7273*y^25 + 36442*y^24 + 14935*y^23 + 29365*y^22 + 4869*y^21 + 43562*y^20 + 6435*y^19 + 4403*y^18 + 32311*y^17 + 7575*y^16 + 28199*y^15 + 28065*y^14 + 23870*y^13 + 37314*y^12 + 15299*y^11 + 7082*y^10 + 36230*y^9 + 18367*y^8 + 12531*y^7 + 25906*y^6 + 26878*y^5 + 43073*y^4 + 11582*y^3 + 4482*y^2 + 35044*y + 31388
Q=y^112 + 31097*y^111 + 15815*y^110 + 17170*y^109 + 43684*y^108 + 16873*y^107 + 17269*y^106 + 10853*y^105 + 10690*y^104 + 24864*y^103 + 10224*y^102 + 28704*y^101 + 16049*y^100 + 1154*y^99 + 40034*y^98 + 29922*y^97 + 27404*y^96 + 32514*y^95 + 40962*y^94 + 32858*y^93 + 36590*y^92 + 41302*y^91 + 20803*y^90 + 43521*y^89 + 13746*y^88 + 19857*y^87 + 21539*y^86 + 36888*y^85 + 16032*y^84 + 35825*y^83 + 24705*y^82 + 31143*y^81 + 22088*y^80 + 6686*y^79 + 37947*y^78 + 5661*y^77 + 29405*y^76 + 36071*y^75 + 35492*y^74 + 28985*y^73 + 36015*y^72 + 24095*y^71 + 34920*y^70 + 6615*y^69 + 9606*y^68 + 4255*y^67 + 22981*y^66 + 3910*y^65 + 23897*y^64 + 22711*y^63 + 23350*y^62 + 7969*y^61 + 8558*y^60 + 8001*y^59 + 8431*y^58 + 3314*y^57 + 23364*y^56 + 39391*y^55 + 32722*y^54 + 2543*y^53 + 22196*y^52 + 24189*y^51 + 19420*y^50 + 10649*y^49 + 19070*y^48 + 23863*y^47 + 19597*y^46 + 39699*y^45 + 7620*y^44 + 25067*y^43 + 29912*y^42 + 14998*y^41 + 14492*y^40 + 31322*y^39 + 43145*y^38 + 32006*y^37 + 38976*y^36 + 32534*y^35 + 6972*y^34 + 37351*y^33 + 30104*y^32 + 6032*y^31 + 33729*y^30 + 27110*y^29 + 5268*y^28 + 2974*y^27 + 2985*y^26 + 31610*y^25 + 28364*y^24 + 34924*y^23 + 17414*y^22 + 28813*y^21 + 43680*y^20 + 32175*y^19 + 18248*y^18 + 25171*y^17 + 31185*y^16 + 30125*y^15 + 36836*y^14 + 7218*y^13 + 11292*y^12 + 31123*y^11 + 40360*y^10 + 34093*y^9 + 39606*y^8 + 2788*y^7 + 27277*y^6 + 21835*y^5 + 1331*y^4 + 32614*y^3 + 25020*y^2 + 20981*y + 12108
N=34036*y^177 + 23068*y^176 + 13147*y^175 + 36344*y^174 + 10045*y^173 + 41049*y^172 + 17786*y^171 + 16601*y^170 + 7929*y^169 + 37570*y^168 + 990*y^167 + 9622*y^166 + 39273*y^165 + 35284*y^164 + 15632*y^163 + 18850*y^162 + 8800*y^161 + 33148*y^160 + 12147*y^159 + 40487*y^158 + 6407*y^157 + 34111*y^156 + 8446*y^155 + 21908*y^154 + 16812*y^153 + 40624*y^152 + 43506*y^151 + 39116*y^150 + 33011*y^149 + 23914*y^148 + 2210*y^147 + 23196*y^146 + 43359*y^145 + 34455*y^144 + 17684*y^143 + 25262*y^142 + 982*y^141 + 24015*y^140 + 27968*y^139 + 37463*y^138 + 10667*y^137 + 39519*y^136 + 31176*y^135 + 27520*y^134 + 32118*y^133 + 8333*y^132 + 38945*y^131 + 34713*y^130 + 1107*y^129 + 43604*y^128 + 4433*y^127 + 18110*y^126 + 17658*y^125 + 32354*y^124 + 3219*y^123 + 40238*y^122 + 10439*y^121 + 3669*y^120 + 8713*y^119 + 21027*y^118 + 29480*y^117 + 5477*y^116 + 24332*y^115 + 43480*y^114 + 33406*y^113 + 43121*y^112 + 1114*y^111 + 17198*y^110 + 22829*y^109 + 24424*y^108 + 16523*y^107 + 20424*y^106 + 36206*y^105 + 41849*y^104 + 3584*y^103 + 26500*y^102 + 31897*y^101 + 34640*y^100 + 27449*y^99 + 30962*y^98 + 41434*y^97 + 22125*y^96 + 24314*y^95 + 3944*y^94 + 18400*y^93 + 38476*y^92 + 28904*y^91 + 27936*y^90 + 41867*y^89 + 25573*y^88 + 25659*y^87 + 33443*y^86 + 18435*y^85 + 5934*y^84 + 38030*y^83 + 17563*y^82 + 24086*y^81 + 36782*y^80 + 20922*y^79 + 38933*y^78 + 23448*y^77 + 10599*y^76 + 7156*y^75 + 29044*y^74 + 23605*y^73 + 7657*y^72 + 28200*y^71 + 2431*y^70 + 3860*y^69 + 23259*y^68 + 14590*y^67 + 33631*y^66 + 15673*y^65 + 36049*y^64 + 29728*y^63 + 22413*y^62 + 18602*y^61 + 18557*y^60 + 23505*y^59 + 17642*y^58 + 12595*y^57 + 17255*y^56 + 15316*y^55 + 8948*y^54 + 38*y^53 + 40329*y^52 + 9823*y^51 + 5798*y^50 + 6379*y^49 + 8662*y^48 + 34640*y^47 + 38321*y^46 + 18760*y^45 + 13135*y^44 + 15926*y^43 + 34952*y^42 + 28940*y^41 + 13558*y^40 + 42579*y^39 + 38015*y^38 + 33788*y^37 + 12381*y^36 + 195*y^35 + 13709*y^34 + 31500*y^33 + 32994*y^32 + 30486*y^31 + 40414*y^30 + 2578*y^29 + 30525*y^28 + 43067*y^27 + 6195*y^26 + 36288*y^25 + 23236*y^24 + 21493*y^23 + 15808*y^22 + 34500*y^21 + 6390*y^20 + 42994*y^19 + 42151*y^18 + 19248*y^17 + 19291*y^16 + 8124*y^15 + 40161*y^14 + 24726*y^13 + 31874*y^12 + 30272*y^11 + 30761*y^10 + 2296*y^9 + 11017*y^8 + 16559*y^7 + 28949*y^6 + 40499*y^5 + 22377*y^4 + 33628*y^3 + 30598*y^2 + 4386*y + 23814
c=5209*x^176 + 10881*x^175 + 31096*x^174 + 23354*x^173 + 28337*x^172 + 15982*x^171 + 13515*x^170 + 21641*x^169 + 10254*x^168 + 34588*x^167 + 27434*x^166 + 29552*x^165 + 7105*x^164 + 22604*x^163 + 41253*x^162 + 42675*x^161 + 21153*x^160 + 32838*x^159 + 34391*x^158 + 832*x^157 + 720*x^156 + 22883*x^155 + 19236*x^154 + 33772*x^153 + 5020*x^152 + 17943*x^151 + 26967*x^150 + 30847*x^149 + 10306*x^148 + 33966*x^147 + 43255*x^146 + 20342*x^145 + 4474*x^144 + 3490*x^143 + 38033*x^142 + 11224*x^141 + 30565*x^140 + 31967*x^139 + 32382*x^138 + 9759*x^137 + 1030*x^136 + 32122*x^135 + 42614*x^134 + 14280*x^133 + 16533*x^132 + 32676*x^131 + 43070*x^130 + 36009*x^129 + 28497*x^128 + 2940*x^127 + 9747*x^126 + 22758*x^125 + 16615*x^124 + 14086*x^123 + 13038*x^122 + 39603*x^121 + 36260*x^120 + 32502*x^119 + 17619*x^118 + 17700*x^117 + 15083*x^116 + 11311*x^115 + 36496*x^114 + 1300*x^113 + 13601*x^112 + 43425*x^111 + 10376*x^110 + 11551*x^109 + 13684*x^108 + 14955*x^107 + 6661*x^106 + 12674*x^105 + 21534*x^104 + 32132*x^103 + 34135*x^102 + 43684*x^101 + 837*x^100 + 29311*x^99 + 4849*x^98 + 26632*x^97 + 26662*x^96 + 10159*x^95 + 32657*x^94 + 12149*x^93 + 17858*x^92 + 35805*x^91 + 19391*x^90 + 30884*x^89 + 42039*x^88 + 17292*x^87 + 4694*x^86 + 1497*x^85 + 1744*x^84 + 31071*x^83 + 26246*x^82 + 24402*x^81 + 22068*x^80 + 39263*x^79 + 23703*x^78 + 21484*x^77 + 12241*x^76 + 28821*x^75 + 32886*x^74 + 43075*x^73 + 35741*x^72 + 19936*x^71 + 37219*x^70 + 33411*x^69 + 8301*x^68 + 12949*x^67 + 28611*x^66 + 42654*x^65 + 6910*x^64 + 18523*x^63 + 31144*x^62 + 21398*x^61 + 36298*x^60 + 27158*x^59 + 918*x^58 + 38601*x^57 + 4269*x^56 + 5699*x^55 + 36444*x^54 + 34791*x^53 + 37978*x^52 + 32481*x^51 + 8039*x^50 + 11012*x^49 + 11454*x^48 + 30450*x^47 + 1381*x^46 + 32403*x^45 + 8202*x^44 + 8404*x^43 + 37648*x^42 + 43696*x^41 + 34237*x^40 + 36490*x^39 + 41423*x^38 + 35792*x^37 + 36950*x^36 + 31086*x^35 + 38970*x^34 + 12439*x^33 + 7963*x^32 + 16150*x^31 + 11382*x^30 + 3038*x^29 + 20157*x^28 + 23531*x^27 + 32866*x^26 + 5428*x^25 + 21132*x^24 + 13443*x^23 + 28909*x^22 + 42716*x^21 + 6567*x^20 + 24744*x^19 + 8727*x^18 + 14895*x^17 + 28172*x^16 + 30903*x^15 + 26608*x^14 + 27314*x^13 + 42224*x^12 + 42551*x^11 + 37726*x^10 + 11203*x^9 + 36816*x^8 + 5537*x^7 + 20301*x^6 + 17591*x^5 + 41279*x^4 + 7999*x^3 + 33753*x^2 + 34551*x + 9659

解密

1
2
3
4
5
PHI = (p ** P.degree() - 1) * (p ** Q.degree() - 1)
D = inverse_mod(e, PHI)
m = c ** D
flag = bytes(m.list())
print(flag)

输出

1
b'watevr{RSA_from_ikea_is_fun_but_insecure#k20944uehdjfnjd335uro}\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

其中需要注意的是,对于多项式来说,φ(N) 应该是与 N 没有公共多项式的且不高于其幂级的多项式的个数,即 (20)φ(N)=(pow(43753,65)1)(pow(43753,112)1)

RSA 攻击

分解模数N

  1. (推荐) 使用在线网站 http://www.factordb.com/index.php 查询素数分解

  2. 使用 yafu 工具本地分解质因数:

    1
    2
    > ./yafu64.exe
    factor(911934970359)

    回显为:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    fac: factoring 911934970359
    fac: using pretesting plan: normal
    fac: no tune info: using qs/gnfs crossover of 95 digits
    div: primes less than 10000
    fmt: 1000000 iterations
    Total factoring time = 0.0080 seconds


    ***factors found***

    P1 = 3
    P1 = 7
    P2 = 97
    P9 = 447685307

    ans = 1

邻近因数 (p,q) 分解

特征

(p,q) 是邻近的大素数

脚本

也可以使用 yafu 进行分解,这里给出 Sagemath 的脚本

1
2
3
4
5
6
7
8
9
n=177606504836499246970959030226871608885969321778211051080524634084516973331441644993898029573612290095853069264036530459253652875586267946877831055147546910227100566496658148381834683037366134553848011903251252726474047661274223137727688689535823533046778793131902143444408735610821167838717488859902242863683
c=1457390378511382354771000540945361168984775052693073641682375071407490851289703070905749525830483035988737117653971428424612332020925926617395558868160380601912498299922825914229510166957910451841730028919883807634489834128830801407228447221775264711349928156290102782374379406719292116047581560530382210049
e=65537
pp = isqrt(n)
qq = pp
while pp * qq != n:
pp = next_prime(pp)
qq = n // pp
p, q = pp, qq

共模数攻击

特征

若干次加密,e不同,N相同,m相同。

原理

由于使用公钥对 (N,e1)(N,e2) 加密明文m

1
2
c1 = pow(m, e1, N)
c2 = pow(m, e2, N)

故使用私钥对 (N,d1)(N,d2) 可以得到相同明文m

1
2
m = pow(c1, d1, N)
m = pow(c2, d2, N)

这时我们只需已知c1,c2,e1,e2,N则可以绕过d1,d2直接恢复明文m

信息安全数学基础证明如下:

假设公钥共模且互素,则有 (21)gcd(e1,e2)=1(22)e1x+e2y=1 其中x,y皆为整数,一正一负。

利用扩展欧几里得算法可以求得解(x,y),在这里不妨设x为正,y为负,利用模运算性质得 (23)c1xc2y=me1xme2y=me1x+e2y=m(modn)

特别地,当 gcd(e1,e2)=g 较小时,也可以构造为: (24)c1xc2y=me1xme2y=me1x+e2y=mg(modn) 随后进行低加密指数攻击。

实现

1
2
3
4
5
6
7
8
9
from gmpy2 import gcdext
n = 0xa6241c28743fbbe4f2f67cee7121497f622fd81947af30f327fb028445b39c2d517ba7fdcb5f6ac9e6217205f8ec9576bdec7a0faef221c29291c784eed393cd95eb0d358d2a1a35dbff05d6fa0cc597f672dcfbeecbb14bd1462cb6ba4f465f30f22e595c36e6282c3e426831d30f0479ee18b870ab658a54571774d25d6875
e1 = 0x3045
e2 = 0xff4d
c1 = 0x5d1e39bc751108ec0a1397d79e63c013d238915d13380ae649e84d7d85ebcffbbc35ebb18d2218ccbc5409290dfa8a4847e5923c3420e83b1a9d7aa67190dc0d34711cce261665c64c28ed2834394d4b181926febf7eb685f9ce81f36c7fb72798da3a14a123287171d26e084948aab0fba81c53f10b5696fc291006254ee690
c2 = 0x3d90f2bec4fe02d8ce4cece3ddb6baed99337f7e6856eef255445741b5cfe378390f058679d70236e51be4746db4c207f274c40b092e24f8c155a0957867e84dca48e27980af488d2615a280c6eadec2f1d30b95653b1ee3135e2edff100dd2c529994f846722f811348b082d0bec7cfab579a4bd0ab789928b1bebed68d628f
g, r, s = gcdext(e1, e2)
m = pow(c1, r, n) * pow(c2, s, n) % n
print(long_to_bytes(int(m)))

公约数攻击

特征

多个n,均不相同,并且都是2048bit,4096bit级别,并且明文都没什么联系。

原理

使用公约数求出共同的素数因子

实现

1
2
3
4
5
6
import gmpy2
n1 = 9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2 = 13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
p = gmpy2.gcd(n1, n2)
q1 = n1 / p
q2 = n2 / p

Nφ(N) 分解

原理

我们已知 (25)N=pq(26)φ(N)=(p1)(q1)(27)=pq(p+q)+1(28)=N(p+q)+1 我们不妨构建一个二次方程,这个二次方程的两根之和为 x1+x2=p+q,两根之积为 x1x2=pq,即方程: (29)x2+(φ(N)N1)x+N=0 该方程的解即为 (p,q)

特别地,如果给予的是 Nkφ(N),也有可能是 kφ(N)=ed1

我们可以计算出 (30)k=kφ(N)N+1=kp+q+1N+1 其中一定存在 (31)p+q+1N=1 所以 k 一定就在 kφ(N)N 附近。

N 位数足够大时,k=kφ(N)N+1 是一定的。

低加密指数攻击

特征

em都特小,例如e=3

原理

在 RSA 中 e 也称为加密指数。

由于 e 是可以随意选取的,选取小一点的 e 可以缩短加密时间,但是选取不当的话,就会造成安全问题。

m3<n,即c=m3

m3>n但并非m3n,即c=(m3+in) mod n,其中i是我们需要爆破的系数

实现

  • m3<n

    1
    2
    3
    4
    5
    6
    7
    8
    9
    import gmpy2
    n= 22885480907469109159947272333565375109310485067211461543881386718201442106967914852474989176175269612229966461160065872310916096148216253429849921988412342732706875998100337754561586600637594798877898552625378551427864501926224989873772743227733285336042475675299391051376624685754547818835551263597996620383338263448888107691240136257201191331617560711786674975909597833383395574686942099700631002290836152972352041024137872983284691831292216787307841877839674258086005814225532597955826353796634417780156185485054141684249037538570742860026295194559710972266059844824388916869414355952432189722465103299013237588737
    e = 3
    c= 15685364647213619014219110070569189770745535885901269792039052046431067708991036961644224230125219358149236447900927116989931929305133870392430610563331490276096858863490412102016758082433435355613099047001069687409209484751075897343335693872741
    m, flag = gmpy2.iroot(c, e)
    if flag:
    print(f"m={m}")
    else:
    print("could not decode m")
  • m3>n但并非m3n (这里需要跑比较久)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    import gmpy2
    n = 114976915747243387792157708464120735018971336213935438953074748276198282761939060395482051056351068439137722626185590043024556656813730840050547350912425438364703854627760482842307943026011880815011654341047422453012558617703411700393668892701036222135444420377515575624398723436532681305293727164639582093389
    e = 3
    c = 5828813410620741112500628876643872258919868379601617907887884191584237969605489971465692568848339200057188383649365078832766143513766368216471491824042974016773526107276856706832404477882581400769791378958901067683158857990261489285951805740071223765359992165262854641069674603160977034446644199945940251030
    i = 0
    while 1:
    m, flag = gmpy2.iroot(c + i * n, e)
    if flag:
    print(f"m={m}")
    break
    i += 1

e=1 攻击

实现

1
2
3
4
5
6
7
8
9
n = 0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd
e = 0x1
c = 0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d
i = 0
# i 可以取很多
while i < 10:
m = c + i * n
print(m)
i += 1

低加密指数广播攻击

特征

三组加密的参数和明密文,其中题目很明确地能告诉你这三组的明文都是一样的,并且e都取了一个较小的数字。

原理

如果选取的加密指数较低,并且使用了相同的加密指数给一个接受者的群发送相同的信息,那么可以进行广播攻击得到明文。

例如当e=3时,有以下等式成立: (32)c1=pow(m,e,n1)c2=pow(m,e,n2)c3=pow(m,e,n3) 对上列等式运用中国剩余定理,得到 (33)cx=pow(m,e,n1×n2×n3×)

随后再进行低加密指数攻击。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
from functools import reduce
def CRT(clist, nlist):
N = reduce(lambda x, y: x * y, nlist)
result = 0
for c, n in zip(clist, nlist):
m = N // n
d, r, s = gmpy2.gcdext(n, m)
if d != 1: raise Exception("Input not pairwise co-prime")
result += c * s * m
return result % N, N
e = 9
n = [142782424368849674771976671955176187834932417027468006479038058385550042422280158726561712259205616626939123504489410624745195777853423961104590708231562726165590769610040722589287393102301338152085670464005026301781192671834390892019478189768725018303217559795377795540494239283891894830166363576205812991157, 153610425077816156109768509904751446801233412970601397035720458311275245730833227428213917577405780162151444202393431444812010569489900435979730559895340377469612234558042643742219128033827948585534761030527275423811282367831985007507137144308704413007806012914286105842311420933479771294576841956749281552971, 152540067782701001222493009941492423063369171831039847414320547494725020441901272486665728360741395415762864872737675660423920609681185809510355937534756399208661762715484879562585724584849261266873624875852300611683382543315580370484972470694466195837255994159609193239840228218925381488410059939975556977947, 125842716702134814646356078531900645012495638692517778270527426844383063904041812273637776798591687732598509470005151551320457132061693618473039437320011446697406190781306264437609046721508738109650829547010385875425097336266103994639126319889016342284747700714199556143378526590058467791687837422897022829661, 116144389285266462769913139639175922392318396923181100785008570884082681963637784423143843845816350379438789947802939701820129805341796427821894273985551331666719808355412080909245720551238149511778060242720419584504473490216670437024863860559347959698828131475160058721701582089480924088773887932997353631767, 127833907448946785858374094953899556339175475846831397383049660262333005992005484987913355932559627279178940862787593749842796469355336182379062826441222705075178971785791223706944120681105575965622931327112817747065200324610697178273898956820957640413744954233327851461318200323486469677469950386824833536523, 130561613227079478921314550968562766645507834694262831586725464124109153306162445639759476845681271537955934718244296904503168256991962908095007040044300188572466395275317838178325500238288302672390013747102961340256309124310478931896245221622317302428447389760864327859640573452084295225059466376349115703119, 115953389401040751013569404909249958538962411171147823610874077094621794755967854844224923689925397631692572916641171075740839099217316101334941033937183815345038898177087515909675028366437302462022970987947264115373697445950951595479758872029099661065186221250394358255523574834723958546450323357472451930993, 143437107845384843564651522639125300763388830136500260725097766445883003928355325003575359566631064630487365774344508496878731109174874449170057678821440711511966073934025028100604234445470976333825866939923998344367645612128590820812489407412175198698290167077116185959180877334222693344630253253476594907313]
c = [85033868418784308573673709960700777350314426427677627319697346811123742342359072170220428874952996988431950989321281905284522596263957356289624365171732095210045916218066135140320107686084053271623461104022705353814233772164502775939590711842361956121603943483040254727995655776263673058788416722141673409688, 66065963470666895005407449599703926269325406456711861190876894466341571726360462706664546294453572319565476664348345756905411939632955966517708138047546806602828064213238537646393524578984547577761559965654539771172357089802682793169968961304179886652390277814477825753096636750388350662980872556701402397564, 116011740820520887443111656288411611070614127688662643257265381793048354928820176624229624692124188995846076431510548507016903260774215950803926107831505634778278712070141663189086436127990584944132764896694777031370995058271038329228336417590284517922855284619653301817355115583540545182119702335431334401666, 97640420284096094887471273365295984332267897927392169402918423863919914002451127544715668846623138003564829254309568918651163254043205129883843425179687841236818720463784828905460885026290909768599562386370732119591181513319548915478512030197629196018254041500662654260834562708620760373487652389789200792120, 8112507653841374573057048967617108909055624101437903775740427861003476480616929517639719198652146909660899632120639789106782550275648578142883715280547602249589837441805676364041484345030575130408744621981440093280624046635769338568542048839419939250444929802135605724150484414516536378791500915047844188300, 36792148360808115566234645242678223867680969786675055638670907933041180936164293809961667801099516457636164692292891528415720085345494773373966277807505798679784807614784581861287048096977968620964436947452527540958289441390882589051225367658014709290392321808926567572528170531844664734909469690750971883323, 53043093283305492238903255767698153246673671181809989362223466090875767705978690531154079519999671834688647277179370374802495005937892824566602423646978168777735383632928274082669949750078161820002768640908750005814934158829006019656592134357897586040866207754535586785064545866404380204728594863102313407789, 88499407133762624445946519155722583633934260410706930537441122463087556094734626189377091740335667052378955691250910459790202385799502439716173363179773811920751410726795431402796346647688144853156900427797933862087074385441977254140336390678022955770879265490567987868532251217565094093318626424653599450992, 138337520305048557335599940473834485492131424901034295018189264168040969172072024612859307499682986987325414798210700710891033749119834960687318156171051379643844580970963540418974136891389303624057726575516576726845229494107327508855516437230240365759885913142671816868762838801720492804671259709458388192984]
x, n = CRT(c, n)
m, flag = gmpy2.iroot(x, e)
if flag:
print(f"m={m}")
else:
print("could not decode m")

扩展

如果每个明文都是线性映射后才加密的,即 (34)ci=(aim+bi)e(modni) 这个时候将转化为 Håstad 问题。

我们手里有 e 个方程,如果 e 个模数都是互质的,使用中国剩余定理得到一个多项式,此多项式必然仅有唯一解 m

生成代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from Crypto.Util.number import getPrime
import random
from math import gcd

def gen_prime(e, nbits = 128):
while True:
p = getPrime(nbits)
q = getPrime(nbits)
phi = (p - 1) * (q - 1)
if gcd(e, phi) == 1:
break
return p, q

m = 12345678909876543210123456789
e = 5
cnt = e
A = [random.getrandbits(32) for i in range(cnt)]
B = [random.getrandbits(32) for i in range(cnt)]

Ns = []
Cs = []
for i in range(cnt):
p, q = gen_prime(e)
n = p * q
assert m < n
Ns.append(n)
c = pow(A[i] * m + B[i], e, n)
Cs.append(c)

print(f'{Ns = }')
print(f'{A = }')
print(f'{B = }')
print(f'{e = }')
print(f'{Cs = }')

求解代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from sage.all import *

Ns = [54083343375234662200099757715655786732319849776299053669258471280425520446563, 57451400898890261568311471323401021425649134079480527619499816018137641523101, 62361269389224974168958185709758463920746172022272059244582082311163541212863, 68958389071922182719189344062138335193303205914947842087348429706174374534933, 76868740862563485837918666110296168275535830960508353132527603298274280231651]
A = [1783329078, 4116509288, 1610410794, 937258067, 3088738863]
B = [1926001878, 88533882, 4144178569, 2673089177, 1693394020]
e = 5
Cs = [36267245963551737844539070991485903279725583484166321759824831482629419234481, 28560773802819161789081370635071282975025711430638171046096333084125012412026, 51931278891526114578870060444759610215259255866146720938080914934508882168071, 13232544162120977310144792467208197733399011581100174942873170595969028745121, 37591263432669152518061731513326056670793427134029106244119790273766985095248]

PR = PolynomialRing(ZZ, 'x')
x = PR.gen()

Fs = []
for i in range(cnt):
f = (A[i] * x + B[i]) ** e - Cs[i]
Fs.append(f)
F = crt(Fs, Ns)
M = prod(Ns)
FF = F.change_ring(Zmod(M))
m = FF.monic().small_roots()
print(m)

扩展的扩展

在 Håstad 问题中,每个多项式的阶数是相同的,如果每个多项式的阶数不同(即加密用的 e 不同),这将化为 SMUPE 问题。

这个时候我们只需要将每个多项式的阶数统一即可。

低解密指数攻击 (Wiener Attack)

特征

e特别大

原理

与低加密指数相同,低解密指数可以加快解密的过程,但是也带来了安全问题。种基于连分数(一个数论当中的问题)的特殊攻击类型就可以危害 RSA 的安全。此时需要满足:q<p<2q。如果满足上述条件,通过 Wiener Attack (维纳攻击) 可以在多项式时间中分解N。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import gmpy2
from Crypto.Util.number import long_to_bytes

def transform(x, y): # 使用辗转相处将分数 x/y 转为连分数的形式
res = []
while y:
res.append(x//y)
x, y = y, x % y
return res


def continued_fraction(sub_res):
numerator, denominator = 1, 0
for i in sub_res[::-1]: # 从sublist的后面往前循环
denominator, numerator = numerator, i*numerator+denominator
return denominator, numerator # 得到渐进分数的分母和分子,并返回


# 求解每个渐进分数
def sub_fraction(x, y):
res = transform(x, y)
# 将连分数的结果逐一截取以求渐进分数
res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res)))))
return res


def get_pq(a, b, c): # 由p+q和pq的值通过维达定理来求解p和q
par = gmpy2.isqrt(b*b-4*a*c) # 由上述可得,开根号一定是整数,因为有解
x1, x2 = (-b+par)//(2*a), (-b-par)//(2*a)
return x1, x2


def wienerAttack(e, n):
for (d, k) in sub_fraction(e, n): # 用一个for循环来注意试探e/n的连续函数的渐进分数,直到找到一个满足条件的渐进分数
if k == 0: # 可能会出现连分数的第一个为0的情况,排除
continue
if (e*d-1) % k != 0: # ed=1 (mod φ(n)) 因此如果找到了d的话,(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
continue

phi = (e*d-1)//k # 这个结果就是 φ(n)
px, qy = get_pq(1, n-phi+1, n)
if px*qy == n:
p, q = abs(int(px)), abs(int(qy)) # 可能会得到两个负数,负负得正未尝不会出现
# 求ed=1 (mod φ(n))的结果,也就是e关于 φ(n)的乘法逆元d
d = gmpy2.invert(e, (p-1)*(q-1))
return d
print("该方法不适用")


n = 507419170088344932990702256911694788408493968749527614421614568612944144764889717229444020813658893362983714454159980719026366361318789415279417172858536381938870379267670180128174798344744371725609827872339512302232610590888649555446972990419313445687852636305518801236132032618350847705234643521557851434711389664130274468354405273873218264222293858509477860634889001898462547712800153111774564939279190835857445378261920532206352364005840238252284065587291779196975457288580812526597185332036342330147250312262816994625317482869849388424397437470502449815132000588425028055964432298176942124697105509057090546600330760364385753313923003549670107599757996810939165300581847068233156887269181096893089415302163770884312255957584660964506028002922164767453287973102961910781312351686488047510932997937700597992705557881172640175117476017503918294534205898046483981707558521558992058512940087192655700351675718815723840568640509355338482631416345193176708501897458649841539192993142790402734898948352382350766125000186026261167277014748183012844440603384989647664190074853086693408529737767147592432979469020671772152652865219092597717869942730499507426269170189547020660681363276871874469322437194397171763927907099922324375991793759
e = 77310199867448677782081572109343472783781135641712597643597122591443011229091533516758925238949755491395489408922437493670252550920826641442189683907973926843505436730014899918587477913032286153545247063493885982941194996251799882984145155733050069564485120660716110828110738784644223519725613280140006783618393995138076030616463398284819550627612102010214315235269945251741407899692274978642663650687157736417831290404871181902463904311095448368498432147292938825418930527188720696497596867575843476810225152659244529481480993843168383016583068747733118703000287423374094051895724494193455175131120243097065270804457787026492578916584536863548445813916819417857064037664101684455000184987531252344582899589746272173970083733130106407810619258077266603898529285634495710846838011858287024329514491058790557305041389614650730267774482954666726949886313386881066593946789460028399523245777171320319444673551268379126203862576627540177888290265714418064334752499940587750374552330008143708562065940245637685833371348603338834447212248648869514585047871442060412622164276894766238383894693759347590977926306581080390685360615407766600573527565016914830132066428454738135380178959590692145577418811677639050929791996313180297924833690095
c = 165251729917394529793163344300848992394021337429474789711805041655116845722480301677817165053253655027459227404782607373107477419083333844871948673626672704233977397989843349633720167495862807995411682262559392496273163155214888276398332204954185252030616473235814999366132031184631541209554169938146205402400412307638567132128690379079483633171535375278689326189057930259534983374296873110199636558962144635514392282351103900375366360933088605794654279480277782805401749872568584335215630740265944133347038070337891035560658434763924576508969938866566235926587685108811154229747423410476421860059769485356567301897413767088823807510568561254627099309752215808220067495561412081320541540679503218232020279947159175547517811501280846596226165148013762293861131544331444165070186672186027410082671602892508739473724143698396105392623164025712124329254933353509384748403154342322725203183050328143736631333990445537119855865348221215277608372952942702104088940952142851523651639574409075484106857403651453121036577767672430612728022444370874223001778580387635197325043524719396707713385963432915855227152371800527536048555551237729690663544828830627192867570345853910196397851763591543484023134551876591248557980182981967782409054277224
d = wienerAttack(e, n)
m = pow(c, d, n)

也可以使用 https://github.com/pablocelayes/rsa-wiener-attack 的脚本

dp & dq 泄露

特征

题目仅给出p,q,dp,dq,c,不给公钥e

原理

已知 dp=inverse(e,p1)dq=inverse(e,q1),使用 CRT 可得 d=inverse(e,(p1)(q1))

m 也是同理

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
def dec(dp, dq, p, q, c):
InvQ = gmpy2.invert(q,p)
mp = pow(c,dp,p)
mq = pow(c,dq,q)
m = (((mp - mq) * InvQ) % p) * q + mq
return m

p=0xf85d730bbf09033a75379e58a8465f8048b8516f8105ce2879ce774241305b6eb4ea506b61eb7e376d4fcd425c76e80cb748ebfaf3a852b5cf3119f028cc5971
q=0xc1f34b4f826f91c5d68c5751c9af830bc770467a68699991be6e847c29c13170110ccd5e855710950abab2694b6ac730141152758acbeca0c5a51889cbe84d57
dp=0xf7b885a246a59fa1b3fe88a2971cb1ee8b19c4a7f9c1a791b9845471320220803854a967a1a03820e297c0fc1aabc2e1c40228d50228766ebebc93c97577f511
dq=0x865fe807b8595067ff93d053cc269be6a75134a34e800b741cba39744501a31cffd31cdea6078267a0bd652aeaa39a49c73d9121fafdfa7e1131a764a12fdb95
c=0xae05e0c34e2ba4ca3536987cc2cfc3f1f7f53190164d0ac50b44832f0e7224c6fdeebd2c91e3991e7d179c26b1b997295dc9724925ba431f527fba212703a0d14a34ce133661ae0b6001ee326303d6ccdc27dbd94e0987fae25a84f197c1535bdac9094bfb3846b7ca696b2e5082bea7bff804da275772ca05dd51b185a4fc30

m = dec(dp,dq,p,q,c)

dp 泄露

原理

已知 (35)dpe1(modp1) 由费马小定理可知,对于任意整数 a 都有 (36)aedp=ak(p1)a(modp)=a+kp 那么有 (37)gcd(aedpa,n)=p 由此找到 p 分解 n

代码

1
2
3
4
5
6
7
8
9
10
11
12
from math import gcd

n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
e = 65537
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

p = gcd(pow(2, e * dp, n) - 2, n)
assert n % p == 0
q = n // p
d = pow(e, -1, (p - 1) * (q - 1))
m = pow(c, d, n)

扩展

若是仅知道 e,dp,此时有 (38)edp1(modp1)=1+kp(p1) 同时也一定有 (39)ed1(modφ(n))=1+kφ(n) 其中定然有 φ(n)|(p1),故 (40)edpkp(p1)1(modφ(n)) 变形得 (41)edp=1+kφ(n)+kp(p1)(42)=1+(kφ(np)+kp)(p1)(43)=1+K(p1) 由大小比例关系可知,dp<p1 必然有 (44)K<ee 较小时可以爆破 K 直接求解得到 p1

扩展代码

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import isPrime

e = 65537
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

for i in range(1, e + 1):
if (dp * e - 1) % i == 0:
p = ((dp * e - 1) // i) + 1
if isPrime(p):
print(f'{p = }')

d 泄露攻击

原理

已知 (n,e,d),第一种方式可以将问题转化为已知 (n,φ(n)) 的问题,在上文中有原理解释。

第二种方式是,我们将 kφ(n) 表示为 (45)ed1=kφ(n)=2st 即奇数 t 与一个偶数 2s 相乘。

可以证明得到对于至少一半的 aZn,存在一个 i[1,s] 满足 (46)r=a2i1t±1(modn)(47)a2it=1(modn) 那么此时,p=gcd(r1,n)n 的一个非平凡因子。

代码

已知 (n,φ(n)) 问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
e = 13521
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913

def n_with_kphi(n, e, d):
kphi = e * d - 1

k = kphi // n
while kphi % k != 0:
k += 1
phi = kphi // k
# 构建方程 x^2+(\varphi(N)-N-1)x+N=0
a = 1
b = phi - n - 1
c = n
delta = b ** 2 - 4 * a * c
if delta < 0:
return 0, 0
from math import isqrt
sqrt_delta = isqrt(delta)
p = (-b + sqrt_delta) // (2 * a)
q = (-b - sqrt_delta) // (2 * a)
if p * q != n:
return 0, 0
return p, q

print(n_with_kphi(n, e, d))

第二种暴力破解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 80642592772746398646558097588687958541171131704233319344980232942965050635113860017117519166348100569115174644678997805783380130114530824798808098237628247236574959152847903491509751809336988273823686988619679739640305091291330211169194377552925908412183162787327977125388852329089751737463948165202565859373
e = 13521
d = 14218766449983537783699024084862960813708451888387858392014856544340557703876299258990323621963898510226357248200187173211121827541826897886277531706124228848229095880229718049075745233893843373402201077890407507625110061976931591596708901741146750809962128820611844426759462132623616118530705745098783140913

def kphi_2st(n, e, d):
kphi = e * d - 1
s = 0
while kphi % (2 ** s) == 0:
s += 1
from random import randint
from math import gcd
for _ in range(e):
a = randint(2, n - 1)
for i in range(1, s + 1):
r = pow(a, kphi // (2 ** i), n)
p = gcd(r - 1, n)
if 1 < p < n and n % p == 0:
return p, n // p

print(kphi_2st(n, e, d))

已知 p 高位

原理

已知 p 的一半高位时,可以使用 Coppersmith 方法分解 N

其中在 Coppersmith 方法里,Xp 未知的位数范围,p>Nβ

1024 位需要知道 570 位

512 位需要知道 300 位

实例

1
2
3
4
5
6
7
8
9
p3 = getPrime(512)
q3 = getPrime(512)
N3 = p3*q3
print pow(msg3,e3,N3)
print (e3,N3)
print p3>>200

# phigh = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
# N = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147

利用 Sagemath 中 small_roots 的参数,变成 Coppersmith 方法求解低位值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
phigh = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
N = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
# 未知的位数
kbits = 200
# beta值按需修改
beta = 0.5

P.<x> = Zmod(N)[]
f = x + (phigh << kbits)
p0 = f.small_roots(X=2**kbits, beta=beta)
assert(p0)
p0 = p0[0]
p = Integer(f(p0))
print(p)

已知 p 低位

原理

假设已知 pk 个低位,那么有: (48)p(mod2k)=p0(49)p=p0+α2k 两边同乘,得到 (50)n=p0q+αq2k(51)np01=q+αqp012k 两边同余,得到: (52)q(mod2k)=np01(mod2k) 换句话说,知道 p 低位,即可求 q 低位。

eφ(n) 不互素

原理

先考虑对于素数 p,满足 (53)cp=me(modp) 那么有 dp=e1(modp),使得 (54)mpcpdp(modp)m(modp)gcd(e,p1)1 时,此时无法直接求出 dp(或者说存在多个 mp),那么我们令 k=gcd(e,p1),那么 gcd(e/k,p1)=1,那么 (55)dp=(e/k)1(modp)(56)mpkcpdp(modp) 此时相当于变为了加密指数为 k 的 RSA 问题,可以使用 AMM 算法求解 mp

那么对于 n=pq,我们首先计算出 mpmq 后,对其进行 CRT 即可求出 m

需要注意 ed=1+kφ(N),如果说 g=gcd(e,φ(N)) 恰好为 k 的因子,可以考虑求解 d=e1(modφ(N)/g),使得其满足 ed=1+kgφ(N),一样可以求解明文。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import itertools

def AMM(delta: int, r: int, q: int, all: bool = False):
"""
使用AMM算法进行有限域开根,即求delta^(1/r)%q下的解

`Parameter`:
delta - 底数
r - 根指数
q - 模数
all - 是否返回所有解

`Return`:
delta^(1/r)%q下的一个根
"""

if (q - 1) % r != 0:
raise Exception("使用AMM算法需要满足e||(q-1)")

# step 1
Fq = GF(q)
delta = Fq(delta)
rho = Fq.random_element()

# step 2
while rho ** ((q - 1) // r) == 1:
rho = Fq.random_element()

# step 3
# step 3.1
t = 0
s = q - 1
while s % r == 0:
t += 1
s //= r
# step 3.2
k = 1
while (k * s + 1) % r != 0:
k += 1
alpha = (k * s + 1) // r
# step 3.3
a = rho ** (r ** t - 1 * s)
b = delta ** (r * alpha - 1)
c = rho ** s
h = 1

# step 4
for i in range(1, t):
d = b ** pow(r, t - 1 - i, q - 1)
j = 0 if d == 1 else -d.log(a)
b *= (c ** r) ** j
h *= c ** j
c **= r

# step 5
root = int(delta ** alpha * h)
if not all:
return root

# if all is True, generate all roots to return
# 2 ^ (q - 1) == 1 (mod q) because of Fermat's little theorem
g = pow(2, (q - 1) // r, q)
# find all primitive i-th roots of 1
ith_roots = [pow(g, i, q) for i in range(r)]
return [int(root * ith_root % q) for ith_root in ith_roots]

def decrypt(c, e, p):
k = gcd(e, p - 1)
dp = pow(e // k, -1, p - 1)
mp = pow(c, dp, p)
return list(set(AMM(mp, k, p, True)))

p = 90015842079287188147863599089252975950229149674532065188179308662941668349067
q = 115639966729427613784046359856154071033236356854800852136894409690977637028073
e = 458759
c = 9377489940941407443668888914142468523442868076408679603369421619879641628020535221060883892082291144102991625695716628752564422493350476912185008866541091

print(f'{gcd(e, p - 1) = }')
print(f'{gcd(e, q - 1) = }')

mps = decrypt(c, e, p)
mqs = decrypt(c, e, q)
print(f'{mps = }')
print(f'{mqs = }')
ms = []
for mp, mq in itertools.product(mps, mqs):
ms.append(CRT([mp, mq], [p, q]))
print(f'{ms = }')

p,q 高位相同

特征

已知 n,其中 |pq| 较小,p,q 数量位知道

实例

1
2
3
4
nbits = 1024
p = getPrime(nbits // 2)
q = next_prime(p + (1 << int(nbits * beta)))
n = p * q

其中

1
2
n = 122774778628333786198247673730199699244621671207929503475974934116435291656353398717362903500544713183492877018211738292001516168567879903073296829793548881467270228989482723510323780292947403861546283099122868428902480999485625751961457245487615479377459707992802193391975415447673215862245349068018710525679
beta = 0.44

不妨看作 n=p(p+(1<<int(nbitsbeta))),则可以将 p 的近似值求出来。

这时再进行小范围的爆破即可。(这里需要注意到,近似值与真实值相比是要偏大的,需要使用 previous_prime 函数)

sagemath 脚本如下:

1
2
3
4
5
6
7
8
delta = (1 << int(nbits * beta))
R = RealField(1000)
p = polygen(R)
f = p * (p + delta) - n
p = int(f.roots()[1][0])

while n % p != 0:
p = previous_prime(p)

这样就将 p 爆破出来了。

简单填充攻击

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import bytes_to_long
from secret import flag, n


def pad(x):
return x + b"\x00" * (128 - len(x))

flag = flag[7:-1]

assert len(flag) == 16

flag = pad(flag)

m = bytes_to_long(flag)

e = 0x10001

c = pow(m, e, n)

f = open("output.txt", "w")

print(f"n = {n}", file=f)
print(f"e = {e}", file=f)
print(f"c = {c}", file=f)

n = 20143874513891625472763023083725333814544365923300648765753585512236262936134576226420495156390118451084859695988018681103828733472481714477702312584392200607513775527941225389450524064860609500522646820403150136601325693755011504371254765148925814568051337093873243247759130508598378247848927825303243080348476280520682747234144016534355268883431 e = 65537 c = 9099248209700870107517981697995437593126643973286742880366239649474438147247165218637687381898125380392681666447352387825995403531162271411514111581358141144178855022212666392579294107956774766000410956462804204065293225382573948622209661112442721208408763210528401826636309622296148093801229149917160087959002855064445785159864465696643561701308

实现

当实际明文m<p时可以恢复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from gmpy2 import gcd, invert
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long

# 仅在p域下

def dec(n, e, phi, c):
d = invert(e, phi)
return pow(c, d, n)


if __name__ == "__main__":
p = 297342668339361548416629796745639177971
q = 67746329937757624632404631102047546126139910162127525807142364896504844830533422758326696949629668349819199912570222748973935637740283799230746144014458722401719184655996325043824137789180083286215748548298177270209171461643103260188864468982281090005047122016817287399362453731379535534001682626445843123261

n = p * q
phi = (p - 1) * (q - 1)

e = 0x10001
c = 9099248209700870107517981697995437593126643973286742880366239649474438147247165218637687381898125380392681666447352387825995403531162271411514111581358141144178855022212666392579294107956774766000410956462804204065293225382573948622209661112442721208408763210528401826636309622296148093801229149917160087959002855064445785159864465696643561701308

m = dec(n, e, p-1, c)
t = 256**112
t = invert(t, p)
m = m*t % p
print(long_to_bytes(int(m)).decode())

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import gmpy2

def CRT(r,d):
M = 1
l = len(r)
for i in range(0,l):
M = d[i] * M
x = 0
for i in range(0,l):
md = M//d[i]
x = (x + gmpy2.invert(md, d[i]) * md *r[i] )%M
return int(M+x% M)%M

p = 109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453

e1 = 15218928658178
q1=127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
c1 = 262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
n1 = p*q1

e2 = 381791429275130
q2 = 114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c2 = 7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
n2 = p*q2

phi1=(p-1)*(q1-1)
phi2=(p-1)*(q2-1)

xx1=gmpy2.gcd(e1,phi1) # xx1=14
xx2=gmpy2.gcd(e2,phi2) # xx2=14

d1=gmpy2.invert(e1//xx1,phi1)
d2=gmpy2.invert(e2//xx2,phi2)

nn=[]
aa=[]

nn.append(q1)
nn.append(q2)
a1=gmpy2.powmod(c1,d1,p*q1)%q1
a2=gmpy2.powmod(c2,d2,p*q2)%q2
aa.append(a1)
aa.append(a2)

last = CRT(aa,nn)
new_e=7
new_phi=(q1-1)*(q2-1)

new_d=gmpy2.invert(new_e,new_phi)
m_2=gmpy2.powmod(last,new_d,q1*q2)
m=gmpy2.iroot(m_2,2)[0]

Rabin 攻击

特征

e=2

原理

  • 计算出 mpmq(57)mp=cmodp(58)mq=cmodq

  • 利用扩展欧几里得算法计算出 ypyq (59)yp·p+yq·q=1

  • 然后解得四个明文: (60){a=(yp·p·mq+yq·q·mp)(modn)b=nac=(yp·p·mqyq·q·mp)(modn)d=nc

  • 其中,如果p,q是形为4k+3的不同素数,即pq3(mod4),则 (61)mp=c14(p+1)(modp)mq=c14(q+1)(modq)

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gmpy2
n=523798549
p=10663
q=49123
e=2
c=162853095
a,inv_q ,inv_p= gmpy2.gcdext(q,p)
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c)
for i in(a, b, c, d):
print(i)

最小根求解

原理

Coppersmith 定理指出在一个 e 阶的 mod n 多项式 f(x) 中,如果有一个根小于 n1e ,就可以运用一个 O(log n) 的算法求出这些根。

这个定理可以应用于 RSA 算法。如果 e=3 并且在明文当中只有三分之二的比特是已知的,这种算法可以求出明文中所有的比特。

代码

一般来说我们借助 Sagemath 中的 small_roots 函数替代求解。

p,q 存在相同 module 攻击

特征

p,q 的生成需要借助某共同的 module M 进行生成

代码

直接使用他人的脚本,roca 攻击:https://github.com/jvdsn/crypto-attacks/blob/c26872bdac2e2d95c5be00e6e593c891c849f446/attacks/factorization/roca.py

论文《The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli》指出该攻击方式中 m,t 的选择依据为 N 的位数。

nbits m t
512 5 6
1024 4 5
2048 6 7
3072 25 26
4096 7 8

有限域开根

特征

e 较小。

或者 gcd(e,φ(p))1,即 eφ(p) 不互素的情况。

原理

e 较小时,有限域开方速度较快。

同时运用到了高次剩余的定理:

对于同余式 Xnd(modp)

n|p1 时,满足 (62)dp1n1(modp) 才有解,此时解数为 n

n 无法整除 p1,满足 (63)dp1k1(modp) 其中 k=gcd(n,p1),此时解数为 k

而我们需要求解的便是 mec(modn)

我们可以在 p,q 域中分别开方得到同余式组(加快求解速度) (64){m1=ce(modp)m2=ce(modq) 然后利用 CRT 得到 (65){m1=ce(modp)m2=ce(modq)m=ce(modn) 但因为有多解,所以需要进行验证。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solve(p, q, e, c):
P.<x>=Zmod(p)[]
f=x^e-c
mps=f.roots(multiplicities=False)

P.<x>=Zmod(p)[]
g=x^e-c
mqs=g.roots(multiplicities=False)

ms = []
import itertools
for mp, mq in itertools.product(mps, mqs):
m = mp.crt(mq)
ms.append(m)
return ms

ms = solve(p, q, e, c)
print(ms)

也可以尝试使用 Sagemath 自带的 nth_root() 函数。

线程加速 check

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
flag = False

def check(something):
if long_to_bytes(int(something)).startswith(b'NCTF'):
print(long_to_bytes(int(something)))
return True
return False

def CRT_threading(mps, mqs, p, q):
global flag
for mp, mq in itertools.product(mps, mqs):
m = CRT([mp, mq], [p, q])
if check(m):
print(long_to_bytes(int(m)))
flag = not flag
print("[-] Done.")

import threading

thread_number = 32
for i in range(thread_number):
print('[+] Thread %d starting...' % i)
thi = threading.Thread(target=CRT_threading, args=(mps, mqs[i*(len(mqs) // thread_number):(i+1)*(len(mqs) // thread_number)], p, q), daemon=True)
thi.start()
print('[+] Thread %d starting...' % (i+1))
thi = threading.Thread(target=CRT_threading, args=(mps, mqs[i*(len(mqs) // thread_number):], p, q), daemon=True)
thi.start()
while not flag:
...

AMM

在 Sagemath 中,构造多项式求根或者使用 nth_rootJohnston 算法(Johnston 算法在针对小指数和不满足 e||p1 的时候效率较高)对较大指数效率都较为低下,这个时候需要使用 Adleman-Manders-Miller rth Root Extraction Method 算法,简称 AMM 算法快速求有限域下的根。

AMM 算法是目前在大指数下求高次根效率也较高的算法,但求高次根时需要满足条件 e||(p1),其中 Fp 为有限域。

目前 Sagemath 的更新进度似乎打算在 Sagemath9.8 加入 nth_root 函数对 AMM 算法的支持。

算法伪代码如下图所示:

AMM伪代码

Sagemath 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
def AMM(delta: int, r: int, q: int, all: bool = False):
"""
使用AMM算法进行有限域开根,即求delta^(1/r)%q下的解

`Parameter`:
delta - 底数
r - 根指数
q - 模数
all - 是否返回所有解

`Return`:
delta^(1/r)%q下的一个根
"""

if (q - 1) % r != 0:
raise Exception("使用AMM算法需要满足e||(q-1)")

# step 1
Fq = GF(q)
delta = Fq(delta)
rho = Fq.random_element()

# step 2
while rho ** ((q - 1) // r) == 1:
rho = Fq.random_element()

# step 3
# step 3.1
t = 0
s = q - 1
while s % r == 0:
t += 1
s //= r
# step 3.2
k = 1
while (k * s + 1) % r != 0:
k += 1
alpha = (k * s + 1) // r
# step 3.3
a = rho ** (r ** t - 1 * s)
b = delta ** (r * alpha - 1)
c = rho ** s
h = 1

# step 4
for i in range(1, t):
d = b ** pow(r, t - 1 - i, q - 1)
j = 0 if d == 1 else -d.log(a)
b *= (c ** r) ** j
h *= c ** j
c **= r

# step 5
root = int(delta ** alpha * h)
if not all:
return root

# if all is True, generate all roots to return
# 2 ^ (q - 1) == 1 (mod q) because of Fermat's little theorem
g = pow(2, (q - 1) // r, q)
# find all primitive i-th roots of 1
ith_roots = [pow(g, i, q) for i in range(r)]
return [int(root * ith_root % q) for ith_root in ith_roots]

p1 光滑数分解

特征

p1 为光滑数。

原理

已知 p1 为若干个 primes 元素相乘得到的平滑数,其中 primes 为一组已知素数,不妨取 (66)P=primes 那么原素数 p 可以表示为 (67)p1=kP 其中 kprimes 任意元素的乘积。

费马小定理有,若 p 为一个素数,则对于任意非 p 整数 aap11(modp)

那么取任意的 a ,有 (68)akP=1(modp) 即有 (69)aP=1(modp)=1+tp,t\ZN=pq,那么 (70)gcd(aP1,N)=p 我们便分解了 N

需要注意的是,实际计算中 aP 不好计算,一般计算 aP1(modN),可以证明与 1(modp) 同余。

实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag

def getPrime(bits):
while True:
n = 2
while n.bit_length() < bits:
n *= choice(primes)
if isPrime(n + 1):
return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)

# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
e = 0x10001
P = prod(primes)

# 这里的3是任取的
pp = pow(3, P, n) - 1
p = gcd(pp, n)
q = n // int(p)
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(c, d, n)

Pollard p-1 method

原理

对于 p1 为光滑数,更有效且通用的方法是使用 Pollard p-1 method 算法。

根据以上的原理证明,Pollard 发现当 primes 恰好为许多小素数的时候,那么 p1 也整除 n!,其中 n 为不太大的一个整数。

故当我们未知 primes 时,可以简单爆破 n 求解 (71)g=gcd(an!1,N)g=1 时,需要接着求下一个 n 的值;

g=N 时,需要修改 a 的值(实际中一般从 2 开始);

1<g<N 时,那么 g 就是 N 的一个因子。

同理我们实际上会直接求 an!1(modN) 而非 an!1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import itertools
N = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513

def PollardMethod(N: int):
"""
Pollard p-1 method

`Parameters`:
N - 要分解的大素数

`Returns`:
N的一个因子
"""
a = 2
for n in itertools.count(2):
a = pow(a, n, N)
g = gcd(a - 1, N)
if g == 1:
continue
elif g == N:
a += 1
else:
return g

print(PollardMethod(N))

需要注意的是,个人使用 Python 没办法跑出结果,得用 Sagemath。

可以借助 Python 模块 primefac 进行分解:

1
python -m primefac -vs -m=p-1 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513

p 进数攻击

原理

首先我们知道多项式分解的复杂度在于其项数的多少和系数的大小,同时任意一个数我们可以使用多项式来表达,比如说数字 1234567890 可以表达为: (72)P10(x)=x9+2x8+3x7+4x6+5x5+6x4+7x3+8x2+9x(73)P(10)=1234567890 或者是 (74)P5(x)=x13+x10+2x9+2x7+2x6+x5+3x4+3x3+3x(75)P(5)=1234567890 甚至是 (76)P1000=x3+234x2+567x+890(77)P(1000)=1234567890 可以发现,在不同的 p 进数下,多项式的复杂度会发生改变。

于是乎有可能出现在十进制下多项式复杂,分解时间复杂度高,但在 p 进数下多项式简单,分解时间复杂度低。

p 进数也被用于证明费马大定理。

实例

分解因数

1
N = 264048827496427248021277383801027180195275776366915828865010362454006394906519399441496561006668252031429735502465174250525698696973129422193405161920872162928097673289330345041221985548078586423910246601720647996170161319016119241836415788315729493164331517547663558380515400720081995290120793014108439083514403659082115510258023834737471488528527557960636984676435543300074504679264476413252780514962473070445293528877641502742438571110744667739728450283295649865745629276142949963507003094791773183928894536793857609738113546410753895719242547720815692998871947957214118354127328586542848234994500987288641595105

代码

1
2
3
4
5
6
7
8
9
10
11
N = 264048827496427248021277383801027180195275776366915828865010362454006394906519399441496561006668252031429735502465174250525698696973129422193405161920872162928097673289330345041221985548078586423910246601720647996170161319016119241836415788315729493164331517547663558380515400720081995290120793014108439083514403659082115510258023834737471488528527557960636984676435543300074504679264476413252780514962473070445293528877641502742438571110744667739728450283295649865745629276142949963507003094791773183928894536793857609738113546410753895719242547720815692998871947957214118354127328586542848234994500987288641595105
base = 11

P.<x> = ZZ[]
f = P(N.digits(base))
# (x^295 + 2*x^249 + x^196 + 1) * (x^295 + 2*x^281 + 2*x^192 + x^100 + 2*x^37 + 1)
F_factor = factor(f)
factors = []
for fac in F_factor:
factors.append(fac[0](base))
print(factors)

多项式关联攻击

原理

如果存在线性相关的明文 m1,m2,即存在多项式函数 f(x) 满足 (78)m2=f(m1)

例如一个最简单的多项式函数是 f(x)=ax+b

如果说存在一个多项式函数 (79)g(x)=alxl+al1xl1++a1x+a0 使得明文满足 (80)c1=g(m1),c2=g(m2)=g(f(m1))

例如一个最常见的首一单项式函数 c=g(m)=me(modN),即 RSA 加密函数。

那么必然有 (81)G(x)=gcd(g(m1)c1,g(m2)c2)(82)=xm1(83)m1=G(0) 在模 N 下也满足。

故在 RSA 中同样可以构建两式破解明文。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from sage.all import *
from Crypto.Util.number import *

e = 5
N = 5836720399
f = lambda x: x + 17
m1 = 781027021
m2 = f(m1)
g = lambda x: pow(x, e, N)
c1 = g(m1)
c2 = g(m2)
print(f'{e = }')
print(f'{N = }')
print(f'{c1 = }')
print(f'{c2 = }')
"""
e = 5
N = 5836720399
c1 = 2083888300
c2 = 2918851827
"""

可以写出求解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from sage.all import *
from Crypto.Util.number import *

e = 5
N = 5836720399
c1 = 2083888300
c2 = 2918851827
f = lambda x: x + 17
m1 = polygen(Zmod(N))
m2 = f(m1)
g = lambda x: x ** e
G = gcd(g(m1) - c1, g(m2) - c2)
m1 = int(-G(0))
print(f'{m1 = }')

或者可借助于理想求解

只有 multivariate polynomial rings 的 Ideal 才有 groebner_basis 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
e = 5
N = 5836720399
c1 = 2083888300
c2 = 2918851827
f = lambda x: x + 17
PR = PolynomialRing(Zmod(N), 'x', 1)
m1 = PR.gen()
m2 = f(m1)
g = lambda x: x ** e
Fs = [g(m1) - c1, g(m2) - c2]
I = Ideal(Fs)
G = I.groebner_basis()[0]
m1 = -G(0)
print(f'{m1 = }')

扩展

当我们已知 l+1 个条件 (84)f0(x1,,xl)=f(x1,,xl)0(modN)(85)f1(x1,,xl)=x1ec10(modN)(86)f2(x1,,xl)=x2ec20(modN)(87)(88)fl(x1,,xl)=xlecl0(modN) 我们对其求 Groebner 基有 (89)[x1m1,,xlml] 生成代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
import random

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 5

flag = b'flag{qsdz_1s_yyds_qsdz_1s_yyds}'
flag = pad(flag, 48)
m = [int.from_bytes(flag[i * 16:i * 16 + 16]) for i in range(3)]
S = sum(m) % n
cnt = len(m)
A = [random.getrandbits(16) for i in range(cnt)]
B = [random.getrandbits(32) for i in range(cnt)]
C = [random.getrandbits(32) for i in range(cnt)]
Cs = [int(pow((A[i] * m[i]**2 + B[i] * m[i] + C[i]), e, n)) for i in range(cnt)]
print(f'{S = }')
print(f'{A = }')
print(f'{B = }')
print(f'{C = }')
print(f'{e = }')
print(f'{n = }')
print(f'{Cs = }')

使用理想求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import long_to_bytes
from sage.all import *

S = 312186279122728322840451063402809132934
A = [59306, 30233, 16498]
B = [3518064068, 1743840779, 968272001]
C = [3937571722, 2632887300, 4010585432]
e = 5
n = 18066984073475342789493692613823811785487239998753985805020579267940896948081977001771518523566472410672469410750970677917794989108185341025224936232967134929583548467862041251918442321275217404983105419368662343665374632165656617420205237026045440172381460935460690939381735444035707066029853110776298630061438907984659853208747287992151782531561151400196784932859377900035524366656621630353334553560825733409533365949100590660823734584006536175326697501394564510286279450317686958337988217355014539606930767250922535983519405417158647496890748820686624906060567276540610448840500483189314710494353563879277794541353
Cs = [1605011707284276632103824644590203887016797212847098299446289280674897645002161069677543064343533796490420264529467459463526241913229967023798085318628445950097108809898826295428523862026843521177725032160711865551726777679038376141316425909360840477060120073221091013634795786803742332494305103072574470667738491664498087291656588818784515569714358898421758142569763447554120962624497276016496694140100000, 181734039700238704012658418593813266912521651894752866626415626828623947405568804251736115950606071068346648144215703817981273278046087507889172667757867256797631566535849534415227715943523579302779674337105968419763028025748461306053447376558392979833811008114700852873079622034093487878691189882417957256088379073866088138200910652985291201335834644957095984704369396287502740148745261121583050802561024, 44120289726668300688172841856869479594776389466065225989061060426577417071904451062768078357173832546168316502143084515709199818093521749001394049673866578656496253883891021254583201653096210245674629552133246459157519698072200401130427631509011414976317349970710420293614611921718541830198891304752451947110143182603538593757393837717582250960575842815038472270815811197204422601423145762307051]
cnt = len(Cs)

PR = PolynomialRing(Zmod(n), 'm', cnt)
m = PR.gens() # 生成 cnt 个 m,用下标区分符号
Fs = [((A[i] * m[i]**2 + B[i] * m[i] + C[i])**e - Cs[i]) for i in range(cnt)]
# 这里的额外条件可变
Fs.append(sum(m) - S)
I = Ideal(Fs)
G_b = I.groebner_basis()
for b in G_b:
mi = ZZ(-b(0, 0, 0)) # 3 个元
print(long_to_bytes(int(mi)))

随机填充多项式

原理

与多项式关联攻击不同的是,在这里我们已知 c1,c2,且已知关系 (90)m2=m1+b 但我们需要求解的是 b

考虑 (91)m13c10(modN)(92)(m1+b)3c20(modN) 由于两式都存在公共根 m1,那么其对 m1 的结式有非零零点,即线性方程 φ(P,Q)=0 有非零解。

显然两式的结式是关于 b 的函数,那么我们可以使用 Coppersmith 方法求解 b,需要满足 b<N1/9

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import random

p = getPrime(128)
q = getPrime(128)
N = p * q
e = 3
m1 = 12345678909876543211234567890987654321
assert m1 < N
b = random.getrandbits(16)
m2 = m1 + b
c1 = pow(m1, e, N)
c2 = pow(m2, e, N)
# print(f'{p = }')
# print(f'{q = }')
# print(f'{e = }')
# print(f'{b = }')
print(f'{N = }')
print(f'{c1 = }')
print(f'{c2 = }')

获得 N,c1,c2 即可求解,但需要知道 b 的范围

1
2
3
4
5
6
7
8
9
10
11
12
N = 56436527799596600766941861586070268729876941786810367535069648964447679452103
c1 = 12073228961013942273133217560992243967967964540450220284564024509779603201167
c2 = 27368061585067693852702568126262342364990409791917711366691159936158442852034

PR.<m1, b> = ZZ[]
e = 3
f1 = m1 ** e - c1
f2 = (m1 + b) ** e - c2
R = f1.resultant(f2, m1)
P.<x> = Zmod(N)[]
F = R(0, x)
F.small_roots(2**16, beta=1./9)

目前只研究了 e=3 的情况。

已知 pq

原理

已知 x=pq 的结果,就相当于一个 GF(2) 下的多项式的加法结果已知,同时又因为 n=pq,故其多项式的乘法结果也已知,此时我们仅需简单爆破系数或直接构造矩阵求解即可。

参考代码:https://github.com/sliedes/xor_factor