View source for 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 signature scheme|ElGamal]] variant, similar to the [[Digital Signature Algorithm]] and GOST R 34.10-94.  The standard algorithm is implemented over <math>GF(p)</math>, 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==
* <math>p</math>: a large prime such that <math>|p| = 512 + 256i</math> for <math>i = 0, 1, \dots, 6</math>.
* <math>q</math>: a prime factor of <math>p-1</math> such that <math>|q| = 128 + 32j</math> for <math>j = 0, 1, \dots, 4</math>.
* <math>g</math>: a base element of order <math>q</math> in <math>\operatorname{GF}(p)</math>.

The revised version of the spec additional requires either that <math>(p-1)/(2q)</math> be prime or that all of its prime factors are greater than <math>q</math>.

==User parameters==
* <math>x</math>: signer's private signature key such that <math>0 < x < q</math>.
* <math>y</math>: signer's public verification key computed by <math>y=g^\bar{x} \pmod{p},</math> where <math>\bar{x}=x^{-1} \pmod{q}</math>.
* <math>z</math>: a hash-value of ''Cert Data'', i.e., <math>z = h(\text{Cert Data})</math>.

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.

* <math>z</math>: the lower B bits of y.

==Hash Function==
* <math>h</math>: a collision resistant hash function with |q|-bit digests.

==Signing==

To sign a message <math>m</math>:

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

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

==Verifying==

To verify a signature <math>(r, s)</math> on a message <math>m</math>:

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

==External links==
* [https://web.archive.org/web/20190227223049/http://pdfs.semanticscholar.org/87b2/b3699c14fd165e3f4ee9c5a307863b8cc235.pdf KCDSA specification and analysis]

[[Category:Digital signature schemes]]
[[Category:Elliptic curve cryptography]]
[[Category:Public-key cryptography]]
[[Category:Standards of South Korea]]


{{crypto-stub}}