Une plongée profonde dans la cryptographie –

Cette plongée profonde dans la cryptographie a été initialement publiée sur le site de Bruno's Bitfalls et est reproduite ici avec la permission.

Les médias sont bourrés de contenu sur cryptocurrency et tout le monde s'extasie sur l'importance des clés publiques et privées . Vous avez entendu parler de cryptage, mais savez-vous ce que c'est réellement et comment cela fonctionne?

Ce post vous ramènera aux bases et expliquera le cryptage décrira les différents types, et démontrera l'algorithme exemples, tous d'une manière conviviale pour les débutants. Si vous avez déjà voulu comprendre cela, mais cela vous a semblé trop compliqué, vous allez adorer ce post.

Cryptographie

La cryptographie transforme, en un mot, un message en un format qui n'a de sens que pour le le destinataire, et pas n'importe qui qui pourrait mettre la main dessus entre les deux.

Quel est le problème que nous essayons de résoudre?

Supposons qu'il y ait deux personnes qui veulent échanger des messages cryptés, indépendamment du canal de communication utilisez – lettres, SMS, e-mail … Ils doivent d'abord se mettre d'accord sur un ensemble de règles à appliquer lors du cryptage ou du décryptage du message. Ces règles sont un ensemble d'une ou plusieurs fonctions qui doivent avoir une contre-fonction . C'est-à-dire, si une fonction donnée est utilisée pour crypter un message, alors il doit exister une contre-fonction pour le déchiffrer. En langage mathématique, une telle fonction est bijective .

L'expéditeur du message applique une fonction à un ensemble d'informations et obtient une version cryptée de cette information qui peut ensuite être envoyée au destinataire. Le destinataire applique la contre-fonction pour extraire les informations vraies de la version cryptée du message. Si quelqu'un au milieu intercepte cette communication mais ne dispose pas du contre-système pour déchiffrer le message, il sera incapable de le lire.

Alice et Bob

Faisons en sorte que cela soit plus clair avec l'aide d'un exemple trivial. Supposons que Bob veuille envoyer un SMS contenant "JE T'AIME" à Alice, mais ne risque pas d'être vu par quelqu'un d'autre. (Quelqu'un choisissant le téléphone d'Alice verrait le message.) Pour réussir à échanger des messages cryptés, Alice et Bob doivent se mettre d'accord sur la façon de crypter / décrypter les messages. Supposons que ceci soit l'accord:

Chaque lettre du message sera remplacée par le numéro d'index à deux chiffres de cette dernière dans l'alphabet anglais. "A" sera "01", "B" sera "02", etc. "00" indiquera un caractère d'espace. C'est leur fonction de cryptage / décryptage, et c'est bijective.

Bob enverra donc le message:

 09001215220500251521

Si quelqu'un intercepte ce message, cela n'aura pas beaucoup de sens pour eux. Leur amour restera un secret. Alice, d'autre part, sera capable de le déchiffrer facilement et de rougir.

Cryptage symétrique (avec une clé privée)

L'approche décrite ci-dessus est appelée cryptage à clé privée symétrique . "Symétrique" indique que le message peut être chiffré et décrypté en utilisant la même clé (secret). La clé (secret) est en fait la fonction de remplacement lettre-nombre-lettre-lettre que nous avons décrite. Cela ressemble un peu à ceci:

Un système comme celui-ci peut sembler parfait à première vue. Bien sûr, une fonction bijective plus complexe est nécessaire pour rendre cette communication vraiment sûre. Le système en tant que tel est parfaitement sûr tant qu'Alice et Bob peuvent se rencontrer et organiser au préalable une méthode de cryptage / décryptage. Mais que se passe-t-il si, comme dans la plupart des cas aujourd'hui, les personnes qui communiquent ne sont pas physiquement proches, ou ne se connaissent même pas? Comment peuvent-ils échanger une clé secrète en toute sécurité sans risque de tomber entre de mauvaises mains?

C'est le plus gros inconvénient d'un tel cryptage à clé partagée: il doit y avoir un canal sécurisé pré-établi pour échanger la clé.

Une solution possible

