View
6
Download
0
Category
Preview:
Citation preview
1
Arithmétique et cryptographie RSA -
Serge Gautier, Groupement des Cartes Bancaires
2
Agenda
Rappels d’arithmétique
Calculs modulo n, cas où n = p et n = pq
Utilisation dans les métros automatiques
Besoins cryptographiques : chiffrement, signature, authentification
Comment le RSA répond à ces besoins
Les attaques et la sécurité des clés
3
Arithmétique
Les 4 opérations : + - × /
Division euclidienne : 17 = 3 × 5 + 2 17 mod 5 = 2
Opérations modulo n : + - × , avec la règle n = 0.
PGCD, Bezout
1/a mod n ?
4
La table de multiplication
Quels sont les nombres qui manquent ?
5
Calculs modulo p premier
• Intérêt : on a droit aux QUATRE opérations!
• p premier avec {1,…,p-1} 1/a mod p toujours défini (sauf 1/0)
1/5 mod 17 ?
mod 17 : 5x = 5y x = y
mod 10 : ????
6
Calculs modulo p premier
• mod p premier : a.b = 0 a = 0 ou b = 0
• Exemple : résoudre x² = 4 (mod 17)
• Résoudre x² = a² (mod p). Combien de solutions ?
• Fermat: a p-1 mod p = 1 pour a 0
7
Calculs modulo n = pq
• p et q premiers différents, n = pq (ex: RSA)
• Pour tout entier x, (x mod pq) mod p = x mod p
• x dans {0,…n-1} peut être représenté par (x mod p, x mod q)
• Représentation unique.
→ que représentent (0,0), (1,1), (2,2)… ?
8
Calculs modulo n = pq
• Il est équivalent de calculer mod pq et (mod p, mod q).
• Exemple : p = 5, q =11, n = 55.
- Décomposer 34 et 36 (mod p, mod q)
- Comparer 34x36 mod 55 et (34,34) x (36,36)
• Recombinaison : Théorème des Restes Chinois
• Résoudre x² = 4 (mod 55). Combien de solutions ?
9
Application – les Métros Automatiques
• Paris (L14, L1), New York, Barcelone, Lyon, Lille…
• Pilote = calculateur de bord → détection des pannes ?
10
Détection des pannes
• Le calculateur fait ses opérations nominales
→ exemple: Z := X + Y
• Une erreur transforme Z en Z + e
→ comment la détecter ?
11
Détection des pannes (suite)
Deux calculateurs travaillent en parallèle
Contrôle du résultat : correct si (Z – Z1) mod A1 = 0
Z devient Z+e, probabilité d’erreur non détectée ?
Chaque variable est composée de deux parties :
Valeur X Y Z := (X + Y)
Redondance X1 = X mod A1 Y1 = Y mod A1 Z1 := (X1 + Y1) mod A1
12
Détection efficace des pannes
Contraintes : taux de détection élevé, temps de détection rapide
Idée : mettre plusieurs calculateurs en parallèle
A1, A2, A3 premiers entre eux calculs mod A1.A2.A3
Valeur X Y Z := (X + Y)
Redondance 1 X1 = X mod A1 Y1 = Y mod A1 Z1 := (X1 + Y1) mod A1
Redondance 2 X2 = X mod A2 Y2 = Y mod A2 Z2 := (X2 + Y2) mod A2
Redondance 3 X3 = X mod A3 Y3 = Y mod A3 Z3 := (X3 + Y3) mod A3
13
Application – la cryptographie RSA
• Utilise des grands nombres (300 chiffres et plus)
• Système basé sur les calculs mod n = pq
14
Chiffrement classique (avant le RSA)
Modèle de base : Alice & Bob partagent une clé secrète K → Ils peuvent échanger secrètement un message m (dans les deux sens)
c = eK(m)
m = texte clair, c = texte chiffré (ou cryptogramme), K = clé secrète
Chiffrement affine: K = (a,b), eK(x) = (ax + b) mod n, dK(x) = (x - b)/a mod n
Chiffrement symétrique : Alice et Bob jouent le même rôle
m
K K
dK(c) = m
15
Comment rompre la symétrie?
Les clés symétriques sont inadaptées pour les opérations où Alice et Bob ne peuvent pas jouer le même rôle :
Signature : celui qui signe veut que personne ne puisse imiter sa signature, mais que tout le monde puisse la vérifier
signature de contrats, montants... : essor de la cryptographie commerciale
Authentification : Alice doit prouver à Bob qu’elle détient un secret, sans que Bob ne connaisse ce secret
Après avoir authentifié Alice, il ne doit pas pouvoir se faire passer pour elle
preuve de participation à une transaction
16
Une Solution Idéale
Alice possède deux fonctions (PA, SA) inverses l’une de l’autre
Pour tout message m, PA (SA (m)) = SA (PA (m)) = m
Elle en publie une (PA) et garde l’autre secrète/privée (SA).
La clé privée n’est jamais diffusée
la clé publique ne doit pas permettre de retrouver la clé privée
Bob fait de même avec un bi-clé (PB, SB)
Peuvent-ils communiquer de manière sécurisée ?
SA SB PA , PB
17
Chiffrement en clé asymétrique
Alice veut envoyer m chiffré à Bob
m c = PB (m) SB (c) =
SB (PB (m)) = m
Elle chiffre m avec la clé publique de Bob
Tout le monde peut chiffrer, mais seul Bob peut déchiffrer
SA SB PA , PB
18
Signature en clé asymétrique
Alice veut prouver à Bob qu’elle a signé un message m
PA (c)) = m ?
Alice signe m (ou une forme compressée) avec sa clé privée
La signature d’Alice est vérifiée par Bob
m, c = SA (m)
PA , PB SA SB
m, c
19
Authentification en clé asymétrique
Alice veut prouver à Bob qu’elle détient SA
Bob crée une donnée aléatoire r et demande à Alice de la signer
Alice signe la donnée r avec sa clé privée
La signature d’Alice est vérifiée par Bob
r
PA (c)) = r ? c = SA (r)
SA SB
c
r
PA , PB
20
Sécurité des systèmes asymétriques
Alice publie PA mais doit garder secrète la fonction inverse SA
Il faut prouver qu’il est difficile de trouver SA à partir de PA
L’attaquant voit les clés publiques, les cryptogrammes…
Preuves de sécurité mathématiques
Paramètres de sécurité : longueurs de clés…
RSA : un cryptosystème asymétrique
Permet le chiffrement, mais aussi la signature (et l’authentification)
21
Un premier essai : calculs mod n = p
On choisit un nombre premier p et un entier e premier avec (p - 1). On pose n = p.
La clé publique est (n,e). Fonction publique (chiffrement): P(x) = xe mod n
Soit d = 1/e mod (p - 1). Fonction privée (déchiffrement): S(x) = xd mod n
ed = 1 + k(p - 1). Fermat : pour x dans {0..n-1}, P(S(x)) = S(P(x)) = x
Sécurité : peut-on retrouver d à partir de (n,e) ?
22
L’algorithme RSA
On prend deux nombres premiers p et q. Le module n = pq est public.
On choisit un entier e premier avec (p - 1) et avec (q - 1).
On calcule d = 1/e mod (p - 1).(q - 1)
e = exposant public (souvent 3, 17, 216 + 1 = 65537). d = exposant secret
ed = 1 + k.(p - 1).(q - 1) (me mod n) et (md mod n) sont inverses.
Chiffrement ou vérification de signature : m → me mod n
Déchiffrement ou signature : m → md mod n
Sécurité : peut-on publier p et q ?
Sécurité : peut-on retrouver d à partir de la clé publique (n,e) ? → Meilleure technique connue : la factorisation de n
23
Sécurité du RSA
• Les attaquants possibles :
24
But des attaquants
Décrypter des messages chiffrés
Contrefaire des signatures
Se faire passer pour quelqu’un d’autre
Ils ont les clés publiques, des cryptogrammes et des couples clairs-chiffrés
Ils peuvent essayer de factoriser n mais parfois ce n’est pas nécessaire
25
Exemples d’attaques (niveau 1)
Alice chiffre son TEL avec une clé RSA (n = 100 chiffres, e = 3). Le TEL fait 10 chiffres. Retrouver TEL dans les trois cas suivants :
1. Alice chiffre directement TEL^3 mod n.
2. Alice chiffre ‘000…000TEL’ avec 50 zéros devant.
3. Alice chiffre ‘TEL000…000’, avec 50 zéros derrière.
Deux modules (n1,n2) utilisent un même nombre premier : n1 = p.q1 n2 = p.q2
Peut-on casser les clés correspondantes ?
.
26
Exemples d’attaques (niveau 2)
Deux exposants publics avec le même module
On chiffre un message m avec (n, e1 = 3) et (n, e2 = 17).
L’attaquant connaît : n, c1 = m^3 mod n, c2 = m^17 mod n
Trouver m (indice : théorème de Bezout)
Injection de fautes en mode TRC (restes chinois)
TRC : calcul en parallèle mod p et mod q (pour gagner du temps)
(x mod n) (x mod p, x mod q) = (xp, xq)
Erreur mod p : (x’p, xq) – (xp, xq) = (x’p – xp, 0) → multiple de q
PGCD(x’ – x, n) = q → factorisation de n
27
RSA et Factorisation
La factorisation du module n permet de casser la clé RSA
au fait, que signifie « casser une clé RSA » ?
Cette attaque peut toujours être tentée, car n est public
Algorithme de factorisation : NFS (Number Field Sieve)
But : trouver toutes les racines carrées d’un nombre modulo n
x² = a² mod n : 4 solutions, (± a , ± a) en décomposition (mod p, mod q)
r = (a, a) + (a, -a) = (2a,0) → multiple de q
PGCD (r, n) = q → factorisation de n.
Difficulté : dépend de la taille de n
28
Records de factorisation (officiels)
Record actuel : 232 chiffres (2010), ~ 5000 PC pendant 2 ans
Prochain record estimé : 270 chiffres (2014)
Records (et prévisions) en factorisation
0
60
120
180
240
300
360
1960 1970 1980 1990 2000 2010 2020 2030
Oblige à allonger les clés RSA avec le temps
29
En conclusion…
L’arithmétique est un outil universel
Mêmes calculs pour les petits ou grands entiers
Elle peut sauver des vies!
métros automatiques → sûreté de fonctionnement
Nombreuses applications high-tech
RSA : pas seulement pour les agents secrets!
Nécessaire pour : les satellites, Internet, les smartphones…
Attaques basées sur : Fermat, Bezout, PGCD, Restes Chinois…
Recommended