C. R. Acad. Sci. Paris, t. , Série I
Théorie des Nombres/Number Theory

Utilisation des modules de Drinfeld en cryptologie
Roland GILLARD, Franck LEPREVOST, Alexei PANCHISHKIN, Xavier-François
ROBLOT
Institut Fourier, Université de Grenoble I
UMR 5582 CNRS-UJF 38402 Saint-Martin-d’Hères (France)
E-mail : gillard@ujf-grenoble.fr, Franck.Leprevost@ujf-grenoble.fr,
panchish@ujf-grenoble.fr

Institut Girard Desargues, Université Claude Bernard (Lyon I)
UMR 5028 CNRS-UCB 69622 Villeurbanne (France)
E-mail : roblot@euler.univ-lyon1.fr

Résumé .

Nous présentons dans cette note un nouveau et efficace cryptosystème à clefpublique basé sur les modules de Drinfeld. Les détails apparaitront ailleurs.

Using Drinfeld modules in cryptology
Abstract .

We present in this note a new and efficient public-key cryptosystem based on
Drinfeld modules. The details will appear elsewhere.

Introduction . — La sécurité des cryptosystèmes à clef publique est basée sur des problèmesmathématiques difficiles à résoudre en pratique. Citons par exemple les cryptosystèmes RSA et deRabin, dont la sécurité est fondée sur le problème de la factorisation des entiers, celui de El Gamal
ou le protocole d’échange de clefs de Diffie-Hellman basés sur le problème du logarithme discretdans le groupe multiplicatif d’un corps fini, ou dans le groupe des points rationnels d’une courbe
elliptique définie sur un corps fini. Ces protocoles ont été longuement étudiés et sont standardisés(par exemple, voir [6] et les références incluses). Néanmoins, il est utile de disposer d’autres cryptosystèmes, dont la sécurité est basée sur d’autres problèmes, et qui, le cas échéant, peuvent être
inclus dans de nouveaux standards. Dans [5], Scanlon montre que des analogues naturels dans lecadre des modules de Drinfeld (voir [1] et [2], ainsi que [4] pour ces objets) des cryptosystèmesévoqués plus haut sont particulièrement faibles. Nous esquissons ici une approche différente, qui
contourne les faiblesses soulevées par Scanlon, en construisant une fonction sens unique à trappe(FSUT). Les détails apparaitront dans un autre article (voir [3]), et une demande de brevet a étédéposée sur ce nouveau cryptosystème.

2

R.GILLARD, F.LEPREVOST, A. PANCHISHKIN, X.-F. ROBLOT

