Deviner le code d’un interphone grâce aux suites de De Bruijn

Mathématique Par la communauté 27 mai 2017

Deviner le code d’un interphone grâce aux suites de De Bruijn

Quand je me balade à Lyon, je rêve de pouvoir ouvrir les portes de tous les immeubles. Ça peut paraître un peu con, mais j’adore visiter des halls d’entrée, découvrir des architectures. Une belle porte fermée, c’est comme une gourmandise inaccessible, je veux entrer et explorer.

Malheureusement, toutes les portes sont verrouillées par un digicode. Alors en googlant un peu, j’ai découvert 3 méthodes pour ouvrir des portes à code.

La moins légale : le pass universel

Posséder un pass Vigik. Les ouvriers EDF, les pompiers, les facteurs en ont un. Ils peuvent ouvrir une bonne partie des portes sans problème. Il y a quelques années, il était facile d’acheter un pass Vigik au marché noir ou sur le Dark Web.

Aujourd’hui, ces pass sont jetables, temporaires ou désactivables à distance, alors ça devient plus compliqué. Tant mieux d’un côté 🙂

Le petit boitier Vigik noir, en bas

 

La plus “James Bond” : l’analyse des touches

Soit vous mettez un peu de farine sur un digicode, vous soufflez pour l’estomper, et vous attendez que quelqu’un passe en tapant son code. Les touches sans farine sont celles des chiffres du code. Ouais, je sais, il faut de la farine.

Sinon, vous observez attentivement les touches du digicode. Vous pourriez y trouver des traces de crasses sur les touches fréquemment appuyées, ou des traces d’usure ENTRE les touches fréquemment appuyées (parce qu’on glisse nos doigts d’une touche à l’autre quand elles sont proches). J’essaie souvent cette méthode, mais sans succès pour l’instant.

La plus mathématique : la suite de De Bruijn

Quand rien ne marche, que la vie est une chienne, que tout fout le camp, heureusement, il reste les maths. Et la pizza.

J’ai donc raisonné autrement : puisque les digicodes me résistent, de combien de temps aurais-je besoin pour essayer toutes les combinaisons sur le clavier ? En partant du principe que le code que je recherche est composé de 4 chiffres, je devrais taper :

  • 0000
  • 0001
  • 0002
  • 9999

À un rythme de 1 code toutes les 2 secondes, il me faudrait environ 13 heures pour tout essayer. Hum… C’est bête, parce que dès les 2 premières tentatives, je perds un temps précieux. Je m’explique.

En essayant chaque combinaison bêtement, je tape 0000, puis 0001. Au final, en tapant seulement 00001, j’essaie bien ces deux premières combinaisons, mais en tapant sur 3 touches de moins.

Et si j’arrivais à trouver la combinaison de touches parfaite, pour essayer TOUS les nombres de 0000 à 9999, en un temps minimal ?

La suite de De Bruijn à la rescousse !

Né en 1918 et mort en 2012 (gg dude), Nicolaas Govert de Bruijn est un célèbre mathématicien. Il a beaucoup travaillé sur des problèmes de maths évidemment (théorie des graphes et assistance de preuves entre autres), mais aussi en neurologie.

Konrad Jacobs, Erlangen, Copyright is MFO
Mathematisches Forschungsinstitut Oberwolfach

Il est célèbre pour avoir théorisé les suites de De Bruijn. En langage mathématique, Wikipédia les définit comme suit :

Une suite de de Bruijn d’ordre n sur k symboles est un mot circulaire sur un alphabet A à k symboles qui contient toutes les suites de longueur n sur A une et une seule fois

Parlons plus simplement. Une suite de De Bruijn permet d’obtenir une suite de toutes les combinaisons possibles d’une série de chiffres, sans répéter 2 fois la même combinaison. C’est ce que je vous montrais toute à l’heure :

– Si je tape 0000, puis 0001 : je tape 2 combinaisons distinctes sur mon digicode. Ça marche, mais ce n’est pas optimal.

– Si je tape 00001 : je ne tape plus qu’une combinaison, qui contient les deux précédentes, sans répétition. Voila déjà une mini-suite de De Bruijn.

Reprenons la définition mathématique, pour ceux que ça intéresse

– Un alphabet (A), composé de (k) symboles. C’est à dire les symboles que nous voulons manipuler. Dans le cadre d’un digicode, l’alphabet à utiliser est l’ensemble des chiffres de 0 à 9 (A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, k = 10).

– Un ordre (n). C’est à dire la taille des combinaisons que l’on veut assembler avec notre alphabet. Les digicodes se composent généralement de 4 chiffres, donc l’ordre n=4.

En appliquant ensuite un algorithme de construction bien précis à vos paramètres de départ, vous obtiendrez une suite de combinaisons optimale.

Concrètement, en quoi ça m’aide à ouvrir une porte ?

Sans utiliser de suite de De Bruijn, en essayant toutes les combinaisons de votre digicode à 4 chiffres, vous allez devoir taper sur potentiellement 39 996 touches.

En optimisant votre recherche avec une suite de De Bruijn, vous n’aurez plus que k^n touches à taper dans le pire des cas (c’est à dire 9999, puisque c’est le dernier code qu’on essaie). Au final, vous taperez seulement sur 10^4 = 10000 touches. C’est 4 fois moins de travail !

Voila la série de chiffres à taper sur n’importe quel digicode pour ouvrir la porte :

