San Vu Ngoc - IRMAR

Cryptographie

Marie Stuart (1542 - 1587)

In [1]:
from IPython.display import HTML

HTML('<iframe width="560" height="315" src="https://www.youtube.com/embed/K9OKdtJ_xHg?rel=0&amp;&amp;showinfo=0" frameborder="0" allowfullscreen></iframe>')
Out[1]:

Le chiffre de Vigenère

https://fr.wikipedia.org/wiki/Chiffre_de_Vigen%C3%A8re

Enigma

Comment construire une machine à crypter ?

Museo della Scienza e della Tecnologia "Leonardo da Vinci" [CC BY-SA 4.0 ]

Alan Turing 1912-1954

Chiffrement RSA (1977)

https://fr.wikipedia.org/wiki/Chiffrement_RSA

On va avoir besoin de l'algorithme d'Euclide étendu (Bézout)

In [2]:
def Bezout (a,b):
    "cette fonction retourne (d,u,v) tel que au+bv=d"
    uu, vv   = 1, 0
    u, v = 0, 1
    rr, r = a, b  # invariants de boucle: a*u + b*v = r  et  a*uu = b*vv = rr
    while r != 0:
        q = rr / r # on divise l'ancien reste "r(n-1)" (rr) par le reste "r(n)" (r)
        print ("On a %d = %d*%d + %d," % (rr, q, r, rr % r ))
        r, rr = rr % r, r
        u, uu = uu - q*u, u # on calcule les nouveaux coefficients u,v
        v, vv = vv - q*v, v
        print ("  donc %d*(%d) + %d*(%d) = %d." % (a, u, b, v, r))
    return (rr,uu,vv)

Principe pour que Bob envoie un message à Alice:

1. Alice construit ses clefs

a) Elle choisit deux nombres premiers p et q, et calcule $n=pq$ et $\varphi(n)=(p-1)(q-1)$

In [3]:
p=11
In [4]:
q=23
In [5]:
n=p*q
n
Out[5]:
253
In [6]:
phi=(p-1)*(q-1)
phi
Out[6]:
220

b) Alice choisit un exposant $e$ premier avec $\varphi(n)$ et calcule son inverse modulo $\varphi(n)$.

In [7]:
Bezout(3,220)

On a 3 = 0*220 + 3,
  donc 3*(1) + 220*(0) = 3.
On a 220 = 73*3 + 1,
  donc 3*(-73) + 220*(2) = 1.
On a 3 = 3*1 + 0,
  donc 3*(221) + 220*(-6) = 0.
Out[7]:
(1, -73.33333333333333, 2.0)

Donc on a pgcd(3,220)=1 et $(-73)\times 3 + 1 \times 220 = 1$. Donc (-73) est un inverse de 3 modulo 220. D'autre part $-73\equiv 147$ modulo 220.

In [8]:
e=3
In [9]:
d=147

La clef publique est donc $(n,e)=(253,3)$ et la clef privée est $d=147$.

Alice peut diffuser sa clef publique à ses correspondants, ou même l'afficher sur sa page web ou son compte social. Alice doit aussi soigneusement détruire les traces de $p$, $q$ et $\varphi(n)$: autant limiter le nombre de secrets à garder; il suffit de garder $d$ secret.

2. Bob veut envoyer le message $m$

a) il vérifie que $m<n$ (sinon il faut le couper en plusieurs messages)

Par exemple $m=123<253$, OK

In [10]:
m=123

b) il utilise la clef publique d'Alice pour chiffrer m:

$x = m^e$ modulo $n$. On utilise ici la fonction dédiée pow(m,e,n)

In [11]:
x = pow(m,e,n)
x
Out[11]:
52
In [12]:
#vérifions
(m**e), (m**e) % n
Out[12]:
(1860867, 52)

On peut l'envoyer à Alice !

Alice reçoit x=52 et veut le déchiffrer

Elle a besoin de sa clef privée d=147. Elle doit calculer $x^d$ modulo 253

In [14]:
y = pow(x,d,n)
print ("Le message envoyé par Bob est:")
print (str(y))
print ('Trop bien ;)')

Le message envoyé par Bob est:
123
Trop bien ;)

(Alice trouve que Bob n'est pas très loquace. Il fera mieux la prochaine fois)