CTF学习笔记一——RSA加密

这篇具有很好参考价值的文章主要介绍了CTF学习笔记一——RSA加密。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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,k1 是一个任意的整数;所以,若知道e和φn ,则很容易计算出d;

(4)公开整数n和e,秘密保存d;

(5)将明文m(m<n是一个整数)加密成密文c,加密算法为: 

c=E(m)=CTF学习笔记一——RSA加密modn

(6)将密文c解密为明文m,解密算法为: 

m=D(c)=CTF学习笔记一——RSA加密modn

然而只根据n和e(注意:不是p和q)要计算出d是不可能的。因此,任何人都可对明文进行加密,但只有授权用户(知道d)才可对密文解密

在证明上述公式之前,先了解一下欧拉代数定理。也就是若n, a为正整数,且n,a互质,则:CTF学习笔记一——RSA加密modn=1φ(n) 为欧拉函数,表示小于n且和n互质的数的个数。特别的,当n为素数时,φ(n)=n-1 ,当p,q为素数时φ(pq)=(p-1)(q-1)

所以有

CTF学习笔记一——RSA加密

   CTF中,对于RSA题型的解题思路大体有如下几种:

1、 直接分解模数N

直接分解模数N是最直接的攻击方法,也是最困难的方法。具体的解析同上RSA安全性分析。

通常可以尝试利用在线网站factordb.com,这一类在线网站进行n的分解。

   例题:竞赛平台 (vidar.club)

CTF学习笔记一——RSA加密

图1 题目源码

c = 110674792674017748243232351185896019660434718342001686906527789876264976328686134101972125493938434992787002915562500475480693297360867681000092725583284616353543422388489208114545007138606543678040798651836027433383282177081034151589935024292017207209056829250152219183518400364871109559825679273502274955582  

n = 135127138348299757374196447062640858416920350098320099993115949719051354213545596643216739555453946196078110834726375475981791223069451364024181952818056802089567064926510294124594174478123216516600368334763849206942942824711531334239106807454086389211139153023662266125937481669520771879355089997671125020789  

题目只给了n和c的值,但n的值不是很大,可以爆破分解

CTF学习笔记一——RSA加密

图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)

CTF学习笔记一——RSA加密

图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)

CTF学习笔记一——RSA加密

图4 题目代码

设p=q+2k,k是一个相对比较小的数,因为n=pq,所以n=+2kq,所以n+=CTF学习笔记一——RSA加密,我们只要爆破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

已知有密文:

CTF学习笔记一——RSA加密

       CTF学习笔记一——RSA加密

条件:

当e1,e2互质,则有gcd(e1,e2)=1

根据扩展欧几里德算法,对于不完全为 0 的整数 a,b,gcd(a,b)。那么一定存在整数 x,y 使得 gcd(a,b)=ax+by

带入本题,则得到:

e1×s1+e2×s2 = 1s1s2 为变量。

因为e1和e2为正整数,又由于s1、s2皆为整数,但是一正一负,此时假设s1为正数,s2为负数。

这里需要用到两条幂运算的性质:

(a × b) mod p = (a mod p × b mod p) mod p 公式一

CTF学习笔记一——RSA加密mod p =CTF学习笔记一——RSA加密 ​​​​​​​  mod p公式二

因为c1 =CTF学习笔记一——RSA加密 ​​​​​​​mod n,c2 = CTF学习笔记一——RSA加密 ​​​​​​​ mod n,需要证明m=(CTF学习笔记一——RSA加密 ​​​​​​​)mod n

先代入公式一可得:

(CTF学习笔记一——RSA加密 ​​​​​​​)mod n = (CTF学习笔记一——RSA加密 ​​​​​​​)mod n​​​​​​​

=(CTF学习笔记一——RSA加密 ​​​​​​​ )mod n  //代入公式二

=(CTF学习笔记一——RSA加密 ​​​​​​​)mod n  //消掉mod n

=(CTF学习笔记一——RSA加密 ​​​​​​​)mod n   //同底数幂相乘,底数不变,指数相加

又因为m<n,所以(CTF学习笔记一——RSA加密 ​​​​​​​)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

CTF学习笔记一——RSA加密

图5 低指数攻击原理

例题:BUUCTF在线评测 (buuoj.cn)

CTF学习笔记一——RSA加密

图6 题目描述

从题目发现,e的值非常的小,为3。由于CTF学习笔记一——RSA加密 ​​​​​​​ ,因而CTF学习笔记一——RSA加密 ​​​​​​​,只要爆破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)

CTF学习笔记一——RSA加密

图7 题目描述

这道题在求E2的时候用到了低指数广播攻击。由于题目告知了E2的89次方分别模三个不同的数得到的不同的结果,因而可以用中国剩余定理进行解决。原理也就是先解决同余方程:

CTF学习笔记一——RSA加密

CTF学习笔记一——RSA加密

CTF学习笔记一——RSA加密

CTF学习笔记一——RSA加密

找到其中的一个解mx ,那么就一定有CTF学习笔记一——RSA加密 ​​​​​​​,接着按照低指数攻击的方法进行求解。本题中给了三组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的加密算法为CTF学习笔记一——RSA加密 ​​​​​​​ ,解密算法为CTF学习笔记一——RSA加密 ​​​​​​​ 其中demodφn=1

那么变形之后可得到:

CTF学习笔记一——RSA加密 ​​​​​​​

带入本题,可以知道a=35 CTF学习笔记一——RSA加密 ​​​​​​​CTF学习笔记一——RSA加密 ​​​​​​​。其中d1E1modφ(n1)=1d2E2mod(φn2)=1e1=aE1e2=aE2

再根据公式若n=pqwmodn=c wmodp=cmodpwmodq=cmodq

