Crypto系列——RSA（一）

不知道为啥就对密码学感兴趣了，上学期学了半天pwn没搞懂，或许就不适合学pwn吧😭

《从0开始的密码学世界生活》😋慢慢学密码方向

在探姬的建议下，还是买了这套课程，开干！

[RSA1]P1

main.py

from Crypto.Util.number import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
phi = (p-1)*(q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 10554915510546378513140074459658086644656654144905337809416976066414771647836950941616441505897207397834928781511863699153349798682451297889979721668885951
q = 8246403321715011123191410826902524505032643184038566851264109473851746507405534573077909160292816825514872584170252311902322051822644609979417178306809223
e = 65537
c = 40005881669517895877352756665523238535105922590962714344556374248977905431683140065629966778249773228248201807844489945346731806741025157651474530811920115794270396320935022110691338083709019538562205165553541077855422953438117902279834449006455379382431883650004540282758907332683496655914597029545677184720
'''

decrypt.py

已知p,q,e,c,可直接求出d,然后求出m

from Crypto.Util.number import *

p = 10554915510546378513140074459658086644656654144905337809416976066414771647836950941616441505897207397834928781511863699153349798682451297889979721668885951
q = 8246403321715011123191410826902524505032643184038566851264109473851746507405534573077909160292816825514872584170252311902322051822644609979417178306809223
e = 65537
c = 40005881669517895877352756665523238535105922590962714344556374248977905431683140065629966778249773228248201807844489945346731806741025157651474530811920115794270396320935022110691338083709019538562205165553541077855422953438117902279834449006455379382431883650004540282758907332683496655914597029545677184720

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

d = pow(e,-1,phi)
m = pow(c,d,n)

print(long_to_bytes(m))   # b'NSSCTF{now!you_know_rsa}'

关于类型的转换，pepper师傅这里说的很好，我就直接copy了

本题需要理解明文和密文的类型及其类型转换函数。long类型为一串数字，bytes是字符。

在下列示例中，message表示bytes类型明文，m表示long类型明文，c表示long类型密文。

在rsa.py函数中：

1. 输入 message 明文为 bytes 类型,加密 c=pow(m,e,n) 中明文 m 为 long 类型，输出密文 c 是 long 类型。

   message 到 m 需要通过 bytes_to_long(message) 方法进行转换

2. 解密 m= pow(c, d, n) 中 m 为 long 类型，c 为 long 类型。

   打印输出的明文 message 需要 bytes 类型，通过 long_to_bytes(m) 方法进行转换

m = bytes_to_long(message) bytes转long
message = long_to_bytes(m) long转bytes

---

[RSA1]P2

main_py

from Crypto.Util.number import *

flag = b'NSSCTF{******}'

p = getPrime(256)
q = getPrime(256)
n = p*q
e = 65537
phi = (p-1)*(q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 7382582015733895208810490097582153009797420348201515356767397357174775587237553842395468027650317457503579404097373070312978350435795210286224491315941881
e = 65537
c = 6511001389892474870028836129813814173158254564777610289284056550272120510686249909340499673868720839756059423749304765055919251717618117507007046973023557
'''

decrypt.py

已知n,e,c,分解n，得到p,q

本题意思是只知道了n，而p和q都不知道，那么我们就要把n这个大整数分解，用到网站factordb.com

得到分解的两个数p和q，即可写出decrypt.py

from Crypto.Util.number import *

n = 7382582015733895208810490097582153009797420348201515356767397357174775587237553842395468027650317457503579404097373070312978350435795210286224491315941881
e = 65537
c = 6511001389892474870028836129813814173158254564777610289284056550272120510686249909340499673868720839756059423749304765055919251717618117507007046973023557

p = 70538125404512947763739093348083497980212021962975762144416432920656660487657
q = 104660876276442216612517835199819767034152013287345576481899196023866133215633

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

d = pow(e,-1,phi)
m = pow(c,d,n)

print(long_to_bytes(m))

---

[RSA1]P3

main_py

from Crypto.Util.number import *

flag = b'NSSCTF{******}'

p = getPrime(128)
q = getPrime(128)
n = p*q
e = 65537
phi = (p-1)*(q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 53690629441472827148854210396580805205350972614395425306316047967905824330731
e = 65537
c = 22130296334673852790451396673112575082637108306697684532954477845025885087040
'''

decrypt.py

已知n,e,c,yafu分解n，得到p,q

虽然它说是要让用yafu，命令为：.\yafu-x64.exe "factor(@)" -batchfile 1.txt

yafu安装及使用 - SkYe Wiki (mrskye.cn)

但我寻思这个数比上面的数还小，直接factordb.com不就行辣😋

求出p和q后，解密函数跟[RSA1]P2一样

---

[RSA1]P4

main_py

from Crypto.Util.number import *
import gmpy2
flag = b'NSSCTF{******}'

p = getPrime(512)
q = gmpy2.next_prime(p)
n = p*q
e = 65537
phi = (p-1)*(q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730
'''

decrypt.py

已知n,e,c，且p,q相差不大（特例款）。

直接copy了xenny师傅的wp，😰😢

• 本题的关键是q = gmpy2.next_prime(p)，相当于q是p的下一个素数
• 然后这里可以采用一个\(\sqrt{n}\)，因为\(n = p*q\)，考虑n的算术平方根为\(sn = \sqrt{n}\)，同时 sn 也是p和q的几何平均值。所以有\(p<sn<q\)
• 又有p，q是相邻的素数，p的下一个素数为q，同理也有sn的下一个素数也应该是q，
• 然后由q求出p即可

这里附上一篇文章：浅析RSA因子大小相近时分解因子攻击方法 - FreeBuf网络安全行业门户

from Crypto.Util.number import *
from gmpy2 import *
p = getPrime(512)
q = gmpy2.next_prime(p)

n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730

sn = isqrt(n)      #或者sn = gmpy2.iroot(n,2)
q = next_prime(sn)
p = n // q

phi = (p-1)*(q-1)
d = invert(e, phi)

m = pow(c, d, n)
print(long_to_bytes(m))

---

[RSA1]P5

main_py

from Crypto.Util.number import *
import gmpy2
flag = b'NSSCTF{******}'

p = getPrime(512)
q = gmpy2.next_prime(p - getPrime(256))
n = p*q
e = 65537
phi = (p-1)*(q-1)
m = bytes_to_long(flag)
c = pow(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
'''
n = 148841588941490812589697505975986386226158446072049530534135525236572105309550985274214825612079495930267744452266230141871521931612761645600600201983605957650711248808703757693378777706453580124982526368706977258199152469200838211055230241296139605912607613807871432800586045262879581100319519318390454452117
e = 65537
c = 69038543593219231496623016705860610154255535760819426453485115089535439537440188692852514795648297200067103841434646958466720891016026061658602312900242658759575613625726750416539176437174502082858413122020981274672260498423684555063381678387696096811975800995242962853092582362805345713900308205654744774932
'''

decrypt1.py

已知n,e,c，且p,q相差不大（经典款）。

直接yafu分解：

但是不能用[RSA1]P4里面的方法，因为根号n的下一个素数不一定是q哦😡

from Crypto.Util.number import *

P = 12200065120379104459630695224710181907653841921369674962900093531339421658815375891425102591939094029941691738405035324548070063226677838530633694428729829
q = 12200065120379104459630695224710181907653841921369674962900093531339421658815305905822146210878434959851438079877557401145694064756239882458467901042367473
e = 65537
c = 69038543593219231496623016705860610154255535760819426453485115089535439537440188692852514795648297200067103841434646958466720891016026061658602312900242658759575613625726750416539176437174502082858413122020981274672260498423684555063381678387696096811975800995242962853092582362805345713900308205654744774932

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

d = pow(e,-1,phi)
m = pow(c,d,n)

print(long_to_bytes(m))   

文章 - RSA1]P5 pepper的WriteUp | NSSCTF

decrypt2.py

已知n,e,c，且p,q相差不大（经典款）。

费马分解： RSA1]P5 pepper的WriteUp | NSSCTF

看懂了，只有一个问题：为什么从a从根号n开始加

• 因为b要从0，a等于根号n时b才等于0😋

from Crypto.Util.number import *
from gmpy2 import *
p = getPrime(512)
q = gmpy2.next_prime(p - getPrime(256))

n = 148841588941490812589697505975986386226158446072049530534135525236572105309550985274214825612079495930267744452266230141871521931612761645600600201983605957650711248808703757693378777706453580124982526368706977258199152469200838211055230241296139605912607613807871432800586045262879581100319519318390454452117
e = 65537
c = 69038543593219231496623016705860610154255535760819426453485115089535439537440188692852514795648297200067103841434646958466720891016026061658602312900242658759575613625726750416539176437174502082858413122020981274672260498423684555063381678387696096811975800995242962853092582362805345713900308205654744774932


def fermat_attack(n):
    a = isqrt(n)
    b2 = a*a - n
    b = isqrt(n)    #这里只是对b进行一个初始化，b=1，2，3，，，等于几应该都行
    count = 0
    while b*b != b2:          
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2)
        count += 1
    p = a+b
    q = a-b
    assert n == p * q
    return p, q


p, q = fermat_attack(n)

phi = (p-1)*(q-1)
d = invert(e, phi)


msg = pow(c, d, n)
message = long_to_bytes(msg)

print(message)

---

[RSA1]P6

main_py

from Crypto.Util.number import *
flag = b'NSSCTF{******}'

p1 = getPrime(512)
q = getPrime(512)
p2 = getPrime(512)

n1 = p1*q
n2 = p2*q

e = 65537

m = bytes_to_long(flag)
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)

print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'e = {e}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
'''
n1 = 143348646254804947818644803938588739009782265465565896704788366218178523508874903492905378927641178487821742289009401873633609987818871281146199303052141439575438691652893995423962176259643151111739185844059243400387734688275416379337335777994990138009973618431459431410429980866760075387393812720247541406893
n2 = 138110854441015362783564250048191029327770295545362614687087481715680856350219966472039006526758450117969049316234863489558254565946242898336924686721846675826468588471046162610143748100096038583426519355288325214365299329095841907207926280081868726568947436076663762493891291276498567791697978693639037765169
e = 65537
c1 = 54957154834913405861345262613986460384513988240935244315981524013378872930144117440787175357956479768211180412158274730449811947349624843965933828130932856052315165316154486515277625404352272475136003785605985702495858150662789554694910771308456687676791434476722168247882078861234982509648037033827107552029
c2 = 122221335585005390437769701090707585780333874638519916373585594040154234166935881089609641995190534396533473702495240511296379249872039728112248708182969185010334637138777948970821974238214641235158623707766980447918480715835847907220219601467702961667091318910582445444058108454023108157805147341928089334736
'''

