RSA基础

RSA原理

1.n = p * q n是模数 p和q都是素数，通过欧拉函数得到与n互素的个数φ(n)

2.欧拉数φ(n)=(p-1)*(q-1)

3.选择一个e，e的取值在(1,φ(n)),且e与φ(n)需要互素，不然无逆元得不到d,通常e取65537

4.求出e与φ(n)的模逆数d, e * d ≡ 1 mod φ(n)

加密解密

对明文进行加密，c = m^e mod n, 即 c= pow(m,e,n)

对密文进行解密，m = c^d mod n,即m = pow(c,d,n)

其中公钥为(e,n),私钥为(d,n)

解密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
import random
p=getPrime(1024)  #题目上所给的p和q
q=getPrime(1024)
c=''
e=65537
n=p*q
phi=(p-1)*(q-1)
d=int(gmpy2.invert(e,phi))
m=pow(c,d,n)
from Crypto.Util.number import *
print(long_to_bytes(m))

大N分解

分解N的办法：1.factordb.com 2.yafux-64.exe

题目中只给了n,e,c的值

首先进行n的分解得到两个素数p和q的值，此时我们已经p,q,e,c,n的值可以参考RSA原理进行解密了.

直接上脚本

1
2
3
4
5
6
7
8
9
from Crypto.Publickey import RSA
import libnum
with open("pubckey1.pem","rb") as f:
      key=RSA.import_key(f.read())     
      n=key.n
      e=key.e                          #生成和读取公钥
with open("flag.txt","rb") as f:
     c=f.read()                     #读取密文
     c=libnum.s2n(c)           #将密文转化为数字形式

共模攻击

题目会给出两组及以上的(n1 e1), （n2 e2) ....加密同一条明文m

如果e1和e2互素的话可用( gcd(e1,e2) = 1)，利用欧几里德算法(辗转相除法)

一定存在两个数s1,s2,使得gcd(e1,e2)=e1s1+e2s2=1,因为s1和s2都是整数，所以说s1和s2一正一负。

因为 c1 = m^e1 mod n c2 = m^e2 mod n 即pow(m,e1,n) pow(m,e2,n)

(c1^s1*c2^s2)%n=((m^e1%n)^s1(m^e2%n)^s2)%n =((m^e1%n)^s1%n*(m^e2%n)^s2%n)%n =((m^e1)^s1%n*(m^e2)^s2%n)%n =((m^e1)^s1*(m^e2)^s2)%n =((m^(e1*s1))*(m^(e2*s2)))%n =(m^(e1*s1+e2*s2))%n =m%n

即(c1^s1 * c2 ^s2)%n=m

因此，同一m，同一n，用不同的e进行加密，在不知道d的情况下可以通过共模攻击解密.

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import gmpy2
import libnum

c1=''
n=''
e1=''
c2=''
e2=''

def rsa_gong_N_def(e1,e2,c1,c2,n):
    e1, e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n)
    s = gmpy2.gcdext(e1, e2)
    s1 = s[1]
    s2 = s[2]
    if s1 < 0:
        s1 = - s1
        c1 = gmpy2.invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = gmpy2.invert(c2, n)
    m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n
    return int(m)

m = rsa_gong_N_def(e1,e2,c1,c2,n)
print(libnum.n2s(int(m)).decode())

dp和dq泄露

首先已知 dp ≡ d mod (p - 1) dq ≡ d mod (q -1 ) m = c^d mod n n = p * q ∵ m ≡ c^d mod n = c^d +k *p * q (k∈Z) m1 ≡ c^d mod p m2 ≡ c^d mod q c^d =m1 +t1*p 代入 m2 ≡ c^d mod q m2 ≡ m1 +t1*p +t2*q (t1,t2∈Z) m2 - m1 =t1*p + t2 *q =t1*p (mod q) ∵p,q 互素 (m2-m1)*p^-1 (mod q) (m2 - m1) ≡ t*p ( mod q) p^-1可利用gcd(p,q)=1,通过扩展欧几里德算法求出 t ≡ (m2 -m1)*p^ -1 (mod q) ∵c^d = m1 +t1 *p c^d = m1 +[(m2-m1)]* p ^-1 (mod q) mod n m = m1 +(m2 -m1)* p^-1(mod q)*p ∵ m1 ≡ c^d mod p dp ≡ d mod (p-1) m1 ≡ c^dp+s(p-1) mod p (s∈Z) c ≡ c^(p-1) ≡ 1 mod p (费马小定理) m1 ≡ c^dp mod p 同理得到 m2 ≡ c ^dq mod q

以上就是dp和dq泄露的原理

脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
c=''
dp=''
dq=''
p=''
q=''
e=65537
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
I=int(gmpy2.invert(p,q))
m = (((m1-m2)*I)%p)*q+m2
from Crypto.Util.number import *
print(long_to_bytes(m))

dp(dq)的泄露

dp(dq)泄露指单个泄露，原理如下:

dp=d%(p-1) 即dp=d mod (p-1) dp*e=d*e mod (p-1) 由于d*e≡1(mod(phi_n)) 所以dp*e+k*(p-1)=d*e dp*e+k*(p-1)≡1(mod(phi_n)) 由于phi_n=(p-1)*(q-1) 所以dp*e+k*(p-1)≡1(mod(p-1)*(q-1)) 即dp*e+k1*(p-1)=1+k2*(p-1)*(q-1) dp*e=(p-1)*[k2*(q-1)-k1]+1 此时设x=k2*(q-1)-k1 因为dp=d mod(p-1) 所以dp<(p-1) 即e>x dp*e=(p-1)*x+1 p=[(dp*e-1)//x]+1 这时x的范围为(1,65535) 可以for i in range(1,65535): p=[(dp*e-1)//x]+1 if n%p==0: q=n//p

脚本如下:

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

e = ''
n = ''
dp = ''

c = ''

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)  # 快速求幂取模运算
from Crypto.Util.number import *
print(long_to_bytes(m))

低解密指数攻击

一般e=3 （个别情况的时候e=2),也就是e很小的时候，可以直接选择开方

1.当m^e<n时c = m^e mod n c=m^e ,直接对c开e次方然后转字符串就可以

2.当m^e>n时，进行爆破 m^e = c + k*n 对 k进行爆破，当k*n+c能被e开次方即得到m

脚本如下

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

import gmpy2
from Crypto.Util.number import *
e=''
c=''
n=''
k=0
while True:
    m=k*n+c   #用遍历的方法解出k的值
    m,result=gmpy2.iroot(m,e)
    if result==True:
        break
    k=k+1
print(long_to_bytes(int(m)))

rabin

当e=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
25
26
27
import gmpy2

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

p = 65428327184555679690730137432886407240184329534772421373193521144693375074983
q = 98570810268705084987524975482323456006480531917292601799256241458681800554123
c = 0x4e072f435cbffbd3520a283b3944ac988b98fb19e723d1bd02ad7e58d9f01b26d622edea5ee538b2f603d5bf785b0427de27ad5c76c656dbd9435d3a4a7cf556
m = rabin_decrypt(c,p,q)
for i in range(4):
	try:
		print(bytes.fromhex(hex(m[i])[2:]))
	except:
		pass
    

# b'hgame{That'5_s0_3asy_to_s@lve_r@bin}'

已知e,d分解n

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

def divide_pq(e, d, n):
    k = e*d - 1
    while True:
        g = random.randint(2, n-1)
        t = k
        while True:
            if t % 2 != 0:
                break
            t //= 2
            x = pow(g, t, n)
            if x > 1 and gmpy2.gcd(x-1, n) > 1:
                p = gmpy2.gcd(x-1, n)
                return (p, n//p)


纳维攻击

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
import gmpy2
import libnum

def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf
def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0
    denominator = 1
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator
def solve_pq(a, b, c):
    """使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
    :param a:x^2的系数
    :param b:x的系数
    :param c:pq
    :return:p，q
    """
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf


def wienerAttack(e, n):
    """
    :param e:
    :param n:
    :return: 私钥d
    """
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for d, k in gf:
        if k == 0: continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return d


n=
e=
c=
d=wienerAttack(e, n)
m=pow(c, d, n)
print(libnum.n2s(m).decode())

rsa poly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!python3
# -*- coding: utf-8 -*-
# @Time : 2020/11/17 10:36
# @Author : A.James
# @FileName: tt2.py
from binascii import *

P = 31337
R.<x> = PolynomialRing(GF(P))
N = 5788*x^215 + 26497*x^214 + 2006*x^213 + 4161*x^212 + 13803*x^211 + 16883*x^210 + 28928*x^209 + 12337*x^208 + 23340*x^207 + 15458*x^206 + 2164*x^205 + 17989*x^204 + 11778*x^203 + 7461*x^202 + 3912*x^201 + 12509*x^200 + 2524*x^199 + 17616*x^198 + 10091*x^197 + 8569*x^196 + 12782*x^195 + 30175*x^194 + 15865*x^193 + 1589*x^192 + 19001*x^191 + 10057*x^190 + 2125*x^189 + 23649*x^188 + 10083*x^187 + 7914*x^186 + 30250*x^185 + 21636*x^184 + 6021*x^183 + 12793*x^182 + 16451*x^181 + 14377*x^180 + 29693*x^179 + 8888*x^178 + 7876*x^177 + 19492*x^176 + 3704*x^175 + 13867*x^174 + 28433*x^173 + 4389*x^172 + 28314*x^171 + 21292*x^170 + 16903*x^169 + 8629*x^168 + 15699*x^167 + 26700*x^166 + 3556*x^165 + 31294*x^164 + 10491*x^163 + 9922*x^162 + 11278*x^161 + 18600*x^160 + 28135*x^159 + 21201*x^158 + 5835*x^157 + 29179*x^156 + 25120*x^155 + 6196*x^154 + 2909*x^153 + 16005*x^152 + 24607*x^151 + 5010*x^150 + 30228*x^149 + 8295*x^148 + 14039*x^147 + 21119*x^146 + 12261*x^145 + 544*x^144 + 21577*x^143 + 771*x^142 + 5324*x^141 + 22125*x^140 + 7449*x^139 + 4975*x^138 + 11478*x^137 + 26395*x^136 + 789*x^135 + 9166*x^134 + 17953*x^133 + 11420*x^132 + 11758*x^131 + 5734*x^130 + 1042*x^129 + 1914*x^128 + 23356*x^127 + 31040*x^126 + 21915*x^125 + 13038*x^124 + 25713*x^123 + 19219*x^122 + 16519*x^121 + 24862*x^120 + 23870*x^119 + 22051*x^118 + 27324*x^117 + 5476*x^116 + 12805*x^115 + 18999*x^114 + 27399*x^113 + 31291*x^112 + 28163*x^111 + 14023*x^110 + 20008*x^109 + 13034*x^108 + 26496*x^107 + 13766*x^106 + 24315*x^105 + 6977*x^104 + 22992*x^103 + 11873*x^102 + 8177*x^101 + 15918*x^100 + 22003*x^99 + 16240*x^98 + 15974*x^97 + 23722*x^96 + 17651*x^95 + 4930*x^94 + 6183*x^93 + 28655*x^92 + 9660*x^91 + 712*x^90 + 10119*x^89 + 19125*x^88 + 30686*x^87 + 18453*x^86 + 15385*x^85 + 19550*x^84 + 19519*x^83 + 11300*x^82 + 28406*x^81 + 10650*x^80 + 20720*x^79 + 19026*x^78 + 13302*x^77 + 22456*x^76 + 8222*x^75 + 13900*x^74 + 12225*x^73 + 5425*x^72 + 30405*x^71 + 26164*x^70 + 1396*x^69 + 11283*x^68 + 16263*x^67 + 19134*x^66 + 31279*x^65 + 16877*x^64 + 24996*x^63 + 16710*x^62 + 14715*x^61 + 23075*x^60 + 11418*x^59 + 29173*x^58 + 16289*x^57 + 28046*x^56 + 17240*x^55 + 11415*x^54 + 28414*x^53 + 18835*x^52 + 30971*x^51 + 854*x^50 + 18588*x^49 + 19558*x^48 + 22203*x^47 + 1991*x^46 + 17138*x^45 + 22804*x^44 + 29858*x^43 + 17180*x^42 + 14530*x^41 + 12799*x^40 + 29676*x^39 + 629*x^38 + 19090*x^37 + 587*x^36 + 21538*x^35 + 21619*x^34 + 19779*x^33 + 4584*x^32 + 22371*x^31 + 19408*x^30 + 16879*x^29 + 11100*x^28 + 7338*x^27 + 4729*x^26 + 6507*x^25 + 7434*x^24 + 3959*x^23 + 17913*x^22 + 10177*x^21 + 2399*x^20 + 7864*x^19 + 6825*x^18 + 14680*x^17 + 28609*x^16 + 22079*x^15 + 5346*x^14 + 24802*x^13 + 17107*x^12 + 4086*x^11 + 4546*x^10 + 3251*x^9 + 7759*x^8 + 12351*x^7 + 7579*x^6 + 14962*x^5 + 13915*x^4 + 23812*x^3 + 27689*x^2 + 22533*x + 721
S.<x> = R.quotient(N)
C = 3346*x^214 + 29774*x^213 + 13276*x^212 + 28577*x^211 + 14816*x^210 + 9857*x^209 + 5125*x^208 + 3171*x^207 + 8203*x^206 + 5248*x^205 + 22500*x^204 + 1974*x^203 + 21252*x^202 + 15733*x^201 + 7257*x^200 + 12616*x^199 + 9375*x^198 + 15468*x^197 + 22377*x^196 + 2111*x^195 + 6825*x^194 + 8889*x^193 + 28282*x^192 + 4619*x^191 + 16049*x^190 + 3101*x^189 + 20421*x^188 + 17495*x^187 + 25057*x^186 + 1867*x^185 + 16614*x^184 + 18334*x^183 + 1460*x^182 + 16056*x^181 + 21600*x^180 + 21322*x^179 + 8765*x^178 + 20677*x^177 + 13539*x^176 + 27956*x^175 + 3595*x^174 + 12037*x^173 + 16002*x^172 + 23491*x^171 + 9485*x^170 + 9432*x^169 + 19182*x^168 + 1752*x^167 + 14167*x^166 + 10439*x^165 + 26946*x^164 + 14661*x^163 + 22742*x^162 + 6173*x^161 + 3480*x^160 + 7223*x^159 + 30598*x^158 + 12953*x^157 + 4663*x^156 + 10054*x^155 + 22717*x^154 + 1401*x^153 + 16241*x^152 + 4639*x^151 + 44*x^150 + 18134*x^149 + 6229*x^148 + 24271*x^147 + 7393*x^146 + 7116*x^145 + 302*x^144 + 29235*x^143 + 7286*x^142 + 11039*x^141 + 5128*x^140 + 23054*x^139 + 3312*x^138 + 22753*x^137 + 13186*x^136 + 15405*x^135 + 23785*x^134 + 15821*x^133 + 21892*x^132 + 30580*x^131 + 22964*x^130 + 5088*x^129 + 6320*x^128 + 31224*x^127 + 30982*x^126 + 14333*x^125 + 15173*x^124 + 14104*x^123 + 2816*x^122 + 3799*x^121 + 8284*x^120 + 4522*x^119 + 4759*x^118 + 2259*x^117 + 28111*x^116 + 5537*x^115 + 22532*x^114 + 12465*x^113 + 20770*x^112 + 17069*x^111 + 19026*x^110 + 27833*x^109 + 14411*x^108 + 17229*x^107 + 31182*x^106 + 2967*x^105 + 1186*x^104 + 22261*x^103 + 9090*x^102 + 28062*x^101 + 5075*x^100 + 557*x^99 + 6805*x^98 + 30665*x^97 + 15129*x^96 + 27966*x^95 + 14432*x^94 + 4044*x^93 + 2937*x^92 + 11460*x^91 + 5820*x^90 + 28014*x^89 + 2374*x^88 + 28649*x^87 + 10864*x^86 + 693*x^85 + 28858*x^84 + 22944*x^83 + 3682*x^82 + 17650*x^81 + 11532*x^80 + 13225*x^79 + 15240*x^78 + 27253*x^77 + 9633*x^76 + 25244*x^75 + 23993*x^74 + 18491*x^73 + 25360*x^72 + 2710*x^71 + 16306*x^70 + 13147*x^69 + 27921*x^68 + 4362*x^67 + 12083*x^66 + 701*x^65 + 23431*x^64 + 29507*x^63 + 9407*x^62 + 19099*x^61 + 30452*x^60 + 13404*x^59 + 26105*x^58 + 8347*x^57 + 21737*x^56 + 7818*x^55 + 10473*x^54 + 25076*x^53 + 4804*x^52 + 19001*x^51 + 24131*x^50 + 10717*x^49 + 27602*x^48 + 7581*x^47 + 9653*x^46 + 26091*x^45 + 14793*x^44 + 13812*x^43 + 28818*x^42 + 8248*x^41 + 12038*x^40 + 27425*x^39 + 12697*x^38 + 6768*x^37 + 30729*x^36 + 864*x^35 + 5682*x^34 + 7100*x^33 + 1371*x^32 + 15863*x^31 + 31278*x^30 + 16065*x^29 + 14624*x^28 + 7211*x^27 + 7983*x^26 + 20891*x^25 + 15136*x^24 + 9548*x^23 + 17089*x^22 + 8549*x^21 + 13526*x^20 + 10626*x^19 + 9576*x^18 + 24733*x^17 + 18300*x^16 + 8682*x^15 + 17996*x^14 + 14781*x^13 + 17305*x^12 + 23365*x^11 + 1008*x^10 + 2749*x^9 + 20817*x^8 + 7411*x^7 + 4465*x^6 + 7784*x^5 + 27301*x^4 + 14697*x^3 + 27980*x^2 + 25732*x + 19140

p,q = N.factor()
p,q = p[0],q[0]
s = (P**p.degree()-1)*(P**q.degree()-1)
#print s
e = 65537
d = inverse_mod(e,s)
M = C^d
#print M
#print M.list()
print ("".join([chr(c) for c in M.list()]))