Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Для дешифрования (т.е. вычисления / *) также необходимы алгоритм и ключ. Этот ключ называется ключом дешифрования Кр. В нашем примере аффинной криптосистемы дешифрование производится также аффинным преобразованием P = а 1С — а Ь (mod N), т.е. алгоритм дешифрования совпадает с алгоритмом шифрования, но с другим ключом, а именно, (а_1,-а_1Ь). (В некоторых криптосистемах алгоритм дешифрования, как и ключ, отличается от алгоритма шифрования.) Мы всегда будем предполагать, что алгоритмы ши-
92
ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ
фрования и дешифрования общеизвестны, а скрыты могут быть лишь ключи Ke и Kp.
Пусть кто-либо пытается использовать для засекречивания связи описанную выше аффинную криптосистему С = аР + Ь. Как мы видели в § III. 1, эту систему нетрудно вскрыть, если используются однобуквенные элементы текста в vV-буквенном алфавите. Немного сложнее вскрыть эту систему при использовании биграмм, что мож-
2
но рассматривать как использование TV -буквенного алфавита. Еще лучше использовать блоки из к букв с числовыми эквивалентами из Z/NkZ. При к > 3 использовать частотный анализ уже затруднительно, так как число возможных fc-грамм очень велико и многие из них можно с равным основанием считать наиболее часто встречающимися. Если идти по пути увеличения к, то надо учитывать затраты времени на решение различных арифметических задач (самая важная из них — нахождение а с помощью алгоритма Евклида) как при выборе ключей, так и при шифровании и дешифровании каждого сообщения. В частности, полезно иметь оценки типа О-большое (при увеличении количественных параметров, т. е. когда криптосистема становится «большой») времени, необходимого для: а) шифрования при известном K?, б) дешифрования при известном Kp, в) вскрытия кода шифрования без знания Ke, г) вскрытия кода дешифрования без знания Kp.
Во всех приведенных выше примерах, как и во всех криптосистемах, использовавшихся более пятнадцати лет назад, не было необходимости задавать ключ дешифрования, если ключ (и алгоритм) шифрования были известны. Даже имея дело с такими большими числами,
к
как TV при весьма большом к, можно определить ключ дешифрования по ключу шифрования за время, близкое по порядку ко времени работы стандартных алгоритмов. Например, в случае аффинного преобразования в Z/NkZ, зная ключ шифрования Ke — (я,6), можно вычислить ключ дешифрования Kp = (а 1 (mod Nk),—a 1O (mod Nk)) с помощью алгоритма Евклида за O(log3 Nk) двоичных операций.
Таким образом, в традиционных криптосистемах любой, кто имел возможность дешифровать сообщение, мог с небольшими усилиями или совсем без них определить ключ шифрования. Казалось наивностью или глупостью думать, что человек, вскрывший шифр, может, тем не менее, не знать ключа шифрования. Об этом свидетельствует следующий отрывок из автобиографии хорошо известного исторического персонажа.
«... Пять или шесть недель спустя она (мадам Дюрфе) спросила меня, расшифровал ли я послание, записанное с помощью транс-
§ 1. СУТЬ КРИПТОГРАФИИ С ОТКРЫТЫМ КЛЮЧОМ
93
мутации. Я ответил утвердительно.
— Извините меня, сэр, но я уверена, что такое без ключа невозможно.
— Мадам! Вы хотите, чтобы я назвал вам ключ?
— Будьте добры.
Тогда я сказал ей ключевое слово, которое не принадлежало ни одному языку, и увидел ее изумление. Она ответила мне, что это невозможно, что она полагала себя единственным обладателем этого слова, которое она держала в своей памяти и никогда не записывала.
Я мог бы сказать ей правду — что те же самые вычисления, при помощи которых я расшифровал послание, позволили мне найти это слово, — но что-то заставило меня сказать, что его открыл мне дух. Это лживое признание приворожило мадам Дюрфе ко мне. В тот день я стал властителем ее души и злоупотребил своей властью. До сих пор мне неприятно и стыдно вспоминать об этом эпизоде, и я рассказал о нем лишь потому, что обязался писать в своих мемуарах одну лишь правду...»
— Казанова, 1757, перевод отрывка, цитированного по книге D. Kahn «Codebreakers».
Ситуация оставалась без изменений почти 220 лет после этого разговора между Казановой и мадам Дюрфе: для любой криптосхе-мы знание способа шифрования и знание способа дешифрования рассматривались как по сути дела эквивалентные. Однако в 1976 году Диффи и Хеллман открыли принципиально новый тип криптосистем и изобрели «криптографию с открытым ключом».
По определению, криптосистема с открытым ключом обладает тем свойством, что знание шифрующего преобразования не позволяет по ключу шифрования найти ключ дешифрования, избежав чрезвычайно длинных вычислений. Другими словами, шифрующая функция /: V —> С легко вычисляется, если ключ шифрования Ke известен, но вычислять значения обратной функции / : С —> V очень сложно. С точки зрения практической вычислимости это значит, что функция / необратима (без дополнительной информации — ключа дешифрования Kq). Такую функцию будем называть функцией с замком*К Таким образом, функция / с замком — это легко вычислимая функция, для которой обратную функцию / вычислить трудно, если не иметь некоторой дополнительной информации сверх той, что используется
