一系列公式推导，费马小定理与CRT
学习出处：http://element-ui.cn/article/show-13917.aspx
p与q推理
1
2
3
| g, r1, r2 = [getRandomRange(1, N) for _ in range(3)]
g1 = pow(g, r1 * (p-1), N)
g2 = pow(g, r2 * (q-1), N)
|
由于费马小定理
如果p是一个质数 ，而整数a不是p的倍数，则有
推出
故
同理
gcd(-1,N)与gcd(,N)求出p,q
解密函数推理
1
2
3
4
5
6
| def encrypt(m):
s1, s2 = [getRandomRange(1, N) for _ in range(2)]
c1 = (m * pow(g1, s1, N)) % N
c2 = (m * pow(g2, s2, N)) % N
return (c1, c2)
|
加密函数如上所示
由于
同理
使用中国剩余定理即可求解m
解密函数如下
1
2
3
4
5
6
| def decrypt(c1, c2):
xp = c1 % p
xq = c2 % q
m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N
return m
|
解题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| from gmpy2 import *
from Crypto.Util.number import *
g1 = 9143176283300810019842153344177123108612540016879643936458724056602746667157014763960725115919119704406826965726023263657276550779443988565368344040505696950820899770544814163379169539926317676679421275092688200844094929042154854719312788471536324082041360841253720783220459009201882865091829118575721525038404689868986360373373122049951274015083845966946475469982961355934516388706446794517870569063777231434618411404965077775991870069073539415961610645268985004687402050059891500490949250730689691141954694508001895390336750734542724392709744200091587065816283592253967715080611459937165344139809223328071517060208
g2 = 14068322834597276347776814624877614869834816383564391664570268934537693322688875343215293618493363798985047779057952636529313879548457643220996398640913517182122425631198219387988691569709691279442005545716133131472147592456812502863851227108284027033557263611949365667779259585770738623603814004666845554284808166195201470503432803440754207350347128045893594280079379926676477680556845095378093693409219131090910168117334308781843178748431526974047817218228075136005979538773141427004682344298827618677773735288946271346252828348742296301538573408254015281232250841148556304927266143397565889649305095857756884049430
n = 18680643069610062851842282268594530254220611012409807422663284548187050713427682950720783343430650669361838067625768840896513125210105582070603021732086193955893838077699465426052925750736212977005683541174195320832791835197114668838654054444342903298662698415765898335350206380896849522280206304272801325820946987172164086644949521111058774180676742851681476123338557138770304164634321305204827406522957769478330124484710532963132900017800651579612646041955628867746525508376194147796920773364680264059390497210260540079810501777507814448518995581208169818764701641258963569599247156932381367802991222265241699715283
c1, c2 = (
3976514029543484086411168675941075541422870678409709261442618832911574665848843566949154289825219682094719766762966082440586568781997199077781276145091509192208487682443007457513002005089654365915817414921574344557570444253187757317116858499013550050579856269915915792827620535138057468531410166908365364129001407147467636145589396570815405571923148902993581000542566387654639930651683044853608873583911638108204074537952317056718986683846742909366072461130053275195290631718363272923316002049685111871888148244026652658482359335651889139243735138819453744763293112267738369048641158946411500606588429007794613880534,
18524535479582837341745231233387403662294605513261199630593257391163433751052467785080620993007681605662927226603747560698627838567782891522546977611597418150309028806158429831471152782211111046118637630899456903846057977815397285171313888516791822545633820066408276065732715348834255021260666966934592884548856831383262013360819013814149529393178712576141627031723067564594282618223686778534522328204603249125537258294561872667849498796757523663858312311082034700705599706428944071848443463999351872482644584735305157234751806369172212650596041534643187402820399145288902719434158798638116870325144146218568810928344
)
p = gcd(g1 - 1, n)
q = gcd(g2 - 1, n)
assert p * q == n
def decrypt(c1, c2):
xp = c1 % p
xq = c2 % q
m = (xp * inverse(q, p) * q + xq * inverse(p, q) * p) % n
return m
print(long_to_bytes(decrypt(c1, c2)))
|
