Authentification de Messages
• Utilisation du chiffrement Conventionnel
– Partage de clé secrète par l’émetteur et le récepteur
• Authentification sans chiffrement de message
– Un champ d’authentication est généré et ajouté à
chaque message
• Code d’Authentification de Message (MAC) --
Calculer le MAC comme une fonction du message M et de
la clé K. MAC = F(K, M)
Authentification de Messages
Authentification de Messages
Authentification de Messages
Une valeur secrète est ajoutée par les 2 parties au message avant l’application
de la fonction de hachage qui est utilisée pour obtenir le MAC,
cette valeur secrète est enlevée avant transmission.
Zero-Knowledge
Identification à apport nul de connaissance
Prouver sans révéler le secret
Vérifier sans connaître le secret
Histoire de la caverne magique
1°) Alice et Bob sont à l’entrée E de la caverne
2°) Seule Alice entre dans la caverne, jusqu’au point de rendez-vous X.
3°) Alors en se cachant de Bob, elle s’engage au hasard dans l’un des couloirs,
noté 1 ou 2, jusqu’à la porte magique M.
4°) Bob entre alors à son tour jusqu’au point de rendez-vous X et
choisit au hasard l’un des deux couloirs puis défie Alice d’apparaître
par le couloir choisi.
5°) Alice répond. Si nécessaire elle passe par la porte magique
(en utilisant le mot de passe secret) Bob vérifie que Claire
apparaît dans le couloir choisi
Alice et Bob répètent L fois les étapes 1 à 5.
La caverne magique de Guillou-Quisquater
Entrée
E
X
1 2
M
Porte Magique
M M
Zero-knowledge protocols
• Alice wants to prove to Bob that she is Alice.
– If she sends identification, Bob (or an
eavesdropper) can use it.
• Example: Authority chooses a number N=77,
known by all.
• Alice’s public ID: (58, 67)
• Alice’s private ID: (9,10)
– These are multiplicative inverses mod 77
Zero-knowledge protocols
• Alice chooses some random numbers and computes
their square mod N: {19, 24, 51}
192(mod 77) = 53,
242(mod 77) = 37,
512(mod 77) = 60
• Alice sends {53,37,60} to Bob.
• Bob sends back a random 2x3 matrix of 1s and 0s.
–01
–10
–11
Zero-knowledge protocols
• Alice uses this grid, plus her original random
numbers and her secret numbers, to compute:
19 * 90 * 101 (mod 77) = 36
24 * 91 * 100 (mod 77) = 62
51 * 91 * 101 (mod 77) = 47
• She sends {36,62,47} to Bob.
Zero-knowledge protocols
• Bob verifies Alice’s identity by computing:
– {58,67} are Alice’s public numbers
362 *580 *671 (mod 77)= 53
622 *581 * 670 (mod 77) = 37
472 * 581 * 671 (mod 77) = 60
• Alice’s original numbers reappear!
Zero-knowledge protocols
• In a real system, N would be very large
– 160 digits.
• Many more numbers would be generated.
• This works because Alice’s secret numbers
are multiplicative inverses of her public
numbers mod N.
• Also, Bob learns nothing that he didn’t
know before.
Courbes elliptiques
Corps de Galois
• Cette appellation est synonyme de Corps fini.
• Pour p premier et n entier ≥ 1, on appelle GF(pn) le
corps de Galois à pn éléments.
• Un élément de cet ensemble est représenté comme un n-
uplet de p éléments de Z/pZ: e = (e1,…,en).
• Cet ensemble est muni d’une addition et d’une
multiplication. En fait, c’est un corps fini: tout élément
non nul est inversible.
• L’addition est simple: c’est l’addition composantes à
composantes dans Z/pZ.
• La multiplication est plus compliquée, mais plus simple
qu’une multiplication modulo un nombre taille pn.
Courbe elliptique sur GF(p)
• Une courbe elliptique C est l’ensemble de points (x,y) dans un
espace vectoriel de dimension 2, obéissant à une équation
cubique sur ses coordonnées.
• Exemple dans Zp2, l’ensemble C(a,b) des points
P = (x,y), x, y Zp tel y2 = x3 + ax + b mod p où a, b R sont
fixes sachant que le discriminant
Δ = - 16 ( 4 a3 + 27 b2) ≠ 0.
• Le problème du Logarithme discret sur une courbe elliptique
(ECDLP Elliptic Curve Discrere Logarithm Problem) se
transcrit comme suit : Soit P un point sur la courbe, étant
donné Q=xP, retrouver x.
Exemples
Elliptic Curve Addition:
• Adding distinct
points P and Q
* The negative of a point P is
its reflection in the x-axis.
Elliptic Curve Addition:
• Adding the points P
and -P
Elliptic Curve Addition
• Doubling the point P
Elliptic Curve Groups over Fp
• Calculations over real
number are slow and
inaccurate.
• y2 mod p = x3 + ax + b mod p
– x, y, a, b are in Fp
• finite points
• no geometric approach
-P
P+Q
P Q
Elliptic Curve Groups over Fp
• Adding distinct points P and Q (P+Q=R)
P(xP, yP) is not − Q = (xQ, − yQ mod p)
s = (yP – yQ) ∕ (xP – xQ) mod p
xR = s2 – xP – xQ mod p
yR = – yP + s(xP – xR) mod p
• Doubling the point P (2P=R)
yP ≠ 0
s = (3xP2 + a) ∕ 2yP mod p
xR = s2 – 2xP mod p, yR = – yP + s(xP – xR) mod p
Addition
Posons P1(x1, y1), P2(x2, y2), P3(x3, y3).
Par convention 0(I,I), I comme Infini. On a: (admis)
1) -P1(x1, -y1)
2) Si x1 ≠ I, x2 ≠ I et P1 = -P2 alors x3 = I et y3 = I.
3) Si x1 ≠ I, x2 ≠ I et P1 ≠ P2 alors en posant
m = (y2 - y1) / (x2 - x1),
on a x3 = m2 - x1 - x2
et y3 = m.(x1 - x3) - y1.
4) Si x1 ≠ I, x2 ≠ I et P1 = P2 alors en posant
m = (3.x12 + a) / (2.y1) puis utiliser les mêmes
formules qu'en 3).
Addition multiple d’un point : k. P
Q = k. P = P + P + … + P (k fois)
La version de square and multiply dans le cas
d’une courbe elliptique
Calculer Q = 77.P
On écrit 77 en binaire : 77 = (1001101)2.
Ensuite si le bit traité est 0, on double le point et si
le bit traité est 1 on double le point et on rajoute au
résultat P :
P→ 2.P → 4.P → 9.P → 19.P → 38.P → 77.P
1 0 0 1 1 0 1
– Addition (P1P2)
y2 y1
Computational Cost x2 x1
I+3M
x3 2 x1 x2
y3 ( x1 x3 ) x3 y1
– Doubling (P1=P2) 3x1 a
2
Computational Cost 2 y1
I+4M x3 2 2 x1
y3 ( x1 x3 ) x3 y1
Diffie-Hellman en courbes
elliptiques
• Alice choisit un point P aléatoirement sur une
courbe elliptique E et un entier a.
• Alice calcule a.P et l’envoie à Bob.
• Bob choisit un entier b, calcule K=b.(a.P) et
envoie b.P à Alice.
• Alice calcule K=a.(b.P).
• Problèmes: déterminer une courbe elliptiques et
choisir des points aléatoirement dans la courbe.
ECC - Diffie-Hellman
Elliptic Curve Security
• Basic computation of ECC
– Q=kP= P ...
P
P where P is a curve point, k is an integer
k times
• Strength of ECC: Given curve, the point P, and kP
It is hard to recover k (ECDLP)
• Elliptic curve cryptosystems give the most security per bit of any known
public-key scheme.
• The ECDLP problem appears to be much more difficult than the integer
factorisation problem and the discrete logarithm problem of Zp.
• The strength of elliptic curve cryptosystems grows much faster with the
key size increases than does the strength of RSA.
Elliptic Curve Security
Symmetric Key RSA and Diffie- Elliptic Curve Key
Size Hellman Size
(bits) Key Size (bits) (bits)
80 1024 160
112 2048 224
128 3072 256
192 7680 384
256 15360 521
NIST Recommended Key Sizes
ECC Benefits
ECC is very useful for application where:
• computational power is limited (wireless devices, PC cards)
• integrated circuit space is limited (wireless devices, PC cards)
• high speed is required.
• intensive use of signing, verifying or authenticating is required.
• signed messages are required to be stored or transmitted
(especially for short messages).
• bandwidth is limited (wireless communications and some
computer networks).
