В прошлом семестре у меня была дисциплина, под названием «Защита информации», очень интересная, я вам скажу. Лекции вел чумовой препод, который знал все тонкости современного 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) и сравнивает хэши между собой. Если они совпадают, то все в порядке, цифровая подпись является настоящей.
Вот так все легко и просто. С математической точки зрения все гораздо сложнее, но об этом как-нибудь в следующий раз.