Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

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

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

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

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

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

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

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

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

прошествии зашифрованная информация перестает представлять интерес для лиц, использующих отображение [pic] в качестве шифра.

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

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

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

[pic].

(1)
Для расшифровки сообщения [pic] достаточно решить сравнение

[pic]. (2)
При некоторых условиях на [pic] и [pic] это сравнение имеет единственное решение [pic].

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

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

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

[pic].

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

[pic].

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

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

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

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

Рекомендуем скачать другие рефераты по теме: оценка реферата, диплом на тему.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки