CAST-128

CAST-128 (или CAST5) в криптографии — блочный алгоритм симметричного шифрования на основе сети Фейстеля, который используется в целом ряде продуктов криптографической защиты, в частности некоторых версиях PGP и GPG и кроме того одобрен для использования Канадским правительством.

Основные сведения

Алгоритм был создан в 1996 году Карлайлом Адамсом (Carlisle Adams) и Стаффордом Таваресом (Stafford Tavares) используя метод построения шифров CAST, который используется также и другим их алгоритмом CAST-256 (алгоритм-кандидат AES).

CAST-128 состоит из 12 или 16 раундов сети Фейстеля с размером блока 64 бита и длиной ключа от 40 до 128 бит (но только с инкрементацией по 8 бит). 16 раундов используются когда размеры ключа превышают 80 бит. В алгоритме используются 8x16 S- блоки, основанные на бент-функции, операции XOR и модулярной арифметике (модулярное сложение и вычитание). Есть три различных типа функций раундов, но они похожи по структуре и различаются только в выборе выполняемой операции (сложение, вычитание или XOR) в различных местах.

Хотя CAST-128 защищён патентом Entrust, его можно использовать во всём мире для коммерческих или некоммерческих целей бесплатно.

Описание

CAST — это популярный 64-битовый шифр, допускающий размеры ключа вплоть до 128 бит, который был разработан в Канаде Карлайлом Адамсом (Carlisle Adams) и Стаффордом Таваресом (Stafford Tavares). Авторы утверждают, что название обусловлено ходом разработки и должно напоминать о вероятностном характере процесса, а не об инициалах авторов.

Алгоритм CAST использует 64-битовый блок и 64-битовый ключ. CAST устойчив к дифференциальному и линейному криптоанализу. Сила алгоритма CAST заключена в его S-блоках. У CAST нет фиксированных S-блоков и для каждого приложения они конструируются заново. Созданный для конкретной реализации CAST S-блок уже больше никогда не меняется. Другими словами, S-блоки зависят от реализации, а не от ключа. Northern Telecom использует CAST в своём пакете программ Entrust для компьютеров Macintosh, PC и рабочих станций UNIX. Выбранные ими S-блоки не опубликованы, что впрочем неудивительно.

CAST-128 принадлежит компании Entrust Technologies, но является бесплатным как для коммерческого, так и для некоммерческого использования. CAST-256 — бесплатное доступное расширение CAST-128, которое принимает размер ключа до 256 бит и имеет размер блока 128 бит. CAST-256 был одним из первоначальных кандидатов на AES.

Описание алгоритма

CAST-128 основан на сети Фейстеля. Полный алгоритм шифрования изложен в следующих четырех шагах:

ВХОД: текст m1 ... m64, ключ K = k1 ... k128. ВЫХОД: зашифрованный текст c1 ... C64.

1. (развертка ключа) составляет 16 пар подключей {Kmi, Kri} полученных из K (см. разделы Пары раундовых ключей и Неидентичные раунды).

2. (L0, R0) <- (m1. .. m64). (Разделяет текст на левую и правую 32-битные половины L0 = m1 ... m32 и R0 = m33 ... m64).

3. (16 раундов) for i from 1 to 16, вычислить Li и Ri следующим образом: Li = Ri-1; Ri = Li-1 ^ F(Ri-1,Kmi,Kri), где F определена в разделе «Пары раундовых ключей» (F имеет тип 1, тип 2, тип 3 или, в зависимости от i).

4. c1 ... c64 <- (R16, L16). (Меняем окончательные блоки местами L16, R16 и объединяем, чтобы сформировать зашифрованный текст.)

Расшифрование совпадает с алгоритмом шифрования, приведенным выше, кроме того, что раунды (и, следовательно, пары подключей), используются в обратном порядке, чтобы вычислить (L0, R0) из (R16, L16).

Пары раундовых ключей

CAST-128 использует пару подключей за раунд: 32-битные величины Km используется в качестве "маскировки" ключа и Kr используют как "перестановки" ключа, из которых используются только начальные 5-бит.

Неидентичные раунды

Три различных типов функции используются в CAST-128. Типы выглядит следующим образом (где "D" является входными данными в функцию F и "Ia"-"Id" является наиболее значимый байт - наименее значимый байт I, соответственно). Обратите внимание, что "+" и "-" сложение и вычитание по модулю 2 ** 32, "^" является побитовое XOR и "<<<" является циклическим сдвигом влево.

Поля замены

CAST-128 использует восемь полей замены: поля S1, S2, S3 и S4 раундовые функции полей замены, S5, S6, S7 и S8 являются ключами развертки полей замены. Несмотря на то, что 8 полей замены требуют в общей сложности 8 Кбайт для хранения, обратите внимание на то, что только 4 Кбайта требуются во время фактического шифрования / дешифрование, так как генерация подключа обычно делается до любого ввода данных. См. Приложение для содержимого полей замены S1 - S8.

Ключи развертки

Представим 128-разрядный ключ в виде x0x1x2x3x4x5x6x7x8x9xAxBxCxDxExF, где x0 старший байт, и xF младший байт.

Представим z0..zF промежуточными (временными) байтами. Si[] представляет поле замены i и "^" представляет сложение по XOR’у.

Поля замены формируются из ключа x0x1x2x3x4x5x6x7x8x9xAxBxCxDxExF следующим образом.

z0z1z2z3 = x0x1x2x3 ^ S5[xD] ^ S6[xf] ^ S7[xC] ^ S8[xE] ^ S7[x8] z4z5z6z7 = x8x9xAxB ^ S5[z0] ^ S6[z2] ^ S7[z1] ^ S8[z3] ^ S8[xA] z8z9zAzB = xCxDxExF ^ S5[z7] ^ S6[z6] ^ S7[z5] ^ S8[z4] ^ S5[x9] zCzDzEzF = x4x5x6x7 ^ S5[zA] ^ S6[z9] ^ S7[zB] ^ S8[z8] ^ S6[xB] K1 = S5[z8] ^ S6[z9] ^ S7[z7] ^ S8[z6] ^ S5[z2] K2 = S5[zA] ^ S6[zB] ^ S7[z5] ^ S8[z4] ^ S6[z6] K3 = S5[zC] ^ S6[zD] ^ S7[z3] ^ S8[z2] ^ S7[z9] K4 = S5[zE] ^ S6[zF] ^ S7[z1] ^ S8[z0] ^ S8[zC] x0x1x2x3 = z8z9zAzB ^ S5[z5] ^ S6[z7] ^ S7[z4] ^ S8[z6] ^ S7[z0] x4x5x6x7 = z0z1z2z3 ^ S5[x0] ^ S6[x2] ^ S7[x1] ^ S8[x3] ^ S8[z2] x8x9xAxB = z4z5z6z7 ^ S5[x7] ^ S6[x6] ^ S7[x5] ^ S8[x4] ^ S5[z1] xCxDxExF = zCzDzEzF ^ S5[xA] ^ S6[x9] ^ S7[xB] ^ S8[x8] ^ S6[z3] K5 = S5[x3] ^ S6[x2] ^ S7[xC] ^ S8[xD] ^ S5[x8] K6 = S5[x1] ^ S6[x0] ^ S7[xE] ^ S8[xf] ^ S6[xD] K7 = S5[x7] ^ S6[x6] ^ S7[x8] ^ S8[x9] ^ S7[x3] K8 = S5[x5] ^ S6[x4] ^ S7[xA] ^ S8[xB] ^ S8[x7] z0z1z2z3 = x0x1x2x3 ^ S5[xD] ^ S6[xf] ^ S7[xC] ^ S8[xE] ^ S7[x8] z4z5z6z7 = x8x9xAxB ^ S5[z0] ^ S6[z2] ^ S7[z1] ^ S8[z3] ^ S8[xA] z8z9zAzB = xCxDxExF ^ S5[z7] ^ S6[z6] ^ S7[z5] ^ S8[z4] ^ S5[x9] zCzDzEzF = x4x5x6x7 ^ S5[zA] ^ S6[z9] ^ S7[zB] ^ S8[z8] ^ S6[xB] K9 = S5[z3] ^ S6[z2] ^ S7[zC] ^ S8[zD] ^ S5[z9] K10 = S5[z1] ^ S6[z0] ^ S7[zE] ^ S8[zF] ^ S6[zC] K11 = S5[z7] ^ S6[z6] ^ S7[z8] ^ S8[z9] ^ S7[z2] K12 = S5[z5] ^ S6[z4] ^ S7[zA] ^ S8[zB] ^ S8[z6] x0x1x2x3 = z8z9zAzB ^ S5[z5] ^ S6[z7] ^ S7[z4] ^ S8[z6] ^ S7[z0] x4x5x6x7 = z0z1z2z3 ^ S5[x0] ^ S6[x2] ^ S7[x1] ^ S8[x3] ^ S8[z2] x8x9xAxB = z4z5z6z7 ^ S5[x7] ^ S6[x6] ^ S7[x5] ^ S8[x4] ^ S5[z1] xCxDxExF = zCzDzEzF ^ S5[xA] ^ S6[x9] ^ S7[xB] ^ S8[x8] ^ S6[z3] K13 = S5[x8] ^ S6[x9] ^ S7[x7] ^ S8[x6] ^ S5[x3] K14 = S5[xA] ^ S6[xB] ^ S7[x5] ^ S8[x4] ^ S6[x7] K15 = S5[xC] ^ S6[xD] ^ S7[x3] ^ S8[x2] ^ S7[x8] K16 = S5[xE] ^ S6[xf] ^ S7[x1] ^ S8[x0] ^ S8[xD]

