RSA 算法介绍

RSA 算法系统主要包含三个子算法：Gen, Enc, Dec，分别是密钥生成算法、加密算法以及解密算法。

密钥生成

密钥生成的过程如下：

选取大素数 $p,q$；
计算 $n=p\cdot q$，此处 $n$ 的位数就是 RSA 密钥的长度，比较稳妥的是2018位；
计算 $\phi(n)=(p-1) \cdot (q-1)$；
随机选取 $e$ 使得 $1\le e \le \phi(n)$，并且 $(e, \phi(n))=1$；
计算$d=e^{-1}\mod \phi(n)$；
因此，$(e, n)$ 即为 RSA 算法的公钥，$(d, n)$ 即为私钥。

加密

假设明文为 $m$；
计算密文 $c=m^e \mod n$。

解密

解密的过程很简单，为：

给定密文 $c$；
计算明文 $\hat{m}=c^d \mod n$

算法证明

算法的可行性证明过程如下：

$\begin{align} \hat{m} &= c^d \mod n\\ &\equiv m^{ed} \mod n \end{align}$

当 $(m,n)=1$ 时，根据欧拉定理很容易知道是对的。如果 $m,n$ 不互质，不妨假设 $m=p\cdot x$，那么有：

$\begin{align} m^{ed} &=(px)^{ed} \mod p\\ & \equiv 0 \mod p \\ & \equiv m \mod p\\ \end{align}$

再看对于 $q$ 的情况，首先有 $ed-1=h\cdot \phi(n) = h(p-1)(q-1)$

$\begin{align} m^{ed} &=m\cdot m^{ed-1} \mod q\\ &\equiv m \cdot m^{h(p-1)(q-1)}\mod q\\ &\equiv m \mod q \end{align}$

所以就有 $m^{ed} \equiv m \mod n$ 了，因此 RSA 在功能上是正确的。

算法案例

此部分代码在

# @author S.L.

import sympy
import numpy as np


class RSA:
    def __init__(self, p=0, q=0, e=0, d=0):
        self.__p = p
        self.__q = q
        self.__n = self.__p * self.__q
        self.__phi = (self.__p-1) * (self.__q-1)
        self.__e = e
        self.__d = d

    def generate_key(self, key_bits=10):
        # choose p and q, and calculate n and phi
        # key_bits = key_bits / 2             # RSA 密钥的位数指的是 n 的位数
        self.__p = sympy.ntheory.generate.randprime(2 ** key_bits, 2 ** (key_bits + 1))
        self.__q = sympy.ntheory.generate.randprime(2 ** key_bits, 2 ** (key_bits + 1))
        self.__n = self.__p * self.__q
        self.__phi = (self.__p - 1) * (self.__q - 1)
        while True:
            # 暴力一点，直接选了一个素数当 e
            self.__e = sympy.ntheory.generate.randprime(2, self.__phi)
            self.__d = sympy.mod_inverse(self.__e, self.__phi)
            if sympy.gcd(self.__e, self.__phi) == 1:
                break

    def encrypt(self, m):
        # todo: 未加速，速度很慢
        return m**self.__e % self.__n

    def decrypt(self, c):
        # todo: 未加速，速度很慢
        return c**self.__d % self.__n

    def get_public_key(self):
        return self.__e, self.__n

    def get_private_key(self):
        return self.__d, self.__n

    def __str__(self):
        return "ttt"

    def is_validate(self):
        # todo: 检测当前参数是否合规
        return True


rsa = RSA()
rsa.generate_key()

x = 12
y = rsa.encrypt(x)
print("the encrypted number is: ", y)
x = rsa.decrypt(y)
print("the decrypted result is: ", x)