Fonctions sens unique à trappe et applications à la cryptographie . — Une fonction
ψ bijective d’un ensemble E dans un ensemble F est dite une fonction sens unique (FSU) si la seuledonnée de ψ et de y ∈ F ne permet pas de résoudre en pratique le problème d’inversion consistant àtrouver l’unique x ∈ E tel que y = ψ(x). La fonction ψ est dite fonction sens unique à trappe (FSUT)
si c’est une FSU telle que la connaissance d’une clé secrète K permette de résoudre le problèmed’inversion. Une application cryptographique est la suivante, sous une forme très simplifiée, où
Alice et Bob sont deux protagonistes cherchant à échanger une information confidentielle sur uncanal ouvert. Alice publie la FSUT ψ de E (messages en clair) dans F (messages cryptés), et garde
secrète la clé K. Pour transmettre un message x ∈ E, Bob calcule et envoie y = ψ(x) à Alice.
Pour décoder le message y, il faut calculer x = ψ −1 (y). Seule Alice, qui possède K, est à même derésoudre efficacement ce problème.
Présentation théorique du protocole. — Soit p un nombre premier. On note A = Fp [T ]l’anneau des polynômes à une variable et à coefficients dans le corps Fp . Puis, on pose A{τ }l’anneau des polynômes à coefficients dans A et en la variable τ avec les règles de l’addition usuelle
ket pour la multiplication, la règle de commutation τ k × a = ap × τ k pour a ∈ A et k ≥ 1.
Nous définissons un module de Drinfeld comme un morphisme de Fp -algèbre ϕ de A dansA{τ }Ptel que ϕ(T ) est un polynôme (en τ ) de degré ≥ 1Pet dont le terme
Pmconstant iest T . Soitmmiia =aT
unélémentdeA,
onadoncϕ(a)=ϕaT=i=0 ii=0 i
i=0 ai ϕ(T ) . Ainsi, lemodule de Drinfeld ϕ est complètement défini une fois que ϕ(T ) a été choisi. L’exemple le plus
simple de module de Drinfeld est le module de Carlitz défini par ϕ(T ) = τ + T . Chaque élémentde A{τ } défini une application de A dans lui-même en identifiant chaque élément a ∈ A avec
l’application z 7→ az et τ avec l’application de Frobenius z 7→ z p . La multiplication dans A{τ }PmPmicorrespond alors à la composition des fonctions. Ainsi, on obtient : i=0 ai τ i : z 7→ i=0 ai z p .
Pour a ∈ A, on note ϕa l’application de A dans lui-même définie par ϕ(a) ∈ A{τ }. L’application
ϕ1 est l’identité sur A.
Soient d > 1 un entier et f (T ) ∈ A un polynôme irréductible de degré d. On pose B = A/(f (T )).
Ainsi B est isomorphe à Fpd . Pour a ∈ A, on note a la classe de a dans B. L’anneau fini B a doncune structure naturelle de A-module. Soit a ∈ A, on note ϕa l’application de B dans B définipar : ϕa : b 7→ ϕa (b). Ainsi, le module de Drinfeld ϕ permet de munir B d’une autre structure deA-module donnée par : a ×ϕ b = ϕa (b).
On note Bϕ l’ensemble B muni de la structure de A-module défini par ϕ. Puisque Bϕ est un
A-module de cardinal pd , il existe un polynôme unitaire fϕ ∈ A de degré d tel que Bϕ ' A/(fϕ )comme A-module. En général, fϕ n’est pas irréductible. Une remarque fondamentale pour notre
propos est que deux éléments a1 et a2 de A donnent la même application ϕa1 = ϕa2 si et seulementsi a1 ≡ a2 (mod fϕ ). Ainsi, l’application ϕa est bijective si et seulement a est premier avec fϕ et,dans ce cas, l’application inverse est ϕa0 où a0 ∈ A est tel que aa0 ≡ 1 (mod fϕ ).
Nous pouvons à présent expliquer comment construire une FSUT de B dans lui-même en utilisantles modules de Drinfeld. Les aspects algorithmiques de cette construction seront succintementdétaillés dans la section suivante. On prend E = F = B. La clé secrète K est composée de deuxéléments c1 et c2 de A, tous les deux premiers avec fϕ , et d’une bijection σ de B dans lui-même(voir la section suivante pour des exemples de choix de σ). La fonction ψ est alors définie par :ψ(z) = (ϕc1 ◦ σ ◦ ϕc2 ) (z)donnée comme un polynôme de B[z]. Cette fonction est bijective et sa réciproque est la fonctionψ −1 (z) = ϕc02 ◦ σ −1 ◦ ϕc01 (z)Utilisation des modules de Drinfeld en cryptologie

3avec c01 et c02 deux éléments de A tels que c1 c01 ≡ 1 (mod fϕ ), et c2 c02 ≡ 1 (mod fϕ ). Cette
fonction inverse ne peut être déterminée en pratique que si la clé secrète (c1 , c2 , σ) est connue.
Présentation pratique du protocole. — Supposons choisis les différents paramètres p, ϕ, det f (les choix de ceux-ci seront discutés dans la section suivante), nous montrons comment trouver
c1 , c2 et σ, puis calculer les fonctions ψ et ψ −1 et s’en servir pour le chiffrement et le déchiffrement.
Pour calculer dans B, nous représentons
chaque classePm
Pd−1par l’unique polynôme de degré < dcontenu dans la classe. Soit a = i=0 ai T i ∈ A et β = j=0 bj T j ∈ B. Alors :ϕa (β) =mX

