Реферат: Применение алгоритма RSA для шифрования потоков данных

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

2. АЛГОРИТМ RSA

Труды Евклида и Диофанта, Ферма и Эйлера, Гаусса, Чебышева и Эрмита содер­жат остроумные и весьма эффективные алгоритмы решения диофантовых уравнений, выяснения разрешимости сравнений, построения больших по тем временам простых чисел, нахождения наилучших приближений и т.д. В последние два десятилетия, благодаря в первую очередь запросам криптографии и широкому распространению ЭВМ, исследова­ния по алгоритмическим вопросам теории чисел переживают период бур­ного и весьма плодотворного развития.

Вычислительные машины и электронные средства связи проникли практически во все сферы человеческой деятельности. Немыслима без них и современная криптография. Шифрование и дешифрование текстов можно представлять себе как процессы переработки целых чисел при помощи ЭВМ, а способы, которыми выполняются эти операции, как неко­торые функции, определённые на множестве целых чисел. Всё это делает естественным появление в криптографии методов теории чисел. Кроме того, стойкость ряда современных криптосистем обосновывается только сложностью некоторых теоретико-числовых задач.

Но возможности ЭВМ имеют определённые границы. Приходится раз­бивать длинную цифровую последовательность на блоки ограниченной длины и шифровать каждый такой блок отдельно. Мы будем считать в дальнейшем, что все шифруемые целые числа неотрицательны и по вели­чине меньше некоторого заданного (скажем, техническими ограничени­ями) числа m. Таким же условиям будут удовлетворять и числа, получае­мые в процессе шифрования. Это позволяет считать и те, и другие числа элементами кольца вычетов . Шифрующая функция при этом может рассматриваться как взаимнооднозначное отображение колец вычетов

а число представляет собой сообщение в зашифрованном виде.

Простейший шифр такого рода - шифр замены, соответству­ет отображению при некотором фиксированном целом k. Подобный шифр использовал еще Юлий Цезарь. Конечно, не каждое отображение подходит для целей надежного сокрытия инфор­мации.

В 1978 г. американцы Р. Ривест, А. Шамир и Л. Адлеман (R.L.Rivest. A.Shamir. L.Adleman) предложили пример функции , обла­дающей рядом замечательных достоинств. На её основе была построена реально используемая система шифрования, получившая название по пер­вым буквам имен авторов -система RSA. Эта функция такова, что

1) существует достаточно быстрый алгоритм вычисления значений ;

2) существует достаточно быстрый алгоритм вычисления значений об­ратной функции ;

3) функция обладает некоторым «секретом», знание которого позво­ляет быстро вычислять значения ; в противном же случае вычисле­ние становится трудно разрешимой в вычислительном отношении задачей, требующей для своего решения столь много времени, что по его
прошествии зашифрованная информация перестает представлять инте­рес для лиц, использующих отображение в качестве шифра.

Еще до выхода из печати статьи копия доклада в Массачусетском Технологическом институте, посвящённого системе RSA. была послана известному популяризатору математики М. Гарднеру, который в 1977 г. в журнале Scientific American опубликовал статью посвящённую этой системе шифрования. В русском переводе заглавие статьи Гарднера зву­чит так: Новый вид шифра, на расшифровку которого потребуются мил­лионы лет. Именно эта статья сыграла важнейшую роль в распростране­нии информации об RSA, привлекла к криптографии внимание широких кругов неспециалистов и фактически способствовала бурному прогрессу этой области, произошедшему в последовавшие 20 лет.

2.1. система шифрования RSA

Пусть и натуральные числа. Функция реализующая схему RSA, устроена следующим образом

. (1)

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

. (2)

При некоторых условиях на и это сравнение имеет единственное решение .

Для того, чтобы описать эти условия и объяснить, как можно найти решение, нам потребуется одна теоретико-числовая функция, так назы­ваемая функция Эйлера. Эта функция натурального аргумента обозна­чается и равняется количеству целых чисел на отрезке от 1 до , взаимно простых с . Так и для любого простого числа и натурального . Кроме того, для лю­бых натуральных взаимно простых и . Эти свойства позволяют легко вычислить значение , если известно разложение числа на простые сомножители.

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

. (3)

Такое число существует, поскольку , и притом единствен­но. Здесь и далее символом будет обозначаться наибольший общий делитель чисел и . Классическая теорема Эйлера, утверждает, что для каждого числа , взаимно простого с , выполняется сравнение и, следовательно.

. (4)

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

. (5)

Если дополнительно предположить, что число состоит из различных простых сомножителей, то сравнение (5) будет выполняться и без предпо­ложения . Действительно, обозначим и . Тогда делится на , а из (2) следует, что . Подобно (4), теперь легко находим . А кроме того, имеем . Получившиеся сравнения в силу дают нам (5).

Функция (1), принятая в системе RSA, может быть вычислена доста­точно быстро. Обратная к функция вычисляется по тем же правилам, что и , лишь с заменой показателя степени на . Таким образом, для функции (1) будут выполнены указанные выше свойства 1) и 2).

Для вычисления функции (1) достаточно знать лишь числа и . Именно они составляют открытый ключ для шифрования. А вот для вы­числения обратной функции требуется знать число . оно и является «се­кретом», о котором речь идёт в пункте в). Казалось бы. ничего не стоит. зная число . разложить его на простые сомножители, вычислить затем с помощью известных правил значение и, наконец, с помощью (3) определить нужное число . Все шаги этого вычисления могут быть реа­лизованы достаточно быстро, за исключением первого. Именно разложе­ние числа на простые множители и составляет наиболее трудоемкую часть вычислений. В теории чисел несмотря на многолетнюю её историю и на очень интенсивные поиски в течение последних 20 лет, эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до , и. деля на них , найти требуемое разложение. Но, учитывая, что количество простых в этом промежутке, асимптотически равно , на­ходим, что при , записываемом 100 десятичными цифрами, найдётся не менее простых чисел, на которые придётся делить при разложе­нии его на множители. Очень грубые прикидки показывают, что компью­теру, выполняющему миллион делений в секунду, для разложения числа таким способом на простые сомножители потребуется не менее, чем лет. Известны и более эффективные способы разложения целых чисел на множители, чем простой перебор простых делителей, но и они работают очень медленно.