Merkle 서명 방식

해시 기반 암호학에서 머클 서명 체계는 해시 트리(Merkle tree라고도 함)를 기반으로 한 디지털 서명 체계와 램포트 서명 체계와 같은 일회성 서명을 말한다.1970년대 후반 랄프 머클에 의해 개발되었으며, 디지털 시그니처 알고리즘이나 RSA와 같은 전통적인 디지털 서명에 대한 대안이다.

머클 시그니처 체계의 장점은 양자 컴퓨터 알고리즘에 내성이 있다고 판단된다는 점이다.(쇼어의 알고리즘으로 인해) 효과적인 양자 컴퓨터를 구축할 수 있는 경우 RSA나 ElGamal과 같은 전통적인 공개 키 알고리즘은 불안정해질 것이다.그러나 Merkle 서명 체계는 보안 해시함수의 존재에만 의존한다.이것은 Merkle 시그니처 체계가 매우 조정 가능하고 양자 컴퓨팅에 내성을 갖게 한다.Merkle 서명은 유한한 서명 잠재력을 가진 일회성 서명이라는 점에 유의하십시오. 단방향 순열과 함수(그리고 보편적 단방향 해시함수의 발명)에 기초한 서명에 관한 Moni Naor와 Moti Yong의 작업은 Merkle 유사 서명을 완전한 서명 체계로 확장하는 방법을 제공한다.^{[citation needed]}

키 생성

Merkle 서명 체계는 하나의 공개 키 ${\displaystyle \text{pub}}$ ${\$와 제한된 수의 메시지에 서명하는 데 사용될 수 있다$.$가능한 메시지 수는 2개의 파워여야 하므로 가능한 $메시지{\displaystyle }$ 수를 N${\displaystyle }$= ${\displaystyle {2n}^{}}$ ${\$로 표시한다$.$

공개 키 ${\displaystyle \text{pub}}$ ${\$을(를) 생성하는 첫 번째 단계는 $N{\displaystyle }$ ${\displaystyle N}$ 비공개$$/공개 키 쌍$({\displaystyle X_{}}$ i${\displaystyle {}_{}}$, ${\displaystyle {Yi}_{}}$) ${\displaystyle(X_{i})$을 생성하는 것이다$$.일부 일회성 시그너처 스키마(예: Lamport 시그너처$$ 스키마$)$의 $Y_{i$}}.각 $1{\displaystyle \mathrm{}i}$ i${\displaystyle }$≤ ${\displaystyle {2n}^{}}$ ${\$ i$\leq 2^{n$에 대해 $공개{\displaystyle {}_{}}$ 키${\displaystyle {}_{}{h}_{}}$ i = $){\displaysty h_{i}=H(Y_{i}})$의 해시 값이 계산된다$$.

이러한 해시 값 ${\displaystyle h_{}}$ i ${\$을 사용하여 이 ${\displaystyle {2n}^{}}$ ${\$ 2$^{n}$ 해시$$ 값을 잎으로 배치하고 재귀적으로 해시하여 이진 트리를 형성함으로써 해시 트리가 구축된다.${\displaystyle {i,}_{}}$ ${\displaystyle j_{}}$ ${\$은(는) 트리의 $노드$를 높이 i ${\displaystyle i}$ 및$$ 왼쪽 오른쪽 $위치{\displaystyle }$ j ${\displaystyle$ j$}$로 표시하십시오$.$그런 다음 해시 $값{\displaystyle {}_{}}$ ${\displaystyle h_{}}$i = ${\displaystyle {0,}_{}}$ i ${\$이(가) 잎이다$$.트리의 각 내부 노드에 대한 값은 두 자식 연결의 해시이다.For example, ${\displaystyle a_{1,0}=H(a_{0,0} a_{0,1})}$ and ${\displaystyle a_{2,0}=H(a_{1,0} a_{1,1})}$. In this way, a tree with ${\displaystyle 2^{n}}$ leaves and ${\displaystyle 2^{n+1}-1}$$$ 노드가 구축된다.

Merkle 서명 방식의 개인 키는 (${\displaystyle {}_{}}$ ${\displaystyle i_{}}$, Y ${\displaystyle i_{}}$ )${\displaystyle (X_{i},)$의 전체 집합이다.$Y_{i}}$ 쌍$$.이 계획의 주요 문제점 중 하나는 개인 키의 크기가 전송할 메시지 수에 따라 선형적으로 확장된다는 것이다.

공용 키 ${\displaystyle \text{펍}}$ ${\$은(는) 트리의 루트, ${\displaystyle {\mathrm{n},}_{}}$ 0 ${\$ 입니다$.$개별 공개키 ${\$은(는) 보안을 어기지 않고 공개할 수 있다$$.다만 공개키에 필요하지 않은 만큼 크기를 최소화하기 위해 비밀에 부치는 것이 더 실용적이다.

서명생성

메시지$M{\displaystyle }$ {\$displaystyle M}$에 Merkle 서명 스키마를 사용하여 서명하려면 서명자가 키 쌍$({\displaystyle X_{}}$ i${\displaystyle {}_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$) ${\displaystyle(X_{i})$을 선택하십시오.$Y_{i}}$은$($는) 일회성 서명 체계를 사용하여 서명을 한 다음, 원본 키 쌍 중 하나임을 증명하기 위해 추가 정보를 추가한다(포거가 새로 생성한 키 쌍이 아님).

먼저 서명자가 a$({\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$) ${\displaystyle(X_{i})$을 선택한다.이전에 다른 메시지에 서명하는 데 사용되지 않았던 $Y_{i}$ 쌍을$$ 사용하고 일회성 서명 체계를 사용하여 메시지에 서명함으로써 서명 ${\$ 및 해당하는$$ 공용 키 ${\displaystyle Y_{}}$ ${\$ 메시지 확인에${\displaystyle }$(${\displaystyle {XI}_{}}$, ${\displaystyle {Yi}_{}}${\$disp$.$레이스타일(X_{i},$$Y_{i}}}$은(는) 사실 원래 키 쌍 중 하나였으며, 서명자는 검증자가 ${\displaystyle h_{}}$ i${\displaystyle {}_{}}$= ${\displaystyle {0,}_{}}$ i ${\$을(를) 확인할 수 있도록 Merkle 트리의 중간 노드를 간단히 포함시켜 나무 뿌리에서 공용$$ 키 ${\displaystyle {a,}_{}}$ ${\displaystyle 0_{}}$, ${\$을 계산하는 데$$ 사용하였다.The path in the hash tree from ${\displaystyle a_{0,i}}$ to the root be ${\displaystyle n+1}$ nodes, call them ${\displaystyle A_{0},\ldots ,A_{n}}$, with ${\displaystyle A_{0}=a_{0,i}=H(Y_{i})}$ being a leaf and ${\displaystyle A_n=a_{n,0}=\text{pub}}$${\displaystyle A_{n}=a_{n,0}={\text{pub}}}$이(가) 루트인 것이다$$.

$우리$는 A ${\displaystyle i_{}}$ ${\$이(가$)$ ${\displaystyle {\mathrm{A}}_{}}$ ${\displaystyle i_{}}$+ 1 {\$displaystyle$A_${i+1$}의 아들로 알고 있다$.$To let the verifier calculate the next node ${\displaystyle A_{i+1}}$ given the previous, they need to know the other child of ${\displaystyle A_{i+1}}$, the sibling node of ${\displaystyle A_{i}}$. We call this node ${\displaystyle {\text{auth}}_{i}}$, so that ${\displaystyle A_{i+1}=}$${\displaystyle A_{i+1}=H(A_{i} {\text{auth}}_{i})}$. Hence, ${\displaystyle n}$ nodes ${\displaystyle {\text{auth}}_{0},\ldots ,{\text{auth}}_{n-1}}$ are needed, to reconstruct ${\displaystyle A_{n}=a_{n,0}={\text{pub}}}$ from A ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle {0\mathrm{},}_{}}$ ${\displaystyle i_{}}$ ${\$ 인증 경로의 예는 오른쪽 그림에 나와 있다.

These nodes ${\displaystyle {\text{auth}}_{0},\ldots ,{\text{auth}}_{n-1}}$, the ${\displaystyle Y_{i}}$, and the one-time signature ${\displaystyle {\text{sig}}'}$, together constitute a signature of ${\displaystyle M}$ using the Merkle signature scheme: ${\displaystyle \text{sig}=(}$${\displaystyle {\text{sig}}^{}}$ ${\displaystyle {}^{}}$ Y ${\displaystyle i_{}}$ ${\displaystyle {\text{auth}}_{}{}_{}{}_{}}$ ${\displaystyle {\mathrm{}}_{}{}_{}}$… ${\displaystyle {\text{auth}}_{}{}_{}}$ ${\displaystyle {}_{}}$…${\displaystyle {}_{}{\mathrm{auth}}_{}}$n - 1 ) {\$displaystyle$ {\$text{sig}}({\text{sig}}})=({\$text${auth}_{0}{\text}}{auth}}{$1}{1$} \dotes}{\text}_${\cert}_{\cert}_${n-1$

서명을 위해 Lamport 시그니처 스키마를 사용하는 경우 ${\displaystyle {}^{}}${\$displaystyle${\$text{sig}}'$ ${\displaystyle {\text{시그널}}^{}}$에는 개인 키 $X{\displaystyle {}_{}}$ ${\displaystyle i_{}}${\$displaystyle X_{i}$의 일부가 포함되어$$ 있다는 점에 유의하십시오$.$

서명확인

The receiver knows the public key ${\displaystyle {\text{pub}}}$, the message ${\displaystyle M}$, and the signature ${\displaystyle {\text{sig}}=({\text{sig}}' Y_{i} {\text{auth}}_{0} {\text{auth}}_{1} \ld$$ots {\text{auth}}_{n-1})}$. First, the receiver verifies the one-time signature ${\displaystyle {\text{sig}}'}$ of the message ${\displaystyle M}$ using the one-time signature public key ${\displaystyle Y_{i}}$. If ${\displaystyle {\text{sig}}'}$ is a valid signature of ${\displaystyle$$M$ 수신기는 일회성 서명의 공개 키를 해싱하여$$ ${\displaystyle {A\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$= H ${\displaystyle ({}_{}}$ ${\displaystyle i_{}}$) ${\displaystyle A_{0}=H(Y_{i}})$를 계산한다.For ${\displaystyle j=1,\ldots ,n-1}$, the nodes of ${\displaystyle A_{j}}$ of the path are computed with ${\displaystyle A_{j}=H(A_{j-1} {\text{auth}}_{j-1})}$. If ${\displaystyle A_{n}}$ equals the public key ${\displaystyle$${\$text${pub}$Merkle 서명 구성표$$, 서명이 유효함.

참조

• E. Dahmen, M. Dring, E. Clintsevich, J. Buchmann, L.C. Coronado Garca. "CMSS - 향상된 머클 서명 체계"암호학의 진보 - Indocrypt 2006, 2006.
• E. 클린세비치, K.오케야, C.뷔야룸, J. 부흐만, E.다멘. "사실상 서명 능력이 무제한인 머클 서명"제5차 응용암호 및 네트워크 보안 국제회의 - ACNS07, 2007.
• 랄프 머클"재활용, 인증 및 공개 키 시스템 / A 인증 디지털 서명"1979년 스탠퍼드대 전기공학과의 박사학위 논문.[1]
• 모니 나오르, 모티 영:Universal One-Way Hash Functions 및 해당 암호화 응용 프로그램.STOC 1989: 33-43
• S. 미칼리, M. 야콥손, T. 레이튼, M. 시들로."추상적인 머클 트리 표현 및 통과"RSA-CT 03, 2003

외부 링크

• Efficient Use of Merkle Trees - RSA 연구소는 효율적인 일회성 서명 방식으로 Merkle 트리 + Lamport 서명의 원래 목적에 대해 설명한다.
• 아담 랭글리의 해시 기반 서명과 머클 서명에 대한 소개.
• 데이비드 웡의 해시 기반 서명에 관한 4부 시리즈.