L’Art du Secret

L'Art du Secret: 2. Assurer la confidentialité dans la société de l'information

1

Leçon 2Assurer la confidentialité dans la société de l’information

31 mars 2011

*L’Art du Secret

Jean-Claude Asselborn

Confidentialité, Discrétion et

Confiancedans la Société de l’Information


2

* structure générale

31 mars 2011

Leçon 2

Discrétion

Signatureélectroniqu

e

Leçon 4

Paiementélectroniqu

eLeçon 5

Leçon 3

confidentialité

entre partenaire

sLeçon 1dans la

société de l’information

Assurer la

En hommage à WhitfieldDIFFIE


3

Bob

clé 128 bitclé 128 bit

*état actuel

31 mars 2011

Edgar

réseau

AES

16 octets en clair

AES16 octets chiffrés

procédé de chiffrement AES

accord sur la clé secrète de chiffrement

0011010101010001110116 octets chiffrés

Alice

16 octets en clair

Rappel :


4

*problème restant

31 mars 2011

AliceBob

canal sécurisé de concertation

canal non sécurisé de

communication

Comment se concerter

en l’absence d’un canal sécurisé ?

Rappel :

Comment échanger des clés à travers un canal non sécurisé ?

Edgar


5 31 mars 2011

*le renouveau

Whitfield

"New Directions in Cryptography"[IEEE Transactions on Information Theory, November 1976] 1976

Martin

Ralph Merkle


6

*structure de cette leçon

31 mars 2011

échange de clés

autour de RSA

autres approches

1

2

3

échange de clés

Diffie-Hellmanou crypto quantique


7 31 mars 2011

n. (n-1) / 2 clés

1

2

3

4

56

n-1

n

...

réseau en étoile: n - 1 clés

*e-commerce et clés1 2 communication bilatérale :1 clé

1

2

3

45

n-1

n

...

réseau ouvert


8 31 mars 2011

* groupes finis

123456789101112

1 2 3 4 5 6 7 8 9 10 111 2 3 4 5 6 7 8 9 10 11 12

12

Exemple : groupe multiplicatif Z13

*2 4 6 8 10 12 1 3 5 7 9 113 6 9 12 2 5 8 11 1 4 7 104 8 12 3 7 11 2 6 10 1 5 95 10 2 7 12 4 9 1 6 11 3 86 12 5 11 4 10 3 9 2 8 1 77 1 8 2 9 3 10 4 11 5 12 68 3 11 6 1 9 4 12 7 2 10 59 5 1 10 6 2 11 7 3 12 8 4

10 7 4 1 11 8 5 2 12 9 6 311 9 7 5 3 1 12 10 8 6 4 212 11 10 9 8 7 6 5 4 3 2 1

3 * 6 = 1818 mod 13

= 5

2 est l’élément inverse de 7, car 7 * 2 = 1 mod 13

Il existe un algorithme rapidepour calculer l’inverse dans Zn

élément neutre


9 31 mars 2011

*ordre des éléments de Z13

123456789101112

1

1 2

3 9 1

3

5 12 8 1

4 5

4 3 12 9 10 1

6 7 8 9 10 11

2 4 8 3 6 12 11 9 5 10 7 1

6789101112

1010123941

8551

125

991

33

211

47

1212

112

76

2

33

9

58

8

44

10

112

6

11

1

12

puissances

Les puissances de 2 engendrent tout le

groupe.2 est un générateur

du groupe

8 est un élément d’ordre 4, car 84 mod

13 = 1

Il existe un algorithme rapide pour calculer une exponentiation modulo n dans Zn


10

BobAlice

31 mars 2011

*échange Diffie-Hellman

Edgar

p, gpublics

x yA = gx mod p B = gy mod p

A

B

= Bx mod p= (gy)x mod p= g x*y mod p

clé = Ay mod p= (gx)y mod p= g x*y mod p

cléA = gx mod pB = gy mod px = ?y = ?

choisir x secret choisir y secret

échanger les résultats

calculer laclé commune

calculer la clé commune

On travaille dans Zp* avec le générateur g


11 31 mars 2011

*problème du logarithme discret

Edgar

A = gx mod px = ? x = log A mod p

ce problème estconsidéré comme difficile

La recherche exhaustive ne fonctionne pas pour des x et

des p élevés.

trouver l‘exposant secret !


12

*approche nouvelle

31 mars 2011

[ parenthèse]

Charles H. BENNET

Gilles BRASSARD

1984

Quantum Cryptography :public key distribution and coin tossing

