FR2811173A1

FR2811173A1 - Procedes cryptographiques a cle publique bases sur la difficulte de trouver les valeurs propres d'un endomorphisme d'un module sur un anneau ou une algebre quelconque

Info

Publication number: FR2811173A1
Application number: FR0100781A
Authority: FR
Inventors: Jean Francois Geneste
Original assignee: Individual
Current assignee: Individual
Priority date: 2000-06-28
Filing date: 2001-01-22
Publication date: 2002-01-04
Anticipated expiration: 2007-01-22
Also published as: WO2002001792A1; AU7067001A; FR2811173B3

Abstract

La présente invention concerne un procédé de cryptographie à clé publique, applicable à des données enregistrées sous forme de bits sur un support exploitable par une entité de calcul, lequel procédé, selon la façon dont il est utilisé peut fournir un procédé de chiffrement, un procédé de preuve d'identité zero-knowledge au sens de Fiat-Shamir, un procédé de signature de signature électronique ou un procédé réalisant une fonction dite à sens unique. Ce procédé de cryptographie à clé publique de données enregistrées sous forme de bits sur un support exploitable par une ou plusieurs unités de calcul aptes à traiter des données d'entrée x pour fournir des données de sortie x', comportant au moins une étape de traitement de données, se caractérise par le fait que la ou les unités de calcul manipulent des matrices carrées à coefficients dans un anneau ou une algèbre, commutatifs ou non, associatifs ou non, les données d'entrée étant considérées comme des vecteurs appartenant à des modules sur ces anneaux ou algèbres, la manipulation binaire amenant en sortie éventuellement une matrice carrée ou un vecteur ou un scalaire ou deux options parmi les trois ou les trois à la fois, les coefficients restant toujours sur les mêmes anneaux ou algèbres.

Description

Procédés cryptographiques à clé publique basés sur la difficulté de trouver les valeurs propres d'un endomorphisme d'un module sur un anneau ou une algèbre quelconque
La présente invention concerne un procédé de cryptographie à clé publique, applicable à des données enregistrées sous forme de bits sur un support exploitable par une entité de calcul, lequel procédé, selon la façon dont il est utilisé peut fournir un procédé de chiffrement, un procédé de preuve d'identité zero-knowledge au sens de Fiat-Shamir, un procédé de signature de signature électronique ou un procédé réalisant une fonction dite à sens unique.

Depuis le milieu des années 1970 de nombreux systèmes de cryptographie à clé publique sont apparus, notamment le RSA de Rivest Shamir et Adelman ainsi que le système d'échange publique de clé dit de Diffie-Hellmann. D'autres systèmes furent proposés, la grande majorité basée sur le problème de la factorisation. Peu sont basés sur d'autres problèmes mais je citerai ici ceux qui sont basés sur les courbes elliptiques ou hyper-elliptiques. Néanmoins, dans tous les cas, les systèmes suggérés n'ont que peu à voir avec la factorisation et leur solidité semble dépendre davantage du fait que l'on ne connaît pas ou peu le domaine concerné (e.g. les courbes elliptiques) que du fait que le problème est réellement difficile à résoudre. On est ainsi en présence d'un phénomène préoccupant. Soit on utilise un système cryptographique à clé publique basé sur la factorisation, soit on en utilise un basé sur un problème peu connu mais peut être pas très difficile. Alors pourquoi ne pas utiliser ceux basés sur la factorisation ? En fait, une personne qui aurait trouvé un algorithme en temps polynômial déterministe pour factoriser les grands nombres aurait-elle intérêt à publier sa découverte ? pays comme les USA qui cherche à écouter toutes les communications de la terre via la NSA (National Security Agency) n'aurait-il pas intérêt à laisser croire que le problème de la factorisation est difficile de façon à, le cas échéant, continuer à écouter, sans être soupçonné, le monde entier ?
Dans ce qui suit, je vais présenter un procédé cryptographique à clé publique qui est, en général, bien plus compliqué à "casser" que de résoudre le problème de la factorisation.

