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

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

Поточное шифрование

Зашифруем поточным шифром замены слово CIPHER:

Зашифровали каждый символ и получили шифротекст. Проще простого.

БЛОЧНОЕ ШИФРОВАНИЕ

Зашифруем слово AVADAKEDAVRA. Поскольку шифр блочный, открытый текст разобьем на блоки по четыре символа: AVAD | AKED | AVRA (на практике блоки текста состоят из 64-256 бит). Для каждого блока придумаем свою таблицу замены:

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

СЕТЬ ФЕЙСТЕЛЯ

Теперь мы готовы перейти к очень важной теме, которая открывает дверь в бескрайний мир современных систем шифрования. Сеть Фейстеля - это метод блочного шифрования, разработанный Хорстом Фейстелем в лаборатории IBM в 1971 году. Сегодня сеть Фейстеля лежит в основе большого количества криптографических протоколов. Попробуем разобрать «на пальцах», что же она собой представляет.

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

• Блок разбивается на две равные части - левую (L) и правую (R).
• После разбиения левый подблок изменяется функцией f с использованием ключа K: x = f(L, K). В качестве функции можно представить себе какое угодно преобразование — например, старый добрый шифр сдвига с ключом К.
• Полученный подблок складывается по модулю 2 с правым подблоком R, который до этого был не у дел: х=х+R
• Далее полученные части меняются местами и склеиваются.

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

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

Теперь посмотрим работу сети Фейстеля на примере. Возьмем слово AVADAKEDAVRA и разобьем его на два блока по шесть символов - AVADAK | EDAVRA. За функцию возьмем шифр сдвига на число позиций, определенных раундовым ключом. Пусть секретный ключ K = . В качестве раундовых ключей возьмем K = 1, K = 2. Для сложения по модулю 2 переведем текст в двоичный код согласно телеграфному алфавитику , которым вряд ли кто-то еще пользуется вообще.

Вот что получилось:

Теперь прогоним через сеть Фейстеля из двух раундов первый блок:

Второй блок попробуй зашифровать сам, у меня получилось MOSSTR.

Расшифрование осуществляется точно так же: шифротекст разбивается на блоки и затем подблоки, левый подблок поступает в функцию, складывается по модулю 2 с правым, и затем подблоки меняются местами. Отличие заключается в том, что раундовые ключи подаются в обратном порядке, то есть в нашем случае в первом раунде применим ключ K = 2, а затем во втором раунде K = 1.

Исследования сети Фейстеля показали, что при независимых раундовых ключах и криптостойкой псевдослучайной функции f трех раундов сети Фейстеля будет достаточно, чтобы шифротекст был псевдослучайным. Это говорит о том, что шифры, основанные на сети Фейстеля, на данный момент достаточно криптостойки.

ГОСТ 28147-89 (МАГМА)

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

Основные характеристики: ключ 256 бит, блок 64 бита.

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

ГОСТ 28147 весьма скупо характеризует свои таблицы замены. Говорится лишь о том, что они являются дополнительным секретным элементом (наряду с секретным ключом) и «поставляются в установленном порядке». Больше ничего. С момента принятия ГОСТ 28147 научно-техническая неопределенность, связанная с выбором S-боксов, порождала слухи и домыслы. Ходили разговоры о секретных критериях, известных только разработчикам ГОСТа. Естественно, что эта неопределенность снижала доверие к криптосистеме.

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

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

Режим простой замены

В режиме простой замены на 32 раунда, согласно стандарту, нам нужно 32 раундовых ключа. Для генерации раундовых ключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: K1…K8. Ключи K9…K24 являются циклическим повторением ключей K1…K8. Ключи K25…K32 являются ключами K8…K1.

1. Каждый блок 64 бита делится на два подблока - Ai и Bi.
2. Левый подблок Ai складывается по модулю 232 с раундовым ключом K1: Ai+1 = Ai + Ki mod 232.
3. Левый подблок проходит через S-бокс.
4. Биты левого подблока сдвигаются на 11 позиций (циклический сдвиг).
5. Левый подблок складывается с правым по модулю 2: A = A ⊕ B . iii
6. Правый подблок принимает первоначальное значение левого подблока: Bi+1 = Ai.
7. Подблоки меняются местами.

Сразу пример одного раунда. Ключ 256 бит:

arvadek adava arvadek adava arvadek adava arvadek adava arva 00011 01010 11110 00011 01001 00001 01111 00011 01001 00011 11110 00011... . . . 00011 01010 11110 0

Тогда раундовые ключи

K1 = 00011 01010 11110 00011 01001 00001 01 K2 = 111 00011 01001 00011 11110 00011 0001 K3 = . . . S - бокс= [ 1 , 15 , 13 , 0 , 5 , 7 , 10 , 4 , 9 , 2 , 3 , 14 , 6 , 11 , 8 , 12 ]

Как пользоваться таким S-боксом? Очень просто! Если на входе S-бокса 0, то на выходе будет 1 (берем 0-й символ S-бокса), если 4, то на выходе будет 5 (берем 4-й символ), если на входе 7, то на выходе 4, и так далее.

Открытый текст:

Делится на два 32-битных блока старших и младших битов:

Пример, конечно, вышел дикий, потому что ГОСТ - это все-таки не такой стандарт, чтоб каждый мог его ручками перебирать.

Режим простой замены чересчур простой и имеет существенные недостатки:

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

Таким образом, применять ГОСТ 28147-89 в режиме простой замены желательно лишь для шифрования ключевых данных.

РЕЖИМ ГАММИРОВАНИЯ

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

А теперь все по порядку.

Шаги 3–5 повторяются для каждого блока. Все эти манипуляции можно посмотреть на схеме.

Расшифрование выполняется аналогично, вместо блока открытого текста подается блок шифротекста.

Режим гаммирования с обратной связью

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

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

Режим имитовставки

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

1. Блок открытого текста проходит 16 раундов в режиме простой замены.
2. К полученному блоку по модулю 2 прибавляется еще один блок открытого текста.
3. Сумма проходит еще 16 раундов в режиме простой замены.
4. Прибавляется следующий блок открытого текста и опять простая замена и так далее, пока не кончатся блоки открытого текста.

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

ГОСТ 34.12-2015 (КУЗНЕЧИК)

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

Основные характеристики: ключ 256 бит, блок 128 бит.

Также стоит сказать, что в новом стандарте S-боксы фиксированы и продуманны, так что не стоит изобретать свои чудо-случайные подстановки. В новом ГОСТе режимов шифрования стало гораздо больше:
режим простой замены (Electronic Codebook, ЕСВ);
режим гаммирования (Counter, CTR);
режим гаммирования с обратной связью по выходу (Output Feedback, OFB);
режим простой замены с зацеплением (Cipher Block Chaining, СВС);
режим гаммирования с обратной связью по шифротексту (Cipher Feedback,CFB);
режим выработки имитовставки (Message Authentication Code algorithm).

Рассмотрим новые режимы.

Режим простой замены с зацеплением

Как было видно на прошлом стандарте, режим простой замены - самый слабый из режимов, поэтому в новом стандарте он теперь выступает с зацеплением и стал вовсе не таким простым.

1. Инициализирующий вектор - звучит страшно, но на деле всего лишь последовательность битов, поступающая на вход.
2. Вектор разбивается на две части - L и R, одна из которых складывается по модулю 2 с открытым текстом, а другая становится половинкой инициализирующего вектора для следующего блока.
3. Сумма открытого текста и кусочка инициализирующего вектора проходит через шифр простой замены.
4. Полученные блоки зашифрованного текста склеиваются.

Стоит посмотреть на схему, и сразу все становится ясно.

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

Для плюсов - Encryptions . Среди отечественных разработок это криптопровайдер КриптоПро CSP .

Пара слов о стойкости режимов шифрования. Немало зарубежных криптографов пытались поднять руку на наш стандарт, однако на данный момент не известно ни одной атаки, которая может быть реализована на современном технологическом уровне развития. Среди программистов этот стандарт долгое время был не слишком популярен, так как из его текста понять алгоритм работы тяжело, а более четких описаний маловато. Но сейчас уже полно реализаций на многих языках программирования. Так что теперь использование ГОСТа вполне реально, и по многим параметрам он превосходит зарубежные стандарты. В конце концов, где же патриотизмъ?!

Аннотация: В этой лекции поставлено несколько целей. Показать различие между традиционными и современными шифрами с симметричным ключом. Привести современные блочные шифры и обсудить их характеристики. Объяснить, почему современные блочные шифры должны быть спроектированы как шифры подстановки. Ввести компоненты блочных шифров, таких как P-блоки и S-блоки. Обсудить и показать различие между двумя классами шифров: шифры Файстеля и шифры не-Файстеля. Обсудить два вида атак, особо направленных на раскрытие современных блочных шифров: дифференциальный и линейный криптоанализ. Ввести понятие "шифры для потока" и показать различие между синхронными и несинхронными шифрами. Обсудить линейную и нелинейную обратную связь регистров сдвига для реализации поточных шифров.

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

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

7.1. Современные блочные шифры

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

Рис. 7.1.

Если сообщение имеет размер меньше, чем n бит , нужно добавить заполнение, чтобы создать этот n -разрядный блок; если сообщение имеет больше, чем n бит , оно должно быть разделено на n -разрядные блоки, и в случае необходимости нужно добавить к последнему блоку соответствующее заполнение. Общие значения для n обычно 64 , 128 , 256 или 512 битов.

Пример 7.1

Сколько дополнительных битов нужно добавить к сообщению 100 символов, если для кодирования используется ASCII по 8 битов и блочный шифр принимает блоки 64 бита?

Решение

Закодировать 100 символов, используя ASCII по 8 битов. Это сообщение содержит 800 бит . Исходный текст должен делиться без остатка на 64 . Если | M | и | Pad | - длина сообщения и длина заполнения, то

| M | + | Pad | == 0 mod 64 -> | Pad | = -800 mod 64-> 32 mod 64

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

Подстановка, или транспозиция

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

Если шифр спроектирован как шифр подстановки , значения бита 1 или 0 в исходном тексте могут быть заменены либо на 0 , либо на 1 . Это означает, что исходный текст и зашифрованный текст могут иметь различное число единиц. Блок исходного текста на 64 бита, который содержит 12 нулей и 52 единицы, может быть представлен в зашифрованном тексте 34 нулями и 30 единицами. Если шифр спроектирован как шифр перестановки (транспозиции) , биты только меняют порядок следования (перемещаются), сохраняя то же самое число символов в исходном и зашифрованном текстах. В любом случае, число возможных n -битовых исходных текстов или зашифрованных текстов равно 2 n , потому что каждый из n битов, использованных в блоке, может иметь одно из двух значений - 0 или 1 .2 64 блока по 64 бита, чтобы найти один, который имеет смысл. Если бы Ева могла пробовать 1 миллиард блоков в секунду, и тогда ей потребовалось бы сотни лет, прежде чем эта работа могла бы принести успех.

b. Во втором случае (перестановка) Ева знает, что в исходном тексте есть точно 10 единиц, потому что транспозиция не изменяет числа единиц (или нулей) в зашифрованном тексте. Ева может начать атаку исчерпывающего поиска, используя только те 64 -битовые блоки, которые имеют точно 10 единиц. Есть только (64!) / [(10!) (54!)] = 151 473 214 816 из 2 64 слов по 64 бита, которые имеют точно 10 единиц. Ева может проверить всех их меньше чем за 3 минуты, если она может провести 1 миллиард испытаний в секунду.

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

09.07.2003

Что такое шифрование?

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

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

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

Основные современные методы шифрования

Среди разнообразнейших способов шифровании можно выделить следующие основные методы:

• Алгоритмы замены или подстановки - символы исходного текста заменяются на символы другого (или того же) алфавита в соответствии с заранее определенной схемой, которая и будет ключом данного шифра. Отдельно этот метод в современных криптосистемах практически не используется из-за чрезвычайно низкой криптостойкости.
• Алгоритмы перестановки - символы оригинального текста меняются местами по определенному принципу, являющемуся секретным ключом. Алгоритм перестановки сам по себе обладает низкой криптостойкостью, но входит в качестве элемента в очень многие современные криптосистемы.
• Алгоритмы гаммирования - символы исходного текста складываются с символами некой случайной последовательности. Самым распространенным примером считается шифрование файлов "имя пользователя.pwl", в которых операционная система Microsoft Windows 95 хранит пароли к сетевым ресурсам данного пользователя (пароли на вход в NT-серверы, пароли для DialUp-доступа в Интернет и т.д.).

Когда пользователь вводит свой пароль при входе в Windows 95, из него по алгоритму шифрования RC4 генерируется гамма (всегда одна и та же), применяемая для шифрования сетевых паролей. Простота подбора пароля обусловливается в данном случае тем, что Windows всегда предпочитает одну и ту же гамму.

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

Симметричные и асимметричные криптосистемы

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

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

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

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

Алгоритм RSA

Алгоритм RSA (по первым буквам фамилий его создателей Rivest-Shamir-Adleman) основан на свойствах простых чисел (причем очень больших). Простыми называются такие числа, которые не имеют делителей, кроме самих себя и единицы. А взаимно простыми называются числа, не имеющие общих делителей, кроме 1.

Для начала выберем два очень больших простых числа (большие исходные числа нужны для построения больших криптостойких ключей. Например, Unix-программа ssh-keygen по умолчанию генерирует ключи длиной 1024 бита).

Определим параметр n как результат перемножения p и q . Выберем большое случайное число и назовем его d , причем оно должно быть взаимно простым с результатом умножения (p -1)*(q -1) .

Отыщем такое число e, для которого верно соотношение

(e*d) mod ((p -1)*(q -1)) = 1

(mod - остаток от деления, т. е. если e, умноженное на d, поделить на ((p -1)*(q -1)) , то в остатке получим 1).

Открытым ключом является пара чисел e и n , а закрытым - d и n .

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

C(i)= (M(i) e) mod n.

В результате получается последовательность C(i) , которая и составит криптотекст. Декодирование информации происходит по формуле

M(i) = (C(i) d) mod n.

Как видите, расшифровка предполагает знание секретного ключа.

Давайте попробуем на маленьких числах.

Установим p=3, q=7 . Тогда n=p*q=21. Выбираем d как 5. Из формулы (e*5) mod 12=1 вычисляем e=17 . Открытый ключ 17, 21 , секретный - 5, 21 .

Зашифруем последовательность «12345»:

C(1)= 1 17 mod 21= 1

C(2)= 2 17 mod 21 =11

C(3)= 3 17 mod 21= 12

C(4)= 4 17 mod 21= 16

C(5)= 5 17 mod 21= 17

Криптотекст - 1 11 12 16 17.

Проверим расшифровкой:

M(1)= 1 5 mod 21= 1

M(2)= 11 5 mod 21= 2

M(3)= 12 5 mod 21= 3

M(4)= 16 5 mod 21= 4

M(5)= 17 5 mod 21= 5

Как видим, результат совпал.

Криптосистема RSA широко применяется в Интернете. Когда вы подсоединяетесь к защищенному серверу по протоколу SSL, устанавливаете на свой ПК сертификат WebMoney либо подключаетесь к удаленному серверу с помощью Open SSH или SecureShell, то все эти программы применяют шифрование открытым ключом с использованием идей алгоритма RSA. Действительно ли эта система так надежна?

Конкурсы по взлому RSA

С момента своего создания RSA постоянно подвергалась атакам типа Brute-force attack (атака методом грубой силы, т. е. перебором). В 1978 г. авторы алгоритма опубликовали статью, где привели строку, зашифрованную только что изобретенным ими методом. Первому, кто расшифрует сообщение, было назначено вознаграждение в размере 100 долл., но для этого требовалось разложить на два сомножителя 129-значное число. Это был первый конкурс на взлом RSA. Задачу решили только через 17 лет после публикации статьи.

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

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

Один из самых распространенных в России почтовых клиентов, программа The Bat!, обладает встроенными возможностями добавлять цифровые подписи к письмам (обратите внимание на пункт меню Privacy при редактировании письма). Подробнее об этой методике читайте в статье (см. «Мир ПК», № 3/02).

Рис. 3

Криптография

Криптография - наука о принципах, средствах и методах преобразования информации для защиты ее от несанкционированного доступа и искажения. В последнее время она развивается очень и очень бурно. Это бесконечная увлекательная гонка, требующая много времени и сил: криптоаналитики взламывают алгоритмы, которые еще недавно были стандартами и повсеместно использовались. Кстати, недавно математики Дэн Голдстон (США) и Кем Илдирим (Турция) доказали первую закономерность в распределении простых чисел (до сих пор таких закономерностей не замечали). Простые числа располагаются на числовой оси некоторыми скоплениями, что несколько облегчает их поиск.

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

Олег Бунин - специалист по разработке ПО для крупных Интернет-проектов, сотрудник компании «Рамблер», http://www..htm ).

Введение в криптографию / Под ред. В.В. Ященко. М.: МЦНМО, 2000.

Носов В. А. Краткий исторический очерк развития криптографии // Материалы конференции "Московский университет и развитие криптографии в России", МГУ, 17-18 октября 2002 г.

Саломаа А. Криптография с открытым ключом. М., 1996 .

Циммерман Ф. PGP - кодирование с открытым ключом для всех.

Система шифрования Цезаря

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

РЛЗЬ ЁМЭЙЗ АВБЖУ ИЙЗАВЛУ, БЖЩЛУ ЖЩЭЗЬЖЗ ЖЮЁЩЕЗ, ЭЫЩ ЫЩАЖФО ИЙЩЫВЕЩ БЩИЗЁЖВ ЭЕШ ЖЩРЩЕЩ: ЛФ ЕМРСЮ ЪЗЕЗЭЩГ, РЮЁ РЛЗ ИЗИЩЕЗ ЮКЛУ, В ЕМРСЮ ЬМЭУ ЗЭВЖ, РЮЁ ЫЁЮКЛЮ К ДЮЁ ИЗИЩЕЗ.

Успели? Привожу «отгадку»:

Чтоб мудро жизнь прожить, знать надобно немало,

Два важных правила запомни для начала:

Ты лучше голодай, чем что попало есть,

И лучше будь один, чем вместе с кем попало.

Ключ для расшифровки: сдвигаем на семь символов (берем седьмой) влево по алфавиту. Алфавит закольцован. Регистр символов не учитывается.

Windows и пароли

Как Windows шифрует пароли?

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

Конкурс AES (Advanced Encryption Standard)

В 80-х гг. в США приняли стандарт симметричного шифрования для внутреннего применения - DES ((Data Encryption Standard, подобный стандарт есть и в России). Но в 1997 г., когда стало понятно, что 56-битового ключа DES недостаточно для надежной криптосистемы, Американский институт стандартизации объявил конкурс на новый стандартный алгоритм. Из 15 вариантов был выбран лучший: бельгийский алгоритм Rijndael (его название составлено из фамилий авторов - Rijmen и Daemen, читается как «Рэйндал». Этот алгоритм уже встроен в различные криптографические средства, поставляемые на рынок). Другими финалистами конкурса стали MARS, RC6, Serpent, TwoFish. Все эти алгоритмы были признаны достаточно стойкими и успешно противостоящими всем широко известным методам криптоанализа.

Криптографические хэш-функции

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

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

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

Криптография – не просто какая-то компьютерная штука

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

ROT13 – еще один распространенный тип шифрования сообщений. В нём каждая буква алфавита сдвигается на 13 позиций, как показано на рисунке:

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

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

Определения и краткое руководство по кибербезопасности

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

Конфиденциальность – данные не могут быть получены или прочитаны неавторизованными пользователями.

Целостность информации – уверенность в том, что информация 100% останется нетронутой и не будет изменена злоумышленником.

Доступность информации – получение доступа к данным, когда это необходимо.

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

Основные способы шифрования:

• Симметрично
• Асимметричное
• Хеширование
• Цифровая подпись

Симметричное шифрование

Прежде чем мы начнем разбираться в теме, ответим на простой вопрос: что именно подразумевается под «шифрованием»? Шифрование – преобразование информации в целях сокрытия от неавторизованных лиц, но в то же время с предоставлением авторизованным пользователям доступа к ней.

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

Ruby

require "openssl" require "pry" data_to_encrypt = "now you can read me!" cipher = OpenSSL::Cipher.new("aes256") cipher.encrypt key = cipher.random_key iv = cipher.random_iv data_to_encrypt = cipher.update(data_to_encrypt) + cipher.final binding.pry true

require "openssl" require "pry" cipher = OpenSSL :: Cipher . new ("aes256" ) cipher . encrypt key = cipher . random _ key iv = cipher . random _ iv data_to_encrypt = cipher . update (data_to_encrypt ) + cipher . final binding . pry true

Вот что выведет программа:

Обратите внимание, что переменная data_to_encrypt , которая изначально была строкой “now you can read me!”, теперь куча непонятных символов. Обратим процесс, используя ключ, который изначально сохранили в переменной key .

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

Давайте рассмотрим и другие способы шифрования.

Асимметричное шифрование

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

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

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

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

Создадим пару открытого и закрытого ключей:

Ruby

require "openssl" require "pry" data_to_encrypt = "now you can read me!" key = OpenSSL::PKey::RSA.new(2048) binding.pry true

require "openssl" require "pry" data_to_encrypt = "now you can read me!" key = OpenSSL :: PKey :: RSA . new (2048 ) binding . pry true

Получится:

Обратите внимание, что приватный ключ и открытый ключ являются отдельными объектами с различными идентификаторами. Используя #private_encrypt , можно зашифровать строку с помощью закрытого ключа, а используя #public_decrypt – расшифровать сообщение:

Хеширование информации

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

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

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

Roadmap

Это четвертый урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:

• Основы и исторические шифраторы. Как работают (и анализируются) шифры сдвига, замены, Рихарда Зорге, шифр Вернама и шифровальные машины
• Что это такое, как выполняется распределение ключей и как выбрать криптостойкий ключ
• Что такое сеть Фейстеля и какими бывают отечественные блочные шифры, используемые в современных протоколах, - ГОСТ 28147-89, «Кузнечик»
• Урок 4. Современные зарубежные шифры. В чем разница между 3DES, AES, Blowfish, IDEA, Threefish от Брюса Шнайера и как они работают (ты здесь)
• Виды электронных подписей, как они работают и как их использовать
• Урок 6. Квантовая криптография. Что это такое, где используется и как помогает в распределении секретных ключей, генерации случайных чисел и электронной подписи

3DES

Итак, первым в ряду зарубежных шифров рассмотрим 3DES, а точнее его ближайшего родственника DES (Data Encryption Standard), который хоть уже и не используется как таковой, но является предком 3DES.

DES разработан командой математиков научной лаборатории IBM, в которую входил уже знакомый нам Фейстель. Первая версия шифра получила имя «Люцифер», но затем он был модифицирован и в результате принят как официальный алгоритм шифрования данных (DEA). На протяжении более двадцати лет он оставался мировым стандартом, прежде чем его сменил Triple DES.

Рассмотрим, как работает алгоритм шифрования DES. Для этого необходимо вспомнить работу сети Фейстеля. DES - это сеть Фейстеля из 16 раундов с симметричными ключами шифрования. Длина блока текста - 64 бита, длина раундового ключа - 48 бит. Итак, пройдем основные этапы шифрования DES, опуская суровую математическую сторону:

1. Текст, как и при любом другом шифровании, разбивается на блоки по 64 бита.
2. Из 56-битного ключа генерируется 16 48-битных раундовых ключиков.
3. Каждый блок подвергается перестановке, то есть все биты входного блока перемешиваются согласно определенной таблице.
4. Блок расщепляется на половинки и поступает в знакомую нам сеть Фейстеля, где прокручивается 16 раундов.
5. Соединяем половинки.
6. И еще одна перестановка.

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

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

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

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

Чтобы решить проблему быстрого поиска ключа, умные зарубежные криптографы предложили использовать два ключа и применять DES дважды. Однако двойной DES оказался уязвим к атаке «встреча посередине». Чтобы реализовать эту атаку, злоумышленнику необходимо иметь открытый и соответствующий ему зашифрованный текст. Злоумышленник шифрует открытый текст на всех возможных ключах, записывая результаты в таблицу 1. Затем расшифровывает зашифрованный текст со всеми возможными ключами и записывает результат в таблицу 2. Далее злоумышленник ищет в таблицах 1 и 2 совпадения.

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

Совсем иначе дела обстоят с Triple DES. Использование трех ключей и применение алгоритмов в указанной на схеме последовательности продлило DES жизнь еще на несколько лет.

Замечательный DES

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

Было доказано, что DES имеет все признаки этого свойства.

Хотя два блока исходного текста не совпадают только самым правым битом, блоки зашифрованного текста отличаются на 29 бит. Это означает, что изменение приблизительно в 1,5% исходного текста вызывает изменение приблизительно 45% зашифрованного текста.

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

Где же применяется DES? Да почти везде, его реализации присутствуют в большинстве программных библиотек. Однако кто знает, насколько использование DES безопасно в наше время? Хотя IBM утверждала, что работа алгоритма была результатом 17 человеко-лет интенсивного криптоанализа, некоторые люди опасались, не вставило ли NSA в алгоритм лазейку, которая позволяет агентству легко дешифровывать перехваченные сообщения. Комитет по разведке сената США тщательно изучал этот вопрос и, разумеется, ничего не обнаружил, обвинения с NSA были сняты, результаты исследования тем не менее засекречены. Одним словом, в Америке еще долго крутились слухи и домыслы насчет того, стоит доверять DES или нет. Но, как я считаю, здесь ситуация описывается поговоркой «Умный не скажет, дурак не поймет». В конце концов NSA признало, что не могло доверить IBM столь важную миссию и внесло несколько корректировок вроде задания S-боксов.

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