МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный технический университет радиотехники, электроники и автоматики" МГТУ МИРЭА
Кибернетика                                (наименование факультета)
Компьютерная безопасность                                     (наименование кафедры)

Курсовая работа
по дисциплине
«Криптографические методы защиты информации.» (наименование дисциплины)
На тему: “ Анализ алгоритмов продуктов GNUPGи PGP4win. ”
Студент группы        ККС-2-12                                (учебная  группа)	____________Витин Я.В.____________ (Фамилия И.О.)
Руководитель (должность, звание, ученая степень)	____________ Хомутов Д.Г._______  (Фамилия И.О.)

Москва 2016

 

 

1.Введение……………………………………………………………………………….3

 Использование PGP в программных продуктах……………………………………..4-9

2.Подробно об алгоритмах GNU PG и PGP4win…………………………………10

Стандарт генерации ключей X9.17……………………………………………………10

Алгоритм IDEA…………………………………………………………………………10-13

Криптоанализ IDEA…………………………………………………………………….14

Алгоритм RSA………………………………………………………………………….14-15

Хеш-функция md5………………………………………………………………………16-18

Безопасность md5……………………………………………………………………….18

Алгоритм Feal…………………………………………………………………………...19-23

Алгоритм S-Way…………………………………………………………………………24

3.Генерация простого числа………………………………………………………….25-28

Список литературы………………………………………………………………………29

 

Введение.

 

1.  PRETTY GOOD PRIVACY (PGP)

Pretty Good Privacy (PGP, весьма хорошая секретность) - это свободно распространяемая программа безопасной электронной почты, разработанная Филипом Циммерманном (Philip Zimmermann). Для шифрования данных она использует IDEA, для управления ключами и цифровой подписи - RSA (длина ключа до 2047 битов), а для однонаправленного хэширования - MD5.

Для получения случайных открытых ключей PGP использует вероятностную проверку чисел на простоту, используя для получения стартовых последовательностей интервалы между нажатиями пользователем клавиш на клавиатуре. PGP генерирует случайные ключи IDEA с помощью метода, в ANSI X9.17, Appendix C, используя вместо DES в качестве симметричного алгоритма IDEA. PGP также шифрует закрытый ключ пользователя с помощью хэшированной парольной фразы, а не пароля непосредственно.

Сообщения, зашифрованные PGP, имеют несколько уровней безопасности. Единственная вещь, известная криптоаналитику о зашифрованном сообщении, - это получатель сообщения при условии, что криптоаналитику известен ID ключа получателя. Только расшифровав сообщение, получатель узнает, кем оно подписано, если оно подписано. Это резко отличается от сообщения PEM, в заголовке которого немало информации об отправителе, получателе и самом сообщении хранится в незашифрованном виде.

Использование PGP   в программных продуктах.

Создание ключей только для шифрования с помощью Kleopatra

1.     Откройте Kleopatra. Появится окно, аналогичное изображенному ниже. (О том, как загрузить Kleopatra).

Рис 1.1 Окно Kleopatra

2.     Выберите пункт Create a personal OpenPGP key pair (Создать пару персональных ключей OpenPGP), как показано ниже.

Рис. 1.2. Выбор формата сертификата

3.     Введите надлежащие значения Name и EMail, затем выберите Advanced Settings (Дополнительные параметры).

Рис. 1.3 Личные данные

4.     Откроется окно дополнительных параметров. В области Key Material выберите RSA и убедитесь, что в области Certificate Usage отмечен только пункт Encryption. (По умолчанию выбран пункт Certification, потому что мы создаем сертификат). Нажмите кнопку OK.

Рис. 1.4 Дополнительные параметры

5.     В окне Review Certificate Parameters (Просмотр параметров сертификата) убедитесь, что выбраны нужные значения типа ключа и назначения сертификата. Подтвердив эти значения, нажмите кнопку Create Key.

Рис. 1.5 Параметры сертификата

6.     Введите произвольный пароль. Он должен состоять по меньшей мере из восьми буквенно-цифровых символов. Нажмите кнопку OK.

7.     Должно появиться сообщение об успешном завершении операции, подобное показанному ниже. Если нужно, создайте резервную копию пары ключей и нажмите кнопку Finish.

Рис. 1.6 Сообщение об успешном завершении операции

Создание ключей только для шифрования с помощью GnuPG

GNU Privacy Guard (GnuPG) — это инструмент командной строки, который позволяет создавать ключи и управлять ими. Он также позволяет шифровать, расшифровывать и подписывать документы с помощью этих ключей. Откройте командную строку Windows и введите следующую команду: gpg –gen –key -expert.

Примечание. По умолчанию создать ключи только для шифрования с помощью GnuPG не удастся. Для этой функции требуется режим Expert.
Выберите вариант RSA (set your own capabilities), как показано ниже.

Рис. 1.7. Запрос RSA

1.     Отключите подпись, как показано ниже (по умолчанию при создании ключа RSA подпись включена).

Рис. 1.8 Отключение подписи

2.     Отображается набор параметров, как на предыдущем шаге. Выберите пункт Finished.

Рис. 1.9 Пункт Finished

3.     В командной строке укажите длину ключа RSA, как показано ниже.

Рис. 1.10 Длина ключа RSA

4.     При появлении запроса укажите срок действия ключа, как показано ниже.

Рис. 1.11 Срок действия ключа

5.     Введите имя и адрес электронной почты. Real name – это имя, присвоенное ключу. Выберите вариант Okay.

Рис. 1.12 Имя и адрес электронной почты

6.     Введите произвольный пароль.

2.  Подробно об алгоритмах GNUPG и PGP4win.

Стандарт генерации ключей X9.17

Стандарт ANSI X9.17 определяет способ Генерации ключей (см. Рис. 2.1). Он не создает легко запоминающиеся ключи, и больше подходит для генерации сеансовых ключей или псевдослучайных чисел в системе. Для генерации ключей используется криптографический алгоритм DES, но он может быть легко заменен любым другим алгоритмом.

Рис. 2.1 Генерация ключей ANSI X9.17

Пусть E_K(X) - это X, зашифрованный DES ключом K, специальным ключом, предусмотренным для генерации секретных ключей. V₀ - это секретная 64-битовая стартовая последовательность. T - это метка времени. Для генерации случайного ключа R_i вычислим:

R_i= E_K(E_K(T_i) Å V_i)

Для генерации V_i+1, вычислим:

V_i+1= E_K(E_K(T_i) Å R_i)

Для превращения R_i в ключ DES, просто удалите каждый восьмой бит. Если вам нужен 64-битовый ключ, используйте ключ без изменения. Если вам нужен 128-битовый ключ, создайте пару ключей и объедините их.

                                          Алгоритм IDEA.

Описание IDEA

Схема IDEA представлена на Рис. 2.2. 64-битовый блок данных делится на четыре 16-битовых подблока: X₁, X₂, X₃ и X₄. Эти четыре подблока становятся входными данными для первого этапа алгоритма. Всего в алгоритме восемь этапов. На каждом этапе четыре подблока подвергаются операциям XOR, сложениям и умножениям друг с другом и с шестью 16-битовыми подключами. Между этапами обмениваются местами второй и третий подблоки. Наконец четыре подблока объединяются с четырьмя подключами в окончательном преобразовании. На каждом этапе события происходят в следующей последовательности:

(1)  Перемножаются X₁ и первый подключ.

(2)  Складываются X₂ и второй подключ.

(3)  Складываются X₃ и третий подключ.

(4)  Перемножаются X₄ и четвертый подключ.

(5)  Выполняется XOR над результатами этапов (1) и (3).

(6)  Выполняется XOR над результатами этапов (2) и (4).

(7)  Перемножаются результаты этапа (5) и пятый подключ.

(8)  Складываются результаты этапов (6) и (7).

(9)  Перемножаются результаты этапа (8) и шестой подключ.

(10) Складываются результаты этапов (7) и (9).

(11) Выполняется XOR над результатами этапов (1) и (9).

(12) Выполняется XOR над результатами этапов (3) и (9).

(13) Выполняется XOR над результатами этапов (1) и (10).

(14) Выполняется XOR над результатами этапов (4) и (10).

Рис. 2.2 IDEA.

Выходом этапа являются четыре подблока - результаты действий (11), (12), (13) и (14). Поменяйте местами два внутренних подблока (но не в последнем этапе), и вы получите исходные данные для следующего этапа.

После восьмого этапа выполняется заключительное преобразование:

(1)  Перемножаются X_l и первый подключ.

(2)  Складываются X₂ и второй подключ.

(3)  Складываются X₃ и третий подключ.

(4)  Перемножаются X₄ и четвертый подключ.

Наконец четыре подблока снова соединяются, образуя шифротекст.

Также несложно создавать подключи. Алгоритм использует 52 из них (шесть для каждого из восьми этапов и еще четыре для заключительного преобразования). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это первые восемь подключей алгоритма (шесть для первого этапа и два - для второго). Затем ключ циклически сдвигается налево на 25 битов и снова делится на восемь подключей. Первые четыре используются на этапе 2, а оставшиеся четыре - на этапе 3. Ключ циклически сдвигается налево на 25 битов для получения следующих восьми подключей, и так до конца алгоритма.

Дешифрирование выполняется точно также за исключением того, что подключи инвертируются и слегка изменяются. Подключи при дешифрировании представляют собой обратные значения ключей шифрования по отношению к операциям либо сложения, либо умножения. (Для IDEA подблоки, состоящие из одних нулей,  считаются равными 2¹⁶ = -1 для умножения по модулю 2¹⁶ + 1, следовательно, обратным значением 0 относительно умножения является 0.) Эти вычисления могут занять некоторое время, но их нужно выполнить один раз для каждого ключа дешифрирования. В Табл. 2.1 представлены подключи шифрования и соответствующие подключи дешифрирования.

Табл. 2.1
Подключи шифрования и дешифрирования IDEA

Этап

Подключи шифрования

Подключи дешифрирования

1

Z1(1)

Z2(1)

Z3(1)

Z4(1)

Z5(1)

Z6(1)

Z1(9)-1

-Z2(9)

-Z3(9)

Z4(9)-1

Z5(8)

Z6(8)

2

Z1(2)

Z2(2)

Z3(2)

Z4(2)

Z5(2)

Z6(2)

Z1(8)-1

-Z2(8)

-Z3(8)

Z4(8)-1

Z5(7)

Z6(7)

3

Z1(3)

Z2(3)

Z3(3)

Z4(3)

Z5(3)

Z6(3)

Z1(7)-1

-Z2(7)

-Z3(7)

Z4(7)-1

Z5(6)

Z6(6)

4

Z1(4)

Z2(4)

Z3(4)

Z4(4)

Z5(4)

Z6(4)

Z1(6)-1

-Z2(6)

-Z3(6)

Z4(6)-1

Z5(5)

Z6(5)

5

Z1(5)

Z2(5)

Z3(5)

Z4(5)

Z5(5)

Z6(5)

Z1(5)-1

-Z2(5)

-Z3(5)

Z4(5)-1

Z5(4)

Z6(4)

6

Z1(6)

Z2(6)

Z3(6)

Z4(6)

Z5(6)

Z6(6)

Z1(4)-1

-Z2(4)

-Z3(4)

Z4(4)-1

Z5(3)

Z6(3)

7

Z1(7)

Z2(7)

Z3(7)

Z4(7)

Z5(7)

Z6(7)

Z1(3)-1

-Z2(3)

-Z3(3)

Z4(3)-1

Z5(2)

Z6(2)

8

Z1(8)

Z2(8)

Z3(8)

Z4(8)

Z5(8)

Z6(8)

Z1(2)-1

-Z2(2)

-Z3(2)

Z4(2)-1

Z5(1)

Z6(1)

Криптоанализ IDEA

Длина ключа IDEA равна 128 битам - более чем в два раза длиннее ключа DES. При условии, что наиболее эффективным является вскрытие грубой силой, для вскрытия ключа потребуется 2¹²⁸ (10³⁸) шифрований. Создайте микросхему, которая может проверять миллиард ключей в секунду, объедините миллиард таких микросхем, и вам потребуется 10¹³ лет для решения проблемы - это больше, чем возраст вселенной. 10²⁴ таких микросхем могут найти ключ за день, но во вселенной не найдется столько атомов кремния, чтобы построить такую машину.

Алгоритм все еще слишком нов, чтобы можно было говорить о каких-то конкретных криптографических результатах. Разработчики сделали все возможное, чтобы сделать алгоритм устойчивым к дифференциальному криптоанализу. Они определили понятие марковского шифра и продемонстрировали, что устойчивость к дифференциальному криптоанализу может быть промоделирована и оценена количественно. Для сравнения с алгоритмом IDEA, устойчивость которого к дифференциальному криптоанализу была усилена. IDEA устойчив к дифференциальному криптоанализ уже после 4 из 8 этапов.

Алгоритм RSA.

Шифрование RSA

n          произведение двух простых чисел p и q (p и q должны храниться в секрете)

e          число, взаимно простое с (p-1)(q-1)

Закрытый ключ:

d          e^-1 mod ((p-1)(q-1))

Шифрование:

c = m^e mod n

Дешифрирование:

Точно также сообщение может быть зашифровано с помощью d, а зашифровано с помощью e, возможен любой выбор.

Короткий пример возможно поможет пояснить работу алгоритма. Если p = 47 и q = 71, то

n = pq = 3337

Ключ e не должен иметь общих множителей

(p-1)(q-1)= 46*70 =3220

Выберем (случайно) e равным 79. В этом случае d = 79^-1 mod 3220 = 1019

При вычислении этого числа использован расширенный алгоритм Эвклида. Опубликуем e и n, сохранив в секрете d. Отбросим p и q. Для шифрования сообщения m = 6882326879666683 сначала разделим его на маленькие блоки. Для нашего случая подойдут трехбуквенные блоки. Сообщение разбивается на шесть блоков m_i:

m_l = 688

m₂ = 232

m₃ = 687

m₄ = 966

m₅ = 668

m₆ = 003

Первый блок шифруется как 688⁷⁹ mod 3337 = 1570 = c_l

Выполняя те же операции для последующих блоков, создает шифротекст сообщения:

c = 1570 2756 2091 2276 2423 158

Для дешифрирования нужно выполнить такое же возведение в степень, используя ключ дешифрирования 1019:

1570¹⁰¹⁹ mod 3337 = 688 = m_l

Аналогично восстанавливается оставшаяся часть сообщения.

                                     Хеш-функция MD5.

MD5 - это улучшенная версия MD4. Хотя она сложнее MD4, их схемы похожи, и результатом MD5 также является 128-битовое хэш-значение.

Описание MD5

После некоторой первоначальной обработки MD5 обрабатывает входной текст 512-битовыми блоками, разбитыми на 16 32-битовых подблоков. Выходом алгоритма является набор из четырех 32-битовых блоков, которые объединяются в единое 128-битовое хэш-значение.

Во-первых, сообщение дополняется так, чтобы его длина была на 64 бита короче числа, кратного 512. Этим дополнением является 1, за которой вплоть до конца сообщения следует столько нулей, сколько нужно. Затем, к результату добавляется 64-битовое представление длины сообщения (истинной, до дополнения). Эти два действия служат для того, чтобы длина сообщения была кратна 512 битам (что требуется для оставшейся части алгоритма), и чтобы гарантировать, что разные сообщения не будут выглядеть одинаково после дополнения. Инициализируются четыре переменных:

A = 0x01234567

B = 0x89abcdef

C = 0xfedcba98

D = 0x76543210

Они называются переменными сцепления.

Теперь перейдем к основному циклу алгоритма. Этот цикл продолжается, пока не исчерпаются 512-битовые блоки сообщения.

Четыре переменных копируются в другие переменные: A в a, B в b, C в c и D в d.

Главный цикл состоит из четырех очень похожих этапов (у MD4 было только три этапа). На каждом этапе 16 раз используются различные операции. Каждая операция представляет собой нелинейную функцию над тремя из a, b, c и d. Затем она добавляет этот результат к четвертой переменной, подблоку текста и константе. Далее результат циклически сдвигается вправо на переменное число битов и добавляет результат к одной из переменных a, b, c и d. Наконец результат заменяет одну из переменных a, b, c и d. (См. Рис. 2.3 и Рис. 2.4). Существуют четыре нелинейных функции, используемые по одной в каждой операции (для каждого этапа - другая функция).

Рис. 2.3 Главный цикл MD5.

Рис. 2.4 Одна операция MD5.

F(X,Y,Z) = (X Ù Y) Ú ((ØX) Ù Z)

G(X,Y,Z) = (X Ù Z) Ú (Y Ù (ØZ))

H(X,Y,Z) = X Å Y Å Z

I(X,Y,Z) = Y Å (X Ú (ØZ))

(Å - это XOR, Ù - AND, Ú - OR, а Ø - NOT.)

Эти функции спроектированы так, чтобы, если соответствующие биты X, Y и Z независимы и несмещены, каждый бит результата также был бы независимым и несмещенным. Функция F - это побитовое условие: если X, то Y, иначе Z. Функция H - побитовая операция четности.

Если M_j обозначает j-ый подблок сообщения (от 0 до 15), а <<

FF(a,b,c,d,M_j,s,t_i) означает a = b + ((a + F(b,c,d) + M_j + t_i) <<

GG(a,b,c,d,M_j,s,t_i) означает a = b + ((a + G(b,c,d) + M_j + t_i) <<

HH(a,b,c,d,M_j,s,t_i) означает a = b + ((a + H(b,c,d) + M_j + t_i) <<

II(a,b,c,d,M_j,s,t_i) означает a = b + ((a + I(b,c,d) + M_j + t_i) <<

После всего этого a, b, c и d добавляются к A, B, C и D, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение A, B, C и D.

Безопасность MD5

Улучшения MD5 в сравнении с MD4:

1.     Добавился четвертый этап.

2.     Теперь в каждом действии используется уникальная прибавляемая константа.

3.     Функция G на этапе 2 с ((XÙY)Ú(XÙZ)Ú(YÙZ)) была изменена на (XÙZ)Ú(YÙ(ØZ)), чтобы сделать G менее симметричной.

4.     Теперь каждое действие добавляется к результату предыдущего этапа. Это обеспечивает более быстрый лавинный эффект.

5.     Изменился порядок, в котором использовались подблоки сообщения на этапах 2 и 3, чтобы сделать шаблоны менее похожими.

6.     Значения циклического сдвига влево на каждом этапе были приближенно оптимизированы для ускорения лавинного эффекта. Четыре сдвига, используемые на каждом этапе, отличаются от значений, используемых на других этапах.

Алгоритм   FEAL.

В алгоритме FEAL используются 64-битовый блок и 64-битовый ключ. Его идея состоит в том, чтобы создать алгоритм, подобный DES, но с более сильной функцией этапа.

Описание FEAL

На Рис. 2.5 представлена блок-схема одного этапа FEAL. В качестве входа процесса шифрования используется 64-битовый блок открытого текста. Сначала блок данных подвергается операции XOR с 64 битами ключа. Затем блок данных расщепляется не левую и правую половины. Объединение левой и правой половин с помощью XOR образует новую правую половину. Левая половина и новая правая половина проходят через n этапов (первоначально четыре). На каждом этапе правая половина объединяется с помощью функции f с шестнадцатью битами ключа и с помощью XOR - с левой половиной, создавая новую правую половину. Исходная правая половина (на начало этапа) становится новой левой половиной. После n этапов (не забывайте, что левая и правая половины не переставляются после n-го этапа) левая половина снова объединяется с помощью XOR с правой половиной, образуя новую правую половину, затем левая и правая соединяются вместе в 64-битовое целое. Блок данных объединяется с помощью XOR с другими 64 битами ключа, и алгоритм завершается.

Рис. 2.5 Один этап FEAL.

Функция f берет 32 бита данных и 16 битов ключа и смешивает их вместе. Сначала блок данных разбивается на 8-битовые кусочки, которые затем объединяются с помощью XOR и заменяют друг друга. Блок-схема функции f  представлена на Рис. 2.6. Две функции S₀и S₁ определяются следующим образом:

S₀ (a, b) = циклический сдвиг влево на два бита ((a + b) mod 256)

S₁ (a, b) = циклический сдвиг влево на два бита ((a + b + 1) mod 256)

Рис. 2.6 Функция f.

Тот же алгоритм может быть использован для дешифрирования. Единственным отличием является то, что при дешифрировании порядок использования частей ключа меняется на обратный.

На Рис 2.7 представлена блок-схема функции генерации ключа. Сначала 64-битовый ключ делится на две половины, к которым применяются операции XOR и функции f_k, как показано на схеме. На Рис 2.8 показана блок-схема функции f_k. Два 32-битовых входа разбиваются на 8-битовые блоки, объединяемые и заменяемые в соответствии со схемой. S₀ и S₁ определяются, как показано на рисунке. Затем в алгоритме шифрования/дешифрирования используются 16-битовые блоки ключа.

Рис. 2.7 Обработка ключа в FEAL.

Рис. 2.8 Функция f_K.

Криптоанализ FEAL

Для вскрытия FEAL-16 нужно 2²⁸ выбранных или 2^46.5 известных открытых текстов. Для вскрытия FEAL-8 требуется 2000 выбранных или 2^37.5 известных открытых текстов. FEAL-4 может быть вскрыт с помощью всего 8 правильно выбранных открытых текстов.

Разработчики FEAL определили также модификацию FEAL - FEAL-NX, в которой используется 128-битовый ключ (см. Рис. 2.9).

Рис. 2.9 Обработка ключа в FEAL-NX.

Алгоритм S-Way.

Этот алгоритм описать несложно. Для шифрования блока открытого текста x:

For i = 0 to n - 1

x = x XOR K_i

x = theta (x)

x = pi - 1 (x)

x = gamma (x)

x = pi - 2 (x)

x = x Å Kⁿ⁺¹

x = theta (x)

При этом используются следующие функции:

—  theta(x) - функция линейной подстановки, в основном набор циклических сдвигов и XOR.

—  pi - 1 (x) и pi - 2 (x) - простые перестановки.

—  gamma (x) - функция нелинейной подстановки. Именно это действие и дало имя всему алгоритму, оно представляет собой параллельное выполнение подстановки 3-битовых данных.

Дешифрирование аналогично шифрованию за исключением того, что нужно изменить на обратный порядок битов исходных данных и результата.

3. Генерация простого числа

Для алгоритмов с открытыми ключами нужны простые числа. Их нужно множество для любой достаточно большой сети. Для чисел, близких n, вероятность того, что случайно выбранное число окажется простым, равна 1/ln n. Поэтому полное число простых чисел, меньших n, равно n/(ln n).

Существуют различные вероятностные проверки на простоту чисел, определяющие, является ли число простым, с заданной степенью достоверности. При условии, что эта "степень достоверности" достаточна велика, такие способы проверки достаточно хороши.

Solovay-Strassen

Роберт Соловэй (Robert Solovay) и Фолькер Штрассен (Volker Strassen) разработали алгоритм вероятностной проверки простоты числа. Для проверки простоты числа p этот алгоритм использует символ Якоби:

(1)  Выберите случайно число a, меньшее p.

(2)  Если НОД (a, p) (1, то p не проходит проверку и является составным.

(3)  Вычислите j = a(p-1)/2 mod p.

(4)  Вычислите символ Якоби J(a,p).

(5)  Если j ¹ J(a,p), то число p наверняка не является простым.

(6)  Если j = J(a,p), то вероятность того, что число p не является простым, не больше 50 процентов.

Число a, которое не показывает, что p наверняка не является простым числом, называется свидетелем. Если p - составное число, вероятность случайного числа a быть свидетелем не ниже 50 процентов. Повторите эту проверку t раз с t различными значениями a. Вероятность того, что составное число преодолеет все t проверок, не превышает 1/2^t.

Lehmann

Другой, более простой тест был независимо разработан Леманном (Lehmann). Вот последовательность действий при проверке простоты числа p:

(1)  Выберите случайно число a, меньшее p.

(2)  Вычислите a^(p-1)/2 mod p.

(3)  Если a^(p-1)/2 ¹ 1 или -1 (mod p), то p не является простым.

(4)  Если a^(p-1)/2 º 1 или -1 (mod p), то вероятность того, что число p не является простым, не больше 50 процентов.

И снова, вероятность того, что случайное число a будет свидетелем составной природы числа p, не меньше 50 процентов. Повторите эту проверку t раз. Если результат вычислений равен 1 или -1, но не всегда равен 1, то p является простым числом с вероятностью ошибки 1/^2t.

Rabin-Miller

Повсеместно используемым является простой алгоритм, разработанный Майклом Рабином (Michael Rabin), частично основанным на идеях Гэри Миллера.

Выберите для проверки случайное число p. Вычислите b - число делений p - 1 на 2 (т.е., 2^b - это наибольшая степень числа 2, на которое делится p - 1). Затем вычислите m, такое что p = 1 + 2^b * m.

(1)  Выберите случайное число a, меньшее p.

(2)  Установите j = 0 и z = am mod p.

(3)  Если z = 1 или если z = p - 1, то p проходит проверку и может быть простым числом.

(4)  Если j > 0 и z = 1, то p не является простым числом.

(5)   Установите j = j + 1. Если j < b и z (p - 1, установите z = z² mod p и вернитесь на этап (4). Если z = p - 1, то p проходит проверку и может быть простым числом.

(6)  Если j = b и z ¹ p - 1, то p не является простым числом.

В этом тесте вероятность прохождения проверки составным числом убывает быстрее, чем в предыдущих. Гарантируется, что три четверти возможных значений a окажутся свидетелями. Это означает, что составное число проскользнет через t проверок с вероятностью не большей (1/4)^t, где t - это число итераций. На самом деле и эти оценки слишком пессимистичны. Для большинства случайных чисел около 99.9 процентов возможных значений a являются свидетелями.

Практические соображения

В реальных приложениях генерация простых чисел происходит быстро.

(1)  Сгенерируйте случайное n-битовое число p.

(2)  Установите старший и младший биты равными 1. (Старший бит гарантирует требуемую длину простого числа, а младший бит обеспечивает его нечетность.)

(3)  Убедитесь, что p не делится на небольшие простые числа: 3, 5, 7, 11, и т.д. Во многих реализациях проверяется делимость p на все простые числа, меньшие 256. Наиболее эффективной является проверка на делимость для всех простых чисел, меньших 2000.

(4)  Выполните тест Rabin-Miller для некоторого случайного a. Если p проходит тест, сгенерируйте другое случайное a и повторите проверку. Выбирайте небольшие значения a для ускорения вычислений. Выполните пять тестов. (Одного может показаться достаточным, но выполните пять.) Если p не проходит одной из проверок, сгенерируйте другое p и попробуйте снова.

Иначе, можно не генерировать p случайным образом каждый раз, но последовательно перебирать числа, начиная со случайно выбранного до тех пор, пока не будет найдено простое число.

Этап (3) не является обязательным, но это хорошая идея. Проверка, что случайное нечетное p не делится на 3, 5 и 7 отсекает 54 процента нечетных чисел еще до этапа (4). Проверка делимости на все простые числа, меньшие 100, убирает 76 процентов нечетных чисел, проверка делимости на все простые числа, меньшие 256, убирает 80 процентов нечетных чисел. В общем случае, доля нечетных кандидатов, которые не делятся ни на одно простое число, меньшее n, равна 1.12/ln n. Чем больше проверяемое n, тем больше предварительных вычислений нужно выполнить до теста Rabin-Miller.

Список литературы

1.     Ю. Лифшиц. Курс лекций «Современные задачи криптографии». Доступно в электронной форме по адресу http://yury.name/cryptography

2.     Шнайер Б. Прикладная криптография.- М. : Триумф, 2002. – 816с.

3.     Erich Wegener, Mario Werner. «Evaluating 16-bit Processors for Elliptic Curve Cryptography». Institute for Applied Information Processing And Communications (IAIK), Graz University of Technology

4.     http://old.pgpru.com/pgp_for_beginners/pgp_for_beg_01.htm

5.     https://www.gpg4win.org/

6.     http://jenyay.net/blog/2012/01/04/shifrovanie-s-pomoshhyu-gnupg-dlya-polzovatelejj/