LES FRACTIONS CONTINUES ET SES APPLICATION

LES FRACTIONS CONTINUES ET SES
APPLICATION

Introduction Générale 

Les fractions continues, partie intégrante de la théorie des nombres, elles ont été étudiées par les plus grands mathématiciens de toute l’histoire. On peut citer notamment Lagrange, Galois, Fermat, Euler, Pythagore, Liouville et bien d’autres encore. L’attention accordée par ces grands penseurs à cette branche des mathématiques montre son importance. Elles sont notamment utilisées pour l’approximation d’un irrationnel par un rationnel, en théorie des approximations diophantiennes, en théorie des gammes musicales… Par contre son utilisation en cryptographie date des années 90 avec l’introduction par Wiener d’une attaque sur le cryptosystème RSA. On note aussi son utilisation récente dans l’élaboration de générateur pseudo-aléatoire cryptographiquement sûre proposé par Amadou Moctar Kane [1] dans son article de 2013 intitulé On the use of continued fractions for stream ciphers. Ce mémoire est consacré dans son intégralité aux applications des fractions continues à la cryptographie. Après donc un premier chapitre introductif, on parlera dans les chapitres deux et trois des applications de cette branche des mathématiques pour la cryptographies à savoir : * Son utilisation pour l’approximation des irrationnels par un rationnel : Théorème de meilleur approximation prouve que les rationnels qui fournissent une meilleur approximation d’un irrationnel donné sons ses réduites. Ce Théorème et ses applications possibles vont être étudiés à la première section du chapitre 2 de ce mémoire. * Son utilisation pour l’attaque du cryptosystème RSA (Attaque de Wiener) : En 1990 Wiener publie Cryptanalysis of Short RSA Secret Exponents qui est une attaque qui permet de retrouver la clé privée d d’un cryptosystème RSA en connaissant uniquement la clé publique (e, N) lorsque celles-ci sont malles choisies. Sa technique s’appuie sur le développement en fraction continue de e N . Parmi les réduites obtenues, l’une a pour dénominateur l’exposant privé d. La deuxième section du chapitre 2 sera l’occasion d’étudier et de donner des cas particuliers ou cette attaque est possible. 7 * Son utilisation pour la création de générateur pseudo-aléatoire On note deux approches fondamentales dans l’étude de la sécurité d’un système cryptographique : à savoir, la notion de confidentialité parfaite de Shannon et le concept de sécurité calculatoire. Théorème 0.1. Théorème de Shannon Soit un procédé de chiffrement tel que |P| = |C| = |K| = n, n > 0. Ce système assure une confidentialité parfaite si, et seulement si, chaque clef est utilisée avec une probabilité 1 n , et pour chaque message clair x ∈ P et chaque message chiffré y ∈ C , il existe une unique clef k ∈ K telle que Ek(x) = y (et donc Dk(y) = x). Une réalisation célèbre de la confidentialité parfaite est le chiffrement de Vernam, également connu sous les noms masque jetable ou one-time pad. Il consiste à combiner le message en clair avec une clé présentant les caractéristiques très particulières suivantes : • La clé doit être une suite de caractères au moins aussi longue que le message à chiffrer. • Les caractères composant la clé doivent être choisis de façon totalement aléatoire. • Chaque clé, ou « masque », ne doit être utilisée qu’une seule fois (d’où le nom de masque jetable). Ce cryptosystème vérifie les conditions du Théorème de Shannon,il assure donc une confidentialité parfaite. Malheureusement les caractéristiques particulières de sa clé de chiffrement rendent très difficile sa mise en œuvre. Par exemple, pour générer une clé on fait souvent appelle à des algorithmes déterministe, dés lors on ne peut plus parler de clé choisis de façon totalement aléatoire. On obtient donc un simulé d’aléatoire ou pseudo-aléatoire, le cryptosystème ainsi obtenu sera appelé chiffrement par flux au lieu de chiffrement par masque jetable. Le chiffrements par flux utilisent donc des générateurs pseudo-aléatoire qu’on peut regrouper en deux groupes en fonction de leur méthode de conception à savoir : • Ceux qui ne sont pas construits au tour d’un problème mathématiques : Bien que cryptographiquement faibles, ces dispositifs sont simples et peu coûteux.Dans cette classe, nous comptons les Linear Feedback Shift Registers (LFSR) réalisé électroniquement,… • Ceux construits autour d’un problème mathématique difficile : Ils sont dans la plus part des cas lourd et lent mais ont l’avantage d’être 8 mathématiquement démontrés comme cryptographiquement sûr. Dans cette classe, nous comptons les générateurs basés sur l’algorithme RSA ou sur la difficulté de calcul des logarithmes discrets… Le troisième chapitre de ce mémoire sera l’occasion de proposer un générateurs pseudo-aléatoire basé sur la difficulté de récupérer un nombre irrationnel de la seule connaissance d’une partie de son développement en fraction continue. Nous montrerons que se problème est un problème mathématique que l’on prouvera difficile.

 Fraction Continue et Cryptanalyse de RSA : Attaque de Wiener 

 Rappel sur le Cryptosystème RSA 

L’algorithme de cryptage (RSA) de Rivest, Shamir et Adleman est un système de chiffrement à clé publique (asymétrique) :kc 6= kd. Le problème RSA est basé sur le problème de la factorisation entière qui est ”difficile” pour N = pq impaire. Définition 2.1. (Le problème de la factorisation entière) Étant donnée un entier N, calculer des facteurs premiers non triviaux de N (différents de 1 et N). Définition 2.2. (Le module RSA) le système RSA est construit à partir de deux grands nombres premiers distincts p et 35 q dont on note N le produit (N = pq). Ce nombre N qui est appelé le module RSA est public (mais p et q sont secrets). On note φ(N) = (p − 1)(q − 1) l’indicateur d’Euler. L’exposant de chiffrement 1 < e < φ(N) est un nombre premier avec φ(N) qui est aussi public. L’exposant de déchiffrement d (clé privée) est secret. Il est calculé de manière à ce que ed ≡ 1 mod (φ(N)), 1 < d < φ(N). Alice et Bop veulent communique ensemble sur un canal non sûr pour cela ils ont décide d’utiliser le cryptogramme RSA. Construction du module RSA d’Alice : – Alice choisit p et q deux nombres premiers et calcule N = pq – Calcule φ(N) = (p − 1)(q − 1), – choisit e tel que 1 < e < φ(N) un nombre premier avec φ(N), – calcule d tel que ed ≡ 1 mod φ(N) , 1 < d < φ(N) – (p, q, d) sont sa clé privé et (N, e) sa clé public qu’elle publie par la suite dans un annuaire. Algorithme de chiffrement RSA : Pour envoyer un message m ∈ 2, 3, …,(N − 1) à Alice, Bop calcule : – c = me mod N et l’envoie à Alice Algorithme de déchiffrement RSA : A la réception de c, Alice calcule : – m0 = c d mod N Comme c = me mod N on a : m0 = med mod N ed ≡ 1 mod φ(N) ⇒ ∃ k ∈ N tel que ed = 1 + kφ(N) m0 = m1+kφ(N) mod N m0 = m mod N Alice retrouve bien le message envoyé par Bop 2.2.2 Attaque de Wiener En 1990, Wiener publié une attaque contre RSA, en utilisant les fractions continues classiques. Cette attaque peut récupérer la clé privée d à la seule connaissance de la clé publique (e, N). Sa technique est basée sur des approximations en utilisant les fractions continues. Pour (e, N) la clé publique et d la clé privée de RSA, l’attaque Wiener peut récupérer la clé privée d en calculant le développement en fraction continue de e N . Parmi les réduites obtenus à partir du développement en fraction continue de e N , il trouve qu’il y a n’en une qui a comme dénominateur d. Cette attaque de Wiener était possible si d est inférieur à la borne de Wiener c’est à dire d vérifie l’inégalité : d ≤ √4 N √ 3 36 Cette borne a été redéfinie par Kaufer Aaron H. dans son article de 2009 Applications of Continued Fractions in Cryptography and Diophantine Equations [2]. Dans cette article la nouvelle borne de Wiener est : d ≤ √4 N p 2(a + 1) , a ∈ N Cette section sera location de parler de cette attaque sur le cryptosystème RSA et proposer une implémentation. Proposition 2.1. Soit N un module RSA. Si on connait φ(N), alors on peut factoriser N. Preuve 2.1. Supposons que φ(N) est connu. φ(N) = (p − 1)(q − 1) = pq − p − q + 1 = N − (p + q) + 1 .