email Admissions
en
Menu
email

Maths for Security

Teaching goals

En mathématiques : Connaitre les algorithmes d’arithmétique multiprécision et leur classe de complexité (addition, soustraction, multiplication, réduction, carré, inversion, exponentiation). Étant donné un algorithme opérant sur des entiers multiprécisions, en donner sa complexité.

En programmation C : savoir utiliser gitlab (principes de base du versionnement de fichier) à plusieurs, organiser un module de code C (fichiers en-tête, fichiers source, tests), Makefile, tester, débugger, gérer les dates limites de rendu.

Course description

Le cours sur 8 semaines décrit l’arithmétique modulaire des entiers multiprécision qui sont des entiers dont la taille dépasse la précision des types de base supportés par un processeur (couramment 64 bits). L’arithmétique multiprécision est nécessaire en cryptographie asymétrique, et des bibliothèques dédiées implémentant ces calculs sont utilisées dans d’autres cours (BC en M1, BCS en M2 notamment). Le but de ce cours est d’expérimenter les opérations multiprécision, de comprendre les structures utilisées, et de découvrir les classes de complexité associées à différents algorithmes (par exemple addition, multiplication, inversion modulaire, exponentiation modulaire). Les TPs en langage C permettent d’obtenir au 8e TP une implémentation complète d’un chiffrement et déchiffrement RSA de taille cryptographique (jusqu’à 2048 bits).

La programmation en C se fait dans le cadre « C pour l’embarqué », autrement dit la mémoire est allouée à la compilation. Un soin particulier est apporté aux tests : tests unitaires, vecteurs de tests, tests des cas limites.

Course content

  • Les types de base en C, les opérations de base, la représentation des mots-machine
  • Structure en C pour la multiprécision
  • Utilisation de la multiprécision en cryptographie
  • Schéma de chiffrement et déchiffrement RSA en cryptographie et opérations modulaires
  • Algorithmes d’arithmétique multi-précision (addition, soustraction, négation, multiplication, pgcd avec algorithme d’Euclide, identité de Bézout avec Euclide étendu)
  • Algorithmes d’arithmétique modulaire multi-précision (réduction modulaire, multiplication schoolbook, Karatsuba, Montgomery, exponentiation binaire, inversion modulaire)
  • Conversions d’affichage entre hexadécimal et décimal en multi-précision
  • Classes de complexité
  • Sécurité mathématique de RSA : difficulté de la factorisation des grands entiers
  • Nombres premiers, densité, test de composition probabiliste : Miller-Rabin pour générer des clés RSA

Prerequisites

Notions qui sont abordées en première année de licence d’informatique ou de mathématiques : Avoir des notions d’arithmétique entière et arithmétique modulaire (pgcd, réduction modulaire), avoir des notions de codage de l’information et d’architecture des ordinateurs (octet, notation hexadécimale…), connaitre dans un langage de programmation les types de base : entiers, entiers non signés, les opérations de base : +, -, *, /, %, et les structures de base comme les tableaux.

Se remémorer le cours de théorie de l’information de L1 (TIC) par exemple.

Aucun prérequis spécifique en programmation n’est demandé, cependant les étudiants doivent suivre conjointement le cours LLP (Low Level Programming, 5 ECTS) et connaître un minimum le terminal unix.

Bibliography

Pour la programmation en langage C :

Pour l’arithmétique modulaire multi-précision :

 

Biography

Aurore Guillevic has been a research scientist at Inria Nancy since 2016 and Rennes since 2024 (CAPSULE group), specialised in asymmetric cryptography, elliptic curves, and record computations.
She was a PhD student at the Laboratoire Chiffre, Thales Communications, in 2010-2013, where she took part in the development of the company’s multi-precision library LibCryptoLCH in C language.
She was adjunct assistant professor at École Polytechnique in 2017-2020 and visiting professor at Aarhus University (Denmark) in 2021-2022.