Data & Security/Donnée & Sécurité #2: Asymmetric Ciphers/Chiffrement asymétrique

Last time, I discussed how symmetric cryptography has long been in use for transmitting secret messages. Despite all of its advantages, we did point out some problems with symmetric ciphers: they require you to safely exchange keys and some can now be easily broken thanks to the newest technologies in computer science. Today, I’ll talk more about the counterpart: asymmetric cryptography. I’ll discuss its pros and cons compared to symmetric cryptography and I’ll also give a very rough picture of a possible game-changer: quantum cryptography.

Keys exchange: the Diffie-Hellman protocol aka “it’s hard to unmix colors!”

The Diffie-Hellman exchange key technique is not used to encrypt and transmit the messages directly but rather, as its name implies, the keys themselves. It is therefore used before any true “conversation”, to insure that both the emitting and the receiving end have the correct keys while still avoiding sending the encryption and decryption keys in plain text (since this is a dangerous moment during which a third party could steal the key and then easily spy on the upcoming transmissions).

This method relies on the idea that, thanks to the magic of mathematics (and more precisely of group theory ;)), it is possible to:

  • get to the same point using two different paths
  • and to make it really hard to find this point if you don’t know any of those paths

To be a bit more concrete: say you have two people who want to exchange secrets: Alice and Bob.

Note: “Alice” and “Bob” are the usual names of the emitting and receiving ends in cryptography, as was initially suggested by Rivest, Shamir and Adleman (see below for more detail on them!) in their 1978 paper “A Method for Obtaining Digital Signatures and Public-key Cryptosystems”. There is a whole cast of characters that goes along with them in which the malicious third-party is often referred to as “Chuck” and the sly eaves-dropping character is often nicknamed “Eve”.

They want to send secret messages (for example using one of the quick-and-easy symmetric cryptography technique discussed last time) to each other but, first, they need to agree on a key. They have no way of meeting in person so they need to send the keys via a network… which means they need to be very careful so it doesn’t get stolen!

So, how does the DH key exchange work? Well:

  1. to begin with, they will decide on a common “base” for their key: this is something that is simply written in plain online on their network without any additional care for security – the whole point of the exchange is to transform this initial key into another un-guessable equivalent.
  2. then, they will both choose a “secret”: each one will have their own and it will not be sent to the other. In practice, both those steps consists in choosing numbers; therefore Alice and Bob can combine them into two “mixed up” pieces of data. These are components of the final key that can be sent over the network safely, too.
  3. this “mixed up” data is put on the network to exchange it with the other participant: Alice retrieves Bob’s and Bob retrieves Alice’s
  4. now, each participant recombines the other’s “mixed up” data with their own “secret”
  5. and tadaa! Alice and Bob have now produced a “common secret”, the key they will use to cipher the rest of the messages – this key has remained secret because they both rebuilt it locally and did not share it at any point in the process

The important thing is to use the right kind of “combination” during steps (2) and (4). Using group theory, you can find ways to assemble numbers that verify the two points mentioned before: you make sure Alice and Bob end up with the same key in the end (otherwise the whole process is quite useless!) and you also insure that it is hard (meaning not feasible in practice) to decompose the middle “mixed up” shared data into the original “secrets”.

The Diffie-Hellman key exchange process can be represented by the following diagram:

Representation of the Diffie-Hellman exchange key process (originally by A.J. Han Vinck, University of Duisburg-Essen; reproduced by Flugaal, here: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange)

Note: for the ones into math: as explained in the wiki, the “combination” in the DH exchange key process is usually exponentiation over multiplicative groups of integers modulo p. The whole logic relies on the fact that, modulo p, you get:

Here: a is Alice’s secret, b is Bob’s secret, A is the “mixed up” data sent by Alice, B is the “mixed up” data sent by Bob and gab = gba is the common secret.

When you take big enough numbers, it is almost impossible to crack the ciphered keys. While modern computers can combine the secrets and the “mixed up” shared data very quickly (by performing modular exponentiation), they cannot currently do the reverse it for numbers containing 600 digits or more (this is the discrete logarithm problem). This means that nowadays this technique is a safe way of agreeing upon a common secret, a key, to use further on for ciphering and deciphering secret messages, if the protocol parameters are well-chosen.

