[논문]SDRAM을 사용한 난수 발생

표창우

초록
AI-Helper

보안을 위한 암호 키는 진난수 발생기를 사용하여 만들어야 한다. 진난수 발생기는 상태 예측이 거의 불가능한 혼란 진원지에서 초기값을 추출하여 비가역적 해시 알고리즘을 적용해 난수를 만들어 낸다. DRAM 접근 대기 시간(latency)에도 불규칙성이 존재하여 혼란 진원지 역할을 할 수 있음이 알려져 있는데, 요즘 널리 사용되는 동기식 DRAM (SDRAM)을 장착한 시스템에서는 접근 대기 시간의 불규칙성이 잘 노출되지 않으며, 난수 비트 패턴의 뭉침 현상이 심해진다. 이 문제를 xor 연산을 사용하여 해결하였다. 이 방법으로 만든 난수를 통계학적으로 평가하여 진난수에 필적하는 품질을 확인하였다. 이와 같은 난수 발생 방법의 성능은 100 Kbits/sec 수준이며, 별도의 장치나 회로를 요구하지 않아 DRAM을 장착하고 있는 여러 형태의 컴퓨터 장비에서 사용 가능하다.

Abstract ▼ AI-Helper

Cryptographic keys for security should be generated by true random number generators that apply irreversible hashing algorithms to initial values taken from a random source. As DRAM shows randomness in its access latency, it can be used as a random source. However, systems with synchronous DRAM (SDR...

Cryptographic keys for security should be generated by true random number generators that apply irreversible hashing algorithms to initial values taken from a random source. As DRAM shows randomness in its access latency, it can be used as a random source. However, systems with synchronous DRAM (SDRAM) do not easily expose such randomness resulting in highly clustered random numbers. We resolved this problem by using the xor instruction. Statistical testing shows that the generated random bits have the quality comparable to true random bit sequences. The performance of bit generation is at the order of 100 Kbits/sec. Since the proposed random number generation requires neither external devices nor any special circuits, this method may be used in any computing device that employs DRAM.

주제어

AI 본문요약
AI-Helper

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

가설 설정

난수의 품질은 15개의 개별 테스트로 구성된 NIST의 통계학적 난수 검증 패키지[13]를 사용하여 평가하였다(DFT 검증에 오류를 [14] 에서 제안한 대로 수정하여 사용하였다、각 테스트의 1회 검증은 1, 000개의표본에 대하여 반복적으로 진행하였다. 각 테스트는 표본 비트 열이 난수 비트라는 가설을 검정한다. 통계학적검증을 통과하더라도 사용한 RNG가 완전한 TRNG라는 증거는 아니고 유의 수준에 따른 신뢰를 할 수 있음을 의미한다.
1 차이의 10개의 등간격 구간에 나누어 배치한 다음 X2 검증을 수행한다. 균일 분포라면 구간 당 100에 가까운 P-value들을 가질 것이다.

제안 방법

대기시간의 변동성이 잘 노출되지 않는다. 이를 극복하기 위하여 xor 연산을 사용하여 포획된 비트들을뒤섞는 방식으로 난수 발생기를 구성하였다. 제안된 난수 발생 방법은 진난수 수준에 근접하는 난수 비트열을초당 수십에서 수백 킬로 비트 정도까지의 속도로 생성해 날 수 있었다.
이를 극복하기 위하여 xor 연산을 사용하여 포획된 비트들을뒤섞는 방식으로 난수 발생기를 구성하였다. 제안된 난수 발생 방법은 진난수 수준에 근접하는 난수 비트열을초당 수십에서 수백 킬로 비트 정도까지의 속도로 생성해 날 수 있었다.
정량적으로 나타낼 수 있다. 집중 접근 코드를여러 차례 실행하여 n 종류의 실행 주기가 측정되었고, 각 실행 주기의 상대 빈도를 fi라 하면 측정된 실행 주기의 분포가 갖는 엔트로피는 다음과 같다.
품질 평가 결과는 표 1에 요약되어 있다. 평가를 위한난수 비트는 메모리 접근을 256회, 512회 반복하게 하고, 3번 비트부터 8비트 단위로 추출하였다. 각 메모리접근 회수의 첫째 열은 개별 테스트 P-value들의 분포를 보이는 P-value이며, 둘째 열은 테스트 통과 비율이다.

대상 데이터

시험은 2.33GHz 펜티움 코어2 쿼드 프로세서와 DDR2의 FB-DIMM을 장착한 서버 시스템에서 진행하였다. 난수의 품질은 15개의 개별 테스트로 구성된 NIST의 통계학적 난수 검증 패키지[13]를 사용하여 평가하였다(DFT 검증에 오류를 [14] 에서 제안한 대로 수정하여 사용하였다、각 테스트의 1회 검증은 1, 000개의표본에 대하여 반복적으로 진행하였다.

데이터처리

33GHz 펜티움 코어2 쿼드 프로세서와 DDR2의 FB-DIMM을 장착한 서버 시스템에서 진행하였다. 난수의 품질은 15개의 개별 테스트로 구성된 NIST의 통계학적 난수 검증 패키지[13]를 사용하여 평가하였다(DFT 검증에 오류를 [14] 에서 제안한 대로 수정하여 사용하였다、각 테스트의 1회 검증은 1, 000개의표본에 대하여 반복적으로 진행하였다. 각 테스트는 표본 비트 열이 난수 비트라는 가설을 검정한다.

성능/효과

비슷한 비율로 측정되었다. 대조적으로 기록 명령으로 메모리 집중 접근 코드를 만들었을 때에는 비순차적실행에 의한 엔트로피 기여도가 거의 없거나, 그림 3의 write-128의 경우와 같이 순차적 접근의 경우 보다 엔트로피 감소 현상을 보이기도 했다(엔트로피 음의 영역으로 표시됨). 읽기 명령과 기록 명령을 번갈아 실행했을 때에도 비순차적 접근에 의한 엔트로피 기여 부분도읽기 명령 만에 의한 것보다 현저히 적었으며 메모리접근 회수가 증가할수록 임의로 발생하는 캐시 미스로인한 엔트로피 기여 부분이 줄어들었다.
메모리 접근을 512 정도 반복하였을때 10회 되풀이된 실험에서 5회 분포와 통과율 모두 통과하였다. 실험 결과는 xor 연산 회수를 증가시키면, 난수 품질이 좋아짐을 보이고 있다. 실험이 진행된 시스템에서 난수 발생 성능은 100 K bits/sec 정도인데, 프로세서의 속도와 DRAM 모듈의 구조에 따라 큰 변동을보인다.
대조적으로 기록 명령으로 메모리 집중 접근 코드를 만들었을 때에는 비순차적실행에 의한 엔트로피 기여도가 거의 없거나, 그림 3의 write-128의 경우와 같이 순차적 접근의 경우 보다 엔트로피 감소 현상을 보이기도 했다(엔트로피 음의 영역으로 표시됨). 읽기 명령과 기록 명령을 번갈아 실행했을 때에도 비순차적 접근에 의한 엔트로피 기여 부분도읽기 명령 만에 의한 것보다 현저히 적었으며 메모리접근 회수가 증가할수록 임의로 발생하는 캐시 미스로인한 엔트로피 기여 부분이 줄어들었다. 읽기 만으로 구성된 접근 코드와 비교할 때 엔트로피 발생 효율은 비슷한 수준이다.

후속연구

제안된 RNG는 난 수화 품질이 좋은 PRNG에 초기값을 공급하는데 유용하게 사용될 수 있다. 메모리 접근회수를 줄여 임의성에서는 손실을 입더라도 양질의 PRNG를 후처리기로 사용하면 성능과 품질의 적절한균형을 이룰 수 있다.
메모리 접근회수를 줄여 임의성에서는 손실을 입더라도 양질의 PRNG를 후처리기로 사용하면 성능과 품질의 적절한균형을 이룰 수 있다. 제안된 RNG는 일반 컴퓨터 시스템으로부터 개인 휴대 단말기에 이르기까지 DRAM을사용하는 모든 시스템에서 사용될 수 있는 장점이 있다.

참고문헌 (14)

A. Alkassar, T. Nicolay, and M. Rohe, "Obtaining true-random binary numbers from a weak radioactive source," ICCSA (2), Lecture Notes in Computer Science, vol.3481, pp.634-646, 2005.
M. Haahr, RANDOM.ORG, http://www.random.org, Trinity College, Ireland, 1998.
L. Noll, LAVARND, http://www.lavarnd.org, 2000.
W. Killmann, W. Schindler, "A Design for a Physical RNG with Robust Entropy Estimators," CHES 2008, Lecture Notes in Computer Science, vol.5154, pp.146-163, 2008.
M. Dichtl and J. Golic, "High-Speed True Random Number Generation with Logic Gates Only," CHES 2007, Lecture Notes in Computer Science, vol.4727, pp.45-62, 2007.
I. Vasyltsov, E. Hambardzumyan, Y. Kim, B. Karpinskyy, "Fast Digital TRNG based on Metastable Ring Oscillator," CHES 2008, Lecture Notes in Computer Science, vol.5154, pp.164-180, 2008.
D. Davis, R. Ihaka, and P. Fenstermacher, "Cryptographic randomness from air turbulence in disk drives," CRYPTO '94: Proc. of the 14th Annual International Cryptology Conference on Advances in Cryptology, pp.114-120, Springer-Verlag, 1994.
A. SEZNEC and N. SENDRIER, "HAVEGE: A User-Level Software Heuristic for Generating Empirically Strong Random Numbers," ACM Transactions on Modeling and Computer Simulation, vol.13, no.4, pp.334-346, 2003.

상세보기
V. Cuppu, B. Jacob, B. Davis, T. Mudge, "A Performance Comparison of Contemporary DRAM Architectures," 26th Annual International Symposium on Computer Architecture (ISCA'99), vol.27, no.2, pp.222-232, 1999.
B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd ed., pp.233- 234, John Wiley & Sons, New York, 1996.
B. Jacob, S. Ng, D. Wang, Memory System: Cache, DRAM, Disk, pp.465-480, Morgan-Kaufman Publishers Inc., Massachusetts, 2007.
B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd ed., p.425, John Wiley & Sons, New York, 1996.
A. Rukhin, J. Soto, etal., A statistical test suite for random and pseudorandom number generators for cryptographic applications, Revised, L. Bassham III, Special Publication SP 800-22 rev.1, National Institute of Standards and Technology (NIST), Aug. 2008.
S. Kim, K. Umeno, A. Hasegawa, Corrections of the NIST statistical test suite for randomness. Cryptology ePrint Archive, Report 2004/018, 2004.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

SDRAM을 사용한 난수 발생
Random Number Generation using SDRAM 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

가설 설정

제안 방법

대상 데이터

데이터처리

성능/효과

후속연구

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

연관된 기능

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

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

선택된 텍스트

연합인증

SDRAM을 사용한 난수 발생 Random Number Generation using SDRAM 원문보기

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

Abstract ▼ AI-Helper

주제어

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

가설 설정

제안 방법

대상 데이터

데이터처리

성능/효과

후속연구

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

표창우 (11)

관련 콘텐츠

원문 보기

원문 URL 링크

연관된 기능

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

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

선택된 텍스트

SDRAM을 사용한 난수 발생
Random Number Generation using SDRAM 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper