1. Introduction

1.1. Pourquoi un tel document

Faire des calculs à la main sur des signatures électroniques est très ludique.

Il faut s’entendre sur le terme "à la main". Au fil du document nous ne ferons aucun calcul à la main ni même avec une calculatrice de bureau. Les nombres manipulés sont beaucoup trop grands. Même à supposer que l’on décide d’utiliser une calculatrice de bureau (la chose est sans doute possible, en transférant les données depuis un PC), il faudrait la programmer en raison du nombre d’étapes de calcul.

1.2. Contenu

Cet article décrit les calculs à faire pour vérifier des signatures RSA et ECDSA, dans le cadre x509 et 2D-Doc.

RSA ECDSA

RSA et ECDSA permettent de signer [1] avec une paire de clés privée et publique. La clé privée est utilisée pour signer. La clé publique permet de vérifier la signature.

Nous examinerons trois cas de signatures électroniques :
  1. RSA dans le contexte x509 : cas du certificat d’un serveur https

  2. ECDSA dans le contexte x509 : création d’un certificat x509 auto-signé, afin de se familiariser avec les calculs sur les courbes elliptiques

  3. ECDSA dans le contexte 2D-Doc : vérification d’un code 2D-Doc, qui est le standard du Certificat Électronique Visible

Au fil du document nous ferons appel aux outils suivants :
  • openssl pour travailler sur les certificats x509 en ligne de commande

  • pkfile pour extraire la partie signée d’un certificat et dder pour afficher certains contenus binaires

  • python ou bc pour faire des calculs avec des nombres entiers de grande taille

  • Conversion entre encodage PEM et encodage binaire (Linux : base64, Windows : notepad++)

  • Édition de contenu de fichier binaire (Linux : gvim/xxd, Windows : notepad++)

Note
Windows versus Linux

Ce document s’adresse aux utilisateurs de Windows et Linux.

Il peut arriver que l’outil ou la commande à employer diffère entre les deux environnements, dans ce cas les deux sont présentés.

2. Le format x509

2.1. Visualisation d’un certificat x509

A l’aide d’un navigateur, ouvrir une page en https et afficher le certificat. Les exemples de ce document sont réalisés avec le certificat https du site https://letsencrypt.org/.

Exemple avec Firefox 44
  1. Cliquer sur l’icône de cadenas à gauche de la barre d’adresse et cliquer sur la flèche droite (Figure 1)

  2. Cliquer sur Plus d’informations (Figure 2)

  3. Cliquer sur Afficher le certificat (Figure 3)

  4. Afficher l’onglet Détails et parcourir les différents champs du certificat (Figure 4, 5 et 6)

Image Firefox 1
Fig. 1
Image Firefox 2
Fig. 2
Image Firefox 3
Fig. 3
Image Firefox 4
Fig. 4
Image Firefox 5
Fig. 5
Image Firefox 6
Fig. 6

Nous nous intéresserons à la partie supérieure (Hiérarchie des certificats) plus tard.

Pour le moment examinons le certificat. L’affichage de Firefox en dessous de Champs du certificat liste trois parties :

  1. Le certificat proprement dit, qui contient beaucoup d’informations structurées sur plusieurs niveaux hiérarchiques

  2. L’algorithme de signature du certificat, dans notre exemple, PKCS #1 SHA-256 avec chiffrement RSA

  3. La signature du certificat, ici, une suite de 256 octets

Cette structure en trois parties est toujours respectée pour un certificat x509. A noter qu’Internet Explorer et Chrome affichent les mêmes informations mais sans faire ressortir la structure trois parties.

2.2. Structure d’un certificat x509

Où la structure d’un certificat est-elle définie, et quelle est cette définition ?

Une recherche sur un moteur de recherche avec les mots-clés RFC et x509 produit l’URL suivante dans les premières réponses :

Et effectivement la[2] RFC 5280 définit le format x509 version 3.

Affichons-la. Dans la section 4.1 se trouve la définition suivante.

...
4.1.  Basic Certificate Fields

   The X.509 v3 certificate basic syntax is as follows.  For signature
   calculation, the data that is to be signed is encoded using the ASN.1
   distinguished encoding rules (DER) [X.690].  ASN.1 DER encoding is a
   tag, length, value encoding system for each element.

Certificate  ::=  SEQUENCE  {
	tbsCertificate       TBSCertificate,
	signatureAlgorithm   AlgorithmIdentifier,
	signatureValue       BIT STRING  }
...

La suite définit les différents éléments du certificat, à savoir TBSCertificate et AlgorithmIdentifier.

Grammaire, ASN.1 et DER

La structure du certificat est décrite par une grammaire, d’après les règles de syntaxe ASN.1 (Abstrat Syntax Notation number 1[1].

Les différents encodages possibles du standard ASN.1 sont eux-mêmes des standards et le X.690 est l’un d’entre eux [2].

La RFC précise que la partie du certificat à signer doit être encodée selon le standard Distinguished Encoding Rules ou DER. Entre autres encodages, le document X.690 définit le DER.

Nous verrons plus loin l’encodage DER. Si vous souhaitez le découvrir, plutôt que d’examiner directement le document X.690, je vous recommande de commencer par l’article Wikipédia [3].

En ASN.1 le mot-clé SEQUENCE sans autre précision indique que la valeur est constituée d’une suite de valeurs elles-mêmes spécifiées en ASN.1. La valeur Certificate contient donc, à la suite :

  1. La valeur tbsCertificate, soit le certificat à signer (to be signed Certificate)

  2. La valeur signatureAlgorithm, soit l’identification de l’algorithme de signature

  3. La valeur signatureValue, soit la signature elle-même

2.3. Hiérarchie des certificats

Dans la partie tbsCertificate de letsencrypt.org, intéressons-nous à deux éléments en particulier, l'émetteur du certificat et le sujet du certificat.

  • Le sujet du certificat a pour CN (Common Name) letsencrypt.org et c’est le dernier nom qui est affiché dans la hiérarchie des certificats (partie supérieure de la fenêtre).

  • L'émetteur du certificat a pour CN TrustID Server CA A52 et on peut voir ce nom au-dessus de letsencrypt.org dans la hiérarchie.

L’émetteur et le sujet ont également le pays © et l’organisation (O) définis dans leur nom, ainsi que d’autres éléments. Le "nom simple" ou "nom court" du certificat est son CN. Le standard x509 ne définit pas cette notion de "nom simple" ou "nom court", nous l’employons ici pour préciser que dans la pratique, le CN est le véritable nom du certificat, les autres éléments donnant des informations annexes.

Cela dit, le nom (au sens du standard x509) est constitué du DN (Distinguished Name), il s’agit de la la totalité des éléments qui le composent (et non pas seulement du CN).

Le lien hiérarchique est toujours établi entre un émetteur et un sujet. L’émetteur est celui qui signe le certificat, le sujet est celui qui est signé. Voir figures 7 et 8.

Un certificat peut être à la fois émetteur (d’autres certificats sont signés par lui) et sujet (il est lui-même signé par un autre certificat), et cette chaîne forme une structure hiérarchique. Dans notre exemple, on voit que le certificat TrustID Server CA A52 est lui-même signé par IdenTrust Commercial Root CA 1.

Note
  • Dans la pratique la situation peut se compliquer avec des certificats croisés.

  • Un cas particulier est celui où l’émetteur et le sujet sont identiques. Ce sont les certificats auto-signés. C’est le cas des certificats racine (en haut de la hiérarchie) et parfois d’autres certificats auto-signés pour toutes sortes de raisons bonnes ou mauvaises (souvent mauvaises, mais il existe des cas légitimes).

  • Quoi qu’il en soit, la structure de base des liens qui relient les certificats est hiérarchique.

Quelques précisions
  • Pour qu’un certificat joue le rôle émetteur, il doit être une autorité de certification ou CA (Certificate Authority), il s’agit de l’une des nombreuses options que l’on peut trouver dans un certificat.

  • En plus des éléments permettant d’identifier le sujet du certificat, la partie tbsCertificate contient sa clé publique. C’est précisément le rôle du certificat : certifier la correspondance entre une entité (un DN) et une clé publique.

  • L’émetteur (qui est forcément une autorité de certification) a toujours un numéro d’identification de clé (Subject Key Identifier). Cet identifiant, qui doit être par construction un entier, doit être enregistré dans les certificats émis comme numéro de clé d’autorité de certification (Authority Key Identifier). Cette logique permet de gérer facilement les cas où une autorité de certification possède plusieurs clés.

    • En résumé, quand un émetteur signe un sujet, on doit avoir égalité entre ces différents éléments

      Dans le certificat émetteur Lien Dans le certificat sujet

      Subject DN [3]

      =

      Issuer DN

      Subject Key Identifier

      =

      Authority Key Identifier

    • La RFC 5280 ([4]) impose l’emploi d’identifiants de clé lors de l’émission de certificats mais la section 4.2.1.2 indique aussi que les applications ne sont pas obligées de vérifier les identifiants de clé lors de la validation d’une chaîne de certification. Conclusion ? Il n’y en a pas.

Image certificat : sujet
Fig. 7 : Sujet du certificat
Image certificat : émetteur
Fig. 8 : Émetteur du certificat

Pour signer, l’émetteur utilise sa clé privée. La vérification de la signature est faite avec sa clé publique. Ainsi pour vérifier l’authenticité du certificat https de letsencrypt.org, nous aurons besoin de la clé publique de son émetteur, TrustID Server CA A52.

Ce principe est toujours respecté avec les certificats x509, que ce soit avec RSA ou d’autres mécanismes à clé publique / clé privée.

Nous allons maintenant passer à la vérification de la signature RSA.

3. Vérification de signature RSA

3.1. La signature RSA

Notations
  • La valeur à signer (ou si l’on préfère, le bloc de données à signer) est tbsCertificate, soit le certificat sans les informations de signature. Dans la structure en trois parties de notre certificat x509, c’est la première.

  • L’entité qui signe le certificat (l’émetteur du certificat) a pour clé RSA (n, e) (n est le modulo, e est l’exposant) et d. Le couple (n, e) est la clé publique, d est la clé privée.

La page Wikipédia consacrée au système RSA [5] explique le lien entre (n, e) et d, et nous indique le calcul à effectuer pour chiffrer. Pour signer, le calcul inverse le rôle de l’exposant privé et public, et pour vérifier la signature, le rôle des exposants privé et public est encore inversé (par rapport à la signature).

Dans notre exemple le tbsCertificate est celui de letsencrypt.org, tandis que la clé RSA (clé publique (n, e) et clé privée d) est celle de TrustID Server CA A52.

3.1.1. Calcul de la signature

  1. L’émetteur calcule le hash (noté M) de la valeur tbsCertificate du sujet, soit M = hash("tbsCertificate")

  2. Il calcule la signature [4] [5] (notée S) avec la formule S = Md mod n

3.1.2. Vérification de la signature

  1. Le vérificateur calcule M = Se mod n

  2. Il calcule M' = hash("tbsCertificate")

  3. Si on a l’égalité M = M', la signature est vérifiée

3.2. Vérification du certificat de letsencrypto.org

3.2.1. Choix d’un programme de calcul

Nous avons besoin d’une "calculatrice" qui calcule sur des nombres entiers arbitrairement grands, sans perte de précision. Dans la suite de ce document, c’est bc qui sera utilisé [6].

  • Linux : bc est disponible par défaut sur la plupart des distributions.

  • Windows : les binaires sont accessibles ici [7]. La version standard de bc (GnuWin32) gère mal le clavier français. La référence [7] vous propose un exécutable bc.exe qui n’a pas ce défaut.

Note
Le choix de bc
  • bc est installé par défaut sur la plupart des distributions Linux, et facile et rapide à installer sous Windows (si ce n’est les problèmes de clavier français).

  • bc contient peu de fonctions mathématiques intégrées mais sur Internet on trouve de nombreux scripts qui permettent de l’enrichir considérablement.

    • Dans bc la variable scale définit le nombre de décimales des nombres manipulés. Comme nous ne ferons que des calculs sur des entiers, nous laisserons scale à zéro (pas de partie décimale). Zéro est la valeur par défaut de scale au lancement de bc [6] .

Note
Alternatives à bc
  • sagemath, logiciel mathématique en licence GPL.

  • python, langage de programmation en licence GPL, calcule par défaut sur des entiers de taille arbitrairement grande et convient donc aux calculs que nous allons faire. Beaucoup de tuto sur Internet utilisent python.

  • Logiciels mathématiques propriétaires bien connus.

Table 1. Comparaison entre bc et python
bc python

Saisie d’un entier en hexadécimal

Exécuter au préalable

ibase = 2 * 8 [7]

Exemple :

ibase = 2 * 8

var = ABEF0E0

(Attention les caractères hexadécimaux doivent être en majuscule.)

Saisir l’entier précédé de 0x

Exemple :

>>> var = 0xabef0e0 [8]

Affichage d’entier en hexadécimal

Exécuter au préalable

obase = 2 * 8 [7]

Exemple :

obase = 2 * 8

2 ^ (2 ^ 4) + 1 [9]

10001

Interpoler avec %x

Exemple :

>>> '%x' % (2 ** (2 ** 4) + 1)

'10001'

3.2.2. Enregistrement de la signature sous forme d’entier

  1. Depuis le navigateur, afficher la signature du certificat de letsencrypt.org.

  2. Sélectionner la signature et la copier-coller dans un éditeur de texte.

  3. Supprimer les caractère surnuméraires (enlever les ':' et les sauts de ligne).

  4. Passer les caractères hexadécimaux en majuscule [10].

  5. Ajouter s= devant le nombre, et ajouter une première ligne ibase = 2 * 8.

  6. Enregistrer dans val.b.

Voir figures 9 et 10.

Image signature dans navigateur
Fig. 9 : Signature dans le navigateur
Image signature dans éditeur
Fig. 10 : Fichier val.b

L’instruction ibase = 2 * 8 ordonne à bc de lire les nombres en hexadécimal. ibase = 16 fonctionne aussi, à condition qu’ibase soit égal à 10 (valeur par défaut) au moment d’exécuter ibase = 16. Si ibase est déjà égal à 16 et que l’on exécute ibase = 16, une erreur se produit car bc lit 16 en hexadécimal (soit 22) et cette valeur est interdite.

Note
  1. Avec bc il est impératif de passer les nombres hexadécimaux en majuscule.

  2. bc n’accepte pas les noms de variable qui contiennent des majuscules.

Le navigateur affiche l’exposant de la clé RSA (le nombre noté e tout à l’heure) sous forme décimale, alors que dans le script bc nous l’entrons en hexadécimal. Pour convertir un nombre décimal en hexadécimal, exécuter dans un terminal :

Linux
$ echo "obase=16; 65537" | bc
10001
Windows
$ echo obase=16; 65537 | bc.exe
10001
Passer du texte en majuscule
Linux

Sous Linux, on peut utiliser la ligne de commande, par exemple (nombreuses autres solutions) :

$ tr '[:lower:]' '[:upper:]' < fichier_entrée > fichier_sortie

Un éditeur suffisamment avancé comme vim ou emacs le permet aussi.

Windows

Windows ne dispose pas par défaut d’outil pour passer du texte en majuscule. L’une des solutions est d’installer les utilitaires adéquats avec GNUWin32 ou bien cygwin.

L’éditeur de texte (natif) adapté pour ce type de transformation est notepad++, disponible à cette URL [8].

Note
vim et emacs sont disponibles sous Windows.

3.2.3. Enregistrement de la clé publique sous forme d’entier

Depuis le navigateur :

  1. Sélectionner le certificat de TrustID Server CA A52 et afficher sa clé publique.

  2. Sélectionner la valeur de la clé publique et la copier-coller dans val.b. Il faut le faire en deux fois, une fois pour le modulo de 256 octets (variable n) et une fois pour l’exposant (variable e).

Ne pas oublier de passer les caractères hexadécimaux en majuscule.

Image clé dans navigateur
Fig. 11 : Clé publique dans le navigateur

A l’arrivée, val.b contient trois variables, s (la signature du certificat), n et e (la clé publique). On a ajouté la sauvegarde et la récupération d'ibase, c’est une bonne pratique.

val.b
save_ibase=ibase
ibase=2*8
s=8049A7CE9627701FC4E520876B97271A8AEF34D13A5ECA776172BD7C9053DBEF9C8504E4C85629135D934D1F9C6FB09375189812B3475D5F0797F5D32BC9B11B12BC29733DCD40E57EB97BC819F21939764A4F2A270036906BAE5FD280D68DCC16428C0FCD3D213025BCFA10A6697529ED1A168E0D2CEFCB24A9C9A64C85F0BF8942B91F2CD1E92989F73EF9F2267BAB5535C3388C10C3C1D55DBC3A50A01A77CEDED612862D83A9B1A68A08B68DC35BE0F2E23E3BD9AFD4C0BA1537CFD694A5AF5D6CF8887861A9DCB89B9DE35AD3F255C251B0ECD54C2CF693DD5732EDF33939334BDB1E64C29636E0502E57914984BDA74C7E05AC948403D2BEBE051452F8
n=9769D7999885023FE9264276E8F4733FA932442690782E78579119A05D762B49F9935A5D5ACE82F3C2D8E54C367A2B1D0DDBA6A7FE91127CED7201B78CA1C5DACC9DFE09FB57E214470FE89E918F942D8032939303F5287868BA7E0F42B4317A0514225333E4A3AD6C8FAFBE636BB2329FD917B9C9E0607C99D631E1E4A0B73FAFB232AC7E8C9CDC02EBE1BC1F149CBC91F7B2FB42F3E1202BCBBF8FF3B37063FAF7752802ABC5D4B0EDEA257F87CD371496833C40021BA09E19477FF3B0CCC52560B83512F151EB17DCFC5BA5D99BEF404CD77771E9FB458B7EF2E369B042661746903ACD463DF1B0096FDCFFEE3361CAFCC72E3CED5E0AD1BF221269804B23
e=10001
ibase=save_ibase

3.2.4. La fonction powmod

Les amateurs de python ont encore un avantage à ce stade. L’équivalent de la fonction powmod y est disponible sous forme d’un troisième paramètre (facultatif) à la fonction pow.

Pour ceux qui utilisent bc comme moi, il faut écrire la fonction.

La fonction powmod met en oeuvre l’algorithme d’exponentiation rapide, décrit à cette URL [9]. En fait nous sommes dans un contexte modulaire et d’après Wikipédia le nom exact de l’algorithme est exponentiation modulaire. Un article y est consacrée [10]. Les deux algorithmes font appel au même principe, mais le second exploite le contexte modulaire pour que les nombres manipulés n’atteignent pas une taille démesurée. C’est le second algorithme (exponentiation modulaire) dont nous avons besoin pour la suite.

Sur Internet, on peut trouver la fonction powmod dans de nombreux scripts bc à télécharger. À noter qu’elle porte parfois d’autres noms, mpower par exemple.

powmod.b
define powmod(a, b, c) {
	auto p, r
	p = a
	r = 1
	while (b > 0) {
		if (b % 2) r = (r * p) % c
		p = (p * p) % c
		b /= 2
	}
	return r
}

3.2.5. Calcul de M

Nous voilà prêts pour calculer M.

  1. Lancer la commande suivante [11] :

$ BC_LINE_LENGTH=0 bc powmod.b val.b
  1. Dans le shell bc, exécuter [7] (pour que les nombres soient affichés en hexadécimal)

obase=2*8
  1. Toujours dans le shell bc, exécuter

powmod(s, e, n)

Rappelons que c’est S (variable s dans val.b) qui doit être élevé à la puissance e, modulo n.

Image résultat powmod
Fig. 12 : Calcul pour vérifier la signature RSA
Important
Si vous exécutez obase = 16, vous obtiendrez le résultat voulu (obase défini à 16 décimal) seulement si ibase vaut 10. Pour parer à toute éventualité, le plus simple est d’utiliser 2 * 8 comme ici (ou bien 2 ^ 4, ou quoi que ce soit qui n’utilise que des nombres à un seul chiffre).

Le résultat (figure 12) avec tous ces F prouve avec une quasi certitude que le calcul s’est bien passé. Les F correspondent au 'padding' standard effectué pour une signature RSA, la valeur qui suit (à partir de 303130) est le hash de tbsCertificate "emballé".

"Emballé", c’est-à-dire ? La valeur est spécifiée en ASN.1 et codée en DER, et elle contient d’autres informations que le seul hash de tbsCertificate.

C’est ce que nous allons voir dans le chapitre suivant.

3.2.6. Analyse de M

Nous allons procéder en trois étapes :

  1. Enregistrement du contenu hexadécimal

  2. Conversion du contenu hexadécimal en binaire

  3. Examen du contenu binaire avec la commande openssl asn1parse

1 Enregistrement du contenu hexadécimal

Faisons un copier-coller de M (en hexadécimal) à partir de l’octet qui suit l’octet nul, et enregistrons le résultat dans le fichier m.hex.

Image m.hex
Fig. 13 : m.hex
Contenu de m.hex
3031300D0609608648016503040201050004208364DA78F1FD8DCC6812E568268BF2DAF8791BE383109745388879C496A8C3DD
2 Conversion du contenu hexadécimal en binaire

Maintenant nous allons convertir m.hex en binaire, puisque le contenu actuel est le codage des octets en hexadécimal de la signature, ce n’est pas la signature elle-même.

Linux

Exécuter la commande

$ xxd -r -p m.hex > m.der
Windows

Le plus simple est d’utiliser notepad++ et d’enregistrer le fichier transformé avec le nom m.der.

Image notepad++ 1
Fig. 14 : Avant la conversion hexadécimal -> binaire