По-видимому, одна из первых открытых работ по криптографии появилась в 1949 году и принадлежала Шеннону (Claude Shannon, см. [17]). В ней рассматривается классическая схема криптосистемы с секретным ключом, которая была представлена на рис. 1.1.
В этой схеме имеется защищенный канал, предназначенный для передачи секретных ключей. Однако отметим, что в настоящее время можно рассмотреть в качестве защищенного канала схему вычисления секретного ключа на основе методов криптографии с открытым ключом, например, схему Диффи-Хеллмана. В дальнейшем мы будем рассматривать только классическую схему с секретным ключом, но многие результаты переносятся на случай создания секретного канала средствами криптографии с открытым ключом.
Все методы шифрования можно грубо разделить на два больших класса:
1) схемы, принципиально не вскрываемые, что доказывается строго;
2) схемы, стойкость которых основана на том, что дешифрование без ключа, вообще говоря, возможно, но для этого требуется перебор очень большого количества вариантов.
В этой главе мы будем заниматься системами первого типа, стойкость которых теоретически доказана. Системы второго типа будут рассмотрены в следующей главе.
Пусть M = {M1, M2, M3,..., Mm} — множество всех возможных сообщений например, множество всех текстов длины не более, чем 1000 букв), K = {K1, K2, K3,..., Kn} — множество всех возможных ключей, E = {E1, E2,..., Ek} — множество всех криптограмм (т.е. зашифрованных сообщений). Зашифрованные сообщения зависят от исходного сообщения и ключа, т.е. .
Мы будем считать, что на всем множестве сообщений M задано распределение вероятаостей P, т.е. определены вероятности P(Mi), i = 1,2,..., m. Это априорное распределение вероятностей, которое известно и противнику. Запись вида P(A\B) будет, как обычно, обозначать условную вероятность события A при условии наступления события B.
Определение 3.1. Криптосистема называется совершенно секретной, если выполняется равенство
(3.1)
при всех Mi, Kl и .
Поясним это определение. Пусть Ева перехватила криптограмму Ej. Если (3.1) выполняется для всех возможных сообщений, то это означает, что она не получила никакой информации о переданном сообщении, т.е. знание Ej совершенно бесполезно для нее. Рассмотрим схематичный пример. Пусть M — множество всех сообщений из шести букв на русском языке. Пусть априори известно, что для нeкоторой системы
Допустим, мы имеем нeсовeршeнную систему, и Ева после перехвата и вычислений получила следующие данные:
Это означаeт, что Ева практически расшифровала сообщение: она практически увeрeна, что передано слово «бутыль», так как вероятность, что передано другое сообщение меньше 0.0001.
Если же для рассмотренной системы при любой перехваченной криптограмме Ej мы получаем
и такие же равенства выполняются для всех остальных сообщений, то Ева вообще может нe обращать внимание на перехваченный шифротекст Ej, а, напримeр, отгадывать сообщение на основе исходных вероятаостей. Другими словами, (3.1) — действительно разумное определение совершенно секретной системы.
Исследуем свойства совершенно секретной системы.
Теорема 3.1. Если система является совершенно секретной (выполняется (3.1)), то справедливо равенство
(3.2)
при всех i и j . Верно и обратное утверждение: если (3.2) выполняется, то система совершенно секретна.
Д о к а з а т е л ь с т в о. По определению условной вероятности
при (см., например, [15]). Поэтому при
можно записать
Принимая во внимание (3.1), получаем
т.е.
Этот шифр был предложен в 1926 году американским инженером Вернамом (Gilbert Vernam) и использовался на практике, но доказательство его невскрываемости было получено значительно позже Шенноном [17]. Для шифра Вернама часто используется название «одноразовая лента» (one-time pad). Мы опишем этот шифр для случая двоичного алфавита, чтобы упростить обозначения.
Пусть множество сообщений M состоит из слов двоичного алфавита длины n, т.е. всего сообщений не более, чем 2n. В шифре Вернама множество ключей также состоит из слов той же длины n и каждый ключ используется с вероятностью 1 /2n. Другими словами, все ключи используются с одинаковой вероятностью.
Пусть необходимо зашифровать сообщение и пусть выбран ключ
. Тогда зашифрованное сообщению
получается по формуле:
(3.3)
где i = 1, 2,..., n и обозначает сложение по модулю 2. Другими словами, сообщение шифруется по схеме
Так как сложение и вычитание по модулю 2 совпадают, то легко видеть, что дешифрование осуществляется по формуле
(3.4)
П р и м е р 3.1. Пусть = 01001,
= 11010. Тогда получаем
= 10011. Сложив
с
, восстанавливаем
.
Теорема 3.2. Шифр Beрнама является совершенно секретной криптосистемой.
Д о к а з а т е л ь с т в о. Согласно теореме 3.1 достаточно доказать справедливость (3.2). Имеем
(в последнем равенстве мы использовали то, что, по предположению, все ключи равновероятны).
Найдем P(Ej). По формуле полной вероятности
Учитывая, что , получаем
Так как сумма вероятностей всех возможных сообщений равна 1, получаем
Таким образом, справедливо (3.2). Теорема доказана.
Известао, что шифр Вернама использовался при защите правительственной связи: например, на так называемой горячей линии «Москва - Вашингтон» [23], а также в других системах, где можно позволить дорогой способ доставки секретного ключа. Однако шифр Вернама можно использовать во многих других практически важных ситуациях. Например, на основе этого шифра легко организовать связь между банком и его филиалами (или связи между банком и клиентами), когда они находятся в одном городе, или защитить электронные письма, скажем, для студентов Алисы и Боба, расстающихся на каникулы (мы предлагаем читателю придумать схему и написать программу, считая, что общая длина писем, которыми они будут обмениваться во время каникул, не превосходит 1.44 Мбайт, т.е. объема стандартной дискеты).
Мы доказали, что шифр Вернама совершенен, однако при его использовании длина ключа равна длине сообщения. К. Шеннон [17] показал, что у любой совершенной системы длина ключа должна быть больше энтропии сообщения (с которой мы кратко познакомимся ниже), т.е. пропорциональна его длине. Во многих практически важных ситуациях приходится использовать короткие ключи (скажем, сотни или тысячи бит) для шифрования длинных сообщений (сотни килобайт и более). В этом случае можно построить только так называемые идеальные системы, впервые описанные Шенноном. Для построения идеальных систем и исследования их свойств Шеннон предложил использовать понятия теории информации. В этом разделе мы определим и кратко проиллюстрируем эти понятия. Достаточно полное и строгое их изложение может быть найдено, например, в [4].
Начнем с определения основного понятия — энтропии Шеннона. Пусть дана дискретная случайная величина , принимающая значения a1, a2, . . .ar с вероятностями P1, P2, . . ., Pr.
Определение 3.2. Энтроnия случайной величины определяется равенством
(3.5)
где 0 log 0 = 0.
Если используется двоичный логарифм, то энтропия измеряется в битах, что общепринято в криптографии, теории информации и в компьютерных науках. В случае натуральных логарифмов единица измерения — нат, в случае десятичных — дит.
При r = 2 можно (3.5) записать иначе, введя следующие обозначения: P1 = p, P2 = 1 — p. Тогда
(3.6)
График энтропии для этого случая приведен на рис. 3.1.
Рассмотрим простейшие свойства энтропии.
Рис. 3.1. График двоичной энтропии
Утверждение 3.3.
Д о к а з а т е л ь с т в о. Первое свойство довольно очевидно (см. (3.5)). Второе свойство докажем только для случая r = 2, так как общий случай аналогичен. Исследуем график энтропии. Нужно найти максимум функции (3.6). Для этого мы найдем первую и вторую производные H(p), считая, что логарифм натуральный.
Отсюда H'(p) = 0 при p = 1/2. Найдем вторую производную
Мы видим, что H''(p) < 0 при . Это означает, что функция H(p) достигает максимума в точке 1/2 и выпукла на отрезке (0; 1). Таким образом, график, изображенный на рис. 3.1, обоснован. Очевидно, при любом основании логарифма график будет аналогичный.
Для доказательства третьего свойства заметим, что наибольшее значение энтропии для r = 2 равно
т.е. составляет один бит в случае двоичного логарифма.
«Физический» смысл энтропии состоит в том, что энтропия — это количественная мера неопределенности. В качестве примера рассмотрим три случайные величины для r = 2. Иными словами, будем считать, что у нас есть три источника сообщений, которые порождают буквы a1, а2, т.е. имеются три случайные величины i, i = 1,2, 3, принимающие значения a1 или a2:
Интуитивно ясно, что неопределенность случайной величины 1 равна нулю. И действительно,
Посмотрим на 2 и
3. Интуитивно кажется, что неопределенность у
2 вьше неопределенности у
3. Вычислим энтропии:
(уже считали выше),
Мы видим, что энтропия действительно является разумной мерой неопределенности. главное, конечно, не примеры такого типа, а то, что эта величина играет ключевую роль во многих задачах теории передачи и хранения информации. В частности, энтропия характеризует максимальную степень сжатия данных. Точнее, если источник сообщений порождает текст достаточно большой длины n с определенной ниже предельной энтропией h на бит сообщения, то этот текст может быть «сжат» в среднем до величины сколь угодно близкой к nh. Например, если h =1/2, то текст сжимается вдвое и т.п. Подчеркнем, что речь идет о так называемом неискажающем сжатии, когда по «сжатому» сообщению можно восстановить исходное.
Рассмотрим теперь двумерную случайную величину, заданную рядом распределения
(3.7)
Пример 3.2. Из многолетнего опыта преподавания в некотором вузе известно, что оценки за первый и второй контрольный срок по математике (соответственно 1 и
2) подчиняются закону распределения, задаваемому табл. 3.1.
Таблица 3.1. Распределение оценок за контрольный срок
Введем следующие обозначения:
Напомним некоторые элементарные соотношения, известные из теории вероятностей (см. [15]):
(3.8)
(3.9)
(3.10)
((3.10) — уже встречавшаяся формула полной вероятности, в которой Hi — попарно несовместные события, сумма которых содержит событие A ).
В соответствии с (3.5) определим энтропию двумерной случайной величины
(3.11)
Aналогично для трехмерной случайной величины (1,
2,
3) и распределения вероятностей Pijk определим
(3.12)
Подобным же образом определяется энтропия для n-мерной случайной величины.
Представим теперь, что значение случайной величины 1 известно, а
2 — неизвестно. Тогда естественно определить условную энтропию
(3.13)
Это — средняя условная энтропия случайной величины 2 при условии, что значение
1 известно.
Утверждение 3.4 (свойство двумерной энтропии).
(3.14)
в частности, для независимыx случайных величин 1 и
2
(3.15)
Напомним, что 1,
2 независимы, если Pij = PiPj для всех i и j. Доказательство утверждения достаточно просто и может быть найдено в [4]. Мы ограничимся только его интерпретацией. Пусть в первом опыте порождается
2, во втором —
1. Тогда общая неопределенность экперимента должна быть равна неопределенности первого опыта, сложенной с условной неопределенностью второго опыта. В случае независимых
1 и
2 знание одной величины не несет никакой информации о другой, что соответствует (3.15).
Пусть дана n-мерная случайная величина (1,
2,... ,
n). Справедливо следующее соотношение [4]:
(3.16)
Для независимых случайных величин
(3.17)
(заметим, что (3.14), (3.15) — частный случай (3.16), (3.17)).
В общем случае
(3.18)
Рассмотрим последовательность случайных величин 1,
2,
3,. . . (
i принимают значения в A), которую можно рассматривать как случайный процесс с дискретным временем. Мы будем считать, что этот процесс стационарный, т.е., неформально, вероятностные характеристики для (
1. . .
n) те же, что и для (
+1. . .
+n) при всех положительных n и
(точное определение дано в [4]).
Пусть H(1,...,
n) — энтропия n-мерной случайной величины (
1...
n). Обозначим через
удельную энтропию n-го порядка и определим
Отметим следующие свойства:
(3.19)
(3.20)
(3.21)
Их доказательство может быть найдено в [4].
Для независимых 1,
2,...,
n справедливы равенства
(Процесс, порождающий независимые случайные величины называется процессом без памяти.)
Теорема 3.5. Для стационарного процесса существуют пределы , причем эти пределы равны.
Доказательство теоремы см. в [4].
Обозначим общее значение этих пределов через ,
(3.22)
Пусть дан алфавит A = (a1, a2,... ar). Мы знаем, что
для процесса без памяти, поэтому, принимая во внимание (3.21) и (3.22), получаем , причем максимум достигается для процессов без памяти, у которых все буквы порождаются с равными вероятностями 1/r. Естественно ввести величину
(3.23)
называемую избыточностью (на букву сообщения). Неформально, это как бы неиспользованная часть алфавита. Избыточность — количественная мера взаимной зависимости символов и их «неравновероятности». Отметим, что в примере из первой главы во втором случае, когда даже простой шифр Цезаря не вскрываем, избыточность шифруемого сообщения равна нулю, так как все десять символов независимы и равновероятны, т.е. и R = 0.
Рассмотрим криптосистему с секретаым ключом, схема которой показана на рис. 1.1. Пусть источник порождает сообщение
. напримeр, mi при каждом i — это буква из русского алфавита или знак пробела, а
— сообщение на русском языке. Алиса и Боб обладают секретным ключом k, известным только им, и пусть
— сообщение, зашифрованное при помощи этого ключа.
П р и м е р 3.3. Пусть источник порождает буквы из алфавита A = {a,b,c} с вероятаостями P(a) = 0.8, P(b) = 0.15, P(c) = 0.05, и пусть это источник без памяти. Пусть шифратор, применяя ключ k, заменяет буквы в исходном сообщении, используя какую-либо перестановку символов:
т.е. ключ принимает значения от 1 до 6 , и если , напримeр, k = 5 , то в исходном тексте осуществляется следующая замена символов: a c, b
a, c
b.
Пусть Ева перехватила зашифрованное сообщение
и хочет определить значение ключа. Оценим количественно вероятности использования всех возможных ключей, используя формулу Байеса
где E, K1, ..., Kt — некоторые события, причем Ki попарно нeсовместны и . В нашем случае событие E — это получение зашифрованного сообщения
, t = 6, а Ki означает, что выбран ключ k = i.
Мы предполагаем, что все ключи равновероятны, т.е.
Тогда
Отсюда легко находим
и получаем по формуле Байеса апостериорную вероятность того, что был использован ключ k = 1, при условии, что получено сообщение
Продолжая аналогично, находим, что наиболее вероятны ключи k = 5 и k = 6:
а вероятности всех остальных ключей меньше 0.01.
Мы видим, что, перехватив всего 5 букв, Ева может определить ключ почти однозначно. Таким образом, из этого примера и из примера с шифром Цезаря в первой главе мы заключаем, что, по-видимому, существует некоторая длина перехваченного сообщения, после которой ключ может быть найден с вероятностью, близкой к единице.
Утверждение 3.6 (о расстоянии единственности шифра (Шеннон [17])). Пусть рассматривается система с секретным ключом, и пусть H(K) — энтропия ключа. Пусть R — избыточность шифруемого сообщения, а n — длина сообщения, такая, что
(3.24)
т.е. при этой длине перехваченного сообщения ключ почти однозначно восстановлет. Тогда справедливо нeравeнство
(3.25)
Дадим несколько замечаний к этому утверждению.
1. Число n, удовлетворяющее неравенству (3.25), называется расстоянием единственности шифра. Это означает, что в среднем достаточно перехватить n букв зашифрованного сообщения для восстановления ключа.
2. Мы видим, что если избыточность сообщения R = 0, то ключ никогда не будет определен так как n = х .Т.е. шифр невозможно взломать (мы видели это в примере с номером замка из первой главы).
3. Уменьшение избыточности может быть достигнуто за счет сжатия данных. Дело в том, что при сжатии данных энтропия «сжатого» текста сохраняется, а длина уменьшается. Следовательно, энтропия на букву в сжатом тексте больше, чем в исходном, а избыточность меньше, см. (3.23). 3начит, после сжимающего кодирования расстояние единственности шифра увеличивается.
4. С практической точки зрения лучше использовать системы, в которых ключ меняется задолго до достижения расстояния единственности шифра.
Д о к а з а т е л ь с т в о. Мы дадим здесь только основную идею доказательства. Пусть противник, перехватив переданный шифротекст , однозначно восстановил ключ, а тем самым и исходное сообщение. 3начит, неопределенность противника уменьшилась на H(K) + H (m1,..., mn), так как он узнал и ключ, и исходное сообщение. При этом он получил n букв из r-буквенного алфавита {a1,... ,ar}. Мы знаем, что максимальное значение энтропии
, значит, неопределенность противника не может уменьшаться больше, чем на n log r. Отсюда
следовательно,
откуда получаем, что
(здесь мы воспользовались тем, что , и определением избыточности (3.23)).
П р и м е р 3.4. Оценим расстояние единственности для шифра из примера 3.3. Имеем , и энтропия на букву источника равна
Поэтому
Мы видели, что пяти букв было практически достаточно для раскрытия ключа. И нeравeнство (3.25) хорошо согласуется с нашим примером.
Поясним еще на одном примере, как взаимная зависимость символов увеличивает избыточность и тем самым уменьшает расстояние единственности.
П р и м е р 3.5. Пусть дан марковский источник, т.е. источник с памятью, в котором вероятность появления очередного символа зависит только от предыдущего символа. Источник описывается следующей матрицей переходов:
и начальными вероятностями P(a) = 0.19, P(b) = 0.34, P(c) = 0.47. Пусть, как и в примере 3.3, используется шифр с шестью возможными ключами, и пусть пeрeхвачeн зашифрованный текст
.
Мы видим по матрице переходов, что сочетание aa нeвозможно (после буквы a вероятность появления снова буквы a равна нулю), а сочетание bb — маловероятно (вероятность появления b после b равна 0.1). Следовательно, скорее всего первая пара букв соответствует буквам cc исходного сообщения, т.е. при шифровании была использована подстановка c b. Тогда ac соответствует исходным парам ab
или ba. По матрице мы видим, что сочетание ba невозможно, а возможно только ab. Поэтому мы можем предположить, что в качестве ключа была использована перестановка номер 2:
Вычислим точные вероятности использования различных ключей, как в примере 3.3. Заметим, что вероятность конкретного сообщения источника равна произведению вероятности начальной буквы и вероятностей переходов от одной буквы к другой.
Отсюда находим
и получаем по формуле Бейеса апостериорные вероятности использованных ключей при условии, что получено сообщение :
Эти вычисления подтверждают справедливость приведенного ранее неформального рассуждения.
Оценку расстояния единственности шифра можно использовать при конструировании криптосистем. Например, кажется разумным менять ключ на новый, когда общая длина зашифрованных с его помощью сообщений приближается к величине расстояния единственности.
Новые подходы к построению теоретически стойких криптосистем, связанные с применением методов специального кодирования, изложены в работах [10, 13, 14, 16, 24, 25] авторов данной книги. Предлагаемые там методы достаточно сложны для описания, однако они эффективны с вычислительной точки зрения и позволяют строить невскрываемые шифры с секретаым ключом. Основная идея этих методов состоит в обеспечении путем кодирования нулевой избыточности сообщения, которое подлежит шифрованию. Один из таких методов будет рассмотрен в следующем разделе.
В разд. 3.2 было введено понятие совершенной секретности, а затем было показано, что шифр Вернама совершенно секретен. Мы видели, что в этом шифре длина ключа равна длине сообщения и ключ используется всего один раз. Если же мы хотим использовать короткий многоразовый ключ (что актуально для большинства практических приложений), то какой наилучший результат в смысле стойкости шифра мы можем достичь? При обсуждении утверждения 3.6 указывалось, что при нулевой избыточности сообщения расстояние единственности шифра бесконечно. Это означает, что даже короткий (или, что эквивалентно, применяемый много раз) ключ, используемый для шифрования очень длинного сообщения нулевой избыточности, не может быть раскрыт. А это, в свою очередь, означает, что у противника, пытающегося разгадать зашифрованный текст, остается неопределенность, равная неопределенности ключа. Очевидно, это лучшее, что может быть достигнуто в данных условиях (здесь можно снова вспомнить пример с кодовым замком из первой главы). Эти рассуждения подводят нас к понятию строго идеального шифра, впервые введенному Шенноном [17].
Пусть сообщение m1m2 ... mt шифруется при помощи секретного ключа , в результате чего получается зашифрованное сообщение
. Обозначим через H(m1m2 ... mt) энтропию сообщения, через
и
— соответственно энтропии шифротекста и ключа. Тогда
представляет неопределенность сообщения, а
— неопределенность ключа при условии, что известен шифротекст
.
Определение 3.3. Шифр называется строго идеальным, если
(3.26)
Если энтропия ключа меньше энтропии сообщения источника, то (3.26) упрощается:
(3.27)
при всех достаточно больших t. Так как мы будем рассматривать случай, когда длина сообщения t велика, то в качестве определения строго идеального шифра будем использовать (3.27) .
Неформально, строгая идеальность шифра означает, что количество решений криптограммы равно количеству различных ключей и все решения равновероятны, как в примере с кодовым замком.
В этом разделе мы рассмотрим конструкцию идеальной системы, недавно предложенную в [10], ограничившись описанием только основной идеи применительно к случаю, когда сообщение порождается двоичным источником без памяти с неизвестной статистикой, иными словами, делается последовательно и независимо случайный выбор буквы из алфавита A = {a1,a2}, причем вероятности выбора букв неизвестны.
Пусть источник порождает потенциально неограниченные сообщения m1m2 ...mt, , и имеется ключ фиксированной длины
,
. (Как мы упомянули вьше, предполагается также, что энтропия источника на букву отлична от нуля, так как в противном случае вообще нет необходимости в передаче сообщений.) Будем последовательно разбивать сообщение источника на блоки символов длины n, где n > 1 — параметр метода. Обозначим один из таких блоков через
. Опишем преобразования, выполняемые над каждым таким n-буквенным блоком.
Вначале определим количество букв а1 и а2 в блоке . Пусть, скажем, имеется n1 букв а1 и n2 = n - n1 букв а2. Определим
как слово длины
бит, кодирующее n1.
Теперь рассмотрим множество S всех последовательностей, состоящих из n1 букв a1 и n2 букв a2. В этом множестве
элементов. Несмотря на то, что нам не известны вероятности последовательностей из множества S, одно мы можем сказать точно — все они равны между собой (в силу независимости выбора отдельных букв сообщения). Зададим на множестве S некоторый порядок, например, расположим сообщения в порядке возрастания соответствующих им двоичных чисел (считая, что а1 = 0, а2 = 1). Вычислим номер данного конкретного блока вутри упорядоченного множества S (для вычисления такого номера известен эффективный алгоритм [11], описание которого выходит за рамки нашей книги). Обозначим этот номер через
.
Разобьем множество S на непересекающиеся подмножества S0, S1, ..., Sv с числами элементов, равными различным степеням двойки (например, если |S| = 21, то получаем три подмножества с числами элементов 16, 4 и 1). По определим, какому подмножеству принадлежит
(обозначим номер такого подмножества через
), и найдем номер m внутри данного подмножества (обозначим этот номер через
).
Посмотрим внимательно на номер сообщения внутри подмножества, . Замечательно то, что
— это полностью случайная последовательность нулей и единиц (т.е. такая, где символы независимы, а вероятаости нуля и единицы равны). Действительно,
— это номер одной из равновероятных последовательностей букв в подмножестве из 2b элементов (для некоторого b). Номера всех таких последовательностей — это всевозможные последовательности из b двоичных цифр. если все последовательности из b двоичных цифр равновероятны, то отдельные символы равновероятны и независимы.
Итак, обрабатывая описанным образом последовательные блоки сообщения, мы представляем сообщение в виде
Теперь перейдем к описанию процесса шифрования преобразованного сообщения. На первый взгляд это может показаться странным, но слова u(•) и v(•) вообще не шифруются! Шифруются только слова с использованием секретного ключа
. В качестве Шифра можно, Например, использовать побитовое сложение по модулю 2 с периодически продолженным ключом. Для описания этого шифра удобно занумeровать символы слов
подряд и обозначить их через
. Тогда шифрование проводится по формуле
В результате примeнeния описанного метода мы зашифровали сообщение следующим образом:
(3.28)
По построению алгоритма ясно, что из правой части (3.28) можно восстановить сообщение, если знать . Вначалe нужно дешифровать символы слов
, используя формулу
(3.29)
а затем из слов восстанавливаются последовательные блоки сообщения.
П р и м е р 3.6. Пусть требуется зашифровать сообщение
с трехбитовым ключом = 011. Разобьем сообщение на два блока по пять символов, n = 5.
Выполним преобразование для первого блока . Для этого блока n1 = 1 и
. Рассмотрим теперь упорядоченное множество всех сообщений, состоящих из одной буквы a1 и четырех букв a2 (табл. 3.2). Всего таких сообщений
, поэтому имеем два подмножества S0 и S1 с числом элементов соответственно 4 и 1. Мы видим, что
входит в S0 под номером 2 = (10)2. Таким образом, мы получаем следующие два слова:
= 0,
= (10)2.
Таблица 3.2. Множество равновероятных сообщений; n1 = 1, n2 = 4
Теперь выполним преобразование для второго блока сообщения . Для этого блока n1 = 2 и
. Рассмотрим упорядоченное множество всех сообщений, состоящих из двух букв а1 и трех букв а2 (табл. 3.3). Всего таких сообщений
= 10, поэтому имеем два подмножества S0 и S1 с числом элементов соответственно 8 и 2. Мы видим, что
входит под номером 6 = (110)2 в S0. Таким образом, мы получаем
.
В результате мы получили следующий двоичный код преобразованного сообщения:
001 0 10 010 0 110
(пробелы здесь поставлены только для удобства чтения; для однозначного декодирования они не нужны).
Теперь зашифруем преобразованное сообщение. Периодически продолженный ключ имеет вид . Сложение битов слов
с этим ключом дает
Таблица 3.3. Множество равновероятных сообщений; n1 = 2, n2 = 3
Зашифрованное сообщение выглядит следующим образом:
= 001 0 11 010 0 011.
Остановимся теперь на основных свойствах рассмотренного метода.
Утверждение 3.7. Построенный шифр строго идеален.
Д о к а з а т е л ь с т в о. Как уже отмечалось при изложении метода, слово для каждого блока
состоит из равновероятных и независимых символов 0 и 1, другими словами, «полностью» случайно. Так как блоки в сообщении независимы, то в преобразованном сообщении последовательность слов
. также полностью случайна. Но любая последовательность
соответствует некоторому сообщению, и все такие сообщения равновероятны. Поэтому при подстановке любого ключа в дешифрующее выражение (3.29) мы получаем какое-либо решение, причем все решения равновероятны. В результате, имея только шифротекст
, мы ничего не можем сказать об использованном ключе, т.е.
Далее, каждому конкретному сообщению m1m2 ... mt соответствует одна и только одна последовательность , и при достаточно большом t, а именно, таком, что длина последовательности
не меньше длины ключа, каждому ключу, подставляемому в (3.29), соответствуют различные равновероятные сообщения. Поэтому
Ненулевая энтропия источника гарантирует то, что требуемое достаточно большое t всегда существует.
Таким образом, мы доказали, что (3.27) выполняется.
Особенностью предложенного шифра является то, что шифрованию подвергается не все преобразованное сообщение, а только его часть. В приведенном примере даже может показаться, что слишком много информации остается «открытой». Какая все-таки доля информации скрывается этим шифром? Следующее утверждение дает ответ на этот вопрос.
Утверждение 3.8. Пусть сообщение порождается источником без памяти с энтропией h на букву . Тогда для каждого блока из n символов сообщения средняя длина шифруемого слова
удовлетворяет неравенству
(3.30)
(здесь E(•) —математическое ожидание, а | • |— длина).
Д о к а з а т е л ь с т в о. Компонента кода может принимать любое значение от 0 до n, и поэтому ее максимальная энтропия равна log(n + 1).
Слово может принимать любое значение от 0 до
, что связано с разбиением S на подмножества S0, S1, ..., Sv. Очевидно, что
. Из известаого неравенства
получаем
. Поэтому максимальная энтропия слова
строго меньше log(n + 1).
Энтропия блока равна (так как символы порождаются источником без памяти). При преобразовании блока энтропия не изменяется, поэтому для энтропии слова
имеем
(из общей энтропии мы вычли верхнюю границу максимальной энтропии слов и
). так как слово
состоит из равновероятных и независимых символов 0 и 1, его средняя длина совпадает с энтропией, что завершает доказательство.
Неформально, утверждение 3.8 говорит о том, что «почти вся» информация сообщения содержится в шифруемой компоненте кода , если длина блока n достаточно велика. Иными словами, представленный шифр скрывает «почти всю» информацию. Причем даже полный перебор ключей не позволяет вскрыть шифр.
Конечно, рассмотренная конструкция идеальной криптосистемы может иметь различные варианты построения. Например, может представлять интерес вариант, в котором часть ключа используется для «закрытия» префикса (т.е. компонент u и v кода). Правда, в этом случае система будет «просто» идеальной (не строго идеальной).
3.1. Зашифровать сообщение шифром Вернама с ключом
:
3.2. Пусть источник без памяти порождает буквы из алфавита A = {a, b, c} с вероятаостями P(a), P(b), P(c). Шифратор заменяет буквы, используя одну из шести возможных перестановок, как это делалось в примере 3.3. Определить апостериорные вероятности использованных ключей для заданного зашифрованного сообщения :
3.3. Для источников задачи 3.2 вычислить энтропию и расстояние единственности.
3.4. По имеющемуся зашифрованному сообщению найти апостериорные вероятности использованных ключей и соответствующие им сообщения, если известно, что используется шифр примера 3.3, а сообщения порождаются марковским источником, описанным в примере 3.5: