Problème d'arithmétique modulaire

Edit: On peut en fait faire beaucoup plus simple, cf mon message suivant.

Yup, my bad. C'est une des deux erreurs de mon message, j'en ai vu une autre (mais j'ai vraiment galéré pour la trouver, c'était fourbe) : quand je mets $d + kp$ au carré, je disais que $d^2 \equiv c \bmod{p^2}$, ce qui n'est pas vrai (c'est vrai mod $p$).

Du coup, je propose une meilleure solution, qui marche cette fois. Sauf quand $c < p$, mais je propose une pirouette pour retomber sur nos pattes. Ça reprend les mêmes idées, mais sans les erreurs.

Théorie

Grosso modo, l'idée est de repartir de $m \equiv \pm \sqrt c \bmod p$, mais de replacer cette racine dans le cercle principal (ie, $[0, p[$). Ça nous donne une nouvelle info qu'on peut exploiter.

Cas où $c \geq p$

Attention, j'ai un peu changé les notations depuis la dernière fois.

On a $c \equiv m^2 \bmod{p^2}$, donc nécessairement $m^2 \equiv c \bmod p$. On pose $c' = c \pmod p$, naturellement $m^2 \equiv c' \bmod p$. On pose $d$ tel que $dp = c - c'$.

On pose $r_i$ les deux racines carrées de $r$ dans $\mathbb Z / p\mathbb Z$, donc $0 \leq r_1, r_2 < p$.

Si $m \equiv r_i \bmod p$, alors $\exists k_i \in \mathbb Z, m = r_i + k_ip $.

On cherche à déterminer ce $k_i$.

Remarque : on sait que $r_i^2 \equiv c' \bmod p$, donc $\exists l_i \in \mathbb Z, r_i^2 = c' + l_ip$. C'est vrai dans $\mathbb Z$, c'est donc vrai modulo $p^2$. Par ailleurs, on connaît c', on vient de calculer $r_i$ donc on connaît $l_i$.

Seconde remarque : sauf si $r_i = 0$, $2r_i$ est inversible dans $\mathbb Z / p\mathbb Z$ (d'inverse $(2r_i)^{p-2}$). De plus, $r_i = 0$ ssi $c = 0$ ce qui est un cas merdique¹.

On a maintenant tous les outils qu'il nous faut. C'est parti.

De plus, on a les inégalités suivantes :

Donc nécessairement, $k_i>0$ sinon $m = r_i + k_ip < 0$ (pour rappel, r_i est positif). De même, $k_i < p$, sinon $m = r_i + k_ip \geq p^2$. Ce qui veut dire qu'en fait, $k_i = (d-l_i) \times (2r_i)^{-1} \pmod p$.

Donc $k_i$ est déterminé de façon unique, donc il y a deux solutions à l'équation :
$m_1 = r_1 + k_1p$ et $m_2 = r_2 + k_2p$. $m$ est nécessairement l'une de ces deux valeurs.

Cas où $c < p$

Comme je disais, dans ce cas-là ça ne va plus marcher, vu que $d = l = 0$ on se retrouve avec $k = 0$, et $m = r$. Cela arrive avec une probabilité de $1/p$ environ, ce qui est assez faible. Mais bon, je suis perfectionniste (de temps en temps).

Pour un entier $n < p^2$ judicieusement choisi, alors en multipliant $c$ par $n^2$, il y a de fortes chances que le produit soit supérieur à $p$, ie $n^2c \geq p$. Sinon, on change de n (m'enfin $p+1$ me semble être une valeur sûre).

On se retrouve ainsi avec un nouveau système à résoudre. Si on pose $cc = n^2c \pmod{p^2}$, et $mm = nm$, alors on s'aperçoit que $cc = mm^2 \bmod{p^2}$, donc on casse ce chiffré, on en déduit $mm$, et en divisant par $p+1$ dans $\mathbb Z / p^2\mathbb Z$ ($ p+1$ y est bien inversible), on en déduit $m$.

Pratique

(Je ne fais que redire la conclusion juste au-dessus, en concentrant toutes les étapes au même endroit de ce message).

Soit $N = p^2$, et $m$ un message. On dispose de $c = m^2 \pmod{p^2}$ son chiffré. On ne lance cette attaque que si $c \geq p$.

On calcule $c' = c \pmod p$, ainsi que $0 \leq r_i < p$ tel que $r_i^2 \equiv c' \bmod p$ (la racine se calcule avec une méthode au choix). On calcule $l_i = (r_i^2 - c')/p$, $d = (c - c')/p$, et $k_i = d \times (2r_i)^{p-2} \pmod p$.

Le message vaut donc $m = r_1 + k_1p$ ou $m = r_2 + k_2p$.

Exemple

(Cette fois-ci, je teste !)

• On pose $p = 7$, $m = 18$.

On a $c = 30$, $c' = 2$, $d = 4$, $r_1 = 3$ et $r_2 = 4$, donc $l_1 = 1, l_2 = 2$, et donc $k_1 = 4$, $k_2 = 2$.

Donc $m = 3 + 4\times 7 = 31$ ou $m = 4 + 2\times 7 = 18$, on retrouve bien notre antécédent de 18.

• On pose $p = 7, m = 10$.

On a $c = 2 < 7$. On pose $n = 8$, $cc = 2 \times 64 \pmod{49} = 30$. On calcule $mm$ tel que $mm^2 \equiv 30 \bmod{p^2}$, ce qui par une curieuse coïncidence est l'exemple donné juste avant. On en déduit que $mm = 18$ ou $mm = 31$.

L'inverse de $8$ modulo $49$ est $43$, donc $m = 18\times 43 \pmod{49} = 39$ ou $m = 31 \times 43 \pmod{49} = 10$. Bingo !

J'ai aussi codé un petit truc en Python histoire d'être bien sûr que je n'avais plus d'erreurs, si vous voulez jouer avec :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

p = 7  # Le nombre premier qu'on utilise

def sqrt_m(n, mod):
   s = []
   for i in range(mod):
       if (i * i) % mod == n:
           s.append(i)

   return s


def invert_m(n, mod):
   for i in range(mod):
       if i*n % mod == 1:
           return i


def encrypt(m, p):
   return (m**2) % (p**2)


def decrypt(c, p):
   if c == 0:
       raise ValueError

   c_p = c % p
   if c_p == c:
       rand = p+1
       new_c = rand**2 * c
       return map(lambda x: (x * invert_m(p+1, p**2)) % (p**2), (decrypt(new_c, p)))

   d = (c - c_p)/p
   r_1, r_2 = sqrt_m(c_p, p)

   l_1 = (r_1**2 - c_p) / p
   l_2 = (r_2**2 - c_p) / p

   i_1 = invert_m((2 * r_1) % p, p)
   i_2 = invert_m((2 * r_2) % p, p)

   k_1 = ((d - l_1) * i_1) % p
   k_2 = ((d - l_2) * i_2) % p

   return [r_1 + k_1*p, r_2 + k_2*p]

error_counter = 0
for i in range(p**2): 
   try: 
       assert i in decrypt(encrypt(i, p), p)
   except AssertionError:
       print 'AssertionError', i
       error_counter += 1
   except ValueError:
       # Valeurs pour lesquelles c = 0, qui ne sont pas facilement resolubles
       pass

print 'Done with {} errors'.format(error_counter)

1
2

Done with 0 errors
[Finished in 0.1s]

Edit : à quand le prévisualiseur $\LaTeX$ ? Accessoirement, je n'arrive pas à aligner mes équations comme il faut, si quelqu'un sait comment faire qu'il me le signale.