Voi presupune că tipicul Paillier a creat asta $n=pq$ cu $p$ și $q$ numere prime $(p-1)\nu\!| q$ si invers.
Recuperarea unui logaritm discret $x$ a unui element general $a$ față de un generator este echivalent cu recuperarea a trei valori:
$$x\equiv\cases{x_\lambda\pmod{\lambda(n)}\ x_p\pmod p\ x_q\pmod q}.$$
Dacă cineva cunoaște valorile $p$ și $q$ atunci $x_p$ și $x_q$ sunt ușor de recuperat folosind coeficienti Fermat sau $p$-versiune adic a seriei Taylor logaritmice. Cele mai cunoscute metode de recuperare $x_\lambda$ bazați-vă pe sita câmpului numeric și pentru dimensionat criptografic* $p$ și $q$, acest lucru ar trebui să fie imposibil. Dacă se alege un generator astfel încât ordinea generatorului să se împartă $n$, aceasta înseamnă că $x_\lambda$ pot fi ignorate, iar logaritmii discreti cu privire la acest generator pot fi calculați cu ușurință de către oricine știe $p$ și $q$.
În primul tău caz în care $n$ împarte ordinea de $g$, asta ne spune doar asta $x_p$ și $x_q$ nu poate fi ignorat. Nu asigură asta $x_\lambda$ poate fi ignorată și, prin urmare, problema noastră ar putea fi încă insolubilă.
În al doilea caz în care $n$ nu împarte ordinea de $r$ asta ne spune că fie $x_p$ poate fi ignorat sau $x_q$ poate fi ignorat (posibil ambele pot fi ignorate). Nu asigură asta $x_\lambda$ poate fi ignorată și problema noastră ar putea fi încă insolubilă.
În general:
- dacă $p$ nu împarte ordinea generatorului, atunci $x_p$ poate fi ignorat,
- dacă $q$ nu împarte ordinea generatorului, atunci $x_q$ poate fi ignorat,
- dacă $\lambda(n)$ nu împarte ordinea generatorului, atunci $x_\lambda$ poate fi luată ignorată.
De asemenea, rețineți că, dacă se întâmplă să cunoaștem o limită a mărimii $x$, atunci este posibil să nu fie necesară recuperarea tuturor celor trei componente. de exemplu. daca stim asta $x<pq$ apoi recuperarea $x_p$ și $x_q$ ne permite să ne recuperăm în mod unic $x$ din teorema chineză a restului.
*- Rețineți că $p$ și $q$ trebuie să fie mai mari module decât pot fi atacați cu sita câmpului numeric, mai degrabă decât pur și simplu $n$ fiind un modul mai mare decât poate fi atacat cu sita câmpului numeric.
