Клод Шеннон - Теория связи в секретных системах, страница 4

Он имеет уравнениеei = mi + ki + li + ... + si (mod 26),где ki,li,...,si вообще говоря, имеют различные периоды. Период их суммы ki + li + ... + si,как и в составной транспозиции, будет наименьшим общим кратным отдельных периодов.Если используется шифр Виженера с неограниченным неповторяющимся ключом,то мы имеем шифр Вернама, в которомei = mi + ki (mod 26),и ki выбираются случайно и независимо среди чисел 0, 1, ... , 25. Если ключом служиттекст, имеющий смысл, то имеем шифр «бегущего ключа».Диграммная, триграммная и п-граммная подстановки.Вместо подстановки одной буквы можно использовать подстановку диграмм,триграмм и т.д.

Для диграммной подстановки в общем виде требуется ключ, состоящий изперестановок 262 диграмм. Он может быть представлен с помощью таблицы, в которой рядсоответствует первой букве диграммы, а столбец – второй букве, причем клетки таблицызаполнены заменяющими символами (обычно также диграммами).Шифр Виженера с перемешанным один раз алфавитом.Такой шифр представляет собой простую подстановку с последующим применениемшифра Виженераei = f (mi) + ki,mi = f –1(ei – ki).«Обратным» к такому шифру является шифр Виженера с последующей простойподстановкойei = g (mi + ki),mi = g–1(ei) – ki.Матричная система.Имеется один метод подстановки n-грамм, который заключается в применении кпоследовательным n-граммам некоторой матрицы, имеющей обратную.

Предполагается,что буквы занумерованы от 0 до 25 и рассматриваются как элементы некоторогоалгебраического кольца. Если к n-грамме сообщения применить матрицу aij то получитсяn-грамма криптограммыnei = å aij m j , i = 1,...,n.j =1Матрица aij является ключом, и расшифровка выполняется с помощью обратнойматрицы. Обратная матрица будет существовать тогда и только тогда, когда определитель|aij| имеет обратный элемент в нашем кольце.Шифр Плэйфер.Этот шифр является частным видом диграммной подстановки, которая производитсяс помощью перемешанного алфавита из 25 букв, записанных в виде квадрата 5´5.

(Буква Jчасто опускается при криптографической работе, так как она редко встречается, и в техслучаях, когда она встречается, ее можно заменить буквой I). Предположим, что ключевойквадрат записывается следующим образом:11LARKXZGDYBQNMHTCOIVEPUFSW.В этом случае диграмма AC, например, заменяется на пару букв, расположенных впротивоположных углах прямоугольника, определяемого буквами A и C, т.е.

на LO,причем L взята первой, так как она выше А. Если буквы диграммы расположены на однойгоризонтали, то используются стоящие справа от них буквы. Таким образом, RI заменяетсяна DF, RF заменяется на DR. Если буквы расположены на одной вертикали, тоиспользуются буквы, стоящие под ними. Таким образом, PS заменяется на UW. Если обебуквы диграммы совпадают, то можно использовать для их разделения нуль или же одну избукв опустить и т.п.Перемешивание алфавита с помощью многократной подстановки.В этом шифре используются последовательно d простых подстановок.

Так, еслиd = 4, тоm1m2m3m4m5m6...заменяется наf (m1) f (m2) f (m3) f (m4)f (m5)f (m6)...и т.д.Шифр с автоключом.Шифр типа Виженера, в котором или само сообщение или результирующаякриптограмма используются в качестве «ключа», называется шифром с автоключом.Шифрование начинается с помощью «первичного ключа» (который является настоящимключом в нашем смысле) и продолжается с помощью сообщения или криптограммы,смещенной на длину первичного ключа, как в указанном ниже примере, где первичнымключом является набор букв COMET.

В качестве «ключа» используется сообщение:Сообщение S E N D SКлюч C OE TMКриптограмма U SZU PS EP L IN D SE SU PTC O AYH L......H ...MЕсли в качестве «ключа» использовать криптограмму, то получится3Сообщение S E N D SКлюч C OE TMКриптограмма U SZH LU PU SPZL IH LO H O STE S ...O H ...TS...Дробные шифры.В этих шифрах каждая буква сначала зашифровывается в две (или более) буквы илив два (или более) числа, затем полученные символы каким-либо способом перемешиваются3Эта система является тривиальной с точки зрения секретности, так как за исключением первых d букв, враспоряжении противника имеется весь «ключ».12(например, с помощью транспозиции), после чего их можно снова перевести впервоначальный алфавит.

Таким образом, используя в качестве ключа перемешанный 25буквенный алфавит, можно перевести буквы в двузначные пятеричные числа с помощьютаблицы:012340LARKX1ZGDYB2QNMHT3COIVE4PUFSWНапример, букве B соответствует число 415. После того, как полученный рядчисел подвергнут некоторой перестановке, его можно снова разбить на пары чисел и перейтик буквам.Коды.В кодах слова (или иногда слоги) заменяются группами букв. Иногда затемприменяется шифр того или иного вида.5. Оценка секретных систем.Имеется несколько различных критериев, которые можно было бы использовать дляоценки качества предлагаемой секретной системы.

Рассмотрим наиболее важные из этихкритериев.Количество секретности.Некоторые секретные системы являются совершенными в том смысле, чтоположение противника не облегчается в результате перехвата любого количествасообщений. Другие системы, хотя и дают противнику некоторую информацию приперехвате очередной криптограммы, но не допускают единственного «решения». Системы,допускающие единственное решение, очень разнообразны как по затрате времени и сил,необходимых для получения этого решения, так и по количеству материала, которыйнеобходимо перехватить для получения единственного решения.Объем ключа.Ключ должен быть передан из передающего пункта в приемный пункт такимспособом, чтобы его нельзя было перехватить.

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

Этот нежелательный эффект можно наблюдать в системах, вкоторых делается попытка потопить статистику сообщения в массе добавляемых нулевыхсимволов, или где используются многократные замены. Он имеет место также во многихсистемах типа «маскировки» (которые не являются обычными секретными системами всмысле нашего определения).6. Алгебра секретных систем.Если имеются две секретные системы Т и R, их часто можно комбинироватьразличными способами для получения новой секретной системы S. Если T и R имеютодну и ту же область (пространство сообщений), то можно образовать своего рода«взвешенную сумму»S = рТ + qR,где p + q = 1.

Эта операция состоит, во-первых, из предварительного выбора систем T илиR с вероятностями p и q. Этот выбор является частью ключа S. После того как этотвыбор сделан, системы T или R применяются в соответствии с их определениями. Полныйключ S должен указывать, какая из систем T или R выбрана и с каким ключомиспользуется выбранная система.Если Т состоит из отображений Т1,...,Тm с вероятностями p1,...,pm, a R – из R1,...,Rk свероятностями q1,...,qk, то система S = рТ + qR состоит из отображений Т1,...,Тm,R1,...,Rk свероятностями pp1,...,ppm,qq1,...,qqk, соответственно.

Обобщая далее, можно образоватьсумму нескольких системS = p1Т + p2R + ... + pmU,S p = 1.iЗаметим, что любая система T может быть записана как сумма фиксированных операцийT = p1Т1 + p2T2 + ... + pmTm,где Ti – определенная операция шифрования в системе T, соответствующая выбору ключаi, причем вероятность такого выбора равна pi.Второй способ комбинирования двух секретных систем заключается в образовании«произведения», как показано схематически на рис.

3. Предположим, что T и R – такие двесистемы, что область определения (пространство языка) системы R может бытьTRK1K2R-1Рис 3. Произведение двух систем S = RT.T-114отождествлена с областью значения (пространством криптограмм) системы T. Тогда можноприменить сначала систему T к нашему языку, а затем систему R к результату этойоперации, что дает результирующую операцию S, которую запишем в виде произведенияS = RT.Ключ системы S состоит как из ключа системы T, так и из ключа системы R,причем предполагается, что эти ключи выбираются соответственно их первоначальнымвероятностям и независимо.

Таким образом, если m ключей системы T выбирается свероятностямиp1,p2,...,pm,а n ключей системы R имеют вероятностиp'1,p'2,...,p'n,то система S имеет самое большее mn ключей с вероятностями pi p'j. Во многих случаяхнекоторые из отображений RiTj будут одинаковыми и могут быть сгруппированы вместе, аих вероятности при этом сложатся.Произведение шифров используется часто; например, после подстановки применяютперестановку или после перестановки – код Виженера; или же применяют код к тексту изашифровывают результат с помощью подстановки, перестановки, дробным шифром и т.д.Можно заметить, что такое умножение, вообще говоря, некоммутативно (т.е.