Cryptographie asymétrique

Dans cette leçon, nous allons explorer la cryptographie à clé asymétrique, qui constitue la base de nombreuses interactions réseau sécurisées aujourd'hui.

À la fin de cette leçon, nous aurons abordé :

• Ce qu'est la cryptographie à clé asymétrique
• Les usages de la cryptographie à clé asymétrique, notamment l'échange de clés et les signatures numériques
• La sécurité de la cryptographie à clé asymétrique en général
• Des détails supplémentaires sur les algorithmes RSA, DSA et les courbes elliptiques, et leur sécurité
• Des exemples de code Python montrant comment ces algorithmes fonctionnent en pratique
• Les menaces pesant sur ces algorithmes, tant du côté des ordinateurs classiques que quantiques

Introduction à la cryptographie asymétrique

Comme nous l'avons vu dans la leçon précédente, la cryptographie à clé symétrique est très rapide et efficace pour protéger les informations, mais elle présente quelques limitations :

1. À mesure que le nombre de parties souhaitant échanger des informations en toute sécurité augmente, le nombre de clés nécessaires croît de manière combinatoire. Elle ne fournit aucun mécanisme pour distribuer ces clés de façon sécurisée entre expéditeurs et destinataires.
2. Il n'existe aucune disposition pour la non-répudiation. N'importe quelle partie peut déchiffrer ou chiffrer des messages sans moyen de garantir qu'un message a été reçu ou d'où il provient.

La solution à ces deux problèmes est apportée par la cryptographie à clé asymétrique (AKC), également connue sous le nom de cryptographie à clé publique (PKC), qui constitue ainsi une pierre angulaire de la sécurité numérique moderne.

La cryptographie à clé asymétrique (AKC) implique l'utilisation d'une paire de clés — une publique, une privée. Les clés publique et privée sont liées cryptographiquement et généralement créées au même moment en tant que paire de clés via un algorithme mathématique spécialisé. La clé publique, comme son nom l'indique, est destinée à être librement distribuée, tandis que la clé privée est gardée secrète par la partie qui génère la paire de clés. La sécurité des communications utilisant des paires de clés asymétriques est assurée tant que la clé privée reste confidentielle.

Figure 1. Chiffrement à clé asymétrique

L'AKC offre plusieurs fonctions utiles, telles que :

1. Chiffrement et déchiffrement pour assurer la confidentialité des communications.
2. Signatures numériques pour garantir l'authenticité, l'intégrité et la non-répudiation.
3. Échange de clés sécurisé pour faciliter l'utilisation ultérieure de cryptosystèmes symétriques.

Dans les applications modernes, l'AKC est principalement utilisée pour les signatures numériques et l'échange de clés sécurisé. Dans cette leçon, nous présentons ces deux fonctions clés, puis nous abordons plusieurs variantes de protocoles cryptographiques pour ces fonctions.

Échange de clés avec la cryptographie asymétrique

L'un des problèmes fondamentaux en cryptographie est l'échange de clés sécurisé. Par exemple, si deux parties veulent utiliser le chiffrement symétrique, les deux parties ont besoin de la même clé pour chiffrer et déchiffrer les messages. Mais comment échangent-elles la clé en toute sécurité ? La cryptographie à clé asymétrique répond à cela via des mécanismes d'échange de clés interactifs et non interactifs.

Échange de clés interactif

Un protocole d'échange de clés interactif désigne une méthode par laquelle deux parties collaborent pour créer une clé secrète partagée sur un canal de communication non sécurisé. Cette clé secrète partagée peut ensuite être utilisée pour les tâches de chiffrement et de déchiffrement symétriques.

Le plus connu de ces protocoles est l'algorithme Diffie-Hellman (DH), conçu spécifiquement pour faciliter l'échange de clés. Dans ce protocole, chaque partie génère une paire de clés (publique et privée) et diffuse sa clé publique. Chaque partie utilise ensuite sa propre clé privée et la clé publique de l'autre partie pour générer une clé secrète partagée. DH s'appuie sur les principes de l'arithmétique modulaire pour garantir que les deux parties obtiennent le même secret partagé, même si chaque partie n'a accès qu'à la clé publique de l'autre.

Les cryptosystèmes modernes basés sur la cryptographie sur les courbes elliptiques (ECC) étendent ce concept avec l'échange de clés Diffie-Hellman sur courbe elliptique (ECDH). L'ECDH fonctionne de façon similaire au DH mais utilise les propriétés des courbes elliptiques, ce qui donne un système plus sécurisé et plus efficace.

Figure 2. Protocole d'échange de clés

Échange de clés non interactif

Contrairement aux protocoles d'échange de clés comme DH et ECDH, qui sont interactifs et nécessitent des échanges aller-retour pour décider de la clé symétrique, l'AKC offre aussi des moyens non interactifs d'établir une clé secrète partagée. Dans ces schémas, une partie génère une paire de clés (publique et privée) et partage la clé publique avec l'autre partie. Cette seconde partie génère alors une clé symétrique aléatoire, la chiffre avec la clé publique reçue et la renvoie à la première partie. La première partie utilise sa clé privée pour déchiffrer le message reçu, obtenant ainsi la clé symétrique partagée. Ce schéma est non interactif en ce sens que la clé symétrique est déterminée par une partie et simplement communiquée de manière sécurisée à l'autre partie sous forme chiffrée.

Une considération importante dans l'échange de clés non interactif concerne la différence de longueur en bits entre la clé symétrique que les parties souhaitent échanger et les tailles de messages recommandées en AKC. En général, les clés symétriques modernes ont une longueur comprise entre 128 et 256 bits, tandis que les cryptosystèmes à clé asymétrique comme RSA travaillent avec des tailles de messages d'environ 1024 à 4096 bits. Par conséquent, lors de l'utilisation de l'AKC pour transmettre une clé symétrique, celle-ci doit néanmoins être encodée dans un message plus long de 1024 à 4096 bits pour des raisons de sécurité. Cela peut être réalisé via deux approches :

• Échange de clés basé sur le rembourrage : Dans cette approche, la clé symétrique plus courte (128-256 bits) est générée en premier, puis un schéma de rembourrage réversible convenu, tel que OAEP, est utilisé pour l'intégrer dans un message plus long (1024-4096 bits). Ce message plus long est chiffré via l'AKC et diffusé comme texte chiffré. Le destinataire déchiffre d'abord le texte chiffré, puis supprime le rembourrage pour extraire la clé symétrique plus courte.

• Mécanismes d'encapsulation de clés (KEMs) : Avec l'échange de clés basé sur les KEM, un message aléatoire en clair long (1024-4096 bits) est d'abord généré, à partir duquel une clé symétrique plus courte (128-256 bits) peut être extraite via une fonction de dérivation de clé (KDF) convenue. Le texte en clair plus long est chiffré via l'AKC et diffusé au destinataire sous forme de texte chiffré. Le destinataire décode le texte chiffré à l'aide de sa clé privée, puis utilise la KDF pour extraire la clé symétrique plus courte (128-256 bits). Des cryptosystèmes populaires comme RSA, avec leur capacité à chiffrer directement des données, peuvent être utilisés pour implémenter des KEMs.

Figure 3. Mécanisme d'encapsulation de clé

Signatures numériques avec la cryptographie asymétrique

Les signatures numériques sont une autre application puissante de la cryptographie à clé asymétrique. Elles offrent l'authentification, l'intégrité et la non-répudiation, rendues possibles par le fait que dans l'AKC, les entités possèdent des clés privées uniques. L'idée de base des protocoles de signature est que les expéditeurs de messages sécurisés signent numériquement les messages en utilisant leur clé privée unique. Le destinataire vérifie ensuite la signature numérique à l'aide de la clé publique de l'expéditeur. Dans l'AKC, les signatures numériques peuvent être mises en œuvre à l'aide d'algorithmes spécifiquement conçus à cet effet ou à l'aide de cryptosystèmes génériques.

Figure 4. Signatures numériques avec la cryptographie asymétrique

Algorithmes de signature numérique dédiés

Actuellement, la norme de traitement de l'information fédérale américaine (FIPS) pour les signatures numériques est un schéma dédié simplement intitulé l'Algorithme de signature numérique (DSA). De façon assez similaire au protocole Diffie-Hellman, le DSA utilise les propriétés algébriques de l'exponentiation modulaire et des inverses multiplicatifs pour la génération et la vérification des signatures.

L'algorithme de signature numérique sur courbe elliptique (ECDSA) est une variante ECC du DSA, offrant les mêmes fonctionnalités mais avec des clés nettement plus courtes. Cela se traduit par une efficacité accrue, ce qui en fait un choix populaire pour les systèmes avec des contraintes de ressources.

DSA et ECDSA seront illustrés plus en détail par la suite.

Schémas de signature numérique utilisant des cryptosystèmes génériques

En plus des algorithmes dédiés, les signatures numériques peuvent également être générées à l'aide de cryptosystèmes asymétriques génériques, tels que RSA.

RSA, qui sera discuté en détail dans une section ultérieure, exploite également les inverses multiplicatifs modulaires et l'exponentiation modulaire comme opérations fondamentales, mais les combine dans une séquence différente de celle du DSA. Dans RSA, le signataire crée généralement un hachage du message puis chiffre ce hachage avec sa clé privée, créant ainsi la signature numérique. N'importe quelle partie peut alors vérifier cette signature en la déchiffrant avec la clé publique du signataire et en la comparant au message haché.

Applications de la cryptographie asymétrique

La cryptographie à clé asymétrique est omniprésente dans les applications technologiques numériques modernes. Les fonctionnalités de base de l'AKC décrites ci-dessus constituent les briques de construction de nombreux protocoles d'application de plus haut niveau, notamment :

1. Communication sur Internet : La communication sécurisée sur Internet, telle que HTTPS, repose fortement sur la cryptographie à clé asymétrique. Le protocole TLS (Transport Layer Security) et son prédécesseur, SSL (Secure Sockets Layer), utilisent la cryptographie à clé asymétrique lors du processus initial de poignée de main pour établir une clé symétrique, qui est ensuite utilisée pour le reste de la session de communication.

2. Authentification : La cryptographie à clé asymétrique est utilisée pour créer des signatures numériques, permettant à une entité d'authentifier un document ou un message numérique comme provenant d'un expéditeur spécifique. Cela est utilisé dans de nombreux scénarios, de la vérification des mises à jour logicielles aux contrats numériques légalement contraignants.

3. Chiffrement des e-mails : Les protocoles de chiffrement des e-mails tels que PGP (Pretty Good Privacy) et son alternative open source GPG (GNU Privacy Guard) utilisent la cryptographie à clé asymétrique pour garantir que seul le destinataire prévu peut lire le contenu de l'e-mail.

4. Shell sécurisé (SSH) : SSH est un protocole permettant la connexion à distance sécurisée et d'autres services réseau sécurisés sur un réseau non sécurisé. Il utilise la cryptographie à clé asymétrique pour authentifier le serveur auprès du client et, éventuellement, le client auprès du serveur.

5. VPN (réseau privé virtuel) : Le chiffrement à clé asymétrique est utilisé pour établir des connexions sécurisées dans les VPN, garantissant une communication sécurisée sur des réseaux publics.

6. Blockchain et cryptomonnaies : Les technologies blockchain, notamment Bitcoin et Ethereum, utilisent la cryptographie à clé asymétrique. Par exemple, la propriété des bitcoins est établie grâce à des signatures numériques utilisant la cryptographie à clé asymétrique.

7. Autorités de certification : La cryptographie à clé asymétrique est utilisée par les autorités de certification (CA) pour émettre et signer des certificats numériques, utilisés dans les communications TLS, la signature de code, le chiffrement des e-mails, et plus encore. Un certificat numérique associe une clé publique à une entité spécifique (par exemple, une personne ou un serveur).

Figure 5. Émission et signature de certificats numériques avec la cryptographie asymétrique

Sécurité de la cryptographie asymétrique

Plusieurs notions cryptographiques se combinent pour permettre une cryptographie à clé asymétrique sécurisée, notamment :

Confidentialité de la clé privée : L'exigence de sécurité la plus fondamentale de l'AKC est que la clé privée reste secrète. Cependant, puisque la clé privée doit être mathématiquement liée à la clé publique, la confidentialité de la clé privée exige également qu'il soit computationnellement infaisable de dériver la clé privée à partir de la connaissance de la clé publique. Les schémas de génération de clés dans l'AKC s'appuient sur des problèmes mathématiques computationnellement difficiles pour faciliter cette exigence.

Fonctionnalité à trappe Dans l'AKC, les opérations de chiffrement et de déchiffrement impliquent différentes clés complémentaires d'une même paire de clés. Le texte chiffré généré par le chiffrement à l'aide de l'une des clés (par exemple la clé publique) doit être impénétrable pour les tiers, tout en étant facilement déchiffrable par le détenteur de la clé complémentaire (dans ce cas la clé privée). Autrement dit, le chiffrement doit ressembler à une fonction à sens unique avec trappe telle que les tiers ne puissent pas inverser l'opération et récupérer le texte en clair, mais que la clé privée fournisse une trappe secrète permettant une inversion facile. Les algorithmes AKC populaires utilisent l'exponentiation modulaire pour mettre en place un comportement de fonction à sens unique avec trappe.

Aléatoire : Le processus de génération de clés doit également exploiter l'aléatoire pour garantir que les clés sont imprévisibles, car tout motif ou toute prévisibilité dans la génération de clés pourrait être exploité par un attaquant. L'aléatoire est également utilisé pour le rembourrage lors du chiffrement afin de générer des textes chiffrés sémantiquement sécurisés et dans les schémas de signature numérique pour produire des signatures uniques, même lorsque le même message est signé plusieurs fois. Pour cette raison, l'utilisation de générateurs de nombres aléatoires forts est un aspect important de l'AKC.

Grande taille de clé : Comme dans le cas du SKC, de grandes tailles de clés assurent une protection contre les attaques par force brute. Cependant, comme de grandes tailles de clés augmentent également le coût computationnel du processus de chiffrement et de déchiffrement, une solution optimale doit équilibrer les considérations de sécurité et d'efficacité. Le tableau suivant montre les tailles de clés typiques pour divers protocoles et applications de cryptographie à clé asymétrique :

Protocole	Tailles de clés typiques (en bits)	Application
RSA	1024 (obsolète), 2048, 3072, 4096	Chiffrement, signatures numériques
DSA	1024 (obsolète), 2048, 3072	Signatures numériques
DH	2048, 3072, 4096	Échange de clés
ECDH	224, 256, 384, 521	Échange de clés
ECDSA	224, 256, 384, 521	Signatures numériques

Infrastructure à clé publique : Dans l'AKC, les clés privées doivent être gardées secrètes par leurs propriétaires tandis que les clés publiques sont partagées. Il doit exister un mécanisme sécurisé pour gérer et distribuer ces clés publiques entre les utilisateurs. L'infrastructure à clé publique (PKI) fournit un moyen de le faire en utilisant des certificats numériques. Un certificat numérique fournit une preuve d'identité du propriétaire de la clé publique et est émis par une autorité de confiance comme une autorité de certification (qui fait partie d'une PKI). Ainsi, la PKI joue un rôle intégral dans la sécurité des applications modernes utilisant l'AKC en permettant une gestion des clés à grande échelle (en créant, gérant, distribuant et révoquant des certificats numériques).

Risques de sécurité pour la cryptographie asymétrique

Comme indiqué dans le tableau ci-dessus, les algorithmes à clé asymétrique modernes tels que RSA emploient généralement des tailles de clés beaucoup plus grandes que leurs homologues à clé symétrique couramment utilisés, comme AES-128. Même les protocoles basés sur ECC (ECDH et ECDSA) qui ont des tailles de clés plus petites emploient un minimum d'au moins 224 bits pour les clés. Cela implique à son tour qu'une attaque par force brute impliquant une recherche exhaustive de l'espace de clés privées pour identifier la clé correcte est computationnellement intraitable dans un avenir prévisible. Cela reste vrai même si des ordinateurs quantiques étaient déployés pour cette tâche. Par conséquent, les attaques contre l'AKC se concentrent généralement sur l'exploitation d'autres faiblesses potentielles de cryptosystèmes spécifiques. Certains modes d'attaque bien documentés ciblent :

1. La faiblesse algorithmique en utilisant des moyens mathématiques et computationnels sophistiqués pour saper les hypothèses de difficulté utilisées pour formuler les algorithmes à clé asymétrique. Par exemple, la sécurité de RSA repose sur la difficulté de factoriser de grands nombres premiers, et des avancées computationnelles récentes ont permis la factorisation réussie de clés RSA de 829 bits. Par conséquent, RSA 1024 bits est actuellement obsolète. Comme cela sera discuté plus tard, le principal risque posé par les ordinateurs quantiques à l'AKC entre également dans cette catégorie.

2. L'aléatoire imparfait, qui peut conduire à une faiblesse dans le processus de génération de clés. Par exemple, si le générateur de nombres aléatoires utilisé pour créer les clés est défectueux et génère des clés qui ne sont pas vraiment aléatoires, un attaquant pourrait être en mesure de prédire les clés.

3. Les failles d'implémentation telles que des erreurs dans l'implémentation des algorithmes cryptographiques qui révèlent par inadvertance des informations sur les clés. Par exemple, un rembourrage incorrect peut potentiellement révéler des détails sur les clés.

4. Les canaux auxiliaires qui désignent la fuite d'informations depuis le système physique qui effectue la cryptographie. Ces fuites pourraient prendre la forme d'informations de synchronisation, de consommation d'énergie, ou même de son, qui peuvent être exploitées dans ce qu'on appelle une attaque par canal auxiliaire. Par exemple, analyser la durée des opérations cryptographiques pourrait révéler le nombre de '1' dans une clé binaire. Cette fuite apparemment innocente réduit considérablement l'espace de recherche, dévoilant des solutions potentielles à des problèmes qui semblaient initialement insurmontables.

5. L'échange de clés en interceptant les clés pendant leur échange, comme dans une attaque de l'homme du milieu (MITM). Le protocole DH est susceptible aux attaques MITM si des étapes d'authentification supplémentaires ne sont pas incorporées.

6. Le stockage des clés en visant à voler les clés depuis des stockages mal sécurisés. Cela inclut les attaques physiques telles que la manipulation ou le vol de dispositifs de stockage.

Sécuriser les cryptosystèmes à clé asymétrique contre la variété des attaques possibles est donc une tâche importante impliquant des considérations mathématiques, matérielles, logicielles, logistiques et juridiques.

RSA

L'algorithme RSA (Rivest-Shamir-Adleman) est l'un des premiers cryptosystèmes à clé publique et est largement utilisé pour la transmission sécurisée de données. C'est un cryptosystème polyvalent en ce sens qu'il fournit les opérations nécessaires pour permettre le chiffrement, le déchiffrement, les signatures numériques et l'échange de clés dans un cadre commun.

Dans cette section, nous allons illustrer la cryptographie à clé asymétrique (AKC) en utilisant RSA à travers des exemples simples.

Nous utiliserons le scénario standard de deux parties, Alice et Bob, qui souhaitent communiquer de manière sécurisée à l'aide de l'AKC.

L'algorithme RSA

L'algorithme RSA de base implique quatre opérations : la génération de clés, la distribution de clés, le chiffrement et le déchiffrement :

1. Génération de clés :

   Les clés publique et privée sont générées sur la base de principes mathématiques autour des nombres premiers, où les calculer est facile, mais l'inverse est difficile.

   Nous allons y faire référence ainsi :

   • Clé publique : $(e, n)$
   • Clé privée : $(d, n)$

   Remarque : $n$ est commun à la clé publique et à la clé privée, et est connu comme le modulus. Nous devrons l'utiliser plus tard.

Détail mathématique

• Choisis deux nombres premiers distincts, $p$ et $q$.
  • choisis aléatoirement (pour la sécurité).
  • Ils doivent être de grandeurs similaires, mais différer en longueur de quelques chiffres, pour rendre la factorisation plus difficile.
  • Les nombres premiers peuvent être choisis efficacement à l'aide d'un test de primalité.
• Calcule $n = p*q$.
  • $n$ est le modulus pour les deux clés publique et privée.
• Calcule la fonction indicatrice d'Euler $φ$ $(n) = (p-1)*(q-1)$.
  • L'indicatrice est censée rester secrète et est généralement supprimée après la génération de clés.
• Choisis un entier $e$ tel que $1 < e <$ $φ$ $(n)$ et $gcd$$(e,$$φ$$(n)) = 1$.
  • c'est-à-dire que $e$ et $φ$$(n)$ doivent être coprimes.
  • Ce nombre $e$ constitue l'exposant de la clé publique et est généralement choisi comme un petit nombre pour l'efficacité computationnelle.
  • Le nombre premier $65537 = 2^{16} + 1$ est souvent utilisé.
  • Calcule $d$ pour satisfaire la relation de congruence $d*e ≡ 1 ($$mod$$φ$$(n))$.
    • C'est-à-dire que $d$ est l'inverse multiplicatif de $e$ modulo $φ$$(n)$.
    • Cela est plus efficacement calculé à l'aide de l'algorithme euclidien étendu.
    • Ce nombre $d$ est l'exposant de la clé privée.
• La clé publique est constituée de $(e, n)$, et la clé privée est $(d, n)$.

2. Distribution de clés :

   • La clé publique $(e, n)$ est rendue publique à ceux qui souhaitent envoyer un message
   • La clé privée $(d, n)$ est gardée secrète.

3. Chiffrement :

   • Alice souhaite envoyer un message $M$ à Bob. Dans ce cas, un simple entier
   • Alice utilise la clé publique de Bob $(e, n)$ pour chiffrer le message en texte chiffré $C$
   Détail mathématique

   • $M$ est un entier $0 ≤ M < n$.
   • $C ≡ M^e (mod n)$, où $C$ est le texte chiffré.

4. Déchiffrement :

   • Bob reçoit le texte chiffré $C$
   • Bob utilise sa clé privée $(d, n)$ pour déchiffrer le message en message $M$
   Détail mathématique

   • $M ≡ C^d (mod n)$.

Voici l'esquisse de base de RSA. En pratique, des schémas de rembourrage plus sophistiqués sont appliqués au texte en clair $M$ avant le chiffrement pour garantir que des textes en clair identiques donnent des textes chiffrés différents. Cela prévient une gamme d'attaques possibles contre les implémentations naïves de RSA et permet la sécurité sémantique.

Illustration de RSA en Python

Dans les cellules de code suivantes, nous illustrons un exemple simple de l'algorithme RSA en utilisant de petits entiers, puis nous démontrons des applications pratiques de distribution de clés et de signature numérique en utilisant des bibliothèques Python implémentant RSA.

remarque

Remarque : Dans cette section, nous montrerons les calculs mathématiques en détail dans le cadre du code Python

Génération de clés RSA

Parcourons pas à pas une instance simple de l'algorithme RSA en employant de petits nombres premiers.

Nous devrons être en mesure de calculer le plus grand commun diviseur de deux entiers, car il sera nécessaire pour tester si deux entiers sont coprimes.

Nous expliquerons une façon simple de calculer cela, mais il est beaucoup plus efficace avec des entiers plus grands d'utiliser la fonction Python math.gcd.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

La première phase du flux de travail RSA est la génération de clés. Elle est initiée en choisissant deux nombres premiers, qui sont censés être gardés secrets par l'entité générant les clés.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

Ensuite, le modulus $n$, qui est simplement le produit des deux premiers choisis, est calculé. Ce modulus sera publié dans le cadre de la clé publique.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

La fonction indicatrice d'Euler $\varphi(n)$ est calculée ensuite, car elle est nécessaire pour l'opération d'inverse multiplicatif modulaire utilisée pour déterminer les clés dans RSA. $phi$ est également gardé secret et généralement supprimé après la génération de clés.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Nous sommes maintenant prêts à calculer les clés publique et privée. Dans RSA, chacune d'elles est spécifiée par un tuple de deux entiers. La première entrée dans chaque tuple est un entier distinct, et la deuxième entrée est le modulus $n$ commun aux deux clés.

La première entrée dans la clé publique peut être n'importe quel entier supérieur à 1 qui est coprime à $phi$. Deux entiers sont coprimes si leur plus grand commun diviseur est 1. Nous utilisons donc la fonction math.gcd pour trouver un entier $e$ coprime à $phi$.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

La clé privée nécessite un entier $d$, qui est l'inverse multiplicatif de $e$ modulo $phi$ ; c'est-à-dire qu'il satisfait la relation de congruence $d*e\equiv 1 \pmod{\varphi(n)}$. Pour cette illustration simple où nous traitons de petits entiers, nous pouvons simplement parcourir les entiers positifs pour localiser un $d$ adéquat. Dans des contextes réalistes, l'algorithme euclidien étendu, computationnellement efficace, est utilisé à cet effet.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Nous formons maintenant les tuples $(e, n), (d, n)$, qui constituent respectivement les clés publique et privée. La clé publique est ensuite publiée, tandis que la clé privée est gardée secrète.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

Le chiffrement et le déchiffrement dans RSA utilisent l'opération d'exponentiation modulaire. De plus, les clés publique et privée sont complémentaires en ce sens que l'une ou l'autre peut être utilisée pour chiffrer un message que l'autre peut ensuite déchiffrer.

Nous illustrons ici le cas où la clé publique $(e,n)$ est utilisée pour le chiffrement et la clé privée $(d, n)$ est utilisée pour le déchiffrement, en définissant une fonction Python pour chaque opération.

Nous chiffrons ensuite et déchiffrons un message entier $msg$.

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

Bien que les petits entiers utilisés ci-dessus soient utiles pour exposer facilement les idées fondamentales de l'algorithme RSA, dans les applications réelles RSA nécessite l'utilisation de très grands entiers. Par exemple, RSA 2048 bits implique l'utilisation d'un modulus $n$ long de 2048 bits, dont les équivalents entiers décimaux sont d'environ 10$^616$. Ces nombres vraiment énormes sont nécessaires pour la sécurité pratique de RSA.

Échange de clés symétrique avec RSA

Comme discuté précédemment, l'AKC permet à deux parties souhaitant communiquer d'établir de manière sécurisée un secret partagé, qui peut être utilisé, par exemple, comme clé secrète pour le chiffrement symétrique ultérieur de texte en clair en masse.

Considérons le scénario suivant. Alice et Bob veulent utiliser le SKC pour chiffrer et déchiffrer des messages. Cependant, avant que ce processus puisse être initialisé, ils doivent s'accorder sur une clé secrète commune. Une option est que l'une des parties — disons Alice — génère une clé secrète et la transmette ensuite de manière sécurisée à Bob. Pour réaliser ce transfert sécurisé, Alice décide d'utiliser RSA comme mécanisme d'encapsulation de clé (KEM).

Cela implique les étapes suivantes :

• D'abord, Alice génère une clé symétrique aléatoire, qu'elle a l'intention de partager avec Bob.
• Ensuite, Bob génère une paire de clés asymétrique et rend sa clé publique disponible sur un canal approprié.
• Puis, Alice utilise la clé publique de Bob pour chiffrer la clé symétrique, l'encapsulant ainsi dans un texte chiffré.
• Ensuite, Alice diffuse le texte chiffré sur un canal fiable mais pas nécessairement sécurisé.
• Enfin, Bob reçoit le texte chiffré et le déchiffre à l'aide de sa clé privée. Il a maintenant accès à la clé symétrique générée par Alice.

Figure 1. Échange de clés symétrique avec RSA

Exemple d'échange de clés basé sur le rembourrage en Python

Un flux de travail pratique utilisant RSA pour l'échange de clés non interactif basé sur le rembourrage est maintenant illustré à l'aide de la bibliothèque Python cryptography.

Importe les modules nécessaires depuis la bibliothèque Python cryptography. Si nécessaire, cette bibliothèque peut être installée à l'aide de la commande pip install cryptography.

Alice génère ensuite une clé secrète aléatoire, qu'elle a l'intention de transmettre à Bob.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

En utilisant le module rsa de la bibliothèque cryptography, Bob génère une paire de clés et diffuse ensuite sa clé publique. N'importe qui peut intercepter la clé publique et lire les nombres publics $(e,n)$ qui la composent.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

À ce stade, on suppose qu'Alice a reçu la clé publique diffusée par Bob. La symmetric_key d'Alice peut maintenant être chiffrée à l'aide de la clé publique de Bob pour produire le texte chiffré. Dans un contexte réaliste, Alice utilisera également des méthodes de rembourrage supplémentaires telles que OAEP pour assurer la sécurité sémantique de ses communications avec Bob.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Alice diffuse ensuite le texte chiffré sur un canal ouvert, confiante que seul Bob, disposant de la clé privée correspondante, pourra le déchiffrer. On suppose que Bob a reçu le texte chiffré et peut maintenant le déchiffrer à l'aide de sa clé privée confidentielle.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

À ce stade, Alice et Bob ont tous les deux accès à la clé symétrique secrète, qu'ils peuvent utiliser pour des applications de chiffrement à clé symétrique (SKC).

Simuler un mécanisme d'encapsulation de clé avec RSA en Python

Dans le flux de travail suivant, on illustre l'utilisation de RSA pour simuler un mécanisme d'encapsulation de clé (KEM), par lequel un message secret aléatoire suffisamment long est échangé de manière sécurisée puis converti en un secret partagé de la longueur appropriée à l'aide d'une KDF.

Une fois encore, Alice et Bob souhaitent établir un secret partagé de façon non interactive, et c'est Alice qui décide quel secret utiliser.

On commence par importer quelques bibliothèques Python nécessaires.