Il est clair que, à moins qu'un canal sécurisé n'existe déjà, il est presque impossible d'échanger la clé privée en toute sécurité. Si le canal existe déjà, alors il n'y a pas besoin d'un autre canal.

La solution n'est pas de trouver un moyen sûr d'échanger la clé, mais d'éliminer complètement le besoin d'un tel échange. Cela peut être accompli en ajoutant une autre clé dans le mélange. L'un d'entre eux serait utilisé uniquement pour le cryptage, l'autre pour le décryptage.

La clé de cryptage pourrait être accessible à tous. En fait, doit être accessible à tous, car sans lui, il est impossible de chiffrer les messages et de les envoyer au destinataire. Cette clé est appelée la clé publique .

L'autre clé est utilisée uniquement pour le décryptage et ne doit être envoyée à personne. Seul le destinataire des informations chiffrées l'a, et nous appelons celui-ci la clé privée .

Chiffrement asymétrique (avec une clé publique)

à l'image ci-dessus, nous pouvons voir qu'il n'y a pas besoin d'un canal sécurisé pour échanger des clés. L'asymétrie réside dans le fait qu'il est impossible de crypter et déchiffrer le message avec la même clé. Un séparé est nécessaire pour chaque action.

Si Bob veut envoyer un message crypté à Alice, il doit avoir sa clé publique. Cette clé publique pourrait lui être directement transmise par Alice, ou elle pourrait simplement la publier sur son site Web où n'importe qui qui veut lui envoyer un message crypté peut le trouver. Quand Alice reçoit le message chiffré avec sa clé publique, elle utilise la clé privée pour la déchiffrer, ce qui rend le message encore lisible.

Si Alice veut envoyer une réponse, elle a maintenant besoin de la clé publique de Bob. La procédure est identique: elle crypte le message, l'envoie, et seul Bob peut le décrypter avec sa clé privée.

Il est important de noter que pour rendre ce type de communication réalisable, les clés doivent être générées avec des procédures assez complexes pour compenser la capacité de n'importe quel ordinateur de les deviner pendant un laps de temps déraisonnable.

Comment ça marche?

Si vous ne comprenez pas complètement les termes dans la section ci-dessous, ne vous inquiétez pas. Lisez-les superficiellement; ils seront expliqués sur un exemple immédiatement après.

Pour rendre impossible de déchiffrer un message avec seulement la clé publique, ou pour dériver la clé privée de la clé publique, des fonctions mathématiques unidirectionnelles sont utilisées. Une fonction unidirectionnelle est telle que f (x) peut être calculé pour n'importe quel x mais pas l'inverse. Par exemple, si nous savons que la somme est de 950, nous ne pouvons pas deviner quels nombres nous avons additionnés pour l'obtenir parce que le nombre de combinaisons possibles est infini.

Il existe de nombreux algorithmes pour calculer les fonctions. Nous allons démontrer un tel algorithme ci-dessous: il s'appelle l'algorithme RSA, basé sur les initiales des noms de ses créateurs en 1977 (Ron Rivest, Adi Shamir, Leonard Adleman)

1. Sélectionnez 2 primaire nombres – nombres divisibles seulement par 1 ou eux-mêmes. Par exemple:

2. Multipliez-les n = pxq :
   n = 61 x 53 = 3233

3. Calculez le multiple commun le plus bas λ (n) (p-1 ) i (q-1) :
   nzv (p-1, q-1) = nzv (60,52) = 780 . Cela peut être fait avec l'algorithme présenté ici .

4. Choisissez n'importe quel nombre entre 1 et le multiple calculé précédemment, de sorte que ce nombre soit relativement premier ou coprime aux deux nombres initiaux . Les nombres sont coprimes si le seul nombre positif qui les divise est 1. Dans ce cas, c'est e = 17 .

5. Calculez l'inverse multiplicatif modulaire de e (mod nzv) . Nous cherchons d tel que:

   • (dxe) mod nzv = 1
   • (dx 17) mod 780 = 1
   • d = 413

