入坑CTF——RSA解密之大素数分解和共模攻击的Python实现

前言

CTF做题时偶尔会遇到RSA相关的题，看题的第一眼，一时不知道题目想表达什么意思，总是选择跳过，想想逃避也不是办法，所以拿出时间好好的学习一下，并做如下记录:

RSA的加密和解密过程

M为明文，e为加密密钥，n（=p*q）为两个大素数p和q的乘积，C为密文。

加密过程为：
$C\equiv M^e mod n$ （Python代码为：C=pow(M,e,n)）
解密过程为：
$M\equiv C^d mod n$ （Python代码为：M=pow(C,d,n)）

其中欧拉函数： $\varphi (n)=(p-1)*(q-1)$ , $ed mod \varphi(n) =1$

则有欧拉定理： $M^{ed}mod n \equiv M mod n$ 可以利用其对明文进行解密：

故关键在于求出解密密钥d，从而进行解密的工作：

$C^d mod n \equiv (M ^e)^d mod n \equiv M ^{ed}mod n \equiv M mod n$

RSA解密之大素数分解：

先看题目：

from Crypto.Util.number import *
from flag import flag

m = bytes_to_long(flag[len(flag)//2:])
c1 = pow(m, 65537, n1)
print(n1)
print(n2)
print(c1)

# 12247140809348479604921471564180586487768585815975746170325674578797616921111648927242702477878849872543969683338347814412280280399275967477718373503763524190496021552733372883417037599168498325950161981721729170194024953207334645938700509179172701603443701676513036373184117480412000162848957930926901064070342060594727138877649766670745134857766661764036934378476688442276560567422187850356210151257923786787091442756100156773140864849609124767854979536563389490085375904027659938964977986897654680889284563129640670232032177056725742821189174971727601008977911455116640309335831115420212521374638571714779847506053
# 18389822985082119646873913587686535874214217599602396974679000398857538596075663540768658488017065196549474272804093118445292224015944596918389865776422060181560031553109483806084574631951190591647750278938010564724055843810793254313504146882222599273288446350501419313914217291247904310021077585634116444021097314062184927716719544311927232109949949458910134433150322055082587361404772349528719519671478486138727923654663563448615598554419892665963321401035629306132188244405787222119955968919006345792782500580161509588811321029347982139894699422553101422836233000469197166308500535772366619674770468010760793069509
# 7452289103798793077695280417169419455166899701788901836734328155284739957725703294559430435103717320729650111554179307802466425440395009249676073483665440706798647037132729666567531235250930696928916715517814635114285584993316017358168840142715891235370969699037025285851393818308877470156970288072245494257783204219286929267254610734755131380439411294744543265526502113623373731011466745762574276043654138385178215058943331773948951832838630012210745419470596111338808224381556830581941343409140019735062104854628895647516786513885853749857584898509027997081419471042234127652413465022131369647282103361292021252058

上来就是一段加密过程 c1=M^65537 mod n1，让求解M。

作为flag的后半段。

【分析】大素数乘积的分解，其实还是相当难的。本题中给出的提示，在于给出了2个大素数乘积n1和n2.考虑n1和n2可能存在非1的公约数p，并将其进行质因数分解。

n1=pq1；φ(n1)=（p-1）（q1-1）

n2=pq2；φ(n2)=（p-1）（q2-1）

利用分解后的：p、q1、q2、φ(n1)、φ(n2)以及加密密钥 e=65537计算出d1

使的 $d_{1}e mod\varphi (n_1)\equiv 1 mod \varphi (n_1)$ 则有：

$c_1^{d_1} mod n \equiv M^{ed_1} mod n \equiv M mod n$ 得到明文M。

代码如下：

from gmpy2 import *
from Crypto.Util.number import *
from gmpy2 import gmpy2
n1 = 12247140809348479604921471564180586487768585815975746170325674578797616921111648927242702477878849872543969683338347814412280280399275967477718373503763524190496021552733372883417037599168498325950161981721729170194024953207334645938700509179172701603443701676513036373184117480412000162848957930926901064070342060594727138877649766670745134857766661764036934378476688442276560567422187850356210151257923786787091442756100156773140864849609124767854979536563389490085375904027659938964977986897654680889284563129640670232032177056725742821189174971727601008977911455116640309335831115420212521374638571714779847506053
n2 = 18389822985082119646873913587686535874214217599602396974679000398857538596075663540768658488017065196549474272804093118445292224015944596918389865776422060181560031553109483806084574631951190591647750278938010564724055843810793254313504146882222599273288446350501419313914217291247904310021077585634116444021097314062184927716719544311927232109949949458910134433150322055082587361404772349528719519671478486138727923654663563448615598554419892665963321401035629306132188244405787222119955968919006345792782500580161509588811321029347982139894699422553101422836233000469197166308500535772366619674770468010760793069509
c1 = 7452289103798793077695280417169419455166899701788901836734328155284739957725703294559430435103717320729650111554179307802466425440395009249676073483665440706798647037132729666567531235250930696928916715517814635114285584993316017358168840142715891235370969699037025285851393818308877470156970288072245494257783204219286929267254610734755131380439411294744543265526502113623373731011466745762574276043654138385178215058943331773948951832838630012210745419470596111338808224381556830581941343409140019735062104854628895647516786513885853749857584898509027997081419471042234127652413465022131369647282103361292021252058
e = 65537
def RSA_Rev(e, c, n1 ,n2):
    e, c, n1 ,n2= int(e), int(c), int(n1) ,int(n2)
    p_gcd=gmpy2.gcd(n1,n2) # 求n1和n2的最大公因数
    q1 = n1 //p_gcd
    q2 = n2 //p_gcd
    phi_n1 = (p_gcd-1)*(q1-1)
    phi_n2 = (p_gcd - 1) * (q2 - 1)
    d1 = inverse(e,phi_n1) # d1*e % phi_n1 =1 m ^(d1*e) % n1 =m % n1
    d2 = inverse(e,phi_n2) # 同上
    m = powmod(c,d1,n1)
    return m
result = RSA_Rev(e, c1, n1 ,n2)
print(long_to_bytes(result))

结果如下：

RSA解密之共模攻击：

先看题目：

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

p = getPrime(1024)
q = next_prime(p)
n = p*q
e1 = 1804229351
e2 = 17249876309
m = bytes_to_long(flag[:len(flag)//2])
c1 = powmod(m, e1, n)
c2 = powmod(m, e2, n)
print(n)
print(c1)
print(c2)

# 14227798861742401852540716332888717235332595511258932399428125495012429818261201186240868671375546180643809315345869312729735352668100158716283088607208451292404162663627276711487019689338710468633410704987197502168728563083176625740126063479495238167172984219407273900290523981389590563738381174675125435910563235888367915191897285579603935365223154045281581682419312751840903594240019982429628783417855528538794749433531158095360003466935959998857033447113462277578120492816081299626797105667620276866227089279904252740529472535147948228322463932897858201223663561471426466212106824114272839095863012820259336144059
# 2748368338696399356059406385595312945664440371827956927334789404676901454102258919606868152316540385208000463440642761405287879849569027874020681549355300369946702438156485982211384887885124482886967526864840331863086331594662631795454303553020872355558178592976537422361579416265570900102758062505943962255117499346913057374083882684989835965522480643110087603318579121205304404525946236083422871576410697046565047678593910601977734714132476221979200843364581376279502810707173477398690996102015964800459309922068049093010978452962359847790672073676418003395400614683686978263829951605421909668803604395510743059852
# 7070101276345592005624370014550240854479574593424211969938240649666938643751466941171043776915676449023981211165935555219820790824597614949347284608975026562914985986222063806111480956426496504946556407374220265497227856480882948301228596856723114892828393147144049633993243598137175008738994501015560080538905886895711926557416875199213888637411899436223058290795415456592713694897141072831473700612930436542512188279951300184002129218824508009944169253380101810937753798244332498115742220765186344500364110972416546143065744238998801429682525071611493344804655212311225682161372326990125019588149565451158694390151

该题中，分别使用了e1、e2两个加密密钥分别对明文m进行了加密，且共用一个n（=p*q），得到了密文c1和c2。

欧几里得算法：

则有 $c_1^{x}c_2^{y}mod n \equiv M^{e_1 x} M^{e_2 y} mod n \equiv M^{e_1 x+e_2 y} mod n \equiv M mod n$

代码如下：

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

c1 = 2748368338696399356059406385595312945664440371827956927334789404676901454102258919606868152316540385208000463440642761405287879849569027874020681549355300369946702438156485982211384887885124482886967526864840331863086331594662631795454303553020872355558178592976537422361579416265570900102758062505943962255117499346913057374083882684989835965522480643110087603318579121205304404525946236083422871576410697046565047678593910601977734714132476221979200843364581376279502810707173477398690996102015964800459309922068049093010978452962359847790672073676418003395400614683686978263829951605421909668803604395510743059852
c2 = 7070101276345592005624370014550240854479574593424211969938240649666938643751466941171043776915676449023981211165935555219820790824597614949347284608975026562914985986222063806111480956426496504946556407374220265497227856480882948301228596856723114892828393147144049633993243598137175008738994501015560080538905886895711926557416875199213888637411899436223058290795415456592713694897141072831473700612930436542512188279951300184002129218824508009944169253380101810937753798244332498115742220765186344500364110972416546143065744238998801429682525071611493344804655212311225682161372326990125019588149565451158694390151
e1 = 1804229351
e2 = 17249876309
# e1=4
# e2=8
n = 14227798861742401852540716332888717235332595511258932399428125495012429818261201186240868671375546180643809315345869312729735352668100158716283088607208451292404162663627276711487019689338710468633410704987197502168728563083176625740126063479495238167172984219407273900290523981389590563738381174675125435910563235888367915191897285579603935365223154045281581682419312751840903594240019982429628783417855528538794749433531158095360003466935959998857033447113462277578120492816081299626797105667620276866227089279904252740529472535147948228322463932897858201223663561471426466212106824114272839095863012820259336144059

def RSA_ComModAtk(e1, e2, c1, c2, n):
    e1, e2, c1, c2, n = int(e1), int(e2), int(c1), int(c2), int(n)
    if gmpy2.gcd(e1,e2) ==1:
        s = gmpy2.gcdext(e1, e2)  # 扩展欧几里得算法-辗转相除法使得  x*e1+y*e2=1,求出t和z
        x = s[1]
        y = s[2]
        if x < 0:
            x = - x  # 变指数为正值
            c1 = gmpy2.invert(c1, n)  # 求c1的逆元
        if y < 0:
            y = -y  # 变指数为正值
            c2 = gmpy2.invert(c2, n)  # 求c2的逆元
        m = (pow(c1, x, n) * pow(c2, y, n)) % n  # (c1^x*c2^y)%n=m^e1x*me2y%n=m^(e1x+e2y)%n=m%n=m
        return m
    else :
        return bytes_to_long(b'e1 and e2 are not relatively prime') # e1和e2不互质
result = RSA_ComModAtk(e1, e2, c1, c2, n)
print(long_to_bytes(result))

结果如下：

将2结果合二为一，得到flag。

Python引入Crypto时遇到的问题，及解决方法：

运行程序发现会报错

网上找了很多方法，并不是每个方法都奏效：

我成功的方法是这样的：

第一步：安装

pip install pycryptodome

pip install crypto

pip install pycrypto

第二步：到：【Project的名称】\venv\Lib\site-packages的路径下更改文件夹的名称：

将原来小写的crypto更改为Crypto。

第三步：重新Run一遍程序：

标签：网络安全密码学 python

本文转载自: https://blog.csdn.net/weixin_45616281/article/details/128394711
版权归原作者 01Dr1ver 所有，如有侵权，请联系我们删除。

入坑CTF——RSA解密之大素数分解和共模攻击的Python实现

前言

RSA的加密和解密过程

RSA解密之大素数分解：

RSA解密之共模攻击：

Python引入Crypto时遇到的问题，及解决方法：

第一步：安装

第二步：到：【Project的名称】\venv\Lib\site-packages的路径下更改文件夹的名称：

第三步：重新Run一遍程序：

发表评论

“入坑CTF——RSA解密之大素数分解和共模攻击的Python实现”的评论:

关于作者

overfit同步小助手

相关阅读

文章导航