Занятие 1

Занятие 1: Асимптотическая сложность алгоритмов. Тестирование простоты чисел и факторизация

Цель: Вспомнить основные конструкции языка и алгоритмы класса bruteforce

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

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

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

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

Напишите тест простоты по теореме Вильсона:

In [1]:
def is_prime_wilson_test(n):
    pass  # FIXME


x = int(input("Enter the number to test:"))
if is_prime_wilson_test(x):
    print(f"{x} is a prime number!")
else:
    print(f"{x} is not a prime number.")

Enter the number to test:214

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

Если $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 оценивается как O(log2n × log log n × log log log n), где n — проверяемое число. Обычно проводится несколько проверок с различными a.

In [1]:
def is_prime_ferma_test(n):
    pass  # TODO: check Ferma test with several numbers a


x = int(input("Enter the number to test:"))
if is_prime_ferma_test(x):
    print(f"{x} is probably a prime number!")
else:
    print(f"{x} is not a prime number.")

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

In [ ]:

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

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

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

$$ c = f(m) = {m^e}\ mod\ n $$$$ m = {f^{-1}}(c) = {c^d}\ mod\ n $$$$ (d * e)\ mod\ φ(n) = 1 $$

Здесь φ(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.

Рассмотрим процесс шифрования сообщения. Возьмём в качестве сообщения число 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 и d на значение функции Эйлера должно быть число 1. Поэтому d можно рассчитать по формуле $$ d = (k*φ(n)+1)/e, $$

Перебираем последовательно значения k = 1, 2, 3,.. до тех пор, пока не будет получено целое число d. Найдём d в рассматриваемом примере: при k = 1, d = 23. Пара чисел (d, n) будет закрытым ключом шифра. Получаем (d, n) = (23, 187).

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

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

Таблица 1. Числовые эквиваленты букв, цифр и символа пробела
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
27 28 29 30 31 32 33 34 35 36 37
0 1 2 3 4 5 6 7 8 9 пробел

Зашифруем строку "MIPT"
Символы исходного сообщения, Ti Коды символов Ti Зашифрованные коды символов Ci
M 13 13^7 mod 187 = 106
I 9 9^7 mod 187 = 70
P 16 16^7 mod 187 = 135
T 20 20^7 mod 187 = 147

Задание 1

Сгенерируйте публичный и приватный ключи и зашифруйте публичным ключем свою фамилию используя одну из предложенных ниже комбинаций p и q:
Вариант p q Вариант p q
1 19 73 14 71 79
2 29 73 15 19 43
3 17 29 16 13 61
4 23 61 17 41 79
5 13 31 18 13 53
6 23 31 19 59 61
7 53 73 20 13 83
8 31 37 21 13 19
9 17 37 22 19 29
10 23 79 23 17 67
11 13 41 24 13 17
12 23 41 25 31 73
13 17 41 26 31 67
In [ ]:

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

$$ T_i = {C_i^d}\ mod\ n $$

Рассмотрим пример восстановления исходного сообщения. В предыдущем примере была получена пара ключей и зашифрованное сообщение «106, 70, 135, 147», созданная открытым ключом. Воссстановим исходное сообщение, применив закрытый ключ (d, n) = (23, 187) той же пары.
Зашифрованные коды символов Ci Дешифрованные коды символов Ti Символы исходного сообщения, Ti
106 106^23 mod 187 = 13 M
70 70^23 mod 187 = 9 I
135 135^23 mod 187 = 16 P
147 147^23 mod 187 = 20 T

Задание 2

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

In [ ]:

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

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

$$ c = m^e\ mod\ n $$$$ m = c^d\ mod\ n $$

Теперь давайте предположим, что отправитель хочет отправить открытку 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)
  • Полученное значение зашифровывается приватным ключем отправителя и прикладывается к документу
  • Получатель документа вычисляет хэш значание документа тем же алгоритмом что и отправитель
  • Получатель документа расшифровывает цифровую подпись публичным ключем отправителя и сравнивает со значением? вычисленным на предыдущем шаге. Их совпадение гарантирует, что автором документа является отправитель и в документ не вносились изменения посторонними лицами.

Задание 3

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

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