RSA 加密方案

RSA 算法

• RSA 加密和签名：因大整数因子分解难算，合数可成公钥。
  
  d - 私钥，e - 公钥，n - 可公开的合数，(e,n) 作为公钥可以公开，(d,n) 作为私钥。

详细理论证明参考：RSA算法原理（二）

假设明文消息为 M，密文为 C
加密过程：$M^e\mathrm{mod}n=C$
解密过程：$C^d\mathrm{mod}n=M$

RSA 签名举例

#-*- coding:utf-8 -*-
import random


# 求最大公约数
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    elif a % b == 0:
        return b
    else:
        return gcd(b, a % b)


# 快速幂+取模
def power(a, b, c):
    ans = 1
    while b != 0:
        if b & 1:
            ans = (ans * a) % c
        b >>= 1
        a = (a * a) % c
    return ans


# 快速幂
def quick_power(a: int, b: int) -> int:
    ans = 1
    while b != 0:
        if b & 1:
            ans = ans * a
        b >>= 1
        a = a * a
    return ans


# 大素数检测
def Miller_Rabin(n):
    a = random.randint(2, n - 2)  # 随机第选取一个a∈[2,n-2]
    # print("随机选取的a=%lld\n"%a)
    s = 0  # s为d中的因子2的幂次数。
    d = n - 1
    while (d & 1) == 0:  # 将d中因子2全部提取出来。
        s += 1
        d >>= 1

    x = power(a, d, n)
    for i in range(s):  # 进行s次二次探测
        newX = power(x, 2, n)
        if newX == 1 and x != 1 and x != n - 1:
            return False  # 用二次定理的逆否命题，此时n确定为合数。
        x = newX

    if x != 1:  # 用费马小定理的逆否命题判断，此时x=a^(n-1) (mod n)，那么n确定为合数。
        return False

    return True  # 用费马小定理的逆命题判断。能经受住考验至此的数，大概率为素数。


# 卢卡斯-莱墨素性检验
def Lucas_Lehmer(num: int) -> bool:  # 快速检验pow(2,m)-1是不是素数
    if num == 2:
        return True
    if num % 2 == 0:
        return False
    s = 4
    Mersenne = pow(2, num) - 1  # pow(2, num)-1是梅森数
    for x in range(1, (num - 2) + 1):  # num-2是循环次数，+1表示右区间开
        s = ((s * s) - 2) % Mersenne
    if s == 0:
        return True
    else:
        return False


# 扩展的欧几里得算法，ab=1 (mod m), 得到a在模m下的乘法逆元b
def Extended_Eulid(a: int, m: int) -> int:
    def extended_eulid(a: int, m: int):
        if a == 0:  # 边界条件
            return 1, 0, m
        else:
            x, y, gcd = extended_eulid(m % a, a)  # 递归
            x, y = y, (x - (m // a) * y)  # 递推关系，左端为上层
            return x, y, gcd  # 返回第一层的计算结果。
        # 最终返回的y值即为b在模a下的乘法逆元
        # 若y为复数，则y+a为相应的正数逆元

    n = extended_eulid(a, m)
    if n[1] < 0:
        return n[1] + m
    else:
        return n[1]


# 按照需要的 bit 来生成大素数
def Generate_prime(key_size: int) -> int:
    while True:
        num = random.randrange(quick_power(2, key_size - 1), quick_power(2, key_size))
        if Miller_Rabin(num): # 大概率是素数
            return num


# 生成公钥和私钥
def KeyGen(p: int, q: int):
    n = p * q
    e = random.randint(1, (p - 1) * (q - 1))
    while gcd(e, (p - 1) * (q - 1)) != 1:
        e = random.randint(1, (p - 1) * (q - 1))
    d = Extended_Eulid(e, (p - 1) * (q - 1))
    return n, e, d


def Sign(x: int, d: int, n: int) -> int:
    s = power(x, d, n)
    return s


def Verify(s: int, e: int, n: int) -> int:
    x_ = power(s, e, n)
    return x_


if __name__ == '__main__':
    key_size = 512
    p = Generate_prime(key_size)
    q = Generate_prime(key_size)
    n, e, d = KeyGen(p, q)

    # 消息
    x = int(input("Message: "))
    if type(x) != int: raise ValueError("Must be an integer!")
    # 签名
    s = Sign(x, d, n)
    # 验证
    x_ = Verify(s, e, n)
    Valid = (x_ == x)

    # Attack
    s_ = random.randint(1, (p - 1) * (q - 1))
    m_ = random.randint(1, (p - 1) * (q - 1))

    # 记录
    print("p:\t", p)
    print("q:\t", q)
    print("Private Key↓")
    print("N:\t", n)
    print("d:\t", d)
    print("Public Key↓")
    print("N:\t", n)
    print("e:\t", e)
    print("Signature↓")
    print("s:\t", s)