decrypt.py

已知（e,n1,c1,n2,c1），求m

两组数中e相同，n,c不同，n1和n2的最大公因数即为p,之后就能求出q、d,继而求出m

from Crypto.Util.number import *
from gmpy2 import *

n1 = 143348646254804947818644803938588739009782265465565896704788366218178523508874903492905378927641178487821742289009401873633609987818871281146199303052141439575438691652893995423962176259643151111739185844059243400387734688275416379337335777994990138009973618431459431410429980866760075387393812720247541406893
n2 = 138110854441015362783564250048191029327770295545362614687087481715680856350219966472039006526758450117969049316234863489558254565946242898336924686721846675826468588471046162610143748100096038583426519355288325214365299329095841907207926280081868726568947436076663762493891291276498567791697978693639037765169
e = 65537
c1 = 54957154834913405861345262613986460384513988240935244315981524013378872930144117440787175357956479768211180412158274730449811947349624843965933828130932856052315165316154486515277625404352272475136003785605985702495858150662789554694910771308456687676791434476722168247882078861234982509648037033827107552029
c2 = 122221335585005390437769701090707585780333874638519916373585594040154234166935881089609641995190534396533473702495240511296379249872039728112248708182969185010334637138777948970821974238214641235158623707766980447918480715835847907220219601467702961667091318910582445444058108454023108157805147341928089334736

# p1 = getPrime(512)
# q = getPrime(512)
# p2 = getPrime(512)            byd你写解代码的时候加上这一段干什么

# n1 = p1*q
# n2 = p2*q

q = gcd(n1,n2)        # 最关键的一句，看出q是n1和n2的最大公因数，然后求出q，后面就常规
# print(q)
p1 = n1 // q

phi = (q-1)*(p1-1)
d1 = invert(e, phi) 

m1 = pow(c1, d1, n1)


# m1=hex(m1).replace('0x','')
# flag = bytes.fromhex(m1)
# print(flag)

print(long_to_bytes(m1))
# 但是有个小问题啊，为什么n1和n2解出来是一样的捏🤒

---

[RSA1]P7

main_py

from Crypto.Util.number import *

flag = b'NSSCTF{******}' + b'1'*170

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p*q*r
e = 65537
phi = (p-1)*(q-1)*(r-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'r = {r}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 10666139331774428325755287635566473140804481321882464031499529816800186578792308674238646794969384836340484775213796013129603472328582005363876462361316357
q = 8419311673449738061914489023962717718536471719688567807316495262754711350004888752049108347226115000749280146228195893953964759818878155006622123533942989
r = 12875078327453384158245832541544758526474680184252540739652077682353277702054275525591573258723948221345537075374635382175740236093131628077747126356403959
e = 65537
c = 424552463648937499189041230155623101311087334789253159440707211761796081289342164253743235182597460622581134089949035117444838205449163269030784233435435681797627188717450074808905561404960693227573181548281296514743775615606388692910356320667720308219275107443303501165027740512539959960217657836317351146520079753390346207659007421416917274795119021374032194294225350901136669304225010974617136606299060486198480556729770211945777266366417547752798441211059402
'''

decrypt.py

已知（e，p，q，r），求m（特例款）

相当于多了一个参数r，还是一样，加上r就行了

from Crypto.Util.number import *

p = 10666139331774428325755287635566473140804481321882464031499529816800186578792308674238646794969384836340484775213796013129603472328582005363876462361316357
q = 8419311673449738061914489023962717718536471719688567807316495262754711350004888752049108347226115000749280146228195893953964759818878155006622123533942989
r = 12875078327453384158245832541544758526474680184252540739652077682353277702054275525591573258723948221345537075374635382175740236093131628077747126356403959
e = 65537
c = 424552463648937499189041230155623101311087334789253159440707211761796081289342164253743235182597460622581134089949035117444838205449163269030784233435435681797627188717450074808905561404960693227573181548281296514743775615606388692910356320667720308219275107443303501165027740512539959960217657836317351146520079753390346207659007421416917274795119021374032194294225350901136669304225010974617136606299060486198480556729770211945777266366417547752798441211059402

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

d = pow(e,-1,phi)
m = pow(c,d,n)

print(long_to_bytes(m))  

#b'NSSCTF{3th_number!}11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111'
# 不过至于本题为何要添加上大量的字符1作为填充内容，这个问题待到P9时我们便会知晓。

---

[RSA1]P8

main_py

from Crypto.Util.number import *

flag = b'NSSCTF{******}' + b'1'*100

p = getPrime(256)
q = getPrime(256)
n = (p**3) * q
e = 65537
phi = (p-1)*(q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 80505091208742938705306670241621545375764148093711243653439069254008824979403
q = 67599990875658931406915486208971556223245451500927259766683936131876689508521
e = 65537
c = 7958690969908064264211283192959937430539613460471121984649054121171267262097603091410178042319139582772142226087020110084551158367679146616732446561228522673699836019156243452069036383047309578614662564794584927846163157472211089368697387945469398750955336949678910159585015004994620777231073804301249774041
'''

decrypt.py

已知（e，p，q，r），求m（经典款）

byd欧拉公式都不知道是吧：

对于： \[ n = p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\cdots p_{r}^{k_{r}} \]

欧拉函数等于：

\[ \varphi (n) = \prod_{i=1}^{r} p_{i}^{k_{i}-1}(p_{i}-1) \]

from Crypto.Util.number import *

p = 80505091208742938705306670241621545375764148093711243653439069254008824979403
q = 67599990875658931406915486208971556223245451500927259766683936131876689508521
e = 65537
c = 7958690969908064264211283192959937430539613460471121984649054121171267262097603091410178042319139582772142226087020110084551158367679146616732446561228522673699836019156243452069036383047309578614662564794584927846163157472211089368697387945469398750955336949678910159585015004994620777231073804301249774041

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

d = pow(e,-1,phi)
m = pow(c,d,n)

print(long_to_bytes(m))  

---

[RSA1]P9

main_py

from Crypto.Util.number import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)

e = 65537
while True:
    r = 2*getPrime(100)*e+1
    if isPrime(r):
        break

