Информационные технологии Современные алгоритмы шифрования Симметричные системы

1.

Информационные
технологии
Современные алгоритмы шифрования
Симметричные системы

2.

Симметричная криптосистема
Для шифрования и дешифрования используется один и тот же секретный ключ.
Задача обеспечения конфиденциальности информации сводится к задаче обеспечения
конфиденциальности ключа
P
Алгоритм
шифрования
EK
C
K
Алгоритм
дешифрования P’
DK
K
P – открытый текст
C =дешифруется
EK (P) с помощью
Открытый текст
с криптотекст
K – симметричный
ключ шифруется
шифрования
помощью (зашифрованный
секретного ключатекст)
C – криптотекст
P’того
= DжеKключа
(EK (P))
P’ = P
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

3.

Симметричная криптосистема
Высокая скорость шифрования/дешифрования
Возможность использования для обеспечения конфиденциальности при
хранении своей информации
Необходимо обеспечить обмен секретными ключами по защищенному
каналу при передаче зашифрованной информации
Симметричная криптосистема для обеспечения связи друг с другом группы
абонентов предусматривает использование матрицы ключей парной связи.
1
1
2
3
…
n
K12
K13
…
K1n
Набор ключей абонента 1
K23
…
K2n
Набор ключей абонента 2
…
K3n
Набор ключей абонента 3
…
2
K21
3
K31
K32
…
…
…
…
…
n
Kn1
(с) Смоленцев С.В. кафедра АВТ ГМА
Kn2
Kn3
…
2007
Набор ключей абонента n

4.

Блочные шифры
Характерной особенностью блочных криптоалгоритмов является тот факт, что в ходе
своей работы они производят преобразование блока входной информации
фиксированной длины и получают результирующий блок того же объема, но
недоступный для прочтения сторонним лицам, не владеющим ключом.
C = EK (P)
P = DK (С)
Ключ K является параметром блочного криптоалгоритма и представляет собой
некоторый блок двоичной информации фиксированного размера. Исходный (P) и
зашифрованный (C) блоки данных также имеют фиксированную разрядность, равную
между собой, но необязательно равную длине ключа.
Блочные шифры являются основой, на которой реализованы практически все
криптосистемы. Методика создания цепочек из зашифрованных блочными
алгоритмами байт позволяет шифровать ими пакеты информации неограниченной
длины.
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

5.

Требования к функции шифрования
На функцию стойкого блочного шифра C = EK (P) накладываются следующие
требования:
1. Функция E должна быть обратимой.
1. Не должно существовать иных методов прочтения сообщения Р по известному
блоку С, кроме как полным перебором ключей K.
1. Не должно существовать иных методов определения каким ключом K было
произведено преобразование известного сообщения Р в сообщение С , кроме как
полным перебором ключей.
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

6.

Сеть Фейштеля
Используется как основа многих блочных алгоритмов шифрования.
Независимые потоки информации, порожденные из
исходного блока, называются ветвями сети. В
классической схеме их две.
Vi - функции от материала ключа.
F – образующая функция.
Действие, состоящее из однократного вычисления
образующей функции и последующего наложения ее
результата на другую ветвь с обменом их местами,
называется циклом или раундом (англ. round) сети
Фейштеля.
Оптимальное число раундов от 8 до 32. Важно то,
что увеличение количества раундов значительно
увеличивает криптостойкость любого блочного
шифра к криптоанализу.
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

7.

DES
DES (Data Encryption Standard - Стандарт Шифрования Данных) - был принят в 1977 году
правительством США как официальный стандарт для несекретных сведений (до 2000 года).
Разработан фирмой IBM.
С момента опубликования DES широко изучался и известен как один из лучших симметричных
алгоритмов.
DES – симметричный алгоритм использующий 56-разрядный ключ (8 четных битов полного 64битного ключа не используются).
Текст обрабатывается блоками по 64 бита.
Аналогичные блочные симметричные алгоритмы шифрования:
Название
алгоритма
Размер блока
Длина ключа
64 бита
128 бит
64 бита
128 бит
Разработал Bruce Schneier
64 бита
128 – 448 бит
Российский стандарт шифрования
64 бита
256 бит
TwoFish
Разработал Bruce Schneier
128 бит
128 – 256 бит
MARS
Разработала корпорация IBM
128 бит
128 – 1048 бит
IDEA
примечание
Европейский стандарт шифрования
CAST128
BlowFish
ГОСТ 28147-89
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

8.

Схема работы DES
64 битный блок текста
Начальная перестановка
56 битный ключ
Итерация 1
Итерация 2
Text
Crypt
Итерация 16
Key
числа
Перестановка 32 бит
P, Pk
S
Инверсная перестановка
L(i)
xor
64 битный блок
шифротекста
2007
5 5 4 3 2 1 1
1 2 3 4 5 6 7
8 0 2 4 6 8 0
6 1
5 1
4 1
3 1
2 1
2 1
9
0 0
2 1
4 2
6 3
8 4
0 5
2
6 1
1
5 1
4 2
3 2
3 2 2
1
2 8
7
4 9
6 0
8 1
0 2 3
4
6 2
2
5 2
4 2
4 2
3 3
2 3
1
4 6 7
5
8 8
0 9
2 0
4 1
6
5 3
3
4 3
4 3 3
2 3
1 3
9
7 4
3
9 5
1 6
3 7
5 8
7 9
5 4
4
5 4 4
3 4
2 4
1 4
1
9 2
1
1 3 4
5 5
7 6
9 7
1
6 5 5
4
4 5
3 5
2 5
2 5
1
1 0
9
3 1
5 2
7 3
9 4
1 5
3
6 5 5
5
4 6
3 6
3 6
2 6
1
исходный текст73 (блок
64
бита)
5
8
7
9
9
0
1
3
2
5
3
4
4 1 5 2 6 3
1 2
8 3 4 5 6 7 8
0
8 6 6 4 4 2
зашифрованный
блок
3 1 1
4 1 1
5 1
2 1
6 1
3
9 7
9 0ключ
7 2
1
5 3
5 4
3 5
3 6
1
64-х разрядный
3 1 1
1
4 2
1 2
5 2 2
6 2
3
6
6 0
9
4ветке
4 алгоритма
1
2 3
2 4
0
разрядность7823 на82данной
4 2
2
1 2
5 3
2 3
6 3
2
5
7
5
6
5
7
3
8
3
9
1
0
1
9
2
перестановки
3 3 3
4 3
1 3
5 3
2 3
6 4
2
4
6 4 5
3
4 6
2 7
2 8
0 9
0 0
8
подстановка
-> 441бита
3 6 бит
4
4 4
5 4
4
1 4
5 4
2
3
5 2 3 4
1
1 5
1 6
9 7
9 8
7
сдвиг (i -- номер
3 5 итерации)
4
4 5
5
1 5 5
1 5 5
2
2
4 0 1
9
2 2
0 3
0 4
8 5
8 6
3 модулю
5
5 5
4 26 6
4 6
1 6
5 6
2
сложение по
1
9
3 8 9
7
1 0 1
9 2
7 3
7 4
5
(с) Смоленцев С.В. кафедра АВТ ГМА
8
2
1
4
6
2
6
4
3
8
2
4
1
0
4
3
8
5
5
6
6
7
4

9.

TripleDES
Использование короткого ключа (56 бит) в алгоритме DES снижает его
криптостойкость. Для ее повышения в 1979 году разработана модификация
алгоритма, предусматривающая использования двух ключей (всего 112 бит).
Использование алгоритма возможно и для реализации простого DES : K1=K2
P
K
K
K
K
K
K
1
2
1
1
2
1
Е
D
Е
D
E
D
C
С
шифрование
2007
(с) Смоленцев С.В. кафедра АВТ ГМА
дешифрование
Р

10.

Конкурс AES
В 1997 году Американский институт стандартизации NIST – National Institute of
Standards & Technology объявил конкурс на новый стандарт симметричного
криптоалгоритма названного AES – Advanced Encryption Standard, который
должен стать де-факто мировым криптостандартом на ближайшие 10-20 лет.
Требования, предъявленные к кандидитам на AES в 1998 году:
1. алгоритм должен быть симметричным,
2. алгоритм должен быть блочным шифром,
3. алгоритм должен иметь длину блока 128 бит, и поддерживать три длины ключа :
128, 192 и 256 бит.
Дополнительно кандидатам рекомендовалось:
1. использовать операции, легко реализуемые как аппаратно (в микрочипах), так и
программно (на персональных компьютерах и серверах),
2. ориентироваться на 32-разрядные процессоры,
3. не усложнять без необходимости структуру шифра для того, чтобы все
заинтересованные стороны были в состоянии самостоятельно провести
независимый криптоанализ алгоритма и убедиться, что в нем не заложено
каких-либо недокументированных возможностей.
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

11.

Финалисты конкурса AES
На первом этапе в оргкомитет соревнования поступило 15 заявок из совершенно
разных уголков мира. В течение 2 лет специалисты комитета, исследуя
самостоятельно, и изучая публикации других исследователей, выбрали 5 лучших
представителей, прошедших в "финал" соревнования.
Алгоритм Создатель
Страна
Быстродействие
(asm, 200МГц)
MARS
IBM
US
8 Мбайт/с
RC6
R.Rivest & Co
US
12 Мбайт/с
Rijndael
V.Rijmen & J.Daemen
BE
7 Мбайт/с
Serpent
Universities
IS, UK, NO
2 Мбайт/с
TwoFish
B.Schneier & Co
US
11 Мбайт/с
2 октября 2000 года NIST объявил о своем выборе – победителем конкурса стал
бельгийский алгоритм RIJNDAEL. С этого момента с алгоритма-победителя сняты
все патентные ограничения – его можно будет использовать в любой
криптопрограмме без отчисления каких-либо средств создателю
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

12.

Победитель конкурса AES – алгоритм RIJNDAEL
Данный алгоритм разработан двумя специалистами по криптографии из Бельгии
(V.Rijmen и J.Daemen). Он является нетрадиционным блочным шифром, поскольку
не использует сеть Фейштеля для криптопреобразований.
Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива
байт размером 4х4, 4х6 или 4х8 в зависимости от установленной длины блока. Далее
на соответствующих этапах преобразования производятся либо над независимыми
столбцами, либо над независимыми строками, либо вообще над отдельными байтами
в таблице.
Алгоритм обладает высокой скоростью работы и хорошей криптостойкостью.
Поддерживаются следующие длины ключей: 128, 192, 256 бит.
Размеры блоков данных: 128, 192, 256 бит
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

13.

Алгоритм AES
128 битный блок текста
rk[0]
rk[1]
128 битный ключ шифрования
rk[2]
rk[3]
rk[4]
rk[5]
rk[6]
rk[7]
rk[8]
rk[9]
rk[10]
Шаг
Шаг
Шаг
1.
3.Посимвольная
4.
Независимое
Полученный
перемешивание
подстановка.
массив
складывается
Каждый
значений
по
байт
в
Шаг 2. Поворот
строк
влево.
используется
столбцах. 128
Каждый
модулю
как
индекс
столбец
2блок
с включом
таблице
рассчитывается
(S-блоке) и
битный
шифротекста
умножением
заменяется
данной итерации
на
себя
значение
на постоянную
– массивом
из этой таблицы
матрицу.
rk[i]
поворот
0 0 0 0
на 0 байт
0
1 1
1 2
1 3
1
на 1 байт
0
3
1
0
2
1
3
2
2 2 2 2
на 2 байта
0
2
1
3
2
0
3
1
3 3 3используется
3
4. Проводят 10 итераций, в каждой из которых
на 3ибайта
2. Из открытого текста
3. Предварительное
выбирается очередной
действие:
1282
битный
блок
0
1
1
2
3
3
0
5. Результирующий
1. Из ключа шифрования
соответствующий
массив содержит
генерируется
массив
128 битный
rk[i].
11 массивов
блок шифротекста
rk[i]
массив state
копируется
поразрядно
в массив
складывается
state (по по
столбцам)
модулю 2 с rk[0]
Каждая итерация состоит из 4 шагов
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

