RSA加密笔记

最后更新：2020-03-02 11:23:12

1. RSA 介绍

RSA 算法涉及参数有：n、e、d（p、q），其中分为私钥和公钥。公钥为：n、e，私钥为：phi、d。涉及数学基础有：欧拉函数（phi）、欧几里得算法（gcd）、同余。

参数介绍：

n ： 两个素数 p 与 q 的乘积。注意：n 将公开，而 p 与 q 不公开。

e ：一个素数。满足 1<e<phi ，且 gcd(phi,e)=1（与 phi 最大公约数为 1 ，即互素）。

phi ： 欧拉数，计算公式：phi = (p-1)(q-1)。

d ： e 模 phi 的逆元，具体关系式：d * e = 1 mod(phi)。

2. 加解密算法

c = m^e mod n = pow(m,e,n)

m = c^d mod n = pow(c,d,n)

3. 基础加解密脚本

加密脚本

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

msg = 'flag is :testflag'	# 明文
hex_msg=int(msg.encode("hex"),16)	# 转换明文为数字

# 生成公钥 n、e
p=getPrime(100)	# 随机生成一个质数
q=getPrime(100)
n=p*q
e=0x10001
print("n=",hex(n))
print("e=",hex(e))

# 生成私钥 phi、d
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)	# 逆元运算
print("phi=",hex(phi))
print("d=",hex(d))

#加密算法
c=pow(hex_msg,e,n)
print("c=",hex(c))

解密脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 已知 c、n、e ，并分解n获得q、p
import gmpy2

c=0x534280240c65bb1104ce3000bc8181363806e7173418d15762
e=0x10001
n=0x80b32f2ce68da974f25310a23144977d76732fa78fa29fdcbf
# 这里使用yafu分解n
p=780900790334269659443297956843
q=1034526559407993507734818408829

# 计算私钥
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
# 解密算法
m=pow(c,d,n)
print(hex(m)[2:].decode('hex'))	# 转换明文为字符

一般情况下，c e n phi p q c 都是 int 型，m 是 str 型。所以需要将 m 转换为 int 型带入算法进行异或运算。

我遇到过有两种转换方式：

1
2
3
4
5
6
7
# 方法 1 
msg=int(msg.encode("hex"),16)
msg=hex(msg)[2:].decode('hex')
# 方法 2 
from Crypto.Util.number import *
bytes_to_long(b'felinae')		# bytes 转 int
long_to_bytes(28821963924201829)# 数字转 bytes

求逆元 d 的话，用 gmpy2.invert 代入参数即可。只是 gmpy2 这个库比较难装。

4. 常见攻击方法

4. 1 p 与 q 相差过大(小)

这种情况下，可以利用工具爆破出两个大质数 p 与 q 。通常认为长度在 256 bit 一以下，可以在本地利用工具爆破：

长度在 712 bit 以下的，可以到在线网站查询一下是否有已经解密的结果：

4.2 有多个公钥 n 且有共用素数因子

可以尝试**利用公约数分解 n **

  • 利用欧几里得辗转相除法求解最大公约数：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def gcd(a, b):
       if a < b:
         a, b = b, a
       while b != 0:
         temp = a % b
         a = b
         b = temp
       return a
    def main():
        a = 38
        b = 18
        print(gcd(a,b))
    if __name__ == '__main__':
      main()

  • 利用Crypto.Util.number 库：

    1
    2
    from Crypto.Util.number import GCD
    GCD(38,18)

4.3 共模攻击

如果在RSA的使用中使用了相同的模n对相同的明文m进行了加密，那么就可以在不分解n，也不需要求解私钥的情况下还原出明文m的值。即：当n不变的情况下，知道n,e1,e2,c1,c2 可以在不知道d1,d2的情况下，解出m。

利用的数学公式：拓展欧几里得算法。 python 脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
#RSA 共模攻击脚本

from libnum import n2s, s2n
from gmpy2 import invert

# 扩展欧几里得算法
def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)


def main():
  n = 27560959918385616419486273009594513460044316476337842585463553105701869531698366304637678008602799005181601310816935394003041930445509801196554897781529962616349442136039951911764620999116915741924245788988332766182305635804754798018489793066811741026902011980807157882639313892932653620491354630354060462594865874663773934670618930504925812833202047183166423043264815905853486053255310346030416687430724204177468176762512566055165798172418622268751968793997676391170773216291607752885987933866163158257336522567086228092863302685493888839866559622429685925525799985062044536032584132602747754107800116960090941957657
  c1 = 21823306870841016169952481786862436752894840403702198056283357605213928505593301063582851595978932538906067287633295577036042158302374948726749348518563038266373826871950904733691046595387955703305846728530987885075910490362453202598654326947224392718573893241175123285569008519568745153449344966513636585290770127055273442962689462195231016899149101764299663284434805817339348868793709084130862028614587704503862805479792184019334567648078767418576316170976110991128933886639402771294997811025942544455255589081280244545901394681866421223066422484654301298662143648389546410087950190562132305368935595374543145047531
  c2 = 9206260935066257829121388953665257330462733292786644374322218835580114859866206824679553444406457919107749074087554277542345820215439646770680403669560474462369400641865810922332023620699210211474208020801386285068698280364369889940167999918586298280468301097349599560130461998493342138792264005228209537462674085410740693861782834212336781821810115004115324470013999092462310414257990310781534056807393206155460371454836230410545171068506044174001172922614805135260670524852139187370335492876094059860576794839704978988507147972109411033377749446821374195721696073748745825273557964015532261000826958288349348269664
  e1 = 464857
  e2 = 190529
  s = egcd(e1, e2)
  s1 = s[1]
  s2 = s[2]
  # 求模反元素
  if s1 < 0:
    s1 = - s1
    c1 = invert(c1, n)
  elif s2 < 0:
    s2 = - s2
    c2 = invert(c2, n)

  m = pow(c1, s1, n) * pow(c2, s2, n) % n
  print(n2s(m))  # 二进制转string


if __name__ == '__main__':
  main()

库 gmpy2.gcdext(e1,e2) 与脚本定义函数相同。

5. 更全面的学习