Занятие 5: Тестирование простоты чисел. Криптографическая система RSA.¶

Цель: Обобщить лекционный материал алгоритмов работы с целыми числами.¶

Тест простоты числа¶

Теорема Вильсона¶

Если $p$ — простое число, то число $(p-1)!+1$ делится на $p$. Обратно: если $(p-1)!+1$ делится на $p$, то $p$ — простое число.

Заманчиво просто, не так ли?! Однако, эта теорема, в основном, имеет теоретическое значение, поскольку факториал $(p-1)!$ вычислить довольно трудно. Проще вычислить $a^{p-1}$, поэтому элементарные тесты, определяющие, является ли число простым, основаны на теореме Ферма, а не на теореме Вильсона. Например, наибольшее простое число, найденное с использованием теоремы Вильсона, скорее всего — 1099511628401, и даже с оптимизированным подходом к расчёту $p!$ потребуется около суток вычислений на процессорах SPARC.

Задача 1 В ячейке ниже реализуйте код функции is_prime_wilson_test(n), осуществляющий тест простоты по теореме Вильсона:

Малая теорема Ферма¶

Если $p$ — простое число и $a$ — целое число, не делящееся на $p$, то $a^{p-1}-1$ делится на $p$.

На языке теории сравнений: $a^{p-1}$ сравнимо с $1$ по простому модулю $p$. Формальная запись: $a^{p-1}\equiv 1{\pmod {p}}$

Малая теорема Ферма может быть использована для тестирования числа на простоту: если $(a^{p}-a)$ не делится на $p$, то $p$ — составное число. Однако обращение малой теоремы Ферма в общем случае неверно: если $a$ и $p$ — взаимно простые числа и $a^{p-1} - 1$ делится на $p$, то число $p$ может быть как простым, так и составным. В случае, когда $p$ является составным, оно называется псевдопростым числом Ферма по основанию $a$.

Для модулярного возведения в степень типа $a^b \mod n$ используют быстрый алгоритм, псевдокод которого приведён ниже.

На вход алгоритма поступает основание степени a, показатель степени b и целое положительное n, ао которому вычисляется модуль.

Выходом является вычисленное значение выражения $a^b \mod n$

Двоичное представление показателя степени b содержится в массиве b[]: в b[0] - младший разряд, в b[k-1] - старший

fast_modular_exponentiation(a, b, n):
1. q <- a
2. if b[0] = 0
3.   then z <- 1
4. else
5.   then z <- a
6. for i <- 1 to k-1
7.     do q <- (q * q) (mod n)
8.          if b[i] = 1 
9.             then z <- (z * q) (mod n)
10. return z

Задача 2 В ячейке ниже реализуйте код функции is_prime_ferma_test(n), осуществляющий проверку числа на простоту на основе малой теоремы Ферма. Для модулярного возведения в степень реализуйте функцию fast_modular_exponentiation(a, b, n) на основе псевдокода выше.

Проверьте, что ваш тест проваливается для чисел Кармайкла, например для наименьшего — 561.

Метод шифрования RSA с реализацией¶

Шифрование методом RSA было впервые представлено в 1978 г. Р. Райвестом, А. Шамиром и А. Адлеманом. Название было образовано по первым буквам фамилий ее основателей. RSA относится к асимметричным шифрам. В асимметричных шифрах используются два ключа – открытый и закрытый, которые создаются получателем сообщения. Открытые ключи доступны всем желающим и передаются по незащищённому каналу связи. Отправляемое сообщение шифруется открытым ключом получателя. Дешифрируется сообщение при его получении закрытым ключом получателя. Обратим внимание, что дешифрировать сообщение не может даже отправитель, что и не требуется. Открытый и закрытый ключи математически связаны друг с другом таким образом, что сообщение, зашифрованное одним ключом из пары, можно дешифрировать только вторым ключом из этой же пары ключей. RSA использует разложение больших чисел на простые множители, что требует большого объема вычислений и эта особенность определяет стойкость данного шифра.

Асимметричные криптографические системы основаны на так называемых односторонних функциях с секретом. Под односторонней понимается такая функция y=f(x), которая легко вычисляется при имеющемся x, но аргумент x при заданном значении функции вычислить сложно. Аналогично, односторонней функцией с секретом называется функция y=f(x, k), которая легко вычисляется при заданном x, причём при заданном секрете k аргумент x по заданному y восстановить просто, а при неизвестном k – сложно. Подобным свойством обладает операция возведения числа в степень по модулю:

Здесь φ(n) – φ-функция Эйлера числа n (функция Эйлера определяет количество целых положительных чисел, не превосходящих n и взаимно простых с n).

Рассмотрим первое выражение. Здесь число c получено в результате возведения в степень по модулю числа m. Назовём это действие шифрованием. Тогда m выступает в роли исходного текста, а c – шифртекста. Результат c зависит от степени e, в которую мы возводим m, и от модуля n, по которому мы получаем результат шифрования. Эту пару чисел (e, n) мы будем называть открытым ключом. Им будем шифровать сообщение.

Рассмотрим второе выражение. Здесь d является параметром, с помощью которого мы получаем исходный текст m из шифртекста c. Этот параметр мы назовём закрытым ключом и выдадим его получателю, чтобы он смог расшифровать сообщение отправителя.

