ACE (Advanced Cryptographic Engine) — набор программных средств, реализующих шифрование в режиме схемы шифрования с открытым ключом, а также в режиме цифровой подписи. Соответствующие названия этих режимов — «ACE Encrypt» и «ACE Sign». Схемы являются вариантами реализации схем Крамера-Шоупа. Внесённые изменения нацелены на достижение наилучшего баланса между производительностью и безопасностью всей системы шифрования.
Все алгоритмы, написанные в ACE, основаны на алгоритмах, разработанных Виктором Шоупом(Victor Shoup) и Рональдом Крамером (Ronald Cramer). Полная спецификация алгоритмов написана Виктором Шоупом. Реализация алгоритмов выполнена Томасом Швейнбергером(Thomas Schweinberger) и Медди Нассей (Mehdi Nassehi), их поддержкой и развитием занимается Виктор Шоуп. Томас Швейнберг принимал участие в составлении документа спецификаций ACE, а также написал руководство пользователя.
Рональд Крамер в настоящее время находится в университете Орхуса, Дания. Он принимал участие в работе, относящейся к ACE Encrypt пока находился в ETH в Цюрихе, Швейцария.
Медди Нассей и Томасом Швейнбергер работали над проектом ACE в исследовательской лаборатории IBM в Цюрихе, Швейцария, но в настоящее время закончили своё пребывание там.
Виктор Шоуп работает в исследовательской лаборатории IBM в Цюрихе, Швейцария.
Доказательство безопасности схемы шифрования и схемы цифровой подписи в ACE проводится с использованием обоснованных и естественных допущений.
Четырьмя основными допущениями являются:
- Допущение Диффи-Хеллмана
- Сильное допущение RSA
- Стойкость к коллизиям на второй прообраз в SHA-1
- Псевдо-случайность режима сумматора/счётчика MARS
Приведём определения некоторых обозначений и терминов, используемых в данной статье.
— множество целых чисел.
— множество одномерных полиномов с коэффициентами в конечном поле
с числом элементов поля — 2.
— такое целое число
, для которого
при целом
и
.
— такой полином
с
, такой что
при
.
— множество всевозможных строк.
— множество всевозможных строк длины n.
Для
— длина строки
. Обозначения для длины нулевой строки —
.
Для
— результат конкатенации строк
и
.
— множество битов.
Рассмотрим множества вида
. Для такого множества A определим нулевой элемент:
;
для
.
Определим
как множество байтов, а
как множество слов.
Для
с
и
определим оператор заполнения:
.
Оператор преобразования
выполняет преобразования между элементами
.
В схеме шифрования ACE задействованы два типа ключей:
открытый ключ ACE:
.
закрытый ключ ACE:
.
Для заданного параметра размера
, такого что
, компоненты ключей определяются следующим образом:
— 256-битное простое число.
— m-битное простое число, такое что
.
— элементы
(чей мультипликативный порядок по модулю
делит
).
— элементы
.
— элементы
, для которых
и
, где
и
.
Алгоритм. Генерация ключа для схемы шифрования ACE.
Вход: параметра размера
, такой что
.
Выход: пара открытый/закрытый ключ.
- Сгенерировать случайное простое число
, такое что
.
- Сгенерировать случайное простое число
,
, такое что
.
- Сгенерировать случайное целое число
, такое что
.
- Сгенерировать случайные целые числа
и ![{\displaystyle x,y,z_{1},z_{2}\in \left\{0,...,q-1\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a6144e93551d0fb8a321a62c9ca1984470e3f7e)
- Вычислить следующие целые числа в
:
,
,
,
,
.
- Сгенерировать случайные байтовые строки
и
, где
и
.
- Вернуть пару открытый/закрытый ключ
![{\displaystyle ((P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2}),(w,x,y,z_{1},z_{2}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc3085b7585e5ba6dc67f90d00ea5361437dfda4)
Шифротекст в схеме шифрования ACE имеет вид
,
где компоненты определяются следующим образом:
— целые числа из
(чей мультипликативный порядок по модулю
делит
).
— элемент
.
— элемент
.
назовём преамбулой, а
— криптограммой. Если текст — строка из
байт, то тогда длина
равна
.
Необходимо ввести функцию
, которая представляет шифротекст в виде байтовой строки, а также обратную функцию
. Для целого
, символьной строки
, целых
, и байтовой строки
,
.
Для целого
, байтовой строки
, для которой
,
.
Алгоритм. Асимметричный процесс шифрования ACE.
Вход: открытый ключ
и байтовая строка
.
Выход: байтовая строка — шифротекст
, полученный из
.
- Сгенерировать случайное
.
- Сгенерировать преамбулу шифротекста:
- Сгенерировать
.
- Вычислить
,
.
- Вычислить
; заметим, что
.
- Вычислить
.
- Вычислить ключ для операции симметричного шифрования:
,
.
- Вычислить
.
- Вычислить криптограмму
.
- Закодировать шифротекст:
.
- Вернуть
.
Перед запуском процесса симметричного шифрования входное сообщение
разбивается на блоки
, где каждый блок кроме, возможно, последнего имеет 1024 байт. Каждый блок шифруется потоковым шифратором. Для каждого зашифрованного блока
вычисляется 16-байтовый код аутентификации. Получаем криптограмму
.
. Заметим, что если
, то
.
Алгоритм. Симметричный процесс шифрования ACE.
Вход:
![{\displaystyle m>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/501173910e6da8425b4e9d44a4e8643620bc2464)
Выход:
,
.
- Если
, тогда вернуть
.
- Проинициализировать генератор псевдо-случайных чисел:
![{\displaystyle genState\leftarrow InitGen(k,s)\in GenState}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02b50aa7b7cb54e4fdbfdbc4504988279ca76f25)
- Сгенерировать ключ
:
.
.
- Пока
, выполнять следующее:
.
- Сгенерировать значения масок для шифрования и MAC:
.
.
- Зашифровать текст:
.
- Сгенерировать аутентификационный код сообщения:
- Если
, тогда
; иначе
.
.
- Обновить шифротекст:
.
.
- Вернуть
.
Алгоритм. Процесс дешифрования ACE.
Вход: открытый ключ
и соответствующий закрытый ключ
, байтовая строка
.
Выход: Расшифрованное сообщение
.
- Дешифровать шифротекст:
- Если
, тогда вернуть
.
- Вычислить:
;
заметим, что
, где
.
- Подтвердить преамбулу шифротекста:
- Если
или
или
, тогда вернуть
.
- Если
, тогда вернуть
.
.
- Если
, тогда
.
- Вычислить
; заметим, что
.
- Если
, тогда
.
- Если
, тогда вернуть
.
- Вычислить ключ для процесс симметричного дешифрования:
,
.
- Вычислить
.
- Вычислить
;заметим, что
может вернуть
.
- Вернуть
.
Алгоритм. Операция дешифрования
.
Вход:
![{\displaystyle m>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/501173910e6da8425b4e9d44a4e8643620bc2464)
Выход: Расшифрованное сообщение
.
- Если
, тогда вернуть
.
- Проинициализировать генератор псевдо-случайных чисел:
![{\displaystyle genState\leftarrow InitGen(k,s)\in GenState}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02b50aa7b7cb54e4fdbfdbc4504988279ca76f25)
- Сгенерировать ключ
:
.
.
- Пока
, выполнять следующее:
.
- Если
, тогда вернуть
.
- Сгенерировать значения масок для шифрования и MAC:
.
.
- Подтвердить аутентификационный код сообщения:
- Если
, тогда
; иначе
.
.
- Если
, тогда вернуть
.
- Обновить текст:
.
.
- Вернуть
.
В схеме цифровой подписи ACE задействованы два типа ключей:
открытый ключ цифровой подписи ACE:
.
закрытый ключ цифровой подписи ACE:
.
Для заданного параметра размера
, такого что
, компоненты ключей определяются следующим образом:
—
-битное простое число, для которого
— тоже простое.
—
-битное простое число, для которого
— тоже простое.
—
и может иметь как
, так и
бит.
— элементы
(квадратичные остатки по модулю
).
— 161-битное простое число.
— элемент ![{\displaystyle \left\{0,...,(p-1)(q-1)/4-1\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e5a8e161e1e1a298ab8d1fc1ef35063fd8c13f)
— элементы
.
— элементы
.
Алгоритм. Генерация ключа для схемы цифровой подписи ACE.
Вход: параметра размера
, такой что
.
Выход: пара открытый/закрытый ключ.
- Сгенерировать случайные простые числа
, такие что
и
— тоже простые, и
,
, и
,
где
и
.
- Положить
.
- Сгенерировать случайное простое число
, где
.
- Сгенерировать случайное
, при условии
и
, и вычислить
.
- Сгенерировать случайное
и вычислить
.
- Сгенерировать случайные байтовые строки
, и
.
- Вернуть пару открытый ключ/закрытый ключ
.
Подпись в схеме цифровой подписи ACE имеет вид
, где компоненты определяются следующим образом:
— элемент
.
— целое число, такое что
.
— элементы
.
— элемент
;заметим, что
, где
— подписываемое сообщение.
Необходимо ввести функцию
, которая представляет подпись в виде байтовой строки, а также обратную функцию
. Для целого
, байтовой строки
, целых
и
, и байтовой строки
,
.
Для целого
, байтовой строки
, для которой
,
.
Алгоритм. Генерирование цифровой подписи ACE.
Вход: открытый ключ
и соответствующий закрытый ключ
и байтовая строка
,
.
Выход: байтовая строка — цифровая подпись
.
- Произвести следующие действия для хеширования входных данных:
- Сгенерировать случайно ключ хеша
, такой что
.
- Вычислить
.
- Выбрать случайное
, и вычислить
.
- Вычислить
.
- Сгенерировать случайное простое число
,
, и его подтверждение корректности
:
. Повторять этот шаг до тех пор, когда
.
- Положить
; заметим, что
.
- Вычислить
, где
,
и где
и
.
- Закодировать подпись:
.
В схемах шифрования и цифровой подписи ACE используются некоторые вспомогательные функции(такие как, например, UOWHash,ESHash и другие), описание которых выходит за рамки данной статьи. Подробнее о данных функциях можно найти в[1].
Схема шифрования ACE рекомендована проектом NESSIE (New European Schemes for Signatures, Integrity and Encryption) как асимметричная схема шифрования. Пресс-релиз датирован февралем 2003.
Обе схемы были реализованы в ANSI C, с использованием пакета GNU GMP. Тесты были проведены на двух платформах: Power PC 604 model 43P под системой AIX и 266 MHz Pentium под системой Windows NT. Таблицы показателей приведены ниже:
Таблица 1. Временные затраты на базовые операции.
|
Power PC
|
Pentium
|
|
Размер операнда(байт)
|
Размер операнда(байт)
|
|
512
|
1024
|
512
|
1024
|
Умножение
|
3.5 * 10^(-5) сек
|
1.0 * 10^(-4) сек
|
4.5 * 10^(-5) сек
|
1.4 * 10^(-4) сек
|
Возведение в квадрат
|
3.3 * 10^(-5) сек
|
1.0 * 10^(-4) сек
|
4.4 * 10^(-5) сек
|
1.4 * 10^(-4) сек
|
Потенцирование
|
1.9 * 10^(-2) сек
|
1.2 * 10^(-1) сек
|
2.6 * 10^(-2) сек
|
1.7 * 10^(-1) сек
|
Таблица 2. Производительность схем шифрования и цифровой подписи.
|
Power PC
|
Pentium
|
|
Постоянные затраты (мсек)
|
МБит/сек
|
Постоянные затраты (мсек)
|
МБит/сек
|
Шифрование
|
160
|
18
|
230
|
16
|
Дешифрование
|
68
|
18
|
97
|
14
|
Подпись
|
48
|
64
|
62
|
52
|
Подпись (начальная установка)
|
29
|
|
41
|
|
Верификация
|
52
|
65
|
73
|
53
|