iloveflag-blog

RSA与费马小定理

字数统计: 660阅读时长: 2 min
2020/09/23 Share

RSA

20200923204921

费马小定理检验素数

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

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

当n为质数时,系数分子就不能被分母约分,保留n,所以存在了倍数关系

杨辉三角与费马小定理的关系

杨辉三角

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

费马小定理

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

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

关系

那么两个式子相加

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

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

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

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

CTF

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

WP

最大公约数与费马小定理求p的推导过程

待更新

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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}

链接

RSA加密算法

费马小定理

费马是如何检验素数的?杨辉三角形和素数有什么关系?

例题

CATALOG
  1. 1. RSA
  2. 2. 费马小定理检验素数
  3. 3. 杨辉三角与费马小定理的关系
    1. 3.1. 杨辉三角
    2. 3.2. 费马小定理
    3. 3.3. 关系
  4. 4. CTF
  5. 5. WP
    1. 5.1. 最大公约数与费马小定理求p的推导过程
    2. 5.2. exp
  6. 6. 链接