Les plus belles inventions en informatique

Je tente de lister ici ce qui - à mon humble avis - représente les plus belles inventions ou réalisations en informatique. Avec leurs applications. J'ai essayé dans cette page d'être accessible: Les spécialistes me pardonneront donc les approximations effectuées au nom de la compréhension.

On ne dit pas "Crypter un fichier avec un mot de passe" car c'est incorrect: On dit chiffrer un fichier avec une clé.

Instinctivement, on se doute bien qu'on prend la même clé pour chiffrer et déchiffrer le fichier.

Mais il existe des algorithmes pour lesquels la clé de déchiffrement est différente de la clé de chiffrement, et on ne peut pas déduire une clé de l'autre. Cela paraît presque magique, mais c'est possible. Typiquement, l'algorithme RSA (basé sur les nombres premiers) permet cela.

Imaginez: Je peux distribuer ma clé de chiffrement à tout le monde. Elle est publique. Tout le monde est ainsi capable de chiffrer les messages qui me sont destinés. Mais moi seul peut les déchiffrer avec ma clé de déchiffrement (qui est privée). (Pour un exemple concret, voir cette page).

L'algorithme RSA (ainsi que bien d'autres tel que Diffie-Hellman) sont à la base de toute la sécurité informatique moderne. Typiquement, votre navigateur l'utilise quand vous avez une adresse en https://...

À quoi ça sert ?

Sans les algorithmes de chiffrement asymétriques, nous ne pourrions pas échanger de manière sûr des données avec des personnes que nous n'avons jamais rencontrées. Il nous faudrait trouver préalablement un canal d'échange sûr pour échanger les clés de chiffrement, ou même devoir rencontrer en personne vos interlocuteurs avant tout échange, ce qui rendrait les choses bien plus compliquées.

Le hashage est une fonction qui prend des données de n'importe quelle taille en entrée, et qui donne en sortie une courte suite de chiffres appelée empreinte (ou hash), de taille fixe. Elle a une particularité intéressante:

Les mêmes données en entrée donneront toujours le même hash en sortie. Un hash est donc comme une empreinte digitale des données.

Il existe différentes fonctions de hashage (md5, sha1, sha256…). Faisons un essai avec md5. Vous pouvez par exemple tester sur ce site: http://www.md5.cz/

Comme vous pouvez le voir:

• Quelle que soit la longueur des données en entrée, la fonction de hashage a une taille fixe en sortie. (La taille dépend de la fonction de hashage.)
• Chaque hash est unique, et spécifique à ce qui a été mis en entrée.
• La moindre modification en entrée (même une seule lettre ou un accent) changement complètement la sortie.

Et plus particulièrement, les fonctions de hashage ont les propriétés suivantes:

• La valeur du hash n'est pas prédictible.
• Il n'est pas possible de déduire ce qu'il y avait en entrée à partir du hash seul (sauf si on essaie toutes les combinaisons possibles de données en entrée).
• Il n'est pas possible de construire des données en entrée ayant un hash voulu (enfin, pas facilement).

(Ces deux dernière affirmations sont généralement vraies, si on excepte les quelques faiblesses découvertes dans certaines fonctions de hashage).

Il existe différentes fonctions de hashage, ayant une sortie plus ou moins longue. md5 et sha1 sont très courantes, mais tout le monde passe de plus en plus à d'autres fonctions comme sha256. Exemples:

À quoi ça sert ?

Ça sert, par exemple

• à s'assurer que les données n'ont pas été modifiées ou corrompues lors du transfert d'un ordinateur à l'autre. Voici comment on procède:
  • On transmet les données + le hash.
  • À la réception, on recalcule le hash sur les données, et on vérifie que les deux hashs correspondent.

• à s'assurer que les données ne sont pas endommagées lors de stockage ou transformations:
  • par exemple les archives zip/rar/7z stockent des hashs des fichiers, et les vérifient lors de la décompression.
  • les disques durs écrivent des sommes de contrôle (ou hash) en plus des données, ce qui permet de détecter les secteurs défectueux lors de la lecture, et d'en informer le système d'exploitation.
• à "signer des documents": Pour signer un document électronique, les deux parties signent juste le hash du document. Comme le hash est unique aux données, c'est équivalent à signer le document lui-même. (Et comme on ne peut pas créer de toutes pièces un document ayant un hash voulu, on ne peut pas le falsifier.)
• C'est utilisé dans BitTorrent pour identifier de manière unique chaque téléchargement, ainsi que contrôler l'intégrité des fichiers téléchargés.
  • Par exemple, le hash du torrent de Linux Mint 19.3 Mate est 90f700358946c85c6dd5244c34c5304810bd9d28. Vous retrouvez ce hash dans les liens Magnet: magnet:?xt=urn:btih:90f700358946c85c6dd5244c34c5304810bd9d28&dn=linuxmint-19.3-mate-64bit.iso
• Il existe même une forme particulière de hash dans laquelle on met en entrée les données et une clé. On obtient en sortie un hash, mais on ne peut calculer le bon hash que si on a les bonnes données et la bonne clé. Exemple: HMAC-SHA1 (à compléter).

• ssh
• rsync
• les codes correcteurs d'erreur (Reed-Solomon, par2…)
• Le P2P, notamment BitTorrent (et ce qui va avec: DHT, PEX…)
• l'émulation et les machines virtuelles (y compris celles des langages: java, javascript, python, .Net.. qui émulent des processeurs fictifs)
• Le Copy-On-Write (cas pratique: btrfs)
• La compression (les rapides génériques (lzo, lz4), les performants génériques (lzma), les spécialisés non destructifs (flac), les spécialisés destructifs (vorbis, av1, opus…))
• La déduplication (cas pratiques: 7z, borg, btrfs..)
• Les bases de données relationnelles (avantages: gestion de gros volume de données (indexation), modifications en masse (opération ensemblistes et groupage), intégrité des données (contraintes, transactions, ACID…). Souvent regardé de haut pas les développeurs qui les considèrent comme de la basse besogne pas intéressante.
• Le wiki
• les flux, les pipes (à la base de la phylosophie Linux: un programme qui ne fait qu'une seule chose mais qui la fait bien, et le pipe pour les lier).
• OTP (TOTP, HOTP)

Voici ce que je considère comme étant les plus belles inventions en informatique. Notez que je ne prétends absolument pas être exhaustif.

• La cryptographie à clés publiques (Diffie-Hellman, RSA)
• Les hashs (crc32, md5, sha1, sha256…)
• HMAC et ses applications (TOTP/HOTP)
• rsync, les rolling-hash
• ssh
• Reed-Solomon et les codes correcteurs d'erreur (application pratique: par2)
• SQLite
• DHT
• la compression lossless (lz77, zstd, lzma…)
• la compression lossy (fourrier (JPEG,mp3), wavelet (ogg/vorbis), opus, AV1…)
• les systèmes de fichiers Copy-On-Write (btrfs, xfs…)