Un brin de réseau

Ce blog propose des articles sur les technologies réseaux et leur utilisation, le tout illustré avec des maquettes et des captures.

Python freeradius-api Python diffplus

Chiffrement et signature RSA

Cet article survole les mathématiques du cryptosystème RSA, propose dans un but pédagogique une implémentation en Python du textbook RSA, souligne la différence entre chiffrer et signer, et termine par la notion de schémas de chiffrement et de signature.

En particulier, nous nous concentrons sur la signature ainsi que l'une de ses applications, la signature-based authentication—sujet de l'article suivant qui illustrera le propos avec les protocoles SSH, TLS et IKE.

Tel un exercice, l'objectif final de cette série d'articles sur RSA est de retrouver, par le calcul, la signature d'une CSR (Certificate Signing Request) générée avec OpenSSL et de vérifier, par le calcul également, la signature d'un certificat SSL existant, celui de Twitch en l'occurrence.

Les mathématiques de RSA

Nous n'étudierons pas (trop) en détail le cryptosystème RSA, chose qui relève des mathématiques et, plus précisément, de la cryptologie. Des ouvrages existent sur le sujet pour en comprendre les fondements, notamment le problème difficile de la factorisation, et en découvrir les attaques.

Il s'agit de voir les « formules » bien connues de RSA—nous parlons plutôt de « primitives » cryptographiques—et d'illustrer sa magie en Python, tout en soulignant la différence entre chiffrer et signer. Pour autant, les lecteurs habitués de ce blog savent que je ne me contente pas d'énumérer des éléments mais que je m'efforce d'expliquer, dans la mesure du possible, le pourquoi des choses et de citer des sources considérées sûres.

Enfin, si nous nous amusons à analyser et reproduire des calculs tout au long de cette série d'articles sur RSA, l'objectif n'est bien sûr en aucun cas de réinventer ce qu'offrent les libs spécialisées mais de sentir comment elles fonctionnent.

Notion de textbook RSA

Cette section se concentre sur le textbook RSA, souvent traduit par RSA naïf, et que je traduirais par celui des « manuels scolaires ». En effet, les primitives cryptographiques des calculs à venir travaillent sur \(M\) directement, le message à chiffrer ou à signer.

Or, dans les implémentations réelles, elles ne travaillent pas sur \(M\) directement mais sur une version modifiée appelée \(EM\) (Encoded Message). Cette dernière est le fruit d'opérations appliquées sur \(M\), notamment de hashing et/ou de padding, afin de se prémunir contre des faiblesses intrinsèques au textbook RSA—la littérature évoque le problème de malléabilité—et contre des attaques. Nous introduirons en fin d'article le concept des méthodes d'encodage, qui construisent \(EM\), dans la section dédiée aux schémas de chiffrement et de signature.

Rappel des paramètres de RSA

Nous disons que \(n\) est le module de chiffrement, \(e\) l'exposant de chiffrement et \(d\) l'exposant de déchiffrement.

Je propose ci-dessous un exemple de génération de tous ces paramètres en Python qui s'appuie sur PyCryptodome. J'apporterai plus loin des détails sur la taille de la clé qui est ici de 64 bits.


    from Crypto.Util.number import getPrime
    from math import gcd

    p = getPrime(32)
    q = getPrime(32)
    assert p != q

    n = p * q
    assert n.bit_length() == 64

    phi = (p - 1) * (q - 1)
    e = 65537
    assert gcd(e, phi) == 1

    d = pow(e, -1, phi)

    print(f"p = ({p.bit_length()} bits) {p}")
    print(f"q = ({q.bit_length()} bits) {q}")
    print(f"n = ({n.bit_length()} bits) {n}")
    print(f"phi = {phi}")
    print(f"e = {e}")
    print(f"d = {d}")
    

    p = (32 bits) 3435686489
    q = (32 bits) 3947406643
    n = (64 bits) 13562051669943946427
    phi = 13562051662560853296
    e = 65537
    d = 11641673259085492529

