Русская Википедия: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

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

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

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

<math>Z</math> — множество целых чисел.
<math>F_2[T]</math> — множество одномерных полиномов с коэффициентами в конечном поле <math>F_2</math> с числом элементов поля — 2.
<math>A rem n</math> — такое целое число <math>r \in \left\{0,...,n-1\right\}</math>, для которого <math>A\equiv r(mod n)</math> при целом <math>n>0</math> и <math>A \in Z</math>.
<math>A rem f</math> — такой полином <math>r \in F_2[T]</math> с <math>deg(r)<deg(f)</math>, такой что <math>A\equiv r(mod f)</math> при <math>A,f \in F_2[T],f \ne 0</math>.

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

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

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

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

<math>0_b\stackrel{\mathrm{def}}{=}0 \in b</math>;
<math>0_{A^n}\stackrel{\mathrm{def}}{=}(0_A,...,0_A) \in A^n</math> для <math>n>0</math>.

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

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

<math> pad_l(x) \stackrel{\mathrm{def}}{=} \begin{cases} x, & L(x) \ge l \\ x||0_{A^{l-L(x)}}, & L(x)<l \end{cases}</math>.

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

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

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

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

В схеме шифрования ACE задействованы два типа ключей:
открытый ключ ACE: <math>(P,q,g_1,g_2,c,d,h_1,h_2,k_1,k_2)</math>.
закрытый ключ ACE: <math>(w,x,y,z_1,z_2)</math>.
Для заданного параметра размера <math>m</math>, такого что <math>1024 \le m \le 16384</math>, компоненты ключей определяются следующим образом:
<math>q</math> — 256-битное простое число.
<math>P</math> — m-битное простое число, такое что <math>P\equiv1(mod q)</math>.
<math>g_1,g_2,c,d,h_1,h_2</math> — элементы <math>\left\{1,...,P-1\right\}</math> (чей мультипликативный порядок по модулю <math>P</math> делит <math>q</math>).
<math>w,x,y,z_1,z_2</math> — элементы <math>\left\{0,...,q-1\right\}</math>.
<math>k_1,k_2</math> — элементы <math>B^\ast</math>, для которых <math>L(k_1)=20l^\prime+64</math> и <math>L(k_2)=32\left\lceil l/16 \right\rceil+40</math>, где <math>l=\left\lceil m/8 \right\rceil</math> и <math>l^\prime=L_b(\left\lceil (2\left\lceil l/4 \right\rceil +4)/16 \right\rceil)</math>.

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

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

1. Сгенерировать случайное простое число <math>q</math>, такое что <math>2^{255} < q < 2^{256}</math>.
2. Сгенерировать случайное простое число <math>P</math>, <math>2^{m-1} < P < 2^{m}</math>, такое что <math>P\equiv1(mod q)</math>.
3. Сгенерировать случайное целое число <math>g_1 \in \left\{ 2,...,P-1 \right\}</math>, такое что <math>g_1^q\equiv1(mod P)</math>.
4. Сгенерировать случайные целые числа <math>w \in \left\{ 1,...,q-1 \right\}</math> и <math>x,y,z_1,z_2 \in \left\{ 0,...,q-1 \right\}</math>
5. Вычислить следующие целые числа в <math>\left\{ 1,...,P-1 \right\}</math>:
   

   <math>g_2 \leftarrow g_1^w rem P</math>,

   
   

   <math>c \leftarrow g_1^x rem P</math>,

   
   

   <math>d \leftarrow g_1^y rem P</math>,

   
   

   <math>h_1 \leftarrow g_1^{z_1} rem P</math>,

   
   

   <math>h_2 \leftarrow g_1^{z_2} rem P</math>.

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

   <math>((P,q,g_1,g_2,c,d,h_1,h_2,k_1,k_2),(w,x,y,z_1,z_2))</math>

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

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

<math>(s,u_1,u_2,v,e)</math>,

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

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

<math>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}</math>.

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

<math>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}</math>.

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

Алгоритм. Асимметричный процесс шифрования ACE.
Вход: открытый ключ <math>(P,q,g_1,g_2,c,d,h_1,h_2,k_1,k_2)</math> и байтовая строка <math>M \in B^{\ast}</math>.
Выход: байтовая строка — шифротекст <math> \psi\ </math>, полученный из <math>M</math>.

1. Сгенерировать случайное <math>r \in \left\{ 0,...,q-1 \right\}</math>.
2. Сгенерировать преамбулу шифротекста:
   1. Сгенерировать <math>s \in W^4</math>.
   2. Вычислить <math>u_1 \leftarrow g_1^r rem P</math>, <math>u_2 \leftarrow g_2^r rem P</math>.
   3. Вычислить <math>\alpha\ \leftarrow UOWHash^\prime (k_1,L_B(P),s,u_1,u_2) \in Z</math>; заметим, что <math>0 < \alpha\ < 2^{160}</math>.
   4. Вычислить <math>v \leftarrow c^r d^{\alpha\ r} rem P</math>.
3. Вычислить ключ для операции симметричного шифрования:
   1. <math>\tilde{h_1} \leftarrow h_1^r rem P</math>, <math>\tilde{h_2} \leftarrow h_2^r rem P</math>.
   2. Вычислить <math>k \leftarrow ESHash(k,L_B(P),s,u_1,u_2,\tilde{h_1},\tilde{h_2}) \in W^8</math>.
4. Вычислить криптограмму <math>e \leftarrow SEnc(k,s,1024,M)</math>.
5. Закодировать шифротекст:
   

   <math>\psi\ \leftarrow CEncode(L_B(P),s,u_1,u_2,v,e)</math>.

6. Вернуть <math> \psi\ </math>.

Перед запуском процесса симметричного шифрования входное сообщение <math>M \in B^{\ast}</math> разбивается на блоки <math>M_1,...,M_t</math>, где каждый блок кроме, возможно, последнего имеет 1024 байт. Каждый блок шифруется потоковым шифратором. Для каждого зашифрованного блока <math>E_i</math> вычисляется 16-байтовый код аутентификации. Получаем криптограмму

<math>e=E_1||C_1||...||E_t||C_t</math>.

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

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

1. Если <math>M=\lambda_B</math>, тогда вернуть <math>\lambda_B</math>.
2. Проинициализировать генератор псевдо-случайных чисел:

<math>genState \leftarrow InitGen(k,s) \in GenState</math>

1. Сгенерировать ключ <math>k_{AXU} AXUHash</math>:

<math>(k_{AXU},genState) \leftarrow GenWords((5L_b(\left\lceil m/64 \right\rceil)+24),genState).</math>.

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

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

Алгоритм. Процесс дешифрования ACE.
Вход: открытый ключ <math>(P,q,g_1,g_2,c,d,h_1,h_2,k_1,k_2)</math> и соответствующий закрытый ключ <math>(w,x,y,z_1,z_2)</math>, байтовая строка <math>\psi \in B^{\ast}</math>.
Выход: Расшифрованное сообщение <math>M \in B^{\ast} \cup {Reject}</math>.

1. Дешифровать шифротекст:
   1. Если <math>L(\psi) < 3L_B(P)+16</math>, тогда вернуть <math>Reject</math>.
   2. Вычислить:
      

      <math>(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}</math>;

      
      заметим, что <math>0 \le u_1,u_2,v<256^l</math>, где <math>l=L_B(P)</math>.
2. Подтвердить преамбулу шифротекста:
   1. Если <math>u_1 \ge P</math> или <math>u_2 \ge P</math> или <math>v \ge P</math>, тогда вернуть <math>Reject</math>.
   2. Если <math>u_1^q \ne 1 rem P</math>, тогда вернуть <math>Reject</math>.
   3. <math>reject \leftarrow 0</math>.
   4. Если <math>u_2 \ne u_1^w rem P</math>, тогда <math>reject \leftarrow 1</math>.
   5. Вычислить <math>\alpha \leftarrow UOWHash^{\prime}(k_1,L_B(P),s,u_1,u_2) \in Z</math>; заметим, что <math>0 \le \alpha \le 2^{160}</math>.
   6. Если <math>v \ne u_1^{x+{\alpha}y} rem P</math>, тогда <math>reject \leftarrow 1</math>.
   7. Если <math>reject=1</math>, тогда вернуть <math>Reject</math>.
3. Вычислить ключ для процесс симметричного дешифрования:
   1. <math>\tilde{h_1} \leftarrow u_1^{z_1} rem P</math>, <math>\tilde{h_2} \leftarrow u_1^{z_2} rem P</math>.
   2. Вычислить <math>k \leftarrow ESHash(k_2,L_B(P),s,u_1,\tilde{h_1},\tilde{h_2}) \in W^8</math>.
4. Вычислить <math>M \leftarrow SDec(k,s,1024,e)</math>;заметим, что <math>SDec</math> может вернуть <math>Reject</math>.
5. Вернуть <math>M</math>.

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

1. Если <math>e=\lambda_B</math>, тогда вернуть <math>\lambda_B</math>.
2. Проинициализировать генератор псевдо-случайных чисел:
   

   <math>genState \leftarrow InitGen(k,s) \in GenState</math>

3. Сгенерировать ключ <math>k_{AXU} AXUHash</math>:
   

   <math>(k_{AXU},genState^{\prime}) \leftarrow GenWords((5L_b(\left\lceil m/64 \right\rceil)+24),genState).</math>.

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

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

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

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

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

1. Сгенерировать случайные простые числа <math>p,q</math>, такие что <math>(p-1)/2</math> и <math>(q-1)/2</math> — тоже простые, и
   

   <math>2^{m_1-1}<p<2^{m_1}</math>, <math>2^{m_2-1}<q<2^{m_2}</math>, и <math>p \ne q</math>,

   
   где
   

   <math>m_1=\left\lfloor m/2 \right\rfloor</math> и <math>m_1=\left\lceil m/2 \right\rceil</math>.

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

   <math>((N,h,x,e^{\prime},k^{\prime},s),(p,q,a))</math>.

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

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

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

<math>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}</math>.

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

<math>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}</math>.

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

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

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

   <math>b \leftarrow e^{-1}(a-r)rem(p^{\prime}q^{\prime})</math>,

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

   <math>\sigma \leftarrow SEncode(L_B(N),d,w,y,y^{\prime},\tilde{k})</math>.

Замечания

В схемах шифрования и цифровой подписи 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 Шаблон:Wayback
• http://www.zurich.ibm.com/security/ace/ Шаблон:Wayback
• NESSIE Portfolio of recommended cryptographic primitives Шаблон:Wayback