Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
96
ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ
димый для прочтения сообщения.
Раньше никто бы не подумал, что системы этого типа обладают какими-либо особенно поразительными преимуществами. Традиционно криптография использовалась, главным образом, военными и дипломатами. Обычно требовалось распределить систему ключей внутри небольшой строго определенной группы пользователей, и эта система ключей периодически (с помощью курьеров) обновлялась, чтобы лишить противника возможности вскрыть ее.
Однако в последние годы сфера реальных и потенциальных приложений криптографии расширилась и включила в себя ряд других областей, в которых системы связи играют важнейшую роль: создание и хранение баз конфиденциальной информации, электронные финансовые расчеты и т. д. Зачастую имеется большая сеть пользователей, любые два из которых должны иметь возможность сделать переписку между ними секретной как для других пользователей сети, так и для посторонних злоумышленников. Два участника могут в какой-то момент установить секретную связь, позднее один из них может захотеть послать конфиденциальное сообщение третьему. Таким образом, множество участников, между которыми поддерживается секретная связь, может постоянно изменяться. Было бы неудобно каждый раз обмениваться ключами со всеми потенциальными корреспондентами.
Заметим, что система с открытым ключом позволяет двум участникам начать секретный обмен данными без предварительного контакта, без взаимной проверки и без предварительного обмена какой-либо информацией. Вся необходимая для посылки шифрованного сообщения информация является общедоступной.
Классическая версия открытого ключа. Под классической криптосистемой (иначе, системой с секретным ключом или симметричной криптосистемой) понимается криптосистема, в которой, имея информацию о преобразовании шифрования, можно реализовать преобразование дешифрования примерно за такое же время, что и преобразование шифрования. Все криптосистемы главы III были классическими. Бывает, что дешифрование в них требует несколько большего времени, поскольку приходится использовать алгоритм Евклида, чтобы найти обратное число по модулю N, или обращать матрицу (а обращение k X /с-матриц при больших к также занимает значительное время); тем не менее, это дополнительное время не слишком велико. (Более того, это дополнительное время используется лишь один раз — при определении Kp — после чего дешифрование становится не сложнее шифрования.) Например, может понадобиться лишь O(log В) двоичных операций для шифрования одного элемента сооб-
§ 1. СУТЬ КРИПТОГРАФИИ С ОТКРЫТЫМ ключом
97
щения и 0(log3v3) двоичных операций для определения Kp по КЕ. Здесь В — граница для размера ключевого параметра. Заметьте, какую роль играют здесь оценки вида О-большое.
С другой стороны, если бы время шифрования было полиномиально по log ІЗ, а время дешифрования (при известном Kg, но не Kp) полиномиально по В, а не log ІЗ, то это, скорее, была бы система с открытым ключом, а не классическая криптосистема.
Аутентикация.^ Часто одной из наиболее важных частей сообщения является подпись. Человеческая подпись, написанная машинальным росчерком пера, которую трудно повторить, позволяет быть уверенным, что сообщение получено действительно от лица, чье имя написано ниже. Если сообщение имеет особенную важность, могут потребоваться дополнительные способы заверения подлинности (ау-тентикации) сообщения. А в электронных средствах связи, где нельзя передать физическую подпись, приходится полагаться совершенно на другие методы. Например, когда сотрудник компании хочет снять деньги со счета компании по телефону, его часто просят сообщить некоторую личную информацию (например, девичью фамилию матери), которую знают как сотрудник, так и банк (эти данные подаются при открытии счета), но навряд ли знает посторонний.
Криптография с открытым ключом предоставляет очень простой способ доказать, что вы — это именно вы, которым не может воспользоваться никто другой, желающий выдать себя за вас. Пусть А (Алиса) и В (Боб) — два пользователя системы. Пусть /А — шифрующее преобразование, которым должен воспользоваться любой, кто отправляет сообщение Алисе, а /в — соответствующее преобразование для Боба. Для простоты считаем, что множества VnC элементов открытого и шифрованного текстов совпадают и одинаковы у всех пользователей. Пусть P — подпись Алисы (включающая в себя, возможно, идентификационный номер Алисы, время отправления сообщения и т.п.). Если Алиса просто пошлет Бобу некоторое сообщение /в(Р), то (поскольку способ вычисления Jb[P) общеизвестен) нет способа проверки, гарантирующего, что подпись принадлежит Алисе. Однако, если в начале или конце сообщения будет помещено /в/а* (P), то Боб, применив /я \ дешифрует сообщение, включая этот добавок, и все превратится в открытый текст, за исключением добавка, который примет вид /д1(Р). Так как Боб знает, что сообщение должно
Английский термин authentication означает удостоверение (или доказательство) подлинности. В русскоязычной литературе часто используется его искаженная калька «аутентификация». — Прим. ред.
