Tutoriel Chiffrement élémentaire et représentation de l'information

[Yarflam]

Bonjour à tous !
Ce tutoriel sera dédié à la représentation de l'information et au chiffrement élémentaire.
On étudiera les bases mathématiques théoriques et leurs applications (publié en pseudo-code & python).
Je vous souhaite une bonne lecture.

Introduction

Dans toutes les formes de vie sur Terre depuis la création de l'Univers, la transmission de données quo-existe avec le monde physique. L'une des plus complexes et anciennes est l'ADN. Chez l'Homme on peut voir apparaître la mémétique à travers une culture et un langage. Ce sont des bribes de données qui une fois placé dans un contexte vont devenir des informations.

Ces informations sont qualitatives ou quantitatives. Une information doit être exacte, précise, à jour et pertinente pour le besoin spécifique du système d'information. Le système d'information peut être de tout type (informatique > moteur de recherche, organique > cerveau, organisationnel > entreprise), il s'agit de différents éléments qui agissent les uns avec les autres. Son rôle est de collecter, stocker, traiter et diffuser l'information.

A savoir : Pour que naisse une information, il faut des données brutes dans un contexte. Ces données vont être interprété par un système d'information.

Partie 1 - La métamorphose

Les données n'ont pas d'apparence spécifique.
Par exemple, le chiffre 14 peut être noté : 2*7, "1"+"4", 1110 (binaire), 16 (octal), E (hexadécimal).
L'ajout d'une donnée notifiant du contexte peut influencer l'apparence.
Par exemple, 14h20 peut se noter : 860 minutes, 51600 secondes.

Simple ? Pour allez plus loin dans le concept, pensez à la flexibilité de la transformation.
On peut très bien joindre une apparence avec une autre par le biais d'un algorithme ou d'une formule mathématique.
Ex: Soit une fonction y=4x+5. Si on donne à notre interlocuteur la formule et la valeur Y, il peut retrouver X.

Alice veut envoyer 4 à Bob.
y = 4x+5 = 4*4+5 = 21
Bob reçoit le chiffre 21, il peut récupérer la donnée initiale.
x = (y-5)/4 = (21-5)/4 = 4

Ici, la résolution se produit par équation.

Dans vos années d'études, vous avez forcément entendu parlé de la théorie des ensembles (et des probabilités).
On distingue un ensemble A et un ensemble B. Deux ensembles qui ont la même taille de chaîne.
La chaîne est le nombre de possibilité qu'offre le système, par exemple en base 10 (numérique) : {0,1,2,3,4,5,6,7,8,9}
En base 2 (binaire) : {0,1}
En base 16 (hexadécimale) : {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}
On peut imaginer n'importe quel base et n'importe quel symbole, ex : {L,U,T,I,N}
Dans le cas de LUTIN, le chiffre 14 deviendra : TN.

0 L
1 U
2 T
3 I
4 N
5 UL
6 UU
7 UT
8 UI
9 UN
10 TL
11 TU
12 TT
13 TI
14 TN

Une fois la chaîne choisi (base + symbole), on peut déterminer notre fonction.
La fonction revient à notre petite équation de toute à l'heure, il s'agit d'un calcul mathématique qui va joindre X à Y.
Vous pouvez avoir un élément X (ensemble A) joint à un élément Y (ensemble B). Dans ce cas, la transformation fonctionne dans les deux sens.
A contrario, si l'élément X relie plusieurs éléments Y, on ne peut pas revenir sur nos pas.

ensemble.jpg

Dans certaine condition, il peut exister une seule image de Y pour plusieurs éléments de X.
Notamment pour catégoriser des données.
Ex: f({1,3,5,7})=0 (impaire), f({2,4,6})=1 (paire), f(x)=(x+1)%2 (x+1 modulo 2).

A savoir : les données peuvent changer d'apparence. A travers une table de conversion, une fonction mathématique, un algorithme. Vu d'un spectateur, la transformation demande une chaîne pour être identifiable. Les entités élémentaires qui composent une représentation (une donnée) doit être unique ({M,O,U,T,O,N} ne fonctionne pas, {M,O,U,T,N} fonctionne).

Partie 2 - L'ancrage des possibilités

J'aime le mot possibilité, c'est le mot parfait pour désigner les limites d'un système.
L'ancrage des possibilités dans la cryptographie symétrique revient à dire que tout élément de X n'est qu'une seule image de Y.
Ainsi le chiffre de César répond au problème :
MOTO (clef : 3) donne 13(M)+3=16(P) 15(O)+3=18(R) 20(T)+3=23(W) 18(R), PRWR.
M correspond à P, O correspond à R, T correspond à W.

Dans l'application réel de cette théorie, on utilise la fonction (magique ) modulo !
Le modulo est le reste d'une division euclidienne ; 5 modulo 2 = 1.
La formule mathématique équivalente est soit (5%2), soit (5-2*Entier(5/2)).
Quand j'indique entier, c'est la valeur entière du nombre. Par exemple 1.5 => 1; 14.54 => 14.

L'avantage de la fonction modulo est la limitation du nombre Y à son système N.

entier x, y, n;
n=60;
x=34;
y=( ( x + 145 ) % n);
afficher(y);

La sortie vaudra 59. Grâce au modulo, on ne sort pas de la chaîne (taille: 60).
Toutefois il existe un problème. Les multiplications, les divisions et les puissances une fois modulé ne permettent pas de revenir au point de départ.

Essayons de revenir à X :

entier x, y, n;
n=60;
y=59;
x=( ( y - 145 ) % n);
afficher(x);

La sortie vaudra bien 34.
Maintenant si on essaye avec les multiplications :

entier x, y, n;
n=20;
x=28;
y=( ( x * 3 ) % n);
x=( ( y / 3 ) % n);
afficher(y);
afficher(x);

La sortie Y vaudra 4, mais X vaudra 1. On ne peut donc pas utiliser les multiplications de cette façon.
Par contre, derrière le calcul on peut démultiplier la complexité du chiffrement symétrique.

A savoir : la fonction modulo permet de limiter le résultat de la fonction à la taille maximum de sa chaîne. Seul les multiplications et les divisions ne permettent pas de retrouver le résultat.

Partie 3 - les rouages de la sécurité

Si une transformation ne suffit pas pour chiffrer efficacement une suite de caractère, on peut en créer une pour chaque.
Pour coder "TONTON", on va devoir générer et calculer de façon temporelle la transformation.
La transformation se représente par E dans le calcul y=((x+e)%n).

entier i, x, y, e, c, clef, n;
string msg, resultat, chaine;

c = 1; // 1 = chiffrer, -1 = déchiffrer
clef = 540; // la clef de chiffrement
resultat = ""; // le résultat
msg = "TONTON"; // message à envoyer
chaine = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // la chaine de définition
n = taille(chaine); // la taille de la chaine

i=0;e=1;
tant que ( i < taille(msg) ) { // on boucle sur le message
    x = chaine.index( msg.char( i ) ); // char() permet de récupérer le caractère i du message et index() renvoi sa position dans la chaine
    e = ( ( e * clef ) % n); // on utilise la multiplication pour moduler la clef efficacement
    y = ( ( x + e * c ) % n); // ré-utilisation de la clef pour le chiffrement
    resultat = resultat + chaine.char( y ); // on renvoi le caractère de la chaine à Y
    i = i + 1; // on incrémente
}
afficher( resultat );

L'équivalent en python :

c=1
clef=540
resultat=""
msg="TONTON"
chaine="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
n=len(chaine)

i=0
e=1
while(i < len(msg)):
    x = chaine.index( msg[i] )
    e = ( ( e * clef ) % n )
    y = ( ( x + e * c ) % n)
    resultat += chaine[y]
    i=i+1
print( resultat )
input()

Le résultat est : NYFPMZ.
Avec ce système, vous avez la possibilité d'associer une lettre avec plusieurs autres sans jamais bloquer le déchiffrement.
Remplacez msg="TONTON" par msg="NYFPMZ" et c=1 par c=-1, miracle ça marche.

Après vous pouvez modifier la transformation E de différente manière.
Mais surtout ne jamais utiliser X ou Y pour créer E.
Pourquoi ? Parce que vous aurez des soucis pour deviner E au déchiffrement.

A savoir : le chiffrement et le déchiffrement sont équivalent en chiffrement symétrique. N'hésitez pas démultiplier votre valeur de transformation.

Conclusion

Je n'ai pas parlé de clef. Vous pouvez sans doute trouver une solution viable pour votre projet, afin qu'elle soit effective dans votre calcul.
A partir de maintenant rien de vous bloque pour commencer à chiffrer vos données.
Expérimentez et si vous avez des questions n'hésitez pas, je suis là !

Merci d'avoir lu mon tutoriel.

[FRKorisS]

Très bon tuto !

Je suis par contre resté buté sur l'exemple avec la base 5 {L,U,T,I,N} -> L:0 U:1 T:2 I:3 N:4
n'est-ce pas ?

Tu dis que 14 reviendrai à écrire UN -> U:1 et N:4

Et justement, c'est là que ça ne me convient pas ^^. Pour moi, 14 serait égale à TN puisque ce sont des modulos. Je m'explique :

L:0 U:1 T:2 I:3 N:4 UL:5 UU:6 UT:7 UI:8 UN:9 TL:10 TU:11 TT:12 TI:13 TN:14

Car comment aurais-tu fais pour écrire le nombre 61 par exemple, dans ton cas, ça n'aurait pas fonctionné.
C'est comme si tu disais que 14, en hexa est égale à 14, non c'est égale à E.

J'espère m'être compris et ne pas m'être trompé, sinon bon explication !

[Yarflam]

Très bon tuto !

Je suis par contre resté buté sur l'exemple avec la base 5 {L,U,T,I,N} -> L:0 U:1 T:2 I:3 N:4
n'est-ce pas ?

Tu dis que 14 reviendrai à écrire UN -> U:1 et N:4

Et justement, c'est là que ça ne me convient pas ^^. Pour moi, 14 serait égale à TN puisque ce sont des modulos. Je m'explique :

L:0 U:1 T:2 I:3 N:4 UL:5 UU:6 UT:7 UI:8 UN:9 TL:10 TU:11 TT:12 TI:13 TN:14

Car comment aurais-tu fais pour écrire le nombre 61 par exemple, dans ton cas, ça n'aurait pas fonctionné.
C'est comme si tu disais que 14, en hexa est égale à 14, non c'est égale à E.

J'espère m'être compris et ne pas m'être trompé, sinon bon explication !

Tu as raison, je me suis planté. J'ai oublié que L valait 0.
Rectification apporté au sujet.

Merci !