RSA——当e与φ(n)不互素时

Crypto

Word count: 3.4kReading time: 14 min

 2020/03/03   Share

记录一下2018年运维挑战赛和新春赛还有一个脚本以及中国剩余定理的记录。

中国剩余定理(CRT)

补充知识

（1）欧几里得算法
欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。
计算公式gcd(a,b) = gcd(b,a mod b)。
假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法，是这样进行的：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此，最大公约数为1
^以除数和余数反复做除法运算^(从计算公式中也可以看出)，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

（2）扩展欧几里得算法
扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。
给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

正题

在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步：

(1)找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。
(2)用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗2得到和233。
(3)用233除以3，5，7三个数的最小公倍数105，得到余数23，即233%105=23。这个余数23就是符合条件的最小数。

我们将“孙子问题”拆分成几个简单的小问题，从零开始，试图揣测古人是如何推导出这个解法的。
首先，我们假设n1是满足除以3余2的一个数，比如2，5，8等等，也就是满足3∗k+2（k>=0）的一个任意数。同样，我们假设n2是满足除以5余3的一个数，n3是满足除以7余2的一个数。

有了前面的假设，我们先从n1这个角度出发，已知n1满足除以3余2，能不能使得n1+n2的和仍然满足除以3余2？进而使得n1+n2+n3的和仍然满足除以3余2？

这就牵涉到一个最基本数学定理，如果有a%b=c，则有(a+k∗b)%b=c(k为非零整数)，换句话说，如果一个除法运算的余数为c，那么被除数与k倍的除数相加（或相减）的和（差）再与除数相除，余数不变。这个是很好证明的。

以此定理为依据，如果n2是3的倍数，n1+n2就依然满足除以3余2。同理，如果n3也是3的倍数，那么n1+n2+n3的和就满足除以3余2。这是从n1的角度考虑的，再从n2，n3的角度出发，我们可推导出以下三点：

为使n1+n2+n3的和满足除以3余2，n2和n3必须是3的倍数。
为使n1+n2+n3的和满足除以5余3，n1和n3必须是5的倍数。
为使n1+n2+n3的和满足除以7余2，n1和n2必须是7的倍数。
　　
因此，为使n1+n2+n3的和作为“孙子问题”的一个最终解，需满足：

n1除以3余2，且是5和7的公倍数。
n2除以5余3，且是3和7的公倍数。
n3除以7余2，且是3和5的公倍数。

所以，孙子问题解法的本质是从5和7的公倍数中找一个除以3余2的数n1，从3和7的公倍数中找一个除以5余3的数n2，从3和5的公倍数中找一个除以7余2的数n3，再将三个数相加得到解。在求n1，n2，n3时又用了一个小技巧，以n1为例，并非从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2。也就是先求出5和7的公倍数模3下的逆元，再用逆元去乘余数。

这里又有一个数学公式，如果a%b=c，那么(a∗k)%b=a%b+a%b+…+a%b=c+c+…+c=k∗c(k>0),也就是说，如果一个除法的余数为c，那么被除数的k倍与除数相除的余数为k∗c。展开式中已证明。

最后，我们还要清楚一点，n1+n2+n3只是问题的一个解，并不是最小的解。如何得到最小解？我们只需要从中最大限度的减掉掉3，5，7的公倍数105即可。道理就是前面讲过的定理“如果a%b=c，则有(a−k∗b)%b=c”。所以（n1+n2+n3）%105就是最终的最小解。

这样一来就得到了中国剩余定理的公式：

$设正整数m_1,m_2,m_3,...m_k两两互素，则同余方程组$ $x\equiv a_1(mod\ m_1)$ $x\equiv a_2(mod\ m_2)$ $x\equiv a_3(mod\ m_3)$ $.$ $.$ $x\equiv a_k(mod\ m_k)$ $有整数解。并且在模M=m_1·m_2·m_3···m_k下的解是唯一的，解为:$

中国剩余定理扩展——求解模数不互质情况下的线性方程组：
普通的中国剩余定理要求所有的互素，那么如果不互素呢，怎么求解同余方程组？
这种情况就采用两两合并的思想，假设要合并如下两个方程：

x=a1+m1x1
x=a2+m2x2

那么得到

a1+m1x1=a2+m2x2$\rightarrow$m2x2-m1x1=a2-a1

我们需要求出一个最小的x使它满足：

x=a1+m1x1=a2+m2x2

那么x1和x2就要尽可能的小，于是我们用扩展欧几里得算法求出x1的最小正整数解，将它代回a1+m1x1，得到x的一个特解x′，当然也是最小正整数解。

对于扩展欧几里得算法的应用，我认为这里是把x=m1x1+a1中的x1当作x，而y等于1，另外m1为a，b等于1
也即x’=a1+m1[x1(min)]

所以x的通解一定是x′加上lcm(m1,m2)∗k，这样才能保证x模m1和m2的余数是a1和a2。由此，我们把这个x′当做新的方程的余数，把lcm(m1,m2)当做新的方程的模数。（这一段是关键）
即：　　

2018运维挑战赛

参考博客：
https://www.cnblogs.com/MashiroSky/p/5918158.html
https://www.anquanke.com/post/id/164575
https://findneo.github.io/181124-what-if-e-phi-not-coprime/
不好意思，飘零哥的做法我理解不了，还是第三位大哥的比较明白。
题目：

n1=0xcfc59d54b4b2e9ab1b5d90920ae88f430d39fee60d18dddbc623d15aae645e4e50db1c07a02d472b2eebb075a547618e1154a15b1657fbf66ed7e714d23ac70bdfba4c809bbb1e27687163cb09258a07ab2533568192e29a3b8e31a5de886050b28b3ed58e81952487714dd7ae012708db30eaf007620cdeb34f150836a4b723L
e1=0xfae3aL
c1=0x81523a330fb15125b6184e4461dadac7601340960840c5213b67a788c84aecfcdc3caf0bf3e27e4c95bb3c154db7055376981972b1565c22c100c47f3fa1dd2994e56090067b4e66f1c3905f9f780145cdf8d0fea88a45bae5113da37c8879c9cdb8ee9a55892bac3bae11fbbabcba0626163d0e2e12c04d99f4eeba5071cbeaL
n2=0xd45304b186dc82e40bd387afc831c32a4c7ba514a64ae051b62f483f27951065a6a04a030d285bdc1cb457b24c2f8701f574094d46d8de37b5a6d55356d1d368b89e16fa71b6603bd037c7f329a3096ce903937bb0c4f112a678c88fd5d84016f745b8281aea8fd5bcc28b68c293e4ef4a62a62e478a8b6cd46f3da73fa34c63L
e2=0x1f9eaeL
c2=0x4d7ceaadf5e662ab2e0149a8d18a4777b4cd4a7712ab825cf913206c325e6abb88954ebc37b2bda19aed16c5938ac43f43966e96a86913129e38c853ecd4ebc89e806f823ffb802e3ddef0ac6c5ba078d3983393a91cd7a1b59660d47d2045c03ff529c341f3ed994235a68c57f8195f75d61fc8cac37e936d9a6b75c4bd2347L
assert pow(flag,e1,n1)==c1
assert pow(flag,e2,n2)==c2
assert gcd(e1,(p1-1)*(q1-1))==14
assert gcd(e2,(p2-1)*(q2-1))==14

给了n1、n2想到了公约数

def gcd(a,b):
    if b!=0:
        return gcd(b,a%b)
    else:
        return a
n1=145902412361478782344770381873783700413638083575664796147183684992615987925480426688706400688307583005196450858827113757408777361940584125700594767997877530445777012630266331221234501260829837820315200747919668506933176146599166089445798737129024362167061966283411487243534460764772316650320961711082540676899
n2=149099187170511972630955070342575714830336629001429055523308641067867185643738492089983321303377141971663123411968339764579768625561000509534051657156505686277638053591553620131562538158327446457847814787147698749502556552831112070838138070024147578824279983531049306936118687161116949990664307619657857322083

