CTF_RSA解密学习指南(三)

首发于知乎:https://zhuanlan.zhihu.com/p/76228394

部分3:题型升级

写在前面:这是RSA系列的学习文章,如果你真的想学习CTF中RSA类型的题目都有哪些特点的话,建议大家花时间细下心来好好看。请不要上来就甩我个CTF题,问我套哪个体型,怎么解。。。

很开心你看到了这里,也不知道你前面的数学基础看的怎么样了,如果你都看懂了,我就先给你竖个大拇指,很强。如果没看懂的话也没关系,我们可以这样去做RSA的题目:

我们可以把每种题型都进行积累,把每种题目的python脚本看做是一个工具,每当遇到相同的题型时,直接拿出python脚本来用就行。前提你要记得这种题型哦。不要觉得上一篇中的数学知识部分是参考其他博客写的,就同样觉得下面我写的和他博客写的一样:

https://willv.cn/2018/07/21/RSA-ATTACK/willv.cn/2018/07/21/RSA-ATTACK/

下面题型是他博客的超级扩展版,添加了很多特殊题型(鬼知道我经历了什么),有的题型百度不一定可以直接找到哦,还有就是有些解题脚本进行了大量的精简(也不知哪来的勇气哈哈)和增强了人性化阅读体验。放心这些题型的难度是逐渐加大的,绝对不会让你看了一眼就放弃的。

img

首先我们先看一下下面的目录,在大脑里形成一个基本的知识结构:

img

如果不看目录直接看下面的话会比较乱。(文末可能不定时更新新的题型,目录图片我就先不换了)

这个链接里面的是我分类整理的下面的题型,几乎每个题都包含对应的解题脚本,而且还包含了一些常用的RSA工具。所以这个链接可是个大礼包哈(ps:链接如果失效了的话,麻烦评论区提醒一下我及时更新)

链接: https://pan.baidu.com/s/10Byy4dSyQwK4qXx5XBH7LA 提取码: rzbh

为了使界面看起来整洁一些,我就不直接把每个题目的脚本放到下面了,部分题目的脚本我都整理到了github上面,每种题型都有链接,而且附件里面都有解题脚本(为你们操碎了心啊,就怕你们找不到解题脚本)

整个RSA系列的Word版本在文章最后可以下载,该Word版本制作百度网盘链接时才写到目录中的标题(13),后面再添加的题目就只在知乎或github上更新了,有需要的话可以自己更新这个Word版本。

2022更新了部分题目。 顺便吐槽一句,几年前写的那个RSA系列的Word版本排版确实不怎么样,建议你自己用markdown自己重新排版,以便后期的学习积累。文章我就不改了,毕竟都有年代感了 哈哈哈🤣

更新:后续更新的题目和之前的题目,现均已上传到github项目,有需要的可以自行下载:

https://github.com/Mr-Aur0ra/RSAgithub.com/Mr-Aur0ra/RSA

1.低加密指数分解攻击

在 RSA 中 e 也称为加密指数。由于 e 是可以随意选取的,选取小一点的 e 可以缩短加密时间(比如 e=2,e=3),但是选取不当的话,就会造成安全问题。下面就是e选取的太小导致存在的安全问题。

(1)e=2把密文c开平方求解

在RSA加密中,由于e只有2,相当于把明文m平方了而已,得到的c也比n小很多。尝试把c开根号看能否得到明文。Python自带的开根号求解的数并不打。我们可以使用gmpy2库来对大整数开根号。

题目: 01-西湖论剑rsa

1
2
3
4
已知:
e=2
c=9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529
求明文m?

解题:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#!/usr/bin/python 
#coding:utf-8 
#@Author:Mr.Aur0ra
 
import gmpy2  
import libnum  
c = 9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529  
m = gmpy2.isqrt(c)  
m = int(m)  
m_text = libnum.n2s(m)  
print(m_text)

(2)e=2 Rabin加密中的N可被分解

Rabin加密是RSA的衍生算法,可以百度或阅读:

Rabin_cryptosystemen.wikipedia.org/wiki/Rabin_cryptosystem

e=2是Rabin加密典型特征,但并不是所有的RSA在e=2时都是Rabin加密。

Rabin解密的Python实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def rabin_decrypt(c, p, q, e=2):  
    n = p * q  
    mp = pow(c, (p + 1) / 4, p)  
    mq = pow(c, (q + 1) / 4, q)  
    yp = gmpy2.invert(p, q)  
    yq = gmpy2.invert(q, p)  
    r = (yp * p * mq + yq * q * mp) % n  
    rr = n - r  
    s = (yp * p * mq - yq * q * mp) % n  
    ss = n - s  
    return (r, rr, s, ss)  

题目: 02-Jarvis OJ -Crypto-Hard RSA

img

确实如题目描述的一般,出题人做手脚了,按照之前做MediumRSA的步骤做完全做不出来,而且求d的时候就会报错找不到e的模反数:

1
ValueError: no invmod for given @a and @n 

所以要多积累一些题型,这里就是考察的e=2时,Rabin加密中的N可被分解。

首先通过openssl提取公钥的信息:

img

我们得到e=2,n=0xC2636….

然后分解n得到p和q:

img

然后就可以写Python脚本了:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/python 
#coding:utf-8 
 
import gmpy2  
import libnum  
 
e = 2  
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461  
p = 275127860351348928173285174381581152299  
q = 319576316814478949870590164193048041239  
c=int(open('./flag.enc','rb').read().encode('hex'),16)  
 
mp=pow(c,(p+1)/4,p)  
mq=pow(c,(q+1)/4,q)  
yp=gmpy2.invert(p,q)  
yq=gmpy2.invert(q,p)  
r=(yp*p*mq+yq*q*mp)%n  
rr=n-r  
s=(yp*p*mq-yq*q*mp)%n  
ss=n-s  
print libnum.n2s(r)  
print libnum.n2s(rr)  
print libnum.n2s(s)  
print libnum.n2s(ss)  

记住这是模板,以后有类似的题目直接拿来用就好,对了一般读取文件获得变量c的值都是这样表示的,这会使代码看上去更简洁。

(3)e=3 小明文攻击

适用情况:e较小,一般为3。

公钥e很小,明文m也不大的话,于是 $m^e=k*n+m$ 中的的k值很小甚至为0,爆破k或直接开三次方即可。

攻击原理:假设用户使用的密钥 e=3。考虑到加密关系满足: $$ C ≡ m^3 \ mod \ N $$

那么: $$ m^3 =C + k * N \ $$

$$ m = \sqrt[3]{C + k * N}\ $$

攻击者可以从小到大枚举 k,依次开三次根,直到开出整数为止。

题目: 03-Jarvis OJ-Crypto-Extremely RSA

img

因为e=3,很可能存在小名文攻击,于是直接写脚本进行爆破。

解题脚本:

https://github.com/Mr-Aur0ra/RSA/blob/master/(1)%E4%BD%8E%E5%8A%A0%E5%AF%86%E6%8C%87%E6%95%B0%E5%88%86%E8%A7%A3%E6%94%BB%E5%87%BB/03%20e%3D3%E5%B0%8F%E5%90%8D%E6%96%87%E6%94%BB%E5%87%BB/extremelyhardRSA/exp.py

我爆破了7分钟,爆破的时候别以为你电脑坏了或者这个脚本坏了哈。

img

啦啦啦,自己爆破,flag不给看。

2.Roll按行加密

顾名思义,这里的的加密是按行进行的。

题目: 04-实验吧—RSAROLL

img

不要总是觉得 密文C 就是一连串的字符串,密文C 也可以是分行的,记住不要把分行符删除让 密文C 变为一个字符串。应该按行进行解密。

n为920139713,e为19,手动把加密的部分另存为一份文件roll.txt。

img

解题脚本:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#!/usr/bin/python 
#coding:utf-8 
#@Author:Mr.Aur0ra
 
import gmpy2  
from Crypto.Util.number import long_to_bytes  
 
n = 920139713  
p = 49891  
q = 18443  
e = 19  
phi = (p-1)*(q-1)  
d = gmpy2.invert(e,phi)  
m = ""  
with open('roll.txt','r') as f:  
    for c in f.readlines():  
    m += long_to_bytes(pow(int(c), d, n))  
print m  

3.模不互素

适用情况:存在两个或更多模数 ,且gcd(N1,N2)!=1 也就是N1和N2不互质。

多个模数n共用质数,则可以很容易利用欧几里得算法求得他们的质因数之一gcd(N1,N2) ,然后这个最大公约数可用于分解模数分别得到对应的p和q,即可进行解密。实现参照本文欧几里得算法 部分和RSA解密部分。

