Introduction à la Cryptologie Cryptographie - Objets - PolSys

Introduction a` la Cryptologie
´
Cryptographie - Objets Mathematiques
de Base
´ el
¨ Renault
Guena
POLSYS LIP6/UPMC/INRIA
22 janvier 2014
Part I
´
Definitions
UPMC - Licence Info - Crypto - 2012/13
2/71
La cryptologie
´
Definitions
La cryptologie est la science du secret. Elle se divise en deux
disciplines :
´
La cryptographie qui est l’etude
des algorithmes permettant de
´
´
proteger
(cacher) de l’information. Ces algorithmes sont appeles
`
cryptosystemes
;
´
´
la cryptanalyse qui est l’etude
du niveau de securit
e´ des
`
cryptosystemes
fournis par les cryptographes.
` partie du cours
Premiere
´
`
On s’interesse
au probleme
de confidentialite´ (chiffrer des
nessages)
ˆ
´
La cle´ est la meme
pour chiffrer et dechiffrer
UPMC - Licence Info - Crypto - 2012/13
3/71
Terminologie et principe de base de la cryptologie
Terminologie
Chiffrer : l’action de rendre un message clair M (plaintext) en un
´ illisible.
message C appele´ cryptogramme ou message chiffre,
´
Dechiffrer
: Action inverse du chiffrement.
`
Cryptosysteme
: L’algorithme (ou le dispositif physique) permettant de
´
chiffrer des donnees.
´
`
Attaquer, Casser : Mettre a` mal la securit
e´ d’un cryptosysteme
´ retrouver la cle).
´
(retrouver M a` partir de C sans connaˆıtre la cle,
Principe de Kerckhoffs (Journal des sciences militaires, 1883)
´
`
La securit
e´ d’un cryptosysteme
ne doit reposer que sur le secret de la
clef. En particulier un attaquant est suppose´ connaˆıtre le
`
`
cryptosysteme
(Les cryptosystemes
militaires, vus comme des
dispositifs physiques, peuvent tomber aux mains de l’ennemi).
´
`
´ par la cryptanalyse.
+La securit
e´ d’un cryptosysteme
est attestee
UPMC - Licence Info - Crypto - 2012/13
4/71
´
´
Cryptographie symetrique
: Modelisation
´
Definition
`
´
´ si pour chiffrer et
Un cryptosysteme
est dit symetrique
(ou a` cle´ privee)
´
ˆ
` est utilisee.
´
dechiffrer,
la meme
cle´ secrete
`
Cryptosysteme
´
P et C les alphabets pour ecrire
les messages clairs et les
´ respectivement.
messages chiffres
´ possibles.
K l’ensemble des cles
´
Pour tout K ∈ K on peut definir
deux applications eK : P → C et
dK : C → P telles que dK (eK (x)) = x pour tout x ∈ P.
ˆ
´ de symboles uniques ou de
+les alphabets peuvent etre
composes
`
blocs de symboles. Pour commencer on s’en tiendra aux caracteres
de l’alphabet usuel.
UPMC - Licence Info - Crypto - 2012/13
5/71
´
La cryptographie symetrique
en pratique
`
´
ˆ
´
Cryptosysteme
symetrique
(la meme
cle´ K pour de/chiffrer)
´
P et C les alphabets clairs et chiffres.
´ possibles.
K l’ensemble des cles
K ∈ K : eK : P → C et dK : C → P avec ∀x ∈ P dK (eK (x)) = x.
´
`
Les applications eK et dK necessitent
la connaissance complete
ˆ
´
de K pour etre
definies.
En pratique : chiffrer avec la cle´ K
`
Pour chiffrer un texte P clair on procede
comme suit
1
´
´ ements
´
On decoupe
P en blocs correspondant aux el
de P
2
On applique eK sur chacun des blocs de P
3
´
On obtient ainsi C un message correspondant a` P et ecrit
a` l’aide
de C.
UPMC - Licence Info - Crypto - 2012/13
6/71
´
La cryptographie symetrique
en pratique
`
´
ˆ
´
Cryptosysteme
symetrique
(la meme
cle´ K pour de/chiffrer)
´
P et C les alphabets clairs et chiffres.
´ possibles.
K l’ensemble des cles
K ∈ K : eK : P → C et dK : C → P avec ∀x ∈ P dK (eK (x)) = x.
´
`
Les applications eK et dK necessitent
la connaissance complete
ˆ
´
de K pour etre
definies.
´
En pratique : dechiffrer
avec la cle´ K
´
`
Pour dechiffrer
le texte C on procede
comme suit
1
´
´ ements
´
On decoupe
C en blocs correspondant aux el
de C
2
3
On applique dK sur chacun des blocs de C
On obtient ainsi P le clair de a` C.
UPMC - Licence Info - Crypto - 2012/13
6/71
Chiffrement de messages en pratique
´
+Decoupage
par blocs de P
Texte clair en blocks
P
eK
P
eK
C
C
Texte chiffré en blocks
UPMC - Licence Info - Crypto - 2012/13
P
eK
C
P
...
C
...
eK
7/71
Part II
´
Cryptographie Mono-alphabetique
UPMC - Licence Info - Crypto - 2012/13
8/71
´
Chiffrement par Substitution ou Mono-alphabetique
´
Definition
´ ement
´
´ ement
´
A` chaque el
de P correspond un unique el
de C.
´ est different
´
´
+Un exemple ou` l’alphabet d’arrivee
de celui de depart
Le chiffrement des Francs-Mac¸ons .
UPMC - Licence Info - Crypto - 2012/13
9/71
´
Chiffrement par Substitution ou Mono-alphabetique
´
Definition
´ ement
´
´ ement
´
A` chaque el
de P correspond un unique el
de C.
`
Cryptosysteme
par substitution
´
ˆ
P, C sont differents
(de meme
cardinal)
K est l’ensemble des bijections de P dans C.
Pour tout K ∈ K on a
eK (x) = K(x)
dK (y) = K −1 (x)
UPMC - Licence Info - Crypto - 2012/13
9/71
´
Chiffrement par Substitution ou Mono-alphabetique
´
Definition
´ ement
´
´ ement
´
A` chaque el
de P correspond un unique el
de C.
+On prend les alphabets canoniques P = C = {A, . . . , Z} mais dans
´
ce cas il faut melanger
cet alphabet.
`
Cryptosysteme
par substitution sur alphabets identiques
´
P, C sont tous les deux egaux
a` A = {A, . . . , Z}
K est l’ensemble des permutations de P dans C.
Pour tout K ∈ K on a
eK (x) = K(x)
dK (y) = K −1 (x)
UPMC - Licence Info - Crypto - 2012/13
9/71
´
Structures Mathematiques
: Groupes
Groupe (G, ?)
Associativite´ : ∀(a, b, c) ∈ G × G × G, a ? (b ? c) = (a ? b) ? c
´ ement
´
Neutre : il existe un el
e neutre pour ?, i.e.
∀a ∈ G, a ? e = e ? a = a
Inverse : ∀a ∈ G, ∃b ∈ G |
a?b=b?a=e
+Le groupe est dit Commutatif si de plus ∀(a, b) ∈ G × G,
a?b = b?a
Exemples
L’ensemble Z des entiers muni de l’addition (commutatif)
L’ensemble Q \ {0} muni de la multiplication (commutatif)
L’ensemble Perm(E) des permutations d’un ensemble fini E muni
de la composition (non commutatif).

´
´
Avoir a` l’esprit quelle est l’operation
du groupe ! Parfois, l’operation
est implicite, par exemple Z/nZ est canoniquement un groupe additif.
UPMC - Licence Info - Crypto - 2012/13
10/71
Groupes et Chiffrement par Substitution
Chiffrement par Substitution
´ ement
´
´ ement
´
A` chaque el
de P correspond un unique el
de C.
´
Si on choisit de numeroter
les lettres de l’alphabet de 0 a` 25 on aura
´
alors la modelisation
:
P = C = {0, . . . , 25}
K = Perm({0, . . . , 25})
σ ∈ K, eK = σ et dK = σ −1
UPMC - Licence Info - Crypto - 2012/13
11/71
´
Cas particulier : Cesar
´ forment un sous-groupe de Perm(P), celui des rotations .
+Les cles
´
Definition
sous-groupe
Soit (G, ?) un groupe fini. Un ensemble H contenu dans G est un
ˆ
sous-groupe (de G) s’il est lui meme
un groupe pour ?.
UPMC - Licence Info - Crypto - 2012/13
12/71
´
Cas particulier : Cesar
´ forment un sous-groupe de Perm(P), celui des rotations .
+Les cles
´
Definition
sous-groupe
Soit (G, ?) un groupe fini. Un ensemble H contenu dans G est un
ˆ
sous-groupe (de G) s’il est lui meme
un groupe pour ?.
UPMC - Licence Info - Crypto - 2012/13
12/71
´
Cas particulier : Cesar
´ forment un sous-groupe de Perm(P), celui des rotations .
+Les cles
´
+Arithmetique
modulaire !
´
Chiffrement de Cesar
: modulaire
P = C = Z/26Z
K = {0, . . . , 25}
ρ ∈ K, eK : p 7→ p + ρ mod 26 et dK : c 7→ c − ρ mod 26
UPMC - Licence Info - Crypto - 2012/13
12/71
´
Cas particulier : Cesar
´
Chiffrement de Cesar
: modulaire
P = C = Z/26Z
K = {0, . . . , 25}
ρ ∈ K, eK : p 7→ p + ρ mod 26 et dK : c 7→ c − ρ mod 26
Exemple ρ = 13 ⇒ 13 = −13 mod 26
UPMC - Licence Info - Crypto - 2012/13
12/71
´
´ es
´
Chiffrement de Cesar
: propriet
ˆ
´
+Une rotation de Perm({0, . . . , 25}) peut etre
definie
comme la
composition de plusieurs fois la rotation de longueur 1.
´
`
Definition
: Groupe cyclique (ou monogene)
ˆ
´ ement
´
C’est un groupe (G, ?) qui peut etre
engendre´ par un el
:
∃g ∈ G tq ∀a ∈ G a = g ? g ? · · · ? g
´ e´ sous la forme G = hgi.
On peut noter cette propriet
+Le sous-groupe de Perm({0, . . . , 25}) des rotations est cyclique.
UPMC - Licence Info - Crypto - 2012/13
13/71
Chiffrement affine
+En utilisant l’encodage habituel, on se place directement dans un
alphabet de la forme Z/nZ (ici n = 26).
`
Cryptosysteme
affine
´
P, C sont tous les deux egaux
a` Z/26Z
K est un sous ensemble de Z/26Z × Z/26Z tel que
Pour tout K = (a, b) ∈ K on a
eK (x) = ax + b mod 26
et il existe une fonction dK : C → P inverse de eK .
+K forme ici aussi un sous-groupe de Perm({0, ldots, 25}).
`
Probleme
´
´ possibles ? Ceci revient a`
Comment determiner
l’ensemble des cles
´
`
determiner
les fonction eK qui possedent
une fonction inverse.
´
´
+Ici il y a deux operations,
besoin de structures mathematiques
plus
riches que celle de groupe, en particulier de savoir inverser.
UPMC - Licence Info - Crypto - 2012/13
14/71
Part III
´
Structures Algebriques
de Base
UPMC - Licence Info - Crypto - 2012/13
15/71
´
Objets Mathematiques
Support de la Cryptographie
Groupe, Anneau, Corps...
´
Arithmetique
dans Z...
´ Nombres premiers...
Divisibilite,
...
UPMC - Licence Info - Crypto - 2012/13
16/71
´
Structures de base : Definitions
Anneau commutatif (A, ?, ◦)
´
Groupe commutatif pour l’operation
?
´ ement
´
Associativite´ et existence d’un el
neutre pour ◦
Distributivite´ par rapport a` ? :
∀(a, b, c) ∈ A3 , c ◦ (a ? b) = c ◦ b ? c ◦ a
´
Commutativite´ de la seconde operation
Exemples
L’anneau Z muni de l’addition (groupe) et de la multiplication.
ˆ
´
L’anneau des fractions Q avec les memes
operations
+Dans la suite, tous les anneaux seront commutatifs et munis de
´ ement
´
l’addition de la multiplication . L’el
neutre pour l’addition est 0 et
1 pour la multiplication.
UPMC - Licence Info - Crypto - 2012/13
17/71
´
Structures de base : Definitions
Sous-****
Un sous ensemble U d’un groupe G (resp. anneau) est un
ˆ
sous-groupe (resp. sous-anneau) de G (resp. A) s’il est lui meme
un
´
groupe (resp. anneau) pour les operations
de G (resp. A).
Exemple
L’anneau Z muni de l’addition (groupe) et de la multiplication est
en fait un sous-anneau de Q.
UPMC - Licence Info - Crypto - 2012/13
18/71
Divisibilite´ dans un anneau (A, +, ×)
Diviseur, Multiples
´ ement
´
Un el
a est un diviseur de b dans un anneau A s’il existe c ∈ A tel
que b = ac. On note alors a | b et b est appele´ multiple de a.
+L’ensemble des multiples de a dans A est note´ aA = {ak : k ∈ A}
´
´
´
+L’arithmetique
= etude
de la divisibilite.
+6 et −6 divisent 12 dans Z.
ˆ
si a est un entier divisant b ∈ Z alors il en est de meme
pour −a. Ceci
vient du fait que −1 est inversible dans Z.
´
´
+On ne s’interesse
donc qu’au cas positif (classes d’equivalence
modulo la multiplication par un inverse)
UPMC - Licence Info - Crypto - 2012/13
19/71
Inversibilite´ dans un anneau (A, +, ×)
Inversibles
´ ement
´
Une el
a d’un anneau A est dit inversible s’il existe b ∈ A tel que
´ ement
´
ab = 1. L’el
b est appele´ inverse de a. L’ensemble des inversibles
d’un anneau A sera note´ A× (ou aussi U(A)).
+A× forme un groupe commutatif dans A pour la multiplication.
ˆ
`
+La divisibilite´ peut etre
vue a un inverse pres.
Association
´ ement
´
Pour a ∈ A nous appelons associe´ a` a tout el
b de la forme
×
b = ua avec u ∈ A et nous noterons b ≡ a.
+Pour A = Z nous avons A× = {1, −1}
´ de a sont {a, −a}
+Pour A = Z les associes
+Pour A = Z on choisira le positif
UPMC - Licence Info - Crypto - 2012/13
20/71
´
Integrit
e´
´ eral,
´
´ ements
´
Dans un cadre gen
certains el
d’un anneau A peuvent
´
´ un obstacle a` l’arithmetique.
´
´ ements
´
represent
es
Ces el
sont les
diviseurs de 0.
´ et anneau Integre
`
Diviseur de zero
´ ement
´
Un el
a 6= 0 ∈ A est diviseur de 0 s’il existe b 6= 0 ∈ A tel que
`
ab = 0. Un anneau A est dit integre
s’il n’existe pas de diviseur de 0
dans A.
`
L’anneau Z est integre
mais nous rencontrerons plus tard des anneaux
´
qui ne le seront pas, les exemples les plus simples etant
ceux
construits par quotient de Z.
UPMC - Licence Info - Crypto - 2012/13
21/71
Division euclidienne
´
´
La division euclidienne represente
un moyen pratique pour etudier
la
divisibilite´ d’un anneau.
Anneau euclidien
`
´
Un anneau integre
A est dit euclidien si on peut l’equiper
d’une
application d : A → N ∪ {−∞} telle que pour tout couple (a, b) ∈ A2
avec b 6= 0, il existe q et r dans A tel que
a = qb + r avec d(r) < d(b).
` relation etant
´
´ division euclidienne de a par b,
Cette derniere
appelee
´ ement
´
l’el
q le quotient et r le reste de cette division.
+Pour A = Z nous choisissons d : x 7→ |x|
´
+a | b est equivalent
a` b = qa + r avec r = 0
´ pour A = Z on prendra comme convention r > 0
+Non unicite,
UPMC - Licence Info - Crypto - 2012/13
22/71
Division euclidienne
Dans le langage C, la division euclidienne sur les entiers est obtenue
´
´
´
en utilisant les operateurs
arithmetiques
binaires / et % qui definissent
respectivement le quotient et le reste de la division de deux entiers.

` la norme ANSI, le resultat
´
D’apres
correspondra a` la convention
´
´
decrite plus haut (i.e. reste positif ou nul) lorsque les operandes
sont
ˆ
´
eux-memes
positifs . Dans le cas contraire le resultat
n’est pas
´ e´ .
specifi
´
ˆ
´
+En particulier le resultat
de (3-14) % 26 peut etre
negatifs
!
´
+Si on divise par 0, le resultat
n’a pas de sens
UPMC - Licence Info - Crypto - 2012/13
23/71
´
´
Irreductibilit
e´ et Decomposition
´ ements
´
+Les el
”minimaux” pour la divisibilite´
´
Irreductible
´ ement
´
´
Un el
p d’un anneau A est irreductible
s’il est ni nul ni inversible
` : 1 et p.
et s’il a exactement deux diviseurs (a` association pres)
´
´
+On veut pouvoir decomposer
selon ces irreductibles
(briques de
base)
Anneau factoriel
`
´
Un anneau A est dit factoriel s’il est integre
et qu’il verifie
les deux
conditions suivantes :
´ ement
´
existence d’une factorisation : tout el
a 6= 0 de A qui n’est
ˆ
´
pas inversible peut etre
ecrit
sous la forme d’un produit p1 p2 · · · pn
´ ements
´
´
d’el
irreductibles
;
´
unicite´ de la factorisation : cette decomposition
est unique a`
` des facteurs irreductibles.
´
association et ordre pres
UPMC - Licence Info - Crypto - 2012/13
24/71
´ emes
`
Theor
fondamentaux
´
Thm. fondamental de l’arithmetique
L’anneau Z est factoriel.
´ eralis
´
Thm. fondamental gen
e´
Un anneau euclidien est factoriel.
UPMC - Licence Info - Crypto - 2012/13
25/71
´ eme
`
Theor
fondamental dans Z
Premiers
´ ement
´
Un el
a d’un anneau A est dit premier s’il est ni nul ni inversible
´
´ e´ suivante :
et s’il verifie
la propriet
p | ab ⇒ p | a ou p | b.
Factoriel et premiers
´ d’etre
ˆ
´
Dans un anneau factoriel les qualites
premier et irreductible
co¨ıncident.
´
´
+Montrer l’equivalence
entre premier et irreductible
va nous permettre
` factoriel de Z.
de montrer le caractere
+Par association on se limite aux entiers naturels (i.e. les entiers
positifs)
UPMC - Licence Info - Crypto - 2012/13
26/71
´ eme
`
Theor
fondamental dans Z
´
Existence de la decomposition
´
´ e´
Tout entier n > 1 verifie
la propriet
´
P(n) : n est le produit de nombres irreductibles.
Preuve :
´
On commence par montrer que a > 1 est irreductible
ssi il n’est pas le
produit de deux entiers > 1. Ensuite, on montre cette existence de
´
´
decomposition
par recurrence
forte sur n :
´
On montre que 2 est irreductible.
´
Pour n > 2 on decompose
n et on applique h.r.
UPMC - Licence Info - Crypto - 2012/13
27/71
´ eme
`
Theor
fondamental dans Z
´
+Pour montrer l’unicite´ de la decomposition
nous montrons
´
l’equivalence
qui suit
´
Premier = Irreductible
dans Z
´
Tout nombre entier > 1 est irreductible
ssi il est premier.
Preuve : Il faut utiliser la division euclidienne !
´
` ici la notion usuelle de nombre premier (vue au college,
`
+On recup
ere
´ etc)
lycee,
UPMC - Licence Info - Crypto - 2012/13
28/71
´ eme
`
Theor
fondamental dans Z
´
Unicite´ de la decomposition
dans Z
´
´
La decomposition
de n > 1 se decompose
sous la forme d’un produit
´
` unique .
de nombres irreductibles
(premiers) de maniere
Preuve :
ms
1
p1n1 · · · pnk k = n = qm
1 · · · qk
´
ou` les pi et les qj sont des nombres irreductibles.
` le resultat
´
´ edent,
´
D’apres
prec
pour i1 fixe´ il existe un entier j1 tel que
ˆ
raisonnement sur le quotient de n par pi1
pi1 = qj1 . En utilisant le meme
´
on obtient de proche en proche le fait que la decomposition
est unique.
´
´ eme
`
Ceci termine la demonstration
du theor
fondamental dans Z.
UPMC - Licence Info - Crypto - 2012/13
29/71
Les nombres premiers
´
+Les nombres irreductibles
sont les nombres premiers !
´ eral
´ est celle d’irreductible.
´
+La ” vraie” notion a` retenir en gen
´
´
+Important de connaˆıtre les irreductibles
car ils definissent
tous les
´ ements.
´
el
+Quel est le nombre de nombres premiers ?
Infinite´ des nombres premiers
L’ensemble des nombres premiers est infini.
Preuve Euclide :
Par l’absurde.
´
On utilise la factorisation pour refuter.
Preuve Constructive :
` un ensemble fini de nombres premiers.
On considere
On construit un nouveau nombre premier par factorisation.
UPMC - Licence Info - Crypto - 2012/13
30/71
Les nombres premiers
+Comment reconnaˆıtre un nombre premier ?
Lem.
Un entier n > 1 est premier ssi il n’est divisible par aucun entier
√
compris entre 2 et n.
#include<stdio.h>
#include<math.h>
int main() {
int p,d,r;
printf("Entrer un entier >2 a tester : ");
scanf("%d",&p);
d=1;
do{
d+=1;
r= p % d;
}while(r!=0 && d < sqrt((double)p));
if (r == 0)
printf("\nL’entier %d n’est pas premier.\n
Il est divisible par %d.\n",p,d);
else
printf("\nL’entier %d est premier.\n",p);
return 0;
}
UPMC - Licence Info - Crypto - 2012/13
31/71
Les nombres premiers, la factorisation
+Comment reconnaˆıtre un nombre premier ?
La complexite´ de ce programme est de l’ordre de
√
p.
Agrawal, Kayal et Saxena (2002) donnent un algorithme de
´ non probabiliste et
complexite´ polynomiale en la taille de l’entree
´
independant
de toute conjecture.
Le meilleur logiciel connu est FastECPP de F. Morain (base´ sur
les courbes elliptiques).
+Comment factoriser un nombre entier ?
C’est beaucoup plus dur !
`
´
Des cryptosystemes
reposent sur cette difficulte.
Des algorithmes de complexite´ sous-exponentielle existent
(MPQS, NFS).
UPMC - Licence Info - Crypto - 2012/13
32/71
Part IV
´
´ eme
`
Relation d’equivalence,
Theor
de
Lagrange
UPMC - Licence Info - Crypto - 2012/13
33/71
´
Relation d’equivalence
´
Une relation binaire R d’un ensemble E est une relation d’equivalence
´
´ es
´ suivantes
lorsqu’elle verifie
les trois propriet
´
´ ement
´
ˆ
R est reflexive
: tout el
de E peut etre
mis en relation avec
ˆ
lui meme
(∀x ∈ E, xRx)
´
´ ement
´
ˆ
R est symetrique
: tout el
de E peut etre
mis en relation
´ ements
´
avec les el
qui lui sont relatifs (∀(x, y) ∈ E2 , xRy ⇒ yRx)
R est transitive : une relation d’une relation est une relation
(∀(x, y, z) ∈ E3 , xRy ∧ yRz ⇒ xRz)
´ ements
´
´
Deux el
de E qui sont mis en relation par R sont dits associes
´
´ ement
´
ou equivalents
pour cette relation. Soit x un el
de E, le sous
´ ements
´
´ pour R est
ensemble de E forme´ des el
de E qui sont associes
´
appele´ classe d’equivalence
.
UPMC - Licence Info - Crypto - 2012/13
34/71
´
Relation d’equivalence
Exemple 1 : la relation d’association
Soit a, b ∈ A un anneau commutatif. On note aA l’ensemble des
multiples de a dans A. aRb ⇔ aA = bA
aA = aA clair
aA = bA ⇒ bA = aA clair
aA = bA et bA = cA ⇒ aA = cA clair
´
Provient du fait que = est une relation d’equivalence.
On peut montrer
´
que aA = bA est equivalent
a` l’assertion : ∃u inversible dans A tq
a = ub.
´
´
Dans Z les differentes
classes d’equivalence
seront alors
{−0, 0}, {−1, 1}, {−2, 2}, . . ..
UPMC - Licence Info - Crypto - 2012/13
35/71
´
Relation d’equivalence
` important)
Exemple 2 : Z/nZ (tres
Soit a, b ∈ Z et n un entier positif. aRn b ⇔ a − b ∈ nZ
a−a=n×0
a − b ∈ nZ ⇒ b − a ∈ (−1) × nZ = nZ
a − b ∈ nZ et b − c ∈ nZ ⇒ (a − b) + (b − c) ∈ nZ
´ ements
´
ˆ
ˆ
+Les el
d’une meme
classe ont le meme
reste modulo n
(exercice : le montrer)
+On choisit le plus petit entier positif de la classe (les classes sont
´
´ par {0, 1, . . . , n − 1}).
donc represent
ees
UPMC - Licence Info - Crypto - 2012/13
36/71
´
Relation d’equivalence
´ e´ de partitionnement
Propriet
´
Soit E un ensemble et R une relation d’equivalence
sur E. L’ensemble
´
des classes d’equivalence
pour R forme une partition de E.
´ en exercice. Idee
´ imagee
´ :
+Preuve laissee
E
=
b∈E
tq
a1 Rb
UPMC - Licence Info - Crypto - 2012/13
∪
b∈E
tq
a2 Rb
∪ · · ·∪
b∈E
tq
ak Rb
···
37/71
´
´ eme
`
Relation d’equivalence
: application au theor
de
Lagrange
´ eme
`
Theor
de Lagrange
Soit (G, ×) un groupe fini et H un sous-groupe de G. Alors le cardinal
de H est un diviseur du cardinal de G . (Le cardinal d’un groupe est
aussi appele´ ordre.)
´
`
Mathematicien
Franc¸ais de la fin du 18eme
`
´
´ sur les
siecle.
Il developpe
les idees
´
groupes (sans que la definition
soit
´
clairement etablie)
de permutations pour
´
´
etudier
les solutions des equations
polynomiales.
UPMC - Licence Info - Crypto - 2012/13
38/71
´
´ eme
`
Relation d’equivalence
: application au theor
de
Lagrange
´ eme
`
Theor
de Lagrange
Soit (G, ×) un groupe fini et H un sous-groupe de G. Alors le cardinal
de H est un diviseur du cardinal de G . (Le cardinal d’un groupe est
aussi appele´ ordre.)
´
Demonstration
´
´
Considerer
la relation d’equivalence
xRH y ⇔ xy−1 ∈ H
On partitionne le groupe G selon les classes de RH
´
On etablie
une application bijective entre les classes
´
d’equivalence.
´ par
Pour le dernier point, il suffit de voir que la classe de x est donnee
−1
´
Hx et que la bijection de G dans G definie par y 7→ yx envoie les
´ ements
´
´ ements
´
el
de H, la classe de l’unite´ e, sur les el
de la classe de
x.
UPMC - Licence Info - Crypto - 2012/13
38/71
´
´ eme
`
Relation d’equivalence
: application au theor
de
Lagrange
´ eme
`
Theor
de Lagrange
Soit (G, ×) un groupe fini et H un sous-groupe de G. Alors le cardinal
de H est un diviseur du cardinal de G . (Le cardinal d’un groupe est
aussi appele´ ordre.)
´
Definition
: Ordre
´ ement
´
Soit g un el
d’un groupe (G, ?). On appelle ordre de g le plus
petit entier strictement positif k tel que
g ? g ? ··· ? g = e
|
{z
}
k fois
´
+Soit g ∈ G on peut considerer
le sous-groupe cyclique de G
´
engendre´ par g. Le cardinal de ce sous-groupe est clairement egal
a`
` Lagrange. Voici une
l’ordre de g. Il divisera le cardinal de G d’apres
raison
pour
on nomme ordre le cardinal d’un groupe.
UPMC - Licence
Infolaquelle
- Crypto - 2012/13
39/71
´
´ eme
`
Relation d’equivalence
: application au theor
de
Lagrange
´ eme
`
Theor
de Lagrange
Soit (G, ×) un groupe fini et H un sous-groupe de G. Alors le cardinal
de H est un diviseur du cardinal de G . (Le cardinal d’un groupe est
aussi appele´ ordre.)
´
Definition
: Ordre
´ ement
´
Soit g un el
d’un groupe (G, ?). On appelle ordre de g le plus
petit entier strictement positif k tel que
g ? g ? ··· ? g = e
|
{z
}
k fois
Corollaire
Tout groupe (G, ?) d’ordre un nombre premier est cyclique .
UPMC - Licence Info - Crypto - 2012/13
39/71
Part V
PGCD
UPMC - Licence Info - Crypto - 2012/13
40/71
Valuation p-adic
´
Soit A un anneau factoriel et P un ensemble de representants
pour
´
chacune des classes d’irreductibles
de A selon la relation
´
d’equivalence
xRy ⇔ ∃u ∈ A× tq x = uy (relation d’association).
´
Decomposition
unique
Pour a ∈ A non nul on a
a=u
Y
pvp (a)
p∈P
´
ou` u est un inversible et les vp (a) des entiers positifs differents
de 0
pour un nombre fini d’entre eux (on dit presque tous nuls ).
Par exemple pour A = Z et a = 453750 :
UPMC - Licence Info - Crypto - 2012/13
41/71
Valuation p-adic
´
Soit A un anneau factoriel et P un ensemble de representants
pour
´
chacune des classes d’irreductibles
de A selon la relation
´
d’equivalence
xRy ⇔ ∃u ∈ A× tq x = uy (relation d’association).
´
Decomposition
unique
Pour a ∈ A non nul on a
a=u
Y
pvp (a)
p∈P
´
ou` u est un inversible et les vp (a) des entiers positifs differents
de 0
pour un nombre fini d’entre eux (on dit presque tous nuls ).
Par exemple pour A = Z et a = 453750 :
453750 = 112 × 3 × 54 × 2
UPMC - Licence Info - Crypto - 2012/13
41/71
Valuation p-adic
a=u
Y
pvp (a)
p∈P
´
Definition
´ ement
´
A tout el
p ∈ P d’un anneau factoriel A est associe´ une fonction
´
´
vp : A 7→ N ∪ {∞} definie
comme suit : Pour a 6= 0 l’entier vp (a) est egal
´
a` la puissance de p dans la decomposition
de a si p divise a et pour
a = 0 on aura par convention vp (a) = ∞. L’entier vp (a) est la valuation
p-adic de a .
UPMC - Licence Info - Crypto - 2012/13
42/71
Valuation p-adic
´
Definition
´ ement
´
A tout el
p ∈ P d’un anneau factoriel A est associe´ une fonction
´
´
vp : A 7→ N ∪ {∞} definie
comme suit : Pour a 6= 0 l’entier vp (a) est egal
´
a` la puissance de p dans la decomposition
de a si p divise a et pour
a = 0 on aura par convention vp (a) = ∞. L’entier vp (a) est la valuation
p-adic de a .
Par exemple pour A = Z et a = 453750 :
453750 = 11 × 11 × 3 × 5 × 5 × 5 × 5 × 2
v2 (a) = 1
v3 (a) = 1
v5 (a) = 4
v11 (a) = 2
vp (a) = 0 pour tout autre premier p
+ vp (0) = ∞ a un sens
UPMC - Licence Info - Crypto - 2012/13
43/71
´ es
´
Valuation p-adic : propriet
´ ements
´
Soit a et b deux el
d’un anneau factoriel A et P un ensemble de
´
´
representants
des irreductibles
de A.
vp (ab) = vp (a) + vp (b)
´
vp (a + b) > min(vp (a), vp (b)) avec egalit
e´ lorsque les valuations
´
sont differentes
a est un diviseur de b ssi ∀p ∈ P : vp (a) 6 vp (b)
Exemples : A = Z, a = 112 × 5, b = 112 × 3 × 2, c = 112 × 5 × 3
UPMC - Licence Info - Crypto - 2012/13
44/71
´ es
´
Valuation p-adic : propriet
´ ements
´
Soit a et b deux el
d’un anneau factoriel A et P un ensemble de
´
´
representants des irreductibles de A.
vp (ab) = vp (a) + vp (b)
´
vp (a + b) > min(vp (a), vp (b)) avec egalit
e´ lorsque les valuations
´
sont differentes
a est un diviseur de b ssi ∀p ∈ P : vp (a) 6 vp (b)
Exemples : A = Z, a = 112 × 5, b = 112 × 3 × 2, c = 112 × 5 × 3
v11 (ab) = 4, v5 (ab) = 1, v3 (ab) = 1
UPMC - Licence Info - Crypto - 2012/13
44/71
´ es
´
Valuation p-adic : propriet
´ ements
´
Soit a et b deux el
d’un anneau factoriel A et P un ensemble de
´
´
representants des irreductibles de A.
vp (ab) = vp (a) + vp (b)
´
vp (a + b) > min(vp (a), vp (b)) avec egalit
e´ lorsque les valuations
´
sont differentes
a est un diviseur de b ssi ∀p ∈ P : vp (a) 6 vp (b)
Exemples : A = Z, a = 112 × 5, b = 112 × 3 × 2, c = 112 × 5 × 3
v11 (a + b) = v11 (112 (5 + 2 × 3)) = v11 (112 (11)) = 3
v11 (a + c) = v11 (112 (5 + 5 × 3)) = v11 (112 (20)) = 2
UPMC - Licence Info - Crypto - 2012/13
44/71
´ es
´
Valuation p-adic : propriet
´ ements
´
Soit a et b deux el
d’un anneau factoriel A et P un ensemble de
´
´
representants
des irreductibles
de A.
vp (ab) = vp (a) + vp (b)
´
vp (a + b) > min(vp (a), vp (b)) avec egalit
e´ lorsque les valuations
´
sont differentes
a est un diviseur de b ssi ∀p ∈ P : vp (a) 6 vp (b)
Exemples : A = Z, a = 112 × 5, b = 112 × 3 × 2, c = 112 × 5 × 3
v11 (ab) = 4, v5 (ab) = 1, v3 (ab) = 1
c | ab
UPMC - Licence Info - Crypto - 2012/13
44/71
PGCD
´ ements
´
Soit a et b deux el
d’un anneau factoriel A et P un ensemble
´
´
representant
les irreductibles
de A.
´
Definition
´ ement
´
´
Le plus grand diviseur commun de a et b est l’el
d definit
par
d :=
Y
pmin(vp(a),vp(b))
p∈P
et est note´ pgcd(a, b) .
Exemples : A = Z, a = 112 × 5, b = 112 × 32 × 2, c = 112 × 5 × 3
UPMC - Licence Info - Crypto - 2012/13
45/71
PGCD
´ ements
´
Soit a et b deux el
d’un anneau factoriel A et P un ensemble
´
´
representant
les irreductibles
de A.
´
Definition
´ ement
´
´
Le plus grand diviseur commun de a et b est l’el
d definit
par
d :=
Y
pmin(vp(a),vp(b))
p∈P
et est note´ pgcd(a, b) .
Exemples : A = Z, a = 112 × 5, b = 112 × 32 × 2, c = 112 × 5 × 3
pgcd(a, b) = 112
car a = 112 × 5 × 30 × 20 et b = 112 × 50 × 32 × 2.
UPMC - Licence Info - Crypto - 2012/13
45/71
PGCD
´ ements
´
Soit a et b deux el
d’un anneau factoriel A et P un ensemble
´
´
representant
les irreductibles
de A.
´
Definition
´ ement
´
´
Le plus grand diviseur commun de a et b est l’el
d definit
par
d :=
Y
pmin(vp(a),vp(b))
p∈P
et est note´ pgcd(a, b) .
Exemples : A = Z, a = 112 × 5, b = 112 × 32 × 2, c = 112 × 5 × 3
pgcd(a, c) = a
UPMC - Licence Info - Crypto - 2012/13
45/71
PGCD
´ ements
´
Soit a et b deux el
d’un anneau factoriel A et P un ensemble
´
´
representant
les irreductibles
de A.
´
Definition
´ ement
´
´
Le plus grand diviseur commun de a et b est l’el
d definit
par
d :=
Y
pmin(vp(a),vp(b))
p∈P
et est note´ pgcd(a, b) .
Exemples : A = Z, a = 112 × 5, b = 112 × 32 × 2, c = 112 × 5 × 3
pgcd(b, c) = 112 × 3
UPMC - Licence Info - Crypto - 2012/13
45/71
PGCD
´
´
+ Une fois que l’ensemble P des representants
des irreductibles
de A
´
est fixe´ , le pgcd est unique . (Dans le cas A = Z les representants
sont
ˆ
positifs, il en sera donc de meme
pour le pgcd.)
+ Le pgcd(a, b) est maximal pour la divisibilite´ comme l’indique son
nom : max(Div(a) ∩ Div(b)) avec Div(a) l’ensemble (fini) des diviseurs
(positifs) de a.
´
Caracterisation
´ ee
´ :
d = pgcd(a, b) si et seulement si l’assertion suivante est verifi
si c divise a et b alors c’est un diviseur de d
UPMC - Licence Info - Crypto - 2012/13
46/71
´ ements
´
El
premiers entre eux
´ a` la divisibilite´
+ Notion liee
Premiers entre eux
´ ements
´
Deux el
a et b sont dits premiers entre eux (ou a est premier
` que l’ensemble des diviseurs communs a` a et b est reduit
´
avec b) des
aux inversibles.
+Dans le cas A = Z les entiers premiers entre eux sont ceux pour qui
´
l’ensemble de leurs diviseurs positifs communs est reduit
a` {1}.
+Lien avec le PGCD ?
UPMC - Licence Info - Crypto - 2012/13
47/71
Part VI
Calcul du PGCD : algorithme d’Euclide
UPMC - Licence Info - Crypto - 2012/13
48/71
Calculer le PGCD : Euclide
On cherche le plus grand diviseur entre 14 et 8.
+On a 14 = 8 + 6 ainsi comme on cherche d divisant 8 et 14 il suffit de
´ e´ avec 8 et 6 etc.
chercher d divisant 8 et 6, on recommence le proced
ˆ des
` que l’un des entiers consider
´ e´ est nul.
+On s’arrete
´
Lemmes immediats
Si d divise a et c et que (a + b) = c alors d divise b.
´ ement
´
Le pgcd d’un el
a 6= 0 et 0 est a.
UPMC - Licence Info - Crypto - 2012/13
49/71
Calculer le PGCD : Euclide
´
Mathematicien
grec (ne´ vers -325, mort
´ antique),
vers -265 a` Alexandrie, Gre´ es
´ ements,
´ des El
´
auteur (suppose)
ouvrage
´
fondateur des mathematiques
modernes. Il
´
´
`
etait
avant tout geom
etre,
comme tous les
´
mathematiciens
grecs de l’antiquite´ !
14
8
UPMC - Licence Info - Crypto - 2012/13
50/71
Calculer le PGCD : Euclide
´
Mathematicien
grec (ne´ vers -325, mort
´ antique),
vers -265 a` Alexandrie, Gre´ es
´ ements,
´ des El
´
auteur (suppose)
ouvrage
´
fondateur des mathematiques
modernes. Il
´
´
`
etait
avant tout geom
etre,
comme tous les
´
mathematiciens
grecs de l’antiquite´ !
6
8
UPMC - Licence Info - Crypto - 2012/13
50/71
Calculer le PGCD : Euclide
´
Mathematicien
grec (ne´ vers -325, mort
´ antique),
vers -265 a` Alexandrie, Gre´ es
´ ements,
´ des El
´
auteur (suppose)
ouvrage
´
fondateur des mathematiques
modernes. Il
´
´
`
etait
avant tout geom
etre,
comme tous les
´
mathematiciens
grecs de l’antiquite´ !
6
2
UPMC - Licence Info - Crypto - 2012/13
50/71
Calculer le PGCD : Euclide
´
Mathematicien
grec (ne´ vers -325, mort
´ antique),
vers -265 a` Alexandrie, Gre´ es
´ ements,
´ des El
´
auteur (suppose)
ouvrage
´
fondateur des mathematiques
modernes. Il
´
´
`
etait
avant tout geom
etre,
comme tous les
´
mathematiciens
grecs de l’antiquite´ !
2
4
UPMC - Licence Info - Crypto - 2012/13
50/71
Calculer le PGCD : Euclide
´
Mathematicien
grec (ne´ vers -325, mort
´ antique),
vers -265 a` Alexandrie, Gre´ es
´ ements,
´ des El
´
auteur (suppose)
ouvrage
´
fondateur des mathematiques
modernes. Il
´
´
`
etait
avant tout geom
etre,
comme tous les
´
mathematiciens
grecs de l’antiquite´ !
2
pgcd
4
UPMC - Licence Info - Crypto - 2012/13
50/71
Calculer le PGCD
+ Plus d’efficacite´ : division euclidienne dans A
´
L’anneau A est donc suppose´ euclidien (de fonction d fixee).
Pour
´ ements
´
calculer le pgcd de deux el
a et b tels que d(b) < d(a).
´
Schema
de calcul d’Euclide
Posant r0 = a et r1 = b on calcule jusqu’a` obtenir un reste nul .
1
2
n−1
n
si r1 6= 0 on a r0 = r1 q1 + r2 avec d(r2 ) < d(r1 )
si r2 =
6 0 on a r1 = r2 q2 + r3 avec d(r3 ) < d(r2 )
..
.
si rn−2 6= 0 on a rn−2 = rn−1 qn−1 + rn avec d(rn ) < d(rn−1 )
si rn−1 6= 0 on a rn−1 = rn qn + rn+1 avec d(rn+1 ) < d(rn ) et
rn+1 = 0
Algorithme d’Euclide
´
Le dernier reste non nul rn est egal
au pgcd de a et b .
UPMC - Licence Info - Crypto - 2012/13
51/71
Algorithme d’Euclide
´
´
Ce schema
se traduit immediatement
en C pour les entiers.
#include<stdio.h>
#include<math.h>
int main() {
int a,b,tmp,r0,r1;
printf("Entrer deux entiers positifs a > b > 0 : ");
scanf("%d",&a);
scanf("%d",&b);
r0=a;
r1=b;
while(r1!=0){
tmp=r1;
r1=r0 % r1;
r0=tmp;
}
printf("\nLe pgcd de %d et %d est %d\n",a,b,r0);
return 0;
}
UPMC - Licence Info - Crypto - 2012/13
52/71
´
Algorithme d’Euclide : demonstration
´
+ Terminaison : c’est immediat
puisque les ri vont en diminuant selon
leur valeur par d.
+ Correction : pour montrer la correction nous calculons des pgcd
´
´ edent.
´
´ edent
´
suivant le schema
prec
On utilise le lemme prec
pour
´
´
´ successives.
demontrer
les egalit
es
pgcd(a, b) = pgcd(r0 , r1 ) = pgcd(r1 q1 + r2 , r1 ) = pgcd(r2 , r1 ) = . . .
UPMC - Licence Info - Crypto - 2012/13
53/71
´ eme
`
´
Theor
de Bachet Bezout
+ L’algorithme d’Euclide calcule plus que le pgcd
´
Relation de Bezout
´ ements
´
Soit a et b deux el
d’un anneau euclidien A. Il existe deux
´ ement
´
el
u et v tel que
pgcd(a, b) = ua + vb.
´ les coefficients de Bezout
´
+ Les coefficients u et v sont appeles
´ eme
`
´
+ Le theor
de Bachet Bezout
a de nombreuses applications.
UPMC - Licence Info - Crypto - 2012/13
54/71
´ eme
`
´
´
Theor
de Bachet Bezout
: demonstration
´
On utilise le schema
d’Euclide.
´
En construisant des relations lineaires
entre ri , a et b pour
26i6n
Pour i = 2 nous avons r2 = r0 − r1 q1 avec r0 = a et r1 = b et donc
r2 = a − q1 b
On suppose avoir la relation ri = ui a + vi b pour i > 2. On a
ri+1 = ri−1 − qi ri = (ui−1 − qi ui )a + (vi−1 − qi vi )b
´
´
´
On deduit
le resultat
par recurrence.
UPMC - Licence Info - Crypto - 2012/13
55/71
´
Algorithme d’Euclide Etendu
´
´ eme
`
´
´
La demonstration
du theor
de Bachet Bezout
permet de deduire
´
´
une formule de recurrence
pour calculer les coefficients de Bezout
de
a et b et le pgcd(a, b). Cette formule se traduit sous la forme d’un
algorithme :
´
Algorithme d’Euclide etendu

v0 = 0,
r0 = a
 u0 = 1,
u1 = 0,
v1 = 1,
r1 = b

ui+1 = ui−1 − qi ui , vi+1 = vi−1 − qi vi , ri+1 = ri−1 − qi ri i > 1
´
+Representation
matricielle pour i > 1:
ui+1 vi+1 ri+1
−qi 1
ui
vi
ri
=
ui
vi
ri
1 0
ui−1 vi−1 ri−1
+Nous verrons plus tard dans le cours, le nombre de calculs
´
´
necessaires
pour obtenir le pgcd et les coefficients de Bezout.
UPMC - Licence Info - Crypto - 2012/13
56/71
Part VII
L’anneau (Z/nZ, +, ×) et le calcul
modulaire
UPMC - Licence Info - Crypto - 2012/13
57/71
L’anneau (Z/nZ, +, ×)
` la relation d”equivalence
´
Soit n un entier positif. On considere
aRn b ⇔ a − b ∈ nZ .
´
´
´ par les
+Les classes d’equivalence
peuvent represent
ees
r + nZ = {r + nk : k ∈ Z} avec r ∈ {0, . . . , n − 1}.
Addition et Multiplication dans Z/nZ
(r1 + nZ) + (r2 + nZ) = (r1 + r2 ) + nZ = r3 + nZ avec r3 le reste
modulo n de r1 + r2 vu dans Z.
(r1 + nZ) × (r2 + nZ) = (r1 × r2 ) + nZ = r3 + nZ avec r3 le reste
modulo n de r1 × r2 vu dans Z.
´
+Muni de ces deux operations
Z/nZ est un anneau (commutatif)
(exercice : montrer le).
UPMC - Licence Info - Crypto - 2012/13
58/71
L’anneau (Z/nZ, +, ×)
Exemple Z/7Z
´
L’ensemble des classes de R7 est represent
e´ par les
0 + 7Z, ; 1 + 7Z, . . . , 6 + 7Z
Nous avons
´ ement
´
ˆ
3 + 7Z = −4 + 7Z l’el
−4 est de la meme
classe que 3.
3 + 7Z − 1 + 7Z = 3 + 7Z + 6 + 7Z = 9 + 7Z = 2 + 7Z se note
3 − 1 = 3 + 6 = 9 = 2 mod 7
UPMC - Licence Info - Crypto - 2012/13
59/71
Lien entre PGCD et multiples
Proposition
Soit nZ et mZ deux ensembles de multiples dans Z. L’ensemble
nZ + mZ = {a1 + a2 : a1 ∈ nZ et a2 ∈ mZ} est aussi un ensemble de
´ ement.
´
multiples d’un el
Plus exactement, on a
nZ + mZ = pgcd(n, m)Z.
+L’ensemble des entiers qui sont des multiples de n ou de m sont les
multiples de pgcd(m, n).
+Quel est l’ensemble des entiers multiples de n et de m ? (exercice).
UPMC - Licence Info - Crypto - 2012/13
60/71
´ ements
´
Lien entre PGCD et el
premiers entre eux
´
Corollaire Bachet-Bezout
´ ements
´
Deux el
a et b de Z sont premiers entre eux ssi il existe u et v
tel que
ua + vb = 1
En d’autres termes, ssi l’ensemble des entiers qui sont multiples de a
ou de b forme l’anneau Z tout entier
aZ + bZ = 1Z = Z
UPMC - Licence Info - Crypto - 2012/13
61/71
´
´ ements
´
Z/nZ, integrit
e´ et el
inversibles
´
Integrit
e´
`
Z/nZ est integre
ssi n est premier.
´ ements
´
El
inversibles
´ ement
´
Un el
x ∈ Z/nZ est inversible ssi il existe y ∈ Z/nZ tq
(x + nZ) × (y + nZ) = 1 + A. Ceci se traduit par xy = 1 mod n. Il existe
donc u dans Z tel que xy + au = 1, ceci revient au calcul d’une relation
´
de Bezout
!
UPMC - Licence Info - Crypto - 2012/13
62/71
´
Z/nZ et la definition
de corps
´ eme
`
Theor
´ ements
´
Les el
inversibles dans Z/nZ sont les classes ayant un
´
representant
premier avec n .
Corollaire
´
´ ements
´
Si n est irreductible
(⇔ premier) alors tous les el
de Z/nZ prive´
´ ement
´
de l’el
nul sont inversibles.
´
Definition
´ ements
´
´
Un anneau dont tous les el
differents
de l’unite´ pour la
` operation
´
premiere
sont inversibles est un corps .
UPMC - Licence Info - Crypto - 2012/13
63/71
Z/nZ en tant que corps premier
´ ements
´
El
inversibles dans Z/nZ
L’ensemble (Z/nZ)× des inversibles de Z/nZ est donne´ par les
´ ements
´
´
el
a verifiant
pgcd(a, n) = 1
´
´
L’inverse etant
calcule´ par l’algorithme d’Euclide etendu
´ ement
´
´
Exemple : L’el
10 dans Z/21Z (representant
la classe 10 + 21Z)
est inversible d’inverse −2 = 19 mod 21. En effet nous avons la
´
relation de Bezout
:
10 × (−2) + 21 × 1 = 1
Corps premiers
Les anneaux quotients Z/pZ avec p un entier premier sont des corps
´ les corps premiers.
de cardinal p. On les notes Fp et sont appeles
UPMC - Licence Info - Crypto - 2012/13
64/71
Calcul modulaire pratique
Principe de base modulo n
´
Ne jamais laisser grossir le representant
de la classe. On effectue
´
´
donc des reductions
modulo n a` la suite des operations.
Comment calculer 15362 mod 26 ?
UPMC - Licence Info - Crypto - 2012/13
65/71
Calcul modulaire pratique
Principe de base modulo n
´
Ne jamais laisser grossir le representant
de la classe. On effectue
´
´
donc des reductions
modulo n a` la suite des operations.
Comment calculer 15362 mod 26 ?
Ne surtout PAS calculer la puissance !
555950055800404828716257724467752260158215698743020306033284422997242638
193590114682698510877751945791100011259442205311499677154994108188813652
986548714887879008460611471446667462293162482154326721629967903287837574
049862446605056531825294441531016708701108585851936237439229798864723350
920277085670064315176655628092922091669772429098440748034205948253206392
619016977781494151991518483379994819415514939464628696441650390625
UPMC - Licence Info - Crypto - 2012/13
65/71
Calcul modulaire pratique
Principe de base modulo n
´
Ne jamais laisser grossir le representant
de la classe. On effectue
´
´
donc des reductions
modulo n a` la suite des operations.
Comment calculer 15362 mod 26 ?
15362 = 3362 × 5362
UPMC - Licence Info - Crypto - 2012/13
mod 26
65/71
Calcul modulaire pratique
Principe de base modulo n
´
Ne jamais laisser grossir le representant
de la classe. On effectue
´
´
donc des reductions
modulo n a` la suite des operations.
Comment calculer 15362 mod 26 ?
15362 = 3362 × 5362
mod 26
De plus 362 = 12 ∗ 30 + 2 avec 33 = 1 mod 26 et 54 = 1 mod 26
UPMC - Licence Info - Crypto - 2012/13
65/71
Calcul modulaire pratique
Principe de base modulo n
´
Ne jamais laisser grossir le representant
de la classe. On effectue
´
´
donc des reductions
modulo n a` la suite des operations.
Comment calculer 15362 mod 26 ?
15362 = 3362 × 5362 = 32 × 52 = −9
mod 26
De plus 362 = 12 ∗ 30 + 2 avec 33 = 1 mod 26 et 54 = 1 mod 26
UPMC - Licence Info - Crypto - 2012/13
65/71
´
Algorithme Euclide etendu
: mise en pratique !
Comment trouver l’inverse de 2345 modulo 30003 s’il existe ?
UPMC - Licence Info - Crypto - 2012/13
66/71
´
Algorithme Euclide etendu
: mise en pratique !
Comment trouver l’inverse de 2345 modulo 30003 s’il existe ?
´
Calcul pratique du pgcd etendu
(a` la main):
i
1
2
3
..
.
ri−1
30003
2345
?
..
.
UPMC - Licence Info - Crypto - 2012/13
ri
2345
1863
?
..
.
qi
12
?
?
..
.
ri+1
1863
?
?
..
.
ui+1
1
?
?
..
.
vi+1
-12
?
?
..
.
66/71
´
Algorithme Euclide etendu
: mise en pratique !
Comment trouver l’inverse de 2345 modulo 30003 s’il existe ?
´
Calcul pratique du pgcd etendu
(a` la main ou en machine):
i
1
2
3
4
5
6
7
8
9
ri−1
30003
2345
1863
482
417
65
27
11
5
UPMC - Licence Info - Crypto - 2012/13
ri
2345
1863
482
417
65
27
11
5
1
qi
12
1
3
1
6
2
2
2
5
ri+1
1863
482
417
65
27
11
5
1
0
ui+1
1
-1
4
-5
34
-73
180
-433
2345
vi+1
-12
13
-51
64
-435
934
-2303
5540
-30003
66/71
´
Algorithme Euclide etendu
: mise en pratique !
Comment trouver l’inverse de 2345 modulo 30003 s’il existe ?
´
Calcul pratique du pgcd etendu
(a` la main):
i
1
..
.
8
9
ri−1
30003
..
.
11
5
ri
2345
..
.
5
1
qi
12
..
.
2
5
ri+1
1863
..
.
1
0
ui+1
1
..
.
-433
2345
vi+1
-12
2303
5540
-30003
´
+On en deduit
que −433 × 30003 + 5540 × 2345 = 1
+et donc 5540 × 2345 = 1 mod 30003
UPMC - Licence Info - Crypto - 2012/13
66/71
Part VIII
Conclusion
UPMC - Licence Info - Crypto - 2012/13
67/71
`
´
Chiffrement affine : probleme
resolu
`
Cryptosysteme
affine
´
P, C sont tous les deux egaux
a` Z/26Z
K est un sous ensemble de Z/26Z × Z/26Z tel que
Pour tout K = (a, b) ∈ K on a
eK (x) = ax + b mod 26
et il existe une fonction dK : C → P inverse de eK .
´
+Comment determiner
l’ensemble K ?
´
`
+Etude de Z/26Z. Attention c’est un anneau non integre
!
´
´ a, b, y il faut resoudre
´
´
Etant
donnes
l’equation
y = ax + b
mod 26
Ceci est possible que si a est inversible modulo 26 . On obtient alors
dK (y) = a−1 y − a−1 b .
UPMC - Licence Info - Crypto - 2012/13
68/71
Chiffrement affine : Table de multiplication mod 26
×
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
4
6
8
10
12
14
16
18
20
22
24
0
2
4
6
8
10
12
14
16
18
20
22
24
6
9
12
15
18
21
24
1
4
7
10
13
16
19
22
25
2
5
8
11
14
17
20
23
8
12
16
20
24
2
6
10
14
18
22
0
4
8
12
16
20
24
2
6
10
14
18
22
10
15
20
25
4
9
14
19
24
3
8
13
18
23
2
7
12
17
22
1
6
11
16
21
12
18
24
4
10
16
22
2
8
14
20
0
6
12
18
24
4
10
16
22
2
8
14
20
14
21
2
9
16
23
4
11
18
25
6
13
20
1
8
15
22
3
10
17
24
5
12
19
16
24
6
14
22
4
12
20
2
10
18
0
8
16
24
6
14
22
4
12
20
2
10
18
18
1
10
19
2
11
20
3
12
21
4
13
22
5
14
23
6
15
24
7
16
25
8
17
20
4
14
24
8
18
2
12
22
6
16
0
10
20
4
14
24
8
18
2
12
22
6
16
22
7
18
3
14
25
10
21
6
17
2
13
24
9
20
5
16
1
12
23
8
19
4
15
24
10
22
8
20
6
18
4
16
2
14
0
12
24
10
22
8
20
6
18
4
16
2
14
0
13
0
13
0
13
0
13
0
13
0
13
0
13
0
13
0
13
0
13
0
13
0
13
2
16
4
18
6
20
8
22
10
24
12
0
14
2
16
4
18
6
20
8
22
10
24
12
4
19
8
23
12
1
16
5
20
9
24
13
2
17
6
21
10
25
14
3
18
7
22
11
6
22
12
2
18
8
24
14
4
20
10
0
16
6
22
12
2
18
8
24
14
4
20
10
8
25
16
7
24
15
6
23
14
5
22
13
4
21
12
3
20
11
2
19
10
1
18
9
10
2
20
12
4
22
14
6
24
16
8
0
18
10
2
20
12
4
22
14
6
24
16
8
12
5
24
17
10
3
22
15
8
1
20
13
6
25
18
11
4
23
16
9
2
21
14
7
14
8
2
22
16
10
4
24
18
12
6
0
20
14
8
2
22
16
10
4
24
18
12
6
16
11
6
1
22
17
12
7
2
23
18
13
8
3
24
19
14
9
4
25
20
15
10
5
18
14
10
6
2
24
20
16
12
8
4
0
22
18
14
10
6
2
24
20
16
12
8
4
20
17
14
11
8
5
2
25
22
19
16
13
10
7
4
1
24
21
18
15
12
9
6
3
22
20
18
16
14
12
10
8
6
4
2
0
24
22
20
18
16
14
12
10
8
6
4
2
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
UPMC - Licence Info - Crypto - 2012/13
69/71
Chiffrement affine : Indicatrice d’Euler
`
Cryptosysteme
affine
´
P, C sont tous les deux egaux
a` Z/26Z
K est le sous-ensemble des (a, b) ∈ Z/26Z × Z/26Z tel que a est
premier avec 26.
Indicatrice d’Euler
´ ements
´
Etant donne´ un entier n, le nombre d’el
strictement positifs,
´
inferieurs
et premier avec n est note´ ϕ(n). Ce nombre est appele´
indicatrice d’Euler de n et note´
ϕ(a) = card{0 < n < a : pgcd(a, n) = 1}
´ possibles est donc ϕ(26) × 26 .
Le nombre de cles
+Comment calculer ϕ(26) ? a` suivre...
UPMC - Licence Info - Crypto - 2012/13
70/71
Conclusion
´
Cesar
et chiffrement affine
´
Nous avons vu l’utilisation des structures mathematiques
de base
´
`
pour definir
des cryptosystemes.
´
Arithmetique
modulaire et groupes de permutations.
´
Je vous conseille de reviser
l’algorithme d’Euclide et son
´
utilisation pour calculer les coefficients de Bezout
!
UPMC - Licence Info - Crypto - 2012/13
71/71

Download Report