RSA与费马小定理

ctf

字数统计: 763阅读时长: 3 min

 2020/09/23   Share

费马小定理与证明

杨辉三角

$(x+1)^{p}$二项式展开减去第一项和最后一项，则
$(n+1)^{p}-n^{p}-1$是p的倍数

费马小定理

费马小定理是数论中的一个定理：假如a是一个整数，p是一个质数，那么$a^{p}-a$是p的倍数，可以表示为

$a^{p} \equiv a \quad(\bmod p)$ $a^{p} /p -a/p=0$

即两个数同余
经过变形可成为

$a(a^{p-1} -1)\equiv 1 \quad(\bmod p)$

则如果a不是p的倍数，这个定理也可以写成

$a^{p-1} \equiv 1 \quad(\bmod p)$

证明

通过杨辉三角形可以看出$(x+1)^{p}$当p为素数时，二项式展开，除了第一项和最后一项，其他系数都是p的倍数，因为二项式展开的系数为${C_{n}^{k-1}}$
如图:

$(x+1)^{n}=x^{n}+n x^{n-1}+\frac{n(n-1)}{2} x^{n-2}+\frac{n(n-1)(n-2)}{2 \times 3} x^{n-3}+...$

当n为质数时，系数分子就不能被分母约分，保留n，所以存在了倍数关系
要证明$a^{p}-a$是p的倍数，那么两个式子相加

$((a+1)^{p}-a^{p}-1)+(a^{p}-a) \equiv (a+1)^{p}-(a+1)$ $((a+1)^{p}-a^{p}-1)必为p的倍数, (a^{p}-a)和(a+1)^{p}-(a+1)相差1项$

则用数学归纳法证明
a=1时成立

$a^{p}-a=1-1 \equiv 0$

0可以被任意素数整除
证明完毕

卡迈尔数

但是费马素性检验不是充分必要的

(卡迈克尔数 Carmichael number）
更极端的反例是卡迈克尔数：假设a与561互质，则$a^560$被561除都余1。这样的数被称为卡迈克尔数，561是最小的卡迈克尔数

欧拉定理

$\phi(n)$表示小于n的素数个数
例如$\phi(8)=4$
取出两个互素的a和n
$a^{\phi(n)}-1=n$的倍数
$a^{\phi(n)}=1 \quad(\bmod n)$
当n=素数时，$\phi(n)$=n-1
则$a^{n-1}=1 \quad(\bmod n)$
即费马小定理

RSA

20200923204921

为什么e和n要互质?

$ed=1 \quad(\bmod n)$
d是e的模逆元，由同余解的存在性可知
$ax=b \quad(\bmod m)$
x解的个数为gcd(a,m)

费马小定理与rsa的奶子关系

20201103105525

CTF

import gmpy2
from Crypto.Util import number
FLAG = "************************************"
mybytes = FLAG.encode('utf-8')
flag = int.from_bytes(mybytes, 'little')
e = 65537
p = number.getPrime(2048)
q = number.getPrime(2048)
r = 663111019425944540514080507309
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi) #find d that e*d mod phi=1
k = (p-r)*d
enc = gmpy2.powmod(flag, e, p * q) # pow(flag,e) mod (p*q)
print("n", p*q)
print("e", e)
print("k", k)
print("enc", enc)
#n = 764789710135699120066739558828098633577013306253421553430847195908034244362783426399681889172711929793563731863384139872322402736681090085666598621114324939409408964563306677742741428195863966989898498906831204752157005288028055139678360291316075877219030667685558110323821117721956754066208709423674599070852863328081495564626811408881020379619280834606394873439653313479059367387482717449792132890040814302415880441497255508283415162957128101398055871020323457216741679183472993371932538507867941404875130906965322325847739960927163953539809036794727803609900302282116111729856921452995125114084009947877974251520302979592670067613546606144401980991349553446645445805493512099309153534117016242573188431650384053169169037929526267038289233193459168030309932136331042640250813278140485915435024593329769782476261202489190771392735516338128092461124553594475652005536021219004598007475896848018535883345275525698202912140165492830229318458220859621536946916060728450732293426918231002157025978449298255884607961112874423611768107044113994666509578842156149561812558917421973274685922015605898024562717582262195308188734233843441532414373538708641762976079302448555298697105806160447760545580129674268456624678445339254341281619657391
#e = 65537
#k = 11376230879464757138290711299984908778464289005173308608189545435463525777268265977729128994228398091834020517958489408848527244519720030536561582611244172458641332639632981518360153087977263620583037286868169984156081495975325137150308201181821183705406433865681037783672009245951450744893423967519534524564872374719067025656950703655360275719627553370956932353637447232396991057691540662128565377895571740302756624004115592822652032877787683190174651306416910281916239819514603714322474683948222133746696116347630808594215555899448203106168014521796360515931362871133025281314243806320464177354177591228332335003551614106832308993911767231860241219942930903683175017203214440697826698228720134550320203010201162227480574211558033922830875117868895970801183417628548046732735178684031479465866770555097097049039401697156697973726498505003813383696303149763801522877588926847414588086172187481338569607545109010485980789181176815929895776940791230453092924387422291052184177606568352378605741988346025715326590594607822822612290794021218154340474272030636989456754518795702696600378337733961339618639033487933752890208434609460829539754273357617487166483257224739734126886305602260084115687043018921964438528469917594211427068125222889990486298031116975211308319185008573568652053973895884503801570264426091699176024805955546836991196229298757508243251307657063191639987383783941231455894746140575040062497070116929901714063774213552073013057990495816268901523247960107878691144148350592800965125699719038873342744331101838577313168280165305316417387319080806526792235761499758367535234473231638455540814177514642349235328627096125963532214440347089295557895745448430528014032156116184317483847359679936198373071447646642313893200567858353913090847963730766120387076016399374559419994285225024354973914324859198201290795827297428960819444555465333396
#enc = 412093036715903128816790953795699287022044216068094761688962237067827011617922387939870348912875721751778771109858780403824076311902683730492233931750791970774429713426105151785974216855033623062170836476535146856670899254646842108216255981889833334584536802754025396041247764488790105972219057375460371490647125698609400300341077029080773163205863745828608512034607447580944258673896462752843386985550199652916670962124910468248134403955249972471292321362551835390767312197538200826967705545638519964452471211583957033796921294363923837791013671753387403623271493340254878112019414988938587497894192020830896786221505942049263600607820879465571254636671934958681859231524860851162323564163724658591380505948307672122532671989440138584048326517351031499576198020315578054570580122064097161740727146596055708533260148164018981133880628043807746488833455752164612507117536000447164187430205500714960736257690852385172040877083740844061320535351927024358525062923099609550661254084283782830424441345671163835622431355492805291956376976262133352159700906015781429216234017365670205976334239654019004580276209764555902322660518746581075014319520704136021241687389064873964101439926478194416552866446689392251268071780662459334135965480296

