Традиционное шифрование информации

Шифр Плейфейера.

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

Алгоритм Плейфейера основан на использовании матрицы букв размерности 5´5, созданной на основе некоторого ключевого слова. Матрица создается путем размещения букв, использованных в ключевом слове, слева направо и сверху вниз. Затем оставшиеся буквы алфавита размещаются в естественном порядке в оставшихся строках и столбцах матрицы. Буквы I и J считаются одной и той же буквой. Ниже приведен пример такой матрицы для ключевого слова monarchy (монархия).

 

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

 

Открытый текст шифруется порциями по две буквы в соответствии со следующими правилами.

1. Если оказывается, что повторяющиеся буквы открытого текста образуют одну пару для шифрования, то между этими буквами вставляется специальная буква-заполнитель, например X. В частности, такое слово как balloon будет преобразовано к виду ba lx lo on.
2. Если буквы открытого текста попадают в одну и ту же строку матрицы, каждая из них заменяется буквой, следующей за ней в той же строке справа – с тем условием, что для замены последнего элемента строки матрицы служит первый элемент той же строки. Согласно выше построенной матрицы AR шифруется как RM.
3. Если буквы открытого текста попадают в один и тот же столбец матрицы, каждая из них заменяется буквой, состоящей в том же столбце сразу под ней, с тем условием, что для замены самого нижнего элемента столбца матрицы берется самый верхний элемент того же столбца. В примере выше MU шифруется как CM.
4. Если не выполняется ни одно из приведенных условий, каждая буква из пары букв открытого текста заменяется буквой, находящейся на пересечении содержащей эту букву строки матрицы и столбца, в котором находится вторая буква открытого текста. Например, HS шифруется как BP, а EA – как IM (или JM, по желанию шифровальщика).

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

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

Шифр Хилла.

Еще одним интересным многобуквенным шифром является шифр, разработанный  математиком Лестером Хиллом (Lester Hill) в 1929 году. Лежащий в его основе алгоритм заменяет каждые m последовательных букв открытого текста m буквами шифрованного текста. Подстановка определяется m линейными уравнениями, в которых каждому символу присваивается числовое значение (A = 0, B = 1, …, Z = 25). Например, при m = 3 получаем следующую систему уравнений:

Эту систему можно записать в виде произведения вектора и матрицы в следующем виде:

или в виде

C = K´P,

где C и P  - векторы длины 3, представляющие соответственно шифрованный и открытый текст, а K – это матрица размерности 3´3, представляющая ключ шифрования. Операции выполняются по модулю 26.

Рассмотрим, например, как будет  зашифрован текст «PAYMOREMONEY» при использовании ключа

.

Первые три буквы открытого  текста представлены вектором (15 0 24). Таким  образом, K(15 0 24) = (275 819 486) mod 26 = (11 13 18) = LNS. Продолжая вычисления, получим для данного примера шифрованный текст LNSHDLEWMTRW.

Для расшифровки нужно воспользоваться  матрицей, обратной K. Обратной по отношению к матрице K называется такая матрица K^-1, для которой выполняется равенство K´K^-1 = K^-1´ K = I, где I – это единичная матрица (матрица, состоящая из нулей всюду, за исключением главной диагонали, на которой находятся единицы). Обратная матрица существует не для всякой матрицы, однако, когда обратная матрица имеется, для неё обязательно выполняется приведенное выше равенство. В нашем примере обратной матрицей является матрица

Это проверяется следующими вычислениями:

Легко проверить, что в результате применения матрицы K^-1 к шифрованному тексту получается открытый текст.

Обратная матрица квадратной матрицы A вычисляется как [A^-1]_ij = (-1)^i+j (D_ij)/det(A), где (D_ij) – определитель матрицы, получаемой путем удаления i-й строки и j-го столбца из матрицы A, а det(A) – определитель самой матрицы A. В нашем случае все вычисления проводятся по модулю 26.

В общем виде систему Хилла можно  записать в следующей форме:

C = E_K(P) = KP,

P = D_K(C) = K^-1C=P.

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

Полиалфавитные  шифры. Шифр Виженера.

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

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

Самым широко известным и одновременно самым простым алгоритмом такого рода является шифр Виженера (Vigenure). Этот шифр базируется на наборе правил моно алфавитной подстановки, представленных 26 шифрами Цезаря со сдвигом от 0 до 25 (для латинского алфавита). Каждый из таких шифров можно обозначить ключевой буквой, являющейся буквой шифрованного текста, соответствующего букве A открытого текста. Например, шифр Цезаря, для которого смещение равно 3, обозначается ключевой буквой D.

Для облегчения понимания и применения этой схемы была предложена матрица, названная «табло Виженера» (см. табл. 1). Все 26 шифров располагаются по горизонтали, и каждому из шифров соответствует своя ключевая буква, представленная в крайнем столбце слева. Алфавит, соответствующий буквам открытого текста, находится в первой сверху строке таблицы. Процесс шифрования прост – необходимо по ключевой букве x и букве открытого текста y найти букву шифрованного текста, которая находится на пересечении строки x и столбца y. В данном случае такой буквой является буква V.

 

Таблица 1. Табло Виженера.

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

a

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Чтобы зашифровать сообщение, нужен  ключ, имеющий туже длину, что и само сообщение. Обычно ключ представляет собой повторяющееся нужное число раз ключевое слово, чтобы получить строку подходящей длины. Например, если ключевым словом является deceptive, сообщение «we are discovered save yourself» шифруется следующим образом:

 

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

D

E

C

E

P

T

I

V

E

D

E

C

E

P

T

I

V

E

D

E

C

E

P

T

I

V

E

Ключ:

W

E

A

R

E

D

I

S

C

O

V

E

R

E

D

S

A

V

E

Y

O

U

R

S

E

L

F

Шифрованный текст:

Z

I

C

V

T

W

Q

N

G

R

Z

G

V

T

W

A

V

Z

H

C

Q

Y

G

L

M

G

J