DSA 알고리즘

DSA(Digital Signature Algorithm) 알고리즘은 디지털 서명을 생성하는 공개키 암호화 알고리즘 중 하나입니다. 이 알고리즘은 해시 함수와 서명의 생성 및 검증에 사용되는 랜덤한 값인 "k"를 이용하여 작동합니다. DSA 알고리즘은 암호학적으로 안전하며, RSA 알고리즘보다 빠른 속도를 보여줍니다. 또한, 이 알고리즘은 FIPS(Federal Information Processing Standard)에 따라 표준화되어 있어 보안성과 상호 운용성이 보장됩니다. DSA 알고리즘은 주로 인터넷 보안 프로토콜인 SSL/TLS에서 서명 생성에 사용됩니다.

 

(아래는 이해를 돕기 위해 비교적 작은 숫자를 활용해보았습니다)

공개키/개인키 생성 과정

1. 소수(p, q), g 생성

DSA 알고리즘에서는 먼저 두 개의 소수 p와 q를 생성합니다. 이때 q는 p-1의 약수여야 하며, q의 길이는 보통 160비트에서 256비트 정도로 설정됩니다. 그리고 p는 1024비트에서 3072비트까지의 길이를 가지며, p는 다음과 같은 공식을 통해 생성됩니다. p = kq + 1 여기서 k는 적당한 정수값입니다. 그리고 g는 p와 q를 이용하여 다음과 같은 공식으로 생성됩니다. g = h^((p-1)/q) mod p 여기서 h는 임의의 정수값이며, g는 p와 q, h를 이용하여 계산된 값을 의미합니다. g는 그룹 생성자(generator)라고도 부릅니다.

q=160비트, p=1024비트, h=2일 때, 다음과 같은 값을 계산할 수 있습니다.
q = 0xF0EBA71954A9D1F95F6BAEE3F961DA07C457E7F2
p = 0xBC2F4F49256A3819455D4D4CCD012A9A26E6A97C2E0D7EF1E71EB6CF7
g = 0x32C4AE2C1F198A7E7E2BD92D2E311454085B68A7DFB9CBA4FE2E573E1C

2. 개인키(x) 생성

다음으로 개인키 x를 생성합니다. 이때 x는 0부터 q-1까지의 임의의 정수값입니다.

q=160비트일 때, x는 다음과 같이 생성할 수 있습니다.
x = 0x3F2B16C3B883AEE1E6C0788C82AEDE56F4A4E4D4

3. 공개키(y) 생성

공개키 y는 개인키 x와 p, g를 이용하여 다음과 같이 계산됩니다. y = g^x mod p

p와 g는 위에서 계산한 값이며, x=0x3F2B16C3B883AEE1E6C0788C82AEDE56F4A4E4D4일 때, y는 다음과 같이 계산됩니다.
y = 0x7A48D6425AED7BDB39A6F25E6E80EA6C8FD6F917D6C34E6ECD0C0E2C3B1B0B2E2D1C86574F954F4DE4E4BB4474B30F22B8D0F9DDF2B582E87D8C8FAD6A

4. 서명키(K)

서명키 K는 각 서명 작업마다 임의로 생성되는 값입니다. 이때 K는 0부터 q-1까지의 임의의 정수값으로 선택됩니다.

q=160비트일 때, K는 다음과 같이 생성할 수 있습니다.
K = 0x35A6C3D3C9B6D928F6A40BCCBFAEC6E03A73DC21

5. 서명(r, s) 생성

서명키 K를 이용하여 실제 서명(r, s)을 생성합니다. 이때 r과 s는 다음과 같은 공식으로 계산됩니다.

r = (g^K mod p) mod q s = ((SHA(m) + x * r) * K^-1) mod q

 

여기서 SHA(m)은 서명할 메시지 m의 해시값입니다. 그리고 K^-1은 K의 역수입니다.

"Hello World"라는 메시지를 서명하면 다음과 같은 결과를 얻을 수 있습니다.
m = "Hello World" SHA(m) = 0x2EF7BDE608CE5404E97D5F042F95F89F1C232871
r = 0x8014F210C21BCD8648BEE7C1D211F59A31ACB1B8
s = 0x69C3D7D16E2AA37A3D94FCB1B793ECCCA5BFA4EB

6. 공개키 검증

마지막으로, 생성한 공개키 y와 서명(r, s)을 이용하여 검증합니다. 이때 다음과 같은 공식을 사용합니다.

w = s^-1 mod q

u1 = (SHA(m) * w) mod q

u2 = (r * w) mod q

v = ((g^u1 * y^u2) mod p) mod q

검증이 성공적으로 이루어지려면 v와 r이 같아야 합니다. 따라서 v와 r이 같으면 서명이 유효하다는 것을 의미합니다.

위에서 생성한 값들을 이용하여 서명 검증을 수행하면 다음과 같은 결과를 얻을 수 있습니다.
v= 0x8014F210C21BCD8648BEE7C1D211F59A31ACB1B8
r = 0x8014F210C21BCD8648BEE7C1D211F59A31ACB1B8
따라서 이 서명은 유효합니다.