TD 2 : Usage de la cryptographie asymétrique

Lionel Morel (lionel.morel@insa-lyon.fr)

Ce TD présente et applique les notions de cryptographie asymétrique :

• Génération de clés RSA
• Distribution de clés
• Signature et chiffrement RSA

Le cryptosystème que nous allons utiliser ici est basé sur la fonction RSA. Le cryptosystème proposé est simple et présente donc certaines vulnérabilités mais illustre le fonctionnement.

Génération de clés RSA

Nous allons commencer par générer une paire de clés RSA pour chacun. Voici l’algorithme simplifié de génération de clés RSA (en réalité, d’autres tests doivent être réalisés) :

• Choisir deux nombres premiers p et q (exemples de premiers)
• Calculer n = p * q (Attention, pour que la suite du TD fonctionne, n doit être supérieur à 1000 !)
• Calculer φ(n) = (p-1)(q-1)
• Choisir e tel que :
  • 1 < e < φ(n)
  • pgcd(e, φ(n)) = 1
  • Par exemple, un premier qui ne divise pas φ(n)
• Déterminer l’inverse modulaire d ≡ e^-1 mod φ(n). Vous pouvez utiliser DCODE pour cela (attention, pas le pow Python pour ça, sauf si vous êtes certain d’avoir python 3.8 !)
• La clé publique est (e,n) et la clé privée est (d,n)

Gardez votre clé privée secrète et inscrivez votre clé publique sur la liste commune au groupe. Cette liste constitue la PKI du groupe. Elle va être recopiée au tableau pour que chaque puisse chiffrer des messages à destinations des différents participants.

Les exemples dans la suite du sujet sont réalisés avec p=31, q=37, n=1147, φ(n)=1080, e=7, d=463. La clé publique est (e,n), ici (7,1147), et la clé privée est (d,n), ici (463,1147).

Rappel : la propriété utilisée est que pour tout message m, m^de[n] = m.

Chiffrement et déchiffrement

Description

Nous allons chiffrer des chaînes de caractères. Pour cela, chaque lettre est remplacée par son rang dans l’alphabet, sur 2 chiffres :

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	_
01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27

Par exemple, “crypto” devient 03 18 25 16 20 15

Ensuite, afin de ne pas retomber dans un chiffrement par substitution simple, les chiffres sont assemblés par blocs de 3 (complété éventuellement de 0 à la fin), ainsi 03 18 25 16 20 15 devient 031 825 162 015.

Enfin, chaque bloc clair de 3 chiffres est chiffré indépendamment par la fonction RSA : bloc_chiffré = bloc_clair^e[n]. Attention, (e,n) représente une clé publique, mais celle de qui ? L’utilisation de la clé (7,1147) donne le chiffré 1116 751 245 1108.

Pour calculer les exponentiations modulaires, vous pouvez utiliser python (dans l’interpréteur, tapez pow(a,b,c) pour obtenir a^b[c]) ou DCODE. Attention, lors des calculs, n’écrivez pas de ‘0’ en début d’entier. Par exemple, pour le bloc clair 031, tapez pow(31,7,1147). Commencer un entier par ‘0’ le fait interpréter comme un nombre encodé en octal (même principe qu’un nombre commençant par ‘0x’ qui est interprété comme un hexadécimal).

Le déchiffrement est opéré de manière analogue, en utilisant la clé privée au lieu de la clé publique. Chaque bloc clair est réobtenu à partir du bloc chiffré par le calcul : bloc_clair = bloc_chiffré^d[n].

Mise en pratique

Vous allez maintenant transmettre un message chiffré à un autre étudiant. Chiffrez votre message sur un brouillon (ou sur votre ordinateur) et inscrivez le sur un bout de papier avec le nom du destinataire. Faites passer votre message de proche en proche, en direction du destinataire. Rappel : on voit bien dans ce cas que le chiffrement assure la confidentialité du message transmis.

1. Chiffrement de votre message : Chiffrez un message de votre choix avec le cryptosystème proposé.
2. Envoi de votre message : Écrivez le message chiffré ainsi que le nom de son destinataire sur un papier que vous faites circuler sans risque dans le groupe.
3. Réception d’un message : À la réception d’un message, appliquez l’algorithme de déchiffrement. Quelqu’un d’autre pouvait-il obtenir le clair de ce message ?

Signature et vérification

Description

Nous allons signer des chaînes de caractères. Pour cela, chaque lettre est remplacée par son rang dans l’alphabet. Pour un message m = (m₀, …, m_i) avec (m₀, …, m_i) les rangs de chaque lettre (attention, on ne fait plus des blocs de 3 chiffres ici), le haché h(m) est calculé par l’algorithme suivant :

h = 2;
for (j=0; j<i; j++) {
	h = h * 2;
	h = h + m[j];
}
return h%1000;

Quelques remarques: :

1. La valeur de la signature vaut alors h(m)^d[n].
2. Exemple : le haché de “crypto” vaut par exemple 831 et la signature par (463,1147) est 335.
3. Attention, (d,n) représente une clé privée, mais celle de qui ?
4. N’hésitez pas à implémenter cette fonction en python par exemple, pour faciliter la signature de vos messages.

Le message est alors envoyé accompagné de sa signature. La vérification d’un message reçu m signé avec sig est opérée de la manière suivante :

• Calculer h(m) par rapport au m reçu
• Calculer sig^e[n]
• Vérifier que h(m) == sig^e[n] sur le message reçu

Mise en pratique

Vous allez maintenant transmettre un message clair (non chiffré) signé à un autre étudiant, par message privé. La signature permet de vérifier l’intégrité du message transmis.

1. Signature de votre message : Signez un message de votre choix avec le cryptosystème proposé.
2. Envoi de votre message : Envoyez le message sur un bout de papier en direction du destinataire (attention, il faut bien envoyer le message en clair + la signature !)
3. Réception d’un message : À la réception d’un message, appliquez l’algorithme de vérification de la signature. Le message reçu est-il intègre ? Si non, quelle attaque avez-vous détectée ?

<!-- * Attaque de la clé privée (par factorisation de _n_ par exemple) -->

Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 2.0 France.