RSA加密笔记

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. 基础加解密脚本

加密脚本

from Crypto.Util.number import *
import gmpy2

msg = &#039;flag is :testflag&#039;    # 明文
hex_msg=int(msg.encode(&quot;hex&quot;),16)    # 转换明文为数字

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

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

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

解密脚本

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : ${DATE} ${TIME}
# @Author  : MrSkYe
# @Email   : [email protected]
# @File    : ${NAME}.py
# @Software: ${PRODUCT_NAME}
# 已知 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:])    # 十六进制的明文

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

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

# 方法 1 
msg=int(msg.encode(&quot;hex&quot;),16)
msg=hex(msg)[2:].decode(&#039;hex&#039;)
# 方法 2 
from Crypto.Util.number import *
bytes_to_long(b&#039;felinae&#039;)        # 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

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

    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 库:

    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 脚本:

#! /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. 更全面的学习

Last modification:August 12th, 2020 at 01:53 pm