Exercices
de Cryptanalyse
Master Sécurité
des Systèmes d'Information
janvier 2006
L' évaluation des étudiants sera
fonction du nombre d'exercices résolus, de la méthode utilisée, et de la rapidité d'exécution. Envoyez moi vos solutions
par email ou sur papier libre au fur et à mesure de votre progression dans la résolution
de ces exercices. Les réponses sous forme de programme en langage
C, script shell bash, ou encore de fichier tex ou latex, etc.. devront être fournies
au format nom-exo.tar contenant au
minimum un makefile, et un fichier d'explications. Les réponses
sous forme de fichiers à lire directement (sans compilation, ni commande)
devront être au format nom-exo.{
txt, ps, pdf,
rtf }. Les formats manuscrits directement dans ma boîte aux
lettres sont les bien venus ! Vous l'avez compris, j'attend des réponses
diverses et variées, pas la solution unique d'un groupe d'étudiants.
[ 1 ] Corrélations.
La table ci-dessous rapporte les résultats du premier tirage du 14
decembre dernier. Estimez le nombres de grilles jouées.
Estimez le chiffre d'affaire de la Francaise des jeux sur ce tirage.
|
1er
tirage dans l'ordre de sortie |
:
| |
Nombre de
grilles gagnantes |
Rapport par
grille
gagnante pour 0,3 € |
| 6 bons numéros |
4 |
211 849,00 € |
| 5 bons numéros + complémentaire |
22 |
4 010,20 € |
| 5 bons numéros |
613 |
498,50 € |
| 4 bons numéros + complémentaire |
2 021 |
23,80 € |
| 4 bons numéros |
29 619 |
11,90 € |
| 3 bons numéros + complémentaire |
47 818 |
3,00 € |
| 3 bons numéros |
450 324 |
1,50 € |
[ 2 ] Registre à décalage.
(a) Implantez une fonction en langage C uint
lfsr( uint r, uint g, uint L) qui retourne l'état
qui suit celui de r aprés une
rétroaction de polynôme g de
degré L i.e. la largeur du
registre à décalage. Votre fonction doit fonctioner pour 1 < L
< 32 .
(b) Donnez une implantation optimale lfsr32 dans le cas L=32. Déterminer
un polynome g0 de retroaction de
periode 2^32 - 1.
Complétez puis mesurez le temps de calcul du programme :
uint lfsr32( unit r, uint g )
{ ... }
int main( void )
{
uint reg = 1;
uint g = g0;
do reg = lfsr32( reg, g) ;
while ( reg != 1);
return 0;
}
(c) Donnez une implantation llfsr dans le cas 32 < L < 64.
Déterminer un polynome g0
de retroaction de periode 2^62 - 1.
Faire un programme pour démontrer que la période est effectivement 2^62 - 1 ! (indication : Mersenne).
Estimez le temps de calcul d'un programme analogue au précédent
mais sur 64 bits.
(d) On dit qu'une suite sn est ultimement
periodique s'il existe un rang no à partir duquel la suite devient
périodique. On peut classer les polyômes de rétroaction
en deux classes. La classe P composée des polynômes qui ne génèrent
que des suites périodiques, et la classe U composée de
ceux qui génèrent au moins une suite ultimement périodique
non périodique. Trouvez une condition nécessaire et suffisante
pour qu'un polynôme de rétrocation soit dans la classe P.
[ 3 ] Attaque "DPA".
Le programme
rsa.exe
chiffre ou déchiffre un entier écrit en base 16 passé
par la ligne de commande par la méthode RSA. Il prend en entrée
un caractère dans {C, D}, puis un nombre
z en base
16. Si le premier argument vaut
C alors il calcule
z^d modulo un entier rsa
N, sinon il calcule
z^c, la tranformation
inverse.
Par exemple,
le résultat de :
$ ./rsa.exe
C da206c0de
est
crypto:1d9f50386d606a5abd090084b9a710f9ee131a8de5da94e6e3cc
7662fb3e0eaa59160ee8da8ae8baae539c480463ea90ccfc94af16110f97780
4d03af4ce1befef4e10175902d363237e33b59caff92e28d13bda6ca48e024d
9cddfab46786917cf79e1ec
et celui de
$ ./rsa.exe D 1d9f50386d606a5abd090084b9a710f9ee131a8de5da94e6e
3cc7662fb3e0eaa59160ee8da8ae8baae539c480463ea90ccfc94af16110f97
7804d03af4ce1befef4e10175902d363237e33b59caff92e28d13bda6ca48e
024d9cddfab46786917cf79e1ec
est
crypto:da206c0de
Le programme
a été écrit par un amateur : déterminez les clés
de chiffrements, le module rsa
N utilisé,
ainsi que la décomposition de
N en produit de
deux facteurs premiers.
Indication, le mangeur
de pizza qui a fait ce programme n'a pas manqué de maladresse en utilisant
la librairie de calcul multiprecision
gmp...
[ 4 ] Attaque par "faute".
Le programme
crt.exe a été écrit
par un autre amateur de pizzas. Il prend sur la ligne de commande un entier
un caractère C ou D et un entiers de 56 bits au plus, puis cacule
un cryptogramme modulo
n = pq ou
p et
q sont deux nombres
premiers de 28 bits. L'auteur qui a décidé de ne pas trop se
creuser la tête a décider d'utiliser le théorème
des reste chinois pour remplacer une opération modulaires
sur 56 bits par deux opérations modulaires sur 28 bits.
z1 * z2 mod n - - - >
(x1 , y1) * (x2 , y2) - - - >(x1* x2 , y1* y2)
Typiquement, pour faire le calcul
x*y mod
p (ou x, y et p
sont sur 28 bits), il suffit de faire une multiplication dans le domaine
56 bits puis de réduire :
long long aux;
aux = x; aux *=y; aux = reduire(aux, p)
Je vous propose trois méthodes pour déterminer
p et q :
( a ) Un simple parcours du code, devrait vous permettre de faire appaitre
p et q. Non ?
( b ) Vous n'aurez pas de difficulté à trouver le module
utilisé, en exécutant le programme plusieurs fois.
Une factorisation vous permettra de déterminer les premiers p et q.
( c ) Enfin,
le plus simple,
et le plus rapide est de faire une attaque par faute ! Indication : pour
faire une faute, il suffit de changer la valeur d'un registre en cours d'exécution,
pour vous éviter un déssassemblage mental, je vous donne une
première piste
crt.s
[ 5 ] Chiffrement à flot.
Ecrire une commande stream [-p] [-k key]
[-r retro] [-i input] [-o ouput] pour chiffrer le fichier input dans le fichier output au moyen d'un registre à
décalage linéaire de 16 bits de rétroaction retro initialisé par la clef key . La commande doit s'appliquer à
des fichiers de caractère, elle ne chiffrera pas le bit de poids fort.
-p probabilite : calcule la probabilite d'avoir 1 sur le fichier source,
pas de chiffrement.
-k cle d'initialisation par défaut égale à 0, chiffrement
si k > 0.
-r retroaction : polynome de retroaction.
-i fichier à chiffrer.
-o fichier se sortie.
[ 6 ] Attaque de Siegenthaler.
Le fichier crypto.txt a été
obtenu par un chiffrement de tous les bits d'un texte clair non aléatoire
( la probabilité d'un bit égal à un dans le texte clair
est moindre que 0.4 ). Vous pouvez consulter un extrait de la source qui a été utilisée
pour implanter le chiffrement à flot. Le système de chiffrement
à flot utilisé pour le cryptage est décrit par la figure
ci-dessous :
Les trois registres à décalages de longueurs 16 bits sont
fondés sur le même polynôme de rétroaction.
Dans chaque registre, à chaque top d'horloge, la somme des bits
0, 2, 3 et 5 rentre à gauche et, les bits de poids faibles sortent
à droite pour alimenter une fonction de combinaisons composée
de deux portes logique &,
d'un additionneur binaire (sans retenue) et d'une diode de négation.
- Les registres R1 et R3 sont attaquables par corrélation.
Pourquoi ?
- Ecrire un programme pour déterminer les clés probablement
utilisées pour initialiser les registres R1 et R3.
- Déterminer les 3 clés de 16 bits, ou encore 4 chiffres
hexadécimaux.
- Retrouver le texte clair.
Philippe Langevin, Janvier 2006
