简单数论

1.题目

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

m=libnum.s2n(flag)
p=libnum.generate_prime(512)
q=libnum.generate_prime(512)
e=65537
n=p*q
h1=pow(2022*p+2021*q,1919,n)
h2=pow(2021*p+2022*q,9191,n)
c=pow(m, e, n)
print("h1 =",h1)
print("h2 =",h2)
print("n =",n)
print("c =",c)

# h1 = 52408251188324218903110941264939993113975640153083218922769421840332203797616035427954737245841881865789684056932017108143362555654581516864554836364582093672497770004012951637580263775831046584440757881414926256334211093224016030790721630120764137147421992220495745906551704882349255846384332175635320111056
# h2 = 38120185829022018408602777600386435127600977064989894855304233013687239209233033212098836145377561174559693485658449220754164165043678509639723798848418062817503476159113376142481660052244331224625904361564766295720664745514420764149786267893188634354138787978903879399624379500094311436197503665452805745503
# n = 88545306160614611300057163915799002191117198821882935232959835324291423839828166715364894615936159732519222088316799102783433084387211698008573905863027546955157467861089839377561074346338978483715224405022670560824364098790835571592973409253255954862511470752552311055837950089395161607605619715303690606067
# c = 65934218167834476684045643333199256590467208964181396500329418110791774250123727801998303132514398214437531616821271834259897104098812221595756648226251674484230574909111490039284126690100214601570566850407850174371440011211665465943047222499495874102515043533516605916704246797243383577457909418615062102384

2.思路

\[ \begin{gather} h_1=(2022p+2021q)^{1919}\%n\\ h_2=(2021p+2022q)^{9191}\%n\\ \downarrow\\ h_1^{9191}=(2022p+2021q)^{1919*9191}\%n\\ h_2^{1919}=(2021p+2022q)^{9191*1919}\%n\\ \downarrow\\ h_1^{9191}=(2022p+2021q)^{1919*9191}+k_1pq\\ h_2^{1919}=(2021p+2022q)^{9191*1919}+k_2pq\\ \downarrow\\ h_1^{9191}\%q=(2022p+2021q)^{1919*9191}\%q+k_1pq\%q\\ h_2^{1919}\%q=(2021p+2022q)^{9191*1919}\%q+k_2pq\%q\\ \downarrow\\ h_1^{9191}\%q=(2022p)^{1919*9191}\%q\\ h_2^{1919}\%q=(2021p)^{9191*1919}\%q\\ \downarrow\\ h_1^{9191}=(2022p)^{1919*9191}+k_3q\\ h_2^{1919}=(2021p)^{9191*1919}+k_4q\\ \downarrow\\ h_1^{9191}*2021^{1919*9191}=(2022p)^{1919*9191}*2021^{1919*9191}+k_5q\\ h_2^{1919}*2022^{1919*9191}=(2021p)^{9191*1919}*2022^{1919*9191}+k_6q\\ \downarrow\\ h_1^{9191}*2021^{1919*9191}=(2021*2022p)^{1919*9191}+k_5q\\ h_2^{1919}*2022^{1919*9191}=(2021*2022p)^{1919*9191}+k_6q\\ \downarrow^{h_2-h_1}\\ h_2^{1919}*2022^{1919*9191}-h_1^{9191}*2021^{1919*9191}=k_7q\\ \end{gather} \]

得出\(h_2^{1919}*2022^{1919*9191}-h_1^{9191}*2021^{1919*9191}\)是q的倍数，通过gcd(\(h_2^{1919}*2022^{1919*9191}-h_1^{9191}*2021^{1919*9191}\),n)即可得出q（为了减少计算量可以把每项模n再进行计算），然后p=n//q，然后按常规方法解出m，即可得到flag

3.解题脚本

from Crypto.Util.number import *
import gmpy2

e = 65537
h1 = 52408251188324218903110941264939993113975640153083218922769421840332203797616035427954737245841881865789684056932017108143362555654581516864554836364582093672497770004012951637580263775831046584440757881414926256334211093224016030790721630120764137147421992220495745906551704882349255846384332175635320111056
h2 = 38120185829022018408602777600386435127600977064989894855304233013687239209233033212098836145377561174559693485658449220754164165043678509639723798848418062817503476159113376142481660052244331224625904361564766295720664745514420764149786267893188634354138787978903879399624379500094311436197503665452805745503
n = 88545306160614611300057163915799002191117198821882935232959835324291423839828166715364894615936159732519222088316799102783433084387211698008573905863027546955157467861089839377561074346338978483715224405022670560824364098790835571592973409253255954862511470752552311055837950089395161607605619715303690606067
c = 65934218167834476684045643333199256590467208964181396500329418110791774250123727801998303132514398214437531616821271834259897104098812221595756648226251674484230574909111490039284126690100214601570566850407850174371440011211665465943047222499495874102515043533516605916704246797243383577457909418615062102384

q = GCD(pow(h2,1919,n)*pow(2022,1919*9191,n)-pow(h1,9191,n)*pow(2021,1919*9191,n),n)
p = n // q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)

print(long_to_bytes(m))