Общие сведения о блочных шифрах
Под 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} между исходным и шифрованным текстами с тем, чтобы аналитические и (или) статистические методы определения исходного текста и (или) ключа на основе соответствия исходного и шифрованного текстов были бы по возможности нереализуемы.