Cependant, dans certains cas, identifiés, le problème en question sera équivalent à la factorisation. L'utilisateur n'aura qu'à choisir ce qu'il veut. Je montrerai ensuite que selon comment on s'en sert on peut obtenir un procédé de preuve interactive zero-knowledge à

résultat indistingable, un procédé de signature électronique et un procédé de construction d'une fonction à sens unique. Enfin, les procédés présentés ici étant parallélisables, je montrerai comment réaliser des circuits intégrés parallèles qui les réalisent et permettent de faire du chiffrement à clé publique en temps réel, ce que n'arrive à faire aucun autre procédé de ce type à l'heure actuelle.

Les calculs explicités ici sont censés être faits sur des données enregistrées sous la forme de bits, et exécutés par des entités de calcul du type "ordinateur" ou selon le cas, des circuits électroniques spécifiques. Le chiffrement consistera à traiter les données d'entrée x pour fournir une sortie x', l'unité de calcul effectuant un certain nombre d'étapes de traitement de données, ce traitement utilisant un certain nombre de fonctions, notamment matricielles.

Pour les preuves d'identité zero-knowledge ou les signatures électroniques, le même procédé sera utilisé, mais il fera intervenir des interactions entre 2 entités de calcul qui traiteront des données enregistrées elles aussi sous forme binaire.

# 1. Notations - Rappels
Soit A un anneau quelconque et E un A-module de type fini. Soit f un endomorphisme

de E. On dira qu'un vecteur x E E* est un vecteur propre de f si 3EA / f(x)=l.x. Pour plus de simplicité on ne considérera ici que les modules à gauche, mais les résultats décrits sont les mêmes et sont aussi valables pour les modules à droite. De même, # est une valeur propre de l'endomorphisme f si #x # E*/ f(x)=Ax. Dans le cas où A est un anneau commutatif, une façon de calculer les valeurs propres de f est de résoudre son polynôme caractéristique.

Lorsqu'un tirage sera fait au hasard cela voudra dire qu'il est fait avec la distribution uniforme sur l'ensemble considéré. Les valeurs propres seront, en général, tirées dans le centre de l'anneau. Si y et z sont deux vecteurs de E, alors (y,z) est une fonction à sens unique depuis un sous-ensemble des bits des 2 dernières coordonnées de y et z dans A, ou bien, selon le cas, #([alpha]) sera une fonction à sens unique de A dans A. Par exemple, dans certains cas, la fonction (y,z) pourra être l'élévation au carré dans A de la deuxième coordonnée de y.

Dans la suite, lorsque l'on dira "Bob" ou "Alice", il faudra entendre la machine de Bob ou Alice. Cette personnalisation des entités de calcul nous paraît permettre une meilleure compréhension.

# 2. Description en dimension 3
On se place dans un contexte où Bob veut envoyer un message à Alice. E est un A-module de dimension 3, et on suppose que les messages à envoyer sont x1 pour le premier jusqu'à xm pour le dernier. Pour fabriquer sa clé publique Alice tire au hasard 3 valeurs

