xXxYOLOxXx

xXxYOLOxXx

Crypto -- RSA

Posted on Edited on In

RSA101

pp, qq为大素数
n=p∗qn = p*q
phi=(p−1)∗(q−1)phi = (p-1)*(q-1)

ee为小于phiphi的素数
e∗d≡1mod  phie*d ≡ 1 \mod phi

ee, nn为公钥; dd, nn为私钥
c≡memod  nc ≡ m^e \mod n
m≡cdmod  nm ≡ c^d \mod n

dp & dq

m≡cdmod  nm ≡ c^d \mod n
n=p∗qn = p*q
dp≡dmod  (p−1)d_p ≡ d \mod (p-1)
dq=dmod  (q−1)d_q = d \mod (q-1)

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

m≡cdmod  nm ≡ c^d \mod n
m≡cdmod  (p∗q)m ≡ c^d \mod (p*q)
mp≡cdmod  pm_p ≡ c^d \mod p
mq≡cdmod  qm_q ≡ c^d \mod q
cd=mp+kp∗pc^d = m_p+k_p*p
cd=mq+kq∗pc^d = m_q+k_q*p

结合两者可得
mq+kq∗q=mp+kp∗pm_q+k_q*q = m_p+k_p*p

mq≡mp+kp∗pmod  qm_q ≡ m_p+k_p*p \mod q
kp∗p≡mq−mpmod  qk_p*p ≡ m_q-m_p \mod q
kp≡(mq−mp)∗p−1mod  qk_p ≡ (m_q-m_p)*p^{-1} \mod q
其中
p−1∗p≡1mod  qp^{-1}*p ≡ 1 \mod q

代入下式
cd=mp+kp∗pc^d = m_p+k_p*p

可得
cd=(((mq−mp)∗p−1)%q)∗p+mpc^d = (((m_q-m_p)*p^{-1})\%q)*p+m_p
m≡cdmod  n≡(((mq−mp)∗p−1)%q)∗p+mpmod  nm ≡ c^d \mod n ≡ (((m_q-m_p)*p^{-1})\%q)*p+m_p \mod n

对于mpm_p, mqm_q
mp≡cdmod  pm_p ≡ c^d \mod p
mp≡cdp+k∗(p−1)mod  pm_p ≡ c^{d_p+k*(p-1)} \mod p
mp≡cdp∗ck∗(p−1)mod  pm_p ≡ c^{d_p}*c^{k*(p-1)} \mod p

费马小定理（p为素数）：
ap−1≡1mod  pa^{p-1} ≡ 1 \mod p
则
ck∗(p−1)≡1mod  pc^{k*(p-1)} ≡ 1 \mod p
mp≡cdpmod  pm_p ≡ c^{d_p} \mod p

同理
mq≡cdqmod  qm_q ≡ c^{d_q} \mod q

m≡cdmod  n≡((((cdq%q)−(cdp%p))∗p−1)%q)∗p+(cdp%p)mod  nm ≡ 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
m≡cdmod  nm ≡ c^d \mod n
m≡cdmod  (p∗q)m ≡ c^d \mod (p*q)
m+k∗p∗q=cdm+k*p*q = c^d
m+k∗p∗q=cdmod  pm+k*p*q = c^d \mod p
m≡cdmod  pm ≡ c^d \mod p
m≡cdp+k∗(p−1)mod  pm ≡ c^{d_p+k*(p-1)} \mod p
m≡cdp∗ck∗(p−1)mod  pm ≡ c^{d_p}*c^{k*(p-1)} \mod p
m≡cdpmod  pm ≡ c^{d_p} \mod p

dp & dq & dr

在三素数（n=p∗q∗rn = p*q*r）的情况下，给出pp, qq, rr, dpd_p, dqd_q, drdr, nn, cc来求解mm
其中
dp≡dmod  (p−1)d_{p} ≡ d \mod (p-1)
dq≡dmod  (q−1)d_{q} ≡ d \mod (q-1)
dr≡dmod  (r−1)d_{r} ≡ d \mod (r-1)
公式不变
m≡cdmod  n≡(((mq−mp)∗p−1)%q)∗p+mpmod  nm ≡ c^d \mod n ≡ (((m_q-m_p)*p^{-1})\%q)*p+m_p \mod n
m≡cdmod  n≡((((cdq%q)−(cdp%p))∗p−1)%q)∗p+(cdp%p)mod  nm ≡ c^d \mod n ≡ ((((c^{d_q}\%q)-(c^{d_p}\%p))*p^{-1})\%q)*p+(c^{d_p}\%p) \mod n
joker

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

d=dp+k∗(q−1)∗(r−1)d = d_p+k*(q-1)*(r-1)
mp≡cdmod  (q∗r)m_p ≡ c^d \mod (q*r)
mp≡cdp+k∗(q−1)∗(r−1)mod  (q∗r)m_p ≡ c^{d_p+k*(q-1)*(r-1)} \mod (q*r)
mp≡cdp∗ck∗(q−1)∗(r−1)mod  (q∗r)m_p ≡ c^{d_p}*c^{k*(q-1)*(r-1)} \mod (q*r)
mp≡cdpmod  (q∗r)m_p ≡ c^{d_p} \mod (q*r)
同理可得
mq≡cdqmod  (p∗r)m_q ≡ c^{d_q} \mod (p*r)

cd≡mp+kp∗q∗rc^d ≡ m_p+k_p*q*r
cd≡mq+kq∗p∗rc^d ≡ m_q+k_q*p*r
mp+kp∗q∗r=mq+kq∗p∗rm_p+k_p*q*r = m_q+k_q*p*r
mq−mp=(kp∗q−kq∗p)∗rm_q-m_p = (k_p*q-k_q*p)*r
kp∗q∗r≡mq−mpmod  pk_p*q*r ≡ m_q-m_p \mod p
kp≡(mq−mp)∗q−1∗r−1mod  pk_p ≡ (m_q-m_p)*q^{-1}*r^{-1} \mod p
cd=mp+kp∗q∗rc^d = m_p+k_p*q*r
cd=mp+(((mq−mp)∗q−1∗r−1)%p)∗q∗r+mpc^d = m_p+(((m_q-m_p)*q^{-1}*r^{-1})\% p)*q*r+m_p
m≡cdmod  n≡(((mq−mp)∗q−1∗r−1)%p)∗q∗r+mpmod  nm ≡ c^d \mod n ≡ (((m_q-m_p)*q^{-1}*r^{-1})\%p)*q*r+m_p \mod n
m≡cdmod  n≡((((cdq%(p∗r))−(cdp%(q∗r)))∗q−1∗r−1)%p)∗q∗r+(cdp%(q∗r))mod  nm ≡ 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
e∗d≡1mod  (p−1)∗(q−1)e*d ≡ 1 \mod (p-1)*(q-1)
e∗d=1+k1∗(p−1)∗(q−1)e*d = 1+ k_1*(p-1)*(q-1)
e∗(dp+k2∗(p−1))=1+k1∗(p−1)∗(q−1)e*(d_p+k_2*(p-1)) = 1+ k_1*(p-1)*(q-1)
e∗dp+e∗k2∗(p−1)=1+k1∗(p−1)∗(q−1)e*d_p+e*k_2*(p-1) = 1 + k_1*(p-1)*(q-1)
e∗dp≡1mod  (p−1)e*d_p ≡ 1 \mod (p-1)
e∗dp−1=k∗(p−1)e*d_p-1 = k*(p-1)
k=e∗dp−1p−1<e∗dpp−1<e∗(p−1)p−1=ek = \frac{e*d_p-1}{p-1} < \frac{e*d_p}{p-1} < \frac{e*(p-1)}{p-1} = e

则可以遍历(2,ee)

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

p=e∗dp−1k+1p = \frac{e*d_p-1}{k} + 1
q=npq = \frac{n}{p}
phi=(p−1)∗(q−1)phi = (p-1)*(q-1)
d≡e−1mod  phid ≡ e^{-1} \mod phi
m≡cdmod  nm ≡ c ^ d \mod n

共模

{c1≡me1mod  nc2≡me2mod  n\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可得
s1∗e1+s2∗e2=1s_1*e_1+s_2*e_2 = 1
c1s1∗c2s2≡me1∗s1∗me2∗s2≡me1∗s1+e2∗s2≡mmod  nc_1^{s_1}*c_2^{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≡(c1−1)−s1mod  nc_1^{s_1} ≡ (c_1^{-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+k∗n=mec+k*n = m^e
    m=k∗n+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}} 成立时
∣en−kd∣<12d2|\frac{e}{n} - \frac{k}{d}| < \frac{1}{2d^{2}} 成立
其中 e∗d=k∗ϕ(n)+1e*d = k*\phi(n) + 1
则 kd\frac{k}{d} 的值在 en\frac{e}{n}的连分数渐进值中存在

以ee = 17993, nn = 90581为例
欧几里得算法流程如下
17993=0∗90851+1799317993 = 0*90851 + 17993
90581=5∗17993+61690581 = 5*17993 + 616
17993=29∗616+12917993 = 29*616 + 129
616=4∗129+100616 = 4*129 + 100
129=1∗100+29129 = 1*100 + 29
100=3∗29+13100 = 3*29 + 13
29=2∗13+329 = 2*13 + 3
13=4∗3+113 = 4*3 + 1
3=3∗1+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=p∗qn = p*q
ϕ(n)=e∗d−1k=(p−1)∗(q−1)\phi(n) = \frac{e*d-1}{k} = (p-1)*(q-1)
n−ϕ(n)=p+q−1n - \phi(n) = p+q-1
设立方程式
x2+(n−ϕ(n)+1)∗x+n=0x^2 + (n-\phi(n)+1)*x + n = 0
x2+(p+q)∗x+p∗q=0x^2 + (p+q)*x + p*q = 0
如果 (p+q)2−4∗p∗q=y>0(p+q)^2 - 4*p*q = y > 0成立
且 y\sqrt{y} 的结果为正整数
则dd为正确值
且可以求出pp, qq

补充

∣ab−cd∣<12d2\vert\frac{a}{b} - \frac{c}{d}\vert < \frac{1}{2d^{2}}
∣ab−cd∣<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=a∗b=x2−y2=(x+y)∗(x−y)n = a*b = x^2-y^2 = (x+y)*(x-y)
而在nn的分解出的因数接近时，可以从 x=n+i,i∈Zx=\sqrt{n}+i, i \in{\Bbb{Z}} 开始进行递增遍历
如果x2−nx^2-n的结果可以被完全开方，则x正确，且开方结果为y
即可得出aa，bb
若nn为有四个因子，则存在两组aa，bb的值

低指数广播

{c1≡memod  n1c2≡memod  n2c3≡memod  n3\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<n1∗n2∗n3m^e < n_1*n_2*n_3
则可以使用中国剩余定理

{k1≡(n2∗n3)−1mod  n1k2≡(n1∗n3)−1mod  n2k3≡(n1∗n2)−1mod  n3\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=(n2∗n3∗k1∗c1+n1∗n3∗k2∗c2+n1∗n2∗k3∗c3)%(n1∗n2∗n3)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=(n2∗n3∗k1∗c1+n1∗n3∗k2∗c2+n1∗n2∗k3∗c3)%(n1∗n2∗n3)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∗(p−1)B = k*(p-1)
aB≡ak∗(p−1)≡1mod  pa^B ≡ a^{k*(p-1)} ≡ 1 \mod p
aB≡ak∗(p−1)≡xmod  na^B ≡ a^{k*(p-1)} ≡ x \mod n

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

aB≡ak∗(p−1)≡xmod  (p∗q)a^B ≡ a^{k*(p-1)} ≡ x \mod (p*q)
aB≡ak∗(p−1)≡xmod  p+p∗(xpmod  q)a^B ≡ a^{k*(p-1)} ≡ x \mod p + p*(\frac{x}{p} \mod q)
aB=ak∗(p−1)=1+k∗pa^B = a^{k*(p-1)} = 1 + k*p

gcd(aB−1,n)=gcd(k∗p,q∗p)=pgcd(a^{B}-1, n) = gcd(k*p, q*p) = p

p（非预期）

m<pm < p
c≡memod  nc ≡ m^e \mod n
c≡memod  (p∗q)c ≡ m^e \mod (p*q)
cp≡me≡cmod  pc_p ≡ m^e ≡ c \mod p
e∗d≡1mod  (p−1)e*d ≡ 1 \mod (p-1)
e∗d=k∗(p−1)+1e*d = k*(p-1)+1
cpd≡me∗d≡mk∗(p−1)+1≡mmod  pc_p^d ≡ m^{e*d} ≡ m^{k*(p-1)+1} ≡ m \mod p

d

q=nextprime(p)q = nextprime(p)
e∗d≡1mod  phie*d ≡ 1 \mod phi
e∗d−1=k∗phie*d-1 = k*phi
e∗d−1k=phi\frac{e*d-1}{k} = phi
根据e∗d−1e*d-1和phiphi的位数之差可以得到kk的大概范围
在范围中遍历kk
得到可能的phiphi值
nextprime(phinextprime(\sqrt{phi}) 即为qq
p=phiq−1+1p = \frac{phi}{q-1}+1
计算 e∗d % (p−1)∗(q−1)e*d\ \%\ (p-1)*(q-1) 的结果若为1
则 p,qp, q 值正确，即所得 phiphi 值正确

n & ed

e∗d=k∗phi+1e*d = k*phi + 1
k=e∗d−1phi=e∗d−1(p−1)∗(q−1)>e∗d−1p∗q=e∗d−1nk = \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略大于e∗d−1n\frac{e*d - 1}{n}
爆破即可得到kk
phi=e∗d−1k=(p−1)∗(q−1)phi = \frac{e*d - 1}{k} = (p - 1)*(q - 1)
n−phi+1=p∗q−(p−1)∗(q−1)+1=p+qn - phi + 1= p*q - (p - 1)*(q - 1) + 1 = p + q
p−q=(p+q)2−4∗p∗q=(p+q)2−4∗np - q = (p + q)^{2} - 4*p*q = (p + q)^{2} - 4*n
p=(p+q)+(p−q)2p = \frac{(p + q)+(p - q)}{2}
q=(p+q)−(p−q)2q = \frac{(p + q)-(p - q)}{2}

Rabin

n=p∗qn = p * q
c≡m2mod  nc ≡ m^{2} \mod n

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

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

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

{cp≡m2≡cmod  pcq≡m2≡cmod  q\begin{cases} c_{p} ≡ m^{2} ≡ c \mod p \\ c_{q} ≡ m^{2} ≡ c \mod q \end{cases}

对于第一个式子
cp≡m2mod  pc_{p} ≡ m^{2} \mod p
则cc是模pp的二次剩余
根据欧拉判别法可以得到
cp−12≡1mod  pc^{\frac{p - 1}{2}} ≡ 1 \mod p
m2≡c≡c∗cp−12≡cp+12mod  pm^{2} ≡ c ≡ c * c^{\frac{p - 1}{2}} ≡ c^{\frac{p + 1}{2}} \mod p
开根号得到以下结果

{c1≡cp+14mod  pc2≡−cp+14≡p−cp+14mod  p\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的情况同理

{c3≡cq+14mod  qc4≡−cq+14≡q−cq+14mod  q\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}

kp≡q−1mod  pk_{p} ≡ q^{-1} \mod p
kq≡p−1mod  qk_{q} ≡ p^{-1} \mod q

{m1=q∗kp∗c1+p∗kq∗c3mod  nm2=q∗kp∗c1+p∗kq∗c4mod  nm3=q∗kp∗c2+p∗kq∗c3mod  nm4=q∗kp∗c2+p∗kq∗c4mod  n\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

(p−1)!≡−1mod  p(p-1)! ≡ -1 \mod p
(p−1)!≡p−1mod  p(p-1)! ≡ p-1 \mod p
(p−2)!≡1mod  p(p-2)! ≡ 1 \mod p
求 q!mod  pq! \mod p 的值
其中 q<pq < p, 且 p−qp - q 的值不大
x=1x = 1
ii 从 q+1q + 1 到 p−2p - 2 进行遍历
x=x∗(i−1mod  p)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+ab−1∗xb−1+...+a1x+a0F(x) = x^b+a_{b-1}*x^{b-1}+...+a_{1}x+a_{0}
我们知道存在一个整数x0x_{0}，使得F(x0)≡0mod  nF(x_{0}) ≡ 0 \mod n
则可以借助coppersmith’s method，将该式转换到整数域上
使得G(x)=0G(x) = 0

Example

n=11∗19=209n = 11 * 19 = 209
F(x)≡23∗x2+13∗x+61≡0mod  nF(x) ≡ 23*x^2 + 13*x + 61 ≡ 0 \mod n
这里的首项不为1，则可以乘上23的逆元
F(x)≡(23∗x2+13∗x+61)∗100≡0mod  nF(x) ≡ (23*x^2 + 13*x + 61)*100 ≡ 0 \mod n
F(x)≡x2+134∗x+40≡0mod  nF(x) ≡ x^2+134*x+40 ≡ 0 \mod n
G(x)=a∗F(x)+n∗KG(x) = a*F(x) + n*K (K为x的多项式)
解得G(6)=0G(6) = 0
即F(6)≡0mod  nF(6) ≡ 0 \mod n

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