Exercice 2 — Clés binaires

Sujet

La simulation de nombres aléatoires est un enjeu fondamental de la recherche scientifique et notamment informatique. Une question importante se pose alors : étant donnée une série de nombres, comment vérifier que celle-ci est aléatoire, c'est-à-dire que chacun des nombres qui la composent a été choisi au hasard ? Un ordinateur fonctionne avec des bits qui ne peuvent prendre que deux valeurs 0 et 1 . Ainsi si l'on souhaite générer un nombre aléatoire, il faut renvoyer soit 0 , soit 1 , chacun avec une probabilité de 0,5 .

Partie A - Préliminaires

1. Combien de clés de 91 bits (c'est-à-dire de suites de 91 chiffres tous égaux à 0 ou à 1) existe-t-il ?
2. On considère l'algorithme ci-contre dans lequel la notation cle \([k]\) désigne le \(k\) ième élément de la liste cle. Que contient la variable \(c\) à la fin de l'exécution de cet algorithme ?

\(c \leftarrow 0\)
Pour kallant de 1à 91 :
Si cle \([k]=1\) alors
\(c \leftarrow c+1\)
Fin Si
Fin Pour

Partie B - Une clé donnée est-elle aléatoire ?

Dans cette partie, on suppose qu'on dispose d'un logiciel de cryptographie capable de générer une clé de 91 bits de manière aléatoire pour protéger des données personnelles. Aline a utilisé ce logiciel mais elle ne se rappelle plus de sa clé. Elle appelle le Service Après-Vente et tombe sur Boris. Ce dernier, un brin facétieux, lui en donne quatre et lui demande de retrouver la bonne (une seule a été générée de manière aléatoire par le logiciel, les trois autres ont été inventées par Boris).
Clé 1: 1100110011001100110011001100110011001100110011001100110011001100
110011001100110011001100110
Clé 2: 1101100101111010100101110101100001111100111001000110000000001011
010001001010001011100000000
Clé 3 : 1101101010011011011101011100100010110100101110010110011000101101
010101010010010011001010010
Clé 4: 1010010111010001101111101111011100101101000011100111110111000010
111000111111011111011111011
3. Aline décide de relever le défi de Boris et élimine immédiatement une des quatre clés. Selon vous laquelle et pourquoi ?
4. Ne parvenant pas, sur des critères simples et logiques, à en éliminer une autre, elle décide de faire appel à ses connaissances mathématiques pour trouver la bonne clé de manière rigoureuse.
a. Elle s'intéresse, pour chacune des trois clés restantes, au nombre de bits qui valent 1. Elle parvient alors à en éliminer une deuxième. Laquelle et pourquoi ?
b. Pour départager les deux clés restantes, Aline s'intéresse alors, pour chacune des deux clés, au nombre de bits différents du précédent. Cela lui permet d'éliminer une troisième clé (et donc de trouver celle qu'elle pense être la bonne). Laquelle et pourquoi ?
5. Après avoir crié victoire, elle réalise que la première clé qu'elle avait éliminée résiste aux deux tests de la question précédente. Elle trouve alors un troisième test permettant de l'éliminer (test réussi par la bonne clé). Quel pourrait être, à votre avis, un tel test ?
6. Proposer un algorithme qui effectue le test de la question 2. b), c'est-à-dire qui, lorsqu'on lui rentre une clé de 91 bits, calcule le nombre de bits différents du précédent. On pourra s'inspirer, pour les instructions, de l'algorithme donné en préliminaires.