logo search
Коды и шифры

Выбор установок барабана в шифрмашине "Хагелин"

Теоретически установки барабана для шифрмашины "Хагелин" без перекрытий могут представлять собой любую комбинацию шести неотрицательных чисел, дающих в сумме 27 или меньше. На практике многие такие варианты будут очень слабыми с криптографической точки зрения. В идеале барабан должен одинаково часто давать каждое из возможных значений гаммы (от 0 до 25). Этот идеал недостижим, так как всего существует

26=64

возможных комбинации из шести штифтов, и следовательно, 64 возможных значения гаммы, в силу того, что каждое из шести колес может быть в данном положении либо активным, либо неактивным. Поскольку значение гаммы приводится по модулю 26, то 26 возможных значений результата этой операции не могут появляться одинаково часто, так как 64 не делится на 26. Для хорошо подобранного барабана каждое значение гаммы должно в среднем встречаться два или три раза. Так, барабан вида (9,9,9,0,0,0), очевидно, крайне слабый, так как он дает только значения гаммы, равные 0, 1 (получается из значения 27), 9 и 18, и даже они появляются неравновероятно, а именно:

Значение гаммы

0

1

9

18

Число появлений (из 64 возможных)

8

8

24

24

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

Пример 10.3

Ниже приведен шифрованный текст сообщения, полученный на шифрмашине "Хагелин" с барабаном (0,0,0,9,9,9). Знак X заменяет пробелы и пунктуацию. Требуется дешифровать сообщение.

ZCTALáBRDSVáIBGDZáSMFVM.

Решение

Для такого барабана возможны только значения гаммы, равные 0, 1, 9 и 18. Если каждую букву шифрованного текста вычесть из этих четырех значений и выписать полученные тексты в четыре строчки, то в этих четырех строчках должны содержаться буквы открытого текста. Поскольку 9 и 18 встречаются в три раза чаще, чем 0 и 1, то, скорее всего, большая часть букв открытого текста лежит в третьей и четвертой строчках. Буква X используется вместо пробелов и пунктуации, и, чтобы выделить ее, будем везде заменять ее знаком ^.

Можно избавиться от необходимости утомительного вычитания числового представления букв из знаков гаммы, если раз и навсегда построить таблицу. У таблицы есть дополнительное преимущество: в отличие от таблиц для книжных шифров главы 7, благодаря упомянутой выше симметрии процессов зашифрования-расшифрования для "Хагелина", одну и ту же таблицу можно использовать как для зашифрования, так и для расшифрования. После построения этой таблицы (см. таблицу 10.2) для получения буквы открытого (шифрованного) текста надо взять элемент, стоящий на пересечении строки, соответствующей букве шифрованного (открытого) текста, и столбца, соответствующего значению гаммы. Действуя таким образом, получаем таблицу 10.3.

Таблица 10.2 Таблица зашифрования-расшифрования для шифрмашины "Хагелин"

Знаки гаммы

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

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

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

C

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

D

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

E

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

F

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

G

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

H

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

I

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

J

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

K

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

L

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

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

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

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

P

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

Q

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

R

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

S

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

T

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

U

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

V

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

W

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

X

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

Y

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

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

Таблица 10.3.

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

Z

C

T

A

L

B

R

D

S

V

I

B

G

D

Z

S

M

F

V

M

гамма = 0

B

Y

H

A

O

Z

J

^

I

F

S

Z

U

^

B

I

O

V

F

O

гамма = 1

C

Z

I

B

P

A

K

Y

J

G

T

A

V

Y

C

J

P

W

G

P

гамма = 9

K

H

Q

J

^

I

S

G

R

O

B

I

D

G

K

R

^

E

O

^

гамма = 18

T

Q

Z

S

G

R

B

P

A

^

K

R

M

P

T

A

G

N

^

G

Использование знаков пробела (^) оказывается полезным, и мы без труда восстанавливаем открытый текст, который в таблице 10.3 выделен жирным шрифтом:

THIS IS A BAD CAGE

Попробуйте решить задачу чуть-чуть потруднее.

Задача 10.1

С помощью шифрмашины "Хагелин" с барабаном (0,5,5,5,5,5) получен следующий шифрованный текст:

CBZPCáCJXWYáCXSHNáIQUSR.

Дешифруйте сообщение.

Так как некоторые барабаны оказываются "плохими" (то есть слабыми с криптографичекой точки зрения), то возникают следующие вопросы:

  1. Сколько всего существует возможных барабанов?

  2. Сколько среди них "хороших"?

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

число различных барабанов равно количеству представлений числа 27 в виде суммы шести неотрицательных целых чисел.

И хотя простой формулы для подсчета этого числа не существует, можно воспользоваться красивым математическим тождеством и с помощью компьютера вычислить это значение: оно равно 811. Если дополнительно потребовать, чтобы напротив каждого колеса стояло хотя бы по одному выступу (так как если напротив колеса нет ни одного выступа, то оно как бы вообще отсутствует), то это число сокращается до 331. Тем же способом можно подсчитать, что если в барабане используется только 26 или 25 выступов, то число вариантов сокращается соответственно до 709 и 612 (если допускается отсутствие выступов напротив одного или более колес), и до 282 и 235 (если это не допускается). Однако следует помнить, что число возможных барабанов, которые необходимо рассматривать криптоаналитику, гораздо больше, так как числа внутри шестерки чисел, задающей барабан, могут быть переставлены, и в этом случае получатся разные последовательности знаков гаммы, хотя они будут иметь близкие статистические характеристики. Поэтому для случая 27 выступов получается 201376 возможных вариантов, а не 811 (подробнее см. приложение M18).

Сколько из общего количества различных барабанов (331) будут "хорошими"? Очевидно, это зависит от того, что именно мы понимает под словом "хороший". Если это значит, что

"хороший" барабан - это такой, который порождает все возможные значения гаммы в диапазоне от 0 до 25,

то можно с помощью компьютера вычислить, для скольких барабанов из этих 331 это выполняется. Ответ будет 113. Перестановка чисел внутри шестерки не изменяет качества барабана: "хороший" барабан остается "хорошим", "плохой" остается "плохим". Если разрешить отсутствие выступов, то из общего количества возможных барабанов (881) останется только 120 "хороших". Другими словами, только 7 барабанов, не имеющих выступов против какого-нибудь колеса, дают все 26 возможных значений гаммы (по модулю 26). Конечно, даже "хороший" барабан можно испортить очень несимметричной установкой штифтов (например, 90% активных, 10% неактивных).

Задача 10.2

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

  1. 0,2,3,4,8,10;

  2. 1,2,2,3,4,15;

  3. 1,2,2,4,5,13;

  4. 2,3,3,3,4,12;

  5. 2,3,3,3,5,11;

  6. 2,3,4,4,7,7.