首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. CTF对抗
    3. 发新帖
[推荐][原创]CTF-RSA常见题型、思路及解法
2020-10-29 18:07 17142

[推荐][原创]CTF-RSA常见题型、思路及解法

happi0 活跃值
1
2020-10-29 18:07
17142

RSA入门:

写在前面:

这篇文章是帮助对RSA不熟悉的朋友且需要较为快速、深入的了解RSA而写的

 

不涉及非常晦涩难懂的数学知识和算法(不过最简单的原理说明还是有的)

 

攻击方法也是最容易遇到的(RSA的进阶篇除外)

 

并且所有的例题都是比较新的,甚至还有刚刚结束的比赛的题目

基本原理:

公钥与私钥的产生：

 

(1)进行加密之前，首先找出2个不同的大质数p和q

 

(2)计算n=p*q

 

(3)根据欧拉函数，求得φ(n)=φ(p)φ(q)=(p−1)(q−1)

 

(4)找出一个公钥e，e要满足: 1<e<φ(n) 的整数，且使e和φ(N)互质。

 

(5)根据e*d除以φ(n)余数为1，找到私钥d。

 

(6)所以,公钥就是(n,e) 私钥就是(n,d)

 

消息加密:

 

m^e除以n求余数即为c(密文)

 

消息解密:

 

c^d除以n求余数即为m(明文)

关于基本原理的一些说明:

算法原理:

RSA公开密钥密码体制的原理是:

根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥

模运算规则:

模运算与基本四则运算有些相似，但是除法例外。其规则如下:

  • (a + b) % p = (a % p + b % p) % p
  • (a - b) % p = (a % p - b % p) % p
  • (a * b) % p = (a % p * b % p) % p
  • (a ^ b) % p = ((a % p)^b) % p

    结合律：

  • ((a+b) % p + c) % p = (a + (b+c) % p) % p （5）
  • ((a*b) % p * c)% p = (a *(b*c)%p) % p （6）

    交换律：

  • (a + b) % p = (b+a) % p
  • (a * b) % p = (b * a) % p

    分配律：

  • ((a +b)% p * c) % p = ((a * c) %p + (b * c) % p) % p

    重要定理：

  • 若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)
  • 若a≡b (% p)，则对于任意的正整数c，都有(a * c) ≡ (b * c) (%p)
  • 若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，
    (a * c) ≡ (b * d) (%p)

欧拉函数:

定义:

在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）

 

例如φ(8)= 4，因为1,3,5,7均和8互质

特殊性质:

  • p^k型欧拉函数:

若N是质数p的k次幂(即N=p^k)，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)。

  • mn型欧拉函数(联想rsa算法的p和q)

设n为正整数，以φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值。

 

若m,n互质，φ(mn)=(m-1)(n-1)=φ(m)φ(n)。

基础知识的练习:

buuctf-RSA:

在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d作为flag提交

1
2
3
4
5
6
7
8
#!/usr/bin/python
import gmpy2                        #导入gmpy2库,gmpy2库在rsa解密过程中有很大的作用
p = 473398607161
q = 4511491
e = 17
phi  =  (q-1) * (p-1)               #φ(n)通常也被写作phi
d  =  gmpy2.invert(e,phi)           #通过e和phi求d
print(d)

buuctf-rsarsa:

题目:

1
2
3
4
5
6
7
8
Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.
 
p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
 
Use RSA to find the secret message

解题:

1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/python
import gmpy2
 
p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
n = q*p
phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(m)

倒数第二行的gmpy2.powmod也可以用pow函数替代,不过前者比后者的计算速度快很多,之后有道题可以体现出来

RSA的基础攻击方式:

自此,我们已经了解了rsa的原理,现在开始进入学习rsa的一些攻击方式

1.暴力分解n

用于已知e,c,m,不是很大的n(小于等于1024),或者n具有缺陷,q和p相差过大或过小

 

常用分解方法:

名称 特点 个人使用感受
factordb n(需要安装对应的py模块，pip install factordb-pycli) 利用数据库查询 可以查询到大多数数据,非常推荐
yafu分解 可以对有缺陷的n快速分解 有时候factordb查询不到时可以用yafu分解试试,可能有奇效
linux下命令行: factor n(计算,n较小时推荐) 环境依赖少 应该是爆破计算,对于大数支持很差
在线分解: http://factordb.com/ 数据库查询 体验不佳
 

如果第一项,和第二项都无法分解,就应该考虑换一种思路了,题目考点应该不是暴力分解

例题1：

已知一段RSA加密的信息为：0xdc2eeeb2782c且已知加密所用的公钥：

 

(N=322831561921859 e = 23)

 

请解密出明文，提交时请将数字转化为ascii码提交

 

比如你解出的明文是0x6162，那么请提交字符串ab

 

提交格式:PCTF{明文字符串}

解题:

首先整理一下已知条件:

 

我们已知公钥:

 

n和e,以及密文c

 

想要通过密文c来解得明文m需要私钥d

 

而私钥d需要通过e和phi求出,其中e已知,所以我们只需要知道phi

 

而phi = (q-1) * (p-1),幸运的是我们知道n = q*p,且q和p都是素数,如果我们能通过n分解出p和q则可以解出这道题目了

分解n:

1
factordb n

得到p = 13574881 , q = 23781539(q和p不涉及其他关系时,p和q的顺序无所谓)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/python
from Crypto.Util.number import long_to_bytes
import gmpy2
 
p =  13574881
q = 23781539
n = q*p
e = 23
c = 0xdc2eeeb2782c
phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
m = long_to_bytes(m)        #把整数依照asc码转化成字符串
print(m)

例题2:[GWCTF 2019]BabyRSA

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
import hashlib
import sympy
from Crypto.Util.number import *
 
flag = 'GWHT{******}'
secret = '******'
 
assert(len(flag) == 38)
 
half = len(flag) / 2
 
flag1 = flag[:half]
flag2 = flag[half:]
 
secret_num = getPrime(1024) * bytes_to_long(secret)
 
p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)
 
N = p * q
 
e = 0x10001
 
F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)
 
c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)
 
m1 = pow(c1, e, N)
m2 = pow(c2, e, N)
 
output = open('secret', 'w')
output.write('N=' + str(N) + '\n')
output.write('m1=' + str(m1) + '\n')
output.write('m2=' + str(m2) + '\n')
output.close()

可以从这两句代码看出:

1
2
p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)

可以知道,q和p相差很小,所以这个n是具有缺陷的,通常有两种攻击方式

  • 对n开方并把值设为r,那么q < r < p ,且q和p是素数,既然p和q相差很小,可以通过循环快速可以确定p和q
  • yafu分解

分解出来后,是一个简单是数学等式,用z3约束器可以快速求解

 

(使用yafu分解的攻击方法比较简单,这里就不写了)

解题:

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
#!/usr/bin/python
import gmpy2
from Crypto.Util.number import isPrime,long_to_bytes
from z3 import *
 
N = 636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
e = 65537
 
cc1 = 90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
cc2 = 487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
 
r = gmpy2.iroot(N,2)[0]
 
for i in range(r,N):
    if isPrime(i):
        if N % i == 0:
            p = i
            q = N // i
            break
 
phi = (p-1) * (q-1)
d = gmpy2.invert(e,phi)
a = gmpy2.powmod(cc1,d,N)
b = gmpy2.powmod(cc2,d,N)
 
#a = 2732509502629189160482346120094198557857912754
#b = 5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554
 
s = Solver()
c1, c2 = Ints('c1 c2')
s.add(c1 + c2 == 2732509502629189160482346120094198557857912754)
s.add(c1**3 + c2**3 == 5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554)
if s.check() == sat:
    m1 = (s.model()[c1]).as_long()
    m2 = (s.model()[c2]).as_long()
 
m1 = str(long_to_bytes(m1))[2:-1]
m2 = str(long_to_bytes(m2))[2:-1]
m = m1 + m2
print(m)

2.与公钥私钥交互获得数据:

工具 优点 缺点
openssl 功能最全 对数据要求严格
RsaCtfTool 操作简单 功能不全
Python 功能灵活 需要自己写脚本

openssl:

指令 功能
genrsa 生成并输入一个RSA私钥
rsa 处理RSA密钥的格式转换等问题
rsautl 使用RSA密钥进行加密、解密、签名和验证等运算

genrsa

1
2
usage: genrsa [args] [numbits]                       //密钥位数，建议1024及以上
-out file       output the key to file             //生成的密钥文件，可从中提取公钥

rsa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
rsa [options] <infile >outfile
-inform arg     input format - one of DER NET PEM                      //输入文件格式，默认pem格式
-outform arg    output format - one of DER NET PEM                     //输入文件格式，默认pem格式
-in arg         input file                                             //输入文件
-passin arg     input file pass phrase source                          //指定输入文件的加密口令，可来自文件、终端、环境变量等
-out arg        output file                                            //输出文件
-passout arg    output file pass phrase source                         //指定输出文件的加密口令，可来自文件、终端、环境变量等
-des            encrypt PEM output with cbc des                        //使用des加密输出的文件
-des3           encrypt PEM output with ede cbc des using 168 bit key  //使用des3加密输出的文件
-seed           encrypt PEM output with cbc seed                       //使用seed加密输出的文件
-aes128, -aes192, -aes256
encrypt PEM output with cbc aes                        //使用aes加密输出的文件
-camellia128, -camellia192, -camellia256
encrypt PEM output with cbc camellia                   //使用camellia加密输出的文件呢
-text           print the key in text                                  //以明文形式输出各个参数值
-noout          don't print key out                                    //不输出密钥到任何文件
-modulus        print the RSA key modulus                              //输出模数指
-check          verify key consistency                                 //检查输入密钥的正确性和一致性
-pubin          expect a public key in input file                      //指定输入文件是公钥
-pubout         output a public key                                    //指定输出文件是公钥
-engine e       use engine e, possibly a hardware device.              //指定三方加密库或者硬件

