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 [math]\displaystyle{ 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]\displaystyle{ p }[/math]: a large prime such that [math]\displaystyle{ |p| = 512 + 256i }[/math] for [math]\displaystyle{ i = 0, 1, \dots, 6 }[/math].
- [math]\displaystyle{ q }[/math]: a prime factor of [math]\displaystyle{ p-1 }[/math] such that [math]\displaystyle{ |q| = 128 + 32j }[/math] for [math]\displaystyle{ j = 0, 1, \dots, 4 }[/math].
- [math]\displaystyle{ g }[/math]: a base element of order [math]\displaystyle{ q }[/math] in [math]\displaystyle{ \operatorname{GF}(p) }[/math].
The revised version of the spec additional requires either that [math]\displaystyle{ (p-1)/(2q) }[/math] be prime or that all of its prime factors are greater than [math]\displaystyle{ q }[/math].
User parameters
- [math]\displaystyle{ x }[/math]: signer's private signature key such that [math]\displaystyle{ 0 \lt x \lt q }[/math].
- [math]\displaystyle{ y }[/math]: signer's public verification key computed by [math]\displaystyle{ y=g^\bar{x} \pmod{p}, }[/math] where [math]\displaystyle{ \bar{x}=x^{-1} \pmod{q} }[/math].
- [math]\displaystyle{ z }[/math]: a hash-value of Cert Data, i.e., [math]\displaystyle{ 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]\displaystyle{ z }[/math]: the lower B bits of y.
Hash Function
- [math]\displaystyle{ h }[/math]: a collision resistant hash function with |q|-bit digests.
Signing
To sign a message [math]\displaystyle{ m }[/math]:
- Signer randomly picks an integer [math]\displaystyle{ 0 \lt k \lt q }[/math] and computes [math]\displaystyle{ w = g^k \mod{p} }[/math]
- Then computes the first part: [math]\displaystyle{ r = h(w) }[/math]
- Then computes the second part: [math]\displaystyle{ s = x(k - r \oplus h(z \parallel m)) \pmod{q} }[/math]
- If [math]\displaystyle{ s=0 }[/math], the process must be repeated from the start.
- The signature is [math]\displaystyle{ (r, s) }[/math]
The specification is vague about how the integer [math]\displaystyle{ 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]\displaystyle{ r = h(I2OSP(w, |q|/8)) }[/math] using the definition of I2OSP from PKCS#1/RFC3447.
Verifying
To verify a signature [math]\displaystyle{ (r, s) }[/math] on a message [math]\displaystyle{ m }[/math]:
- Verifier checks that [math]\displaystyle{ 0 \le r \lt 2^{|q|} }[/math] and [math]\displaystyle{ 0 \lt s \lt q }[/math] and rejects the signature as invalid if not.
- Verifier computes [math]\displaystyle{ e = r \oplus h(z \parallel m) }[/math]
- Verifier checks if [math]\displaystyle{ 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]\displaystyle{ E }[/math] over a finite field.
- A point [math]\displaystyle{ G }[/math] in [math]\displaystyle{ E }[/math] generating a cyclic subgroup of prime order [math]\displaystyle{ q }[/math]. ([math]\displaystyle{ q }[/math] is often denoted [math]\displaystyle{ 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]\displaystyle{ Y=\bar{x}G }[/math]
- In signature generation, [math]\displaystyle{ r=h(W_x || W_y) }[/math] where [math]\displaystyle{ W=kG }[/math]
- In signature verification, the verifier tests whether [math]\displaystyle{ r=h(sY+eG) }[/math]
External links
 |  |