0 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 7 0 0 0 8 0 0 0 9 0 0 1 1 0 0 1 2 0 0 1 3 0 0 1 4 0 0 1 5 0 0 1 6 0 0 1 7 0 0 1 8 0 0 1 9 0 0 2 1 0 0 2 2 0 0 2 3 0 0 2 4 0 0 2 5 0 0 2 6 0 0 2 7 0 0 2 8 0 0 2 9 0 0 3 1 0 0 3 2 0 0 3 3 0 0 3 4 0 0 3 5 0 0 3 6 0 0 3 7 0 0 3 8 0 0 3 9 0 0 4 1 0 0 4 2 0 0 4 3 0 0 4 4 0 0 4 5 0 0 4 6 0 0 4 7 0 0 4 8 0 0 4 9 0 0 5 1 0 0 5 2 0 0 5 3 0 0 5 4 0 0 5 5 0 0 5 6 0 0 5 7 0 0 5 8 0 0 5 9 0 0 6 1 0 0 6 2 0 0 6 3 0 0 6 4 0 0 6 5 0 0 6 6 0 0 6 7 0 0 6 8 0 0 6 9 0 0 7 1 0 0 7 2 0 0 7 3 0 0 7 4 0 0 7 5 0 0 7 6 0 0 7 7 0 0 7 8 0 0 7 9 0 0 8 1 0 0 8 2 0 0 8 3 0 0 8 4 0 0 8 5 0 0 8 6 0 0 8 7 0 0 8 8 0 0 8 9 0 0 9 1 0 0 9 2 0 0 9 3 0 0 9 4 0 0 9 5 0 0 9 6 0 0 9 7 0 0 9 8 0 0 9 9 0 1 0 1 0 2 0 1 0 3 0 1 0 4 0 1 0 5 0 1 0 6 0 1 0 7 0 1 0 8 0 1 0 9 0 1 1 1 0 1 1 2 0 1 1 3 0 1 1 4 0 1 1 5 0 1 1 6 0 1 1 7 0 1 1 8 0 1 1 9 0 1 2 1 0 1 2 2 0 1 2 3 0 1 2 4 0 1 2 5 0 1 2 6 0 1 2 7 0 1 2 8 0 1 2 9 0 1 3 1 0 1 3 2 0 1 3 3 0 1 3 4 0 1 3 5 0 1 3 6 0 1 3 7 0 1 3 8 0 1 3 9 0 1 4 1 0 1 4 2 0 1 4 3 0 1 4 4 0 1 4 5 0 1 4 6 0 1 4 7 0 1 4 8 0 1 4 9 0 1 5 1 0 1 5 2 0 1 5 3 0 1 5 4 0 1 5 5 0 1 5 6 0 1 5 7 0 1 5 8 0 1 5 9 0 1 6 1 0 1 6 2 0 1 6 3 0 1 6 4 0 1 6 5 0 1 6 6 0 1 6 7 0 1 6 8 0 1 6 9 0 1 7 1 0 1 7 2 0 1 7 3 0 1 7 4 0 1 7 5 0 1 7 6 0 1 7 7 0 1 7 8 0 1 7 9 0 1 8 1 0 1 8 2 0 1 8 3 0 1 8 4 0 1 8 5 0 1 8 6 0 1 8 7 0 1 8 8 0 1 8 9 0 1 9 1 0 1 9 2 0 1 9 3 0 1 9 4 0 1 9 5 0 1 9 6 0 1 9 7 0 1 9 8 0 1 9 9 0 2 0 2 0 3 0 2 0 4 0 2 0 5 0 2 0 6 0 2 0 7 0 2 0 8 0 2 0 9 0 2 1 1 0 2 1 2 0 2 1 3 0 2 1 4 0 2 1 5 0 2 1 6 0 2 1 7 0 2 1 8 0 2 1 9 0 2 2 1 0 2 2 2 0 2 2 3 0 2 2 4 0 2 2 5 0 2 2 6 0 2 2 7 0 2 2 8 0 2 2 9 0 2 3 1 0 2 3 2 0 2 3 3 0 2 3 4 0 2 3 5 0 2 3 6 0 2 3 7 0 2 3 8 0 2 3 9 0 2 4 1 0 2 4 2 0 2 4 3 0 2 4 4 0 2 4 5 0 2 4 6 0 2 4 7 0 2 4 8 0 2 4 9 0 2 5 1 0 2 5 2 0 2 5 3 0 2 5 4 0 2 5 5 0 2 5 6 0 2 5 7 0 2 5 8 0 2 5 9 0 2 6 1 0 2 6 2 0 2 6 3 0 2 6 4 0 2 6 5 0 2 6 6 0 2 6 7 0 2 6 8 0 2 6 9 0 2 7 1 0 2 7 2 0 2 7 3 0 2 7 4 0 2 7 5 0 2 7 6 0 2 7 7 0 2 7 8 0 2 7 9 0 2 8 1 0 2 8 2 0 2 8 3 0 2 8 4 0 2 8 5 0 2 8 6 0 2 8 7 0 2 8 8 0 2 8 9 0 2 9 1 0 2 9 2 0 2 9 3 0 2 9 4 0 2 9 5 0 2 9 6 0 2 9 7 0 2 9 8 0 2 9 9 0 3 0 3 0 4 0 3 0 5 0 3 0 6 0 3 0 7 0 3 0 8 0 3 0 9 0 3 1 1 0 3 1 2 0 3 1 3 0 3 1 4 0 3 1 5 0 3 1 6 0 3 1 7 0 3 1 8 0 3 1 9 0 3 2 1 0 3 2 2 0 3 2 3 0 3 2 4 0 3 2 5 0 3 2 6 0 3 2 7 0 3 2 8 0 3 2 9 0 3 3 1 0 3 3 2 0 3 3 3 0 3 3 4 0 3 3 5 0 3 3 6 0 3 3 7 0 3 3 8 0 3 3 9 0 3 4 1 0 3 4 2 0 3 4 3 0 3 4 4 0 3 4 5 0 3 4 6 0 3 4 7 0 3 4 8 0 3 4 9 0 3 5 1 0 3 5 2 0 3 5 3 0 3 5 4 0 3 5 5 0 3 5 6 0 3 5 7 0 3 5 8 0 3 5 9 0 3 6 1 0 3 6 2 0 3 6 3 0 3 6 4 0 3 6 5 0 3 6 6 0 3 6 7 0 3 6 8 0 3 6 9 0 3 7 1 0 3 7 2 0 3 7 3 0 3 7 4 0 3 7 5 0 3 7 6 0 3 7 7 0 3 7 8 0 3 7 9 0 3 8 1 0 3 8 2 0 3 8 3 0 3 8 4 0 3 8 5 0 3 8 6 0 3 8 7 0 3 8 8 0 3 8 9 0 3 9 1 0 3 9 2 0 3 9 3 0 3 9 4 0 3 9 5 0 3 9 6 0 3 9 7 0 3 9 8 0 3 9 9 0 4 0 4 0 5 0 4 0 6 0 4 0 7 0 4 0 8 0 4 0 9 0 4 1 1 0 4 1 2 0 4 1 3 0 4 1 4 0 4 1 5 0 4 1 6 0 4 1 7 0 4 1 8 0 4 1 9 0 4 2 1 0 4 2 2 0 4 2 3 0 4 2 4 0 4 2 5 0 4 2 6 0 4 2 7 0 4 2 8 0 4 2 9 0 4 3 1 0 4 3 2 0 4 3 3 0 4 3 4 0 4 3 5 0 4 3 6 0 4 3 7 0 4 3 8 0 4 3 9 0 4 4 1 0 4 4 2 0 4 4 3 0 4 4 4 0 4 4 5 0 4 4 6 0 4 4 7 0 4 4 8 0 4 4 9 0 4 5 1 0 4 5 2 0 4 5 3 0 4 5 4 0 4 5 5 0 4 5 6 0 4 5 7 0 4 5 8 0 4 5 9 0 4 6 1 0 4 6 2 0 4 6 3 0 4 6 4 0 4 6 5 0 4 6 6 0 4 6 7 0 4 6 8 0 4 6 9 0 4 7 1 0 4 7 2 0 4 7 3 0 4 7 4 0 4 7 5 0 4 7 6 0 4 7 7 0 4 7 8 0 4 7 9 0 4 8 1 0 4 8 2 0 4 8 3 0 4 8 4 0 4 8 5 0 4 8 6 0 4 8 7 0 4 8 8 0 4 8 9 0 4 9 1 0 4 9 2 0 4 9 3 0 4 9 4 0 4 9 5 0 4 9 6 0 4 9 7 0 4 9 8 0 4 9 9 0 5 0 5 0 6 0 5 0 7 0 5 0 8 0 5 0 9 0 5 1 1 0 5 1 2 0 5 1 3 0 5 1 4 0 5 1 5 0 5 1 6 0 5 1 7 0 5 1 8 0 5 1 9 0 5 2 1 0 5 2 2 0 5 2 3 0 5 2 4 0 5 2 5 0 5 2 6 0 5 2 7 0 5 2 8 0 5 2 9 0 5 3 1 0 5 3 2 0 5 3 3 0 5 3 4 0 5 3 5 0 5 3 6 0 5 3 7 0 5 3 8 0 5 3 9 0 5 4 1 0 5 4 2 0 5 4 3 0 5 4 4 0 5 4 5 0 5 4 6 0 5 4 7 0 5 4 8 0 5 4 9 0 5 5 1 0 5 5 2 0 5 5 3 0 5 5 4 0 5 5 5 0 5 5 6 0 5 5 7 0 5 5 8 0 5 5 9 0 5 6 1 0 5 6 2 0 5 6 3 0 5 6 4 0 5 6 5 0 5 6 6 0 5 6 7 0 5 6 8 0 5 6 9 0 5 7 1 0 5 7 2 0 5 7 3 0 5 7 4 0 5 7 5 0 5 7 6 0 5 7 7 0 5 7 8 0 5 7 9 0 5 8 1 0 5 8 2 0 5 8 3 0 5 8 4 0 5 8 5 0 5 8 6 0 5 8 7 0 5 8 8 0 5 8 9 0 5 9 1 0 5 9 2 0 5 9 3 0 5 9 4 0 5 9 5 0 5 9 6 0 5 9 7 0 5 9 8 0 5 9 9 0 6 0 6 0 7 0 6 0 8 0 6 0 9 0 6 1 1 0 6 1 2 0 6 1 3 0 6 1 4 0 6 1 5 0 6 1 6 0 6 1 7 0 6 1 8 0 6 1 9 0 6 2 1 0 6 2 2 0 6 2 3 0 6 2 4 0 6 2 5 0 6 2 6 0 6 2 7 0 6 2 8 0 6 2 9 0 6 3 1 0 6 3 2 0 6 3 3 0 6 3 4 0 6 3 5 0 6 3 6 0 6 3 7 0 6 3 8 0 6 3 9 0 6 4 1 0 6 4 2 0 6 4 3 0 6 4 4 0 6 4 5 0 6 4 6 0 6 4 7 0 6 4 8 0 6 4 9 0 6 5 1 0 6 5 2 0 6 5 3 0 6 5 4 0 6 5 5 0 6 5 6 0 6 5 7 0 6 5 8 0 6 5 9 0 6 6 1 0 6 6 2 0 6 6 3 0 6 6 4 0 6 6 5 0 6 6 6 0 6 6 7 0 6 6 8 0 6 6 9 0 6 7 1 0 6 7 2 0 6 7 3 0 6 7 4 0 6 7 5 0 6 7 6 0 6 7 7 0 6 7 8 0 6 7 9 0 6 8 1 0 6 8 2 0 6 8 3 0 6 8 4 0 6 8 5 0 6 8 6 0 6 8 7 0 6 8 8 0 6 8 9 0 6 9 1 0 6 9 2 0 6 9 3 0 6 9 4 0 6 9 5 0 6 9 6 0 6 9 7 0 6 9 8 0 6 9 9 0 7 0 7 0 8 0 7 0 9 0 7 1 1 0 7 1 2 0 7 1 3 0 7 1 4 0 7 1 5 0 7 1 6 0 7 1 7 0 7 1 8 0 7 1 9 0 7 2 1 0 7 2 2 0 7 2 3 0 7 2 4 0 7 2 5 0 7 2 6 0 7 2 7 0 7 2 8 0 7 2 9 0 7 3 1 0 7 3 2 0 7 3 3 0 7 3 4 0 7 3 5 0 7 3 6 0 7 3 7 0 7 3 8 0 7 3 9 0 7 4 1 0 7 4 2 0 7 4 3 0 7 4 4 0 7 4 5 0 7 4 6 0 7 4 7 0 7 4 8 0 7 4 9 0 7 5 1 0 7 5 2 0 7 5 3 0 7 5 4 0 7 5 5 0 7 5 6 0 7 5 7 0 7 5 8 0 7 5 9 0 7 6 1 0 7 6 2 0 7 6 3 0 7 6 4 0 7 6 5 0 7 6 6 0 7 6 7 0 7 6 8 0 7 6 9 0 7 7 1 0 7 7 2 0 7 7 3 0 7 7 4 0 7 7 5 0 7 7 6 0 7 7 7 0 7 7 8 0 7 7 9 0 7 8 1 0 7 8 2 0 7 8 3 0 7 8 4 0 7 8 5 0 7 8 6 0 7 8 7 0 7 8 8 0 7 8 9 0 7 9 1 0 7 9 2 0 7 9 3 0 7 9 4 0 7 9 5 0 7 9 6 0 7 9 7 0 7 9 8 0 7 9 9 0 8 0 8 0 9 0 8 1 1 0 8 1 2 0 8 1 3 0 8 1 4 0 8 1 5 0 8 1 6 0 8 1 7 0 8 1 8 0 8 1 9 0 8 2 1 0 8 2 2 0 8 2 3 0 8 2 4 0 8 2 5 0 8 2 6 0 8 2 7 0 8 2 8 0 8 2 9 0 8 3 1 0 8 3 2 0 8 3 3 0 8 3 4 0 8 3 5 0 8 3 6 0 8 3 7 0 8 3 8 0 8 3 9 0 8 4 1 0 8 4 2 0 8 4 3 0 8 4 4 0 8 4 5 0 8 4 6 0 8 4 7 0 8 4 8 0 8 4 9 0 8 5 1 0 8 5 2 0 8 5 3 0 8 5 4 0 8 5 5 0 8 5 6 0 8 5 7 0 8 5 8 0 8 5 9 0 8 6 1 0 8 6 2 0 8 6 3 0 8 6 4 0 8 6 5 0 8 6 6 0 8 6 7 0 8 6 8 0 8 6 9 0 8 7 1 0 8 7 2 0 8 7 3 0 8 7 4 0 8 7 5 0 8 7 6 0 8 7 7 0 8 7 8 0 8 7 9 0 8 8 1 0 8 8 2 0 8 8 3 0 8 8 4 0 8 8 5 0 8 8 6 0 8 8 7 0 8 8 8 0 8 8 9 0 8 9 1 0 8 9 2 0 8 9 3 0 8 9 4 0 8 9 5 0 8 9 6 0 8 9 7 0 8 9 8 0 8 9 9 0 9 0 9 1 1 0 9 1 2 0 9 1 3 0 9 1 4 0 9 1 5 0 9 1 6 0 9 1 7 0 9 1 8 0 9 1 9 0 9 2 1 0 9 2 2 0 9 2 3 0 9 2 4 0 9 2 5 0 9 2 6 0 9 2 7 0 9 2 8 0 9 2 9 0 9 3 1 0 9 3 2 0 9 3 3 0 9 3 4 0 9 3 5 0 9 3 6 0 9 3 7 0 9 3 8 0 9 3 9 0 9 4 1 0 9 4 2 0 9 4 3 0 9 4 4 0 9 4 5 0 9 4 6 0 9 4 7 0 9 4 8 0 9 4 9 0 9 5 1 0 9 5 2 0 9 5 3 0 9 5 4 0 9 5 5 0 9 5 6 0 9 5 7 0 9 5 8 0 9 5 9 0 9 6 1 0 9 6 2 0 9 6 3 0 9 6 4 0 9 6 5 0 9 6 6 0 9 6 7 0 9 6 8 0 9 6 9 0 9 7 1 0 9 7 2 0 9 7 3 0 9 7 4 0 9 7 5 0 9 7 6 0 9 7 7 0 9 7 8 0 9 7 9 0 9 8 1 0 9 8 2 0 9 8 3 0 9 8 4 0 9 8 5 0 9 8 6 0 9 8 7 0 9 8 8 0 9 8 9 0 9 9 1 0 9 9 2 0 9 9 3 0 9 9 4 0 9 9 5 0 9 9 6 0 9 9 7 0 9 9 8 0 9 9 9 1 1 1 1 2 1 1 1 3 1 1 1 4 1 1 1 5 1 1 1 6 1 1 1 7 1 1 1 8 1 1 1 9 1 1 2 2 1 1 2 3 1 1 2 4 1 1 2 5 1 1 2 6 1 1 2 7 1 1 2 8 1 1 2 9 1 1 3 2 1 1 3 3 1 1 3 4 1 1 3 5 1 1 3 6 1 1 3 7 1 1 3 8 1 1 3 9 1 1 4 2 1 1 4 3 1 1 4 4 1 1 4 5 1 1 4 6 1 1 4 7 1 1 4 8 1 1 4 9 1 1 5 2 1 1 5 3 1 1 5 4 1 1 5 5 1 1 5 6 1 1 5 7 1 1 5 8 1 1 5 9 1 1 6 2 1 1 6 3 1 1 6 4 1 1 6 5 1 1 6 6 1 1 6 7 1 1 6 8 1 1 6 9 1 1 7 2 1 1 7 3 1 1 7 4 1 1 7 5 1 1 7 6 1 1 7 7 1 1 7 8 1 1 7 9 1 1 8 2 1 1 8 3 1 1 8 4 1 1 8 5 1 1 8 6 1 1 8 7 1 1 8 8 1 1 8 9 1 1 9 2 1 1 9 3 1 1 9 4 1 1 9 5 1 1 9 6 1 1 9 7 1 1 9 8 1 1 9 9 1 2 1 2 1 3 1 2 1 4 1 2 1 5 1 2 1 6 1 2 1 7 1 2 1 8 1 2 1 9 1 2 2 2 1 2 2 3 1 2 2 4 1 2 2 5 1 2 2 6 1 2 2 7 1 2 2 8 1 2 2 9 1 2 3 2 1 2 3 3 1 2 3 4 1 2 3 5 1 2 3 6 1 2 3 7 1 2 3 8 1 2 3 9 1 2 4 2 1 2 4 3 1 2 4 4 1 2 4 5 1 2 4 6 1 2 4 7 1 2 4 8 1 2 4 9 1 2 5 2 1 2 5 3 1 2 5 4 1 2 5 5 1 2 5 6 1 2 5 7 1 2 5 8 1 2 5 9 1 2 6 2 1 2 6 3 1 2 6 4 1 2 6 5 1 2 6 6 1 2 6 7 1 2 6 8 1 2 6 9 1 2 7 2 1 2 7 3 1 2 7 4 1 2 7 5 1 2 7 6 1 2 7 7 1 2 7 8 1 2 7 9 1 2 8 2 1 2 8 3 1 2 8 4 1 2 8 5 1 2 8 6 1 2 8 7 1 2 8 8 1 2 8 9 1 2 9 2 1 2 9 3 1 2 9 4 1 2 9 5 1 2 9 6 1 2 9 7 1 2 9 8 1 2 9 9 1 3 1 3 1 4 1 3 1 5 1 3 1 6 1 3 1 7 1 3 1 8 1 3 1 9 1 3 2 2 1 3 2 3 1 3 2 4 1 3 2 5 1 3 2 6 1 3 2 7 1 3 2 8 1 3 2 9 1 3 3 2 1 3 3 3 1 3 3 4 1 3 3 5 1 3 3 6 1 3 3 7 1 3 3 8 1 3 3 9 1 3 4 2 1 3 4 3 1 3 4 4 1 3 4 5 1 3 4 6 1 3 4 7 1 3 4 8 1 3 4 9 1 3 5 2 1 3 5 3 1 3 5 4 1 3 5 5 1 3 5 6 1 3 5 7 1 3 5 8 1 3 5 9 1 3 6 2 1 3 6 3 1 3 6 4 1 3 6 5 1 3 6 6 1 3 6 7 1 3 6 8 1 3 6 9 1 3 7 2 1 3 7 3 1 3 7 4 1 3 7 5 1 3 7 6 1 3 7 7 1 3 7 8 1 3 7 9 1 3 8 2 1 3 8 3 1 3 8 4 1 3 8 5 1 3 8 6 1 3 8 7 1 3 8 8 1 3 8 9 1 3 9 2 1 3 9 3 1 3 9 4 1 3 9 5 1 3 9 6 1 3 9 7 1 3 9 8 1 3 9 9 1 4 1 4 1 5 1 4 1 6 1 4 1 7 1 4 1 8 1 4 1 9 1 4 2 2 1 4 2 3 1 4 2 4 1 4 2 5 1 4 2 6 1 4 2 7 1 4 2 8 1 4 2 9 1 4 3 2 1 4 3 3 1 4 3 4 1 4 3 5 1 4 3 6 1 4 3 7 1 4 3 8 1 4 3 9 1 4 4 2 1 4 4 3 1 4 4 4 1 4 4 5 1 4 4 6 1 4 4 7 1 4 4 8 1 4 4 9 1 4 5 2 1 4 5 3 1 4 5 4 1 4 5 5 1 4 5 6 1 4 5 7 1 4 5 8 1 4 5 9 1 4 6 2 1 4 6 3 1 4 6 4 1 4 6 5 1 4 6 6 1 4 6 7 1 4 6 8 1 4 6 9 1 4 7 2 1 4 7 3 1 4 7 4 1 4 7 5 1 4 7 6 1 4 7 7 1 4 7 8 1 4 7 9 1 4 8 2 1 4 8 3 1 4 8 4 1 4 8 5 1 4 8 6 1 4 8 7 1 4 8 8 1 4 8 9 1 4 9 2 1 4 9 3 1 4 9 4 1 4 9 5 1 4 9 6 1 4 9 7 1 4 9 8 1 4 9 9 1 5 1 5 1 6 1 5 1 7 1 5 1 8 1 5 1 9 1 5 2 2 1 5 2 3 1 5 2 4 1 5 2 5 1 5 2 6 1 5 2 7 1 5 2 8 1 5 2 9 1 5 3 2 1 5 3 3 1 5 3 4 1 5 3 5 1 5 3 6 1 5 3 7 1 5 3 8 1 5 3 9 1 5 4 2 1 5 4 3 1 5 4 4 1 5 4 5 1 5 4 6 1 5 4 7 1 5 4 8 1 5 4 9 1 5 5 2 1 5 5 3 1 5 5 4 1 5 5 5 1 5 5 6 1 5 5 7 1 5 5 8 1 5 5 9 1 5 6 2 1 5 6 3 1 5 6 4 1 5 6 5 1 5 6 6 1 5 6 7 1 5 6 8 1 5 6 9 1 5 7 2 1 5 7 3 1 5 7 4 1 5 7 5 1 5 7 6 1 5 7 7 1 5 7 8 1 5 7 9 1 5 8 2 1 5 8 3 1 5 8 4 1 5 8 5 1 5 8 6 1 5 8 7 1 5 8 8 1 5 8 9 1 5 9 2 1 5 9 3 1 5 9 4 1 5 9 5 1 5 9 6 1 5 9 7 1 5 9 8 1 5 9 9 1 6 1 6 1 7 1 6 1 8 1 6 1 9 1 6 2 2 1 6 2 3 1 6 2 4 1 6 2 5 1 6 2 6 1 6 2 7 1 6 2 8 1 6 2 9 1 6 3 2 1 6 3 3 1 6 3 4 1 6 3 5 1 6 3 6 1 6 3 7 1 6 3 8 1 6 3 9 1 6 4 2 1 6 4 3 1 6 4 4 1 6 4 5 1 6 4 6 1 6 4 7 1 6 4 8 1 6 4 9 1 6 5 2 1 6 5 3 1 6 5 4 1 6 5 5 1 6 5 6 1 6 5 7 1 6 5 8 1 6 5 9 1 6 6 2 1 6 6 3 1 6 6 4 1 6 6 5 1 6 6 6 1 6 6 7 1 6 6 8 1 6 6 9 1 6 7 2 1 6 7 3 1 6 7 4 1 6 7 5 1 6 7 6 1 6 7 7 1 6 7 8 1 6 7 9 1 6 8 2 1 6 8 3 1 6 8 4 1 6 8 5 1 6 8 6 1 6 8 7 1 6 8 8 1 6 8 9 1 6 9 2 1 6 9 3 1 6 9 4 1 6 9 5 1 6 9 6 1 6 9 7 1 6 9 8 1 6 9 9 1 7 1 7 1 8 1 7 1 9 1 7 2 2 1 7 2 3 1 7 2 4 1 7 2 5 1 7 2 6 1 7 2 7 1 7 2 8 1 7 2 9 1 7 3 2 1 7 3 3 1 7 3 4 1 7 3 5 1 7 3 6 1 7 3 7 1 7 3 8 1 7 3 9 1 7 4 2 1 7 4 3 1 7 4 4 1 7 4 5 1 7 4 6 1 7 4 7 1 7 4 8 1 7 4 9 1 7 5 2 1 7 5 3 1 7 5 4 1 7 5 5 1 7 5 6 1 7 5 7 1 7 5 8 1 7 5 9 1 7 6 2 1 7 6 3 1 7 6 4 1 7 6 5 1 7 6 6 1 7 6 7 1 7 6 8 1 7 6 9 1 7 7 2 1 7 7 3 1 7 7 4 1 7 7 5 1 7 7 6 1 7 7 7 1 7 7 8 1 7 7 9 1 7 8 2 1 7 8 3 1 7 8 4 1 7 8 5 1 7 8 6 1 7 8 7 1 7 8 8 1 7 8 9 1 7 9 2 1 7 9 3 1 7 9 4 1 7 9 5 1 7 9 6 1 7 9 7 1 7 9 8 1 7 9 9 1 8 1 8 1 9 1 8 2 2 1 8 2 3 1 8 2 4 1 8 2 5 1 8 2 6 1 8 2 7 1 8 2 8 1 8 2 9 1 8 3 2 1 8 3 3 1 8 3 4 1 8 3 5 1 8 3 6 1 8 3 7 1 8 3 8 1 8 3 9 1 8 4 2 1 8 4 3 1 8 4 4 1 8 4 5 1 8 4 6 1 8 4 7 1 8 4 8 1 8 4 9 1 8 5 2 1 8 5 3 1 8 5 4 1 8 5 5 1 8 5 6 1 8 5 7 1 8 5 8 1 8 5 9 1 8 6 2 1 8 6 3 1 8 6 4 1 8 6 5 1 8 6 6 1 8 6 7 1 8 6 8 1 8 6 9 1 8 7 2 1 8 7 3 1 8 7 4 1 8 7 5 1 8 7 6 1 8 7 7 1 8 7 8 1 8 7 9 1 8 8 2 1 8 8 3 1 8 8 4 1 8 8 5 1 8 8 6 1 8 8 7 1 8 8 8 1 8 8 9 1 8 9 2 1 8 9 3 1 8 9 4 1 8 9 5 1 8 9 6 1 8 9 7 1 8 9 8 1 8 9 9 1 9 1 9 2 2 1 9 2 3 1 9 2 4 1 9 2 5 1 9 2 6 1 9 2 7 1 9 2 8 1 9 2 9 1 9 3 2 1 9 3 3 1 9 3 4 1 9 3 5 1 9 3 6 1 9 3 7 1 9 3 8 1 9 3 9 1 9 4 2 1 9 4 3 1 9 4 4 1 9 4 5 1 9 4 6 1 9 4 7 1 9 4 8 1 9 4 9 1 9 5 2 1 9 5 3 1 9 5 4 1 9 5 5 1 9 5 6 1 9 5 7 1 9 5 8 1 9 5 9 1 9 6 2 1 9 6 3 1 9 6 4 1 9 6 5 1 9 6 6 1 9 6 7 1 9 6 8 1 9 6 9 1 9 7 2 1 9 7 3 1 9 7 4 1 9 7 5 1 9 7 6 1 9 7 7 1 9 7 8 1 9 7 9 1 9 8 2 1 9 8 3 1 9 8 4 1 9 8 5 1 9 8 6 1 9 8 7 1 9 8 8 1 9 8 9 1 9 9 2 1 9 9 3 1 9 9 4 1 9 9 5 1 9 9 6 1 9 9 7 1 9 9 8 1 9 9 9 2 2 2 2 3 2 2 2 4 2 2 2 5 2 2 2 6 2 2 2 7 2 2 2 8 2 2 2 9 2 2 3 3 2 2 3 4 2 2 3 5 2 2 3 6 2 2 3 7 2 2 3 8 2 2 3 9 2 2 4 3 2 2 4 4 2 2 4 5 2 2 4 6 2 2 4 7 2 2 4 8 2 2 4 9 2 2 5 3 2 2 5 4 2 2 5 5 2 2 5 6 2 2 5 7 2 2 5 8 2 2 5 9 2 2 6 3 2 2 6 4 2 2 6 5 2 2 6 6 2 2 6 7 2 2 6 8 2 2 6 9 2 2 7 3 2 2 7 4 2 2 7 5 2 2 7 6 2 2 7 7 2 2 7 8 2 2 7 9 2 2 8 3 2 2 8 4 2 2 8 5 2 2 8 6 2 2 8 7 2 2 8 8 2 2 8 9 2 2 9 3 2 2 9 4 2 2 9 5 2 2 9 6 2 2 9 7 2 2 9 8 2 2 9 9 2 3 2 3 2 4 2 3 2 5 2 3 2 6 2 3 2 7 2 3 2 8 2 3 2 9 2 3 3 3 2 3 3 4 2 3 3 5 2 3 3 6 2 3 3 7 2 3 3 8 2 3 3 9 2 3 4 3 2 3 4 4 2 3 4 5 2 3 4 6 2 3 4 7 2 3 4 8 2 3 4 9 2 3 5 3 2 3 5 4 2 3 5 5 2 3 5 6 2 3 5 7 2 3 5 8 2 3 5 9 2 3 6 3 2 3 6 4 2 3 6 5 2 3 6 6 2 3 6 7 2 3 6 8 2 3 6 9 2 3 7 3 2 3 7 4 2 3 7 5 2 3 7 6 2 3 7 7 2 3 7 8 2 3 7 9 2 3 8 3 2 3 8 4 2 3 8 5 2 3 8 6 2 3 8 7 2 3 8 8 2 3 8 9 2 3 9 3 2 3 9 4 2 3 9 5 2 3 9 6 2 3 9 7 2 3 9 8 2 3 9 9 2 4 2 4 2 5 2 4 2 6 2 4 2 7 2 4 2 8 2 4 2 9 2 4 3 3 2 4 3 4 2 4 3 5 2 4 3 6 2 4 3 7 2 4 3 8 2 4 3 9 2 4 4 3 2 4 4 4 2 4 4 5 2 4 4 6 2 4 4 7 2 4 4 8 2 4 4 9 2 4 5 3 2 4 5 4 2 4 5 5 2 4 5 6 2 4 5 7 2 4 5 8 2 4 5 9 2 4 6 3 2 4 6 4 2 4 6 5 2 4 6 6 2 4 6 7 2 4 6 8 2 4 6 9 2 4 7 3 2 4 7 4 2 4 7 5 2 4 7 6 2 4 7 7 2 4 7 8 2 4 7 9 2 4 8 3 2 4 8 4 2 4 8 5 2 4 8 6 2 4 8 7 2 4 8 8 2 4 8 9 2 4 9 3 2 4 9 4 2 4 9 5 2 4 9 6 2 4 9 7 2 4 9 8 2 4 9 9 2 5 2 5 2 6 2 5 2 7 2 5 2 8 2 5 2 9 2 5 3 3 2 5 3 4 2 5 3 5 2 5 3 6 2 5 3 7 2 5 3 8 2 5 3 9 2 5 4 3 2 5 4 4 2 5 4 5 2 5 4 6 2 5 4 7 2 5 4 8 2 5 4 9 2 5 5 3 2 5 5 4 2 5 5 5 2 5 5 6 2 5 5 7 2 5 5 8 2 5 5 9 2 5 6 3 2 5 6 4 2 5 6 5 2 5 6 6 2 5 6 7 2 5 6 8 2 5 6 9 2 5 7 3 2 5 7 4 2 5 7 5 2 5 7 6 2 5 7 7 2 5 7 8 2 5 7 9 2 5 8 3 2 5 8 4 2 5 8 5 2 5 8 6 2 5 8 7 2 5 8 8 2 5 8 9 2 5 9 3 2 5 9 4 2 5 9 5 2 5 9 6 2 5 9 7 2 5 9 8 2 5 9 9 2 6 2 6 2 7 2 6 2 8 2 6 2 9 2 6 3 3 2 6 3 4 2 6 3 5 2 6 3 6 2 6 3 7 2 6 3 8 2 6 3 9 2 6 4 3 2 6 4 4 2 6 4 5 2 6 4 6 2 6 4 7 2 6 4 8 2 6 4 9 2 6 5 3 2 6 5 4 2 6 5 5 2 6 5 6 2 6 5 7 2 6 5 8 2 6 5 9 2 6 6 3 2 6 6 4 2 6 6 5 2 6 6 6 2 6 6 7 2 6 6 8 2 6 6 9 2 6 7 3 2 6 7 4 2 6 7 5 2 6 7 6 2 6 7 7 2 6 7 8 2 6 7 9 2 6 8 3 2 6 8 4 2 6 8 5 2 6 8 6 2 6 8 7 2 6 8 8 2 6 8 9 2 6 9 3 2 6 9 4 2 6 9 5 2 6 9 6 2 6 9 7 2 6 9 8 2 6 9 9 2 7 2 7 2 8 2 7 2 9 2 7 3 3 2 7 3 4 2 7 3 5 2 7 3 6 2 7 3 7 2 7 3 8 2 7 3 9 2 7 4 3 2 7 4 4 2 7 4 5 2 7 4 6 2 7 4 7 2 7 4 8 2 7 4 9 2 7 5 3 2 7 5 4 2 7 5 5 2 7 5 6 2 7 5 7 2 7 5 8 2 7 5 9 2 7 6 3 2 7 6 4 2 7 6 5 2 7 6 6 2 7 6 7 2 7 6 8 2 7 6 9 2 7 7 3 2 7 7 4 2 7 7 5 2 7 7 6 2 7 7 7 2 7 7 8 2 7 7 9 2 7 8 3 2 7 8 4 2 7 8 5 2 7 8 6 2 7 8 7 2 7 8 8 2 7 8 9 2 7 9 3 2 7 9 4 2 7 9 5 2 7 9 6 2 7 9 7 2 7 9 8 2 7 9 9 2 8 2 8 2 9 2 8 3 3 2 8 3 4 2 8 3 5 2 8 3 6 2 8 3 7 2 8 3 8 2 8 3 9 2 8 4 3 2 8 4 4 2 8 4 5 2 8 4 6 2 8 4 7 2 8 4 8 2 8 4 9 2 8 5 3 2 8 5 4 2 8 5 5 2 8 5 6 2 8 5 7 2 8 5 8 2 8 5 9 2 8 6 3 2 8 6 4 2 8 6 5 2 8 6 6 2 8 6 7 2 8 6 8 2 8 6 9 2 8 7 3 2 8 7 4 2 8 7 5 2 8 7 6 2 8 7 7 2 8 7 8 2 8 7 9 2 8 8 3 2 8 8 4 2 8 8 5 2 8 8 6 2 8 8 7 2 8 8 8 2 8 8 9 2 8 9 3 2 8 9 4 2 8 9 5 2 8 9 6 2 8 9 7 2 8 9 8 2 8 9 9 2 9 2 9 3 3 2 9 3 4 2 9 3 5 2 9 3 6 2 9 3 7 2 9 3 8 2 9 3 9 2 9 4 3 2 9 4 4 2 9 4 5 2 9 4 6 2 9 4 7 2 9 4 8 2 9 4 9 2 9 5 3 2 9 5 4 2 9 5 5 2 9 5 6 2 9 5 7 2 9 5 8 2 9 5 9 2 9 6 3 2 9 6 4 2 9 6 5 2 9 6 6 2 9 6 7 2 9 6 8 2 9 6 9 2 9 7 3 2 9 7 4 2 9 7 5 2 9 7 6 2 9 7 7 2 9 7 8 2 9 7 9 2 9 8 3 2 9 8 4 2 9 8 5 2 9 8 6 2 9 8 7 2 9 8 8 2 9 8 9 2 9 9 3 2 9 9 4 2 9 9 5 2 9 9 6 2 9 9 7 2 9 9 8 2 9 9 9 3 3 3 3 4 3 3 3 5 3 3 3 6 3 3 3 7 3 3 3 8 3 3 3 9 3 3 4 4 3 3 4 5 3 3 4 6 3 3 4 7 3 3 4 8 3 3 4 9 3 3 5 4 3 3 5 5 3 3 5 6 3 3 5 7 3 3 5 8 3 3 5 9 3 3 6 4 3 3 6 5 3 3 6 6 3 3 6 7 3 3 6 8 3 3 6 9 3 3 7 4 3 3 7 5 3 3 7 6 3 3 7 7 3 3 7 8 3 3 7 9 3 3 8 4 3 3 8 5 3 3 8 6 3 3 8 7 3 3 8 8 3 3 8 9 3 3 9 4 3 3 9 5 3 3 9 6 3 3 9 7 3 3 9 8 3 3 9 9 3 4 3 4 3 5 3 4 3 6 3 4 3 7 3 4 3 8 3 4 3 9 3 4 4 4 3 4 4 5 3 4 4 6 3 4 4 7 3 4 4 8 3 4 4 9 3 4 5 4 3 4 5 5 3 4 5 6 3 4 5 7 3 4 5 8 3 4 5 9 3 4 6 4 3 4 6 5 3 4 6 6 3 4 6 7 3 4 6 8 3 4 6 9 3 4 7 4 3 4 7 5 3 4 7 6 3 4 7 7 3 4 7 8 3 4 7 9 3 4 8 4 3 4 8 5 3 4 8 6 3 4 8 7 3 4 8 8 3 4 8 9 3 4 9 4 3 4 9 5 3 4 9 6 3 4 9 7 3 4 9 8 3 4 9 9 3 5 3 5 3 6 3 5 3 7 3 5 3 8 3 5 3 9 3 5 4 4 3 5 4 5 3 5 4 6 3 5 4 7 3 5 4 8 3 5 4 9 3 5 5 4 3 5 5 5 3 5 5 6 3 5 5 7 3 5 5 8 3 5 5 9 3 5 6 4 3 5 6 5 3 5 6 6 3 5 6 7 3 5 6 8 3 5 6 9 3 5 7 4 3 5 7 5 3 5 7 6 3 5 7 7 3 5 7 8 3 5 7 9 3 5 8 4 3 5 8 5 3 5 8 6 3 5 8 7 3 5 8 8 3 5 8 9 3 5 9 4 3 5 9 5 3 5 9 6 3 5 9 7 3 5 9 8 3 5 9 9 3 6 3 6 3 7 3 6 3 8 3 6 3 9 3 6 4 4 3 6 4 5 3 6 4 6 3 6 4 7 3 6 4 8 3 6 4 9 3 6 5 4 3 6 5 5 3 6 5 6 3 6 5 7 3 6 5 8 3 6 5 9 3 6 6 4 3 6 6 5 3 6 6 6 3 6 6 7 3 6 6 8 3 6 6 9 3 6 7 4 3 6 7 5 3 6 7 6 3 6 7 7 3 6 7 8 3 6 7 9 3 6 8 4 3 6 8 5 3 6 8 6 3 6 8 7 3 6 8 8 3 6 8 9 3 6 9 4 3 6 9 5 3 6 9 6 3 6 9 7 3 6 9 8 3 6 9 9 3 7 3 7 3 8 3 7 3 9 3 7 4 4 3 7 4 5 3 7 4 6 3 7 4 7 3 7 4 8 3 7 4 9 3 7 5 4 3 7 5 5 3 7 5 6 3 7 5 7 3 7 5 8 3 7 5 9 3 7 6 4 3 7 6 5 3 7 6 6 3 7 6 7 3 7 6 8 3 7 6 9 3 7 7 4 3 7 7 5 3 7 7 6 3 7 7 7 3 7 7 8 3 7 7 9 3 7 8 4 3 7 8 5 3 7 8 6 3 7 8 7 3 7 8 8 3 7 8 9 3 7 9 4 3 7 9 5 3 7 9 6 3 7 9 7 3 7 9 8 3 7 9 9 3 8 3 8 3 9 3 8 4 4 3 8 4 5 3 8 4 6 3 8 4 7 3 8 4 8 3 8 4 9 3 8 5 4 3 8 5 5 3 8 5 6 3 8 5 7 3 8 5 8 3 8 5 9 3 8 6 4 3 8 6 5 3 8 6 6 3 8 6 7 3 8 6 8 3 8 6 9 3 8 7 4 3 8 7 5 3 8 7 6 3 8 7 7 3 8 7 8 3 8 7 9 3 8 8 4 3 8 8 5 3 8 8 6 3 8 8 7 3 8 8 8 3 8 8 9 3 8 9 4 3 8 9 5 3 8 9 6 3 8 9 7 3 8 9 8 3 8 9 9 3 9 3 9 4 4 3 9 4 5 3 9 4 6 3 9 4 7 3 9 4 8 3 9 4 9 3 9 5 4 3 9 5 5 3 9 5 6 3 9 5 7 3 9 5 8 3 9 5 9 3 9 6 4 3 9 6 5 3 9 6 6 3 9 6 7 3 9 6 8 3 9 6 9 3 9 7 4 3 9 7 5 3 9 7 6 3 9 7 7 3 9 7 8 3 9 7 9 3 9 8 4 3 9 8 5 3 9 8 6 3 9 8 7 3 9 8 8 3 9 8 9 3 9 9 4 3 9 9 5 3 9 9 6 3 9 9 7 3 9 9 8 3 9 9 9 4 4 4 4 5 4 4 4 6 4 4 4 7 4 4 4 8 4 4 4 9 4 4 5 5 4 4 5 6 4 4 5 7 4 4 5 8 4 4 5 9 4 4 6 5 4 4 6 6 4 4 6 7 4 4 6 8 4 4 6 9 4 4 7 5 4 4 7 6 4 4 7 7 4 4 7 8 4 4 7 9 4 4 8 5 4 4 8 6 4 4 8 7 4 4 8 8 4 4 8 9 4 4 9 5 4 4 9 6 4 4 9 7 4 4 9 8 4 4 9 9 4 5 4 5 4 6 4 5 4 7 4 5 4 8 4 5 4 9 4 5 5 5 4 5 5 6 4 5 5 7 4 5 5 8 4 5 5 9 4 5 6 5 4 5 6 6 4 5 6 7 4 5 6 8 4 5 6 9 4 5 7 5 4 5 7 6 4 5 7 7 4 5 7 8 4 5 7 9 4 5 8 5 4 5 8 6 4 5 8 7 4 5 8 8 4 5 8 9 4 5 9 5 4 5 9 6 4 5 9 7 4 5 9 8 4 5 9 9 4 6 4 6 4 7 4 6 4 8 4 6 4 9 4 6 5 5 4 6 5 6 4 6 5 7 4 6 5 8 4 6 5 9 4 6 6 5 4 6 6 6 4 6 6 7 4 6 6 8 4 6 6 9 4 6 7 5 4 6 7 6 4 6 7 7 4 6 7 8 4 6 7 9 4 6 8 5 4 6 8 6 4 6 8 7 4 6 8 8 4 6 8 9 4 6 9 5 4 6 9 6 4 6 9 7 4 6 9 8 4 6 9 9 4 7 4 7 4 8 4 7 4 9 4 7 5 5 4 7 5 6 4 7 5 7 4 7 5 8 4 7 5 9 4 7 6 5 4 7 6 6 4 7 6 7 4 7 6 8 4 7 6 9 4 7 7 5 4 7 7 6 4 7 7 7 4 7 7 8 4 7 7 9 4 7 8 5 4 7 8 6 4 7 8 7 4 7 8 8 4 7 8 9 4 7 9 5 4 7 9 6 4 7 9 7 4 7 9 8 4 7 9 9 4 8 4 8 4 9 4 8 5 5 4 8 5 6 4 8 5 7 4 8 5 8 4 8 5 9 4 8 6 5 4 8 6 6 4 8 6 7 4 8 6 8 4 8 6 9 4 8 7 5 4 8 7 6 4 8 7 7 4 8 7 8 4 8 7 9 4 8 8 5 4 8 8 6 4 8 8 7 4 8 8 8 4 8 8 9 4 8 9 5 4 8 9 6 4 8 9 7 4 8 9 8 4 8 9 9 4 9 4 9 5 5 4 9 5 6 4 9 5 7 4 9 5 8 4 9 5 9 4 9 6 5 4 9 6 6 4 9 6 7 4 9 6 8 4 9 6 9 4 9 7 5 4 9 7 6 4 9 7 7 4 9 7 8 4 9 7 9 4 9 8 5 4 9 8 6 4 9 8 7 4 9 8 8 4 9 8 9 4 9 9 5 4 9 9 6 4 9 9 7 4 9 9 8 4 9 9 9 5 5 5 5 6 5 5 5 7 5 5 5 8 5 5 5 9 5 5 6 6 5 5 6 7 5 5 6 8 5 5 6 9 5 5 7 6 5 5 7 7 5 5 7 8 5 5 7 9 5 5 8 6 5 5 8 7 5 5 8 8 5 5 8 9 5 5 9 6 5 5 9 7 5 5 9 8 5 5 9 9 5 6 5 6 5 7 5 6 5 8 5 6 5 9 5 6 6 6 5 6 6 7 5 6 6 8 5 6 6 9 5 6 7 6 5 6 7 7 5 6 7 8 5 6 7 9 5 6 8 6 5 6 8 7 5 6 8 8 5 6 8 9 5 6 9 6 5 6 9 7 5 6 9 8 5 6 9 9 5 7 5 7 5 8 5 7 5 9 5 7 6 6 5 7 6 7 5 7 6 8 5 7 6 9 5 7 7 6 5 7 7 7 5 7 7 8 5 7 7 9 5 7 8 6 5 7 8 7 5 7 8 8 5 7 8 9 5 7 9 6 5 7 9 7 5 7 9 8 5 7 9 9 5 8 5 8 5 9 5 8 6 6 5 8 6 7 5 8 6 8 5 8 6 9 5 8 7 6 5 8 7 7 5 8 7 8 5 8 7 9 5 8 8 6 5 8 8 7 5 8 8 8 5 8 8 9 5 8 9 6 5 8 9 7 5 8 9 8 5 8 9 9 5 9 5 9 6 6 5 9 6 7 5 9 6 8 5 9 6 9 5 9 7 6 5 9 7 7 5 9 7 8 5 9 7 9 5 9 8 6 5 9 8 7 5 9 8 8 5 9 8 9 5 9 9 6 5 9 9 7 5 9 9 8 5 9 9 9 6 6 6 6 7 6 6 6 8 6 6 6 9 6 6 7 7 6 6 7 8 6 6 7 9 6 6 8 7 6 6 8 8 6 6 8 9 6 6 9 7 6 6 9 8 6 6 9 9 6 7 6 7 6 8 6 7 6 9 6 7 7 7 6 7 7 8 6 7 7 9 6 7 8 7 6 7 8 8 6 7 8 9 6 7 9 7 6 7 9 8 6 7 9 9 6 8 6 8 6 9 6 8 7 7 6 8 7 8 6 8 7 9 6 8 8 7 6 8 8 8 6 8 8 9 6 8 9 7 6 8 9 8 6 8 9 9 6 9 6 9 7 7 6 9 7 8 6 9 7 9 6 9 8 7 6 9 8 8 6 9 8 9 6 9 9 7 6 9 9 8 6 9 9 9 7 7 7 7 8 7 7 7 9 7 7 8 8 7 7 8 9 7 7 9 8 7 7 9 9 7 8 7 8 7 9 7 8 8 8 7 8 8 9 7 8 9 8 7 8 9 9 7 9 7 9 8 8 7 9 8 9 7 9 9 8 7 9 9 9 8 8 8 8 9 8 8 9 9 8 9 8 9 9 9 9 0 0 0

Partons toujours du principe que vous mettez environ 2 secondes à taper 4 chiffres, vous mettrez seulement 3h30 à ouvrir votre porte si le code est le “pire code possible”, c’est à dire 9999 (le dernier code essayé). Contre 13 heures toute à l’heure, presque 4 fois plus long.

La probabilité d’aller beaucoup plus vite ?

Dans les différents logements que j’ai habités, les codes ont toujours été inférieurs au nombre 3000. Si j’avais utilisé cette suite sur mes digicodes, j’aurais pu mettre entre 10 et 30 minutes pour ouvrir la porte. C’est long, mais pourquoi pas ?

Automatiser les tentatives ?

Ça pourrait être un projet passionnant : créer un petit boitier, à base d’Arduino et équipé de quelques servomoteurs, permettant de taper à notre place sur un digicode. Pas mal de difficultés à prendre en compte (adaptation universelle aux digicodes, précision, puissance de frappe). Mais pourquoi pas 😀

Pour en savoir plus sur les suites de de Bruijn

Un générateur de suites, très bien fait.
La page Wikipédia sur le sujet.
La page Wikipédia sur Nicolaas Govert de Bruijn.

Auteur turbulent, et fondateur de l'Institut Pandore. Je me lasse de tout, sauf d'apprendre et de dire des gros mots. J'écrivais sous pseudonyme (Félix Boussa et Charles Cohle).

