Chiffrement de clé publique

Cryptographie à clé publique

Contrairement à la cryptographie à clé symétrique, nous ne trouvons pas d'utilisation historique de la cryptographie à clé publique. C'est un concept relativement nouveau.

La cryptographie symétrique était bien adaptée pour les organisations telles que les gouvernements, l'armée et les grandes sociétés financières impliquées dans la communication classifiée.

Avec la propagation de réseaux informatiques non sécurisés au cours des dernières décennies, un réel besoin s'est fait sentir d'utiliser la cryptographie à plus grande échelle. La clé symétrique s'est avérée non pratique en raison des défis auxquels elle était confrontée pour la gestion des clés. Cela a donné naissance aux cryptosystèmes à clé publique.

Le processus de cryptage et de décryptage est décrit dans l'illustration suivante -

Les propriétés les plus importantes du schéma de chiffrement à clé publique sont:

  • Différentes clés sont utilisées pour le cryptage et le décryptage. C'est une propriété qui définit ce schéma différent du schéma de chiffrement symétrique.

  • Chaque récepteur possède une clé de déchiffrement unique, généralement appelée sa clé privée.

  • Le destinataire doit publier une clé de chiffrement, appelée sa clé publique.

  • Une certaine assurance de l'authenticité d'une clé publique est nécessaire dans ce schéma pour éviter l'usurpation d'identité par l'adversaire en tant que destinataire. Généralement, ce type de cryptosystème implique un tiers de confiance qui certifie qu'une clé publique particulière appartient à une personne ou une entité spécifique uniquement.

  • L'algorithme de chiffrement est suffisamment complexe pour empêcher l'attaquant de déduire le texte en clair du texte chiffré et de la clé de chiffrement (publique).

  • Bien que les clés privées et publiques soient liées mathématiquement, il n'est pas possible de calculer la clé privée à partir de la clé publique. En fait, une partie intelligente de tout système de cryptage à clé publique consiste à concevoir une relation entre deux clés.

Il existe trois types de schémas de chiffrement à clé publique. Nous en discutons dans les sections suivantes -

Cryptosystème RSA

Ce cryptosystème est l'un des systèmes initiaux. Il reste encore aujourd'hui le cryptosystème le plus utilisé. Le système a été inventé par trois chercheursRon Rivest, Adi Shamir, et Len Adleman et par conséquent, il est appelé cryptosystème RSA.

Nous verrons deux aspects du cryptosystème RSA, d'une part la génération de paires de clés et d'autre part les algorithmes de cryptage-décryptage.

Génération de la paire de clés RSA

Chaque personne ou partie qui souhaite participer à une communication en utilisant le cryptage doit générer une paire de clés, à savoir clé publique et clé privée. Le processus suivi dans la génération des clés est décrit ci-dessous -

  • Generate the RSA modulus (n)

    • Sélectionnez deux grands nombres premiers, p et q.

    • Calculez n = p * q. Pour un cryptage incassable fort, soit n un grand nombre, généralement un minimum de 512 bits.

  • Find Derived Number (e)

    • Nombre e doit être supérieur à 1 et inférieur à (p - 1) (q - 1).

    • Il ne doit y avoir aucun facteur commun pour e et (p - 1) (q - 1) sauf pour 1. En d'autres termes, deux nombres e et (p - 1) (q - 1) sont premiers.

  • Form the public key

    • La paire de nombres (n, e) forme la clé publique RSA et est rendue publique.

    • Fait intéressant, bien que n fasse partie de la clé publique, la difficulté à factoriser un grand nombre premier garantit que l'attaquant ne peut pas trouver en temps fini les deux nombres premiers (p & q) utilisés pour obtenir n. C'est la force de RSA.

  • Generate the private key

    • La clé privée d est calculée à partir de p, q et e. Pour n et e donnés, il existe un nombre unique d.

    • Le nombre d est l'inverse de e modulo (p - 1) (q - 1). Cela signifie que d est le nombre inférieur à (p - 1) (q - 1) tel que, multiplié par e, il est égal à 1 modulo (p - 1) (q - 1).

    • Cette relation s'écrit mathématiquement comme suit -

ed = 1 mod (p − 1)(q − 1)

L'algorithme euclidien étendu prend p, q et e comme entrée et donne d comme sortie.

Exemple

Un exemple de génération d'une paire de clés RSA est donné ci-dessous. (Pour faciliter la compréhension, les nombres premiers p & q pris ici sont de petites valeurs. En pratique, ces valeurs sont très élevées).

  • Soit deux nombres premiers p = 7 et q = 13. Ainsi, module n = pq = 7 x 13 = 91.

  • Sélectionnez e = 5, ce qui est un choix valide car il n'y a pas de nombre qui est le facteur commun de 5 et (p - 1) (q - 1) = 6 × 12 = 72, sauf pour 1.

  • La paire de nombres (n, e) = (91, 5) forme la clé publique et peut être mise à la disposition de toute personne que nous souhaitons pouvoir nous envoyer des messages chiffrés.

  • Entrez p = 7, q = 13 et e = 5 dans l'algorithme euclidien étendu. La sortie sera d = 29.

  • Vérifiez que le d calculé est correct en calculant -

de = 29 × 5 = 145 = 1 mod 72

  • Par conséquent, la clé publique est (91, 5) et les clés privées est (91, 29).

Cryptage et décryptage

Une fois que la paire de clés a été générée, le processus de cryptage et de décryptage est relativement simple et facile en termes de calcul.

Fait intéressant, RSA n'opère pas directement sur des chaînes de bits comme dans le cas d'un cryptage à clé symétrique. Il fonctionne sur les nombres modulo n. Par conséquent, il est nécessaire de représenter le texte en clair comme une série de nombres inférieurs à n.

Chiffrement RSA

  • Supposons que l'expéditeur souhaite envoyer un message texte à quelqu'un dont la clé publique est (n, e).

  • L'expéditeur représente alors le texte brut sous la forme d'une série de nombres inférieurs à n.

  • Pour crypter le premier texte brut P, ​​qui est un nombre modulo n. Le processus de cryptage est une simple étape mathématique car -

C = Pe mod n

  • En d'autres termes, le texte chiffré C est égal au texte clair P multiplié par lui-même e fois puis réduit modulo n. Cela signifie que C est également un nombre inférieur à n.

  • Revenant à notre exemple de génération de clé avec le texte brut P = 10, nous obtenons le texte chiffré C -

C = 105 mod 91

Décryptage RSA

  • Le processus de décryptage pour RSA est également très simple. Supposons que le récepteur de la paire de clés publiques (n, e) a reçu un texte chiffré C.

  • Le récepteur élève C à la puissance de sa clé privée d. Le résultat modulo n sera le texte en clair P.

Plaintext = Cd mod n

  • Pour revenir à notre exemple numérique, le texte chiffré C = 82 serait déchiffré au numéro 10 en utilisant la clé privée 29 -

Plaintext = 8229 mod 91 = 10

Analyse RSA

La sécurité de RSA dépend des atouts de deux fonctions distinctes. Le cryptosystème RSA est le cryptosystème à clé publique le plus populaire dont la force est basée sur la difficulté pratique de factoriser les très grands nombres.

  • Encryption Function - Il est considéré comme une fonction unidirectionnelle de conversion du texte clair en texte chiffré et il ne peut être inversé qu'avec la connaissance de la clé privée d.

  • Key Generation- La difficulté de déterminer une clé privée à partir d'une clé publique RSA équivaut à la factorisation du module n. Un attaquant ne peut donc pas utiliser la connaissance d'une clé publique RSA pour déterminer une clé privée RSA à moins qu'il ne puisse factoriser n. C'est aussi une fonction unidirectionnelle, passer des valeurs p & q au module n est facile mais l'inverse n'est pas possible.

Si l'une de ces deux fonctions est prouvée non unidirectionnelle, alors RSA sera interrompu. En fait, si une technique d'affacturage efficace est développée, le RSA ne sera plus sûr.

La puissance du cryptage RSA diminue considérablement contre les attaques si les nombres p et q ne sont pas de grands nombres premiers et / ou si la clé publique choisie e est un petit nombre.

Cryptosystème ElGamal

Outre RSA, d'autres systèmes de cryptage à clé publique sont proposés. Beaucoup d'entre eux sont basés sur différentes versions du problème du logarithme discret.

Le cryptosystème ElGamal, appelé Variante de courbe elliptique, est basé sur le problème du logarithme discret. Il dérive la force de l'hypothèse que les logarithmes discrets ne peuvent pas être trouvés dans la période de temps pratique pour un nombre donné, tandis que l'opération inverse de la puissance peut être calculée efficacement.

Passons en revue une version simple d'ElGamal qui fonctionne avec les nombres modulo p. Dans le cas des variantes de courbes elliptiques, il est basé sur des systèmes de nombres assez différents.

Génération de la paire de clés ElGamal

Chaque utilisateur d'ElGamal cryptosystem génère la paire de clés comme suit -

  • Choosing a large prime p. Généralement, un nombre premier de 1024 à 2048 bits est choisi.

  • Choosing a generator element g.

    • Ce nombre doit être compris entre 1 et p - 1, mais ne peut pas être un nombre quelconque.

    • C'est un générateur du groupe multiplicatif d'entiers modulo p. Cela signifie que pour chaque entier m co-premier à p, il existe un entier k tel que g k = un mod n.

      Par exemple, 3 est le générateur du groupe 5 (Z 5 = {1, 2, 3, 4}).

N 3 n 3 n mod 5
1 3 3
2 9 4
3 27 2
4 81 1

  • Choosing the private key. La clé privée x est n'importe quel nombre supérieur à 1 et inférieur à p − 1.

  • Computing part of the public key. La valeur y est calculée à partir des paramètres p, g et de la clé privée x comme suit -

