FR 3016716 A1 20150724 FR 1401493 A 20140620 Description I) -Domaine technique de l'invention. Le domaine technique de l'invention est celui de la sécurité des cartes bancaires et plus précisément celui de l'authentification de la carte lors d'un paiement avec une carte bancaire à un terminal 5 électronique de paiement. Les techniques utilisées pour l'authentification des cartes bancaires reposant sur des procédés cryptographiques le domaine technique de l'invention est donc aussi celui de la cryptographie. II) -Technique antérieure Le type de paiement par carte bancaire qui va être considéré dans l'exposé de l'invention est le 10 paiement par carte bancaire à un terminal de paiement électronique chez un commerçant . Lors d'un paiement à l'aide d'un terminal de paiement électronique (TPE) chez un commerçant une authentification à distance de la carte bancaire peut être effectuée (en général pour des paiements d'un montant élevé). Cette authentification à distance est menée à l'aide d'un procédé de cryptographie symétrique utilisant un protocole « défi/réponse ». La technique connue est la 15 suivante : une clé secrète k est inscrite dans la mémoire de la puce dans sa partie illisible. Lors du paiement le terminal interroge un centre de contrôle à distance qui envoie à la carte une valeur aléatoire x . La carte calcule alors y = f (k,x) où f est un algorithme de chiffrement symétrique utilisant la clé secrète k. La valeur y , qui est le chiffre de x avec la clé k , est transmise au centre de contrôle qui lui-même calcule la valeur f (k,x) à l'aide de k qu'il détient aussi . S'il retrouve y cela 20 prouve que la carte détient la clé secrète k . Ce qui authentifie la carte de paiement. L'algorithme de chiffrement utilisé dans ce protocole est selon les informations connues l'AES. On note ici que dans ce procédé d'authentification il est nécessaire que le contrôleur central détienne les clés de toutes les cartes puisque le système cryptographique est symétrique. Le procédé de cryptographie qui va être décrit ci-après est un procédé d'authentification de carte 25 bancaire ayant pour but que le contrôleur central n'ait pas à stocker les clés privées de toutes les cartes . III)-Exposé de l'invention L'invention permet que le centre de contrôle n'ait plus besoin de détenir et de stocker les clés secrètes de chaque carte. Ces dernières sont associées dans l'invention à un entier qui peut être 30 choisi de manière aléatoire , être public , et qui fait fonction de clé publique . Cet entier faisant fonction de clé publique peut être inscrit dans la mémoire lisible de la puce ( ou même éventuellement être constitué par le code PIN à quatre chiffres de l'utilisateur de la carte). Les procédés cryptographiques qui permettent l'authentification de cartes bancaires de la manière qu'on vient de décrire reposent sur sur l'utilisation de théories et résultats mathématiques qui feront 35 l'objet de la section A de la présente partie III. La section B sera consacrée à l'utilisation et l'application de ces outils mathématiques pour l'authentification des cartes bancaires. A) Mathématiques L'une des caractéristiques de l'invention est de reposer sur des procédés cryptographiques qui utilisent les résultats mathématiques qui sont ceux de l'algèbre des permutations , notamment ils reposent sur l'utilisation de la structure algébrique de groupe ( Se , o) . Se est le groupe symétrique d'un ensemble E d'éléments et o est l'opération de composition de fonctions. Ces résultats, connus , sont détaillés dans les six paragraphes qui suivent. § 1 - Groupe symétrique d'un ensemble E Soit E un ensemble quelconque d'éléments. On appelle en mathématique Groupe symétrique de E l'ensemble des permutations de E et on note cet ensemble Se . Se est aussi l'ensemble des bijections de E dans E si E est muni d'un ordre. Par exemple (3 1 2) est une bijection p de l'ensemble {1,2,3} dans lui-même muni de l'ordre standard des entiers naturels . p est définie par p(1) = 3 , p(2) = 1 p(3) = 2. § 2- Cycle d'une permutation Le cycle d'une permutation S appartenant à Se , pour un élément i de cette permutation, est la suite (i , el , e2 , ph-1(i) ) , telle que : pl( i) = el , p2(i) = e2, ....., ph( i) = i , où : - p est la bijection associée à la permutation S. - pn est la bijectionp o p o....o p , o étant l'opération de composition de fonction itérée n-1 fois. - h est le plus petit entier tel que ph (i) = i . Le « cycle d'une permutation » est un concept identique à celui de « cycle d'une bijection » . La littérature mathématique appelle aussi parfois de tels objets des « orbites » (orbite de l'élément i selon p ) , ou « disjoints » , du fait qu'ils opèrent une partition de E en ensembles disjoints. Ici on les appellera « cycles » , ou « disjoints » . On donne quelques exemples de décomposition de permutations en cycle. ler Exemple : Soit S une permutation des neuf premiers entiers naturels définie de la manière suivante: S = ( 7 6 9 1 4 3 5 2 8 ) S s'écrit comme une fonction bijective p de {1,2,3,4,5,6,7,8,9} dans {1,2,3,4,5,6,7,8,9} muni de l'ordre standard des entiers : p(1) = 7 p(2) = 6 P(3) = 9 p(4) = 1 p(5) = 4 p(6) = 3 p(7) = 5 p(8) = 2 p(9) = 8 (qui signifie « 7 est le premier élément de S » , « 6 le second etc » etc). Pour i = 1 , on a Ci = (1 7 5 4) , puisque p(1) = 7 ,p2(1) = 5 ,p3(1) = 4 , puisqu'en effet : P2(1) = (P(P(1)) = 5 P3(1) =p(5) = 4 p4(1) =p(4) = 1 Pour i = 2 , on a de même C2 = ( 2 6 3 9 8) puisque p(2) = 6 , p2(2) = 3 , p3(2) = 9 , p4(2) = 8 , p5(2) = 2. Tous les éléments de E figurant dans CI et C2 , la fonction p ci-dessus définie ne possède donc que deux cycles .En définissant la longueur d'un cycle par le nombre de ses éléments ces deux cycles 15 sont de longueurs respectives 4 et 5. Une méthode simple et rapide , visuelle , pour construire les cycles d'une bijection est d'écrire celle-ci avec les numéros d'ordre au dessus des éléments de la permutation : 000000000 S=(76 9 14 35 2 8) 20 Il suffit alors de lire , « en dessous du O le 7 » , donc p(1) = 7 , puis « en dessous du O le 5 » , donc p2(1) = 5 , etc.. On construit ainsi les cycles de la bijection . Pour mieux représenter leur caractère cyclique on peut aussi les écrire sous forme de suites fléchées et rajouter le premier élément à la fin du cycle : 25 14745444 1 24643494842 Le premier élément d'un cycle donné peut par ailleurs être n'importe quel élément de ce cycle. Ainsi le cycle 24643494842 peut s'écrire 3494842 4643. 2nd exemple 30 Soit E = {0,1{3 l'ensemble des huit triplets de bits. E est donc ici composé de blocs de symboles (triplets de bits) Une permutation de E est alors par exemple la permutation S définie par : S = ( 000 010 111 110 001 101 100 011) Cette suite peut s'exprimer par une bijection de E dans E si l'on définit un ordre strict sur E. soit o cet ordre qu'on définit arbitrairement ainsi : o=( 001 111 101 011 100 116 006 ) 001 est le premier élément de E , 111 le second etc.. On écrit ces derniers en grisé pour mettre en valeur qu'ils constituent des « numéros d'ordre », comme les chiffres en rond noirs du premier exemple ci- dessus ( 0,0..) représentent des numéros d'ordre pour les suites de n premiers entiers. 001 111 101 011 100 110 000 010 Donc on a : S = ( 000 010 111 110 001 101 100 011 ) Maintenant la fonction bijective p associée à cette suite est donc : p(001) = 000 p(111)=010 p(101)=111 p(011)=110 15 p(100) = 001 p(110)=101 p(000) = 100 p(010) = 011 On peut vérifier par la méthode visuelle ou par calcul par composition de fonction que cette 20 bijection possède deux cycles (disjoints) de longueur respective 5 et 3 et qui sont : Cl= ( 001 000 100 ) C2 = ( 111 010 011 110 101) Dans la suite , les cycles d'une permutation seront pour des raisons de calculs présentés le plus 25 souvent sous forme de « puissances » de la bijection p , comme par exemple ci-après en ce qui concerne la permutation de triplets de bits ci-dessus (le premier élément i du disjoint est l'argument de p , on le réécrit par ailleurs à la fin du cycle sous la forme ph(i) = i , on peut aussi écrire au début du cycle l'identité p°(i) = i puisque h = 0 mod h , du fait que le cycle est de longueur h) : 35 Cl= p°(001) = 001 /91(001)- 000 p2(001) = 100 p3(001) = 001 C2= p°(111)=111 /91(111)= 010 p2(111) = 011 p3(111) = 110 p4(111) = 101 p5(111)= 111 30 § 3 - Sous-groupes cycliques de bijections (permutations) Un Sous-Groupe cyclique du groupe symétrique Se d'un ensemble E généré par une permutation p de Se est l'ensemble des permutations {p,p2,...pi,...,pa},oùpl =p ,p2=pop,p3=popop , etc . L'opération o est l'opération de composition de fonction . L'entier a est le ppcm des entiers représentant la longueur des cycles de p. Ce sous-groupe est cyclique modulo a et commutatif. L'entier a est aussi ce que l'on appelle en mathématiques l'ordre de la permutation p , c'est à dire le plus petit entier h tel que la fonction ph est la permutation identique. L'entier a est aussi l'ordre, au sens de cardinal , du sous-groupe généré par p. Soit p une bijection de E dans E , E muni d'un ordre (au sens de relation d'ordre) . On note donc pi la fonction telle que pi = p op o o p , l'opération o de composition de fonctions étant itérée j-1 fois. pj est une permutation du sous-groupe cyclique G de Se généré par p. Si les cycles CI , C2 ...,Ck de p ont pour longueur ni , n2, ...nk alors p génère un sous-groupe cyclique G de bijections { p , p2 , } , d'ordre a (de cardinal a), avec a = ppcm ( ni , n2 , ...nk ). Ce sous-groupe de Se contient un nombre de permutations égal à a. Chaque bijection de ce groupe est unique. Ce sous-groupe est cyclique modulo a en ce sens que si h> a , par exemple , alors ph = pl- avec r = reste(h/a). La fonction « reste » associant naturellement à la division de deux entiers le reste de la division. La permutation pa est l'ordre sur E (ici au sens de relation d'ordre) , c'est à dire la fonction identique , c'est à dire aussi la suite ordonnée des arguments de p à partir de laquelle est définie celle-ci . (D'autres manières de définir un sous-groupe-cyclique de Se existent , mais ici la notion de sous-groupe cyclique de Se sera toujours entendue comme ci-dessus, à savoir comme l'ensemble des permutations { p , p2 , pi ,...,pa }. Quand on parle en effet de sous-groupe cyclique d'un groupe symétrique Se en algèbre , c'est en général de cette manière qu'est entendue cette notion). Pour résumer , les sous-groupes cycliques de bijections pa} générés par une bijection (permutation) p, sont donc simplement les ensembles : p' =p p2 =pop p3 =popop p =pop o...o p , l'opération o appliquée j-1 fois pa=popo ......o p , l'opératio o de composition de fonction appliquée a - 1 fois. a est le ppcm de la longueur des cycles composant p et l'ordre du sous-groupe cyclique de bijections (l'ordre au sens de cardinal , qui ne doit pas être confondu avec l'ordre o sur E qui est la relation d'ordre sur E). On donne maintenant deux exemples de sous-groupes cycliques d'un groupe symétrique Se . Des exemples peuvent être utiles pour comprendre l'invention. Exemple 1 : 00000000 Soit S = (7 6 91 43 52 8) une bijection de E = {1,2,3,4,5,6,7,8,9} dans {1,2,3,4,5,6,7,8,9}. On peut vérifier que cette bijection possède deux cycles de longueur 4 et 5 , qui sont (sous forme 10 fléchée ): 1->7->544->1 246->349->8->2 On peut vérifier que cette bijection engendre le sous-groupe cyclique de bijections suivant qui possède 20 éléments , puisque ppcm(4,5) = 20 : 15 p= p2= 000000000 ( 7 6 9 1 4 3 5 2 8 ) ( 5 3 8 7 1 9 4 6 2 ) p3= (4 92 57 8 13 6) p4= ( 1 8 6 4 5 2 7 9 3 ) 20 p5= ( 7 2 3 1 4 6 5 8 9 ) P6 = ( 5 69 71 3 42 8) p7_ ( 4 3 8 5 7 9 1 6 2 ) P8 = ( 1 92 45 8 73 6) P9 = ( 7 86 1 4 2 59 3) 25 p10 ( 5 23 71 6 4 8 9) p11 ( 4 6 9 5 7 3 1 2 8 ) p12 ( 1 38 45 9 7 6 2 ) p13 ( 7 92 14 8 53 6) p14 ( 5 86 71 2 4 9 3) 30 p15 ( 4 2 3 57 6 1 8 9) p16 ( 1 69 45 3 72 8) p17 ( 7 38 14 9 5 6 2 ) p18 ( 5 92 71 8 43 6) p19 ( 4 8 6 5 7 2 1 9 3 ) 35 p20 (1 23 45 6 78 9)=o Ce sous-groupe de bijections est cyclique modulo 20. En effet p2° = ( 1 2 3 4 5 6 7 8 9 ) qui est l'ordre (relation d'ordre) sur E et la fonction identique , donc on a à la suite : pzi(1) = p(p20(1)) = p(1) - 7 p21(2) = p(p20(2)) = 6 , etc , on calcule ainsi la suite p primitive génératrice qui est S= ( 7 6 9 1 4 3 5 2 8) Et donc p21 = p1 , p22 , p2 P23 = 193 , etc , le sous-groupe cyclique de bijections est cyclique modulo 20. Exemple 2 Soit E = {0,1} 3 l'ensemble des huit triplets de bits Soit S = (000 010 111 110 001 101 100 011) une permutation de E. On définit l'ordre sur E par la suite ordonnée o = ( 001 111 101 011 100 110 000 010 ) La bijection associée à la permutation S est donc : p(001) = 000 p(111)=010 p(101)=111 p(011)= 110 p(100) = 001 p(110)=101 p(000) = 100 p(010) = 011 Cette bijection possède deux cycles de longueurs 3 et 5 qui sont sous forme de disjoints: ( 001 000 100 ) ( 111 010 011 110 101) Cette permutation de triplets de bits engendrera donc un sous-groupe G cyclique de bijections de {0,1} 3 dans {0,1} 3 d'ordre (cardinal) : ppcm(3,5) = 15. Ce groupe est cyclique mod15. On peut vérifier en effet que G est : 001 111 101 011 100 110 000 010 000 010 111 110 001 101 100 011 = pl 100 011 010 101 000 111 001 110 = p2 001 110 011 111 100 010 000 101 = p3 000 101 110 010 001 011 100 111 = p4 8 100 111 101 011 000 110 001 010 = p5 001 010 111 110 100 101 000 011 = p6 000 011 010 101 001 111 100 110 = 197 100 110 011 111 000 010 001 101 = /98 001 101 110 010 100 011 000 111 = p9 000 111 101 011 001 110 100 010 = p10 100 010 111 110 000 101 001 011 = p" 001 011 010 101 100 111 000 110 = /912 000 110 011 111 001 010 100 101 = p13 100 101 110 010 000 011 001 111 = p14 001 111 101 011 100 110 000 010 = p'5 On refait ici la remarque que E peut être composé de blocs de symboles (des n-uplets de bits par exemple) et non pas seulement de symboles . Le groupe symétrique Se de E dans un tel cas est donc composé de permutations dont les éléments sont des blocs de symboles. Dès lors quand E est constitué de blocs de symboles on peut aussi faire la remarque qu'il n'est pas nécessaire que ces blocs de symboles soient « standards » , comme par exemple des n-uplets de bits de même longueur (cas où E = {0,1}n par exemple) Il est en effet possible de choisir aléatoirement les blocs de symboles qui composent E . La seule condition requise est que ces blocs soient tous différents deux à deux. Par exemple E peut être : {0011 , 00 , 11011 , 10110 , 11 , 0010 , 0000 , 20 1100 , 00001 }, ces neuf n-uplets de bits ainsi que leur ordre étant choisi aléatoirement . En dernier point enfin on précise que les sous-groupes cycliques de Se sont commutatifs et que toutes les permutations appartenant à un sous-groupe cyclique de Se sont différentes les unes des autres. 4-Calcul de p' dans G 25 Calcul de pi dans G : une méthode de calcul appelée {Sa} --> , ou {p a} --> , ou encore plus simplement méthode « j » calcule la permutation p' de G. L'algorithme est le suivant : 1- Si i est le premier élément d'un des cycles C de p, alors pi(i) = , avec r = j mod L , L étant la longueur du cycle C de i. 30 2- Sinon : On cherche le cycle Ck , dont le premier élément est k, dans lequel figure i. Cela nous donne l'entier x tel que px(k) = i , qui est donné par le cycle Ck On calcule ensuite le reste r de (j + x)/Lk , Lk étant la longueur du cycle Ck. On obtient alors : pi(i) = pr(k) , avec r = (j + x)mod Lk . § 5- w-uplet du produit cartésien des disjoints d'une permutation. Soit E un ensemble ordonné et p une permutation de E engendrant le sous-groupe cyclique G de Se défini par G = {p,p2, ..,pa} , a ppcm des longueurs des disjoints de p. Soient CI , C2 ,.... .Cw les w cycles (disjoints ) de p , et ji , j2,....jw les w premiers éléments 5 (éléments pris comme éléments de base ) de chaque cycle de p. Dès lors si les entiers définissant les longueurs des w cycles de p n'ont pas de diviseur commun, alors pour chaque w-uplet , wz , ...ww) du produit cartésien CI x C2 x.... x Cw il existe une et une seule permutation p.' appartenant à G telle que : AI) = wi , pX(j2) = w2, px(j3) = w3, pX(w) ww. 10 On ne démontre pas ce résultat . On donne simplement un exemple d'illustration : Exemple : Soit la permutation S suivante de E = {1,2,3,4,5,6,7}muni de l'ordre standard des entiers: 0000000 S = ( 3 7 5 2 6 1 4) 15 Les disjoints de S sont au nombre de 2 (donc w = 2) et sont : CI = (1 3 5 6 ) , de longueur Li = 4 C2= (2 7 4) , de longueur L2 = 3 Le ppcm des entiers représentant la longueur des cycles de S est ppcm{4,3} = 4 x 3 = 12. Le sous-groupe cyclique G de Se généré par S est reproduit ci-après : 20 00 00 0 0 S = ( 3 7 5 2 6 1 4) S2 = (5 4 6 7 1 3 2 )=SoS 53 -(6 2 1 4 3 5 7)=SoSoS,etc, S4 = (1 7 3 2 5 6 4) 25 S5 = (3 4 5 7 6 1 2 ) S6 = (5 2 6 4 1 3 7) S7 = (6 7 1 2 3 5 4) S8 = (1 4 3 7 5 6 2) S9 = 2 5 4 6 1 7) 30 S10- (5 7 6 2 1 3 4 ) S''= (6 4 1 7 3 5 2) S'2= (1 2 3 4 5 6 7) On constate ainsi que les éléments du premier cycle (disjoint) Ci : 3 , 5 , 6 , 1 , reviennent de manière cyclique dans la colonne 0.De même pour les éléments du cycle C2 qui reviennent en boucle dans la colonne 0. Dans chaque permutation appartenant à G figure un 2-uplet appartenant au produit cartésien des 5 disjoints Ci et C2 . Ces 2-uplets sont des w-uplets avec ici w = 2. Les éléments de ces 2-uplets figurent (en grisé) aux colonnes 00 dont les numéros sont les premiers éléments (1 et 2) de chacun des deux cycles . On constate par ailleurs que ces 2-uplets sont tous différents et donc puisque a est égal à 12 qu'il existe douze 2-uplets différents. L'ensemble des 2-uplets figurant aux colonnes 1 et 2 de G est donc 10 le produit cartésien CI x C2 des disjoints de S , puisque quand les cycles ont des longueurs n'ayant pas de diviseur commun le cardinal de G (qui est a) est égal au cardinal du produit cartésien des cycles. On a en effet les 2-uplets suivants (chiffres dans les cercles = numéros de colonne) : 0 0 3 7 5 7 4 6 4 6 2 1 2 1 7 3 4 5 2 6 7 1 4 3 2 Chacun de ces douze 2-uplets ne figure que dans une et une seule permutation Sx appartenant à G. 25 Puisque le nombre de w-uplets est égal à a (a = ppcm des entiers représentant la longueur des disjoints de S) et que chaque w-uplet ne figure que dans une seule permutation appartenant à G il en résulte que quand ces entiers n'ont pas de diviseur commun l'ensemble des w-uplets figurant dans les permutations composant G est égal au produit cartésien des disjoints de S. Note : Dans la suite un élément du produit cartésien des disjoints composant une permutation p 30 sera toujours désigné par le terme « w-uplet ». 6- Couples de solutions d'une composition de deux bijections où les deux composantes sont inconnues : Soit p une bijection donnée de E dans E , E fini de cardinal n. On cherche les bijections inconnues x et y telles que x o y =p 35 Exemple : Soit p la bijection suivante de {1,2,3} dans {1,2,3} muni de l'ordre standard des entiers naturels (on la donne sous forme de suite S) : S = (2 3 1) 15 20 Cette permutation est une permutation du groupe symétrique Se de E = {1 , 2 , 3} . On a par ailleurs Se = { (1 2 3) , (1 3 2) , (2 1 3) , (2 3 1) , (3 1 2) , (3 2 1) 1 C'est l'ensemble des permutations de {1,2,3} . On constate dès lors que dans l'équation x o y = ( 2 3 1) il existe 3! couples de bijection ( x , y) 5 qui sont solution de l'équation. En effet on peut vérifier que : (2 3 1) o (1 2 3) = (2 3 1) (3 2 1) o (1 3 2) = (2 3 1) (1 3 2) o (2 1 3) = (2 3 1) 10 (1 2 3) o (2 3 1) = (2 3 1) (3 1 2) o (3 1 2) = (2 3 1) (2 1 3) o (3 2 1) = (2 3 1) Dans la seconde équation par exemple on a x(1) = 3 , x(3) = 2 , x(3) = 1 ; et y(1) = 1 ,y(2) = 3 , y(3) = 2 . Donc en composant (x o y) , c'est à dire en calculant y(x(i)) pour tout i de {1,2,3} on a bien: 15 y(x(1)) = y(3) = 2 y(x(2)) = y(2) = 3 y(x(3)) =y(1) = 1 Pour chaque bijection x choisie il existe une bijection y telle que (x o y) = (2 3 1) . Donc 3! couples de solutions (x y). 20 Par ailleurs on peut remarquer que chaque bijection y est différente de chaque autre. Ce résultat s'énonce mathématiquement ainsi : Soit h une fonction bijective d'un ensemble E dans E , E de cardinal n fini . Alors , pour toute fonction bijective g de E dans E , il existe une fonction bijective f de E dans E telle que fog=h; et si g' * g il existe une fonction f ' telle que f' o g' = h , avec f # f'. 25 Ce qu'il y a à retenir est que l'équation x o y = f, où x , y et f sont des bijections définies sur un ensemble E de cardinal n possède n! couples de solutions (x,y) Cette propriété est parfois énoncée par « toute suite divise toute suite » ou « toute bijection divise toute bijection » en ce sens que : une bijection f sur un ensemble E étant donnée , pour toute bijection g de E il existe une bijection x de E qui satisfait l'équation x o g=f. L'équation x og=f 30 pouvant être considérée comme une division de f par g (division à droite , la division à gauche s'exprimant par go x =f). B) Application à l'authentification des cartes bancaires L'authentification des cartes bancaires qui va être décrite correspond à une situation où une entité centrale (banque , centre de contrôle , autorité vérificatrice) fabrique et attribue à chaque carte bancaire les clés de chiffrement permettant l'authentification par défi/réponse à partir d'une clé secrète uniquement détenue par elle. L'authentification se fait ensuite toujours auprès de ce contrôleur central. Authentification à distance à un terminal électronique de paiement chez un commerçant: La banque où l'entité centrale qui fabrique et attribue les cartes bancaires choisit une clé-mère constituée de : - un ensemble ordonné E de symboles ou blocs de symboles , de grand ordre (cardinal), - une permutation p appartenant à Se composée de nombreux disjoints dont les longueurs n'ont pas de diviseur commun , - un « w-uplet » de p . Les cartes bancaires délivrées aux usagers sont alors conçues et fabriquées de la manière suivante : 15 Pour chaque carte l'entité vérificatrice choisit un entier j de manière aléatoire et calcule pi . - pi est alors la clé secrète k propre à chaque carte , inscrite dans la partie illisible de la puce avec le w-uplet w = ( i] ,i2'iw) qui est constitué des premiers éléments de chaque cycle de p. - j est la clé publique figurant dans la partie lisible de la puce . Chaque carte possède alors un couple de clé « publique/privée » de type (j,pJ) qui est unique et donc 20 qui lui est propre si le sous-groupe cyclique G de permutations généré par la clé-mère p est de grand cardinal. Lors d'une authentification à distance le centre de contrôle envoie à la carte un entier aléatoire h. La carte doit alors calculer h(ik) pour chaque ik de w. La valeur obtenue y est une suite de symboles ou blocs de symboles de E. 25 De son côté le centre de contrôle prend connaissance de la clé publique j de la carte et calcule de même pi x h (ik) pour chaque h de w. S'il retrouve y cela prouve que la carte est authentique car cela signifie que sa clé secrète est bien pi qui a été fabriquée et attribuée par la banque ou l'entité vérificatrice. Avec cette méthode le centre de contrôle n'a pas à connaître et stocker les clés secrètes de 30 chaque carte. La valeur y est calculée par le centre de contrôle uniquement à partir de la clé-mère p qui est secrète et détenue uniquement par lui. Selon une variante du procédé le w-uplet (i. ,i2 'iw) peut ne pas faire partie de la clé secrète k inscrite dans la partie illisible de la carte à puce mais faire partie de l'envoi du centre de contrôle . Il peut aussi être un n-uplet quelconque À d'éléments de E . Dans ce cas la clé secrète k de chaque 35 carte est constituée uniquement de la permutation pi et les données envoyées à la carte par le centre de contrôle pour calculer la valeur y de contrôle sont constituées du couple (h, À) , À pouvant être choisi aléatoirement par le centre de contrôle et ne pas être constitué des premiers éléments de chaque cycle. IV-Exemple de mode de réalisation de l'invention. L'entité qui délivre les cartes bancaires doit attribuer à chaque carte un couple de clé « publique/privée » . La clé privée étant calculée à partir de la clé-mère que seule cette entité détient. L'entité centrale ou la banque doit donc dans un premier temps choisir une clé-mère de la manière décrite ci-dessus. Puis dans un second temps elle fabrique les couples de clés « publique/privée » 10 pour les attribuer à chaque carte. La banque choisit donc un ensemble E de symboles ou blocs de symboles induisant un groupe symétrique Se de permutations de E. Soit p cette permutation. La banque chosit ici un ensemble E composé de n-uplets de bits choisis aléatoirement. Pour des 15 raisons pratique de calcul on choisit dans l'exemple E composé uniquement de 18 n-uplets de bits. Les disjoints de p sont choisis de longueur 5 , 6 et 7. Soit E = {0011 , 001 , 11011 , 10110 , 11 , 0010 , 0000 , 1100 , 00001 , 010001 , 110111 , 0110 , 01111,01001 ,100110,10010 , 110101 , 00100} Les disjoints (cycles) de p sont : 20 (1100 01111 0010 10010 11) (010001 001 0011 100110 110101 00100) (110111 11011 10110 01001 00001 0110 0000) Exprimés sous forme de « puissances » de la fonction p , ces cycles sont : C1= C2 - C3 = 25 p°(1100) = 1100 p°(010001) = 010001 p°(110111) = 110111 p' (1100) = 01111 p' (010001) = 001 pl(110111)= 11011 p2(1100) = 0010 p2(010001) = 0011 p2(110111) = 10110 p3(1100) = 10010 p3(010001) = 100110 p3(110111) = 01001 p4(1100) = 11 p4(010001) = 110101 p4(110111) = 00001 30 p5(1100) = 1100 p5(010001) = 00100 p5(110111) = 0110 p6(010001) = 010001 p6(110111) = 0000 p7(110111) = 110111 C'est à partir de cette clé-mère que la banque attribue les couples de clés « publique/privée » de la manière suivante. Soit CB une carte bancaire à doter d'un tel couple de clé. La banque choisit un entier j de manière aléatoire. Puis elle calcule la permutation pi qui sera la clé privée attribuée à la carte et qui sera écrite sous forme de « puissances » d'une bijection afin de pouvoir utiliser par exemple l'algorithme {pa} ----> pi pour les calculs lors de l'authentification. Note : Sur le plan du calcul de la clé p . le calcul de pi peut être fait en choisissant un ordre (relation d'ordre) sur E puis en calculant pi(i) 10 pour chaque i de E pris dans l'ordre des éléments de E. De la permutation pi on en déduit ensuite ses disjoints (à titre d'information il est ici à noter que la structure cyclique de pi n'est pas forcément la même que celle de p . p peut avoir un nombre de disjoints donné n et pi un nombre supérieur à n , en fait les cycles de p peuvent être divisés comme le montre l'exemple ci-dessous, on ne démontre pas ce résultat mathématique qui est par ailleurs connu). 15 Il est aussi possible de calculer les disjoints de pi de la manière suivante : Soit par exemple j = 7292 (on choisit j ici à quatre chiffres mais j n'est pas forcément au format code PIN , j qui est la clé publique de la carte peut être un entier quelconque). La banque ou l'autorité vérificatrice calcule alors pour chaque élément de base i des cycles : p7292(i) ) puis p7292(p7292(i)) , puis p7292(p7292(p7292(i))) , etc , jusqu'à ce que la valeur obtenue 20 soit i . Le cycle est alors achevé. Ainsi pour i = 1100 , premier élément du cycle CI de p, de longueur 5 , on calcule : p7292(1100) =p2(1100) , car 2 = 7292 mod 5 p2(1100) = 0010 , voir cycle CI. On doit ensuite calculer p7292(p7292(1100)) , c'est à dire p7292(0010) , 25 p7292(0010) =p2(0010) =p4(1100) , puisque 0010 =p2(1100) p4(1100) = 11 , voir cycle CI. De même on calcule les valeurs qui suivent : p7292(11) ---p2(11) =p6(1100) =p'(1100) -1 (1100) = 01111 p7292(01111) =p2(01111) =p3(1100) = 10010 p7292(10010) =p2(10010) =p5(1100) = 1100 Le cycle est achevé puisqu'on est revenu à i = 1100. En posant que k = p7292 le premier cycle KI de la clé privée k attribuée à la carte bancaire sera donc : KI = k°(1100) = 1100 k1(1100) = 0010 k2(1100) = 11 k3(1100) = 01111 k4(1100) = 10010 k5(1100) = 1100 On calcule ensuite K2 à partir de i = 010001 qui est le premier élément du deuxième cycle C2 de p p7292(010001) =p2(010001) , car 2 = 7292mod 6. p2(010001) = 0011 , donc kl(010001) = 0011 , puis : p7292(0011)=p2(0011)=p4(010001)= 110101 p7292(110101)=p2(110101)=p6(010001)= 010001 Le cycle est achevé puisqu'on est revenu à i = 010001. Le cycle C2 de p est donc divisé dans p7292. Pour calculer le cycle suivant on prend le premier élément du disjoint C2 de p qui ne figure pas dans le cycle qui vient d'être calculé . C'est ici 001 . On calcule donc ensuite le cycle de i = 001. Au final on peut vérifier que la clé privée k = p7292 attribuée à la carte est composée des quatre 20 cycles suivants: KI = K2 = K3 = K4 = k°(1100) = 1100 k°(010001) = 010001 k°(001) = 001 k°(110111) = 110111 kI(1100)= 0010 kl(010001)= 0011 kI(001)= 100110 kl(110111)= 0110 k2(1100) = 11 k2(010001) = 110101 k2(001) = 00100 k2(110111) = 01001 25 k3(1100) = 01111 k3(010001) = 010001 k3(001) = 001 k3(110111) =11011 0(1100) = 10010 0(110111) = 0000 k5(1100) = 1100 k5(110111) = 00001 k6(110111) = 10110 k7(110111) = 110111 La carte bancaire de l'utilisateur sera donc dotée : - de la clé privée k écrite dans la partie illisible de la puce - de l'entier j = 7292 dans la partie lisible de la puce et faisant fonction de clé publique. (Le n-uplet À est ici envoyé par le contrôleur central et ne fait pas partie de la clé privée). Lors d'une authentification à distance le centre de contrôle envoie par exemple à la carte un n-uplet À d'éléments de E et un entier h choisis de manière aléatoire, par exemple À = (11 00001 100110 10110) et h = 4589. la carte calcule alors avec l'algorithme {pa} -+ k4589(11) = k4(k2(1100)) = k6(1100) = k'(1100)= 0010 k4589(00001)= k4(00001)= k4(k5(110111))= k9(110111)= k2(110111)= 01001 k4599(100110)= k2(100110)= k2(k1(001))= k3(001) = 001 0589(10110) = 0(10110) = k4(k6(110111))= k10(110111)=k3(110111)= 11011 La valeur envoyée par la carte au centre de contrôle est donc y = 00100100100111011 De son côté le centre de contrôle prend connaissance de la clé publique j = 7292 de la carte et 15 calcule (à l'aide la la permutationp qu'il détient et qui est la clé-mère et avec {pa} ---> p'): p4589 x 7292(11) =p33462988(11) = p3(11) , puisque le cycle Ci de la fonction p (page 23 ci-dessus) est de longueur 5 et que 3 = 33462988 mod5, p3(11) =p3(p4(1100)) , voir cycle Ci de p. p3(p4(1100))=p7(1100)=p2(1100)= 0010 20 de même : p4589 x 7292(00001) =p33462988(00001) = p6(00001) = p6(p4(110111))=p1°( 110111) = p3( 110111)= 01001 p4589 X 7292(100110) =p33462988(100110) = p4(100110) = p4(p3(010001)) =p7( 010001 )= pl (010001) = 001 25 p4589 x 7292(10110) =p33462988(10110) = p6(10110)= p6(p2(110111))=p8(110111)- p1( 110111 ) = 11011 Le centre de contrôle retrouve bien y = 00100100100111011 et la carte bancaire est donc authentique. V-Autre mode de réalisation Concernant la sécurité , le point important du procédé ci-dessus décrit est qu'il doit être impossible de retrouver la clé privée k d'une carte ou la clé-mère à partir de la clé clé publique de la carte. Sans quoi de fausses cartes pourraient être conçues par un faussaire. Dans le cas de l'authentification à un terminal de paiement électronique l'analyste ne peut connaitre que la clé publique j . La clé privée k = pi est en effet normalement inaccessible dans la puce . Par ailleurs même connaissant j et pi il ne semble pas possible de retrouver la clé-mère p si l'ordre o (relation d'ordre) sur E est inconnu , cela sauf recherche exhaustive sur toutes les possibilités de relation d'ordre sur E . En effet l'analyste qui aurait connaissance de pi et de j , par exemple de j = 6 et de la permutation de triplets de bits K6 = p6 = 001 010 111 110 100 101 000 011 , doit d'abord connaître , pour retrouver la bijection p , la suite xi , x2' x8 telle que : p6(xl) = 001 p6(x2) = 010 p6(x3) = 111 p6(x4) = 110 p6(x5) = 100 p6(x6) = 101 p6(x7) = 000 p6(x8) = 011 Mais la suite de triplets de bits xi ,x2, x8 qui est l'ordre secret sur E lui est inconnue. Si E = {0,1} 8 , par exemple , il existe 256! ordres o possibles sur E . (si l'ordre sur E est connu il peut être possible dans certains cas de retrouver pi à partir de j de manière méthodique par un algorithme de calcul , on ne démontre pas ce point). Malgré ces garanties de sécurité on va exposer rapidement ci-après une autre méthode pour fabriquer des couples de clé « publique/privée » pour le paiement à un terminal électronique de paiement. Cette méthode permet que les informations figurant sur les cartes bancaires donnent encore moins d'information sur la clé mère et que la recherche exhaustive soit plus difficile. Elle est une simple variante de celle déjà exposée . Pour le paiement à un terminal électronique: L'entité qui fabrique et attribue les couples de clés « publique/privée » choisit deux permutations p et q d'un ensemble E et calcule la permutation (p1 o qi) appartenant à Se . La permutation k = ( pi o ) est la clé privée de la carte , j la clé publique. Exemples Exemple (avec un ensemble E de petit cardinal pour écourter les calculs): Soit E = {1 2 3 4 5 6 7 8 9 10 11 12 } , l'ensemble des douze premiers entiers. Les clés-mères p et q , permutations de E , sont choisies de la manière suivante: p= (3 7 11) , cycle de longueur 3 (5 8 6 10 9) , cycle de longueur 5 (2 12 1 4) , cycle longueur 4 q= (1 7 9 10 8 4 3) , cycle de longueur 7 (2 5 12 11 6) , cycle de longueur 5 Ces cycles (disjoints) exprimés sous forme de « puissances » de p et q sont : Clp = C2p = -= 5 C3p = = 2 Pc1(3) = 3 P°(5) p°(2) p1(3) = 7 pl (5) = 8 /91(2) = 12 p2(3) = 11 p2(5) = 6 p2(2) = 1 P3(3) = 3 p3(5) = 10 p3(2) = 4 p4(5) = 9 p4(2) = 2 p5(5) = 5 pour p , C2q = Clq = q°(1) = 1 q°(2) = 2 q1(1) = 7 q1(2) = 5 q2(1) = 9 q2(2) = 12 q3(1) = 10 q3(2) = 11 q4(1) = 8 q4(2) = 6 q5(1) = 4 q5(2) = 2 q6(1) = 3 q7(1) = 1 pour q . La banque ou le centre de contrôle , pour fabriquer la clé privée de chaque carte , calcule la fonction ( pi o ) en entier. Soit j = 14 On peut vérifier en calculant q14(1914(i)) , pour chaque i de E , que p14 o q14 ) est : (1 6 8 2) (3 12 4 5 9 10 11 7) Dès lors la permutation k telle que k = p14 014 q ) est la clé privée de la carte (exprimée sous forme de « puissances » de la bijection k) , et j = 14 la clé publique. Note : dans cette variante il est nécessaire pour pouvoir vérifier si le défi est relevé que le centre de contrôle lors de l'authentification recalcule en totalité la permutation k . En effet après l'envoi de l'entier aléatoire h , la carte pour relever le défi calcule kh(ik) pour chaque ik du n-uplet À , avec k = ( pi o qi ) . Mais le centre de contrôle qui doit effectuer ses calculs de vérification avec les seules permutations p et q qu'il détient ne peut vérifier en calculant pixh(ik ) o ) car la bijection ( 0 (qi)h n'est pas égale à kh . On a en effet kh = ( pi o qJ )h qui est différente de ( pi)h o (qJ)h , sauf si p et q commutent. Pour calculer ( pi o qi )h(ik) , c'est à dire la valeur de ( o )I pour chaque ik de À le centre de contrôle doit recalculer en totalité ( pi o qJ )h . Il est possible cependant selon une méthode plus complexe de faire subir à la clé privée k une transformation après l'avoir fabriquée pour que des algorithmes de calcul permettent de calculer ( pi o qi )h(ik) sans avoir à recalculer en totalité la bijection ( o )11 . Sur le plan de la sécurité : Choisir deux permutations différentes de E pour les composer permet d'améliorer la sécurité . En effet connaissant la permutation ( pi o qi ) ainsi que j l'analyste ne peut retrouver les clés-mères p et q que par une recherche exhaustive sur l'ensemble Se des permutations de E en testant pour chaque couple (p , q) de permutations appartenant à Se o qJ = k . En effet l'analyste doit résoudre une équation de type x o y =f avec f une bijection connue et x et y deux bijections inconnues définies sur un ensemble E de cardinal n. Or dans ce cas l'équation x o y =f possède n! couples (x,y ) de solutions (voir partie III , section A , § 6). Donc dans l'équation k = ( o ) , si k vient à être connu mais que p' et qi sont inconnues l'analyste doit tester pour chaque couple (p , q) de permutations de E si pi o = k . Il semble qu'il n'existe pas d'autre méthode pour retrouver les permutations p et q connaissant j. Si l'ordre (cardinal) de E est grand la recherche exhaustive devient très difficile . Si E contient par exemple 132 éléments il existe 132! permutations de E. Donc la recherche dans ce cas doit être menée sur les ( 132! x 132! ) couples de permutations de E ( cela en supposant que la relation d'ordre o sur E soit connue pour que la calcul de composition de fonction puisse être appliqué).5 REVENDICATIONS1 - Procédé d'authentification à distance d'une carte bancaire par un centre de contrôle lors d'un paiement à un terminal électronique chez un commerçant dans lequel la carte est authentifiée selon un protocole « défi/réponse » par un système de cryptographie symétrique par le procédé suivant : chaque carte est dotée d'une clé secrète de chiffrement k , connue et stockée par le centre de contrôle , ce dernier envoie alors à la carte par l'intermédiaire du terminal électronique une donnée x, la carte retourne alors au centre de contrôle la valeur chiffrée de x avec la clé secrète k qu'elle détient , si cette valeur est correcte , c'est à dire si elle correspond bien au chiffre de x avec k , la carte est authentique et le centre de contrôle autorise le paiement ; caractérisé en ce que chaque carte bancaire est dotée d'une clé privée k , écrite dans la partie illisible de la puce , et en outre d'une clé publique j écrite dans la partie lisible de la puce avec laquelle le centre de contrôle vérifie que le défi est relevé , le couple de clés « publique/privée » (k, j) étant fabriqué par la banque ou le centre de contrôle à partir d'une clé secrète appelée clé-mère connue uniquement par ces derniers , cela de la manière suivante: la banque ou le centre de contrôle choisit en premier lieu une permutation appartenant au groupe symétrique Se d'un ensemble ordonné E composé de symboles ou blocs de symboles , définie et notée par la bijection p de E dans E associée à cette permutation , p composée spécialement de plusieurs disjoints afin de générer un sous-groupe cyclique G = {p,...pi,..., pal de Se de grand cardinal, a étant le ppcm des entiers représentant les longueurs des disjoints de p , lesquelles 20 longueurs n'ont pas ou peu de diviseurs communs afin que a soit très grand ; la permutation p constituant alors la clé-mère détenue secrètement par la banque ou le centre de contrôle . Puis en second lieu la banque ou le centre de contrôle choisit pour chaque carte bancaire un entier aléatoire j et calcule la permutation pi , où pi est définie par p o p o ....o p avec l'opération o de composition de fonction itérée j-1 fois ; la clé privée k de la carte bancaire est alors la permutation k 25 = pi et la clé publique est l'entier j. L'authentification à distance s'opère alors par l'envoi à la carte d'une donnée x composée d'un entier aléatoire h et d'un n-uplet quelconque X = ( il ,i2,..,ik,...,in) d'éléments de E. Le n-uplet X , selon une variante du procédé , peut aussi être constant et figurer dans la partie illisible de la puce comme complément de la clé privée k de la carte. Le défi consiste pour la carte à calculer kh( h) pour 30 chaque ik appartenant à X , c'est à dire la valeur de la bijection kh pour chaque argument ik de X . Le centre de contrôle vérifie si le défi est relevé en calculant pi X h( ik) pour chaque ik appartenant à X après avoir pris connaissance de la clé publique j de la carte , cette vérification étant faite sans que le centre de contrôle ait besoin de détenir et de stocker la clé privée de chaque carte bancaire. Le calcul de kh( ik) et pi x h( ik) étant mené avec l'algorithme {pa} --> pi qui calcule pour une 35 bijection p quelconque la valeur pi (i) de la manière suivante : si i est le premier élément d'un des cycles C de p , alors pi(i) = , avec r = j mod L , L étant la longueur du cycle C de i ; sinon chercher le cycle Ck , dont le premier élément est k, dans lequel figure i. Cela donne l'entier x tel que px(k) = i qui est donné par le cycle Ck . Calculer ensuite le reste r de (j + x)/Lk , Lk étant la longueur du cycle Ck. On obtient alors : =pr(k) , avec r = (j + x)mod Lk . 40 2 - Procédé d'authentification à distance d'une carte bancaire par un centre de contrôle lors d'un paiement à un terminal électronique chez un commerçant , selon revendication 1 , caractérisé en ce que la clé-mère secrète détenue par le centre de contrôle n'est plus constituée d'une seule permutation mais de deux permutations p et q , la clé privée k attribuée à chaque carte bancaireétant alors la permutation k = ( pi o ) . Le défi consiste ensuite pour la carte à calculer kh( ik) pour chaque ik appartenant au w-uplet X , le centre de contrôle vérifie si le défi est relevé en calculant (19' o )h( ik) pour chaque ik appartenant au w-uplet X sans avoir à stocker les clés privées de chaque carte.I Dossier de la demande initiale dont les revendications au moins ont été limitées à un seul objet (revendications 1 et 3).