An article called “Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice” published in October 2015 by A. David & al. does raise a flag on the fact that improper parametrization could lead to security breaches if your attacker as enough resources (for example, if they are part of a governmental secret service)… They even end the article with a list of suggestions and recommendations on how to improve your DH setup!

Asymmetric cipher: private eyes only!

Contrary to symmetric ciphers, asymmetric ciphers use a pair of keys for encrypting and decrypting messages. The encoding key is called the “public” key because it can be shared with anyone: you allow anyone who is interested to send you encrypted messages. On the other hand, the decryption key is said to be “private” because only you have it: you (and your trusted friends who have it too) are the only one who can decipher the encoded content.

The main thing with asymmetric (or public-key) cryptography is that the plain text is transformed via a one-way function, or in other words a mathematical process that is (theoretically) impossible to reverse.

Although it is usually not a concern for this type of algorithms, if you want to limit the number of people that can encrypt messages (for example to avoid the impersonation issue mentioned last time), you can ask for robust authentication. To do that, you need people who are allowed to encode data to use their own private key as a unique digital signature, and to combine it with the message itself to insure authenticity.

These algorithms are fairly recent with regard to the symmetric ones: they have actually been in use only since the mid-1970s. Some focus on securing the exchange of keys, like the Diffie-Hellmann process described up above. Others are specifically designed for digital signatures. The current state-of-the-art algorithm, the RSA algorithm, does both.

Note: because the encryption is public, these schemes can be subject to “man-in-the-middle” attacks where a third-party alters the keys to prevent proper communication between the initial sender and receiver. I will do a more in-depth description of the various cryptographic attacks in an upcoming article 😉

ElGamal’s algorithm

The ElGamal’s encryption technique was described by Taher Elgamal in 1985. It involves fairly complex mathematical objects that I won’t detail here. Still, it is interesting to mention because it reveals one of the big downside of asymmetric ciphers: they are way slower than symmetric ones. This is why a common process is not to encrypt the data per se with the algorithm, but instead to encrypt a symmetric key so it can be passed on an open channel without any risk.

Once again, consider Alice and Bob.

Alice wants to send Bob her latest cooking recipes. The problem is that there is a lot of them! Applying the ElGamal’s scheme would be too long. Alice will rather use some robust symmetric cipher and use ElGamal’s encryption process on the symmetric key. Then, she can pass it on to Bob through any discussion channel… even a completely open one full of foes! In parallel, the important thing is to secretly convey the ElGamal’s decryption parameters to Bob, too. This is usually done with the Diffie-Hellmann key exchange process. Bob will then be able to decrypt the symmetric key since he has the ElGamal’s decryption parameters. Finally, he will be able to use the symmetric decryption counterpart to restore the original content.

Another fun fact is that ElGamal’s encryption is probabilistic: this inherent randomness means that the same plain text input can result in different cipher texts.

RSA: the state-of-the-art security algorithm

In 1977, 3 MIT scientists called Rivest, Shamir and Adleman proposed a new encryption-decryption algorithm to the public named after their initials: the RSA algorithm.

The RSA technique security is solely dependent on the mathematical complexity of a seemingly simple problem: integer factorization into prime numbers (i.e. numbers that can only be divided by 1 or themselves: 1, 2, 3, 5, 7, 11…). This is one of these mathematical questions that is very easy to understand, pretty simple to answer on small numbers and impossible to solve on large ones even with today’s technology.

Say you have a number like 12. You can write it down as: 12 = 3 x 4 = 3 x 22. This final form is the factorization of 12 into prime numbers (here: 3 and 2, this last one being repeated twice). The funny thing is that while it’s straight-forward to compute for small numbers, there is currently no algorithm to do it in a reasonable time on large numbers.

Note: for the ones into maths, this problem is NP-hard, meaning that we haven’t found any algorithm running in polynomial time to solve it yet (on a normal and real-life computer, at least!).

Now, when we talk about large numbers here, we’re referring too really big numbers. As explained on the quite nice police drama series “Numb3rs”, we mean numbers with a lot of zeros… (sorry for the not-so-good quality):

So, for RSA to work, you just need to take large enough prime numbers (they are your private key) and multiply them together to build the public key. Since no one is able to decompose this insanely huge number back to the initial two prime numbers, they cannot find your private key and they cannot decrypt the messages. According to the available factorization algorithms estimated running times, decrypting a message encrypted with a (weak) public key containing only 300 digits would take almost 22,000 years… and the standards for RSA keys recommend to take keys of 600 digits!

Nowadays, the RSA algorithm is the most used technique for any sensitive transaction: for example banks use it for credit card payment, online contract signature, etc. However, new technologies like quantum computing may drastically alter the landscape of cryptography and even render this type of algorithms unsecure if it ever becomes tractable in practice (by brute-forcing it, as proven by Peter Shor in 1994)…

Note: it happened many times that, due to top-secret classification, inventions in the field of cryptography were only revealed years after being used by secret services or armies, or that some discoveries had actually already been done before their public equivalent. For example, Clifford Cocks was a British mathematician who had designed a system quite similar to the RSA algorithm in the early 1970s, a few years before Rivest, Shamir and Adleman published their technique; but this method was kept secret until 1997.

Bonus: Quantum cryptography

At the heart of quantum physics are photons: small “grains” of light that travel through space and time. Quantum cryptography is a subfield of cryptography that intends to use quantum mechanics to encrypt data in a way that is safe enough to resist attacks from quantum computers. Compared to our current classical computers, quantum computers would be able to run a lot (lot!) more of operations in a second and could therefore break ciphers like RSA by solving the problem of integer factorization into prime numbers.

In quantum cryptography, the point is basically to encode the data in your message as photons and to send those photons in a well-prepared physical channel. So instead of using electrical signals through wires to send encrypted messages, you would rather use light through optical fibres.

Quantum mechanics could be used for an efficient and theoretically “perfect” (with regard to information theory) key distribution process. The best-known algorithm at the moment is the quantum key distribution (QKD) and, similarly to the Diffie-Hellman key exchange protocol, it would only be used to send the key in a safe way. Then, the rest of the communication is encrypted with classical cryptography techniques, even symmetric ciphers. Thanks to the specific properties of quantum objects, it can be mathematically proven that it is a safe protocol: you cannot tamper with the QKD process without being noticed and it does what it’s supposed to without the need to restrict the eaves-dropper in anyway. Thus this algorithm is said to have “unconditional security”.

Note: to be honest, it seems to be the most promising application of quantum systems to cryptography from what I’ve read for now…

There’s another principle in quantum physics that is relevant to cryptography: the observer principle. To put it simply, it’s the idea that merely observing a phenomenon has an impact on it, that even the passive observation of a situation changes it. Measuring something alters the measurement itself. This would be very interesting for cryptography because it would prevent any eaves-dropper from ever listening on a communication and staying unnoticed. As soon as a third party would try and spy on your secret channel, they would necessarily modify any messages send on it and you could catch on them quite quickly.

The big problem with quantum cryptography is, however, that it’s not yet feasible in practice. In particular, there are severe limitations on the distance the message can travel. Despite the latest achievements in communications such as the design of very optimized optical fibres, you still cannot send a message using photons as far as you want. In the early 2010s, the record distance was only of 90 kilometres. In 2019, Minder and al. managed to do a real-life quantum key distribution experiment and to send a message 550 kilometres away by following a protocol previously proposed by Lucamarini and al. in their 2018-article “Overcoming the rate–distance limit of quantum key distribution without quantum repeaters”. This is a nice improvement, but this is the maximum distance that has been reached to this day.

Note: there is also another field of study called “post-quantum cryptography” that focuses specifically on finding and optimizing cryptography algorithms that can resist to attacks from quantum computers.

Even though it sounds a bit like science-fiction, quantum computing is becoming more and more of a reality. QKD has been actually used during various experiments since 2004. Big players like Microsoft are of course in the race to stabilize computers with enough quantum bits (qbits) to run algorithms such as Shor’s, break RSA and profoundly change cryptography.

Until next time…

I hope you enjoyed this small introduction on symmetric and asymmetric ciphers! It was but a quick description of the most used techniques and some concepts and, if you’re interested, I invite you to go ahead and search for more details… there’s still a lot to say about these methods, their history, their dangers and their promises 😉

Beside an article on the various cryptographic attacks, the following articles in the “Data & Security” series won’t be as technical and will probably focus more on the relationship between the security technologies and our society, or on our relation to data and information sharing.