rsautl

数据补齐方式 输入数据长度 输出数据长度 参数字符串
PKCS#1 v1.5 少于(密钥长度-11)字节 同密钥长度 -pkcs
PKCS#1 OAEP 少于(密钥长度-11)字节 同密钥长度 -oaep
PKCS#1 for SSLv23 少于(密钥长度-11)字节 同密钥长度 -ssl
不使用补齐 同密钥长度 同密钥长度 -raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Usage: rsautl [options]
-in file        input file                                           //输入文件
-out file       output file                                          //输出文件
-inkey file     input key                                            //输入的密钥
-keyform arg    private key format - default PEM                     //指定密钥格式
-pubin          input is an RSA public                               //指定输入的是RSA公钥
-certin         input is a certificate carrying an RSA public key    //指定输入的是证书文件
-ssl            use SSL v2 padding                                   //使用SSLv23的填充方式
-raw            use no padding                                       //不进行填充
-pkcs           use PKCS#1 v1.5 padding (default)                    //使用V1.5的填充方式
-oaep           use PKCS#1 OAEP                                      //使用OAEP的填充方式
-sign           sign with private key                                //使用私钥做签名
-verify         verify with public key                               //使用公钥认证签名
-encrypt        encrypt with public key                              //使用公钥加密
-decrypt        decrypt with private key                             //使用私钥解密
-hexdump        hex dump output                                      //以16进制dump输出
-engine e       use engine e, possibly a hardware device.            //指定三方库或者硬件设备
-passin arg    pass phrase source                                    //指定输入的密码

生成私钥:

openssl genrsa -out prikey

查看私钥:

openssl rsa -in prikey -text -modulus

从私钥总提取公钥:

openssl rsa -in prikey -pubout -out pubkey

查看公钥:

openssl rsa -in pubkey -text -modulus -pubin

加密:

openssl rsautl -encrypt -in filename -inkey pubkey -pubin -out filename

解密:(如果有对应的补齐方式需要指定)

rsautl -decrypt -inkey prikey -in filename

Rsactftool:

1
2
3
4
5
6
7
usage: RsaCtfTool.py [-h] [--publickey PUBLICKEY] [--timeout TIMEOUT]
[--createpub] [--dumpkey] [--ext]
[--uncipherfile UNCIPHERFILE] [--uncipher UNCIPHER]
[--verbosity {CRITICAL,ERROR,WARNING,DEBUG,INFO}]
[--private] [--ecmdigits ECMDIGITS] [-n N] [-p P] [-q Q]
[-e E] [--key KEY]
[--attack ]

生成公钥:

RsaCtfTool.py --createpub -n number -e number > pubkey

查看公钥:

RsaCtfTool.py --dumpkey --filename pub.pem

已知公钥求私钥:

RsaCtfTool.py --publickey pubkey --private

已知公钥,自动解密:

RsaCtfTool.py --publickey pubkey --uncipherfile filename

例题1.西湖论剑-rsa

给了两个文件,message 和 public.key

 

以及加密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import flag
import os
rsa = RSA.generate(2048)
public_key = rsa.publickey().exportKey()
f=open("public.key","w")
f.write(public_key.decode())
f.close()
 
rsakey=RSA.importKey(open("public.key","r").read())
rsa = PKCS1_OAEP.new(rsakey)
msg=rsa.encrypt(flag.encode())
f=open("message","wb")
f.write(msg)
f.close()

首先打开公钥看看

1
openssl rsa -in public.key -pubin -modulus -text
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
Modulus:
00:c2:07:45:22:3f:f5:b9:4b:2c:d8:41:21:66:f7:
28:8a:21:f2:18:7e:1a:42:14:53:91:8c:ab:03:c8:
02:53:45:12:33:eb:1b:dc:23:63:74:42:28:aa:86:
94:a8:c2:cb:c8:33:f8:0d:df:40:83:1a:68:90:1b:
23:0b:83:f3:f0:fe:d4:b7:2d:0b:94:2b:5e:95:de:
da:c8:dc:c0:04:7a:2a:fb:90:c8:1e:d7:2d:3a:d4:
9b:72:fc:8b:d0:d3:16:7d:dd:aa:6a:b5:16:7c:05:
8d:f3:6a:f1:90:b2:16:08:5b:bd:9d:62:1f:9b:d2:
3a:09:3e:4e:3d:9c:c3:87:b6:27:4f:2c:33:9c:88:
e1:b2:d9:08:ac:b3:3f:4e:20:e6:47:ab:ee:07:14:
a3:cc:e4:64:6e:89:62:94:b7:81:03:dc:c9:a4:db:
7e:d6:81:16:4c:6e:6c:c7:fd:33:47:6e:17:4a:6c:
70:70:37:b2:50:49:13:65:f9:f0:eb:76:ae:ab:a0:
7d:b2:f6:62:d8:80:48:af:98:c8:8c:76:c6:71:0d:
b9:65:8d:49:fc:a0:ca:f1:f5:cd:99:dc:07:f1:88:
43:2b:48:f8:55:71:16:8a:d1:0f:c8:24:b7:b6:82:
ba:d6:ca:a5:d1:2f:f6:f0:4c:92:78:6b:73:8a:b1:
9b:b7
Exponent:
1d:2d:2f:1f:17:3f:81:cf:36:8f:ec:06:d4:0d:47:
fd:92:f8:61:5c:12:ee:c1:41:68:f2:88:42:79:52:
b8:cf:5a:53:8f:70:ba:33:41:b6:a1:73:ae:80:37:
5a:96:b0:d3:84:d9:72:2b:19:14:9f:78:94:73:75:
e0:a3:3d:f5:e6:93:ed:ab:d5:e4:d4:4c:ff:a9:e5:
25:ea:01:4f:3f:a4:99:b5:f7:b2:9b:21:9d:90:b8:
8d:a5:5a:ae:3a:08:63:73:38:d7:be:d0:56:e3:ae:
c5:75:be:56:bb:de:53:4b:35:5a:2e:77:57:db:7a:
ec:a9:6e:78:d6:7f:21:53:0b:7c:3e:c2:4a:c6:1f:
9b:47:4a:b2:83:22:0d:d9:54:51:35:d0:65:a7:24:
ce:2f:8f:44:e3:2e:46:0e:ef:5f:99:58:00:9c:58:
af:59:51:93:d7:7e:72:c2:5f:0c:b0:15:05:b9:93:
c1:35:32:8b:11:b5:00:dc:ab:c9:55:c9:17:7f:83:
9d:d0:43:58:6e:25:a3:13:35:e7:d5:43:7d:c9:e6:
cd:6d:4e:be:cb:29:37:e1:60:26:c2:79:2e:17:45:
f4:4e:ed:54:11:be:aa:b5:5e:d0:90:5d:b9:19:8c:
bd:43:11:11:be:87:46:2f:46:36:9e:31:d1:a4:61:
3f

可以看到e和n非常大,应该考虑Wiener攻击(后面会介绍到)

 

不过这里主要是介绍和公钥、私钥的交互

 

所以我们用RsaCtfTool来爆破出私钥

1
python RsaCtfTool.py --publickey public.key --private >> pri.key

得到了私钥,尝试用openssl解密

1
openssl rsautl -decrypt  -in message -inkey pri.key

却报错了,为什么呢

 

我们观察题目给出的加密脚本第二行"from Crypto.Cipher import PKCS1_OAEP"

 

说明这里是用的使用OAEP的填充方式,而解密是也必须指明对应的填充模式

1
openssl rsautl -decrypt -oaep -in message -inkey pri.key

3.简单的数学变换

例题1:[GUET-CTF2019]BabyRSA

1
2
3
4
5
p+q : 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
(p+1)(q+1) : 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e : 0xe6b1bee47bd63f615c7d0a43c529d219
d : 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
enc_flag : 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a

解题:

这类题核心解法大体相同,出题人给出有唯一解的q和p的方程,通过解出q,p来解题

 

大多数简单的数学方程可以用z3约束器快速解出

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
#!/usr/bin/python
import gmpy2
from Crypto.Util.number import long_to_bytes
from z3 import *
 
tmp1 = 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
tmp2 = 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e = 0xe6b1bee47bd63f615c7d0a43c529d219
d = 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
c = 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a
 
s = Solver()
p,q = Ints('p q')
s.add(p+q == tmp1)
s.add((p+1) * (q+1) == tmp2)
assert s.check() == sat
p = s.model()[p].as_long()
q = s.model()[q].as_long()
n = q*p
 
phi = (p-1) * (q-1)
 
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

例题2.[BJDCTF2020]easyrsa

题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import getPrime,bytes_to_long
from sympy import Derivative
from fractions import Fraction
from secret import flag
 
p=getPrime(1024)
q=getPrime(1024)
e=65537
n=p*q
z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))
m=bytes_to_long(flag)
c=pow(m,e,n)
print(c,z,n)
'''
output:
7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
 
'''

解题:

这道题挺有意思的,在给出的脚本第10行

 

有两个没见过的函数,通过搜索资料,可以查到相关资料

  • Fraction,返回参数1/参数2的分数形式

  • Derivative，返回参数1函数在参数2点的导数

    联系这两点

    可以知道

    z = Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))

    = 1/(1/(1+p^2)) - 1/(1/(1-q^2))

    = 1+p^2 + q^2 -1

    = p^2 + q^2

    又把本题转化成简单的数学问题了

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
import gmpy2
from Crypto.Util.number import long_to_bytes
from z3 import *
 
c = 7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z = 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n = 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
e=65537
 
s = Solver()
a,b = Ints('a b')
s.add( a*b == 15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441)
s.add( a**2 + b**2 == 32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482)
s.add(0 < a, 0 < b)
 
if s.check() == sat:
    q = s.model()[a].as_long()
    p = s.model()[b].as_long()
 
phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))

常见攻击方式:

1.低加密指数分解攻击

原理:

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

 

由于e很小,当n很大时,m^e也比n小很多.尝试把c开根号看能否得到明文.

例题:[NCTF2019]easyRSA

题目描述:

 

When you need really secure communications, you use RSA with a 4096 bit key.

 

I want really really really secure communications to transmit the nuclear launch codes (yeah IoT is everywhere man) so I used RSA with a 16777216 bit key. Surely russians will not be able to factor that one !

 

File md5 : 1049a0c83a2e34760363b4ad9778753f

解题:

题目给出了n和c,e,不过这个文本文件的大小高达7.4m,要是常规分解的话,估计量子计算机也够呛

 

不过由于n是16777216 bit的数字,e只有0x10001,所以m^e << n,符合低加密指数分解攻击的条件

1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/python
import gmpy2
from Crypto.Util.number import long_to_bytes
 
e = 0x10001
 
f = open("./out.txt","r")
data = f.read()
data = int(data,16)
 
m = gmpy2.iroot(data,e)[0]
print(long_to_bytes(m))

这里我们也应该理解到,低加密指数并非指e == 2或e == 3这类,e的数值很小,而是m^e和n的相对大小

2.小明文攻击

原理:

公钥e很小，明文m也不大的话，于是m^e=k*n+m 中的的k值很小甚至为0(k==0时,和上一种攻击方式差别不大)，爆破k或直接开e次方即可。

例题:[De1CTF2019]babyrsa(部分)

1
2
3
4
5
6
7
8
9
from data import e1,e2,p,q1p,q1q,hint,flag
ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
assert(pow(e1,ee1,n)==ce1)          #断言,括号里的等式恒成立
assert(pow(e2+tmp,ee2,n)==ce2)

解题:

我们拿到两个类似rsa加密的式子:

  • (e1^ee1) mod n == ce1
  • ((e2+tmp)^ee2) mod n == ce2
    由于两个式子的加密指数很小(ee1 = 42,ee2 = 3),考虑小指数攻击
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
#!/usr/bin/python
import gmpy2
 
ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
 
#--------find e1--------
for k in range(200000000):
    c = k*n + ce1
    if gmpy2.iroot(c,ee1)[1]:
    e1 = gmpy2.iroot(c,ee1)[0]
    break
#---------check e1-----
if ce1 == gmpy2.powmod(e1,ee1,n):
    print("e1 = %d"%e1)
 
#--------find e2--------
for k in range(1000000):
    c = k*n + ce2
    if gmpy2.iroot(c,3)[1]:
    m = gmpy2.iroot(c,3)[0]
    e2 = m - tmp
    break
#---------check e2-----
if ce2 == gmpy2.powmod((e2+tmp),3,n):
    print("e2 = %d"%e2)
1
2
e1 = 15218928658178
e2 = 381791429275130

3.低解密指数攻击:

本质上,第一种、第二种攻击方式都是因为e选取的较小而造成的缺陷,那么e选取的非常大是不是就很安全呢？

 

实际上也不是,当e很大时,就会造成d非常的小,也具有相当大的危险

原理:

顾名思义,这是一种针对d很小时的攻击方式

 

此种攻击方法由Micheal j.Wiener于1989提出,所以也被称为Wiener's attack,该方法基于连分数

 

该方法在github已有完整可用的代码,之后所有的低解密指数也是利用以上脚本进行的

题目:buuctf-rsa2

1
2
3
4
5
N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
 
import hashlib
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"

解题:

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/python2
 
import gmpy2
from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic
from Crypto.Util.number import long_to_bytes
 
def wiener_hack(e, n):
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("Hacked!")
return d
return False
def main():
n = int(input("input the n :\n"))
e = int(input("input the e :\n"))
 
d = wiener_hack(e, n)
print(d)
if __name__=="__main__":
main()

4.模不互素

原理:

把大数分解成两个素数很困难,但是求两个大数的公因子很容易

 

当:

  • n1 = a*b
  • n2 = a*c

我们可以通过求gcd(n1,n2)来得到a,再通过除法分别求得b和c,从而达到了分解大素数的目的

例题:QCTF2018Xman-RSA(部分)

1
2
3
4
5
6
7
8
9
10
p1 = get_a_prime(128)
p2 = get_a_prime(128)
p3 = get_a_prime(128)
n1 = p1*p2
n2 = p1*p3
e = 0x1001
c1 = encrypt(msg1, e, n1)
c2 = encrypt(msg2, e, n2)
print(c1)
print(c2)

解题:

可以通过gcd(n1,n2)快速求得p1

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
#!/usr/bin/python
import gmpy2
from Crypto.Util.number import long_to_bytes,isPrime
n1 = 2499586809914462821807624371088011200618603528498132509598946284572455726453497171635086810524607288333625665025664872216634366700044105279185519761587818169021167370991396691510275499486673922916370294043072503635630922980240462022218565365191228535222150496387990987123639567257124081274667568443678527637259644488779394704508217357758791670308548246801142468699716221789070607334747835552167450340441488756779323653879402176647890584656379628685893686585469918686253137796663587854943386347039389769790329948165162483370187914412810153613198247569427480466488647563900948387020677830797976534568626241686906738179
n2 = 7741603029707932330739678982394275613217057249691533148704382574439895657047911501600910571360188397109729289277796711334388156202412769743785164713243932001078475541271281825859671767783178037363138683152051263779907568124470598237502689045677891605285193637790880045372303913424654655825837641694318544209980415256180296972066060073206323473960669679401950151966003026531573962072358852304635671658878866030003484715256388556599713638695448516673643703041094737763957937855870992247472296348887788212823714735080211059688680618314050267995177478035769912691185787944037050674163079867101586607780761245261558200843
n3 = 9895571060693703887018268413746107679094703478067972087862851570192520012058188062485476484700707994684397704099884436398099581319015589480235346899990863625919087077906193223937343450727301243043576326163300258770936289423785376338765758863453745278516208013244068358484113062931878984339475569902332075509121153749576470546863477142562563573654198332099438611713385318497180237117792417826080724886477023904678472464557511959911739272258202310963925049222305927992349171516332320267610895787011879250778522843808895509894741144901052000573058315131265960606119769594234837973757057319170067823816025499647517874841
c1 = 0x1240198b148089290e375b999569f0d53c32d356b2e95f5acee070f016b3bef243d0b5e46d9ad7aa7dfe2f21bda920d0ac7ce7b1e48f22b2de410c6f391ce7c4347c65ffc9704ecb3068005e9f35cbbb7b27e0f7a18f4f42ae572d77aaa3ee189418d6a07bab7d93beaa365c98349d8599eb68d21313795f380f05f5b3dfdc6272635ede1f83d308c0fdb2baf444b9ee138132d0d532c3c7e60efb25b9bf9cb62dba9833aa3706344229bd6045f0877661a073b6deef2763452d0ad7ab3404ba494b93fd6dfdf4c28e4fe83a72884a99ddf15ca030ace978f2da87b79b4f504f1d15b5b96c654f6cd5179b72ed5f84d3a16a8f0d5bf6774e7fd98d27bf3c9839
c2 = 0x129d5d4ab3f9e8017d4e6761702467bbeb1b884b6c4f8ff397d078a8c41186a3d52977fa2307d5b6a0ad01fedfc3ba7b70f776ba3790a43444fb954e5afd64b1a3abeb6507cf70a5eb44678a886adf81cb4848a35afb4db7cd7818f566c7e6e2911f5ababdbdd2d4ff9825827e58d48d5466e021a64599b3e867840c07e29582961f81643df07f678a61a9f9027ebd34094e272dfbdc4619fa0ac60f0189af785df77e7ec784e086cf692a7bf7113a7fb8446a65efa8b431c6f72c14bcfa49c9b491fb1d87f2570059e0f13166a85bb555b40549f45f04bc5dbd09d8b858a5382be6497d88197ffb86381085756365bd757ec3cdfa8a77ba1728ec2de596c5ab
 
