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

EPIGRAPHE

Si les mathématiques offraient mille exemples différents d'une même règle, la preuve d'un seul de ces exemples démontrerait l'exactitude de tous les autres.

« MARY BAKER Eddy»

DEDICACE

A l'Eternel, Père-Mère Dieu ;

A toute ma famille ;

A ma future épouse.

Je dédie ce travail.

REMERCIEMENTS

Nos sincèrement remerciements au Professeur Dr. MANYA NDJADI Léonard, qui a bien voulu assurer la direction de ce travail malgré ses multiples occupations.

Nous pensons également à tous les Professeurs, Chefs des travaux et Assistants de la Faculté des Sciences en Générale et du Département de Mathématiques et Informatique en particulier, pour la formation qu'ils ont assurée durant toutes ces années d'études.

Nous pensons aussi à tous nos compagnons de lutte.

Enfin, nous remercions très sincèrement toutes les personnes qui ont contribué d'une manière où d'une autre pour la réussite de nos études.

INTRODUCTION

Les nombres aléatoires jouent un rôle important en cryptographie. Ils sont utilisés pour générer des clés, à chiffrer les messages ou à masquer les contenus de certains protocoles en les associant avec une séquence aléatoire. Claude Shannon a montré que dans un système cryptographique, si la clé est générée de manière aléatoire et que cette clé n'est plus utilisée, alors ce système est parfaitement sûr.

On distingue deux types des générateurs de nombres : les générateurs de nombres aléatoires non déterministes et les générateurs de nombres aléatoires déterministes. Les générateurs de nombres aléatoires non déterministes sont basés sur des mécanismes physiques tels que le lancer des dés, roulette, le bruit thermique dans les résistances de circuits électroniques, etc. La reproduction d'une séquence du générateur non déterministe est impossible. Tandis que les générateurs de nombres aléatoires déterministes sont basés sur des moyens mathématiques, la séquence est initialisée par une valeur appelée germe ou graine. La reproduction de la séquence est possible.

Dans ce travail, nous étudions comment produire une séquence binaire aléatoire cryptographiquement sûr, indépendante, imprédictible et équiprobable à utiliser pour clés au chiffrement par flot ou au chiffrement de Verman.

Notre travail est subdivisé en quatre chapitres. Dans le premier chapitre, nous parlons des quelques éléments de la théorie des nombres. Nous avons beaucoup plus détaillé la notion des résidus quadratiques qui constitue l'outil de base du générateur utilisé. Dans le second chapitre, nous présentons les généralités sur la cryptographie et ensuite nous présentons l'aspect d'un système cryptographique parfaitement sûr. Le troisième chapitre concerne les générateurs pseudo-aléatoires. Nous avons présenté quelques générateurs pseudo-aléatoires ; ensuite nous nous sommes concentrés sur le générateur utilisé : Blum-Blum-Shub. Et enfin, au quatrième chapitre, nous présentons l'implémentation du générateur Blum-Blum-Shub et l'interprétation des résultats obtenus.

[1], [2], [3], [13], [14], [15], [16]

CHAPITRE I : ELEMENTS DE LA THEORIE DES NOMBRES

I.1.Quelques notions de base

Définition

Un entier est dit premier s'il est différent de et s'il n'admet aucun diviseur positif différent de et .

Un nombre qui n'est pas premier est appelé nombre composé.

Proposition

Il existe une infinité de nombres premiers

Preuve

Montrons par l'absurde. Supposons qu'il n'existe qu'un nombre fini

d'entiers premiers, soit . On peut alors montrer un entier qui n'est divisible par aucun de ces nombres premiers, ce qui est contradictoire compte tenu du fait que cet entier possède un diviseur premier. En effet, considérons : si divisait , alors diviserait , ce qui est absurde.

Lemme de Gauss.

Si des entiers et sont tels que divise et premier avec

alors divise .

Preuve

Comme est premier avec , on peut écrire pour des entiers . Ainsi et comme divise (car il divise ) et (car il divise ), il divise la somme qui vaut .

Théorème (Décomposition en facteurs premiers)

Ce théorème est appelé théorème fondamental de l'arithmétique.

Soit un entier se décompose d'une et d'une seule manière en un produit de nombres premiers. Autrement dit, pour tout entier , il existe des nombres premiers deux à deux distincts et des

entiers strictement positifs , uniquement déterminés à l'ordre près, tels que :



Preuve

Le théorème reste bien vrai pour : il faut choisir , le produit d'aucun entier étant par convention égal à 1.

Commençons par l'existence de la décomposition. On raisonne par récurrence sur . Pour alors ça s'écrit comme un produit de nombres premiers, étant lui-même premier.

Soit un entier. Supposons que tous les entiers strictement inferieurs à s'écrivent comme le précise le théorème et montrons que la conclusion subsiste pour l'entier . Il y a deux cas : soit est premier, soit il ne l'est pas. Le premier cas est vite réglé : premier s'écrit bien comme un produit de nombres premiers. Supposons donc que soit composé.

Ainsi, il s'écrit avec et . Les entiers et relèvent de l'hypothèse de récurrence et on peut écrire :





pour des nombres premiers et Il ne reste plus qu'à effectuer le produit pour conclure.

Montrons l'unicité :

Supposons que Pour certains nombres premiers et .

On veut montrer que et que les sont égaux aux à l'ordre près.

Raisonnons ensuite par l'absurde. Le nombre premier divise le produit donc par le lemme précédent, il divise .

Or, les diviseurs de (qui est premier) ne sont que 1 et . Comme il ne reste plus que la possibilité On peut alors simplifier l'égalité :



en divisant par ,on obtiens une contradiction et l'unicité est prouvé.

I.2. La congruence

Définition

Soient et des entiers, alors on dit que est congru à modulo , ce qui s'écrit si ; est le module de la congruence.

Propriétés de la congruence



- et ont le même reste dans la division par

- (réflexivité).

- (symétrie).

- et (transitivité).

- et

I.3. Classes des résidus

Soit Pour chaque entier on définit , en d'autres termes est l'ensemble de tous les entiers qui sont congrus à modulo . Les autres auteurs appellent la classe congruence ou la classe d'équivalence de modulo

Théorème.

Pour on a : .

Preuve

Supposons

pour tout . Notons que dépends de

On a deux façons d'écrire l'équation ci-haut :

ou

Tout élément est une représentation de la classe de résidu .

I.4. Ensemble réduit des résidus

Définition

On défini , alors est l'ensemble de toutes les classes modulo . Nous appelons l'anneau des entiers .

 

Addition et multiplication dans

Pour , on a :

et

Exemple

Pour

et

Notons que puisque et ,nous avons et . Nous pouvons aussi écrire et

I.5. La fonction d'Euler ou fonction totient

Définition

Pour ,soit le nombre d'entiers premiers avec dans l'intervalle . La fonction est la fonction d'Euler.

Exemple

Pour , il y a différentes classes de résidu modulo  ; les classes et ne sont pas premiers avec  ; ainsi seules les classes et sont premiers avec  :alors .

