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 года.

Ссылки

править