25 этюдов о шифрах - [17]
3) нулевое разглашение (или стойкость) — в результате работы протокола (P, V, S) абонент V не увеличит свои знания об утверждении S или, другими словами, не сможет извлечь никакой информации о том, почему S истинно.
Самое удивительное, что в 1991 году для широкого класса математических проблем (включающего так называемые NP-полные задачи) удалось доказать существование доказательств с нулевым разглашением. Впрочем, это доказано только в предположении, что существует односторонняя функция.
Приведем одно практическое применение теории доказательств с нулевым разглашением — «интеллектуальные карточки» (неподделываемые удостоверения личности, кредитные карточки и т.п.). В них вмонтирован микропроцессор, реализующий действия абонента P в протоколе, претендующем быть протоколом доказательства с нулевым разглашением (P, V, S). Здесь абонент P — владелец карточки, а абонент V — например, компьютер в банке или в проходной секретного учреждения. Подумайте, почему в таком случае можно обеспечить неподделываемость удостоверений личности и кредитных карточек.
Заключение
Вы прочли первую книгу по криптографии.
Если вам хочется подробней узнать историю криптографии, события и легенды, связанные с ней, то рекомендуем попытаться найти и прочесть упомянутые в этюде 1.4 книги Д. Кана и Т.А. Соболевой, а также любые номера журнала «Cryptology».
Если вы увлекаетесь программированием и вам захотелось самому реализовать какие-нибудь криптографические алгоритмы, то прежде всего полезно овладеть упомянутой в этюде 2.8 книгой Д. Кнута. Затем можно обратиться к одной из многочисленных книг для программистов по вопросам защиты информации в ЭВМ.
Если вас интересуют математические вопросы криптографии, то в первую очередь необходимо углубиться в те разделы математики, которые упомянуты в этюдах 2.1, 2.2, 2.3, 3.3, 3.4 и 3.8. Систематическое образование в этой области можно получить в любом из вузов, указанных во введении.
1. Т.А. Соболева. Тайнопись в истории России. (История криптографической службы России XVIII — начала XX в.). М., 1994.
2. К. Шеннон. Работы по теории информации и кибернетике. М., ИЛ, 1963.
3. У. Диффи, М.Э. Хеллмэн. Защищенность и имитостойкость. Введение в криптографию. ТИИЭР, том 67, N 3, 1979.
4. Г. Фролов. Тайны тайнописи. М., 1992.
5. М. Гарднер. От мозаик Пенроуза к надежным шифрам. М., Мир, 1993.
6. А.Н. Лебедев. Криптография с «открытым ключом» и возможности ее практического применения. «Защита информации», выпуск 2, 1992.
ПРИЛОЖЕНИЕ
Избранные задачи олимпиад по криптографии
Институт криптографии, связи и информатики (ИКСИ) входит в состав Академии Федеральной службы контрразведки Российской Федерации. ИКСИ имеет в своем составе два факультета: информатики и специальной техники. Институт готовит высококвалифицированных специалистов в области защиты информации, криптографии, специальной связи, компьютерной безопасности.
Для школьников при ИКСИ действует вечерняя физико-математическая школа. С 1991 года институт проводит олимпиады по криптографии и математике, избранные задачи которых публикуются в данном приложении.
1. Ключом шифра, называемого «решетка», является трафарет, сделанный из квадратного листа клетчатой бумаги размером n×n (n — четно). Некоторые из клеток вырезаются с тем, чтобы в получившиеся отверстия на чистый лист бумаги того же размера можно было вписывать буквы текста, подлежащего зашифрованию. Одна из сторон трафарета является помеченной. Кроме того, трафарет должен обладать одним важным свойством: при наложении его на чистый лист бумаги четырьмя возможными способами (помеченной стороной вверх, вправо, вниз, влево) его вырезы полностью покрывают всю площадь квадрата, причем каждая клетка оказывается под вырезом ровно один раз.
Буквы сообщения, имеющего длину n>2, последовательно вписываются в вырезы трафарета при каждом из четырех его указанных положений. После снятия трафарета на листе бумаги оказывается зашифрованное сообщение.
Найдите число различных ключей для произвольного четного числа n.
2. В адрес олимпиады пришла шифртелеграмма
>ЦДОЗИФКДЦЮ.
Прочитайте зашифрованное сообщение, если известно, что использовался шифр, по которому к двузначному порядковому номеру буквы в алфавите (от 01 до 33) прибавлялось значение многочлена
f(x) = x>6 + 3x>5 + x>4 + x>3 + 4x>2 + 4x + 5,
вычисленное либо при x = x>1, либо при x = x>2 (в случайном порядке), где x>1,x>2 — корни трехчлена x>2 + 3x + 1, а затем полученное число заменялось соответствующей ему буквой.
3. Одна фирма предложила устройство для автоматической проверки пароля. Паролем может быть любой непустой упорядоченный набор букв в алфавите {a, b, c}. Будем обозначать такие наборы большими латинскими буквами. Устройство перерабатывает введенный в него набор
Эта книга состоит из трех частей и охватывает период истории физики от Древней Греции и до середины XX века. В последней части Азимов подробно освещает основное событие в XX столетии — открытие бесконечно малых частиц и волн, предлагает оригинальный взгляд на взаимодействие технического прогресса и общества в целом. Книга расширяет представления о науке, помогает понять и полюбить физику.
Автор множества бестселлеров палеонтолог Дональд Протеро превратил научное описание двадцати пяти знаменитых прекрасно сохранившихся окаменелостей в увлекательную историю развития жизни на Земле. Двадцать пять окаменелостей, о которых идет речь в этой книге, демонстрируют жизнь во всем эволюционном великолепии, показывая, как один вид превращается в другой. Мы видим все многообразие вымерших растений и животных — от микроскопических до гигантских размеров. Мы расскажем вам о фантастических сухопутных и морских существах, которые не имеют аналогов в современной природе: первые трилобиты, гигантские акулы, огромные морские рептилии и пернатые динозавры, первые птицы, ходячие киты, гигантские безрогие носороги и австралопитек «Люси».
К созданию невозможного вечного двигателя одни изобретатели приступали, игнорируя законы природы, другие же, не зная их, действовали на авось. В наше время, в эпоху расцвета науки и техники, едва ли есть серьёзные изобретатели, которых увлекала бы бесплодная в своей основе идея создания вечного двигателя.
Легендарная книга Лоуренса Краусса переведена на 12 языков мира и написана для людей, мало или совсем не знакомых с физикой, чтобы они смогли победить свой страх перед этой наукой. «Страх физики» — живой, непосредственный, непочтительный и увлекательный рассказ обо всем, от кипения воды до основ существования Вселенной. Книга наполнена забавными историями и наглядными примерами, позволяющими разобраться в самых сложных хитросплетениях современных научных теорий.
Если наша планета не уникальна, то вероятность повсеместного существования разумной жизни огромна. Более того, за всю историю человечества у инопланетян было достаточно времени, чтобы дать о себе знать. Так где же они? Какие они? И если мы найдем их, то чем это обернется? Ответы на эти вопросы ищут ученые самых разных профессий – астрономы, физики, космологи, биологи, антропологи, исследуя все аспекты проблемы. Это и поиск планет и спутников, на которых вероятна жизнь, и возможное устройство чужого сознания, и истории с похищениями инопланетянами, и изображение «чужих» в научной фантастике и кино.
Книга немецкого историка, востоковеда, тюрколога, специалиста по истории монголов Бертольда Шпулера посвящена истории и культуре Золотой Орды. Опираясь на широкий круг источников и литературы, автор исследует широкий спектр вопросов: помимо политической истории он рассматривает религиозные отношения, государственный строй, право, военное дело, экономику, искусство, питание и одежду.