-
Notifications
You must be signed in to change notification settings - Fork 16
/
algos_classiques.theory.txt
179 lines (171 loc) · 11.7 KB
/
algos_classiques.theory.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
ALGOS CLASSIQUES
Soit :
- E() le chiffrement
- D() le déchiffrement
- E(x) : chaque unit du ciphertext
- E(w) : unit précédente du ciphertext
- X : plaintext
- x : chaque unit du plaintext / valeur minimale chiffrée (bit/octet/lettre/block)
- w : précédente unit du plaintext
- K : clef
- k : chaque unit de la clef
- AB : taille de "l'alphabet" de l'unit
Transposition : écrit un texte sur une grille dans un certain sens, et le lit dans un autre. Applique en fait une permutation
sur l'ensemble du plaintext. Can do padding (random letters, i.e. "nulls") to fit plaintext to block size.
- disrupted transposition : pratique de rajouter des blanks dans le plaintext, pour compliquer cryptanalyse.
- columnar transposition : écrit le plaintext horizontalement sur une grille, et lit verticalement. Le nombre de colonnes == taille du keyword, et ordre de lecture des colonnes est l'ordre alphabétique du keyword.
- myszkowski transposition : comme columnar transposition, mais keyword doit contenir des lettres récurrentes : lors de la lecture des colonnes, les colonnes de ces lettres récurrentes sont lues ligne par ligne et non colonne par colonne.
- double transposition : 2 columnar transpositions avec la même clef ou non (superencryption)
- route cipher : sur une grille. Sens d'écriture et de lecture dépend de la clef qui spécifie le chemin (en escargot, en diagonale, etc.). Si mauvaise clef, peut laisser ciphertext proche du plaintext (par exemple juste inversé).
- rail fence / zigzag cipher : écrit en diagonale sur une grille, puis lecture ligne par ligne. La seule clef est le nombre de lignes de la grille (crackable à la main). Exemple :
1 5
2 4 6
3 7
- écrire à l'envers : écrire à l'envers les mots, phrases ou tout.
Substitution : applique E(x), function bijective. Domain and codomains are called "alphabet" and "substitution alphabet"
(peuvent etre différent). n! clefs possibles, où n est la taille de l'alphabet.
- simple substitution : l'unité est une lettre
- monoalphabétic simple substitution : monoalphabétic signifie qu'on utilise qu'une seule clef.
- Affine cipher :
- E(x) = (a.x + b) % AB, où a et b sont les clefs (constantes).
- D(x) = c (x - b) % AB, où c est le modular multiplicative inverse de a % AB (donc 1 == (a.c) % AB)
- Chiffrement de César :
- rotation alphabétique, où a == 1, et b est la clef.
- rot13 :
- clef est 13
- Atbash cipher :
- où a et b == AB - 1 (utilise la lettre opposée dans l'alphabet)
- Pigpen cipher :
- suite graphique de # et de X, avec ou non des ., où chaque case contient une lettre associée aux lignes qui l'entourent.
- Variantes : #X#X, , ou XX (que voici) :
A |B | C A |B | C \ S / \ W /
| | .|. |. \ / \./
--+--+-- --+--+-- T X U X .X. Y
D |E | F D |E | F / \ /.\
| | .|. |. / V \ / Z \
--+--+-- --+--+--
| | .|. |. Ce qui donne : _|, |_|, |_, etc., \/, >, <, etc. pour A, B, C, etc., S, T, U, etc.
G |H | I G |H | I
- dvorak encoding : taper texte QWERTY avec clavier DVORAK
- polyalphabétic simple substitution : polyalphabétic signifie qu'on utilise plusieurs clefs, alternativement à chaque unité ou groupe d'unités. Il faut donc non seulement deviner les clefs, mais aussi la raison pour laquelle les clefs changent.
- avec autokey cipher :
- text-autokey cipher :
- Trithemius cipher :
- E(x) = ( x + E(w) - 1 ) % AB
- Utilise une tabula recta pour cela.
- Alberti cipher :
- E(x) = ( x + k - 1 ) % AB
- La clef est la dernière lettre majuscule du texte. Mettre une majuscule modifie donc la clef.
- Utilise deux disques concentriques pour cela.
- L'alphabet contient dans les faits 4 nulls en plus des 26 lettres
- sans autokey cipher :
- Vigénère cipher, "le chiffre indéchiffrable" :
- E(x) == ( x + k - 1 ) % AB
- La clef est un mot répété indéfiniment.
- un peu comme un stream cipher, mais un mot répété indéfiniment
- Problème : répétition de la clef, donc patterns.
- Utilise une tabula recta.
- running key cipher :
- comme Vigénère cipher, mais la clef est ici une partie de livre.
- Le livre est transmis avant la communication, et le premier mot de départ pour le ciphertext courant est envoyé avec le ciphertext, à un endroit fixe du ciphertext, selon une grammaire qui le fait ressembler au reste du ciphertext.
- permutation generated running key cipher :
- variante où la clef est un ensemble de livres xor'd
- polygraphic substitution : l'unité est un ensemble de lettre (parfois variable). Par conséquent, une unité en ciphertext == plusieurs unités en plaintext (ou inverse), ce qui augmente la fractionation et donc la diffusion. Peut être digraphic, trigaphic, etc. cipher, en fonction du nombre d'unités.
- monoalphabetic polygraphic susbstitution (cf ci-dessus) :
- nomenclators :
- utilise une table, avec toutes les mots, groupes de lettres et lettres les plus courantes du plaintext, et leur équivalent chiffré.
- Les tables sont souvent très grandes.
- book cipher :
- nomenclator où la table est un livre, et le ciphertext représente la position, depuis le début du livre, des mots en plaintext.
- Ainsi, pas besoin de distribuer de clef dans un canal sécurisé.
- Polybius's square :
- grille de 5 x 5 de A à Z (I et J sont la même lettre) en écriture, et on lit les coordonnées horizontales puis verticales (2 chiffres de 1 à 5).
- Permet fractionation (digraphes).
- Variations :
- au Japon avec des hiraganas
- 12345 peut être une suite de symboles
- avec un mixed alphabet
- parfois commence par un keyword (comme keyword cipher).
- Playfair cipher :
- grille 5 x 5, remplis par le keyword, puis par les lettres restantes de l'alphabet (sauf Q).
- Chiffrer :
- mettre un 'X' entre chaque lettre doublon, et à la fin du message si taille est impaire
- pour chaque digraphe ab, de coordonnées (ax,ay) et (bx,by), produit un digraphes cd, tel que :
- c = (bx,ay) et d = (ax,by), sauf si :
- ax == bx, alors cx = ax et cy = ( ay + 1 ) % 5
- ay == by, alors cy = ay et cx = ( ax + 1 ) % 5
- Déchiffrer :
- pareil, mais ne met pas de X, mais les supprime à la fin
- pas ay ou ax + 1, mais - 1
- Four-square cipher :
- utilise quatre tables 5 x 5.
- Deux opposées ont un keyword + lettres restantes, les deux autres sont simplement de A à Z.
- Un digraphe sur les deux dernières se chiffre avec les lettres dans la même ligne et colonne sur les deux autres tables.
- Two-square cipher / Double playfair :
- comme Four-square cipher, mais avec que deux tables.
- nihilist cipher :
- d'abord polybius's square sur plaintext, puis sur la clef (répétée pour avoir même taille que plaintext)
- somme des deux
- VIC cipher :
- comme nihilist cipher, sauf que :
- straddling checkerboard et non Polybius's square
- clef tirée d'un livre
- addition sont chiffre par chiffre, et non nombre par nombre, puis % 10
- à la fin, ajout d'un straddling checkerboard inversé (un peu comme le bifid cipher)
- Tapcode :
- comme Polybius's square, mais c'est ici le K qui est absent
- straddling checkerboard :
- comme Polybius's square, sauf que :
- rectangle, non carré
- symboles horizontales différents de verticaux
- premier symbole horizontal est vide : premier rang ayant les lettres les plus courantes, cela permet une légère compression
- le . et le / sont utilisés pour indiquer le début d'une suite numérique
+---------------------+
| 0 1 2 3 4 5 6 7 8 9 |
+-+---------------------+
| | E T A O N R I S |
|2| B C D F G H J K L M |
|6| P Q / U V W X Y Z . |
+-+---------------------+
- Hill cipher :
- plaintext devient un vecteur de taille n (== taille du plaintext), où A = 0 .. Z = 25.
- le vecteur est multiplié par une matrice de dimension [n,n], remplie avec des nombres aléatoires de 0 à 25. La matrice doit avoir un inverse, pour pouvoir déchiffrer.
- le résultat a un % 26
- polyalphabetic polygraphic susbstitution (cf ci-dessus)
Combinaison de susbstitution + transposition :
- ADFGVX :
- d'abord Polybius's square 6 x 6 (A..Z0..9), avec ADFGVX à la place de 123456, et avec un mixed alphabet.
- puis columnar transposition.
- bifid cipher :
- d'abord polybius's square avec mixed alphabet
- puis columnar transposition, avec hauteur de 2
- puis polybius's square inversé (lettre à partir de deux chiffres)
- trifid cipher :
- comme bifid cipher, sauf que polybius's square est cette fois un cube 3x3x3
- reservehandverfahren :
- d'abord columnar transposition
- puis polygraphic (bigraphic) substitution, via tables
Grille :
- cadre avec des trous pour lecture d'un ciphertext laissant apparaître dans les trous (lettres ou mots) le plaintext.
Autres :
- One-time pad (OTP) :
- stream cipher dont keystream est aléatoire, et que l'on transmet (PSK) en entier
- peut utiliser un alphabet et non être binaire
- peut presque être fait sans ordinateur (cependant aléatoirité sera faible)
- perfect secrecy. Cependant, il faut :
- que la clef soit vraiment random (et non pseudo-aléatoire)
- clef doit être transmise dans channel secure.
- clef, ou partie de la clef, ne doit être utilisé qu'une seule fois (sinon apparition de patterns possible)
- par conséquent, doit être de taille >= plaintext
- Problèmes :
- taille de la clef
- requirements forts
- quasiment impossible à implémenter sans failles
- pas de ckeck d'entity authentication, message authentication ni intégrité
Notes :
- Après algo de crypto classique, on regroupe souvent le ciphertext en groupe de 5 x (ou autres), après avoir enlever la ponctuation.
- Tabula recta : grille de 26 x 26 lettres (A à Z horizontalement et verticalement), chaque case == ( coordonnées X + Y ) % 26
- Un xor peut être considéré comme proche d'une substitution.
- book ciphers et livres utilisés comme clef : KGB conseille d'utiliser des almanachs, contenant des statistiques (meilleure entropie)