Dans la pratique, \(e = 65537\), un nombre premier de Fermat (s'écrivant sous la forme \(2^{16} + 1\)). Nous retiendrons, en termes simples, qu'une telle valeur apporte un bon compromis entre sécurité et efficacité de calcul. En effet, les articles spécialisés mettent en avant qu'elle est suffisamment grande pour se prémunir contre certaines attaques et que, en raison de sa représentation binaire particulière, à savoir \(10000000000000001\), elle allège le calcul de l'exponentiation modulaire rapide, notamment utilisé dans le chiffrement d'un message et la vérification d'une signature (où \(e\) fait partie du calcul).

Paire de clés

Ces paramètres engendrent une paire de clés ou key pair :

Je ne l'expliquerais pas mieux que Jean-Philippe Aumasson dans son livre :

Une de ces clés est votre clé publique, qui peut être utilisée par quiconque pour chiffrer des messages que seulement vous pourrez déchiffrer à l'aide de votre clé privée. […] Outre le chiffrement, RSA peut également créer des signatures. Dans ce cas, les rôles sont inversés : le détenteur de la clé privée est le seul à pouvoir signer un message, et la clé publique permet à quiconque de vérifier la validité d'une signature.

La cryptographie appliquée, par Jean-Philippe Aumasson

Nous parlons de cryptographie asymétrique—de chiffrement à clé publique ou encore de signature à clé publique—par opposition à la cryptographie symétrique où la même clé (secrète) sert à chiffrer et déchiffrer.

Taille de la clé

Générer une clé RSA de 64 bits signifie que le codage en binaire du module de chiffrement \(n\) requiert 64 bits, avec \(p\) et \(q\) codés sur 32 bits chacun. Par exemple : 


    from Crypto.Util.number import getPrime

    # générer deux nombres premiers distincts p et q (sur 32 bits chacun)
    p = getPrime(32)
    q = getPrime(32)
    assert p != q
    print(f"p = ({p.bit_length()} bits) {p}")
    print(f"q = ({q.bit_length()} bits) {q}")

    # calculer le module de chiffrement n (résultat sur 64 bits)
    n = p * q
    print(f"n = ({n.bit_length()} bits) {n}")
    

    p = (32 bits) 3930794773
    q = (32 bits) 2843237939
    n = (64 bits) 11176184829016492847

Le résultat \(n\) est bien codé sur 64 bits. En réalité, le produit \(p \times q\) peut également donner un résultat \(n\) sur 63 bits :


    p = (32 bits) 2441722141
    q = (32 bits) 3338835559
    n = (63 bits) 8152508709568411819

Plus généralement, avec \(p\) et \(q\) codés sur \(N/2\) bits, le résultat de leur produit peut donner un \(n\) codé sur \(N\) ou \(N - 1\) bits. Afin d'atteindre la taille de la clé demandée, nous pouvons imaginer que les libs régénèrent \(p\) et \(q\) jusqu'à ce que leur produit soit effectivement codé sur \(N\) bits. Le code source de PyCryptodome le montre d'ailleurs assez bien dans RSA.py#L498 : 


    while n.size_in_bits() != bits and d < (1 << (bits // 2)):
        # Generate the prime factors of n: p and q.
        # By construciton, their product is always
        # 2^{bits-1} < p*q < 2^bits.
        p = generate_probable_prime(...)
        q = generate_probable_prime(...)
        # (...)
        n = p * q

Tant que la taille de \(n\) en bits ne vaut pas bits, l'algorithme régénère les nombres \(p\) et \(q\) et réévalue leur produit.

Dans la vraie vie

J'ai généré jusqu'alors, pour alléger les outputs, des clés volontairement petites de 64 bits, insuffisantes pour une utilisation réelle. En effet, un module \(n\) sur 64 bits se factorise facilement avec un outil tel que factordb qui retrouve rapidement, pour \(n = 11176184829016492847\), ses deux facteurs premiers \(p = 3930794773\) et \(q = 2843237939\). Connaissant \(e\) (clé publique), nous retrouvons \(d\) (clé privée).

La sécurité de RSA repose essentiellement sur la difficulté à factoriser un grand nombre \(n\) en ses deux facteurs premiers \(p\) et \(q\)—la littérature parle d'integer factorization cryptography ou IFC, catégorie de cryptosystèmes dans laquelle rentre RSA mais aussi Rabin. Et par « grand nombre » est entendu un nombre codé sur au moins 2048 bits, comme recommandé par le NIST à l'heure où j'écris ces lignes, ce qui donne un nombre à 617 chiffres comme :


    n =  22 821 144 296 413 405 905 844 194 467 082 279 220 234 406
        910 911 888 778 860 582 679 889 058 814 100 539 598 724 255
        562 839 421 635 067 394 810 223 055 292 033 710 361 363 001
        920 941 331 649 084 717 120 880 006 977 644 673 582 355 371
        098 720 421 686 154 945 983 102 095 986 776 327 721 867 467
        774 220 385 251 456 017 844 743 843 085 127 772 418 073 509
        924 399 149 735 745 190 426 340 483 694 237 486 082 944 098
        819 761 928 242 542 542 729 703 152 523 423 671 901 706 934
        330 324 693 101 338 585 044 971 021 533 399 760 436 611 071
        882 335 717 054 806 429 367 255 308 520 684 946 752 379 317
        870 809 165 901 967 419 967 982 892 886 769 083 258 432 393
        488 347 925 854 320 940 374 148 121 309 528 568 986 120 286
        124 618 152 193 210 331 100 570 510 814 735 537 812 434 664
        796 955 252 643 277 049 943 767 556 453 141

Plus généralement, outre la taille de \(n\), et comme expliqué pour \(e = 65537\), les valeurs des paramètres de RSA ne sont pas choisies arbitrairement et n'ont pas toutes la même « qualité » :

\(n\) is the modulus and product of two prime numbers, \(p\) and \(q\). The security of IFC depends on the quality and secrecy of these primes and the private exponent \(d\).

FIPS 186-5 (Digital Signature Standard)

Le standard que je viens de citer recense ainsi des critères de sélection dans son paragraphe Criteria for IFC Key Pairs. Inutile pour nous ici de rentrer dans davantage de considérations mathématiques : retenons que les valeurs des paramètres n'apportent pas toutes le même niveau de sécurité, et que nous pouvons en théorie faire confiance aux outils spécialisés, comme OpenSSL, pour générer une paire de clés de « qualité ».

Chiffrer versus signer

Comme introduit avec la citation du livre de Jean-Philippe Aumasson et en termes clairs :

Chiffrement-déchiffrement

Pour chiffrer un message \(M\) en ciphertext \(C\) :

\[C \equiv M^e \pmod n\]

Déchiffrer un ciphertext \(C\) en message \(M\) :

\[M \equiv C^d \pmod n\]
Signature-vérification

Calculer la signature \(S\) d'un message \(M\) :

\[S \equiv M^d \pmod n\]

Vérifier la signature \(S\) d'un message \(M\) :

\[M' \equiv S^e \pmod n\]

La signature est vérifiée si \(M' = M\).

Intérêts du chiffrement et de la signature

Intérêt du chiffrement asymétrique

L'intérêt du chiffrement RSA se comprend assez intuitivement : envoyer un message chiffré que seul le détenteur de la clé privée peut déchiffrer. Cependant, il s'avère peu performant en pratique sur un large volume de données, contrairement au chiffrement symétrique, comme AES, conçu justement pour cette tâche. J'aime bien l'explication suivante :

What asymmetric encryption achieves is no trivial feat. The possibility to reveal the public key while not saying too much about the private key, but such that both keys work together […] requires a lot of mathematics! RSA is full of mathematics. This contrasts with symmetric encryption algorithms which are “just” ways to make a big mess of data by mixing bits together.

https://security.stackexchange.com/a/9265

Le chiffrement asymétrique se combine souvent au chiffrement symétrique, ce qui engendre un cryptosystème dit hybride : RSA sert à chiffrer une petite quantité de données, à savoir une clé secrète ensuite utilisée pour le chiffrement symétrique. C'était le cas dans TLS 1.2 (RFC 5246) :


    If RSA is being used for key agreement and authentication, the
    client generates a 48-byte premaster secret, encrypts it using the
    public key from the server's certificate, and sends the result in
    an encrypted premaster secret message.

Cela dit, afin de changer régulièrement la clé publique, et ainsi atteindre la PFS (Perfect Forward Secrecy), l'échange de clé DH (Diffie-Hellman) remplace aujourd'hui souvent RSA :


    With RSA, key exchange and server authentication are combined.  The
    public key is contained in the server's certificate.  Note that
    compromise of the server's static RSA key results in a loss of
    confidentiality for all sessions protected under that static key.
    TLS users desiring Perfect Forward Secrecy should use DHE cipher
    suites.  […] Additionally, using a fresh key for each handshake
    provides Perfect Forward Secrecy.

Intérêt de la signature

L'intérêt de la signature RSA, toujours très répandue, se veut lui moins intuitif. Le FIPS 186-5 dit :


    Digital signatures are used to detect unauthorized modifications and
    to authenticate the identity of the signatory. In addition, the recipient of
    signed data can use a digital signature as evidence in demonstrating to a
    third party that the signature was, in fact, generated by the claimed signatory.
    This is known as non-repudiation since the signatory cannot easily repudiate
    the signature at a later time.

Autrement dit, la signature sert notamment à garantir l'intégrité d'un message et à authentifier un hôte auprès d'un autre, méthode connue sous le nom de signature-based authentication—qui fait souvent d'une pierre deux coups, authentification et intégrité, comme mentionné explicitement par la RFC 8446 de TLS 1.3 sur laquelle nous reviendrons dans l'article suivant :


    This message is used to provide explicit proof that an endpoint
    possesses the private key corresponding to its certificate.  The
    CertificateVerify message also provides integrity for the handshake
    up to this point.  Servers MUST send this message when authenticating
    via a certificate.

Enfin, l'extrait parle aussi de la notion de non-répudiation (hors périmètre de cet article), c'est-à-dire l'impossibilité pour l'auteur d'un message de nier en être l'origine, en raison de la signature qu'il a calculée avec sa clé privée, que seul lui possède en théorie, puis apposée.

Implémentation en Python du textbook RSA

Primitives cryptographiques

Au lieu de « formules », la RFC 8017, sur laquelle nous nous appuierons beaucoup, parle plus justement de « primitives » cryptographiques :

Afin de préparer le terrain, pour quand nous verrons les schémas de chiffrement et de signature, je vais utiliser dans le code les noms de primitive ci-dessus. À quelques détails d'implémentation près par rapport à la RFC, je propose donc les fonctions suivantes :


    # encryption and decryption primitives

    def RSAEP(n: int, e: int, m: int) -> int:
        return pow(m, e, n)  # m^e mod n

    def RSADP(n: int, d: int, c: int) -> int:
        return pow(c, d, n)  # c^d mod n
    

    # signature and verification primitives

    def RSASP1(n: int, d: int, m: int) -> int:
        return pow(m, d, n)  # m^d mod n

    def RSAVP1(n: int, e: int, s: int) -> int:
        return pow(s, e, n)  # s^e mod n
La contrainte de \(m \lt n\)

La RFC mentionne en effet cette contrainte, et ce, car les calculs travaillent modulo \(n\). J'illustre pourquoi avec les petites valeurs suivantes (clé de 8 bits) :


    p = (4 bits) 11
    q = (4 bits) 13
    n = (8 bits) 143
    phi = 120
    e = 17
    d = 113

Admettons que \(m = 145\), supérieur à \(n\) donc. Côté chiffrement, nous avons :

\[c \equiv m^e \pmod n\ \equiv \textcolor{green}{145}^{17} \pmod {143}\ \equiv \textcolor{green}2^{17} \pmod {143} \equiv 84 \pmod {143}\]

Et ce, car \(145\) se réduit à \(2 \pmod {143}\). Côté déchiffrement, nous avons :

\[m \equiv c^d \pmod n \equiv 84^{113} \pmod {143} \equiv \textcolor{green}2 \pmod {143}\]

Primitives de conversion de données

Une question se pose déjà à ce stade. Les primitives cryptographiques opèrent sur des entiers (type int en Python). Or, dans les formules bien connues que j'ai données et souvent présentées telles quelles, si nous prenons celle du chiffrement (ou de la signature), elle prend \(M\) en entrée, c'est-à-dire le message à chiffrer (ou à signer), que nous imaginons assez naturellement être du texte—dans le textbook RSA tout du moins. Or, le calcul s'effectue bien évidemment sur des nombres et non du texte. Comment convertir \(M\) en entier \(m\) ?

En pratique, \(M\) est de type octet-string, littéralement chaîne d'octets (type bytes en Python), représentable en hexadécimal pour en obtenir une version un peu plus lisible humainement, et qu'il convient de convertir en entier \(m\) pour le calcul.

Chaîne d'octets, concrètement

Prenons par exemple une chaîne de cinq octets, chacun exprimé en décimal :


    M = bytes([72, 101, 108, 108, 111])

Nous aurions aussi pu l'écrire avec la représentation hexadécimale ou binaire de chaque octet :


    M = bytes([0x48, 0x65, 0x6c, 0x6c, 0x6f])
    M = bytes([0b01001000, 0b01100101, 0b01101100, 0b01101100, 0b01101111])

Cette chaîne d'octets se veut plus humainement lisible ainsi (en concaténant la représentation hexadécimale de chaque octet la constituant) :


    print(M.hex())
    # 48656c6c6f

Pour convertir la chaîne d'octets en entier :


    print(int.from_bytes(M, byteorder="big"))
    # 310939249775

Pour faire l'inverse (convertir un entier en chaîne d'octets) :


    m = 310939249775
    M = int.to_bytes(m, byteorder="big", length=(m.bit_length() + 7) // 8)
    print(M.hex())
    # 48656c6c6f

Le paramètre length prend la taille de l'entier en octets. Le calcul pour l'obtenir :


    m = 310939249775
    print(m.bit_length())
    # 39
    print((m.bit_length() + 7) // 8)
    # 5

L'entier \(m\) est ici codé sur 39 bits soit 5 octets.

Enfin, il s'avère que je n'ai pas pris cette chaîne d'octets par hasard. Comme ce sera le cas dans notre exemple de textbook RSA, elle est issue de l'encodage ASCII du texte suivant :


    T = "Hello"
    M = T.encode(encoding="ascii")

    print(type(M))
    # <class 'bytes'>

    print(M.hex())
    # 48656c6c6f

    print(M.decode(encoding="ascii"))
    # Hello
Retour à la RFC

Elle utilise les notations suivantes :


    M     message, an octet string
    C     ciphertext, an octet string
    S     signature, an octet string

    m     message representative, an integer between 0 and n-1
    c     ciphertext representative, an integer between 0 and n-1
    s     signature representative, an integer between 0 and n-1

Afin de convertir un octet-string en entier (et inversement), elle définit les primitives :

De nouveau, j'emprunte volontairement ces noms de primitive pour les fonctions afin de préparer le terrain pour quand nous verrons les schémas de chiffrement et de signature :


    def OS2IP(octet_string: bytes) -> int:
        return int.from_bytes(octet_string, byteorder="big")

    def I2OSP(i: int) -> bytes:
        return int.to_bytes(i, byteorder="big", length=(i.bit_length() + 7) // 8)

Exemple d'utilisation :


    T = "Hello"
    print("T =", T)

    M = T.encode(encoding="ascii")
    print("M = T.encode =", M.hex())

    m = OS2IP(M)
    print("m = OS2IP(M) =", m)

    M = I2OSP(m)
    print("M = I2OSP(m) =", M.hex())

    T = M.decode(encoding="ascii")
    print("T = M.decode =", T)
    

    T = Hello
    M = T.encode = 48656c6c6f
    m = OS2IP(M) = 310939249775
    M = I2OSP(m) = 48656c6c6f
    T = M.decode = Hello

\(M\) est de type octet-string ou bytes en Python, dont la valeur est ici issue de l'encodage ASCII du texte \(T\). On affiche sa représentation hexadécimale 48656c6c6f convertie en entier avec la primitive \(\text{OS2IP}\) et inversement avec la primitive \(\text{I2OSP}\).

Chiffrement-déchiffrement

Chiffrement du message \(M\) :


    print(f"n = ({n.bit_length()} bits) {n}")
    print(f"e = {e}")
    print("Will encrypt message using (n, e) public key")
    T = "Hello"
    M = T.encode(encoding="ascii")
    m = OS2IP(M)
    assert m < n
    c = RSAEP(n, e, m)
    C = I2OSP(c)
    print("T =", T)
    print("M =", M.hex())
    print("m = OS2IP(M) =", m)
    print("c = m^e mod n =", c)
    print("C = I2OSP(c) =", C.hex())
    print("Sending ciphertext C =", C.hex())
    

    n = (64 bits) 13125801996593161877
    e = 65537
    Will encrypt message using (n, e) public key
    T = Hello
    M = 48656c6c6f
    m = OS2IP(M) = 310939249775
    c = m^e mod n = 7436180272767880705
    C = I2OSP(c) = 67329e8f3c18ce01
    Sending ciphertext C = 67329e8f3c18ce01

Déchiffrement du ciphertext \(C\) :


    print("Received ciphertext C =", C.hex())
    print(f"n = ({n.bit_length()} bits) {n}")
    print(f"d = {d}")
    print("Will decrypt message using (n, d) private key")
    c = OS2IP(C)
    m = RSADP(n, d, c)
    M = I2OSP(m)
    T = M.decode(encoding="ascii")
    print("c = OS2IP(C) =", c)
    print("m = c^d mod n =", m)
    print("M =", M.hex())
    print("T =", T)
    

    Received ciphertext C = 67329e8f3c18ce01
    n = (64 bits) 13125801996593161877
    d = 7997211856385085113
    Will decrypt message using (n, d) private key
    c = OS2IP(C) = 7436180272767880705
    m = c^d mod n = 310939249775
    M = 48656c6c6f
    T = Hello

Constat : nous retrouvons bien le message \(M\) depuis le ciphertext \(C\).

En orchestrant ainsi les appels aux primitives cryptographiques et celles de conversion de données, nous nous approchons de la notion de schémas de chiffrement ou encryption schemes.

L'article se concentrant sur la signature et sa vérification, nous ne développerons pas davantage le chiffrement-déchiffrement.

Signature-vérification

Calcul de la signature \(S\) du message \(M\) :


    print(f"n = ({n.bit_length()} bits) {n}")
    print(f"d = {d}")
    print("Will sign message using (n, d) private key")
    T = "Hello"
    M = T.encode(encoding="ascii")
    m = OS2IP(M)
    assert m < n
    s = RSASP1(n, d, m)
    S = I2OSP(s)
    print("T =", T)
    print("M =", M.hex())
    print("m = OS2IP(M) =", m)
    print("s = m^d mod n =", s)
    print("S = I2OSP(s) =", S.hex())
    print(f"Sending signature S = {S.hex()} along with message M = {M.hex()}")
    

    n = (64 bits) 13125801996593161877
    d = 7997211856385085113
    Will sign message using (n, d) private key
    T = Hello
    M = 48656c6c6f
    m = OS2IP(M) = 310939249775
    s = m^d mod n = 3527520017897905948
    S = I2OSP(s) = 30f444c444e25f1c
    Sending signature S = 30f444c444e25f1c along with message M = 48656c6c6f

Vérification de la signature \(S\) du message \(M\) :


    print(f"Received signature S = {S.hex()} with message M = {M.hex()}")
    print(f"n = ({n.bit_length()} bits) {n}")
    print(f"e = {e}")
    print("Will verify signature using (n, e) public key")
    s = OS2IP(S)
    m_prime = RSAVP1(n, e, s)
    M_prime = I2OSP(m_prime)
    print("s = OS2IP(S) =", s)
    print("m_prime = s^e mod n =", m_prime)
    print("M_prime = I2OSP(m_prime) =", M_prime.hex())
    print(f"Does M_prime={M_prime.hex()} equal M={M.hex()}?")
    assert M_prime == M
    print("Yes, signature is valid!")
    

    Received signature S = 30f444c444e25f1c with message M = 48656c6c6f
    n = (64 bits) 13125801996593161877
    e = 65537
    Will verify signature using (n, e) public key
    s = OS2IP(S) = 3527520017897905948
    m_prime = s^e mod n = 310939249775
    M_prime = I2OSP(m_prime) = 48656c6c6f
    Does M_prime=48656c6c6f equal M=48656c6c6f?
    Yes, signature is valid!

Constat : le \(M'\) calculé depuis la signature est égal au \(M\) initial \(\implies\) la signature est vérifiée.

En orchestrant ainsi les appels aux primitives cryptographiques et celles de conversion de données, nous nous approchons de la notion de schémas de signature ou signature schemes.

Nous verrons dans les autres parties de l'article, en particulier dans le contexte de la signature d'une CSR et d'un certificat, à quoi correspond concrètement \(M\).

Méthodes d'encodage et schémas de signature

Dans les implémentations réelles, contrairement au textbook RSA, les primitives cryptographiques ne travaillent pas sur le message \(M\) directement mais sur une version modifiée appelée \(EM\) (Encoded Message).

Dans le monde IETF, la RFC 8017 démystifie la chose avec une terminologie précise, bien définie, et m'a aidé à mieux appréhender les différents termes existants, en particulier ceux de encoding methods et de signature schemes. Je propose un bref résumé.

Elle se présente comme apportant des recommandations sur l'implémentation de RSA :


    This document provides recommendations for the implementation of
    public-key cryptography based on the RSA algorithm, covering
    cryptographic primitives, encryption schemes, signature schemes with
    appendix, and ASN.1 syntax for representing keys and for identifying
    the schemes.

Elle définit les primitives cryptographiques suivantes que nous connaissons déjà à ce stade :

Ainsi que les primitives de conversion de données suivantes que nous connaissons aussi :

Nous avons en effet déjà illustré ces primitives dans l'implémentation Python, justement afin de préparer le terrain pour cette section, qui devrait donc être assez simple à comprendre.

Méthodes d'encodage

La version modifiée de \(M\) sur laquelle les primitives cryptographiques opèrent est appelée \(EM\) (Encoded Message). Elle résulte de l'appel à une méthode d'encodage pouvant être de type :

Concernant le deuxième type, le document parle plus spécifiquement des EMSA (EMS with Appendix) qui se distinguent des EMSR (EMS with message Recovery), l'expression with appendix signifiant que la vérification de la signature se fait avec le message sur lequel a porté le calcul :


    To verify a signature constructed with this type of scheme, it is
    necessary to have the message itself.  In this way, signature schemes
    with appendix are distinguished from signature schemes with message
    recovery, which are not supported in this document.

Ces méthodes d'encodage, en particulier les EMSA qui nous intéressent dans cette série d'articles dédiée aux signatures, appliquent sur \(M\) du hashing et du padding pour construire \(EM\). Le document distingue deux EMSA :


    Two encoding methods for signatures with appendix are employed in the
    signature schemes and are specified here: EMSA-PSS and
    EMSA-PKCS1-v1_5.

Sachant que la transition vers \(\text{EMSA-PSS}\) est encouragée :


           […] Moreover, while no attack is known against the
    EMSA-PKCS-v1_5 encoding method, a gradual transition to EMSA-PSS is
    recommended as a precaution against future developments.

Et ce, car la méthode \(\text{EMSA-PSS}\) est considérée plus sûre. En cherchant dans la littérature à notre dispostion, et sans trop rentrer dans des considérations mathématiques, nous comprenons que cette méthode possède en effet, contrairement à sa concurrente, une « preuve de sécurité » dans le ROM (Random Oracle Model), comme le mentionne l'article Optimal security proofs for PSS and other signatures schemes de Jean-Sébastien Coron :


    The Probabilistic Signature Scheme (PSS) designed by Bellare and Rogaway
    is a signature scheme provably secure against chosen message attacks in
    the random oracle model, […]

La définition de ROM qui, comme son nom l'indique, a à voir avec l'aléatoire, est aussi rappelée :


    The random oracle model, introduced by Bellare and Rogaway in [1],
    is a theoretical framework allowing to prove the security of hash-and-sign
    signature schemes. In this model, the hash function is seen as an
    oracle which outputs a random value for each new query.

En effet, la méthode \(\text{EMSA-PSS}\), dite non-déterministe, introduit de l'aléatoire dans la construction de \(EM\) : le calcul de la signature de \(M\) avec la même clé privée donnera une valeur toujours différente. Au contraire, la méthode \(\text{EMSA-PKCS-v1\_5}\), dite déterministe, produira toujours la même signature pour le même message et la même clé privée. Cette page dresse une comparaison plus détaillée.

Pour autant, nous illustrerons en détail la méthode \(\text{EMSA-PKCS-v1\_5}\), encore très répandue, qui simplifiera nos calculs pour l'exercice—déjà compliqué quand on débute dans la cryptographie. À titre d'exemple, quand j'écris ces lignes, le certificat de Twitch emploie cette méthode et l'exercice de la dernière partie portera justement sur la vérification de sa signature.

Noter que SSH emploie aussi la méthode \(\text{EMSA-PKCS-v1\_5}\) comme l'explique sa RFC 8332 :


    This document prescribes RSASSA-PKCS1-v1_5 signature padding because:

    (1)  RSASSA-PSS is not universally available to all implementations;
    (2)  PKCS #1 v1.5 is widely supported in existing SSH
        implementations;
    (3)  PKCS #1 v1.5 is not known to be insecure for use in this scheme.

L'extrait cité parle de \(\text{RSASSA-PKCS1-v1\_5}\), le nom du schéma de signature associé, ce qui nous mène à la prochaine section.

Schémas de signature

Le document définit encryption schemes et signature schemes ainsi :


    A scheme combines cryptographic primitives and other techniques to
    achieve a particular security goal.  Two types of scheme are
    specified in this document: encryption schemes and signature schemes
    with appendix.

Un schéma joue en quelque sorte le rôle d'orchestrateur des appels aux primitives (de conversion et cryptographiques) ainsi qu'aux méthodes d'encodage. Associés aux EMSA, les schémas de signature \(\text{RSASSA-PSS}\) et \(\text{RSASSA-PKCS1-v1\_5}\) sont définis—RSASSA signifiant RSA Signature Scheme with Appendix.

Le schéma de signature \(\text{RSASSA-PKCS1-v1\_5}\) définit deux opérations—le calcul de la signature et sa vérification—orchestrant ainsi les appels :


    RSASSA-PKCS1-V1_5-SIGN (K, M)
        EM = EMSA-PKCS1-V1_5-ENCODE (M, k)
        m = OS2IP (EM)
        s = RSASP1 (K, m)
        S = I2OSP (s, k)
        return S
    

    RSASSA-PKCS1-V1_5-VERIFY ((n, e), M, S)
        s = OS2IP (S)
        m = RSAVP1 ((n, e), s)
        EM = I2OSP (m, k)
        EM' = EMSA-PKCS1-V1_5-ENCODE (M, k)
        if EM == EM'
          output "valid signature"
        else
          output "invalid signature"

Nous retrouvons la logique implémentée dans notre exemple avec en plus ici la notion de \(EM\), une version modifiée de \(M\), construite en appelant la méthode d'encodage \(\text{EMSA-PKCS1-v1\_5}\).

Notez que je n'ai volontairement pas cité mot pour mot les algorithmes de la RFC avec leurs détails. Je voulais mettre en évidence la logique haut niveau de chaque opération du schéma.

À titre d'information, PyCryptodome implémente le schéma de signature \(\text{RSASSA-PKCS1-v1\_5}\) dans pkcs1_15.py#L55 pour l'opération de signature :


    # Step 1
    em = _EMSA_PKCS1_V1_5_ENCODE(msg_hash, k)
    # Step 2a (OS2IP)
    em_int = bytes_to_long(em)
    # Step 2b (RSASP1) and Step 2c (I2OSP)
    signature = self._key._decrypt_to_bytes(em_int)

Et dans pkcs1_15.py#L87 pour l'opération de vérification :


    # Step 2a (O2SIP)
    signature_int = bytes_to_long(signature)
    # Step 2b (RSAVP1)
    em_int = self._key._encrypt(signature_int)
    # Step 2c (I2OSP)
    em1 = long_to_bytes(em_int, k)

La logique apparaît ici aussi clairement, en particulier via les commentaires qui reprennent le nom exact des primitives de conversion de données et cryptographiques.

Ouvrons la boîte

Le corps de la fonction EMSA-PKCS1-V1_5-ENCODE montre en premier lieu l'application d'une fonction \(\text{Hash}\) :


    1.  Apply the hash function to the message M to produce a hash
        value H:

           H = Hash(M).

Puis la concaténation d'un \(PS\) (Padding String) qui répète plusieurs fois le motif 0xff :


    4.  Generate an octet string PS consisting of emLen - tLen - 3
        octets with hexadecimal value 0xff.
    5.  Concatenate PS, the DER encoding T, and other padding to form
        the encoded message EM as

           EM = 0x00 || 0x01 || PS || 0x00 || T.

J'ai volontairement omis des étapes dont la construction de \(T\) car inutile de détailler tous les rouages à ce stade.

PyCryptodome implémente cette fonction dans pkcs1_15.py#L142, l'instruction finale montrant bien la construction de \(EM\) :


    return b'\x00\x01' + PS + b'\x00' + digestInfo

Avant-goût de l'exercice

Lorsque nous vérifierons la signature du certificat de Twtich, la répétition de ce motif 0xff apparaîtra clairement dans la valeur calculée de \(EM\) :


    0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
    ffffffffffffffffffffffff003031300d060960864801650304020105000420
    1d899762a2e59e9e9ceac4bbd5f0803337334e89be40764722c03d6064f02e42

Concernant le contenu du certificat, une rapide analyse dévoile :


    $ openssl x509 -in twitch.pem -text -noout
    Certificate:
        Data:
            […]
            Issuer: C = BE, O = GlobalSign nv-sa, CN = GlobalSign Atlas R3 DV TLS CA 2025 Q2
            Validity
                Not Before: May  7 21:43:11 2025 GMT
                Not After : Jun  8 21:43:10 2026 GMT
            Subject: CN = twitch.tv
            Subject Public Key Info:
                Public Key Algorithm: rsaEncryption
                    Public-Key: (2048 bit)
                    Modulus:
                        00:e3:b7:70:5e:dc:f3:c9:d1:6a:0d:9a:bc:52:7e:
                        63:cb:91:8d:0d:b4:b8:af:51:6f:fa:6c:bf:3a:f9:
                        06:8e:6b:94:c1:ec:e1:3d:18:66:78:89:0f:a2:b0:
                        bb:33:25:fe:cc:b0:d7:9f:68:fa:92:4c:46:7d:84:
                        2d:5d:2b:5b:09:fd:07:05:7e:19:25:3f:d2:45:a7:
                        98:29:81:ea:2a:e3:51:85:ac:30:b6:98:92:50:9c:
                        3a:2d:f8:e5:24:cd:95:a4:11:14:bf:b1:7b:d5:c9:
                        04:77:df:bf:c9:7b:1d:23:ee:56:f5:d8:2e:69:db:
                        c4:20:39:b3:d7:cf:d2:45:15:cb:fe:ed:71:38:f0:
                        c4:96:13:a5:48:a2:d7:3c:cb:92:a5:97:69:80:21:
                        05:9f:cc:e1:f0:bc:a9:09:cb:76:89:18:08:3a:20:
                        6a:f8:15:87:12:ad:4f:9b:44:46:14:4e:ae:ab:86:
                        9a:5a:cc:df:35:98:d1:45:09:ea:9d:ea:24:3d:f6:
                        61:d7:df:43:25:71:4c:f6:27:67:3a:35:33:19:35:
                        08:f7:af:46:26:c5:34:f6:a9:2c:01:c5:64:13:fc:
                        7a:be:5f:4e:b4:2d:e0:66:80:77:87:a0:d4:3a:95:
                        92:38:2e:f2:7a:0c:26:42:3b:6a:5e:33:bb:c4:ec:
                        14:7f
                    Exponent: 65537 (0x10001)
            X509v3 extensions: […]
        Signature Algorithm: sha256WithRSAEncryption
        Signature Value:
            aa:f8:76:98:22:1e:be:16:51:8c:ac:3d:a3:4b:00:c0:9d:c0:
            6f:8c:49:0d:86:8f:c0:f9:7f:1f:cd:02:67:8a:de:15:80:ec:
            5a:be:12:40:5c:4d:28:38:01:2e:00:4e:79:1a:b8:a1:a6:6f:
            1e:5e:11:0a:07:2c:2b:05:94:8b:9a:92:76:b5:3b:4c:02:1e:
            b1:2c:61:91:96:75:12:6f:17:d8:fc:a2:aa:86:f5:5e:84:62:
            b1:ec:cd:b7:45:f2:82:c0:57:6f:d7:c3:79:51:8a:75:d8:3e:
            89:1b:d5:00:55:ab:28:10:cf:8c:2f:e8:e1:e8:cd:be:19:b1:
            af:48:b1:e4:48:26:d2:cd:d0:66:cf:1b:a0:c8:84:a3:58:e9:
            e5:ac:ad:cf:8c:9e:5f:e9:1e:9a:b4:de:41:26:78:00:8b:5e:
            77:7e:94:21:77:f9:94:e7:c3:e5:51:dc:29:78:88:d2:8e:3f:
            00:ac:14:93:b6:58:c1:09:3d:5b:36:a7:b0:d4:85:fe:ef:25:
            c9:59:f8:a5:e4:38:eb:ff:67:e2:4b:ec:62:38:e4:32:9b:a3:
            1f:26:e2:e2:4c:cf:30:c9:00:10:f0:f9:77:d3:66:4b:48:75:
            cc:9b:f0:c5:50:af:0d:89:7a:23:29:1a:24:78:f4:5f:c2:8e:
            c4:47:c0:de

Le certificat comporte les paramètres RSA décrits dans cet article : la clé publique \((n, e)\) avec le module \(n\) sur 2048 bits et l'exposant \(e = 65537\). La clé privée \(d\) est bien sûr absente. Il comporte aussi la signature à vérifier côté client, calculée et apposée par une CA (Certificate Authority), en l'occurrence GlobalSign.

Enfin, l'algorithme de signature positionné à sha256WithRSAEncryption sous-entend l'utilisation du schéma de signature \(\text{RSASSA-PKCS1-v1\_5}\). Bien que le lien entre les deux noms puisse étonner, la RFC 8017 le stipule explicitement en annexe :


    The object identifier for RSASSA-PKCS1-v1_5 SHALL be one of the
    following.

          Hash algorithm   OID
          ------------------------------------------------------------
          MD2              md2WithRSAEncryption        ::= {pkcs-1 2}
          MD5              md5WithRSAEncryption        ::= {pkcs-1 4}
          SHA-1            sha1WithRSAEncryption       ::= {pkcs-1 5}
          SHA-256          sha224WithRSAEncryption     ::= {pkcs-1 14}
          SHA-256          sha256WithRSAEncryption     ::= {pkcs-1 11}
          SHA-384          sha384WithRSAEncryption     ::= {pkcs-1 12}
          SHA-512          sha512WithRSAEncryption     ::= {pkcs-1 13}
          SHA-512/224      sha512-224WithRSAEncryption ::= {pkcs-1 15}
          SHA-512/256      sha512-256WithRSAEncryption ::= {pkcs-1 16}

Sans surprise, la fonction EMSA-PKCS1-V1_5-ENCODE appliquera ici SHA-256 comme fonction \(\text{Hash}\).

L'article suivant se concentre sur la signature-based authentication, une application de la signature RSA, et en illustre le principe sur les protocoles SSH, TLS et IKE.