Earticle

암호학의 암호 생성과 해독의 곱셈 횟수는 대부분 모듈러 지수연산의 효율적 구현여부로 결정된다. 표준 모듈러 지수연산법으로는 법인 이진법이 있으며, 법이 많이 적용되고 있다. 법은 에 대해 R-L 방향으로 비트로 고정된 분할을 하고, 회 제곱과 비트값 곱셈을 수행하는 제곱-곱셉법이다. 본 논문에서는 에 대해 L-R 방향으로 가변길이로 분할하는 방법을 적용한다. 또한, 개변길이의 제곱과 곱셈 또는 나눗셈을 적용한다. 제안된 가변길이 분할법은 고정길이 분할법인 법에 비해 곱셈 수행횟수를 감소시킬 수 있었다.

The times of multiplication for encryption and decryption of cryptosystem is primarily determined by implementation efficiency of the modular exponentiation of . The most frequently used among standard modular exponentiation methods is a standard binary method, of which is most popular. The is a square-and-multiply method which partitions into fixed bits from right to left and squares times and multiplies bit values. This paper proposes a variable-length partition algorithm that partitions from left to right. The proposed algorithm has proved to reduce the multiplication frequency of the fixed-length partition method.

비대칭키 RSA의 공개키 e와 합성수 n=pq 은 알고 있고 개인키 d를 모를 때, ∅(n)=(p-1)(q-1)=n+1-(p+q) 을 구하여 d=e^{-1} (mod ∅(n))으로 개인키 d를 해독한다. 암호해독은 일반적으로 n/p=q 또는 a^{2}≡b^{2} (mod n), a=(p+q)/ 2, b=(q-p)/2 를 구하는 소인수 분해법이 널리 적용되고 있다. 그러나 아직까지도 많은 RSA 수들이 해독되지 않고 있다. 본 논문은 ∅(n)을 직접 구하는 알고리즘을 제안하였다. 제안된 알고리즘은 이산대수의 아기걸음-거인걸음법과 모듈러 지수연산의 2^{k}-ary법을 적용하였다. 이 알고리즘은 역-아기걸음과 2^{k}-ary 성인걸음법을 적용하여 기본적인 성인걸음법 수행횟수를 1/2^{k} 로 줄이고, m=⌊sqrt {n}⌋의 저장 메모리 용량도 l, a^{l} >n로 감소시켜 ∅(n)을 l회 이내로 구하였다.

When the public key e and the composite number n=pq are disclosed but not the private key d in an asymmetric-key RSA, message decryption is carried out by obtaining ∅(n)=(p-1)(q-1)=n+1-(p+q) and subsequently computing d=e^{-1} (mod ∅(n)). The most commonly used decryption algorithm is integer factorization of n/p=q or a^{2}≡b^{2} (mod n), a=(p+q)/ 2, b=(q-p)/2. But many of the RSA numbers remain unfactorable. This paper therefore applies baby-step giant-step discrete logarithm and 2^{k}-ary modular exponentiation to directly obtain ∅(n). The proposed algorithm performs a reverse baby-step and 2^{k}-ary adult-step. As a results, it reduces the execution time of basic adult-step to 1/2^{k} times and the memory m=⌊sqrt {n}⌋ to l, a^{l} >n, hence obtaining ∅(n) by executing within l times.

정보보호용 디바이스에 암호 알고리듬을 탑재하여 사용할 경우 구현상의 문제점으로 인해 전력 분 석이나 오류 주입 등과 같은 부채널 공격에 의해 내장된 비밀 키가 노출될 수 있음이 밝혀졌다. 특히, RSA와 같은 공개 키 암호 시스템에서 사용하는 멱승(exponentiation) 알고리듬은 이러한 부채널 공격 들의 목표가 되어 왔다. 본 논문에서는 최근 제안된 암호용 디바이스에 대한 수평 충돌 전력 분석 (Horizontal Collision Power Analysis) 공격의 위협 요소를 분석하고 이를 방어할 수 있는 효율적인 대응 알고리듬을 제시한다. 제안하는 멱승 알고리듬은 기존에 제시된 부채널 공격 및 오류 주입 공격 을 방어할 수 있으면서 CRT-RSA(Chinese Remainder Theorem based RSA)를 구현하는 데에도 효과 적으로 적용할 수 있다.

Recently, the power analysis and fault injection attacks have been developed to extract the secret key based on implementation flaw of a security device in which some cryptographic algorithms are implemented. Especially, these side channel attacks are focused on several exponentiation algorithms which are adopted in public key cryptosystem such as RSA. In this paper, we analyze the main threat of the horizontal collision analysis attack on security devices and propose an efficient countermeasure algorithm. The proposed exponentiation algorithm defeats most existing side channel analysis and fault attacks and can be adopted in CRT-RSA implementation.

모듈라 멱승(modular exponentiation) 연산은 암호학에서 기본적이고 중요한 연산이다. 그러나, 이는 다정도 정수(multiple precision integer)들을 다루기 때문에 그 연산시 간이 무척 많이 걸리므로 이를 단축시킬 필요가 있다. 모듈라 멱승 연산은 모듈라 곱셈(modular multiplication)의 반복으로서, 전체 연산시간을 단축시키기 위해서는 모듈라 곱셈의 수행시간을 단축시키거나, 모듈라 곱셈의 반복횟수를 줄이는 것이 필요하다. 본 논문에서는 모듈라 곱셈을 빠르게 수행하기 위한 알고리즘 두 개를 제안한다. 하나는 서로 다른 두 수의 모듈라 곱셈 알고리즘이고, 다른 하나는 모듈라 제곱을 빠르게 수행하는 알고리즘이다. 이 둘은 기존의 모듈라 곱셈 알고리즘들에 비해 각각 절반과, l/3가량의 단정도 곱셈(single-precision multiplication)만을 필요로 한다. 실제로 PC상에서 구현한 결과 각각 100%와 30%의 속도향상을 보인다.

RSA 암호 시스템에서 512비트 이상의 큰 정수 소수의 모듈라 멱승 연산이 필요하기 때문에 효율적인 암호화 및 복호화를 위해서는 모듈라 멱승 연산의 고속 처리가 필수적이다. 따라서 본 논문에서는 몫을 추정하여 모듈라 감소를 실행하고 carry-save 덧셈과 중간 곱의 크기를 제한하는 interleaved 모듈라 곱셈 및 감소 기법을 이용하여 모듈라 멱승 연산을 수행하는 고속 모듈라 멱승 연산 프로세서를 논리 자동 합성 기법을 바탕으로 하는 탑다운 선계 방식으로 VHDL을 이용하여 모델링하고 SYNOPSIS 툴을 이용하여 합성 및 검증한 후 XILINX XC4025 FPGA에 구현하여 성능을 평가 및 분석한다.

모듈러 멱승은 주어진 값 X, E, N에 대하여 $X^{E}$ mod N으로 정의 된다. 모듈러 멱승은 대부분의 공개키 암호시스템과 전자서명에 사용되므로, 이 연산을 빠르게 수행하는 문제는 암호학 분야에서 중요하게 연구되고 있다. 본 논문에서는 모듈러 멱승을 효율적으로 계산하기 위하여, 멱승 계산을 위한 일반화된 그래프 모델을 제시하였다. 이 모델은 기존의 방법들을 대부분 포용할 수 있으며, 특히 새로운 방법을 개발하는데 유용할 것이다. 이 모델의 장점을 정당화하기 위하여 기존 알고리즘 중 가장 성능이 좋은 VLNW(Variable Length Nonzero Window)방법과 실험을 통하여 비교하였으며, 확장성이 높음을 확인하였다.

모듈러 멱승은 양수 x, E, N에 대하여 $x^Emod$ N로 정의된다. 모듈러 멱승 연산은 대부분의 공개키 암호화 알고리즘과 전자서명 프로토콜에서 핵심적인 연산으로 사용되고 있으므로, 그 효율성은 암호 프로토콜의 성능에 직접적인 영향을 미친다. 따라서 모듈러 멱승 연산에 필요한 곱셈 수를 감소시키기 위하여, 슬라이딩 윈도우를 적용한 CLNW 방법이나 VLNW 방법이 가장 널리 사용되고 있다. 본 논문에서는 조합론(combinatorics)에서 많이 응용되는 그래프 모델을 모듈러 멱승 연산에 적용할 수 있음을 보이고, 일반화된 그래프 모델을 통하여 VLNW 방법보다 더 적은 곱셈 수로 모듈러 멱승을 수행하는 방법을 설명한다. 본 논문이 제안하는 방법은 전체 곱셈 수를 감소시키는 새로운 블록들을 일반화된 그래프 모델의 초기 블록 테이블에 추가할 수 있는 초기 블록 테이블의 두 가지 확장 방법들로써, 접두사 블록의 확장과 덧셈 사슬 블록의 확장이다. 이 방법들은 새로운 블록을 초기 블록 테이블에 추가하기 위해 필요한 곱셈의 수와 추가한 뒤의 전체 곱셈 수를 비교하면서 초기 블록 테이블을 제한적으로 확장하므로, 지수 E에 non-zero bit가 많이 나타날수록 VLNW 방법에 비해 좋은 성능을 보이며 이는 실험을 통하여 검증하였다.

본 논문에서는 right-to-left 형태의 멱승 연산에 적합한 고속 모듈라 감소 알고리듬을 제안하고 이를 여러 멱승 방식에 적용했을 경우의 계산 속도 및 메모리 사용효율을 기존의 방식들과 비교하였다. 분석 결과, 기존의 방식보다 고속으로 멱승을 수행할 수 있고 m-ary 방식이나 window 방식에서는 사용 메모리를 줄일 수 있다.

본 논문에서는 고속 멱승을 위한 모듈라 곱셈기를 시스토릭 어레이로 설계한다. Montgomery 알고리듬 및 시스토릭 어레이 구조를 분석하고 공통 피승수 곱셈 개념을 사용한 변형된 Montgomery 알고리듬에 대해 시스토릭 어레이 곱셈기를 설계한다. 제안 곱셈기는 각 처리기 내부 연산을 병렬화 할 수 있고 연산 자체도 간단화 할 수 있어 시스토릭 어레이 하드웨어 구현에 유리하며 기존의 곱셈기를 사용하는 것보다 멱승 전체의 계산을 약 0.4배내지 0.6배로 감소시킬 수 있다.