FR2887352A1 - Dispositif et procede pour proteger l'integrite de donnees. - Google Patents

Abstract

Par la disposition d'un dispositif de redondance et un dispositif de contrôle avant un dispositif de cryptage qui crypte et décrypte des données à mémoriser dans une mémoire externe peut être assurée l'intégrité de données lorsque la génération d'une information de redondance est réalisée par le dispositif de redondance et la génération d'un vecteur de bits de syndrome est réalisée par le dispositif de contrôle qui indique une éventuelle modification des données. Il est préféré une matrice de contrôle qui est constituée de simples sous-matrices carrées circulantes à faible occupation de même puissance. Par un dispositif de redondance (12) et un dispositif de contrôle (14) avant le dispositif de cryptage/décryptage, il est obtenu qu'il peut être démontré tant des erreurs dans les données cryptées que des erreurs des données non cryptées, pour autant que celles-ci se soient produites dans le trajet de données entre le dispositif de redondance/contrôle et le dispositif de cryptage/décryptage.

Description

2887352 1

Description

Dispositif et procédé pour protéger l'intégrité de données La présente invention concerne un dispositif et un procédé pour protéger l'intégrité de données, tels qu'ils peuvent être utilisés dans le traitement et la mémorisation de données, par exemple, par un microcrontrôleur.

Dans de nombreux scénarios d'application, il. est souhaitable de protéger des données mémorisées contre l'accès par des personnes non autorisées, d'où elles sont mémorisées cryptées dans une mémoire. Les données peuvent être modifiées lors de leur transfert via un système de bus ou pendant leur séjour dans la mémoire par des erreurs se présentant de manière accidentelle, par exemple le basculement d'un seul bit. Un agresseur qui veut altérer la sécurité d'un système par des attaques par erreurs (fault attacks) modifiera délibérément les données mémorisées, lors d'attaques par erreurs étant le plus souvent changé plus d'un bit d'un paquet de données mémorisé ou transféré via un bus. En dehors du cryptage des données mémorisées étant donc nécessaire un dispositif qui puisse identifier une modification accidentelle ou provoquée intentionnellement des données.

Des capteurs sont utilisés par endroits, pour identifier généralement des attaques sur un système. Ces capteurs peuvent être, par exemple, des appareils de mesure de tension, pour identifier des surtensions introduites intentionnellement dans un système. Par ailleurs, il est utilisé des capteurs de température et de lumière pour identifier l'ouverture ou l'ouverture par limage d'un boîtier.

Une autre possibilité de sécurisation consiste à pourvoir les mots de données, avant la mémorisation, d'une information de redondance, l'information de redondance permettant de détecter la modification de bits d'un mot de données mémorisé numériquement et, selon la propriété de l'information de redondance, également de corriger la modification. L'information de redondance est habituellement appliquée, après le cryptage des données, aux informations cryptées, 2887352 2 pour identifier une modification des données cryptées dans une zone de mémoire externe. La demande de brevet allemand 10 2005 001953.6 décrit, par ailleurs, un procédé pour vérifier un ensemble de données composé de plusieurs mots de données, dans lequel un mot de données de redondance a lieu par un traitement "XOR" de tous les mots de données avant le cryptage, l'ensemble de données étant, après la formation de redondance, crypté par mot et mémorisé.

La détection d'une attaque à l'aide de capteurs ne permet pas d'identifier une attaque par erreurs "couvrant la surface" et entraîne des coûts sensiblement plus élevés que, par exemple, un circuit purement numérique. Couvrant la surface signifie ici que tout le trajet des données à partir du moment de la génération des données ne peut pas être surveillé par des capteurs physiques. L'addition d'information de redondance après le cryptage des données présente le grand inconvénient qu'elle ne permet de démontrer que les erreurs qui se produisent dans la mémoire externe. Les erreurs de données qui se produisent accidentellement ou par une attaque dans les données entre l'unité de calcul et l'unité de cryptage ne peuvent pas ètre identifiées. La soumission à un traitement XOR des données avant le cryptage présente l'inconvénient que par suite de la simplicité mathématique, les attaques par traitement XOR ne peuvent être constatées que lorsqu'un nombre impair de bits de données de l'ensemble de données ont été modifiés par l'attaque.

L'objet de la présente invention consiste à créer un dispositif et un procédé par lesquels peuvent être démontrées la modification de données avant le cryptage et la modification de données cryptées.

La présente invention crée un dispositif pour protéger l'intégrité de données, aux caractéristiques suivantes: un dispositif de redondance, pour former, à partir d'une pluralité de mots de données d'un bloc de données, un vecteur de bits de données et générer, par multiplication du vecteur de bits de données par une matrice de génération binaire, un vecteur de bits de contrôle; 2887352 3 un dispositif de cryptage/décryptage destiné à crypter chacun des mots de données, pour obtenir des mots de données cryptés, et à crypter le vecteur de bits de contrôle, pour obtenir un vecteur de bits de contrôle crypté, et à décrypter chacun des mots de données cryptés, pour obtenir des mots de données décryptés, et à décrypter le vecteur de bits de contrôle crypté, pour obtenir un vecteur de bits de contrôle décrypté; un dispositif de contrôle, pour former, à partir des mots de données décryptés ou des mots de données décryptés et du vecteur de bits de contrôle décrypté, un vecteur de bits total et créer, par multiplication d'une matrice de contrôle binaire par le vecteur de bits total, un vecteur de bits de syndrome, de sorte qu'à l'aide du vecteur de bits de syndrome puisse être vérifiée l'intégrité du vecteur de bits total.

Par ailleurs, la présente invention crée un dispositif pour protéger l'intégrité de données, aux caractéristiques suivantes: un dispositif de décryptage destiné à décrypter des mots de données cryptés, pour obtenir des mots de données décryptés et à décrypter un vecteur de bits de contrôle crypté, pour. obtenir un vecteur de bits de contrôle décrypté ; et un dispositif de contrôle, pour former, à partir des mots de données décryptés ou des mots de données décryptés et du vecteur de bits de contrôle décrypté, un vecteur de bits total et à créer, par multiplication d'une matrice de contrôle binaire par le vecteur de bits total, un vecteur de bits de syndrome, de sorte qu'à l'aide du vecteur de bits de syndrome puisse être vérifiée l'intégrité du vecteur de bits total.

Par ailleurs, la présente invention crée un dispositif pour protéger l'intégrité de données, aux caractéristiques suivantes: un dispositif de redondance pour former, à partir d'une pluralité de mots de données d'un bloc de données, un vecteur de bits de données et pour générer, par multiplication du vecteur de bits de données par une matrice de génération binaire, un vecteur de bits de contrôle; 2887352 4 un dispositif de cryptage destiné à crypter chacun des mots de données, pour obtenir des mots de données cryptés et à crypter le vecteur de bits de contrôle, pour obtenir un vecteur de bits de contrôle crypté.

Par ailleurs, la présente invention crée un procédé pour protéger l'intégrité de données, aux étapes suivantes consistant à : décrypter des mots de données cryptés, pour obtenir des mots de données décryptés et décrypter un vecteur de bits de contrôle crypté, pour obtenir un vecteur de bits de contrôle décrypté ; former un vecteur de bits total à partir des mots de données décryptés et du vecteur de bits de contrôle décrypté ; et multiplier une matrice de contrôle binaire par le vecteur de bits total, pour créer un vecteur de bits de syndrome, de sorte qu'à l'aide du vecteur de bits de syndrome puisse être vérifiée l'intégrité des mots de données.

Par ailleurs, la présente invention crée un procédé pour protéger l'intégrité de données, aux étapes suivantes consistant à : former un vecteur de bits de données à partir d'une pluralité de mots de données d'un bloc de données; multiplier le vecteur de bits de données par une matrice de génération binaire, pour générer un vecteur de bits de contrôle; et crypter chacun des mots de données, pour obtenir des mots de données codés et crypter le vecteur de bits de contrôle, pour obtenir un vecteur de bits de contrôle crypté.

La pensée centrale de la présente invention réside dans le fait que par l'aménagement d'un dispositif de redondance et d'un dispositif de contrôle avant un dispositif de cryptage qui crypte et décrypte des données à mémoriser dans une mémoire externe peut être assurée l'intégrité de données, lorsque la génération d'une information de redondance est réalisée par le dispositif de redondance et la génération d'un vecteur de bits de syndrome est réalisée par le dispositif de contrôle qui indique une éventuelle variation des données. Il est préféré une matrice de contrôle constituée de sous-matrices carrées circulantes simplement de même puissance à faible occupation. Par un dispositif de redondance et de contrôle avant le dispositif de cryptage/décryptage, il est obtenu qu'il peut être démontré tant des erreurs dans les données cryptées que des erreurs dans les données non cryptées, pour autant qu'elles se soient produites dans le trajet de données entre le dispositif de redondance/contrôle et le dispositif de cryptage/décryptage. La matrice de contrôle de conception spéciale, composée de sous-matrices carrées circulantes de même puissance à faible occupation et représentant un code de préférence linéaire de protection contre les attaques par erreurs permet, par ailleurs, la mise en oeuvre du dispositif ou du procédé en matériel d'ordinateur, seule une surface de silicium réduite étant requise et la consommation de courant de la mise en oeuvre étant faible.

Dans un exemple de réalisation spécial de la présente invention, le dispositif de redondance et le dispositif de contrôle sont disposés dans la même puce d'ordinateur que le processeur de traitement de données, les mots de données à mémoriser étant pourvus, immédiatement après leur génération, de l'information de redondance par le processeur de traitement de données. Les données sont amenées, avant leur mémorisation dans une mémoire externe, par l'intermédiaire de registres et de mémoires intermédiaires, vers une unité de cryptage qui crypte les données et mémorise les données cryptées dans la mémoire externe. Cet aménagement offre le grand avantage que les données du processeur de traitement de données sont protégées pendant tout le trajet par le système, de sorte que puisse être démontrée une modification des données ou une attaque sur le système, donc tant avant le cryptage des données qu'après le cryptage des données.

Dans un autre exemple de réalisation de la présente invention, le dispositif de redondance est réalisé de sorte que la génération des informations de redondance pour plusieurs mots de données d'un bloc 2887352 6 de données allant ensemble contienne une multiplication d'une matrice d'une matrice de génération par un vecteur de bits de données qui est formé des différents bits des mots de données. La matrice de génération est choisie de sorte que puisse être formée de manière simple une deuxième information de redondance d'un deuxième vecteur de bits de données, lorsque le deuxième vecteur de bits de données diffère du premier vecteur de bits de données précédant d'un vecteur de bits de différence. La deuxième information de redondance peut alors être formée à partir de la première information de redondance, lorsque le vecteur de bits de différence est multiplié par la matrice de génération et que le vecteur de bits de redondance de différence ainsi obtenu est additionné avec le premier vecteur de bits de redondance. Si deux vecteurs de bits de données successifs ne diffèrent que de quelques bits, il peut être obtenu, par cette propriété de la matrice, en cas de mise en oeuvre de la génération de redondance en matériel, une économie d'énergie substantielle, étant donné que seuls les quelques bits qui se modifient doivent être soumis à une opération de multiplication.

Dans un autre exemple de réalisation de la présente invention, les données lues d'une mémoire externe sont vérifiées quant à l'intégrité, après qu'elles aient été décryptées par une unité de décryptage. Par le dispositif de redondance est généré, au moyen de la multiplication d'une matrice de contrôle appropriée aux données décryptées, un vecteur de bits de syndrome. Si ce vecteur de bits de syndrome est le vecteur zéro, il est conclu que les données n'ont été modifiées ni pendant la mémorisation, ni par le cryptage/décryptage. Les données lues sont donc considérées comme étant non manipulées. Si le vecteur de bits de syndrome est différent du vecteur zéro, une erreur d'un bit dans les données peut toujours être corrigé, du fait que l'information de redondance a été ajoutée aux données avant le cryptage. C'est un grand avantage, étant donné que le cryptage des données représente une opération hautement non linéaire, de sorte qu'un mot de données crypté qui n'est modifié qu'en une seule position de bit, donne, après le 2887352 7 décryptage, un mot de données qui sera modifié en plusieurs positions de bit par rapport au mot de données original. Par le dispositif selon l'invention, il est, en particulier, même créé la possibilité de distinguer si les données ont été modifiées par une erreur de 1 bit accidentelle ou si elles ont été modifiées par une attaque sur le système en plusieurs positions de bit.

Dans un autre exemple de réalisation spécial de la présente invention, chaque message, composé de quatre mots de 32 bits est pourvu d'une information additionnelle (un mot de contrôle) qui est calculé à partir du message, le mot de contrôle associé ayant également une longueur de 32 bits. Une vérification de l'intégrité des données a lieu par le fait qu'à partir des quatre mots de message et du mot de contrôle est calculé le syndrome. Le syndrome est alors un autre mot de 32 bits. S'il ne s'est pas produit d'erreur, le syndrome est le mot zéro (ou le vecteur zéro composé de 32 zéros). Inversement, on interprète le fait "syndrome = vecteur zéro" comme s'il ne s'est pas produit d'erreur.

Cette conclusion inverse est correcte avec la probabilité 1 -1/232, pour autant qu'il pouvait se produire une erreur quelconque (un nombre quelconque des 160 bits au total ont été modifiés lors de l'attaque par erreurs). Dans des scénarios d'attaque déterminés, tel que par exemple dans le cas d'erreurs limitées générées par des attaques par de la lumière, par laser, ou par impulsions pendant le transfert du message via un bus ou dans le cas d'erreurs qui ont été provoquées en forçant une seule ligne de bus, la conclusion inverse est toutefois absolument correcte. C'est-à-dire que de telles attaques sont toujours identifiées. L'avantage dans la présente invention réside dans le fait qu'une attaque sur un système peut être démontrée de manière absolument sûre, par la réalisation selon l'invention du dispositif de redondance et du dispositif de contrôle de manière à traiter des mots de 32 bits étant créée la possibilité d'intégrer le dispositif pour protéger l'intégrité des données sans problème dans une architecture de processeur à 32 bits existante.

2887352 8 Ci-après sont décrits en détail des exemples de réalisation préférés de la présente invention, en référence aux dessins joints en annexe, dans lesquels: la figure 1 illustre un dispositif pour protéger l'intégrité de données.

la figure 2 illustre un diagramme d'état qui décrit les états de mots de données lors de l'opération d'écriture.

la figure 3 illustre un diagramme de d'état qui décrit les états de mots de données lors de l'opération de lecture.

les figures 4a à d illustrent une représentation de matrices carrées circulantes de même puissance à faible occupation.

la figure 5 illustre un champ de code destiné à générer un code de produit.

A la figure 1 est représenté de manière schém.atisée un dispositif pour protéger l'intégrité de données selon l'invention. Il est illustré un processeur principal 2 et un système de mémoire 4. Le processeur principal comporte un registre de données 6 destiné à envoyer et recevoir des mots de données, un processeur central 8 qui se compose d'une unité de calcul 10, d'une unité de redondance 12 et d'une unité de contrôle 14. Le système de mémoire 4 comporte une mémoire intermédiaire rapide 16, le soi-disant caché, une mémoire interne 18, une unité de cryptage/décryptage 20 et une mémoire de masse 22. L'unité de redondance 12 est reliée au registre de données 6 par un premier circuit de transmission de données 24 destiné à envoyer des mots de données au registre de données. Le registre de données 6 est relié par l'intermédiaire d'un deuxième circuit de transmission de données 26 à l'unité de contrôle 14, pour envoyer des mots de données du registre de données 6 à l'unité de contrôle 14. Le registre de données 6 est relié au caché 16 par un premier circuit de transmission de données bidirectionnel 28, pour pouvoir échanger des mots de données entre le registre de données 6 et le caché 16. A ce même effet, le registre de données 6 est relié, par l'intermédiaire d'un deuxième circuit de 2887352 9 transmission de données bidirectionnel 30, à la mémoire interne 18. Par l'intermédiaire d'un troisième circuit de transmission de données bidirectionnel 32, le caché 16 est relié à l'unité de cryptage/décryptage 20 qui, à son tour, est reliée, par l'intermédiaire d'un quatrième circuit de transmission de données bidirectionnel 34, à la mémoire de masse 22.

Ci-après est expliqué brièvement le mode de fonction de l'exemple de réalisation à la figure 1, pour la description précise des étapes de procédé sur les mots de données à transmettre lors de la lecture et de l'écriture, il est renvoyé ici aux diagrammes d'état aux figures 2 et 3.

Les mots de données calculés par l'unité de calcul 10 sont assemblés par l'unité de redondance 12 avec un mot de données de redondance qui est calculé par l'unité de redondance 12, de sorte que les mots de données et le mot de données de redondance soient transmis via le premier circuit de transmission de données 24 vers le registre de données 6. Le registre de données 6 peut transmettre les mots de données et le mot de données de redondance, en fonction de la durée de mémoire nécessaire, d'une part par l'intermédiaire du circuit de transmission de données bidirectionnel 30 vers la mémoire interne 18, d'autre part, par l'intermédiaire du circuit de transmission de données bidirectionnel 28 vers le caché 16. Les mots de données et le mot de données de redondance sont transmis du caché 16, par l'intermédiaire du circuit de transmission de données bidirectionnel 32, vers l'unité de cryptage/décryptage 20, où ils sont convertis par l'unité de cryptage/décryptage 20 en mots de données cryptés et mot de données de redondance crypté, chacun des mots de données étant transformé séparément en mot de données crypté. Les mots de données cryptés et le mot de données de redondance crypté sont alors transmis par l'intermédiaire du circuit de transmission de données bidirectionnel 34 vers la mémoire de masse et y mémorisés.

Lors de l'opération de lecture, les mots de données cryptés et le mot de données de redondance crypté sont transmis ensemble, par 2887352 10 l'intermédiaire du circuit de transmission de données bidirectionnel 34, de la mémoire de masse 22 à l'unité de cryptage/décryptage 20 et y décryptés par mot. Les mots de données décryptés et le mot de données de redondance décrypté sont transmis par l'intermédiaire du circuit de transmission de données bidirectionnel 32 au caché 16, d'où ils sont transmis par l'intermédiaire du circuit de transmission de données bidirectionnel 28 vers le registre de données 6. Du registre de données 6, les mots de données décryptés et le mot de données de redondance décrypté sont transmis, par l'intermédiaire du circuit de transmission de données 26 vers l'unité de contrôle 16 qui calcule, à partir des mots de données et du mot de données de redondance, un vecteur de bits de syndrome à l'aide duquel il peut être décidé si les mots de données ont été modifiés sur leur chemin à travers le système de mémoire 4.

Ci-après sont décrites plus en détail, en référence à la figure 1 dans le diagramme d'état à la figure 2, les opérations lors de la mémorisation des données. A la figure 2 est représenté un ensemble de données non crypté 36 qui se compose des mots de données mo à m3, les mots de données mo à m3 étant, chacun, un mot de 32 bits, c'est-à-dire pouvant être représenté comme vecteur de 32 bits successifs.

L'ensemble de données 36 est représenté par un vecteur de bit de données 38 qui est formé en disposant chaque fois les 32 bits des différents mots de données mo à m3 les uns après les autres dans un vecteur. Il est, par ailleurs, illustré un vecteur de bits de contrôle 40, un vecteur de bits total 42 et un vecteur de bits total crypté 44. Lors de l'opération d'écriture, les mots de données sont calculés par l'unité de calcul 10 et transmis comme vecteur de bits de données 38 à l'unité de redondance 12. L'unité de redondance 12 génère, par multiplication du vecteur de bits de donnée 38 par une matrice de génération dans une étape de formation de redondance 46, le vecteur de bits de contrôle 40.

Pendant la génération de vecteur de bits total 48, le vecteur de bits de contrôle 40 et le vecteur de bits de donnée 38 sont assemblés dans le vecteur de bits total 42 par l'unité de redondance 12, le vecteur de bits 2887352 11 de contrôle 40 étant ajouté, comme derniers 32 bits du vecteur de bits total 42, au vecteur de bits de données 38. Pendant l'étape de cryptage 50, le vecteur de bits total 42 est transmis, par l'intermédiaire du registre de données 6 et du caché 16, à l'unité de cryptage/décryptage 20, où ils sont cryptés par mot, de sorte qu'à la sortie de l'unité de cryptage/décryptage 20 soit disponible le vecteur de bits total crypté 44 qui est mémorisé dans une mémoire externe 22. Etant donné que le cryptage se produit par mot, le vecteur de bits total crypté 44 se compose des représentations de bits juxtaposées des mots cryptés mo à m3 et du vecteur de bits de contrôle crypté.

Ci-après sont expliqués en détail, en référence à la figure 3, les différents états des mots de données d'un ensemble de données lu de la mémoire de masse 22, et il est également expliqué la manière dont peut être corrigée une variation des données mémorisées éventuellement démontrée. La figure 3 illustre un ensemble de données crypté et mémorisé 52, qui est représenté par un vecteur de bits total crypté 54, un vecteur de bits total décrypté 56, un vecteur de bit de syndrome 58, des vecteurs de mot de données décryptés 6Oa à 6Oe, des vecteurs de mot de données substitués 62a à 62e et des vecteurs de mot de données substitués cryptés 64a à 6ê4e. Dans la mémoire de masse 22 est mémorisé le vecteur de bits total crypté 54 qui est décrypté par mot, dans une étape de décryptage 66, par l'unité de cryptage/décryptage 20, de sorte que, après que le décryptage, soit disponible le vecteur de bits total décrypté 56 qui se compose des vecteurs de mot de données décryptés 6Oa à 6Oe et qui est transmis, dans une étape de transfert de lecture 68, de l'unité de cryptage/décryptage 20, par l'intermédiaire du caché 16 et du registre de données 6, vers l'unité de contrôle 14. L'unité de contrôle 14 forme, à partir du vecteur de bits total décrypté 56, par multiplication du vecteur de bits total décrypté 56 par une matrice de contrôle binaire, un vecteur de bit de syndrome 58 à l'aide duquel peut être vérifiée l'intégrité du vecteur de bits total décrypté 56. Si le vecteur de bits de syndrome 58 est le vecteur zéro, c'est-à-dire si ses 32 bits 2887352 12 sont tous égaux à 0, il est conclu, dans une étape de confirmation 69, que les données n'ont pas été modifiées ni dans la mémoire de masse 22, ni pendant l'étape de transfert de lecture 68, et il est supposé que le vecteur de bits total décrypté 56 correspond au vecteur de bits total 42 créé pendant l'opération d'écriture.

Si le vecteur de bits de syndrome est différent du vecteur zéro, les données ont été modifiées depuis la création du vecteur de bits de contrôle 40 pendant l'opération d'écriture. Il est tout d'abord supposé qu'un bit de l'un des mots de données a été modifié par accident pendant le séjour des données dans la mémoire de masse 22. Par suite de l'opération de décryptage hautement non linéaire de l'unité de cryptage/décryptage 20 pendant l'étape de décryptage 66, un seul bit modifié avant le décryptage d'un vecteur de mots de données s'exprimera par une pluralité de bits modifiés d'un vecteur de mots de données décrypté, c'est-à-dire qu'un tel vecteur de mots de données décrypté diffère dans une pluralité de bits du vecteur de bits de données à la base de ce dernier. Grâce au dispositif selon. l'invention, il est maintenant néanmoins possible d'identifier une erreur d'un seul bit dans l'un des vecteurs de mots de données cryptés et de corriger celle- ci. Cela est possible grâce à l'information de redondance qui a été ajoutée à l'ensemble de données non crypté pendant l'écriture, tel qu'il sera décrit ci-après.

Si le vecteur de bits de syndrome 58 est différent du vecteur zéro, il est tout d'abord formé, dans une étape de substitution 70, par l'unité de contrôle 14, des vecteurs de mots de données substitués 62a à 62e, les vecteurs de mots de données substitués 62a à 62e étant formés en fonction des vecteurs de mot de données décryptés 6Oa à 6Oe, ce qui est possible par suite de l'information de redondance additionnelle. Suivant notre supposition qu'un seul des mots de données du vecteur de bits total crypté 54 est concerné par une erreur de bit, il existe alors exactement un vecteur substitué de mots de données 62a à 62e qui ne 2887352 13 dépend que des 4 mots de données décryptés sans erreur des vecteurs de mots de données 6Oa à 6Oe.

Dans une étape de vérification 72, les vecteurs de mots de données substitués 62a à 62e sont décryptés par rnot codé par l'unité de cryptage/décryptage 20, de sorte que soient obtenus les vecteurs de mots de données substitués cryptés 64a à 64e. Dans une étape de comparaison 74 sont alors formés, par l'unité de contrôle 14, les distances de Hamming entre les vecteurs de mots de données substitués cryptés 64a à 64e et les mots de données du vecteur de bits total crypté 54 leur associés. Si une erreur dans une mot de données du vecteur de bits total crypté 54 a été provoquée par une erreur d'un seul bit, la distance de Hamming entre le mot de données concerné et son partenaire substitué crypté sera exactement de 1 et le vecteur de bits total décrypté 56 peut, dans une étape de reconstruction 76, être reconstruit entièrement exempt d'erreur. Si aucun des mots de données de l'ensemble de données crypté 52 ne présente une distance de Hamming de 1 par rapport à son vecteur de mots de données substitué crypté lui associé, il est supposé, dans une étape d'erreur 78, que plus de 1 bit de l'ensemble de données crypté 52 a été modifié par une attaque, de sorte que des mesures appropriées peuvent être prises pour contrecarrer l'attaque.

Dans un autre exemple de réalisation spécial de la présente invention, un code linéaire pour la protection contre des attaques par des erreurs est défini ou réalisé par une matrice de contrôle de conception particulière. Ci-après sont présentées brièvement les considérations de principe nécessaires pour la conception du dispositif selon l'invention pour protéger l'intégration des données. La condition de base requise pour développer une identification d'erreur (EDC) ou un code de correction d'erreur (ECC) pour un système est l'adoption d'un modèle d'erreur. Le modèle d'erreur est une abstraction mathématique de possibles erreurs.Dans le présent cas, le modèle d'erreur doit tenir compte des effets de possibles attaques sur le système. Etant donné 2887352 14 qu'un microcontrôleur est un système extrêmement compliqué, le système est tout d'abord subdivisé en petits sous-systèmes dont le comportement peut être modelé plus simplement. A la fin des considérations, un modèle d'erreur général du système d'ensemble doit à nouveau être synthétisé à partir des différents blocs de fonction des sous-systèmes. Dans le présent exemple de réalisation, il est tenu compte d'un registre de données 6 présent sur le trajet de données, d'un caché 16, d'une mémoire interne 18, d'une unité de cryptage/décryptage 20 et d'une mémoire de masse 22, tel que visible à la figure 1.

Ci-après sont exposées les suppositions relatives au scénario d'attaque faites pour le développement de la présente invention.

Il existe de nombreuses formes d'attaque qui ont un caractère local, c'est-à-dire où l'agresseur a la possibilité de modifier des bits individuels. Un agresseur professionnel pourrait avoir la possibilité de modifier de manière contrôlée des bits individuels (en utilisant par exemple un rayon laser concentré) ou d'utiliser des microsondes. D'autres formes d'attaque modifient des bits individuels ou des groupes de bits de manière arbitraire. Si l'agresseur utilise, par exemple, un rayonnement ionisant en rapport avec un dispositif de diaphragme pour sélectionner des groupes de bits individuels, il est à même de modifier arbitrairement des groupes de bits individuels. Une adaptation de l'intensité de rayonnement pourrait même permettre d'affiner l'attaque en ce sens que le poids d'un vecteur d'erreur soit maximisé. Le vecteur d'erreur est un vecteur composé de nombres binaires qui présente, aux positions des bits modifiés, un 1 et, aux positions restantes, un O. Des surtensions de faibles durée ou des attaques à forte surchauffe locale (par exemple, variations de tension induites par la température) peuvent entraîner des erreurs de bit arbitraires. Des attaques moins sophistiquées (nonobstant très efficaces), telles qu'une irradiation d'un système par de la lumière (flash light attacks) ou une modification du cycle d'horloge d'un circuit peuvent entraîner des "paquets" d'erreurs, 2887352 15 c'est-à-dire qu'un plus grand nombre de bits sont amenés dans le même état logique, donc 1 ou O. Il n'y a toutefois pas de connaissance fondée sur les caractéristiques ou les rapports qui provoquent des paquets d'erreurs, il existe toutefois quelques indications que, dans le cas de nombreuses de telles attaques, des bits voisins sont avec une plus grande probabilité commutés au même état. C'est pourquoi, nous supposons, pour les considérations futures, le pire cas où toutes les erreurs avec des poids de 1 à 160 présentent la même probabilité, c'est-à-dire donc que, après une attaque, toute combinaison binaire d'un vecteur de bits de données d'une longueur de 160 bits se présente avec la même probabilité.

Ci-après sont discutées brièvement, sur base de cette supposition, les conditions de sécurité requises pour une identification d'erreur et une correction d'erreurs efficaces. Il est tout d'abord supposé qu'un agresseur réalise une attaque automatisée, où il peut réaliser 10 attaques par des erreurs par seconde et qu'il laisse se produire les attaques en continu pendant une période d'un mois, d'où il s'ensuit un nombre total d'attaques de * 30 * 24 * 3600 = 2,59 * 107<225 La probabilité qu'une attaque individuelle ne soit pas identifiée est de 1:232. Ainsi, la probabilité qu'une attaque ne soit pas découverte en tout un mois est inférieure à 1% lorsqu'on considère le scénario d'attaque illustré ci-dessus.

Ci-après est donné un bref aperçu de différentes possibilités de mise en oeuvre d'un procédé de correction d'erreurs. Tout d'abord, il y a lieu de considérer en détail les codes d'erreur linéaires. Dans le cas d'un code systématique, k bits d'information ala2... ak sont enrichis au moyen de n k bits de contrôle ou de vérification, pour former un mot de code c = ala2... an de longueur n. Il est donc d'application C = alaza3... ak ak+ lak+Z...an bits d'information bits de contrôle La quantité C de tous les mots de code est une sous-quantité de IF,", IF2 = {0,1} étant la quantité des nombres binaires. Lorsque C ç IF," est un sous-espace linéaire de IF2" à la dimension k, on parle d'un code (n, k) linéaire (binaire systématique). Ci-après sont traités de tels codes dans lesquels n = 160 et k = 128. A des fins d'illustration, il est utilisé, par ailleurs, un exemple de simplification d'un code (n, k) linéaire avec n = 7 et k = 4. Un code (n, k) linéaire peut être décrit de manière univoque au moyen de sa matrice de contrôle de parité (parity check matrix) H. La matrice de contrôle de parité H est une matrice (n - k) x n binaire de rang n - k. Elle a la forme H = (A, In-k), In-k étant la matrice unitaire (n k) x (n - k). Le vecteur de ligne c E IF2n est un mot de code lorsque, et uniquement lorsque, He. O. Ici, cT signifie la transposée de c. Lorsque c est un vecteur de ligne, cT est un vecteur de colonne.

Comme exemple sert dorénavant un code (7,4) linéaire qui est défini par sa matrice de contrôle de parité 1011 100 H= 1101 010 1110 001) On notera que les quatre premières colonnes de H forment une matrice A, les trois dernières colonnes formant la matrice unitaire I3. On peut facilement vérifier que c = (1,1,0,0,1,0,0) est un mot de code, étant donné qu'est d'application HcT = (0,0,0), que le résultat de l'opération précédente est donc le vecteur zéro.

Ci-après est décrite plus en détail l'opération de formation du mot de redondance, de soi-disant codage. Lorsque H = (A,In-k) est la matrice de vérification de parité d'un code (n, k) linéaire binaire, on appelle la matrice k x n G = (Ik, AT) 2887352 17 la matrice de génération canonique du code. Le codage du mot de données a = ala2... ak pour obtenir le mot de code correspondant c = ala2... ak ak_1... an est effectué au moyen d'une multiplication de matrice aG = c.

Cela est équivalent à = ala2...ak AT = ak+l...an bots d'information bits de contrôle En prenant l'exemple précédent, la matrice de génération canonique G correspondante pour la matrice de contrôle de parité H de 10 l'exemple est donc la matrice 4 x 7 1000 111 011 G= 0010 101 \0001 110) Le mot de données (al, a2, a3, a3) E IF24 est donc codé par l'opération suivante pour obtenir le mot de code: c = (a,,a2,a3,a4) G=(al,a2,a3,a4,al +a3 +a4,a, +a2 a 1 + +a2 + a3) Cela est équivalent au fait qu'à partir des bits d'information ala2a3a4 sont calculés les bits de contrôle correspondants selon la règle suivante: (a,,a2,a3,a4) = (al + a3 +a4,a, + a2 +a4,a, +a2 +a3) 101 bits d'information bits de contrôle \110 Remarque: On notera que la matrice de contrôle de parité H a un même nombre de uns dans chacune de ses trois lignes. Cette propriété est souhaitée pour une mise en oeuvre en matériel efficace de la procédure de codage. C'est précisément dans ce cas que le calcul de chacun des bits de contrôle (n-k) requiert le même nombre de liaisons XOR, c'est-à-dire qu'il ait la même profondeur logique. Une autre propriété souhaitable est que H soit à faible occupation, une matrice 2887352 18 binaire H étant appelée à faible occupation lorsqu'elle présente relativement peu de uns.

Ci-après est examinée plus en détail l'opération de décodage, donc de vérification d'un mot de données à vérifier quant à une modification, tel qu'elle est effectuée dans l'exemple de réalisation selon l'invention à la figure 1 par l'unité de contrôle 14.

Supposons que x, y soient, pour les considérations suivantes, deux vecteurs binaires. La distance de Hamming d(x, y) entre x et y est le nombre des coordonnées dans lesquelles x et y sont différents. Le poids de Hamming w(x) de x est le nombre de coordonnées du vecteur x qui ne sont pas O. Par conséquent, on a donc w(x) = d(x, 0) et d(x, y) = u'(x -y) .

Lorsque C désigne un code, le nombre d = min d(u,v) u,vcc est appelé la distance minimale de C. La distance minimale d'un code linéaire C est le poids minimum (poids de Hamming) de chaque mot de code qui n'est pas O. Il est donc d'application: d = min W (c) o*cEc Si H est la matrice de vérification de parité d'un code linéaire, dans ce cas, et seulement dans ce cas, le code a une distance minimale d lorsque les d - 1 colonnes de H sont linéairement: indépendantes et que les d colonnes sont linéairement dépendantes.

Cela est équivalent, dans le cas des codes binaires, à la définition de la distance minimale d, telle qu'elle a été rencontrée plus haut. Ces propriétés sont, ci-après, à nouveau appliquées à ]!.'exemple présenté plus haut, la matrice de contrôle de parité H étant considérée. Toute combinaison de trois colonnes de H sont linéairement indépendantes, quatre colonnes étant chaque fois linéairement dépendantes. Ainsi, le code linéaire correspondant à la matrice H a la distance minimale d = 4.

Un code linéaire avec une distance minimale d de nombre pair peut en même temps corriger (d - 2)/2 erreurs et identifier d/2 erreurs. Supposons que le message a E IFs ait été codé, pour obtenir le mot de code c E IF,' et ensuite transmis via un canal affecté de bruit (ou mémorisé dans une mémoire de masse). Il est reçu le vecteur y e IF," . S'il se produit pendant la transmission (ou la mémorisation) moins de (d -1)/2 erreurs, le mot de code correct c peut être reconstruit, du côté du récepteur, à partir de y. Pour obtenir cela est nécessaire le soi-disant syndrome.

Le syndrome est défini comme suit: Soit H la matrice de vérification de parité d'un code (n, k) linéaire C. Le vecteur de colonne S(y) = HyT de longueur n - k est alors appelé syndrome de y e IF2" . Sur base de la définition de la matrice de contrôle de parité H, y e IFZ" est un mot de code lorsque, et seulement lorsque, S(y) est le vecteur zéro.

Il s'ensuit également que, pour un code binaire, le syndrome est égal à la somme des colonnes de la matrice de contrôle de parité H dans lesquelles s'est produite l'erreur. De cette manière s'explique également le nom syndrome de S(y), étant donné que le syndrome indique les symptômes des erreurs (errors).

Ci-après, la connaissance ci-dessus est appliquée au code (7, 4) linéaire de notre exemple qui est défini par la matrice de contrôle de parité 1011 100 H= 1101 010 1110 001 A cet effet, il est tout d'abord supposé que soit reçu le vecteur y = (1,0,1,0,0,0,1). Le calcul du syndrome donne le résultat suivant: (0 S(y) = HyT = 1.

2887352 20 Le syndrome S(y) coïncide avec le deuxième vecteur de colonne de la matrice H, ce qui indique que la deuxième coordonnée de y est erronée. Le mot de code correct est donc c = (1,1,1,0,0,0,1) et les bits porteurs d'informations sont 1110.

Dans le cas du code qui est décrit dans l'exemple de réalisation selon l'invention ci-après, les sous-matrices qui forment la matrice de contrôle de parité d'un code linéaire sont formés par des matrices circulantes, d'où les propriétés des matrices circulantes pertinentes pour l'invention sont brièvement discutées ci-après.

Une matrice circulante de l'ordre n est une matrice n x n carrée qui est entièrement déterminée par sa première ligne. Dans chaque ligne suivant la première ligne, les différents éléments de matrice sont décalés exactement d'une position vers la droite, les éléments de matrice déplacés hors de la matrice étant à nouveau insérés dans la rangée, du côté gauche. Par exemple, "abcde" eabcd Z = deabc cdeab bcdea est donc une matrice circulante de l'ordre 5. Pour cette matrice est utilisée ci- après également la notation Z = [a, b, c, d, e].

Lorsque A et B sont deux matrices circulantes de l'ordre n, le produit C = AB est à nouveau une matrice circulante l'ordre n.

La quantité des matrices n x n binaires non singulières (c'est-à-dire pouvant être inversées) forment un groupe dans la multiplication de matrice, le groupe linéaire général GL(n, IF2). La quantité de toutes les matrices circulantes non singulières binaires est 'un sous-groupe de GL(n, IF2). Lorsque A est une matrice n x n circulante binaire non singulière, il y a au moins un nombre entier positif e, de sorte que Ae = In., In désignant la matrice unitaire nx n. Il s'ensuit que Ae-1 doit être l'inverse de la matrice A, lequel est également désigné par A-1.

2887352 21 Une propriété des matrices circulantes est le fait que l'inverse d'une matrice circulante non singulière est, à son tour, une matrice circulante. Le calcul du produit d'une matrice circulante A et d'un vecteur de colonne u peut être mis en oeuvre, à l'aide d'un circuit logique, en matériel avec économie de place et de courant. Soit Au = x, donc ra, a an vu1 /x, an a, an-, u, x2 a2 a3 a1 / \un / \xn / Cela est équivalent à x1 =a1u1 +a2u2 +...+anl[n, x2 =anu1 +alu2 +...+an-fun, x,, =a2u1 +a3u2 +...+alun.

Pour mettre en ouvre en matériel les équations ci-dessus, il est requis un registre à n bistables qui contient les entrées des coordonnées de u. Chaque bistable a une sortie qui est reliée à un multiplicateur de constante. Ce multiplicateur de constante a une entrée et fournit, comme résultat d'une opération, le produit de l'entrée avec une constante binaire ai. Les sorties des n multiplicateurs de constante sont soumis à une opération XOR entre elles, pour générer ainsi un seul résultat commun.

Au début d'une opération de matrice, telle que représentée ci-dessus, le registre est rempli par les bits de données ul, u2, ...,un. De ce fait, le résultat produit décrit par le matériel ci-dessus sera xi. A l'étape suivante, les contenus des bistables sont tournés d'une position vers la gauche, de sorte que le registre contient alors les nombres binaires U2, u3, ... , un, Ui.

Le résultat de l'aménagement de matériel ci-dessus sera donc, dans cette étape, x2. Cette opération est répétée jusqu'à ce que soient calculées toutes les coordonnées xi, x2, ..., Xn.

2887352 22 Dans les paragraphes suivants est décrit, comme exemple de réalisation spécial de la présente invention, un code de construction spéciale qui est utilisé dans l'unité de redondance 12 et l'unité de contrôle 14. Les points forts de la conception étant la possibilité d'intégrer le code de manière efficace en matériel et d'entraîner, lors de l'exécution du code dans l'unité de redondance et l'unité de contrôle 14, une consommation de courant aussi faible que possible. La réalisation de cette exigence spéciale sera encore expliquée plus particulièrement à un endroit donné.

Le code selon l'invention (ECC 160) est un code (160, 128, 4) linéaire systématique spécial. Cela signifie donc qu'aux 128 bits porteurs d'informations sont associés 32 bits de contrôle, pour former ensemble un mot de code de longueur 160. La distance de Hamming entre différents mots de code est d'au moins 4. La matrice de contrôle de parité H = (A, I32) est une matrice 32 x 160, I32 décrivant la matrice unitaire 32 x 32. H a donc 32 lignes et 160 colonnes. La matrice 32 x 128 A est de forme A = (Ao, Ai, A2, A3), pour chaque j = 0, 1, 2, 3, la sous-matrice Ai étant une matrice binaire non 32 x 32 circulante non singulière à faible occupation qui a la propriété que A. =132. Cette propriété signifie que Ai est identique à son inverse A;' (de même puissance). Les matrices Ai sont: Ao =[10000100 00000000 00000100 000000001 A1=[10000010 00000000 00000010 000000001 A2 =[10000001 00000000 00000001 000000001 A3 =[10000000 10000000 00000000 100000001 la convention ayant été utilisée que les matrices cm-culantes peuvent être représentées de manière univoque par indication de leur première ligne, tel qu'expliqué dans le paragraphe précédent. Les matrices Ai 2887352 23 étant choisies parmi le choix de matrices circulantes Pi de même puissance, 0 s i 14, qui sont indiquées aux figures 4a à 4d.

Les figures 4a à 4d illustrent les 15 matrices binaires 32 x 32 circulantes à faible occupation non singulières possibles qui présentent la propriété d'être de même puissance. Tel que visible en référence à une première ligne 100 de la matrice Po et à une deuxième ligne 102 de la matrice, une ligne 102 de la matrice suivant la première ligne 100 se produit en ce que les entrées de la deuxième ligne de matrice 102 sont décalées, chacune, d'une position vers la droite par rapport aux entrées de la première ligne de matrice 100. Pour le code selon l'invention, il est choisi, parmi les matrices possibles, les matrices suivantes: Ao = P4 A2 = P5, A2 = P6, et A3 = P7.

Pour les considérations mathématiques suivantes seront utilisées les conventions suivantes concernant la notation. Si v = (vo, vi, ..., vn_1) est un vecteur de ligne, la transposée vT du vecteur de colonne correspondant à v est: (v

T V = vl

\vn-1 i Pour les deux cas, nous écrivons v E IF2 et vT E IFz. Par ailleurs, il est d'application que, lorsque A est une matrice m x n, la transposée 20 de A, donc AT, est une matrice n x m dont la j-ième colonne est la transposée de la j-ième ligne de A, 1 < j m.

Cela sera expliqué à l'aide de l'exemple suivant: (10\ X110" T Si A = A = 11 011 ' Les étapes de traitement de base à réaliser par l'unité de 25 redondance 12 et l'unité de contrôle 14 à l'aide du code 160 ECC sont présentées dans les paragraphes suivants.

2887352 24 Il est tout d'abord présenté le codage d'un message au moyen de l'unité de contrôle 12, lequel est représenté de manière schématisée, dans le diagramme d'état à la figure 2, par la formation de redondance 46 et la génération de vecteur de bits total 48 suivante. Comme exemple sert un message m e IF,'" composé de quatre mots de 32 bits: m = (mo, m:, m2, m3) Coder signifie ici calculer un autre mot de 32 bits x, que l'on appelle le mot de redondance ou le vecteur de bits de contrôle 40, et le rattachement successif du mot de redondance au message m (ou au vecteur de bits de données 38), pour former le vecteur de bits total 42. Le vecteur de ligne de 160 bits qui en résulte c = (m, r) = (mo, ml, m2, m3, r), est appelé mot de code. Le mot de redondance r du message m est calculé selon la formule suivante: r _ mAT équation 1 Cela peut être représenté, alternativement, également comme suit: r=moAô + miAIT +m2A2 + m3A3 Ci-après est décrite la manière dont il est vérifié par l'unité de redondance 12 s'il s'agit ou non, pour un message d'une longueur 160 bits reçu, d'un mot de code. Dans un monde idéal dans lequel il n'y a pas d'erreurs de bit accidentels et pas d'agresseurs qui provoquent délibérément des erreurs, tous les mots de données se présentant dans un microprocesseur sont des mots de code. S'il se présente maintenant une erreur de 1 bit à un endroit quelconque d'un mot de données codé par l'unité de redondance 12 et crypté dans l'unité de cryptage/décryptage 20 dans la mémoire de masse 22 ou une erreur de 1 bit dans un bit quelconque des 160 bits d'un message y, par exemple dans le caché 16, cette erreur est identifiée et corrigée par le code ECC 160. Des erreurs plus grandes (qui ont été provoquées, par exemple, par 2887352 25 une microsonde, des attaques par de la lumière ou une surtension, etc.) sont identifiées avec une probabilité de 1: 2 32.

Supposons ci-après, comme information de 160 bits y, un vecteur de ligne, donc y e Pour vérifier si y est un mot de code, il est calculé par l'unité de contrôle 14 le syndrome S(y) de y, ou le vecteur de bits de syndrome 58, qui est un vecteur de colonne de 32 bits. Le vecteur y est précisément un mot de code lorsque S(y) est le vecteur zéro. Le syndrome S(y) est formé selon la règle suivante: S(y) = HyT H est la matrice de contrôle de parité, telle qu'elle a été présentée dans les paragraphes précédents. Le rapport suivant est donc d'application: y est un mot de code a S(y) = 0 Pour mieux comprendre la probabilité avec laquelle peut être démontrée une attaque sur le système par le code, il est expliqué brièvement ci-après l'effet sur un système d'un vecteur d'erreur introduit dans le système. A cet effet, on part tout d'abord d'un mot de code c E IF2 6 . Si c est modifié comme résultat d'une attaque extérieure dans y e IFZ160, on peut décrire la modification, donc l'attaque par le fait que l'on ajoute un vecteur d'erreur e E IF260 au mot de code e (= soumission à une opération XOR par bit). Selon le type d'attaque, le vecteur d'erreur e peut être un vecteur arbitraire. Il est donc également d'application y = c + e et on obtient lors de la formation de syndrome: S(y)=HyT =HcT +HeT =HeT.

Par conséquent, une d'attaque par une erreur ne reste inaperçue que lorsque, et uniquement lorsque, le vecteur d'erreur e est également un code de mot. Si e est un vecteur de 160 bits arbitraire, la probabilité que e est un mot de code est de 1: 232.

2887352 26 Une autre propriété que présente le code spécial selon l'exemple de réalisation de la présente invention est la possibilité de pouvoir corriger de manière efficace et rapide une erreur de 1 bit. S'il se présente une erreur de 1 bit dans les 160 bits du message y quelque part entre l'unité de cryptage/décryptage 20 et l'unité de contrôle 14, cette erreur peut être corrigée par le code ECC 160 selon l'invention en une ou deux étapes de calcul.

Cela sera décrit brièvement ci-après, où tout d'abord y e F2160. Pour la vérification de y, il est tout d'abord formé le syndrome S(y) - -I0 HyTe 1E2' 60. Si le syndrome est différent du vecteur zéro et que S(y) est égal à l'un des 160 vecteurs de colonne de la matrice de contrôle de parité H=(A,I32)_(ho,hl,...,h159),, par exemple, s'il est d'application S(y) = il peut en être conclu que la coordonnée y = (yo, yi, ..., y159) est erroné. Pour corriger l'erreur, il suffit de remplacer y par y + 1. Du fait de la forme spéciale de la matrice de contrôle de parité H, on obtient la propriété que, en cas d'erreur, le syndrome S(y) correspond à l'une des 160 colonnes de la matrice H. La localisation de cette colonne spéciale en une ou deux étapes de calcul est possible lorsqu'on intègre en outre une logique spéciale dans le matériel.

Ci-après est expliquée plus en détail la correction d'erreurs de 1 bit, telles qu'elles se présentent dans la mémoire de masse 22, ces erreurs de 1 bit pouvant être corrigées par l'unité de contrôle 14.

Pour les considérations suivantes, l'on part d'un mot de code c = (mo, m m2, m3, r) e F26o Dans une mémoire non volatile 22 (NVM, RAM ou ROM) est mémorisée une version cryptée du mot de code, le mot de code ayant été crypté par l'unité de cryptage/décryptage 20 (MED). Pour les considérations faites ici, le cryptage représente l'espace IF232 en soi, ce qui signifie: 27 MED:aEIF:" MED(a)EIFF32.

A partir de ce moment, MED-' désigne l'opération inverse au cryptage de l'unité de cryptage/décryptage 20. L'opération dans laquelle la MED est appliquée à un argument a e IF232 est appelée cryptage.

L'opération inverse, donc l'application de MED-' sur un argument b E F2'2 est appelée décryptage.

Une caractéristique importante pertinente pour la sécurité de la MED est le soi-disant effet d'avalanche: Lorsque deux arguments a et a' ne sont différents que dans l'une de leurs positions binaires, MED (a) et 10 MED (a') seront différentes dans environ la moitié de leurs bits. De manière équivalente, lorsque b et b' de IF2 2 sont différentes dans un bit, MED1(b) et MED-' (b') différeront généralement dans un nombre du bits qui est en moyenne de 16.

Le mot de code c = (mo, mi, m2, m3, m4) E IFF 6 avec m4 = r est crypté en appliquant la fonction MED séparément à chaque mot mi E IFF 2 individuel. De ce fait, pendant l'étape de transfert 50, un vecteur de bits total 42 devient un vecteur total de bits total crypté 44. Par conséquent, le vecteur de données suivant sera mémorisé dans une mémoire non volatile: (MED(m ), MED(ml), MED(m2), MED(m3), MED(m4)) . Il se produira de temps en temps une erreur de 1 bit accidentelle, une soi- disant "moving bit error". Etant donné que c'est là un cas qui ne se présente que très rarement, on peut supposer que dans la plupart de ces cas, seul un bit des 160 bits de l'information mémorisée est modifié.

Ci-après, il est supposé qu'un mot de l'équation ci-dessus présente une erreur de 1 bit, les autres quatre mots étant corrects. Si le vecteur de ligne de 160 bits décrit ci-dessus est lu, il est décrypté par la MED et l'unité de contrôle 14 reçoit le vecteur de 160 bits suivant comme vecteur de bits total décrypté 56: = (p ,Y,'Y25y3,.v4) 2887352 28 Pour quatre des indices j {0,1,2,3,4} vaut le fait que les mots de données originaux correspondent aux mots de données lus et décryptés, donc que y; = toutefois, il existe un indice pour le y 0 m;. Du fait de l'effet d'avalanche décrit ci-dessus, y; et m; diffèrent en plus d'une position binaire.

Pour la vérification par l'unité de contrôle 14, il est tout d'abord supposé que y est un vecteur de bits total décrypté 56 provenant de l'unité de cryptage/décryptage 20 après une opération de lecture. Il est tout d'abord calculé le syndrome S(y). Si S(y) = 0, il est supposé qu'il ne s'est pas produit d'erreur, en particulier pas de moving bit error'. Si S(y) # 0, il existe en principe deux possibilités: i) il s'est produit une moving bit error' ; ii) il s'est produit plusieurs erreurs, probablement comme résultat d'une attaque sur le système.

Pour décider ce qui est le cas et pour corriger, dans le cas i), la moving bit error', le dispositif selon l'invention procède tel que décrit ci-après. L'on se base tout d'abord sur l'hypothèse qu'il s'est produit une moving bit error' dans le mot MED(r) mémorisé. Dans ce cas, y4 # r, mais également y; = m; pour tous les j = 0,1,2,3.

Aussi, le dispositif selon l'invention exécute l'algorithme suivant: 1. Calcule x4 = (yo, yi, y2, y3) AT.

2. Calcule MED(x4) et MED(y4).

3. Calcule d = dist(MED(x4), MED(y4), (il est rappelé ici le fait que pour u, v E IF2k, d:ist (u, v) désigne la distance de Hamming entre u et v).

Si d = 1, l'hypothèse faite ci-dessus est confirmée. Dans ce cas, y4 est remplace par x4, pour obtenir alors le mot de code corrigé C _ (YO) Y,,Y2, Y3,x4) e IF d'où la moving bit error' a donc été corrigée.

2887352 29 Si d o 1, l'hypothèse ci-dessus doit être rejetée. Comme hypothèse suivante, il est alors supposé qu'il s'est produit une moving bit error' dans MED(mo), de sorte que yo 0 mo et y, = mj pour tous les j = 1,2,3,4.

L'algorithme à exécuter est alors comme suit: 1. Remplace dans (yo, yl, y2, y3) le mot yo par le mot zéro 0 E IF'' et calcule q = (yo, y', y2, y3) AT.

2. Calcule b = q+r, r = y4.

(le signe "+" décrit l'addition par bit modulo 2, c'est-à-dire la soumission par bit à une opération XOR).

3. Calcule = xô = AobT, Ao étant les 32 x 32 sous-matrices de la matrice de contrôle de parité H. 4. Calcule MED(xo) et MED(yo).

5. Calcule d = dist(MED(xo), MED(yo)).

Si d = 1, l'hypothèse est confirmée. Dans ce cas, le mot de données 15 yo est remplacé par xo et on obtient comme vecteur de ligne de 160 bits reconstruit dO] - (xo,Yl,Y2,Y3,Y4) EFZ160. c[o] est donc un mot de code et la moving bit error' a été corrigée. Si d 0 1, l'hypothèse doit être rejetée.

Si cela était nécessaire, l'algorithme décrit ci-dessus serait effectué pour tous les j = 1,2,3, les adaptations évidentes devant être prises. Par exemple, dans le cas de j = 1, on part de l'hypothèse qu'il s'est produit une moving bit error' dans MED(mi). Dans la première étape de l'algorithme ci-dessus, dans le mot (yo, yi, y2, Y3) yi est remplacé parle mot zéro O. Dans la troisième étape est alors utilisée la sous-matrice Al (au lieu de Ao) et le vecteur calculé à partir de celle-ci est xi.

Si l'hypothèse ne pouvait à nouveau pas être confirmée, il est vérifié les hypothèses analogues pour j = 2 et j = 3. Si toutes les (5) hypothèses étaient fausses, il serait conclu qu'il s'est produit une erreur de bits multiples, donc une modification simultanée de plusieurs bits de 2887352 30 données mémorisés, ce qui est avec une grande probabilité la conséquence d'une attaque.

Le code selon linvention présente, en outre, la propriété importante qu'il peut identifier de manière sûre la modification de plusieurs bits voisins l'un de l'autre.

Pour le vérifier, on considère tout d'abord la matrice de contrôle de parité 32 x 160 H = (A, I32) = (ho, hi, . É - h159), qui décrit complètement le code ECC 160 selon les suppositions théoriques faites dans les paragraphes précédents. On peut démontrer que toute combinaison de k 32 vecteurs de colonne hi successifs de la matrice H sont linéairement indépendants. C'est-à-dire, en d'autres termes, que pour chaque 0 i 159 et pour chaque 1 s k 32, l'ensemble de vecteurs de colonne {hi, h;+1, ..., hj+k_1} (à indices modulo 160) ne contient jamais de sous- quantité de vecteurs de colonne qui, lorsqu'ils sont additionnés, donnent le vecteur zéro.

Cette propriété remarquable de la matrice de contrôle de parité H implique que l'ECC 160 peut identifier avec une sécurité absolue chaque paquet d'erreurs de longueurs 32. Cela signifie, en d'autres termes, que, lorsque dans un mot de code c = (co, ci, ..., c159), tout au plus k s 32 bits deviennent erronés et que le premier et le dernier bit erronés ne se situent pas à plus de 32 positions l'un de l'autre, la présence d'un e E IF2 6â est identifiée avec une sécurité absolue. Dans ce cas, le syndrome S(y) de y = c + e ne sera pas O. L'aptitude à détecter des paquets d'erreurs est une caractéristique essentielle du code. Pour éclaircir cela, nous considérons un mot de code c = (mo, mi, m2, m3, r) E IF260 qui est transmis via un bus de données composé de trajets de données 32. Il est successivement transmis les mots de données mo, m3 E IF2 60 et le mot de redondance r E IF2 2. Si un seul mot est modifié de manière arbitraire par une attaque à la lumière, au laser ou par surtension, tandis que les 2887352 31 quatre autres mots restent inchangés, l'attaque est identifiée par le test de syndrome suivant.

Dans un autre scénario, nous considérons le caché 16 ou la mémoire tampon dans laquelle les mots de code sont mémorisés substantiellement de manière linéaire, des bits logiques successifs correspondant donc également à des bits physiques successifs. Par une attaque à la lumière ou au laser, les bits sont modifiés en soi-disant paquets, donc en groupes de bits de mémoire adjacents. Tant que la grandeur du paquet est limitée à une longueur de maximum 32 bits, cette attaque est également identifiée avec une sécurité absolue.

Le code selon l'invention présente, par ailleurs, la soi-disant propriété delta qui est sensiblement avantageuse pour une mise en oeuvre en matériel à économie de courant et qui est brièvement expliquée ci-après. A cet effet, il est considéré un mot de code e = (m, r) E IFZ 60. Si on décompose le message m e IFZ 28 en bits individuels bj e IF: , on peut également écrire le mot de code comme suit: c = (m, r) = (bo, b,,..., b,5, r) . Un cas qui se présente fréquemment est qu'un octet bj du message m doit être remplacé par un autre octet b; . Le codage du 20 nouveau message complet donne le nouveau mot de code c'= (m',r = r') L'objet qui doit être résolu est de savoir comment le mot de 25 redondance r' peut être calculé avec une moindre consommation de courant.

Tout d'abord est d'application r = mAT et r' = m'AT. Ainsi, r'=m'AT =(m'm)AT +mAT =AAT +r, 30 A=m'-m=(0,...,0,A,0,...0)EIF228 32 et A. =b' -bf =b'. +bJ étant la différence (ou somme, c'est-à-dire soumission à une opération XOR par bit) de l'ancien et du nouvel octet.

Ci-après est expliquée la manière dont la propriété delta du code ECC 160 est mise en oeuvre sous forme d'algorithme dans le matériel selon l'invention.

On part d'un mot de code c = (m, r) dans lequel le j-ième octet k du bloc de message m est remplacé par l'octet b'j, après quoi le mot de redondance doit être mis à jour. A cet effet, les étapes suivantes sont nécessaires: 1. Calcule A = b, + b;.

2. Calcule s = (0, ..., 0, Ai, 0, .., 0)AT.

3. Calcule r' = s + r.

Le mot de données r' est alors exactement le mot de redondance mis à jour.

Cela peut mathématiquement également être formulé autrement.

A cet effet, les matrices 32 x 32 Ao, Al,A2,A3 qui se présentent dans la matrice de contrôle de parité H sont subdivisés en sous-matrices 32 x 8 20 B,, de sorte( que A0 =(B0,B1,B2,B3), Al =(B4,B5,B6,B7), A2 _(B8, B9, B10,B11), A3 = (B12,B13,B14,B15), On peut alors écrire: /4T ( BT 0 A1T B1T AT

AT BT

3/ \ 15) les B5 étant des matrices 8 x 32. Le vecteur s E IF32, qui est nécessaire dans la mise en oeuvre de la propriété delta, peut alors être calculé comme suit: =A,B'j' AT = 2887352 33 Les critères de conception qui étaient importants pour la mise au point du code ECC 160 sont que la mise en oeuvre du code en matériel requiert une surface réduite sur la puce et que Le code n'entraîne, pendant le fonctionnement, qu'une faible consommation de courant. En effet, il n'existe pas de code linéaire (160, 128) à distance de Hamming minimale de d = 4 dont la mise en oeuvre requiert moins de surface de puce (c'est-à-dire dont la matrice de contrôle de parité contient moins de uns) ou dont le fonctionnement (codage et calcul de syndrome) entraîne une moindre consommation de courant. Il existe toutefois un code linéaire (160, 128) à distance de Hamming minimale d = 2 qui peut être mis en oeuvre sur une moindre surface de puce et qui consomme moins de courant que le code ECC 160. Ce code est défini par la matrice de contrôle de parité suivante: H = (I32, I32, I32, I32, I32), I32 désignant la matrice unitaire 32 x 32.

Pour ce code spécial, le mot de redondance r E 1F 2 est obtenu par soumission à une opération XOR des quatre mots de données mo. ... m3, il est donc r=mo+mm+m2+m3.

Ce code n'offre toutefois qu'une très faible protection contre les attaques dans lesquelles des bus individuels sont écoutés ou modifiés ("forçage"). Par exemple, si un agresseur modifie une ligne de données pendant qu'est transmis un mot de code, l'attaque ne peut pas être observée s'il est modifié deux ou quatre bits. S'il est modifié 1, 3 ou 5 bits, un test de syndrome suivant pourra démontrer l'attaque au moyen de ce code. Une telle attaque n'est donc détectée qu'avec une probabilité de 3/5 = 60%. Par contre, le code ECC 160 décrit peut démontrer une attaque décrite ci-dessus avec une sécurité absolue par un test de syndrome. (Du fait de la structure spéciale de la matrice de parité H = (ho, h1, ..., h159) qui définit le code ECC 160, toutes les sous-quantités de forme {hi, hj+32, 4+64, hh+96, hi+128} avec 05j<_31 sont linéairement indépendantes.) 2887352 34 Ci-après sont expliqués plus en détail les critères qui devaient être pris en considération pour la construction du code selon l'invention, en ce qui concerne leur mise en oeuvre en matériel.

Les caractéristiques essentielles d'un code de correction d'erreur sont la dimension de code k, la longueur de code m, aa distance de code dmin, l'aptitude à la correction d'erreur t, l'efficacité de code r et la probabilité de ne pas détecter une erreur pu. Le nombre de bits de contrôle m est calculé comme étant m = n - k.

L'efficacité du code est définie comme étant le rapport entre le nombre de bits de contrôle et le nombre de bits de message, c'est-à-dire qu'elle est une mesure du temps de système qui se produit par suite de la protection. La première condition requise d'un code est qu'il puisse être décrit de forme systématique. Cela signifie que chaque mot de code individuel c doit pouvoir être séparé en une forme c =_ (m, p), m étant le vecteur de bits de message et p le vecteur de bits de correction.

Par ailleurs, nous supposons que le code se compose d'éléments de F2. En général, des codes binaires sont préférés pour les mises en oeuvre en matériel efficaces, étant donné que les codes qui se basent sur d'autres quantités de données à la base requièrent normalement la mise en oeuvre d'une arithmétique de Galois-Feld coûteuse. C'est pourquoi, les codes linéaires sont préférés.

Le nombre total de uns dans chaque rangée individuelle de la matrice de contrôle de parité H a un rapport direct avec la profondeur de logique du circuit qui est utilisé dans une mise en oeuvre en matériel pour former le bit de contrôle ou le bit de syndrome de la ligne concernée. Si ei est le nombre total de uns dans la i-ième rangée, la profondeur de logique du circuit qui calcule un bit de vérification est donnée par la formule suivante: 1,, (i) = I log p (e; -1) La profondeur de logique du circuit de bit de syndrome est alors donnée par 2887352 35 ls (i) _ 1 Iog p (er) p décrivant le nombre d'entrées des cellules XOR qui sont utilisées dans la mise en oeuvre en matériel (par exemple 2 ou 3) .

Cela signifie, pour une mise en oeuvre en matériel de la matrice de contrôle de parité H, qu'un coût de matériel minimum, une consommation de courant minimale et un temps de traitement minimum peuvent être obtenus par une minimisation du nombre de uns dans chaque rangée de la matrice de contrôle de parité.

Une deuxième condition requise est que le nombre de uns dans chaque rangée se rapproche le plus possible du nombre moyen de uns par rangée. Cette distribution uniforme de uns assure qu'il ne se présente pas de trajet de traitement long et critique dans le circuit codant ou calculant le bit de syndrome.

Généralement est d'application: Lorsque C est. un code linéaire à matrice de contrôle de parité H associée, la distance de Hamming de C est égale ou inférieure au nombre de colonnes de H qui, lorsqu'elles sont additionnées, donnent le vecteur zéro.

Au cas où chaque colonne de H contient un nombre impair de uns, il résulte de l'affirmation ci-dessus que la distance de Hamming du code doit être au moins 4. Les codes qui suivent les trois principes ci-dessus (nombre minimum de uns, même nombre de uns dans chaque rangée de la matrice H, nombre impair de uns dans chaque colonne de la matrice H) sont appelés codes de Hsiao. Cette classe de codes garantit donc une efficacité optimale lors de l'intégration dans un matériel d'ordinateur.

Une autre conséquence de l'affirmation générale ci-dessus est qu'une plus grande distance de Hamming d'un code conduit généralement à un plus grand nombre de uns dans une matrice de contrôle de parité (bien qu'il n'existe pas de rapport mathématique stricte).

2887352 36 Le code selon l'invention suit les principes ci-dessus et a, en outre, la propriété delta et est, par ailleurs, compatible avec MED, propriétés qui sont une condition obligatoire pour une mise en oeuvre à économie de courant et de place dans des contrôleurs de sécurité.

L'efficacité de code r de l'ECC 160 est r = 25%. Si le temps de système qui en résulte pour une application prévue était trop long, il pourrait, en outre, être mis oeuvre un code de la famille de codes selon l'invention qui présente une efficacité de code r = 12.5%, pour la construction de la matrice H devant être utilisées huit des matrices circulantes qui sont représentées aux figures 4a à 4e. Les circuits pour la détection d'erreurs, pour le calcul de syndrome, pour la conversion de la propriété delta et pour la correction d'erreurs doivent alors être adaptés de manière étroite.

L'aptitude à la mise en oeuvre particulièrement efficace du point de vue matériel du code d'erreur ECC 160 selon l'invention est à nouveau brièvement décrit ci-après.

La mise en oeuvre de la multiplication de matrice dans l'équation 1 requiert 32 x 16 = 512 portes XOR avec deux entrées et a la profondeur de logique 4. S'il est utilisé un mélange de portes XOR avec deux et trois entrées, il est requis 32 x 9 = 288 portes et la profondeur de logique est réduite à 3.

Le calcul du syndrome peut chaque fois être réalisé par le même matériel, pour la dérivation exacte du rapport, l'on se référera aux paragraphes suivants.

La propriété delta et l'algorithme pour la mise en oeuvre de celle-ci peuvent également être exécutés par le matériel. Dans ce cas, seul un groupe de huit lignes adjacentes de la matrice est multiplié l'octet modifié. Pour des raisons de balance de courant, il y a lieu de veiller à ce que la partie du circuit qui est associée aux octets inchangés n'arrive pas dans un état non défini. Si cela peut être garanti, la consommation de courant d'une mise à jour d'un octet ne sera, en cas d'utilisation de 2887352 37 la propriété delta, que d'environ 10% de la consommation de courant qui se produit lors du codage d'un bloc de message entier.

Dans les équations précédentes sont utilisées tant les matrices que les matrices transposées dans les matrices. C'est le cas, étant donné que dans les descriptions précédentes du code linéaire selon l'invention ont été respectées, pour autant que possible, les conventions standard en particulier en ce qui concerne la représentation les matrices appropriés. Dans une application typique est utilisée, à un endroit, la matrice M et, à un autre endroit, la matrice MT transposée à cette dernière. Pour assurer une mise en oeuvre efficace (par exemple dans le langage de description de matériel VHDL, du code, il peut maintenant être renoncé, dans un exemple de réalisation préféré de la présente invention, à l'utilisation tant de M que de MT. En effet, on peut complètement éviter l'utilisation de la transposée de toutes les matrices en observant les règles suivantes (même s'il en résulte le déploiement additionnel qu'il est nécessaire de calculer tant avec des vecteurs de ligne qu'avec des vecteurs de colonne) : (AT 1 = A et (AB)T = Br AT A l'aide des équations ci-dessus, les formules qui décrivent le codage et le test de syndrome peuvent être transformées de la manière suivante: rT = Amr rT = Aomo + Alm[ + A2m2 + A3m3 T\ Yo

T

YT = 4yo + AIYI + A2Yi + A3y3 Y2

T

\Y3) / O qT =A T Y1

T Y2

T \y3= A,y,T + A2y2 + A3y3 sr=A Dans un autre exemple de réalisation spécial de la présente invention, le code ECC 160 qui vient d'être décrit est modifié. Dans cette modification, la correction d'erreur est possible plus rapidement au moyen du code, ce qui est possible aux dépenses d'un déploiement en matériel légèrement accru. Ci-après, il est démontré qu'il est plus favorable, pour cette variante du code, de construire la matrice de contrôle de parité H à partir de quatre matrices circulantes à faible occupation qui ne sont pas auto-inverses, mais, en lieu et place, d'utiliser des matrices chaque fois inverses de deux en deux.

Dans les considérations suivantes, m est un message de dimension k = 128 bits qui est organisé en mots d'une longueur de 32 bits. La longueur d'un mot de code est n = 160 bits et la longueur du vecteur de bits de contrôle est donc de n - k = 32 bits.

m = (mo, m, , m2, m3) avec m,e (0,1)32.

La matrice de génération canonique de ce code linéaire systématique est donnée par G=(Ik,P)= IP0 IP P2 IP3, Ik p étant une matrice 128 x 32 et pi étant des matrices 32 x 32. Le 20 vecteur de bits de contrôle p est calculé à partir de p=mp et le mot de code est u=mÉG=(m, p).

La matrice de contrôle de parité H est donc H=( P7,In k)=(PT,PT, P2TP3T, 132) La matrice de génération G est l'espace zéro de la matrice de contrôle de parité, c'est-à-dire GÉHT=O.

Nous désignons le mot de code probablement modifié par v = u + e, e étant le vecteur d'erreur. Le vecteur de syndrome s est calculé selon la formule suivante: s=vÉHT =(u+e)ÉHT =eÉHT.

S'il n'y a pas de vecteur de bits d'erreur, le vecteur de bits de syndrome sera le vecteur zéro O. Dans la notation suivante sera utilisé p pour désigner un vecteur arbitraire et non pas toujours le même vecteur arbitraire parmi la quantité de vecteurs (0,1)32.

Pour illustrer le code selon l'invention, il est décrit ci-après, pas à pas, tout d'abord l'information de redondance à calculer par l'unité de redondance 12 et la mémorisation et le cryptage par le dispositif de cryptage/ décryptage 20.

1. Calcul du vecteur de bits de contrôle p=mÉP=moPo +m,P +m2P2 + m3P3 20 2. Formation du mot de code u = (m Ép) = (uo,ul,u2,u3,u) _ (mo,ml, m2,m3, p) 3. Crypter le mot de code à l'aide de la MED ou du dispositif de cryptage/décryptage 20. Ci-après, ek(x) désignera une opération de cryptage de la MED, un mot de 32 bits x étant crypté par une clé k. Le cryptage par mot peut donc ètre écrit comme suit: ue =ek(u;) pour i = 1,2, 3,4,5..

Formation du vecteur de code crypté : e e e e e 1le = u,Zf Z12,1l3, Zf4).

5. Mémorisation du vecteur de code crypté ue, par exemple, dans 30 la mémoire de masse 22.

2887352 40 Le processus de lecture de la mémoire et de reconstruction d'un bit erroné par l'unité de contrôle 14 est, ci-après, également reproduit pas à pas.

Il est tout d'abord traité le cas d'une erreur de 1 bit corrigible, par exemple d'une moving bit error dans une mémoire non volatile, telle que la mémoire de masse 22. Il est supposé, sans restriction de la généralité, que l'erreur de 1 bit se situe dans le deuxième mot de 32 bits, à la position f. Le vecteur de code crypté ou le vecteur de bits total crypté 54, qui est lu de la mémoire, est désigné par v. Il est v = ue + e avec e = (eo, el, e2, e3, e4) = (0, el, 0, 0, 0) et el = (0, ..., 0,1,0, ..., 0).

1. Lire le message crypté v de la mémoire, v=(v0,v,,v2,v3,v4)=(uo, u( +et, u2,u3,u4) 2. Décrypter le message à l'étape de décryptage 66 par la MED.

Par analogie au cas décrit ci-dessus, dk(x) désigne un décryptage MED 15 d'un mot de 32 bits x au moyen de la clef k. Ainsi, lors de l'opération de décryptage, il est effectué le calcul suivant: vd = dk(v;) pour i = 1, 2,3,4,5.

Pour le cas d'erreur décrit ci-dessus, le résultat de l'opération précédente est en particulier: vod =dk(vo)=dk(uô)=dk(ek(uo =mo vd =dk(vi) =dk(ui +e,)=p v2 =m2 d v3 = m3 d v4 =p Du fait de la parfaite décorrélation de bits adjacents par l'algorithme MED, v; sera un vecteur de bits d'une longueur de 32 bits.

3. Calculer le vecteur de bits de syndrome 58: s = vd.HT = v] +vpT +VZP2T+ V3P3T+P mopT +p +m2pT +m3 P3T +Pp Le vecteur de bits de syndromes sera, avec une probabilité de p 2-32, égal au vecteur zéro. La probabilité de ne pas détecter une erreur de bit est donc de p 2 4. Découvrir le mot erroné.

Une étape non triviale est la localisation du mot erroné et la correction de l'erreur, étant donné que le code corrigeant l'erreur est certes appliqué avant le cryptage. Si on considère l'équation de contrôle de parité s = v É H = 0, cette équation peut être résolue pour chaque mot des mots de 32 bits du message: vo =(vif +v2P2 +v3P3 +v,)-Po-1 = (voPo + v2 P2 +v3P3 + v4) É p-1 v2 =(voPo+vif +v3P3+v4)ÉP2' équation 2.

v3 =(voPo+v1J +v2 P2+v4)ÉP 1 v1 ' = voPo + v1P + vZPz + v3P3 Dans l'étape de substitution 70 sont formés les vecteurs de mots de données substitués décryptés 62a à 62e ci-dessus. Sur base de la connaissance de quatre des cinq mots de données, on peut donc reconstruire le cinquième mot de données restant. Les mots reconstruits sont caractérisés par une apostrophe.

Pour notre exemple considéré, on obtient comme premier mot de 32 bits: mo = (vdf +v Pz +v3 P3 +v4 d)É Po i d _ (pP, +m2P2 +m3P3 + p)ÉPo-i = P Le mot reconstruit ou substitué est alors à nouveau crypté, 20 m'eo = ek (m'o) et il est for tué la distance de Hamming entre m'ô et le mot vo qui a été lu à l'origine de la mémoire: do =d m,eo,vo)É Dans le cas de l'exemple, on obtient do = d(p, vo), do > 1 avec une probabilité de p 232/32 =228.

Étant donné que do est différent de 1, il est conclu que vo n'est pas le mot qui contient l'erreur de bit.

Dans une étape suivante est appliquée la même procédure pour le deuxième mot de données: = (yod P +v2 P, +v'P3 +v4 d)-Pi-1.

É (moP+m_P+m3P+p)ÉP-' ^ m, Le mot reconstruit est alors à nouveau crypté, = ek (m', ), et il est calculé la distance de Hamming entre m' et le mot de données vi lu à l'origine de la mémoire: d, =d(m,e,v,)=d(mie,u; +e,) =d(mie,m +e,)=1 5. Correction de l'erreur Du fait que di = 1, il est maintenant connu que l'erreur de 1 bit a 10 été localisée dans le deuxième mot de données et on peut finalement écrire le mot corrigé m'; à la position de mémoire de vi.

Dans le cas général, la reconstruction des mots de données à l'étape de substitution 70 est effectuée successivement pour mo, mi, m2, m3, m4. A la première occurrence d'une distance de Hamming de 1 est déterminée la position de l'erreur et le processus est arrêté. Au cas où il ne peut être trouvé de distance de Hamming de 1, il s'est produit une erreur dans laquelle plusieurs bits ont été modifiés simultanément, et il est supposé une attaque sur le système.

L'avantage particulier de l'exemple de réalisation selon l'invention dans lequel le code ECC 160 est modifié réside dans le fait que la correction de données erronées peut ètre effectuée à une vitesse de traitement supérieure, d'où il y a lieu de considérer à nouveau séparément, pour l'exemple de réalisation de la présente invention qui vient d'être décrit, la complexité de la mise en oeuvre en matériel.

A première vue, la mise en oeuvre des équations 2, qui décrivent les vecteurs de mot de données substitués cryptés, semble compliquée, étant donné qu'il s'y présentent des matrices inversées.

Ci-après, il sera démontré que la mise en oeuvre n'est pas plus complexe que la mise en oeuvre du calcul du vecteur de bits de syndrome. Les matrices circulantes cycliques de rang 32 indiquées aux figures 4a à 4e présentent la propriété d'être auto-inverses et présentent, chacune, trois uns dans les vecteurs de colonne qui les forment. Cela signifie que l'inverse des matrices n'est pas dense, donc qu'il donne une matrice avec beaucoup de uns, tel qu'on s'y attendrait normalement pour l'inversion d'une matrice à faible occupation choisie de manière arbitraire. Pour ces matrices, les produits Pi É P7, i j sont donc également à faible occupation. En particulier, le poids des matrices de produit cycliques à 5 bandes 160 (pour les matrices 10 originales Pi est le poids 96).

Il existe en tout six matrices de produit Pi É P;' , i j, chaque matrice de produit ayant cinq bandes, c'est-à-dire un nombre de cinq uns dans chaque ligne. Aussi, la complexité de la mise en oeuvre en matériel est d'environ (6. rlog2(5)1 + 4 É rlog3(3)1) É 32 = 512 portes 3 AND + 4 x 32 = 128 portes 3 XOR. La profondeur de logique est 3.

Une autre amélioration devient possible si on utilise des matrices inverses deux par deux Pi. Dans ce cas, il n'y a que quatre produits de matrice, et on obtient une complexité de (4. rlog3(5)1 + 4 É rlog3(3)1) É 32 = 384 portes 3 AND + 4 x 32 = 128 portes 3 XOR. La profondeur de logique est également 3. Pour le mode de réalisation spécial de la présente invention, il est choisi Po = et P2 = P3-' . Pour la mise en oeuvre d'un dispositif de vérification de l'intégrité de données selon l'invention, il est en principe également possible d'utiliser d'autres codes d'erreur, tels que par exemple des codes cycliques, en particulier le code de BCH et les codes de produit.

Pour les codes de produit, des codes puissants à distances de Hamming supérieures peuvent être formés à partir de codes ayant une distance de Hamming inférieure par le fait que l'on génère de soi-disant codes de produit. Si Ci est un code (ni, k1) linéaire et C2 est un code (n2, k2) linéaire, il peut être formé un code (nin2, kik2), tel que représenté à la figure 5, des codes systématiques étant supposés ici.

2887352 44 A la figure 5 est illustré un bloc de bits de données 200, ainsi que des premiers vecteurs de bits de contrôle 202 et des deuxièmes vecteurs de bits de contrôle 204. Un nombre k1 de mots de données de longueur 1(2 sont disposés dans le bloc de bits de données 200 de sorte qu'un mot de données forme chaque fois une ligne du bloc de bits de données m et que les kl mots de données différentes soient disposés entre eux dans le bloc de bits de données 200 tel que visible à la figure 5 en référence au mot de données représenté de manière schématisée 206. Au bloc de données 200 sont appliqués deux codes linéaires CI et C2 de sorte que chaque rangée soit un mot de code de longueur ni dans CI et chaque colonne soit un mot de code de longueur n2 dans C2. La zone de contrôle rectangulaire 208 à la figure 5a contient les bits de contrôle que donne une application de CI aux bits de contrôle de C2 et inversement. La distance de Hamming minimale d'un tel code de produit est d =dm.d(2) min min min le code est donc à même de corriger t = L(dmi n É dm2ô -1)/2 J erreurs. Une variation d'un code de produit est le soi-disant code de produit incomplet, tel qu'illustré à la figure 5b. La figure 5b diffère de la figure 5a par le fait que la zone de contrôle 208 est omise, le code de produit linéaire (km2 +k2ni - kik2, klk2) qui en résulte est plus faible et a une distance de Hamming minimale de seulement drain = d? + d(?? -1.

Un code de produit incomplet est également appelé code de somme linéaire.

Le code de produit incomplet de deux codes de parité simples (single parity code, SPC) est utilisé de manière générale dans les conceptions de RAM industrielles et dans les microprocesseurs, par exemple dans la conception des registres. Ces codes sont souvent également appelés code de parité horizontale et verticale (horizontal and vertical parity code). Si l'on forme le code de produit complet de deux SPC, la distance de Hamming minimale est de dmin = 4.

2887352 45 Différentes conceptions de DRAM peuvent servir d'exemple de conversion de codes de produit incomplets. Par extension par une parité formée dans la diagonale (cross parity), mentionnons ici, par ailleurs, le SUN Sparc Register File. Dans notre cas spécial seraient nécessaires deux codes linéaires qui présentent une pluralité de bits de contrôle, pour répondre aux hautes exigences posées pour le code en ce qui concerne la non-détection d'une erreur. Étant donné que la grandeur de bloc de données de 128 ou 256 bits est relativement petite, un tel code produirait un temps de système important. Pour expliquer cela, il est supposé, ci-après, une grandeur de bloc de données k = 256. Le bloc de données 200 est disposé dans un champ de huit lignes et 32 colonnes (donc des mots de 32 bits). Le code de bloc linéaire le plus petit pour un mot de données de 32 bits permettant une distance de Hamming drain > 3, compte tenu de la limite de Hamming n k >_ log2 E n i=oit, est un code (38, 32) linéaire. On peut montrer que le code de Hsiao le plus petit possible est un code de Hsiao (39, 32). Si on combine le code de Hsiao (39, 32) qui est appliqué aux lignes avec un code SPC (9, 8) qui est appliqué aux colonnes, on obtient un code de produit (351, 256). Ce code est caractérisé par drain = 4 É 2 = 8 et r = 73%, la probabilité d'une erreur non détectée étant de l'ordre de grandeur de pu 2n-k = 2-95 La matrice de contrôle de parité pour le code de Hsiao (39, 32) est: 10000110 01001101 00011000 10110010 1000000 11000011 00100110 10001100 01011001 0100000 1110000110010011 01000110 00100100 0010000 H= 01110000 11001001 10100011 00011010 0001000 00111000 01100100 11010101 10000101 0000100 00011101 00110000 01101010 11001010 0000010 00001110 10011010 00110001 01100101 0000001 2887352 46 De tels codes de produit ne conviennent pas pour la mise en oeuvre en matériel efficace souhaitée, étant donné qu'ils possèdent, avec r = 73%, un temps de système important.

Comme autre possibilité pour la mise en oeuvre d'un code dans 5 un dispositif pour vérifier l'intégrité de données sont décrits brièvement ci-après des codes BCH.

Un code BCH avec une faible probabilité d'erreur non détectée est formé par le polynôme de génération p(x) =x27 +x26 +x24 +x22 +x21 +x16 + x13 + x11 +x9 +x8 +x6 +x5 +x4 +x3 +1, qui est le produit de trois polynômes primitifs p1(x)=x9+x6+x4+x3+1, p2(x) = x9 +x8 +x5 +x4 +1, p3 (x) = x9 + x4 +1.

Ce code a la distance de Hamming minimale dmin = 7, la longueur n = 511, la dimension k = 484 et m = n - k = 27 bits de contrôle. En ce qui concerne la probabilité d'une erreur non détectée, il peut être indiqué, comme limite supérieure, pus 227. Les codes BCH ont une structure cyclique. Cette propriété n'est pas requise pour une exécution rapide du contrôle d'erreur, le codage et la génération du syndrome pouvant être mis en oeuvre comme registre à décalage linéaire. Lorsqu'il est requis une mise en oeuvre rapide et entièrement parallèle dans un circuit, ce circuit serait très grand, étant donné que la matrice de contrôle de parité qui en résulte présenterait de forme systématique environ 50% de uns. La mise en oeuvre de registre à décalage présente, en outre, l'inconvénient que la propriété delta nécessaire du code ne devient possible qu'avec un déploiement en matériel supplémentaire considérable, ce qui vaut généralement pour tous les codes cycliques. Aussi, ce code ne convient pas pour une mise en oeuvre en matériel efficace et rapide selon l'invention.

L'avantage des exemples de réalisation de la présente invention réside donc dans le fait qu'un code linéaire pour la protection contre des 2887352 47 attaques par des erreurs est défini ou réalisé par une matrice de contrôle de conception particulière. Celle-ci se compose de sousmatrices carrées circulantes à faible occupation simplement de même puissance. A faible occupation signifie que les matrices ne contiennent que peu de uns et principalement des zéros. Cela correspond, dans la mise en oeuvre en matériel du code, à une surface de silicium réduite et, en fonctionnement, à une faible consommation de courant.

Les matrices circulantes sont des matrices carrées qui sont déjà déterminées de manière univoque par leur première ligne. Les lignes suivantes résultent d'un déplacement cyclique de cette première ligne. Par la construction de la matrice de contrôle à partir de matrices simplement circulantes, il est obtenu, en particulier, que chaque ligne de la matrice de contrôle contienne un même nombre de uns.

Cela signifie que, lors du calcul des bits individuels du mot de contrôle ou du syndrome, il y a toujours lieu de parcourir chaque fois la même profondeur de porte. Cela est important pour une mise en oeuvre en matériel efficace. Une matrice carrée est appelée de même puissance lorsqu'elle peut être inversée et que la matrice inverse est identique à la matrice originale (la matrice est "auto-inverse"). La même puissance des sous-matrices utilisées du code selon l'invention de reconstruire, de manière à économie de matériel, un mot erroné du bloc de données à partir des autres mots (sans erreur) plus le mot de contrôle. Cette propriété est utilisée pour pouvoir corriger des erreurs de 1 bit (de soi-disant moving bit errors') - telles qu'elles se produisent de temps à autre dans l'EEPROM. Lors de la lecture de l'EEPROM, une telle erreur de 1 bit est notamment décryptée dans une valeur mémorisée. Le dispositif de décryptage a un soi-disant effet d'avalanche: Lors du cryptage ou décryptage d'un mot de 32 bits, une erreur de 1 bit devient une erreur de bits multiples (de manière typique, une erreur de 10 à 20 bits). Après la lecture est utilisé le code linéaire. Le syndrome est différent de 0, une indication que soit il s'est produit une attaque par des erreurs, soit qu'il s'est produit une moving bit error' dans la 2887352 48 mémoire. Le mot erroné doit alors être reconstruit à partir des autres mots (sans erreur) du bloc de données décrypté. Comme exemple de réalisation spécial de la classe de codes selon l'invention a été décrit en détail, dans les paragraphes précédents, un code linéaire de longueur 160 pour une largeur de mot de 32, ce code étant appelé ECC 160.

Bien que, dans l'exemple de réalisation de la présente invention représenté à la figure 1, le dispositif de redondance 12 et le dispositif de contrôle 14 soient directement intégrés dans le processeur ou dans l'unité de calcul 10, le dispositif de redondance 12 et le dispositif de contrôle 14 peuvent, selon l'invention, être disposés à un endroit arbitraire le long du trajet de données, avant le dispositif de cryptage/décryptage 20. De manière flexible, le dispositif de redondance 12 et le dispositif de contrôle 14 selon l'invention peuvent être placés à un endroit dans le trajet de données qui est déterminé par la portée de protection désirée. Si l'on ne désire protéger, par exemple, que le transfert à la mémoire de masse, le dispositif de redondance 12 et le dispositif de contrôle 14 peuvent être disposés entre le caché 16 et le dispositif de cryptage/décryptage 20; si le caché doit également être surveillé, une disposition entre le registre de données 6 et le caché 16 peut être mise en oeuvre sans autre.

En fonction des conditions, le procédé pour protéger l'intégrité de données selon l'invention peut être mis en oeuvre en matériel ou en logiciel. La mise en oeuvre peut avoir lieu sur un support de mémoire numérique, en particulier une disquette ou un CD à signaux de commande pouvant être lus électroniquement, qui peuvent coopérer avec un système d'ordinateur programmable de sorte que soit exécuté le procédé pour protéger l'intégrité de données selon l'invention. En général, l'invention consiste donc également en un programme d'ordinateur avec un code de programme mémorisé sur un support pouvant être lu en machine pour l'exécution du procédé selon l'invention lorsque le programme d'ordinateur se déroule sur un ordinateur. En d'autres termes, l'invention peut donc être réalisée sous 2887352 49 forme de programme d'ordinateur avec un code de programme pour l'exécution du procédé lorsque le programme d'ordinateur se déroule sur un ordinateur.

2887352 50 Liste des numéros de repère 2 Processeur principal 4 Système de memoire 6 Registre de données 8 Processeur central Unité de calcul 12 Unité de redondance 14 Unité de contrôle 16 Caché 18 Mémoire interne Unité de cryptage/décryptage 22 Mémoire de masse 24 Premier circuit de transmission de données 2 6 Deuxième circuit de transmission de données 28 Premier circuit de transmission de données bidirectionnel Deuxième circuit de transmission de données bidirectionnel 32 Troisième circuit de transmission de données bidirectionnel 34 Quatrième circuit de transmission de données bidirectionnel 36 Ensemble de données non crypté 38 Vecteur de bits de données 40 Vecteur de bits de contrôle 42 Vecteur de bits total 44 Vecteur de bits total crypté 46 Formation de redondance 48 Génération de vecteur de bits total 50 Etape de codage 52 Ensemble de données crypté 54 Vecteur de bits de total crypté 58 6Oa-6Oe 62a-62e 64a64e 66 102 200 202 204 206 208 Vecteur de bits de total décrypté Vecteur de bits de syndrome vecteurs de mots de données décryptés Vecteurs de mots de données substitués décryptés Vecteurs de mots de données substitués cryptés Etape de décryptage Etape le de transfert de lecture Etape de confirmation Etape de substitution Etape de vérification Etape de comparaison Etape de reconstruction Etape d'erreur Première ligne de matrice Deuxième ligne de matrice Bloc de bits données Premiers vecteurs de bits de contrôle Deuxièmes vecteurs de bits de contrôle Mot de données Zone de contrôle 2887352 512

Claims (15)

REVENDICATIONS

1. Dispositif pour protéger l'intégrité de données, aux caractéristiques suivantes: un dispositif de redondance (12), pour former, à partir d'une pluralité de mots de données d'un bloc de données (36), un vecteur de bits de données (38) et générer, par multiplication du vecteur de bits de données (38) par une matrice de génération binaire, un vecteur de bits de contrôle (40) ; un dispositif de cryptage/décryptage (20) destiné à crypter chacun des mots de données, pour obtenir des mots de données cryptés, et à crypter le vecteur de bits de contrôle, pour obtenir un vecteur de bits de contrôle crypté, et à décrypter chacun des mots de données cryptés, pour obtenir des mots de données décryptés (60a à d), et à décrypter le vecteur de bits de contrôle crypté, pour obtenir un vecteur de bits de contrôle décrypté (60e) ; un dispositif de contrôle (14), pour former, à partir des mots de données décryptés (60a à d) ou des mots de données décryptés (60a à d) et du vecteur de bits de contrôle décrypté (60e), un vecteur de bits total (56) et créer, par multiplication d'une matrice de contrôle binaire par le vecteur de bits total (56), un vecteur de bits de syndrome (58), de sorte qu'à l'aide du vecteur de bits de syndrome (58) puisse être vérifiée l'intégrité du vecteur de bits total (56).

2. Dispositif selon la revendication 1, dans lequel le dispositif de redondance (12) est réalisé de manière à utiliser une matrice de génération comportant des sous-matrices carrées circulantes, et dans lequel le dispositif de contrôle (14) est réalisé de manière à utiliser une matrice de contrôle comportant des sous-matrices carrées circulantes.

3. Dispositif selon la revendication 1 ou 2, dans lequel le dispositif de redondance (12) est réalisé de manière à utiliser une matrice de génération présentant des sous-matrices de même puissance.

4. Dispositif selon l'une des revendications 1 à 3, dans lequel le dispositif de redondance (12) est réalisé de manière à utiliser une 2887352 53 matrice de génération comportant 2, 4, 8 ou 16 sous-matrices carrées circulantes et à traiter 2, 4, 8 ou 16 mots de données, et dans lequel le dispositif de contrôle (14) est réalisé de manière à utiliser une matrice de contrôle comportant 2, 4, 8 ou 16 sous-matrices carrées circulantes et à traiter 2, 4, 8 ou 16 mots de données.

5. Dispositif selon la revendication 4, dans lequel le dispositif de redondance (12) est réalisé de manière à utiliser une matrice de génération dans laquelle une première et une deuxième paire de chaque fois deux des quatre sous-matrices comprennent des sous-matrices inverses entre elles de deux en deux, et dans lequel le dispositif de contrôle (14) est réalisé de manière à utiliser une matrice de contrôle dans laquelle des paires de chaque fois deux parmi un nombre pair de sous-matrices comprennent des sous-matrices inverses entre elles de deux en deux.

6. Dispositif selon l'une des revendications 4 ou 5, dans lequel le dispositif de redondance (12) est réalisé de manière à utiliser des mots de données d'une longueur de 32 bits et une matrice de génération comprenant 4 matrices 32 x 32 carrées comme sous-matrices, et dans lequel le dispositif de contrôle (14) est réalisé de manière à utiliser des mots de données d'une longueur de 32 bits et une matrice de contrôle comprenant 4 matrices 32 x 32 carrées comme sous-matrices.

7. Dispositif selon l'une des revendications l à 6, présentant, en outre, un dispositif de surveillance de vecteur de bits de syndrome destiné à compter les zéros du vecteur de bits de syndrome (58), pour déclencher une action d'alarme lorsqu'un nombre de zéros est supérieur à un seuil prédéterminé.

8. Dispositif selon la revendication 7, dans lequel le dispositif de surveillance de vecteur de bits de syndrome est réalisé de manière à réaliser, lors de l'action d'alarme, les étapes suivantes consistant à : générer de nouveaux mots de données à partir des mots de données décryptés, 2887352 54 - crypter les nouveaux mots de données, pour obtenir de nouveaux mots de données cryptés, - comparer les nouveaux mots de données avec les mots de données cryptés, déclencher une alarme d'attaque lorsque l'étape de comparaison constate un écart de plus d'un bit pour chaque paire de mot de données crypté et de nouveau mot de données crypté, ou libération des données lorsque l'étape de comparaison constate un écart d'un bit pour une paire par rapport au mot de données crypté et au nouveau mot de données crypté.

9. Dispositif pour protéger l'intégrité de données, aux caractéristiques suivantes: un dispositif de décryptage (20) destiné à décrypter des mots de données cryptés, pour obtenir des mots de données décryptés (6Oa à 6Od) et à décrypter un vecteur de bits de contrôle crypté, pour obtenir un vecteur de bits de contrôle décrypté ; et un dispositif de contrôle (14), pour former, à partir des mots de données décryptés (6Oa à d) ou des mots de données décryptés (6Oa à d) et du vecteur de bits de contrôle décrypté (6Oe), un vecteur de bits total (56) et à créer, par multiplication d'une matrice de contrôle binaire par le vecteur de bits total (56), un vecteur de bits de syndrome (58), de sorte qu'à l'aide du vecteur de bits de syndrome (58) puisse être vérifiée l'intégrité du vecteur de bits total (56).

10. Dispositif selon l'une des revendications 1 à 6, dans lequel le dispositif de redondance (12) est réalisé de sorte que la matrice de contrôle soit réalisée de sorte que le vecteur de bits de syndrome (58) corresponde à une combinaison linéaire de vecteurs de colonne avec les bits des mots de données (6Oa à 6Od) comme coefficients plus le vecteur de bits de contrôle (6Oe), chaque vecteur de colonne possédant un poids de Hamming impair; et 2887352 55 tous les vecteurs de colonne possédant le même poids de Hamming.

11. Dispositif pour protéger l'intégrité de données, aux caractéristiques suivantes: un dispositif de redondance (12) pour former, à partir d'une pluralité de mots de données d'un bloc de données (36), un vecteur de bits de données (38) et pour générer, par multiplication du vecteur de bits de données (38) par une matrice de génération binaire, un vecteur de bits de contrôle (40) ; un dispositif de cryptage (20) destiné à crypter chacun des mots de données, pour obtenir des mots de données cryptés et à crypter le vecteur de bits de contrôle, pour obtenir un vecteur de bits de contrôle crypté.

12. Dispositif selon l'une des revendications 1 à 8 ou la revendication 11, dans lequel le dispositif de redondance (12) est réalisé de manière à générer, à un vecteur de bits de données suivant qui diffère d'un vecteur de différence du vecteur de bits de données (38), par multiplication du vecteur de différence par la matrice de génération, un mot de bits de contrôle de différence, et à former un mot de bits de contrôle suivant à partir de la somme du mot de bits de contrôle (40) et du mot de bits de contrôle de différence.

13. Procédé pour protéger l'intégrité de données, aux étapes suivantes consistant à : décrypter des mots de données cryptés, pour obtenir des mots de données décryptés (6Oa à 6Od) et décrypter un vecteur de bits de contrôle crypté, pour obtenir un vecteur de bits de contrôle décrypté (6Oe) ; former un vecteur de bits total (56) à partir des mots de données décryptés (6Oa à 6Od) et du vecteur de bits de contrôle décrypté (6Oe) ; et multiplier une matrice de contrôle binaire par le vecteur de bits total (56), pour créer un vecteur de bits de syndrome (58) , de sorte qu'à 2887352 5 l'aide du vecteur de bits de syndrome (58) puisse être vérifiée l'intégrité des mots de données (6Oa à 6Od).

14. Procédé pour protéger l'intégrité de données, aux étapes suivantes consistant à : former un vecteur de bits de données (38) à partir d'une pluralité de mots de données d'un bloc de données (36) multiplier le vecteur de bits de données (38) par une matrice de génération binaire, pour générer un vecteur de bits de contrôle (40) ; et crypter chacun des mots de données, pour obtenir des mots de données cryptés et crypter le vecteur de bits de contrôle (40), pour obtenir un vecteur de bits de contrôle crypté.

15. Programme d'ordinateur avec un code de programme pour l'exécution du procédé selon la revendication 13 ou 14 lorsque le programme d'ordinateur se déroule sur un ordinateur.