View
221
Download
0
Category
Preview:
Citation preview
1/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception et sécurisation d'unités arithmétiqueshautes performances pour courbes elliptiques
Soutenance de thèse de Doctorat d'Informatique
Julien Francq
decembre
2/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Introduction
Cryptographie
La cryptographie est l'étude des techniques pouvant permettrede sécuriser des opérations en présence de personnespotentiellement malveillantes (attaquants) :
Chi�rementSignature numériqueAuthenti�cationVéri�cation d'intégritéAutres (Internet)
3/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Introduction
Contexte de la thèse
Projet : Briques Technologiques pour le Renforcement de laSécurité (BTRS)
Partenaires :
CEA-LETIGemaltoSmart Packaging Solutions (SPS)
Thèse e�ectuée conjointement au :Centre de Microélectronique de Provence-Georges Charpak(CMP-GC)
Équipe SAS (Systèmes et Architectures Sécurisées)
Laboratoire d'Informatique de Robotique et deMicroélectronique de Montpellier (LIRMM)
Équipe ARITH
Financement : Fonds Social Européen (FSE)
4/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Introduction
Cryptographie et courbes elliptiques
Cryptographie symétrique
Même clé pour le chi�rement et le déchi�rementPerformante mais nécessite un échange de clé avant utilisation
Cryptographie asymétrique
Paire clé privée / clé publiquePas besoin de partager un secret avant utilisation
Historique :
Di�e et Hellman, 1976Rivest, Shamir et Adleman (RSA), 1977Koblitz et Miller, 1985
Cryptographie sur courbes elliptiques (Elliptic Curve
Cryptography, ECC)ECC-160 ' RSA-1024
=⇒ ECC alternative crédible au RSA (standards NIST etCerticom)
5/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Introduction
Du point de vue du concepteur de circuits cryptographiques
Un opérateur (ou unité) arithmétique pour l'ECC doit être :performant
temps d'exécution court, débit important, petite surface,consommation électrique faible, etc.
sécuriséface à d'éventuelles attaques théoriques et physiques (parobservation, par perturbation)implantation de parades (contre-mesures)......pouvant diminuer les performances
=⇒ Trouver le meilleur compromis performances/sécurité
6/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Introduction
Travaux réalisés
Nouvelle architecture d'unité arithmétique pour l'ECC sur Fp
Performances meilleures que la plupart de celles de lalittérature
Protection de cette unité contre les attaques par observation àl'aide de l'état de l'art
Solution la plus performante de la littérature
Protection de cette unité contre les attaques parperturbation...
...à l'aide du principe de la préservation de la parité
6/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Introduction
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
6/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
6/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Courbes elliptiques
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
7/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Courbes elliptiques
Introduction générale
Une courbe elliptique E sur Fp est l'ensemble des points (x , y)obéissant à l'équation simpli�ée de Weierstrass :
E : y2 = x3 + ax + b ∪ {∞}E (Fp) : groupe additif
Élément neutre : ∞ (point à l'in�ni)Opération de groupe : addition de points (+)
loi � corde et tangente �
8/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Courbes elliptiques
Formules de doublement et d'addition de points
P1(x1, y1) + P2(x2, y2) donne le point P3(x3, y3), où :{x3 = λ2 − x1 − x2y3 = (x1 − x3)λ− y1
, avec
λ =
y2 − y1
x2 − x1, si x1 6= x2 [Addition, A]
3x21
+ a
2y1, si x1 = x2 [Doublement, D]
Formulation de λ di�érente pour l'addition et le doublement
L'addition et le doublement entraînent donc le calculd'additions, de soustractions, de multiplications, de carrés etd'inversions sur Fp
9/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Courbes elliptiques
Multiplication scalaire et ECDLP
La sécurité de l'ECC repose notamment sur un sous-groupecyclique de E (Fp) noté G généré par le point de base P etd'ordre n grand :
G = 〈P〉 = {∞,P, [2]P, · · · , [n−1]P} ⊆ E (Fp), avec [n]P =∞
Multiplication scalaire de P par un grand entier k (la clé) :
Q = [k]P = P + P + · · ·+ P︸ ︷︷ ︸k fois
Opération importante dans les protocoles ECCOpération � à sens unique � : connaissant k et P ∈ G, facilede calculer Q = [k]P ∈ G, mais connaissant P et [k]P, di�cilede retrouver k
→ Problème du logarithme discret sur courbes elliptiques (EllipticCurve Discrete Logarithm Problem, ECDLP)
10/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Courbes elliptiques
Multiplication scalaire avec l'algorithme� doublement-et-addition �
Entrées : P ∈ E , k =∑i=0
ki2i = (k`−1 · · · k0)2.
Sortie : Q = [k]P .
1. Q ←∞2. pour i = `− 1 à 03. Q ← [2]Q [Doublement]4. si ki = 15. Q ← Q + P [Addition]6. �n si
7. �n pour
8. retourner Q
Nombre moyen de bits non-nuls dans k : `/2=⇒ Nombre d'opérations de points : `D + (`/2)A
11/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Courbes elliptiques
Exemples d'optimisations classiques
Recodage de k sous une forme non-adjacente (NAF)
NAFw (k) =∑i=0
ki2i , avec |ki | < 2w−1
Exemple : k = 763
k2 = ( 1 0 1 1 1 1 1 0 1 1)NAF2(k) = (1 0 1 0 0 0 0 0 1 0 1)
Nombre moyen de bits non-nuls dans NAFw (k) : `/(w + 1)=⇒ Nombre d'opérations de points : (`− 1)D + (`/(w + 1))A
Autres voies d'amélioration : chaînes d'additions spéciales,courbes particulières (Montgomery, Edwards), etc.
11/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Arithmétique des ordinateurs
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
12/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Arithmétique des ordinateurs
Addition classique
Cellule d'addition complète (Full-Adder, FA) :
FA
b c
s
a
r{s = a ⊕ b ⊕ c
r = ab + ac + bc
Additionneur à propagation séquentielle de la retenue
1 1 0 0
05 4 3 2 1
012345s6 s s s s s s
rrrrrr
5 5 4 4 3 3 2 2ba
FA
ba
FA
ba
FA
ba
FA
ba
FA
ba
FA
Si opérandes sur n bits
=⇒ Temps de calcul pire cas = n × T(FA)
13/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Arithmétique des ordinateurs
Addition en représentation redondante
Représentation redondante à retenues conservées : Carry-Save(CS), Borrow-Save (BS)
BS : X = (xn−1 · · · x1x0)BS =n−1∑i=0
xi2i =
n−1∑i=0
(x+i − x−i )2i
b2 a1 b1 a0 b0a b b b ba a
0
0
a3 b3 a2 a3 2 2 1 1 0 0
s4 s3 s2 s1 s0s s s s s4 3 2 1 0
3
PPM PPM
PPM PPM PPM PPM
PPMPPM
+ + − − − − − − − −+ + + + + +
+ + + + +− − − − −
4 3 3 2 2 1 1 0
3 3 2 2 2 1 1 1 0 0 0
01122334
3
=⇒ Temps de calcul de l'addition BS (BSA) indépendant de n(T(BSA(n)) = 2× T(PPM) ≈ 2× T(FA))
Mais comparaison et signe di�ciles, coût mémoire 2× grand
14/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Arithmétique des ordinateurs
Calculs sur Fp
L'ECC a besoin de trois opérations modulaires :Addition
Méthode classiqueMéthode d'OmuraMéthode de Takagi
MultiplicationMultiplication puis réductionMultiplication et réduction croisées (Montgomery)
InversionPetit théorème de FermatPGCDMontgomery
14/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Attaques physiques
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
15/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Attaques physiques
Attaques par observationMesurer des paramètres externes (canaux cachés :consommation électrique, rayonnement électromagnétique(EM), temps de calcul, etc.) pour récupérer des informationsinternesMesures globales (consommation électrique) / locales (EM)Attaques simples / di�érentielles
16/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Attaques physiques
Attaques par perturbationModi�er l'environnement du cryptosystème de telle sorte queson fonctionnement soit altéré et qu'il apparaisse des fautes
Pics de courant sur :l'alimentationl'horloge
Variations :de la températureou du champ EM environnant
Injection de particules :rayons Xions lourdsphotons (laser)
17/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Attaques physiques
Perturbations : modèles et conséquences sur l'ECC
Degré d'invasivité
Degré de destructivité (Fautes permanentes / transitoires)
Modèles de perturbation :
Localisation temporelle/spatialeNombre de bits fautésModèle de faute injectée : collage, inversion, etc.
Pour l'ECC :
Forcer le calcul de la multiplication scalaire sur une autrecourbe où l'ECDLP est plus facile à calculerObtenir un point résultat faux mais appartenant à la courbeinitialeAttaques initialement mises en évidence sur le RSA
17/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Contre-mesures
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
18/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Contre-mesures
Contre-mesures vis-à-vis des attaques par observationsimples
Un cryptosystème ECC est vulnérable vis-à-vis des attaquespar observation simples si :
les formules utilisées pour l'addition et le doublement sontdi�érentesl'exécution de la multiplication scalaire dépend de la clé
D'où 2 contre-mesures possibles :
Rendre le doublement et l'addition de points indistinguables(formules uni�ées d'addition de points, atomicité)Utiliser un algorithme de multiplication scalaire régulier(� Doublement-et-toujours-addition �, échelle de Montgomery,chaînes d'additions, atomicité, recodage de k,� doublement-addition �, � addition-seulement �)
19/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Contexte
Contre-mesures
Détecter une perturbation
Véri�er que le résultat est bien sur E
(y2 − x3 − ax)?= b (mod p)
Attaques conservant la courbe initiale
= Attaques di�érentielles=⇒ Changer la représentation de k à chaque exécution de la
multiplication scalaireQ = [k∗]P = [k + rn]P (avec [n]P =∞)Q = [k]P = [k − r ]P + [r ]P
[Blömer, 2006] : e�ectuer [k]P modulo p0 (<p) et modulop0p, puis véri�er que les deux points résultats sont égauxmodulo p0
La politique adoptée en cas de détection ne doit pas donnerd'information à l'attaquant
19/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
19/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Paramètres d'implantation
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
20/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Paramètres d'implantation
Modulo choisi
Version initiale de la multiplication modulaire de Montgomerycontient une soustraction conditionnelle
Vulnérable face à des attaques par observation
=⇒ Algorithme de Montgomery sans soustraction conditionnelleEntrées : p = (pn−1 · · · p1p0)2, pgcd(p, 2) = 1,A = (anan−1 · · · a1a0)2 < 2p, B = (bnbn−1 · · · b1b0)2 < 2p.
Sortie : S = MMM(A,B, 2p) = A.B.2−(n+2) (mod 2p).
1. S ← 02. pour i = 0 à n + 13. mi ← s0 ⊕ ai .b04. S ← (S + ai .B + mi .p)/25. �n pour
6. retourner S
=⇒ Modulo 2p
21/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Paramètres d'implantation
Choix de la représentation des nombres utilisée
Multiplication modulaire de Montgomery conduit au calculd'additions/décalages
Inversion modulaire conduit au calcul de multiplications et/oud'additions
Besoin d'une addition rapide
=⇒ Représentation redondante pour une addition rapide (CS ouBS)
Or, CS très utilisée dans la littérature et BS peu (voir pas dutout)
=⇒ Explorer les possibilités o�ertes par BS
22/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Paramètres d'implantation
Opérations que l'unité arithmétique doit pouvoir e�ectuer
Opérations pour les calculs en coordonnées a�nes
Addition modulaire : A + B (mod 2p), avec A 6= B
Soustraction modulaire : A− B (mod 2p)Multiplication modulaire : A× B (mod 2p), avec A 6= B
Carré modulaire : A2 (mod 2p)Inversion modulaire : 1/X (mod 2p)
Opérations pour les calculs en coordonnées projectives
Multiplication modulaire par 2 : 2× A (mod 2p)Multiplication modulaire par −3 : −3× A (mod 2p)
Opérations pour les calculs de formules uni�ées d'additions
Cube modulaire : A3 (mod 2p)
22/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Arithmétique utilisée
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
23/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Arithmétique utilisée
Addition modulaire en BS
Méthode de Takagi modulo 2p
Entrées : 2n ≤ 2p < 2n+1, −2p < A = (an+1an · · · a0)BS < 2p,−2p < B = (bn+1bn · · · b0)BS < 2p.Sortie : S = A + B (mod 2p), avec S = (sn+1sn · · · s0)BS .1. (T+,T−)← BSA[(A+,A−), (B+,B−)]
2. si tv = 4tn+2 + 2tn+1 + tn < 0
3. (S+, S−)← BSA[(T+,T−), (2p, 0)]
4. sinon si tv > 0
5. (S+, S−)← BSA[(T+,T−), (0, 2p)]
6. sinon si tv = 0
7. (S+, S−)← BSA[(T+,T−), (0, 0)]
8. �n si
9. retourner S
24/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Arithmétique utilisée
Multiplication de Montgomery en BSEntrées : p = (pn−1 · · · p1p0)2, pgcd(p, 2) = 1,−2p < A = (an+1an · · · a0)BS < 2p,−2p < B = (bn+1bn · · · b0)BS < 2p.Sortie : (S+, S−) = (A+,A−).(B+,B−).2−(n+2) (mod 2p).
1. (U+,U−)← BSA[(B+,B−), (p, 0)]2. (V+,V−)← BSA[(B−,B+), (p, 0)]3. (S+, S−)← BSA[(0, 0), (0, 0)]4. pour i = 0 à n + 15. mi ← (a+
i ⊕ a−i ).(b+0⊕ b−
0)
6. si (a+i , a
−i ,mi ) = (0, 0, 0) ou (1, 1, 0)
7. (S+, S−)← BSA[(S+, S−), (0, 0)]8. sinon si (a+
i , a−i ,mi ) = (1, 0, 0)
9. (S+, S−)← BSA[(S+, S−), (B+,B−)]10. sinon si (a+
i , a−i ,mi ) = (0, 1, 0)
11. (S+, S−)← BSA[(S+, S−), (B−,B+)]12. sinon si (a+
i , a−i ,mi ) = (0, 0, 1) ou (1, 1, 1)
13. (S+, S−)← BSA[(S+, S−), (p, 0)]14. sinon si (a+
i , a−i ,mi ) = (1, 0, 1)
15. (S+, S−)← BSA[(S+, S−), (U+,U−)]16. sinon si (a+
i , a−i ,mi ) = (0, 1, 1)
17. (S+, S−)← BSA[(S+, S−), (V+,V−)]18. �n si
19. (S+, S−)← (S+/2, S−/2)20. �n pour
21. retourner (S+, S−)
24/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Architecture de l'unité arithmétique
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
25/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Architecture de l'unité arithmétique
Une observation et une optimisation possible
Toutes les opérations modulaires pourront être e�ectuées àl'aide d'un seul BSA
(C+,C−)← BSA[(A+,A−), (B+,B−)]
Deux multiplexeurs en amont du BSA
MUX 1 pour sélectionner les valeurs de (A+,A−)MUX 2 pour sélectionner les valeurs de (B+,B−)
Or, 3 valeurs initialement possibles pour B+ et B− : 0, p et 2p
=⇒ Se servir du caractère redondant de BS pour n'avoir que pcomme entrée du MUX2
26/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Architecture de l'unité arithmétique
Addition modulaire en BS (version optimisée)
Méthode de Takagi modulo 2p
Entrées : 2n ≤ 2p < 2n+1, −2p < A = (an+1an · · · a0)BS < 2p,−2p < B = (bn+1bn · · · b0)BS < 2p.Sortie : S = A + B (mod 2p), avec S = (sn+1sn · · · s0)BS .1. (T+,T−)← BSA[(A+,A−), (B+,B−)]
2. si tv = 4tn+2 + 2tn+1 + tn < 0
3. (S+, S−)← BSA[(T+,T−), (4p, 2p)]
4. sinon si tv > 0
5. (S+, S−)← BSA[(T+,T−), (2p, 4p)]
6. sinon si tv = 0
7. (S+, S−)← BSA[(T+,T−), (p, p)]
8. �n si
9. retourner S
27/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Architecture de l'unité arithmétique
Multiplication de Montgomery en BS (version optimisée)Entrées : p = (pn−1 · · · p1p0)2, pgcd(p, 2) = 1,−2p < A = (an+1an · · · a0)BS < 2p,−2p < B = (bn+1bn · · · b0)BS < 2p.Sortie : (S+, S−) = (A+,A−).(B+,B−).2−(n+2) (mod 2p).
1. (U+,U−)← BSA[(B+,B−), (2p, p)]2. (V+,V−)← BSA[(B−,B+), (2p, p)]3. (S+, S−)← BSA[(p, p), (p, p)]4. pour i = 0 à n + 15. mi ← (a+
i ⊕ a−i ).(b+0⊕ b−
0)
6. si (a+i , a
−i ,mi ) = (0, 0, 0) ou (1, 1, 0)
7. (S+, S−)← BSA[(S+, S−), (p, p)]8. sinon si (a+
i , a−i ,mi ) = (1, 0, 0)
9. (S+, S−)← BSA[(S+, S−), (B+,B−)]10. sinon si (a+
i , a−i ,mi ) = (0, 1, 0)
11. (S+, S−)← BSA[(S+, S−), (B−,B+)]12. sinon si (a+
i , a−i ,mi ) = (0, 0, 1) ou (1, 1, 1)
13. (S+, S−)← BSA[(S+, S−), (2p, p)]14. sinon si (a+
i , a−i ,mi ) = (1, 0, 1)
15. (S+, S−)← BSA[(S+, S−), (U+,U−)]16. sinon si (a+
i , a−i ,mi ) = (0, 1, 1)
17. (S+, S−)← BSA[(S+, S−), (V+,V−)]18. �n si
19. (S+, S−)← (S+/2, S−/2)20. �n pour
21. retourner (S+, S−)
28/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Architecture de l'unité arithmétique
Architecture de l'unité arithmétique
BSA−
SHIFT−
BSA+
SHIFT+
S−S+V+ V−
V−V+U−U+
U+ U−
S+ S−
OUT+ OUT−
MUX1+MUX1− MUX2−MUX2+
MUX 2MUX 1
out_A+out_A− out_B+
out_B−
b−0b
+0a
−i
a+i
cmd3
cmd5
cmd4
cmd1
tv(2 : 0)SELECTOR
mi
cmd2
A−A+ B−B+ P
MUX 3
BSA
DEMUX
SHIFT
28/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Résultats des implantations matérielles e�ectuées
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
29/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Résultats des implantations matérielles e�ectuées
Propriétés de l'unité arithmétiqueFPGA Xilinx XCV2000Fréquence de fonctionnement quasi-constante quelque soit `(longueur de k , en bits)
` 160 192 224 256 384 521
Fréquence (MHz) 93 87 91 87 91 88
` (taille des cles)
Surface (Slices) × Chemin critique (ns)
100 200 300 400 500 600
1× 10−5
2× 10−5
3× 10−5
4× 10−5
5× 10−5
6× 10−5
7× 10−5
8× 10−5
9× 10−5
10× 10−5
11× 10−5
12× 10−5
0
Mise à l'échelle facilitée
30/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Résultats des implantations matérielles e�ectuées
Résultats comparatifs
Référence Surface Temps Opérateurs
occupée [k]P FPGA?
[Orlando, 2001] − − Non
[Byrne, 2007] − − Non
[Mentens, 2007] − − Non
[Örs, 2008] − − Non
[Crowe, 2005] + − Non
[Daly, 2005] + − Non
[McIvor, 2004] − + Oui
[Sakiyama, 2006] − + Non
[Güneysu, 2008] + + Oui
Notre unité arithmétique supporte bien la comparaison avecl'état de l'art
30/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Conclusion et perspectives
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
31/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Conclusion et perspectives
Conclusion
L'unité arithmétique proposée est très performante :
Fréquence de fonctionnement élevéeMise à l'échelle facilitéeTemps de calcul de [k]P souvent plus court que l'état de l'artArchitecture compacte−→ intégration dans des milieux fortement contraints (ex. : cartes
à puce)
Nouvelle implantation de l'algorithme de Montgomery en BS
Apport décisif de la représentation BS
32/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conception d'une unité arithmétique pour courbes elliptiques
Conclusion et perspectives
Perspectives
Multiplieur de Montgomery en grande base dans lequel lesopérandes sont représentés dans un système redondant(d'Avizienis)
Moins de cycles d'horlogeMais...temps de cycle et surface augmentée
Utiliser une méthode d'inversion modulaire en BS
PGCDInversion de Montgomery
Utiliser des extensions arithmétiques du FPGA
blocs DSP
Concevoir une unité arithmétique autonome
Implanter un ensemble de registres (blocs RAM du FPGA)Conversion BS → Numération simple de position
Implantation sur circuit dédié ASIC
32/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
32/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par observation
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
33/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par observation
Comparaisons
Nombreuses contre-mesures pour les attaques simples parobservation dans la littérature
2 unités arithmétiques de la littérature embarquent desprotections :
[Byrne, 2007] : chaînes d'addition proposées par [Méloni, 2007][Ghosh, 2008] : opérations arithmétiques peuvent s'e�ectuer enparallèle
Contre-mesure vis-à-vis des attaques simples par observation laplus rapide (à 1 processeur) de la littérature combine :
NAF2(k)atomicité [Chavallier-Mames, 2004]
−→ En implantant cette contre-mesure, notre unité arithmétiquepour l'ECC est protégée contre les attaques simples parobservation avec le plus petit temps de calcul de [k]P
33/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
34/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
Protéger un cryptosystème ECC grâce à l'implantation de lapréservation de la parité
[Parhami, 2006] propose des portes logiques pour laquelle laparité des entrées = parité des sorties (Parity-Preserving Logic
Gates, PPLGs)
Exemple : une PPLG ayant deux bits en entrée (e1, e2) et deuxbits en sortie (s1, s2) doit obéir à la relation :
e1 ⊕ e2 = s1 ⊕ s2
Proposées initialement pour augmenter la �abilité des circuits
Objectifs de cette étude :
Montrer que les PPLGs peuvent également être utiliséescomme contre-mesure vis-à-vis des attaques par perturbationDonner des résultats pratiques (surcoût, taux de détection defautes)
35/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
PPLGs
Portes pour lesquelles la parité des entrées = parité sorties
Porte de Feynman (F2G)
F2Gs3 = e1 ⊕ e3
s2 = e1 ⊕ e2
s1 = e1
e3
e2
e1
−→ s1 ⊕ s2 ⊕ s3 = e1 ⊕ (e1 ⊕ e2)⊕ (e1 ⊕ e3) = e1 ⊕ e2 ⊕ e3
Porte de Fredkin (FRG)
FRGs3 = e1e3 ⊕ e1e2
s2 = e1e2 ⊕ e1e3
s1 = e1
e3
e2
e1
−→ s1 ⊕ s2 ⊕ s3 = e1 ⊕ (e1e2 ⊕ e1e3)⊕ (e1e3 ⊕ e1e2) =e1 ⊕ e2(e1 ⊕ e1)⊕ e3(e1 ⊕ e1) = e1 ⊕ e2 ⊕ e3
36/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
Conception d'un circuit préservant la parité (1/3)
Exemple d'application : BSA
b2 a1 b1 a0 b0a b b b ba a
0
0
a3 b3 a2 a3 2 2 1 1 0 0
s4 s3 s2 s1 s0s s s s s4 3 2 1 0
3
PPM PPM
PPM PPM PPM PPM
PPMPPM
+ + − − − − − − − −+ + + + + +
+ + + + +− − − − −
4 3 3 2 2 1 1 0
3 3 2 2 2 1 1 1 0 0 0
01122334
3
1. Choisir la partie du circuit à protéger
Diviser le circuit initial en n sous-circuits identiques (notés C)Chaque C sera ainsi protégé de la même façon avec des PPLGsExemple : C a comme bits d'entrées a+
i, b+
i, a−
i, b−
iet c+
iet
comme bits de sortie s−i+1 et s+
i
37/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
Conception d'un circuit préservant la parité (2/3)
b2 a1 b1 a0 b0a b b b ba a
0
0
a3 b3 a2 a3 2 2 1 1 0 0
s4 s3 s2 s1 s0s s s s s4 3 2 1 0
3
PPM PPM
PPM PPM PPM PPM
PPMPPM
+ + − − − − − − − −+ + + + + +
+ + + + +− − − − −
4 3 3 2 2 1 1 0
3 3 2 2 2 1 1 1 0 0 0
01122334
3
2. Obtenir les équations logiques correspondantesC relativement simple a�n de récupérer les équationsfacilementExemple : 1ère ligne de PPMs{
c−i = a+i ⊕ b+
i ⊕ a−ic+i = a+
i−1.b+i−1
+ a+i−1.a−i−1
+ b+i−1.a−i−1
2nde ligne de PPMs{s−i+1
= c−i .b−i + c−i .c
+i + b−i .c
+i
s+i = c−i ⊕ b−i ⊕ c+
i
38/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
Conception d'un circuit préservant la parité (3/3)
b2 a1 b1 a0 b0a b b b ba a
0
0
a3 b3 a2 a3 2 2 1 1 0 0
s4 s3 s2 s1 s0s s s s s4 3 2 1 0
3
PPM PPM
PPM PPM PPM PPM
PPMPPM
+ + − − − − − − − −+ + + + + +
+ + + + +− − − − −
4 3 3 2 2 1 1 0
3 3 2 2 2 1 1 1 0 0 0
01122334
3
3. Exprimer ces équations dans un corps de Galois
Ni F2G, ni FRG ne peuvent calculer la fonction � OR �
−→ Transformer les équations logiques grâce à x + y = x ⊕ y ⊕ x .y
Exemple :{c+i = a+
i−1.b+i−1⊕ a+
i−1.a−i−1
⊕ b+i−1.a−i−1
s−i+1= c−i .b
−i ⊕ c−i .c
+i ⊕ b−i .c
+i
4. Implanter ces équations grâce aux PPLGs
39/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
C protégé contre les fautes
PPM1
Verif.
b+ia+i a−i
p1
s+is−i+1po
Parite
PPM2
p24
5
b−i
c+ic+i+1
par1 = a+
i ⊕ b+i ⊕ a−i ⊕ c−i
par2 = a+i ⊕ b+
i ⊕ a−i ⊕ p1 ⊕ c+i+1
par3 = c+i ⊕ b−i ⊕ c−i ⊕ s−i+1
⊕ p2 ⊕ s+i
Si po = par1 + par2 + par3 = 1, faute(s) détectée(s)
40/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
Cellule PPM1
F2G
F2G
F2G
FRG
FRG
F2G
FRG
F2G
a+
b+
a− s
a+b+
a−a−b+
c
a+a−b+
0
0
0
0
0
0
0
0
0
Duplication : F2G(e1 = x , e2 = 0, e3 = 0, s1 = x , s2 = x ,s3 = x)
Bits de parité potentiellement simpli�ables
41/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
Cellule PPM2
FRG
F2G F2G
F2G
F2G
FRG
F2G
FRG
s
a+b+
a−b+
c
a+a−
0
0
0
0
0
a−
a+a+
0
0b+
0
0
Duplication : F2G(e1 = x , e2 = 0, e3 = 0, s1 = x , s2 = x ,s3 = x)
Bits de parité potentiellement simpli�ables
42/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
Résultats d'implantation
Surcoût (avec n = 160)
Architecture Surface (µm2) Chemin critique (ns)
BSA sans PPLGs 134440 1,39
BSA avec PPLGs 698157 5,69
Surcoût ×5,2 ×4,1Capacité de détection de fautes
Nombre de bits fautés 1 bit 2 bits
Fautes détectées 80% 86,8%
Fautes sans conséquence 14,3% 2,1%
Fautes non-détectées 5,7% 11,1%
43/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Sécurisation de cette unité arithmétique contre les attaques...
...par perturbation
Conclusion et perspectives
Utilisation du principe de la préservation de la parité pourprotéger les cryptosystèmes contre les attaques parperturbation
Méthode de conceptionPremiers résultats encourageants
Perspectives :
Diminuer le taux de fautes non-détectéesDiminuer le surcoût sur la surface
Trouver de nouvelles PPLGs plus complexes
Étude plus poussée sur le mécanisme de détectionAutres modèles de fautes (collage, etc.), > 2 fautes, fautescontigues
Suite logicielle pour automatisationUtiliser cette méthode pour protéger le reste de l'unitéarithmétique (multiplexeurs, etc.)
43/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conclusion et perspectives générales
Sommaire
1. Contexte
1.1 Courbes elliptiques1.2 Arithmétique des ordinateurs1.3 Attaques physiques1.4 Contre-mesures
2. Conception d'une unité arithmétique pour courbes elliptiques
2.1 Paramètres d'implantation2.2 Arithmétique utilisée2.3 Architecture de l'unité arithmétique2.4 Résultats des implantations matérielles e�ectuées2.5 Conclusion et perspectives
3. Sécurisation de cette unité arithmétique contre les attaques...
3.1 ...par observation3.2 ...par perturbation
4. Conclusion et perspectives générales
44/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conclusion et perspectives générales
Bilan
Bilan des travaux e�ectués et perspectives (1/2)
Conception d'une unité arithmétique hautes performances pourl'ECC
Perspectives :
Multiplieur de Montgomery en grande base dans lequel lesopérandes sont représentés dans un système redondant(d'Avizienis)Inversion modulaire en BSExtensions arithmétiques du FPGAUnité arithmétique à l'autonomie accrueImplantation sur circuit dédié ASIC
Protection de cette unité arithmétique contre les attaquessimples par observation amenant un temps de calcul de [k]Pplus petit que l'état de l'art
45/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conclusion et perspectives générales
Bilan
Bilan des travaux e�ectués et perspectives (2/2)
Protection de cette unité arithmétique contre les attaques parperturbation à l'aide de la préservation de la parité
Perspectives :
Diminuer le taux de fautes non-détectéesDiminuer le surcoût sur la surfaceÉtude plus poussée sur le mécanisme de détectionSuite logicielle pour automatisationUtiliser cette méthode pour protéger le reste de l'unitéarithmétique
Plus largement, cette étude se veut être une aide utile pourtout concepteur de circuits pour l'ECC devant concilier desimpératifs de performance et de sécurité
46/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conclusion et perspectives générales
Di�usion de nos résultats
Production scienti�que (selon norme AERES)
Communications avec actes dans un congrès internationalFDTC 2008, NordSec 2007, ReCoSoC 2006
Communications avec actes dans un congrès nationalJP-CNFM 2008
Communications orales sans actes dans un congrèsinternational ou national
YACC 2008, JNRDM 2008
Communications par a�che dans un congrès international ounational
JNRDM 2007, ARCHI'07
DistinctionMeilleure présentation orale aux JNRDM 2008
Productions scienti�ques futuresArticle dans revue internationale avec comité de lecture pourl'unité arithmétique proposée au cours de cette étude
47/47
Conception et sécurisation d'unités arithmétiques hautes performances pour courbes elliptiques
Conclusion et perspectives générales
Remerciements
Cette présentation est terminée.Je vous remercie de votre attention.
Je tâcherai de répondre à vos questions le plus clairement possible.(Cette présentation a été réalisée avec la classe Beamer
� Montpellier �)
Recommended