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

Основные обозначения и терминология

Приведём определения некоторых обозначений и терминов, используемых в данной статье.

Основные математические обозначения

${\displaystyle Z}$ — множество целых чисел.
${\displaystyle F_{2}[T]}$ — множество одномерных полиномов с коэффициентами в конечном поле ${\displaystyle F_{2}}$ с числом элементов поля — 2.
${\displaystyle Aremn}$ — такое целое число ${\displaystyle r\in \left\{0,...,n-1\right\}}$ , для которого ${\displaystyle A\equiv r(modn)}$ при целом ${\displaystyle n>0}$ и ${\displaystyle A\in Z}$ .
${\displaystyle Aremf}$ — такой полином ${\displaystyle r\in F_{2}[T]}$ с ${\displaystyle deg(r)<deg(f)}$ , такой что ${\displaystyle A\equiv r(modf)}$ при ${\displaystyle A,f\in F_{2}[T],f\neq 0}$ .

Основные строковые обозначения

${\displaystyle A^{\ast }}$ — множество всевозможных строк.
${\displaystyle A^{n}}$ — множество всевозможных строк длины n.
Для ${\displaystyle x\in A^{\ast }L(x)}$ — длина строки ${\displaystyle x}$ . Обозначения для длины нулевой строки — ${\displaystyle \lambda _{A}}$ .
Для ${\displaystyle x,y\in A^{\ast }}$ ${\displaystyle x||y}$ — результат конкатенации строк ${\displaystyle x}$ и ${\displaystyle y}$ .

Биты, байты, слова

${\displaystyle b{\stackrel {\mathrm {def} }{=}}\left\{0,1\right\}}$ — множество битов.
Рассмотрим множества вида ${\displaystyle b,b^{n_{1}},(b^{n_{1}})^{n_{2}},...}$ . Для такого множества A определим нулевой элемент:

${\displaystyle 0_{b}{\stackrel {\mathrm {def} }{=}}0\in b}$ ;
${\displaystyle 0_{A^{n}}{\stackrel {\mathrm {def} }{=}}(0_{A},...,0_{A})\in A^{n}}$ для ${\displaystyle n>0}$ .

Определим ${\displaystyle B{\stackrel {\mathrm {def} }{=}}b^{8}}$ как множество байтов, а ${\displaystyle W{\stackrel {\mathrm {def} }{=}}b^{32}}$ как множество слов.

Для ${\displaystyle x\in A^{\ast }}$ с ${\displaystyle A\in \left\{b,B,W\right\}}$ и ${\displaystyle l>0}$ определим оператор заполнения:

${\displaystyle pad_{l}(x){\stackrel {\mathrm {def} }{=}}{\begin{cases}x,&L(x)\geq l\\x||0_{A^{l-L(x)}},&L(x)<l\end{cases}}}$ .

Оператор преобразования

Оператор преобразования ${\displaystyle I_{src}^{dst}:src\rightarrow dst}$ выполняет преобразования между элементами ${\displaystyle Z,F_{2}[T],b^{\ast },B^{\ast },W^{\ast }}$ .

Схема шифрования

Пара ключей шифрования

В схеме шифрования ACE задействованы два типа ключей:
открытый ключ ACE: ${\displaystyle (P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2})}$ .
закрытый ключ ACE: ${\displaystyle (w,x,y,z_{1},z_{2})}$ .
Для заданного параметра размера ${\displaystyle m}$ , такого что ${\displaystyle 1024\leq m\leq 16384}$ , компоненты ключей определяются следующим образом:
${\displaystyle q}$ — 256-битное простое число.
${\displaystyle P}$ — m-битное простое число, такое что ${\displaystyle P\equiv 1(modq)}$ .
${\displaystyle g_{1},g_{2},c,d,h_{1},h_{2}}$ — элементы ${\displaystyle \left\{1,...,P-1\right\}}$ (чей мультипликативный порядок по модулю ${\displaystyle P}$ делит ${\displaystyle q}$ ).
${\displaystyle w,x,y,z_{1},z_{2}}$ — элементы ${\displaystyle \left\{0,...,q-1\right\}}$ .
${\displaystyle k_{1},k_{2}}$ — элементы ${\displaystyle B^{\ast }}$ , для которых ${\displaystyle L(k_{1})=20l^{\prime }+64}$ и ${\displaystyle L(k_{2})=32\left\lceil l/16\right\rceil +40}$ , где ${\displaystyle l=\left\lceil m/8\right\rceil }$ и ${\displaystyle l^{\prime }=L_{b}(\left\lceil (2\left\lceil l/4\right\rceil +4)/16\right\rceil )}$ .

Генерация ключа

Алгоритм. Генерация ключа для схемы шифрования ACE.
Вход: параметра размера ${\displaystyle m}$ , такой что ${\displaystyle 1024\leq m\leq 16384}$ .
Выход: пара открытый/закрытый ключ.

1. Сгенерировать случайное простое число ${\displaystyle q}$ , такое что ${\displaystyle 2^{255}<q<2^{256}}$ .
2. Сгенерировать случайное простое число ${\displaystyle P}$ , ${\displaystyle 2^{m-1}<P<2^{m}}$ , такое что ${\displaystyle P\equiv 1(modq)}$ .
3. Сгенерировать случайное целое число ${\displaystyle g_{1}\in \left\{2,...,P-1\right\}}$ , такое что ${\displaystyle g_{1}^{q}\equiv 1(modP)}$ .
4. Сгенерировать случайные целые числа ${\displaystyle w\in \left\{1,...,q-1\right\}}$ и ${\displaystyle x,y,z_{1},z_{2}\in \left\{0,...,q-1\right\}}$
5. Вычислить следующие целые числа в ${\displaystyle \left\{1,...,P-1\right\}}$ :
   

   ${\displaystyle g_{2}\leftarrow g_{1}^{w}remP}$ ,

   
   

   ${\displaystyle c\leftarrow g_{1}^{x}remP}$ ,

   
   

   ${\displaystyle d\leftarrow g_{1}^{y}remP}$ ,

   
   

   ${\displaystyle h_{1}\leftarrow g_{1}^{z_{1}}remP}$ ,

   
   

   ${\displaystyle h_{2}\leftarrow g_{1}^{z_{2}}remP}$ .

6. Сгенерировать случайные байтовые строки ${\displaystyle k_{1}\in B^{20l^{\prime }+64}}$ и ${\displaystyle k_{2}\in B^{2\left\lceil l/16\right\rceil +40}}$ , где ${\displaystyle l=L_{B}(P)}$ и ${\displaystyle l^{\prime }=L_{B}(\left\lceil (2\left\lceil l/4\right\rceil +4)/16\right\rceil )}$ .
7. Вернуть пару открытый/закрытый ключ
   

   ${\displaystyle ((P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2}),(w,x,y,z_{1},z_{2}))}$

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

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

${\displaystyle (s,u_{1},u_{2},v,e)}$ ,

где компоненты определяются следующим образом:
${\displaystyle u_{1},u_{2},v}$ — целые числа из ${\displaystyle \left\{1,...,P-1\right\}}$ (чей мультипликативный порядок по модулю ${\displaystyle P}$ делит ${\displaystyle q}$ ).
${\displaystyle s}$ — элемент ${\displaystyle W^{4}}$ .
${\displaystyle e}$ — элемент ${\displaystyle B^{\ast }}$ .
${\displaystyle s,u_{1},u_{2},v}$ назовём преамбулой , а ${\displaystyle e}$ — криптограммой . Если текст — строка из ${\displaystyle l}$ байт, то тогда длина ${\displaystyle e}$ равна ${\displaystyle l+16\left\lceil l/1024\right\rceil }$ .

Необходимо ввести функцию ${\displaystyle CEncode}$ , которая представляет шифротекст в виде байтовой строки, а также обратную функцию ${\displaystyle CDecode}$ . Для целого ${\displaystyle l>0}$ , символьной строки ${\displaystyle s\in W^{4}}$ , целых ${\displaystyle 0\leq u_{1},u_{2},v<256^{l}}$ , и байтовой строки ${\displaystyle e\in B^{\ast }}$ ,

${\displaystyle CEncode(l,s,u_{1},u_{2},v,e){\stackrel {\mathrm {def} }{=}}I_{W^{\ast }}^{B^{\ast }}(s)||pad_{l}(I_{Z}^{B^{\ast }}(u_{1}))||pad_{l}(I_{Z}^{B^{\ast }}(u_{2}))||pad_{l}(I_{Z}^{B^{\ast }}(v))||e\in B^{\ast }}$ .

Для целого ${\displaystyle l>0}$ , байтовой строки ${\displaystyle \psi \in B^{\ast }}$ , для которой ${\displaystyle L(\psi )\geq 3l+16}$ ,

${\displaystyle CDecode(l,\psi ){\stackrel {\mathrm {def} }{=}}(I_{B^{\ast }}^{W^{\ast }}({\Bigl [}\psi {\Bigr ]}_{0}^{16}),I_{B^{\ast }}^{Z}({\Bigl [}\psi {\Bigr ]}_{16}^{16+l}),I_{B^{\ast }}^{Z}({\Bigl [}\psi {\Bigr ]}_{16+l}^{16+2l}),I_{B^{\ast }}^{Z}({\Bigl [}\psi {\Bigr ]}_{16+2l}^{16+3l}),{\Bigl [}\psi {\Bigr ]}_{16+3l}^{L(\psi )})\in W^{4}\times Z\times Z\times Z\times B^{\ast }}$ .

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

Алгоритм. Асимметричный процесс шифрования ACE.
Вход: открытый ключ ${\displaystyle (P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2})}$ и байтовая строка ${\displaystyle M\in B^{\ast }}$ .
Выход: байтовая строка — шифротекст ${\displaystyle \psi \ }$ , полученный из ${\displaystyle M}$ .

1. Сгенерировать случайное ${\displaystyle r\in \left\{0,...,q-1\right\}}$ .
2. Сгенерировать преамбулу шифротекста:
   1. Сгенерировать ${\displaystyle s\in W^{4}}$ .
   2. Вычислить ${\displaystyle u_{1}\leftarrow g_{1}^{r}remP}$ , ${\displaystyle u_{2}\leftarrow g_{2}^{r}remP}$ .
   3. Вычислить ${\displaystyle \alpha \ \leftarrow UOWHash^{\prime }(k_{1},L_{B}(P),s,u_{1},u_{2})\in Z}$ ; заметим, что ${\displaystyle 0<\alpha \ <2^{160}}$ .
   4. Вычислить ${\displaystyle v\leftarrow c^{r}d^{\alpha \ r}remP}$ .
3. Вычислить ключ для операции симметричного шифрования:
   1. ${\displaystyle {\tilde {h_{1}}}\leftarrow h_{1}^{r}remP}$ , ${\displaystyle {\tilde {h_{2}}}\leftarrow h_{2}^{r}remP}$ .
   2. Вычислить ${\displaystyle k\leftarrow ESHash(k,L_{B}(P),s,u_{1},u_{2},{\tilde {h_{1}}},{\tilde {h_{2}}})\in W^{8}}$ .
4. Вычислить криптограмму ${\displaystyle e\leftarrow SEnc(k,s,1024,M)}$ .
5. Закодировать шифротекст:
   

   ${\displaystyle \psi \ \leftarrow CEncode(L_{B}(P),s,u_{1},u_{2},v,e)}$ .

6. Вернуть ${\displaystyle \psi \ }$ .

Перед запуском процесса симметричного шифрования входное сообщение ${\displaystyle M\in B^{\ast }}$ разбивается на блоки ${\displaystyle M_{1},...,M_{t}}$ , где каждый блок кроме, возможно, последнего имеет 1024 байт. Каждый блок шифруется потоковым шифратором. Для каждого зашифрованного блока ${\displaystyle E_{i}}$ вычисляется 16-байтовый код аутентификации. Получаем криптограмму

${\displaystyle e=E_{1}||C_{1}||...||E_{t}||C_{t}}$ .

${\displaystyle L(e)=L(M)+16\left\lceil L(M)/m\right\rceil }$ . Заметим, что если ${\displaystyle L(M)=0}$ , то ${\displaystyle L(e)=0}$ .

Алгоритм. Симметричный процесс шифрования ACE.
Вход: ${\displaystyle (k,s,M,m)\in W^{8}\times W^{4}\times Z\times B^{\ast }}$ ${\displaystyle m>0}$
Выход: ${\displaystyle e\in B^{l}}$ , ${\displaystyle l=L(M)+16\left\lceil L(N)/m\right\rceil }$ .

