结论

对二项式取模时

c=(a⋅p+b⋅q)emod  Nc = (a \cdot p + b \cdot q)^e \mod N

可以转换为

c=(a⋅p)e+(b⋅q)emod  Nc = (a \cdot p)^e + (b \cdot q)^e \mod N

思路：

  1. 先转换 c1, c2 的二项式
  2. 使 c1 , c2 幂数相同
  3. 乘个啥玩意儿消去一项
  4. 剩下的部分分别模p， 模q， 看包含 N 中的哪个因子
  5. gcd(剩下的部分， N) = 包含的那个因子

证明

例如

c1=(3⋅p+7⋅q)emod  Nc2=(2⋅p+5⋅q)emod  Nc_1 = (3\cdot p + 7\cdot q)^e \mod N \\ c_2 = (2\cdot p + 5\cdot q)^e \mod N \\

对于

c=(a⋅p+b⋅q)emod  Nc = (a\cdot p + b\cdot q) ^ e \mod N

由二项式展开定理

(a⋅p+b⋅q)e=∑i=0e(ei)(a⋅p)i(b⋅q)e−i(a \cdot p + b \cdot q)^e = \sum_{i=0}^{e} \binom{e}{i} (a \cdot p)^{i} (b \cdot q)^{e-i}

对于除了 i=0 和 i=e 的时候， 其他情况：

(a⋅p)x(b⋅q)e−x=ax⋅px⋅be−x⋅qe−x(a \cdot p)^x (b \cdot q)^{e-x} = a^x \cdot p^x \cdot b^{e-x} \cdot q^{e-x} \\

px和qe−xp^x 和 q^{e-x}可以组合出N，那么此时模 N 就等于0

所以只有i=0 和 i=e 的时候，模 N 才会有结果

∴c=(a⋅p)e+(b⋅q)emod  N\therefore c = (a \cdot p)^e + (b \cdot q)^e \mod N

按照以上公式转换 c1, c2

c1=(3p)e1+(7q)e1mod  Nc2=(2p)e2+(5q)e2mod  Nc_1 = (3p)^{e_1} + (7q)^{e_1} \mod N \\ c_2 = (2p)^{e_2} + (5q)^{e_2} \mod N

将c1, c2调整为齐次， 这样可以消去一项

c1e2=(3p)e1⋅e2+(7q)e1⋅e2mod  Nc2e1=(2p)e1⋅e2+(5q)e1⋅e2mod  Nc^{e_2}_{1} = (3p)^{e_1 \cdot e_2} + (7q)^{e_1 \cdot e_2} \mod N \\ c^{e_1}_{2} = (2p)^{e_1 \cdot e_2} + (5q)^{e_1 \cdot e_2} \mod N

用2e1e2c1e2−3e1e2c2e12^{e_1e_2}c_1^{e_2} - 3^{e_1e_2}c_2^{e_1}消去pe1e2p^{e_1e_2}
(注意不是2c1e2−3c2e12c_1^{e_2} - 3c_2^{e_1})

f=(2e1⋅e2c1e2−3e1⋅e2c2e1)mod  N=(14e1⋅e2−15e1⋅e2)⋅qe1⋅e2mod  Nf = (2^{e_1 \cdot e_2} c^{e_2}_{1} - 3^{e_1 \cdot e_2} c^{e_1}_{2}) \mod N = (14^{e_1 \cdot e_2} - 15^{e_1 \cdot e_2}) \cdot q^{e_1 \cdot e_2} \mod N

设 q0=a⋅qxmod  Nq_0 = a \cdot q ^ x \mod N
消掉模N后

q0=a⋅qx−k⋅Nq_0 = a \cdot q ^ x - k \cdot N

∵N=p⋅q\because N = p \cdot q
对 q0q_0 取模p和模q

  1. 模q时

    q0=a⋅qx−k⋅N=q(a⋅qx−1−k⋅p)≡0mod  qq_0 = a \cdot q ^ x - k \cdot N = q(a \cdot q ^ {x-1} - k \cdot p) \equiv 0 \mod q

    ∴q0和N有公因数q\therefore q_0 和 N 有公因数 q
  2. 模p时

    q0=a⋅qx−k⋅N≢0mod  pq_0 = a \cdot q ^ x - k \cdot N \not\equiv 0 \mod p

