암호에 대한 이해 - 비대칭 암호 알고리즘

비대칭 암호화 방식은 (Diffie-Hellman)이 위에서 콜라를 마시다 아래층으로 내려가면서 번뜩이는 아이디어로 처음에 어떻게 하면 둘 사이에 키를 쉽게 관리할 수 있을까 키 분배에 대한 문제를 해결하다가 생각해냈습니다.

 

모든 사람은 딱 한 쌍의 키(공개키,비밀키)를 갖고 있으면 됩니다. 공개키는 누구나 다 알 수 있도록 오픈하는 키, 비밀키 또는 개인키는 나만 알고 있는 키입니다.

 

암호화는 누구나 할 수 있어야 되기 때문에 Bob의 공개키로 암호화하고 암호화한 키와 한 쌍인 Bob의 개인키로만 복호화 할 수 있습니다.

 

 

 

키 관리가 굉장히 쉬워집니다. 비밀로 유지해야 하는 건 자신의 비밀키뿐입니다. 하나정도는 안전하게 유지할 수 있습니다. 대칭키의 문제를 바로 해결할 수 있습니다. 하지만 어떻게 구현할 것인가...

 

비대칭 암호화는 굉장히 풀기 어려운 수학적 문제를 가지고 와서 이 문제를 풀어야만 깰 수 있는데 아직 오픈된 problem으로 풀 수 없는 문제에 기반하고 있습니다. 물론 key 사이즈에 기반하고 있지만 공개키는 최소 1024bit의 키를 사용합니다. (번의 경우의 수를 다 해봐야 풀 수 있기 때문에 사실상 불가능)

 

수학적 난제를 이용한다고 했는데 (정수론에 대해서는 나중에 시간이 되면 글을 올리도록 하겠습니다)

a (mod n)  여기서 z는 a의 discrete logarithm이라고 합니다.

은 와 같습니다. 따라서 와 같습니다. 실수에서 log문제와 같은 문제입니다.

그러면 z를 찾고 싶으면 log를 써서 찾으면 되지 않을까 생각할 수 있지만 그게 어렵다는 것이죠. 안풀립니다.

모든 경우를 해보면 답을 구할 수 있지만 딱 얼마다 라고는 찾을 수 없다는 말과 같습니다.

 

☞ Discrete Logarithm Problem(DLP)

모두 알려줬지만 mod n 일때 x를 찾는 것이 어렵다는 것입니다. x를 비밀로 유지하고 를 만들어서 y로 하고 g,y를 공개해도 x는 노출되지 않는다는 겁니다. 현대 암호의 기반이됩니다.(DLP에 기반하고 있다)

 

암호에서는 prime number를 좋아합니다. 어마무시하게 큰 prime number가 필요합니다. 1024비트의 크기정도..

하지만 그 큰 수가 prime인지 아닌지 아는 것 자체가 어렵습니다. 그래서 엄청나게 큰 숫자가 주어졌을 때 이 숫자가 prime number인지 아닌지 확인하는게 먼저입니다. 그래야 사용을 할 수가 있겠죠.

가장 간단한 방법은 1부터 그 수보다 작은 수까지 나눠보는 겁니다. 하지만 이 말은 번 다 시도한다는 것과 같습니다.

어떻게 빨리 prime인지 알아낼 수 있을까요?

Fermat's의 소정리를 이용하는 겁니다. 만약 prime수라고 한다면 임의의 n보다 작은어떤 수 a에 대해서

 

를 만

 

족합니다.

따라서 1이 나왔다고 페르마 소정리를 해봤을 때 1이 나왔다고 하면 이 숫자는 prime일 확률이 높다는 겁니다.

하지만 예로 341을 들어보겠습니다. 이 숫자는 11과 31의 곱입니다. 굉장히 소수처럼 보입니다. 페르마 소정리를 해보면

을 해보았습니다. 그랬더니 1이 나옵니다. prime이 아닌 합성수임에도 불구하고 1이 나옵니다. 따라서 이 알고리즘을 믿을 수 없게 됩니다. 그럼 여기서 더 발전을 시켜보겠습니다. 2에 대해서만 하지말고 여러번 시도해보는 겁니다.

진짜 prime이라면 어떤 수를 해도 1이 나올 것이기 때문입니다. 합성수는 저렇게 예외적인 경우가 있을 수있지만 모든 경우에 대해서 1이 나올 순 없습니다.

따라서 아주 다양한 k개의 서로 다른 a들에 대해서 알고리즘을 돌립니다. k번 정도 했을 때 계속 1이 나오면 prime입니다.

충분히 k를 늘려서 해보는 겁니다.

여기서 하고 싶은 말은 prime이다 찾는 것도 굉장히 어렵다 입니다.

 

 

비대칭 암호화 방식은 크게 2가지가 있습니다.

● ElGamel

->DLP문제의 어려움에 안전성을 기반.

일때, g와 y가 알려져도 x를 알 수 없다 기반.

 

 

● RSA

->소인수분해의 어려움에 기반.

 

다음 글에서 ElGamel Encryption부터 공부해 보도록 하겠습니다~