Комбинированное использование шифра перестановки и замены

Из-за обратимости шифра замены, целесообразно для защиты информации применять комбинацию алгоритмов замены и перестановки. Перестановку можно рассматривать как умножение вектора сообщения на матрицу перестановки бит P с элементами 0 и 1 и размером в длину сообщения в битах. При этом возможны два случая.

1. Перестановка может делаться до наложения на сообщение случайной последовательности g:

S’=Pt + g (1.8)

В случае если текст в сообщении отсутствует, то в канал связи попадет чистый ключ:

t = 0; S' = P 0 + g = g (1.9)

2. Перестановка может делаться после наложения на сообщение случайной последовательности:

S' = P (t + g) (1.10)

В случае если текст отсутствует, в канал связи поступает ключ, шифрованный перестановкой:

t = 0; S' = P (0 + g) = P g (1.11)

Обычно предпочтение отдается второй схеме.

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

Существует множество вычислительных способов перестановок. Например, широко применяется перестановка по номерам N от 0 до L-1 на основе рекуррентного соотношения:

Ni+1 = (K Ni + M) mod L (1.12)

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

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

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

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

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

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

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

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

Шифровальная машина «Энигма»

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

Первоначально «Энигма» состояла из 4 барабанов. С каждой стороны барабана находилось по 25 контактов, соответствовавших буквам алфавита и случайным образом соединенных проводами. Электрический импульс, обозначавший букву алфавита, таким образом, проходил через все четыре барабана, что приводило к 8-ми кратной замене. Кроме того, после каждого символа, все барабаны поворачивались что обеспечивало длину ключа гораздо большую длины сообщения. Ключ вводили, устанавливая барабаны в определенном порядке. И если в годы Первой мировой войны, «Энигма» так и не нашла широкого применения, то во Вторую мировую она стала значительным препятствием для союзников, с трудом вскрывавших ее шифры.

Для того, чтобы эффективно взламывать шифры «Энигмы», необходимо было знать распайку проводов внутри каждого барабана (вскрыть шифр «Энигмы» теоретически возможно и без этого, но тогда замен становится не 4, а 8, и шифр уже нельзя вскрыть вручную в течении достаточно короткого времени), поэтому, необходимо было достать образец самой машины. Барабаны в каждой машине были стандартными, для того, чтобы обеспечить дешифровку сообщения, поэтому с началом войны британская разведка развернула настоящую охоту за образцами «Энигмы», не прекращавшуюся до конца войны (так как немцы периодически меняли распайку проводов в барабанах). Первый образец этой машины, вместе с чертежами был похищен польской разведкой еще в 1939 году прямо с завода, и вскоре передан британским спецслужбам. Вторую сняли с борта сбитого над Норвегией немецкого бомбардировщика в 1940. В дальнейшем британские спецслужбы начали настоящую охоту за немецкими подводными лодками с единственной целью снять с них образец этой шифровальной машины.

Но даже имея образец этой машины необходимо было взломать шифр 4-хкратной замены, определявшийся положением барабанов. Это представляло почти непреодолимую трудность до тех пор, пока в 1942 году в Англии не начала функционировать первая ЭВМ «Колосс», специально созданная для взлома немецких шифров и справлявшаяся с «Энигмой» за полтора часа, хотя это относилось лишь к армейским «полевым» шифрам, в то время как большинство дипломатических и наиболее важные военные сообщения шифровались с помощью более сложных моделей «Энигм», имевших по 6 барабанов, и ни одна из них не попала в руки союзников. Следует отметить и тот факт, что сами немцы не считали «Энигму» неуязвимой и многократно ведущие немецкие криптоаналитики, не зная заранее даже расположения проводов в барабанах, вручную взламывали ее шифры.

Дата добавления: 2013-12-12