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)}${\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.

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

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

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

• ${\displaystyle z}${\displaystyle z}: the lower B bits of y.

• ${\displaystyle h}${\displaystyle h}: a collision resistant hash function with |q|-bit digests.

To sign a message ${\displaystyle m}${\displaystyle m}:

• Signer randomly picks an integer ${\displaystyle 0<k<q}${\displaystyle 0<k<q} and computes ${\displaystyle w=g^{k}\mod {p}}${\displaystyle w=g^{k}\mod {p}}
• Then computes the first part: ${\displaystyle r=h(w)}${\displaystyle r=h(w)}
• Then computes the second part: ${\displaystyle s=x(k-r\oplus h(z\parallel m)){\pmod {q}}}${\displaystyle s=x(k-r\oplus h(z\parallel m)){\pmod {q}}}
• If ${\displaystyle s=0}${\displaystyle s=0}, the process must be repeated from the start.
• The signature is ${\displaystyle (r,s)}${\displaystyle (r,s)}

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

To verify a signature ${\displaystyle (r,s)}${\displaystyle (r,s)} on a message ${\displaystyle m}${\displaystyle m}:

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

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

The domain parameters are:

• An elliptic curve ${\displaystyle E}${\displaystyle E} over a finite field.
• A point ${\displaystyle G}${\displaystyle G} in ${\displaystyle E}${\displaystyle E} generating a cyclic subgroup of prime order ${\displaystyle q}${\displaystyle q}. (${\displaystyle q}${\displaystyle q} is often denoted ${\displaystyle n}${\displaystyle 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 ${\displaystyle Y={\bar {x}}G}${\displaystyle Y={\bar {x}}G}
• In signature generation, ${\displaystyle r=h(W_{x}||W_{y})}${\displaystyle r=h(W_{x}||W_{y})} where ${\displaystyle W=kG}${\displaystyle W=kG}
• In signature verification, the verifier tests whether ${\displaystyle r=h(sY+eG)}${\displaystyle r=h(sY+eG)}

• KCDSA specification and analysis

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

• All stub articles