А.Конан Дойл, ``Пляшущие человечки''
В этом рассказе Холмсу необходимо было прочитать тексты пяти записок:
I.
II.
III.
IV.
V.
Первая записка была так коротка, что дала возможность Холмсу сделать всего лишь одно правдоподобное предположение, оказавшееся впоследствии правильным. По-видимому, флаги употребляются лишь для того, чтобы отмечать концы отдельных слов. Больше ничего по первой записке установить было нельзя. Четвертая записка, по всей видимости, содержала всего одно слово, так как в ней не было флагов.
Вторая и третья записки начинались, несомненно, с одного и того же слова из четырех букв. Вот это слово:
Оно кончается той же буквой, какой и начинается. Счастливая мысль: письма обычно начинаются с имени того, кому письмо адресовано. Человек, писавший миссис Кьюбит эти послания, был, безусловно, близко с ней знаком. Вполне естественно, что он называет ее просто по имени. А зовут ее Илси. Таким образом, Холмсу стали известны три буквы: И, Л и С.
В двух записках их автор обращается к миссис Кьюбит по имени и, видимо, чего-то требует от нее. Не хочет ли он, чтобы она пришла куда-нибудь, где он мог с ней поговорить? Холмс обратился ко второму слову третьей записки. В нем 7 букв, из которых третья и последняя - И. Холмс предположил, что слово это - ПРИХОДИ, и сразу оказался обладателем еще 5 букв: П, Р, Х, О, Д.
Тогда он обратился к четвертой записи, которая появилась на двери сарая. Холмс предположил, что она является ответом и что написала ее миссис Кьюбит. Подставив в текст уже известные буквы, он получил: -И-О-Д-. Что же могла миссис Кьюбит ответить на просьбу прийти? Внезапно Холмс догадался: НИКОГДА
Возвратившись к первой записке, Холмс получил:
- -Д-С- А- СЛ-НИ
Он предположил, что четвертое слово - СЛЕНИ Это - фамилия, чрезвычайно распространенная в Америке. Коротенькое слово из двух букв, стоящее перед фамилией, по всей вероятности, имя. Какое же имя может состоять из двух букв? В Америке весьма распространено имя Аб. Теперь остается установить только первое слово фразы; оно состоит всего из одной буквы, и отгадать его нетрудно: это - местоимение Я.
Далее Холмс восстанавливает содержание второй записки:
Здесь указаны границы слов, а снизу одинаковыми символами отмечены одинаковые буквы. Четвертое слово состоит из одной буквы (по-видимому, это союз или предлог). Буквы О и И уже определены, С, А и К - тоже. Остаются следующие возможности: это - либо В, либо У. Вряд ли это - В, так как в этом случае получилось бы ``нечитаемое'' третье слово -И-В. Поэтому, скорее всего - это предлог У. Небольшой перебор незадействованных букв дает правдоподобную гипотезу о значении третьего слова: ЖИВУ. Скорее всего, последнее слово (-ЛРИДЖА) - мужское имя, в котором неизвестная буква - Э. Поэтому вторая записка гласит: ИЛСИ Я ЖИВУ У ЭЛРИДЖА
Холмс послал телеграмму в нью-йоркское полицейское управление с запросом о том, кто такой Аб Слени. Поступил ответ: ``Самый опасный бандит в Чикаго''.
Сразу после этого появилась последняя (5-я) записка, в которой не хватало трех букв: ИЛСИ ГО-ОВЬСЯ К С-ЕР-И, из которой сразу определяются буквы М и Т:
ИЛСИ ГОТОВЬСЯ К СМЕРТИ
Шестая записка была направлена Холмсом преступнику:
Next: Э. По, ``Золотой жук''
Up: 7.2. Шифры замены
Previous: 7.2. Шифры замены
Contents:
А можно ли обойтись без пароля?
Как видите, применять пароль в качестве ключа шифрования не так удобно, как кажется на первый взгляд. Либо защита будет нестойкой, либо пароль трудно запомнить и ввести без ошибок. Если вы хотите построить по-настоящему надежную защиту, вместо пароля нужно использовать что-то другое.
Можно, например, хранить ключ на дискете1). Вы создаете каким-то образом (каким - обсудим позже) случайный, равновероятный и достаточно длинный ключ и записываете его на дискету. Когда программа шифрования запрашивает ключ, вы вводите ключ не с клавиатуры, а с дискеты. Вы просто вставляете дискету в дисковод, а программа считывает оттуда ключ и зашифровывает файл на этом ключе. При расшифровании файла программа просит ``Вставьте ключевую дискету в дисковод''. Вы вставляете дискету в дисковод, программа считывает оттуда ключ, проверяет его правильность и, если ключ правильный, расшифровывает файл.
Конечно, программа шифрования должна уметь работать с ключевыми дискетами.
Ключевую дискету нужно хранить в месте, недоступном для злоумышленников. Если кто-то воспользуется вашей ключевой дискетой, то он сможет прочесть все, что вы зашифровали с ее помощью. Не теряйте ключевые дискеты! Если вы потеряете такую дискету, то тем самым вы потеряете все данные, которые вы зашифровали с ее помощью.
Удобно ли пользоваться ключевыми дискетами? Нет. Но за надежность защиты приходится платить. Вообще, это общая закономерность - чем надежнее система защиты, тем труднее с ней работать. И наоборот, чем система защиты удобнее в обращении, тем она слабее. Конечно, разрабатывая систему защиты, можно наделать ошибок, и система получится и ненадежной, и неудобной. Но если система разрабатывалась на совесть, приведенное выше утверждение почти всегда верно.
Можно ли как-нибудь защитить ключ, хранящийся на дискете? Конечно! Его тоже можно зашифровать. И не нужно для этого придумывать сложный шифр - вполне хватит самого примитивного . Почему? Да потому, что ключ шифрования - текст случайный и равновероятный. На чем основан метод дешифрования шифра простой замены? На том, что открытый текст - это осмысленный текст. А в осмысленном тексте обязательно присутствуют статистические закономерности. Но в ключе никаких закономерностей нет - ключ случаен и равновероятен!
Что использовать в качестве ключа, на котором шифруется ключ? Можно использовать пароль, но, как вы уже знаете, это не очень надежно. Можно завести вторую ключевую дискету, на которой хранить ключ, необходимый для доступа к первой. Но тогда придется заводить третью дискету, чтобы защитить вторую, а потом заводить четвертую, чтобы защитить третью ...
Так как же быть? Подумайте сами. Один из возможных
вы найдете в конце главы.
Next: Где взять ключи?
Up: 6.3. Как зашифровать файл?
Previous: Какой должен быть пароль?
Contents:
Алгебра секретных систем
Если имеются две секретные системы и , их часто можно комбинировать различными способами для получения новой секретной системы . Если и имеют одну и ту же область (пространство сообщений), то можно образовать своего рода ``взвешенную сумму''
где . Эта операция состоит, во-первых, из предварительного выбора систем или с вероятностями и . Этот выбор является частью ключа . После того как этот выбор сделан, системы или применяются в соответствии с их определениями. Полный ключ должен указывать, какая из систем или выбрана и с каким ключом используется выбранная система.
Если состоит из отображений с вероятностями , а -- из с вероятностями , то система состоит из отображений с вероятностями соответственно.
Обобщая далее, можно образовать сумму нескольких систем
Заметим, что любая система может быть записана как сумма фиксированных операций
где -- определенная операция шифрования в системе , соответствующая выбору ключа , причем вероятность такого выбора равна .
Второй способ комбинирования двух секретных систем заключается в образовании ``произведения'', как показано схематически на рис. . Предположим, что и -- такие две системы, что область определения (пространство языка) системы может быть отождествлена с областью определения (пространством криптограмм) системы . Тогда можно применить сначала систему к нашему языку, а затем систему к результату этой операции, что дает результирующую операцию , которую запишем в виде произведения
Ключ системы состоит как из ключа системы , так и из ключа системы , причем предполагается, что эти ключи выбираются соответственно их первоначальным вероятностям и независимо.
Таким образом, если ключей системы выбирается с вероятностями
а ключей системы имеют вероятности
то система имеет самое большее ключей с вероятностями . Во многих случаях некоторые из отображений будут одинаковыми и могут быть сгруппированы вместе, а их вероятности при этом сложатся.
Произведение шифров используется часто; например, после подстановки применяют транспозицию или после транспозиции -- код Виженера; или же применяют код к тексту и зашифровывают результат с помощью подстановки, транспозиции, дробным шифром и т.д.
Можно заметить, что такое умножение, вообще говоря, некоммутативно (т. е. не всегда ), хотя в частных случаях (таких, как подстановка и транспозиция) коммутативность имеет место. Так как наше умножение представляет собой некоторую операцию, оно по определению ассоциативно, т. е. . Кроме того, верны законы
(взвешенный ассоциативный закон для сложения);
(право- и левосторонние дистрибутивные законы), а также справедливо равенство
Следует подчеркнуть, что эти операции комбинирования сложения и умножения применяются к секретным системам в целом. Произведение двух систем не следует смешивать с произведением отображений в системах , которое также часто используется в настоящей работе. Первое является секретной системой, т.е. множеством отображений с соответствующими вероятностями; второе -- является фиксированным отображением. Далее, в то время как сумма двух систем является системой, сумма двух отображений не определена. Системы и могут коммутировать, в то время как конкретные и не коммутируют. Например, если -- система Бофора данного периода, все ключи которой равновероятны, то, вообще говоря,
но, конечно, произведение не зависит от порядка сомножителей; действительно
является системой Виженера того же самого периода со случайным ключом. С другой стороны, если отдельные отображения и двух систем и коммутируют, то и системы коммутируют.
Системы, у которых пространства и можно отождествить (этот случай является очень частым, если последовательности букв преобразуются в последовательности букв), могут быть названы эндоморфными. Эндоморфная система может быть возведена в степень .
Секретная система , произведение которой на саму себя равно , т.е. такая, что
будет называться идемпотентной. Например, простая подстановка, транспозиция с периодом , система Виженера с периодом (все с равновероятными ключами) являются идемпотентными.
Множество всех эндоморфных секретных систем, определенных в фиксированном пространстве сообщений, образует ``алгебраическую систему'', т.е. некоторый вид алгебры, использующей операции сложения и умножения. Действительно, рассмотренные свойства сложения и умножения можно резюмировать следующим образом.
Множество эндоморфных шифров с одним и тем же пространством сообщений и двумя операциями комбинирования -- операцией взвешенного сложения и операцией умножения -- образуют линейную ассоциативную алгебру с единицей, с той лишь особенностью, что коэффициенты во взвешенном сложении должны быть неотрицательными, а их сумма должна равняться единице.
Эти операции комбинирования дают способы конструирования многих новых типов секретных систем из определенных данных систем, как это было показано в приведенных примерах. Их можно также использовать для описания ситуации, с которой сталкивается шифровальщик противника, когда он пытается расшифровать криптограмму неизвестного типа. Фактически он расшифровывает секретную систему типа
где в данном случае -- известные типы шифров с их априорными вероятностями , а соответствует возможности использования совершенно нового неизвестного шифра.
Next: 7. Чистые и смешанные
Up: Часть I. МАТЕМАТИЧЕСКАЯ СТРУКТУРА СЕКРЕТНЫХ
Previous: 5. Оценка секретных систем
Contents:
Алгоритмические проблемы теории чисел
Next: 4.1. Введение
Up: Введение в криптографию
Previous: Литература к главе 3
Contents:
Целостность. Протоколы аутентификации и электронной подписи
``Волк и семеро козлят''. Русская народная сказка.
Как уже отмечалось во введении, понятие целостности информации, по-видимому, не допускает математической формализации. В данном разделе мы рассмотрим методы обеспечения целостности на примере двух наиболее важных и распространенных типов криптографических протоколов - схем аутентификации и электронной подписи.
Назначение и суть протоколов аутентификации (называемых также протоколами идентификации) легко понять на следующем примере. Представим себе информационную систему, которая работает в компьютерной сети и обеспечивает доступ к некоторым данным. У администратора системы имеется список всех ее пользователей вместе с сопоставленным каждому из них набором полномочий, на основе которых осуществляется разграничение доступа к ресурсам системы. Ресурсами могут быть, например, некоторые фрагменты информации, а также функции, выполняемые системой. Одним пользователям может быть разрешено читать одну часть информации, другим - другую ее часть, а третьим - еще и вносить в нее изменения. В данном контексте под обеспечением целостности понимается предотвращение доступа к системе лиц, не являющихся ее пользователями, а также предотвращение доступа пользователей к тем ресурсам, на которые у них нет полномочий. Наиболее распространенный метод разграничения доступа, парольная защита, имеет массу недостатков. Их обсуждение стало общим местом для текстов по компьютерной безопасности, поэтому мы сразу перейдем к криптографической постановке задачи.
В протоколе имеются два участника - Алиса, которая должна доказать свою аутентичность, и Боб, который эту аутентичность должен проверить. У Алисы имеются два ключа - общедоступный открытый и секретный . Фактически, Алисе нужно доказать, что она знает , и сделать это таким образом, чтобы это доказательство можно было проверить, зная только .
Задача аутентификации уже обсуждалась в главе . Там же были сформулированы основные требования, которым должен удовлетворять стойкий протокол аутентификации. Напомним, что для удовлетворения этих требований достаточно, чтобы протокол аутентификации был доказательством с нулевым разглашением. В главе приведен протокол доказательства с абсолютно нулевым разглашением для задачи ИЗОМОРФИЗМ ГРАФОВ. Но этот протокол имеет неприемлемо большое с практической точки зрения количество раундов обмена сообщениями между Алисой и Бобом.
Ниже мы приводим протокол Шнорра [], один из наиболее эффективных практических протоколов аутентификации. Для его описания нам потребуются некоторые обозначения, которые будут использоваться и в последующих разделах данной главы.
Пусть и - простые числа такие, что делит . Шнорр предлагает [] использовать длины порядка 512 битов и - длины порядка 140 битов. Пусть таково, что , . Пусть и . Задача вычисления значения по заданному значению при известных , и называется задачей дискретного логарифмирования (см. главу ). Для задачи дискретного логарифмирования на данный момент не известно эффективных алгоритмов. Поэтому в криптографии широко используется гипотеза о вычислительной трудности задачи дискретного логарифмирования. Сформулируем ее более строго. Пусть - растущий целочисленный параметр, число выбирается из множества всех простых чисел длины таких, что имеет простой делитель длины не меньше для некоторой константы 0$" width="41" height="28" >, - из множества всех таких простых делителей числа , - из множества всех чисел таких, что , а . Тогда функция - односторонняя (см. главу ). Рекомендации, данные Шнорром относительно длин чисел и , можно трактовать следующим образом. На тот момент (1989 г.) считалось практически невыполнимым уже для и длины порядка 512 и 140 битов соответственно. Здесь, однако, следует учитывать, что прогресс в области вычислительной техники и в алгоритмической теории чисел (см. главу ) может привести к необходимости пересмотра этих величин.
В качестве секретного ключа схемы аутентификации Алиса выбирает случайное число из . Далее Алиса вычисляет и публикует открытый ключ . Открытые ключи всех участников схемы должны публиковаться таким образом, чтобы исключалась возможность их подмены (такое хранилище ключей называется общедоступным сертифицированным справочником). Эта проблема, называемая часто проблемой аутентичности открытых ключей, составляет отдельный предмет исследований в криптографии и в данной главе не рассматривается.
Next: 3.3. Неотслеживаемость. Электронные деньги
Up: 3. Криптографические протоколы
Previous: 3.1. Введение
Contents:
ЧастьI. МАТЕМАТИЧЕСКАЯ СТРУКТУРА СЕКРЕТНЫХ СИСТЕМ
Next: 2. Секретные системы
Up: Приложение
Previous: 1. Введение и краткое
Contents:
ЧастьII. ТЕОРЕТИЧЕСКАЯ СЕКРЕТНОСТЬ
Next: 9. Введение
Up: Приложение
Previous: 8. Подобные системы
Contents:
Что надо знать перед написанием программы шифрования
С появлением персональных компьютеров криптография приобрела совершенно новое лицо. Хотя компьютеры привнесли немало нового и в криптографию, все же самое радикальное новшество заключается в том, что о криптографии стали говорить открыто и на каждом углу. Где есть компьютеры, там обязательно появляются вопросы о защите информации. А где начинают задумываться о защите информации - там неизбежно вспоминают о криптографии.
Криптография - очень таинственная и хитрая область знаний. Как правило, о ней можно было прочитать очень мало. Сейчас же ситуация изменилась, и о ней пишут много. Парадокс в том, что чем больше о ней пишут, тем меньше в ней понимаешь. Точнее, тем больше понимаешь, что ты в ней ничего не понимаешь.
Не секрет, что каждый, кто хоть немного поработал на компьютере, не раз задумывался о защите своих файлов. Неважно от кого. Просто каждый из нас не любит, когда в его делах кто-то копается. А при работе с персональным компьютером (ПК) постоянно возникает ситуация, когда он находится в безраздельной власти, в общем-то, посторонних вам людей. К соблазну попробовать зашифровать файлы, директории или диски постоянно подталкивают нас и многочисленные программы со встроенными функциями шифрования: нортоновский Diskreet, Secretdisk, различные архиваторы, редакторы и т.д. Поэтому без преувеличения можно сказать, что с криптографией сталкивался каждый пользователь ПК.
На более серьезном уровне приходится строить отношения с криптографией тем, кто имеет свое дело и использует ПК или локальную сеть ПК в своей организации или фирме. Здесь уже потери от небрежного обращения со своей информацией могут привести к непоправимым последствиям. Не будем утомлять читателя примерами из жизни, поскольку каждый наверняка читал об этом в газетах или слышал от друзей.
Дело не в примерах, а в сути дела. А суть в том, что без криптографии решить задачи сохранения ваших тайн практически невозможно. Не будем тратить время на доказательство этого тезиса. Интуитивно это понимают все, хотя у непрофессионалов и возникает иногда некоторое чувство внутреннего сопротивления.
Итак, вы поняли, что вам надо воспользоваться какой-либо программой для шифрования. И вот здесь-то сразу появляются непреодолимые трудности. То, что они непреодолимые, вы понимаете чуть позднее. Для того, чтобы выбрать для себя нужную программу, надо научиться оценивать ее качество и уметь сравнивать такие программы между собой. А вот здесь-то никаких критериев вам никто и никогда не расскажет, да и в книгах вы ничего путного не прочитаете. А верить продавцу с его навязчивой и крикливой рекламой в данном случае полностью абсурдно, так как продавцом может оказаться ваш конкурент со всеми вытекающими отсюда последствиями. Верить можно только той программе, которую вы написали сами. Если вы с этим не согласны, значит у вас еще все впереди. Ваши иллюзии еще не скоро рассеются.
Итак, приступим к написанию программы шифрования файлов. Поначалу создание такой программы кажется вполне доступной задачей, с которой может справиться любой человек, изучивший какой-нибудь язык программирования. Нет ничего проще. Вы выбираете самый надежный из известных вам алгоритм шифрования, например описанный в ГОСТ 28147, садитесь за компьютер, и через некоторое время у вас появляется работающая программа. Хотя она работает не очень быстро и интерфейс у нее не очень удобный, она вас вполне устраивает и вы ей полностью доверяете, поскольку это ваша программа.
Но со временем у вас опять появляется червь сомнения. Вы опять начинаете задумываться о надежности вашей защиты и понимаете, что, несмотря на свой богатый опыт в области криптографии, вы в сущности ничего в этом не понимаете. Единственное, что согревает душу в такой ситуации, так это то, что вы теперь ясно осознаете необходимость серьезного подхода к решению задачи. А это уже очень много. С этого момента и начинается ваша работа по освоению криптографии.
Next: Какой алгоритм выбрать?
Up: 6.2. Немного теории
Previous: 6.2. Немного теории
Contents:
Дискретное логарифмирование
Пусть - нечетное простое число. Еще Эйлер знал, что мультипликативная группа кольца циклична, т.е. существуют такие целые числа , что сравнение
|
(22) |
разрешимо относительно при любом , не делящемся на . Числа с этим свойством называются первообразными корнями, и количество их равно , где - функция Эйлера. Целое , удовлетворяющее сравнению (), называется индексом или дискретным логарифмом числа .
В разделе мы описали алгоритм, позволяющий по заданному числу достаточно быстро вычислять . Обратная же операция - вычисление по заданному его дискретного логарифма, вообще говоря, является очень сложной в вычислительном отношении задачей. Именно это свойство дискретного логарифма и используется в его многочисленных криптографических применениях (см. главу ). Наиболее быстрые (из известных) алгоритмы решения этой задачи, основанные на так называемом методе решета числового поля, требуют выполнения
арифметических операций (см. []), где - некоторая положительная постоянная. Это сравнимо со сложностью наиболее быстрых алгоритмов разложения чисел на множители. Конечно, указанная оценка сложности получена при условии справедливости ряда достаточно правдоподобных гипотез.
Говоря о сложности задачи дискретного логарифмирования, мы имели в виду ``общий случай''. Ведь и большое целое число легко может быть разложено на простые сомножители, если все эти сомножители не очень велики. Известен алгоритм, позволяющий быстро решать задачу дискретного логарифмирования, если есть произведение малых простых чисел.
Пусть - простое число, делящее . Обозначим
, тогда классы вычетов все различны и образуют полное множество решений уравнения в поле
. Если не велико и целое число удовлетворяет сравнению
, то показатель , , легко может быть найден, например, с помощью перебора. Именно на этом свойстве основан упомянутый выше алгоритм.
Допустим, что , . Алгоритм последовательно строит целые числа , , для которых выполняется сравнение
| (23) |
, то найдется целое число , для которого
. При таком выборе сравнение () с , очевидно, выполняется. Предположим, что найдено число , удовлетворяющее сравнению (). Тогда определим с помощью сравнения
| (24) |
| (25) |
При сравнение () означает в силу (), что
. Целое число есть первообразный корень по модулю , поэтому имеем
и
Если
, где все простые числа малы, то указанная процедура позволяет найти вычеты
, , и, с помощью китайской теоремы об остатках, вычет , т.е. решить сравнение ().
В случае обычных логарифмов в поле действительных чисел имеется специальное основание , позволяющее достаточно быстро вычислять логарифмы с произвольной точностью. Например, это можно делать с помощью быстро сходящегося ряда
| (26) |
| (27) |
Так как поле неполно, вычисление дискретных логарифмов не может использовать предельный переход и основано на иных принципах. Прежде всего, нужный дискретный логарифм вычисляется не сам по себе, а вместе с совокупностью логарифмов ряда других чисел. Заметим, что всякое сравнение вида
| (28) |
| (29) |
то
| (30) |
| (31) |
. Затем с помощью () можно найти .
Мы опишем ниже реализацию этой идеи, взятую из работы []. Эвристические соображения позволили авторам [] утверждать, что предложенный ими алгоритм требует , где
, арифметических операций для вычисления .
Положим
Тогда выполняется сравнение
| (32) |
при некотором 0$" width="41" height="28" >, то правая часть сравнения () не превосходит
. Можно доказать, что случайно выбранное натуральное число
, с вероятностью большей, чем .
Обозначим через совокупность всех простых чисел при
. Будем теперь перебирать случайным образом числа и для каждой такой пары пытаться разложить на множители соответствующее выражение из правой части (). Для разложения можно воспользоваться, например, делением на все простые числа, меньшие чем . Перебрав все
указанных пар , мы найдем, как это следует из указанных выше вероятностных соображений, не менее
| (33) |
Напомним, что число , согласно нашему предположению, существенно меньше, чем . Поэтому оно раскладывается в произведение простых чисел, входящих в множество
, и это приводит к сравнению ().
Заметим, что количество () найденных сравнений типа () превосходит число . Следовательно, построенная система неоднородных линейных сравнений относительно содержит сравнений больше, чем неизвестных. Конечно, множество ее решений может при этом быть бесконечным. Одна из правдоподобных гипотез состоит в том, что система все-таки имеет единственное решение, и, решив ее, можно определить дискретные логарифмы всех чисел . На этом завершается первый этап работы алгоритма из [].
Как было отмечено, каждое из чисел, стоящих в правой части сравнения (), не превосходит . Поэтому оно раскладывается в произведение не более простых сомножителей и, следовательно, каждое из сравнений () построенной системы содержит лишь отличных от нуля коэффициентов. Матрица системы сравнений будет разреженной, что позволяет применять для ее решения специальные методы с меньшей оценкой сложности, чем обычный гауссов метод исключения переменных.
Вместо перебора всех допустимых значений в [] предлагается использовать так называемое решето, отбрасывающее все пары этих чисел, для которых правая часть () заведомо не раскладывается в произведение малых простых сомножителей. Для каждого и каждой малой простой степени
Организованная правильным образом, эта процедура одновременно отбирает все нужные пары чисел и дает разложение на простые сомножители правых частей сравнений (32).
Итак, после первого этапа работы алгоритма в нашем распоряжении оказываются дискретные логарифмы всех чисел из множества . Второй этап алгоритма сводит поиск дискретного логарифма числа к поиску логарифмов некоторого множества чисел , не превосходящих по величине . Выбирая случайным образом число не более раз, можно, как показывают вероятностные соображения, найти такое , что вычет раскладывается в произведение простых чисел, меньших . Пусть
такое разложение, где - некоторые простые числа с условием арифметических операций. В результате вычисление дискретного логарифма числа сводится к вычислению дискретных логарифмов для чисел , среднего размера.
Наконец, на последнем этапе производится вычисление логарифмов всех чисел . Пусть - простое число из интервала
Для любых целых чисел
| (34) |
арифметических операций.
Существуют и другие способы построения соотношений (). В [] для этого используются вычисления в полях алгебраических чисел. В качестве множителей в соотношениях типа () используются не только простые числа, но и простые идеалы с небольшой нормой.
Задача вычисления дискретных логарифмов может рассматриваться также и в полях , состоящих из элементов, в мультипликативных группах классов вычетов , в группах точек эллиптических кривых и вообще в произвольных группах. С литературой по этому вопросу можно ознакомиться по работе [].
Next: 4.9. Заключение
Up: 4. Алгоритмические проблемы теории
Previous: 4.7. Как раскладывают составные
Contents:
Для чего компьютеру нужна криптография?
Пока компьютеры были большими, их обслуживали специально подготовленные инженеры-программисты, системщики, аппаратчики, информационщики, а также операторы и технический персонал. Доступ к хранящейся и обрабатываемой в них информации имел также ограниченный круг людей. Поэтому проблемы защиты информации в основном сводились к повышению надежности работы, дублированию критичной информации и организационным мерам. Позднее было осознано, что наряду с безопасностью данных огромную роль играет также безопасность программного обеспечения и аппаратных средств. Поэтому стали говорить о компьютерной безопасности. Наконец, с появлением автоматизированных систем обработки данных (представляющих собой неразрывное целое из объединенных в сеть компьютеров, средств телекоммуникаций, информационных технологий и распределенных информационных массивов) стали больше говорить об информационной безопасности системы в целом, понимая под этим состояние защищенности всех процессов обработки, хранения и передачи информации в системе.
Естественно, что криптография заняла в этой области подобающее ей место, предоставив массу алгоритмов для закрытия хранимой и передаваемой конфиденциальной информации. Как ни странно, но даже для информационных систем, обрабатывающих только открытую и общедоступную информацию, также не удалось обойтись без криптографических решений. Действительно, можно ли доверять полученным от такой системы данным, если они могут быть легко изменены, модифицированы или даже уничтожены кем-то из пользователей. Например, кому нужна информационная система с недостоверной информацией, или система принятия решений, работа которой основана на случайной или подтасованной информации? Именно криптография предоставляет незаменимый набор средств для обеспечения безопасности работы системы, такие как , , коды аутентификации сообщений и многое другое.
Вместе с тем, как это обычно бывает, при практической реализации даже самых хороших теоретических результатов возникают ``маленькие'' трудности. Чтобы получить представление о том, что это за трудности, проанализируем процесс создания программы для шифрования файлов.
Next: 6.2. Немного теории
Up: 6.1. Вместо введения
Previous: Для чего криптографии нужен
Contents:
Для чего криптографии нужен компьютер?
- одна из древнейших наук. О ней вспоминают всегда, когда возникает необходимость скрывать тайны. Но одним карандашом и бумагой пользоваться достаточно трудоемко и обременительно. И с древнейших времен человек пытается использовать различные орудия, позволяющие облегчить труд шифровальщика. После многовекового использования веревочек, жезлов, полосок, ленточек, планшетов, трафаретов, дисков и т.д. и т.п., криптография в начале ХХ века поставила себе на службу массу механических, пневматических, электрических, а затем и электронных устройств. В 40-х годах она придумала для своих нужд первые электронные вычислители. Появление компьютеров также поначалу было воспринято именно как появление мощнейшего помощника для людей, занимающихся разработкой и анализом алгоритмов шифрования. Кстати, первый компьютер с названием ``Colossus'', в создании которого участвовал математик А. Тьюринг, был разработан в Англии именно для решения задач дешифрования германской шифрмашины ``Enigma'' в самом начале Второй мировой войны. Но компьютеры не облегчили изнуряющий труд криптографа, а только привнесли массу новых проблем. Появились новые виды информации, требующей закрытия, новые области применения криптографических методов, а самое главное - существенно возросли возможности противника по раскрытию применявшихся ранее шифров.
Первые три десятилетия после своего появления компьютеры оправдывали свое название ``вычислитель'' и представляли собой инструмент для создания новых и взлома старых шифров.
В восьмидесятые годы произошла неизбежная переоценка ценностей. Из подсобного средства, вычислителя, компьютер стал центральным звеном для множества различных самостоятельных систем, выполняющих самые разнообразные функции. Это - информационные системы, системы связи и системы управления, системы автоматического проектирования, автоматизированные системы практически для всех областей человеческой деятельности, включая производственную, военную, финансовую, экономическую, медицинскую, и многие другие. Нетрудно догадаться, что и в области криптографии компьютер занял центральное место, взяв на себя большинство функций традиционной криптографической деятельности, включая реализацию криптографических алгоритмов, проверку их качества, генерацию и распределение ключей, автоматизацию работы по анализу перехвата и раскрытию шифров и т.д.
Наконец, сейчас, в конце девяностых годов в связи с появлением глобальных сетей, мы начинаем осознавать неизбежность вхождения в мировое информационное пространство, часто называемое киберпространством, которое стремительно развивается по своим законам, засасывая миллионы новых и новых обитателей. Проваливаясь в него, мы забываем о существовании времени и пространства, теряем грань между реальностью и вымыслом. Самые фантастические идеи находят в нем простое и естественное воплощение, действительное становится виртуальным, а виртуальное действительным. Универсальность, полная совместимость и взаимосвязанность удаленных друг от друга компьютеров позволяют, с одной стороны, реализовать принципиально новые криптографические идеи, а с другой, существенно расширить области применения криптографии.
Вместе с тем, восхищаясь возможностями компьютеров, не надо забывать о простых вещах. Как справедливо заметил американский математик Нил Коблиц - автор книги ``Курс по теории чисел и криптографии'', - выступая на семинаре в Московском университете, системы с открытыми ключами созданы для людей, которые очень сильно не доверяют друг другу, но при этом бесконечно доверяют своим компьютерам.
Next: Для чего компьютеру нужна
Up: 6.1. Вместо введения
Previous: 6.1. Вместо введения
Contents:
Доказательства с нулевым разглашением
Предположим, что Алиса знает доказательство некоторой теоремы и желает убедить Боба в том, что теорема верна. Конечно, Алиса может просто передать доказательство Бобу на проверку. Но тогда впоследствии Боб сможет сам, без помощи Алисы, доказывать третьим лицам эту теорему. А может ли Алиса убедить Боба так, чтобы он не получил при этом никакой информации, которая помогла бы ему восстановить доказательство теоремы? Этим двум, казалось бы взаимно исключающим требованиям, удовлетворяют протоколы доказательства с нулевым разглашением. Последнее понятие было введено Гольдвассер, Микали и Ракоффом в 1985 г. [].
Рассматривается следующая модель протокола. В распоряжении Алисы и Боба имеются вероятностные машины Тьюринга P
и V
соответственно. Вычислительные ресурсы, которые может использовать Алиса, неограничены, в то время как машина V
работает за полиномиальное время. Машины P и V имеют общую коммуникационную ленту для обмена сообщениями. После записи сообщения на коммуникационную ленту машина переходит в состояние ожидания и выходит из него, как только на ленту будет записано ответное сообщение. Машины P и V имеют также общую входную ленту, на которую записано входное слово . Утверждение, которое доказывает Алиса, суть ``'', где - некоторый фиксированный (известный и Алисе, и Бобу) язык. Чтобы избежать тривиальности, язык должен быть трудным (например, NP-полным), иначе Боб сможет самостоятельно проверить, что . По существу, протокол доказательства состоит в том, что Боб, используя случайность, выбирает некоторые вопросы, задает их Алисе и проверяет правильность ответов. Выполнение протокола завершается, когда машина V останавливается, при этом она выдает 1, если доказательство принято, и 0 - в противном случае.
Пусть и - две интерактивные, т.е. взаимодействующие через общую коммуникационную ленту, вероятностные машины Тьюринга. Через обозначается случайная величина - выходное слово машины , когда и работают на входном слове . Через обозначается длина слова .
Определение 4. Интерактивным доказательством для языка
называется пара интерактивных машин Тьюринга такая, что выполняются следующие два условия.
1. (Полнота). Для всех
2. (Корректность). Для любой машины Тьюринга , для любого полинома и для всех достаточно большой длины
Полнота означает, что если входное слово принадлежит языку и оба участника, и Алиса, и Боб, следуют протоколу, то доказательство будет всегда принято. Требование корректности защищает Боба от нечестной Алисы, которая пытается обмануть его, ``доказывая'' ложное утверждение. При этом Алиса может каким угодно образом отклоняться от действий, предписанных протоколом, т.е. вместо машины Тьюринга P использовать любую другую машину . Требуется, чтобы вероятность обмана была в любом случае пренебрежимо малой.
Определение 5. Интерактивный протокол доказательства для языка называется доказательством с абсолютно нулевым разглашением, если, кроме условий 1 и 2, выполнено еще и следующее условие.
3. (Свойство нулевого разглашения). Для любой полиномиальной вероятностной машины Тьюринга
существует вероятностная машина Тьюринга , работающая за полиномиальное в среднем время, и такая, что для всех
Машина
называется моделирующей машиной для . Предполагается, что математическое ожидание времени ее работы ограничено полиномом от длины . Это означает, что в принципе может, в зависимости от того, какие значения примут используемые в ее работе случайные переменные, работать достаточно долго. Но вероятность того, что время ее работы превысит некоторую полиномиальную границу, мала. Для каждой машины строится своя моделирующая машина; последняя может использовать как подпрограмму. Через обозначается случайная величина - выходное слово машины
, когда на входе она получает слово .
Свойство нулевого разглашения защищает Алису от нечестного Боба, который, произвольно отклоняясь от действий, предписанных протоколом (используя вместо V), пытается извлечь из его выполнения дополнительную информацию. Условие 3 означает, что Боб может при этом получить только такую информацию, которую он смог бы вычислить и самостоятельно (без выполнения протокола) за полиномиальное время.
Приведем в качестве примера протокол доказательства с абсолютно нулевым разглашением для языка ИЗОМОРФИЗМ ГРАФОВ из работы Гольдрайха, Микали и Вигдерсона []. Входным словом является пара графов и . Здесь - множество вершин, которое можно отождествить с множеством натуральных чисел , и - множества ребер такие, что . Графы и называются изоморфными, если существует перестановка на множестве такая, что тогда и только тогда, когда
(обозначается ). Задача распознавания изоморфизма графов - хорошо известная математическая задача, для которой на данный момент не известно полиномиальных алгоритмов. С другой стороны, неизвестно, является ли эта задача NP-полной, хотя есть веские основания предполагать, что не является.
Протокол IG
Пусть - изоморфизм между и . Следующие четыре шага выполняются в цикле раз, каждый раз с независимыми случайными величинами.
P выбирает случайную перестановку на множестве , вычисляет и посылает этот граф V.
V выбирает случайный бит и посылает его P.
Если , то P посылает V перестановку , в противном случае - перестановку .
Если перестановка, полученная V, не является изоморфизмом между и , то V останавливается и отвергает доказательство. В противном случае выполнение протокола продолжается.
Если проверки п.4 дали положительный результат во всех
циклах, то V принимает доказательство.
Заметим, что если в протоколе IG машина P получает изоморфизм в качестве дополнительного входного слова, то ей для выполнения протокола не требуются неограниченные вычислительные ресурсы. Более того, в этом случае P может быть полиномиальной вероятностной машиной Тьюринга.
Теорема 2. ([]) Протокол IG является доказательством с абсолютно нулевым разглашением для языка ИЗОМОРФИЗМ ГРАФОВ.
Полнота протокола IG очевидна.
Для доказательства корректности достаточно заметить, что бит , который V выбирает на шаге 2, указывает P, для какого из графов - или - требуется продемонстрировать изоморфизм с графом . Если и не изоморфны, то может быть изоморфен, в лучшем случае, одному из них. Поэтому проверка п. 4 даст положительный результат с вероятностью в одном цикле и с вероятностью во всех циклах.
Доказательство свойства нулевого разглашения значительно сложнее. Поэтому мы воспроизводим только основную идею. Прежде всего, заметим, что основная задача машины - получить максимально возможную информацию об изоморфизме между и . Естественно предположить, что она, в отличие от V, будет выдавать в качестве выходного слова не один бит, а всю полученную в результате выполнения протокола информацию, включая содержимое своей случайной ленты, графы и перестановки, полученные соответственно на шагах 1 и 3 протокола IG. Моделирующая машина должна уметь строить такие же случайные строки, графы и перестановки, не зная при этом изоморфизм ! Поэтому пытается угадать тот бит , который будет запросом машины на шаге 2. Для этого выбирает случайный бит , случайную перестановку и вычисляет . Далее запоминает состояние машины (включая содержимое случайной ленты) и вызывает ее как подпрограмму, подавая ей на вход граф . Ответом машины будет некоторый бит . Если , то моделирование в данном цикле завершено успешно, поскольку может продемонстрировать требуемый изоморфизм. Если же , то
восстанавливает ранее сохраненное состояние машины и повторяет попытку.
Если в определении свойства нулевого разглашения заменить равенство случайных величин и
требованием, чтобы их распределения вероятностей ``почти не отличались'', то получится другая разновидность доказательств - доказательства со статистически нулевым разглашением.
Еще один тип - доказательства с вычислительно нулевым разглашением. В этом случае требуется, чтобы моделирующая машина создавала распределение вероятностей, которое неотличимо от никаким полиномиальным вероятностным алгоритмом (неотличимость здесь определяется аналогично тому, как это делалось в определении псевдослучайного генератора).
Подчеркнем особо, что во всех трех определениях нулевого разглашения условия накладываются на действия моделирующей машины только на тех словах, которые принадлежат языку.
Помимо интереса к доказательствам с нулевым разглашением как к нетривиальному математическому объекту, они исследуются также и в связи с практическими приложениями. Наиболее естественный и важный тип таких приложений - (см. главу ). С помощью такого протокола Алиса может доказать Бобу свою аутентичность.
Предположим, например, что Алиса - это интеллектуальная банковская карточка, в которой реализован алгоритм P, а Боб - это компьютер банка, выполняющий программу V. Прежде чем начать выполнение каких-либо банковских операций, банк должен убедиться в подлинности карточки и идентифицировать ее владельца, или, говоря на языке криптографии, карточка должна пройти аутентификацию. В принципе для этой цели можно использовать приведенный выше протокол IG. В этом случае в памяти банковского компьютера хранится пара графов , сопоставленная Алисе, а на интеллектуальной карточке - та же пара графов и изоморфизм . Предполагается, что, кроме Алисы, этот изоморфизм никто не знает (кроме, быть может, Боба) и поэтому с помощью протокола IG карточка доказывает свою аутентичность. При этом свойство полноты означает, что карточка наверняка докажет свою аутентичность. Свойство корректности защищает интересы банка от злоумышленника, который, не являясь клиентом банка, пытается пройти аутентификацию, используя фальшивую карточку. Свойство нулевого разглашения защищает клиента от злоумышленника, который, подслушав одно или более выполнений протокола аутентификации данной карточки, пытается пройти аутентификацию под именем Алисы. Конечно, в данном случае бессмысленно доказывать, что пара графов принадлежит языку ИЗОМОРФИЗМ ГРАФОВ, поскольку она заведомо выбирается из этого языка. Вместо этого Алиса доказывает, что она знает изоморфизм . Интерактивные доказательства такого типа называются доказательствами знания.
Для практического применения очень важным свойством протокола IG, как и других протоколов доказательства знания, является то, что алгоритм P, получивший в качестве дополнительного входа изоморфизм , работает за полиномиальное время. Вместо протокола IG можно использовать, вообще говоря, любое другое доказательство с нулевым разглашением, в котором алгоритм P обладает этим свойством. Но для реальных приложений протокол IG, как и большинство подобных протоколов, не эффективен: большое количество циклов, слишком длинные сообщения и т.д. Поиск более эффективных доказуемо стойких протоколов - одно из основных направлений исследований в данной области.
Next: Литература к главе 2
Up: 2. Криптография и теория
Previous: 2.4. Псевдослучайные генераторы
Contents:
Еще раз о разделении секрета
В работе [] со ссылкой на книгу ``Gent und seine schoenheiten'' (Thill-Verlag, Bruessel, 1990) описывается следующий исторический пример. В XIII-XIV веках в г. Генте была построена ратушная башня. В ``секрете'' (secreet), самом надежном помещении башни, хранились уставы и привилегии, имевшие важное значение. Помещение имело две двери, каждая с тремя замками, ключи от которых находились во владении различных цехов. Документы хранились в шкафу, который, в свою очередь, также запирался на три ключа. Один из этих ключей хранился у фогта, а два других - у главного шеффена.
Мы привели этот пример в разделе, посвященном протоколам разделения секрета, главным образом для того, чтобы показать, что хотя криптографические протоколы - сравнительно молодая отрасль криптографии, задачи, которые решаются с помощью протоколов, возникли очень давно и имеют свою историю.
Почему ``еще раз о разделении секрета''? В главе разделение секрета рассматривается в основном как математическая, прежде всего комбинаторная, задача. Здесь же мы его обсуждаем как криптографический протокол. При этом предполагается, что читатель знаком с главой .
В протоколе разделения секрета имеются участников , которых мы будем называть процессорами, и один выделенный участник , называемый дилером (или, иногда, лидером). Протокол состоит из двух фаз.
На фазе разделения секрета дилер, знающий некоторый секрет , генерирует долей секрета и посылает процессору по защищенному каналу связи. На фазе восстановления секрета любое подмножество из не менее чем процессоров, где - параметр протокола, однозначно восстанавливает секрет, обмениваясь сообщениями по защищенным каналам связи. А любое подмножество из не более чем процессоров не может восстановить секрет (что означают слова ``не может восстановить'' будет пояснено ниже).
Как и в других типах криптографических протоколов, в протоколе разделения секрета участники, вообще говоря, не доверяют друг другу и каждый из них может оказаться противником. В том числе и дилер. Можно ли обеспечить какую-либо защиту честных участников даже и в этом случае? Безусловно, нечестный дилер может просто саботировать выполнение протокола. Но если дилер пытается обмануть более хитрым способом, то от этого, оказывается, можно защититься следующим образом. Фаза разделения секрета начинается с того, что дилер публикует секрет в ``зашифрованном'' виде (точнее было бы сказать - выполняет привязку к строке , по аналогии с привязкой к биту). С помощью этой информации каждый процессор может проверить, что значение , полученное им от дилера, действительно является долей секрета . Такой протокол называется протоколом проверяемого разделения секрета. В обычных схемах разделения секрета рассматривается пассивный противник, а именно, противником являются не более чем участников, которые, объединив свои доли, пытаются получить какую-либо информацию о значении секрета. На фазе восстановления секрета в протоколе проверяемого разделения секрета действует активный противник: нечестные участники могут преследовать цель сорвать восстановление значения честными участниками, посылая им вместо своих долей секрета любую другую информацию. От протокола требуется, чтобы честные участники, если их по крайней мере , всегда правильно восстанавливали значение .
Рассмотрим конструкцию протокола проверяемого разделения секрета из работы []. Конструкция основана на задаче дискретного логарифмирования.
В соответствии со схемой Шамира дилер выбирает случайный полином степени , где , вычисляет ( ) и публикует . После этого для всякого дилер вычисляет и посылает это значение процессору по защищенному каналу. Процессор , проверяя равенство
убеждается, что - доля секрета . В самом деле,
Конструкцию протокола для фазы восстановления секрета рассмотрим в наиболее простом случае, когда дилер честный. На этой фазе каждый процессор посылает каждому другому процессору свою долю . Всякий честный участник , получив некоторое значение от , проверяет это значение, как описано выше, и отбрасывает все доли , не прошедшие проверку. Поскольку честных участников не менее , получит по крайней мере правильных долей секрета. Используя алгоритм восстановления секрета из схемы Шамира, восстановит значение .
В отличие от схем разделения секрета, рассматриваемых в главе , стойкость данного протокола основывается на предположении о вычислительной трудности задачи дискретного логарифмирования. Поэтому, если в обычных схемах разделения секрета требуется, чтобы любое подмножество участников, не составляющее кворума, не получало никакой информации о секрете, то во многих схемах проверяемого разделения секрета такое подмножество лишь ``не может восстановить'' секрет. В том смысле, что для его восстановления требуется решить некоторую гипотетически трудную вычислительную задачу. В рассмотренном выше примере всякий участник мог бы узнать секрет , если бы он умел вычислять дискретные логарифмы.
Одно из возможных приложений схем разделения секрета - организация хранения криптографических ключей. Свойство проверяемости представляется далеко не лишним для таких приложений. Но круг приложений схем проверяемого разделения секрета существенно шире.
Предположим, что с помощью описанной выше схемы разделены два секрета и и что оба эти секреты являются числами. Теперь представим себе ситуацию, что после этого потребовалась разделить секрет . Конечно, это может сделать дилер с помощью того же протокола. А могут ли процессоры выполнить то же самое без участия дилера?
Пусть и - полиномы, которые использовались для разделения секретов и соответственно. Пусть
и для . Для любого пусть и - доли секретов и , полученные процессором . Ясно, что
- также полином степени и .
Поэтому каждый процессор может вычислить долю секрета просто по формуле . Эти доли проверяемы с помощью значений .
Рабин и Бен-Ор показали [], что выполняя такого рода вычисления над долями секретов, процессоры могут вычислить любую функцию над конечным полем ``проверяемым образом''. Этот результат относится к области протоколов конфиденциального вычисления (secure multi party computation). Типичная задача здесь такая. Требуется вычислить значение функции на некотором наборе значений аргументов . С помощью схемы проверяемого разделения секрета вычисляются доли этих значений. В начале выполнения протокола доля известна процессору и только ему. Протокол должен обеспечивать вычисление значения таким образом, чтобы для некоторого параметра :
1) в результате выполнения протокола любое подмножество из не более чем процессоров не получало никакой информации о значениях других процессоров (кроме той, которая следует из известных им долей и значения функции
;
2) при любых действиях нечестных участников остальные участники вычисляют правильное значение , если только количество нечестных участников не превосходит .
Протоколы конфиденциального вычисления, ввиду своей общности, представляют несомненный теоретический интерес. Кроме того, многие типы прикладных криптографических протоколов (например, протоколы голосования) по существу являются частными случаями протоколов конфиденциального вычисления.
При различных предположениях о процессорах и о сети связи доказан ряд теорем следующего типа: если не превосходит некоторого порогового значения (зависящего от и от предположений), то всякая вычислимая функция имеет протокол конфиденциального вычисления.
Next: 3.6. Поиграем в ``кубики''.
Up: 3. Криптографические протоколы
Previous: 3.4. Протоколы типа ``подбрасывание
Contents:
Где взять истинно случайную последовательность?
На первый взгляд, эта задача очень проста. Можно, например, вычислить случайный адрес памяти и взять оттуда данные. Или можно вычислить случайный номер сектора на диске и взять данные оттуда. Эти данные, бесспорно, будут случайными. Но какое распределение будут иметь члены полученной случайной последовательности? Неизвестно. Если полученные случайные данные представляют собой фрагмент текстового файла, то распределение символов, представляемых байтами файла, будет одно, если это фрагмент машинного кода - совсем другое. Одно можно сказать точно - это распределение почти никогда не будет равномерным. Ниже приведены гистограммы встречаемости символов для различных видов информации.
Как видите, из всех приведенных гистограмм только последняя более-менее похожа на гистограмму равномерного распределения. Однако, если приглядеться повнимательнее, в ней можно заметить пик вдоль оси (впрочем, этот пик нетипичен для архивов pkzip - он объясняется тем, что выбранный архив включал в себя очень много коротких файлов).
Конечно, если распределение исходной последовательности задано априорно, путем несложного преобразования эту последовательность можно превратить в распределенную равномерно. Но подсчитать распределение символов для информации, хранимой в памяти и на дисках компьютера, не удается даже в том случае, если известно, откуда эта информация взялась. Посмотрите на гистограмму встречаемости символов в тексте этой главы. А теперь посмотрите на следующую гистограмму.
Как видите, распределения отличаются довольно сильно. Получается, что если в документе есть картинки, исходное распределение одно, а если нет - совсем другое.
Кроме того, в осмысленных текстах (в том числе и в текстах exe-файлов, баз данных и т.д.) обязательно присутствуют статистические закономерности более высокого порядка. Если построить гистограмму встречаемости биграмм и триграмм, она будет еще менее похожа на горизонтальную линию (что должно иметь место при равномерном распределении), чем гистограмма встречаемости отдельных символов. Например, в exe-файле, скомпилированном с помощью Visual C, машинный код подавляющего большинства функций (подпрограмм) начинается байтами
55 8B EC 83 EC2)
и заканчивается байтами
8B E5 5D C3.3)
Поэтому последовательность байтов, полученных из случайного места оперативной памяти или диска, нельзя считать случайной. В такой последовательности наверняка есть внутренние статистические зависимости.
Next: Так где же взять
Up: 6.3. Как зашифровать файл?
Previous: Где взять ключи?
Contents:
Где взять ключи?
Каким должен быть ключ шифрования? Случайным и равновероятным. А как получить случайную и равновероятную последовательность символов? Правильно, с помощью . Написать свой генератор ``случайных'' чисел очень просто. Хорошие по статистическим свойствам последовательности получаются по формуле линейного конгруэнтного метода:
где - -й член псевдослучайной последовательности; , , - некоторые целые числа.
Качество псевдослучайной последовательности зависит от выбора чисел , и . Эти числа обязательно должны быть взаимно просты. Есть и другие правила выбора этих коэффициентов, о них можно прочитать в []. В , например, используется следующий генератор псевдослучайной последовательности:
Как видите, формула для получения очередного ``случайного'' числа рекурсивна - каждый член последовательности зависит от предыдущего. Возникает вопрос: откуда берется первый член? Обычно в качестве берут текущее время с точностью до тика таймера (0,054945 сек.). Если для генерации ключа используется линейный конгруэнтный метод, ключом является последовательность чисел , где
Предположим, что с помощью линейного конгруэнтного метода сгенерирована последовательность , где каждое есть короткое целое число (16 бит). Созданный ключ представляет собой случайную равновероятную последовательность длиной 256 байт. Оценим, сколько различных вариантов ключа можно получить по данной схеме.
Зафиксируем значение . Какие значения может принимать ? Только одно значение. Если фиксировано, то значение определено однозначно:
Значение тоже определено однозначно. Оно равно
Таким образом, значение однозначно определяет значения всех следующих членов последовательности. Получается, что различных последовательностей
в точности столько же, сколько различных значений . В нашем примере - короткое целое число, принимающее значения от 0 до
. Оказывается, что стойкость ключевой системы (число различных вариантов ключа) равна не , а всего лишь , что в раз меньше!
Получается, что псевдослучайные последовательности в качестве ключей использовать нельзя. А что можно?
В чем слабость псевдослучайных последовательностей? В том, что они псевдослучайны. Первый член последовательности однозначно определяет остальные. Чтобы ключ был по-настоящему случайным и равновероятным, последовательность должна быть не псевдослучайной, а истинно случайной.
Next: Где взять истинно случайную
Up: 6.3. Как зашифровать файл?
Previous: А можно ли обойтись
Contents:
Идеальное разделение секрета и матроиды
Начнем с определения идеальных СРС. Для этого вернемся к комбинаторному определению совершенной СРС. Следующее определение совершенной СРС [] является даже более общим, чем вероятностное , поскольку условие заменено в нем на более слабое.
Для произвольного множества обозначим через -матрицу, полученную из матрицы удалением столбцов, номера которых не принадлежат множеству . Пусть обозначает число различных строк в матрице .
Определение 3.
Матрица задает БД-совершенную СРС, реализующую структуру доступа , если labeli4
|
(4) |
где , если , и
в противном случае.
Это определение отличается от
и тем, что на неразрешенные множества накладывается довольно слабое условие, а именно, если множество строк с данными значениями координат из множества непусто, то все возможные значения секрета встречаются в нулевой координате этих строк (без требований ``одинаково часто'' как в комбинаторном
или же ``с априорной вероятностью'' как в вероятностном ). Легко видеть, что матрица любой совершенной вероятностной СРС задает БД-совершенную СРС, но обратное неверно.
Для произвольной комбинаторной СРС, задаваемой матрицей , определим на множествах функцию
где Легко проверить, что
для любых множеств и , а условие (4) может быть переписано в виде
Лемма . Для любой БД-совершенной СРС если и , то .
Доказательство. По условиям леммы и
. Следовательно,
Так как мы предполагаем, что все точки существенные, т.е. для любого найдется подмножество такое, что и , то из леммы вытекает
Следствие . Для любой БД-совершенной СРС
для всех .
Следствие означает, как мы и предупреждали в начале статьи, что для совершенных СРС ``размер'' проекции не может быть меньше ``размера'' секрета. Поэтому БД-совершенная СРС называется идеальной, если для всех .
Замечание .
Неравенство справедливо и для совершенных вероятностных СРС, поскольку их матрицы задают БД-совершенные СРС.
Естественный вопрос состоит в том, для каких структур доступа существуют реализующие их идеальные (вероятностные или комбинаторные) СРС. Как уже отмечалось во введении, наилучший на сегодняшний день ответ использует слово ``матроид''. Напомним определение матроидов и некоторые их основные свойства (см. []).
Матроидом называется конечное множество и семейство его подмножеств, называемых независимыми (остальные множества называются зависимыми), если выполнены следующие свойства:
Пример 4.
Множество - это множество векторов в некотором линейном векторном пространстве, а независимые подмножества - это линейно независимые подмножества векторов.
Собственно с этого примера и началась теория матроидов, вначале как попытка дать аксиоматическое определение линейной независимости векторов через ``внутренние свойства'', т.е. не апеллируя к понятию вектора. К счастью, попытка не удалась, так как нашлись матроиды, не представимые как линейные (т.е. как системы векторов), а сама теория матроидов разрослась далеко за пределы ``линейной алгебры'' (см. []).
Пример 5. (матроид Вамоса)
Рассмотрим следующее множество: и положим , , и . Матроид Вамоса определяется как матроид, в котором множества , , , , , а также все подмножества из пяти или более элементов являются зависимыми. Известно, что этот матроид не является линейным.
Матроид также можно определить через так называемую ранговую функцию матроида, определяемую как максимальная мощность независимого подмножества . Очевидно, что независимые множества (и только они) задаются условием . Ранговая функция матроида обладает свойствами
Обратно, пусть некоторая функция обладает свойствами . Назовем независимыми те множества , для которых .
Тогда эти множества задают матроид, а функция является его ранговой функцией. Возможно также определить матроид через минимальные зависимые множества, называемые циклами. Матроид называется связным, если для любых двух его точек существует содержащий их цикл.
Теперь мы можем сформулировать основной результат.
Теорема . ([]) Для любой БД-совершенной идеальной СРС, реализующей структуру доступа , независимые множества, определяемые условием
, задают связный матроид на множестве
. Все циклы этого матроида, содержащие точку , имеют вид , где
.
Главным в доказательстве теоремы является ``проверка'' целочисленности функции . В самом деле, очевидно обладает остальными свойствами и, следовательно, при условии целочисленности является ранговой функцией и задает матроид. Доказательство этой теоремы и несколько более общих утверждений можно найти в [].
Отметим, что из второй части утверждения теоремы следует, что разным идеальным СРС, реализующим данную структуру доступа , всегда соответствует один и тот же матроид, поскольку матроид однозначно определяется всеми циклами, проходящими через фиксированную точку (см. []). Тем самым, каждой идеально реализуемой структуре доступа соответствует однозначно определенный матроид.
В связи с теоремой возникает несколько естественных вопросов. Прежде всего, не порождают ли идеальные СРС все матроиды? Нет, например, матроид Вамоса не может быть получен как матроид идеальной СРС []. С другой стороны, линейные матроиды есть ни что иное как рассмотренные в разделе идеальные одномерные линейные СРС. В связи с этим возникает вопрос о существовании структуры доступа , которую невозможно реализовать в виде идеальной одномерной линейной СРС, но можно в виде идеальной многомерной линейной СРС. Недавно такой пример был построен [], и, значит, мы можем говорить о многомерных линейных матроидах как классе матроидов более общем, чем линейные.
Итак, идеальных СРС больше, чем линейных матроидов, но меньше, чем всех матроидов. Уточнить, ``насколько больше'', представляется довольно сложной задачей. В частности, существует ли идеально реализуемая структура доступа , которую невозможно реализовать как идеальную линейную многомерную СРС?
Next: Литература к главе 5
Up: 5. Математика разделения секрета
Previous: 5.3. Линейное разделение секрета
Contents:
-Я попытка
Теперь встанем на сторону нападающей стороны и попробуем написать программу для нахождения неизвестного ключа. Пусть у вас есть исходный и закрытый файлы. Если это не так, то надо постараться получить хотя бы общее представление о том, что представляет собой исходный файл: исполняемый код, текст программы на каком-либо языке программирования, текст в кодировке ASCII, ANSI, KOI-8 и т.п. Если даже это неизвестно, то возможность определен ия правильного ключа зачастую вообще становится проблематичной. Но не будем о грустном. Пусть у вас есть оба файла. Воспользуемся написанной ранее программой шифрования и добавим к ней блоки генерации ключей и сравнения полученного зашифрованного текста с имеющимся открытым. Прежде чем запустить на исполнение программу, подумаем, сколько времени она может работать.
Сначала найдем среднее число знаков текста, которое требуется для отбраковки случайного ключа. Предположим, что наша программа последовательно сравнивает биты текста, полученного шифрованием с помощью случайно выбранного ключа, с битами имеющегося закрытого файла. Если реализованный в программе шифр обладает хорошими свойствами и дает , похожий на случайную последовательность, то по первому биту будет забракована приблизительно половина ключей, по второму - еще четверть, и т.д. В итоге мы получим, что среднее число знаков для отбраковки оценивается бесконечной суммой
Математики знают, что эта сумма равна двум. Поэтому, как это ни странно, потребуется в среднем всего два бита текста для отбраковки ложного случайного ключа. Это один из первых парадоксов криптографического анализа. А ведь для того, чтобы убедиться в том, что ключ найден правильно, надо расшифровать весь текст.
Данный результат обнадеживает своей неожиданностью. Поэтому сразу переходим ко второй части задачи и найдем, сколько потребуется в среднем перебрать вариантов ключа до появления искомого. Считаем, что все ключи равноправны. Перенумеруем их и начнем по очереди проверять с помощью нашей программы. На первый взгляд кажется, что от выбора порядка нумерации ключей зависит очень много. Действительно, если у вас есть дар предвидения и вы выбрали такой порядок, что искомый ключ имеет первый номер, то программа сработает уже на первом шаге. Но не будем верить в чудо и найдем среднее число шагов для случайно выбранного порядка. Оно равно
где - число различных упорядочений множества из ключей, у которых истинный ключ стоит на месте с номером . Так как легко подсчитать, что , то наша сумма равна
Итак, в среднем придется перебрать чуть больше половины всех ключей.
Теперь вернемся от математики к суровой действительности. Пусть вы написали великолепную программу, которая проверяет за одну секунду один миллион вариантов ключа. Тогда за час программа переберет 3600000000 ключей, за сутки - 86400000000 ключей, а за год - более 30000000000000. Короче, для перебора ключей шифратора DES вашей программе потребуется в среднем чуть более 1500 лет. Вдохновляющий результат, не правда ли? А теперь подсчитайте, сколько лет потребуется вашей программе для нахождения неизвестного ключа у отечественного алгоритма шифрования ГОСТ 28147, в котором число ключей равно .
Подобные оценки помогут вам избежать излишеств и правильно выбрать длину ключа для вашей программы.
А теперь перейдем к решению практических вопросов.
Next: 6.3. Как зашифровать файл?
Up: 6.2. Немного теории
Previous: Удобно ли носить большую
Contents:
Э.По, ``Золотой жук''
Найден пергамент с текстом криптограммы. Для удобства пронумеруем по порядку все символы этого текста:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 5 | 3 | # | # | + | 3 | 0 | 5 | ) | ) | 6 | * | ; | 4 | 8 | 2 | 6 | ) | 4 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 |
| # | ) | 4 | # | ) | ; | 8 | 0 | 6 | * | ; | 4 | 8 | + | 8 |
| 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 |
| 6 | 0 | ) | ) | 8 | 5 | ; | ; | ] | 8 | * | ; | : | # | * | 8 |
| 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 |
| + | 8 | 3 | ( | 8 | 8 | ) | 5 | * | + | ; | 4 | 6 | ( | ; | 8 | 8 |
| 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 |
| * | 9 | 6 | * | ? | ; | 8 | ) | * | # | ( | ; | 4 | 8 | 5 | ) | ; |
| 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 |
| 5 | * | + | 2 | : | * | # | ( | ; | 4 | 9 | 5 | 6 | * | 2 | ( |
| 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 |
| 5 | * | = | 4 | ) | 8 | 8 | * | ; | 4 | 0 | 6 |
| 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 |
| 9 | 2 | 8 | 5 | ) | ; | ) | 6 | + | 8 | ) | 4 | # |
| 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 |
| # | ; | 1 | ( | # | 9 | ; | 4 | 8 | 0 | 8 | 1 | ; | 8 |
| 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 |
| : | 8 | # | 1 | ; | 4 | 8 | + | 8 | 5 | ; | 4 | ) | 4 |
| 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 |
| 8 | 5 | + | 5 | 2 | 8 | 8 | 0 | 6 | * | 8 | 1 | ( |
| 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 |
| # | 9 | ; | 4 | 8 | ; | ( | 8 | 8 | ; | 4 | ( | # |
| 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 |
| ? | 3 | 4 | ; | 4 | 8 | ) | 4 | # | ; | 1 | 6 | 1 |
| 196 | 197 | 198 | 199 | 200 | 201 | 202 | 203 | 204 |
| ; | : | 1 | 8 | 8 | ; | # | ? | ; |
Кроме того, на пергаменте изображены череп и козленок. Главный герой рассказа рассуждал следующим образом. По английски козленок - kid; череп связан с капитаном Киддом, по английски - kidd. Козленок был нарисован на пергаменте в том месте, где ставится подпись. Изображение черепа в противоположном по диагонали углу наводило на мысль о печати или гербе. Капитан Кидд владел несметным богатством. Кидд, насколько мы можем судить о нем, не сумел бы составить истинно сложную криптограмму. По-видимому, это была простая замена. Возникает только вопрос о языке, на котором был написан текст. В данном случае трудностей с определением языка не было: подпись давала разгадку. Игра слов kid и kidd возможна лишь в английском языке.
Текст криптограммы идет в сплошную строку. Задача была бы намного проще, если бы отдельные слова были отделены пробелами. Тогда можно было бы начать с анализа и сличения более коротких слов, и как только нашлось бы слово из одной буквы (например, местоимение ``я'' или союз ``и'' - для русского языка), начало было бы положено. Но просветов в строке не было.
Приходится подсчитывать частоты одинаковых символов, чтобы узнать, какие из них чаще, а какие реже встречаются в криптограмме. В результате получилась таблица частот всех символов:
| 8 | ; | 4 | ) | # | * | 5 | 6 | ( | + | 1 | 0 | 2 | 9 | : | 3 | ? | ] | = | ||
| 34 | 27 | 19 | 16 | 15 | 14 | 12 | 11 | 9 | 8 | 7 | 6 | 5 | 5 | 4 | 4 | 3 | 2 | 1 | 1 | 1 |
В английской письменной речи самая частая буква - e. Далее идут в нисходящем порядке: a, o, i, d, h, n, r, s, t, u, y, c, f, g, l, m, w, b, k, p, q, x, z. Буква e, однако, настолько часто встречается, что трудно построить фразу, в которой она не занимала бы господствующего положения. Итак, уже сразу у нас в руках путеводная нить. Составленная таблица, вообще говоря, может быть очень полезна, но в данном случае она понадобилась лишь в начале работы.
Поскольку символ 8 встречается чаще других, примем его за букву e английского алфавита. Для проверки этой гипотезы взглянем, встречается ли этот символ дважды подряд, так как в английском языке буква e часто удваивается, например, в словах meet, fleet, speed, seen, seed, been, agree, и т.д. Хотя криптограмма невелика, пара 88 стоит в нем пять раз.
Самое частое слово в английском языке - определенный артикль the. Посмотрим, не повторяется ли у нас сочетание из трех символов, расположенных в одинаковой последовательности и оканчивающихся символом 8. Если такое найдется, то это будет, по всей вероятности, the. Приглядевшись, находим семь раз сочетание из трех символов ;48. Итак, мы имеем право предположить, что символ ; - это буква t, а 4 - h; вместе с тем подтверждается, что 8 - это действительно e. Мы сделали важный шаг вперед.
То, что мы расшифровали целое слово, потому так существенно, что позволяет найти границы некоторых других слов. Для примера возьмем предпоследнее из сочетаний этого рода ;48 (позиции 172-174). Идущий сразу за 8 символ ; будет, как видно, начальной буквой нового слова. Выпишем, начиная с него, 6 символов подряд. Только один из них нам незнаком. Обозначим известные символы буквами и оставим свободное место для неизвестного символа (обозначим его точкой) t.eeth, ни одно слово, начинающееся с t и состоящее из 6 букв, не имеет в английском языке окончания th. В этом легко убедиться, подставляя на свободное место все буквы по очереди. Попробуем отбросить две последние буквы и получим t.ee, для заполнения свободного места можно снова взяться за алфавит. Единственно верным прочтением этого слова будет tree (дерево). В таком случае мы узнаем еще одну букву - r, она обозначена символом ( и мы можем прочитать два слова подряд the tree, в дальнейшем эта гипотеза может либо подтвердиться, либо привести к некоторому ``нечитаемому'' фрагменту. В последнем случае следует попытаться восстановить либо слово t.e, либо t.eet, либо слово, целиком включающее в себя t.eeth
Развиваем успех. Немного далее (186-188) находим уже знакомое нам сочетание ;48. Примем его опять за границу нового слова и выпишем целый отрывок, начиная с двух расшифрованных нами слов. Получаем такую запись:
the tree ;4(#?34 the
Заменим уже известные символы буквами:
the tree thr#?3h the
а неизвестные - точками:
the tree thr...h the
Нет никакого сомнения, что неясное слово - through (через). Это открытие дает нам еще три буквы - o, u и g, обозначенные в криптограмме символами # ? и 3.
Надписывая над уже определенными символами криптограммы их значения, находим вблизи от ее начала (позиции 54-58) группу символов 83(88, которая читается так egree, это, конечно, слово degree (градус) без первой буквы. Теперь мы знаем, что буква d обозначена символом +. Вслед за словом degree через 4 символа встречаем группу ;46(;88*. Заменим известные символы буквами, а неизвестные - точками th.rtee, по-видимому, перед нами слово thirteen (тринадцать). К известным нам буквам прибавились i и n, обозначенные в криптограмме символами 6 и *.
Криптограмма начинается так: 53##+. Подставляя буквы и точки, получаем .good, недостающая буква, конечно, a, и, значит, два первых слова будут читаться так: a good (хороший). Определены следующие 11 символов:
| 5 | + | 8 | 3 | 4 | 6 | * | # | ( | ; | ? |
| a | d | e | g | h | i | n | o | r | t | u |
На этом анализ Э. По заканчивается. Дальнейшую работу проделаем самостоятельно.
Четвертый по частоте (16 вхождений) символ ) еще не определен. Возвратимся к диаграмме встречаемости букв английского языка. Среди первого десятка букв этой диаграммы у нас не встретилась лишь буква s. Она - первый претендент на значение символа ). Эта гипотеза подтверждается тем, что вряд ли ) обозначает гласную букву, так как в таком случае мы получили бы ``нечитаемые'' фрагменты
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| g | . | a | ) | ) | i | n |
| 37 | 38 | 39 | 40 | 41 | 42 |
| i | . | ) | ) | e | a |
Перебирая возможные значения символа 0, стоящего на позициях 7 и 28 криптограммы, убеждаемся в том, что единственно возможным его значением может быть лишь буква l (glass - стекло, hostel - общежитие, гостиница или трактир).
Определяем, далее, значение символа как v по фрагменту текста в позициях 107-113.
Теперь на участке текста с 22-й по 70-ю позиции остались неопределенными лишь значения символов ] и :, встретившихся по одному разу. Очевидно, что символ ] - это w, а символ : - это y. Теперь на участке текста с 172-й по 204-ю позиции не выявлено лишь значение символа 1, которое, как нетрудно заметить, может быть лишь буквой f.
Символ 2, стоящий на позициях 117 и 90, очевидно, заменяет букву b.
Осталось определить лишь значения символов и =. Небольшой перебор еще неустановленных букв показывает, что символ = - это c, а символ может обозначать одну из букв k, p, q, x или z. Обратившись к словарю, находим единственное подходящее окончание p слова bishop (епископ, слон).
Таким образом, однозначно определились значения всех 21 символов, встречающихся в криптограмме. Получился следующий открытый текст:
``A good glass in the bishop's hostel in the devil's seat twenty one degrees and thirteen minutes northeast and by north main branch seventh limb east side shoot from the left eye of the death's head a bee line from the tree through the shot fifty feet out''.
В переводе на русский язык: ``Хорошее стекло в трактире епископа на чертовом стуле двадцать один градус и тринадцать минут северо-северо-восток главный сук седьмая ветвь восточная сторона стреляй из левого глаза мертвой головы прямая от дерева через выстрел на пятьдесят футов''.
Восстановленная простая замена:
| A | B | C | D | E | F | G | H | I | L | M | N | O | P | R | S | T | U | V | W | Y |
| 5 | 2 | = | + | 8 | 1 | 3 | 4 | 6 | 0 | 9 | * | # | ( | ) | ; | ? | ] | : |
Up: 7.2. Шифры замены
Previous: А. Конан Дойл, ``Пляшущие человечки''
Contents:
К задачам четвертой олимпиады
Исходный текст состоит из 48 букв, следовательно, при зашифровании было использовано три положения решетки полностью и еще три буквы вписаны в четвертом положении. Значит, незаполненные 12 клеток совпадают с вырезами решетки в четвертом положении. Так как текст вписывается последовательно, то неизвестные нам три выреза могут располагаться только в первой строке таблицы и первых пяти клетках второй строки (до первого известного выреза). Считаем, что трафарет лежит в четвертом положении. Учитывая, что в одну клетку листа нельзя вписать две буквы, получаем, что вырезы могут быть только в отмеченных знаком ``?'' местах трафарета (``'' - места известных вырезов):
| ? | ? | |||||||||
| ? | ? | |||||||||
Очевидно, что из отмеченных в первой строке двух клеток вырезается только одна (так как они совмещаются поворотом). Получаем два возможных варианта решетки (либо первый ``?'', либо второй ``?'' в первой строке). Читаемый текст получается при втором варианте.
Ответ: ПОЛЬЗУЯСЬШИФРОМРЕШЕТКАНЕЛЬЗЯОСТАВЛЯТЬПУСТЫЕМЕСТА
Один из вариантов решения состоит из следующих этапов.
1. 19=н из второй строки (``19,2 19,5'').
2. 29=о из третьей строки (``29,н,10'') и 10=а или 10=и.
3. 14=щ из ``но,14,но''.
4. 8=д, 2=е, 10=и из ``денно и нощно''.
Получили текст:
5. 5=а и 27=з из второй строки.
6. 17=в 6=п 16=й - последнее слово второй строки - водопой.
Получили текст:
7. 21=т 18=у 28=л 20=с из последней строки ``ищут веселой толпой''.
8. 11=р из ``зве11ей'' первой строки.
Итак,
9. 24=г из ``егерей''.
10. 12=б 3=ю из ``бегают''.
11. 31=ы 22=ч из ``добычей''.
Ответ: Бегают по лесу стаи зверей -
Не за добычей, не на водопой:
Денно и нощно они егерей
Ищут веселой толпой.
Занумеруем буквы латинского алфавита последовательно числами от 1 до 24. Пусть - некоторое число от 1 до 24, а - число, в которое переходит на втором этапе. Тогда перестановочность этапов можно записать в следующем виде:
Это означает, что соседние числа и на втором этапе переходят в соседние же числа и , т.е. второй этап - тоже сдвиг. Последовательное применение двух сдвигов - очевидно тоже сдвиг и остается рассмотреть 24 варианта различных сдвигов. Читаемый текст определяется однозначно. Осложнения, связанные с переходом Z в A, устраняются либо переходом к остаткам при делении на 24, либо выписыванием после буквы Z второй раз алфавита AB...Z.
Ответ: INTER ARMA SILENT MUSAE
(интер арма силент музэ - когда гремит оружие, музы молчат).
Составим возможные варианты переданных букв:
| ГЪЙ | АЭЕ | БПРК | ЕЖЩЮ | НМЬЧ | СЫЗЛ | ШДУ | ЦХОТ | ЯФВИ |
| БШЗ | АЫВ | АНОИ | ГЕЧЬ | ЛКЪХ | ПЩЕЙ | ЦВС | ФУМР | ЭТАЖ |
| ВЩИ | БЬЕ | БОПЙ | ДШЭ | МЛЫЦ | РЪЖК | ЧГТ | ХФНС | ЮУБЗ |
| ГЪЙ | ВЭ | ВПРК | ЕЖЩЮ | НМЬЧ | СЬЗЛ | ШДУ | ЦХОТ | ЯФВИ |
| ДЫК | ЮЖ | ГРСЛ | ЗЪЯ | ОНЭШ | ТЬИМ | ЩЕФ | ЧЦПУ | ХГЙ |
| ЕЬЛ | ЯЗ | СТМ | ЖИЫ | ПОЮЩ | УЭЙН | ЪХ | ШЧРФ | ЦДК |
| ГЪЙ | АЭЕ | БПРК | ЕЖЩЮ | НМЬЧ | СЫЗЛ | ШДУ | ЦХОТ | ЯФВИ |
| БШ | НОИ | ГЕЧЬ | ЛКЪХ | ПЩЕЙ | Ц С | ФУМР | ЭТАЖ | |
| ЩИ | БОПЙ | ДШ | МЛЫЦ | РЪ К | ЧГ | ХФНС | ||
| ГЪЙ | В |
ПРК | Е Щ | НМЬЧ | СЬ Л | ШДУ | ЦХО | |
| ГРСЛ | Ъ | ОН |
ЬИМ | ЩЕФ | ЧЦПУ | |||
| ЕЬЛ | ЯЗ | С М | ИЫ | ПО |
У ЙН | ЪХ | ШЧРФ |
|
ГНОЙ ГНОМ ГРОМ |
Ответ:БЫК ВЯЗ ГНОЙ ДИЧЬ ПЛЮЩ СЪМ ЦЕХ ШУРФ ЭТАЖ
Заметим, что для всех натуральных . Складывая почленно эти равенства при
, получим . По условию . Следовательно, справедливо соотношение .
Ясно, что при расшифровании так же, как и при зашифровании, вместо чисел , , , , , , можно воспользоваться их остатками от деления на 30. Так как для каждого целого неотрицательного
где - некоторое целое число, то получаем следующие остатки при делении чисел на 30:
| 0 | 3 | 12 | 3 | 12 | 15 | 18 |
| шифрованное сообщение | К | Е | Н | З | Э | Р | Е |
| числовое шифрованноесообщение | 9 | 5 | 12 | 7 | 27 | 15 | 5 |
| шифрующий отрезок | 0 | 3 | 12 | 3 | 12 | 15 | 18 |
| числовое исходное сообщение | 9 | 2 | 0 | 4 | 15 | 0 | 17 |
| исходное сообщение | К | В | А | Д | Р | А | Т |
.
Next: ...к задачам пятой олимпиады
Up: 7.6. Указания и решения
Previous: ...к задачам третьей олимпиады
Contents:
К задачам девятой олимпиады
а) Для доказательства достаточно указать хотя бы одну последовательность из 33 различных букв, сумма которой с русским алфавитом из 33 букв не содержит одинаковых букв. В качестве искомой последовательности возьмем сам алфавит. Докажем, что сумма алфавита с самим собой не содержит одинаковых букв. Пусть и - порядковые номера различных букв алфавита. Тогда по определению сложения букв достаточно показать, что числа и имеют разные остатки от деления на 33. В самом деле, если бы они были одинаковы, то число делилось бы на 33 без остатка. В силу того что
, разность также делилась бы на 33 без остатка, что невозможно. Утверждение пункта а) доказано.
Замечание. Утверждение пункта а) остается в силе для любого алфавита из нечетного числа букв.
б) При сложении двух последовательностей сумма порядковых номеров всех букв получаемой при этом последовательности и сумма порядковых номеров всех букв обоих слагаемых имеет один и тот же остаток от деления на 26. Значит, разность упомянутых сумм должна делиться на 26 без остатка. Докажем утверждение пункта б) методом от противного. В самом деле, если такая последовательность из 26 различных букв существует, то упомянутая разность равна сумме порядковых номеров букв алфавита. Однако сумма
при делении на 26 имеет остаток 13. Это доказывает утверждение пункта б).
Замечание. Утверждение пункта б) остается в силе для любого алфавита из четного числа букв.
Представляет интерес доказательство пункта б), предложенноеучастниками олимпиады.
При делении на любое четное число суммы двух четных или двух нечетных чисел получается четный остаток, а при делении суммы четного и нечетного чисел - нечетный остаток.
Соответствующие буквы складываемых последовательностей могут быть как одинаковой, так и различной четности. (Для краткости мы называем букву четной, если ее номер четен, и нечетной - если номер нечетен.) Будем решать задачу от противного. Предположим, что требуемая последовательность существует. Всего в сложении участвуют 52 буквы. Пар букв одинаковой и различной четности должно быть одинаковое количество, а именно 13 (так как в результате сложения должно получиться 13 четных и 13 нечетных букв). Пары букв различной четности включают в себя 26 букв. Оставшиеся 26 букв входят в 13 пар букв одинаковой четности. Однако, 13 пар букв одинаковой четности не могут содержать одинаковое количество четных и нечетных букв (так как 13 - нечетное число). Полученное противоречие доказывает утверждение пункта б).
В этой задаче условимся писать , если числа и имеют одинаковые остатки при делении на 33. Пусть - номер первой буквы искомой последовательности. Эту букву указанное число раз прибавили к букве К, в результате получили букву А. Запишем соответствующее уравнение:
| (1) |
Уравнение () принимает вид: , или
| (2) |
| А | Б | В | Г | Д | Е | Ж | З | И | Й | К | Л | М | Н | О | П | Р | С | Т | У | Ф | |
| 17 | 1 | 18 | 2 | 19 | 3 | 20 | 4 | 21 | 5 | 22 | 6 | 23 | 7 | 24 | 8 | 25 | 9 | 26 | 10 | 27 | 11 |
| Х | Ц | Ч | Ш | Щ | Ъ | Ы | Ь | Э | Ю | Я | |||||||||||
| 28 | 12 | 29 | 13 | 30 | 14 | 31 | 15 | 32 | 16 | 0 |
К задачам первой олимпиады
Все клетки квадрата размера разобьем на непересекающиеся группы по четыре клетки в каждой.
| 1 | 2 | 3 | 4 | 5 | 1 |
| 5 | 6 | 7 | 8 | 6 | 2 |
| 4 | 8 | 9 | 9 | 7 | 3 |
| 3 | 7 | 9 | 9 | 8 | 4 |
| 2 | 6 | 8 | 7 | 6 | 5 |
| 1 | 5 | 4 | 3 | 2 | 1 |
Отнесем клетки к одной и той же группе, если при каждом повороте квадрата до его самосовмещения они перемещаются на места клеток этой же группы. На рисунке показано такое разбиение на группы всех клеток квадрата , причем клетки одной группы помечены одной и той же цифрой. Всего таких групп будет (целое, так как - четное число). При наложении трафарета на квадрат ровно одна клетка из каждой группы окажется под его вырезами. Каждому трафарету поставим в соответствие упорядоченный набор всех клеток из таких групп, оказавшихся под вырезами трафарета при наложении его на квадрат помеченной стороной вверх. Такое соответствие является взаимнооднозначным, поскольку каждому ключу будет однозначно соответствовать упорядоченный набор из клеток (по одной из каждой группы), вырезанных в трафарете, и наоборот. Всего таких наборов . В самом деле, существует ровно четыре различных варианта выбора клетки из каждой группы независимо от выбранных клеток из других таких групп. Таким образом, число различных ключей шифра ``поворотная решетка'' при четных значениях равно .
Легко видеть, что . Отсюда , где - корни многочлена . Получаем
| Буква ш.с. | Ф | В | М | Е | Ж | Т | И | В | Ф | Ю |
|
Номер |
22 | 3 | 14 | 7 | 8 | 20 | 10 | 3 | 22 | 32 |
| Номер | 20 | 1 | 12 | 5 | 6 | 18 | 8 | 1 | 20 | 30 |
|
Буква о.с. |
Т | А | К | Д | Е | Р | Ж | А | Т | Ь |
Ответ: ТАКДЕРЖАТЬ
Разложим числа и на простые множители: ;
. Обозначим буквой число , равное произведению . Найдем все его делители вида:
, где числа , , и принимают только значения 0 и 1. Тогда, как нетрудно видеть, числа и окажутся взаимно простыми. Полагая и , получим все искомые пары . В самом деле, в указанных выше условиях наибольший общий делитель такой пары равен , а ее наименьшее общее кратное равно . Таким образом, искомое число упорядоченных пар совпадает с числом всех делителей вида: , которое равно числу всех упорядоченных наборов длины 4 и состоящих только из 0 и 1. Число всех таких наборов равно , так как для каждого места в наборах существует ровно 2 варианта его значений независимо от значений на других местах. В общем случае число представляется в виде , где ,,..., - различные простые числа, а ,,..., - натуральные числа. Число всех делителей вида:
, где числа ,,..., принимают только по два значения (0 и соответствующий натуральный показатель степени в представлении числа ), равно , где - число всех простых делителей числа . Если число различных простых множителей в каноническом разложении числа равно , то число различных упорядоченных пар равно .
Ответ: 16 пар (пары и разные). В общем случае число упорядоченных пар равно , где - число всех простых делителей .
Из последней строчки легко заметить, что Ш=0. Тогда из первого столбца находим, что И=1. Затем из последнего столбца находим Ф=2. Итак,
Из средней строки ясно, что Н$" width="16" height="28" >Е. Из первого столбца находим Е=7. Из средней строки можно вычислить значения Н и З: Н=8 и З=4. Получим
Далее, последовательно вычисляем значения: А=5,Ы=9, М=6, Р=3. Расставим буквы в порядке возрастания их цифровых значений и получим текст ШИФРЗАМЕНЫ
Ответ: ШИФРЗАМЕНЫ
Ответ: например, .
Обозначим - набор , выписанный в обратном порядке.
В общем случае можно показать, что множество искомых наборов состоит из слов вида:
Next: ...к задачам второй олимпиады
Up: 7.6. Указания и решения
Previous: 7.6. Указания и решения
Contents:
К задачам пятой олимпиады
Указание. Найдите допустимые варианты для остатков от деления неизвестных и на 7. Таких вариантов будет восемь. Учитывая принадлежность неизвестных к заданному диапазону, найдите допустимые варианты для (19 вариантов). Для каждой пары найдите . В диапазон попадают только три решения: (12,16,11), (13,17,17), (13,18,12).
Так как при записывании сообщения в таблицу пробелы опускались, можно сделать вывод, что столбцы, содержащие пробел в последней клетке, до перестановки стояли в конце таблицы. Таким образом, столбцы можно разбить на две группы, как показано на рис. . При этом для получения исходного текста потребуется переставлять столбцы только внутри групп.
| Я | Н | Л | В | Р | А | Л | О | Е | Г | О | М | З | Е |
| Й | Л | Т | А | Ф | Ы | И | П | И | О | Г | Е | Б | Р |
| Ч | Р | Д | Ч | Е | С | М | О | К | И | Н | Т | К | О |
| Н | У | Л | А | Р | Е | Б | Ы | Е | И | О | Н | Ы | Д |
| Ы | Т | Д | О | М | П | П | Т | А | И | П | Т | З | Л |
| И | К | С | И | Т | Ч | Н | О | Е | Л | У | Л | Т | Ж |
| К | Е | Т | Р | И | Я |
| Л | Е | У | О | Д | О |
| И | Н | Д | Х | И | Е |
| Е | Ы | Е | З | Н | Ч |
| Е | Щ | В | Н | Я | С |
| - | - | - | - | - | - |
Естественно предположить, что сообщение оканчивалось точкой. Поэтому на третьем с конца месте в первой группе должен быть столбец, оканчивающийся на Т, на втором - на Ч, на последнем - на К. Получаем два варианта (рис. ), из которых первый является явно ``нечитаемым''.
|
Р |
А | Н | З | А | Н | Я | Л | В | Р | Л | О | Е | Г | О | М | Е | ||
| Ф | Ы | Л | Б | Ы | Л | Й | Т | А | Ф | И | П | И | О | Г | Е | Р | ||
| Е | С | Р | К | С | Р | Ч | Д | Ч | Е | М | О | К | И | Н | Т | О | ||
| Р | Е | У | Ы | Е | У | Н | Л | А | Р | Б | Ы | Е | И | О | Н | Д | ||
| М | П | Т | З | П | Т | Ы | Д | О | М | П | Т | А | И | П | Т | Л | ||
| Т | Ч | К | Т | Ч | К | И | С | И | Т | Н | О | Е | Л | У | Л | Ж | ||
|
З |
А | Н | Я | Т | И | Е | К | Р |
| Б | Ы | Л | О | У | Д | Е | Л | О |
| К | С | Р | Е | Д | И | Н | И | Х |
| Ы | Е | У | Ч | Е | Н | Ы | Е | З |
| З | П | Т | С | В | Я | Щ | Е | Н |
| Т | Ч | К | - | - | - | - | - | - |
Таким образом, удалось зафиксировать последние три столбца первой группы. Переставляя столбцы второй группы, ищем ``читаемые'' продолжения зафиксированных столбцов (рис. ). Действуя далее аналогичным образом с оставшимися столбцами первой группы, достаточно легко получаем исходное сообщение.
Ответ:
| Д | О | Л | Г | О | Е | В | Р | Е | М | Я | З | А | Н | Я | Т | И | Е | К | Р |
| И | П | Т | О | Г | Р | А | Ф | И | Е | Й | Б | Ы | Л | О | У | Д | Е | Л | О |
| М | О | Д | И | Н | О | Ч | Е | К | Т | Ч | К | С | Р | Е | Д | И | Н | И | Х |
| Б | Ы | Л | И | О | Д | А | Р | Е | Н | Н | Ы | Е | У | Ч | Е | Н | Ы | Е | З |
| П | Т | Д | И | П | Л | О | М | А | Т | Ы | З | П | Т | С | В | Я | Щ | Е | Н |
| Н | О | С | Л | У | Ж | И | Т | Е | Л | И | Т | Ч | К |
Ответ: во втором случае легче.
Ответ: 481.
Можно заметить, что последовательность букв МОСКВА входит как подпоследовательность в каждый из шифртекстов первой тройки:
й МывОт СьлКъгВц Аяя
укМапОч Ср Кщ Вз Ах
ш МфэОгчСйъКфьВыеАкк
На основе этого наблюдения можно предположить, что шифрование заключается в следующем. В каждый промежуток между буквами исходного сообщения (начало и конец также считаются промежутками) вставляются одна либо две буквы в соответствии с известным только отправителю и получателю ключом.
Очевидно, что первая буква сообщения должна попасть на 2-е или 3-е место шифрованного текста. Сравнивая буквы, стоящие на указанных местах в подлежащих расшифрованию криптограммах, делаем вывод, что одно и то же исходное сообщение соответствует первому и третьему шифртексту и что первая буква этого сообщения - П.
Рассуждая далее аналогичным образом, заключаем, что второй буквой повторяющегося сообщения является О (сопоставили ОИ из 1-й криптограммы и ИО из 3-й) и так далее. В итоге получим, что первой и третьей криптограмме соответствует исходное сообщение
Теперь расшифруем вторую криптограмму. Первой буквой сообщения могут быть только С или И. Далее, подбирая к каждой из них возможные варианты последующих букв и вычеркивая заведомо ``нечитаемые'' цепочки букв, получим:
СЕ, СМ, ИМ, ИГ
СЕГ, сео, СМО, СМР, ИМО, ИМР, ИГР, игт
сегр, сегт, СМОТ, СМОК, смрк, смрр, ИМОТ, ИМОК,
имрк, имрр, игрк, игрр
СМОТР, СМОТО, СМОКО, смокм, ИМОТР, ИМОТО, ИМОКО, имокм
СМОТРМ, СМОТРИ,
смотои, смотот, смокои, смокот, имотрм, имотри,
имотои, имотот, имокои, имокот
СМОТРИВ, СМОТРИА
СМОТРИВВ, СМОТРИВК, СМОТРИАК, СМОТРИАН и так далее.
В итоге получим исходное сообщение СМОТРИВКОРЕНЬ.
Ответ: 1,3 - ПОВТОРЕНИЕМАТЬУЧЕНИЯ
2 - СМОТРИВКОРЕНЬ
5.7. Обратив внимание на то, что некоторые символы в тексте условий задач пятой олимпиады набраны выделенным шрифтом, и выписав эти символы в порядке их следования, получаем текст:
Next: ...к задачам шестой олимпиады
Up: 7.6. Указания и решения
Previous: ...к задачам четвертой олимпиады
Contents:
К задачам седьмой олимпиады
Для того, чтобы сохранилась связь при выходе из строя любых двух узлов, необходимо, чтобы в каждый узел входило не менее трех линий связи. Ситуация
недопустима, ибо при выходе из строя узлов и узел становится недоступным. Значит, всего линий должно быть не менее
.
Вот два примера, удовлетворяющие условиям задачи с 15-ю линиями связи:
Приведем доказательство для первого примера. Если вышли из строя два узла на одном пятиугольнике, то связь сохранится через другие пятиугольники. Если вышли из строя по одному узлу на разных пятиугольниках, то связь сохранится по линиям, соединяющим эти пятиугольники.
Ответ: 15.
Процедура зашифрования может быть полностью описана квадратной таблицей . На пересечении строки с номером и столбца с номером записываем цифру, в которую при зашифровании переходит цифра , если она стоит в пароле после цифры . Из однозначности расшифрования следует, что в каждой строке каждая цифра встречается ровно один раз.
Обозначим через и зашифрованные пароли и два известных пароля в порядке, определяемом условием задачи. Процедура зашифрования сохраняет длину, поэтому и не могут соответствовать ни , ни . Предположив, что соотвествует , получим часть таблицы, в которой в одной строке две одинаковые цифры. Это означает, что предположение неверно. Составляя таблицы, убеждаемся, что не шифруется ни в , ни в , ни в . В результате таких рассуждений остается только один вариант перехода , . Заполнение таблицы будет следующим:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|
0 |
5 | |||||||||
|
1 |
3 | |||||||||
|
2 |
4 | 3 | 7 | 8 | ||||||
|
3 |
7 | |||||||||
|
4 |
2 | |||||||||
|
5 |
3 | |||||||||
|
6 |
||||||||||
|
7 |
4 | |||||||||
|
8 |
1 | 9 | ||||||||
|
9 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|
0 |
6 | 5 | ||||||||
|
1 |
3 | |||||||||
|
2 |
4 | 3 | 7 | 0 | 6 | 2 | 5 | 8 | 9 | |
|
3 |
3 | 7 | ||||||||
|
4 |
2 | |||||||||
|
5 |
3 | 7 | ||||||||
|
6 |
||||||||||
|
7 |
4 | |||||||||
|
8 |
1 | 9 | ||||||||
|
9 |
1 |
Очевидно, что в строке с номером 2 в последней клетке стоит 1. Знание этой таблицы позволяет однозначно расшифровать : получится 5830829. Пароли, соответствующие , , , , восстанавливаются не полностью.
Ответ: полностью можно расшифровать только 5393511, получится 5830829.
Сообщение состоит из буквы. Поэтому или (при и - получается нечитаемый текст). При не получается осмысленного текста при всех шести возможных вариантах перестановки букв (, ). Рассмотрим случай :
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| Б | Т | И | П | Ч | Ь | Л | О | Я | Ч | Ы | Ь | Т | О | Т | П | У |
| Н | Т | Н | О | Н | З | Л | Ж | А | Ч | О | Ь | О | Т | У | Н | И |
| У | Х | Н | И | П | П | О | Л | О | Ь | Ч | О | Е | Л | О | Л | С |
| Ч | И | Т | Ь | П | Я | Т | Ь | Ч | Т | О | Б | Ы | П | О | Л | У |
| Ч | Н | О | З | Н | А | Т | Ь | Н | У | Ж | Н | О | О | Т | Л | И |
| Ь | Н | Е | П | Л | О | Х | О | П | О | Л | У | Ч | И | Л | О | С |
Ответ:
Последовательность обхода доски показана на рисунке:
Кавалергардов век недолог
И потому так сладок он.
Труба трубит, откинут полог...
Из однородности всех членов следует, что неравенство эквивалентно неравенству 1/4$" width="181" height="33" > при условии , 0$" width="42" height="28" >, 0$" width="40" height="29" >, 0$" width="40" height="28" >.
Пусть - минимальное из чисел (. Тогда
Находим минимум квадратного трехчлена с параметром и положительным коэффициентом при . Минимум достигается в точке , при этом значение будет положительным.
Если мелом с квадратным сечением нарисовать на доске отрезок прямой так, чтобы стороны сечения были параллельны краям доски, то площадь полученной линии будет равна площади ступенчатой линии с такими же концами (см. рис. ).
Если на доске нарисовать некоторый (выпуклый) многоугольник, то найдутся такие граничные ``точки'' этого многоугольника, которые являются ближайшими к одному из краев доски. Площадь границы прямоугольника, содержащей все такие ``точки'', равна площади границы нарисованного выпуклого многоугольника (см. рис. ).
Если многоугольник со сторонами и имеет площадь 10000 см, то площадь его границы равна
Минимум достигается в случае, когда возводимое в квадрат выражение равно 0. В этом случае , что влечет . Таким образом, наименьшую площадь границы, равную 404 см, имеет квадрат со стороной 1 м.
Ответ: квадрат со стороной 1 м; площадь его границы - 404 см.
Если группа цифр, из которой образуются числа, состоит из цифр, то существует ровно различных чисел, для записи которых используются все цифры группы ровно по одному разу. Группу из цифр будем обозначать .
Поскольку в сообщении отсутствуют цифры 2 и 9, эти цифры образуют либо две группы по одной цифре, либо одну группу из двух цифр. В обоих случаях эти цифры могут быть использованы для зашифрования ровно двух букв алфавита.
Так как , то
.
Если , то из сообщения находим:
а) , , либо
б) , , .
| Случай а | Случай б | Случай а | Случай б | Случай а | Случай б | |||||
| А | 2 (4) | 0 | К | 1738 | 1738 | Х | 7183 | 7183 | ||
| Б | 4 (29) | 2 (29) | Л | 1783 | 1783 | Ц | 7318 | 7318 | ||
| В | 9 (56) | 9 (92) | М | 1837 | 1837 | Ч | 7381 | 7381 | ||
| Г | 56 (65) | 456 | Н | 1873 | 1873 | Ш | 7813 | 7813 | ||
| Д | 65 (92) | 465 | О | 3178 | 3178 | Щ | 7831 | 7831 | ||
| Е | 506 | 546 | П | 3187 | 3187 | Ъ | 8137 | 8137 | ||
| 605 | 564 | Р | 3718 | 3718 | Ы | 8173 | 8173 | |||
| Ж | 650 | 645 | С | 3781 | 3781 | Ь | 8317 | 8317 | ||
| З | 650 | 654 | Т | 3817 | 3817 | Э | 8371 | 8371 | ||
| И | 1378 | 1378 | У | 3871 | 3871 | Ю | 8713 | 8713 | ||
| Й | 1387 | 1387 | Ф | 7138 | 7138 | Я | 8731 | 8731 |
Сообщение после расшифрования имеет вид: а) ЯАЗЧ или б) ЯДАЧ, т.е. не читается.
Если , то из сообщения находим ,
. В этом случае таблица замены букв числами имеет вид:
| А | 1 | 465 | Л | 783 | С | 4560 | Ч | 5460 | Э | 6450 | |
| Б | 2(29) | Ж | 546 | М | 837 | Т | 4605 | Ш | 5604 | Ю | 6504 |
| В | 9(92) | З | 564 | Н | 873 | У | 4650 | Щ | 5640 | Я | 6540 |
| Г | 378 | И | 645 | О | 4056 | Ф | 5046 | Ъ | 6045 | ||
| Д | 387 | Й | 654 | П | 4065 | Х | 5064 | Ы | 6054 | ||
| Е | 456 | К | 738 | Р | 4506 | Ц | 5406 | Ь | 6405 | ||
Next: ...к задачам восьмой олимпиады
Up: 7.6. Указания и решения
Previous: ...к задачам шестой олимпиады
Contents:
К задачам шестой олимпиады
Так как каждый из 1997 абонентов связан ровно с другими, то общее число направлений связи равно . Отсюда общее число связанных пар абонентов равно , так как каждая связанная пара имеет ровно 2 направления связи. Поскольку число должно быть целым, а число 1997 - нечетное, то число должно быть четным.
Докажем, что для каждого существует система связи из 1997 абонентов, в которой каждый связан ровно с другими. В самом деле, расположив всех абонентов на окружности и связав каждого из них с ближайшими к нему по часовой стрелке и с ближайшими к нему против часовой стрелки, получим пример такой сети связи.
Покажем, что на диагонали присутствуют все числа от 1 до 1997. Пусть число не стоит на диагонали. Тогда, в силу симметрии таблицы, число встречается четное количество раз. С другой стороны, так как число по одному разу встречается в каждой строке, всего в таблице чисел нечетное количество (1997). Получили противоречие.
Всего на диагонали 1997 клеток, поэтому каждое число из множества
встретится на диагонали ровно по одному разу. Вычисляя сумму арифметической прогрессии, находим ответ.
Ответ: 1995003.
Ответ: ШЕСТАЯОЛИМПИАДАПОКРИПТОГРАФИИПОСВЯЩЕНАСЕМИДЕСЯТИ
ПЯТИЛЕТИЮСПЕЦИАЛЬНОЙСЛУЖБЫРОССИИ
Указание. Пусть некоторая буква при зашифровании первым способом заменялась на букву . Тогда количество повторов буквы в первой криптограмме будет равно числу повторов буквы во второй криптограмме.
а) Определим моменты остановок после начала шифрования. Для этого каждой букве русского алфавита припишем ее порядковый номер: А - 0, Б - 1, и т.д. Тогда буквам из шифруемого слова будут соответствовать номера: О - 15, Л - 12, И - 9, М - 13, П -16, А - 0, Д - 4. Моменты остановок будем указывать числом одношаговых (на один зубец) поворотов I колеса до соответствующей остановки.
| # остановки | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
Буква I колеса |
О | Л | И | М | П | И | А | Д | А |
|
Число одношаговых поворотовот начала до остановки |
15 | 45 | 75 | 79 | 82 | 108 | 132 | 136 | 165 |
|
Цифра II колеса |
5 | 5 | 5 | 1 | 8 | 2 | 8 | 4 | 5 |
|
Цифра III колеса |
1 | 2 | 5 | 2 | 5 | 3 | 6 | 3 | 4 |
К задачам шестой олимпиады
Так как каждый из 1997 абонентов связан ровно с другими, то общее число направлений связи равно . Отсюда общее число связанных пар абонентов равно , так как каждая связанная пара имеет ровно 2 направления связи. Поскольку число должно быть целым, а число 1997 - нечетное, то число должно быть четным.
Докажем, что для каждого существует система связи из 1997 абонентов, в которой каждый связан ровно с другими. В самом деле, расположив всех абонентов на окружности и связав каждого из них с ближайшими к нему по часовой стрелке и с ближайшими к нему против часовой стрелки, получим пример такой сети связи.
Покажем, что на диагонали присутствуют все числа от 1 до 1997. Пусть число не стоит на диагонали. Тогда, в силу симметрии таблицы, число встречается четное количество раз. С другой стороны, так как число по одному разу встречается в каждой строке, всего в таблице чисел нечетное количество (1997). Получили противоречие.
Всего на диагонали 1997 клеток, поэтому каждое число из множества
встретится на диагонали ровно по одному разу. Вычисляя сумму арифметической прогрессии, находим ответ.
Ответ: 1995003.
Ответ: ШЕСТАЯОЛИМПИАДАПОКРИПТОГРАФИИПОСВЯЩЕНАСЕМИДЕСЯТИ
ПЯТИЛЕТИЮСПЕЦИАЛЬНОЙСЛУЖБЫРОССИИ
Указание. Пусть некоторая буква при зашифровании первым способом заменялась на букву . Тогда количество повторов буквы в первой криптограмме будет равно числу повторов буквы во второй криптограмме.
а) Определим моменты остановок после начала шифрования. Для этого каждой букве русского алфавита припишем ее порядковый номер: А - 0, Б - 1, и т.д. Тогда буквам из шифруемого слова будут соответствовать номера: О - 15, Л - 12, И - 9, М - 13, П -16, А - 0, Д - 4. Моменты остановок будем указывать числом одношаговых (на один зубец) поворотов I колеса до соответствующей остановки.
| # остановки | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
Буква I колеса |
О | Л | И | М | П | И | А | Д | А |
|
Число одношаговых поворотовот начала до остановки |
15 | 45 | 75 | 79 | 82 | 108 | 132 | 136 | 165 |
|
Цифра II колеса |
5 | 5 | 5 | 1 | 8 | 2 | 8 | 4 | 5 |
|
Цифра III колеса |
1 | 2 | 5 | 2 | 5 | 3 | 6 | 3 | 4 |
К задачам третьей олимпиады
Если каждый из 993 абонентов связан с 99 абонентами, то для этого потребуется линий связи, которое не может быть целым числом.
Ответ: нельзя.
Несложно заметить, что рассматриваемый шифр обладает тем свойством, что при зашифровании разные буквы заменяются разными. Следовательно, при зашифровании разных слов получаются разные слова. С другой стороны, одинаковые буквы заменяются на одинаковые независимо от цикла шифрования, так как используется один и тот же ключ. Следовательно, при зашифровании одинаковых слов получаются одинаковые слова. Таким образом, число различных слов, которые можно получить в указанном процессе шифрования с начальным словом СРОЧНО, совпадает с наименьшим номером цикла шифрования, дающем это начальное слово.
Так как буква С повторяется в каждом цикле шифрования, номер которого кратен 5, а буквы Р, О, Ч, Н - в каждом цикле, номера которых кратны 13, 7, 2 и 3 соответственно, то слово СРОЧНО появится впервые в цикле с номером, равным
Ответ: 2730.
Если символы одного отрезка занумеровать последовательно числами от 1 до 12, то после передачи его из А в Б символы расположатся в порядке (2,4,6,8,10,12,1,3,5,7,9,11), а после передачи этого отрезка (замена символов не меняет порядка) из Б в В - в порядке (4,8,12,3,7,11,2,6,10,1,5,9). Переставим символы перехваченных отрезков в соответствии с их номерами до передачи из пункта А. Получим отрезки вида:
| Л | П | Г | С | Ж | Н | Ж | О | О | Б | Т | - |
| Е | С | К | Р | У | П | Д | С | Б | Х | К | Т |
| Ю | У | П | - | О | Б | Ф | Е | Б | - | П | - |
| Л | Ж | Е | С | Ж | У | О | П | Л | У | К | - |
| Щ | К | Х | С | П | Г | Б | М | Ы | О | Э | Ц |
| Л | К | Л | У | Ж | Н | - | Л | Г | Т | И | К |
Поскольку в пунктах А и Б одинаковые буквы заменялись одинаковыми, а разные - разными, то найденные отрезки можно рассматривать как замену одинаковых символов исходного текста одинаковыми, а разных - разными. Сравнивая места одинаковых букв слова КРИПТОГРАФИЯ и места одинаковых символов в отрезках, находим, что слово КРИПТОГРАФИЯ зашифровано во втором отрезке. Это дает возможность найти исходное сообщение, используя гипотезы о частых буквах русского языка и смысле исходного сообщения.
Ответ:
| С | О | В | Р | Е | М | Е | Н | Н | А | Я | - |
| К | Р | И | П | Т | О | Г | Р | А | Ф | И | Я |
| Э | Т | О | - | Н | А | У | К | А | - | О | - |
| С | Е | К | Р | Е | Т | Н | О | С | Т | И | - |
| Ш | И | Ф | Р | О | В | А | Л | Ь | Н | Ы | Х |
| С | И | С | Т | Е | М | - | С | В | Я | З | И |
делится на . Кроме того, делится на для всех 1$" width="43" height="28" >. Вместе с тем,
где каждое из слагаемых делится на 2 (так как содержит произведение ) и делится на 5 (поскольку первое слагаемое есть произведение пяти последовательных чисел, а второе содержит множитель 5). Следовательно, делится на 10. Число
делится на 10, так как каждое из слагаемых делится на 10.
Проверим, что 20 является наименьшим периодом. Выписывая первые 20 значений последовательности , , ...
легко убедиться, что она не имеет периода меньшей длины.
Для того, чтобы найти исходное сообщение, найдем сначала цифровое сообщение, полученное из него с помощью таблицы замены. Согласно этой таблице на нечетных местах цифрового образа исходного сообщения могут быть только цифры 0, 1, 2 и 3. Последовательно рассматривая эти значения для каждого нечетного места цифрового сообщения с использованием соответствующей цифры шифрованного сообщения, найдем соответствующие варианты значений цифр шифрующего отрезка. Для этого вычислим остатки от деления разностей цифр шифрованного и варианта цифрового сообщений:
| порядковый номер места | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 |
| шифрованное сообщение | 2 | 3 | 8 | 7 | 1 | 4 | 8 | 6 | 6 | 0 | 1 | 3 | 5 | 8 |
| вариант 0 для | 2 | 3 | 8 | 7 | 1 | 4 | 8 | 6 | 6 | 0 | 1 | 3 | 5 | 8 |
| вариант 1 для | 1 | 2 | 7 | 6 | 0 | 3 | 7 | 5 | 5 | 9 | 0 | 2 | 4 | 7 |
| вариант 2 для | 0 | 1 | 6 | 5 | 9 | 2 | 6 | 4 | 4 | 8 | 9 | 1 | 3 | 6 |
| вариант 3 для | 9 | 0 | 5 | 4 | 8 | 1 | 5 | 3 | 3 | 7 | 8 | 0 | 2 | 5 |
По задаче 3. 4 последовательность, из которой выбран шифрующий отрезок, является периодической с периодом 20. Из таблицы вариантов значений цифр шифрующего отрезка видим, что 5-я его цифра может быть равна 5, 6, 7 или 8, а его 25-я цифра - 2, 3, 4 или 5. Отсюда получаем, что . На периоде последовательности, из которой выбран шифрующий отрезок, есть две цифры 5: и . Поэтому рассмотрим два случая. Если
, то . Это противоречит таблице вариантов значений цифр шифрующего отрезка, в которой может быть равна 4, 5, 6 или 7. Если же , то соответствующий шифрующий отрезок: 1636567490147656369016365674 хорошо согласуется с таблицей вариантов значений его цифр. Вычитая цифры найденного отрезка из соответствующих цифр шифрованного сообщения и заменяя разности их остатками от деления на 10, получим по таблице замены пар цифр на буквы исходное сообщение:
| шифрованное сообщение | 23 | 39 | 86 | 72 | 16 | 45 | 81 | 60 | 67 | 06 | 17 | 31 | 55 | 88 |
| шифрующийотрезок | 16 | 36 | 56 | 74 | 90 | 14 | 76 | 56 | 36 | 90 | 16 | 36 | 56 | 74 |
| цифровоесообщение | 17 | 03 | 30 | 08 | 26 | 31 | 15 | 14 | 31 | 16 | 01 | 05 | 09 | 14 |
| исходноесообщение | С | В | Я | З | Ь | - | П | О | - | Р | А | Д | И | О |
Обозначения понятны из рис. .
1) центрально симметричен относительно .
2) центрально симметричен относительно .
3) (параллельный перенос).
4) - квадрат.
5) , .
6) (, , ).
7) Без ограничения общности .
8) , , ,
.
9) (, , ) .
10) .
11) Площадь равна площади ,
.
12) (половина высоты ).
13) .
14) (теорема Пифагора), т.е.
15)
Замечание. Точки и можно построить с помощью циркуля и линейки. Подумайте, как это можно сделать.
Ответ: .
Next: ...к задачам четвертой олимпиады
Up: 7.6. Указания и решения
Previous: ...к задачам второй олимпиады
Contents:
К задачам восьмой олимпиады
Проведем прямые, проходящие через точки пересечения границ сложенной ленты параллельно ее краям. Очевидно, что тогда лента разобьется на равные равносторонние треугольники. Отметим цифрой 0 все просветы, а цифрой 2 все треугольники, которые получились наложением друг на друга двух треугольников в сложенной ленте. Построим дополнительно ряд треугольников вне эмблемы, как показано на рисунке . В полученной фигуре число треугольников, отмеченных цифрой 2, равно числу треугольников, отмеченных цифрой 0. Поэтому площадь всей ленты равна площади трапеции . Количества треугольников в горизонтальных рядах являются 9 последовательными членами арифметической прогрессии с первым членом, равным 3 (нижний ряд), и разностью 2. Следовательно, общее число треугольников равно
Если - ширина ленты, то площадь одного равностороннего треугольника с высотой равна
С другой стороны, если длина прямоугольника, полученного послеразрезания ленты, равна , то . Отсюда находим искомую величину: .
Ответ: .
Последовательность из нулей или единиц обозначим соответственно через или . Тогда шифрование каждого знака сообщения состоит в замене
|
(1) |
В зашифрованном сообщении все серии из единиц имеют длину для первого способа и длину для второго способа, поэтому, для совпадения результатов зашифрования необходимо, чтобы
|
(2) |
Теперь легко получить, что в сообщении должно быть одинаковое число нулей и единиц.
Пусть - число нулей в сообщении. Тогда число нулей в зашифрованном I способом сообщении равно , а II способом - . Таким образом,
|
(3) |
Из () видно, что сообщение должно начинаться с нуля и оканчиваться единицей. Пусть перед первой единицей сообщения расположено нулей. Тогда первые знаков сообщения представляются при шифровании в виде:
|
(4) |
При получаем необходимость равенства , а значит, с учетом () - равенства .
При 1$" width="42" height="28" > получаем условия:
Подставляя в (), получаем равенство , которое при натуральных , и возможно лишь в случае . Следовательно, , а значит, с учетом () .
Таким образом, при 1$" width="42" height="28" > необходимы условия , , где - натуральное. Из () следует, что сообщение должно иметь вид , где число нулей и число единиц равно .
Ответ: При , , сообщения вида шифруются одинаково.
При , , где - натуральное, сообщения вида
(группы из нулей и единиц) шифруются одинаково.
Примечание. Первый ответ не является частным случаем второго при .
Естественно предположить, что все члены оргкомитета родились в ХХ веке. Отсюда сразу замечаем, что на 3, 7, 11, 15, 19 и 23 местах последовательности простых чисел расположены числа 11, 17, 47, 53, 83 и 89 соответственно.
Выясним, какие числа являются соседними с указанными шестью числами. Для этого составим таблицу их возможных ``соседей''. В соответствии с условием имеем:
| число | соседи |
| 11 | 13, 19, 43, 7, 3 |
| 17 | 13, 19 |
| 47 | 79, 43, 31 |
| 53 | 61, 37 |
| 83 | 79, 67, 19 |
| 89 | 97, 73. |
| 15 | 02 | 20 | 45 | 42 | 13 | 26 | 67 | 44 | 30 | 56 | 82 | 53 | 33 | 62 | 32 | 73 | 63 | 92 | 49 | 75 | 70 | 98 | 49 | ||
| 19 | 19 | 19 | 19 | 19 | 19 | ||||||||||||||||||||
| 11 | 17 | 31 | 47 | 37 | 53 | 61 | 67 | 83 | 73 | 89 | 97 | ||||||||||||||
| 03 | 03 | 13 | 13 | 43 | 19 | ||||||||||||||||||||
| 07 | 07 | 19 | 19 | 79 | 79 | ||||||||||||||||||||
| 13 | |||||||||||||||||||||||||
| 19 | |||||||||||||||||||||||||
| 43 |
где в первой строке расположено шифрованное сообщение, во второй строке - известные участки исходного сообщения, в третьей строке - ставшие известными участки ключевой последовательности, в остальных строках - возможные варианты ключевой последовательности в соответствующих позициях. При составлении таблицы учитывалось, что каждое число должно встретиться ровно один раз. Позиции чисел 31, 37, 67, 73 определяются однозначно. Их расположение однозначно определяет места для простых чисел 61 и 97.
Снова выпишем известные числа последовательности простых чисел и варианты для их соседей (первые две строки таблицы на этом шаге не понадобятся):
| 11 | 17 | 31 | 37 | 67 | 73 | ||||||||||||||||||||
| 03 | 03 | 13 | 13 | 43 | 19 | ||||||||||||||||||||
| 07 | 07 | 19 | 19 | 79 | 79 | ||||||||||||||||||||
| 13 | |||||||||||||||||||||||||
| 19 | |||||||||||||||||||||||||
| 43 |
| 11 | 17 | 31 | |||||||||||||||||||||||
| 03 | 03 | 13 | 13 | 29 | |||||||||||||||||||||
| 07 | 07 | 19 | 19 | 23 | |||||||||||||||||||||
| 13 | |||||||||||||||||||||||||
| 19 |
Участок последовательности имеет только два варианта доопределения: (а) и (б) . Рассмотрим оба случая.
а) Выпишем фрагмент таблицы для первого случая:
| 11 | 13 | ||||||||||
| 03 | 03 | ||||||||||
| 07 | 07 |
б) Выпишем фрагмент таблицы для второго случая:
| 05 | 11 | 23 | |||||||||
| 03 | 03 | ||||||||||
| 07 | 07 |
Таким образом, приходим к выводу, что возможен всего один вариант ключевой последовательности. Получим окончательный вариант таблицы и найдем ответ:
| 15 | 02 | 20 | 45 | 42 | 13 | 26 | 67 | 44 | 30 | 56 | 82 | 53 | 33 | 62 | 32 | 73 | 63 | 92 | 49 | 75 | 70 | 98 | 49 | ||
| 10 | 09 | 19 | 48 | 29 | 04 | 19 | 54 | 25 | 09 | 19 | 49 | 12 | 06 | 19 | 71 | 24 | 06 | 19 | 70 | 04 | 07 | 19 | 52 | ||
| 05 | 03 | 11 | 07 | 23 | 19 | 17 | 13 | 29 | 31 | 47 | 43 | 41 | 37 | 53 | 61 | 59 | 67 | 83 | 79 | 71 | 73 | 89 | 97 |
Занумеруем горизонтали и вертикали квадрата натуральными числами от 1 до 13 сверху вниз и слева направо соответственно. Тогда каждая клетка квадрата однозначно определяется парой чисел , где - номер горизонтали, а - номер вертикали, в которых находится клетка.
Расстояние между центром клетки и центром клетки равно . Заметим, что и . Обозначим , , . Тогда - число натуральное, если . Отсюда получаем, что
В общем случае, если , то
Ясно, что и должны быть одинаковой четности. По условию, , поэтому искомыми решениями будут только пары
Клетку назовем существенной для клетки , если выполнено условие . Ясно, что цвет данной клетки менялся лишь тогда, когда Криптоша находился в какой-либо существенной для нее клетке. А так как в каждой клетке Криптоша побывал ровно 1999 раз (нечетное число), то цвет данной клетки изменился, если общее число существенных для нее клеток нечетно.
Для определения четности числа всех существенных клеток для данной клетки воспользуемся тем, что у симметричных клеток относительно той или иной диагонали квадрата или относительно центрального вертикального или центрального горизонтального рядов эти числа будут одинаковы. Это, в частности, означает, что достаточно определить указанную четность только для клеток , где , (этих клеток 15, занумеруем их, как показано на рис. ).
Зоной асимметрии для той или иной клетки мы назовем множество тех клеток, которые в пределах исходного квадрата не имеют клеток, симметричных относительно вертикального, горизонтального и правого диагональных рядов, содержащих данную клетку. Ясно, что для данной клетки число существенных клеток, не лежащих в ее зоне асимметрии, четно.
На рис. показана зона асимметрии для клетки 1, а также все клетки верхнего левого угла , меняющие свой цвет.
Ответ на рис. .
1. Пусть , . Уравнение имеет вид
, то есть - любое число.
2. Пусть , . Уравнение имеет вид
, или , то есть не имеет решений.
3. Аналогично, при , нет решений.
4. При , удобно рассмотреть три случая: а) , b) , c) .
a) :
, ,
- любое, кроме .
b) :
, ,
, , решений нет.
c) :
Ответ. При - любое число.
При
.
При или или решений нет.
При
.
Число представляет собой сумму кубов, сумму пятых степеней, а также из него можно выделить полный квадрат. Каждое из этих представлений позволяет найти некоторые делители исходного числа:
Таким образом, установлено, что среди простых делителей числа содержатся 41, 13, 5. Непосредственной проверкой получаем равенство
.
Осталось проверить, что 1321 - простое число. Для этого достаточно показать, что 1321 не делится ни на одно простое число, меньшее 37 (, 1321$" width="89" height="28" >).
Ответ: .
Next: ...к задачам девятой олимпиады
Up: 7.6. Указания и решения
Previous: ...к задачам седьмой олимпиады
Contents:
К задачам второй олимпиады
Рассмотрим один виток ленты на развертке цилиндра (разрез по горизонтальной линии). По условию высота , опущенная на сторону , равна . Угол равен . Отсюда равно . Так как высота строки равна , то всего на одном витке букв.
Ответ: чтобы прочитать текст, надо разрезать ленту на участки по букв и сложить их рядом.
Согласно условию, исходное сообщение состоит из двух пятерок цифр: и . Пусть - последние две цифры суммы чисел, изображенных этими пятерками. Через обозначим последнюю цифру суммы чисел и . Пусть обозначает цифру переноса (цифру десятков) суммы . По условию имеем, что и .
Пусть - первый член, а - разность арифметической прогрессии, которую коммерсант использовал при шифровании. Тогда из условия получаем:
Обозначим символом равенство остатков от деления на 10 чисел и . Тогда записи и имеют одинаковый смысл. Если и , то , . Bсегда , так как остаток от деления единствен.
Из соотношений (), (), () и () находим соответственно:
Подставляя эти значения в равенства () и (), получим следующие равенства: и . Отсюда следует, что
Подставив из () и из () в (), (),(), (), (), (), (), (), (), (), найдем выражения для цифр исходного сообщения:
Найденные выражения дают два варианта исходных сообщений:
4470416411 (при ), 2371640978 (при ).
Ответ: - любое, - не должно делиться на 2 и на 5.
Указание. Обозначим через - остаток от деления значения многочлена на 10. Для однозначного расшифрования необходимо и достаточно, чтобы разным значениям соответствовали разные значения . Поэтому , , ..., принимают все значения от 0 до 9. Найдем эти значения:
где - остаток от деления числа на 10.
Отсюда, пользуясь свойствами остатков, замечаем, что должно быть нечетным (иначе будут только четные числа) и не должно делиться на 5 (иначе будут только 0 и 5). Непосредственной проверкой можно убедиться, что при любом и при всех , удовлетворяющим приведенным условиям, гарантируется однозначность расшифрования.
Обозначим через остаток от деления на 26 суммы чисел, которые соответствуют первым буквам алфавита ( ) .
Если среди чисел
есть нуль: , то искомой ключевой комбинацией является цепочка первых букв алфавита.
Если среди чисел
нет нуля, то обязательно найдутся два одинаковых числа: (считаем, что -й и заканчивающийся -й буквой.
Если две буквы с порядковыми номерами и зашифрованы в буквы с порядковыми номерами и с помощью одной и той же буквы, то остатки от деления чисел и на 30 равны между собой и совпадают с порядковым номером шифрующей буквы (порядковым номером буквы удобно считать число 0). Тогда, с учетом соглашения о порядковом номере буквы , справедливо, что равен остатку от деления числа
на 30, а, вместе с тем, равен остатку от деления числа
на 30. Если каждое из выражений в скобках заменить соответствующим остатком от деления на 30, то упомянутая связь не нарушится.
Представим в виде набора порядковых номеров известные шифрованные сообщения (обозначим их соответственно ш. с. 1 и ш. с. 2) и слово КОРАБЛИ:
| слово | К | О | Р | А | Б | Л | И |
| 10 | 14 | 16 | 1 | 2 | 11 | 9 |
| ш.с.1 | Ю | П | Т | Ц | А | Р | Г | Ш | А | Л | Ж | Ж | Е | В | Ц | Щ | Ы | Р | В | У | У |
| 29 | 15 | 18 | 22 | 1 | 16 | 4 | 24 | 1 | 11 | 7 | 7 | 6 | 3 | 22 | 25 | 27 | 16 | 3 | 19 | 19 |
| ш.с.2 | Ю | П | Я | Т | Б | Н | Щ | М | С | Д | Т | Л | Ж | Г | П | С | Г | Х | С | Ц | Ц |
| 29 | 15 | 0 | 18 | 2 | 13 | 25 | 12 | 17 | 5 | 18 | 11 | 7 | 4 | 15 | 17 | 4 | 21 | 17 | 22 | 22 |
Вначале для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 1 найдем соответствующий участок и. с. 2. Имеем:
| 0 | 0 | 12 | 26 | 1 | 27 | 21 | 18 | 16 | 24 | 11 | 4 | 1 | 1 | 23 | 22 | 7 | 5 | 14 | 3 | 3 |
| 10 | 14 | 16 | 1 | 2 | 11 | 9 | |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| 10 | 10 | 22 | 6 | 11 | 7 | 1 | 28 | 26 | 4 | 21 | 14 | 11 | 11 | 3 | |
| 14 | 26 | 10 | 15 | 11 | 5 | 2 | 0 | 8 | 25 | 18 | 15 | 15 | 7 | 6 | |
| 28 | 12 | 17 | 13 | 7 | 4 | 2 | 10 | 27 | 20 | 17 | 17 | 9 | 8 | 23 | |
| 27 | 2 | 28 | 22 | 19 | 17 | 25 | 12 | 5 | 2 | 2 | 24 | 23 | 8 | 6 | |
| 3 | 29 | 23 | 20 | 18 | 26 | 13 | 6 | 3 | 3 | 25 | 24 | 9 | 7 | 16 | |
| 28 | 2 | 29 | 27 | 5 | 22 | 15 | 12 | 12 | 4 | 3 | 18 | 16 | 25 | 14 | |
| 0 | 27 | 25 | 3 | 20 | 13 | 10 | 10 | 2 | 1 | 16 | 14 | 23 | 12 | 12 |
Теперь для каждого из 15 вариантов расположения слова КОРАБЛИ в и. с. 2 найдем соответствующий участок и. с. 1. Имеем:
| 0 | 0 | 18 | 4 | 29 | 3 | 9 | 12 | 14 | 6 | 19 | 26 | 29 | 29 | 7 | 8 | 23 | 25 | 16 | 27 | 27 |
| 10 | 14 | 16 | 1 | 2 | 11 | 9 | |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| 10 | 10 | 28 | 14 | 9 | 13 | 19 | 22 | 24 | 16 | 29 | 6 | 9 | 9 | 17 | |
| 14 | 2 | 18 | 13 | 17 | 23 | 26 | 28 | 20 | 3 | 10 | 13 | 13 | 21 | 22 | |
| 4 | 20 | 15 | 19 | 25 | 28 | 0 | 22 | 5 | 12 | 15 | 15 | 23 | 24 | 9 | |
| 5 | 0 | 4 | 10 | 13 | 15 | 7 | 20 | 27 | 0 | 0 | 8 | 9 | 24 | 26 | |
| 1 | 5 | 11 | 14 | 16 | 8 | 21 | 28 | 1 | 1 | 9 | 10 | 25 | 27 | 18 | |
| 14 | 20 | 23 | 25 | 17 | 0 | 7 | 10 | 10 | 18 | 19 | 4 | 6 | 27 | 8 | |
| 18 | 21 | 23 | 15 | 28 | 5 | 8 | 8 | 16 | 17 | 2 | 4 | 25 | 6 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| К | К | Ц | Е | Л | Ж | А | Э | Ь | Г | Х | О | Л | Л | В | |
| О | Ь | К | П | Л | Д | Б | Я | З | Щ | Т | П | П | Ж | Е | |
| участок | Э | М | С | Н | Ж | Г | Б | К | Ы | Ф | С | С | И | З | Ч |
| и.с.2 | Ы | Б | Э | Ц | У | С | Щ | М | Д | Б | Б | Ш | Ч | З | Е |
| В | Ю | Ч | Ф | Т | Ь | Н | Е | В | В | Щ | Ш | И | Ж | Р | |
| Э | Б | Ю | Ы | Д | Ц | П | М | М | Г | В | Т | Р | Щ | О | |
| Я | Ы | Щ | В | Ф | Н | К | К | Б | А | Р | О | Ч | М | М |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| К | К | Э | О | И | Н | У | Ц | Ш | Р | Ю | Е | И | И | С | |
| О | Б | Т | Н | С | Ч | Ь | Э | Ф | В | К | Н | Н | Х | Ц | |
| участок | Г | Ф | П | У | Щ | Э | Я | Ц | Д | М | П | П | Ч | Ш | И |
| и.с.1 | Д | Я | Г | К | Н | П | Ж | Ф | Ы | Я | Я | З | И | Ш | Ь |
| А | Д | Л | О | Р | З | Х | Э | А | А | И | К | Щ | Ы | Т | |
| О | Ф | Ч | Щ | С | Я | Ж | К | К | Т | У | Г | Е | Ы | З | |
| Т | Х | Ч | П | Э | Д | З | З | Р | С | Б | Г | Щ | Е | Е |
| и.с.1 | = | К | О | Г | Д | А | О | Т | . | . | . | . | . | . | . | К | О | Р | А | Б | Л | И |
| и.с.2 | = | К | О | Р | А | Б | Л | И | . | . | . | . | . | . | . | В | Е | Ч | Е | Р | О | М |
Каждую букву шифрованного сообщения расшифруем в трех вариантах, предполагая последовательно, что соответствующая буква шифрующей последовательности есть буква А, Б или буква В:
| шифрованное сообщение | Р | Б | Ь | Н | П | Т | С | И | Т | С | Р | Р | Е | З | О | Х |
| вариант А | П | А | Щ | М | О | С | Р | З | С | Р | П | П | Д | Ж | Н | Ф |
| вариант Б | О | Я | Ш | Л | Н | Р | П | Ж | Р | П | О | О | Г | Е | М | У |
| вариант В | Н | Ю | Ч | К | М | П | О | Е | П | О | Н | Н | В | Д | Л | Т |
Замечание. Из полученной таблицы можно было найти такое исходное сообщение как
которое представляется не менее осмысленным, чем приведенное выше. А если предположить одно искажение в шифрованном сообщении (скажем, в качестве 11-й буквы была бы принята не буква Р, а буква П), то, наряду с правильным вариантом, можно получить и такой:
| НАШ МОРОЗ ПОМОГ ЕМУ |
Next: ...к задачам третьей олимпиады
Up: 7.6. Указания и решения
Previous: ...к задачам первой олимпиады
Contents:
Как отличить составное число от простого
Существует довольно эффективный способ убедиться, что заданное число является составным, не разлагая это число на множители. Согласно малой теореме Ферма, если число простое, то для любого целого , не делящегося на , выполняется сравнение
|
(9) |
Если же при каком-то это сравнение нарушается, можно утверждать, что - составное. Проверка () не требует больших вычислений, это следует из алгоритма 1. Вопрос только в том, как найти для составного целое число , не удовлетворяющее (). Можно, например, пытаться найти необходимое число , испытывая все целые числа подряд, начиная с 2. Или попробовать выбирать эти числа случайным образом на отрезке
К сожалению, такой подход не всегда дает то, что хотелось бы. Имеются составные числа , обладающие свойством () для любого целого с условием . Такие числа называются числами Кармайкла. Рассмотрим, например, число . Так как делится на каждое из чисел , , , то с помощью малой теоремы Ферма легко проверить, что есть число Кармайкла. Можно доказать (Carmichael, 1912), что любое из чисел Кармайкла имеет вид
, , где все простые различны, причем делится на каждую разность . Лишь недавно, см. [], была решена проблема о бесконечности множества таких чисел.
В 1976 г. Миллер предложил заменить проверку () проверкой несколько иного условия. Детали последующего изложения можно найти в []. Если - простое число, , где нечетно, то согласно малой теореме Ферма для каждого с условием хотя бы одна из скобок в произведении
делится на . Обращение этого свойства можно использовать, чтобы отличать составные числа от простых.
Пусть - нечетное составное число, , где нечетно. Назовем целое число , , если нарушается одно из двух условий:
) не делится на ;
) или существует целое ,
Из сказанного ранее следует, что для простого числа не существует хороших чисел . Если же составное число, то, как доказал Рабин, их существует не менее
.
Теперь можно построить вероятностный алгоритм, отличающий составные числа от простых.
Next: 4.5. Как строить большие
Up: 4. Алгоритмические проблемы теории
Previous: 4.3. Сложность теоретико-числовых алгоритмов
Contents:
Как проверить большое число на простоту
Есть некоторое отличие в постановках задач предыдущего и настоящего разделов. Когда мы строим простое число , мы обладаем некоторой дополнительной информацией о нем, возникающей в процессе построения. Например, такой информацией является знание простых делителей числа . Эта информация иногда облегчает доказательство простоты .
В этом разделе мы предполагаем лишь, что нам задано некоторое число , например, выбранное случайным образом на каком-то промежутке, и требуется установить его простоту, или доказать, что оно является составным. Эту задачу за полиномиальное количество операций решает указанный в разделе алгоритм Миллера. Однако, справедливость полученного с его помощью утверждения зависит от недоказанной . Если число выдержало испытания для 100 различных значений параметра , то, по-видимому, можно утверждать, что оно является простым с вероятностью большей, чем . Эта вероятность очень близка к единице, однако все же оставляет некоторую тень сомнения на простоте числа . В дальнейшем в этом разделе мы будем считать, что заданное число является простым, а нам требуется лишь доказать это.
В настоящее время известны детерминированные алгоритмы различной сложности для доказательства простоты чисел. Мы остановимся подробнее на одном из них, предложенном в 1983 г. в совместной работе Адлемана, Померанца и Рамели []. Для доказательства простоты или непростоты числа этот алгоритм требует арифметических операций. Здесь - некоторая положительная абсолютная постоянная. Функция хоть и медленно, но все же возрастает с ростом , поэтому алгоритм не является полиномиальным. Но все же его практические реализации позволяют достаточно быстро тестировать числа на простоту. Существенные усовершенствования и упрощения в первоначальный вариант алгоритма были внесены в работах Х.Ленстры и А.Коена [,]. Мы будем называть описываемый ниже алгоритм алгоритмом Адлемана - Ленстры.
В основе алгоритма лежит использование сравнений типа малой теоремы Ферма, но в кольцах целых чисел круговых полей, т.е. полей, порожденных над полем числами - корнями из . Пусть - простое нечетное число и - первообразный корень по модулю , т.е. образующий элемент мультипликативной группы поля , которая циклична. Для каждого целого числа , не делящегося на , можно определить его индекс, , называемый также дискретным логарифмом, с помощью сравнения . Рассмотрим далее два простых числа с условием, что делится на , но не делится на .
Следующая функция, определенная на множестве целых чисел,
является характером по модулю и порядок этого характера равен . Сумма
называется суммой Гаусса. Формулируемая ниже теорема 3 представляет собой аналог малой теоремы Ферма, используемый в алгоритме Адлемана - Ленстры.
Теорема 5. Пусть - нечетное простое число, . Тогда в кольце
выполняется сравнение
Если при каких-либо числах сравнение из теоремы 3 нарушается, можно утверждать, что составное число. В противном случае, если сравнение выполняется, оно дает некоторую информацию о возможных простых делителях числа . Собрав такую информацию для различных , в конце концов удается установить, что имеет лишь один простой делитель и является простым.
В случае легко проверить, что сравнение из теоремы 3 равносильно хорошо известному в элементарной теории чисел сравнению
| (13) |
Пример 1. (Х. Ленстра). Пусть - натуральное число, , для которого выполнены сравнения
| (14) |
| (15) |
Докажем, что из выполнимости (14-15) следует, что каждый делитель числа удовлетворяет одному из сравнений
| (16) |
означающие (в силу того, что символ Якоби может равняться лишь или ), что
При k$" width="48" height="29" > это равенство означает, что при , и, следовательно,
. Если же , то имеем и . Этим () доказано.
Информация такого рода получается и в случае произвольных простых чисел и с указанными выше свойствами.
Опишем (очень грубо) схему алгоритма Адлемана - Ленстры для проверки простоты :
1) выбираются различные простые числа и различные простые нечетные такие, что
а) для каждого все простые делители числа содержатся
среди и не делятся на квадрат простого числа,
б) \sqrt{N} $" width="163" height="37" >;
2) для каждой пары выбранных чисел , проводятся тесты, подобные сравнению из теоремы 3. Если не удовлетворяет какому-либо из этих тестов - оно составное. В противном случае
3) определяется не очень большое множество чисел, с которыми только и могут быть сравнимы простые делители . А именно, каждый простой делитель числа должен удовлетворять сравнению вида
4) проверяется, содержит ли найденное множество делители . Если при этом делители не обнаружены, утверждается, что - простое число.
Если число составное, оно обязательно имеет простой делитель , меньший
Пример 2.
Если выбрать следующие множества простых чисел
то таким способом удается проверять простоту чисел
Отметим, что в работе [] для тестирования использовались не сравнения теоремы 3, а закон взаимности для степенных вычетов и так называемые суммы Якоби. Сумма Якоби
определяется для двух характеров по модулю . Если характеры имеют порядок , то соответствующая сумма Якоби принадлежит кольцу . Поскольку числа , участвующие в алгоритме, сравнительно невелики, то вычисления с суммами Якоби производятся в полях существенно меньшей степени, чем вычисления с суммами Гаусса. Это главная причина, по которой суммы Якоби предпочтительнее для вычислений. При выполняется классическое соотношение
связывающее суммы Гаусса с суммами Якоби и позволяющее переписать сравнение теоремы 3 в терминах сумм Якоби (см. []). Так, при и соответствующее сравнение, справедливое для простых , отличных от 2, 3, 7, принимает вид
где и - некоторый корень кубический из 1.
В 1984 г. в работе [] было внесено существенное усовершенствование в алгоритм, позволившее освободиться от требования неделимости чисел на квадраты простых чисел. В результате, например, выбрав число
и взяв равным произведению простых чисел с условием, что делится на , получим 1{,}5\cdot10^{52} $" width="97" height="33" >, что позволяет доказывать простоту чисел , записываемых сотней десятичных знаков. При этом вычисления будут проводиться в полях, порожденных корнями из 1 степеней 16, 9, 5 и 7.
Мой персональный компьютер с процессором Pentium-150, пользуясь реализацией этого алгоритма на языке UBASIC, доказал простоту записываемого 65 десятичными знаками, большего из простых чисел в примере Ривеста, Шамира и Адлемана (см. раздел ) за 8 секунд. Сравнение этих 8 секунд и 17 лет, потребовавшихся для разложения на множители предложенного в примере числа, конечно, впечатляет.
Отметим, что оценка сложности этого алгоритма представляет собой трудную задачу аналитической теории чисел. Как уже указывалось, количество операций оценивается величиной . Однако соответствующие числа и , возникающие в процессе доказательства, не могут быть явно указаны в зависимости от . Доказано лишь существование чисел и , для которых достигается оценка. Впрочем, есть вероятностный вариант алгоритма, доказывающий простоту простого числа c вероятностью большей за
арифметических операций. А в предположении эта оценка сложности может быть получена при эффективно указанных и .
Next: 4.7. Как раскладывают составные
Up: 4. Алгоритмические проблемы теории
Previous: 4.5. Как строить большие
Contents:
Как проверять правильность ключа?
Кстати, а как программа при расшифровании файла определяет, что пароль неправильный? По-разному. Некоторые программы вообще не проверяют правильность пароля. В этом случае, если вы ввели неправильный пароль, файл как бы расшифруется, но вы увидите совсем не то, что зашифровали. Это неудобно. Предположим, вы зашифровали файл мегабайт в 50 с помощью алгоритма ГОСТ. Сколько времени он будет расшифроваться? Если у вас дома стоит обычный Pentium, то, по крайней мере, минуту. А скорее всего, минуты три. Вы все это время сидите, ждете, а потом оказывается, что зря ждали - пароль-то ввели неправильный. А если вы exe-файл неправильно расшифровали, а потом запустили на выполнение? Скорее всего, придется давить Reset. Так что лучше, когда перед расшифрованием программа проверяет правильность пароля.
Остается вопрос: как проверять правильность пароля? Можно просто вписать пароль в начало зашифрованного файла перед шифртекстом. При расшифровании вы вводите пароль, программа читает начало зашифрованного файла и сравнивает то, что вы ввели, и то, что в файле. Если совпало, значит, пароль правильный. А если не совпало - неправильный. Просто и удобно. Только что произойдет, если кто-нибудь другой случайно просмотрит зашифрованный файл, например, с помощью Norton Commander? Весь файл - сплошная абракадабра, а в начале файла - осмысленное слово. Не нужно быть семи пядей во лбу, чтобы догадаться, что это и есть пароль. Так что нужно придумывать что-то другое.
Очевидно, эталон пароля, который хранится в зашифрованном файле, тоже надо зашифровать. Только как? Проще всего шифровать пароль по той же схеме, что и текст исходного файла. Если шифр стойкий (а иначе его и не стоит использовать), пароль будет закрыт надежно. А что брать в качестве ключа? Можно взять константу. Тогда в каждом зашифрованном файле эталон пароля будет зашифрован на одном и том же ключе. Так, например, делает встроенная система шифрования файлов электронной почты Sprint Mail. Только там зашифрованный пароль хранится не в начале зашифрованного файла, а в конце. Но что будет, если кто-то узнает ключ, на котором шифруются все пароли? Он сможет расшифровывать все файлы, которые вы зашифруете. И не важно, что пароли разные - злоумышленник возьмет нужный пароль прямо из файла, который хочет прочесть.
Вы, скорее всего, подумали: а откуда злоумышленник узнает ключ, на котором шифруются эталоны паролей? Этот ключ встроен в программу шифрования, его никто не знает, даже вы его не знаете. Тем не менее, если злоумышленник достаточно квалифицирован, если он умеет пользоваться дизассемблером и отладчиком, этот ключ он узнает без труда. Обычно на решение такой задачи уходит всего несколько часов. Как это можно сделать - тема отдельной статьи. Пока поверьте на слово - имея только exe-файл, определенные навыки и много свободного времени, можно разобраться в том, что делает программа, до мельчайших подробностей.
Лучше шифровать эталон пароля сам на себе. Взять пароль в качестве открытого текста и взять тот же пароль в качестве ключа. При расшифровании файла, когда вы вводите пароль, программа пытается расшифровать только начало файла. Если в результате получилась строка, совпадающая с паролем, значит, пароль правильный, и можно расшифровывать файл дальше. А если получилось что-то другое, значит, пароль неправильный.
Некоторые программы шифрования шифруют пароли иначе. Берется какая-то строка, всегда одна и та же, шифруется на пароле и записывается в зашифрованный файл. Diskreet, например, шифрует на пароле строку ``ABCDEFGHENRIXYZ'' (эта строка завершается нулевым байтом, как принято в языке C). Когда Diskreet проверяет пароль, он берет начало зашифрованного файла (точнее, байты с 16-го по 31-й) и расшифровывает их на пароле, который ввел пользователь. Если после расшифрования получилось ``ABCDEFGHENRIXYZ'' - пароль правильный, если не получилось - неправильный.
На первый взгляд кажется, что эта схема хуже, чем предыдущая. Действительно, в предыдущем случае злоумышленнику неизвестны ни открытый текст, ни ключ, а в последнем случае неизвестен только ключ, а открытый текст известен. Но если вы еще помните, что было написано в начале этой главы, то, наверное, уже поняли, что последняя схема ничуть не слабее предыдущей. Если шифр стойкий, то ключ
невозможно получить за приемлемое время, даже если известны и открытый текст, и шифртекст.
Next: Какой должен быть пароль?
Up: 6.3. Как зашифровать файл?
Previous: Как вводить ключ?
Contents:
Как раскладывают составные числа на множители
Мы лишь кратко коснемся этой темы, отсылая читателей к книгам [,,]. Среди многих алгоритмов разложения мы выберем ту линию развития, которая привела к разложению числа, предложенного RSA.
Поиском эффективных способов разложения целых чисел на множители занимаются уже очень давно. Эта задача интересовала выдающихся ученых в области теории чисел. Вероятно Ферма был первый, кто предложил представить разлагаемое число в виде разности квадратов , а затем, вычисляя , попытаться найти нетривиальный делитель . Он же предложил и способ, позволяющий найти требуемое представление. Если разлагаемое число имеет два не очень отличающиеся по величине множителя, этот способ позволяет определить их быстрее, чем простой перебор делителей. Лежандр обратил внимание на то, что при таком подходе достаточно получить сравнение
|
(17) |
Конечно, не каждая пара чисел, удовлетворяющих ему, позволяет разложить на множители. Эйлер и Гаусс предложили некоторые способы нахождения чисел, связанных соотношением (). Лежандр использовал для этой цели непрерывные дроби.
Напомним, что каждому иррациональному числу может быть поставлена в соответствие бесконечная последовательность целых чисел , называемая его непрерывной дробью. Это сопоставление строится следующим образом
Лежандр доказал, что непрерывная дробь квадратичной иррациональности периодична. Если раскладывать в непрерывную дробь число , то возникающие в процессе разложения числа имеют вид с целыми , причем всегда , , вычисляемых по правилам
и стремящихся к разлагаемому числу. Если в непрерывную дробь разлагается число , то справедливо соотношение
|
(18) |
из которого следует
|
(19) |
Заметим, что длина периода разложения в непрерывную дробь числа может быть большой и достигать величин порядка .
В 1971 г. Шенкс предложил использовать сравнения () для конструирования чисел, удовлетворяющих (). Если вычисления проводить до тех пор, пока при четном не получится при некотором целом , то пара чисел
$" width="69" height="31" > будет удовлетворять () и с ее помощью можно надеяться получить разложение на простые множители.
В 1975 г. Моррисон и Бриллхарт стали перемножать сравнения () при различных с тем, чтобы таким способом получить квадрат целого числа в правой части. Этот метод, метод непрерывных дробей, позволил впервые разложить на множители седьмое число Ферма . Для реализации алгоритма выбирается так называемая база множителей . В нее входят ограниченные по величине некоторым параметром простые числа такие, что
. Последнее условие связано с тем, что, согласно (), в разложение на простые множители чисел могут входить лишь те простые, для которых является квадратичным вычетом.
На первом этапе алгоритма каждое очередное число делится на все числа
и, если оно не разлагается полностью в произведение степеней этих простых, то отбрасывается. Иначе получается разложение
| (20) |
Эти вычисления проводятся до тех пор, пока не будет построено вектора показателей. В получившейся матрице показателей, очевидно, можно подобрать вектора-строки так, что их сумма будет вектором с четными координатами . Если - множество номеров векторов, вошедших в эту сумму, то, как легко проверить с помощью (), имеет место сравнение
Если с помощью этого сравнения не удается разложить на множители, разложение в непрерывную дробь продолжается, продолжается набор векторов показателей и т.д.
В этот алгоритм был внесен ряд усовершенствований: вместо можно раскладывать в непрерывную дробь число , где маленький множитель подбирается так, чтобы в базу множителей вошли все малые простые; была предложена так называемая стратегия раннего обрыва и т.д. Сложность этого алгоритма была оценена в 1982 г. величиной
. При выводе этой оценки использовался ряд правдоподобных, но не доказанных гипотез о распределении простых чисел. Получившаяся в оценке функция растет медленнее любой степенной функции. Алгоритмы, сложность которых оценивается подобным образом, получили название субэкспоненциальных (в зависимости от ).
В 1982 г. Померанцом был предложен еще один субэкспоненциальный алгоритм - алгоритм квадратичного решета. Его сложность оценивается такой же функцией, как и в методе непрерывных дробей, но вместо константы получена лучшая - . Обозначим , и выберем ту же базу множителей, что и в методе непрерывных дробей. При малых целых значениях величина будет сравнительно невелика. Следующий шаг объясняет название алгоритма - квадратичное решето. Вместо того, чтобы перебирать числа и раскладывать соответствующие значения на множители, алгоритм сразу отсеивает негодные значения , оставляя лишь те, для которых имеет делители среди элементов базы множителей.
Задав некоторую границу , для каждого простого числа , входящего в базу множителей, и каждого показателя степени , с условием находим решения квадратичного сравнения
. Множество решений обозначим буквой . Итак, для каждого найдется элемент базы множителей, а может быть и не один, входящий в некоторой степени в разложение на простые сомножители числа . Те числа , при которых значения оказываются полностью разложенными, дают нам вектор показателей, как и в алгоритме непрерывных дробей. Если таких векторов окажется достаточно много, с ними можно проделать те же операции, что и в алгоритме непрерывных дробей.
Мы кратко описали здесь лишь основную идею алгоритма. Помимо этого, используется много других дополнительных соображений и различных технических приемов. Например, аналог соотношения () имеет вид
| (21) |
Некоторые детали реализации алгоритма можно найти в работе []. Отметим здесь только, что на множители раскладывалось число , база множителей состояла из и 524338 простых чисел, меньших, чем . При этом было использовано . В результате просеивания получилось 112011 соотношений вида () без множителей , 1431337 соотношений с одним таким множителем и 6881138 соотношений с двумя множителями. Именно на поиск всех этих соотношений понадобились 220 дней и большое количество работавших параллельно компьютеров. На втором шаге алгоритма, когда из соотношений () комбинировались четные векторы показателей степеней, приходилось работать с матрицами, размеры которых измерялись сотнями тысяч битов. Этот второй шаг потребовал 45 часов работы. Уже четвертый вектор с четными показателями привел к искомому разложению на множители.
Next: 4.8. Дискретное логарифмирование
Up: 4. Алгоритмические проблемы теории
Previous: 4.6. Как проверить большое
Contents:
Как строить большие простые числа
Мы не будем описывать здесь историю этой задачи, рекомендуем обратиться к книге [] и обзорам [,]. Конечно же, большие простые числа можно строить сравнительно быстро. При этом можно обеспечить их случайное распределение в заданном диапазоне величин. В противном случае теряла бы всякий практический смысл система шифрования RSA. Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма.
Теорема 4. Пусть , - нечетные натуральные числа,
, причем для каждого простого делителя числа существует целое число такое, что
|
(10) |
Тогда каждый простой делитель числа удовлетворяет сравнению
Доказательство.
Пусть - простой делитель числа , а - некоторый делитель . Из условий () следует, что в поле вычетов справедливы соотношения
|
(11) |
Обозначим буквой порядок элемента в мультипликативной группе поля . Первые два из соотношений () означают, что входит в разложение на простые множители числа в степени такой же, как и в разложение , а последнее - что делится на . Таким образом, каждый простой делитель числа входит в разложение в степени не меньшей, чем в , так что делится на . Кроме того, четно. Теорема 2 доказана.
Следствие . Если выполнены условия теоремы 2 и , то - простое число.
Действительно, пусть равняется произведению не менее двух простых чисел. Каждое из них, согласно утверждению теоремы 2, не меньше, чем . Но тогда . Противоречие и доказывает следствие.
Покажем теперь, как с помощью последнего утверждения, имея большое простое число , можно построить существенно большее простое число . Выберем для этого случайным образом четное число на промежутке
и положим . Затем проверим число на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем некоторое количество раз с помощью алгоритма 5. Если при этом выяснится, что - составное число, следует выбрать новое значение и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число , выдержавшее испытания алгоритмом 5 достаточно много раз. В этом случае появляется надежда на то, что - простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2.
Для этого можно случайным образом выбирать число ,
| (12) |
Предположим, что построенное число действительно является простым. Зададимся вопросом, сколь долго придется перебирать числа , пока не будет найдено такое, для которого будут выполнены условия (). Заметим, что для простого числа первое условие (), согласно малой теореме Ферма, будет выполняться всегда. Те же числа , для которых нарушается второе условие (), удовлетворяют сравнению . Как известно, уравнение в поле вычетов имеет не более решений. Одно из них . Поэтому на промежутке чисел, для которых не выполняются условия (). Это означает, что, выбирая случайным образом числа на промежутке можно с вероятностью большей, чем , найти число , для которого будут выполнены условия теоремы 2, и тем доказать, что действительно является простым числом.
Заметим, что построенное таким способом простое число будет удовлетворять неравенству S^2 $" width="58" height="33" >, т.е. будет записываться вдвое большим количеством цифр, чем исходное простое число . Заменив теперь число на найденное простое число и повторив с этим новым все указанные выше действия, можно построить еще большее простое число. Начав с какого-нибудь простого числа, скажем, записанного 10 десятичными цифрами (простоту его можно проверить, например, делением на маленькие табличные простые числа), и повторив указанную процедуру достаточное число раз, можно построить простые числа нужной величины.
Обсудим теперь некоторые теоретические вопросы, возникающие в связи с нахождением простых чисел вида , где числа и удовлетворяют неравенствам . Прежде всего, согласно теореме Дирихле, доказанной еще в 1839 г., прогрессия , содержит бесконечное количество простых чисел. Нас интересуют простые числа, лежащие недалеко от начала прогрессии. Оценка наименьшего простого числа в арифметической прогрессии была получена в 1944 г. Ю.В.Линником. Соответствующая теорема утверждает, что наименьшее простое число в арифметической прогрессии не превосходит , где - некоторая достаточно большая абсолютная постоянная. В предположении справедливости расширенной гипотезы Римана можно доказать, [, с. 272], что наименьшее такое простое число не превосходит при любом положительном .
Таким образом, в настоящее время никаких теоретических гарантий для существования простого числа , не существует. Тем не менее, опыт вычислений на ЭВМ показывает, что простые числа в арифметической прогрессии встречаются достаточно близко к ее началу. Упомянем в этой связи гипотезу о существовании бесконечного количества простых чисел с условием, что число также простое, т.е. простым является уже первый член прогрессии.
Очень важен в связи с описываемым методом построения простых чисел также вопрос о расстоянии между соседними простыми числами в арифметической прогрессии. Ведь убедившись, что при некотором число составное, можно следующее значение взять равным и действовать так далее, пока не будет найдено простое число . И если расстояние между соседними простыми числами в прогрессии велико, нет надежды быстро построить нужное число . Перебор чисел до того момента, как мы наткнемся на простое число окажется слишком долгим. В более простом вопросе о расстоянии между соседними простыми числами и в натуральном ряде доказано лишь, что , что, конечно, не очень хорошо для наших целей. Вместе с тем существует так называемая гипотеза Крамера (1936 г.), что
, дающая вполне приемлемую оценку. Примерно такой же результат следует и из расширенной гипотезы Римана. Вычисления на ЭВМ показывают, что простые числа в арифметических прогрессиях расположены достаточно плотно.
В качестве итога обсуждения в этом разделе подчеркнем следующее: если принять на веру, что наименьшее простое число, а также расстояние между соседними простыми числами в прогрессии при
оцениваются величиной , то описанная схема построения больших простых чисел имеет полиномиальную оценку сложности. Кроме того, несмотря на отсутствие теоретических оценок времени работы алгоритмов, отыскивающих простые числа в арифметических прогрессиях со сравнительно большой разностью, на практике эти алгоритмы работают вполне удовлетворительно. На обычном персональном компьютере без особых затрат времени строятся таким способом простые числа порядка .
Конечно, способ конструирования простых чисел для использования в
должен быть массовым, а сами простые числа должны быть в каком-то смысле хорошо распределенными. Это вносит ряд дополнительных осложнений в работу алгоритмов. Впрочем, описанная схема допускает массу вариаций. Все эти вопросы рассматриваются в статье [].
Наконец, отметим, что существуют методы построения больших простых чисел, использующие не только простые делители , но и делители чисел , , . В основе их лежит использование последовательностей целых чисел, удовлетворяющих линейным рекуррентным уравнениям различных порядков. Отметим, что последовательность , члены которой присутствуют в формулировке малой теоремы Ферма, составляет решение рекуррентного уравнения первого порядка , .
Next: 4.6. Как проверить большое
Up: 4. Алгоритмические проблемы теории
Previous: 4.4. Как отличить составное
Contents:
Как вводить ключ?
Как вы собираетесь вводить ключ в программу шифрования? Проще всего - с клавиатуры. Именно этот вариант реализован в большинстве готовых программ, и знакомство с ними начинается с вежливого приглашения: ``enter your password: ...''. Только имейте в виду, что пароль, вводимый с клавиатуры, можно подсмотреть. Если программа шифрования при вводе пароля отображает его на экране, такой программой лучше не пользоваться. Когда при зашифровании файла вы вводите пароль, он тоже не должен отображаться на экране.
А что случится, если при вводе пароля вы случайно нажали не ту клавишу? Вы думаете, что ввели один пароль, а на самом деле ввели другой. Пробуете расшифровать файл, а программа говорит: ``Пароль неправильный''. Чтобы такого не было, обычно программы шифрования при вводе пароля для зашифрования файла просят ввести пароль дважды. Если пользователь в первый раз ввел один пароль, а во второй раз - другой, значит, по крайней мере один раз он ошибся. А если оба раза пользователь ввел одно и то же, значит, все нормально. Вряд ли пользователь дважды ошибется одинаково.
Next: Как проверять правильность ключа?
Up: 6.3. Как зашифровать файл?
Previous: Руки прочь от моих
Contents:
Как зашифровать файл?
Next: Руки прочь от моих
Up: 6. Компьютер и криптография
Previous: 49783156431138-я попытка
Contents:
Какой алгоритм выбрать?
Мы разговаривали со многими криптографами, и все они начинали с объяснения, что такое . Он прост и удобен в обращении, но имеет один существенный недостаток - раскрыть его может каждый школьник. Поэтому не будем на нем останавливаться и сразу перейдем к , либо , либо любому другому, в котором шифрование сводится к наложению одной последовательности на другую. Как признают все криптографы, при одноразовом использовании такого типа шифров дешифровать сообщение невозможно.
Простейший способ построить программу шифрования - реализовать , знаки которой можно последовательно складывать со знаками исходного сообщения. Для наложения, конечно, нужна не любая последовательность, а именно случайная. Что это такое? На первый взгляд нет проблем. Различных генераторов известно великое множество. Какой из них выбрать? Ответ очевиден - тот, который вырабатывает последовательность, наиболее близкую к случайной.
А теперь попробуйте дать определение случайной последовательности. Для эксперимента попросите кого-нибудь это сделать, и он наверняка скажет вам, что это такая последовательность, в которой каждый элемент случайно, независимо от других элементов и равновероятно может принимать каждое из возможных значений, или что-нибудь вроде ``это последовательность, являющаяся реализацией схемы независимых испытаний'', или - ``полученная в результате выборки из множества всех последовательностей с равномерным распределением''.
Недостаток использования такого рода определений для целей криптографии становится очевидным при взгляде на последовательность
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.
Она является одной из реализаций схемы последовательных независимых испытаний и ни в чем не уступает любой другой последовательности, например,
1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1,
так как вероятности появления их на выходе удовлетворяющего таким определениям случайного датчика одинаковы. С точки зрения теории, разницы нет никакой, но попробуйте их использовать для шифрования.
Таким образом, наша случайная последовательность должна быть не просто получена по той или иной вероятностной схеме, но еще и быть похожей на случайную (ведь никому не придет в голову назвать первую из этих последовательностей случайной). Но кто может ответить, что значит ``похожей''? На что похожа, например, последовательность
| 38765043353179975014693910353191097086635896251806230 |
| 29822890926723711514115245155566479256098717968310496 |
| 83605391251330391031054184702591128155858755970005635 |
| 69377039492262413967236168374702472481350482084517454 |
| 3990212200528238143667515252273 ? |
Попробуйте отличить ее от случайной последовательности. Вместе с тем, специалист по теории чисел скажет, что это десятичное представление простого числа . А теперь подумайте, как эта последовательность будет выглядеть в двоичной записи.
Каковы возможные критерии похожести? Легко сформулировать условия похожести одной последовательности на другую. Но как сформулировать, что значит ``последовательность похожа на случайную последовательность''? Эта проблема не имеет однозначного ответа. Есть много подходов к определению понятия ``похожести'', но каждый из них страдает односторонностью. Поэтому от выбранного вами подхода во многом зависит качество шифрования.
Next: Удобно ли носить большую
Up: 6.2. Немного теории
Previous: Что надо знать перед
Contents:
Какой должен быть пароль?
Какой длины должен быть пароль, чтобы защита была стойкой? Число различных вариантов пароля должно быть не меньше числа различных ключей. Если вы шифруете файл с помощью алгоритма ГОСТ, а для пароля используете только строчные английские буквы и хотите, чтобы стойкость защиты была не ниже стойкости ГОСТа, то длина пароля должна быть не меньше, чем
. (Здесь - число различных ключей ГОСТ, а 26 - число различных английских букв.) Так что вам придется придумывать 55-буквенный пароль. К тому же учтите, что если вы используете в качестве пароля не хаотичную последовательность букв, а осмысленную фразу, то нужно сделать поправку на избыточность языка. Если в пароль входят не только строчные буквы, но и заглавные, то для обеспечения необходимого числа ключей ГОСТ достаточно 51 символа. Только имейте в виду, что некоторые программы шифрования, получив пароль, преобразуют все его буквы к одному регистру. Например, делает все английские буквы, входящие в пароль, заглавными. Вы можете использовать в пароле русские буквы, но будьте осторожны! Не все программы шифрования корректно работают с русскими паролями. Таблица поможет вам оценить требуемую длину пароля в различных ситуациях.
| Алфавит | Мощность алфавита | Количество вариантов 6-символьного пароля | Длина пароля для достижения | ||
| стойкости DES = | стойкости ГОСТ = | ||||
| строчные английские буквы | 26 | 12 | 55 | ||
| строчные русские буквы | 33 | 12 | 51 | ||
| строчные и заглавные английские буквы | 52 | 10 | 45 | ||
| строчные и заглавные английские буквы и цифры | 62 | 10 | 43 | ||
| строчные и заглавные русские буквы | 66 | 10 | 43 | ||
| строчные и заглавные русские буквы и цифры | 76 | 9 | 41 | ||
| строчные и заглавные английские буквы, цифры и знаки препинания | 94 | 9 | 40 | ||
| строчные и заглавные русские буквы, цифры и знаки препинания | 108 | 9 | 38 | ||
| все алфавитно-цифровые символы русифицированной клавиатуры | 160 | 8 | 35 | ||
Имейте в виду, что данные в этой таблице относятся к тому случаю, когда в качестве пароля берется равномерно распределенная случайная последовательность символов. Если в качестве пароля вы используете только осмысленные слова и фразы, количество возможных вариантов пароля будет гораздо меньше. Если в качестве пароля используется длинная фраза русского языка, то, как показывают теоретико-информационные исследования, количество возможных вариантов будет равно не , где - число символов во фразе, а всего лишь (эта приближенная оценка верна только для больших ). Так что в этом случае для достижения стойкости DES придется брать пароль длиной 56 символов, а для достижения стойкости ГОСТ - 256 символов.
Так стоит ли вообще использовать для шифрования пароль, вводимый с клавиатуры? Для ответа на этот вопрос надо определить для себя - от кого вы собираетесь защищать информацию. Если ваш противник умеет только подбирать пароль с клавиатуры, то в качестве пароля лучше всего взять осмысленное слово длиной 6-8 символов. Главное, чтобы злоумышленнику было трудно догадаться до этого слова. При этом надо помнить, что нельзя использовать в качестве пароля:
свое имя (фамилию, отчество, прозвище, ...);
свою дату рождения (номер телефона, номер паспорта, ...);
имя того файла, который вам надо зашифровать;
и все другие пароли, которые легко угадать.
Если ваш противник, от которого вы защищаете информацию, умеет программировать, то он может написать программу, которая будет подбирать пароль автоматически. Даже если противник не умеет программировать, он может взять такую программу из Internet - там таких программ много. В этом случае пароль не должен быть осмысленным словом. В современном английском языке обычно употребляется всего около 100000 слов, в русском - чуть больше. Перебрать 100000 паролей можно очень быстро. Если в качестве шифра используется DES, на процессоре Pentium можно перебрать все английские слова-пароли всего за несколько секунд.
Даже если пароль представляет собой слово, которого нет в словаре, его все равно можно легко угадать. Вы уже знаете, что порядок букв в словах и фразах естественного языка подчиняется определенным статистическим закономерностям. Например, в русском языке комбинация букв ий встречается часто, а оь - никогда. Для большинства естественных языков статистика встречаемости символов документирована. Если программа перебора вначале подбирает наиболее вероятные пароли, а менее вероятные оставляет на потом, то перебор сокращается в десятки и сотни раз. Один из авторов видел, как подобная программа подобрала пароль natenok на компьютере с процессором 386DX-40 всего за 10 минут. Общая сложность перебора была равна . Вот другие известные авторам случаи удачного подбора паролей:
| Сложность перебора Имеется в виду сложность тотального перебора. Поскольку реально проводился оптимизированный перебор, его сложность была гораздо меньше. Этим и объясняется несоответствие сложности перебора и времени подбора. |
Время подбора | Тип процессора |
| 15 минут | 486DX/4-100 | |
| 8 часов | Pentium-120 |
В первом случае пароль представлял собой два английских слова, записанных подряд без пробела. Одно из них было трехбуквенным, другое - пятибуквенным. Во втором случае пароль состоял из трех строчных английских букв, двух заглавных английских букв и одной цифры. Этот пароль был абсолютно бессмысленным. Выводы делайте сами.
Лучший результат по подбору ключа был достигнут в 1997 году, когда в сети Internet был дешифрован файл, зашифрованный с помощью DES. В подборе ключа участвовали десятки тысяч пользователей Internet. Все множество ключей было разбито на непересекающиеся подмножества и каждый перебирал ключи из своего подмножества. Перебор длился несколько недель. Руководил работой добровольной ``виртуальной'' бригады взломщиков со своего сервера программист Рокки Версер - автор программы, перебирающей ключи. Общая сложность перебора составляла
, но ключ был найден после перебора всего 25% ключей. При этом ``расколол'' сообщение компьютер с процессором Pentium/90 c 16 Мбайт оперативной памяти. Оно гласило: ``Надежная криптография делает мир безопасным''.
Next: А можно ли обойтись
Up: 6.3. Как зашифровать файл?
Previous: Как проверять правильность ключа?
Contents:
Компьютер и криптография
М. Е. Салтыков-Щедрин
Next: 6.1. Вместо введения
Up: Введение в криптографию
Previous: Литература к главе 5
Contents:
Криптографические протоколы
Next: 3.1. Введение
Up: Введение в криптографию
Previous: Литература к главе 2
Contents:
Криптография и гипотеза PNP
Как правило, знакомство математиков-неспециалистов с теорией сложности вычислений ограничивается классами P и NP и знаменитой гипотезой PNP.
Напомним вкратце необходимые сведения из теории сложности вычислений. Пусть - множество всех конечных строк в двоичном алфавите . Подмножества в теории сложности принято называть языками. Говорят, что машина Тьюринга работает за полиномиальное время (или просто, что она полиномиальна), если существует полином такой, что на любом входном слове длины машина останавливается после выполнения не более, чем операций. Машина Тьюринга распознает (другой термин - принимает) язык , если на всяком входном слове машина
останавливается в принимающем состоянии, а на всяком слове - в отвергающем. Класс P - это класс всех языков, распознаваемых машинами Тьюринга, работающими за полиномиальное время. Функция
вычислима за полиномиальное время, если существует полиномиальная машина Тьюринга такая, что если на вход ей подано слово , то в момент останова на ленте будет записано значение . Язык принадлежит классу NP, если существуют предикат , вычислимый за полиномиальное время, и полином такие, что . Таким образом, язык принадлежит NP, если для всякого слова из длины можно угадать некоторую строку полиномиальной от длины и затем с помощью предиката убедиться в правильности догадки. Ясно, что
. Является ли это включение строгим - одна из самых известных нерешенных задач математики. Большинство специалистов считают, что оно строгое (так называемая гипотеза PNP). В классе NP выделен подкласс максимально сложных языков, называемых NP-полными: любой NP-полный язык распознаваем за полиномиальное время тогда и только тогда, когда P=NP.
Для дальнейшего нам потребуется еще понятие вероятностной машины Тьюринга. В обычных машинах Тьюринга (их называют детерминированными, чтобы отличить от вероятностных) новое состояние, в которое машина переходит на очередном шаге, полностью определяется текущим состоянием и тем символом, который обозревает головка на ленте. В вероятностных машинах новое состояние может зависеть еще и от случайной величины, которая принимает значения 0 и 1 с вероятностью каждое. Альтернативно, можно считать, что вероятностная машина Тьюринга имеет дополнительную случайную ленту, на которой записана бесконечная двоичная случайная строка. Случайная лента может читаться только в одном направлении и переход в новое состояние может зависеть от символа, обозреваемого на этой ленте.
Рассмотрим теперь следующий естественный вопрос: не является ли гипотеза PNP необходимым и достаточным условием для существования стойких криптографических схем?
Необходимость, и в самом деле, во многих случаях почти очевидна. Вернемся к примеру 1. Определим следующий язык
существует сообщение такое, что и его -ый бит равен 1.
Ясно, что : вместо описанного во введении полного перебора можно просто угадать открытый текст и проверить за полиномиальное время, что и -ый бит равен 1. Если да, то входное слово принимается, в противном случае - отвергается.
В предположении P=NP существует детерминированный полиномиальный алгоритм, распознающий язык . Зная
и , с помощью этого алгоритма можно последовательно, по биту, вычислить открытый текст . Тем самым криптосистема нестойкая.
Тот же подход: угадать секретный ключ и проверить (за полиномиальное время) правильность догадки, применим в принципе и к другим криптографическим схемам. Однако, в некоторых случаях возникают технические трудности, связанные с тем, что по информации, которая имеется у противника, искомая величина (открытый текст, секретный ключ и т.п.) восстанавливается неоднозначно.
Что же касается вопроса о достаточности предположения PNP, то здесь напрашивается следующий подход: выбрать какую-либо NP-полную задачу и построить на ее основе криптографическую схему, задача взлома которой (т.е. задача, стоящая перед противником) была бы NP-полной. Такие попытки предпринимались в начале 80-х годов, в особенности в отношении криптосистем с открытым ключом, но к успеху не привели. Результатом всех этих попыток стало осознание следующего факта: даже если PNP, то любая NP-полная задача может оказаться трудной лишь на некоторой бесконечной последовательности входных слов. Иными словами, в определение класса NP заложена мера сложности ``в худшем случае''. Для стойкости же криптографической схемы необходимо, чтобы задача противника была сложной ``почти всюду''. Таким образом, стало ясно, что для криптографической стойкости необходимо существенно более сильное предположение, чем PNP. А именно, предположение о существовании односторонних функций.
Next: 2.3. Односторонние функции
Up: 2. Криптография и теория
Previous: 2.1. Введение
Contents:
Криптография и теория сложности
Основное внимание в настоящей главе мы уделяем разъяснению важнейших идей, связанных с применением теоретико-сложностного подхода в криптографии. Изложение по необходимости недостаточно формальное - для математической криптографии типичны многостраничные определения. Предполагается знакомство читателя с основами теории сложности вычислений: понятиями машины Тьюринга, классов P и NP (см. []), а также с главой настоящей книги.
Next: 2.1. Введение
Up: Введение в криптографию
Previous: 1.5. Заключение
Contents:
Линейное разделение секрета
Начнем с предложенной А. Шамиром [] элегантной схемы разделения секрета для пороговых структур доступа. Пусть конечное поле из элементов (например, - простое число и ) и n.$" width="47" height="28" > Сопоставим участникам различных ненулевых элементов поля и положим . При распределении секрета дилер СРС генерирует независимых равномерно распределенных на случайных величин ( ) и посылает -му участнику () ``его'' значение многочлена
, где . Поскольку любой многочлен степени однозначно восстанавливается по его значениям в произвольных точках (например, по интерполяционной формуле Лагранжа), то любые участников вместе могут восстановить многочлен и, следовательно, найти значение секрета как . По этой же причине для любых участников, любых полученных ими значений проекций и любого значения секрета существует ровно один ``соответствующий'' им многочлен, т.е. такой, что и . Следовательно, эта схема является совершенной в соответствии с . ``Линейность'' данной схемы становится ясна, если записать ``разделение секрета'' в векторно-матричном виде:
|
(3) |
где , -матрица
и . Заметим, что любые столбцов этой матрицы линейно независимы, а максимально возможное число столбцов матрицы равно , и чтобы добиться обещанного в разделе значения надо добавить столбец, соответствующий точке ``бесконечность''.
Упражнение. Придумайте сами, как это сделать.
Возьмем в в качестве произвольную -матрицу с элементами из поля . Получаемую СРС будем называть одномерной линейной СРС. Она является совершенной комбинаторной СРС со структурой доступа , состоящей из множеств таких, что вектор представим в виде линейной комбинации векторов где это -ый столбец матрицы Строками матрицы , соответствующей данной СРС являются, как видно из , линейные комбинации строк матрицы . Перепишем
в следующем виде
где - скалярное произведение векторов и . Если , т.е. если , то
и, следовательно, значение секрета однозначно находится по его ``проекциям''. Рассмотрим теперь случай, когда вектор не представим в виде линейной комбинации векторов . Нам нужно показать, что в этом случае для любых заданных значений координат из множества число строк матрицы с данным значением нулевой координаты не зависит от этого значения. В этом нетрудно убедиться, рассмотрев как систему линейных уравнений относительно неизвестных и воспользовавшись тем, что система совместна тогда и только тогда, когда ранг матрицы коэффициентов равен рангу расширенной матрицы, а число решений у совместных систем одинаково и равно числу решений однородной системы.
Указание. Рассмотрите две системы: без ``нулевого'' уравнения (т.е. со свободным членом) и с ним. Так как вектор не представим в виде линейной комбинации векторов , то ранг матрицы коэффициентов второй системы на 1 больше ранга матрицы коэффициентов первой системы. Отсюда немедленно следует, что если первая система совместна, то совместна и вторая при любом .
Эта конструкция подводит нас к определению общей линейной СРС. Пусть секрет и его ``проекции'' представляются как конечномерные векторы
и генерируются по формуле где - некоторые -матрицы. Сопоставим каждой матрице линейное пространство ее столбцов (т.е. состоящее из всех линейных комбинаций вектор-столбцов матрицы ). Несложные рассуждения, аналогичные приведенным выше для одномерного случая (все ), показывают, что данная конструкция дает совершенную СРС тогда и только тогда, когда семейство линейных подпространств конечномерного векторного пространства удовлетворяет упомянутому во введении свойству ``все или ничего''. При этом множество является разрешенным (), если и только если линейная оболочка подпространств содержит подпространство целиком. С другой стороны, множество является неразрешенным ( ), если и только если линейная оболочка подпространств пересекается с подпространством только по вектору . Отметим, что если бы для некоторого пересечение и линейной оболочки было нетривиальным, то участники не могли бы восстановить секрет однозначно, но получали бы некоторую информацию о нем, т.е. схема не была бы совершенной.
Пример 3.
Рассмотрим следующую структуру доступа для случая четырех участников, задаваемую
Она известна как первый построенный пример структуры доступа, для которой не существует идеальной реализации. Более того, было доказано, что для любой ее совершенной реализации
. С другой стороны, непосредственная проверка показывает, что выбор матриц , приведенных в табл. 1, дает совершенную линейную СРС с , реализующую эту структуру, которая, следовательно, является и оптимальной (наиболее экономной) СРС.
Up: 5. Математика разделения секрета
Previous: 5.2. Разделение секрета для
Contents:
How to generate crytographically strong
1
Анохин М. И., Варновский Н. П., Сидельников В. М., Ященко В. В.
Криптография в банковском деле. М.: МИФИ, 1997.
2
Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.
3
Blum M., Micali S. How to generate crytographically strong sequences of pseudo-random bits // SIAM J. Comput. V. 13, No 4, 1984. P. 850-864.
4
Goldwasser S., Micali S., Rackoff C. The knowledge complexity of interactive proof systems // SIAM J. Comput. V. 18, No 1, 1989. P. 186-208.
5
Goldreich O., Micali S., Wigderson A. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems // J. ACM. V. 38, No 3, 1991. P. 691-729.
6
Hastad J.
Pseudo-random generators under uniform assumptions // Proc. 22nd Annu. ACM Symp. on Theory of Computing. 1990. P. 395-404.
7
Impagliazzo R., Luby M. One-way functions are essential for complexity based cryptography // Proc. 30th Annu. Symp. on Found. of Comput. Sci. 1989. P. 230-235.
8
Impagliazzo R. , Levin L., Luby M. Pseudo-random generation from one-way functions // Proc. 21st Annu. ACM Symp. on Theory of Computing. 1989. P. 12-24.
9
Impagliazzo R., Rudich S.
Limits on the provable consequences of one-way permutations // Proc. 21st Annu. ACM Symp. on Theory of Computing. 1989. P. 44-61.
10
Yao A.C. Theory and applications of trapdoor functions // Proc. 23rd Annu. Symp. on Found. of Comput. Sci. 1982. P. 80-91.
Next: 3. Криптографические протоколы
Up: Введение в криптографию
Previous: 2.5. Доказательства с нулевым
Contents:
Efficient identification and signatures for
1
Schnorr C. P. Efficient identification and signatures for smart cards // Proc. Crypto'89, Lect. Notes in Comput. Sci. V. 435, 1990. P. 239-252.
2
Goldreich O., Krawczyk H. On the composition of zero-knowledge proof systems // SIAM J. Comput. V. 25, No 1, 1996. P. 169-192.
3
Goldwasser S., Micali S., Rivest R. A secure digital signature scheme // SIAM J. Comput. V. 17, No 2, 1988. P. 281-308.
4
Naor M., Yung M. Universal one-way hash functions and their cryptographic applications // Proc. 21st Annu. ACM Symp. on Theory of Computing. 1989. P. 33-43.
5
Rompel J. One-way functions are necessary and sufficient for secure signatures // Proc. 22nd Annu. ACM Symp. on Theory of Computing. 1990. P. 387-394.
6
Fiat A., Shamir A. How to prove yourself: practical solutions to identification and signature problems // Proc. Crypto'86, Lect. Notes in Comput. Sci. V. 263, 1987. P. 186-194.
7
Feige U., Fiat A., Shamir A. Zero-knowledge proofs of identity // J. of Cryptology, V. 1, No 2, 1988. P. 77-94.
8
Варновский Н. П. О стойкости схем электронной подписи с аппаратной поддержкой. Технический отчет. Лаборатория МГУ по математическим проблемам криптографии, 1997.
9
Chaum D. Online cash checks // Proc. EUROCRYPT'89, Lect. Notes in Comput. Sci., V. 434, 1990. P. 288-293.
10
Yacobi Y. Efficient electronic money // Proc. ASIACRYPT'94, Lect. Notes in Comput. Sci., V. 739, 1994. P. 131-139.
11
Brands S. Untraceable off-line cash in wallets with observers // Proc. Crypto'93, Lect. Notes in Comput. Sci., V. 773, 1994. P. 302-318.
12
Анохин М. И., Варновский Н. П., Сидельников В. М., Ященко В. В. Криптография в банковском деле. М.: МИФИ, 1997.
13
Chaum D., Pedersen T. P. Transferred cash grows in size // Proc. EUROCRYPT'92, Lect. Notes in Comput. Sci., V. 658, 1993. P. 390-407.
14
Blum M. Coin flipping by telephone: A protocol for solving impossible problems // Proc. 24th IEEE Comp. Conf., 1982. P. 133-137; reprinted in SIGACT News, V. 15, No 1, 1983. P. 23-27.
15
Bellare M., Micali S., Ostrovsky R. Perfect zero-knowledge in constant rounds // Proc. 22nd Annu. ACM Symp. on Theory of Computing. 1990. P. 482-493.
16
Kersten A. G. Shared secret Schemes aus geometrisches sicht. Mitteilungen mathem. Seminar Giessen, Heft 208, 1992.
17
Feldman P. A practical scheme for non-interactive verifiable secret sharing // Proc. 28th Annu. Symp. on Found. of Comput. Sci. 1987. P. 427-437.
18
Rabin T., Ben-Or M. Verifiable secret sharing and multiparty protocols with honest majority // Proc. 21st Annu. ACM Symp. on Theory of Computing. 1989. P. 73-85.
19
Goldwasser S., Micali S. Probabilistic encryption // J. of Computer and System Sciences, V. 28, No 2, 1984. P. 270-299.
20
El Gamal T. A public-key cryptosystem and a signature scheme based on discrete logarithms // IEEE Trans. Inf. Theory, IT-31, No 4, 1985. P. 469-472.
21
Chaum D., Pedersen T. P. Wallet databases with observers // Proc. Crypto'92, Lect. Notes in Comput. Sci., V. 740, 1993. P. 89-105.
22
Cramer R., Gennaro R., Schoenmakers B. A secure and optimally efficient multi-authority election scheme // Proc. EUROCRYPT'97, Lect. Notes in Comput. Sci., V. 1233, 1997. P. 103-118.
23
Cramer R., Franklin M., Schoenmakers B., Yung M. Multi-authority secret ballot elections with linear work // Proc. EUROCRYPT'96, Lect. Notes in Comput. Sci., V. 1070, 1996. P. 72-83.
24
Dolev D., Dwork C., Waarts O., Yung M. Perfectly secure message transmission // Proc. 31st Annu. Symp. on Found. of Comput. Sci. 1990. P. 36-45.
Next: 4. Алгоритмические проблемы теории
Up: Введение в криптографию
Previous: 3.8. Вместо заключения
Contents:
A method for obtaining digital
1
Rivest R. L., Shamir A., Adleman L. A method for obtaining digital signatures and public key cryptosystems // Commun. ACM. V.21, No 2, 1978. P. 120-126.
2
Gardner M. A new kind of cipher that would take millions of years to break // Sci. Amer. 1977. P. 120-124.
3
Виноградов И. М. Основы теории чисел. М.: Наука, 1972.
4
Карацуба А. А. Основы аналитической теории чисел. М.: Наука, 1983 г.
5
Atkins D., Graff M., Lenstra A. K. and Leyland P. C. The magic words are squeamish ossifrage // ASIACRYPT-94, Lect. Notes in Comput. Sci. V. 917. Springer, 1995.
6
Кнут Д. Искусство программирования на ЭВМ. Т.2: Получисленные алгоритмы. М.: Мир, 1977.
7
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
8
Williams H. C. Primality testing on a computer // Ars Combin., 5, 1978. P. 127-185. (Русский перевод: Кибернетический сборник, вып. 23, 1986. С. 51-99.)
9
Василенко О. Н. Современные способы проверки простоты чисел // Кибернетический сборник, вып. 25, 1988. С. 162-188.
10
Alford W. R., Granville A., Pomerance C. There are infinitely many Carmichael numbers // Ann. Math. 140, 1994. P. 703-722.
11
Прахар К. Распределение простых чисел. М.: Мир, 1967.
12
Plaisted D. A. Fast verification, testing, and generation of large primes // Theor. Comp. Sci. 9, 1979. P. 1-16.
13
Adleman L. M., Pomerance C., Rumely R. S. On distinguishing prime numbers from composite numbers // Annals of Math. 117, 1983. P. 173-206.
14
Lenstra H. W. (jr.) Primality testing algorithms (after Adleman, Rumely and Williams) // Lecture Notes in Math. V. 901, 1981. P. 243-257.
15
Cohen H., Lenstra H. W. (jr.) Primality testing and Jacobi sums // Math. of Comput. V. 42, #165, 1984. P. 297-330.
16
Riesel H. Prime numbers and computer methods for factorization.
Birkhauser, 1985.
17
Cohen H. A course in computational algebraic number theory. GraduateTexts in Math. V. 138. New York, Springer, 1993.
18
Coppersmith D., Odlyzko A. M., Schroeppel R. Discrete logarithms in // Algorithmica. V. 1, 1986. P. 1-15.
19
McCurley K. S. The discrete logarithm problem // Proc. of Symp. in Appl. Math. V. 42, 1990. P. 49-74.
20
Lenstra A. K., Lenstra H. W., Manasse M. S., Pollard J. M. The number field sieve // Proc. 22nd Ann. ACM Symp. on Theory of Computing. Baltimore, May 14-16, 1990. P. 564-572.
21
Lenstra H. W. (jr.) Elliptic curves and number-theoretic algorithms // ICM86. P. 99-120. (Русский перевод: Международный конгресс математиков в Беркли, М.: Мир, 1991, С. 164-193.)
22
Koblitz N. A Course in Number Theory and Cryptography. 2nd ed. Springer, 1994.
23
Lenstra A. K., Lenstra H. W. (jr.) The Development of the Number Field Sieve. Lect. Notes in Math. V. 1554. Springer, 1993.
24
Ben-Or M. Probabilistic algorithms in finite fields. Proc. 22 IEEE Symp. Found. Comp. Sci, 1981. P. 394-398.
25
Gordon D.M. Discrete logarithms in , using the number field sieve. SIAM J. Disc. Math. V.6, #1, 1993. P. 124-138.
Next: 5. Математика разделения секрета
Up: Введение в криптографию
Previous: 4.9. Заключение
Contents:
AFIPS 1979 National Computer Conference.
1
Blakley G. R. Safeguarding cryptographic keys // Proc. AFIPS 1979 National Computer Conference. V. 48. N. Y., 1979. P. 313-317.
2
Shamir A. How to Share a Secret // Comm. ACM. V. 22, No 1, 1979. P. 612-613.
3
Brickell E. F., Davenport D. M. On the classification of Ideal Secret Sharing Schemes. // J. Cryptology. V. 4, 1991. P. 123-134.
4
Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
5
Csirmaz L. The size of a share must be large // J. Cryptology. V. 10, No 4, 1997. P. 223-232.
6
Welsh D. J. A. Matroid Theory. Academic Press, 1976.
7
Блейкли Г. Р., Кабатянский Г. А. Обобщенные идеальные схемы, разделяющие секрет, и матроиды // Проблемы передачи информации. Т. 33, вып. 3, 1997. С. 102-110.
8
Seymour P. O. On Secret-Sharing Matroids. // J. Comb. Theory. Ser. B. V. 56, 1992. P. 69-73.
9
Ashihmin A., Simonis J. Almost Affine codes. // Designs, codes and cryptography.
Next: 6. Компьютер и криптография
Up: Введение в криптографию
Previous: 5.4. Идеальное разделение секрета
Contents:
и практика обеспечения информационной безопасности.
1
Д. Кнут. Искусство программирования для ЭВМ. Т. 2, М.: Мир, 1977.
2
Теория и практика обеспечения информационной безопасности. Под редакцией П. Д. Зегжды. М.: Издательство Агентства ``Яхтсмен'', 1996. 192 с.
3
Р. Сайка. 56-разрядный код DES ``расколот'' на персональном компьютере. Computerworld Россия, 29 июля 1997.
4
http://www.softseek.com/
Business_and_Productivity/Microsoft_Office/
Word_Add_Ons/Review_14603_index.html
5
http://oliver.efri.hr/~crv/security/bugs/NT
6
T. Ylonen, T. Kivinen, M. Saarinen. SSH Transport Layer Protocol. Internet-Draft, November 1997.
draft-ietf-secsh-transport-03.txt.
7
Orman H., The Oakley Key Determination Protocol. Version 1, TR97-92. Department of Computer Science Technical Report, University of Arizona.
Next: 7. Олимпиады по криптографии
Up: Введение в криптографию
Previous: Ответ на второй вопрос
Contents:
Криптография от папируса до компьютера.
1
М. Гарднер. От мозаик Пенроуза к надежным шифрам. М.: Мир, 1993.
2
У. Болл, Г. Кокстер. Математические эссе и развлечения. М.: Мир, 1986.
3
С. А. Дориченко, В. В. Ященко. 25 этюдов о шифрах. М.: ТЭИС, 1994.
4
В. Жельников. Криптография от папируса до компьютера. М.: ABF, 1996.
5
Г. Фролов. Тайны тайнописи. М., 1992.
6
Ч. Уэзерелл. Этюды для программистов. М.: Мир, 1982.
7
А. Саломаа. Криптография с открытым ключом. М.: Мир, 1995.
8
Т. А. Соболева. Тайнопись в истории России (История криптографической службы России XVIII - начала XX в.). М., 1994.
9
Б. Анин, А. Петрович. Радиошпионаж. М.: Международные отношения, 1996.
10
Г. А. Гуревич. Криптограмма Жюля Верна. // Квант, #9, 1985.
11
В. Каверин. Собрание сочинений в 6 т., т. 2. ``Исполнение желаний'' С. 211-552. М.: Художественная литература, 1964.
12
Э. По. Стихотворения. Проза (``Золотой жук'' С. 433-462). М.: Художественная литература, 1976.
13
А. Конан Дойл. Записки о Шерлоке Холмсе. ``Пляшущие человечки'' С. 249-275. М.: Правда, 1983.
14
Ж. Верн. Собрание сочинений в 12 т. ``Путешествие к центру Земли'' С. 7-225. М.: Художественная литература, 1995.
15
Ж. Верн. Жангада. Библиотечка приключений. Т. 9. М.: Детская литература, 1967.
Next: Приложение
Up: Введение в криптографию
Previous: ...к задачам девятой олимпиады
Contents:
Математические основы
Большое влияние на развитие криптографии оказали появившиеся в середине XX века работы американского математика Клода Шеннона. В этих работах были заложены основы теории информации, а также был разработан математический аппарат для исследований во многих областях науки, связанных с информацией. Более того, принято считать, что теория информации как наука родилась в 1948 году после публикации работы К. Шеннона ``Математическая теория связи''1).
В своей работе ``Теория связи в секретных системах'' Клод Шеннон обобщил накопленный до него опыт разработки шифров (см. Приложение ). Оказалось, что даже в очень сложных шифрах в качестве типичных компонентов можно выделить такие простые шифры как шифры замены, шифры перестановки или их сочетания.
является простейшим, наиболее популярным шифром. Типичными примерами являются шифр Цезаря, ``цифирная азбука'' Петра Великого и ``пляшущие человечки'' А.Конан Дойла. Как видно из самого названия, шифр замены осуществляет преобразование замены букв или других ``частей'' открытого текста на аналогичные ``части'' шифрованного текста. Легко дать математическое описание шифра замены. Пусть и - два алфавита (открытого и шифрованного текстов соответственно), состоящие из одинакового числа символов. Пусть также - взаимнооднозначное отображение в . Тогда шифр замены действует так: открытый текст преобразуется в шифрованный текст .
, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным примером шифра перестановки является шифр ``Сцитала''. Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок шифруется независимо. Пусть, например, длина отрезков равна и - взаимнооднозначное отображение множества в себя. Тогда шифр перестановки действует так: отрезок открытого текста преобразуется в отрезок шифрованного текста
.
Важнейшим для развития криптографии был результат К. Шеннона о существовании и единственности абсолютно стойкого шифра.
Единственным таким шифром является какая-нибудь форма так называемой ленты однократного использования, в которой открытый текст ``объединяется'' с полностью случайным ключом такой же длины.
Этот результат был доказан К.Шенноном с помощью разработанного им теоретико- информационного метода исследования шифров. Мы не будем здесь останавливаться на этом подробно, заинтересованному читателю рекомендуем изучить работу К.Шеннона (cм. Приложение .).
Обсудим особенности строения абсолютно стойкого шифра и возможности его практического использования. Типичным и наиболее простым примером реализации абсолютно стойкого шифра является шифр Вернама, который осуществляет побитовое сложение -битового открытого текста и -битового ключа:
Здесь - открытый текст, - ключ, - шифрованный текст.
Подчеркнем, что для абсолютной стойкости существенным является каждое из следующих требований к ленте однократного использования:
1) полная случайность (равновероятность) ключа (это, в частности, означает, что ключ нельзя вырабатывать с помощью какого-либо детерминированного устройства);
2) равенство длины ключа и длины открытого текста;
3) однократность использования ключа.
В случае нарушения хотя бы одного из этих условий шифр перестает быть абсолютно стойким и появляются принципиальные возможности для его вскрытия (хотя они могут быть трудно реализуемыми).
Но, оказывается, именно эти условия и делают абсолютно стойкий шифр очень дорогим и непрактичным. Прежде чем пользоваться таким шифром, мы должны обеспечить всех абонентов достаточным запасом случайных ключей и исключить возможность их повторного применения. А это сделать необычайно трудно и дорого.
Как отмечал Д.Кан: ``Проблема создания, регистрации, распространения и отмены ключей может показаться не слишком сложной тому, кто не имеет опыта передачи сообщений по каналам военной связи, но в военное время объем передаваемых сообщений ставит в тупик даже профессиональных связистов. За сутки могут быть зашифрованы сотни тысяч слов. Создание миллионов ключевых знаков потребовало бы огромных финансовых издержек и было бы сопряжено с большими затратами времени. Так как каждый текст должен иметь свой собственный, единственный и неповторимый ключ, применение идеальной системы потребовало бы передачи по крайней мере такого количества знаков, которое эквивалентно всему объему передаваемой военной информации.''
В силу указанных причин абсолютно стойкие шифры применяются только в сетях связи с небольшим объемом передаваемой информации, обычно это сети для передачи особо важной государственной информации.
Теперь уже понятно, что чаще всего для защиты своей информации законные пользователи вынуждены применять неабсолютно стойкие шифры. Такие шифры, по крайней мере теоретически, могут быть вскрыты. Вопрос только в том, хватит ли у противника сил, средств и времени для разработки и реализации соответствующих алгоритмов. Обычно эту мысль выражают так: противник с неограниченными ресурсами может вскрыть любой неабсолютно стойкий шифр.
Как же должен действовать в этой ситуации законный пользователь, выбирая для себя шифр? Лучше всего, конечно, было бы доказать, что никакой противник не может вскрыть выбранный шифр, скажем, за 10 лет и тем самым получить теоретическую оценку стойкости. К сожалению, математическая теория еще не дает нужных теорем - они относятся к нерешенной проблеме нижних оценок вычислительной сложности задач.
Поэтому у пользователя остается единственный путь- получение практических оценок стойкости. Этот путь состоит из следующих этапов:
- понять и четко сформулировать, от какого противника мы собираемся защищать информацию; необходимо уяснить, что именно противник знает или сможет узнать о системе шифра, а также какие силы и средства он сможет применить для его вскрытия;
- мысленно стать в положение противника и пытаться с его позиций атаковать шифр, т.е. разрабатывать различные алгоритмы вскрытия шифра; при этом необходимо в максимальной мере обеспечить моделирование сил, средств и возможностей противника;
- наилучший из разработанных алгоритмов использовать для практической оценки стойкости шифра.
Здесь полезно для иллюстрации упомянуть о двух простейших методах вскрытия шифра: случайное угадывание ключа (он срабатывает с маленькой вероятностью, зато имеет маленькую сложность) и перебор всех подряд ключей вплоть до нахождения истинного (он срабатывает всегда, зато имеет очень большую сложность). Отметим также, что не всегда нужна атака на ключ: для некоторых шифров можно сразу, даже не зная ключа, восстанавливать открытый текст по шифрованному.
Next: 1.4. Новые направления
Up: 1. Основные понятия криптографии
Previous: 1.2. Предмет криптографии
Contents:
Математика разделения секрета
Next: 5.1. Введение
Up: Введение в криптографию
Previous: Литература к главе 4
Contents:
