Recent Posts
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 코루틴 컨텍스트
- preemption #
- 겨울 부산
- JanusWebRTC
- terminal
- pytest
- addhooks
- 개성국밥
- Value too long for column
- 깡돼후
- RouteLocator
- JanusGateway
- python
- Spring Batch
- 자원부족
- mp4fpsmod
- PytestPluginManager
- JanusWebRTCGateway
- ErrorResponse
- vfr video
- PersistenceContext
- tolerated
- kotlin
- 코루틴 빌더
- taint
- table not found
- JanusWebRTCServer
- gitflow-shFlags
- VARCHAR (1)
- 달인막창
Archives
너와 나의 스토리
[컴퓨터 보안] 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
- r = H(M||y) 계산
- 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]
반응형
'Computer Security' 카테고리의 다른 글
Block Chain이란? (0) | 2020.12.07 |
---|---|
[컴퓨터 보안] Key Management and Distribution (0) | 2020.12.07 |
[컴퓨터 보안] Message Authentication Code / HMAC(Hash MAC) / CMAC(Cipher-based MAC) / Authenticated Encryption(CCM/GCM) (0) | 2020.12.04 |
Public-Key Cryptosystems - Diffie-Hellman/Elgamal cryptographic system/Elliptic curve cryptography (0) | 2020.12.03 |
[컴퓨터 보안] Attack against RSA(RSA 공격하기) (0) | 2020.12.02 |
Comments