RSA学习笔记

发表于 更新于 阅读次数： 本文字数： 7.1k 阅读时长 ≈ 13 分钟

RSA原理

生成公私钥

  1. 选取两个不同的大素数p，q，计算N=p*q

  2. 求N的欧拉函数值

    1
    φ(N)=φ(p)φ(q)=(p−1)(q−1)

  3. 选择一个小于 φ(N) 的整数 e ，并且满足 e* 和 φ*(N) 互质，求得 e* 在模 φ(N) 意义下的乘法逆元 d ，有 ed≡1(modφ(N))。t

  4. 销毁 p 和 q

    逆元

    • 乘法逆元：

      在加法中，我们有a*+(−a)=0，我们称其互为相反数。
      在乘法中，我们有a⋅(1/a)=1，我们称其互为倒数。
      在矩阵中，我们有M      ⋅*$M^{-1}$=E，我们称其为逆矩阵。

      但是其实我们可以用一个统一的称呼：逆元，即某种运算下的逆元素，我们会发现，元素和其逆元素进行运算之后总是一个定值，实际上在代数中，他们构成了一个群（不用深究），而我们进行要了解则是在模意义下的乘法逆元。

      在模 p 意义下，指的是后续的所有运算都是在模 p 的条件下满足，例如 3⋅4≠1

      但 (3⋅4)mod11=(1)mod11，对于这种式子我们称其为同余式，并且有专门的同余符号进行表示

      3⋅4≡1(mod11)

      所以参考上面乘法中的逆元运算规则，在模意义下则有

      a⋅*$a^{-1}$≡1(mod*p)

      我们称 a和 $a^{-1}$ 互为在模 p 意义下的乘法逆元。例如上述中的 3 与 4 互为在模 11 下的乘法逆元。

    加密

    c≡$m^{e}$(modN)

    解密

    m≡$c^{d}$(modN)

基本题型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
phi = (p-1)*(q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 10554915510546378513140074459658086644656654144905337809416976066414771647836950941616441505897207397834928781511863699153349798682451297889979721668885951
q = 8246403321715011123191410826902524505032643184038566851264109473851746507405534573077909160292816825514872584170252311902322051822644609979417178306809223
e = 65537
c = 40005881669517895877352756665523238535105922590962714344556374248977905431683140065629966778249773228248201807844489945346731806741025157651474530811920115794270396320935022110691338083709019538562205165553541077855422953438117902279834449006455379382431883650004540282758907332683496655914597029545677184720

解密脚本

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
p = 10554915510546378513140074459658086644656654144905337809416976066414771647836950941616441505897207397834928781511863699153349798682451297889979721668885951
q = 8246403321715011123191410826902524505032643184038566851264109473851746507405534573077909160292816825514872584170252311902322051822644609979417178306809223
e = 65537
c = 40005881669517895877352756665523238535105922590962714344556374248977905431683140065629966778249773228248201807844489945346731806741025157651474530811920115794270396320935022110691338083709019538562205165553541077855422953438117902279834449006455379382431883650004540282758907332683496655914597029545677184720

n=p*q
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)

print(long_to_bytes(m))

延伸题型

1,e与phi不互素

由RSA基本原理可得只有当e与phi互素时，才能求出e在phi下的乘法逆元作为公钥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
26
from Crypto.Util.number import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)

e = 65537*2

n = p*q

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 9927950299160071928293508814174740578824022211226572614475267385787727188317224760986347883270504573953862618573051241506246884352854313099453586586022059
q = 9606476151905841036013578452822151891782938033700390347379468858357928877640534612459734825681004415976431665670102068256547092636766287603818164456689343
e = 131074
c = 68145285629092005589126591120307889109483909395989426479108244531402455690717006058397784318664114589567149811644664654952286387794458474073250495807456996723468838094551501146672038892183058042546944692051403972876692350946611736455784779361761930869993818138259781995078436790236277196516800834433299672560
'''

可知c≡$m^{e}$(modN)，且$m^{e}$=$m^{2*65537}$，我们将$m^{2}$看作一个整体并用e=65537加密。此时即可得到的d，解密后开平方即可得到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from gmpy2 import *

p = 9927950299160071928293508814174740578824022211226572614475267385787727188317224760986347883270504573953862618573051241506246884352854313099453586586022059
q = 9606476151905841036013578452822151891782938033700390347379468858357928877640534612459734825681004415976431665670102068256547092636766287603818164456689343
e = 131074
c = 68145285629092005589126591120307889109483909395989426479108244531402455690717006058397784318664114589567149811644664654952286387794458474073250495807456996723468838094551501146672038892183058042546944692051403972876692350946611736455784779361761930869993818138259781995078436790236277196516800834433299672560

n = p*q
phi = (p-1)*(q-1)
d = invert(e // 2, phi)
m = pow(c, d, p*q)

print(long_to_bytes(isqrt(m)))

通解

通过归纳总结我们可以得到这类问题的通解（仅限于双因子p，q）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2  
import libnum
import rsa
from Cryptodome.PublicKey import RSA 



def known_p_q_eprime_c():
    p = int(input('请输入一个素数p：'))
    q = int(input('请输入另一个素数q：'))
    e = int(input('请输入公钥e：'))
    c = int(input('请输入密文c：'))

    n = p * q
    phi = (p - 1) * (q - 1)
    t = gmpy2.gcd(e, phi)
    d = gmpy2.invert(e // t, phi)
    m = pow(c, d, n)

    return int(gmpy2.iroot(m, t)[0]) 
    print(f'私钥d：{d}')
    print(f'明文m：{m}')
if m != None:
    print(f'字符明文：{libnum.n2s(int(m)).decode("utf-8")}')

2，小明文攻击

我们知道加密时

c≡$m^{e}$(modN)

当n极大，e较小时，我们可以假设m很小，即$m^{e}$<n，此时c=$m^{e}$，我们可以直接通过m = iroot(c, e)求解

（我们使用gmpy2中的iroot开任意次方，用法为iroot(10, 3)代表对10开3次方，返回结果为(mpz(2), False)，其中第一项为返回的结果，mpz为gmpy2包中对整数的封装类，看作一个整数即可，第二项代表这个数是否为完全开放的结果，例如103310并不是一个整数，但gmpy2只会返回取整后的整数值，故通过第二项我们能够知道是否为完全k次方数。

例如iroot(9, 2)返回(mpz(3), True)代表9是一个完全平方数。）

3，低加密指数攻击（e非常小）

同样是n很大，此时的e极小，而当我们用到小明文攻击的方法求解时，发现出错，说明此时$m^{e}$>n,由c≡$m^{e}$(modN)得，$m^{e}$=c+k⋅n，此时我们可以遍历k，当c+kn为一个完全平方数时，即可得到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
from Crypto.Util.number import *
from gmpy2 import *

flag = b'NSSCTF{******}'

p = getPrime(512)
q = getPrime(512)

n = p*q
e = 3
phi = (p-1)*(q-1)
m = bytes_to_long(flag)

c = powmod(m, e, n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 111573371787314339229652810703380127177507745009618224416171957526984270337589283887959174610818933914845556276472159360153787395638087723501889651641965684241070152541291185349571453536221312112508437223801640552330390095266644485311958102687735113533739324296417077804219395793942670324182191309872918900717
e = 3
c = 90782646242308381145716338972639920044710403094882163620436540965475107006005657722222634294458956650085252212452241377251397323707019480880284004845674260662647720809672266571040936376737882878688872281858048646517100139303896804340224961592424635124272549514473232731744884837572128596217771005209683966262
'''

wp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from gmpy2 import *
n = 111573371787314339229652810703380127177507745009618224416171957526984270337589283887959174610818933914845556276472159360153787395638087723501889651641965684241070152541291185349571453536221312112508437223801640552330390095266644485311958102687735113533739324296417077804219395793942670324182191309872918900717
e = 3
c = 90782646242308381145716338972639920044710403094882163620436540965475107006005657722222634294458956650085252212452241377251397323707019480880284004845674260662647720809672266571040936376737882878688872281858048646517100139303896804340224961592424635124272549514473232731744884837572128596217771005209683966262

for k in range(100000):
    cc = c + k*n
    res = iroot(cc, e)
    if res[1]:
        m = res[0]
        break

print(long_to_bytes(m))
print('k:',k) # 11