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 , 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

edit
  •  : a large prime such that   for  .
  •  : a prime factor of   such that   for  .
  •  : a base element of order   in  .

The revised version of the spec additional requires either that   be prime or that all of its prime factors are greater than  .

User parameters

edit
  •  : signer's private signature key such that  .
  •  : signer's public verification key computed by   where  .
  •  : a hash-value of Cert Data, i.e.,  .

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.

  •  : the lower B bits of y.

Hash Function

edit
  •  : a collision resistant hash function with |q|-bit digests.

Signing

edit

To sign a message  :

  • Signer randomly picks an integer   and computes  
  • Then computes the first part:  
  • Then computes the second part:  
  • If  , the process must be repeated from the start.
  • The signature is  

The specification is vague about how the integer   be reinterpreted as a byte string input to hash function. In the example in section C.1 the interpretation is consistent with   using the definition of I2OSP from PKCS#1/RFC3447.

Verifying

edit

To verify a signature   on a message  :

  • Verifier checks that   and   and rejects the signature as invalid if not.
  • Verifier computes  
  • Verifier checks if  . If so then the signature is valid; otherwise it is not valid.

EC-KCDSA

edit

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

The domain parameters are:

  • An elliptic curve   over a finite field.
  • A point   in   generating a cyclic subgroup of prime order  . (  is often denoted   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  
  • In signature generation,   where  
  • In signature verification, the verifier tests whether  
edit