Problème d'arithmétique modulaire

L'auteur de ce sujet a trouvé une solution à son problème.
Staff
Auteur du sujet

Bonsoir,

Pour un challenge, je souhaite déchiffrer un flag chiffrer dans le cryptosystème de Rabin.

Soit $m$ un entier qui est le flag en clair, soit $c$ sont chiffré, et $N$ un produit de deux nombres premiers.

Alors je sais que

$c\equiv m^2 \pmod N$

Le système se repose sur le fait, comme pour RSA, qu'il est difficile de factoriser un grand nombre entier.

Dans mon cas cependant, je connais la valeur de $c$, et je sais aussi que $N=P*P$ avec $P$ premier. Ma question c'est comment je peux retrouver $m$ ?

La solution proposée sur wikipédia utilise le théorème des restes chinois qui ne fonctionne que si $N=P*Q$ et $P\neq Q$. Les algorithmes qui permettent de calculer des résidus quadratiques fonctionnent seulement si le modulo est un nombre premier.

Cependant, même si on a l'implication

$a \equiv b \pmod {P^2} \Rightarrow a \equiv b \pmod P$

la réciproque est fausse ce qui n'aide pas. Du coup je suis un peu à court d'idées. Est-ce quelqu'un aurait une piste pour mon problème ?

Merci d'avance,

Bonne soirée =)

Édité par Saroupille

+0 -0

N'as tu pas moyen de calculer P ?

Il est difficile de calculer la decomposition en facteur premier mais quand on connais sa forme, cela revient à un simple calcul non ?

ache.one                                                                                   🦊

+0 -0

Crypto <3

J'ai fait quelques calculs sur une feuille, mais je n'ai pas le temps de bien vérifier.

Tu as $m^2 \equiv c \bmod{p^2}$, donc $m^2 \equiv c \bmod p$. Tu calcules la racine carrée avec la méthode de ton choix ($m \equiv d = \pm c^{\frac{p+1}4} \bmod p$ si p est congru à 3 mod 4), et tu obtiens $m \equiv d \bmod p$, ie $m = d + kp$, avec k borné vu que m < p^2 . On pourrait bruteforcer sur tous les k, mais je suis moyen convaincu. Donc on continue.

Donc $c \equiv m^2 \equiv (d + kp)^2 \equiv d^2 \pm 2dkp \bmod{p^2}$. Et d^2 = c, donc $2dkp = 0 \bmod p$, donc p divise 2dk, or p ne divise ni 2 ni d (car d est défini mod p), donc p divise k.

Normalement, ça devrait complètement restreindre les k possibles, puisque m < p^2 . Tu devrais donc te retrouver avec un nombre d'antécédents tout à fait raisonnable.

Édité par melepe

+0 -0
Staff
Auteur du sujet

Crypto <3

J'ai fait quelques calculs sur une feuille, mais je n'ai pas le temps de bien vérifier.

Tu as $m^2 \equiv c \bmod{p^2}$, donc $m^2 \equiv c \bmod p$. Tu calcules la racine carrée avec la méthode de ton choix ($m \equiv d = \pm c^{\frac{p+1}4} \bmod p$ si p est congru à 3 mod 4), et tu obtiens $m \equiv d \bmod p$, ie $m = d + kp$, avec k borné vu que m < p^2 .

J'ai obtenu un m tel que $c\equiv m \pmod p$. Je suppose que c'est bon jusqu'ici.

On pourrait bruteforcer sur tous les k, mais je suis moyen convaincu. Donc on continue.

Donc $c \equiv m^2 \equiv (d + kp)^2 \equiv d^2 \pm 2dkp \bmod{p^2}$. Et d^2 = c, donc $2dkp = 0 \bmod p$, donc p divise 2dk, or p ne divise ni 2 ni d (car d est défini mod p), donc p divise k.

Normalement, ça devrait complètement restreindre les k possibles, puisque m < p^2 . Tu devrais donc te retrouver avec un nombre d'antécédents tout à fait raisonnable.

melepe

Si $p$ divise $k$, et que $k=p$ alors $m = d + p \times p$, du coup tu as $m> p*p$ non ? Du coup ça voudrait dire que $k=0$. Il y a un truc qui ne va pas dans mon raisonnement…

+0 -0

Cette réponse a aidé l'auteur du sujet

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 merdique1.

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

$$\begin{align*} \mbox{On sait que}\quad & m^2 &\equiv & r_i^2 + 2 k_ipr_i & \bmod{p^2} \\ \mbox{Donc}\quad & c& \equiv & c' + l_ip + 2 k_ipr_i & \bmod{p^2} \\ & c-c'&\equiv & l_ip + 2 k_ipr_i & \bmod{p^2} \\ \mbox{Or } c-c' = dp \mbox{ donc}\quad& dp & \equiv & l_ip + 2 k_ipr_i & \bmod{p^2} \\ \mbox{En divisant par } p \quad& d - l_i &\equiv & 2 k_ir_i & \bmod{p} \\ \mbox{Donc}\quad & k_i &\equiv & (d-l_i) \times (2r_i)^{-1} & \bmod p \end{align*} $$

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

$$\begin{cases} m = r_i + k_ip \\ 0 \leq m < p^2 \\ 0 \leq r_i < p\end{cases}$$

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$ ? :D Accessoirement, je n'arrive pas à aligner mes équations comme il faut, si quelqu'un sait comment faire qu'il me le signale. :)


  1. Plus précisément, $c = 0 \Leftrightarrow p \mid m$. Donc le chiffré $0$ admet exactement $p$ antécédents, ce qui fait potentiellement beaucoup. 

Édité par melepe

+2 -0

J'ai réfléchi à nouveau au problème en rentrant chez moi ce soir, parce que je trouvais ma réponse horriblement compliquée pour un problème qui ne l'est pas.

Et de fait, je me suis aperçu que la solution était beaucoup plus simple. :euh: Remettre dans le cercle principal, en fait c'est du pipeau, et j'essaie de me souvenir pourquoi ça m'avait paru une bonne idée (spoiler : j'ai pas trouvé).

Bref, en fait on a $m^2 \equiv c \bmod p$, donc pour $r_i$ une racine de $c$ tq $m = r_i \bmod p$, alors $m = r_i + k_ip$ et $m^2 \equiv r_i^2 + 2k_ipr_i \bmod{p^2}$, or $r_i^2 = c + lp$ donc finalement $k_i$ doit satisfaire $k_i \equiv -l_i \times (2r_i)^{-1} \bmod p$. On garde les contraintes que $k_i \in [0, p[$, donc finalement $k_i = -l_i \times (2r_i)^{-1} \pmod p$.

Et voilà. :D

Donc la méthode simple est de calculer les racines $r_i$ de $c$ mod $p$, de calculer $l_i = (r_i^2 - c)/p$, d'en déduire $k_i$ puis de donner les deux antécédents : $m_i = r_i + k_i p$.

Même pas besoin de se compliquer la vie quand $c$ a des valeurs spéciales les vendredis de pleine lune (enfin, si $c = 0$ on a quand même le cas merdique avec $p$ antécédents).

Le code python de déchiffrement devient alors :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def decrypt(c, p):
    if c == 0:
        raise ValueError

    r_1, r_2 = sqrt_m(c, p)

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

    k_1 = (-l_1 * invert_m(2 * r_1, p)) % p
    k_2 = (-l_2 * invert_m(2 * r_2, p)) % p

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

Désolé pour la première solution complètement folle.

Édité par melepe

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte