Alice et Bob ne ce connaisse pas, il communique sur un canal compromis que Eve écoute, ils veulent partager une clé
Alice prend un nombre p premier et aleatoire qu'elle envoie a Bob
Alice prend un nombre g générateur de ℤ/pℤ qu'elle envoie a Bob
Bob choisit un nombre b aléatoire dans ℤ/pℤ
Bob calcule B = pow(g, b)%p
Alice choisit un nombre a aléatoire dans ℤ/pℤ
Alice calcule A = pow(g, a)%p
A et B sont envoyerrespectivement à Bob et Alice
Alice calcule K = pow(B, a)%p
Bob calcule K' = pow(A, b)%p
comment Eve peut-elle retrouver K ?

• elle connait p, g, A, B
• seul solution connue : logarithme discret

idée: une clé secrète pour décrypter, une clé publique pour crypté (asymétrique)
plus besoin d'échange de clés: Alice met à disposition la clé publique à tout le monde

example du système El Granal

Alice choisit p,g avec g: gnérateur de ℤ/pℤ


• elle choisit une clé secrete k<p< li="">
• elle calcule K = pow(g,k)%p
• la clé publique est p,g,K qui est envoyer à Bob
• elle reçoit une messages crypter de Bob
• elle calcule pow(T,k)%p = pow(pow(g,k),b) = pow(K,b)%p
• elle calcule M/pow(k,b)%p = m, le message

Bob veut envoyer un message qu'il découpe en bloques representer par des entier dans ℤ/pℤ
chaque bloques en crypter et tranmit à Alice


• choisit une clé temporaire b (différente à chaque bloques)
• il calcule pow(g,b)%p = T
• il calcule m*pow(K,b)%p = M
• il envoie T et M

• Alice est la seul à pouvoir signer -> clé privée
• tout le monde peut verifier -> clé publique
• (clé privée / clé publique sont inversé)
• Alice crypte M avec ça clé privée : S pour verifier la signature
• Bob decrypte S avec la clé publique de Alice et compare le resultate avec M

Générateur pseudo-aléatorie qui produit des nombre entre 0 et 255
Inventer par R.Rivest en 1987
En 1994, le fonctionement est dévoilé sur le groupe usenet 'cyberpunk' (ARC4)
fonctionement de RC4: deux étapes (initialisation avec une clé de 256 octets / génération)
l'état interne du générateur est donnée par i, j entier et p[] contenant 256 octets (dans le désordre)

initialisation

K: tableau de taille t<256 (seed)
P = {0, ..., 255}, j = 0
for i in 0..255 loop
j = j + P[i] + K[i%len]
swap(P[i], P[j])
end loop


génération

i = i+1
j = j + P[i]
swap(P[i], P[j])
return P[P[i] + P[j]];