[ International Conference on Computing, Systems & Signal Processing, Bangalore, India ]

transmettre des états quantiques (non falsifiables)

0° 45° 90° 135°polarisation de photons

0

1

mode de codage A

0

1mode de codage B

BB


13

BobAlice

31 mars 2011

*échange quantique[ parenthèse]

générateur de

photons polarisés

analyseur dephotons polarisés

fibreoptique


communication

canal de concertatio

n

canal d’échange

de clé


14

*protocole d’échange BB84

31 mars 2011

A B110101001000101011

1 1 0 1 0 1 0 0 1 0

1 101 010 101 11séquence commune

1 101 010 101 11

110101010111

lice obaléatoir

e

aléatoire

aléatoire

[ parenthèse]


15

*validation BB84

31 mars 2011

A B110101001000101011

1 1 0 1 0 1 0 0 1 0 0 0 1 0

lice obtoute intervention d’Edgar introduit des incohérences dans la

suite binaire

Tester un sous-ensemble des

bitscommuns

[OK][KO]

maintenir la chaîne excepté les bits testés

rejeter la chaîne et recommencer

Edgar dans les parages

[ parenthèse]


16


31 mars 2011

échange de clés

autour de RSA

autres approches

1

2

3

autour de RSAcryptographieà clé publique


17 31 mars 2011

registre desclés publiques

*clé publique – clé privée

x y

A = gx mod p B = gy mod pA

B

clé commune =

clé publiquedu partenaire( )

ma clé privée

mod p

Bob

Alice

clé privéeAlice

clé privéeBob


18 31 mars 2011

*cryptographie asymétrique

fc1

f

k1 k2

c2

paire de clés

m

texte en clair

m

texte en clairtexte chiffré

fonction trappe


19 31 mars 2011

*chiffrement de messages

f fm

texte en clair

m

texte en clair

c1

texte chiffré

e

clé publiquedu partenaire

d

clé secrètedu partenaire

Seul le partenaire est à même de déchiffrer le

message.

20 31 mars 2011L'Art du Secret: 2. Assurer la confidentialité dans la société de l'information

*authentification de messages

fm

texte en clair

c2

texte chiffré

e

clé publique de l’expéditeur

f m

texte en clair

d

clé privée de l’expéditeur

Tout le monde peut déchiffrer

ce message.

le message est authentifié

L’expéditeur est le seul à

même de chiffrer le

message de cette façon.


21 31 mars 2011

*trouver un exemple

Qui est en mesure de trouver un bon

exemple de fonction à sens unique ?


22 31 mars 2011

*RSA

Ronald Adi Leonard

1978« A Method for Obtaining Digital

Signatures and Public Key Cryptosystems"

[Communications of the ACM, Vol 21, n° 12]


23 31 mars 2011

*RSA en 1977

RivestShamir

Adleman


24 31 mars 2011

*fonction trappe RSA

m' = m k mod nm

message en entrée message en sortie

m'

k n

le truc:n est le produit de

deux nombres premiersayant chacun 512 bit au

moins

n est public, mais ses deux facteurs premiers sont maintenus secrets,

car ils permettent de calculer la clé secrète

k est l’exposant(public ou secret)


25 31 mars 2011

*message = nombreBonjour !message

10000101101111110111011010101101111111010111100100100000une suitede codesbinaires

10000101101111110111011010101101111111010111100100100000un grand nombrebinaire

37 646 688 348 633 376un grand nombre décimal

Tout message peut être interprété comme un grand nombre entier

37 billiards 646 billions 688 milliards 348 millions 633 mille et 376

[ commentaire]

26 31 mars 2011L'Art du Secret: 2. Assurer la confidentialité dans la société de l'information

*calculer avec des messagesBonjour !message

37.646.688.348.633.376nombre associé

Bonjour !( )2= 37.646.688.348.633.376( )2

=1.417.273.143.619.127.986.862.606.861.157.376

RSA nécessite des nombres à plusieurs centaines de chiffres

décimaux.

1 quintilliard 417 quintillions 273 quadrillards 143 quadrillions619 trilliards 127 trillions 986 billiards 862 billions

606 milliards 861 millions 157 mille et 376

[ commentaire]


27 31 mars 2011

*conséquences des grands nombres

Les processeurs calculent seulement sur 64 ou 128 bits

on doit disposer d'algorithmes spéciaux de calcul

l'exploration complète de domaines de grands nombres est pratiquement

impossible

âge de l'univers : 10 10 années = 10 17 secondes = 10 26 nanosecondes

[ commentaire]


28

*autres conséquences

31 mars 2011

m' = m k mod nm m'

{ m < n } { m’ < n }Les messages doivent être assez courts.

une centaine de caractères

messages longs: décomposer en blocs

peu performant comparé à AES

On préfère des messages courts :

transmission de clé AES

signature électronique

transactions financières

leçon 4

leçon 5

leçon 1

[ commentaire]


29

BobAlice

31 mars 2011

*chiffrement AES

RSA RSAm

message en clair

m

message en clair

me mod n

message chiffré

ed

exposant public Bob

exposant privé de

Bob

( e, n)

clé publique de Bob

module de Bob

( e, n)

transmission de la clé publique:voir leçon 4

ne

n

Bob

31 mars 2011L'Art du Secret: 2. Assurer la confidentialité dans la société de l'information

*relation entre e, d et n

RSA m

message en clair

me mod n

message chiffré

d

30

exposant public Bob

exposant privé de

Bob

module de Bob

e

n

(me)d mod n =

n = p * q

On montre quee et d

doivent êtreinversesmodulo

(p-1)*(q-1) nombre

d’éléments de Zn*


31 31 mars 2011

*génération des paramètres1. choisir deux nombres premiers

très grands(à tenir secrets)

p

q

2. calculer n

3. sélectionner l‘exposant d’encodage

e

4. calculer l’exposant de décodage

calculer inverse de e

modulo(p – 1)(q – 1)

d

7. publier

*

5. sauvegarderdans un système

sécurisé

6. détruirep et q

n


31 mars 2011

*choix de e

Fn = 2 + 12n

F0 = 21 + 1 = 3 = (11)2

F1 = 22 + 1 = 5 = (101)2

F2 = 24 + 1 = 17 = (10001)2

F3 = 28 + 1 = 257 = (100000001)2

F4 = 216 + 1 = 65 537 = (10000000000000001)2

nombres de Fermat

Pierre de FERMAT1601-1665

Contrainte: e ne doit pas avoir de diviseurs communs avec (p – 1) ou avec (q – 1)

Essayer d’optimiser les calculs d’encodage:• longueur binaire courte• minimiser le nombre de 1 binaires

dangereux

fréquemment utilisé32

chiffré(m) = m 65537 mod n


33 31 mars 2011

*problèmes RSA

p

q

Celui qui connaît p et qpeut recalculer

la clé privée ne

d

Qui doit choisir

p et q ?

Peut-on retrouver

p et q à partir de n ?

voir leçon 4


34 31 mars 2011

*algorithmes de factorisation

FermatLehmer- Powers

p+1 (Williams)

p–1 (Pollard)

rho (Pollard)

Morrison- BrillhartShanks

Dixon

QS (Pomerance)

ECC (Lenstra)

NFS (Lenstra)

MPQS (Silverman)

Valle

Seysen

Shor


35

*record 2009

31 mars 2011

RSA-768 = 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

= 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 × 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Joppe W. Bos, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, et Paul Zimmermann

232 chiffres

décimaux

équipe

p

q

n


36 31 mars 2011

*Recommandationspour la longueur

de nprivé: 1024 bit

entreprise: 2048 bit

longue durée : 3072 bit

Edgar

Si je découvre un algorithme

de factorisation efficace,

alors RSA est mort

au-delà de 2030

NSA

GCHQGovernment

Communications Headquarters


37 31 mars 2011

low exponent

attack

commonmodulus

attackblind

signature attack

*33 années d‘attaques de RSA

shortmessage

attackmasked

message attackcycle

attackpartial

key exposureattack

timingattackrandom

faultsattack

paddingattack


38

*deux pionniers à Luxembourg

31 mars 2011

Whitfield DIFFIE Clifford COCKS


39


31 mars 2011

échange de clés

autour de RSA

autres approches

1

2

3 autres approches courbeselliptiques


40

*l’informatique mobile

31 mars 2011

processeur

mémoireprogramm

emémoirede travail

mémoirepermanente

entrée /sortie

cryptographie

cléstemporair

e

bloc en clair/ bloc chiffré

faiblepuissance

Il faut des algorithmes appropriés


41 31 mars 2011

*les courbes elliptiquesy2 = x3 + ax + b

Si on travaille sur des nombres réels, la courbe peut être

représentée.

symétrie par rapport

à OxUne droite passant par deux points de la courbe,passe aussi par un troisième point de la courbe.


*opérations sur des points (1)

