이번 시간은 암호학에서 많이 사용되는 수학적 개념을 살펴보고자 한다. 암호학의 모든 메커니즘은 수학을 기반으로 이루어지기 때문에 기본적인 수학 개념없이는 암호화 및 복호화되는 과정을 설명하기란 어렵다. 물론 깊은 내용의 수학적인 개념을 다루지는 않을 것이고, 아주 얕은 수준에서 '배타적 논리합'과 '합동식'에 대해서 살펴보려고 한다.
암호학에서 사용되는 수학
암호학(Cryptography)을 연구하는 많은 사람들이 바라보는 일차적인 목적은 '평문의 데이터를 어떻게 암호화할 것인가?'일 것이다. 왜냐하면 암호학은 데이터를 안전하게 암호화하여 기밀성을 유지하기위한 목적으로 개발되었기 때문이다. 따라서 안전하게 암호화하지 못하여 누구나 암호문을 해독할 수 있다면, 그것은 더 이상 암호라고 부르기 어려울 것이다.
그런데 여기서 이야기하는 '어떻게 안전하게 암호화할 것인가?'에 대한 답은 결국 '어떤 수학적 메커니즘을 적용할 것인가?'로 볼 수 있다. 암호를 생성하는데 사용되는 알고리즘은 아주 기본적인 연산을 활요하는 것부터 매우 고난이도의 수학적 개념을 사용하는 것까지 다양하다. 많은 수학적인 개념을 다루기 앞서 우리는 오늘 아주 기본적인 수학적 개념인 '배타적 논리합'이라고 불리는 'XOR'연산과 '합동식'에 대해 알아보도록 하자.
배타적 논리합(eXclusive OR)
배타적 논리합(eXclusive OR, XOR)은 무엇일까? 우리가 흔히 'XOR 연산'이라고 생각하는 배타적 논리합은 두 개의 입력 비트 중 하나만이 1일 때 결과가 1이 되는 논리 연산이다. 그래서 배타적 논리학을 정확히 구분하자면 단순 수학 연산이 아니라, 수리 논리학에 가깝다. 그리고 XOR 연산은 보통 "⊕"나 "xor"로 나타내어지며, 다음과 같은 진리표를 가진다.
여기서 A와 B는 입력 비트를 나타내고, A XOR B는 XOR 연산 결과를 나타낸다. XOR 연산의 특징은 두 입력이 서로 다를 때만 결과가 1이 되며, 입력이 모두 같거나 모두 다를 때만 결과가 0이 된다. XOR은 다양한 컴퓨터과학 및 정보 이론 응용에서 사용되며, 특히 암호학, 오류 감지 및 수정, 그리고 이진 데이터 처리에 널리 활용되고 있다.
XOR 연산은 평문의 암호화나 암호문의 복호화 연산 때 사용될 수 있다. 나중에 스트럼 암호에 대해서 이야기를 나눌 때 살펴보겠지만, 지금은 스트럼 암호의 연산과정만 살짝 살펴보자. 예를 들어, 평문(Plaintext)의 데이터가 '11011010 10101101 00110011' 이고, 키(Key)의 데이터가 '01101011 11011011 01010101' 이라면 이 둘의 XOR 연산은 어떻게 될까?
XOR 연산 결과는 '10110001 01110110 01100110' 이다. (정답 드래그 이용)
그렇다면 나온 정답을 가지고 다시 '키 스트림 값'을 XOR 연산하면 어떤 값이 나올까? 바로, 평문 값을 얻을 수 있다. 이렇게 평문 값과 키 스트림 값을 XOR 연산하여 암호문을 생성하는 암호화와 평문을 만드는 복호화 과정을 수행할 수 있다. 추후에 다뤄볼 여러가지 암호의 연산에서도 가장 많이 사용되는 연산 방법이니, 헷갈렸다면 이번 기회에 확실히 알아두도록 하자!
합동(congruence)
합동식(Congruent)는 무엇일까? 우선, 합동식에 대한 개념을 파악하기 전에 '합동'에 대한 개념을 먼저 살펴보자. 합동(congruence)은 비교하고자 하는 두 대상에 대한 형태나 모양, 크기, 양이 같음을 나타내는 표현이다. 예를 들어, '기하학적인 합동이다.' 라고 한다면, 비교하고자 하는 두 도형의 모양과 크기가 같다는 것을 의미할 수 있다. 하지만 합동은 단순히 같음 그 이상을 나타내는 표현이다. 아래 그림의 두 삼각형을 비교해보자.
두 삼각형은 서로 같아보인다. 그러나 두 도형의 좌표값(x,y)은 엄연히 다른 두 도형이다. 그래서 두 삼각형은 같은 삼각형이라고 표현할 수 없다. 하지만 삼각형의 위치를 변경하거나 각도를 틀 수 있다면 어떻게 될까? 첫번째 삼각형이나 두번째 삼각형을 회전시킨다면 같은 삼각형을 만들 수 있을 것이다. 이러한 관계를 합동이라고 이야기 할 수 있다. (수학적으로 합동의 관계를 확인할 수 있는 충분 조건들이 있지만, 거기까진 설명하지 않도록 한다...)
그래서, 합동은 완벽히 같진 않지만, 대략적으로 같음을 의미한다.
이 합동의 개념을 실생활에서 가장 많이 쓰이는 곳은 아마도 시간을 나타낼 때일 것이다. 예를 들어, 우리가 저녁 식사시간을 이야기할 때 한 사람이 7시를 이야기하든 19시를 이야기하든 듣는 사람에게 문제가 없음을 알 수 있다. 왜냐하면 7시든 19시든 우린 동일하게 오후 7시를 생각하기 때문이다. 이처럼 7시와 19시는 다르지만, 같다고 할 수 있는 이런 관계를 합동이라고 할 수 있다.
그러면 이제 합동식에 대해서 살펴보자.
합동식(Congruent)
합동식(Congruent)은 두 정수가 특정 조건에서 합동임을 나타내는 식을 이야기한다. 그래서 '두 정수에 대해서 특정 조건(값)을 나눳을 때, 몫이 아닌 나머지 값이 일치하는가?' 를 통해서 합동의 유무를 가릴 수 있다. 우리가 앞서 이야기했던 7시와 19시가 12시간제 조건에서 합동임을 나타내는 합동식은 아래와 같다.
7 ≡ 19 mod 12
7을 12로 나눈다면 몫이 0, 나머지는 7이다.
19를 12로 나눈다면 몫이 1, 나머지는 7이다.
나머지 값이 동일한 7인 것을 확인할 수 있다.
이러한 합동식은 각 개인이 알고 있는 a, b와 둘 다 알고 있는 x 값을 통해서 암호화 통신을 하는데 사용할 수 있다. 대표적인 예로 RSA 암호시스템이나 DH(디피-헬만) 프로토콜의 연산에 사용된다.(연산에 대한 적용 예시는 RSA나 DH 프로토콜에 대해서 이야기나눌 때 적용해보도록 한다.) 이러한 알고리즘에 사용될 수 있는 이유는 합동식의 성질 때문인데, 두 정수(a, b)가 합동이라면 두 정수에 특정 수(c)를 합하거나, 곱하거나, 빼거나, 나누더라도 합동식은 동일하게 적용되기 때문이다.
(a + c) ≡ (b + c) mod x | (a - c) ≡ (b - c) mod x
(a · c) ≡ (b · c) mod x | (a / c) ≡ (b / c) mod x
정리(Summury)
이번 시간은 '배타적 논리합(XOR 연산)'과 '합동식'에 대해 살펴보았다. XOR 연산은 스트럼 암호와 같은 바이너리 코드의 데이터를 연산하는데 사용되는 것을 알아보았고, 이 연산을 통해 암호화 또는 복호화에 적용할 수 있음을 확인했다. 그리고 합동식을 통해 두 정수의 합동 관계를 나타낼 수 있는 방법을 알아보았다. 이 합동식은 합동의 관계안에서 특정 수의 합하거나 빼거나 곱하거나 나누어도 동일하게 합동이 적용될 수 있기 때문에 RSA 암호시스템이나 DH(디피-헬만) 프로토콜 연산에 사용될 수 있다.
'Study > Security' 카테고리의 다른 글
| 암호학(Cryptrography)의 시작 (0) | 2023.12.01 |
|---|