Ajouter un commentaire

L'addresse électronque est déjà enregistrée sur le site. S'il vous plaît, veuillez utiliser Le formulaire de connexion ou veuillez saisir un autre.

Vous avez saisi un nom d'utilisateur ou mot de passe incorrects

Sorry that something went wrong, repeat again!

24commentaires

des plus récents
Meilleur des plus récents des plus anciens
1

Partisane du moindre effort… Personnellement, j’attends. De façon générale, si vous traînez dans le champ de vision d’un habitant dont l’immeuble requiert un code, il va le composer en cachant ce qu’il tape comme s’il était en caisse de supermarché avec une carte bleue. Le mieux est de ne pas être dans son champ direct, et si possible dans sa diagonale. De cette manière, vous allez le voir taper mais vous serez loin pour voir. Alors, j’enregistre le mouvement de son doigt, et à l’aide de la crasse, je reconstitue le tout (le mouvement ressemble un peu aux pass des téléphones modernes). Ca me prend disons 15 minutes au max (jusqu’à ce qu’une personne entre et se place à peu près comme je l’avais envisagé). Quand j’ai besoin d’entrer la nuit, l’attente est plus longue mais dans une grande ville, pas de problème, ça rentre et ça sort à toute heure.
Puis, d’autres techniques encore, légales et rusées^^ quoi d’en pense Vigik, quand on veut entrer quelque part, on entre. Cordialement,

