Алгоритм Ривеста-Шамира-Эдлемана

Этот алгоритм известен как RSA и носит инициалы его изобретателей. Этот алгоритм имеет важное значение, поскольку может быть использован как для шифрования, так и для цифровых подписей.

Стойкость алгоритма RSA определяется сложностью разложения больших чисел на множители. (Наверное, криптоанализ шифра RSA возможен и без использования операции разложения на множители, но никто до сих пор не доказал этого).

Ниже кратко описан принцип действия алгоритма RSA:

Генерируется два простых числа p и q (100 цифр и более), причем n=pq.

В качестве открытого ключа выбирается целое число e, взаимно простое с числом (p-1)(q-1).

Закрытый ключ d вычисляется из условия ed mod (p-1)(q-1) = 1.

Шифрование открытого числа m (где m < n), осуществляется путем вычисления m^c mod n.

Расшифровка зашифрованного числа c осуществляется путем вычисления c^d mod m.

Основным недостатком шифра RSA и других алгоритмов с открытым ключом, является их низкая производительность, по сравнению с алгоритмами с секретным ключом. Алгоритм RSA уступает по скорости сопоставимым реализациям алгоритма DES в 100, а то и в 1000 раз.

Хотя шифр RSA еще никому не удалось раскрыть, прогресс в математике может сделать этот шифр устаревшим. При наличии эффективного способе разложения больших чисел на множители шифр RSA можно легко раскрыть. К тому же алгоритм RSA и другие алгоритмы с открытым ключом не защищены от множества атак, которые определяются способами использования этих алгоритмов.

Алгоритм AlGamal

Хотя RSA и является одним из самых популярных алгоритмов шифрования с открытым ключом, имеется также множество других алгоритмов. Один из них – алгоритм AlGamal, разработанный в 1984 г. Тэгером Эль-Гамалом. Он не запатентован и может использоваться свободно.

Защищенность алгоритма AlGamal базируется на сложности вычисления дискретного логарифма в конечном поле. А заключается алгоритм в следующем:

1.Выбирается простое число p и два случайных числа, g и x, меньших чем p.

2.Открытый ключ состоит из чисел g, p, и y, где y=g^x mod p. Закрытым ключом является число x.

3.Для шифрования блока сообщения m, выбирается случайное чтило k, такое, что k и (p-1) взаимно простые числа, и вычисляется a=g^k mod p. Зашифрованным блоком являются оба числа – a и b.

4.Для расшифровки a и b вычисляется m=(b/a^x) mod p.

5.Дайджесты сообщений

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

1. Целостность – для обнаружения фактов изменения или подмены сообщения

2. Аутентификация – для проверки того, что сообщение действительно создано лицом или организацией, от имени которой они поступили.

3. Неаннулируемость – для недопущения того, чтобы тот, кто послал сообщение или выполнил некоторую операцию над объектом, мог отрицать тот факт, что именно он сделал это.

Перечисленные задачи решаются с помощью дайджестов сообщений и цифровых подписей.

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

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

· Невозможно численными методами найти два различных сообщения, по которым функция дайджеста сообщения вычислила совпадающие значения.

Заметьте, в самой функции дайджеста сообщений никакого секрета нет – она общедоступна и не использует ключей. Примерами алгоритма дайджеста сообщения являются алгоритмы MD5 и SHA-1.

Цифровые подписи и цифровые сертификаты

Цифровые подписи обеспечивают замечательную возможность узнавать то, было ли сообщение (или иной объект) случайно или преднамеренно изменено. Цифровые сертификаты позволяют установить было ли сообщение действительно создано конкретным лицом или организацией.

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

1. Создается цифровая подпись

1.1. Вычисляется дайджест сообщения

1.2. Дайджест сообщения зашифровывается с помощью закрытого ключа из пары “открытый/закрытый ключ”, в результате чего получается цифровая подпись.

2. Производится верификация цифровой подписи

2.1. Подпись расшифровывается с помощью открытого ключа из вышеупомянутой пары “открытый/закрытый ключ ”, в результате чего восстанавливается дайджест сообщения.

2.2. Значение расшифрованного дайджеста сообщения расшифровывается и сравнивается со значением дайджеста сообщения вычисленного из исходного сообщения

Если оба значения дайджеста сообщения совпадают, то подпись подлинная. В противном случае или подпись, или сообщение были изменены.

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

· Подпись нельзя подделать – подписавшее лицо использует для подписи закрытый ключ, а он является секретным.

· Подлинность подписи всегда можно проверить – поскольку открытый ключ подписавшего лица общедоступен, любое лицо, имеющее в руках сообщение и цифровую подпись может проверить, что сообщение было подписано данным лицом и что ни оно, ни подпись не были изменены.

· Подпись неповторима – каждому сообщению соответствует своя, неповторимая подпись. Невозможно численными методами использовать подписи вместе с другим сообщением.

· Факт подписи невозможно отрицать – после того как сообщение подписано и отослано вместе с подписью, лицо, сделавшее это не может отрицать, что оно сделало это (если только не докажет, это закрытый ключ был похищен)

Как видно, цифровые подписи – это прекрасный способ подтверждения того, что сообщение (или объект) было создано или проверено конкретным лицом или организацией. Но есть одна каверза – вам нужно каким-то образом определить, что открытый ключ, который вы получили от имени кого-то, - это действительно его открытый ключ. Вот где в дело вступают цифровые сертификаты.

Цифровые сертификаты – это сообщения, подписанные полномочным органом сертификации (Certificate Aythory – CA), который заверяет значение открытого ключа, принадлежащего кому-либо, и использование конкретного алгоритма шифрования. Чтобы получить сертификат полномочного органа сертификации, обычно нужно представить в него документы, подтверждающие личность заявителя.

В больших сетях, таких как Internet, может оказаться необходимой многоуровневая структура сертификации. В таком случае орган высшего уровня, например компания VeriSign, Inc., могут выдавать сертификаты полномочным органам второго уровня. Органы второго уровня могут, в свою очередь, выдавать сертификаты другим компаниям. В результате возникает иерархическая структура сертификации. Сертификация лиц находящихся в конце ветвей этой структуры зависит от лиц занимающих более высокий уровень иерархии. Такие связи называют цепочками сертификации.

Сертификаты X.509 ISO являются популярным видом цифровых сертификатов. X.509 означает определенный формат и содержание цифрового сертификата. Этот формат стал популярным благодаря протоколу защищенных сокетов (SSL) компании Netscape, формату архивных файлов Java (JAR), а также ряду других новых стандартов безопасности Internet.

Заключение

Значение криптографии в современном информационном обществе трудно переоценить. Новая информационная инфраструктура создает новые опасности для информации. Открытые каналы Internet могут стать серьезной угрозой безопасности передачи данных. Однако и криптография не стоит на месте. Теперь она стала доступна широким массам пользователей. При помощи широкодоступных алгоритмов шифрования, а также цифровых подписей и сертификатов, пользователи могут добиться безопасности и скрытности передачи своих данных. Нужно только уметь всем этим пользоваться.

Список использованной литературы

1.Джим Яворски, Пол Дж. Перроун Система безопасности Java. Спб 2001 г.

2.М. Холл Сервлеты и Java Server Pages. Спб 2001 г.

3.М. Холл, Л Браун Программирование для Web. Спб 2002 г.