∵N只有因子p,q\because N 只有因子 p , q

Boss

∴gcd(p0,N)=q\therefore gcd(p_0, N) = q

直接通过gcd计算出q， 再 n // q = p

exercise

moectf2024_大白兔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import *

flag = b'moectf{xxxxxxxxxx}'
m = bytes_to_long(flag)

e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697

def encrypt(m , e1 , e2):
    p = getPrime(512)
    q = getPrime(512)
    N = p*q
    c1 = pow((3*p + 7*q),e1,N)
    c2 = pow((2*p + 5*q),e2,N)
    e = 65537
    c = pow(m , e , N)
    return c
    

print(encrypt(m ,e1 , e2))

'''
N = 107840121617107284699019090755767399009554361670188656102287857367092313896799727185137951450003247965287300048132826912467422962758914809476564079425779097585271563973653308788065070590668934509937791637166407147571226702362485442679293305752947015356987589781998813882776841558543311396327103000285832158267
c1 = 15278844009298149463236710060119404122281203585460351155794211733716186259289419248721909282013233358914974167205731639272302971369075321450669419689268407608888816060862821686659088366316321953682936422067632021137937376646898475874811704685412676289281874194427175778134400538795937306359483779509843470045
c2 = 21094604591001258468822028459854756976693597859353651781642590543104398882448014423389799438692388258400734914492082531343013931478752601777032815369293749155925484130072691903725072096643826915317436719353858305966176758359761523170683475946913692317028587403027415142211886317152812178943344234591487108474
c = 21770231043448943684137443679409353766384859347908158264676803189707943062309013723698099073818477179441395009450511276043831958306355425252049047563947202180509717848175083113955255931885159933086221453965914552773593606054520151827862155643433544585058451821992566091775233163599161774796561236063625305050
'''

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *

e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
N = 107840121617107284699019090755767399009554361670188656102287857367092313896799727185137951450003247965287300048132826912467422962758914809476564079425779097585271563973653308788065070590668934509937791637166407147571226702362485442679293305752947015356987589781998813882776841558543311396327103000285832158267
c1 = 15278844009298149463236710060119404122281203585460351155794211733716186259289419248721909282013233358914974167205731639272302971369075321450669419689268407608888816060862821686659088366316321953682936422067632021137937376646898475874811704685412676289281874194427175778134400538795937306359483779509843470045
c2 = 21094604591001258468822028459854756976693597859353651781642590543104398882448014423389799438692388258400734914492082531343013931478752601777032815369293749155925484130072691903725072096643826915317436719353858305966176758359761523170683475946913692317028587403027415142211886317152812178943344234591487108474
c = 21770231043448943684137443679409353766384859347908158264676803189707943062309013723698099073818477179441395009450511276043831958306355425252049047563947202180509717848175083113955255931885159933086221453965914552773593606054520151827862155643433544585058451821992566091775233163599161774796561236063625305050
e = 65537

ee = e1*e2
s1 = pow(c1, e2, N) # 不管啥都把模带上稳妥些
s2 = pow(c2, e1, N)
f = (pow(2, ee, N) * s1 - pow(3, ee, N) * s2) % N
q = GCD(f, N)
p = N // q
assert p*q == N
phi = N - (p+q) + 1
d = inverse(e, phi)
m = pow(c, d, N)
print(long_to_bytes(m))

CRYPTOHACK_Modular Binomials

1
2
3
4
5
N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

exp

一样的思路

  1. 先转换 c1, c2 的二项式
  2. 使 c1 , c2 幂数相同
  3. 乘个啥玩意儿消去一项
  4. 剩下的部分分别模p， 模q， 看包含 N 中的哪个因子
  5. gcd(剩下的部分， N) = 包含的那个因子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *

N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

cc1 = pow(c1, e2, N)
cc2 = pow(c2, e1, N)
ee = e1*e2
s1 = pow(5, ee, N)
s2 = pow(2, ee, N)
f = (s1*cc1 - s2*cc2) % N
q = GCD(f, N)
p = N // q
assert p*q == N
print(f"crypto{{{p},{q}}}")  # 使用双花括号来转义花括号，使其成为普通字符