NC不互素2

1.题目

import libnum
from flag import flag
assert flag[:5] == b'flag{'

m=libnum.s2n(flag)
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
n=p*q
e=65537
c=pow(m*p+n,e,n)
print("n =",n)
print("c =",c)
print("e =",e)

# n = 20907659771977390321625197455070749374316698255628596726776342105324211545142012274040941004018721265472254071032578096250685359985882566885436374279774278423314607501642224412143471480982685151029050777790073587324859377653331372384124481912058726904992676169132973906213094360762583071129161942038073844126199053319529934663766486323874957814285941502920348241014559579614041960734514600088675168838996375535243097400999377564854704919935200452266401198476578899716735971622826315544696276960623115809160349849364532177942363314527748670317237948647163395744812690352835516405710940917091943319041899179944016773757
# c = 10095118897695767096498558802557145433839785043008067177533638379011286854755660650460352622772882329829116004970967429980487206686090261385075708329144463747027855722633959426958070719330073283228012426460304356979946012805485539159722434707782682562729198346991489935313051096816650444868070099602889920122282706905815438806066859993904017821371398093510850369176851176793753701405043371981386886258367792199419479707034680530499202896774421152196344125515638190250076858485077409091501853400584250073084257248075134271303990206769692955172934135582531822648729099950543304317787784532541717935769076846420061835609
# e = 65537

2.思路

\[ \begin{gather} c=(mp+n)^e\ \%n\\ \downarrow\\ c=(mp+n)^e+kn\\ \downarrow^{两边同时模n}\\ c\%n=(mp+n)^e\%n+kn\%n\\ \downarrow\\ c\%n=(mp)^e\%n\\ \downarrow\\ c=(mp)^e+kn\\ \downarrow\\ c=(mp)^e+kpq\\ \downarrow^{两边同时模p}\\ c\%p=(mp)^e\%p+kpq\%p\\ \downarrow\\ c\%p=0\\ \end{gather} \]

从上面的推导过程可以看出(mp+n)中的n是不起作用的，去掉也和原式相等

所以c是p的倍数，可以用gcd(c,n)求出p，q=n//p，然后按常规方法解出m1，因为m1=m*p，所以m=m1//p，即可得到flag

3.解题脚本

from Crypto.Util.number import *
import gmpy2

n = 20907659771977390321625197455070749374316698255628596726776342105324211545142012274040941004018721265472254071032578096250685359985882566885436374279774278423314607501642224412143471480982685151029050777790073587324859377653331372384124481912058726904992676169132973906213094360762583071129161942038073844126199053319529934663766486323874957814285941502920348241014559579614041960734514600088675168838996375535243097400999377564854704919935200452266401198476578899716735971622826315544696276960623115809160349849364532177942363314527748670317237948647163395744812690352835516405710940917091943319041899179944016773757
c = 10095118897695767096498558802557145433839785043008067177533638379011286854755660650460352622772882329829116004970967429980487206686090261385075708329144463747027855722633959426958070719330073283228012426460304356979946012805485539159722434707782682562729198346991489935313051096816650444868070099602889920122282706905815438806066859993904017821371398093510850369176851176793753701405043371981386886258367792199419479707034680530499202896774421152196344125515638190250076858485077409091501853400584250073084257248075134271303990206769692955172934135582531822648729099950543304317787784532541717935769076846420061835609
e = 65537

p = GCD(n,c)
q = n // p
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m1 = pow(c, d, n)
m = m1 // p
print(long_to_bytes(m))