Sistema criptográfico de chave pública RSA¶
Sejam $p$ e $q$ dois primos ímpares distintos, "grandes". Seja ainda $n=p\cdot q$.
In [1]:
p = random_prime(2^1025, lbound=2^1024)
q = random_prime(2^1024, lbound=2^1023)
n = p*q
n
Out[1]:
29709687174446862743770736656101779571123161475543912205447690592561345248069208044639624284429944589604617362089205626416835866006502685229624110696542667007202050071451471910818775022062079587923460827307319777581845351811701804903402213206486446414230209830761208214449748383381512767949930591380935410069773413145087654261436554027054044679103524857183132268437635887012318902466867410114311314600783259177581219821040651580222116060529608723073063918481548572224634423087130861141951146737896280057841865927721194102109208053067208205213299589912643244207149319972536602314931063134303597912444848743817023371713
Calcula-se $m=\varphi(n)=(p-1)(q-1)$.
In [2]:
m = (p-1)*(q-1)
Consideramos ainda $e\in \mathbb{Z}_n^*$, ou seja, $e\in \mathbb{Z}_n$ tal que $mdc(e, n)=1$. Isto significa que $e$ é invertível $\mod m$. Seja, então, $d\in \mathbb{Z}_n$ tal que $ed\equiv 1 \mod m$.
In [3]:
e = randint(2, m-1)
while gcd(e, m) != 1:
e = randint(2, m-1)
d = power_mod(e, -1, m)
PubK = (n, e)
PrivK = d
O par $(n,e)$ é a chave pública, que é publicado abertamente. Já $d$ é a chave privada, que fica na posse unicamente de quem receberá a mensagem.
In [4]:
PubK
Out[4]:
(29709687174446862743770736656101779571123161475543912205447690592561345248069208044639624284429944589604617362089205626416835866006502685229624110696542667007202050071451471910818775022062079587923460827307319777581845351811701804903402213206486446414230209830761208214449748383381512767949930591380935410069773413145087654261436554027054044679103524857183132268437635887012318902466867410114311314600783259177581219821040651580222116060529608723073063918481548572224634423087130861141951146737896280057841865927721194102109208053067208205213299589912643244207149319972536602314931063134303597912444848743817023371713, 24249259772452917385911249909107364033487703617273167310721787091138065932033601651547541753521414453960691458311129152287343747621402821200008799664153297950955669230196526983321682106676524302660656491384963000059300159101634653638428100710380438304521241714617496257199766539953978922161961460369737520474952599434802881344961882494630155103717859439695367873433547936920192797857263107326610413024386830999654558412975857913084282796298289456774351059681000920732799303986111752560096778956569891250722361002335320451079417608279746126688998195601624559558335097401919670885152262227234449572440286135308394687335)
In [5]:
PrivK
Out[5]:
14627072026953360653013516231701248600419087888325371049575605275820782551690496135976859390917156554074411462163841372347598718329127136475970513034284325514503723672408275490862967351908317821181443559826355412843434455046409438388754692365351221345921063891543208834394703231389512119445744349682908474955816867332400494798853990363713993386729784403722752808321562303575119488555969603738015596037005712125554542933746116726146273979403266499062979862059440255582363209128783120875431969462472973360397007527687725963097155581780492493775014985752227679751306268501385072991383515632792264859560272866442262966023
Suponhamos agora que Alice pretende enviar a mensagem $mens=1234$ a Bob. Para tal, Alice consulta a chave pública $(n, e)$ de Bob para cifrar a mensagem.
In [6]:
mens = 1234
Alice, para cifrar $mens$, calcula $c=mens^e\mod n$, enviando $c$ a Bob.
In [7]:
c = power_mod(mens, e, n)
c
Out[7]:
2752921254095965462679143243089145401686836085773526190105077941163052980322174690392522226670567285717653435548332672811194898700461249064643890072743009201233728817943421899394664962632460767268718308647488225319034427211577589614137973940786436984166275949006162140406600662258620812024429964994123919857081128200541458256720919345176488840991030653125407865229035493850683439606501487819943147043856743490141766322938314723970275146364205046545317233260723690867972954803208592098122654764732170493259517037819425521666624084028322546274782083459877792562475562944451103364415541226388809549450505014149127087842
Bob recebe o criptograma $c$ de Alice. Para o decifrar usa a sua chave privada $d$ e calcula $c^d \mod n$.
In [8]:
power_mod(c, d, n)
Out[8]:
1234
In [9]:
power_mod(c, d, n) == mens
Out[9]:
True