Offre de thèse
Méthodes d'Optimisation pour la Cryptanalyse de Documents Anciens
Date limite de candidature
15-05-2025
Date de début de contrat
01-10-2025
Directeur de thèse
BOUILLAGUET Charles
Encadrement
Co-encadrant (avec HDR) : Charles Bouillaguet https://perso.lip6.fr/Charles.Bouillaguet/ Charles Bouillaguet est maitre de conférence à Sorbonne Université mais nous rejoint dans l'équipe Caramba du Loria en délégation à partir de septembre 2025.PIERRIPIZE
Type de contrat
école doctorale
équipe
CARAMBAcontexte
Le contexte de cette thèse est interdisciplinaire : il s'agit de mettre l'informatique au service des historiens, en les aidant à traiter des milliers de pages restées indéchiffrables dans les archives Européennes. Le cadre de cette thèse s'arrête aux frontières des langues européennes, et ne couvre que les documents et lettres anciens jusqu'au XIX° siècle.spécialité
Informatiquelaboratoire
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Mots clés
cryptographie à clef secrète, optimisation, histoire
Détail de l'offre
Il arrive que, dans un carton d'archives, l'historien butte soudainement sur un document chiffré resté tel qu'il a été envoyé des siècles auparavant. De très nombreux documents historiques demeurent inexploités car incompréhensibles.
Ce premier constat s'est effectué `a la faveur du déchiffrement d'une lettre de 1546 de l'Empereur Charles Quint [3]. Les cryptographes découvrent alors l'existence de milliers de pages historiques non déchiffrées, tandis que les historiens trouvent l'espoir de comprendre les documents qu'ils tenaient pour indéchiffrables, faute d'expertise.
Le premier verrou au déchiffrement se trouve dans la lecture des symboles : en effet les textes sont manuscrits, rarement écrits en alphabet latin, et les algorithmes de cryptanalyse ne peuvent travailler que sur des textes numériques. L'équipe Almanach à Paris travaille en ce moment à adapter des techniques HTR (handwritting text recognition) pour nous permettre d'avoir ces transcriptions.
Une fois la transcription obtenue, la question de cette thèse consiste à établir les bons algorithmes d'attaque sur différents chiffrements anciens.
Compréhension des méthodes de chiffrement. Aussi étonnant que cela puisse paraitre, les techniques d'attaque des protocoles historiques entre le XVI° et le XIX° siècle ne sont pas (ou peu) connues. Une rapide première partie consistera donc à classer les différentes méthodes, par époque, style ou critère (nombre de symboles différents, graphie, quelques statistiques de bases...) pour que la bonne cryptanalyse s'applique.
Cryptanalyse des chiffrements homophoniques. Majoritaire au XVI° et XVII° siècle, le chiffrement homophonique consiste en l'utilisation de plusieurs symboles différents pour chiffrer une même lettre claire. Le nombre de symboles pour chaque permet de brouiller les effets de fréquence. Dès 1550 nous voyons apparaitre des symboles nuls (sans signification) et des symboles annulants (qui annulent un symbole adjacent ou parfois une ligne entière). Des premiers résultats de la communauté [2, 1] pour d'autres chiffrements indiquent que la famille des algorithmes d'escalade (hill-climbing, simulated annealing...) donneraient de bons premiers résultats pour la cryptanalyse. L'idée est d'associer une altitude à chaque clef potentielle, et de se promener sur un paysage en 3 dimension en espérant atteindre le sommet du paysage, qui correspondrait à la clef réelle. La difficulté principale réside dans le choix de la fonction d'altitude, mais également dans la notion de voisinage à parcourir pour une même clef potentielle, car la multiplicité des voisins entraine des trop grandes complexité aussi bien en temps qu'en mémoire.
Cryptanalyse des chiffrements à répertoire. Au XVIII° et XIX° siècle en revanche, les symboles (qui sont des chiffres) ne représentent plus des lettres mais des mots entiers, agissant comme un dictionnaire entre deux langues. Le second axe de cette thèse couvre donc la cryptanalyse de ses chiffrements restés jusqu'ici totalement impénétrables. Les méthodes d'optimisation – comme pour les chiffrements homophoniques – devront s'adapter en passant du niveau des lettres au niveau des mots. Ici encore l'utilisation de calcul intensif sera d'une grande aide : les tailles de clefs que nous trouvons dans ces systèmes font parfois plus de 10 000 bits, à comparer avec
les tailles de clefs actuelles sur RSA (800 bits) que les records mondiaux actuels de calculs parviennent à casser.
Vers une automatisation des déchiffrements. L'objectif final de cette thèse est la création d'un logiciel qui puisse traiter automatiquement les lettres chiffrées : d'abord en orientant les documents vers les bons algorithmes d'attaque, puis en appliquant la cryptanalyse adéquate. Nous disposons `a cet effet d'un jeu de test grandeur nature, issus de demandes que nous avons reçues (cf pdf).
Keywords
private key cryptography, optimisation, history
Subject details
Sometimes, in a box of archives, the historian suddenly comes across an encrypted document that remains just as it was sent centuries ago. Many historical documents remain unexploited because they are incomprehensible. This first observation was made with the decryption of a 1546 letter from Emperor Charles V [3]. Cryptographers then discovered the existence of thousands of undeciphered historical pages, while historians found hope in understanding documents that they had considered indecipherable for lack of expertise. The first obstacle to decipherment lies in reading the symbols: the texts are handwritten, rarely written in the Latin alphabet, and cryptanalysis algorithms can only work on digital texts. The Almanach team in Paris is currently working on adapting HTR (handwriting text recognition) techniques to enable us to obtain these transcriptions. Once the transcription has been obtained, the question for this thesis is to establish the right attack algorithms for different ancient ciphers. Understanding encryption methods. Surprising as it may seem, there is little or nothing known about the techniques used to attack historical protocols between the 16th and 19th centuries. A quick first part will therefore consist of classifying the different methods, by period, style or criterion (number of different symbols, spelling, some basic statistics, etc.) so that the right cryptanalysis can be applied. Cryptanalysis of homophonic ciphers. Homophonic encryption, which was in the majority in the 16th and 17th centuries, consists of using several different symbols to encrypt the same clear letter. The number of symbols for each cipher blurs the effects of frequency. As early as 1550, we saw the appearance of null symbols (meaningless) and cancelling symbols (which cancel out an adjacent symbol or sometimes an entire line). Initial results from the community [2, 1] for other ciphers indicate that the family of hill-climbing algorithms would give good initial results for cryptanalysis. The idea is to associate an altitude with each potential key, and to walk around a 3-dimensional landscape hoping to reach the top of the landscape, which would correspond to the real key. The main difficulty lies in the choice of altitude function, but also in the notion of neighborhoods to be traversed for the same potential key, because the multiplicity of neighbors leads to excessive complexity in terms of both time and memory. Cryptanalysis of directory based ciphers. In the eighteenth and nineteenth centuries, on the other hand, the symbols (which are numbers) no longer represent letters but whole words, acting like a dictionary between two languages. The second part of this thesis therefore covers the cryptanalysis of these ciphers, which until now have remained totally impenetrable. Optimisation methods - as with homophonic ciphers - will have to be adapted by moving from the letter level to the word level. Here again, the use of intensive computing will be of great help: the key sizes we find in these systems are sometimes more than 10,000 bits, compared with current key sizes for RSA (800 bits), which the current world records for computation can break. Towards automated decryption. The final objective of this thesis is to create software that can automatically process encrypted letters: firstly by directing the documents towards the right attack algorithms, and then by applying the appropriate cryptanalysis. To this end, we have a set of full-scale tests, based on requests we have received.
Profil du candidat
Le sujet nécessite des connaissances solides en cryptographie, en algorithmique et une volonté de valider ses idées par des implémentations. Une maitrise du calcul haute performance et de la parallélisation est un avantage.
Il n'y a pas de prérequis indispensable en intelligence artificielle, en histoire et en linguistique, mais toute compétence ou attirance pour ces disciplines est un atout certain pour s'emparer du sujet, et échanger avec les collaborateurs.
Candidate profile
The subject requires a solid knowledge of cryptography and algorithms and a willingness to validate ideas through implementation. Mastery of high-performance computing and parallelization is an advantage.
There are no essential pre-requisites in artificial intelligence, history or linguistics, but any skills or interest in these disciplines will be a definite asset in getting to grips with the subject and sharing ideas with colleagues.
Référence biblio
[1] Eugen Antal. Cryptanalysis of a special polybius-like cipher using hill-climbing. Tatra Mountains Mathematical Publications, 87:25–42, 11 2024.
[2] Luka Bulatovic, Andjela Mijanovi ́c, Nikola Trajkovi c, and Vladimir Bozovic. Automated cryptanal- ysis of substitution cipher using hill climbing with well designed heuristic function. Mathematica Montisnigri, 44:135–143, 01 2019.
[3] Cécile Pierrot, Camille Desenclos, Pierrick Gaudry, and Paul Zimmermann. Deciphering Charles Quint (A diplomatic letter from 1547). In 6th International Conference on Historical Cryptology, HistoCrypt, June 2023.