14.

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

15.

Режим электронного шифроблокнота
(ECB - Electronic Code Book)
Текст разбивается на блоки и каждый блок шифруется независимо от других.
Одинаковым блокам текста соответствуют одинаковые блоки шифротекста.
P
P
0
1
P
C блоки)
Пример атаки
(128 битные
2
имя клиента
K
Е
K
AAAA
BBBB
CCCC
Е
K
0
C
C
1
2
идентификатор
сумма выплат
xxxx
xxxx
K
xxxx
000000010000000
0000000000000010
K0
000000000005001
4
Е
D
D
D
C
C
C
P
P
P
0
1
2
0
1
2
шифрование
дешифрование
Злоумышленник
может даже не зная
ключа заменить
Возможна
атака
на
зашифрованное
сообщение
Информация
о выплатах
зашифрована
блочным
блоки сообщения,
например,
скопировать
3 блокшифром
в 6.
2007
K
(с) Смоленцев С.В. кафедра АВТ ГМА

16.

Режим сцепления блоков шифра
(CBC - Cipher Block Chaining)
Каждый блок открытого текста перед зашифровкой складывается по модулю 2 с
предыдущим уже зашифрованным блоком. При этом одинаковым блокам открытого
текста соответствуют разные блоки шифротекста.
P
P
P
C
C
C
0
1
2
0
1
2
IV
K
Е
K
Е
K
Е
K
D
K
D
K
D
IV
C
C
C
P
P
P
0
1
2
0
1
2
шифрование
дешифрование
IV (Initialization Vector) -вектор инициализации передается вместе с шифротекстом.
2007
может передавать только блоки шифротекста, что не подходит для организации
интерактивной связи
(с) Смоленцев С.В. кафедра АВТ ГМА

17.

Режим шифрованной обратной связи
CFB – Cipher Feed Back
Применяется для обеспечения возможности отправки шифротекста побайтно, без
накопления полного блока исходного текста. Для этого используется сдвиговый
регистр, по размеру равный блоку шифрования.
Для начала шифрования требуется вектор инициализации (начальное заполнение
сдвигового регистра). При дешифрации так же используется алгоритм шифрования!
С С С С С С С С
С С С С С С С С
2
2
3
K
4
5
6
7
8
9
Е
K
Выбор левого
байта
4
5
6
7
8
9
Е
Выбор левого
байта
P
С
С
Р
1
1
1
1
0
0
0
0
шифрование
2007
3
дешифрование
В случае повреждения 1 передаваемого байта ошибка распространится на пакет
равный размеру блока (т.е. пока ошибочный байт находится в сдвиговом
регистре)
(с) Смоленцев С.В. кафедра АВТ ГМА

18.

Режим группового шифра
С помощью ключа шифруется вектор инициализации, а затем на каждом шаге с
помощью ключа шифруется выходной блок предыдущего шага. Таким образом
получают ключевой поток, который по модулю 2 складывается с открытым текстом.
Ключевой поток не зависит от передаваемых данных и может быть вычислен
заранее.
IV
Атака при многократном использовании
K
одного ключевогоЕ
потока:
P1 xor K = C1 – шифротекст 1
P2 xor K = C2 – шифротекст 2
Ключевой поток
Ключевой поток
если провести операцию
C1 xor C2 = P1 xor
P2
шифротек
шифротек
текст
ст
тем
самым удалят ст
криптографическую защиту
(ключ) и получат комбинацию
открытых текстов
шифрование
дешифрование
K
текст
IV
Е
Нельзя использовать одну пару (K, IV) повторно, поскольку они порождают
одинаковый ключевой поток.
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

19.

Режим счетчика
Все режимы шифрования (кроме ECD) не дают возможности осуществить доступ к
произвольной части зашифрованных данных. Это не удобно особенно при хранении
больших объемов зашифрованных данных.
В режиме счетчика шифруется вектор инициализации плюс некоторая константа
(номер блока). Полученный шифроблок складывается по модулю 2 с текстом. При
дешифрации любого блока не нужно расшифровывать все предыдущие блоки.
IV+0
IV+n
IV+0
…
K
P
C
P
C
0
0
n
n
K
Е
Е
IV+n
…
K
C
P
C
P
0
0
n
n
K
шифрование
Е
Е
дешифрование
Нельзя использовать одну пару (K, IV) повторно, поскольку они порождают
одинаковый ключевой поток. Возможна атака как в предыдущем случае.
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

20.

Поточные шифры
Теоретическое открытие, оказавшее существенное влияние на развитие
криптографии, было сделано в работе «Теория связи в секретных системах»
К.Шеннона, опубликованной в 1949 году. В ней сформулированы и доказаны
необходимые и достаточные условия стойкости системы шифра. Они
заключаются в том, что получение злоумышленником шифротекста не изменяет
вероятностей используемых ключей. При этом было установлено, что
единственным таким шифром является так называемая лента одноразового
использования, когда открытый текст шифруется с помощью случайного ключа
такой же длины. Это обстоятельство делает стойкий шифр очень дорогим в
эксплуатации.
Поэтому основная проблема криптографии — трудность генерирования
непредсказуемых двоичных последовательностей большой длины с применением
короткого случайного ключа. Для ее решения используются генераторы двоичных
псевдослучайных последовательностей. Получаемые программно из ключа
псевдослучайные ряды чисел или бит называются гаммой. Стойким считается
генератор:
• с большим периодом (повторяемость знаков) ряда;
• равновероятностью знаков в ряде;
• простым способом получения знаков.
2007
(с) Смоленцев С.В. кафедра АВТ ГМА

21.

Поточный шифр RC4
Алгоритм RC4 разработан в 1987 году в RSA Data Security. В 1994 году опубликован
в Интернет. Позволяет генерировать гамма-последовательность из короткого ключа.
3.
4. С
Генерируется
2.
1.помощью
Ключевой
Подстановочный
ключевого
массив
гамма-последовательность,
массив
размером
массива
размером
256
инициализируется
байт
256
(К-box)
которая
байт
заполняется
XOR(S-box)
с символами
ключом
заполняется
(если
S-box
текста
необходимо,
числами
дает шифротекст
0..255
повторяя)
0
1
2
3
к у р с а ……..…..
н т
K
2
0
3
4
2
0
4
3
2
0
4
0
2
0
4
1
2
0
2
4
7
0
2
6
1
0
9
3
6
1
0
8
4
9
j
S
2
3
0
4
2
4
0
2
1
3
2
Pi
2
0
3
7
2
0
4
2
2
3
0
4
Si+Sj
2
0
4
3
2
0
4
0
i
……..…..
2 2 2
0 2
4
0 3
0
1 4 7
Si
2
0
4
2
2
5
3
j
2
3
0
4
……..…..
2 2 2
0 4
4
0 4
0
3 0 1
2
2
0
4
2
3
0
7
……..…..
2 2 2
4
0 3
0 4
0
2 4 3
2
4
0
0
S
Gi150 506 1307 1908 1209 1101 201 2301 1101 701 301 601 1601 2201 201 j 302 702 1602 802
4
6
1
4
8
0
4
1
7
2
9
3
7
Si+Sj
7
4
5
9
6
7
6
8
6
0
9
8
0
2
1
2
9
8
3
2
5
4
2
5
5
……..…..
j
j
……..…..
2
0
4
1
2
2
0
4
2
3
0
7
2
4
0
2
2
3
0
4
2
0
4
3
2
0
4
0
2
0
4
1
2
0
4
3
8
1
2
0
9
4
8
9
2
6
0
5
2
0
2
7
0
5
1
2
8
0
5
4
2
2
0
4
5
0
3
2
5
0
5
5
4
1
2
0
8
5
4
5
Ci
j=0
for i=0 to 255
j=(j+Ki+Si) mod 256
swap(Si,Sj)
i = (i+1) mod 256
j = (j+Sj) mod 256
swap(Si,Sj)
t = (Si + Sj) mod 256
gi = St
Ci = Pi XOR gi
P
C
2007
(с) Смоленцев С.В. кафедра АВТ ГМА