ACE Encrypt (ACE Encrypt)

Перейти к навигации Перейти к поиску

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.
Вход: параметра размера , такой что .
Выход: пара открытый/закрытый ключ.

  1. Сгенерировать случайное простое число , такое что .
  2. Сгенерировать случайное простое число , , такое что .
  3. Сгенерировать случайное целое число , такое что .
  4. Сгенерировать случайные целые числа и
  5. Вычислить следующие целые числа в :

    ,


    ,


    ,


    ,


    .

  6. Сгенерировать случайные байтовые строки и , где и .
  7. Вернуть пару открытый/закрытый ключ

Представление шифротекста

[править | править код]

Шифротекст в схеме шифрования ACE имеет вид

,


где компоненты определяются следующим образом:
 — целые числа из (чей мультипликативный порядок по модулю делит ).
 — элемент .
 — элемент .
назовём преамбулой, а  — криптограммой. Если текст — строка из байт, то тогда длина равна .

Необходимо ввести функцию , которая представляет шифротекст в виде байтовой строки, а также обратную функцию . Для целого , символьной строки , целых , и байтовой строки ,

.


Для целого , байтовой строки , для которой ,

.

Процесс шифрования

[править | править код]

Алгоритм. Асимметричный процесс шифрования ACE.
Вход: открытый ключ и байтовая строка .
Выход: байтовая строка — шифротекст , полученный из .

  1. Сгенерировать случайное .
  2. Сгенерировать преамбулу шифротекста:
    1. Сгенерировать .
    2. Вычислить , .
    3. Вычислить ; заметим, что .
    4. Вычислить .
  3. Вычислить ключ для операции симметричного шифрования:
    1. , .
    2. Вычислить .
  4. Вычислить криптограмму .
  5. Закодировать шифротекст:

    .

  6. Вернуть .

Перед запуском процесса симметричного шифрования входное сообщение разбивается на блоки , где каждый блок кроме, возможно, последнего имеет 1024 байт. Каждый блок шифруется потоковым шифратором. Для каждого зашифрованного блока вычисляется 16-байтовый код аутентификации. Получаем криптограмму

.

. Заметим, что если , то .

Алгоритм. Симметричный процесс шифрования ACE.
Вход:
Выход: , .

  1. Если , тогда вернуть .
  2. Проинициализировать генератор псевдо-случайных чисел:

  1. Сгенерировать ключ :

.

  1. .
  2. Пока , выполнять следующее:
    1. .
    2. Сгенерировать значения масок для шифрования и MAC:
      1. .
      2. .
    3. Зашифровать текст: .
    4. Сгенерировать аутентификационный код сообщения:
      1. Если , тогда ; иначе .
      2. .
    5. Обновить шифротекст: .
    6. .
  3. Вернуть .

Процесс дешифрования

[править | править код]

Алгоритм. Процесс дешифрования ACE.
Вход: открытый ключ и соответствующий закрытый ключ , байтовая строка .
Выход: Расшифрованное сообщение .

  1. Дешифровать шифротекст:
    1. Если , тогда вернуть .
    2. Вычислить:

      ;


      заметим, что , где .
  2. Подтвердить преамбулу шифротекста:
    1. Если или или , тогда вернуть .
    2. Если , тогда вернуть .
    3. .
    4. Если , тогда .
    5. Вычислить ; заметим, что .
    6. Если , тогда .
    7. Если , тогда вернуть .
  3. Вычислить ключ для процесс симметричного дешифрования:
    1. , .
    2. Вычислить .
  4. Вычислить ;заметим, что может вернуть .
  5. Вернуть .

Алгоритм. Операция дешифрования .
Вход:
Выход: Расшифрованное сообщение .

  1. Если , тогда вернуть .
  2. Проинициализировать генератор псевдо-случайных чисел:

  3. Сгенерировать ключ :

    .

  4. .
  5. Пока , выполнять следующее:
    1. .
    2. Если , тогда вернуть .
    3. Сгенерировать значения масок для шифрования и MAC:
      1. .
      2. .
    4. Подтвердить аутентификационный код сообщения:
      1. Если , тогда ; иначе .
      2. .
      3. Если , тогда вернуть .
    5. Обновить текст: .
    6. .
  6. Вернуть .

В схеме цифровой подписи ACE задействованы два типа ключей:
открытый ключ цифровой подписи ACE: .
закрытый ключ цифровой подписи ACE: .
Для заданного параметра размера , такого что , компоненты ключей определяются следующим образом:
 — -битное простое число, для которого  — тоже простое.
 — -битное простое число, для которого  — тоже простое.
 — и может иметь как , так и бит.
 — элементы (квадратичные остатки по модулю ).
 — 161-битное простое число.
 — элемент
 — элементы .
 — элементы .

Алгоритм. Генерация ключа для схемы цифровой подписи ACE.
Вход: параметра размера , такой что .
Выход: пара открытый/закрытый ключ.

  1. Сгенерировать случайные простые числа , такие что и  — тоже простые, и

    , , и ,


    где

    и .

  2. Положить .
  3. Сгенерировать случайное простое число, где .
  4. Сгенерировать случайное , при условии и , и вычислить .
  5. Сгенерировать случайное и вычислить .
  6. Сгенерировать случайные байтовые строки , и .
  7. Вернуть пару открытый ключ/закрытый ключ

    .

Представление подписи

[править | править код]

Подпись в схеме цифровой подписи ACE имеет вид , где компоненты определяются следующим образом:
 — элемент .
 — целое число, такое что .
 — элементы .
 — элемент ;заметим, что , где  — подписываемое сообщение.

Необходимо ввести функцию , которая представляет подпись в виде байтовой строки, а также обратную функцию . Для целого , байтовой строки , целых и , и байтовой строки ,

.


Для целого , байтовой строки , для которой ,

.

Процесс генерирования подписи

[править | править код]

Алгоритм. Генерирование цифровой подписи ACE.
Вход: открытый ключ и соответствующий закрытый ключ и байтовая строка , .
Выход: байтовая строка — цифровая подпись .

  1. Произвести следующие действия для хеширования входных данных:
    1. Сгенерировать случайно ключ хеша , такой что .
    2. Вычислить .
  2. Выбрать случайное , и вычислить .
  3. Вычислить .
  4. Сгенерировать случайное простое число , , и его подтверждение корректности : . Повторять этот шаг до тех пор, когда .
  5. Положить ; заметим, что .
  6. Вычислить , где

    ,


    и где и .
  7. Закодировать подпись:

    .

В схемах шифрования и цифровой подписи 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

Литература

[править | править код]
  1. ACE: The Advanced Cryptographic Engine, T. Schweinberger and V. Shoup, manuscript 2000. Дата обращения: 17 декабря 2010. Архивировано 28 июля 2011 года.