В криптографии под случайным простым числом понимается простое число, содержащее в двоичной записи заданное количество битов, на алгоритм генерации которого накладываются определенные ограничения. Получение случайных простых чисел является… … Википедия
Мартин Хеллман Мартин Хеллман (Martin E. Hellman; род. 2 октября 1945) американский криптограф. Получил известность благодаря разработке первой асимметричной криптосистемы в соавторстве с Уитфилдом Диффи и Ральфом Мерклем (1976г). Один из… … Википедия
Немецкая криптомашина Lorenz использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от др. греч … Википедия
Немецкая криптомашина Lorenz, использовалась во время Второй мировой войны для шифрования самых секретных сообщений Криптография (от греч. κρυπτός скрытый и γράφω пишу) наука о математических методах обеспечения конфиденциальности… … Википедия
Факторизацией натурального числа называется его разложение в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики. В отличие от… … Википедия
Состоит из процедур, обеспечивающих: включение пользователей в систему; выработку, распределение и введение в аппаратуру ключей; контроль использования ключей; смену и уничтожение ключей; архивирование, хранение и восстановление ключей.… … Википедия
Эта статья должна быть полностью переписана. На странице обсуждения могут быть пояснения. Существуют два класса систем связи: цифровые и аналоговые … Википедия
Простое число это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы… … Википедия
Вероятностный полиномиальный тест простоты. Тест Миллера Рабина позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера Рабина часто… … Википедия
Тест простоты алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… … Википедия
Режим шифрования метод применения блочного шифра, позволяющий преобразовать последовательность блоков открытых данных в последовательность блоков зашифрованных данных. При этом для шифрования одного блока могут использоваться данные другого … Википедия
Под общ. ред. В.В.Ященко ВВЕДЕНИЕ В КРИПТОГРАФИЮ Авторский коллектив: В. В. Ященко (редактор, глава 1), Н. П. Вар-новский (главы 2, 3), Ю. В. Нестеренко (глава 4), Г. А. Кабатянский (глава 5), П. Н. Девянин, В. Г. Проскурин, А. В. Черемушкин (глава 6), П. А. Гырдымов, А. Ю. Зубов, А. В. Зязин, В. Н. Овчинников (глава 7). В книге впервые на русском языке дается систематическое изложение научных основ криптографии от простейших примеров и основных понятий до современных криптографических конструкций. Понимание принципов криптографии стало для многих потребностью в связи с широким распространением криптографических средств обеспечения информационной безопасности. Поэтому книга может быть полезна массовому читателю. Книга рассчитана на студентов-математиков и специалистов по информационной безопасности. Содержание Предисловие 5 Глава 1. Основные понятия криптографии 7 1. Введение 7 2. Предмет криптографии. 8 3. Математические основы 15 4. Новые направления 18 5. Заключение 23 Глава 2. Криптография и теория сложности 25 1. Введение 25 2. Криптография и гипотеза P=/NP 28 3. Односторонние функции 30 4. Псевдослучайные генераторы 32 5. Доказательства с нулевым разглашением 35 Глава 3. Криптографические протоколы 41 1. Введение 41 2. Целостность. Протоколы аутентификации и электронной подписи 44 3. Неотслеживаемость. Электронные деньги 60 4. Протоколы типа «подбрасывание монеты по телефону» 67 5. Еще раз о разделении секрета 72 6. Поиграем в «кубики». Протоколы голосования 76 7. За пределами стандартных предположений. Конфиденциальная 81 передача сообщений 8. Вместо заключения 84 Глава 4. Алгоритмические проблемы теории чисел 86 1. Введение 86 2. Система шифрования RSA 88 3. Сложность теоретико-числовых алгоритмов 91 4. Как отличить составное число от простого 96 5. Как строить большие простые числа 99 6. Как проверить большое число на простоту 102 7. Как раскладывают составные числа на множители 107 8. Дискретное логарифмирование 110 9. Заключение 115 Глава 5. Математика разделения секрета 118 1. Введение 118 2. Разделение секрета для произвольных структур доступа 120 3. Линейное разделение секрета 123 4. Идеальное разделение секрета и матроиды 125 Глава 6. Компьютер и криптография 130 1. Вместо введения. 130 2. Немного теории 132 3. Как зашифровать файл? 140 4. Поучимся на чужих ошибках 153 5. Вместо заключения 163 Глава 7. Олимпиады по криптографии для школьников 165 1. Введение 166 2. Шифры замены 169 3. Шифры перестановки 182 4. Многоалфавитные шифры замены с периодическим ключом 190 5. Условия задач олимпиад по математике и криптографии 198 6. Указания и решения 210 Приложение: отрывок из статьи К. Шеннона «Теория связи в секретных 235 системах» Содержание Предисловие 5 Глава 1. Основные понятия криптографии 7 1. Введение 7 2. Предмет криптографии 8 3. Математические основы 15 4. Новые направления 18 5. Заключение 23 Глава 2. Криптография и теория сложности 25 1. Введение 25 2. Криптография и гипотеза P^NP 28 3. Односторонние функции 30 4. Псевдослучайные генераторы 32 5. Доказательства с нулевым разглашением 35 Глава 3. Криптографические протоколы 41 1. Введение 41 2. Целостность. Протоколы аутентификации и электронной подписи 44 3. Неотслеживаемость. Электронные деньги 60 4. Протоколы типа «подбрасывание монеты по телефону» ... 67 5. Еще раз о разделении секрета 72 6. Поиграем в «кубики». Протоколы голосования 76 7. За пределами стандартных предположений. Конфиденци- Конфиденциальная передача сообщений 81 8. Вместо заключения 84 Глава 4. Алгоритмические проблемы теории чисел 86 1. Введение 86 2. Система шифрования RSA 88 3. Сложность теоретико-числовых алгоритмов 91 4. Как отличить составное число от простого 96 5. Как строить большие простые числа 99 6. Как проверить большое число на простоту 102 7. Как раскладывают составные числа на множители 107 8. Дискретное логарифмирование 110 9. Заключение 115 Глава 5. Математика разделения секрета 118 1. Введение 118 2. Разделение секрета для произвольных структур доступа. . 120 3. Линейное разделение секрета 123 4. Идеальное разделение секрета и матроиды 125 Глава 6. Компьютер и криптография 130 1. Вместо введения 130 2. Немного теории 132 3. Как зашифровать файл? 140 4. Поучимся на чужих ошибках 153 5. Вместо заключения 163 Глава 7. Олимпиады по криптографии для школьников 165 1. Введение 166 2. Шифры замены 169 3. Шифры перестановки 182 4. Многоалфавитные шифры замены с периодическим ключом 190 5. Условия задач олимпиад по математике и криптографии. . 198 6. Указания и решения 210 Приложение: отрывок из статьи К. Шеннона «Теория свя- связи в секретных системах» 235 Предисловие ко второму изданию В настоящем втором издании исправлены опечатки и неточности, заме- замеченные в первом издании. сентябрь 1999 г. В. Ященко Предисловие к первому изданию Криптография - наука о шифрах - долгое время была засекречена, так как применялась, в основном, для защиты государственных и военных се- секретов. В настоящее время методы и средства криптографии используются для обеспечения информационной безопасности не только государства, но и частных лиц, и организаций. Дело здесь совсем не обязательно в секретах. Слишком много различных сведений «гуляет» по всему свету в цифровом ви- виде. И над этими сведениями «висят» угрозы недружественного ознакомления, накопления, подмены, фальсификации и т. п. Наиболее надежные методы за- защиты от таких угроз дает именно криптография. Пока криптографические алгоритмы для рядового потребителя - тайна за семью печатями, хотя многим уже приходилось пользоваться некоторыми криптографическими средствами: шифрование электронной почты, интел- интеллектуальные банковские карточки и др. Естественно, что при этом основной вопрос для пользователя - обеспечивает ли данное криптографическое сред- средство надежную защиту. Но даже правильно сформулировать этот элементар- элементарный вопрос непросто. От какого противника защищаемся? Какие возможно- возможности у этого противника? Какие цели он может преследовать? Как измерять надежность защиты? Список таких вопросов можно продолжить. Для ответа на них пользователю необходимы знания основных понятий криптографии. Популярное изложение научных основ криптографии (речь идет толь- только о «негосударственной» криптографии; разделы криптографии, связан- связанные с государственной безопасностью, должны оставаться секретными) - цель настоящей книги. Ее можно использовать и в качестве учебного по- пособия. На русском языке аналогичных книг пока нет. Материалы ряда глав публиковались авторами ранее в других изданиях (глава 1 - в кни- книге С. А. Дориченко, В. В. Ященко, «25 этюдов о шифрах», М.: ТЕИС, 1994; главы 1,2,4,5 - в журнале «Математическое просвещение», третья серия, вы- выпуск 2, М.: МЦНМО, 1998; глава 7 - в газете «Информатика» (еженедельное приложение к газете «Первое сентября»), № 4, январь 1998). При подготовке настоящего издания эти материалы были переработаны и дополнены. Изложение материала рассчитано на читателя с математическим скла- складом ума. В основном главы не зависят друг от друга (это достигнуто за счет некоторых повторов) и их можно читать в произвольном порядке. Главу 1 - вводную - рекомендуется прочитать всем, поскольку в ней на популярном уровне разъясняются все основные понятия современной крип- криптографии: шифр, ключ, стойкость, электронная цифровая подпись, крипто- криптографический протокол и др. В других главах часть материала повторяется, но уже более углубленно. В главах 2, 3, 4, 5 используются некоторые сведе- сведения из высшей математики, известные ученикам математических классов и студентам. Глава 6 ориентирована на знатоков компьютерных технологий. Глава 7 содержит материалы олимпиад по криптографии для школьников и поэтому для ее чтения никаких знаний, выходящих за пределы школьной программы, не требуется. Предупреждение: криптографические средства и программные продук- продукты, упоминаемые в книге, используются только для иллюстрации общих криптографических идей; авторы не ставили своей целью давать оценки или сравнивать имеющиеся на рынке криптографические средства. Криптография была поставлена на научную основу во многом благодаря работам выдающегося американского ученого Клода Шеннона. Его доклад «Математическая теория криптографии» был подготовлен в секретном вари- варианте в 1945 г., рассекречен и опубликован в 1948 г., переведен на русский язык в 1963 г. Поскольку «Работы по теории информации и кибернетике» A963 г.) К. Шеннона стали библиографической редкостью, мы включили в приложение основную часть статьи К. Шеннона «Теория связи в секретных системах». Эту основополагающую работу рекомендуется прочитать всем интересующимся криптографией. Для профессионального понимания криптографических алгоритмов и умения оценивать их сильные и слабые стороны необходима уже серьезная математическая подготовка (на уровне математических факультетов уни- университетов). Это объясняется тем, что современная криптография основана на глубоких результатах таких разделов математики, как теория сложности вычислений, теория чисел, алгебра, теория информации и др. Желающим серьезно изучать криптографию можно порекомендовать обзорную моногра- монографию «Криптография в банковском деле» Анохина М. И., Варновского Н. П., Сидельникова В. М., Ященко В. В., М.: МИФИ, 1997. октябрь 1998 г. В. Ященко Глава 1 Основные понятия криптографии 1. Введение Как передать нужную информацию нужному адресату в тайне от других? Каждый из читателей в разное время и с разными целями на- наверняка пытался решить для себя эту практическую задачу (для удоб- удобства дальнейших ссылок назовем ее «задача ТП», т. е. задача Тайной Передачи). Выбрав подходящее решение, он, скорее всего, повторил изобретение одного из способов скрытой передачи информации, ко- которым уже не одна тысяча лет. Размышляя над задачей ТП, нетрудно прийти к выводу, что есть три возможности. 1. Создать абсолютно надежный, недоступный для других канал связи между абонентами. 2. Использовать общедоступный канал связи, но скрыть сам факт передачи информации. 3. Использовать общедоступный канал связи, но передавать по нему нужную информацию в так преобразованном виде, чтобы восстановить ее мог только адресат. Прокомментируем эти три возможности. 1. При современном уровне развития науки и техники сделать такой канал связи между удаленными абонентами для неоднократной переда- передачи больших объемов информации практически нереально. 2. Разработкой средств и методов скрытия факта передачи сообще- сообщения занимается стеганография. Первые следы стеганографических методов теряются в глубокой древ- древности. Например, известен такой способ скрытия письменного сообщения: голову раба брили, на коже головы писали сообщение и после отрастания волос раба отправляли к адресату. Из детективных произведений хорошо известны различные способы тай- тайнописи между строк обычного, незащищаемого текста: от молока до сложных химических реактивов с последующей обработкой. Также из детективов известен метод «микроточки»: сообщение запи- записывается с помощью современной техники на очень маленький носитель 8 Глава 1 (микроточку), который пересылается с обычным письмом, например, под маркой или где-нибудь в другом, заранее обусловленном месте. В настоящее время в связи с широким распространением компьютеров известно много тонких методов «запрятывания» защищаемой информации внутри больших объемов информации, хранящейся в компьютере. Нагляд- Наглядный пример запрятывания текстового файла в графический можно найти в Интернете1"; он же приведен в журнале «Компьютерра», №48 B25) от 1 де- декабря 1997 г., на стр. 62. (Следует отметить, что авторы статьи в журна- журнале ошибочно относят стеганографию к криптографии. Конечно, с помощью стеганографии можно прятать и предварительно зашифрованные тексты, но, вообще говоря, стеганография и криптография - принципиально различные направления в теории и практике защиты информации.) 3. Разработкой методов преобразования (шифрования) информации с целью ее защиты от незаконных пользователей занимается крипто- криптография. Такие методы и способы преобразования информации называ- называются шифрами. Шифрование (зашифрование) - процесс применения шифра к за- защищаемой информации, т. е. преобразование защищаемой информации (открытого текста) в шифрованное сообщение (шифртекст, кри- криптограмму) с помощью определенных правил, содержащихся в шифре. Дешифрование - процесс, обратный шифрованию, т. е. преобразо- преобразование шифрованного сообщения в защищаемую информацию с помо- помощью определенных правил, содержащихся в шифре. Криптография - прикладная наука, она использует самые послед- последние достижения фундаментальных наук и, в первую очередь, матема- математики. С другой стороны, все конкретные задачи криптографии суще- существенно зависят от уровня развития техники и технологии, от приме- применяемых средств связи и способов передачи информации. 2. Предмет криптографии Что же является предметом криптографии? Для ответа на этот вопрос вернемся к задаче ТП, чтобы уточнить ситуацию и используе- используемые понятия. Прежде всего заметим, что эта задача возникает только для ин- информации, которая нуждается в защите. Обычно в таких случаях гово- говорят, что информация содержит тайну или является защищаемой, при- приватной, конфиденциальной, секретной. Для наиболее типичных, часто встречающихся ситуаций такого типа введены даже специальные по- понятия: - государственная тайна; - военная тайна; ://www.geocities.com/SiliconValley/Vista/6001/ Основные понятия криптографии - коммерческая тайна; - юридическая тайна; - врачебная тайна и т. д. Далее мы будем говорить о защищаемой информации, имея в виду следующие признаки такой информации: - имеется какой-то определенный круг законных пользователей, ко- которые имеют право владеть этой информацией; - имеются незаконные пользователи, которые стремятся овладеть этой информацией с тем, чтобы обратить ее себе во благо, а законным пользователям во вред. Для простоты мы вначале ограничимся рассмотрением только од- одной угрозы - угрозы разглашения информации. Существуют и другие угрозы для защищаемой информации со стороны незаконных пользо- пользователей: подмена, имитация и др. О них мы поговорим ниже. Теперь мы можем изобразить ситуацию, в которой возникает задача ТП, следующей схемой (см. рис. 1). А < т > В П Рис. 1. Здесь А и В --¦ удаленные законные пользователи защищаемой ин- информации; они хотят обмениваться информацией по общедоступному каналу связи. П - незаконный пользователь (противник), который мо- может перехватывать передаваемые по каналу связи сообщения и пытать- пытаться извлечь из них интересующую его информацию. Эту формальную схему можно считать моделью типичной ситуации, в которой применя- применяются криптографические методы защиты информации. Отметим, что исторически в криптографии закрепились некоторые воен- военные слова (противник, атака на шифр и др.) Они наиболее точно отражают смысл соответствующих криптографических понятий. Вместе с тем широ- широко известная военная терминология, основанная на понятии кода (военно- морские коды, коды Генерального штаба, кодовые книги, кодобозначения и т.п.), уже не применяется в теоретической криптографии. Дело в том, что за последние десятилетия сформировалась теория кодирования - большое научное направление, которое разрабатывает и изучает методы защиты ин- информации от случайных искажений в каналах связи. И если ранее термины кодирование и шифрование употреблялись как синонимы, то теперь это недо- недопустимо. Так, например, очень распространенное выражение «кодирование - разновидность шифрования» становится просто неправильным. Криптография занимается методами преобразования информации, которые бы не позволили противнику извлечь ее из перехватываемых 10 Глава 1 сообщений. При этом по каналу связи передается уже не сама защища- защищаемая информация, а результат ее преобразования с помощью шифра, и для противника возникает сложная задача вскрытия шифра. Вскрытие {взламывание) шифра - процесс получения защищаемой информации из шифрованного сообщения без знания примененного ши- шифра. Однако помимо перехвата и вскрытия шифра противник может пы- пытаться получить защищаемую информацию многими другими способа- способами. Наиболее известным из таких способов является агентурный, когда противник каким-либо путем склоняет к сотрудничеству одного из за- законных пользователей и с помощью этого агента получает доступ к защищаемой информации. В такой ситуации криптография бессильна. Противник может пытаться не получить, а уничтожить или моди- модифицировать защищаемую информацию в процессе ее передачи. Это - совсем другой тип угроз для информации, отличный от перехвата и вскрытия шифра. Для защиты от таких угроз разрабатываются свои специфические методы. Следовательно, на пути от одного законного пользователя к друго- другому информация должна защищаться различными способами, противо- противостоящими различным угрозам. Возникает ситуация цепи из разнотип- разнотипных звеньев, которая защищает информацию. Естественно, противник будет стремиться найти самое слабое звено, чтобы с наименьшими за- затратами добраться до информации. А значит, и законные пользователи должны учитывать это обстоятельство в своей стратегии защиты: бес- бессмысленно делать какое-то звено очень прочным, если есть заведомо более слабые звенья («принцип равнопрочности защиты»). Не следует забывать и еще об одной важной проблеме: проблеме соотношения цены информации, затрат на ее защиту и затрат на ее добывание. При современном уровне развития техники сами средства связи, а также разработка средств перехвата информации из них и средств защиты информации требуют очень больших затрат. Прежде чем защищать информацию, задайте себе два вопроса: 1) является ли она для противника более ценной, чем стоимость атаки; 2) является ли она для вас более ценной, чем стоимость защиты. Именно перечисленные соображения и являются решающими при выборе подходящих средств защиты: физических, стеганографических, криптографических и др. Некоторые понятия криптографии удобно иллюстрировать истори- историческими примерами, поэтому сделаем небольшое историческое отступ- отступление. Долгое время занятие криптографией было уделом чудаков-одиночек. Среди них были одаренные ученые, дипломаты, священнослужители. Извест- Основные понятия криптографии 11 ны случаи, когда криптография считалась даже черной магией. Этот период развития криптографии как искусства длился с незапамятных времен до на- начала XX века, когда появились первые шифровальные машины. Понимание математического характера решаемых криптографией задач пришло толь- только в середине XX века - после работ выдающегося американского ученого К. Шеннона. История криптографии связана с большим количеством дипломатических и военных тайн и поэтому окутана туманом легенд. Наиболее полная книга по истории криптографии содержит более тысячи страниц. Она опубликована в 1967 году и на русский язык не переведена1". На русском языке недавно вышел в свет фундаментальный труд по истории криптографии в России К Свой след в истории криптографии оставили многие хорошо известные исторические личности. Приведем несколько наиболее ярких примеров. Пер- Первые сведения об использовании шифров в военном деле связаны с именем спартанского полководца Лисандра (шифр «Сцитала»). Цезарь использовал в переписке шифр, который вошел в историю как «шифр Цезаря». В древней Греции был изобретен вид шифра, который в дальнейшем стал называться «квадрат Полития». Одну из первых книг по криптографии написал аббат И.Трителий A462-1516), живший в Германии. В 1566 году известный мате- математик Д. Кардано опубликовал работу с описанием изобретенной им системы шифрования («решетка Кардано»). Франция XVI века оставила в истории криптографии шифры короля Генриха IV и Ришелье. В упомянутой книге Т. А. Соболевой подробно описано много российских шифров, в том числе и «цифирная азбука» 1700 года, автором которой был Петр Великий. (Некото- (Некоторые примеры из книги приведены на форзаце.) Некоторые сведения о свойствах шифров и их применении можно найти и в художественной литературе, особенно в приключенческой, детективной и военной. Хорошее подробное объяснение особенностей одного из простей- простейших шифров - шифра замены и методов его вскрытия содержится в двух известных рассказах: «Золотой жук» Э. По и «Пляшущие человечки» А. Конан Дойла. Рассмотрим более подробно два примера. Шифр «Сцитала». Этот шифр известен со времен войны Спарты против Афин в V веке до н.э. Для его реализации использовалась сцитала - жезл, имеющий форму цилиндра. На сциталу виток к витку наматывалась узкая па- папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль оси сциталы записывался открытый текст. Лента разматывалась и получалось (для непосвященных), что поперек ленты в беспорядке написаны какие-то буквы. Затем лента отправлялась адресату. Адресат брал такую же сциталу, таким же образом наматывал на нее полученную ленту и читал сообщение вдоль оси сциталы. Отметим, что в этом шифре преобразование открытого текста в шифро- шифрованный заключается в определенной перестановке букв открытого текста. David. Codebreakers. The story of Secret Writing. New York: Macmillan, 1967. 2" Соболева Т. А. Тайнопись в истории России (История криптографической служ- службы России XVIII - начала XX в.). М., 1994. 12 Глава 1 Поэтому класс шифров, к которым относится и шифр «Сцитала», называет- называется шифрами перестановки. Шифр Цезаря. Этот шифр реализует следующее преобразование откры- открытого текста: каждая буква открытого текста заменяется третьей после нее буквой в алфавите, который считается написанным по кругу, т. е. после бу- буквы «я» следует буква «а». Отметим, что Цезарь заменял букву третьей после нее буквой, но можно заменять и какой-нибудь другой. Главное, чтобы тот, кому посылается шифрованное сообщение, знал эту величину сдвига. Класс шифров, к которым относится и шифр Цезаря, называется шифрами замены. Из предыдущего изложения понятно, что придумывание хорошего шифра - дело трудоемкое. Поэтому желательно увеличить «время жиз- жизни» хорошего шифра и использовать его для шифрования как можно большего количества сообщений. Но при этом возникает опасность, что противник уже разгадал (вскрыл) шифр и читает защищаемую инфор- информацию. Если же в шифре есть сменный ключ, то, заменив ключ, можно сделать так, что разработанные противником методы уже не дают эф- эффекта. Под ключом в криптографии понимают сменный элемент шифра, который применяется для шифрования конкретного сообщения. Напри- Например, в шифре «Сцитала» ключом является диаметр сциталы, а в шифрах типа шифра Цезаря ключом является величина сдвига букв шифртек- ста относительно букв открытого текста. Описанные соображения привели к тому, что безопасность защи- защищаемой информации стала определяться в первую очередь ключом. Сам шифр, шифрмашина или принцип шифрования стали считать из- известными противнику и доступными для предварительного изучения, но в них появился неизвестный для противника ключ, от которого существенно зависят применяемые преобразования информации. Те- Теперь законные пользователи, прежде чем обмениваться шифрованны- шифрованными сообщениями, должны тайно от противника обменяться ключами или установить одинаковый ключ на обоих концах канала связи. А для противника появилась новая задача - определить ключ, после чего можно легко прочитать зашифрованные на этом ключе сообще- сообщения. Вернемся к формальному описанию основного объекта криптогра- криптографии (рис. 1, стр. 9). Теперь в него необходимо внести существенное изменение - добавить недоступный для противника секретный канал связи для обмена ключами (см. рис. 2). Создать такой канал связи впол- вполне реально, поскольку нагрузка на него, вообще говоря, небольшая. Отметим теперь, что не существует единого шифра, подходяще- подходящего для всех случаев. Выбор способа шифрования зависит от особен- особенностей информации, ее ценности и возможностей владельцев по за- защите своей информации. Прежде всего подчеркнем большое разно- Основные понятия криптографии 13 ключи д <- " сообщения " . „ П Рис. 2. образие видов защищаемой информации: документальная, телефон- телефонная, телевизионная, компьютерная и т. д. Каждый вид информации имеет свои специфические особенности, и эти особенности сильно влияют на выбор методов шифрования информации. Большое зна- значение имеют объемы и требуемая скорость передачи шифрованной информации. Выбор вида шифра и его параметров существенно за- зависит от характера защищаемых секретов или тайны. Некоторые тайны (например, государственные, военные и др.) должны сохра- сохраняться десятилетиями, а некоторые (например, биржевые) - уже че- через несколько часов можно разгласить. Необходимо учитывать так- также и возможности того противника, от которого защищается данная информация. Одно дело - противостоять одиночке или даже бан- банде уголовников, а другое дело - мощной государственной структу- структуре. Способность шифра противостоять всевозможным атакам на него называют стойкостью шифра. Под атакой на шифр понимают попытку вскрытия этого шифра. Понятие стойкости шифра является центральным для криптогра- криптографии. Хотя качественно понять его довольно легко, но получение стро- строгих доказуемых оценок стойкости для каждого конкретного шифра - проблема нерешенная. Это объясняется тем, что до сих пор нет необ- необходимых для решения такой проблемы математических результатов. (Мы вернемся к обсуждению этого вопроса ниже.) Поэтому стойкость конкретного шифра оценивается только путем всевозможных попыток его вскрытия и зависит от квалификации крипто аналитике в, атаку- атакующих шифр. Такую процедуру иногда называют проверкой стойко- стойкости. Важным подготовительным этапом для проверки стойкости шифра является продумывание различных предполагаемых возможностей, с помощью которых противник может атаковать шифр. Появление та- таких возможностей у противника обычно не зависит от криптографии, это является некоторой внешней подсказкой и существенно влияет на стойкость шифра. Поэтому оценки стойкости шифра всегда содержат те предположения о целях и возможностях противника, в условиях ко- которых эти оценки получены. 14 Глава 1 Прежде всего, как это уже отмечалось выше, обычно считается, что противник знает сам шифр и имеет возможности для его предва- предварительного изучения. Противник также знает некоторые характери- характеристики открытых текстов, например, общую тематику сообщений, их стиль, некоторые стандарты, форматы и т. д. Из более специфических приведем еще три примера возможностей противника: - противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов; - противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты; - противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровывать и дешифровывать любую информацию. На протяжении многих веков среди специалистов не утихали споры о стойкости шифров и о возможности построения абсолютно стойкого шифра. Приведем три характерных высказывания на этот счет. Английский математик Чарльз Беббидж (XIX в.): «Всякий человек, даже если он не знаком с техникой вскрытия шифров, твер- твердо считает, что сможет изобрести абсолютно стойкий шифр, и чем более умен и образован этот человек, тем более твердо это убеждение. Я сам раз- разделял эту уверенность в течение многих лет.» «Отец кибернетики» Норберт Винер: «Любой шифр может быть вскрыт, если только в этом есть настоятельная необходимость и информация, которую предполагается получить, стоит за- затраченных средств, усилий и времени...» Автор шифра PGP Ф. Зиммерманн («Компьютерра», №48 от 1.12.1997, стр. 45-46): «Каждый, кто думает, что изобрел непробиваемую схему шифрования, - или невероятно редкий гений, или просто наивен и неопытен...» «Каждый программист воображает себя криптографом, что ведет к распро- распространению исключительно плохого криптообеспечения...» В заключение данного раздела сделаем еще одно замечание - о тер- терминологии. В последнее время наряду со словом «криптография» часто встречается и слово «криптология», но соотношение между ними не все- всегда понимается правильно. Сейчас происходит окончательное форми- формирование этих научных дисциплин, уточняются их предмет и задачи. Криптология - наука, состоящая из двух ветвей: криптографии и криптоанализа. Криптография - наука о способах преобразования (шифрования) информации с целью ее защиты от незаконных пользователей. Криптоанализ - наука (и практика ее применения) о методах и способах вскрытия шифров. Основные понятия криптографии 15 Соотношение криптографии и криптоанализа очевидно: криптогра- криптография - защита, т. е. разработка шифров, а криптоанализ - нападение, т. е. атака на шифры. Однако эти две дисциплины связаны друг с дру- другом, и не бывает хороших криптографов, не владеющих методами кри- криптоанализа. 3. Математические основы Большое влияние на развитие криптографии оказали появившиеся в середине XX века работы американского математика Клода Шен- Шеннона. В этих работах были заложены основы теории информации, а также был разработан математический аппарат для исследований во многих областях науки, связанных с информацией. Более того, приня- принято считать, что теория информации как наука родилась в 1948 го- году после публикации работы К. Шеннона «Математическая теория связи»1). В своей работе «Теория связи в секретных системах» Клод Шеннон обобщил накопленный до него опыт разработки шифров2". Оказалось, что даже в очень сложных шифрах в качестве типичных компонентов можно выделить такие простые шифры как шифры замены, шифры перестановки или их сочетания. Шифр замены является простейшим, наиболее популярным шифром. Типичными примерами являются шифр Цезаря, «цифирная азбука» Петра Великого и «пляшущие человечки» А. Конан Дойла. Как видно из самого названия, шифр замены осуществляет преобразование замены букв или других «частей» открытого текста на аналогичные «части» шифрованного текста. Легко дать математическое описание шифра замены. Пусть X и Y - два алфавита (открытого и шифрованного текстов соответственно), состоящие из одинакового числа символов. Пусть также д: X -> Y - взаимнооднозначное отображение X в У. Тогда шифр замены действует так: открытый текст х\х2 ¦¦.хп пре- преобразуется в шифрованный текст д(х1)д(х2) ¦ ¦ -д(хп). Шифр перестановки, как видно из названия, осуществляет преобра- преобразование перестановки букв в открытом тексте. Типичным примером шифра перестановки является шифр «Сцитала». Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок ши- шифруется независимо. Пусть, например, длина отрезков равна п и а - взаимнооднозначное отображение множества {1,2,..., п} в себя. Тогда шифр перестановки действует так: отрезок открытого текста х\ ... хп преобразуется в отрезок шифрованного текста ха^\) .. .ха(п). ^Shannon С. Е. A mathematical theory of communication // Bell System Techn. J. V. 27, №3, 1948. P. 379-423; V. 27, №4, 1948. P. 623-656. 2"См. Приложение. 16 Глава 1 Важнейшим для развития криптографии был результат К. Шен- Шеннона о существовании и единственности абсолютно стойкого шифра. Единственным таким шифром является какая-нибудь форма так на- называемой ленты однократного использования, в которой открытый текст «объединяется» с полностью случайным ключом такой же дли- длины. Этот результат был доказан К. Шенноном с помощью разработанно- разработанного им теоретико-информационного метода исследования шифров. Мы не будем здесь останавливаться на этом подробно, заинтересованному читателю рекомендуем изучить работу К.Шеннона1". Обсудим особенности строения абсолютно стойкого шифра и воз- возможности его практического использования. Типичным и наиболее про- простым примером реализации абсолютно стойкого шифра является шифр Вернама, который осуществляет побитовое сложение n-битового от- открытого текста и n-битового ключа: yi = Xi®ki, i = l,...,n. Здесь Xi ...хп - открытый текст, к\,...,кп - ключ, у\ ¦ ¦ .уп - ши- шифрованный текст. Подчеркнем, что для абсолютной стойкости существенным является каждое из следующих требований к ленте однократного использования: 1) полная случайность (равновероятность) ключа (это, в частности, означает, что ключ нельзя вырабатывать с помощью какого-либо де- детерминированного устройства); 2) равенство длины ключа и длины открытого текста; 3) однократность использования ключа. В случае нарушения хотя бы одного из этих условий шифр перестает быть абсолютно стойким и появляются принципиальные возможности для его вскрытия (хотя они могут быть трудно реализуемыми). Но, оказывается, именно эти условия и делают абсолютно стойкий шифр очень дорогим и непрактичным. Прежде чем пользоваться таким шифром, мы должны обеспечить всех абонентов достаточным запасом случайных ключей и исключить возможность их повторного примене- применения. А это сделать необычайно трудно и дорого. Как отмечал Д. Кан: «Проблема создания, регистрации, распространения и отмены ключей может показаться не слишком сложной тому, кто не име- имеет опыта передачи сообщений по каналам военной связи, но в военное вре- время объем передаваемых сообщений ставит в тупик даже профессиональных связистов. За сутки могут быть зашифрованы сотни тысяч слов. Создание миллионов ключевых знаков потребовало бы огромных финансовых издер- издержек и было бы сопряжено с большими затратами времени. Так как каждый текст должен иметь свой собственный, единственный и неповторимый ключ, 1"См. Приложение. Основные понятия криптографии 17 применение идеальной системы потребовало бы передачи по крайней мере такого количества знаков, которое эквивалентно всему объему передаваемой военной информации.» В силу указанных причин абсолютно стойкие шифры применяются только в сетях связи с небольшим объемом передаваемой информации, обычно это сети для передачи особо важной государственной инфор- информации. Теперь уже понятно, что чаще всего для защиты своей информа- информации законные пользователи вынуждены применять неабсолютно стой- стойкие шифры. Такие шифры, по крайней мере теоретически, могут быть вскрыты. Вопрос только в том, хватит ли у противника сил, средств и времени для разработки и реализации соответствующих ал- алгоритмов. Обычно эту мысль выражают так: противник с неогра- неограниченными ресурсами может вскрыть любой неабсолютно стойкий шифр. Как же должен действовать в этой ситуации законный пользова- пользователь, выбирая для себя шифр? Лучше всего, конечно, было бы дока- доказать, что никакой противник не может вскрыть выбранный шифр, ска- скажем, за 10 лет и тем самым получить теоретическую оценку стойкости. К сожалению, математическая теория еще не дает нужных теорем - они относятся к нерешенной проблеме нижних оценок вычислительной сложности задач. \ Поэтому у пользователя остается единственный путь - получение практических оценок стойкости. Этот путь состой^ из следующих эта- этапов: ," - понять и четко сформулировать, от какого противника мы соби- собираемся защищать информацию; необходимо уяснить, что именно про- противник знает или сможет узнать о системе шифрй, а также какие силы и средства он сможет применить для его вскрытия; - мысленно стать в положение противника и пытаться с его позиций атаковать шифр, т.е. разрабатывать различные алгоритмы вскрытия шифра; при этом необходимо в максимальной мере обеспечить модели- моделирование сил, средств и возможностей противника; - наилучший из разработанных алгоритмов использовать для прак- практической оценки стойкости шифра. Здесь полезно для иллюстрации упомянуть о двух простейших мето- методах вскрытия шифра: случайное угадывание ключа (он срабатывает с маленькой вероятностью, зато имеет маленькую сложность) и перебор всех подряд ключей вплоть до нахождения истинного (он срабатывает всегда, зато имеет очень большую сложность). Отметим также, что не всегда нужна атака на ключ: для некоторых шифров можно сразу, даже не зная ключа, восстанавливать открытый текст по шифрованному. 18 Глава 1 4. Новые направления В 1983 году в книге «Коды и математика» М. Н. Аршинова и Л. Е. Са- Садовского (библиотечка «Квант») было написано: «Приемов тайнописи - великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое.» Однако это было оче- очередное большое заблуждение относительно криптографии. Еще в 1976 году была опубликована работа молодых американских математиков У.Диффи и М.Э.Хеллмана «Новые направления в криптографии»1", которая не только существенно изменила криптографию, но и привела к появлению и бурному развитию новых направлений в математике. Центральным понятием «новой криптографии» является понятие одно- односторонней функции (подробнее об этом см. главу 2). Односторонней называется функция F: X -> У, обладающая двумя свойствами: а) существует полиномиальный алгоритм вычисления значений F(x); б) не существует полиномиального алгоритма инвертирования фун- функции F (т. е. решения уравнения F(x) = у относительно х, точное определение см. на стр. 30). Отметим, что односторонняя функция существенно отличается от функций, привычных со школьной скамьи, из-за ограничений на слож- сложность ее вычисления и инвертирования. Вопрос о существовании одно- односторонних функций пока открыт. Еще одним новым понятием является понятие функции с секретом. Иногда еще употребляется термин функция с ловушкой. Функцией с се- секретом К называется функция Fk: X -> Y, зависящая от параметра К и обладающая тремя свойствами: а) существует полиномиальный алгоритм вычисления значения Fk(x) для любых К и х; б) не существует полиномиального алгоритма инвертирования Fa при неизвестном К; в) существует полиномиальный алгоритм инвертирования Fk при известном К. Про существование функций с секретом можно сказать то же са- самое, что сказано про односторонние функции. Для практических це- целей криптографии было построено несколько функций, которые могут оказаться функциями с секретом. Для них свойство б) пока строго не доказано, но считается, что задача инвертирования эквивалентна не- некоторой давно изучаемой трудной математической задаче. Наиболее известной и популярной из них является теоретико-числовая функция, на которой построен шифр RSA (подробнее об этом см. главу 4). ""Диффи У., Хеллман М. Э. Защищенность и имитостойкость. Введение в крип- криптографию // ТИИЭР. Т. 67, №3, 1979. Основные понятия криптографии 19 Применение функций с секретом в криптографии позволяет: 1) организовать обмен шифрованными сообщениями с использова- использованием только открытых каналов связи, т. е. отказаться от секретных каналов связи для предварительного обмена ключами; 2) включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра; 3) решать новые криптографические задачи, отличные от шифро- шифрования (электронная цифровая подпись и др.). Опишем, например, как можно реализовать п. 1). Пользователь А, который хочет получать шифрованные сообщения, должен выбрать какую-нибудь функцию Fk с секретом К. Он сообщает всем заинте- заинтересованным (например, публикует) описание функции Fk в качестве своего алгоритма шифрования. Но при этом значение секрета К он никому не сообщает и держит в секрете. Если теперь пользователь В хочет послать пользователю А защищаемую информацию ж? X, то он вычисляет у = Fk(x) и посылает у по открытому каналу пользовате- пользователю А. Поскольку А для своего секрета К умеет инвертировать Fk, to он вычисляет х по полученному у. Никто другой не знает К и поэтому в силу свойства б) функции с секретом не сможет за полиномиальное время по известному шифрованному сообщению Fk{x) вычислить за- защищаемую информацию х. Описанную систему называют криптосистемой с открытым клю- ключом, поскольку алгоритм шифрования Fk является общедоступным или открытым. В последнее время такие криптосистемы еще называют асимметричными, поскольку в них есть асимметрия в алгоритмах: ал- алгоритмы шифрования и дешифрования различны. В отличие от таких систем традиционные шифры называют симметричными: в них ключ для шифрования и дешифрования один и тот же. Для асимметричных систем алгоритм шифрования общеизвестен, но восстановить по нему алгоритм дешифрования за полиномиальное время невозможно. Описанную выше идею Диффи и Хеллман предложили использовать также для электронной цифровой подписи сообщений, которую невоз- невозможно подделать за полиномиальное время. Пусть пользователю А не- необходимо подписать сообщение х. Он, зная секрет К, находит такое у, что Рк{у) - х, и вместе с сообщением х посылает у пользователю В в качестве своей цифровой подписи. Пользователь В хранит у в качестве доказательства того, что А подписал сообщение х. Сообщение, подписанное цифровой подписью, можно представлять себе как пару (х,у), где х - сообщение, у - решение уравнения Рк{у) - х, Fk"¦ X -> Y - функция с секретом, известная всем вза- взаимодействующим абонентам. Из определения функции Fk очевидны следующие полезные свойства цифровой подписи: 20 Глава 1 1) подписать сообщение х, т.е. решить уравнение Fn(y) = х, может только абонент - обладатель данного секрета К; другими словами, подделать подпись невозможно; 2) проверить подлинность подписи может любой абонент, знающий открытый ключ, т.е. саму функцию Fk\ 3) при возникновении споров отказаться от подписи невозможно в силу ее неподделываемости; 4) подписанные сообщения (х, у) можно, не опасаясь ущерба, пере- пересылать по любым каналам связи. Кроме принципа построения криптосистемы с открытым ключом, Диффи и Хеллман в той же работе предложили еще одну новую идею - открытое распределение ключей. Они задались вопросом: можно ли организовать такую процедуру взаимодействия абонентов А и В по открытым каналам связи, чтобы решить следующие задачи: 1) вначале у А ш В нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у А и В появляется, т. е. вырабатывается; 2) пассивный противник, который перехватывает все передачи ин- информации и знает, что хотят получить А и В, тем не менее не может восстановить выработанный общий ключ А ж В. Диффи и Хеллман предложили решать эти задачи с помощью функ- функции F(x) = ах (mod p), где р - большое простое число, х - произвольное натуральное чи- число, q - некоторый примитивный элемент поля GF(p). Общепризнан- Общепризнанно, что инвертирование функции ах (modp), т.е. дискретное лога- логарифмирование, является трудной математической задачей. (Подробнее см. главу 4.) Сама процедура или, как принято говорить, протокол выработки общего ключа описывается следующим образом. Абоненты А и В независимо друг от друга случайно выбирают по одному натуральному числу - скажем ха и хв- Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент: у А = otXA (mod p), у в = аХв (mod p). (Числа р и а считаются общедоступными.) Потом они обмениваются этими элементами по каналу связи. Теперь абонент А, получив ув и зная свой секретный элемент ха, вычисляет новый элемент: ухвА (modp) = (aXB)XA (modp). Аналогично поступает абонент В: ухАв (mod р) = (аХА)Хв (mod p). Основные понятия криптографии 21 Тем самым у А и В появился общий элемент поля, равный аХлХв. Этот элемент и объявляется общим ключом А и В. Из описания протокола видно, что противник знает р,а,аХА,аХв, не знает ха и хц и хочет узнать аХАХв. В настоящее время нет ал- алгоритмов действий противника, более эффективных, чем дискретное логарифмирование, а это - трудная математическая задача. Успехи, достигнутые в разработке схем цифровой подписи и откры- открытого распределения ключей, позволили применить эти идеи также и к другим задачам взаимодействия удаленных абонентов. Так возникло большое новое направление теоретической криптографии - крипто- криптографические протоколы (подробнее см. главу 3). Объектом изучения теории криптографических протоколов являют- являются удаленные абоненты, взаимодействующие, как правило, по откры- открытым каналам связи. Целью взаимодействия абонентов является реше- решение какой-то задачи. Имеется также противник, который преследует собственные цели. При этом противник в разных задачах может иметь разные возможности: например, может взаимодействовать с абонента- абонентами от имени других абонентов или вмешиваться в обмены информацией между абонентами и т. д. Противником может даже оказаться один из абонентов или несколько абонентов, вступивших в сговор. Приведем еще несколько примеров задач, решаемых удаленными абонентами. (Читателю рекомендуем по своему вкусу самостоятельно придумать еще какие-нибудь примеры.) 1. Взаимодействуют два не доверяющих друг другу абонента. Они хотят подписать контракт. Это надо сделать так, чтобы не допустить следующую ситуацию: один из абонентов получил подпись другого, а сам не подписался. Протокол решения этой задачи принято называть протоколом подписания контракта. 2. Взаимодействуют два не доверяющих друг другу абонента. Они хотят бросить жребий с помощью монеты. Это надо сделать так, что- чтобы абонент, подбрасывающий монету, не мог изменить результат под- подбрасывания после получения догадки от абонента, угадывающего этот результат. Протокол решения этой задачи принято называть протоколом подбрасывания монеты. Опишем один из простейших протоколов подбрасывания монеты по теле- телефону (так называемая схема Блюма-Микали). Для его реализации у абонен- абонентов Аи В должна быть односторонняя функция /: X -> У, удовлетворяющая следующим условиям: 1) X - множество целых чисел, которое содержит одинаковое количество четных и нечетных чисел; 22 Глава 1 2) любые числа xi,X2 ? X, имеющие один образ }{х\) - одну четность; 3) по заданному образу f(x) «трудно» вычислить четность неизвестного аргумента х. Роль подбрасывания монеты играет случайный и равновероятный выбор элемента х 6 X, а роль орла и решки - четность и нечетность х соот- соответственно. Пусть А - абонент, подбрасывающий монету, а В - абонент, угадывающий результат. Протокол состоит из следующих шагов: 1) А выбирает х («подбрасывает монету»), зашифровывает х, т. е. вычи- вычисляет у = f(x), и посылает у абоненту В; 2) В получает у, пытается угадать четность х и посылает свою догадку абоненту А; 3) А получает догадку от В и сообщает В, угадал ли он, посылая ему выбранное число х; 4) В проверяет, не обманывает ли А, вычисляя значение /(ж) и сравнивая его с полученным на втором шаге значением у. 3. Взаимодействуют два абонента А и В (типичный пример: А - клиент банка, В - банк). Абонент А хочет доказать абоненту В, что он именно А, а не противник. Протокол решения этой задачи принято называть протоколом иден- идентификации абонента. 4. Взаимодействуют несколько удаленных абонентов, получивших приказы из одного центра. Часть абонентов, включая центр, могут быть противниками. Необходимо выработать единую стратегию дей- действий, выигрышную для абонентов. Эту задачу принято называть задачей о византийских генералах, а протокол ее решения - протоколом византийского соглашения. Опишем пример, которому эта задача обязана своим названием. Визан- Византия. Ночь перед великой битвой. Византийская армия состоит из п легионов, каждый из которых подчиняется своему генералу. Кроме того, у армии есть главнокомандующий, который руководит генералами. Однако империя нахо- находится в упадке и до одной трети генералов, включая главнокомандующего, могут быть предателями. В течение ночи каждый из генералов получает от главнокомандующего приказ о действиях на утро, причем возможны два ва- варианта приказа: «атаковать» или «отступать». Если все честные генералы атакуют, то они побеждают. Если все они отступают, то им удается со- сохранить армию. Но если часть из них атакует, а часть отступает, то они терпят поражение. Если главнокомандующий окажется предателем, то он может дать разным генералам разные приказы, поэтому приказы главноко- главнокомандующего не стоит выполнять беспрекословно. Если каждый генерал будет действовать независимо от остальных, результаты могут оказаться плачев- плачевными. Очевидно, что генералы нуждаются в обмене информацией друг с другом (относительно полученных приказов) с тем, чтобы прийти к согла- соглашению. Основные понятия криптографии 23 Осмысление различных протоколов и методов их построения приве- привело в 1985--1986 г.г. к появлению двух плодотворных математических мо- моделей - интерактивной системы доказательства и доказательства с нулевым разглашением. Математические исследования этих новых объектов позволили доказать много утверждений, весьма полезных при разработке криптографических протоколов (подробнее об этом см. гла- ву 2). Под интерактивной системой доказательства (Р, V, S) понимают протокол взаимодействия двух абонентов: Р (доказывающий) и V (про- (проверяющий). Абонент Р хочет доказать V, что утверждение 5 истинно. При этом абонент V самостоятельно, без помощи Р, не может прове- проверить утверждение S (поэтому V и называется проверяющим). Абонент Р может быть и противником, который хочет доказать V, что утверж- утверждение S истинно, хотя оно ложно. Протокол может состоять из многих раундов обмена сообщениями между Р и V и должен удовлетворять двум условиям: 1) полнота - если 5 действительно истинно, то абонент Р убедит абонента V признать это; 2) корректность - если 5 ложно, то абонент Р вряд ли убедит абонента V, что 5 истинно. Здесь словами «вряд ли» мы для простоты заменили точную мате- математическую формулировку. Подчеркнем, что в определении системы (Р, V, S) не допуска- допускалось, что V может быть противником. А если V оказался против- противником, который хочет «выведать» у Р какую-нибудь новую полез- полезную для себя информацию об утверждении 5? В этом случае Р, ес- естественно, может не хотеть, чтобы это случилось в результате ра- работы протокола (Р, V, S). Протокол (Р, V, S), решающий такую за- задачу, называется доказательством с нулевым разглашением и дол- должен удовлетворять, кроме условий 1) и 2), еще и следующему усло- условию: 3) нулевое разглашение - в результате работы протокола (Р, V, S) абонент V не увеличит свои знания об утверждении S или, другими словами, не сможет извлечь никакой информации о том, почему S ис- истинно. 5. Заключение За последние годы криптография и криптографические методы все шире входят в нашу жизнь и даже быт. Вот несколько примеров. От- Отправляя Email, мы в некоторых случаях отвечаем на вопрос меню: «Нужен ли режим зашифрования?» Владелец интеллектуальной банков- банковской карточки, обращаясь через терминал к банку, вначале выполняет 24 Глава 1 криптографический протокол аутентификации карточки. Пользовате- Пользователи сети Интернет наверняка знакомы с дискуссиями вокруг возмож- возможного принятия стандарта цифровой подписи для тех страниц, которые содержат «критическую» информацию (юридическую, прайс-листы и др.). С недавних пор пользователи сетей стали указывать после своей фамилии наряду с уже привычным «Email ... » и менее привычное - «Отпечаток открытого ключа... ». С каждым днем таких примеров становится все больше. Именно новые практические приложения криптографии и являются одним из источников ее развития. Глава 2 Криптография и теория сложности Основное внимание в настоящей главе мы уделяем разъяснению важ- важнейших идей, связанных с применением теоретико-сложностного под- подхода в криптографии. Изложение по необходимости недостаточно фор- формальное - для математической криптографии типичны многостранич- многостраничные определения. Предполагается знакомство читателя с основами те- теории сложности вычислений: понятиями машины Тьюринга, классов Р и NP (см. ), а также с главой 1 настоящей книги. 1. Введение В теоретической криптографии существуют два основных подхода к определению стойкости криптосистем и криптографических прото- протоколов (в дальнейшем мы будем также использовать общий термин - криптографические схемы): теоретико-информационный и теоретико- сложностной. Теоретико-информационный подход предполагает, что противник, атакующий криптографическую схему, не имеет даже тео- теоретической возможности получить информацию, достаточную для осу- осуществления своих целей. Классическим примером здесь может служить шифр Вернама с одноразовыми ключами, абсолютно стойкий против пассивного противника. Подавляющее большинство используемых на практике криптогра- криптографических схем не обладает столь высокой стойкостью. Более того, обычно бывает несложно указать алгоритм, который выполняет сто- стоящую перед противником задачу, но не практически, а в принципе. Рассмотрим следующий пример. Пример 1 (Криптосистема с открытым ключом). Криптосис- Криптосистема с открытым ключом полностью определяется тремя алгоритма- алгоритмами: генерации ключей, шифрования и дешифрования. Алгоритм гене- генерации ключей G общедоступен; всякий желающий может подать ему на вход случайную строку г надлежащей длины и получить пару ключей (А"1,Хг). Открытый ключ К\ публикуется, а секретный ключ К-i и случайная строка г хранятся в секрете. Алгоритмы шифрования Екх и 26 Глава 2 дешифрования D^2 таковы, что если (К\, K-i) - пара ключей, сгенери- сгенерированная алгоритмом G, то Dk2(Ek1 [т)) = т для любого открытого текста т. Для простоты изложения предполагаем, что открытый текст и криптограмма имеют одинаковую длину п. Кроме того, считаем, что открытый текст, криптограмма и оба ключа являются строками в дво- двоичном алфавите. Предположим теперь, что противник атакует эту криптосистему. Ему известен открытый ключ К\, но неизвестен соответствующий се- секретный ключ Ki. Противник перехватил криптограмму d и пытается найти сообщение т, где d = Ец^ (т). Поскольку алгоритм шифрования общеизвестен, противник может просто последовательно перебрать все возможные сообщения длины п, вычислить для каждого такого сооб- сообщения ТП{ криптограмму di = Екх (тп-г) и сравнить di с d. To сообщение, для которого di = d, и будет искомым открытым текстом. Если пове- повезет, то открытый текст будет найден достаточно быстро. В худшем же случае перебор будет выполнен за время порядка 2"Т(п), где Т(п) - время, требуемое для вычисления функции Ек, от сообщений длины п. Если сообщения имеют длину порядка 1000 битов, то такой перебор неосуществим на практике ни на каких самых мощных компьютерах. Мы рассмотрели лишь один из возможных способов атаки на кри- криптосистему и простейший алгоритм поиска открытого текста, назы- называемый обычно алгоритмом полного перебора. Используется также и другое название: «метод грубой силы». Другой простейший алгоритм поиска открытого текста - угадывание. Этот очевидный алгоритм требует небольших вычислений, но срабатывает с пренебрежимо малой вероятностью (при больших длинах текстов). На самом деле противник может пытаться атаковать криптосистему различными способами и использовать различные, более изощренные алгоритмы поиска откры- открытого текста. Естественно считать криптосистему стойкой, если любой такой алгоритм требует практически неосуществимого объема вычи- вычислений или срабатывает с пренебрежимо малой вероятностью. (При этом противник может использовать не только детерминированные, но и вероятностные алгоритмы.) Это и есть теоретико-сложностной под- подход к определению стойкости. Для его реализации в отношении того или иного типа криптографических схем необходимо выполнить следу- следующее: 1) дать формальное определение схемы данного типа; 2) дать формальное определение стойкости схемы; 3) доказать стойкость конкретной конструкции схемы данного ти- типа. Здесь сразу же возникает ряд проблем. Во-первых, в криптографических схемах, разумеется, всегда ис- используются фиксированные значения параметров. Например, крипто- Криптография и теория сложности 27 системы разрабатываются для ключей длины, скажем, в 256 или 512 байтов. Для применения же теоретико-сложностного подхода необхо- необходимо, чтобы задача, вычислительную сложность которой предполага- предполагается использовать, была массовой. Поэтому в теоретической крипто- криптографии рассматриваются математические модели криптографических схем. Эти модели зависят от некоторого параметра, называемого пара- параметром безопасности, который может принимать сколь угодно большие значения (обычно для простоты предполагается, что параметр безопас- безопасности может пробегать весь натуральный ряд). Во-вторых, определение стойкости криптографической схемы зави- зависит от той задачи, которая стоит перед противником, и от того, какая информация о схеме ему доступна. Поэтому стойкость схем приходит- приходится определять и исследовать отдельно для каждого предположения о противнике. В-третьих, необходимо уточнить, какой объем вычислений можно считать «практически неосуществимым». Из сказанного выше следу- следует, что эта величина не может быть просто константой, она должна быть представлена функцией от растущего параметра безопасности. В соответствии с тезисом Эдмондса алгоритм считается эффективным, если время его выполнения ограничено некоторым полиномом от дли- длины входного слова (в нашем случае - от параметра безопасности). В противном случае говорят, что вычисления по данному алгоритму практически неосуществимы. Заметим также, что сами криптографи- криптографические схемы должны быть эффективными, т. е. все вычисления, пред- предписанные той или иной схемой, должны выполняться за полиномиальное время. В-четвертых, необходимо определить, какую вероятность можно считать пренебрежимо малой. В криптографии принято считать та- таковой любую вероятность, которая для любого полинома р и для всех достаточно больших п не превосходит 1/р(п), где и - параметр безо- безопасности. Итак, при наличии всех указанных выше определений, проблема обо- обоснования стойкости криптографической схемы свелась к доказатель- доказательству отсутствия полиномиального алгоритма, который решает задачу, стоящую перед противником. Но здесь возникает еще одно и весьма се- серьезное препятствие: современное состояние теории сложности вычи- вычислений не позволяет доказывать сверхполиномиальные нижние оценки сложности для конкретных задач рассматриваемого класса. Из этого следует, что на данный момент стойкость криптографических схем мо- может быть установлена лишь с привлечением каких-либо недоказанных предположений. Поэтому основное направление исследований состоит в поиске наиболее слабых достаточных условий (в идеале - необходимых и достаточных) для существования стойких схем каждого из типов. 28 Глава 2 В основном, рассматриваются предположения двух типов - общие (или теоретико-сложностные) и теоретико-числовые, т. е. предположения о сложности конкретных теоретико-числовых задач. Все эти предполо- предположения в литературе обычно называются криптографическими. Ниже мы кратко рассмотрим несколько интересных математиче- математических объектов, возникших на стыке теории сложности и криптографии. Более подробный обзор по этим вопросам можно найти в книге . 2. Криптография и гипотеза Как правило, знакомство математиков-неспециалистов с теорией сложности вычислений ограничивается классами Р и NP и знаменитой гипотезой Напомним вкратце необходимые сведения из теории сложности вычи- вычислений. Пусть?* - множество всех конечных строк в двоичном алфавите S = {0,1}. Подмножества L С S* в теории сложности принято называть язы- языками. Говорят, что машина Тьюринга М работает за полиномиальное время (или просто, что она полиномиальна), если существует полином р такой, что на любом входном слове длины п машина М останавливается после выполне- выполнения не более, чем р(п) операций. Машина Тьюринга М распознает (другой термин - принимает) язык L, если на всяком входном слове х Е L машина М останавливается в принимающем состоянии, а на всяком слове х $ L - в отвергающем. Класс Р - это класс всех языков, распознаваемых машинами Тьюринга, работающими за полиномиальное время. Функция / : 2* -> 2* вычислима за полиномиальное время, если существует полиномиальная ма- машина Тьюринга такая, что если на вход ей подано слово х Е?*, то в момент останова на ленте будет записано значение /(ж). Язык L принадлежит классу NP, если существуют предикат Р(х, у) : S* x S* -? {0,1}, вычислимый за по- полиномиальное время, и полином р такие, что L = {x\3yP(x,y)&i\y\ ^ p(|z|)}. Таким образом, язык L принадлежит NP, если для всякого слова из L дли- длины п можно угадать некоторую строку полиномиальной от п длины и за- затем с помощью предиката Р убедиться в правильности догадки. Ясно, что Р С NP. Является ли это включение строгим - одна из самых известных не- нерешенных задач математики. Большинство специалистов считают, что оно строгое (так называемая гипотеза P^NP). В классе NP выделен подкласс максимально сложных языков, называемых NP-полными: любой NP-полный язык распознаваем за полиномиальное время тогда и только тогда, когда P=NP. Для дальнейшего нам потребуется еще понятие вероятностной машины Тьюринга. В обычных машинах Тьюринга (их называют детерминированны- детерминированными, чтобы отличить от вероятностных) новое состояние, в которое машина переходит на очередном шаге, полностью определяется текущим состояни- состоянием и тем символом, который обозревает головка на ленте. В вероятностных машинах новое состояние может зависеть еще и от случайной величины, ко- которая принимает значения 0 и 1 с вероятностью 1/2 каждое. Альтернативно, Криптография и теория сложности 29 можно считать, что вероятностная машина Тьюринга имеет дополнитель- дополнительную случайную ленту, на которой записана бесконечная двоичная случайная строка. Случайная лента может читаться только в одном направлении и пе- переход в новое состояние может зависеть от символа, обозреваемого на этой ленте. Рассмотрим теперь следующий естественный вопрос: не является ли гипотеза P^NP необходимым и достаточным условием для существо- существования стойких криптографических схем? Необходимость, и в самом деле, во многих случаях почти очевидна. Вернемся к примеру 1. Определим следующий язык L = {(Ki,d,i)\ существует сообщение т такое, что Ек^т) = d и его г-ый бит равен 1}. Ясно, что L ? NP: вместо описанного во введении полного перебора можно просто угадать открытый текст m и проверить за полиномиаль- полиномиальное время, что Efdim) = d и г-ый бит тп равен 1. Если да, то входное слово (Ki,d,i) принимается, в противном случае - отвергается. В предположении P=NP существует детерминированный полиноми- полиномиальный алгоритм, распознающий язык L. Зная К\ и d, с помощью это- этого алгоритма можно последовательно, по биту, вычислить открытый текст гп. Тем самым криптосистема нестойкая. Тот же подход: угадать секретный ключ и проверить (за полиноми- полиномиальное время) правильность догадки, применим в принципе и к другим криптографическим схемам. Однако, в некоторых случаях возникают технические трудности, связанные с тем, что по информации, которая имеется у противника, искомая величина (открытый текст, секретный ключ и т. п.) восстанавливается неоднозначно. Что же касается вопроса о достаточности предположения P^NP, то здесь напрашивается следующий подход: выбрать какую-либо NP- полную задачу и построить на ее основе криптографическую схему, задача взлома которой (т. е. задача, стоящая перед противником) была бы NP-полной. Такие попытки предпринимались в начале 80-х годов, в особенности в отношении криптосистем с открытым ключом, но к успеху не привели. Результатом всех этих попыток стало осознание сле- следующего факта: даже если P^NP, то любая NP-полная задача может оказаться трудной лишь на некоторой бесконечной последовательно- последовательности входных слов. Иными словами, в определение класса NP заложе- заложена мера сложности «в худшем случае». Для стойкости же криптогра- криптографической схемы необходимо, чтобы задача противника была сложной «почти всюду». Таким образом, стало ясно, что для криптографиче- криптографической стойкости необходимо существенно более сильное предположение, чем P^NP. А именно, предположение о существовании односторонних функций. 30 Глава 2 3. Односторонние функции Говоря неформально, односторонняя функция - это эффективно вычислимая функция, для задачи инвертирования которой не сущест- существует эффективных алгоритмов. Под инвертированием понимается мас- массовая задача нахождения по заданному значению функции одного (лю- (любого) значения из прообраза (заметим, что обратная функция, вообще говоря, может не существовать). Поскольку понятие односторонней функции - центральное в мате- математической криптографии, ниже мы даем его формальное определение. Пусть Е™ = {0,1}" - множество всех двоичных строк длины п. Под функцией / мы понимаем семейство {/„}, где /„ : Е" -> Ет, т = т,(п). Для простоты изложения мы предполагаем, что п пробегает весь натуральный ряд и что каждая из функций /„ всюду определена. Функция / называется честной, если существует полином q такой, что п $С q{m(n)) для всех п. Определение 1. Честная функция / называется односторонней, если 1. Существует полиномиальный алгоритм, который для всякого х вычисляет f(x). 2. Для любой полиномиальной вероятностной машины Тьюринга А выполнено следующее. Пусть строка х выбрана наудачу из множест- множества Е" (обозначается х €д X"). Тогда для любого полинома р и всех достаточно больших п Pr{f(A(f(x))) = /(*)} < l/p(n). Вероятность здесь определяется случайным выбором строки х и слу- случайными величинами, которые А использует в своей работе. Условие 2 качественно означает следующее. Любая полиномиальная вероятностная машина Тьюринга А может по данному у найти х из уравнения f(x) = у лишь с пренебрежимо малой вероятностью. Заметим, что требование честности нельзя опустить. Поскольку длина входного слова f(x) машины А равна т, ей может не хватить полиномиального (от т) времени просто на выписывание строки х, ес- если / слишком сильно «сжимает» входные значения. Ясно, что из предположения о существовании односторонних функ- функций следует, что P^NP. Однако, не исключена следующая ситуация: P^NP, но односторонних функций нет. Существование односторонних функций является необходимым ус- условием для стойкости многих типов криптографических схем. В неко- некоторых случаях этот факт устанавливается достаточно просто. Обра- Обратимся опять к примеру 1. Рассмотрим функцию / такую, что /(г) = К\. Она вычислима с помощью алгоритма G за полиномиальное время. По- Покажем, что если / - не односторонняя функция, то криптосистема Криптография и теория сложности 31 нестойкая. Предположим, что существует полиномиальный вероятност- вероятностный алгоритм Л, который инвертирует / с вероятностью по крайней мере 1/р(п) для некоторого полинома р. Здесь п - длина ключа К\. Противник может подать на вход алгоритму А ключ К\ и получить с указанной вероятностью некоторое значение г" из прообраза. Далее противник подает г" на вход алгоритма G и получает пару ключей (Ki,K2). Хотя К2 не обязательно совпадает с К^, тем не менее, по определению криптосистемы DK* {Екг (тп)) = m для любого открытого текста т. Поскольку К2 найден с вероятностью по крайней мере 1/р(п), которая в криптографии не считается пренебрежимо малой, криптоси- криптосистема нестойкая. Для других криптографических схем подобный результат доказы- доказывается не столь просто. В работе Импальяццо и Луби доказана не- необходимость односторонних функций для существования целого ряда стойких криптографических схем. Из всего сказанного следует, что предположение о существова- существовании односторонних функций является самым слабым криптографи- криптографическим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем раз- различных типов. На выяснение того, является ли это условие и в са- самом деле достаточным, направлены значительные усилия специалистов. Трудность задачи построения криптографических схем из односто- односторонних функций можно пояснить на следующем примере. Пусть / - односторонняя функция и нам требуется построить криптосистему с секретным ключом. В такой криптосистеме имеется только один ключ - секретный, который известен и отправителю, и получателю шифрованного сообщения. Алгоритмы шифрования Ец и дешифро- дешифрования Dk оба зависят от этого секретного ключа К и таковы, что Dk(Ek(tti)) = т для любого открытого текста т. Ясно, что если кри- криптограмму d сообщения т вычислять как d = /(m), то противник, перехвативший d, может вычислить m лишь с пренебрежимо малой вероятностью. Но во-первых, непонятно, каким образом сможет вос- восстановить сообщение m из криптограммы законный получатель? Во- вторых, из того, что функция / односторонняя следует лишь, что про- противник не может вычислить все сообщение целиком. А это - весьма низкий уровень стойкости. Желательно, чтобы противник, знающий криптограмму d, не мог вычислить ни одного бита открытого тек- текста. На настоящий момент доказано, что существование односторонних функций является необходимым и достаточным условием для суще- существования стойких криптосистем с секретным ключом, а также стой- стойких криптографических протоколов нескольких типов, включая про- протоколы электронной подписи. С другой стороны, имеется результат 32 Глава 2 Импальяццо и Рудиха , который является достаточно сильным ар- аргументом в пользу того, что для некоторых типов криптографиче- криптографических схем (включая протоколы распределения ключей типа Диффи- Хеллмана) требуются более сильные предположения, чем предположе- предположение о существовании односторонних функций. К сожалению, этот ре- результат слишком сложный, чтобы его можно было разъяснить в насто- настоящей главе. 4. Псевдослучайные генераторы Существенный недостаток шифра Вернама состоит в том, что клю- ключи одноразовые. Можно ли избавиться от этого недостатка за счет не- некоторого снижения стойкости? Один из способов решения этой проб- проблемы состоит в следующем. Отправитель и получатель имеют общий секретный ключ К длины п и с помощью некоторого достаточно эффективного алгоритма д генерируют из него последовательность г - д(К) длины q(n), где q - некоторый полином. Такая криптоси- криптосистема (обозначим ее С г) позволяет шифровать сообщение m (или со- совокупность сообщений) длиной до q{n) битов по формуле d - г (В in, где © - поразрядное сложение битовых строк по модулю 2. Деши- Дешифрование выполняется по формуле т = d Ф г. Из результатов Шенно- Шеннона вытекает, что такая криптосистема не является абсолютно стой- стойкой, т. е. стойкой против любого противника (в чем, впрочем, не- нетрудно убедиться и непосредственно). Но что будет, если требуется защищаться только от полиномиально ограниченного противника, ко- который может атаковать криптосистему лишь с помощью полиномиаль- полиномиальных вероятностных алгоритмов? Каким условиям должны удовлетво- удовлетворять последовательность г и алгоритм д, чтобы криптосистема Сг бы- была стойкой? Поиски ответов на эти вопросы привели к появлению по- понятия псевдослучайного генератора, которое было введено Блюмом и Микали . Пусть д: {0,1}" -» {0,1}?"п" - функция, вычислимая за поли- полиномиальное (от п) время. Такая функция называется генератором. Интуитивно, генератор д является псевдослучайным, если порождае- порождаемые им последовательности неотличимы никаким полиномиальным ве- вероятностным алгоритмом от случайных последовательностей той же длины q(n). Формально этот объект определяется следующим обра- образом. Пусть А - полиномиальная вероятностная машина Тьюринга, ко- которая получает на входе двоичные строки длины q{n) и выдает в ре- результате своей работы один бит. Пусть Р,(А,п) = Рг{А(г) = 1|г ед {0, Криптография и теория сложности 33 Вероятность здесь определяется случайным выбором строки г и слу- случайными величинами, которые А использует в своей работе. Пусть Р2(А,п) = Pr{A(g(s)) = l|e ед {0,1}"}. Эта вероятность определяется случайным выбором строки s и случай- случайными величинами, которые А использует в своей работе. Подчеркнем, что функция д вычисляется детерминированным алгоритмом. Определение 2. Генератор д называется криптографически стой- стойким псевдослучайным генератором, если для любой полиномиальной вероятностной машины Тьюринга А, для любого полинома р и всех до- достаточно больших п \Р,(А,п)-Р2(А,п)\<1/р(п). Всюду ниже мы для краткости будем называть криптографически стойкие псевдослучайные генераторы просто псевдослучайными гене- генераторами. Такое сокращение является общепринятым в криптографи- криптографической литературе. Нетрудно убедиться, что для существования псевдослучайных гене- генераторов необходимо существование односторонних функций. В самом деле, сама функция g должна быть односторонней. Доказательство это- этого простого факта мы оставляем читателю в качестве упражнения. Вопрос о том, является ли существование односторонних функций од- одновременно и достаточным условием, долгое время оставался откры- открытым. В 1982 г. Яо построил псевдослучайный генератор, исходя из предположения о существовании односторонних перестановок, т. е. сохраняющих длину взаимнооднозначных односторонних функций. За этим последовала серия работ, в которых достаточное условие все более и более ослаблялось, пока наконец в 1989-1990 гг. Импальяццо, Левин и Луби и Хостад не получили следующий окончательный резуль- результат. Теорема 1. Псевдослучайные генераторы существуют тогда и толь- только тогда, когда существуют односторонние функции. Псевдослучайные генераторы находят применение не только в крип- криптографии, но и в теории сложности, и в других областях дискретной математики. Обсуждение этих приложений выходит за рамки настоя- настоящей главы. Здесь же в качестве иллюстрации мы рассмотрим описан- описанную в начале данного раздела криптосистему Сг, использующую псев- псевдослучайный генератор в качестве алгоритма д. Прежде всего, нам необходимо дать определение стойкости криптосистемы с секретным ключом. Пусть Ец - алгоритм шифрования криптосистемы с секретным ключом. Обозначим результат его работы d = Ек(т), здесь К - се- секретный ключ длиной п битов, am - открытый текст длиной q(n) 34 Глава 2 битов. Через т* обозначается г-ый бит открытого текста. Пусть А - полиномиальная вероятностная машина Тьюринга, которая получает на вход криптограмму d и выдает пару (г,сг), где г б {1,.. .,q(n)}, а б {0,1}. Интуитивно, криптосистема является стойкой, если ника- никакая машина Тьюринга А не может вычислить ни один бит открытого текста с вероятностью успеха, существенно большей, чем при простом угадывании. Определение 3. Криптосистема называется стойкой, если для лю- любой полиномиальной вероятностной машины Тьюринга А, для любого полинома р и всех достаточно больших п Pr{A(d) = (г,а)ка = пц\Кен {0,1}", т 6д {0,1}*<п)} < J + ~. 2 р(п) Эта вероятность (всюду ниже для краткости мы ее обозначаем про- просто Рг) определяется случайным выбором секретного ключа К, слу- случайным выбором открытого текста т из множества всех двоичных строк длины q(n) и случайными величинами, которые А использует в своей работе. Покажем, что криптосистема Сг с псевдослучайным генератором в качестве д является стойкой в смысле данного определения. Предполо- Предположим противное, т. е. что существуют полиномиальный вероятностный алгоритм А и полином р такие, что Рг ^ 1/2 + 1/р(п) для бесконечно многих п. Рассмотрим алгоритм В, который получает на входе двоич- двоичную строку г длины 0, q - из множества всех таких простых делителей числа р - 1, д - из множества всех чисел д таких, что д9 = 1 mod р, а х € Zg. Тогда функция f(x,p,q,g) = (gx mod p, p, q, д) - односторонняя (см. главу 2). Рекомен
Книги. Скачать книги DJVU, PDF бесплатно. Бесплатная электронная библиотека
В.В. Ященко, Введение в криптографию
Вы можете (программа отметит желтым цветом)
Вы можете посмотреть список книг по высшей математике с сортировкой по алфавиту.
Вы можете посмотреть список книг по высшей физике с сортировкой по алфавиту.
Бесплатно скачать книгу
, объем 1.69 Мб, формат.djvu
Издание второе под ред. Ященко В.В., сентябрь 1999 года
Уважаемые дамы и господа!! Для того, чтобы без "глюков" скачать файлы электронных публикаций, нажмите на подчеркнутую ссылку с файлом ПРАВОЙ кнопкой мыши , выберите команду "Save target as ..." ("Сохранить объект как..." ) и сохраните файл электронной публикации на локальный компьютер. Электронные публикации обычно представлены в форматах Adobe PDF и DJVU.
Глава 1. Основные понятия криптографии
1. Введение
2. Предмет криптографии
3. Математические основы
4. Новые направления
5. Заключение
Глава 2. Криптография и теория сложности
1. Введение
2. Криптография и гипотеза
3. Односторонние функции
4. Псевдослучайные генераторы
5. Доказательства с нулевым разглашением
Глава 3. Криптографические протоколы
1. Введение
2. Целостность. Протоколы аутентификации и электронной подписи
3. Неотслеживаемость. Электронные деньги
4. Протоколы типа "подбрасывание монеты по телефону"
5. Еще раз о разделении секрета
6. Поиграем в "кубнки". Протоколы голосования
7. За пределами стандартных предположений. Конфиденциальная передача сообщений
8. Вместо заключения
Глава 4. Алгоритмические проблемы теории чисел
1. Введение
2. Система шифрования RSA
3. Сложность теоретико-числовых алгоритмов
4. Как отличить составное число от простого
5. Как строить большие простые числа
6. Как проверить большое число на простоту
7. Как раскладывают составные числа на множители
8. Дискретное логарифмирование
9. Заключение
Глава 5. Математика разделения секрета
1. Введение
2. Разделение секрета для произвольных структур доступа
3. Линейное разделение секрета
4. Идеальное разделение секрета и матроиды
Глава 6. Компьютер и криптография
1. Вместо введения
2. Немного теории
3. Как зашифровать файл?
4. Поучимся на чужих ошибках
5. Вместо заключения
Глава 7. Олимпиады по криптографии для школьников
1. Введение
2. Шифры замены
3. Шифры перестановки
4. Многоалфавитные шифры замены с периодическим ключом
5. Условия задач олимпиад по математике и криптографии
6. Указания и решения
Приложение: отрывок из статьи К. Шеннона "Теория связи в секретных системах"
Краткая аннотация книги
Под общ. ред. В.В.Ященко. Авторский коллектив: В. В. Ященко (редактор, глава 1), Н. П. Варновский (главы 2, 3), Ю. В. Нестеренко (глава 4), Г. А. Кабатянский (глава 5), П. Н. Девянин, В. Г. Проскурин, А. В. Черемушкин (глава 6), П. А. Гырдымов, А. Ю. Зубов, А. В. Зязин, В. Н. Овчинников (глава 7).
В книге впервые на русском языке дается систематическое изложение научных основ криптографии от простейших примеров и основных понятий до современных криптографических конструкций. Понимание принципов криптографии стало для многих потребностью в связи с широким распространением криптографических средств обеспечения информационной безопасности. Поэтому книга может быть полезна массовому читателю. Книга рассчитана на студентов-математиков и специалистов по информационной безопасности.
Криптография - наука о шифрах - долгое время была засекречена, так как применялась, в основном, для защиты государственных и военных секретов. В настоящее время методы и средства криптографии используются для обеспечения информационной безопасности не только государства, но и частных лиц, и организаций. Дело здесь совсем не обязательно в секретах. Слишком много различных сведений "гуляет" по всему свету в цифровом виде. И над этими сведениями "висят" угрозы недружественного ознакомления, накопления, подмены, фальсификации и т. п. Наиболее надежные методы защиты от таких угроз дает именно криптография.
Пока криптографические алгоритмы для рядового потребителя - тайна за семью печатями, хотя многим уже приходилось пользоваться некоторыми криптографическими средствами: шифрование электронной почты, интеллектуальные банковские карточки и др. Естественно, что при этом основной вопрос для пользователя - обеспечивает ли данное криптографическое средство надежную защиту. Но даже правильно Сформулировать этот элементарный вопрос непросто. От какого противника защищаемся? Какие возможности у этого противника? Какие цели он может преследовать? Как измерять надежность защиты? Список таких вопросов можно продолжить. Для ответа на них пользователю необходимы знания основных понятий криптографии.
Популярное изложение научных основ криптографии (речь идет только о "негосударственной" криптографии; разделы криптографии, связанные с государственной безопасностью, должны оставаться секретными) - цель настоящей книги. Ее можно использовать и в качестве учебного пособия. На русском языке аналогичных книг пока нет. Материалы ряда глав публиковались авторами ранее в других изданиях (глава 1 - в книге С. А. Дориченко, В. В. Ященко, "25 этюдов о шифрах", М.: ТЕИС, 1994; главы 1,2,4,5 - в журнале "Математическое просвещение", третья серия, выпуск 2, М.: МЦНМО, 1998; глава 7 - в газете "Информатика" (еженедельное приложение к газете "Первое сентября"), N 4, январь 1998). При подготовке настоящего издания эти материалы были переработаны и дополнены. Изложение материала рассчитано на читателя с математическим складом ума.
В основном главы не зависят друг от друга (это достигнуто за счет некоторых повторов) и их можно читать в произвольном порядке. Главу 1 - вводную - рекомендуется прочитать всем, поскольку в ней на популярном уровне разъясняются все основные понятия современной криптографии: шифр, ключ, стойкость, электронная цифровая подпись, криптографический протокол и др. В других главах часть материала повторяется, но уже более углубленно. В главах 2, 3, 4, 5 используются некоторые сведения из высшей математики, известные ученикам математических классов и студентам. Глава 6 ориентирована на знатоков компьютерных технологий. Глава 7 содержит материалы олимпиад по криптографии для школьников и поэтому для ее чтения никаких знаний, выходящих за пределы школьной программы, не требуется.
Предупреждение: криптографические средства и программные продукты, упоминаемые в книге, используются только для иллюстрации общих криптографических идей; авторы не ставили своей целью давать оценки или сравнивать имеющиеся на рынке криптографические средства.
Криптография была поставлена на научную основу во многом благодаря работам выдающегося американского ученого Клода Шеннона. Его доклад "Математическая теория криптографии" был подготовлен в секретном варианте в 1945 г., рассекречен и опубликован в 1948 г., переведен на русский язык в 1963 г. Поскольку "Работы по теории информации и кибернетике" (1963 г.) К. Шеннона стали библиографической редкостью, мы включили в приложение основную часть статьи К. Шеннона "Теория связи в секретных системах". Эту основополагающую работу рекомендуется прочитать всем интересующимся криптографией.
Для профессионального понимания криптографических алгоритмов и умения оценивать их сильные и слабые стороны необходима уже серьезная математическая подготовка (на уровне математических факультетов университетов). Это объясняется тем, что современная криптография основана на глубоких результатах таких разделов математики, как теория сложности вычислений, теория чисел, алгебра, теория информации и др. Желающим серьезно изучать криптографию можно порекомендовать обзорную монографию "Криптография в банковском деле" Анохина М. И., Варновского Н. П., Сидельникова В. М., Ященко В. В., М.: МИФИ, 1997.
Как передать нужную информацию нужному адресату в тайне от других? Каждый из читателей в разное время и с разными целями наверняка пытался решить для себя эту практическую задачу (для удобства дальнейших ссылок назовем ее "задача ТП", т. е. задача Тайной Передачи). Выбрав подходящее решение, он, скорее всего, повторил изобретение одного из способов скрытой передачи информации, которым уже не одна тысяча лет.
Размышляя над задачей ТП, нетрудно прийти к выводу, что есть три возможности.
1. Создать абсолютно надежный, недоступный для других канал
связи между абонентами.
2. Использовать общедоступный канал связи, но скрыть сам факт передачи информации.
3. Использовать общедоступный канал связи, но передавать по нему нужную информацию в так преобразованном виде, чтобы восстановить
ее мог только адресат.
Прокомментируем эти три возможности.
1. При современном уровне развития науки и техники сделать такой
канал связи между удаленными абонентами для неоднократной передачи больших объемов информации практически нереально.
2. Разработкой средств и методов скрытия факта передачи сообщения занимается стеганография.
Первые следы стеганографических методов теряются в глубокой древности. Например, известен такой способ скрытия письменного сообщения: голову раба брили, на коже головы писали сообщение и после отрастания волос раба отправляли к адресату. Из детективных произведений хорошо известны различные способы тайнописи между строк обычного, незащищаемого текста: от молока до сложных химических реактивов с последующей обработкой.
Также из детективов известен метод "микроточки": сообщение записывается с помощью современной техники на очень маленький носитель (микроточку), который пересылается с обычным письмом, например, под маркой или где-нибудь в другом, заранее обусловленном месте.
В настоящее время в связи с широким распространением компьютеров известно много тонких методов "запрятывания" защищаемой информации внутри больших объемов информации, хранящейся в компьютере. Наглядный пример эапрятывания текстового файла в графический можно найти в Интернете; он же приведен в журнале "Компьютерра", N48 (225) от 1 декабря 1997 г., на стр. 62. (Следует отметить, что авторы статьи в журнале ошибочно относят стеганографию к криптографии. Конечно, с помощью стеганографии можно прятать и предварительно зашифрованные тексты, но, вообще говоря, стеганография и криптография - принципиально различные направления в теории и практике зашиты информации.)
3. Разработкой методов преобразования (шифрования) информации с целью ее защиты от незаконных пользователей занимается криптография. Такие методы и способы преобразования информации называются шифрами.
Шифрование (зашифрование) - процесс применения шифра к защищаемой информации, т. е. преобразование защищаемой информации (открытого текста) в шифрованное сообщение (шифртекст, криптограмму) с помощью определенных правил, содержащихся в шифре.
Дешифрование - процесс, обратный шифрованию, т. е. преобразование шифрованного сообщения в защищаемую информацию с помощью определенных правил, содержащихся в шифре.
Криптография - прикладная наука, она использует самые последние достижения фундаментальных наук и, в первую очередь, математики. С другой стороны, все конкретные задачи криптографии существенно зависят от уровня развития техники и технологии, от применяемых средств связи и способов передачи информации.
Предмет криптографии. Что же является предметом криптографии? Для ответа на этот вопрос вернемся к задаче ТП, чтобы уточнить ситуацию и используемые понятия. Прежде всего заметим, что эта задача возникает только для информации, которая нуждается в защите. Обычно в таких случаях говорят, что информация содержит тайну или является защищаемой, приватной, конфиденциальной, секретной. Для наиболее типичных, часто встречающихся ситуаций такого типа введены даже специальные понятия:
- государственная тайна;
- военная тайна;
- коммерческая тайна;
- юридическая тайна;
- врачебная тайна и т. д.
Далее мы будем говорить о защищаемой информации, имея в виду следующие признаки такой информации:
- имеется какой-то определенный круг законных пользователей, ко
торые имеют право владеть этой информацией;
- имеются незаконные пользователи, которые стремятся овладеть этой информацией с тем, чтобы обратить ее себе во благо, а законным пользователям во вред.
Книги, книги скачать, скачать книгу, книги онлайн, читать онлайн, скачать книги бесплатно, читать книги, читать книги онлайн, читать, библиотека онлайн, книги читать, читать онлайн бесплатно, читать книги бесплатно, электронная книга, читать онлайн книги, лучшие книги математика и физика, интересные книги математика и физика, электронные книги, книги бесплатно, книги бесплатно скачать, скачать бесплатно книги математика и физика, скачать книги бесплатно полностью, онлайн библиотека, книги скачать бесплатно, читать книги онлайн бесплатно без регистрации математика и физика, читать книги онлайн бесплатно математика и физика, электронная библиотека математика и физика, книги читать онлайн математика и физика, мир книг математика и физика, читать бесплатно математика и физика, библиотека онлайн математика и физика, чтение книг математика и физика, книги онлайн бесплатно математика и физика, популярные книги математика и физика, библиотека бесплатных книг математика и физика, скачать электронную книгу математика и физика, бесплатная библиотека онлайн математика и физика, электронные книги скачать, учебники онлайн математика и физика, библиотека электронных книг математика и физика, электронные книги скачать бесплатно без регистрации математика и физика, хорошие книги математика и физика, скачать книги полностью математика и физика, электронная библиотека читать бесплатно математика и физика, электронная библиотека скачать бесплатно математика и физика, сайты для скачивания книг математика и физика, умные книги математика и физика, поиск книг математика и физика, скачать электронные книги бесплатно математика и физика, электронная книга скачать математика и физика, самые лучшие книги математика и физика, электронная библиотека бесплатно математика и физика, читать онлайн бесплатно книги математика и физика, сайт книг математика и физика, библиотека электронная, онлайн книги читать, книга электронная математика и физика, сайт для скачивания книг бесплатно и без регистрации, бесплатная онлайн библиотека математика и физика, где бесплатно скачать книги математика и физика, читать книги бесплатно и без регистрации математика и физика, учебники скачать математика и физика, скачать бесплатно электронные книги математика и физика, скачать бесплатно книги полностью, библиотека онлайн бесплатно, лучшие электронные книги математика и физика, онлайн библиотека книг математика и физика, скачать электронные книги бесплатно без регистрации, библиотека онлайн скачать бесплатно, где скачать бесплатно книги, электронные библиотеки бесплатные, электронные книги бесплатно, бесплатные электронные библиотеки, онлайн библиотека бесплатно, бесплатно читать книги, книги онлайн бесплатно читать, читать бесплатно онлайн, интересные книги читать онлайн математика и физика, чтение книг онлайн математика и физика, электронная библиотека онлайн математика и физика, бесплатная библиотека электронных книг математика и физика, библиотека онлайн читать, читать бесплатно и без регистрации математика и физика, найти книгу математика и физика, каталог книг математика и физика, скачать книги онлайн бесплатно математика и физика, интернет библиотека математика и физика, скачать бесплатно книги без регистрации математика и физика, где можно скачать книги бесплатно математика и физика, где можно скачать книги, сайты для бесплатного скачивания книг, онлайн читать, библиотека читать, книги читать онлайн бесплатно без регистрации, книги библиотека, бесплатная библиотека онлайн, онлайн библиотека читать бесплатно, книги читать бесплатно и без регистрации, электронная библиотека скачать книги бесплатно, онлайн читать бесплатно.
,
С 2017 года возобновляем мобильную версию веб-сайта для мобильных телефонов (сокращенный текстовый дизайн, технология WAP) - верхняя кнопка в левом верхнем углу веб-страницы. Если у Вас нет доступа в Интернет через персональный компьютер или интернет-терминал, Вы можете воспользоваться Вашим мобильным телефоном для посещения нашего веб-сайта (сокращенный дизайн) и при необходимости сохранить данные с веб-сайта в память Вашего мобильного телефона. Сохраняйте книги и статьи на Ваш мобильный телефон (мобильный интернет) и скачивайте их с Вашего телефона на компьютер. Удобное скачивание книг через мобильный телефон (в память телефона) и на Ваш компьютер через мобильный интерфейс. Быстрый Интернет без излишних тэгов, бесплатно (по цене услуг Интернет) и без паролей. Материал приведен для ознакомления. Прямые ссылки на файлы книг и статей на веб-сайте и их продажи третьими лицами запрещены.
Примечание. Удобная текстовая ссылка для форумов, блогов, цитирования материалов веб-сайта, код html можно скопировать и просто вставить в Ваши веб-страницы при цитировании материалов нашего веб-сайта. Материал приведен для ознакомления. Сохраняйте также книги на Ваш мобильный телефон через сеть Интернет (есть мобильная версия сайта - ссылка вверху слева страницы) и скачивайте их с Вашего телефона на компьютер. Прямые ссылки на файлы книг запрещены.
В книге впервые на русском языке дается систематическое изложение научных основ криптографии от простейших примеров и основных понятий до современных криптографических конструкций. Понимание принципов криптографии стало для многих потребностью в связи с широким распространением криптографических средств обеспечения информационной безопасности. Поэтому книга может быть полезна массовому читателю.
Книга рассчитана на студентов-математиков и специалистов по информационной безопасности.
Предмет криптографии.
Что же является предметом криптографии? Для ответа на этот вопрос вернемся к задаче ТП, чтобы уточнить ситуацию и используемые понятия.
Прежде всего заметим, что эта задача возникает только для информации, которая нуждается в защите. Обычно в таких случаях говорят, что информация содержит тайну или является защищаемой, приватной, конфиденциальной, секретной. Для наиболее типичных, часто встречающихся ситуаций такого типа введены даже специальные понятия:
- государственная тайна;
- военная тайна;
- коммерческая тайна;
- юридическая тайна;
- врачебная тайна и т. д.
Далее мы будем говорить о защищаемой информации, имея в виду следующие признаки такой информации:
- имеется какой-то определенный круг законных пользователей, которые имеют право владеть этой информацией;
- имеются незаконные пользователи, которые стремятся овладеть этой информацией с тем. чтобы обратить ее себе во благо, а законным пользователям во вред.
Для простоты мы вначале ограничимся рассмотрением только одной угрозы - угрозы разглашения информации. Существуют и другие угрозы для защищаемой информации со стороны незаконных пользователей: подмена, имитация и др. О них мы поговорим ниже.
Оглавление
Предисловия
Глава 1. Основные понятия криптографии
§1. Введение
§2. Предмет криптографии
§3. Математические основы
§4. Новые направления
§5. Заключение
Глава 2. Криптография и теория сложности
§1. Введение
§2. Криптография и гипотеза Р = NP
§3. Односторонние функции
§4. Псевдослучайные генераторы
§5. Доказательства с нулевым разглашением
Глава 3. Криптографические протоколы
§1. Введение
§2. Целостность. Протоколы аутентификации и электронной подписи
§3. Неотслеживаемость. Электронные деньги
§4. Протоколы типа «подбрасывание монеты по телефону»
§5. Еще раз о разделении секрета
§6. Поиграем в «кубики». Протоколы голосования
§7. За пределами стандартных предположений. Конфиденциальная передача сообщений
§8. Вместо заключения
Глава 4. Алгоритмические проблемы теории чисел
§1. Введение
§2. Система шифрования RSA
§3. Сложность теоретико-числовых алгоритмов
§4. Как отличить составное число от простого
§5. Как строить большие простые числа
§6. Как проверить большое число на простоту
§7. Как раскладывают составные числа на множители
§8. Дискретное логарифмирование
§9. Заключение
Глава 5. Математика разделения секрета
§1. Введение
§2. Разделение секрета для произвольных структур доступа
§3. Линейное разделение секрета
§4. Идеальное разделение секрета и матроиды
Глава 6. Компьютер и криптография
§1. Вместо введения
§2. Немного теории
§3. Как зашифровать файл?
§4. Поучимся на чужих ошибках
§5. Вместо заключения
Глава 7. Олимпиады по криптографии для школьников
§1. Введение
§2. Шифры замены
§3. Шифры перестановки
§4. Многоалфавитные шифры замены с периодическим ключом
§5. Условия задач олимпиад по математике и криптографии
§6. Указания и решения
Приложение А. Отрывок из статьи К. Шеннона «Теория связи в секретных системах»
Приложение Б. Аннотированный список рекомендованной литературы
Приложение В. Словарь криптографических терминов
Алфавитный указатель русскоязычных терминов
Алфавитный указатель англоязычных терминов.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Введение в криптографию, Ященко В.В., 2012 - fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.