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.

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

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

• 👁 {\displaystyle x}
  : signer's private signature key such that 👁 {\displaystyle 0<x<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}})}
  .

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}
  : the lower B bits of y.

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

To sign a message 👁 {\displaystyle m}
:

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

The specification is vague about how the integer 👁 {\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))}
using the definition of I2OSP from PKCS#1/RFC3447.

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

• Verifier checks that 👁 {\displaystyle 0\leq r<2^{|q|}}
  and 👁 {\displaystyle 0<s<q}
  and rejects the signature as invalid if not.
• Verifier computes 👁 {\displaystyle e=r\oplus h(z\parallel m)}
  
• Verifier checks if 👁 {\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}
  over a finite field.
• A point 👁 {\displaystyle G}
  in 👁 {\displaystyle E}
  generating a cyclic subgroup of prime order 👁 {\displaystyle q}
  . (👁 {\displaystyle q}
  is often denoted 👁 {\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}
  
• In signature generation, 👁 {\displaystyle r=h(W_{x}||W_{y})}
  where 👁 {\displaystyle W=kG}
  
• In signature verification, the verifier tests whether 👁 {\displaystyle r=h(sY+eG)}
  

• KCDSA specification and analysis