Клод Шеннон - Теория связи в секретных системах (1085222), страница 2
Текст из файла (страница 2)
Покажем, что «совершенная секретность»возможна, но требует в случае конечного числа сообщений того же самого числа возможныхключей. Если считать, что сообщение создается с данной «скоростью» R (понятие скоростибудет определено позже), то ключ должен создаваться с той же самой или с большейскоростью.Если используется секретная система с конечным ключом и перехвачены N буквкриптограммы, то для противника будет существовать определенное множество сообщений с4определенными вероятностями, которые могли бы создать эту криптограмму.
Сувеличением N это множество обычно сужается до тех пор, пока в конце концов неполучится единственного «решения» криптограммы: одно сообщение с вероятностью,близкой к единице, а все остальные с вероятностями, практически равными нулю. В работеопределяется величина H(N), названная ненадежностью. Эта величина измеряет (встатистическом смысле), насколько близка средняя криптограмма из N букв кединственному решению, т.е. насколько неточно известно противнику истинное сообщениепосле перехвата криптограммы из N букв. Далее выводятся различные свойстваненадежности, например: ненадежность ключа не возрастает с ростом N. Эта ненадежностьявляется теоретическим показателем секретности – теоретическим, поскольку она позволяетпротивнику дешифровать криптограмму лишь в том случае) если он обладаетнеограниченным запасом времени.В этой же части определяется функция H(N) для некоторых идеализированныхтипов шифров, называемых случайными шифрами.
С некоторыми видоизменениями этафункция может быть применена ко многим случаям, представляющим практическийинтерес. Это дает способ приближенного вычисления количества материала, которыйтребуется перехватить, чтобы получить решение секретной системы.Из подобного анализа следует, что для обычных языков и обычных типов шифров(но не кодов) это «расстояние единственности» равно приблизительно H(K)/D. Здесь H(K)– число, измеряющее «объем» пространства ключей.
Если все ключи априориравновероятны, то H(K) равно логарифму числа возможных ключей. Вводимое число D –это избыточность языка. Оно измеряет количество «статистических ограничений»,налагаемых языком. Для простой подстановки со случайным ключом наше H(K) равноlog1026! или приблизительно 20, а D (в десятичных единицах на букву) для английскогоязыка равно приблизительно 0.7. Таким образом, единственность решения достигаетсяприблизительно при 30 буквах.Для некоторых «языков» можно построить такие секретные системы с конечнымключом, в которых неопределенность не стремится к нулю при N ® ¥. В этом случаепротивник не получит единственного решения такого шифра, сколько бы материала он неперехватил, и у него будет оставаться много альтернатив с довольно большимивероятностями. Такие системы назовем идеальными системами.
В любом языке можноаппроксимировать такую ситуацию, т.е. отсрочить приближение H(N) к нулю до скольугодно больших N. Однако такие системы имеют много недостатков, таких как сложность ичувствительность к ошибкам при передаче криптограммы.Третья часть статьи посвящена «практической секретности».
Две системы содинаковым объемом ключа могут быть обе разрешимы единственным образом, когдаперехвачено N букв, но они могут значительно отличаться по количеству времени и усилий,затрачиваемых для получения решения. На основе анализа основных недостатков секретныхсистем предлагаются методы построения систем, для решения которых требуются большиезатраты времени и сил. Наконец, рассматривается проблема несовместимости различныхжелательных качеств секретных систем.Часть I.МАТЕМАТИЧЕСКАЯ СТРУКТУРА СЕКРЕТНЫХ СИСТЕМ.2.
Секретные системы.Чтобы приступить к математическому анализу криптографии, необходимо ввестиудовлетворительную идеализацию и определить математически приемлемым способом, что5будет пониматься под термином секретная система. Схематическая структура секретнойсистемы показана на рис.1.ШифровальщикпротивникаEСообщениеИсточниксообщенийMСообщениеШифровальщикTKШифровальщикКриптограммаMTK-1EКлючKКлючKИсточникключейРис.
1. Схема общей секретной системы.На передающем конце имеются два источника информации – источник сообщений иисточник ключей. Источник ключей отбирает конкретный ключ среди всех возможныхключей данной системы. Этот ключ передается некоторым способом на приемный конец,причем предполагается, что его нельзя перехватить (например, ключ передаетсяпосыльным). Источник сообщений формирует некоторое сообщение (незашифрованное),которое затем зашифровывается, и готовая криптограмма передается на приемный конец,причем криптограмма может быть перехвачена (например, пересылается по радио). Наприемном конце шифровальщик с помощью ключа по криптограмме восстанавливаетисходное сообщение.Очевидно, шифровальщик на передающем конце выполняет некоторуюфункциональную операцию. Если M – сообщение, K – ключ и E – зашифрованноесообщение (криптограмма), то имеемE = f (M,K),т.е.
E является функцией от M и K. Удобнее, однако, понимать E не как функцию двухпеременных, а как (однопараметрическое) семейство операций или отображений, изаписывать его в виде:E = Ti M.Отображение Ti примененное к сообщению M, дает криптограмму E. Индекс iсоответствует конкретному используемому ключу.Вообще мы будем предполагать, что имеется лишь конечное число возможныхключей, каждому из которых соответствует вероятность pi. Таким образом, источникключей является статистическим процессом, или устройством, которое выбирает одно измножества отображений T1,...,Tm с вероятностями p1,...,pm соответственно. Будем такжепредполагать, что число возможных сообщений конечно и эти сообщения M1,...,Mn имеютаприорные вероятности q1,...,qn. Например, возможными сообщениями могли бы бытьвсевозможные последовательности английских букв, включающих по N букв каждая, асоответствующими вероятностями тогда были бы относительные частоты появления такихпоследовательностей в нормативном английском тексте.6Должна иметься возможность восстанавливать M на приемном конце, когдаизвестны E и K.
Поэтому отображение Ti, из нашего семейства должно иметьединственное обратное отображение Ti–1, так что TiTi–1 = I, где I – тождественноеотображение. Таким образом:M = Ti–1E.Во всяком случае, это обратное отображение Ti–1 должно существовать и бытьединственным для каждого E, которое может быть получено из M с помощью ключа i.Приходим, таким образом, к следующему определению: секретная система есть семействооднозначно обратимых отображений Ti множества возможных сообщений во множествокриптограмм, при этом отображение Ti имеет вероятность pi.
Обратно, любое множествообъектов такого типа будет называться «секретной системой». Множество возможныхсообщений для удобства будет называться «пространством сообщений», а множествовозможных криптограмм – «пространством криптограмм».Две секретные системы совпадают, если они образованы одним и тем жемножеством отображений Ti и одинаковыми пространствами сообщений и криптограмм,причем вероятности ключей в этих системах также совпадают.Секретную систему можно представлять себе как некоторую машину с одним илиболее переключающими устройствами. Последовательность букв (сообщение) поступает навход машины, а на выходе ее получается другая последовательность.
Конкретное положениепереключающих устройств соответствует конкретному используемому ключу. Для выбораключа из множества возможных ключей должны быть заданы некоторые статистическиеметоды.Для того чтобы нашу проблему можно было рассмотреть математически,предположим, что противнику известна используемая система. Иными словами, он знаетсемейство отображений Ti и вероятности выбора различных ключей.
Можно было бы, вопервых, возразить, что такое предположение нереалистично, так как шифровальщикпротивника часто не знает, какая система использовалась или чему равны рассматриваемыевероятности. На это возражение имеется два ответа.1. Наложенное ограничение слабее, чем кажется с первого взгляда, из-за широтынашего определения секретной системы. Предположим, что шифровальщик перехватываетсообщение и не знает, использовалась ли здесь подстановка или транспозиция, или шифртипа Виженера. Он может считать, что сообщение зашифровано с помощью системы, вкоторой часть ключа является указанием того, какой из трех типов имеющихся ключей былиспользован, а следующая часть – конкретный ключ этого типа. Указанным трем различнымвозможностям шифровальщик приписывает вероятности, учитывая при этом все имеющиесяу него сведения об априорных вероятностях использования шифровальщиком противникасоответствующих типов шифров.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