题目: 05-存货1

N is 18674375108313094928585156581138941368570022222190945461284402673204018075354069827186085851309806592398721628845336840532779579197302984987661547245423180760958022898546496524249201679543421158842103496452861932183144343315925106154322066796612415616342291023962127055311307613898583850177922930685155351380500587263611591893137588708003711296496548004793832636078992866149115453883484010146248683416979269684197112659302912316105354447631916609587360103908746719586185593386794532066034112164661723748874045470225129298518385683561122623859924435600673501186244422907402943929464694448652074412105888867178867357727
e is 65537
message is 0x8BD7BF995BF9E16A0D04ADB49A2411C74FFDB0DB4F35DB3A79A1B44691947C9824085BC4CA5F7F4EFA3C8FD0BC3E870AA6D5E15307A63A2172C44C5903D35785B8D06B51651EE7106B070D5A6AABA089AB67609661265B74914C865F863DC1D2DC08CE0B026107A74EC3FDC62666B50110B9D15A243EAAD6F53646929A3369285404868E42DD0BBE92D956018E3C0B36EF5E9516E433228CFDD06D6E662EC0A9A31061EA11F61CA17EABF43D2D4977FC9D6FC53AB6DC01509401B8D9A46B59A9ADAA97D54CC50C27445E4C21B893510620EC3566AD6E8727FA147437B207505217E6F2DF009E2286C8354D281374D7802D08A2062FE48DBF135BBCAB120EBF84

N is 20071978783607427283823783012022286910630968751671103864055982304683197064862908267206049336732205051588820325894943126769930029619538705149178241710069113634567118672515743206769333625177879492557703359178528342489585156713623530654319500738508146831223487732824835005697932704427046675392714922683584376449203594641540794557871881581407228096642417744611261557101573050163285919971711214856243031354845945564837109657494523902296444463748723639109612438012590084771865377795409000586992732971594598355272609789079147061852664472115395344504822644651957496307894998467309347038349470471900776050769578152203349128951
e is 65537
message is 0x8C3CF3161AA3E37831030985C60566A7604688B73E5B1D3B36E72EF06ED4F71289EFE80E0D94BD755034E6C210F17DA85B9D0388F3AD104C68BC514A8EB1569A109EB5F266F7C5FA4DDFA638258949B43D4CF1406720CCD4CA11E74FDF8AEB35C56A79781C87157FC4213573329C5B0FF411F8A4F34580AA103DB9FD403C0D409FA11860A7C4595FDC49DC2CF94E5112B772E5DEC8F17E24B10A7FD7A95DCB87BE5E27C32FC931574A7847BC506A61EFE9DB3D3F612143845FE80D7B3EA548B886A67A29CBDB2775B1F91178B6DA763F1A6ECFF46592E4C7FFAAB6C9FEF29D9CB9E035A3D98ECFFB26BA2EEAA56D1CD096E6A2CF9A58086CAD7718DDA5CB0C1B

求明文m?

这里把明文字符串一分为二做了分别做了RSA加密,上面的message其实就是密文c。关键是加密时它们多个模数使用了相同的质数e,而且模数N1和N2不互素,所以可以进行模不互素攻击。

判断两个数是否互素的脚本:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/python 
#coding:utf-8 
#@Author:Mr.Aur0ra
 
def gcd(a,b):    #判断来两个数是否互素,辗转相除法 
    if(b==0):  
        return a  
    else:  
        return gcd(b,a%b)  

def main():  
    x = 17              #x,y的值根据需要修改即可 
    y = 65537  
    if gcd(x,y)==1:    #如果两个数的最大公约数是1,那么两数互素。 
        print str(x)+" "+str(y) + "两个数互素" 
    else:  
        print str(x)+" "+str(y) + "两个数不互素" 
if __name__=="__main__":  
    main()

img

题目是给出的文件rsa2.txt,为了方便Python直接读取文件为变量赋值,这里把无关的解释性东西删除掉,生成新的tmp.txt文件。

内容如下:

img

解题脚本:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/python  
#coding:utf-8  
#@Author:Mr.Aur0ra
  
import gmpy2  
from Crypto.Util.number import long_to_bytes  
  
lines = open('tmp.txt','r').readlines()  
  
c1 = int(lines[2],16)  
c2 = int(lines[6],16)  
n1 = int(lines[0])  
n2 = int(lines[4])  
  
p12 = gmpy2.gcd(n1, n2)  
assert (p12 != 1)  
q1 = n1 / p12  
q2 = n2 / p12  
e = 0x10001  
d1 = gmpy2.invert(e, (p12 - 1) * (q1 - 1))  
d2 = gmpy2.invert(e, (p12 - 1) * (q2 - 1))  
m1 = pow(c1, d1, n1)  
m2 = pow(c2, d2, n2)  
print long_to_bytes(m1)+long_to_bytes(m2)   

4.共模攻击

适用情况:明文m、模数n相同,公钥指数e、密文c不同,gcd(e1,e2)==1也就是e1和e2互质。

对同一明文的多次加密使用相同的模数和不同的公钥指数可能导致共模攻击。

题目: 06-Jarvis OJ -Crypto-very hard RSA

img

这个题目就比较有意思了,4096位的RSA加密,要不是这里存在共模攻击说不定你死活都解不开。哈哈哈,要是有量子计算机的话说不定能解开。

题目给出了两个flag.enc文件以及一个easyRSA.py的加密脚本。

通过分析加密脚本可知,该加密脚本首先会从flag.txt中读取字符串flag,然后对flag根据不同的e的值进行2次RSA加密,并分别将密文保存到了flag.enc1和flag.enc2中。

我们发现明文m、模数n相同,但是公钥指数e1和e2不同,而且e1与e2互素(上面给过判断2数是否互素的脚本),所以这就是典型的共模攻击。

img

img

解题脚本:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#!/usr/bin/python
#coding:utf-8
#@Author:Mr.Aur0ra

import gmpy2
from Crypto.Util.number import long_to_bytes

def egcd(a,b):
    if b==0:
        return a,1,0
    else:
        g,x,y=egcd(b,a%b)
        return g,y,x-a//b*y

e1 = 17
e2 = 65537
n = n1 = n2 = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
c1=int(open('./flag.enc1','rb').read().encode('hex'),16)  
c2=int(open('./flag.enc2','rb').read().encode('hex'),16)  

assert n1==n2

# s1=gmpy2.invert(e1,e2)
s1=egcd(e1,e2)[1]
s2=egcd(e1,e2)[2]

#此处判断s1和s2是否小于0,因为pow()函数里s1和s2不能为负,
if(s1<0):
    s1=-s1
    c1=gmpy2.invert(c1,n)#若s1为负,s1取正,c1取逆
if(s2<0):
    s2=-s2
    c2=gmpy2.invert(c2,n)

m=pow(c1,s1,n) * pow(c2,s2,n) %n
print(long_to_bytes(m))

其中,函数egcd是扩展欧几里得算法的一个实现,用于找到两个整数ab的最大公约数 (GCD),以及贝祖等式的系数xy(这些系数是满足等式ax + by = gcd(a, b)的整数)。

针对函数egcd 我们这里解释一下。

1
2
3
def egcd(a, b):
    if b == 0:
        return a, 1, 0

在函数的第一部分,它检查b是否为零。如果是,那么a0的最大公约数就是a,并且系数分别是10,满足等式a*1 + 0*0 = a。然后它返回这三个值。

1
2
    else:
        g, x, y = egcd(b, a % b)

如果b不是零,函数会递归调用自己,传入ba除以b的余数(a % b)。这是基于这样一个性质:ab的最大公约数与ba % b的最大公约数相同。递归调用最终会达到基本情况,即b为零。

1
        return g, y, x - a // b * y

递归调用返回后,函数会计算满足原始输入ab的贝祖等式的xy的新值。具体的计算方法如下:

  • g 是两个数的最大公约数,在递归中保持不变。
  • y 是原来的 x 值,即在递归过程中 a % b 的系数。
  • x - a // b * y 是根据贝祖等式计算出的新的 x 值,a // ba 除以 b 的商,x - a // b * y 就是新的 x 值,即原来的 y 值减去 a 除以 b 的商乘以原来的 x 值。

这个算法通过不断递归,直到b为零时结束,最终能找到最大公约数,并且计算出满足ax + by = gcd(a, b)的整数xy

上述脚本:

https://github.com/Mr-Aur0ra/RSA/blob/master/(4)%E5%85%B1%E6%A8%A1%E6%94%BB%E5%87%BB/veryhardRSA/exp0.py

简化版的脚本:

