Зашифрованное слово – Онлайн калькулятор: Шифр A1Z26

Онлайн калькулятор: Шифр Виженера

Так как Шифр Цезаря у нас уже есть, было бы логично дополнить его калькулятором, который шифрует/расшифровывает текст используя шифр Виженера.

Суть алгоритма шифрования проста. Шифр Виженера — это последовательность шифров Цезаря с различными значениями сдвига (ROTX — см. Шифр Цезаря). То есть к первой букве текста применяется преобразование, например, ROT5, ко второй, например, ROT17, и так далее. Последовательность применяемых преобразований определяется ключевой фразой, в которой каждая буква слова обозначает требуемый сдвиг, например, фраза ГДЕ ОН задает такую последовательность шифров Цезаря: ROT3-ROT4-ROT5-ROT15-ROT14, которая повторяется, пока не будет зашифрован весь текст сообщения.

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

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

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

Шифр Виженера
АлфавитАнглийскийИспанскийРусскийРусский (без ё)Квадрат Виженера начинается сROT0 («a» преобразуется в «а»)ROT1 («а» преобразуется в «б») Карл у Клары украл кораллыПреобразование

Преобразованный текст

 

save Сохранить share Поделиться extension Виджет

planetcalc.ru

Детские квесты: подборка идей — Прелесть и лапочка — LiveJournal

Поскольку пробный квест на деле оказался слишком уж простым, я озадачилась поиском более сложных задач
Тут все, конечно, очень индивидуально. Надо знать ребенка, его способности и опыт — встречал ли он уже какие-то похожие задания. Поэтому я не буду расписывать подробно весь сценарий, просто выпишу идеи. Некоторые из них уже опробованы нами, некоторые только в планах. Все в основном на возраст 6-7-8 лет, хотя многое можно упростить или наоборот усложнить — и тем самым расширить возрастные рамки.

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

Шифр с простой заменой — самый простой и самый очевидный вариант. Каждая буква — некий символ. Классика жанра — пляшущие человечки. Например, такие:


Наше задание:

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

Более сложный вариант — когда таблицы соответствий нет, поэтому их надо подобрать самим. Здорово, если дети сами обратят внимание на одинаковые буквы и одинаковые символы.


Загаданное слово — карта. У нас висит большая карта мира на стене — именно за нее была заткнута следующая записочка.

Литорея — вариация простой замены. Использовалась еще в древнерусских летописях.

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

б в г д ж з к л м н
щ ш ч ц х ф т с р п

употребляют в письме верхние буквы вместо нижних и наоборот, причём гласные остаются без перемены (лсошамь = словарь)

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

Решетка Кардано: я про нее уже писала в прошлом посте.

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

А высший пилотаж — зашифровать текст в тексте. Картинка из сети:

Также писала про зеркально отраженный текст

Чтобы понять написанное, надо поднести записку к зеркалу. Можно дать подсказку в духе «Спроси у своего отражения». А чтобы точно невозможно было прочитать без этого — пишите письменными буквами

Про анаграммы тоже писала. Перемешиваем буквы и/или пробелы в предложении — и пусть гадают, что там было изначально: ПО ДСТО ЛОМ или ПДО ЛСОТМО

Еще одна классика жанра — сдвоенные буквы. Кто-то сразу понимает,

on-the-cloud.livejournal.com

Простейшие методы шифрования текста

Методы: объяснительно-иллюстративный, частично-поисковый.

Цели.

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

Задачи:

образовательные:

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

развивающие:

  • развивать познавательную деятельность и творческие способности учащихся;
  • формировать логическое и абстрактное мышление;
  • развивать умение применять полученные знания в нестандартных ситуациях;
  • развивать воображение и внимательность;

воспитательные:

  • воспитывать коммуникативную культуру;
  • развивать познавательный интерес.

Предлагаемая разработка может быть использована для учащихся 7–9 классов. Презентация помогает сделать материал наглядным и доступным.

Общество, в котором живёт человек, на протяжении своего развития имеет дело с информацией. Она накапливается, перерабатывается, хранится, передаётся. (Слайд 2. Презентация)

А все ли и всегда должны знать всё?

Конечно, нет.

Люди всегда стремились скрыть свои секреты. Сегодня вы познакомитесь с историей развития тайнописи, узнаете простейшие способы шифрования. У вас появится возможность расшифровать послания.

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

Тайнопись – криптография — является ровесницей письменности. История криптографии насчитывает не одно тысячелетие. Идея создания текстов с тайным смыслом и зашифрованными сообщениями почти так же стара, как и само искусство письма. Этому есть много свидетельств. Глиняная табличка из Угарита (Сирия) – упражнения обучающие искусству расшифровки (1200 год до н.э.). “Вавилонская теодицея” из Ирака – пример акростиха (середина II тысячелетия до н.э.).

Один из первых систематических шифров был разработан древними евреями; этот метод называется темура — “обмен”.

Самый простой из них “Атбаш”, алфавит разделялся посередине так, чтобы первые две буквы, А и Б, совпадали с двумя последними, Т и Ш. Использование шифра темура можно обнаружить в Библии.  Это пророчество Иеремии, сделанное в начале VI века до нашей эры, содержит проклятие, всем правителям мира, заканчивая “царем Сесаха” который при дешифровки с шифра “Атбаш” оказывается царём Вавилона.

(Слайд 3) Более хитроумный способ шифрования был изобретён в древней Спарте во времена Ликурга (V век до н.э.) Для зашифровывания текста использовалась Сциталла — жезл цилиндрической формы, на который наматывалась лента из пергамента. Вдоль оси цилиндра построчно записывался текст, лента сматывалась с жезла и передавалась адресату, имеющему Сциталлу такого же диаметра. Этот способ осуществлял перестановку букв сообщения. Ключом шифра служил диаметр Сциталлы. АРИСТОТЕЛЬ придумал метод вскрытия такого шифра. Он изобрёл дешифровальное устройство “Антисциталла”.

(Слайд 4) Задание “Проверь себя”

(Слайд 5) Греческий писатель ПОЛИБИЙ использовал систему сигнализации, которая применялась как метод шифрования. С его помощью можно было передавать абсолютно любую информацию. Он записывал буквы алфавита в квадратную таблицу и заменял их координатами. Устойчивость этого шифра была велика. Основной причиной этого являлась возможность постоянно менять последовательность букв в квадрате.

(Слайд 6) Задание “Проверь себя”

(Слайд 7) Особую роль в сохранении тайны сыграл способ шифрования, предложенный ЮЛИЕМ ЦЕЗАРЕМ и описанный им в “Записках о галльской войне.

(Слайд 8) Задание “Проверь себя”

(Слайд 9) Существует несколько модификаций шифра Цезаря. Один из них алгоритм шифра Гронсфельда (созданный в 1734 году бельгийцем Хосе де Бронкхором, графом де Гронсфельд, военным и дипломатом). Шифрование заключается в том, что величина сдвига не является постоянной, а задается ключом (гаммой).

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

(Слайд 11) Научные методы в криптографии впервые появились в арабских странах. Арабского происхождения и само слово шифр (от арабского «цифра»). Арабы первыми стали заменять буквы цифрами с целью защиты исходного текста. О тайнописи и её значении говорится даже в сказках “Тысячи и одной ночи”. Первая книга, специально посвящённая описанию некоторых шифров, появилась в 855 г., она называлась “Книга о большом стремлении человека разгадать загадки древней письменности”.

(Слайд 12) Итальянский математик и философ ДЖЕРОЛАМО КАРДАНО написал книгу «О тонкостях», в которой имеется часть, посвященная криптографии.

Его вклад в науку криптография содержит два предложения:

Первое — использовать открытый текст в качестве ключа.

Второе — он предложил шифр, называемый ныне «Решетка Кардано».

Кроме данных предложений Кардано дает «доказательство» стойкости шифров, основанное на подсчете числа ключей.

Решётка Кардано представляет собой лист из твердого материала, в котором через неправильные интервалы сделаны прямоугольные вырезы высотой для одной строчки и различной длины. Накладывая эту решетку на лист писчей бумаги, можно было записывать в вырезы секретное сообщение. Оставшиеся места заполнялись произвольным текстом, маскирующим секретное сообщение. Этим методом маскировки пользовались многие известные исторические лица, кардинал Ришелье во Франции и русский дипломат А. Грибоедов. На основе такой решетки Кардано построил шифр перестановки.

(Слайд 13) Задание “Проверь себя”

(Слайд 14) Увлекались тайнописью и в России. Используемые шифры — такие же, как в западных странах — значковые, замены, перестановки.

Датой появления криптографической службы в России следует считать 1549 год (царствование Ивана IV), с момента образования «посольского приказа», в котором имелось «цифирное отделение».

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

(Слайд 15) Задание “Проверь себя”

(Слайд 16) Много новых идей в криптографии принес XIX век. ТОМАС ДЖЕФФЕРСОН создал шифровальную систему, занимающую особое место в истории криптографии — «дисковый шифр». Этот шифр реализовывался с помощью специального устройства, которое впоследствии назвали шифратором Джефферсона.

В 1817 г. ДЕСИУС УОДСВОРТ сконструировал шифровальное устройство, которое внесло новый принцип в криптографию. Нововведение состояло в том, что он сделал алфавиты открытого и шифрованного текстов различных длин. Устройство, с помощью которого он это осуществил, представляло собой диск, с двумя подвижными кольцами с алфавитами. Буквы и цифры внешнего кольца были съемными и могли собираться в любом порядке. Эта шифрсистема реализует периодическую многоалфавитную замену.

(Слайд 17) Способов кодирования информации можно привести много.

Капитан французской армии ШАРЛЬ БАРБЬЕ разработал в 1819 году систему кодирования ecriture noctrume – ночное письмо. В системе применялись выпуклые точки и тире, недостаток системы её сложность, так как кодировались не буквы, а звуки.

ЛУИ БРАЙЛЬ усовершенствовал систему, разработал собственный шифр. Основы этой системы используются поныне.

(Слайд 18) СЭМЮЕЛЬ МОРЗЕ разработал в 1838 году систему кодирования символов с помощью точки и тире. Он же является изобретателем телеграфа (1837год) – устройства в котором использовалась эта система. Самое важное в этом изобретении – двоичный код, то есть использованием для кодирования букв только двух символов.

(Слайд 19) Задание “Проверь себя”

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

В истории криптографии XIX в. ярко запечатлелось имя ОГЮСТА КЕРКГОФФСА. В 80-х годах XIX века издал книгу «Военная криптография» объемом всего в 64 страницы, но они обессмертили его имя в истории криптографии. В ней сформулированы 6 конкретных требований к шифрам, два из которых относятся к стойкости шифрования, а остальные — к эксплуатационным качествам. Одно из них («компрометация системы не должна причинять неудобств корреспондентам») стало называться «правилом Керкгоффса». Все эти требования актуальны и в наши дни.

В XX веке криптография стала электромеханической, затем электронной. Это означает, что основными средствами передачи информации стали электромеханические и электронные устройства.

(Слайд 21) Во второй половине XX века, вслед за развитием элементной базы вычислительной техники, появились электронные шифраторы. Сегодня именно элек

urok.1sept.ru

Игры-шифровки — Летидор

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

Белые пятна

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

Например, вот во что превращается простое и понятное предложение «Встречаемся на берегу озера»«В стре чаем с Янабер егуоз ера».

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

Без гласных