Остающаяся половина идентична тому, что дано выше, продолжение от последнего создало x0..xF, чтобы генерировать ключи K17 - K32.

z0z1z2z3 = x0x1x2x3 ^ S5[xD] ^ S6[xf] ^ S7[xC] ^ S8[xE] ^ S7[x8] z4z5z6z7 = x8x9xAxB ^ S5[z0] ^ S6[z2] ^ S7[z1] ^ S8[z3] ^ S8[xA] z8z9zAzB = xCxDxExF ^ S5[z7] ^ S6[z6] ^ S7[z5] ^ S8[z4] ^ S5[x9] zCzDzEzF = x4x5x6x7 ^ S5[zA] ^ S6[z9] ^ S7[zB] ^ S8[z8] ^ S6[xB] K17 = S5[z8] ^ S6[z9] ^ S7[z7] ^ S8[z6] ^ S5[z2] K18 = S5[zA] ^ S6[zB] ^ S7[z5] ^ S8[z4] ^ S6[z6] K19 = S5[zC] ^ S6[zD] ^ S7[z3] ^ S8[z2] ^ S7[z9] K20 = S5[zE] ^ S6[zF] ^ S7[z1] ^ S8[z0] ^ S8[zC] x0x1x2x3 = z8z9zAzB ^ S5[z5] ^ S6[z7] ^ S7[z4] ^ S8[z6] ^ S7[z0] x4x5x6x7 = z0z1z2z3 ^ S5[x0] ^ S6[x2] ^ S7[x1] ^ S8[x3] ^ S8[z2] x8x9xAxB = z4z5z6z7 ^ S5[x7] ^ S6[x6] ^ S7[x5] ^ S8[x4] ^ S5[z1] xCxDxExF = zCzDzEzF ^ S5[xA] ^ S6[x9] ^ S7[xB] ^ S8[x8] ^ S6[z3] K21 = S5[x3] ^ S6[x2] ^ S7[xC] ^ S8[xD] ^ S5[x8] K22 = S5[x1] ^ S6[x0] ^ S7[xE] ^ S8[xf] ^ S6[xD] K23 = S5[x7] ^ S6[x6] ^ S7[x8] ^ S8[x9] ^ S7[x3] K24 = S5[x5] ^ S6[x4] ^ S7[xA] ^ S8[xB] ^ S8[x7] z0z1z2z3 = x0x1x2x3 ^ S5[xD] ^ S6[xf] ^ S7[xC] ^ S8[xE] ^ S7[x8] z4z5z6z7 = x8x9xAxB ^ S5[z0] ^ S6[z2] ^ S7[z1] ^ S8[z3] ^ S8[xA] z8z9zAzB = xCxDxExF ^ S5[z7] ^ S6[z6] ^ S7[z5] ^ S8[z4] ^ S5[x9] zCzDzEzF = x4x5x6x7 ^ S5[zA] ^ S6[z9] ^ S7[zB] ^ S8[z8] ^ S6[xB] K25 = S5[z3] ^ S6[z2] ^ S7[zC] ^ S8[zD] ^ S5[z9] K26 = S5[z1] ^ S6[z0] ^ S7[zE] ^ S8[zF] ^ S6[zC] K27 = S5[z7] ^ S6[z6] ^ S7[z8] ^ S8[z9] ^ S7[z2] K28 = S5[z5] ^ S6[z4] ^ S7[zA] ^ S8[zB] ^ S8[z6] x0x1x2x3 = z8z9zAzB ^ S5[z5] ^ S6[z7] ^ S7[z4] ^ S8[z6] ^ S7[z0] x4x5x6x7 = z0z1z2z3 ^ S5[x0] ^ S6[x2] ^ S7[x1] ^ S8[x3] ^ S8[z2] x8x9xAxB = z4z5z6z7 ^ S5[x7] ^ S6[x6] ^ S7[x5] ^ S8[x4] ^ S5[z1] xCxDxExF = zCzDzEzF ^ S5[xA] ^ S6[x9] ^ S7[xB] ^ S8[x8] ^ S6[z3] K29 = S5[x8] ^ S6[x9] ^ S7[x7] ^ S8[x6] ^ S5[x3] K30 = S5[xA] ^ S6[xB] ^ S7[x5] ^ S8[x4] ^ S6[x7] K31 = S5[xC] ^ S6[xD] ^ S7[x3] ^ S8[x2] ^ S7[x8] K32 = S5[xE] ^ S6[xf] ^ S7[x1] ^ S8[x0] ^ S8[xD]

Маскировка и перестановка подключей

Km1, ..., Km16 32-разрядные подключи маскировки (один на раунд). Kr1,, Kr16 32-разрядные перестановки подключей (один на раунд); только младшие 5 битов используются в каждом раунде.

for (i=1; i<=16; i++) { Kmi = Ki; Kri = K16+i; }

Переменный размер ключа

CAST-128 Алгоритм шифрования был разработан, чтобы размер ключа мог варьироваться от 40 до 128 бит, в 8-битном шаге (т. е. допустимые размеры ключа равняются 40, 48, 56, 64..., 112, 120, и 128 битам). Для переменной работы размера ключа спецификация следующие:

1) Для размеров ключа до и включая 80 битов (т. е., 40, 48, 56, 64, 72, и 80 битов) алгоритм точно такой же, но использует 12 раундов вместо 16;

2) Для размеров ключа больше, чем 80 битов, алгоритм использует полные 16 раундов;

3) Для размеров ключа меньше, чем 128 битов ключ дополнен нулевыми байтами (в самых правых, или младших, позициях) к 128 битам (так как расписание ключа CAST 128 принимает входной ключ 128 битов).

Приложение: Поля замены

S-Box S1

S1

S-Box S2

S2

S-Box S3

S3

S-Box S4

S4

S-Box S5

S5

S-Box S6

S6

S-Box S7

S7

S-Box S8

S8

Расшифрование

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