Engineer's Book

————— PHYSICS – SPACE – ALGORITHMICS ——-

Algorithmique 02 – Cryptographie : Comment Crypter et Décrypter un nombre en RSA

Written By: Jean-Paul Cipria - Jan• 03•17

Vous voulez décoder la Matrice ?

Codage Privé

Cryptographie, Cyphering : Ce n’est pas parce qu’on ne comprend pas qu’il n’y a pas d’explications ! Jean-Paul Cipria.

Comment encrypter et décrypter un message selon la méthode RSA … 4 bits ?

Il est est assez poilant de faire les calculs que les experts se tapent en bac+8 avec un niveau de 5ième. C’est assez amusant d’essayer de comprendre ? Vous verrez par vous mêmes : « On n’y chique que dalle dans les cours ! » Les « congruents » ou « moldus » nous ont fournis des « démonstrations récursives ». Alors , heureux ! …
Pourtan yadé ecsplicassions ! Yakavoir lebonprof !

It’s pretty fun to do calculations that doctors in computer science are doing and realizing that the concepts are of college level … then … do it ?

Jean-Paul Cipria


.

.
Created :2017-01-03 16:51:09. – Modified : 2017-05-15 10:35:51.


Article Terminé ... Café ?

Article Terminé.



.

Crypter et Transmettre un Message ?

Le message « z »?

On affecte la valeur 26 à la lettre z que nous voulons transmettre (en fait c’est un premier codage) :

  • M=26

Comment trouver les Clefs d’Encryptage et de Décryptage en fonction de p et q ?

Que donnent les Résultats Matlab?

Matlab Résultat : Recherche par méthode d’Euclide et boucle sur 30 valeurs consécutives. N’affiche que les valeurs possibles : (Pas de simulink ni de langages objets : juste des additions, des divisions, …). Nous sommes restés sur des petits nombres. A titre d’exemple :

Fin de Matlab

Crypter M avec la clef publique ?

  • (n,e)=(35,29) Clef publique.
  • C=M^e mod(n)
  • C=26^{29} mod 35=1,0819995774172099689456234729292e+41 mod 35=31

Un coup de bol que cela fonctionne à la calculette de m…de de win$ows ! Sinon utilisez la méthode d’exponentiation modulaire.

Nous transmettons la valeur cryptée ?

  • C=31

A la réception nous décryptons avec la clé privée ?

  • (n,d)=(35,5) Clé privée connue que par le récepteur.
  • M=C^d mod(n)
  • M=31^5 mod(35)=28629151 mod(35)=26
  • M=26

D’où le message « z ». Si tout le monde possède la table d’alphabet qui associe une lettre à un chiffre et du langage français ou autres.

Tables de cryptage par exponentiation modulaire

Codage Matlab par exponentielle 10 « à la main »

En trois coups : nous découpons la puissance e=29=10+10+9 .

Fin Matlab

Table de Cryptage

M0 est le message envoyé. Crypt est la valeur cryptée.

Comment s’authentifier ?

C’est moi ?

J’envoie la lettre « z » à ma dulcinée (z veut dire ze t’m) ou en cryptée 31. Je dis en clair à ma Dulcinée : « Je t’ai envoyé le chiffre crypté 31. Si tu retrouves 26 avec ta clé privée … c’est moi !« 

Pourquoi suis-je authentifié ?

Il n’y a qu’avec la clé cryptée privée que nous pouvons retrouver le nombre 26 en partant du crypté 31, si (e) et (d) sont suffisamment grands. Ce qui n’est pas le cas ici. Je peux révéler le nombre 26 en clair sur la transmission. Si la dulcinée retrouve un autre nombre c’est que quelqu’un n’ayant pas la clé de l’émetteur n’a pas pu trouver le bon code. Encore faut-il ne pas partager sa clé … publique ! Mais la dulcinée peut envoyer aussi un « z » à son amoureux transi ! 😉 Ou alors l’amoureux utilise la clé privée … ce qui évite l’utilisation de la clé publique – C’est symétrique.

Conclusions

« Praticité » de la méthode ?

Le cryptage RSA est lourd, lent, insécure mais utilisé de partout. D’où les concours de nombres premiers à plusieurs millions de décimales. C’est l’A380 ! Très gros aussi ! Mais tout le monde est content. Il vole !

Lourd et lent ? Nous sommes obligés de chercher des exposants d’encryptage, (e) et (d) dans l’article, à … 128 bits soit environ un chiffre de cryptage ou exponentiel à … 35 décimales ! Le calcul d’encryptage et donc lent … lent … lent même si on décompose le PGCD « en puissance qui s’additionnent » comme dirait un CM2. Ce qui est vrai ! Ou que les « congruents » l’appellent « exponentiation modulaire » comme en maternelles supérieures.

Force brute et décryptage « non prévu » ?

Insécure : Transmettez un « z » ou le nombre 26 comme l’exemple de cet article. Si vous transmettez un texte en Français nous trouvons le décodage en 4 à 5 passes ! Il faut donc « désentropiser » ou éliminer l’information de « langue » qu’une transmission lettre par lettre ou mot par mot contient ! C’est pratique ? D’où les enlaçages, les emmêlages, les entrelacements, et autres joyeusetés, compliquées à défaut d’être difficiles à mettre en œuvre.

Avec des clés petites (e=29 ; 2 digits ; 4 bits) un certain nombre de nombres cryptés sont égaux à leurs valeurs non cryptées. Il en existe 10 sur 26 dans l’exemple de cet article !

Entropiser ?

Transmettre le minimum d’information ?

Excusez-nous pour ce néologisme (nouveau mot). Entropiser consiste à enlever une information redondante contenue dans le message. C’est à dire qu’en transmettant le code nous ne sommes pas descendus au minimum réel d’information nécessaire mais suffisante pour se faire décoder à l’autre bout de transmission. Ainsi si nous transmettons la lettre « e », qui est très présente statistiquement en langue française, alors nous allons la repérer facilement. C’est le code « 5 » et le nombre chiffré « 10 » sur la transmission qui va être facilement trouvé s’il se présente aux environs de 12%. Il faut donc que chaque nombre chiffré se présente avec une probabilité de présence de 1/26. C’est à dire que aucune lettre chiffrée ne doit prédominer sur la transmission publique. Le signal doit ressembler à un bruit blanc ou dit « plat ». Mais ce n’est pas obligé si nous affectons aléatoirement une probabilité différente. C’est une ruse.

Bourrer le mou ?

On peut ruser évidemment et augmenter la fréquence relative du « z » par exemple. On fait du « bourrage » mais … on augmente la dimension du message et on est obligé d’augmenter le débit. Ce qui devrait chagriner un ingénieur « normal ». Ce qui n’est pas le cas aujourd’hui ? Nous nous apercevons que quoi que nous fassions nous n’arrivons pas correctement à éliminer ces fréquences d’apparition qui trahissent le codage du message ? En fait il faut changer de paradigme c’est à dire de type de codage. Si nous codons lettre à lettre alors nous conservons la forme et la constitution des mots français. Nous ne chiffrons pas cela ! D’où son apparition en « clair » sur la transmission. Entropiser consiste à éliminer le « contexte » du signal à coder. C’est un peu difficile. En fait il faut transmettre le « sens » ou « meaning » en Anglais. On pourrait transmettre une image ? Malheureusement celle-ci contient 1000 fois plus d’informations parasites que trois mots.

Dictionnaire de codage

Une solution : Il faut construire un dictionnaire des significations qui sont décorrélées d’un alphabet, d’une prononciation. C’est déjà un sacré codage. Mais on peut le livrer au public si nous possédons le bon algorithme de cryptage.

  • je : mlkpt tu : fkjhf il : fheir nous : kdget vous : atfpr ils : sfrte
  • aime : trupe
  • toi : rpoeu

Exemple de Codage

  • « je taime » : « mlkpt trupe rpoeu »

Nous venons d’entropiser le codage ASCII ! Bravo ! Maintenant que nous avons codé le message « je t’aime » nous pouvons le crypter suivant la grille fournie ou par calcul. Mais ici nous avons cassé l’alphabet mais pas … les mots. Il y a trois mots sur la transmission codée … etc …

Entropiser les groupes de mots ?

On peut fournir le dictionnaire de codage mais en général celui-ci est « secret défense ». Le cryptage est classifié « très secret » et c’est le maximum en France dans le domaine militaire. Les méchants, qui sont tous dans l’autre camp, auront quand même du mal à décrypter même si nous fournissons le dico. C’est le but. Mais on n’est jamais trop prudent il n’y a que l’officier transmission, sur ordre du commandant, qui peut consulter le dico.

  • Message : « Sous-Marin d’escorteur route au NE« . 8 mots.
  • Codage : « ldpu plif sueq ». 3 Groupes. Destinataire+Émetteur+Ordre de Navigation.
  • Cryptage : « jhfozdpavmyg ». 1 Groupe. Très Court. Aucune répétition. Fréquence 1/26. Signal bruit.

Références

Acronymes

  • RSA : Ronald Rivest, Adi Shamir et Leonard Adleman.
  • MMSE : Minimum Mean Square Error.
  • RLS : Recursive Least Square.
  • LMS : Least Mean Square.

Livres de références

Algorithme de Codages – Difficult to decipher – A technique called « frequency analysis, » which involves making a list of the symbols and determining their frequency of use to sort out their meaning.

.

Jean-Paul Cipria
04/01/2017

You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Anti-Spam Quiz: