Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
а) Страна А настаивает на ознакомлении с содержанием (открытым текстом) всех сообщений, отправляемых с ее территории, чтобы быть уверенной в том, что оборудование не используется страной В в целях шпионажа.
б) Страна В настаивает на том, чтобы страна А не могла сфабриковать сообщение, передаваемое оборудованием с его территории (т. е. сообщение типа «все нормально», когда сейсмограф зафиксировал нарушение договора).
в) Страна А настаивает на том, чтобы в случае, если страна В сделает ложное заявление о получении от оборудования сигнала о нарушении договора, любая
100
ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ
заинтересованная третья страна была в состоянии определить, что в реальности сообщения о нарушении не посылалось.
г) Условия а)-в) с переменой сторон.
д) Контрольное оборудование в обеих странах должно быть идентичным и созданным совместно учеными обеих стран.
4. В этой задаче требуется с помощью какой-нибудь функции с замком типа два-в-один организовать игру в монетку на большом расстоянии между игроками. Например, двое, находясь в различных частях света, собираются сыграть партию в шахматы по переписке или по телефону и им надо определить, кто играет белыми. Или, при подготовке к международному хоккейному матчу, представители команд решили бросить монетку для определения того, кто будет считаться хозяином, но не хотят ради этого встречаться или привлекать третью сторону.
Под системой функций с замком типа два-в-один мы понимаем пару алгоритмов: алгоритм, который при заданном ключе Ke подходящего типа строит такую функцию /: V —> С, что каждому элементу с образа / отвечают ровно два таких прообраза р\,Р2 Є V, что /(pi) = f(pi) = с, и алгоритм, который при заданном ключе Kq, «обратном к Ke», может найти оба прообраза для любого с из образа /. Здесь предполагается, что вычислительная сложность нахождения Ku по Ke чрезвычайно велика. Заметим, что при заданном элементе Pi Є V можно найти другой элемент р2, имеющий тот же образ (т.е. найти оба обратных к /(pi)), если знать как Ke, так и Kd- Однако мы предполагаем, что, зная лишь Ke, практически невозможно найти Р2 ни для какого р\.
Предположим, что игроки А (Анюта) и В (Бьерн) хотят использовать этот подход для игры в монетку. Игрок А вырабатывает пару ключей Ke и Kd и посылает Ke (но не Kd) игроку В. Объяснить процедуру, предоставляющую каждому из игроков равные шансы на «выигрыш» (дать подходящее определение «выигрыша») и надежную защиту от обмана.
ЛИТЕРАТУРА к § 1 ГЛАВЫ IV
1. Blum М. Coin-flipping by telephone — a protocol for solving imposible problems. — IEEE Proc, Spring Compcon., p. 133-137.
2. Diffie W., Hellman M. E. New directions in cryptography. — IEEE Trans. Inform. Theory IT-22, 1976, p. 644-654.
3. Chaum D. Achieving electronic privacy. — Sei. American, 1992, v. 267, p. 96-101.
4. Goldwasser S. The search for provably secure cryptosystems. — Crypt. Comput. Number Theory, Proc. Symp. Appl. Math., 1990, v. 42, p. 89-113.
5. Hellman M. E. The mathematics of public-key cryptography. — Sei. American, 1979, v. 241, p. 146-157.
6. Kranakis E. Primality and Cryptography. N.-Y. etc.: Wiley, 1986.
7. Rivest R. Cryptography. — In: Handbook of Theoretical Computer Science. Vol. A. Amsterdam: Elsevier, 1990, p. 717-755.
8. Ruggiu G. Cryptology and complexity theories. — In: Advances in Cryptology. Proceedings of Eurocrypt 84. Heidelberg etc.: Springer, 1985, p. 3-9.
§ 2. КРИПТОСИСТЕМА RSA
101
§ 2. Криптосистема RSA
При подборе функции с замком / для системы с открытым ключом желательно, чтобы идея шифрования была проста концептуально и несложна в реализации. С другой стороны, хотелось бы иметь убедительное эмпирическое обоснование — основанное на многолетних попытках построения алгоритма для / 1 — свидетельствующее о том, что дешифрование реально не осуществимо без знания секретного ключа дешифрования. По этой причине естественно обратить внимание на старинную проблему теории чисел — задачу полной факторизации большого составного целого числа при неизвестных заранее простых множителях. Успех так называемой криптосистемы «RSA» (названной по именам ее создателей: Rivest, Shamir и Adleman), являющейся одной из самых старых (16 лет) и самых популярных криптосистем с открытым ключом, определен чрезвычайной трудностью этой задачи.
Теперь опишем, как работает криптосистема RSA. Сначала каждый пользователь выбирает два очень больших простых числа р и q (имеющих, скажем, по 100 десятичных разрядов каждое) и вычисляет п = pq. Зная факторизацию числа п, несложно вычислить tp(n) = (р - l)(g — \) = п + 1—р — q. Затем пользователь выбирает случайно целое число е между 1 и <р(п), которое взаимно просто с <р(п).
Замечание. Когда мы говорим «случайно», то всегда подразумеваем, что число выбрано с помощью датчика случайных (или псевдослучайных) чисел, т.е. компьютерной программы, генерирующей последовательность цифр, которую никто не может повторить или предугадать, и которая, по-видимому, имеет те же статистические свойства, что и истинно случайная последовательность. Много написано об эффективных и надежных способах генерации случайных чисел, но здесь мы не будем касаться этого вопроса. В системе RSA генератор случайных чисел используется не только для выбора е, но и для выбора больших простых чисел р и q (чтобы никто не смог предугадать наш выбор, взяв таблицы простых чисел специального