La dernière fois, j’ai parlé de cryptographie symétrique et de son utilisation à travers le temps pour l’échange de messages secrets. Malgré tous leurs avantages, on peut identifier quelques problèmes avec les chiffres symétriques : ils nécessitent d’échanger la clé de manière sécurisée et certains peuvent maintenant être facilement cassés à l’aide des dernières découvertes informatiques. Aujourd’hui je vais me concentrer sur l’autre facette : la cryptographie asymétrique. Je vais parler de certains avantages et certains inconvénients par rapport à la cryptographie symétrique et je vais aussi donner un aperçu très basique d’un possible grand changement dans le domaine : la cryptographie quantique.

Echange de clés : protocole de Diffie-Hellman aka “difficile de séparer les couleurs !”

La technique d’échange de clés de Diffie-Hellman ne s’utilise pas pour chiffrer et envoyer des messages directement mais plutôt, comme son nom l’indique, les clés elles-mêmes. Elle est donc utilisée en amont de n’importe quelle véritable “conversation” pour s’assurer que l’émetteur et le récepteur ont les bonnes clés tout en évitant d’envoyer les clés de chiffrage et déchiffrage en texte clair (puisque c’est un moment dangereux pendant lequel une personne tierce peut voler la clé pour facilement espionner les transmissions par la suite).

Cette méthode repose sur l’idée que, grâce à la magie des mathématiques (et plus précisément de la théorie des groupes ;)), il est possible de :

  • prendre deux chemins différents pour arriver au même endroit
  • faire en sorte que cet endroit soit très difficile à trouver si on ne connaît aucun des deux chemins

De manière un peu plus concrète : supposons que nous ayons affaire à deux personnes qui veulent échanger des secrets : Alice et Bob.

Note : “Alice” et “Bob” sont les noms usuels de l’émetteur et du récepteur en cryptographie, ainsi qu’ils ont été initialement introduits dans le papier “A Method for Obtaining Digital Signatures and Public-key Cryptosystems” de Rivest, Shamir et Adleman publié en 1978. Ils sont accompagnés de tout un ensemble de personnages où la personne tierce malveillante est souvent appelée “Chuck” et l’intrus malicieux est surnommé “Eve” (pour “eavesdropper”, en anglais).

Ils souhaitent s’envoyer des messages secrets (en utilisant l’un des chiffres symétriques détaillés dans mon dernier article, par exemple) mais, d’abord, ils doivent décider d’une clé. Ils n’ont aucun moyen de se rencontrer en vrai et doivent donc envoyer leur clé sur un réseau… ce qui signifie qu’ils doivent faire très attention pour qu’elle ne soit pas volée !

Alors, comment le processus d’échange de clés de DH fonctionne-t-il ?

  1. pour commencer, ils décident d’une “base” commune pour leur clé : cette valeur peut simplement être écrite en clair sur leur réseau sans se préoccuper davantage de la sécurité – tout le but de l’échange va être de transformer cette clé initiale en un équivalent impossible à deviner.
  2. ensuite, ils choisissent un “secret” : chacun a le sien et il ne sera pas envoyé à l’autre. En pratique, ces deux étapes sont des échanges de nombres ; Alice et Bob peuvent donc les combiner pour obtenir des données “mélangées”. Ces données vont être le matériau de base de la clé finale et peuvent être envoyées sans problème sur le réseau également.
  3. ces données “mélangées” sont envoyées pour être échangées avec l’autre participant : Alice récupère les données de Bob, et Bob celles d’Alice
  4. maintenant, chaque participant recombine les données “mélangées” de l’autre avec son propre “secret”
  5. et voilà ! Alice et Bob ont maintenant créé un “secret commun”, la clé qu’ils utiliseront pour chiffrer le reste de leurs messages – cette clé demeure secrète car ils l’ont tous les deux recréée de leur côté et qu’elle n’a jamais été partagée

L’important est d’utiliser le bon type de “combinaison” pendant les étapes (2) et (4). A l’aide de la théorie des groupes, on peut trouver des façons d’assembler des nombres qui vérifient les deux points mentionnés plus tôt : on s’assure qu’Alice et Bob arrive à la même clé au final (sinon le processus serait assez inutile !) et on s’assure également qu’il est difficile (autrement dit impossible en pratique) de décomposer les données “mélangées” partagées au cours de l’échange pour retrouver les “secrets” initiaux.

Le processus d’échange de clés de Diffie-Hellman peut être représenté par ce schéma :

Représentation du processus d’échange de clés de Diffie-Hellman (original par A.J. Han Vinck, Université de Duisburg-Essen ; reproduit par Flugaal, ici: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange)

Note : pour ceux intéressés par les maths : comme expliqué dans le wiki, la “combinaison” du processus d’échange de clés de DH est généralement une exponentiation sur des groupes multiplicatifs d’entiers modulo p. Toute la logique repose sur le fait que, modulo, p, on obtient :

Ici : a est le secret d’Alice, b est le secret de Bob, A sont les données “mélangées” envoyées par Alice, B sont les données “mélangées” envoyées par Box et gab = gba est le secret commun.

Quand on prend des nombres suffisamment grands, il est presque impossible de craquer les clés chiffrées. Les ordinateurs actuels sont capables de combiner les secrets et les données “mélangées” partagées très rapidement (en utilisant l’exponentiation modulaire), en revanche l’opération inverse est actuellement impossible pour des nombres contenant au moins 600 chiffres (c’est le problème du logarithme discret).  Cela signifie que cette technique est un moyen sûr de nos jours de créer un secret commun, une clé, à utiliser par la suite pour le chiffrage et le déchiffrage de messages secrets, si les paramètres du protocole sont bien choisis.

Un article intitulé “Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice” publié en octobre 2015 par A. David & al. donne l’alerte sur le fait qu’un mauvais choix de paramètres peut mener à des failles de sécurité si l’attaquant a suffisamment de ressources (par exemple, s’il fait partie de services secrets gouvernementaux)… Ils terminent même leur article par une liste de suggestions et de recommendations pour améliorer son sytème DH !

Cryptographie asymétrique : c’est privé !

Contrairement aux chiffres symétriques, les chiffres asymétriques utilisent une paire de clés pour le chiffrage et le déchiffrage de messages. La clé d’encryption est dite “publique” car elle peut être partagée avec tout le monde : on autorise n’importe quelle personne intéressée à nous envoyer des messages codés. A l’inverse, la clé de déchiffrage est “privée” car on est le seul à l’avoir : nous (et éventuellement nos amis de confiance qui l’ont également) sommes les seuls à pouvoir déchiffrer les textes cryptés.

La base de la cryptographie asymétrique (ou à clé publique) est de transformer le texte en clair à l’aide d’une fonction “à sens unique”, en d’autres termes un processus mathématique qu’il est (théoriquement) impossible d’inverser.

Même si ce n’est généralement pas un problème pour ce type d’algorithmes, si on souhaite limiter le nombre de personnes qui peuvent chiffrer des messages (par exemple pour éviter le problème de falsification d’identité mentionné la dernière fois), on peut demander une authentification robuste. Pour cela, on force les personnes qui peuvent encoder des données à utiliser leur propre clé privée comme signature numérique et à la combiner avec le message lui-même pour assurer son authenticité.

Ces algorithmes sont assez récents comparés aux chiffres symétriques : ils ne sont réellement utilisés que depuis le milieu des années 1970. Certains se concentrent sur l’échange de clés, comme le processus de Diffie-Hellman décrit plus haut. D’autres sont spécifiquement conçus pour la signature informatique. L’actuel état de l’art, l’algorithme RSA, fait les deux.

Note : étant donné que le chiffrage est publique, ces algorithmes peuvent être sujets à une attaque “par le milieu” dans laquelle une partie tierce altère les clés pour empêcher la communication entre l’émetteur et le récepteur initiaux. Je ferai une description plus en profondeur des différentes attaques en cryptographie dans un prochain article 😉

L’algorithme d’ElGamal

La technique de chiffrage d’ElGamal a été décrite par Taher Elgamal en 1985. Elle utilise des objets mathématiques relativement complexes dont je ne parlerai pas ici. Néanmoins, il est intéressant d’y jeter un oeil car elle révèle l’un des désavantages de la cryptographie asymétrique : elle est beaucoup plus lente que la cryptographie symétrique. C’est pourquoi il est courant de ne pas chiffrer les données elles-mêmes avec l’algorithme mais plutôt de coder une clé qui peut ainsi être transmise sur un canal ouvert sans aucun risque.

Encore une fois, parlons d’Alice et Bob.

Alice veut envoyer ses dernières recettes de cuisine à Bob. Le problème, c’est qu’il y en a beaucoup ! Appliquer la technique d’ElGamal serait trop long. Alice va plutôt se servir d’un chiffre symétrique robuste et chiffrer la clé symétrique à l’aide du processus d’ElGamal. Ensuite, elle peut passer cette clé à Bob sur n’importe quel canal… même un totalement ouvert ! En parallèle, il est important d’également échanger une clé en secret avec Bob pour lui transmettre les paramètres de déchiffrage d’ElGamal. On fait souvent cela à l’aide du protocole d’échange de clés de Diffie-Hellman. Bob sera ensuite capable de déchiffrer la clé symétrique avec les paramètres de décodage d’ElGamal. Enfin, il pourra se servir de la clé symétrique pour déchiffrer le message secret et récupérer le contenu initial.

Autre fait amusant à propos du chiffrement d’ElGamal : il est probabiliste. A cause de cet aléatoire inhérent à l’algorithme, le même texte en clair pourra être chiffré en de multiple textes codés différents.

RSA : l’état de l’art des algorithmes sécurisés

En 1977, 3 scientifiques du MIT appelés Rivest, Shamir and Adleman ont proposé un nouvel algorithme de chiffrage-déchiffrage au public nommé par leurs trois initiales : l’algorithme RSA.

La technique RSA dépend entièrement de la complexité d’un problème mathématique qui paraît simple : la factorisation d’entiers en nombre premiers (i.e. des nombres qui ne sont divisibles que par 1 et eux-mêmes : 1, 2, 3, 5, 7, 11…). C’est une de ces questions mathématiques très simple à comprendre, assez simple à calculer pour de petits nombres et impossible à résoudre pour de grands nombres, même avec la technologie d’aujourd’hui.

Imaginons que l’on a un nombre comme 12. On peut l’écrire : 12 = 3 x 4 = 3 x 22. Cette forme finale est la factorisation de 12 en nombres premiers (ici : 3 et 2, le dernier étant répété deux fois). Ce qui est intéressant, c’est que même si on peut calculer le résultat sans trop de problème pour un petit nombre, il n’y a pour l’instant aucun algorithme capable de trouver la solution en temps raisonnable pour des grands nombres.

Note : pour ceux intéressés par les maths, ce problème est NP-difficile, c’est-à-dire que nous n’avons pas encore trouvé d’algorithme en temps polynomial pour le résoudre (sur un ordinateur classique, en tout cas !).

Quand on parle de grands nombres, ici, on fait référence à des nombres vraiment grands. Comme expliqué dans la bonne série policière “Numb3rs”, on parle de nombres avec beaucoup de zéros… (vidéo en anglais – désolée pour la qualité moyenne) :

Donc pour que RSA fonctionne, il suffit de prendre des nombres premiers suffisamment grands (ils constituent la clé privée) et de les multiplier ensemble pour créer la clé publique. Comme personne n’est capable de décomposer ce nouveau nombre incroyablement grand pour retrouver les deux nombres premiers de départ, on ne peut pas obtenir la clé privée et on ne peut pas décoder les messages. Si on se réfère aux temps estimés de calcul des algorithmes de factorisation actuellement disponibles, déchiffrer un message codé avec une clé publique (faible) qui ne contient que 300 chiffres prendrait presque 22 000 ans… et les standards pour les clés RSA recommandent de choisir des clés de 600 chiffres !

A l’heure actuelle, l’algorithme RSA est la technique la plus utilisée pour toute transaction sensible : par exemple, les banques s’en servent pour les paiements de carte bancaire, la signature de contrat en ligne, etc. Pourtant, de nouvelles technologies comme l’informatique quantique pourrait modifier drastiquement le champ de la cryptographie et même rendre cet algorithme obsolète si elles devenaient jamais une réalité (en utilisant la force brute, comme montré par Peter Shor en 1994)…

Note : il est arrivé de nombreuses fois qu’à cause du secret défense, des inventions de cryptographie ne soient révélées que des années après avoir été utilisées par les services secrets ou les armées, ou que certaines découvertes aient en réalité déjà été faites bien avant qu’un équivalent soit dévoilé au public. Par exemple, Clifford Cocks était un mathématicien anglais qui a conçu un système ressemblant fortement à l’algorithme RSA au début des années 1970, quelques années avant que Rivest, Shamir et Adleman ne publient leur technique ; mais cette méthode est restée secrète jusqu’en 1997.

Bonus : Cryptographie quantique

Les photons sont au coeur de la physique quantique : ce sont de petits “grains” de lumière qui voyagent à travers l’espace et le temps. La cryptographie quantique est un sous-domaine de la cryptographie qui entend utiliser la mécanique quantique pour chiffrer les données de manière suffisamment sûre pour résister à des attaques d’ordinateurs quantiques. Par rapport aux ordinateurs classique que nous avons actuellement, ces ordinateurs quantiques seraient capables d’effectuer un nombre beaucoup (beaucoup !) plus important d’opérations à la seconde et pourraient donc casser des chiffres comme RSA en résolvant le problème de factorisation des entiers en nombre premiers.

Avec la cryptographie quantique, le but est globalement d’encoder les données du message sous la forme de photons et d’envoyer ces photons à travers un canal physique habilement préparé. Donc plutôt que d’envoyer des signaux électriques à travers des câbles pour transmettre les messages chiffrés, on utiliserait plutôt de la lumière à travers des fibres optiques.

La mécanique quantique pourrait être utilisée pour créer un processus de distribution de clés efficace et théoriquement “parfait” (du point de vue de la théorie de l’information). L’algorithme le plus connu aujourd’hui est la distribution de clé quantique, en anglais quantum key distribution (QKD). De la même façon que pour le protocole d’échange de clés de Diffie-Hellman, il ne servirait qu’à envoyer les clés de manière sécurisée. Ensuite, le reste de la communication serait chiffré avec des techniques cryptographiques classiques, et même des chiffres symétriques. Grâce aux propriétés uniques des objets quantiques, il a été prouvé mathématiquement que ce protocole est sûr : on ne peut pas trafiquer le processus QKD sans être repéré et il fonctionne sans problème sans qu’on ait besoin d’imposer des restrictions à l’intrus malveillant. On dit donc que cet algorithme a une “sécurité inconditionnelle”.

Note : pour être honnête, cela semble être l’application la plus prometteuse des systèmes quantiques dans le domaine de la cryptographie d’après ce que j’ai lu pour l’instant…

Un autre principe de la physique quantique intéressant pour la cryptographie est l’effet d’observateur. Il s’agit grossièrement de l’idée que la simple observation d’un phénomène a un impact, que même une observation passive de la situation la modifie. Mesurer quelque chose altère la mesure elle-même. Ce serait très utile en cryptographie car cela permettrait d’empêcher un intrus d’écouter une conversation en restant inaperçu. Dès qu’une personne tierce essaierait d’espionner votre canal secret, elle modifierait nécessairement les messages qui y passent et vous pourriez identifier sa présence assez rapidement.

Mais le gros problème de la cryptographie quantique est que, pour l’instant, ce n’est pas encore réalisable en pratique. En particulier, il y a de sévères limitations sur la distance que peut parcourir un message. Malgré les dernières avancées dans le domaine des télécommunications avec la conception de fibres optiques plus optimisées, on ne peut toujours pas envoyer de messages à l’aide de photons aussi loin que l’on veut. Au début des années 2010, la distance record n’était que de 90 kilomètres. En 2019, Minder et al. ont réussi à réaliser une expérience de distribution de clé quantique et à envoyer un message sur 550 kilomètres en suivant un protocole proposé précédemment par Lucamarini et al. dans leur article de 2018 “Overcoming the rate–distance limit of quantum key distribution without quantum repeaters”. C’est un beau progrès, mais cela reste la distance la plus importante jamais parcourue par un message chiffré par le quantique à ce jour.

Note : il existe aussi un champ d’étude appelé la “cryptographie post-quantique” qui s’intéresse spécifiquement à la recherche et l’amélioration d’algorithmes cryptographiques capables de résister aux attaques d’ordinateurs quantiques.

Bien que ça puisse ressembler à de la science-fiction, l’informatique quantique commence à devenir une réalité. QKD a été réellement utilisé au cours de diverses expériences depuis 2004. De gros joueurs comme Microsoft sont bien évidemment dans la course pour stabiliser des ordinateurs avec assez de bits quantiques (qbits) pour appliquer des algorithmes comme celui de Shor, casser RSA et changer en profondeur la cryptographie.

D’ici la prochaine fois…

J’espère que cette petite introduction sur les chiffres symétriques et asymétriques vous a plu ! Ce n’était qu’une description rapide des techniques les plus utilisées et de certains concepts et, si vous êtes intéressés, je vous invite à aller fouiller plus en détail… il y a bien d’autres choses à raconter sur toutes ces méthodes, leur historique, leurs dangers et leurs promesses 😉

En-dehors d’un article sur les diverses attaques cryptographiques, la suite de la série “Données & Sécurité” sera probablement moins technique et plus axé sur les relations entre ces technologies de sécurité et notre société, ou bien sur notre rapport aux données et au partage d’information.

REFERENCES / SOURCES
  1. Simon Singh’s website: https://simonsingh.net/
  2. QuantumXC, “Quantum cryptography explained”: https://quantumxc.com/quantum-cryptography-explained/
  3. Microsoft’s quantum cryptography intro page: https://cloudblogs.microsoft.com/quantum/2020/02/26/cryptography-quantum-computers/
  4. “Prime numbers on Numb3rs”: https://www.youtube.com/watch?v=GKTexzwFpck
  5. S. Singh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography (https://www.amazon.fr/Code-Book-Science-Secrecy-Cryptography/dp/0385495323), 1999. [Online; last access 18-May-2020].
  6. R.L. Rivest, A. Shamir, L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” (https://people.csail.mit.edu/rivest/Rsapaper.pdf), 1978. [Online; last access 24-May-2020].
  7. P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring” (https://ieeexplore.ieee.org/document/365700), Aug. 2002. [Online; last access 24-May-2020].
  8. D. Adrian and al., “Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice” (https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf), Oct. 2015. [Online; last access 24-May-2020].
  9. Lucamarini and al., “Overcoming the rate–distance limit of quantum key distribution without quantum repeaters” (https://www.nature.com/articles/s41586-018-0066-6), 2018. [Online; last access 24-May-2020].
  10. T. Olzak, “Chapter 7: The Role of Cryptography in Information Security” (https://resources.infosecinstitute.com/role-of-cryptography/), June 2012. [Online; last access 18-May-2020].
  11. Educba, “RSA Algorithm” (https://www.educba.com/rsa-algorithm/). [Online; last access 24-May-2020].
  12.  Z. Merali, “Quantum cryptography conquers noise problem” (https://www.nature.com/news/quantum-cryptography-conquers-noise-problem-1.11849), Nov. 2012. [Online; last access 24-May-2020].
  13. D. Powell, “What Is Quantum Cryptography?” (https://www.popsci.com/what-is-quantum-cryptography/), Mar. 2016. [Online; last access 24-May-2020].
  14.  Microsoft Quantum, “Cryptography in the era of quantum computers” (https://cloudblogs.microsoft.com/quantum/2020/02/26/cryptography-quantum-computers/), Feb. 2020. [Online; last access 24-May-2020].
  15. I. Wikimedia Foundation, “Diffie-Hellman key exchange” (https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange), May 2020. [Online; last access 24-May-2020].
  16. I. Wikimedia Foundation, “Group theory” (https://en.wikipedia.org/wiki/Group_theory), May 2020. [Online; last access 24-May-2020].
  17. I. Wikimedia Foundation, “Alice and Bob” (https://en.wikipedia.org/wiki/Alice_and_Bob), May 2020. [Online; last access 24-May-2020].
  18. I. Wikimedia Foundation, “Modular exponentiation” (https://en.wikipedia.org/wiki/Modular_exponentiation), May 2020. [Online; last access 24-May-2020].
  19. I. Wikimedia Foundation, “Discrete logarithm” (https://en.wikipedia.org/wiki/Discrete_logarithm), Apr. 2020. [Online; last access 24-May-2020].
  20. I. Wikimedia Foundation, “ElGamal encryption” (https://en.wikipedia.org/wiki/ElGamal_encryption), Apr. 2020. [Online; last access 24-May-2020].
  21. I. Wikimedia Foundation, “Information theory” (https://en.wikipedia.org/wiki/Information_theory), May 2020. [Online; last access 24-May-2020].
  22. I. Wikimedia Foundation, “Observer effect (physics)” (https://en.wikipedia.org/wiki/Observer_effect_(physics)), May 2020. [Online; last access 24-May-2020].
  23. I. Wikimedia Foundation, “Post-quantum cryptography” (https://en.wikipedia.org/wiki/Post-quantum_cryptography), May 2020. [Online; last access 24-May-2020].

Leave a Reply

Your email address will not be published. Required fields are marked *