P Q P = QP and Q ne sont pas alignés verticalement

On définit une opération : P(x1,y1) + Q(x2, y2) = R(x3, y3)

= P + Q

= P + Q

x3 et y3 se calculent facilemen

t

31 mars 2011L'Art du Secret: 2. Assurer la confidentialité dans la société de l'information

OO

*opérations sur des points (2)

P Q P = QP et Q sont alignés verticalement

élément neutre= point à l‘infini

43


44 31 mars 2011

*courbes elliptiques sur Zp

y2 x3 + 3x + 9 (mod 11)

a, b Z11Pour les opérations de groupe P + Q = R

on se sert des formules analytiques dans Zp

m = 3 xP2 + a

2 yP

m = yQ - yP xQ - xP xR = m2 - xP - xQ

yR = -m (xR - xP ) - yP

P Q

P = Q

R

P + O = O + P = PxP = xQ R = O


45 31 mars 2011

*exemple : groupe y2 x3 + 3x + 9 (mod 11)

pointABCDEFGHIJO

(0, 3)(0, 8)(2, 1)(2, 10)(3, 1)(3, 10)(6, 1)(6, 10)(10, 4)(10, 7)infini

source de l‘exemple: D. Wätgen: "Kryptographie", Spektrum Akademischer Verlag, 2004, p. 247

ABCDEFGHIJO

EOJCGBIFDHA

AOFDIAHEJGCB

BJDAOHIFGBEC

CCIOBJGHEFAD

DGAHJIODBCFE

EBHIGOJACEDF

FIEFHDACOJBG

GFJGEBCODAIH

HDGBFCEJAHOI

IHCEAFDBIOGJ

JABCDEFGHIJO

O+Ordre : 11


46

*courbe elliptique standardisée

31 mars 2011

courbe NIST P-384 E : y2 x3 – 3x + b (mod p)module p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319

ordre du groupe = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643 points

b = b3312fa7 e23ee7e4 988e056b e3f82d19 181d9c6e fe814112 0314088f 5013875a c656398d 8a2ed19d 2a85c8ed d3ec2aef

Générateur:Gx= aa87ca22 be8b0537 8eb1c71e f320ad74 6e1d3b62 8ba79b98 59f741e0 82542a38 5502f25d bf55296c 3a545e38 72760ab7Gy= 3617de4a 96262c6f 5d9e98bf 9292dc29 f8f41dbd 289a147c e9da3113 b5f0b8c0 0a60b1ce 1d7e819d 7a431d7c 90ea0e5f

registre public

*échange de clé

B = y. G

K = x. B= (k1, k2)

A = x. G

K = y. A= (k1, k2)

E(Zp) courbe elliptique sur ZpG = générateur de E(Zp)

x, y dans Zp

E(Zp) G

x yA

B

Bob

Alicepoint commun sur la courbe

G + G + … + G

y foisG + G + … + G

x fois


48 31 mars 2011

*chiffrement simple

k1.m1 (mod p)

k2.m2 (mod p)

m1

demi-blocs chiffrés

k1-1.e1 (mod p)

k2-1.e2 (mod p)m2

e1

e2

m1m2

K = x. B= (k1, k2)

K = y. A= (k1, k2)

Bob

Alice

blocen clair

blocen clair

échange

inverse modulo p

k1 -1 k2 -1k1 k2

Menezes-Vanstone


49

*menaces sur votre carte

31 mars 2011

Il y a toujours de

l’information qui suinte.

Jean-Sébastien CORON

durée des calcul

consommation électrique

radiations

erreursprovoquéescontraintes

physiquesside-channel

attacks

*Alice et ses outils

31 mars 2011L'Art du Secret: 2. Assurer la confidentialité dans la société de l'information 50

échange de clés avec des inconnus

chiffrement de messages

authentification de messages

utilisation de cartes intelligentes


*Alice et Bob suspects

31 mars 201151

AliceBob


communication

Tiens, tiens !Ces deux-là chiffrent leur communication.

une affaire ?des terroristes ?

un mauvais coup ?

Comment communiquer sans attirer l’attention ?


52

* vous le saurez la prochaine fois

31 mars 2011

Leçon 2

Discrétion

Signatureélectroniqu

e

Leçon 4

Paiementélectroniqu

eLeçon 5

Leçon 3

confidentialité

entre partenaire

sLeçon 1dans la

société de l’information

Assurer la le 14 avril 2011


53

*attention

31 mars 2011

17:30 hrsCampus Kirchberg

Salle B02

Documents

L’Art du Secret