https://github.com/Mr-Aur0ra/RSA/blob/master/(4)%E5%85%B1%E6%A8%A1%E6%94%BB%E5%87%BB/veryhardRSA/exp.py

5.低解密指数攻击

在RSA中d也称为解密指数,当d比较小的时候,e也就显得特别大了。

适用情况:e过大或过小(一般e过大时使用)

在e过大或过小的情况下,可使用算法从e中快速推断出d的值,进而求出m。详细的算法原理可以阅读:

RSA 大礼包 | Tr0y’s Blog www.tr0y.wang/2017/11/06/CTFRSA/index.html#%E4%BD%8E%E8%A7%A3%E5%AF%86%E6%8C%87%E6%95%B0%E6%94%BB%E5%87%BB

题目: 07-存货2

1
2
3
4
n = 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597L
e = 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619L
c = 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192
求明文m?

首先需要需要下载工具rsa-wiener-attack :

1
git clone https://github.com/pablocelayes/rsa-wiener-attack

然后把exp.py放入这个目录中运行即可:

https://github.com/Mr-Aur0ra/RSA/blob/master/(5)%E4%BD%8E%E8%A7%A3%E5%AF%86%E6%8C%87%E6%95%B0%E6%94%BB%E5%87%BB/exp.py

img

6.根据公钥计算得到私钥

这种题型需要使用RsaCtfTools根据公钥生成私钥

题目: 08-存货3

题目只给出了两个文件(一个私钥文件和一个密文文件)

按照常规查看提取一下公钥文件,发现n特别大,无法直接分解为p和q,而且e也不存在是特殊值的可能,也不存在其他的攻击方法。

img

首先进入RsaCtfTools,接着执行下面的命令生成私钥。

img

接着把这些内容复制到新创建的文件pri.key中。

使用openssl通过私钥文件进行解密:

img

打开生成的文件txt即可得到flag。

7.分解n得到相同的几个p

这个题目牵扯到欧拉函数的一些知识,一会你就知道该补一补了,哈哈哈。

题目: 09-存货4

题目给出两个文件,一个文件是加密脚本encrypt.py,另一个是加密脚本输出的文件2.txt。

下面是我注释了的加密脚本:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import gmpy2
import random
from Crypto.Util.number import *
from flag import flag

def generate_key(1024):
    p = getPrime(1024)
    r = random.randint(2, 10)
    s = random.randint(r, 1024)
    while True:
        e = random.randint(3, p**r*(p-1))
        if gmpy2.gcd(e, p**s*(p-1)) == 1:
        	break
    pubkey = (long(e), long(p**r))   #返回e和p^r
    return pubkey

def crypt(msg, pubkey):
    e, n = pubkey             #e,n=p^r
    m = bytes_to_long(msg)    
    assert m < n - 1
    enc = pow(m, e, n)       
    return long_to_bytes(enc)

nbit = 1024
pubkey = generate_key(1024)
print 'pubkey =', pubkey  #输出e和p^r
msg = flag值   
enc = crypt(msg, pubkey)  

print 'enc =\n', enc.encode('base64')

下面是我当时做题时解题思路:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
RSA加密:
pow(enc,e,N)
RSA解密:
n==>p,q
phi=(p-1)*(q-1)  
d = gmpy2.invert(e,phi)
m=pow(enc,d,n)


本题常规解题思路:
enc已知  n已知  d?==> e已知 ,求phi ==>求p和q
看着加密脚本中多次出现p及p^r
本打算直接开用p=gmpy2.iroot(n,r)[0] 开多次方根求p进而求q 
//根据加密脚本逆运算 未果 开不出来 (╯▽╰)


另一种思路:
e太大 可使用算法从e中快速推断出d的值 可使用Wieners Attack进行解d
求出d可直接求m
但是这样也确实解不出来


好吧 正确解题思路
n==>分解n得到k个p  即n=p**k
phi=(p**k)-(p**k-1)     //由欧拉函数得
d = gmpy2.invert(e,phi)
m=pow(enc,d,n)

欧拉函数学习链接(这个数学知识不看还真不行):

浅谈欧拉函数_liuzibujian的博客-CSDN博客_欧拉函数:blog.csdn.net/liuzibujian/article/details/81086324

题目中幂使用的是r而不是k。

解题脚本:

https://github.com/Mr-Aur0ra/RSA/blob/master/(7)%E5%88%86%E8%A7%A3N%E5%BE%97%E5%88%B0%E7%9B%B8%E5%90%8C%E7%9A%84%E5%87%A0%E4%B8%AAp/exp.py

哈哈 好好看哈 当时我也是想了好久才做出来的这个题 不懂的可以随时找我问哈。

8.已知n,e,d求p,q

一看这个标题你就应该有个觉悟,n一定无法直接分解得到p和q。

题目: 10-存货5

题目给出了两个文件,一个是加密脚本chall.py,一个是加密后输出的内容output.txt。

分析一下加密脚本:

img

加密脚本真的是很简单啊,flag就是str(p+q)进行md5运算之后的得到的字符串,从output.txt中可以得到n,e,d。

现在的关键问题就是求出p和q来,google一把梭好像可以找到这种骚操作,当时线上比赛做这个题目的时候真的就是google找到的类似题目,百度啊,可不可以靠谱一点。

解题脚本:

https://github.com/Mr-Aur0ra/RSA/blob/master/(8)%E5%B7%B2%E7%9F%A5n%2Ce%2Cd%E6%B1%82p%2Cq/exp.py

9.私钥文件修复

题目: 11-Jarvis OJ-Crypto-God Like RSA

img

呵呵,这个题我认了,别的不会的题目起码都能看个大概,这个题绝了,只是知道解题脚本中对应的变量是谁了(哈哈哈),顺带把变量给你们注释了,反正我是写不出来。

这里面涉及到的东西太多了,我觉得绝不单单是Python脚本的问题,什么数学、什么算法的,必须给你安排的明明白白的。So,我把这题作为了一个模板,以后有类似的题目,直接掏出来用,莫非这真是"上帝之手"?

题目给出三个文件,一个是公钥文件pubkey.pem,一个是残损的私钥文件private.corrupted,还有一个是密文文件flag.enc。

首先使用openssl提取公钥信息:

img

然后将提取到的公钥信息填充到"恢复私钥的脚本fix.py"中,然后运行这个脚本。

https://github.com/Mr-Aur0ra/RSA/blob/master/(9)%E7%A7%81%E9%92%A5%E6%96%87%E4%BB%B6%E4%BF%AE%E5%A4%8D/godlikeRSA/fix.py

img

img

接着,将私钥文件修复脚本fix.py恢复出私钥来,存放到文件private.pem中。

这就结束了吗,没有,god不是白叫的。你会发现你根据私钥使用openssl直接解密密文文件解不开,而且直接根据p,q,d,c也无法直接求出m。这里又涉及到了RSA加密的填充模式。

这里使用的是PKCS1_OAEP填充模式,参考链接:www.cnblogs.com/lzl-sml/p/3501447.html

然后,接着运行下面的脚本即可得到flag。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/python
# coding=utf-8

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

with open('pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n
    e = key.e

print N
print e

with open('private.pem', 'r') as f:
    private = RSA.importKey(f)
    oaep = PKCS1_OAEP.new(private)

with open('flag.enc', 'r') as f:
    print oaep.decrypt(f.read())

img

刚才说无法根据私钥使用openssl解密密文文件,那是因为没有指定填充模式,openssl也可以指定模式。

首先,把生成的私钥保存为名为"private.pem"的私钥文件,接着执行命令进行解密。

img

10.低加密指数广播攻击

如果选取的加密指数较低,并且使用了相同的加密指数给一个接受者的群发送相同的信息,那么可以进行广播攻击得到明文。

适用范围:模数n、密文c不同,明文m、加密指数e相同。一般情况下,e=k (k是题目给出的n和c的组数)。

例如:下面的就是e=k=3

$$ \begin{aligned} C_1 ≡ m^e \ mod \ n_1 \\ C_2 ≡ m^e \ mod \ n_2 \\ C_3 ≡ m^e \ mod \ n_3 \end{aligned} $$
使用不同的模数n,相同的公钥指数e加密相同的信息。就会得到多个$m^e ≡ C_i \; mod \; n_i$,将$m^e$视为一个整体M,这就是典型的中国剩余定理适用情况。按照本文的中国剩余定理小节容易求得$m^e$的值,当e较小时直接开e方即可,可使用`gmpy2.iroot(M,e)`方法。(ps:都看到这里了,就一块细下心来把中国剩余定理了解一下吧)

题目: 12-Jarvis OJ-2018强网杯nextrsa-Level9

题目给出n1,n2,n3,c1,c2,c3,e。求明文m的值。

img

解题脚本1:

https://github.com/Mr-Aur0ra/RSA/blob/master/(10)%E4%BD%8E%E5%8A%A0%E5%AF%86%E6%8C%87%E6%95%B0%E5%B9%BF%E6%92%AD%E6%94%BB%E5%87%BB/2018%E5%BC%BA%E7%BD%91%E6%9D%AFnextrsa-Level9/exp1.py

解题脚本2:

https://github.com/Mr-Aur0ra/RSA/blob/master/(10)%E4%BD%8E%E5%8A%A0%E5%AF%86%E6%8C%87%E6%95%B0%E5%B9%BF%E6%92%AD%E6%94%BB%E5%87%BB/2018%E5%BC%BA%E7%BD%91%E6%9D%AFnextrsa-Level9/exp2.py

解题脚本2使用的是中国剩余定理解的题,代码确实简洁。

题目: 存货6

怕你觉得上面解出来的m是纯数字看着不舒服,特意给你找了个带flag的题型,还有就是这个e=9也不大呀。

题目给出n1,n2,n3,c1,c2,c3,e。求明文m的值。

img

解题脚本:

https://github.com/Mr-Aur0ra/RSA/blob/master/(10)%E4%BD%8E%E5%8A%A0%E5%AF%86%E6%8C%87%E6%95%B0%E5%B9%BF%E6%92%AD%E6%94%BB%E5%87%BB/%E5%AD%98%E8%B4%A76/exp.py

img

题目: 存货6-1(新增)

题目给出n1,n2,n3,c1,c2,c3求明文m的值。注意这次没有给出e的值。

1
2
3
4
5
6
n1=0x7d9ec519935fecf80eef98e1e500d1da3f7bdfd5b94375243c9e8cba36bf4cbd5a3cacd9d981e3710172deaf9158628b13e28eafc835bad12123ce0abd66540836e6267b50294ee8bfb7dbaf7ec5c7d593303a3329be749f6bd8226af47ddd0fe2475c4ad0560156e1efa1f91496fa279d18e12ad10bea5f72f18bcf851c22d9a9bac8f70b5a0f227dfa49019d26f673470cd1de0d0bbe0df8c57ca90b1c271733e21bd9cd28f3ae2e7fa25eacf98201fec6fdd585ae58db16f543f31cef0db2ae71e3f184a96d662604bed370ca8daede9dbdfdb39e682bc72d37c31c7d64a4e41710c8ff170075d0e7f8ec9d5a122cad33a11876e7c3def7edf6bd16b1b24aff3d677cdb421e1cd9ade2e137034ae0541631139d55d1641f5f56614feec17221aafe9aefcacd0856f8d114813e73a6e70330d4e2bba5eef984bc824fbcd987993438cc7b6da58c090be809c5b378f40459388c32756770982d0964ae9914a81a43596f306e4cae443c5eecbff4e4af521bdf20dc0c78441030eadc21257c9c7daca9de65f84678566b217e8ea0e1bffb3cd86d9056eb0a814ac4bcf23ddc51a134484d3491689f64611e83a3b35e54811a53ad8f391363f9799d5772f82bcc73ddc30939b3de2a374fa1c451ee64fa50c9a00e9dc8ed6cc787f97918908089853405c80808321202162b32edeb0935c4a1c3b15d6e7190440f445dfa1be269L
n2=0x6b794f7168ab67262328f0f90618e274c8a3f8ba2bac2c1bd2147d894150e1a29a7e92ef4193df5c95331106ac09ce65e90b6e90fc2ce13bf040a92425a97bd0661e5d8b5c5243f4ebc519d7179d05bcccb8e9746ed1281cf3e7782322dd092c515cf1ecbfb4e1f338e3f11760a0011cd102a2b1aedda70ff126ce922b4bd93a84ea09c4ec9785db18be8db02cd2885fc6e3b87e4993bfcc4973cd77ce7fbbe139b0c730138550c7fa363c0807daeb8cac020ce8acbc20a8786ff4b5bccd2a3479fa714096cdd48b29d7f8a522c1aa175b1c39c5de2dec099f9fcb2e2b1ba36f34c5b5cece9cb37e3ac5659373c15ecbc59ba5a89c90f9d19b81b99b3642d6b58d4d3a639239a9c817b4cd714eefd825caa75d083ee2aa19a20842d5b0aa71f9a95c7f5bd35d0df1a3e300a90c92183735e679e5c1be2b96d45dcf22965b914370efc890620f6633bbf4489249071c0f254b641a161c51d4f84c84b5be3eb514ab4bb52d2a2c37a66d9a6370beff5286dbaae080f809a2681d6826fc80399c4332313cab8f9a9e4553bf2f2d2ea09f4c47c472177b1c3bff4c2e4b8b30c88041e6ea6863cb5edc2215470f8ccba6a528004cf094d5a07d9b99b4730358e09cacec353a94fafad6aafef22e8f55952fba96d0d7f63cffcf672ea7550619b140dd500ec1b419a99704c91430afcc2f6f208a0e5544eab606d4884f2c96c17dc609L
n3=0xa023e410eebf1ab19c0022e5fbebbcd40787bbc886980bcbc777f25a0c9bc951da654268d5136b0cc957093d62bfd90086d4545fe02ba4a51707e5231831fc0d60070b5eccb992b321d021dea8d12118937ae7a4f2ad068ed7764fe7ae5057552308df4c64899dff6047e4ef3a74c21403f5783b19ccf6b5bdfa66ded2ada5a8708ab9edd14db3120de55fe94710834dd9015082b2269688b09d22b4d54f5a6f7606bcf07a9c2693bb96914b5faca5cf6e2964ff920f8565ecbf4d7d2458c19908607accdf881023153cfb27fa054bc6b0877e31c88fa1017d2354e58477fe8e68bc1b7a52d61150e3e447d8eaef0bcc0f0b9443b38e334bd2c2cf0546ef14c201be99097ae3a4aa4ba8d519fd77d51a3ebeb944b096cb0665dd3ccbf15a6ff0ea3faeb9163df708ad8b95e5862afb5137d0b945fca589590affd406f24888a2c86f5d4fa148573a7b7cafb9262b06b41cffeef2282782efa131b7f504e064f1904a6c7fbbf97149250719649b139550d6eb1853ac4564dffc76f807de3f0b0a8b0b58b4dc6edf1397efccc9ae08a2cae403269f0c683d3b5559c3eae03d0a910dcc9ce12ddbdca396d4c8c946ced50cbcc33d639f6d788bc98257bb6f97655f6d03cf721aa5b6d2964bfd141cdcd1b8087e04a701c156a754c659c0a19393790cd8dd05739eb6e87c23d90679538f819ab1190a381be8d20cc524d67c40cf89L
c1=0x61ce20185c2f3bb10cd0af2aa5ea62cfc7213896e15a511f6516518c6a8a644a823bb45fcd97ec6297aef54cc8a1ecf5cd7f37b75359b0052b127b4373dba37b7afae4f5a872665e0cadfcff62deba6895a0ae160da052f6fef96a1a87f2e8b9643ee54381f97cf81c38785d81e714427f1e2dd882e0403955605a44a9b85e2d8e94663c95735987fde7c60cbd3e8bd2a485bd2c32776fb2d8541709478d94a4173d5056c0b6c8a4e41465be92a317cebad1dba92b12f22df081039d08025372155bffeaea59a9a6a8a96818f7b47d7fac53dea14b763fc1983ac84e67f54c2d17fcbbd64626036e7c237e460888121af71a355da7641e4d93579c405b3778951a87d7716b9ee348e44ebb7bcc82ac75191ebae109cb885e84858bc0edfd8064e2a4cd7baa4b8d1636b404aaf2a86f555152c133e06439dc125f3dcaaff33cd5ac2a0923192b5843a8fde1bf3198ba87978fd54e2f429c93bfbd9e58372db49aaa558304b322e85c1dc64c608a9fb902956921e1bb3cc0f7ded7cd469a263d9c60950d1e132199b07f4143d47d63234ff4b24b84b866b19e3070591fdd420efe245f24aef5f43c6269cfa4ea7bc40595124f91869b0236a3de679bcfc945019a7385383d18ab1ce1e585371af20ebe6f028361c6c398811aace99f2d1cf402c89190bffb34dd388f8b926a8b8b0f146d4e1612561fad83206b94a71894da4da4L
c2=0x18ec6c682f53a49b6974a96dbb1ac33c6d55011e28acf6cc27adb1dca8db33620ed9cee7b720fe2475eb0ab7ba2ea2b7648794e1c06a0732e2737978ccafabc219259b984065caad51abe73e8fbc20889b5ac64dc75b6adea46122ba589b6c13838b154c2f78ef5782f2a284a51efa0724bc94a4d2c8fd1dadf0d3b23ef21c6144784375b808e3a3eb32059d99a3c359db6e38608196909c2fbc1211aad8fc6215aea1ad422c75dd7842b30c802849ff077a4661dc315c735591bf3e4c4004ed3f8098d4d0afa51192814a0bac7450b9f12a40b218b263c022d2868cce270510023904e0301a8f0c0cd1501c64e1cbd84905b5e801b880067468d7b68e9270b29d0b5657b6d7605ffbbbba7d5e54ac183b45cf72429ee80f98a9f2a4ef6284a4548c00e7b145b998bcdb35d73d1d61e0fc1378554eef7264ce5fc249c5a685d4905d5c9251108013ea5e62f1ee1742699bc991543624640927c1248f55f342f57746b3783659a8a0078c5b8fe14304238d02dc675416fbec6d973418979482cbeba08b81d23f49fee7abeb67bf54ed1726fe4375625225bdb2e73d4b8be5f8d50bf2c7160cd5ec93fa84cf70d28fa848a5df72c41d778b5ba02abc3845a080299527a151ef73d4ecd9f803b6d358f8b3543becf6ad50b3d968c2f3351afa97e7e8e04aa7f73a81a63ecb78856f34bcaf8f7d5c9d025a9a30352de51c74cfebc1L
c3=0x9fc32050f50e191c99070816ddb3dccd0974bf0197c1c1cd067218b5e9c0c8aac90c40245f6e2dff17bf13387bc3bc5ce9eec7bda955feac0b20ef3035a4f847ee2e207cf35002bf33c408f861eb960ed7180ee743b62e84594c237b9e7828225b69b26864ba2127fb208e57d8d16ba49ff2c5c9d294da545290ce8e007392010d6cf1c4b959786341f5d1f044ae6ff36b146d11eba9387e70ac876516d7f96fc5769cb93d46daf91b5d241ac619e3a13b4c6d6b8684cf80690838efa05e751388f3ea255672c181dd8bdcc637552e49ec7e07074b11c52ddfa9eacc4e6db0ed34bf2cbca2621bf32238cea1eb834989858bfb82554cabc60e347ce859a652e7b5eb4e37203324804a3dd66b6aed3a6a1137257fb89bf59d97a7c5fa02440b2f88bd7a4b7986e8ae4e421610adc98ece4b3ab0b66582a1d11527d60196da5c4b63cff7a875adae448e886aa5af4a27d3aac2625914c696da18fae2886710fbf23031327c94a041609da2f8588e0f72ed5355d286906a8e8f28c693e44d53e8382da6d64e9f3237ea71b06b210f3ec1cdf40c383540214dc65d1c3acfb6918c25997a4ae19397dfbc54c56bd4f26cd07187733ed91d1203bd5abadf1667e572d3fef9cc0d3ecea8fc6a3804cd9012aa4f89a1ac3613704b6f2dd566e6d6b4ae797365ca69f966158dc0d62e767bbdabc5fad52d868cec33bec3e2623e3f72d300L

解题的话,可以先尝试e=3,但是没解出flag。

此时就需要爆破e的值,理论上讲,e的值不可能特别大。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#!/usr/bin/python
#coding:utf-8

import gmpy2
import time
from Crypto.Util.number import long_to_bytes

def CRT(items):
    N = reduce(lambda x, y: x * y, (i[1] for i in items))
    result = 0
    for a, n in items:
        m = N / n
        d, r, s = gmpy2.gcdext(n, m)
        if d != 1: raise Exception("Input not pairwise co-prime")
        result += a * s * m
    return result % N, N

# 读入 e, n, c
# e可以随意取大点的值,本题e很小就可以得到flag
# 所以就做了[1,100)之间的循环,你也可以取[1,65537)
# 注意e不可以为0
for e in range(1,100):
    print "e的值为:"+ str(e)
    n = [512485683379248627994222054928198152386318092644738180381554991475217377796405434854335056277622930547863024818767444598344410114539577997600760963632431418175495524212085227342236317690282303579871792604136978688849603906940046044534323144974053231416767418730793910263975433053461456721073431678088001273173284389468140530700307609776388997865772839512574327150259671379170026613490736333987026453811040095250243133527257805577313715212812958664333627735599163789040400505627822241159031720604542905728505522971011717666817345682281260608494735673864681250466412331593958894961131488445737536608944832487664399026112772867107087511943463538583457683579491879673641747689921593966314187930608676512863996255918764250565309330970516261788076369420228272626436321005067854817412234934831868982242339922158712560874614372107706079567173989259456857608363761805364620698478353230772690734471510134342068390134954906482464260622773680007027270240927217704723404590378763918240935998163799908756686555902792898116295063931404222813003278812035337906714468974195245694839181751219111401835806870499348487733491946647101567421316709805465910092315582508830042739317183125257526385847182925549204858279744905286118241383712008804714524959337L,438455129905663326510217996453387937818265147158140912081178396743766705601124940665790932344481155400002301338515524231925714648114810219744906401692738457749458278151114387635536422652494466839733126044697474681703619367177810933835403243322075569780826658879869369073520408208881042059373788457691248620041363036256053901332732025192473513880966852569324181325637113811528881626784815652329195878816996045400785780863488097039442217416113657576307367610903230358079374901165790819244990843302685212147937153498655927622235924092330572523305629875231791404715651959183795358420179448279473775095313467638399477146757229070378632818776284346057352441718601252186467300865188809011881157659965626389442897514625454445586427853274594179142076630186758618951856854369899214565996874415367745532324528369058533990486031307221691495860169756892482038169396339092890711719474815240465100920233523155578622866773601776749758630566368939795717596554340628161945827353855540096690670439478394005656412231410467731001387527736194221724672706430756234754940822630104576940365000003870106656376805817265622018226286424874849207544941467791006032204338343828474870841718078157179104550873232976483975616382329979719134670083763882419066043745801L,653315011935722683633899239971517941619349225695222088452194012082260326313201677835660945384275485145096065789222102748796071121711741203243670414338927148826702659529852592126552866279897276172924949211665542075745606262930965969289469269385301071552633342358778736510473222632405762525274716680890233538863243345692088160380126514797731426532170556602864402270537622591136334016473986479380886333915960074299602274671326676436465721122648878937456119562883070126768308182048342065999178801029549307888585963509968312202636585782857004099050511100978623830631609264692400949699741726049139455818499378351117228903547409337889830316549423121620369033893579169220786264356102811922557390482838303383978852873130668081323828348612838822334030273451283626768826170742066900163715681536233509267601661429117260438377187730730034557272078251624627747748768164927882629463582925338671073691854448141606348848569385399779605558939845122283956988301029392645516848789335435999529269974727866199089608234196347034929836500632922152689344010813924445789115346540480520677473336451000106471051448922245859528982264117288034012176740729039917085047680314285043383807860886975328022081757231586996665711685759320301324337611554984459865268735881L]
    c = [399010311121182943332309121114907411971005715655147896283369909476319473320142906797174433944197736682155228613837419252518602898442959789436466058872795204684719139465569382123104599556182756881512146887835901762524124952169928552088784468883025949156497960737022461897943895387142452146896439885966442758514883551398180828108448038344602784548819521285900170439253491829051725879130937677485144773782521693714498513283707353421186155236088813956052327129437629781022749262691591903818002745150640452705864306967771312436295009214557351255495381997105698411916814556536780279272815368148780203872635230392276897038561029968066298918693863362128071013792150689063207647118900886716782643660458005277167365424238794827411411025963471035659129582133847548362840024006275626160743108434783501160707247644258474071101048981371157536016841319724905482389910167999437472868380967163152370362239187926424917469145689563508506504834309075169219014250408812927354102861156064165623878898346687465296913386550602835135798632531680549909595951180893284332783411347133761580603793979970749905619763806933044555810234621000823825742812412350701424826572434253481700878717477193917096525871323813383655618357256914271825408980286254757657357995428L,101679127888134323725416317100411720344826429929601328830868924222029861957243313130888629593943146715504722159868347829741654002116628427240384129016395510386411083515704260057559942172196997688477611541379008440315525316323378006679145918547369295922501238705223385759650387660754808143678545678441899153341228089669541301309154208551196055571665128996579361850190451835989886402761079553669245333442973834901750807859208019800931394134333884538829836559098119575423601453695242340711462656301014871141326221684472998453644674700574750611088468850059788694559149584998461969466200699430608777201007485329143552935271042350737207244773742158476032266489948431865071820745289852064304693461790424825326755826807490144386639668870704391714183649200687936642883542238703444082716114345750431099371235795680332396127429200259296001455589068681502453198015842837674520962582234472173147801727327037498300172851794008303961739725055356570920954996102811127534547751755606626494829801001521950432984882492261314920320540574998939744987184277444447882158088666360204231746334686511237233889476914338775126672202451100099836815620060273259496385106193137702971000898173496712086672858552829708543458356018009228876954328125176399940266486721L,651772959894870840060102038649718098624287975188831353563157895211464117397354692694376307356217104809294356436693017232734414966073515715756220710870282877518135284377272355100684336075930019293411882322079560643529612235963044721844611100622244718471536231327233428643853698908853467079122167042327498402688154226515102711290801517703393081695874935492231825031203363534068625173045722223997882474274748963849884733327551858142505525087203555003800843026732158720251038619039816119396261158977354910621299476774407868591073821412845260844364621190213250892034844436195591940833748984393882432317958987741676458005543046381494570625865553127054568200356516586531928435872450053173532081370638426771798393956893679060639774311468035158208104718372121197462041463810903719442698671063036585602918806277123795224127059383077780909672382158306786154051753779666264201462236110658367733033404001181979613839663302066116787817088037203018689704591027311041019288748853090272606431612223021609997420842480765936764638248845753574667339942415336226419163132243409610852241935411558278958551060715644054460732821982619702657854190398281165478586242902687379449741828444267651003458264204219235283795584568034971205824995190606412406743814912L]
    data = zip(c, n)
    x, n = CRT(data)
    m = gmpy2.iroot(gmpy2.mpz(x), e)[0].digits()
    print long_to_bytes(m)

注:exp脚本中的n为数组形式表示的多个n的值,中间用逗号隔开。(建议先将n从十六进制转为十进制)。

脚本执行结果:

img

11.已知dp,dq求解m

其中关系式如下:

1
2
dp=d%(p-1)
dq=d%(q-1)

解题脚本:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#!/usr/bin/python  
#coding:utf-8  
  
import gmpy2  
from Crypto.Util.number import long_to_bytes  
  
c = xxx  
p = xxx  
q = xxx  
dp = xxx  
dq = xxx   
  
InvQ=gmpy2.invert(q,p)  
mp=pow(c,dp,p)  
mq=pow(c,dq,q)  
m=(((mp-mq)*InvQ)%p)*q+mq  
  
print long_to_bytes(m)  

这个题型实在没找到对应的题目,就先只记录一下这种方法吧,说不定以后会遇到。

12.CopperSmith定理攻击

建议先跳过(12)先看后面的(13)(14)…,等时间充裕的时候再回来好好研究这部分。(12)这部分我写的不是很详细,建议看看后去网上找些其他相关的资料进行学习。

之前已经成功安装了sage,现在我们再来介绍一个工具包“RSA-and-LLL-attacks”,具体的功能在这个目录中的ppt和pdf有详细介绍。下载链接:

https://github.com/mimoo/RSA-and-LLL-attacks

(1)Stereotyped messages Attack

适用情况:若e较小,并且已知m的高位,则可通过此方法求出完整的m。

什么叫m的高位呢,很简单,比如题目给你m=0x65c46754a7776c8b88867e000000000000000000 前面的部分就是高位,后面的0就是低位,0只是占位的作用并不是真正m的值。

题目: 13-2019强网杯copperstudy—level1

题目给出如下加密脚本参数:

1
2
3
4
5
n=0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953L   
e=3  
m=random.getrandbits(512)   
c=pow(m,e,n)=0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c451562c816e2303990834c94e580bf0cbd1L  
((m>>72)<<72)=0x9e67d3a220a3dcf6fc4742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000L 

要求出完整的m的值。

很明显e较小,并且已知了m的高位,我们通过CopperSmith算法的Stereotyped messages Attack获得完整的m。sage解题脚本(交互式输入):

https://github.com/Mr-Aur0ra/RSA/blob/master/(12)coppersmith%E7%AE%97%E6%B3%95/2019%E5%BC%BA%E7%BD%91%E6%9D%AFcopperstudy---level1/exp.sage

sage是基于python开发,所以python的语法几乎对它完全适用,但是sage自己还开发出了很多语法格式和数学公式,学习难度还是不低的,所以我把这些脚本都当做了工具,拿来直接用,自己写出来似乎能力还不够,因为不光要学语法,关键是这里面的数学算法知识。

使用方法:通过终端进入上面说的RSA-and-LLL-attacks工具包目录下,然后运行sage。

复制脚本内容到终端中然后回车回车运行(不知为何无法直接运行脚本,很是不解,可能是我的打开方式不对,你要是会的话,麻烦一定和我说一声,就当是带带我吧)

img

img

ps:感谢大佬@啦啦啦 提供的方法 sage下直接运行load(“exp.sage”)就可以解题运行,不用粘贴脚本内容了。

(2)Partial Key Exposure Attack

适用情况:若e较小,已知d的低位,则可通过此方法求出完整的d。

Partial Key Exposure Attack中文名叫”部分私钥暴露攻击”。

题目: 13-2019强网杯copperstudy—level3

题目给出如下加密脚本参数:

1
2
3
4
5
6
n=0x51fb3416aa0d71a430157d7c9853602a758e15462e7c08827b04cd3220c427bbb8199ed4f5393dae43f013b68732a685defc17497f0912c886fa780dfacdfbb1461197d95a92a7a74ade874127a61411e14a901382ed3fb9d62c040c0dbaa374b5a4df06481a26da3fca271429ff10a4fc973b1c82553e3c1dd4f2f37dc24b3bL    
e=3  
m=random.getrandbits(512)  
c=pow(m,e,n)=0x3d7e16fd8b0b1afdb4e12594c3d8590f1175800ef07bb275d7a8ad983d0d5d5fd5c6f81efa40f5d10c48bb200f805e679d633ee584748e5feef003e0921dea736ba91eef72f3d591d3a54cd59fd36f61140fdd3fb2e2c028b684e50cbeae4a1f386f6ab35359d46a29996c0f7d9a4a189f1096150496746f064c3cc41cf111b0L  
d=invmod(e,(p-1)*(q-1))  
d&((1<<512)-1)=0x17c4b18f1290b6a0886eaa7bf426485a3994c5b71186fe84d5138e18de7e060db57f9580381a917fdfd171bfd159825a7d1e2800e2774f5e4449d17e6723749bL  

要求出完整的d。

sage解题脚本:

https://github.com/Mr-Aur0ra/RSA/blob/master/(12)coppersmith%E7%AE%97%E6%B3%95/2019%E5%BC%BA%E7%BD%91%E6%9D%AFcopperstudy---level3/exp.sage

脚本注释:d0代表已知的d的较低位,kbits是已知的d0的位数。

(3)Factoring with high bits known Attack

题目: 13-2019强网杯copperstudy—level2

题目给出如下加密脚本参数:

1
2
3
4
5
n=0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578dL
e=65537
m=random.getrandbits(512)
c=pow(m,e,n)=0x1922e7151c779d6bb554cba6a05858415e74739c36df0bcf169e49ef0e566a4353c51a306036970005f2321d1d104f91a673f40944e830619ed683d8f84eaf26e7a93c4abe1dbd7ca3babf3f4959def0e3d87f7818d54633a790fc74e9fed3c5b5456c21e3f425240f6217b0b14516cb59aa0ce74b83ca17d8cc4a0fbc829fb8L
((p>>128)<<128)=0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000L

要求完整的p。

sage解题脚本:

https://github.com/Mr-Aur0ra/RSA/blob/master/(12)coppersmith%E7%AE%97%E6%B3%95/2019%E5%BC%BA%E7%BD%91%E6%9D%AFcopperstudy---level2/exp.sage

13.已知e,n,dp,c求m

题目内容如下:

img

解题脚本:

https://github.com/Mr-Aur0ra/RSA/blob/master/(13)%E5%B7%B2%E7%9F%A5%E5%B7%B2%E7%9F%A5e%2Cn%2Cdp%2Cc%E6%B1%82m/exp.py

这个题目具体的讲解可以参考这个的详解:

RSA之拒绝套路(1):www.jianshu.com/p/74270dc7a14b

14.N分解出多个不同的因子

适用情况:题目给出的模数N可直接分解,但是分解之后得到了多个不同的因子

题目: 15-山东省大学生爱好者线上赛-上午RSA

题目给出一个文件里面的内容如下:

1
2
3
4
n= 544187306850902797629107353619267427694837163600853983242783
e= 39293
c= 439254895818320413408827022398053685867343267971712332011972
m=???

很明显n不大,可直接使用factordb进行分解。

img

分解得到了3个因子,其实当时做这题时我也是一脸懵的,从没遇到过,试了n种方法,最后推到了这个方法。

解题脚本如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#!/usr/bin/python
#coding:utf-8

import gmpy2
from Crypto.Util.number import long_to_bytes

n= 544187306850902797629107353619267427694837163600853983242783
e= 39293
c= 439254895818320413408827022398053685867343267971712332011972
p1 = 67724172605733871
p2 = 11571390939636959887
p3 = 694415063702720454699679
phi = (p1-1)*(p2-1)*(p3-1)  
d = gmpy2.invert(e, phi)  
m = pow(c, d, n)  
print long_to_bytes(m) 

15.LSB Oracle Attack

适用情况:可以通过选择输入的密文进而泄露最低位解题。

该攻击方式详细请参考该文章:

https://introspelliam.github.io/2018/03/27/crypto/RSA-Least-Significant-Bit-Oracle-Attack/

题目: 14-SUCTF-RSA

img

img

正式进入rsa解题之前会让你提供一个字符串str,只有md5(str+给定的值salt) == 给定的部分哈希值part_hash,才能进入正式的题目。

然后,通过输入D,服务端会帮你解给出的给出的密文,但只会返回这个数是奇数(odd)还是偶数(even),通过G选项可以测试你输入的m是否正确,如果正确就会进入下1轮的

解题(3轮都是相同的原理,只是给出数c,n不同)(必须使用交互式解题)

解题脚本:

https://github.com/Mr-Aur0ra/RSA/blob/master/(15)LSB%20Oracle%20Attack/exp.py

本题摘自Nu1L战队提供的wp,膜,膜,膜

16.PKCS1_OAEP模式的RSA

西湖论剑2020–BrokenSystems。

题目给出三个文件,一个加密脚本BrokenSystems.py,一个密文文件message,一个RSA公钥文件public.key。

img

通过openssl查看,可以看到该公钥文件的e特别大,此时便存在rsa-wiener-attack攻击,通过此可以求出d。

img

通过rsa-wiener-attack求解d:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic

def wiener_hack(e, n):
    # firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    for (k, d) in convergents:
        if k != 0 and (e * d - 1) % k == 0:
            phi = (e * d - 1) // k
            s = n - phi + 1
            discr = s * s - 4 * n
            if (discr >= 0):
                t = Arithmetic.is_perfect_square(discr)
                if t != -1 and (s + t) % 2 == 0:
                    print("First: Hacked d.")
                    return d
    return False
n = 0xC20745223FF5B94B2CD8412166F7288A21F2187E1A421453918CAB03C80253451233EB1BDC2363744228AA8694A8C2CBC833F80DDF40831A68901B230B83F3F0FED4B72D0B942B5E95DEDAC8DCC0047A2AFB90C81ED72D3AD49B72FC8BD0D3167DDDAA6AB5167C058DF36AF190B216085BBD9D621F9BD23A093E4E3D9CC387B6274F2C339C88E1B2D908ACB33F4E20E647ABEE0714A3CCE4646E896294B78103DCC9A4DB7ED681164C6E6CC7FD33476E174A6C707037B250491365F9F0EB76AEABA07DB2F662D88048AF98C88C76C6710DB9658D49FCA0CAF1F5CD99DC07F188432B48F85571168AD10FC824B7B682BAD6CAA5D12FF6F04C92786B738AB19BB7
e = 0x1d2d2f1f173f81cf368fec06d40d47fd92f8615c12eec14168f288427952b8cf5a538f70ba3341b6a173ae80375a96b0d384d9722b19149f78947375e0a33df5e693edabd5e4d44cffa9e525ea014f3fa499b5f7b29b219d90b88da55aae3a08637338d7bed056e3aec575be56bbde534b355a2e7757db7aeca96e78d67f21530b7c3ec24ac61f9b474ab283220dd9545135d065a724ce2f8f44e32e460eef5f9958009c58af595193d77e72c25f0cb01505b993c135328b11b500dcabc955c9177f839dd043586e25a31335e7d5437dc9e6cd6d4ebecb2937e16026c2792e1745f44eed5411beaab55ed0905db9198cbd431111be87462f46369e31d1a4613f

message = open('./message', 'r')
secret = message.read()
d = wiener_hack(e, n)

此时,我们便可以求出d。已知d,我们便可以求出p和q。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def getpq(n,e,d):
    p = 1
    q = 1
    while p==1 and q==1:
        k = d * e - 1
        g = random.randint ( 0 , n )
        while p==1 and q==1 and k % 2 == 0:
            k /= 2
            y = pow(g,k,n)
            if y!=1 and gcd(y-1,n)>1:
                p = gcd(y-1,n)
                q = n/p
    return p,q

因为加密脚本采用了PKCS1_OAEP模式下的RSA加密,所以我们需要通过手动构造私钥进而才可以去解密密文。采用原始的pow(c,d,n)是无法正确的解密密文的。

因此,我们需要先采用PKCS1_OAEP模式构造私钥,然后利用这个私钥来解密密文文件。

1
2
3
4
5
privkey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
key = PKCS1_OAEP.new(privkey)  

m = key.decrypt(secret)
print m

完整的exp如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#rsa-wiener-attack/exp1.py
#!/usr/bin/python
#coding:utf-8

import gmpy2
import random
from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import long_to_bytes 
 
def gcd(a, b):
   if a < b:
     a, b = b, a
   while b != 0:
     temp = a % b
     a = b
     b = temp
   return a
 
def getpq(n,e,d):
    p = 1
    q = 1
    while p==1 and q==1:
        k = d * e - 1
        g = random.randint ( 0 , n )
        while p==1 and q==1 and k % 2 == 0:
            k /= 2
            y = pow(g,k,n)
            if y!=1 and gcd(y-1,n)>1:
                p = gcd(y-1,n)
                q = n/p
    return p,q


def wiener_hack(e, n):
    # firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    for (k, d) in convergents:
        if k != 0 and (e * d - 1) % k == 0:
            phi = (e * d - 1) // k
            s = n - phi + 1
            discr = s * s - 4 * n
            if (discr >= 0):
                t = Arithmetic.is_perfect_square(discr)
                if t != -1 and (s + t) % 2 == 0:
                    print("First: Hacked d.")
                    return d
    return False
def main():
    n = 0xC20745223FF5B94B2CD8412166F7288A21F2187E1A421453918CAB03C80253451233EB1BDC2363744228AA8694A8C2CBC833F80DDF40831A68901B230B83F3F0FED4B72D0B942B5E95DEDAC8DCC0047A2AFB90C81ED72D3AD49B72FC8BD0D3167DDDAA6AB5167C058DF36AF190B216085BBD9D621F9BD23A093E4E3D9CC387B6274F2C339C88E1B2D908ACB33F4E20E647ABEE0714A3CCE4646E896294B78103DCC9A4DB7ED681164C6E6CC7FD33476E174A6C707037B250491365F9F0EB76AEABA07DB2F662D88048AF98C88C76C6710DB9658D49FCA0CAF1F5CD99DC07F188432B48F85571168AD10FC824B7B682BAD6CAA5D12FF6F04C92786B738AB19BB7
    e = 0x1d2d2f1f173f81cf368fec06d40d47fd92f8615c12eec14168f288427952b8cf5a538f70ba3341b6a173ae80375a96b0d384d9722b19149f78947375e0a33df5e693edabd5e4d44cffa9e525ea014f3fa499b5f7b29b219d90b88da55aae3a08637338d7bed056e3aec575be56bbde534b355a2e7757db7aeca96e78d67f21530b7c3ec24ac61f9b474ab283220dd9545135d065a724ce2f8f44e32e460eef5f9958009c58af595193d77e72c25f0cb01505b993c135328b11b500dcabc955c9177f839dd043586e25a31335e7d5437dc9e6cd6d4ebecb2937e16026c2792e1745f44eed5411beaab55ed0905db9198cbd431111be87462f46369e31d1a4613f
    message = open('./message', 'r')
    secret = message.read()
    d = wiener_hack(e, n)
    p,q = getpq(n,e,d)
    #print p
    #print q
    privkey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
    key = PKCS1_OAEP.new(privkey)  

    m = key.decrypt(secret)
    print m

if __name__=="__main__":
    main()

注意,该脚本需要rsa-wiener-attack工具包的目录中执行,还需提前将密文文件message一同放到该目录下。

解题脚本如下:

https://github.com/Mr-Aur0ra/RSA/blob/master/(16)PKCS1_OAEP%E6%A8%A1%E5%BC%8F%E7%9A%84RSA/rsa-wiener-attack/exp1.py

img

以上是我当时做的步骤。

大佬们其实只要几行代码就可以解决,膜膜膜。

以下是ChaMd5团队给出的本题WriteUp(我进行了部分修改,便于理解):

维纳攻击,公钥文件中获取到e很大,利用维纳攻击可以拿到d。

维纳攻击github.com/pablocelayes/rsa-wiener-attack

然后利用e、d、n获取p、q,生成私钥文件:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#exp2.py
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse, long_to_bytes

e = 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583
d = 1779217788383673416690068487595062922771414230914791138743960472798057054853883175313487137767631446949382388070798609545617543049566741624609996040273727
n = 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
p=163724217068973025857079545677048587508164102644298632911494474022224582218067057349189211462632427829087720476013052665037199232658015194718500750961261016558605363103092187533086949903145449057015220561698195502163792192055762108803714387175594231859738263839090338762578040513451585421537323416472060788989
q=149604112324264915811376746906108325951188179904814259006959765070266946659481820938211689946210254302179197289522748397160602946376246768419310765669852537378426700376878745285639531531077237124655345323906476180103106894642043615024716862503414785057646920410083538192951872861366496901158348770066798098371
keypair = RSA.generate(2048)
keypair.p = p
keypair.q = q
keypair.e = e
keypair.n = n
keypair.d = d

private_key = keypair.exportKey().decode('utf-8')
f = open('pri.pem', 'w') #生成的私钥文件是pri.pem。
f.write(private_key)

openssl解密即可。

img

详细的openssl使用方法可参考:

https://abcdxyzk.github.io/blog/2018/02/09/tools-openssl/

17.已知p+q和(p+1)(q+1)

题目给出p+q,(p+1)(q+1),e和c。

img

首先需要求出phi,然后求解d,最后再求解m。

1
2
phi = (p-1)(q-1)
    = pq - (p+q) + 1 

p+q的值题目已经给出了,接下来只需要求出pq的值即可求出phi的值。题目还给出了(p+1)(q+1),我们考虑下pq是否可以表示为(p+1)(q+1)的形式:

1
2
(p+1)(q+1) = pq + p + q + 1    
	   = pq + (p+q) + 1

那么pq就可以表示为:

1
pq = (p+1)(q+1) - (p+q) -1

然后,求解phi的值。

1
2
3
phi = (p-1)(q-1)
    = pq - (p+q) + 1 
    = n - (p+q) + 1

最后:

1
2
d = gmpy2.invert(e,phi)
m = pow(c,d,n)

完整的解题脚本如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#!/usr/bin/python
#coding:utf-8

import gmpy2
from Crypto.Util.number import long_to_bytes

#p+q通过p_add_q表示
p_add_q = 326429100407681651814978442415826213864753565034919374282004148849764531414964129530662174521568050093736341197400405816551402307458686750141836996345723514698979514133066389538988520826440776264241138888155090851605191090286605183976443204444854546781116840786281855819689375353337207819361769484061133586660

#(p+1)(q+1)为了方便用x表示
x = 26601616557971867831128918184476970808722471200861600741488181559976427915212193001812160532906370924454473038671991616741424706794741682437728013348910646937734672343325523407437596920797247711273378236903138971315823251358525257853681659038646150834388504990678755552658405772625078429891153401221091704935464031276762725209220275197422069811202440482709667987828399235771854454331605660739185369563297937712412914621262089799368586352843414856752338979163598254668715003106493342377951882955338211218066635494610164992383277776336257215001515405312235576928828485922034700150519853591032361405975195251746299510720

c = 24831377919906161196266552704492935537768087456188711284519872226691826290351027606307936414989585764319104737516021733938210516424254235349369088344349700976416957839221585194510124601438798302079231278339823353520868327987552051471031155633165987892206927171527428590536203275545528900845222038924459888879261986663709510987273937159905675940592632023428129764650249246182611973968609631056274792336171105433760493214971141615401120748113420469659787315651721605227003326305005720436114240966565179896456348773794946970503274768701856591123183247406604013805700201562056023223765073732621940021232679124486597812994

e = 65537


#n = pq = (p+1)(q+1) - (p+q) - 1 = x - p_add_q - 1
n = x - p_add_q - 1

#phi = (p-1)(q-1) = pq - (p+q) + 1 = n - (p+q) + 1 = n - p_add_q + 1
phi = n - p_add_q + 1

d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

运行结果:

img

18.已知p-q和n

这个题相比于(17)而言,不太容易直接想到转化的等式。

题目给出p-q,n,e和c。

img

常规的RSA解密步骤:

1
2
3
4
n = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)

