KCDSA

KCDSA (Корейський алгоритм цифрового підпису на основі сертифіката) — це алгоритм цифрового підпису, створений групою під керівництвом Шаблон:Iw (KISA). Це варіант ElGamal, аналогічний Алгоритму цифрового підпису та Шаблон:Iw. Стандартний алгоритм реалізовано над $GF(p)$, але також вказано варіант на еліптичних кривих (EC-KCDSA).

Для KCDSA потрібна колізійно стійка криптографічна хеш-функція, яка може створювати вихідні дані змінного розміру (від 128 до 256 біт із кроком 32 біт). Шаблон:Iw, інший корейський стандарт, є запропонованим вибором.

Параметри

• $p$ : велике просте таке, що $|p|=512+256i$ для $i=0,1,\dots ,6$ .
• $q$ : основний множник $p-1$ такий, що $|q|=128+32j$ для $j=0,1,\dots ,4$ .
• $g$ : базовий елемент порядку $q$ в $\mathrm{GF}(p)$ .

Параметри користувача

• $x$ : особистий ключ підпису підписувача такий, що $0<x<q$ .
• $y$ : відкритий ключ перевірки підписувача, обчислений $y=g^{\overline{x}}(\mathrm{mod}p),$ де $\overline{x}=x^{-1}(\mathrm{mod}q)$ .
• $z$ : хеш-значення даних сертифіката, тобто $z=h(\text{Cert Data})$ .

У специфікації 1998 року неясно, який саме формат «Даних сертифіката». У переглянутій специфікації z визначається як B нижніх бітів відкритого ключа y, де B — розмір блоку хеш-функції в бітах (зазвичай 512 або 1024). Ефект полягає в тому, що перший вхідний блок відповідає y mod 2^B.

• $z$ : молодші B бітів y.

Хеш-функція

• $h$ : колізійно стійка хеш-функція з |q|-бітовими дайджестами.

Підписання

• Підписувач навмання вибирає ціле число $0<k<q$ і обчислює $w=g^{k}modp$
• Потім обчислює першу частину: $r=h(w)$
• Потім обчислює другу частину: $s=x(k-r\oplus h(z\parallel m))(\mathrm{mod}q)$
• Якщо $s=0$, процес потрібно повторити спочатку.
• Підписом є кортеж $(r,s)$

Перевірка

• Верифікатор перевіряє це $0\le r<2^{|q|}$ і $0<s<q$ і відхиляє підпис як недійсний, якщо ні.
• Верифікатор обчислює $e=r\oplus h(z\parallel m)$
• Потім він перевіряє, чи $r=h(y^s\cdot g^{e}modp)$

Посилання

• Специфікація та аналіз KCDSA