GnuPG fait usage de nombreux concepts de cryptographie dont les algorithmes de chiffrement symétriques, algorithmes de chiffrement à clé publique, et hachage à sens unique. Il n'est pas nécessaire de comprendre complètement ces concepts pour utiliser les fonctionnalités de GnuPG.
Ce chapitre est une introduction aux concepts cryptographiques de base utilisés par GnuPG. D'autres livres couvrent ces sujets plus en détails. Un bon livre pour approfondir cette étude est ``Cryptographie Appliquée'' de Bruce Schneier.
Un algorithme de chiffrement symétrique utilise la même clé pour le chiffrement et le déchiffrement. Les deux partis qui veulent communiquer en utilisant un algorithme de chiffrement symétrique doivent au préalable se mettre d'accord sur la clé. Une fois qu'elles le sont, l'émetteur chiffre le message en utilisant la clé, l'envoie au destinataire, et ce dernier le déchiffre en utilisant la même clé. Par exemple, la machine allemande Enigma utilisait un algorithme de chiffrement symétrique, et les clés quotidiennes étaient distribuées dans des livres de code. Chaque jour, les opérateurs radio qui émettaient ou recevaient devaient consulter leur copie du livre de codes, pour trouver la clé du jour. Le trafic radio pour la journée était chiffré et déchiffré en utilisant la clé du jour. Des exemples modernes d'algorithmes de chiffrement symétrique sont 3DES, Blowfish, ou IDEA.
Un bon procédé de chiffrement fait reposer la sécurité seulement sur la clef, nullement sur l'algorithme. En d'autres termes, ce ne sera d'aucune aide à un éventuel cryptanaliste de connaître l'algorithme utilisé. La connaissance de l'algorithme est nécessaire seulement s'il a obtenu la clé. Les procédés de chiffrement utilisés dans GnuPG vérifient cette propriété.
Comme toute la sécurité repose sur la clé, il est très important qu'il soit très difficile de deviner la clé. Autrement dit, l'ensemble des clés possibles, c'est à dire l'espace des clés se doit d'être grand. Lorsqu'il était à Los Alamos, Richard Feynman était célèbre pour sa capacité à forcer les coffres forts. Pour encourager le mythe, il transportait presque toujours avec lui un ensemble d'outils incluant un vieux stéthoscope. En réalité, il utilisait une quantité d'astuces pour réduire le nombre de combinaisons, il devait donc en essayer un petit nombre et continuait jusqu'à ce qu'il trouve la bonne. En d'autres termes, il réduisait la taille de l'espace des clés.
Les anglais utilisaient des machines pour découvrir les clés pendant la seconde guerre mondiale. La machine allemande Enigma avait un espace de clés très grand, mais les anglais ont construit des machines à calculer spécialisées dénommées les Bombes, pour essayer mécaniquement les clés, jusqu'à ce que la clé du jour soit trouvée. Cela signifie que parfois ils trouvaient la clé du jour pendant qu'elle était utilisée, mais cela signifie aussi que certains jours ils ne la trouvaient jamais. Les Bombes n'étaient pas des ordinateurs à proprement parler, mais étaient des précurseurs de nos ordinateurs modernes.
Aujourd'hui, les ordinateurs peuvent deviner des clés très rapidement : c'est la raison pour laquelle la taille des clés est très importante dans les cryptosystèmes modernes. Le procédé DES utilise une clé de 56 bits, ce qui signifie qu'il y a 256 clés possibles. 256 cela fait 72,057,594,037,927,936 clés. Cela fait beaucoup de clés, mais pour un ordinateur de base, essayer l'ensemble des clés est une question de jours. Un ordinateur spécialisé peut le faire en quelques heures. D'un autre côté, les procédés de chiffrement qui ont été conçus plus récemment, comme 3DES, Blowfish ou IDEA utilisent tous une clé de 128 bits, ce qui signifie qu'il y a 2128 clés possibles. C'est beaucoup, beaucoup trop de clés, et même si tous les ordinateurs de la planète coopéraient, il faudrait encore plus de temps que l'âge de l'univers pour trouver la clé.