english version
Vitrine de la RDCLes 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.
CHAPITRE I : ELEMENTS DE LA THEORIE DES NOMBRES
I.1.Quelques notions de base Définition Un entier n > 0 est dit premier s’il est différent de 1 et s’il n’admet aucun diviseur positif différent de 1 et n. 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 p_1 p_2 〖…p〗_k. 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 n = p_1 p_2 〖…p〗_k+1 : si p_i (1≤i≤k) divisait n, alors p_i diviserait 1, ce qui est absurde.
Lemme de Gauss. Si des entiers a,b et c sont tels que a divise bc et a premier avec b, alors a divise c. Preuve Comme a est premier avec b, on peut écrire au + bv = 1 pour des entiers u et v. Ainsi auc + bvc = c et comme a divise auc (car il divise a) et bvc (car il divise bc), il divise la somme qui vaut c.
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 n ≥ 1 se décompose d’une et d’une seule manière en un produit de nombres premiers. Autrement dit, pour tout entier n ≥ 1, il existe des nombres premiers deux à deux distincts p_1,...,p_k et des entiers strictement positifs α_1,...,∝_k, uniquement déterminés à l’ordre près, tels que : n=p_1^(∝_1 ) p_2^(∝_2 ) 〖…p〗_k^(∝_k )
Preuve Le théorème reste bien vrai pour n = 1 : il faut choisir k = 0, 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 n. Pour n = 2 alors ça s’écrit comme un produit de nombres premiers, étant lui-même premier. Soit n ≥ 3 un entier. Supposons que tous les entiers strictement inferieurs à n s’écrivent comme le précise le théorème et montrons que la conclusion subsiste pour l’entier n. Il y a deux cas : soit n est premier, soit il ne l’est pas. Le premier cas est vite réglé : n premier s’écrit bien comme un produit de nombres premiers. Supposons donc que n soit composé. Ainsi, il s’écrit n = dd’ avec 2≤ d < n et2≤ d' < n. Les entiers d et d’ relèvent de l’hypothèse de récurrence et on peut écrire : d=p_1 p_2 〖…p〗_k d'=〖p'〗_1 〖p'〗_2 〖…p'〗_k' pour des nombres premiers p_i et 〖p'〗_i. Il ne reste plus qu’à effectuer le produit pour conclure. Montrons l’unicité : Supposons que p_1 p_2 〖…p〗_k=〖p'〗_1 〖p'〗_2 〖…p'〗_k' Pour certains nombres premiers p_i et 〖p'〗_i. On veut montrer que k=k' et que les p_i sont égaux aux 〖p'〗_i à l’ordre près. Raisonnons ensuite par l’absurde. Le nombre premier p_1 divise le produit 〖p'〗_1 〖p'〗_2 〖…p'〗_k' donc par le lemme précédent, il divise 〖p'〗_i.∀ i. Or, les diviseurs de 〖p'〗_i (qui est premier) ne sont que 1 et 〖p'〗_i. Comme p_1≠1, il ne reste plus que la possibilité p_1=〖p'〗_1=p. On peut alors simplifier l’égalité : p_1 p_2 〖…p〗_k=〖p^'〗_1 〖p^'〗_2 〖…p^'〗_(k^' ) en divisant par p,on obtiens une contradiction et l’unicité est prouvé.
I.2. La congruence Définition Soient a b ,et n des entiers, alors on dit que a est congru à b modulo n, ce qui s’écrit a ≡b (mod n), si n/(a - b) ; n est le module de la congruence.
Propriétés de la congruence ∀ a,a_1,b,b_1,c ∈Z∶ a≡b(mod n)↔a et b ont le même reste dans la division par n. a≡a(mod n) (réflexivité). a≡b(mod n)→ b≡a (mod n) (symétrie). a≡b(mod n) et b≡c (mod n) → a≡c(mod n) (transitivité). a≡a_1 (mod n) et b≡b_1 (mod n)→{█(a+b≡a_1+b_1 (mod n),@ab≡a_1 b_1 (mod n).)┤
I.3. Classes des résidus
Théorème. Pour m>0 on a : [a]={mq+a/q∈Z}. Preuve Supposons x ∈ [a] ↔x≡a (mod m)↔m⁄(x-a ↔x-a=mq) pour tout ∈ Z ↔x=mq+a . Notons que [a] dépends de m. On a deux façons d’écrire l’équation ci-haut : [a]= {mq+a/q=0,±1,±2,…} ou [a]={…,-2m+a,a,m+a;2m+a,…} Tout élément x∈[a] est une représentation de la classe de résidu [a].
I.4. Ensemble réduit des résidus
Définition On défini Z_m={ ├ [a] ┤| a∈Z} , alors Z_m est l’ensemble de toutes les classes modulo m. Nous appelons Z_m l’anneau des entiers modulo m. Z_m={ [0],[1],[2],…,[m-1] } Addition et multiplication dans Z_m Pour [a] ,[b]∈Z_m , on a : [a]+[b]=[a+b] et [a][b]=[ab] Exemple Pour m=5 [2]+[3]=[5] et [2][3]=[6] Notons que puisque 5≡0 (mod 5) et 6≡1 (mod 5) ,nous avons [5]=[0] et [6]=[1]. Nous pouvons aussi écrire [2]+[3]=[0] et [2][3]=[1]
I.5. La fonction d’Euler ou fonction totient
Définition Pour m≥0 ,soit φ(n) le nombre d’entiers premiers avec m dans l’intervalle [1,m]. La fonction φ est la fonction d’Euler. Exemple Pour m=6, il y a 6 différentes classes de résidu modulo 6 ; les classes [0],[2],[3] et [4] ne sont pas premiers avec 6 ; ainsi seules les classes [1] et [5] sont premiers avec 6 :alors φ(6)=2 . Si p est un premier, toutes les p-1 classes [1],[2],[3],…,[p-1] sont premiers avec , alors φ(p)=p-1. Exemple : p 2 4 5 6 7 8 9 10 12 15 φ(p) 2 2 4 2 6 4 6 4 4 8
Théorème (Euler)
Soit (m,a)=1 , alors a^( φ(m) )=1 mod m
Ceci permet de calculer l’inverse modulaire définit par :
a^( φ(m)-1)=1 mod m
Exemple
Quel est l’inverse de 3 mod 7: on sait que φ(7)=7-1=6,φ(7)-1=5
On a (3,7)=1, d’où 3^5 mod 7=〖(3〗^2 〖.3〗^2.3)mod 7=5
Théorème (Petit théorème de Fermat)
Soit m un premier et a un entier tel que (m,a)=1 alors a^(m-1)=1 mod m
Preuve
Considérons les m-1 entiers suivants :a,2a,3a,…,ka,…,(m-1)a ainsi que leurs restes dans la division euclidienne par m, notés :〖 r〗_1,r_2,r_3,…,r_(m-1). Ces restes sont compris entre 1 et m-1.
En effet, d’après le même de Gauss, si m divisait un des ces produits ka,m diviserait k puisque a et m sont premiers entre eux, mais ceci est impossible puisque 1
Théorème du reste Chinois Soit a_1,a_2,〖…,a〗_k des entiers et m_1,m_2,…,m_k des entiers relativement premiers entre eux, alors le système des congruences x≡a_1 mod m_1, x≡a_2 mod m_(2,) . . . x≡a_k mod m_k admet une unique solution modulo m_1 m_2…m_k
Preuve Soit m=m_1 m_2…m_k,et considérons m/m_1 .Ceci est relativement premier à m_1, ainsi il existe un entier t_( 1 ) tel que t_1.m/m_1 ≡1 mod m_1. En conséquence, soit s_1=t_1.m/m_1 . Alors s_1≡1 mod m_1 et s_1≡0 mod m_j, j≠1. D’une manière similaire, ∀i, il existe un s_i tel que s_i≡1 mod m_i et s_i≡0 mod m_j,j≠i. Alors x=a_1 s_1+a_2 s_2+⋯+a_k s_k est une solution du système ci-haut. Soit x^' une autre solution, alors x-x^'≡0 mod m_i pour tout i⇒x-x^'≡0 mod m_1 m_2…m_k
I.6. Résidus quadratiques
Soit n>1 un entier positif , et a∈ Z_n^* tel que (a,n)=1. On dit que a est un résidu quadratique mod n si ∃ b∈Z_n^* tel que b^2≡a mod n. Si un tel b n’existe pas, a est un non-résidu quadratique mod n. Avec Z_n^*={a∈Z_n | pgcd(a,n)=1} Si a et b sont des résidus quadratique mod n ,alors leur produit est ab Si a est un résidu quadratique mod n, et b un non-résidu quadratique mod n , alors ab est un non-résidu quadratique mod n Le produit de deux résidus quadratiques mod n n’est pas nécessairement un résidu quadratique mod n.
Théorème 1 Soit p un nombre premier impair. Exactement la moitie des éléments de Z_p^* sont des résidus quadratiques. Preuve Chaque résidu quadratique modulo p est congru à un des (p-1)/2 résidus suivants : 1^2,2^2,…,k^2,…,(〖(p-1)/2)〗^2 On montre que ces classes des résidus sont tous distincts. Pour 1≤h≤k≤(p-1)/2 , h^2≡k^2 mod p si et seulement si (k-h)(h+k) est divisible par p, ceci est impossible puisque chacun de k-h et h+k est petit que p . Corollaire 1 Soit p un nombre premier impair, le produit de deux non résidus est un résidu quadratique. Théorème 2 Soit p un nombre premier impair. -1 est un résidu quadratique mod p si et seulement si p≡1 mod 4.
Preuve Si x^2=-1 mod p , alors par le petit théoreme de Fermat : 〖(-1)〗^((p-1)/2)≡x^(p-1)≡1 mod p . Ceci signifie que (p-1)/2 est pair, et ≡1 mod 4 . Inversement si p≡1 mod 4, l’entier (p-1)/2 est pair. Par le théorème de Wilson, 〖(((p-1)/2)!)〗^2=∏_(i=1)^((p-1)/2)▒〖j^2=〗 ∏_(i=1)^((p-1)/2)▒〖j(-j)≡∏_(i=1)^((p-1)/2)▒〖j(p-j)=(p-1)!≡-1 mod p.〗〗 Les solutions de x^2=-1 mod p sont donc x≡± ((p-1)/2)!.
