• 这篇博客正式开始我的RSA加密的密码分析学的学习，之前一直想写这个博客，但是由于基础知识有限以及时间关系一直就鸽了，现在基础知识跟上来了，直接开始疯狂学习。
  • 之前也做过不少RSA加密的题型，所以我根据集合的划分，将RSA加密题型进行分类，尽我所能的将题型分类成如下图所示，我会根据我的分类进行学习。目前还没分类完成，只能说边学边分类吧（此图会不定期跟新与完善）。这个分类的构建有参考这本国外书籍：《Cryptanalysis of RSA and Its Variants (M. Jason Hinek)》

RSA加密题型大总结

题型1_工具分解

工具分解的话就使用yafu、factordb这两个常见的工具分解就行，常规的题型还是比较简单的，之前已经做过很多这样的简单题了。等寒假或者什么时候有空再将这个补充完整吧。

题型2_运用定理和规律

题目1_easy_factor1

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 *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import *
from secret import flag

p,q,r = getPrime(256),getPrime(256),getPrime(256)
n = p*q*r
phi = (p-1)*(q-1)*(r-1)

key = sha256(str(p+q+r).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
c = enc.encrypt(pad(flag,16))

print("n =",n)
print("hint =",getrandbits(256)*phi**3)
print("c =",c)

'''
n = 343127312894441264623060100705188723106648253383902349620699412384677995734576572885137280031507308915752070128528949423639735964709160841591038148069185325450544546735392923674211031016035209702254447128968565740534765322198664691
hint = 3802744632475774666777934738986183209966233570124815804333822490240409933768208822899072601181527365734196352249978937639454658680559993507805820991037544059215540360338084909833242583087617315128513337647913472696515770688338805196215328080662137260951972365100322795737835152857750114216709340410268143017180826135339564387228460663261697814425298725805568817218360964967025967384766127098203664964210047103829182895016532403825215903779806760754721373523135367007867453212189953817229696304611549977864533229540971457717668560698088917340909962348110683581294453903261530189579223087858081200349343639420534779115290433982968345085704202494045885911950427043282588446343291558819683037970053828479057449781943479407877748772895179095205885377333120540311815022381056
c = b';#\x1b\xa6R\xe2\x1d\x9dpf\x8e\xda\xe4\x14\x9a\xfb\tr\x99\x8a\xc9r\x03C\xb58Zb\x97\x0b\xc7S\x0fa\x88\xb4\xe4\x16.M\x92\x94\x94\x8b\xa9Ki\x9b\xe4\xe9d5\xa3~\x1a\x9cx\x03\xdc\x1f\x87\x14E\x90'
'''
  • 首先来看看hint，题目中给出hint=x∗phi(n)3hint=x*phi(n)^3，并没有看出什么苗头来。但是尝试分解一下hint发现可以分解出来。

image-20250722121805512

  • 那么就直接从分解后的hint入手，由算数基本定理可以得知

\begin{align} hint &= x*[(p-1)(q-1)(r-1)]^{3}\\ &=p_1^{\alpha_{1}}*p^{\alpha_{2}}_2....p_k^{\alpha_{k}}\\ &=p_1^{\alpha_{1}}*...*(p_k^{\beta_1}*p_{k+1}^{\beta_2}...)^{3} \end{align}

  • 在分解的时候发现分解出来的结果存在73、413....7^3、41^{3}....这样的数，这其实就有可能是p-1、q-1、r-1这三个数的其中一个数分解的特有因子。可以从这个地方入手。不妨设737^3是r-1的特有因子。那么hint就存在如下的推导

\begin{align} hint &= x*(p-1)^{3}*(q-1)^{3}*(r-1)^{3}\\ &=x*k*7^3*(p-1)^{3}*(q-1)^{3} \end{align}

  • 那么hint开3次方再除7就会得到如下的式子

\begin{align} \frac{hint}{7^{3}}=k'(p-1)*(q-1) \end{align}

  • 这样由欧拉定理：若n,an,a是正整数，且gcd(n,a)=1，则有aphi(n)≡1(mod n)a^{phi(n)}\equiv1(mod ~n)，带入到该题目中就有

ak′∗(p−1)∗(q−1)≡1 mod(p∗q)a^{k'*(p-1)*(q-1)}\equiv 1~mod(p*q)

  • 这样我们取a=2刚好与p*q互素，此时就有：

ak′∗(p−1)∗(q−1)−1≡0 mod(p∗q)a^{k'*(p-1)*(q-1)}-1\equiv 0~mod(p*q)

  • 此时就可以有gcd(2k′∗(p−1)∗(q−1)−1,p∗q∗r)=p∗qgcd(2^{k'*(p-1)*(q-1)}-1,p*q*r)=p*q，再重复一次即可求出p、q的其中一个

  • exp如下：

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
import gmpy2
from hashlib import sha256
from Crypto.Cipher import AES
hint = 3802744632475774666777934738986183209966233570124815804333822490240409933768208822899072601181527365734196352249978937639454658680559993507805820991037544059215540360338084909833242583087617315128513337647913472696515770688338805196215328080662137260951972365100322795737835152857750114216709340410268143017180826135339564387228460663261697814425298725805568817218360964967025967384766127098203664964210047103829182895016532403825215903779806760754721373523135367007867453212189953817229696304611549977864533229540971457717668560698088917340909962348110683581294453903261530189579223087858081200349343639420534779115290433982968345085704202494045885911950427043282588446343291558819683037970053828479057449781943479407877748772895179095205885377333120540311815022381056
hint1 = hint//(7^3)
n = 343127312894441264623060100705188723106648253383902349620699412384677995734576572885137280031507308915752070128528949423639735964709160841591038148069185325450544546735392923674211031016035209702254447128968565740534765322198664691
c = b';#\x1b\xa6R\xe2\x1d\x9dpf\x8e\xda\xe4\x14\x9a\xfb\tr\x99\x8a\xc9r\x03C\xb58Zb\x97\x0b\xc7S\x0fa\x88\xb4\xe4\x16.M\x92\x94\x94\x8b\xa9Ki\x9b\xe4\xe9d5\xa3~\x1a\x9cx\x03\xdc\x1f\x87\x14E\x90'
#print(hint,x)
leak = gcd(pow(2,hint1,n)-1,n)
print("p*q=",leak)
r = n//leak
print(r)
# 同样再来一次这个操作就可以求p
hint2 = hint//(r-1)^3
print(hint2) # 分解hint2后发现 277^3 248701^3
hint3 = hint2//(277^3)
p = gcd(pow(2,hint3,leak)-1,leak)
print('p =',p)
q = leak//p
print("q =",q)
key = sha256(str(p+q+r).encode()).digest()
enc = AES.new(key,AES.MODE_ECB)
m = enc.decrypt(c)
print(m)
"""
b'NSSCTF{Just_simply_try_t0_divid3_s0m3_f4ct0rs_0f_phi}\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b'
"""

题目2_BlitzCTF_CUSTOM_RSA_revenge

  • 题目附件如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Cryptodome.Util.number import long_to_bytes, getPrime, bytes_to_long

m = b"Blitz{REDACTED}"

p = getPrime(150)
q = getPrime(150)
e = getPrime(128)
n = p*q
mod_phi = (p-1)*(q-1)*(e-1)
d = pow(e, -1, mod_phi)
print(mod_phi)
print(n)
c = pow(bytes_to_long(m), e, n)
print(c)
print(p)
"""
mod_phi = 381679521901481226602014060495892168161810654344421566396411258375972593287031851626446898065545609421743932153327689119440405912
n = 1236102848705753437579242450812782858653671889829265508760569425093229541662967763302228061
c = 337624956533508120294617117960499986227311117648449203609049153277315646351029821010820258
"""
  • 此题的思路和题目一差不多，只不过不需要使用gcd进行分解。先来看看mod_phi=(p-1)*(q-1)*(e-1)，其实这个地方也是能分解的。这里就使用sagemath内置的factor()函数进行分解。分解的结果如下，发现分解出来的素数对应的次数都不超过3
1
[(2, 3), (3, 2), (67, 1), (673, 1), (3181, 1), (252401, 1), (23896409, 1), (145028189, 1), (79561224974873, 1), (308026511504069, 1), (4509599821882817, 1), (9907158782085681344183, 1), (38588687064594940957905160665643, 1)]
  • 这个时候就可以直接遍历这些素数，设遍历的素数为g，就有phi=(p−1)∗(q−1)∗(e−1)phi=(p-1)*(q-1)*(e-1)
    • 如果遍历到g是e-1的因数，那么phig=k∗(p−1)∗(q−1)\frac{phi}{g}=k*(p-1)*(q-1)，此时就使用欧拉定理(aphi(n))k≡1 mod(n)(a^{phi(n)})^{k}\equiv1~mod(n)
    • 如果遍历到g不是e-1的因数，那么aphig≢1 mod(n)a^{\frac{phi}{g}}\not\equiv1~mod(n)，通过这样的判断就可以得到e的所有因数
    • 这里取a=2，满足gcd(2,n)=1
  • exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import libnum
mod_phi = 381679521901481226602014060495892168161810654344421566396411258375972593287031851626446898065545609421743932153327689119440405912
n = 1236102848705753437579242450812782858653671889829265508760569425093229541662967763302228061
c = 337624956533508120294617117960499986227311117648449203609049153277315646351029821010820258
x = list(factor(mod_phi))
print(x)
e = 1
for i in x:
    t = mod_phi//i[0]
    if pow(2,t,n)==1:
        e = e*i[0]
print(e)
phi=mod_phi//(e)
d = inverse_mod(e+1,phi)
m = pow(c,d,n)
print(libnum.n2s(int(m)))
"""
[(2, 3), (3, 2), (67, 1), (673, 1), (3181, 1), (252401, 1), (23896409, 1), (145028189, 1), (79561224974873, 1), (308026511504069, 1), (4509599821882817, 1), (9907158782085681344183, 1), (38588687064594940957905160665643, 1)]
308776508606152118670230312260475727066
b'Blitz{Cust0m_RSA_OMGGG}'
"""

题目3_easy_factor2

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
from Crypto.Util.number import *
from random import *
from gmpy2 import *
#from secret import flag
flag = b'flag{test_flag}'
m = bytes_to_long(flag)

def gen_prime(bits,common_bits):
    shift = bits - common_bits
    while(True):
        high = ((1<<(common_bits-1)) + getrandbits(common_bits-1)) << shift
        p = high + 2*getrandbits(shift-1) + 1
        q = high + 2*getrandbits(shift-1) + 1
        if(isPrime(p) and isPrime(q)):
            return p,q

p,q = gen_prime(1024,350)
n = p*q
leak = (pow(p,q,n) + pow(q,p,n)) & ((1 << 300) - 1)
e = 65537
c = pow(m,e,n)

print("n =",n)
print("e =",e)
print("c =",c)
print("leak =",leak)

#n = 20304817598463991883487911425007927214135740826150882692657608404060781116387976327509281041677948119173928648751205240686682904704601086882134602075008186227364732648337539221512524800875230120183740426722086488143679856177002068856911689386346260227545638754513723197073169314634515297819111746527980650406024533140966706487847121511407833611739619493873042466218612052791074001203074880497201822723381092411392045694262494838335876154820241827541930328508349759776586915947972105562652406402019214248895741297737940426853122270339018032192731304168659857343755119716209856895953244774989436447915329774815874911183
#e = 65537
#c = 7556587235137470264699910626838724733676624636871243497222431220151475350453511634500082904961419456561498962154902587302652809217390286599510524553544201322937261018961984214725167130840149912862814078259778952625651511254849935498769610746555495241583284505893054142602024818465021302307166854509140774804110453227813731851908572434719069923423995744812007854861031927076844340649660295411912697822452943265295532645300241560020169927024244415625968273457674736848596595931178772842744480816567695738191767924194206059251669256578685972003083109038051149451286043920980235629781296629849866837148736553469654985208
#leak = 1511538174156308717222440773296069138085147882345360632192251847987135518872444058511319064