09.07.2003

Qu’est-ce que le cryptage ?

Le cryptage est utilisé par l’humanité depuis le moment même où sont apparues les premières informations secrètes, c’est-à-dire les informations dont l’accès doit être limité. C'était il y a très longtemps - par exemple, l'une des méthodes de cryptage les plus célèbres porte le nom de César, qui, s'il ne l'a pas inventé lui-même, l'a ensuite activement utilisé (voir l'encadré).

La cryptographie garantit que la signification d'un message est cachée et révélée par décryptage à l'aide d'algorithmes et de clés spéciaux. Nous comprenons la clé comme un état secret spécifique des paramètres des algorithmes de cryptage et de déchiffrement. Connaître la clé permet de lire le message secret. Cependant, comme vous le verrez ci-dessous, la méconnaissance de la clé ne garantit pas toujours que le message ne pourra pas être lu par un inconnu.

Le processus consistant à casser un chiffre sans connaître la clé est appelé cryptanalyse. Le temps nécessaire pour déchiffrer un chiffre est déterminé par sa force cryptographique. Plus il est grand, plus l’algorithme de cryptage est « fort ». C'est encore mieux s'il est initialement impossible de savoir si le résultat du piratage est réalisable.

Méthodes de cryptage modernes de base

Parmi les différentes méthodes de cryptage, on distingue les principales méthodes suivantes :

• Algorithmes de remplacement ou de substitution - les caractères du texte source sont remplacés par des caractères d'un autre (ou du même) alphabet conformément à un schéma prédéterminé, qui sera la clé de ce chiffre. Par ailleurs, cette méthode n'est pratiquement pas utilisée dans les cryptosystèmes modernes en raison de sa force cryptographique extrêmement faible.
• Algorithmes de permutation - les caractères du texte original sont échangés selon un certain principe, qui est la clé secrète. L'algorithme de permutation lui-même a une faible force cryptographique, mais est inclus en tant qu'élément dans de nombreux cryptosystèmes modernes.
• Algorithmes gamma - les caractères du texte source sont ajoutés aux caractères d'une certaine séquence aléatoire. L'exemple le plus courant est le cryptage des fichiers « username.pwl », dans lequel le système d'exploitation Microsoft Windows 95 stocke les mots de passe des ressources réseau d'un utilisateur donné (mots de passe pour se connecter aux serveurs NT, mots de passe pour l'accès Internet DialUp, etc.). .

Lorsqu'un utilisateur saisit son mot de passe lors de sa connexion à Windows 95, un gamma (toujours le même) en est généré à l'aide de l'algorithme de cryptage RC4, utilisé pour crypter les mots de passe réseau. La simplicité de sélection du mot de passe dans ce cas est due au fait que Windows préfère toujours le même jeu de couleurs.

• Algorithmes basés sur des transformations mathématiques complexes du texte source selon une certaine formule. Beaucoup d’entre eux utilisent des problèmes mathématiques non résolus. Par exemple, l’algorithme de chiffrement RSA largement utilisé sur Internet repose sur les propriétés des nombres premiers.

Cryptosystèmes symétriques et asymétriques

Avant de passer aux algorithmes individuels, considérons brièvement le concept de cryptosystèmes symétriques et asymétriques. Générer une clé secrète et chiffrer un message avec celle-ci ne représente que la moitié de la bataille. Mais comment envoyer une telle clé à quelqu’un qui doit l’utiliser pour déchiffrer le message original ? La transmission de la clé de chiffrement est considérée comme l’un des principaux problèmes de la cryptographie.

Tout en restant dans le cadre d'un système symétrique (ainsi nommé car la même clé est utilisée pour le chiffrement et le déchiffrement), il est nécessaire de disposer d'un canal de communication fiable pour transmettre la clé secrète. Mais un tel canal n'est pas toujours disponible, c'est pourquoi les mathématiciens américains Diffie, Hellman et Merkle ont développé le concept de clé publique et de cryptage asymétrique en 1976. Dans de tels systèmes cryptographiques, seule la clé du processus de cryptage est accessible au public et la procédure de décryptage n'est connue que du propriétaire de la clé secrète.

Par exemple, lorsque je souhaite qu'un message me soit envoyé, je génère des clés publiques et privées. Je vous l'envoie, vous cryptez le message et me l'envoyez. Moi seul peux décrypter le message, puisque je n'ai donné la clé secrète à personne. Bien entendu, les deux clés sont liées d’une manière particulière (de différentes manières dans chaque système cryptographique) et la distribution de la clé publique ne détruit pas la force cryptographique du système.

Dans les systèmes asymétriques, la condition suivante doit être satisfaite : il n’existe pas d’algorithme (ou on ne le sait pas encore) qui dériverait le texte original du cryptotexte et de la clé publique. Un exemple d’un tel système est le cryptosystème bien connu RSA.

Algorithme RSA

L'algorithme RSA (d'après les premières lettres des noms de famille de ses créateurs Rivest-Shamir-Adleman) est basé sur les propriétés des nombres premiers (et des très grands). Les nombres premiers sont les nombres qui n'ont pas d'autre diviseur qu'eux-mêmes et un. Et les nombres premiers entre eux sont les nombres qui n’ont pas de diviseur commun autre que 1.

Tout d'abord, choisissons deux très grands nombres premiers (de grands nombres premiers sont nécessaires pour construire des clés grandes et fortes. Par exemple, le programme Unix ssh-keygen génère des clés de 1024 bits de long par défaut).

Définissons le paramètre nà la suite d'une multiplication p Et q. Choisissons un grand nombre aléatoire et appelons-le d, et il doit être premier avec le résultat de la multiplication (p-1)*(q-1).

Trouvons un nombre e pour lequel la relation est vraie

(e*d) mod ((p -1)*(q -1)) = 1

