RSS
 

Записи по метке ‘rsa’

Еще одно доказательство работы RSA

21 Янв

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

f: x → xe(mod n) (1)

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

xe = a(mod n) (2)

При некоторых условиях на «n» и «e» это сравнение имеет единственное решение «x». Для этого воспользуемся функцией Эйлера. Эта функция натурального аргумента «n» обозначается φ(n) и равняется количеству целых чисел на отрезке от 1 до «n», взаимно простых с «n». Так φ(1) = 1 и φ(pr) = pr-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) и следовательно ad ≡ xed ≡ x(mod n).

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

x ≡ ad(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 c математической точки зрения

21 Янв

Рассуждения, приводимые ниже, рассказывают о том, почему алгоритм шифрования 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)) ≡ (be)d ≡ bed(mod n) (1)

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

bed ≡ b1+kφ(n) ≡ (bφ(n))k b(mod n)

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

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

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

bed ≡ b(b(p-1))k(q-1) (mod n)

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

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

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

 
Нет комментариев

Опубликовано в рубрике Безопасность

 

Об алгоритме шифрования RSA

18 Янв

В прошлом семестре у меня была дисциплина, под названием «Защита информации», очень интересная, я вам скажу. Лекции вел чумовой препод, который знал все тонкости современного 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 = Me(mod n), где M – то, что шифруем.

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

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

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

 
Комментариев: 7

Опубликовано в рубрике Безопасность