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

PM(E) не должно зависеть от M.Другими словами, полная вероятность всех ключей, переводящих сообщение Mi вданную криптограмму E, равна полной вероятности всех ключей, переводящих сообщениеMj в ту же самую криптограмму E для всех Mi, Mj и E.Далее, должно существовать по крайней мере столько же криптограмм E, сколько исообщений M, так как для фиксированного i отображение Ti дает взаимно-однозначноесоответствие между всеми M и некоторыми из E. Для совершенно секретных систем длякаждого из этих E и любого M PM(E) = P(E) ¹ 0. Следовательно, найдется по крайнеймере один ключ, отображающий данное M в любое из E.

Но все ключи, отображающиефиксированное M в различные E, должны быть различными, и поэтому число различныхключей не меньше числа сообщений M. Как показывает следующий пример, можно получитьсовершенную секретность, когда число сообщений точно равно числу ключей. Пусть Miзанумерованы числами от 1 до n, так же как и Ei, и пусть используются n ключей. ТогдаTiMj = Es,где s = i + j (mod n). В этом случае оказывается справедливым равенство PE(M) = 1/n = P(E)и система является совершенно секретной. Один пример такой системы показан на рис. 5,гдеs = i + j – 1 (mod 5).231M123455M24M3M4M531234 512E1E2E33 45122 3451E4E5Рис 5. Совершенная система.Совершенно секретные системы, в которых число криптограмм равно числусообщений, а также числу ключей, характеризуются следующими двумя свойствами:1) каждое M связывается с каждым E только одной линией; 2) все ключи равновероятны.Таким образом, матричное представление такой системы является «латинским квадратом».В «Математической теории связи» показано, что количественно информациюудобно измерять с помощью энтропии.

Если имеется некоторая совокупность возможностейс вероятностями p1,…,pn, то энтропия дается выражениемH = - å pi log pi .Секретная система включает в себя два статистических выбора: выбор сообщения ивыбор ключа. Можно измерять количество информации, создаваемой при выборесообщения, через H(M)H ( M ) = -å P ( M ) log P ( M ) ,где суммирование выполняется по всем возможным сообщениям. Аналогично,неопределенность, связанная с выбором ключа, дается выражениемH ( K ) = - å P ( K ) log P ( K ) .В совершенно секретных системах описанного выше типа количество информации всообщении равно самое большее log n (эта величина достигается для равновероятныхсообщений). Эта информация может быть скрыта полностью лишь тогда, когданеопределенность ключа не меньше log n. Это является первым примером общегопринципа, который будет часто встречаться ниже: существует предел, которого нельзяпревзойти при заданной неопределенности ключа – количество неопределенности, котороеможет быть введено в решение, не может быть больше, чем неопределенность ключа.Положение несколько усложняется, если число сообщений бесконечно.Предположим, например, что сообщения порождаются соответствующим марковскимпроцессом в виде бесконечной последовательности букв.

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

Пусть логарифм числа букв в алфавитесообщений будет RM, а такой же логарифм для ключа – RK. Тогда из рассуждений дляконечного случая, очевидно, следует, что для совершенной секретности требуется, чтобывыполнялось неравенствоRMLM £ RKLK.Такой вид совершенной секретности реализован в системе Вернама.24Эти выводы делаются в предположении, что априорные вероятности сообщенийнеизвестны или произвольны. В этом случае ключ, требуемый для того, чтобы имела местосовершенная секретность, зависит от полного числа возможных сообщений.Можно было бы ожидать, что если в пространстве сообщений имеютсяфиксированные известные статистические связи, так что имеется определенная скоростьсоздания сообщений R в смысле, принятом в «Математической теории связи», тонеобходимый объем ключа можно было бы снизить в среднем в R/RM раз, и этодействительно верно. В самом деле, сообщение можно пропустить через преобразователь,который устраняет избыточность и уменьшает среднюю длину сообщения как раз во столькораз.

Затем к результату можно применить шифр Вернама. Очевидно, что объем ключа,используемого на букву сообщения, статистически уменьшается на множитель R/RM, и вэтом случае источник ключа и источник сообщений в точности согласован – один бит ключаполностью скрывает один бит информации сообщения. С помощью методов,использованных в «Математической теории связи», легко также показать, что это лучшее,чего можно достигнуть.Совершенно секретные системы могут применяться и на практике, их можноиспользовать или в том случае, когда полной секретности придается чрезвычайно большоезначение, например, для кодирования документов высших военных инстанций управления,или же в случаях, где число возможных сообщений мало.

Так, беря крайний пример, когдаимеются в виду только два сообщения – «да» или «нет», – можно, конечно, использоватьсовершенно секретную систему со следующей таблицей отображений:MданетKA01B10Недостатком совершенно секретных систем для случая корреспонденции большогообъема является, конечно, то, что требуется посылать эквивалентный объем ключа.

Вследующих разделах будет рассмотрен вопрос о том, чего можно достигнуть при помощименьших объемов ключа, в частности, с помощью конечного ключа.11.Ненадежность.Предположим теперь, что для английского текста используется шифр простойподстановки и что перехвачено определенное число, скажем N, букв зашифрованноготекста. Если N достаточно велико, скажем более 50, то почти всегда существуетединственное решение шифра, т.е.

единственная последовательность, имеющая смысл наанглийском языке, в которую переводится перехваченный материал с помощью простойподстановки. Для меньших N шансы на неединственность решения увеличиваются; дляN = 15, вообще говоря, будет существовать некоторое число подходящих отрывков осмысленного английского текста, в то время как для N = 8 окажется подходящей значительнаячасть (порядка 1/8) всех возможных значащих английских последовательностей такойдлины, так как из восьми букв редко повторится больше чем одна. При N = 1, очевидно,возможна любая буква и апостериорная вероятность любой буквы будет равна ее априорнойвероятности.

Для одной буквы система является совершенно секретной.Это происходит, вообще говоря, со всеми разрешимыми шифрами. Прежде чемперехвачена криптограмма, можно представить себе априорные вероятности, связанные сразличными возможными сообщениями, а также с различными ключами. После того какматериал перехвачен, шифровальщик противника вычисляет их апостериорные вероятности.При увеличении числа N вероятности некоторых сообщений возрастают, но длябольшинства сообщений они убывают до тех пор, пока не останется только одно сообщение,имеющее вероятность, близкую к единице, в то время как полная вероятность всех другихблизка к нулю.25Для самых простых систем эти вычисления можно эффективно выполнить.Таблица 1 дает апостериорные вероятности для шифра Цезаря, примененного к английскомутексту, причем ключ выбирался случайно из 26 возможных ключей. Для того, чтобы можнобыло использовать обычные таблицы частот букв, диграмм и триграмм, текст был начат вслучайном месте (на страницу открытой наугад книги был случайно опущен карандаш).Сообщение, выбранное таким способом, начинается с «creases to» (карандаш опущен натретью букву слова increases).

Если известно, что сообщение начинается не с середины, а сначала некоторого предложения, то нужно пользоваться иной таблицей, соответствующейчастотам букв, диграмм и триграмм, стоящих в начале предложения.Таблица 1. Апостериорные вероятности для криптограммы типа. Цезаря.РасшифровкиN=1CREAS0,028DSFBT0,038ETGCU0,131FUNDV0,029GVIEW0,020HWJFX0,053IXKGY0,063JYLHZ0,001KZMIA0,004LANJB0,034МВОКС0,025NCPLD0,071ODQME0,080PERNF0,020QFSOG0,001RGTPH0,068SHUQI0,061TIVRJ0,105UJWSK0,025VKXTL0,009WLYUM0,015XMZVN0,002YNAWO0,020ZOBXP0,001APCYQ0,082BQDZR0,014H (десятичных единиц) 1,2425N=20,03770,03140,08810,0189N=30,1111N=40,3673N=510,00630,01260,13210,25000,02220,11950,03770,08180,43890,01260,08810,28300,00560,16670,63270,00560,05030,96860,60340,2850Шифр Цезаря со случайным ключом является чистым, и выбор частного ключа невлияет на апостериорные вероятности.

Чтобы определить эти вероятности, надо простовыписать возможные расшифровки с помощью всех ключей и вычислить их априорныевероятности. Апостериорные вероятности получатся из этих последних в результате деленияих на их сумму. Эти возможные расшифровки, образующие остаточный класс этогосообщения, найдены с помощью стандартного процесса последовательного «пробеганияалфавита», в таблице 1 они даны слева. Для одной перехваченной буквы апостериорныевероятности равны априорным вероятностям для всех букв6 (они приведены в таблице подрубрикой N = 1).6Вероятности в приводимой таблице были взяты из таблиц частот, данных в книге Pratt F., Secret and Urgent,Blue Ribbon Books, New York, 1939.

Хотя эти таблицы и не являются полными, но для настоящих целей ихдостаточно.26Для двух перехваченных букв эти вероятности равны априорным вероятностямдиграмм, пронормированным на их сумму (они приведены в столбце N = 2). Триграммныечастоты получены аналогично и приведены в столбце N = 3. Для четырех- и пятибуквенныхпоследовательностей вероятности находились из триграммных частот с помощьюумножения, так как с некоторым приближениемp(ijkl) = p(ijk)pjk(l).Заметим, что для трех букв число возможных сообщений снижается до четырех сообщенийдостаточно высокой вероятности, причем вероятности всех других сообщений малы посравнению с вероятностями этих четырех сообщений. Для четырех букв имеются двавозможных сообщения и для пяти – только одно, а именно правильная дешифровка.В принципе это может быть проведено для любой системы, однако в том случае,когда объем ключа не очень мал, число возможных сообщений настолько велико, чтовычисления становятся практически невыполнимыми.Получаемое таким образом множество апостериорных вероятностей описывает, какпостепенно, по мере получения зашифрованного материала, становятся более точнымисведения шифровальщика противника относительно сообщения и ключа.Это описание, однако, является слишком исчерпывающим и слишком сложным длянаших целей.