У криптографії під випадковим простим числом розуміється просте число, що містить у двійковому записі задану кількість бітів , на алгоритм генерування якого накладаються певні обмеження. Отримання випадкових простих чисел є невід'ємною частиною процедур вироблення ключів у багатьох криптографічних алгоритмах, зокрема в RSA і ElGamal.
Зважаючи на те, що перевірка простоти великих чисел вимагає істотних часових витрат, вимогу простоти одержуваного числа часто послаблюють до сильної псевдопростоти за кількома різними випадковим основами. Існують алгоритми перевірки сильної псевдопростоти на порядки швидші від найкращих відомих алгоритмів перевірки простоти. Разом з тим, числа, які успішно пройшли тестування сильної псевдопростоти за кількома випадковими основами, з великою ймовірністю є простими, причому ця ймовірність зростає зі зростанням кількості основ, за якими проводиться перевірка.
Вимоги до алгоритму і його реалізації
Вимоги до алгоритмів генерування випадкових простих чисел зводяться до таких двох:
- Розподіл одержуваних простих чисел має бути близьким до рівномірного на множині всіх k-бітових простих чисел. Існує кілька способів забезпечити виконання цієї вимоги.
- Процес генерування конкретного випадкового простого числа неможливо відтворити, навіть знаючи деталі алгоритму та його реалізації. Зазвичай виконання цієї вимоги забезпечується використанням криптостійкого ГПВЧ, проініціалізованого деяким ключем, одержуваним ззовні (тобто, який не є частиною алгоритму або його реалізації). Ключем може виступати, наприклад, значення криптографічної геш-функції від секретної фрази, запитуваної в користувача.
Типові алгоритми генерування випадкових простих чисел
Скрізь далі передбачається використання криптографічно стійкого ГПВЧ, проініціалізованого за допомогою секретного ключа (деталі залежать від використовуваного ГПВЧ і способу отримання та подання ключа).
Тестування простоти
Перевірити (ймовірну) простоту числа p, що містить k бітів, можна так:
- Переконатися, що p не ділиться на невеликі прості числа 3, 5, 7, 11, і т. д. до деякої невеликої межі (наприклад, 256). Така перевірка дозволяє ефективно відсікти багато складених чисел, перш ніж перевіряти їх за допомогою трудомісткіших алгоритмів. Так, перевірка подільності p на прості числа 2, 3, 5 і 7 відсіває всі парні числа і 54 % непарних чисел, перевірка подільності p на всі прості числа до 100 відсіває 76 % непарних чисел, а перевірка подільності p на всі прості числа до 256 відсіває 80 % непарних чисел.
- Виконати тест Міллера — Рабіна з кількістю раундів не менше k.
Якщо число p не проходить хоча б однієї з перевірок — воно не є простим. В іншому випадку з великою ймовірністю (залежить від кількості раундів) число p є простим.
Пряма побудова
- Згенерувати випадкових бітів і скласти з них k-бітове число p зі старшим бітом рівним 1.
- Збільшити p на 1 і перевірити його простоту. Повторювати цей крок доти, поки не буде знайдено просте число.
Другий крок можна прискорити, якщо розглядати тільки непарні числа або числа, порівнянні з 1 і 5 за модулем 6 тощо.
(n-1)-методи
(n-1)-методи побудови простих чисел використовують знання про прості дільники числа n-1 для тестування простоти n за допомогою тесту простоти Люка.
Типового представника цього класу методів описано в книзі «Вступ до криптографії» під редакцією В. В. Ященко.
Генерування простих чисел Софі Жермен
Прості числа Софі Жермен — такі прості p, що 2p + 1 теж просте.
Примітки
- Черёмушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М. : МЦНМО, 2002. — 104 с. — .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U kriptografiyi pid vipadkovim prostim chislom rozumiyetsya proste chislo sho mistit u dvijkovomu zapisi zadanu kilkist bitiv k displaystyle k na algoritm generuvannya yakogo nakladayutsya pevni obmezhennya Otrimannya vipadkovih prostih chisel ye nevid yemnoyu chastinoyu procedur viroblennya klyuchiv u bagatoh kriptografichnih algoritmah zokrema v RSA i ElGamal Zvazhayuchi na te sho perevirka prostoti velikih chisel vimagaye istotnih chasovih vitrat vimogu prostoti oderzhuvanogo chisla chasto poslablyuyut do silnoyi psevdoprostoti za kilkoma riznimi vipadkovim osnovami Isnuyut algoritmi perevirki silnoyi psevdoprostoti na poryadki shvidshi vid najkrashih vidomih algoritmiv perevirki prostoti Razom z tim chisla yaki uspishno projshli testuvannya silnoyi psevdoprostoti za kilkoma vipadkovimi osnovami z velikoyu jmovirnistyu ye prostimi prichomu cya jmovirnist zrostaye zi zrostannyam kilkosti osnov za yakimi provoditsya perevirka Vimogi do algoritmu i jogo realizaciyiVimogi do algoritmiv generuvannya vipadkovih prostih chisel zvodyatsya do takih dvoh Rozpodil oderzhuvanih prostih chisel maye buti blizkim do rivnomirnogo na mnozhini vsih k bitovih prostih chisel Isnuye kilka sposobiv zabezpechiti vikonannya ciyeyi vimogi Proces generuvannya konkretnogo vipadkovogo prostogo chisla nemozhlivo vidtvoriti navit znayuchi detali algoritmu ta jogo realizaciyi Zazvichaj vikonannya ciyeyi vimogi zabezpechuyetsya vikoristannyam kriptostijkogo GPVCh proinicializovanogo deyakim klyuchem oderzhuvanim zzovni tobto yakij ne ye chastinoyu algoritmu abo jogo realizaciyi Klyuchem mozhe vistupati napriklad znachennya kriptografichnoyi gesh funkciyi vid sekretnoyi frazi zapituvanoyi v koristuvacha Tipovi algoritmi generuvannya vipadkovih prostih chiselSkriz dali peredbachayetsya vikoristannya kriptografichno stijkogo GPVCh proinicializovanogo za dopomogoyu sekretnogo klyucha detali zalezhat vid vikoristovuvanogo GPVCh i sposobu otrimannya ta podannya klyucha Testuvannya prostoti Pereviriti jmovirnu prostotu chisla p sho mistit k bitiv mozhna tak Perekonatisya sho p ne dilitsya na neveliki prosti chisla 3 5 7 11 i t d do deyakoyi nevelikoyi mezhi napriklad 256 Taka perevirka dozvolyaye efektivno vidsikti bagato skladenih chisel persh nizh pereviryati yih za dopomogoyu trudomistkishih algoritmiv Tak perevirka podilnosti p na prosti chisla 2 3 5 i 7 vidsivaye vsi parni chisla i 54 neparnih chisel perevirka podilnosti p na vsi prosti chisla do 100 vidsivaye 76 neparnih chisel a perevirka podilnosti p na vsi prosti chisla do 256 vidsivaye 80 neparnih chisel Vikonati test Millera Rabina z kilkistyu raundiv ne menshe k Yaksho chislo p ne prohodit hocha b odniyeyi z perevirok vono ne ye prostim V inshomu vipadku z velikoyu jmovirnistyu zalezhit vid kilkosti raundiv chislo p ye prostim Pryama pobudova Zgeneruvati k 1 displaystyle k 1 vipadkovih bitiv i sklasti z nih k bitove chislo p zi starshim bitom rivnim 1 Zbilshiti p na 1 i pereviriti jogo prostotu Povtoryuvati cej krok doti poki ne bude znajdeno proste chislo Drugij krok mozhna priskoriti yaksho rozglyadati tilki neparni chisla abo chisla porivnyanni z 1 i 5 za modulem 6 tosho n 1 metodi n 1 metodi pobudovi prostih chisel vikoristovuyut znannya pro prosti dilniki chisla n 1 dlya testuvannya prostoti n za dopomogoyu testu prostoti Lyuka Tipovogo predstavnika cogo klasu metodiv opisano v knizi Vstup do kriptografiyi pid redakciyeyu V V Yashenko Generuvannya prostih chisel Sofi ZhermenProsti chisla Sofi Zhermen taki prosti p sho 2p 1 tezh proste PrimitkiCheryomushkin A V Lekcii po arifmeticheskim algoritmam v kriptografii M MCNMO 2002 104 s ISBN 5 94057 060 7