基于Python实现RSA 加密和解密算法【100011713】

## RSA 加密和解密算法 ### 1. 算法原理 #### 1.1 RSA 原理概述 * **RSA算法原理**：采用模函数 $M^k\mod n$ 构造单向函数 * 加密：明文 $M$ 经过加密运算得到密文$C$：$M^e\mod n = C$，$e$ 为加密密钥。 * 解密：：$C^d \mod n =(M^e \mod n)^d \mod n=M$，$d$ 为解密秘钥。 * 即必须存在$e$、$d$、$n$，使$M^{ed} \mod n=M$成立，其中$n$、$e$为公钥，$d$为私钥。确定$n$、$e$、$d$ 基于两大定理：欧拉函数以及费马小定理。 * **RSA密钥生成**： * 选两个保密的大素数 $p$、$q$； * 计算$n=q\times p$，$\varphi (n)=(p-1) \times (q-1)$，其中 $\varphi(n)$ 是 $n$ 的欧拉函数值； * 选一整数 $e$，满足 $1<e<\varphi(n)$ 和 $\gcd (\varphi(n),e) = 1$ 成立； * 计算 $d$，满足$ed ≡ 1 \mod \varphi(n)$ ； * 即 $d$ 是 $e$ 在模 $\varphi(n)$ 下的乘法逆元，因 $e$ 与 $\varphi(n)$ 互素，由模运算可知，它的乘法逆元一定存在； * 可以用辗转相除法求解：$e \times d + \varphi(n) \times y = 1$； * 以 $\{e,n\}$ 为公钥，$\{d,n\}$ 为私钥。 #### 1.2 中国剩余定理原理概述 * 中国剩余定理（CRT）：设整数 $m_1, m_2,...,m_n$ 两两互素，对于任意整数 $a_1, a_2, ..., a_n$，方程组： $$ x \equiv a_1 (\mod m_1) \\ x \equiv a_2 (\mod m_2) \\ \vdots \\ x \equiv a_n (\mod m_n) \\ $$ 都存在整数解，且若 $x_1$，$x_2$ 都满足此方程组，则有 $x_1 \equiv x_2 (\mod \Pi_{i= 1}^nm_i)$ 我们将 $n = 2$ 的情况运用到 RSA 解密中。 * **RSA-CRT 密钥生成**： > 参考以下文档和博客：[Using the CRT with RSA](https://www.di-mgt.com.au/crt_rsa.html#PKCS1) 和 [使用中国剩余定理CRT对RSA运算进行加速](https://blog.csdn.net/youngbug/article/details/123409838)，可能与老师提供的论文 Faster RSA Algorithm for Decryption Using Chinese Remainder Theorem 有出入。 * 选两个保密的大素数 $p$、$q$； * 计算 $n = q \times q$ * 计算 $d_p = e^{-1}\mod (p - 1)$， $d_q = e^{-1}\mod (q - 1)$ 和 $q_{Inv} = q^{-1}\mod p$，其中 $e^{-1}$ 表示求模的逆元。 * 取五元组 $(p, q, d_p, d_q, q_{Inv})$ 为私钥，二元组 $\{e,n\}$ 为公钥 * **RSA-CRT 解密过程：** * 加密过程与 RSA 一致，中国剩余定理主要用在加速解密过程 * 令密文为 $c$，私钥为 $(p, q, d_p, d_q, q_{Inv})$ ，计算以下式子，最终求出明文 $m$。 $$ m_1 = c^{d_p} \mod p \\ m_2 = c^{d_q} \mod q \\ h = q_{Inv} \times (m_1 - m_2) \mod pc \\ m = m_2 + h \times q $$ ### 2. 代码实现 > RSA 代码实现于 `rsa.py` 文件 #### 2.1 RSA 代码实现 1. 首先实现扩展欧几里得算法： 用于求解 $ax + by = 1$ 中的 $x$ 和 $y$，使用递归的思路实现。 ```python def ext_gcd(a, b): if b == 0: return a, 1, 0 else: r, x_, y_ = ext_gcd(b, a % b) x = y_ y = x_ - a // b * y_ return r, x, y ``` 2. 实现快速幂算法：用于计算 $(base ^{exponent}) \mod n$，使用迭代的思路实现，算法复杂度为 $O(\log(n))$ ``` python def exp_mod(base, exponent, n): # 取 exponent 的二进制并倒置 bin_array = bin(exponent)[2:][::-1] r = len(bin_array) # 快速幂 base_array = [base] for _ in range(r - 1): next_base = (base * base) % n base_array.append(next_base) base = next_base res = 1 for i in range(len(base_array)): if int(bin_array[i]): res = (res * base_array[i]) % n return res % n ``` 3. 使用一个类来封装 RSA 算法：对象初始化时创建公私钥，可以通过 `get_pub_key` 方法获取公钥，加密明文时可以调用 `encrypt` 方法，解密明文时可以调用 `decrypt` 方法 ```python # RSA class RSA: def __init__(self, p=None, q=None): if p is None: p = make_prime(1024) if q is None: q = make_prime(1024) # 生成公私钥 n = p * q f = (p - 1) * (q - 1) e = 65537 _, d, _ = ext_gcd(e, f) if d < 0: d += f self._pub_key = (e, n) self._pri_key = (d, n) def get_pub_key(self): return self._pub_key # 加密 def encrypt(self, plaintext): m = str_to_int(plaintext) # 字符串转整形 e, n = self._pub_key return exp_mod(m, e, n) # 解密 def decrypt(self, ciphertext): d, n = self._pri_key m = exp_mod(ciphertext, d, n) return int_to_str(m) # 整形转字符串 ``` 4. 最后实现了一个通用的加密明文函数，用于模拟其他用户使用他人的公钥加密明文： ``` python def encrypt_with_pub_key(plaintext, pub_key): m = str_to_int(plaintext) e, n = pub_key return exp_mod(m, e, n) ``` #### 2.2 CRT-RSA 代码实现 1. 使用一个类来封装 CRT-RSA，内部的方法与上一步实现的 RSA 类一致。 ``` python class CRT_RSA: def __init__(self, p=None, q=None): if p is None: p = make_prime(1024) if q is None: q = make_prime(1024) # 生成公私钥 n = p * q e = 65537 self._pub_key = (e, n) _, dP, _ = ext_gcd(e, p - 1) _, dQ, _ = ext_gcd(e, q - 1) _, qInv, _ = ext_gcd(q, p) if dP < 0: dP += p - 1 if dQ < 0: dQ += q - 1 if qInv < 0: qInv += p self._pri_key = (p, q, dP, dQ, qInv) def get_pub_key(self): return self._pub_key # 加密 def encrypt(self, plaintext): m = str_to_int(plaintext) # 字符串转整形 e, n = self._pub_key return exp_mod(m, e, n) # 解密 def decrypt(self, ciphertext): p, q, dP, dQ, qInv = self._pri_key m1 = exp_mod(ciphertext, dP, p) m2 = exp_mod(ciphertext, dQ, q) h = (qInv * (m1 - m2)) % p m = m2 + h * q return int_to_str(m) # 整形转字符串 ``` ### 3. 算法效果对比 * 我们的算法可以处理字符串输入，模拟将消息转化成数字串，再进行加密的过程，并全部封装在了类里，下面以明文： `Shinde, G. N., and H. S. Fadewar. 'Faster RSA algorithm for decryption using Chinese remainder theorem'. ICCES: International Conference on Computational & Experimental Engineering and Sciences. Vol. 5. No. 4. 2008.` 为例 测试 RSA 和 CRT-RSA 的加解密，并比较运行时间。 * 随机选取 1024 位的两个互素大整数 $p$ 和 $q$，生成公私钥，并输出公钥：`65537, 23508174192368769894131484827446673314864471253327778810272713852859805820504829059851248634431578353683060228503338758726756909147458399570844126338952432304985626461103377110018405309283860391573903403693898292038305669780616047612419787001496899469090747047941069842391593209530433844916240177980519590987191925010265075433879906274702490427000307109819084135347332250929004776757824713723191148768261048332827688761464108061863773808024922655329607799731091507289438975682656713377068698522843173496387912076275843891340993349060721244894547797294805795090013118635982601932173121547703332744166687498790956467369` * 使用公钥加密明文得到密文： `155080700604953452292552430901324656339082318711976659925187274466443910067811141633302828038706553305816243843339968139627817479490511967092855908