Либо можно воспользоваться таким методом – писать текст без гласных букв.

Для примера привожу такое предложение: «Записка лежит в дупле дуба, который стоит на опушке леса». Шифрованный текст выглядит так: «Зпска лжт в дпл дб, ктр стт н пшке лс».

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

Читай наоборот

Эта шифровка объединяет в себе сразу два метода. Текст нужно читать справа налево (то есть наоборот), причем пробелы между словами могут быть расставлены наобум.

Вот, прочтите и расшифруйте: «Нелета минвь дуб, маноро тсоп иртомс».

Второй за первого

Либо каждую букву алфавита можно обозначить следующей за ней буквой. То есть вместо «а» мы пишем «б», вместо «б» напишем «в», вместо «в» — «г» и так далее.

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

Разгадайте, что за фразу мы для вас зашифровали: «Тьъйлб г тжсйбмж фиобуэ мждлп – по ожлпдеб ож тойнбжу щмарф».

Заместители

По такому же принципу, как и предыдущий шифр, используется метод «Замена». Я читала, что его использовали для шифровки священных иудейских текстов.

Вместо первой буквы алфавита мы пишем последнюю, вместо второй – предпоследнюю и так далее. То есть вместо А – Я, вместо Б – Ю, вместо В – Э…

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

Таблицы

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

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

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

Пробел будем обозначать буквой «р», слова пишем сверху вниз. Таблица 3 на 3 (рисуем в клеточках обычного тетрадного листа).

Вот что у нас получается:
Н Ь И М О Т К А Й
О Ю Д Р В Ь А С Р
Ч Р Е Л И Р Р Е .

Решетка

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

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

Ключ в книге

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

Записки выглядели примерно так:
«324 с, 4 а, в, 7 сл.
150 с, 1 а, н, 11 сл….»

Первая цифра обозначала номер страницы,
вторая – номер абзаца,
третья буква – как надо считать абзацы сверху (в) или снизу (н),
четвертая буква – слово.

В моем примере нужные слова нужно искать:
Первое слово: на странице 324, в 4 абзаце сверху, седьмое слово.
Второе слово: на странице 150, в 1 абзаце снизу, одиннадцатое слово.

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

letidor.ru

Самые действенные способы кодирования. Топ-10: кодов и шифров

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


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

2. ROT1
Этот шифр знаком многим детям. Ключ к шифру очень прост: каждая буква алфавита заменяется на последующую букву, поэтому, А заменяется на Б, Б заменяется на В, и так далее. «ROT1» буквально означает «вращать на 1 букву вперед по алфавиту». Фраза, «Я все знаю» превратится в секретную фразу «А гтё кобя». Этот шифр предназначен для развлечения, потому что его, легко понять и использовать, и столь же легко расшифровать, даже если ключ используется в обратном направлении.

3. Перестановка
В перестановочном шифре буквы переставляются с использованием некоторых заданных правил или ключей. Например, слова могут быть записаны в обратном направлении, так что фраза «рад видеть вас» превращается во фразу «дар ьтедив сав». Другой перестановочный ключ заключается в перестановке каждой пары букв, так что предыдущее сообщение становится «ар вд ди те вь са». Такие шифры использовались для того, чтобы отправлять конфиденциальные сообщения во время Первой мировой войны и Гражданской войны в США. На первый взгляд, кажется, что сложные правила перестановки могут сделать эти шифры очень трудными. Однако, многие зашифрованные сообщения могут быть расшифрованы с использованием анаграмм или современных компьютерных алгоритмов, которые перебирают тысячи возможных ключей перестановки.

4. Код Морзе (Азбука Морзе)
Несмотря на свое название, код Морзе не является кодом — это шифр. Каждая буква алфавита, цифры от 0 до 9 и некоторые символы пунктуации заменены на последовательность коротких и длинных звуковых сигналов, которые часто называют «точка и тире». А становится «• — «, Б становится « — • • •” и так далее. В отличие от большинства других шифров, код Морзе не используется для сокрытия сообщений. Код Морзе начал широко применяться с изобретением телеграфа Сэмюэлем Морзе. Это было первое широко используемое электрическое приспособление для передачи сообщений на дальние расстояния. Телеграф произвел революцию в средствах массовой информации и позволял немедленно передавать сообщения о событиях, произошедшие в одной стране, по всему миру. Код Морзе изменил характер войны, позволяя обеспечивать мгновенную связь с войсками на большом расстоянии.

5. Шифр Цезаря
Шифр Цезаря (сдвижной), называется так потому, что он использовался Юлием Цезарем. Шифр состоит на самом деле из 33 различных шифров (количество шифров меняется в зависимости от алфавита используемого языка), по одной на каждую букву алфавита. «ROT1» является лишь одним из этих шифров. Человек должен был знать, какой шифр Цезаря использовать для того, чтобы расшифровать сообщение. Если используется шифр Ё, то, А становится Ё, Б становится Ж, В становится З, и так далее по алфавиту. Если используется шифр Ю, то, А становится Ю, Б становится Я, В становится, А, и так далее. Данный алгоритм является основой для многих более сложных шифров, но сам по себе не обеспечивает надежную защиту тайны сообщений, поскольку проверка 33-х различных ключей шифра займет относительно небольшое время.

6. Моноалфавитная замена
ROT1, шифр Цезаря и азбука Морзе относятся к одному и тому же типу — моноалфавитной замене, а это означает, что каждая буква алфавита заменяется в соответствии с ключом, другой буквой или символом. На самом деле их легко расшифровать, даже не зная ключа. Наиболее употребительной буквой в английском языке является буква Е. Таким образом, во многих моноалфавитных шифрах, наиболее употребительной буквой или символом также будет E (прим. переводчика. — в русском языке наиболее употребительная — это буква О). Вторая наиболее употребительная буква в английском языке — это T, и третьей является буква, А, поэтому эти две буквы также могут быть определены для дешифрования. С этой точки зрения, человек может расшифровать сообщение с использованием частотности английских букв, или он может искать почти полные слова, такие как «T_E», которое наиболее вероятным образом является «THE».

7. Шифр Виженера
Данный алгоритм является более сложным, чем моноалфавитныя замена. Его ключевыми словами являются, такие слова, как например «CHAIR». Первая буква сообщения с ключевым словом «CHAIR» будет закодирована с алфавитным шифром С, вторая буква с алфавитным шифром Н и так продолжается до последней буквы ключевого слова. Ключевое слово состоит всего из пяти букв, так что для шестой буквы сообщения снова будет использоваться алфавитный шифр С. Длительное времени считалось, что Шифр Виженера взломать невозможно. Чтобы его расшифровать, прежде всего, надо найти длину ключевого слова. Если ключевое слово состоит из пяти букв, то буквы с номерами 1, 6, 11, 16, 21, и т.д. будут соответствовать первой букве ключевого слова, и анализ частотности букв позволит расшифровать сообщение. Декодеровщик затем переходит на буквы 2, 7, 12, 17, и так далее. Если ключевое слово, действительно состоит из пяти букв, то расшифровать сообщение будет несложно. Если нет, то надо найти другое ключевое слово, и снова повторить процесс.

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

9. Код Энигма
Код Энигма, который был очень сложным шифром, использовался немцами во время Второй Мировой войны. Для этого использовали машину Энигма, которая очень похожа на пишущую машинку, при нажатии на определенную букву на экране загоралась буква шифра. Машина имела несколько колес, которые были связаны с буквами проводами, для определения, какая буква шифра будет высвечиваться. Все машины Энигма были идентичны, и начальная конфигурация колес была ключом к шифрованию сообщений. Чтобы усложнить процесс, колесо должно было вращаться после того, как определённое количество букв было напечатано. Немецкое командование каждый день выдавало списки начальной конфигурации колес для использования в шифровании, так что все немецкие командиры использовали одну и ту же конфигурацию, и могли расшифровать сообщения друг друга. Даже когда союзники заполучили копию машины, они все равно не могли расшифровать сообщения, поскольку машина выдавала сотню триллионов возможных начальных конфигураций колес. Код Энигма был взломан польскими умельцами и окончательно расшифрован англичанами, которые использовали смекалку и компьютеры. Знание немецких коммуникационных систем дало союзникам значительное преимущество в ходе войны, а процесс взлома кода Энигма позволил создать первый прообраз компьютера.

10. Криптография с открытыми ключами
Это самый современный шифр, и он имеет несколько вариантов. Это шифр, который используется во всем мире, и имеет два ключа: один открытый и один личный. Открытый ключ — это большое число, доступное всем. Ключ является таким сложным потому что при делении можно получить только два целых числа (кроме 1 и самого числа). Эти два числа и есть личный ключ, и, если их перемножить, получится открытый ключ. Например, открытый ключ может быть 1961, следовательно, личный ключ — это 37 и 53. Открытый ключ используется для шифрования сообщения, и сообщение невозможно расшифровать без личного ключа. При отправке личных данных в банк, или когда ваша банковская карта обрабатывается машиной, данные зашифрованы именно таким образом, и только банк со своим личным ключом может получить к ним доступ. Причина, почему этот способ является настолько безопасным, заключается в том, что математически очень трудно найти делители больших чисел. Для улучшения безопасности до 2007 года компания «RSA Laboratories» выплачивала деньги любому, кто сможет найти два делителя для чисел, которые она предлагала. Вот сравнительно легкий пример, который стоил 1000 долларов, вам предлагается найти два 50-значных делителя для числа: 15226050279225333605356183781326374 29718068114961380688657908494580 12296325895289765400350692006139

xenon13.livejournal.com

Введение в криптографию и шифрование, часть первая. Лекция в Яндексе

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


Мы впервые публикуем эту лекцию вместе с расшифровкой. Начнём с первой части. Под катом вы найдёте текст и часть слайдов.

Я когда-то читал в МГУ лекции по крипте, и они занимали у меня по полгода. Я попытаюсь вам всё рассказать за два с половиной часа. Никогда этого не делал. Вот и попробуем.

Кто понимает, что такое DES? AES? TLS? Биноминальное отображение?

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

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

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

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

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

Современные и коммерчески доступные системы шифрования — все или почти все или лучшие из них — построены из компонент, устройство и принцип работы которых хорошо известны. Единственная секретная вещь в них — ключ шифрования. Есть только одно известное мне значимое исключение — набор секретных криптографических протоколов для всевозможных государственных организаций. В США это называется NSA suite B, а в России это всякие странные секретные алгоритмы шифрования, которые до определенной степени используются военными и государственными органами.

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

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

Первый криптографический примитив — симметричные шифры.

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

Какие здесь важные нюансы? В большинстве распространенных алгоритмов симметричного шифрования, с которыми можно столкнуться, размер шифротекста всегда равен размеру открытого текста. Современные алгоритмы шифрования оперируют размерами ключей. Размер ключей измеряется в битах. Современный размер — от 128 до 256 бит для алгоритмов симметричного шифрования. Об остальном, в том числе о размере блока, мы поговорим позже.

Исторически, в условном IV веке до нашей эры, существовало два метода дизайна шифров: шифры подстановки и перестановки. Шифры подстановки — алгоритм, где в те времена заменяли одну букву сообщения на другую по какому-то принципу. Простой шифр подстановки — по таблице: берем таблицу, где написано, что А меняем на Я, Б на Ю и т. д. Дальше по этой таблице шифруем, по ней же дешифруем.

Как вы считаете, с точки зрения размера ключа насколько это сложный алгоритм? Сколько вариантов ключей существует? Порядок факториала длины алфавита. Мы берем таблицу. Как мы ее строим? Допустим, есть таблица на 26 символов. Букву А можем заменить на любой из них, букву Б — на любой из оставшихся 25, С — на любой из оставшихся 24… Получаем 26*25*24*… — то есть факториал от 26. Факториал размерности алфавита.

Если взять log226!, это будет очень много. Думаю, вы точно получите в районе 100 бит длины ключа, а то и поболее. Оказалось, что с точки зрения формального представления стойкости указанный алгоритм шифрования — довольно неплохой. 100 бит — приемлемо. При этом все, наверное, в детстве или юности, когда сталкивались с кодировками, видели, что такие алгоритмы дешифруются тривиально. Проблем с расшифровкой нет.

Долго существовали всякие алгоритмы подстановки в разных конструкциях. Одним из них, еще более примитивным, является шифр Цезаря, где таблица формируется не случайной перестановкой символов, а сдвигом на три символа: А меняется на D, B на Е и т. д. Понятно, что шифр Цезаря вместе со всеми его вариантами перебрать очень легко: в отличие от табличной подстановки, в ключе Цезаря всего 25 вариантов при 26 буквах в алфавите — не считая тривиального шифрования самого в себя. И его как раз можно перебрать полным перебором. Здесь есть некоторая сложность.

Почему шифр табличной подстановки такой простой? Откуда возникает проблема, при которой мы можем легко, даже не зная ничего про криптографию, расшифровать табличную подстановку? Дело в частотном анализе. Есть самые распространенные буквы — какая-нибудь И или Е. Их распространенность велика, гласные встречаются намного чаще, чем согласные, и существуют негативные пары, никогда не встречающиеся в естественных языках, — что-то вроде ЬЪ. Я даже давал студентам задание сделать автоматический дешифратор шифра подстановки, и, в принципе, многие справлялись.

В чем проблема? Надо статистику распределения букв исказить, чтобы распространенные буквы не так светились в зашифрованном тексте. Очевидный способ: давайте будем шифровать самые часто встречающиеся буквы не в один символ, а в пять разных, например. Если буква встречается в среднем в пять раз чаще, то давайте по очереди — сначала в первый символ будем зашифровывать, потом во второй, в третий и т. д. Далее у нас получится маппинг букв не 1 к 1, а, условно, 26 к 50. Статистика, таким образом, нарушится. Перед нами первый пример полиалфавитного шифра, который как-то работал. Однако с ним есть довольно много проблем, а главное, очень неудобно работать с таблицей.

Дальше придумали: давайте не будем шифровать такими таблицами, а попробуем брать шифр Цезаря и для каждой следующей буквы изменять сдвиг. Результат — шифр Виженера.

Берем в качестве ключа слово ВАСЯ. Берем сообщение МАША. Задействуем шифр Цезаря, но отсчитывая от этих букв. Например, В — третья буква в алфавите. Мы должны сдвинуть на три буквы соответствующую букву в открытом тексте. М сдвигается в П. А в А. Ш — на 16, перескочим букву А, получим, условно, Д. Я сдвинет А в Я. ПАДЯ.

Что удобно в получившемся шифре? Здесь было две одинаковых буквы, но в результате они зашифровались в разные. Это классно, потому что размывает статистику. Метод хорошо работал, пока где-то в XIX веке, буквально недавно на фоне истории криптографии, не придумали, как его ломать. Если посмотреть на сообщение из нескольких десятков слов, а ключ довольно короткий, то вся конструкция выглядит как несколько шифров Цезаря. Мы говорим: окей, давайте каждую четвертую букву — первую, пятую, девятую — рассматривать как шифр Цезаря. И поищем среди них статистические закономерности. Мы обязательно их найдем. Потом возьмем вторую, шестую, десятую и так далее. Опять найдем. Тем самым мы восстановим ключ. Единственная проблема — понять, какой он длины. Это не очень сложно, ну какой он может быть длины? Ну 4, ну 10 символов. Перебрать 6 вариантов от 4 до 10 не очень сложно. Простая атака — она была доступна и без компьютеров, просто за счет ручки и листа бумаги.

Как из этой штуки сделать невзламываемый шифр? Взять ключ размера текста. Персонаж по имени Клод Шэннон в ХХ веке, в 1946 году, написал классическую первую работу по криптографии как по разделу математики, где сформулировал теорему. Длина ключа равна длине сообщения — он использовал XOR вместо сложения по модулю, равному длине алфавита, но в данной ситуации это не очень принципиально. Ключ сгенерирован случайным образом, является последовательностью случайных бит, и на выходе тоже получится случайная последовательность бит. Теорема: если у нас есть такой ключ, то подобная конструкция является абсолютно стойкой. Доказательство не очень сложное, но сейчас не буду про него говорить.

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

Возьмем два сообщения: МАША, зашифрованная ключом ВАСЯ, и другое слово, у которого ключ тоже был ВАСЯ, — ВЕРА. Получим примерно следующее: ЗЕШЯ. Сложим два полученных сообщения, причем так, чтобы два ключа взаимно удалились. В итоге получим лишь разницу между осмысленным шифротекстом и осмысленным шифротекстом. На XOR это делается удобнее, чем на сложении по длине алфавита, но разницы практически никакой.

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

Помимо шифров подстановки, были еще шифры перестановки. С ними тоже все довольно просто. Берем сообщение ВАСЯИ, записываем его в блок какой-то длины, например в ДИДОМ, и считываем результат так же.

Не бог весть какая штука. Как ее ломать, тоже понятно — переберем все возможные варианты перестановок. Тут их не очень много. Берем длину блока, подбираем и восстанавливаем.

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

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

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

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

Из этой истории есть одно занятное исключение — шифроблокноты. Речь идет о настоящей шпионской истории про настоящий шпионаж. Некие люди, которым нужна абсолютно устойчивая коммуникация, генерируют случайные числа — например, буквальным бросанием кубика или буквальным выниманием шаров из барабана, как в лото. Создают два листа, где печатают эти случайные числа. Один лист отдают получателю, а второй оставляют у отправителя. При желании пообщаться они используют этот поток случайных чисел в качестве ключевого потока. Нет, история взята не из совсем далекого прошлого. У меня есть настоящий радиоперехват от 15 октября 2014 года: 7 2 6, 7 2 6, 7 2 6. Это позывной. 4 8 3, 4 8 3, 4 8 3. Это номер шифроблокнота. 5 0, 5 0, 5 0. Это количество слов. 8 4 4 7 9 8 4 4 7 9 2 0 5 1 4 2 0 5 1 4 и т. д. 50 таких числовых групп. Не знаю где, где-то не в России сидел какой-нибудь человек с ручкой и карандашом у обычного радиоприемника и записывал эти цифры. Записав их, он достал похожую штуку, сложил их по модулю 10 и получил свое сообщение. Другими словами, это реально работает, и подобное сообщение нельзя взломать. Если действительно были сгенерированы хорошие случайные числа и он впоследстии сжег бумажку с ключом, то осуществить взлом нельзя никак, совсем.

Но тут есть довольно много проблем. Первая — как нагенерировать по-настоящему хорошие случайные числа. Мир вокруг нас детерминирован, и если мы говорим про компьютеры, они детерминированы полностью.

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

Самый исторически распространенный алгоритм подобного рода называется RC4. Он был разработан Роном Ривестом лет 25 назад и активно использовался очень долго, был самым распространенным алгоритмом для TLS, всех его различных вариантов, включая HTTPS. Но в последнее время RC4 начал показывать свой возраст. Для него существует некоторое количество атак. Он активно используется в WEP. Была одна хорошая лекция Антона, история, которая показывает: плохое применение пристойного даже по нынешним меркам алгоритма шифрования приводит к тому, что компрометируется вся система.

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

Большое достоинство RC4 — в том, что он целиком внутрибайтовый, а значит, его программная реализация работает довольно быстро — сильно быстрее, в разы, если не в десятки раз быстрее, чем сравнимый и существовавший примерно в одно время с ним шифр DES. Поэтому RC4 и получил такое распространение. Он долго был коммерческим секретом компании RSA, но потом, где-то в районе 90-х годов, некие люди анонимно опубликовали исходники его устройства в списке рассылки cypherpunks. В результате возникло много драмы, были крики, мол, как же так, какие-то неприличные люди украли интеллектуальную собственность компании RSA и опубликовали ее. RSA начала грозить всем патентами, всевозможными юридическими преследованиями. Чтобы их избежать, все реализации алгоритма, которые находятся в опенсорсе, называются не RC4, а ARC4 или ARCFOUR. А — alleged. Речь идет о шифре, который на всех тестовых кейсах совпадает с RC4, но технически вроде как им не является.

Если вы конфигурируете какой-нибудь SSH или OpenSSL, вы в нем не найдете упоминания RC4, а найдете ARC4 или что-то подобное. Несложная конструкция, он уже старенький, на него сейчас есть атаки, и он не очень рекомендуется к использованию.

Было несколько попыток его заменить. Наверное, на мой предвзятый взгляд самым успешным стал шифр Salsa20 и несколько его последователей от широко известного в узких кругах персонажа Дэна Берштайна. Линуксоидам он обычно известен как автор qmail.

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

Salsa20 устроен так, чтобы он всегда выполнялся за константное одинаковое время. Внутри он состоит всего из трех примитивов: это сдвиг на константное время, а также сложение по модулю 2 и по модулю 32, 32-битных слов. Скорость Salsa20 еще выше, чем у RC4. Он пока что не получил такого широкого распространения в общепринятой криптографии — у нас нет cipher suite для TLS, использующих Salsa20, — но все равно потихоньку становится мейнстримом. Указанный шифр стал одним из победителей конкурса eSTREAM по выбору лучшего поточного шифра. Их там было четыре, и Salsa — один из них. Он потихоньку начинает появляться во всяких опенсорс-продуктах. Возможно, скоро — может, через пару лет — появятся даже cipher suite в TLS с Salsa20. Мне он очень нравится.

На него имеется некоторое количество криптоанализа, есть даже атаки. Снаружи он выглядит как поточный, генерируя на основе ключа последовательность почти произвольной длины, 264. Зато внутри он работает как блочный. В алгоритме есть место, куда можно подставить номер блока, и он выдаст указанный блок.

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

Если данные, например гигабайтный файл целиком, зашифрованы на диске поточным шифром, то чтобы прочитать последние 10 байт, вам нужно будет сначала сгенерировать гаммы потока шифра на 1 гигабайт, и уже из него взять последние 10 байт. Очень неудобно.

В Salsa указанная проблема решена, поскольку в нем на вход поступает в том числе и номер блока, который надо сгенерировать. Дальше к номеру блока 20 раз применяется алгоритм. 20 раундов — и мы получаем 512 бит выходного потока.

Самая успешная атака — в 8 раундов. Сам он 256-битный, а сложность атаки в 8 раундов — 250 или 251 бит. Считается, что он очень устойчивый, хороший. Публичный криптоанализ на него есть. Несмотря на всю одиозность личности Берштайна в этом аспекте, мне кажется, что штука хорошая и у нее большее будущее.

Исторически поточных шифров было много. Они первые не только в коммерческом шифровании, но и в военном. Там использовалось то, что называлось линейными регистрами сдвига.

Какие тут проблемы? Первая: в классических поточных шифрах, не в Salsa, чтобы расшифровать последнее значение гигабайтного файла, последний байт, вам нужно сначала сгенерировать последовательность на гигабайт. От нее вы задействуете только последний байт. Очень неудобно.

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

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

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

Размер блока в современных шифрах — как правило, 128 бит. Бывают разные вариации, но как правило, речь идет про 128 или 256 бит, не больше и не меньше. Размер ключа — точно такой же, как для поточных алгоритмов: 128 или 256 бит в современных реализациях, от и до.

Из всех широко распространенных блочных шифров сейчас можно назвать два — DES и AES. DES очень старый шифр, ровесник RC4. У DES сейчас размер блока — 64 бита, а размер ключа — 56 бит. Создан он был в компании IBM под именем Люцифер. Когда в IBM его дизайном занимался Хорст Фейстель, они предложили выбрать 128 бит в качестве размера блока. А размер ключа был изменяемый, от 124 до 192 бит.

Когда DES начал проходит стандартизацию, его подали на проверку в том числе и в АНБ. Оттуда он вернулся с уменьшенным до 64 бит размером блока и уменьшенным до 56 бит размером ключа.

20 лет назад вся эта история наделала много шума. Все говорили — наверняка они туда встроили закладку, ужасно, подобрали такой размер блока, чтобы получить возможность атаковать. Однако большое достоинство DES в том, что это первый шифр, который был стандартизован и стал тогда основой коммерческой криптографии.

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

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

У нее есть несколько интересных достоинств. Первое важное достоинство: функция F может быть любой. Она не должна обладать свойствами обратимости, она может и не быть линейной или нелинейной. Все равно шифр остается симметричным.

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

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

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

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

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

И наконец, окончательная перестановка P. Она опять перемешивает 32 бита между собой. Все очень несложно, раундовая функция максимально простая.

Самое интересное ее свойство заключается в указанных S-боксах: задумано очень сложное превращение 6 бит в 4. Если посмотреть на всю конструкцию, видно, что она состоит из XOR и пары перестановок. Если бы S-боксы были простыми, весь DES фактически представлял бы собой некоторый набор линейных преобразований. Его можно было бы представить как матрицу, на которую мы умножаем наш открытый текст, получая шифротекст. И тогда атака на DES была бы тривиальной: требовалось бы просто подобрать матрицу.

Вся нелинейность сосредоточена в S-боксах, подобранных специальным образом. Существуют разные анекдоты о том, как именно они подбирались. В частности, примерно через 10 лет после того, как DES был опубликован и стандартизован, криптографы нашли новый тип атак — дифференциальный криптоанализ. Суть атаки очень простая: мы делаем мелкие изменения в открытом тексте — меняя, к примеру, значение одного бита с 0 на 1 — и смотрим, что происходит с шифротекстом. Выяснилось, что в идеальном шифре изменение одного бита с 0 на 1 должно приводить к изменению ровно половины бит шифротекста. Выяснилось, что DES, хоть он и был сделан перед тем, как открыли дифференциальный криптоанализ, оказался устойчивым к этому типу атак. В итоге в свое время возникла очередная волна паранойи: мол, АНБ еще за 10 лет до открытых криптографов знало про существование дифференциального криптоанализа, и вы представляете себе, что оно может знать сейчас.

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

56 бит сейчас уже можно просто перебрать на кластере машин общего назначения — может, даже на одном. И это плохо. Что можно предпринять?

Просто сдвинуть размер ключа нельзя: вся конструкция завязана на его длину. Triple DES. Очевидный ответ был таким: давайте мы будем шифровать наш блок несколько раз, устроим несколько последовательных шифрований. И здесь всё не слишком тривиально.

Допустим, мы берем и шифруем два раза. Для начала нужно доказать, что для шифрований k1 и k2 на двух разных ключах не существует такого шифрования на ключе k3, что выполнение двух указанных функций окажется одинаковым. Здесь вступает в силу свойство, что DES не является группой. Тому существует доказательство, пусть и не очень тривиальное.

Окей, 56 бит. Давайте возьмем два — k1 и k2. 56 + 56 = 112 бит. 112 бит даже по нынешним меркам — вполне приемлемая длина ключа. Можно считать нормальным всё, что превышает 100 бит. Так почему нельзя использовать два шифрования, 112 бит?

Одно шифрование DES состоит из 16 раундов. Сеть применяется 16 раз. Изменения слева направо происходят 16 раз. И он — не группа. Есть доказательство того, что не существует такого ключа k3, которым мы могли бы расшифровать текст, последовательно зашифрованный выбранными нами ключами k1 и k2.

Есть атака. Давайте зашифруем все возможные тексты на каком-нибудь ключе, возьмем шифротекст и попытаемся его расшифровать на всех произвольных ключах. И здесь, и здесь получим 256 вариантов. И где-то они сойдутся. То есть за два раза по 256 вариантов — плюс память для хранения всех расшифровок — мы найдем такую комбинацию k1 и k2, при которых атака окажется осуществимой.

Эффективная стойкость алгоритма — не 112 бит, а 57, если у нас достаточно памяти. Нужно довольно много памяти, но тем не менее. Поэтому решили — так работать нельзя, давайте будем шифровать три раза: k1, k2, k3. Конструкция называется Triple DES. Технически она может быть устроена по-разному. Поскольку в DES шифрование и дешифрование — одно и то же, реальные алгоритмы иногда выглядят так: зашифровать, расшифровать и снова расшифровать — чтобы выполнять операции в аппаратных реализациях было проще.

Наша обратная реализация Triple DES превратится в аппаратную реализацию DES. Это может быть очень удобно в разных ситуациях для задачи обратной совместимости.

Где применялся DES? Вообще везде. Его до сих пор иногда можно пронаблюдать для TLS, существуют cipher suite для TLS, использующие Triple DES и DES. Но там он активно отмирает, поскольку речь идет про софт. Софт легко апдейтится.

