RSA加密算法是一种非对称加密算法,1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的,RSA的安全性基于大整数因式分解的数学难题,可用于加密和签名

算法描述

  1. 密钥生成

    • 选取两个大素数p和q,(p≠q,且p和q须保密)

    • 计算 n=p×q,φ(n)=(p-1)×(q-1),φ为n的欧拉函数

    • 选择整数e,e与φ(n)互素,1<e<φ(n)

    • 计算d,d = e-1 mod φ(n),公钥为{e,n},私钥为{d}

  2. 加密

    • 明文 M<n,密文 C = Me mod n
  3. 解密

    • 密文 C,明文 M = Cd mod n

大素数的生成

  1. 生成伪素数,随机选取奇数 num
  2. 使用素性检验方法如Miller-Rabin算法对伪素数num进行检验,如果num没有通过检验,转到步骤1
  3. 重复步骤2足够多次,如果num都通过了检验,则可以认为num是一个素数
    # 素数生成
    def generate_key(key_len):
    # 生成key_len长度的p和q
    p = random_prime(key_len)
    q = random_prime(key_len)
    n = p * q
    ph_n = (p -1) * (q -1)
    e = 65537 #e取固定值
    d = generate_d(ph_n, e)
    return (n ,e, d)

    #开始选择p q
    def random_prime(half_len):
    while True:
    n = random.randint(0, 1 << half_len)#求2^half_len之间的大数
    if n % 2 != 0:
    found = True
    # 随机性测试
    for i in range(0, 20): # 检测的次数
    if prime_test(n) == False:
    found = False
    break
    if found == True:
    return n
    获得私钥d:d = e-1 mod φ(n)
    # 扩展欧几里得算法
    def ext_gcd(a, b):
    if b == 0:
    return 1, 0, a
    else:
    x, y, q = ext_gcd(b, a % b)
    x, y = y, (x - (a // b) * y)
    return x, y, q

    # 产生私钥d
    def generate_d(ph_n, e):
    (x, y, r) = ext_gcd(ph_n, e)
    if y < 0:
    return y + ph_n #直接用加法效率高一丢丢
    return y

Miller-Rabin算法

基础理论

  • 费马小定理:p为素数,有 ap-1 = 1 (mod p)
  • 二次探测:p为素数,0 < x < p,则方程 x2 = 1 (mod p) 的解为 x=1 或 x=p-1
    # Miller-Rabin检测
    def prime_test(n):
    """
    测试n是否为素数
    """
    q = n - 1
    k = 0
    # 寻找k,q 是否满足2^k*q =n - 1
    while q % 2 == 0:
    k += 1
    q = q // 2
    a = random.randint(2, n - 2)
    # 如果 a^q mod n= 1, n 可能是一个素数
    if fast_mod(a, q, n) == 1:
    return True
    # 如果存在j满足 a ^ ((2 ^ j) * q) mod n == n-1, n 可能是一个素数
    for j in range(0, k):
    if fast_mod(a, (2 ** j) * q, n) == n - 1:
    return True
    # n 不是素数
    return False

RSA的攻击

针对n分解的攻击

  1. 试除法:完全尝试所有小于√n的素数
  2. 因式分解法
    • 二次筛法
    • 连分数法
    • 椭圆曲线筛法

循环攻击

  1. 设m为明文,(n,e)为公钥,密文 c = me mod n

    • 攻击者得到密文c后,对c依次进行如下变换:
      c1 = ce mod n
      c2 = c1e mod n
      …… ……
      ck = ck-1e mod n
      ck+1 = cke mod n
    • k+1次迭代后,如果ck+1=c,由c=me mod n,则ck= m,获得明文
  2. 避免循环攻击:

    • ordn(m)要大,且φ(ordn(m))要有大的素因子
    • ordn(m)是φ(n)的因子,所以需要p-1和q-1都有大的因子

共模攻击

  • m为明文,两用户的公钥分别为e1和e2,且互素,共同的模数n,两个密文分别为c1和c2
  • 攻击者知道n,e1,e2,c1和c2
  • 恢复明文m:由欧几里得算法可找出r和s满足 re1+se2=1,假定r是负数,那么 (c1-1)-r c2s = mre1+se2 = m mod n
  • 无需私钥d即可获得明文m

共模攻击脚本:

from gmpy2 import invert

def gongmogongji(n, c1, c2, e1, e2):
def egcd(a, b):
if b == 0:
return a, 0
else:
x, y = egcd(b, a % b)
return y, x - (a // b) * y
s = egcd(e1, e2)
s1 = s[0]
s2 = s[1]

# 求模反元素
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
return m

防御:使用RSA公钥加密的通信中,不同用户的密钥不能有相同的模值

低加密指数攻击

小的公钥e可以加快加密的速度,但过小的公钥易受到攻击

  • 如果3个用户都使用3作为公钥,对同一个明文 m 加密,则 c1=m3 mod n1,c2=m3 mod n2,c3=m3 mod n3,且n1,n2,n3互素,m小于模数
  • 中国剩余定理可从c1,c2,c3计算出c,且 c = m3mod (n1n2n3),m = c1/3
  • 如果采用不同的n,相同的e,对e(e+1)/2个线性相关的消息加密,系统就会受到威胁,所以一般选取16位以上的素数(速度快且可防止攻击)
  • 对短消息,用随机数填充以保证me ≠ memod n,从而杜绝低加密指数攻击