distinctes non nulles dans A. Soient A, .2 et A3 ces valeurs. Alice forme alors la matrice CM 1 0 Fo = 0 X2 0 puis elle tire au hasard une matrice de la forme h~l= 0 p cp qui 0 0 Â3J 0 il/ soit inversible. Elle forme alors la matrice F=h-1 Fo h qui est la clé publique. Dans la suite cette matrice sera écrite i F= 0 a (3 Cette clé publique est enregistrée dans un annuaire électronique >0 y ô "hardware" consultable et "importable" depuis l'extérieur par une connexion, par exemple, du type Internet.

Algorithme de chiffrement du z# message x; Etant donné xi Bob tire au hasard 2 vecteurs yi et z; tels que {x,, y,, z,) forme une base de E.

11 12 gl3 Soit alors g 1 = gzl g22 913 la matrice Soit alors 921 922 923 la matrice g31 932 g33 formée des coordonnées de ces vecteurs en colonne. Elle est évidemment inversible. Bob calcule alors f = g Fg et (y,, zi)x, + y; +zi. Bob envoie alors à Alice le couple (f, e(yi, z,)x, + Y +z).

Algorithme de déchiffrement du ième message Comme Alice connaît les valeurs propres de f, Alice cherche 3 vecteurs propres de f associés (Uil à chacune des valeurs .1;. Si on considère le vecteur propre ui = Ui2 associé à .2 par uns 0 exemple, alors ce dernier est proportionnel à g p On a donc le système d'équations ' P<3i2 + W913 = kuis pg22 + W923 = kUi2. ing32 + úJg33 = kui3 Vil De même si vi = Vi2 est le vecteur propre associé à.13, on a alors v, qui est proportionnel Vi3

0 à g' i p . On obtient alors le système suivant : 1 't gi2+gi3=k'vii (/jg22 + 923 = kl 12. On peut alors écrire ces équations sous la forme suivante. g32 + g33 = k Vi3 (912, â1,3) - (kul k'vi)0 w p (ô22> 92,3) = (kU2, k'v2) w çp et (932, 93,) -1 9i2 g13 (ku3, k'v3) j Rappelons que y g22 et z = g23 Si on écrit alors g32 933 y, C' kui tj' k' v, nos équations peuvent alors être écrites sous la forme z P1 , , kui , .... Ce qui

prouve que yt et z, sont dans le plan engendré par les valeurs propres .l2 et A3 . Le texte chiffré est composé de la matrice f et d'un vecteur aléatoire U=g(y" z,)xi + y, +z, . Ecrivons alors que U-({/+Ift')ku-(w'+rp')k'vl est colinéaire à n'importe quel vecteur propre non nul associé à #1. Appelons ce dernier vecteur IL On

(Ul - (Q' + !/J') kUl1 - (úJ' + ({J') k' Vi1 = ul obtient alors U2 - (e' + i/r1 ) kul2 - (ai1 + cp' ) k' V,2 = r\[x2 où les inconnues sont Ü3 - (7' + f' ) kui3 - (W' + (P' ) k' Vi3 = f/tJ-3

x, lit et 17. Le système se resoua aisément et a une solution unique qui va aonner le et K et donc va permettre de retrouver #. Le reste du déchiffrement est alors trivial.

# 3. Difficulté de casser le système
La difficulté de casser le système précédent vient de la difficulté de trouver les valeurs propres d'une matrice à coefficients dans un anneau quelconque. On peut en particulier démontrer que lorque l'anneau est Z/nZ où n=pq est le produit de 2 grands nombres premiers comme dans le RSA, l'algorithme précédent est aussi dur à casser qu'il est difficile de factoriser le nombre n. Dans ce cas particulier, une fonction intéressante pour est l'élévation au carré de la 2ième coordonnée de y modulo n.

# 4. Preuve zero-knowledge
Considérons R un anneau non commutatif. Supposons que R vérifiela condition dite de Ore à droite. C'est à dire que V a, b # R, 3 a', b' e R / aa' = bb'. On démontre alors que sous cette condition, l'anneau R admet un anneau de fractions, c'est à dire des éléments du type a/b où a # R et b # S où S est une partie de R sur laquelle on peut construire une

relation d'équivalence. Dans ce cadre, pour peu que a e S, l'inverse de a/b s'écrit b/a. La construction d'un tel anneau de fraction est unique dès qu'on a choisi S. Cette construction ne sera donc pas décrite ici. Par contre, une même construction existe pour une condition dite de Ore à gauche avec le même résultat, mais une autre structure d'anneau. Le résultat présenté ici est donc valable pour les 2 cas. Ce qui est important, c'est que l'on travaille sur des classes d'équivalence et non sur des objets numériques directement. Appelons alors CI le procédé de chiffrement du paragraphe 2 et D1 le procédé de déchiffrement du paragraphe 2. Dans le scenario présent, Alice veut prouver son identité à Bob. De même que dans les protocoles zero-knowledge classiques, elle va montrer qu'elle connaît une information connue d'elle seule, sans donner davantage d'information que le fait qu'elle connaît cette information. En clair, Alice va montrer qu'elle connaît les valeurs propres de F. Le protocole se déroule comme suit : Bob chiffre un message tiré au hasard dans le module sur l'anneau A des fractions de R avec Ci et l'envoie à Alice. A la réception, Alice vérifie qu'il est de la forme (f, v) où f est une matrice 3x3 à coefficients dans A et v un vecteur de dimension 3 sur A. Si tel n'est pas le cas, alors Alice arrête le protocole. Sinon Alice déchiffre avec D1 On montre facilement que le message obtenu est x' si le message de Bob est x et que chaque coordonnée de x' est dans la meme classe d'équivalence que celle correspondante de x. Les deux vecteurs sont donc équivalents et, d'un point de vue théorique on a déchiffré le message. Néanmoins, d'un point de vue pratique, on a, numériquement, 2 vecteurs équivalents potentiellement différents. Il n'y a aucune raison théorique ou pratique pour favoriser une forme plutôt qu'une autre. Par contre, seul le détenteur des valeurs propres peut trouver un équivalent de x. A la réception de x' Bob vérifie l'équivalence des 2 vecteurs. Si tel n'est pas le cas, Bob refuse d'identifier Alice, sinon Bob accepte.

On démontre qu'un tel protocole est un protocole de preuve interactive Zero-knowledge au sens de Fiat-Shamir à résultat inconditionnelement indistingable.

# 5. Signature
Nous allons nous inspirer ici d'une technique due à Jean-Jacques Quisquater et Louis Guillou qui permet, à partir d'un système interactifde preuve zero-knowledge, de déduire un système de signature interactif. Comme dans le paragraphe 2, Alice construit sa matrice publique F. On suppose ici que le message à signer est m # E. Comme dans le procédé CI, Bob tire au hasard 3 vecteurs tels que {x, y, z} forme une base de E et on appelle g-1la matrice formée de ces vecteurs en colonne, ainsi que f=g-1Fg. f est envoyée à Alice. A la réception, Alice calcule comme dans le paragraphe 2, x, y et z ainsi que f(m) et le décompose sur la base {x, y, z}. Elle a ainsi f(m)=t1 + t2 + t3. Alice tire alors au hasard 3

valeurs or, 8 et y et envoie à Bob le couple (atl + f3t2 + yt3, (ar)). Bob décompose ru) sur la base {x, y, z}, obtient les t3 , décompose atl + /3t2 + yt3sur la base des tt, ce qui lui donne a, j3 et y et calcule g( a) pour vérifier que la deuxième partie du couple correspond bien.

On remarquera que cet algorithme marche quelque soit l'anneau considéré, commutatif ou non, anneau des fractions ou non.

# 6. Le choix de l'anneau
Dans les sections précédentes nous avons décrit des procédés qui marchent dans quasiment tous les types d'anneaux. Cependant, on peut ici donner quelques conseils judicieux et apporter des précisions. Tout d'abord, les procédés CI et D1 marchent dans tout anneau. Lorsque l'anneau est commutatif, il faut vérifier que le problème de trouver les valeurs propres est un problème difficile. A priori, mais de manière non exhaustive, un anneau local pourra marcher. Une façon de construire un tel anneau est de choisir dans un anneau R un idéal premier P. Soit S = R - P. Alors A = S-1 R est un anneau local. Pour le cas des preuves zero-knowledge et des signatures, l'anneau quotient d'un anneau non commutatif peut être choisi. Là encore, même si la construction est un peu différente, on pourra choisir un anneau local. Enfin, on n'est pas obligé d'être réellement dans un anneau. En effet, l'associativité de la multiplication n'est pas une condition nécessaire. Ainsi un anneau convenable pourrait être le suivant. Soit R=On l'ensemble des octonions modulo n où n=pq est le produit de 2 nombres premiers. Soit S l'ensemble des éléments de R dont aucune des composantes n'est divisible par p. Considérons alors l'anneau non associatifdes fractions A = S-1 R. Les algorithmes précédents marchent dans un tel anneau.

Tout cela n'est donné qu'à titre d'exemple, les procédés décrits marchant dans quasiment toutes les structures à 2 opérations.

# 7. Description en dimension 4
Les procédés de la dimension 3 peuvent être adaptés à la dimension 4. Nous

A1 U U V reprenons les mêmes notations que précédemment. Soit Fo 0 p2 0 la clé secrète 0 0 0 A4, d'Alice où les sont choisies au hasard non nulles et toutes distinctes. Alice tire alors au hasard une a r 0 0 matrice h- . # ii v v 0 0 et publie la matrice F = h Fo h. Un message est toujours un 0 0 p p 0 0 Co

vecteur u e ii, r. qui est cette rois-ci ae dimension 4 sur A.

Chiffrement d'un message Bob veut envoyer u. Il tire alors au hasard x et pose y = u - x. Il complète en choisissant au hasard z et t tels que {x, y, z, t} forme une base de E. Appelons g-1 = (g,j ) la matrice formée des colonnes de ces vecteurs. Bob envoie alors à Alice f=g-1Fg suivie d'un vecteur du type (z,t)(x + y) + z +t ou #1 (z, t) x + #2(z, t) y + z + t.

Déchiffrement du message
On raisonne comme au paragraphe 2 pour retrouver les vecteurs z et t en écrivant que le vecteur propre associé à #3 est proportionnel

0 0 àg-1 ,0 et en écrivant que celui associé à A4 est proportionnel à g 1 .En résolvant les (À), 4p systèmes et équations on obtient z et t et donc #(z, t) ou les #i(z, t) et donc u de manière évidente.

Propriété particulière
A partir de la dimension 4 on peut démontrer que le système résiste à une attaque adaptative à chiffré choisi, alors que dans le cas de la dimension 3 l'attaque ne doit pas être adaptative.

Généralisations
Un tel schéma ou celui en dimension 3 peuvent être facilement généralisés à des dimensions supérieures à 4. Cela étant immédiat, nous n'irons pas plus loin dans la description de tels systèmes. Cependant, nous citerons pour mémoire le cas des dimensions supérieures ou égales à 5 pour lesquelles, en plus de la difficulté traditionnelle de trouver des valeurs propres vient s'ajouter, dans le cas d'un anneau commutatif en particulier, l'impossibilité de la résolution par radicaux du polynôme caractéristique.

# 8. Variantes
Nous présentons ici, de manière non exhaustive, quelques variantes des procédés précédents de façon à prouver la puissance du système. Ces variantes sont toutes en dimension 3 ou 4 mais se généralisent à d'autres dimensions très facilement. Nous ne donnerons ici que des descriptions partielles, le reste étant identique aux paragraphes précédents. De plus, saufmention du contraire, nous nous intéresserons principalement aux aspects de chiffrement.

Variante numéro 1
Dans le procédé CI, au lieu d'envoyer à Alice (f, #(y, z) x + y + z), Bob envoie

directement (f, x+y+z). On démontre qu'aucune sécurité n'est apportée par un tel procédé s'il est sur un anneau commutatif. Par contre, dès que l'anneau est non commutatif, la sécurité est assurée (via une conjecture qui est hors du cadre de ce texte). Ainsi le chiffrement et déchiffrement sont simplifiés d'autant pour un anneau non commutatif. De même, cette variante peut être étendue à la preuve zero-knowledge du paragraphe 4 et à la signature du paragraphe 5.

Variante numéro 2
On se place ici en dimension 4 et strictement dans le cas d'un anneau non commutatif. Sous la condition que certains éléments de la matrice g-1soient connus et par exemple égaux à 1, on peut alors modifier le chiffrement comme suit. Supposons que

l'équivalent d'une ligne de g soit connu, par exemple ga, = g4,2 = gl,3 = 91,4 = 1, alors il suffit à Bob d'envoyer la matrice f. En suivant le même type de raisonnement que pour D1 Alice retrouve les vecteurs x, y, z et t et peut donc calculer x+y et z+t qui forme alors le message en clair.

Variante numéro 3
Nous allons donner ici un système de preuve interactive zero-knowledge en dimension 2 ; il nous faut pour cela une hypothèse supplémentaire, celle selon laquelle Alice sait trouver le valeurs propres d'une matrice 2#2 en temps polynomial déterministe. Soit F0 = (0#1#20) tirée au hasard par Bob. Ce dernier tire alors au hasard 2 vecteurs x et y formant une base de E et soit g-1la matrice formée de ces vecteurs en colonne. Soit F=g-1 1 Fo g. Bob envoie alors à Alice le couple (F, x+y). Alice, qui sait retrouver les valeurs propres peut alors retrouver x

et y et elle tire au hasard a et {3, puis envoie à Bob (ax+/3y, g(o:)). A la réception, Bob, qui connaît la base de vecteurs propres {x, y} retrouve a et,6 et calcule #([alpha]) pour voir la correspondance avec le deuxième élément du couple qu'Alice lui a envoyé. Si tel est le cas, Bob accepte, sinon Bob refuse.

Un tel algorithme est particulièrement bien adapté au cas où A=Z/nZ et n=pq comme dans le RSA. En effet, connaissant la factorisation de n, Alice peut facilement résoudre le polynôme caractéristique en utilisant, entre autre, le théorème chinois des restes et dans ce cas on peut par exemple choisir #([alpha]) = [alpha]2 mod n.

Variante numéro 4
Nous donnons ici, en dimension 3 une version de preuve interactive zero-knowledge qui marche dans un anneau commutatif. De même que dans le paragraphe 2, Bob chiffre un message tiré au hasard, x, à l'aide de Ci. Alice le déchiffre et obtient donc x, y et z. Elle

renvoie donc à Bob (o:x+f3y+yz,g( 0:)) et Bob vérifie alors comme dans la variante numéro 3.

Des schémas similaires marchent dans toutes les dimensions.

Nota
Les variantes 3 et 4 donnent bien sûr naissance aux systèmes de signature interactifs

du type Guillou-Quisquater.

Variante numéro 5
Voici un système de chiffrement basé sur la difficulté de trouver les valeurs propres d'un endomorphisme lorsqu'Alice connaît une information qui lui permet elle, de les calculer C'est le cas typique où on travaille dans l'ensemble des entiers modulo n et où seule Alice connaît la factorisation de n. Bob, lorsqu'il veut s'adresser à Alice, tire au hasard une matrice #1 0 0 diagonale F= 0 #2 0 et la garde sans modification tant qu'il correspond avec Alice.

0 0 #3 Le ième message est un vecteur x, # E et Bob tire au hasard y, et z, pour que les 3 vecteurs forment une base de E. Soit alors gi-1la matrice formée de ces vecteurs en colonne. Bob

envoie à Alice (f, = g Fg,, g(y" z,)x; + y, +z,). Pour déchiffrer, Alice calcule les valeurs propres de f1 (seulement pour le premier message, qui au passage peut être public pour faciliter encore les choses), et cherche une base propre de fi. Elle décompose ensuite #(yi, z,)x, + yi + z, sur cette base, obtient y, et z, donc #(xi, y,) et par voie de conséquence x,.

Variante numéro 6
Nous présentons ici une généralisation directe de l'algorithme présenté au paragraphe 2. Si n est la dimension de E, on considère une matrice nxn, clé publique d'Alice et de la forme F= (0#1 R0)ou R est une matrice non diagonale comme dans le paragraphe 2 mais de taille (n-l)x(n-l) et qui a pour valeurs propres #2, ..., #n. Le message est toujours un vecteur de E et Bob envoie à Alice le message chiffré (f=g-1 Fg, #(y, z, t, ...)x+y+z+t+...). Le déchiffrement est alors évident compte tenu de ce qui précède.

# 9. La parallélisation
Dans ce paragraphe, nous allons voir deux types de parallélisation.

# 9. 1. Parallélisation brute
Ici, les opérations sont supposées câblées dans du hardware. Nous avons alors plusieurs briques de hardware pour réaliser les opérations. Le but est de diminuer au maximum le nombre de multiplications série que l'on va avoir à faire. Les opérations de base qui sont câblées sont la multiplication, l'addition, la soustraction et l'addition dans l'anneau A.

Elle sont représentées schématiquement sur les figures 1 à 4. On peut alors définir la multiplication parallèle de 2 matrices. Prenons l'exemple en dimension 3. Si P=(Pi,j) et si

M=(Mj) alors on a PM = (ai,j) où ai,j = ì=i Mkj Pik. On remarquera que cette formule est valable que l'anneau soit commutatif ou non. La formule de multiplication des matrices sera indiquée selon le schéma figure 5 et le détail effectué est selon la figure 6. Sur cette

dernière figure on peut constater que la multiplication de 2 matrices entre elles peut se faire en le temps d'une multiplication série, puisque pour i et j fixés on peut effectuer les 3 multiplications en parallèle. Conformément à la coutume, on néglige le temps de calcul des additions et soustractions. On pourrait continuer ainsi et détailler chaque opération nécessaire à l'exécution de chaque procédé décrit ci-dessus. La chose étant évidente, nous n'irons pas plus loin, mais il est aisé de concevoir un circuit électronique spécifique à chaque procédé qui effectue en parallèle le maximum possible d'opérations de façon à diminuer au maximum le temps de calcul vu par l'utilisateur. Ainsi, dans un anneau commutatif, le temps nécessaire, avec un tel circuit, pour calculer CI est le temps de 5 multiplications séries. Pour cette évaluation, nous avons considéré que le temps d'une division est équivalent à celui d'une multiplication, ce qui est courant mais peut être optimiste. A l'inverse, dans un anneau de fraction, le temps d'une division est négligeable. En ce qui concerne D1, 7 multiplications série sont nécessaires.

Dans les anneaux de fractions non commutatifs, ces temps peuvent varier quelque peu selon l'algorithme d'inversion choisi pour une inversion de matrice. Cependant, comme le temps d'une division est négligeable, on arrive là encore, à d'excellentes performances.

# 9. 2. Parallélisaton par microprocesseurs
La parallélisation précédente a l'avantage de procurer les meilleurs débits possibles.

Elle a cependant l'inconvénient de ne pas utiliser toute la puissance des procédés présentés ici.

En effet, dans le paragraphe 9.1., une fois l'anneau choisi, on ne peut plus en changer.

Comme nous l'avons dit plus haut, en introduction, pour le RSA par exemple, le jour où le problème de la factorisation est résolu, si c'est possible, tous les circuits intégrés qui effectuent cet algorithme sont bons àjeter à la poubelle. Pire, si l'on doute (c.f. ce qui a été dit sur la NSA) on est prisonnier du système et il n'y a guère d'alternative. Nous proposons donc ici une parallélisation d'un type nouveau.

Le lecteur est invité à reprendre les figure 1 à 4 précédentes, et à considérer que chaque "boîte" est un microprocesseur pour lequel on peut programmer une opération dans l'anneau de son choix, et cela dans un langage évolué du type Mathematica. On peut alors créer des macro microprocesseurs comme celui de la figure 5 en parallélisant l'utilisation des premiers dans une structure du type de celui de la figure 6. C'est uniquement le compilateur qui insérera dans chaque partie adéquate le "morceau" d'algorithme convenable. En continuant ainsi, toujours avec le souci de la parallélisation, les procédés de chiffrement et déchiffrement se construisent comme des sortes de superprocesseurs.

L'avantage de cette technique réside dans le fait que si on a un doute sur un anneau, on peut en changer immédiatement. Le problème est alors basé sur le cas très général de la recherche des valeurs propres d'un endomorphisme sur un module sur un anneau quelconque, voire, comme nous l'avons dit pour les octonions, sur une algèbre quelconque qui peut ne pas être associative. Ce problème, qui englobe celui de la factorisation, est très large et bien plus complexe que cette dernière.

# 10. Une nouvelle fonction à sens unique
Les fonctions à sens unique sont d'une importance capitale en tant que primitives cryptographiques. Dans ce cadre, il est toujours interessant d'en avoir de nouvelles à disposition, puisque certains protocoles formels existent et sont bâtis sur la conjecture selon laquelle de telles fonctions existent.

Nous reprenons donc le procédé Ci mais dans un anneau de fractions non commutatif, où tous les éléments de g sont tirés au hasard et les valeurs propres choisies avec la distribution uniforme sur tout l'anneau et sont distinctes. Un tel procédé, Ci, est alors une fonction à sens unique qui à x associe une image. La difficulté de retrouver x réside dans le fait que dans un tel anneau, en général, la recherche d'un vecteur propre est très difficile (e. g. l'ensemble des vecteurs propres peut ne pas être un sous-module du module E).

Bien entendu, cette fonction à sens unique peut se généraliser à n'importe quelle dimension

Claims

Revendications

1. Procédé de cryptographie à clé publique de données enregistrées sous forme de bits sur un support exploitable par une ou plusieurs unités de calcul aptes à traiter des données d'entrée x pour fournir des données de sortie x', comportant au moins une étape de traitement de données, caractérisé par le fait que la ou les unités de calcul manipulent des matrices carrées à coefficients dans un anneau ou une algèbre, commutatifs ou non, associatifs ou non, les données d'entrée étant considérées commes des vecteurs appartenant à des modules sur ces anneaux ou algèbres, la manipulation binaire amenant en sortie éventuellement une matrice carrée ou un vecteur ou un scalaire ou deux options parmi les trois ou les trois à la fois, les coefficients restant toujours sur les mêmes anneaux ou algèbres.

2. Procédé cryptographique selon la revendication 1 caractérisé en ce que la matrice F constituant la clé publique est carrée et diagonalisable, en ce que la fabrication de la clé publique se fait en tirant une matrice à coéfficients dans l'algèbre sur laquelle on travaille, avec la distribution uniforme, et en ce que cette matrice doit être inversible.

3. Procédé cryptographique selon les revendications 1 et 2 caractérisé en ce que dans un mode de réalisation, le chiffrement du vecteur qui représente le message en clair constitue en la complétion de distribution uniforme (sur un sous-ensemble du module) de ce vecteur en base dans le module de travail, cette complétion étant "archivée" dans l'unité de calcul sous la forme d'une matrice carrée, chaque colonne de cette matrice étant constituée d'un des vecteurs de la base, le premier étant le message en clair, la continuation du chiffrement se faisant en changeant la matrice constituant la clé publique via un changement de base lié à la matrice de complétion ci-dessus évoquée, le résultat étant accompagné du vecteur "message en clair" multiplié, éventuellement, par le résultat de l'application d'une fonction à sens unique sur les coordonnées des vecteurs complétant la base, additionné de ces vecteurs de complétion.

4. Procédé cryptographique selon l'une quelconque des revendications précédentes, permettant la preuve d'identité zero-knowledge, caractérisé en ce que lors de l'utilisation d'un anneau ou d'une algèbre de fractions non commutative, dans le mode de réalisation de la revendication 3, le prouveur fournit au vérifieur le résultat de son déchiffrement comme preuve de connaissance, à savoir un vecteur égal au message en clair qui aura au préalable été tiré au hasard avec la distribution uniforme, l'égalité étant établie dans l'anneau ou l'algèbre de fractions non commutative concernée, mais en fait potentiellement un vecteur numériquement différent mais équivalent au message en clair, équivalence au sens de celle définie par la condition de Ore.

5. Procédé cryptographique selon les revendication 1, 2 et 3, permettant la signature électronique, caractérisé en ce qu'une fois la matrice f=g-1Fg ayant été envoyée au "fabricant" de la clé publique F, ce dernier calcule le changement de base effectué sur F, décompose le message à signer sur la base du module ainsi obtenue et envoie une combinaison linaire de cette décomposition accompagnée de l'image par une fonction à sens

unique de l'un des coefficients de la combinaison linéaire.

6. procédé cryptographique selon l'une quelconque des revendications précédentes, caractérisé en ce qu'un mode de réalisation met en oeuvre une parallélisation des calculs dans un circuit spécifique, ce circuit étant programmable ou non et donc, selon le cas, permettant le choix ou non, respectivement, de la structure d'anneau ou d'algèbre, retenue pour travailler.