Si est un premier, toutes les classes sont premiers avec  , alors

Exemple :

	2	4	5	6	7	8	9	10	12	15
	2	2	4	2	6	4	6	4	4	8

Théorème (Euler)

Soit , alors

Ceci permet de calculer l'inverse modulaire définit par :



Exemple

Quel est l'inverse de on sait que

On a d'où

Théorème (Petit théorème de Fermat)

Soit un premier et un entier tel que alors

Preuve

Considérons les entiers suivants : ainsi que leurs restes dans la division euclidienne par notés : Ces restes sont compris entre

En effet, d'après le même de Gauss, si divisait un des ces produits diviserait puisque et sont premiers entre eux, mais ceci est impossible puisque De plus les restes de division de par sont tous différents. Si on trouvait des restes identiques pour et alors le reste de par serait nul, ce qui est impossible d'après ce qui précède.

Notons que ces restes sont donc des entiers compris entre et .

En multipliant membre à membre les congruences :



Alors nous obtenons :





Par définition de la congruence, cette égalité signifie que divise Or ne divise aucun des entiers il est également premier avec leur produit

Ainsi d'après le lemme de Gauss divise c'est-à-dire .

Théorème de Wilson

Si est un premier, alors

Preuve

Considérons la congruence Alors , ainsi les seules solutions sont et Donc, pour chaque , il existe qu'un inverse unique de , . Ainsi lorsque nous groupons des inverses en pairs, nous obtenons :







Théorème du reste Chinois

Soit des entiers et des entiers relativement premiers entre eux, alors le système des congruences

,











admet une unique solution modulo

Preuve

Soit ,et considérons .Ceci est relativement premier à ainsi il existe un entier tel que .

En conséquence, soit . Alors et D'une manière similaire, il existe un tel que et , Alors est une solution du système ci-haut.

Soit une autre solution, alors

pour tout

I.6. Résidus quadratiques

Soit un entier positif , et tel que

On dit que est un résidu quadratique si tel que .

Si un tel n'existe pas, est un non-résidu quadratique .

Avec

- Si et sont des résidus quadratique ,alors leur produit est

- Si est un résidu quadratique , et un non-résidu quadratique , alors est un non-résidu quadratique

- Le produit de deux résidus quadratiques n'est pas nécessairement un résidu quadratique .

Théorème 1

Soit un nombre premier impair. Exactement la moitie des éléments de sont des résidus quadratiques.

Preuve

Chaque résidu quadratique modulo est congru à un des résidus suivants :



On montre que ces classes des résidus sont tous distincts. Pour , si et seulement si est divisible par , ceci est impossible puisque chacun de et est petit que .

Corollaire 1

Soit un nombre premier impair, le produit de deux non résidus est un résidu quadratique.

Théorème 2

Soit un nombre premier impair. est un résidu quadratique si et seulement si .

Preuve

Si , alors par le petit théoreme de Fermat :

. Ceci signifie que est pair, et . Inversement si , l'entier est pair. Par le théorème de Wilson,



Les solutions de sont donc .

Voici les racines carrés de pour les 20 premiers nombres premiers de la forme :

	5	13	17	29	37	41	53	61	73	89	97	101	109	113	137	149	157	173	181	193

Théorème 3

Il y a une infinité des nombres premiers de la forme

Preuve

Supposons qu'il y a une finité des nombres premiers de la forme Considérons le produit

Notons que . Puisque est grand que chaque , il ne peut pas être premier, ainsi il doit y avoir un facteur premier différent de Mais alors modulo ,-1 est une racine. Par le théorème précédent, doit être de la forme , une contradiction.

Dans la table ci-dessus nous montrons pour les nombres premiers , les résidus quadratiques ainsi que leurs racines carrés. Il est à noter que les racines carrées entrent en pairs. Par exemple, l'entrée (2,7) pour le nombre premier 47 serait interpréter comme disant que les deux solutions de la congruence sont Aussi, pour les nombres premiers de la forme , puisque -1 est un résidu quadratique modulo , on liste seulement les résidus quadratiques plus petit que . Ceux qui sont plus grands que peuvent être trouvé avec l'aide des racines carrés de -1.

3	(1,1)
7	(-1,2) (1,1) (2,3) (4,2)
11	(1,1) (3,5) (4,2) (5,4) (9,3)
13	(-1,5) (1,1) (3,4) (4,2)
17	(-1,13) (1,1) (2,6) (4,2) (8,5)
19	(1,1) (4,2) (5,9) (6,5) (7,8) (9,3) (11,7) (16,4) (17,6)
23	(1,1) (2,5) (3,7) (4,2) (6,11) (8,10) (9,3) (12,9) (13,6) (16,4) (18,8)
29	(-1, 12) (1,1) (4,2) (5,11) (6,8) (7,6) (9,3) (13,10)
31	(1,1) (2,8) (4,2) (5,6) (7,10) (8,15) (9,3) (10,14) (14,13) (16,4) (18,7) (19,9) (20,12) (25,5) (28,11)
37	(-1, 6) (1,1) (3,15) (4,2) (7,9) (9,3) (10,11) (11,14) (12,7) (16,4)

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é.

II.1.1. Définition d'un système cryptographique

Soit un ensemble fini, appelé l'alphabet de définition.

Soit un ensemble appelé l'espace des messages clairs.

Soit un ensemble appelé l'espace des messages chiffrés.

Soit un ensemble appelé l'espace des clés.

Chaque , détermine une injection de vers , appelée fonction de chiffrement, est appelé clé de chiffrement.

A chaque est associé un , tel que dénote une injection de vers , appelée fonction de déchiffrement, est appelé clé de déchiffrement.

Un système cryptographique (cryptosystème) est un quintuple tel que



II.2 Cryptosystème symétrique et asymétrique

II.2.1 Cryptosystème symétrique

Les algorithmes de cryptographie symétrique utilisent les mêmes clés lors du chiffrement et du déchiffrement.

Considérons un ensemble fini de fonctions de chiffrement et un autre ensemble fini de fonctions de déchiffrement , nous avons:

Dans un système symétrique, la sécurité repose sur la clé. La clé doit rester inconnue aux tierces personnes. La génération des clés est choisie d'une manière aléatoire dans l'espace des clés.

L'avantage du cryptosystème symétrique est basé sur sa rapidité et son désavantage réside dans la distribution des clés. Pour un système à utilisateurs, il y aura paires des clés.

II. 2.1.1 Exemples des chiffrements symétriques

II.2.1.1.1 Chiffrement symétriques classiques

Identifions l'alphabet usuel avec par et les opérations sont réalisées dans

1. Chiffrement par décalage

Soit

Soit

Et soit et

et

Ainsi pour nous avons le chiffrement de César.

Exemple: Avec , le texte clair  '' politique'', nous obtenons le texte chiffré '' srolwltxh''

Ce système de chiffrement est facilement cassable puisque l'espace des clés ne contient que 26 éléments (26 clés possibles).

2. Chiffrement par substitution

Soit

L'espace des clés est l'ensemble des permutations de .

Chacune des lettres est remplacée par une autre lettre de l'alphabet.

Pour , nous avons :

et

où et est la permutation inverse de

Le nombre de clés possibles est , une recherche exhaustive n'est pas possible. Cette méthode est facilement cassable suite à la fréquence des lettres.

Exemple:

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

p

q

r

s

t

u

v

w

x

y

z

f

l

h

j

a

r

c

p

u

x

d

i

q

y

m

k

b

t

g

w

n

z

s

v

o

e

Soit la permutation suivante :

Le texte clair ''symétrique'' est chiffré en '' goqawtubna'

3. Chiffrement du Vigenère

Soit

Soit

Soit

Alors

et

où

Le nombre de mots-clés possibles de longueur est , une recherche exhaustive est impossible.

Exemple:

Soit le mot en clair '' Faculté '' et la clé '' Ornela ''

Texte claire	f	a	c	u	l	t	e
	5	0	2	20	11	19	4
Clé	o	r	n	e	l	a	o
	14	17	13	4	11	0	14
Texte chiffré	19	17	15	24	22	19	18
	t	r	p	y	w	t	s

4. Chiffrement par permutation

Soit

Soit

Soit l'ensemble des permutations de

Pour nous avons :

et



où et est la permutation inverse de

Exemple :

