[논문]지수연산 부분군의 충돌을 이용한 Diffie-Hellman 기반의 비대칭 키 교환 방법

송준호; 김성수; 전문석

doi:10.3745/ktsde.2020.9.2.39

지수연산 부분군의 충돌을 이용한 Diffie-Hellman 기반의 비대칭 키 교환 방법
Diffie-Hellman Based Asymmetric Key Exchange Method Using Collision of Exponential Subgroups 원문보기

정보처리학회논문지. KIPS transactions on software and data engineering. 소프트웨어 및 데이터 공학, v.9 no.2, 2020년, pp.39 - 44

송준호 (숭실대학교 컴퓨터학과) , 김성수 (한국정보화진흥원 ICT융합본부) , 전문석 (숭실대학교 컴퓨터학과)

초록
AI-Helper

본 논문에서는 사전연산이 가능한 세션 키 쌍을 이용하여, 최소의 정보만을 노출하여 키 교환이 가능한 변형된 Diffie-Hellman 키 교환 프로토콜을 보인다. 기존 Diffie-Hellman 및 Diffie-Hellman 기반 기법들의 보안성인 이산대수문제를 변형하여 생성원이 노출되지 않도록 설계함으로써 전송되는 암호문에 대한 공격으로부터 향상된 보안성을 가진다. 제안하는 기법에 실제 값을 적용하여 알고리즘의 동작을 증명하고 기반이 되는 기존 알고리즘과의 수행시간과 안전성을 비교 분석하여, 키 교환 시점 연산량을 유지하며 두 기반 알고리즘 시간복잡도의 곱 이상으로 알고리즘의 안전성이 향상되었음을 보였다. 제안하는 알고리즘을 기반으로 보안성이 향상된 키 교환 환경을 제공할 수 있을 것으로 기대된다.

Abstract ▼ AI-Helper

In this paper, we show a modified Diffie-Hellman key exchange protocol that can exchange keys by exposing only minimal information using pre-computable session key pairs. The discrete logarithm problem, which provides the safety of existing Diffie-Hellman and Diffie-Hellman based techniques, is modified to prevent exposure of primitive root. We prove the algorithm's operation by applying the actual value to the proposed scheme and compare the execution time and safety with the existing algorithm, shown that the security of the algorithm is improved more than the product of the time complexity of the two base algorithms while maintaining the computation amount at the time of key exchange. Based on the proposed algorithm, it is expected to provide a key exchange environment with improved security.

주제어

표/그림 (7)

표 Table 1. Security Strength of Public Key Cryptographic Algorithms
그림 Fig. 1. Diffie-Hellman Based Asymmetric Key Exchange Method using Collision of Exponential Subgroups Procedure
표 Table 2. Exponential Subgroups Asymmetric Key Exchange Parameter
$Table 3. Example of Algorithm Application in <TEX>$Z^*_{487}$</TEX> - Application of Parameter Value$ 표 Table 3. Example of Algorithm Application in $Z^*_{487}$ - Application of Parameter Value
그림 Fig. 2. Diffie-Hellman, Pre-Generation Key Pair, Elgamal and Proposed Algorithm Comparison of Time Required for Calculation of the Same Key
그림 Fig. 3. The Size Ratio of the Circulating Subgroup
표 Table 4. Comparison of Decryption Time for Attacks Against Discrete Algebra Problem, Factorization Problem, and Proposed Algorithm

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 기존 비대칭 키 키 교환 알고리즘의 안전성을 향상시키기 위해 순환부분군의 역원을 이용하여 밑수와승수를 모두 비밀로 하는 생성원이 노출되지 않는 비대칭 키교환 방법을 제안한다.
본 논문에서는 동일 키 길이에서 기존 이산대수 문제를 기반으로 하는 알고리즘보다 안전성이 향상된 방법을 제안한다. 안전성을 개선하는 과정에서 늘어난 연산량을 역원 쌍에대한 연산을 미리 수행할 수 있도록 설계하여 키 교환 시 발생하는 절차의 부하를 분산시킨다.
본 논문에서는 보안성이 필요한 환경에서 통신 노드 간 대칭키를 수립하는데 널리 사용되는 Diffie-Hellman 키 교환프로토콜을 기반으로 하는 개선 기법을 제안한다.

가설 설정

