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

Основные обозначения и терминология[править | править исходный текст]

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

Основные математические обозначения[править | править исходный текст]

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

Основные строковые обозначения[править | править исходный текст]

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

Биты, байты, слова[править | править исходный текст]

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

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


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

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


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

Оператор преобразования[править | править исходный текст]

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

Схема шифрования[править | править исходный текст]

Пара ключей шифрования[править | править исходный текст]

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

Генерация ключа[править | править исходный текст]

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

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

    g_2 \leftarrow g_1^w rem P,


    c \leftarrow g_1^x rem P,


    d \leftarrow g_1^y rem P,


    h_1 \leftarrow g_1^{z_1} rem P,


    h_2 \leftarrow g_1^{z_2} rem P.

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

    ((P,q,g_1,g_2,c,d,h_1,h_2,k_1,k_2),(w,x,y,z_1,z_2))\,

Представление шифротекста[править | править исходный текст]

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

(s,u_1,u_2,v,e)\,,


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

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

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


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

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

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

    \psi\ \leftarrow CEncode(L_B(P),s,u_1,u_2,v,e).

  6. Вернуть  \psi\ .

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

e=E_1||C_1||...||E_t||C_t\,.

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

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

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

genState \leftarrow InitGen(k,s) \in GenState

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

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

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

Процесс дешифрования[править | править исходный текст]

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

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

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


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

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

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

    genState \leftarrow InitGen(k,s) \in GenState

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

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

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

Схема цифровой подписи[править | править исходный текст]

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

Генерация ключа[править | править исходный текст]

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

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

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


    где

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

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

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

Представление подписи[править | править исходный текст]

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

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

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


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

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

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

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


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

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

Замечания[править | править исходный текст]

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

Литература[править | править исходный текст]

Ссылки[править | править исходный текст]