算法原理

  • 模 pq\mathrm{pq} 时高次同余方程的求解
    假设 p\mathrm{p} 和 q\mathrm{q} 是不同的素数, 并假设 e≥1e \geq 1, 满足

    gcd⁡(e,(p−1)(q−1))=1\operatorname{gcd}(e,(p-1)(q-1))=1

    则 ee 模 (p−1)(q−1)(p-1)(q-1) 存在逆元， 即

    de≡1( mod (p−1)(q−1))d e \equiv 1(\bmod (p-1)(q-1))

    则同余方程

    xe≡c( mod pq)x^{e} \equiv c(\bmod p q)

    有唯一解 x≡xed≡cd( mod pq)x \equiv x^{ed} \equiv c^{d}(\bmod p q)
  • 安全性分析
    已知 p、qp 、q 时该方程易解，敌手可以计算欧拉函数φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1),然后利用扩展欧几里得算法计算ee对于φ(n)\varphi(n)的乘法逆元dd,然后解密。
    而p、q\mathrm{p、q}未知时,已知公钥(e,n)(e,n)求私钥等价于大数因子分解问题；已知一对(M,C)(M,C)试图还原dd,等价于离散对数问题。

算法流程

  1. 密钥生成过程:
    选择两个大素数 p、qp 、 q, 计算公开模数:

    N=q∗pN=q * p

    选择公开加密指数 e，满足:

    gcd⁡(e,(p−1)(q−1))=1\operatorname{gcd}(e,(p-1)(q-1))=1

  2. RSA 加密过程:
    将明文转化为整数 m\mathrm{m}，使用公钥N计算

    C≡me( mod N)C \equiv m^{e}(\bmod N)

    得到密文CC

  3. RSA解密过程：
    已知p,qp,q,计算dd:

    de≡1( mod (p−1)(q−1))d e \equiv 1(\bmod (p-1)(q-1))

    然后计算明文M：

    M≡Cd( mod N)M\equiv C^d(\bmod N)

==在实际应用中，RSA加解密经过分组的数据段，这些数据段长度相等，固定长度时长度不足的数据段需要进行填充。==

算法实现

  1. 使用快速模幂运算计算，python中使用pow函数可以达到同样的效果。

  2. 一般加密过程e比较小，可以快速实现，但解密时d比较大所以实际中利用中国剩余定理来加快计算：

    m≡cd( mod N)⇒{m1≡cd( mod p)m2≡cd( mod q)⇒{m1≡(c mod p)dmod  (p−1)( mod p)m2≡(c mod q)dmod  (q−1)( mod q)⇒m≡m1Aq+m2Bp( mod N=pq)A=q−1 mod pB=p−1 mod q\begin{aligned} & m \equiv c^d(\bmod N) \\ & \Rightarrow\left\{\begin{array}{l} m_1 \equiv c^d(\bmod p) \\ m_2 \equiv c^d(\bmod q) \end{array}\right. \\ & \Rightarrow\left\{\begin{array}{l} m_1 \equiv(c \bmod p)^{d \mod (p-1)}(\bmod p) \\ m_2 \equiv(c \bmod q)^{d \mod (q-1)}(\bmod q) \end{array}\right. \\ & \Rightarrow m \equiv m_1 A q+m_2 B p(\bmod N=p q) \\ & A=q^{-1} \bmod p \quad B=p^{-1} \bmod q \\ & \end{aligned}

  3. 密钥产生——伪随机数发生器、执行素数判定测试（Miller Rabin）

  4. 安全性优化——密钥生成阶段参数选择（否则会产生参数选取不当攻击）
    (1)使用大素数，同时要求p，q相差很大
    (2)尽量使用强素数p，q,强素数指p-1有很大的素因子。否则若p-1没有很大的质因数，而是由m个较小的质因数p1p2...pmp_1p_2...p_m组成。则p−1=p1a1p2a2...pmamp-1=p_1^{a_1}p_2^{a_2}...p_m^{a_m}，那么，要分解n则相对容易。(有相关论文可以找到详细分解方法)
    (3)d>N14d>N^\frac{1}{4},避免连分式理论

对RSA的攻击方式

因式分解攻击

分解成功后按照算法原理中的内容可以计算得到明文m

参数选取不当攻击

p，q相差要大(但不能过大)

  • ∣p−q∣|p-q|小时，(p−q)24\frac{(p-q)^2}{4}也小，此时(p+q)24\frac{(p+q)^2}{4}稍大于nn，即(p+q)2\frac{(p+q)}{2}稍大于n12n^\frac{1}{2}.

    (p+q)24−n=(p+q)24−pq=(p−q)24\frac{(p+q)^2}{4}-n=\frac{(p+q)^2}{4}-pq=\frac{(p-q)^2}{4}

    那么：

    while x>n12x>n^\frac{1}{2}:
     if x2−n=y2x^2-n=y^2:
     n=(x+y)(x−y)n=(x+y)(x-y)

  • p,q取值差异过大时，可以用开源项目yafu进行分解(过小也可以)，
    使用方法
    安装地址

d特别小，e很大(接近N)

  • 问题描述

    flag = s2n(flag)
    p = getPrime(1024)
    q = getPrime(1024)
    if p < q:
        p, q = q, p
    assert q < p < 2 * q
    phi = (p - 1) * (q - 1)
    N = p * q
    d = randint(0, int(iroot(N, 4)[0]) // 3)
    print(f'N = {N}')
    print(f'd = {d}')
    e = invmod(d, phi)
    print(f'e = {e}')
    c = pow(flag, e, N)
    print(f'c = {c}')

    '''
    N = 21327609432635697635661734492967514868032345219646509293473450728946796929125596264796686608077350282146808431543688814099354946988813695125850734043400446455515569653767982263228375866016212125033017742119349015072822178318196190745694850995570515630230752678292777440574778729120793338895028632923682027496271327472935942662500117169921554840041050071839641224638348524022215169727418319630285293394980617769914591506983043636592739835090149763802884920200300368993239366686843677366099965654860267609759882686378049533310393901183559714507043035045332273502601434654726043496991435324318063462466253726816633686491
    e = 18977835107309220930390004484766560831346929608900345454868912576417879395319152391809677007908654095951324946088077940809180932163517507338773363819836058226479707254933679974004335002153790380237807333376658330135322627930737835299410373663744954613372507542594748704398503555416693543828015836373800739443278657909905379530092958500438988035068330839162959013568315176411267327500693507377318806169025417092598473813234048525222602269176512302545380940501266666455315603787471273429334914051803354595877792553046681362881913923273953799258321308753602286651515092850863999625965095880385885087205694014033060741113
    c = 2951989543787250024227309988919939594167825226148750874062428524625014545445228307222640088545937734380203828988989321941362142365155595290586130523703955533644047842799047518117049515659231726842039527270329713890518786418601487875975864228006745361862477308867519292913016550436143764016127132235503694918940332463597026396960672403183254520332051492462851679089378927071373658225211987354898477962818171916800202243021649078952845125153161320695143579666246174891848723194556125740925439954503389599981696506010841328091656707182777225501527571416356759631836676820899342968642257694841513191347688952532566252238
    '''

  • 攻击原理
    在数学中，连分数或繁分数即如下表达式

    x=a0+1a1+1a2+1a3+1⋱,Lx=a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+\frac{1}{\ddots, L}}}}

    由于 ed≡1( mod φ(N))e d \equiv 1(\bmod \varphi(N)) ，所以存在整数 k\mathrm{k} ，满足

    ed−kφ(N)=1e d-k \varphi(N)=1

    由于 N=pq>q2N=p q>q^{2}, 即 q<Nq<N ，所以

    0<N−φ(N)=p+q−1<2q+q−1<3q<3N⇒∣eN−kd∣=∣ed−kNdN∣=∣1+k(φ(N)−N)dN∣<3kNdN=3kdN\begin{gathered} 0<N-\varphi(N)=p+q-1<2 q+q-1<3 q<3 \sqrt{N} \\ \Rightarrow\left|\frac{e}{N}-\frac{k}{d}\right|=\left|\frac{e d-k N}{d N}\right|=\left|\frac{1+k(\varphi(N)-N)}{d N}\right|<\frac{3 k \sqrt{N}}{d N}=\frac{3 k}{d \sqrt{N}} \end{gathered}

    由于 k<dk<d, 所以 3k<3d<N143k<3d<N^{\frac{1}{4}}, 即

    ∣eN−kd∣<1dN14⇒∣eN−kd∣<13d2\left|\frac{e}{N}-\frac{k}{d}\right|<\frac{1}{d N^{\frac{1}{4}}} \quad \Rightarrow \quad \left|\frac{e}{N}-\frac{k}{d}\right|<\frac{1}{3 d^{2}}

    由连分数理论，此时 kd\frac{k}{d} 是 eN\frac{e}{N} 的一个收敛子：
    计算 eN\frac{e}{N} 的连分数展开, 依次算出每一个渐进分数。因为 eN>kd\frac{e}{N}>\frac{k}{d},所以 eN\frac{e}{N} 的渐进分数覆盖了 kd∘\frac{k}{d^{\circ}} 。 就是说 eN\frac{e}{N} 的渐进分数里有等于 kd\frac{k}{d} 的分数。接着验证 k,dk, d 是否满足条件就求得了 k,dk, d 的值

  • 攻击代码

    # numerator(n):分子, denominator(d)：分母
    def t_cf(n, d):  # 将分数 x/y 转为连分数的形式
        res = []
        while d:
            res.append(n // d)
            n, d = d, n % d
        return res


    def cf(sub_res):    # 得到渐进分数的分母和分子
        n, d = 1, 0
        for i in sub_res[::-1]:  # 从后面往前循环
            d, n = n, i * n + d
        return d, n


    def list_fraction(x, y):     # 列出每个渐进分数
        res = t_cf(x, y)
        res = list(map(cf, (res[0:i] for i in range(1, len(res)))))  # 将连分数的结果逐一截取以求渐进分数
        return res


    def get_pq(a, b, c):  # 由p+q和pq的值通过维达定理来求解p和q(解二元一次方程)
        par = gmpy2.isqrt(b * b - 4 * a * c)  # 由上述可得，开根号一定是整数，因为有解
        x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)
        return x1, x2


    def wienerAttack(e, n):
        for (d, k) in list_fraction(e, n):  # 用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
            if k == 0:  # 可能会出现连分数的第一个为0的情况，排除
                continue
            if (e * d - 1) % k != 0:  # ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
                continue

            phi = (e * d - 1) // k  # 这个结果就是 φ(n)
        
            px, qy = get_pq(1, n - phi + 1, n)

            if px * qy == n:
                p, q = abs(int(px)), abs(int(qy))  # 可能会得到两个负数，负负得正未尝不会出现
                d = gmpy2.invert(e, (p - 1) * (q - 1))  # 求ed=1 (mod  φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
                return d
        print("求解d失败")

    d =  wienerAttack(e,N)
    #print(d)
    m=int(pow(c,d,N))
    flag = n2s(m)
    print(flag)

选择密文攻击/中间人攻击

  • RSA算法具有同态特点，即对任意x1,x2∈Znx_1,x_2\in Z_n,有Ek(x1,x2)=Ek(x1)Ek(x2)E_k(x_1,x_2)=E_k(x_1)E_k(x_2).
    攻击人截获密文cc,发出伪造密文recr^ec(rr为随机数),可以获得对应明文m‘=(rec)d=redcd=rm( mod N)m^`=(r^ec)^d=r^{ed}c^d=rm(\bmod N),得

m=m‘r−1m=m^`r^{-1}

  • RSA-OAEP可抗击适应性选择密文攻击（EUROCRYPT’94，Bellare-Rogaway, Optimal Asymmetric Encryption Padding (OAEP))
    RSA最优非对称加密填充 (RSA-OAEP) 的密钥参数 (N,e,d,G,H,n,k0,k1)\left(N, e, d, G, H, n, k_{0}, k_{1}\right) 满足:

    • (N,e,d)(N, e, d) 是RSA的密钥, 其中
      d=e−1( mod φ(N))d=e^{-1}(\bmod \varphi(N)), 并且 ∣Nf=k=n+k0+k1,n\mid N f=k=n+k_{0}+k_{1}, \mathrm{n} 是明文消息的长度,

    • G,H\mathrm{G}, \mathrm{H}是两个杂湊函数, 且满足G:{0,1}k0→{0,1}k−k0,H:{0,1}k−k0→{0,1}k0G:\{0,1\}^{k_{0}} \rightarrow\{0,1\}^{k-k_{0}}, H:\{0,1\}^{k-k_{0}} \rightarrow\{0,1\}^{k_{0}}

    • 设 (N,e)(N, e) 是Alice的RSA公钥, dd 是私钥。
      加密过程:
      为了发送一个消息 m∈{0,1}nm \in\{0,1\}^{n}, 给Alice, Bob执行以下几步计算:

      • r←U{0,1}k0;s←(m∥0k1)⨁G(r^);t=r⨁H(s)r \leftarrow_{U}\{0,1\}^{k_{0}} ; s \leftarrow\left(m \| 0^{k_{1}}\right) \bigoplus G(\hat{r}) ; t=r \bigoplus H(s)
      • 如果 (s∥t≥N)(s \| t \geq N), 则返回 VaV_{a}
        c←(s∥t)e( mod N)c \leftarrow(s \| t)^{e}(\bmod N)
      • 所得密文为 cc

      解密过程:
      收到密文 cc 后, Alice执行以下几步计算:

      • s∣∣t←cd( mod N)s|| t \leftarrow c^{d}(\bmod N) 满足 ∣s∣=n+k11k−k0,∣t∣=k0|s|=n+k_{1} \underset{k}{1}-k_{0},|t|=k_{0}
      • u←t⨁H(s);v=s⨁G(u)u \leftarrow t \bigoplus H(s) ; v=s \bigoplus G(u)
      • 输出 {m, 若 v=m∥0k1 拒绝, 其他 \left\{\begin{array}{c}m, \text { 若 } v=m \| 0^{k_{1}} \\ \text { 拒绝, 其他 }\end{array}\right.

共模攻击

对于给定的模数N，最多应该只使用一个加密指数，不同用户间不要共享N

  • 攻击原理
    用公开指数e1,e2e_1,e_2加密同一段明文mm，且公开模数NN不变.
    若截获密文
    c1≡m1e(modN)c_1≡m^e_1 (mod N)和 c2≡m2e(modN)c_2≡m^e_2 (mod N)
    可解出u、vu、v: e1u+e2v=gcd⁡(e1,e2)e_1u+e_2v=gcd⁡(e_1,e_2)
    进而 c1uc2v≡me1ume2v≡mgcd⁡(e1,e2)(modN)c_1^uc_2^v≡m^e1um^e2v≡m^{gcd⁡(e1,e2)} (mod N)
    若解得gcd(e1,e2)=1gcd(e_1,e_2)=1，可直接得到mm

低指数广播攻击

同一份明文使用不同模数和相同指数多次加密，可以考虑用中国剩余定理破解，然后直接开e次

c1=me(mod  n1)c2=me(modn2)…cn=me(modnn)⇒me≡x(mod  n1…nn)\begin{gather*} c_1=m^e (mod ~~n_1)\\ c_2=m^e (mod n_2)\\ \dots\\ c_n=m^e (mod n_n)\\ \Rightarrow m^e≡x(mod~~ n_1…n_n) \end{gather*}

e很小时可以直接爆破

循环攻击

在构造n时应选择𝑝和q，使得𝑝-1和q-1有大的素因子。一般选择𝑝和 (𝑝 − 1)/2 均是素数.
否则进行重复加密：

ce≡(me)me2( mod n)ce2≡(me)e2≡me3( mod n)⋯cet−1≡(me)et−1≡met( mod n)cet≡(me)et≡met+1( mod n)\begin{aligned} &c^{e} \equiv\left(m^{e}\right) m^{e^{2}}(\bmod n) \\ &c^{e^{2}} \equiv\left(m^{e}\right)^{e^{2}} \equiv m^{e^{3}}(\bmod n) \\ &\cdots \\ &c^{e^{t-1}} \equiv\left(m^{e}\right)^{e^{t-1}} \equiv m^{e^{t}}(\bmod n) \\ &c^{e^{t}} \equiv\left(m^{e}\right)^{e^{t}} \equiv m^{e^{t+1}}(\bmod n) \end{aligned}

若 met+1≡c( mod n)m^{e^{t+1}} \equiv c(\bmod n), 即 (met)e≡c( mod n)\left(\mathrm{m}^{e^{t}}\right)^{e} \equiv c(\bmod n) ，则有 met≡m( mod n)m^{e^{t}} \equiv m(\bmod n), 即:

cet−1≡m( mod n)=1Nc^{e^{t-1}} \equiv m(\bmod n)=\frac{1}{N}

可以恢复出明文，但这种攻击方式只有在t比较小时才可行，所以t应该很大
met≡m( mod  n),met−1≡1( mod  n)m^{e^t}\equiv m(\bmod~ n),m^{e^t-1}\equiv 1(\bmod~ n)
设m在模n下的阶为kk,k∣et−1⇒et≡1( mod  k)k|e^t-1 \Rightarrow e^t\equiv 1(\bmod~k),所以t∣φ(k)t|\varphi(k),且k∣φ(n)k|\varphi(n),要保证t很大需要p−1,q−1p-1,q-1有很大的素因子，即为强素数。

消息隐藏

用RSA加密后还是本身的点为不动点.ye≡y  mod  ny^e\equiv y~\bmod~n.
由数论和中国剩余定理RSA的不动点总数(详细证明我没了解)为
$$(1 + 𝑔cd(𝑒 − 1, 𝑝 − 1))(1 + 𝑔cd(𝑒 − 1, 𝑞 − 1)$$
因e-1, p-1, q-1均为偶数， RSA的不动点至少有9个。

私钥dd相关信息泄露

定义dp=ddp=d%(p-1),dq=d%(q-1),倘若敌手已知dpdp，可进行如下攻击：

dp=d%(p−1)d=k1(p−1)+dp即ed=ek1(p−1)+dp∗e已知ed≡1 mod φ(N)所以ed=k2∗φ(N)+1所以ek1(p−1)+dp∗e=k2∗φ(N)+1整理得dp∗e=[k2∗(q−1)−k1∗e](p−1)+1因为dp>p−1所以e>[k2∗(q−1)−k1∗e]令X=[k2∗(q−1)−k1∗e](意味着这样的数只有有限个)，穷举即可\begin{gather*} dp=d\%(p-1)\\ d=k_1(p-1)+dp\\ 即ed=ek_1(p-1)+dp*e\\ 已知 ed≡1~mod~φ(N)\\ 所以ed=k_2*φ(N)+1\\ 所以ek_1(p-1)+dp*e=k_2*φ(N)+1\\ 整理得dp*e=[k_2*(q-1)-k_1*e](p-1)+1\\ 因为dp>p-1 所以e> [k_2*(q-1)-k_1*e]\\ 令X=[k_2*(q-1)-k_1*e](意味着这样的数只有有限个)，穷举即可 \end{gather*}