Рубрика: Безопасность

Пусть «n» и «e» — натуральные числа. Функция «f», реализующая RSA, устроена следующим образом:

f: x → x^e(mod n) (1)

Для расшифровки сообщения достаточно решить сравнение:

x^e = a(mod n) (2)

При некоторых условиях на «n» и «e» это сравнение имеет единственное решение «x». Для этого воспользуемся функцией Эйлера. Эта функция натурального аргумента «n» обозначается φ(n) и равняется количеству целых чисел на отрезке от 1 до «n», взаимно простых с «n». Так φ(1) = 1 и φ(p^r) = p^r-1(p-1) для любого простого числа «p» и натурального числа «r». Кроме того, φ(ab) = φ(a)φ(b) для любых натуральных взаимно простых чисел «a» и «b». Эти свойства позволяют легко вычислять значения φ(n), если известно разложение числа «n» на простые сомножители.

Если показатель степени «e» в (2) взаимно прост с φ(n), то (2) имеет единственное решение. Для того, чтобы его найти, определим целое число «d», удовлетворяющее условию:

de ≡ 1(mod φ(m)), 1 ≤ d ≤ φ(n) (3)

Такое число существует и оно единственное, т.к. (e, φ(n)) = 1. Классическая теорема Эйлера утверждает, что для каждого числа «x», взаимно простого с  «n», выполняется сравнение: x^φ(n) ≡ 1(mod n) и следовательно a^d ≡ x^ed ≡ x(mod n).

Таким образом, единственное решение сравнения (2) может быть найдено в виде:

x ≡ a^d(mod n) (4)

В RSA n = p*q, т.к. φ(n) = φ(p*q) = (p-1)(q-1) (5), то единственное условие на выбор показателя степени «e» в отображении (1) есть (e, p-1) = (e, q-1) = 1 (6).

В итоге: выбирается число «e», удовлетворяющее условиям (6), вычисляется с помощью (5) число φ(n) и с помощью (3) — число «d». Любой может зашифровать сообщение через (1), а расшифровать через (4).

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

Шифруемый текст можно разбить на блоки «P», так, что 0 < P < n. Это можно сделать, если блоки будут по «k»-бит, где  «k» — максимально целое число, для которого 2^k < n.

Пусть имеется открытый ключ (n,e) и закрытый ключ (n,d). Нужно доказать, что для любого целого числа «b» (0 ≤ b ≤ n) выполняется тождество: D(E(b)) = b. Достаточным будет доказать даже следующее: D(E(b)) ≡ b(mod n).

Действительно, как «b», так и D(E(b)) — неотрицательные целые числа, которые меньше «n», поэтому они сравнимы по модулю «n» тогда и только тогда, когда они равны (это объясняет и то, почему блоки разбиваются на < n). Из «рецептов» шифрования и дешифрования следует, что:

D(E(b)) ≡ (b^e)^d ≡ b^ed(mod n) (1)

Поскольку элементы «d» и «e» взаимно обратны по модулю φ(n), найдется также натуральное «k», что ed = 1 + kφ(n). Более того, по условию, числа «d» и «e» больше 2 и φ(n) > 0. Следовательно, k > 0. Подставляя  1 + kφ(n) вместо произведения «ed» в уравнение (1), получаем:

b^ed ≡ b^1+kφ(n) ≡ (b^φ(n))^k b(mod n)

Теперь воспользуемся теоремой Эйлера, которая утверждает, что b^φ(n) ≡ 1(mod n). Отсюда b^ed ≡ b(mod n), т.е.

D(E(b)) ≡ b(mod n)

Еще надо убедится в простоте чисел «b» и «n» (n = p*q). Определим вычеты числа b^ed по модулям «p» и «q». Мы уже убедились в том, что: ed = 1 + kφ(n) = 1 + k(p-1)(q-1) для некоторого целого k > 0. Следовательно:

b^ed ≡ b(b^(p-1))^k(q-1) (mod n)

Тогда по теореме Эйлера: b^(p-1) ≡ 1(mod p), и получается b^ed ≡ b(mod p), и b^ed ≡ b(mod q). Другими словами, b^ed — «b» делится и на «p», и на «q», но НОД (p,q) = 1. Т.к. n = p*q, то b^ed ≡ b(mod n), т.е. D(E(b)) ≡ b(mod n).

Что и следовало доказать.

Источник: С.Коутинхо «Введение в теорию чисел алгоритма RSA».

В прошлом семестре у меня была дисциплина, под названием «Защита информации», очень интересная, я вам скажу. Лекции вел чумовой препод, который знал все тонкости современного IT, и поэтому слушать его было одно удовольствие. Да-да, приятно слушать того, который разбирается в чем-то современном, говорит о новых технологиях и готов дискутировать на эту тему. К сожалению, за все время обучения в университете, я видел несколько преподавателей, которые могли этими качествами похвастаться. Остальные же засели где-то глубоко в древности, рассказывая про технологии 60-х годов. Как бы это не было печально, но такое у нас в стране высшее образование.

И так, я продолжаю. Практику по «Защите информации» вел ассистент, который любил (по-крайней мере у меня) докапываться до основания, что делает тот или иной алгоритм. Хуже всего пришлось мне с алгоритмом шифрования RSA. Как буд-то ничего сложного в нем нет, задание было реализовать данный алгоритм на каком-нибудь языке программирования. Когда сдавал, ассистент начал задавать вопросы не про то, как реализован алгоритм, а про то, почему этот алгоритм работает. Т.е. начал рыть под самый корень возникновения RSA. Я, как не пытался, ответить не смог, поэтому получил предложения поискать ответы в литературе. На следующий день я уже был вооружен тремя статьями об RSA с математической моделью описания. В итоге, ассистенту я все успешно сдал и получил допуск к экзамену.

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

RSA — очень хороший алгоритм шифрования, основанный на использовании открытого и закрытого ключей. Если кратко, то вот его суть:

1. Берутся два простых числа (т.е. такое, которые имеют всего два общих делителя — самого себя и единицу) большой длины (к примеру, 1024 бит, а это 128 десятичных знаков). Пусть эти числа будут называться «p» и «q».
2. Затем эти числа необходимо перемножить: n = p*q (если взяли число, равное 1024 бит, то длина «n» будет равна 256 десятичных знаков, многовато, правда?). «n» называется модулем.
3. Потом делается такая махинация: f(n) = (p-1)*(q-1), где f(n) — это функция Эйлера. Если кратко, то функция Эйлера равняется количеству простых чисел на отрезке от 1 до «n», взаимно простых с «n».
4. Выбирается такое число «e» (его называют открытой экспонентой), которое будет являться взаимно простым с f(n) (т.е. «d» и f(n) должны иметь лишь один общий делитель, равный 1).
5. Ищется число «d» (его называют закрытой экспонентой), мультипликативно обратное к числу «e» по модулю f(n). Число «d» можно легко найти, если использовать расширенный алгоритм Евклида.

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

Шифрование
Есть пара чисел (e,n), которые образуют открытый ключ, тогда шифрование будет представляться следующим образом: C = M^e(mod n), где M — то, что шифруем.

Дешифрование
Есть пара чисел (d,n), которые образуют закрытый ключ, тогда дешифрование будет представляться следующим образом: M = C^d(mod n).

Алгоритм RSA также нашел широкое применение и в качестве цифровой подписи. Тут тоже никаких сложностей не возникает. Сначала берется исходный файл, вычисляется его хэш-функция, потом хэш-функция шифруется с помощью закрытого ключа (d,n), и передается вместе с исходным файлом получателю. Стоит заметить, что исходный файл не шифруется, ибо нам этого и не надо, ведь цифровая подпись нужна для подтверждения того, что передаваемые данные (исходный файл) являются достоверными. Получатель в начале вычисляет хэш-функцию от полученного исходного файла, затем расшифровывает полученную цифровую подпись с помощью открытого ключа (e,n) и сравнивает хэши между собой. Если они совпадают, то все в порядке, цифровая подпись является настоящей.

Вот так все легко и просто. С математической точки зрения все гораздо сложнее, но об этом как-нибудь в следующий раз.