y = gx mod p

  • Obtaining Public key. La clé publique ElGamal se compose des trois paramètres (p, g, y).

    Par exemple, supposons que p = 17 et que g = 6 (On peut confirmer que 6 est un générateur du groupe Z 17 ). La clé privée x peut être n'importe quel nombre supérieur à 1 et inférieur à 71, nous choisissons donc x = 5. La valeur y est alors calculée comme suit -

y = 65 mod 17 = 7

  • Ainsi, la clé privée est 62 et la clé publique est (17, 6, 7).

Cryptage et décryptage

La génération d'une paire de clés ElGamal est comparativement plus simple que le processus équivalent pour RSA. Mais le cryptage et le décryptage sont légèrement plus complexes que RSA.

Chiffrement ElGamal

Supposons que l'expéditeur souhaite envoyer un texte en clair à quelqu'un dont la clé publique ElGamal est (p, g, y), alors -

  • L'expéditeur représente le texte en clair sous la forme d'une série de nombres modulo p.

  • Pour crypter le premier texte clair P, qui est représenté par un nombre modulo p. Le processus de cryptage pour obtenir le texte chiffré C est le suivant -

    • Générer aléatoirement un nombre k;
    • Calculez deux valeurs C1 et C2, où -
C1 = gk mod p
C2 = (P*yk) mod p

  • Envoyez le texte chiffré C, composé des deux valeurs distinctes (C1, C2), envoyés ensemble.

  • En référence à notre exemple de génération de clé ElGamal donné ci-dessus, le texte brut P = 13 est chiffré comme suit -

    • Générer au hasard un nombre, disons k = 10
    • Calculez les deux valeurs C1 et C2, où -
C1 = 610 mod 17
C2 = (13*710) mod 17 = 9

  • Envoyez le texte chiffré C = (C1, C2) = (15, 9).

Décryptage ElGamal

  • Pour déchiffrer le texte chiffré (C1, C2) à l'aide de la clé privée x, les deux étapes suivantes sont effectuées -

    • Calculez l'inverse modulaire de (C1) x modulo p, qui est (C1) -x , généralement appelé facteur de décryptage.

    • Obtenez le texte brut en utilisant la formule suivante -

C2 × (C1)-x  mod p = Plaintext

  • Dans notre exemple, pour déchiffrer le texte chiffré C = (C1, C2) = (15, 9) en utilisant la clé privée x = 5, le facteur de déchiffrement est

15-5  mod 17 = 9

  • Extraire le texte brut P = (9 × 9) mod 17 = 13.

Analyse ElGamal

Dans le système ElGamal, chaque utilisateur dispose d'une clé privée x. et athree components de clé publique - prime modulus p, generator g, and public Y = gx mod p. La force de l'ElGamal est basée sur la difficulté du problème de logarithme discret.

La taille de la clé sécurisée est généralement> 1024 bits. Aujourd'hui, même une clé de 2048 bits est utilisée. Sur le front de la vitesse de traitement, Elgamal est assez lent, il est principalement utilisé pour les protocoles d'authentification par clé. En raison de l'efficacité de traitement plus élevée, les variantes de courbe elliptique d'ElGamal sont de plus en plus populaires.

Cryptographie à courbe elliptique (ECC)

La cryptographie à courbe elliptique (ECC) est un terme utilisé pour décrire une suite d'outils et de protocoles cryptographiques dont la sécurité est basée sur des versions spéciales du problème du logarithme discret. Il n'utilise pas de nombres modulo p.

ECC est basé sur des ensembles de nombres associés à des objets mathématiques appelés courbes elliptiques. Il existe des règles pour ajouter et calculer des multiples de ces nombres, tout comme pour les nombres modulo p.

ECC comprend des variantes de nombreux schémas cryptographiques initialement conçus pour les numéros modulaires tels que le cryptage ElGamal et l'algorithme de signature numérique.

On pense que le problème du logarithme discret est beaucoup plus difficile lorsqu'il est appliqué à des points sur une courbe elliptique. Cela invite à passer des nombres modulo p aux points sur une courbe elliptique. Un niveau de sécurité équivalent peut également être obtenu avec des clés plus courtes si nous utilisons des variantes basées sur des courbes elliptiques.

Les touches plus courtes offrent deux avantages -

  • Facilité de gestion des clés
  • Calcul efficace

Ces avantages rendent les variantes de schéma de chiffrement basées sur des courbes elliptiques très attrayantes pour les applications où les ressources informatiques sont limitées.

Schémas RSA et ElGamal - Une comparaison

Comparons brièvement les schémas RSA et ElGamal sur les différents aspects.

RSA ElGamal
C'est plus efficace pour le cryptage. Il est plus efficace pour le décryptage.
Il est moins efficace pour le décryptage. Il est plus efficace pour le décryptage.
Pour un niveau de sécurité particulier, de longues clés sont requises dans RSA. Pour le même niveau de sécurité, des clés très courtes sont nécessaires.
Il est largement accepté et utilisé. C'est nouveau et pas très populaire sur le marché.