Шифры перестановки
Из-за отмеченных особенностей шифр замены в чистом его виде никогда не применяется, а всегда употребляется вместе с перестановкой, например, бит внутри байта. Если после замены символы сообщения превращались во что угодно, но сохраняли в шифровке свое исходное местоположение, то после перестановки они там и расположены еще и где угодно, что надежно защищает шифровку от атак криптологов. Потому что перестановку можно рассматривать как умножение вектора сообщения на матрицу перестановки бит Р с элементами 0 и 1 и размером в длину сообщения в битах. Рассмотрим два случая.
1. Перестановка может делаться до наложения на
сообщение случайной последовательности, то
есть s'=Pt+y. В случае, если текст в сообщении
отсутствует t=0 и идут нули или пробелы, то
s'=y, а в канал связи попадает чистый ключ.
2. Перестановка может делаться и после наложе-
ния на сообщение случайной последовательно-
сти, то есть s"=P(t+y). В случае, если текст в со-
общении отсутствует t=0 и идут нули или пробе-
лы, как s"=Py, а в канал связи попадает ключ,
шифрованный перестановкой.
Поэтому обычно предпочтение отдается второй схеме, когда в отсутствие текста шифровка представляет собой не чистый ключ, а осложненный перестановкой. Хотя и в том, и в другом случае наложение на шифровку своего текста для введения получателя в заблуждение ничего не дает. Однако перестановки необходимы и для того, чтобы атака на ключ стала неэффективной. Если передача идет побайтно, то достаточно лишь переставлять биты внутри байта, чтобы с вероятностью 0.97 исказить его и сделать перехват ключа описанным способом невозможным.
Перестановка может выполняться отдельными битами или группами бит как байты, что программно куда удобнее, хотя и не перемешивает биты полностью. Перестановку можно было бы произвести и побитно, но это был бы очень дорогой процесс. Временная сложность перестановки связана с квадратом числа переставляемых элементов, поэтому перестановка бит была бы в 64 раза дороже перестановки байт. Вычислительных способов перестановок существует множество, на любой вкус. Например, в программах широко применяется перестановка по номерам N от 0 до L-1 на основе рекуррентного выражения:
N(i+1)=(K-Ni+M) MOD L
при выполнении следующих 4 условий:
1) К и М берутся из интервала [1, L-1],
2) М взаимно просто с L,
3) К- 1 делится на любой простой делитель L,
4) К-1 делится на 4, если L делится на 4.
Для хорошего запутывания в этом случае приходится делать перестановку несколько раз, меняя случайным образом К и М. Часть криптографов рекомендует для перестановки использовать такие же последовательности, как и у генераторов ключей, описанных ниже, хотя с этими генераторами существует проблема в том, что они переставляют 2**n-1 элементов, а на ЭВМ приходится иметь дело с группами длиной 2**n.
Интересна схема перестановки, напоминающая тасовку колоды карт. Так, если S=A+B+C представляет собой исходный блок текста, переставляемый побайтно, то результатом такой перестановки будет S'=C+B+A, где разбиение на фрагменты А, В и С делается случайным образом. После нескольких тасовок исходный текст оказывается основательно перепутанным. Эта тасовка в состоянии после многократного повторения осуществить любую перестановку. Однако число тасовок при этом должно быть очень велико, и для быстрого получения качественной перестановки лучше употреблять перестановку пар:
FOR i = 0 ТО N
SWAP arr(i), arr(N*RND)
NEXT
Перестановка тасовкой зачастую очень удобна, так как одиночный ее шаг практически не оставляет ни одного символа на своем месте. Прием перестановки тасовкой демонстрирует следующая программа:
' программа шифрования перестановкой
DEFINT I-N: DEFSTR S
RANDOMIZE 1379: CLS
'задание текста и перестановки
s = "Вверху синева и внизу откос"
l = LEN(s$): PRINT s
s$ = ""
FOR i=1 TO 2*l: s$=s$+CHR$(l*RND):NEXT
' шифровка
FOR i = 2 TO LEN(s$) STEP 2
n = ASC(MID$(s$, i-1, 1))
m = ASC(MID$(s$, i, 1))
IF n > m THEN SWAP n, m
s=RIGHT$ (s,l-m)+MID$ (s,n+1,m-n)+LEFT$ (s,n)
NEXT
PRINT s
' расшифровка
FOR i = LEN(s$) TO 1 STEP -2
n = ASC(MID$(s$, 1-1, 1))
m = ASC(MID$(s$, i, 1))
IF n > m THEN SWAP n, m
s=RIGHT$ (s,n) +MID$ (s, l-m+1,m-n) +LEFT$ (s, l- m)
NEXT
PRINT s
END
После ее выполнения на экране дисплея появляются три строки: верхняя с исходным текстом, средняя - шифрованная перестановкой, а нижняя - результат расшифровки. Например:
Вверху синева и внизу откос
рву еиаонуа етв с иинВковсх
Вверху синева и внизу откос
Шифр замены, осложненный перестановкой, представлял собой раннее поколение машинных криптографических преобразований. Он окончательно испортил надежду на вскрытие шифра хитроумными методами отгадывания текста сообщения, оставив взломщикам лишь возможность прямого подбора ключа. Вскрытие случайной перестановки без знания ключа неоднозначно, что не позволяет сколько-нибудь уверенно расшифровать сообщение. Однако по сохранившейся статистике использованных в сообщении символов можно делать более или, скорее, менее уверенные прогнозы о его общем содержании.
