Перейти к содержанию

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

    [math]\displaystyle{ g_2 \leftarrow g_1^w rem P }[/math],


    [math]\displaystyle{ c \leftarrow g_1^x rem P }[/math],


    [math]\displaystyle{ d \leftarrow g_1^y rem P }[/math],


    [math]\displaystyle{ h_1 \leftarrow g_1^{z_1} rem P }[/math],


    [math]\displaystyle{ h_2 \leftarrow g_1^{z_2} rem P }[/math].

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

    [math]\displaystyle{ ((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]\displaystyle{ (s,u_1,u_2,v,e) }[/math],


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

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

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


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

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

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

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

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

    [math]\displaystyle{ \psi\ \leftarrow CEncode(L_B(P),s,u_1,u_2,v,e) }[/math].

  6. Вернуть [math]\displaystyle{ \psi\ }[/math].

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

[math]\displaystyle{ e=E_1||C_1||...||E_t||C_t }[/math].

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

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

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

[math]\displaystyle{ genState \leftarrow InitGen(k,s) \in GenState }[/math]

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

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

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

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

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

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

      [math]\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} }[/math];


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

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

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

    [math]\displaystyle{ genState \leftarrow InitGen(k,s) \in GenState }[/math]

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

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

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

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

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

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

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

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

    [math]\displaystyle{ 2^{m_1-1}\lt p\lt 2^{m_1} }[/math], [math]\displaystyle{ 2^{m_2-1}\lt q\lt 2^{m_2} }[/math], и [math]\displaystyle{ p \ne q }[/math],


    где

    [math]\displaystyle{ m_1=\left\lfloor m/2 \right\rfloor }[/math] и [math]\displaystyle{ m_1=\left\lceil m/2 \right\rceil }[/math].

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

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

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

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

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

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


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

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

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

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

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

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


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

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

Замечания

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

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=ACE_Encrypt&oldid=5862005