FR 3002349 A1 20140822 FR 1300375 A 20130220 Description Seront successivement exposés: SECTION I : l'indication du domaine technique auquel se rapporte l'invention et les principes généraux de celle-ci ainsi que ses avantages. SECTION II : Une Annexe , constituée de théories et résultats mathématiques nécessaires à la compréhension de l'invention , placée avant l'exposé technique car il est nécessaire d'en prendre connaissance pour la compréhension de l'exposé technique. SECTION III: l'exposé technique de l'invention qui se décompose en trois sous-exposés. SECTION I INDICATION DU DOMAINE TECHNIQUE DE L'INVENTION La présente invention est constituée de méthodes cryptographiques ayant pour but la confidentialité des communications et l'identification. Le domaine technique de l'invention est donc celui de la cryptographie. Plus spécifiquement l'invention objet de la présente demande de brevet, concerne des systèmes de chiffrement et d'identification basés sur des technique cryptographiques utilisant des clés secrètes privées (systèmes dits symétriques). Encore plus spécifiquement encore l'invention objet de la présente demande de brevet concerne des 10 techniques cryptographiques utilisant des clés sous forme de permutations d'objets. On développe ci-après de manière brève les principes sur lesquels elle repose. Les principes de cryptographie qui vont être exposés dans la SECTION III (« Exposés techniques ») reposent sur des objets qu'on appelle des suites ordinales. I-Une suite ordinale est une permutation d'objets quelconques tous différents deux à deux. 15 Par exemple une permutation des cinq premiers entiers naturels comme ( 4 5 2 1 3) est une suite ordinale. De même ( m 1 + & 8 d) est une suite ordinale composée des six symboles que sont :1,8,d , m,+, &, puisqu'elle est une permutation de ces six symboles. Ou bien encore on peut former des suites ordinales en considérant des ensembles de symboles (et 20 non plus des symboles ) , comme par exemple des n-uplets de bits. Chaque n-uplet est alors considéré comme un seul élément. Par exemple la suite ( 011 111 101 011 100 110 000 010 ) composée de huit triplets de bits est une suite ordinale , tous les triplets de bits étant différents les uns des autres. Elle est une permutation de l'ensemble {0,1} 3 qui est l'ensemble des huit triplets de bits. 25 On peut donc définir mathématiquement une suite ordinale de n éléments comme une fonction bijective de {1,2,....,n} dans un ensemble E de cardinal fini n. La suite (acedb) par exemple peut être définie par la fonction bijective p suivante p(1) = a , p(2) = c , p(3) = e , p(4) = d , p(5) = b. L'ensemble de définition de p étant l'ensemble {1,2,3,4,5} qui est donc considéré comme un ensemble de numéros d'ordre. On peut aussi définir une suite ordinale par une fonction bijective p d'un ensemble E quelconque dans E si E est muni d'un ordre strict. Si par exemple E = { 1,8 , d , m , + , &} et est ordonné de la manière suivante : ( d + 1 m 8 &) , c'est à dire que d est premier élément de E, + est le second, 1 le troisième , etc, alors la suite ( m 1 + & 8 d) est définie par la fonction bijective p suivante : p(d) = m , p(+) = 1 , p(1) = + , p(m) = & , p(8) = 8 , p(&) = d . L'ordre sur E c'est à dire la suite ordonnée ( d + 1 m 8 &) jouant le rôle de numéros d'ordre . C'est pour ce motif qu'on nomme de tels objets suites ordinales et non suites ou suites ordonnées comme usuellement en mathématiques , lesquelles sont définies uniquement en général comme des bijections de {1,2,...,n} dans un ensemble E. Les suites ordinales peuvent donc être définies mathématiquement comme des fonctions bijectives d'un ensemble quelconque E dans E , E étant de cardinal fini et muni d'un ordre strict. Lorsque les permutations sont des permutations de n premiers entiers naturels ( comme par exemple permutation des cinq premiers entiers ) on appelle suites ordinales numériques de telles permutations. On appelle P[n] l'ensemble des permutations des n premiers entiers naturels. Lorsqu'elles sont composées d'objets quelconques on les appelle suites ordinales non numériques. On appelle P[E] les permutations d'un ensemble quelconque E d'objets où les éléments sont tous différents deux à deux. II-Dans le domaine de la cryptographie , les suites ordinales peuvent servir de clés de 20 chiffrement. On les appelle donc ici « clés ordinales ». (Cette terminologie sera utilisée par la suite). Les procédés de cryptographie ordinale , objet de la présente invention , sont des procédés qui utilisent spécifiquement de telles clés de chiffrement. Les suites ordinales , donc clés ordinales , peuvent servir de nombreuses manières comme clé de 25 chiffrement dans des procédés de chiffrement à clé privée. Par exemple , si le procédé de chiffrement consiste basiquement à permuter une suite binaire M composée de cinq bits notés b1, où i est le rang du bit dans M ( ex : 11010) , celle-ci est permutée par exemple par la suite ( 5 2 3 1 4) qui est la clé de chiffrement. La permutation s'opérant par une fonction de substitution « s » définie par : 30 s(bi) = b5 s(b2) = b2 s(b3) = b3 s(b4) = b1 s(b5) = Ou bien si la clé ordinale est une suite ordinale de n-uplets de bits , celle-ci , concaténée , est une clé de chiffrement qui peut chiffrer un message , par addition « + » sur les bits définie par la fonction « XOR ou exclusif » : Si la clé ordinale est comme ci-dessus 011 111 101 011 100 110 000 010 , donc sous forme 5 concaténée K = 011111101011100110000010 et si le message M est par exemple 110110010101101100010111 On peut chiffrer ce message de même longueur que la clé (soit ici 24 bits) par K= 0 1 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 1 0 + 10 M= 110110010101101100010111 C= 101001111110011011111101 où C est le chiffre de M. III- Les procédés et techniques de « Cryptographie Ordinale » objets de la présente demande permettent dès lors les applications cryptographiques suivantes. 15 La présente invention permet donc de muter une clé secrète , donnée sous forme de clé ordinale , dans un système de chiffrement symétrique , par la seule donnée d'un n-uplet de l'ensemble de définition E de la clé secrète K , appelée clé primitive ou clé racine.Ils permettent de chiffrer en conséquence des clés ordinales par un tel n-uplet . 20 La présente invention résout donc le problème suivant : dans le cadre d'un cryptosystème symétrique, pouvoir changer la clé de chiffrement secrète de manière publique et sûre pour le cas où ledit cryptosystème utilise une clé ordinale , puisqu'on rappelle que les procédés cryptographiques objet de l'invention utilisent uniquement ce type de clé . Notamment une clé sous forme de suites de bits , si elle est spécifiquement une permutation de 10,11n , n donné, 25 peut être mutée de manière publique et sûre par le procédé. Selon un autre mode de réalisation ils permettent en outre un protocole d'identification et selon encore un autre mode de réalisation un protocole d'échange de clé. On mentionne ici par ailleurs que les « Procédés de Cryptographie Ordinale » qui vont être décrits par la suite sont liés d'un point de vue conceptuel à des procédés ayant fait l'objet d'une précédente 30 requête en délivrance de brevet ( requête déposée le 30/10/2012 n° d'enregistrement 12/02902). Il n'est pas nécessaire cependant de connaître le contenu de l'exposé technique de la demande de brevet du 30/10/2012. Tous les éléments nécessaires à la compréhension des procédés cryptographiques ci-après exposés sont présents dans cette description. SECTION II ANNEXE: THEORIES ET RESULTATS MATHEMATIQUES La présente Annexe mathématique est un extrait de celle jointe à la description des Procédés de 5 Cryptographie Ordinale ayant déjà fait l'objet d'une demande de brevet en date du 30/10/2012 , n° d'enregistrement 12/02902. On peut donc éventuellement se reporter à l'annexe mathématique figurant dans le demande de brevet n° 12/02902 si celle-ci est connue. Sinon les éléments mathématiques nécessaires à la compréhension de l'exposé technique des 10 procédé cryptographiques faisant l'objet de la présente requête en délivrance de brevet figurent dans l'annexe mathématique qui va suivre. PARTIE I_''tg -LrtftebRDINAL,ETMPERATICIN ORDINALE. P[n] est l'ensemble des permutations de l'ensemble des n premiers entiers {1,2'n} On appelle calcul ordinal l'opération qui attribue à une suite de n premiers entiers naturels donnés dans un ordre quelconque un autre ordre qui est déterminé par une autre suite de n premiers entiers 5 de IN. Cette opération, dite opération ordinale , est notée par son initiale O. On appelle par ailleurs suite ordinale numérique une telle suite formée par une permutation des n premiers entiers naturels ( S est une suite ordinale si S = (Xi, Xi,....Xn) avec Vi , Xi e {1, .,n} et Vi,j , Xi , {1, .n} étant l'ensemble des n premiers entiers naturels). Exemple : soit S la suite des 5 premiers entiers naturels ordonnés de la manière aléatoire suivante : 10 ( 2 3 5 1 4). S est une suite ordinale numérique . L'ordre de cette suite peut être modifié par une autre suite S' des 5 premiers entiers de IN ( ex : S' = (5 1 4 2 3)) en appliquant l'opération ordinale 0 de la manière suivante : Soit S = ( 2 3 5 1 4) et 15 soit S'= (5 1 4 2 3) 00000 00000 00000 S'OS= (5 1423)0(23 51 4)=(42 135) S' S S" La suite S est la suite permutée, 20 La suite S'est la suite permutante, La suite S" est le produit de l'opération ordinale. Les chiffres dans les ronds noirs représentent les numéros d'ordre des éléments des trois suites S , S' et S". Comment le produit S" est il obtenu ? 25 La suite S"= (4 2 1 3 5) a été obtenue en permutant S = (2 3 5 1 4) à partir des éléments de S'qui représentent les numéros d'ordre des éléments de S. C'est à dire que le calcul s'effectue de la manière suivante : «En position 0 dans S" : le 5 ème élément de S» «En position 0 dans S' : lel er élément de S» 30 «En position 0 dans S" : le 4_ème élément de S» «En position 0 dans S" : le 2_ème élément de S» «En position 0 dans S' : le 3 ème élément de S» (Les chiffres en gras soulignés ci-dessus sont ceux constituant les éléments de la suite permutante '). 35 Ainsi si la suite permutante est S' = ( Xi X2 X3X4X5) , alors on obtient S" par la formule générale suivante : «Le i-ème élément dans S" est égal au Xi.. ème élément de S ». Dans l'exemple repris ci-dessous , le 1-ème élément (le premier élément ) de S" est égal au X i-ième élément de S , c'est à dire au 5-ième élément de S car Xi =5 dans S'. 00000 00000 00000 (51423)0( 23514)=(42135) S' S S" Cette définition de l'opération ordinale peut être appelée définition « intuitive » ou « visuelle » , (car il suffit de « voir » sous les n° d'ordre les éléments de la suite S). DEFINITION FORMELLE DE L'OPERATION ORDINALE L'opération ordinale a été définie ci-dessus par une formule générale qu'on a qualifiée d'intuitive. 10 On définit dans cette section de manière plus formelle l'opération ordinale. On la définit dans le cas où elle est binaire, c'est-à-dire quand elle n'a que deux arguments comme dans le cas ci-dessus selon le schéma S O S'. On la définira aussi dans le cas où elle est n-aire (avec n suites) , pour un n quelconque , selon le schéma Si 0 S2 0 S3 0 Sn.. 15 A-DEFINITION ORDINALE BINAIRE Une permutation des éléments de {1, n} est donnée par une bijection de {1, n} dans {1, n}. Ainsi la permutation S' = ( 5 1 4 2 3 ) est donnée par la fonction bijective suivante p' (p' pour « position » ) qui associe à un numéro d'ordre (à un rang dans la suite) l'élément qui figure à ce 20 rang , p'(i) = j signifiant ainsi naturellement : « en position i le j » : 00000 S' = (5 1 42 3 ) , donc p' est définie par p'(1) =5 p'(2) =1 25 p'(3) =4 1),(5) -3 00000 De même la permutation S = (2 35 14) est donnée par la bijection p ci-dessous : p(1) = 2 p(2) = 3 P(3) = 5 p(4) = 1 5 p(5) = 4 00000 et S" = ( 4 2 1 3 5 ) est donnée par p" : p"(2) = 2 10 p"(3) = 1 p"(4) = 3 P"(5) = 5 Pour une suite S = , sa fonction ordinale p , fonction de {1,2.....n} dans {1,2, .....n}, est donc définie par : 15 p'(i) = Xi. Comment traduire dès lors avec la notation fonctionnelle utilisant ces fonctions « p », « p'» et « p" » l'opération ordinale donnée par l'équation ordinale donnée page 1 et reproduite ci-après ? 00000 00000 00000 20 ( 5 1 4 2 3 ) 0 ( 2 3 5 1 4) = ( 4 2 1 3 5) S' S S" Les chiffres dans les cercles noirs représentent le rang (le numéro d'ordre) des éléments des suites S', S et S". Calculer la suite S" par l'opération ordinale à partir de S et S' consiste à chercher pour chaque 25 numéro d'ordre de S" l'élément de {1,2,3,4,5} qui lui est assigné. D'après la définition intuitive de l'opération ordinale on a: «Si la suite permutante est S' = (Xi X2 X3 Xa X5) , alors le i-ème élément dans S" est le Xiième élément de S , qui est la suite permutée» Ce qui signifie , en utilisant les fonctions p" et p et la notation fonctionnelle : p"(i) = p (Xi) , avec p fonction ordinale de S , suite permutée , et p" fonction ordinale de S", produit ordinal. Dans l'exemple ci-dessus : p"(1) , qui est 4 , est égal à p( Xi) qui est p(5) puisque Xi = 5 (voir 5 composition de S' ci-dessus). Donc p"(i) = p (Xi) . Mais par définition p'(i)= Xi. Donc en substituant : p"(i) = p(p'(i)). p est la fonction ordinale de la suite permutée 10 p' la fonction ordinale de la suite permutante p" la fonction ordinal du produit L'opération ordinale binaire peut ainsi être définie comme une composition de fonctions. Les fonctions de type «p » (p , p' , p") à partir desquelles sont calculées les produits ordinaux peuvent être appelées fonctions ordinales associées aux suites ordinales. 15 Elles associent à un indice «j », c'est à dire un numéro d'ordre , l'élément de la suite S figurant au rang « i ». On définit maintenant l'opération ordinale n-aire. B-DEFINITION ORDINALE m-AIRE On définit maintenant l'opération ordinale lorsqu'on l'utilise pour un nombre quelconque m de 20 suites ordinales , c'est-à-dire lorsque l'on veut calculer le produit Si 0 S2 0 0 Sm, produit de m suites ordinales (l'opération est m-aire , on réserve n pour le nombre d'éléments des suites). Soient donc Si , S2, S3, Sm , m suites ordinales qui sont des permutations de {1, n}. Soient pi , pz , p3 , pm leurs fonctions ordinales associées. 25 On définit le produit Si 0 S2 0 S3 0 0 Sm de la manière suivante : Si 0 S2 0 S3 0 Sm = (Xi, Xi, Xn) , avec: Xi = pm ( pm-1( ( p2 ( pi ( i))) ) , m parenthèses fermantes à droite. Ou bien si l'on appelle Sp le produit ordinal de Si 0 S2 0 S3 0 Sm , et pp sa fonction ordinale associée : pp(i) = pm(pm-1(.. ...... (p2(pi(i))).....) , m parenthèses fermantes à droite. Cette formule est déduite de la définition binaire de l'opération ordinale et se démontre par 5 récurrence sur le nombre de suites. On ne reproduit pas ici cette démonstration qui repose sur la loi de composition de fonction. (Ainsi pour trois suites Si , S2 , et S3 par exemple, le produit ordinal (Si 0 S2 0 S3) est donné par la composition de fonction p3(p2(pi(i))) , où les fonctions pi ,P2 ,p3 sont les fonctions ordinales respectives de Si, S2 , et Si). 10 COMMENTAIRE SUR LE CALCUL ORDINAL: Bien que le calcul ordinal se réduise au calcul de composition de fonctions le calcul ordinal peut être pratiqué de manière autonome à partir des définitions intuitives de l'opération ordinale. Ses objets sont des suites de n premiers entiers naturels et l'opération entre ses objets est l'opération O. Il n'est pas nécessaire du reste de qualifier d'intuitive l'opération ordinale lorsque l'on écrit et 15 calcule par exemple : 00000 (2 5 1 3 4) 0 ( 3 4 2 5 1) - ( 4 1 3 2 5). On peut dire qu'on obtient la suite ( 4 3 5 1 2) tout simplement par utilisation de l'opération ordinale. 20 La notion d'autonomie que l'on vient d'utiliser se justifie par le fait que l'on se place ici sur le plan du calcul. Le calcul ordinal est autonome par rapport au calcul de composition de fonctions. Il n'est pas nécessaire , par exemple , si l'on veut calculer le produit ordinal écrit ci-dessus de poser les fonctions ordinales associées aux suites et de procéder par composition de fonctions. Le calcul ordinal a été défini en termes de composition de fonction pour le motif que les propriétés 25 du calcul ordinal sont plus faciles à démontrer quand on utilise la définition en termes de composition de fonctions. La définition en termes de composition de fonctions sera donc en général utilisée dans la suite de cette partie mathématique. Du point de vue des calculs toutefois ceux-ci peuvent être menés aussi bien par composition de fonction que par utilisation des définitions intuitives du calcul ordinal. Cette dernière méthode est 30 par ailleurs beaucoup plus rapide en cas de calcul fait à la main. Pour la description des applications cryptographiques la définition intuitive ( qui présente les calculs sous la forme S' 0 S = S" ) sera utilisée conjointement avec la définition par composition de fonctions car elle est souvent plus pratique pour représenter et comprendre les problèmes. RESUME Concernant les applications en cryptographie on doit retenir que le calcul ordinal permet de permuter une suite de n premiers entiers naturels ( qu'on appelle suite ordinale numérique) , par exemple les cinq premiers entiers naturels , les dix premiers , cent premiers etc , par la 5 donnée d'une autre suite de n premiers entiers naturels. Sur le plan mathématique cette permutation s'effectue par composition de fonctions bijectives. Le calcul ordinal est donc un calcul de composition de fonctions. Si la suite S est la suite permutée , la suite S' la suite permutante , et la suite S" le résultat de 10 la permutation, appelé produit, alors l'opération s'écrit : S' 0 S = S". 0 étant l'opération ordinale. Le calcul par composition de fonctions s'effectue selon la formule : P"(i) = P(P'(i)) 15 où : p est la fonction ordinale associée à la suite permutée S p' est la fonction ordinale associée à la suite permutante S' p" est la fonction ordinale associée à la suite S" résultant de la permutation, appelé produit. Si l'on pose en inversant S et S' que S 0 S' = S" la formule est inversée : p"(i) = p'(p(i)). 20 Les fonctions ordinales de type « p » (p , p' , p ") étant définies ainsi : Pour une suite S quelconque telle que S = ( Xi Xi Xn ) , sa fonction ordinale bijective associée p , de (1'n} dans {1'n} , est définie par : p(i) = Xi. (La fonction ordinale p d'une suite ordinale associe à un indice , c'est-à-dire à un numéro d'ordre (à un rang) l'élément de la suite qui figure sous ce numéro d'ordre) 25 Le calcul du produit ordinal S'O S = S" peut aussi s'effectuer de manière intuitive selon la définition dite « intuitive visuelle »: « Si la suite permutante est S' = (Xi Xi Xn) , alors le i-ième élément dans S" est le Xi- ième élément de S ». Enfin l'opération ordinale peut aussi être n-aire. 30 A plusieurs suites ordinales Si ,S2 , .....,Sm peut être associé un produit ordinal Sp défini par : Sp = Si 0 S2 0 Sm. Le calcul de Sp peut se faire comme pour un produit binaire soit par composition de fonctions soit de manière intuitive par application m-1 fois de l'opération O. Dans la partie suivante on établit que les suites ordinales numériques munies de l'opération ordinale possèdent une structure algébrique de groupe. PARTIE U-.. GROUPES ORDINAUX Cette partie de l'annexe mathématique comportant beaucoup de données mathématique un résumé synthétique pour les applications cryptographiques est donné en premier La partie développée est à la suite. RESUME A-Soit n un entier naturel quelconque. P[n] est l'ensemble des permutations de {1,2, n}. Cet ensemble muni de l'opération ordinale 0 possède une structure de groupe. Par ailleurs , soit S une suite ordinale appartenant à Pin]. Alors l'ensemble {Sx} qui est défini par le/ x E N} est un sous-groupe commutatif de Pin]. Si signifiant l'opération 0 itérée j-1 fois, par exemple pour j = 3 : S3= SOSO S. Exemple d'ensemble {Sx} : soit S = (3142) une suite ordinale de P[n] , p sa fonction ordinale. L'ensemble {e} généré par S est alors égal à: S= (3142) S2=(4321) S3=(2413) S4= (1234) qui est équivalent à: P1(1) 1)1(2) 1)1(3) P1(4) P2(1) P2(2) p3(2) 1)2(3) p3(3) P2(4) p3(4) p3(1) P4(2) P4(3) P4(4) P4(1) En termes de composition de fonction les Sous Groupes Ordinaux Commutatifs {S x} peuvent être définis de manière équivalente de la façon suivante : Soit p une bijection donnée de {1,2, n} dans {1,2, n} , alors p génère un ensemble {Sx} défini par {px / x E N} Les ensembles {Sx1 sont par ailleurs toujours fini en ce sens qu'ils sont cycliques et leur cardinal est égal au ppcm des nombres entiers représentant la longueur des cycles fonctionnels composant S (voir B ci-dessous pour définition des cycles fonctionnels d'une suite ordinale. Si l'on note a ce ppcm , l'ensemble {Sx} est égal à l'ensemble {Sa} qui est défini par {Sa}= fSi/ j E {1,2,.....a} 1. Pour ce motif on notera parfois dans la suite par {Sa} au lieu de 15x1 les sous groupes ordinaux commutatifs de P[n] générés par une suite ordinale S. On appellera aussi toujours dans la suite Groupe Ordinaux Commutatifs (GOC) au lieu de sous-groupes ordinaux commutatifs les ensembles {Sa}. Les GOC ont par ailleurs les autres propriétés suivantes : L'élément neutre e = ( 1 2 .n) est toujours égal Ils sont cycliques en ce sens que pour tout entier supérieur à a , quelle que soit la suite S, on a toujours Sxa+w = ,w w étant le reste de la division de (xa + w) par a. Deux suites S et S' commutent si et seulement si elles appartiennent au même Groupe Ordinal 20 Commutatif. 13IEn dernier point enfin , important pour les applications cryptographiques : à chaque suite ordinale sont associés des cycles fonctionnels exponentiels. Un Cycle Fonctionnel Exponentiel Ordinal C pour un argument À de la fonction ordinale p est la suite des « puissances » de la fonction p définie par les identités suivantes: 25 pl( = ei p2( ) e2, p"( X) = X . où chaque eh est la valeur de ph( À) et où n est le plus petit entier tel que p"( X) = X. Ce sont ces cycles qui déterminent le GOC associé à chaque suite S. Lorsque ces cycles sont présentés sous forme de « puissances » de la fonction p pour l'élément initial du cycle , on les appelle « Cycles Fonctionnels Exponentiels Ordinaux » , en abrégé 30 CFEO. 009.0904900 Par exemple la suite S = ( 3 9 5 7 8 4 6 1 2) de P[9] possède trois CFEO qui sont : p°(1) = 1 p°(2) = 2 p°(4) = 4 p1(1) = 3 p1(2) = 9 p1(4) = 7 p2(1) = 5 p2(2) = 2 p2(4) = 6 p3(1) = 8 p3(4) = 4 p4(1) = 1 (On ajoute par convention au début de chaque cycle que j, premier élément du cycle est égal à p°(i) , cela pour le motif que si h est la longueur du cycle on a pn+h(i) puisque ph(i) = I. Donc pn+h(i) pn+O(i) = pn(p 0(i)) = pn(i) et i = po(i) ). PARTIE DEVELOPPEE On rappelle qu'on nomme suite ordinale numérique une permutation des n premiers entiers naturels , n étant donné. Ainsi (2 3 5 1 4) est une suite ordinale de {1,2,3,4,5}. On appelle dès lors ensemble ordinal l'ensemble des permutations des n premiers entiers naturels pour un n donné. On note P[n] un tel ensemble. P[5] est ainsi l'ensemble des permutations de {1,2,3,4,5} . On établit dans cette partie que les ensembles ordinaux munis de l'opération ordinale possèdent une structure de groupe (I). En outre , pour un ensemble ordinal donné P[n], on verra ci-après que des sous groupes de P[n] sont commutatifs (II). Dans une troisième partie on énoncera quelques résultats concernant les sous-groupes commutatifs de P[n] (III). I-Structure de groupe des ensembles ordinaux. La structure de groupe des ensembles ordinaux résulte du résultat connu selon lequel l'ensemble des bijections d'un ensemble E sur lui-même muni de la loi de composition entre fonctions possède une structure de groupe. L'opération ordinale étant une composition de fonctions , fonctions bijectives de {1, n} dans {1, .n} , la structure de groupe des ensembles ordinaux munis de l'opération ordinale découle de ce résultat. Soit maintenant P[n] un ensemble ordinal. P[n] est l'ensemble des permutations des n premiers entiers naturels , c'est-à-dire l'ensemble des permutations de {1, n} .0n décrit ci-après comment obtenir des sous-groupes de P[n] commutatifs et on démontre leur existence. II-Existence de sous-groupes ordinaux commutatifs de P[n] Soit S = (Xi .Xn) une suite ordinale donnée de P[n]. On note S2 le produit S 0 S , S3 le produit SOSO S, Sx le produit S 0 S 0 .OS. (0 appliquée x-1 fois) La suite S est d'exposant 1 , c'est à dire S = S'. On note {Sx}de tels ensembles. L'ensemble {Sx} est donc l'ensemble {Sx / x E IN } . 10 On donne un exemple d'un tel sous ensemble de P[n]. Soit par exemple S = (3142) une suite ordinale appartenant à P[4]. On a: S2=(3142)0(3142)=(43 21) S3=(4321)0(3142)=(2413) 15 S4=(2413)0(3142)=(1234) Les suites S , S2,53, S4 sont des permutations de { 1,2 , 3 , 4}. L'ensemble { S , S2, S3, S4} ,c'est à dire l'ensemble { ( 3 1 2 4) , ( 43 2 1) , ( 2 413 ), ( 123 4) J est donc clairement un sous- ensemble de P[4] puisque toute permutation des éléments de {1 , 2, 3 , 4} appartient par définition à P[4]. 20 On note {S4} cet ensemble. On remarque que cet ensemble ne comporte pas d'autre élément que ces quatre suites, c'est à dire que pour tout x tel que x> 4 la suite Sx E 54. Si l'on calcule Sx pour x > 4 en effet, on obtient : S5=S40 S-(1234)0(3142)=(3142)=S 25 S6=550 S=(3142)0 (3142) =(4321)=S2 S7=S60S-----(4321)0(3142)=(2413)=S3 S8=S70S= (2413)0(3142) = (1234) = S4 Puis si l'on itère à nouveau : S9=S40S=(1234)0S-(1234)0(3142)=S40S=55 De manière cyclique donc les suites S, S2, S3, S4 réapparaissentlorsque l'on calcule Sx pour x> 4. On note aussi que ce caractère cyclique des ensembles {Sx} permet qu'une suite S puisse être définie pour un exposant négatif : S3 dans notre exemple est ainsi égal à S4-3= Sl. Pour la suite S = (3142) l'ensemble {Sx} est donc égal à {S4}. Autre exemple d'ensemble {Sx} : Soit la suite S = (3 95 78 46 1 2) prise sur P[9]. On peut vérifier que pour cette suite S l'ensemble {Sx} est : 000000000 S= (3 95 78 46 12) S2= (5 28 61 7439) 53= (8 91 43 67 52) S4= (1 23 75 46 89) S5= (3 95 68 74 12) S6= (5 28 41 67 39) S7= (8 91 73 46 52) S8= (1 23 65 74 89) 59= (3 95 48 67 12) S10= (5 28 71 46 39) S11= (8 91 63 74 52) S12= (1 23 45 67 89) Dès lors , on énonce maintenant que : Les ensembles de type {Sx} définis par {Sx}= {Sx / x E fsJ } munis de l'opération 0 sont des sous-ensembles commutatifs de P[n] ( donc des Sous-Groupes Ordinaux Commutatifs de 25 P[n]). On le démontre ci-après. Démonstration :(commutativité , stabilité , présence de l'élément neutre ): La commutativité et la stabilité des ensembles {Sx} muni de l'opération 0 résultent simplement de la loi de composition de fonctions bijectives. On démontre donc sommairement ces deux propriétés. 15 20 Si Sw et SY sont deux suites ordinales quelconques de {Sx} leurs fonctions ordinales associées sont pw et pY (avec par exemple, pw(i) = p(p(p(...p(i))..) , avec w parenthèses à gauche et à droite , c'est à dire p itérée w fois). Dès lors Sw O SY = SYO Sw car epw(i)) pw(pY(i)) pour tout i , et donc Sw et SY commutent. 5 De même pour la stabilité de l'opération 0 dans {Sx} on a Sw 0 = S" . Dès lors 0 est stable dans {5X} si SY'w appartient à {5'}. Mais SY'w appartient nécessairement à {Sx} puisque {Sx} = {Sx / x E IN let que (y + w) E IN. On passe maintenant à la démonstration que l'élément neutre appartient nécessairement aux ensembles de type {S'i}. 10 Cette démonstration sera plus développée. L'élément neutre appartient aux ensembles {el. La démonstration de ce résultat repose sur les « cycles fonctionnels ordinaux » qui seront définis ci-après et qui sont importants pour les systèmes de cryptographie exposés ci-après. Les suites composant les ensembles {e} étant en effet obtenues par itération de l'opération 0 15 chaque élément de Si est en fait obtenu par itération de la fonction p. La notation pi signifiant la fonction p itérée j fois ( p(p(i)) p2(i) , p(p(p(i))) = p3(i) , etc...). Ainsi pour S = (3124) qui génère l'ensemble {54} construit ci-dessus et reproduit ci-après : S =(3142) S2 =(4321) 20 S3 =(2413) S4 = (1234 ) , On peut vérifier que {S4} est égal à: 25 s= (p(1) 1)(2) 1)(3) 1)(4) ) S2= ( P2(1) P2(2) 1)2(3) p3(3) 1)2(4) ) p3(4) ) S3= ( p3(1) p3(2) P4(3) P4(4) ) S4 = ( P4(1) 1)4(2) Où p est la fonction ordinale associée à S = (3142) définie par: p(1) = 3 (« en position 1 le 3 ») p(2) = 1 (« en position 2 le 1») p(3) = 4 (« en position 3 le 4 ») p(4) = 2 (« en position 4 le 2 ») On passe maintenant à la démonstration que les ensembles {e} contiennent toujours l'élément neutre. L'élément neutre des ensembles {e} est la suite e = (1 2 .n) c'est-à-dire la suite des n premiers entiers naturels donnés dans l'ordre standard ( exemple : e = (1 2 3 4 5) pour P[5] ). On montre donc que les ensembles el contiennent forcément l'élément neutre, c'est à dire qu'une suite ordinale S = (Xi.....Xi.....Xn) de P[n] étant donnée il existe forcément un nombre j tel que Si= (1 2 n). La démonstration que les ensembles {e} contiennent nécessairement l'élément neutre repose sur le fait que les suites ordinales peuvent être décomposées en cycles fonctionnels. Le paragraphe suivant (a) est donc consacré à cette propriété des suites ordinales .Ce paragraphe est le plus important de la partie mathématique II car les cycles fonctionnels sont 15 à la base de la plupart des applications cryptographiques qui seront exposées par la suite. On montrera ensuite dans un second paragraphe (b) que l'élément neutre appartient nécessairement aux ensembles {Sx}. a- Décomposition des suites ordinales en cycles fonctionnels Les suites ordinales peuvent être décomposées en cycles fonctionnels. 20 On commence par donner deux exemples de décomposition d'une suite ordinale en cycles fonctionnels. Exemple 1 : 000000000 Soit la suite ordinale S = (7 6 9 1 4 3 5 2 8) appartenant à P[9]. 25 La fonction ordinale p associée à S est donc ainsi définie : P (1) = 7 p (2) = 6 1) (3) = 9 p (4) = 1 30 p (5) = 4 p (6) = 3 P (7) = 5 p (8) = 2 P (9) = 8 On extrait dès lors de cette définition de la fonction p les identités suivantes : p (1) = 7, p (7) = 5 , p (5) = 4 , p (4) = 1 ( c'est-à-dire qu'on prend p (1) , p(p(1)..... , p(l) , etc , jusqu'à ce que l'on revienne à 1 comme valeur de p pour l'argument 1, c'est à dire jusqu'à ce que l'on ait trouvé un x tel que px (1) = 1). on fait de même pour 2: p (2) = 6 , p (6) = 3 , p (3) = 9 , p (9) = 8 , p (8) = 2 Il n'existe pas d'autre identité composant la fonction p , les valeurs 7 , 5 , 4 ,1,6,3,9,8,2 étant celles composant la suite S. Les suites de valeurs 7 , 5 , 4 , 1 et 6 , 3 , 9 , 8 , 2 constituent ainsi les cycles fonctionnels 10 composant la suite S. Il en existe 2. Ce sont des cycles puisque si l'on poursuit par exemple pour la première suite de valeurs , après avoir écrit p (4) = 1, on obtient p (1) = 7 et l'on revient aux mêmes identités. On peut par ailleurs les représenter par des suites fléchées de la manière suivante : 147454441 15 24643494842 On rajoute le 1 au début du premier cycle et le 2 au début du second cycle afin de mettre en évidence l'argument de la fonction p à partir duquel on a généré le cycle et afin aussi de montrer que l'on est bien en présence d'un cycle. Les flèches indiquent la valeur de la fonction ( qui est à droite de la flèche), pour l' argument, 20 (qui est à gauche de la flèche) . 147 signifiant ainsi naturellement « on associe à 1 le 7 » ou bien « on envoie le 1 sur le 7 ». le cycle entier étant ainsi lu comme suit : on envoie le 1 sur le 7 , puis le 7 sur le 5 , puis le 5 sur le 4 , puis le 4 sur le 1. Chaque chiffre étant tour à tour pris comme valeur puis comme argument. 25 Exemple 2: 000000000 Soit S = ( 3 9 5 7 8 4 6 1 2) une suite ordinale de P[9]. Sa fonction ordinale p associée est donc définie ainsi : 30 p (1) = 3 p (2) = 9 1) (3) = 5 p (4) = 7 P(5)=8 p (6) = 4 p (7) = 6 p (8) = 1 p (9) = 2 On a dès lors : p (1) = 3 Puis : , p (3) = 5 , p (5) = 8 , p (8) = 1 , qui constitue le premier cycle fonctionnel p (2) = 9 Puis : , p (9) = 2 , qui constitue le second cycle fonctionnel, p (4) = 7 , p (7) = 6 , p (6) = 4 , qui constitue le troisième cycle fonctionnel. On constate donc que la suite ( 3 9 5 7 8 4 6 1 2 ) possède trois cycles fonctionnels. On remarque aussi que dans le troisième cycle la première identité ne donne pas la valeur de 3 pour 15 la fonction p mais la valeur de 4. En effet 3 figure déjà dans le premier cycle ( on voit en effet que p (3) = 5 figure déjà dans le premier cycle).C'est donc p (4) = 7 qui est la première identité du troisième cycle. Sous forme de suite fléchée les trois cycles sont : 143454841 20 24942 4474644 Les cycles fonctionnels d'une suite ordinale S donnée sur P[n] sont donc les suites d'éléments de S (c'est à dire les suites de valeurs de la fonction p) obtenus après application de l'algorithme suivant : 25 1) On calcule : p(1) ,p (p(1)) , p (p (p (1))) p"(1) , jusqu'au nombre x tel que px(1) = 1, les valeurs : p(1) , p ( p (1)) , p ( p ( p(1))) , ....px (1) , constituent le premier cycle. Puis, s'il n'existe pas de nombre y tel que p' (1) = 2 , c'est à dire si 2 ne fait pas partie du premier cycle on calcule : 2) p (2) , p ( p(2)) , p (p( p(2))) pn(2), jusqu'au nombre x tel que px(2) = 2 30 les valeurs : p(2) , p( p (2)) 'p (p ( p(2)))'px (2) , constituent le second cycle. Puis, s'il n'existe pas de nombre w ou y tels que le (1) = 3 ou I)" (2) = 3 , c'est à dire si 3 ne fait pas partie des deux premiers cycles , on calcule : 3) p (3) , p(p(3)) , p (p ( p(3))) p1(3), jusqu'au nombre x tel que 11'1(3) = 3 les valeurs p(3) , p(p(3)) , p (p(p (3)))),...., px (3) constituent alors le troisième cycle, 5 et ainsi de suite jusqu'à ce que la totalité des éléments de S figure dans les cycles. A chaque étape , c'est-à-dire à chaque fois que l'on a obtenu un cycle , on doit chercher si l'argument i de la fonction p à partir duquel on veut générer un nouveau cycle ne fait pas partie d'un des cycles précédents. Si tel est le cas on doit tester l'argument suivant i + 1.Et ainsi de suite. On peut donc définir un cycle , pour une suite ordinale S de P[n] donnée et pour un indice i 10 quelconque de {1 , 2 , n}, comme la suite des valeurs des « puissances » de sa fonction ordinale p associée pour l'indice i (ex : p(i) = p1(i) , p(p(i)) = p2(i) , p(p(p(i))) = p3(i) , etc..) jusqu'à ce que soit obtenu un entier j tel que pi(i) = i. Autre méthode : Il existe une autre méthode pour obtenir les cycles fonctionnels d'une suite ordinale. 15 Les cycles fonctionnels d'une suite ordinale peuvent en effet s'obtenir sans passer par le calcul par composition de fonctions par la simple lecture de la suite. 000000000 Soit en effet la suite de P[9] , S = ( 7 6 9 1 4 3 5 2 8). 20 On obtient facilement , à la lecture de cette suite, en observant les numéros d'ordre de ses éléments : 147 (en position 1 le 7 , c'est à dire p(1) = 7), puis on utilise le 7 comme argument de p , on obtient donc : 745 (en position 7 le 5 , p(7) = 5) , 25 etc. On obtient ainsi le premier cycle : 147454441 Le premier cycle étant construit on teste 2 , on constate que 2 n'appartient pas au premier cycle. On construit donc le second cycle à partir de 2 : En position 2 le 6 , en position 6 le 3 , etc. On obtient donc : 24643494842 A ce stade on constate que les chiffres 3 , 4 , 5 , 6 ,7 ,8 , 9 , c'est-à-dire les éléments de S supérieurs à 2, figurent déjà dans les deux premiers cycles. Les deux premiers cycles générés à partir de 1 et 2 sont donc les deux seuls cycles fonctionnels composant la suite S = ( 7 6 9 1 43 5 2 8) . L'argument de départ pris pour générer un cycle est par ailleurs sans incidence sur le nombre de cycles et le nombre d'éléments de chaque cycle. Ainsi dans l'exemple ci-dessus on aurait pu pour générer le premier cycle partir de 5 au lieu de 1. 10 On aurait obtenu : 544414745 au lieu de 147454441. Ainsi pour tout élément x d'un cycle C donné , le nombre j tel que pi (x) = x est le même.Ce nombre j est la longueur du cycle. Il est aussi le cardinal de l'ensemble des éléments composant un cycle donné. Dans la suite fléchée 147454441, par exemple , j = 4 ( en effet : p4(1) = 1 , p4(7) = 7 , p4(5) = 15 5 , p4(4) = 4). 4 éléments composent ce cycle. Par ailleurs : - pour tout multiple h de j on a aussi ph(x) = x: p8(7) =p12(7) = p16(7) = 7 , etc , pour le cycle ci- dessus de longueur j = 4, par exemple. - Si h> j mais que h n'est pas multiple de j alors ph(x) = pr(x) avex r = reste de h/j : p5(1) = pl (1) 20 = 7 par exemple , toujours pour le cycle ci-dessus de longueur 4. En conclusion de ce paragraphe on doit donc retenir les résultats suivants : Soit S une suite ordinale et p sa fonction ordinale associée. I-) Pour tout indice i appartenant à {1,2 ,.....,n} il existe toujours un nombre j tel que pi(i) = ce qui signifie que i sera en i-ième position dans la suite Si ( par exemple le 3 sera en 3ième 25 position). II-) Pour tous les éléments d'un même cycle le nombre j est le même. III-)Pour tout x tel que 1 x j ,p'(j) appartient au cycle de i. IV-) Le nombre j est la longueur du cycle. V-) Dans un cycle C donné , ph(i) = i pour tout nombre h multiple de j. Si h n'est pas multiple de j mais que h > j alors ph(i) = Pr() , avec r = reste(h/j) . Cela résulte du caractère cyclique des cycles fonctionnels. On montre maintenant que pour toute suite S appartenant à P[n] il existe toujours un nombre a tel 5 que Sa = (1 2.....n) , c'est à dire la suite des n premiers entiers naturels donnés dans leur ordre standard. Ce qui signifie que l'élément neutre appartient nécessairement à tout ensemble {Sx}. b- L'élément neutre appartient nécessairement à tout ensemble {Sx}. Soit en effet S une suite ordinale appartenant à p[n] . S = (Xi Xi Xn) 10 Cette suite se décompose en cycles fonctionnels comme on vient de le voir. Ces cycles fonctionnels sont en nombre finis (r cycles par exemple) : Ci = 14X114Xk4 iXn41 , de longueur Li 15 . Cr = Xid->X14X14 ->Xci , de longueur Lr Soit maintenant a le ppcm (plus petit commun multiple) de {Li, Lr} , c'est-à-dire le plus petit commun multiple des nombres représentant la longueur des cycles fonctionnels de S. Alors Sa = (1 2 .n). 20 En effet : Soit un indice i quelconque de {1,2,....n}. Alors il existe un nombre j tel que j = Li et pi (i) = i car i appartient forcément à un des cycles de S (j est la longueur du cycle Li auquel i appartient). Donc i est en i-ième position dans Si. Par ailleurs pour tout multiple h = xj de j on a aussi ph (i)= i 25 Mais alors i est aussi en i-ième position dans Sh. Or par définition le ppcm a de {Li, .,Lr} est un multiple de j ( j = Li). Donc on a aussi pa(i)= j, c'est-à-dire que i est en i-ième position dans Sa. Mais a est par définition un multiple commun de toutes les longueurs LJ des différents cycles fonctionnels composant S (a = ppcm de {Li, Lr } ). Donc pour tout i on a pa(i) = i et pour tout Xi appartenant à Sa on aura donc Xi = pa(i) = Ce qui signifie que Sa = (1 2 .n) , a étant le ppcm des nombres représentant la longueur des cycles fonctionnels de S. Ainsi l'élément neutre e = (1 2 n) appartient nécessairement à tout ensemble {S'i} généré par une suite S appartenant à P[n]. III-Résultats sur les sous-groupes ordinaux commutatifs de P[n] (ensembles de type {Sx}). On énonce dans cette partie cinq propriétés des sous-groupes ordinaux commutatifs de P[n]. Pour les applications cryptographiques seul le résultat doit être connu et l'on peut se limiter à la seule connaissance de ces résultats qui sont écrits en gras. Propriété 1 : Le nombre a , égal au ppcm des longueurs des cycles composant la suite S , est le plus petit nombre x pour lequel Sx = (1 2 n). Cela résulte du fait que pour tout multiple commun h des longueurs des cycles composant une suite ordinale S on a Sh = (1 2 n) Par ailleurs c'est a , ppcm de ces longueurs , qui est par définition le plus petit de ces multiples communs. Donc a est le plus petit nombre x pour lequel 5' = (1 2 n). Exemple : 000000000 Soit la suite ordinale de l'exemple 1, S = ( 7 6 9 1 4 3 5 2 8) Les cycles de cette suite sont : 147454441 (sous forme fonctionnelle : p(1) = 7 , p2(1) = 5 , p3(1) = 4 , p4(1) = 1) 24643494842 (sous forme fonctionnelle : p(2) = 6 , p2(2) = 3 , p3(2) = 9 , 114(2) = 8 , p5(2) = 2). Les longueurs respectives de ces deux cycles sont 4 et 5. 25 On a donc ppcm {4,5} = 20 On aura dès lors Sx = (1 2.....n) pour x = 20 et pas avant, et donc a = 20 Vérification (On calcule avec l'opération 0 ,c'est à dire par méthode « visuelle », plus rapide que le calcul par composition de fonction): Ainsi : S=(769143528) 000000000 S2= (769143528)0(76 91 4 352 8)=(5387194 62) 000000000 S3=S20S=(538719462)0(7 691 4 352 8)=(492578136) Etc, On obtient le sous-groupe ordinal commutatif {S29} de P[9] généré par S = (769143528): 000000000 S= (7 69 14 3 52 8) S2= (5 38 71 9 46 2) S3= (492 57 8 13 6) S4= (1 86 45 2 79 3) S5= (723 14 6 58 9) S6= (5 69 71 3 42 8) S7= (4 38 57 9 16 2) S8= (1 92 45 8 73 6) S9= (7 86 142 59 3) S10= (5 23 71 648 9) S11= (4 69 57 3 12 8) S12 (1 38 45 9 76 2) S13= (7 92 14 8 53 6) S14= (5 86 71 2 49 3) S15= (423 576 189) S16= (1 69 45 3 72 8) S17= (7 38 149 562) S18= (5 92 71 843 6) S19= (4 86 57 2 19 3) Sw= (1 23 45 6 78 9)=e On a donc bien Sx = (1 2 n) pour x = 20 et 20 est le plus petit nombre ayant cette propriété. (On aura par ailleurs S" = e pour tout h multiple de 20 ; et pour tout entier w supérieur ou égal à 20 on aura S'y E {S20} puisque l'itération de l'opération 0 au-delà de S2° est cyclique : (S"° S) E {s2o1 / pour tout w supérieur ou égal à 20 car S21 = S). Propriété 2: Pour toute suite S , si w > a , alors Sw = Sr , avec r = reste(w/a) , « reste » étant la fonction qui associe à la division de deux entiers leur reste. Cela résulte du caractère cyclique des ensembles {e}. Soient en effet w tel que w = xa + r et S une suite ordinale quelconque (x et r deux entiers tels que : x 0 et 1 r Donc w > a. On a toujours dès lors: Sw = = S'o 5r, avec xa = a + a + .....+a (l'opération + itérée x-1 fois ). Doncea= Sa+a+a - - - +a = Sa 0 Sa 0 .....Sa =e0e0e 0e=e Et: Sxa 0 Sr = e O Sr = Sr, avec r = reste(w/a). 15 Et donc Sw = Sr avec r = reste(w/a). Propriété 3 : le cardinal des ensembles {e}, pour une suite ordinale S donnée est toujours égal à a, ppcm de la longueur des cycles composant S. On a établi en effet que de tels ensembles n'ont jamais un cardinal supérieur à a puisqu'ils sont cycliques pour tout entier supérieur à a. Mais leur cardinal peut il être inférieur à a? 20 En d'autres termes, Soit Si et Sr deux suites ordinales de {e} avec j a et r a et j # r. Peut on avoir Si = 5r9. S est une suite ordinale de P[n]. p sa fonction ordinale associée. Dès lors Si = (p(1) pi(2) pi(n) ) et Sr = ( pr(1) pr(2) pr(n) ) et donc : Si = Sr ssi , pour tout i appartenant à {1,2, n} , on a pi(i) = On montre dès lors que si j a,r Est il possible dès lors que, pour tout i, pour une suite S quelconque , on ait un j et un r avec j et r a , j r, tels que : pi(i) = pr(i) , p étant la fonction ordinale de S? Supposons que cela soit le cas. C'est à dire supposons par l'absurde qu'il existe un j et un r répondant aux hypothèses ci-dessus posées tels que Si = Sr, c'est à dire que pour tout i de {1,2, n} on ait pi(i) = Soit dès lors h un élément quelconque de {1,2, .n} Lh la longueur du cycle de S auquel appartient h. Dès lors puisqu'on a posé par hypothèse que pour tout i , on a pi(i) = pr(i) , on a pour cet h particulier appartenant à S: pi(h) = pr(h) , c'est-à-dire que reste(j/Lh) = reste(r/Lh). Hypothèse (1) On montre dès lors que si j a et r a , avec j r , il existe toujours un autre élément k appartenant à {1,2, n} tel que pi(k) pr(k) . On note {Li} l'ensemble des nombres entiers représentant les longueurs des cycles composant S. a est le ppcm {Li}. On prend arbitrairement j Le reste de la division de r par Lh est aussi 13 par hypothèse (hypothèse (1) ci-dessus) : reste(r/Lh) = reste(j/Lh) ) . Par ailleurs r > j , et donc r = j +A. Donc r = (ix.Lh + (3) + A , avec A multiple de Lh (c'est à dire reste(A/ Lh) = 0), car reste(j/Lh) = reste(r/Lh) = 13. Ainsi : j = 01.1A + 13. r= On prend dès lors un cycle Ck de S de longueur Lk tel que Lk ne divise pas A et un élément k quelconque de Ck. Un tel Ck et sa longueur associée Lk existent car on a A Propriété 4: Soit S une suite ordinale de P[n]. p sa fonction ordinale associée. Ch, Ci , Cm , les cycles fonctionnels de S et w leur nombre. On note {Ch} , {Cj} ,..... {Cm} , les ensembles des éléments appartenant à chaque cycle. Si l'on prend un élément de chaque cycle on forme un w-uplet qui appartient au produit cartésien {Ch} x {Ci} x x {Cm} . On démontre alors que : Propriété 4 :Le nombre de w-uplets différents figurant dans les suites appartenant au Sous-10 Groupe Ordinal Commutatif {Sx} est égal à a. On étudie d'abord cette propriété sur un exemple puis on donnera ensuite une démonstration. 15 Exemple : 9 5 7 8 4 6 1 2 ) une suite ordinale de P[9] . au nombre de 3 (donc w = 3) sont : , de longueur Li = 4 , de longueur L2 =2 , de longueur L4 = 3 Soit S = ( 3 Ses cycles fonctionnels Ci = 1->3->5->8-->1 C2 = 2-->9->2 C4= 4->7-->6--->4 Le ppcm des entiers représentant la longueur des cycles de S est ppcm{LI} = 12. Le sous-groupe ordinal commutatif {S12} généré par S est reproduit ci-après : 20 00 0 00 0 0 0 S = ( 3 9 5 7 8 4 6 1 2) S2 =(5 2 8 6 1 7 4 3 9) S3 =(8 9 1 4 3 6 7 5 2) S4 = (1 2 3 7 5 4 6 8 9) 25 55 = (3 9 5 6 8 7 4 1 2) S6 = (5 2 8 4 1 6 7 3 9) S7 = (8 9 1 7 3 4 6 5 2) S8 = (1 2 3 6 5 7 4 8 9) 58 = (3 9 5 4 8 6 7 1 2) 31 S10=(5 2 8 7 1 4 6 3 9) S11= (8 9 1 6 3 7 4 5 2) S12= (1 2 3 4 5 6 7 8 9) On constate ainsi que les éléments du premier cycle Ci: 3 , 5 , 8 , 1 , reviennent de manière 5 cyclique dans la colonne 0. De même pour les éléments du cycle C2 qui reviennent en boucle dans la colonne 0 et pour les éléments du cycle C4 qui reviennent dans la colonne 0. Dans chaque suite de {S1 2 } figure un triplet appartenant au produit cartésien des ensembles {Ci } , {C2} , {C4}. 10 Les éléments de ces triplets figurent aux colonnes 00 et 0 qui sont les premiers éléments de chacun des trois cycles. On constate par ailleurs que ces triplets sont tous différents et donc puisque a est égal à 12 qu'il existe 12 triplets différents. On a en effet les triplets suivants (chiffres dans les cercles = numéros de colonne) : 0 0 0 0 0 0 3 9 7 5 2 7 2 6 8 9 6 8 9 4 1 2 4 1- 2 7 3 9 6 5 2 4 8 9 7 1 2 6 3 9 4 25 Ces triplets sont au nombre de 12 et sont tous différents. On démontre maintenant la propriété 4: Le nombre de w-uplets différents dans les suites appartenant au Sous-Groupe Ordinal Commutatif {e} généré par une suite S de P[n] est égal à a. Démonstration : 30 La démonstration est analogue à celle de la propriété 3 à la seule différence qu'on ne raisonne plus sur les suites entières du Groupe Ordinal Commutatif mais sur les w-uplets figurant dans les suites, i étant pris non plus dans {1,2,....,n} mais dans {h,j,....m} , l'ensemble des premiers éléments des cycles de S : Ch , Cj , . . .Cm. 15 20 On note wi le w-uplet figurant dans la suite Si et wr le w-uplet figurant dans la suite Sr. On montre que pour un j et un r quelconque : si j a, r a 'j r , alors wi * wr. wr si et seulement si pi(i) pr(i) pour au moins un i appartenant à {h,j,...m} , l'ensemble {h,j, ....m} étant l'ensemble des premiers éléments des cycles Ch , ..., Cm. Supposons par l'absurde le contraire et posons qu'il existe un j et un r répondant aux hypothèses posées ci-dessus tels que : que pour tout i de {h , j , .....m} on ait pi(i) = pr(i). Soit i un élément quelconque de {h , j, .....m} . Alors pi(i) = pr(i) pour deux entiers j et r quelconques répondant aux hypothèses posées. On prend par convention j MIIIIII111111111111-11FIEEMII A- DEFINITION: Soit n un entier quelconque. Soit S et S' deux suites ordinales du groupe ordinal P[n] . L'opération ordinale ainsi qu'on l'a vu permet d'associer à S et S' une suite S" égale à S 0 S': S 0 S' = S" On appelle division ordinale le calcul qui à l'inverse permet d'associer à deux suites S et S" données la suite S' telle que S 0 S' = S". En d'autres termes on cherche la suite S'. Cette suite est inconnue et on la note d'un X entre 10 parenthèses. Ainsi S = (X). La division ordinale , division de S" par S , revient à résoudre l'équation : S 0 (X) = S" Exemple: 15 Soit S et S" deux suites ordinales de P[10]. S = (79108354612) S"= (38105912674) Diviser S" par S revient à chercher la suite (X) telle que : (79108354612) 0 (X) = (38105912674) 20 On trouve dans cet exemple que (X) = (74921635810). On vérifie en effet que: 0000000000 (79108354612) 0 (74 92 163 5810) = (38105912674). Avant de donner le calcul pour obtenir la suite (X) une remarque doit être faite. 25 L'opération ordinale n'étant en effet pas commutative (sauf dans le cas où S et S' font partie d'un Groupe Ordinal Commutatif) le produit S 0 S' n'est pas égal à S' 0 S. Ainsi pour deux suites ordinales données S et S" , résoudre l'équation S 0 (X) = S" ne donne pas en général la même suite (X) que résoudre l'équation (X) 0 S = S. Cherchons en effet, en reprenant les suites S et S" de l'exemple ci-dessus, la suite (W) telle que : (W) 0 (7 9 10 8 3 5 4 6 1 2) = (3 8 10 5 9 1 2 6 7 4) On obtient : (W) = ( 5 4 3 6 2 9 10 8 1 7) 000 0000000 En effet : ( 5 4 3 6 2 9 10 8 1 7 ) 0 ( 7 9 10 8 3 5 4 6 1 2) = (3 8 10 5 9 1 2 6 7 4). et donc (X) # (W). Il existe donc en fait deux types de division ordinale : la division à gauche qui résout S O (X) = S" ( « à gauche » car la suite S connue, diviseur, est à 10 gauche du premier membre de l'équation). La division à droite qui résout (X) O S = S" (« à droite » car la suite S connue , diviseur, est à droite du premier membre de l'équation). Pour les cas où S et S" commutent la division à droite est identique à la division à gauche. On explique maintenant comment est calculée l'inconnue (X) dans une division ordinale. 15 B-CALCUL DE LA DIVISION ORDINALE a-) ler cas : division à gauche On reprend l'exemple ci-dessus. S = ( 7 9 10 8 3 5 4 6 1 2) S" = (3 8 10 5 9 1 2 6 7 4) 20 Comment déterminer (X) dans l'équation: 00 00000000 0000000000 ( 9 1083 54 61 2)0 QQ=(3810591 2674) S' S" La simple lecture (« méthode « intuitive » ou « visuelle ») de l'équation ci-dessus permet de 25 déterminer la suite (X). Cette équation s'interprète en effet naturellement de la manière suivante: « le 3 (en position 1 dans S") est en >me position dans (X) », car 7 est premier élément de S. o donc (X) = ( ------ 3 - - -) Puis: « le 8 (en position 2 dans S") est en 9eme position dans (X) » , car 9 est second élément de S. 00 donc (X) = ( ------ 3 - -8 -) Et ensuite : « le10 (en position 3 dans S") est en 10eme position dans (X) » donc (X) = ( ------ 3- -8 10) « le 5 (en position 4 dans S") est en 8eme position dans (X) » donc (X) - ( 3 5 8 10) « le 9 (en position 5 dans S") est en 3eme position dans (X) » donc (X) = (- -9 - - -3 5 8 10) « le 1 (en position 6 dans S") est en 5eme position dans (X) » donc (X) = (- -9- 1- 3 5 8 10) « le 2 (en position 7 dans S") est en 4eme position dans (X) » 15 donc (X) = (- -9 2 1- 3 5 8 10) « le 6 (en position 8 dans S") est en 6eme position dans (X) » donc (X) = (- - 9 2 1 6 3 5 8 10) « le 7 (en position 9 dans S") est en lere position dans (X) » donc (X) = ( 7 - 9 2 1 6 3 5 8 10) 20 « le 4 (en position 10 dans S") est en 2eme position dans (X) » donc (X) = (7 4 9 2 1 6 3 5 8 10) Cette suite est bien celle qui vérifie : ( 7 9 1083 5 46 12) 0 (X) = (3 8 10 5 9 1 2 6 7 4) On donne maintenant deux formules pour obtenir le résultat d'une division ordinale à gauche. Ces 25 deux formules sont basées sur une notation en termes de composition de fonctions. lere formule: Soit S et S" deux suites ordinales de P[n]. S = ( Z1, 4, Zn) S" = ( Yi, Y,, Y.) 30 Avec pour tout Z. et tout Y , 1 et Y E {1,2, n}. Les fonctions ordinales p et p" associées respectivement à S et S" sont donc : pour tout i appartenant à {1,2, n} , p(i) = Zi , pour S. pour tout i appartenant à {1,2, n} , p"(i) =Y , pour S". Résoudre l'équation (4, 4, Zn) 0 (X) = (Yi, Y' Y.) revient à chercher la fonction ordinale p' associée à l'inconnue (X) et donc à S'. Par définition (définition par composition de fonction) de l'opération ordinale on a: p"(i) = p' ( p(i)) , ou bien en inversant: p' (p (i)) = p"(i). Or, p(i) = Zi et p"(i) = Y. Donc : p'(Zi) = Yi (« en position Zi le Yi »). Cette équation permet de calculer les valeurs de la fonction p' pour chaque valeur de Zi puisque chaque Z et chaque Yi est connue, ce sont les valeurs des suites ordinales S et S" , valeurs prises dans {1,2, n} Deuxième formule: Il est aussi possible d'exprimer p' en fonction de i et non plus en fonction de Z En reprenant en effet la définition de l'opération ordinale on a: P'(P(i)) = p"(i). Mais par définition, i = 1 (p(i)), donc en substituant dans le deuxième membre : Pi(p(i)) = P" (P-1(P(i))) et donc: p'(i) = p"(p-l(i)) - On peut donc aussi calculer S' par la fonction p' selon la formule: Pt(i) = P"(P-1(»). qui est équivalente à la précédente. C'est cette seconde formule plus simple d'application qui sera toujours privilégiée et utilisée par la suite. On aborde maintenant la division ordinale à droite. b-) 2eme cas : division à droite. On reprend les suites S et S" de notre exemple ci-dessus. S = (79108354612) S" = (38105912674) La division ordinale à droite consiste à résoudre l'équation: (X) 0 (79108354612) = (38105912674) Ainsi qu'on l'a vu ci-dessus la solution de cette équation est (X) = (5 4 3 6 2 9 10 8 1 7). 0 00 0000000 (5 4 3 6 2 9 10 8 1 7) 0 (7 910 83 54 61 2) = (38105912674). Comment calculer la division à droite? On simplement lire, comme pour la division à gauche , l'équation à résoudre : 00 00000000 0000000000 IX) 0 (7 9 1083 54 61 2) = (3810591 2674) S' s'interprète en effet de la manière suivante: « le 3 est en position 1 dans S", donc 5 est en position 1 dans (X) » (car 3 est en position5 dans S). donc (X) = (5 puis, « le 8 est en position 2 dans S" , donc 4 est en position 2 dans (X) »(car 8 est en position4 dans S). donc (X) = (546 ) , etc , on obtient bien de cette manière la suite S = (5 4 3 6 2 9 10 8 1 7). On donne maintenant deux formules. lere formule Comme pour la division à gauche on part de la définition de l'opération ordinale. La division ordinale revient à résoudre l'équation suivante: (X) 0 S' = S". Avec: p fonction ordinale associée à (X) p' fonction ordinale associée à S' p" fonction ordinale associée à S" On calcule S" à partir de sa fonction ordinale associée p" qui est définie par : p"(i) = p'(p(i)) , ( définition de l'opération ordinale par composition de fonctions). On cherche donc p' qui est inconnue: on a: p'(p(i)) = p"(i) , par définition. mais p"(i) = Yi, Donc : p'(p(i)) = et donc : P(i) Ou bien directement en fonction de i comme pour la division à droite: Deuxième formule: On exprime p' en fonction de i. p'(p(i)) = p"(i) ( définition de l'opération ordinale ). d'où l'on tire : P(i) = re-1(P"(»). Unicité de S' , solution de (X) , dans l'équation S 0 (X) = S". Soient S et S" deux suites ordinales de P[n]. S = ( Zi, 4, Z.) S" = (Yi, Yi, Y.) leurs fonctions ordinales associées sont notées pz et py et sont donc définies par : pour tout i de {1,2, n} , pz(i) = Zi pour tout i de {1,2, n} , py(i) = Yi Dès lors la suite ordinale (X) telle que S 0 (X) = S" aura pour fonction ordinale associée la fonction p. définie par : pour tout i de {1,2, n} , px(i) = py(p.-1(i)) , (par définition de la division à gauche , donnée par la formule ci-dessus). Soit maintenant une suite ordinale (W) telle que S 0 (W) = S". Alors la fonction ordinale pw(i) associée à (W) aura aussi pour définition: p..(i) = py(p.-1(i)) , qui est identique à px(i). Il n'existe donc qu'une seule suite ordinale S' solution de l'équation S 0 (X) = S". La démonstration est analogue pour les cas de la division à droite (X) 0 S = S". C-TOUTE SUITE DIVISE TOUTE SUITE. On va maintenant énoncer une propriété de la division ordinale utile en cryptographie. Une propriété de la division ordinale est en effet que toute suite divise toute suite. Soit P[n] un groupe ordinal. On rappelle que P[n] est l'ensemble des permutations des n premiers entiers naturels, c'est à dire l'ensemble des permutations de {1,2, n} Dès lors on énonce que tout suite ordinale (permutation) de P[n] divise toute suite de P[n] en ce sens qu'une suite S" quelconque de P[n] étant donnée, celle-ci est divisible par toute suite de Pin]: Démonstration: La démonstration est simple et quasi immédiate Soit S" une suite ordinale quelconque de P[n] Sa fonction ordinale associée p" existe donc nécessairement par définition et est bijective. Soit maintenant S une autre suite ordinale prise au hasard dans P[n]. Sa fonction ordinale associée p existe donc aussi nécessairement et est bijective. Il en est de même par définition de sa fonction inverse p-1. Dès lors la fonction p' définie par p'(i) = p"(p-1(i)) existe aussi nécessairement et est bijective puisqu'elle est la composée des fonctions p" et p-1 qui sont elles-mêmes bijective. On en conclut que S divise à gauche S" et que le résultat de cette division est la suite S' puisque la formule ci-dessus est la formule qui donne le résultat d'une division à gauche. Le raisonnement est le même pour le cas de la division à droite. Il résulte de cette propriété qu'une suite S" de P[n] étant donnée celle-ci peut être divisée par tous les éléments de P[n] à gauche ou à droite. Par ailleurs le nombre d'éléments de P[n] étant égal à n! (nombre de permutations de {1,2, n}) il existe n! opérations ordinales de la forme (X) 0 (Y) donnant S". Exemple: Soit le Groupe Ordinal P[3]. P[3] = { (1 2 3) , (1 3 2) , (2 1 3) , (2 3 1) , (3 1 2) , (3 2 1) }. 10 C'est l'ensemble des permutations de {1,2,3}. Soit S" = (2 3 1) une suite ordinale de P[3]. On constate que toutes les suites de P[3] divisent S" à droite ( par exemple). En effet: 15 (X) 0 (1 2 3) = = = = = = (2 (2 (2 (2 (2 (2 3 1) donne (X) = (2 3 1) donne (X) = (3 3 1) donne (X) = (1 3 1) donne (X) = (1 3 1) donne (X) = (3 3 1) donne (X) = (2 3 1) (X) 0 (1 3 2) 2 1) (X) 0 (2 1 3) 3 2) 23) 1 2) 13) (X) 0 (2 3 1) (X) 0 (3 1 2) (X) 0 (3 2 1) 20 On a bien 3! = 6 opérations ordinales donnant S = (2 3 1). Toutes les suites de P[3] divisent donc bien S. Par ailleurs on constate aussi que les solutions des 6 équations ci-dessus sont toutes différentes. On montre ci-après que les solutions d'une division ordinale sont toujours toutes différentes. On commence par la division à gauche. 25 En effet , pour une suite ordinale S" donnée prenons deux divisions à gauche quelconques différentes de cette suite S" , c'est à dire : S O (X) = S" Q 0 (Y) = S" avec S 4 Q. Dès lors , si: p est la fonction ordinale bijective associée à S q est la fonction ordinale bijective associée à Q p" est la fonction ordinale bijective associée à S" on a: p"(p-1(i)) pour fonction ordinale de (X) et p"(q-1(i)) pour fonction ordinale de (Y). Cela résulte de la formule de division ordinale à gauche. Dès lors peut on avoir p"(p-1(i)) - p"(q-1(i)) pour tout i , c'est à dire (X) = (Y) ? On a S Q et donc p q . Mais si p q alors on a aussi p-1 q-1. Mais si jzo-1 q-1 alors il existe un i tel que p-1(i) q-1(i). Et donc il existe un i tel que p"(p-1(i)) p"(q-1(i)) . En effet , puisque p" est bijective , si p-1(i) q-1(i) alors p"(p-1(i)) p"(q-1(i)). Donc (X) (Y) Dans le cas d'une division ordinale à droite les formules donnant (X) et (Y) sont : P-1(P"(i)) ci- 1 (p"(i)) Peut on dès lors avoir (X) - (Y) c'est à dire p' (p"(i)) = q-1(p"(i)) pour tout i ? On a 13-1 q-1 puisque S Q. Donc il existe une valeur x pour p"(i) telle que p-1(x) q-1(x). Et donc il existe un i tel que p-1(p"(i) q-1(p"(i)). Donc (X) (Y) Il en résulte que la division d'une suite quelconque S" de P[n] par chacune des suites appartenant à P[n] donne une solution différente pour chaque division (à droite comme à gauche). L'ensemble des solutions de toutes les divisions possibles , à droite comme à gauche , de (2 3 1) dans P[3] , par exemple , est donc égal à P[3] lui-même puisque toute solution (X) des équations appartient par définition à P[3] , que ces solutions sont toutes différentes les unes des autres et que leur nombre est le même que le cardinal de P[3]. Ainsi l'ensemble des solutions de toutes les divisions possibles pour une suite S" donnée d'un groupe ordinal P[n] donné est égal à l'ensemble P[n] lui-même. Dans cette partie on décrit un type de calcul utilisant l'opération 0 mais où les permutations ne sont plus des permutations de n premiers entiers naturels mais des permutations d'objets quelconques. Ceci aussi bien pour la suite permutante que pour les suites permutées. Malgré cela on conserve le nom « d'opération ordinale » car l'opération 0 reste ici une opération de permutation d'une suite d'objets par une autre suite d'objets. Pour la distinguer de l'opération ordinale proprement dite on l'appellera toutefois « Opération ordinale non numérique » car les objets des permutations ne sont pas des nombres. On ne la décrit ici aussi que dans le cas où elle est binaire. 15 A)- OPERATION ORDINALE NON NUMERIQUE Les suites sont prises sur un ensemble E d'objets quelconques et leurs fonctions ordinales sont des fonctions bijectives de E dans E. La seule condition requise est que les objets de E soient tous différents les uns des autres comme pour les suites de P[n]. 20 Par exemple E = {a,b,c,d,e} S=(cead b) , p sa fonction ordinale associée. S' = (b d a e c) , p' sa fonction ordinale associée On peut par exemple définir p et p' de la manière suivante : p(a) = c 25 p(b) - e p(c) = a p(d) = d p(e) = b p'(a) = b 30 p'(b) = d p'(c) = a p'(d) -- e p'(e) - c Au lieu de (1 2 3 4 5) on prend donc comme suite d'arguments de p et p' la suite ordonnée (a b c d e) , c'est à dire ces cinq lettres dans leur ordre alphabétique standard. Cette suite joue le rôle de numéros d'ordre comme (1 2 3 4 5 ) sont des numéros d'ordre pour les suite de P[5]. Elle définit donc un ordre sur E. On calcule alors l'opération ordinale non numérique appliquée à S et S' en calculant le résultat de SOS'=(ceadb)0(bdaec) par la formule de composition de fonction p'(p(i), où i n'est plus pris parmi les entiers représentant les indices des éléments de S 0 S' , c'est à dire parmi (1 2 3 4 5), mais parmi la suite ordonnée (a b c d e) qui constitue la suite des arguments des fonctions p et p'. Ainsi on calcule : p'(p(a)) = p'(c) = a p'(p(b)) = p'(e) = c p'(p(c)) = p'(a) = b p'(p(d)) = p'(d) = e eP(e)) = P'(b) = d 15 Et donc : S 0 S' = (ceadb)0(bdaec)=(acbed) qui est une permutation de S'. L'ensemble E peut par ailleurs cependant ne pas avoir d'ordre standard. L'ordre des arguments des fonctions p et p' est alors arbitraire. Soit par exemple E = {+ , § , k , - , « , 3 } 20 P[E] l'ensemble des permutations des objets composant E. Soit S et S' deux suites de P[E] , p et p' leurs fonctions ordinales respectives. On définit p et p' par : p(k) = 3 P(3) = « 25 P(« ) = + p(+) = k P(§) = - PO = § p'(k) = + 30 p'(« ) = k P'(+) = - P'(-) = « ( L'ordre de E , explicité par la suite des arguments de p et p' , est donc I I I I). Les permutations de E associées à S et S' sont : S = ( 3 « + k - §) S' = (+ § k - 3 «) On calcule donc le produit ordinal S 0 S' = (3 « + k - § ) 0 ( + § k - 3 « ) par: P'(P(k)) = p'(3) = § 131(1)(3)) = p'(« ) = k Pb(« )) = 1)'(+) = - Pb(±)) =1Y(k) 131(1)(§)) = 11'0 = « Pb(-)) = p'(§) =3 Donc S 0 S' = (3 « + k - §) 0 (+ § k - 3 «)= (§ k - + « 3) Si l'on veut utiliser l'opération 0 à la place de la composition de fonctions (méthode « intuitive visuelle ») il est nécessaire de poser l'ordre de E (préalablement défini) au-dessus de la suite 15 permutée : I (3 « + k - § ) ( + § k - 3 «)= (§ k - + « 3) S' S" La suite ) jouant le rôle des numéros d'ordre : le premier élément de S" étant celui « en- 20 dessous » de 3 dans S' car 3 est le premier élément de S , le second élément de S" étant celui « en dessous de « dans S' car « est le second élément de S , etc. B)- CONSTRUCTION DES GROUPES ORDINAUX COMMUTATIFS NON NUMERIQUES On donne simplement un exemple d'un tel GOC non numérique 25 Les Groupes Ordinaux Commutatifs non numériques sont générés à partir de permutations non numériques. Ils sont calculés comme tout GOC par itération de l'opération 0 , ou en termes de composition de fonction par le calcul des puissances successives de la fonction ordinale p associée à la suite génératrice S pour tous les éléments de E pris dans leur ordre. Exemple: Soit E = {+, § , k, « , 3 } muni de l'ordre suivant : ( k 3 « + § ) Soit par exemple S = ( 3 k + § « ) une suite de P[E] et p sa fonction ordinale définie par : p(k) = 3 5 p(3) = k 11(« ) = + 11(+) = § p(§) = « les cycles de S sont donc , sous forme fléchée: 10 k -->3--> k , de longueur 2 « -> + -> § --> « , de longueur 3 Sous forme de Cycles Fonctionnels Exponentiels Ordinaux : p°(k) = k p 1 (k) = 3 15 p2(k) = k p°(« ) = « 1) 1(« ) = + p2(« ) = § p3(« ) ---- « 20 Le ppcm des entiers représentant la longueur des cycles est 6. Le Groupe Ordinal sera donc de longueur 6 , c'est à dire qu'il comportera 6 permutations. On génère ce GOC en calculant le tableau suivant en utilisant la méthode par composition de fonctions: ( 1)(k) P2(k) 1)(3) 1)(« ) ) ) ) ) ) P(+) 1)2(+) 1)3(+) P4(+) P5(+) 1)6(+) 1)(§ ) ) 47 ( P3(k) 1)2(3) 132(« 132(§ ) ) = S ( P4(k) P5(k) P3(3) 1)3(« 1)3(§ ) ) = S2 ( P6(k) 134(3) P5(3) P4(« P4(§ ) ) = S3 ( 1)6(3) 115(« ) ) = 54 ( 1)6(« 1)6(§ ) ) = 55 = S6 3ème colonne : p(« ) = 4ème colonne: P(+) = § p2(« ) = p(±) = § P2(+) =13(§) = « p3(« ) = p(§) = « 133(+) =1)(« ) = p4(« ) = p(« ) = =1)(+) = § p5(« ) = p(±) = § 1)5(+) = P(§) =« 1)6(« ) = P(§) « P6(±) = P(« ) = Le calcul de ce GOC est donné ci-après : Détail du Calcul: lère colonne: 10 p(k) = 3 p2(k) = p(3) = k p3(k) = p(k) = 3 p4(k) = p(3) = k p5(k) = p(k) = 3 15 p6(k) = p(3) = k 20 2nde colonne : Sème colonne : p(3) = k P(§ ) =« P2(3) =1)(k) = 3 P3(3) =1)(3) = k p4(3) = p(k) = 3 1)2(§ ) =1)(« ) = 135(3) =1)(3) = k P6(3) = P(k) = 3 P3(§ ) = P(+) § 114(§ ) = P(§) « ) = P(« ) = P6(§ ) = P(±) = § On obtient donc le GOC suivant: ( 3 ( k k § «) =s ( 3 ( k ( 3 ( k 3 § « +) =s2 k 3 k 3 « §) =s3 + § « ) =S4 § Si qui a été décrit qui a été décrit dans la demande de de brevet n°12/02902 déposée le 30/10/2012.Ceci pour le motif que les procédés ci-20 après exposés s'y réfèreront ou l'utiliseront. Soit S une suite ordinale de P[n]. Soit p la fonction ordinale de {1,2 n) dans {1,2, n) associée à S et CI, Ck, Cr les cycles fonctionnels de S sous forme exponentielle. On obtient dès lors Si dans le GOC généré par S, pour un j quelconque , en calculant pi(i) 25 pour tout i appartenant à {1,2, n) de la manière suivante: On cherche le cycle Ck dans lequel figure i. Cela nous donne le rang y de i dans Ck (c'est à dire l'entier y tel que pY(k) = j, qui est donné par le cycle fonctionnel exponentiel Ck k étant le premier élément du cycle Ck). On calcule ensuite le reste r de (j + y)/Lk , Lk étant la longueur du cycle Ck. On obtient alors : pi(i) = P1(k) , avec r = (j + y)mod Lk . SECTION III EXPOSE TECHNIQUE DE L'INVENTION Dans le détail l'exposé qui va suivre va décrire les trois procédés suivants : 1- Exposé technique n°1 : «Méthode de calcul rapide d'une clé de chiffrement dans un Groupe 5 Ordinal Commutatif ( algorithme {Sa} 4Â) ». 2-Exposé technique n° 2 : «Système d'identification ». 3-Exposé technique n°3 : « Procédé Ordinal d'Echange de Clé (POEC) ». EXPOSE TECHNIQUE N°1 Présentation: Soit S une suite ordinale de P[n]. L'algorithme {Sa} ->Si ) exposée dans la demande de brevet déposée le 30/10/2012 (n° 5 d'enregistrement 12/02902) permet de calculer rapidement, pour un entier j que l'on se donne, la suite Si appartenant au GOC {Sa} généré par S. On obtient ainsi rapidement par cette méthode la suite de rang j , c'est à dire Si. Cette suite étant d'un point de vue cryptographique une clé de chiffrement). L'algorithme {Sa}->A (ou plus simplement algorithme A) qui va être décrit ci-après permet de 10 calculer une suite quelconque (une suite « lambda » ) de {Sa}, en ce sens que son rang dans {Sa) n'est pas connu et n'a pas besoin de l'être. C'est à dire qu'on obtient par cette méthode une suite Sx appartenant à {Sa} , c'est à dire une clé de chiffrement , sans que son rang x soit connu. Remarque :L'algorithme {Sa} 4À ne va être décrit que pour les cas où les entiers représentant la 15 longueur des cycles fonctionnels de S sont premiers entre eux. On commence maintenant par donner un exemple d'utilisation de l'algorithme À pour ensuite en donner la définition générale. Exemple: 000000000e 20 Soit par exemple S = ( 6 10 72 4 9 5 3 1 8) une suite ordinale de P[10]. Ses cycles fonctionnels sont: Ci = 1464941 , de longueur L1= 3. C2=2410484347454442 de longueur L2= 7. Sous forme fonctionnelle exponentielle: 25 C1 : p(1) = 6 , p2(1)= 9 , p3(1)= 1. C2: p(2) = 10, p2(2) = 8, p3(2) = 3 , p4(2) = 7, p5(2) = 5, p6(2) = 4, p7(2) = 2. Le cardinal a de {Sa} est égal au ppcm des entiers représentant la longueur des cycles composant S. Donc a = 3 x 7 = 21. On reproduit ci-dessous le GOC {Sa} = {S21} généré par S qui sera utile pour la suite de l'exposé. Les 21 suites composant le GOC généré par S sont donc les suivantes: (Les cycles sont en grisé colonnes 0 et 0) 00 0 0 0 0 0 0 0 0 S = ( 6 10 7 2 4 9 5 3 1 8) S2= ( 9 8 5 102 1 4 7 6 3) S3= ( 1 3 4 8 10 6 2 5 9 7) S4= ( 6 7 2 3 8 9 10 4 1 5) S5= ( 9 5 10 7 3 1 8 2 6 4) S6= ( 1 4 8 5 7 6 3 10 9 2) S7= ( 6 2 3 4 5 9 7 8 1 10) S8= ( 9 10 7 2 4 1 5 3 6 8) S9= (1 8 5 10 2 6 4 7 9 3) S10= (6 3 4 8 109 2 5 1 7) S1' = (9 7 2 3 8 1 10 4 6 5 ) S12 = (1 5 10 7 3 6 8 2 9 4 ) S13 = (6 4 8 5 7 9 3 10 1 2 ) S14 = (9 2 3 4 5 1 7 8 6 10 ) S15 = (1 10 7 2 4 6 5 3 9 8 ) S16 = (6 8 5 10 2 9 4 7 1 3 ) S17 = (9 3 4 8 10 1 2 5 6 7 ) S18 = (1 7 2 3 8 6 10 4 9 5 ) S19= (6 5 10 7 3 9 8 2 1 4) S20= (9 4 8 5 7 1 3 10 6 2) S21 -= (1 2 3 4 5 6 7 8 9 10 ) On appelle comme à l'accoutumé p la fonction ordinale associée à S. Maintenant, pour construire et obtenir une suite Sx quelconque de {S21} sans que celui-ci soit construit on doit chercher successivement les valeurs de la fonction ordinale px associée à Sx pour chacun de ses arguments i de {1,2, n}. Comment procéder ? px est la fonction ordinale associée à Sx. Soit i = 1. On cherche donc px(1). N'importe quelle valeur du cycle auquel appartient 1 peut être prise. Toutes les suites de {Sa} ont en effet en première position un élément du cycle C1 , c'est à dire 1 , 6 ou 9. On prend donc au hasard un de ces éléments. Par exemple 9. On pose donc el) = 9. Cherchons maintenant px(2). Pour i = 2 on peut aussi prendre au hasard un élément du cycle C2 auquel appartient 2 puisque toutes les suites de {S21} ont en deuxième position l'un des éléments de C2 compte tenu que les entiers représentant la longueur des cycles de S sont premiers entre eux et que tous les w-uplets (ici les couples) sont donc présents dans chaque suite du GOC de S. On prend donc par exemple px(2) =4. Pour tous les autres arguments possibles de px , c'est à dire pour 3 , 4, 5 , 6 , 7, 8 , 9, 10 , le choix de la valeur de la fonction px ne peut être fait au hasard. Leur valeur en effet est déterminée par les valeurs précédentes de px prises pour i = 1 et pour i = 2. Si px(1) = 9 et px(2) = 4 en effet la suite Sx commence par (9 4). Or il n'existe qu'une seule suite dans {Sa} qui commence par (9 4 ) (voir propriété 4 des GOC , partie II de l'annexe 20 mathématique : chaque w-uplet dans un GOC est unique) . Dans le GOC {Sa} généré par S reproduit ci-dessus on constate ainsi que la suite commençant par (9 4) est S2° =(- 8 5 7 1 3 10 6 2 ). Comment sont déterminées les valeurs ( 8 5 7 1 3 10 6 2) ? On sait que si px(1) = 9 cela signifie que x = OLLI + 2 avec L1 longueur du cycle C1 auquel 25 appartient 1. Cela résulte du fait que 9 = p2(1). (voir cycle Ci). Donc puisque LI = 3 on a x = 01.3 +2. Le 9 revient donc en première position selon un cycle de longueur 3 dans toute suite Sx où x = oc.3 + 2 (par exemple la première suite dans laquelle 9 est en première position est S2 , puisque 9 = p2(1) selon cycle Ci , c'est à dire qu'ici oz = 0 , puis 9 revient ensuite en position 1 dans S5 , S8 , etc. ). Et donc el) = 9 pour tout x tel que reste(xJ3) = 2. On en déduit donc que si i appartient à C1 , la valeur y de px(i) , c'est à dire l'élément figurant dans Sx en i-ème position , doit obligatoirement être égale à p2(i) pour que cela soit compatible avec le fait que px(1) = 9. Par exemple , soit i = 6. 6 appartient à Ci , de longueur 3 On cherche la valeur de px(6). Comme reste(x/3) = 2 du fait qu'on a posé p'(1) = 9 , on a forcément px(6) = (Et au cas particulier px(6) = p2(6) = p2(p1(1)) d'après cycle Ci et algorithme {Sa} ,Si . Donc p2(6) = p3(1) = 1 , ce qui correspond bien à S2° =( 9 4 8 5 7 1 3 10 6 2) où le 1 est bien en 6-ième 15 position). De même si i appartient à C2 puisqu'on a choisi px(2) = 4 cela signifie que x = OE.L2 + 6 avec L2 longueur du cycle C2 auquel appartient 2. Car 4 = p6(2). (cf cycle C2). Donc puisque L2 = 7 on a x = 0(.7 + 6 et reste(x/7) = 6. 20 Le 4 revient donc en seconde position dans les suites du GOC généré par S selon un cycle de longueur 7 et dans toute suite Sx où x = oc.7 + 6. La première suite dans laquelle 4 est en seconde position étant S6 (puisque 4 = p6(2) , voir GOC {S21} reproduit ci-dessus). Et px(2) = 4 pour tout x tel que reste(x17) = 6. Donc si i appartient à C2 la valeur y de px(i) est obligatoirement égale à p6(i).Cette valeur est la 25 seule compatible avec px(2) = 4. En définitive donc , on doit choisir pour chaque argument i autre que 1 et 2 la valeur y pour px(i) de la manière suivante: est égal à: p2(i) si i appartient à Ci. p6(i) si i appartient à C2. On calcule donc ainsi: px(1) = 9 (pris au hasard) px(2) = 4 (pris au hasard puis à l'aide de {Sa} 4Si pour le calcul de chaque autre identité : Px(3)= P6(3) = P6(P3(2)) = P9(2) = P2(2) - détailler les calculs: 8 , car 3 appartient à C2 et reste(9/7) = 2 ; de même sans px(4) = p6(4) = 5 pX (5) = p 6(5) = 7 px(6) = p2(6) =1 pX (7) = p6(7) = 3 px(8) = p6(8) = 10 15 pX (9) = p2 (9) = 6 px(10) = p6(1 0) = 2 On obtient ainsi la suite ( 9 4 8 5 7 1 3 10 6 2) qui est la suite S2° (donc x est ici égal à 20 mais il n'a pas vocation à être connu dans le cadre de la méthode À). Les valeurs p2(i) et p6(i) pour chaque i peuvent par ailleurs être lues dans les cycles fléchés de S: 20 1464941 2410484347454442 la valeur v de p2(i) par exemple, est celle qui figure deux flèches après i : i4j4v. On prend garde évidemment à ne pas compter deux fois le 1 qui figure au début et à la fin du cycle. p2(9) par exemple est 6 et non 1 car le cycle est 94146. 25 On peut aussi obtenir les valeurs p2(i) et p6(i) en déterminant leur valeur en fonction des puissances de la fonction p pour les arguments 1 et 2 qui sont les éléments de base des cycles fonctionnels (c'est à dire par algorithme {Sa} 4Si ). Cas général: On décrit maintenant l'algorithme de calcul {Sa } 4À pour le cas général. 30 Soit S une suite ordinale de P[n]. Ci Ck, Cm , les cycles fonctionnels de S. Les entiers représentant la longueur de ces cycles sont premiers entre eux. {Ci} , {Ck} , {C.} les ensembles des éléments composant chaque cycle fonctionnel de S. p est la fonction ordinale associée à S. On construit une suite quelconque X de {Sa} de la manière suivante: On note lu la fonction ordinale de la suite X. On choisit au hasard un élément de chaque cycle. On exprime cet élément en fonction du premier élément de chaque cycle d'après la fonction p. Par exemple si z est l'élément choisi et i le premier élément de Ci , cycle auquel appartient z, on 10 calcule l'exposant n pour lequel on a z = pn(i) et on pose évidemment par définition que z est en i- ème position dans la suite X , c'est à dire px(i) = z En notant w le nombre de cycles de S on obtient ainsi w éléments de X qui sont situés en i-ème , k- ième , , m-ième position dans X puisque i, k , sont les premiers éléments des cycles Ci , Ck ...,Cm 15 Un w-uplet appartenant au produit cartésien des ensembles {Ci }, {Ck},... {C.} est donc ainsi choisi aléatoirement. On complète ensuite X en comblant les « positions vacantes » à l'aide de l'exposant n obtenu et déterminé comme mentionné ci-dessus par le choix de chaque z dans chaque cycle de la manière suivante: 20 Soient Z , zk , z. , les éléments choisis aléatoirement dans chaque cycle C. ,C k,....C. de S , c'est à dire les éléments composant le w-uplet ( z est en position i dans X , zk en position k , zm en position m). On note: n l'exposant de l'élément zi , c'est à dire le nombre ni tel que zi = p(i) 25 ni l'exposant de l'élément zk , c'est à dire le nombre nk tel que zk pnk(k) ri. l'exposant de l'élément z. , c'est à dire le nombre nm tel que z. = pn.(m) On pose alors pour chaque j différent de {i , k ,...,m} , ( c'est à dire pour chaque place vacante de la suite À) que : px(j) = p" (j) si j appartient au cycle Ci px(j)= pnk(j) si j appartient au cycle Ck - px(j)= en(j) si j appartient au cycle C. Cette définition de l'algorithme de calcul {Sa}->X peut paraître complexe mais celui-ci est dans la 10 pratique assez simple. On peut le constater sur un exemple : Soit S = ( 14 6 15 10 2 9 19 7 11 17 13 4 16 8 3 5 1 12 20 18 ) une suite ordinale de P[20] . Les cycles fonctionnels de S sous forme fléchée sont: Ci = ->20-->18->12-4-->10->17-->1 , de longueur LI = 11 15 C2= 2->6-+9-+11--->13->16->5->2 , de longueur L2 = 7 C3 = 3->15-->3, de longueur L3 =2. ppcm {2,7,11} = 154 et donc a = 154. On calcule une suite À de {S154} avec la méthode décrite ci-dessus: On choisit aléatoirement un élément de chaque cycle , c'est à dire un triplet , par exemple 20, 13 et 20 15. Et donc: 20 = p5(1) , voir cycle C1, donc ni = 5 13 = p4(2) , voir cycle C2 donc n2 = 4 15 = p1(3) , voir cycle C3 donc n3 = 1 On écrit les trois cycles de S sous forme de CFEO: , 6, ..... , 20 (en utilisant par = C2 = C3 = p°(1) = 1 p°(2) = 2 po(3) = 3 p1(1) = 14 p1(2) = 6 p1(3) = 15 p2(1) = 8 p2(2) = 9 p2(3) = 3 p3(1) = 7 p3(2) = 11 p4(1) = 19 p4(2) = 13 p5(1) = 20 p5(2) = 16 p6(1) = 18 p6(2) = 5 p7(1)= 12 p7(2) = 2 p8(1) = 4 p9(1) = 10 p1°(1) = 17 p"(1) = 1 On peut donc alors calculer les éléments de X situés en position 4, 5 exemple {Sa} ->Si ) : px(4) ( l'élément de X situé en 4ème position dans X) : px(4) = p5(4) = 8 (car 4 appartient à Ci, donc l'exposant est n=5 , et p5(4) = p5(p8(1)) = p13(1) = p2(1) =8) de même sans détailler les calculs: 1)45) =p4(5) = 11 px(6) = p4(6) = 16 px(7) = P5(7) = 4 1)48) = p5(8) = 12 Px(9) =114(9) = 5 px(10) = p5(10) = 7 px(11)=p4(11)= 2 px(12) = p5(12) = 14 px(13) = 0(13) = 6 p(l4)=p5(l4)=l8 px(15) = pl(15) = 3 px(16)= p4(16)= 9 px(17)= p5(17) = 19 px(18) = p5(18)= 1 px(19) =p5(19)= 10 px(20) = p5(20) = 17 On obtient ainsi la suite A = ( 20 13 15 8 11 16 4 12 5 7 2 14 6 18 3 9 19 1 10 17). COMMENTAIRES Premièrement: L'algorithme {Sa}-+A ( ou algorithme A ) , ci-dessus décrit , a été définie pour le cas où les longueurs des cycles de la suite S sont premiers entre eux. Dans ce cas tous les n-uplets issus du du produit cartésien des cycles figurent dans les suites composant le GOC généré par S. Ce qui permet 10 de choisir au hasard un élément de chaque cycle pour utiliser l'algorithme de calcul générant la suite A. Si les longueurs des cycles ne sont pas premiers entre eux on doit construire l'ensemble des n-uplets possibles (par exemple si Ci = {1,4,5} de longueur 3 et C2 = {2,3,6,7,8,9} de longueur 6 , les seuls w-uplets du GOC seront : (1 2) (4 3) (5 6) (1 7) (4 8) (5 9) . Le choix ne peut alors plus être fait 15 au hasard. Deuxièmement: L'algorithme A peut évidemment être utilisée avec des Groupes Ordinaux Commutatifs non numériques (voir annexe mathématique partie IV). Soit par exemple E = {+, § , k, « , 3 } muni de l'ordre suivant : 20 Soit S = ( 3 k + § « ) une permutation de P[E] . les cycles de S sont donc, sous forme fléchée: k -*3-> k , de longueur 2 « -> + -> § --> « , de longueur 3 25 Sous forme de Cycles Fonctionnels Exponentiels Ordinaux : P°(k) = k P1(k) = 3 pz(k) = k10 p°(« ) = « p1(« ) --- ± p2(« ) = § p3(« ) = « En choisissant comme w-uplet le couple (3 , §) on peut vérifier que l'application de l'algorithme A permet de calculer la suite ( 3 k § « +) qui est la suite S5 du GOC généré par S: 1111111111111111 ( 3 k + § «) =S ( k 3 § « +) =S2 ( 3 k « + §) =S3 ( k 3 + § «) =s4 ( 3 k § « + ) = S5 ( k 3 « + §) =s6 EXPOSE TECHNIQUE N°2 L'identification avec méthode À se passe ainsi : A et B possèdent une clé privée sous forme de suite ordinale. A veut s'identifier auprès de B . B lui communique un w-uplet qu'on appelle W et lui demande de calculer et de lui communiquer la suite A associée à W appartenant au GOC généré par S. Exemple : On reprend simplement l'exemple donné ci-dessus pour l'exposé de l'algorithme A avec la suite S de P[20] : S = ( 14 6 15 10 2 9 19 7 11 17 13 4 16 8 3 5 1 12 20 18 ). S est la clé privée partagée par A et B. A veut s'identifier auprès de B . B lui demande de calculer la suite A associée par exemple au wuplet W = (20 13 15) qui est donc ici un triplet (car S possède trois cycles ). A calcule par l'algorithme A la suite : A ( 20 13 15 8 11 16 4 12 5 7 2 14 6 18 3 9 19 1 10 17). Il la communique à B qui peut vérifier que ce résultat est correct. Autres variantes : - Ou bien pour plus de sécurité A communique simplement à B une fraction de la suite A . Par exemple A envoie à B la demi-suite ( 20 13 15 8 11 16 4 12 5 7 ) . 5 - Ou encore A et B conviennent à l'avance de nk numéros d'ordre ( Iii, n2 ...nk ) de la suite À et s'identifient en se communiquant pk(m), pk(n2)' p(n) Soit par exemples cinq numéros d'ordre convenus à l'avance : 8, 12, 19 , 4, 11 A envoie alors à B pour s'identifier : (12 14 10 8 2) 10 puisque A r(20 13 15 8 11 16 4 12 5 7 2 14 6 18 3 9 19 1 10 17). Communiquer une fraction de la suite A ou la valeur de px pour certains numéros d'ordre évite qu'un espion ait connaissance de la suite A en son entier. - Enfin il est aussi possible que soit demandé à A, qui veut s'identifier, de donner le cryptogramme d'un message ou d'une suite de symboles chiffré à l'aide de la permutation (clé) associée au w-uplet communiqué par B. Par exemple en permutant une suite de bits à l'aide de la clé associée au w-uplet (B envoie un w-uplet et une suite de bits , A doit lui retourner la permutation de la suite de bits opérée à l'aide de la clé associée au w-uplet ). EXPOSE TECHNIQUE N°3 Plan de l'exposé technique: I-Schéma général des Procédés d'échange de clé II- Procédé d'échange de clé utilisant les Groupes Ordinaux Commutatifs numériques. III - Exemple utilisant des Groupes Ordinaux non numériques IV-Variantes du procédé. fl l Un processus d'échange de clé de « Diffie-Hellman » repose sur le schéma suivant: 10 Un groupe G est choisi de la manière suivante : - G est commutatif - l'opération ± commutative sur G est non inversible ou difficilement inversible. Une opération binaire est difficilement inversible quand connaissant le produit de deux éléments de G on ne peut pas retrouver ses arguments. 15 Exemple : soit a et b deux éléments non connus de G. leur produit par 1 est P et donc P = (a 1 b). Si 1 n'est pas inversible on ne peut pas , connaissant P, retrouver les arguments a et b. Ou bien, connaissant un seul des arguments , par exemple a, et le produit P = (a 1 b) , on ne peut pas calculer b. Un processus d'échange de clé repose donc sur l'existence d'un groupe G et d'une opération 20 commutative sur G qui n'est pas ou qui est difficilement inversible. Le processus est alors le suivant Un élément g appartenant à un groupe commutatif G est donné et public. L'émetteur (l'initiateur) de l'échange , qu'on appelle A, choisit un élément a de G qu'il garde secret et calcule: 25 (g 1 a) - Pi Il envoie le produit P1 à B qu'on appelle le récepteur. L'opération 1 n'étant pas inversible , ni le récepteur , ni un éventuel espion qui aurait intercepté l'envoi et eu connaissance de Pi ne peut retrouver a. Le récepteur B choisit à son tour un élément b de G qu'il garde secret et calcule: (g 1 b) = P2. B envoie le produit P2 à A. De même que pour l'envoi de A, ni A ni un espion ne peuvent retrouver b car l'opération 1 n'est pas inversible. A ce stade donc , après les envois croisés de Pi et P2 , la situation est la suivante: A est en possession de P2 , avec P2 = (g 1 b). B est en possession de Pi, avec Pi = (g 1 a). Dès lors: A calcule (g 1 b) 1 a B calcule (g 1 a) 1 b L'opération 1 étant associative et commutative , puisque G est un groupe commutatif, les produits (g 1 b) 1 a et (g 1 a) 1 b sont égaux. Ainsi A et B sont simultanément en possession du produit P = (g 1 b) 1 a = (g 1 a) 1 b qui constitue leur clé commune échangée. On va décrire dans la suite un processus d'échange de clé reposant sur ce schéma mais utilisant les Groupes Ordinaux Commutatifs. Dans le procédé « POEC » la clé échangée est une permutation d'objets . Le schéma est analogue à celui exposé ci-dessus à la différence près que la fonction non inversible n'est pas binaire mais ternaire et que l'on utilise le calcul ordinal et les groupes ordinaux. On va décrire ici ce procédé avec des permutations de n premiers entiers naturels , c'est à dire des suites ordinales (Groupes Ordinaux numériques).Dans le paragraphe suivant un exemple sera donné utilisant un Groupe Ordinal Commutatif non numérique. A)-description: Le procédé est le suivant: g est une suite ordinale de P[n]. g est publique. L'émetteur A choisit une suite S de P[n] ne commutant pas avec g, (S et g n'appartiennent donc pas au même Groupe Ordinal Commutatif). S est communiquée à B afin que_ce dernier en ait connaissance. A choisit ensuite deux suites Sx et SY appartenant au GOC généré par S. Les suites Sx et SY sont tenues secrètes. A envoie alors ensuite à B le produit P1 suivant : Pi = Sx 0 g 0 SI'. B de son côté choisit lui aussi deux suites SW et Sr appartenant au GOC généré par S. Il envoie alors à A le produit P2 suivant : P2= SW 0 g 0 Sr. 10 Ace stade: A est en possession de P2 = SW O g O Sr. Il connaît donc P2et Sx et SY qu'il a lui-même calculé. B est en possession de Pi= Sx 0 g 0 SI'. Il connaît donc P1 et Sw et Sr qu'il a lui-même calculé. A "multiplie" alors P2 par Sx à gauche et par SY à droite pour obtenir le produit P' suivant: P' = 0 (Sw 0 g 0 Sr) 0 SY. 15 B de son côté multiplie P1 par S' à gauche et par Sr à droite pour obtenir le produit P" suivant: P" = Sw 0 (Sx 0 g 0 SY) 0 sr.. Les suites S' et S' commutant, ainsi que les suites SY et S', puisqu'elles appartiennent au même Groupe Ordinal Commutatif , les produits P' et P" sont égaux : Sx0(Sw0g0S5 OSY = SwO(Sx0g0SY)0Sr= K. 20 Ce produit K constitue donc leur clé échangée. Note : le calcul de S' et SY peut être fait avec la méthode {Sa} 4 Si en choisissant deux nombres entiers x et y pour calculer Sx et SY . Mais on peut aussi utiliser la méthode {S } -+A en choisissant deux w-uplets pour calculer deux suites quelconques À et À' appartenant au GOC généré par S. Dans tout l'exposé qui suit on se réfèrera à la méthode { Sa} 4 Si et on l'utilisera éventuellement car 25 elle est plus pratique de calcul. B-Exemple On donne ici un exemple de procédé d'échange de clé ordinale. Soit g = ( 3 9 7 10 2 5 6 4 8 1) . g appartient à P[10]. (On prend ici n = 10 , g est en effet une suite ordinale de P[10]. Dans la pratique , pour la sécurité 5 du système , n doit être évidemment un entier beaucoup plus grand. La manière de choisir g et la suite S sera vue au paragraphe « cryptanalyse »). A choisit aléatoirement une suite S = ( 6 10 7 2 4 9 5 3 1 8) qu'il communique à B . S doit évidemment être communiquée à B avec l'envoi de A (ou antérieurement à l'envoi). Cette suite S ne doit pas commuter avec g. 10 A teste la non-commutativité de g et S en calculant g 0 S et S 0 g. Ainsi: 0000000000 gOS=(3 971025648 1)0(6 1072 49 53 1 8)-(71581049236) 0000 000000 15 SOg=(610724953 18)0(3 9 710 25 64 8 1)=(5 1691082734) g et S telles qu'on les a choisies ne commutent pas , les suites g et S peuvent donc être les suivantes: g= (3 97 10 2 5648 1) S= (6 10 72 49 53 18) A choisit dès lors aléatoirement deux suites secrètes appartenant au GOC généré par S en 20 choisissant deux entiers , par exemple 10 et 17 , et en calculant S1° et S17 par la méthode {Sa}->Si ( Ici cependant , n étant petit on peut utiliser le Groupe Ordinal Commutatif généré par S en le calculant en totalité tel que ci-après de la manière « intuitive visuelle » avec l'opération 0): 0 0 0 0 0 0 0 0 0 S = ( 6 10 7 2 4 9 5 3 1 8) S2= (9 8 5 10 2 1 4 7 6 3) S3= ( 1 3 4 8 10 6 2 5 9 7) S4= (6 7 2 3 8 9 10 4 1 5) S5= (9 5 10 7 3 1 8 2 6 4) S6= ( 1 4 8 5 7 6 3 10 9 2) 25 30 65 S7= (6 2 3 4 5 9 7 8 1 10) S8= (9 10 7 2 4 1 5 3 6 8) S8= ( 1 8 5 10 2 6 4 7 9 3) S10=(6 3 4 810 9 2 5 1 7) Sil= (9 7 2 3 8 110 4 6 5) S12= (1 5 10 7 3 6 8 2 9 4) S13=(6 4 8 5 7 9 3 10 1 2) S14=(9 2 3 4 5 1 7 8 6 10) S15=(1 10 7 2 4 6 5 3 9 8) S16=(6 8 510 2 9 4 7 1 3) S17= (9 3 4 8 10 1 2 5 6 7) S18=(1 7 2 3 8 610 4 9 5) S19=(6 5 10 7 3 9 8 2 1 4) S20=(9 4 8 5 7 1 3 10 6 2) S21=(1 2 3 4 5 6 7 8 9 10) A obtient donc SI° et SI 7 : S10=(63481092517) SI7-(93481012567) Si l'on avait utilisé la méthode {Sa} ->Si , par exemple pour SI° , on aurait utilisé les Cycles 20 Fonctionnels Exponentiels Ordinaux (CFEO) de S : C1= p°(1) = 1 pl(1)= 6 p2(1) = 9 25 p3(1)= 1 c2= p°(2) = 2 p1(2) = 10 p2(2) = 8 30 p3(2) = 3 p4(2) = 7 p5(2) =5 p6(2) =4 p7(2) =2 pour calculer : p10(1) = pl°(p°(1)) = pl°(1) = pl(1) =6, car reste (10+0)/3=1, p'°(2) = pl °(p°(2)) = p'°(2) = p3(2) =3, car reste (10+0)/7=3 , 1) 1 °(3) = P I °(P3(2)) = P13(2) - P6(2) = 4, car reste (10+3)/7=6, etc... p l 0(4) = p 1 0(p6(2)) -_ p16(2) = p2(2) = 8 p10(5) - pi o(ps(2)) = pisf2) = -1 p (2) =10 p10(6) = pl°(pl(1)) = p11(1) = p2(1) =9 p l 0(7) = p 1 0(pel(Z" = - 14 )) p (2) = p°(2) =2 P 1 °(8) = PI °(1)2(2)) -1312(2) ' P5(2) =5 P10(9) =P1°(P2(1)) = P12(1) = P°(1) =1 p 1 °(10) = p1 o(p i (2)) = p i i (2) = p4(2) = 7 Et l'on aurait bien trouvé après calcul la suite SI°. A a donc choisi ou calculé : SI° = (63481092517) S" =(93481012567) Par ailleurs g = (39710256481) A envoie donc à B (avec la suite S ) : Sl° 0 g 0 Sl7 qui est égal à: (63481092517)0(39710256481)0(93481012567) 25 A calcule ce produit en calculant tout d'abord : 510 0 g: 0000 000000 (63481092517)0(39710256481)=(57104189236) 00000 00000 puis:(57104189236)0( 93481012567)-(10278956341) qui est égal à Sl° 0 g 0 S17 du fait de l'associativité de l'opération O. (Remarque sur le plan du calcul : si le calcul est fait par composition de fonction avec la méthode {Sa} 4Si à partir des fonctions ordinales associées à g , Sl° et S17 et de leur CFEO , A calcule directement (S'° 0 g 0 S17) sans passer par le calcul intermédiaire de 510 et S17 par la fonction 5 P17(Pg( 113(i))) ,OÙ p17, g,et pl° sont les fonctions ordinales respectivement de S17 , g et S10). A envoie donc à B la permutation ( 10 2 78 95 6 3 4 1) qui peut être qualifiée de clé partielle communiquée à B. On l'appelle K.. Réciproquement B choisit aussi de son côté deux nombres entiers qu'il garde secret , par exemple 5 et 9 et calcule S5 et 59. 10 Il obtient (voir GOC calculé ci-dessus) : S5= (95107318264) S9=(18510264793) Il calcule ensuite S50 g 0 59: Tout d'abord S50 g: 15 0000 000000 (95107318264)0(39710256481) =(82167349510) Puis S50 g 0 S9: 0000000000 (82167349510)0(18510264793)=(78164510923) 20 qui est la clé partielle de B que ce dernier communique à A et qui peut être appelée Kb . Dès lors A calcule: Sl° 0 Kb 0 S17, qui est égal à : Sl00 (78164510923) 0 517 et B calcule : 25 S50 Ka 0 S9, qui est égal à : S50(10278956341)0S9. Ils obtiennent chacun: pour A: 0000000 000 S100Kb =(63481092517)0(78164510923)-(51693284710) 0000000000 etS100KbOS" = (51693284710)0 (93481012567)= pour B: 0000000000 S501C=(95107318264)0(10278956341)=(49167103258) 00.0000000 S501(.0S9=(49167103258)0(18510264793)= A et B obtiennent donc tous les deux la permutation nalligià qui est la clé K échangée. Note sur la sécurité du système: On montre ici simplement pourquoi g ne doit pas commuter avec S (on fera aussi une remarque sur le choix de S). Le produit (Sx 0 g 0 SY) n'est pas inversible de par la propriété des Groupes Ordinaux que toute suite divise toute suite (voir annexe mathématique ,partie III). Si on reprend en effet l'exemple ci-dessus un analyste qui aurait connaissance de la clé partielle envoyée par A aurait à résoudre l'équation suivante: Sx 0 g 0 SY = (10278956341) = P (Dans l'exemple on a Sx = S1° et SY = S17 qui sont les deux suites que l'analyste doit retrouver). Quel que soit le choix de l'analyste pour SY (par exemple) , il obtient toujours une suite Sx qui 25 vérifie cette équation. S'il prend par exemple y = 3 on a S3 = (1 3 4 8 10 6 2 5 9 7) , voir GOC ci-dessus. Comme g = (3 9 7 10 2 5 6 4 8 1) , il calcule (3 9 Il obtient (4 9 2 7 3 10 6 8 5 1). 7 10 2 5 0000000000 Puis il divise ensuite à droite le produit P = ( 10 2 7 8 9 5 6 4 8 1) 0 (1 3 4 8 10 6 2 5 9 7). 6 3 4 1) par (4 9 2 7 3 10 6 8 5 1) : (X)0(49273106851)=(10278956341) Il obtient (X) = (6 3 4 8 2 9 7 5 110) Et il obtient donc deux suites (X) et (Y) qui vérifient (X) 0 g 0 (Y) = P , mais qui ne sont pas égales à S'° et S17 . Il en aurait été de même pour tout autre choix de SY .Cela résulte du fait que 10 « toute suite ordinale divise toute suite ordinale ». Il ne semble pas par ailleurs qu'il existe d'autre méthode d'analyse que de tester une par une les suites appartenant au GOC généré par S. (On note que dans notre exemple la suite (X) obtenue qui est (6 3 4 8 2 9 7 5 110) n'appartient pas au GOC généré par S ce qui permet à l'espion de l'exclure comme possibilité ; mais même si la suite 15 (X) appartient au GOC généré par S cela ne permet pas de conclure qu'il a trouvé les deux suites Sx et SY car il n'est pas établi qu'il n'existe à l'intérieur du GOC généré par S qu'un seul couple de solutions). En tout état de cause pour que le calcul de (Sx 0 g 0 SY) ne soit pas inversible ou difficilement inversible, c'est à dire pour que l'on ne puisse pas retrouver Sx et SY à partir du 20 produit Sx 0 g 0 SY , il est nécessaire g ne commute ni avec Sx ni avec SY ni avec St" ni avec Sr. En effet , si g commute avec Sx par exemple , alors g commute aussi avec SY car si g et Sx commutent elles appartiennent au même GOC. Mais SY appartient aussi au même GOC que 5'. Donc g, Sx et SY appartiennent au même GOC et commutent donc toutes les trois. 25 D'où il suit que g, Sx , SY , Sv' et Sr appartiennent toutes au même GOC et commutent entre elles. Dès lors : Sx 0 g 0 SY = Sx 0 SY 0g et e0g0Sr=e0SrOg Et l'espion peut alors retrouver Sx O SY en divisant à droite par g la clé partielle envoyée par A qui est égale à (Sx O SY 0 g) , puis aussi retrouver Sw 0 Sr en divisant à droite par g la clé partielle envoyée par B qui est égale à (S'y 0 Sr 0 g). Ensuite il peut reconstituer la clé K, car il connait alors (Sx O SY) et ( Sv 0 Sr) : En effet K = Sx O Sw 0 g 0 Sr 0 SY = Sx O SY 0 g 0 Sw 0 , compte tenu que les cinq suites commutent. Il lui suffit alors de former le produit (Sx 0 SY) 0 g 0 (Sw 0 Sr) pour reconstituer la clé K. Il est donc nécessaire pour la sécurité du processus d'échange de clé ordinale ici décrit que g ne commute ni avec Sx ni avec SY ni avec S'Y ni avec Sr. Or cela est réalisé si la suite S à partir de laquelle sont calculées les clés privées Sx , SY , Sw ,Sr ne commute pas avec g. En effet : si deux suites S et g ne commutent pas (Hypothèse), alors pour tout w: Sw 0 g * g 0 Sw. C'est à dire que Sw et g ne commutent pas. Supposons en effet par l'absurde que S'Y et g commutent. Donc elles appartiennent au même GOC 15 (car deux suites S et S' commutent si et seulement si elles appartiennent au même GOC : voir propriété 5 des Groupes Ordinaux Commutatifs , partie II de l'annexe mathématique ). Mais S'Y commute avec S par définition puisque Sw appartient au GOC généré par S. Il s'ensuit alors que S commute avec g puisque g , S et Sw appartiennent alors au même GOC . Ce qui contredit l'hypothèse que S et g ne commutent pas. 20 Donc si S et g ne commutent pas alors il n'existe pas d'entier w et de suite Sw appartenant au GOC généré par S telle que Sw commute avec g. Pour la sécurité du système d'échange de clé ordinal il est donc nécessaire que la clé publique g ne commute pas avec S. Choix de S: 25 Un autre point à noter pour la sécurité du système est que le cardinal du GOC généré par S doit évidemment être très grand, en d'autres termes que le ppcm a des longueurs des cycles fonctionnels composant S soit très grand. La sécurité du procédé ordinal d'échange de clé repose sur cette caractéristique de la suite S choisie car celle-ci ayant vocation à être connue d'un analyste ce dernier peut effectuer des recherches 30 exhaustives sur l'ensemble des clés appartenant au GOC généré par S pour en déduire l'univers des possibles pour la clé finale K échangée. Exemple :s i l'on prend pour S des cycles de longueurs 7, 11 , 15, 17, 19 , 23 , 29 , 31 , 37 , 41 ,43 , 47, 53 , 59 , 61 , 67, 71 , 73 , 79, 83 , 89, 97, 100, 101 , la suite S est une permutation de P[1251]. C'est à dire qu'elle est une permutation des 1251 premiers entiers naturels. Le GOC {Sa} généré par une telle suite comportera donc environ 9 x 1038 permutations différentes 5 puisque : 7 x11 x13 x 17 x 19 x23 x 29 x 31 x37 x 41 x43 x 47 x 53 x 59 x 61 x 67 x 71 x 73 x 79 x 83 x 89 x 97 x 100 x 101 9 x 1038. Ces facteurs étant tous premiers entre eux puisque ce sont tous des nombres premiers à l'exception de 100 qui est cependant premier avec tous les autres facteurs. 10 III- EXEMPLE UTILISANT UN ENSEMBLE D'OBJETS "E" QUELCONQUE (GROUPES ORDINAUX NON NUMERIOUES) La technique est strictement identique à celle utilisée ci-dessus pour les suites de P[n]. On ne fait donc ici que donner un exemple d'échange de clé. Soit E = {010 , 011 , 101 , 001 , 110 , 111 , 100 , 0000} l'ensemble {0,1} 3 des triplets de bits. 15 E comporte donc huit éléments. Soit l'ordre de E défini par : ( 1111 MI A choisit et définit une suite S de manière arbitraire (ici par ses CFEO au nombre de deux): S= 0(001) = 001 p°(101) = 101 20 p1(001) = 000 p1(101) = 111 p2(001)= 100 p2(101)= 010 p3(001)= 001 p3(101) = 011 p4(101) = 110 p5(101) = 101 25 Le triplet 001 est l'élément de base (initial) du premier cycle, 101 celui du second cycle. On définit ensuite g par sa fonction ordinale, g est publique. (on note g la fonction ordinale de la suite g) : g(001) = 110 g(111) = 010 g(101) = 101 g(011) = 000 g(100) = 111 g(110) = 001 g(000) = 011 g(010) = 100 La suite g est donc g = ( 72 Ei iek EN II 1/1.0 110 010 101 000 111 001 011 100) S et g sont donc les deux clés publiques utilisées par les protagonistes A et B (du moins S est communiquée à B de manière non secrète et g est publique). Conformément au Procédé Ordinal d'Echange de Clé l'échange de clé se fait ainsi: A choisit deux entiers secrets x et y , par exemple x = 3 et y = 11 (le calcul est donc fait avec la 15 méthode {Sa} -> Si pour calculer 53 et Sll ). Puis il calcule S3 0 g 0 Sll Calcul de S3: (à l'aide des CFEO de S ci-dessus) p3(001) = 001 20 p3(111)=p3(p1(101))=p4(101)= 110 p3(101)= 011 p3(011)=p3(p3(101))=p6(101)=p1(101)= 111 p3(100)= p3(p2(001)) = p5(001) = p2(001) = 100 p3(110)=p3(p4(101))=p7(101)= p2(101)= 010 25 p3(000)= p3(p1(001)) = p4(001) = pl (001) = 000 p3(010)=p3(p2(101))=p5(101) = 101 Donc S3 = ( 001 110 011 111 100 010 000 101) Calcul de Sll pi 1(001) = p2(001) = 100 73 010 p"(111)= pl 1(1)1(101)) = pl2(101)= p2(101)= p11(101) =111(101) = 111 110 000 101 001 p1 '(011) = pl 1(p3(101)) =1)14(101) = p4(101)= p11(100)= pl 1(p2(001)) =1)13(001) = p1(001)= pl1(110)= pl l(p4(101)) = p15(101) = p°(101)= pl 1(000) = p11(p-1(001)) = p12(001) = p°(001) = pl1(010)= pl l(p2(101)) =1)13(101) =p3(101)= 011 Donc S" = ( 100 010 111 110 000 101 001 011) Calcul de S3 0 g 0 Sll: 10 Pour simplifier et écourter les calculs on utilise ici l'opération ordinale au lieu de la composition de fonction (méthode « intuitive visuelle »): MI RU 1 S30g=( 001110011111100010000101)0(110 010 101 000 11111 01e1 011 111010)= 11.!2: ( 110 001 000 010 111 100 011 101) 15 (le calcul a été fait de la manière intuitive visuelle : « en dessous de ldi dans g, le 110 » , « en dessous de 111 dans g le 001 » , etc ) Ensuite S3 0 g 0 S" = 20 am (110 001 000 010 111 100 011 101)0(100 010 111 110 000 101 001 011)= ( 101 100 001 011 010 000 110 111) Dès lors A envoie à B le produit S3 0 g 0 S" = ( 101 la clé partielle envoyée à B par A. 100 001 011 010 000 110 111 ) qui est 25 De son côté B choisit lui aussi deux entiers secrets w et r , par exemple w = 5 et r = 8. Il calcule S5 0 g 0 58. Calcul de S5: p5(001)=p2(001)= 100 p5(111)=p5(p1(101))=p6(101)=p1(101)= 111 p5(101) =101 p5(011)=p5(p3(101))=p8(101)=p3(101)= 011 p5(100)=p5(p2(001))=p7(001)=p1(001)= 000 p5(110)=p5(p4(101))=p9(101)=p4(101)= 110 p5(000)=p5(p1(001))=p6(001)=p°(001)= 001 p5(010)=p5(p2(101))=p7(101) =p2(101)= 010 Donc S5 = (100 111 101 011 000 110 001 010) Calcul de S8: p8(001)=p2(001)= 100 p8(111)=p8(p1(101))=p9(101)=p4(101)= 110 p8(101) =p3(101)= 011 p8(011)= p8(p3(101))=p11(101)=p1(101)= 111 p8(100)=p8(p2(001))=p10(001)=p1(001)= 000 p8(110)=p8(p4(101))=p12(101)=p2(101)= 010 p8(000)=p8(p1(001))=p9(001)=p6(001)= 001 p8(010)=p8(p2(101))=p10(101) =0(101)=101 Donc S8 = (100 110 011 111 000 010 001 101) B calcule alors S5 0 g 0 S8 On utilise ici aussi l'opération ordinale: MI V11 to S5 O g=(100 111 101 011 000 110 001 010)0(110 010 101 000 111 001 011 100)= ( 111 010 101 000 011 001 110 100) S5 0g0S8 = II Mi MI Ill IN (111 010 101 000 011 001 110 100) 0 (100 110 011 111 000 010 001 101)= ( 110 101 011 001 111 100 010 000) qui est la clé partielle de B envoyée à A. B envoie donc à A : 0 g 0 S8 = ( 110 101 011 001 111 100 010 000) Donc à ce stade: A est en possession de (S5 0 g 0 S8) qui est ( 110 101 011 001 111 100 010 000) B est en possession de (S3 0 g 0 511) qui est ( 101 100 001 011 010 000 110 111) Dès lors A calcule : S30 ( 110 101 011 001 111 100 010 000 ) 0 S11 Il obtient d'abord : S3 0 ( 110 101 011 001 111 100 010 000) , qui est égal à : ( 001 110 011 111 100 010 000 101)0 (110 101 011 001 111 100 010 000)= (110 100 001 101 111 000 010 011) Et: (110 100 001 101 111 000 010 011 ) 0 S11 = il a IR 4111 (110 100 001 101 111 000 010 011 )0(100 010 111 110 000 101 001 011) = ( 101 000 100 111 010 001 011 110) qui est la clé K échangée puisque B calcule aussi de son côté: S5 0 ( 101 100 001 011 010 000 110 111 ) 0 S8 On a: S5 0 ( 101 100 001 011 010 000 110 111 ) = ( 100 111 101 011 000 110 001 010) 0 ( 101 100 001 011 010 000 110 111) = ( 010 100 001 011 110 000 101 111) et ( 010 100 001 011 110 000 101 111) 0 S8 = fi (010 100 001 on no 000 101 ni.) 0 (100 no on 111 000 olo 001 Pm) = ( 101 000 100 111 010 001 011 110) On retrouve bien la clé K calculée par A qui est la clé échangée par A et B. On mentionne ici pour finir deux techniques qui peuvent constituer des variantes du procédé POEC. 15 1-) Concaténation de la clé Une variante simple du Procédé Ordinal d'échange de clé est de concaténer la clé K. Si les les suites S et g sont composées d'entiers ou d'éléments pouvant être interprétés comme des entiers (par exemple : n-uplets de bits, symboles de numération hexa-décimale) la suite K échangée après concaténation est alors un entier. 20 Le procédé POEC est donc alors un système d'échange de nombre entier et permet donc de générer un entier secret pour deux protagonistes. La concaténation rend aussi plus difficile la cryptanalyse. 2-) Clés partielles multiples Les clés partielles sont celles que s'envoient les protagonistes et qui sont de la forme Sx 0 g 0 SY . Il est dès lors possible que les protagonistes s'échangent plusieurs clés partielles pour obtenir au final plusieurs clés communes. Celles-ci peuvent ensuite être multipliées pour obtenir une unique 5 clé commune K. Exemple: A choisit plusieurs couples d'entiers , par exemple trois couples (en pratique ce nombre peut être plus grand). Ces couples d'entiers sont secrets. Ils déterminent les clés (suites) privées de A. Ces trois couples sont par exemple : (5 9) , (45 21) , (11 84). 10 A envoie alors à B : S50 g0S9 S45 0 g 0 S21 S'10 g0S84 B de son côté choisit lui aussi trois couples d'entiers : (8 4) , (78 56) , (9 58) 15 B envoie alors à A: S8 0 g 0 S4 578Ø g 0 S58 S9 0 g 0 S58 Puis après cet échange A calcule: 20 = S5 0(S8 0 g0S4 )0S9 K2 = S45 0 (S78 0 g 0 S58 ) 0 S21 K3 = Sil 0(S9 0 g0S58 )0 S84 De son côté B calcule : K1= S8 0 ( S5 0 g 0 S8 ) 0 S4 K2 = S79 0 ( S49 0 g 0 S21 ) 0 S56 K3= S9 0 (S 1 1 0 g 0 S84 ) 0 S58 A et B sont alors en possession de trois clés communes K1, 1(2, K3. Celles-ci peuvent être alors multipliées pour donner la clé unique commune K partagée par A et B: KI 0 1(20 K3 = K L'avantage de ce système d'échange de clés partielles multiples est de rendre plus difficile l'analyse puisque l'espion doit alors faire une analyse pour chaque clé partielle. Outre l'analyse qui est plus difficile A et B peuvent aussi utiliser ce système pour se doter de plusieurs clés communes. REVENDICATIONS1- Procédé pour calculer une clé de chiffrement dérivée d'une clé secrète primitive dans le cadre d'un cryptosystème symétrique , en conséquence procédé pour muter ladite clé secrète primitive de chiffrement , éventuellement de manière publique dans un protocole de changement de clé, 5 caractérisé en ce que, - la clé secrète primitive est spécifiquement une bijection p d'un ensemble E dans E composé d'objets quelconques , E de cardinal fini et muni d'un ordre (type de clé appelé aussi « suite ordinale » , ou « clé ordinale » ) , p possédant en outre des cycles dont les longueurs sont des nombres n'ayant pas de diviseur commun, la clé p induisant en conséquence un Groupe cyclique 10 de bijections pl, (appelé aussi Groupe ordinal Commutatif , a étant le ppcm des longueurs des cycles de la fonction p) qui constitue un espace de clés secrètes partagé par les protagonistes ; - le calcul de la clé dérivée et mutée s'opére à l'aide de l'algorithme {Sa} X X ; lequel procède à partir de l'écriture de la clé primitive de chiffrement p sous forme de cycles et d'une variable 15 d'entrée constituée d'un w-uplet d'éléments de E ainsi défini : soit w le nombre de cycles de p, un élément de chaque cycle de la bijection p est alors choisi aléatoirement pour construire un w-uplet d'éléments de E, cet algorithme produisant en sortie une clé quelconque À de G qui est une bijection px dont l'exposant « x » n'a pas besoin d'être connu pour qu'elle puisse être calculée. D'où il résulte que la clé mutée peut être calculée à l'aide de ce seul w-uplet d'éléments de E à 20 partir de p , puis communiquée publiquement par ce w-uplet qui constitue le chiffre de la clé mutée , la clé mutée À ne pouvant être déterminée à partir de ce w-uplet sans la connaissance de p. 2 - Procédé selon revendication n° 1 , caractérisé en ce que, ledit procédé de mutation de clé est utilisé dans un protocole d'identification par « défi/réponse » dans lequel le défi consiste , à partir d'une clé secrète donnée sous forme de clé ordinale partagée par les protagonistes , à chiffrer une 25 donnée ou calculer une valeur sur la base d' une information communiquée sous forme de w-uplet choisi au hasard (le défi), ce w-uplet servant à muter la clé secrète par application de l'algorithme {Sa} -> À , ladite clé mutée servant à calculer la réponse au défi ou constituant elle-même la valeur calculée en réponse au défi. 3 - Procédé d'échange de clé dans lequel un élément g public d'un groupe commutatif G est donné 30 ainsi qu'une opération / non inversible sur G, l'échange de clé entre A et B s'opérant en communiquant (g / a) à B et (g / b)àA,a et b appartenant à G et choisis respectivement par A et B , d'où il résulte que A et B peuvent calculer après échange une clé identique qui est ((g _L b) / a) pour A, et ((g _L a) / b) pour B, selon revendication n°1 , caractérisé en ce que, - g est une clé ordinale donc g est une bijection de E dans E, E composé d'objets 35 quelconques , de cardinal fini et muni d'un ordre, - l'opération / est l'opération ordinale 0 , c'est à dire l'opération de composition de fonctions, - Les éléments a et b ne sont pas uniques mais doubles , en ce sens que A choisit deux éléments Si et S2 et B deux éléments S3 et S4 , calculés éventuellement par {Sa} -> À, lesquels éléments appartiennent à un groupe cyclique commutatif de bijections G généré par 40 une bijection p de E dans E , p ne commutant pas avec g,- A envoie à B le produit (Si 0 g 0 S2) et B envoie à A le produit ( S3 0 g 0 S4) , d'où il résulte que A calcule ( Si 0 ( S3 0 g 0 S4) 0 S2) et B calcule (S3 0 (Si 0 g 0 S2) 0 S4 ) qui sont deux produits identiques et qui constituent la clé K échangée par A et B.