Brevet FR2696567A1 — publié le 19940408

PROCEDE DE CRYPTOGRAPHIE DE MESSAGES TRANSMIS PAR UN SUPPORT D'INFORMATIONS A UN SYSTEME DE TRAITEMENT. La présente invention concerne un procédé de cryptographie de message transmis par un support d'informations à un système de traitement et d'exploitation. Les procédés de cryptographie connus peuvent être répertoriés dans deux familles bien connues. Une première famille repose sur l'emploi d'une clé secrète. Cette clé secrète est distribuée à tous les systèmes de traitement et d'exploitation, ce qui présente déjà un grand risque puisque si cette clé est découverte il faut redistribuer une nouvelle clé à tous les systèmes existants. D'autre par il est nécessaire dans le cas ou l'on désire avoir diverses hiérarchies et niveaux de sécurité de générer des clés. On utilise alors un principe connu et couramment utilisé de diversification. Ce principe a comme inconvénient d'imposer une gestion des différentes clés distribuées dans tous les supports d'informations qui ont été émis. Une deuxième famille de procédés de cryptographie repose sur l'utilisation d'une clé publique mais présente en revanche l'inconvénient de nécessiter une grande capacité de calcul ce qui est incompatible avec une implantation sur des composants à bas coût. On peut citer d'autre part une troisième famille dont le principe est basé le parcours d'arbre d'authentification. On pourra d'ailleurs se reporter aux références citées ci-après (1) W. Diffie and M. Hellman New directions in cryptography IEEE Transaction on Information Theory, IT-22(6), November 1976. (2) L. Lamport Construcing digital signatures from a one way function. Technical Report CSL-98, SRI Intl. (3) Ralph C. Merkle Potocols for public key crytposystems In Symp. on Security and Privacy, IEEE, Computer Society, April 1980. (4) Ralph C. Merkle A certified digital signature. In advances in Cryptology, lecture notes in computer Science. Springer Verlag, 1989. Proceedings of Crypto'89. Les procédés de cryptographie reposant sur un parcours d'arbre d'authentification peuvent dans leur principe assurer une authentification et une signature des messages transmis par le support d'information émetteur, mais ne peuvent en pratique être mis en oeuvre dans des applications implantées sur des supports ayant de faibles capacités de calcul et/ou de faible capacité mémoire notamment dans des supports tels que des cartes à puce du fait des temps de calcul que demande le parcours de l'arbre. Aucun procédé basé sur ce principe n'apporte une solution à ce problème de temps de calcul de manière à être compatible avec une implantation sur une carte à puce par exemple. De toute façon, la capacité mémoire requise pour parcourir l'arbre et donc pour permettre tout simplement les opérations d'identification et d'authentification est trop importante. Il est donc nécessaire d'utiliser des composants de grande capacité pour mettre en oeuvre ces procédés. Comme le coût de fabrication du matériel augmente avec la capacité mémoire et avec la capacité de calcul des circuits entrant dans ces fabrications, il devient sans intérêt de développer des applications autour de ce principe sur de tels supports. La présente invention permet de remédier à ces problèmes. Ella a pour objet un procédé de cryptographie susceptible d'être mis en oeuvre par tout support d' information et notamment par des cartes à puces sans que leur coût de fabrication soit prohibitif. La présente invention a plus particulièrement pour objet un procédé de cryptographie de messages transmis par un support d'informations à un système de traitement et d'exploitation, le support d'information comprenant des moyens de traitement et de mémorisation caractérisé en ce qu'il consiste - à calculer une valeur p(i) à partir de fonctions de hachage f opérées sur une valeur Vi générée par les moyens de traitement du support d'information et successivement sur les résultats obtenus, de manière à obtenir et à mémoriser C valeurs intermédiaires suivant une structure de donnée arborescente dans laquelle (i) est la racine d'un sous arbre, - à transmettre p(i) pour un message à transmettre donné, - à transmettre sur requête du système de traitement et d'exploitation c valeurs intermédiaires parmi les C valeurs mémorisées ayant permis d'obtenir (i), et étant définies à partir d'un chemin d'authentification permettant de remonter jusqu'à la racine (i) du sous-arbre, - à transmettre n valeurs parmi les C valeurs ou n valeurs étant définies à partir d'un chemin d'authentification permettant de remonter jusqu'à la racine (n) d'un arbre utilisateur du support, - à transmettre p valeurs parmi les c valeurs, ces E valeurs étant définies à partir d'un chemin d'authentification permettant de remonter jusqu'à la racine (p) de l'arbre général décrit par la structure de donnée, - à recalculer une nouvelle valeur (i) à chaque message à transmettre et à redéfinir les valeurs intermédiaires c à transmettre après la transmission de la nouvelle valeur p(i). Selon une autre caractéristique du procédé, l'arbre d'authentification est un arbre équilibré de degré a et de profondeur n. Selon une autre caractéristique du procédé, le calcul de (i) est opéré à chaque message émis par le support vers le système d'exploitation et permet d'obtenir une valeur de clef Ki attribuée à l'utilisateur ut du support, chaque clef obtenue étant différente d'un message à l'autre, les clefs déjà utilisées et, les valeurs intermédiaires C définissant le parcours pour atteindre une valeur Ki étant effacées des moyens de mémorisation au fur et à mesure du calcul d'une nouvelle valeur Ki. Selon une autre caractéristique du procédé, la valeur Vi est une valeur pseudo-aléatoire obtenue par combinaison d'une valeur aléatoire et d'une clef secrète (k) stockée dans le support, chaque support ayant sa propre clef secrète. D'autres particularités et avantage de l'invention apparaîtront à la lecture de la description qui faite e qui est donnée par un exemple illustratif et non limitatif en référence aux dessus sur lesquels - la figure 1 illustre une structure hiérarchique arborescente assurant trois niveaux de sécurité selon le procédé conforme à l'invention; - la figure 2, illustre selon un exemple particulier l'arbre selon l'invention d'authentification; - la figure 3, illustre l'exemple d'un parcours certifiant; - la figure 4, illustre les échanges authentification et signature entre le support 1 et le système 2. Selon l'invention, le procédé de cryptographie inclu trois arbres d'authentification permettant ainsi d'obtenir les trois différentes composantes d'une preuve ler niveau : un arbre afin d'authentifier chaque utilisateur est défini et permet de constituer un annuaire d'attribution, 2ème niveau : pour chaque utilisateur ut on définit un arbre permettant de certifier chaque ensemble de clefs visant à authentifier un message donné. En effet, on fait correspondre à tout message un ensemble de clefs qui sera utilisée une seule fois lors de la signature. 3ème niveau : enfin pour un ensemble de clefs, un arbre permet d'authentifier chaque clefs. Les parcours du premier (par mémorisation de l'unique chemin d'authentification) et du dernier niveau (du fait de sa taille le recalculer est aisé) sont facilement implementables. Le deuxième niveau implique de considérer tous les chemins, et ceci est réalisé par la mise en oeuvre des étapes 1 à 11 décrites dans la suite afin d'obtenir un parcours certifiant selon une caractéristique du procédé on rappelle dans ce qui suit quelques définitions et des notations couramment utilisées soit une fonction de hachage vérifiant la propriété = Xi > On notera f une fonction à sens unique et g un générateur de nombres pseudo-aléatoires. Il est connu que l'on peut construire la fonction de hachage et le générateur à partir de la fonction à sens unique f. Enfin, on considérera que le temps nécessaire pour hacher deux valeurs est équivalent au temps nécessaire pour calculer deux valeurs à l'aide de f et que f et g ont le même niveau de complexité. Définition général d'un arbre d'authentification. On considère un arbre ordonné T, l'ensemble de ses noeuds V et l'ensemble de ses arêtes E. On repère chaque noeud appartenant à V par un mot sur l'alphabet des entiers avec (1) le mot vide représente la racine de T (2) a0a1...ak-(0), a0a1...ak-1(1), a0a1...ak-1 (&alpha;-1) représente la liste dans cet ordre des fils du noeud représenté par le mot a, a étant le degré de ce noeud. On définit Vf l'ensemble des feuilles de V c'est à dire l'ensemble des noeuds de V ne possédant aucun fils. T ainsi défini sera en règle générale un arbre ordonné de degré constant, tout autre configuration pouvant être envisagée, mais ne représentant que peu d'intérêt dans le cadre de la présente invention. Définition de la notification d'affectation. Soit M, un ensemble donné de valeurs et une fonction de hachage sur M. On appelle affectation de G, un arbre de degré a et de profondeur k, une application p* sur Vf l'ensemble des feuilles de Vf par #*(a) = La valeur affectée à un noeud donné est donc la valeur hachée des valeurs affectées à ses fils. Définition de la notion de certification. On appelle certificat de l'affectation 0* (a) d'un noeud a = ....... akl, la donnée des valeurs 0*(a0a1...ai-1j) pour 0 # i (1) l'affectation de la racine est authentifiée (2) la recherche de collisions pour la fonction de hachage sur la liste des valeurs de l'arbre est difficile. Définition de l'annuaire d'attribution rappel de la notion de liste d'attribution. Il est peut être intéressant de représenter une liste d'attribution définie par une autorité à l'aide d'un arbre T correspondant aux définitions précédentes. Considérons que l'on associe à chaque feuille a de l'arbre un utilisateur. Il est possible de former une valeur d'affectation du type (a) = avec *Id étant le nom de l'utilisateur *Ku une clef publique associée à l'utilisateur * t une date limite de validité L'affectation peut donc être une valeur résumante d'un profil défini par le système émetteur incluant - la notion d'identité et donc de propriété - la notion de temporalité d'un droit d'accès sur des données sensibles - la notion de donnée publique De par sa forme, grâce à l'utilisation de la fonction de hachage, on peut oublier l'arbre et donc l'annuaire d'attribution. Preuve d'identité à clef jetable et signature d'un message selon l'invention: on peut se reporter au schéma de la figure 1, donnant la structure de l'arbre. Considérons les trois niveaux de l'arbre général. Chaque niveau est un arbre d'authentification dont on déduit la structure à travers les valeurs d'affectation de leurs feuilles respectives. On définit une fonction d'affectation n pour chaque niveau n de l'arbre général. ler niveau : a chaque feuille u de l'arbre de premier niveau correspond une valeur d'affectation résultat du hachage de l'identité Id d'un utilisateur et de l'affectation par # 2 de la racine T(u) de l'arbre de second niveau T(u). On adresse bien ainsi l'ensemble des utilisateurs concernés par le système. Ainsi #u, #1(u) = #*2(^T(u)),t > On procède donc à l'authentification de l'identité de l'utilisateur et de l'affectation de la racine de son arbre. 2ème niveau : Dans T(u), on fait correspondre à chaque feuille aila ième preuve interactive et un arbre Ti qui permet l'authentification d'un ensemble de clefs. La notion de lien entre un ensemble de clés (arbre Ti) et une preuve, signature de message par exemple est ici mise en évidence. Ainsi #ai, #2(ai) = #(ai) = #3*(^Ti) L'affectation de chaque feuille ai est donc la valeur hachée de la racine d'un arbre authentifiant d'un ensemble de clés publiques donné. 3ème niveau : l'arbre du troisième niveau est constituée d'une racine ai et de s fils bi,j qui sont donc les feuilles de ce dernier. On fait correspondre à chaque bi,j une clé publique en lui affectant la valeur #3(bi,j)=fss-1(Ki,j) Ainsi, pour toute feuille ai du second niveau, on a = #3*(bi,1, bi,2,..., bi,s) = #3*(fss-1(Ki,1), fss-1(Ki,2),..., fss-1(Ki,s)) = En supposant qu'un utilisateur donné possède une clef secrète K, on définit les Ki,j grâce au générateur g par : Ki,j = g (K,i,j) Les Ki,j sont donc le résultat d'une opération de diversification sur la clef maître K. On peut se reporter pour la suite au schéma de la figure 4. Dans une procédure interactive d'authentification, l'utilisateur afin de démontrer que son identité Id est bien celle qu'il annonce, doit apporter la preuve qu'il connaît un ensemble de clefs{Kij;0 Le prouveur 1 choisit donc une valeur i et annonce ainsi clairement quel arbre Ti il compte utiliser au cours de la procédure d'authentification. Le vérifieur 2 choisit à son tour s valeurs bj en base ss telles que : b1 + b2+...+bj = [s(ss-1)/2]. Alors le prouveur donnent les fbj (Kij) pour tous les j. Avec le protocole suivant, le prouveur montre sa connaissance de tous les Kij et donc de K compte tenu des hypothèses précédentes sur les fonctions , f et g. En règle générale, le niveau de sécurité exigé pour la signature d'un message est plus élevé que celui d'un procédé de preuve interactive du type identification. Il suffira donc d'utiliser plusieurs arbres Ti en fonction du niveau de sécurité que l'on désire atteindre. Ainsi, chaque i représente une unité de sécurité. Une preuve d'identité coûtera donc simplement une unité alors qu'il faudra en utiliser plusieurs pour effectuer une opération de signature. On voit clairement apparaître la notion de dépense à travers le principe des clefs jetables et donc de dépense d'une unité de sécurité pour un service donné. Il peut donc être intéressant d'assimiler le coût d'une unité de sécurité à celui de la dépense d'une unité monétaire. Le fait de donner les fss-l(Ki,j) correspondra au don d'une unité monétaire mais aussi prouvera qu'une unité monétaire a bien été distribué. En effet, si quelqu'un donne la même unité à différentes personnes, il fournira de mêmes différentes combinaisons de bJ et donc, plus d'informations sur Ki,j qu'il n'en avait le droit. Le faussaire fournira donc de lui-même les preuves permettant de le confondre. Ainsi le procédé peut s'appliquer à la construction d'un système de paiement électronique. L'initialisation du système se fera par le simple don d'une quantité de monnaie certifiée par l'autorité aux membres du système et donc l'introduction de fausse monnaie, du moins au démarrage, pourra être évitée. On va maintenant illustrer à partir de la figure 2 l'authentification d'une valeur (121). L'image par d'un noeud est donc la valeur hachée des images par de ses fils. Dans l'exemple de la figure 2, on suppose une application définie sur l'ensemble des feuilles (000,001,...,222). On la prolonge en une application p * définie sur tous les noeuds avec par exemple #/(12)= = , #(122) > et Dans toute la suite on notera au lieu de * sachant que * n'est qu'une succession d'opération de hachage . Si l'on admet que #(#) est authentifiée, d'après les propriétés cryptographiques de la fonction de hachage, pour authentifier une valeur #(a0a1...an-1), il suffit de donner l'image par de tous les noeuds qui ont un père parmi les ancêtres de ....... anl. Ces noeuds correspondent à l'ensemble minimal des valeurs à donner pour permettre de calculer (N à partir de #(a0a1...an-1) par des opérations de hachage. Par exemple, pour authentifier (121) dans l'arbre de la figure 1, il faut donner #(0), #(2), #(10), #(120), #(122). On peut alors retrouver ( ) à partir de (121) par: ( ) = où #(1) = où (12) = Plus formellement, une authentification de #(a0a1...an-1), est la donnée des #(a0a1...ak-1j) pour tout k et tout j différent de ak. D'après la propriété admise de la fonction de hachage, on peut remplacer les (a0a1...ak~lj) avec j Dans l'exemple ci-dessus, on peut remplacer (10) et (11) par car #(1)= #(12) > Ainsi, si on note #(a0a1...ak-1ak)= une authentification de #(a0a1...an-1) est la donnée des g(aOal...ak) et des #(a0a1...ak-1j) pour tout k et j > ak. Dans l'exemple de la figure 2, l'authentification de (121) consiste à révéler les valeurs #g(1) = #(0) g(12) = g(121) = (120) g(2) g(122) En règle générale, le niveau de sécurité exigé pour la signature d'un message est plus élevé que celui d'un procédé de preuve interactive de type identification.Il suffira donc d'utilise plusieurs arbres Ti en fonction du niveau de sécurité que l'on désire atteindre. Ainsi, chaque i représente une unité de sécurité. Une preuve d'identité coûtera simplement une unité alors qu'il faudra en utiliser plusieurs pour effectuer une opération de signature. On voit clairement apparaître la notion de dépense à travers le principe des clefs jetables et donc de dépense d'une unité de sécurité pour un service donné. Il peut être intéressant d'assimiler le coût d'une unité de sécurité à celui de la dépense d'une unité monétaire. Le fait de donner les fss-1(Ki,i) correspondra au don d'une unité monétaire mais aussi prouvera qu'une unité monétaire a bien été distribuée. En effet, si quelqu'un donne la même unité à différentes personnes, il fournira de même différentes combinaisons de bj et donc, plus d'informations sur Kij qu'il n'en avait le droit. Le faussaire fournira donc de lui-même les preuves permettant de le confondre. Ainsi le procédé peut s'appliquer à la construction d'un système de paiement électronique. L'initialisation du système se fera par le simple don d'une quantité de monnaie certifiée par l'autorité aux membres du système. Par conséquent, l'introduction de fausse monnaie, du moins au démarrage, pourra être évitée. Les différentes étapes du parcours certifiant selon le procédé vont être développées dans la suite en regard de la figure 2. Conformément au procédé, le grand nombre de clefs utilisées nécessite d'affecter ces clefs aux feuilles d'un arbre dont le rôle est de pouvoir les authentifier. Le parcours certifiant, selon le procédé, consiste à visiter les feuilles d'un tel arbre une par une en conservant en mémoire des données intermédiaires (C) de telle sorte que l'on soit capable à chaque visite de feuille de donner les valeurs de son chemin d'authentification. Pour calculer "progressivement" la valeur (a) pour un noeud a, comme on a p(a)= , #(al) > , p(a2) > ...,0 (a(a-l)) > , on calcule successivement les valeurs , #(a2) > ..., #(aj) > pour j=0 (en convenant =x) jusqu'à j=a-1. Pour effectuer ce calcul, on utilise un accumulateur qui contient successivement ces valeurs. On définit donc la fonction accumulation Acc par Acc(x,c,y)= Y si c=0 si c p 0 Au début du calcul, l'accumulateur est considéré comme vide. Calculer (a) au moyen d'un accumulateur A consiste donc à répéter l'étape suivante de j = 0 jusqu'à j = a-l. Ainsi, calculer (a0a1... ak) consiste à utiliser récursivement ce procédé au moyen de n-k-1 accumulateurs Ak+1,...,An-1 : de Ak+1,...,An-1= 0...0 jusqu'à (&alpha;-1)...(&alpha;-1) de i= n-2 jusqu'à i=p résultat = Ak+l Dans la suite on considère un arbre équilibré de degré a et de hauteur n, en prenant comme exemple a = 3 n = 4 (tel que représenté sur la figure 3). Le parcours certifiant est obtenu à partir des moyens de traitement placés sur le support et à partir des moyens de mémorisation qui comportent outre une mémoire de travail, une mémoire de programme, trois types de registres des registres Ak (0 chaque étage de l'arbre (A0 correspond au niveau des fils de la racine, et An-1 correspond au niveau des feuilles); des registres Mk,j (0 S k correspondent à des listes de a valeurs à chaque étage de l'arbre; des registres Tk,i (2 S k sont des accumulateurs. On souhaite parcourir l'arbre de gauche à droite, c'est-à-dire, dans l'exemple, de la feuille 0000 à la feuille 2222. Le chemin qui va de chaque feuille a0a1a2a3 à la racine sépare les valeurs nécessaires à l'authentification en deux catégories : des valeurs à gauche sont regroupées par étage en ##(a@...ak), et qui seront dans les accumulateurs Ak,et des valeurs à droite qui sont dans des registres Mk,j. On définit donc AK comme étant la valeur hachée des frères de gauche du noeud ....... a, et la liste Mk, comme étant la liste des valeurs du noeud a0a1...ak et de ses &alpha;-1 voisins de droite (qui sont donc des frères et des cousins plus ou moins éloignés). Sur la figure 3, on suppose que l'on visite la feuille, 1201. A0 contient la valeur du noeud 0 qui est l'unique frère de gauche de 1. A1 contient la valeur hachée des valeurs des noeuds 10 et 11 qui sont les frères de gauche de 12. A2 ne contient rien du tout car 120 n'a pas de frère de gauche. . A3 contient la valeur de 1200, seul frère de gauche de 1201. M37 est la liste des valeurs de 1201, 1202 et 1210. M27 est la liste des valeurs de 120, 121 et 122. . M17 est la liste des valeurs de 12, 20 et 21 M07 est la liste inachevée des valeurs de 1 et2 (il n'y a plus d'autres voisins à droite). Une fois la visite d'une feuille terminée, il faut changer les valeurs de certains registres pour préparer la prochaine visite. pour changer les Ak, il suffit d'accumuler des valeurs par hachage à chaque niveau où le parent de la feuille change. Ainsi, pour préparer la visite de 1202, il suffit d'accumuler la valeur de 1201 qui est dans un M3, dans A3, les autres Ak restant inchangés. Après la visite de 1202, pour préparer la visite de 1210, il faudra changer A2 en accumulant la valeur de 120 qui est dans un M2,. Ici, l'opération d'accumulation est une simple opération de stockage, car l'accumulateur A2 est vide. Pour changer les Mk, il suffit de faire "glisser" les fenêtres d'un cran vers la droite. En fait, pour éviter tout décalage en mémoire, on considère qu'une valeur d'un noeud a0a1...ak doit être stockée dans le registre Mk,ak. Ainsi, glisser une fenêtre consiste à récupérer le registre Mk,ak et lui mettre la valeur du a-ième voisin de droite. pour calculer progressivement cette valeur, on a besoin des accumulateurs Tk,i. En fait, les accumulateurs qui calculent la nouvelle valeur de Mk ak, c'est-à-dire la valeur de S(a0a1...ak-1)ak sont les Tk,ak. Dans l'exemple, T3,2 calcule S(12)0=200, et T2,1 et T3,1 calculent S(1)2 = 22. Pour calculer la valeur d'un noeud quelconque, il faut calculer la valeur de ses fils en les accumulant. Ainsi, pour calculer la valeur de 22, on cherche d'abord à calculer la valeur de 220. pour cela, on calcule d'abord la valeur de 2200 que l'on place dans un accumulateur T3,1), on calcule ensuite la valeur de 2201 que l'on accumule, enfin la valeur de 2202. On obtient alors la valeur de 220 que l'on peut ranger dans l'accumulateur T2 1, et chercher à calculer la valeur de 221... Voici la définition formelle des registres, si l'on suppose que l'on visite la feuille a0a1...an-1: Mk,j = #*(Sa0a1...ak-1)J) si j Mk,j = #*(a0a1...ak-1J) si j # Ak = ##(a0a1...ak) si ak t Tk,i = ##(Sa0...ai-1)ai...ak) si ak L'algorithme de parcours mis en oeuvre est décrit formellement sur le tableau A. A la ligne 2, on donne aux registres Mk,j leurs valeurs initiales. A la ligne 3, on effectue l'opération de visite souhaitée sur la feuille a. On peut authentifier O(a) en révélant le contenu des registres Ak pour tout k tel que akt0 et des registres Mk,j pour tout k et tout j tel que ak Pour passer à la feuille suivante,il faut passer, pour un certain nombre de générations, à un parent suivant. passer de a à S(a) revient à ajouter 1 en base a. le nombre de générations où se produit un changement correspond au nombre de retenues effectuées dans cette addition, donc a nombre de chiffres égaux à a-l à droite de a. La ligne 4 de l'algorithme permet de calculer p l'indice du dernier niveau inchangé. la ligne 5 est un test en fin de parcours. A chaque niveau où le voisin de droite ne correspond pas au même père, Ak "vidé mentalement", et au niveau p, on accumule une nouvelle valeur dans ap. La modification des accumulateurs Ak se réduit à l'étape de la ligne 6. Les fenêtres Mk sont décalées vers la droit jusqu'au niveau p. Au niveau n-l, cela se fait par un calcul à l'aide de la fonction # (voir ligne 7). Pour les autres niveaux, il faut utiliser les registres Tk,i(voir ligne 9a). lies accumulateurs Tk,i sont modifiés au niveau n-l à la ligne 8 par utilisation de la fonction . Aux autres niveaux, les modifications sont effectuées à la ligne 9b. Le tableau A suivant donne donc les différentes étapes mises en oeuvre conformément au procédé pour obtenir un parcours certifiant 2. initialiser Mk,j pour O # k 7. Mn-1,an-1 - #(S(a0...an-2)an-1) 8. pour tout i tel que O Tn-1,i - Acc(Tn-1,i,an-1, #(S(a0...ai-1)ai...an-1)); 9. de k = n - 2 jusqu'à k = p : (b) pour tout i tel que 0 11. aller en 3. Ainsi conformément au procédé en choisissant des fonctions de hachage f qui se déroulent en 1 ou 2 ms en prenant des clefs de 16 octets et une sécurité de une chance sur 38165, ce qui correspond à ss=5 et s=8 et par conséquent à un arbre Tk de la figure 1 de degré 8 et de profondeur 5, une opération d'une unité de sécurité (authentification : une unité - signature : trois unités), coûtera environ 50 ms de calcul et le temps de transmission de 128 octets soit 8 clefs (information nécessaire pour parcourir ce petit arbre). Le régénération de certificat prend, dans ce cas, 500 ms de calcul et nécessite de transmettre 224 octets soit 14 clefs (ce qui correspond à a=5 et n=5). Au total on a donc une opération d'une unité: 400 + 50 + 352* 1,6 1000 ms soit 1 seconde. On a, au préalable, enregistré dans le support d'information (carte à puce par exemple), et plus précisément dans la mémoire de type EEPROM, 16 octets qui définissent la clef secrète K et 576 octets, soit 36 clefs, qui sont utilisés pour sauvegarder les valeurs A, M et T des registres durant le parcours, et de plus, le code du programme mettant en oeuvre le procédé qui nécessite environ 500 octets. Dans le cas d'une application monétique au moyen d'une carte à puce, la carte possède, d'après les valeurs citées précédemment, 3125 unités soit environ 700 signatures et 900 authentifications ou 3000 authentifications ou 1000 signatures. A la mise en service de la carte on a enregistré sa clef secrète K et on charge les valeurs initiales des registres A, M et T pour le parcours A chaque opération d'une unité, la carte donne son numéro l'identifiant et son état d'utilisation (nombre d'unités dépensées). Elle reçoit une question ou "challenge" sur un octet pour indiquer la nature de la preuve et donc du certificat demandé. Elle fournit enfin la réponse et certificat en dépensant une unité conformément au procédé qui a été décrit. Le procédé conforme a l'invention peut être implementé sur un composant de type COS ou MCOS 16kbits. REVENDICATIONS 1. Procédé de cryptographie de messages transmis par un support d'informations à un système de traitement et d'exploitation, le support d'information comprenant des moyens de traitement et de mémorisation caractérisé en ce qu'il consiste - à calculer une valeur p(i) à partir de fonctions de hachage f opérées sur une valeur Vi générée par les moyens de traitement du support d'information et successivement sur les résultats obtenus, de manière à obtenir et à mémoriser C valeurs intermédiaires suivant une structure de donnée arborescente dans laquelle (i) est la racine d'un sous arbre, - a transmettre (i) pour un message à transmettre donné, - a transmettre sur requête du système de traitement et d'exploitation c valeurs intermédiaires parmi les C valeurs mémorisées ayant permis d'obtenir p(i), et étant définies à partir d'un chemin d'authentification permettant de remonter jusqu'à la racine p(i) du sous-arbre, - a transmettre n valeurs parmi les C valeurs ou n valeurs étant définies à partir d'un chemin d'authentification permettant de remonter jusqu'à la racine p(n) d'un arbre utilisateur du support, - à transmettre p valeurs parmi les c valeurs, ces p valeurs étant définies à partir d'un chemin d'authentification permettant de remonter jusqu'à la racine p(p) de l'arbre général décrit par la structure de donnée, - à recalculer une nouvelle valeur (i) à chaque message à transmettre et à redéfinir les valeurs intermédiaires c à transmettre après la transmission de la nouvelle valeur p(i). 2. Procédé de cryptographie selon la revendication 1, caractérisé en ce que l'arbre d'authentification est un arbre équilibré de degré a et de profondeur n. 3. Procédé de cryptographie selon la revendication 1 ou 2, caractérisé en ce que le calcul de p(i) est opéré à chaque message émis par le support vers le système d'exploitation et permet d'obtenir une valeur de clef Ki attribuée à l'utilisateur ut du support, chaque clef obtenue pour un même utilisateur étant différente d'un message à l'autre, les clefs déjà utilisées et les valeurs intermédiaires C définissant le parcours pour atteindre une valeur Ki étant effacées des moyens de mémorisation au fur et à mesure du calcul d'une nouvelle valeur ki. 4. Procédé de cryptographie selon l'une quelconque des revendications 1 à 3, caractérisé en ce que la valeur Vi est une valeur pseudo-aléatoire obtenue par combinaison d'une valeur aléatoire et d'une clef secrète (k) stockée dans le support, chaque support ayant sa propre clef secrète. 5. Procédé de cryptographie selon l'une quelconque des revendications, caractérisé en ce qu'il consiste à prendre comme support une carte à puce.