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).

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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

Domain parameters

p : a large prime such that |p| = 512 + 256i for i = 0, 1, \dots, 6 . q : a prime factor of p-1 such that |q| = 128 + 32j for j = 0, 1, \dots, 4 . g : a base element of order q in \operatorname{GF}(p) . The revised version of the spec additional requires either that (p-1)/(2q) be prime or that all of its prime factors are greater than q .

User parameters

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

Hash Function

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

Signing

To sign a message m : Signer randomly picks an integer 0 and computes w = g^k \mod{p} Then computes the first part: r = h(w) Then computes the second part: s = x(k - r \oplus h(z \parallel m)) \pmod{q} If s=0 , the process must be repeated from the start. The signature is (r, s) The specification is vague about how the integer w be reinterpreted as a byte string input to hash function.

In the example in section C.1 the interpretation is consistent with r = h(I2OSP(w, |q|/8)) using the definition of I2OSP from PKCS#1/RFC3447.

Verifying

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

KCDSA specification and analysis

Text derived from https://en.wikipedia.org/w/index.php?oldid=1304974773 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.