Náhodné prvočíslo

V kryptografii je náhodné prvočíslo chápáno jako prvočíslo obsahující daný počet bitů v binárním zápisu , na jehož generační algoritmus jsou uvalena určitá omezení. Generování náhodných prvočísel je nedílnou součástí postupů odvozování klíčů v mnoha kryptografických algoritmech, včetně RSA a ElGamal .

Vzhledem k tomu, že testování jednoduchosti velkých čísel vyžaduje značné časové náklady, je požadavek na jednoduchost výsledného čísla často z několika různých náhodných důvodů oslaben na silnou pseudojednoduchost. Existující silné algoritmy testování pseudojednoduchosti jsou řádově rychlejší než nejznámější algoritmy testování primality. Přitom čísla, která úspěšně projdou testem silné pseudojednoduchosti na několika náhodných základech, jsou s vysokou pravděpodobností prvočísla a tato pravděpodobnost roste s počtem základen, na kterých se test provádí.

Požadavky na algoritmus a jeho implementaci

Požadavky na algoritmy pro generování náhodných prvočísel se scvrkají na následující dva:

• Distribuce výsledných prvočísel by měla být téměř rovnoměrná na množině všech k - bitových prvočísel. Existuje několik způsobů, jak zajistit splnění tohoto požadavku.
• Proces generování určitého náhodného prvočísla nelze reprodukovat, i když známe podrobnosti o algoritmu a jeho implementaci. Tento požadavek je obvykle splněn použitím zabezpečeného PRNG inicializovaného nějakým klíčem získaným zvenčí (to znamená, že není součástí algoritmu nebo jeho implementace). Klíčem může být například hodnota kryptografické hašovací funkce z tajné fráze požadované od uživatele.

Typické algoritmy pro generování náhodných prvočísel

Všude níže se předpokládá použití kryptograficky silného PRNG inicializovaného tajným klíčem (podrobnosti závisí na použitém PRNG a na tom, jak je klíč získán a prezentován).

Testování jednoduchosti

Můžete zkontrolovat (pravděpodobnou) prvotřídnost čísla p obsahujícího k bitů takto:

1. Ujistěte se, že p není dělitelné malými prvočísly 3, 5, 7, 11 atd. do nějakého malého limitu (např. 256). Taková kontrola vám umožňuje efektivně odříznout mnoho zjevně složených čísel před jejich kontrolou pomocí časově náročnějších algoritmů. Takže kontrola, že p je dělitelné prvočísly 2, 3, 5 a 7, odfiltruje všechna sudá čísla a 54 % lichých čísel, kontrola, že p je dělitelné všemi prvočísly až do 100, odfiltruje 76 % lichých čísel. , a kontrola, že p je dělitelné všemi prvočísly až do 256, odstraní 80 % lichých čísel.
2. Spusťte Miller-Rabinův test s alespoň k koly .

Pokud číslo p neprojde alespoň jednou kontrolou, není prvočíslo. Jinak s velkou pravděpodobností (v závislosti na počtu kol) je číslo p prvočíslo.

Přímá konstrukce

1. Vygenerujte náhodné bity a složte je do k -bitového čísla p s nejvýznamnějším bitem rovným 1.
2. Zvyšte p o 1 a zkontrolujte, zda je prvočíslo. Tento krok opakujte, dokud nenajdete prvočíslo.

Druhý krok lze urychlit, pokud uvažujeme pouze lichá čísla nebo čísla srovnatelná s 1 a 5 modulo 6 atd.

( n - 1)-metody

Metody konstrukce ( n -1)-prvočísel používají znalost prvočíselných dělitelů n -1 k testování, zda je n prvočíslo pomocí Lucasova testu primality . [jeden]

Typický představitel této třídy metod je popsán v knize „Úvod do kryptografie“, kterou vydal V. V. Yashchenko. [2]

Generace prvočísel Sophie Germain

Prvočísla Sophie Germain  jsou prvočísla p taková, že 2p + 1 je také prvočíslo.

Poznámky

1. ↑ Cheryomushkin A.V. Přednášky o aritmetických algoritmech v kryptografii. - M. : MTSNMO , 2002. - 104 s. — ISBN 5-94057-060-7 .
2. ↑ Yu. V. Nesterenko. Kapitola 4.5. Jak stavět velká prvočísla // Úvod do kryptografie / Ed. V. V. Jaščenko. - Petr, 2001. - 288 s. - ISBN 5-318-00443-1 . Archivovaná kopie (nedostupný odkaz) . Datum přístupu: 18. února 2008. Archivováno z originálu 25. února 2008. (neurčitý)