Моноалфавитные шифры

Модульное сложение и вычитание букв

Давайте рассмотрим пример модульного сложения и вычитания применимо к буквам.

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

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

Прибавить TODAY к NEVER по модулю 26

Вычесть TODAY из NEVER по модулю 26

Решение

TODAY= 19 14 03 00 24

NEVER= 13 04 21 04 17

Сумма = 32 18 24 04 41 06 18 24 04 15 = GSYEP

TODAY= 19 14 03 00 24

NEVER= 13 04 21 04 17

Разность = 06 10 -18 -04 07 06 10 08 22 07 = GKIWH

Давайте вспомним шифр Цезаря.

открытый текст

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

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

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

Если в строке «шифрованный текст» допустить использование любой из перестановок 26 символов алфавита, то мы получим 26!, или более 4х10²⁶ возможных ключей. Т.е метод последовательного перебора становится невозможным.

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

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

VUEPHZMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

EPYEPOPDZSUFPOMBZWPFUPZHMDJUDTMOHMQ

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

АНГЛИСКИЙ ЯЗЫК
a			p
b			q
c			r
d			s
e			t
f			u
g			v
h			w
i			x
j			y
k			z
l
m
n
o
На 1000 знаков

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

P 13,33 Z 11,67 S 8,33 U 8,33 O 7,50 M 6,67

H 5,83 D 5,00 E 5,00 V 4,17 X 4,17

F 3,33 W 3,33 Q 2,50 T 2,50 A 1,67

B 1,67 G 1,67 Y 1,67 I 0,83 J 0,83

C 0,00 K 0,00 L 0,00 N 0,00 R 0,00

Сравнивая эти результаты со среднестатистическими данными, можно заключить, что, скорее всего, буквы P и Z шифрованного текста являются эквивалентами букв e и t открытого текста, хотя трудно сказать, какой именно букве, какая соответствует. Буквы S, U, O, M и H, обладающие относительно высокой частотой появления в тексте, скорее всего, соответствуют буквам из множества {r,n,i,o,a,s}. буквы с низкой частотой появления (а именно A, В, G, Y, I, J), по-видимому, соответствуют буквам множества {w,v,b,k,x,q,j,z}.

Дальше можно пойти несколькими путями. Можно принять какие-то соответствия и на их основе попытаться восстановить текст, чтобы увидеть, похож ли этот текст на что-то осмысленное. Более систематизированный подход заключается в продолжении поиска в тексте новых характерных закономерностей. Например, может быть, известно, что в тексте должны присутствовать некоторые слова. Или можно искать повторяющиеся последовательности букв в шифрованном тексте. Один из эффективных способов заключается в подсчете частоты используемой комбинации, состоящих из двух букв. Такие комбинации называются биограммами. Известно, что в английском языке самой распространенной является биограмма th. В нашем тексте чаще сего встречается комбинация ZW. Поэтому можно предположить, что Z соответствует t, а W – h. Тогда из ранее сформулированной гипотезы вытекает, что Р это е. Заметим, что в шифрованном тексте имеется буквосочетание ZWP, и теперь мы можем представить его как the. В английском языке это самая распространенная триграмма.

Теперь обратите внимание на комбинацию ZWSZ в первой строке. Конечно, мы не можем сказать с полной уверенностью, что эти буквы принадлежат одному и тому же слову, но, если предположить, что это так, скорее всего это слово th?t. Отсюда можно заключить, чтоS a. Даже после небольшого анализа мы имеем следующий результат.

U

Z

Q

S

O

V

U

O

H

X

M

O

P

V

G

P

O

Z

P

E

V

S

G

Z

W

S

Z

O

P

F

P

E

S

X

U

D

B

M

E

T

S

X

A

I

Z

t

a

e

e

t

e

a

t

h

a

t

e

e

a

a

t

V

U

E

P

H

Z

M

D

Z

S

H

Z

O

W

S

F

P

A

P

P

D

T

S

V

P

Q

U

Z

W

Y

M

X

U

Z

U

H

S

X

e

t

t

a

t

h

a

e

e

e

a

e

t

h

t

a

E

P

Y

E

P

O

P

D

Z

S

Z

U

F

P

O

M

B

Z

W

P

F

U

P

Z

H

M

D

J

U

D

T

M

O

H

M

Q

e

e

e

t

a

t

e

t

h

e

e

t

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

it was disclosed yesterday that several inform but

direct contacts have been made with political

representatives of the viet cong in moscow

Моноалфавитные шифры легко раскрываются, так как они наследуют частотность употребления букв оригинального алфавита.

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

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

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

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. Если оказывается, что повторяющиеся буквы открытого текста образуют одну пару для шифрования, то между этими буквами вставляется специальная буква заполнитель, например х. В частности, такое слово как balloon будет преобразовано к виду ba lx lo on. Если перейдем на русский чтобы было более понятно возьмем слово рассвет что получим ра сх св ет.

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

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

4. Если не выполняется ни одно из приведенных выше условий, каждая буква из пары букв открытого текста заменяется буквой, находящейся на пересечении содержащей эту букву строки матрицы и столбца, в котором находится вторая буква открытого текста. Например, hs шифруется BP, а ea – как IM.

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

Дата добавления: 2014-01-03