관리 메뉴

너와 나의 스토리

[컴퓨터 보안] Digital Signature - Schnorr Identification/Schnorr signature 본문

Computer Security

[컴퓨터 보안] Digital Signature - Schnorr Identification/Schnorr signature

노는게제일좋아! 2020. 12. 7. 00:11
반응형

Digital Signature의 특성

  • 누가 보낸 건지, 추가로 언제 보낸 건지 확인할 수 있음
  • 서명이 생성될 당시, 메시지의 내용에 대한 확인할 수 있음
  • 제삼자가 분쟁을 해결할 수 있음을 보장

 

Digital Signature 요구 조건

  • 보낸 사람이 보낸 사실을 부인/위조할 수 없어야 함.
  • 서명 생성 및 확인이 쉬워야 한다.
    • private key가 없으면 서명 생성은 어려워야 한다.
  • 기존 디지털 서명을 가지고 새 메시지를 구성하거나, 특정 메시지에 대한 사기 디지털 서명을 구성하여 디지털 서명을 위조하는 것은 계산상 불가능해야 한다.

 

간단한 전자 서명 과정

 

1. 메시지 길이가 길면 -> hash function을 사용해서 압축

2. Bob's private key로 digital signature generation algorithm을 돌림 

3. 그래서 나온 결과를 메시지 뒤에 붙임 

 

 

Schnorr를 설명하기 전 Background

  • Schnorr, DSA같은 서명 알고리즘은 discrete log 문제에 기반하고 있다.
  • Discrete log 문제: [y = $a^x$ mod p]에서 x를 구하는 문제
    • 하단의 그림을 보면, a가 2인 경우, 18개의 모든 원소를 가진다. 이런 값을 generator라고 한다.
    • a가 8인 경우, 6번마다 사이클이 돌며, 이 6개의 원소들을 subgroup이라고 한다.
    • 이러한 성질을 이용해 지수의 크기를 줄일 수 있다.
      • 예: $8^7$ = $8^1$ mod 19
      • 즉, subgroup의 크기가 6이므로, 지수에 mod 6을 취해서 크기를 줄일 수 있다.

 

 

Schnorr Identification

  • : 사용자 인증 프로토콜
  • Challenge-response 방식: 단순히 똑같은 비밀번호를 입력하는 것이 아니라, 주어진 질문에 대해 계산을 해서 답하는 방식
    • 내가 비밀번호를 입력하는 것을 옆에서 누가 몰래 봐도 안전
    • 이 경우, 상대방(나를 인증하는 쪽)이 내 비밀번호(private key)를 알고 있어야 하는 거 아닌가? 상대방이 나의 private key를 아는 것은 불안한뎅...
    • Don't worry! 상대방이 나에 대해 얻어가는 정보는 없다.
      • 이걸 증명하는게  "zero-knowledge proof"
      • public key는 원래 공개되는 거니까 패스
      • "interactive proof protocol"

  • 위의 그림에서 한 가지 문제점이 있다.
    • Bob이 만들어낼 질문, 즉 r이 무엇인지 미리 안다면 Alice가 아닌 다른 사람도 이 테스트를 통과할 수 있다.
    • 이 문제를 해결하기 위해 다음과 같이 바꿀 수 있다.
    • "Fiat-Shamir heuristic" 방식

  • 원래는 r을 받아서 $\Gamma$를 만들어 냈는데, 이제는 처음부터 Alice가 $\Gamma$를 만들어 Bob에게 보낸다.
  • Bob은 M(message)와 $\Gamma$를 넣고 hash를 돌려서 r을 만들어 냄 -> r = H(M||y)
  • 결과적으로, Alice는 Bob에게 ($\Gamma$, y) 쌍을 보내는 것
  • $\Gamma$ 먼저 정하고, Hash에 의해서 r을 생성하기 때문에, a를 가진 Alice만 이 테스트를 통과할 수 있다.
  • Verifier
    1. r = H(M||y) 계산
    2. y = ${\alpha}^yv^r$ mod p 증명

 

Schnorr signature

  • 위의 방식을 살짝 바꾼 것.
  • Proof가 ($\Gamma$, y)로 구성되는 것이 아니라, M: (r, y)로 구성됨 <- 서명
  • Verifier
    • y' = ${\alpha}^yv^r$ mod p 계산
    • r = H(M||y')
  • 순서만 바꾼 것.

 

 

정리

  • Zero knowledge proof의 일종인 Schnorr Identification에 Fiat-Shamir heuristic을 이용해 varifier가 랜덤하게 던져주는 challenge를 메시지에 의존해서 생성되는 hash 값으로 대체해 서명으로 사용할 수 있다.
  • 이것을 Schnorr Signature라고 한다.

 

 

 

 

출처:

- [Cryptography and Network Security: Principles and Practices]

 

 

 

 

반응형
Comments