효율적인 키-난수화를 사용한 차분 전력 분석 공격에 대응하는 타원곡선 위의 스칼라 곱셈 방법 A Method for Scalar Multiplication on Elliptic Curves against Differential Power Analysis using Efficient Key-Randomization원문보기
사물인터넷 시대가 되면서 다양한 디바이스가 유·무선으로 연결되고 있다. 이에 따른 일상생활의 편리성 향상과 함께 사생활 침해, 정보유출, 서비스 거부 등의 보안 문제가 증가하고 있다. 공개키 암호 시스템의 하나인 타원곡선 암호 시스템 ECC는 사용하는 키의 크기가 RSA 알고리즘보다 상대적으로 작아 제약적인 환경의 디바이스에 널리 사용되고 있다. 그러나 제약적인 환경의 디바이스에 적용된 ECC의 비밀 키는 스칼라 곱셈 연산을 수행하는 과정에서 전력 분석 공격법에 의해 노출될 수 있다. 본 논문에서는 SECG 표준 타원곡선파라미터의 스칼라 곱셈 방법에 대해 차분 전력 분석에 대응하고 연산의 효율성을 증가시키는 방법을 알아본다. 제안하는 방법은 비밀 키에 타원곡선 위수의 난수 배를 더하여 차분 전력 분석에 대응하는 Coron의 방법을 사용한다. 연산의 효율성을 증가시키기 위해 SECG 표준 파라미터의 위수 n을 상대적으로 작은 상수 c로 n=2l±c로 표현하고, 2lP =∓cP인 성질을 이용한다. 임의의 난수를 사용한 Coron의 키-난수화 방법은 스칼라 곱셈 수행을 2l번 하는데, 본 논문에서 제안하는 방법은 위수 성질을 이용하면 스칼라 곱셈 수행을 약 (3/2)l번 수행하게 되어 25% 정도 연산의 효율성이 향상된다.
사물인터넷 시대가 되면서 다양한 디바이스가 유·무선으로 연결되고 있다. 이에 따른 일상생활의 편리성 향상과 함께 사생활 침해, 정보유출, 서비스 거부 등의 보안 문제가 증가하고 있다. 공개키 암호 시스템의 하나인 타원곡선 암호 시스템 ECC는 사용하는 키의 크기가 RSA 알고리즘보다 상대적으로 작아 제약적인 환경의 디바이스에 널리 사용되고 있다. 그러나 제약적인 환경의 디바이스에 적용된 ECC의 비밀 키는 스칼라 곱셈 연산을 수행하는 과정에서 전력 분석 공격법에 의해 노출될 수 있다. 본 논문에서는 SECG 표준 타원곡선 파라미터의 스칼라 곱셈 방법에 대해 차분 전력 분석에 대응하고 연산의 효율성을 증가시키는 방법을 알아본다. 제안하는 방법은 비밀 키에 타원곡선 위수의 난수 배를 더하여 차분 전력 분석에 대응하는 Coron의 방법을 사용한다. 연산의 효율성을 증가시키기 위해 SECG 표준 파라미터의 위수 n을 상대적으로 작은 상수 c로 n=2l±c로 표현하고, 2lP =∓cP인 성질을 이용한다. 임의의 난수를 사용한 Coron의 키-난수화 방법은 스칼라 곱셈 수행을 2l번 하는데, 본 논문에서 제안하는 방법은 위수 성질을 이용하면 스칼라 곱셈 수행을 약 (3/2)l번 수행하게 되어 25% 정도 연산의 효율성이 향상된다.
As a becoming era of Internet-of-Things, various devices are connected via wire or wirless networks. Although every day life is more convenient, security problems are also increasing such as privacy, information leak, denial of services. Since ECC, a kind of public key cryptosystem, has a smaller ke...
As a becoming era of Internet-of-Things, various devices are connected via wire or wirless networks. Although every day life is more convenient, security problems are also increasing such as privacy, information leak, denial of services. Since ECC, a kind of public key cryptosystem, has a smaller key size compared to RSA, it is widely used for environmentally constrained devices. The key of ECC in constrained devices can be exposed to power analysis attacks during scalar multiplication operation. In this paper, a key-randomization method is suggested for scalar multiplication on SECG parameters. It is against differential power analysis and has operational efficiency. In order to increase of operational efficiency, the proposed method uses the property 2lP=∓cP where the constant c is small compared to the order n of SECG parameters and n=2l±c. The number of operation for the Coron's key-randomization scalar multiplication algorithm is 21, but the number of operation for the proposed method in this paper is (3/2)l. It has efficiency about 25% compared to the Coron's method using full random numbers.
As a becoming era of Internet-of-Things, various devices are connected via wire or wirless networks. Although every day life is more convenient, security problems are also increasing such as privacy, information leak, denial of services. Since ECC, a kind of public key cryptosystem, has a smaller key size compared to RSA, it is widely used for environmentally constrained devices. The key of ECC in constrained devices can be exposed to power analysis attacks during scalar multiplication operation. In this paper, a key-randomization method is suggested for scalar multiplication on SECG parameters. It is against differential power analysis and has operational efficiency. In order to increase of operational efficiency, the proposed method uses the property 2lP=∓cP where the constant c is small compared to the order n of SECG parameters and n=2l±c. The number of operation for the Coron's key-randomization scalar multiplication algorithm is 21, but the number of operation for the proposed method in this paper is (3/2)l. It has efficiency about 25% compared to the Coron's method using full random numbers.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 타원곡선 알고리즘의 스칼라 곱셈에 대한 구조와 전력 분석 공격법에 대해 알아보았다. 2장에서는 Coron이 제안한 스칼라 곱셈 알고리즘을 전력 분석 공격법에 따라 분석해 보았다.
본 논문에서는 타원곡선 알고리즘의 차분 전력 분석법에 대응하기 위해 제안된 Coron의 방법에 대해 알아본다. 또한 SECG 표준 타원곡선 파라미터에 Coron의 방법을 적용할 때 취약점이 알려져 있는데, 이를 개선하기 위해 키-난수화 방법을 사용한다.
제안 방법
그러나 효율성 증대를 위해 20비트 난수를 사용하는 경우, SECG 파라미터와 같이 위수의 값에 0의 열 또는 1의 열이 많은 경우에는 차분 전력 분석 공격에 취약하 다. [표 2]에서 보는 바와 같이 본 논문에서 제안하는 방법은 키 비트를 모두 난수화시켜 SECG 파라미터에 대해서도 차분 전력 분석 공격을 막고 있다. 임의 난수 를 사용한 Coron의 키-난수화 방법은 연산 횟수가 키의 길이가 l비트 일 때, 덧셈 2l번과 두 배 2l번의 연산을 수행하지만, 제안 방법은 위수의 상수 c가 t비트 일때, 덧셈 1+t번과 두 배 1+t번의 연산만을 수행한다.
Coron은 논문 [10]에서 차분 전력 분석 공격법을 막기 위해 비밀 키를 타원곡선 위수의 배수로 난수화시키 는 방법을 제안하였다. 계산의 효율성을 위해 난수의 크기를 20비트 정도로 제한하는 것을 권고하였다. 그러나 3장 1절에서 살펴보았듯이 SECG에서 권고하는 타원곡선 파라미터들 중 일부에 대해서는 키 비트가 완전히 난수화되지 않는 경우가 발생하여 차분 전력 분석 공격이 가능하게 된다.
본 논문에서는 이러한 문제점을 극복하기 위해 비밀키 k와 같은 크기의 l비트 난수 r을 사용하도록 한다. 이 경우 k+rn는 2l비트가 되므로 알고리즘 2를 사용할 때, (k+rn)P 계산에 2l번의 For문이 실행된다.
임의 난수 를 사용한 Coron의 키-난수화 방법은 연산 횟수가 키의 길이가 l비트 일 때, 덧셈 2l번과 두 배 2l번의 연산을 수행하지만, 제안 방법은 위수의 상수 c가 t비트 일때, 덧셈 1+t번과 두 배 1+t번의 연산만을 수행한다.
이론/모형
본 논문에서는 타원곡선 알고리즘의 스칼라 곱셈에 대한 구조와 전력 분석 공격법에 대해 알아보았다. 2장에서는 Coron이 제안한 스칼라 곱셈 알고리즘을 전력 분석 공격법에 따라 분석해 보았다. 3장에서 Coron이 제안한 키-난수화 방법에 타원곡선 군의 위수 특징을 이용하여 난수화 된 키의 비트 크기를 줄여 연산의 효율성을 얻는 방법을 살펴보았다.
성능/효과
본 논문에서 제안하는 타원곡선 상의 모듈러 감산을 이용한 키-난수화 스칼라 곱셈 방법은 단순 전력 분석과 차분 전력 분석에 강인하다. 또한 SECG 파라미터에 대해 본 논문에서 제안하는 방법이 임의의 난수를 사용한 Coron의 방법보다 약 25% 정도 효율적이다.
본 논문에서 제안하는 타원곡선 상의 모듈러 감산을 이용한 키-난수화 스칼라 곱셈 방법은 단순 전력 분석과 차분 전력 분석에 강인하다. 또한 SECG 파라미터에 대해 본 논문에서 제안하는 방법이 임의의 난수를 사용한 Coron의 방법보다 약 25% 정도 효율적이다.
Coron은 이 사실을 사용하여 여러 개의 타원곡선점 입력에 대한 소비전력 파형을 수집한 후 키 비트의 추측에 따라 소비전력들을 분류하였다. 이들의 평균값 분포를 이용하여 키 비트의 추측이 올바른지를 판단하여 비밀 키비트를 찾아내는 방법을 제안하여 알고리즘 2가 차분 전력 분석 공격에 취약함을 보였다.
SECG의 파라 미터에 대해 제안하는 방법이 Coron의 방법 대비 연산 횟수가 약 75% 정도를 차지하고 있다. 즉, 제안하는 방법이 Coron의 방법보다 전체 계산이 약 25% 정도 효율적이다.
후속연구
본 논문에서 제안하는 스칼라 곱셈 방법은 타원곡선을 이용한 전자서명, 키 교환 등을 구현하는 핵심요소로 사물인터넷의 디바이스 인증, 핀테크 분야의 전자서명, 디지털 콘텐츠 보호를 위한 키 교환 등에 활용될 수있다. 향후, 연산의 효율성을 좀 더 줄이는 방법에 대한 연구와 Coron의 방법 이외의 다른 전력 분석 대응법과의 연산 효율성 비교에 대한 연구가 필요하다.
본 논문에서 제안하는 스칼라 곱셈 방법은 타원곡선을 이용한 전자서명, 키 교환 등을 구현하는 핵심요소로 사물인터넷의 디바이스 인증, 핀테크 분야의 전자서명, 디지털 콘텐츠 보호를 위한 키 교환 등에 활용될 수있다. 향후, 연산의 효율성을 좀 더 줄이는 방법에 대한 연구와 Coron의 방법 이외의 다른 전력 분석 대응법과의 연산 효율성 비교에 대한 연구가 필요하다.
질의응답
핵심어
질문
논문에서 추출한 답변
타원곡선 알고리즘의 장점은?
이 안내서에서 타원곡선 알고리즘은 키 관리/분배 기법 제공, 전자 서명 기반의 부인 방지 기법, 인증서 기반의 SSL(Secure Socket Layer) 등을 이용한 안전한 채널 통신 제공 등에 사용되고 있다[1]. 타원곡선 알고리즘은 공개키 알고리즘으로 소인수 분해의 어려움에 근거한 RSA에 비해 키의 크기가 작아 실행 속도가 빠르고 전송 데이터 양이 작은 장점이 있다. 이러한 장점으로 인해 타원곡선 알고리즘은 6LoWPAN과 CoAP 프로토콜에서 사용되며, 비트코인에도 사용되고 있다[5][6].
ECC의 특징은?
이에 따른 일상생활의 편리성 향상과 함께 사생활 침해, 정보유출, 서비스 거부 등의 보안 문제가 증가하고 있다. 공개키 암호 시스템의 하나인 타원곡선 암호 시스템 ECC는 사용하는 키의 크기가 RSA 알고리즘보다 상대적으로 작아 제약적인 환경의 디바이스에 널리 사용되고 있다. 그러나 제약적인 환경의 디바이스에 적용된 ECC의 비밀 키는 스칼라 곱셈 연산을 수행하는 과정에서 전력 분석 공격법에 의해 노출될 수 있다.
키-난수화 방법을 사용할 때 연산 효율성을 향상시키는 방법은?
또한 SECG 표준 타원곡선 파라미터에 Coron의 방법을 적용할 때 취약점이 알려져 있는데, 이를 개선하기 위해 키-난수화 방법을 사용한다. 이때 연산의 효율성이 떨어지게 되는데 타원곡선 위수의 성질을 이용 하여 연산 효율성을 향상시킨다.본 논문의 구성은 다음과 같다.
참고문헌 (21)
미래창조과학부, 한국인터넷진흥원, 사물인터넷(IoT) 환경에서의 암호.인증기술 이용 안내서, p.14, 2017.
안철수연구소, "IoT 시스템관리, 가장 큰 문제와 취약점은 무엇일까?," 월간 안 3월호, pp.26-27, 2019.
최동진, "5G 시대의 차세대 IoT 보안," 주간기술동향 1914호, pp.2-16, 2019.
행정안전부, 한국정보화진흥원, 정부사물인터넷 도입가이드라인, pp.19-22, 2019.
Andreas M. Antonopoulos, Mastering Bitcoin, O'Reilly, pp.65-81, 2014.
E. Brier and M. Joye, "Weirstrass elliptic curves and side-channel attacks," PKC 2002, LNCS 2274, pp.335-345, 2002.
M. Ciet and M. Joye, "(Virtually) Free Randomization Techniques for Elliptic Curve Cryptography," ICICS 2003, LNCS 2836, pp.348-359, 2003.
C. Clavier and M. Joye, "Universal exponentiation algorithm," CHES 2001, LNCS 2162, pp.300-308, 2001.
J. S. Coron, "Resistance against differential power analysis for elliptic curve cryptosystems," CHES'99, LNCS 1717, pp.292-302, 1999.
P. A. Fouque and F. Valette, "The doubling attack why upwards is better than downwards," CHES 2003, LNCS 2779, pp.269-280, 2003.
K. Gandolfi, C. Mourtel, and F. Olivier, "Electromagnetic analysis: Concrete results," CHES 2001, LNCS 2162, pp.251-261, 2001.
L. Goubin, "A refined power-analysis attack on elliptic curve cryptosystem," PKC 2003, LNCS 2567, pp.199-211, 2002.
R. R. Goundar, M. Joye, A. Miyaji, M. Rivain, and A. Venelli, "Scalar multiplication on Weierstass elliptic curves from Co-Z arithmetic," J. of Crytographic Engineering, Vol.1, No.2, pp.161-176, 2011.
D. Gullasch, E. Bangerter, and S. Krenn, "Cache Games - Bringing Access Based Cache Attacks on AES to Practice," IEEE Symposium on Security and Privacy, pp.490-505, 2011.
J. Ha, J. Park, S. Moon, and S. Yen, "Provably secure countermeasure resistant to several types of power attack for ECC," WISA 2007, LNCS 4867, pp.333-344, 2007.
D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, pp.75-97, 2004.
M. Joye, A. K. Lenstra, and J. J. Quisquater, "Chinese remaindering cryptosystems in the presence of faults," J. Cryptol., Vol.12, No.4, pp.241-245, 1999.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.