M01 - Arithmétique et chiffrement affine

Objectif

Diviseurs, PGCD (Euclide), congruences modulo n, puis chiffrer et déchiffrer avec un chiffrement affine (clé valide, inverse modulaire). Ta fiche de révision : fiche_revision_maths_bts_sio.

---

1. Division euclidienne et diviseurs

Pour deux entiers $a$ et $b>0$, il existe un unique couple $(q,r)$ tel que : $a=b\times q+r\text{avec}0\le r<b$ $q$ = quotient, $r$ = reste. Si $r=0$, $b$ divise $a$ (noté $b\mid a$).

Décomposition en facteurs premiers : on divise par 2, 3, 5, 7… tant que c’est possible. $168=2^3\times 3\times 7$ → diviseurs par paires : 1·168, 2·84, 3·56, 4·42, 6·28, 7·24, 8·21, 12·14.

Un nombre est premier s'il n'est divisible par aucun premier $p$ tel que $p^2\le n$. Ex. 37 : non divisible par 2, 3, 5 (et $7^2=49>37$) → premier.

2. PGCD et algorithme d’Euclide

$\text{pgcd}(a,b)=\text{pgcd}(b,r)\text{ouˋ }r\text{ est le reste de }a÷b$ On recommence jusqu’à un reste nul : le dernier reste non nul est le PGCD.

Étape	Division	Reste
1	$592=104\times 5+72$	72
2	$104=72\times 1+32$	32
3	$72=32\times 2+8$	8
4	$32=8\times 4+0$	0 → stop

$\text{pgcd}(592,104)=8$. Deux nombres sont premiers entre eux si leur PGCD vaut 1.

3. Congruences

$a\equiv r[n]⟺n\text{ divise }(a-r)⟺a\text{ et }r\text{ ont le meˆme reste dans la division par }n$

• $1453=26\times 55+23\Rightarrow 1453\equiv 23[26]$
• Négatif : $-178÷26\approx -6,85$ → on prend $q=-7$ (arrondi vers le bas) → $r=-178+182=4$ → $-178\equiv 4[26]$

Propriétés : on peut additionner et multiplier des congruences de même modulo. Ex. $27\equiv 1[26]$ donc $27^{100}\equiv 1[26]$.

---

4. Le chiffrement affine

flowchart LR
  L["Lettre claire<br/>ex. B"] -->|"rang x<br/>A=0 … Z=25"| X["x = 1"]
  X -->|"y = (a·x + b) mod 26"| Y["y = 18"]
  Y -->|"lettre de rang y"| C["Lettre chiffrée<br/>S"]
  C -.->|"x = a⁻¹·(y − b) mod 26"| L

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

$\text{Chiffrement : }y\equiv ax+b[26]\text{Deˊchiffrement : }x\equiv a^{-1}(y-b)[26]$

Clé valide

La clé $(a,b)$ n’est utilisable que si $\text{pgcd}(a,26)=1$ (sinon deux lettres différentes donnent la même lettre chiffrée → impossible de déchiffrer). Valeurs possibles de $a$ : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 (12 valeurs) ; $b$ : 0 à 25 → 312 clés seulement → cassable par force brute.

L’inverse modulaire $a^{-1}$

On cherche $i$ tel que $a\times i\equiv 1[26]$, c’est-à-dire $a\times i=26k+1$.

$a$	1	3	5	7	9	11	15	17	19	21	23	25
$a^{-1}$	1	9	21	15	3	19	7	23	11	5	17	25

Méthode : tester $a\times 1,a\times 2,\dots$ jusqu’à tomber sur un multiple de 26 plus 1 (ex. $5\times 21=105=4\times 26+1$), ou Euclide étendu (le script le fait).

---

5. Exercices corrigés

Ex. 1 - Chiffrer « BONJOUR » avec la clé (5, 13).

Correction

Lettre	B	O	N	J	O	U	R
$x$	1	14	13	9	14	20	17
$5x+13$	18	83	78	58	83	113	98
mod 26	18	5	0	6	5	9	20
Chiffré	S	F	A	G	F	J	U
Résultat : SFAGFJU.

Erreur dans la fiche de révision

Le tableau « BONJOUR → STIITHI » de fiche_revision_maths_bts_sio est faux à partir de la 2e lettre (ex. O : $5\times 14+13=83\equiv 5[26]$ → F, pas T). Le bon résultat est SFAGFJU (vérifié avec le script). Le déchiffrement « PDZ → QYS » de la fiche est, lui, correct.

Ex. 2 - Déchiffrer « PDZ » avec la clé (5, 13).

Correction

$5^{-1}=21$ → $x\equiv 21(y-13)\equiv 21y-273\equiv 21y+13[26]$ P (15) → $21\times 15+13=328\equiv 16$ → Q ; D (3) → $76\equiv 24$ → Y ; Z (25) → $538\equiv 18$ → S. Résultat : QYS.

Ex. 3 - La clé (13, 4) est-elle valide ?

Correction

$\text{pgcd}(13,26)=13\ne 1$ → non. Ex. A (0) et C (2) donnent tous deux $4$ et $30\equiv 4$ → E. Impossible de déchiffrer.

Ex. 4 - Clé (7, 10) : chiffrer « DON » puis donner la fonction de déchiffrement.

Correction

D (3) → 31 ≡ 5 → F ; O (14) → 108 ≡ 4 → E ; N (13) → 101 ≡ 23 → X : FEX. $7^{-1}=15$ → $x\equiv 15(y-10)=15y-150\equiv 15y+6[26]$ (car $-150+156=6$).

6. Scripts

scripts/maths/euclide_et_inverse.py - PGCD avec étapes, facteurs premiers, modulo, inverse :

python3 euclide_et_inverse.py pgcd 592 104
python3 euclide_et_inverse.py modulo -178 26
python3 euclide_et_inverse.py inverse 7 26
python3 euclide_et_inverse.py table 26

scripts/maths/chiffrement_affine.py - chiffrer, déchiffrer, détail étape par étape, casser par force brute :

python3 chiffrement_affine.py detail 5 13 "BONJOUR"
python3 chiffrement_affine.py dechiffrer 5 13 "PDZ"
python3 chiffrement_affine.py casser "SFAGFJU" | grep BONJOUR

#!/usr/bin/env python3
"""Chiffrement affine y = (a·x + b) mod 26 — version courte (le fichier complet a plus d'options)."""
import math
 
ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 
 
def inverse_modulaire(a: int, n: int = 26) -> int:
    ancien_r, r = a % n, n
    ancien_u, u = 1, 0
    while r != 0:
        quotient = ancien_r // r
        ancien_r, r = r, ancien_r - quotient * r
        ancien_u, u = u, ancien_u - quotient * u
    if ancien_r != 1:
        raise ValueError(f"Clé invalide : pgcd({a}, {n}) ≠ 1")
    return ancien_u % n
 
 
def chiffrer(texte: str, a: int, b: int) -> str:
    assert math.gcd(a, 26) == 1, "pgcd(a, 26) doit valoir 1"
    return "".join(ALPHABET[(a * ALPHABET.index(c) + b) % 26] if c in ALPHABET else c
                   for c in texte.upper())
 
 
def dechiffrer(texte: str, a: int, b: int) -> str:
    a_inverse = inverse_modulaire(a)
    return "".join(ALPHABET[(a_inverse * (ALPHABET.index(c) - b)) % 26] if c in ALPHABET else c
                   for c in texte.upper())
 
 
print(chiffrer("BONJOUR", 5, 13))     # SFAGFJU
print(dechiffrer("SFAGFJU", 5, 13))   # BONJOUR

Lien avec l’informatique

Le chiffrement affine est un chiffrement par substitution : historique, trivial à casser (312 clés, analyse de fréquences). Mais les mêmes outils (arithmétique modulaire, inverse modulaire, PGCD) sont au cœur de RSA et de la cryptographie moderne → P09 - Cybersécurité (RGPD, ANSSI, PKI).

Voir aussi

• M02 - Numération (binaire, hexa) · M03 - Logique booléenne et Karnaugh
• Retour : 00 - Index général