Procédé de cryptage de messages à destination d'au moins deux récepteurs, dispositif de cryptage et dispositif de décryptage associés.

Domaine technique Le domaine de l'invention est celui de la cryptographie.

Art antérieur

La cryptographie trouve application dans la sécurisation des échanges entre au moins deux entités. Parmi ces applications, on trouve des schémas de chiffrement de messages. Le chiffrement d'un message consiste à le transformer, par exemple en appliquant une fonction à ce message, de manière à le rendre inintelligible à toute entité autre que le destinataire légitime ou les destinataires légitimes du message. On peut représenter le chiffrement par une fonction E qui prend comme argument un message M, une clé de chiffrement k et qui retourne un message chiffré C :

C=E(M, k)

Inversement, le déchiffrement d'un message consiste à transformer un message chiffré de manière à obtenir le message d'origine. On peut représenter le déchiffrement par une fonction D qui prend comme argument un message chiffré C, une clé de déchiffrement k' et qui retourne le message d'origine M :

M=D(C, k')

Un schéma de chiffrement de message est dit symétrique si la clé servant à déchiffrer un message est la même que celle qui a servi à le chiffrer (k=k'). Cette clé doit rester secrète.

Dans un schéma de chiffrement asymétrique, la clé utilisée pour déchiffrer un message peut être différente de celle qui a servi à son chiffrement (k≠k'). Dans ce cas, seule la clé de déchiffrement k' doit être secrète.

Le chiffrement d'un même message à destination de plusieurs récepteurs, disposant chacun d'une clé de déchiffrement secrète kj' propre, l'indice i désignant le récepteur concerné, nécessite que l'émetteur procède à autant de chiffrements qu'il y a de récepteurs. Cette solution devient rapidement impraticable dans le cas où le nombre de récepteurs est important. Pour pallier ce problème de multiplication des chiffrements, une solution consiste à mettre à disposition de tous les récepteurs une même clé de déchiffrement secrète k\ Dans ce cas, l'émetteur peut se contenter de ne chiffrer son message qu'une seule fois, mais il n'est plus possible d'identifier un traitre, c'est-à dire un récepteur légitime qui a illicitement divulgué la clé de déchiffrement secrète commune k' .

Plus précisément, le domaine de l'invention est celui de la «traque des traitres» (traitor tracing, en Anglais). La traque des traitres trouve application dans la sécurisation des envois de messages d'un émetteur vers au moins deux récepteurs. Dans un schéma de traque des traitres, l'émetteur ne crypte qu'une seule fois le message à émettre à destination de récepteurs qui disposent chacun d'une donnée de décryptage différente pour décrypter le message reçu. Dans le schéma de traque des traitres, crypter est l'opération qui consiste à rendre inintelligible un message à toute entité autre que les récepteurs qui sont les destinataires légitimes du message. On appellera message crypté le résultat du cryptage d'un message. Dans le schéma de traque des traitres, décrypter est l'opération qui consiste à transformer un message crypté de façon à obtenir le message d'origine.

La principale différence entre chiffrer et déchiffrer d'une part et crypter et décrypter d'autre part est qu'un message chiffré ne peut être déchiffré qu'avec une seule clé de déchiffrement alors qu'un message crypté peut être décrypté avec des données de décryptage différentes.

Un traitre est un récepteur légitime qui a divulgué tout ou partie de sa donnée de décryptage de manière à permettre à une ou plusieurs entités non destinataires

légitimes des messages de pouvoir décrypter des messages à l'insu de l'émetteur. Un traitre peut agir seul et dans ce cas il divulgue tout ou partie de sa donnée de décryptage à une ou plusieurs entités. Des traitres peuvent aussi se coaliser afin de construire une donnée de décryptage illégitime (possiblement différente des données de décryptage de chacun des traitres de la coalition) qui permet de décrypter les messages de l'émetteur. Un procédé de traque des traitres est dit « m- résilient » si la connaissance d'une donnée de décryptage illégitime permet l'identification d'au moins un membre de la coalition de traitres qui a permis la construction de cette donnée de décryptage illégitime, à la condition que cette coalition ne comporte pas plus de m traitres. Un traitre agissant seul peut être vu comme un cas particulier de coalition ne comportant qu'un seul membre.

Dans le schéma de traque des traitres, l'émetteur dispose d'une donnée de cryptage Ke et chaque récepteur i dispose d'une donnée de décryptage Kdj différente pour chaque récepteur. Le schéma de traque des traitres comprend deux procédés distincts :

• un procédé de cryptage de messages ;

• un procédé d'identification des traitres à partir de la connaissance d'au moins une donnée de décryptage illégitime.

Nous décrivons, plus particulièrement, dans ce qui suit le procédé de cryptage de messages.

Un procédé de cryptage de messages comporte trois étapes : l'initialisation, le cryptage et le décryptage.

L'initialisation consiste à déterminer les paramètres du procédé et, en particulier, à déterminer la donnée de cryptage Ke de l'émetteur et pour chaque récepteur i, sa donnée de décryptage Kdi.

Le cryptage d'un message M consiste à construire un message ciypté <H, O où :

• C désigne le message chiffré résultat du chiffrement du message M avec une clé de chiffrement k : C=E(M, k) ;

• H désigne un en-tête qui est fonction de la donnée de cryptage Ke du diffuseur et de la clé de chiffrement k.

Une nouvelle clé de déchiffrement peut être avantageusement utilisée à chaque nouveau cryptage.

La forme du message crypté n'a pas d'importance. En particulier, l' en-tête peut être indifféremment placé devant ou derrière le message chiffré dans un message crypté.

Le décryptage d'un message consiste, pour le récepteur i, à obtenir le message M à partir d'un message crypté <H, C> en : • calculant une clé de déchiffrement secrète k' à partir de la donnée de décryptage Kdi du récepteur i et de l' en-tête H ;

• reconstruisant le message M en déchiffrant le message chiffré C à l'aide de la clé de déchiffrement k' : M=D(C, k').

Dans les schémas de traque des traitres proposés dans la littérature (cf. « Tracing Traitors », Benny Chor, Amos Fiat & Moni Naor, Lecture Notes in Computer Science, volume 839, pages 257-270, 1994), la donnée de cryptage Ke de l'émetteur est un ensemble de clés (utilisées aussi bien pour le chiffrement que pour le déchiffrement) et chaque donnée de décryptage Kdj est un sous-ensemble distinct de la donnée de cryptage Ke. Le cryptage d'un message M donne le message crypté <H, C> où :

• le message chiffré C est le résultat du chiffrement du message M avec une clé de chiffrement k composée de plusieurs parties ;

• l'entête H est constitué des résultats des chiffrements des parties de la clé de chiffrement k avec chacune des clés constituant la donnée de cryptage Ke de l'émetteur.

Dans un schéma « m-résilient », le nombre de clés constituant la donnée de cryptage de l'émetteur et le nombre de clés constituant la donnée de décryptage de chaque récepteur sont dépendants de m. Pour un nombre donné de récepteurs, plus on voudra résister à des coalitions importantes de pirates (plus m est grand) et plus le nombre de clés constituant la donnée de cryptage de l'émetteur et le nombre de clés constituant la donnée de décryptage de chaque récepteur sont grands.

Le principal défaut des schémas de traques des traîtres existants est qu'ils ne résistent qu'à des coalitions de traitres de taille limitée et dont ladite taille sera d'autant plus contrainte que la taille de la donnée de cryptage de l'émetteur, la taille de l'en-tête d'un message crypté ou la taille de la donnée de décryptage de chaque récepteur seront contraintes. La taille d'une coalition est le nombre de traitres qu'elle comporte. La taille de la donnée de cryptage de l'émetteur ou la taille d'une donnée de décryptage d'un récepteur est le nombre de clés qu'elle comporte. La taille de l'en-tête est, en général, égale à la taille de la donnée de cryptage de l'émetteur.

Un des objectifs de la présente invention est de définir un nouveau procédé de cryptage de messages à destination d'au moins deux récepteurs qui résiste à des coalitions de traitres arbitrairement grandes, c'est-à-dire que même si tous les récepteurs se coalisaient, ils ne seraient pas capables de générer une donnée de décryptage illégitime différente des données de décryptage des récepteurs de la coalition permettant de déchiffrer les messages de l'émetteur.

Résumé de l'invention

Selon un premier aspect, la présente invention propose un procédé de cryptage permettant à un émetteur, disposant d'une donnée de cryptage Ke, de crypter des

messages à destination d'au moins deux récepteurs, chaque récepteur î disposant d'une donnée de décryptage Kdj. Le procédé de cryptage comporte les étapes suivantes :

• une initialisation, qui consiste à déterminer la donnée de cryptage Ke de l'émetteur et à déterminer pour chaque récepteur i sa donnée de décryptage

Kd ₁ ;

• un cryptage d'un message M, qui consiste à construire un message crypté constitué d'un en-tête H et d'un message chiffré C résultat du chiffrement du message M avec une clé de chiffrement k ; • un décryptage d'un message crypté, qui consiste à déchiffrer le message chiffré C avec une clé de déchiffrement k' obtenue à partir de l' en-tête H et de la donnée de décryptage Kdj du récepteur i. Dans le procédé

• la donnée de cryptage Ke de l'émetteur est une information secrète inconnue des récepteurs ;

• la donnée de décryptage Kd; du récepteur i est constituée de secrets partiels choisis de sorte qu'il existe une fonction de composition de secrets partiels qui permet d'obtenir la donnée de cryptage Ke de l'émetteur à partir desdits secrets partiels et que cette fonction de composition de secrets partiels est inconnue des récepteurs ; et

• la clé de chiffrement k dépend de la donnée de cryptage Ke de l'émetteur et d'un aléa r.

Le fait que la fonction de composition de secrets partiels soit une fonction inconnue des récepteurs fait que la connaissance éventuelle de la donnée de décryptage d'un récepteur (voire de tous les récepteurs) ne permet pas de déduire la donnée de cryptage Ke de l'émetteur par l'utilisation de cette fonction.

Les caractéristiques décrites ci-dessus du procédé selon l'invention font que celui- ci résiste à des coalitions de pirates arbitrairement grandes. En effet, même si tous

les récepteurs se coalisaient, ils ne seraient pas capables de générer des secrets partiels valides, c'est-à-dire qui permettent de décrypter les messages ciyptés, et nouveaux, c'est-à-dire différents des secrets partiels constituants les données de décryptage des traitres de la coalition. En effet, déterminer de tels secrets partiels nécessite au moins la connaissance de la donnée de cryptage Ke de l'émetteur ou la connaissance de la fonction de composition de secrets partiels. Or la fonction de composition de secrets partiels et la donnée de cryptage Ke de l'émetteur sont inconnues des récepteurs.

Selon un deuxième aspect, l'invention propose un dispositif de cryptage pour crypter des messages selon le procédé décrit ci-dessus, et comprenant :

• des moyens de stockage de la donnée de cryptage Ke de l'émetteur ;

• des moyens de génération d'aléas ;

• des moyens de calcul agencés pour : calculer la clé de chiffrement k en fonction de la donnée de cryptage Ke de l'émetteur et d'un aléa r ; chiffrer un message avec la clé de chiffrement k ; calculer l' en-tête H en fonction du même aléa r ;

• des moyens de communication.

Selon un troisième aspect, l'invention propose un dispositif de décryptage pour décrypter des messages cryptés constitués d'un en-tête H et d'un message chiffré C selon le procédé décrit plus haut, et comprenant :

• des moyens de stockage des secrets partiels constituant la donnée de décryptage Kdi du récepteur i ; • des moyens de calcul agencés pour : calculer la clé de déchiffrement k' en fonction de la donnée de décryptage Kdj du récepteur i et de l' en-tête H ; déchiffrer le message chiffré C à l'aide de la clé de déchiffrement k' ;

• des moyens de communication.

Brève description des figures

L'invention ainsi que les avantages qu'elle procure seront mieux compris à la lumière de la description suivante faite en référence aux figures annexées dans lesquelles :

• FIG 1. représente un procédé de cryptage selon l'invention dans un exemple de mode de réalisation spécifique ;

• FIG 2. illustre un dispositif de cryptage selon un exemple de mode de réalisation de l'invention ;

• FIG 3. illustre un dispositif de décryptage selon un exemple de mode de réalisation de l'invention.

Exemple de modes de réalisation de l'invention

Faisant référence à la FIG 1, le procédé selon l'invention est décrit sur la base d'un exemple où un émetteur souhaite transmettre de façon confidentielle à un grand nombre de récepteurs une série de messages M, MM, etc.

Etape d'initialisation (101).

L'émetteur choisit une donnée de cryptage Ke secrète puis choisit pour chaque récepteur i les secrets partiels qui vont constituer sa donnée de décryptage Kdj. Ces secrets partiels sont choisis de sorte qu'il existe une fonction de composition de secrets partiels qui permet de calculer la donnée de cryptage Ke de l'émetteur en fonctions des secrets partiels de chaque récepteur.

Avantageusement, les données de décryptage sont uniques par récepteur, c'est-à- dire que deux récepteurs différents ont des données de décryptage différentes. La connaissance d'une donnée de décryptage permet ainsi l'identification univoque du récepteur à qui elle a été attribuée.

La donnée de décryptage Kdi du récepteur i comprend deux secrets partiels Aj et B ₁ .

Si de nouveaux récepteurs apparaissent, il suffit de choisir de nouveaux secrets partiels pour chacun de ces nouveaux récepteurs sans obligation de changer les données de décryptage des autres récepteurs.

La donnée de cryptage Ke de l'émetteur et les secrets partiels Aj et Bi sont des éléments d'un groupe fini G (cf. la définition d'un groupe au chapitre 2.5.1 de « Handbook of Applied Cryptography », Alfred J. Menezes, Paul C. van Oorschot & Scott A. Vanstone, CRC Press, ISBN: 0-8493-8523-7.).

Plus, particulièrement, le groupe fini G est l'ensemble des entiers non nuls modulo n, noté Z _n , où n est le produit de deux nombres premiers p et q inconnus des récepteurs.

La donnée de cryptage Ke de l'émetteur est égale à g ^(e*s ^ modulo n, le secret partiel A; est égal à g ^(e*(ai+1)) modulo n et le secret partiel Bj est égal à bj où :

• g est un élément de Z _n ^* inconnu des récepteurs ;

• s est un élément de Z _n inconnu des récepteurs ;

• aj et b _; sont des éléments de Z _n ^* et ai est inconnu des récepteurs tels que modulo λ et tels que le plus grand diviseur commun de deux bj quelconques est égal à c et où λ désigne le plus petit multiple commun de p-

1 et q-1 et c un élément de Z _n supérieur à 1 ;

• e est un élément de Z _n inconnu des récepteurs et choisi conjointement avec d, un autre élément de Z _n ^* inconnu aussi des récepteurs de sorte que e*d=l modulo λ.

On peut vérifier que (Ai/g ^e ) ^Bl modulo n est égal à g ^(e*s) modulo n. L'image des secrets partiels A ₁ et Bi par la fonction de composition de secrets partiels est donc (A/g ⁶ ) ⁶ ' modulo n. La fonction de composition de secrets partiels est inconnue des récepteurs car les éléments g et e du groupe Z _n ne sont pas connus des récepteurs. Un récepteur i, ne connaissant pas la fonction de composition de secrets partiels,

est donc dans l'in capacité d'utiliser cette fonction pour calculer la donnée de cryptage Ke de l'émetteur à partir des ses secrets partiels Aj et Bj.

Il est aussi important qu'une coalition de récepteurs ne puisse pas déduire la donnée de cryptage Ke de l'émetteur à partir des données de décryptage de récepteurs de cette coalition.

Or deux récepteurs, i et j, peuvent en mettant en commun leurs secrets partiels respectifs calculer d'une part la valeur g ^e*s*(bJ"bl) modulo n et d'autre part la valeur (b _j -b;) modulo n (on considère ici que b _j est plus grand que b _} ) que l'on notera δ. Pour calculer la valeur g ^{e s} modulo n, il faut calculer l'inverse de δ modulo λ puis élever g ^{e s} ^ ^bj"bl ^ à la puissance de cet inverse. Or les récepteurs ne sont pas capables de calculer un inverse modulo λ car λ, étant le produit de deux entiers p et q tous deux inconnus des récepteurs, est inconnu des récepteurs. Il est donc impossible à une coalition de deux récepteurs de déduire la donnée de cryptage Ke de l'émetteur.

Une coalition plus grande de récepteurs (au moins trois récepteurs) peut calculer selon le schéma décrit plus haut les valeurs suivantes g ^e*s*δl modulo n, δi, g ^{e s δ2} modulo n et δ ₂ où O ₁ et δ ₂ sont des différences de bj. La mise en œuvre de l'attaque du « modulus commun » (cf. la description de « Common Modulus Attack on RSA » dans le chapitre 19.3 de « Cryptanalysis of RSA-type cryptosystems: a visit », Marc Joye & Jean- Jacques Quisquater, R. Whright and P. Neumann, Eds., Network Threats, DIMACS Séries in Discrète Mathematics and Theoretical Computer Science, vol. 38, pp. 21-31, American Mathematical Society, 1998) pourraient permettre de déduire la valeur g ^(e*s) modulo n si le plus grand diviseur commun de δi etδ ₂ était égal à 1. Or le plus grand diviseur commun de δi et δ ₂ est égal à c, le plus grand diviseur commun de tous les bj et est, de ce fait, supérieur à 1. Il est donc impossible à une coalition de plus de deux récepteurs de déduire la donnée de cryptage Ke de l'émetteur.

A la fin de cette étape d'initialisation l'émetteur possède sa donnée de cryptage Ke et chaque récepteur possède sa donnée de décryptage, la donnée de décryptage Kd ₁ du récepteur i étant constituée des secrets partiels Ai et Bj.

Etape de cryptage (102).

Le cryptage du premier message M consiste à construire le message crypté <H, O où H est P en-tête du message crypté et C un message chiffré résultat du chiffrement du message M avec une clé de chiffrement k.

La clé de chiffrement k est fonction de la donnée de cryptage Ke de l'émetteur et d'un aléa r. Nous entendons par aléa une information choisie arbitrairement, de façon déterministe ou indéterministe, et dont la valeur n'est pas prédictible par les récepteurs.

L'aléa r est un élément du groupe fini G et est, de ce fait, un élément du groupe

Z _n ^* .

La clé de chiffrement k est obtenue en élevant la donnée de cryptage Ke de l'émetteur à la puissance du produit de l'aléa r avec d. La clé de chiffrement k est donc égale à (Ke) ^(d*r) modulo n, qui est égal à g ^(s*r) modulo n.

L'en-tête H du message crypté est constitué d'une première partie Hi, qui est égale à d*r modulo λ, et d'une deuxième partie H ₂ , qui est égale à g ^r modulo n.

En définitive, le cryptage du message M donne le message crypté <(Hi, H ₂ ), O où étant donné l'aléa r :

• la première partie de l'en-tête Hi est égale à d*r modulo λ ;

• la deuxième partie de l'en-tête H ₂ est égale à g ^r modulo n ;

• le message chiffré C est le résultat du chiffrement du message M avec la clé de chiffrement k, qui est égale à g ^(s*r) modulo n.

Un autre avantage du procédé de cryptage selon l'invention est qu'il ne nécessite pas une deuxième phase d'initialisation pour le cryptage des messages suivants. Pour crypter le message MM, par exemple, il suffît, de tirer un nouvel aléa rr puis de calculer le message <(HHi , HH ₂ ), CO où :

• la première partie de l' en-tête HHi est égale à d*rr modulo λ ;

• la deuxième partie de l' en-tête HH ₂ est égale à g ^rr modulo n ; • le message chiffré CC est le résultat du chiffrement du message MM avec la clé de chiffrement kk, qui est égale à g ^(s*rr) modulo n.

Etape de décryptage (103).

Le décryptage du message crypté <H, C> par le récepteur i consiste à déchiffrer le message chiffré C avec une clé de déchiffrement k' obtenue à partir de l' en-tête H et de la donnée de décryptage Kdi du récepteur i.

Comme décrit dans l'étape de cryptage, l' en-tête H est constitué de deux parties Hi et H ₂ et le message crypté peut être représenté sous la forme : <(Hi, H ₂ ), C>.

La clé de déchiffrement k' est égale à (Ai ^H 7H ₂ ) ^Bl modulo n où Aj et Bj sont les deux secrets partiels constituants la donnée de décryptage Kdj du récepteur i. En remplaçant chaque élément de l'expression (Aj ^Hl /H ₂ ) ^Bl modulo n par sa valeur, il est facile de vérifier que la valeur de la clé de déchiffrement k' est g ^(s*r) modulo n. On peut constater que la clé de chiffrement k et la clé de déchiffrement k' sont égales.

Une fois la clé de déchiffrement k' connue, il suffit de déchiffrer le message chiffré C à l'aide de la clé de déchiffrement k' pour obtenir le message d'origine M.

Le décryptage du message crypté correspondant au cryptage du message MM ainsi que tous les décryptages suivants ne nécessitent pas une nouvelle étape d'initialisation.

Un autre avantage du procédé selon l'invention est que la taille de la donnée de cryptage de l'émetteur, la taille de l' en-tête et la taille des données de décryptage sont fixes, c'est à dire qu'elles ne dépendent pas du nombre de récepteurs. De plus, cette taille est relativement raisonnable. En effet, la donnée de cryptage Ke de l'émetteur est constituée d'un seul élément du groupe Z _n ^* , la donnée de décryptage Kdj d'un récepteur i est constituée de deux éléments du groupe Z _n et l' en-tête H d'un message crypté est aussi constitué de deux éléments, Hi et H ₂ , du groupe Z _n .

Dispositif de cryptage (200).

L'invention concerne aussi un dispositif de cryptage (200) illustré dans la FIG 2, pour crypter des messages selon le procédé décrit plus haut, le dispositif comprenant :

• des moyens de stockage (201) de la donnée de cryptage Ke de l'émetteur ;

• des moyens de génération d'aléas (204) ;

• des moyens de calcul agencés (202) pour : o calculer la clé de chiffrement k en fonction de la donnée de cryptage

Ke de l'émetteur et d'un aléa r ; o chiffrer un message avec la clé de chiffrement k ; o calculer l' en-tête H en fonction du même aléa r ;

• des moyens de communication (203).

Ce dispositif de cryptage (200) peut être, par exemple, un ordinateur, une carte à puce ou tout autre appareil cryptographique.

Dispositif de décryptage (300).

L'invention concerne enfin un dispositif de décryptage (300) illustré dans la FIG 3, pour décrypter des messages cryptés constitués d'un en-tête H et d'un message chiffré C selon le procédé décrit plus haut, le dispositif comprenant :

• des moyens de stockage (301) des secrets partiels qui constituent la donnée de décryptage Kd ₁ du récepteur i ;

• des moyens de calcul agencés (302) pour : o calculer la clé de déchiffrement k' en fonction de la donnée de décryptage Kd ₁ du récepteur i et de l' en-tête H ; o déchiffrer le message chiffré C à l'aide de la clé de déchiffrement k' ; • des moyens de communication (303).

Ce dispositif de décryptage (300) peut être, par exemple, l'un des éléments suivants :

• un ordinateur ; • une carte à puce ou tout autre appareil cryptographique ;

• un décodeur de télévision numérique, un téléphone mobile, un assistant personnel numérique, et plus généralement tout appareil permettant de recevoir ou de visualiser des données multimédia numériques.

Le dispositif de décryptage peut aussi être une combinaison des éléments cités ci- dessus. Le dispositif de décryptage peut être, par exemple, constitué par un décodeur de télévision numérique et une carte à puce. Le décodeur de télévision numérique stockant, par exemple, le secret partiel Aj et la carte à puce stockant le secret partiel B ₁ .

Application industrielle possible.

Une application industrielle possible, mais non exclusive, de la présente invention est l'accès conditionnel dans un système de télévision à péage. Un système d'accès conditionnel dans la télévision à péage assure que les contenus audiovisuels ne sont accessibles qu'aux seuls abonnés qui en ont acquis les droits. Les systèmes

d'accès conditionnel actuels n'utilisent pas des schémas de traque des pirates car l'encombrement induit par ces derniers est incompatible avec les contraintes de diffusion de contenus audiovisuels. L'utilisation de secrets communs à tous les abonnés rend difficile l'identification de la source d'une contrefaçon dans le cas d'un piratage. Le faible encombrement (les faibles tailles des données de cryptage, de décryptage et des en-têtes) engendré par le procédé selon la présente invention rend parfaitement possible son utilisation dans un système d'accès conditionnel pour la télévision à péage rendant ainsi l'identification des pirates plus aisée.

Les modes de réalisation présentés ne constituent que des exemples de réalisation de l'invention non limitatifs de la portée de l'invention. D'autres modes de réalisation sont possibles dans des variations qui sont à la portée d'un homme du métier à la lecture de la présente description. La portée de l'invention est déterminée par les revendications annexées à la présente description.