KCDSA explained

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 + 256 i for i = 0 , 1 , ... , 6 .q : a prime factor of p -1 such that |q| = 128 + 32 j for j = 0 , 1 , ... , 4 .g : a base element of order q in \operatorname{GF}(p) .

The revised version of the spec additional requires either that

(p -1 )/( 2 q) 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( CertData ) .

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 ⊕ 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(I 2 OSP(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 ^{|q|} and 0 < s < q and rejects the signature as invalid if not.

• Verifier computes

e = r ⊕ h(z \parallel m)

• Verifier checks if

r = h(y ^{s} ⋅ 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:

• The public key is

Y = \bar{x}G

• 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