p=gcd(n1,n2)
print("gcd(n1,n2)=%d\n"%(p))
#gcd(n1,n2)=12120327527644543811107783655014863098833219936714394976342507913322405566177432644931575840816861543106701611662013978324877080018872656490603706071067111

所以解到了p，然后进一步我们可以求q1,q2

q1=n1//p
q2=n2//p
print("p=%d\n"%(p))
print("q1=%d\n"%(q1))
print("q2=%d"%(q2))
#p=12120327527644543811107783655014863098833219936714394976342507913322405566177432644931575840816861543106701611662013978324877080018872656490603706071067111
#q1=12037827528067911684278967221392433256129944002157200272548317200308481572950474775891360447285969682243206009995242277136633522897723532096467191105943909
#q2=12301580698247665838432962460247894405698817646605188562297985838079356879336309758823376086396761749681729993573203954506346863479448531269351981555913253

看起来很顺利，但是发现题目中：

1 2	assert gcd(e1,(p1-1)(q1-1))==14 assert gcd(e2,(p2-1)(q2-1))==14

因为e与phi(n)不互素，所以不能直接求出逆元d
只有当他们互素时，即gcd(e,(p-1)*(q-1))==1，才能保证e的逆元d唯一存在。
我们令

$e=a*b$

令b=14，则a=e//b
我们知道e与phi不互素，但是a与phi此时必定互素，因为除掉了公约数了
当然我们也可以试试

phi1=(p-1)*(q1-1)
phi2=(p-1)*(q2-1)
b=14
e1=e1//b
e2=e2//b
test1=math.gcd(e1,phi1)
test2=math.gcd(e2,phi2)
print (test1)
print (test2)
#1
#1

下面是根据第三篇博客的记录：
n1,n2均可分解，且有一个公因数
由于gcd(e,phi)==14，将 (flag^e)%n = c 看作 (((flag^14)%n) ^ (e//14) ) % n == c
分别记 e1//14，e2//14为e1,e2
(flag^14)%n1 为 f1 , (flag^14)%n2 为 f2
则 pow(f1,e1,n1)==c1,pow(f2,e2,n2)==c2
且我们已知 gcd(e1,phi1)==gcd(e2,phi2)==1，因此可求得 f1,f2：

e1=e1//14;e2=e2//14
phi1=(p1-1)*(q1-1);phi2=(p2-1)*(q2-1)
d1=gmpy2.invert(e1,phi1);d2=gmpy2.invert(e2,phi2)
f1=pow(c1,d1,n1);f2=pow(c2,d2,n2)

记 flag^14 为 f3,则有同余方程组 f3 % n1 == f1; f3 % n2 == f2
其中f1,f2,n1,n2已知，可利用中国剩余定理解 f3:

def GCRT(mi, ai):
    # mi,ai分别表示模数和取模后的值,都为列表结构
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0) #不成立则不存在解
        K = c // d * gmpy2.invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
        cura %= curm
    return (cura % curm, curm) #(解,最小公倍数)
f3,lcm = GCRT([n1,n2],[f1,f2])
assert(f3%n1==f1);assert(f3%n2==f2);assert(lcm==p1*p2*q)

此时求出的 f3 满足关系式子：flag^14 % lcm == f3

因为我们知道$flag^14 % n1 == f1$ ，此时$flag^14，n1（p1q）$，$f1$三者位数应该相同
当$n1p2$时，$flag^14$小于lcm，模完就等于本身f3

$p1q即n1 ,p2q即n2, p1*p2记作n3$
flag^14 % lcm == f3可看作 pow(flag^2,7,lcm)==f3，等价于 pow(flag^2,7,n1)==f3%n1,pow(flag^2,7,n2)==f3%n2,pow(flag^2,7,n3)==f3%n3

因为flag^14 % lcm == f3，两边同时模n1，即（flag^14 % lcm）% n1 == f3 % n1
而且因为flag^14 % lcm == flag^14，所以flag^14 % n1 == f3 % n1, 也即pow(flag^2,7,n1)==f3%n1

博客原话：由于 gcd(7,n1)==7,gcd(7,n2)==7。所以尝试选取 pow(flag^2,7,n3)==f3%n3 计算 flag^2 的值
应该是：gcd(7,phi(n1))==7,gcd(7,phi(n2))==7;并且发现gcd(7,phi(n3))==1,所以尝试选取 pow(flag^2,7,n3)==f3%n3 计算 flag^2 的值

n3=p1*p2
c3=f3%n3
phi3=(p1-1)*(p2-1)
assert(gmpy2.gcd(7,phi3)==1)
d3=gmpy2.invert(7,phi3)
m3=pow(c3,d3,n3)
if gmpy2.iroot(m3,2)[1] == 1:
    flag=gmpy2.iroot(m3,2)[0]
    print(binascii.unhexlify(hex(flag)[2:]))

所以原博客代码汇总起来：

# -*- coding : utf-8 -*-
# python 3.7
# __author__ = 'https://github.com/findneo'


import gmpy2
import requests
import json
import binascii

def factordb(n):
    api="http://factordb.com/api.php"
    r=requests.get(api,params={'query':n})
    res=json.loads(r.content)
    if res['status'] == "FF":
        p,q=res['factors'][0][0],res['factors'][1][0]
        [p,q]=map(int,[p,q])
        # print('\n'.join([hex(p),hex(q)]))
        return p,q
    else:
        print("not fully factored!")

n1=0xcfc59d54b4b2e9ab1b5d90920ae88f430d39fee60d18dddbc623d15aae645e4e50db1c07a02d472b2eebb075a547618e1154a15b1657fbf66ed7e714d23ac70bdfba4c809bbb1e27687163cb09258a07ab2533568192e29a3b8e31a5de886050b28b3ed58e81952487714dd7ae012708db30eaf007620cdeb34f150836a4b723
e1=0xfae3a
c1=0x81523a330fb15125b6184e4461dadac7601340960840c5213b67a788c84aecfcdc3caf0bf3e27e4c95bb3c154db7055376981972b1565c22c100c47f3fa1dd2994e56090067b4e66f1c3905f9f780145cdf8d0fea88a45bae5113da37c8879c9cdb8ee9a55892bac3bae11fbbabcba0626163d0e2e12c04d99f4eeba5071cbea
#p1,q1=factordb(n1)
p1=0xe5d7acdf77ca09e4391f21cea16c01cd2302d1a1df3983d413e9ee91fce8d9184ec0d0ca1608dbed748ed905a2beddc00168a1245f27f67e1240073c3d097965
q1=0xe76aed4830504369c7c12070490f18900b80da1035ef82991dd35c52fd51731025c4498e8998bd026b9898963b6b69ded47b1dd96c264eac9d875756fd1b29e7

n2=0xd45304b186dc82e40bd387afc831c32a4c7ba514a64ae051b62f483f27951065a6a04a030d285bdc1cb457b24c2f8701f574094d46d8de37b5a6d55356d1d368b89e16fa71b6603bd037c7f329a3096ce903937bb0c4f112a678c88fd5d84016f745b8281aea8fd5bcc28b68c293e4ef4a62a62e478a8b6cd46f3da73fa34c63
e2=0x1f9eae
c2=0x4d7ceaadf5e662ab2e0149a8d18a4777b4cd4a7712ab825cf913206c325e6abb88954ebc37b2bda19aed16c5938ac43f43966e96a86913129e38c853ecd4ebc89e806f823ffb802e3ddef0ac6c5ba078d3983393a91cd7a1b59660d47d2045c03ff529c341f3ed994235a68c57f8195f75d61fc8cac37e936d9a6b75c4bd2347
#p2,q2=factordb(n2)[::-1]
p2=0xeae0dfb99949af5175c425e22ec3c2e5b73cec0b70510dcc0ccd368ca6e868146c8783fa4aee0548fc725a3c3b0e46e44ec60357d3e6f4a5207e8a8ddf9c1225
q2=0xe76aed4830504369c7c12070490f18900b80da1035ef82991dd35c52fd51731025c4498e8998bd026b9898963b6b69ded47b1dd96c264eac9d875756fd1b29e7

assert(q1==q2)
q=q1

e1=e1//14;e2=e2//14
phi1=(p1-1)*(q1-1);phi2=(p2-1)*(q2-1)
d1=gmpy2.invert(e1,phi1);d2=gmpy2.invert(e2,phi2)
f1=pow(c1,d1,n1);f2=pow(c2,d2,n2)


def GCRT(mi, ai):

    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = gmpy2.gcd(curm, m)
        c = a - cura
        assert (c % d == 0) 
        K = c // d * gmpy2.invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
        cura %= curm
    return (cura % curm, curm) 
f3,lcm = GCRT([n1,n2],[f1,f2])
#assert(f3%n1==f1);assert(f3%n2==f2);assert(lcm==p1*p2*q)


n3=p1*p2
c3=f3%n3
phi3=(p1-1)*(p2-1)
assert(gmpy2.gcd(7,phi3)==1)
d3=gmpy2.invert(7,phi3)
m3=pow(c3,d3,n3)
if gmpy2.iroot(m3,2)[1] == 1:
    flag=gmpy2.iroot(m3,2)[0]
    print(binascii.unhexlify(hex(flag)[2:]))

来自知乎的脚本

#-*- coding:utf-8 -*-
# 当指数e和Phi(n)不互素时
from Crypto.Util.number import *
import sympy

def gcd(a,b):
    if a < b:
        a,b = b,a
    while b != 0:
        tem = a % b
        a = b
        b = tem
    return a

def invalidExponent(p,q,e,c):
    phiN = (p - 1) * (q - 1)
    n = p * q
    GCD = gcd(e, phiN)
    if (GCD == 1):
        return "Public exponent is valid....."
    d = inverse(e//GCD,phiN)
    c = pow(c, d, n)
    plaintext = sympy.root(c, GCD)
    plaintext = long_to_bytes(plaintext)
    return plaintext


def main():
    p = 111052706592359766492182549474994387389169491981939276489132990221393430874991652628482505832745103981784837665110819809096264457329836670397000634684595709283710756727662219358743235400779394350023790569023369287367240988429777113514012101219956479046699448481988253039282406274512111898037689623723478951613
    q = 146182161315365079136034892629243958871460254472263352847680359868694597466935352294806409849433942550149005978761759458977642785950171998444382137410141550212657953776734166481126376675282041461924529145282451064083351825934453414726557476469773468589060088164379979035597652907191236468744400214917268039573
    e = 200
    c = 7797067792814175554801975939092864905908878472965854967525218347636721153564161093453344819975650594936628697646242713415817737235328825333281389820202851500260665233910426103904874575463134970160306453553794787674331367563821223358610113031883172742577264334021835304931484604571485957116313097395143177603380107508691261081725629713443494783479897404175199621026515502716868988672289887933681890547568860707175288422275073767747544353536862473367590288531216644146154729962448906402712219657000812226637887827912541098992158458173920228864293993030475885461755767069329678218760943185942331149777258713727459739405

    plaintext = invalidExponent(p,q,e,c)
    print plaintext

main()

按照知乎下面的回答，他认为是m^GCD$<$n才行，但我做题时怎么知道满不满足这个关系= =。

如果按照2018运维挑战赛的方法求解：

from Crypto.Util.number import *

p = 111052706592359766492182549474994387389169491981939276489132990221393430874991652628482505832745103981784837665110819809096264457329836670397000634684595709283710756727662219358743235400779394350023790569023369287367240988429777113514012101219956479046699448481988253039282406274512111898037689623723478951613
q = 146182161315365079136034892629243958871460254472263352847680359868694597466935352294806409849433942550149005978761759458977642785950171998444382137410141550212657953776734166481126376675282041461924529145282451064083351825934453414726557476469773468589060088164379979035597652907191236468744400214917268039573
e = 200
c = 7797067792814175554801975939092864905908878472965854967525218347636721153564161093453344819975650594936628697646242713415817737235328825333281389820202851500260665233910426103904874575463134970160306453553794787674331367563821223358610113031883172742577264334021835304931484604571485957116313097395143177603380107508691261081725629713443494783479897404175199621026515502716868988672289887933681890547568860707175288422275073767747544353536862473367590288531216644146154729962448906402712219657000812226637887827912541098992158458173920228864293993030475885461755767069329678218760943185942331149777258713727459739405
phi=(p-1)*(q-1)
n=p*q
GCD=math.gcd(e,phi)#8
e=e//GCD
#print (math.gcd(e,phi)) #1
d1=inverse(e,phi)
f1=pow(c,d1,n)
print(f1) #8790672647699888791168395876725267498380050204509042605325148440775761512060209862878377062250498277565324799241101114626203022698873680727368886696009248411945050428305804829613871379890954039096785744465245794789247131505229329627996841022729341182437065625045609809888462300362847200777304046131988810944506109283470335905223526693623008137885581446429211468764465976794495528511148211351567422881
print (math.gcd(GCD,phi)) #8

而且发现就算是将8转成2*4，2和4与phi得gcd都等于本身，没有互质，也没有同余式可以构造，所以求解方法大概只能直接开方了。

i春秋Warm up

按照rabin求解可以看Apeng的脚本
假如我想用中国剩余定理求s呢?

n1: 15653165971272925436189715950306169488648677427569197436559321968692908786349053303839431043588260338317859397537409728729274630550454731306685369845739785958309492188309739135163206662322980634812713910231189563194520522299672424106135656125893413504868167774287157038801622413798125676071689173117885182987841510070517898710350608725809906704505037866925358298525340393278376093071591988997064894579887906638790394371193617375086245950012269822349986482584060745112453163774290976851732665573217485779016736517696391513031881133151033844438314444107440811148603369668944891577028184130587885396017194863581130429121
n2: 16489315386189042325770722192051506427349661112741403036117573859132337429264884611622357211389605225298644036805277212706583007338311350354908188224017869204022357980160833603890106564921333757491827877881996534008550579568290954848163873756688735179943313218316121156169277347705100580489857710376956784845139492131491003087888548241338393764269176675849400130460962312511303071508724811323438930655022930044289801178261135747942804968069730574751117952892336466612936801767553879313788406195290612707141092629226262881229776085126595220954398177476898915921943956162959257866832266411559621885794764791161258015571
e1=125794
e2=42373
c1: 9977992111543474765993146699435780943354123551515555639473990571150196059887059696672744669228084544909025528146255490100789992216506586730653100894938711107779449187833366325936098812758615334617812732956967746820046321447169099942918022803930068529359616171025439714650868454930763815035475473077689115645913895433110149735235210437428625515317444853803605457325117693750834579622201070329710209543724812590086065816764917135636424809464755834786301901125786342127636605411141721732886212695150911960225370999521213349980949049923324623683647865441245309856444824402766736069791224029707519660787841893575575974855

我们可以发现缺了一个对应的e2和c2，原题目提供的e2并不能用
运维赛中提到：

记 flag^14 为 f3,则有同余方程组 f3 % n1 == f1; f3 % n2 == f2。其中f1,f2,n1,n2已知，可利用中国剩余定理解 f3

我们在这道题可以记s^2为f3，但是只有同余方程组f3 % n1 == f1，并没有f3 % n2 == f2，所以用不了中国剩余定理，而且看到s^2，指数为二，也应该想到Rabin。

Author：DGZ

原文链接：https://dgz-cyber.github.io/2020/03/03/RSA%E2%80%94%E2%80%94%E5%BD%93e%E4%B8%8E%CF%86(n)%E4%B8%8D%E4%BA%92%E7%B4%A0%E6%97%B6/

发表日期：March 3rd 2020, 12:43:56 am

更新日期：April 25th 2020, 11:30:56 pm

Next Post

hgame2020 not_One-time
Previous Post

Socketserver学习（待填）

CATALOG

1. 中国剩余定理(CRT)
1. 1.1. 补充知识
2. 1.2. 正题
2. 2018运维挑战赛
3. 来自知乎的脚本
4. i春秋Warm up

