N1key's Blog

RSA常见攻击

 密码学习笔记  11 分钟

工具准备

工具和第三方库的安装教程请自行百度

  • python3.8环境： https://www.python.org/downloads/windows/

  • 大素数分解工具:

    • factordb在线分解：http://factordb.com/
    • win10 yafu-x64：https://sourceforge.net/projects/yafu/

  • python第三方库：

    • gmpy2
    • pycryptodome
    • libnum
    • sympy
    • rsa

公钥解析,签名加密

如果题目给了pem或者key后缀结尾的文件，用工具解析出n和e。或者可以用kali自带的Openssl从公钥文件中提取出n和e。

命令：openssl rsa -pubin -text -modulus -in key.pem

例题：

BUURSA： https://buuoj.cn/challenges#RSA

公钥文件

-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMAzLFxkrkcYL2wch21CM2kQVFpY9+7+
/AvKr1rzQczdAgMBAAE=
-----END PUBLIC KEY-----

在线网站解析公钥： http://ctf.ssleye.com/

得到n和e之后，用factordb： http://factordb.com/

分解模n，得到p,q的值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import rsa            #rsa模块
from gmpy2 import*    #gmpy2模块

e= 65537
n= 86934482296048119190666062003494800588905656017203025617216654058378322103517
p= 285960468890451637935629440372639283459
q= 304008741604601924494328155975272418463

#求私钥d
'''
phi = (p-1)*(q-1)
d = invert(e,phi)     #gmpy2.invert(),用来求模逆的方法
print(d)
'''
d= 81176168860169991027846870170527607562179635470395365333547868786951080991441


key = rsa.PrivateKey(n,e,d,q,p)         #在pkcs标准中,pkcs#1规定,私钥包含(n,e,d,p,q)

with open("C:\\Users\\MIKEWYW\\Desktop\\flag.txt","rb") as f:  #以二进制读模式，读取密文  
    f = f.read()
    print(rsa.decrypt(f,key))           # f:公钥加密结果  key:私钥

例题：2020西湖论剑BrokenSystems

题目

BrokenSystems.py

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

public.txt

-----BEGIN PUBLIC KEY-----
MIICITANBgkqhkiG9w0BAQEFAAOCAg4AMIICCQKCAQEAwgdFIj/1uUss2EEhZvco
iiHyGH4aQhRTkYyrA8gCU0USM+sb3CNjdEIoqoaUqMLLyDP4Dd9AgxpokBsjC4Pz
8P7Uty0LlCteld7ayNzABHoq+5DIHtctOtSbcvyL0NMWfd2qarUWfAWN82rxkLIW
CFu9nWIfm9I6CT5OPZzDh7YnTywznIjhstkIrLM/TiDmR6vuBxSjzORkbolilLeB
A9zJpNt+1oEWTG5sx/0zR24XSmxwcDeyUEkTZfnw63auq6B9svZi2IBIr5jIjHbG
cQ25ZY1J/KDK8fXNmdwH8YhDK0j4VXEWitEPyCS3toK61sql0S/28EySeGtzirGb
twKCAQAdLS8fFz+BzzaP7AbUDUf9kvhhXBLuwUFo8ohCeVK4z1pTj3C6M0G2oXOu
gDdalrDThNlyKxkUn3iUc3Xgoz315pPtq9Xk1Ez/qeUl6gFPP6SZtfeymyGdkLiN
pVquOghjczjXvtBW467Fdb5Wu95TSzVaLndX23rsqW541n8hUwt8PsJKxh+bR0qy
gyIN2VRRNdBlpyTOL49E4y5GDu9fmVgAnFivWVGT135ywl8MsBUFuZPBNTKLEbUA
3KvJVckXf4Od0ENYbiWjEzXn1UN9yebNbU6+yyk34WAmwnkuF0X0Tu1UEb6qtV7Q
kF25GYy9QxERvodGL0Y2njHRpGE/
-----END PUBLIC KEY-----

message.txt

'Ω?奟?ypG睉晜< U,.
W?盔敲m銖?.嗘7?s来薶 
只Z???'D?夞%莰}?~a,妄姷槢谏v}玊??#ad??$ 爝湆鄃 
0遀; 
#缮刜2?顪娪k+需?捨HD篹枒筡婌 辆 赅?跌婊	CD瓦?3?h¬?V?p琙|
黡UU沯?酟讵分b澾硲€}?~QJ?绫摪	偑鳕塖
?I骟?费JB_?O0&?髀
SxN岑y?

解题思路

首先进行公钥解析得到 n，e的值：

n = 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
e = 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583

我们可以看出，e的值特别大。尝试winner攻击，解得 d。(winner攻击在后面低解密指数攻击会详细介绍)

这时发现我们已知了n, e , d；但N不能直接分解，这里涉及到一个解密算法
已知n, e , d，求P,Q
https://www.di-mgt.com.au/rsa_factorize_n.html


得到n，e，d，p，q的值后，通过分析加密代码我们可以知道这里 涉及Crypto.Cipher.PKCS1_OAEP 和 Crypto.PublicKey.RSA 的加密协议

Crypto的官方学习源文件 https://pythonhosted.org/pycrypto/Crypto-module.html


Python3解密脚本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

n = 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
e = 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583
d = 1779217788383673416690068487595062922771414230914791138743960472798057054853883175313487137767631446949382388070798609545617543049566741624609996040273727
p = 149604112324264915811376746906108325951188179904814259006959765070266946659481820938211689946210254302179197289522748397160602946376246768419310765669852537378426700376878745285639531531077237124655345323906476180103106894642043615024716862503414785057646920410083538192951872861366496901158348770066798098371
q = 163724217068973025857079545677048587508164102644298632911494474022224582218067057349189211462632427829087720476013052665037199232658015194718500750961261016558605363103092187533086949903145449057015220561698195502163792192055762108803714387175594231859738263839090338762578040513451585421537323416472060788989

key=RSA.construct((n, e, d, p, q))
cipher = PKCS1_OAEP.new(key)

with open("C:\\Users\\MIKEWYW\\Desktop\\message.txt","rb") as f:  #以二进制读模式，读取密文  
    f = f.read()
    flag = cipher.decrypt(f)
    print(flag)

代码中有看不懂的地方，如果是关于第三方库模块的，请认真学习一下上面的Crypto的官方学习源文件

利用公约数求解

如果两次公钥的加密过程中使用的 n1 和 n2 具有相同的素因子，则可以利用欧几里得算法直接将 n1 和 n2 分解

p = gmpy2.gcd(n1,n2)   #gmpy2库函数gcd(),用于求最大公约数。

自定义函数gcd()欧几里得算法

def gcd(a,b):
    if a<b:
        a,b = b,a
    while(b!=0):
        temp = a%b
        a = b
        b = temp
    return a

对于欧几里得算法的时间复杂度，即便是4096bit级别的也是秒破级别。

分解 N 得到多个相同的 P

知识点：

1.欧拉函数的性质：

p为素数，$n = p ^ a$ 所以 $φ(n) = (p-1) * p ^ {a-1} = p ^ a - p ^ {a-1}$


2.RSA加密公式：

$n = p*q$，$φ(n) = (p-1) * (q-1)$

$e*d ≡ 1$ mod $φ(n)$，$C ≡ m^e$ mod $n$

$m ≡ C^d$ mod $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

import gmpy2  
import random  
from Crypto.Util.number import *  
from flag import flag  
  
def generate_key(1024):  
    p = getPrime(1024)  
    r = random.randint(2, 10)  
    s = random.randint(r, 1024)  
	    while True:  
	        e = random.randint(3, p**r*(p-1))  
	        if gmpy2.gcd(e, p**s*(p-1)) == 1:  
	            break  
	    pubkey = (long(e), long(p**r))   #返回e  和p^r  
	    return pubkey  
	  
def crypt(msg, pubkey):  
    e, n = pubkey                            #e  n=p^r  
    m = bytes_to_long(msg)      
    assert m < n - 1  
    enc = pow(m, e, n)         
    return long_to_bytes(enc)  
  
nbit = 1024  
pubkey = generate_key(1024)  
print 'pubkey =', pubkey                    #输出e  和p^r  
msg = flag值     
enc = crypt(msg, pubkey)    
  
print 'enc =\n', enc.encode('base64')

解题思路：

通过分析加密脚本，我们可以知道：

已知e, $n=p^r$ , enc的值了。

由欧拉函数的性质可以得到：phi=$φ(n)=(p-1)*p^{r-1}=p^r-p^{r-1}$

  1. 要求得 $m=c^d$ mod $n$ ,则先求d。

  2. 由于 $e*d=1$ mod $φ(n)$，求得d，则先求φ(n)

  3. 题目给的是 $n=p^r$ ,所以先要分解n以获得p和r的值。

dp、dq 泄露

知识点：

攻击条件：

已知p，q，dp，dq，c

关系公式：

$$\begin{cases} \ dp≡d mod (p-1) \\ \ \\ \ dq≡d mod (q-1) \\ \end{cases}$$

