Шифрование -- отображение
E: Zm --> Zm Encryption
сообщение x <- Zm
y = E(x) -- зашифрованное сообщение
Для расшифровки надо знать
обратное отображение
D: Zm --> Zm Decription
D*E = 1
x = D(y)
Схема RSA (Rumley, Shamir, Adleman из MIT)
Основана на элементарной теории чисел
1. Расширенный алгоритм Евклида (позволяет
вычислить обратный элемент в Zm)
2. Китайская теорема об остатках
m = m1 * m2 * ... *m_k
gcd(m_i, m_j) = 1 при i != j
то
Zm == Zm1 + Zm2 + ... + Zmk
Пример:
Z_105 105 = 3*5*7
Z_105 == Z3 + Z5 + Z7
x, y <- Z_105
x = 19 y = 53
x == (1, 4, 5)
y == (2, 3, 4)
x+y == (0, 2, 2)
72 == (0, 2, 2)
Корни из 1 в Z_105
(1, 1, 1)
(-1, 1, 1)
(1, -1, 1)
(-1, -1, 1)
. . .
(-1, -1, -1)
=======================================
Малая теорема Ферма
Пусть p -- простое число
b -- любое число: b != 0 (mod p)
Тогда
b^(p-1) == 1 (mod p)
========================================
Другая форма Малой теоремы Ферма
Для любого основания b
b^p == b (mod p)
И даже для любого k > 0
b^(k*(p-1) + 1) == b (mod p)
====================================
Теорема Эйлера
m не обязательно простое.
Пусть b обратимо в Zm (взаимно просто с m)
Обозначим фи от m
phi(m)
порядок группы обратимых элементов кольца Zm
Пусть b обратимо в Zm. Тогда
b^phi(m) == 1 (mod 1)
=======================================
Частный случай случай теоремы Эйлера
Пусть m свободно от квадратов
m = p1 * p2 * p3 * ... * p_s
(m -- произведение различных простых чисел).
Тогда для любого b и любого целого k > 0
b^(k*phi(m) + 1) == b (mod m)
(вытекает из Малой теоремы Ферма и
Китайской теоремы об остатках).
Вычисление функции Эйлера
Пусть m = p^e
Сколько в кольце Z_m обратимых элементов?
Число необратимых = p^e/p = p^(e-1)
Число обратимых = число всех - число необратимых =
= p^e - p^(e-1) =
= (p - 1)*p^(e - 1)
Тогда для
m = p1^e1 * ... * p_s^e_s
phi(m) = (p1-1)*p^(e1-1) *... * (p_s-1)*p_s^(e_s-1)
Для m, свободного от квадратов
m = p1 * p2 * ... * p_s
phi(m) = (p1 - 1)*(p2 - 1)* ... *(p_s - 1)
В частности, для m = p*q, где p, q -- простые
phi(m) = (p - 1)*(q - 1)
Применив частный случай теоремы Эйлера
==========================
Частный случай случай теоремы Эйлера
Пусть m свободно от квадратов
m = p1 * p2 * p3 * ... * p_s
Тогда для любого b и любого целого k > 0
b^(k*phi(m) + 1) == b (mod m)
==================================
получим
b^(k*(p-1)(q-1) + 1) == b (mod m)
======================================
Схема RSA
m = p * q
где p, q -- большие простые числа
Число m открыто, его разложение на множители
секретно (p, q не известны широкой публике)
phi(m) = (p - 1)(q - 1) -- секретно
Берем любое число e, обратимое в Z_phi(m)
Открытый ключ -- пара (m, e)
Пусть d -- обратный к e элемент в Z_phi(m)
d*e = 1 (mod phi(m))
Секретный ключ -- пара (m, d)
Шифрование:
E: Zm --> Zm
E: x --> x^e (mod m)
Дешифровка:
E: Zm --> Zm
E: y --> y^d (mod m)
Докажем, что D*E = 1
y = E(x) = x^e (mod m)
D(y) = D(x^e) = (x^e)^d = x^(e*d) =
e*d = 1 (mod phi(m))
e*d = k*phi(m) + 1
== x^(k*phi(m) + 1) == x (mod m)
Пример:
p = 997
q = 1021
m = p*q = 1017937
phi(m) = (p-1)*(q-1) = 1015920
e = 1019
d = 574259
открытый ключ (1017937, 1019)
секретный ключ (1017937, 574259)
Шифруем x = 123456
>>> x = 123456
>>> y = pow(x, e, m)
>>> y
220548
Зашифрованное сообщение y = 220548
Расшифровать может только
обладатель секретного ключа
>>> z = pow(y, d, m)
>>> z
123456
Для того, чтобы, зная m, e, вычислить
секретный ключ d, надо знать функцию Эйлера
phi(m) = (p-1)*(q-1)
а для этого надо знать разложение числа m
на множители.
Закон распределения простых чисел
Формула Чебышева
pi(n) -- количество простых чисел < n
Теорема Чебышева
pi(n) ~ n/ln(n)
В среднем в отрезке длины ln(n) содержится одно простое число
>>> log(1000000)
13.815510557964274
Каждое 14-е число около миллиона простое.
Вероятностный тест Миллера-Рабина
Выдает для числа m один из 2-х ответов:
1) m -- составное число;
2) не знаю.
При ответе (1) выдается и доказательство того,
что число простое.
Вероятность ответа (2) для составного числа <= 1/4.
Идея теста основана на Малой теореме Ферма.
Если
m -- простое число, b != 0 (mod m) -- любое
ненулевое число в кольце Z_m,
то
b^(m-1) == 1 (mod m)
Верно ли обращение Малой теоремы Ферма?
Древние греки ошибались, считая, что, если даже для
основания b = 2 выполняется сравнение
b^(m-1) == 1 (mod m),
то m простое.
Примеры, подтверждающие их заблуждение:
>>> 2 ** 14 % 15
4
Значит, число 15 не простое;
>>> 2 ** 26 % 27
13
Значит, число 27 не простое.
Пьер Сарруз (Франция, 1830) первым нашел
контрпример к обращению Малой теоремы Ферма:
Число 341 = 31*11 не простое, но
2^340 == 1 (mod 341)
Посчитаем:
2^340 = (2^10) ^ 34 = 1024 ^ 34 =
= (3*341 + 1) == (1) ^ 34 == 1 (mod 341)
Однако для основания b = 3 Малая теорема Ферма для числа
341 не выполняется:
3^340 == 56 (mod 341)
>>> 3 ** 340 % 341
56
Самый маленький подобный контрпример -- это
число 91 = 7*13 для основания 3:
3^90 == 1 (mod 91)
Действительно,
3^90 = (3^6)^15 = 729^15 =
= (8*91+1)^15 == 1^15 == 1 (mod 91)
В 1910 г. Роберт Кармайкл (США) нашел удивительное число 561,
которое ведет себя как простое в Малой теореме Ферма, но
не является простым.
561 = 3 * 11 * 17
>>> 2 ** 560 % 561
1
>>> 41 ** 560 % 561
1
>>> 100 ** 560 % 561
1
Чиcло m называется кармайкловым, если
для любого основания b, взаимно простого с m,
(т.е. gcd(b, m) = 1), выполняется утверждение
Малой теоремы Ферма:
b^(m-1) == 1 (mod m)
Теорема
m кармайклово <==> m = p1*p2*...*p_k, где k >= 3
и для всякого i
(p_i - 1) | (m - 1)
Проверим m = 561 = 3 * 11 * 17
3 - 1 = 2 | 560
11 - 1 = 10 | 560
17 - 1 = 16 | 560
Первые кармайкловы числа -- это 560, 1105, 1729, ...
Их бесконечно много.
Идея теста Миллера -- Рабина:
m -- нечетное число
b -- случайное число
Вычисляем b^(m-1) по модулю m следующим образом:
Так как m-1 -- четное число, то
m - 1 = t * 2^s
где t -- нечетное число.
Сначала вычисляем b^t (mod m) и потом
полученное число s раз возводим в квадрат.
Получаем последовательность
b^t, (b^t)^2, (b^t)^4, (b^t)^8, ..., b^(m-1)
=======================================
s раз
Если послевательность не заканчивается единицей
*, *, ..., *, y != 1 (mod m)
или имеет вид
*, *, ..., *, 1, 1, ..., 1
то число составное. Здесь * -- любое число,
отличное от плюс-минус 1.
Ответ "скорее всего, простое" выдается, когда
последовательность имеет один из двух видов:
1, 1, 1, ..., 1
или
*, *, ..., *, -1, 1, ..., 1
Теорема: вероятность ответа "число составное"
(последовательность имеет вид либо
*, *, ..., *, y != 1
либо
*, *, ..., *, 1, 1, ..., 1
) для составного m >= 3/4
Пример:
Проверим, что третье кармайклово число m = 1729
составное.
m - 1 = 1728
1728 = 27 * 2^6 =
27 * 64 = (30 - 3)*64 = 1920 - 192 = 1728
Берем основание b = 2
2^27 (mod 1729) = 645
>>> pow (2, 27, 1729)
645
645*645 % 1729 = 1065
>>> 645*645 % 1729
1065
1065*1065 % 1729 = 1
>>> 1065*1065 % 1729
1
Итак, последовательность имеет вид
654, 1065, 1, 1, 1, 1, 1
=======
Значит, m = 1729 не является простым числом.
Китайская теорема об остатках
==============================
Пусть
m = m1 * m2 * ... * m_k,
где числа m_i взаимно простые, gcd(m_i, m_j) = 1.
Тогда кольцо вычетов по модулю m изоморфно прямой сумме
колец вычетов по модулю m_i:
Z_m == Z_m1 + Z_m2 + ... + Z_m_k
x == (x1, x2, ..., x_k), где x_i == x (mod m_i)
Алгоритм:
дан набор взаимно простых чисел m1, m2, ..., m_k
и остатков r1, r2, ..., r_k.
Надо найти число x такое, что
x == r_i (mod m_i)
Идея: пусть мы нашли число x в кольце Z_m1*m2*...*m_s, где s < k
x == r_i (mod m_i) для i <= s
Подправим его так, чтобы
x == r_i (mod m_i) для i <= s + 1
x' = x + t*m1*m2*...*m_s
Найдем t из условия
x' == r_s+1 (mod m_s+1)
x + t*m1*m2*...*m_s == r_s+1 (mod m_s+1)
Число m1*m2*...*m_s обратимо в кольце Z_m_s+1
Применив расш. алгоритм Евклида, найдем обратный элемент u:
u*m1*m2*...*m_s == 1 (mod m_s+1)
Умножим уравнение на u:
u*(x + t*m1*m2*...*m_s) == u*r_s+1 (mod m_s+1)
u*x + t == u*r_s+1 (mod m_s+1)
t = u*(r_s+1 - x) (mod m_s+1)
Мы вычислили x' = x + t*m1*m2*...*m_s