ai ϕT i (β) =i=0d−1m X
Xai bj ϕT i (T j ).

i=0 j=0Donc il suffit de savoir calculer ϕT i (T j ) pour en déduire ϕa (β) par cette formule. De surcroı̂t,puisque ϕa = ϕa0 si a ≡ a0 (mod fϕ ), si on prend pour a0 le reste de la division euclidienne de apar fϕ , on voit qu’il est suffisant de considérer uniquement les exposants i tels que 0 ≤ i ≤ d − 1.
PdkOn écrit ϕ(T ) =k=0 φk τ , avec φk ∈ A et, par définition, φ0 = T . Alors, on a, pour toutPdjjj ≥ 0 : ϕ1 (T ) = T et ϕT (T j ) = k=0 φk × T jpk , puis la formule de récurrence ϕT i+1 (T j ) =ϕT ϕT i (T j ) (i ≥ 1) pour le calcul des autres valeurs.

Le calcul de fϕ s’obtient comme suit. En tant que Fp -espace vectoriel, B est de dimension dd−1

admettant la famille {1, T , . . . , T} pour base. L’application ϕT est en fait un endomorphismede cette espace vectoriel dont on calcule facilement la matrice, puis le polynôme caractéristiqueC(T ). Le calcul montre que fϕ = C(T ).
Il convient à présent de choisir la clé secrète, i-e. les deux éléments c1 et c2 de A, de degré < det premiers avec fϕ , et la bijection σ. Pour c1 et c2 , la meilleure méthode est de choisir au hasard
un couple de deux polynômes distincts premiers avec fϕ . Des exprimentations montrent aussi qu’il
vaut mieux choisir c1 et c2 sans coefficients nuls. On calcule aussi les deux polynômes c01 et c02 dedegré < d et tels que c1 c01 ≡ 1 (mod fϕ ) et c2 c02 ≡ 1 (mod fϕ ) ; ces deux polynômes serviront
pour le décryptage. Pour la bijection σ, il faut une fonction simple et rapide à calculer, donnéesous la forme d’un polynôme. Soit e < pd − 1 un entier non divisible par p et premier avec pd − 1,on prend σ : z 7→ z e + δ, où δ est un élément pris au hasard dans B. Si on note f un entier tel queef ≡ 1 (mod pd − 1), alors on a σ −1 : z 7→ (z − δ)f .
A présent, on calcule la FSUT ψ(z) = (ϕc1 ◦ σ ◦ ϕc2 ) (z) sous la forme d’un polynôme. Pour cela,Pd−1
Pd−1
on écrit à nouveau : a = i=0 ai T i , avec ai ∈ A, et donc ϕa (z) = i=0 ai ϕT i (z), et les ϕT i (z)sont reliés par P
la relation de récurrence déjà mentionnée ci-dessus. Pour utiliser cette formule, ondkécrit ϕ(T)=k=0 φk τ , avec φi ∈ A, et, par définition, φ0 = T . Alors, pour tout polynômePmiP (z) = i=0 πi z ∈ B[z], on aϕT (P (z)) =d XmXkk

φk πip z ip .

k=0 i=0Grâce à cette formule, on obtient une expression pour ψ(z) donné comme un polynôme en z et à
coefficients dans B. Il est à noter que dans ce calcul, on doit remplacer les termes de la forme γz mavec m ≥ pd par γz r , où r est le reste de la division euclidienne de m par pd − 1, puisque β m = β rpour tout β ∈ B. On s’assure ainsi que tous les termes de ψ(z) restent de degré < pd .

4R.GILLARD, F.LEPREVOST, A. PANCHISHKIN, X.-F. ROBLOT

Le cardinal de B est pd , donc la FSUT ψ permet de coder des messages donnés sous la formed’un nombre M vérifiant 0 ≤ M < pd . En effet, étant donné un tel nombre M , on le transforme enun élément de B en utilisant l’écriture de M en base p : il existe des entiers uniques m0 , . . . , md−1vérifiant 0 ≤ mi < p et tels que M = m0 + m1 p + m2 p2 + · · · + md−1 pd−1 , ce qui permet d’associerde manière unique à l’entier M , l’élémentµ = m0 + m1 T + · · · + md−1 T d−1
de B. On calcule alorsχ = ψ(µ) = k0 + k1 T + · · · + kd−1 T d−1
et le message codé C est alors donné, comme nombre entre 0 et pd , par le procédé inverse :C = k0 + k1 p + · · · + kd−1 pd−1 . Inversement, pour décrypter le message C, on construit l’élément χde B correspondant, on applique ψ −1 pour en déduire µ et finalement M . Il est à noter cependant−1que, plutôt que calculer ψ −1 (z) sous forme d’un polynôme pour effectuer le calcul de ψ (µ), il−1−100est plus efficace de faire ce calcul en utilisant l’expression : ψ (µ) = ϕc2 σ
ϕc1 (µ) .
Choix des paramètres. — Plusieurs attaques du cryptosystème sont envisageables (calcul decycle, factorisation, énumération, etc). La considération de ces attaques montre que l’on doit prendre p très grand par rapport à d. Cependant, par souci d’efficacité algorithmique et d’architectured’ordinateur, il est souhaitable que p < 232 . Par ailleurs, la taille du polynôme ψ(z) augmente
avec l’exposant e, donc e doit être petit. D’un autre côté, e doit être premier avec pd − 1, donc
e est impair. Des choix raisonnables sont e = 5 ou e = 7. Finalement, afin de pouvoir utiliser ce
protocole pour crypter des clés AES, il faut que pd > 2160 ' 1018 . En résumé, des restrictions
souhaitables sur les paramètres sont les suivantes : p est un grand nombre premier plus petit que
232 ; d est un entier tel que pd ≥ 2160 ; f est un polynôme de Fp [T ] irréductible de degré d ; e est
petit et premier avec pd − 1 ; ϕ est le module de Carlitz ; c1 et c2 sont deux polynômes de Fp [T ]de degré d − 1, premiers avec fϕ , et sans coefficients nuls ; δ est un élément non nul de B. Nousavons implémenté des exemples, et il en découle que le stockage des données de cryptage nécessite
environ 26000 caractères. Sur un Pentium 700MHz, tournant sous Linux 2.4, une implémentationde ce protocole en C++ avec la librairie NTL [7] donne un temps de codage de l’ordre de un centièmede seconde. Le temps de décodage est négligeable.
Références bibliographiques[1]

V.G.Drinfeld, 1976. Elliptic modules, Math.USSR-Sbornik 23, 561-592[2]

V.G.Drinfeld, 1977. Elliptic modules, Math.USSR-Sbornik 31, 159-170[3]

R. Gillard, F. Leprévost, A. Panchishkin, X.-F. Roblot, 2002. A new public-key cryptosystem basedon Drinfeld modules, (En préparation)[4]

A.A.Panchishkin, 1993-94. Algorithmes rapides pour factorisation des nombres et des polynômes, tests deprimalité, courbes elliptiques et modules de Drinfeld, Séminaire de Théorie des nombres (Caen), 1-10

[5]

T. Scanlon, 2001. Public key cryptosystems based on Drinfeld modules are insecure, Journal of Cryptology
14, 225-230[6]IEEE Standards, 1999. Group P1363: Standard Specification for Public-Key Cryptography, page internet :http://grouper.ieee.org/groups/1363[7]

V. Shoup, 2002. NTL: A Library for doing Number Theory, page internet : http://shoup.net/ntl/