RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥,“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。
在公开密钥密码体制中,加密密钥(即公开密钥)PK是公开信息,而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的,但却不能根据PK计算出SK。
正是基于这种理论,1978年出现了著名的RSA算法,它通常是先生成一对RSA密钥,其中之一是保密密钥,由用户保存;另一个为公开密钥,可对外公开,甚至可在网络服务器中注册。为提高保密强度,RSA密钥至少为500位长。这就使加密的计算量很大。为减少计算量,在传送信息时,常采用传统加密方法与公开密钥加密方法相结合的方式,即信息采用改进的DES或IDEA对话密钥加密,然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后,用不同的密钥解密并可核对信息摘要。
RSA算法的具体描述如下:
(1)任意选取两个不同的大素数p和q计算乘积n=pq ,φ(n)=(p-1)(q-1) ;
(2)任意选取一个大整数e,满足gcd(e,φ(n))=1 ,也就是e 和φ(n )互质,整数e用做加密钥(注意:e的选取是很容易的,例如,所有大于p和q的素数都可用);
(3)确定的解密钥d,满足demodφ(n)=1 ,即de=kφ(n)+1,k≥1 是一个任意的整数;所以,若知道e和φn ,则很容易计算出d;
(4)公开整数n和e,秘密保存d;
(5)将明文m(m<n是一个整数)加密成密文c,加密算法为:
c=E(m)=modn
(6)将密文c解密为明文m,解密算法为:
m=D(c)=modn
然而只根据n和e(注意:不是p和q)要计算出d是不可能的。因此,任何人都可对明文进行加密,但只有授权用户(知道d)才可对密文解密。
在证明上述公式之前,先了解一下欧拉代数定理。也就是若n, a为正整数,且n,a互质,则:modn=1,φ(n) 为欧拉函数,表示小于n且和n互质的数的个数。特别的,当n为素数时,φ(n)=n-1 ,当p,q为素数时φ(pq)=(p-1)(q-1) 。
所以有
CTF中,对于RSA题型的解题思路大体有如下几种:
1、 直接分解模数N
直接分解模数N是最直接的攻击方法,也是最困难的方法。具体的解析同上RSA安全性分析。
通常可以尝试利用在线网站factordb.com,这一类在线网站进行n的分解。
例题:竞赛平台 (vidar.club)
图1 题目源码
c = 110674792674017748243232351185896019660434718342001686906527789876264976328686134101972125493938434992787002915562500475480693297360867681000092725583284616353543422388489208114545007138606543678040798651836027433383282177081034151589935024292017207209056829250152219183518400364871109559825679273502274955582
n = 135127138348299757374196447062640858416920350098320099993115949719051354213545596643216739555453946196078110834726375475981791223069451364024181952818056802089567064926510294124594174478123216516600368334763849206942942824711531334239106807454086389211139153023662266125937481669520771879355089997671125020789
题目只给了n和c的值,但n的值不是很大,可以爆破分解
图2 大数质因数分解
知道了p,q的值,那么密文很快就能求出来了,python代码如下:
import gmpy2
import binascii
c = 110674792674017748243232351185896019660434718342001686906527789876264976328686134101972125493938434992787002915562500475480693297360867681000092725583284616353543422388489208114545007138606543678040798651836027433383282177081034151589935024292017207209056829250152219183518400364871109559825679273502274955582
n = 135127138348299757374196447062640858416920350098320099993115949719051354213545596643216739555453946196078110834726375475981791223069451364024181952818056802089567064926510294124594174478123216516600368334763849206942942824711531334239106807454086389211139153023662266125937481669520771879355089997671125020789
e = 65537
p = 11239134987804993586763559028187245057652550219515201768644770733869088185320740938450178816138394844329723311433549899499795775655921261664087997097294813
q = 12022912661420941592569751731802639375088427463430162252113082619617837010913002515450223656942836378041122163833359097910935638423464006252814266959128953
# invert是求乘法逆元
d = gmpy2.invert(e,(p-1)*(q-1))
jiemi = hex(pow(c,d,n))[2:]
print(binascii.unhexlify(jiemi))
得到flag的值
b'hgame{factordb.com_is_strong!}'
2、 利用公约数分解N
识别此类题目,通常会发现题目给了多个n,均不相同,并且都是2048bit,4096bit级别,无法正面硬杠,并且明文都没什么联系,e也一般取65537。
这种题目一般可以直接gcd(n1,n2)求出一个因数。
例题:攻防世界 (xctf.org.cn)
图3 题目描述
Python代码如下:
import gmpy2
n1 = 23220619839642624127208804329329079289273497927351564011985292026254914394833691542552890810511751239656361686073628273309390314881604580204429708461587512500636158161303419916259271078173864800267063540526943181173708108324471815782985626723198144643256432774984884880698594364583949485749575467318173034467846143380574145455195152793742611717169602237969286580028662721065495380192815175057945420182742366791661416822623915523868590710387635935179876275147056396018527260488459333051132720558953142984038635223793992651637708150494964785475065404568844039983381403909341302098773533325080910057845573898984314246089
n2 = 22642739016943309717184794898017950186520467348317322177556419830195164079827782890660385734113396507640392461790899249329899658620250506845740531699023854206947331021605746078358967885852989786535093914459120629747240179425838485974008209140597947135295304382318570454491064938082423309363452665886141604328435366646426917928023608108470382196753292656828513681562077468846105122812084765257799070754405638149508107463233633350462138751758913036373169668828888213323429656344812014480962916088695910177763839393954730732312224100718431146133548897031060554005592930347226526561939922660855047026581292571487960929911
p = gmpy2.gcd(n1, n2)
print('gcd(n1, n2):n', p)
q1 = n1// p
q2 = n2// p
print('q1 is:n', q1)
print('q2 is:n', q2)
求出了p和q的值,那么问题也就迎刃而解了,最后的flag答案为:flag{336BB5172ADE227FE68BAA44FDA73F3B}。
3、 构造平方数分解模数N
识别此类题目,通常会发现N的两个质因数p和q挨的非常近,这个时候就可以将N加一个比较小的数k,令N+k为平方数,从而解决此类题目。
例题:攻防世界 (xctf.org.cn)
图4 题目代码
设p=q+2k,k是一个相对比较小的数,因为n=pq,所以n=+2kq,所以n+=,我们只要爆破k,使得n+是一个平方数,那么p和q就都解出来了。代码如下:
n = 12194420073815392880989031611545296854145241675320130314821394843436947373331080911787176737202940676809674543138807024739454432089096794532016797246441325729856528664071322968428804098069997196490382286126389331179054971927655320978298979794245379000336635795490242027519669217784433367021578247340154647762800402140321022659272383087544476178802025951768015423972182045405466448431557625201012332239774962902750073900383993300146193300485117217319794356652729502100167668439007925004769118070105324664379141623816256895933959211381114172778535296409639317535751005960540737044457986793503218555306862743329296169569
def is_square(n):
low, high, ans = 0, n, -1
while low <= high:
mid = (low + high) // 2
if mid * mid <= n:
ans = mid
low = mid + 1
else:
high = mid - 1
if ans**2 == n:
return True
else:
return False
for i in range(1000):
if is_square(n+i**2):
print(i)
break
得到k的值为716,所以可以解出pq的值,从而flag就出来了,代码如下:
import gmpy2
import binascii
c = 4504811333111877209539001665516391567038109992884271089537302226304395434343112574404626060854962818378560852067621253927330725244984869198505556722509058098660083054715146670767687120587049288861063202617507262871279819211231233198070574538845161629806932541832207041112786336441975087351873537350203469642198999219863581040927505152110051313011073115724502567261524181865883874517555848163026240201856207626237859665607255740790404039098444452158216907752375078054615802613066229766343714317550472079224694798552886759103668349270682843916307652213810947814618810706997339302734827571635179684652559512873381672063
n = 12194420073815392880989031611545296854145241675320130314821394843436947373331080911787176737202940676809674543138807024739454432089096794532016797246441325729856528664071322968428804098069997196490382286126389331179054971927655320978298979794245379000336635795490242027519669217784433367021578247340154647762800402140321022659272383087544476178802025951768015423972182045405466448431557625201012332239774962902750073900383993300146193300485117217319794356652729502100167668439007925004769118070105324664379141623816256895933959211381114172778535296409639317535751005960540737044457986793503218555306862743329296169569
e = 65537
p = 110428348144013242234907008083355974834266917027228724749730385104087025249352345946164980361082178532313669767485270254326404723948153912910688118140621712922649644396733499972695482991866293857864311557686710317462165131360819813493524457615383204504505224030129953230866877990529769205769592709254542472051
q = 110428348144013242234907008083355974834266917027228724749730385104087025249352345946164980361082178532313669767485270254326404723948153912910688118140621712922649644396733499972695482991866293857864311557686710317462165131360819813493524457615383204504505224030129953230866877990529769205769592709254542470619
# invert是求乘法逆元
d = gmpy2.invert(e,(p-1)*(q-1))
jiemi = hex(pow(c,d,n))[2:]
print(binascii.unhexlify(jiemi))
flag{5c9c885c361541e0b261f58b61db8cec}
4、 共模攻击
共模攻击,也称同模攻击。
同模攻击利用的大前提就是,RSA体系在生成密钥的过程中使用了相同的模数n。
在CTF题目中,就是同一明文,同一n,不同e,进行加密。
m,n相同;e,c不同,且e1 和 e2互质
例题:攻防世界 (xctf.org.cn)
题目给了四个文件,先用代码看一下题目信息:
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
f1 = open('publickey1.pem',"rb").read()
f2 = open('publickey2.pem',"rb").read()
c1 = open('cipher1.txt',"rb").read()
c2 = open('cipher2.txt',"rb").read()
pub1 = RSA.importKey(f1)
pub2 = RSA.importKey(f2)
n1 = pub1.n
e1 = pub1.e
n2 = pub2.n
e2 = pub2.e
c1 = bytes_to_long(c1)
c2 = bytes_to_long(c2)
print("n1 =",n1)
print("e1 =",e1)
print("c1 =",c1)
print("n2 =",n2)
print("e2 =",e2)
print("c2 =",c2)
得到:
n1
13060424286033164731705267935214411273739909173486948413518022752305313862238166593214772698793487761875251030423516993519714215306808677724104692474199215119387725741906071553437840256786220484582884693286140537492541093086953005486704542435188521724013251087887351409946184501295224744819621937322469140771245380081663560150133162692174498642474588168444167533621259824640599530052827878558481036155222733986179487577693360697390152370901746112653758338456083440878726007229307830037808681050302990411238666727608253452573696904083133866093791985565118032742893247076947480766837941319251901579605233916076425572961
e1 = 117
c1
12847007370626420814721007824489512747227554004777043129889885590168327306344216253180822558098466760014640870748287016523828261890262210883613336704768182861075014368378609414255982179769686582365219477657474948548886794807999952780840981021935733984348055642003116386939014004620914273840048061796063413641936754525374790951194617245627213219302958968018227701794987747717299752986500496848787979475798026065928167197152995841747840050028417539459383280735124229789952859434480746623573241061465550303008478730140898740745999035563599134667708753457211761969806278000126462918788457707098665612496454640616155477050
n2
13060424286033164731705267935214411273739909173486948413518022752305313862238166593214772698793487761875251030423516993519714215306808677724104692474199215119387725741906071553437840256786220484582884693286140537492541093086953005486704542435188521724013251087887351409946184501295224744819621937322469140771245380081663560150133162692174498642474588168444167533621259824640599530052827878558481036155222733986179487577693360697390152370901746112653758338456083440878726007229307830037808681050302990411238666727608253452573696904083133866093791985565118032742893247076947480766837941319251901579605233916076425572961
e2 = 65537
c2
6830857661703156598973433617055045803277004274287300997634648800448233655756498070693597839856021431269237565020303935757530559600152306154376778437832503465744084633164767864997303080852153757211172394903940863225981142502888126928982009493972076013486758460894416710122811249903322437742241269681934551237431668187006176418124934488775505816544733929241927900392924886649420943699356314278255683484998359663404611236056664149725644051300950988495549164517140159041907329062655574220869612072289849679613024196448446224406889484578310512232665571188351621585528255501546941332782446448144033997067917984719103068519
发现n1和n2的值是相等的,那么就可以通过共模攻击解决此题,原理如下:
共模攻击即用两个及以上的公钥(n,e)来加密同一条信息m
已知有密文:
条件:
当e1,e2互质,则有gcd(e1,e2)=1
根据扩展欧几里德算法,对于不完全为 0 的整数 a,b,gcd(a,b)。那么一定存在整数 x,y 使得 gcd(a,b)=ax+by
带入本题,则得到:
e1×s1+e2×s2 = 1,s1,s2 为变量。
因为e1和e2为正整数,又由于s1、s2皆为整数,但是一正一负,此时假设s1为正数,s2为负数。
这里需要用到两条幂运算的性质:
(a × b) mod p = (a mod p × b mod p) mod p 公式一
mod p = mod p公式二
因为c1 = mod n,c2 = mod n,需要证明m=( )mod n
先代入公式一可得:
( )mod n = ( )mod n
=( )mod n //代入公式二
=( )mod n //消掉mod n
=( )mod n //同底数幂相乘,底数不变,指数相加
又因为m<n,所以( )mod n =m mod n=m
以下为求s1,s2的python代码:
e1 = 117
e2 = 65537
def ext_gcd(a, b): #扩展欧几里得算法
if b == 0:
return 1, 0, a
else:
x, y, gcd = ext_gcd(b, a % b) #递归直至余数等于0(需多递归一层用来判断)
x, y = y, (x - (a // b) * y) #辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立
return x, y, gcd
print(ext_gcd(e1,e2))
得到s1=30808,s2=-55,带入上面公式,得到flag:
import binascii
c1 = 12847007370626420814721007824489512747227554004777043129889885590168327306344216253180822558098466760014640870748287016523828261890262210883613336704768182861075014368378609414255982179769686582365219477657474948548886794807999952780840981021935733984348055642003116386939014004620914273840048061796063413641936754525374790951194617245627213219302958968018227701794987747717299752986500496848787979475798026065928167197152995841747840050028417539459383280735124229789952859434480746623573241061465550303008478730140898740745999035563599134667708753457211761969806278000126462918788457707098665612496454640616155477050
n = 13060424286033164731705267935214411273739909173486948413518022752305313862238166593214772698793487761875251030423516993519714215306808677724104692474199215119387725741906071553437840256786220484582884693286140537492541093086953005486704542435188521724013251087887351409946184501295224744819621937322469140771245380081663560150133162692174498642474588168444167533621259824640599530052827878558481036155222733986179487577693360697390152370901746112653758338456083440878726007229307830037808681050302990411238666727608253452573696904083133866093791985565118032742893247076947480766837941319251901579605233916076425572961
c2 = 6830857661703156598973433617055045803277004274287300997634648800448233655756498070693597839856021431269237565020303935757530559600152306154376778437832503465744084633164767864997303080852153757211172394903940863225981142502888126928982009493972076013486758460894416710122811249903322437742241269681934551237431668187006176418124934488775505816544733929241927900392924886649420943699356314278255683484998359663404611236056664149725644051300950988495549164517140159041907329062655574220869612072289849679613024196448446224406889484578310512232665571188351621585528255501546941332782446448144033997067917984719103068519
s1 = 30808
s2 = -55
jiemi = hex(pow(pow(c1,s1,n)*pow(c2,s2,n),1,n))[2:]
print(binascii.unhexlify(jiemi))
flag{interesting_rsa}
5、 低指数攻击
加密指数指的是e,e一般选取65535,当e很小,可直接破解。这类攻击在CTF题中,一般是 e=3
图5 低指数攻击原理
例题:BUUCTF在线评测 (buuoj.cn)
图6 题目描述
从题目发现,e的值非常的小,为3。由于 ,因而 ,只要爆破k,使得kn+c 是一个立方数即可。Python代码如下:
import gmpy2
from Crypto.Util.number import *
n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
e = 3
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
def de(c, e, n):
k = 0
while True:
m = c + n*k
result, flag = gmpy2.iroot(m, e)
if True == flag:
return result
k += 1
m = de(c,e,n)
print(long_to_bytes(m))
得到flag的值b'flag{25df8caf006ee5db94d48144c33b2c3b}'
6、 低指数广播攻击
如果选取的加密指数较低,并且使用了相同的加密指数给一个接受者的群发送相同的信息,那么可以进行广播攻击得到明文。
在CTF中,n、c不同,明文m,e相同,其e比较小。使用中国剩余定理求解。
例题:攻防世界 (xctf.org.cn)
图7 题目描述
这道题在求E2的时候用到了低指数广播攻击。由于题目告知了E2的89次方分别模三个不同的数得到的不同的结果,因而可以用中国剩余定理进行解决。原理也就是先解决同余方程:
找到其中的一个解mx ,那么就一定有 ,接着按照低指数攻击的方法进行求解。本题中给了三组c和n。
代码如下:
import gmpy2
import sympy
from functools import reduce
def chinese_remainder(n, a):
sum = 0
prod = reduce(lambda a, b: a * b, n)
for n_i, a_i in zip(n, a):
p = prod // n_i
sum += a_i * sympy.invert(p, n_i) * p
return int(sum % prod)
ns=[15863230586500684911356384742123404120213699052018048588650392009927565369685497256344682150189923131009586323640507773706997704860898682946308031020361302334248895233255911348365179153799197341744863134926804603973507415697810440916305092395180382239729550833607847524005391137474497849077097574452115379368463540087172800902210822143687014813631366360652583216269138116785489485772437870528892032119729929607857459621078790511144060710035933887337208301078892163837203412081114510143406013892393607932596921308889058909544584619676380766485493114814753878272881866907210235681877689493671668534251778397658670518117, 14144098469438619358682652828507744381697293556670717685553585719665002440476256008471235313826051740009083510860714991201047915737216102220242621674841600987122005914542061963618272275986835928673920375768272390912778741502655909281390948606467847118377641357547931472588836726339758576038273820470879637555458446243401248151675266602656677360819563744765522495640821496694918515669243614141704744848980746101569785439728585144841655665959389460512628800782742764147773150430552859331269667626942993392101897661719871375721143240270211821269260950380944670195863016621594387236339317938305273510719419578308449465183, 27563822879593503938377821960427219022565215631856333510782568496016547757945464794632272818101891677705256471714805217606503652132995136255720639088424576003650628211271025648183600635145895528466199068640094470078526413324708028578289949241288828542143203769199399500669311878391255837977932634772778594526940501234736059441483897017015324765266787399950699732518347518591167932031031320265136158304460199654008895095274754918153773566824931440342525688741289235153882699461549523425169846266597156773535163599640189457171272058311480951820887261040891344076039474315985825984444520336790670313179493074014037981261]
cs=[3833095607830862948079097323254872789586576953317671099752083261949616608759231291050566542764984974722790226120399722937104503590740358249900089784508490830379531632752169777949200718567033018577184658177019404903817920024468923715441355404672443007723525750768430895425376124679225715687382380114628103058312176343693900115638265002657622618744666247132114654135429040069316368839938881716554901593031901272992940200484460436193699175500376368456706998564064693820008778900344357745691652875500810447147088715289581351501876012044611990972521570253106671158207677490849249612002954497927762168699886110455354481924, 1502420121177211156091634258259634977709023894278792755694473756163084431123774101512866316989917922052023168401167212284219907272528117024670443698990238243030221117004372456475521502350404137469088570170885409265567084376069256924135270283335242133163303599239181417949980292944203204296598188175632723968779672994090788585343302473442389865459398142634104331743517384589200789331489394375604801951994831647339839112698394141328178967516636452592385248135340133712522135715943787590172334743893259621909532456281362868290556461907936774231166936915669816509378419892149164552548131776979706381641477878931403040942, 8992204063713908492214256291861339175525948946919629972908439132005643626148678347198381531633907182877152728077958345519083406637446972079387161726967295886447791613166577391233866583354793842121902234644830640050181130381996083089350911224037154798259291124104894554037604500881250119806371348673833105103600782286898276354573884788251542211434143476774391457587885772379990104835187104619922442613860682792470389490804228050671124495925536024571104944112397143299499508504917890140939438891891453283594000764399193028606955089853654071198909973555844004685149713774167524224100487937899126480545681565581673958854]
res = chinese_remainder(ns,cs)
print(gmpy2.iroot(res,89))
得到E2 = 561236991551738188085
7、 拆解e转化
正常的RSA应该有e与φ(n)互素,但是有的题目并不满足,但通常会给两组关于e与φ(n)的等式。这个时候就需要将e进行质因数分解,构造出新的RSA求解。
例题和6一样,6中求出了E2的值,而E1可以通过爆破求解得出,代码如下:
from gmpy2 import invert,iroot
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
def next_prime(num: int) -> int:
num = num + 2 if num % 2 else num + 1
while not isPrime(num):
num += 2
return num
n = 1605247600724752598798254639224215706171506359654961357324428027985787942008103766562745464838961569081446916113769517713344420113584254259000172572811154232107339480903672251992191997458469905064423618888336088652352540882576826988355783159237971043770132628344798937353150930071309347972804118952814447576207066147031238749098842662046825743988208813903138796789940911515825517078554074496474819128789835309636804325132602557092847746454786387067599510769382078521691609970320528531270474091713477040343897269903489441410062592732302402854035415438078656688806905350495825334584533345448091335565792091890185673190424063
e = 65537
c = 751639057610677013264061431434189083017589908118307247217007533938435229431015858783222167911772848893015518607229280589985711010766459396989232072512314594917029375221335361209036112742388866873824163350886610514973038316512032459352053158417705406031466332440378871927174731975794579894912999936641163063898365134788537389162378185448090279397717831977803284480743612393591614284972981435749362255654561121758163485884075260156288337176713756471879489767416836868661153693157792733142765671887792303181376620864506386820826866340907593080654521498766421056474652652337037121881207188033108746890998208582406826010121861
for i in range(2 ** 16,2**15,-1):
print('\r'+str((65536-i)/32768*100)+"%",end='')
if isPrime(i):
q = next_prime(i * iroot(n // i, 2)[0] + 38219)
if n % q == 0:
print(q)
break
p = n // q
phi = (p - 1) * (q - 1)
d = invert(e, phi)
E1 = pow(c, d, n)
print(E1)
得到E1的值E1 = 377312346502536339265
接着通过观察,发现n1和n2有共同的因数P,所以可以辗转相除法求出P。
Python代码如下:
import gmpy2
n1 = 21655617838358037895534605162358784326495251462447218485102155997156394132443891540203860915433559917314267455046844360743623050975083617915806922096697304603878134295964650430393375225792781804726292460923708890722827436552209016368047420993613497196059326374616217655625810171080545267058266278112647715784756433895809757917070401895613168910166812566545593405362953487807840539425383123369842741821260523005208479361484891762714749721683834754601596796707669718084343845276793153649005628590896279281956588607062999398889314240295073524688108299345609307659091936270255367762936542565961639163236594456862919813549
n2 = 24623016338698579967431781680200075706241014384066250660360949684385831604822817314457973559632215801205780786144608311361063622813017396858888436529116737754653067203843306015767091585697803364656624926853551997229897087731298797904208292585562517602132663331748784390752958757661484560335406769204491939879324079089140420467301773366050084810282369044622442784113688062220370531522036512803461607049619641336524486507388232280683726065679295742456158606213294533956580462863488082028563360006966912264908424680686577344549034033470952036766850596897062924137344079889301948258438680545785139118107899367307031396309
p = gmpy2.gcd(n1, n2)
print('gcd(n1, n2):\n', p)
q1 = n1// p
q2 = n2// p
print('q1 is:\n', q1)
print('q2 is:\n', q2)
得到结果:
gcd(n1, n2):
139221606892711163311861502165720779685040991146236819771077311473266519931947605782571900027963055886773086091452724527664738159398782494677824268515616754695749805253260616352348311702497776259344985568675527862394653437170150947836869132073518219409311180128931469597871185033476336585646820347139844842399
q1 is:
155547822796260230301163493572328276759754179923840369685187766807125087369928975444183346813644731672051277851645460274588975060909127179689654378234675963719955065971621191295992778117297548246126322013897580863954772277036417493420548297592968260640347856809237210752134250598888189729496548294692404268851
q2 is:
176862032325728733112232812799746628539676281475101885729648695725069625447450093015182103211896449720721008446169371711893103335768209077906398522734998474760674095210567056451011572994691734256964295917711714584736577060817163508416373914379207885134617634676468095190710307036248746843930480925386278062091
接着就是本题的题型了,这道题目中q1-1和q2-1都是5的倍数,p-1是7的倍数,而恰巧e1和e2都是35的倍数,不满足e1,e2和(q1-1)和( p-1),(q2-1)和( p-1)互质,原来的方法失效。所以我们要尝试进行转化,构造一个新的RSA。
我们先假设gcd(e,φ(n))=a ,那么就可以将e写成e=E×a 的形式。再构造d使得dEmodφ(n)=1 。由于RSA的加密算法为 ,解密算法为 其中demodφn=1 。
那么变形之后可得到:
带入本题,可以知道a=35 , , 。其中d1E1modφ(n1)=1,d2E2mod(φn2)=1,e1=aE1,e2=aE2 。
再根据公式若n=pq,wmodn=c 则wmodp=cmodp,wmodq=cmodq 。
因而代入本题,有 。
为了方便,这里设 ,那么有 ,根据中国剩余定理,可以很快求出一个数k,使得 ,于是一个新的RSA就构造好了。由于在本题中q1-1,q2-1 都是5的倍数,而a也是5的倍数,并没有满足互质的前提,因而需要变形一下。由于a=35=5×7 。所以 ,7和q1-1,q2-1 是互质的,满足RSA的构造条件,因而可以求出m5 的值,最后开五次方就可以得到答案了。Python代码如下:
from Crypto.Util.number import long_to_bytes
import gmpy2
import sympy
from functools import reduce
n1 = 21655617838358037895534605162358784326495251462447218485102155997156394132443891540203860915433559917314267455046844360743623050975083617915806922096697304603878134295964650430393375225792781804726292460923708890722827436552209016368047420993613497196059326374616217655625810171080545267058266278112647715784756433895809757917070401895613168910166812566545593405362953487807840539425383123369842741821260523005208479361484891762714749721683834754601596796707669718084343845276793153649005628590896279281956588607062999398889314240295073524688108299345609307659091936270255367762936542565961639163236594456862919813549
n2 = 24623016338698579967431781680200075706241014384066250660360949684385831604822817314457973559632215801205780786144608311361063622813017396858888436529116737754653067203843306015767091585697803364656624926853551997229897087731298797904208292585562517602132663331748784390752958757661484560335406769204491939879324079089140420467301773366050084810282369044622442784113688062220370531522036512803461607049619641336524486507388232280683726065679295742456158606213294533956580462863488082028563360006966912264908424680686577344549034033470952036766850596897062924137344079889301948258438680545785139118107899367307031396309
c1 = 2615722342860373905833491925692465899705229373785773622118746270300793647098821993550686581418882518204094299812033719020077509270290007615866572202192731169538843513634106977827187688709725198643481375562114294032637211892276591506759075653224150064709644522873824736707734614347484224826380423111005274801291329132431269949575630918992520949095837680436317128676927389692790957195674310219740918585437793016218702207192925330821165126647260859644876583452851011163136097317885847756944279214149072452930036614703451352331567857453770020626414948005358547089607480508274005888648569717750523094342973767148059329557
c2 = 6769301750070285366235237940904276375318319174100507184855293529277737253672792851212185236735819718282816927603167670154115730023644681563602020732801002035524276894497009910595468459369997765552682404281557968383413458466181053253824257764740656801662020120125474240770889092605770532420770257017137747744565202144183642972714927894809373657977142884508230107940618969817885214454558667008383628769508472963039551067432579488899853537410634175220583489733111861415444811663313479382343954977022383996370428051605169520337142916079300674356082855978456798812661535740008277913769809112114364617214398154457094899399
E1 = 377312346502536339265
E2 = 561236991551738188085
P = gmpy2.gcd(n1,n2)
Q2 = n2//P
Q1 = n1//P
c = [pow(c1, gmpy2.invert(E1 // 35, (P - 1) * (Q1 - 1)), n1),
pow(c2, gmpy2.invert(E2 // 35, (P - 1) * (Q2 - 1)), n2)]
w2 = c[1] %Q2
w1 = c[0] %Q1
def chinese_remainder(n, a):
sum = 0
prod = reduce(lambda a, b: a * b, n)
for n_i, a_i in zip(n, a):
p = prod // n_i
sum += a_i * sympy.invert(p, n_i) * p
return int(sum % prod)
result = chinese_remainder([Q1,Q2],[w1,w2])
d = gmpy2.invert(7,(Q1-1)*(Q2-1))
n = Q1*Q2
m = pow(result,d,n)
flag = gmpy2.iroot(m,5)[0]
print(long_to_bytes(flag))
得到flag的值flag{27dab675-9e9b-4c1f-99ab-dd9fe49c190a}
8、 多素数分解
这类题目的n并不是两个大素数相乘,往往是多个素数的乘积,但解法是类似的。
例题:攻防世界 (xctf.org.cn)
图8 题目描述
本题的n就是5个大素数的乘积,先将其进行分解。
图9 分解结果图
接着欧拉函数就要相应的进行变化,两个素数的时候,欧拉函数为φ(n)=(p-1)(q-1) ;相应的,多个素数时,欧拉函数就是每个素数减一再乘起来,代码如下:文章来源:https://www.toymoban.com/news/detail-460580.html
import gmpy2
import binascii
c = 144009221781172353636339988896910912047726260759108847257566019412382083853598735817869933202168
n = 175797137276517400024170861198192089021253920489351812147043687817076482376379806063372376015921
E = 0x10001
data=[9401433281508038261,10252499084912054759,11215197893925590897,11855687732085186571,13716847112310466417]
phi = 1
for p in data:
phi = phi * (p-1)
# invert是求乘法逆元
d = gmpy2.invert(E,phi)
jiemi = hex(pow(c,d,n))[2:]
print(binascii.unhexlify(jiemi))
得到flag: HSCTF{@Tv0_br3ad5_c1ip_cHe3se_!@}文章来源地址https://www.toymoban.com/news/detail-460580.html
到了这里,关于CTF学习笔记一——RSA加密的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!