2. СИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ

2.1. Основные классы симметричных криптосистем

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

Исходное Отправитель Зашифр. Получатель сообщение (Д) сообщение (В)

Y=Ek(k,X),

> Шифратор

Дешифратхэр Х=Ек \к, Е (кД))

Ключ (к)

Ключ (к)

Рис 2.1. Схема симметричной криптосистемы.

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

Моно- и многоалфавитные подстановки.

Моноалфавитные подстановки - это наиболее простой вид преобразований, заключаюш,ийся в замене символов исходного текста на другие (того же алфавита) по более или менее сложному правилу. В случае моноалфавитных подстановок каждый символ исходного текста преобразуется в символ шифрованного текста по одному и тому же закону. При многоалфавитной подстановке закон преобразования меняется от символа к символу. Один и тот же шифр может рассматриваться и как моно- и как многоалфавитный в зависимости от определяемого алфавита. Например, шифр Плейфера (подстановка биграмм) с точки зрения обычного алфавита является моноалфавитным, а с точки зрения алфавита биграмм - многоалфавитным.

Перестановки.

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

ного текста по некоторому правилу. Шифры перестановок в на-стояш,ее время не используются в чистом виде, так как их криптостойкость недостаточна. Блочные шифры.

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

Гаммирование.

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

2.2. Общие сведения о блочных шифрах.

Под N-разрядным блоком будем понимать последовательность из нулей и единиц длины N:

Х = (Хо ,Xi , ...,Xn-\) G Z2,№

X в Zijj можно интерпретировать как вектор и как двоичное представление целого числа

N-i-1

Теория блочных шифров в целом изложена по работе [8]. 16

Например, если N=4, то (0,0,0,0)0 (0,0,0,1)1 (0,0,1,0)2 (0,0,1,1)3 (0,1,0,0)4 (0,1,0,1)5 (0,1,1,0)6 (0,1,1,1)7 (1,0,0,0)8 (1,0,0,1)9 (1,0,1,0)10 (1,0,1,1)11 (1,1,0,0)12 (1,1,0,1)13 (1,1,1,0)14 (1,1,1,1)15.

Блочным шифром будем называть элемент л g SYM(Z2,n): л: х-у = 7i;(x), где х = (хо, Хх, Хмл), У = (Уо, Уъ Умл). Хотя блочные шифры являются частными случаями подстановок (только на алфавитах очень большой мош,ности), их следует рассматривать особо, поскольку, во-первых, большинство симметричных шифров, используемых в системах передачи информации, являются блочными и, во-вторых, блочные шифры удобнее всего описывать в алгоритмическом виде, а не как обычные подстановки.

Предположим, что

7i;(xi) = у,, О < / < w,

для некоторого л g SYM(Z2,a), исходного текста X = {х,: х, gZ2} и шифрованного текста Y = {у;}. Что можно сказать о л(х), если х€ {xi}? Поскольку % является перестановкой на Z2n , то {у,} различны и л(х)€ {у,} при х€ {х,}. Что же еш,е можно сказать о л?

(2 - т)! из (2)! перестановок в SYM(Z2 a) удовлетворяет уравнению

л(х,) = у,, О < / < т.

Дальнейшая спецификация л(х) при отсутствии дополнительной информации не представляется возможной. Это определяется в основном тем обстоятельством, что л является элементом, при-надлежаш,им SYM(Z2 n)- Если известно, что л принадлежит небольшому подмножеству П из SYM(Z2,n), то можно сделать более определенный вывод. Например, если

П = {л,: 0< j <2}, л/О = (i+j) (mod 2), О < / <2 ,

то значение л(х) при заданном значении х однозначно определяет л. В этом случае X является подмножеством подстановок Цезаря на Z2,№

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

X/ <->у1,0< i<m,

не в состоянии на основе этой информации определить исходный текст, соответствуюш,ий у€ {у,}.

Если для шифрования исходного текста используется подсистема л из Hg SYM(Z2 n)5 то получаюш,уюся в результате систему подстановок П будем называть системой блочных шифров или системой блочных подстановок. Блочный шифр представляет собой частный случай моноалфавитной подстановки с алфавитом Z2N = Z2 N • Если информация исходного текста не может быть представлена N-разрядными блоками, как в случае стандартного алфавитно-цифрового текста, то первое, что нужно сделать, это перекодировать исходный текст именно в этот формат. Перекодирование можно осуш,ествить несколькими способами и с практической точки зрения неважно, какой из способов был выбран.

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

группы SYM(Z2,7v)

П[K] = {л{A:}:GK},

индексируемое по параметру А: g К; А: является ключом, а К -пространством ключей. При этом не требуется, чтобы различные ключи соответствовали различным подстановкам Z2 n-

Ключевая система блочных шифров П[К] используется сле-дуюш,им образом. Пользователь / и пользователь j некоторым образом заключают соглашение относительно ключа к из К, выбирая, таким образом, элемент из П[К] и передавая текст, зашифрованный с использованием выбранной подстановки. Запись

У = х}

будем использовать для обозначения N-разрядного блока шифрованного текста, который получен в результате шифрования N-разрядного блока исходного текста х с использованием подстановки л {А:}, соответствуюш,ей ключу к. Положим, что злоумышленнику

известно пространство ключей К;

известен алгоритм определения подстановки л{А:} по

значению ключа к; неизвестно, какой именно ключ к выбрал пользователь. Какими возможностями располагает злоумышленник? Он может:

получить ключ вследствие небрежности пользователя / или пользователя j;

перехватить (путем перехвата телефонных и компьютерных сообш,ений) шифрованный текст у, передаваемый пользователем / пользователю j, и производить пробы на все возможные ключи из К до получения читаемого сообш,ения исходного текста;

получить соответствуюш,ие исходный и шифрованный тексты (ху) и воспользоваться методом пробы на ключ;

получить соответствуюш,ие исходный и шифрованный тексты и исследовать соотношение исходного текста X и шифрованного текста у для определения ключа к,

организовать каталог N-разрядных блоков с записью частот их появления в исходном или шифрованном тексте. Каталог дает возможность производить поиск наиболее вероятных слов, используя, например, сле-дуюш,ую информацию:

листинг на языке ассемблера характеризуется сильно выраженным структурированным форматом,

цифровое представление графической и звуковой информации имеет ограниченный набор знаков. Предположим, что iV = 64 и каждый элемент SYM(Z2,a) может быть использован как подстановка, так что K=SYM(Z2). Тогда:

суш,ествует 2 64-разрядных блоков; злоумышленник не может поддерживать каталог с 2 =l,8•10 строками;

проба на ключ при числе ключей, равном (2")!, практически невозможна; соответствие исходного и шифрованного текстов для некоторых N-разрядных блоков л{А:,Х/} = у, , О < / < /и, не дает злоумышленнику информации относительно значения к{к, х} для х€ {х,}. Системы шифрования с блочными шифрами, алфавитом Z2 64 и пространством ключей K=SYM(Z2 64) являются неделимыми в том смысле, что поддержание каталога частот появления букв для 64-разрядных блоков или проба на ключ при числе ключей 2 выходит за пределы возможностей злоумышленника Следует сравнить эту проблему с той задачей, с которой сталкивается злоумышленник в процессе криптоанализа текста, зашифрованного подстановкой Цезаря с алфавитом {А,..., Я, }; для определения ключа подстановки Цезаря требуется лишь log232 = 5 бит, в то время как для пространства ключей K=SYM(Z2,64) требуется 2" битов.

К сожалению, разработчик и злоумышленник находятся в одинаковом положении: разработчик не может создать систему, в которой были бы реализованы все 2\ подстановок SYM(Z2 64)5 а злоумышленник не может испытать такое число ключей. Остается согласиться с тем, что не каждый элемент из SYM(Z2,64) будет использован в качестве подстановки.

Таким образом, требования к хорошему блочному шифру формулируются следуюш,им образом. Необходимы:

достаточно большое N (64 или более) для того, чтобы затруднить составление и поддержание каталога В новом стандарте шифрования СШАЖне меньше 128; достаточно большое пространство ключей для того, чтобы исключить возможность подбора ключа; сложные соотношения л{к,х} : х у=л{к,х} между исходным и шифрованным текстами с тем, чтобы аналитические и (или) статистические методы определения исходного текста и (или) ключа на основе соответствия исходного и шифрованного текстов были бы по возможности нереализуемы.

2.3. Генерирование блочных шифров

Одним из наиболее распространенных способов задания блочных шифров является использование так называемых сетей