Génération des clés pour cryptosystèmes symétriques basée sur les bits pseudo-aléatoires

I.6.1.Le symbole de Legendre

Soit un premier. Pour un entier , on définit le symbole de Legendre

Lemme 1

Preuve

Ceci est équivalent de dire que, le produit de deux résidus quadratiques (respectivement non-résidu ) est un résidu quadratique , et le produit d'un résidu quadratique et un non-résidu quadratique est un non résidu quadratique .

Pour un premier impair , . Ceci est une répétition du théorème 2 que -1 est un résidu quadratique si et seulement si

Théorème (Euler)

Soit un premier impair. Pour chaque entier non divisible par

Preuve

Supposons que est un non-résidu quadratique . Les résidus quadratique sont partitionnés en pairs en satisfaisant l'équation . Dans ce cas,

Cas l'autre sens, si est un résidu quadratique, avec à part 0, , le reste de éléments de peut être partitionné en pairs satisfaisant

En résumant, on obtient

Notons qu'en mettant on obtient le théorème de Wilson : Par comparaison, on obtient une formule pour :

I.6.2.Le symbole de Jacobi

Définition

Le symbole de Jacobi est une généralisation du symbole de Legendre utilisant la décomposition en produit de facteurs premiers du nombre du dessous. Sa définition est la suivante :

Soit un entier impair supérieur à 2 et la décomposition de n en facteurs premiers.

Alors, pour tout entier , le symbole de Jacobi vaut :

Propriétés du symbole de Jacobi

Le symbole de Jacobi possède de très nombreuses propriétés :

1. Si est premier, le symbole de Jacobi et le symbole de Legendre sont équivalents.

2.

3. si et seulement si et ne sont pas premiers entre eux.

4. si est impair.

5. Si alors si est impair.

6.

7. vaut 1 si et -1 si

8. vaut 1 si ou et -1 si ou

si et sont impairs, autrement dit sauf si et sont tous deux congrus à auquel cas

Les énoncés généraux sur les résidus quadratiques faisant intervenir le symbole de Legendre ne s'étendent pas au symbole de Jacobi. Cependant, si alors n'est pas un résidu quadratique de puisque n'est pas le résidu quadratique d'un des divisant .

Dans le cas où , il est impossible de dire si est un résidu quadratique de . Puisque le symbole de Jacobi est un produit de symboles de Legendre, il y a des cas ou deux symboles de Legendre sont égaux à -1 et le symbole de Jacobi est égal à 1.

[5], [12], [13], [14], [15], [17], [18], [20]

CHAPITRE II : GENERALITES SUR LA CRYPTOGRAPHIE

II.1 Définitions

Cryptologie: Science des messages secrets, elle est composée en deux disciplines: la Cryptographie et la cryptanalyse.

Cryptographie: Art de transformer un message clair en un message inintelligible par celui qui ne possède pas les clés de chiffrement.

Cryptanalyse: Art d'analyser un message chiffré afin de le décrypter.

Chiffrement: Procédé qui consiste à transformer une donnée (généralement un message texte) afin de la rendre incompréhensible à toute personne qui ne connait pas la clé.

Déchiffrement: Procédé qui consiste à retrouver le texte clair à partir du texte chiffré.

Cryptogramme: Texte chiffré ou message chiffré.

Clé: Séquence sécrète en bits qui permettent de chiffrer ou de déchiffrer un message donné.