램포트 시그니처

암호학에서 Lamport 시그니처 또는 Lamport 일회성 시그니처 체계는 디지털 시그니처를 구성하는 방법이다.램포트 서명은 암호화된 보안 단방향 함수로 구축될 수 있으며, 일반적으로 암호 해시 함수가 사용된다.

양자컴퓨터의 잠재적인 개발은 RSA와 같은 많은 일반적인 형태의 암호문의 보안을 위협하지만, 그 경우에도 해시 함수가 큰 램포트 서명은 여전히 안전할 것으로 생각된다.유감스럽게도 각 램포트 키는 하나의 메시지에 서명하는 데만 사용할 수 있다.그러나 해시 트리와 결합하면 하나의 키가 많은 메시지에 사용될 수 있어 상당히 효율적인 디지털 서명 체계가 된다.

램포트 시그니처 암호 시스템은 1979년에 발명되었고 그것의 발명가인 레슬리 램포트의 이름을 따서 명명되었다.^[1]

예

앨리스는 256비트 암호화 해시함수와 일종의 보안 난수 생성기를 가지고 있다.그녀는 램포트 키 쌍, 즉 개인 키와 그에 상응하는 공개 키를 만들어 사용하길 원한다.

키 쌍 만들기

개인 키를 생성하기 위해 앨리스는 무작위 번호 생성기를 사용하여 256쌍의 무작위 번호(총 2×256개)를 생성하는데, 각 숫자는 크기가 256비트, 즉 총 2×256×256비트 = 128Kibit이다.이것은 그녀의 개인 열쇠고 그녀는 나중에 사용하기 위해 안전한 곳에 보관할 것이다.

공개 키를 생성하기 위해 그녀는 개인 키에 있는 512개의 난수 각각을 해시하여 각각 256비트 크기의 512개의 해시를 만든다.(또한 총 128Kbits이다.)이 512개의 숫자가 그녀의 공개키를 형성하고, 그녀는 그것을 세계와 공유할 것이다.

메시지 서명

나중에 앨리스는 메시지에 서명을 하고 싶어한다.먼저 그녀는 메시지를 256비트 해시섬으로 해시한다.그런 다음, 해시의 각 비트에 대해, 비트의 값을 기초로, 그녀는 자신의 개인 키를 구성하는 해당 숫자 쌍에서 한 수를 선택한다(즉, 비트가 0이면 첫 번째 숫자를 선택하고, 비트가 1이면 두 번째를 선택한다).이렇게 하면 256개의 숫자가 나온다.각각의 숫자는 그 자체로 256비트 길이기 때문에 그녀의 서명의 총 크기는 256×256비트 = 65536비트 = 64Kibit이 될 것이다.이 (원래 무작위로 뽑은) 번호들은 그녀의 서명이고 그녀는 이 숫자들을 메시지와 함께 게재한다.

이제 앨리스의 개인 키가 사용되었으므로 다시는 사용해서는 안 된다는 점에 유의하십시오.그녀는 서명을 위해 사용하지 않은 나머지 256개의 숫자를 파괴해야 한다.그렇지 않으면 개인 키를 사용하는 각각의 추가 서명은 나중에 상대방으로부터 거짓 서명을 만들 수 있는 상대들에 대한 보안 수준을 감소시킨다.^[2]

서명 확인

그리고 나서 밥은 앨리스의 메시지 서명을 확인하고 싶어한다.그는 또한 256비트 해시섬을 얻기 위해 메시지를 해시한다.그런 다음 그는 해시섬의 비트를 사용하여 앨리스의 공개키에 있는 해시 256개를 골라낸다.그는 앨리스가 서명을 위해 무작위 번호를 고른 것과 같은 방식으로 해시를 선택한다.즉, 메시지 해시의 첫 번째 비트가 0이면 첫 번째 쌍에서 첫 번째 해시를 선택하는 등의 작업을 한다.

그리고 나서 밥은 앨리스의 서명에 256개의 난수를 각각 해시한다.이것은 그에게 256개의 해시를 준다.만약 이 256개의 해시가 그가 방금 앨리스의 공개키에서 고른 256개의 해시와 정확히 일치한다면, 그 서명은 괜찮다.만약 그렇지 않다면, 서명이 틀렸다.

앨리스가 메시지의 서명을 게시하기 전에 개인 키의 2×256 임의 번호를 다른 사람이 알지 못한다는 점에 유의하십시오.따라서 다른 누구도 서명을 위해 256개의 난수 목록을 만들 수 없다.그리고 앨리스가 서명을 발표한 후에도 다른 사람들은 나머지 256개의 무작위 번호를 알지 못하기 때문에 다른 메시지 해시에 맞는 서명을 만들 수 없다.

형식 설명

아래는 램포트 서명이 어떻게 작용하는지에 대한 간략한 설명으로, 수학적 표기법으로 쓰여 있다.이 설명의 "메시지"는 적당한 크기의 고정된 블록이며, 임의의 긴 메시지가 서명될 때 해시 결과일 수 있음(그러나 반드시 그렇지는 않음)에 유의하십시오.