(module- reste de la division, c'est-à-dire si e multiplié par d est divisé par ((p -1)*(q -1)), alors le reste est 1).

La clé publique est une paire de chiffres e et n, et fermé - d et n.

Lors du cryptage, le texte source est traité comme une série de nombres, et nous effectuons une opération sur chaque nombre

C(i)= (M(i) e) mod n.

Le résultat est la séquence C(je), qui constituera le cryptotexte. Le décodage des informations s'effectue selon la formule

M(je) = (C(je) d) mod n.

Comme vous pouvez le constater, le décryptage nécessite la connaissance de la clé secrète.

Essayons sur de petits nombres.

Installons p=3, q=7. Alors n=p*q=21. Choisir d comme 5. De la formule (e*5) module 12=1 calculer e=17. Clé publique 17, 21 , secrète - 5, 21 .

Chiffrons la séquence "12345" :

C(1)= 1 17 mod 21= 1

C(2)= 2 17 mod 21 =11

C(3)= 3 17 mod 21= 12

C(4)= 4 17 mod 21= 16

C(5)= 5 17 mod 21= 17

Cryptotexte - 1 11 12 16 17.

Vérifions le décryptage :

M(1)= 1 5 mod 21= 1

M(2)= 11 5 mod 21= 2

M(3)= 12 5 mod 21= 3

M(4)= 16 5 mod 21= 4

M(5)= 17 5 mod 21= 5

Comme vous pouvez le constater, le résultat a coïncidé.

Le cryptosystème RSA est largement utilisé sur Internet. Lorsque vous vous connectez à un serveur sécurisé via SSL, installez un certificat WebMoney sur votre PC ou connectez-vous à un serveur distant à l'aide d'Open SSH ou SecureShell, tous ces programmes utilisent le cryptage à clé publique en utilisant les idées de l'algorithme RSA. Ce système est-il vraiment si fiable ?

Concours de piratage RSA

Depuis sa création, RSA a été constamment soumis à des attaques par force brute. En 1978, les auteurs de l’algorithme publient un article dans lequel ils présentent une chaîne chiffrée avec la méthode qu’ils viennent d’inventer. La première personne à déchiffrer le message recevait une récompense de 100 dollars, mais cela nécessitait de diviser un nombre à 129 chiffres en deux facteurs. Il s'agissait du premier concours permettant de cracker RSA. Le problème n’a été résolu que 17 ans après la publication de l’article.

La force cryptographique de RSA repose sur l'hypothèse selon laquelle il est extrêmement difficile, voire impossible, de déterminer la clé privée à partir de la clé publique. Pour ce faire, il fallait résoudre le problème de l'existence de diviseurs d'un grand entier. Jusqu'à présent, personne ne l'a résolu en utilisant des méthodes analytiques, et l'algorithme RSA ne peut être déchiffré que par la force brute. À proprement parler, l’affirmation selon laquelle le problème de la factorisation est difficile et qu’il est difficile de briser le système RSA n’est pas non plus prouvée.

Le numéro obtenu suite au traitement du texte du message par la fonction de hachage est crypté à l'aide de l'algorithme RSA sur la clé privée de l'utilisateur et envoyé au destinataire avec la lettre et une copie de la clé publique. Le destinataire, à l'aide de la clé publique de l'expéditeur, exécute la même fonction de hachage sur le message entrant. Si les deux nombres sont égaux, cela signifie que le message est authentique, mais si au moins un caractère a été modifié, les nombres ne correspondront pas.

L'un des clients de messagerie les plus courants en Russie, le programme The Bat!, possède des capacités intégrées pour ajouter des signatures numériques aux lettres (faites attention à l'élément de menu Confidentialité lors de la modification d'une lettre). Apprenez-en davantage sur cette technique dans l'article (voir « PC World », n° 3/02).

Riz. 3

Cryptographie

La cryptographie est la science des principes, moyens et méthodes de transformation des informations pour les protéger contre tout accès non autorisé et toute distorsion. Dernièrement, cela s’est développé très, très rapidement. C'est une course sans fin et passionnante qui demande beaucoup de temps et d'efforts : les cryptanalystes déchiffrent des algorithmes qui, jusqu'à récemment, étaient des standards et largement utilisés. À propos, les mathématiciens Dan Goldston (États-Unis) et Kem Ildirim (Turquie) ont récemment prouvé la première régularité dans la distribution des nombres premiers (de telles régularités n'avaient pas été remarquées jusqu'à présent). Les nombres premiers sont situés sur l’axe des nombres dans certains groupes, ce qui les rend un peu plus faciles à trouver.

Les recherches mathématiques menées partout dans le monde conduisent constamment à de nouvelles découvertes. Qui sait, peut-être sommes-nous sur le point de casser l’algorithme RSA ou d’autres cryptosystèmes basés sur des problèmes mathématiques non résolus.

Oleg Bounine- spécialiste du développement de logiciels pour les grands projets Internet, salarié de la société Rambler, http://www..htm).

Système de chiffrement de César

Un exemple d’algorithme de remplacement est le système de cryptage Caesar. Cette méthode consiste à remplacer chaque lettre du message par une autre en décalant l'original d'un nombre fixe de caractères. Essayez de déchiffrer les quatrains d'Omar Khayyam (durée de réalisation - 10 minutes).

RLZ YOMEIZ AVBZHU IYZAVLU, BZHSCHLU ZHSCHEZZHZ ZHUOSCHZ, EYSH YSHCHAZhFO ISHCHYVESH BSHCHIZHV EESH ZHSCHRSCHG : LF EMRSYU ЪZEZESCHG, RYYO RLZ IZISHCHEZ YUKLU, IN EMRSYU BMEU ZEVZH, RYO OYYUKLU K DUYO IZISHCHEZ.

L'avez-vous fait ? Voici la réponse :

Pour vivre sa vie sagement, il faut en savoir beaucoup,

N'oubliez pas deux règles importantes pour commencer :

Tu préfères mourir de faim plutôt que de manger quoi que ce soit

Et il vaut mieux être seul qu’avec n’importe qui.

Clé de décryptage : décalage de sept caractères (prendre le septième) vers la gauche par ordre alphabétique. L'alphabet est en boucle. La casse des caractères n'est pas sensible.

Windows et mots de passe

Comment Windows crypte-t-il les mots de passe ?

Le système prend le mot de passe, le convertit en majuscules, le réduit à 14 caractères, puis les divise en deux moitiés de 7, les chiffre chacune séparément et l'enregistre de cette façon, ce qui facilite un peu le piratage. À propos, lorsque vous proposez un mot de passe, gardez à l'esprit qu'une combinaison de plus de 14 caractères n'a pas de sens.

Concours AES (Advanced Encryption Standard)

Dans les années 80 aux États-Unis, ils ont adopté une norme de cryptage symétrique à usage interne - DES ((Data Encryption Standard, il existe une norme similaire en Russie). Mais en 1997, lorsqu'il est devenu évident que la clé DES de 56 bits n'était pas suffisante pour un cryptosystème, l'American Standards Institute a annoncé un concours pour un nouvel algorithme standard. Parmi 15 options, le meilleur a été choisi : l'algorithme belge Rijndael (son nom est composé des noms des auteurs - Rijmen et Daemen, lu comme « Rijndael »). Cet algorithme est déjà intégré à divers outils cryptographiques fournis sur le marché par d'autres finalistes. Les gagnants du concours étaient MARS, RC6, Serpent, TwoFish. Tous ces algorithmes se sont révélés assez robustes et résistent avec succès à toutes les méthodes de cryptanalyse bien connues. .

Fonctions de hachage cryptographique

Les fonctions de hachage cryptographique convertissent les données d'entrée de n'importe quelle taille en une chaîne de taille fixe. Il est extrêmement difficile de trouver pour eux :

• deux ensembles de données différents avec le même résultat de transformation (résistance aux collisions) ; par exemple, le nombre d'opérations arithmétiques requises pour trouver un bloc de données contenant également un message court pour la fonction de hachage MD5 est d'environ 2,64 ;
• valeur d'entrée basée sur un résultat de hachage connu (irréversibilité) ; pour MD5, le nombre estimé d’opérations nécessaires pour calculer le message d’origine est de 2 128.

Comme vous vous en souvenez, les chiffres de décalage, de substitution, de permutation et de Vernam appliquent une opération à chaque caractère spécifique du texte. Nous devons décaler - nous décalons le caractère, appliquons la clé - l'appliquons au caractère, puis au caractère suivant, et ainsi de suite, jusqu'à ce que nous chiffrions tous les caractères en clair. Cette méthode de cryptage est appelée cryptage de flux : nous chiffrons chaque caractère individuellement. Une autre approche consiste à diviser le texte brut d'origine en groupes de plusieurs caractères (blocs) et à effectuer des opérations de cryptage sur chaque bloc. Il s'agit d'une méthode de cryptage par blocs.

Pour rendre plus claire la différence entre les chiffrements par bloc et par flux, nous donnerons un exemple utilisant un simple chiffrement de substitution.

Cryptage du flux

Chiffrons le mot CIPHER avec un chiffrement de flux de remplacement :

Nous avons chiffré chaque caractère et obtenu un texte chiffré. Cela ne pourrait pas être plus simple.

BLOC DE CHIFFREMENT

Chiffrons le mot AVADAKEDAVRA. Puisque le chiffre est un bloc, nous diviserons le texte brut en blocs de quatre caractères : AVAD | AKED | AVRA (en pratique, les blocs de texte sont constitués de 64 à 256 bits). Pour chaque bloc, nous créerons notre propre tableau de remplacement :

Maintenant, nous chiffrons chacun des blocs avec l'alphabet correspondant :
Cela s'est avéré un peu mieux qu'avec l'approche en ligne, si l'on parle de durabilité. Après tout, nous avons appris à déchiffrer le chiffre de substitution habituel avec une main gauche. Et avec une telle approche par blocs, l'attaquant devra se creuser la tête avant de pouvoir sélectionner la longueur du bloc, puis appliquer la cryptanalyse pour les chiffrements de remplacement pour chaque bloc.

RÉSEAU FEISTEL

Nous sommes maintenant prêts à aborder un sujet très important qui ouvre la porte au monde sans fin des systèmes de cryptage modernes. Le réseau Feistel est une méthode de chiffrement par blocs développée par Horst Feistel au laboratoire IBM en 1971. Aujourd'hui, le réseau Feistel sous-tend un grand nombre de protocoles cryptographiques. Essayons de comprendre « sur les doigts » ce que c'est.

Le réseau Feistel fonctionne sur des blocs de texte clair, nous allons donc examiner le mécanisme de son fonctionnement sur l'un des blocs. Les actions pour les blocs restants seront similaires.

• Le bloc est divisé en deux parties égales : gauche (L) et droite (R).
• Après partitionnement, le sous-bloc gauche est modifié par une fonction f à l'aide de la clé K : x = f(L, K). En tant que fonction, vous pouvez imaginer n'importe quelle transformation que vous aimez - par exemple, le bon vieux chiffre par décalage avec la clé K.
• Le sous-bloc résultant est ajouté modulo 2 avec le sous-bloc droit R, qui n'était pas utilisé auparavant : x=x+R
• Ensuite, les pièces résultantes sont échangées et collées ensemble.

Comme vous pouvez le constater, tout est assez simple. Pour comprendre comment cela fonctionne, regardez le schéma :

Cet arrangement est appelé cellule de Feistel. Le réseau Feistel lui-même se compose de plusieurs cellules. Les sous-blocs obtenus en sortie de la première cellule vont à l'entrée de la deuxième cellule, les sous-blocs résultants de la deuxième cellule vont à l'entrée de la troisième cellule, et ainsi de suite, en fonction du nombre de tours du réseau Feistel. Dans chacun de ces tours, une clé de tour prédéterminée est utilisée. Le plus souvent, les clés rondes sont générées à partir de la clé secrète principale K. Lorsque tous les tours sont terminés, les sous-blocs de texte sont collés ensemble et un texte chiffré normal est obtenu.

Regardons maintenant le fonctionnement du réseau Feistel à l'aide d'un exemple. Prenons le mot AVADAKEDAVRA et divisons-le en deux blocs de six caractères - AVADAK | ÉDAVRA. Pour la fonction on prend le chiffre de décalage du nombre de positions déterminé par la clé ronde. Soit la clé secrète K = . Comme clés rondes, nous prenons K = 1, K = 2. Pour l'addition modulo 2, nous convertissons le texte en code binaire selon l'alphabet télégraphique, que presque personne d'autre n'utilise.

Voici ce qui s'est passé :

Passons maintenant au premier bloc via le réseau Feistel en deux tours :

Essayez de chiffrer le deuxième bloc vous-même, j'ai MOSSTR.

Le déchiffrement s'effectue exactement de la même manière : le texte chiffré est divisé en blocs puis sous-blocs, le sous-bloc de gauche entre dans la fonction, s'ajoute modulo 2 avec celui de droite, puis les sous-blocs sont intervertis. La différence est que les clés rondes sont soumises dans l'ordre inverse, c'est-à-dire que dans notre cas, au premier tour nous utiliserons la clé K = 2, puis au deuxième tour K = 1.

Des recherches sur le réseau Feistel ont montré qu'avec des clés rondes indépendantes et une fonction pseudo-aléatoire f crypto-résistante, trois tours du réseau Feistel suffiront pour que le texte chiffré soit pseudo-aléatoire. Cela suggère que les chiffrements basés sur le réseau Feistel sont actuellement assez sécurisés.

GOST 28147-89 (MAGMA)

Nous avons déjà presque tous les concepts nécessaires dans notre arsenal, nous sommes donc prêts à passer au premier sujet important de la cryptographie nationale - GOST 28147-89. Il vaut la peine de dire que seuls les paresseux n'ont pas écrit sur cette norme, je vais donc essayer pour la millionième et première fois de décrire brièvement et sans nuage de formules l'essence des modes de cryptage du grand et terrible Magma. Si vous décidez de lire la norme elle-même, vous devez alors faire le plein de temps, d'énergie, de patience et de nourriture, car, comme vous le savez, il est strictement interdit d'écrire des normes en langage humain.

Caractéristiques principales : clé 256 bits, bloc 64 bits.

Avant d'analyser Magma, vous devez apprendre un nouveau concept : les tables de substitution, ou S-box. Il s'agit du même type de table que la table du chiffre de substitution. Conçu pour remplacer les symboles de sous-blocs par des symboles enregistrés dans le tableau. Ne pensez pas que la S-box est constituée de nombres aléatoires générés par la fonction rand(). Les boîtes S sont le résultat de séquences générées de manière réfléchie, car c’est sur elles que repose la force cryptographique de l’ensemble du chiffre.

GOST 28147 décrit ses tables de remplacement avec beaucoup de parcimonie. Il indique seulement qu’ils constituent un élément secret supplémentaire (avec la clé secrète) et qu’ils sont « remis de la manière prescrite ». Rien de plus. Depuis l'adoption de GOST 28147, l'incertitude scientifique et technique liée au choix des S-box a donné lieu à des rumeurs et à des spéculations. On a parlé de critères secrets connus uniquement des développeurs de GOST. Naturellement, cette incertitude a réduit la confiance dans le cryptosystème.

Cette lacune constitue une excellente base pour critiquer la norme. Le cryptographe français Nicolas Courtois a publié plusieurs articles contenant un certain nombre de dispositions controversées concernant la force de GOST. Courtois estime que la norme russe est facile à attaquer et ne peut être considérée comme internationale. Cependant, Courtois effectue son analyse pour des S-box autres que celles réelles, vous ne devez donc pas vous fier à son opinion.

Voyons maintenant ce qu'ils ont trouvé entre les murs de la sombre Loubianka.

Mode de remplacement facile

En mode remplacement simple pour 32 tours, selon la norme, nous avons besoin de 32 clés rondes. Pour générer des clés rondes, la clé originale de 256 bits est divisée en huit blocs de 32 bits : K1…K8. Les touches K9...K24 sont une répétition cyclique des touches K1...K8. Les clés K25…K32 sont les clés K8…K1.

1. Chaque bloc de 64 bits est divisé en deux sous-blocs : Ai et Bi.
2. Le sous-bloc gauche Ai est ajouté modulo 232 avec la clé ronde K1 : Ai+1 = Ai + Ki mod 232.
3. Le sous-bloc gauche passe par la S-box.
4. Les bits du sous-bloc gauche sont décalés de 11 positions (décalage cyclique).
5. Le sous-bloc de gauche s'additionne à celui de droite modulo 2 : A = A ⊕ B . iii
6. Le sous-bloc droit prend la valeur initiale du sous-bloc gauche : Bi+1 = Ai.
7. Les sous-blocs sont échangés.

Juste un exemple d'un tour. Clé de 256 bits :

Puis les clés rondes

Comment utiliser cette S-box ? Très simple ! Si l'entrée de la S-box est 0, alors la sortie sera 1 (prendre le 0ème symbole de la S-box), si 4, alors la sortie sera 5 (prendre le 4ème symbole), si l'entrée est 7 , alors la sortie sera 4, et ainsi de suite.

Texte brut :

Divisé en deux blocs de 32 bits de bits hauts et bas :

L'exemple, bien sûr, s'est avéré sauvage, car GOST n'est toujours pas une norme telle que tout le monde puisse le parcourir de ses propres mains.

Le mode de remplacement simple est trop simple et présente des inconvénients importants :

• une erreur dans un bloc chiffré corrompt tous les bits de ce bloc ;
• lors du chiffrement de blocs identiques de texte en clair, des blocs identiques de texte chiffré sont obtenus, ce qui peut fournir certaines informations à un cryptanalyste.

Ainsi, il est conseillé d'utiliser GOST 28147-89 en mode de remplacement simple uniquement pour crypter les données clés.

MODE DE JEU

Ce mode ne présente pas les inconvénients du mode de remplacement simple. Le mode gamma est ainsi appelé car il utilise le gamma, une séquence pseudo-aléatoire qui est ajoutée modulo 2 au texte en clair à chaque tour. Gamma est formé à partir du message de synchronisation S - une séquence pseudo-aléatoire qui change à chaque itération et est cryptée en mode de remplacement simple, après quoi elle se transforme en gamma et se superpose au texte clair.

Et maintenant tout est en ordre.

Les étapes 3 à 5 sont répétées pour chaque bloc. Toutes ces manipulations sont visibles sur le schéma.

Le déchiffrement est effectué de la même manière ; au lieu d'un bloc de texte en clair, un bloc de texte chiffré est fourni.

Mode Gamma avec feedback

Soyons plus compliqués. L'algorithme est similaire au mode gamma, mais le gamma est formé sur la base du bloc précédent de données cryptées, donc le résultat du cryptage du bloc actuel dépend également des blocs précédents. 1. Message de synchronisation S - Séquence pseudo-aléatoire de 64 bits.

2. S est crypté en mode de remplacement simple.
3. Le texte en clair est ajouté modulo 2 au gamma résultant.
4. Le texte chiffré résultant est envoyé sous forme de message de synchronisation pour le bloc suivant et est également envoyé à la sortie. Vous pouvez voir à quoi cela ressemble sur le diagramme.

Mode d'insertion simulé

Dans ce mode, une insertion simulée est générée - un bloc supplémentaire d'une longueur fixe, en fonction du texte source et des clés. Un si petit bloc est nécessaire pour confirmer qu'aucune distorsion n'a été introduite accidentellement ou intentionnellement dans le texte chiffré, c'est-à-dire pour vérifier l'intégrité. Ce mode fonctionne comme ceci :

1. Un bloc de texte brut passe par 16 tours en mode de remplacement simple.
2. Un autre bloc de texte en clair est ajouté au bloc résultant modulo 2.
3. La somme passe par 16 tours supplémentaires en mode de remplacement simple.
4. Le bloc de texte en clair suivant est ajouté et à nouveau un simple remplacement, et ainsi de suite jusqu'à ce qu'il n'y ait plus de blocs de texte en clair.

Pour vérifier, le destinataire, après avoir déchiffré le texte, effectue une procédure similaire à celle décrite. Si le résultat ne correspond pas à l'insert imitatif transmis, tous les blocs M correspondants sont considérés comme faux.

GOST 34.12-2015 (SAUTERELLE)

Beaucoup considèrent GOST 28147-89 comme obsolète et pas assez robuste par rapport aux algorithmes étrangers. Pour le remplacer, les cryptographes nationaux ont publié une nouvelle norme de cryptage. Ils disent que cela s'est produit soit à cause du grand nombre d'attaques contre l'ancien GOST, soit parce que cette longueur de bloc est déjà obsolète et trop petite pour les ensembles de données modernes. Personne n’annonce les véritables raisons. Bien entendu, quelques modifications ont été apportées aux principales caractéristiques.

Caractéristiques principales : clé 256 bits, bloc 128 bits.

Il convient également de dire que dans la nouvelle norme, les boîtes S sont fixes et réfléchies, il n'est donc pas nécessaire d'inventer vos propres substitutions aléatoires miraculeuses. Le nouveau GOST propose de nombreux autres modes de cryptage :
mode de remplacement simple (Electronic Codebook, ECB) ;
mode gamma (Compteur, CTR) ;
mode gamma avec retour de sortie (Output Feedback, OFB) ;
mode de remplacement simple avec engagement (Cipher Block Chaining, SBC) ;
mode gamma avec retour de texte chiffré (Cipher Feedback, CFB) ;
mode de génération d'insertion de simulation (algorithme de code d'authentification de message).

Regardons les nouveaux modes.

Mode de remplacement facile avec engagement

Comme on l'a vu dans la norme précédente, le mode de remplacement simple est le plus faible des modes, donc dans la nouvelle norme, il dépasse désormais avec l'engagement et n'est plus aussi simple du tout.

1. Un vecteur d'initialisation semble effrayant, mais en réalité, ce n'est qu'une séquence de bits entrant dans l'entrée.
2. Le vecteur est divisé en deux parties - L et R, dont l'une est ajoutée modulo 2 avec le texte en clair et l'autre devient la moitié du vecteur d'initialisation du bloc suivant.
3. La somme du texte en clair et d'un morceau du vecteur d'initialisation est transmise via un simple chiffre de substitution.
4. Les blocs de texte chiffré résultants sont collés ensemble.

Dès que vous regardez le schéma, tout devient immédiatement clair.

Bien entendu, le vecteur d’initialisation n’est pas si simple : il subit une série de transformations linéaires (à l’aide d’un registre à décalage linéaire) avant de commencer à chiffrer un nouveau bloc. Mais pour se familiariser avec le chiffre, il suffit d'imaginer un tel schéma. Le décryptage dans ce mode n’est pas non plus tout à fait évident, il est donc préférable de regarder le schéma.

Pour les plus - Les cryptages. Parmi les développements nationaux figure le fournisseur de cryptographie CryptoPro CSP.

Quelques mots sur la force des modes de cryptage. De nombreux cryptographes étrangers ont tenté de s'opposer à notre norme, mais à l'heure actuelle, aucune attaque connue ne peut être mise en œuvre au niveau de développement technologique actuel. Pendant longtemps, cette norme n'a pas été très populaire parmi les programmeurs, car il est difficile de comprendre l'algorithme de fonctionnement à partir de son texte et il n'y a pas suffisamment de descriptions plus claires. Mais il existe déjà de nombreuses implémentations dans de nombreux langages de programmation. Alors maintenant, l'utilisation de GOST est tout à fait possible et dépasse à bien des égards les normes étrangères. Au final, où est le patriotisme ?!

Sergueï Panasenko,
Responsable du département développement logiciel chez Ankad,
[email protégé]

Concepts de base

Le processus de conversion de données ouvertes en données cryptées et vice versa est généralement appelé cryptage, et les deux composants de ce processus sont appelés respectivement cryptage et déchiffrement. Mathématiquement, cette transformation est représentée par les dépendances suivantes qui décrivent les actions avec les informations d'origine :

C = Ek1(M)

M" = Dk2(C),

où M (message) est une information ouverte (dans la littérature sur la sécurité de l'information, elle est souvent appelée « texte source ») ;
C (texte chiffré) - le texte chiffré (ou cryptogramme) obtenu à la suite du cryptage ;
E (cryptage) - une fonction de cryptage qui effectue des transformations cryptographiques sur le texte source ;
k1 (clé) - paramètre de la fonction E, appelé clé de cryptage ;
M" - informations obtenues à la suite du décryptage ;
D (déchiffrement) - fonction de décryptage qui effectue des transformations cryptographiques inverses sur le texte chiffré ;
k2 est la clé utilisée pour décrypter les informations.

Le concept de « clé » dans la norme GOST 28147-89 (algorithme de chiffrement symétrique) est défini comme suit : « un état secret spécifique de certains paramètres d'un algorithme de transformation cryptographique, assurant la sélection d'une transformation parmi un ensemble de transformations possibles pour un algorithme donné. En d'autres termes, la clé est un élément unique avec lequel vous pouvez modifier les résultats de l'algorithme de cryptage : le même texte source sera crypté différemment lors de l'utilisation de clés différentes.

Pour que le résultat du décryptage corresponde au message d'origine (c'est-à-dire pour M" = M), deux conditions doivent être remplies simultanément. Premièrement, la fonction de décryptage D doit correspondre à la fonction de cryptage E. Deuxièmement, la clé de décryptage k2 doit correspondre au cryptage. clé k1.

Si un algorithme de cryptage cryptographiquement fort a été utilisé pour le cryptage, alors en l'absence de la clé k2 correcte, il est impossible d'obtenir M" = M. La force cryptographique est la principale caractéristique des algorithmes de cryptage et indique principalement le degré de complexité d'obtention de l'original. texte à partir d'un texte crypté sans clé k2.

Les algorithmes de chiffrement peuvent être divisés en deux catégories : le chiffrement symétrique et asymétrique. Pour le premier, le rapport entre les clés de cryptage et de déchiffrement est défini comme k1 = k2 = k (c'est-à-dire que les fonctions E et D utilisent la même clé de cryptage). Avec le chiffrement asymétrique, la clé de chiffrement k1 est calculée à partir de la clé k2 de telle sorte que la transformation inverse soit impossible, par exemple en utilisant la formule k1 = ak2 mod p (a et p sont les paramètres de l'algorithme utilisé).

Cryptage symétrique

Les algorithmes de cryptage symétriques remontent à l'Antiquité : c'est cette méthode de dissimulation d'informations qui a été utilisée par l'empereur romain Gaius Julius Caesar au 1er siècle avant JC. e., et l’algorithme qu’il a inventé est connu sous le nom de « cryptosystème César ».

Actuellement, l'algorithme de cryptage symétrique le plus connu est le DES (Data Encryption Standard), développé en 1977. Jusqu'à récemment, il s'agissait du « standard américain », puisque le gouvernement de ce pays recommandait son utilisation pour la mise en œuvre de divers systèmes de cryptage de données. Bien que le DES ne devait initialement être utilisé que pendant 10 à 15 ans, les tentatives visant à le remplacer n'ont commencé qu'en 1997.

Nous n'examinerons pas le DES en détail (presque tous les livres de la liste des matériaux supplémentaires en ont une description détaillée), mais nous nous tournerons vers des algorithmes de cryptage plus modernes. Il convient seulement de noter que la principale raison du changement de norme de cryptage est sa force cryptographique relativement faible, la raison en est que la longueur de la clé DES n'est que de 56 bits significatifs. Il est connu que tout algorithme de chiffrement puissant peut être piraté en essayant toutes les clés de chiffrement possibles (ce qu'on appelle l'attaque par force brute). Il est facile de calculer qu'un cluster de 1 million de processeurs, chacun calculant 1 million de clés par seconde, vérifiera 256 options de clés DES en près de 20 heures. Et comme une telle puissance de calcul est tout à fait réaliste par rapport aux normes actuelles, il est clair que. une clé de 56 bits est trop courte et l'algorithme DES doit être remplacé par un algorithme plus puissant.

Aujourd'hui, deux algorithmes de cryptage forts modernes sont de plus en plus utilisés : la norme nationale GOST 28147-89 et la nouvelle norme de cryptage américaine - AES (Advanced Encryption Standard).

Norme GOST 28147-89

L'algorithme défini par GOST 28147-89 (Fig. 1) a une longueur de clé de cryptage de 256 bits. Il crypte les informations en blocs de 64 bits (ces algorithmes sont appelés algorithmes de blocs), qui sont ensuite divisés en deux sous-blocs de 32 bits (N1 et N2). Le sous-bloc N1 est traité d'une certaine manière, après quoi sa valeur est ajoutée à la valeur du sous-bloc N2 (l'ajout est effectué modulo 2, c'est-à-dire que l'opération logique XOR est appliquée - "ou exclusif"), puis les sous-blocs sont échangés . Cette transformation est effectuée un certain nombre de fois (« tours ») : 16 ou 32, selon le mode de fonctionnement de l'algorithme. A chaque tour, deux opérations sont effectuées.

Le premier est la saisie. Le contenu du sous-bloc N1 est additionné modulo 2 avec la partie 32 bits de la clé Kx. La clé de chiffrement complète est représentée comme une concaténation de sous-clés de 32 bits : K0, K1, K2, K3, K4, K5, K6, K7. Lors du processus de cryptage, l'une de ces sous-clés est utilisée, en fonction du numéro de tour et du mode de fonctionnement de l'algorithme.

La deuxième opération est le remplacement de la table. Après codage, le sous-bloc N1 est divisé en 8 parties de 4 bits dont la valeur de chacune est remplacée conformément au tableau de remplacement de cette partie du sous-bloc. Le sous-bloc subit ensuite une rotation de 11 bits vers la gauche.

Remplacements de tables(Boîte de substitution - S-box) sont souvent utilisés dans les algorithmes de cryptage modernes, il convient donc d'expliquer comment une telle opération est organisée.

Les valeurs de sortie des blocs sont enregistrées dans le tableau. Un bloc de données d'une certaine dimension (dans notre cas, 4 bits) possède sa propre représentation numérique, qui détermine le numéro de la valeur de sortie. Par exemple, si la S-box ressemble à 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 et le bloc de 4 bits « 0100 » est arrivé à l'entrée (valeur 4), alors, selon le tableau, la valeur de sortie sera 15, c'est-à-dire « 1111 » (0 a 4, 1 a 11, 2 a 2 ...).

L'algorithme, défini par GOST 28147-89, propose quatre modes de fonctionnement : remplacement simple, gamma, gamma avec retour et génération de pièces jointes d'imitation. Ils utilisent la même transformation de chiffrement décrite ci-dessus, mais comme la finalité des modes est différente, cette transformation s'effectue différemment dans chacun d'eux. En mode remplacement facile

Pour chiffrer chaque bloc d'informations de 64 bits, les 32 tours décrits ci-dessus sont effectués. Dans ce cas, les sous-clés de 32 bits sont utilisées dans l'ordre suivant :

K0, K1, K2, K3, K4, K5, K6, K7, K0, K1, etc. - aux tours 1 à 24 ;

K7, K6, K5, K4, K3, K2, K1, K0 - aux tours 25 à 32.

Le déchiffrement dans ce mode s'effectue exactement de la même manière, mais avec une séquence d'utilisation des sous-clés légèrement différente :

K0, K1, K2, K3, K4, K5, K6, K7 - aux tours 1 à 8 ;

K7, K6, K5, K4, K3, K2, K1, K0, K7, K6, etc. - aux tours 9 à 32.

Tous les blocs sont chiffrés indépendamment les uns des autres, c'est-à-dire que le résultat du chiffrement de chaque bloc dépend uniquement de son contenu (le bloc correspondant du texte original). S'il existe plusieurs blocs identiques de texte original (brut), les blocs de texte chiffré correspondants seront également identiques, ce qui fournit des informations utiles supplémentaires à un cryptanalyste essayant de déchiffrer le chiffre. Par conséquent, ce mode est principalement utilisé pour chiffrer les clés de chiffrement elles-mêmes (des schémas multi-clés sont très souvent mis en œuvre, dans lesquels, pour un certain nombre de raisons, les clés sont cryptées les unes sur les autres). Deux autres modes de fonctionnement sont destinés au cryptage des informations elles-mêmes : gamma et gamma avec feedback. DANS mode gamma

1. Leur remplissage initial est écrit dans les registres N1 et N2 - une valeur de 64 bits appelée message de synchronisation.

2. Le contenu des registres N1 et N2 (dans ce cas, les messages de synchronisation) est crypté en mode de remplacement simple.

3. Le contenu du registre N1 est ajouté modulo (232 - 1) avec la constante C1 = 224 + 216 + 28 + 24, et le résultat de l'addition est écrit dans le registre N1.

4. Le contenu du registre N2 est ajouté modulo 232 avec la constante C2 = 224 + 216 + 28 + 1, et le résultat de l'addition est écrit dans le registre N2.

5. Le contenu des registres N1 et N2 est affiché sous la forme d'un bloc gamma de 64 bits du chiffre (dans ce cas, N1 et N2 forment le premier bloc gamma).

Si le bloc gamma suivant est nécessaire (c'est-à-dire que le cryptage ou le déchiffrement doit continuer), il revient à l'étape 2.

Pour le déchiffrement, gamma est généré de la même manière, puis le texte chiffré et les bits gamma sont à nouveau XOR. Cette opération étant réversible, dans le cas d'une échelle correctement élaborée, on obtient le texte original (tableau).

Cryptage et décryptage en mode gamma

Pour développer le chiffrement nécessaire au décryptage du gamma, l'utilisateur qui déchiffre le cryptogramme doit disposer de la même clé et de la même valeur de message de synchronisation que celles utilisées lors du chiffrement des informations. Sinon, il ne sera pas possible d'obtenir le texte original à partir du texte crypté.

Dans la plupart des implémentations de l'algorithme GOST 28147-89, le message de synchronisation n'est pas secret. Cependant, il existe des systèmes dans lesquels le message de synchronisation est le même élément secret que la clé de cryptage. Pour de tels systèmes, la longueur de clé effective de l'algorithme (256 bits) est augmentée de 64 bits supplémentaires du message secret de synchronisation, qui peuvent également être considérés comme un élément clé.

En mode feedback gamma, pour remplir les registres N1 et N2, à partir du 2ème bloc, ce n'est pas le bloc gamma précédent qui est utilisé, mais le résultat du cryptage du bloc de texte en clair précédent (Fig. 2). Le premier bloc de ce mode est généré de manière tout à fait similaire au précédent.

Riz. 2. Développement d'un chiffrement gamma en mode gamma avec feedback.

Compte tenu du mode génération de préfixes d'imitation, la notion de sujet de génération devrait être définie. Un préfixe est une somme de contrôle cryptographique calculée à l'aide d'une clé de cryptage et conçue pour vérifier l'intégrité des messages. Lors de la génération d'un préfixe d'imitation, les opérations suivantes sont effectuées : le premier bloc de 64 bits du tableau d'informations, pour lequel le préfixe d'imitation est calculé, est écrit dans les registres N1 et N2 et crypté en mode de remplacement simple réduit (le les 16 premiers tours sur 32 sont effectués). Le résultat résultant est additionné modulo 2 avec le bloc d'informations suivant et le résultat est stocké dans N1 et N2.

Le cycle se répète jusqu'au dernier bloc d'informations. Le contenu 64 bits résultant des registres N1 et N2 ou d'une partie d'entre eux à la suite de ces transformations est appelé préfixe d'imitation. La taille du préfixe d'imitation est choisie en fonction de la fiabilité requise des messages : avec la longueur du préfixe d'imitation r bits, la probabilité qu'un changement dans le message passe inaperçu est égale à 2-r. Un préfixe d'imitation de 32 bits est utilisé, c'est-à-dire la moitié du contenu des registres. Cela suffit car, comme toute somme de contrôle, la pièce jointe d'imitation est principalement destinée à protéger contre la distorsion accidentelle des informations. Pour se protéger contre la modification intentionnelle des données, d'autres méthodes cryptographiques sont utilisées, principalement une signature numérique électronique.

Lors de l'échange d'informations, le préfixe d'imitation sert en quelque sorte de moyen de contrôle supplémentaire. Il est calculé pour le texte en clair lorsque des informations sont cryptées et est envoyé avec le texte chiffré. Après décryptage, une nouvelle valeur du préfixe d'imitation est calculée et comparée à celle envoyée. Si les valeurs ne correspondent pas, cela signifie que le texte chiffré a été corrompu lors de la transmission ou que des clés incorrectes ont été utilisées lors du déchiffrement. Le préfixe d'imitation est particulièrement utile pour vérifier le décryptage correct des informations clés lors de l'utilisation de schémas multi-clés.

L'algorithme GOST 28147-89 est considéré comme un algorithme très puissant - à l'heure actuelle, aucune méthode plus efficace n'a été proposée pour sa divulgation que la méthode de la « force brute » mentionnée ci-dessus. Sa haute sécurité est obtenue principalement grâce à la grande longueur de clé - 256 bits. Lors de l'utilisation d'un message de synchronisation secret, la longueur effective de la clé passe à 320 bits et le chiffrement de la table de remplacement ajoute des bits supplémentaires. De plus, la force cryptographique dépend du nombre de tours de transformation, qui, selon GOST 28147-89, devrait être de 32 (le plein effet de dispersion des données d'entrée est obtenu après 8 tours).

Norme AES

Contrairement à l'algorithme GOST 28147-89, qui est resté longtemps secret, la norme de cryptage américaine AES, conçue pour remplacer DES, a été sélectionnée par le biais d'un concours ouvert, au cours duquel toutes les organisations et individus intéressés ont pu étudier et commenter les algorithmes candidats.

Un concours pour remplacer le DES a été annoncé en 1997 par le National Institute of Standards and Technology des États-Unis (NIST - National Institute of Standards and Technology). 15 algorithmes candidats ont été soumis au concours, développés à la fois par des organisations renommées dans le domaine de la cryptographie (RSA Security, Counterpane, etc.) et des particuliers. Les résultats du concours ont été annoncés en octobre 2000 : le gagnant était l'algorithme Rijndael, développé par deux cryptographes belges, Vincent Rijmen et Joan Daemen.

L'algorithme de Rijndael n'est pas similaire à la plupart des algorithmes de chiffrement symétriques connus, dont la structure est appelée « réseau Feistel » et est similaire au GOST russe 28147-89. La particularité du réseau Feistel est que la valeur d'entrée est divisée en deux sous-blocs ou plus, dont une partie à chaque tour est traitée selon une certaine loi, après quoi elle est superposée aux sous-blocs non traités (voir Fig. 1).

Contrairement à la norme de cryptage nationale, l'algorithme de Rijndael représente un bloc de données sous la forme d'un tableau d'octets bidimensionnel de taille 4X4, 4X6 ou 4X8 (l'utilisation de plusieurs tailles fixes du bloc d'informations crypté est autorisée). Toutes les opérations sont effectuées sur des octets individuels du tableau, ainsi que sur des colonnes et des lignes indépendantes.

L'algorithme de Rijndael effectue quatre transformations : BS (ByteSub) - remplacement de table de chaque octet du tableau (Fig. 3) ; SR (ShiftRow) - décalage des lignes du tableau (Fig. 4). Avec cette opération, la première ligne reste inchangée et les autres sont décalées cycliquement octet par octet vers la gauche d'un nombre fixe d'octets, en fonction de la taille du tableau. Par exemple, pour un tableau 4X4, les lignes 2, 3 et 4 sont décalées respectivement de 1, 2 et 3 octets. Vient ensuite MC (MixColumn) - une opération sur des colonnes de tableau indépendantes (Fig. 5), lorsque chaque colonne est multipliée par une matrice fixe c(x) selon une certaine règle. Et enfin, AK (AddRoundKey) - ajout d'une clé. Chaque bit du tableau est ajouté modulo 2 au bit correspondant de la clé ronde, qui, à son tour, est calculé d'une certaine manière à partir de la clé de cryptage (Fig. 6).

Riz. 3. Opération BS.

Riz. 4. Opération SR.

Riz. 5. Opération MC.

Le nombre de tours de chiffrement (R) dans l'algorithme de Rijndael est variable (10, 12 ou 14 tours) et dépend de la taille du bloc et de la clé de chiffrement (il existe également plusieurs tailles fixes pour la clé).

Le décryptage est effectué à l'aide des opérations inverses suivantes. Une inversion et un remplacement de table sont effectués sur la table inverse (par rapport à celle utilisée lors du chiffrement). L'opération inverse de SR consiste à faire pivoter les lignes vers la droite plutôt que vers la gauche. L'opération inverse pour MC est la multiplication selon les mêmes règles par une autre matrice d(x) satisfaisant la condition : c(x) * d(x) = 1. L'ajout de la clé AK est l'inverse de lui-même, puisqu'elle utilise uniquement le XOR opération. Ces opérations inverses sont appliquées lors du déchiffrement dans la séquence inverse de celle utilisée lors du chiffrement.

Rijndael est devenu la nouvelle norme en matière de cryptage des données en raison de nombreux avantages par rapport aux autres algorithmes. Tout d’abord, il offre une vitesse de cryptage élevée sur toutes les plates-formes : implémentation logicielle et matérielle. Il se distingue par des possibilités incomparablement meilleures de parallélisation des calculs par rapport aux autres algorithmes soumis au concours. De plus, les besoins en ressources pour son fonctionnement sont minimes, ce qui est important lorsqu'il est utilisé dans des appareils aux capacités informatiques limitées.

Le seul inconvénient de l’algorithme peut être considéré comme son schéma inhérent non conventionnel. Le fait est que les propriétés des algorithmes basés sur le réseau Feistel ont été bien étudiées, et Rijndael, en revanche, peut contenir des vulnérabilités cachées qui ne peuvent être découvertes qu'après un certain temps depuis son utilisation généralisée.

Chiffrement asymétrique

Les algorithmes de chiffrement asymétriques, comme déjà indiqué, utilisent deux clés : k1 - la clé de chiffrement, ou publique, et k2 - la clé de déchiffrement, ou secrète. La clé publique est calculée à partir du secret : k1 = f(k2).

Les algorithmes de chiffrement asymétriques reposent sur l’utilisation de fonctions unidirectionnelles. Par définition, une fonction y = f(x) est unidirectionnelle si : il est facile de calculer pour toutes les valeurs possibles de x et pour la plupart des valeurs possibles de y il est assez difficile de calculer une valeur de x pour laquelle y = f(x).

Un exemple de fonction unidirectionnelle est la multiplication de deux grands nombres : N = P*Q. En soi, une telle multiplication est une opération simple. Cependant, la fonction inverse (décomposition de N en deux grands facteurs), appelée factorisation, selon les estimations de l'époque moderne, est un problème mathématique assez complexe. Par exemple, la factorisation N de dimension 664 bits en P ? Q nécessitera environ 1023 opérations, et pour calculer inversement x pour l'exposant modulaire y = ax mod p avec a, p et y connus (avec les mêmes dimensions de a et p), vous devez effectuer environ 1026 opérations. Le dernier exemple donné s'appelle le problème du logarithme discret (DLP), et ce type de fonction est souvent utilisé dans les algorithmes de chiffrement asymétrique, ainsi que dans les algorithmes utilisés pour créer une signature numérique électronique.

Une autre classe importante de fonctions utilisées dans le chiffrement asymétrique sont les fonctions de porte dérobée unidirectionnelle. Leur définition stipule qu'une fonction est unidirectionnelle avec une porte dérobée si elle est unidirectionnelle et qu'il est possible de calculer efficacement la fonction inverse x = f-1(y), c'est-à-dire si la « porte dérobée » (un nombre secret, appliqué pour une fonction asymétrique) algorithmes de cryptage - la valeur de la clé secrète).

Les fonctions de porte dérobée unidirectionnelle sont utilisées dans l’algorithme de chiffrement asymétrique RSA, largement utilisé.

Algorithme RSA

Développé en 1978 par trois auteurs (Rivest, Shamir, Adleman), il tire son nom des premières lettres des noms de famille des développeurs. La fiabilité de l'algorithme repose sur la difficulté de factoriser de grands nombres et de calculer des logarithmes discrets. Le paramètre principal de l'algorithme RSA est le module système N, qui est utilisé pour effectuer tous les calculs dans le système, et N = P*Q (P et Q sont de grands nombres premiers aléatoires secrets, généralement de même dimension).

La clé secrète k2 est choisie aléatoirement et doit répondre aux conditions suivantes :

1

où PGCD est le plus grand diviseur commun, c'est-à-dire que k1 doit être premier à la valeur de la fonction d'Euler F(N), cette dernière étant égale au nombre d'entiers positifs compris entre 1 et N premiers à N, et est calculé comme F(N) = (P - 1)*(Q - 1).

La clé publique k1 est calculée à partir de la relation (k2*k1) = 1 module F(N), et à cet effet l'algorithme euclidien généralisé (l'algorithme de calcul du plus grand diviseur commun) est utilisé. Le chiffrement du bloc de données M à l'aide de l'algorithme RSA s'effectue de la manière suivante : C=M [à la puissance k1] mod N. A noter que puisque dans un cryptosystème réel utilisant RSA le nombre k1 est très grand (actuellement sa dimension peut atteindre jusqu'à 2048 bits), le calcul direct de M [à la puissance k1] irréaliste. Pour l'obtenir, une combinaison de quadrature répétée de M et de multiplication des résultats est utilisée.

L'inversion de cette fonction pour les grandes dimensions n'est pas réalisable ; en d’autres termes, il est impossible de trouver M étant donné les valeurs C, N et k1 connues. Cependant, disposant d'une clé secrète k2, à l'aide de transformations simples on peut calculer M = Ck2 mod N. Évidemment, en plus de la clé secrète elle-même, il faut assurer le secret des paramètres P et Q. Si un attaquant obtient leurs valeurs , il pourra calculer la clé secrète k2.

Quel cryptage est le meilleur ?

Le principal inconvénient du chiffrement symétrique est la nécessité de transférer les clés « de main en main ». Cet inconvénient est très grave, car il rend impossible l'utilisation du chiffrement symétrique dans des systèmes comportant un nombre illimité de participants. Cependant, le cryptage symétrique présente certains avantages qui sont clairement visibles dans le contexte des graves inconvénients du cryptage asymétrique.

Le premier d’entre eux est la faible vitesse des opérations de chiffrement et de décryptage, due à la présence d’opérations gourmandes en ressources. Un autre inconvénient « théorique » est que la force cryptographique des algorithmes de chiffrement asymétrique n’a pas été mathématiquement prouvée. Cela est principalement dû au problème du logarithme discret - il n'a pas encore été prouvé que sa solution dans un délai acceptable est impossible. Des difficultés inutiles sont également créées par la nécessité de protéger les clés publiques contre la substitution - en remplaçant la clé publique d'un utilisateur légal, un attaquant pourra crypter un message important avec sa clé publique et ensuite le déchiffrer facilement avec sa clé privée.

Toutefois, ces inconvénients n’empêchent pas l’utilisation généralisée d’algorithmes de chiffrement asymétrique. Il existe aujourd'hui des systèmes de chiffrement qui prennent en charge la certification des clés publiques, ainsi que la combinaison d'algorithmes de chiffrement symétriques et asymétriques. Mais c'est un sujet pour un article séparé.

Algorithme RSA : http://www.rsasecurity.com/rsalabs/pkcs/pkcs-1.

Au 21e siècle, la cryptographie joue un rôle important dans la vie numérique des gens modernes. Examinons brièvement les moyens de crypter les informations.

La cryptographie n'est pas qu'une simple affaire informatique

Très probablement, vous avez déjà rencontré la cryptographie de base et connaissez peut-être certaines méthodes de cryptage. Par exemple, le chiffre de César est souvent utilisé dans les jeux éducatifs pour enfants.

ROT13 est un autre type courant de cryptage de messages. Dans celui-ci, chaque lettre de l'alphabet est décalée de 13 positions, comme le montre la figure :

Comme vous pouvez le constater, ce chiffre n'assure pas une sécurité des informations vraiment fiable : il s'agit d'un exemple simple et compréhensible de toute l'idée de la cryptographie.

Aujourd’hui, nous parlons le plus souvent de cryptographie dans le contexte de certaines technologies. Comment les informations personnelles et financières sont-elles transmises en toute sécurité lorsque nous effectuons un achat en ligne ou consultons des comptes bancaires ? Comment pouvez-vous stocker des données en toute sécurité afin que personne ne puisse simplement ouvrir votre ordinateur, retirer le disque dur et avoir un accès complet à toutes les informations qu'il contient ? Nous répondrons à ces questions et à d’autres dans cet article.

Définitions de cybersécurité et guide de démarrage rapide

En matière de cybersécurité, un certain nombre de choses inquiètent les utilisateurs lorsqu'il s'agit de données. Ceux-ci incluent la confidentialité, l’intégrité et la disponibilité des informations. Confidentialité

– les données ne peuvent pas être reçues ou lues par des utilisateurs non autorisés. Intégrité des informations

– la confiance que les informations resteront intactes à 100 % et ne seront pas modifiées par un attaquant. Disponibilité des informations

– accéder aux données lorsque cela est nécessaire.

Cet article examinera également les différentes formes de cryptographie numérique et comment elles peuvent contribuer à atteindre les objectifs énumérés ci-dessus.

• Méthodes de cryptage de base :
• Symétrique
• Asymétrique
• Hachage

Cryptage symétrique

Avant d’entrer dans le vif du sujet, répondons à une question simple : qu’entend-on exactement par « cryptage » ? Le cryptage est la transformation d'informations pour les cacher aux personnes non autorisées, tout en permettant aux utilisateurs autorisés d'y accéder.

Pour crypter et déchiffrer correctement les données, vous avez besoin de deux choses : les données et la clé de déchiffrement. Lors de l'utilisation du chiffrement symétrique, la clé de chiffrement et de déchiffrement des données est la même. Prenons une chaîne et chiffrons-la à l'aide de Ruby et OpenSSL :

Rubis

require "openssl" require "pry" data_to_encrypt = "maintenant vous pouvez me lire !" cipher = OpenSSL::Cipher.new("aes256") cipher.encrypt key = cipher.random_key iv = cipher.random_iv data_to_encrypt = cipher.update(data_to_encrypt) + cipher.final Binding.pry true

Voici ce que le programme va afficher :

Veuillez noter que la variable data_to_encrypt, qui était à l’origine la phrase « maintenant tu peux me lire ! » est maintenant un tas de caractères incompréhensibles. Inversons le processus en utilisant la clé initialement stockée dans une variable clé.

Après avoir utilisé la même clé que celle que nous avons définie pour le cryptage, nous déchiffrons le message et obtenons la chaîne d'origine.

Examinons d'autres méthodes de cryptage.

Chiffrement asymétrique

Le problème du chiffrement symétrique est le suivant : supposons que vous deviez envoyer des données sur Internet. Si la même clé est requise pour crypter et déchiffrer les données, elle doit être envoyée en premier. Cela signifie que la clé devra être envoyée via une connexion non sécurisée. Mais de cette façon, la clé peut être interceptée et utilisée par un tiers. Pour éviter ce résultat, le cryptage asymétrique a été inventé.

Pour utiliser le chiffrement asymétrique, vous devez générer deux clés mathématiquement liées. L’une est une clé privée à laquelle vous seul avez accès. Le second est ouvert et accessible au public.

Regardons un exemple de communication utilisant le cryptage asymétrique. Dans celui-ci, le serveur et l'utilisateur s'enverront des messages. Chacun d'eux possède deux clés : privée et publique. Il a été dit plus tôt que les clés étaient connectées. Ceux. Un message chiffré avec une clé privée ne peut être déchiffré qu'à l'aide d'une clé publique adjacente. Par conséquent, pour démarrer la communication, vous devez échanger des clés publiques.

Mais comment comprendre que la clé publique du serveur appartient à ce serveur en particulier ? Il existe plusieurs façons de résoudre ce problème. La méthode la plus courante (et celle utilisée sur Internet) est l’utilisation d’une infrastructure à clé publique (PKI). Dans le cas des sites Web, il existe une autorité de certification qui dispose d'un répertoire de tous les sites Web pour lesquels des certificats et des clés publiques ont été délivrés. Lorsque vous vous connectez à un site Web, sa clé publique est d'abord vérifiée par une autorité de certification.

Créons une paire de clés publiques et privées :

Rubis

require "openssl" require "pry" data_to_encrypt = "maintenant vous pouvez me lire !" clé = OpenSSL :: PKey :: RSA.new (2048) liaison.pry vrai

Il s'avérera :

Notez que la clé privée et la clé publique sont des entités distinctes avec des identifiants différents. En utilisant #private_encrypt, vous pouvez chiffrer une chaîne à l'aide d'une clé privée et en utilisant #public_decrypt– décrypter le message :

Informations de hachage

Le hachage, contrairement au chiffrement symétrique et asymétrique, est une fonction unidirectionnelle. Il est possible de créer un hachage à partir de certaines données, mais il n'existe aucun moyen d'inverser le processus. Cela fait du hachage un moyen peu pratique de stocker des données, mais il convient pour vérifier l’intégrité de certaines données.

La fonction prend certaines informations en entrée et génère une chaîne apparemment aléatoire qui aura toujours la même longueur. Une fonction de hachage idéale produit des valeurs uniques pour différentes entrées. La même entrée produira toujours le même hachage. Par conséquent, le hachage peut être utilisé pour vérifier l’intégrité des données.

Le besoin de chiffrer la correspondance est apparu dans le monde antique et de simples chiffres de remplacement sont apparus. Les messages cryptés ont déterminé le sort de nombreuses batailles et ont influencé le cours de l'histoire. Au fil du temps, les gens ont inventé des méthodes de cryptage de plus en plus avancées.

Soit dit en passant, le code et le chiffre sont des concepts différents. La première consiste à remplacer chaque mot du message par un mot de code. La seconde consiste à chiffrer chaque symbole d’information à l’aide d’un algorithme spécifique.

Après que les mathématiques ont commencé à coder l’information et que la théorie de la cryptographie a été développée, les scientifiques ont découvert de nombreuses propriétés utiles de cette science appliquée. Par exemple, les algorithmes de décodage ont permis de déchiffrer des langues mortes comme l’égyptien ancien ou le latin.

Stéganographie

La stéganographie est plus ancienne que le codage et le cryptage. Cet art est apparu il y a longtemps. Cela signifie littéralement « écriture cachée » ou « écriture secrète ». Bien que la stéganographie ne corresponde pas exactement à la définition d’un code ou d’un chiffre, elle a pour but de cacher des informations aux regards indiscrets.

La stéganographie est le chiffre le plus simple. Des exemples typiques sont des notes avalées recouvertes de cire ou un message sur une tête rasée cachée sous des cheveux poussés. L'exemple le plus clair de stéganographie est la méthode décrite dans de nombreux livres policiers anglais (et pas seulement), lorsque les messages sont transmis via un journal où les lettres sont discrètement marquées.

Le principal inconvénient de la stéganographie est qu’elle peut être remarquée par un étranger attentif. Par conséquent, pour empêcher la lecture facile du message secret, des méthodes de cryptage et de codage sont utilisées en conjonction avec la stéganographie.

ROT1 et chiffre César

Le nom de ce chiffre est ROTate 1 lettre vers l'avant, et il est connu de nombreux écoliers. Il s'agit d'un simple chiffre de substitution. Son essence est que chaque lettre est cryptée en décalant l'alphabet d'une lettre vers l'avant. A -> B, B -> B, ..., I -> A. Par exemple, chiffrons la phrase « notre Nastya pleure fort » et obtenons « obshb Obtua dspnlp rmbsheu ».

Le chiffrement ROT1 peut être généralisé à un nombre arbitraire de décalages, il est alors appelé ROTN, où N est le nombre par lequel le cryptage des lettres doit être décalé. Sous cette forme, le chiffre est connu depuis l’Antiquité et est appelé « chiffre de César ».

Le chiffre de César est très simple et rapide, mais il s’agit d’un simple chiffre à permutation unique et est donc facile à déchiffrer. Ayant un inconvénient similaire, il ne convient que pour les farces des enfants.

Chiffres de transposition ou de permutation

Ces types de chiffres à permutation simples sont plus sérieux et ont été activement utilisés il n'y a pas si longtemps. Pendant la guerre civile américaine et la Première Guerre mondiale, il était utilisé pour transmettre des messages. Son algorithme consiste à réarranger les lettres - écrire le message dans l'ordre inverse ou réorganiser les lettres par paires. Par exemple, chiffrons la phrase « Le code Morse est aussi un chiffre » -> « Akubza ezrom - ezhot rfish ».

Avec un bon algorithme qui déterminait des permutations arbitraires pour chaque symbole ou groupe d’entre eux, le chiffre est devenu résistant au simple craquage. Mais! Seulement en temps voulu. Étant donné que le chiffre peut être facilement déchiffré par simple force brute ou par correspondance avec un dictionnaire, n'importe quel smartphone peut aujourd'hui le déchiffrer. Par conséquent, avec l’avènement des ordinateurs, ce chiffre est également devenu un code pour enfants.

Code Morse

L'alphabet est un moyen d'échange d'informations et sa tâche principale est de rendre les messages plus simples et plus compréhensibles à transmettre. Bien que cela soit contraire à l’objectif du cryptage. Néanmoins, cela fonctionne comme les chiffres les plus simples. Dans le système Morse, chaque lettre, chiffre et signe de ponctuation possède son propre code, composé d'un groupe de tirets et de points. Lors de la transmission d'un message à l'aide du télégraphe, les tirets et les points représentent des signaux longs et courts.

Le télégraphe et l'alphabet furent les premiers à breveter « son » invention en 1840, bien que des dispositifs similaires aient été inventés avant lui en Russie et en Angleterre. Mais peu importe maintenant… Le télégraphe et le code Morse ont eu une très grande influence sur le monde, permettant la transmission quasi instantanée de messages sur des distances continentales.

Substitution monoalphabétique

Les codes ROTN et Morse décrits ci-dessus sont des représentants des polices de remplacement monoalphabétiques. Le préfixe « mono » signifie que lors du cryptage, chaque lettre du message d'origine est remplacée par une autre lettre ou code issu d'un seul alphabet de cryptage.

Déchiffrer des chiffres de substitution simples n'est pas difficile, et c'est leur principal inconvénient. Ils peuvent être résolus par une simple recherche ou. Par exemple, on sait que les lettres les plus utilisées dans la langue russe sont « o », « a », « i ». Ainsi, nous pouvons supposer que les lettres qui apparaissent le plus souvent dans le texte chiffré signifient soit « o », « a » ou « i ». Sur la base de ces considérations, le message peut être déchiffré même sans recherche informatique.

Marie Ier, reine d'Écosse de 1561 à 1567, est connue pour avoir utilisé un chiffre de substitution monoalphabétique très complexe avec de multiples combinaisons. Pourtant, ses ennemis furent capables de déchiffrer les messages, et l’information fut suffisante pour condamner la reine à mort.

Chiffre de Gronsfeld, ou substitution polyalphabétique

Les chiffres simples sont considérés comme inutiles par la cryptographie. Beaucoup d’entre eux ont donc été modifiés. Le chiffre de Gronsfeld est une modification du chiffre de César. Cette méthode est beaucoup plus résistante au piratage et consiste dans le fait que chaque caractère de l'information codée est crypté à l'aide de l'un des différents alphabets, qui se répètent cycliquement. On peut dire qu'il s'agit d'une application multidimensionnelle du chiffre de substitution le plus simple. En fait, le chiffre de Gronsfeld est très similaire à celui présenté ci-dessous.

Algorithme de chiffrement ADFGX

Il s’agit du chiffre le plus célèbre de la Première Guerre mondiale utilisé par les Allemands. Le chiffre tire son nom du fait qu'il réduisait tous les chiffrements à l'alternance de ces lettres. Le choix des lettres elles-mêmes était déterminé par leur commodité lors de leur transmission sur des lignes télégraphiques. Chaque lettre du chiffre est représentée par deux. Examinons une version plus intéressante du carré ADFGX qui comprend des nombres et s'appelle ADFGVX.

L'algorithme de composition du carré ADFGX est le suivant :

1. Nous prenons n lettres aléatoires pour désigner les colonnes et les lignes.
2. Nous construisons une matrice N x N.
3. Nous entrons dans la matrice l'alphabet, les chiffres, les signes, dispersés aléatoirement dans les cellules.

Faisons un carré similaire pour la langue russe. Par exemple, créons un carré ABCD :

Cette matrice semble étrange, puisqu'un certain nombre de cellules contiennent deux lettres. C’est acceptable ; le sens du message n’est pas perdu. Il peut être facilement restauré. Chiffrons l'expression « Compact Cipher » à l'aide de ce tableau :

Ainsi, le message final crypté ressemble à ceci : « bvgvgbgdagbvdbabdgvdvaadbbga ». Bien entendu, les Allemands ont suivi une ligne similaire en utilisant plusieurs autres chiffres. Et le résultat était un message crypté très résistant au piratage.

Chiffre de Vigenère

Ce chiffre est d'un ordre de grandeur plus résistant au craquage que les chiffrements monoalphabétiques, bien qu'il s'agisse d'un simple chiffre de remplacement de texte. Cependant, grâce à son algorithme robuste, il a longtemps été considéré comme impossible à pirater. Ses premières mentions remontent au XVIe siècle. Vigenère (un diplomate français) est considéré à tort comme son inventeur. Pour mieux comprendre de quoi nous parlons, considérons le tableau de Vigenère (carré Vigenère, tabula recta) pour la langue russe.

Commençons par chiffrer la phrase « Kasperovich rit ». Mais pour que le cryptage réussisse, vous avez besoin d'un mot-clé – que ce soit « mot de passe ». Commençons maintenant le cryptage. Pour ce faire, on note la clé tellement de fois que le nombre de lettres qu'elle contient correspond au nombre de lettres de la phrase cryptée, en répétant la clé ou en la coupant :

Maintenant, en utilisant le plan de coordonnées, nous recherchons une cellule qui est l'intersection de paires de lettres, et nous obtenons : K + P = b, A + A = B, C + P = B, etc.

Nous obtenons que « Kasperovitch rit » = « abvyusnyugshch eykhzhgal ».

Décrypter le chiffre de Vigenère est si difficile car l'analyse de fréquence nécessite de connaître la longueur du mot-clé pour que cela fonctionne. Par conséquent, le piratage consiste à lancer au hasard la longueur d’un mot-clé et à essayer de déchiffrer le message secret.

Il faut également mentionner qu'en plus d'une clé totalement aléatoire, une toute autre table de Vigenère peut être utilisée. Dans ce cas, le carré Vigenère est constitué de l'alphabet russe écrit ligne par ligne avec un décalage de un. Ce qui nous amène au chiffre ROT1. Et tout comme dans le chiffre de César, le décalage peut être n'importe quoi. De plus, l’ordre des lettres ne doit pas nécessairement être alphabétique. Dans ce cas, la table elle-même peut être une clé, sans savoir laquelle il sera impossible de lire le message, même en connaissant la clé.

Codes

Les codes réels sont constitués de correspondances pour chaque mot d'un code distinct. Pour travailler avec eux, vous avez besoin de ce qu'on appelle des livres de codes. En fait, il s'agit du même dictionnaire, contenant uniquement des traductions de mots en codes. Un exemple typique et simplifié de codes est la table ASCII - le chiffrement international de caractères simples.

Le principal avantage des codes est qu’ils sont très difficiles à déchiffrer. L'analyse de fréquence ne fonctionne presque pas lors du piratage. La faiblesse des codes, ce sont en fait les livres eux-mêmes. Premièrement, leur préparation est un processus complexe et coûteux. Deuxièmement, pour les ennemis, ils se transforment en un objet désiré, et intercepter ne serait-ce qu'une partie du livre les oblige à changer complètement tous les codes.

Au XXe siècle, de nombreux États utilisaient des codes pour transmettre des données secrètes, modifiant ainsi le livre de codes après une certaine période. Et ils recherchaient activement les livres de leurs voisins et opposants.

"Énigme"

Tout le monde sait qu’Enigma était la principale machine de cryptage nazie pendant la Seconde Guerre mondiale. La structure Enigma comprend une combinaison de circuits électriques et mécaniques. Le résultat du chiffrement dépend de la configuration initiale de l'Enigma. Dans le même temps, Enigma modifie automatiquement sa configuration pendant le fonctionnement, cryptant un message de plusieurs manières sur toute sa longueur.

Contrairement aux chiffres les plus simples, Enigma offrait des milliards de combinaisons possibles, ce qui rendait presque impossible la déchiffrement des informations cryptées. À leur tour, les nazis préparaient une combinaison spécifique pour chaque jour, qu’ils utilisaient un jour spécifique pour transmettre des messages. Ainsi, même si Enigma tombait entre les mains de l'ennemi, elle ne contribuait en aucune façon au déchiffrement des messages sans entrer quotidiennement dans la configuration nécessaire.

Ils ont activement tenté de briser Enigma tout au long de la campagne militaire d'Hitler. En Angleterre, en 1936, l'un des premiers appareils informatiques (machine de Turing) a été construit à cet effet, qui est devenu le prototype des ordinateurs du futur. Sa tâche consistait à simuler le fonctionnement de plusieurs dizaines d'Enigmas simultanément et à y faire passer les messages nazis interceptés. Mais même la machine de Turing n’était capable de déchiffrer un message qu’occasionnellement.

Chiffrement à clé publique

L'algorithme de cryptage le plus populaire, utilisé partout dans la technologie et les systèmes informatiques. Son essence réside, en règle générale, dans la présence de deux clés, dont l'une est transmise publiquement et la seconde est secrète (privée). La clé publique est utilisée pour chiffrer le message et la clé secrète pour le déchiffrer.

Le rôle de la clé publique est le plus souvent un très grand nombre, qui n'a que deux diviseurs, sans compter un et le nombre lui-même. Ensemble, ces deux diviseurs forment la clé secrète.

Regardons un exemple simple. Soit la clé publique 905. Ses diviseurs sont les nombres 1, 5, 181 et 905. Alors la clé secrète sera, par exemple, le nombre 5*181. Diriez-vous que c'est trop simple ? Et si le numéro public est un numéro à 60 chiffres ? Il est mathématiquement difficile de calculer les diviseurs d’un grand nombre.

Pour un exemple plus réaliste, imaginez que vous retirez de l’argent à un guichet automatique. Lorsqu’une carte est lue, les données personnelles sont cryptées avec une certaine clé publique et, du côté de la banque, les informations sont décryptées avec une clé secrète. Et cette clé publique peut être modifiée à chaque opération. Mais il n'existe aucun moyen de trouver rapidement les diviseurs clés lors de son interception.

Durabilité des polices

La force cryptographique d’un algorithme de chiffrement réside dans sa capacité à résister au piratage. Ce paramètre est le plus important pour tout cryptage. Il est évident que le simple chiffre de substitution, qui peut être déchiffré par n’importe quel appareil électronique, est l’un des plus instables.

À ce jour, il n'existe pas de normes uniformes permettant d'évaluer la force d'un chiffre. Il s’agit d’un processus long et laborieux. Cependant, un certain nombre de commissions ont élaboré des normes dans ce domaine. Par exemple, les exigences minimales pour l'algorithme de cryptage Advanced Encryption Standard ou AES, développé par NIST USA.

Pour référence : le chiffre Vernam est reconnu comme le chiffre le plus résistant au crack. En même temps, son avantage est que, selon son algorithme, il s'agit du chiffre le plus simple.