Tutoriel de cryptographie Tutoriel de cryptographie

Simon Guillem-Lessard
Projet de fin d'étude 2001-2002
Département des mathématiques et de l'informatique
Université du Québec à Trois-Rivières


Table Des Matières
 Systèmes à clé publique

Le chiffrement à clé publique, aussi appelé le chiffrement asymétrique, implique une paire de clés : une clé publique et une clé privée. La clé publique est publiée dans des annuaires et ainsi connue de tous alors que la clé privée n'est connue que de la personne à qui la paire appartient.



Pour envoyer un texte chiffré à une personne, il faut utiliser la clé publique de cette personne et chiffrer le texte. Une fois reçu, le destinataire utilise sa clé privée correspondante pour retrouver le message clair.

Les systèmes à clé publique les plus utilisés sont RSA et PGP.

Contrairement au chiffrement à clé privée, le chiffrement asymétrique requiert beaucoup d'opérations et donc n'est pas recommandé pour de grande quantité d'informations.
Autre point négatif : il peut y avoir un problème d'authentification d'un destinataire. En effet, il n'y a aucune certitude à savoir qui est le véritable propriétaire d'une clé publique. Ainsi un faussaire peut tenter d'entraîner une personne à chiffrer un message avec sa clé publique, alors que cette personne croit que la clé publique appartient à une autre personne. Une société devra être mise en place pour assurer la vérification des clés publiques avec leur véritable propriétaire.

Pour en savoir plus
· HAC : Chapter 8 - Public-Key Encryption
http://cacr.math.uwaterloo.ca/hac/about/chap8.pdf
· NIST PKI Program
http://csrc.nist.gov/pki/
· RSA :
http://www.rsasecurity.com/rsalabs/pkcs/pkcs-1/
· PGP :
http://www.pgpi.org
http://www.pgp.com
· Liste de systèmes à clé publique
/appendices/publics.php
· Liens
/liens/

 Signatures numériques

Les signatures numériques (traduites parfois à tort "digitales") sont fondamentales au niveau de l'authentification, de l'identification d'entité, de l'autorisation et de la non-répudiation. Le but est de fournir des moyens à une entité de pouvoir lier son identité à une information.

Son fonctionnement général est l'inverse du système à clé publique et implique aussi la paire de clés publique/privée. Une personne voulant assurer le destinataire qu'il est bel et bien la bonne personne chiffrera un message avec sa clé privée et le destinataire déchiffrera le message chiffré avec la clé publique correspondante de l'expéditeur. Habituellement, une fonction de hachage est utilisée pour créer une empreinte du message et la transformation à l'aide de la clé privée est appliquée sur l'empreinte.

Fonctionnement

1. L'expéditeur calcule l'empreinte de son message à l'aide d'une fonction de hachage.
2. L'expéditeur chiffre l'empreinte avec sa clé privée.
3. L'expéditeur chiffre l'empreinte chiffrée avec le texte clair à l'aide de la clé publique du destinataire.
4. L'expéditeur envoie le message chiffré au destinataire.
5. Le destinataire déchiffre le message avec sa clé privée.
6. Le destinataire déchiffre l'empreinte avec la clé publique de l'expéditeur.
7. Le destinataire calcule l'empreinte du texte clair à l'aide de la même fonction de hachage que l'expéditeur.
8. Le destinataire compare les deux empreintes.

Les systèmes de chiffrement à clé publique peuvent habituellement aussi servir à générer des signatures numériques. Néanmoins, le standard américain est le DSS, lequel spécifie trois algorithmes : le DSA (Digital Signature Algorithm), RSA et ECDSA (Elliptic Curves Digital Signature Algorithm).

Les algorithmes de signatures numériques ne sont jamais utilisés pour le chiffrement de données.

Pour en savoir plus
· HAC : Chapter 11 - Digital Signatures
http://cacr.math.uwaterloo.ca/hac/about/chap11.pdf
· DSS - Digital Signature standard :
http://csrc.nist.gov/publications/fips/fips186-2/fips186-2.pdf
ANSI X9.30 The Digital Signature Algorithm (DSA).

 Factorisation

Les systèmes fonctionnant avec la difficulté de factorisation sont les plus populaires. En fait, ils sont fondés sur la difficulté de factoriser des grands nombres qui sont le produit de deux grands nombres premiers. Multiplier deux grands nombres premiers est une fonction à sens unique; il est facile de multiplier deux nombres pour obtenir un produit, mais difficile de factoriser ce produit et de retrouver les deux grands nombres premiers.

Exemple

Le RSA

Inventé en 1978 par Ronald L. Rivest, Adi Shamir et Leonard M. Adleman, le RSA est le plus populaire des systèmes à clé publique. Il peut être utilisé pour chiffrer des informations et/ou pour les signer (signature numérique).

Initialisation

1. Choisir deux nombres premiers, p et q, les deux étant plus grands que 10100.
2. Calculer n = p · q (n est le modulus)
3. Choisir e aléatoire tel que e et ((p - 1) · (q - 1)) n'aient aucun facteur commun excepté 1.
4. Trouver d tel que (e · d) soit divisible par ((p - 1) · (q - 1)),
donc : ed = 1 mod((p - 1)(q - 1))
.

Clé publique : (n,e).
Clé privée : (n,d) ou (p,q,d) si on désire garder p et q.

Chiffrement/Déchiffrement

1. L'expéditeur crée le texte chiffré c à partir du message m :
c = me mod(n), où (n,e) est la clé publique du destinataire.
2. Le destinataire reçoit c et effectue le déchiffrement :
m = cd mod(n), où (n,d) est la clé privée du destinataire.

Signature numérique

1. L'expéditeur crée la signature s à partir du message m :
s = md mod(n), où (n,d) est la clé privée de l'expéditeur.
2. Le destinataire reçoit s et m et effectue la vérification de m :
m = se mod(n), où (n,e) est la clé publique de l'expéditeur.

À titre de comparaison, le RSA est 1500 fois plus lent que le DES.

Pour en savoir plus
· RSA :
http://www.rsasecurity.com/rsalabs/pkcs/pkcs-1/
http://www.rsasecurity.com/rsalabs/faq/3-1.html
http://www.hack.gr/users/dij/crypto/overview/rsa.html
Démonstration du RSA en application Web :
http://www.chez.com/roaldd/RSA/CryptWithRSA.htm
· Nombres premiers :
http://www.utm.edu/research/primes/

 Logarithmes discrets

Les principaux systèmes basés sur le problème du calcul des logarithmes discrets sont le protocole de Diffie-Hellman, le chiffrement ElGamal et les systèmes à courbe elliptique (Elliptic curve cryptosystems).

Pour en savoir plus
· Diffie-Hellman
http://www.hack.gr/users/dij/crypto/overview/diffie.html
· Courbes elliptiques :
http://os390-mvs.hypermart.net/cryptoecc.htm
http://cheng.ececs.uc.edu/578/2-2.html

 Autres

Deux autres systèmes à clé publique peuvent être mentionnés : les systèmes Knapsacks (sac à dos, appelé aussi algorithme à empilement) et les systèmes Lattices.

À noter que les algorithmes knapsacks existent depuis le début de la cryptographie à clé publique (1978) et ont été démontrés non sûrs.

Pour en savoir plus
· The First General Public-Key Algorithm - the Knapsack Algorithm
http://www.chipcenter.com/eexpert/jleiseboer/jleiseboer011.html
· NTRUEncrypt Public Key Cryptosystem (Lattices)
http://www.ntru.com/technology/techpapers/review.htm



.Sources.
.Haut de page.


Algorithmes Importants

  Systèmes à clé privée

     Blowfish

     DES

     IDEA

     RC2, RC5, RC6

     RC4

     Rijndael

     SEAL

     TripleDES

  Systèmes à clé publique

     Diffie-Hellman

     DSA

     PGP

     RSA

  Fonctions de hachage

     MD2, MD4, MD5

     RIPEMD-128, RIPEMD-160

     SHA0, SHA1

     Tiger

  Protocoles Web

     SSL

     SHTTP