Материал: Раздел 1. Криптографические одноключевые системы

S B C D F

G I P Q R

T U V X Z

Многоалфавитная система Виженера (1523-1596).

Квадрат Виженера выглядит следующим образом:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Система Виженера подобна системе Цезаря, в которой ключ меняется от шага к шагу. Квадрат Виженера используется как для зашифрования, так и для расшифрования. Для зашифрования читаем исходное сообщение из строк и ключи системы Цезаря из столбцов. Так, для исходного сообщения PURPLE и ключевого слова CRYPTO находим пересечение P- строки и C - столбца, получаем R Криптотекст имеет вид: RLPEES. Для расшифрования находим, в какой строке в C- столбце лежит R? Получаем P.

Существует много других подобных квадратов; одним из наиболее известных является квадрат Бьюфорта, строками которого являются строки квадрата Виженера, записанные в обратном порядке.

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

Криптосистема AUTOKLAVE (приписываемая математику 16 века Дж. Кардано, известному своими формулами для решения уравнений 3-й и 4-й степени) является дальнейшей модификацией системы Виженера. Исходное сообщение с некоторым сдвигом само является и ключом шифровки. В следующем сообщении ключ равен 6:

Сообщение: A I D S I S T R A N S M I T T E D T H R O U G H

Ключ: A I D S I S T RA N S M I T T E D T

Ключ используется, как в системе Виженера для подстановки Цезаря для каждой буквы. Пустые символы в начале ключа могут заполняться циклическим концом сообщения или ключевым словом. Так для ключевого слова IMMUNE получаем следующее начало для криптотекста:

Сообщение: A I D S I S T R A N S M I T T E D T H R O U G H

Ключ: I MMUNE A I D S I S T RA N S M I T T E D T

Криптотекст: I U PMVWT Z D F A E B KT RV F P K H Y J A

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

Сообщение: A I D S I S T R A N S M I T T E D T H R O U G H

Ключ: I MMUNE I U P M VWB L P Z N I J E I D O B

Криптотекст: I U PMVW B L P Z N I J E I D Q B Q V W X W I

Для криптоанализа последней версии криптоаналитику достаточно только найти длину ключа.

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

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

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

Система «кодовая книга» (CODE BOOK). Зашифрование осуществляется в соответствии с кодовой книгой, например,

Оригинал	Перевод
ATTACK	FISHING
...................	.............................
IN	BETWEEN
.....................	.............................
MORNING	WORK HOUR
.......................	..........................
THE	THE

В этом случае сообщение ATTACK IN THE MORNING (атака утром) будет зашифрована как FISHING BETWEEN THE WORK HOURSE (рыбалка в рабочем перерыве). Чтобы сделать криптотекст синтаксически правильным, в него добавляются разумные концовки.

1.2. Роторные криптографические машины.

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

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

До начала 50-х годов в армии США использовалась машина С-36 известного разработчика криптографических машин Бориса Хэйглина.

Некоторые известные криптографические машины, такие как немецкая ENIGMA, американская SIGABA, японские RED и PURPLE времен второй мировой войны, являются электромеханическими. Основным блоком в них является диск в виде кодового колеса с проволочными перемычками внутри, называемый ротором.

1.3.Криптографический стандарт des

В 1977 г. Был опубликован стандарт шифрования данных (DES- Data Encryption Standard) Национального бюро стандартов. DES- алгоритм был разработан специально для электронных устройств для зашифрования и расшифрования данных. До опубликования DES не было открытых публикаций, содержащих полный алгоритм для практического криптографического применения. Хотя в криптографии предполагается, что криптоаналитик знает используемую криптосистему, однако, большинство разработчиков криптосистем стараются скрыть детали их алгоритмов. DES является исключением. Существует два противоположных мнения о целесообразности опубликования общей системы шифрования данных. С одной стороны этот шаг рассматривается как вызов всем тем, кто пытается вскрывать системы. С другой стороны разработчики лучше всех знают слабости данной системы, что может позволять государственным организациям контролировать переговоры между банками, предприятиями и частными лицами.

Рассмотрим работу алгоритмов криптосистемы DES.

Пользователи выбирают ключ, содержащий 56 битов. Один и тот же ключ используется при зашифровании и расшифровании сообщений, поэтому храниться и передаваться он должен секретной почтой. В позиции 8, 16, 24,...,64 ключа добавляются двоичные символы так, чтобы сумма единиц в байтах была нечетной. Это позволяет проводить проверку ключа при передаче и хранении. 56 бит ключа, находящиеся на позициях 1,2,3,...,7,9,19,11,...17,19,20,21,...63 подвергаются следующей перестановке:

57 49 41 33 25 17 9

1 58 50 42 34 26 18

10 2 59 51 43 35 27 Блок C₀

19 11 3 60 52 44 36

-----------------------------------

63 55 47 39 31 23 15

7 62 54 46 38 30 22

14 6 61 53 45 37 29 Блок D₀

21 13 5 28 20 12 4

Перестановка определяется двумя блоками C₀ и D₀ по 28 бит в каждом. Далее используются итеративные процедуры преобразования. Получив некоторые блоки C_n-1 , D_n-1 , строим блоки C_n , D_n для n = 1,2,3,4,...,16 одним или двумя левыми сдвигами из блоков C_n-1 , D_n-1 в соответствии со следующей таблицей сдвигов:

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Число левых 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

сдвигов

При левых сдвигах все элементы блока смещаются влево на одну или две позиции циклически в пределах данного блока. Из блоков C_nD_n строятся перестановки K_n , состоящие из 48 бит (биты 9,18,22,25,35,38,43,54 в перестановки не входят). Остальные биты переставляются следующим образом:

14 17 11 24 1 5

3 28 15 6 21 10

23 19 12 4 26 8

16 7 27 20 13 2

41 52 31 37 47 55

30 40 51 45 33 48

44 49 39 56 34 53

46 42 50 36 29 32

Все вышеприведенные вычисления являются предварительными. Из исходного ключа вычислено 16 последовательностей K_n по 48 бит в каждой.

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

58 50 42 34 26 18 10 2

60 52 44 36 28 20 12 4

62 54 46 38 30 22 14 6

64 56 18 40 32 24 16 8

57 49 41 33 25 17 9 1

59 51 43 35 27 19 11 3

61 53 45 37 29 21 13 5

63 55 47 39 31 23 15 7

Полученный блок w’ условно разбивается на два блока w’ = L₀R_O, где каждый содержит по 32 бита. Далее используется итерационная процедура. Построив блоки L_n-1 и R_n-1 , 1 £ n £ 16 определим L_n и R_n следующим образом:

L_n = R_n-1,

R_n = L_n-1 Å f ( R_n-1,K_n), где Å - сложение по модулю 2, а функция f будет определена ниже.

Расшифрование сообщения производится достаточно просто: приведенные выше уравнения могут быть представлены в виде:

R_n-1 = L_n.,

L_n-1 = R_n Å f (L_n,K_n)

Можно вычислять L_n и R_n, спускаясь до L₀,R₀, после чего расшифрование становится очевидным.

Функция f строит из 32 - битовых блоков R_n-1 или L_n и 48 битового блока Kn 32 - битовый блок следующим образом. Блок из 32 бит расширяется до 48 бит в соответствии с таблицей:

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

То есть некоторые биты из 32 битового блока повторяются в 48 - битовом блоке. После такого расширения два 48 битовых блока побитно складываются по модулю 2. Результирующий 48 битовый блок делится на 8 блоков по 6 бит каждый B = B₁B₂B₃...B₈. Затем каждый из этих восьми блоков B_i трансформируется в 4-х битовый блок B_i’ с помощью соответствующей таблицы (для каждого блока B_i - своя таблица) и ряда правил.

14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7

S₁ 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

-------------------------------------------------------------------------------------

15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10

S₂ 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5

0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15

13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9

-------------------------------------------------------------------------------------

10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8

S₃ 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1

13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7

1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12