|
|
| Fonctions de base |
La cryptographie fait appel à l'algèbre linéaire, la théorie des groupes, la théorie de la complexité, la théorie combinatoire et la théorie des graphes.
Différentes fonctions mathématiques de base sont importantes pour comprendre en détail les algorithmes de chiffrement.
Fonction un-à-un (1 - 1)
Une fonction un-à-un est une fonction où chacun des éléments du codomaine est l'image d'un seul élément du domaine.
Fonction à sens unique (One-way function)
F(x) = y
Facile de trouver y à partir de x, mais impossible de trouver x à partir de y. Il n'a jamais été prouvé que ce genre de fonction existe (remplacer "impossible" par "difficile" dans l'énoncé précédent). La facilité peut être vue comme étant un compromis entre la puissance de calcul et le temps.
Fonction à sens unique avec brèches secrètes (Trapdoor one-way function)
F(x) = y
Facile de trouver y à partir de x mais difficile de trouver x à partir de y sauf si on connaît une information supplémentaire.
Exemple
Factorisation, p * q = n, p et q sont des nombres premiers très grands, mais nous savons qu'ils ont une longueur de dix décimales. Sans cette information, il est très difficile de retrouver p et q à partir de n. C'est le problème bien connu de la factorisation des nombres entiers, qui est la source de plusieurs fonctions à sens unique avec brèche secrète. |
Les fonctions à sens unique avec ou sans brèche secrète sont à la base des systèmes cryptographiques à clé publique. Pour ce type de système, la clé privée est la brèche secrète.
Permutation
La permutation est une fonction un-à-un bijective où les éléments du domaine et du codomaine appartiennent au même ensemble.
Exemple
Ensemble = { 1,2,3,4,5 }
p(1) = 3
p(2) = 5
p(3) = 4
p(4) = 2
p(5) = 1 |
Exemple
X = { 1,2,3,4,...,pq-1 }, où p et q sont de très grands nombres premiers et où p-1 et q-1 ne sont pas divisibles par 3.
P(x) = x3 MOD pq
Trouver la permutation inverse de cette fonction est impossible avec le pouvoir des ordinateurs d'aujourd'hui.
|
Involution
Une involution à la propriété d'équivaloir son inverse :
F = f-1 (f(f(x)) = x)
Une bijection d'un ensemble E sur lui-même égale sa bijection réciproque.
Opérateur binaire OU exclusif (XOR)
Fondamental dans la mathématique booléenne et très utilisé dans les algorithmes de chiffrement symétriques, l'opération logique OU-Exclusif retourne "1" seulement si les deux bits sont différents.
L'algorithme utilisant seulement le OU-Exclusif est appelé "chiffrement de Vigenere".
Table de vérité
| Bit 1 |
Bit 2 |
Résultat |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
0 |
Propriétés importantes
A XOR A = 0
A XOR B = C => C XOR B = A
A XOR B XOR B = A
| Symbole |
 |
Le décalage binaire
Chaque caractère pouvant être représenté par un octet de huit bits, il suffit simplement de décaler les bits vers la droite ou vers la gauche.
|
 |
|
|
|
|