Рассмотрим процесс генерации ключей. Выберем число n такое, что: $$ n\ =\ p*q, $$ где p и q – некоторые разные простые числа. Для такого n функция Эйлера имеет вид: $$ φ(n) = (p — 1)*(q — 1) $$ Такой выбор n обусловлен по следующим соображениям. Как мы могли заметить ранее, закрытый ключ d можно получить, зная открытый e. Зная числа p и q, вычислить φ-функцию Эйлера не является вычислительно сложной задачей, ровно как и нахождение обратного элемента по модулю. Однако в открытом ключе указано именно число n. Таким образом, чтобы вычислить значение φ-функции Эйлера от n (а затем получить закрытый ключ), необходимо решить задачу факторизации, которая является вычислительно сложной задачей для больших n (в современных системах, основанных на RSA, n имеет длину 2048 бит и более).

Возвращаемся к генерации ключей. Выберем целое число e: $$ e ∈ [3, φ(n)—1], \ НОД(e,φ(n)) = 1. $$ Для него вычислим число d: $$ d = e^{−1}\ mod\ φ(n) $$ Для отыскания числа, обратного по модулю, можно воспользоваться расширенным алгоритмом Евклида, рассмотренном на лекции. Теперь получатель публикует свой открытый ключ (e, n), прячет закрытый (d, n).

Рассмотрим процесс шифрования сообщения. Возьмём в качестве сообщения число m (m ∈ [1, n − 1]). Чтобы зашифровать его, необходимо возвести его в степень e по модулю n. Эти числа идут вместе с открытым ключом: $$ c = m^e\ mod\ n $$

Здесь с обозначает шифротекст, который отправитель должен передать получателю. Отметим также, что c ∈ [1, n − 1], как и m. Расшифруем шифртекст, возведя его в степень закрытого ключа d: $$ m = c^d\ mod\ n $$

Пример¶

Первым этапом асимметричного шифрования является создание получателем шифрограмм пары ключей:

• Выбирается два простых числа p и q, например p = 11 и q = 17
• Вычисляется произведение n = p*q, в нашем примере n = 11*17 = 187
• Вычисляется φ-функция Эйлера φ(n): φ(n) = (p-1)*(q-1). В нашем примере φ(n) = (11-1)*(17-1) = 160.
• Выбирается произвольное целое e: 0 < e < n взаимно простое с значением функции Эйлера φ(n). В нашем примере возьмём e = 7. Пара чисел (e, n) объявляется открытым ключом шифра. Получаем (e, n) = (7, 187)
• Вычисляется целое число d из соотношения $$ (d*e)\ mod\ φ(n) = 1. $$

Рассмотренный на лекции расширенный алгоритм Евклида для пары чисел e (7) и φ(n) (160) даст нам в качестве d значение d = 23. Пара чисел (d, n) будет закрытым ключом шифра. Получаем (d, n) = (23, 187).

RSA-шифрование сообщения T выполняется с помощью открытого ключа получателя (e, n) по формуле $$ C_i = T_i^e\ mod\ n $$

где T_i и C_i числовые эквиваленты символов исходного и зашифрованного сообщений.

Таблица 1. Числовые эквиваленты букв, цифр и символа пробела

Зашифруем строку "MIPT"

Задача 3¶

Сгенерируйте публичный и приватный ключи и зашифруйте публичным ключем свою фамилию используя одну из предложенных ниже комбинаций p и q. Для вычисления закрытого ключа d реализуйте расширенный алгоритм Евклида, рассмотренный на лекции. Для вычисления модулярного возведения в степень - функцию fast_modular_exponentiation(a, b, n) из Задачи 2:

Расшифровка RSA-закодированного сообщения T выполняется с помощью закрытого ключа получателя (d, n) по формуле

Рассмотрим пример восстановления исходного сообщения. В предыдущем примере была получена пара ключей и зашифрованное сообщение «106, 70, 135, 147», созданная открытым ключом. Воссстановим исходное сообщение, применив закрытый ключ (d, n) = (23, 187) той же пары.

Задача 4¶

Расшифруйте зашифрованное в Задаче 3 сообщение.

Цифровая подпись сообщения¶

Ещё раз напишем две ключевые формулы шифрования и расшифрования:

Теперь давайте предположим, что отправитель хочет отправить открытку m от своего имени. У него в распоряжении уже имеются два ключа (e, n) и d, которые он сгенерировал по алгоритму, описанному ранее. Поскольку d является закрытым ключом, то можно им воспользоваться как уникальным идентификатором отправителя; "зашифруем" m с помощью d: $$ s = m^d\ mod\ n $$ У получателя есть сообщение m, подпись s и открытый ключ (e, n). По аналогии с расшифрованием, проверка подписи осуществляется возведением подписи s в степень открытой экспоненты e: $$ m' = s^e\ mod\ n. $$ Если m = m', то подпись считается правильной.

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

• Вычисляется хэш функция документа (необратимое приобразование входного потока байт произвольной длины в значение фиксированного размера при помощи специального алгоритма, CRC32, SHA-256, MD5)
• Полученное значение зашифровывается приватным ключем отправителя и прикладывается к документу
• Получатель документа вычисляет хэш значание документа тем же алгоритмом что и отправитель
• Получатель документа расшифровывает цифровую подпись публичным ключем отправителя и сравнивает со значением? вычисленным на предыдущем шаге. Их совпадение гарантирует, что автором документа является отправитель и в документ не вносились изменения посторонними лицами.

Задача 5¶

Используя функцию crc32 модуля zlib (как показано ниже) вычислите цифровую подпись своей фамилии и убедитесь в ее правильности. Для шифрования и расшифрования используйте пару ключей из задачи 3 и 4.

>>> import zlib
>>> data='Hello world'
>>> s=hex(zlib.crc32(data.encode('utf-8')))
>>> print(s)
0x8bd69e52