Обзор основных понятий криптографии

Раздел Математика
Класс 11 класс
Тип Другие методич. материалы
Автор
Дата
Формат docx
Изображения Есть
For-Teacher.ru - все для учителя
Поделитесь с коллегами:

Обзор основных понятий криптографии

1. Введение

Как передать нужную информацию нужному адресату в тайне от других?

И много лет назад, и в наше время люди вынуждены решать эту задачу. Есть три различных подхода к решению этой задачи.

  1. Попытаться создать абсолютно надежный, недоступный для других канал связи между абонентами.

  2. Использовать общедоступный канал связи, но скрыть сам факт передачи информации.

  3. Использовать общедоступный канал связи, но передавать по нему нужную информацию в так преобразованном виде, чтобы восстановить ее мог только адресат.

Прокомментируем эти три подхода.

  1. При современном уровне развития науки и техники сделать такой канал связи между удаленными абонентами для неоднократной передачи больших объемов информации практически нереально.

  2. Разработкой средств и методов скрытия факта передачи сообщения занимается стеганография.

Первые следы стеганографических методов теряются в глубокой древности. Например, известен такой способ скрытия письменного сообщения: голову раба брили, на коже головы писали сообщение и после отрастания волос раба отправляли к адресату.

Из детективных произведений хорошо известны различные способы тайнописи между строк обычного, незащищаемого текста: от молока до сложных химических реактивов с последующей обработкой.

Также из детективов известен метод «микроточки»: сообщение записывается с помощью современной техники на очень маленький носитель(микроточку), который пересылается с обычным письмом, например, под маркой или где-нибудь в другом, заранее обусловленном месте.

3. Разработкой методов преобразования (шифрования) информации с целью ее защиты от незаконных пользователей занимается криптография. Такие методы и способы преобразования информации называются шифрами.

Шифрование (зашифрование) - процесс применения шифра к защищаемой информации, т. е. преобразование защищаемой информации (открытого текста) в шифрованное сообщение (шифртекст, криптограмму) с помощью определенных правил, содержащихся в шифре.

Расшифрование - процесс, обратный шифрованию, т. е. преобразование шифрованного сообщения в защищаемую информацию с помощью определенных правил, содержащихся в шифре.

Криптография - прикладная наука, она использует самые последние достижения фундаментальных наук и, в первую очередь, математики. С другой стороны, все конкретные задачи криптографии существенно зависят от уровня развития техники и технологии, от применяемых средств связи и способов передачи информации.

2. Предмет криптографии

Что же является предметом криптографии? Для ответа на этот вопрос вернемся к задаче тайной передачи информации.

Прежде всего заметим, что эта задача возникает только для информации, которая нуждается в защите. Обычно в таких случаях говорят, что информация содержит тайну или является защищаемой, приватной, конфиденциальной, секретной. Для наиболее типичных, часто встречающихся ситуаций такого типа введены даже специальные понятия

- государственная тайна;

- военная тайна;

- коммерческая тайна;

- юридическая тайна;

- врачебная тайна и т. д.

Мы будем говорить о защищаемой информации, имея в виду следующие признаки такой информации:

- имеется строго определенный круг законных пользователей, которые имеют право владеть этой информацией;

- имеются незаконные пользователи, которые стремятся овладеть этой информацией с тем, чтобы обратить ее себе во благо, а законным пользователям во вред.

Для простоты мы вначале ограничимся рассмотрением только одной угрозы - угрозы разглашения информации. Существуют и другие угрозы для защищаемой информации со стороны незаконных пользователей: подмена, имитация и др.

Теперь мы можем изобразить ситуацию, следующей схемой (см. рис. 1).

А

В

П

Рис.1

Здесь А и В - удаленные законные пользователи защищаемой информации; они хотят обмениваться информацией по общедоступному каналу связи. П - незаконный пользователь (противник), который может перехватывать передаваемые по каналу связи сообщения и пытаться извлечь из них интересующую его информацию. Эту формальную схему можно считать моделью типичной ситуации, в которой применяются криптографические методы защиты информации.

Отметим, что исторически в криптографии закрепились некоторые военные термины (противник, атака на шифр и др.) Они наиболее точно отражают смысл соответствующих криптографических понятий.

Криптография занимается методами преобразования информации, которые бы не позволили противнику извлечь ее из перехватываемых сообщений. При этом по каналу связи передается уже не сама защищаемая информация, а результат ее преобразования с помощью шифра. Таким образом, одна из важных задач криптографии-обеспечение конфиденциальности информации.

Вскрытие (взламывание) шифра - процесс получения защищаемой информации из шифрованного сообщения без знания примененного шифра.

Однако помимо перехвата и вскрытия шифра противник может пытаться получить защищаемую информацию многими другими способами. Наиболее известным из таких способов является агентурный, когда противник каким-либо путем склоняет к сотрудничеству одного из законных пользователей и с помощью этого агента получает доступ к защищаемой информации. В такой ситуации криптография бессильна.

Противник может пытаться не получить, а уничтожить или модифицировать защищаемую информацию в процессе ее передачи. Это - совсем другой тип угроз для информации, отличный от перехвата и вскрытия шифра. Для защиты от таких угроз разрабатываются свои специфические методы.

Следовательно, на пути от одного законного пользователя к другому информация должна защищаться различными способами, противостоящими различным угрозам. Возникает ситуация цепи из разнотипных звеньев, которая защищает информацию. Естественно, противник будет стремиться найти самое слабое звено, чтобы с наименьшими затратами добраться до информации. А значит, и законные пользователи должны учитывать это обстоятельство в своей стратегии защиты: бессмысленно делать какое-то звено очень прочным, если есть заведомо более слабые звенья («принцип равнопрочности защиты»).

Не следует забывать и еще об одной важной проблеме: проблеме соотношения цены информации, затрат на ее защиту и затрат на ее добывание. При современном уровне развития техники сами средства связи, а также разработка средств перехвата информации из них и средств защиты информации требуют очень больших затрат. Прежде чем защищать информацию, необходимо задать себе два вопроса:

1) является ли она для противника более ценной, чем стоимость атаки;

2) является ли она для вас более ценной, чем стоимость защиты.

Именно перечисленные соображения и являются решающими при выборе подходящих средств защиты: физических, стеганографических, криптографических и др.

Некоторые понятия криптографии удобно иллюстрировать историческими примерами, поэтому сделаем небольшое историческое отступление.Наукой не установлен точный исторический период,когда появилась криптография, каковы были ее первоначальные формы и кто был ее создателем. Однако считается , что криптография старше египетских пирамид. Уже в исторических документах древних цивилизаций-Индии, Египта, Месопотамии-имеются сведения о системах и способах составления шифрованного письма. Сохранились достоверные сведения о системах шифров,применявшихся в Древней Греции. Свой след в истории криптографии оставили многие хорошо известные исторические личности. Первые сведения об использовании шифров в военном деле связаны с именем спартанского полководца Лисандра, разработавшего шифр "Сцитала". Этот шифр известен со времен войны Спарты против Афин в V веке до н.э. Для его реализации использовалась сцитала - жезл, имеющий форму цилиндра. На сциталу виток к витку наматывалась узкая папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль оси сциталы записывался текст. Лента разматывалась и получалось (для непосвященных), что поперек ленты в беспорядке написаны какие-то буквы. Затем лента отправлялась адресату. Адресат брал такую же сциталу, таким же образом наматывал на неё полученную ленту и читал сообщение вдоль оси сциталы. В этом шифре преобразование открытого текста в шифрованный заключается в определенной перестановке букв открытого текста. Поэтому класс шифров, к которым относится и шифр "Сцитала", называется шифрами перестановки.

Известен прибор времен Спарты, называемый ``таблица Энея ``.Это был шифр замены. Также Энею принадлежит идея,использовавшаяся тысячелетиями. Он предложил книжный шифр,в котором буквам открытого текста соответствуют буквы, находящиеся на определенных местах в являющемся ключом книжном тексте.Эта система применялась даже в середине 20-го века, во время Второй мировой войны. Первые попытки систематизации и обобщения накопленного за века опыта были предприняты в арабских странах.Арабского происхождентя и само слово ``шифр``.Первая книга, специально посвященная описанию и сравнению разных систем шифрования, появилась в 855 году. В 1412 году была издана энциклопедия,содержащая обзор всех важнейших областей человеческого знания. В ней есть раздел, в котором описано много шифров и приводятся примеры раскрытия шифров методом частотного анализа встречаемости букв. Большое внимание уделяли созданию и применению шифров такие известные исторические деятели, как Оливер Кромвель,Николо Макиавелли,кардинал Ришелье…Традиции русского тайнописания уходят своими корнями в допетровскую эпоху.Известно, что крупные политические и военные акции Ивана Грозного оказали влияние и на развитие тайнописного дела. И традиции были продолжены. Так, в наказе царя Федора Иоанновича(1557-1589)-сына Ивана Грозного,- данном в 1589г.послу Николаю Воркачу, ему поручалось ``писать письма мудрою азбукою, чтоб оприч Царского величества никто не разумел``. С конца 16в. русские посланники за рубежом получают шифры в виде таблиц.И все же первым из российских государей,который предельно ясно осознавал важность развития шифровального дела для обеспечения безопасности государства,был Петр Великий.Государственные шифры того времени были шифрами простой замены.В российские шифры с начала 18в. , как правило, вводятся ``пустышки``--шифробозначения, которым не соответствует никакого знака открытого текста. Хотя обычно для этого использовалось всего пять-восемь шифрвеличин в качестве пустышек, очевидно, что введение их в шифртекстотражает стремление создателей шифров осмыслить процесс дешифрования. Эти пустышки разбивают структурные лингвистические связи открытого текста и изменяют статистические характеристики , то есть именно те особенности текста, которые используют в первую очередь при атаке на шифр простой замены. Кроме того, они изменяют длину передаваемого сообщения.Поэтому, видимо , не случайно, первый такой русский шифр был раскрыт англичанами лишь в 1725г….Известно также и о применении шифров в переписке революционерами. И первая, и вторая мировые войны дали много примеров применения математики к анализу шифров. Криптографы воюющих стран напряженно работали, совершенствуя свои алгоритмы шифрования и ``взламывая`` шифры противника. И во второй половине 20в. ведущие державы мира уделяли большое внимание развитию криптографии.

Долгое время занятие криптографией было уделом чудаков-одиночек. Среди них были одаренные ученые, дипломаты, священнослужители. Известны случаи, когда криптография считалась даже чёрной магией. Этот период развития криптографии как искусства длился с незапамятных времён до начала ХХ века, когда появились первые шифровальные машины. Понимание математического характера решаемых криптографией задач пришло только в середине ХХ века - после работ выдающегося американского ученого К. Шеннона.

Можно использовать хороший шифр для шифрования как можно большего количества сообщений. Однако при этом возникает опасность, что противник уже разгадал (вскрыл) шифр и читает защищаемую информацию. Если же в шифре есть сменный ключ, то, заменив ключ, можно сделать так, что разработанные противником методы уже не дают эффекта.

Под ключом в криптографии понимают сменный элемент шифра, который применяется для шифрования конкретного сообщения. Например, в шифре «Сцитала» ключом является диаметр сциталы, а в шифрах типа шифра Цезаря ключом является величина сдвига букв шифртекста относительно букв открытого текста.

Описанные соображения привели к тому, что безопасность защищаемой информации стала определяться в первую очередь ключом. Сам шифр, шифрмашина или принцип шифрования стали считать известными противнику и доступными для предварительного изучения, но в них появился неизвестный для противника ключ, от которого существенно зависят применяемые преобразования информации. Теперь законные пользователи, прежде чем обмениваться шифрованными сообщениями, должны тайно от противника обменяться ключами. А для противника появилась новая задача - определить ключ, после чего можно легко прочитать зашифрованные на этом ключе сообщения.

Вернемся к формальному описанию основного объекта криптографии (рис. 1). Теперь в него необходимо внести существенное изменение - добавить недоступный для противника секретный канал связи для обмена ключами (рис. 2). Создать такой канал связи вполне реально, поскольку нагрузка на него, вообще говоря, небольшая.

А

В

П

ключи

сообщения


Рис. 2

Отметим теперь, что не существует единого шифра, подходящего для всех случаев. Выбор способа шифрования зависит от особенностей информации, ее ценности и возможностей владельцев по защите своей информации. Прежде всего подчеркнем большое разнообразие видов защищаемой информации: документальная, телефонная, телевизионная, компьютерная и т. д. Каждый вид информации имеет свои специфические особенности, и эти особенности сильно влияют на выбор методов шифрования информации. Большое значение имеют объемы и требуемая скорость передачи шифрованной информации. Выбор вида шифра и его параметров существенно зависит от характера защищаемых секретов или тайны. Некоторые тайны (например, государственные, военные и др.) должны сохраняться десятилетиями, а некоторые (например, биржевые) - уже через несколько часов можно разгласить. Необходимо учитывать также и возможности того противника, от которого защищается данная информация. Одно дело - противостоять одиночке или даже банде уголовников, а другое дело - мощной государственной структуре. Под атакой на шифр понимают попытку вскрытия этого шифра. Способность шифра противостоять всевозможным атакам на него называют стойкостью шифра.

Понятие стойкости шифра является центральным для криптографии. Хотя качественно понять его довольно легко, но получение строгих доказуемых оценок стойкости для каждого конкретного шифра - проблема нерешенная. Это объясняется тем, что до сих пор нет необходимых для решения такой проблемы математических результатов. Поэтому стойкость конкретного шифра оценивается только путем всевозможных попыток его вскрытия и зависит от квалификации криптоаналитиков, атакующих шифр. Такую процедуру иногда называют проверкой стойкости.

Важным подготовительным этапом для проверки стойкости шифра является продумывание различных предполагаемых возможностей, с помощью которых противник может атаковать шифр. Появление таких возможностей у противника обычно не зависит от криптографии, это является некоторой внешней подсказкой и существенно влияет на стойкость шифра. Поэтому оценки стойкости шифра всегда содержат те предположения о целях и возможностях противника, в условиях которых эти оценки получены.

Прежде всего, как это уже отмечалось выше, обычно считается, что противник знает сам шифр и имеет возможности для его предварительного изучения. Противник также знает некоторые характеристики открытых текстов, например, общую тематику сообщений, их стиль, некоторые стандарты, форматы и т. д.

Из более специфических приведем еще три примера возможностей противника:

- противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов;

- противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты;

- противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровывать и дешифровывать любую информацию.

На протяжении многих веков среди специалистов не утихали споры о стойкости шифров и о возможности построения абсолютно стойкого шифра.

3. Математические основы

Большое влияние на развитие криптографии оказали появившиеся в середине XX века работы американского математика Клода Шеннона. В этих работах были заложены основы теории информации, а также был разработан математический аппарат для исследований во многих областях науки, связанных с информацией. Более того, принято считать, что теория информации как наука родилась в 1948 году после публикации работы К. Шеннона «Математическая теория связи».

В своей работе «Теория связи в секретных системах» Клод Шеннон обобщил накопленный до него опыт разработки шифров. Оказалось, что даже в очень сложных шифрах в качестве типичных компонентов можно выделить такие простые шифры как шифры замены, шифры перестановки или их сочетания.

Шифр замены является простейшим, наиболее популярным шифром. Типичными примерами являются шифр Цезаря, «цифирная азбука» Петра Великого и «пляшущие человечки» А. Конан Дойла. Как видно из самого названия, шифр замены осуществляет преобразование замены букв или других «частей» открытого текста на аналогичные «части» шифрованного текста. Легко дать математическое описание шифра замены. Пусть X и Y - два алфавита (открытого и шифрованного текстов соответственно), состоящие из одинакового числа символов. Пусть также g: X -> Y - взаимнооднозначное отображение Х в Y. Тогда шифр замены действует так: открытый текст х1х2...хп преобразуется в шифрованный текст g(x1)g(x2)... g(хп).

Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным примером шифра перестановки является шифр «Сцитала». Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок шифруется независимо. Пусть, например, длина отрезков равна п и σ - взаимнооднозначное отображение множества {1,2,..., п} в себя. Тогда шифр перестановки действует так: отрезок открытого текста х1...хп преобразуется в отрезок шифрованного текста

Важнейшим для развития криптографии был результат К. Шеннона о существовании и единственности абсолютно стойкого шифра. Единственным таким шифром является какая-нибудь форма так называемой ленты однократного использования, в которой открытый текст «объединяется» с полностью случайным ключом такой же длины.

Этот результат был доказан К. Шенноном с помощью разработанного им теоретико-информационного метода исследования шифров.

Обсудим особенности строения абсолютно стойкого шифра и возможности его практического использования. Типичным и наиболее простым примером реализации абсолютно стойкого шифра является шифр Вернама, который осуществляет побитовое сложение n-битового открытого текста и n-битового ключа:

yi = xiОбзор основных понятий криптографииki, i = 1,...,n.

Здесь x1...хп - открытый текст, k1,...,kп - ключ, у1...уn - шифрованный текст. Пример из …

Подчеркнем, что для абсолютной стойкости существенным является каждое из следующих требований к ленте однократного использования:

1) полная случайность (равновероятность) ключа (это, в частности, означает, что ключ нельзя вырабатывать с помощью какого-либо детерминированного устройства);

2) равенство длины ключа и длины открытого текста;

3) однократность использования ключа.

В случае нарушения хотя бы одного из этих условий шифр перестает быть абсолютно стойким и появляются принципиальные возможности для его вскрытия (хотя они могут быть трудно реализуемыми).

Но, оказывается, именно эти условия и делают абсолютно стойкий шифр очень дорогим и непрактичным. Прежде чем пользоваться таким шифром, мы должны обеспечить всех абонентов достаточным запасом случайных ключей и исключить возможность их повторного применения. А это сделать необычайно трудно и дорого.

Формальные модели шифров

Для того чтобы иметь возможность доказывать в криптографии точные результаты, нужны математические модели основных исследуемых объектов, к которым относятся в первую очередь шифр и открытый текст. Введем сначала алгебраическую модель шифра (шифрсистемы), предложенную К. Шенноном. С моделями открытых текстов мы познакомимся ниже.

Как мы уже знаем, криптография защищает информацию с помощью шифрования - процедуры, использующей некое обратимое преобразование. При этом преобразование открытого текста в шифрованный называется зашифрованием, а обратный процесс - расшифрованием. Шифрование предполагает наличие множества обратимых преобразований. Выбор преобразования из указанного множества для зашифрования данного сообщения осуществляется с помощью ключа. Имеется однозначное соответствие между множеством ключей и множеством преобразований.

Выбор ключа естественным образом определяет функцию (вообще говоря, многозначную), отображающую множество возможных открытых текстов в множество возможных шифрованных текстов. Способ вычисления значения этой функции для произвольного аргумента будем называть правилом зашифрования. Выбранный ключ будем называть ключом зашифрования. Требование однозначности расшифрования определяет обратную функцию, отображающую множество возможных (при выбранном ключе) шифрованных текстов в множество возможных открытых текстов. Способ вычисления значения этой функции для произвольного аргумента будем называть правилом расшифрования. Ключ, определяющий выбор правила расшифрования, будем называть ключом расшифрования.

Формализуем сказанное.

Пусть X,K,Y - конечные множества возможных открытых текстов, ключей и шифрованных текстов соответственно; Ek : X -> Y - правило зашифрования на ключе kОбзор основных понятий криптографииК. Множество {Еk: kОбзор основных понятий криптографииК} обозначим через Е, а множество {Еk (х): хОбзор основных понятий криптографииХ} - через Еk (X). Пусть Dk: Еk (X) -> X - правило расшифрования на ключе kОбзор основных понятий криптографииК, и D - это множество {Dk: kОбзор основных понятий криптографииК}.

Здесь и далее мы будем предполагать, что если kОбзор основных понятий криптографииК представляется в виде k = (k3,kp), где k3 - ключ зашифрования, а kр- ключ расшифрования (причем k3Обзор основных понятий криптографии kр), то Еk понимается как функция Еk3 ,а Dk - как функция Dkp.

Определение . Шифром (шифрсистемой) назовем совокупность

Обзор основных понятий криптографииA=(X,K,Y,E,D)

введенных множеств, для которых выполняются следующие свойства:

1) для любых хОбзор основных понятий криптографииX и kОбзор основных понятий криптографииК выполняется равенство Dk(Ek(x)) = x;

2)Обзор основных понятий криптографии

Неформально, шифр - это совокупность множеств возможных открытых текстов (то, что шифруется), возможных ключей (то, с помощью чего шифруется), возможных шифр-текстов (то, во что шифруется), правил зашифрования и правил расшифрования.

