Dénombrer l’invisible

Certains chiffres entendus sur les médias sont surprenants, surtout quand ils sont donnés sans explication.

Dénombrer les migrants

Aujourd’hui, vous apprenez que, selon le ministère de l’intérieur, il y aurait entre 200000 et 400000 clandestins présents sur le territoire français. D’où viennent ces chiffres ? Le propre des clandestins … est de l’être, et donc d’échapper à tout recensement.

Comment dénombrer ceux qui se cachent ?

La démographie permet cependant d’évaluer leur nombre. Pour commencer, nous connaissons les taux de mortalité par âge et par origine. Nous pouvons estimer que les taux sont environ les mêmes pour les clandestins. Du nombre de décédés sans papiers, nous pouvons donc déduire une approximation du nombre de vivants sans papiers. La même opération est possible grâce aux naissances. Les recensements permettent aussi de se douter de la présence de clandestins, quand les nombres recensés ne correspondent pas aux nombres prévus.

Dénombrer les séropositifs

De même, vous apprenez que 150000 personnes sont porteuses du virus du sida (c’est-à-dire séropositives) en France, dont 40000 l’ignorent. Comment peut-on faire une telle estimation ? S’ils l’ignorent, comment le savons-nous ? Ici encore, l’idée est de faire des recoupements. Sans rentrer dans toute la subtilité des détails, voyons le principe du calcul. Imaginons que nous connaissions le nombre de cas de sida diagnostiqués une certaine année, 500 par exemple. Parmi ceux-ci, 370 correspondent à des personnes dont la séropositivité était connue. Ainsi 130 étaient des séropositifs inconnus les années précédentes. Il est donc légitime d’estimer que pour 370 séropositifs connus, il en existe 130 inconnus. Nous multiplions le nombre de séropositifs connus (110000 par exemple) par le rapport 130 / 370 pour en déduire le nombre de séropositifs inconnus, ce qui donne un peu moins de 40 000. Bien sûr, le modèle est un peu plus raffiné que cela car certains milieux sont plus conscients du danger de cette maladie que d’autres et pratiquent les tests plus volontiers. Les taux entre connus et inconnus diffèrent alors selon le milieu. Dans tous les cas, à défaut d’un vaccin, l’idéal pour enrayer l’épidémie et mieux soigner les malades serait un test annuel pour tous. Ce serait malgré tout coûteux et difficile à mettre en place.

Et Marie Stuart perdit la tête à cause d’un mauvais chiffre …

Ayant été élevée à la cour de France à l’époque d’Henri II, Marie Stuart,qui fut reine d’Écosse et de France, utilisait un chiffre du type de ceux d’Henri II comme le suivant, qu’il avait avec Philibert Babou, ambassadeur à Rome.

Ce chiffre utilisé par Henri II est un chiffre par substitution offrant plusieurs équivalents pour chaque lettre, muni d’un nomenclateur pour les mots courants.

Les chiffres de Marie Stuart

Marie Stuart utilisait plusieurs chiffres, selon ses correspondants. L’examen de celui utilisé dans le complot de 1586, qui se trouve aux archives du Royaume-Uni, montre qu’il est bien du type précédent.

Le chiffre utilisé par Marie Stuart en 1586. On voit clairement qu’il est de même nature que celui de Henri II.

Autrement dit, le chiffre de Marie Stuart était du niveau de ceux des rois de son époque. Elle perdit pourtant la tête de l’avoir utilisé. Un chiffre faible est toujours pire que l’absence de chiffre. Son sort se noua alors qu’elle était prisonnière au château de Chartley au nord de l’Angleterre. Son seul contact avec le monde extérieur était sa correspondance, chiffrée par son secrétaire, Gilbert Curle. Elle la faisait sortir clandestinement, cachée dans des tonneaux de bière.

Espionnage de la correspondance de Marie

La principale faille dans ce scénario était la personne chargée de cette tâche, Gilbert Gifford, un agent double de Francis Walsingham (1530 – 1590), secrétaire d’Élisabeth Ie. Il lui transmit toutes les lettres de Marie, ce qui permit au cryptanalyste de Walsingham, Thomas Phelippes de les décrypter, en utilisant vraisemblablement la méthode du mot probable (c’est-à-dire rechercher la présence de mots qu’on estime probable dans une correspondance, en fonction du destinataire, par exemple « reine », « cousine », etc.). L’abondance des messages lui facilita sans doute la tâche.

Le complot et la manipulation de Walsingham

En 1586, son ancien page, Anthony Babington, qui faisait partie d’un complot contre la reine d’Angleterre, lui écrivit une longue lettre chiffrée où il lui décrivait les détails du complot et demandait son accord. La réponse de Marie scella son destin. Quand Thomas Phelippes l’eut décryptée, il ajouta une potence à la copie qu’il en fit ! Pour que Walsingham obtienne les noms de tous les complices, il ajouta un postscriptum à la lettre demandant les noms de tous les comploteurs. En plus d’être excellent cryptanalyste, Phelippes était un faussaire hors pair ! Ainsi, Babington livra lui-même ses complices. Tous furent exécutés avant le procès de Marie.

La cryptographie et le mouvement : d’un conflit à l’autre

Dès la Grande Guerre, les communications reposaient sur la radio et étaient donc quasi instantanées mais la cryptographie utilisée les ralentissait car elle reposait sur un travail manuel long et pénible. Elle correspondait à une guerre immobile, pas à une guerre de mouvement. Tous les chiffres de cette guerre était fondés sur un mélange de substitutions alphabétiques et de transpositions. De ce temps, le décryptement français était excellent si bien que les messages allemands furent décryptés quasiment tout au long de la guerre.

Le chiffre ADFGX

En 1918, le haut commandement allemand ayant compris que ses chiffres n’étaient guère secrets, décida d’en changer avant le jour de la grande offensive du printemps 1918, rendue possible par sa victoire sur la Russie, et nécessaire par l’arrivée des Américains. Pour une fois, la question fut prise au sérieux et une conférence sur le thème fut organisée à Berlin. Le prix fut remporté par un colonel au nom prédestiné, Fritz Nebel, même si le brouillard qu’il généra ne fut guère épais pour les décrypteurs français, dont l’excellent Georges Painvin. Pour éviter les confusions à la réception, le système de Nebel n’utilisait que cinq lettres, toutes très éloignées en code morse : A, D, F, G et X.

  • A · · D · · · F — — · G · · X

Les messages ne comportant  que ces cinq lettres explique le nom donné à ce chiffre par l’armée française. Ces cinq symboles firent penser à l’utilisation d’un carré de Polybe de côte 5, un carré où on dispose les 25 lettres de l’alphabet (en confondant le I et le J) et où les substitue ensuite par leurs coordonnées. Ce carré constitue la clef d’une substitution alphabétique, clef qui peut être retenue par une phrase.

Carré de Polybe utilisé par le système ADFGX. Ici, il a été construit à partir de la phrase « Geheimschrift der Funker »

Considérons par exemple le message « Attaquez demain à quatre heures ». Pour le chiffrer, nous chiffrons chaque lettre suivant le carré ci-dessus. Ainsi, A est codé FX (ligne et colonne de A dans le carré). Nous obtenons la suite :

FX DX DX FX GX FD AD XX FA AD AX FX AG FF FX GX FD FX DX DF AD AF AD FD DF AD DA

Surchiffrement par transposition

Ce message est alors surchiffré au moyen d’une transposition. Celle-ci est déterminée par un mot clef. Si celui-ci est « nébuleux », nous formons un tableau dont la première ligne est la clef (voir le tableau ci-dessous). La deuxième ligne donne l’ordre des lettres de la clef dans l’ordre alphabétique. Ensuite, nous copions les lettres du message précédent ligne par ligne. Nous complétons la dernière ligne par des nulles choisies arbitrairement parmi les lettres ADFGX.

Seconde étape du chiffrement après substitution mais avant permutation. Celle-ci est toutefois indiquée en seconde ligne.

Nous écrivons alors les colonnes dans l’ordre donné par la seconde ligne du tableau et groupons les lettres par cinq pour obtenir le message chiffré :

DFAFF AAXXA GDDFX DXXXD ADAAF DADFG FAFAD XDDFX FDFXF GDFGX XXXFD X

Attaques allemandes et décryptement de ADFGX

Le système ADFGX fut utilisé à partir du 5 mars 1918. Les messages allemands devinrent alors indécryptables pour les Français. Même s’il était évident que les Allemands allaient attaquer, l’état-major ne savait pas où, et l’offensive du 21 mars fut une surprise. Elle fut suivie par plusieurs offensives qui, progressivement, asséchaient les réserves françaises. Alors qu’au départ, elles étaient échelonnées à l’arrière dans tous les endroits probables d’attaques allemandes, il fallait maintenant choisir où les disposer. Heureusement, le 5 avril, Georges Painvin réussit à décrypter le système. La présence de cinq symboles faisait penser à un carré de Polybe, donc à une substitution suivie d’une transposition mais Georges Painvin avait besoin de la longueur de la seconde clef pour commencer le décryptement. Or, les Allemands étaient devenus méfiants, changeaient leurs clefs tous les jours et limitaient l’usage du nouveau système au niveau stratégique. Les tranchées communiquaient autrement. La chance arriva le 4 avril, quand Painvin reçut deux messages ayant de fortes similarités, qui lui permirent d’accéder à cette longueur (le lecteur intéressé trouvera les détails du décryptement dans mon livre l’univers des codes secrets de l’Antiquité à Internet).

Une « amélioration » catastrophique

Malgré cela, les Allemands réussirent plusieurs attaques par surprise. Paris n’était plus loin et les réserves françaises s’épuisaient. Le 1er juin, les Allemands changèrent à nouveau de code, ajoutant un V aux cinq autres lettres. Georges Painvin comprit immédiatement que le système n’avait pas réellement changé, que le carré de Polybe avait seulement maintenant un côté de six. En tout cela faisait 36 symboles. L’hypothèse naturelle était qu’ils chiffraient ainsi les 26 lettres de l’alphabet plus les dix chiffres. Cette apparente complication fit la perte des Allemands. En effet, ils commençaient leurs messages par leur adresse comme « 15e division d’infanterie » ou « 25e division d’infanterie ». En toutes lettres, cela donnait des messages commençant par « quinze » ou « vingt-cinq », qui différaient énormément. Avec le nouveau système, entre « 15 » et « 25 », seule la première lettre différait.

Deux messages ayant les particularités que nous venons d’étudier furent interceptés le 1er juin. Georges Painvin les décrypta dès le 2. Tous les messages du 1er furent alors décryptés et le lieu de la future offensive allemande se dévoila. Les réserves françaises furent placées exactement où il fallait et ce fut la victoire de Méry, qui changea le cours de la guerre en ce printemps 1918. Les Allemands ne purent plus prendre les Français par surprise, cela essentiellement grâce à un décrypteur de génie, Georges Painvin.

Seconde Guerre mondiale

La cryptographie de la Première Guerre mondiale était inadaptée à une guerre de mouvement, qui exige la rapidité des communications. C’est ainsi que, dès la fin de la Grande Guerre, des machines cryptographiques dont la célèbre Enigma virent le jour. La lutte contre cette machine fera l’objet d’autres articles sur ce blog.

Les suites qui se racontent et le jeu de Robinson

Les suites qui se racontent sont entrées un jour dans ma vie pour ne plus en sortir à travers une énigme mathématique que me posa un ami :

Si une suite commence par 0, 10, 1110, 3110, 132110, 13123110, quel est le nombre suivant ?

Ma réponse fût 23124110 (dans 0, je compte un 0 ce que j’écris 10 ; dans 10, je compte un 1, un 0 ce que j’écris 1110 ; dans 1110, je compte trois 1, un 0 ce qui donne 3110, etc.). En quelque sorte, chaque terme « raconte » le précédent.

L’énigme se transforme en suite … et en conjecture

J’aurais pu m’arrêter là mais, allez savoir pourquoi, je continuais : 1413223110, 1423224110, 2413323110, 1433223110, 1433223110. La suite est donc constante à partir de ce terme. Le résultat me sembla surprenant, c’est pourquoi j’essayais d’autres valeurs initiales. J’avais beau examiner un grand nombre de valeurs, je trouvais toujours une suite périodique, la période étant 1, 2 ou 3. Très vite convaincu de ce résultat, je tentais de prouver ce qui était devenu une conjecture. Après plusieurs mois de recherche, je trouvais 109 points fixes, 31 cycles de période deux et 10 cycles de période trois (voir plus loin leur liste exhaustive). 

Puis la conjecture en théorème

Pour trouver tous les cycles des suites qui se racontent, on peut utiliser un ordinateur à condition de réduire d’abord le nombre de cas à essayer. Il est également possible de faire un raisonnement analytique classique. Pour ceux que le sujet intéresse, j’ai raconté cette quête de la preuve dans :

Hervé Lehning, « Computer-aided or analytic proof? », College Mathematics Journal, vol. 21, no 3,‎ 1990, p. 228-239

Hervé Lehning, « Quelle est la meilleure preuve ? », Quadrature, n° 11, 1992 (Ce dernier article est illustré Par Charb.)

Page de l’article avec l’illustration de Charb

Le jeu de Robinson

Quand j’ai proposé mon article, on me fit remarquer que je résolvais sans le savoir une conjecture de Douglas Hofstadter (parue dans Ma Thémagie) liée à un jeu inventé dans les années soixante-dix par Raphaël Robinson (1911 – 1995), un mathématicien américain. Le but est de remplir les blancs de la phrase suivante afin qu’elle devienne vraie :

Dans cette phrase, il y a __ 0, __ 1, __ 2, __ 3, __ 4, __ 5, __ 6, __ 7, __ 8, et __ 9

On remarque immédiatement que tout point fixe utilisant les dix chiffres d’une suite qui se raconte est solution, et réciproquement. En utilisant la liste des 109 points fixes, on trouve deux solutions :

Dans cette phrase, il y a 1 0, 11 1, 2 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1 8, et 1 9.

Dans cette phrase, il y a 1 0, 7 1, 3 2, 2 3, 1 4, 1 5, 1 6, 2 7, 1 8, et 1 9.

Les autres points fixes fournissent des solutions à un jeu de Robinson légèrement modifié où certains chiffres peuvent être supprimés. Par exemple :

Dans cette phrase, il y a 3 1, 2 2, 3 3, 1 4 et 1 5.

Suppléments : cycles des suites qui se racontent

Pour en simplifier la lecture, je noterai <n> le fait que n chiffres, choisis arbitrairement parmi les chiffres possibles, soient précédés d’un 1.

Liste des points fixes

1 9 / 1 8 / 1 7 / 1 6 / 1 5 / 1 4 / 1 3 / 2 2 / 11 1 / 1 0 et

1 9 / 1 8 / 2 7 / 1 6 / 1 5 / 2 3 / 3 2 / 7 1 / 1 0 ce qui fait 2 points fixes,

11 1 / <8> ce qui fait 9 points fixes, 2 6 / 2 3 / 3 2 / 6 1 / <5> ce qui fait 6 points fixes, 2 5 / 2 3 / 3 2 / 5 1 / <4> ce qui fait 15 points fixes, 2 4 / 2 3 / 3 2 / 4 1 / <3> ce qui fait 20 points fixes, 3 3 / 2 2 / 3 1 / <2> ce qui fait 21 points fixes, 2 3 / 3 2 / 2 1 / <1> ce qui fait 7 points fixes, 3 3 / 3 1 / <2> ce qui fait 28 points fixes, 2 2 ce qui fait 1 point fixe, d’où un total de 109 points fixes.

Liste des cycles de période deux

2 8 / 1 7 /  1 4 / 4 2 / 7 1 / <5>       1 8 / 2 7 / 2 4 / 2 2 / 8 1 / <5> ce qui fait 1 cycle, 

2 7 / 1 6 / 1 4 / 4 2 / 6 1 / <4>                   1 7 / 2 6 / 2 4 / 2 2 / 7 1 / <4> ce qui fait 5 cycles,

2 6 / 1 5 / 1 4 / 4 2 / 5 1 / <3>                   1 6 / 2 5 / 2 4 / 2 2 / 6 1 / <3> ce qui fait 10 cycles,

2 4 / 1 3 / 4 2 / 3 1 / <2>                 2 4 / 2 3 / 2 2 / 4 1 / <2> ce qui fait 15 cycles,

d’où un total de 31 cycles de période 2.

Liste des cycles de période trois

2 5 / 1 4 / 1 3 / 4 2 / 4 1 / <2>     1 5 / 3 4 / 1 3 / 2 2 / 5 1 / <2>      2 5 / 1 4 / 2 3 / 2 2 / 5 1/ <2>

ce qui fait 10 cycles de période 3.