Программная реализация RC5
Автор: Василий Текин
Сразу скажем, что речь здесь пойдёт о шифре RC5, точнее, об одной из его модификаций.
Разумеется, существуют специальная литература, а также библиотеки программ, в которых помимо
RC5 можно найти и множество других алгоритмов. Немало материалов, включая тексты программ,
бродят и в Интернете. Однако книг ещё мало, а те, что выпущены, в большей части касаются
теоретических вопросов криптографии, либо ориентируют читателя на использование готовых
библиотек загрузочных модулей, содержимое которых, кстати, доподлинно никому не известно.
Обычно говорят, что криптография используется для защиты информации. Но информация
является объективным свойством материи и ни в какой защите (как и сама материя) не
нуждается. Защищают лишь представление информации на материальном носителе (иногда
вместе с носителем), т.е. сообщения или данные, стандартной математической моделью для
которых являются натуральные числа.
Возможность использование такой модели основана на позиционной записи натуральных
чисел конечным числом цифр. В качестве цифр рассматривается алфавит языка сообщения,
при необходимости дополненный арабскими цифрами, пробелом и знаками препинания.
Конечность такого алфавита очевидна, исключая иероглифическую письменность, а также
неоцифрованный звук и изображение.
Оцифровка может оказаться затруднительной при наличии в передаваемом сообщении
стеганограммы. Иногда такая же проблема возникает и при передаче "обычных" текстов, например,
при их неоднозначности, как это имеет место при использовании телеграфного кода Морзе.
С абстрактной точки зрения, криптография является наукой об обратимых преобразованиях,
зависящих от некоторого параметра — ключа шифрования. Ключ и защищаемые данные
рассматриваются как натуральные числа, а всякое такое преобразование описывается функцией
F: N*N --> N, где N — множество натуральных чисел, а N*N — множество его упорядоченных
пар.
Первый элемент в такой паре можно считать ключом, второй элемент — шифруемым сообщением.
Введя для множества ключей, исходных и шифрованных сообщений обозначения K, S и T
(каждое из которых есть N), указанное преобразование можно записать ещё и в виде F: K*S -->
T. Для каждого фиксированного ключа k из K функция F обратима, т. е. для любого
шифрованного сообщения t из T существует единственное исходное сообщение s в S.
Криптография распадается на криптологию, занимающуюся поиском соответствующих
отображений F, и криптоанализ, исследующий вопросы восстановления исходного сообщения s
по его шифрограмме t при неизвестном ключе k (иногда восстановлению ключа k по исходному s
и шифрованному t сообщениям). В криптологии в отличие от криптоанализа суть исходного
сообщения интереса не представляет.
Поскольку любое натуральное число может быть записано с использованием всего лишь двух
цифр 0 и 1, то криптография обычно рассматривает только действия над двоичными числами и
векторами с двоичными компонентами.
В зависимости от размера порции шифруемой информации различают блочные и потоковые
шифры. Размер блока блочного шифра конечен и заранее фиксирован. Размер блока поточного
шифра не определён.
Описать блочные и потоковые преобразования можно, в принципе, с помощью невырожденных
матриц (в последнем случае заранее неопределённого размера). Элементами таких матриц
являются числа 0 и 1. Сообщения представляются последовательностями этих же цифр
фиксированной для блочных или неопределённой для потоковых шифров длины. Особенность
матричных операций состоит в том, что все действия над числами здесь выполняются по модулю 2.
Вид матрицы зависит от используемого ключа шифрования и, возможно, исходного текста. В
последнем случае говорят о "свёрточности" шифра. Свёрточными могут быть как блочные, так и
потоковые шифры.
Матрица преобразования, если она конечна, может быть представлена, как обычно, в виде
некоммутирующего произведения двух матриц, одна из которых содержит в каждой строке ровно
одну 1 и описывает перестановки битов преобразуемого вектора, а вторая соответствующим
образом дополняет первую и описывает подстановки.
Для потоковых шифров размер преобразующей матрицы не определён и перестановки
оказываются невозможны. Из этого, конечно, не следует, что стойкость потоковых шифров ниже
блочных. Просто потоковые шифры качественно отличаются от последних.
В шифре RC5, который относится к блочным, перестановочные операции реализованы
циклическими (кольцевыми) сдвигами (rol/ror), а подстановки осуществляются арифметическим
сложением по модулю 2(xor) и по модулю b разрядной сетки вычислителя (обычные +/–).
Для усиления шифра сдвиги и сложения выполняются циклически в нескольких раундах (от англ.
Round — круг, цикл) шифрования.
Каждый раунд шифрования увеличивает случайность получаемого результата прежде всего за
счёт возрастания рассеивания его битов.
Вводя по аналогии с линейными операциями shl и shr операции rol и ror циклического сдвига
влево и вправо, а также полагая T=Y|Z и Key=Key[0]|Key[1]|...|Key[2*R+1], где R определяет
число раундов шифрования, знак двойного штриха "|" означает операцию сцепления b-
разрядных беззнаковых целых Y, Z и Key[i], i=0..2*R+1, имеющих смысл, соответственно, левого
и правого полублоков преобразуемого блока T разрядности 2b битов и частичных подключей
ключа Key, алгоритмы шифрования и дешифрирования для RC5 на паскалеподобном псевдокоде
можно записать [2] следующим образом.
(*-------------------------------------------------------------*)
Шифрование.
Вход: шифруемый блок T = Y | Z;
(* Один псевдораунд шифрования *)
Y := Y + Key [0];
Z := Z + Key [1];
(* R раундов шифрования *)
for I := 1 to R
do
begin
Y := (Y xor Z) rol Z + Key [2 * I];
Z := (Z xor Y) rol Y + Key [2 * I + 1]
end;
Выход: зашифрованный блок T = Y | Z;
(*-------------------------------------------------------------*)
Дешифрирование.
Вход: зашифрованный блок T = Y | Z;
(* R раундов дешифрирования *)
for I := R downto 1
do
begin
Z := (Z - Key [2 * I + 1]) ror Y xor Y;
Y := (Y - Key [2 * I]) ror Z xor Z
end;
(* Один псевдораунд дешифрования *)
Z := Z - Key [1];
Y := Y - Key [0];
Выход: расшифрованный блок T = Y | Z;
(*-------------------------------------------------------------*)
А вот как (после некоторой оптимизации) может выглядеть соответствующая 16-разрядная
(b=16) реализация алгоритма на Turbo Pascal, если Stringtype объявлен следующим образом:
type
Stringtype = string [$FF];
(*-------------------------------------------------------------*)
procedure EnCrypt (var Y, Z : integer; Key : Stringtype);
var
I, K, L : byte;
begin
K := Length (Key) shr 2;
if K = 0
then Exit;
L := 1;
Y := Y + MemW [Seg (Key) : Ofs (Key) + L];
L := L + 2;
Z := Z + MemW [Seg (Key) : Ofs (Key) + L];
for I := 1 to Pred (K)
do
begin
Y := Y xor Z;
K := Z and $0F;
L := L + 2;
Y := Y shl K or Y shr (Sizeof (Y) shl $04 - K)
+ MemW [Seg (Key) : Ofs (Key) + L];
Z := Z xor Y;
K := Y and $0F;
L := L + 2;
Z := Z shl K or Z shr (Sizeof (Z) shl $04 - K)
+ MemW [Seg (Key) : Ofs (Key) + L]
end;
Exit
end; (* EnCrypt *)
(*-------------------------------------------------------------*)
procedure Decrypt (var Y, Z : integer; Key : Stringtype);
var
I, K, L : byte;
begin
K := Length (Key) shr 2;
if K = 0
then Exit;
L := Pred (K shl 2);
for I := Pred (K) downto 1
do
begin
K := Y and $0F;
Z := Z - MemW [Seg (Key) : Ofs (Key) + L];
L := L - 2;
Z := (Z shr K or Z shl (Sizeof (Z) shl $04 - K)) xor Y;
K := Z and $0F;
Y := Y - MemW [Seg (Key) : Ofs (Key) + L];
L := L - 2;
Y := (Y shr K or Y shl (Sizeof (Y) shl $04 - K)) xor Z
end;
Z := Z - MemW [Seg (Key) : Ofs (Key) + L];
L := L - 2;
Y := Y - MemW [Seg (Key) : Ofs (Key) + L];
Exit
end; (* Decrypt *)
(*-------------------------------------------------------------*)
Как видно из построения программ, число раундов шифрования R зависит от длины l строки ключа
Key. Если длина ключа l<=3, то шифрование/дешифрирование не выполняется. При длина ключе
более 3 байт, число раундов R шифрования/дешифрирования определяется по формуле:
l := Length (Key);
R := 8 * l div (2 * b) – 1;
При значение R=0 выполняется один только псевдорауд. При R=–1 никаких преобразований не
производится (другие значения R невозможны).
Отвечающая разрядности 2b входного блока, длине ключа в байтах l и числу раундов
шифрования/дешифрирования R модификация алгоритма RC5 записывается в виде RC5-b/R/l. В
данном случае b=16, а значения R и l определяются приведёнными выше формулами.
Как указывается в [2] криптостойкое шифрование соответствует R>=12, что предполагает длину
ключа l>=52 байтов. Правда, это при b=32 вместо наших b=16. Но проблема преодолима, если
используется Turbo Pascal старших версий, поддерживающих работу с 32-битовыми регистрами.
(*-------------------------------------------------------------*)
procedure EnCrypt (var Y, Z : longint; Key : Stringtype);
var
I, K, L : byte;
begin
K := Length (Key) shr 3;
if K = 0
then Exit;
L := 1;
Y := Y + MemL [Seg (Key) : Ofs (Key) + L];
L := L + 4;
Z := Z + MemL [Seg (Key) : Ofs (Key) + L];
for I := 1 to Pred (K)
do
begin
Y := Y xor Z;
K := Z and $1F;
L := L + 4;
Y := Y shl K or Y shr (Sizeof (Y) shl $04 - K)
+ MemL [Seg (Key) : Ofs (Key) + L];
Z := Z xor Y;
K := Y and $1F;
L := L + 4;
Z := Z shl K or Z shr (Sizeof (Z) shl $04 - K)
+ MemL [Seg (Key) : Ofs (Key) + L]
end;
Exit
end; (* EnCrypt *)
(*-------------------------------------------------------------*)
procedure Decrypt (var Y, Z : longint; Key : Stringtype);
var
I, K, L : byte;
begin
K := Length (Key) shr 3;
if K = 0
then Exit;
L := K shl 3 - 3;
for I := Pred (K) downto 1
do
begin
K := Y and $1F;
Z := Z - MemL [Seg (Key) : Ofs (Key) + L];
L := L - 4;
Z := (Z shr K or Z shl (Sizeof (Z) shl $04 - K)) xor Y;
K := Z and $1F;
Y := Y - MemL [Seg (Key) : Ofs (Key) + L];
L := L - 4;
Y := (Y shr K or Y shl (Sizeof (Y) shl $04 - K)) xor Z
end;
Z := Z - MemL [Seg (Key) : Ofs (Key) + L];
L := L - 4;
Y := Y - MemL [Seg (Key) : Ofs (Key) + L];
Exit
end; (* Decrypt *)
(*-------------------------------------------------------------*)
Если же ограничиться Turbo Pascal 3.xx, то эффективность ранее представленных программ
можно заметно повысить, переписав их непосредственно в кодах:
(*-------------------------------------------------------------*)
procedure EnCrypt (var Y, Z : integer; Key : Stringtype);
begin
InLine (
$29/$D2 (* sub DX, DX *)
/$8A/$96/Key (* mov DL, [BP+Key] *)
/$D1/$EA (* shr DX, 1 *)
/$D1/$EA (* shr DX, 1 *)
/$09/$CA (* or DX, DX *)
/$74/$47 (* jz Exit2 *)
/$C4/$B6/Y (* les SI, [BP+Y] *)
/$26/$8B/$04 (* mov AX, ES:[SI] *)
/$C4/$B6/Z (* les SI, [BP+Z] *)
/$26/$8B/$1C (* mov BX, ES:[SI] *)
/$29/$F6 (* sub SI, SI *)
/$46 (* inc SI *)
/$03/$82/Key (* add AX, [BP+Key][SI] *)
/$46 (* inc SI *)
/$46 (* inc SI *)
/$03/$9A/Key (* add BX, [BP+Key][SI] *)
/$4A (* dec DX *)
/$74/$1B (* jz Exit1 *)
(* Cycle: *)
/$31/$D8 (* xor AX, BX *)
/$8A/$CB (* mov CL, BL *)
/$D3/$C0 (* rol AX, CL *)
/$46 (* inc SI *)
/$46 (* inc SI *)
/$03/$82/Key (* add AX, [BP+Key][SI] *)
/$31/$C3 (* xor BX, AX *)
/$8A/$C8 (* mov CL, AL *)
/$D3/$C3 (* rol BX, CL *)
/$46 (* inc SI *)
/$46 (* inc SI *)
/$03/$9A/Key (* add BX, [BP+Key][SI] *)
/$4A (* dec DX *)
/$75/$E5 (* jnz Cycle *)
(* Exit1: *)
/$C4/$B6/Y (* les SI, [BP+Y] *)
/$26/$89/$04 (* mov ES:[SI], AX *)
/$C4/$B6/Z (* les SI, [BP+Z] *)
/$26/$89/$1C (* mov ES:[SI], BX *)
(* Exit2: *)
);
Exit
end; (* EnCrypt *)
(*-------------------------------------------------------------*)
procedure Decrypt (var Y, Z : integer; Key : Stringtype);
begin
InLine (
$29/$D2 (* sub DX, DX *)
/$8A/$96/Key (* mov DL, [BP+Key] *)
/$D1/$EA (* shr DX, 1 *)
/$D1/$EA (* shr DX, 1 *)
/$09/$D2 (* or DX, DX *)
/$74/$4B (* jz Exit2 *)
/$C4/$B6/Y (* les SI, [BP+Y] *)
/$26/$8B/$04 (* mov AX, ES:[SI] *)
/$C4/$B6/Z (* les SI, [BP+Z] *)
/$26/$8B/$1C (* mov BX, ES:[SI] *)
/$8B/$F2 (* mov SI, DX *)
/$D1/$E6 (* shl SI, 1 *)
/$D1/$E6 (* shl SI, 1 *)
/$4E (* dec SI *)
/$4A (* dec DX *)
/$74/$1B (* jz Exit1 *)
(* Cycle: *)
/$2B/$9A/Key (* sub BX, [BP+Key][SI] *)
/$4E (* dec SI *)
/$4E (* dec SI *)
/$8A/$C8 (* mov CL, AL *)
/$D3/$CB (* ror BX, CL *)
/$31/$C3 (* xor BX, AX *)
/$2B/$82/Key (* sub AX, [BP+Key][SI] *)
/$4E (* dec SI *)
/$4E (* dec SI *)
/$8A/$CB (* mov CL, BL *)
/$D3/$C8 (* ror AX, CL *)
/$31/$D8 (* xor AX, BX *)
/$4A (* dec DX *)
/$75/$E5 (* jnz Cycle *)
(* Exit1: *)
/$2B/$9A/Key (* sub BX, [BP+Key][SI] *)
/$4E (* dec SI *)
/$4E (* dec SI *)
/$2B/$82/Key (* sub AX, [BP+Key][SI] *)
/$C4/$B6/Y (* les SI, [BP+Y] *)
/$26/$89/$04 (* mov ES:[SI], AX *)
/$C4/$B6/Z (* les SI, [BP+Z] *)
/$26/$89/$1C (* mov ES:[SI], BX *)
(* Exit2: *)
);
Exit
end; (* Decrypt *)
(*-------------------------------------------------------------*)
Эмулировать 32-разрядные операции 16-разрядной арифметикой, конечно, можно, но при этом
теряется главное достоинство RC5, именно, его быстродействие. Если же отказаться от
эмуляции, то программы не смогут работать на 16-разрядных ПЭВМ.
Статьи подобного рода принято заканчивать [3] ссылками на указ Президента РФ Ельцина Б.Н. от
03.04.95, который запрещает "деятельность юридических и физических лиц, связанную с
разработкой, производством, реализацией и эксплуатацией шифровальных средств без
лицензий, выданных ФАПСИ".
Вместе с тем, авторы [2] системы "Кобра", сами немало натерпевшиеся от этого ФАПСИ, ссылаясь
на примеры из [1], убеждены, что запретительные меры не способны сдержать рост
компьютерных преступлений, а "владение основами криптографии в информационном обществе
не может быть привилегией отдельных государственных служб". Примеры из [4] существенно
дополняют сказанное. Остаётся только заметить, что любое информационное общество, будь то
социалистического или капиталистического окраса, изначально обречено, если основанно на
несправедливости, лжи, лицемерии или насилии (хотя бы и в яркой демократической упаковке),
и не поможет тут никакая криптография...
Литература:
1. Жельников В. Криптография от папируса до компьютера. — М.: ABF, 1966 г., 335 с.
2. Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. — С.-Пб: "Лань", 2001 г., 224 с.
3. Беляев А. Криптография. Общая классификация, блочные шифры. // Журнал "Программист", 2001, № 4, с. 78—81.
4. Бёрд Киви. Гигабайты власти. — М.: "Бестселлер", 2004 г., 352 с.
:: на начало ::
Главная
