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(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 \pmod,$ where $\bar=x^ \pmod$.
* $z$: a hash-value of ''Cert Data'', i.e., $z = h(\text)$.

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$
* Then computes the first part: $r = h(w)$
* Then computes the second part: $s = x(k - r \oplus h(z \parallel m)) \pmod$
* 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 \le r < 2^$ 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)$. 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:
* The public key is $Y=\barG$
* In signature generation, $r=h(W_x , , W_y)$ where $W=kG$
* In signature verification, the verifier tests whether $r=h(sY+eG)$

External links

KCDSA specification and analysis

Digital signature schemes
Elliptic curve cryptography
Public-key cryptography
Standards of South Korea

{{crypto-stub