In [1]:
from IPython.display import Image
Image("images/F2.png",width=300)
Out[1]:
In [2]:
Image("images/dieti.png",width=200)
Out[2]:

Department of Electrical Engineering and Information Technology

Via Claudio 21, 80125 Naples, Italy

RSA (Rivest–Shamir–Adleman) public key encryption: an example

In [51]:
Image("images/Asymmetric.png",width=600)
Out[51]:
In [18]:
from sympy import *

Bob choose two prime numbers $p$ and $q$, and calculate their product $N$

In [18]:
p = 11
q = 17

N = p*q

print('Is p prime number ? = ',isprime(p))
print('Is q prime number ? = ',isprime(p))

pm1qm1 = (p-1)*(q-1)
print('(p-1)(q-1) =',pm1qm1)
Is p prime number ? =  True
Is q prime number ? =  True
(p-1)(q-1) = 160

Bob picks up a number $c$ to have no factor in common with $(p-1)(q-1)$

Bob finds $d$, i.e. the multiplicative inverse of $c$ in mod $(p-1)(q-1)$

In [41]:
c = 7

print('Has',c,'factors in common with', (p-1)*(q-1),' ? ',pm1qm1 % c == 0)

d = mod_inverse(c, pm1qm1)

print(c,'x',d,'= 1 ( mod',pm1qm1,')')
Has 7 factors in common with 160  ?  False
7 x 23 = 1 ( mod 160 )

Bob gives Alice the number $N$ through a public channel

Alice encodes its message $a$

$$ b = a^c \quad \left(\text{mod} \, N\right) $$
In [48]:
b = pow(a,c) % N

print(b)
130

Alice gives Bob the encrypted message, i.e. $b$

Bob decodes the message $b$, using the number $d$

$$ a = b^d \quad \left(\text{mod} \, N\right) $$
In [49]:
aa = pow(b,d) % N

print(a)
3

Bibliography

Rivest, Shamir, Adleman "Cryptographic communications system and method" Patent US4405829A

Manfred Schroeder "Number Theory in Science and Communication" (1984)

N. David Mermin "Quantum Computer Science (An Introduction)" (2007)

In [ ]: