The problem of finding the private key (g, f) returns to a problem of computation of the shortest vector (SVP) in the network L_NTRU , where L_NTRU = {(u, v) el² \ u * h - v = 0 {mod q)}. Let B be a base of a network L, being a set of linearly independent vectors of W¹ , the problem of calculating the shortest vector is to find a nonzero vector of L as small as possible, that is to say find v ≠ 0 £ L such that | | T> | is minimal, | | T> | |

En effet, la clé privée {g, f) appartient au réseau, car g = h * f mod q, l'opération de multiplication par p étant effectuée lors du chiffrement, dans ce cas h = g * f_q {mod q), donc f * h = g {mod q) et f * h— g = 0 {mod q). Si g et / sont constitués uniquement de coefficients 0, 1 et -1, alors il y a de très fortes chances que les rotations de {g, f) soient les plus courts vecteurs du réseau. En trouvant le plus court vecteur du réseau L_NTRU, on trouve très certainement la clé privée.Indeed, the private key {g, f) belongs to the network, because g = h * f mod q, the multiplication operation by p being performed during the encryption, in this case h = g * f_q {mod q) so f * h = g {mod q) and f * h- g = 0 {mod q). If g and / consist only of coefficients 0, 1 and -1, then there is a very good chance that the rotations of {g, f) are the shortest vectors of the network. Finding the shortest vector of the L_NTRU network, we most certainly find the private key.

Le problème de déchiffrement peut être vu comme le problème du plus proche vecteur (CVP). Etant donnée une base B d'un réseau L et un vecteur w £ L, le problème consiste à trouver le vecteur v e L le plus proche de w, c'est-à-dire trouver v e L tel que The decryption problem can be seen as the problem of the nearest vector (CVP). Given a base B of a network L and a vector w £ L, the problem is to find the vector v e L closest to w, that is to say to find v e L such that

1 \v— w\ I est minimal. Dans le cryptosystème NTRU, le chiffré est e = r * h + m {mod q), donc le vecteur {e, 0) est proche du vecteur (p * r * h {mod q), p * r) du L_NTRU, la différence entre les deux vecteurs {m, p * r) étant par définition très courte.1 \ v- w \ I is minimal. In the cryptosystem NTRU, the cipher is e = r * h + m {mod q), so the vector {e, 0) is close to the vector (p * r * h {mod q), p * r) of the L_NTRU , the difference between the two vectors {m, p * r) being by definition very short.

L'invention permet de rendre le cryptosystème NTRU adapté aux appareils de faibles capacités et passifs, grâce à la modification de la méthode de génération et de multiplication de polynômes en produisant plusieurs produits de deux polynômes à partir d'un seul produit existant. The invention makes the NTRU cryptosystem suitable for low capacitance and passive devices, by modifying the method of generating and multiplying polynomials by producing several products of two polynomials from a single existing product.

La valeur p du cryptosystème NTRU peut être égale à 2. Le domaine polynomial D_m est dans ce cas l'ensemble des polynômes binaires.The value p of the cryptosystem NTRU can be equal to 2. The polynomial domain D_m is in this case the set of binary polynomials.

La valeur N du cryptosystème NTRU peut être égale à 251. The N value of the NTRU cryptosystem can be equal to 251.

La valeur q du cryptosystème NTRU peut être égale à 113. The q value of the NTRU cryptosystem can be equal to 113.

Les valeurs N et q du cryptosystème NTRU peuvent notamment être n'importe quel couple valide pour p = 2. The values N and q of the cryptosystem NTRU may in particular be any valid pair for p = 2.

Dans le cas où (N p, q) = (251, 2, 113), chaque coefficient peut être écrit sur 8 bits. Par conséquent, chaque rotation vers la droite par s bits du produit r * h, où s est un multiple de 8, correspond à un nouveau produit r' * h, où r' est une rotation vers la droite de r de s bits. Chaque r * h + rot^r * h) correspond au nouveau produit r_s * h où r_s = r + r' .In the case where (N p, q) = (251, 2, 113), each coefficient can be written on 8 bits. Therefore, every rotation to the right by s bits of the product r * h, where s is a multiple of 8, corresponds to a new product r '* h, where r' is a rotation to the right of r of s bits. Each r * h + rot ^ r * h) corresponds to the new product r_s * h where r_s = r + r '.

L'invention est avantageusement conçue pour les appareils à faibles capacités. Toutes les opérations complexes pour les appareils, comme par exemple la multiplication de polynômes, la génération des polynômes aléatoires dans le domaine polynomial D_m du cryptosystème NTRU, ou le calcul des modulos, sont réalisées par le domaine d'administration.The invention is advantageously designed for low capacity devices. All the complex operations for the devices, as for example the multiplication of polynomials, the generation of the random polynomials in the polynomial domain D_m of cryptosystem NTRU, or the calculation of modulos, are carried out by the administration domain.

Les coefficients d'un polynôme utilisé dans la mise en œuvre de l'invention sont de préférence écrit sur E(log₂(2q-l)+l) bits, E représentant la partie entière.The coefficients of a polynomial used in the implementation of the invention are preferably written on E (log₂ (2q-1) + 1) bits, where E represents the integer part.

L'appareil peut n'enregistrer que 2N + n bits, avec n = E(log₂(2q-l)+l) *N, et peut ne supporter qu'un générateur de séquences pseudo-aléatoires de 32 bits dans le cas où (N, p, q) = (251, 2, 113) et une fonction de calcul légère, c'est-à-dire compacte, de faible puissance et nécessitant une faible énergie, dont la sortie est supérieure ou égale à N bits. Les calculs effectués par l'appareil sont de préférence limités aux deux valeurs de la fonction de calcul, au calcul d'une séquence pseudo-aléatoire, et, dans le cas où (N, p, q) = (251 , 2, 1 13), à 8N + n + 1024 décalages à droite au maximum, à 4n additions binaires et à N + n + 32 opérations mettant en œuvre l'opérateur « ou exclusif» pour un générateur pseudo-aléatoire de 32 bits.The device can record only 2N + n bits, with n = E (log₂ (2q-1) + 1) * N, and can support only a pseudo-random sequence generator of 32 bits in the case where (N, p, q) = (251, 2, 113) and a light, i.e. compact, low power, low energy requiring function, whose output is greater than or equal to N bits. The calculations made by the apparatus are preferably limited to the two values of the computation function, to the computation of a pseudo-random sequence, and, in the case where (N, p, q) = (251, 2, 1 13), at 8N + n + 1024 maximum right shifts, 4n binary additions and N + n + 32 operations implementing the "or exclusive" operator for a 32-bit pseudo-random generator.

D'autre part, le domaine d'administration peut effectuer des opérations de décalage à gauche et à droite et deux algorithmes NTRU pour le cryptage et le décryptage, chacun avec une complexité de 0(N²). Le domaine d'administration peut authentifier les appareils sans effectuer de recherche exhaustive.On the other hand, the administration domain can perform left and right shift operations and two NTRU algorithms for encryption and decryption, each with a complexity of 0 (N² ). The administration domain can authenticate devices without performing an exhaustive search.

Dans les spécifications du cryptosystème NTRU, r est un petit polynôme. De manière connue, ses coefficients sont pris dans {—1, 0, 1}. Dans les procédés selon l'invention, certains coefficients de ce polynôme r peuvent être égaux à—2 et/ou à 2. In the specifications of the NTRU cryptosystem, r is a small polynomial. In known manner, its coefficients are taken in {-1, 0, 1}. In the methods according to the invention, certain coefficients of this polynomial r can be equal to 2 and / or 2.

Une telle modification n'a pas de conséquence significative sur la sécurité du cryptosystème NTRU. En effet, pour casser la clé privée (#, /), il est nécessaire de résoudre un problème SVP dans le réseau L_NTRU, indépendant du choix du polynôme r. En outre, le problème de décryptage pouvant être considéré comme un problème CVP, la différence entre le vecteur (e, 0) et le vecteur (p * r * h (mod q), p * r) du L_NTRU, est égale à (m, p * r), donc si quelques coefficients de r sont égaux à—2 et/ou 2, la différence (m, p * r) reste très petite. Pour un attaquant, décrypter un message issu d'un cryptage NTRU dans lequel quelques coefficients de r sont égaux à—2 et/ou à 2 reste un problème CVP dans le réseau L_NTRU.Such a modification has no significant consequence on the security of the NTRU cryptosystem. Indeed, to break the private key (#, /), it is necessary to solve a problem SVP in the network L_NTRU , independent of the choice of the polynomial r. Moreover, since the decoding problem can be considered as a CVP problem, the difference between the vector (e, 0) and the vector (p * r * h (mod q), p * r) of the L_NTRU is equal to (m, p * r), so if some coefficients of r are equal to-2 and / or 2, the difference (m, p * r) remains very small. For an attacker, decrypt a message from an NTRU encryption in which some coefficients of r are equal to-2 and / or 2 remains a CVP problem in the network L_NTRU .

Cryptage des données Data Encryption

Les données peuvent être cryptées en leur ajoutant un produit r_s*h déterminé à partir d'au moins deux rotations du produit r*h. L'une des rotations dudit produit peut être la fonction identité.The data can be encrypted by adding a product r_s * h determined from at least two rotations of the product r * h. One of the rotations of said product may be the identity function.

Ladite au moins une rotation du produit r*h peut être une rotation dudit produit vers la droite par k*E(log₂(2q-l)+l) fois le nombre de 1 d'une séquence pseudo-aléatoire r_h k étant un entier et E représentant la partie entière. Le produit r_s*h peut être alors égal à : r *h = r*h + rot(r*h, k*E(log₂(2q-l)+l) ' r_t).Said at least one rotation of the product r * h may be a rotation of said product to the right by k * E (log₂ (2q-1) + 1) times the number of 1 of a pseudo-random sequence r_h k being an integer and E representing the integer part. The product r_s * h can then be equal to: r * h = r * h + rot (r * h, k * E (log₂ (2q-1) + l) 'r_t ).

Dans le cas où les valeurs de (N, p, q) du cryptosystème NTRU sont 251, 2 et 113, la rotation du produit r*h peut être une rotation dudit produit vers la droite par 32 fois le nombre de 1 de la séquence pseudo-aléatoire, k étant un entier. Le produit r_s*h peut être égal à :In the case where the values of (N, p, q) of the cryptosystem NTRU are 251, 2 and 113, the rotation of the product r * h can be a rotation of said product to the right by 32 times the number of 1 of the sequence pseudo-random, where k is an integer. The product r_s * h may be equal to:

r_s*h = r*h + rot(r*h, 32 ' r_t).r_s * h = r * h + rot (r * h, 32 'r_t ).

Echange de données Data exchange

Le message peut être construit en convertissant une séquence pseudo-aléatoire en un polynôme binaire. La séquence pseudo-aléatoire peut être calculée par une fonction de calcul appliquée à la séquence pseudo-aléatoire générée par l'appareil après une sollicitation du domaine d'administration et à ladite valeur d'initialisation contenue dans la mémoire de l'appareil. The message can be constructed by converting a pseudo-random sequence into a binary polynomial. The pseudo-random sequence can be computed by a calculation function applied to the pseudo-random sequence generated by the apparatus after a solicitation of the administration domain and to said initialization value contained in the memory of the apparatus.

La fonction de calcul peut mettre en œuvre une fonction de hachage H, le message pouvant être égal à : The calculation function can implement a hash function H, the message being equal to:

m = B2P(H(s@r_t)), où B2P représente une opération transformant une séquence binaire en un polynôme binaire.m = B2P (H (s @ r_t )), where B2P represents an operation transforming a binary sequence into a binary polynomial.

Cette fonction de hachage, dont la sortie est supérieure ou égale à N bits, est de préférence légère, c'est-à-dire compacte, de faible puissance et nécessitant une faible énergie, comme notamment la fonction de hachage connue Keccak, décrite dans "A Lightweight Implementation ofi Keccak Hash Function for Radio-Frequency Identification Applications" de E. B. Kavun and T. Yalcin, Lecture Notes in Computer Science, S. O. Yalcin, Ed., vol. 6370, Springer, Juin 2010, pp. 258-269. This hash function, whose output is greater than or equal to N bits, is preferably light, that is to say compact, of low power and requiring low energy, such as in particular the known hash function Keccak, described in "A Lightweight Implementation of Keccak Hash Function for Radio-Frequency Identification Applications" by EB Kavun and T. Yalcin, Lecture Notes in Computer Science, SO Yalcin, Ed., Vol. 6370, Springer, June 2010, pp. 258-269.

Après transmission du premier nombre au domaine d'administration, l'appareil peut remplacer dans sa mémoire la valeur d'initialisation par une valeur calculée par une fonction de calcul appliquée à la séquence pseudo-aléatoire précédemment générée par l'appareil et à l'ancienne valeur d'initialisation. La fonction de calcul peut mettre en œuvre la fonction de hachage H, la valeur d'initialisation étant par exemple remplacée par H(s@r_t).After transmission of the first number to the administration domain, the apparatus can replace in its memory the initialization value by a value calculated by a calculation function applied to the pseudo-random sequence previously generated by the apparatus and to the old initialization value. The calculation function can implement the hash function H, the initialization value being for example replaced by H (s @ r_t ).

Le décryptage du premier nombre par le domaine d'administration permet d'identifier l'appareil. Decrypting the first number by the administration domain makes it possible to identify the device.

Authentification Authentication

Le domaine d'administration peut posséder une seule clé privée (g, fi) pour authentifier tous les appareils, et peut être initialisée avec un seul identifiant pour chaque appareil. Le domaine d'administration peut authentifier un appareil sans connaître au préalable son identité, une seule clé privée (g, f) pouvant être utilisée pour authentifier tous les appareils, ce qui est indispensable dans certaines applications où une authentifïcation « offline », c'est-à-dire sans connexion au réseau, est nécessaire.The administration domain can have a single private key (g, fi) to authenticate all devices, and can be initialized with a single identifier for each device. The administration domain can authenticate a device without first knowing its identity, a single private key (g, f) that can be used to authenticate all the devices, which is essential in certain applications where "offline" authentication, that is to say without a connection to the network, is necessary.

Le deuxième nombre peut être généré par application d'une fonction de calcul mettant en œuvre une rotation vers la gauche des produits r '*h et r*h. Le deuxième nombre peut notamment s'écrire : The second number can be generated by applying a calculation function implementing a left rotation of products r '* h and r * h. The second number can be written in particular:

e₂ = rof'(r '*h, r*h + rot(r*h, k*E(log₂(2q-l) +l) ' r_t)) ® (r*h + rot(r*h, k*E(log₂(2q-l) +l) ' r_t)).e₂ = rof '(r' * h, r * h + rot (r * h, k * E (log₂ (2q-1) + l) 'r_t )) ® (r * h + rot (r * h, k * E (log₂ (2q-1) + 1) (r_t )).

Dans le cas où les valeurs (TV, p, q) du cryptosystème NTRU sont égales à (251 , 2, 1 13), le deuxième nombre peut s'écrire : In the case where the values (TV, p, q) of the cryptosystem NTRU are equal to (251, 2, 1 13), the second number can be written:

e₂ = rof'(r '*h, r*h + rot(r*h, 32 ' r_t)) ® (r*h + rot(r*h, 32 ' r_t)).e₂ = rof '(r' * h, r * h + rot (r * h, 32 'r_t )) ® (r * h + rot (r * h, 32' r_t )).

Le troisième nombre peut être généré par une fonction de calcul appliquée au produit r '*h et au message, la fonction de calcul mettant en œuvre la fonction de hachage H. Le troisième nombre peut par exemple être égal à : The third number can be generated by a calculation function applied to the product r '* h and the message, the calculation function implementing the hash function H. The third number can for example be equal to:

e₃ = H((r '*h) @m).e₃ = H ((r '* h) @m).

Le quatrième nombre peut être égal à : The fourth number can be:

β4 = r_s '*h + id©m,β4 = r_s ' * h + id m m,

le produit r_s '*h pouvant être égal à r ' *h+rot(r ' *h,E(log₂(2q-l) +l) 'm).the product r_s '* h may be equal to r' * h + rot (r '* h, E (log₂ (2q-l) + l)' m).

Dans le cas où les valeurs de (TV, p, q) du cryptosystème NTRU sont 251 , 2 et 1 13, le produit r_s '*h peut être égal à r' * h + rot(r' * h, 8'm) .In the case where the values of (TV, p, q) of the cryptosystem NTRU are 251, 2 and 1 13, the product r_s '* h may be equal to r' * h + rot (r '* h, 8' m).

Appareil Apparatus

L'appareil, ne disposant pas de clé privée, peut utiliser la clé publique du domaine d'administration pour crypter le message. The device, which does not have a private key, can use the public key of the administration domain to encrypt the message.

L'appareil peut transmettre d'autres informations que le message crypté au domaine d'administration lors de la transmission du premier nombre, par exemple, dans le cas où l'appareil est un capteur, des données transmises par ce dernier. The device can transmit other information than the encrypted message to the administration domain when transmitting the first number, for example, in the case where the device is a sensor, data transmitted by the latter.

L'appareil peut être porté par un article lors de son traitement par une chaîne logistique dans le cadre de la livraison d'articles. Il peut par exemple remplacer un code à barres ou être disposé sur l'article en complément de ce dernier. L'invention permet de résoudre des problèmes de contrefaçon, de mauvais reconditionnement des articles, et évite également que des articles soient illégalement scannés en vue d'un inventaire détaillé. L'invention permet en effet de réaliser de façon sécurisée les inventaires, le contrôle de l'expédition, le contrôle de la réception, le suivi industriel en chaîne de montage, ou encore la traçabilité des médicaments. Le suivi de la chaîne logistique de bout en bout où de multiples entités interviennent, telles que par exemple les producteurs, les transporteurs, les entreposeurs, est également possible.The device can be carried by an article during its processing by a supply chain in the context of the delivery of articles. It can for example replace a barcode or be arranged on the article in addition to the latter. The invention solves problems of counterfeiting, bad reconditioning articles, and also prevents items from being illegally scanned for a detailed inventory. The invention makes it possible to securely carry out the inventories, the control of the shipment, the control of the reception, the industrial follow-up in the assembly line, or the traceability of the drugs. End-to-end supply chain tracking where multiple entities involved, such as for example producers, transporters, warehousemen, is also possible.

En variante, l'appareil est porté par un document de sécurité et permet d'authentifier une personne et/ou d'autoriser son accès à une zone à accès restreint, par exemple un espace privé ou un espace pour lequel un contrôle de sécurité est nécessaire, tel que par exemple dans un service de transport par métro ou avion, dans des zones contrôlées des aéroports, dans des bâtiments sensibles, des universités, des clubs privés, ou encore lors d'un événement de masse, comme un spectacle ou un événement sportif dans un stade. Alternatively, the device is carried by a security document and can authenticate a person and / or allow access to a restricted area, for example a private area or a space for which a security check is necessary, such as in a transport service by metro or plane, in controlled areas of airports, in sensitive buildings, universities, private clubs, or at a mass event, such as a show or a sporting event in a stadium.

En variante encore, l'appareil est porté par un objet réservé à la vente, à la location ou au prêt, par exemple dans des bibliothèques, médiathèques, vidéothèques, ou autres magasins ou ventes aux enchères, permettant de faciliter les inventaires et faisant office de système antivol. In another variant, the apparatus is carried by an object reserved for sale, rental or loan, for example in libraries, media libraries, video libraries, or other stores or auctions, to facilitate inventories and acting anti-theft system.

Dans les exemples ci-dessus, l'appareil peut inclure des métadonnées relatives à l'objet sur lequel il est disposé, par exemple des propriétés de cet objet. L'appareil peut être associé à une personne, par exemple par implant RFID, et peut inclure des métadonnées, telles que par exemple son groupe sanguin, ses allergies, son nom, ou son adresse. L'invention garantit aux utilisateurs la sécurité de ces métadonnées, et le respect de la vie privée du porteur. In the examples above, the apparatus may include metadata relating to the object on which it is disposed, for example properties of this object. The apparatus may be associated with a person, for example by RFID implant, and may include metadata, such as, for example, blood type, allergies, name, or address. The invention guarantees users the security of these metadata, and the respect of the privacy of the wearer.

Dans d'autres variantes, l'appareil est porté par ou attaché à des bagages, faisant par exemple partie d'étiquettes utilisées dans le transport aérien. L'invention permet une automatisation sécurisée de la gestion des bagages dans les aéroports, améliorant la flexibilité et la performance des processus opérationnels. Le taux de lecture des appareils RFID est proche de 100%, contre 15 % de non- lecture avec les systèmes connus utilisant des codes à barres. In other variants, the apparatus is carried by or attached to luggage, for example part of labels used in air transport. The invention enables secure automation of baggage handling at airports, improving the flexibility and performance of business processes. The reading rate of RFID devices is close to 100%, against 15% of non-reading with known systems using bar codes.

En variante encore, l'appareil est porté par un être humain dans un but de surveillance de ce dernier. L'appareil est par exemple intégré à un collier, un bracelet ou tout autre accessoire ou vêtement pouvant être porté par un être humain afin de pouvoir surveiller ou repérer ce dernier. L'invention peut être utilisable pour un suivi sécurisé et personnalisé des personnes dépendantes, par exemple dans le contexte d'une maternité, d'une garderie, d'une maison de retraite, ou d'un hôpital. L'invention peut également remplacer les bracelets électroniques utilisés pour surveiller des personnes et renseigner sur les antécédents judiciaires des personnes. In another variant, the device is worn by a human being for the purpose of monitoring the latter. The device is for example integrated into a necklace, a bracelet or any other accessory or garment that can be worn by a human being in order to monitor or locate the latter. The invention can be used for secure and personalized monitoring of dependent persons, for example in the context of a maternity ward, a nursery, a retirement home, or a hospital. The invention can also replace electronic bracelets used to monitor people and provide information on people's criminal record.

Dans une autre variante, l'appareil peut être porté par des équipements électroménagers, des objets d'une maison ou une voiture. Après un nouvel achat, l'appareil peut être associé au domaine d'administration de l'acheteur, lui permettant de gérer la sécurité de son réseau domestique, et par exemple d'appairer ses équipements, objets et/ou voitures à son domicile de façon sécurisée. Si l'appareil est inclus dans une voiture, le système de verrouillage de celle-ci peut être personnalisé en fonction de son propriétaire. Un même équipement, tel un badge ou un téléphone mobile, peut permettre de déverrouiller plusieurs systèmes et peut aussi servir à administrer les divers équipements de l'environnement domestique de l'acheteur.In another variant, the device can be carried by household appliances, objects of a house or a car. After a new purchase, the device can be associated with the buyer's domain of administration, allowing him to manage the security of his home network, and for example to pair his equipment, objects and / or cars to his home in a secure way. If the device is included in a car, the locking system of the car can be customized according to its owner. The same equipment, such as a badge or a mobile phone, can unlock multiple systems and can also be used to administer the various equipment in the home environment of the buyer.

Dans le cas où l'appareil est un capteur, par exemple de température, de chocs, ou d'humidité, il peut servir au suivi d'une chaîne logistique. L'appareil peut délivrer uniquement ses alarmes au domaine d'administration autorisé, après une authentification mutuelle réussie. In the case where the device is a sensor, for example temperature, shock, or humidity, it can be used to monitor a supply chain. The device can only issue its alarms to the authorized administration domain, after a successful mutual authentication.

Le capteur, grâce à l'invention, peut transmettre un faible volume de données, telles que des relevés de température ou des alertes diverses, de façon très sécurisée à un domaine d'administration autorisé, et ce avec un très faible coût en ressources. The sensor, thanks to the invention, can transmit a small volume of data, such as temperature readings or various alerts, very securely to an authorized administration domain, and with a very low resource cost.

L'invention pourra être mieux comprise à la lecture de la description détaillée qui va suivre, d'un exemple non limitatif de mise en œuvre de celle-ci, et à l'examen du dessin annexé, sur lequel : The invention may be better understood on reading the following detailed description of a nonlimiting example of implementation thereof, and on examining the appended drawing, in which:

- la figure 1 est un schéma représentant différentes étapes d'échange entre un domaine d'administration et un appareil dans un exemple de mise en œuvre de l'invention. Un domaine d'administration 2 et un appareil 3 sont représentés à la figure 1. - Figure 1 is a diagram showing different stages of exchange between a field of administration and an apparatus in an exemplary implementation of the invention. An administration domain 2 and an apparatus 3 are shown in FIG.

Bien qu'un seul appareil 3 ait été représenté sur la figure 1 , l'invention s'applique à un nombre quelconque d'appareils.Although only one apparatus 3 has been shown in FIG. 1, the invention applies to any number of devices.

Le domaine d'administration utilise un cryptosystème NTRU (N, p, q) à clé publique h et polynôme r de degré inférieur ou égal à (N - 1) choisi aléatoirement dans le domaine polynomial D_r du cryptosystème NTRU.The administration domain uses a cryptosystem NTRU (N, p, q) public key h and polynomial r of degree less than or equal to (N - 1) randomly chosen in the polynomial domain D_r of the cryptosystem NTRU.

Le domaine d'administration 2 et l'appareil 3 comportent chacun une mémoire. L'appareil 3 comprend dans sa mémoire un identifiant unique id appartenant au domaine polynomial D_m du cryptosystème NTRU. L'appareil 3 est initialisé avec une valeur d'initialisation s de Nbits choisie aléatoirement et avec le produit r*h.The administration domain 2 and the apparatus 3 each comprise a memory. The apparatus 3 comprises in its memory a unique identifier id belonging to the polynomial domain D_m of the NTRU cryptosystem. The apparatus 3 is initialized with an initialization value s of Nbits chosen randomly and with the product r * h.

Le domaine d'administration 2 et l'appareil 3 peuvent être tels que décrits précédemment. The administration domain 2 and the apparatus 3 may be as previously described.

On va décrire, en référence à la figure 1 , un exemple d'itération des procédés d'échange de données et d' authentification selon l'invention. Lorsque l'appareil 3 est sollicité par le domaine d'administration à une étape 10, il génère une séquence pseudo-aléatoire r_t de 32 bits, et récupère dans sa mémoire la valeur d'initialisation s et le produit r * h. L'appareil 3 construit un message m, qui est un vecteur de n bits, en convertissant une séquence pseudo-aléatoire en un polynôme binaire. La séquence pseudo-aléatoire est calculée par une fonction de calcul appliquée à la séquence pseudoaléatoire r_t et à la valeur s. La fonction de calcul met en œuvre une fonction de hachage H. Le message m est égal à :An example of iteration of the data exchange and authentication methods according to the invention will be described with reference to FIG. When the apparatus 3 is requested by the administration domain in a step 10, it generates a pseudo-random sequence r_t of 32 bits, and recovers in its memory the initialization value s and the product r * h. The apparatus 3 constructs a message m, which is a vector of n bits, by converting a pseudo-random sequence into a binary polynomial. The pseudo-random sequence is computed by a computation function applied to the pseudo-random sequence r_t and the value s. The calculation function implements a hash function H. The message m is equal to:

m = B2P(H(s®r_t)),m = B2P (H (s®r_t)),

où BIP: {0, 1}'→ D_m : convertit une séquence binaire pseudo-aléatoire en un polynôme binaire, avec l≥ N.where BIP: {0, 1} '→ D_m : converts a pseudo-random binary sequence into a binary polynomial, with l≥ N.

L'appareil 3 calcule ensuite, pour crypter le message m, le produit r_s * h déterminé à partir d'au moins une rotation du produit r*h. Le produit r_s*h est notamment déterminé à partir d'au moins deux rotations du produit r*h, l'une des rotations du produit r*h pouvant être la fonction identité.The apparatus 3 then calculates, to encrypt the message m, the product r_s * h determined from at least one rotation of the product r * h. The product r_s * h is in particular determined from at least two rotations of the product r * h, one of the rotations of the product r * h may be the identity function.

Une rotation du produit r*h est avantageusement une rotation dudit produit vers la droite par k*E(log₂(2q-l)+l) fois le nombre de 1 de la séquence r_t pseudo-aléatoire, k étant un entier. Ainsi, le produit r_s*h est égal à :A rotation of the product r * h is advantageously a rotation of said product to the right by k * E (log₂ (2q-1) + 1) times the number of 1 of the sequence r_t pseudo-random, k being an integer. Thus, the product r_s * h is equal to:

r_s*h = r*h + rot(r*h, k*E(log₂(2q-l)+l) ' r_t).r_s * h = r * h + rot (r * h, k * E (log₂ (2q-l) + l) 'r_t ).

L'appareil 3 remplace dans sa mémoire la valeur d'initialisation s par une valeur calculée par une fonction de calcul appliquée à la séquence pseudo-aléatoire r_t et à l'ancienne valeur d'initialisation s, la fonction de calcul mettant en œuvre la fonction de hachage H. La valeur d'initialisation s est ainsi remplacée par H(s@r_t).The device 3 replaces in its memory the initialization value s by a value calculated by a calculation function applied to the pseudo-random sequence r_t and to the old initialization value s, the calculation function implementing the hash function H. The initialization value is thus replaced by H (s @ r_t ).

