📂정수론

암호론에서의 암호화와 복호화

빌드업

앨리스^alice가 밥^bob에게 전하고 싶은 메세지가 있다고 생각해보자. 세상에 사람이 둘 뿐이라면 이 메세지는 오직 둘만이 공유하며, 감출 이유가 없다. [ NOTE: 암호론에서 앨리스는 $A$ 를 대신하는 이름이고, 밥은 $B$ 를 대신하는 이름이다. ] 하지만 이들 외의 제3자로 이브^eve가 있다고 하자. 이브는 딱히 나쁜 의도는 없지만, 앨리스가 밥에게 전하고 싶은 메세지에 관심이 있다. 반면 앨리스는 밥에게 전달되는 메세지를 밥만이 알길 원한다. [ NOTE: 암호론에서 이브는 ‘엿듣는 사람’을 뜻하는 Eavesdropper의 앞글자인 $E$ 를 대신하는 이름으로, 메세지를 훔쳐보기만 하는 소극적 공격자의 역할을 한다. ] 그래서 앨리스는 이브가 알 수 없도록 메세지를 보내려고 한다. 이는 인간이라면 누구나 공감할 수 있는 ‘암호론’의 모티브다.

이 때 앨리스가 밥만이 알 수 있도록 메세지를 변형하는 것을 암호화^encryption , 밥이 변형된 메세지를 읽을 수 있도록 원래대로 되돌리는 것을 복호화^decryption라 한다. 또한 어떤 메세지를 암호화할 때, 암호화되기 전의 메세지를 평문^plaintext이라 하고 그 집합을 $\mathcal{M}$, 암호화된 후의 메세지를 비문^ciphertext이라 하고 그 집합을 $\mathcal{C}$ 이라 나타낸다.암호화와 복호화는 어떤 규칙을 가지고 이루어질 것이고, 제3자는 이러한 규칙을 알고 있어도 복호화를 할 수 없도록 키^key를 공유한다. 이러한 키의 집합을 $\mathcal{K}$ 이라고 나타낸다면, 암호화와 복호화는 다음과 같이 수학적으로 나타낼 수 있다.

정의 ¹

1. 함수 $e : \mathcal{K} \times \mathcal{M} \to \mathcal{C}$ 를 암호화라 하고, 간략히 $e_{k} : \mathcal{M} \to \mathcal{C}$ 로도 나타낸다.
2. 함수 $d : \mathcal{K} \times \mathcal{C} \to \mathcal{M}$ 를 복호화라 하고, 간략히 $d_{k} : \mathcal{C} \to \mathcal{M}$ 로도 나타낸다.

단, $e_{k}$ 와 $d_{k}$ 는 서로 역함수다. 다시 말해, 모든 $m \in \mathcal{M}$ 에 대해 $d_{k} \left( e_{k} ( m ) \right) = m$ 이어야한다.

그러나 이러한 대응관계는 너무나 많고, 그 중에서 쓸만한 암호는 다음과 같은 조건을 만족시켜야한다.

암호 체계 $( \mathcal{K} , \mathcal{M} , \mathcal{C} , e , d )$ 는 다음의 성질들을 가질 때 유용하다.

• (i): 모든 $k \in \mathcal{K}$ 와 $m \in \mathcal{M}$ 에 대해 $e_{k} (m)$ 을 계산하기 쉬워야한다.
• (ii): 모든 $k \in \mathcal{K}$ 와 $c \in \mathcal{C}$ 에 대해 $d_{k} (c)$ 를 계산하기 쉬워야한다.
• (iii): $k$ 를 모른다면 $c_{1} , \cdots , c_{n} \in \mathcal{C}$ 이 주어져 있어도 $d_{k} ( c_{1} ) , \cdots , d_{k} ( c_{n} )$ 를 계산하기 어려워야한다.

설명

위의 성질들을 요약하면 메세지를 볼 자격이 있는 사람만 쉽게 보고 자격이 없는 사람은 볼 수 없는 것이 유용한 암호 체계다. 중간에 메세지를 가로채는 공격자가 없다면 가장 좋겠지만, 설령 있다고 하더라도 그 내용을 들키지 않아야 한다. 또한 통신을 하는 당사자들끼리도 암호화와 복호화가 너무 오래 걸린다면 보안이 좋아도 통신의 기능을 너무 많이 포기해야한다.