А вот в банкоматах он отмирал очень долго, и я не уверен, что окончательно умер. Не знаю, нужна ли отдельная лекция о том, как указанная конструкция устроена в банкоматах. Если коротко, клавиатура, где вы вводите PIN, — самодостаточная вещь в себе. В нее загружены ключи, и наружу она выдает не PIN, а конструкцию PIN-блок. Конструкция зашифрована — например, через DES. Поскольку банкоматов огромное количество, то среди них много старых и до сих пор можно встретить банкомат, где внутри коробки реализован даже не Triple DES, а обычный DES.

Однажды DES стал показывать свой возраст, с ним стало тяжело, и люди решили придумать нечто поновее. Американская контора по стандартизации, которая называется NIST, сказала: давайте проведем конкурс и выберем новый классный шифр. Им стал AES.

DES расшифровывается как digital encrypted standard. AES — advanced encrypted standard. Размер блока в AES — 128 бит, а не 64. Это важно с точки зрения криптографии. Размер ключа у AES — 128, 192 или 256 бит. В AES не используется сеть Фейстеля, но он тоже многораундовый, в нем тоже несколько раз повторяются относительно примитивные операции. Для 128 бит используется 10 раундов, для 256 — 14.

Сейчас покажу, как устроен каждый раунд. Первый и последний раунды чуть отличаются от стандартной схемы — тому есть причины.

Как и в DES, в каждом раунде AES есть свои раундовые ключи. Все они генерируются из ключа шифрования для алгоритма. В этом месте AES работает так же, как DES. Берется 128-битный ключ, из него генерируется 10 подключей для 10 раундов. Каждый подключ, как и в DES, применяется на каждом конкретном раунде.

Каждый раунд состоит из четырех довольно простых операций. Первый раунд — подстановка по специальной таблице.

В AES мы строим байтовую матрицу размером 4 на 4. Каждый элемент матрицы — байт. Всего получается 16 байт или 128 бит. Они и составляют блок AES целиком.

Вторая операция — побайтовый сдвиг.

Устроен он несложно, примитивно. Мы берем матрицу 4 на 4. Первый ряд остается без изменений, второй ряд сдвигается на 1 байт влево, третий — на 2 байта, четвертый — на 3, циклично.

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

Четвертая, вновь очень простая операция — XOR каждого байта в каждой колонке с соответствующим байтом ключа. Получается результат.

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

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

Мы повторяем 4 описанных шага 10 раз, и на выходе из 128-битного блока снова получаем 128-битный блок.

Какие достоинства у AES? Он оперирует байтами, а не битами, как DES. AES намного быстрее в софтовых реализациях. Если сравнить скорость выполнения AES и DES на современной машине, AES окажется в разы быстрее, даже если говорить о реализации исключительно в программном коде.

Производители современных процессоров, Intel и AMD, уже разработали ассемблерные инструкции для реализации AES внутри чипа, потому что стандарт довольно несложный. Как итог — AES еще быстрее. Если через DES на современной машинке мы можем зашифровать, например, 1-2 гигабита, то 10-гигабитный AES-шифратор находится рядом и коммерчески доступен обычным компаниям.

Блочный алгоритм шифрует блок в блок. Он берет блок на 128 или 64 бита и превращает его в блок на 128 или 64 бита.

А что мы будем делать, если потребуется больше, чем 16 байт?

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

Да, очевидно, побьем всё на блоки по 16 байт и зашифруем. Такое шифрование называется ECB — electronic code boot, когда каждый из блоков по 16 байт в случае AES или по 8 байт в случае DES шифруется независимо.

Шифруем каждый блок, получаем шифротекст, складываем шифротексты и получаем полный результат.

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

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

Мы не только берем ключ и открытый текст, но и генерируем случайное число, которое не является секретным. Оно размером с блок. Называется оно инициализационным вектором.

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

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

Однако у CBC есть несколько проблем.

О размере блока. Представьте: мы начали шифровать и, допустим, у нас DES. Если бы DES был идеальным алгоритмом шифрования, выход DES выглядел бы как равномерно распределенные случайные числа длиной 64 бита. Какова вероятность, что в выборке из равномерно распределенных случайных чисел длиной 64 бита два числа совпадут для одной операции? 1/(264). А если мы сравниваем три числа? Давайте пока прервемся.

habr.com

Значение слова ЗАШИФРОВАТЬ. Что такое ЗАШИФРОВАТЬ?

  • ЗАШИФРОВА́ТЬ, —ру́ю, —ру́ешь; прич. страд. прош. зашифро́ванный, —ван, -а, -о; сов., перех. (несов. зашифровывать и шифровать). Засекретить с помощью шифра, условных обозначений. Зашифровать донесение. Зашифровать радиограмму.

Источник (печатная версия): Словарь русского языка: В 4-х т. / РАН, Ин-т лингвистич. исследований; Под ред. А. П. Евгеньевой. — 4-е изд., стер. — М.: Рус. яз.; Полиграфресурсы, 1999; (электронная версия): Фундаментальная электронная библиотека

Делаем Карту слов лучше вместе

Привет! Меня зовут Лампобот, я компьютерная программа, которая помогает делать Карту слов. Я отлично умею считать, но пока плохо понимаю, как устроен ваш мир. Помоги мне разобраться!

Спасибо! Когда-нибудь я тоже научусь различать смыслы слов.

В каком смысле употребляется прилагательное настоящий в отрывке:

Для настоящих чувств нам нужно время.

В прямом
смысле

В переносном
смысле

Это устойчивое
выражение

Это другое
прилагательное

kartaslov.ru

Разное

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Семейный блог Ирины Поляковой Semyablog.ru® 2019. При использовании материалов сайта укажите, пожалуйста, прямую ссылку на источник.Карта сайта