ACE Encrypt - ACE Encrypt

ACE (Продвинутый криптографический движок) - совокупность единиц, реализующих как схему шифрования с открытым ключом, так и схему цифровой подписи. Соответствующие названия этих схем - «ACE Encrypt» и «ACE Sign». Схемы основаны на схеме шифрования с открытым ключом Cramer-Shoup и схеме подписи Cramer-Shoup. Представленные варианты этих схем предназначены для достижения хорошего баланса между производительностью и безопасностью всей системы шифрования.

Авторы

Все алгоритмы, реализованные в ACE, основаны на алгоритмах, разработанных Виктором Шоупом и Рональдом Крамером. Полная спецификация алгоритмов написана Виктором Шупом. Реализацией алгоритмов занимаются Томас Швайнбергер и Мехди Нассехи, а поддержку и сопровождение - Виктор Шуп. Томас Швайнбергер участвовал в создании документа спецификации ACE, а также написал руководство пользователя.

Рональд Крамер в настоящее время учится в Орхусском университете, Дания. Он работал над проектом ACE Encrypt, находясь в ETH в Цюрих, Швейцария.

Мехди Нассехи и Томас Швайнбергер работали над проектом ACE в исследовательской лаборатории IBM в г. Цюрих, Швейцария.
Виктор Шуп работает в исследовательской лаборатории IBM в г. Цюрих, Швейцария.

Безопасность

Схема шифрования в ACE может быть доказана безопасностью при разумных и естественных предположениях о неприемлемости этих четырех предположений:

• Решительное допущение Диффи-Хеллмана (DDH)
• Сильное предположение 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: ${\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})\,}$.
Для заданного параметра размера m ${\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.
Ввод: параметр размера m ${\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}$
3. Сгенерируйте ключ ${\displaystyle k_{AXU}AXUHash\,}$: ${\displaystyle (k_{AXU},genState)\leftarrow GenWords((5L_{b}(\left\lceil m/64\right\rceil )+24),genState).}$.
4. ${\displaystyle e\leftarrow \lambda _{B},i\leftarrow 0}$.
5. В то время как ${\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}$.
6. Вернуть ${\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: ${\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}})}$.
8. Вернуть ${\displaystyle \sigma \,}$

Заметки

В определении процесса шифрования ACE и процесса подписи ACE используются некоторые вспомогательные функции (например, UOWHash, ESHash и некоторые другие), определение которых выходит за рамки данной статьи. Подробнее об этом можно прочитать в в.^[1]

Внедрение, использование и производительность

Схема шифрования ACE рекомендована NESSIE (Новые европейские схемы для подписей, целостности и шифрования) в качестве схемы асимметричного шифрования. Пресс-релиз датирован февралем 2003 года.

Обе схемы были реализованы на ANSI C с использованием библиотеки GNU GMP. Тесты проводились на двух платформах: Power PC 604 модели 43P в системе AIX и Pentium 266 МГц в системе Windows NT. Таблицы результатов:

Таблица 1. Временные затраты на основные операции.

	Питание ПК		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. Характеристики схемы шифрования и схемы подписи.

	Питание ПК		Pentium
	Постоянные затраты (мс)	Мбит / сек	Постоянные затраты (мс)	Мбит / сек
Зашифровать	160	18	230	16
Расшифровать	68	18	97	14
Знак	48	64	62	52
Настройка знака	29		41
Проверить	52	65	73	53

Литература

1. ACE: Advanced Cryptographic Engine, T. Schweinberger и V. Shoup, рукопись 2000 г.

внешние ссылки

• http://www.alphaworks.ibm.com/tech/ace
• http://www.zurich.ibm.com/security/ace/
• NESSIE Портфолио рекомендуемых криптографических примитивов