네모난 세상
[본문스크랩] Diffie-Hellman방식이 지수 키 교환방식라고 불리는 .. 본문
Written by windwiser
Security을 공부함에 있어서 역시나 중요한 부분은 대부분은 암호학에 속해 있다는 생각이 든다. 오늘은 그중에서 Diffie-Hellman Algorithm이랄까 키교환 방식에 대한 애기를 해볼까 한다. 임베디드라는 주제와 다소 거리가 있으나,
개인적으론, 임베디드 시스템에서의 보안적 측면에 대한 것을 기본적인 선에서 닦아두려 이런 것을 공부하고 있는데, 글쎄.. 언젠가 이런 노력을 빛을 보게될지..
이 문서를 이해하기 위해서는 다소의 수학적 background와 RSA암호화 알고리즘으로 유명한 공개키 알고리즘에 대한 이해가 선행되어야 한다.
먼저 출발점을 잡아보자.
간단히, 공개키 암호화 알고리즘 방식은 소히 키분배에서 쓰일수 있다고 하는데,
이것에 대해 먼저 짚고 넘어가 보자.
공개키 암호화방식에서는 두개의 key를 가진다. 실제 이것이 핵심이다.
Ku Kr 이라고 보통 표기하는 공개키와 개인키 혹은 비밀키라는 것이다.
이것은 A라는 송신측에서, 어떠한 비밀키를 선정한다.(이것이 또한 중요하다.!!인지해두기)
그리곤, 이를 수신측인 B의 공개키로 암호화한다.(공개키이기에 알수 있으며 알수있기에 암호화가 가능할 것이다.) 그러면, 이를 B가 이를 받아서, 개인키로 복호화한다.
또한 중요한 매우 기본적인 생각은, 개인키는 비밀키 즉, B가 아니면 누구도 모른다는 것이다. 또한 b의 공개키로 암호화된 것은 b의 비밀키 개인키로만 복호화될수 있다는 것이다.
같은 concept으로,
B는 A가 선정해서!!(중요하다.) 보내준 그 키 대체적으로 이를 k라 부르겠다.
이 k를 다시 a의 공개키로 암호화하여 보내주고 같은 방식으로 a또한 이를 자신의 개인키로 복호화하여 키를 알아낸다.
이로써 둘다 동일한(이것은 중요하다.) 키를 가지게 된다.
공개키 알고리즘의 기본적인 concept에 대해서 애기해 보았다. 물론, 이건 핵심적이고 또한 기본적인 관점에서 애기한거라, 이것이 다는 아니다.
하지만 Diffie Hellman의 키분배 방식을 설명하기 위해 도입하기에는 충분한듯 하다.
언뜻보아 완벽해 보이는 이 방식에 문제가 있을까?
쌍방간 아니 그 이상의 통신에서, 키라는 것은,(실제 이것은 Ks라 표현되는 세션키라한다.) 쌍방간에 동의된 것이어야지 어느 한쪽에서 일방적으로 결정해선 곤란하다.
이것 말고도, 신분 위장이나 재전송공격같이 중간에서 공격자가 개입하는 형태에도 공격당할 여지가 있다.
또한 잊지 말아야 할 것은 위 방식에서 둘다 같은 Ks를 가진다는 것이다.
허나, 이 Ks를 어느 쪽에서 일방적으로 정하는 형태가 아니면서 같이 똑 같은 Ks를 가질수 있는 방법이 없지 않을까?하는 출발점에서 Diffie Hellman의 생각이 탄생했다.
잠시 원시근이 먼지 이해하지 못하는 분들을 위해 잠시 애기를 하면,
이 개념이 상당히 중요하다.
뿌리근이라고 하며,
다음 두조건이 정확히 맞아야만, 원시근 뿌리근이라 할 수가 있다.
먼저,
원시근이 되려면 정확히 법p와 즉 moduler p와 정확히 서로 소이어야 한다.
즉, gcd가 1이어야 한다.
두번째로,
그 서로 소인 수중에서, 말하자면, 원시근이 될수 있는 그놈들중에서,
그놈들의 지수승을 p로 mod햇을 때 1이 되는 만족하는 그때의 최소 위수가
정확히 p-1과 일치하여야만, 뿌리근이 될수가 있다.
이때 중요한 가정은 p가 소수라는점 이 p가 소수이면 p-1개의 원시근이 반드시 존재한다는 점이다.
원시근 애기는 이정도에서 그만하고,
위 그림에서,
∂ 는 p보다 작은 수이고, 소수 p의 원시근이라 하였다. ∂은 7과 서로 소이다.
이는 7-1=6 즉, 위에서 3에 대해서 법7에서 계산을 해보아서,
각 값에 대해서 mod7을 했을 때 1이 나오는 놈의 위수가 6임을 알수가 있다.
즉 3은 원시근이다.
이런 원시근을 여러 개 생각해 볼수가 있다.
이때, 그의 위수들은 법에 따라 즉 p에 따라 p-1승까지 가능할 것이다.
지금까지의 내용을 이해했다면 앞으론 별문제 없다.
아 참고로, 원시근이라면, 그 결과집합이 완전한 형태일 것이다.
그것은 위에 보면 결과값들이 중복없이 완전함을 의미한다.
그렇다면, 어떻게 합의된 공동키를 서로 가지게 할 수가 있을까?
앞서 1에서 p-1승까지 위수가 범위를 가짐을 애기했다.
이는 원시근애기를 하면서 왜 그런지 애기했으니,
그렇다면, 이 지수들을 알아낼수 있을까?
즉 밑수와 p를 알고 있다고 해서 이놈을 알 수가 잇을까?
y= ax mod p 여기서, 0≤x≤ p-1
y= ax mod p 형태에서 y, a, p를 알더라도 x를 계산하기는 매우 어려움
A라는 놈과 B라는 놈이 서로 통신을 한다고 했을 때,
A라는 놈이
양쪽다 ax mod p bx mod p 이 두텀을 계산한다고 하자.
이제 이를 서로 교환해서 주고받는다.
그리곤, A는 받은 bx mod P에 대해서 ax mod p승을 한다고 하자.
마찬가지로 B쪽에서도 반대방향의 연산을 한다고 하자.
위쪽을 보면, b에서 보내온 Xb를 밑수로 쓴다고 해보죠.이는 실제
제일 밑에처럼 결국 a에서 b로 보냈을 때 랑 결국은 결과가 같음을 알수가 있습니다.
즉, 동일한 키를 서로 가진게 된 것이죠!!
이는 실제 동일한 서로 합의하는 공동키를 어떻게하면 분배할 것인가에 초첨을 맞춘것입니다. 그리고 이 알고리즘은 , ax mod p 를 예를 들어
A와 p를 안다고 해도 x는 실제 수학적으로 매우 구하기 어려운 성질을 이용한 것입니다.
위 그림을 보죠.
앞서 주저리 주저리 애기한 내용을 단방에 가르쳐 줍니다.
랜덤하게 위수하나를 잡는데 물론 그놈은 q보다 작고 이때 q는 소수이며,
중요한게, 이 랜덤으로 잡은 놈은 p-1과 gcd가 1입니다. 즉 원시근의 만족하는 최소 위수라는 애기죠 즉 q와 gcd가 1이되는 그 최소위수라는 애기입니다.
이놈은 비밀입니다. 하지만 나머지를 알아도 앞서애기되로 이놈을 구하기란 거진 불가능합니다. 이놈을 위수로 해서 Ya를 보냅니다.
그럼 b는 이놈을 밑수로 해서 자기꺼를 위수로 해서 승을 합니다.
이놈은 실제 반대로 햇을 때 a에서 한거랑 같다는 것입니다.
이것이 바로 Diffi – Hellman의 기본적인 Concept입니다.
이 Diffie-Hellman을 지수 키 교환방식이라고도 부릅니다.
왜 그럴까요? 감이 오나요?^^ 그렇다면 제대로 이해한 것입니다. ~
즉, 서로 랜덤하게 지수를 만들고 이를 서로 교환했죠? 그리고 이 두놈을 서로 상대적으로 해서 승을 취하는 것인데 이는 실제, 결국 둘다 같은 결과가 되죠
a의 b의 c승은 a의 c의 b승과 같죠?^^
저도 요즘 암호쪽 배우고 있는데,
이렇게 배우는것들이 나중에 임베디드 시스템에 혹여나
보안쪽 기술을 접목시킬 때 도움이 되기를 바라고 있답니다. ~