[MIT OCW] 3. Signiture

 

이 글은 MIT OpenCourseWare 의 MAS.S62 - Cryptocurrency Engineering and Design의 강의를 요약, 정리 한 것입니다..

글을 읽으실 때 이해를 위하여 원 강의를 함께 보시는 것을 추천합니다.

*글에 포함된 이미지는 강의에서 제공되는 Lecture Note로부터 캡쳐한 것입니다.

 

*최종수정 : 2025.01.09. 강의 렉쳐노트 요약을 chatgpt에게 요청한 결과물을 약간 다듬음. 추후 설명을 덧붙일 예정입니다.

 

 

1. 다중 사용 해시 서명 (Multiple Use Hash Signatures)

 

 - 서명 (Signatures)
강의 3에서는 디지털 서명과 그 다양한 유형에 대해 다룹니다. 첫 번째 문제 세트에서는 램포트 서명(Lamport Signatures)을 다뤘습니다. 이는 해시 기반 서명의 한 예로, 간단하면서도 기본적인 구조를 갖고 있습니다. 이 외에도 RSA, ECDSA, EC Schnorr 등 다양한 서명 방식이 존재하며, 각각 독특한 기능과 특성을 가지고 있습니다.

- Lamport Signiture의 단점

램포트 서명은 한 번만 사용할 수 있는 키 구조를 가지며, 동일한 키로 여러 서명을 하면 위조 가능성이 생깁니다.

또한 signiture, pub/priv key의 size가 너무나도 커지게 됩니다.

 

일회용 서명의 단점을 해결하는 간단한 방법:

• 두 개의 공개 키를 생성하여 연결한 뒤 이를 게시합니다.
• 서명을 생성할 때, 어떤 키를 사용할지 표시합니다.
• 이의 경우 서명 크기는 동일하지만, 공개 키와 개인 키 크기는 두 배로 증가합니다.

규모의 문제는 각 키를 해싱을 통하여 규모를 줄이는 방법을 활용할 수 있습니다.

개인 키를 효율적으로 만들기 위해, 루트 개인 키를 생성하고 이를 해싱하여 하위 키를 생성합니다. 예를 들어:

• key1=hash(root, 1) : 첫번째 키임을 표현하기 위해 루트 키에 1을 합쳐 해시하는 것. 이를 통해 preimage issue도 해결가능.
• key2=hash(root, 2)

결과적으로 개인 키는 32바이트 크기로 줄어듭니다.

• hash(seed, row, column) 형식으로 데이터를 해싱하여 256개의 키를 생성합니다.
• 이를 통해 16KB에서 32바이트로 크기를 줄이는 효율적인 구조를 만듭니다.

 

• 개인 키는 32바이트로 최적화되었지만, 공개 키는 여전히 큰 크기를 유지합니다.
• commitment 기법을 사용해 공개 키 크기를 줄이는 방안을 탐구합니다.

Merkle Tree(Hash Tree)

• 다수의 공개 키를 효율적으로 관리하기 위해 해시 트리(Merkle Tree)를 사용합니다.
• 루트 해시를 공개 키로 사용하며, 서명에는 특정 키가 트리에 포함되었음을 증명하는 데이터를 포함합니다.

Merkle Tree의 장점:

• 루트 해시는 고정 크기(32바이트)를 유지하며, 트리에 포함된 요소 수와 무관합니다.
• O(n) 의 규모로 늘어나는 요소(각 요소의 생성은 O(1))를 증명하기 위해 O(log⁡ n) 크기의 중간 해시만 필요합니다.

 

결론:
램포트 서명의 기본 구조에서 출발해 Merkle Tree를 활용한 효율적인 다중 사용 서명 구조를 설계했습니다.
이는 개인 키와 공개 키의 크기를 줄이고, 실용성을 높이는 데 기여합니다.

 

 

더 강력한 서명 방식이 필요하다

• 해시 기반 서명은 유용하지만, 한계를 극복할 필요가 있습니다.
• RSA, ECDSA, EC Schnorr과 같은 더 강력한 서명 방식을 탐구합니다.

---

페이지 12

RSA 서명

• RSA는 두 개의 소수 p와 q를 사용해 n=p×q를 계산합니다.
• n은 공개 키로 사용되고, p와 q는 개인 키 계산에 사용됩니다.
• RSA의 기본 속성은 n을 통해 p와 q를 찾는 것이 매우 어렵다는 점입니다.

---

페이지 13

RSA 서명의 기본 연산

• e: 공개 지수 (보통 3 또는 65537 사용).
• d: 개인 지수 (d=e−1mod  (p−1)(q−1))
• 서명: s=m^d mod  n
• 검증: s^e mod  n=m

---

페이지 14

RSA의 특징

• 키 크기는 해시 기반 서명보다 작지만, 구현이 까다롭습니다.
• 키를 잘못 설정하면 개인 키가 노출될 수 있습니다.
• 비트코인과 같은 암호화폐에서는 RSA 대신 타원 곡선을 사용합니다.

타원 곡선 (Elliptic Curves)

• 비트코인이 사용하는 타원 곡선의 방정식: y2=x3+7
• 곡선 위의 점들 간의 연산(덧셈, 곱셈)을 정의하여 암호학적 기능을 수행합니다.

타원 곡선 연산

• 두 점 P와 Q의 합 R을 계산하는 방법:
  • P+Q=R
  • 접선과 교차점을 활용하여 계산.
• 점의 곱셈은 동일한 점을 반복적으로 더하는 방식으로 정의됩니다.

타원 곡선의 효율성

• 타원 곡선은 RSA보다 키 크기가 작고 연산이 빠릅니다.
• 비트코인과 같은 암호화폐에서 널리 사용됩니다.

ECDSA (Elliptic Curve Digital Signature Algorithm)

• 비트코인에서 사용하는 디지털 서명 알고리즘.
• 서명 생성:
  1. 무작위 키 k 생성.
  2. R=k⋅G 계산.
  3. s=k−1(hash(m)+a⋅r) 계산.
• 검증:
  s⋅G=R+hash(m)⋅A

 

ECDSA의 문제점

• Schnorr 서명과 비교해 복잡하고 비효율적.
• Schnorr 서명이 특허 만료 후 더 널리 사용될 가능성이 있음.

Diffie-Hellman 키 교환

• 두 사용자 간 비밀 키 공유 방법.
• 각자의 개인 키와 상대방의 공개 키를 사용해 공유 키 계산.
• 공유 키는 암호화와 인증에 사용 가능.

 

타원 곡선의 추가 활용

• 두 공개 키 A=aG, B=bG를 더해 D=A+B=(a+b)G 계산 가능.
• D를 사용해 다중 서명 생성:
  • 두 사용자가 각각의 개인 키를 공유하지 않고 결합된 공개 키로 서명 가능.
  • 비트코인 다중 서명 주소와 같은 응용 가능.

서명 집계 (Signature Aggregation)

• 여러 사용자의 서명을 단일 서명으로 결합하여 크기 감소.
• 모든 서명이 동일한 메시지를 서명했는지 확인 가능.
• 결과적으로 효율적이고 저장 공간 절약.

양자 컴퓨터와 암호화의 미래

• 양자 컴퓨터는 RSA와 타원 곡선 기반 암호화를 무력화할 가능성이 있음.
• 해시 기반 서명은 양자 컴퓨터에 안전한 대안으로 고려됨.
• 해시 기반 서명의 효율성을 높이기 위한 연구 필요.

결론

• 디지털 서명은 암호화와 데이터 무결성 보장에 필수적.
• RSA, ECDSA, Schnorr 서명 등 다양한 방식이 존재하며 각각의 장단점이 있음.
• 타원 곡선 서명은 효율성과 크기 면에서 뛰어나 암호화폐에서 널리 사용됨.
• 미래에는 양자 컴퓨터의 위협에 대비한 새로운 서명 방식이 필요할 것.