Fichier PDF

Partagez, hébergez et archivez facilement vos documents au format PDF

Partager un fichier Mes fichiers Boite à outils PDF Recherche Aide Contact



Resume Cours .pdf



Nom original: Resume_Cours.pdf

Ce document au format PDF 1.4 a été généré par TeX / pdfeTeX-1.30.4, et a été envoyé sur fichier-pdf.fr le 02/03/2011 à 19:04, depuis l'adresse IP 77.195.x.x. La présente page de téléchargement du fichier a été vue 1551 fois.
Taille du document: 129 Ko (4 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


´
´ DE COURS DE CRYPTOGRAPHIE
RESUM
E
´
DUT Informatique, S4 Parcours Etudes
Courtes

1
1.1

Arithm´
etique ´
el´
ementaire
Division, congruence

Division euclidienne
Soient a et b deux entiers avec b 6= 0 ; il existe un
unique couple d’entiers (q, r) tel que a = q.b + r et
0 ≤ r < |b|. a s’appelle le dividende, b s’appelle le
diviseur, q s’appelle le quotient de la division de a
par b, r s’appelle le reste de la division de a par b.

2. Pour tout entier c non nul, a ≡ b [m] ⇔
a.c ≡ b.c [m.c].
3. Si a ≡ b [m.n], alors a ≡ b [m] et a ≡ b [n].
4. La relation de congruence modulo m est une
relation d’´equivalence :
– pour tout entier a, a ≡ a [m] (r´efl´exivit´e),
– si a ≡ b [m], alors b ≡ a [m] (sym´etrie),
– si a ≡ b [m] et b ≡ c [m], alors a ≡ c [m]
(transitivit´e).

Entiers modulaires
On note Z/nZ l’ensemble des entiers modulo n,
Divisibilit´
e
c’est-`a-dire l’ensemble des classes d’´equivalence
Notation : a | b ⇔ a divise b ⇔ b est un multiple pour la relation de congruence modulo n. Chaque
de a ⇔ ∃k ∈ Z, b = ak
´el´ement de Z/nZ a un unique repr´esentant compris entre 0 et n−1. L’addition et la multiplication
sont
bien d´efinies dans Z/nZ.
Propri´
et´
es
1. Pour tout entier a, 1 | a et a | a (r´eflexivit´e).
2. Si a | b et b | c, alors a | c (transitivit´e).
1.2 Exponentiation modulaire
3. Si a | b et a | c, alors a | (b + c).
4. Pour tout entier c non nul, a | b ⇔ a.c | b.c Algorithme d’exponentiation rapide : Pour
calculer ab modulo n :
Congruence
– Ecrire
P b comme somme de puissances de 2 :
Notation : a ≡ b [n] ⇔ a est congru `a b modulo n
b = ki=0 bi 2i (´ecriture binaire).
k
⇔ n divise b − a ⇔ ∃k ∈ Z, a = b + k.n.
– Calculer a2 , a4 , a8 , . . . a2 modulo n par mises
au carr´e successives.
i
Propri´
et´
es
– Faire le produit des a2 modulo n pour les indices i tels que bi = 1.
1. L’addition et la multiplication sont compaeme du lotibles avec la relation de congruence : si Le probl`eme inverse s’appelle probl`
a ≡ b [m] et c ≡ d [m], alors a+b ≡ c+d [m] garithme discret : ´etant donn´es a et c, trouver
et a.c ≡ b.d [m]
b tel que ab ≡ c [n]. C’est un probl`eme difficile.


esum´
e de cours


ethode na¨ıve de factorisation : Pour
1. Alice et Bob choisissent un modulo N (de d´ecomposer un entier n en nombre premier, on
si p | n pour tout nombre
pr´ef´erence un grand nombre premier) et un teste successivement

premier p < n ; en cas de succ`es, on recommence
entier g ; N et g ne sont pas secrets.
`a partir de p en rempla¸cant n par n/p, sinon, n
2. Alice choisit un nombre secret a. Bob choisit est premier.
un nombre secret b.
Lemme d’Euclide
3. Alice calcule ca ≡ g a [N ] et le transmet `a
Soient a et b deux entiers et p un nombre premier.
Bob. Bob calcule cb ≡ g b [N ] et le transmet
Alors p | ab ⇒ p | a ou p | b .
`a Alice. ca et cb ne sont pas secrets.

Echange de cl´
es Diffie-Hellman :

4. Alice re¸coit cb et calcule Kab ≡ (cb )a ≡
(g b )a ≡ g ba [N ]. Bob re¸coit ca et calcule 2.2
Kab ≡ (ca )b ≡ (g a )b ≡ g ab [N ].

PGCD et nombres premiers entre
eux

5. Alice et Bob disposent maintenant d’une cl´e
efinitions : Soient a et b deux entiers. Le plus
commune Kab dont ils peuvent se servir pour D´
grand commun diviseur de a et b, not´e pgcd(a, b)
chiffrer leur correspondance.
ou a ∧ b, est le plus grand entier d tel que d | a
Un attaquant passif qui ´ecoute les ´echanges et d | b. Le plus petit commun multiple de a et b,
connaˆıt N , ca ≡ g a [N ] et cb ≡ g b [N ] mais il not´e ppcm(a, b) ou a ∨ b, est le plus petit entier m
ne connaˆıt ni a ni b : il ne peut pas calculer (faci- tel que a | m et b | m.
lement) la cl´e Kab .
On dit que a et b sont premiers entre eux si leur
pgcd vaut 1.

2

2.1

Nombres
premiers,
th´
eor`
eme de B´
ezout

pgcd,


ecomposition en nombres premiers

Lien avec la d´
ecomposition en nombres premiers
Si a = pα1 1 pα2 2 . . . pαk k et b = ±pβ1 1 pβ2 2 . . . pβk k , alors
a ∧ b = pγ11 pγ22 . . . pγkk
a ∨ b = pδ11 pδ22 . . . pδkk

o`
u γi = min(αi , βi ) et δi = max(αi , βi ).

efinition : Un nombre premier est un nombre
entier diff´erent de ±1 qui n’est divisible que par Propri´
et´
es
1 et par lui-mˆeme. Exemples : 2, 3, 5, 7, 11, 13,
- (a ∧ b) × (a ∨ b) = ab. En particulier si a et
17 . . . On note P l’ensemble des nombres premiers,
b sont premiers entre eux, a ∨ b = ab.
cet ensemble est infini (th´eor`eme d’Euclide).
- a ∧ b = b ∧ a, a ∧ (b ∧ c) = (a ∧ b) ∧ c.
Th´
eor`
eme (R´epartition des nombres premiers).
- 0 ∧ a = a, a ∧ a = a, 1 ∧ a = 1.
Si on note π(x) le nombre de nombres premiers
- Si x | a et x | b, alors x | (a ∧ b).
x
, c’est-`
a-dire
inf´erieurs `
a x, alors π(x) ∼ ln(x)
- Si a | x et b | x, alors (a ∨ b) | x.
x
π(x)/ ln(x)
→x→∞ 1.
- ma∧mb = m(a∧b). En particulier, si a∧b =
d, alors d | a, d | b, et (a/d) ∧ (b/d) = 1.
Informellement, autour d’un grand nombre n en- Pour tout entier k, a ∧ b = a ∧ (b + ak)
viron un entier sur ln(n) est premier.
Lemme de Gauss

ecomposition en nombre premier
Si a | bc et a ∧ b = 1, alors a | c.
Tout nombre entier n peut se d´ecomposer en facteurs premiers : n = ±pα1 1 pα2 2 . . . pαk k , pi ∈ P. Algorithme d’Euclide : pour calculer le pgcd
Cette ´ecriture est unique `a permutation des fac- de deux entiers a et b,
1. si a < b, ´echanger a et b ;
teurs premiers pr`es.
2

IUT d’Orsay
D´epartement d’informatique

Cryptographie – S4 PEC

2. faire la division euclidienne de a par b :
a = bq + r ;
3. si r = 0, le pgcd est ´egal `a b, sinon, remplacer a par b, b par r et retourner `a l’´etape
2.

2.3

Th´
eor`
eme de B´
ezout et applications