因而代入本题,有CTF学习笔记一——RSA加密 ​​​​​​​

为了方便,这里设CTF学习笔记一——RSA加密 ​​​​​​​ ,那么有CTF学习笔记一——RSA加密 ​​​​​​​,根据中国剩余定理,可以很快求出一个数k,使得CTF学习笔记一——RSA加密 ​​​​​​​,于是一个新的RSA就构造好了。由于在本题中q1-1q2-1 都是5的倍数,而a也是5的倍数,并没有满足互质的前提,因而需要变形一下。由于a=35=5×7 。所以CTF学习笔记一——RSA加密 ​​​​​​​ ,7和q1-1q2-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)

CTF学习笔记一——RSA加密

图8 题目描述

本题的n就是5个大素数的乘积,先将其进行分解。

CTF学习笔记一——RSA加密

图9 分解结果图

接着欧拉函数就要相应的进行变化,两个素数的时候,欧拉函数为φ(n)=(p-1)(q-1) ;相应的,多个素数时,欧拉函数就是每个素数减一再乘起来,代码如下:

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【密码学复习】第七章 公钥加密体制(二)

    RSA单向陷门函数及其应用 ElGamal单向陷门函数 1)密钥生成 ① 选择一大素数 p ,选取Z p * 的生成元 g ; ② 任选 小于 p 的随机数 x ,计算 y ≡ g x mod p ; ③ ( y , g , p )为公开密钥, ( x , g , p )为秘密密钥. 2)加密: 设待加密明文为 M . ① 随机选一整数 k ,0 k = p -1; ② 计算密文对

    2024年02月05日
    浏览(54)
  • 信息安全复习六:公开密钥密码学

    1.公开密钥密码模型的基本原理 2.两个算法:RSAD-H算法 主要内容 1.对称密钥密码的密钥交换问题 2.公钥密码模型的提出 3.设计公钥密码的基本要求 4.数字签名 5.RSA算法 6.公钥密码的特征总结 1.对称加密是什么 :对称加密是指加密和解密用的是同一个密钥的加密方式。 2.对称加

    2023年04月25日
    浏览(51)
  • js实现rsa密钥的加密、解密与生成

    今天想用js实现rsa的加解密的,在网上找了好久,下载啊什么的,十分麻烦,今天我也不bb的直接放代码 rsa.html 生成完了后,可以去在线rsa网站上检测一下,RSA在线加解密 下载链接: rsa.zip - 蓝奏云 备用下载链接: 百度网盘 密码1234 参考文献: travist/jsencrypt: (github.com)

    2024年02月16日
    浏览(48)
  • 密码学——Hill体制密码中已知明文M和密文C求解密钥矩阵K的两种方法之逆矩阵求解法和待定系数求解法

    本文主要解决古典密码中的Hill体制密码在已知明文M和密文C的情况下求解密钥矩阵K的两种方法:①求逆矩阵②待定系数法。 如若不懂Hill体制的古典密码可以参照我上一篇文章密码学——几种典型的古典密码体制(Caesar体制、Playfair体制、Vigenere体制、Beaufort体制以及Hill体制)

    2024年02月02日
    浏览(59)
  • CTF入门学习笔记——Crypto密码(古典密码)

    🚀🚀这篇笔记是我对自己初步学习CTF的一个小总结,主要涉及了Crypto板块的古典密码,这部分内容比较简单,利用一些工具加上观察分析一般都能解决,但是古典密码一般会和编码结合起来一起考察,所以此篇笔记主要起到一个分析总结的作用。 🚀🚀凯撒密码算是古典密

    2024年02月09日
    浏览(41)
  • springboot + vue 前后端加密传输 RSA互相加解密、加签验签、密钥对生成

    参考 由于Java非对称加解密、加验签都是采用PKCS#8格式的密钥,PKCS#1格式的密钥跑不通,这里先简单介绍一下两者的区别。 PKCS#1和PKCS#8是两个不同的数字证书标准。 PKCS#1是一个公钥加密标准,它定义了使用RSA算法进行加密和签名的格式。主要用于对数字签名、加密以及数字签

    2024年04月27日
    浏览(41)
  • RSA加密:Web前端登录账户密码加密传输

        一般在做系统时候对安全性要求比较高,现在通常选择https协议来进行数据传输。很多情况下一般的javaweb网站,如果安全要求不是很高的话,用https协议就可以了。在这种情况下,密码的明文传输显然是不合适的,因为请求如果在传输过程中被截了,就可以直接拿明文密

    2024年02月10日
    浏览(55)
  • 【密码学基础】RSA加密算法

    RSA是一种非对称加密算法,即加密和解密时用到的密钥不同。 加密密钥是公钥,可以公开;解密密钥是私钥,必须保密保存。 基于一个简单的数论事实:两个大质数相乘很容易,但想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥,即公钥;而两个

    2024年02月01日
    浏览(65)
  • 使用RSA密钥交换和密码验证进行安全的stelnet远程登录配置实验(华为ensp实现)

    配置R1与R3之间的RSA密钥交换,使得R1可以通过stelnet方式安全地访问R3。 配置R2通过使用密码登录,使得R2可以通过stelnet方式安全地访问R3。 了解了RSA密钥交换和密码验证方式在实际中的应用,加深了对这些知识点的理解。 设备:ensp下的路由器R1,R2,R3和交换机。 连接:R1的

    2024年02月04日
    浏览(54)
  • vue前端对密码进行Rsa加密

    在信息技术发达的信息化世界,我们的敏感信息在各个平台都已进行注册使用。例如我们支付宝的支付密码、微信的支付密码、电子银行的登陆密码、我们的个人身份信息等等都会被不法分子利用。为了保障我们的身份不被暴露以及账户财产安全,研发人员使用了很多加密算

    2024年02月13日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包