# 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 ${\displaystyle 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

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

## User parameters

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

## Signing

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

## Verifying

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