CAST-128

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
CAST-128
Создатель:

Карлайл Адамс, Стаффорд Таварес

Размер ключа:

40-128 бит

Размер блока:

64 бит

Число раундов:

12 (16 при ключе > 80 бит)

Тип:

Сеть Фейстеля

CAST-128-large.png

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.


Раздел 1: Описание алгоритма[править | править вики-текст]

Cast-128(1).png

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

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

1. (развертка ключа) составляет 16 пар подключей {Kmi, Kri} полученных из K (см. разделы 2 и 6). 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 определена в разделе 2.2 (F имеет тип 1, тип 2, тип 3 или, в зависимости от i). 4. c1 ... c64 <- (R16, L16). (Меняем окончательные блоки местами L16, R16 и объединяем, чтобы сформировать зашифрованный текст.)

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

Раздел 2: Пары раундовых ключей[править | править вики-текст]

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

Раздел 3: Неидентичные раунды[править | править вики-текст]

Рис.2 Исходная функция F

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


Раунды
1,4,7,10,13,16
I = ((Kmi + Ri-1) <<< Kri)
F = ((S1[Ia] ^ S2[Ib]) – (S3[Ic]) )+ S4[Id]
Раунды
2,5,8,11,14
I = ((Kmi ^ Ri-1) <<< Kri)
F = ((S1[Ia] - S2[Ib]) + (S3[Ic])) ^ S4[Id]
Раунды
3,6,9,12,15
I = ((Kmi - Ri-1) <<< Kri)
F = ((S1[Ia] + S2[Ib]) ^ (S3[Ic]) )- S4[Id]

Раздел 4: Поля замены[править | править вики-текст]

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

Раздел 5: Ключи развертки[править | править вики-текст]

Представим 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]

Раздел 6: Маскировка подключей и перестановка подключей[править | править вики-текст]

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

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

Раздел 7: Переменный размер ключа[править | править вики-текст]

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

S-Box S2

S-Box S3

S-Box S4

S-Box S5

S-Box S6

S-Box S7

S-Box S8

Расшифрование[править | править вики-текст]

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

Ссылки[править | править вики-текст]