Crypto -- RSA

RSA101

pp, qq为大素数
n=pqn = p*q
phi=(p1)(q1)phi = (p-1)*(q-1)

ee为小于phiphi的素数
ed1modphie*d ≡ 1 \mod phi

ee, nn为公钥; dd, nn为私钥
cmemodnc ≡ m^e \mod n
mcdmodnm ≡ c^d \mod n


dp & dq

mcdmodnm ≡ c^d \mod n
n=pqn = p*q
dpdmod(p1)d_p ≡ d \mod (p-1)
dq=dmod(q1)d_q = d \mod (q-1)

通过pp, qq, dpd_p, dqd_q, cc运算得出mm

mcdmodnm ≡ c^d \mod n
mcdmod(pq)m ≡ c^d \mod (p*q)
mpcdmodpm_p ≡ c^d \mod p
mqcdmodqm_q ≡ c^d \mod q
cd=mp+kppc^d = m_p+k_p*p
cd=mq+kqpc^d = m_q+k_q*p

结合两者可得
mq+kqq=mp+kppm_q+k_q*q = m_p+k_p*p

mqmp+kppmodqm_q ≡ m_p+k_p*p \mod q
kppmqmpmodqk_p*p ≡ m_q-m_p \mod q
kp(mqmp)p1modqk_p ≡ (m_q-m_p)*p^{-1} \mod q
其中
p1p1modqp^{-1}*p ≡ 1 \mod q

代入下式
cd=mp+kppc^d = m_p+k_p*p

可得
cd=(((mqmp)p1)%q)p+mpc^d = (((m_q-m_p)*p^{-1})\%q)*p+m_p
mcdmodn(((mqmp)p1)%q)p+mpmodnm ≡ c^d \mod n ≡ (((m_q-m_p)*p^{-1})\%q)*p+m_p \mod n

对于mpm_p, mqm_q
mpcdmodpm_p ≡ c^d \mod p
mpcdp+k(p1)modpm_p ≡ c^{d_p+k*(p-1)} \mod p
mpcdpck(p1)modpm_p ≡ c^{d_p}*c^{k*(p-1)} \mod p

费马小定理(p为素数):
ap11modpa^{p-1} ≡ 1 \mod p

ck(p1)1modpc^{k*(p-1)} ≡ 1 \mod p
mpcdpmodpm_p ≡ c^{d_p} \mod p

同理
mqcdqmodqm_q ≡ c^{d_q} \mod q

mcdmodn((((cdq%q)(cdp%p))p1)%q)p+(cdp%p)modnm ≡ c^d \mod n ≡ ((((c^{d_q}\%q)-(c^{d_p}\%p))*p^{-1})\%q)*p+(c^{d_p}\%p) \mod n

可能存在的非预期
m<pm < p
mcdmodnm ≡ c^d \mod n
mcdmod(pq)m ≡ c^d \mod (p*q)
m+kpq=cdm+k*p*q = c^d
m+kpq=cdmodpm+k*p*q = c^d \mod p
mcdmodpm ≡ c^d \mod p
mcdp+k(p1)modpm ≡ c^{d_p+k*(p-1)} \mod p
mcdpck(p1)modpm ≡ c^{d_p}*c^{k*(p-1)} \mod p
mcdpmodpm ≡ c^{d_p} \mod p


dp & dq & dr

在三素数(n=pqrn = p*q*r)的情况下,给出pp, qq, rr, dpd_p, dqd_q, drdr, nn, cc来求解mm
其中
dpdmod(p1)d_{p} ≡ d \mod (p-1)
dqdmod(q1)d_{q} ≡ d \mod (q-1)
drdmod(r1)d_{r} ≡ d \mod (r-1)
公式不变
mcdmodn(((mqmp)p1)%q)p+mpmodnm ≡ c^d \mod n ≡ (((m_q-m_p)*p^{-1})\%q)*p+m_p \mod n
mcdmodn((((cdq%q)(cdp%p))p1)%q)p+(cdp%p)modnm ≡ c^d \mod n ≡ ((((c^{d_q}\%q)-(c^{d_p}\%p))*p^{-1})\%q)*p+(c^{d_p}\%p) \mod n
joker

在三素数(n=pqrn = p*q*r)的情况下,给出pp, qq, rr, dpd_p, dqd_q, drdr, nn, cc来求解mm
其中
dp=d%((q1)(r1))d_p = d \% ((q-1)*(r-1))
dq=d%((p1)(r1))d_q = d \% ((p-1)*(r-1))
dr=d%((p1)(q1))d_r = d \% ((p-1)*(q-1))

d=dp+k(q1)(r1)d = d_p+k*(q-1)*(r-1)
mpcdmod(qr)m_p ≡ c^d \mod (q*r)
mpcdp+k(q1)(r1)mod(qr)m_p ≡ c^{d_p+k*(q-1)*(r-1)} \mod (q*r)
mpcdpck(q1)(r1)mod(qr)m_p ≡ c^{d_p}*c^{k*(q-1)*(r-1)} \mod (q*r)
mpcdpmod(qr)m_p ≡ c^{d_p} \mod (q*r)
同理可得
mqcdqmod(pr)m_q ≡ c^{d_q} \mod (p*r)

cdmp+kpqrc^d ≡ m_p+k_p*q*r
cdmq+kqprc^d ≡ m_q+k_q*p*r
mp+kpqr=mq+kqprm_p+k_p*q*r = m_q+k_q*p*r
mqmp=(kpqkqp)rm_q-m_p = (k_p*q-k_q*p)*r
kpqrmqmpmodpk_p*q*r ≡ m_q-m_p \mod p
kp(mqmp)q1r1modpk_p ≡ (m_q-m_p)*q^{-1}*r^{-1} \mod p
cd=mp+kpqrc^d = m_p+k_p*q*r
cd=mp+(((mqmp)q1r1)%p)qr+mpc^d = m_p+(((m_q-m_p)*q^{-1}*r^{-1})\% p)*q*r+m_p
mcdmodn(((mqmp)q1r1)%p)qr+mpmodnm ≡ c^d \mod n ≡ (((m_q-m_p)*q^{-1}*r^{-1})\%p)*q*r+m_p \mod n
mcdmodn((((cdq%(pr))(cdp%(qr)))q1r1)%p)qr+(cdp%(qr))modnm ≡ c^d \mod n ≡ ((((c^{d_q}\%(p*r))-(c^{d_p}\%(q*r)))*q^{-1}*r^{-1})\%p)*q*r+(c^{d_p}\%(q*r)) \mod n


dp

通过ee, dpd_p, nn, cc来求解mm
ed1mod(p1)(q1)e*d ≡ 1 \mod (p-1)*(q-1)
ed=1+k1(p1)(q1)e*d = 1+ k_1*(p-1)*(q-1)
e(dp+k2(p1))=1+k1(p1)(q1)e*(d_p+k_2*(p-1)) = 1+ k_1*(p-1)*(q-1)
edp+ek2(p1)=1+k1(p1)(q1)e*d_p+e*k_2*(p-1) = 1 + k_1*(p-1)*(q-1)
edp1mod(p1)e*d_p ≡ 1 \mod (p-1)
edp1=k(p1)e*d_p-1 = k*(p-1)
k=edp1p1<edpp1<e(p1)p1=ek = \frac{e*d_p-1}{p-1} < \frac{e*d_p}{p-1} < \frac{e*(p-1)}{p-1} = e

则可以遍历(1,ee)

1
2
3
for i in range(2,e):
if (e*d_p-1)%i == 0:
k = i

p=edp1k+1p = \frac{e*d_p-1}{k} + 1
q=npq = \frac{n}{p}
phi=(p1)(q1)phi = (p-1)*(q-1)
de1modphid ≡ e^{-1} \mod phi
mcdmodnm ≡ c ^ d \mod n


共模

