Misplaced Pages

KCDSA

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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 G F ( p ) {\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.

Domain parameters

  • p {\displaystyle p} : a large prime such that | p | = 512 + 256 i {\displaystyle |p|=512+256i} for i = 0 , 1 , … , 6 {\displaystyle i=0,1,\dots ,6} .
  • q {\displaystyle q} : a prime factor of p − 1 {\displaystyle p-1} such that | q | = 128 + 32 j {\displaystyle |q|=128+32j} for j = 0 , 1 , … , 4 {\displaystyle j=0,1,\dots ,4} .
  • g {\displaystyle g} : a base element of order q {\displaystyle q} in GF ⁡ ( p ) {\displaystyle \operatorname {GF} (p)} .

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

User parameters

  • x {\displaystyle x} : signer's private signature key such that 0 < x < q {\displaystyle 0<x<q} .
  • y {\displaystyle y} : signer's public verification key computed by y = g x ¯ ( mod p ) , {\displaystyle y=g^{\bar {x}}{\pmod {p}},} where x ¯ = x − 1 ( mod q ) {\displaystyle {\bar {x}}=x^{-1}{\pmod {q}}} .
  • z {\displaystyle z} : a hash-value of Cert Data, i.e., z = h ( Cert Data ) {\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.

  • z {\displaystyle z} : the lower B bits of y.

Hash Function

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

Signing

To sign a message m {\displaystyle m} :

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

The specification is vague about how the integer w {\displaystyle 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 ( I 2 O S P ( w , | q | / 8 ) ) {\displaystyle r=h(I2OSP(w,|q|/8))} using the definition of I2OSP from PKCS#1/RFC3447.

Verifying

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

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

External links


Stub icon

This cryptography-related article is a stub. You can help Misplaced Pages by expanding it.

Categories: