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. Вход: параметра размера , такой что . Выход: пара открытый/закрытый ключ. Сгенерировать случайное простое число , такое что . Сгенерировать случайное простое число , , такое что . Сгенерировать случайное целое число , такое что . Сгенерировать случайные целые числа и Вычислить следующие целые числа в :,,,,. Сгенерировать случайные байтовые строки и , где и . Вернуть пару открытый/закрытый ключ
Представление шифротекста Шифротекст в схеме шифрования ACE имеет вид , где компоненты определяются следующим образом: — целые числа из (чей мультипликативный порядок по модулю делит ). — элемент . — элемент . назовём преамбулой, а — криптограммой. Если текст — строка из байт, то тогда длина равна . Необходимо ввести функцию , которая представляет шифротекст в виде байтовой строки, а также обратную функцию . Для целого , символьной строки , целых , и байтовой строки ,. Для целого , байтовой строки , для которой ,.
Процесс шифрования Алгоритм. Асимметричный процесс шифрования ACE. Вход: открытый ключ и байтовая строка . Выход: байтовая строка — шифротекст , полученный из . Сгенерировать случайное . Сгенерировать преамбулу шифротекста: Сгенерировать . Вычислить , . Вычислить ; заметим, что . Вычислить . Вычислить ключ для операции симметричного шифрования: , . Вычислить . Вычислить криптограмму . Закодировать шифротекст:. Вернуть . Перед запуском процесса симметричного шифрования входное сообщение разбивается на блоки , где каждый блок кроме, возможно, последнего имеет 1024 байт. Каждый блок шифруется потоковым шифратором. Для каждого зашифрованного блока вычисляется 16-байтовый код аутентификации. Получаем криптограмму.. Заметим, что если , то . Алгоритм. Симметричный процесс шифрования ACE. Вход: Выход: , . Если , тогда вернуть . Проинициализировать генератор псевдо-случайных чисел:
Сгенерировать ключ : . . Пока , выполнять следующее: . Сгенерировать значения масок для шифрования и MAC: . . Зашифровать текст: . Сгенерировать аутентификационный код сообщения: Если , тогда ; иначе . . Обновить шифротекст: . . Вернуть .
Процесс дешифрования Алгоритм. Процесс дешифрования ACE. Вход: открытый ключ и соответствующий закрытый ключ , байтовая строка . Выход: Расшифрованное сообщение . Дешифровать шифротекст: Если , тогда вернуть . Вычислить:;заметим, что , где . Подтвердить преамбулу шифротекста: Если или или , тогда вернуть . Если , тогда вернуть . . Если , тогда . Вычислить ; заметим, что . Если , тогда . Если , тогда вернуть . Вычислить ключ для процесс симметричного дешифрования: , . Вычислить . Вычислить ;заметим, что может вернуть . Вернуть . Алгоритм. Операция дешифрования . Вход: Выход: Расшифрованное сообщение . Если , тогда вернуть . Проинициализировать генератор псевдо-случайных чисел: Сгенерировать ключ :. . Пока , выполнять следующее: . Если , тогда вернуть . Сгенерировать значения масок для шифрования и MAC: . . Подтвердить аутентификационный код сообщения: Если , тогда ; иначе . . Если , тогда вернуть . Обновить текст: . . Вернуть .
Схема цифровой подписи В схеме цифровой подписи ACE задействованы два типа ключей: открытый ключ цифровой подписи ACE: . закрытый ключ цифровой подписи ACE: . Для заданного параметра размера , такого что , компоненты ключей определяются следующим образом: — -битное простое число, для которого — тоже простое. — -битное простое число, для которого — тоже простое. — и может иметь как , так и бит. — элементы (квадратичные остатки по модулю ). — 161-битное простое число. — элемент — элементы . — элементы .
Генерация ключа Алгоритм. Генерация ключа для схемы цифровой подписи ACE. Вход: параметра размера , такой что . Выход: пара открытый/закрытый ключ. Сгенерировать случайные простые числа , такие что и — тоже простые, и , , и ,где<p style="text-align:center;"> и . Положить . Сгенерировать случайное простое число, где . Сгенерировать случайное , при условии и , и вычислить . Сгенерировать случайное и вычислить . Сгенерировать случайные байтовые строки , и . Вернуть пару открытый ключ/закрытый ключ.
Представление подписи Подпись в схеме цифровой подписи ACE имеет вид , где компоненты определяются следующим образом: — элемент . — целое число, такое что . — элементы . — элемент ;заметим, что , где — подписываемое сообщение. Необходимо ввести функцию , которая представляет подпись в виде байтовой строки, а также обратную функцию . Для целого , байтовой строки , целых и , и байтовой строки ,. Для целого , байтовой строки , для которой ,.
Процесс генерирования подписи Алгоритм. Генерирование цифровой подписи ACE. Вход: открытый ключ и соответствующий закрытый ключ и байтовая строка , . Выход: байтовая строка — цифровая подпись . Произвести следующие действия для хеширования входных данных: Сгенерировать случайно ключ хеша , такой что . Вычислить . Выбрать случайное , и вычислить . Вычислить . Сгенерировать случайное простое число , , и его подтверждение корректности : . Повторять этот шаг до тех пор, когда . Положить ; заметим, что . Вычислить , где,и где и . Закодировать подпись: <p style="text-align:center;">.
Замечания В схемах шифрования и цифровой подписи ACE используются некоторые вспомогательные функции(такие как, например, UOWHash,ESHash и другие), описание которых выходит за рамки данной статьи. Подробнее о данных функциях можно найти в.
Реализация, применение и производительность Схема шифрования 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
Литература
Ссылки http://www.alphaworks.ibm.com/tech/ace http://www.zurich.ibm.com/security/ace/ NESSIE Portfolio of recommended cryptographic primitives
Категория:Криптографическое программное обеспечение