Математические основы криптологии. Галуев Г.А. - 46 стр.

UptoLike

Составители: 

Рубрика: 

91
этот текст будет получен в шифрованном виде, то его содержи-
мому могут поверить, что недопустимо. Даже если перехвачен-
ное сообщение не будет чистым ключом
k
γ
, и будут, конечно,
некоторые искажения ложного шифрования, получатель может
их интерпретировать как помехи в канале связи.
Шифры перестановки.
При применении шифра замены символы исходного сооб-
щения могут превращаться во что угодно, но сохраняют в шиф-
ротексте своё первоначальное положение, т.е. местоположение
символа в исходном тексте такое же, как и в шифрованном тек-
сте. Если теперь к шифротексту применить шифр перестановки,
то местоположение символов в шифротексте может стать произ
-
вольным по отношению к расположению этих символов в ис-
ходном тексте. Это позволяет существенно увеличить стойкость
шифра. Примерами шифров перестановки являются скиталь, ма-
гические квадраты и другие, о которых говорилось на первой
лекции. Перестановка символов текста может осуществляться
двумя способами:
1. Перестановка может делаться до наложения на сообще-
ние случайной последовательности
k
γ
(т.е. до применения
шифра замены). В этом случае шифрованное сообщение имеет
вид
k
mpc
γ
+=
1
, где р - перестановка заданного типа. При та-
ком, способе, если в канале связи отсутствует сообщение, т.е.
m=0, то в канал попадает чистый ключ
k
γ
.
2. Перестановка может делаться после наложения на ис-
ходный текст случайной последовательности
k
γ
.
В этом случае
)(
k
mpc
γ
+
=
и при отсутствии сообще-
ния, т.е. при
m=0, в канал связи поступает ключ
k
Hp
, подверг-
нутый шифрованию перестановкой.
Перестановка может осуществляться отдельными битами
или такими группами бит, как байт или блок. Временная слож-
ность перестановки оценивается квадратом числа переставляе-
мых элементов. Поэтому перестановка бит будет в 64 раза слож-
нее, чем перестановка байтами. Вычислительных способов пере-
92
становок существует очень много. Например, широко применя-
ется
перестановка по номерам N от 0 до L-1 на основе рекур-
рентного соотношения
LMkNN
nn
mod)(
1
+
=
+
,
где
а)
К и М берутся из интервала (1,L -1)
б)
М - взаимно простое L
в)
К -1 делится на любой простой делитель L
г)
К -1 делится на 4,если L делится на 4.
Для хорошего запутывания такую перестановку делают не-
сколько раз, выбирая каждый раз
K и М случайным образом.
Шифр замены, осложненный перестановкой, обладает дос-
таточно высокой стойкостью. Его вскрытие без знания ключа
неоднозначно, что не позволяет сколько-нибудь уверенно рас-
шифровать сообщение. Существенно повысить стойкость шифра
можно, если вместо перестановки использовать линейное преоб-
разование вида
с=Lm, где L -невырожденная матрица случайно-
го линейного преобразования (или, что тоже самое, детерминант
L не равен нулю). Шифры на основе этого преобразования полу-
чили название
скремблеров или взбивалок.
Шифры взбивания.
Для шифров этого типа характерным является зависимость
каждого бита шифротекста от каждого бита исходного текста.
Детерминант случайной матрицы
L, также как и её элементы
может принимать два значения
0 и 1. Если
0)det(
=
L
, матрица
является
вырожденной. Основной проблемой использования
шифра взбивания является стремительное убывание числа невы-
рожденных матриц с увеличением их размера. Для получения
случайных невырожденных матриц специалистами фирмы
IBM
при сознании криптосистемы
Lucifer, ставшей впоследствии
(1976 год) национальным стандартам шифрования США под
именем DEC, был предложен достаточно эффективный способ,
не требующий много вычислений. Суть одного шага этого спо-
соба сводится к следующему: