Cryptography Theorems and Terms CC1

Définition de Divisibilité

Soient a et b deux entiers ; on dit que a divise b (ou que b est un multiple de a) et on note a | b, s'il existe un entier k tel que ak = b

Si a | b et c | d ...

alors ac | bd

Pour tout c != 0, ac | bc ssi ...

a | b

Tous les entiers divisent...

0

Pour tout entier n, __ divise(nt) n

n et -n

Réflexivité (pour Divisibilité)

For all n E Z, n | n

Transitivité (Divisibilité)

for all a, b, c E Z, si a | b et b | c, alors a | c

Antisymétrie sur N (Divisibilité)

For all a, b E N, si a | b et b | a, alors a = b

si x | a et x | b, alors...

x | au + bv pour tous u, v

L'ensemble des multuples d'un entier a est noté :

aZ = {au | u E Z}

Nombre premier

Un entier naturel est premier s'il admet exactement 2 diviseurs

- tout entier différent de 1 admet un facteur premier

- plus précisément, tout nombre > 1 admet une unique décomposition en facteurs premiers

- l'ensemble des nombres premiers est infini

Quatre problèmes concernant P

1. Dresser la liste des premiers nombres premiers

2. Décider si un entier n est premier

3. Construire un grand nombre premier

4. Déterminer un facteur d'un entier n non premier

Principe du crible

Soit p1 < p2 < p3 .... la liste ordonnée des nombres premiers.

- pour tout i, les multiples k(pi) de pi avec k >= 2 ne sont pas premiers

- réciproquement, si un nombre n'est pas premier, alors en appelant pi son plus petit facteur premier, n s'écrit k(pi) pour un certain k >= pi

- le premier entier supérieur à pi, et non multiple de p1, p2, ... pi est pi + 1

Algorithme de la primarité

1. Choisir au hasard un entier n

2. Tester si n est premier ; sinon, recommencer au point précédent

Théorème des nombres premiers

La probabilité pour qu'un nombre n soit premier est de l'ordre de 1 / ln n, autrement dit autour de n, un nombre sur ln n est premier

Division euclidienne

Soit a E Z et b E N*. Il existe un unique couple (q, r) tel que a = b x q + r et 0 <= r < b

L'écriture a = b x q + r est la division euclidienne de a par b ; q est le quotient et r est le reste

Théorème 5

Soient a, b E Z. Il existe un unique c = N tel que aZ + bZ = cZ

Définition du pgcd

Soit a, b E Z, l'entier c E N tel que aZ + bZ = cZ est le pgcd de a et b, noté pgcd(a, b)

Théorème sur les diviseurs communs

pgcd (a, b) est le plus grand (au sens de la divisibilité) diviseur commun de a et b. Autrement dit, c'est un diviseur commun, et tout diviseur commun de a et b divise pgcd(a,b)

Identité de Bézout

Soit a et b deux entiers, il existe x et y tels que ax + by = pgcd(a,b)

Euclide

Pour tous a, b, p E Z, pgcd(a,b) = pgcd(a + bp, b)

Des propriétiés :

- pgcd(a, b) = pgcd(b, a)

- pgcd(a, 0) = a

Euclide étendu

Trouver les coordonnées du pgcd(a,b) dans le tableau des au + bv, c'est-à-dire déterminer u, v tels que au + bv = pgcd(a, b)

On pose 𝝋 : coordonnées (u, v) --> contenu de la cellule (u, v), ie.

𝝋 : { Z^2 --> Z,

(u,v) --> au + bv}

𝝋 est un morphisme. Les opérations effectuées sur le contenu des cases du tableau se transposent aux coordonnées de ces cases.

𝝋((u, v) + (u', v')) = 𝝋(u, v) + 𝝋(u', v')

𝝋(k(u, v)) = k x 𝝋(u, v)

Nombres premiers entre eux

a, b premiers entre eux lorsque pgcd(a, b) = 1

Si n est premier alors for all a, a est premier avec n ou a est un multiple de n

Théorème de Bézout

a et b premiers entre eux ssi there exists u,v tels que au + bv = 1

a, b sont premiers entre eux ssi :

- aZ + bZ = Z

- pour tout k, l'équation au + bv = k admet des solutions (u, v)

- la fraction a / b est irréductible

- a et b n'ont pas de facteur commun, à part 1

- a et b n'ont pas de facteur premier commun

- le ppcm de a et b est ab

Théorème de Gauss

si a et b premiers entre eux et a | bc, alors a | c

a est premier avec b et c ssi...

il est premier avec bc

Indicatrice d'Euler

Soit n E N*, 𝝋(n) est le nombre d'entiers naturels premiers avec n et inférieurs à n. La fonction 𝝋 est l'indicatrice d'Euler.

si p premier, alors 𝝋(p) =

p - 1

si n = p^k avec p premier, alors 𝝋(n) =

(1 - 1/p)n

si n = ab avec a et b premiers entre eux, alors 𝝋(n) =

𝝋(a)𝝋(b)

Anneaux Z/nZ

a ≡ b mod n ssi n divise a - b. a ≡ b n ce lit « a congru à b modulo n »

Z/nZ est l'ensemble des entiers dans lequel on considère égaux deux nombres a et b tels que n divise a - b, c'est-à-dire tels que a ≡ b mod n

a ≡ 0 mod n ssi...

a est un multiple de n

pour n > 0, modulo 10, n est congru au...

dernier chiffre de son écriture décimale

L'addition dans Z/nZ

L'addition dans Z/nZ est bien définie : si a ≡ a' mod n et b ≡ b' mod n alors a + b ≡ a' + b' mod n

La multiplication dans Z/nZ

La multiplication dans Z/nZ est bien définie : si a ≡ a' mod n et b ≡ b' mod n alors a x b ≡ a' x b' mod n

Éléments inversibles de Z/nZ

k inversible modulo n ssi k et n premiers entre eux.

k et n premiers entre eux :

- ssi there exists u,v tels que ku + nv = 1 (Bézout)

- ssi there exists u tel que ku = 1 mod n

- ssi k inversible modulo n

Expliquez pourqui, dans la représentation d'un produit dans Z/nZ, une ligne/colonne contient 1 ssi elle contient tous les nombres

Si la ligne de k contient 1, alors il existe u tels que ku = 1, alors quel que soit v, kuv = v, donc v apparaît dans la ligne de k

Le nombre d'inversible modulo n est...

𝝋(n)

le produit de deux inversibles est...

un inversible.

Démo 1 : Si k et k' inversibles, alors there exists u, u' tels que ku = 1 et k'u' = 1, alors kk'uu' = 1, donc kk' inversible

Démo 2 : Si k et k' inversibles, alors k et k' premiers avec n, donc kk' premier avec n.

Théorème d'Euler

pour tout k premier avec n, [k^𝝋(n)] = 1 mod n

Théorème de Fermat

si n est premier, alors 𝝋(n) = n - 1 et pour tout k non multiple de n, k^(n-1) = 1 mod n

Motivation du théorème des restes chinois

On veut résoudre « systèmes de congruences » :

{ x = a mod n

{ x = b mod m

Qu'est-ce que signifie ce système de congruence ?

{ x = 0 mod n

{ x = 0 mod m

x multiple commun de n et m. Si n, m premiers entre eux, x multiple nm

Définissez ψ

ψ : { Z/nmZ --> Z/nZ x Z/mZ

{ x --> (x mod n, x mod m)

Résoudre :

{ x = a mod n

{ x = b mod m

qui est équivalent à

{ a = x mod n

{ b = x mod m

qui est équivalent à ψ(x) = (a, b)

C'est de chercher les antécédents x de (a, b) par ψ

ψ est injective ssi...

n et m premiers entre eux

Si n et m premiers entre eux, alors...

ψ est bijective

ψ est injective d'un ensemble de cardinal nm vers un ensemble de même cardinal. Par le principe des tiroirs, ψ est aussi surjective.

Théorème des solutions de ψ

Si n et m sont premiers entre eux, le système

{ x = a mod n

{ x = b mod m

admet une unique solution modulo nm

ψ est une application...

linéaire. ψ est un morphisme de groupe : ψ(a + b) = ψ(a) + ψ(b)

Autrement dit, additionner les nombres (modulo nm) du tableau revient à additionner les vecteurs (modulo (n, 0) et (0, m)).

ψ(au + bv) = uψ(a) + vψ(b)

Algorithme pour résoudre

{ x = a mod n

{ x = b mod m

avec n et m premiers entre eux

1. Résoudre nu + mv = 1 par l'algorithme d'Euclide étendu

1. La solution (modulo nm) est bnu + amv

Injectivité

Une fonction f : X --> Y est dite injective si elle satisfait pour tout x1, x2 E X, (f(x1) = f(x2) --> x1 = x2)

Cela signifie que quelque soit y E Y, l'équation f(x) = y a au plus une solution x E X. On peut donc déduire x à partir de f(x).

Surjectivité

Une fonction f : X --> Y est dite surjective si elle satisfait pour tout y E Y, il existe x E X : f(x) = y

Cela signifie que quelque soit y E Y, l'équation f(x) = y a AU MOINS une solution x E X.

Si on pense à f comme une opération qui transforme x en f(x), la surjectivité signifie qu'on peut obtenir n'importe quel y E Y grâce à l'opération f. La surjectivité s'interprète comme le fait que l'ensemble de départ contient au moins autant d'éléments que l'ensemble d'arrivée.

Bijectivité

Une fonction f : X --> Y est dite bijective lorsqu'elle est à la fois injective et bijective, ce qui donne sous forme de proposition :

pour tout y E Y, il existe un unique x E X : f(x) = y

Cela signifie que quelque soit y E Y, l'équation f(x) = y a exactement une solution x E X, que l'on note f-1(y). Ceci définit une fonction f-1 : Y --> X appelée inverse ou réciproque de f.

La bijectivité s'interprète comme le fait que les ensembles de départ et d'arrivée contiennent autant d'éléments.

texte clair/message clair

message initial

message chiffré

texte trasmis

chiffrement

transformation du message clair en message chiffré, en général à l'aide d'un algorithme et une clé de chiffrement

cryptosystème

La description d'un algorithme, des clés, des messages qu'on peut chiffrer, etc.

Une instance d'un cryptosystème

ce qu'on utilise pour chiffrer

cryptosystèmes symétriques ou à clé secrète

une seule clé, qui est donc secrète. Ex: César, Vigenère, Enigma, DES, AES

cryptosystèmes asymétriques ou à clé publique

deux clés : une pour chiffrer (clé publique) et une pour déchiffrer (privée). Ex: RSA

RSA

Alice veut transmettre un message à Bob. Bob :

1. Choisit deux grands nombres premiers p et q. Il calcule n = pq

2. Choisit un entier e premier avec p-1 et q-1

3. Il diffuse (e, n), qui est la clé publique

4. Il calcule d, inverse de e modulo 𝝋(n) = (p - 1)(q - 1)

M message à transmettre, sous forme de...

Suite d'octets. On découpe M en blocs B1, B2... de k octets de sorte que 256^k < n, donc pour tout i, Bi < n

Théorème --> on calcule Bi'^d pour chaque bloc chiffré Bi'

Pour tout b E [0 ; n-1], (b^e)^d = b mod n

Comment calculer d, l'inverse de e modulo 𝝋(n)?

On a ed ≡ 1 mod 𝝋(n), donc ed + 𝝋(n)v = 1 pour un certain v. On obtient d (et v) grâce à l'algorithme d'Euclide étendu appliqué au couple (e, 𝝋(n)).

Test de Fermat

Ce teste utilise le fait que si n est premier, alors pour tout a non multiple de n, a^(n-1) ≡ 1 mod n. On ne fait le teste qu'avec quelques valeurs de a. Ce teste donne la bonne réponse, mais il est inefficace : il a un taux d'erreur qui diminue trop lentement lorsque le nombre de bases augmente.

Écrire l'algorithme du test de Fermat

def premierprobable(n)

L = [2, 3, 5, 7, 11, 13, 17, 19]

for a in L:

if pow(a, n-1, n) != 1

return False

return True #probablement premier

Teste de Miller-Rabin

Idée principale --> si n est premier, alors les seules solutions de x^2 = 1 dans Z/nZ sont 1 et -1.

Si a^(n-1)/2 = 1 mod n et (n-1)/2 pair : on peut recommencer a^(n-1)/4 = +- 1 mod n

Si n premier, alors les nombres (modulo n) a^(n-1), a^(n-1)/2, a^(n-1)/4... (on continue tant que (n-1)/2^k entier) sont :

- soit 1, 1....1, -1...

- soit 1, 1, 1, .... 1

Précision du teste de Miller-Rabin

On pourrait montrer que :

a) Si n se comporte « comme un nombre premier » vis-à-vis de la base a, alors la probabilité qu'il soit composé est < 1/4.

b) S'il se comporte « comme un nombre premier » vis-à-vis de k bases tirées aléatoirement, alors la probabilité qu'il soit composé est < 4^-k

Écrire l'algorithme du teste de Miller-Rabin

def MillerRabinBase(n, a)

e = n-1

if pow(a, e, n) != 1 : return False

while e % 2 == 0 :

e //= 2

p = pow(a, e, n)

if p == -1 : return True

if p != 1 : return False

return True

def MillerRabin(n) :

for i in range(50) :

a = random.randint(2, n)

if not(MillerRabinBase(n,a)):

return False

return True

Pour obtenir un grand nombre premier (de 450 chiffres)...

1. Choisir au hasard un nombre n de 450 chiffres

2. Effectuer un teste de Miller-Rabin avec 50 bases tirées aléatoirement

3. Si n échoue (fail) à l'un de ces testes, aller en 1

4. Sinon considérer que n est premier

Le théorème des nombres premiers (2)

Il faut en moyenne 1000 essais avant de tomber sur un nombre premier (réduit à 207 si on écarte directement les multiples de 2, 3, 5, 7, 11)

Pourquoi l'exponentiation modulaire est-elle importante ?

Pour appliquer Milller-Rabin ou Fermat, et pour chiffrer/déchiffrer un message, il faut pouvoir calculer a^n mod m efficacement pour des grandes valeurs de n.

L'exponentiation rapide, version récursive

def expmod(a, n, m)

# calcul de a^n mod m

if n == 0 : return 1

if n % 2 == 0

return expomod(a, n//2, m) ** 2 % m

return (a expomod(a, n//2, m) * 2) % m )

L'exponentiation rapide, version itérative

def expomod(a, n, m) :

# écriture de n en binaire

L = []

while n != 0 :

L.append(n%2) ; n //= 2

L.reverse() #poids fort en tete

p = 1

for c in L :

p = p ** 2 % m

if c == 1 : p = p * a % m

return p

Comment calculer le nombre de multiplications effectuées dans l'exponentiation rapide ?

Le nombre de chiffres binaires de n plus le nombre de 1 de l'écriture binaire de n.

l'efficacité de RSA

Même avec l'exponentiation rapide, RSA est lent, environ 1000 fois plus lent que les cryptosystèmes symétriques.

l'usage de RSA

On se sert de RSA pour l'authentification des messages, les certificats, les signatures, mais pas pour chiffrer les messages eux-mêmes

Pourquoi utiliser les cryptosystèmes symétriques ?

pour chiffrer les messages

Quels sont les types d'attaques contre le RSA ?

1. Attaque par la méthode de Pollard

2. Attaque de Hastad (choix de e)

3. Risques causés par le problème du déterminisme

4. L'authentication

Quelle taille des nombres premiers à utiliser pour RSA ?

De 3000 chiffres binaires pour n, donc p et q de 1500 chiffres binaires (450 chiffres décimaux)

Attaque par la méthode de Pollard

Aussi appelé la méthode p - 1 de Pollard : si n = pq et p - 1 (ou q - 1) « B-superfriable » avec B petit, alors on peut factoriser n relativement facilement.

Nombre B-superfriable

dont tous les facteurs de la forme a^n avec a premier sont inférieurs à B

Comment combattre les attaques par la méthode Pollard ?

Assurer que p - 1 et q - 1 possèdent un grand facteur premier

Attaque de Hastad

Si le même e, petit, est utilisé dans plusieurs clés publiques (e, ni), et si un message est chiffré par ces clés, alors on peut retrouver le message initial.

Comment combattre l'attaque par Hastad ?

Prendre e > 65536 ; ne pas envoyer le même message chiffré avec le même e

Le problème du déterminisme

Le chiffrement est déterministe : un même bloc sera codé toujours de la même manière

Comment résoudre le problème du déterminisme ?

Insérer des octets aléatoires dans les blocs

Le problème d'authentification (RSA)

La clé de chiffrage est publique : comment savoir que le message reçu par Bob est bien envoyé par Alice ?

Objectifs de la signature

1. Authentification de l'émetteur : seule Alice peut signer le message

2. Non-répudiation : Alice ne peut pas nier avoir signé le message

3. Vérification d'intégrité : une signature est liée à un message ; on ne peut pas réutiliser la même signature pour deux messages différents.

Fonction de hachage

Une fonction H qui prend un message quelconque M et rend un message court M' = H(M) appelé hash ou résumé ou condensat de M. Ex : MD5, SHA256

Contrainte de la fonction de hachage

Connaissant M', il est impossible en pratique de déterminer un M tel que H(M) = M'

Signature numérique

Fondée sur une fonction de hachage.

1. Alice calcule elle aussi une clé publique (e', n') et une clé privée (d', n')

2. Alice et Bob conviennent d'une fonction de hachage H

3. En plus de M' (M chiffré avec la clé (e, n) de Bob), Alice envoie H' = H(M)^d' mod n'

4. Bob reçoit M', le déchiffre, obtient M, calcule H(M) et H'^e' mod n'

5. SI H(M) = H'^e' mod n', alors celui qui a émis le message ne peut pas être qu'Alice.