Th´
eor`
eme de B´
ezout :
Deux entiers a et b sont premiers entre eux si et
seulement si il existe deux entiers u et v tels que
au + bv = 1.
Plus g´en´eralement, si a∧b = d, alors il existe deux
entiers u et v tels que au + bv = d.

1. On calcule d = a ∧ b par l’algorithme d’Euclide. Si d - c, l’´equation n’a pas de solution ;
sinon, en divisant par d on obtient l’´equation
´equivalente a0 x + b0 y = c0 o`
u a0 = a/d,
0
0
b = b/d, c = c/d (en particulier a0 ∧ b0 = 1).
2. D’apr`es le th´eor`eme de B´ezout il existe deux
entiers u et v tels que a0 u + b0 v = 1 ; on les
calcule par l’algorithme d’Euclide ´etendu.
3. L’ensemble des solutions est alors {(c0 u +
kb0 , c0 v − ka0 ) ; k ∈ Z}.
Entiers inversibles modulo n
Un entier a est inversible modulo n si et seulement
si il existe un entier b tel que ab ≡ 1 [n]. Cet entier b, s’il existe, est unique modulo n et s’appelle
inverse modulaire de a ; on note b ≡ a−1 [n].

et´
e
Algorithme d’Euclide ´
etendu : pour calculer Propri´
u et v, on utilise l’algorithme d’Euclide ´etendu : Un entier a est inversible modulo n si et seulement si a et n sont premiers entre eux. A l’aide de
1. On effectue les divisions successives comme
l’algorithme d’Euclide ´etendu, on calcule les coefdans l’algorithme d’Euclide. On note
ficients de B´ezout u et v tels que au + nv = 1.
r0 , r1 , . . . , rm et q1 , q2 , . . . , qm−1 les restes
Alors a−1 ≡ u [n].
et les quotients successifs, avec a = r0 et
b = r1 :
Chiffrement El Gamal :
a = q1 b+r2 ,
...

