Технологии защиты информации в сети

Примеры
Задачи

Возрождение

Лекции
Чертеж

Математические основы криптографии.

Криптографические примитивы.

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

Подстановки

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

Таблица 2 - Таблица простой замены

Символы шифруемого текста

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Заменяющие символы

С

П

Х

Л

Р

З

Э

М

А

Ы

Я

Д

Ю

Т

Г

Ж

Символы шифруемого текста

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ь

Ы

Ъ

Э

Ю

Я

Заменяющие символы

Н

Й

О

Ц

Б

Ф

У

К

Ч

Ш

Щ

Ь

И

Ъ

Е

В

Используя эту таблицу зашифруем слово криптография. Получим: янажоглнсбав.

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

Перестановки

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

Пример перестановки. Зашифровать текст «встреча состоится в 16-20» с помощью перестановки

N

1

2

3

4

5

6

7

8

P(N)

4

7

8

1

6

5

2

3

(первый символ переходит на 4-ю позицию, второй – на седьмую и т.д.).

Длина текста равна 24. Разобьем текст на блоки по восемь символов и переставим каждый блок по- отдельности. Получим:

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

M

в

с

т

р

е

ч

а

с

о

с

т

о

и

т

с

я

в

1

6

-

2

0

Enc(M)

р

а

в

ч

е

с

т

т

т

с

с

и

о

о

с

1

2

0

я

-

6

в

Получился текст «ра вчестттссиоос120я-6 и».

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

в

с

т

р

е

ч

а

с

о

с

т

о

и

т

с

я

в

8

-

2

0

Читаем по столбцам «вчасс8сатя-т о 2рсив0еот »

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

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

В методе DES используется расширенная перестановка следующего вида

32

1

2

3

4

5

4

5

6

7

8

9

8

9

10

11

12

13

12

13

14

15

16

17

16

17

18

19

20

21

20

21

22

23

24

25

24

25

26

27

28

29

28

29

30

31

32

1

В этом методе шифруемый текст разбивается на блоки по 64 бита, и каждый блок подвергается серии перестановок. Сначало выделяется первая половина блока из 32 битов – некоторый вектор X(x1, x2, ..., x32). Он подается на вход этой перестановки, и после преобразования будет получен вектор E(X) длины 48 бит. При этом 1-й бит вектора E(X) будет равен x32, второй – x1, третий – x2 и т.д. согласно таблице расширенной перестановки.

4.1.3. Гаммирование.

Гаммированием называется преобразование, при котором складываются посимвольно элементы двух последовательностей – исходного текста и ключевой последовательности. Если исходный текст задан в виде последовательности символов, заданных ASCII или ANSI- кодами (кодовые таблицы DOS – 861 или Windows – 1251 соответственно), которые являются числами от 1 до 255, то ключевая последовательность задается также в виде последовательности чисел от 0 до 255 и сложение с ключевой последовательностью происходит по модулю 256.

Пример. Исходный текст – слово «пароль». В кодах ASNI получим «239, 224, 240, 238, 235, 252». Гамма последовательность – 174, 245, 211. Длина гаммы меньше длины текста, поэтому повторяет гамму дважды: 

Текст

239

224

240

238

235

252

Гамма

174

245

211

174

245

211

Шифрованное

соообщение=

157

213

195

156

224

207

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

В методе DES на втором подшаге 48-битовый вектор, полученный путем расширенной перестановки (см. пред. раздел), суммируется с 48-битовой выборкой из 56-битового ключа K.

4.1.4. Нелинейное преобразование с помощью S-боксов

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

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

14

4

13

1

2

15

11

8

3

10

6

12

5

9

0

7

0

15

7

4

14

2

13

1

10

6

12

11

9

5

3

8

4

1

14

8

13

6

2

11

15

12

9

7

3

10

5

0

15

12

8

2

4

9

1

7

5

11

3

14

10

0

6

13

Перенумеруем строки s-бокс двоичными наборами (0,0), (0,1), (1,0), (1,1), а столбцы – 4-х битовыми наборами в лексикографическом порядке. Тогда значением 6-битового вектора (x1,x2,x3,x4,x5,x6) является двоичный набор, соответствующий числу, записанному в строке с номером (x5,x6) и столбцом (x1,x2,x3,x4).

Пример. Пусть входной вектор имеет вид (1, 0, 1, 0, 1, 1). Тогда номер строки m=(1, 1)=3, что соответствует 4-й строке (нумерация идет от 0), номер стролбца n=(1, 0, 1, 0)=10, что соответствует 11-у столбцу. В клетке с координатами (m+1, n+1)=(4, 11) находится число 3, равное (0,0,1,1) в двоичном представлении. Значит, S1(1, 0, 1, 0, 1, 1)= (0,0,1,1).

4.1.5. Комбинированные методы.

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

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

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

1) подстановка + гаммирование;

2) перестановка + гаммирование;

3) подстановка + перестановка.

 Эти приемы были использованы в методе DES. Суть алгоритма (алгоритм разработан для блока данных длиной 64 бит) заключается в преобразовании, которое состоит из серии перестановок (правая половина блока становится левой половиной “следующего” блока), операций запутывания (из правой половины блока длиной 32 бит формируется код длиной 48 бит, а каждый бит ключа размножается и превращается в подключ длиной 48 бит) и логических операций (с помощью функций ИСКЛЮЧАЮЩЕЕ ИЛИ производится обработка кода длиной 48 бит и подключа такой же длины, затем из получившегося сегмента длиной 48 бит выбираются 32 бит и, наконец, с помощью функции ИСКЛЮЧАЮЩЕЕ ИЛИ производится совместная обработка отобранных на втором этапе 32 бит и левой половины блока длиной 32 бит). Этот процесс перестановок в половине блока, повторных операций запутывания и многократных логических операций выполняется 16 раз (или говорят 16 раундов). Ключ состоит из 56 бит, из которого генерируется 16 подключей длины 48 бит (за счет выполнения операций запутывания). Каждый подключ используется в своем раунде.

Свое развитие DES получил в ГОСТ 281478-89 (отечественный стандарт на шифрование данных), который увеличил длину ключа до 256 бит, число раундов до 32, и допустил произвольные перестановки.

Ланшафтный дизайн