WikiSort.ru - Не сортированное

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

• Входные данные: целые ${\displaystyle N,q,d_{f},d_{g},B>0}$ , строка ${\displaystyle t=standard}$ или ${\displaystyle transpose}$ .
• Генерация ${\displaystyle B}$ закрытых решёточных базисов и один открытый решеточный базис

Установить ${\displaystyle i=B}$ . До тех пор, пока ${\displaystyle i>0}$ :

1. Произвольно выбрать ${\displaystyle f}$ , ${\displaystyle g}$ ∈ ${\displaystyle \mathbb {R} }$ , взаимно простые с ${\displaystyle d_{f}}$ , ${\displaystyle d_{g}}$ соответственно.
2. Найти малые ${\displaystyle F,G\in R}$ такие, что ${\displaystyle f*G-F*g=q}$ .
3. Если ${\displaystyle t=standard}$ , установить ${\displaystyle f_{i}=f}$ и ${\displaystyle f'_{i}=F}$ .

Если ${\displaystyle t=transpose}$ , установить ${\displaystyle f_{i}=f}$ и ${\displaystyle f'_{i}=g}$ .

Вычислить ${\displaystyle h_{i}=f_{i}^{-1}*f'_{i}modq}$ . Установить ${\displaystyle i=i-1}$ .

• Публичный ключ: входные параметры и ${\displaystyle h=ho=f_{0}^{-1}*f'_{0}\operatorname {mod} q}$ .
• Закрытый ключ: ${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\}}$ для ${\displaystyle i=0...B}$ .

Подпись

Подпись требует хеш-функцию ${\displaystyle H:{\mathcal {D}}\rightarrow R}$ на цифровом пространстве документа ${\displaystyle {\mathcal {D}}}$ .

• Входные данные: цифровой документ ${\displaystyle D\in {\mathcal {D}}}$ и закрытый ключ ${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\}}$ для ${\displaystyle i=0...B}$ .
• Установить ${\displaystyle r=0}$ .
• Установить ${\displaystyle s=0}$ и ${\displaystyle i=B}$ . Представить ${\displaystyle r}$ как строку бит. Установить ${\displaystyle m_{o}=H(D||r)}$ , где ${\displaystyle ||}$ обозначает конкатенацию. Установить ${\displaystyle m=m_{o}}$ .

1. ${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\}}$ - ${\displaystyle i}$ -е основание
2. Вычислить ${\displaystyle x=\lfloor -{\frac {1}{q}}m_{i}*f'_{i}\rceil }$
3. Вычислить ${\displaystyle y=\lfloor {\frac {1}{q}}m_{i}*f_{i}\rceil }$
4. ${\displaystyle s_{i}=x*f+y*f'}$
5. ${\displaystyle m_{i}=si*(h_{i}-h_{i-1})\mod q}$
6. Подпись: ${\displaystyle s=s+s_{i}}$

Проверка подписи

Верификация требует такую же хеш-функцию ${\displaystyle H}$ , «нормирующую связь» ${\displaystyle {\mathcal {N}}\in \mathbb {R} }$ и норму полинома ${\displaystyle ||.||}$ . Норма ${\displaystyle ||t||}$ полинома ${\displaystyle t}$ определяется как ${\displaystyle \inf _{0\leq k<q}||t+kq||_{z}}$ , где ${\displaystyle ||r||_{z}=\sum _{i=0}^{N-1}r_{i}^{2}-{\frac {1}{N}}\sum _{i=0}^{N}r_{i}}$ (где последнее - Евклидова норма).

• Входные данные: Подписанные данные ${\displaystyle (D,r,s)}$ и публичный ключ ${\displaystyle h}$ .
• Представить r как строку бит. Установить ${\displaystyle m=H(D||r)}$ .
• Вычислить ${\displaystyle b=||(s,s*h-m\operatorname {mod} g))||}$ .
• подпись считается верной, если ${\displaystyle b<{\mathcal {N}}}$ .

Замечание

• Рекомендуемые параметры ${\displaystyle (N,q,d_{f},d_{g},B,t,{\mathcal {N}})=(251,128,73,71,1,transpose,310)}$