KCDSA

KCDSA (Korean Certificate-based Digital Signature Algorithm) is a digital signature algorithm created by a team led by the Korea Internet & Security Agency (KISA). It is an ElGamal variant, similar to the Digital Signature Algorithm and GOST R 34.10-94. The standard algorithm is implemented over $GF(p)$, but an elliptic curve variant (EC-KCDSA) is also specified.

KCDSA requires a collision-resistant cryptographic hash function that can produce a variable-sized output (from 128 to 256 bits, in 32-bit increments). HAS-160, another Korean standard, is the suggested choice.

Domain parameters

• $p$: a large prime such that $|p| = 512 + 256i$ for $i = 0, 1, \dots, 6$.
• $q$: a prime factor of $p-1$ such that $|q| = 128 + 32j$ for $j = 0, 1, \dots, 4$.
• $g$: a base element of order $q \in GF(p)$.

User parameters

• $x$: signer's private signature key such that $x \in Z_q$.
• $y$: signer's public verification key computed by $y=g^\bar{x} \pmod{p},$ where $\bar{x}=x^{-1} \pmod{q}$.
• $z$: a hash-value of Cert Data, i.e., $z = h(\text{Cert Data})$.

Signing

• Signer randomly picks an integer $k \in Z_q$ and computes $w = g^k \mod{p}$
• Then computes the first part: $r = h(w)$
• Then computes the second part: $s = x(k - r \oplus h(z \parallel m)) \pmod{q}$
• The signature is $(r, s)$

Verifying

• Verifier computes $e = r \oplus h(z \parallel m)$
• Then he checks if $r = h(y^s \cdot g^e \mod{p})$

External links

• KCDSA specification and analysis