1. Если ${\displaystyle M=\lambda _{B}}$ , тогда вернуть ${\displaystyle \lambda _{B}}$ .
2. Проинициализировать генератор псевдо-случайных чисел:

${\displaystyle genState\leftarrow InitGen(k,s)\in GenState}$

1. Сгенерировать ключ ${\displaystyle k_{AXU}AXUHash}$ :

${\displaystyle (k_{AXU},genState)\leftarrow GenWords((5L_{b}(\left\lceil m/64\right\rceil )+24),genState).}$ .

1. ${\displaystyle e\leftarrow \lambda _{B},i\leftarrow 0}$ .
2. Пока ${\displaystyle i<L(M)}$ , выполнять следующее:
   1. ${\displaystyle r\leftarrow min(L(M)-i,m)}$ .
   2. Сгенерировать значения масок для шифрования и MAC:
      1. ${\displaystyle (mask_{m},genState)\leftarrow GenWords(4,genState)}$ .
      2. ${\displaystyle (mask_{e},genState)\leftarrow GenWords(r,genState)}$ .
   3. Зашифровать текст: ${\displaystyle enc\leftarrow {\Bigl [}M{\Bigr ]}_{i}^{i+r}\oplus mask_{e}}$ .
   4. Сгенерировать аутентификационный код сообщения:
      1. Если ${\displaystyle i+r=L(M)}$ , тогда ${\displaystyle lastBlock\leftarrow 1}$ ; иначе ${\displaystyle lastBlock\leftarrow 0}$ .
      2. ${\displaystyle mac\leftarrow AXUHash(k_{AXU},lastBlock,enc)\in W^{4}}$ .
   5. Обновить шифротекст: ${\displaystyle e\leftarrow e||enc||I_{W^{\ast }}^{B^{\ast }}(mac\oplus mask_{m})}$ .
   6. ${\displaystyle i\leftarrow i+r}$ .
3. Вернуть ${\displaystyle e}$ .

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

Алгоритм. Процесс дешифрования ACE.
Вход: открытый ключ ${\displaystyle (P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2})}$ и соответствующий закрытый ключ ${\displaystyle (w,x,y,z_{1},z_{2})}$ , байтовая строка ${\displaystyle \psi \in B^{\ast }}$ .
Выход: Расшифрованное сообщение ${\displaystyle M\in B^{\ast }\cup {Reject}}$ .

1. Дешифровать шифротекст:
   1. Если ${\displaystyle L(\psi )<3L_{B}(P)+16}$ , тогда вернуть ${\displaystyle Reject}$ .
   2. Вычислить:
      

      ${\displaystyle (s,u_{1},u_{2},v,e)\leftarrow CDecode(L_{B}(P),\psi )\in W^{4}\times Z\times Z\times Z\times B^{\ast }}$ ;

      
      заметим, что ${\displaystyle 0\leq u_{1},u_{2},v<256^{l}}$ , где ${\displaystyle l=L_{B}(P)}$ .
2. Подтвердить преамбулу шифротекста:
   1. Если ${\displaystyle u_{1}\geq P}$ или ${\displaystyle u_{2}\geq P}$ или ${\displaystyle v\geq P}$ , тогда вернуть ${\displaystyle Reject}$ .
   2. Если ${\displaystyle u_{1}^{q}\neq 1remP}$ , тогда вернуть ${\displaystyle Reject}$ .
   3. ${\displaystyle reject\leftarrow 0}$ .
   4. Если ${\displaystyle u_{2}\neq u_{1}^{w}remP}$ , тогда ${\displaystyle reject\leftarrow 1}$ .
   5. Вычислить ${\displaystyle \alpha \leftarrow UOWHash^{\prime }(k_{1},L_{B}(P),s,u_{1},u_{2})\in Z}$ ; заметим, что ${\displaystyle 0\leq \alpha \leq 2^{160}}$ .
   6. Если ${\displaystyle v\neq u_{1}^{x+{\alpha }y}remP}$ , тогда ${\displaystyle reject\leftarrow 1}$ .
   7. Если ${\displaystyle reject=1}$ , тогда вернуть ${\displaystyle Reject}$ .
3. Вычислить ключ для процесс симметричного дешифрования:
   1. ${\displaystyle {\tilde {h_{1}}}\leftarrow u_{1}^{z_{1}}remP}$ , ${\displaystyle {\tilde {h_{2}}}\leftarrow u_{1}^{z_{2}}remP}$ .
   2. Вычислить ${\displaystyle k\leftarrow ESHash(k_{2},L_{B}(P),s,u_{1},{\tilde {h_{1}}},{\tilde {h_{2}}})\in W^{8}}$ .
4. Вычислить ${\displaystyle M\leftarrow SDec(k,s,1024,e)}$ ;заметим, что ${\displaystyle SDec}$ может вернуть ${\displaystyle Reject}$ .
5. Вернуть ${\displaystyle M}$ .

Алгоритм. Операция дешифрования ${\displaystyle SDec}$ .
Вход: ${\displaystyle (k,s,m,e)\in W^{8}\times W^{4}\times Z\times B^{\ast }}$ ${\displaystyle m>0}$
Выход: Расшифрованное сообщение ${\displaystyle M\in B^{\ast }\cup {Reject}}$ .

1. Если ${\displaystyle e=\lambda _{B}}$ , тогда вернуть ${\displaystyle \lambda _{B}}$ .
2. Проинициализировать генератор псевдо-случайных чисел:
   

   ${\displaystyle genState\leftarrow InitGen(k,s)\in GenState}$

3. Сгенерировать ключ ${\displaystyle k_{AXU}AXUHash}$ :
   

   ${\displaystyle (k_{AXU},genState^{\prime })\leftarrow GenWords((5L_{b}(\left\lceil m/64\right\rceil )+24),genState).}$ .

4. ${\displaystyle M\leftarrow \lambda _{B},i\leftarrow 0}$ .
5. Пока ${\displaystyle i<L(e)}$ , выполнять следующее:
   1. ${\displaystyle r\leftarrow min(L(e)-i,m+16)-16}$ .
   2. Если ${\displaystyle r\leq 0}$ , тогда вернуть ${\displaystyle Reject}$ .
   3. Сгенерировать значения масок для шифрования и MAC:
      1. ${\displaystyle (mask_{m},genState)\leftarrow GenWords(4,genState)}$ .
      2. ${\displaystyle (mask_{e},genState)\leftarrow GenWords(r,genState)}$ .
   4. Подтвердить аутентификационный код сообщения:
      1. Если ${\displaystyle i+r+16=L(M)}$ , тогда ${\displaystyle lastblock\leftarrow 1}$ ; иначе ${\displaystyle lastblock\leftarrow 0}$ .
      2. ${\displaystyle mac\leftarrow AXUHash(k_{AXU},lastBlock,{\Bigl [}e{\Bigr ]}_{i}^{i+r})\in W^{4}}$ .
      3. Если ${\displaystyle {\Bigl [}e{\Big ]}r_{i+r}^{i+r+16}\neq I_{W^{\ast }}^{B^{\ast }}(mac\oplus mask_{m})}$ , тогда вернуть ${\displaystyle Reject}$ .
   5. Обновить текст: ${\displaystyle M\leftarrow M||({\Bigl [}e{\Bigr ]}_{i}^{i+r})\oplus mask_{e})}$ .
   6. ${\displaystyle i\leftarrow i+r+16}$ .
6. Вернуть ${\displaystyle M}$ .

Схема цифровой подписи

В схеме цифровой подписи ACE задействованы два типа ключей:
открытый ключ цифровой подписи ACE: ${\displaystyle (N,h,x,e^{\prime },k^{\prime },s)}$ .
закрытый ключ цифровой подписи ACE: ${\displaystyle (p,q,a)}$ .
Для заданного параметра размера ${\displaystyle m}$ , такого что ${\displaystyle 1024\leq m\leq 16384}$ , компоненты ключей определяются следующим образом:
${\displaystyle p}$ — ${\displaystyle \left\lfloor m/2\right\rfloor }$ -битное простое число, для которого ${\displaystyle (p-1)/2}$ — тоже простое.
${\displaystyle q}$ — ${\displaystyle \left\lfloor m/2\right\rfloor }$ -битное простое число, для которого ${\displaystyle (q-1)/2}$ — тоже простое.
${\displaystyle N}$ — ${\displaystyle N=pq}$ и может иметь как ${\displaystyle m}$ , так и ${\displaystyle m-1}$ бит.
${\displaystyle h,x}$ — элементы ${\displaystyle \left\{1,...,N-1\right\}}$ (квадратичные остатки по модулю ${\displaystyle N}$ ).
${\displaystyle e^{\prime }}$ — 161-битное простое число.
${\displaystyle a}$ — элемент ${\displaystyle \left\{0,...,(p-1)(q-1)/4-1\right\}}$
${\displaystyle k^{\prime }}$ — элементы ${\displaystyle B^{184}}$ .
${\displaystyle s}$ — элементы ${\displaystyle B^{32}}$ .

Генерация ключа

Алгоритм. Генерация ключа для схемы цифровой подписи ACE.
Вход: параметра размера ${\displaystyle m}$ , такой что ${\displaystyle 1024\leq m\leq 16384}$ .
Выход: пара открытый/закрытый ключ.

1. Сгенерировать случайные простые числа ${\displaystyle p,q}$ , такие что ${\displaystyle (p-1)/2}$ и ${\displaystyle (q-1)/2}$ — тоже простые, и
   

   ${\displaystyle 2^{m_{1}-1}<p<2^{m_{1}}}$ , ${\displaystyle 2^{m_{2}-1}<q<2^{m_{2}}}$ , и ${\displaystyle p\neq q}$ ,

   
   где
   

   ${\displaystyle m_{1}=\left\lfloor m/2\right\rfloor }$ и ${\displaystyle m_{1}=\left\lceil m/2\right\rceil }$ .

2. Положить ${\displaystyle N\leftarrow pq}$ .
3. Сгенерировать случайное простое число ${\displaystyle e^{\prime }}$ , где ${\displaystyle 2^{160}\leq e^{\prime }\leq 2^{161}}$ .
4. Сгенерировать случайное ${\displaystyle h^{\prime }\in \left\{1,...,N-1\right\}}$ , при условии ${\displaystyle gcd(h^{\prime },N)=1}$ и ${\displaystyle gcd(h^{\prime }\pm 1,N)=1}$ , и вычислить ${\displaystyle h\leftarrow (h^{\prime })^{-2}remN}$ .
5. Сгенерировать случайное ${\displaystyle a\in \left\{0,...,(p-1)(q-1)/4-1\right\}}$ и вычислить ${\displaystyle x\leftarrow h^{a}remN}$ .
6. Сгенерировать случайные байтовые строки ${\displaystyle k^{\prime }\in B^{184}}$ , и ${\displaystyle s\in B^{32}}$ .
7. Вернуть пару открытый ключ/закрытый ключ
   

   ${\displaystyle ((N,h,x,e^{\prime },k^{\prime },s),(p,q,a))}$ .

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

Подпись в схеме цифровой подписи ACE имеет вид ${\displaystyle (d,w,y,y^{\prime },{\tilde {k}})}$ , где компоненты определяются следующим образом:
${\displaystyle d}$ — элемент ${\displaystyle B^{64}}$ .
${\displaystyle w}$ — целое число, такое что ${\displaystyle 2^{160}\leq w\leq 2^{161}}$ .
${\displaystyle y,y^{\prime }}$ — элементы ${\displaystyle \left\{1,...,N-1\right\}}$ .
${\displaystyle {\tilde {k}}}$ — элемент ${\displaystyle B^{\ast }}$ ;заметим, что ${\displaystyle L({\tilde {k}})=64+20L_{B}(\left\lceil (L(M)+8)/64\right\rceil )}$ , где ${\displaystyle M}$ — подписываемое сообщение.

Необходимо ввести функцию ${\displaystyle SEncode}$ , которая представляет подпись в виде байтовой строки, а также обратную функцию ${\displaystyle SDecode}$ . Для целого ${\displaystyle l>0}$ , байтовой строки ${\displaystyle d\in B^{64}}$ , целых ${\displaystyle 0\leq w\leq 256^{21}}$ и ${\displaystyle 0\leq y,y^{\prime }<256^{l}}$ , и байтовой строки ${\displaystyle {\tilde {k}}\in B^{\ast }}$ ,

${\displaystyle SEncode(l,d,w,y,y^{\prime },{\tilde {k}}){\stackrel {\mathrm {def} }{=}}d||pad_{21}(I_{Z}^{B^{\ast }}(w))||pad_{l}(I_{Z}^{B^{\ast }}(y))||pad_{l}(I_{Z}^{B^{\ast }}(y^{\prime }))||{\tilde {k}}\in B^{\ast }}$ .

Для целого ${\displaystyle l>0}$ , байтовой строки ${\displaystyle \sigma \in B^{\ast }}$ , для которой ${\displaystyle L(\sigma )\geq 2l+53}$ ,

${\displaystyle CSecode(l,\sigma ){\stackrel {\mathrm {def} }{=}}({\Bigl [}\sigma {\Bigr ]}_{0}^{64},I_{B^{\ast }}^{Z}({\Bigl [}\sigma {\Bigr ]}_{64}^{85}),I_{B^{\ast }}^{Z}({\Bigl [}\sigma {\Bigr ]}_{85}^{85+l}),I_{B^{\ast }}^{Z}({\Bigl [}\sigma {\Bigr ]}_{85+l}^{85+2l}),{\Bigl [}\sigma {\Bigr ]}_{85+2l}^{L(\sigma )})\in B^{64}\times Z\times Z\times Z\times B^{\ast }}$ .

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

Алгоритм. Генерирование цифровой подписи ACE.
Вход: открытый ключ ${\displaystyle (N,h,x,e^{\prime },k^{\prime },s)}$ и соответствующий закрытый ключ ${\displaystyle (p,q,a)}$ и байтовая строка ${\displaystyle M\in B^{\ast }}$ , ${\displaystyle 0\leq L(M)\leq 2^{64}}$ .
Выход: байтовая строка — цифровая подпись ${\displaystyle \sigma \in B^{\ast }}$ .

1. Произвести следующие действия для хеширования входных данных:
   1. Сгенерировать случайно ключ хеша ${\displaystyle {\tilde {k}}\in B^{20m+64}}$ , такой что ${\displaystyle m=L_{b}(\left\lceil (L(M)+8)/64\right\rceil )}$ .
   2. Вычислить ${\displaystyle m_{h}\leftarrow I_{W^{\ast }}^{Z}(UOWHash^{\prime \prime }({\tilde {k}},M))}$ .
2. Выбрать случайное ${\displaystyle {\tilde {y}}\in \left\{1,...,N-1\right\}}$ , и вычислить ${\displaystyle y^{\prime }\leftarrow {\tilde {y}}^{2}remN}$ .
3. Вычислить ${\displaystyle x^{\prime }\leftarrow (y^{\prime })^{r^{\prime }}h^{m_{h}}remN}$ .
4. Сгенерировать случайное простое число ${\displaystyle e}$ , ${\displaystyle 2^{160}\leq e\leq 2^{161}}$ , и его подтверждение корректности ${\displaystyle (w,d)}$ : ${\displaystyle (e,w,d)\leftarrow GenCertPrime(s)}$ . Повторять этот шаг до тех пор, когда ${\displaystyle e\neq e^{\prime }}$ .
5. Положить ${\displaystyle r\leftarrow UOWHash^{\prime \prime \prime }(k^{\prime },L_{B}(N),x^{\prime },{\tilde {k}})\in Z}$ ; заметим, что ${\displaystyle 0\leq r<2^{160}}$ .
6. Вычислить ${\displaystyle y\leftarrow h^{b}remN}$ , где
   

   ${\displaystyle b\leftarrow e^{-1}(a-r)rem(p^{\prime }q^{\prime })}$ ,

   
   и где ${\displaystyle p^{\prime }=(p-1)/2}$ и ${\displaystyle q^{\prime }=(q-1)/2}$ .
7. Закодировать подпись:
   

   ${\displaystyle \sigma \leftarrow SEncode(L_{B}(N),d,w,y,y^{\prime },{\tilde {k}})}$ .

Замечания

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

Литература

Ссылки

• от 26 июля 2011 на Wayback Machine
• от 28 июля 2011 на Wayback Machine
• от 12 августа 2011 на Wayback Machine