因为n不可分解,所以,我们无法直接得到p和q的值,也就无法得到phi的值。

通过对phi的如下分解可知,如果已知n和p+q便可求得phi的值。

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

因为,给了p-q的值,所以,我们需要设法将p+q表示为p-q,进而求得phi的值。

推导过程如下:

(1)p-q的平方可以如下分解:

$$ (p-q)^2 = p^2 + q^2 -2pq $$

因此:

$$ p^2 + q^2 = (p-q)^2 +2pq $$

(2)p+q的平方可以如下分解:

$$ \begin{aligned} (p+q)^2 &= p^2 + q^2 + 2pq \\ &= (p-q)^2 + 2pq + 2pq \\ &= (p-q)^2 + 4pq \end{aligned} $$

故p+q可表示为:

$$ \begin{aligned} p+q &= \sqrt{(p-q)^2 + 4pq} \\ &= \sqrt{(p-q)^2 + 4n} \end{aligned} $$
这样,我们就可以求出p+q的值,进而可以求出phi的值。最后就可以求出明文m的值了。

解题脚本如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/python
#coding:utf-8
#变量p_add_q:p + q
#变量p_sub_q:p - q

import gmpy2
from Crypto.Util.number import long_to_bytes

n = 27552304606229034903366058815849954030287648695063385362955432137790872571412035824128918674719247737295565001575991597519270789776408208970323808016733976338433371328100880898942106515627607388226912870981180215883273805491209461671730377099185278711453949265641966582563910708529619185885928310168288810488784242368160743359666583499117949407921812317700250240067929572558785431071173411100434109661677786734923283679392823901052633992456780285091988542875991410528415886437666510014123352497264017734716859350294159440761760921548702546470902740121962033241003215821780125194400741190925169397917247376657863011603
e = 65537 
c = 8643831704675414121804983915084443744489969712473300784256427784417167322852556975560503484179280700293119974607254037642425650493676448134024809335297135239994950178868535219541095694358323044214971760829173918774094415933808417722001811285178546917655837402000771685507972240389565704149610032767242977174132826100177368764169367458684152505611469248099487912367364804360878611296860803835816266114046682291529593099394952245852157119233687981777202751472502060481232341206366584532964027749320641690448228420342308891797513656897566100268729012788419021059054907653832828437666012596894150751431936476816983845357
p_sub_q = 3216514606297172806828066063738105740383963382396892688569683235383985567043193404185955880509592930874764682428425994713750665248099953457550673860782324431970917492727256948066013701406000049963109681898567026552657377599263519201715733179565306750754520746601394738797021362510415215113118083969304423858

