ДИПЛОМНАЯ РАБОТА на тему Применение алгоритма RSA при шифровании. Применение алгоритма rsa при шифровании потоков данных

• Название: Применение алгоритма rsa при шифровании потоков данных
• Дата: 18.12.2022
• Размер: 1.17 Mb.
• Имя файла: ДИПЛОМНАЯ РАБОТА на тему Применение алгоритма RSA при шифровании.doc
• Тип: Диплом; #851138
• страница: 2 из 7

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

. (1)

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

. (2)

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

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

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

. (3)

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

. (4)

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

. (5)

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

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

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

Авторы схемы RSA предложили выбирать число в виде произведе­ния двух простых множителей и , примерно одинаковых по величине. Так как

, (6)

то единственное условие на выбор показателя степени в отображении (1) есть

. (7)

Итак, лицо, заинтересованное в организации шифрованной переписки с помощью схемы RSA, выбирает два достаточно больших простых числа и . Перемножая их, оно находит число . Затем выбирается число , удовлетворяющее условиям (7), вычисляется с помощью (6) число и с помощью (3) - число . Числа и публикуются, число остается секретным. Теперь любой может отправлять зашифрованные с помощью (1) сообщения организатору этой системы, а организатор легко сможет расшифровывать их с помощью (5).

Для иллюстрации своего метода Ривест, Шамир и Адлеман зашифро­вали таким способом некоторую английскую фразу. Сначала она стан­дартным образом (а=01, b=02, .... z=26, пробел=00) была записана в виде целого числа , а затем зашифрована с помощью отображения (1) при

m=11438162575788886766932577997614661201021829672124236256256184293570 6935245733897830597123563958705058989075147599290026879543541

и . Эти два числа были опубликованы, причем дополнительно сообщалось, что . где и - простые числа, записываемые со­ответственно 64 и 65 десятичными знаками. Первому, кто расшифрует соответствующее сообщение

,

была обещана награда в 100$.

Эта история завершилась спустя 17 лет в 1994 г., когда D. Atkins, M. Graff, А. К. Lenstra и Р. С. Leyland сообщили о расшифровке фразы. Числа и оказались равными

,

.

Этот замечательный результат (разложение на мно­жители 129-значного десятичного числа) был достигнут благодаря ис­пользованию алгоритма разложения чисел на множители, называемого методом квадратичного решета. Выполнение вычислений потребовало колоссальных ресурсов. В работе, возглавлявшейся четырьмя авторами проекта, и продолжавшейся после предварительной теоретической под­готовки примерно 220 дней, на добровольных началах участвовало около 600 человек и примерно 1600 компьютеров, объединённых сетью Inter­net. Наконец, отметим, что премия в 100$ была передана в Free Software Foundation.

2.2.Сложность теоретико-числовых алгоритмов

Сложность алгоритмов теории чисел обычно принято измерять коли­чеством арифметических операций (сложений, вычитаний, умножений и делений с остатком), необходимых для выполнения всех действий, пред­писанных алгоритмом. Впрочем, это определение не учитывает величины чисел, участвующих в вычислениях. Ясно, что перемножить два стозначных числа значительно сложнее, чем два однозначных, хотя при этом и в том, и в другом случае выполняется лишь одна арифметическая опе­рация. Поэтому иногда учитывают ещё и величину чисел, сводя дело к так называемым битовым операциям, т. е. оценивая количество необхо­димых операций с цифрами 0 и 1, в двоичной записи чисел.

Говоря о сложности алгоритмов, мы будем иметь в ви­ду количество арифметических операций. При построении эффективных алгоритмов и обсуждении верхних оценок сложности обычно хватает ин­туитивных понятий той области математики, которой принадлежит алго­ритм. Формализация же этих понятий требуется лишь тогда, когда речь идёт об отсутствии алгоритма или доказательстве нижних опенок слож­ности.

Приведем теперь примеры достаточно быстрых алгоритмов с опен­ками их сложности. Здесь и в дальнейшем мы не будем придерживаться формального описания алгоритмов, стараясь в первую очередь объяснить смысл выполняемых действий.

Следующий алгоритм вычисляет за арифмети­ческих операций. При этом, конечно, предполагается, что натуральные числа и не превосходят по величине .

2.2.1. Алгоритм вычисления

1. 
   Представим в двоичной системе счисления , где , цифры в двоичном представлении, равны 0 или 1, .
   
2. 
   Положим и затем для вычислим
   

.

3) есть искомый вычет .

Справедливость этого алгоритма вытекает из сравнения