exp

import gmpy2
import libnum
n = 764789710135699120066739558828098633577013306253421553430847195908034244362783426399681889172711929793563731863384139872322402736681090085666598621114324939409408964563306677742741428195863966989898498906831204752157005288028055139678360291316075877219030667685558110323821117721956754066208709423674599070852863328081495564626811408881020379619280834606394873439653313479059367387482717449792132890040814302415880441497255508283415162957128101398055871020323457216741679183472993371932538507867941404875130906965322325847739960927163953539809036794727803609900302282116111729856921452995125114084009947877974251520302979592670067613546606144401980991349553446645445805493512099309153534117016242573188431650384053169169037929526267038289233193459168030309932136331042640250813278140485915435024593329769782476261202489190771392735516338128092461124553594475652005536021219004598007475896848018535883345275525698202912140165492830229318458220859621536946916060728450732293426918231002157025978449298255884607961112874423611768107044113994666509578842156149561812558917421973274685922015605898024562717582262195308188734233843441532414373538708641762976079302448555298697105806160447760545580129674268456624678445339254341281619657391
e = 65537
k = 11376230879464757138290711299984908778464289005173308608189545435463525777268265977729128994228398091834020517958489408848527244519720030536561582611244172458641332639632981518360153087977263620583037286868169984156081495975325137150308201181821183705406433865681037783672009245951450744893423967519534524564872374719067025656950703655360275719627553370956932353637447232396991057691540662128565377895571740302756624004115592822652032877787683190174651306416910281916239819514603714322474683948222133746696116347630808594215555899448203106168014521796360515931362871133025281314243806320464177354177591228332335003551614106832308993911767231860241219942930903683175017203214440697826698228720134550320203010201162227480574211558033922830875117868895970801183417628548046732735178684031479465866770555097097049039401697156697973726498505003813383696303149763801522877588926847414588086172187481338569607545109010485980789181176815929895776940791230453092924387422291052184177606568352378605741988346025715326590594607822822612290794021218154340474272030636989456754518795702696600378337733961339618639033487933752890208434609460829539754273357617487166483257224739734126886305602260084115687043018921964438528469917594211427068125222889990486298031116975211308319185008573568652053973895884503801570264426091699176024805955546836991196229298757508243251307657063191639987383783941231455894746140575040062497070116929901714063774213552073013057990495816268901523247960107878691144148350592800965125699719038873342744331101838577313168280165305316417387319080806526792235761499758367535234473231638455540814177514642349235328627096125963532214440347089295557895745448430528014032156116184317483847359679936198373071447646642313893200567858353913090847963730766120387076016399374559419994285225024354973914324859198201290795827297428960819444555465333396
enc = 412093036715903128816790953795699287022044216068094761688962237067827011617922387939870348912875721751778771109858780403824076311902683730492233931750791970774429713426105151785974216855033623062170836476535146856670899254646842108216255981889833334584536802754025396041247764488790105972219057375460371490647125698609400300341077029080773163205863745828608512034607447580944258673896462752843386985550199652916670962124910468248134403955249972471292321362551835390767312197538200826967705545638519964452471211583957033796921294363923837791013671753387403623271493340254878112019414988938587497894192020830896786221505942049263600607820879465571254636671934958681859231524860851162323564163724658591380505948307672122532671989440138584048326517351031499576198020315578054570580122064097161740727146596055708533260148164018981133880628043807746488833455752164612507117536000447164187430205500714960736257690852385172040877083740844061320535351927024358525062923099609550661254084283782830424441345671163835622431355492805291956376976262133352159700906015781429216234017365670205976334239654019004580276209764555902322660518746581075014319520704136021241687389064873964101439926478194416552866446689392251268071780662459334135965480296
r = 663111019425944540514080507309
aa=pow(2,e*k+r-1,n)-1
p=gmpy2.gcd(aa,n) #最大公约数求p
q=n/p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=gmpy2.powmod(enc,d,n)
print(libnum.n2s(m)[::-1]) #转换为字符串反向
#ZJCTF(f0r_w311_inj3ct}