p1 = gmpy2.gcd(n1,n2)
p2 = n1//p1
p3 = n2//p1
 
assert isPrime(p1)          //检查这三个数是否为素数
assert isPrime(p2)
assert isPrime(p3)
 
e = 0x1001
phi1 = (p1-1) * (p2-1)
phi2 = (p1-1) * (p3-1)
 
d1 = gmpy2.invert(e,phi1)
d2 = gmpy2.invert(e,phi2)
 
m1 = gmpy2.powmod(c1,d1,n1)
m2 = gmpy2.powmod(c2,d2,n2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))

5.共模攻击:

原理:

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

 

证明:

1
2
3
4
5
6
7
8
9
10
11
明文m、模数n相同，公钥指数e、密文c不同，gcd(e1,e2)==1,也就是e1和e2互质时
e1*s1+e2*s3 = 1
有唯一的解
由于:
c1 == m^e1 mod n
c2 == m e2 mod n
那么:
  (c1^s1 * c2 ^ s2) mod n
= ( (m^e1 mod n)^s1 * (m^e2 mod n)^s2 )mod n
= m^(e1*s1) * m^(e2*s2) mod n
= m mod n

当n不变，知道n,e1,e2,c1,c2 可以在不知道d1,d2情况下，解出m。

题目:RSA_what:

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
from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from gmpy2 import powmod
 
p = getPrime(2048)
q = getPrime(2048)
N = p*q
Phi = (p-1)*(q-1)
def get_enc_key(N,Phi):
e = getPrime(N)
if Phi % e == 0:
    return get_enc_key(N, Phi)
else:
    return e
e1 = get_enc_key(randint(10, 12), Phi)
e2 = get_enc_key(randint(10, 12), Phi)
 
fr = open(r"./base64", "rb")#flag is in this file
f1 = open(r"./HUB1", "wb")
f2 = open(r"./HUB2", "wb")
base64 = fr.read(255)
f1.write("%d\n%d\n" % (N, e1))
f2.write("%d\n%d\n" % (N, e2))
while len(base64)>0:
    pt = bytes_to_long(base64)
    ct1 = powmod(pt, e1, N)
    ct2 = powmod(pt, e2, N)
    f1.write("\n%d" % ct1)
    f2.write("\n%d" % ct2)
    base64 = fr.read(255)
fr.close()
f1.close()
f2.close()

解题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/usr/bin/python2
 
import gmpy2
from Crypto.Util.number import long_to_bytes
 
f1 = open("./HUB1","r")
f2 = open("./HUB2","r")
data1 = f1.readlines()
data2 = f2.readlines()
 
n = int(data1[0])
e1 = int(data1[1])
c1 = int(data1[3])
 
e2 = int(data2[1])
c2 = int(data2[3])
 
_, r, s = gmpy2.gcdext(e1, e2)
 
m = pow(c1, r, n) * pow(c2, s, n) % n
print long_to_bytes(m)

这道题解出来后是base64加密后的字符串,实际上没有看上去那么简单,这里涉及到base64隐写,不过不是本文的主题,先暂且不管

6.广播攻击:

原理:

对于相同的明文,使用相同的指数e和不同的模数n1,n2...ni加密得到i组密文(i>=e),可以使用中国剩余定理解出明文

题目:buuctf-rsa4:

1
2
3
4
5
6
7
8
N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004
c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243
 
N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114
c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344
 
N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323
c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242

解题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#!/usr/bin/python2
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
n = [129114230505356333697118994510021413915051088225570531043026917550451581564734952308651566723784981323900403426111056537185011193232603296112121643742691356399992969898010827710994350803494919151948423732426591598888439712920344266205641475348312727365971717305409127667391782677854219689063549759596429716629,109269702205029292120022054633721536134438763741801805368759852020529400112797868566931991813909053016228871499067304592740926931055426540840268677218282537450757063806695831503892336975370479004151114020279110611956433492281834217463178735931660370487895538198474855043942908224106013915984721193047940206159,130184984206907873325788608067133260010668825744109785989754700869397713689450907426005869455386099782561530247238688647088683853688926890638399087109982966623800264662846723141786785531512452737825132399495839974974884122270947543684537604890177662807013640102549749593966105133111628112742472630785570141963]
c = [112820376318708309511883266356668393396816131447182791445506209031700236878469506355658352414748854472099361508824474365112325602319862842561436679067358900089331778617100580343694334226208753320435002324108477884950933641216044198203776075918323272795752182687450526442079367110656868374931125538339145721573,45651293556966072304818630107703140982560165499022836594523320391474750266281527820821435052904791681898782443840766880327957385288649094238886877657228597671521358830021677304123300882210216797719566693160533018601632768048713030788957904378243453859832229603157052843135978639276611231634399594108602071349,7145575537980676074780210417817024536632595547590648616669010213946256431795860784357127920679439181517662499063976244238924613193503273987203026894830988537974932336129245277788828190575305229420617551083516420170192425247732269483299819348769856966536443995217830327641185916042049253075074223777360483322]
e = 3
data = zip(c, n)
x, n = CRT(data)
m = gmpy2.iroot(gmpy2.mpz(x), e)[0].digits()
m = long_to_bytes(m)
print m

7.已知e和d,求p,q

原理:

当已知e,n,可以通过算法快速求得p和q

 

详细算法见:

 

https://www.di-mgt.com.au/rsa_factorize_n.html

例题:MRCTF2020Easy_RSA(部分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def gen_q():
p = getPrime(1024)
q = getPrime(1024)
assert (p < q)
n = p * q
print("Q_n = ", n)
e = getRandomNBitInteger(53)
F_n = (p - 1) * (q - 1)
while gcd(e, F_n) != 1:
e = getRandomNBitInteger(53)
d = invert(e, F_n)
print("Q_E_D = ", e * d)
factor2 = 2021 * p - 2020 * q
if factor2 < 0:
factor2 = (-1) * factor2
return sympy.nextprime(factor2)
1
2
Q_n =  20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
Q_E_D =  100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201

解题:

可以看到,这里的p和q都高达1024bit,基本可以排除暴力分解

 

这时我们知道e*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
27
28
29
30
31
32
33
34
35
36
37
#!/usr/bin/python2
 
import random
 
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,d_e):
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 main():
 
n =  20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
d_e =  100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201
 
p,q = getpq(n,d_e)
print(p)
print(q)
if __name__ == '__main__':
main()

8.n分解成多个素数

原理:

rsa加密基本原理

 

需要严格按照欧拉函数的定义来求解phi

例题:15年山东大学生爱好者线上赛

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

解题:

n = p * q * r

 

那么φ(n) = (q-1) * (p-1) * (r-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/python
import gmpy2
from Crypto.Util.number import long_to_bytes
 
n= 544187306850902797629107353619267427694837163600853983242783
e= 39293
c= 439254895818320413408827022398053685867343267971712332011972
p = 67724172605733871
q = 11571390939636959887
r = 694415063702720454699679
phi = (p-1)*(q-1)*(r-1) 
d = gmpy2.invert(e, phi) 
m = pow(c, d, n) 
print(long_to_bytes(m))

9.dp泄漏攻击

原理:

dp本来是为了加速rsa加解密效率的,不过由于dp和p的关系相当密切,所以当dp泄漏也有相当大的危害

1
2
3
4
dp=d%(p-1)
dq=d%(q-1)
dp*e = 1 mod(p-1)
dq*e = 1 mod(q-1)

例题:buuctf-RSA1

1
2
3
4
5
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

解题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/python2
 
import gmpy2 
from Crypto.Util.number import long_to_bytes 
 
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
 
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))

进阶攻击方式

1.私钥文件修复

题目:Jarvis OJ -Crypto-God Like RSA

题目给出了密文文件,公钥和破损的私钥文件(这里就不放上来了)

解题:

首先读出公钥信息和破损的私钥信息填入以下脚本即可恢复出完整的私钥

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
#!/usr/bin/python2
 
import re
import pickle
from itertools import product
from libnum import invmod, gcd
 
 
def solve_linear(a, b, mod):
    if a & 1 == 0 or b & 1 == 0:
        return None
    return (b * invmod(a, mod)) & (mod - 1)  # hack for mod = power of 2
 
 
def to_n(s):
    s = re.sub(r"[^0-9a-f]", "", s)
    return int(s, 16)
 
 
def msk(s):
    cleaned = "".join(map(lambda x: x[-2:], s.split(":")))
    return msk_ranges(cleaned), msk_mask(cleaned), msk_val(cleaned)
 
 
def msk_ranges(s):
    return [range(16) if c == " " else [int(c, 16)] for c in s]
 
 
def msk_mask(s):
    return int("".join("0" if c == " " else "f" for c in s), 16)
 
 
def msk_val(s):
    return int("".join("0" if c == " " else c for c in s), 16)
 
 
E = 65537
 
N = to_n("""00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
    58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
    d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
    b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
    3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
    bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
    67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
    1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
    31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
    ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
    06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
    7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
    3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
    c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
    4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
    9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
    c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
    09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
    8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
    e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
    c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
    79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
    e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
    d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
    41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
    14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
    32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
    e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
    fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
    4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
    ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
    9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
    08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
    89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
    e8:6c:1d""")
 
p_ranges, pmask_msk, pmask_val = msk(""" 0: e:  :  :  :c :c :  :  :  :b :  :  :  :  :
      :ab: e: 2: 8:c :  :  : 1:6 :6 : 6: f:d9: 0:
    8 :5c:7 :06:  :  :  :0 : 3:5 :4b:  :6 :  :  :
    2 :  :6 :  :  :  :2 :bc: c:  :85:1 : 1:d : 3:
     1:b4:  : b: 1: 3: d:a :  :  :6e: 0:b :2 :  :
      :b :  :9 :e :  :82:8d:  :  :13:  :  : a: a:
      :  :4 :  :c : f:  :  :7 :e :0a:  :  : b: 5:
      : e:91:3 :  :3c: 9:  : 6:  :  :b5:7d: 1:  :
      :  :  :b :a1:99:6 :4 :3 :c :1a:02:4 :  : 9:
    9 :f : d:bd:  :0 :  :  :  :b3:  : 4:  :e9: 9:
      : d:  :  :7 :  :93:  : e:dc:  : 0:  :e7:  :
    e :  :2 : b: 2:5 :  :  :  :  : c:5f:  :  :e2:
      :  : 9:  :2a:  : e:  :  :2 :  :9f: 7:3 :  :
    b : f:b :  : 8: 7:  :  :f :6 :e :c :  :3 :  :
    f7: 5: 8: 5:  :  :  :  :  : 8: e:  :03: c:  :
    33:76:e : 1:7 : c:  : 0:  :0b:  : a:  : 2: 9:
      :c8:bf:  :  :06: 7:d5:  :02: c:b :e2: 7:2 :
      :  """)
 
q_ranges, qmask_msk, qmask_val = msk(""" 0: f:  :d0: 1:55: 4:31:  : b:c4:8 :  : e: d:
    34: 3:f :  :  :  :  : 8:99:1 :  : a:0 :  :4 :
    0 :  :f :  :a4:41:2 :  :a :  : 1:  : a: c:  :
      :  : 9:  :  : 2:f4: f:  :  :  :  :1 : 4:9 :
    a :  :  :79:0 :  :  :  :  : 2: 8:b :  :4 : 8:
      :9b: 1:  :d :  :f :e4:  :4 :c :e :  :3 :  :
     7:2 :  :d :8 :2 :7 :  :d :67:fc:e : 0:f9: 7:
    8 :  :  :  :1 :2f:  :51:  :  :2e:0a: e:3d: 6:
    b :  :dd:  : 0:fb:  :f4:  :  :  :b4: 9:c :  :
     a:  :  :  :d :  :  :6b: 2:  :9b: a:60:  :d6:
     0:4f:16:d1:  :  :5 :fc:  :f :  :8 :  :  :  :
     1: 6:e1:9 : e:4 : 6: c: d:d :73: 3:  :  :7 :
      :8 : 9:  :3b:f : 2:  :  :f1: e:  :  :1e:  :
    8 :  :  : 6:0 : 4:99:e :  : 5:  :  : 4:  :  :
      : a:81:64:  :7 :f : 9: d:  :9 :  : 7:93:f :
    ac:8c:  : 8:  : 0: d: 8:  :7 :  :1d:  :f :  :
    1 :a :6 :8 :  :60:  :b3:  :  :  :89:  :  :14:
      :5 """)
 
_, dmask_msk, dmask_val = msk("""  :  :  : f:8 :a5:d : 2: 0:b :7 :  : 1:  : 4:
     1:0d:  :3 :  :6 :  :  : b:  :  :  :e :  :  :
    0e: 0:db:  :1a:1c:c0:  : e:  :  :99:bc:8 :a5:
    7 :7 :7 : b:  :  : 8: 8:  :7 :55: 2:  :  :f :
    b2:  :  :b :f :4 :  : 8:  :b :  :  :  : 0:  :
    0 :  :6 :9 :  :  :  : b: 4:  : 0: a: 5:07:b :
     9: c:9a: 9:  : 7:9e:  : b:60:f :  :  :  :0 :
      : 3:0 :  :  :  : 1:b :  :  : b: 6:0 :f :  :
      : 2:18: 6: b:1 :  :  :  :  :d3:f3:  :a :  :
     3:  :  :  :  : 3: d: 1: 2:7 :  : d:  : 2: d:
      :  : d:4 :  :d :  :6d: c:a :b6:  :  :  : 1:
    69:  : 7:  :89:  :c :8 :61: d:25: 3:7 :1b: 4:
    b :  :8 :55:  :49: 1:2 :3 :  :1 :e9:a8: 3:  :
    9 :  : 1:f8:d3:  :e :  :d :  :9 :b6:  :  :71:
    1 :  :c1:  : b: 1:  : 6:e :  :64:  :  :1a:c :
      : b:  :bf:c :  : 0:  : 8:a :4 :  :26:a :5 :
    6 :  :  :  :eb:  :e5: a:  :3e:f9:10:0 :  :  :
     6:0 :  : 8:  : 1:72: c:0 : f:5 : f:9c: 0: e:
     7:b :  :  :  :  :d9: 4:  : e:c :68:  :  :  :
     c:  :3a:  :  :a0:ea: 3: 4:  :72:a :d : 8:  :
      :0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
      :  :17:6 :  : c: b:  : f:  :3 : 5:6 :3 :0e:
      : 7:c :3e: 2: 9: 7: 6: f: e: f: 9:  :f3: 9:
    a :c1:6 :  : 1:9 :  :43:  : f: 5:  :0 :27: 4:
    4 :a :  :e9:  : 8: 4:3 :8a: 6:16:d5:c : e: e:
      :d : c:b :a8:  : 7:  : 9:  :7 :7d:  :  :  :
      :  :  :4 :2 :  : 3: 3: 6:  :  :  :7b:0 :  :
     e:  :0 :  :a :  : 5:  :  :  : 5:1 :82:c :0d:
    4 :2 :fd:36: 5:50:0 :  :  :d : f: 6:  :  :e :
    0 :  :  :ce:  :9e:8 :  :0 :d :07:b3:  :  :  :
    0 :e4:  :  :68:b :c :  : c:5 :  :  :3 : 7: 2:
     c:e0:  :5 :  :  :b4:  :ef: 7:  :1 :e : 0:f :
      :6 :  :  :  :e0:c :3 :  :  : 3:  : d:  :  :
     3: 3: c: a:  :b : a:71: 3: 0:a :  :4 :5d:  :
    0 :4 """)
 
_, dpmask_msk, dpmask_val = msk("""  : 3:2a:  : d:  :  :  :  :0 :1 : f:  :  : 6:
    1 :2 :1b:07: a:e :b :c5:58:7 :  :e8: 7: 1: c:
      : 1:b :a0: 4:0f:5 :67:  :3 :7 :6 :f9:  : c:
      :79: 0:1 :65:  :8 :  :99: d:d :  :2 :9 :0 :
     e:  :0 :  :  :  : d:  :d :7 :6 :a9: a:8b: b:
      :  : 7: a:37:  :  :7 :1 :6 :  :c2: 7:6 :b :
     e:  :  :  :  :  :  :b :3a:5 :  :  :  :  :  :
      :  :  :cd:8 :  : d:  :7 : 3:  : f:e : c:  :
      : a:  :c : f:c : 7:b :5 :  :  :2 :8 :8 :6 :
    0a: a:  :  :3 :db:  : 4:00:  : d:  :b : 5:  :
    20: 2: 5:  :82:  : 0: 6:  :8a:  :7 :  : 8:  :
     4: 1:  :  :  : 8:46:  :  :  :  :  : 0:f :c8:
    2 :  : c:7 :  : 1:  :  :2 : 0: 5:  :  : 1:9b:
     6:9 : 0:74:  :c :  :e :  :  :cb:b :3 :3 :  :
     2:  :  :47:  :2 : 0:5 :  :  : d: 6:83:  :  :
      :c7:  :  :0b:  :  : c:  :3 :8 :  :9 :4 : 7:
    5 :c0:fe:  :f9: 1:  :0 : e: 8:02:  : f:  :c :
    55:61""")
 
_, dqmask_msk, dqmask_val = msk("""  :0b:7 :4 :0 : 0:6 : 7:7e:  : 5:  : 7:  : a:
    a :d : 0: 6: 4:86:  :  :8 :  :  :  :  :e :8f:
     9:  :  :  : 1:  :2 :  : 7: b:1 :5 : f:  :8 :
      :d :21:  :e : d:  :c9:e : b:  :  :1 :  :  :
      :d :a2:b7:  :  :  :f3:  :42:  :e : c:  :f :
      : 0:f :7 : 4: 5:34:  :4 : c:  :  :8 :d : 8:
    5 :af: 3:1d: 5:4 :  :2 :  :6 :c : 6:a :1 :5 :
     a:9 :  :d :  :  :0a:a1:  :f :7 :9 :b :  :  :
     f:2 :27: f:  :0 :f6:4d:  :  :  :  :  :5 :  :
     4:08:  : 5:  : 8: 5:  :  :  :18: 4: 8:57: 2:
     f: a:  :  :a8: f: c:f : e: 1:9 :c : 4:9 :  :
      :  :  :  :  : 1:  :2 :  :d1:  : 6:e : d:  :
      : f:04:2 :8d:  : 3:  :  :b : 8:  :d6:  : 2:
      :  :  :6 :  : f:  :  : 0:6 :  :51:  :48:19:
      :  :  :69:4 : c:  :c :  : f:  :f4:d :  : f:
     d:0 :0d:b :3 : 3:2 :  :  :6 : b:5 :2 :  : c:
     1:5a: f:f :  :  :7e:3e:  :d :f :0 : d: c: 6:
     1""")
 
 
def search(K, Kp, Kq, check_level, break_step):
    max_step = 0
    cands = [0]
    for step in range(1, break_step + 1):
        #print " ", step, "( max =", max_step, ")"
        max_step = max(step, max_step)
 
        mod = 1 << (4 * step)
        mask = mod - 1
 
        cands_next = []
        for p, new_digit in product(cands, p_ranges[-step]):
            pval = (new_digit << ((step - 1) * 4)) | p
 
            if check_level >= 1:
                qval = solve_linear(pval, N & mask, mod)
                if qval is None or not check_val(qval, mask, qmask_msk, qmask_val):
                    continue
 
            if check_level >= 2:
                val = solve_linear(E, 1 + K * (N - pval - qval + 1), mod)
                if val is None or not check_val(val, mask, dmask_msk, dmask_val):
                    continue
 
            if check_level >= 3:
                val = solve_linear(E, 1 + Kp * (pval - 1), mod)
                if val is None or not check_val(val, mask, dpmask_msk, dpmask_val):
                    continue
 
            if check_level >= 4:
                val = solve_linear(E, 1 + Kq * (qval - 1), mod)
                if val is None or not check_val(val, mask, dqmask_msk, dqmask_val):
                    continue
 
                if pval * qval == N:
                    print "Kq =", Kq
                    print "pwned"
                    print "p =", pval
                    print "q =", qval
                    p = pval
                    q = qval
                    d = invmod(E, (p - 1) * (q - 1))
                    coef = invmod(p, q)
 
                    from Crypto.PublicKey import RSA
                    print RSA.construct(map(long, (N, E, d, p, q, coef))).exportKey()
                    quit()
 
            cands_next.append(pval)
 
        if not cands_next:
            return False
        cands = cands_next
    return True
 
 
 
def check_val(val, mask, mask_msk, mask_val):
    test_mask = mask_msk & mask
    test_val = mask_val & mask
    return val & test_mask == test_val
 
 
# K = 4695
# Kp = 15700
# Kq = 5155
 
for K in range(1, E):
    if K % 100 == 0:
        print "checking", K
    if search(K, 0, 0, check_level=2, break_step=20):
        print "K =", K
        break
 
for Kp in range(1, E):
    if Kp % 1000 == 0:
        print "checking", Kp
    if search(K, Kp, 0, check_level=3, break_step=30):
        print "Kp =", Kp
        break
 
for Kq in range(1, E):
    if Kq % 100 == 0:
        print "checking", Kq
    if search(K, Kp, Kq, check_level=4, break_step=9999):
        print "Kq =", Kq
        break

解出私钥后,写入到文件中,用openssl解密即可(不过需要注意的是这依然是用oaep的填充方式,需要指明)

2.对e爆破

题目1:[HDCTF2019]bbbbbbrsa
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
from base64 import b64encode as b32encode
from gmpy2 import invert,gcd,iroot
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex
import random
 
flag = "******************************"
 
nbit = 128
 
p = getPrime(nbit)
q = getPrime(nbit)
n = p*q
 
print p
print n
 
phi = (p-1)*(q-1)
 
e = random.randint(50000,70000)
 
while True:
    if gcd(e,phi) == 1:
        break;
    else:
        e -= 1;
 
c = pow(int(b2a_hex(flag),16),e,n)
 
print b32encode(str(c))[::-1]

这道题e的大致范围已经给出,可以尝试爆破

 

不过加密脚本的第一行有点坑

1
from base64 import b64encode as b32encode

(应该是出题人故意)把人误导成base32解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/python
import gmpy2
from Crypto.Util.number import long_to_bytes
import base64
p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
q = n//p
phi = (p-1)*(q-1)
c = '==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM'
c = int(str((base64.b64decode(c[::-1])))[2:-1])
 
for e in range(50000,70000):
    if gmpy2.gcd(e,phi) == 1:
            d = gmpy2.invert(e,phi)
            m = gmpy2.powmod(c,d,n)
            try:
                print(long_to_bytes(m).decode())
            except:
                continue

题目2:[BJDCTF2020]RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import getPrime,bytes_to_long
 
flag = open("flag","rb").read()
 
p = getPrime(1024)
q = getPrime(1024)
assert(e<100000)
n = p*q
m = bytes_to_long(flag)
c = pow(m,e,n)
print c,n
print pow(294,e,n)
 
p = getPrime(1024)
n = p*q
m = bytes_to_long("BJD"*32)
c = pow(m,e,n)
print c,n

也是对e爆破,不过我们可以通过这道题来对比pow()函数和gmpy2.powmod()的速度
pow:

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
import libnum
import gmpy2
from Crypto.Util.number import long_to_bytes
 
n = 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
c1 = 381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
 
for e in range(10000000000):
    if e % 1000 == 0:
        print(e)
    if c1 == pow(294,e,n):
        print("found")
        print(e)
        break
 
n2 = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
p = gmpy2.gcd(n,n2)
q = n//p
 
#e = 52361
phi = (q-1) * (p-1)
c = 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
d = libnum.invmod(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
用时信息:

3.03s user 0.01s system 99% cpu 3.050 total

 

gmpy2.powmod

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
import gmpy2
from Crypto.Util.number import long_to_bytes
 
n = 13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
c1 = 381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
 
for e in range(10000000000):
    if e % 1000 == 0:
        print(e)
    if c1 == gmpy2.powmod(294,e,n):
        print("found")
        print(e)
        break
n2 = 12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
p = gmpy2.gcd(n,n2)
q = n//p
 
#e = 52361
phi = (q-1) * (p-1)
c = 12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
print(long_to_bytes(m))
用时信息:

1.30s user 0.00s system 99% cpu 1.310 total

 

可以看到,gmpy2中的powmod()函数用时不到pow()函数的二分之一,所以以后优先使用gmpy2.powmod()函数

题目3:[RoarCTF2019]babyRSA

1
2
3
4
5
6
A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
p=next_prime(z*x*y)
q=next_prime(z)
A =  2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n =  117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c =  41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128

解题:

题目给出了A和p,q的关系,一通花里胡哨的运算之后得到A

 

以我已知的知识想不到什么好的算法

 

不过可以直接分解n得到p和q

 

当我们做完这些后,发现题目并没有告知e,盲猜e = 65537,结果正好是

 

当然平时做题我们还是严谨一点,尝试爆破e

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/python
import gmpy2
from Crypto.Util.number import *
 
q = 842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569
p = 139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183
c =  41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128
n = q*p
phi = (q-1) * (p-1)
 
for e in range(1,100000):
    if e % 1000 == 0:
        print(e)
    if isPrime(e):
        try:
            d = gmpy2.invert(e,phi)
            m = gmpy2.powmod(c,d,n)
            m = str(long_to_bytes(m))
            if "{" in m and "}" in m and "CTF" in m:
                print(m)
                break
        except:
            continue

关于e = 65537的说明

NIST SP800-78 Rev 1 (2007) 曾强调“不允许使用比65537更低的公钥指数e”，但PKCS#1却从未有过类似的建议。e=65537=(2^16+1)，其签名/加密运算只需要17次模乘，性能也算不错。65537可以在安全上和性能上做出一个很好的平衡,因此大多数加密的e都默认为65537

对于e未知的题型的总结:

可以优先尝试e == 65537,不行再爆破

3.已知p和q的最小公倍数

题目:[NPUCTF2020]EzRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from gmpy2 import lcm , powmod , invert , gcd , mpz
from Crypto.Util.number import getPrime
from sympy import nextprime
from random import randint
p = getPrime(1024)
q = getPrime(1024)
n = p * q
gift = lcm(p - 1 , q - 1)
e = 54722
flag = b'NPUCTF&#123;******************&#125;'
m = int.from_bytes(flag , 'big')
c = powmod(m , e , n)
print('n: ' , n)
print('gift: ' , gift)
print('c: ' , c)
 
#n:  17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
#gift:  2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104
#c:  3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319

解题:

已知n = q

 

gift = lcm(q-1,p-1)
= (q-1)*(p-1) // gcd(q-1,p-1)

 

又因为(q-1)*(p-1) 约等于 q*p = n

 

gift 约等于 n // gcd(q-1,p-1)

 

于是可以得出gcd(q-1,p-1) 约等于 n // gift

 

于是得出gcd(q-1,p-1)约等于8

 

设k = gcd(q-1,p-1) ( k 约等于8,于是爆破k的取值范围为0<k<10)

 

最后得到q,p,e,又由于gcd(e,phi) != 1

 

于是:
new_e = e//2
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
m = gmpy2.iroot(m,2)[0]
m = long_to_bytes(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
25
26
27
#!/usr/bin/python
import gmpy2
from gmpy2 import lcm , powmod , invert , gcd , mpz
from Crypto.Util.number import *
 
n = 17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121 # q * p
gift = 2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104 # lcm((q-1),(p-1)) == (q-1) * (p-1)
c = 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
 
for k in range(1,10):
    tmp = gift * k - 1                   # q*p - (p+q)
    q__p = n - tmp                       #q+p
    q_p = pow(q__p,2) -4*n               #(q-p) ^ 2
    if q_p < 0 :
        q_p = - q_p
    if gmpy2.iroot(q_p,2)[1]:
        q_p = gmpy2.iroot(q_p,2)[0]
        q = (q_p+q__p) //2
        p = q__p - q
 
e = 54722
e = e//2
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
m = gmpy2.iroot(m,2)[0]
print(long_to_bytes(m))

最后两道综合题:

1.[De1CTF2019]babyrsa

题目:

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
import binascii
from data import e1,e2,p,q1p,q1q,hint,flag
 
n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423L, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421L, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303L, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791L]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569L, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031L, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446L, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797L]
f=lambda m,e,n,c:pow(m,e,n)==c
assert(sum(map(f,[p]*4,[4]*4,n,c))==4)
 
ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
assert(pow(e1,ee1,n)==ce1)
assert(pow(e2+tmp,ee2,n)==ce2)
 
e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
hint=int(binascii.hexlify(hint),16)
assert(q1p*q1q==n)
assert(q1p<q1q)
assert(c==pow(hint,e,n))
 
flag=int(binascii.hexlify(flag),16)
q1=q1p
q2 =  114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
assert(c1==pow(flag,e1,p*q1))
assert(c2==pow(flag,e2,p*q2))

解题:

本题过程大致可以分为三部分:

  • 解得e1和e3

  • 解得hint和q1

  • 解得flag

1.解得e1和e3

通过这两句断言:

1
2
3
4
5
6
7
8
ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
assert(pow(e1,ee1,n)==ce1)
assert(pow(e2+tmp,ee2,n)==ce2)

可以建立两个方程,由于两个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
30
31
32
#!/usr/bin/python
import gmpy2
 
ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
  ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
  n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
  tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
 
  #--------find e1--------
  for k in range(200000000):
      c = k*n + ce1
      if gmpy2.iroot(c,ee1)[1]:
          e1 = gmpy2.iroot(c,ee1)[0]
          break
 
  #--------check e1------
  if ce1 == gmpy2.powmod(e1,ee1,n):
      print("e1 = %d"%e1)
 
  #--------find e2--------
  for k in range(1000000):
      c = k*n + ce2
      if gmpy2.iroot(c,3)[1]:
          m = gmpy2.iroot(c,3)[0]
          e2 = m - tmp
          break
 
  #--------check e2------
  if ce2 == gmpy2.powmod((e2+tmp),3,n):
      print("e2 = %d"%e2)

解的e1,e2

1
2
e1 = 15218928658178
e2 = 381791429275130

2.解的hint和q1

1
2
3
4
5
6
7
e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
hint=int(binascii.hexlify(hint),16)
assert(q1p*q1q==n)
assert(q1p<q1q)
assert(c==pow(hint,e,n))

一个常规的rsa加密,没有明显的缺陷,尝试分解n

1
factordb n

得到两个质数

1
2
q1p = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
q1q = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088835693

常规的分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/python
import gmpy2
e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
q = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
p = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088835693
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
 
assert p*q == n
 