열쇠들.

$k{\displaystyle }$ ${\displaystyle k}$을(를) 양의 정수로 하고$$ P${\displaystyle }$=${\displaystyle }${ 0${\displaystyle ,{}^1}$ k ${\$ P$=\{0,1\}^{k}}}}$을(를) 메시지의 집합으로$$ 한다.$Let{\displaystyle }$ f${\displaystyle }$: ${\displaystyle Y}$→ Z ${\displaystyle$ f$:\,$$Y\오른쪽$ 화살표 $Z}$은(는) 단방향 함수가 된다.

For ${\displaystyle 1\leq i\leq k}$ and ${\displaystyle j\in \{0,1\}}$ the signer chooses ${\displaystyle y_{i,j}\in Y}$ randomly and computes ${\displaystyle z_{i,j}=f(y_{i,j})}$.

개인 키 $K{\displaystyle }$ ${\displaystyle$ K$}$는$$2k$${\$displaystyle$ 2k} $값{\displaystyle {}_{}}$ $y$i, ${\displaystyle j_{}}$ ${\$ $y_{i,j$}로 $구성$되며$,$ ${\displaystyle {\mathrm{공용}}_{}}$ 키는 ${\displaystyle \mathrm{2k}}$ ${\displaystyle$ 2k$}$ 값 $z$ ${\displaystyle {i,}_{}}$j {\$displaystysty z_{i,j}$로 구성된다$.$

메시지 서명

$\{0,$ m_${k$}\$in$\{0,$1\}}{0,$1\}^{$k}}}$을(를) 메시지처럼$$ 두십시오.

메시지의 서명은

${\displaystyle \operatorname {sig} (m_{1}\ldots m_{k})=(y_{1,m_{1}},\ldots ,y_{k,m_{k}})=(s_{1},\ldots ,s_{k})}$.

서명 확인

확인자는 1 ${\displaystyle \le }$ ${\displaystyle i}$ ${\displaystyle \le }$ ${\displaystyle k}$ ${\displaystyle f(s_{i}=z_$${i,m_{i}}}}}$에 $대해$ f${\displaystyle }$(${\displaystyle {}_{}}$ $i$)${\displaystyle }$= ${\displaystyle z_{}}$i를 ${\displaystyle {{확인}_{}}_{}}$하여 서명을 검증한다$.$

메시지를 위조하기 위해 이브는 단방향 함수 $f{\displaystyle }$ ${\displaystyle f}$을(를) 반전시켜야 한다$.$이것은 적절한 크기의 입력과 출력에 난해한 것으로 가정한다.

보안 매개 변수

램포트 서명의 보안은 단방향 해시함수의 보안과 출력 길이에 기초한다.

n비트 메시지 다이제스트를 생성하는 해시함수의 경우, 단일 해시함수 호출에 대한 이상적인 프리이미지 및 두 번째 프리이미지 저항은 고전적 컴퓨팅 모델에서 충돌을 찾기 위한 2 연산ⁿ 순서를 내포한다.그로버 알고리즘에 따르면 이상적인 해시함수의 단일 호출에서 프리이미지 충돌 발견은 양자 컴퓨팅 모델 하의 O(2^n/2) 연산에 상한이 있다.램포트 서명의 경우, 공개 키와 서명의 각 비트는 해시함수에 대한 단일 호출만 요구하는 짧은 메시지에 기초한다.

각 개인 키 y와_i,j 해당 개인_i,j 키 쌍에 대해 개인 키 길이를 선택해야 입력 길이에 사전 이미지 공격을 수행하는 것이 출력 길이에 사전 이미지 공격을 수행하는 것보다 빠르지 않다.예를 들어, 퇴보된 경우, 각 개인 키 y_i,j 요소의 길이가 16비트밖에 되지 않았다면, 메시지 다이제스트 길이에 관계 없이 출력과의 일치를 찾기 위해 2번의¹⁶ 작업에서 가능한 2개의 개인¹⁶ 키 조합을 모두 철저히 검색하는 것은 사소한 일이다.따라서 균형 잡힌 시스템 설계는 두 길이 모두 대략적으로 동일함을 보장한다.

양자 보안 시스템인 그로버 알고리즘에 근거하여, 공개 키 요소 z의_i,j 길이, 비공개 키 요소 y 및_i,j 서명 요소들은_i,j 시스템의 보안 등급보다 2배 이상 커야 한다.즉,

• 80비트 보안 시스템은 160비트 이상의 요소 길이를 사용한다.
• 128비트 보안 시스템은 256비트 이상의 요소 길이를 사용한다.

그러나 위의 이상론적 작업 추정치는 이상적인 (완벽한) 해시함수를 가정하고 한 번에 하나의 프리이미지만을 대상으로 하는 공격으로 제한되므로 주의를 기울여야 한다.기존 컴퓨팅 모델에서는 프리이미지 2개를^3n/5 검색하면 프리이미지당 전체 비용이 2에서^n/2 2로^2n/5 줄어든다고 알려져 있다.^[3]다중 메시지 다이제스트의 컬렉션을 고려하여 최적의 요소 크기를 선택하는 것은 개방적인 문제다.512비트 요소 및 SHA-512와 같은 더 큰 요소 크기와 더 강력한 해시 함수를 선택하면 이러한 미지의 요소를 관리할 수 있는 더 큰 보안 마진이 보장된다.

최적화 및 변형

짧은 개인 키

개인 키의 임의 번호를 모두 만들어 저장하는 대신, 충분한 크기의 단일 키를 저장할 수 있다.(일반적으로 개인 키의 임의 숫자 중 하나와 같은 크기)그런 다음 단일 키를 암호화된 보안 가성 번호 생성기(CSPRNG)의 시드로 사용하여 필요할 때 개인 키의 모든 난수를 생성할 수 있다.암호화된 보안 해시(또는 적어도 시드와의 XORed가 아닌 출력은)를 CSPRNG 대신 사용할 수 없다는 점에 유의하십시오. 메시지에 서명하면 개인 키의 추가 랜덤 값이 노출되기 때문이다.상대방이 의도된 수령자가 서명하기 전에 서명에 접근할 수 있는 경우, 개인 키에서 공개되는 임의 값을 두 배로 늘릴 때마다 보안 수준의 절반으로 서명을 위조할 수 있다.

동일한 방법으로 단일 키를 CSPRNG와 함께 사용하여 많은 Lamport 키를 생성할 수 있다.가급적 BBS와 같은 어떤 종류의 랜덤 액세스 CSPRNG를 사용해야 한다.

짧은 공개 키

램포트 서명은 해시 목록과 결합할 수 있어 공개 키의 모든 해시 대신 단일 상단 해시만 게시할 수 있다.즉, ${\displaystyle \mathrm{2k}}$ ${\displaystyle 2k}$ 값 대신$$ $z{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ j ${\$단일 상단 해시에 대해 검증하려면 서명에는 공개 키의 해시 목록에서 임의의 숫자와 사용되지 않은 해시가 포함되어야 하며, 따라서 크기가 약 2배 정도 된다.즉, 모든 $j{\displaystyle }$ ${\displaystyle \ne }$ ${\displaystyle m_{}}$ i ${\$에 대한$$ 값$({\displaystyle z_{}}$ i ${\displaystyle j_{}}$ $){\displaystyle (z_{ij}})$을 포함해야 한다$$.

해시 목록 대신 암호화된 축전지를 사용하는 경우 사용하지 않는 해시는 서명에 포함시킬 필요가 없다.^[4]그러나 축전지가 수 이론적 가정에 기초한다면 이는 아마도 램포트 시그니처 채택의 효익을 저하시킬 것이다. 예를 들어 양자 컴퓨팅 저항성.

단축키 및 서명

윈터니츠 시그니처 압축은 개인 키와 공개 키의 크기를 비트 ${\displaystyle 2\langle{\text{chunk size in bits$의 $2{\displaystyle \mathrm{}}$signature ${\displaystyle \text{청크 크기}}$ 계수보다 약간 적게 줄이며, 서명에 대한 인수는 절반으로 줄어든다.계산은 ${\displaystyle {\text{비트}}^{}}$ ${\displaystyle ⟩/⟨}$ ${\displaystyle \text{청크 크기(비트}}$ {\$displaystyle 2^{\langle {\text{chunk size in bits}/\langle {\text{chunk size in bits}}\langle}}}).$ CSPRNG 요구 사항 대신 암호학적으로 안전한 해시 질량이다$.$^[5]

앞 절에서 설명한 것처럼 서명 크기를 두 배로 늘리는 비용을 들여 공개 키를 단일 값으로 단축하기 위해 해시 목록을 사용할 수도 있다.

여러 메시지에 대한 공용 키

각 Lamport 공용 키는 하나의 메시지에 서명하는 데만 사용할 수 있으며, 이는 많은 메시지가 서명되려면 많은 키가 게시되어야 함을 의미한다.그러나 해시 트리는 대신 해시 트리의 상위 해시를 게시하는 공용 키에 사용될 수 있다.이렇게 하면 해시 트리의 일부가 서명에 포함되어야 하기 때문에 결과 서명의 크기가 커지지만, 단일 해시를 게시할 수 있으며, 이 해시는 지정된 수의 미래 서명을 검증하는 데 사용될 수 있다.

참고 항목

• S/KEY

참조

추가 읽기

• L. 램포트, 1979년 10월 SRI 국제 컴퓨터 과학 연구소 기술 보고서 SRI-CSL-98의 단방향 함수의 디지털 서명 구성.
• Efficient Use of Merkle Trees - RSA 연구소는 효율적인 일회성 서명 방식으로 Merkle 트리 + Lamport 서명의 원래 목적에 대해 설명한다.
• 아담 랭글리의 해시 기반 서명과 머클 서명에 대한 소개.
• 블레이크2b(C++) 위에 Lamport 스키마의 참조 구현
• SHA256, SHA512 또는 Blake2b(러스트) 위에 Lamport 시그니처 구현 참조