[암호학 둘러보기](11)[전자 서명 2]

ElGamal 서명: D-H 알고리즘의 발전형

디피-헬만 알고리즘에서 사용했던 (g, p, y)를 사용하면서 서명기능까지 있다!

• 과정
  큰 소수 p와, g, 비밀키 x선택 (단, 1<= x <= p-2)
  y = g^x (mod p) 계산
  공개키: (p, g, y), 개인키: x이후 서명 검증
  y^r*r^s (mod p)= g^M' (mod p)라면 유효함
  
  서명(r, s)
  해싱: M -> M'
  랜덤값 k를 선택 (단 1 <= k <= p-2이고, k, p는 서로소)
  r = g^k (mod p)
  s = k^(-1)(M' - xr) (mod p-1) (단, k^(-1)은 mod p-1에서 곱셈 역원)
• 예
  앨리스가 밥에게 서명과 메세지를 보낸다고 한다. 파라미터는 g = 7, p = 11을 합의해놨다. (편의를 위해 작은 소수로 정함.)
  앨리스의 개인키 = 3, 밥의 개인키 = 4
  앨리스의 공개키 = 7^3 (mod 11) = 2 = y
  밥의 공개키 = 7^4 (mod 11) = 3
  
  앨리스는 k로 9를 선택했고 메세지 8을 보낼 것이다.
  해싱: 8 -> 10 (이것도 대충 정한거)
  r = 7^2 (mod 11) = 5
  s = 9^(-1)\*(10 - 3\*5) (mod 10) = 9 * (-5) (mod 10) = 45 (mod 10) = 5
  따라서 서명은 (5, 5)
  
  공개된 (g, p, y), (r, s)로 검증
  2^5 * 5^5 (mod 11) = 3125 (mod 11) = 1
  7^10 (mod 11) = 282475249 (mod 11) = 1
  둘이 같으므로 올바른 서명이다.
  
  
• 블라인드 서명: 메세지 내용을 모른채 서명
  메세지 내용을 알리고 싶지 않으나 인증을 받고 싶을 때 사용. (전자결제, 전자투표 등)
  그러나 상대가 메세지에 대해 아무것도 모른채 서명하므로 악용 가능