Digital Signature은 message authentication을 위한 보안 기술로, 메시지를 교환하는 2개의 parties를 third party로부터 보호해주지만, 메시지를 교환하는 당사자들 사이의 authentication은 보장하지 않는다.
Digital signature은 1) signature의 author, date, time을 verify하고 2) 메시지 내용을 authenticate 하며
3) third party가 이를 검증하게 해 dispute resolution(분쟁 해결)을 할 수 있다.
Attack and Forgeries
Attacks
1) Key-only attack: signature이 attacked 당하는 A의 public key만 알고 있다.
2) Known message attack: 메시지, signature의 쌍에 접근할 수 있다.
3) Generic chosen message attack: 공격자는 공격 전에 A의 public key와 independent한 list of messages를 선택한 후, 해당 메시지에 대한 A의 valid signature을 얻어낸다.
4) Directed chosen message attack: 공격자는 A의 public key를 알고, list of messages에 대한 서명을 A의 public key로부터 얻어낸다. Generic chosen message attack 은 어떤 메시지에 대해서도 서명을 얻을 수 있는 반면, Directed chosen message attack은 특정한 메시지에 대한 서명을 목표로 한다.
5) Adaptive chosen message attack: 공격자는 A를 oracle로 사용하여, 이전에
Forgeries(위조)
- Total break: 암호화 시스템의 보안을 완전히 파괴하는 능력 → digital signature에 사용된 private key를 결정하는 방법
- Universal forgery: arbitrary message에 대한 signature을 만들기 위해 efficient 한 알고리즘을 찾는 것
- Selective forgery: chosen 메시지에 대한 signature을 위조. 이는 weak collision hash와 관련이 있다.
- Existential forgery: 최소한 하나의 메시지에 대한 signature을 위조. 이는 strong collision hash와 관련이 있으며, 특정 메시지를 제어하지는 못한다.
Digital Signature Requirements
1) digital signature은 특정 메시지에 의존하여 생성되어야 하고, 메시지의 내용이 변경되면 signature도 변경되어야 한다.
2) sender에게 고유한 정보를 사용하여 forgery, denial 을 막아야 한다.
3) 상대적으로 produce하기 쉬워야 한다.
4) recognize, verify하기 상대적으로 쉬워야 한다.
5) forge하기 computationally infeasible 해야한다. 이는 주어진 전자서명에 대해 새로운 메시지를 만드는 것이나 / 특정 메시지에 대해 위조된 전자 서명을 만드는 것이 어려워야 한다는 것을 뜻한다.
6) storage에 전자서명을 저장하는 것이 practical 해야한다.
Direct Digital Signatures
Direct digital signatures는 송신자와 수신자만 포함하는 전자서명 과정을 말한다.
<특징>
1) 이는 receiver이 sender의 public key를 가지고 있다고 가정한다.
2) sender은 private key로 전체 메시지 또는 메시지의 해시 값을 서명하여 sender의 신원을 증명한다.
3) confidentiality를 위해 receiver의 public key를 이용해 encrypt 할 수 있다.
4) dispute handling을 위해 sender은 sign 후 메시지와 서명을 encrypt 할 수 있다.
5) 보안은 sender의 private key에 달려있다.
ElGamal Digital Signatures
ElGamal digital signatures는 ElGamal 알고리즘을 기반으로 하는 variant로, finite GF에서 exponentiation을 사용한다. 이는 ElGamal 알고리즘을 기반으로 하였기 때문에, discrete logarithm의 difficulty에 기반한 security를 제공한다.
이는 encryption에 private key를 쓰고(signing) / decryption에 public key를 쓴다(verification).
<작동 방식>
1. 각 유저가 자신의 키를 생성한다. 어떠한 임의의 사용자를 A라고 가정하자.
2. A는 메시지 M을 computing 하여 메시지에 sign 한다.
3. any user B가 computing 하여 signature을 verify 한다.
*** 증명
*** 예제
Schnorr Digital Signatures
Schnorr Digital Signatures 또한 finite GF 에서 exponentiation 을 사용하므로, security가 discrete logarithms difficulty에 기반한다. 이는 message에 dependent 한 computation을 최소화하여, 작업이 idle time(유효 시간)내에 수행될 수 있도록 하며, message dependent 한 부분은 2n bit integar과 n bit integar을 곱하는 작업을 요구한다.
이는 prime modulus p 에 기반하며, p-1은 주로 prime number인 q를 factor로 갖는다. p는 주로 1024-bit 숫자, q는 주로 160-bit 숫자이다.
<Key Setup>
1. prime p, q를 고르고 q는 p-1의 prime factor여야 한다.
2. a^q = 1 mod p인 a를 선정한다. (a,p,q)는 전역적인 global public parameters에 해당한다.
3. 각 user이 key를 생성한다.
1) 0<s<q인 secret key(number) s를 고른다.
2) Public Key 생성
<Signature>
1. 유저는 메시지에 다음과 같이 서명한다.
1) 0<r<q인 random r 을 선정한 후 , x를 compute 한다.
2) 메시지와 x를 concatenate 하고, 해시한다.
3) compute: y = ( r + se ) mod q
4) signature은 (e,y)의 쌍이다.
** 증명
Digital Signature Standard (DSS)
DSS는 NIST, NSA에서 90년대 초 공동으로 개발한 전자 서명 알고리즘이다.
<특징>
1) 91년 FIPS-186에 publish 되어 93, 96, 2000년도에 개정되었다.
2) 이는 SHA 해시 알고리즘을 쓰고, DSA 디지털 서명 알고리즘을 사용한다.
3) FIPS-186은 RSA, ellipyic curve cryptography에 기반한 DSA를 포함한다.
4) RSA와 다르게, DSA는 encryption이나 key exchange에 사용될 수 없다.
- DSS에서 서명 생성 시 마지막에 수행되는 테스트는 r이라는 값에 대한 것으로, 이는 메시지에 전혀 depend 되지 않는다.
- signature generation에서 computationally demanding task는 다음의 exponential calculation이다.
- 메시지에 의존하지 않는 r과 k^-1 값은 사용자가 서명 생성 전 precalculatae 하여 서명 생성에 사용되는 계산 비용을 줄일 수 있다.
Digital Signature Algorithm (DSA)
<특징>
1) 512, 1024-bit security로 320-bit signature을 생성한다. 이는 높은 안전성을 가진다.
2) RSA와 비교하여 알고리즘이 훨씬 작고 빠르게 동작한다: RSA는 일반적으로 더 큰 크기의 키를 필요로 한다 (1024비트 이상). 하지만 해당 알고리즘은 320 bit의 키를 이용하면 된다.
3) 디지털 서명 전용 scheme이다. 따라서 암호화나 키 교환에는 사용되지 않는다.
4) security는 discrete logarithm difficulty에 기반한다.
5) ElGmal, Schnorr scheme의 variant이다.
<Key Generation>
1) global public key value (p, q, g)를 생성한다.
① 큰 prime nnumber p를 선정한다. 이 때 2^(L-1) < p < 2^L 이어야 하는데, L은 512 또는 1024 bit이고 64의 배수이다.
② q는 160 bit prime number이다. 이 때 q는 p-1의 factor이다.
③ g 선정
2) private key를 정하고, public key를 compute 한다.
<Signature Creation>
sender이 메시지 M에 서명하기 위해서는
1) random signature key k를 생성한다. (단 k<q) 이 k는 한번 사용되면 바로 파기되며, 절대 재사용되지 않는다.
2) signature pair을 compute
3) signature (r,s)를 메시지 M과 함께 전송한다.
<Signature verification>
Public Key Certificate
개인의 public key를 다른 사람에게 보내기 위해서는, key를 community에 broadcast 한다. 이는 편리하지만 누구나 announcement를 forge할 수 있다.
이 문제점을 해결하기 위해 public key certificate를 사용한다. public key certificate는 public key에 key owner의 ID를 추가하는 것으로, 이는 신뢰할 수 있는 third-party인 CA(Certificate Authority)에 의해 RSA, DSA 등의 알고리즘을 이용하여 전체 block이 서명된다.
X. 509는 universial 하게 accept 된 public-key certificate로 거의 모든 네트워크 보안 application(e.g. IPsec, TLS, SSH, S/MIME 등)에 사용된다.
Group Signature
Group signature은 특정 그룹을 대표하여 한 명의 멤버가 익명으로 메시지에 사인하도록 허용하는 것이다.
verifier은 메시지가 그룹 멤버 중 한명에 의해 서명된 것은 알지만, 누가 서명했는지는 알 수 없다.
group manager은 그룹 멤버를 추가하는 역할을 하며, dispute 발생 시 서명을 누가 했는지를 밝혀낼 수 있다.
<주요 특징>
1) Unforgeability: 그룹 멤버만이 메시지에 서명을 할 수 있다.
2) Anonymity/ Traceability: 그룹 멤버 중 누가 서명을 했는지 그룹 매니저 이외에는 알 수가 없다.
3) Unlinkability: 2개의 서명이 같은 그룹 멤버에 의해 서명된 것인지 알아낼 수 없다.
4) Security against framing attacks: 한 그룹 멤버는 다른 그룹 멤버를 대신하여 메시지에 서명할 수 없다.
Ring Signature
- R. Rivest, A. Shamir, Y. Tauman, “How to leak a secret”, Asiacrypt 2001
Ring Signature은 Group signature과 비슷하지만, 두 가지가 다르다.
1) individual signature의 anonymity를 revoke(철회)할 수 있는 방법이 없다.
2) 어떠한 group of user이든 추가설정 없이 group으로 사용될 수 있다. 즉 즉석에서 improvised 될 수 있다.
Crytocurrency에 적용
e.g. Monero
1) 모네로는 transaction간 linkage를 숨긴다 : unlinkability, untraceability
2) ring signatures은 account key와, blockchain 에서 가져온 여러 public keys를 쓴다.
3) Ring에 속한 possible signer들, 즉 모든 ring member은 동등하고 valid 하다.
4) outsider(외부인)은 어떠한 가능한 signer이 내 account에 존재하는지 알 수 없으므로, transaction output이 추적불가능함(untraceable)을 보장한다.
'CS > 정보보호' 카테고리의 다른 글
| [정보보호] Message Authentication Codes (1) | 2023.11.23 |
|---|---|
| [정보보호] Cryptographic Hash Functions (1) | 2023.11.22 |
| [정보보호] PRNG(Pseudorandom Number Generator) (2) | 2023.11.21 |
| [정보보호] TLS(Transport Layer Secrecy)에서의 Forward Secrecy (0) | 2023.11.21 |
| [정보보호] Elliptic Curve Cryptography (1) | 2023.11.15 |
