Design and Implementation of High-Performance and Low-Complexity Security System on Chip (SoC)

Abstract

A security system on chip (SoC) includes various security intellectual properties (IPs) such as public key cryptographic modules, symmetric key cryptographic modules, a hash function module, and a random number generator. In this thesis, I propose high-performance and low-complexity design methods for an elliptic curve cryptography (ECC) processor, a prime generator, and a true random number generator required for security SoCs. In the proposed ECC processor, the two main operations, i.e., modular inversion and modular multiplication, are designed for high speed and low complexity. The modular inversion design is based on the right-shift binary inversion algorithm with a sufficient number of adders, and its area consumption and processing speed are further improved by replacing its subtractions with additions and adding 2-bit shifts. The modular multiplication is designed based on a partial modular reduction method for NIST primes, which is a variant of the fast modular reduction for NIST primes. The iterative partial reduction of the partial products instead of a modular reduction of a full product reduces the complexity of the hardware design of modular multiplication. In addition, the sizes of the partial products are parameterized, so that the processing time and the occupied area can be configured. The proposed modular inversion and modular multiplication methods, along with modular addition/subtraction, are designed as a single integrated module in the proposed ECC processor, thereby reducing the complexity of the entire ECC processor when compared to designing them as separate modules. In the proposed hardware prime generator, two primality tests, a trial division test and a Fermat test, are designed to be carried out in parallel. Two-stage methods for finding their optimal combination and estimating their prime generation time are presented. In the first stage, the approximate optimal combination is quickly found using some parameter values. The second stage is very time-consuming, but Monte Carlo simulations are used for more accurate calculations. A new true random number generator (TRNG) based on digital logic is also proposed. Unlike most other digital TRNGs that use only one point of the ring oscillators (ROs), the proposed TRNG uses the outputs of all the elements in an RO as clock signals. This reduces the sampling interval, which increases the amount of entropy accumulated during the same amount of time. As a result, the proposed TRNG has a high bit rate, and its area is very small because of its simple structure. In addition, a built-in random test module is presented. It can examine the abnormal operation of a TRNG and the randomness of physical unclonable functions (PUFs), and it occupies very small area. All the proposed IPs were synthesized or implemented in ASIC chips or FPGA devices to verify their operation and evaluate their performance. The proposed ECC processor was synthesized using 180-nm process technology and in many FPGA devices. The experimental results show that the proposed ECC processor is very fast and has very high area efficiency. The hardware prime generators for generating 512- and 1024-bit prime numbers were implemented in an FPGA device. Their running times were almost the same as the Monte Carlo simulation results, which means that the proposed equations used in the Monte Carlo simulations are accurate. The simulations were also repeated with various parameter values to generalize the relationship between the optimal combination and the parameter values. The generalized results help to find the optimal combination for given parameter values without repeating complex simulations. The proposed TRNG was implemented in two FPGA devices, and its randomness was confirmed by the NIST random test suite. In addition, the experimental results show that the proposed TRNG is compact and fast.; 보안 SoC는 비대칭 암호, 대칭 암호, 해위 함수, 랜덤 수 생성기 등 다양한 보안 IP들을 탑재한다. 본 논문에서는 이 중 타원 곡선 암호(elliptic curve cryptography, ECC) 프로세서, 소수 생성기, 진성 난수 생성기(true random number generator, TRNG)의 고성능 및 저복잡도의 하드웨어 설계 방법을 제시한다. 제안하는 ECC 프로세서에서는 주요 두 연산인 모듈라 역과 모듈라 곱이 고속 및 저복잡도로 설계되었다. 모듈라 역은 right-shift 기반의 역 알고리즘을 기반으로, 충분한 수의 덧셈기를 이용하여 설계되었다. 기존의 뺄셈 연산이 덧셈으로 변경되고 2-bit shift를 추가하여 처리 속도와 면적을 개선하였다. 모듈라 곱은 NIST 소수에 대한 기존의 모듈라 감소(reduction)을 변형한 부분 모듈라 감소 기법을 기반으로 설계되었다. 전체 곱에 대한 모듈라 감소 대신 부분 곱에 대한 부분 모듈라 감소 방식은 모듈라 곱의 복잡도를 낮춰주게 된다. 또한 부분 곱의 크기가 파라미터화되어 처리 시간과 면적이 조절될 수 있도록 하였다. 제안하는 모듈라 역과 곱에 모듈라 덧셈/뺄쎔까지 하나의 통합 모듈로 설계함에 따라 이들을 별도의 모듈로 구현할 때보다 낮은 복잡도를 갖는 ECC 프로세서를 설계하였다. 제안하는 하드웨어 소수 생성기는 두 가지 소수 판별법인 trial division과 Fermat test를 병렬로 처리되도록 설계되었으며, 이들의 최적의 조합을 찾고 소수 생성 시간을 예측할 수 있는 방법을 제시하였다. 이 방법은 두 단계로 구성되어, 첫 번째 단계에서는 파라미터의 수치만으로 대략적인 최적의 조합을 빠르게 찾으며, 두 번째 단계에서는 Monte Carlo 시뮬레이션을 통해 시간은 오래 걸리나 더 정확한 계산이 가능하다. 새로운 디지털 기반의 진성 난수 생성기도 제시되었다. 기존의 디지털 진성 난수 생성기는 내부의 링 오실레이터의 한 지점만을 사용하나 제시하는 진성 난수 생성기는 이와 달리 링 오실레이터 내 모든 소자의 출력 값을 모두 클럭 신호로 사용한다. 이를 통해 매우 짧은 간격의 샘플링이 가능해 동일한 시간 동안 축적할 수 있는 엔트로피의 양이 증가하게 되어 빠른 속도로 난수를 생성할 수 있다. 그리고 간단한 구조로 인해 면적도 적게 소모한다. 이에 더하여, 칩 테스트 과정에서 난수 생성기의 이상 동작이나 physical unclonable function (PUF)의 랜덤성을 판별하는 데 사용될 수 있는 내장형 랜덤 판별 모듈도 함께 제시하였으며, 제시된 모듈은 매우 작은 면적을 갖는다. 제안한 보안 IP들은 모두 ASIC 또는 FPGA로 합성 또는 구현하여 동작을 검증하고 성능을 평가하였다. 제안 ECC 프로세서를 ASIC과 다수의 FPGA에서 합성하고 이를 다른 연구와 비교하였으며, 비교 결과는 제안 ECC 프로세서가 처리 속도가 매우 빠를 뿐만 아니라 면적 효율이 매우 높음을 보여준다. 소수 생성기는 512-bit과 1024-bit의 두 가지 길이에 대해 각각 FPGA로 구현하여 동작 시간을 측정하였다. 측정 결과는 Monte Carlo 시뮬레이션 결과와 거의 일치한 결과를 보여 Monte Carlo 시뮬레이션에 사용된 수식이 정확하다는 것을 증명한다. 그리고 다양한 파라미터들에 대한 시뮬레이션을 수행하여 파라미터들간의 관계를 일반화하였으며, 이는 복잡한 시뮬레이션의 반복 없이 주어진 파라미터 값에 맞는 최적을 조합을 쉽게 찾도록 도와준다. 제안한 진성 난수 생성기는 두 가지 FGPA에 구현하여 엔트로피를 측정하고 NIST random test suite을 통과하는 것을 확인하였다. 그리고 면적과 bit rate의 비교 결과, 다른 연구 결과에 비해 매우 작고 빠른 성능을 가짐을 확인할 수 있었다.