ClickFR Reseau Publicitaire Francophone
Pour jouer au poker par correspondance, il faut dire à l'adversaire de choisir une carte parmi le tas sans révéler le contenu de ce tas. La solution consiste à utiliser soit un tiers insoupçonnable soit à la cryptographie, c'est cette dernière solution qui a été retenue ici.
Soit P un (grand) nombre premier congru à 3 modulo 8 par exemple
Soit M un nombre représentant un message. avec 0<M<P-1
Soit k la clé de codage (0 < k < P-1)
Soit C le message chiffré.
M ^ k = C [ P ]
Le signe ^ représente la puissance, les crochets indiquent que l'opération se fait modulo P (l'ensemble des nombres compris entre 0 et P-1 muni de la multiplicaton modulo P est un corps).
Pour déchiffer le message chiffré C, il trouver le nombre q tel que :
C ^q = M [ P ]
en fait il y a une relation simple entre k et q :
k x q = 1 [ P - 1] , il est facile de trouver q à partir de k (il suffit de faire une division euclidienne)
Le programme de poker par correspondance utilise un algorithme basé sur ces propriétés. La sécurité de l'algorithme repose sur le fait qu'il est diffcile d'inverser la fonction puissance si la clé k n'est pas connu.
L'algorithme de poker par correspondance diffère de l'algorithme RSA utilisé par PGP : pour le poker par correspondance, il faut un algorithme symétrique. Tands que dans l'algorithme RSA est asymétrique : il y a une clé publique et une clé privée, la base P utilisée n'est pas un nombre premier mais le produit de deux nombres premiers :
P = a * b
avec a et b deux grand nombres premiers.
P et k sont les clés publiques (connus de tous)
q est la clé privée.
Dans ce cas on a toujours
M ^ p = C [ P]
et C ^ q = M [ P ]
mais la relation entre p et q est la suivante :
p x q = 1 [ Phi (P) ]
avec Phi (P) = indicatrice d'Euler (P) = (a-1)*(b-1)
Pour pouvoir décrypter l'algorithme de chiffrement proposé par PGP, il faut donc disposer de a et b, ces deux entiers se déduisent de P (qui est public) par décomposition de P en facteurs premiers. Or il n'existe pas encore d'algorithme rapide de décomposition d'un nombre en facteurs premiers, il faut essayer tous les chiffres inférieurs à la racine de P.
remarque : pour un nombre premier a, Phi (a)= a-1.
plus généralement (programme Math Sup), si P=(a1^b1)*(a2^b2)*...*(aN^bN) (décomposition en facteurs premiers) avec a1..aN nombres premiers tous ddifférents alors :
Phi(P) = P * ( 1 - 1 / a1) * ( 1 - 1 / a2) * ... * ( 1 - 1 / aN)
l'algorithme RSA repose aussi sur le fait que la fonction puissance dans l'anneau (ce n'est plus un corps, la base P n'est pas un nombre premier) des nombres compris entre compris entre 0 et P -1 est difficilement inversible.
L'algorithme de poker par correspondance est donc aussi sûr que le R S A dès lors que l'on s'assure que la clé k n'est pas révélée. D'ailleurs plusieurs clés k sont générées aléatoirement à chaque tour de jeu. Il faut tout de même s'assurer que le générateur de nombre aléatoire est efficient.
L'algorithme R S A n'apportait rien de plus ici et ne pouvait être utilisé.
Il est par contre très efficace pour transmettre des messages chiffrés (schémas de confidentialité) ou pour signer un message (schéma de signature : on veut établir de façon certaine l'origine du message on code le message en clair avec la clé privée dans ce cas)
Une fois les principes cryptographiques établis, voici le protocole utilisé pour l'échange des cartes dans le programme de Poker par correspondance réalisé par Laurent Pelé en 1988 :
On a vu que M ^ a = C [P] et C ^ aa = M [P] si a * aa = P -1
l'idée de base du poker par correspondance est d'appliquer deux fois ce protocole :
Joueur A : T ^ a = X [ P ] ===> envoie au joueur B
Joueur B : X ^ b = Y [ P ] ===> envoie au joueur A
Joueur A : Y ^ aa = Z [ P ] ===> envoie au joueur B (aa est tel que quelque soit X, on ait (X ^ a ) ^ aa = X [ P ], il suffit a * aa = 1 [ P ], à partir de a et P, obtient " facilement " aa par divisions euclidienes successives jusqu'à ce que le quotient soit nul, ce qui permettra alors, en inversant ces divisions euclidiennes successives de résoudre l'équation de Bezout ! )
Joueur B : Z ^ bb = T [ P ] , le joueur B voit donc une carte en clair sans que le joueur A ne la connaisse !
Prenons par exemple comme base un petit nombre premier comme P = 9973 (juste pour l'exemple).
Maintenant, admettons que l'on utilise les règles suivantes du poker (il en existe plusieurs) : 3 distributions de 5 cartes, à chaque tour de jeu, les joueurs peuvent donc remettre dans le tas de 0 à 5 cartes. Chaque joueur ne peut donc redmander des cartes que deux fois maximum. Tous les joueurs savent combien de cartes ont été rendues par les autres joueurs (cela a une importance pour les paris).
Pour simplifier, le protocole n'est présenté que pour le cas du jeu avec 2 joueurs A et B.
Chacune des 32 cartes est symbolisée par un numéro compris entre 2 et P-1= 9972, supposons par exemple que ce numéro est de la forme 47+293*i avec i variant de 0 à 31. Ce codage des cartes n'a pas grande importance, sa prncipale fonction est d'assurer un identifiant unique pour chacune des cartes. Cette symbolisation est commune aux deux joueurs, elle n'est pas secrète.
Phase 1
Par exemple les cartes étaient dans l'ordre originel :
As de pic =====> 47 As de coeur ====> 340 As de trêfle ===> 633 As de carreau ==> 926 7 de pic =======> 1219 7 de coeur =====> 1512 ... Roi de carreau => 9130
Le premier joueur A mélange les cartes,
Elles sont alors par exemple dans l'ordre suivant :
1512 (7 de coeur) 4442 (9 de carreau) ... 633 (As de trêfle)
tire au hasard un code a1 tel que 1<a1<=P-1=9972 et envoie au joueur B les cartes codées avec ce code a1.
prenons par exemple a1=2 (pour simplifier), les cartes sont donc maintenant codées ansi :
1512 (7 de coeur) ^ 2 [9973] = 2327 +229*9973 = 327 4442 (9 de carreau) ^ 2 [9973] = 4770 +1978*9973 = 4770 ... 633 (As de trêfle) ^ 2 [9973] = 1769 + 9973*40 = 1769
Par mélange, on entend ici, que l'ordre de réception des cartes par le joueur B, n'est plus le classement originel des cartes, il est essentiel que ce mélange soit bien fait aléatoirement sinon le joueur B pourrait décoder le jeu plus facilement (même s'il n'existe pas d'algorithme plus rapide que d'essayer toutes les combinaisons de 1 à P-1 jusqu'à ce que l'on trouve un qui corresponde)
Lors de l'envoi, un code de redondance cyclique est envoyé, celui du minitel (7 bits de redondance cycliques pour 120 bits de données + 1 bit de parité est tout à fait satisfaisant : si il y a un seul bit de faux parmi les 128, on peut corriger l'erreur, si il y a deux bits de faux, on voit qu'il y a deux bits de faux et qu'il faut renvoyer le message, il existe mieux (avec un polynôme générateur binaire plus gros), mais ce n'est pas l'essentiel du programme.
Phase 2
Le joueur B reçoit donc les cartes codées par les chiffres suivants :
1512,4442,...,633
il commence par les mélanger, il choisit 5 cartes dans le jeu, et les chiffre à l'aide de deux clés b1 et b2, il utilise en effet des clés différentes pour les cartes qu'il a choisies et pour le tas.
Il chiffre les 5 cartes choisies (CHOIX Joueur B) avec b1 et les 27 autres cartes (TAS) avec b2 et renvoie le tout au joueur A.
Phase 3
Le joueur A reçoit deux groupes de cartes :
1- un groupe de 5 cartes (CHOIX joueur B) codées par a1 * b1
Il mélange ces 5 cartes (pour la forme) et les chiffre avec aa1,
elles sont donc chiffrées avec a1 * b1 * aa1 soit b1
2- un groupe de 27 cartes (TAS) formant le tas codées avec a1 * b2
Le joueur A mélange ces 27 cartes, en choisit 5.
Le joueur A génère alors deux nouvelles clés a2 et a3, il va coder les 5 cartes qu'il a choisi avec aa1 * a2 et les autres avec aa1 * a3 (on fait intervenir aa1 ici pour ne pas s'encombrer avec tropde vieilles clés).
il envoie donc à B 5 cartes (CHOIX Joueur A) codées avec a1 * b2 * aa1 * a2 soit b2 * a2
et 22 cartes (TAS) codées avec a1 * b2 * aa1 * a3 soit b2 * a3
Le code a1 ne servira plus.
Phase 4
Dans cette phase, le joueur B va enfin découvrir quelles sont les cartes qu'il a choisies !
Le joueur B génère en outre deux nouveaux codes b3 et b4, globalement, après cette phase, les cartes choisies seront codées avec b3 tandis que les autres seront codées avec b4.
Le joueur B reçoit 3 groupes de cartes :
1 - le groupe " CHOIX Joueur B " codées par a1 * b1 * aa1 soit b1,
il multiplie chacune des cartes par bb1, il obtient alors l'identifiant en clair de la carte (sous la forme 47 +293* i comme convenu)
Il voit ses cartes, il peut donc décider de celles qu'ils gardent et de celles qu'il rejette.
Supposons qu'il garde 3 cartes et en rejette 2 (il aurait pu faire autrement).
les 3 cartes que le joueur B garde appartiennent au groupe " CHOIX Joueur B "., elles seront codées avec le code b3 : a1 * b1* aa1 * bb1 * b3 = b3 (on aurait pu ne pas les chiffrer à nouveau, mais on ne souhaite pas trainer le code b1)
les deux cartes rejetées sont mises dans le groupe " REJET Joueur B ", elles seront codées aec le code b4 : a1 * b1 * aa1 * bb1 * b4 soit b4
2. Le Tas formé de 22 cartes codées par a1 * b2 * aa1 * a3 soit b2 * a3
De ces cartes, le joueur B en choisit deux (car il a rejeté deux cartes), elles sont mises dans le groupe " REPIOCHE Joueur B ", elles sont codées avec bb2 * b3 soit : b2 * a3 * bb2 * b3 = a3 * b3.
Les 20 autres cartes sont codées avec bb2 * b4 : b2 * a3 * bb2 * b4 = a3 * b4 et forment le groupe " TAS ".
3. Le " CHOIX Joueur A " est codé avec bb2 de telle sorte que le joueur A puisse les décrypter :
(a1 * b2 * aa1 * a2) * bb2 = (b2 * a2 * b2) = a2
A l'issue de cette phase, les codes b1 et b2 ne servent plus (pour ne pas compliquer l'algorithme)
Phase 5
Dans cette phase, le joueur A va découvrir les cartes qu'il a choisies. Il reçoit plusieurs groupes de cartes, deux nouveaux codes a4 et a5 sont générés (a4 pour les cartes gardées, a5 pour les cartes rejetées).
1. Le groupe " CHOIX Joueur B " codé par b3 reste inchangé.
2. Le groupe " REJET Joueur B " est codé par a5 (par défaut, le joueur A ne choisit pas immédiatement les cartes rejettées par B, il va ensuite rejoindre le groupe " Tas ", il s'ensuit que ces (deux) cartes sont codées par b4 * a5.
3. Le groupe " REPIOCHE Joueur B " comprenant 2 cartes est décrypté avec le code aa3 afin que le joueur B puisse les lire : a3 * b3 * aa3 = b3
4. Le groupe " Choix Joueur A " est décodé avec le code aa2.
Le joueur A voit donc ses cartes 5 cartes en clair, il peut décider de ce qu'il veut garder.
Supposons par exemple qu'il ne rejette qu'une carte, cette carte est mise dans le groupe " REJET Joueur A " et codées avec a5.
Les 4 autres cartes restent dans le groupe " CHOIX Joueur A " et sont codées avec a4.
5. Le tas est composé de 20 cartes codées avec le code a3 * b4, une carte est choisie parmi elles (pour remplacer la carte rejetée), cette carte est mise dans le groupe " REPIOCHE Joueur A " et est codée avec aa3 * a4 : ( a3 * b3 ) * aa3 * a4 = b3 * a4.
Les 19 autres cartes du tas sont codées avec le code aa3 * a5 : ( a3 * b3 ) * aa3 * a5 = b3 * a5.
A ces 19 cartes on ajoute les deux cartes du groupe " REJET Joueur B ", on n'oublie pas de les mélanger, le tas est ainsi codé par b3 * a5.
Phases suivantes :
Et ainsi de suite jusqu'à la phase 9 (les joueurs peuvent changer deux fois leur jeu) où les deux joueurs connaissent leur jeu définitif, il peuvent parier alors librement, phase ne nécessitant d'échange chiffrés. Pour vérifier les jeux, les joueurs annoncent leurs cartes et les derniers codes finals. En cas de litige, il peut être nécessaire de remonter l'algorithme à l'aide des codes intermédiaires.
Ce schéma résiste à l'attaque par intrusion, ou écoute, en fait, le joueur adverse n'a pas plus de chances de trouver le jeu de l'adversaire. La seule solution consiste à esayer toutes les combinaisons possibles.
De plus, comme de nouvelles clés sont générées aléatoirement à chaque tour de jeu, il faut à nouveau les trouver.
La loi 90-1170 du 29 décembre 1990 soumet à autorisation,
l'utilisation et l'exportation de toute prestation cryptographique.
Ce programme, bien que réalisé en 1988-89, serait soumis
à autorisation pour son utilisation en France.
Cependant, je pense que cette loi ne s'applique pas pour un tel logiciel
car il ne comporte pas de "convention secrète".
Voir ce que j'ai écrit dans Failles dans la loi française sur la crypto
Faire un dossier d'autorisation risquerait de prendre un peu de temps (surtout que je revois sérieusement le programme original (nouvelles fonctionalités : optimisation, possibilité de jouer à plus de deux et extension à tout jeu de cartes, interface graphique sous Windows, nouveau système de gestion de fichier, possibilité d'interfaçage avec l'Internet.
De plus, une fois le programme et le dossier finis, il n'est pas acquis que l'autorisation soit accordée vu la puissance de l'algorithme utilisé. Il va falloir que je prouve que le programme ne puisse pas être utilisé pour chiffrer des messages au lieu de jouer aux cartes. Mais je refuse tout compromis pour brider l'algorithme de chiffrement. Donc je pense qu'il est plus simple de se passer d'autorisation et de montrer que la loi ne s'applique pas en l'espèce en cas de pousuites.
Enfin, pour ceux qui s'inquiètent de la légalité du jeu de poker en France, je rappelle :
- d'une part que ce programme permet de jouer à d'autres jeu de cartes,
- d'autre part et surtout, que si dans le cas général, il est effectivement interdit de jouer au poker en France, même sans miser de l'argent, il est tout à fait autorisé de jouer au poker entre membres d'une même famille et de miser autant d'argent que les joueurs souhaitent dans ce dernier cas.
Suite à l'éclatement des familles, un tel programme est idéal pour ceux qui souhaitent s'adonner - par exemple entre cousins - à leur jeu préféré dans la plus grande légalité.