Cryptage à clé publique
• Non seulement pour le cryptage, mais aussi pour l’authentification et la signature électronique
• Fonctions à sens unique • Chaque utilisateur A possède 2 clés : une publique (KA+) et une privée (KA-)
• On peut trouver des clés sûres KA+ et KA- telles que : KA-(KA+(m)) = KA+(KA-(m)) = m – A!B : KB+(m) – B?A : m=KB-(KB+(m)) • Algorithme RSA (Rivest, Shamir, Adelman)
Algorithme RSA
• Pour recevoir un message crypté, B doit : – Choisir 2 entiers premiers p et q – Calculer n = pq – Choisir e < n premier avec (p-1) et (q-1) – Soit d tel que ed=1 mod (p-1)(q-1) (théorème de Bachet de Méziriac) – KB+ = (n,e), KB- = (n,d)
• Pour envoyer une suite de bits représentée par un nombre m < n, A envoie c = me mod n • Pour décrypter, B calcule m = cd mod n • En pratique n est représenté sur 1024 bits
La théorie
• Cryptage/décryptage calcule : (me mod n)d = (me)d mod n = med mod n
• Théorème (Euler) : x(p-1)(q-1) = 1 mod n
• med mod n = m(1+k(p-1)(q-1)) mod n = m.(m(p-1)(q-1))k mod n = m • La sécurité est fondée sur la non connaissance d’algorithme rapide de factorisation (non garantie)
Authentification
• Preuve en ligne de l’identité
• Il ne suffit pas de donner son identité en clair, car un intrus peut se faire passer pour un autre, y compris en cas d’envoi de mot de passe (qui peut être observé)
• Le cryptage du mot de passe n’est pas une solution (l’intrus peut rejouer le scénario) -> mots de passe à usage unique : notion de “nonce”
Exemple de protocole cryptographique
• A!B : je suis A
• B!A : nonce R
• A!B : KA-(R)
• B!A : demande KA+
• A!B : KA+ • B calcule KA+(KA-(R)) = R, authentifiant A
Attaque
• Intrus!B : je suis A
• B!Intrus : nonce R
• Intrus!B : KIntrus-(R)
• B!Intrus : demande KA+
• Intrus!B : KIntrus+
• B calcule KIntrus+(KIntrus-(R)) = R, authentifiant Intrus comme A !
Mais A pourrait se rendre compte de cette attaque
Attaque par interception
• A!B : je suis A
• Intrus!B : je suis A
• B!Intrus : nonce R
• Intrus!B : KIntrus-(R)
• B!Intrus : demande KA+
• Intrus!B : KIntrus+
• Intrus!A : R
• A!Intrus : KA-(R)
• Intrus!A : demande KA+
• A!Intrus : KA+
• B!Intrus : KIntrus+(X) /* donnée cryptée X */
• Intrus décrypte X = KIntrus-(KIntrus+(X))
• Intrus!A : KA+(X)
• A décrypte X = KA-(KA+(X))
A et B ne se rendent compte de rien …
Protocole Needham-Schroeder, 1978 S est un serveur de clés publiques
• A!S : B
• S!A : KS-(KB+,B)
• A!B : KB+(RA,A)
• B décrypte (RA,A) = KB-(KB+(RA,A))
• B!S : A
• S!B : KS-(KA+,A) • B!A : KA+(RA,RB)
• A décrypte (RA,RB) = KA-(KA+(RA,RB)) /* Retrouver RA authentifie B */
• A!B : KB+(RB) • B décrypte RB = KB-(KB+(RB)) /* Retrouver RB authentifie A */