Cette semaine, nous étudierons l'algorithme d'Euclide et ses applications. Cet algorithme fondamental est le principal tremplin pour comprendre une grande partie de la cryptographie moderne ! Non seulement cet algorithme permet de trouver le plus grand diviseur commun de deux nombres (ce qui est un problème incroyablement important en soi), mais sa version étendue offre également un moyen efficace de résoudre les équations diophantiennes et de calculer les inverses modulaires.

La cryptographie étudie les moyens de partager des secrets en toute sécurité, de sorte que même les oreilles indiscrètes ne puissent extraire aucune information de ce qu'elles entendent ou du trafic réseau qu'elles interceptent. L'un des algorithmes cryptographiques les plus populaires, appelé RSA, est basé sur la factorisation unique des nombres entiers, le théorème chinois des restes et l'exponentiation modulaire rapide. Dans ce module, nous allons étudier ces propriétés et ces algorithmes qui sont les éléments constitutifs de RSA. Dans le module suivant, nous utiliserons ces éléments pour mettre en œuvre l'algorithme RSA, ainsi que pour lancer des attaques intelligentes contre l'algorithme RSA et décrypter certains codes secrets.

La cryptographie moderne s'est surtout développée pendant la Première et la Seconde Guerre mondiale, parce que tout le monde espionnait tout le monde. Vous entendrez cette histoire et vous comprendrez pourquoi les cyphers simples ne fonctionnaient plus. Vous apprendrez que la clé secrète partagée doit être modifiée à chaque communication si l'on veut qu'elle soit sécurisée. Cela pose un problème lorsque la demande de communication sécurisée monte en flèche et que les parties qui communiquent peuvent se trouver sur des continents différents. Vous étudierez ensuite le système cryptographique RSA, qui permet aux parties d'échanger des clés secrètes de telle sorte qu'aucun espion ne puisse déchiffrer ces clés secrètes dans un délai raisonnable. Ensuite, vous étudierez et mettrez en œuvre quelques attaques contre un système RSA mal implémenté, ce qui vous permettra de déchiffrer quelques codes secrets et même de réussir une petite épreuve cryptographique !