p_add_q = gmpy2.iroot(p_sub_q**2 + 4*n, 2)  
#iroot()返回值为一个(x,y)元组。其中x为结果值,y为一个bool型变量,如果x为整数,y=True,否则y=False。


phi = n - p_add_q[0] + 1

d = gmpy2.invert(e,phi)

m = pow(c,d,n)

print(long_to_bytes(m))

运行结果:

img

19.其它

适用情况:还有其他的一些题型,在接下来的学习中就靠你们自己积累了。我只能帮你到这里了。

说道这,‘题型升级’也讲的差不多了,基本上我掌握的就这么些了,我也该转战别的方向了,哈哈哈,IDA真的迷人。

这里只讲了前3部分,第四部分–综合题目,我就不搬上来了,可以访问这个github地址去查看。建议做做里面的题目"V&N2020 公开赛"和"DASCTF题目"。

https://github.com/Mr-Aur0ra/RSA/tree/master/%E7%BB%BC%E5%90%88%E9%A2%98%E7%9B%AE

对了,要是有讲的错误的地方,可以指出来我改正呦。

对于从标题(13)之后偶尔更新的题目,我就不共享百度网盘链接了,一次次重新打包文件夹太麻烦了,所以,我就直接连同题目和解题脚本放到给出的github链接上了。

word文档下载:

链接: https://pan.baidu.com/s/1u7z69UTCWwgd-MOO6KYJdw 提取码: y74u

updatedupdated2024-02-012024-02-01