{c1me1modnc2me2modn\begin{cases} c_1 ≡ m^{e_1} \mod n \\ c_2 ≡ m^{e_2} \mod n \\ \end{cases}

给出c1c_1, c2c_2, e1e_1, e2e_2来求解mm

gce(e1,e2)=1gce(e_1, e_2) = 1
使用EEA可得
s1e1+s2e2=1s_1*e_1+s_2*e_2 = 1
c1s1c2s2me1s1me2s2me1s1+e2s2mmodnc_1^{s_1}*c2^{s_2} ≡ m^{e_1*s_1}*m^{e_2*s_2} ≡ m^{e_1*s_1+e_2*s_2} ≡ m \mod n

但是s1s_1, s2s_2中有一个为负数
模运算的负数次幂运算如下(假设s1s_1为负数)
c1s1(c11)s1modnc_1^{s_1} ≡ (c1^{-1})^{-s_1}\mod n

1
2
3
4
5
6
7
8
9
10
11
s = gmpy2.gcdext(e1,e2)
if s[1] < 0:
s1 = -s[1]
s2 = s[2]
c1_ = gmpy2.invert(c1,n)
m = (pow(c1_,s1,n)*pow(c2,s2,n))%n
elif s[2] < 0:
s1 = s[1]
s2 = -s[2]
c2_ = gmpy2.invert(c2,n)
m = (pow(c1,s1,n)*pow(c2_,s2,n))%n

低指数

ee很小,存在两种情况

  • c=me<nc = m^e < n
    则可以直接开方
    m=cem = \sqrt[e]{c}

  • c=me>nc = m^e > n
    c+kn=mec+k*n = m^e
    m=kn+cem = \sqrt[e]{k*n+c}
    枚举k即可解出明文

1
2
3
4
for i in range(0,100):
k = gmpy2.iroot(i*n+c,e)
if k[1] == True:
m = k[0]

低解密指数 – wiener

理论推导部分省略
结论为当 d<13N14d < \frac{1}{3}N^{\frac{1}{4}} 成立时
enkd<12d2|\frac{e}{n} - \frac{k}{d}| < \frac{1}{2d^{2}} 成立
其中 ed=kϕ(n)+1e*d = k*\phi(n) + 1
kd\frac{k}{d} 的值在 en\frac{e}{n}的连分数渐进值中存在

ee = 17993, nn = 90581为例
欧几里得算法流程如下
17993=090851+1799317993 = 0*90851 + 17993
90581=517993+61690581 = 5*17993 + 616
17993=29616+12917993 = 29*616 + 129
616=4129+100616 = 4*129 + 100
129=1100+29129 = 1*100 + 29
100=329+13100 = 3*29 + 13
29=213+329 = 2*13 + 3
13=43+113 = 4*3 + 1
3=31+03 = 3*1 + 0
得到的商数集为 [0,5,29,4,1,3,2,4,3][0, 5, 29, 4, 1, 3, 2, 4, 3]
en\frac{e}{n} 的连分数形式为
1799390581=0+15+129+14+11+13+12+14+13\frac{17993}{90581} = 0+\cfrac{1}{5+\cfrac{1}{29+\cfrac{1}{4+\cfrac{1}{1+\cfrac{1}{3+\cfrac{1}{2+\cfrac{1}{4+\cfrac{1}{3}}}}}}}}
可求得连分数渐进值为 [0,15,29146,117589,146735,5552794,12566323,557928086,1799390581][0, \frac{1}{5}, \frac{29}{146}, \frac{117}{589}, \frac{146}{735}, \frac{555}{2794}, \frac{1256}{6323}, \frac{5579}{28086}, \frac{17993}{90581}]
则遍历收敛即可得到(k,d)(k, d)的值

通过韦达定理可以进行进一步的判别
n=pqn = p*q
ϕ(n)=ed1k=(p1)(q1)\phi(n) = \frac{e*d-1}{k} = (p-1)*(q-1)
nϕ(n)=p+q1n - \phi(n) = p+q-1
设立方程式
x2+(nϕ(n)+1)x+n=0x^2 + (n-\phi(n)+1)*x + n = 0
x2+(p+q)x+pq=0x^2 + (p+q)*x + p*q = 0
如果 (p+q)24pq=y>0(p+q)^2 - 4*p*q = y > 0成立
y\sqrt{y} 的结果为正整数
dd为正确值
且可以求出pp, qq

补充

abcd<12d2\vert\frac{a}{b} - \frac{c}{d}\vert < \frac{1}{2d^{2}}
abcd<12b2\vert\frac{a}{b} - \frac{c}{d}\vert < \frac{1}{2b^{2}}
区别在于前者在ab\frac{a}{b}的趋近值中求cd\frac{c}{d}的值,后者在cd\frac{c}{d}的趋近值中求ab\frac{a}{b}的值


费马因式分解

对于任意一个奇数n,有n=ab=x2y2=(x+y)(xy)n = a*b = x^2-y^2 = (x+y)*(x-y)
而在nn的分解出的因数接近时,可以从 x=n+i,iZx=\sqrt{n}+i, i \in{\Bbb{Z}} 开始进行递增遍历
如果x2nx^2-n的结果可以被完全开方,则x正确,且开方结果为y
即可得出aabb
nn为有四个因子,则存在两组aabb的值


低指数广播

{c1memodn1c2memodn2c3memodn3\begin{cases} c_1 ≡ m^e \mod n_1 \\ c_2 ≡ m^e \mod n_2 \\ c_3 ≡ m^e \mod n_3 \\ \end{cases}

且满足 me<n1n2n3m^e < n_1*n_2*n_3
则可以使用中国剩余定理

{k1(n2n3)1modn1k2(n1n3)1modn2k3(n1n2)1modn3\begin{cases} k_1 ≡ (n_2*n_3)^{-1} \mod n_1 \\ k_2 ≡ (n_1*n_3)^{-1} \mod n_2 \\ k_3 ≡ (n_1*n_2)^{-1} \mod n_3 \\ \end{cases}

me=(n2n3k1c1+n1n3k2c2+n1n2k3c3)%(n1n2n3)m^e = (n_2*n_3*k_1*c_1+n_1*n_3*k_2*c_2+n_1*n_2*k_3*c_3)\%(n_1*n_2*n_3)
m=(n2n3k1c1+n1n3k2c2+n1n2k3c3)%(n1n2n3)em = \sqrt[e]{(n_2*n_3*k_1*c_1+n_1*n_3*k_2*c_2+n_1*n_2*k_3*c_3)\%(n_1*n_2*n_3)}


smooth number

若p-1的素因子均不大于b
那么p-1为 b-smooth number
遍历不大于b的素数aia_i
B=iaiB = \prod_{i}{a_i}
B=k(p1)B = k*(p-1)
aBak(p1)1modpa^B ≡ a^{k*(p-1)} ≡ 1 \mod p
aBak(p1)xmodna^B ≡ a^{k*(p-1)} ≡ x \mod n

wiki中给出模除的计算方法如下
dmod(abc)=(dmoda)+a[(d/a)modb]+ab[(d/a/b)modc]d \mod (abc) = (d \mod a) + a[(d / a) \mod b] + ab[(d / a / b) \mod c]

aBak(p1)xmod(pq)a^B ≡ a^{k*(p-1)} ≡ x \mod (p*q)
aBak(p1)xmodp+p(xpmodq)a^B ≡ a^{k*(p-1)} ≡ x \mod p + p*(\frac{x}{p} \mod q)
aB=ak(p1)=1+kpa^B = a^{k*(p-1)} = 1 + k*p

gcd(aB1,n)=gcd(kp,qp)=pgcd(a^{B}-1, n) = gcd(k*p, q*p) = p


p(非预期)

m<pm < p
cmemodnc ≡ m^e \mod n
cmemod(pq)c ≡ m^e \mod (p*q)
cpmecmodpc_p ≡ m^e ≡ c \mod p
ed1mod(p1)e*d ≡ 1 \mod (p-1)
ed=k(p1)+1e*d = k*(p-1)+1
cpdmedmk(p1)+1mmodpc_p^d ≡ m^{e*d} ≡ m^{k*(p-1)+1} ≡ m \mod p


d

q=nextprime(p)q = nextprime(p)
ed1modphie*d ≡ 1 \mod phi
ed1=kphie*d-1 = k*phi
ed1k=phi\frac{e*d-1}{k} = phi
根据ed1e*d-1phiphi的位数之差可以得到kk的大概范围
在范围中遍历kk
得到可能的phiphi
nextprime(phinextprime(\sqrt{phi}) 即为qq
p=phiq1+1p = \frac{phi}{q-1}+1
计算 ed % (p1)(q1)e*d\ \%\ (p-1)*(q-1) 的结果若为1
p,qp, q 值正确,即所得 phiphi 值正确


n & ed

ed=kphi+1e*d = k*phi + 1
k=ed1phi=ed1(p1)(q1)>ed1pq=ed1nk = \frac{e*d - 1}{phi} = \frac{e*d - 1}{(p - 1)*(q - 1)} > \frac{e*d - 1}{p*q} = \frac{e*d - 1}{n}
nn略大于phiphi
kk略大于ed1n\frac{e*d - 1}{n}
爆破即可得到kk
phi=ed1k=(p1)(q1)phi = \frac{e*d - 1}{k} = (p - 1)*(q - 1)
nphi+1=pq(p1)(q1)+1=p+qn - phi + 1= p*q - (p - 1)*(q - 1) + 1 = p + q
pq=(p+q)24pq=(p+q)24np - q = (p + q)^{2} - 4*p*q = (p + q)^{2} - 4*n
p=(p+q)+(pq)2p = \frac{(p + q)+(p - q)}{2}
q=(p+q)(pq)2q = \frac{(p + q)-(p - q)}{2}


Rabin

n=pqn = p * q
cm2modnc ≡ m^{2} \mod n

这种情况下即使已知phiphiee,也不能通过正常的方法去解出mm
pp, qq为素数,即为奇数
(p1)(p - 1)(q1)(q - 1) 为均为偶数
phiphi为偶数
gcd(phi,e)=2gcd(phi, e) = 2
ee在模phiphi的情况下逆元则不存在

这里需要使用Rabin算法来进行计算
其核心为二次剩余以及中国剩余定理

cm2modnc ≡ m^{2} \mod n
这里可以分解为两个式子

{cpm2cmodpcqm2cmodq\begin{cases} c_{p} ≡ m^{2} ≡ c \mod p \\ c_{q} ≡ m^{2} ≡ c \mod q \end{cases}

对于第一个式子
cpm2modpc_{p} ≡ m^{2} \mod p
cc是模pp的二次剩余
根据欧拉判别法可以得到
cp121modpc^{\frac{p - 1}{2}} ≡ 1 \mod p
m2cccp12cp+12modpm^{2} ≡ c ≡ c * c^{\frac{p - 1}{2}} ≡ c^{\frac{p + 1}{2}} \mod p
开根号得到以下结果

{c1cp+14modpc2cp+14pcp+14modp\begin{cases} c_{1} ≡ c^{\frac{p + 1}{4}} \mod p \\ c_{2} ≡ -c^{\frac{p + 1}{4}} ≡ p - c^{\frac{p + 1}{4}} \mod p \end{cases}

对于c模q的情况同理

{c3cq+14modqc4cq+14qcq+14modq\begin{cases} c_{3} ≡ c^{\frac{q + 1}{4}} \mod q \\ c_{4} ≡ -c^{\frac{q + 1}{4}} ≡ q - c^{\frac{q + 1}{4}} \mod q \end{cases}

对于以下组合分别进行CRT

{c1&c3c1&c4c2&c3c2&c4\begin{cases} c_{1} \& c_{3} \\ c_{1} \& c_{4} \\ c_{2} \& c_{3} \\ c_{2} \& c_{4} \end{cases}

kpq1modpk_{p} ≡ q^{-1} \mod p
kqp1modqk_{q} ≡ p^{-1} \mod q

{m1=qkpc1+pkqc3modnm2=qkpc1+pkqc4modnm3=qkpc2+pkqc3modnm4=qkpc2+pkqc4modn\begin{cases} m_{1} = q*k_{p}*c_{1} + p*k_{q}*c_{3} \mod n \\ m_{2} = q*k_{p}*c_{1} + p*k_{q}*c_{4} \mod n \\ m_{3} = q*k_{p}*c_{2} + p*k_{q}*c_{3} \mod n \\ m_{4} = q*k_{p}*c_{2} + p*k_{q}*c_{4} \mod n \end{cases}

mm就存在于四种结果之中


wilson

(p1)!1modp(p-1)! ≡ -1 \mod p
(p1)!p1modp(p-1)! ≡ p-1 \mod p
(p2)!1modp(p-2)! ≡ 1 \mod p
q!modpq! \mod p 的值
其中 q<pq<p, 且 pqp-q 的值不大
x=1x = 1
iiq+1q+1p2p-2 进行遍历
x=x(i1modp)x = x * (i^{-1} \mod p)
q!=xq! = x


openssl

public.key

1
openssl rsa -pubin -modulus -text -in public.key

得到ee, nn


flag.enc

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
key_info = RSA.construct((n, e, d, p, q))
key = RSA.importKey(key_info.exportKey())
key = PKCS1_OAEP.new(key)
f = open('flag.enc', 'r').read()
c = base64.b64decode(f)
m = key.decrypt(c)
##################
import rsa
key = rsa.PrivateKey(n,e,int(d),p,q)
c = open('flag.enc','rb').read()
print(rsa.decrypt(c,key))

coppersmith 101

首先有一个首一的多项式
F(x)=xb+ab1xb1+...+a1x+a0F(x) = x^b+a_{b-1}*x^{b-1}+...+a_{1}x+a_{0}
我们知道存在一个整数x0x_{0},使得F(x0)0modnF(x_{0}) ≡ 0 \mod n
则可以借助coppersmith’s method,将该式转换到整数域上
使得G(x)=0G(x) = 0

Example

n=1119=209n = 11 * 19 = 209
F(x)23x2+13x+610modnF(x) ≡ 23*x^2 + 13*x + 61 ≡ 0 \mod n
这里的首项不为1,则可以乘上23的逆元
F(x)(23x2+13x+61)1000modnF(x) ≡ (23*x^2 + 13*x + 61)*100 ≡ 0 \mod n
F(x)x2+134x+400modnF(x) ≡ x^2+134*x+40 ≡ 0 \mod n
G(x)=aF(x)+nKG(x) = a*F(x) + n*K (K为x的多项式)
解得G(6)=0G(6) = 0
F(6)0modnF(6) ≡ 0 \mod n


对于RSA的学习大概要告一段落了,该去花点时间学学Web,或是做做题,或是写写PHP。
The End, The Start.