解密公式：

  1. $m_1=c^{dp}$ mod $p$
  2. $m_2=c^{dq}$ mod $q$
  3. $m=(((m_1-m_2)*I)$$mod$ $p)*q+m_2$
  4. I:乘法逆元，I=invert(q,p)

解密数学原理：

利用中国剩余定理可得： $m_1≡c^d$ mod $p$，$m_2≡c^d$ mod $q$

证明：

由 $m≡c^d$ mod $n$,得 $m=c^d+k*n$

因为 $n = p * q$ ,所以 $m = c ^ d + k * p * q$

上述公式中，同时取余p和q，可分别得到： $m_1≡c^d$ mod $p$，$m_2≡c^d$ mod $q$

所以 $c ^ d = m_1 + k * p$ ，代入 $m_2 ≡ c ^ d$ mod $q$ 可得：$m_2 ≡ (m_1 + k * p)$ mod $q$

等式两边同时减去 $m_1$，可以得到：$(m_2-m_1)≡(k*p)$ mod $q$

这里因为gcd(p,q)=1 ,所以可以得到p的逆元，得：$(m_2-m_1)*p^{-1}≡k$ mod $q$ ($p^{-1}$ 表示p的逆元，可用gmpy2.invert(q,p)函数求得)

即：$k≡(m_2-m_1)*p^{-1}$ mod $q$

由$k ≡ (m_2 - m_1) * p ^ {-1}$ mod $q$ 和 $c ^ d = k * p + m_1$

$\begin{cases} k≡(m_2-m_1)*p^{-1} mod q\\ c^d=k*p+m_1\\ \end{cases}$

可得到：

$c^d=((m_2-m_1)*p^{-1}$ mod $q)*p+m_1$


代入$m≡c^d$ mod $n$得：
$m≡(((m_2-m_1)*p^{-1}$ mod $q)*p+m_1)$ mod $n$

例题：

BUURSA1 

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

from gmpy2 import*
from libnum import*

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
#n=p*q

I = invert(q,p)            #求p的逆元
mp = pow(c,dp,p)           #求幂取模运算
mq = pow(c,dq,q)           #求幂取模运算

m = (((mp-mq)*I)%p)*q+mq   #求明文公式
#m = m%n(可以加上，不加也没事，这里数值不大)
print(n2s(m))              #n2s()函数，用于数值转字符串

dp 泄露

知识点：

攻击条件：

已知e，n，dp，c

关系公式：

dp≡d mod (p-1)

$φ(n) = (p-1) * (q-1)$

$d*e≡1$ mod $φ(n)$

$m≡c^d$ mod $n$

解密数学原理：

思路：

1.破解m的关键在于获取到d
利用gmpy2库，d=gmpy2.invert(e,φ(n))
2.由$φ(n)=(p-1)*(q-1)$ ，dp≡d mod (p-1)

可得到(p-1),进而得到p,q因为n已知,n=p*q
证明：

$dp * e ≡ d * e$ mod $(p-1)$
推导：$ed=k_2(p-1)+dp*e$ $(k_2为整数)$

由$e*d≡1$ mod $(p-1)(q-1)$ 得 $ed=k_1(q-1)(p-1)+1$

所以：$k_1(q-1)(p-1) + 1 = k_2(p-1) + dp * e$
推导得：$(p - 1)(k_1(q - 1) - k_2)+1 = dp * e$

令:$x=(k_1(q-1)-k_2)$，即$(p-1)x+1=dp*e$

因为 $dp<(p-1)$

所以 $e>x$

所以 $x∈(1,e)$

3.求出p后即可求出q，进而求得φ(n)，得到d
通过遍历x，可求出存在p，使得n % p=0

关键代码：

1
2
3
4
5
6
7
8

