Мониторинг обменных курсов валют
18c0693f

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


Под 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. Положим, что злоумышленнику