Brevet FR2736485A1 — publié le 19970110

PROCEDE DE TRAITEMENT D'UN SIGNAL NUMERIQUE TEL QUE LE SIGNAL NUMERIQUE EN SORTIE NE PEUT SE DEDUIRE DU SIGNAL NUMERIQUE EN ENTREE, ET UTILISATION DE CE PROCEDE POUR LE CONTROLE D'ACCES ET/OU LA SIGNATURE BINAIRE La présente invention concerne un procédé de traitement d'un signal numérique de dimension k tel que le signal numérique en sortie ne peut se déduire du signal numérique en entrée. Ce type de procédé est particulièrement utile dans les systèmes de communication dits sécurisés. Ces systèmes sont en général des systèmes à accès conditionnel nécessitant l'utilisation d'un mot de contrôle ou d'une signature. Les systèmes mettant en oeuvre ce type de communications sécurisées sont très nombreux. On peut en particulier citer les systèmes de télévision à péage, les systèmes de type bancaire permettant d'effectuer des transferts d'ordre ou tous autres systèmes de même type donnant lieu à des échanges d'informations confidentielles. Dans les systèmes à accès conditionnel, tels que ceux implémentés dans les systèmes de télévision à péage, on utilise en général un signal numérique de n bits formant un mot de contrôle permettant notamment, de commander l'embrouillage et le désembrouillage des informations transmises. Ce mot de contrôle doit être changé fréquemment et est, en général, transféré depuis la station émettrice vers le système récepteur ou terminal. Ce mot de contrôle ne doit être accessible qu'à la personne autorisée. De ce fait, ce mot de contrôle est chiffré durant la transmission vers le récepteur qui est un système sécurisé tel qu'une carte à puce. Ce récepteur est éventuellement appairé à un système de desembrouillage non sécurisé et il fournit alors, à ce dernier le mot, de contrôle après déchiffrement. Pour réaliser ce type de transaction, on utilise un système cryptographique à clé secrète dans lequel l'émetteur et le récepteur partagent un signal numérique commun appelé clé secrète commune. De ce fait, I'émetteur chiffre le mot de contrôle et le récepteur le déchiffre par une opération symétrique. Pour réaliser ce type d'opération, différents procédés de traitement sont connus de l'homme de l'art. Ainsi, on peut citer notamment le système DES pour "Data Encryption Standard". Cette méthode présente l'inconvénient qu'il faut utiliser une fonction réversible afin de chiffrer puis déchiffrer le message. Or certains problèmes ne nécessitent pas l'utilisation d'un signal numérique fixé et significatif qui serait chiffré et déchiffré; il suffit souvent que l'expéditeur et le destinataire puissent partager un signal numérique aléatoire confidentiel. Il suffit alors d'utiliser une fonction à sens unique, c'est à dire une fonction qui ne permet pas de trouver l'image du signal numérique si la dite fonction n'est pas parfaitement connue. En particulier, on peut utiliser une fonction de hachage à clé, le principe de fonctionnement étant connu mais inexploitable sans la clé valide. Ainsi, comme représenté sur la figure 1 qui concerne I'utilisation d'une fonction à sens unique, un signal numérique aléatoire m appelé sélecteur de mot de contrôle, est tiré au hasard par l'émetteur E comportant un circuit de génération de signal numérique aléatoire référencé A. Son image par la fonction à sens unique f est alors le signal numérique aléatoire confidentiel partagé par l'émetteur E et le récepteur R, appelés ci-après mot de contrôle. L'émetteur transmet le sélecteur de mot de contrôle m au récepteur et les deux calculent son image par la fonction de hachage à sens unique f avec la même clé, obtenant ainsi le même mot de contrôle m. La seule contrainte imposée pour la confidentialité est qu'il doit être impossible de calculer le mot de contrôle m à partir du sélecteur de mot de contrôle m sans connaître un certain secret, la clé partagée, qui se trouve dans deux domaines sécurisés: l'émetteur et le récepteur. L'état de l'art est d'utiliser soit des fonctions réversibles cryptographiquement sûres, par exemple le DES, soit d'utiliser des fonctions cryptographiquement faibles dont la seule défense est la complexité calculatoire et le secret de la structure, ce qui revient à dire que la clé est la fonction elle-même et ce qui limite son usage et son universalité. La présente invention a pour but de proposer un procédé de traitement de signaux numériques répondant notamment à ce problème, dans la mesure o la fonction est publique et que seule une clé de taille limitée est gardée secrète. La compromission d'une clé ne met pas en péril les systèmes utilisant le même schéma avec une clé différente La présente invention a aussi pour but de proposer un procédé de traitement qui peut être utilisé dans tous systèmes de transmission de signaux numériques de type sécurisé. En conséquence, la présente invention a pour objet un procédé de traitement d'un signal numérique de dimension k. tel que le signal nurnmérique (y) en sortie ne peut se déduire du signal nurmérique (x) en entrée, consistant à envoyer le signal numérique sur un dispositif réalisant une fonction de hachage à sens unique, ledit procédé étant caractérisé par les étapes suivantes: - on envoie le signal numérique (x) en entrée sur un circuit d'embrouillage optimisé en fonction des caractéristiques de la fonction à sens unique donnant en sortie un signal numérique (x'); - on envoie le signal numérique (x') sur un circuit de formatage donnant en sortie un signal numérique (x"). acceptable par la fonction à sens unique; - on envoie le signal numérique (x") sur un circuit réalisant la fonction à sens unique donnant en sortie le signal numérique (y). Selon un mode de réalisation, la fonction à sens unique est réalisée en multipliant le signal numérique (x") par une matrice M de dimensions n x m dont les coefficients aij sont choisis aléatoirement une fois pour toute. Une fonction de ce type est décrite par exemple dans la demande de brevet français N 92 15915 au nom de Jacques Stern. De préférence, pour notamment, limiter le stockage en mémoire, les coefficients aij de la matrice sont générés par une fonction pseudoaléatoire. Selon ce mode de réalisation, le circuit d'embrouillage est choisi de manière à présenter de bonnes qualités de diffusion, c'est à dire qu'une modification très faible du signal en entrée entratne une grande différence dans le signal en sortie. De préférence, la fonction d'embrouillage est commandée par une clé secrète (S). De même, le circuit de formatage a pour but de transformer le signal en entrée en une donnée de dimension n bits et de poids approximativement d, d étant déterminé par la borne de Gilbert- Warshamrnov: m =n.H2(d/n) o H2(x) est la fonction d'entropie H2(x) = - x 10og2(x) - (1-x) 10og2(1-x). Selon un mode de réalisation préférentiel, m = n/2; alors le poids du signal numérique en entrée de la fonction à sens unique doit être approximativement 0, 1 1 x n. Dans le cadre de la présente invention, les fonctions d'embrouillage et de formatage peuvent être réalisées selon l'une des deux méthodes suivantes, à savoir: - soit un circuit d'embrouillage de type connu et un circuit de formatage dont l'entrée définis une permutation sur un mot binaire de longueur n et de poids d. - soit un circuit unique d'embrouillage et de permutation dont l'entrée et la clé secrète définissent un générateur pseudo-aléatoire biaisé tel que le mot en sortie de longueur n soit avec une très forte probabilité de poids d ou approchant. La présente invention a aussi pour objet l'utilisation du procédé décrit ci-dessus pour générer un mot de contrôle dans les systèmes à contrôle d'accès et en particulier dans le cas d'un système de télévision à péage pour générer le ou les mots de contrôle en utilisant la rnmême fonction à sens unique au niveau de l'émetteur et au niveau du ou des récepteurs. D'autres caractéristiques et avantages de la présente invention apparaîtront à la lecture de la description détaillée de différents modes de réalisation, cette description étant faite avec référence aux dessins ci- annexés dans lesquels: - la figure 1 déjà décrite représente schématiquement I'utilisation d'une fonction à sens unique lors de la transmission d'un signal nurnmérique entre un émetteur et un récepteur; la figure 2 est un schéma représentant un dispositif permettant d'obtenir un signal numérique en sortie qui ne peut se déduire du signal numérique en entrée; - la figure 3 est une représentation schématique d'un autre dispositif permettant d'obtenir un signal numérique en sortie qui ne peut se déduire du signal numérique en entrée; - la figure 4 est une vue schématique d'un dispositif permettant à partir d'un signal numérique en entrée d'obtenir plusieurs signaux numériques en sortie qui ne peuvent se déduire du signal nunmérique d'entrée; - les figures 5 et 6 sont des représentations schématiques utilisant l'un des dispositifs décrits ci-dessus pour réaliser une vérification cryptographique; - la figure 7 est un schéma montrant l'utilisation du dispositif des figures 1 et 2 pour réaliser un générateur aléatoire. Le procédé et le dispositif conformes à la présente invention sont basés sur le problème du décodage par syndrome (SD) décrit dans la demande de brevet français N 92 15915 au nom de Jacques Stern qui peut être explicité de la manière suivante: soit une matrice binaire M et un vecteur binaire y, il s'agit de trouver un vecteur binaire x de poids relativement fort ou relativement faible tel que Mx = y. Par poids, on entend le nombre de bits à 1 dans le vecteur concerné. Le problème posé ci-dessus est en fait très difficile à résoudre par les moyens de calcul connus à ce jour si les dimensions n x m de la matrice M et le poids de Hamming du vecteur x sont choisis judicieusement. On a démontré qu'avec les moyens de calcul actuels, le problème est très difficile lorsque le signal numérique x en entrée présente un poids de Hamming d faible. De manière générale, les paramètres d, n, m donnant le poids de Hamming et les dimensions de la matrice M sont choisis sensiblement sous la borne Gilbert-Warshamov donnant une valeur limite théorique pour le poids minimal d d'un code (n,m) aléatoire, à savoir: m = nH2(d/n) o H2(x) est la fonction d'entropie H2(x) = -x.log2(x) - (1- x).log2( 1 -x) Sur la figure 2, on a représenté schématiquement un dispositif permettant la mise en oeuvre d'un premier procédé de traitement d'un signal numérique tel que le signal numérique en sortie ne peut se déduire du signal numérique en entrée. Dans ce dispositif, le signal numérique en entrée (x) est envoyé sur un circuit d'embrouillage (1) de type connu de l'homme de l'art. Ce signal numérique est un signal constitué par des mots binaires de dimension k. On obtient en sortie un signal numérique (x') définissant une permutation qui est envoyée sur un circuit de permutation (2). Ce circuit possède deux entrées: l'une admet la définition de la permutation, I'autre le mot binaire sur lequel est appliqué cette permutation; en sortie, on obtient le mot permuté. Le circuit reçoit sur la première entrée le signal (x'), sur la seconde entrée une clé secrète (S) qui, dans le mode de réalisation décrit, est constituée par un signal numérique binaire de n bits présentant un poids d tel que défini précédemment. En sortie du circuit de permutation (2), on obtient donc un signal numérique aléatoire (x") comportant n bits et présentant un poids d. Ce signal (x") est envoyé sur un circuit multiplicateur (3) qui procède à la multiplication matricielle du mot binaire de n bits en entrée avec une matrice binaire fixe de dimensions nxm bits. En sortie, on obtient un signal numérique (y) de m bits. Dans le schéma décrit ci-dessus, le signal numérique en entrée (x) est utilisé pour permuter la clé secrète (S). Pour des raisons de sécurité, le signal numérique en entrée est tout d'abord embrouillé et le résultat est utilisé pour définir une permutation sur n bits. L'embrouillage peut être relativement simple, car il suffit que les bits soient bien diffusés, c'est à dire que la valeur d'un bit du signal en entrée influence la valeur de beaucoup de bits en sortie. De nombreuses possibilités sont ici à la disposition de l'homme de l'art, par exemple l'utilisation de tables de correspondance ou de générateurs pseudo-aleatoires. La définition d'une permutation sur n bits peut se faire en définissant l'image de chaque bit ou bien en utilisant un générateur de permutation de type connu de l'homme de l'art, comme décrit par exemple dans l'article de M.Luby & C.Rackoff, 'How to construct pseudo random permutation from pseudo random functions', SIAM.J of computing 17(2) Avril 1988, ce qui demande moins de données en entrée. On peut éviter d'avoir à stocker toute la clé secrète en utilisant une clé à n bits dans laquelle les premiers bits sont à 1 et tous les autres à 0. Dans ce cas, la clé n'est plus secrète, et tout le 'secrets du schéma se trouve dans l'embrouillage du signal numérique en entrée qui doit être suffisamment bon pour la sécurité demandée. La matrice de dimensions mxn bits est constituée de coefficients aij qui ont été choisis aléatoirement une fois pour toute. Cette matrice est stockée dans une mémoire. Pour éviter de mémoriser toute la matrice M, il est possible, de manière connue, de générer chaque coefficient aij par l'intermédiaire d'une fonction pseudoaléatoire. Le signal numérique (y) en sortie présentant une dimension de m bits peut être utilisé comme mot de contrôle dans tous les systèmes à contrôle d'accès. Dans le cas d'un système de télévision à péage, le signal numérique (y) en sortie peut être généré aussi bien au niveau de l'émetteur qu'au niveau du ou des récepteurs. On décrira maintenant avec référence à la figure 3, une autre méthode pour traiter un signal numérique de dimension k tel que le signal numérique en sortie ne peut se déduire du signal numérique en entrée ainsi qu'un dispositif pour la mise en oeuvre de cette méthode. Dans le cas de la figure 3, le signal numérique (Xl) en entrée, qui est un signal comportant k bits, est envoyé sur un générateur pseudo- aléatoire (4) en même temps qu'une clé secrète constituée par un signal numérique (S). Le générateur pseudo-aléatoire est choisi de telle sorte que le signal numérique en sortie présente pour une dimension n un poids de Hamming d fixé avec une forte probabilité, n dépendant du circuit réalisant la fonction unidirectionnelle. Ainsi, en sortie du générateur pseudoaléatoire, on obtient un signal numérique aléatoire (x' 1) de longueur n bits et présentant un poids d'environ d. Ensuite le signal (x'l) est envoyé sur un circuit multiplicateur (5) o il est multiplié par les coefficients d'une matrice fixe présentant des dimensions mxn bits de manière à donner en sortie un signal numérique (Yl) présentant une longueur de m bits. La matrice fixe est une matrice identique à celle décrite avec référence à la figure 2. L'utilisation d'un générateur pseudo-aléatoire de bonne qualité pour obtenir le signal numérique aléatoire assure une diffusion suffisante pour notre application. De ce fait, si la clé reste secrète, I'embrouillage est suffisamment bon pour assurer une bonne sécurité même si le signal numérique en entrée est connu. Toutefois, l'utilisation d'un générateur pseudo-aléatoire pour définir les positions binaires des signaux numériques entraîne un problème. En effet, certaines positions peuvent être produites plus d'une fois. Dans le cas o la mémoire de stockage des positions binaires des signaux est suffisante, on peut simplement éliminer la valeur redondante et en tirer une autre, mais si on ne peut pas les stocker, en particulier lorsque le calcul est effectué dans une carte à puces, alors le poids du signal numérique aléatoire peut être inférieur au nombre de positions tirées. Ceci doit être pris en compte et il est nécessaire de tirer plus d'informations que le poids pour obtenir la valeur souhaitée en moyenne. Lorsque le poids des mots en entrée de la fonction unidirectionnelle n'a pas besoin d'être exactement d, mais peut-être une valeur proche, cette méthode est alors valable à condition de calculer la répartition statistique des valeurs non redondantes. Ainsi, si l'on cherche à obtenir une valeur moyenne de 56 positions non redondantes, on s'aperçoit qu'il faut tirer 59 positions, et on obtient 25% des tirages à exactement 56, 66% entre et 57 et 98% entre 53 et 59. On décrira maintenant un autre mode de réalisation du système permettant de mettre en oeuvre un procédé de traitement d'un signal numérique, tel que le signal numérique en sortie ne peut se déduire du signal numérique en entrée, dans lequel à partir d'un seul signal numérique en entrée on peut obtenir plusieurs signaux numériques en sortie répondant auxdits critères. Comme représenté sur la figure 4, le signal numérique en entrée (x2) est envoyé sur un générateur pseudo-aléatoire (6) en même temps qu'une clé secrète (S). Si le signal en entrée est un signal nurmérique de longueur k bits utilisé pour produire des signaux en sortie (x'2.1), (x2.2)..., (x2),.-- 2,... (x'2.N) présentant des longueurs de n bits et des poids approximatifs di, il est possible de produire Nxn bits alimentant ainsi N multiplicateurs matriciels (M1), (M2), (M3),..., (MN), de manière à obtenir N signaux numériques (Y21, Y22,... Y2N) en sortie ayant chacun une longueur de m bits. La matrice utilisée au niveau des multiplicateurs (M1, M2, M3,... MN) présente les mêmes caractéristiques que la matrice décrite avec référence aux figures 2 et 3. La production de tels signaux selon un mode préférentiel nécessite l'utilisation d'un générateur pseudo-aléatoire fiable permettant de générer environ N x n bits. Les dispositifs décrits ci-dessus peuvent être utilisés dans de nombreuses applications. Ainsi, comme représenté sur les figures 5 et 6, les dispositifs décrits ci-dessus peuvent être utilisés pour calculer un code de détection d'erreurs cryptographique avec des clés secrètes partagées. Ceci signifie que l'émetteur et le récepteur partagent une clé secrète et le code de détection d'erreurs est calculé et vérifié en utilisant cette clé. Comme représenté sur la figure 5, un message (M) est divisé en blocs comportant k bits référencé (Bi), i variant de 1 à n. On définit (CO) comme un signal numérique fixe présentant une longueur de k bits, (C0) pouvant être uniformément nul, le code de détection d'erreurs est défini comme (Cn) o (Ci) est obtenu comme représenté sur la figure 5. Dans ce cas, un dispositif correspondant à l'ensemble des circuits de la figure 2 ou de la figure 3 est référencé (7). Le circuit est défini de telle façon que k=m (la taille du signal en entrée est identique à celle du signal en sortie). Il reçoit en entrée un signal numérique (x3) de k bits issu d'un additionneur (8) qui reçoit sur une entrée un des blocs (Bi) et sur l'autre entrée k bits d'un signal numérique (Ci-1) qui est en fait le signal issu du circuit (7) à l'étape précédente de manière à donner le signal (Ci). Si k est supérieur à m, il existe une autre manière pour rattacher k-m bits d'un message à un mot de sortie. Dans ce cas, le message (M) qui est un mot binaire, est divisé en blocs de k-m bits, (B'1) 2, (B'2),..., (B'n). Comme représenté sur la figure 6, (B'i) est envoyé en entrée d'un circuit de concaténation (9) avec (Ci_1) qui est un signal de taille m bits, le mot binaire (x'3) issu du circuit de concaténation est envoyé sur un circuit (7) tel que défini ci-dessus de manière à obtenir le mot (Ci). D'autre part, le circuit décrit aux figures 2 et 3 peut aussi être utilisé comme un générateur binaire pseudo-aléatoire lorsque le signal en entrée est de taille inférieure au signal en sortie. Par exemple, comme représenté sur la figure 7, si le signal d'entrée est constitué par des mots binaires de k bits, on peut utiliser le schéma suivant: calculer l'image de l'entrée, prendre les m-k premiers bits pour la séquence aléatoire en sortie, et utiliser les k bits suivants pour les envoyer sur un circuit OU exclusif avec le mot d'entrée créant un nouveau mot d'entrée. Ceci est représenté sur la figure 7. Sur cette figure, un mot d'entrée 11 est envoyé sur un circuit OU exclusif 10 qui reçoit sur son autre entrée k bits du mot issu du circuit 7. D'autre part, la sortie du circuit OU exclusif est renvoyée sur le circuit d'entrée 11 et aussi en entrée du circuit 7. Le mot de sortie de m bits issu du circuit 7 est séparé en deux, les m-k bits du début étant envoyés vers la sortie, comme formant la sortie d'un générateur pseudo-aléatoire, le reste étant réinjecté comme vu précédemment. Dans le mode de réalisation représenté, k = m - k = 128 bits. Il est évident que k peut être différent de m - k. Il est évident pour l'homme de l'art que le système décrit ci- dessus peut être utilisé de nombreuses manières dans le domaine de la cryptographie appliqué aux systèmes sécurisés, tels que la télévision à péage, les systèmes bancaires, les systèmes d'accès sécurisé, etc... il 2736485 REVENDICATIONS 1. Procédé de traitement d'un signal numérique de dimension k, dans un système de communication dit sécurisé, tel que le signal numérique (y) en sortie ne peut se déduire du signal numérique (x) en entrée, consistant à envoyer le signal numérique (x) sur un dispositif réalisant une fonction à sens unique, caractérisé en ce que le traitement comporte les étapes suivantes: - on envoie le signal numérique (x, xl) se trouvant en entrée sur un circuit C (1, 2, 4) donnant en sortie un signal numérique (x, x'1) de dimension n acceptable par la fonction à sens unique; - on envoie le signal (x', x'1) issu du circuit C (1, 2, 4) sur le circuit (3, 5) réalisant la fonction à sens unique donnant en sortie le signal numérique (y). 2. Procédé selon la revendication 1, caractérisé en ce que le circuit C est constitué par un circuit d'embrouillage (1) recevant en entrée le signal d'entrée (x) et par un circuit de formatage (2) recevant le signal (x') issu du circuit d'embrouillage et donnant en sortie un signal numérique (x") acceptable par le circuit réalisant la fonction à sens unique. 3. Procédé selon la revendication 2, caractérisé en ce que le circuit de formatage est constitué par un circuit (2) de génération de permutation, la permutation ainsi définie étant appliquée sur un signal numérique de dimension n et de poids de Hamming d. 4. Procédé selon la revendication 1, caractérisé en ce que le circuit C est constitué par un générateur pseudo-aléatoire (4) dont le germe est constitué par le signal (xl) numérique en entrée, le générateur donnant en sortie un signal numérique (x'1) de dimension n et avec une forte probabilité de poids de Hamming d. 5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que le circuit C est commandé par un signal numérique (S) appelé clé secrète 6. Procédé selon la revendication 5, caractérisé en ce que la clé secrète est un signal binaire de dimension n et de poids de Hamming approximativement d. 12 2736485 7. Procédé selon la revendication 1, caractérisé en ce que la fonction à sens unique est obtenue en multipliant un signal numérique (x) sous forme binaire par une matrice binaire. 8. Procédé selon la revendication 7, caractérisé en ce que la matrice est de dimension m x n, n représentant le nombre de colonnes de la matrice. 9. Procédé selon les revendications 7 et 8, caractérisé en ce que la matrice binaire est générée aléatoirement. 10. Procédé selon la revendication 9, caractérisé en ce que les coefficients aij de la matrice M sont générés par un circuit pseudo- aléatoire. 1 1. Procédé selon les revendications 3, 4, 6 et 8, caractérisé en ce que les paramètres d, n, m donnant le poids de Hamming (d) et les dimensions de la matrice M (n, m) sont choisis sensiblement sous la borne de Gilbert-Warshamov, à savoir: m = nxH2(d/n) o H2(y) est la fonction d'entropie: H2(y) = -yxlog2(y) - (1-y)xlog92(1-y) 12. Procédé selon les revendications 3, 4, 6, 8 et 11, caractérisé en ce que les dimensions de la matrice sont n et m=n/2, et que le poids de Hamming (d) est égal à 0, 11xn. 13. Procédé selon la revendication 4, caractérisé en ce que l'on envoie le signal issu du circuit de génération pseudo-aléatoire sur N circuits réalisant une fonction unidirectionnelle de manière à obtenir en sortie N signaux présentant une longueur de m bits. 14. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce qu'il est utilisé pour générer un mot de contrôle dans les systèmes à contrôle d'accès. 15. Procédé selon la revendication 14, caractérisé en ce que, dans le cas d'un système de télévision à péage, le ou les mots de contrôle sont générés en utilisant la même fonction à sens unique au niveau de l'émetteur et au niveau du ou des récepteurs.