[논문]최신 준안정성 및 발진기 기반 진 난수 발생기 비교

신화수; 유호영

doi:10.7471/ikeee.2020.24.2.543

초록
AI-Helper

산업의 발전과 인터넷의 발전으로 보안의 중요성이 증가하면서 암호화에 필수적인 요소인 암호화 키의 생성에 사용되는 난수 발생기의 연구가 활발하게 이루어지고 있다. 외부 공격으로부터 안전한 고성능의 암호화 키를 생성하기 위해서는 예측하기 어려운 품질 좋은 난수 발생기가 필수적이다. 일반적으로 사용되는 의사 난수 발생기는 충분한 성능의 난수를 발생하기 위해서 많은 양의 하드웨어 리소스가 요구됨에도 외부에서 암호화 키를 외부에서 알아낼 가능성이 존재한다. 그러므로, 다양한 잡음을 통해 난수를 발생시켜 외부에서 예측 불가능하며 품질 좋은 진 난수 발생기에 대한 요구가 증가하고 있다. 본 논문은 진 난수 생성기술로 대표적인 준안정성 및 발진기를 통한 진 난수 발생기의 최신구조가 랜덤소스를 생성하는 방식을 조사 및 비교한다. 또한, NIST에서 제공하는 난수 검증용 도구인 SP 800-22 테스트를 통해 발진기 기반 진 난수 발생기 성능을 검증한 자료를 분석한다.

Abstract ▼ AI-Helper