Отметим, что условие 1) отвечает требованию однозначности расшифрования. Условие 2) означает, что любой элемент уОбзор основных понятий криптографииY может быть представлен в виде Еk (х) для подходящих элементов хОбзор основных понятий криптографииX и kОбзор основных понятий криптографииК. Отметим также, что в общем случае утверждение "для любых kОбзор основных понятий криптографииК и уОбзор основных понятий криптографииЕk (X) выполняется равенство Еk (Dk (у)) = у" является неверным.

Легко проверить, что из условия 1) следует свойство инъективности функции Еk. Другими словами, если x1, x2Обзор основных понятий криптографииX, причем х1Обзор основных понятий криптографиих2, то при любом kОбзор основных понятий криптографииК выполняется неравенство Еk1)Обзор основных понятий криптографииЕk2).

По сути дела определение 1 вводит математическую модель, отражающую основные свойства реальных шифров. В силу этого мы будем отождествлять реальный шифр с его моделью Обзор основных понятий криптографииА, которую будем называть алгебраической моделью шифра. Для подавляющего большинства известных шифров несложно составить такую модель.

Классификация шифров по различным признакам

В качестве первичного признака, по которому производится классификация шифров, используется тип преобразования, осуществляемого с открытым текстом при шифровании. Если фрагменты открытого текста (отдельные буквы или группы букв) заменяются некоторыми их эквивалентами в шифртексте, то соответствующий шифр относится к классу шифров замены. Если буквы открытого текста при шифровании лишь меняются местами друг с другом, то мы имеем дело с шифром перестановки. С целью повышения надежности шифрования шифрованный текст, полученный применением некоторого шифра, может быть еще раз зашифрован с помощью другого шифра. Всевозможные такие композиции различных шифров приводят к третьему классу шифров, которые обычно называют композиционными шифрами. Заметим, что композиционный шифр может не входить ни в класс шифров замены, ни в класс шифров перестановки. В результате получаем первый уровень классификации шифров:


Шифры

Шифры замены

Шифры перестановки

Композиционные шифры


Итак, мы рассмотрели некоторые понятия криптографии.Криптография в настоящее время бурно развивается и находит применения в самых разных областях человеческой деятельности.Заметим, что уже появились факультативные курсы по криптографии для школьников и практика показывает, что многие идеи и методы вполне доступны учащимся 10-11 классов. В заключение нашего краткого очерка приведем условия и решения нескольких олимпиадных задач.

1.Английский язык. Открытый текст на английском языке (различие между строчной и прописной буквой не делается) кодируется, т. е. переводится в числовую форму, по правилу: букве А присваивается номер 0, букве В - номер 1, букве Z - номер 25, пробелу соответствует номер 26. Затем текст шифруется по следующему алгоритму: вычисляется число aP+b, где Р - номер буквы открытого текста, а числа a и b - ключ шифрования (неизвестный вам). Вычисленное число заменяется остатком от деления на 27, полученному числу соответствует буква шифрованного текста. Вам известен алгоритм, неизвестен ключ.

Перед вами перехваченный шифрованный текст. Этих данных недостаточно для расшифровки. Однако из агентурных сведений стало известно: второй символ открытого текста - пробел. Теперь данных достаточно. Прочитайте открытый текст.

Шифртекст: TBUEC

Решение.Так как второй символ открытого текста - пробел, то текст начинается с однобуквенного слова. Но таких слов в английском языке всего два: А (неопределённый артикль) и I («Я»). Значит, возможны два варианта: 1) А_... ; 2) I_... .

Рассмотрим первый вариант. Буква А кодируется числом ноль, далее шифруется по формуле: Обзор основных понятий криптографии получается 19 - код буквы Т. Итак, b = 19. Пробел кодируется числом 26, шифруется: Обзор основных понятий криптографии

Имеем условие на а: Обзор основных понятий криптографии или Обзор основных понятий криптографии где p, q - некоторые целые числа (сдвиг на 27 позиций не меняет текста). Из чисел от 1 до 26 только одно удовлетворяет условию: a = 18. Итак, a = 18, b= 19. Имеем уравнения для оставшихся букв:

Обзор основных понятий криптографии

где r, s, t - некоторые целые числа.

Запишем систему в виде

Обзор основных понятий криптографии

Последнее уравнение запишем в виде Обзор основных понятий криптографииили Обзор основных понятий криптографии

Так как z и t - целые, то и число 2z - 3t - целое. Но тогда в левой части произведение числа 9 на некоторое целое число, получим противоречие с тем, что 17 - простое число.

Рассмотрим второй вариант. Имеем систему

Обзор основных понятий криптографии

Решение: a = 2, b = 3. Теперь открытый текст находится:

I_WON («Я ПОБЕДИЛ»).

Задача 2.Разделение секрета. Сейф с документами открывается, если набрано секретное число М. Для разделения секрета используется многочлен Обзор основных понятий криптографии где a, b - целые числа. Каждый из трех членов комиссии получил свою долю секрета. Именно: первый знает, что F(2) делится на 13 с остатком 3, второй знает: F(3) делится на 13 с остатком 7, третий знает: F(5) делится на 13 с остатком 5.

Докажите, что объединив свои знания, эти трое смогут открыть сейф (и найдите число М), а любые двое из них не смогут (числа a и b члены комиссии не знают).

Решение. Нужно найти М из условий:

Обзор основных понятий криптографии

где p, q, t - некоторые целые числа.

Складывая первое равенство со вторым и вычитая из их суммы третье, получим: Обзор основных понятий криптографии, где Обзор основных понятий криптографии - некоторое целое. Вычитая первое из второго, получим Обзор основных понятий криптографии.

Теперь подставим Обзор основных понятий криптографии, Обзор основных понятий криптографии в первое уравнение. Получим Обзор основных понятий криптографии, u - целое число. Так как каждое число заменяется его остатком от деления на 13, то Обзор основных понятий криптографии.

Поскольку a, b, M - неизвестны, то любые двое, объединившись, получат систему из двух уравнений относительно трех неизвестных.

Задача 3. Специалист по защите информации А разработал собственную систему авторизации на компьютере. Пользователь вводит пароль - трехзначное натуральное число. Компьютер делит это число на 31, полученный при этом остаток M умножает на 2 и получает число K. После этого число K делит на 23 и полученный остаток A сохраняет на жестком диске. Например, если N = 123, то М = 30, соответственно, К = 60 и А = 14. Если пользователь ввел пароль P, и после указанных вычислений получилось число, совпадающее с числом, хранящимся в памяти компьютера, то он получает доступ.

Пользователь Б решил использовать на своем компьютере такую же систему. Но чтобы А не подал на него в суд за кражу интеллектуальной собственности, решил поменять местами числа 23 и 31. То есть сначала стал делить на 23, а потом на 31.

Известно, что в компьютере А и в компьютере Б хранится число А = 5. Злоумышленник не знает паролей А и Б и поэтому перебирает их все подряд в случайном порядке. Чей компьютер он взломает быстрее?

Решение.

Всего различных паролей 900 (100 ≤ N ≤ 999). Вычислим, сколько из них дают в итоге число 5 по схеме пользователя А. Остаток 5 от деления на 23 дают натуральные числа 5, 28, 51. Больших чисел быть не может, так как K < 62 = 31∙2. Так как 5 и 51 - нечетные числа, то К = 2М = 28, значит, М = 14. Числа N, дающие остаток от деления на 31, равный 14, имеют вид N = 14 + 31s. Так как 100 ≤ N ≤ 999, то s = 3, 4, 5, …, 31. В итоге получаем 31 - 2 = 29 допустимых паролей (из 900 возможных).

Если те же вычисления провести по схеме Б, то получим следующих претендентов для числа К: 5, 36. Следовательно, М = 18 и N = 18 + 23s, где s = 4, 5, 6, …, 42. Итого 39 допустимых паролей.

Итак, вероятность взлома системы Б выше в 39/29 ≈ 1,34 раза, чем у А.

Задача 4.Столбцовая перестановка. Открытый текст, сохраняя пробелы между словами, записали в таблицу. Начало было в первой строке, текст записывали слева направо, переходя со строки на следующую, шифрование заключалось в перестановке столбцов. Найдите открытый текст.

Шифрованный текст:

Д

В

Ы

Т

Г

О

Е

Р

О

У

Ь

Д

У

Б

М

М

Я

Ы

Р

П


Решение. Присвоим столбцам номера в порядке их следования. Наша задача - найти такой порядок столбцов, при котором текст будет осмысленным.

Составим таблицу:

1

2

3

4

5

6

1

Х


2

Х


3

Х

4

Х

5


Х

6


Х

Клетка (k, m) в этой таблице означает, что столбец с номером m следует за столбцом с номером к. Знаком «Х» отметим невозможные случаи.

Сочетания столбцов 1, 2 и 5, 2 невозможны, так как гласная не может находиться перед мягким знаком. Невозможны и следования столбцов 2, 1 и 2, 5. Теперь из третьей строки следует, что 1, 5 и 5, 1 невозможны, так как УУ - нехарактерная для русского языка биграмма. Далее, два пробела подряд не могут быть в тексте, значит, ставим «Х» в клетках 3, 4 и 4, 3. Снова обратимся к третьей строке. Если бы столбец 2 следовал за столбцом 4, то слово началось бы с мягкого знака. Ставим «Х» в клетке 4, 2. Из первой строки: невозможна комбинация 4, 5, невозможна и 3, 5. Итог наших рассуждений представлен в таблице:



1

2

3

4

5

6

1

Х

Х

Х

2

Х

Х

Х

3

Х

Х

Х

4

Х

Х

Х

Х

5

Х

Х

Х

6


Х

Итак, после столбца 6 обязательно следует столбец 5. Но тогда поставим «Х» в клетке 6, 2 и получим: столбец 2 следует за столбцом 3. Далее, мы вычеркнули 5, 1 и 2, 1, следовательно, надо проверить варианты: …6532… и …65432… . Но (4, 3) вычеркнуто ранее. Итак, остались варианты:

1

6

5

3

2

4





6

5

3

2

4

1

4

1

6

5

3

2

1

4

6

5

3

2

Запишем 6, 5, 3, 2 столбцы подряд:

6

5

3

2

т

ы

-

в

о

р

о

г

б

у

д

ь

п

р

я

м

