RSA密码系统：原理、攻击与实践

### RSA密码系统：原理、攻击与实践 #### 1. RSA密码系统简介 1978年，Rivest、Shamir和Adleman引入了第一个实用且最流行的公钥密码系统——RSA密码系统。该系统基于分解大合数的困难性，下面对其进行简要描述。 - **密钥生成**： - Bob精心选择两个大素数p和q，计算n = pq和φ(n) = (p - 1)(q - 1)。 - 选择一个加密密钥e < φ(n)，使得gcd(e, φ(n)) = 1。 - 计算解密密钥d，使得ed = 1 (mod φ(n))。 - Bob的公钥是(n, e)，私钥是d，明文空间是Zn。 - **加密过程**：Alice要加密消息m ∈ Z⋆n，使用Bob的公钥计算c = me (mod n)，并将密文c发送给Bob。 - **解密过程**：Bob收到密文c后，通过计算m = cd (mod n)得到明文。 **正确性证明**：由于ed = 1 (mod φ(n))，则ed = k×φ(n) + 1（k为整数），所以cd = med (mod n) = m1 + kφ(n) (mod n) = m（根据欧拉定理），方程ed = 1 (mod φ(n))被称为RSA方程。 **注意事项**：一般将RSA密码系统的明文和密文空间设为Zn，但明文m必须是Z⋆n的元素，否则gcd(m, n)会给出RSA模数n的一个因子。 **示例**： - **示例119**：Bob选择p = 23，q = 31，n = 713，φ(n) = 660，e = 19，d = 139。Alice要发送消息m = 15，加密得到c = 525，Bob解密得到m = 15。 - **示例120**：Bob选择p = 257，q = 337，n = 86609，φ(n) = 86016，e = 17，d = 65777。Alice发送消息“HE”（数值表示为0705），加密得到c = 46293，Bob解密得到m = 705，即“HE”。 #### 2. RSA作为分组密码 原始消息M可能长度任意，使用RSA加密时，先将其分成固定大小的块M = m1m2m3 ... mk，使得mi < n（i = 1, 2, 3, ..., k），然后使用分组密码技术逐块加密。 设RSA模数为n，明文和密文包含N个字母数字符号字符，使用字母表Σ = ZN = {0, 1, 2, 3, ..., N - 1}表示明文/密文字符。此时，RSA密码系统可定义为块长为k的分组密码，其中k = ⌊logNn⌋。 任何块长为k的明文单词m1m2m3 ... mk ∈ Σk对应一个整数m = Σki=1miNk - i，且0 ≤ m < n。块通过计算c = me (mod n)进行加密，密文整数c以N为基表示为c = Σki=0ciNk - i，c0c1c2 ... ck就是对应明文块m1m2 ... mk的密文块。RSA将长度为k的块映射到长度为k + 1的块，这不符合传统分组密码明文和密文块长度相等的定义，但可用于稍微修改ECB模式和CBC模式。在任何公钥密码系统（如RSA）中，由于该模式下加密和解密密钥相同，无法使用CFB模式或OFB模式。 **示例121**：考虑p = 23，q = 31，n = 713，e = 19，d = 139，Σ = {0, a, b, c, d}，k = ⌊log5713⌋ = 4。明文abc0对应整数m = 190，加密得到c = 225，以5为基表示为0ad00。 #### 3. RSA假设和RSA问题 - **RSA问题**：给定c = me (mod n)（n = pq为两个大素数之积，e为正整数且e < φ(n)，gcd(e, φ(n)) = 1），计算m。 - **RSA假设**：如果不存在概率多项式时间（PPT）算法A以不可忽略的成功概率ε解决RSA问题，则称RSA假设成立，即不存在PPT算法A使得Prob[m ← A(n, e, me (mod n)] < ε（ε > 0为不可忽略的量）。 **备注**：RSA假设的成立意味着存在陷门单向函数me : Z⋆n → Z⋆n（n的素因数分解是陷门），该假设中的概率空间包括实例空间、明文消息空间和解决RSA问题的随机算法的随机操作空间。 许多研究探讨了RSA问题和因数分解问题之间的关系，如《Breaking RSA may not be equivalent to factoring》《Breaking RSA May Be As Difficult As Factoring》《Breaking RSA May Be Easier Than Factoring》等论文的分析有助于理解这两个问题和假设之间的关系。 #### 4. RSA的密码分析攻击 RSA密码系统面临多种攻击，下面介绍几种常见的攻击方式。 - **因数分解攻击**：如果RSA模数被分解，系统将毫无安全性可言，密码分析者可以轻松获取私钥。寻找给定合数的因数被称为因数分解问题，如果不存在多项式时间算法以不可忽略的成功概率解决该问题，则称该实例满足因数分解假设。虽然可以通过因数分解算法解决RSA问题，但反之仍是一个开放问题，因此RSA的安全性与因数分解并不等价。 - **私钥与因数分解**：虽然RSA问题与因数分解不等价，但计算RSA的私钥d在计算上等价于分解RSA模数n。 - **定理9.1**：设< e, n >是RSA公钥，给定私钥d，可以有效地分解模数n = pq；反之，给定n = pq的分解，可以有效地恢复d。 - **证明**： - **第一部分**：若能分解RSA模数n = pq，可计算φ(n) = (p - 1)(q - 1)，然后使用扩展欧几里得算法计算私钥d。 - **第二部分**：假设已知私钥d，设ed - 1 = 2sk（k为奇数），可以使用算法19分解RSA模数n。该算法基于模n下1的平方根的某些事实，若x2 = 1 (mod n)，则模n下1有四个平方根，其中两个是平凡的±1，另外两个是非平凡的，且在模n下互为相反数。若x是模n下1的非平凡平方根，则x2 = 12 (mod n)但x ≠ ±1 (mod n)，通过计算gcd(x + 1, n)和gcd(x - 1, n)可找到n的因数。 ```plaintext Algorithm 19 RSA Factor (n,e,d) INPUT: e,d,n, (Comments - we are a ```