ISO/IEC 9796:1991

ISOICEI
NORME
INTERNATIONALE
Première édition
1991-09-15
Technologies de l’information - Techniques de
sécurité - Schéma de signature numérique
rétablissant le message
Information technology - Security techniques - Digital signature
scheme giving message recovery
Numéro de référence
ISCYCEI 9796: 199 1 (F)
ISO/CEI 9796: 1991 (F)
Sommaire
Page
. . .
Avant-propos . III
iv
Introduction .
1 Domaine d’application .
2 Définitions .
3 Symboles et abréviations .
4 Vue générale .
5 Opération de signature .
6 Opération de vérification .
Annexes
A Exemple d’un système à clé publique pour signature numérique . 4
B Exemples explicatifs se rapportant à l’annexe A .
C Quelques précautions prises contre diverses attaques potentielles
se rapportant à l’annexe A . 11
D Bibliographie . 12
0 ISO/CEI 1991
Tous droits réservés. Aucune partie de cette publication ne peut être reproduite ni
utilisée sous quelque forme que ce soit et par aucun procédé, électronique ou
mécanique, y compris la photocopie et les microfilms, sans l’accord écrit de l’éditeur.
ISOKEI Bureau du copyright l Case postale 56 l Cl-i-121 1 Genève 20 l Suisse
Imprimé en France
ii
ISO/CEI 9796: 1991 (F)
Avant-propos
L’ISO (Organisation internationale de normalisation) et la CEI (Com-
mission électrotechnique internationale) forment le système spécialisé
de normalisation mondiale. Les organismes nationaux membres de
I’ISO ou de la CEI participent au développement de Normes internatio-
nales par l’intermédiaire des comités techniques créés par I’organi-
sation concernée afin de s’occuper des différents domaines particuliers
de l’activité technique. Les comités techniques de I’ISO et de la CEI
collaborent dans des domaines d’intérêt commun. D’autres organi-
sations internationales, gouvernementales ou non gouvernementales,
en liaison avec I’ISO et la CEI participent également aux travaux.
Dans le domaine des technologies de l’information, I’ISO et la CEI ont
créé un comité technique mixte, I’ISOKEI JTC 1. Les projets de Nor-
mes internationales adoptés par le comité mixte sont soumis aux orga-
nismes nationaux pour vote. Leur publication comme Normes
internationales requiert l’approbation de 75 % au moins des organismes
nationaux votants.
La Norme internationale ISOKEI 9796 a été élaborée par le comité
technique ISOKEI JTC ‘l, TecIwologies de l’information.
Les annexes A, B, C et D sont donnees uniquement à titre d’information.

lSO/CEl 9796: 1991 (F)
Introduction
Une s ignature numérique en écha
nge é lectronique d e l’in for matio n est une
contre
partie d’une signature manue Ile en courrier class #iq ue.
La plupart des schémas de signature numérique sont basés sur un système
particulier à clé publique. Tout système à clé publique comporte trois
opérations de base :
- une production de paires de clés : une clé secrète et une clé publique;
- une opération mettant en œuvre une clé secrète;
- une opération mettant en œuvre une clé publique.
Dans tout schéma de signature numérique à clé publique, la clé secrète est
mise en œuvre dans l’opération de signature pour signer des messages, et la
clé publique est mise en œuvre dans l’opération de vérification pour vérifier
des signatures. Une paire de clés pour un schéma de signature numérique se
compose donc d’une ((clé secrète de signature)) et d’une ((clé publique de
vérification )).
Deux types de schémas de signature numérique ont été clairement identifiés.
- Quand l’opération de vérification exige le message comme élément
d’entrée, le schéma est un ((schéma de signature avec appendice». Une
fonction de hachage est utilisée au cours du calcul de l’appendice.
- Quand l’opération de vérification révèle à la fois le message et sa
redondance spécifique, parfois appelée ((l’ombre du message)), le schéma
est un ((schéma de signature rétablissant le message)).
La présente Norme internationale prescrit un schéma de signature n umé rique
de messages de Ion gueur limitée.
Le présent schéma de signature numérique permet de minimiser les
ressources requises pour vérifiér. II ne fait pas appel à une fonction de hachage
et il évite les attaques connues contre l’algorithme spécifique utilisé.
Le message peut ne pas être formulé en langage naturel. N’importe quel train
de bits de longueur limitée convient. Des exemples de tels messages sont des
éléments de mise à la clé ou le résultat du hachage d’un autre message plus
long, ce qui est encore appelé «l’empreinte d’un message)). Un exemple carac-
téristique est un ensemble structuré de quelques trains de bits provenant de
logiciel et matériel cryptographiques, l’un de ces trains codant une information
de contrôle produite dans le matériel.
NOTE - La présente Norme internationale peut impliquer l’emploi d’éléments brevetés.

ISO/CEI 9796 : 1991 (F)
NORME INTERNATIONALE
Technologies de l’information - Techniques
de sécurité - Schéma de signature numérique
rétablissant le message
1 Domaine d’application 3 Symboles et abréviations
La présente Norme internationale prescrit un schéma de MP Message complété
signature numérique qui rétablit le message quand sa
Message étendu
ME
longueur est limitée et qui utilise un système à clé
publique.
MR Message étendu avec redondance
Le présent schéma de signature numérique comprend IR Entier intermédiaire
- une opération de signature mettant en œuvre une
Signature
c
clé secrète de signature et une fonction de signature
Longueur de la signature en bits
pour signer des messages; ks
- une opération de vérification mettant en œuvre IR’ Entier intermédiaire rétabli
une clé publique de verification et une fonction de
MR‘ Message rétabli avec redondance
vérification pour contrôler des signatures tout en
rétablissant les messages.
MP’ Message complété rétabli
Pendant l’opération de signature, les messages à signer
Sign Fonction de signature sous contrôle de la clé
sont complétés et étendus si nécessaire. Puis on y ajoute
secrète de signature
une redondance artificielle dépendant du message. II n’y a
Vérif Fonction de vérification sous contrôle de la clé
pas d’hypothése sur la présence de redondance naturelle
publique de vérification
dans les messages. L’opération de vérification révèle la
redondance artificielle. En enlevant cette redondance
mod z Calcul arithmétique modulo z
artificielle, on rétablit le message.
Quartet
P
La présente Norme internationale ne spécifie pas I’opé-
Permutation des quartets
n
ration de production des clés, la fonction de signature et
la fonction de vérification. L’annexe A donne un exemple
m Octet
de système à clé publique comprenant une production de
clés, une fonction de signature et une fonction de
S Ombre des octets
vérification. Les différentes étapes de ces opérations sont
XII Y Concaténation des trains de bits X et Y
expliquées par des exemples dans l’annexe B.
X@Y Ou-exclusif des trains de bits X et Y
Certains paramétres du schéma sont liés à la sécurité: la
présente Norme internationale ne prescrit pas les valeurs
à leur donner pour atteindre un niveau donne de sécurité. NOTES
Toutefois, la présente Norme internationale est prescrite
1 Les entiers (et les trains de bits ou d’octets) s’écrivent avec
de façon à limiter les changements entraînés par une
le chiffre (ou le bit ou l’octet) de poids fort à gauche.
éventuelle modification de ces paramètres.
2 La notation hexadécimale avec les chiffres 0 à 9 et A à F est
utilisée dans le tableau 1 et dans l’annexe B.
2 Définitions
4 Vue générale
Pour les besoins de la présente Norme internationale, les
définitions suivantes s’appliquent.
Les deux articles suivants prescrivent
2.1 message: Train de bits de longueur limitée.
- l’opération de signature à l’article 5;
2.2 signature: Train de bits résultant de l’opération de
- l’opération de vérification à l’article 6.
signature.
ISO/CEI 9796 : 1991 (F)
Le nombre z multiplié par seize doit être inférieur ou égal
Chaque entité qui signe doit utiliser et garder secrète sa
au nombre k,+3. Par conséquent, le nombre de bits du
propre clé de signature qui correspond à sa propre clé
message à signer doit être au plus 8 fois le plus grand
publique de vérification.
entier inférieur ou égal à (k,+3)/16.
Les messages à signer doivent être complétés et étendus
si nécessaire. Puis de la redondance y est ajoutée selon 5.2 Extension
des règles prescrites à l’article 5. A partir du message
Le nombre tutilisé par la suite est le plus petit entier .tef
étendu avec redondance, la signature doit être calculée
qu’un train de 2t octets contienne au moins k,-1 bits.
grâce à la clé secrète de signature selon l’article 5.
Le message étendu ME s’obtient en répétant les z octets
Chaque entité qui vérifie devrait connaître et utiliser la clé
de MP autant de fois qu’il le faut, dans l’ordre et chaînés
publique de vérification spécifique à l’entité qui signe. Une
sur la gauche, jusqu’à former un train de t octets.
signature doit être acceptée si et seulement si l’opération
de vérification prescrite à l’article 6 est réussie.
Pour ;Valant de 1 à t et i égal à i-l (mod z) plus un (jvaut
donc de 1 à z), le i-ième octet de ME est égal au j-ième
NOTE - La production et la distribution de clés ne font pas
octet de MP.
l’objet de la présente Norme internationale.
ME= . . . m,II . . . m2 II ml
<- t octets ->
5 Opération de signature NOTE - Le nombre z est inférieur ou égal au nombre t. L’égalité
n’est possible que si k, est congru à 13, 14, 15, 0 ou 1 mod 16.
La figure 1 résume I ‘opération de signature.
5.3 Redondance
Message
Le message étendu avec redondance MR s’obtient en
entrelaçant les t octets de ME en positions impaires et t
octets de redondance en positions paires. Altéré par
l’index r, le quartet de poids faible du 2z-ième octet de MR
code la longueur du message par sa valeur et sa position.
Pour ;Valant de 1 à t,
- le (2i-l)-ième octet de MR est égal au i-ième octet
de ME;
Redondance
I I
- le 2Lième octet de MR est égal à l’image du iième
Troncature et forçage
octet de ME selon l’ombre S prescrite au tableau 1, à
I I
part le 2z-ième octet de MR qui est égal au ou-exclusif
de l’index ravec l’ombre du z-ième octet de ME.
Production de la signature
,
l
MR = . . . S(mJ 0 Al mJI . . . S(m2) II m2 II S(mI) II n?l
< 2 t octets >
NOTE - Le calcul des 2t octets de MR (rn~-~, à mr,) à partir des z
Signature
octets de MP (mp, à mp,) s’effectue en appliquant successive-
Figure 1 - Opération de signature ment les trois formules suivantes pour jvalant de 1 à t.
:= (i-1 mod d+l ; mr2i,l := mpj; mr2,- := S(mp,d
i
NOTE - Une bonne réalisation de l’opération de signature
Enfin, le 2z-ième octet est altéré par l’index r.
devrait protéger physiquement les calculs pour qu’il n’y ait pas
:= r@ mr2,
m2z
d’accès direct à la fonction de signature sous contrôle de la clé
secrète de signature.
5.4 Troncature et forçage
5.1 Remplissage
L’entier intermédiaire IR est codé par un train de I$ bits où
le bit de poids fort vaut 1 et où les ksl bits de poids faible
Le message est un train de bits. Ce train de bits est
sont ceux de MR, à part l’octet de poids faible qui est
complété sur la gauche par 0 à 7 zéros pour obtenir un
remplacé. Si ~2 II ~1 est l’octet de poids faible de Ml?, alors
train de z octets. L’index r utilisé par la suite vaut un de
l’octet de poids faible de IR doit être ~1 II 6.
plus que le nombre de zéros de remplissage. L’index r a
donc une valeur de 1 à 8.
5.5 Production de la signature
Par conséquent, dans le message complét& noté par MP,
les 8z+l -r bits de poids faible sont de l’information.
La signature C est le train de k, bits obtenu en appliquant à
IR la fonction de signature sous contrôle de la clé secrète
MP= m, II rn*l II . . . m2 II ml
de signature.
m, = (r-1 zéros de remplissage) Il (9-r bits d’information) C = Sign( IR)

ISO/CEI 9796 : 1991 (FI
- Permutation net ombre S
Tableau 1
5 6 7 8 9 A B C D E F
P 0 1 2 3 4
/
8 9 4 2 F 0 D B 6 7 A C 1
l7@d E 3 5
I
Si le quartet p comprend les bits a4 a3 a2 al, alors selon la permutation n, son image notée par I~(U) comprend les bits
a4@a2ealel; a4ea3eaI@l; a4@a3ea2@1; a303a2eal.
Si l’octet m comprend les quartets h ccl, alors selon l’ombre S, son image notee par S(m) comprend les quartets nGu2) fl@,).
quatre quartets de poids faible de IR’, alors l’octet de poids
6 Opération de vérification
faible de MR’doit être n-Y& II ~2.
La figure 2 résume l’opération de vérification.
MR’= mzt II rnzt-l II . . . 4 II ml
Signature
NOTE - Les trains MR et MR’ peuvent être différents. Le train
MR’ comprend les ksl bits de poids faible de MR complétés en
poids forts par 0 à 15 zéros.
A partir des 2t octets de MR’, t sommes sont calculées.
Selon l’ombre S prescrite au tableau 1, la I-ième somme
est égale au ou-exclusif du 2kième octet avec l’ombre du
Rétablir le message
(2i-1 )-iéme octet.
\
Oui Non 1
m2j Ci3 S(m2j.-j)
v f
La signature C doit être rejetée quand les t sommes sont
Contrôler la redondance
nulles.
Le nombre z est rétabli par la position de la première
Y
somme non nulle. Le message complété rétabli MP’ est le
Message rétabli
train des z octets de MR’ en positions impaires de poids
(Signature acceptée)
faible.
Figure 2 - Opération de vérification
MP’= ~~1 II rn2M II . . . ~i-1 II . . . Q II ml
L’index r est rétabli par la valeur du quartet de poids faible
6.1 Ouvrir la signature
de la première somme non nulle.
La signature C est transformée en l’entier intermédiaire
La signature C doit être rejetée quand l’index r ne vaut pas
rétabli Wen appliquant à C la fonction de vérification sous
de 1 à 8, et aussi quand les r-l bits de poids fort de MP’
contrôle de la clé publique de vérification.
ne sont pas tous nuls.
IR’ = Vérif( C)
mzzel = (r-l zéros de remplissage) II (9-r bits d’information)
La signature C doit être rejetée quand IR’ n’est pas un
Le message est rétabli par le train des 8z+ 1 -r bits de poids
train de k, bits où le bit de poids fort vaut 1 et où le quartet
faible de MP’.
de poids faible vaut 6.
6.3 Contrôler la redondance
6.2 Rétablir le message
La signature C doit être acceptée si et seulement si les
Le message rétabli avec redondance MR’ est le train de 2t
ksl bits de poids faible de MR’ sont égaux aux ks-1 bits
octets où les l-k, (mod 16) bits de poids forts sont nuls et
de poids faible d’un autre message étendu avec
où les ksl bits de poids faible sont ceux de IR’, h part
redondance calculé à partir du message complété rétabli
l’octet de poids faible qui est remplacé. Selon la permu-
MP’ conformément à 5.2 et 5.3.
tation fl prescrite au tableau 1, si ~4 II ~3 II ~2 II 6 sont les
ISO/CEI 9796 : 1991 (F)
Annexe A
(informative)
Exemple d’un système à clé publique
pour signature numérique
L’exposant public de vérifica tion peut être normalisé dans
A. 1 Définitions
des applications spécifiques.
Module: Entier construit comme le produit de deux
- Les valeurs 2 et 3 peuvent présenter des avantages
NOTE
nombres premiers.
pratiques.
Clé publique de vérification: Module et exposant de
vérification.
A.3.2 Facteurs premiers secrets et module public
Clé secrète de signature: Exposant de signature.
Chaque entité qui signe doit secrètement choisir au hasard
deux nombres premiers impairs distincts p et g respectant
les contraintes suivantes.
A.2 Symboles et abréviations
doivent être
- Si v est impair, alors p-l et q-l
RR Élément représentatif
premiers avec v.
IS Entier résultant
- Si v est pair, alors (p-l)/2 et (q-1 )/2 doivent être
n Module
premiers avec v. De plus, p et g ne doivent pas être
congrus l’un à l’autre modulo 8.
k Longueur du module en bits
Facteurs premiers du module
P8 cl
Le module public n est le produit des facteurs premiers
V Exposant de vérification
secrets p et g.
S Exposant de signature
n=pq
ppcm(a, b) Plus petit commun multiple des entiers a et b
La longueur du module est k. Le nombre k doit valoir k,+l .
Symbole de Jacobi de a par rapport à n
(a1 n)
NOTES
NOTE - Soit n un nombre premier impair, et a un entier positif.
1 Certaines autres contraintes peuvent être prises en compte
La formule suivante définit le symbole de Legendre de l’entier a
dans le choix des nombres premiers de façon à décourager la
par rapport au nombre premier p.
mise en facteurs du module.
(a I p) = a(pi)n mod p
2 Certaines formes du module simplifient la réduction modulo
Quand l’entier a n’est pas un multiple de p, alors le symbole de
tout en utilisant moins de mémoire. Ces formes sont
Legendre de l’entier a par rapport au nombre premier p vaut +l
ou -1 selon que l’entier a est ou n’est pas un carré modulo p.
F ,: n=2 64X-c de longueur * . k = 64x bits
,
x y,
Le symbole de Legendre des multiples de p par rapport au
F = 264x+c de longueur : k = 64x+1 bits,
nombre premier p est nul. x, y, + : n
où : 1 5 y 5 2.x et c < 264x -8y c 2c.
Soit n un entier positif impair, et a un entier positif. Le symbole
Dans les formes négatives, tous les bits des y octets de poids
de Jacobi de l’entier a par rapport à l’entier n est le produit des
fort sont à un, jusqu’à un quart de la longueur du module.
symboles de Legendre de l’entier a par rapport aux facteurs
premiers de n.
Dans les formes positives, après un bit à 1 isolé en poids fort,
Par conséquent, si n = tous les bits des y octets de poids fort sont à zéro, jusqu’à un
p Q, alors (a I n) = (a I pl (a I 4).
quart de la longueur du module.
Le symbole de Jacobi de tout entier a par rapport à tout entier n
peut être efficacement calcule sans les facteurs premiers de n.
A.3.3
Exposant secret de signature
L’exposant secret de signature est le plus petit entier
A.3 Production de clés
soit un multiple d e
positif s tel que sw
A.3.1 Exposant public de vérification
- ppcm(p1, g-1) si v est impair;
Chaque entité qui sig ne doit choisir un entier positif v
- k ppcm@--1 , el) si v est pair.
comme exposant publi c de vérification
ISO/CEI 9796 : 1991 (F)
A.5 Fonction de vérification
A.4 Fonction de signature
La signature C est un entier positif inférieur à n/2 qu’il faut
L’entier intermédiaire IR est un train de k-l bits calculé
élever à la puissance v modulo n pour obtenir l’entier
selon 5.4.
résultant IS.
L’élément représentatif de IR par rapport à n s’appelle RR.
L’entier intermédiaire rétabli IR’ est alors défini par le
- Si v est impair, alors RR vaut IR.
décodage suivant.
- Si v est pair et si (IR I n) = +l, alors RR vaut IR.
- Si IS est congru à 6 mod 16, alors IR’ vaut IS.
- Si v est pair et si (IR I n) = -1, alors RR vaut lR/Z.
- Si n-6 est congru à 6 mod 16, alors IR’vaut n--E.
NOTE - Si v est pa ir, alors le symbole de de RR par
De plus, quand v est pair,
rapport à n est force à +l.
- si IS est congru à 3 mod 8, alors IR’vaut 21s;
II faut élever RR à la puissance s modulo n. La signature C
- si n-E est congru à 3 mod 8, alors IR’vaut 2(MS).
est le résultat ou bien son complément à n, le plus petit
des deux.
La signature C doit être rejetée dans tous les autres cas,
et aussi quand IR’ n’est pas compris entre 2k-2 et 2k-1-1.
C = min { RRS mod n, n-(RRS mod n) )
Ceci définit la fonction de signature Gign». Ceci définit la fonction de vérification «Vérif».
2 = Sign( IR ) IR’ = Vérif( C)
ISO/CEI 9796 : 1991 (F)
Annexe B
(informative)
Exemples explicatifs
se rapportant à l’annexe A
La notation hexadécimale est utilisée.
8.1.3 Exemple 1
B.1 Exemples avec l’exposant public trois
Cet exemple explique le remplissa ge, I’exten sion et la
B.1.1 Production des clés
troncature pou r signer un message d e 100 bits.
C BBAA 9988 7766 5544 3322 1100
L’exposant public de vérification est v = 3.
Opération de signature
Les facteurs premiers secrets p et q sont donc tous les
deux congrus à 2 modulo 3.
Après remplissage par quatre zéros à gauche, le message
BA09106C 754EB6FE BBC21 479 9FFl B8DE
P= complété MP est un train de 13 octets. Ainsi, z=13 et r=5.
1 B4CBB7A 7A782B15 7Cl BCI 52 90AlA3AB
MP= OC BBAA9988 77665544 33221100
=
1 6046EB39 E03BEAB6 21 DO3CO8 B8AE6B66
CFF955B6 4B4F48B7 EE152A32 6BF8CB25
Le message étendu ME s’obtient en répétant les 13 octets
...

ISOICEI
NORME
INTERNATIONALE
Première édition
1991-09-15
Technologies de l’information - Techniques de
sécurité - Schéma de signature numérique
rétablissant le message
Information technology - Security techniques - Digital signature
scheme giving message recovery
Numéro de référence
ISCYCEI 9796: 199 1 (F)
ISO/CEI 9796: 1991 (F)
Sommaire
Page
. . .
Avant-propos . III
iv
Introduction .
1 Domaine d’application .
2 Définitions .
3 Symboles et abréviations .
4 Vue générale .
5 Opération de signature .
6 Opération de vérification .
Annexes
A Exemple d’un système à clé publique pour signature numérique . 4
B Exemples explicatifs se rapportant à l’annexe A .
C Quelques précautions prises contre diverses attaques potentielles
se rapportant à l’annexe A . 11
D Bibliographie . 12
0 ISO/CEI 1991
Tous droits réservés. Aucune partie de cette publication ne peut être reproduite ni
utilisée sous quelque forme que ce soit et par aucun procédé, électronique ou
mécanique, y compris la photocopie et les microfilms, sans l’accord écrit de l’éditeur.
ISOKEI Bureau du copyright l Case postale 56 l Cl-i-121 1 Genève 20 l Suisse
Imprimé en France
ii
ISO/CEI 9796: 1991 (F)
Avant-propos
L’ISO (Organisation internationale de normalisation) et la CEI (Com-
mission électrotechnique internationale) forment le système spécialisé
de normalisation mondiale. Les organismes nationaux membres de
I’ISO ou de la CEI participent au développement de Normes internatio-
nales par l’intermédiaire des comités techniques créés par I’organi-
sation concernée afin de s’occuper des différents domaines particuliers
de l’activité technique. Les comités techniques de I’ISO et de la CEI
collaborent dans des domaines d’intérêt commun. D’autres organi-
sations internationales, gouvernementales ou non gouvernementales,
en liaison avec I’ISO et la CEI participent également aux travaux.
Dans le domaine des technologies de l’information, I’ISO et la CEI ont
créé un comité technique mixte, I’ISOKEI JTC 1. Les projets de Nor-
mes internationales adoptés par le comité mixte sont soumis aux orga-
nismes nationaux pour vote. Leur publication comme Normes
internationales requiert l’approbation de 75 % au moins des organismes
nationaux votants.
La Norme internationale ISOKEI 9796 a été élaborée par le comité
technique ISOKEI JTC ‘l, TecIwologies de l’information.
Les annexes A, B, C et D sont donnees uniquement à titre d’information.

lSO/CEl 9796: 1991 (F)
Introduction
Une s ignature numérique en écha
nge é lectronique d e l’in for matio n est une
contre
partie d’une signature manue Ile en courrier class #iq ue.
La plupart des schémas de signature numérique sont basés sur un système
particulier à clé publique. Tout système à clé publique comporte trois
opérations de base :
- une production de paires de clés : une clé secrète et une clé publique;
- une opération mettant en œuvre une clé secrète;
- une opération mettant en œuvre une clé publique.
Dans tout schéma de signature numérique à clé publique, la clé secrète est
mise en œuvre dans l’opération de signature pour signer des messages, et la
clé publique est mise en œuvre dans l’opération de vérification pour vérifier
des signatures. Une paire de clés pour un schéma de signature numérique se
compose donc d’une ((clé secrète de signature)) et d’une ((clé publique de
vérification )).
Deux types de schémas de signature numérique ont été clairement identifiés.
- Quand l’opération de vérification exige le message comme élément
d’entrée, le schéma est un ((schéma de signature avec appendice». Une
fonction de hachage est utilisée au cours du calcul de l’appendice.
- Quand l’opération de vérification révèle à la fois le message et sa
redondance spécifique, parfois appelée ((l’ombre du message)), le schéma
est un ((schéma de signature rétablissant le message)).
La présente Norme internationale prescrit un schéma de signature n umé rique
de messages de Ion gueur limitée.
Le présent schéma de signature numérique permet de minimiser les
ressources requises pour vérifiér. II ne fait pas appel à une fonction de hachage
et il évite les attaques connues contre l’algorithme spécifique utilisé.
Le message peut ne pas être formulé en langage naturel. N’importe quel train
de bits de longueur limitée convient. Des exemples de tels messages sont des
éléments de mise à la clé ou le résultat du hachage d’un autre message plus
long, ce qui est encore appelé «l’empreinte d’un message)). Un exemple carac-
téristique est un ensemble structuré de quelques trains de bits provenant de
logiciel et matériel cryptographiques, l’un de ces trains codant une information
de contrôle produite dans le matériel.
NOTE - La présente Norme internationale peut impliquer l’emploi d’éléments brevetés.

ISO/CEI 9796 : 1991 (F)
NORME INTERNATIONALE
Technologies de l’information - Techniques
de sécurité - Schéma de signature numérique
rétablissant le message
1 Domaine d’application 3 Symboles et abréviations
La présente Norme internationale prescrit un schéma de MP Message complété
signature numérique qui rétablit le message quand sa
Message étendu
ME
longueur est limitée et qui utilise un système à clé
publique.
MR Message étendu avec redondance
Le présent schéma de signature numérique comprend IR Entier intermédiaire
- une opération de signature mettant en œuvre une
Signature
c
clé secrète de signature et une fonction de signature
Longueur de la signature en bits
pour signer des messages; ks
- une opération de vérification mettant en œuvre IR’ Entier intermédiaire rétabli
une clé publique de verification et une fonction de
MR‘ Message rétabli avec redondance
vérification pour contrôler des signatures tout en
rétablissant les messages.
MP’ Message complété rétabli
Pendant l’opération de signature, les messages à signer
Sign Fonction de signature sous contrôle de la clé
sont complétés et étendus si nécessaire. Puis on y ajoute
secrète de signature
une redondance artificielle dépendant du message. II n’y a
Vérif Fonction de vérification sous contrôle de la clé
pas d’hypothése sur la présence de redondance naturelle
publique de vérification
dans les messages. L’opération de vérification révèle la
redondance artificielle. En enlevant cette redondance
mod z Calcul arithmétique modulo z
artificielle, on rétablit le message.
Quartet
P
La présente Norme internationale ne spécifie pas I’opé-
Permutation des quartets
n
ration de production des clés, la fonction de signature et
la fonction de vérification. L’annexe A donne un exemple
m Octet
de système à clé publique comprenant une production de
clés, une fonction de signature et une fonction de
S Ombre des octets
vérification. Les différentes étapes de ces opérations sont
XII Y Concaténation des trains de bits X et Y
expliquées par des exemples dans l’annexe B.
X@Y Ou-exclusif des trains de bits X et Y
Certains paramétres du schéma sont liés à la sécurité: la
présente Norme internationale ne prescrit pas les valeurs
à leur donner pour atteindre un niveau donne de sécurité. NOTES
Toutefois, la présente Norme internationale est prescrite
1 Les entiers (et les trains de bits ou d’octets) s’écrivent avec
de façon à limiter les changements entraînés par une
le chiffre (ou le bit ou l’octet) de poids fort à gauche.
éventuelle modification de ces paramètres.
2 La notation hexadécimale avec les chiffres 0 à 9 et A à F est
utilisée dans le tableau 1 et dans l’annexe B.
2 Définitions
4 Vue générale
Pour les besoins de la présente Norme internationale, les
définitions suivantes s’appliquent.
Les deux articles suivants prescrivent
2.1 message: Train de bits de longueur limitée.
- l’opération de signature à l’article 5;
2.2 signature: Train de bits résultant de l’opération de
- l’opération de vérification à l’article 6.
signature.
ISO/CEI 9796 : 1991 (F)
Le nombre z multiplié par seize doit être inférieur ou égal
Chaque entité qui signe doit utiliser et garder secrète sa
au nombre k,+3. Par conséquent, le nombre de bits du
propre clé de signature qui correspond à sa propre clé
message à signer doit être au plus 8 fois le plus grand
publique de vérification.
entier inférieur ou égal à (k,+3)/16.
Les messages à signer doivent être complétés et étendus
si nécessaire. Puis de la redondance y est ajoutée selon 5.2 Extension
des règles prescrites à l’article 5. A partir du message
Le nombre tutilisé par la suite est le plus petit entier .tef
étendu avec redondance, la signature doit être calculée
qu’un train de 2t octets contienne au moins k,-1 bits.
grâce à la clé secrète de signature selon l’article 5.
Le message étendu ME s’obtient en répétant les z octets
Chaque entité qui vérifie devrait connaître et utiliser la clé
de MP autant de fois qu’il le faut, dans l’ordre et chaînés
publique de vérification spécifique à l’entité qui signe. Une
sur la gauche, jusqu’à former un train de t octets.
signature doit être acceptée si et seulement si l’opération
de vérification prescrite à l’article 6 est réussie.
Pour ;Valant de 1 à t et i égal à i-l (mod z) plus un (jvaut
donc de 1 à z), le i-ième octet de ME est égal au j-ième
NOTE - La production et la distribution de clés ne font pas
octet de MP.
l’objet de la présente Norme internationale.
ME= . . . m,II . . . m2 II ml
<- t octets ->
5 Opération de signature NOTE - Le nombre z est inférieur ou égal au nombre t. L’égalité
n’est possible que si k, est congru à 13, 14, 15, 0 ou 1 mod 16.
La figure 1 résume I ‘opération de signature.
5.3 Redondance
Message
Le message étendu avec redondance MR s’obtient en
entrelaçant les t octets de ME en positions impaires et t
octets de redondance en positions paires. Altéré par
l’index r, le quartet de poids faible du 2z-ième octet de MR
code la longueur du message par sa valeur et sa position.
Pour ;Valant de 1 à t,
- le (2i-l)-ième octet de MR est égal au i-ième octet
de ME;
Redondance
I I
- le 2Lième octet de MR est égal à l’image du iième
Troncature et forçage
octet de ME selon l’ombre S prescrite au tableau 1, à
I I
part le 2z-ième octet de MR qui est égal au ou-exclusif
de l’index ravec l’ombre du z-ième octet de ME.
Production de la signature
,
l
MR = . . . S(mJ 0 Al mJI . . . S(m2) II m2 II S(mI) II n?l
< 2 t octets >
NOTE - Le calcul des 2t octets de MR (rn~-~, à mr,) à partir des z
Signature
octets de MP (mp, à mp,) s’effectue en appliquant successive-
Figure 1 - Opération de signature ment les trois formules suivantes pour jvalant de 1 à t.
:= (i-1 mod d+l ; mr2i,l := mpj; mr2,- := S(mp,d
i
NOTE - Une bonne réalisation de l’opération de signature
Enfin, le 2z-ième octet est altéré par l’index r.
devrait protéger physiquement les calculs pour qu’il n’y ait pas
:= r@ mr2,
m2z
d’accès direct à la fonction de signature sous contrôle de la clé
secrète de signature.
5.4 Troncature et forçage
5.1 Remplissage
L’entier intermédiaire IR est codé par un train de I$ bits où
le bit de poids fort vaut 1 et où les ksl bits de poids faible
Le message est un train de bits. Ce train de bits est
sont ceux de MR, à part l’octet de poids faible qui est
complété sur la gauche par 0 à 7 zéros pour obtenir un
remplacé. Si ~2 II ~1 est l’octet de poids faible de Ml?, alors
train de z octets. L’index r utilisé par la suite vaut un de
l’octet de poids faible de IR doit être ~1 II 6.
plus que le nombre de zéros de remplissage. L’index r a
donc une valeur de 1 à 8.
5.5 Production de la signature
Par conséquent, dans le message complét& noté par MP,
les 8z+l -r bits de poids faible sont de l’information.
La signature C est le train de k, bits obtenu en appliquant à
IR la fonction de signature sous contrôle de la clé secrète
MP= m, II rn*l II . . . m2 II ml
de signature.
m, = (r-1 zéros de remplissage) Il (9-r bits d’information) C = Sign( IR)

ISO/CEI 9796 : 1991 (FI
- Permutation net ombre S
Tableau 1
5 6 7 8 9 A B C D E F
P 0 1 2 3 4
/
8 9 4 2 F 0 D B 6 7 A C 1
l7@d E 3 5
I
Si le quartet p comprend les bits a4 a3 a2 al, alors selon la permutation n, son image notée par I~(U) comprend les bits
a4@a2ealel; a4ea3eaI@l; a4@a3ea2@1; a303a2eal.
Si l’octet m comprend les quartets h ccl, alors selon l’ombre S, son image notee par S(m) comprend les quartets nGu2) fl@,).
quatre quartets de poids faible de IR’, alors l’octet de poids
6 Opération de vérification
faible de MR’doit être n-Y& II ~2.
La figure 2 résume l’opération de vérification.
MR’= mzt II rnzt-l II . . . 4 II ml
Signature
NOTE - Les trains MR et MR’ peuvent être différents. Le train
MR’ comprend les ksl bits de poids faible de MR complétés en
poids forts par 0 à 15 zéros.
A partir des 2t octets de MR’, t sommes sont calculées.
Selon l’ombre S prescrite au tableau 1, la I-ième somme
est égale au ou-exclusif du 2kième octet avec l’ombre du
Rétablir le message
(2i-1 )-iéme octet.
\
Oui Non 1
m2j Ci3 S(m2j.-j)
v f
La signature C doit être rejetée quand les t sommes sont
Contrôler la redondance
nulles.
Le nombre z est rétabli par la position de la première
Y
somme non nulle. Le message complété rétabli MP’ est le
Message rétabli
train des z octets de MR’ en positions impaires de poids
(Signature acceptée)
faible.
Figure 2 - Opération de vérification
MP’= ~~1 II rn2M II . . . ~i-1 II . . . Q II ml
L’index r est rétabli par la valeur du quartet de poids faible
6.1 Ouvrir la signature
de la première somme non nulle.
La signature C est transformée en l’entier intermédiaire
La signature C doit être rejetée quand l’index r ne vaut pas
rétabli Wen appliquant à C la fonction de vérification sous
de 1 à 8, et aussi quand les r-l bits de poids fort de MP’
contrôle de la clé publique de vérification.
ne sont pas tous nuls.
IR’ = Vérif( C)
mzzel = (r-l zéros de remplissage) II (9-r bits d’information)
La signature C doit être rejetée quand IR’ n’est pas un
Le message est rétabli par le train des 8z+ 1 -r bits de poids
train de k, bits où le bit de poids fort vaut 1 et où le quartet
faible de MP’.
de poids faible vaut 6.
6.3 Contrôler la redondance
6.2 Rétablir le message
La signature C doit être acceptée si et seulement si les
Le message rétabli avec redondance MR’ est le train de 2t
ksl bits de poids faible de MR’ sont égaux aux ks-1 bits
octets où les l-k, (mod 16) bits de poids forts sont nuls et
de poids faible d’un autre message étendu avec
où les ksl bits de poids faible sont ceux de IR’, h part
redondance calculé à partir du message complété rétabli
l’octet de poids faible qui est remplacé. Selon la permu-
MP’ conformément à 5.2 et 5.3.
tation fl prescrite au tableau 1, si ~4 II ~3 II ~2 II 6 sont les
ISO/CEI 9796 : 1991 (F)
Annexe A
(informative)
Exemple d’un système à clé publique
pour signature numérique
L’exposant public de vérifica tion peut être normalisé dans
A. 1 Définitions
des applications spécifiques.
Module: Entier construit comme le produit de deux
- Les valeurs 2 et 3 peuvent présenter des avantages
NOTE
nombres premiers.
pratiques.
Clé publique de vérification: Module et exposant de
vérification.
A.3.2 Facteurs premiers secrets et module public
Clé secrète de signature: Exposant de signature.
Chaque entité qui signe doit secrètement choisir au hasard
deux nombres premiers impairs distincts p et g respectant
les contraintes suivantes.
A.2 Symboles et abréviations
doivent être
- Si v est impair, alors p-l et q-l
RR Élément représentatif
premiers avec v.
IS Entier résultant
- Si v est pair, alors (p-l)/2 et (q-1 )/2 doivent être
n Module
premiers avec v. De plus, p et g ne doivent pas être
congrus l’un à l’autre modulo 8.
k Longueur du module en bits
Facteurs premiers du module
P8 cl
Le module public n est le produit des facteurs premiers
V Exposant de vérification
secrets p et g.
S Exposant de signature
n=pq
ppcm(a, b) Plus petit commun multiple des entiers a et b
La longueur du module est k. Le nombre k doit valoir k,+l .
Symbole de Jacobi de a par rapport à n
(a1 n)
NOTES
NOTE - Soit n un nombre premier impair, et a un entier positif.
1 Certaines autres contraintes peuvent être prises en compte
La formule suivante définit le symbole de Legendre de l’entier a
dans le choix des nombres premiers de façon à décourager la
par rapport au nombre premier p.
mise en facteurs du module.
(a I p) = a(pi)n mod p
2 Certaines formes du module simplifient la réduction modulo
Quand l’entier a n’est pas un multiple de p, alors le symbole de
tout en utilisant moins de mémoire. Ces formes sont
Legendre de l’entier a par rapport au nombre premier p vaut +l
ou -1 selon que l’entier a est ou n’est pas un carré modulo p.
F ,: n=2 64X-c de longueur * . k = 64x bits
,
x y,
Le symbole de Legendre des multiples de p par rapport au
F = 264x+c de longueur : k = 64x+1 bits,
nombre premier p est nul. x, y, + : n
où : 1 5 y 5 2.x et c < 264x -8y c 2c.
Soit n un entier positif impair, et a un entier positif. Le symbole
Dans les formes négatives, tous les bits des y octets de poids
de Jacobi de l’entier a par rapport à l’entier n est le produit des
fort sont à un, jusqu’à un quart de la longueur du module.
symboles de Legendre de l’entier a par rapport aux facteurs
premiers de n.
Dans les formes positives, après un bit à 1 isolé en poids fort,
Par conséquent, si n = tous les bits des y octets de poids fort sont à zéro, jusqu’à un
p Q, alors (a I n) = (a I pl (a I 4).
quart de la longueur du module.
Le symbole de Jacobi de tout entier a par rapport à tout entier n
peut être efficacement calcule sans les facteurs premiers de n.
A.3.3
Exposant secret de signature
L’exposant secret de signature est le plus petit entier
A.3 Production de clés
soit un multiple d e
positif s tel que sw
A.3.1 Exposant public de vérification
- ppcm(p1, g-1) si v est impair;
Chaque entité qui sig ne doit choisir un entier positif v
- k ppcm@--1 , el) si v est pair.
comme exposant publi c de vérification
ISO/CEI 9796 : 1991 (F)
A.5 Fonction de vérification
A.4 Fonction de signature
La signature C est un entier positif inférieur à n/2 qu’il faut
L’entier intermédiaire IR est un train de k-l bits calculé
élever à la puissance v modulo n pour obtenir l’entier
selon 5.4.
résultant IS.
L’élément représentatif de IR par rapport à n s’appelle RR.
L’entier intermédiaire rétabli IR’ est alors défini par le
- Si v est impair, alors RR vaut IR.
décodage suivant.
- Si v est pair et si (IR I n) = +l, alors RR vaut IR.
- Si IS est congru à 6 mod 16, alors IR’ vaut IS.
- Si v est pair et si (IR I n) = -1, alors RR vaut lR/Z.
- Si n-6 est congru à 6 mod 16, alors IR’vaut n--E.
NOTE - Si v est pa ir, alors le symbole de de RR par
De plus, quand v est pair,
rapport à n est force à +l.
- si IS est congru à 3 mod 8, alors IR’vaut 21s;
II faut élever RR à la puissance s modulo n. La signature C
- si n-E est congru à 3 mod 8, alors IR’vaut 2(MS).
est le résultat ou bien son complément à n, le plus petit
des deux.
La signature C doit être rejetée dans tous les autres cas,
et aussi quand IR’ n’est pas compris entre 2k-2 et 2k-1-1.
C = min { RRS mod n, n-(RRS mod n) )
Ceci définit la fonction de signature Gign». Ceci définit la fonction de vérification «Vérif».
2 = Sign( IR ) IR’ = Vérif( C)
ISO/CEI 9796 : 1991 (F)
Annexe B
(informative)
Exemples explicatifs
se rapportant à l’annexe A
La notation hexadécimale est utilisée.
8.1.3 Exemple 1
B.1 Exemples avec l’exposant public trois
Cet exemple explique le remplissa ge, I’exten sion et la
B.1.1 Production des clés
troncature pou r signer un message d e 100 bits.
C BBAA 9988 7766 5544 3322 1100
L’exposant public de vérification est v = 3.
Opération de signature
Les facteurs premiers secrets p et q sont donc tous les
deux congrus à 2 modulo 3.
Après remplissage par quatre zéros à gauche, le message
BA09106C 754EB6FE BBC21 479 9FFl B8DE
P= complété MP est un train de 13 octets. Ainsi, z=13 et r=5.
1 B4CBB7A 7A782B15 7Cl BCI 52 90AlA3AB
MP= OC BBAA9988 77665544 33221100
=
1 6046EB39 E03BEAB6 21 DO3CO8 B8AE6B66
CFF955B6 4B4F48B7 EE152A32 6BF8CB25
Le message étendu ME s’obtient en répétant les 13 octets
...