2
Philippe Peytroux

Je vois Monsieur Paton… vous passez votre temps à faire des recherches pour contrôler le monde, c’est ça ?
On commence par le cerveau humain (manipulation) et on finit par les digicodes ?
Haha, sincèrement, c’est super intéressant ! Et je ne savais pas quoi faire cette aprèm, donc…..

Auteur3

Je suis démasqué !

Merci Phil 😀

4

Oh un article sur un sujet mathématique ! Très bonne idée !!
Je pense que je vais t’envoyer un petit truc qui va te plaire dans la semaine !

Auteur5

Cool, hâte de voir ça 🙂

6

Super intéressant, merci pour cet article !

Auteur7

Merci Bastien !

8

Ahahaha Je me demande si ce n’est pas cet algorithme qu’utilise les hackeurs lorsqu’ils connectent un petit machin dans les systèmes à code et après analyse ils retrouvent le code exacte…

En tout cas, merçi parfait sujet.

Auteur9

Jacks,

Pourquoi pas ! Mais il existe des manières plus sophistiquées d’attaquer un système. L’idée derrière de Bruijn, c’est ce qu’on appelle de la brute-force : on n’a pas beaucoup d’ingéniosité, donc on essaie toutes les solutions jusqu’à trouver la bonne. 🙂

