Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

Qalqan (алгоритм шифрования)

Материал из Циклопедии
Перейти к навигации Перейти к поиску
Qalqan
Создатель:НИЛИБ,
Satbayev university
Создан:2020
Опубликован:2021
Размер ключа:256..1024 бит
Размер блока:128 бит
Число раундов:17..23
Тип:SP-сеть

Qalqan (в переводе с казахского — «щит») — алгоритм симметричного блочного шифрования.

Общая информация[править]

Размер блока составляет 128 битов, размер ключа варьируется от 256 до 1024 битов с шагом 128 битов. В зависимости от длины ключа содержит от 17 до 23 раундов преобразований.

Алгоритм Qalqan разработан коллективом Научно-исследовательской лаборатории информационной безопасности университета им. К. И. Сатпаева (бывш. Казахский политехнический институт им. В. И. Ленина) под руководством к.ф-м.н. Н.А. Сейловой. Впервые представлен широкой публике в ходе конференции РусКрипто-2021[1].

Разработка осуществлена в ходе проекта с грантовым финансированием №АР06851287, её итогом планируется внедрение Qalqan в качестве первого национального стандарта шифрования Республики Казахстан.

Алгоритм построен в соответствии с архитектурой SP-сети, каждый раунд содержит три операции: наложение раундового ключа, нелинейную операцию (задана фиксированной подстановкой) и линейную операцию, кроме последнего раунда, который состоит только из операции наложения ключа.

Идеи при проектировании алгоритма[править]

Каждая из основных операций алгоритма выполняет одну задачу, причём делает это максимально эффективно, но без ущерба быстродействию. Все они созданы на основе хорошо изученных функций и не содержат секретных значений. В соответствии с постулатами К. Шеннона, эти относительно простые операции обеспечивают перемешивание и рассеивание битов обрабатываемого блока и ключа на протяжении нескольких раундов.

В отличие от большинства современных алгоритмов шифрования наложение ключа происходит путём сложения с переносом битов. Только в первом и последнем раунде для этой операции применяется исключающее ИЛИ (XOR). Таким образом ценой достаточно простых операций усложняется взаимная зависимость битов обрабатываемого блока.

Линейная операция также является последовательностью операций сложения по модулю 256 (с переносом битов без выхода за пределы байта). Она сконструирована таким образом, чтобы уже за два раунда обеспечить требуемый лавинный эффект (при изменении одного бита входа каждый бит выхода меняется с вероятностью 0.5).

Подстановка алгоритма Qalqan[править]

В виду наличия серьёзных претензий[2] к секретной внутренней структуре таблиц подстановки алгоритма Кузнечик и хеш-функции Стрибог подстановка алгоритма Qalqan была разработана максимально прозрачным методом. Для этого был выбран подход, аналогичный применённому в алгоритме AES, а именно генерация подстановки по методу, предложенному К. Найберг в 1991 году[3][4]. Константы, используемые при генерации, были изменены с целью достижения более близких к оптимальным значений таких криптографически важных параметров, как снижение максимума дифференциального профиля по сложению и XOR (противодействие дифференциальному анализу), снижение максимума таблицы линейных аппроксимаций (противодействие линейному анализу), высокая алгебраическая степень, максимальное расстояние до класса аффинных преобразований.

Использованные константы легко получить путём реверсивного анализа итоговой подстановки.

В результате основные параметры подстановки приняли следующие значения:

  1. Максимум таблицы линейных аппроксимаций: 32.
  2. Максимум дифференциальной таблицы: 4.
  3. Степень полинома Жегалкина: 7.
  4. Расстояние до класса аффинных функций: 112.

Отдельно авторы предлагают при необходимости использовать собственную подстановку, обладающую не худшими параметрами.

Таблицы подстановки алгоритма шифрования Qalqan
Подстановка фиксирована в следующем виде (в Си-подобном формате):
uint8 sb[256] = {

0xeb, 0x89, 0xdb, 0xcb, 0xf3, 0xf5, 0xfb, 0x90, 0xe6, 0x3d, 0xe5, 0x2e, 0xe3, 0x0b, 0x56, 0xe1,

0x6c, 0x12, 0x80, 0x28, 0xed, 0x22, 0x09, 0x4a, 0xee, 0x27, 0x9b, 0x58, 0x35, 0x57, 0xef, 0x94,

0x29, 0xc0, 0x16, 0x7c, 0x5e, 0x87, 0x0a, 0x7e, 0xe8, 0x11, 0x0e, 0xaf, 0x9a, 0x84, 0x3a, 0x1a,

0x69, 0x71, 0x8c, 0xbc, 0xd2, 0x55, 0x33, 0xd1, 0x85, 0x75, 0xb5, 0x83, 0xe9, 0x50, 0x54, 0xac,

0x8a, 0xd6, 0x7f, 0x1f, 0x14, 0x4e, 0x21, 0x82, 0x30, 0x24, 0xdd, 0x9f, 0x1b, 0x32, 0x20, 0xa8,

0x6a, 0xb0, 0x97, 0x62, 0x19, 0xd8, 0xc8, 0x0c, 0x52, 0x02, 0x5c, 0x43, 0x03, 0x95, 0x13, 0x81,

0xab, 0x77, 0xa6, 0xf2, 0x59, 0x67, 0x41, 0xec, 0x76, 0x98, 0xb4, 0x73, 0x86, 0x9c, 0xf7, 0xcf,

0xdc, 0xba, 0xa4, 0xfd, 0xc4, 0x99, 0xdf, 0xce, 0xea, 0x1c, 0x36, 0xbd, 0x34, 0xd7, 0x49, 0x64,

0x5a, 0x6f, 0x74, 0x01, 0xa0, 0x39, 0x91, 0x00, 0x15, 0x3f, 0x38, 0xb8, 0x8f, 0x26, 0x5f, 0xf8,

0x07, 0xa3, 0x0d, 0xda, 0xf0, 0xe7, 0xd0, 0xd9, 0x93, 0xf6, 0x06, 0x47, 0x0f, 0xa1, 0x4b, 0xc5,

0x2a, 0xff, 0x46, 0x60, 0xd5, 0x1d, 0x2f, 0xa9, 0x92, 0x17, 0x72, 0x8e, 0x7a, 0xaa, 0x18, 0x6e,

0x37, 0x08, 0x1e, 0x63, 0x31, 0xc2, 0xbf, 0xc6, 0x9e, 0x65, 0xd4, 0x3b, 0x96, 0x9d, 0xde, 0x45,

0xca, 0x2d, 0xa5, 0xfe, 0x4d, 0xb9, 0x66, 0xc3, 0xb3, 0xcc, 0xad, 0x61, 0xbe, 0x7b, 0x68, 0x88,

0x25, 0x2b, 0x53, 0x5b, 0x44, 0x40, 0xa7, 0xa2, 0x5d, 0xc9, 0x51, 0xae, 0xe4, 0xc7, 0xf9, 0x78,

0x70, 0xcd, 0x42, 0x4f, 0x4c, 0x3c, 0xe0, 0x3e, 0x7d, 0xb7, 0xd3, 0xb2, 0xf1, 0x8d, 0x79, 0x8b,

0x6b, 0xe2, 0x10, 0x23, 0x04, 0x6d, 0xc1, 0xfc, 0x05, 0xb6, 0xf4, 0x48, 0xbb, 0xb1, 0x2c, 0xfa };

Инверсная подстановка, применяемая при расшифровании:

uint8 isb[256] = {

0x87, 0x83, 0x59, 0x5c, 0xf4, 0xf8, 0x9a, 0x90, 0xb1, 0x16, 0x26, 0x0d, 0x57, 0x92, 0x2a, 0x9c,

0xf2, 0x29, 0x11, 0x5e, 0x44, 0x88, 0x22, 0xa9, 0xae, 0x54, 0x2f, 0x4c, 0x79, 0xa5, 0xb2, 0x43,

0x4e, 0x46, 0x15, 0xf3, 0x49, 0xd0, 0x8d, 0x19, 0x13, 0x20, 0xa0, 0xd1, 0xfe, 0xc1, 0x0b, 0xa6,

0x48, 0xb4, 0x4d, 0x36, 0x7c, 0x1c, 0x7a, 0xb0, 0x8a, 0x85, 0x2e, 0xbb, 0xe5, 0x09, 0xe7, 0x89,

0xd5, 0x66, 0xe2, 0x5b, 0xd4, 0xbf, 0xa2, 0x9b, 0xfb, 0x7e, 0x17, 0x9e, 0xe4, 0xc4, 0x45, 0xe3,

0x3d, 0xda, 0x58, 0xd2, 0x3e, 0x35, 0x0e, 0x1d, 0x1b, 0x64, 0x80, 0xd3, 0x5a, 0xd8, 0x24, 0x8e,

0xa3, 0xcb, 0x53, 0xb3, 0x7f, 0xb9, 0xc6, 0x65, 0xce, 0x30, 0x50, 0xf0, 0x10, 0xf5, 0xaf, 0x81,

0xe0, 0x31, 0xaa, 0x6b, 0x82, 0x39, 0x68, 0x61, 0xdf, 0xee, 0xac, 0xcd, 0x23, 0xe8, 0x27, 0x42,

0x12, 0x5f, 0x47, 0x3b, 0x2d, 0x38, 0x6c, 0x25, 0xcf, 0x01, 0x40, 0xef, 0x32, 0xed, 0xab, 0x8c,

0x07, 0x86, 0xa8, 0x98, 0x1f, 0x5d, 0xbc, 0x52, 0x69, 0x75, 0x2c, 0x1a, 0x6d, 0xbd, 0xb8, 0x4b,

0x84, 0x9d, 0xd7, 0x91, 0x72, 0xc2, 0x62, 0xd6, 0x4f, 0xa7, 0xad, 0x60, 0x3f, 0xca, 0xdb, 0x2b,

0x51, 0xfd, 0xeb, 0xc8, 0x6a, 0x3a, 0xf9, 0xe9, 0x8b, 0xc5, 0x71, 0xfc, 0x33, 0x7b, 0xcc, 0xb6,

0x21, 0xf6, 0xb5, 0xc7, 0x74, 0x9f, 0xb7, 0xdd, 0x56, 0xd9, 0xc0, 0x03, 0xc9, 0xe1, 0x77, 0x6f,

0x96, 0x37, 0x34, 0xea, 0xba, 0xa4, 0x41, 0x7d, 0x55, 0x97, 0x93, 0x02, 0x70, 0x4a, 0xbe, 0x76,

0xe6, 0x0f, 0xf1, 0x0c, 0xdc, 0x0a, 0x08, 0x95, 0x28, 0x3c, 0x78, 0x00, 0x67, 0x14, 0x18, 0x1e,

0x94, 0xec, 0x63, 0x04, 0xfa, 0x05, 0x99, 0x6e, 0x8f, 0xde, 0xff, 0x06, 0xf7, 0x73, 0xc3, 0xa1 };

Линейное преобразование[править]

Линейная функция преобразует входной блок B размером 16 байтов в выходной блок R такого же размера следующим образом (байты пронумерованы от старшего к младшему):

Развёртывание ключа[править]

Для исключения атак, использующих ключевое расписание, в алгоритме Qalqan предприняты следующие меры:

  1. Раундовые ключи невозможно вычислить один из другого.
  2. Отсутствуют классы слабых ключей.
  3. Атакующий, имеющий доступ к узлу развёртывания ключа, может произвольно задать максимум один раундовый ключ.
  4. Высокий лавинный эффект, распространяющий отличие мастер-ключа от раундовых ключей (исключены атаки на связанных ключах).

Помимо этого, доступно разворачивание раундовых ключей на лету.

Механизм развёртывания раундовых ключей использует принцип комбинирующего генератора на базе регистров сдвига. Однако, в отличие от линейных регистров сдвига, данные регистры используют нелинейное преобразование алгоритма Qalqan внутри функции обратной связи.

Байты ключа (начиная с младшего) подаются по очереди в байтовые регистры сдвига L0 и L1, начиная с L0. Регистр L0 имеет длину 17 байтов, L1 – 15 байтов. Таким образом 256-битный ключ, состоящий из байтов заполняет регистры следующим образом:

Обратная связь регистров сдвига задана следующим образом:

Регистры движутся равномерно, на каждом шаге после 17-го значение заносится в байт очередного раундового ключа начиная с младшего.

Для ключей, состоящих из более чем 256 бит, последующие байты в порядке от младших к старшим загружаются в регистры сдвига путём прибавления к функции обратной связи регистров по модулю 256 начиная с регистра L1 после 17-го шага работы регистров.

Криптографическая стойкость[править]

Первичный криптоанализ алгоритма показал его устойчивость к дифференциальному и линейному анализу.

Дифференциальный анализ на 3-раундовый алгоритм позволяет определить ключ с вероятностью , после 4 раунда вероятность составляет .

Линейный анализ требует пар открытых и шифрованных текстов.

По состоянию на сентябрь 2021 года в официальных изданиях какие-либо результаты криптографического анализа не публиковались.

Примечания[править]

  1. Алгоритм шифрования Qalqan (русский) (2021).
  2. Léo Perrin, Aleksei Udovenko Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog (англ.) // IACR Transactions on Symmetric Cryptology. — 2016. — С. 99–124. — ISSN 2519-173X. — DOI:10.13154/tosc.v2016.i2.99-124
  3. https://link.springer.com/content/pdf/10.1007/3-540-46416-6_32.pdf
  4. K. Nyberg Perfect non-linear S-boxes (english) // Advances in Cryptology — EUROCRYPT ’91. — 1991. — С. 378-386.