Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
G(X) = Yl(X + Tr(J)Y'.
Теперь Алиса может найти величины Sj, разлагая G(X) на множители (для чего имеется эффективный алгоритм; см. второй том книги Кнута).
УПРАЖНЕНИЯ
1. Для каждого из приводимых вариантов наборов и «объемов» определить, является ли набор быстрорастущим, имеет ли задача о рюкзаке решение и, если имеет, то сколько:
а) {2,3,7,20,35,69}, V - 45; б) {1,2,5,9,20,49}, V = 73; в) {1,3,7,12,22,45}, V - 67; г) {2,3,6,11,21,40}, V = 39;
д) {4, 5, 10, 30, 50, 10I)1V = 186; е) {3, 5, 8, 15, 28, 60}, V = 43.
2. а) Показать, что быстрорастущая последовательность с наименьшими членами — это последовательность 1,2,4,8,...,21,...
б) Показать, что задача о рюкзаке с этим быстрорастущим набором всегда имеет решение га, а именно, га = V, и что не существует других быстрорастущих наборов, при которых задача всегда имеет решение.
3. Показать, что всякая последовательность натуральных чисел {^1} со свойством Vi+i 2и,- при всех і является быстрорастущей.
4. Предположим, что элементами открытого текста являются буквы 26-буквенного алфавита A-Z, которым отвечают числа от 0 до 25. Вы принимаете последовательность элементов шифртекста 14, 25, 89, 3, 65, 24, 3, 49, 89, 24, 41, 25, 68, 41, 71. Открытым ключом является последовательность {57, 14, 3, 24, 8}, а секретным ключом — пара Ъ = 23, т 61.
а) Попробуйте дешифровать сообщение, не пользуясь ключом дешифрования; проверьте результат, используя ключ дешифрирования и алгоритм решения задач о рюкзаке с быстрорастущим набором.
б) Использовать открытый ключ для посылки сообщения «TENFOUR».
§ 4. ЗАДАЧА О РЮКЗАКЕ
129
5. Предположим, что элементами открытого текста являются тройки букв 32-буквенного алфавита, где буквам A-Z отвечают числа 0-25, пробел = 26, ? = 27, ! = 28, . = 29, '= 30, $ = 31. Вы получили последовательность элементов шифртекста 152472, 116116, 68546, 165420, 168261. Открытым ключом является набор {24038, 29756, 34172, 34286, 38334, 1824, 18255, 19723, 143, 17146, 35366, 11204, 32395, 12958, 6479}, а секретным ключом — пара 6 = 30966, тп = 47107. Расшифруйте сообщение.
6. Предположим, что элементами открытого текста являются биграммы букв 32-буквенного алфавита из примера 5. Вы получили последовательность элементов шифртекста 33219, 7067, 18127, 43099, 37953, которые зашифрованы с помощью двухступенчатого рюкзачного ключа {23161, 6726, 4326, 16848, 21805, 11073, 120, 15708, 2608, 341}. Секретный ключ: &i = 533, mi = 2617, 62 = 10175, m2 = 27103. Расшифруйте сообщение.
ЛИТЕРАТУРА к §4 ГЛАВЫ IV
1. Brickell Е. Breaking iterated knapsacks. — In: Advances in Cryptology. Crypto'84. Heidelberg etc.: Springer, 1985, p. 342-358.
2. Brickell E., Odlyzko A. Cryptanalysis: A survey of recent results. — Proc. IEEE, 1988, v. 76, p. 578-593.
3. Chor В., Rivest R. A knapsack-type public key cryptosystem based on arithmetic in finite fields. — In: Advances in Cryptology. Crypto'84. Heidelberg etc.: Springer, 1985, p. 54-65; revised version in IEEE Trans. Inform. Theory IT-34, 1988, p. 901-909.
4. Garey M. Д., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San-Francisco: W. H. Freeman, 1979. (Русск. ne-рев. — ГэриМ., Джонсон Д. С. Вычислительные машины и труднорешаемые задачи. M.: Мир, 1982.)
5. Goodman R. М. F., McAuley A. J. A new trapdoor knapsack public key cryptosystem. — In: Advances in Cryptology. Proceedings of Eurocrypt 84. Heidelberg etc.: Springer, 1985, p. 150-158.
6. Hellman M. E. The mathematics of public-key cryptology. — Sei. American, 1979, v. 241, p. 146-157.
7. Hellman M. E., Merkle R. C. Hiding information and signatures in trapdoor knapsack. — IEEE Trans. Inform. Theory IT-24, 1978, p. 525-530.
8. Odlyzko A. The rise and fall of knapsack cryptosystems. — Crypt. Comput. Number Theory, Proc. Symp. Appl. Math., 1990, v. 42, p. 75-88.
9. Schnorr С. Efficient identification and signatures for smart cards. — In: Advances in Cryptology. Crypto '89. Heidelberg etc.: Springer, 1990, p. 239-251.
10. Shamir A. A polynomial time algorithm for breaking the basic Mercle-Hellman cryptosystem. — In: Proceedings of the 23rd Annual Symposium on the Foundations of Computer Science, 1982, p. 145-152.
11. van Oorschot P. A comparison of practical public-key cryptosystems based on integer factorisation and discrete logarithms. — In: Contemporary Cryptology: The Science of Information Integrity./Ed. by G. Simmons. Piscataway: IEEE Press, 1992, p. 289-322.
130
ГЛ. IV. ОТКРЫТЫЙ ключ
§ 5. Протоколы с нулевым разглашением и скрытая передача
«Нулевое разглашение» — это название криптографического понятия, введенного в начале восьмидесятых годов в связи со следующей задачей. Пусть кто-либо желает убедить кого-то в том, что он умеет делать нечто, например, решать некоторое уравнение, доказывать теорему или разгадывать головоломку, не передавая при этом никакой информации о способе решения. Возможно ли это? Как можно убедить кого-либо в том, что вы имеете некоторое решение, не демонстрируя его? Удивительно, но во многих ситуациях это вполне возможно.
