WikiSort.ru - Компьютерные программы

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

${\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}})}$ .