Криптография - это наука, занимающаяся построением безопасных шифров, т.е. алгоритмов, обеспечивающих преобразование электронных документов в нечитаемый набор символов, из которого можно восстановить исходный документ только зная некоторый пароль (секретное слово). Криптография развивалась с самого начала истории человечества. Известны примеры шифрования текстов из глубокой древности - у римлян, греков и других народов. Однако эра современной криптографии началась сравнительно недавно, в 70-е годы XX столетия. Приведем здесь основные события тех лет. В 1977 г. трое ученых Рональд Райвест (Ronald Linn Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman) из Массачусетского Технологического Института (MIT) опубликовали в журнале Scientific American новый алгоритм шифрования, основанный на идее двухключевого шифрования, названный по первым буквам фамилий авторов методом RSA. В этом методе известным параметром служит некоторое целое число n большой длины (обычно 1024 или 2048 бита), являющееся произведением двух простых чисел p и q . Эти числа p и q являлись секретными параметрами метода, и для взлома системы RSA было достаточно найти множители p и q , т.е выполнить разложение числа n на простые сомножители. На момент опубликования алгоритма RSA было известны лишь небольшое количество алгоритмов факторизации, самым известным из которых являлся метод Ферма. Эти методы позволяли на тот день факторизовать числа, состоящие не более чем из 25 - 30 цифр. Поэтому использование в качестве n натурального числа, имеющего более 100 десятичных знаков, гарантированно обеспечивало безопасность шифрования этим методом. Сами создатели метода предложили всей математической общественности для тестового взлома 129-значное десятичное число, пообещав за его разложение условное вознаграждение в $100. Масла в огонь подлила также опубликованная в 1977 г. в журнале Sci.Amer. статья известного математика и популяризатора Мартина Гарднера «A new kind of cipher that would take millions of years to break» («Новый алгоритм шифрования, для взлома которого потребуется миллионы лет»).
Однако через 17 лет 129-значное число создателей метода RSA было разложено на составные множители с помощью алгоритма квадратичного решета, реализованного в сети коллективом авторов, возглавляемым А.Ленстрой. Эта процедура потребовала колоссальных усилий. Была задействована сеть, состоящая из 1600 компьютеров, которые проработав 220 дней, подготовили систему линейных уравнений, содержащую более 0,5 млн неизвестных. Потом эта система была решена с помощью суперкомпьютера за 2 дня вычислений. Параллельно с методом RSA американцами У.Диффи и М.Хеллманом в 1976 году был разработан алгоритм, позволяющий вырабатывать общий секретный ключ для двух пользователей сети, общающихся через открытую сеть. Этот метод основывался на трудности задачи вычисления дискретного логарифма в конечных полях. Схема построения электронной цифровой подписи на электронные документы, обеспечивающей те же условия, что и обычная собственноручная подпись, была разработана в 1984 году египетским криптографом Эль- Гамалем, и была развитием метода Диффи-Хеллмана. Следующий серьезный этап в развитии криптографии связан с разработкой понятия эллиптических кривых. В 1985 В.Миллер и Н.Коблиц показали, что проблема вычисления кратного точки эллиптической кривой, рассматриваемой над конечным полем, имеет большую вычислительную сложность, чем проблема факторизации числа или проблема вычисления дискретного логарифма в полях той же размерности. В начале 2000-х годов в криптографию вошло и получило большую популярность преобразование Вейля, которое позволило разработать и реализовать много новых алгоритмов типа короткой ЭЦП, ЭЦП, основанной на идентификационных данных пользователя, многосторонние протоколы Диффи-Хеллмана и другие.
Для реферата я выбрал один из способов шифрования: криптосистему Рабина. Меня очень заинтересовал алгоритм шифрования, который базируются на концепции открытого ключа. Я приложу все усилия, чтобы изложить все просто, наглядно и с использованием примеров.