Digital Signatures

1. Digital Signatures

- 메세지 인증과 무결성(Integrity)를 보장

- 암호화가 목적은 아님

- Bob이 자신의 비밀키로 서명한 메세지를 Alice한테 보내면

- Alice는 Bob의 공개키로 서명을 검증

- Bob의 비밀 키를 모른다면 누구도 서명할 수 없어야 함

 

- KeyGen(λ) → (pk, sk) : 입력은 보안 수준 λ, 출력은 pk와 sk

- Sign(sk, M) → σ : 입력은 sk와 메세지 M, 출력은 서명 σ. 즉 이 서명은 비밀키 소유자만 만들 수 있음

- Verify(pk, M, σ) → 1 or 0 : 1이면 서명이 유효, 0이면 서명이 틀리거나 위조됨

- Correctness : Verify(pk,M,Sign(sk,M)) = 1

 

 

2. Security Model for Digital Signatures

- 디지털 서명이 실제로 공격자에게 얼마나 안전한지 평가하기 위해 사용하는 가상의 게임 시나리오

  1) Setup 단계: Challenger C가 키 생성 실행. KeyGen(λ) → (pk,sk)

      공개키 pk를 공격자 A에게 제공

  2) Signing Queries: 공격자 A는 원하는만큼 메세지 Mi​를 지정해 서명 요청

      C는 해당 메시지에 대한 서명 σi = Sign(sk,Mi)를 만들어 반환

  3) Output: 공격자는 자신이 만든 위조 서명 (M,σ)를 제출함

 

- 공격 성공 조건 : Verify(pk,M,σ) = 1이면서 M은 이전에 받은 메세지이면 안됨

- 공격자의 성공 확률이 보안 파라미터 λ에 대해 무시할 만큼 작아야 안전

- 즉, 어떤 공격자 A도 성공 확률이 거의 0에 수렴하면 adaptive chosen message attack에 안전

 

 

3. RSA Signatures

- 원래 암호화 알고리즘이지만 디지털 서명으로도 사용 가능

 

- Key Generation : 

  1) 큰 소수 p, q 선택 → N=pq

  2) φ(N) = (p−1)(q−1) 계산

  3) 공개 지수  e∈Zφ(N)* 선택

  4) d 계산: de ≡ 1 mod φ(N)

  5) 결과: 공개키 pk = (N,e), 비밀키 sk = d

 

- 서명(Sign)과 검증(Verify) :

  1) 메세지 M에 대해 s = M^d (modN), 결과: σ = (M,s)

  2) 받은 서명 (M,s)에 대해 s^e = M modN 이 성립하는지 확인

  3) 성립하면 유효한 서명(1), 아니면 거부(0)

 

- Existential Forgery Attack : 공격자가 비밀키 없이도 유효한 서명을 만들어낼 수 있음

  1) 공격자가 임의의 값 s∈ZN 를 선택

  2) M = s^e (modN) 계산

  3) 서명 σ = (M,s) 출력

  4) 검증해보면 se = M (modN) ⇒ 검증 통과!

 

 

4. PSS 패딩

- RSA의 Existential Forgery 공격을 막기 위한 강력한 서명 포맷

- 서명 메세지에 salt값을 넣어 임의의 s에 대응되는 메세지를 찾기 불가능하게 만듬

  1) 랜덤 salt값 생성 -> 확률적 요소

  2) 정해진 padding에 Hash(M)과 salt를 뒤에 붙여 새로운 메세지 M' 생성

  3) H = Hash(M′) 계산

  4) PS(0으로 채워짐)와 0x01, salt를 붙여 DB를 만듬

  5) MGF(H) 계산

  6) MGF(H) ⊕ DB를 계산해 maskedDB를 얻음

  7) EM = maskedDB || H || TF(고정값)이 실제로 RSA로 서명할 대상 데이터

  8) s = (EM)^d mod N

 

- Verify :

  1) s^e = EM modN 계산

  2) EM을 maskedDB, H, TF로 나눈 후 TF가 올바른지 확인

  3) DB = MGF(H) ⊕ masedDB를 계산

  4) DB에서 PS, 0x01, salt를 구한 후, PS와 0x01이 올바른지 확인

  5) mHash = Hash(M)을 계산하고, M' = 80x00 || mHash || salt로 세팅

  6) H = Hash(M')인지 확인한다. 성립하면 1, 아니면 0 출력

 

 

5. ElGamal Signatures

- Key Generation :

  1) 큰 소수 p 선택

  2) Zp∗*의 생성자 g 선택

  3) 비밀키 x∈{2,…,p−2} 선택

  4) 공개키 X= g^x (mod p)

  5) 공개키: (p,g,X), 비밀키 x

 

- Sign(주어진 메세지 M에 대해) :

  1) k∈Z(p−1)* 랜덤 선택

  2) r = g^k mod p

  3) s = (M − rx)⋅k^−1 mod(p−1)

  4) 서명 결과: σ = (M, r, s)

 

- Verify(받은 서명과 공개키로) :

  1) t = X^r⋅r^s mod p

  2) t = g^M mod p가 맞는지 확인

 

- Existential Forgery Attack : 공격자가 비밀키 없이도 유효한 서명을 만들어낼 수 있음

  1) 임의의 정수 i,j 선택 (단, gcd⁡(j, p−1) = 1)

  2) r = g^i⋅X^j  mod p

  3) s = −rj^−1 mod(p−1)

  4) M = si mod(p−1)

  5) 서명 결과: σ = (M,r,s)

 

- 보안 강화 방법 : 원본 메시지 M 대신 H(M)에 서명

 

 

6. DSA Signatures

- Parameter Generation : 

  1) Select a 2λ-bit prime q

  2) Select a random l

  3) Compute p = 2lq + 1

  4) Check if p is prime. If not go to 2

  5) Select a random g from Zp(차수가 q인 부분군의 생성자여야 함)

  6) Compute g = g^(p-1/q) = (g^2l)

  7) Check if g=1. If yes, go to 5

  8) Output (p,q,g)

 

- Key Generation : 

  1) 비밀키 x∈Zq*  임의로 선택

  2) 공개키 X = g^x mod p

  3) 공개키: (p,q,g,X), 비밀키: x

 

- Sign (주어진 메세지 M에 대해) :

  1) 임의 k∈Zq* 선택

  2) r = (g^k mod p) mod q

  3) s = (H(M) + x⋅r)⋅k^−1 mod q

  4) 서명 결과: σ = (M, (r,s))

 

- Verify(받은 서명과 공개키로) : 

  1) w = s^−1 mod q

  2) u1​ = H(M)⋅w mod q

  3) u2 = r⋅w mod q

  4) ν = (g^u1⋅X^u2  mod  p) mod  q

  5) v = r mod q 성립하면 서명 유효