All published worksheets from http://sagenb.org

Project: sagenb.org published worksheets

Path: pub / 1401-1501 / 1448-Chiffrement RSA.sagews

Views: ¹⁶⁸⁷³⁷
Image: ubuntu2004

Chiffrement RSA

I - Contexte cryptographique

Avant de parler de la méthode de chiffrement proprement dite, rappelons quelques principes.

Le but d'un système cryptographique est d'assurer la confidientialité sous des hypothèses bien précises. En effet, on cherche a avoir des garanties. Par exemple, on veux pourvoir concevoir un système qui soit sûr même lorsqu'il est connu de l'adversaire. Toute la sécurité est contenue dans la clé, et non dans l'algorithme permettant ainsi par exemple de partager un même algorithme pour tout un pays, avec des clés différentes pour chaque personnes. Si une clé est découverte, seule les messages de cette personne sont compromis, et les autres personnes peuvent continuer d'utiliser leurs clés en toute sécurité. (voir principes de Kerchoff http://fr.wikipedia.org/wiki/Principe_de_Kerckhoffs).

Il existe deux grands types de systèmes de chiffrement. Tout d'abord les plus ancens: les systèmes dits symétriques, ou à clé secrète. Les deux personnes voulant échanger un message (il est traditionnel de les appeler Alice et Bob dans le domaine de la cryptologie) partagent la même clé. On peut donc penser à un système classique avec un cadenas et deux clés identiques. Plus récemment, un autre type de chiffrement offrant des possibilités nouvelles est apparu: le chiffrement asymétrique, ou à clé publique. Dans ce cas, chaque personne possède deux clés: une publique utilisée par les personnes voulant lui envoyer un message (pour "fermer" le cadenas) et une privée connue d'elle seule pour les déchiffrer (pour "ouvrir" le message). On peut donc publier sa clé publique sur une page web par exemple, et des personnes que l'on ne connaît pas et avec qui il n'a pas été possible d'échanger des clés peuvent nous envoyer un message de manière sécurisée.

Le système RSA est le plus connu et certainement le plus utilisé des systèmes à clé publique (il est par exemple utilisé dans les cartes bancaires, ou encore sur de nombreux sites internet). Nous allons voir brièvement comment il fonctionne.

II - Préliminaires: le codage

Le domaine de la cryptographie est un domaine très mathématique et on préfère considérer des messages constitués de chiffres, et non de lettres.

Pour cela, il suffit de choisir un alphabet et de numéroter les lettres. En informatique, on a l'habitude de numéroter à partir de 0:

a	b	c	d	e	f	g	h	i	j
0	1	2	3	4	5	6	7	8	9

Cette étape est appelée le codage. Passer des chiffres aux lettres est le décodage. Ici rien n'est secret, tout le monde sait que $5$ signifie $f$ dans notre exemple.

III - Le chiffrement proprement dit

Nous allons ici voir les opérations nécéssaires au chiffrement sans s'occuper des justifications mathématiques assurant la sécurité. Pour cela il va falloir parler d'arithmétique modulaire. C'est en fait très simple: il suffit d'imaginer que les nombres entiers sont "enroulés" sur un cercle de taille donnée (penser aux fonctions trigonométriques). On fait donc les opérations habituelles (+,-,*) et ensuite le résultat est "réduit" pour revenir à l'équivalent d'une "mesure principale".

Par exemple modulo 17 nous avons:

6*7 % 17

8

Ici le signe % siginifie "modulo"; cela veut donc dire que $6*7 = 8 \pmod{17}$ en effet, $6*7 = 42$ et $42 = 8+17+17$ . On enlève $17$ jusqu'à obtenir un nombre $0\leq x < 17$ ; ou encore, compter jusqu'à 42 sur ce cercle, vous arrivez sur le $8$ .

graphs.CycleGraph(17).plot()

Il nous faut maintenant définir les clés.

Pour la clé publique, choisissons deux nombres premiers (généralement de même taille environ) traditionnellement notés $p$ et $q

La première partie de la clé publique est alors le produit de ces nombres: $N = p q$

Par exemple:

p = 17
q = 19

Nous allons donc faire nos opérations modulo 323 (sur un cercle de taille 323).

La deuxième partie de la clé nécessite de décomposer en produits de facteurs premiers le nombre $\Phi = (p-1)(q-1)$ . On remarquera que pour calculer ce nombre il faut connaître $p$ et $q$ . Si l'on connaît seulement le produit $N$ , cela ne suffit pas. C'est en fait ici que réside toute la sécurité de ce système, nous y reviendrons.

(remarque: $\Phi$ s'appelle indicateur d'Euler, on pourra éventuellement se renseigner sur sa signification...)

Ici:

phi = (p-1)*(q-1)
print phi,"=",factor(phi)

288 = 2^5 * 3^2

On choisi alors un nombre $e$ qui n'a aucun facteur commun avec $\Phi$ ce qui revient à dire que $pgcd(e,\Phi)=1$ (on dit qu'il est premier avec $\Phi$ ). C'est le deuxième partie de notre clé publique.

Par exemple ici:

e = 35

Notre clé publique est le couple: $(N,e) = (323, 35)$ .

Comment utilise-t-on cela pour chiffrer?

À partir d'un message $m$ (c'est-à-dire un nombre entre $0$ et $322$ puisque la phase de codage a déjà eu lieu) nous calculerons le message chiffré $c$ ainsi:

$c = m^e \pmod N$

m = 97
c = m^e % N
c

181

Pour déchiffrer, nous avons besoin de l'inverse modulaire de l'exposant secret $e$ modulo $\Phi$ .

Un théorème que l'on peut démontrer en suivant l'algorithme d'Euclide du calcul de $pgcd$ assure l'existence de nombres $u$ et $d$ tels que:

$ed+ u\Phi = pgcd(e,\Phi)$ c'est-à-dire ici à cause du choix particulier de $e$

$ed+ u\Phi = 1$ . En faisant le calcul modulo $\Phi$ (donc $\Phi = 0$ ; on fait un tour complet avec $\Phi$ ) on obtient

$ed = 1 \pmod \Phi$ .

C'est pour cela que l'on appelle $d$ l'inverse de $e$ modulo $\Phi$ .

Sur notre exemple:

d = 107
e*d % phi

1

Pour déchiffrer on calcule alors:

$c^d = m \pmod N$

c ^ d % N

97

Le théorème qui assure que l'on retrouve bien le message initial est basé sur le "petit théorème de Fermat" (par curiosité, on pourra regarder quel est le grand théorème de Fermat qui n'a rien à voir ici...). Nous ne détaillerons pas plus ici.

Exercice:

Déchiffrer le message suivant codé avec l'alphabet

a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	z	.	,	;	?	!	<espace>	'
0	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

et chiffré avec la clé publique $(33,7)$ et l'exposant secret $3$ :

$1, 8, 0, 21, 20, 24$

IV - Programmation

Voici un exemple de programmation des différentes étapes (le langage utilisé s'appelle Python).

On commence par le codage:

alphabet = "abcdefghijklmnopqrstuvwxyz.,;?! '"

def codage( lettre ):
    return alphabet.index(lettre) #retourne la position de la lettre dans l'alphabet

#un exemple
codage( 'g' )

6

Ensuite le chiffrement à proprement parler. Ici nous avons besoin de la clé publique.

def chiffrement_nombre( m , cle_publique):
    N,e = cle_publique
    return m^e % N

#un exemple
chiffrement_nombre( m = 6, cle_publique = (33,7) )

30

Troisièmement le déchiffrement, qui utilise en plus l'exposant secret.

def dechiffrement_nombre( c , cle_publique, exposant_secret ):
    N,e = cle_publique
    d = exposant_secret
    return c^d % N

#un exemple
dechiffrement_nombre( c = 30, cle_publique = (33,7), exposant_secret = 3 )

6

Et enfin le décodage.

def decodage( nombre ):
    n = nombre
    return alphabet[n] # la lettre numéro n dans notre alphabet

#un exemple
decodage(6)

'g'

On peut ensuite regrouper les étapes de codage et de chiffrement et les appliquer à plusieurs lettres de suite.

def chiffrement( message , cle_publique ):
    chiffre = [] # pour l'instant rien
    for lettre in message:
        m = codage(lettre)
        c = chiffrement_nombre( m, cle_publique)
        chiffre.append(c) # on ajoute une lettre chiffrée
    return chiffre

#un exemple
chiffrement( "vive le rsa", (33,7) )

[21, 2, 21, 16, 4, 11, 16, 4, 8, 6, 0]

Et de même pour le déchiffrement.

def dechiffrement( chiffre, cle_publique, exposant_secret):
    message = "" # pour l'instant rien
    for c in chiffre:
        m = dechiffrement_nombre(c, cle_publique, exposant_secret)
        lettre = decodage(m)
        message = message + lettre # on ajoute une lettre au message déchiffré
    return message

#un exemple
dechiffrement([21, 2, 21, 16, 4, 11, 16, 4, 8, 6, 0], cle_publique = (33,7), exposant_secret = 3)

'vive le rsa'

V - Sur la sécurité

La sécurité de cet algorithme repose sur la difficulté de la factorisation: connaissant N, il est difficile de retrouver p et q.

Il faut bien se rendre compte en pratique que l'on prend des nombres très grands, voici des exemples typique de valeurs pouvant être utilisées actuellement:

p = random_prime(2^512)
q = random_prime(2^512)
N = p*q
print "p = ", p
print "q = ", q
print "N = ", N

p =  9706322961292074408608923270033998360106246085325736214838826860539507031035602372300335897870961594454713079649680894074224126480113945264250207524416657
q =  10805356660479526284697338628393010535961587220427234235642294281144867441068237616000288540050227197786813328440621282482603776580550448522075594081068191
N =  104880281458562675403978848611669576656330552746145084488690724948782666519138440420822813600313290778099873737145480573652477358433669405679998300247837145719064790260895969365848626229676168061696153832078642133092638707576952627290836756652595888640721611692476414865888051704842234391213002148304713257487

Pour "mesurer" la taille d'un nombre, on peut parler de son nombre de chiffres. Ici $N$ est un nombre de $308$ chiffres décimaux c'est la taille minimale conseillée actuellement pour assurer un secret durant les 5 prochaines années. Le record de factorisation d'un nombre de type RSA ( c'est-à-dire produit de deux nombres premiers de taille proche) est actuellement de $232$ chiffres décimaux et a été établi très récemment (le 29 décembre 2009, cf. http://fr.wikipedia.org/wiki/RSA-768 ).

Il faut faire attention cependant, l'assurance mathématique de sécurité doit être prise avec précaution. En effet, comme tout théorème, elle repose sur des hypothèses précises. En sortant de ce cadre, on peut trouver des failles au système. Par exemple, si l'on programme cet algorithme sans précautions particulières, on peut retrouver la clé de chiffrement en mesurant le temps mis pour chiffrer (par exemple le temps que met le site internet de la banque pour répondre), c'était encore le cas il y a seulement quelques années. On parle alors d'attaques par "canaux cachés" c'est-à-dire ici en utilisant des mesures non spécifiées par l'algorithme mathématique (les principaux "canaux cachés" utilisés sont le temps, la consommation électrique, la température de la puce, et le champ magnétique émis).

Enfin, la physique moderne, et en particulier la mécanique quantique prévoit la possibilité de construire des ordinateurs fonctionnant sur de nouveaux principes (appelés ordinateurs quantiques) qui rendraient cette factorisation très facile. Bien que pour l'instant les difficultés techniques soit encore trop importantes pour être totalement surmontées (le calcul le plus difficile réalisé sur un ordinateur quantique à l'heure actuelle a été la factorisation du nombre $15$ ), la recherche de nouveaux algorithmes premettant l'échange de données de manière sécurisée même si l'adversaire dispose d'ordinateurs quantiques est un domaine de recherche très actif.

VI - Quelques remarques

Premièrement, l'algorithme présenté ici n'est en fait que le coeur du système utilisé en pratique et présente quelques inconvénients, par exemple comme $0$ et $1$ sont invariants quand on les élève à n'importe quelle puissance, ils ne sont jamais chiffrés dans l'algorithme présenté. Sur notre exemple cela signifie que les $a$ et $b$ du message initial donneront toujours des $0$ et $1$ dans le message chiffré.

Deuxièmement, comme on utilise des grands nombres, il nous faut un très grand alphabet. On chiffre en fait non pas des lettres, mais des phrases entières. Pour cela, chaque lettre correspond à un chiffre, et la phrase entière à un nombre. Par exemple avec notre petit alphabet de l'exemple, le mot 'message' correspondra au nombre constitué des chiffres: $12-4-18-18-0-6-4$ ce qui donne en base $33$

12*33^6 + 4*33^5 + 18*33^4 + 18*33^3 + 0*33^2 + 6*33^1 + 4*33^0

15676150846

(on pourra éventuellement se renseigner sur l'écriture d'un nombre en base autre que 10)