[2021/01/23][짤막한 이야기 - 이산 로그]

[2021/01/23][짤막한 이야기 - 이산 로그]
암호학에서 이산 로그(“이산 대수 문제”라고도 알려짐)는 매우 중요한 개념 중 하나이다.
만약 당신이 “2^x = 16”이라는 표현식을 본다면, “x = 4”임을 쉽게 알 수 있다.
그러나 일반적인 로그 연산이 적용될 수 없는 상황도 있으며, 이를 “이산 로그”라고도 한다.
이산 로그의 정확한 조건은 “구글” 혹은 “네이버”에서 “이산 로그 문제”로 검색할 수 있다.
해당 예시에서 밑이 “G”이고 지수가 “Ra”, “Rb”인 수를 도청 공격으로 획득할 수는 있지만, “Ra”와 “Rb”를 추출할 수는 없다. (G가 공개되었다고 하더라도.)
“앨리스(Alice)”는 “Ra”를 알고 있으며 “G^Rb”를 “밥(Bob)”으로부터 받았으니 “G^(Ra*Rb)를 계산할 수 있고, 밥 또한 같은 값을 계산할 수 있다.
“이브(Eve)”는 “G^(Ra*Rb)”를 계산할 수 있을까? 불가능하다.
왜냐하면 이브는 “G^R”로부터 “R”을 추출하는 것이 불가능하기 때문이다. (이브 뿐 아니라 어느 누구도.)
또한 “G^Ra”와 “G^Rb”로 “G^(Ra*Rb)”를 계산하는 것도 불가능하다.
따라서 “키 합의(Key Agreement)” 과정에서 이산 로그를 활용하면 다소 안전한 “키 교환(Key Exchange)”이 가능하다.
이것은 기본적인 “디피-헬만 키 합의 프로토콜”으로 알려져 있다.
그런데 이것은 정말 안전할까?
[관련된 짤막한 이야기 - 키 합의 & 키 전송[2021/01/21]]
#이야기#루니프#암호학#이산#로그#디피#헬만#키합의

[2021/01/23][Short Story - Discrete Logarithm]
In cryptography, the discrete logarithm(Also known as the “Discrete Logarithm Problem”) is one of the important concepts.
If you look at the expression such as “2^x = 16”, you can easily find that “x = 4”.
However, there are situations in which the logarithm operation cannot be applied, and this is also called “Discrete Logarithm”.
The exact conditions of the discrete logarithm can be found if you search “Google” or “Naver” with the keyword “Discrete Logarithm Problem”.
As in the example, the number having the base “G” and the exponents “Ra” and “Rb” is obtained by performing an eavesdropping attack, but “Ra” and “Rb” cannot be calculated. (Even if G is known to all.)
Since “Alice” knows “Ra” and received “G^Rb” from bob, she can calculate “G^(Ra*Rb)”, and “Bob” can also calculate it.
On the other hand, can “Eve” calculate “G^(Ra*Rb)”? This is impossible.
Because Eve is impossible to extract “R” from “G^R”. (Not only Eve but anyone)
Eve is also unable to calculate “G^(Ra*Rb)” with “G^Ra” and “G^Rb”.
So, using a discrete logarithm in the “Key Agreement” process enables a somewhat secure “Key Exchange”.
This is known as the basic “Diffie-Hellman Key Agreement Protocol”.
By the way, is this really secure?
[Related Short Story - Key Agreement & Key Transport[2021/01/21]]
#Story#LootNiP#Cryptography#Discrete#Logarithm#Diffie#Hellman#KeyAgreement