Page 1 of 2
1°) Historique
code de césar
x = (x+3)%26
tableau -> études statistique
La cryptographie est l'art de caché des messages, rendre incompréhenssibles les messages sans connaitre une manière non-ambigue de le déchiffrer. Par exemple on veut :
- l'impossibilité de décrypté un message crypté
- l'impossibilité de décrypté même si on dispose de plusieur messages cryptés
- l'impossibilité de décrypté même si on dispose des messages en claires
- l'impossibilité de décrypté même si on peut gnéré des messages cryptés
2°) Le bloc note à usage unique
C'est le seul code crypto sûre:
on ne réutilise pas les bits de la clé
clé: suite de bit aléatoires (long)
on xor le message avec la clé pour crypté
on ne réutilise pas les bits de la clé
clé: suite de bit aléatoires (long)
on xor le message avec la clé pour crypté
problème:
certain générateur peuvent être utilisé et sont en pratique suffisament sûre (RC4)- il faut transmettre la clée (physiquement au mieux)
- la clé à la même taille que le message
- la clé doit être aléatoire (pas de générateur pseudo-aléatoire)
on initialise avec une clé de taille 255 (ou moin)
avantage: taille de la clé <= 255 octéts
c'est ce générateur qui est utilisé dans le codage WEP qui n'est pas sûre3°) crytpographie symetrique
le seul secret partagé par Alice et Bob est une clé (secète) de petite taille
ex: générateur aléatoire + xor (RC4) = DES / AES (très rapide)
ex: générateur aléatoire + xor (RC4) = DES / AES (très rapide)
problème de transmission de la clé: échange de clés de Diffie-Hellman 1976
cette méthode permet l'échange de clé même si un attaquent écoute toutes les communications, il ne pourras pas craquer la clée
cette méthode permet l'échange de clé même si un attaquent écoute toutes les communications, il ne pourras pas craquer la clée
4°) crypto clé publique/privé, arithmétique
a°) rappels
def: m est multiple de n si n = n*a
on it aussi que n divise m, on note m|n
on it aussi que n divise m, on note m|n
- On note pgcd(n,m) pour le plus grand diviseur commun de n et m
- si n et m sont des nombres entiers alors il existe un unique quotient et
un unique r apartenant à [0,m] telque n = q*m + r
b°) euclide : pgcd
pgcd(0, n) = n ; pgcd(m, n) = pgcd(n%m, m) si m <= n, pgcd(m, n) = pgcd(m, n) sinon
exemple
pgcd(15, 12) = pgcd(12, 15) =
pgcd(15%12, 12) = pgcd(12%3, 3) =
pgcd(0, 3) = 3c°) bézout : euclide étendue
theoreme: si a est le pgcd de n et m alors on peut trouver x et y telque m*x + n*y = a (x et y peuvent être négatif)
exemple
pgcd(14, 22)
= pgcd(8, 14) car 22 = 1*14 + 8 | x = -3 et y = 2
= pgcd(6, 08) car 14 = 1*08 + 6 | 2 = 2*(22-14) - 1*14 = -3*14 + 22*2
= pgcd(2, 06) car 08 = 1*06 + 2 | 2 = 8*1 - (14-1*8)*1 = 2*8 - 1*14
= pgcd(0, 02) car 06 = 3*02 + 0 | 2 = 8 - 6*1
= 2, on remonte: -------------------------/d°) nombre premier
def: un nombre est premier si il a exactement 2 diviseur, 1 et lui même
theoreme: tout entier se décompose de manière unique en produit de nombres premier
theoreme: il y a une infinité de nombre premier pow(2, 43112609) et 43112609 sont premier
constation/conjecture: on ne sait pas trouver les facteurs premiers d'un nombre en temps raisonable
theoreme: la proportion de nombre premier entre 1 et n est environ n/ln(n)
e°) calcule modulo
on note a ≡ d%n quand m | (a-d), ou, a%m = b%m
theoreme: {a≡b%m ; a'≡b'%m} ⇒
remarque: division modulo, si a et m sont premier entre eux alors on peut diviser par a%m
a+a' ≡ (b+b')%m
a*a' ≡ (b*b')%m
a-a' ≡ (b-b')%m
pow(a, k) ≡ pow(b, k)%m
⇒ pow(a, a') ≢ pow(b, b')%m (en général)methode
on cherche x et y telque ax+my=1
on a ax+bm ≡ 1%m ⇒ ax ≡ 1%m
on dit que x est l'inversse de a%m, la division est donc la multiplication par l'inversse de a : x
si m est un nombre premier, on peut diviser par 1..m-1 ; on dit que {0, ..., n-1} forme on corp, noté ℤ/nℤ
theoreme euleur: si p est premier alors pow(a, p-1) ≡ 1%p
si p et q sont premier alors pow(a, (p-1)*(q-1)) ≡ 1%p
si p et q sont premier alors pow(a, (p-1)*(q-1)) ≡ 1%p
f°) problème du logarithme discret
si p est premier alors un élément générateur est un nombre a telque
{a⁰=1, a¹=a, ..., a^(p-2)} = {1, 2, ..., p-1} c à d les puissances de a engendre tout les nombres %p sauf 0
Si a est générateur, la fonction n➝pow(a,n)%p est facile à calculer, mais on ne sait pas faire l'inversse en temps raisonable
c'est le problème du logarithme discret
{a⁰=1, a¹=a, ..., a^(p-2)} = {1, 2, ..., p-1} c à d les puissances de a engendre tout les nombres %p sauf 0
Si a est générateur, la fonction n➝pow(a,n)%p est facile à calculer, mais on ne sait pas faire l'inversse en temps raisonable
c'est le problème du logarithme discret
⎡ X1 = ( aX + c)%m
⎢ X2 = (aX1 + c)%m
⎣ X3 = (aX2 + c)%m
a = (X3-X2) / (X2-X1)
c = X2 - aX1