참조 테이블 기반 스칼라 곱 알고리즘에 대한 충돌 특성을 이용한 향상된 수평상관분석

Abstract

FBC(Fixed-Base Comb)는 사전계산된 참조 테이블을 활용하여 ECDSA(Elliptic Curve DigitalSignature Algorithm) 서명 생성의 핵심 연산인 스칼라 곱을 효율적으로 연산하는 방법이다. FBC는 비밀정보에의존하여 테이블을 참조하고 테이블의 값은 공개되어 있기 때문에 단일파형 부채널 공격 기법인 수평상관분석(HCA, Horizontal Correlation Analysis)에 의해 그 비밀정보가 드러날 수 있다. 그러나 HCA는 통계 분석의일종으로 하나의 스칼라 곱 파형으로부터 충분한 수의 단위 연산 파형을 얻을 수 있어야만 공격에 성공할 수 있다. ECDSA 서명 생성에 쓰이는 스칼라 곱의 경우 RSA 거듭제곱에 비해 HCA에 이용 가능한 단위 연산 파형의 수가현저히 적어 공격에 실패할 수 있다. 본 논문에서는 FBC와 같은 참조 테이블 기반 스칼라 곱에 대하여 향상된HCA를 제안한다. 제안하는 기법은 충돌 분석으로 중간값이 같은 단위 연산 파형을 식별함으로써 공격에 이용되는단위 연산 파형의 수를 증가시켜 HCA의 공격 성능을 향상시킨다. 제안하는 기법은 사용된 타원곡선 파라미터의 보안 강도가 높을수록 공격 성능이 향상하는 특징이 있다.