Bob génère ensuite sa paire de clés RSA et diffuse sa clé publique.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice génère d'abord un long secret aléatoire à partir duquel le secret partagé sera finalement dérivé. Dans un KEM pur, le long secret est un élément aléatoire de la structure algébrique sous-jacente au cryptosystème. Dans le cas de RSA 2048 bits, ce serait un entier aléatoire modulo le module RSA de 2048 bits. Un tel KEM pur ne nécessite pas de rembourrage supplémentaire, mais dans cet exemple, on simule seulement un KEM à l'aide de RSA et la bibliothèque cryptography exige l'utilisation d'un rembourrage lors du chiffrement avec RSA. On utilisera donc un long secret un peu plus court, qui reste néanmoins bien plus long qu'une clé AES standard de 256 bits.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

Alice chiffre ensuite le long secret à l'aide de la clé publique de Bob, et le secret chiffré est communiqué à Bob.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob déchiffre le secret chiffré reçu d'Alice à l'aide de sa clé privée.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

Enfin, Alice et Bob appliquent séparément une fonction de dérivation de clé (KDF) convenue sur le long secret pour dériver la clé symétrique.

Il est à noter que le processus implique un protocole de hachage et l'utilisation d'un sel aléatoire, ce qui garantit l'unicité et l'imprévisibilité de la clé symétrique partagée au cas où le long secret serait réutilisé (ce qui n'est pas recommandé). Cependant, le sel lui-même n'a pas besoin d'être secret, et une fois qu'il est généré aléatoirement — par Alice dans cet exemple —, il peut être diffusé à Bob en même temps que le long secret chiffré.

On suppose donc qu'Alice et Bob ont tous les deux accès au même sel aléatoire.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Signatures numériques avec RSA

On va maintenant étendre le scénario de communication confidentielle entre Alice et Bob pour y inclure la validation à l'aide d'une signature numérique.

Comme précédemment, Alice enverra confidentiellement un message encapsulant une clé symétrique à Bob, mais elle signera également le message numériquement pour que Bob, à la réception, puisse vérifier que c'est bien Alice qui en est l'auteure et que le contenu n'a pas été altéré pendant la transmission.

Plus généralement, il est souhaitable de permettre la validation sans compromettre la confidentialité, de sorte que toute partie intéressée soit en mesure de vérifier l'intégrité, l'authenticité, et d'établir la non-répudiation d'une communication donnée, même si cette partie n'a pas accès au message en clair.

On va considérer ce cadre général, qui implique alors les étapes suivantes :

• D'abord, Bob et Alice rendent leurs clés publiques disponibles sur un canal ouvert.
• Ensuite, Alice chiffre le texte en clair à l'aide de la clé publique de Bob, créant ainsi un texte chiffré.
• Alice crée ensuite un hachage du texte chiffré avec une fonction de hachage, puis chiffre le hachage résultant à l'aide de sa clé privée. Ce hachage chiffré est la signature.
• Alice transmet alors le texte chiffré et la signature sur un canal ouvert.
• Bob utilise la clé publique d'Alice pour déchiffrer la signature, révélant ainsi le hachage du texte chiffré.
• Puisque Bob a également accès au texte chiffré lui-même, il utilise la même fonction de hachage qu'Alice pour recréer une deuxième instance du hachage. Si celle-ci correspond à celle obtenue en déchiffrant la signature d'Alice, alors le message est validé, même si le texte chiffré lui-même n'a pas encore été déchiffré.
• Enfin, Bob, ayant validé le message, déchiffre le texte chiffré à l'aide de sa propre clé privée.

Figure 2. Signatures numériques avec RSA

Ce flux de travail pour une signature numérique est illustré ci-après.

On importe à nouveau quelques modules utiles de la bibliothèque cryptography. Comme précédemment, Alice souhaite envoyer de manière sécurisée une clé symétrique à Bob, mais elle veut également la signer numériquement. Dans ce cas, on a besoin des clés publiques d'Alice et de Bob. La première étape consiste donc pour les deux à créer leur propre paire de clés RSA et à diffuser leur propre clé publique au monde entier.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

À l'étape suivante, comme précédemment, Alice utilise la clé publique de Bob pour chiffrer la clé symétrique et prépare le texte chiffré.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

À ce stade, au lieu de simplement diffuser le texte chiffré, Alice souhaite y joindre une signature numérique pour pouvoir prouver à Bob qu'elle est bien l'expéditrice du message. Cela se fait en deux étapes :

1. Créer un hachage du texte chiffré à l'aide d'un algorithme de hachage.
2. Chiffrer le hachage à l'aide de la clé privée d'Alice, ce qui constitue la signature.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Alice diffuse ensuite le texte chiffré et la signature sur un réseau pour que Bob puisse les intercepter tous les deux.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Du côté de Bob, la première tâche consiste à vérifier l'intégrité et l'authenticité du texte chiffré. Pour ce faire, Bob crée un hachage du texte chiffré reçu en utilisant le même algorithme de hachage qu'Alice.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

Ensuite, Bob déchiffre la signature reçue à l'aide de la clé publique d'Alice. Puisqu'Alice a utilisé sa clé privée pour créer la signature, Bob peut la déchiffrer avec la clé publique d'Alice. La signature déchiffrée n'est rien d'autre qu'un hachage du texte chiffré créé du côté d'Alice. Si le hachage créé par Bob correspond à la signature déchiffrée, alors Bob a vérifié que le texte chiffré qu'il a reçu n'a pas été altéré et que c'est bien Alice qui l'a signé.

Dans le code Python ci-dessous, ces opérations sont regroupées dans une fonction utilitaire appelée verify fournie par un objet associé à la clé publique d'Alice.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

Ayant vérifié l'intégrité et l'authenticité du texte chiffré reçu, Bob peut alors le déchiffrer à l'aide de sa clé privée, car Alice a créé le texte chiffré en utilisant la clé publique de Bob.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

Dans le scénario de signature numérique ci-dessus, n'importe quelle partie — pas seulement Bob — peut vérifier qu'Alice est l'expéditrice du texte chiffré, car tout le monde peut accéder à la clé publique d'Alice, au texte chiffré et à la signature numérique. De plus, après avoir envoyé le texte chiffré et la signature, Alice ne peut pas nier ultérieurement l'avoir fait, car la signature ne peut être déchiffrée en un hachage significatif qu'en utilisant sa clé publique. Cela établit la non-répudiation.

En permettant une distribution sécurisée des clés et en prenant en charge la non-répudiation, la cryptographie à clé publique établit une base solide pour une communication numérique sécurisée.

Casser RSA

L'utilité et la sécurité de l'algorithme RSA décrit ci-dessus reposent sur deux hypothèses mathématiques :

1. Trouver l'inverse multiplicatif modulaire $d$ en n'ayant accès qu'à $(e, n)$ est informatiquement infaisable.

2. Dans le contexte RSA, l'opération d'exponentiation modulaire se comporte comme une fonction à sens unique avec trappe. Utilisée pour le chiffrement, elle produit un texte chiffré indéchiffrable, et sans accès à la clé privée, inverser l'opération pour retrouver le texte en clair à partir du texte chiffré n'est pas faisable. En revanche, avec la clé privée, qui joue le rôle de trappe, le texte chiffré peut être facilement déchiffré.

L'attaque la plus connue contre l'algorithme RSA vise à contourner l'hypothèse 1 en récupérant efficacement le nombre de clé privée $d$ via la factorisation du modulus $n$. Comme illustré ci-dessous, il est facile de retrouver $d$ si on a accès aux facteurs premiers $p$ et $q$ de $n$ ou à l'indicatrice d'Euler $φ$$(n)$. Rappelons que $p$, $q$ et $φ$$(n)$ sont gardés secrets lors de la génération des clés et supprimés ensuite. Un tiers qui récupère ces informations à l'aide d'un ordinateur classique ou quantique obtient essentiellement la clé privée, ce qui casse RSA. La factorisation en nombres premiers est donc la primitive calculatoire clé nécessaire pour casser RSA.

Informatique classique et RSA

La factorisation en nombres premiers de grands entiers est connue pour présenter une complexité super-polynomiale ou sous-exponentielle sur les ordinateurs classiques. Le meilleur algorithme classique connu pour factoriser des entiers supérieurs à $10^{100}$ est le crible algébrique (GNFS)

Détail mathématique

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

en fonction de l'entier $n$ à factoriser.

Cette complexité est super-polynomiale par rapport au nombre de bits nécessaires pour représenter $n$.

Par conséquent, la factorisation en nombres premiers est considérée comme inefficace sur les ordinateurs classiques.

À ce jour, les plus grands entiers factorisés sur du matériel classique se situent dans la plage de 829 bits ou 250 chiffres décimaux. Compte tenu de la croissance exponentielle de la puissance de calcul classique observée au cours des dernières décennies, RSA 1024 bits n'est plus considéré comme sûr à court terme et est désormais déprécié. Néanmoins, dans un avenir prévisible, factoriser des entiers de 2048 bits dont la magnitude se situe dans la plage de $10^{617}$ est actuellement considéré comme infaisable sur les systèmes classiques, ce qui suggère une viabilité continue. L'avènement des ordinateurs quantiques remet toutefois en question cette évaluation.

L'algorithme quantique de Shor et RSA

L'algorithme quantique probablement le plus connu aujourd'hui est l'algorithme de Shor pour trouver les facteurs premiers d'entiers. Lors de son introduction par Peter Shor en 1994, il a été reconnu comme le premier algorithme quantique offrant une accélération super-polynomiale par rapport aux algorithmes classiques sur un problème d'importance pratique majeure, à savoir la factorisation en nombres premiers.

L'algorithme de Shor peut factoriser des nombres premiers avec $O(n^2)$ où $n$ est le nombre de bits.

Explication mathématique de l'algorithme de Shor

Dans le contexte de RSA, l'algorithme de Shor fonctionne en exploitant la périodicité de la fonction exponentielle modulaire $f(x) = a^x (mod~n)$ et fournit une primitive quantique de recherche de période qui permet la factorisation efficace en nombres premiers du modulus $n$.

Voici un aperçu simplifié du schéma général de Shor pour casser RSA :

1. Étant donné le modulus $n$, publié dans le cadre de la clé publique, on choisit un nombre $a$ copremier avec $n$, c'est-à-dire $gcd(a,n) = 1$. Puisqu'on sait que $n = p*q$ possède exactement deux facteurs premiers $(p, q)$, presque n'importe quel nombre inférieur à $n$ choisi aléatoirement sera vraisemblablement copremier avec $n$.

2. Ayant choisi $a$, on cherche l'exposant $r$ tel que $a^r \equiv 1 (mod~n)$. Cela implique $a^r - 1 \equiv 0 (mod~n)$. L'existence d'un exposant $r$ tel que la congruence ci-dessus soit vérifiée est garantie par la propriété de périodicité de l'exponentiation modulaire.

3. Si $r$ est pair, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ pour un certain entier $\gamma$. Le membre gauche de cette dernière égalité doit contenir $p$ et $q$ parmi ses facteurs premiers car le membre droit les contient. Si $r$ est impair, reviens à l'étape 1 et essaie un choix différent pour $a$.

4. Utilise l'algorithme d'Euclide étendu pour trouver $gcd((a^{r/2} - 1), n)$ ou $gcd((a^{r/2} + 1), n)$. Le PGCD calculé identifiera très probablement l'un des facteurs premiers $p$ ou $q$. Divise $n$ par ce facteur premier pour retrouver l'autre.

5. Une fois que $p, q$ sont connus, utilise les étapes de l'algorithme RSA original pour reconstruire l'indicatrice $\phi(n)$ et générer le nombre de clé privée $d$ comme l'inverse modulaire du nombre de clé publique connu $e$.

En août 2023, Oded Regev a publié une amélioration de l'algorithme original de Shor en utilisant une approche multidimensionnelle aboutissant à $O(n^{1.5})$. Des recherches se poursuivent, notamment par Ragavan et Vaikuntanathan dans ce domaine, qui pourraient améliorer le temps d'exécution, le coût ou le nombre de qubits nécessaires. Bien qu'on ne puisse pas dire quand l'exécution de tels algorithmes contre le chiffrement RSA réel deviendra vraiment viable, cela se rapproche de plus en plus.

Exemple Python illustrant le cassage du chiffrement RSA

Dans les cellules de code suivantes, on illustre un exemple de recherche d'une clé privée en n'ayant accès qu'à la clé publique. Cela utilisera une computation classique par force brute, mais montre comment l'algorithme de Shor pourrait être utilisé — y compris pour de grandes clés.

remarque

Dans cette section, on affichera les calculs mathématiques en détail dans le code Python

Dans l'exemple, on a une clé publique $(5, 247)$, et on va retrouver la clé privée.

Étape 1 : La première étape consiste à choisir un nombre copremier avec 247. Presque n'importe quel nombre qu'on devine fera l'affaire. Choisissons 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Étape 2 : Ensuite, on doit trouver la période $r$ telle que $6^r \equiv 1 (mod~247)$. Dans cet exemple, on calcule $r$ classiquement par force brute, mais on pourrait aussi utiliser l'algorithme de Shor sur un ordinateur quantique avec Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Étape 3 : Comme la période $r = 36$ est paire, on peut calculer $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Étape 4 : On trouve le PGCD de l'un de ces facteurs avec $n$. Il suffit de diviser $n$ par le facteur premier déjà trouvé pour obtenir le second facteur premier.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Étape 5 : Après avoir retrouvé les facteurs premiers de $n = 247$ comme $p_{found}=13$ et $q_{found}=19$, on calcule l'indicatrice $\phi_{found} = (p_{found}-1)*(q_{found}-1)$.

La clé privée est l'inverse modulaire du nombre de clé publique $e=5$.

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

Dans le schéma ci-dessus, l'étape 2 est l'opération cruciale de recherche de période pour laquelle l'algorithme de Shor utilise deux primitives quantiques fondamentales, à savoir la transformée de Fourier quantique et l'estimation de phase quantique. Pour une explication détaillée des aspects quantiques de l'algorithme de Shor, consulte la leçon sur l'estimation de phase et la factorisation dans le cours Fondamentaux des algorithmes quantiques. Les étapes 1 et 3 à 5 impliquent des opérations relativement peu coûteuses qui peuvent être facilement effectuées sur des ordinateurs classiques.

Optionnellement, voici un guide visuel détaillé sur l'implémentation de l'algorithme de Shor.

Sur les ordinateurs quantiques, l'algorithme de Shor peut présenter une complexité polylogarithmique aussi favorable que $O((log~n)^2 (log~log~n))$ en termes du modulus $n$, ou une complexité polynomiale en termes du nombre de bits nécessaires pour représenter $n$. C'est une accélération super-polynomiale par rapport à l'algorithme GNFS classique.

Les estimations de ressources récentes indiquent que, selon certaines hypothèses concernant la configuration matérielle, quelques dizaines de milliers à plusieurs millions de qubits seront nécessaires pour casser RSA 2048 bits en utilisant l'algorithme de Shor. Il n'est pas inconcevable que des ordinateurs quantiques avec plusieurs dizaines de milliers de qubits deviennent disponibles au cours des prochaines années, rendant accessible l'extrémité inférieure de l'estimation des ressources.

Échange de clés Diffie-Hellman et l'algorithme de signature numérique

Dans la section précédente, on a discuté du système cryptographique RSA, dont la sécurité repose sur la difficulté de calcul de la factorisation en nombres premiers. Ici, on va discuter de deux protocoles cryptographiques asymétriques populaires, l'échange de clés Diffie-Hellman (DH) et l'algorithme de signature numérique (DSA), tous deux basés sur un problème mathématique différent, à savoir le problème du logarithme discret (DLP).

Le problème du logarithme discret

Dans l'équation suivante, on doit trouver $a$ en connaissant uniquement $e$, $M$, $c$

$a^e$ $mod$ $M = c$

On croit que ce problème est difficile avec les ordinateurs classiques en raison de l'utilisation de l'arithmétique modulaire, ce qui en fait une bonne base mathématique pour un algorithme de chiffrement.

C'est ce qu'on appelle le problème du logarithme discret (DLP).

Détails mathématiques du problème du logarithme discret

Le DLP est généralement formulé dans le contexte des groupes cycliques et est énoncé comme suit.

Considère un groupe cyclique $G$ engendré par un élément de groupe $g \in G$ et, étant donné un élément arbitraire $h \in G$, trouve un entier $k$ tel que $h = g^{k}$.

Ici, l'entier $k \equiv log_{g}h$ est le logarithme discret. La propriété cyclique de $G$ garantit que pour tout $h$, il existe un entier $k$ valide.

Pour la cryptographie, le DLP sur le groupe multiplicatif des entiers modulo un nombre premier $p$, noté $(\mathbb{Z}_p)^{\times}$, s'avère utile. Les éléments de $(\mathbb{Z}_p)^{\times}$ sont des classes de congruence étiquetées par des entiers modulo $p$ qui sont copremieres avec $p$.

Par exemple :

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{and}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

L'opération de multiplication $(\times)$ sur ces groupes est simplement la multiplication ordinaire d'entiers suivie d'une réduction modulo $p$, et l'exponentiation par un entier $k$ n'est que la multiplication répétée $k$ fois suivie d'une réduction modulo $p$.

Illustrons une instance du DLP sur $(\mathbb{Z}_7)^{\times}$.

Ce groupe multiplicatif a deux générateurs ${[3],[5]}$, également appelés racines primitives. On utilisera $[5]$ comme générateur, c'est-à-dire générer chaque élément de $(\mathbb{Z}_7)^{\times}$ en utilisant des puissances entières successives de 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

On voit qu'en arithmétique modulo 7, élever 5 à des puissances entières successives produit chaque élément de $(\mathbb{Z}_7)^{\times}$ exactement une fois avant que le cycle se répète indéfiniment avec une période $p-1 =6$.

Donc le DLP sur $(\mathbb{Z}_7)^{\times}$ avec le générateur [5] est :

$\mathrm{Given}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, find~} k \mathrm{~such~that~} 5^{k} \equiv h~(mod~7)$.

D'après la sortie de la cellule Python ci-dessus, on voit que :

$h = 2 \implies k=4 \mathrm{~or~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~or~} 3 = log_5(6) (mod~7)$

En arithmétique réelle ordinaire, l'exponentiation est une fonction monotone et calculer le logarithme de n'importe quel nombre en n'importe quelle base est informatiquement facile. En revanche, comme on le voit dans le simple exemple $(\mathbb{Z}_7)^{\times}$ ci-dessus, l'exponentiation modulaire est non monotone, et même si elle est périodique avec une période $p-1$, elle est par ailleurs hautement non triviale. Calculer son inverse, le logarithme discret, s'avère donc inefficace pour de grands $p$ sur les ordinateurs classiques.

Cette observation sous-tend à la fois l'échange de clés Diffie-Hellman (DH) et l'algorithme de signature numérique (DSA), qui sont discutés dans la section suivante.

Le DLP peut être étendu aux sous-groupes cycliques comme suit :

• Considère $(\mathbb{Z}_p)^{\times}$ défini ci-dessus et un élément $g \in (\mathbb{Z}_p)^{\times}$ d'ordre premier $r$, c'est-à-dire $g^r \equiv 1 (~mod~p)$.
• L'ensemble des puissances entières de $g$ : $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ est un sous-groupe cyclique de $(\mathbb{Z}_p)^{\times}$ d'ordre de groupe $r$.
• Un DLP peut être spécifié sur $\langle g \rangle$ en choisissant un $h \in \langle g \rangle$ et en demandant $1 \le a \le r$ tel que $g^a~(mod~p) = h$

Échange de clés Diffie-Hellman

En 1976, Whitfield Diffie et Martin Hellman ont proposé un protocole d'échange de clés pour permettre la création d'une clé secrète partagée sur des canaux de communication non sécurisés. La clé secrète pouvait ensuite être utilisée par les parties qui la partagent pour le chiffrement symétrique. L'algorithme repose sur le DLP.

Figure 1. Échange de clés Diffie-Hellman

Détails mathématiques de l'échange de clés Diffie-Hellman

Avec Alice et Bob comme les deux parties communicantes, le protocole fonctionne comme suit :

• D'abord, Alice et Bob se mettent d'accord sur un grand nombre premier $p$ et une racine primitive ou générateur $a$.
• Ensuite, Alice choisit un exposant secret $k_A$ aléatoirement avec $1 \le k_A \le p-2$ et calcule $h_A = a^{k_A}~(mod~p)$. $k_A, h_A$ sont respectivement les clés privée et publique d'Alice.
• Puis, Bob choisit un exposant secret $k_B$ aléatoirement avec $1 \le k_B \le p-2$ et calcule $h_B = a^{k_B}~(mod~p)$. $k_B, h_B$ sont respectivement les clés privée et publique de Bob.
• Ensuite, Alice envoie $h_A$ à Bob et Bob envoie $h_B$ à Alice via un canal fiable mais pas nécessairement sécurisé.
• Puis, Alice utilise le $h_B$ qu'elle a reçu pour calculer la clé secrète partagée $\kappa = h_B^{k_A}~(mod~p)$.
• Enfin, Bob utilise le $h_A$ qu'il a reçu pour calculer la clé secrète partagée $\kappa = h_A^{k_B}~(mod~p)$.

Avec ce protocole :

• Alice et Bob sont assurés d'obtenir la même clé secrète $\kappa$ car $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$.
• Un tiers qui intercepte $h_A$ ou $h_B$ ne peut pas construire la clé secrète $\kappa$ car il n'a pas accès à $k_B$ ou $k_A$ respectivement.
• Extraire $k_A$ ou $k_B$ à partir des informations publiques $a$, $p$, $h_A$ et $h_B$ est informatiquement difficile car c'est équivalent à résoudre le DLP sur $(\mathbb{Z}_p)^{\times}$.

Illustration du protocole Diffie-Hellman en Python

Regardons un exemple simple du protocole DH en Python en utilisant de petits nombres premiers :

remarque

Dans cette section, on affichera les calculs mathématiques en détail dans le code Python

Étape 1 : Alice et Bob se mettent d'accord sur un nombre premier $p$ et une racine primitive $a$. Choisissons $p=11, a=7$.

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Étapes 2, 3 : Alice choisit un exposant secret $k_A$ et calcule $h_A = a^{k_A}~(mod~p)$. De même, Bob choisit un exposant secret $k_B$ et calcule $h_B = a^{k_B}~(mod~p)$.

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Étape 4 : Les deux parties diffusent leurs clés publiques $h_A$ et $h_B$.

Étapes 5, 6 : Chaque partie combine sa clé privée avec la clé publique de l'autre partie pour créer la clé secrète partagée.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alice et Bob peuvent maintenant utiliser la clé secrète partagée pour le chiffrement symétrique.

Sécurité de l'échange de clés Diffie-Hellman

Comme indiqué ci-dessus, la sécurité de DH est conditionnée par la difficulté de calcul pour résoudre le DLP avec de grands nombres premiers $p$. Dans les applications typiques, le NIST recommande des entiers premiers de 2048 ou 3072 bits pour l'échange de clés DH, ce qui est considéré comme suffisamment sécurisé contre les tentatives de résolution du DLP à l'aide d'ordinateurs classiques.

Attaques de l'homme du milieu (MITM) : Le fait que DH soit un schéma interactif où la clé secrète partagée dépend de la combinaison de la clé privée d'une partie avec la clé publique de l'autre partie le rend vulnérable à une attaque dite de l'homme du milieu (MITM).

Détails mathématiques de la sécurité DH et des attaques MITM

Dans ce scénario, un tiers — disons, Ève — intercepte les clés publiques $h_A, h_B$ pendant la transmission et substitue sa propre clé publique $h_E$ à chacune des clés $h_A$ et $h_B$ avant de les transmettre respectivement à Bob et Alice.

Ainsi, au lieu d'utiliser $h_B$ pour créer sa clé secrète partagée, Alice utilisera $h_E$ en pensant qu'elle utilise la clé publique de Bob. De même, au lieu d'utiliser $h_A$ pour créer sa clé secrète partagée, Bob utilisera $h_E$ en pensant qu'il utilise la clé publique d'Alice.

Comme $h_E$ a été utilisée pour créer la clé secrète partagée d'Alice (de Bob), le texte en clair chiffré par Alice (Bob) peut être déchiffré par Ève.

Ainsi, l'échange de clés DH est généralement utilisé conjointement avec un algorithme de signature numérique pour s'assurer que chaque partie utilise une clé publique authentifiée pour créer sa clé secrète partagée.

L'algorithme de signature numérique (DSA)

Même si des systèmes cryptographiques génériques comme RSA offrent des fonctionnalités de signature numérique, en 1994, le NIST a adopté un schéma de signature spécialisé basé sur l'exponentiation modulaire et le problème du logarithme discret comme norme fédérale pour les signatures numériques. Ce schéma, connu simplement sous le nom d'algorithme de signature numérique (DSA), implique quatre phases distinctes :

1. Génération des clés :

   Les clés DSA sont générées à partir de :

   • 2 nombres premiers répondant à certaines règles
     • $p$ - généralement 256 bits (on appellera cette longueur $N$)
     • $q$ - généralement 3072 bits (on appellera cette longueur $L$)
   • Une fonction de hachage cryptographique qui convertira des chaînes de longueur $L$ en chaînes de longueur $N$
   • Un paramètre supplémentaire $g$ (voir les détails ci-dessous)

   À partir de cela, on choisit un nombre aléatoire $x$ comme clé privée, et on peut calculer une clé publique $y$

   Détails mathématiques de la génération des clés

   • Génération des paramètres : Mathématiquement, DSA implique un sous-groupe cyclique de $(\mathbb{Z}_p)^{\times}$ engendré par un élément $g$ d'ordre premier q < p. La première étape du DSA est donc de sélectionner deux nombres premiers p, q pour mettre en place les structures mathématiques nécessaires.

     • Choisir un nombre premier $q$ de $N$ bits.
     • Choisir un nombre premier $p$ de $L$ bits tel que $p-1$ soit un multiple de $q$. Le choix de $p$ spécifie le groupe $(\mathbb{Z}_p)^{\times}$
     • Choisir un entier $1 < h < p-1$ aléatoirement et calculer $g = h^{(p-1)/q}~mod~p$. Si $g=1$, ce qui arrive rarement, essayer un autre h.
     • Vérifier que $g^q~mod~p = 1$. g est donc un générateur d'un sous-groupe cyclique $\langle g \rangle$ de $(\mathbb{Z}_p)^{\times}$ d'ordre premier q.

     Les paramètres $(q, p, g)$ spécifient une instance de l'algorithme et sont des informations publiques. Typiquement, $N \sim 256$ et $L \sim 3072$ dans les applications réelles.

     Le protocole nécessite également une fonction de hachage cryptographique $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ qui fait correspondre des chaînes binaires de $L$ bits à des chaînes de $N$ bits, par exemple SHA-256.

   • Génération de la paire de clés : Le signataire doit générer une paire de clés de son côté.

     • Choisir un entier secret aléatoire $x \in \{1,2...q-1\}$. $x$ est la clé privée.
     • Générer $y = g^{x}~mod~p$. $y$ est la clé publique du signataire.

2. Distribution des clés :

   Les informations suivantes sont partagées avec toute personne souhaitant valider une signature :

   • Les paramètres utilisés $(p,q,g)$ qui décrivent l'algorithme
   • La fonction de hachage $H$
   • La clé publique $y$

3. Signature :

   • Le signataire peut maintenant signer un message $m$. La signature résultante est $(r,s)$
   • Le message et la signature sont ensuite envoyés au destinataire
   Détails mathématiques de la signature d'un message

   Le signataire signe un message $m$ comme suit :

   • Choisir un entier secret k aléatoirement dans $\{1,2...q-1\}$
   • Calculer $r = (g^k~mod~p)~mod~q$. Dans le cas rare où $r=0$, essayer un autre k aléatoire.
   • Calculer $s = (k^{-1} (H(m) + xr))~mod~q$. Dans le cas rare où $s=0$, essayer un autre k aléatoire.
   • La signature est le tuple $(r, s)$.
   • Le signataire transmet le message $m$ ainsi que la signature $(r,s)$ au vérificateur.

   Comme $r, s$ sont tous deux des entiers, modulo $q$ la taille de la signature est de l'ordre de $N$ bits et non des $L$ bits plus longs.

4. Vérification :

   Le destinataire souhaite maintenant vérifier l'authenticité de l'expéditeur. Il a accès aux informations publiques $(q, p, g, H, y, (r,s), m)$ Il peut effectuer un calcul qui prouve que l'expéditeur avait accès à la clé privée $x$

   et cherche à établir que le signataire est quelqu'un ayant accès à la clé privée $x$.

   Détails mathématiques du schéma de vérification DSA

   • Vérifier que $0 \lt r \lt q$ et $0 \lt s \lt q$, c'est-à-dire que $r, s$ sont des entiers valides modulo~q.
   • Calculer $w = s^{-1}~mod~q$.
   • Calculer $u_1 = H(m)w~mod~q$.
   • Calculer $u_2 = rw~mod~q$.
   • Calculer $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$.
   • La signature est vérifiée si $v = r$.

   Pour les signatures légitimes, la correction de l'algorithme DSA est facilement démontrée comme suit :

   • Du côté du signataire : $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • En considérant le membre droit de cette dernière égalité, un vérificateur peut calculer $s^{-1}, H(m)$ car $s, q, m, H$ sont des informations publiques.
   • Ainsi, le vérificateur calcule $w = s^{-1}~mod~q$ et $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$.
   • Le vérificateur calcule également $u_2 = rw~mod~q = rs^{-1}~mod~q$ car $r$ est aussi public.
   • Notons que $k = (u_1 + xu_2)~mod~q$.
   • Cependant, un vérificateur n'a pas accès à $x$ car c'est la clé privée du signataire, donc $k$ lui-même ne peut pas être calculé directement. Le schéma repose plutôt sur le fait que même si le vérificateur ne peut pas calculer $k$, avec un signataire légitime, le vérificateur devrait être capable de recalculer $(g^k~mod~p)~mod~q = r$ à l'aide de la clé publique du signataire $y = g^{x}~mod~p$.
   • Ainsi, le vérificateur calcule $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$.
   • La dernière égalité découle du fait que $g$ a l'ordre $q$ et établit $v = r$ pour les signatures valides.

Illustration du DSA en Python

Dans cet exemple, on utilisera de petits nombres premiers pour illustrer le processus DSA dans un scénario où Alice envoie un message signé à Bob. On utilisera de petits entiers dans cet exemple. Un scénario réel emploierait des nombres premiers beaucoup plus grands de l'ordre de 2048 à 3072 bits.

remarque

Tu peux essayer de relancer cet exemple avec des valeurs différentes pour voir comment l'algorithme se comporte, mais assure-toi de commencer à exécuter depuis la première cellule de cette section.

On commence par importer les bibliothèques nécessaires et choisir nos paramètres. Les paramètres entiers $p$, $q$, $g$ sont des informations publiques et satisfont les règles suivantes :

• $p$, $q$ sont tous deux premiers
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

Ensuite, la signataire, Alice, génère sa clé privée.

La clé privée, k (alice-private-key dans le code Python) doit satisfaire :

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alice garde sa clé privée secrète.

Ensuite, Alice calcule sa clé publique à l'aide de l'exponentiation modulaire. Inverser cette étape pour récupérer la clé privée est une instance du DLP, donc difficile à calculer sur des ordinateurs classiques lorsque de grands nombres premiers sont utilisés.

D'après l'explication mathématique ci-dessus, on sait que cela peut être calculé à l'aide de la formule :

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Comme d'habitude, Alice rend sa clé publique disponible via un canal qui n'est pas nécessairement secret.

Alice peut maintenant signer un message.

Pour le schéma de signature numérique, on doit générer un hachage $H(m)$ du message $m$ à signer.

Supposons qu'Alice et Bob s'accordent sur un algorithme de hachage particulier avec une longueur de hachage $N$ égale au nombre de bits dans $q$. Dans cet exemple simplifié, on va borner les sorties de notre fonction de hachage factice par $q$. La fonction de hachage ici est triviale : elle génère simplement un entier aléatoire.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

Ensuite, Alice doit générer un nombre secret aléatoire par message $k$ ainsi que son inverse multiplicatif modulo $q$ pour calculer la signature.

Un simple algorithme par force brute peut être utilisé pour calculer l'inverse modulaire. Il vaut mieux toutefois utiliser la fonction Python intégrée pow comme indiqué ci-dessous.

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Alice peut maintenant calculer la signature.

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

Note : il existe des conditions particulières qui nous obligeront à choisir une valeur différente pour $k$ si $r$ ou $s$ valent $0$. Dans ce cas, on génère une nouvelle valeur et on recommence.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice diffuse le message et sa signature au destinataire ou vérificateur, Bob.

Bob a préalablement obtenu la clé publique d'Alice et peut maintenant vérifier la signature pour authentifier son message.

Pour ce faire, il effectue quelques vérifications, puis recalcule un hachage du message diffusé par Alice et calcule les quantités auxiliaires $w, u_1, u_2$ et $v$.

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

Enfin, Bob vérifie si $v$ est égal à $r$. S'ils sont égaux, la signature est validée.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Sécurité du DSA

Avec l'informatique classique, la sécurité du DSA peut être influencée par plusieurs facteurs :

1. Taille des clés : Comme toujours, la taille des clés offre une protection de base contre les attaques par force brute. Les applications modernes qui utilisent DSA emploient des tailles de clés d'au moins 2 048 bits.

2. Qualité de $k$ : Dans DSA, chaque signature nécessite une valeur $k$ unique, aléatoire et secrète (voir ci-dessus). L'unicité, l'entropie et le secret de $k$ sont critiques, et une faiblesse dans l'un de ces aspects pourrait compromettre la clé privée $x$. Les générateurs de nombres aléatoires utilisés pour générer $k$ doivent eux-mêmes être sécurisés.

3. Robustesse de la fonction de hachage : Comme DSA utilise une fonction de hachage dans le processus de génération et de vérification de signature, une fonction de hachage faible pourrait compromettre la sécurité de la signature numérique. Par exemple, l'utilisation de SHA-1 avec DSA est dépréciée et SHA-2 ou supérieur est recommandé.

En plus de ces points, une implémentation DSA robuste doit également se prémunir contre d'autres types d'attaques ciblant la cryptographie à clé asymétrique comme décrit précédemment.

Échange de clés authentifié avec Diffie-Hellman et DSA

Les protocoles modernes de sécurité réseau, tels que Transport Layer Security (TLS) et bien d'autres, combinent les fonctionnalités d'échange de clés et d'authentification. Dans le contexte de Diffie-Hellman, l'authentification est nécessaire pour se protéger contre les attaques MITM. Dans les cellules de code suivantes, on illustre un exemple où Alice et Bob réalisent un échange de clés authentifié en combinant les protocoles Diffie-Hellman et DSA. Pour cela, on utilisera la bibliothèque Python cryptography.

Figure 2. Échange de clés authentifié avec Diffie-Hellman et DSA

D'abord, Alice et Bob s'accordent sur un ensemble de paramètres DH et génèrent chacun une paire de clés publique-privée DH.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

Les clés publiques DH sont diffusées. Ensuite, Alice et Bob génèrent chacun une paire de clés séparée pour utilisation avec DSA. Ces clés seront à leur tour utilisées pour signer les clés publiques DH à échanger.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice signe sa clé publique DH avec sa clé privée DSA.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

De même, Bob signe sa clé publique DH avec sa clé privée DSA.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

Les clés publiques DH et les signatures correspondantes sont maintenant diffusées par Alice et Bob. Ayant reçu la clé publique et la signature de leur interlocuteur, chaque partie vérifie ensuite la validité de la signature. Ainsi, une attaque MITM peut être prévenue, car Alice sait, par exemple, que la clé publique DH de Bob a bien été signée par Bob, et vice versa.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

Après la vérification des signatures, Alice et Bob génèrent le secret partagé, ce qui complète l'échange de clés.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

En option, pour une sécurité renforcée, Alice et Bob peuvent utiliser une fonction de dérivation de clés spécialisée comme HKDF pour générer une clé symétrique plus sécurisée à partir de leur secret partagé grâce à des techniques d'étirement de clé.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Casser Diffie-Hellman et DSA

Les protocoles Diffie-Hellman (DH) et DSA impliquent tous deux la génération de clés publiques de la forme $y = g^{x}~mod~p$, où la clé privée $x$ est le logarithme discret.

Un attaquant capable de résoudre une instance du DLP peut exposer la clé privée de l'une des deux parties et, en la combinant avec la clé publique de la seconde partie, accéder au secret partagé. Dans le cas du DSA, un attaquant capable de résoudre le DLP peut récupérer la clé privée du signataire, annulant ainsi le principe fondamental d'une signature numérique.

Sur les systèmes informatiques classiques, on pense que le DLP n'a pas de solution en temps polynomial. Mais comme l'a montré Peter Shor dans son article original de 1994, l'algorithme de Shor résout également le DLP en temps polynomial sur les ordinateurs quantiques.

L'algorithme de Shor et le problème du logarithme discret

L'algorithme de Shor est capable de résoudre le problème du logarithme discret en temps polynomial. Il tire principalement son efficacité de l'utilisation d'algorithmes quantiques capables de trouver la période d'une fonction qui dépend de l'entrée du problème, puis combine ce résultat avec des opérations plus conventionnelles.

Détails mathématiques de l'algorithme de Shor

L'algorithme de Shor fournit une solution efficace au DLP en le ramenant à un problème plus général en théorie des groupes, connu sous le nom de problème du sous-groupe caché (HSP).

Dans le HSP, on se donne un groupe algébrique $G$ et une fonction $f: G \rightarrow X$ de $G$ vers un ensemble $X$ telle que $f$ est constante sur chaque coset d'un sous-groupe $H$ de $G$ (et distincte sur les différents cosets). La tâche consiste alors à déterminer $H$. Il est connu que les ordinateurs quantiques peuvent résoudre le HSP sur des groupes abéliens finis en temps polynomial en $log~|G|$, où $|G|$ est l'ordre du groupe.

Dans le cas du DLP entier discuté dans cette leçon, la correspondance avec le HSP est la suivante :

• Soit $p$ un nombre premier et considérons le DLP donné par $y = g^r~mod~p$ où $g$ est un générateur de $(\mathbb{Z}_p)^{\times}$. Comme $g^{p-1} \equiv 1~mod~p$, $g$ est d'ordre $p-1$.
• Choisissons $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ où $\mathbb{Z}_{p-1}$ est le groupe des entiers modulo $(p-1)$.
• Choisissons $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ définie par $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$.
• Le noyau de $f$ est alors le sous-groupe $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$.
• $f$ est constante sur les cosets $(\delta, 0) + H_0$ et « cache » le sous-groupe $H_0$, définissant ainsi un HSP.

Sur cette base, l'algorithme quantique de Shor pour le DLP entier utilise un oracle quantique pour évaluer la fonction $f$ sur un état représentant une superposition uniforme sur $G$, puis utilise la transformée de Fourier quantique et des mesures avec estimation de phase pour produire des états quantiques permettant d'identifier le générateur $(r, 1)$ de $H_0$. De là, $r$, le logarithme discret recherché, peut être extrait.

L'article original de Shor contient une description détaillée de l'algorithme.

Cryptographie sur courbes elliptiques

La cryptographie sur courbes elliptiques (ECC), fondée sur les mathématiques des courbes elliptiques, offre une approche puissante de la cryptographie à clé asymétrique. L'ECC est connue pour offrir un niveau de sécurité comparable à des méthodes comme RSA, mais avec des clés plus courtes, ce qui la rend plus efficace et particulièrement bien adaptée aux systèmes à ressources limitées, tels que les systèmes embarqués et les appareils mobiles, où les économies de stockage et de calcul liées à des tailles de clés réduites sont très appréciées.

