베루의 보안공부

정수론의 기본 바탕인 나눗셈 관계식,  자주 쓰일 유클리드 알고리즘에 대해 다뤄보고자 한다.

 나눗셈 관계식이란 피제수(dividend), 제수(divisor), 몫(quotient)으로 되어있는 관계식이다.

그림으로 이러한 형태로 나오며, 이는 차 후 합동식에서 나머지와 최대공약수를 구하기 위해 자주 쓰인다.

이 식을 가로형태로 만들면 a = q x b + r  이고 0  ≤  r  <  b의 조건을 성립해야한다.

암호학에서 사용하는 나눗셈 관계식은 2개의 제약이 존재한다.

1. 재수는 양의 정수 (b > 0)이다.
2. 나머지는 음이 아닌 정수(r  ≥ 0) 이여야 한다.

유클리드 알고리즘 : 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다

유클리드 알고리즘은 아래 2개를 기반하고 있다.

1. gcd(a, b) = a이며 0은 모든 정수의 배수이고 모든 정수는 0의 약수이다.
2. gcd(a, b) = gcd(b, r)이다, 이 때 r은 a을 b로 나눈 나머지다.

계산을 할 때는 알고리즘 표를 작성을 해야 계산하기 유리하다. 

위와 같은 형태가 유클리드 알고리즘을 계산할 때 쓰이는 "표" 이다.

유클리드 알고리즘은 사용은 하나 한계가 있기에 이름하여 "확장된 유클리드 알고리즘" 을 사용한다.

확장된 유클리드 알고리즘이며 r = r1 - (q x r2), s = s1 - (q x s2), t = t1 - (q x t2) , s1  =  1,  s2  =  0,  t1  =  0,  t2 = 1은 해당 알고리즘에 고정된 값이며, 주로 사용되는 공식은 디피헬먼, RSA, 역원,  원시근등이 존재한다. 

확장된 유클리드 알고리즘의 공식은 (a x s)  + (b x t) = d , d는 최대공약수 1이다. 

양수가 아닌 음수가 존재 할 때 

• a  >  0, b  <  0 인 경우
• a  <  0, b  >  0 인 경우 

즉, r1 = 음의 정수(피제수),  r2 = 양의 정수(제수) 로 계산을 시작해야한다.

현대 암호로 들어올 때 정보통신과 컴퓨터의 발달로 인해 암호학이 발달하는 계기가 탄생하였다.

컴퓨터 중심으로 발달된 암호알고리즘은 대표적으로 RSA 알고리즘( Ron Rivest,  Adi Shamir, Leonard Adleman Algorithm) , 디피 헬만 알고리즘(Diffie-Hellman Algorithm)이다. 

RSA와 DH알고리즘의 공통점은 "합동식"을 기반으로 만들어졌으며, 어렸을 때 배웠던 최대공약수, 정수 등을 자주 사용하게 된다. 

합동식 : a ≡ b( mod m )

미국의 CIA는 모두가 알 것이다. 기밀성(Confideniatlity) 무결성(Integration) 가용성(Availblity)을 시작으로 암호 알고리즘에 "필수"로 들어가게 되어야 하며, 시간이 지난 후 부인방지(Non-repudiation)가 들어가야 한다는 새로운 조건이 추가되었다.

RSA 알고리즘

DH 알고리즘

보안에 대한 경각심이 생기게 된 여러 사건이 나오면서 자연스럽게 암호학 또한 발달을 하였다. 암호학은 수학과 관련이 있다 보니 기존 알고리즘의 새로운 수식을 합치면서 현재까지 쓰이고 있다. 

기초 역사에 대해서는 여기까지 작성하여, 작성자가 공부를 어느정도 끝 마치고 여유가 생긴다면 차 후 "미래의 암호 알리즘으로 쓸 수 있는 양자 암호"에 대해 다뤄보겠다

암호는 오래전 부터 쓰였다.

역사 순서대로 들어가본다면 고전 암호 (고대 그리스 ~ 19세기 말) 의 카이사르 암호, 카이사르를 보완한 아핀암호, 전치 암호등이 존재한다.

일정한 거리를 만든다음 해당 거리에 존재하는 알파벳을 치환하는 방식이다.

f(x) ≡ x+n (mod26)

옆으로 이동하는 거리 = Key

x는 평문이며, n은 거리를 나타내는 key이고, 알파벳은 26개가 존재하기에 mod값은 26을 최대로 가집니다.

전치 암호는 "행렬"의 기반으로 만든 암호이다. 

평문으로 미리 정의된 길이로 나누며, 각 블록의 문자 위치를 바꾸는 규칙(Key)를 사용하여 문자열을 재배열을 진행하고 난 후 암호문을 생성합니다.

해당 암호를 수식화 시킨다면

C = F(P)

암호문(Cipher text)  = 위치를 나타내는 함수 F(평문(Plain text))

로 보일 수 있다. 

근대 암호 ( 20세기 전반부 : 전신의 발명 ~ 제2차 세계대전 이전) 로 들어가면서 기계, 통신이 발달하면서 만들어진 대표적인 기계암호 "에니그마"가 있다. 

에니그마는 2차 세계대전 당시 나치독일이 쓰던 기계로 처음 등장했을 때 연합군이 해독하기 정말 어려웠다라는 기계중 하나이다.

에니그마의 원리를 이미지로 보여준다면

문장을 작성하고 해당 문자에 "로터(KEY)" 값을 넣어 한번 초기화를 시키고 다시 로터를 돌리는 방식을 기반으로 해독하기 어렵게 만드는 원리이다.