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

From CryptoWiki
Jump to: navigation, search

Существует ли нераскрываемый шифр? Каким образом он должен быть построен? И какие условия необходимо обеспечить? Все эти вопросы привели к понятию совершенных или теоретически стойких криптосистем.

Вопрос о теоретической стойкости шифров впервые был исследован К. Шенноном в его фундаментальной публикации 1949 г., в которой, используя вероятностную модель шифра, он впервые сформулировал понятие совершенно стойкого шифра и показал, что он существует, на примере шифра Вернама, называемого также одноразовым блокнотом. Данный шифр предложил еще в 1917 г. американский инженер из компании AT&T Джилберт Вернам для шифрования телеграфных сообщений. Алгоритм шифрования Вернама заключался в том, что представленная в двоичном коде последовательность открытого текста побитово складывалась с ключом - случайной двоичной последовательностью. Сложение битов открытого текста и ключа осуществлялось по правилам:

0+0=0; 0+1=1; 1+0=1; 1+1=0.

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

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

Совершенно стойкий шифр (по Шеннону)– это шифр, у которого открытый и шифрованный тексты статистически независимы, т.е. для любого открытого текста a и любого шифртекста y

13031.png (1)

при условии, что 13032.png. Иначе говоря, знание шифрованного текста не дает никакой информации об открытом тексте, что означает, что для совершенных шифров апостериорные вероятности открытых текстов (вычисленные после получения шифртекста) совпадают с их априорными вероятностями.

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

Так как при всех открытых текстах a и шифртекстах y, при которых 130325.png, 13032.png, справедливо равенство

130326.png,

то при указанных текстах a и y равенство(1), определяющее совершенно стойкий шифр, эквивалентно равенству

130327.png. (2)

Шеннон доказал, что совершенно стойкие шифры существуют. В качестве примера рассмотрим так называемый шифр Вернама по модулю m, в котором знаки открытого текста, шифрованного текста и ключа принимают значения из кольца вычетов 130328.png, а длина ключа и длина криптограммы совпадают с длинной n открытого текста. Операция шифрования n-граммы открытого текста 130329.png с помощью n-граммы ключа 130330.png, в результате которой получается n-грамма шифрованного текста 130331.png, определяется уравнением:

130332.png (3)

Теорема(о совершенной стойкости шифра Вернама). Шифр Вернама по модулю m является совершенно стойким шифром при случайном равновероятном выборе ключа из множества 130333.png всех n-грамм в алфавите 130328.png.


Важные свойства шифра Вернама по модулю m:

1. Равенство (5) означает, что при известном открытом тексте все криптограммы длины n равновероятны.

2. Из равенства (2) следует, что и при неизвестном открытом тексте все криптограммы длины n равновероятны.


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

Тем не менее, совершенно стойкие шифры все же нашли практическое применение для защиты особо важных линий связи с относительно небольшим объемом передаваемой информации. Немцы еще в начале 1920-х гг. снабдили свои дипломатические представительства совершенно стойкими шифрами, а англичане и американцы перешли к использованию шифров типа Вернама во время второй мировой войны. Шифр Вернама по модулю 2 использовался на правительственной "горячей линии" между Вашингтоном и Москвой, где ключевые материалы представляли собой бумажные ленты (производившиеся в двух экземплярах), на которые знаки ключевой последовательности наносились с помощью перфорации.