Merci beaucoup pour ton commentaire.

10
antonio de la vega

Génial et passionnant ! Si on voit quelqu’un taper frénétiquement sur un digicode pendant 30 minutes, on pourra dire : “salut Stephane”

11

Si on voit quelqu’un entrain de surveiller pendant 30 min quelqu’un qui tape frénétiquement sur un digicode pendant 30 minutes, on pourra dire : “salut Antonio” , puis on profite de cette occasion pour saluer Stéphane .

Auteur12

Merci Antonio ! 😀

13

Mathématiquement très intéressant mais malheureusement inapplicable dans la réalité car les Digicode possède très souvent un code à 4 chiffres suivi d’un A / B.
Dans ce cas, la suite de Bruijn ne marche pas ! Par contre j’ai déjà réussi à plusieurs reprises l’ouverture d’une porte grâce au touche usé ou salle !

Auteur14

Les suites de De Bruijn fonctionnent avec n’importe quel alphabet. Si tu veux appliquer l’algo sur A = { 0,1,2,3,4,5,6,7,8,9,A,B }, tu peux. Voila d’ailleurs le résultat : https://pastebin.com/Ryp7UTmy

15

Pour un code à 4 chiffres suivi d’un A / B les résultats de ce lien https://pastebin.com/Ryp7UTmy sont mauvais exemple 5827A n’y est pas

merci pour votre article

Auteur16

Mince bien vu :-/ Le générateur que j’ai utilisé n’était sûrement pas terrible. Il faut que j’en trouve un mieux ! Merci pour la remarque !

17

Il manque 9000, 9900 et 9990 dans la série pour les codes de 4 chiffres. Il faut ajouter trois 0 à la fin de la liste pour qu’elle soit bonne.

Il faut donc en moyenne 1h23min27,5s pour ouvrir une porte avec ce type de digicode.

Sauf s’il y a un médecin ou tout autre personne recevant du public dans l’immeuble, à ce moment, c’est 2s le temps d’appuyer sur la sonnette. 😉

Auteur18

Merci beaucoup pour la correction ! 🙂

19

Super article ! Très bien vulgarisé comme d’habitude avec une touche d’humour très appréciable.
Si j’avais su, j’aurais pu éviter de réveiller ma grand-mère à 3h du matin parce que je me trompais de “sens” dans le code (2556 au lieu de 6552…)

Auteur20

Ahah, merci pour ton commentaire.

21

Ah! J’attendais ton article avec impatience, tu avais fait un bon teaser 🙂 , et j’ai adoré.
Quel plaisir de trouver des codes, souvent on peut essayer le numéro du bâtiment avec le numéro de département. Je l’ai déjà vu plusieurs fois dans différents immeubles.
Le système Vigik est cassable, mais demande pas mal d’effort.

Alors, il reste ton idée d’Arduino, j’en ai un dans un tiroir qui ne sert pas! Je vais le dépoussiérer!

Have Fun

Auteur22

Hey Bryk,

Tu me diras si tu arrives à quelque chose ! Merci pour ton commentaire en tous cas.

23

Il serait utile de préciser que cela marche uniquement pour les systèmes ne nécessitant pas de valider le code à chaque fois.

Auteur24

On en discutait sur Slack, et ça dépend beaucoup des villes et probablement de l’année de construction des logements. Dans mon cas, je n’ai jamais rencontré ce type de digicode.