Попытка поставить столбец 1 перед столбцом 6 приведет к биграмме МП в последней строке и сочетанию ДТЫ в первой. Остались варианты: 653241, 146532.

Ответ: 653241 - ключ, открытый текст:

ты_в_д

ороге_

будь_у

прямым

(строка из популярной в 1970-е гг. песни).


Задача 5.Первый шифртекст получен из исходного текста перестановкой букв. Второй шифртекст получен из того же исходного текста заменой каждой буквы на другую букву так, что разные буквы заменены разными, а одинаковые - одинаковыми.

Восстановите исходный текст.

Первый шифртекст:

И Т Ш И Ь О К Т С О Г М А О Ф О К Е Т А П С С Е О Н С С Ы А В М Ь Ю З Т Ы Т А Ф О Ь В В Б А С О Ж Е З Т С И Н Й А Я Р Р Р Т О С Н М Я П Н Н О А Т Ш А О В О

Второй шифртекст:

Ф Я Р Ф Р У Ч Р Ф Ц Ы С А Б О В Я О Р Ц А Г Р Ф Ц Р Э Ц Ы Г Ф И Г Р Х Н Р Ш Ч Д Н В Ц В Т В Н Ч В Ч И Ж Р Ч В Х Д Г В И Ц Ф Э Ф Ц Р Л Т Р Ф Ц Ы М С А Б О В

Решение.Подсчитаем частоты букв первого шифртекста. Эти частоты будут частотами букв исходного текста, так как первый шифртекст получен перестановкой букв из исходного текста. Одновременно подсчитаем частоты шифробозначений второго текста.


Первый шифртекст

Второй шифртекст

О - 11

Р - 11

Т, А, С - 8

Ц, Ф, В - 8

Н - 5

Ч - 5

В - 4

Г - 4

И, Ь, М, Е, Р - 3

Ы, А, О, И, Н - 3

Ш, К, Ф, П, Ы, З, Я - 2

Я, С, Б, Э, Х, Д, Т - 2

Й, Г, Ю, Б, Ж - 1

У, Ш, Ж, Л, М - 1

Сразу можно сделать вывод: шифробозначению Р соответствует буква О открытого текста, Ч соответствует Н, а Г - В.

Будем постепенно «проявлять» текст. Запишем второй шифртекст (в нем порядок следования букв не менялся), заменяя уже известные нам шифробозначения их значениями (прописные буквы - это буквы открытого текста, строчные - шифробозначения):

фяОфОуНОфцысабов…

Далее, шифробозначение Ф скрывает одну из букв: Т, А, С. Шифробозначение Я скрывает либо букву Я, либо согласную. Предположим, что Я→Я, пробуем читать начало:

Ф→Т: ТЯОТО…

Ф→А: АЯОАО…

Ф→С: СЯОСО…

Не читается. Вывод: Я скрывает согласную, причем одну из следующих: Ш, К, Ф, П, З (вариант Я→Ы мы отбросили сразу). Но если Ф→Т, то слово не читается. Проверим вариант Ф→С. Пробуем читать: СяОСОуНОСцы…, и из всех возможных замен для Я подходит только П, тогда начало текста: СПОСОБНОСТЬ, и мы знаем теперь, что Я→П, У→Б, Ц→Т, Ы→Ь.

Обратим внимание на фрагмент …яорцагрфцрэцы… С учетом наших знаний это: ПоОТаВОСТОэТЬ, и мы находим еще соответствия: О→Р, А→И, Э→Я. Кроме того, так как Ф→С, Ц→Т, то из таблицы: В→А.

Теперь исследуем последний фрагмент текста: …фцрлтрфцымсабов. Заменим обозначения их значениями: …СТОлтОСТЬм… Обратимся к таблице. Обозначению Л соответствует одна из букв Й, Г, Ю, Б, Ж. Пробуем читать, получаем: Л→Й, и из таблицы: Т→К. Но тогда М→Ю, и слово получилось СТОЙКОСТЬЮ.

Теперь начало второй строки: …АТАКАнНА…, ясно, что Н→М. Далее, записываем вторую строку:

…АТАКАМНАНижОНАхдВАиТСЯСТОЙКОСТЬЮ…

И мы знаем: И→Е, Ж→Г, Х→З, Д→Ы.

Текст: «Способность шифра противостоять всевозможным атакам на него называется стойкостью шифра».

Задачи для самостоятельного решения.

1.Цифры заменены буквами, разные цифры- разными буквами, одинаковые -одинаковыми. В фразе

И ВСЕ ЖЕ ОН НЕ ПРАВ

Каждое слово является квадратом некоторого натурального числа. Найдите соответствие между цифрами и буквами.

2.Для подтверждения своих полномочий в компьютерной системе пользователь должен ввести свое имя и пароль, состоящий из 10 букв русского алфавита с исключенными Ё и Ь. Файл с паролями пользователей хранится на сервере в зашифрованном виде. Для их зашифрования использовался следующий способ. Буквам алфавита поставлены в соответствие числа от 0 до 30: А - 0, Б - 1,… , Я - 30. При зашифровании пароля каждую его букву заменяют остатком от деления на 31 значения выражения (6a3 + 5a2 + 6a + 20), где а - число, соответствующее заменяемой букве. В начале каждого сеанса работы введенный пользователем пароль зашифровывается и сравнивается с соответствующей записью в файле. При совпадении сеанс продолжается, а при расхождении пароль запрашивается снова. Злоумышленник хочет войти в систему под чужим именем, а соответствующий этому имени пароль не знает. Он написал программу, которая в случайном порядке перебирает пароли. Какой из двух паролей - «ШИФРОВАНИЕ» или «КРИПТОГРАФ» - устойчивее к действию этой программы?

