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 $\operatorname {GF} (p)$ .

The revised version of the spec additional requires either that $(p-1)/(2q)$ be prime or that all of its prime factors are greater than $q$ .

User parameters

$x$ : signer's private signature key such that $0<x<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}})$ .

The 1998 spec is unclear about the exact format of the "Cert Data". In the revised spec, z is defined as being the bottom B bits of the public key y, where B is the block size of the hash function in bits (typically 512 or 1024). The effect is that the first input block corresponds to y mod 2^B.

$z$ : the lower B bits of y.

Hash Function

$h$ : a collision resistant hash function with |q|-bit digests.

Signing

To sign a message $m$ :

Signer randomly picks an integer $0<k<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}}$
If $s=0$ , the process must be repeated from the start.
The signature is $(r,s)$

The specification is vague about how the integer $w$ be reinterpreted as a byte string input to hash function. In the example in section C.1 the interpretation is consistent with $r=h(I2OSP(w,|q|/8))$ using the definition of I2OSP from PKCS#1/RFC3447.

Verifying

To verify a signature $(r,s)$ on a message $m$ :

Verifier checks that $0\leq r<2^{|q|}$ and $0<s<q$ and rejects the signature as invalid if not.
Verifier computes $e=r\oplus h(z\parallel m)$
Verifier checks if $r=h(y^{s}\cdot g^{e}\mod {p})$ . If so then the signature is valid; otherwise it is not valid.

EC-KCDSA

EC-KCDSA is essentially the same algorithm using Elliptic-curve cryptography instead of discrete log cryptography.

The domain parameters are:

An elliptic curve $E$ over a finite field.
A point $G$ in $E$ generating a cyclic subgroup of prime order $q$ . ( $q$ is often denoted $n$ in other treatments of elliptic-curve cryptography.)

The user parameters and algorithms are essentially the same as for discrete log KCDSA except that modular exponentiation is replaced by point multiplication. The specific differences are: