On the Method of Inverse Modulo 2k for PKC Implementations

Abstract

오늘날 공개키 암호 시스템은 정보 보호 프로토콜을 구현함에 있어서 부인방지 기능과 같은 필수적인 기능을 제공한다. 그러나 공개키 암호 시스템은 비밀키 시스템에 비해서 더 긴 비밀정보의 길이를 갖고 있을 뿐만 아니라, 암호화 및 복호화를 수행하는데 있어 더 많은 연산량을 필요로 한다는 문제를 갖고 있다. 일반적으로 공개키 암호 시스템은 모듈러 덧셈, 뺄셈, 곱셈, 및 역원 연산을 일정 순서에 따라 수행하게 된다. 이러한 연산을 효율적으로 수행하기 위해서 Montgomery 모듈러 곱셈이나 Jebelean 의 정확한 나눗셈 기법과 같은 것들이 사용된 바 있다. 그 중에서 모듈러 역원은 입력의 크기가 클 때 많은 시간을 소모하고, 계산이 복잡한 과정으로 잘 알려져 있다. Arazi 와 Qi 는 재귀적인 방식으로 역원을 구할 수 있도록 하나의 변수를 반으로 분할하여 2 의 거듭 제곱 형태의 모듈러스를 갖는 역원 연산을 효율적으로 수행할 수 있는 알고리즘을 제안한 바 있다. 이 논문에서는 Arazi 와 Qi 의 방법을 변경하여 특별한 경우에 더욱 효율적인 연산이 수행한 단순화된 알고리즘을 제안한다. 연산에 사용되는 숫자들이 특별한 구조를 갖는 경우 연산 알고리즘은 보다 단순화될 수 있고, 그 결과 재귀적 과정이 제거되어 고속으로 효율적인 연산을 수행할 수 있다는 사실을 밝혀 내었다. 시뮬레이션 결과에 따르면 새롭게 제안한 알고리즘은 2 의 거듭 제곱 형태의 모듈러스를 갖는 역원 연산을 기존의 Arazi 와 Qi 가 제안한 방식뿐만 아니라, Dusse 및 Kaliski 의 연산 법, 직접적인 연산 법, 그리고 확장된 유클리드 알고리즘 보다 더 빠르게 연산할 수 있다는 사실을 확인할 수가 있었다. 그러나 이러한 고속의 성능은 입력되는 숫자가 특별한 구조를 취한 경우에만 달성될 수 있다는 제약을 갖는다. 하지만 암호학적 연산의 경우에는 이 논문에서 가정한 특별한 구조를 갖는 숫자를 이용하는 경우가 많이 있기 때문에, 이 논문에 따르면 그러한 연산의 경우 보다 효율적인 고속 연산이 가능한 것을 확인할 수가 있다.|Public key crypto-systems (PKCs) offer powerful and convenient methods for implementation of information security, since we do not need to disseminate a common secret key before starting communication. However, PKCs require more computational resources and also need to have a key of larger size for the system to be as secure as secret key crypto-systems. Most PKCs are based on modular operations such as modular addition, subtraction, multiplication and inversion. Among them, modular inversion is a relatively more time consuming and computationally complicated process, especially when the size of the input is large. A special case is inverse modulo power of 2 which is needed in the algorithms required for PKC implementations, such as Montgomery modular multiplication and Jebelean’s exact division method. Arazi and Qi have proposed an efficient algorithm for calculation of inversion modulo power of 2, which recursively divides a number into halves in order to find the required inverse. This thesis gives a detail description of the method as well as proposes a simplification. A special structure of numbers is introduced, which helps to eliminate the recursion process, hence making the algorithm simpler, execute faster and computationally more efficient. It shows that the calculation of inverse modulo a power of 2 can be done faster than the method proposed by Arazi and Qi, as well as faster than popular methods such as Dusse and Kaliski’s method, straight forward method and extended Euclidean method. However, in their binary representation the input numbers should confirm to a special structure