1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| def rsaParameters(p,q,e):
print 'one computes n=p*q=',p,'*',q,'=',p*q
n=p*q
print
print 'one computes φ(n)=(p-1)(q-1)=',p-1,'*',q-1,'=',(p-1)*(q-1)
print
print 'one checks that e (=',e,') is actually coprime with φ(n) since gcd(e,φ(n))=',gcd(e,(p-1)*(q-1)) ,'and one computes its inverse d= e^(-1) mod φ(n).'
print 'For this, one may use the extended Euclidean algorithm, or d=1/mod(e,φ(n))=',1/mod(e,(p-1)*(q-1))
d=1/mod(e,(p-1)*(q-1))
print
print 'Finally, the public key is Ke=(e,n)=(',e,',',p*q,'). The private key is Kd=(d,n)=(',d,',',n,').'
return d
d=rsaParameters(47,59,17)
> one computes n=p*q= 47 * 59 = 2773
one computes \u03c6(n)=(p-1)(q-1)= 46 * 58 = 2668
one checks that e (= 17 ) is actually coprime with \u03c6(n) since gcd(e,\u03c6(n))= 1 and one computes its inverse d= e^(-1) mod \u03c6(n).
For this, one may use the extended Euclidean algorithm, or d=1/mod(e,\u03c6(n))= 157
Finally, the public key is Ke=(e,n)=( 17 , 2773 ). The private key is Kd=(d,n)=( 157 , 2773 ).
def RSAencryption(m,e,n): #
print 'Encryption: one computes',m,'^',e,'mod', n,'=',mod(m^e, n)
encr=mod(m^e, n)
return encr
c=RSAencryption(66,17,2773)
> Encryption: one computes 66 ^ 17 mod 2773 = 872
# one computes c^d mod n and one checks that it is actually equal to the original message
RSAencryption(c,157,2773)
> Encryption: one computes 872 ^ 157 mod 2773 = 66
66
|
