RSA 一些进阶攻击方式及变体

RSA 进阶攻击：

1.Rabin：

一个密文可以解出四个明文（并非单射）

具体实现：

取两个大素数 (p,q)
满足：

$$p \equiv q \equiv 3 \pmod4$$

加密：

$$c=m^{2} \pmod n$$

解密，即求解：

$$m^{2} \equiv c \pmod n$$

因为 p,q | n ,相当于求

$$\begin{cases} m^{2}\equiv c \pmod p \\ m^{2}\equiv c \pmod q\end{cases}$$

c 是模 p 的二次剩余
即：

$$c^{\frac{p-1}{2}}\equiv 1 \pmod p$$

代入原式得：

$$m^{2}\equiv c \equiv c^{\frac{p-1}{2}} \cdot c \equiv c^{\frac{p+1}{2}} \pmod p$$

开方得：

$$\begin{cases} m1 \equiv c^{\frac{p+1}{4}} \pmod p \\ m2 \equiv (p-c^{\frac{p+1}{4}}) \pmod p\end{cases}$$

同理，可求出 m3,m4 。

注：

若：

$$x^{2}\equiv a \pmod p$$

则称 a 为关于模 p 的二次剩余，p 为素数。
有

$$(\cfrac{a}{p})=a^{\frac{p-1}{2}}\equiv 1 \pmod p$$

ex:

from gmpy2 import *
from Crypto.Util.number import *
p= 13934102561950901579
q= 14450452739004884887
n = 201354090531918389422241515534761536573
c = 20442989381348880630046435751193745753
e=2
c1=pow(c,(p+1)//4,p)
c2=pow(c,(q+1)//4,q)
cp1=p-c1
cq1=q-c2
t1=invert(p,q)
t2=invert(q,p)
m1=(c1*q*t2+c2*p*t1)%n
m2=(c1*q*t2+cq1*p*t1)%n
m3=(cp1*q*t2+c2*p*t1)%n
m4=(cp1*q*t2+cq1*p*t1)%n
print(long_to_bytes(m1))
print(long_to_bytes(m2))
print(long_to_bytes(m3))
print(long_to_bytes(m4))

2.dp,dq 泄露

条件：

知道 $d_p$,$d_q$,p,q,c ,但不知道 e

$d_p$,$d_q$ 的含义:

$$d_p=d \pmod {(p-1)}$$ $$d_q=d \pmod {(q-1)}$$

记方程：

$$\begin{cases} m_1=c^{d} \pmod p \\m_2=c^{d} \pmod q \end{cases}$$

根据欧拉降幂，可知：

$$\begin{cases} m_1=c^{d_p \pmod {(p-1)}} \pmod p \\m_2=c^{d_q \pmod {(q-1)}} \pmod q \end{cases}$$

从而得到 $m_1$,$m_2$
将 $c^{d}=kp+m_1$ 代入 $m_2$ 得

$$m_2 \equiv (kp+m_1) \pmod q$$

同时减去 $m_1$ 得：

$$(m_2-m_1)\equiv kp \pmod q$$ $$(m_2-m_1)p^{-1}\equiv k \pmod q$$

因为 m<n ,所以 k 一定小于 q ,所以 $k=(m_2-m_1)p^{-1} \pmod q$
从而得出：

$$m=c^{d}=((m_2-m_1)p^{-1} \pmod q)p+m_1$$

3.dp 泄露：

条件：

知道 $d_p$,$d_q$ 之一，且知道公钥。
不妨设知道 $d_p$:

$$\because d_p =d \pmod {(p-1)}$$ $$\therefore d=k_1(p-1)+d_p$$

有：

$$ed=k_1e(p-1)+d_pe$$ $$ed \equiv 1 \pmod{\varphi(n)}$$ $$\therefore k_1e(p-1)+d_pe=k_2\varphi(n)+1$$ $$\therefore ed_p=(p-1)[k_2(q-1)-k_1e]+1$$

已知 $d_p<p-1$,所以当 $[k_2(q-1)-k_1e]=e$ 时，左式一定小于右式。
设 $X=[k_2(q-1)-k_1e]$,当 $X$ 遍历 $[1,e]$ 时,一定会存在某个值使等式成立

$$p=\cfrac{ed_p-1} {X}+1$$

从而分解 n 。
ex:

from gmpy2 import *
from Crypto.Util.number import *
import libnum
n= 93172788492926438327710592564562854206438712390394636149385608321800134934361353794206624031396988124455847768883785503795521389178814791213054124361007887496351504099772757164211666778414800698976335767027868761735533195880182982358937211282541379697714874313863354097646233575265223978310932841461535936931
dp=307467153394842898333761625034462907680907310539113349710634557900919735848784017007186630645110812431448648273172817619775466967145608769260573615221635
c=52777705692327501332528487168340175436832109866218597778822262268417075157567880409483079452903528883040715097136293765188858187142103081639134055997552543213589467751037524482578093572244313928030341356359989531451789166815462417484822009937089058352982739611755717666799278271494933382716633553199739292089
e=65537
for i in range(1,e):
    if (e*dp-1)%i==0:
        p=((e*dp-1)//i)+1
        if isPrime(p) and isPrime(n//p):
            break


q=n//p
d=invert(e,(p-1)*(q-1))
m=pow(c,d,n)
m=long_to_bytes(m)
print(m)

4.Schemidt Samoa 密码体系：

加密方式：

加密方式与 RSA 类似,计算：

$$n=p^{2}q$$ $$dn\equiv1 \pmod{\varphi(pq)}$$ $$c=m^{n} \pmod n$$

解密：

计算：

$$m=c^{d} \pmod{pq}$$

证明：

根据欧拉函数性质：

$$(x,n)=1$$ $$x^{\varphi(n)}\equiv 1 \pmod n$$

则

$$x^{nd}\equiv x^{nd \pmod{(p-1)(q-1)}}\equiv x\pmod{pq}$$

因此：

$$x^{nd}-x\equiv 0 \pmod{pq}$$ $$\therefore pq|x^{nd}-x$$

因此：

$$pq=gcd(x^{nd}-x,n)$$

即可得到 p,q 。
从而：

$$c^{d}\equiv m^{nd}\equiv m^{nd \pmod{(p-1)(q-1)}} \equiv m \pmod {pq}$$

5.求二次剩余:

Tonelli-Shanks 算法：

算法过程:

求同余式： $x^{2}\equiv n \pmod p$

• 1.分解 p-1 , 使其满足 $p-1=q*2^{s}$
• 2.如果 p 满足 $p\equiv 3\pmod 4$, 则返回 $r=n^{\frac{p+1}{4}}$

• 上式的正确性证明：

• $$r^{2}=n^{\frac{p+1}{2}}$$
• 因为 n 是 p 的二次剩余,所以 $n^{\frac{p-1}{2}}\equiv 1 \pmod p$
• 所以 $r^{2}=n^{\frac{p-1}{2}+1}\equiv n \pmod p$ ,则 $x=r$
• 3.若不满足上述条件，则找一个整数 z 使其是模 p 的二次非剩余(最好 z 是最小的)
• 计算： $c\equiv z^{q} \pmod p$ , $r=n^{\frac{q+1}{2}} \pmod p$ , $t=n^{q} \pmod p$ , m=s
• 4.进行外层循环：
• 若 t 满足 $t\equiv 1 \pmod p$ ,则返回结果 r ,否则进入内层循环
• 5.内层循环：
• 找一个最小的 i ,使得 $t^{2^{i}}\equiv 1 \pmod p$ 并进行以下计算：
• $$b=c^{2^{m-i-1}} \pmod p$$
• $$r=r*b \pmod p$$
• $$c=b*b \pmod p$$
• $$t=t*c \pmod p$$
• $$m=i$$
• 不断进行内层循环，直至 $t\equiv 1 \pmod p$

• 正确(必要)性检验:

• 当满足循环退出的条件时
• $$t=n^{q}*z^{q*2^{m-i}}\equiv 1 \pmod p$$
• 此时
• $$r=n^{\frac{q+1}{2}}*z^{q*2^{m-i-1}}$$
• $$r^{2}=n^{q+1}*z^{q*2^{m-i}}\equiv n \pmod p$$
• (充分性检验略去)

  注:

  勒让德符号：
  p 是素数： $$(\cfrac{a}{p})=\begin{cases} 1 \ \ ( a 是模 p 的二次剩余) \\ -1 \ \ ( a 是模 p 的二次非剩余) \\ 0 \ \ ( p 整除 a ) \end{cases}$$