CRYPTOGRAPHIE


Résumé du livre "Cryptographie appliquée" de Bruce Schneier, édition Thomson Publishing


I- Les problèmes


On range les problèmes mathématiques par classes de complexité. Les frontières entre classes sont ce qu'elles sont jusqu'à preuve du contraire !

N < NP <= NP-Complet < PSPACE <= PSPACE-Complet < EXPTIME

Avec :

N : les problèmes sont résolus en temps polynomial.

NP : Idem, mais sur une machine de Turing non déterministe : la machine devine une solution, et vérifie son hypothèse en temps polynomiale.

NP-Complet : aussi difficile que tout autre problème dans NP. Exemple : problème du voyageur.

PSPACE : soluble en espace polynomiale et pas en temps.

EXPTIME : soluble en temps exponentiel


II- Le cryptage à clé privé : le DES

Page 229

L'algorithme du DES découpe le texte en bloc de 64 bits. Pour un bloc, on effectue une permutation initiale, puis on le coupe en deux : pour chacune des parties, on effectue 16 rondes d'une fonction. Puis les parties réassemblées, on fait une permutation finale, inverse de l'initiale. Dans une ronde, on effectue des permutations, des XOR, et des substitutions par l'intermédiaire de tables (les tables S).


III- Le cryptage à clé public : le RSA

Page 297

L'algorithme du RAS repose sur la difficulté de factoriser des grands nombres. Soit n = p*q (p et q étant de grands nombres premiers), on calcule :

- La clef publique : e tel que e et (p-1)*(q-1) soient premiers

- La clef privée : d = e-1 mod ((p-1)*(q-1))

- Chiffrement d'un message m : c = me mod n

- Déchiffrement : m = cd mod n


IV- Le hachage : le SHA

Page 351

La hachage permet d'obtenir d'une information (contrat, facture, ...) une empreinte unique. Tout changement de la source modifie l'empreinte.

Pour le SHA, les données sont en blocs de 512 bits. L'empreinte sera de 160 bits. On utilise des constantes et des fonctions de mélanges de bits (opérateurs binaires). Un bloc de 512 bits est découpé en 16 mots de 32 bits et transformé en 80 mots. On applique les fonctions sur ces mots (4 rondes de 20 opérateurs = 80 mots) en conservant une trace à l'aide de 5 variables. A la fin, l'empreinte est la juxtaposition de ces variables.


V- La signature : le DSA

Page 322

Le DSA utilise une clé de p bits. p est compris entre 512 et 1024 et est un multiple de 64. Soit q un facteur premier de p-1 et long de 160 bits. Soit h<p-1 tel que h(p-1)/q>1.

On note g=h(p-1)/q; x < q; y = gxmod p; H(x) = SHA(x).

p, q et g sont publics et peuvent être commun à un groupe d'utilisateur. x est la clé privée, y la clé publique. La signature du message m est calculée comme suit :

Soit k<q; r=(gkmod p) mod q; s=(k-1(H(m)+x*r))mod q

r et s forment la signature. La vérification de la signature se calcule comme suit :

Soit w = s-1 mod q; u1=(H(m)*w) mod q; u2=(r*w) mod q; v=((gu1*yu2)mod p) mod q

La signature est correcte si v = r.


VI- Suite de bits : le BBS

Page 367

Le Blum Blum Shub est un générateur aléatoire qui tire sa théorie des résidus quadratiques modulo n. On recherche deux grands nombres premiers p et q tels que p mod 4 = q mod 4 = 3. On a alors n=p*q qui est un entier de Blum. On choisit x aléatoire, puis x0=x2mod n est le germe du générateur. La suite se calcule soit par xi = xi-12 mod n, soit par xi=x02^imod((p-1)*(q-1))mod n.

Le BBS peut être utilisé pour chiffrement en continu (par XOR avec le message) : en effet, si l'on ne connaît que n, on ne peut pas prédire ce qu'il y a à droite ou à gauche d'une suite de données.


VII- Echange de clés : Diffie-Hellman

Page 291/397

C'est un algorithme qui permet d'échanger une clé de manière sûre. On choisit deux grands nombres n et g / g < n. Leur longueur est de 1024 bits. Ils sont publiés et peuvent être commun à un groupe. La 1ère personne choisit x et calcule X=gxmod n. La seconde personne choisit y et calcule Y=gymod n. Ils échangent X et Y et utilisent la clé privé k=Yxmod n=k'=Xymod n=gxymod n

Pour nous contacter : siteclic.aro.microclic.com en remplaçant '.aro.' par @
3 requêtes