|
Криптография (блочный шифр)
Что такое Blowfish.
Blowfish это 64-бит блочный шифр разработанный Шнайером (Schneier) в 1993 году. Это
шифр Файстела (Feistel) и каждый проход состоит иззависимой от ключа перестановки и
зависимой от ключа с данными замены. Все операции основаны на операциях XOR и
прибавлениях к 32-битным словам (XORs andadditions on 32-bit words). Ключ имеет
переменную длину (максимально 448 бит) и используется для генерации нескольких
подключевых массивов (subkey arrays).Шифр был создан специально для 32-битных машин
и существенно быстрее DES.
В 1994 Dr.Dobb журнал спонсировал открытое соревнование с выиграшем в $1000. Это
соревнование закончилось в Апреле 1995 и среди результатов было
открытосуществование нескольких слабых ключей. Однако, Blowfish может считаться
защищенным, и Шнайер пригласил криптоаналитиков для продолжения исследованияего
шифра.
Что такое DES.
DES (Data Encryption Standart) это симметричный алгоритм шифрования, т.е. один ключ
используется как для зашифровывания, так и для расшифрованиясообщений. Разработан
фирмой IBM и утвержден правительством США в 1977 как официальный стандарт.
DES имеет блоки по 64 бит и основан на 16 кратной перестановке данных, также для
зашифрования использует ключ в 56 бит. Существует несколько режимов DES,например
Electronic Code Book (ECB) и Cipher Block Chaining (CBC).
56 бит - это 8 семибитовых ASCII символов, т.е. пароль не может быть больше чем 8 букв.
Если вдобавок использовать только буквы и цифры, то количествовозможных вариантов
будет существенно меньше максимально возможных 2^56.
Один из шагов алгоритма DES:
Входной блок данных делится пополам на левую (L') и правую (R') части. После этого
формируется выходной массив так, что его левая часть L'' представленаправой частью R'
входного, из 32-битового слова R' с помощью битовых перестановок формируется 48-
битовое слово. Полученное 48-битовое слово XOR-итсяс 48-битовым раундовым ключом.
Результирующее 48-битовое слово разбивается на 8 6-битовых групп, каждая 6-битовая
группа посредством соответствующего S-box'азаменяется на 4-битовую группу и из
полученных восьми 4-битовых групп составляется 32-битовое слово. Полученное слово
XOR-ится с L', в результатеполучается R''. Можно убедиться, что все проведенные
операции могут быть обращены и расшифрование осуществлятся за число операций,
линейно зависящее отразмера блока. После нескольких таких взбиваний можно считать,
что каждый бит выходного блока шифровки может зависеть от каждого бита сообщения.
Что такое Тройной DES.
Так как текст, зашифроaвaнный двойным DES оказывается хрупким при
криптографической атаке - встреча на середие (meet in the middle), то текстшифруется 3 раза
DES. Таким образом длина ключа возрастает до 168-бит (56x3).
Не всегда, применеие тройного DES означает увелечение уровня безопасности сообщения.
Типы тройного шифрования DES:
? DES-EEE3: Шифруется 3 раза с 3 различными ключами.
? DES-EDE3: 3 DES операции шифровка-расшифровка-шифровка с 3 различными
ключами.
? DES-EEE2 и DES-EDE2: Как и предыдущие, за исключением того, что первая и
третья операции используют одинаковый ключ.
Сравнение различных видов DES
шифрования.
#
Ш
иф
ров
ан
ия
#
Кл
юч
ей
Вычисление
(Computation
)
Хранение
(Storage)
Ти
п
ата
ки
оди
ноч
ны
й
1
2^56
-
kno
wn
plai
ntex
t
оди
ноч
ны
й
1
2^38
2^38
cho
sen
plai
ntex
t
оди
ноч
ны
й
1
-
2^56
cho
sen
plai
ntex
t
дво
йн
ой
2
2^112
-
kno
wn
plai
ntex
t
дво
йн
ой
2
2^56
2^56
kno
wn
plai
ntex
t
дво
йн
ой
2
-
2^112
cho
sen
plai
ntex
t
тро
йн
ой
2
2^112
-
kno
wn
plai
ntex
t
тро
йн
ой
2
2^56
2^56
2^5
6
cho
sen
plai
ntex
t
тро
йн
ой
2
2^(120-t)
-
2^t
kno
wn
plai
ntex
t
тро
йн
ой
2
-
2^56
cho
sen
plai
ntex
t
тро
йн
ой
3
2^112
2^56
kno
wn
plai
ntex
t
тро
йн
ой
3
2^56
2^112
cho
sen
plai
ntex
t
Что такое DES с независимыми ключами (independent
subkeys).
DES выделяет из 56-битного ключа введенного пользователем 16 48-битных ключей, для
использования в каждой из 16 перестановок. Интересно сравнениеэффекта при
использовании 768-битного ключа (разделенного на 16 48-битных подключиков) взамен
использования 16 зависимых ключей создающимся режимомключей в DES алгоритме.
При использовании независимых ключей будет существенно увеличиваться количество
попыток, нужных для исчерпывающего поиска ключей. Изменение шифраповлечет за
собой лишь не значительное увеличение стойкости шифра против дифференциальной и
линейной криптоаналитических атаках чем у обычного DES. Этобыло открыто Битамом
(Bitham).
Что такое IDEA.
IDEA (International Data Encryption Algorithm) - это вторая версия блочного шифра
разработанный К.Лейем (Lai )и Д.Месси (Massey) в конце 80-х. Это шифрсостоящий из 64-
битных повторяющихся блоков со 128-битным ключом и восемью проходами (rounds).
Хотя этот шифр не шифр Файстела (Feistel), дешифрованиевыполняется по тому же
принципу,чтоишифрование. Структура шифра была разработана для легкого воплощения
как программно, так и аппаратно,и безопасность IDEA основывается на использовании
трех не совместимх типов арифметических операций над 16-битными словами. Скорость
программного IDEAсравнима со скоростью DES.
Один из принципов создания IDEA - затруднить дифференциальный криптоанализ. Также
не одна линейная криптоаналитическая атака не закончилась успешно, как ине было
выявлено алгебраически слабых мест. Самый полный анализ провел Daemen. Он открыл
большой класс 2^51 слабых ключей, при использовании которых впроцессе шифрования,
ключ может быть обнаружен и востановлен. Однако, т.к. в IDEA существует 2^128
возможных вариантов ключей, то это открытие не влияет напрактическую безопасность
шифра.
Что такое RC2 и RC4.
RC2 и RC4 это блочные шифры с ключом переменной длины созданные Роном Ривестом
(Ron Rivest) для RSA Data Security. "RC" расшифровываетсякак "Ron's Code" или "Rivest Cipher
(шрифт)". RC2 быстрее чем DES и был спецальноразработан для замены ("drop-in"
replacement) DES. Он может быть реализован более или менее защищенным чем DES, в
зависимости от длины ключа.RC2 алгоритм конфиденциален и является собственностью
RSA Data Security. RC2 может использоваться там, где используется DES.
Соглашение, заключенное между Software Publishers Association (SPA) и правительством
США дает RC2 и RC4 специальный статус, который означает, чторазрешено
экспортировать шифры длинной ключа до 40 бит. 56-битные ключи разрешено
использовать заграничным отделениям американских компаний. Однако,несколько
мощных компьютеров, могут перебрать все возможные у 40-битного ключа 2^40 варианты
всего за неделю. Поэтому дополнительно могут использоваться строкиназываемые солью
(salt), которые сильно мешают при переборе всех возможных вариантов. Соль
присоединяется к исходному ключу, и удлиненный ключиспользуется для шифрования.
сообщения, потом соль посылается с сообщением в не зашифрованном виде.
RC2 и RC4 с ключами 128 бит обеспечивают такой же уровень безопасности как и IDEA
или тройной DES. RC2 и RC4 используется широко разработчиками, чьи продукты
экспортируются за пределы США,поскольку экспортировать DES запрещено.
Надежность RC4 была недавно поставлена под сомнение из за несанкционированного
соглашения текста программы, использующей этот шифр.
Что такое RC5.
RC5 это довольно-таки быстрый блочный шифр разработанный Ривестом для RSA Data
Security. Этот алгаритм параметричен, т.е. с пременным размером блока,длинной ключа и
переменным числом проходов. Размер блока может быть 32, 64, или 128 битов.
Количество проходов в промежутке от 0 до 2048 бит. Параметричностьтакого рода дает
гибкость и эффективность шифрования.
RC5 состоит из ввода ключа (key expansion), шифрования и дешифрования. При вводе
ключа вводятся также количество проходов, размер блока и т.д. Шифрованиесостоит из 3
примитвных операций : сложения, побитового XOR и чередования (rotation).
Исключительная простота RC5 делает его простым в использовании, RC5текст, также как
и RSA, может быть дописан в конец письма в зашифрованном виде.
Безопасность RC5 основывается на зависящем от данных чередованием и смешиванием
результатов различных операций. RC5 с размером блока 64 бита и 12или более проходов
обеспечивает хорошую стойкость против дифференциального и линейного криптанализов.
Что такое RSA.
RSA (авторы: Rivest, Shamir и Alderman) это система с открытым ключом (public-key)
предназначенная как дляшифрования, так и для аутентификации была разработана в 1977
году. Она основана на трудности разложения очень больших целых чисел на простые
сомножители.
RSA очень медленный алгоритм. Для сравнения, на програмном уровне DES по меньше
мере в 100 разбыстрее RSA, на апаратном аж в 1,000-10,000 раз, взависимости от
выполнения.
RSA алгоритм:
1. Берутся два очень больших целых числа P и Q и находятся N=PQ и M=(P-1)(Q-1)
2. Выбирается случайное целое число D, взаимно простое с M и вычисляется E=(1
MOD M)/D
3. Потом публикуется D и N как открытый ключ, E сохраняется в тайне.
4. Если S - сообщение, длина которого, определяемая по значению выражаемого
имцелого числа, должна быть в интервале (1,N), то оно превращается в шифровку
возведением в степень D по модулю N и отправляется получателю S'=S^D MOD N
5. Получатель сообщения расшифрорвывает его, возведя в степень E (число E ему
уже известно) по модулю N, т.к. S=(S'^E MOD N)=S^(DE) MOD N
Что такое ГОСТ 28147-89.
ГОСТ 28147-89 - это стандарт, принятый в 1989 году в Советском Союзе и установивший
алгоритм шифрования данных, составляющих гостайну. Историясоздания этого алгоритма
- тайна, покрытая мраком. По свидетельству причастных к его реализациям и
использованию людей, алгоритм был разработан в 70-е годы в8-м Главном Управлении
КГБ СССР, тогда он имел гриф Сов.Секретно. Затем гриф был понижен до Секретно, а
когда в 89-м году алгоритм был проведен черезГосстандарт и стал официальным
государственным стандартом, гриф с него был снят, однако алгоритм оставался ДСП. В
начале 90-х годов он стал полностьюоткрытым.
ГОСТ предусматривает 3 режима шифрования (простая замена, гаммирование,
гаммирование с обратной связью) и один режим выработки имитовставки. Первый
изрежимов шифрования предназначен для шифрования ключевой информации и не может
использоваться для шифрования других данных, для этого предусмотрены два
другихрежима шифрования. Режим выработки ИМИТОВСТАВКИ (криптографической
контрольной комбинации) предназначен для ИМИТОЗАЩИТЫ шифруемых данных, то
есть для ихзащиты от случайных или преднамеренных несанкционированных изменений.
Алгоритм построен по тому же принципу, что и DES - это классический блочный шифр с
секретным ключом - однако отличается от DES'а большей длиной ключа,большим
количеством раундов, и более простой схемой построения самих раундов. Ниже
приведены его основные параметры, для удобства - в сравнении с параметрамиDES'а:
П
А
РА
М
Е Т
Р
ГО
СТ
DE
S
1.
Раз
мер
бло
ка
ши
фро
ван
ия
64
бит
а
64
бит
а
2.
Дл
ина
кл
юч
а
256
бит
56
бит
3.
Чи
сло
рау
ндо
в
32
16
4.
Узл
ы
зам
ен
(S-
бло
ки)
не
фик
сир
ова
ны
фик
сир
ова
ны
5.
Дл
ина
кл
юч
а
для
одн
ого
рау
нда
32
бит
а
48
бит
6.
Схе
ма
вы
раб
отк
и
рау
ндо
вог
о
кл
юч
а
про
ста
я
сло
жн
ая
7.
На
чал
ьна
я и
кон
ечн
ая
пер
ест
ано
вки
бит
ов
нет
ест
ь
В силу намного большей длины ключа ГОСТ гораздо устойчивей DES'а к вскрытию
"грубой силой" - путем полного перебора по множеству возможныхзначений ключа.
Функция шифрования (*) ГОСТа гораздо проще функции шифрования DES'а, она не
содержит операций битовых перестановок, коими изобилует DES и которые
крайненеэффективно реализуются на современных универсальных процессорах (хотя
оченьпросто аппаратно - путем разводки проводников в кристалле или на плате). В
силусказанного, при вдвое большем количестве раундов (32 против 16) программная
реализация ГОСТа на процессорах Intel x86 более чем в 2 раза превосходит
побыстродействию реализацию DES'а. Естественно, сравнивались близкие к оптимуму по
быстродействию реализации [1].
Из других отличий ГОСТа от DES'а надо отметить следующее:
1. На каждом раунде шифрования используется "раундовый ключ", в DES'е он 48-
битовый и вырабатывается по относительно сложному алгоритму, включающему
битовые перестановки и замены по таблице, в ГОСТе он берется как фрагмент
ключа шифрования. Длина ключа шифрования в ГОСТе равна 256 битам, длина
раундового ключа - 32 битам, итого получаем, что ключ шифрования ГОСТа
содержит 256/32=8 раундовых ключей. В ГОСТе 32 раунда, следовательно, каждый
раундовый ключ используется 4 раза, порядок использования раундовых ключей
установлен в ГОСТе и различен для различных режимов.
2. Таблица замен в ГОСТе - аналог S-блоков DES'а - представляет собой таблицу
(матрицу) размером 8x16, содержащую число от 0 до 15. В каждой строке каждое из
16-ти чисел должно встретиться ровно 1 раз. В отличие от DES'а, таблица замен в
ГОСТе одна и та же для всех раундов и не зафиксирована в стандарте, а является
сменяемым секретным ключевым элементом. От качества этой таблицы зависит
качество шифра. При "сильной" таблице замен стойкость шифра не опускается ниже
некоторого допустимого предела даже в случае ее разглашения. И наоборот,
использование "слабой" таблицы может уменьшить стойкость шифра до
недопустимо низкого предела. Никакой информации по качеству таблицы замен в
открытой печати России не публиковалось, однако существование "слабых" таблиц
не вызывает сомнения - примером может служить "тривиальная" таблица замен, по
которой каждое значение заменяется на него самого. Это делает ненужным для
компетентных органов России ограничивать длину ключа - можно просто
поставить недостаточно "сильную" таблицу замен.
3. В ГОСТе, в отличие от DES'а, нет начальной и конечной битовых перестановок
шифруемого блока, которые, по мнению ряда специалистов, не влияют
существенно на стойкость шифра, хотя влияют (в сторону уменьшения) на
эффективность его реализации.
(*) Что такое функция шифрования?
Многие алгоритмы, включая DES и ГОСТ, построены по одному и тому же принципу:
Процесс шифрования состоит из набора раундов-шагов, на каждом шагевыполняются
следующие действия.
1. Входной блок делится пополам на старшую (L) и младшую (R) части.
2. Вычисляется значение функции шифрования от младшей части (R) и раундового
ключа (k) X=f(R,k).Используемая на данном шаге функция и называется
ФУНКЦИЕЙ ШИФРОВАНИЯ РАУНДА. Она может быть одна для всех раундов,
или индивидуальна для каждого раунда. В последнем случае функции шифрования
различных раундов одного шифра отличаются, как правило, лишь в деталях.
3. Формируется выходной блок, его старшая часть равна младшей части входного
блока L'=R, а младшая часть это результат выполнения операции побитового
ИСКЛЮЧАЮЩЕГО ИЛИ (обозначим его (+)) для старшая части входного блока и
результата вычисления функции шифрования R'=L(+)f(R,k).
Tак вот, функция шифрования ГОСТа очень проста:
1. Младшая часть блока R и раундовый ключ складываются по модулю 2^32.
2. Полученное значение преобразуется по таблице замен - оно делится на 8 4-битовых
групп, и каждая группа заменяется на новое значение с использованием
соответствующего УЗЛА ЗАМЕН.
3. Полученное значение циклически сдвигается на 11 бит влево.
Как видите, в отличие от DES'а очень простая и легко реализуемая функция шифрования.
Более подробно обо всем этом можно прочитать в [2].
И последнее: ГОСТ не запантентован, поэтому его может свободно использовать
любоеюридическое и физическое лицо, если, конечно, это не противоречит
законодательству страны где находятся это лицо. Со стороны авторов ГОСТа
претензийнет и быть не может, так как юридические права на алгоритм ни за кем не
закреплены.
Составил Андрей Винокуров. (http://www.halyava.../crypto)
| |