for i in range(1,e):                   #在范围(1,e)之间进行遍历
    if(dp*e-1)%i == 0:
        if n%(((dp*e-1)//i)+1) == 0:   #存在p，使得n能被p整除
            p=((dp*e-1)//i)+1
            q=n//(((dp*e-1)//i)+1)
            phi=(q-1)*(p-1)            #欧拉定理
            d=gmpy2.invert(e,phi)         #求模逆
            m=pow(c,d,n)               #快速求幂取模运算

例题：

BUURSA2

题目

1
2
3
4
5

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

解题脚本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from gmpy2 import*
from libnum import*

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

for i in range(1,e):                   #在范围(1,e)之间进行遍历
    if(dp*e-1)%i == 0:
        if n%(((dp*e-1)//i)+1) == 0:   #存在p，使得n能被p整除
            p=((dp*e-1)//i)+1
            q=n//(((dp*e-1)//i)+1)
            phi=(q-1)*(p-1)            #欧拉定理
            d=invert(e,phi)         #求模逆
            m=pow(c,d,n)               #快速求幂取模运算
print(n2s(m))       #16进制转文本

Roll 按行加密

例题：

BUU RSAROLL https://buuoj.cn/challenges#RSAROLL

解题思路：

由图二可知 N 和 e 的值。 把图二中的每行数据进行解密：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from gmpy2 import*
from libnum import*

n=920139713
p=18443
q=49891
e=19

phi = (q-1)*(p-1)
d=invert(e,phi)

m=""
with open("C:\\Users\\MIKEWYW\\Desktop\\BUURSA题目\\ROLL\\Data.txt","r")as f:
    for i in f.readlines():                #读取每一行
        m+=n2s(pow(int(i),d,n))            

print(m)

注意读取的密文数据要新建一个文本：只保留卷轴数据

共模攻击

知识点：

共模攻击，Common Modulus Attack,也称为同模攻击。同模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数n。

对于同一条明文m，新手小白A和B对其进行加密：
A: $C_1≡M^{e_1}$ mod $n$
B: $C_2≡M^{e_2}$ mod $n$

如果，此时有一个攻击者，同时监听了A和B接收到的密文$C_1,C_1$。因为模数不变，以及所有的公钥都是公开的，那么利用同模攻击，就可以在不知道$d_1,d_2$的条件下破解明文M

攻击条件：

已知 $n,e_1,e_2,c_1,c_2$

解密数学原理：

当n一定时，已知 $e_1,e_2,c_1,c_2$

假设 $e_1,e_2$ 互质，即 $gcd(e_1,e_2)=1$
此时有：$e_1s_1+e_2s_2=1$ (其中$s_1,s_2$为整数，且一正一负)

通过扩展欧几里得算法，我们可以得到上式的一组解($s_1,s_2$)

假设$s_1$为正数，$s_2$为负数

因为$c_1≡m^{e_1}$ mod $n$，$c_2≡m^{e_2}$ mod $n$
所以:

$(c_1^{s_1}c_2^{s_2})$ mod $n$
=(($m^{e_1}$ mod $n$)$^{s_1}$ *($m^{e_2}$ mod $n$)$^{s_2}$) mod $n$
$=((m^{e_1s_1+e_2s_2}) mod n) mod n$
(由$e_1s_1+e_2s_2=1$)

可得到：
$c_1^{s_1}c_2^{s_2} = m$ mod $n$

即：
$m = c_1^{s_1}c_2^{s_2}$ mod $n$


例题：

BUU RSA3

c1=22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
n=22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
e1=11187289
c2=18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e2=9647291

解题脚本：

from libnum import*   #python第三方库
from gmpy2 import*    #python第三方库

n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801
c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361
c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397
e1 = 11187289
e2 = 9647291

s = gcdext(e1,e2)    #gmpy2.gcdext(),扩展欧几里得算法，返回tuple元组，满足s[1]*e1+s[2]*e2=1

m = pow(c1,s[1],n)*pow(c2,s[2],n)%n   #获取明文m

print(n2s(m))

低加密指数攻击

e=3时的小明文攻击：

特点：e=3，m很小，n很大

  1. 当 e=3 时，如果明文过小，导致明文的三次方仍然小于n，那么通过直接对密文开三次方即可得到明文。

即：$C ≡ m^e$ mod $n$,如果e=3，且 $m^e < n$，则：$C = m^e$，$m = \sqrt[3]{C}$

2.如果明文的三次方比n大，但不是足够大，那么设k有： $C=m^e+k*n$

爆破$k$，如果 $C - k * n$ 或者 $C + k * n$ 能开三次根式，那么就可以直接得到明文。

关键代码

1
2
3
4
5
6

i=0
while 1:
    if(iroot(c+i*n,3)[1]==1):           #或者 iroot(c-i*n,3)
        print(iroot(c+i*n,3)[0])
        break
    i=i+1

例题：

BUU Dangerous RSA

https://buuoj.cn/challenges#Dangerous%20RSA

题目：

#n:  0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
#e:  0x3
#c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
so,how to get the message?

解题思路：

假设我们 $Ｍ ^ e$ / n 商 k 余数为c，

所以$Ｍ ^ e$ = $k * n$ + C，对K进行爆破，只要k满足 k*n + C能够开方就可以

解题脚本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from libnum import*   #python第三方库
from gmpy2 import*    #python第三方库

n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365

i=0
while 1:
    if(iroot(c+i*n,3)[1]==1):           #或者 iroot(c-i*n,3)
        print(n2s(iroot(c+i*n,3)[0]))
        break
    i=i+1

e=2时的小明文攻击：

e=2时，直接将密文C开平方获得解

由于e只有2，相当于把明文m平方而已，得到的C也比n小很多。尝试直接将C开根号看能否得到明文。

1
2
3
4
5
6
7
8

from libnum import*   #python第三方库
from gmpy2 import*    #python第三方库

c=......              #C的值
m=isqrt(c)            #开平方根
#m=iroot(c,2)[0]      #开C的二次方根

print(n2s(m))

e=1时的小明文攻击：

加密过程：

C≡m mod n ,明文与密文同模

所以有：m=C+n*k,爆破k

1
2
3
4
5
6
7
8
9

from libnum import*

n=....
c=....
max_num = 7   #设置遍历上限

for k in range(max_num):
    m = c + n*k
    print(n2s(m))

低加密指数广播攻击

背景：

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

适用条件：

模数n，密文C不同，明文m，加密指数e相同。（一般的话e=k，k是题目给出的n和c的组数）

例如：e=k=3

同余式组：

$\begin{cases} C_1≡m^e mod n_1\\ C_2≡m^e mod n_2\\ C_3≡m^e mod n_3\\ \end{cases}$

由中国剩余定理：

设$n_1,n_2,n_3$ 是两两互素的正整数，$M = n_1 * n_2 * n_3$
$M_i = \frac{M}{n_i}(i=1,2,3)$
则同余式组： $m^e≡C_i mod n_i(i=1,2,3)$

有唯一解： $m^e=X≡C_1M_1y_1+C_2M_2y_2+C_3M_3y_3$ $(mod$ $M)$
其中$(M_iy_i≡1$ mod $n_i，i=1,2,3)$

攻击代码

#python3，在$n_i$两两互质的情况下

 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

from gmpy2 import*
n1=...
n2=...
n3=...
c1=...
c2=...
c3=...
e=3

def CRT(a,n):
    sum = 0
    N = reduce(lambda x,y:x*y,n)   # ni 的乘积,N=n1*n2*n3

    for n_i, a_i in zip(n,a):    # zip()将对象打包成元组
        N_i = N // n_i           #Mi=M/ni
        sum += a_i*N_i*invert(N_i,n_i)   #sum=C1M1y1+C2M2y2+C3M3y3
    return sum % N 

n =[n1,n2,n3] 
c =[c1,c2,c3]

x = CRT(c,n)

m = iroot(x,e)[0]
print(n2s(m))

例题：

BUURSA4
https://buuoj.cn/challenges#RSA4

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
23
24
25
26
27
28
29
30
31
32
33
34

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

# 将5进制数转换为10进制数  int('',5)
N1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004',5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243',5)

N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114',5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344',5)

N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323',5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242',5)

e=3

n = [N1,N2,N3]
c = [c1,c2,c3]


def CRT(a,n):
    sum = 0
    N = reduce(lambda x,y:x*y,n)   # ni 的乘积,N=n1*n2*n3

    for n_i, a_i in zip(n,a):    # zip()将对象打包成元组
        N_i = N // n_i           #Mi=M/ni
        sum += a_i*N_i*invert(N_i,n_i)   #sum=C1M1y1+C2M2y2+C3M3y3
    return sum % N 

x = CRT(c,n)

m = iroot(x,e)[0]           #开e次方根
print(n2s(m))               #数值转字符串

低解密指数攻击

知识点：

与低加密指数相同，低解密指数可以加快解密的过程，但同时也带来了安全问题。Wiener表示如果满足：

$$d < \frac{1}{3}n^{\frac{1}{4}}$$

那么一种基于连分数（数论中的问题）的特殊攻击类型，就可以危害RSA的安全，此时需要满足： $$q < p < 2q$$


如果满足上述条件，通过Wiener Attack 可以在多项式时间中分解n。

下载工具：rsa-wiener-attack

github上有公开的攻击代码。

将解密的代码放入wiener-attack的目录下即可。

下载网址: https://github.com/pablocelayes/rsa-wiener-attack

低解密指数攻击的特点：

e看起来特别大就行，且n分解无望

例题：

BUU rsa2
https://buuoj.cn/challenges#rsa2

题目：

N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085

import hashlib
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"

解题步骤：

wiener攻击脚本用于求出d的值
（注意，这里要将攻击脚本和rsa-wiener-attack的py文件放在同一个目录下）


攻击脚本：

1
2
3
4
5
6
7

import  RSAwienerHacker
n = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085

d =  RSAwienerHacker.hack_RSA(e,n)
if d:
    print(d)

得到d后在python2的环境下对其进行MD5哈希即可得到flag

updatedupdated2022-06-032022-06-03

相关文章：