Основы современной криптографии

       

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


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

x = (x0 , x1

, ..., xN?1) О Z2,N;

x в Z2,N можно интерпретировать как вектор и как двоичное представление целого числа

||x|| =

.

Например, если 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.

Блочным шифром будем называть элемент pО SYM(Z2,N):

 p: x®y = p(x),

где x = (x0, x1, ..., xN-1), x = (y0, y1, ..., yN?1). Хотя блочные шифры являются частными случаями подстановок (только на алфавитах очень большой мощности), их следует рассматривать особо, поскольку, во-первых, большинство симметричных шифров, используемых в системах передачи информации, являются блочными и, во-вторых, блочные шифры удобнее всего описывать в алгоритмическом виде, а не как обычные подстановки.



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

p(xi) = yi , 0 Ј i < m,

для некоторого p О SYM(Z2,N), исходного текста X = {xi: xi

ОZ2,N} и шифрованного текста Y = {yi}. Что можно сказать о p(x), если xП{xi}? Поскольку p является перестановкой на Z2,N , то {yi} различны и p(x)П{yi} при xП{xi}. Что же еще можно сказать о p?

(2N ? m)! из (2N)! перестановок в SYM(Z2,N) удовлетворяет уравнению

p(xi) = yi , 0 Ј i < m,

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

П = {pj

: 0Ј j <2}, p(i) = (i+j) (mod 2N ), 0 Ј i <2 ,

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


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

xi « yi , 0 Ј i < m,

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

Если для шифрования исходного текста используется подсистема p из ПОSYM(Z2,N), то получающуюся в результате систему подстановок П будем называть системой блочных шифров или системой блочных подстановок. Блочный шифр представляет собой частный случай моноалфавитной подстановки с алфавитом Z2N

= Z2,N . Если информация исходного текста не может быть представлена N-разрядными блоками, как в случае стандартного алфавитно-цифрового текста, то первое, что нужно сделать, это перекодировать исходный текст именно в этот формат. Перекодирование можно осуществить несколькими способами и с практической точки зрения неважно, какой из способов был выбран.

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

является подмножество П[K] симметрической группы SYM(Z2,N)

П[K] = {p{k}: kОK},

индексируемое по параметру k О K; k является ключом, а K - пространством ключей. При этом не требуется, чтобы различные ключи соответствовали различным подстановкам Z2,N.

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

y = p{k, x}

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

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




  • известен алгоритм определения подстановки p{k} по значению ключа k;


  • неизвестно, какой именно ключ k выбрал пользователь.


  • Какими возможностями располагает злоумышленник? Он может:

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


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


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


    • получить соответствующие исходный и шифрованный тексты и исследовать соотношение исходного текста x и шифрованного текста y

      для определения ключа k;


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


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

      2)    цифровое представление графической и звуковой информации имеет ограниченный набор знаков.

      Предположим, что N = 64 и каждый элемент SYM(Z2,N) может быть использован как подстановка, так что K = SYM(Z2,N).

      Тогда:

              существует 264

      64-разрядных блоков; злоумышленник не может поддерживать каталог с 264

      =1,8x1019 строками;

                проба на ключ при числе ключей, равном (264)!, практически невозможна; соответствие исходного и шифрованного текстов для некоторых N-разрядных блоков p{k,xi} = yi

      , 0 Ј i < m, не дает злоумышленнику информации относительно значения p{k, x} для  xП{xi}.

      Системы шифрования с блочными шифрами, алфавитом Z2,64

      и пространством  ключей K = SYM(Z2,64) являются неделимыми в том смысле, что поддержание каталога частот появления букв для 64-разрядных блоков или проба на ключ при числе ключей 264 выходит за пределы возможностей злоумышленника. Следует сравнить эту проблему с той задачей, с которой сталкивается злоумышленник в процессе криптоанализа текста, зашифрованного подстановкой Цезаря с алфавитом {A,..., Я,}; для определения ключа подстановки Цезаря требуется лишь log232 = 5 бит, в то время как для пространства ключей K = SYM(Z2,64) требуется 264 битов.



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

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

      *         достаточно большое N (64 или более) для того, чтобы затруднить составление и поддержание каталога. В требованиях к новому стандарту шифрования ;

      *         достаточно большое пространство ключей для того, чтобы исключить возможность подбора ключа;

      *         сложные соотношения p{k,x} : x ® y=p{k,x}  между исходным и шифрованным текстами с тем, чтобы аналитические и (или) статистические методы определения исходного текста и (или) ключа на основе соответствия исходного и шифрованного текстов были бы по возможности нереализуемы.


      Содержание раздела