Număr prim aleatoriu

În criptografie , un număr prim aleator este înțeles ca un număr prim care conține un număr dat de biți în notație binară , pe algoritmul de generare al căruia sunt impuse anumite restricții. Generarea de numere prime aleatorii este o parte integrantă a procedurilor de derivare a cheilor în mulți algoritmi criptografici, inclusiv RSA și ElGamal .

Datorită faptului că testarea simplității numerelor mari necesită costuri semnificative de timp, cerința pentru simplitatea numărului rezultat este adesea slăbită la o pseudo -simplitate puternică din mai multe motive aleatorii diferite. Algoritmii puternici de testare a pseudosimplicității existenți sunt cu ordine de mărime mai rapid decât cei mai cunoscuți algoritmi de testare a primalității. În același timp, numerele care trec cu succes testul de pseudosimplitate puternică pe mai multe baze aleatoare sunt prime cu o probabilitate mare, iar această probabilitate crește odată cu numărul de baze pe care se efectuează testul.

Cerințe pentru algoritm și implementarea acestuia

Cerințele pentru algoritmi pentru generarea numerelor prime aleatoare se reduc la următoarele două:

Algoritmi tipici pentru generarea numerelor prime aleatoare

Peste tot mai jos se presupune că se utilizează un PRNG criptografic puternic inițializat cu o cheie secretă (detaliile depind de PRNG-ul utilizat și de modul în care este obținută și prezentată cheia).

Testarea simplității

Puteți verifica prima (probabilă) a unui număr p care conține k biți astfel:

  1. Asigurați-vă că p nu este divizibil cu numere prime mici 3, 5, 7, 11 etc. până la o limită mică (de ex. 256). O astfel de verificare vă permite să tăiați în mod eficient o mulțime de numere evident compuse înainte de a le verifica cu algoritmi care consumă mai mult timp. Deci, verificarea faptului că p este divizibil cu numerele prime 2, 3, 5 și 7 filtrează toate numerele pare și 54% din numerele impare, verificând că p este divizibil cu toate numerele prime până la 100 filtrează 76% din numerele impare. , iar verificarea faptului că p este divizibil cu toate numerele prime până la 256 elimină 80% din numerele impare.
  2. Rulați testul Miller-Rabin cu cel puțin k runde .

Dacă numărul p eșuează cel puțin o verificare, nu este prim. În caz contrar, cu mare probabilitate (în funcție de numărul de runde) numărul p este prim.

Construcție directă

  1. Generați biți aleatori și compuneți-i într-un număr de k - biți p cu bitul cel mai semnificativ egal cu 1.
  2. Măriți p cu 1 și verificați dacă este prim. Repetați acest pas până când se găsește un număr prim.

Al doilea pas poate fi accelerat dacă luăm în considerare numai numere impare sau numere comparabile cu 1 și 5 modulo 6 etc.

( n - 1)-metode

Metodele de construcție ( n -1)-primă utilizează cunoștințele divizorilor primi ai lui n -1 pentru a testa dacă n este prim folosind testul de primalitate Lucas . [unu]

Un reprezentant tipic al acestei clase de metode este descris în cartea „Introduction to Cryptography” editată de V. V. Yashchenko. [2]

Generarea numerelor prim Sophie Germain

Primele Sophie Germain  sunt prime p astfel încât 2p + 1 este de asemenea prim.

Note

  1. ↑ Cheryomushkin A.V. Prelegeri despre algoritmi aritmetici în criptografie. - M. : MTSNMO , 2002. - 104 p. — ISBN 5-94057-060-7 .
  2. ↑ Yu. V. Nesterenko. Capitolul 4.5. Cum se construiesc numere prime mari // Introducere în criptografie / Ed. V. V. Iascenko. - Petru, 2001. - 288 p. - ISBN 5-318-00443-1 . Copie arhivată (link indisponibil) . Data accesului: 18 februarie 2008. Arhivat din original la 25 februarie 2008.