费马小定理

1.题目

import libnum
from flag import flag
from Crypto.Util.number import *
assert flag[:5] == b'flag{'
m = libnum.s2n(flag)

e =65537
p = getPrime(1024)
q = getPrime(1024)
n=p*q
c = pow(m, e, n)
hint = pow(2020 * p + 2021, q, n)

print(f'n={n}')
print(f'c={c}')
print(f'hint={hint}')

# n=19758693057470719265452480505233561735506365693302326248065184045520089010653869545206742051760242586340940449536352551333089498820325722697448811788731593383663808932452166942285923287406110580952841326403830034237038921408084364811760879861696554117463613922703605235222303598325536275259341939770300705306087223946835884214525887314718135338104619860910956141883248592612892362367122253521669535872666365125845078511305060252336198880082780056124662489894759312076528707223240954649703104805021331022345117791731817543137188962469427236311236700739396746380000375211072202375181095053521278987646084815581084696941
# c=16498264098538117589281424565992536658263121499215493577856742266000830380523726861899589053741599982500535069893557741186431123616201272627584314395977313396241832000671516172847749695200847005432789305173187083817712181447477134229431828760607519664941025426618258546285246312918925558776142965195098715868915303035039672960689888177300754866057012173890733235476519204636145765222990959749549698674959955357085652700821221476693496091331019853599929311093372159977105968343183075690226379862997592783290723546093758978899363441446395522860726889570046957347981941073406675416198056519611035020437650279011557892603
# hint=17383532565619140648537027416979830792219578051984480305886610241702801116875343950629688640658564174494109792341377534170966239382294317806276443709178228197359976983397998582651419544052022792302975548009093920991553720127625623911681620991750701340851431386587679279397141698892659226762471484474826954942932599668188624518442553980573779436981069830586784746941684877046270285623118308425369226110958819070913036574159756433610124643666868508419367337709271378203767687307781665142711115907772614139515307798006738768650468963205610554855828074439892146335923524502120492165738126231161227021813401053461078277608

2.思路

从题中得知\(hint=(2020p+2021)^q\ \%\ n\)（后hint简写为h）

\[ \begin{gather} h=(2020p+2021)^q\ \% \ n \\ \downarrow \\ h=(2020p+2021)^q+kn \\ \downarrow \\ h=k_1p+2021^q+kpq \\ \downarrow ^{两边同时模p} \\ h\%p=k_1p\%p+2021^q\%p+kpq\%p\\ \downarrow \\ h\%p=2021^q\%p \\ \downarrow \\ h+k_2p=2021^q \\ \downarrow \\ 2021^q-h=k_2p \end{gather} \]

所以只要gcd(\((2021^q-h),n\))就可以求出p，但是此时并不知道q的值，所以继续推导

\[ \begin{gather} n=p*q\\ \downarrow^{两边同时除以q} \\ n/q=p \\ \downarrow \\ n/q-1=p-1 \\ \downarrow^{两边同时乘以q} \\ n-q=(p-1)q \\ \downarrow \\ q=n-(p-1)q \\ \end{gather} \]

\[ \begin{gather} h\%p=2021^{n-q(p-1)}\%p\\ \downarrow\\ h\%p=2021^n\%p\ *(2021^{-q})^{p-1}\%p\\ \downarrow^{根据费马小定理a^{p-1}\%p=1\%p}\\ h\%p=2021^n\%p\\ \downarrow\\ h+k_3p=2021^n\\ \downarrow\\ 2021^n-h=k_3p \end{gather} \]

现在式子中都是已知数，可以求出p=gcd(\((2021^n\%n-h),n\))（因为\(2021^n\)比较大，所以%n之后再进行计算，结果相同），q=n//p，然后按照常规解法解出m，即可得到flag

3.解题脚本

from Crypto.Util.number import *
import gmpy2

e = 65537
n=19758693057470719265452480505233561735506365693302326248065184045520089010653869545206742051760242586340940449536352551333089498820325722697448811788731593383663808932452166942285923287406110580952841326403830034237038921408084364811760879861696554117463613922703605235222303598325536275259341939770300705306087223946835884214525887314718135338104619860910956141883248592612892362367122253521669535872666365125845078511305060252336198880082780056124662489894759312076528707223240954649703104805021331022345117791731817543137188962469427236311236700739396746380000375211072202375181095053521278987646084815581084696941
c=16498264098538117589281424565992536658263121499215493577856742266000830380523726861899589053741599982500535069893557741186431123616201272627584314395977313396241832000671516172847749695200847005432789305173187083817712181447477134229431828760607519664941025426618258546285246312918925558776142965195098715868915303035039672960689888177300754866057012173890733235476519204636145765222990959749549698674959955357085652700821221476693496091331019853599929311093372159977105968343183075690226379862997592783290723546093758978899363441446395522860726889570046957347981941073406675416198056519611035020437650279011557892603
hint=17383532565619140648537027416979830792219578051984480305886610241702801116875343950629688640658564174494109792341377534170966239382294317806276443709178228197359976983397998582651419544052022792302975548009093920991553720127625623911681620991750701340851431386587679279397141698892659226762471484474826954942932599668188624518442553980573779436981069830586784746941684877046270285623118308425369226110958819070913036574159756433610124643666868508419367337709271378203767687307781665142711115907772614139515307798006738768650468963205610554855828074439892146335923524502120492165738126231161227021813401053461078277608

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