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., ${\displaystyle z=h({\text{Cert Data}})}$.

Signing

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

Verifying

• Verifier computes ${\displaystyle 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