As the importance of security increases in various fields, research on a random number generator (RNG) used for generating an encryption key, has been actively conducted. A high-quality RNG is essential to generate a high-performance encryption key, but the initial pseudo-random number generator (PR...

As the importance of security increases in various fields, research on a random number generator (RNG) used for generating an encryption key, has been actively conducted. A high-quality RNG is essential to generate a high-performance encryption key, but the initial pseudo-random number generator (PRNG) has the possibility of predicting the encryption key from the outside even though a large amount of hardware resources are required to generate a sufficiently high-performance random number. Therefore, the demand of high-quality true random number generator (TRNG) generating random number through various noises is increasing. This paper examines and compares the representative TRNG methods based on metastable-based and ring-oscillator-based TRNGs. We compare the methods how the random sources are generated in each TRNG and evaluate its performances using NIST SP 800-22 tests.

주제어

표/그림 (10)

그림 Fig. 1. Representative structure of TRNGs. 그림 1. 진 난수 발생기의 대표구조
그림 Fig. 2. Metastable voltage condition. 그림 2. 준 안정 상태의 전압
그림 Fig. 3. Metastability-based TRNG[2]. 그림 3. 준안정성 기반 진 난수 발생기[2]
그림 Fig. 4. Metastability-based TRNG timing diagram[2]. 그림 4. 준안정성 기반 진 난수 발생기 타이밍도[2]
그림 Fig. 5. (a) Beat frequency detection TRNG, (b) BFD TRNG output diagram[5]. 그림 5. (a) BFD TRNG의 구조, (b) BFD TRNG 출력[5]
그림 Fig. 6. Multi-stage BFD TRNG[7]. 그림 6. 다단 BFD TRNG 구조[7]
그림 Fig. 7. DCM based BFD TRNG. 그림 7. DCM 기반의 BFD TRNG 구조
그림 Fig. 8. 4-input LUT based Programmable Delay Inverter[9]. 그림 8. 4-입력 LUT 기반의 지연 조절이 가능한 인버터 구조[9]
그림 Fig. 9. PDL-based TRNG[9]. 그림 9. PDL 기반의 진 난수 발생기 구조[9]
표 Table 1. NIST SP 800-22 Test Suite result comparison of Ring Oscillator-based TRNGs. 표 1. 발진기 기반 진 난수 발생기의 SP 800-22 테스트 결과 비교

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

진 난수 발생기는 그림 1에서 보이는 바와 같이 각 랜덤소스를 구현하기 위한 하드웨어, 출력된 랜덤 소스를 난수로 변환하기 위한 샘플링, 그리고 의미 있는 난수 생성을 위한 후 처리 하드웨어[10-11]로 구성되기 때문에 상대적으로 적은 하드웨어 오버헤드를 사용하여 구현할 수 있다[1-9]. 본 논문에서는 다양한 방식으로 연구 및 개발되고 있으며 구현 난이도와 성능 측면에서 선호되어 일반적으로 많이 사용되는 준안정성 기반[2-4] 및 발진기 기반[5-9]의 진 난수 발생기를 연구한 논문을 분석한다.
본 논문에서는 준안정성 기반의 진 난수 발생기와 발진기 기반의 진 난수 발생기에 대하여 연구를 진행한 논문 4편을 분석하였다. 일반적인 진 난수 발생기는 랜덤소스를 발생시키는 모듈, 랜덤소스를 난수로 샘플링하는 모듈, 그리고 샘플링 된 난수의 질을 높이기 위한 후처리 모듈로 구성이 되며, 그 중에서도 샘플링은 DFF, 후처리는 폰 노이만 방식[10, 11]을 이용하는 경우가 일반적이다.

제안 방법

난수 생성기술을 통해 암호화키를 생성하고, 생성된 암호화 키의 성능을 높이기 위해서는 품질 좋은 난수의 생성이 필요하다. 난수 생성기술은 의사 난수 생성기술과 진 난수 생성기술로 나뉘는데, 초기의 암호화 키 생성은 비교적 구현이 단순하고 쉬운 의사 난수 생성기술을 이용했다. 그러나 의사 난수 생성기술은 출력의 예측이가능하므로 외부에서 암호화 키를 알아내어 보안문제를 일으킬 염려가 있으므로, 최근 진 난수 발생기의 연구 및 개발이 활발하게 이루어지고 있다.
생성된 난수는 폰 노이만 후처리 모듈[10,11]을 통해 후처리 과정을 거치며, 이 후처리 과정에서는 출력 시퀀스를 감소시키는 것이 아닌 기존의 출력 시퀀스에 후처리를 통해 생성된 값을 추가하는 방식으로 동작하여 전체 시퀀스가 증가하도록 설계되었다. 또한, 이 논문에서는 그림 6에서 보이는 바와 같이 동일 회로를 여러 단으로 중첩하는 구조를 제안하고 있으며, 다단 난수 발생기는 발진기를 공유하는 서로 다른 인버터의 출력을 각각 다른 샘플링 모듈로 입력하여 그중 한 단의 출력과 전체를 연산한 출력을 MUX를 통해 선택적으로 사용하는 구조를 갖는다.
여기에 클록 지터가 발생하면서 100 사이클보다 길거나 짧은 길이의 펄스로 출력이 변화하게 되고, 카운터를 통해 이 출력 펄스의 길이를 세어 난수를 생성하게 된다. 생성된 난수는 폰 노이만 후처리 모듈[10,11]을 통해 후처리 과정을 거치며, 이 후처리 과정에서는 출력 시퀀스를 감소시키는 것이 아닌 기존의 출력 시퀀스에 후처리를 통해 생성된 값을 추가하는 방식으로 동작하여 전체 시퀀스가 증가하도록 설계되었다. 또한, 이 논문에서는 그림 6에서 보이는 바와 같이 동일 회로를 여러 단으로 중첩하는 구조를 제안하고 있으며, 다단 난수 발생기는 발진기를 공유하는 서로 다른 인버터의 출력을 각각 다른 샘플링 모듈로 입력하여 그중 한 단의 출력과 전체를 연산한 출력을 MUX를 통해 선택적으로 사용하는 구조를 갖는다.
[2]는 준안정성 기반의 진 난수 발생기에 대한 구조를 제안하고 있다. 이 논문에서는 그림 3에서 보이는 것과 같이 MUX를 이용하여 인버터의 입력이 클록에 맞추어 변화되면서 Metastability(MS) 모드와 Generation(Gener.) 모드가 반복되며 생기는 변화가 진 난수 발생기의 랜덤소스로 사용된다. MS모드는 준 안정 모드를 의미하며, 그림 4에서 보이는 바와 같이 클록이 low일 때, 각 단의 인버터 출력이 MUX에 의해 입력으로 피드백되어 각 인버터가 준 안정 상태가 된다.
PDL은 Xilinx 사의 FPGA 보드 내부에서 사용되는 4-input 또는 6-input LUT[3]을 이용하여 LUT의 내부에서 데이터의 이동 경로를 선택적으로 사용하여 경로의 차이에 따른 지연시간의 차이를 임의로 조절하는 것이다. 이 논문에서는 그림 8에서 볼 수 있듯이 인버터를 PDL 개념을 활용하여 Programmable Delay Inverter를 구현하여 발진기를 구성하였다. Programmable Delay Inverter는 그림 8과 같이 4-input LUT[3]을 구성하는 MUX tree의 각 MUX 입력을 select 신호와 반대되는 값으로 고정하여 반전 값을 출력할 수 있도록 하고, select 신호 A1을 inverter의 입력으로 설정하여 한 개의 4-input LUT가 한 개의 inverter의 역할을 하도록 구성된다.
[7]은 2개의 서로 다른 발진기를 랜덤 소스로 사용하여 ASIC으로 구현한 발진기 기반 진 난수 발생기에 대한 논문이다. 이 논문에서는 두 개의 발진기를 구현할 때, 두 발진기의 주파수를 약 1% 수준으로 미세하게 차이 나도록 하고, 이 차이를 beat frequency로 정의한다. 이렇게 구현한 두 발진기의 출력은 그림 5-a에서 보이는 바와 같이 샘플링을 위한 DFF의 입력과 클록 신호로 각각 연결되며, 두 발진기 중에서 느린 발진기의 출력이 DFF의 클록 신호로 입력되어 샘플링된다.
입력으로 사용된 A1을 제외한 나머지 3개의 select 신호는 LUT의 출력이 생성되기 위해 거치는 경로를 선택하는 신호로 사용되어 각 경로의 지연시간 차이를 이용하여 inverter의 내부지연시간을 조절할 수 있도록 한다. 이와 같은 방식으로 만들어진 인버터를 그림 9과 같이 체인 형태로 홀수개를 연결하는 방법으로 다수의 발진기를 생성하고, 각 발진기의 인버터에 관하여 입력 및 지연시간 조절에 사용되는 MUX의 select 신호를 컨트롤 로직을 통해 선택적으로 입력할 수 있도록 구성하여 진 난수 발생기의 랜덤소스를 구현한다. 구현된 랜덤소스의 각 발진기에서 생성된 랜덤 비트는 같은 샘플링 클록에 의해 DFF을 통해 샘플링되고, 샘플링된 데이터는 XOR tree를 통한 연산과정을 거쳐 다시 한번 동일한 샘플링 클록으로 DFF에서 샘플링되어 난수로 출력된다.

대상 데이터

표 1은 본 논문에서 소개한 발진기 기반 진 난수 발생기의 성능을 NIST에서 제공하는 SP 800-22 테스트[12]를 통해 검증한 결과를 나타내며, 다양한 데이터에 대해 비교한 논문의 경우 한 개의 데이터만을 선별하여 작성하였다. NIST SP 800-22 테스트[12]는 검증하고자 하는 난수 발생기의 출력 시퀀스에 대하여 표 1에 표시한 15가지 항목으로 검증하여 난수 발생기의 난수성을 판단하는 지표로 사용된다.

후속연구

그러므로, 랜덤소스의 생성 방법이 진 난수 발생기의 동작과 성능을 결정짓게 되며, 생성된 난수의 질을 높이기 위해 랜덤소스 모듈의 하드웨어 리소스가 굉장히 커지는 경우도 존재한다. 향후 진 난수 발생기 연구는 기존의 발진기나 준안정성을 위해 사용되는 모듈과 동일한 기능을 더 소량의 하드웨어 리소스로 구현하기 위한 방식을 연구 및 개발하는 방향으로 진행할 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	암호화 키를 생성하기 위해 사용하는 기술은 무엇인가?	이를 위해 다양한 보안 솔루션이 개발되었으며, 대표적으로 암호화 키를 이용한 암호화 방식이 폭넓게 사용된다. 암호화 키를 이용한 암호화 방식은 암호화 키를 외부에서 유추할 수 없도록 생성하는 것이 핵심이며, 이 암호화 키를 생성하기 위해 일반적으로 사용되는 기술이 난수 생성기술이다. 난수 생성기술을 통해 암호화키를 생성하고, 생성된 암호화 키의 성능을 높이기 위해서는 품질 좋은 난수의 생성이 필요하다.
	난수 생성기술은 어떻게 나누어지는가?	난수 생성기술을 통해 암호화키를 생성하고, 생성된 암호화 키의 성능을 높이기 위해서는 품질 좋은 난수의 생성이 필요하다. 난수 생성기술은 의사 난수 생성기술과 진 난수 생성기술로 나뉘는데, 초기의 암호화 키 생성은 비교적 구현이 단순하고 쉬운 의사 난수 생성기술을 이용했다. 그러나 의사 난수 생성기술은 출력의 예측이가능하므로 외부에서 암호화 키를 알아내어 보안문제를 일으킬 염려가 있으므로, 최근 진 난수 발생기의 연구 및 개발이 활발하게 이루어지고 있다.
	진 난수 생성기술이 상대적으로 적은 하드웨어 오버헤드를 사용할 수 있는 이유는 무엇인가?	일반적으로 진 난수 생성기술은 PLL(PhaseLocked Loop) 방식, Self-Timed Ring 방식, Metastability(준안정성) 방식[2-4], 그리고 Ring Oscillator (발진기) 방식[5-9]으로 크게 4가지 방식을 통해 랜덤소스를 생성한다[1]. 진 난수 발생기는 그림 1에서 보이는 바와 같이 각 랜덤소스를 구현하기 위한 하드웨어, 출력된 랜덤 소스를 난수로 변환하기 위한 샘플링, 그리고 의미 있는 난수 생성을 위한 후 처리 하드웨어[10-11]로 구성되기 때문에 상대적으로 적은 하드웨어 오버헤드를 사용하여 구현할 수 있다[1-9]. 본 논문에서는 다양한 방식으로 연구 및 개발되고 있으며 구현 난이도와 성능 측면에서 선호되어 일반적으로 많이 사용되는 준안정성 기반[2-4] 및 발진기 기반[5-9]의 진 난수 발생기를 연구한 논문을 분석한다.

참고문헌 (12)

M. Bakiri, C. Guyeux, J.-F. Couchot, and A. K. Oudjida, "Survey on hardware implementation of random number generators on FPGA: Theory and experimental analyses," Computer Science Review, vol.27, pp.135-153, 2018. DOI: 10.1016/j.cosrev.2018.01.002

상세보기
I. Vasyltsov, E. Hambardzumyan, Y.-S. Kim, and B. Karpinskyy, "Fast Digital TRNG Based on Metastable Ring Oscillator," Berlin, Heidelberg, 2008: Springer Berlin Heidelberg, in Cryptographic Hardware and Embedded Systems, pp.164-180, 2008.
M. Majzoobi, F. Koushanfar, and S. Devadas, "FPGA-based true random number generation using circuit metastability with adaptive feedback control," in Proc. Cryptograph. Hardw. Embedded Syst. (CHES), pp.17-32, 2011.
H. Hata and S. Ichikawa, "FPGA implementation of metastability-based true random number generator," IEICE Trans. Inf. Syst., vol.E95.D, no.2, pp.426-436, 2012. DOI: 10.1587/transinf.E95.D.426

상세보기
B. Sunar, W. J. Martin, and D. R. Stinson, "A provably secure true random number generator with built-in tolerance to active attacks," IEEE Trans. Comput., vol.56, no.1, pp.109-119, 2007. DOI: 10.1109/TC.2007.250627

상세보기
D. Liu, Z. Liu, L. Li, and X. Zou, "A low-cost low-power ring oscillatorbased truly random number generator for encryption on smart cards," IEEE Trans. Circuits Syst. II, Exp. Briefs, vol.63, no.6, pp.608-612, 2016. DOI: 10.1109/TCSII.2016.2530800

상세보기
Q. Tang, B. Kim, Y. Lao, K. K. Parhi and C. H. Kim, "True Random Number Generator circuits based on single-and multi-phase beat frequency detection," Proceedings of the IEEE 2014 Custom Integrated Circuits Conference, pp.1-4, 2014. DOI: 10.1109/CICC.2014.6946136
A. P. Johnson, R. S. Chakraborty and D. Mukhopadyay, "An Improved DCM-Based Tunable True Random Number Generator for Xilinx FPGA," in IEEE Transactions on Circuits and Systems II: Express Briefs, vol.64, no.4, pp.452-456, 2017. DOI: 10.1109/TCSII.2016.2566262

상세보기
N. Nalla Anandakumar, S. K. Sanadhya and M. S. Hashmi, "FPGA-Based True Random Number Generation Using Programmable Delays in Oscillator-Rings," in IEEE Transactions on Circuits and Systems II: Express Briefs, vol.67, no.3, pp.570-574, 2020. DOI: 10.1109/TCSII.2019.2919891

상세보기
J. Von Neumann, "Various techniques used in connection with random digits," Nat. Bureau Standards Appl. Math. Ser., vol.12, pp.36-38, 1951.
V. Rozic, B. Yang, W. Dehaene, and I. Verbauwhede, "Iterating von Neumann's postprocessing under hardware constraints," in 2016 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), pp.37-42, 2016. DOI: 10.1109/HST.2016.7495553
L. E. Bassham, III et al., "A statistical test suite for random and pseudorandom number generators for cryptographic applications, Rev. 1a," U.S. Dept. Commerce, Nat. Inst. Stand. Technol., Rep. SP 800-22, 2010.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

최신 준안정성 및 발진기 기반 진 난수 발생기 비교
Comparison on Recent Metastability and Ring-Oscillator TRNGs 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (10)

표/그림 (10)

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

후속연구

질의응답

참고문헌 (12)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

최신 준안정성 및 발진기 기반 진 난수 발생기 비교 Comparison on Recent Metastability and Ring-Oscillator TRNGs 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

표/그림 (10) 모든 표/그림 보기

표/그림 (10) 슬라이드로 보기

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

후속연구

질의응답

참고문헌 (12)

이 논문을 인용한 문헌

저자의 다른 논문 :

유호영 (7)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

최신 준안정성 및 발진기 기반 진 난수 발생기 비교
Comparison on Recent Metastability and Ring-Oscillator TRNGs 원문보기

초록
AI-Helper

표/그림 (10)

표/그림 (10)

AI 본문요약
AI-Helper