Шифры перестановки.docx

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

Шифр замены в чистом его виде никогда не применяется, а употребляется вместе с перестановками, например, бит внутри байта.

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

сообщения x на матрицу P перестановки бит с элементами 0, 1 и размером в длину сообщения в битах.

 

- Если перестановка делается  после гаммирования    ''

[ ](x

y) , то при

x = 0

имеем

 

'' [ ] y

и в канал попадает уже ключ, шифрованный перестановкой. Атака на ключ

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

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

Придумано много вычислительных способов перестановок.

Например, широко применяется перестановка программно по номерам N от 0 до L–1

рекуррентным выражением

+1 =

× N + M

mod L

При выполнении следующих 4 условий

1)      K и M берутся из интервала [1, L–1]

2)      M взаимно просто с L

3)      K–1 делится на любой простой делитель L

4)      K–1 делится на 4, если L делится на 4

В этом случае для хорошего запутывания приходится делать перестановку несколько раз меняя случайно K и M.

Быструю и качественную перестановку можно получить перестановкой пар по случайному ключу. Например, для блока из N бит заведем массив arr переменных целого типа (0, 1) и загрузим в него блок исходного двоичного текста. Программа перестановки на языке QBasic будет иметь вид:

RANDOMIZE 1379 FOR i = 1 TO N

SWAP arr(i), arr(N*RND) 'обменять переменные arr(i) « arr(j) NEXT i

Эта перестановка практически не оставляет ни одного символа на своем месте. Заметим, что эта же программа применима и для перестановки букв, закодированных байтами ASCII.

Можно производить перестановку по аналогии с тасованием колоды карт: тасовать биты или байты блока текста. Обозначим присоединение (конкатенацию) знаком «+». Пусть блок текста разбит на фрагменты Y=A+B+C и разбиение на фрагменты из бит или байт производится случайным образом. Тогда результат перестановки, например, будет Y'=C+B+A. Однако, чтобы текст основательно перепутать нужно очень многократно повторить тасование.

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

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