Об алгоритме шифрования 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 = Me(mod n), где M - то, что шифруем.

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

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

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

  • Какие новые технологии ты имел ввиду, говоря о преподавателе?

  • Под новыми технологиями я подразумеваю те, которые используются активно последние лет десять. Конечно, назвать технологию, которая появилась, к примеру, в 2001 году, назвать трудно, но если абстрагироваться и брать период в полвека, то уже можно смело называть новыми.

    У нас препод есть, который любит рассказывать про дискретное косинусное преобразование (ДКП), мат.часть он знает прекрасно. Но я уверен, если спросить, как используется ДКП в JPG, то он ответить не сможет. Мне куда интереснее было бы слушать после небольшой мат.части реальное применение, чем целый семестр слушать нудные вещи...

  • Красильников хорошо знал как используется ДКП 😉
    На чем RSA реализовывал?

  • Ну, Красильников может быть, не спорю. Но я про другого препода говорил.

    Реализовывал на Java, правда, без помощи code.google не обошлось =)

  • странно) я на все на pure java делал

  • Ты числа "p" и "q" какой длины брал? 1024 бита?
    У меня эти числа были маленькие (по 64 бита) для простоты реализации, препод не придирался.

  • Да, 1024, все по-взрослому. Даже код где-то сохранился.

  • Хрен

    Никакой конкретики. Хватит зарабатывать на блогах! Пишите нормально!