rsa基础

rsa基础

rsa概述

m 明⽂
c 密⽂
p、q 素数
e 公钥
d 私钥
n=p*q

rsa算法核心公式
加密
c = ( m e ) m o d n c=(m^e)modn c=(me)modn
解密
m = ( c d ) m o d n m=(c^d)modn m=(cd)modn

rsa加密具体过程

1.任意找出两个整数q和p（q，p互素），计算n
$$n=p\times q$$
2.计算欧拉函数
$$\phi (n)=(p-1)\times (q-1)$$
3.公钥e
$$1<e<\phi (n)$$

$$(e,\phi (n))=1$$

4.私钥d
$$ed\equiv 1mod\phi (n)$$

rsa的数学证明

证明欧拉定理

欧拉函数：
在数论，对正整数n，欧拉函数是小于等于n的正整数中与n互质的数的数目。

完全余数集合：
定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。

根据定义显然有
$$|Zn|=\phi (n)$$
当n满足条件
$$n=p\times q$$
推得
Z n = { 1 , 2 , 3 ⋯ , n − 1 } − { p , 2 p ⋯ , ( q − 1 ) p } − { q , 2 q ⋯ , ( p − 1 ) q } Zn=\{1,2,3\cdots,n-1\}-\{p,2p\cdots,(q-1)p\}-\{q,2q\cdots,(p-1)q\} Zn={1,2,3⋯,n−1}−{p,2p⋯,(q−1)p}−{q,2q⋯,(p−1)q}
可得
$$\phi (n)=n-1-(q-1)-(p-1)=(p-1)\times (q-1)$$
欧拉定理：
a φ ( n ) ≡ 1 m o d n a^{\varphi(n)}\equiv1\ mod\ n aφ(n)≡1 mod n
证明

令
Z n = { X 1 , X 2 ⋯ , X n } S = { a X 1 m o d n , a X 2 m o d n ⋯ , a X φ ( n ) m o d } Zn=\{X_{1},X_{2}\cdots,X_{n}\}\\ S=\{aX_{1}mod\ n,aX_{2}mod\ n\cdots,aX_{\varphi(n)}mod\} Zn={X1​,X2​⋯,Xn​}S={aX1​mod n,aX2​mod n⋯,aXφ(n)​mod}
因为
( a , n ) = 1 ( X i , n ) = 1 ( 1 ≤ i ≤ φ ( n ) ) (a,n)=1\\ (X_{i},n)=1(1\leq i \leq \varphi(n)) (a,n)=1(Xi​,n)=1(1≤i≤φ(n))
所以
a X i m o d n ∈ Z n aX_{i}\ mod\ n \in Zn aXi​ mod n∈Zn
又因为
X i ≠ X j ( i < j ) X_{i}\neq X_{j}(iXi​​=Xj​(i<j)
所以
a X i ≠ a X j m o d n aX_{i}\neq aX_{j}\ mod\ n aXi​​=aXj​ mod n
得到
$$Zn=S$$
则
a φ ( n ) × X 1 X 2 ⋯ X n m o d n ≡ ( a × X 1 ) ( a × X 2 ) ⋯ ( a × X n ) m o d n ≡ ( a × X 1 m o d n ) ( a × X 2 m o d n ) ⋯ ( a × X n m o d n ) m o d n ≡ X 1 X 2 ⋯ X n m o d n a^{\varphi(n)}\times X_{1}X_{2}\cdots X_{n}\ mod\ n\\ \equiv(a\times X_{1})(a\times X_{2})\cdots (a\times X_{n})\ mod\ n\\ \equiv(a\times X_{1}\ mod\ n)(a\times X_{2}\ mod\ n)\cdots (a\times X_{n}\ mod\ n)\ mod\ n\\ \equiv X_{1}X_{2}\cdots X_{n}\ mod\ n aφ(n)×X1​X2​⋯Xn​ mod n≡(a×X1​)(a×X2​)⋯(a×Xn​) mod n≡(a×X1​ mod n)(a×X2​ mod n)⋯(a×Xn​ mod n) mod n≡X1​X2​⋯Xn​ mod n
根据消去律可得
a φ ( n ) ≡ 1 m o d n ( 欧 拉 定 理 得 证 ) a^{\varphi(n)}\equiv1\ mod\ n(欧拉定理得证) aφ(n)≡1 mod n(欧拉定理得证)

证明rsa算法

存在y满足
$$ed\equiv 1+y\phi (n)$$
因为
c = ( m e ) m o d n c d ≡ m e d m o d n c d ≡ m 1 + y φ ( n ) m o d n c=(m^e)\ mod\ n\\ c^d\equiv m^{ed}\ mod\ n\\ c^d\equiv m^{1+y\varphi(n)}\ mod\ n c=(me) mod ncd≡med mod ncd≡m1+yφ(n) mod n
又因为
a φ ( n ) ≡ 1 m o d n a^{\varphi(n)}\equiv1\ mod\ n aφ(n)≡1 mod n
因为n为两个大素数相乘的结果，而m的值并不大，所以
$$(m,n)=1$$
得到
m = c d m o d n m=c^d\ mod\ n m=cd mod n

求逆元方法

扩展欧几里得定理:

$$ax+by=gcd(a,b)$$

数学归纳法证明

1.当b=0时，式子显然成立

2.假设bx_2+（a\ mod\ b）y_2=gcd（b，a\ mod\ b）成立，证明ax_1+by_1=gcd(a,b)成立
令a=kb+c,移项得：c=a-kb,代入已知式子
b x 2 + ( a − k b ) y 2 = g c d ( b , a m o d b ) = g c d ( a , b ) = a y 2 + b ( x 2 − k y 2 ) a x 1 + b y 1 = g c d ( a , b ) 得 证 bx_2+(a-kb)y_2=gcd(b,a\ mod\ b)=gcd(a,b)=ay_2+b(x_2-ky_2)\\ ax_1+by_1=gcd(a,b)得证 bx2​+(a−kb)y2​=gcd(b,a mod b)=gcd(a,b)=ay2​+b(x2​−ky2​)ax1​+by1​=gcd(a,b)得证

若 ed ≡ 1 mod phi, 则称e关于1模phi的乘法逆元为d。也可表示为ed ≡ 1 (mod phi)。逆元相当于数论中的倒数。条件：
只有当gcd(e,phi) = 1时,m 才有关于模phi的逆元。

代入上式得
e x 1 + φ ( n ) y 1 = 1 ( d = x 1 ) ex_1+\varphi(n)y_1=1(d=x_1) ex1​+φ(n)y1​=1(d=x1​)
递推可求出逆元d。(如此便不难解释我们常用的invert函数)

例题

直接模数分解N

c = 34533624647193630459864898193867716746457242698156942414136896826169638045191
n = 38915622445322594788113853812230848083133274092845339659216148461050062802771
e = 65537
q=184447441856923584506972548629664462921
p=210984885740565358250291732634631217851

分解质因数网站

http://factordb.com/

分解质因数工具yafu

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
import gmpy2
import libnum
import hashlib
q = 210984885740565358250291732634631217851
p = 184447441856923584506972548629664462921
c = 34533624647193630459864898193867716746457242698156942414136896826169638045191
n = 38915622445322594788113853812230848083133274092845339659216148461050062802771
e = 65537
n_ol = (p-1) * (q-1)
d = gmpy2.invert(e,n_ol)
m = gmpy2.powmod(c,d,n)
print(libnum.n2s(m))

公约数模数分解

如果在信息传递的过程中，不⼩⼼在两次通信中⽣成的⼤素数有⼀个是相同的，那么就可以通过计算n的公约数来求密⽂

import gmpy2
from Crypto.Util.number import *
import libnum
n1=824309976713255040678774414315188911324305343946939068909416612709427405647590959202342069019687909827092434444738101792679253192217384554228922429405912765227299967576480004693502002706412618405848902047952249003683180646566555226980812871255985212785459728851482116385274886923030294336883118688943249637504111890941209117072125746914179382718841738938542647288128064878216596964710061943380933923317756767868900496106852496453030519617669299982705549374229502330525781052290174942572613344201021252879326095620935532484506572612967292839330025773029359908312962614731172968139177410904955609738349904997096375511564814382685053981249781750176436863678070180664579983017200009530939815220400486376740060465859081480696946249903279025539697834581358967123153969680757041410395146786259547823312557522601991424424780515118072828799902432329203842554206968777062590538956711084620951141331083100850610394090226480405466880324484810299761769275660553824905489329036439444269606193857756472844072315538452095272865161396795572965527449721108417342506231371917632592432396627440113643668181341007626924926752996257541349928107829776244387124514376067059436403317102173969866403920047378658985491771106094848218483420872665866345564496827
c1=619914776107204299421445515173752551578219512744832453386701408956131174382320293166571812398142061624071844793902243230988065164689738932213640598607827763120716664826659348935506492768840667618225389848502303543184323923750014314468273838436900100602616360301578680417070089037669208417514209496064782776638328659280595442584379339709690595064375146973041893766612952550104106304945793198707913036776562970941681277387345166363055403617979919206215550071922838408131362316374998986152131970583571257394242002989402779457115646413931644663555330819307049576617764087014494844129906098270686406058331758868723651041516567453323769768954687687202307774567305854473941230877789037414544400622116272774149579612412707977679341464711326395329328746997671371678549747416132575437991623923520089934467780767741968218870533906551561755021778559582638320070802534402702441689980582215813996309661425381981953031455267480573603282477682645039060338023983236132572154559608798674661049316746566458858853902292172161686826090441354261889811244610252422433735484707855667726547016802906293840413275921015090833094030889513775808522094907659133321728552859456301911921882441570565302485792013026978232768832198065043569203133298692101550276793242
n2=905589252405843373769915380293297111534760160714737080968066656272265067237261488456971858456917989327188732044692331992189086519820435633306176464411261896021205034205490970644012401822191880790030875680376477319350989208508591406379353590606990790187262655027873609762696926884097121412806124968361945732028625146592611563133972373222186510357547047870461524686536342088980414561620202107652793943447542030500100100438546978201140485266000991269033918263304132180594282910120350517431177243383393951480422824952551390879069092986257009179295057946730605973160346524195449500021703749379427308594689270698548425547616170119689641602115020951172647164330653185839148908281150010508830578946902028400175833666756810132914706574636302946981088249485384995123961868977200184192366871488238130493276320548228987765469367680884015794318055385681062658024380060853629777987397931994453740025625110420802340709951010187420093537470088728911794883713099533087772597248823814645583216509715894593709142551596518622892980794670674353243620390795154580419812174256794942916769770550059026084217681241980763703393095418708693297369255695621169620925250022220663830988716484961599451891633153226183322921970730586750473413763286928431026521685503
c2=673931551637686573733931629946259955273050809105413358970865200931337620800601472110603043036230330369308198862836020608370123474012622263062171294537227742055596124838615523641277612651513376399422388728998723881390750022802888924469874997383403315092150360404739350111053494140814081500234944823944838342851486117828948012785473829786919168505899092926364319233270563625167199627187969831097779544020398227294075980803974781408640110508283074795045029934267450514279868306481527002838558049458432355280575187364797865249444744186956192622171429969229590383633312442290257337521345975778920638983724068169611670153900548976779043697802190755538297452687741381067668713313038012240461367852752324450730890453516495687244181415711446356025503068925532832441729497205951722171806849453544384230181139694995076734472488950052672657187723121538897634719634849656096065795251013915979636071103988880297602168171474689743253367371894201376237227289251967333720190335216940010089300129979229084907563995802063939925492798235466279747474279314734378363118765257958698347531646918232605837643662036855703017542230709453864001404693532353827244434156882808171822447915265832615174700571049925710515965628161428609658333071907595502748554057056
e = 65537 p = gmpy2.gcd(n1, n2)
print(p)
q = n1 // p 
n1_ol= (p - 1) * (q - 1)
q = n2// p 
n2_ol= (p - 1) * (q - 1)#d=gmpy2.invert(e,phi)
#m = pow(c1, d, n1) 
#print (long_to_bytes(m))
#print(libnum.n2s(m))d1 = gmpy2.invert(e,n1_ol)
m1= gmpy2.powmod(c1,d1,n1)
flag_1 = libnum.n2s(m1)
d2 = gmpy2.invert(e,n2_ol)
m2= gmpy2.powmod(c2,d2,n2)
flag_2 = libnum.n2s(m2)
print(str(flag_1) + str(flag_2))

peiqi

1,⽣成m的1~30的随机数次⽅ --->c1
2,⽤公钥(n,e)加密c1 --->c2
3,⽤公钥(peiqi,e)加密c2 --->c3
import gmpy2
import libnum
import binascii
n=26609708421376677628454402900087009846291167287676911113310671001067916215975654619357943078675057781284419971876364188201285756254849493795101184689472972451252559267516902582277554505702670110528791300961267369272080284734306320521513748467464633545459859474195548892296577923424451509458569436363709731402197392186162426572460924170144815459280292038798573517240473723212917475994555278140089160884080770934882248855992019482512867322735936930918031567624003424284507526700957286437082738893899468444943650565398213516262653534101927337725614414267105976588592783298584640344155571836662897588729868409203459117059
e=65537
peiqi=26609708421376677628454402900087009846291167287676911113310671001067916215975654619357943078675057781284419971876364188201285756254849493795101184689472972451252559267516902582277554505702670110528791300961267369272080284734306320521513748467464633545459859474195548892296577923424451509458569436363709731572253846238252647161985685432295738082766877396752019943012580636589164644125010073946413108951305564059881537794476457602047138719485228161010739405064157783241778448944470473298163156034126054406807297456937129548816176179704045207131224909988357244665869859061263890702529905040557579134990132844969289396259
c=5482202777490716534742001860730733245703162680164829063899425154796149111749426755752696933474476315957195654145886661833161128752650489114348801850277281013599078248459234726247608999052658393093261773012085995729908722425867518715231403283837324730986276769991562455242112930535955638946020374499583285967368081356098316200877276281391326176072541717343183325729633161998105304336388217903809696260815719456619790067591554832909766088841683629739632809828420661566086443444796658031348007908713779060772794447103923388464348339614504047304444504066194611260026519898801631578959669217929301004775518173581480779628
paq = ((peiqi - n - pow(520, 2)) // 520) # p+q
phi_n = n - paq + 1
phi_peiqi = n + 519 * paq + pow(519, 2)
d_peiqi = gmpy2.invert(e, phi_peiqi)
c_n = pow(c, d_peiqi, peiqi)
d_n = gmpy2.invert(e, phi_n)
c_fi = pow(c_n, d_n, n)
for k in range(1, 30):mid = gmpy2.iroot(c_fi, k)[0]try:#print libnum.n2s(mid)print (binascii.unhexlify(hex(mid)[2:]).decode('utf-8'))breakexcept:continue

小指数明文爆破

在⼀般的信息传递过程中e取值为65537，⼜时如果e的值过⼩
且满⾜m很⼩，n很⼤，e很⼩

题目

#n:  0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L
#e:  0x3
#c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
so,how to get the message?

题解

import gmpy2
import os
from functools import reduce 
from Crypto.Util.number import long_to_bytes 
def CRT(items):N = reduce(lambda x, y: x * y, (i[1] for i in items))result = 0for a, n in items:m = N // nd, r, s = gmpy2.gcdext(n, m)if d != 1:raise Exception("Input not pairwise co-prime")result += a * s * mreturn result % N, N
# e, n, c
e = 0x3
n=[0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L]
c=[0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365]
data = list(zip(c, n))
x, n = CRT(data)
m = gmpy2.iroot(gmpy2.mpz(x), e)[0].digits()
print('m is: ' + long_to_bytes(m))

大指数

题目

N =
101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322
747780420210884852166586717636559058152544979471
e =
467319195632657213071051804103025186766761355097379929126250929768490752621920925493230823675182643786305433382190257448209164719136960720502919906204865817194103543851217607613742293748476951482305960054099783833697403058160827702839096119563559721818480775199
20922059268376958811713365106925235218265173085
import hashlib
flag = "flag{" + hashlib.md5(hex(d)).hexdigest() + "}"
import RSAwienerHacker

题解

import RSAwienerHacker
import hashlib
N =101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471
e =46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
hack_d = RSAwienerHacker.hack_RSA(e, N)
print(hack_d)
flag = hashlib.md5(hex(hack_d)).hexdigest()
print(flag)

dp泄漏

1.dp是什么

$$dp=dmod(p-1)$$

2.推导过程

d p × e ≡ d × e m o d ( p − 1 ) d × e = k 1 ( p − 1 ) + d p × e dp\times e\equiv d\times e\ mod\ (p-1)\\ d\times e=k_1(p-1)+dp\times e dp×e≡d×e mod (p−1)d×e=k1​(p−1)+dp×e

结合
$$\begin{gathered} ed\equiv 1mod\phi (n) \\ \phi (n)=(p-1)\times (q-1) \end{gathered}$$
得到
k 1 ( p − 1 ) + d p × e ≡ 1 m o d ( p − 1 ) × ( q − 1 ) d p × e = [ k 2 ( p − 1 ) × ( q − 1 ) + 1 − k 1 ( p − 1 ) d p × e = [ k 2 ( q − 1 ) − k 1 ] ( p − 1 ) + 1 k_1(p-1)+dp\times e\equiv1\ mod\ (p-1)\times(q-1)\\ dp\times e=[k_2(p-1)\times(q-1)+1-k_1(p-1)\\ dp\times e=[k_2(q-1)-k_1](p-1)+1 k1​(p−1)+dp×e≡1 mod (p−1)×(q−1)dp×e=[k2​(p−1)×(q−1)+1−k1​(p−1)dp×e=[k2​(q−1)−k1​](p−1)+1
设
X = k 2 ( q − 1 ) − k 1 d p × e = X ( p − 1 ) + 1 X=k_2(q-1)-k_1\\ dp\times e=X(p-1)+1 X=k2​(q−1)−k1​dp×e=X(p−1)+1
因为
$$\begin{gathered} dp<p-1 \\ X<e \end{gathered}$$
所以
$$X\in (0,e)$$

3.WUSTCTF2020

题目

e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

代码

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
import gmpy2
import libnum
import hashlibe = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825for x in range(1, e):if(e*dp%x==1):p=(e*dp-1)//x+1if(n%p!=0):continueq=n//pphin=(p-1)*(q-1)d=gmpy2.invert(e, phin)m=gmpy2.powmod(c, d, n)print("m:",m)#print(hex(m)[2:])print(libnum.n2s(m))

4.西湖论剑2021

题目

from Crypto.Util.number import *
import gmpy2
from secret import flagp = getPrime(512)
q = getPrime(512)
n = p**4*qe = 65537
phi = gmpy2.lcm(p - 1, q - 1)
d = gmpy2.invert(e, phi)
dp = d % (p - 1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print ("dp = " + str(dp))
print ("c = " + str(c))y = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839g = 2
x = 2019*p**2 + 2020*p**3 + 2021*p**4
c1 = pow(g, x, y)
print( "c1 = " + str(c1))# dp = 379476973158146550831004952747643994439940435656483772269013081580532539640189020020958796514224150837680366977747272291881285391919167077726836326564473# c = 57248258945927387673579467348106118747034381190703777861409527336272914559699490353325906672956273559867941402281438670652710909532261303394045079629146156340801932254839021574139943933451924062888426726353230757284582863993227592703323133265180414382062132580526658205716218046366247653881764658891315592607194355733209493239611216193118424602510964102026998674323685134796018596817393268106583737153516632969041693280725297929277751136040546830230533898514659714717213371619853137272515967067008805521051613107141555788516894223654851277785393355178114230929014037436770678131148140398384394716456450269539065009396311996040422853740049508500540281488171285233445744799680022307180452210793913614131646875949698079917313572873073033804639877699884489290120302696697425# c1 = 78100131461872285613426244322737502147219485108799130975202429638042859488136933783498210914335741940761656137516033926418975363734194661031678516857040723532055448695928820624094400481464950181126638456234669814982411270985650209245687765595483738876975572521276963149542659187680075917322308512163904423297381635532771690434016589132876171283596320435623376283425228536157726781524870348614983116408815088257609788517986810622505961538812889953185684256469540369809863103948326444090715161351198229163190130903661874631020304481842715086104243998808382859633753938512915886223513449238733721777977175430329717970940440862059204518224126792822912141479260791232312544748301412636222498841676742208390622353022668320809201312724936862167350709823581870722831329406359010293121019764160016316259432749291142448874259446854582307626758650151607770478334719317941727680935243820313144829826081955539778570565232935463201135110049861204432285060029237229518297291679114165265808862862827211193711159152992427133176177796045981572758903474465179346029811563765283254777813433339892058322013228964103304946743888213068397672540863260883314665492088793554775674610994639537263588276076992907735153702002001005383321442974097626786699895993544581572457476437853778794888945238622869401634353220344790419326516836146140706852577748364903349138246106379954647002557091131475669295997196484548199507335421499556985949139162639560622973283109342746186994609598854386966520638338999059

本题使用公式
m = c d p m o d p m=c^{dp}\ mod\ p m=cdp mod p
推导过程
m < p m = c d m o d n m = c d + k 1 n m m o d p = c d m o d p m = c d p + k 2 ( p − 1 ) m o d p m = c d p m o d p mm<pm=cd mod nm=cd+k1​nm mod p=cd mod pm=cdp+k2​(p−1) mod pm=cdp mod p
脚本

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
import gmpy2
import libnum
import hashlibe = 65537
c1 = 78100131461872285613426244322737502147219485108799130975202429638042859488136933783498210914335741940761656137516033926418975363734194661031678516857040723532055448695928820624094400481464950181126638456234669814982411270985650209245687765595483738876975572521276963149542659187680075917322308512163904423297381635532771690434016589132876171283596320435623376283425228536157726781524870348614983116408815088257609788517986810622505961538812889953185684256469540369809863103948326444090715161351198229163190130903661874631020304481842715086104243998808382859633753938512915886223513449238733721777977175430329717970940440862059204518224126792822912141479260791232312544748301412636222498841676742208390622353022668320809201312724936862167350709823581870722831329406359010293121019764160016316259432749291142448874259446854582307626758650151607770478334719317941727680935243820313144829826081955539778570565232935463201135110049861204432285060029237229518297291679114165265808862862827211193711159152992427133176177796045981572758903474465179346029811563765283254777813433339892058322013228964103304946743888213068397672540863260883314665492088793554775674610994639537263588276076992907735153702002001005383321442974097626786699895993544581572457476437853778794888945238622869401634353220344790419326516836146140706852577748364903349138246106379954647002557091131475669295997196484548199507335421499556985949139162639560622973283109342746186994609598854386966520638338999059
c = 57248258945927387673579467348106118747034381190703777861409527336272914559699490353325906672956273559867941402281438670652710909532261303394045079629146156340801932254839021574139943933451924062888426726353230757284582863993227592703323133265180414382062132580526658205716218046366247653881764658891315592607194355733209493239611216193118424602510964102026998674323685134796018596817393268106583737153516632969041693280725297929277751136040546830230533898514659714717213371619853137272515967067008805521051613107141555788516894223654851277785393355178114230929014037436770678131148140398384394716456450269539065009396311996040422853740049508500540281488171285233445744799680022307180452210793913614131646875949698079917313572873073033804639877699884489290120302696697425
dp = 379476973158146550831004952747643994439940435656483772269013081580532539640189020020958796514224150837680366977747272291881285391919167077726836326564473
y = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839for x in range(1, e):if(e*dp%x==1):p=(e*dp-1)//x+1g = 2j = 2019*p**2 + 2020*p**3 + 2021*p**4t=pow(g, j, y)if(t!=c1):continuem=gmpy2.powmod(c, dp, p)print("m:",m)#print(hex(m)[2:])print(libnum.n2s(m))

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！