RSA

RSA及非对称密码学简介

非对称密码学

经典的加密/解密系统都是对称密码学（亦称“私钥密码学”），其中加密方和解密方使用相同密钥。
而在计算机网络环境中，密钥的管理与分发将成为一个难题；同时加密和解密所需的权限相同（即拥有加密权限的人也拥有解密权限），不利于权限控制等。

非对称密码学（亦称“公钥密码学”）采用的加/解密方法中，加密方和解密方的密钥不同。称加密方的密钥为“公钥”，解密方的密钥为“私钥”。

一般称加密“公钥”为 public 的原因是多数场景下，加密所需的权限比解密低。

实践中，公钥是（相对地）可以公开的密钥集，私钥则需要保密。
公钥和私钥的关系在于：

• 私钥是由公钥决定的（即公、私钥之间存在某种数学联系，这种数学联系因加密方式不同而异），生成密钥时二者相伴而生，搭配使用。
  
• 加密方式的安全性依赖于某个数学难题，攻击者即使已知公钥和加密方式，由于该数学难题的存在，亦很难从中获得私钥（计算上不可行）。

其中，非对称加密算法都涉及到“陷门函数”(trapdoor function)的使用：类似于二极管，通过陷门函数正向计算时非常简单，但逆向计算时极为困难。

不同于哈希函数(Hash Functions)的是，陷门函数是可逆的，只是在参数满足一定条件时，逆映射在计算上不可行。

非对称密码学的应用极为广泛，比较常见的场景包括：

• 不可靠信道下的密文传输
  
• 密钥交换与分发
  
• ...

RSA：非对称密码学的朝阳

RSA于1977年由Ron Rivest, Adi Shamir和Leonard Adleman共同提出，是第一种被极广泛应用（且至今依然被大量使用）的非对称加密算法。
RSA依赖的数学难题是大整数分解难题：
给定 \((p,q)\)，计算 \(N = pq\) 很容易，但给定 \(N\)，找到满足 \(pq = N\) 的 \((p,q)\) 是困难的。

密钥生成

1. 选择大质数 \(p,q\) 且 \(p \neq q\)，计算 \(N = pq\)。
   
2. 计算 \(\varphi(N) = (p-1)(q-1)\)，其中 \(\varphi(N)\) 表示N的欧拉函数值。
   
3. 选择整数 \(e\) 且 \(gcd(e,\varphi(N)) = 1\)（即 \(e\) 与 \(\varphi(N)\) 互质），计算 \(d = e^{-1} (\bmod \varphi(N))\)。
   
4. 将 \(p,q\) 的记录销毁，\((N,e)\) 为公钥，\(d\) 为私钥。

第三步后半部分中，\(d\) 是 \(e\) 关于 \(\varphi(N)\) 的模逆元；换言之，\(d\) 是满足 \(ed \equiv 1 (\bmod \varphi(N))\) 的最小正整数。
要求 \(e\) 与 \(\varphi(N)\) 互质的原因是，若不然，则 \(e\) 在 \(F_{\varphi(N)}\) 下的逆元不存在。

加密/解密

加/解密前，首先需要将信息编码为一个正整数 \(m\)，且 \(m < N\)。
若消息比较长，可以将消息分成多段，保证每一段待加密的 \(m_i < N\)。

加密：
加密方计算 \(c = m^e \bmod N\)，\(c\)即为密文。

解密：
解密方计算 \(m = c^d \bmod N\)，\(m\)即为明文。

正确性证明

显然我们有 \(m_c = (m^e)^d \bmod N = m^{ed} \bmod N\)。

• 若 \(gcd(m,N) = 1\)，又 \(ed \equiv 1 (\bmod \varphi{N})\)，故由欧拉定理知其成立。
  
• 若 \(gcd(m,N) = k \neq 1\)，则显然 \(gcd(\frac{m}{k},\frac{N}{k}) = 1\)。
  考虑 \(m^{ed} = \frac{m}{k}^{ed}k^{ed}\)，同理有 \(\frac{m}{k}^{ed} \equiv \frac{m}{k} (\bmod N)\)；
  又因 \(N = pq\)，则必有 \(k = lp\) 或 \(k = lq\) 成立(\(k \in Z\))，以 \(k = lp\) 为例说明（另一者互偶，同理）：
  \(k^{ed} = (lp)^{ed} = l^{ed}p^{ed}\)，同时有 \(p^{ed} \equiv mp (\bmod N) (m \in Z)\)，

RSA应用

RSA的应用场景包括：

• 少量信息的加密（参考bytes_to_long，信息不太大时可以直接以RSA加密）；
  
• 密钥的加密传输，现实中考虑到计算效率等问题，常用非对称密钥体系完成密钥交换/传输，随后再使用对称加密体系进行主要通信内容的加密；
  
• 用于数字签名，此时公私钥的位置“互换”。

简单说下 bytes_to_long 的原理：
计算机中，将字节转化为整数的方式是将这些字节以十六进制方式并列写出（并将“拼凑”成的十六进制串直接转化为十进制）。
如，字节\x50对应的整数就是80；字节\x50\x50对应的整数则是80*256+80（大端序下），即20560。
显然，\(n\) 个字节的信息对应的整数 \(m \in [0,2^{8n})\)，故随着消息长度变长，一段消息转化而成的整数会急剧膨胀。
这点对于中文信息尤为明显。使用unicode编码时一个汉字会被编码成三个字节，即使在中文编码gb2312中，一个汉字亦会被编为两个字节，参考如下代码的输出：

from Crypto.Util.number import *

print(bytes_to_long('你好'.encode('gb2312'))) #3303258819
print(bytes_to_long('剑歌飒沓访云屋'.encode('gb2312'))) #3846346832410219639926018479148765
print(bytes_to_long('世界人民大团结万岁').encode()) # 94090383611140304887381919181091888735613186691794682179454612097

注：Python3中对int类加入了from_bytes和to_bytes方法来实现字节和整数之间的转换但笔者觉得用着还是不习惯，继续pycryptodome启动

RSA-Attacks: Past

针对RSA，最简单的攻击方式就是因数分解了。只要能获取到满足 \(pq = N\) 的 \((p,q)\)，就可以通过 \((p,q,e)\) 计算获得私钥 \(d\)，进而完全攻破RSA。
给一个简单的（以至于可以口算）的实例：

已知RSA的公钥为 \((N,e) = (55,3)\)，计算私钥 \(d\)。
解：显然 \((p,q) = (5,11)\)，计算 \(\varphi(N) = (p-1)(q-1) = 40\)。
经过盲猜+肉眼观察计算可得 \(e^{-1} \bmod \varphi(N) = 27\)，故私钥为 \(d = 27\)。

在密码学应用中，一般建议N至少为2048位（即 $N > 2^{2048} = $ 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656）。

普通的个人计算机可以在不太长（几秒至几小时内）分解 \(N<2^{512}\)。
分解 \(N\)的方法有很多，稍加改善的手搓法（遍历\(i \in (2,\sqrt{N})\) 的所有奇数）对于 \(N<2^{128}\) 来说都是极其高效的。
对于稍大一些的 \(N\)，通用的分解方法包括二次筛选法、椭圆曲线分解法、普通数域筛选法（目前因数分解复杂度最低的非量子计算方法）等。

同时，若质数 \(p,q\) 选取不当，则可能存在其它投机取巧之法，如 \((p,q)\) 相差太小时，攻击者可以从 \(\lceil \sqrt{N} \rfloor\) 向上/下枚举爆破；\((p,q)\) 相差太大时试除即可攻破之（因数分解的复杂度取决于较小的因子大小）。

约定factor()函数返回一个数的因子：

def factor_attack(N:int,e:int):
    p,q = factor(N)
    phi = (p-1)*(q-1)
    d = pow(e,-1,phi)
    return d

是不是非常简单？您现在已经完全掌握RSA了，快来CTF的世界里大战各种ezRSA吧

RSA-Attacks: Present

比较“普通”的RSA攻击一般针对 \(p,q\) 以外某些参数的选取不当，或应用时获得了一些额外信息。
针对RSA的攻击大致可分为两级：
- 获得私钥 \(d\)（无论是通过分解 \(N\) 还是其它方法使然）；
- 仅解出密文 \(c\) 对应的明文 \(m\)。

任何加密算法的成长都是在不断应对针对它的攻击中进行的，因此下述在介绍攻击方式后，亦会附上防范此类攻击的参数选择要点。

共模攻击

如果同一个明文 \(m\) 被相同的 \(N\)，两个互质的 \(e\) 加密，则其会受到共模攻击而被解出 \(m\)。

假设公钥对是 \((N,e_1)\) 和 \((N,e_2)\) 且 \(gcd(e_1,e_2) = 1\)，
根据RSA加密算法可知 \(c_1 = m^{e_1} \bmod N\)，\(c_2 = m^{e_2} \bmod N\)。

而根据扩展欧几里得算法(extended gcd)，\(gcd(e_1,e_2) = 1\)时，必定存在 \(k_1,k_2 \in Z\) 使得 \(k_1e_1 + k_2e_2 = 1\) 成立，且对 \(k_1,k_2\) 的计算是极其高效的。
在获得 \((k_1,k_2)\) 后，原式中存在：
\(c_1^{k_1}c_2^{k_2} = m^{e_1k_1}m^{e_2k_2} = m^{e_1k_1+e_2k_2} = m \bmod N\)。

攻击代码：

from gmpy2 import gcdext

def module_attack(N:int,e1:int,e2:int,c1:int,c2:int):
    k1,k2 = gcdext(e1,e2)
    m = pow(c1,k1,N) * pow(c2,k2,N)
    return m

防御措施：
避免复用公钥模数 \(N\) （当然看下面的广播攻击，结论是RSA加密中尽量避免复用公钥组 \((N,e)\) 中的任何一项）。

低加密指数攻击

• 对于比较小的e，若待加密明文过小且参数e也太小，导致 \(m^e < N\) （或 $c = m^e + kN $ 中 \(k\) 过小），则可以直接开方或枚举 \(k\) 的值来获得明文。
  如下述实例：

N = 15067247495220337739044658580299422870743900516291641900709982926345667445039146043233960939583805867654877804217823602164965308434379916314531787544484331879416867309985969107571009640793541373033817591265862576042098374671328353177269157927530773089919450474387718226408886464418934301939562552412210432078973011198275525131589077112707811244813014186842704804798516862080895193027541400001107109348059144275554795461055553022886195506734038234367433077440246383581544003867276627576721675797264983653531410560174664964798418527973330630833350627208925524624696705806770455875901332452920931280846343304764406432431
e = 3
m = int.from_bytes(msg)
print(f'c={pow(m,e,N)}')
# c = 56904331863513826993889193197580675994130972045548192078570591022171553205166868384632082720292597125

显然由于N太大，e太小且待加密的信息太小，因此会受到低解密指数攻击（直接开三次根即可）。

防御措施：

• 不选择太小的e；
  
• 加密前对消息进行填充(padding)，使之达到与N相近的长度。

盲目选择较大的e可能会导致计算负载变大，故在很多密码学应用中可以看到e = 65537的声明，因其可表示为0x10001，计算速度快（参考快速幂取模算法），且是较大的质数，易于满足 \(gcd(e,\varphi(N)) = 1\)的要求。

广播攻击

先介绍一下韩信点兵CRT(Chinese Remainder Theorem，中国剩余定理)：

假设存在以下的同余方程组：
\(\begin{align*} x &\equiv r_1 (\bmod m_1)\\ x &\equiv r_2 (\bmod m_2)\\ \vdots \\ x &\equiv r_n (\bmod r_n) \end{align*}\)
且 \(m_1,m_2,\cdots,m_n\) 两两互质，记 \(S = \prod_{i=1}^{n} m_i\)，
则该方程组在模 \(S\) 意义下必定有且仅有唯一解；整数域 \(Z\) 下的通解由下式给出：
记 \(M_i = \frac{S}{m_i}\)，\(t_i \equiv M_i^{-1} (\bmod m_i)\)，则 \(x = \sum_{i=1}^{n} r_it_iM_i + kS (k \in Z)\)。

其应用场景为当一个明文被相同的 \(e\) 和不同的模数 \(N\) 加密多次后，可以通过CRT得到其通解，当该通解满足 \(\prod_{i=1}^{n} N_i > m^e\) 时，取 \(k=0\) 的特解得到的必定是 \(m^e\) 的值。

from Crypto.Util.number import *
from functools import reduce

class RSA:
    def __init__(self):
        self.e = 17
        self.m = int.from_bytes(msg)

    def encrypt(self):
        N = getPrime(512) * getPrime(512)
        c = pow(self.m,self.e,N)
        return N,c
    
if __name__=='__main__':
    rsa = RSA()
    Nlist = []
    clist = []
    for _ in range(17):
        n_,c_ = rsa.encrypt()
        Nlist.append(n_)
        clist.append(c_)

    S = reduce(lambda x,y: x*y, Nlist)
    Mlist = [S//Nlist[i] for i in range(17)]
    tlist = [pow(Mlist[i],-1,Nlist[i]) for i in range(17)]

    result = 0
    for i in range(17):
        result += clist[i]*Mlist[i]*tlist[i]
        
    result %= S
    print(f'm = {result}')

sagemath中内置了crt函数，直接调用之即可：

#sage
Nlist = ...
clist = ...
e = 17

m = crt(Nlist,clist) ^ (1/e)

可以发现，若 \(m\) 与 \(N_i\) 位数相近，则必须要 \(e\) 组数据才能让CRT获得解。而在数据量较大时 \(\prod_{i=1}^{n} N_i\) 会急速膨胀，故在 \(m^e\) 较大时此方法在计算上并不可行。

防御措施：

• 依然需要避免加密过小的明文或令 \(e\) 的值太小；
  
• 避免复用 \((N,e)\) 进行加密。

低解密指数攻击

如果解密指数 \(d\) 太小，可能会受到低解密指数攻击（又名“连分数攻击”，Wiener's Attack）。

Wiener's Attack的成立条件是 \(p < q < 2p\) 且 \(d < \frac{1}{3}N^{\frac{1}{4}}\)。

RSA中存在等式 \(ed \equiv 1 (\bmod \varphi(N))\)，即 \(ed = k\varphi(N) + 1 = k(N-p-q+1) + 1 (k \in Z)\)。
由于N很大，且 \(N >> p,q >> 1\)，故 \(ed < kN\)，但同时 \(\frac{e}{N} \approx \frac{k}{d}\)。
左侧式是一个已知量，此时我们可以将之展开为连分数，遍历每一组近似解，就可能找到右侧的 \((k,d)\)（\(k,d \in Z\)）。

Wiener证明了在满足上述引用中的条件时，对 \(\frac{e}{N}\) 进行连分数遍历会精准覆盖 \(\frac{k}{d}\)。

连分数的拓展知识：
连分数就是“分母是带分数/连分数的分数”，如 \(\frac{1}{1+\frac{1}{3}}\) 就是一个连分数。
事实上连分数只是分数的表示形式之一，任何一个连分数都可以被“归并”成一个普通分数，
如 \(\frac{1}{1+\frac{1}{3}} = \frac{1}{\frac{4}{3}} = \frac{3}{4}\)。

同时，任何一个分数都可以通过欧几里得算法（辗转相除）被唯一地分解为分子恒为1的连分数。
证明：设存在假分数 \(x = \frac{a}{b} > 1\)，记 \(d = \lfloor \frac{a}{b} \rfloor\)，\(r = a \bmod b\)，则 $r $ 时 \(x = d + \frac{r}{b}\)，且 \(\frac{r}{b}\) 必是真分数。
对任意的真分数，存在 \(\frac{r}{b} = \frac{1}{\frac{b}{r}}\)，显然 \(\frac{b}{r}\) 又是一个假分数，则可以递归地依上述之法分解为带分数，以此类推，直至某次计算时 \(r = 0\)。
由此，我们约定对于一个真分数 \(\frac{x}{y} = \frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\cdots}}}\)，则记将之分解为连分数的结果为 \(\{a_1,a_2,\cdots,a_n\}\)。

举例：分解 \(\frac{232}{335}\)。 显然我们只需要对 \((232,335)\) 进行辗转相除即可，每次记录其商，并将除数和余数分别做下一次的被除数和除数： \(335 \div 232 = 1 \cdots 103, 232 \div 103 = 2 \cdots 26, 103 \div 26 = 3 \cdots 25, 26 \div 25 = 1 \cdots 1, 25 \div 1 = 25 \cdots 0\)
故分解结果即为 \((1,2,3,1,25)\)。

连分数还原成普通分数的原理，则类似于拓展欧几里得算法解二元方程的执行过程。

class ContinuedFraction:
    def __init__(self,n:int,d:int):


    def __next__(self):


if __name__=='__main__':
    

在sagemath中亦内置了求解连分数的函数sage magic再体验.py：

#sage
N = 8633
e = 700

cf = continued_fraction(e/N)
print(cf) #[0;12,3,233]

Wiener's Attack还有一个更便捷的格(lattice)形式，参考格。

防御措施：

• 校验 \(d\) 的位数，避免 \(d\) 过小。很显然d过小比e过小要致命的多

dp,dq 泄露攻击

\(dp\) 和 \(dq\)，形如其名，和 \(d,p,q\) 三个RSA中的关键参数有关，目的是在RSA中实现快速解密，降低计算负载。

具体地，\(dp = d \bmod p-1\)，\(dq = d \bmod q-1\)。解密方拥有 \((p,q,dp,dq)\) 时可进行对消息的解密：
根据欧拉定理，存在 \(\begin{align*} c^{dp} &\equiv c^d \bmod p \\ c^{dq} &\equiv c^d \bmod q \end{align*}\)，
又因为 \(p,q\) 显然互质，则根据中国剩余定理(CRT)，预先计算 \(t_p \equiv p^{-1} (\bmod q)\) 和 \(t_q =\equiv q^{-1} (\bmod p)\)，
则记 \(m_p = c^{dp} \bmod p\) 和 \(m_q = c^{dq} \bmod q\)，存在 \(m = (qt_qm_p + pt_pm_q) \bmod pq\)。

但若 \(dp,dq\) 及一些其它关键参数发生泄露，就可能令RSA被攻破。

攻击一：已知(N,e)和(dp,dq)之一

为便于辨识记号，将 \(dp\) 记作 \(d_p\)。

显然有 \(ed_p \equiv 1 (\bmod (q-1))\) 与 \(ed \equiv 1 (\bmod (p-1)(q-1))\) 成立。

转化为等式，\(ed_p + k_1(p-1) = ed\) 及 \(ed + k_2(p-1)(q-1) - 1 = 0\)，\(k_1,k_2 \in Z\)，联立得 \(ed_p + [k_2(q-1)+k_1](p-1) - 1 = 0\) 成立。
又，\(d_p = d \bmod p-1\) 则显然有 \(d_p < p-1\) 成立，又以 \(e,d_p >> 1\)，记 \(X = -(k_2(q-1)+k_1)\)，则 \(X \in (0,e),X \in Z\)。

当 \(e\) 不大时点名批评65537，可以枚举爆破 \(X\)，逐个校验 \(p = \frac{ed_p-1}{X} + 1\) 是否为 \(N\) 的非平凡因子，即可分解 \(N\)。

def factor_dp(N:int,e:int,dp:int):
    for i in range(1,e):
        if (e*dp - 1) % i == 0:
            fc = (e*dp - 1) // i
            if N % (fc + 1) == 0:
                return fc + 1, N % (fc + 1)

攻击二：已知(N,dp,dq)

若已知 \(d_p = d \bmod p-1\)，\(d_q = d \bmod q-1\)，

光滑数攻击

即使 \(N\) 确实是两个大质数 \(p,q\) 的乘积，但这两个质数可能是脆弱的“光滑数”(Smooth number)。

光滑数是指可以分解为小质数之积的大整数。
若一个数 \(n\) 满足 \(n = \prod_{i=1}^{n} p_i^{e_i}\) 且 \(p_i \leq B\)，则称 \(n\) 是一个 \(B\)-光滑数(\(B\)-smooth number)。

p-1

对于 \(N = pq\)，若已知 \(p-1\) 是一个光滑数，则可以采用 Pollard's p-1 Algorithm 对 \(N\) 进行分解。

根据费马小定理，\(gcd(a,p) = 1\) 时，存在 \(a^{p-1} \equiv 1 (\bmod p)\)。考虑 \(p\) 是质数且 \(a\) 不是 \(p\) 的倍数时，其显然成立。
推广得，\(a^{K(p-1)} - 1 | p\)，等价于只需计算 \(gcd(a^{K(p-1)} - 1,N)\) 即可（极大概率）得到 \(p\)。
而在不知道 \(K(p-1)\) 的情况下，应当如何计算 \(a^{K(p-1)}\)？