b = q2 r2 +r3 ,

r2 = q3 r3 +r4 ,

rm−2 = qm−1 rm−1 + rm

Le dernier reste non nul rm est ´egal au pgcd
d de a et b.
2. On calcule par r´ecurrence une s´erie d’´egalit´e
de la forme d = uk rk−1 + vk rk , en partant de
l’´egalit´e d = rm = rm−2 − qm−1 rm−1 (c’est`a-dire um−1 = 1 et vm−1 = −qm−1 ) :
si d = uk+1 rk + vk+1 rk+1 , comme rk−1 =
qk rk + rk+1 , en rempla¸cant rk+1 on obtient
d = uk+1 rk + vk+1 (rk−1 − qk rk ) =
vk+1 rk−1 + (uk+1 − qk vk+1 ) rk .
On a donc
(
uk = vk+1
vk = uk+1 − qk vk+1

1. Alice choisit un modulo N (de pr´ef´erence un
grand nombre premier) et deux entiers g et
s, et elle calcule h ≡ g s [N ].
2. Alice rend public N , g et h (sa cl´e publique)
et garde secret s (sa cl´e priv´ee).
3. Pour envoyer un message chiffr´e m, Bob
choisit un entier al´eatoire r, calcule c1 ≡
g r [N ] et c2 ≡ hr .m [N ], et envoie (c1 , c2 )
`a Alice.
4. Pour d´echiffrer le message re¸cu (c1 , c2 ),
Alice calcule (cs1 )−1 .c2 ≡ ((g r )s )−1 .hr .m ≡
(g rs )−1 .g sr .m ≡ m [N ].
Un attaquant passif qui ´ecoute les ´echanges ne
peut pas retrouver facilement r ou s (probl`eme
du log discret), et ne peut alors pas calculer m.
Ce cryptosyst`eme ne fonctionne correctement que
si l’entier r est choisi suffisamment al´eatoirement.

3. On remonte ainsi jusqu’`a trouver d = u1 r0 +
v1 r1 = u1 a + v1 b.
2.4 Th´
eor`
eme des restes chinois et applications.
Applications aux ´
equations diophan´
tiennes : Etant donn´es trois entiers a, b et c, on
eor`
eme des restes chinois : Soient m et n
veut d´eterminer tous les couples d’entiers (x, y) Th´
deux entiers premiers entre eux, et a et b deux ensolutions de l’´equation ax + by = c.
IUT d’Orsay
D´epartement d’informatique

3


esum´
e de cours

tiers quelconques. Alors le syst`eme de congruences 3.2
(
x ≡ a [m]
x ≡ b [n]

Le syst`
eme RSA

La s´ecurit´e de ce syst`eme repose sur la difficult´e de
calculer des “racines e-i`emes modulaires” : ´etant
donn´es des entiers e, n et a, trouver un entier x tel
que xe ≡ a [n]. On ne sait r´esoudre efficacement
ce probl`eme que quand la factorisation de n est
connue.

admet une solution x, unique modulo mn.
En particulier, si x ≡ y [m] et x ≡ y [n], alors

en´
eration des cl´
es : Alice choisit deux grands
x ≡ y [mn].
nombres premiers p et q et calcule leur produit

esolution pratique : `a l’aide de l’algorithme n = pq. Elle choisit un entier e premier avec
d’Euclide ´etendu, on calcule les coefficients de (p − 1)(q − 1) et calcule avec Euclide ´etendu son
B´ezout u et v tels que mu + nv = 1. Alors inverse d modulo (p − 1)(q − 1). Alice publie (n, e)
x ≡ bmu + anv [mn].
(la cl´e publique) et garde secret d (la cl´e priv´ee).
Utilisation en confidentialit´
e (chiffrement) :

3
3.1

Th´
eor`
eme de Fermat et RSA
Le petit th´
eor`
eme de Fermat

1. Pour transmettre un message m `a Alice,
Bob r´ecup`ere sa cl´e publique (n, e), calcule
c ≡ me [n] et envoie le message chiffr´e c `
a
Alice.
2. Pour d´echiffrer le message re¸cu c, Alice calcule m0 ≡ cd [n].

On v´erifie qu’on a bien m0 ≡ m [n] :
Petit th´
eor`
eme de Fermat : Soit p un nombre
Comme on a de = 1 + k(p − 1)(q − 1), modulo
premier. Alors pour tout entier a, ap ≡ a [p].
p on trouve que m0 ≡ (me )d ≡ m1+k(p−1)(q−1) ≡
De fa¸con ´equivalente, si a 6≡ 0 [p], alors ap−1 ≡
m × (mp−1 )k(q−1) ≡ m [p] avec le petit th´eor`eme
1 [p].
de Fermat, et on trouve de mˆeme que m ≡ m0 [q] ;
comme p et q sont premiers entre eux, le th´eor`eme
Application `
a la primalit´
e
0
On peut se servir de ce th´eor`eme comme test de des restes chinois implique que m ≡ m [n].
primalit´e : pour v´erifer si un nombre n est preUtilisation en authentification (signature) :
mier ou pas, on teste pour plusieurs entiers a si
1. Pour authentifier un message m, Alice calan ≡ a[n]. En cas d’´echec, on sait que n n’est
cule sa signature s ≡ md [n] et envoie (m, s)
pas premier, sinon n est probablement (mais pas
`a Bob.

urement) premier.
Cons´equence : prouver qu’un nombre n’est pas
2. Pour s’assurer que le message re¸cu (m, s) a
premier est beaucoup plus facile que de factoriser
bien ´et´e envoy´e par Alice, Bob r´ecup`ere sa
un nombre.
cl´e publique (n, e) et v´erifie que m ≡ se [n].

4

IUT d’Orsay
D´epartement d’informatique


Resume_Cours.pdf - page 1/4
Resume_Cours.pdf - page 2/4
Resume_Cours.pdf - page 3/4
Resume_Cours.pdf - page 4/4

Documents similaires


Fichier PDF 60
Fichier PDF exercices algorithmiques 2 corriges
Fichier PDF correctiontd2
Fichier PDF tp info
Fichier PDF coursnombrespremiersetppcm
Fichier PDF examen de rattrapage


Sur le même sujet..