Diffie-Hellman 알고리즘은 갈루아 체와 생성원을 이용하여 이산대수 문제를 구현하였다[2]. 기반을 두는 모든 가정은 유한순환군을 기반으로 하며, 그룹의 위수는 인수분해가 어려운 큰 소수를 약수로 가지도록 한다. 군을 생성하는 생성원이 필요하며, 군의 원소 중 하나가 주어졌을 때, 그 군의 원소를 생성하는 생성원의 승수를 찾는 것이 이산대수 문제이다.

제안 방법

Nyang은 역원의 존재를 이용하여 지수연산 시간이 합의를 지연시키지 않도록 사전 키 쌍을 구성하는 방법을 제안하고 있다[3]. Diffie-Hellman 키 교환 알고리즘을 기반으로하였으며, 전송하는 생성원의 승수에 대해 역원 쌍을 미리 계산하여 저장해 두도록 설계하였다. 사전에 생성된 역원 쌍은‘역변환 지수 문제’에 기반하여 안전하게 세션키에 연산된 값을 복호화하여 합의할 수 있도록 하였다[4].
Hellman, Nyang의 사전 역원 생성, Elgamal과 제안 알고리즘을 대상으로 동일수준의 키 연산을 기준으로 각 1000000회 연산하여, 각 10000번의 수행시간마다 표본화하여 100건의 수행시간을 대푯값으로 정리하였다. 제안한 알고리즘은 기존 알고리즘과 수행시간의 증가율을 비교해 볼 경우 Diffie-Hellman 대비 102%, 사전 역원 생성 대비 193%, Elgamal 대비 107%의 수행시간을 보였다.
각 알고리즘에 공격 결과는 도식화하여 비교하기엔 현저한차이가 있어, 1000 이상의 소수 17개의 공격 결과에 대한 비교 표로 작성하였다. 이산대수 문제와 소인수분해 문제에 대한 공격은 밑수의 크기에 비례하여 약 2배의 차이를 보였으나, 제안 알고리즘은 해당 모듈러 값에 해당하는 모든 순환부분군에서 일치하는 메시지 값을 구하여 단순히 확률적으로비교하기 힘든 시간차이를 보였다.
같은 컴퓨팅 환경에서 각 군의 생성원들로 생성원별 동일메시지 값을 생성하는데 까지 걸린 시간을 측정하였으며, 공격하는 밑수 g는 각 소수의 절반보다 큰 임의의 완전부분군을 대상으로 하였다. 이산대수의 복잡성에 기반을 둔 알고리즘은 Equation (5)를 기준으로 밑수 g, 모듈러 p에서 지수연산 값 x를 1부터 증가시켜 공격하였고, 소인수분해의 복잡성에 기반을 둔 알고리즘은 Equation (4)의 암호화된 메시지S에 대한 공격으로, x로 반복 지수연산하여 메시지를 찾아낼때까지 걸린 연산시간을 측정하였다.
제안 알고리즘의 효율성을 평가하기 위해서는 비교 대상알고리즘과 동일한 절차를 보아야 한다. 그러나 제안 알고리즘의 사전 키 생성 절차는 타 알고리즘에 존재하지 않으며,제안하는 알고리즘은 키 교환단계에 연산량을 줄이기 위하여사전 생성이 가능하도록 설계하였다. 이에 키 교환을 위한 사전 절차를 미리 수행한 것으로 가정하여, 키 교환 요청이 발생한 시점에서 키 교환 시 소요되는 연산부하에 대해 분석하였다.
다음으로 제안 알고리즘의 공격에 대한 안전성을 평가하기에 앞서, 제안 알고리즘의 연산이 이루어지는 군이 안전한지에 대한 평가를 하였다. 이를 위해 지수연산의 역원이 존재하는 순환부분군을 생성하는 생성원이 군의 원소 중 얼마나 되는지 알아야한다.
분석 과정에서 비교할 알고리즘으로 이산대수의 복잡성에 기반을 둔 알고리즘과 소인수분해의 복잡성에 기반을 둔 알고리즘을 가정하고, 각 알고리즘에서 전송되는 메시지를 탈취하여 탈취한 메시지 값을 생성하는 키를 찾아내는데 소요되는 시간을 측정하였다. 단, 소인부분해의 복잡성에 기반을 둔 알고리즘의 경우 동일한 시간 복잡도를 가지는 것으로 알려진 순환공격을 수행하였다.
이산대수의 복잡성에 기반을 둔 알고리즘은 Equation (5)를 기준으로 밑수 g, 모듈러 p에서 지수연산 값 x를 1부터 증가시켜 공격하였고, 소인수분해의 복잡성에 기반을 둔 알고리즘은 Equation (4)의 암호화된 메시지S에 대한 공격으로, x로 반복 지수연산하여 메시지를 찾아낼때까지 걸린 연산시간을 측정하였다. 단, 제안하는 알고리즘에서는 공격 시 전송되는 메시지와 일치하는 g^x 후보군에 대한 검증을 수행하는 절차도 필요하나, 이 과정은 타 알고리즘에 대한 공격 시 존재하지 않는 과정으로 비교하기 어려우므로 단순히 메시지 값을 생성하는 밑수와 승수 쌍을 구하는데걸리는 시간만을 측정하여 비교하였다. 따라서 제안 알고리즘에 대한 공격 시 공격자는 그림에 표기된 시간 외에 g^x 후보군에 대한 검증을 수행하여야 하나 본 비교절차에서는 제외하였다.
본 장에서는 제안한 알고리즘을 기존 알고리즘과 비교하여연산의 효율성과 안전성에 대해서 평가한다.
이에 순환부분군의 개수를 확인한8191보다 작거나 같은 소수 195개를 대상으로 공격 시 안전성을 분석하였다. 분석 과정에서 비교할 알고리즘으로 이산대수의 복잡성에 기반을 둔 알고리즘과 소인수분해의 복잡성에 기반을 둔 알고리즘을 가정하고, 각 알고리즘에서 전송되는 메시지를 탈취하여 탈취한 메시지 값을 생성하는 키를 찾아내는데 소요되는 시간을 측정하였다. 단, 소인부분해의 복잡성에 기반을 둔 알고리즘의 경우 동일한 시간 복잡도를 가지는 것으로 알려진 순환공격을 수행하였다.
Diffie-Hellman 키 교환 알고리즘이 제안된 이래로 Diffie-Hellman을 기반으로 하는 다양한 방법들이 연구되었다. 안전성을 보장할 수 있는 이산대수 문제기반, 소인수분해 문제기반의 기본 알고리즘과 연구된 변형 기법을 살펴본다.
노드A는 노드B로부터 127과 170을 전달받는다. 암호화키를 풀기위해 노드B에서 전달받은 127에 지수연산의 곱 역원인 개인 곱비밀키 4를 지수연산하여 g^K를 도출한다. 도출된g^K값 442에 지수연산의 합의 역원인 복호 합비밀키 162를 지수연산하여 170과 곱하면 합비밀키의 역원 쌍 g^K·S_Pe와 g^K·S_Pd가 상쇄되고 메시지인 세션키 SK값 324가 도출된다.
같은 컴퓨팅 환경에서 각 군의 생성원들로 생성원별 동일메시지 값을 생성하는데 까지 걸린 시간을 측정하였으며, 공격하는 밑수 g는 각 소수의 절반보다 큰 임의의 완전부분군을 대상으로 하였다. 이산대수의 복잡성에 기반을 둔 알고리즘은 Equation (5)를 기준으로 밑수 g, 모듈러 p에서 지수연산 값 x를 1부터 증가시켜 공격하였고, 소인수분해의 복잡성에 기반을 둔 알고리즘은 Equation (4)의 암호화된 메시지S에 대한 공격으로, x로 반복 지수연산하여 메시지를 찾아낼때까지 걸린 연산시간을 측정하였다. 단, 제안하는 알고리즘에서는 공격 시 전송되는 메시지와 일치하는 g^x 후보군에 대한 검증을 수행하는 절차도 필요하나, 이 과정은 타 알고리즘에 대한 공격 시 존재하지 않는 과정으로 비교하기 어려우므로 단순히 메시지 값을 생성하는 밑수와 승수 쌍을 구하는데걸리는 시간만을 측정하여 비교하였다.
생성된 순환부분군의 크기를 확인하였으나, 아직 순환부분군의 크기가 실제 공격 시 어느 정도의 안전성을 향상시킬 수있는지는 알기 어렵다. 이에 순환부분군의 개수를 확인한8191보다 작거나 같은 소수 195개를 대상으로 공격 시 안전성을 분석하였다. 분석 과정에서 비교할 알고리즘으로 이산대수의 복잡성에 기반을 둔 알고리즘과 소인수분해의 복잡성에 기반을 둔 알고리즘을 가정하고, 각 알고리즘에서 전송되는 메시지를 탈취하여 탈취한 메시지 값을 생성하는 키를 찾아내는데 소요되는 시간을 측정하였다.
만약 역원이 존재하는 순환부분군을 생성하는 생성원의 개수가 적을 경우, 제안 알고리즘은 설계에서의도된 보안성의 향상을 보일 수 없다. 이에 작은 소수를 대상으로 생성원으로 만들어지는 부분군 중 순환부분군이 차지하는 비율과 개수를 분석하였다.
그러나 제안 알고리즘의 사전 키 생성 절차는 타 알고리즘에 존재하지 않으며,제안하는 알고리즘은 키 교환단계에 연산량을 줄이기 위하여사전 생성이 가능하도록 설계하였다. 이에 키 교환을 위한 사전 절차를 미리 수행한 것으로 가정하여, 키 교환 요청이 발생한 시점에서 키 교환 시 소요되는 연산부하에 대해 분석하였다. 키 교환은 사전 검증한 데이터를 기반으로 하여 Diffie-
두 개의 소수를 고르고, 두 소수를 곱하여 암호화와 복호화를위한 환으로 활용한다. 환에서 역원관계를 만들기 위해 승수의성질을 이용하여 각 소수의 오일러 토션트 함수 값을 곱한 군에서 역원을 이루는 두 개의 값을 선택하여 공개값과 비밀값으로 선정한다. 두 값은 암호화와 복호화를 위한 환에서 선택한하나의 생성원에 지수연산을 하였을 시 항등원을 생성한다.

