Brevet FR3016715A1 — publié le 20150724

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. 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 Les deux types de paiement par carte bancaire qui vont être considérés dans l'exposé de l'invention sont le paiement à distance en ligne par le biais d'internet et le paiement chez un commerçant à un 10 terminal de paiement électronique. 1°) -Lors d'un achat sur Internet l'acheteur doit entrer son numéro de carte bancaire N et ce qu'on appelle en général le « cryptogramme visuel » , qu'on note ici C , et qui est le plus souvent un nombre de trois chiffres. Le numéro de carte N est toujours composé en premier lieu de codes composés de chiffres 15 identifiant le type de carte puis la banque , puis ensuite vient un numéro qui est le numéro de carte proprement dit qui peut désigner un numéro de compte. Le cryptogramme visuel est fonction du numéro de carte car il résulte du chiffrement de ce dernier à l'aide d'outils cryptographiques qui sont propres à chaque banque et tenus secrets. De tels outils peuvent être constitués d'un algorithme qui appliqué à N donne C (analogue à l' 20 algorithme de LUHN par exemple, mais secret ) , ou d'un algorithme et d'une clé de chiffrement pour chiffrer N à l'aide de la clé. L'authentification de la carte de paiement de l'acheteur (c'est à dire le fait pour le vendeur d'être certain que la carte a bien été délivrée par la banque de l'acheteur dans laquelle ce dernier a bien un compte , fait qui garantit le paiement ) est alors menée de la manière suivante : le vendeur , à qui la 25 banque a délivré l'accès à un moyen de calcul , ou éventuellement l' autorité vérificatrice vers laquelle est redirigée l'autorisation de paiement, calcule le chiffre du numéro de carte N . S'il retrouve par ce chiffrement le cryptogramme C cela prouve que la carte est authentique , c'est à dire qu'elle a bien été délivrée par la banque émettrice de la carte , car seule cette dernière détient les outils cryptographiques qui ont permis de construire le couple (N,C) . 30 Schématiquement , si l'on appelle f l'algorithme de chiffrement , le vérificateur vérifie que f(N) = C. Si une clé secrète k est utilisée , si f(N,k) = C. Les méthodes cryptographiques utilisées par les banques sont tenues secrètes. Dans ce protocole d'identification le cryptogramme est donc calculé à partir du numéro de carte N et dépend donc de celui-ci. 2°)- 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 5 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 10 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. Les procédés de cryptographie qui vont être décrits ci-après sont des procédés d'authentification de 15 carte bancaire spécifiques à ces deux types de paiement à distance. III)-Exposé de l'invention L'invention concerne les deux types d'authentification de cartes bancaires décrits ci-dessus au paragraphe concernant la technique antérieure . Ces deux types d'authentification dans l'invention utilisent les mêmes techniques cryptographiques et sont à considérer comme deux inventions liées 20 par un même concept inventif général. La présente invention a pour caractéristique , lors du paiement par internet , que le cryptogramme qu'on appellera désormais identifiant et qu'on notera « j » : - ne soit plus calculé à partir du numéro de carte N mais au contraire que N dépende de ( du moins pour la partie du numéro de carte ne correspondant pas aux chiffres identifiant le type 25 de carte et la banque). - puisse être choisi de manière aléatoire et puisse être par exemple le code secret du détenteur de la carte (code « PIN » à quatre chiffres). Pouvant être le code secret de l'utilisateur de la carte cela permet que l'identifiant « j » ne soit plus écrit sur la carte de l'utilisateur. Ce qui permet qu'un tiers qui serait en possession de la carte ne puisse pas s'en servir pour un 30 paiement par internet. Concernant le paiement à distance à un TPE chez un commerçant 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 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 35 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 l'objet de la section A de la présente partie III. La section B sera consacrée à l'utilisation et 40 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. 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 S. 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 10 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. 15 - pn est la bijection p 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 20 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 ) 25 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 30 p(4) = 1 19(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 C1 = (1754) , puisque p(1) = 7 ,p2(1) = 5 ,p3(1) = 4 , puisqu'en effet : P2(1) = (P(P(1)) =p(7) = 5 p3(1) =p(5) = 4 p4(1) = p(4) = 1 Pour i = 2 , on a de même C2 = ( 26398) 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 sont de 15 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 suite : 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 147->594-> 1 2->64349-3842 Le premier élément d'un cycle donné peut par ailleurs être n'importe quel élément de ce cycle. Ainsi le cycle 2->64349->8->2 peut s'écrire 3->9-->842 46->3. 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 : 10 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 110 000 ) 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,19..) représentent des numéros d'ordre pour les suites de n premiers entiers. 001 111 101 011 100 110 000 019 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 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 bijection possède deux cycles (disjoints) de longueur respective 5 et 3 et qui sont : C1= ( 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 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) : CI= p°(001) = 001 C2= p°(111) =111 p1(001)= 000 p1(111) = 010 p2(001) = 100 p2(111) = 011 p3(001) = 001 p3(111) = 110 p4(111) =101 p5(111) = 111 35 § 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ù p1 =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. pi 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 , . . . . , pa } , 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 = pr 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 .pi , pal générés par une bijection (permutation) p, sont donc simplement les ensembles : =P p2 = pop p3=popop pi =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 5 exemples peuvent être utiles pour comprendre l'invention. Exemple 1 000000000 Soit S = ( 7 6 9 1 4 3 5 2 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 ): 147454441 24643494842 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 000000000 p= ( 7 6 9 1 4 3 5 2 8 ) p2= (5 38 71 9 46 2) p3= (4 92 57 8 13 6) p4= ( 1 8 6 4 5 2 7 9 3 ) 20 p5= (7 23 14 6 58 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 14 2 59 3) 25 p10 = ( 5 23 71 6 4 8 9) pl 1 = ( 4 69 57 3 12 8) p12 = ( 1 38 45 9 76 2) p13 = ( 7 9 2 1 4 8 53 6) p14 = ( 5 8 6 7 1 2 4 9 3 ) 30 p15 = ( 4 2 3 5 7 6 1 8 9 ) p16 = ( 1 69 45 3 72 8) P17= p18 = ( 7 3 8 1 4 9 5 6 2 ) ( 5 92 71 8 4 3 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 : p21(1) p( p20(1)) = p(1) = 7 , -21 p (2) = p( p2°(2)) = 6 , etc , on calcule ainsi la suite p primitive 2 8) génératrice qui est S= ( 7 6 9 1 4 3 5 Et donc p21 = p1 , p22 = p2 1923 = p3 , 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 01 Ô ) La bijection associée à la permutation S est donc : p(001) = 000 p(111)=010 p(101)=111 15 p(011) = 110 p(100) = 001 p(110)=101 p(000) = 100 p(010) = 011 20 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. 25 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 9 000 101 110 010 001 011 100 111 = p4 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 = 100 110 011 111 000 010 001 101 = p8 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 = p1' 001 011 010 101 100 111 000 110 = p12 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 = pis 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 15 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}" par exemple) .I1 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 20 différents deux à deux. Par exemple E peut être : {0011 , 00 , 11011 , 10110 , 11 , 0010 , 0000 , 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. 25 § 4-Calcul de pi dans G Calcul de pi dans G : une méthode de calcul appelée {Sa} -> Si , ou {p a} -> pi , ou encore plus simplement méthode « j » calcule la permutation pi de G. L'algorithme est le suivant : 1- Si i est le premier élément d'un des cycles C de S , alors pi(i) =Ai) , avec r = j mod L , L étant 30 la longueur du cycle C de i. 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 S une permutation d'un ensemble E. Se le groupe symétrique de E. Ch , Ci , Cm, les disjoints de S et w leur nombre. Si l'on prend un élément de chaque disjoint on forme un w-uplet qui appartient au produit cartésien Ch X Ci X X Cm . Il est démontré que :le nombre de w-uplets figurant dans les permutations appartenant au Sous-Groupe cyclique de Se généré par S est égal à a (a = ppcm des entiers représentant la longueur des 10 disjoints de S) . On donne simplement un exemple : Exemple : Soit la permutation S suivante de E = {1,2,3,4,5,6,7,8,9}muni de l'ordre standard des entiers: 000000000 15 S=(39 57 84 61 2) Les disjoints de S sont au nombre de 3 (donc w = 3) sont : Ci - (1 3 5 8) , de longueur LI = 4 C2 = (2 9 2) , de longueur L2 = 2 C4 = (4 7 6 ) , de longueur L4 = 3 20 Le ppcm des entiers représentant la longueur des cycles de S est ppcm{4,2,3} = 12. Le sous-groupe cyclique G de Se généré par S est reproduit ci-après : 00 0 00 0 0 0 S= ( 3, 9 5 7 8 4 6 1 2) S2 = (5 2 8 fi 1 7 4 3 9)=SoS 25 S3 = (8 9 1 4 3 6 7 5 2)=SoSoS,etc, S4 = d 2 3 7 5 4 6 8 9) S5 ( § 5 6 8 7 4 1 2) S6 2 8 4 1 6 7 3 9) S7 = iM 9 1 2 3 4 6 5 2) 30 S8 = 1 2 3 5 7 4 8 9) S9 = 3 9 5 4 8 6 7 1 2) 4 6 3 9) 3 7 4 5 2) 6 7 8 9) Sl°= (5 S"= ($ 9 Sl2= 11 On constate ainsi que les éléments du premier cycle (disjoint) Ci : 3 , 5 , 8 , 1 , reviennent de 5 manière cyclique dans la colonne 0. De même pour les éléments du cycle C2 qui reviennent en boucle dans la colonne et pour les éléments du cycle C4 qui reviennent dans la colonne 0. Dans chaque permutation appartenant à G figure un triplet appartenant au produit cartésien des disjoints Ci ,C2 , Ca. Ces triplets sont des w-uplets avec ici w = 3. 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 3 9 7 5 2 7 5 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 deux à deux. Puisque le nombre de w-uplets est égal à a (a = ppcm des entiers représentant la longueur des disjoints de S) il en résulte que quand ces entiers n'ont pas de diviseur commun l'ensemble des wuplets figurant dans les permutations composant G est égal au produit cartésien des disjoints de S. § 6- Couples de solutions d'une composition de deux bijections où les deux composantes sont 30 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 Exemple : Soit p la bijection suivante de {1,2,3} dans {1,2,3} muni de l'ordre standard des entiers naturels (on 35 la donne sous forme de suite S) : S = (2 3 1) 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) (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 fo g= 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 o g=f 30 pouvant être considérée comme une division de f par g (division à droite , la division à gauche s'exprimant par g o x =f). 10 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 numéros d'authentification ou les clés de chiffrement à partir d'une clé secrète uniquement détenue uniquement par elle. L'authentification se fait ensuite toujours auprès de cette entité ou auprès d'un tiers à qui est délivré l'accès à un moyen technique de vérification. Paiement par internet: La banque ou l'entité vérificatrice qui fabrique les numéros d'authentification choisit: - un ensemble E de grand ordre (cardinal), composé de symboles ou blocs de symboles. - une permutation p appartenant à Se composée de nombreux disjoints dont les longueurs n'ont pas de diviseur commun (on note w le nombre de disjoints) ; si p est par exemple une permutation de 132 symboles ou blocs de symboles comportant neuf disjoints de longueur respective 13, 11 , 8 , 7 , 9 , 17 , 19 , 23 , 25 , alors le sous-groupe cyclique G engendré par p comportera : 13 x 11 x 8 x 7 x 9x 17 x 19 x 23 x 25 = 13 385 572 200 permutations différentes , c'est à dire 13 385 572 200 w-uplets différents (voir section A , § 5 pour la définition de la notion de w-uplet). - un w-uplet de p . Chacun des éléments du w-uplet est par ailleurs posé comme premier élément du disjoint (cycle) auquel il appartient (les premiers éléments de chaque disjoint sont choisis de manière aléatoire par l'entité vérificatrice dans chaque disjoint ) E, Se , et le w-uplet d'éléments de E : w = ( ,i2'iw) , constituent la clé secrète , qui est détenue uniquement par l'entité qui fabrique les numéros d'authentification . On appelle ces trois données « clé-mère » car c'est à partir de ces données que vont être construits tous les couples d'authentifiants (N,j) qui seront attribués aux cartes (on rappelle que j est l'entier qui remplace le cryptogramme visuel et qui est le code PIN de l'utilisateur). Ces couples sont construits de la manière suivante: Soit une carte bancaire CB à doter de couples d'authentifiants. La banque choisit : - un entier j choisi de manière aléatoire (mais au format code PIN , donc quatre chiffres) - puis calcule le w-uplet : N = (pi( h) , h) ,.... i,v) ) qui est une suite de symboles ou blocs de symboles de E. La suite N , éventuellement concaténée , est apposée sur la carte et constitue le numéro de carte . Le couple (N,j) est le couple d'authentifiants attribué à la carte CB par la banque . N est est inscrit sur la carte, j est le code secret à quatre chiffre de l'utilisateur. Ensuite lors d'un paiement par internet l'utilisateur entre son numéro de carte N qui figure écrit sur cette dernière ainsi que son code secret j , en conséquence non écrit sur la carte . Le moyen de calcul auquel a accès le vendeur , qui est délivré par la banque ou l'autorité vérificatrice qui détient les composants de la clé-mère secrète ,à savoir le w-uplet ( ,i2 'i,v) et la fonction p, calcule à partir de l'entier j donné par l'utilisateur les valeurs pi( , pi( h) ,.... pi( iw) , avec par exemple la première clause de l'algorithme « {pa } -> » , défini section A , § 4 ci- dessus. Si le calcul donne N , les données (N , j) fournies par l'utilisateur sont authentiques. Donc la carte est authentique (carte délivrée par la banque ou l'entité vérificatrice). Chaque carte délivrée par l'entité vérificatrice peut ainsi être dotée d'un couple d'authentifiants personnel . Pour chaque entier j inférieur à a , le couple (N , j ) est unique (voir section A , § 5) . N 10 est fonction de j et est un w-uplet unique appartenant au sous-groupe cyclique de permutations G. Notes : - si j est un nombre à quatre chiffres il n'existe en théorie que 10 000 possibilités pour j et donc pour N . Il est possible pour remédier à cet inconvénient de doter la carte d'un « complément » de code PIN , sous forme d'entier h choisi aléatoirement , écrit sur la carte , et par par lequel est par exemple 15 multiplié j pour calculer N. Les données d'authentification sont alors constituées du triplet (N , h , L'autorité vérificatrice calcule alors ph X i(ik) , pour chaque élément ik du w-uplet ( ,i2 'i.) afin de calculer le numéro de carte N . L'entier h est écrit sur la carte avec N et l'usager lors d'un paiement internet entre N , h puis son code secret j . 20 - alors que dans la technique existante les numéros identifiant la banque et le type de carte ainsi parfois que la date d'expiration de la carte font partie du numéro de carte N et sont chiffrés pour donner le cryptogramme , dans cette technique d'authentification qui fait l'objet de l'invention ces données ne font pas partie du numéro de carte N composante du couple d'authentifiants. Authentification à distance à un terminal électronique de paiement chez un commerçant: 25 Le principe est analogue au paiement internet. La banque où l'entité centrale qui fabrique et attribue les cartes bancaires choisit une clé-mère toujours constituée de : - un ensemble 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 , 30 - 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 : 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 'i.) qui est constitué des premiers éléments de chaque cycle de p. 35 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,p') qui est unique et donc 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 x h,. (ik) pour chaque ik de w. La valeur obtenue y est une suite de symboles ou blocs de symboles de E. 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 ik 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é 10 vérificatrice. Avec cette méthode le centre de contrôle n'a pas à connaître et stocker les clés secrètes de 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 ( il ,i2'iw) peut ne pas faire partie de la clé secrète k 15 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 X d'éléments de E . Dans ce cas la clé secrète k de chaque 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, X) , X pouvant être choisi aléatoirement par le centre de contrôle et ne pas être constitué des premiers éléments de 20 chaque cycle. IV-Exemple de mode de réalisation de l'invention. 1)-Paiement par internet Soit E = {1,2,3, ,132} l'ensemble des 132 premiers entiers naturels. Se le groupe symétrique de E. 25 Soit S une permutation appartenant à Se . p la fonction bijective associée à S L'entité vérificatrice choisit S telle que S ait pour disjoints (cycles) : (83 121 20 41 7 45 30 1 53 15 72 61 111) (74 82 84 28 2 34 94 99 117 47 57) 30 (51 56 132 89 131 130 3 129) (19 38 50 29 116 128 4) (97 65 5 22 79 93 101 59 76) 16 88 124 87 127 105 6 55 35 81 66 86 107 60 90 13 43) 100 42 102 58 44 54 17 8 36 33 122 78 11 49 95 113 68 75) 96 112 119 77 69 26 37 80 64 115 9 39 52 27 18 125 108 73 63 114 10 (21 103 110 92 106 12 23 48 32 62 71 85 123 67 91 104 16 24 98 120 31 14 46 126 118) Ces neuf cycles sont de longueur 13, 11 , 8 , 7 , 9 , 17 , 19 , 23 , 25. Ces nombres entiers n'ayant pas de diviseur commun la permutation S engendre donc un sous-groupe cyclique de Se d'ordre (cardinal) :13 x 11 x 8x7x 9x 17 x 19 x 23 x 25 = 13 385 572 200 , qui est le nombre de numéros de carte possible. Ces neuf disjoints sont choisis de manière secrète et aléatoire (hormis leurs longueurs , qui doivent de préférence être telles que les nombres entiers qui représentent ces longueurs n'aient pas de diviseur commun , ceci afin de générer un sous-groupe cyclique G de Se de grand cardinal) , de même que le premier élément de ceux-ci. L'ordre dans lequel ils sont pris est aussi aléatoire et secret. Le nombre de disjoints ainsi que leurs longueurs peut être appelé structure cyclique de la permutation. Ici w est : w = (83 74 51 19 97 25 70 40 21) La clé-mère secrète détenue par la banque ou l'entité vérificatrice est donc le triplet (E, S, w) , ou bien en notant S par sa fonction bijective associée p , le triplet (E, p , w) , avec p exprimée sous sous forme de puissances pour le premier élément i de chaque disjoint . Les neuf disjoints (cycles) 20 de p , notés C1 ,C2 , C3 , C4 , C5 , C6 , C7 C8 , C9 , sont ainsi: CI= 83 C2= C3= p°(83) = 121 pc)(74) = 74 p°(51) = 51 pl(51)= 56 p1(83) = pl(74) = 82 p2(83) = 20 p2(74) = 84 p2(51) = 132 25 p3(83) = 41 p3(74) = 28 p3(51) = 89 p4(83) = 7 p4(74) = 2 p4(51) = 131 p5(83) = 45 p5(74) = 34 p5(51) = 130 p6(83) = 30 p6(74) = 94 p6(51) = 3 p7(83) = 1 p7(74) = 99 p7(51) = 129 30 p8(83) = 53 p8(74) = 117 p8(51) = 51 p9(83) = 15 p9(74) = 47 p10(83) = 72 pi o(74) = 57 p 1 1(83) = 61 p 11(74) =74 p12(83) = 111 35 /913(83) = 83 (25 (70 (40 109 ) C4= C5= C6= 17 C7= p°(19) = 19 p°(97) = 97 p°(25) = 25 p°(70) = 70 pl(19) = 38 p'(97) = 65 p'(25) = 88 p'(70) = 100 p2(19) = 50 p2(97) = 5 p2(25) = 124 p2(70) = 42 p3(19) = 29 p3(97) = 22 p3(25) = 87 p3(70) = 102 p4(19) = 116 p4(97) = 79 p4(25) = 127 p4(70) = 58 p5(19) = 128 p5(97) = 93 p5(25) = 105 p5(70) = 44 /96(19) = 4 p6(97) = 101 p6(25) = 6 p6(70) = 54 p7(19) = 19 p7(97) = 59 p7(25) = 55 p7(70) = 17 p8(97) = 76 p8(25) = 35 p8(70) = 8 p9(97) = 97 p9(25) = 81 p9(70) = 36 pl °(25) = 66 pi 0(70) = 33 p"(25) 1(25) = 86 pl 1(70) = 122 p12(25) = 107 p 12(70) , 78 p13(25) = 60 p13(70) = 11 1,14(25) = 90 p' 4(70) = 49 p15(25) = 13 p15(70) = 95 p16(25) = 43 p16(70) = 113 p17(25) = 25 p17(70) = 68 p18(70) = 75 p19(70) = 70 G= c9= 18 p°(40) = 40 pl (40) = 96 p2(40)= 112 p3(40)= 119 p4(40) = 77 p5(40)= 69 p6(40) = 26 p7(40)= 37 p8(40)= 80 p9(40)= 64 p"(40)= 115 p11(40)= 9 p12(40)= 39 p13(40)= 52 p14(40)= 27 p15(40)= 18 /916(40)- 125 /917(40) = 108 pl 8(40) = 73 p19(40)= 63 p2°(40)= 114 p21(40)= 10 p22(40)= 109 p23(40)= 40 p°(21)=21 p1(21)= 103 p2(21)= 110 p3(21) = 92 p4(21)= 106 p5(21)= 12 p6(21)= 23 p7(21)= 48 p8(21)= 32 p9(21) = 62 p10(21)=71 /911(21) = 85 p12(21)= 123 p13(21)= 67 p14(21)= 91 p'5(21)= 104 p16(21)= 16 /917(21) = 24 p18(21)= 98 p19(21)= 120 p20(21) = 31 p21(21)= 14 p22(21)= 46 p23(21)= 126 p24(21)= 118 p25(21) = 21 Dès lors soit une carte bancaire à doter d'un couple d'authentifiants (N, j) pour un paiement sur internet tel que décrit en partie III. L'entité centrale vérificatrice choisit deux entiers aléatoires h et 30 j, par exemple h = 2133 et j = 7515 puis calcule h x j = 16029495. Elle calcule alors pour chaque i de w = (83 74 51 19 97 25 70 40 21) la valeur p 1 60 29 49 5 (i) avec l'algorithme {pa} -> pi (voir partie III , section A § 4) . Ainsi p16029495(83) = p1(83) , puisque 1 = 16029495 mod 13 , le cycle auquel appartient 83 étant de 35 longueur 13. pl(83) = 121 (cf cycle Ci , cycle de 83). De même elle calcule : p16029495 (74) = p9(74) , puisque 9 = 16029495 mod 11 , le cycle auquel appartient 74 étant de longueur 11. p9(74) = 47 p16029495(51) = p7(51) , puisque 7 = 16029495mod 8 , le cycle auquel appartient 51 étant de longueur 8. p7(51)= 129 p16029495(19) -= - p6/ 09) , puisque 6 = 16029495mod 7 , le cycle auquel appartient 19 étant de longueur 7. p6(19) = 4 p16029495(97) = p°(97) , puisque 0 = 16029495mod 9 , le cycle auquel appartient 97 étant de longueur 9. p°(97) = 97 p16029495(25) = p8(25) , puisque 8 = 16029495mod 17 , le cycle auquel appartient 25 étant de longueur 17. p8(25) = 35 p16029495(70) =- -12 p (70) , puisque 12 = 16029495mod 19 , le cycle auquel appartient 70 étant de longueur 19. p12(70) = 78 p16029495(40) = p13(40) , puisque 13 = 16029495mod 23 , le cycle auquel appartient 40 étant de longueur 23 . p13(40) = 52 p16029495(21)= p20(21) , puisque 20 = 16029495mod 25 , le cycle auquel appartient 21 étant de longueur 25 . p20(21) = 31 Elle obtient donc la suite d'entiers N suivante : 121 47 129 4 97 35 78 52 31 Sous forme concaténée N = 1214712949735785231 Elle dote alors la carte des authentifiants (N , h , j) avec : N = 1214712949735785231 h = 2133 j = 7515 Les nombres N et h sont écrits sur la carte, j n'est pas écrit et constitue le code secret à quatre chiffres de l'utilisateur de la carte. Lors d'un paiement par internet l'utilisateur entre les deux numéros N et h , ainsi que son code secret j. L'autorité vérificatrice où le vendeur à qui est mis à disposition un moyen de calcul utilisant les 5 outils cryptographiques secrets calcule alors à l'aide des données entrées par l'utilisateur la valeur p 1 6 0 2 9 4 9 5(i) pour chaque i de w . Si elle retrouve N cela prouve que la carte est authentique. Chaque carte bancaire peut ainsi être doté de numéros d'authentification pour un paiement par internet qui lui sont propres. Dans notre exemple 13 385 572 200 possibilités existent pour N Autre exemple: 10 Soit E l'ensemble des 56 n-uplets de bits suivants , choisis aléatoirement : E ={ 00110110010 , 10100 , 1110 , 11011 , 011110 , 0011 , 1011000 , 111 , 00100, 101000, 010101111 , 01010101 , 1011 , 001110 , 1011000 , 011011 , 1 , 10001000 , 01011101 , 10 , 011 , 011011110, 11 , 0110100 , 0001 , 01110111 , 000, 0101110, 01000100, 0101 , 1001, 10010011 , 11000 , 00011 , 01001 , 011010110 , 100101 , 0111001001 , 01110 , 0100 , 001101100 , 110101 , 1000 , 110011 , 110 , 00101 , 11001 , 0010100 , 011100 , 101 , 01010 , 1100 , 101000100 ,0, 001100 , 010100010 } (Le cardinal de E peut être choisi plus grand mais pour des raisons pratiques de calcul on se limite ici à 56 n-uplets de bits. Si la clé-mère est définie sur un ensemble de 132 n-uplets de bits avec la même structure cyclique que dans le premier exemple Se sera composé de 13 385 572 200 20 permutations de n-uplets de bits). Se est l'ensemble des permutations de E. Une permutation p appartenant à Se comportant plusieurs disjoints est alors choisie de manière aléatoire par la banque ou l'entité centrale (on prend ici pour p quatre disjoints de longueur 11 , 13 , 15 et 17). 25 Soit C1 , C2 , C3 , C4 ces quatre disjoints (le premier élément de chaque disjoint est aussi choisi aléatoirement) : CI = (01001 011010110 100101 110 11001 1011 001110 10001000 01011101 10 011 ) C2= ( 011011110 11 0110100 0001 01110111 000 0101110 01000100 0101 1001 10010011 11000 00011) 30 C3= ( 1011000 011011 1 1110 11011 011110 0111001001 01110 0100 001101100 110011 0010100 011100 101 01010 ) C4=(0011 00100 101000 010101111 01010101 00110110010 10100 1100 101000100 0 110101 1000 001100 010100010 1011000 111 00101 ) Exprimés sous forme de « puissances » de la fonction p pour le premier élément (élément de base ) 35 de chaque cycle ces disjoints sont: 15 C1 = 21 C3 = C2 = "01001) = 01001 "011011110) = 011011110 "1011000) = 1011000 p1(01001) = 011010110 pl(011011110) = 11 p1(1011000) = 011011 p2(01001) = 100101 p2(011011110) = 0110100 p2(1011000) = 1 p3(01001) = 110 p3(011011110) = 0001 p3(1011000) = 1110 "01001) = 11001 "011011110) = 01110111 "1011000) = 11011 p5(01001) = 1011 p5(011011110) = 000 p5(1011000) = 011110 "01001) = 001110 "011011110) = 0101110 "1011000) = 0111001001 p7(01001) = 10001000 "011011110) = 01000100 "1011000) = 01110 p8(01001) = 01011101 p8(011011110) = 0101 p8(1011000) = 0100 "01001) = 10 "011011110) = 1001 p9(1011000) = 001101100 p19(01001) = 011 p19(011011110) = 10010011 p19(1011000) = 110011 p11(01001) = 01001 p 1 1(011011110) = 11000 p 1 1(1011000) = 0010100 p12(011011110) = 00011 p12(1011000) = 011100 p13(011011110) = 011011110 p13(1011000) = 101 p14(1011000) = 01010 p15(1011000) = 1011000 C4 = "0011) = 0011 p1(0011) = 00100 p2(0011) = 101000 p3(0011) = 010101111 "0011) = 01010101 p5(0011) = 00110110010 "0011) = 10100 "0011) = 1100 p8(0011) = 101000100 "0011) = 0 p19(0011) = 110101 p11(0011) = 1000 p12(0011) = 001100 p13(0011) = 010100010 p14(0011) = 1011000 p15(0011) = 111 p18(0011) = 00101 p17(0011) = 0011 Ces quatre cycles sont de longueur respective 11,13,15,17 et génèrent donc un sous-groupe cyclique de Se d'ordre 11 x 13 x 15 x 17 = 36465 permutations. Soit h = 4278 Soit j = 8235 8235 x 4278 = 35229330 w = ( 01001 011011110 1011000 0011 ) L'entité ou la banque qui attribue aux cartes les authentifiants calcule donc : p 35229330(01001) =p4(01001) , car 4 = 35229330mod 11, 01001 étant l'élément de base du cycle C1 de longueur 11. p4(01001)= 11001 p 35 22933° (011011110) =p6(011011110) , car 6 = 35229330mod 13, 011011110 étant l'élément de base du cycle C2 de longueur 13. p6(011011110) = 0101110 p 35 2 29 3"(1011000) =p°(1011000) , car 0 = 35229330mod 15, 1011000 étant l'élément de base du cycle C3 de longueur 15. p°(1011000) = 1011000 p35229330(0011) =p9(0011) , car 9 = 35229330mod 17, 0011 étant l'élément de base du cycle Code longueur 17. p9(0011)=0 En concaténant les quatre valeurs obtenues on obtient :11001010111010110000 Puis converti en décimal on obtient 831152 Les identifiants apposés sur la carte bancaire sont donc : h = 4278 N = 831152 j = 8235 est le code secret de l'utilisateur 2)-Authentification à un terminal électronique de paiement Dans ce cas de figure , 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 même manière que pour l'authentification par internet. Puis dans un second temps elle fabrique les couples de clés « publique/privée » pour les attribuer à chaque carte. C'est cette deuxième phase qui va être décrite ci-après avec un exemple. 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 aussi un ensemble E composé de n-uplets des raisons pratique de calcul on choisit E composé uniquement de p sont choisis de longueur 5 , 6 et 7. Soit E = {0011 , 001 , 11011 , 10110 , 11 , 0010 , 0000 , 1100 01111 , 01001 , 100110 , 10010 , 110101 , 00100} Les disjoints (cycles) de p sont : (1100 01111 0010 10010 11) (010001 001 0011 100110 110101 00100) (110111 11011 10110 01001 00001 0110 0000) de bits choisis aléatoirement. Pour de 18 n-uplets de bits. Les disjoints , 00001 , 010001 , 110111 , 0110 , Exprimés sous forme de « puissances » de la fonction p , ces cycles sont : C1 = c2 = C3= p6(1100) = 1100 p6(010001) = 010001 "110111) = 110111 p1(1100) = 01111 p1(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 p5(1100) = 1100 p5(010001) = 00100 p5(110111) = 0110 p6(010001) = 010001 p6(110111) = 0000 p7(110111) = 110111 25 C'est à partir de cette clé-mère que la banque attribue les couples de clés « publique/privée » de la manière exposée en partie III. 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 30 forme de « puissances » d'une bijection afin de pouvoir utiliser par exemple l'algorithme {pa} pi pour les calculs lors de l'authentification.20 Sur le plan du calcul de la clé pi : le calcul de pi peut être fait en choisissant un ordre (relation d'ordre) sur E puis en calculant pi(i) 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 5 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). 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 10 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 p7292Q)7292(p7292(i))) , etc , jusqu'à ce que la valeur obtenue soit i . Le cycle est alors achevé. Ainsi pour i = 1100 , premier élément du cycle Ci de p, de longueur 5 , on calcule : 15 p7292(1100) =p2(1100) , car 2 = 7292 mod 5 p2(1100) = 0010 , voir cycle Ci. On doit ensuite calculerp7292(197292(1100-\ )) , c'est à dire p7292(0010) , p7292(0010) =p2(0010) =p4(1100) , puisque 0010 =p2(1100) p4(1100) = 11 , voir cycle C1. 20 De même on calcule les valeurs qui suivent : p7292(11) ...-122(11) =p6(1100) =p l(1100) (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 25 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 k1(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 15 dans le cycle qui vient d'être calculé C'est ici 001 . On calcule donc ensuite le cycle dei = 001. Au final on peut vérifier que la clé privée k = p7292 attribuée à la carte est composée des quatre cycles suivants: KI = K2 = K3 = K4 -= k°(1100) = 1100 k°(010001) = 010001 k°(001) = 001 k°(110111) = 110111 20 k1(1100) = 0010 k1(010001)= 0011 k1(001) = 100110 k1(110111) = 0110 k2(1100)=11 k2(010001) = 110101 k2(001) = 00100 k2(110111) = 01001 k3(1100) = 01111 k3(010001) = 010001 k3(001) = 001 k3(110111) =11011 k4(1100) = 10010 k4(110111) = 0000 k5(1100) = 1100 k5(110111) = 00001 25 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. Lors d'une authentification à distance le centre de contrôle envoie par exemple à la carte un n-uplet X 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 : k4589(11) = q4(q2(1100)) = q6(1100)= q1(1100) = 0010 0589(00001) = q4(00001)= q4(q5(110111))=89(110111)=82(110111)= 01001 0589(100110) = q2(100110) = q2(q1 (001)) = q3(001) = 001 0589(10110) = 84(10110) =q4(q6(110111))= q19(110111)=q3(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 calcule (à l'aide la la permutation p qu'il détient et qui est la clé-mère): p4589 X 7292(11) =p33462988(11 ) = p3(11) , puisque le cycle Cade 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 de même : p4589 X 7292(00001) =p33462988(00001) = p6(00001) = p6(p4(110111)) =p10( 110111) = p3( 110111) = 01001 P4589 X 7292(100110) =P33462988(100110) = p4(100110)= p4(p3(010001)) =p7( 010001 )- 20 191(010001 ) = 001 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. 25 V-Autre mode de réalisation Concernant la sécurité , le point important des procédés ci-dessus décrits est qu'il doit être impossible de retrouver la clé-mère à partir du numéro de carte N et du code secret , ou dans le cas de l'authentification à un terminal électronique de paiement qu'il 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 30 fausses cartes pourraient être conçues par un faussaire. Dans le cas du paiement par internet il n'est pas possible de retrouver la clé-mère à partir de N , j et h . La concaténation de N pose déjà une difficulté pour retrouver chaque valeur phxj(i) , notamment - si E est défini à partir de n-uplets de bits choisis aléatoirement. Même si chaque valeur ph x (1) était connue cependant l'analyste n'obtient comme seule information que le nombre de cycles de p et un 5 élément de chaque cycle , élément qui est pind(i) . Ces données ne lui permettent pas de retrouver la clé-mère. L'analyste ignore en effet la longueur de chaque cycle et le premier élément i de chaque cycle , données qui sont secrètes. 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 10 ailleurs même connaissant j et pi il n'est pas possible de retrouver p si l'ordre (relation d'ordre) sur E est inconnu , cela sauf recherche exhaustive sur toutes les possibilités possibles pour p en testant pour chacune de ces possibilités si k = pi (si l'ordre sur E est connu il peut être possible de retrouver pi à partir de j de manière méthodique par un algorithme de calcul). On ne démontre pas ces données concernant la sécurité. 15 Malgré ces garanties de sécurité on va exposer rapidement ci-après une autre méthode pour fabriquer des authentifiants pour le paiement sur internet ou 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 20 Pour le paiement internet: Le principe est de choisir non plus une clé-mère sous forme de permutation d'un ensemble E mais deux permutations notées p et q , et de calculer un n-uplet de la fonction (pi o qui est la fonction composée pi o à partir de p et q , l'entité qui fabrique et attribue les authentifiants calcule à partir de l'entier j de quatre chiffres , choisi aléatoirement , et d'un w-uplet ( ,i2, 'ive) de p (ou de 25 q) la suite N = ( qi(pi(iI)) , qi(pi(i2)) 'qi(pkiw)) . N est l'authentifiant écrit sur la carte , j le code secret de l'utilisateur. Pour le paiement à un terminal électronique: De la même manière 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 o Ti) appartenant à Se . La 30 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= Cep= Cap= p°(3) = 3 p1(3) = 7 p2(3) = 11 P3(3) = 3 po(5) = 5 191 (5) = 8 p2(5) = 6 p3(5) = 10 p4(5) = 9 P5(5) = 5 p°(2) = 2 p1(2) = 12 p2(2) = 1 p3(2) = 4 p4(2) = 2 Clq = C2q = 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 Dès lors pour attribuer un couple d'authentifiants à une carte , l'entité vérificatrice choisit un w-uplet de E ( les premiers éléments de chaque disjoint de p par exemple) et un entier de quatre chiffres choisi de manière aléatoire. Par exemple , soit w = ( 3 5 2) et j = 14 (pour simplifier les calculs on prend ici j avec deux chiffres au lieu de quatre) L'entité mère calcule dès lors : qi4(pi4(3))= qi4(p2,3, » car le cycle Cip de 3 pourp est de longueur 3 , donc 2 = 14mod 3 q' 4(p2(3)) = q14(11)= 14,w q 3(2)) , voir cycle C2q q14 (q3 (2)) = q17(2) = q2(2) = 12 De même : ql 4 (pl 4 (5)) = ql 4 (p4 (5)) = ql 4 (9) = q°(9) = 9 ql 4 (pl 4 (2)) = ql 4 (p2 (2)) = -1 4 ( ) q°(1) = 1 Donc N = 1291 et j = 14 Dans le cas l'authentification à distance lors d'une transaction à un TPE la banque ou le centre de contrôle , pour fabriquer la clé privée de chaque carte , calcule la fonction ( pi o qJ ) en entier. On peut vérifier en calculantiq 4(pi4(p, )) pour chaque i de E , que ( pi o q' ) est : (1 6 8 2) (3 12 4 5 9 10 11 7) Dès lors la permutation k telle que k = ( pi o ) est la clé privée de la carte (exprimée sous forme de « puissances » de la bijection k) , et j = 14 la clé publique. Choisir deux permutations différentes de E pour les composer permet d'améliorer la sécurité , notamment pour l'authentification à distance lors d'un paiement par TPE . En effet connaissant la permutation ( pi o ) ainsi que j l'analyste ne peut retrouver les clés-mères p et q que par une 15 recherche exhaustive sur l'ensemble Se des permutations de E en testant pour chaque couple (p , q) de permutations appartenant à Se si pi o = 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 20 A , § 6). Donc dans l'équation k = ( pi o ) , si k vient à être connu mais que pi et qJ 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 25 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. REVENDICATIONS1 - Procédé cryptographique d'authentification de carte bancaire lors d'un paiement par internet dans lequel l'acheteur communique un numéro de carte N et un cryptogramme C qui résulte du chiffrement de N avec des outils cryptographiques secrets , notamment par exemple une clé secrète 5 de chiffrement , outils détenus par l'autorité ayant délivré la carte bancaire , et dans lequel le vendeur à qui a été délivré par cette dernière un moyen de calcul pour chiffrer N vérifie que le couple (N,C) est cohérent , c'est à dire que le chiffre de N est C , d'où il résulte , si la réponse est positive que la carte est authentique , caractérisé : - en ce que le cryptogramme C n'est plus inscrit sur la carte et ne résulte plus du chiffrement du 10 numéro de carte N , mais est constitué par le code secret à quatre chiffres du détenteur de la carte , appelé usuellement code PIN et noté ici « j » , lequel est choisi de manière aléatoire pour chaque carte par l'autorité vérificatrice ; - en ce que la clé secrète de chiffrement détenue par l'autorité vérificatrice ayant fabriqué et attribué le couple d'authentifiants (N,C) est composée : 15 en premier lieu d'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 sa bijection p de E dans E , la permutation p spécialement choisie de manière à être composée d'un nombre de disjoints assez grand pour générer un sous-groupe cyclique G = {p,...pi,..., pal de Se de grand cardinal, a étant le ppcm des entiers représentant la longueurs des disjoints de p , lesquels disjoints dont le nombre est 20 noté w ont des longueurs n'ayant pas ou peu de diviseur commun afin que a soit très grand; en second lieu d'un w-uplet w = ( il ,i2,..,ik,...,i.) d'éléments de E spécialement choisi de manière à être un élément du produit cartésien des disjoints de la permutation p avec chaque ik premier élément du cycle Ck auquel il appartient; - en ce que le numéro ou authentifiant de carte N inscrit sur la carte bancaire sous forme de suite 25 de symboles est N = (Pi( ii) Iii( ik),..., pi( iw) ) , éventuellement concaténé , où la permutation pi est définie par popo ....o p , avec l'opération o de composition de fonction itérée j- 1 fois. Lors du paiement par internet l'acheteur donne alors N et son code secret j , l'autorité vérificatrice ou le vendeur à qui a été délivré un moyen de calcul délivrée par cette dernière vérifie que N et j sont cohérents , c'est à dire vérifie si N = (pi( il) , pi( i2),...,pi( ik),..., pi( i.)) . Si la réponse 30 est oui la carte est authentique car cela signifie que le couple (N , j) a été fabriqué et délivré par la banque ou l'autorité vérificatrice à partir de sa clé secrète constituée par le couple (p , w) qu'elle seule détient. Le numéro de carte N est donc alors authentifié par le code PIN du porteur de la carte. Le calcul de chaque élément pi( ik) de N étant fait avec avec la première clause de l'algorithme {pa} -> pi définie par : pkik) = pr(ik) , avec r j mod L , L étant la longueur du cycle C de ik . 35 2 - Procédé cryptographique d'authentification de carte bancaire lors d'un paiement par internet, selon revendication 1 , caractérisé en ce que la clé secrète détenue par l'autorité vérificatrice et servant à fabriquer les couples d'authentifiants (N , j) n'est plus constituée d'une seule permutation mais de deux permutations p et q , le numéro ou authentifiant de carte N étant alors N = ( qi(pJ(ii)) , qi(pki2)) 'qi(pki.)) .