phi = (p-1) * (q-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
if q < p :
    print(q)
else:
    print(p)

得到完全没用的hint,但是得到了对第三步很有用的q1

3.解得flag

1
2
3
4
5
6
7
flag=int(binascii.hexlify(flag),16)
q1=q1p
q2 =  114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
assert(c1==pow(flag,e1,p*q1))
assert(c2==pow(flag,e2,p*q2))

乍一看似乎很简单,连n都已经分解好了(这让我想起了NCTF的easyRSA)

 

一测试,果然gcd(e1,phi1) == gcd(e2,phi2) == 14

 

既然到这里了,就总结一下e和phi不互素时的解法(下次)

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
#!/usr/bin/python
import gmpy2
import math
from Crypto.Util.number import long_to_bytes
from functools import reduce
 
 
e1 = 15218928658178
e2 = 381791429275130
q1 = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
p = 109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453
q2 =  114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
 
c1 =  262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 =  7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
 
 
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
 
tmp = 14
phi1 = (p-1) * (q1-1)
phi2 = (p-1) * (q2-1)
e1 = e1 // tmp
e2 = e2 // tmp
d1 = gmpy2.invert(e1,phi1)
d2 = gmpy2.invert(e2,phi2)
 
c1=gmpy2.powmod(c1,d1,p*q1)%q1
c2=gmpy2.powmod(c2,d2,p*q2)%q2
 
n = [q1,q2]
c = [c1,c2]
 
 
data = list(zip(c,n))
last = CRT(data)
 
e = 7
phi = (q1-1) * (q2-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(last[0],d,last[1])
m = gmpy2.iroot(m,2)[0]
print(long_to_bytes(m))

2. [QCTF2018]Xman-RSA

题目:

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
gqhb jbkl2 pbkhqw pt_kqpbd
gqhb ht pbkhqw zqreahb
pbkhqw urtd64
 
adg ulwdt_wh_ezb(u):
    qdwzqe pew(u.dexhad('mdi'), 16)
 
adg ezb_wh_ulwdt(e):
    u = mdi(e)[2:-1]
    u = '0' + u pg yde(u)%2 == 1 dytd u
    qdwzqe u.adxhad('mdi')
 
adg jdw_r_kqpbd(y):
    qreahb_tdda = zqreahb(y)
 
    ezb = ulwdt_wh_ezb(qreahb_tdda)
 
    fmpyd Tqzd:
        pg pt_kqpbd(ezb):
            uqdrv
        ezb+=1
    qdwzqe ezb
 
adg dexqlkw(t, d, e):
    k = ulwdt_wh_ezb(t)
    k = khf(k, d, e)
    qdwzqe ezb_wh_ulwdt(k).dexhad('mdi')   
 
adg tdkrqrwd(e):
    k = e % 4
    w = (k*k) % 4
    qdwzqe w == 1
 
g = hkde('gyrj.wiw', 'q')
gyrj = g.qdra()
 
btj1 = ""
btj2 = ""
ghq p pe qrejd(yde(gyrj)):
    pg tdkrqrwd(p):
        btj2 += gyrj[p]
    dytd:
        btj1 += gyrj[p]
 
k1 = jdw_r_kqpbd(128)
k2 = jdw_r_kqpbd(128)
k3 = jdw_r_kqpbd(128)
e1 = k1*k2
e2 = k1*k3
d = 0i1001
x1 = dexqlkw(btj1, d, e1)
x2 = dexqlkw(btj2, d, e2)
kqpew(x1)
kqpew(x2)
 
d1 = 0i1001
d2 = 0i101
k4 = jdw_r_kqpbd(128)
k5 = jdw_r_kqpbd(128)
e3 = k4*k5
x1 = ezb_wh_ulwdt(khf(e1, d1, e3)).dexhad('mdi')
x2 = ezb_wh_ulwdt(khf(e1, d2, e3)).dexhad('mdi')
kqpew(x1)
kqpew(x2)
 
kqpew(urtd64.u64dexhad(ezb_wh_ulwdt(e2)))
kqpew(urtd64.u64dexhad(ezb_wh_ulwdt(e3)))

解题:

从密文形式可以看出是用的python编写的加密脚本,不过这个脚本又被再次加密,猜想应该是纺射加密,从中挑选了两端话来对比得出a和b

1
2
gqhb jbkl2 pbkhqw
from xxxxx import
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/python
 
#-------------data---------------
#
#   c   :  6 16 7 1 -2 15 1 10 7 16 22
#   m   :  5 17 14 12 -2 8 12 15 14 17 19
 
#---------get encode  a and b---------
for a in range(30):
    for b in range(30):
        if (a*5 + b) % 26 == 6 :
            if (17 * a + b) % 26 == 16 :
                if (14*a + b) % 26 == 7:
                    print(a)
                    print(b)

得出a = 3, b = 17

 

纺射解密后得到加密脚本,如下

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
from gmpy2 import is_prime
from os import urandom
import base64
 
def bytes_to_num(b):
        return int(b.encode('hex'), 16)
 
def num_to_bytes(n):
        b = hex(n)[2:-1]
        b = '0' + b if len(b)%2 == 1 else
        return b.decode('hex')
 
def get_a_prime(l):
        random_seed = urandom(l)
 
        num = bytes_to_num(random_seed)
 
        while True:
                if is_prime(num):
                        break
                num+=1
        return num
 
def encrypt(s, e, n):
        p = bytes_to_num(s)
        p = pow(p, e, n)
        return num_to_bytes(p).encode('hex')
 
def separate(n):
        p = n % 4
        t = (p*p) % 4
        return t == 1
 
f = open('flag.txt', 'r')
flag = f.read()
 
msg1 = ""
msg2 = ""
for i in range(len(flag)):
        if separate(i):
                msg2 += flag[i]
        else:
                msg1 += flag[i]
 
p1 = get_a_prime(128)
p2 = get_a_prime(128)
p3 = get_a_prime(128)
n1 = p1*p2
n2 = p1*p3
e = 0x1001
c1 = encrypt(msg1, e, n1)
c2 = encrypt(msg2, e, n2)
print(c1)
print(c2)
 
e1 = 0x1001
e2 = 0x101
p4 = get_a_prime(128)
p5 = get_a_prime(128)
n3 = p4*p5
c1 = num_to_bytes(pow(n1, e1, n3)).encode('hex')
c2 = num_to_bytes(pow(n1, e2, n3)).encode('hex')
print(c1)
print(c2)
 
print(base64.b64encode(num_to_bytes(n2)))
print(base64.b64encode(num_to_bytes(n3)))

进入了rsa解题过程,我们先看最后一个加密,相同的明文,相同的n,不同的e

 

用共模攻击解出n1来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/python2
#coding:utf-8
 
import gmpy2
from Crypto.Util.number import long_to_bytes
 
e1 = 0x1001
e2 = 0x101
n = 9895571060693703887018268413746107679094703478067972087862851570192520012058188062485476484700707994684397704099884436398099581319015589480235346899990863625919087077906193223937343450727301243043576326163300258770936289423785376338765758863453745278516208013244068358484113062931878984339475569902332075509121153749576470546863477142562563573654198332099438611713385318497180237117792417826080724886477023904678472464557511959911739272258202310963925049222305927992349171516332320267610895787011879250778522843808895509894741144901052000573058315131265960606119769594234837973757057319170067823816025499647517874841
c1 = 0x2639c28e3609a4a8c953cca9c326e8e062756305ae8aee6efcd346458aade3ee8c2106ab9dfe5f470804f366af738aa493fd2dc26cb249a922e121287f3eddec0ed8dea89747dc57aed7cd2089d75c23a69bf601f490a64f73f6a583081ae3a7ed52238c13a95d3322065adba9053ee5b12f1de1873dbad9fbf4a50a2f58088df0fddfe2ed8ca1118c81268c8c0fd5572494276f4e48b5eb424f116e6f5e9d66da1b6b3a8f102539b690c1636e82906a46f3c5434d5b04ed7938861f8d453908970eccef07bf13f723d6fdd26a61be8b9462d0ddfbedc91886df194ea022e56c1780aa6c76b9f1c7d5ea743dc75cec3c805324e90ea577fa396a1effdafa3090
c2 = 0x42ff1157363d9cd10da64eb4382b6457ebb740dbef40ade9b24a174d0145adaa0115d86aa2fc2a41257f2b62486eaebb655925dac78dd8d13ab405aef5b8b8f9830094c712193500db49fb801e1368c73f88f6d8533c99c8e7259f8b9d1c926c47215ed327114f235ba8c873af7a0052aa2d32c52880db55c5615e5a1793b690c37efdd5e503f717bb8de716303e4d6c4116f62d81be852c5d36ef282a958d8c82cf3b458dcc8191dcc7b490f227d1562b1d57fbcf7bf4b78a5d90cd385fd79c8ca4688e7d62b3204aeaf9692ba4d4e44875eaa63642775846434f9ce51d138ca702d907849823b1e86896e4ea6223f93fae68b026cfe5fa5a665569a9e3948a
_, r, s = gmpy2.gcdext(e1, e2)
 
m = pow(c1, r, n) * pow(c2, s, n) % n
 
print m

对于倒数第二段加密,通过这两句代码

1
2
n1 = p1*p2
n2 = p1*p3
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
#!/usr/bin/python
import gmpy2
from Crypto.Util.number import long_to_bytes,isPrime
n1 = 2499586809914462821807624371088011200618603528498132509598946284572455726453497171635086810524607288333625665025664872216634366700044105279185519761587818169021167370991396691510275499486673922916370294043072503635630922980240462022218565365191228535222150496387990987123639567257124081274667568443678527637259644488779394704508217357758791670308548246801142468699716221789070607334747835552167450340441488756779323653879402176647890584656379628685893686585469918686253137796663587854943386347039389769790329948165162483370187914412810153613198247569427480466488647563900948387020677830797976534568626241686906738179
n2 = 7741603029707932330739678982394275613217057249691533148704382574439895657047911501600910571360188397109729289277796711334388156202412769743785164713243932001078475541271281825859671767783178037363138683152051263779907568124470598237502689045677891605285193637790880045372303913424654655825837641694318544209980415256180296972066060073206323473960669679401950151966003026531573962072358852304635671658878866030003484715256388556599713638695448516673643703041094737763957937855870992247472296348887788212823714735080211059688680618314050267995177478035769912691185787944037050674163079867101586607780761245261558200843
n3 = 9895571060693703887018268413746107679094703478067972087862851570192520012058188062485476484700707994684397704099884436398099581319015589480235346899990863625919087077906193223937343450727301243043576326163300258770936289423785376338765758863453745278516208013244068358484113062931878984339475569902332075509121153749576470546863477142562563573654198332099438611713385318497180237117792417826080724886477023904678472464557511959911739272258202310963925049222305927992349171516332320267610895787011879250778522843808895509894741144901052000573058315131265960606119769594234837973757057319170067823816025499647517874841
c1 = 0x1240198b148089290e375b999569f0d53c32d356b2e95f5acee070f016b3bef243d0b5e46d9ad7aa7dfe2f21bda920d0ac7ce7b1e48f22b2de410c6f391ce7c4347c65ffc9704ecb3068005e9f35cbbb7b27e0f7a18f4f42ae572d77aaa3ee189418d6a07bab7d93beaa365c98349d8599eb68d21313795f380f05f5b3dfdc6272635ede1f83d308c0fdb2baf444b9ee138132d0d532c3c7e60efb25b9bf9cb62dba9833aa3706344229bd6045f0877661a073b6deef2763452d0ad7ab3404ba494b93fd6dfdf4c28e4fe83a72884a99ddf15ca030ace978f2da87b79b4f504f1d15b5b96c654f6cd5179b72ed5f84d3a16a8f0d5bf6774e7fd98d27bf3c9839
c2 = 0x129d5d4ab3f9e8017d4e6761702467bbeb1b884b6c4f8ff397d078a8c41186a3d52977fa2307d5b6a0ad01fedfc3ba7b70f776ba3790a43444fb954e5afd64b1a3abeb6507cf70a5eb44678a886adf81cb4848a35afb4db7cd7818f566c7e6e2911f5ababdbdd2d4ff9825827e58d48d5466e021a64599b3e867840c07e29582961f81643df07f678a61a9f9027ebd34094e272dfbdc4619fa0ac60f0189af785df77e7ec784e086cf692a7bf7113a7fb8446a65efa8b431c6f72c14bcfa49c9b491fb1d87f2570059e0f13166a85bb555b40549f45f04bc5dbd09d8b858a5382be6497d88197ffb86381085756365bd757ec3cdfa8a77ba1728ec2de596c5ab
p1 = gmpy2.gcd(n1,n2)
p2 = n1//p1
p3 = n2//p1
 
assert isPrime(p1)
assert isPrime(p2)
assert isPrime(p3)
 
e = 0x1001
phi1 = (p1-1) * (p2-1)
phi2 = (p1-1) * (p3-1)
 
d1 = gmpy2.invert(e,phi1)
d2 = gmpy2.invert(e,phi2)
 
m1 = gmpy2.powmod(c1,d1,n1)
m2 = gmpy2.powmod(c2,d2,n2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))

解出两组明文,最后通过栅栏解密得到flag


[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

最后于 2020-10-29 19:39 被happi0编辑 ，原因：
收藏
点赞・8
打赏
分享
最新回复 (6)
八岛
雪    币： 871
活跃值： (627)
能力值： ( LV6，RANK：80 )
在线值：
发帖
回帖
粉丝
私信
八岛 1 2020-10-29 19:39
2 楼
0
大佬，关于p-adic 和随机数生成器有啥好的教程或者书籍推荐吗
I0gan
雪    币： 205
能力值： ( LV1，RANK：0 )
在线值：
发帖
回帖
粉丝
私信
I0gan 2020-10-29 23:19
3 楼
0
happi0师傅，写得好详细，学到了许多，以后记得多多写相关的文章，学学新姿势。。。。:）
VEhl
雪    币： 360
活跃值： (106)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
VEhl 2020-11-5 21:31
4 楼
0
mark，学到了很多，感谢感谢，希望能够看到更多类似的文章
1nt3
雪    币：
能力值： ( LV1，RANK：0 )
在线值：
发帖
回帖
粉丝
私信
1nt3 2020-11-5 21:32
5 楼
0
大佬写的好详细呀
happi0
雪    币： 75
活跃值： (842)
能力值： ( LV4，RANK：50 )
在线值：
发帖
回帖
粉丝
私信
happi0 1 2020-11-5 21:57
6 楼
0
八岛 大佬，关于p-adic 和随机数生成器有啥好的教程或者书籍推荐吗
《密码学随机数发生器的设计与分析》,这本书不错
sistttt
雪    币： 20
能力值： ( LV1，RANK：0 )
在线值：
发帖
回帖
粉丝
私信
sistttt 2021-7-4 00:14
7 楼
0
https://github.com/Ganapati/RsaCtfTool 
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回