一种方法是瞎猜大法考虑到 \(p-1\) 的素因子都很小，故计算 \(B!\) 即可有很大把握覆盖所有的 \(p-1\) 的素因子。

对于这一步，可以通过一个实例来理解：假设 \(p = 61, p-1 = 60 = 2^2 \times 3 \times 5\)，那么我们计算 \(5! = 120\) 就已经覆盖了所有的 \(p-1\) 的素因子（目标显然就是整除 \(p-1\)）。

p-1 Algorithm 实践中有两个要点：

• \(B!\) 可能会非常大，且对 \(a^{B!}\) 的计算可在 \(Z (\bmod N)\) 下进行，故应利用幂取模公式进行迭代计算，即 \(\forall i > 2, a^{i!} \bmod N = (a^{(i-1)!} \bmod N)^{i} \bmod N\)。
  
• 由于只需要 \(gcd(a,p) = 1\) 即可满足求解要求，且已知 \(p\) 为奇数，故为了提高计算效率，一般选择 \(a = 2\)。

每次迭代后，若计算 \(gcd(a^{i!},N)\) 不为 \(1\) 或 \(N\)，则已经成功分解 \(N\)（所谓 non-trivial factor ，即“非平凡因子”）。

def factor_smooth(N:int):
    a = 2
    i = 2
    while True:
        a = pow(a,i,N)
        res = gcd(a,N)
        if res != 1 and res != N:
            return res, N // res
        i += 1

关于 Pollard's p-1 Algorithm 的数论部分更深入探讨（选看）：

1. 上述方法的时间开销可能会远大于预期，因为可以注意到我们用 \(B!\) 覆盖 \(p-1\) 的素因子时极容易存在疏漏。
   对于素因子的幂数较高的 \(p_i\)，其可能要往上额外遍历数次才能完全覆盖之。如考虑 \(p-1 = 2738 = 2 \times 37^2\) 的情况，若用 \(B!\) 之法覆盖之，不难发现其必须计算到 \(2^{74!} \bmod N\) 才能得出结果。存在多个较大的高阶素因子时，其时间开销更大。
2. 关于 \(gcd(a^{i!},N)\) 结果的分析： 若 \(gcd(a^{i!},N) = 1\)，说明 \(i!\)（或该幂数）没有覆盖 \(p-1\) 的素因子，此时应当增大 \(B\)（幂数上界）；
   若 \(gcd(a^{i!},N) = N\)，此时 \(i!\)（或该幂数）同时已经覆盖了另一个质数与1之差 \(q-1\) 的全部素因子。

同时，上述算法实际上针对RSA的分解需求进行过调整。原版的 p-1 Algorithm 描述如下：

1. 选定一个光滑数上界 \(B\)；
   
2. 标定 \(M = \prod_{i=1}^{n} q_i^{\lfloor \log_{q_i}B \rfloor}\)，其中 \(\{q_i\}\) 是小于 \(B\) 的全部质数；
3. 随机选定与 \(N\) 互质的整数 \(a\)；
   
4. 计算 \(g = gcd(a^{M}-1,N)\)；
   
5. 若 \(g \notin \{1,N\}\)，则分解成功，\(g\) 就是 \(N\) 的一个素因子。否则或分解失败，或做以下调整再进行计算：
   • 若 \(g = 1\)，适当增大 \(B\)；
     
   • 若 \(g = N\)，适当减小 \(B\)。

• 实际上由于锚定的 \(N\) 是奇数（不是奇数的话先除到奇数），故一般都取 \(a = 2\) 来加快计算速度。
  
• \(g = 1\) 在极少数情况下可能是选取的 \(a\) 在 \(Z(\bmod N)\) 中的阶过小所致。
  
• “标定”的含义是计算 \(gcd(a^M-1)\) 时，并不需要计算出 \(M\) 的具体数值（参考幂取模算法，步步为营）。
  
• 若对于 \(N\) 的全部素因子 \(p_i\)，\(p_i-1\) 的最大素因子相同，则该分解算法必定失败。

防御措施：

• 选择 \(p,q\) 时使用强质数（强质数指 \(p-1\)、\(p+1\) 至少有一个大的素因子的质数 \(p\)）。

Python库 Crypto.Util.number 中除了众所周知的 getPrime函数，还有一个getStrongPrime函数用于产生强质数，其要求锚定的质数bits为128的整数倍且不低于512。

p+1

数论分析攻击

数论分析在实践中的应用非常少，多作为纯“数学”试题出现在CTF赛事中，考察选手的信安数基掌握情况数论功底。

就笔者的乱糊做题经验而言，数论分析题目多涉及到的内容如下：

• 最大公约数(gcd)的灵活运用；
  
• 费马小定理，即若 \(gcd(a,p) = 1\)，则 \(a^{p-1} \equiv 1 (\bmod p)\)（实际上是欧拉定理的特殊情况）；
  
• 同余相关知识的“倒腾”；
  
• 和枚举爆破有关的结合，等等。

已知d时执行对N的分解

当我们获得 \(d\) 后，我们自然可以解密所有加密的消息，但远征之途不止于此——我们还希望对 \(N\) 进行分解。

已知 \(ed \equiv 1 (\bmod \varphi(N))\)，不难得 \(\forall a \in Z_{+}, a^{ed-1} \equiv 1 (\bmod N)\)。
显然 \(ed - 1\) 是一个偶数（因为 \(\varphi(N)\) 必定为偶数）。可令 \(ed - 1 = t2^{s} (s \in Z_{+},t \equiv 1 (\bmod 2))\)。
可证明对于至少一半的 \(a \in Z_{+}\)，\(\exists i \in [1,s]\)，令 \(a^{2^{i-1}t} \not\equiv \pm1 (\bmod N)\) 且 \(a^{2^{i}t} \equiv 1 (\bmod N)\)。
此时 \(gcd(a^{2^{i-1}t} - 1,N)\) 是 \(N\) 的一个非平凡因子（即其不等于1或N，但可以整除N）。

from gmpy2 import gcd

def factor_N_d(N:int,e:int,d:int):
    t = e*d - 1
    s = 0
    while t & 1:
        t >>= 1
        s += 1

    a = 2
    while True:
        const = pow(a,t,N)
        for i in range(1,s+1): 
            if abs(const) != 1 and pow(const,2,N) == 1:
                return gcd(const,N)
            const = pow(const,2,N)
        else:
            a += 1
        

研究 \(Z \bmod(n)\) 的数论中存在不少如此般的“飘渺”算法：每次执行时，其可能得到一个解也可能得不到。
有名的类似算法包括 Pollard's rho algorithm 、 **

“解密”特例： \(e\) 和 \(\varphi(N)\) 不互质

RSA的参数选取中强调了要求 \(gcd(e,\varphi(N)) = 1\)。若不然呢？

由于 \(\varphi(N)\) 从群论的角度看就是 \(Z(\bmod N)\) 群的阶，因而若 \(e\) 不与之互质，则 \(e\) 在 \(\varphi(N)\) 下的逆元不存在，意即此时我们无法完成密文到明文的单射。
但根据拉格朗日定理，记 \(gcd(e,\varphi(N)) = k\)，则可以将 \(e\) 和 \(\varphi(N)\) “抬升”到 \(Z(\bmod N)\) 的一个新子群，新子群的阶就是 \(\frac{\varphi(N)}{k}\)，\(e\) 在其中就有逆元了。

若将该结果代回到RSA解密中，可以注意到其问题就在于我们只能解密出 \(Z(\bmod N)\) 下的 \(m^{k}\)，需要在该域下对之开 \(k\) 次根。

在二次剩余的基础上，通过 AMM Algorithm 可以实现有限域下开任意次根（当然如同二次剩余不一定有解一样，n次根也不一定有解），但大部分情况下其求解耗时会非常长。
关于 AMM Algorithm 的原理和实现可移步论文

sagemath对于 \(Z(\bmod N)\) 下的元素提供了nth_root成员函数，结合sage的蛇皮特性，可以在对 \(m\) RSA求解后的结果直接调用之，无需换环：

#sage

p = 11
q = 7
e = 9
c = 35
n = p * q
phi = (p-1)*(q-1)

k = gcd(e,phi) 
ee = e / k
phii = phi / k
d = pow(ee,-1,phii)

mk = pow(c,d,n)
m = mk.nth_root(k,all=True) 

RSA-Attacks: Future

在RSA中，如果我们可以进行选择明/密文攻击，则在一定场景下存在诸多较为“花哨”的攻击方式。

RSA LSB Orcale

一段：Parity Orcale

Orcale可以理解为一种交互装置，其可以对给定的输入运行密码算法，并按特殊的规则输出（意即其执行的并不是常规的完整加/解密操作，但会返回和加/解密过程有关的信息）。

Parity Orcale又名“奇偶攻击”，本质是一种选择密文攻击。
其描述为：给定一个解密Orcale，其接受任意密文 \(c\) 并解密之，但只会输出计算明文的奇偶性（变种是输出其最后一个/n个字节，本质是 \(\bmod 2\) 和 \(\bmod 16^{n}\) 的区别而已）。
攻击目标是解密一个用对应公钥加密的密文 \(c_0\)。

攻击思路：公钥 \((N,e)\) 公开，同时显然我们有 \(m,c < N\)。
已知 \(m \equiv c^{d} \bmod N\)，
现计算 \(c_1 = c2^e \bmod N\)（等价于 \(c_1\) 就是 \(2m\) 的加密结果），将 \(c_1\) 输入该Orcale，观察输出：
由于其解密的 \(m_1\) 必定满足 \(m_1 \equiv 2m (\bmod N)\)，即 \(m_1 + kN = 2m\)，又以 \(m \in (0,N)\)，故必定有 \(k \in \{0,1\}\)，同时显然 \(N \equiv 1 (\bmod 2)\) 成立，因而：

• 若Orcale返回奇数，则 \(k = 1\)，说明 \(m \in [\lceil \frac{N}{2} \rceil,N)\)；
  
• 若Orcale返回偶数，则 \(k = 0\)，说明 \(m \in (0,\lceil \frac{N}{2} \rceil)\)。

可以发现，其逻辑分析完成后与“二分查找” \(m\) 的值无异。

因此每次将 \(m\) “加倍” （对上一次的 \(c\) 乘以 \(2^e\) 后对 \(N\) 取模）后，都可以通过Orcale返回的奇偶性缩小 \(m\) 的范围：奇数则为上半部分，偶数则为下半部分。
故该算法可以在 \(O(\log_2N)\) 的时间内运行完毕。

代码示例：

class Orcale:
    def __init__(self):
        p = getPrime(1024)
        q = getPrime(1024)
        self.e = 65537
        self.N = p * q
        self.d = pow(self.e,-1,(p-1)*(q-1))
    
    def decrypt(self,c:int):
        return pow(c,self.d,self.N) % 2

    def get_pubkey(self):
        return self.N,self.e

    def get_cipher(self):
        return pow(int.from_bytes(msg),self.e,self.N)

if __name__=='__main__':
    rsa = Orcale()
    N,e = rsa.get_pubkey()
    c = rsa.get_cipher()

    low = 0
    high = N

    while low < high:
        c = c * pow(2,e,N) % N
        mid = high // 2
        if rsa.decrypt(c):
            high = mid
        else:
            low = mid + 1

    result = low
    print(f'result = {result}')

二段：Byte(s) Orcale...?

上述攻击更高难度的形式即为泛化的LSB Orcale，以单字节为例，每次已知 \(m^{'} \equiv m (\bmod 256)\)，即可让上述算法的时间开销降低为当前值的 \(\frac{1}{8}\) 。
实例可见nctf2024-Arcahv-RSA_LSB_Orcale

RSA side channel attack

侧信道攻击简介

Side Channel Attack, 侧信道攻击，指攻击者通过对密码算法运行设备的信号特征等进行分析，从中提取关键信息的攻击。
现实中，此类攻击针对的对象主要有：

• 设计有疏漏的服务端，其在运行过程中泄露了部分关键/非关键信息；
  
• 微型的电子设备，其在运行密码算法时自身的功耗、信号特征等会随运行过程而明显波动。

多数情况下，侧信道攻击会和其它类型的攻击一同使用（即侧信道很可能只是获取部分参数，而非全部）。

快速幂？

RSA中的侧信道攻击主要针对的是快速幂（取模）算法的特征。
数学上，根据幂的递归定义我们可以得到：
\(a^{b+1} = a \cdot a^{b} (a,b \in R; a,b \neq 0)\) 。
因此计算 \(a^b\) 时，我们诚然可以将 \(b\) 个 \(a\) 相乘来获得结果，但如此做的时间复杂度是 \(O(b)\)，在 \(b\) 很大时显然是不现实的。

快速幂的计算思想是将幂数分解为二进制位，对每一个二进制位都只需要乘一次（因为根据幂运算法则，该位对应的乘数可以预先计算）。数学表达就是：
若 \(b \equiv 0 (\bmod 2)\)，则 \(a^b = (a^2)^{\frac{b}{2}}\)；
若 \(b \equiv 1 (\bmod 2)\)，则 \(a^b = a \cdot (a^2)^{\frac{b-1}{2}}\)。
设 \(b\) 是一个 \(k\) 位的二进制数 \(\{b_n b_{n-1} b_{n-2} \cdots b_1 b_0\} (b_i \in \{0,1\})\)，
则 \(a^b\) 可以表示成 \(b_0a \cdot b_1a^2 \cdot b_2a^{2^{2}} \cdots b_na^{2^{n}}\)。
显然 \(a^{2^{n+1}} = (a^{2^{n}})^2\)，故该算法运行的时间复杂度会瞬间降至 \(\log_{2}N\)。

而对于 \(Z \bmod(N)\) 上的幂运算，其分析同理。

def fastexpmod(a:int,b:int,N:int):
    assert a>0 and b>0 and N>0
    res = 1
    while b:
        if b & 1:
            res = res * a % N
        b >>= 1
        a = a * a % N

    return res

显然对于不取模的情况，将对 \(N\) 取模的部分去除即可。

攻击

对于小型的电子设备，快速幂的运算特点就会暴露出一些信息。
如上，当b & 1 == 1 时，每次循环中会额外将res的值进行一次乘数+取模的操作，宏观上其会体现为一个电磁脉冲的峰值。
分析脉冲的谷峰，则可以从中“套取”到幂数的信息；而RSA中最关键的参数（公钥e/私钥d）均作为幂数出现，因此攻击者就有可能通过加/解密过程来获得公钥/私钥。

对于小型的电子设备，其可能只具有（部分的）加/解密功能而并不会直接公开公钥，因此密码分析时公钥不能作为“理所当然”的条件。

RSA N-Orcale

上述中考虑到了RSA中针对 \(e\) 的一种攻击方法（\(d\)同理）。
事实上，在已知 \(N\) 时若我们拥有一个加/解密Orcale，则其相当于去解一个离散对数问题，若 \(e < 2^{64}\) 则其亦能在不太长的时间内破解。
但假如我们连 \(N\) 都不知道呢？

对于 \(N\) 的攻击可以通过选择明(密)文进行（加密/解密Orcale任取其一即可）。
具体地，假设存在一个可以加密任意密文的RSA Orcale，但不知道其公钥 \((N,e)\) 为何。

此时我们可以传递 \(m \in \{2,2^2,2^3,2^4,\cdots\}\) ，收集加密的密文。
设 \(m_i = 2^{i} (i \in Z_+)\)，显然 \(m_i = m_1^{i}\)。
又， \(c_i \equiv m_i^e (\bmod N)\)，推定 \(c_1 \equiv m_1^e (\bmod N)\)，结合上式可得 \(c_1^i - c_i \equiv 0 (\bmod N)\)，即 \(c_1^i - c_i = kN (k \in Z)\)。
在加密了足够多的 \(m_i\) 后，对 \({c_1^i - c_i}\) 求其最大公约数，即可有很大把握得到 \(N\)。

实际上只要构造足够多组的满足 \(c_1 \equiv c_{2}^{e} (\bmod N)\) 的 \((c_1,c_2)\)，收集 \(c_{2}^{i} - c_1\) 并对之求最大公约数就都可以获得解，构造方法不唯一。

from Crypto.Util.number import *
from gmpy2 import gcd

class RSA:
    def __init__(self):
        self.N = getPrime(1024) * getPrime(1024)
        self.e = getPrime(32)
        
    def encrypt(self,m:int):
        return pow(m,self.e,self.N)

if __name__=='__main__':
    rsa = RSA()
    clist = []
    gcdls = []
    for i in range(5):
        clist.append(rsa.encrypt(pow(2,i+1)))

    gcdls = [clist[0]**(i+1) - clist[i] for i in range(1,5)]
    n = gcd(*gcdls)
    print(f'n = {n}')
    

RSA-Attacks: Beyond

可曾听闻格攻击？

增广格

在RSA中，如果私钥 \(d\) 被复用且满足 \(d < N^{\frac{1}{2}}\)，则攻击者可以仅通过一些公钥集 \((N_i,e_i)\) 获得私钥 \(d\)。

考虑 \(ed \equiv 1 (\bmod \varphi(N))\)，即 \(ed + k\varphi(N) - 1 = 0 (k \in Z)\)。
若 \(d\) 比较小，则本质上其可以转化为一个HNP问题：
$ed + k(N-p-q+1) - 1 = 0 $
$ed + kN = k(p+q-1) + 1 $
右侧依然近似等于 \(2k\sqrt{N}\)，作一个CVP问题处理，即找到一个离 \(\begin{bmatrix}2k\sqrt{N_1}&2k\sqrt{N_2}&\cdots&2k\sqrt{N_n}&Cd\end{bmatrix}\) 最近的向量，格由 \(\begin{bmatrix}N_1\\&N_2\\&&\ddots\\&&&N_n\\e_1&e_2&\cdots&e_n&C_0\end{bmatrix}\) 给定。

可以看出它的解法其实非常类似于一种“拓展”的低解密指数攻击。

#sage
class RSA:
    def __init__(self):
        self.d = getPrime(1000)

    def gen_pubkey(self):
        N = getPrime(1024)*getPrime(1024)
        e = pow(self.d,-1,N)
        return N,e

if __name__=='__main__':
    rsa = RSA()

    for i in range(30):

Coppersmith： “小根”之春

关于Coppersmith

固化的消息头

所谓"stereotyped messages"极易受到Coppersmith法的攻击。

RSA的解密问题常形如：给定 \(c \equiv m^e \bmod N\) 中的 \((c,e,N)\)，找出 \(m\)。但若我们可以知道 \(m\) 的一个大致值 \(m^{'}\)，即可试以此法击之。
结合bytes向int的转化情景，一般的应用场景即为该消息存在固定前缀且长度已知。

sagemath中内置了small_roots函数，其接受可选的参数是...

#sage
def pad_trunc(m:bytes,l:int):
    if len(m) > l:
        return m[:l]
    return m.ljust(l,b'\x00')


class RSA:
    def __init__(self):
        self.N = getPrime(1024)*getPrime(1024)
        self.e = 7
        self.d = ZZ(pow(self.e,-1,self.N))
    
    def encrypt(self,m:bytes):
        msg = int.from_bytes(f"Today's message are as follows:{pad_trunc(m,10).hex()}".encode(),'big')
        c = pow(msg,self.e,self.N)
        return c
    
    def get_pubkey(self):
        return self.N,self.e

if __name__=='__main__':
    rsa = RSA()
    n,e = rsa.get_pubkey()

    P.<x> = Zmod(n)[]
    m0 = int.from_bytes("Today's message are as follows:".encode(),'big') << 10 * 4

    f = (m0 + x) ^ e
    res = f.small_roots()

徐徐而间进——高(低)位因子已知

可以发现，Coppersmith法能大显身手的场景主要就和方程组中部分参数的泄露有关，其导致余下的未知量在方程组中是一个小量，进而为攻破其解提供了可能。
另一种比较简单的应用场景是因子的高/低位已知：给定 \(N\)，相较于既往解 \(N = pq\)，现我们只需解 \(N = (p^{'}+x)q\) 中的 \(x\)，其中 \(p^{'} >> x\)。

由于这是一个一次方程，所以给定 \(p\) 的连续高/低位是等效的（参考f.monic()）。

在锚定的未知量 \(x\) 足够小时，Coppersmith即可有较大把握解出其根。

class RSA:
    def __init__(self):
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.N = self.p*self.q
        self.e = 65537
    
    def leak(self):
        return self.N, (self.p >> 335)

if __name__=='__main__':
    rsa = RSA()
    n,p0 = rsa.leak()

    P.<x> = Zmod(n)[]
    f = p0 + x
    xx = f.small_roots()
    p = ZZ(p0 + xx)