Public Key Cipher

〈컴퓨터정보보안〉 수업 노트

퍼블릭 키 암호화(Public Key Cipher) 혹은 비대칭 암호화는 두 개의 키를 사용해 하나는 암호화, 다른 하나는 복호화에 사용하는 암호화 방식을 의미한다. 이 방법은 두 가지 사용 사례를 가지고 있는데, 암호화 외에도 디지털 서명에도 사용된다.

암호화 시나리오에서는 평문 $M$ 을 암호화해 암호문 $C$ 를 생성하는 데 공개 키를 사용한다. 역으로 복호화하는데에는 개인키를 사용해 $C$ 를 평문 $M$ 으로 되돌린다. 사용자 측면에서는 암호화와 복호화에 다른 키를 사용한다는 것 외에는 대칭 키 암호화와 동일하게 동작한다.

디지털 서명은 자신이 작성한 자료에 대해 부인 방지에 보통 사용된다. 한 쪽이 비밀 키를 이용해 암호화하는 것을 서명하는 것이라고 하고, 누구나 공개 키를 이용해 복호화함으로써 서명을 검증한다.

냅색 문제

냅색 문제 알고리즘을 응용하여 공개 키 암호화 알고리즘을 만들 수 있다. 냅색 문제가 NP-완전 문제로 알려져 있기 때문이다. 이 문제를 해결하는 데 필요한 계산량은 키 길이에 따라 기하급수적으로 증가한다.

$n$ 개 가중치 $W_0, W_1, …, W_{n-1}$ 와 합 $S$ 가 주어질 때 $a_i \in {0, 1}$ 를 찾으려고 한다면 $S$ 는 다음에 대해 정리하여 시도할 수 있다.

\[S = a_0 W_0 + a_1 W_1 + ... + a_{n-1} W_{n-1}\]

공개키 가중치 수열에서 평문의 각 비트가 1인 위치의 가중치를 더해 암호문을 만든다. 공격자는 공개키와 암호문으로부터 어떤 가중치들이 선택되었는지 알아내야 한다. 공격자는 모든 가중치 조합을 시도해야 하므로, 키 길이가 충분히 길다면 계산량이 기하급수적으로 증가한다.

예: 가중치 $(62, 93, 26, 52, 166, 48, 91, 141)$ 에서 합 $S = 302$ 를 찾으려면, 공격자는 모든 가중치 조합을 시도해야 한다. $2^8 = 256$ 가지 조합이 존재한다.

이 문제에서 일반 냅색(GK; General Knapsack)은 해결이 어렵지만 슈퍼증가 냅색(SIK; Super Increasing Knapsack)은 쉽게 해결할 수 있다.

슈퍼증가 냅색은 모든 가중치에 대해, 각 가중치가 모든 선행하는 가중치의 합보다 크다는 조건을 만족한다.

\[\begin{aligned} W_1 &> W_0 \\ W_2 &> W_0 + W_1 \\ \ldots \\ W_{n-1} &> W_0 + W_1 + \cdots + W_{n-2} \end{aligned}\]

예: 가중치 $(2, 3, 7, 14, 30, 57, 120, 251)$ 에서 합 $S = 186$ 을 만족하는 서브셋을 찾아야 한다면, 큰 가중치부터 차례로 확인하여 $120 + 57 + 7 + 2 = 186$ 을 쉽게 찾을 수 있다.

이러한 원리를 이용해 냅색 암호화 알고리즘을 만들 수 있다. 퍼블릭 키는 공격이 어려운 일반 냅색을 사용하고, 개인 키는 쉽게 해결할 수 있는 슈퍼증가 냅색을 사용한다.

이렇게 하여 쉽게 암호화하고, 비밀 키 없이는 복호화하기 어렵게 만든다.

예: 가중치 $(2, 3, 7, 14, 30, 57, 120, 251)$ 로 SIK 냅색 문제를 만든다. 이어서 $m = 41$, $n = 491$ 로 선택한다.

$m$, $n$ 은 서로소, $n$ 은 SIK 가중치의 합을 초과하도록 선택한다.

이어서 각 SIK 가중치에 대해, 다음과 같이 일반 냅색을 만든다.

\[W_i' = m \cdot W_i \mod n\] \[\begin{aligned} 2 \cdot 41 \mod 491 &= 82 \\ 3 \cdot 41 \mod 491 &= 123 \\ 7 \cdot 41 \mod 491 &= 287 \\ 14 \cdot 41 \mod 491 &= 83 \\ 30 \cdot 41 \mod 491 &= 248 \\ 57 \cdot 41 \mod 491 &= 373 \\ 120 \cdot 41 \mod 491 &= 10 \\ 251 \cdot 41 \mod 491 &= 471 \end{aligned}\]

이렇게 하면 일반 냅색 가중치 $(82, 123, 287, 83, 248, 373, 10, 471)$ 을 얻는다. 원래는 슈퍼증가 수열이었으나 mod 연산으로 원래의 수열의 모습은 찾아보기 어려워졌다. 하지만 여전히 mod 연산의 역과정으로 슈퍼증가 수열을 복원할 수 있다.

따라서 비밀키로 원래의 가중치 $(2, 3, 7, 14, 30, 57, 120, 251)$ 를 사용하고, 공개키로 일반 냅색 가중치 $(82, 123, 287, 83, 248, 373, 10, 471)$ 과 $n = 491$ 를 사용해 암호화를 구현한다.

예: 키와 동일한 길이의 평문 10010110 을 앞에서 사용한 수열을 사용해 암호화하려고 한다. 평문의 각 비트와 같은 인덱스의 공개키 가중치를 곱해 합을 구한다.

\[\begin{aligned} &1 \cdot 82 + 0 \cdot 123 + 0 \cdot 287 + 1 \cdot 83 \\ &+ 0 \cdot 248 + 1 \cdot 373 + 1 \cdot 10 + 0 \cdot 471 \\ &= 82 + 83 + 373 + 10 \\ &= 548 \end{aligned}\]

결과값 548은 암호문이 되어, 비밀키를 이용해 쉽게 복호화할 수 있다.

\[548 \cdot 12 = 193 mod 491\]

$S = 193$ 을 만드는 SIK 가중치의 조합을 찾으면, $193 = 120 + 57 + 14 + 2$ 를 쉽게 찾을 수 있다. 따라서 평문은 10010110 이 된다.

RSA

〈RSA〉 참조

Misconceptions on PK

공개 키 암호화가 오늘날 널리 쓰이게 되면서, 몇 가지 오해가 생겼다.

• 퍼블릭 키 암호화는 더 안전하다는 주장이 있지만, 어떤 암호화 방법이든 안전함은 키 길이와, 암호화 알고리즘을 깨는데 요구되는 계산량에 따라 결정된다.

• 공개 키는 전통적인 대칭 키 암호화를 대체하는 방법이 아니다. 퍼블릭 키 방법의 계산 오버헤드가 더 높기 때문에, 두 방법은 혼합해서 사용된다.

• 두 방법은 모두 보안을 제공할 수 있다.