Si un ordinateur essaie de craquer un mot de passe à 4 chiffres par force brute, sans répéter une entrée, sur quelle tentative l’ordinateur a-t-il le plus de chances de craquer le code (en termes de probabilité mathématique) ?


Si tous les chiffres du mot de passe sont choisis de manière indépendante et ad aléatoire, que vous dit votre intuition ? Il y a [math]10^4[/math] mots de passe possibles (en supposant que vous voulez parler des chiffres de 0 à 9).

Cependant, si les gens conçoivent leurs propres mots de passe, la réponse est tout à fait différente. Un anniversaire peut-être ?


Simplifions le problème :

Un homme rentre chez lui ivre. (Ou femme si vous préférez, je ne'veux pas vous offenser). (S)il a un jeu de 4 clés, mais n'a plus aucune idée de la clé qui ouvre la porte. Il décide donc de les essayer au hasard. Mais (s)il'est assez intelligent pour jeter la clé si elle'ne correspond pas à la porte.

[math]Souligner{k}[/math] Nombre de clés à essayer

Le résultat pourrait être un peu surprenant :

[math]N{i1}Début{i}{i1}c|c|}N{i1}Ligne k & text{i}P}(underline{k}=k) & k cdot text{i}P}(iunderline{k}=k)N{i1}. 1 & 1/4 & 1/4\ hline 2 & 3/4cdot 1/3=1/4 & 2/4\ hline 3 & 3/4 cdot 2/3 cdot 1/2=1/4 & 3/4\hline 4 & 3/4 cdot 2/3 cdot 1/2 cdot 1=1/4 & 4/4\\hline text{total} & 1 & 10/4\hline end{array}[/math]

Cela nous dit que la probabilité qu'un ouvre avec succès la porte à l'essai [math]k[/math] est indépendante de [math]k[/math] et est fixée : [math]1/4[/math].

Chaque clé ouvre la porte avec la même probabilité ; c'est une instance de la distribution uniforme discrète.

Ou pour le dire autrement : on ne peut pas maximiser la probabilité de succès, chaque valeur de [math]k[/math] a la même probabilité. La réponse serait : pas de tentative particulière.

On peut calculer le nombre attendu d'essais. Dans ce cas, il s'agit simplement du nombre moyen d'essais : [math](4+1)/2=2.5[/math]. Donc, en moyenne, la clé 2 ou 3 fera l'affaire.

En prolongeant le tableau avec une colonne supplémentaire, [math]k^2text{P}(underline{k}=k)[/math], on aurait la possibilité de calculer [math]text{E}(k^2)[/math], le second moment de [math]k[/math].

On a :

[math]text{var}(underline{k})=text{E}(underline{k}^2)-left(text{E}(underline{k})right)^2[/math]

Ce qui donnerait (essayez..):

[math]text{var}(underline{k})=7.5 - 2.5^2=1.25[/math]

ou

[math]sigma(underline{k})=sqrt{1.25} approximativement 1,12 [/math]

Supposons maintenant que notre ivrogne a peur de jeter (ses) clés, après tout (s)il'est ivre et essayer de faire entrer une clé dans la serrure est déjà assez difficile. (Je parle par expérience ici). Supposons que (s)il a également des difficultés à se souvenir de la clé qu'(s)il a déjà essayée, alors (s)il'dessine avec remplacement.

Qu'est-ce que notre tableau ressemble maintenant :

[math]Ndébut{array}{|c|c|} Nligne k & text{P}(underline{k}=k) & k cdot text{P}(underline{k}=k)Nligne 1 & 1/4 & 1/4\\ hline 2 & 1/4 & 2/4\\hline 3 & 1/4 & 3/4\\hline 4 & 1/4 & 4/4\\hline 5 & 1/4 & 5/4\\hline .. & .. & ..\\ hline text{total} & text{??} & text{??}\hline end{array}[/math]

La probabilité de succès est toujours fixée à [math]1/4[/math]. Mais le nombre d'essais n'est pas du tout fixé. Le nombre d'essais attendu est de [math]infty[/math].

Si l'on pirate sa propre porte, mieux vaut jeter les clés !

.