Principes de base de la cryptographie sur courbes elliptiques

Une courbe elliptique est typiquement de la forme $y^2 = x^3 + ax + b$ avec quelques propriétés intéressantes.

• Elle est symétrique horizontalement. Ainsi, pour tout point $(x,y)$ sur la courbe, son symétrique $(x,-y)$ est également sur la courbe.
• Toute droite non verticale n'intersecte la courbe qu'en trois points au maximum.

Figure 1. Opérations d'addition et de doublement de point sur une courbe elliptique. Le volet 1 définit P + Q = -R. Le volet 2 illustre le doublement de point 2Q = -P. Le volet 3 définit l'inverse additif d'un point comme son symétrique par rapport à l'axe des abscisses, c'est-à-dire P = -Q.

La cryptographie sur courbes elliptiques utilise une série d'opérations arithmétiques sur des points de la courbe. Chacune permet d'atteindre un nouveau point sur la courbe. C'est un processus simple à suivre dans un sens, et avec des tailles de clés plus courtes, il est plus efficace que d'autres algorithmes comme RSA — mais l'inverser est très difficile, d'où son application à la cryptographie.

Principes mathématiques de la cryptographie sur courbes elliptiques

Une courbe elliptique sur un corps algébrique $K$ est définie par une équation mathématique, typiquement de la forme $y^2 = x^3 + ax + b$ avec des coefficients $a, b \in K$ et décrit des points $(x, y) \in K \otimes K$ avec la contrainte supplémentaire que la courbe n'ait ni points de rebroussement ni auto-intersections.

Les propriétés des courbes elliptiques permettent de définir des opérations d'« addition » et de « multiplication scalaire » impliquant des points sur la courbe.

Addition : Si $P$ et $Q$ sont deux points sur une courbe elliptique, alors $P + Q$ désigne un troisième point unique identifié comme suit : on trace la droite passant par $P$ et $Q$ et on trouve le troisième point, $R$, où la droite intersecte à nouveau la courbe. On définit alors $P + Q = −R$, le point opposé à $R$ réfléchi par rapport à l'axe des $x$ (voir figure ci-dessous). Lorsque la droite passant par $P, Q$ n'intersecte pas la courbe en un point fini $(x, y)$, on dit qu'elle intersecte la courbe au point à l'infini $\mathbf{O}$.

L'addition sur les courbes elliptiques satisfait les propriétés algébriques d'un groupe avec le point à l'infini comme identité additive.

Doublement et multiplication scalaire : L'opération de doublement de point, qui correspond à la multiplication scalaire par $2$, est obtenue en posant $P = Q$ dans l'opération d'addition et correspond graphiquement à la tangente en $P$. La multiplication scalaire générale par un entier $n$ définie comme $nP = P + P + ...~n$ fois est obtenue par des doublements et additions successifs.

Problème du logarithme discret sur courbes elliptiques

Le problème du logarithme discret sur courbes elliptiques (ECDLP) présente de nombreuses similitudes avec le problème du logarithme discret discuté précédemment, reposant sur la difficulté de trouver des facteurs.

L'opération de multiplication scalaire sur les courbes elliptiques permet de définir le problème du logarithme discret sur courbes elliptiques :

Étant donnés des points $P, Q$ sur une courbe elliptique tels que $Q = nP$, déterminer $n$.

Ce problème est réputé insoluble en temps raisonnable sur les ordinateurs classiques pour des grandes valeurs de $n$ et constitue la base de la sécurité cryptographique.

Description mathématique de l'ECDLP

La cryptographie sur courbes elliptiques repose principalement sur l'ECDLP formulé sur certains corps finis algébriques. En 1999, le NIST a recommandé dix corps finis pour l'utilisation en ECC. Ce sont :

• Cinq corps premiers $\mathbb {F} _{p}$ pour des nombres premiers $p$ de taille $\{192, 224, 256, 384, 521\}$ bits.
• Cinq corps binaires $\mathbb {F} _{2^{n}}$ pour $n \in \{163, 233, 283, 409, 571\}$.

Avec cette configuration, un système de cryptographie asymétrique basé sur l'ECC dans le cas des corps premiers peut être spécifié comme suit :

• Choisir un $p$ dans la liste de valeurs recommandées par le NIST pour spécifier $\mathbb {F} _{p}$.

• Sélectionner les paramètres $a, b$ de la courbe elliptique.

• Choisir un point de base $G$ qui « génère » un sous-groupe cyclique sur la courbe d'ordre $n$ ; c'est-à-dire le plus petit entier tel que $nG = \mathbf{O}$.

• Calculer le cofacteur $h = |E(\mathbb {F} _{p})|/n$ où $|E(\mathbb {F} _{p})|$ est le nombre de points sur la courbe. $h$ est typiquement un petit entier.

• Les paramètres de domaine $(p, a, b, G, n, h)$ permettent de spécifier des clés asymétriques de cette manière :

  • La clé privée est un entier choisi aléatoirement $d$ avec autant de bits que dans le nombre premier $p$. Elle doit rester secrète.
  • La clé publique est le résultat de la « multiplication » du point de base $G$ par la clé privée $d$. On note généralement cela $Q = dG$.

Retrouver $d$ est équivalent à résoudre l'ECDLP, ce qui est supposé insoluble en temps raisonnable pour de grandes valeurs de $d$. L'ECDLP constitue donc la base des schémas d'échange de clés et de signatures numériques, en analogie directe avec les schémas Diffie-Hellman et DSA définis sur $(\mathbb{Z}_p)^{\times}$ discutés précédemment.

Échange de clés avec l'ECC

L'une des principales utilisations de l'ECC est dans le protocole d'échange de clés connu sous le nom de Diffie-Hellman sur courbes elliptiques (ECDH). Dans ECDH, chaque partie génère une paire de clés privée-publique puis échange les clés publiques. Chaque partie utilise ensuite sa propre clé privée et la clé publique de l'autre partie pour calculer un secret partagé, pouvant servir de clé pour le chiffrement symétrique.

Bien qu'il soit relativement facile d'effectuer une addition de points sur une courbe elliptique et de dériver une clé publique à partir d'une clé privée, il est computationnellement infaisable d'inverser le processus et de dériver une clé privée à partir d'une clé publique. Ce comportement « à sens unique » assure la sécurité de l'échange de clés ECDH.

Voici un exemple illustrant comment réaliser un échange de clés ECDH en Python avec la bibliothèque cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Signatures numériques avec l'ECC

L'ECC peut également être utilisée pour générer des signatures numériques à l'aide de l'algorithme de signature numérique sur courbes elliptiques (ECDSA). Dans ECDSA, le signataire crée une signature avec sa clé privée, et n'importe qui peut vérifier la signature à l'aide de la clé publique du signataire. Tout comme pour ECDH, la sécurité d'ECDSA repose sur l'ECDLP. Il est computationnellement infaisable pour quelqu'un de falsifier une signature sans accès à la clé privée du signataire.

Voici un exemple simple de transaction signer-et-vérifier avec ECDSA en Python et cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

Dans le code ci-dessus, si on modifie le message après qu'il a été signé, la vérification échouera, garantissant ainsi l'authenticité et l'intégrité du message.

Casser ECDH et ECDSA

De manière analogue au problème du logarithme discret entier, l'ECDLP s'avère difficile sur les ordinateurs classiques, mais possède une solution efficace sur les ordinateurs quantiques, là encore via l'algorithme de Shor. Nous vous renvoyons à la littérature récente pour une discussion sur la généralisation de l'algorithme de Shor au cas de l'ECDLP.

Résumé

Dans cette leçon, on a commencé par examiner les principales caractéristiques de la cryptographie à clé asymétrique (AKC) et discuté des considérations de sécurité de base qui sous-tendent les cryptosystèmes asymétriques. En particulier, on a introduit les deux principales applications de l'AKC — à savoir l'échange de clés et les signatures numériques — qui sont toutes deux des composantes essentielles des communications modernes sur Internet.

On a ensuite examiné le cryptosystème RSA qui, depuis les années 1970, s'est avéré d'une valeur immense pour sécuriser les communications numériques modernes en permettant l'échange de clés et les signatures numériques dans un cadre simple et polyvalent. La sécurité cryptographique de RSA vis-à-vis de l'informatique classique repose sur la difficulté de factoriser de grands entiers et nécessite des tailles de clés de l'ordre de 2 048 bits pour s'assurer que les entiers utilisés dans les applications pratiques sont suffisamment grands pour résister à la factorisation.

On a ensuite examiné l'échange de clés Diffie-Hellman (DH) et l'algorithme de signature numérique (DSA). La sécurité de ces schémas repose sur le problème du logarithme discret entier (DLP) : la clé privée est computationnellement difficile à extraire à partir de la clé publique, sans solution en temps polynomial sur les ordinateurs classiques. L'utilisation de clés aléatoires et uniques offre une sécurité supplémentaire contre les attaques. Les variantes sur corps finis entiers et sur courbes elliptiques des protocoles DH et DSA trouvent actuellement une utilisation généralisée dans de nombreux protocoles de communications numériques modernes tels que TLS, SSH, et bien d'autres.

Enfin, on a examiné la cryptographie sur courbes elliptiques. Avec sa taille de clé efficace et ses solides propriétés de sécurité, elle représente actuellement un excellent choix pour de nombreuses applications cryptographiques, de l'échange de clés aux signatures numériques.

Tous ces algorithmes sont exposés à des attaques par des algorithmes quantiques, car des solutions peuvent être développées pour résoudre les problèmes mathématiques sur lesquels repose leur conception. L'algorithme de Shor en est un exemple. Ils devront donc être remplacés par des cryptosystèmes asymétriques à sécurité quantique, plus résistants aux attaques quantiques tout en restant sûrs face aux algorithmes classiques. Les problèmes mathématiques sur lesquels ils s'appuient peuvent être résolus efficacement par des ordinateurs quantiques, ce qui nécessite le développement de cryptosystèmes asymétriques à sécurité quantique capables de résister aux attaques quantiques tout en maintenant la sécurité classique.