Ce document a été proposé comme sujet de projet informatique pour les élèves du tronc commun de l'Ecole Polytechnique en 1998-99. Sa difficulté est "moyenne" (**).

Penser à consulter l'erratum à la fin de ce document.

Procédé de Signature Numérique

Auteur: Serge Vaudenay
Ecole Normale Supérieure - CNRS

Préambule

Un algorithme de signature numérique permet d'assurer l'analogue de l'opération de signature manuscrite d'un document sur papier: il est difficile d'"imiter" une signature, si bien qu'un document numérique accompagné d'une signature est authentifié. Ce concept de signature numérique permet de mettre en oeuvre des outils de sécurité pour l'un des principaux moteurs économiques de l'informatique actuelle: le commerce électronique.

Le projet de norme ISO 14888 propose plusieurs procédés, dont le "procédé de Pointcheval-Vaudenay". On se propose d'implémenter celui-ci en Java.

Dans ce projet, on cherche à implémenter le procédé de signature de Pointcheval-Vaudenay avec l'algorithme de hachage SHA-1 proposé par la chambre de commerce du gouvernement américain.

Principe de la Signature Numérique

Pour mettre en place le système proposé, on suppose définis les paramètres suivants.

Un nombre premier $p$ .
Un nombre premier $q$ qui est facteur de $p-1$ .
Un entier $g$ compris entre 2 et $p-1$ et d'ordre $q$ modulo $p$ (on a $g$ ^q=1 (mod p)).

Pour fixer les idées, on suppose

2

⁵¹¹<p<2⁵¹² et

2

¹⁵⁹<q<2¹⁶⁰.

En outre, on suppose que chaque utilisateur détient un couple d'entiers $(x,y)$ liés par la relation

y=g

On impose

0<x<q

. Chaque utilisateur détient sa clef

x

secrète. On suppose que les clefs

y

sont publiées dans un "annuaire électronique". On note, qu'étant donné

y

, il est très difficile de retrouver

x

. (En fait, aucun algorithme connu ne permet de faire ce calcul en un temps raisonnable pour ces tailles de paramètres.)

Un message numérique se présente sous la forme d'une chaîne de bits $m=m$ ₁ ... m_n.

Le procédé de signature permet, à partir des paramètres $(p,q,g)$ , de $x$ et de $m$ , de calculer un couple $sigma=(r,s)$ que l'on appelle "signature de $m$ ". Dans ce couple, on a $0<=r<q$ et $0<=s<q$ . La longueur de la signature ne dépend donc pas de la taille $n$ du message. On note que $sigma$ n'est pas déterminée par $m$ : il peut y avoir plusieurs signatures possibles pour un même message.

Un autre procédé de vérification permet, à partir des paramètres $(p,q,g)$ , de $y$ , de $m$ et de $sigma$ de vérifier que la signature est correcte.

Dans la section suivante, on définit une "fonction de hachage" $h$ qui permet de calculer un entier $h(c)$ à partir d'une chaîne de bits $c$ quelconque. Le procédé de signature fonctionne ainsi.

On tire un nombre $k$ aléatoire tel que $0<k<q$ .
On calcule $r=(g$ ^k mod p) mod q.
On calcule

Dans ce calcul, la notation

r||m

représente la concaténation des chaînes de caractères qui représentent l'entier

r

et le message

m

Pour vérifier une signature $(r,s)$ de $m$ avec la clef $y$ , on procède ainsi.

On vérifie $0<r<q$ et $0<s<q$ .
On vérifie

Le calcul de $r||m$ nécessite une convention pour représentater $r$ sous la forme d'une chaîne de caractères. Dans le cas où $q$ est de 160 bits, on représentera $r$ sous la forme d'une chaîne de caractères ASCII (en lettres minuscules) sur 40 caractères. Par exemple, si $r=11134$ , on utilise la chaîne

00000000 00000000 00000000 00000000 00002b7e

Si l'on a

r=1268909481109348069110682404183134451126664881173

on utilise

de43de78 df484d91 52b5053b 3d70c28c 337ee415

De même, la signature $(r,s)$ devra être représentée suivant la même convention standard, soit sur 80 caractères hexadécimaux $r||s$ .

Fonction de Hachage

On suppose que l'on dispose d'une chaîne de caractère

m

qui représente un message. Une fonction de hachage cryptographique est une fonction qui, pour tout message

m

de longueur arbitraire, calcule une "empreinte numérique"

h(m)

qui est une chaîne de longueur fixée (ici, 160 bits, soit 40 chiffres hexadécimaux). Dans le cas de la signature numérique, cette chaîne est ensuite traitée comme un entier de 160 bits.

Afin d'effectuer le hachage, on effectue un premier codage de $m$ en une chaîne $m'$ . On note $l(m)$ la longueur (en bits) de $m$ . Si l'on représente $l(m)$ sous la forme d'une chaîne de 64 bits, soit 16 chiffres hexadécimaux (par exemple, si $m$ contient 419 bits, on note $l(m)=$ "00000000000001a3". On complète $m$ par un bit "1", suivi d'un nombre variable de bits "0" puis de $l(m)$ . Le nombre de bits nuls doit être minimal pour que la chaîne finale soit de longueur multiple de 512. On a donc

m'=m || pad || l(m)

où

pad

est constituée d'un bit "1" suivi d'un certain nombre de bits "0".

La chaîne $m'$ est ensuite découpée $n$ en blocs $m$ ₁,...,m_n de 512 bits (128 chiffres hexadécimaux), soit

m'=m

₁

De même, chaque chaîne

m

_i est découpée en 16 blocs

m

_i,1,...,m_i,16 de 32 bits (8 chiffres hexadécimaux), soit

m

_i,1

_i,16

Dans la suite, on effectue des opérations sur des chaînes de 32 bits. Les opérations utilisées sont les suivantes.

AND: et bit-à-bit.
OR: ou bit-à-bit.
XOR: ou exclusif bit-à-bit.
NOT: complément à 1 bit-à-bit.
$+$ : addition modulo $2$ ³².
$S$ ⁿ: rotation circulaire de $n$ bits vers la gauche.

(L'opération <<< de Java effectue la rotation sur 64 bits.)

Une autre méthode consiste à utiliser des entiers de type short, donc des entiers signés de 32 bits. On peut alors utiliser les opérations &, |, ^, ~, +, <<<. Il faudra cependant prendre soin de bien représenter des entiers non signés.

Dans la suite, on définit les fonctions suivantes:

f

ainsi que les constantes suivantes:

K

5a827999

6ed9eba1

8f1bbcdc

ca62c1d6

On utilise cinq registres de 32 bits $a,b,c,d,e$ , ainsi que cinq registres $h$ ₀,...,h₄ et que 80 registres $w$ ₀,...,w₇₉. On traite itérativement chaque bloc de 512 bits $m$ _i, soit chaque bloc de 16 mots de 32 bits $m$ _i,1,...,m_i,16. On effectue les étapes suivantes.

initialiser
pour i=1 jusqu'à n:
1. initialiser $w$ _t=m_i,t+1 pour $t=0,...,15$
2. pour t=16 jusqu'à 79:
3. initialiser $a=h$ ₀, $b=h$ ₁, $...$ , $e=h$ ₄
4. pour t=0 jusqu'à 79:
  1. effectuer $x=S$ ⁵(a)+f_t(b,c,d)+e+w_t+k_t dans la variable temporaire $x$
  2. effectuer $e=d$ , $d=c$ , $c=S$ ³⁰(b), $b=a$ , $a=x$
5. effectuer $h$ ₀=h₀+a, $...$ , $h$ ₄=h₄+e

Le résultat du hachage est alors

h(m)=h

₀

₄

Par exemple, si $m=$ "abc", le message $m$ représente en fait la chaîne de bits 01100001 01100010 01100011, soit 616263 en hexadécimal. C'est une chaîne de 24 bits, il faut donc la compléter par un bit "1", 423 bits "0", et la chaîne $l(m)=$ 0000000000000018 en hexadécimal. On obtient donc

m'=

61626380 000...0 00000000 00000018

qui fait exactement 512 bits, soit

m

_1,1=61626380,

m

_i,j=0 pour

2<= j<= 15

m

_1,16=00000018. Les 80 itérations conduisent aux résultats suivants dans les registres

a,b,c,d,e

$t$	$a$	$b$	$c$	$d$	$e$
0	`0116fc33`	`67452301`	`7bf36ae2`	`98badcfe`	`10325476`
1	`8990536d`	`0116fc33`	`59d148c0`	`7bf36ae2`	`98badcfe`
2	`a1390f08`	`8990536d`	`c045bf0c`	`59d148c0`	`7bf36ae2`
3	`cdd8e11b`	`a1390f08`	`626414db`	`c045bf0c`	`59d148c0`
4	`cfd499de`	`cdd8e11b`	`284e43c2`	`626414db`	`c045bf0c`
5	`3fc7ca40`	`cfd499de`	`f3763846`	`284e43c2`	`626414db`
6	`993e30c1`	`3fc7ca40`	`b3f52677`	`f3763846`	`284e43c2`
7	`9e8c07d4`	`993e30c1`	`0ff1f290`	`b3f52677`	`f3763846`
8	`4b6ae328`	`9e8c07d4`	`664f8c30`	`0ff1f290`	`b3f52677`
9	`8351f929`	`4b6ae328`	`27a301f5`	`664f8c30`	`0ff1f290`
10	`fbda9e89`	`8351f929`	`12dab8ca`	`27a301f5`	`664f8c30`
11	`63188fe4`	`fbda9e89`	`60d47e4a`	`12dab8ca`	`27a301f5`
12	`4607b664`	`63188fe4`	`7ef6a7a2`	`60d47e4a`	`12dab8ca`
13	`9128f695`	`4607b664`	`18c623f9`	`7ef6a7a2`	`60d47e4a`
14	`196bee77`	`9128f695`	`1181ed99`	`18c623f9`	`7ef6a7a2`
15	`20bdd62f`	`196bee77`	`644a3da5`	`1181ed99`	`18c623f9`
16	`4e925823`	`20bdd62f`	`c65afb9d`	`644a3da5`	`1181ed99`
17	`82aa6728`	`4e925823`	`c82f758b`	`c65afb9d`	`644a3da5`
18	`dc64901d`	`82aa6728`	`d3a49608`	`c82f758b`	`c65afb9d`
19	`fd9e1d7d`	`dc64901d`	`20aa99ca`	`d3a49608`	`c82f758b`
20	`1a37b0ca`	`fd9e1d7d`	`77192407`	`20aa99ca`	`d3a49608`
$...$
78	`5738d5e1`	`860d21cc`	`681e6df6`	`d8fdf6ad`	`d7b9da25`
79	`42541b35`	`5738d5e1`	`21834873`	`681e6df6`	`d8fdf6ad`

On effectue ensuite

h

₀

67452301

42541b35

a9993e36

₁

efcdab89

5738d5e1

4706816a

₂

98badcfe

21834873

ba3e2571

₃

10325476

681e6df6

7850c26c

₄

c3d2e1f0

d8fdf6ad

9cd0d89d

et l'empreinte numérique est finalement

a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d

Pour tester si une implémentation de cette fonction est correcte, on pourra effectuer les trois tests suivants:

h(m

₁

a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d

₂

84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1

₃

34aa973c d4c4daa4 f61eeb2b dbad2731 6534016f

où

m

₁="abc", où

m

₂ est la chaîne

"

abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq

et où

m

₃ est la chaîne composée de 1 million de caractères égaux à "a".

Travail Demandé

Mise en Oeuvre

Faire une application Signature qui permet les utilisations suivantes.

Signature -p par.key:
engendre les paramètres $p$ , $q$ et $g$ et les écrit dans un fichier par.key.
Signature -f par.key -g sec.key pub.key:
engendre une paire $(x,y)$ à partir des paramètres situés dans le fichier par.key, et écrit $x$ et $y$ dans les fichiers séparés sec.key et pub.key.
Signature -f par.key -s sec.key -m mes:
engendre une signature (et l'affiche dans un format standard) pour le message situé dans le fichier mes au moyen des paramètres et de la clef secrète contenus dans les fichiers par.key et sec.key.
Signature -f par.key -s sec.key "str":
même chose, mais pour un message court représenté par la chaîne "str".
Signature -f par.key -k pub.key -m mes "sig":
vérifie la signature "sig" du fichier mes.
Signature -f par.key -k pub.key "str" "sig":
même chose, mais pour un message court représenté par la chaîne "str".
Signature -h -m mes:
calcule l'empreinte numérique du fichier mes.
Signature -h "str":
même chose, mais pour un message court représenté par la chaîne "str".

Problème de la Sécurité

Dans cette question, on supprime l'intervention de

r

dans le calcul de

h(r||m)

. On a alors

s=(h(m)+xr)/k mod q.

Montrer que l'on peut construire des paramètres

p,q,g,m

₁,m₂ tels que

p,q,g

forme un jeu de paramètres valides, que

m

₁ et

m

₂ sont différents et que

h(m

₁

₂

Pour un jeu de clefs

(x,y)

quelconque, calculer une signature

(r,s)

m

₁. Vérifier que

(r,s)

est une signature valide de

m

₂ pour la clef publique

y

. Que penser d'une telle propriété?

Librairie Utiles

Dans la librairie standard java.math est définie la classe BigInteger qui permet de faire des opérations sur des grands nombres. Notamment, on y trouve un test de primalité. Si l'on ne souhaite pas utiliser cette librairie, on devra implémenter le test de Miller-Rabin.

Pour lire un fichier texte ligne par ligne, on pourra utiliser la classe RandomAccessFile. De même, la classe FileOutputStream permet d'écrire dans un fichier.

Références

FIPS 180-1, Secure Hash Standard. U.S. Department of Commerce - National Institute of Standards and Technology, National Technical Information Service, Springfield, Virginia. Federal Information Processing Standards 180-1, 1995.
FIPS 186, Digital Signature Standard. U.S. Department of Commerce - National Institute of Standards and Technology, National Technical Information Service, Springfield, Virginia. Federal Information Processing Standards 186, 1994.
ISO/IEC 14888 Final Draft, Information Technology - Security Techniques - Digital Signatures with Appendix. International Organization for Standardization, Berlin, Germany, 1998.
D. Pointcheval, S. Vaudenay. On Provable Security for Digital Signature Algorithms. Rapport LIENS 96-17, Ecole Normale Supérieure, 1996.
C. P. Schnorr. Efficient Signature Generation by Smart Cards. Journal of Cryptology, vol. 4, pp. 161-174, 1991.
S. Vaudenay. Hidden Collisions on DSS. In Advances in Cryptology CRYPTO'96, Santa Barbara, Californie, U.S.A., Lectures Notes in Computer Science 1109, pp. 83-88, Springer-Verlag, 1996.

Erratum

Sur la page 80, la formule
a été malencontreusement remplacée par
(erreur de position de parenthèse).
Sur la page 78, la formule
a été malencontreusement remplacée par
(q à la place de p).