Si et est la permutation qui envoie ( sur alors le texte clair `' cryptographie '' est chiffré en `' prctoyprghea `'.

5. Chiffrement de Verman

Le chiffrement de Verman est aussi appelé Masque jetable, en Anglais One- time pad est définit sur les bits,

Ainsi pour un message binaire est modifié par une clé binaire de même taille, comme suit:





Le chiffrement est incassable si la clé est choisie aléatoirement, et si cette même clé n'est plus jamais utilisée.

Exemple:

Soit le message clair `' 101001101110101 `' et la clé `' 100111101110110 ''

On a :





I.2.1.1.2 Chiffrement par bloc

Un chiffrement par bloc est une fonction prenant en paramètre une clé et un texte clair d'une longueur finie. Alors génère un texte chiffré de longueur finie à partir d'un message clair et d'une clé.

Principe:

1. Remplacer les caractères du message par des bits

2. Segmenter cette chaine en blocs de chacun n bits

3. Chiffré successivement chaque bloc:

- Appliquer l'opération logique bit par bit avec une clé

- Déplacer certains bits du bloc

- Recommencer un certain nombre de fois l'opération 3.

4. Passer au bloc suivant et retourner au point 3 jusqu'à ce que tout le message soit chiffré.

Il existe trois catégories de chiffrement par bloc:

- Chiffrement par substitution

- Chiffrement par transposition

- Chiffrement par produit

1. Chiffrement par substitution

Le chiffrement par substitution consiste à remplacer les symboles par d'autres symboles.

Exemple:



Fig.1.Exemple de chiffrement par substitution

2. Chiffrement par transposition

Le chiffrement par transposition est un chiffrement dans lequel est réalisé une permutation sur les symboles de chaque bloc à chiffré.



Fig.2.Exemple de chiffrement par transposition

Exemple:

3. Chiffrement par produit

Le chiffrement par produit est la combinaison du chiffrement par substitution et du chiffrement par transposition.

Le chiffrement par substitution ou par transposition ne garantie pas un niveau de sécurité élevée, on obtient en combinant ces deux transformations, un chiffrement ayant un niveau de sécurité élevée.

Les algorithmes les plus utilisés sont: DES, 3DES, AES, RC5.

Exemple



Fig.3.Exemple de chiffrement par produit

II. 2.1.1.2 Chiffrement par flot

Le chiffrement par flot est un chiffrement par bloc de longueur égale à un. Cette opération s'effectue sur chaque caractère, bits. La structure d'un chiffrement par flot réside sur un générateur de clés qui produit une séquence des clés (voir chapitre 3). C'est la qualité du générateur qui détermine la sécurité du chiffrement par flot. Si la séquence des clés est infinie et aléatoire, on a un One-time pad.

Texte

Clair

Texte

Clair



Clé k

Chiffrement

Texte

Chiffré



Clé k

Déchiffrement

Fig.3. Schéma du chiffrement à flot

Une erreur dans n'affecte qu'un bit de . La perte ou l'ajout d'un bit de affecte tous les bits suivants de après déchiffrement.

II.2.2 Cryptosystème asymétrique

Dans un Cryptosystème asymétrique, chaque interlocuteur possède deux clés, l'une étant privée (secrète) et l'autre publique, elles sont mathématiquement liées avec impossibilité de déduire la clé privée à partir de la clé publique. La clé privée doit rester secrète tandis que la clé publique sera distribuer; la clé publique permet de chiffré un message et la clé privée permet de déchiffré un message.

Soit un ensemble fini de fonctions de chiffrement et de déchiffrement

, pour toutes paires de transformation , il est impossible (ou très difficile) de trouver le message clair tel que

Considérons deux interlocuteurs Alice et Bob qui désirent communiquer ensemble, Bob sélectionne une paire de clés et envoie à Alice. Alice après avoir reçu , envoie un message à Bob. Alice calcule puis le fait parvenir à Bob. A la réception, Bob calcule la transformation inverse .

II.2.2.1 Exemples de chiffrement asymétrique

Nous distinguons plusieurs méthodes de chiffrements asymétrique tels que : RSA, CCE, Rabin, El Gamal, Mc Eliece, Merkle-Hellman, Gold wasser-Micali, etc.

- Méthode RSA

RSA est basé sur le calcul exponentiel; sa sécurité repose sur la fonction unidirectionnelle et la difficulté de factoriser un grand nombre en deux facteurs premiers.

a. Génération des clés

- choisir aléatoirement deux grands premiers distincts et approximativement de la même taille

- calculer et

- choisir un entier aléatoire dans tel que

- calculer l'unique tel que

- La clé publique est et la clé privée est

b. Chiffrement

Soit le message à chiffrer,

Calculer

c. Déchiffrement

est déchiffré en calculant :

Exemple :

Considérons et très petits, et

Nous avons :





On peut choisir (7 est premier avec 40)

On calcule tel que :



On obtient :

Clé publique :

Clé privée :

Soit le texte clair à chiffrer `' IMAGE `'

I	M	A	G	E
9	13	1	7	5

1. Chiffrement

- I :

- M :

- A :

- G :

- E :

2. Déchiffrement

- 14 :

- 52 :

- 1 :

- 13 :

- 15 :

La distribution des clés ne pose pas problème, chaque utilisateur possède une paire de clés. L'utilisateur après avoir chiffré le message du destinataire ne sera plus capable de déchiffrer son propre message, seul le détenteur de la clé gardée secrète pourra déchiffrer le message. On utilise le chiffrement asymétrique aussi pour chiffrer les nombres aléatoires qui servent de clés secrètes pour les algorithmes de chiffrement symétrique; on l'utilise également pour assurer l'authenticité d'un message.

II.3. Sécurité d'un système cryptographique

On distingue deux approches fondamentales dans l'étude de la sécurité d'un cryptosystème : la sécurité parfaite de Shannon et la sécurité calculatoire.

II.3.1. Notions élémentaires de probabilité

Définition classique de probabilité

Considérons une expérience aléatoire possédant la symétrie mutuelle et un événement quelconque relatif à La probabilité de l'événement est le nombre , où est le nombre de cas favorables à et le nombre total des éventualités rattaché à l'épreuve.

Définition axiomatique de probabilité

Une mesure de définie sur un espace probabilisable , l'application qui vérifie les 3 axiomes suivants :

1.

2. Si pour

alors ;

3.

Le triplet est appelé espace probabilisé.

Probabilité conditionnelle

Soient et deux événement telque

On appelle probabilité conditionnelle de l'événement par rapport à l'événement , ou encore la probabilité de A étant donné B :



La probabilité conditionnelle nous permet de calculer la probabilité de l'intersection :



Indépendance stochastique des événements

Deux événements et sont indépendant si



si et et que les événement et sont indépendants alors

Les événements sont indépendants si



Théorème de Bayes

Si est un système complet d'événements et est un événement quelconque.

Supposons que puisse se produire qu'en combinaison avec l'un des événements de , c'est-à-dire .

, alors on a la formule de Bayes



Preuve. Voir [12]

II.3.2. La sécurité calculatoire

La sécurité calculatoire est basée sur la mesure de la quantité de calcul nécessaire pour casser un système. On dit qu'un procédé est sûr au sens de la théorie de la complexité si le meilleur algorithme pour le casser nécessite opérations où est un nombre beaucoup trop grand pour que cet algorithme soit applicable en pratique. Dans la pratique, on dit souvent qu'un système est sûr si la meilleure attaque connue ne peut se faire avec une quantité raisonnable de temps de calcul. Le problème de cette approche c'est qu'un cryptosystème peut être sûr pendant un moment puis ne plus l'être lorsque l'on découvre un algorithme plus efficace.

II.3.3 La sécurité parfaite de Shannon

Claude Shannon en 1949 dans son article intitulé « Communication Theory of Secrecy System » introduit la notion des systèmes cryptographiquement sûrs, qui eut une influence considérable sur l'étude de la cryptographie.

Considérons l'ensemble fini de textes clairs, l'ensemble fini de textes chiffrés, l'ensemble fini de clés.

Supposons qu'une clé est utilisée une et une seule fois.

Notons que l'ensemble des textes clairs est muni d'une probabilité ainsi que l'ensemble des clés muni d'une probabilité

Supposons que les clés sont choisies indépendamment des textes clairs.

Ainsi les deux probabilités et induisent une probabilité sur l'ensemble des textes chiffrés Nous pouvons calculer la probabilité que le texte chiffré soit transmis.

Pour une clé , notons que représente l'ensemble des textes chiffrés avec la clé nous définissons

, qui est l'ensemble de toutes les clés possibles qui permettent d'obtenir le chiffré

Nous avons alors la probabilité de donnée par :



L'événement « le texte chiffré est  » n'est possible que si ou .

La probabilité d'avoir le « texte chiffré  » est la somme de toutes les probabilités mutuelles les événements « le texte clair est » et « la clé est » sont supposés indépendants, alors cette probabilité est égale à .

et ,nous pouvons calculer la probabilité conditionnelle (la probabilité que soit le texte chiffré en sachant que est la texte clair) par  où .

En utilisant le théorème de Bayes, nous avons :



II.3.4. Système cryptographique parfaitement sûr

Un système cryptographique parfaitement sûr si on a :

En d'autres termes : la probabilité que le texte clair soit sachant que le texte chiffré est est égale à la probabilité que le texte clair soit Dans ce cas le texte chiffré n'apporte aucune information sur le texte clair.

Lemme 1

Un système cryptographique vérifiant la propriété de sécurité parfaite et tel que alors :

Démonstration

Fixons tel que , on a :

, d'après le théorème de Bayes :

donc ceci signifie qu'il exite au moins une clé telle que .

Par suite , comme est injective on a :

Théorème

Un système cryptographique vérifiant ainsi que

il est à la sécurité parfaite si et seulement si les deux conditions suivantes sont réalisées :

a. Toutes les clés sont équiprobables,

b. Pour chaque et chaque existe une unique clé vérifiant .

Démonstration

Supposons les conditions vérifiées. Alors , on a successivement :



= ,

=

D'autre part pour et , puisqu'il n'y a qu'une clé qui vérifie on a :



En appliquant le théorème de Bayes :



La sécurité est donc parfaite.

Réciproquement, supposons que la sécurité est parfaite. Comme dans le lemme précédent, on montre que pour chaque couple , il existe une clé telle que .

Pour fixé on a donc ce qui montre que pour fixé l'ensemble des est de cardinal . Ces sont donc distincts deux à deux et pour chaque la clé vérifiant est unique.

Pour deux clés et , comparons et . Pour cela fixons et désignons et les uniques éléments de vérifiant et (chaque est injective et donc ici bijective.

Par le théorème de Bayes, et à la sécurité parfaite on obtient :



Le même calcul peut être fait avec Ce qui prouve que Les clés sont donc équiprobables.

Exemple

Le chiffrement de Verman ou le one-time-pad ou encore le masque jetable vérifie les conditions du théorème précédent. C'est un système parfaitement sûr. Il utilise une clé secrète très longue (séquence aléatoire binaire) où chaque bit est indépendant des autres et une probabilité d'être ou . Une nouvelle clé est utilisée à chaque chiffrement, la clé est aussi longue que le texte clair. La construction de cette clé aussi longue sera l'objet de notre chapitre suivant.

[4], [6], [7], [8], [9], [10], [11], [14] , [17], [19],[20], [21], [22], [23], [24],[25], [26], [27]

CHAPITRE III : GENERATEURS PSEUDO-ALEATOIRES

Définition

Soit un ensemble fini appelé espace d'états, un générateur pseudo-aléatoires est défini par :

,

et l'état s'évolue selon : ,

l'état initial s'appelle germe ou graine.

Autrement dit un générateur pseudo-aléatoire est un procédé qui, à partir d'une initialisation de taille fixée appelée germe ou graine, engendre de manière déterministe une séquence de très grande longueur.

Cette séquence consiste à imiter une séquence de variables aléatoires.

Définition

Une séquence binaire constituée de bits est dite aléatoire lorsque les bits sont indépendants, imprédictibles et équiprobables.

Un générateur de nombres pseudo-aléatoires et un générateur de bits aléatoires ont pour buts de générer une séquence de mots aléatoires. Les mots appartiennent à l'alphabet fini Dans le cas d'un générateur de bits aléatoires, l'alphabet est de dimension 2 c'est.-à-dire.

On distingue plusieurs générateurs pseudo-aléatoires tels que Générateur à congruence linéaire, Générateur carré-médian, Générateur à congruence additive, Générateur de type « multiplication avec retenue », Générateur de Blum-Blum-Shub ou Générateur quadratique etc....

III.1. Exemples de quelques générateurs pseudo-aléatoires

1. Générateur à congruence linéaire

Le générateur à congruence linéaire est un algorithme inventé par Lehmer en 1948. C'est une suite définie par la relation suivante :



où est appelé multiplicateur, est l'incrément, et est le module (le maximum plus un des nombres de la suite). La suite est initialisée par le germe . Tous ces nombres sont positifs.

Pours avoir une période maximale, les paramètres suivants doivent être respecté avec non nul :

- et doivent être premiers entre eux

- doit être multiple de , nombre premier diviseur de

Exemple :

Avec , la suite est :

2. Générateur carré-médian

Le générateur carre-médian est construit de la manière suivante : on élève au carré un nombre de -chiffres et on prend les -chiffres du milieu du produit (de chiffres). Il fut historiquement l'un des premiers générateurs utilisés mais c'est un très mauvais générateur ; si l'on tombe sur zéro tous les autres termes de la suite seront nuls et de manière générale sa période est trop courte.

Exemple :

	12	14	19	36	29	84	5	2	0	0
	0144	0196	0361	1296	0841	7056	0025	0004	0	0

3. Générateur à congruence additive

Le générateur à congruence additive est défini de la manière suivante :

Soient des entiers naturels, pour



Pour on obtient la suite de Fibonacci.

Cette méthode a deux inconvénients :

1. Il nécessite de stocker nombres.

2. Si est petit les nombres présentent une forte corrélation.

4. Générateur Blum-Blum-Shub

Définition

L'ensemble des résidus quadratiques est noté par et l'ensemble des non-résidus quadratiques est noté par

Définition

Un entier de Blum est un produit de deux premiers distincts dont tous deux congrus à 3 modulo 4.

Proposition

Soit un entier de Blum et soit un carrée de alors possède quatre racines carrées dont une (et une seule) est un carrée de . Cette racine est appelée racine principale de

Preuve

Comme le nombre de racines carrées de est quatre, on peut écrire que ces racines carrées sont : dans (qui s'identifie à grâce au théorème des restes chinois), seul le couple formé par les deux racines principales de modulo et modulo est un carré modulo

Définition

Le générateur Blum-Blum-Shub est définit de la manière suivant :

Soit un entier de Blum tel que et

On choisit un nombre d'une manière aléatoire tel que , alors le germe de la suite est calculé par : . Et les autres termes de la suite sont définis par :



Exemple

Soit et . Alors . Les autres termes sont : . La sortie en bit : 1, 0, 0,1, avec .

III.2. Générateurs cryptographiquement sûrs

Du point de vue de la formalisation de la sécurité d'un générateur pseudo-aléatoire, il faut d'une part définir le problème de sécurité, d'autre part il faut définir ce qu'est l'attaque. Un attaquant est considéré comme un algorithme réalisable qui sort un résultat relatif au problème de sécurité posé. La notion d'algorithme réalisable est extrêmement importante car comme on travaille souvent sur des situations finies on peut décrire théoriquement des algorithmes qui cassent la sécurité des systèmes. Mais ces algorithmes ne sont pas réalisables en pratique à cause de la durée des calculs. On cherche donc à assurer la sécurité calculatoire.

Nous allons utiliser le générateur de Blum-Blum-Shub qui est cryptographiquement sûr.

Définition

Soit un paramètre, appelé paramètre de sécurité.

Définition

Soit une fonction en telle que Un générateur pseudo-aléatoire est une fonction calculable en temps polynomial en de dans .

Lorsque nous composons la distribution uniforme sur avec , nous obtenons une distribution sur appelée la distribution induite par .

Définition

Soit un générateur pseudo-aléatoire et . Un -distingueur pour est un algorithme probabiliste polynomial tel que



où signifie que les bits sont choisis selon la distribution induite par et qu'ils sont choisis selon la distribution uniforme.

Définition

Un générateur pseudo-aléatoire est dit cryptographiquement sûr s'il n'existe d' -distingueur pour que pour des fonctions négligeables (par rapport au paramètre

III.3. Extrapoleurs

Définition

Soit un générateur pseudo-aléatoire, un entier, et . On note des bits choisis suivant la distribution induite par sur . Un extrapoleur d'ordre pour d'avantage est un algorithme probabiliste polynomial calculant le bit en fonction des précédents avec probabilité .

Ainsi à partir d'un extrapoleur d'ordre et d'avantage pour , nous obtenons un -distingueur pour comme suit :











La probabilité que soit égal à vaut au moins lorsque est choisi selon la distribution induite par et vaut lorsque est choisi selon la distribution uniforme.

Théorème de Yao

Un générateur pseudo-aléatoire est sûr si et seulement si, pour chaque entier, il n'existe pas d'extrapoleur pour autres que d'avantage négligeable.

Preuve

D'après la construction de distingueur à partir d'un extrapoleur, ne peut être sûr que si tout extrapoleur n'est que d'avantage négligeable.

Inversement, supposons que ne soit pas sûr. Pour , notons la distribution sur selon laquelle les premiers bits sont produits par et les autres sont choisis uniformément au hasard. Ainsi, est la distribution uniforme et celle induite par . Par hypothèse, il existe un -distingueur pour telle que ne soit pas négligeable, c'est-à -dire



Donc il existe un et une fonction pas négligeable tels que



Considérons l'algorithme suivant :













Nous allons montrer que est un extrapoleur d'avantage pour

On a tout d'abord et

.

On a aussi donc



Pour alléger les notations, nous posons et . La probabilité que prévoie le bit correctement est donnée par

















III.4 Sécurité du générateur Blum-Blum-Shub 

III.4.1 Problème de la résiduosité quadratique

Le problème de la résiduosité quadratique est comme suit : étant donné un nombre il faut déterminer si est un carré modulo ou non.

Lorsque un premier, le problème sera résolu en temps polynomial en la taille de par le calcule du symbole de Legendre Puisqu'on sait que est un résidu quadratique modulo si et seulement si son symbole de Legendre est 1.

Lorsque est un nombre composé dont on ne connait pas la factorisation, aucun algorithme polynomial en la taille de sera disponible pour résoudre le problème de la résiduosité quadratique.

Supposons que où et deux premiers distincts. Si la factorisation de est connue alors le problème de la résiduosité quadratique se résout en temps polynomial en cherchant tout simplement si et sont des résidus quadratiques par le calcul de leurs symboles de Legendre. Mais lorsqu'on ne connait pas la factorisation de ,il sera impossible de résoudre le problème en temps polynomial.

Un autre problème s'oppose à savoir l'extraction d'une racine carrée modulaire : sachant qu'un nombre est un résidu quadratique , comment déterminer un nombre tel que

Nota

Soit un entier de Blum, un élément de symbole de Jacobi 1 et son carré modulo On sait que , et possède 4 racines carrées dont deux ont pour symbole de Jacobi 1 : et . Une et une des deux valeurs et est dans En outre et ont des parités différentes. Autrement dit, si on disposait d'un algorithme capable de déterminer avec une probabilité de succès non négligeable, à partir de quelle est la parité de la racine carrée qui est elle-même un carré, on pourrait déterminer avec la même probabilité de succès si est un carré ou non.

III.4.2 Détails sur la sécurité du générateur Blum-Blum-Shub

On va noter l'ensemble des entiers de symbole de Jacobi valant 1.

Les nombres d'éléments de est donné par :



Et aussi alors

Comme est un entier de Blum, par conséquent l'application de dans lui-même définie par est une bijection.

Soit la taille de l'entier qui servira de paramètre de sécurité. On dispose d'un algorithme probabiliste polynomial en qui étant donné en entrée le paramètre de sécurité construit au hasard un environnement de travail, c'est-à-dire un entier de Blum de taille (pour notre cas). Soit la fonction d'élévation au carrée modulo On note l'ensemble des environnements possibles.

Soit un algorithme probabiliste polynomial en dont l'entrée est le paramètre de sécurité le nombre et un élément de et la sortie un bit dont on souhaite qu'il détermine avec succès si est un élément de ou non.

Considérons les expériences :



























L'avantage de l'attaquant est définie par :



Le problème de la résiduosité quadratique est sûr par l'hypothèse de la difficulté de la résiduosité quadratique, c'est-à-dire que pour tout attaquant polynomial et pour tout entier Autrement dit tout attaquant polynomial a un avantage qui est une fonction négligeable du paramètre de sécurité .

Les algorithmes d'extrapolation

Soit le paramètre de sécurité, un entier de Blum de taille et le générateur des nombres pseudo-aléatoire définie par :

, où pour tout le calcul de se fait de la façon suivante :

1. La bijection de dans lui-même définie par permet de calculer

2. Chaque donne un bit

3.

Lemme

Soit et un algorithme probabiliste polynomial qui étant donnés les bits prédit le bit avec un avantage non négligeable. Alors on fournit en entrée de cet algorithme probabiliste polynomial, les bits d'un , il prédit le bit avec le même avantage non négligeable.

Preuve

Du fait est une bijection, la loi de probabilité du terme calculé est la même que la loi de probabilité du terme tiré au sort dans qui sert de germe

Pour prouver que le générateur BBS est sûr, on montrera que s'il existe un extrapoleur probabiliste polynomial qui prédit le bit avec un avantage non négligeable, alors, il existe un algorithme probabiliste polynomial qui possède un avantage non négligeable pour résoudre le problème de la résiduosité quadratique.

Soit un algorithme polynomial probabiliste, dont les entrées sont et dont l'avantage de prédiction du bit n'est pas une fonction négligeable de . Construisons l'algorithme dont les entrées sont ( où et sort un bit.



















Par le nota précédent, on voit que l'algorithme ainsi construit, a un avantage non négligeable pour le problème de la résiduosité quadratique. En tenant compte de la difficulté de la résiduosité quadratique, on conclut que le générateur Blum-Blum-Shub est sûr.

CHAPITRE IV : IMPLEMENTATION ET INTERPRETATION DES RESULTATS

Dans ce chapitre nous présentons l'implémentation de l'algorithme de Blum-Blum-Shub et l'interprétation des résultats obtenus.

Voici l'algorithme de Blum-Blum-Shub :

Générer et

Faire

Choisir

Calculer le germe :

La séquence est

Sortie est :

Nous avons implémenté l'algorithme de Blum-Blum-Shub en c++ à partir du compilateur DEV-C++.

Voici les codes du programme :

#include <iostream>

#include<conio.h>

using namespace std;

int main()

{

int i,B;

unsigned long long int X,n,p,q,s;

cout<<endl<<"Entrer la valeur de p:";// p un entier congru à 3 modulo 4

cin>>p;

cout<<endl<<"Entrer la valeur de q:";//q un entier congru à 3 modulo 4

cin>>q;

n=p*q;//ceci calcule l'entier de blum

cout<<endl<<" L'entier de Blum est:"<<n;

cout<<endl<<"Entrer la valeur pour calculer le germe:";//Le germe,un entier premier avec n

cin>>s;

X=(s*s);

X=X%n;//calcule du germe

for(int i=1;i<=10000;i++)

{

X=(X*X)%n;//

B=X%2;//calcule les bits de la séquence

cout<<B;

}

getch ();

}

Nous savons que l'entier de Blum est défini par , où et sont tous deux congrus à 3 modulo 4. En d'autres termes et . Nous prenons et petits, avec et .

Alors et , alors ,prenons , puisque ,la séquence comportera 10.000 bits.

La séquence était produite en 1,20 secondes dans un ordinateur dont les caractéristiques sont :

Ø Dual Core , Processeur AMD Sempron (tm) 2.10 GHz

Ø 3.00 Go de RAM

Voici la sequence :

011100001010110011000110100111000001011000001000000101010101110101101111110111110100011110100100100011000100100010010010000001111100010111010101111110100001010101101011101100001111111001101100100000110111000000101010011101010101111100100010111110111111101010111111001110100101111010000001101110001101100010111101000100110000010000101001110110110101000011010011100000001111110110100110110101010100100110100111011010100101001001111011001111010001000101000111110100011000110110000110010110001000000101101010111001110101010001100100110111100110110111011101101000100110011000011100101001000101011010010011011101000001100001111111010000001010101001000110100010111101000100111001010101011010001100011101011111010000011000110101111011001010001110111100101101101111101110110100101000011001111010000011110100001000111100000010011111111100010111011111100010001001001110010111010101001111000101010011001010000111010000000011011010110101011000111100011111100100110110000010101100101111000111000111111110100001110100000101110100011110001001011100100001111001101100101100001101011100010111011000001011100000101010111000100111001010100110101111011111001111001101000000000101111111101000000001001110011010010011011110110110011111100001001010000111000111000110100111001010100011111100011010100111110001110010011000101001110101111111100011110001111001010001011011000001110001111110000010011011001000011101000001110001101101010010010000011101111111101100101100110000000011100011110100101101010010010000100010110010010101010101011000110100100111111111010001010101000011001010111100111111000011000001110011010011111011000111100000101101011010011000010000000111011100011100110011011011010001100101001011010001011101110111101100100010100000001100111011111000100011000100110000110001110010000000011000101100000100110100101010101011010011001011010111111100011001011011011110000110101111101011111000000000101000000100011100100000111110010100111010110101101011011000010001001111011100100010001010010000000010010010000001001111011010101101011111000001111110000010100011101011011110011011000111011011111100011011001000101001001010110011010011110101111101011111010110111101011011110011100011001100101010011010010111100101100111010001000100000011100100110010001111000010010010100110001001100000110010100011010001101000010111000100100001000010001000001010111010110001100010001101100000001010011100101000011011000001011001001011011111000100101010010011111101101110010110100010110101111101100111010010101111110110111011111100110100010011111010010011010010000011110000001110000011100000010011010000101000101110001001001101100000000001001110110100110001000101100011000110010000100100010001001000101100110001010010100111011100010001110100111100011101100001011110100001110100001100000110010011110001100000010000000111000001001000111010001011101010110000010011010000100010101001001100111011100010011011010000100001001110111111000100011100111010011000000110000101001111111101111100001010111000100000101111000111101010011000110111010010100110101010110110001010011001101000001101001100111101101110001101011111101011100100000101101101010010111001110011001111110011110000110111000100111010100001111111101110011000110110000101110111101000001110100100010101101110101011101100101001111100110100100011100110111001010011010110010100111100010010011010111000111101010110011100010101111101011111111111101101010100011010000000110101101101001100000010111001101100010100100001001110001000101000001100110010010011011000000011011000100001100110111110111111111000100101100000011001111110110110110110011010111001000010100100110000111100101011100111011001100110000110000111000101100111000100010111011101001110110101011001111010101111001000101000110111000011000111110111100011000010010101101100001111100100111001100110101000001011010000000010110101000111011110111011001101001011010110111111000000001110000011110001110011010101100101001000001111100011111101010000010101101001010100100101110011001000111101111100011100010011100001011001101001101100100111110111001011111001001011011111010111000100011000110000100000000100000110001110011010111001111101101000001101111000100101111000111010001110000001111101110100011100101101010010010000000110010101110011001011101010011000010101000100001111101001110111010010010000011011100000001110000001110110010101000101010101001001001011001111001111001011110000001100010010110001100111101110011000111001000010011000111111010100110101101101001101111000001100100010110110110001010010010101101100101100000000101001000001111110001110001101100000100101110000101001001010111110000110110101000111111011110010000101011111010110100110101011011110100101110110001100100100000000010011001100000110011111011010000001111011101001100111001010000100001000000000011101101001011110011100000010000011001001010111111010011100000010010111101110001111110011010011010000001000111100000100010001101111011100110011000010011001010011001000011001010101110110010001100001011000010011100101101111111110011010000101010000111001100000111110101011011011001000101011011001010100110101110110100001111111

001111101111001001111111001110110011110101001010010100111010010100111110011001100000001000010010101000111000111111100000110100111001010110101101110111110110111110111001010101011101011010101101010011000000010011000101100110011010111110110011011000111111011000110000111111100110100111010110011100111100001001111010000100101000111010111000101100110000100000111010001000010100000000000111000110101011100011110000111100111010001001100001110100001011111010010100011011111000110011010110001110101000011100000101011110011001100010000011110010101011001111011100110011001001100000110000101110101001110110010111101011100011011001001010010111010111100110000011101100010010010010111111011011101111111110101111110100000010110110100111111001111001001111000110111111100101011111111111010001000100011100101011100000001101111101100001001001010001101110010101001110100111001110110101001111110011101111101110111010110001000101001010101100001111101101100000001110010000000000000001011100001010011101110110001100101101111011101110111101101001110100010010111110101101110011001011000000001011011101100100101011010111111111100001101000100010110110000000011010000110010011000111010011010000111110001000100110111010110000111011001101010111001010001110001111000100100001110110011101111101010000000010000001110000100010001111001000101110111111010110011010101100000101101111111010010100000011010100100101000001010110100111100000100010010000111001011001111010110111010110101011011010111011000101011011000000101111110011001101111010100110010101001000101101101001101000000000110101011111001101110101101000101111010100010000001110100100111110111010110110101010111101000111101010101100100110011010000011111000011011100100111001111111001101000110111010100110011110100100001010111100111100001101010010000001010011010010110011000010100000001111000101100111010000000000001000011111000100001111001111001010011110001001000010101000000001011101010110111100110001100010011110111001111100000111100100100010100010001111100100001100011100111011011101011001010010101101001001011100111000110011000011010011101101110111000011000000010000110001100110100111010001011111100000011001000110111110001110010010101111011111010111110101010111111100111001100100000010010011000011111000000010011100000101111010111111110000001010010110011110111110110101101001000111011011000110010011110110101110011010011100111000000011110000001010001101001001010000001111110000010111100110000011100111011001111101010011111110011110101110010010001001111110011000100001010010101101111110010010111100011011100001001110011000110001001010111011100100110110110001110001001000000100101111110101111000011000001111100100001110111001111010111110010101100101011110101111010000011011000001000111101011000101100100001011000001100011110010101010111000101001000111010000100011000010001101110001010111001111101011010101010000000000101100100010110011000100100000000101011001111001100100000010101000001010010101100000111111000001001010000000000010111100100001010110101100101100101101100001011101001011101110001110110000000010101101101101110000010101011100001000100001100110010101011100101111011111001101110111001011101111000001101011110110001101100010110001111110111010101110011101011111101101101111000001000111011000011011010011110101110100100001101100110001110000011101000011010010111001001101100110110011011010101100000110001111010110001110111011110011100110000111000110000011010011110100101100101111010001101111100111111111100110111111110001010001111101110010101100110101001111101001111010110011110001001010100101101110100111010001100001110111001011010010100111101110001011010000110101010000001010010011001010111010111111110110010101011000101000000101101010100001010010111101000110111000010000001010010110101010000101001101011100010010011100111000011110010001110101100001101001111111100011011000010111011001101010110010101011110010011101101001000101110100001000100010001011101001100101010001110011000011001101010101010110011010111000110001101011011100000111100111001100010111001011101011001100111011000011000001111001100000110000011101001010000010110010110000000101111000101100010111000010111110100000100001010100010111001110001001010011101010100100011011010110110001000100111111111110011000111001100011010011100111111010011011001101011101111010011011010011001100010000001111100110110111111000100001010110011100111011111110101110000101000111011010101011000001100010010110000111011100010110101010100101111110001111101110100011010111011010001110010011011111101010011011011100111101011100000001010100110111010110001011101110101011000100101110111100011010000110000111110110010111111000011111010101111100001110111011110010011100010100101101101011001101001110001101111110110001100001010100100011000111110110010011100110101111011100110011010010011111011110100101101010100011010000100100011011001110011101000011010000100111010101111000000100010011100100110001101100111010111010011001100101011110111010010101101011111101001010110000101100000100101111011000000

La séquence binaire aléatoire produite peut être utilisée pour clés au chiffrement par flot ou au chiffrement de verman enfin de répondre aux conditions du théorème de Claude Shannon sur la sécurité parfaite : une nouvelle clé est tirée à chaque chiffrement, la clé est aussi longue que le texte clair, toutes les clés sont équiprobables.

Si nous avons un message de bits à chiffrer, on considère les premiers bits de la séquence aléatoire générée qui constituent un mot et on fait l'opération « ou exclusif bit à bit » entre le message et la partie de la séquence aléatoire considérée comme clé. C'est-à-dire

Il est à noter que l'expéditeur et le destinateur ont le même générateur. A la réception, le destinateur extrait de la même façon les premiers bits de la séquence aléatoire et calcule ensuite . Les deux interlocuteurs jettent la partie utilisée et peuvent effectuer une nouvelle transaction en procédant de même avec le reste de la clé.

Voici le schéma illustrant l'utilisation de la séquence binaire générée avec un message quelconque binaire

Fig.4. Schéma illustrant l'utilisation de la séquence binaire produite

Clé



Partie utilisée K

Nouvelle clé

Message clair

Message chiffré

1

0

0

0

1

0

0

1

0

0

1

0

1

0

1

1

0

0

.

.

.

.

1

1

1

0

0

0

0

1

0

.

1

1

1

1

0

0

0

1

0

1

1

CONCLUSION

Il existe plusieurs générateurs pseudo-aléatoires mais tous ne sont pas utiliser pour l'usage cryptographique, la plupart sont utilisés en simulation. Nous avons étudié dans le présent travail la façon dont un générateur produit une séquence complètement déterministe à partir d'une valeur initiale appelé germe.

Nous avons montré que le générateur Blum-Blum-Shub est cryptographiquement sûr suite au problème de la résiduosité quadratique et à la difficulté de décomposer un grand nombre en deux facteurs premiers. Même si le générateur Blum-Blum-Shub est cryptographiquement sûr, il faudra respecter les paramètres de base pour générer une bonne séquence sinon la séquence à produite serait un échec du point de vue cryptographique.

Enfin, la génération des séquences aléatoires cryptographiquement sûres est un défi chez les cryptographes, mathématiciens, informaticiens et ingénieurs.

BIBLIOGRAPHIE

I. Ouvrages

[1] Hans Delfs, Helmut Knebl, Introduction to Cryptography-Principles and Applications, 2nd ed, (Springer, 2007) WW

[2] Johannes Buchmann, Introduction à la cryptographie, Dunod, Paris, 2006

[3] J.S. Milne, Algebraic Number Theory, version 3.02, April 30,2009

II. Articles

[4] Lenore Blum, Manual Blum, and Michael Shub. A Simple Unpredict

able PseudoRandom Number Generator. SIAM Journal on Computing,

15(2):364.383, May 1986.

[5] C.E. Shannon. Communication theory of secrecy systems. Bell Systems Technical journal, 28 : 656-715, 1949.

[6] Pascal Junod. Cryptographic Secure Pseudo-Random Bits Generation : The Blum-Blum-Shub Generator. August 1999

[7] Andrey Sidorenko and Berry Schoenmakers. Concrete Security of the Blum-Blum-Shub

[8] Pseudorandom Generator, Lecture Notes in Computer Science 3796 (2005) 355-375. Springer-Verlag.

[9] Robert Rolland, Sécurité des générateurs pseudo-aléatoires

[10] Kaustubh Gawande and Maithily Mundle, Various implementations of Blum Blum Shub pseudo-random sequence generator

[11] Robert Rolland, Sécurité des générateur de Blum Blum Shub, partie I, 22 mars 2008

III. Cours

[12] MANYA NDJADI L., Probabilité, Note de cours, deuxième graduat Mathématiques, Université de Kinshasa, 2006-2007.

[13] Olivier MARKOVITCH , sécurité informatique , note de cours en format imprimable,UNIVERSITÉ LIBRE DE BRUXELLES

[14] Francois ARNAULT, Théorie des nombres et cryptographie, Note de cours de D.E.A en format imprimable, Univérsité de Limoges, France, 2002

[15] Renaud Dumont, Cryptographie et Sécurité informatique, note de cours en format imprimable, Université de Liège, Faculté des Sciences Appliquées, 2009 - 2010

[16] W. Edwin Clark, Elementary Number Theory, Note de cours en format imprimable, University of South Florida, Departement of Mathmatics, revised December 17, 2002,

IV.Thèses

[17] Renaud SANTORO, Vers des générateurs de nombres aléatoires uniformes et gaussiens à très haut débit, Thèse en Traitement du signal et télécommunications, école doctorale Matisse , Université de rennes 1,soutenue jeudi 17 décembre 2009.

[18] Duong Hi?u PHAN, Sécurité et efficacité des schémas cryptographiques, École normale supérieure, Département d'informatique, présentée et soutenue publiquement le 16 septembre 2005

[19] Andrea Röck, Quantifying Studies of (Pseudo) Random

Number Generation for Cryptography, Thèse de Doctorat présentée à L'ÉCOLE POLYTECHNIQUE pour obtenir le titre de DOCTEUR EN SCIENCES Spécialité Informatique soutenue le 18 mai 2009

V. Sites internet

[20] http://www.acrypta.fr

[21] http://en.wikipedia.org/wiki/Random_number_generation#cite_ref-0

[22] http://en.wikipedia.org/wiki/Hardware_random_number_generator

[23] http://www.random.org/randomness/

[24] http://en.wikipedia.org/wiki/Pseudorandom_number_generator#cite_note-0

[25] http://fr.wikipedia.org/wiki/Blum_Blum_Shub

[26] http://en.wikipedia.org/wiki/Lagged_Fibonacci_generator

[27] http://fr.wikipedia.org/wiki/Linear_congruential_generator

TABLE DES MATIERES

EPIGRAPHE Erreur ! Signet non défini.

DEDICACE ii

REMERCIEMENTS iii

INTRODUCTION 1


CHAPITRE I : ELEMENTS DE LA THEORIE DES NOMBRES 3

I.1.Quelques notions de base 3

I.2. La congruence 5

I.3. Classes des résidus 5

I.4. Ensemble réduit des résidus 6

I.5. La fonction d'Euler ou fonction totient 6

I.6. Résidus quadratiques 9

I.6.1.Le symbole de Legendre 12

I.6.2.Le symbole de Jacobi 13

II.1 Définitions 15

II.1.1. Définition d'un système cryptographique 15

II.2 Cryptosystème symétrique et asymétrique 16

II.2.1 Cryptosystème symétrique 16

II.2.2 Cryptosystème asymétrique 22

II.3. Sécurité d'un système cryptographique 25

II.3.1. Notions élémentaires de probabilité 25

II.3.2. La sécurité calculatoire 27

II.3.3 La sécurité parfaite de Shannon 27

II.3.4. Système cryptographique parfaitement sûr 28

CHAPITRE III : GENERATEURS PSEUDO-ALEATOIRES 31

III.1. Exemples de quelques générateurs pseudo-aléatoires 32

III.2. Générateurs cryptographiquement sûrs 34

III.3. Extrapoleurs 35

III.4 Sécurité du générateur Blum-Blum-Shub 38

III.4.1 Problème de la résiduosité quadratique 38

III.4.2 Détails sur la sécurité du générateur Blum-Blum-Shub 39

CHAPITRE IV : IMPLEMENTATION ET INTERPRETATION DES RESULTATS 43


CONCLUSION 50


BIBLIOGRAPHIE 51

TABLE DES MATIERES 54