ACE Encrypt

${\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.
Вход: параметра размера ${\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}})}$.