6. Ces calculs produisent tous les composants nécessaires d'un ensemble de clés publiques et privées. La clé publique est la paire (n, e) et la clé privée est (n, d) . Ainsi, la clé publique est (n = 3233, e = 17) . La clé publique sert à chiffrer les messages via la formule suivante:

   c (m) = m ¹⁷ mod 3233

   La clé privée est (n = 3233, d = 413) . Il est utilisé pour déchiffrer un message:

   m (c) = c ⁴¹³ mod 3233

Maintenant que nous avons les fonctions de cryptage et de décryptage, nous pouvons revenir à notre Alice et Bob scénario. Puisque ces fonctions ne peuvent traiter que des nombres, nous devons d'abord transformer les lettres en chiffres. La table ASCII – une norme utilisée par les ordinateurs pour travailler avec des lettres sur des systèmes informatiques – peut être utile. Concentrons-nous uniquement sur les majuscules ici

Pour chaque code ASCII du message de Bob, nous besoin de calculer le c (m) . Comme le message est "JE T'AIME", l'ASCII de la première lettre est 73. c (73) est:

c (m) = m ¹⁷ mod 3233
c (73) = 73 ¹⁷ mod 3233
c (73) = 47477585226700098686074966922953 mod 3233
c (73) = 1486

Calculons également le repos

Espace: c (32) = 32 ¹⁷ mod 3233 = 1992
L: c (76) = 76 ¹⁷ mod 3233 = 2726
O: c (79) = 79 ¹⁷ mod 3233 = 1307
V: c (86) = 86 ¹⁷ mod 3233 = 1906
E: c (69) = 69 ¹⁷ mod 3233 = 28
O: c (89) = 89 ¹⁷ mod 3233 = 99
U: c (85) = 85 ¹⁷ mod 3233 = 2310

La fonction de cryptage calcule le mod 3233 (division reste quand divisant avec 3233) donc le résultat d'une lettre s chiffrement ne peut pas être plus de 3232, ce qui signifie que quatre est le nombre maximal de chiffres dans la version cryptée de chaque lettre. Par conséquent, nous pad chaque nombre avec des zéros sur le côté gauche: 1486, 1992, 2726, 1307, 1906, 0028, 1992, 0099, 1307, 2310.

Le message complet est:

 ] 1486199227261307190600281992009913072310

Alice a sa clé privée, et peut l'utiliser pour déchiffrer ceci. Elle utilisera la fonction inversée précédemment définie m (c) = c ⁴¹³ mod 3233 où c est le message crypté. La fonction inversée montre que mod 3233 est calculé, et que chaque lettre peut être au plus 3232 et avoir quatre chiffres. Ainsi, Alice sait que le message doit être divisé en séries de quatre, les zéros de tête de chaque étant sans signification:

 1486 1992 2726 1307 1906 (00) 28 1992 (00) 99 1307 2310

Décryptons 1486:

m (c) = c ⁴¹³ mod 3233
m (1486) = 1486 ⁴¹³ mod 3233
m (1486) = 1,1060335282256977039647849058382e + 1310 mod 3233
m (1486) = 73

Nous avons obtenu le numéro 73, qui correspond à la lettre "I" selon la table ASCII. En suivant le même processus, nous pouvons déchiffrer le reste du message:

m (1992) = 1992 ⁴¹³ mod 3233 = 32 ASCII 32 = razmak
m (2726) = 2726 ⁴¹³ mod 3233 = 76 ASCII 76 = L
m (1307) = 1307 ⁴¹³ mod 3233 = 79 ASCII 79 = O
m (1906) = 1906 ⁴¹³ mod 3233 = 86 ASCII 86 = V
m (28) = 28 ⁴¹³ mod 3233 = 69 ASCII 69 = E
m (1992) = 1992 ⁴¹³ mod 3233 = 32 ASCII 32 = razmak
m (99) = 99 ⁴¹³ mod 3233 = 89 ASCII 89 = Y
m (1307) = 1307 ⁴¹³ mod 3233 = 79 ASCII 79 = O
m (2310) = 2310 ⁴¹³ mod 3233 = 85 ASCII 85 = U

Réitérons pourquoi le cryptage asymétrique est meilleur que le cryptage symétrique. Avec le chiffrement symétrique, une seule clé est utilisée pour déchiffrer et chiffrer les messages. Si les participants veulent communiquer en toute sécurité, ils doivent d'abord échanger cette clé en toute sécurité. S'ils sont physiquement éloignés, cela devient un gros problème. Avec le cryptage asymétrique, il y a une clé publique que nous pouvons donner librement et que les gens peuvent utiliser pour crypter les messages qui nous sont destinés. Notre clé privée reste secrète et n'est utilisée que pour déchiffrer les messages que nous recevons. Il n'y a pas besoin d'un canal sécurisé par lequel échanger une clé secrète, ce qui rend le chiffrement asymétrique beaucoup plus sûr que le chiffrement symétrique.

Mais serait-il possible de calculer la clé privée à partir de la clé publique? une touche  » width= »1000″ height= »318″ class= »aligncenter size-full wp-image-165922″/>

Deviner la clé privée RSA

Regardons les fonctions une fois de plus:

• Chiffrer: F (x) = x ^e mod (pxq)
• Décrypter: F ^-1 (c) = c ^d mod (pxq)

La fonction de cryptage – c'est-à-dire, (pxq, e) paire – représente une clé publique. Si nous connaissons cette paire et que nous voulons calculer la clé privée, nous devons trouver les nombres p et q . Cela signifie que nous devons factoriser le produit de p x q . Si nous supposons que les nombres p et q sont des nombres de 1024 bits, alors leur produit est un nombre de 2048 bits – un nombre avec 617 chiffres si représenté comme nombre décimal. Pour factoriser un si grand nombre, même le supercalculateur le plus puissant aurait besoin d'une quantité absurde de temps, rendant le processus une impossibilité mathématique.

Techniquement il n'est pas impossible de factoriser le nombre. Il existe des algorithmes spéciaux développés à cette fin, et le plus efficace actuellement est GNFS (General Number Field Sieve) . C'est particulièrement pratique pour la factorisation de nombres de plus de 110 chiffres. Le tableau ci-dessous indique le temps nécessaire pour factoriser un grand nombre exprimé en MIPS ( Millions d'instructions par seconde ). En conséquence, une année MIPS est le nombre d'opérations informatiques exécutables en un an par un ordinateur avec la puissance de 1 MIPS. Ce nombre est 3.1536 x 10 ¹³ .

Si nous supposons que l'algorithme appliqué multiplie les nombres de 1024 bits, produisant un produit de 2048 bits et que les CPU les plus puissants d'aujourd'hui ont environ 300.000 MIPS le nombre devient assez élevé. Même les ordinateurs quantiques les plus puissants d'aujourd'hui, avec 100 millions de MIPS (ce qui est rare, s'ils existent), auraient besoin de 3 000 000 000 000 d'années pour factoriser un nombre de 2 048 bits

Mersenne

idée principale derrière l'algorithme RSA, il est de plus en plus important de trouver de grands nombres premiers. Il y a une sous-classe de nombres premiers appelés nombres premiers de Mersenne, et ils ressemblent à ceci: 2 ⁿ -1. Ils ont été nommés d'après un frère français qui a été le premier à identifier (à tort) 11 d'entre eux. Il y a un grand mouvement autour de trouver les plus grands nombres premiers possibles de Mersenne ces jours. (Vous pouvez trouver les détails à Mersenne.org .) Le dernier (49e) et le plus grand nombre de Mersenne à ce jour a été trouvé le 7 janvier 2016. Il est 2 ^74.207.281 -1 et a 22 338 618 chiffres. Celui d'avant, il a été trouvé le 1er janvier 2013: il était 2 ^57.885.161 -1 et il a presque 5 millions de chiffres de moins que le 49ème nombre.

Un fait amusant sur les nombres premiers: le FEP , Electronic Frontier Foundation, a des primes sur les grands nombres premiers. Leur site Web énumère ces primes et montre que la récompense de 50 000 $ pour avoir obtenu un prime de 1 million de chiffres et la récompense de 100 000 $ pour avoir obtenu un prime de 10 millions de dollars ont été récompensées de 150 000 $ et 250 000 $ pour 100 millions et 1 milliard de chiffres respectivement sont toujours en attente. Vous avez une bonne idée d'algorithme?

Asymmetric Encryption et Bitcoin

Alors qu'est-ce que tout cela a à voir avec la crypto-monnaie, autre que le partage du nom "crypto"?

Alors que ce qui suit s'applique à presque toutes les cryptocurrences, prenons le plus célèbre – Bitcoin – à titre d'exemple. Bitcoin utilise également une paire de clés publique / privée. La clé publique – ou au moins une forme de celle-ci – est l'adresse à laquelle vous pouvez envoyer des Bitcoins. Comme avec les messages cryptés où une clé publique est nécessaire pour que quelqu'un puisse nous envoyer un message, avec Bitcoin, une clé publique est nécessaire pour que quelqu'un puisse nous envoyer de l'argent. D'autre part, une clé privée nous permet de confirmer, d'approuver et d'effectuer une transaction avec laquelle nous envoyons certains de nos bitcoins de notre adresse (compte) à la clé publique de quelqu'un d'autre (adresse).

L'idée est similaire, mais Bitcoin a une approche différente pour calculer la clé privée et publique. La clé privée de Bitcoin est un nombre de 256 bits. Nous avons généralement affaire à un grand nombre choisi au hasard parmi un ensemble de 2 numéros ²⁵⁶ . C'est un peu plus de 10 ⁷⁷ choix possibles. Cela peut sembler peu, mais si l'on considère l'estimation qu'il y a 10 ⁸⁰ atomes dans l'univers entier, la taille de ce nombre peut encore nous faire réfléchir et réfléchir. Le simple fait de compter tous ces nombres à la vitesse d'un milliard par seconde prendrait plus de temps que l'âge de l'univers.

Nous avons donc une clé privée que nous connaissons et que personne ou aucun ordinateur ne peut deviner. une quantité de temps raisonnable. Dans le protocole Bitcoin, la clé privée est utilisée pour calculer la clé publique en utilisant l'algorithme ECC, Elliptic-curve cryptography . Cet algorithme est basé sur une courbe dont la fonction peut être mathématiquement exprimée par y ² = x ³ + ax + b . Le résultat est la clé publique. Cette URL et cette URL expliquent l'algorithme en détail si cela vous intéresse

Avec Bitcoin, la clé publique n'est pas l'adresse à laquelle envoyer de l'argent, mais elle peut être facilement calculé en utilisant la formule suivante:

 address = RIPEMD160 (SHA256 (clé publique))

Cette URL contient des détails sur le processus si vous êtes intéressé.

Conclusion

Il est important de se souvenir de la différence entre l'encodage et le cryptage. L'encodage est le processus consistant à rendre le message envoyé aussi identique à l'original que possible afin de minimiser les erreurs. Le cryptage rend le message illisible pour tout le monde sauf le destinataire prévu.

Il existe plusieurs types de cryptage, les principaux étant asymétriques et symétriques. Nous avons couvert le premier dans cet article, et expliqué que contrairement au cryptage symétrique, le cryptage asymétrique introduit une clé publique et privée plutôt qu'une seule clé privée partagée entre les parties, permettant une communication sécurisée sur des canaux non sécurisés.

l'avantage du cryptage asymétrique devient évident en crypto-monnaie, où la clé publique est utilisée pour recevoir des fonds et vérifier l'équilibre et les transactions, alors que la clé privée est la seule façon de signer réellement les messages et d'envoyer les jetons. [19459178] Bruno développeur de blockchain et auditeur de code de Croatie avec des maîtrises en informatique et en langue et littérature anglaise. Il a été développeur web pendant 10 ans jusqu'à ce que JavaScript le conduise. Il dirige maintenant une entreprise de cryptomonnaie à Bitfalls.com via laquelle il rend la technologie blockchain accessible aux masses, et gère Coinvendor une plate-forme d'intégration permettant aux gens d'acheter facilement de la crypto-monnaie. Il est également un développeur évangéliste pour Diffbot.com un grattoir web basé sur la technologie de l'IA basée à San Francisco. En savoir plus sur ses antécédents avec la blockchain ici .