3.А теперь Вы по заданию Центра должны проникнуть на сервер противника. Для этого Вам предстоит подобрать пароль к серверу методом "грубой силы" (последовательного перебора). Известно, что пароль назначается компьютером, регулярно меняется, а предыдущие пароли выглядели следующим образом (все буквы - латинские):

abStwdRd

pVtrKRLp

iryzhToz

URbhhbEH

OJEXHZmJ

pzTDXJrZ

Какие выводы надо сделать, чтобы ускорить процесс подбора пароля? (Время имеет значение!).

РЕШЕНИЯ

1.Заметим, что в этой задаче буквы Е и Ё не различаются, иначе цифр было бы 11.Двузначные числа, являющиеся квадратами: 16, 25, 36, 49, 64, 81.Запишем варианты для слов ЖЕ , ОН и НЕ:

ЖЕ ОН НЕ

16 16 16

25 25 25

36 36 36

49 49 49

64 64 64

81 81 81.

Вторая цифра числа из первого столбца должна совпадать со второй цифрой числа из третьего столбца, а первые цифры должны быть разными. Следовательно, либо ЖЕ=16,НЕ=36, либо ЖЕ=36,НЕ=16.Но первая цифра числа из третьего столбца совпадает со второй цифрой числа из второго столбца, поэтому остался единственный вариант: НЕ=16,ОН=81,ЖЕ=36.Теперь обратим внимание на слово ВСЕ. Этому слову соответствует число, последняя цифра которого 6.Квадрат двузначного числа оканчивается цифрой 6, следовательно, это двузначное число может иметь вторую цифру либо 4, либо 6.Такие числа : 14, 16, 24, 26.Но 142=196,а букве В не может соответствовать 1.Далее, 162=256,но тогда В=2, и слову ПРАВ соответствует число, оканчивающееся цифрой 2, что невозможно: квадрат натурального числа не может иметь последнюю цифру 2.Проверяем число 26, получаем: 262=676, но тогда В=6, то есть В=Е, противоречие. Вычисляем:242=576, и это единственный вариант для слова ВСЕ, не противоречащий условиям задачи. Итак,В=5.Значит, число, квадрат которого соответствует слову ПРАВ, оканчивается цифрой 5, но тогда последние две цифры числа, соответствующего ПРАВ, это 25, то есть А=2.Двузначное число, вторая цифра которого 5 и квадрат которого состоит из различных цифр, только одно, это 95, так что ПРАВ=9025.И для буквы И остался единственный вариант, это 4.Ответ: 4 576 36 81 16 9025.

2.В данной задаче необходимо вычислить все значения многочлена (6a3 + 5a2 + 6a + 20) по модулю 31 для всех чисел от 0 до 30. Результаты вычисления представлены в следующей таблице:

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Э

Ю

Я

20

6

7

28

12

26

13

9

19

17

8

28

20

20

2

2

25

14

5

3

13

9

27

10

25

15

16

2

9

11

13

Таким образом, слово «ШИФРОВАНИЕ» зашифруется строкой чисел «25, 19, 13, 25, 2, 7, 20, 20, 19, 26». Перечисленные числа в качестве шифрсимволов встречаются соответственно 2, 1, 3, 2, 3, 1, 3, 3, 1 и 1 раза в таблице. Следовательно, число различных паролей, в зашифрованном виде имеющих вид «25, 19, 13, 25, 2, 7, 20, 20, 19, 26» будет ровно 34⋅22 = 324.

Для слова «КРИПТОГРАФ» мы после шифрования получаем последовательность «8, 25, 19, 2, 5, 2, 28, 25, 20, 13». Аналогичный подсчет дает число различных паролей, зашифровывающихся такой же последовательностью, равное 34⋅23 = 648.

Пароль «ШИФРОВАНИЕ» в 2 раза надежнее, чем «КРИПТОГРАФ».

3.Нетрудно заметить, что каждый из паролей является строкой из 8 латинских символов в верхнем и нижнем регистрах. Таким образом, пространство перебора имеет вид {a…z A…Z}8. Мощность парольного пространства равна 528 ≈ 5,31013.

Для ускорения процесса подбора пароля необходимо обнаружить какие-либо закономерности в последовательности известных паролей, чтобы сократить пространство перебора.

Из приведенных в условии задачи паролей видно, что в каждом из них есть хотя бы одна буква в нижнем регистре и хотя бы одна - в верхнем. Можно предположить, что генератор парольных последовательностей исключает возможность генерации пароля, состоящего только из строчных или только из заглавных букв. Это предположение естественно, так как это является одним из классических критерием стойкости пароля к подбору.

Таким образом, из подбора следует исключить строки, состоящие только из строчных или только из заглавных букв. Это позволит уменьшить пространство перебора на 2268 ≈ 4,11011 попыток подбора.


© 2010-2022