15. 각종 암호학 알고리즘 정리

Diffie-Hellman Key Exchange

공개값

q = 큰 소수

α = 원시근

 

비대칭키 생성

Xa = random value (1 < Xa < q-1)

Ya = α^Xa mod q

 

대칭키 생성

K = Yb^Xa mod q

 

 

ElGamal Cryptography

공개값

q = 큰 소수

α = 원시근

 

비대칭키 생성

Xa = random value (1 < Xa < q-1)

Ya = α^Xa mod q

 

암호화

k = random value (1 < k < q-1)

K = Ya^k mod q

C1 = α^k mod q

C2 = KM mod q

(C1, C2)가 암호문

 

복호화

K = C1^Xa mod q

M = C2*K^-1 mod q

 

 

RSAES-OAEP

메시지 암호화

DataBlock = Hash(L) || Padding String || 01 || Message (2048bit)

Seed = Random Value (len(hash function))

MaskedDataBlock = DataBlock XOR MGF(Seed)

MaskedSeed = Seed XOR MGF(MaskedDataBlock)

Encoded Message = 00(bytes) || MaskedSeed || MaskedDataBlock 

 

메시지 복호화

Seed = MaskedSeed XOR MGF(MaskedDataBlock)

DataBlock = MaskedDataBlock XOR MGF(Seed)

 

 

RSASSA-PSS

서명

M' = 00000000(bytes) || H(M) || salt (salt = len(hash function))

DB = 0000...1 || salt (총길이 = 2048bit - Hashlen - 8)

maskedDB = DB XOR MGF(H(M'))

EM = maskedDB || H(M') || TF (bytes) // 만약 맨 왼쪽 비트가 1이라면 0으로 바꾼다.

 

검증

DB = maskedDB XOR MGF(H(M'))

M'' = 00000000(bytes) || H(M) || salt

M' == M'' 라면 검증 완료

 

 

Elgamal Digital Signature

키 생성

Xa = random value (1 < Xa < q-1)

Ya = α^Xa mod q

 

서명

H(M) (0 < H(M) < q)

K = random vlaue (0 < K < q && gcd(K, q-1) = 1)

S1 = α^K mod q

S2 = K^-1 (H(M) - Xa * S1) mod (q-1)

(S1, S2)가 서명

 

검증

V1 = α^(H(M)) mod q

V2 = Ya^S1 * S1^S2 mod q

V1 == V2 라면 검증 완료

 

 

Schonorr Digital Signatures

기본값

적절한 소수 p, q 선택

α 선택 (α^q ≡ 1 mod p)

 

키생성

개인키 s 선택 (0 < s < q)

공개키 v = α^(-s) mod p

 

서명

r 선택 (0 < r < q)

x = α^r mod p

e = H(M || x)

y = (r + se) mod q

(e, y)가 서명

 

검증

x' = α^y * v^e mod p

e == H(M || x') 라면 검증 완료

 

 

Digital Signature Standard - DSS

공개값

p = 큰 소수 (2^(L-1) < p < 2^L)

q = p-1의 소인수 중 하나

h = random value (1 < h < p)

g = h^((p-1)/q) mod p (g != 1) g는 p의 원시근

 

키생성

개인키 x 선택 ( x < q )

공개키 y = g^x mod p

 

서명

k = random value (k < q)

r = (g^k mod p) mod q

s = k^-1 * (H(M) + xr) mod q

(r,s)가 서명이 된다.

 

검증

w = s^-1 mod q

u1 = H(M) * w mod q

u2 = rw mod q

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

v == r이면 검증 완료

 

 

ECDSA

점 간의 덧셈

a!=b,
   c.x = ((b.y - a.y) / (b.x - a.x))^2 - b.x - a.x
   c.y = ((b.y - a.y) / (b.x - a.x))(a.x - c.x) - a.y

a==b,
   c.x = ((3 * a.x + a) / (2 * a.y))^2 - 2 * a.x
   c.y = ((3 * a.x + a) / (2 * a.y))(a.x - c.x) - a.y

 

공개값

q = 큰 소수 또는 2의 거듭제곱 (유한 타원곡선의 크기)

n = 큰 소수 (점의 개수)

G = 기저점 (nG = O)

 

키생성

d = random value ( d<n )

Q = dG

 

서명

e = H(m), 만약 e가 n보다 비트상 길이가 길다면 뒤를 잘라냄

k = random value (1 < k < n)

(x1, y1) = kG

r = x1 mod n

s = k^-1 (e+rd) mod n

(r,s)가 서명이 된다.

 

검증

0 < r,s < n 이 아니라면 잘못된 서명

e = H(m)

u1 = es^-1 mod n

u2 = rs^-1 mod n

(x1, y1) = u1G + u2Q

(x1, y1) = O 이면 잘못된 서명

r ≡ x1 (mod n) 이면 검증 완료