kiev-security.org.ua-Криптография.Проблемы безопасности в системах обработки информации. Ранцевые алгоритмы

A.F.Ronzhin. Problems of Security in Information Processing Systems//В сб.: 2.5. РАНЦЕВЫЕ АЛГОРИТМЫ Эти алгоритмы основаны на классической задаче теории чисел (Merkle, Hellman, 1978). Пусть X=(x(1),...,x(n)) будет секретным двоичным вектором, который является открытым текстом, а A=(a(1),...,a(n)) будет несекретным вектором с целыми компонентами. Тогда зашифрованная информация - это число Y=(A,X)=a(1)x(1) +...+ a(n)x(n). Простота шифрования очевидна. Возможность восстановления X с помощью Y может быть получена благодаря соответствующему выбору A. Единственной проблемой является введение секретного значения, позволяющего легко дешифровать принятую скрытую информацию. Это можно сделать следующим образом. Выбирается секретный вектор A'=(a'(1),...,a'(n)) такой, что a'(l+1)>a'(1)+...+a'(l), l=1,...,n-1. Для такого вектора легко решается задача определения X из Y'=(A',X)=a'(1)x(1)+...+a'(n)x(n), поскольку x(n)=1, если Y'>=a'(1)+...+a'(n-1), x(n-1)=1, если Y'-a'(n)>=a'(1)+...+a'(n-2) и т.д. Ведем секретные взаимно простые числа r и t и найдем s такое, что st=1 mod r. Теперь шифрование можно организовать следующим образом. Определим несекретное A с координатами a(i)=a'(i)t mod r и выберем Y=(A,X) в качестве шифртекста, оставляя все сложности дешифрования на A. Для дешифрования преобразуем Y в Y'=Ys mod r и учитывая, что Y'=(A',X), уменьшим сложность восстановления X. Оценки соответствующих сложностей можно найти у (Shamir, 1982). 2.6. Последовательное шифрование Пусть открытый текст будет двоичной последовательностью, и существуют автономные автоматы A(k), k K, с выходным алфавитом {0,1}. Тогда для открытого текста X=(x(1),...,x(n)) и выходной последовательности R(k)=(r(1,k),...,r(n,k)) автомата A(k) шифртекст Y=(y(1),...,y(n)) определяется как y(i)=x(i) + r(i,k), i=1,...,n. Обычно, хотя и не необходимо, ключ k является начальным состоянием автомата. Поскольку x(i)=y(i) - r(i,k), i=1,...,n, шифрование и дешифрование реализуются одной и той же схемой. Такая схема шифрования-дешифрования имеет следующие важные черты: если ключ k используется для шифрования нескольких открытых текстов (например, если открытый текст разбит на блоки, и каждый блок шифруется отдельно той же самой последовательностью), и один из этих открытых текстов становится известным нарушителю, то он может легко получить последовательность R(k)=X+Y и затем без знания ключа k дешифровать все остальные записи, добавляя соответствующие шифртексты и R(k). Это происходит потому, что автомат A(k) для одинаковых начальных состояний каждый раз выдает тот же самый выход. Этого недостатка можно избежать, если каждый раз перед шифрованием изменять начальное состояние автомата. Начальным состоянием можно управлять с помощью некоторого параметра Z. Параметр вводится только для перевода автомата с ключом k в различные начальные состояния, но не для обеспечения криптографической надежности. По этой причине требования к Z не так сильны, как к ключам K. 2.7. Алгоритм DES Опишем алгоритм, известный как Data Encryption Standard (Стандарт шифрования данных). Перед обсуждением технической стороны процедуры обратимся к законодательству США по вопросам секретности и к истории разработки DES. Ясно, что такая информация может быть полезной для осуществления организационных мер по защите информации. Для сохранения тайны в системах обработки информации необходимо следовать ряду правил, регулирующих возможности пользователей по выбору, хранению и изменению информации по своему желанию. Кроме того, пользователи должны иметь авторское право на свою информацию. В настоящее время в США эти правила регулируются актом 1974 года (Privacy Act, 1974). Касательно криптографических мер защиты данных, их применение регулируется актом 1997 года (Public Law 95-213). Более подробное описание законодательства США по защите вычислительных систем можно найти в (Hoffman, 1977). В 1973 году Национальное бюро стандартов США опубликовало статью (Cryptographic Algorithms, 1973), в которой предлагалось разработать унифицированный криптоалгоритм для обработки компьютерных данных в коммерческой и оборонной областях. Были сформулированы следующие требования к алгоритму: 1. Алгоритм должен быть полностью описан без какой-либо неопределенности. 2. Он должен обеспечить соответствующий уровень безопасности, который можно естественным образом оценить по времени или количеству операций, требуемых для раскола системы. 3. Его стойкость должна быть основана только на стойкости ключа. 4. Он может без каких-либо ограничений применяться пользователями. 6 августа 1974 года IBM предложила алгоритм, разработанный научной группой под руководством W.L.Tuchman (Ehrsan et al., 1976), как удовлетворяющий этим требованиям. Алгоритм основывался на криптосистеме Lucifer (IBM Research Report, 1971), разработанной Файстелем (Feistel, 1974). Американским экспертом в криптологии и безопасности связи является Агентство национальной безопасности (АНБ). Национальное бюро стандартов совместно с АНБ оценило стойкость предложенного алгоритма (Report Workshop on Cryptography, 1977), который и составил основу DES, опубликованного АНБ 17 марта 1975 года; 15 июля 1975 года алгоритм был официально принят в качестве федерального стандарта. DES позволено применять федеральным агентствам и Государственному департаменту для шифрования данных, не попадающих под классификацию Акта о национальной безопасности (1974) и Акта о ядерной энергии (1954). Более того, он был рекомендован для применения промышленным корпорациям. DES был адаптирован Американским национальным институтом по стандартам (АНИС) к требованиям CCIP(X3) и принят в качестве стандартного промышленного алгоритма DEC X3.92 (American National Standard, 1981). Требования к стойкости, физической и электронной защите DES-оборудования были одобрены в (Proposed Federal Standard 1026, 1980; Proposed Federal Standard 1027, 1980). Там же можно найти более подробную информацию о разработке DES. В (Unclassified Summary, 1978) даны следующие официальные характеристики DES: 1. DES более, чем приемлем в своих областях применения. 2. IBM - изобретатель и создатель DES. 3. АНБ не принимало участия в разработке. 4. АНБ проверило стойкость DES против атак всеми известными статистическими методами. 5. АНБ рекомендовало ФБР использоватиь DES для передачи данных с помощью электронных средств. Алгоритм DES - это типичный представитель класса блочных шифров. Дадим его описание, следуя (DES, 1977). Алгоритм используется для шифрования и дешифрования блоков данных длиной 64 бита и управляется ключом длиной 64 бита. Как видно из рис.1, шифрование выполняется следующим образом. 64 бита входного блока преставляются в соответствии с начальной перестановкой (НП). Эта перстановка ставит на первую позицию 58-ой бит, на вторую позицию - 50-ый бит и т.д. Выход этой перестановки идет на вход процессора, который зависит от ключа. Выход процессора называют предварительным выходом; он переставляется в соответствии с подстановкой, обратной НП. Процессор выполняет 16 итераций с функцией f, которая зависит от двух 32-битных блоков предыдущей итерации и 48 бит ключа. Функция f называется функцией шифрования и принимает значения на множестве 32-битных блоков. Для каждой итерации 64 бита входного блока разбиваются на 32-битные блоки L и R. Пусть k будет 48-битным блоком, выбираемым из 64-битного блока ключа, тогда выход итерации состоит из 32-битного блока L' и 32-битного блока R' таких, что L'=R, R'=L+f(R,k). В каждой итерации ключ k выбирается из ключевой последовательности K, которая является 64-битным блоком. Выбор выполняется функцией Ks, зависящей от числа итераций n=1,...,16 и ключевой последовательности K. Ключ k , используемый в n-ой итерации, равен k =Ks(n,K). Дешифрование выполняется по тому же алгоритму лишь с тем различием, что ключи k ,...,k используются в обратном порядке. Функцию шифрования f можно представить схемой, показанной на рис.2. Функция Е на схеме размещает 32-битный блок R на 48 позициях по предписанному правилу. Каждая из восьми групп B ,...,B из 6 последовательных битов является входом соответствующей функции выбора Si, i=1,...,8, c 4-битными выходами. Для каждого i функция Si определяется (16х4)-матрицей Ai с элементами a , принимающими значения 0,1,...,15. Первый и последний биты входа рассматриваются как двоичное число, определяющее число r, а 4 средних бита рассматриваются как двоичное число6 определяющее s. Тогда выход Si равен a , представленному в двоичном счислении. Выход Si преобразуется перестановкой P. Таким образом, если входы функции f равны R и k, то f(R,k)=P(S (B ),...,S (B )), где B B ...B = k+E(R). Отметим, что мы рассматриваем g-блоки А и h-блок В записанными вместе как единый блок АВ длиной g+h. Процесс построения ключа k из 64-битного блока KEY показан на рис.3. Из 64 бит KEY функция PC-1 выбирает 56 бит и делит их на 28-битные блоки C и D. В каждой итерации i, i=1,...,16, выполняется циклический сдвиг содержимого регистров Ci и Di на l(i) бит влево, и с помощью функции PC-2 из полученного блока CiDi выбирается 48-битный блок k . Для завершения описания алгоритма остается задать значения НП, Е, S ,...,S , PC-1, PC-2 и L=(l(1),...,l(16)). Функции S ,...,S и PC-2 можно найти в (DES, 1977). Все они не имеют определенной структуры, и мы не даем здесь их описание. Таким образом, мы видим, что DES выполняет 16 итераций и зависит от 16 ключей длиной 48 бит каждый. Эти ключи, как следует из описания PC-1, выбираются из одного установленного ключа. Кроме того, содержимое регистров Ci, Di сдвигается, поэтому С =Со и D =Dо. При дешифровании функция выбора ключа действует точно так же, только сдвиг регистров выполняется вправо. Завершим описание алгоритма DES матрицей для выбора ключей k ,...,k k = 10 51 ... 41 22 28 ... 31 k = 2 43 ... 33 14 20 ... 23 .................................. k = 18 59 ... 49 30 5 ... 39 Среди этих чисел нет битов из разрядов 8,16,...,64, используемых для управления на начальном этапе построения ключа. Отметим некоторые черты алгоритма DES. 1. Слабые ключи (Meyer and Matyas, 1982). Существуют ключи, для которых k =...=k , т.е. ключи, для которых содержимое регистров C и D состоит только из нулей (толлько из единиц), либо из последовательностей вида 0101...01; 1010...10; 0011...0011; 0110...0110; 1001...1001; 1100...1100. Хотя число таких ключей очень мало по сравнению с общим числом ключей, равным 7*10^17, и вероятность того, что такой ключ появится при случайной генерации ключей, очень мала, необходимо исключать такие ключи путем специального контроля. 2. Критерии выбора математических преобразований. Первый этап DES длился 5 лет. В результате были предложены некоторые критерии, часть из которых строго сформулирована и может использоваться в криптоанализе. В частности, для выбора перестановок был принят принцип, что каждый выходной бит должен фактически зависеть от каждого бита ключа и открытого текста, а преобразование должно включать минимум итераций (Meyer, 1978). Другим важным принципом является требование, что функции в DES для своей реализации используют минимальное число логических операций (Honget al., 1974).