Шифры с секретным ключом

 

Итак, наша задача заключается в том, чтобы снабдить участников обмена надежными алгоритмами шифрования. Первый вопрос, который мы себе зададим – это решаема ли задача в принципе, и если да, то какую максимальную степень секретности мы можем обеспечить? Ответ на этот вопрос был найден Шенноном – теорема, носящая его имя, гласит, что существуют абсолютно стойкие шифры, то есть такие шифры, которые невозможно раскрыть, даже если криптоаналитик обладает неограниченным запасом времени и вычислительных ресурсов. Шенноном также было установлено, что условием абсолютной стойкости шифра является использование в алгоритме шифрования не меньшего количества секретной информации, чем содержится информации в шифруемом сообщении.

Как реализовать такой шифр? Прежде чем отвечать на этот вопрос вспомним, что все современные шифры базируются на принципе Кирхгофа, который гласит, что алгоритмы шифрования должны строиться таким образом, чтобы даже при их разглашении они все еще обеспечивали определенный уровень надежности. Вернемся к обсуждаемой теме – ясно, что криптоалгоритмы, построенные в соответствии с принципом Кирхгофа должны использовать при шифровании секретные данные, называемые ключом, которые и обеспечивают секретность сообщения в условиях открытости самого алгоритма. Другими словами, секретность шифра должна обеспечиваться секретностью ключа, а не секретностью алгоритма шифрования. Это означает, что алгоритмы E и D, введенные нами в рассмотрение в предыдущем разделе, используют секретный ключ K, и могут быть обозначены нами теперь как E_Kи D_K. Тогда уравнения шифрования будут иметь следующий вид:

С = E_K(T) – зашифрование;

T = D_K(С) – расшифрование.

Вспомним, что в шифрах рассматриваемого класса для за- и расшифрования используется один и тот же ключ. Ясно, что процедура расшифрования должна в любом случае приводить к правильному результату. Это означает, что каковы бы ни были допустимые блок данных T и ключ K, должно выполняться следующее равенство: E_K(D_K(T)) = T.

Вернемся к абсолютно стойким шифрам, реализующим принцип Кирхгофа. Так как вся их секретность сосредоточена в ключе K, применительно к ним требование Шеннона означает, что размер ключа шифрования не должен быть меньше размера шифруемого сообщения: êKï ³ êTï. Будем полагать, что они имеют одинаковый размер, равный N бит: êKï = êTï = N. Это минимум, при котором все еще возможна абсолютная стойкость. Для зашифрования сообщение T необходимо скомбинировать с ключом K с помощью некоторой бинарной операции °таким образом, чтобы полученный шифротекст зависел и от исходного текста T, и от ключа K. При этом уравнение зашифрования будет иметь следующий вид: C = E_K(T) = T ° K.

Размер шифротекста при этом также равен N бит: |C| = |T| = |K| = N. Для обеспечения абсолютной стойкости шифра количество секретной информации в ключе K должно быть максимально возможным для его размера. Это означает, что все биты ключа должны быть случайны с равновероятными значениями и статистически независимы. Такой ключ может быть получен только аппаратным способом, алгоритмически его выработать нельзя, так как в этом случае указанное требование будет нарушено и шифр перестанет быть абсолютно стойким.

Обсудим теперь требования, которым должна удовлетворять операция °. Во-первых, чтобы шифрование было обратимым, уравнение T ° K = C должно быть однозначно разрешимо относительно T при любых значениях C и K. Это означает, что у бинарной операции °должна существовать обратная, которую мы обозначим через •, и каковы бы ни были N-битовые блоки данных T и K, всегда должно выполняться равенство (T ° K) • K = T. Во-вторых, для обеспечения полной секретности шифра необходимо, чтобы разные ключи давали для одинаковых исходных текстов разные шифротексты. Это равносильно требованию однозначной разрешимости уравнения T ° K = C относительно K. Так как секретность шифрованного сообщения целиком опирается на секретность ключа, во всем остальном операции °и •могут выбираться из соображений удобства. В качестве таких операций может использоваться сложение и вычитание по модулю 2^N:

T ° K = (T + K) mod 2^N, T • K = (T – K) mod 2^N.

Осуществить вычисления над сообщением как единым целым может оказаться затруднительным по причине его значительного размера, поэтому целесообразно разбить сообщение и ключ на блоки меньшего размера и применить указанные операции к этим блокам:

T = (T₁, T₂, ..., T_n), K = (K₁, K₂, ..., K_n), ïK_iï = ïT_iï = N_i,

, .

Если довести этот процесс дробления до логического конца, мы придем к операции побитового сложения по модулю 2, называемой также побитовым «исключающим или»:

T ° K = T • K = T Å K.

Последняя операция оказалась обратной к самой себе и по этой причине, а также в силу своей простоты и легкости реализации (отдельные биты сообщения в ней обрабатываются независимо друг от друга), получила наибольшее распространение.

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

Для шифрования двух различных сообщений нельзя применять одну и ту же последовательность элементов гаммы. Если это требование нарушено, всегда можно найти такую пару бинарных операций Ä и *, которые, будучи примененными соответственно к блокам открытых и зашифрованных с использованием одного и того же элемента гаммы данных, дадут идентичные результаты:

.

Это сделает задачу криптоанализа тем более легкой, чем больше избыточности содержится в сообщении. Для текстов на естественных языках ввиду их колоссальной избыточности эта задача становится почти тривиальной – отделить друг от друга такие сообщения не представляет труда. Такое разделение может быть выполнено методом перебора, причем на каждом шаге в переборе участвуют лишь несколько символов.

Если для наложения гаммы используется операция побитового суммирования по модулю 2, то в качестве бинарных операций, устраняющих влияние секретной гаммы на результат, может быть использована та же самая операция. Действительно, пусть, например, два блока шифруются с помощью одного и того же элемента гаммы G_iналагаемого на них операцией побитового сложения по модулю 2:

,

.

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

.

Как видим, результат совпадает с побитовой суммой по модулю 2 блоков открытого текста, что делает криптоанализ тривиальным.

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

Барьер, перед которым мы остановились, непреодолим: достичь эффективности практической реализации криптоалгоритма можно только отказавшись от абсолютной стойкости. Шифр, не являющийся абсолютно стойким, можно раскрыть за конечное время, точнее, за конечное число шагов, каждый из которых состоит в выполнении элементарной арифметической или логической операции. Однако ничто не мешает нам создать такой теоретически нестойкий шифр, для раскрытия которого требовалось бы выполнить настолько большое число операций, чтобы это было неосуществимо на современных и ожидаемых в не очень далекой перспективе вычислительных средствах за разумное время. Мерой практической стойкости шифров подобного типа может служить количество работы, необходимое для их раскрытия, выраженное в элементарных операциях или в длительности соответствующих вычислений на современных компьютерах. Отметим, что в реальных системах криптозащиты информации используются почти исключительно теоретически нестойкие шифры.

Хороший шифр должен быть устойчив к статистическому и алгоритмическому анализу, то есть не должно существовать легко обнаружимых статистических связей между открытым и шифрованным текстом и зависимости между ними должны быть достаточно сложными для того, что бы их можно было обнаружить путем анализа. Есть четкая граница между хорошо и не очень хорошо спроектированными блочными шифрами: первый невозможно раскрыть способом, более эффективным чем полный перебор по всем возможным значениям ключа, для раскрытия второго могут оказаться пригодными и более эффективные способы. Как же строить стойкие шифры? Наука об этом засекречена практически везде, где имеют дело с криптографией – публикуются лишь соображения, носящие самый общий характер и не содержащие никакой конкретики. Приобщиться к этим тайным знаниям можно, лишь работая в соответствующем подразделении соответствующей специальной службы. Ну, а мы с вами попытаемся рассмотреть проблему исключительно с позиции здравого смысла. По большому счету, можно предложить лишь два фундаментальных подхода к построению шифра с секретным ключом:

· вырабатываемый элемент гаммы G_iне зависит от шифруемого блока данных T_i;

· шифрование массива информации T осуществляется путем манипулирования с ним самим.

Первый подход очевидным образом вытекает из шифра Вернама. Все отличие заключаются в том, что в нем гамма сама по себе не является ключевым элементом, а только вырабатывается из ключа K фиксированного размера с помощью некоторого набора функций f_i: G_i = f_i(K), или, точнее, одной универсальной функции G_i = f(i, K) – хотя с точки зрения математики это одно и то же, с алгоритмической точки зрения это разные вещи. Требование практической реализуемости шифра в виде аппарата или программы для ЭВМ приводит к необходимости возможности его описания в форме алгоритма с конечным числом возможных состояний, наиболее общей моделью которого может служить конечный автомат. Таким образом, генератор гаммы может быть определен с помощью следующих соотношений как конечный автомат без входа:

S_i = W_K(S_i–1), G_i = Q_K(S_i) – простое гаммирование,

или как конечный автомат со входом, если вырабатываемый блок гаммы зависит от предшествующего блока шифротекста и/или открытого текста:

, G_i = Q_K(S_i) – гаммирование с обратной связью.

Первое из двух соотношений определяет правило изменения состояний, второе – правило выработки выходного элемента, то есть элемента гаммы. Ясно, что для обеспечения секретности шифра оба эти правила должны или сами быть секретными, или зависеть от значения секретного ключа K. Шифры, построенные по данной схеме, называются потоковыми, так как в них используется поток гаммы, вырабатываемый генератором. Зашифрование (расшифрование) осуществляется путем простого наложения элементов гаммы на блоки открытого (шифрованного) текста с помощью соответствующих бинарных операций: , . В зависимости от используемых операций наложение гаммы может осуществляться как побитово, так и блоками иного размера. Основная сложность при реализации данного подхода заключается в разработке действительно качественного источника криптостойкой гаммы.

Прежде чем перейти к дальнейшему изложению напомним определение конечного автомата. Конечным автоматом называют устройство (реально существующее или гипотетическое) у которого имеются входные и выходные каналы, само устройство в каждый дискретный момент времени может находиться в одном из нескольких возможных внутренних состояний. Множество входных (выходных) сигналов и множество внутренних состояний конечны. Считается известным правило по которому устройство переходит из некоторого состояния в момент t в другое или тоже состояние в момент t+1. Известно правило по которому определяется выходной сигнал в момент t в зависимости от того каким в этот момент был входной сигнал и каково было внутреннее состояние устройства.

Конечным автоматом будем называть пятерку объектов V = {A, B, Q, j, y}, где

A = {a₁, ..., a_m} – входной алфавит;

B = {b₁, ..., b_s} – выходной алфавит;

Q = {q₁, ..., q_n} – алфавит состояний;

j: Q´A ® Q – функция переходов;

y: Q´A ® B – функция выходов;

q(t+1) = j(q(t), a(t)), b(t) = y(q(t), a(t)).

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