대상 데이터

대상이 되는 소수는 1000보다 작은 소수 168개와 8191보다 작은 소수 17개를 선정하여 지수 곱의 위수를 구하여정리하였다. 순환부분군을 이루는 생성원은 각 소수의 잉여류별로 최소 21.
에서 알고리즘을 적용한다. 순환부분군을 생성할 생성원 g로 463을 선택하였다. 생성원 463으로 생성되는 순환부분군의 위수는 243으로 지수연산의 곱셉의 역원을 가지는 쌍의 곱은 243n+1을 해로 가진다.

데이터처리

노드B에서 전달받은 SR_K에 S_Pe지수연산의 곱 역원인 S_Pr을 지수연산하여 g^K값을 계산한다. 도출된 g^K에 지수연산의합의 역원인 S_Pd을 지수연산하여 MR_K와 곱하면 g^K의 S_Pe승과 g^K의 S_Pd승이 역원 연산으로 상쇄되고 메시지인 세션키SK가 도출된다.

이론/모형

Diffie-Hellman 알고리즘은 갈루아 체와 생성원을 이용하여 이산대수 문제를 구현하였다[2]. 기반을 두는 모든 가정은 유한순환군을 기반으로 하며, 그룹의 위수는 인수분해가 어려운 큰 소수를 약수로 가지도록 한다.

성능/효과

본 논문에서는 지수의 곱연산에 의한 순환부분군을 이용하여 생성원까지 비밀값으로 하는 Diffie-Hellman 키 교환 방법이 가능함을 보였다. 또한 제안하는 알고리즘의 키 교환 시필요한 연산량과, 후보 키 그룹의 크기, 공격에 대한 연산 부하량을 측정하여 효율성과 안전성을 검증하였다. 기존의 알고리즘과 비교하여 같은 크기의 키 쌍에서 크게 향상된 안전성을 보이므로, 안전성이 향상된 키 교환 환경을 제공할 수있을 것으로 기대된다.
본 논문에서는 지수의 곱연산에 의한 순환부분군을 이용하여 생성원까지 비밀값으로 하는 Diffie-Hellman 키 교환 방법이 가능함을 보였다. 또한 제안하는 알고리즘의 키 교환 시필요한 연산량과, 후보 키 그룹의 크기, 공격에 대한 연산 부하량을 측정하여 효율성과 안전성을 검증하였다.
대상이 되는 소수는 1000보다 작은 소수 168개와 8191보다 작은 소수 17개를 선정하여 지수 곱의 위수를 구하여정리하였다. 순환부분군을 이루는 생성원은 각 소수의 잉여류별로 최소 21.1%에서 최대 50%의 분포를 보였다. 평균 순환부분군은 37.
위의 평가를 통해 제안 알고리즘은 활용단계에서 연산량에큰 증가량 없이, 충분한 후보 키 그룹을 가지며, 향상된 시간복잡도를 제공할 수 있음을 확인하였다.
각 알고리즘에 공격 결과는 도식화하여 비교하기엔 현저한차이가 있어, 1000 이상의 소수 17개의 공격 결과에 대한 비교 표로 작성하였다. 이산대수 문제와 소인수분해 문제에 대한 공격은 밑수의 크기에 비례하여 약 2배의 차이를 보였으나, 제안 알고리즘은 해당 모듈러 값에 해당하는 모든 순환부분군에서 일치하는 메시지 값을 구하여 단순히 확률적으로비교하기 힘든 시간차이를 보였다.
Hellman, Nyang의 사전 역원 생성, Elgamal과 제안 알고리즘을 대상으로 동일수준의 키 연산을 기준으로 각 1000000회 연산하여, 각 10000번의 수행시간마다 표본화하여 100건의 수행시간을 대푯값으로 정리하였다. 제안한 알고리즘은 기존 알고리즘과 수행시간의 증가율을 비교해 볼 경우 Diffie-Hellman 대비 102%, 사전 역원 생성 대비 193%, Elgamal 대비 107%의 수행시간을 보였다. 이는 제안 알고리즘의 효율성이기존의 알고리즘과 큰 차이가 없음을 보여준다.
제안한 절차에 따라 생성원인 g값이 안전하지 않은 경로상에 노출되지 않으며, 안전하지 않은 경로 상으로 전송되는g의 연산 값은 모두 지수연산의 결과 값으로 최소 이산대수문제를 기반으로 하는 안전성이 보장된다.
1%에서 최대 50%의 분포를 보였다. 평균 순환부분군은 37.4%의 비율로 발생하였으나, 실제 순환부분군의 개수는 순환군의 크기가 클수록 커지므로 순환부분군의생성 비율이 21.1%로 비율이 가장 작은 소수 8171의 원소중 순환부분군을 생성하는 생성원이 1728개로 가장 큰 것을 확인할 수 있다.

후속연구

또한 제안하는 알고리즘의 키 교환 시필요한 연산량과, 후보 키 그룹의 크기, 공격에 대한 연산 부하량을 측정하여 효율성과 안전성을 검증하였다. 기존의 알고리즘과 비교하여 같은 크기의 키 쌍에서 크게 향상된 안전성을 보이므로, 안전성이 향상된 키 교환 환경을 제공할 수있을 것으로 기대된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	환에서 역원관계를 만들기 위한 방법은?	두 개의 소수를 고르고, 두 소수를 곱하여 암호화와 복호화를위한 환으로 활용한다. 환에서 역원관계를 만들기 위해 승수의성질을 이용하여 각 소수의 오일러 토션트 함수 값을 곱한 군에서 역원을 이루는 두 개의 값을 선택하여 공개값과 비밀값으로 선정한다. 두 값은 암호화와 복호화를 위한 환에서 선택한하나의 생성원에 지수연산을 하였을 시 항등원을 생성한다.
	Diffie-Hellman 알고리즘의 특징은 무엇인가?	Diffie-Hellman 알고리즘은 갈루아 체와 생성원을 이용하여 이산대수 문제를 구현하였다[2]. 기반을 두는 모든 가정은 유한순환군을 기반으로 하며, 그룹의 위수는 인수분해가 어려운 큰 소수를 약수로 가지도록 한다.
	공개키의 크기가 급격히 증가하는것을 극복하기 위한 방법은?	이에 안전한 암호화 강도를 유지하기 위해서는 요구되는 공개키의 크기가 급격히 증가한다.이를 극복하기 위하여 작은 키 길이로 충분한 안정성을 제공할 수 있는 알고리즘으로 타원곡선 암호와 같은 응용 알고리즘들이 제안되어 사용되고 있다.

참고문헌 (6)

NIST, "Recommendation for Key Management", NIST Special Publication 800-57 Part 1, Revision 4, 2016.
W. Diffie and M. Hellman, "New directions in cryptography," IEEE Transactions on Information Theory, Vol.22, Issue 6, pp.644-654, Nov. 1976.

상세보기
Dae Hun Nyang and Kyung Hee Lee, "Information Security: One Variant of Diffie-Hellman Key Exchange Protocol," The KIPS Transactions: Part C, Vol.14, No.6, pp.9-17, Oct. 2010.
A.-R. Sadeghi and M. Steiner, "Assumptions related to discrete logarithms: Why subtleties make a real difference," Advances in Cryptology - EUROCRYPT 2001 - International Conference on the Theory and Application of Cryptographic Techniques, Proceedings, 2045: 244-261, 2001.
T. Elgamal, "A public key cryptosystem and a signature scheme based on discrete logarithms," IEEE Transactions on Information Theory IEEE Trans. Inform. Theory Information Theory, IEEE Transactions on. Vol.31, Issue 4, pp.469-472, Jul. 1985.
R. L. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, Vol.21, Issue 2, pp.120-126, Feb. 1978.

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증