램포트 서명
예제 편집
앨리스(Alice)가 256비트 암호 해시함수를 가지고 있고, 어떤 종류의 안전한 난수 발생기를 가지고 있다고 하자. 그는 Lamport 키 쌍을 생성하고, 사용하기를 바란다. (즉, 개인키와 그에 따른 공개키를 사용하려고 한다.)
키 생성 편집
앨리스의 개인키를 만들기 위해, 난수 발생기를 이용해 256개의 랜덤값 쌍을 만든다. (2 × 256 = 총 512개) 각각의 랜덤값은 앨리스의 개인키가 되고, 키 하나당 256 비트의 길이를 갖는다. (2 × 256 × 256 비트 = 16 KB) 공개키를 만들기 위해, 앨리스의 256개의 개인키 쌍의 해시 값을 각각 구한다. 이렇게 만들어진 256개 개인키 쌍에 대한 해시 값이 (총 512개) 앨리스의 공개키가 된다. 이 공개키는 다른 사람들에게 알려져야 한다.
메시지 서명 편집
앨리스가 메시지를 서명하고 싶을 경우, 먼저 메시지 M에 대한 해시 값을 구한다. 그리고 나서 각각의 비트에 대응되는 위치의 앨리스의 개인키 쌍에서 값을 선택한다. 예를 들어, 만약 해시 값의 첫 번째 비트 값이 0일 경우, 첫 번째 개인키 쌍의 첫 번째 값을 선택한다. 만약 해시 값의 첫 번째 비트 값이 1일 경우, 첫 번째 개인키 쌍의 두 번째 값을 선택한다. 이러한 방식으로 계속 진행하여 256개의 값을 개인키 쌍에서 선택할 수 있다. (256 × 256 비트 = 8 KiB) 이 랜덤 값이 앨리스의 서명이 되고, 이 값을 메시지와 함께 공개한다. 이 때 주의해야 할 점은, 이처럼 앨리스의 개인키가 한번 사용되고 나면 절대 다시 사용되어서는 안 된다는 점이다. 앨리스가 서명하는데 사용하지 않은 256 개의 랜덤 값은 공개되거나 사용되어서는 안 된다.
서명의 확인 편집
밥(Bob)이 앨리스의 서명을 확인하기 위해서는, 먼저 밥도 역시 메시지 M의 해시 값(256 비트)을 구한다. 그리고 이렇게 얻은 해시 값을 이용해 앨리스의 공개키에서 256 개의 값을 선택한다. 이는 앨리스가 위의 서명 과정에서 개인키를 이용해 서명 값을 생성할 때 사용한 방법과 같은 방법을 사용하면 된다. 즉, 만약 메시지 M의 해시 값 첫 번째 비트가 0이면 앨리스의 첫 번째 공개키 쌍의 첫 번째 값을 사용하는 식이다. 그리고 나서, 밥은 앨리스의 메시지와 함께 공개되어 있는 서명 값 256개의 해시 값을 구한다. 만약 이렇게 구한 256개의 해시 값이 앨리스의 공개키 쌍에서 고른 값과 정확히 일치한다면 서명은 올바른 것이다.
참고로, 앨리스가 메시지 M의 서명을 공개하기 이전에는 아무도 앨리스의 개인키를 알 수 없으므로 아무도 주어진 메시지를 서명하기 위해 필요한 적절한 256 개의 랜덤값을 생성할 수 없다.
그리고 앨리스가 서명을 공개한 이후에도 역시 다른 사람들은 앨리스의 개인키 중에서 여전히 서명을 위해 사용되지 않은 나머지 256 개의 랜덤 값을 알지못하고, 그러므로 공개된 해시 값과 같은 또다른 메시지 M’을 만드는 것 역시 불가능하다.
참고 문헌 편집
- L. Lamport, Constructing digital signatures from a one-way function, Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, Oct. 1979.
- Efficient Use of Merkle Trees - RSA labs explanation of the original purpose of Merkle trees + Lamport signatures, as an efficient one-time signature scheme.