n = p*q*r

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'r = {r}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 7478755670255767435237487693415479182290330775502792675052667363676831056436638619069277770540533350723045234676443621124912287506103439704868369839725279
q = 9232828888049557325429111621080998490274442347556398052322580869768941301413255711626092627273543579067597113958627672298942570149816938335701615759283713
r = 102909133680612532601801231903654039
e = 65537
c = 142893174944324070830219394465469685943669308818639857030565389839224452373848570577201378981080333784852764502832587008270072323948511579823852437852643609820245476634896477031076952735298279618952398460203032125853063235638358942643559551563899381032067185778629120272032518475352761100115057449043142848203976076694124978394099839339406197
'''

decrypt.py

已知（e，p，q，r)，且m已知很短

总结：

满足以下情况时，可以不使用题中给的n=pqr计算公式，自己重新计算n，再进一步计算公私钥：

1. 明文m比较简短
   • flag = b’NSSCTF{ \(\cdots\cdots\)}’ + b’1’ * 100 不行
   • flag = b’NSSCTF{ \(\cdots \cdots\) }’ 可以
2. 分析发现使用给定的n无法计算d，原因可能是d = inverse(e, phi)中e、phi不互素

from Crypto.Util.number import *
from gmpy2 import *


p = 7478755670255767435237487693415479182290330775502792675052667363676831056436638619069277770540533350723045234676443621124912287506103439704868369839725279
q = 9232828888049557325429111621080998490274442347556398052322580869768941301413255711626092627273543579067597113958627672298942570149816938335701615759283713
r = 102909133680612532601801231903654039
e = 65537
c = 142893174944324070830219394465469685943669308818639857030565389839224452373848570577201378981080333784852764502832587008270072323948511579823852437852643609820245476634896477031076952735298279618952398460203032125853063235638358942643559551563899381032067185778629120272032518475352761100115057449043142848203976076694124978394099839339406197

n = p * q    # 相当于直接把r给忽略掉了，但原理还没懂，xenny师傅的wp有点没看懂
phi = (p-1)*(q-1)

d = invert(e, phi)
m = pow(c,d,n)

print(long_to_bytes(m))   

Xenny师傅的wp：Crypto系列——RSA（一） | NSSCTF

---

[RSA1]P10

main_py

from Crypto.Util.number import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)

e = 65537*2

n = p*q

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 9927950299160071928293508814174740578824022211226572614475267385787727188317224760986347883270504573953862618573051241506246884352854313099453586586022059
q = 9606476151905841036013578452822151891782938033700390347379468858357928877640534612459734825681004415976431665670102068256547092636766287603818164456689343
e = 131074
c = 68145285629092005589126591120307889109483909395989426479108244531402455690717006058397784318664114589567149811644664654952286387794458474073250495807456996723468838094551501146672038892183058042546944692051403972876692350946611736455784779361761930869993818138259781995078436790236277196516800834433299672560
'''

decrypt.py

已知(e，p，q，c），但是e和phi不互素

因为p−1或q−1都是偶数，e也是偶数，他们显然不互素。

关键の公式： \[ c\equiv m^{e}\equiv (m^{2})^{65537} (mod \quad n) \] 把 \(m^{2}\)看成一个整体即可

from Crypto.Util.number import *
from gmpy2 import *

p = 9927950299160071928293508814174740578824022211226572614475267385787727188317224760986347883270504573953862618573051241506246884352854313099453586586022059
q = 9606476151905841036013578452822151891782938033700390347379468858357928877640534612459734825681004415976431665670102068256547092636766287603818164456689343
e = 65537
c = 68145285629092005589126591120307889109483909395989426479108244531402455690717006058397784318664114589567149811644664654952286387794458474073250495807456996723468838094551501146672038892183058042546944692051403972876692350946611736455784779361761930869993818138259781995078436790236277196516800834433299672560


n = p*q
phi = (p-1)*(q-1)
d = invert(e, phi)
m = pow(c, d, p*q)

print(long_to_bytes(isqrt(m)))


# 后面这部分也能写出下面这样：


n = p * q    
phi = (p-1)*(q-1)
# print(gcd(e, phi))

d = invert(e, phi)
m = pow(c,d,n)
a,b = gmpy2.iroot(m,2) 

print(long_to_bytes(a))   

2023.09.10-2023.09.14