1425.sagews

Blum Blum Shub

L'algorithme de Blum Blum Shub permet de générer des suites pseudo-aléatoires cryptographiquement sûres. C'est-à-dire qu'un attaquant ne peut pas prévoir le prochain nombre $x_{n+1}$ de cette suite en connaissant uniquement les premiers éléments $x_1,\ldots,x_n$.

La définition de cet algorithme est assez simple:

on choisit deux nombres premiers $p$ et $q$ et on considère $N=p*q$.

La clé sera l'élément initial $x_0$ de notre suite que l'on définit par la récurrence $x_{n+1}=x_n^2 \pmod N$.

p=1483; q=1487; N = p*q

exemple de suite générée avec comme clé $17$:

cle = 17; x=[0]*10; x[0] = cle
for i in (1..9):
    x[i] = x[i-1]**2 % N
x

\newcommand{\Bold}[1]{\mathbf{#1}}\left[17, 289, 83521, 643418, 584394, 386629, 1078156, 2061595, 790642, 775294\right]

Pour chiffrer un message, un première étape consiste à transformer une suite de lettres en une suite de chiffres. C'est ce que l'on appelle le codage.

Pour cela, nous allons considérer un alphabet (avec en plus des chiffres, des signes de ponctuation, etc) et chaque caractère sera remplacé par l'entier correspondant à sa position.

alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789,.?! "

def code(message):
    return [alphabet.index(lettre) for lettre in message]

Un exemple:

on remarquera que la première lettre de l'alphabet, ici $a$ est considérée comme étant en position $0$.

code('allo!')

\newcommand{\Bold}[1]{\mathbf{#1}}\left[0, 11, 11, 14, 65\right]

Le passage inverse d'un entier à une lettre est appelé le décodage.

def decode(sequence):
    return ''.join([alphabet[i] for i in sequence])

on vérifie que cela fonctionne bien:

decode([0, 11, 11, 14, 65])

\newcommand{\Bold}[1]{\mathbf{#1}}\hbox{allo!}

Le principe des chiffrements à flots est alors le suivant.

On génére une suite d'entiers de la même taille que notre message à partir de notre clé. Cette suite est appelée suite chiffrante. Le chiffrement du message est alors une simple addition modulo la taille de notre alphabet.

def chiffre_sequence(sequence,cle):
    taille_alphabet = len(alphabet)
    suite_chiffrante = cle
    for position,lettre in enumerate(sequence):
        suite_chiffrante = suite_chiffrante**2 % N         # la recurrence de Blum Blum Shub
        sequence[position] = (lettre+suite_chiffrante)%taille_alphabet
    return sequence

un exemple:

chiffre_sequence([0, 11, 11, 14, 65],17)

\newcommand{\Bold}[1]{\mathbf{#1}}\left[21, 50, 28, 34, 37\right]

Notre alphabet est de taille $67$. On a ici:

• $17^2 = 289 \pmod N$ et $0 + 289 \pmod 67 = 21$
• $289^2 = 83521 \pmod N$ et $11 + 83521 \pmod 67 = 50$
• etc

et en utilisant nos fonction $code$ et $decode$, on peut obtenir un message chiffré dans notre alphabet de départ.

def chiffre(message, cle):
    return decode(chiffre_sequence(code(message),cle))

toujours notre exemple:

chiffre('allo!',cle)

\newcommand{\Bold}[1]{\mathbf{#1}}\hbox{vYCIL}

Pour déchiffrer, il suffit de faire la même chose en remplaçant l'addition par une soustraction.

Ainsi on a, en notant $m$ le message initial, $s$ la suite chiffrante, $c$ le message chiffré et $d$ le message déchiffré:

• $c = m+s \pmod N$
• et $d = c - s \pmod N$
• d'où $d = m+s-s \pmod N = m$

 

def dechiffre_sequence(sequence,cle):
    taille_alphabet = len(alphabet)
    suite_chiffrante = cle
    for position,lettre in enumerate(sequence):
        suite_chiffrante = suite_chiffrante**2 % N
        sequence[position] = (lettre-suite_chiffrante)%taille_alphabet
    return sequence

def dechiffre(message, cle):
    return decode(dechiffre_sequence(code(message),cle))

Si on utilise une clé différente, on ne peut pas lire le message obtenu

dechiffre(chiffre('Bonjour!',19),17)

\newcommand{\Bold}[1]{\mathbf{#1}}\hbox{GWF lIgk}

mais si on utilise la bonne clé on retrouve bien le message d'origine

dechiffre(chiffre('Bonjour!',19),19)

\newcommand{\Bold}[1]{\mathbf{#1}}\hbox{Bonjour!}

Exercice:

déchiffrer le message suivant en utilisant la clé $123$:  'wWAEP5guAZU0QvXx8QzJvXDZTmbcf6SxLPoyo1hany cS?8wVZ'

Conclusion et extensions

Le système de Blum Blum Shub est intéressant car on peut prouver (mais c'est compliqué!) qu'il fourni une bonne sécurité.

Cependant le principe des chiffrement à flots peut être très facilement adapté, il suffit de choisir une autre suite récurrente.

Par exemple, on peut décider d'utiliser $x_{n+1} = x_n + 17 \pmod N$ mais on a alors aucune garantie quant à la sécurité.

Comme on peut s'y attendre, cette suite est en fait trop simple pour résister...

Exercice:

déchiffrer le message suivant chiffré avec ce système faible, sans connaître la clé:  'Irgsvidyridjsmwdfvezsaaa'