L'appareil 3 remplace également dans sa mémoire la valeur du produit r*h par une rotation de ce produit, notamment par rot(r*h, k*E(log₂(2q-l)+l) ' r_t).The apparatus 3 also replaces in its memory the value of the product r * h by a rotation of this product, in particular by rot (r * h, k * E (log₂ (2q-1) + 1) (r_t ).

L'appareil 3 génère un premier nombre ei pour crypter le message m en lui ajoutant le produit r_s * h, le premier nombre s 'écrivant alors : e = r_s * h + m.The apparatus 3 generates a first number ei to encrypt the message m by adding the product r_s * h, the first number then writing: e = r_s * h + m.

Dans une étape 11, l'appareil 3 transmet le premier nombre ei au domaine d'administration 2. In a step 11, the device 3 transmits the first number ei to the administration domain 2.

Si la précédente tentative d'authentification a été achevée avec succès, le premier nombre e s'écrit, de façon polynomiale : If the previous authentication attempt has been successfully completed, the first number e is written polynomially:

e_i = r_s * h + m = {X^HW^ + l) * r * i + m mod(^w - 1),e_i = r_s * h + m = {X^HW ^ + l) * r * i + m mod (^w - 1),

où HW représente le poids de Hamming.where HW represents the weight of Hamming.

Si une ou plusieurs tentatives ont échoué, e s'écrit, de façon polynomiale : e₁ = r_s * h + m = (X^l + X^j) * r * h + m ταοά{Χ^Ν — 1).If one or more attempts have failed, e is written polynomially: e₁ = r_s * h + m = (X^l + X^j ) * r * h + m ταοά {Χ^Ν - 1).

L'appareil 3 peut transmettre d'autres informations que le message m crypté au domaine d'administration 2 lors de la transmission du premier nombre ei. The apparatus 3 may transmit other information than the encrypted message m to the administration domain 2 when transmitting the first number ei.

Dès la réception de la réponse de l'appareil 3, le domaine d'administration 2 décrypte le premier nombre e afin de retrouver le message m. Le premier nombre e est décrypté par e mod q, qui est une valeur valide, e mod q étant calculable par le domaine d'administration 2 car chacun de ses coefficients est inférieur à 2q — 1, chaque coefficient du produit r_s * h est dans {0, 1, ... , 2q— 2} et chaque coefficient du message m est dans {0, 1}.As soon as the response from the device 3 is received, the administration domain 2 decrypts the first number e in order to retrieve the message m. The first number e is decrypted by e mod q, which is a valid value, e mod q being computable by the administration domain 2 because each of its coefficients is less than 2q-1, each coefficient of the product r_s * h is in {0, 1, ..., 2q- 2} and each coefficient of the message m is in {0, 1}.

Le domaine d'administration 2 choisit ensuite aléatoirement un polynôme r' de degré inférieur ou égal à (N- 1) dans le domaine polynomial D_r du cryptosystème NTRU.The administration domain 2 then randomly selects a polynomial r 'of degree less than or equal to (N-1) in the polynomial domain D_r of the NTRU cryptosystem.

Le domaine d'administration 2 génère un deuxième nombre e₂ par application d'une fonction de calcul mettant en œuvre une rotation vers la gauche des produits r'*h et r*h, notamment :The administration domain 2 generates a second number e₂ by applying a calculation function implementing a left rotation of the products r '* h and r * h, in particular:

e₂ = rof'(r '*h, r*h + rot(r*h, k*E(log₂(2q-l)+l) ' r_t)) ® (r*h + rot(r*h, k*E(log₂(2q-l)+l) ' r_t)).e₂ = rof '(r' * h, r * h + rot (r * h, k * E (log₂ (2q-1) + l) 'r_t )) ® (r * h + rot (r * h, k * E (log₂ (2q-1) + 1) (r_t )).

Le domaine d'administration 2 génère un troisième nombre par une fonction de calcul appliquée au produit r'*h et au message m, la fonction de calcul mettant en œuvre la fonction de hachage H, notamment = H((r'*h)®m). The administration domain 2 generates a third number by a calculation function applied to the product r '* h and the message m, the calculation function implementing the hash function H, in particular = H ((r' * h) ®M).

Dans une étape 12, le domaine d'administration 2 transmet à l'appareil 3 les deuxième et troisième nombres e₂ etIn a step 12, the administration domain 2 transmits to the apparatus 3 the second and third numbers e₂ and

Dès la réception du deuxième nombre e₂, l'appareil 3 retrouve le produit r' * h par r' * h = rotÇe₂ ® r_s * h, r_s * h). L'appareil 3 authentifie le domaine d'administration 2 en comparant le troisième nombre e₃ à un nombre généré à partir du produit r '*h et du message m. Le produit r'*h ne peut être généré que par un domaine d'administration légitime qui possède la clé privée (g, f), assurant ainsi la sécurité de l'authentifïcation.Upon receipt of the second number e₂ , the apparatus 3 finds the product r * * h by r '* h = rotie₂ ® r_s * h, r_s * h). The apparatus 3 authenticates the administration domain 2 by comparing the third number e₃ with a number generated from the product r '* h and the message m. The product r * * h can only be generated by a legitimate administration domain which has the private key (g, f), thus ensuring the security of the authentication.

En cas d'égalité à l'issue de cette comparaison, le domaine d'administration 2 est authentifié, sinon l'appareil 3 annule la session, en concluant que le domaine d'administration n'a pas pu déchiffrer le premier nombre e correctement. In case of equality after this comparison, the administration domain 2 is authenticated, otherwise the apparatus 3 cancels the session, concluding that the administration domain could not decipher the first number e correctly. .

Si le domaine d'administration 2 est authentifié, l'appareil 3 génère un quatrième nombre β4 à partir d'un produit r_s '*h, calculé à partir d'au moins une rotation du produit r'*h et du message m, de l'identifiant id de l'appareil et du message m, le quatrième nombre β4 étant notamment égal r_s '*h + id®m. Le produit r_s '*h est égal à :If the administration domain 2 is authenticated, the apparatus 3 generates a fourth number β4 from a product r_s '* h, calculated from at least one rotation of the product r' * h and the message m , the identifier id of the apparatus and the message m, the fourth number β4 being in particular equal to_s * h + id®m. The product r_s ' * h is equal to:

r'_s *h= r' *h+rot(r ' *h,E(log₂(2q - \) + \) 'm). Similairement au premier nombre e_l5 le quatrième nombre e₄ peut s'écrire :r '_s * h = r' * h + rot (r '* h, E (log₂ (2q - \) + \)' m). Similarly to the first number e₁₅ the fourth number e₄ can be written:

e₄ =_rs' * h + m © id = (x^HW(^m) + l) *_r' * h + m © id mod(^w - 1).e₄ =_rs '* h + m' id = (x^HW (^m ) + l) *_r '* h + m' id mod (^w - 1).

Dans une étape 13, l'appareil 3 transmet au domaine d'administration 2 le quatrième nombre e₄.In a step 13, the apparatus 3 transmits to the administration domain 2 the fourth number e₄ .

Le domaine d'administration 2 authentifie et trouve l'identité de l'appareil 3 en calculant son identifiant id = (e — r_s * K) © m, ou en décryptant le quatrième nombre e mod q pour retrouver le terme m © id et donc l'identifiant id de l'appareil 3.The administration domain 2 authenticates and finds the identity of the device 3 by calculating its identifier id = (e - r_s * K) m m, or by decrypting the fourth number e mod q to find the term m id id and therefore the ID id of the device 3.

La valeur d'initialisation s et le produit r*h sont réinitialisés dans la mémoire de l'appareil 3, la valeur d'initialisation s étant remplacée par H(r * h) et le produit r * h par le produit r' * h. The initialization value s and the product r * h are reset in the memory of the device 3, the initialization value s being replaced by H (r * h) and the product r * h by the product r * h.

La prochaine session d'authentification de l'appareil 3 est alors exécutée avec le produit r * h. The next authentication session of the device 3 is then executed with the product r * h.

Dans le cas où les valeurs (N, p, q) du cryptosystème NTRU du domaine d'administration 2 sont 251 , 2 et 113, la rotation du produit r*h est une rotation dudit produit vers la droite par 32 fois le nombre de 1 de la séquence r_t pseudo-aléatoire, k étant un entier. Le produit r_s*h est égal à r*h + rot(r*h, 32 ' r_t). Le produit r_s '*h est égal à r '*h + rot(r'*h, 8 ' m).In the case where the values (N, p, q) of the cryptosystem NTRU of the administration domain 2 are 251, 2 and 113, the rotation of the product r * h is a rotation of said product to the right by 32 times the number of 1 of the sequence r_t pseudo-random, k being an integer. The product r_s * h is equal to r * h + rot (r * h, 32 'r_t ). The product r_s '* h is equal to r' * h + rot (r '* h, 8' m).

Dans le cas « inter-domaine », c'est-à-dire dans les cas où l'appareil 3 change de domaine d'administration 2, par exemple dans un environnement de chaîne logistique, le domaine d'administration précédent met à jour la clé publique h' du domaine d'administration suivant dans l'appareil 3. La génération des deuxième, troisième et quatrième nombres e?, et e₄ ne se fait plus à partir de la clé publique h, mais à partir de ladite clé publique h' du domaine d'administration suivant.In the "inter-domain" case, i.e., in cases where the apparatus 3 changes administration domain 2, for example in a supply chain environment, the previous administration domain updates. the public key h 'of the next administration domain in the device 3. The generation of the second, third and fourth numbers e ?, and e_{4 is} no longer made from the public key h, but from said key public to the following area of administration.

L'invention n'est pas limitée à l'exemple qui vient d'être décrit. The invention is not limited to the example which has just been described.

L'invention, disposant d'un très haut niveau de sécurité, peut avantageusement remplacer des solutions d'authentification plus gourmandes en capacités, permettant la réduction des coûts d'exploitation. The invention, having a very high level of security, can advantageously replace more capacity-intensive authentication solutions, allowing the reduction of operating costs.

En outre, l'invention peut permettre d'obtenir les avantages suivants. In addition, the invention can provide the following advantages.

Pour chaque session d'authentification, les messages échangés sont personnalisés, le domaine d'administration et l'appareil générant des nouvelles valeurs pseudo-aléatoires m, r_s*h et r'*h. Une attaque par rejeu sur le domaine d'administration a très peu de chances d'aboutir, car, le domaine d'administration utilisant un générateur efficace de séquences de polynômes pseudo-aléatoires, la même valeur a peu de chances d'être générée. Ce type d'attaque vise à aboutir à une mauvaise identification ou authentifîcation, ou à la duplication d'une transaction. Par exemple, les messages échangés entre un appareil 3 et un domaine d'administration 2 légitimes peuvent être interceptés par un intrus qui peut se servir de ces messages pour tenter de s'authentifier auprès du domaine d'administration même si les messages sont chiffrés.For each authentication session, the exchanged messages are personalized, the administration domain and the device generating new pseudo-random values m, r_s * h and r '* h. A replay attack on the domain of administration has very little chance of success because, since the domain of administration uses an efficient generator of pseudo-random polynomial sequences, the same value is unlikely to be generated. This type of attack is aimed at misidentifying or authenticating or duplicating a transaction. For example, messages exchanged between a legitimate device 3 and a legitimate administration domain 2 may be intercepted by an intruder who can use these messages to attempt to authenticate with the administration domain even if the messages are encrypted.

Une attaque par rejeu sur l'appareil 3 peut survenir uniquement si l'attaquant empêche l'appareil de recevoir les deuxième et troisième nombres ¾ et ej, l'appareil générant alors les même données m et r_s*h dans la prochaine session d' authentifîcation. Ceci est largement négligeable en termes de probabilités.A replay attack on the apparatus 3 may only occur if the attacker prevents the apparatus from receiving the second and third numbers ¾ and ej, the apparatus then generating the same data m and r_s * h in the next session. Authentication. This is largely negligible in terms of probabilities.

L'invention permet également de se protéger des attaques de l'homme du milieu. The invention also makes it possible to protect oneself from the attacks of the middle man.

Le but d'un tel attaquant est de s'authentifier soit comme appareil légitime, soit comme domaine d'administration légitime.The purpose of such an attacker is to authenticate either as a legitimate device or as a legitimate domain of administration.

Si l'attaquant est passif, c'est-à-dire s'il ne peut pas interroger l'appareil 3 mais qu'il peut écouter les échanges entre celui-ci et le domaine d'administration 2, il ne peut faire qu'une attaque par rejeu. En effet, l'attaquant, voulant être authentifié comme un appareil légitime, doit produire un message valide, le quatrième nombre β₄, ou retrouver l'identifiant id. L'attaquant ne peut pas produire un message valide en utilisant les messages échangés durant les sessions précédentes, toute modification du premier nombre ei étant nécessairement détectée dans le calcul du quatrième nombre ¾ grâce au calcul du troisième nombre e?, mettant en œuvre la fonction de hachage, et grâce à la valeur pseudo-aléatoire r_s '*h générée par le domaine d'administration lui-même. D'autre part, l'attaquant ne peut trouver ni le message m, ni l'identifiant id, car il ne peut pas casser le cryptosystème NTRU.If the attacker is passive, that is to say if he can not interrogate the apparatus 3 but he can listen to the exchanges between the latter and the administration domain 2, he can only a replay attack. Indeed, the attacker, wanting to be authenticated as a legitimate device, must produce a valid message, the fourth number β₄ , or find the identifier id. The attacker can not produce a valid message by using the messages exchanged during the previous sessions, any modification of the first number ei being necessarily detected in the calculation of the fourth number ¾ by calculating the third number e,, implementing the function hash, and thanks to the pseudo-random value r_s ' * h generated by the administration domain itself. On the other hand, the attacker can not find the message m, nor the identifier id, because he can not break the cryptosystem NTRU.

Si l'attaquant est actif, c'est-à-dire s'il peut interroger l'appareil 3 pour retrouver son identité, il doit tout d'abord retrouver le message m ou la valeur initiale du produit r*h affectée à l'appareil. Pour ce faire, l'attaquant doit interroger l'appareil 3 entre deux sessions d' authentifîcation successives. Il doit trouver m® - m® pour un k spécifique et plusieurs i afin de retrouver m et r*h, où /;/'^'' correspond au message m de la z^'-ème tentative d' authentifîcation par l'attaquant. En effet, chaque m® étant un polynôme binaire, si l'attaquant retrouve certains m - m⁽ⁱ⁾ pour un k spécifique et plusieurs i, il retrouvera des coefficients de m et pourra procéder à une attaque par force brute pour retrouver le reste des coefficients. Il peut retrouver r * et^{+ !} et ainsi de suite, et finalement aboutir au produit r*h en utilisant le calcul du premier nombre ei précédemment décrit. Cela accompli, il peut retrouver l'identité de l'appareil en utilisant les messages échangés durant la session précédente ou lors de la prochaine session. L'invention rend une telle attaque irréalisable, l'attaquant ne pouvant pas trouver m® - m⁽ⁱ⁾ pour un k spécifique et plusieurs i. En effet, si l'attaquant commence l'attaque ci- dessus, l'appareil va répondre à la z^'-ème et à la (i+lj-ème requête par :If the attacker is active, that is to say if he can interrogate the apparatus 3 to find his identity, he must first find the message m or the initial value of the product r * h assigned to the 'apparatus. To do this, the attacker must interrogate the device 3 between two successive authentication sessions. He must find m®-m for a specific k and several i's in order to find m and r * h, where /; / '^''corresponds to the message m of the z^' -th attempt by the attacker to authenticate. Indeed, each m® being a binary polynomial, if the attacker finds some m - m⁽ⁱ⁾ for a specific k and several i, he will find coefficients of m and can proceed to a brute force attack to find the rest coefficients. He can find r * and^+! and so on, and finally to the product r * h using the calculation of the first number ei previously described. Once done, he can find the identity of the device using the messages exchanged during the previous session or during the next session. The invention renders such an attack impractical, since the attacker can not find m® -⁽ⁱ⁾ for a specific k and several i. Indeed, if the attacker starts the attack above, the device will respond to the z^' -th and the (i + lj-th request by:

e (₌ ( fc_{; + X}ki_^ *_r *_{h + m}(_mod(X^N - 1), et eⁱ⁺¹⁾ = (X^k^ + X^k * r * h + mod(X^N - 1),e (₌ (fc_{; + X} ki_ ^ *_r *_{h + m} (_mo d (X^N - 1), and e^{i + 1)} = (X^k ^ + X^k * r * h + mod (X^N - 1),

où X^N * r * h mod (X^N - 1) = r * h et (/ +^ /C / i) £ N³.where X^N * r * h mod (X^N - 1) = r * h and (/ + ^ / C / i) £ N³ .

D'où : From where :

eⁱ⁺¹⁾ - = (X^k^ - X^ki→ * r * h + - m mod(X^N - 1), où l'on suppose que (_k_i+1, ki_ ) £ 0, N— l]² grâce au calcul modulo - 1, mais dans un souci de simplification, l'on suppose que (k_i+1, /c^) E N² et que, dans ce cas, k_t =e^{i + 1)} - = (X^k ^ - X^ki → * r * h + - m mod (X^N - 1), where we assume that (_k_{i + 1} , ki_) £ 0, N-1 ]² thanks to the modulo - 1 calculation, but for the sake of simplification, we assume that (k_{i + 1} , / c ^) EN² and that, in this case, k_t =

4 ^ HW(r_t^Ci)), soit k_i+1 - / i = k ( Hw(r_t⁽ⁱ⁺¹⁾ ) + H (r_t⁽ⁱ⁾)), où k = 4 pour (N, p, q)4 ^ HW (r_t^Ci) ), let k_{i + 1} - / i = k (Hw (r_t^{(i + 1)} ) + H (r_t⁽ⁱ⁾ )), where k = 4 for (N, p, q)

= (251 , 2, 1 13).= (251, 2, 1 13).

Pour retrouver /;/'^{' +}

*r*h dans le calcul de

cela étant possible uniquement si /¾₊; et /¾_; sont égaux ou si chacun d'eux est un multiple de N. Cependant, cela est improbable parce que l'égalité entre kj₊i et kj-i signifie que l'appareil a généré deux valeurs nulles successives de la séquence r_h ce qui est très peu probable. D'autre part, si (N, p, q) = (251 , 2, 1 13), chaque terme /¾₊; et /¾_; ne peut être un multiple de N, k_i+1— ki_ = 4(HW(r^l+1^) + HW(r® ne pouvant pas être un multiple de 251 , car HW(r^l+1^) + HW(r^) est au maximum égal à 64. L'attaquant ne peut donc pas trouver /;/'^{' +} ^ - m® et /;/'^'' - /;/'^{' "} ^ pour lancer l'attaque décrite ci-dessus sur /;/' '.To find /; / '^{' +}

* r * h in the calculation of

this being possible only if / ¾₊ ; and / ¾_; are equal or if each of them is a multiple of N. However, this is unlikely because the equality between kj₊ i and kj-i means that the apparatus generated two successive null values of the sequence r_h which is very unlikely. On the other hand, if (N, p, q) = (251, 2, 1 13), each term / ¾₊ ; and / ¾_; can not be a multiple of N, k_{i + 1} - ki_ = 4 (HW (r^{l + 1} ^) + HW (r® can not be a multiple of 251, because HW (r^{l + 1} ^) + HW (r ^) is at most 64. The attacker can not find /; / '^{' +} ^ - m® and /; / '^''-/;/'^'" ^ to launch the attack described above on /; / ''.

Cependant, considérons que w produits r_s*h peuvent être générés à partir d'une valeur initiale de r*h, avec w = N + N - 1 + ... + N- (N- 1) = ½(N² + N) = 31626 pour N = 251. Par conséquent, si l'attaquant interroge l'appareil plus de ½(N² + N) fois, il y aura certainement deux termes e "¹-* et

utilisant la même valeur r_s*h, à partir du calcul du premier nombre ei. On en déduit que :However, consider that w products r_s * h can be generated from an initial value of r * h, with w = N + N - 1 + ... + N- (N-1) = ½ (N² + N) = 31626 for N = 251. Therefore, if the attacker interrogates the device more than ½ (N² + N) times, there will certainly be two terms e "¹ - * and

using the same value r_s * h, from the calculation of the first number ei. It follows that:

e^Ul) - e^Vl) = m(^ui) - {u_t, v_t) e [1, w]², où w = i (N² + N) .e^Ui) - e^Vl) = m (^ui ) - {u_t , v_t ) e [1, w]² , where w = i (N² + N).

L'attaquant ne peut pas déterminer avec exactitude e "¹-* et

S'il continue à interroger l'appareil avant la prochaine session d'authentifïcation mutuelle, il y aura e "²-¹ et e^{v /)} tels que e "²-¹ - e^{v /)} = n "²-¹ - m^(y2 Cependant, et grâce à la fonction de hachage H et la séquence r_t, il est très probable que les valeurs m^(vl), m^(u2) et /;/"^' '' soient deux à deux distinctes. L'attaquant est alors incapable de trouver dans un temps raisonnable m - m® pour un k spécifique et plusieurs i, ce qui ne lui permet pas de lancer l'attaque décrite ci-dessus et de retrouver le message m et le produit r*h.The attacker can not accurately determine e "¹ - * and

If he continues to interrogate the apparatus before the next mutual authentication session, there will be e "² -¹ and e^{v /)} such that e"² -¹ - e^{v /)} = n "² -¹ - m^(y2 However, thanks to the hash function H and the sequence r_t, it is very likely that the m values^(yl), m^(u2) and /; /.^'' '' are pairwise distinct L attacker is then unable to find in a reasonable time m - m® for a specific k and several i, which does not allow him to launch the attack described above and to find the message m and the product r * h.

L'attaquant ne peut pas utiliser l'attaque décrite ci-dessus pour attaquer le quatrième nombre β4 afin de retrouver id©m ou r '*h, ce produit changeant pour chaque calcul du quatrième nombre. Cependant, comme la prochaine session d'authentification est exécutée avec r '*h, une fois que la session k est achevée avec succès et avant que la prochaine session d'authentification mutuelle n'ait lieu, l'attaquant peut lancer l'attaque décrite ci-dessus sur l'appareil, plus précisément sur le premier nombre ei. S'il interroge l'appareil plus que w = ½(N² + N) fois, il y aura un e^l) tel que e^l) = (χ™(πιΜ) + i^ *_r^> * h +_m(_mod(X^N - l), soit e^l) - ef^} = m® - m ® id, (k, /) G N².The attacker can not use the attack described above to attack the fourth number β4 to find id © m or r * h, this product changing for each calculation of the fourth number. However, since the next authentication session is executed with r '* h, once the session k is successfully completed and before the next mutual authentication session takes place, the attacker can launch the attack described above on the device, more precisely on the first number ei. If it interrogates the device more than w = ½ (N² + N) times, there will be an e^l) such that e^l) = (χ ™ (πιΜ) + i ^ *_r^> * h +_m (_mo d (X^N - l), that is e^l) - ef^} = m® - m ® id, (k, /) GN² .

Néanmoins, même si l'attaquant a trouvé le bon ep , il est clair qu'il ne trouvera pas l'identifiant id de l'appareil, ne connaissant ni

ni m .Nevertheless, even if the attacker has found the correct ep, it is clear that he will not find the identifier id of the device, knowing neither

neither m.

D'autre part, l'identifiant id de l'appareil est crypté de façon à éviter l'attaque par multiples transmissions sur le cryptosystème NTRU. En effet, si un message m est transmis plusieurs fois un utilisant la même clé publique h et un polynôme r différent, un attaquant peut trouver une grande partie de ce message, comme expliqué dans l'article "NTRU: A ring- based public key cryptosystem", de J. Hoffstein, J. Pipher, and J. H. Silverman, Lecture Notes in Computer Science. Springer-Verlag, 1998, pp. 267-288. Pour éviter une telle attaque, le terme id@m, qui est différent dans chaque session, est chiffré au lieu de l'identifiant id de l'appareil. On the other hand, the identifier id of the device is encrypted so as to avoid attack by multiple transmissions on the cryptosystem NTRU. Indeed, if a message m is transmitted several times using the same public key h and a different polynomial r, an attacker can find a large part of this message, as explained in the article "NTRU: A ring- based public key cryptosystem ", J. Hoffstein, J. Pipher, and JH Silverman, Lecture Notes in Computer Science. Springer-Verlag, 1998, pp. 267-288. To avoid such an attack, the id @ m term, which is different in each session, is encrypted instead of the id of the device.

L'invention permet également d'assurer l'anonymat de l'appareil 3 et sa résistance à la traçabilité malveillante pour les systèmes RFID. En effet, si l'attaquant est passif, l'anonymat de l'appareil est garanti, sa réponse étant différente dans chaque session d'authentification grâce au message m et au produit r '*h utilisés lors du calcul du quatrième nombre β4. The invention also ensures the anonymity of the device 3 and its resistance to malicious traceability for RFID systems. Indeed, if the attacker is passive, the anonymity of the device is guaranteed, its response being different in each authentication session with the message m and the product r '* h used in computing the fourth number β4.

Si l'attaquant est actif, l'anonymat de l'appareil 3 est aussi garanti car la réponse de l'appareil par le biais du premier nombre ei est rendue aléatoire à chaque interrogation par l'attaquant. En effet, l'attaquant ne peut pas tracer l'appareil entre deux authentifications successives en essayant de distinguer la valeur du produit r*h utilisée par l'appareil, car le premier nombre ei est généré à partir de rotations de ce produit. L'attaquant ne peut pas retrouver d'informations sur les coefficients de r*h lui permettant de tracer l'appareil 3 entre deux authentifications successives. Si l'attaquant interroge l'appareil 3 un nombre de fois supérieur à ½(N² + N), il y aura forcément des premiers nombres

qui utiliseront la même valeur pour le produit r_s*h, le nombre de valeurs différentes de ce produit étant limité. On aurait alors :

-

= - /;/" '. Même si l'attaquant arrive à déterminer cela ne lui permet toutefois pas de tracer l'appareil car chaque séquence représentant le message m est pseudoaléatoire pour chaque session. L'anonymat de l'appareil est bien garanti.If the attacker is active, the anonymity of the device 3 is also guaranteed because the response of the device through the first number ei is made random at each interrogation by the attacker. Indeed, the attacker can not trace the device between two successive authentications by trying to distinguish the value of the product r * h used by the device, because the first number ei is generated from rotations of this product. The attacker can not find information on the coefficients of r * h allowing him to trace the apparatus 3 between two successive authentications. If the attacker interrogates the device 3 a number of times greater than ½ (N² + N), there will inevitably be first numbers

which will use the same value for the product r_s * h, the number of different values of this product being limited. We would then have:

-

= - /; / "'Even if the attacker manages to determine this does not allow him to trace the device because each sequence representing the message m is pseudo-random for each session.The anonymity of the device is well guaranteed .

En outre, une autre attaque potentielle consiste à désynchroniser l'appareil 3 et le domaine d'administration 2 en modifiant le deuxième nombre ¾ afin de délivrer à l'appareil une valeur invalide de r'*h. Une telle modification sera nécessairement détectée par l'appareil car l'attaquant ne peut pas produire le troisième nombre e?, ne connaissant pas le message m et le produit r'*h utilisés par la fonction de hachage pour calculer ce troisième nombre. La synchronisation entre l'appareil et le domaine d'administration est ainsi garantie. In addition, another potential attack consists in desynchronizing the apparatus 3 and the administration domain 2 by modifying the second number ¾ in order to deliver to the apparatus an invalid value of r '* h. Such a modification will necessarily be detected by the apparatus because the attacker can not produce the third number e ?, not knowing the message m and the product r '* h used by the hash function to calculate this third number. Synchronization between the device and the administration domain is guaranteed.

L'expression « comportant un » doit être comprise comme étant synonyme de « comportant au moins un ». The phrase "with one" should be understood as being synonymous with "having at least one".

Claims

REVENDICATIONS

1. Procédé pour crypter des données lors d'au moins une session entre un appareil (3) et un domaine d'administration (2) utilisant un cryptosystème NTRU (N, p, q) à clé publique (h) et à polynôme (r) de degré inférieur ou égal à (N - 1) choisi aléatoirement dans le domaine polynomial (D_r) du cryptosystème NTRU, dans lequel l'appareil (3) crypte les données en leur ajoutant un produit (r_s*h) déterminé à partir d'au moins une rotation du produit (r*h).A method for encrypting data during at least one session between a device (3) and an administration domain (2) using an NTRU (N, p, q) public key (h) and polynomial cryptosystem ( r) of degree less than or equal to (N - 1) randomly selected in the polynomial domain (D_r ) of the cryptosystem NTRU, wherein the apparatus (3) encrypts the data by adding to them a product (r_s * h) determined from at least one rotation of the product (r * h).

2. Procédé selon la revendication 1 , dans lequel l'appareil (3) crypte les données en leur ajoutant un produit (r_s*h) déterminé à partir d'au moins deux rotations du produit (r*/z).2. The method of claim 1, wherein the apparatus (3) encrypts the data by adding a product (r_s * h) determined from at least two rotations of the product (r * / z).

3. Procédé selon la revendication 2, dans lequel, lors du cryptage des données, l'une des rotations du produit (r*h) est la fonction identité. 3. The method of claim 2, wherein, during data encryption, one of the rotations of the product (r * h) is the identity function.

4. Procédé selon l'une quelconque des revendications précédentes, dans lequel ladite au moins une rotation du produit (r*h) est une rotation dudit produit vers la droite par k*E(log₂(2q-l)+l) fois le nombre de 1 d'une séquence (r_t) pseudo-aléatoire, k étant un entier, le produit (r_s*h) étant notamment égal à r*h + rot(r*h, k*E(log₂(2q-l) +l) 'The method according to any one of the preceding claims, wherein said at least one product rotation (r * h) is a rotation of said product to the right by k * E (log₂ (2q-1) + 1) times the number of 1 of a pseudo-random sequence (r_t ), where k is an integer, the product (r_s * h) being in particular equal to r * h + rot (r * h, k * E (log₂ ( 2q-1) + 1)

5. Procédé selon l'une quelconque des revendications précédentes, dans lequel la valeur p du cryptosystème NTRU est égale à 2.5. Method according to any one of the preceding claims, in which the p value of the cryptosystem NTRU is equal to 2.

6. Procédé selon l'une quelconque des revendications précédentes, dans lequel la valeur N du cryptosystème NTRU est égale à 251. The method of any one of the preceding claims, wherein the N value of the NTRU cryptosystem is 251.

7. Procédé selon l'une quelconque des revendications précédentes, dans lequel la valeur q du cryptosystème NTRU est égale à 1 13. 7. Method according to any one of the preceding claims, wherein the value q of the cryptosystem NTRU is equal to 1 13.

8. Procédé selon l'une quelconque des revendications 1 à 4, dans lequel les valeurs du cryptosystème NTRU sont (N, 2, q). The method of any one of claims 1 to 4, wherein the values of the NTRU cryptosystem are (N, 2, q).

9. Procédé selon la revendication précédente, ladite au moins une rotation du produit (r*h) est une rotation dudit produit vers la droite par k*E(log₂(2q-l) +l) fois le nombre de l d'une séquence (r_t) pseudo-aléatoire, k étant un entier, le produit (r_s*h) étant notamment égal à r*h + rot(r*h, k*E(log₂(2q-l) +l) ' r_t).9. Method according to the preceding claim, said at least one rotation of the product (r * h) is a rotation of said product to the right by k * E (log₂ (2q-1) + 1) times the number of 1 d a sequence (r_t ) pseudo-random, k being an integer, the product (r_s * h) being in particular equal to r * h + rot (r * h, k * E (log₂ (2q-1) + l ) r_t ).

10. Procédé selon l'une quelconque des revendications 1 à 3, dans lequel les valeurs de (N, p, q) du cryptosystème NTRU sont 251 , 2 et 1 13, la rotation du produit (r*h) étant une rotation dudit produit vers la droite par 32 fois le nombre de 1 d'une séquence (r_t) pseudo-aléatoire, le produit (r_s*h) étant notamment égal à r*h + rot(r*h, 32 'The method according to any one of claims 1 to 3, wherein the values of (N, p, q) of the NTRU cryptosystem are 251, 2 and 13, the rotation of the product (r * h) being a rotation of said product to the right by 32 times the number of 1 of a sequence (r_t ) pseudo-random, the product (r_s * h) being in particular equal to r * h + rot ( r * h, 32 '

1 1. Procédé d'échange de données entre au moins un appareil (3) et un domaine d'administration (2) utilisant un cryptosystème NTRU (N, p, q) à clé publique (h) et à polynôme (r) de degré inférieur ou égal k (N- 1) choisi aléatoirement dans le domaine polynomial (D_r) du cryptosystème NTRU, chaque appareil (3) et le domaine d'administration (2) comprenant chacun une mémoire, chaque appareil comprenant dans sa mémoire un identifiant unique (id) appartenant au domaine polynomial (D_m) du cryptosystème NTRU et étant initialisé avec une valeur d'initialisation (s) de N bits choisie aléatoirement et avec le produit (r*h),A method of exchanging data between at least one apparatus (3) and an administration domain (2) using an NTRU (N, p, q) public key (h) and polynomial (r) cryptosystem of degree less than or equal to k (N-1) chosen randomly in the polynomial domain (D_r ) of the NTRU cryptosystem, each apparatus (3) and the administration domain (2) each comprising a memory, each apparatus comprising in its memory a unique identifier (id) belonging to the polynomial domain (D_m ) of the NTRU cryptosystem and being initialized with an initialization value (s) of N bits randomly chosen and with the product (r * h),

procédé dans lequel :process in which

après une sollicitation du domaine d'administration (2), l'appareil (3) génère une séquence pseudo-aléatoire (r_t) et construit un message (ni) à partir de ladite séquence (r_t) et de ladite valeur (s) contenue dans la mémoire de l'appareil,after a solicitation of the administration domain (2), the apparatus (3) generates a pseudo-random sequence (r_t ) and constructs a message (ni) from said sequence (r_t ) and said value (s). ) contained in the memory of the device,

l'appareil (3) génère un premier nombre (eî) cryptant ledit message (ni) en utilisant le procédé pour crypter des données selon l'une quelconque des revendications précédentes, et transmet ledit premier nombre (eî) au domaine d'administration (2), the apparatus (3) generates a first number (ei) encrypting said message (ni) using the method for encrypting data according to any one of the preceding claims, and transmits said first number (ei) to the domain of administration ( 2)

l'appareil (3) remplace dans sa mémoire la valeur d'initialisation (s) par une valeur calculée à partir de la séquence pseudo-aléatoire (ri) et de l'ancienne valeur d'initialisation (s), et remplace dans sa mémoire la valeur du produit (r*h) par une rotation de ce produit, et the apparatus (3) replaces in its memory the initialization value (s) with a value calculated from the pseudo-random sequence (ri) and the old initialization value (s), and replaces in its memory the value of the product (r * h) by a rotation of this product, and

le domaine d'administration (2) décrypte ledit premier nombre (eî) afin de retrouver le message (ni). the administration domain (2) decrypts said first number (ei) in order to retrieve the message (ni).

12. Procédé selon la revendication précédente, dans lequel le message (ni) est construit en convertissant une séquence pseudo-aléatoire, calculée par une fonction de calcul appliquée à ladite séquence pseudo-aléatoire (r_t) et à ladite valeur (s) contenue dans la mémoire de l'appareil (3), en un polynôme binaire, la fonction de calcul mettant en œuvre une fonction de hachage H, notamment m = B2P(H(s@r_t)), où B2P représente une conversion binaire à polynomial.12. Method according to the preceding claim, wherein the message (ni) is constructed by converting a pseudo-random sequence, calculated by a calculation function applied to said pseudo-random sequence (r_t ) and to said value (s) contained in the memory of the apparatus (3), in a binary polynomial, the calculation function implementing a hash function H, in particular m = B2P (H (s @ r_t )), where B2P represents a binary conversion to polynomial.

13. Procédé selon l'une quelconque des revendications 8 à 1 1 , dans lequel l'appareil (3) remplace dans sa mémoire la valeur d'initialisation (s) par une valeur calculée par une fonction de calcul appliquée à la séquence pseudo-aléatoire (r_t) et à l'ancienne valeur d'initialisation (s), la fonction de calcul mettant en œuvre la fonction de hachage H, notamment la valeur d'initialisation (s) est remplacée par H(s@r_t).The method according to any one of claims 8 to 11, wherein the apparatus (3) replaces in its memory the initialization value (s) with a value calculated by a calculation function applied to the pseudo-random sequence (r_t ) and to the old initialization value (s), the calculation function implementing the hash function H, in particular the initialization value ( s) is replaced by H (s @ r_t ).

14. Procédé d'authentification d'au moins un appareil (3) par un domaine d'administration (2) lors d'au moins une session, le domaine d'administration utilisant un cryptosystème NTRU (N, p, q) à clé publique (h) et à polynôme (r) de degré inférieur ou égal à (N - 1) choisi aléatoirement dans le domaine polynomial (D_r) du cryptosystème NTRU, chaque appareil (3) et le domaine d'administration (2) comprenant chacun une mémoire, chaque appareil comprenant dans sa mémoire un identifiant unique (id) appartenant au domaine polynomial (D_m) du cryptosystème NTRU et étant initialisé avec une valeur d'initialisation (s) de N bits choisie aléatoirement et avec le produit (r*h), le domaine d'administration (2) ayant retrouvé par le procédé d'échange de données selon l'une quelconque des revendications 8 à 12 un message (ni) construit par l'appareil (3) à partir du décryptage d'un premier nombre (ei),14. A method for authenticating at least one device (3) with an administration domain (2) during at least one session, the administration domain using a cryptosystem NTRU (N, p, q) with key public (h) and polynomial (r) of degree less than or equal to (N - 1) randomly selected in the polynomial domain (D_r ) of the cryptosystem NTRU, each apparatus (3) and the administration domain (2) comprising each a memory, each apparatus comprising in its memory a unique identifier (id) belonging to the polynomial domain (D_m ) of the cryptosystem NTRU and being initialized with an initialization value (s) of N bits randomly chosen and with the product (r h), the administration domain (2) having retrieved by the data exchange method according to any one of claims 8 to 12 a message (ni) constructed by the apparatus (3) from the decryption of 'a first number (ei),

procédé dans lequel :process in which

le domaine d'administration (2) choisit aléatoirement un polynôme (r ') de degré inférieur ou égal à (N - 1) dans le domaine polynomial (D_r) du cryptosystème NTRU,the administration domain (2) randomly chooses a polynomial (r ') of degree less than or equal to (N - 1) in the polynomial domain (D_r ) of the NTRU cryptosystem,

le domaine d'administration (2) génère un deuxième nombre (ei) à partir des produits (r '*h) et (r*h) et de rotations de ces produits, et un troisième nombre (es) à partir du message (ni) et du produit (r '*h), et transmet à l'appareil (3) lesdits deuxième et troisième nombres (ei) et (es), the administration domain (2) generates a second number (ei) from the products (r '* h) and (r * h) and rotations of these products, and a third number (es) from the message ( ni) and the product (r '* h), and transmits to the apparatus (3) said second and third numbers (ei) and (es),

l'appareil (3) calcule le produit (r '*h) à partir d'une rotation utilisant le deuxième nombre (ei) et le produit (r_s*h) calculé lors du calcul du premier nombre (ei) par le procédé d'échanges de données selon l'une quelconque des revendications 8 à 12, et compare au troisième nombre (es) un nombre généré à partir du produit (r '*h) et du message (ni),the apparatus (3) calculates the product (r '* h) from a rotation using the second number (ei) and the product (r_s * h) calculated when calculating the first number (ei) by the method data exchange according to any one of claims 8 to 12, and compares to the third number (es) a number generated from the product (r '* h) and the message (n1),

en cas d'égalité à l'issue de cette comparaison, l'appareil (3) génère et transmet au domaine d'administration (2) un quatrième nombre (ei) à partir d'un produit (r_s '*h), calculé à partir d'au moins une rotation du produit (r '*h) et du message (ni), de l'identifiant (id) de l'appareil (3) et du message (ni), le domaine d'administration (2) décrypte ledit quatrième nombre (ej) afin de retrouver l'identifiant (id) de l'appareil (3) pour l'authentifier, etin case of equality after this comparison, the apparatus (3) generates and transmits to the domain of administration (2) a fourth number (ei) from a product (r_s ' * h), calculated from at least one rotation of the product (r '* h) and the message (ni), the identifier (id) of the apparatus (3) and the message (ni), the administration domain (2) decrypts said fourth number (ej) in order to find the identifier (id) of the device (3) to authenticate it, and

les valeurs d'initialisation (s) et le produit (r*h) sont réinitialisés dans la mémoire de l'appareil (3). the initialization values (s) and the product (r * h) are reset in the device memory (3).

15. Procédé selon la revendication précédente, dans lequel le deuxième nombre (¾) est généré par application d'une fonction de calcul mettant en œuvre une rotation vers la gauche des produits (r '*h) et (r*h), notamment ¾ = rot ' ' (r'*h, r*h + rot(r*h, k*E(log₂(2q-l)+l) ' r_t)) ® (r*h + rot(r*h, k*E(log₂(2q-l)+l) ' r_t)).15. Method according to the preceding claim, wherein the second number (¾) is generated by applying a calculation function implementing a left-turn of the products (r '* h) and (r * h), in particular ¾ = rot '' (r '* h, r * h + rot (r * h, k * E (log₂ (2q-l) + l)' r_t )) ® (r * h + rot (r * h, k * E (log₂ (2q-1) + 1) (r_t )).

16. Procédé selon la revendication 13 ou 14, dans lequel le troisième nombre (ei) est généré par une fonction de calcul appliquée au produit (r'*h) et au message (m), la fonction de calcul mettant en œuvre la fonction de hachage H, notamment = H((r'*h)®m). 16. The method of claim 13 or 14, wherein the third number (ei) is generated by a calculation function applied to the product (r '* h) and the message (m), the calculation function implementing the function. hash H, especially = H ((r '* h) ®m).

17. Procédé selon l'une quelconque des revendications 13 à 15, dans lequel le quatrième nombre (¾) est égal à r_s '*h + id®m, le produit (r_s '*h) étant notamment égal à r'*h + rot (r '*h, ki *E(log₂(2q-l)+l) ' m), kj étant un entier.17. A method according to any one of claims 13 to 15, wherein the fourth number (¾) is equal to r_s ' * h + id®m, the product (r_s ' * h) being in particular equal to r ' * h + rot (r '* h, ki * E (log₂ (2q-l) + l)' m), kj being an integer.