[논문]분할 구조를 갖는 Leap-Ahead 선형 궤환 쉬프트 레지스터 의사 난수 발생기

박영규; 김상춘; 이제훈

doi:10.13089/jkiisc.2014.24.1.51

문제 정의

따라서, 기존 Leap-ahead LFSR의 출력 난수열의 비트 수와 LFSR의 레지스터 수를 고려하여 늘 최대주기를 유지하며 상관관계를 줄여야 한다는 단점을 갖는다. 본 논문에서는 출력되는 난수들간의 상관관계는 기존 Leap-ahead LFSR 구조와 동등하나, 최대 주기 감소폭을 줄일 수 있는 새로운 Leap-ahead LFSR 구조를 제안한다.
본 논문은 Leap-Ahead LFSR로부터 생성되는 난수열의 최대 주기가 감소하는 문제를 해결하는 방법을 제안한다. 이를 위해 LFSR의 레지스터 수와 생성할 난수의 비트 수에 따라 생성되는 난수열의 최대 주기가 감소되는 영향을 분석하고, 이를 토대로 생성된 난수열의 최대주기 감소를 줄일 수 있는 분할구조를 갖는 Leap-ahead LFSR 구조를 제안한다.
하나의 LFSR로 다중 비트 난수를 생성하는 Leap-ahead LFSR 구조는 회로 크기면에서 유리하나, 생성되는 난수열의 최대 주기가 급격히 감소하는 단점을 갖는다. 본 논문은 이를 위해 하나의 큰 LFSR을 사용하는 대신 여러 개로 분할된 Leap-ahead LFSR 구조를 제안하였다. 또한, 분할된 LFSR의 크기에 따라 생성 난수열의 최대 주기 변화를 분석하였다.
Leap-ahead LFSR 구조는 생성하려는 난수의 비트 수와 LFSR의 스테이지 수에 따라 최대 주기가큰 폭으로 감소하는 단점을 갖는다. 최대 주기가 감소 하는 현상을 방지하기 위하여 본 논문에서는 하나의큰 LFSR을 이용하는 대신 분할된 LFSR을 연결하는 세그먼티드 Leap-ahead 구조를 제안한다.

제안 방법

제안된 분할 구조를 갖는 Leap-ahead 구조는 기존 Leap-ahead 구조에서 사용되는 LFSR의 절반 크기를 갖는 두 LFSR를 연결하여 구성하였다. 32-비트 난수발생기는 16단의 LFSR을 두 개 연결하여 구성하였고, 마찬가지 방식으로 64 및 128비트 난수발생기는 32단 및 64단의 LFSR을 각각 연결하여 회로를 구성하였다.
마지막으로, 분할된 LFSR의 크기에 따른 최대 주기 변화율을 실험하였다. 64-bit 난수발생기를 설계하고, 생성 난수열의 최대주기 변화를 실험하였다. 두개로 분할된 LFSR은 같은 32-bit 크기인 경우와 서로 다른 크기를 갖는 경우의 출력을 비교하였다.
64-bit 난수발생기를 설계하고, 생성 난수열의 최대주기 변화를 실험하였다. 두개로 분할된 LFSR은 같은 32-bit 크기인 경우와 서로 다른 크기를 갖는 경우의 출력을 비교하였다. 특히, 서로 다른 크기의 LFSR은 모두 소수로만 연결 가능한 조합을 구한 후 그 차이가 가장 적은 조합으로 구성하였다.
본 논문은 이를 위해 하나의 큰 LFSR을 사용하는 대신 여러 개로 분할된 Leap-ahead LFSR 구조를 제안하였다. 또한, 분할된 LFSR의 크기에 따라 생성 난수열의 최대 주기 변화를 분석하였다. 이를 통해 두 개로 분할된 LFSR의 경우 LFSR의 단 수, n 의 2ⁿ-1과 출력 난수열의 비트수 m이 서로 소인 경우 동일한 크기로 구성하면 이론적인 최대 주기 2ⁿ-1에가깝게 난수열을 생성할 수 있고, 만일 그렇지 않은 경우 두 LFSR을 차이가 가장 적은 두 개의 소수로 크기를 결정하면 평균적으로 11%의 손실만이 발생함을 확인하였다.
마지막으로, 분할된 LFSR의 크기에 따른 최대 주기 변화율을 실험하였다. 64-bit 난수발생기를 설계하고, 생성 난수열의 최대주기 변화를 실험하였다.
본 논문에서 제안된 구조를 VHDL로 합성한 후, Xilinx사의 FPGA를 이용하여 동작을 검증하였다. 실험을 위해 설계된 난수 발생기는 매 사이클마다 32, 64, 그리고 128 비트의 난수열을 하나씩 출력한다.
실험을 위해 설계된 난수 발생기는 매 사이클마다 32, 64, 그리고 128 비트의 난수열을 하나씩 출력한다. 성능 비교를 위해 기존 Leap-ahead LFSR과 제안된 구조를 동일한 설계과정으로 합성 후 성능을 비교 하였다. 제안된 분할 구조를 갖는 Leap-ahead 구조는 기존 Leap-ahead 구조에서 사용되는 LFSR의 절반 크기를 갖는 두 LFSR를 연결하여 구성하였다.
그림 6과 기존 16-bit Leap-ahead LFSR 구조에서 발생되는 최대 주기 감소를 극복하기 위해 하나의 16-bit LFSR 대신 두 개의 8-bit LFSR들을 연결하여 구성한 난수발생기에서 생성한 난수열의 최대 주기를 비교한 결과를 나타낸다. 실험은 m의 값을 1에서 15까지 증가시켜 최대 주기 변화율을 구하였다. 기존 Leap-Ahead LFSR 구조는 2¹⁶-1과 나누어지는 m값을 갖는 3, 5, 6, 9, 그리고 15인 부분에서 최대 주기가 (2¹⁶-1)/3, (2¹⁶-1)/5, (2¹⁶-1)/6, (2¹⁶-1)/9, (2¹⁶-1)/15만큼 감소되는 결과를 나타낸다.
본 논문에서 제안된 구조를 VHDL로 합성한 후, Xilinx사의 FPGA를 이용하여 동작을 검증하였다. 실험을 위해 설계된 난수 발생기는 매 사이클마다 32, 64, 그리고 128 비트의 난수열을 하나씩 출력한다. 성능 비교를 위해 기존 Leap-ahead LFSR과 제안된 구조를 동일한 설계과정으로 합성 후 성능을 비교 하였다.
그러나, 난수발생기 설계 특성상 LFSR의 단 수와 출력되는 난수의 비트 수를 위와 같은 조건으로 구성하기 어려워져 생성되는 난수열의 최대 주기가 짧아지게 된다. 이러한 문제를 해결하기 위해 하나의 LFSR 대신 여러 개의 작은 LFSR을 시리즈로 연결하는 분할된 Leap-ahead LFSR 구조를 제안한다.
생성된 난수열이 복잡하여 예측이 어려워야 한다. 이를 위해 LFSR을 이용한 난수발생기를 이용한다.
본 논문은 Leap-Ahead LFSR로부터 생성되는 난수열의 최대 주기가 감소하는 문제를 해결하는 방법을 제안한다. 이를 위해 LFSR의 레지스터 수와 생성할 난수의 비트 수에 따라 생성되는 난수열의 최대 주기가 감소되는 영향을 분석하고, 이를 토대로 생성된 난수열의 최대주기 감소를 줄일 수 있는 분할구조를 갖는 Leap-ahead LFSR 구조를 제안한다.
최근 대부분의 어플리케이션은 다중 비트 난수 생성이 요구된다. 이를 위해 n개의 LFSR을 중첩시켜 구성한 다중 LFSR 구조로 n-비트 난수를 출력한다. 이는 하드웨어적으로 설계가 간단하나, 회로가 커진다는 단점을 갖는다.
표 2는 제안된 세그먼티드 Leap-Ahead LFSR 구조를 사용할 때 생성되는 난수열의 최대 주기를 나타낸다. 전체 Leap-ahead LFSR을 두 개의 Leap-ahead LFSR로 분할하였다.
제안된 구조는 2n-1이 m으로 나누어지는 경우와 그렇지 않은 경우에 따라 두 개의 MUX를 제어한다.
성능 비교를 위해 기존 Leap-ahead LFSR과 제안된 구조를 동일한 설계과정으로 합성 후 성능을 비교 하였다. 제안된 분할 구조를 갖는 Leap-ahead 구조는 기존 Leap-ahead 구조에서 사용되는 LFSR의 절반 크기를 갖는 두 LFSR를 연결하여 구성하였다. 32-비트 난수발생기는 16단의 LFSR을 두 개 연결하여 구성하였고, 마찬가지 방식으로 64 및 128비트 난수발생기는 32단 및 64단의 LFSR을 각각 연결하여 회로를 구성하였다.
제안된 회로는 그림 5와 같이 하나의 LFSR을 두 세그먼트로 분할했다. 제안된 구조는 2ⁿ-1이 m으로 나누어지는 경우와 그렇지 않은 경우에 따라 두 개의 MUX를 제어한다.
특히, 서로 다른 크기의 LFSR은 모두 소수로만 연결 가능한 조합을 구한 후 그 차이가 가장 적은 조합으로 구성하였다. 즉, 64-bit LFSR을 두 개의 LFSR로 분할할 경우, 소수로만 가능한 조합은 (41, 23), (47+17), (53+11) 이렇게 3가지 경우가 발생하고두 LFSR의 크기 차이가 가장 적은 (41, 23)을 기준 하여 설계하였다. 실험 결과는 16-bit LFSR을 이용 하여 설계한 예와 유사한 결과를 나타낸다.
첫 번째로, 회로의 하드웨어적인 복잡도와 동작 속도를 비교하였다. 표 3은 기존 Leap-ahead 구조와 제안된 구조를 비교 결과를 나타낸다.

성능/효과

따라서, 상관관계는 감소되나, 최대 주기가 15대신 5로 줄어들게 된다. 결론적으로 Leap-Ahead LFSR 구조의 경우 생성된 난수열의 상관관계와 최대주기간의 변화를 고려하여 m을 설정하여야만 한다. 특히, 출력되는 난수들의 상관관계가 가장 적으면서 최대 주기 2 ⁿ-1을 유지하는 조합이 가장 이상적이다.
기존 Leap-Ahead LFSR 구조는 2¹⁶-1과 나누어지는 m값을 갖는 3, 5, 6, 9, 그리고 15인 부분에서 최대 주기가 (2¹⁶-1)/3, (2¹⁶-1)/5, (2¹⁶-1)/6, (2¹⁶-1)/9, (2¹⁶-1)/15만큼 감소되는 결과를 나타낸다. 두 개의 8-bit LFSR들로 나누어 구성한 경우, 8-비트 LFSR의 최대 주기인 2⁸-1과 나누어지지 않는 m값을 갖는 6과 9인 경우 생성되는 난수열의 최대 주기가 이론적으로 가장 긴 2ⁿ-1에 근접할 정도로 회복됨을 알 수 있다. 또한 m이 3, 5인 경우에는 2개로 분할할 경우 최대 주기가 오히려 감소한다.
첫째, 출력되는 키 수열의 주기가 짧으면 쉽게 예측이 가능하므로 긴 주기를 가져야 한다. 둘째, 출력 난수열은 상호간에 상관관계 없이 랜덤해야 한다. 셋째, 키 수열은 큰 성형 복잡성을 가져야 한다.
따라서 제안된 분할 구조를 갖는 Leap-ahead 구조에서 생성된 난수열은 크게 2ⁿ-1과 m이 서로 소인 경우 하나의 큰 LFSR로 동작하는 경우와, 그렇지 않고 두 개의 작은 LFSR들로 구동될 때 각각 주기 계산식이 변화한다. 첫 번째로, 하나의 큰 Leap-ahead LFSR 구조로 동작하는 경우 생성 난수열의 최대 주기, T_max는 식 (6)과 같이 구할 수 있다.
반면에, 제안된 구조는 m이 3과 5일 때 각각 최대 주기의 크기가 65,025와 21,675가 된다. 따라서, m이 3인 경우 최대 주기는 65,535로 유지되고 m이 3인 경우에도 기존 Leap-ahead 구조에 비해 최대 주기의 감소폭을 크게 줄일 수 있다.
이 결과는 128-bit와 256-bit를 출력하는 난수발생기에서도 동일한 현상이 발생한다. 따라서, 제안된 난수 발생기는 기존 Leap-ahead LFSR에 비해 생성되는 난수열의 최대주기의 감소율을 크게 줄일수 있고, 동일한 크기로 분할하였을 때, 각 LFSR의단 수, n의 2ⁿ-1과 출력 난수열의 비트수 m이 서로 소인 경우 동일한 크기로 구성할 경우 생성되는 최대 주기의 손실이 가장 적고, 만일 서로 소가 아닌 경우두 LFSR을 소수 중 가장 차이가 적은 크기로 구성할 경우 평균적으로 생성 난수열의 최대 주기가 가장 적게 감소함을 확인하였다.
둘째, 출력 난수열은 상호간에 상관관계 없이 랜덤해야 한다. 셋째, 키 수열은 큰 성형 복잡성을 가져야 한다. 생성된 난수열이 복잡하여 예측이 어려워야 한다.
또한, 분할된 LFSR의 크기에 따라 생성 난수열의 최대 주기 변화를 분석하였다. 이를 통해 두 개로 분할된 LFSR의 경우 LFSR의 단 수, n 의 2ⁿ-1과 출력 난수열의 비트수 m이 서로 소인 경우 동일한 크기로 구성하면 이론적인 최대 주기 2ⁿ-1에가깝게 난수열을 생성할 수 있고, 만일 그렇지 않은 경우 두 LFSR을 차이가 가장 적은 두 개의 소수로 크기를 결정하면 평균적으로 11%의 손실만이 발생함을 확인하였다.
표 1에서 나타낸 것처럼 출력되는 난수의 비트 수가 3과 5일 때 생성되는 난수열의 최대 주기가 감소된다. 즉, 최대주기인 2ⁿ-1인 65,535를 최대공약 수인 3과 5로 각각 나눈 값만큼 감소되어, 각각의 최대 주기가 21,845 그리고 13,107로 감소한다. 반면에, 제안된 구조는 m이 3과 5일 때 각각 최대 주기의 크기가 65,025와 21,675가 된다.
첫째, 출력되는 키 수열의 주기가 짧으면 쉽게 예측이 가능하므로 긴 주기를 가져야 한다.
표 3은 기존 Leap-ahead 구조와 제안된 구조를 비교 결과를 나타낸다. 표 3에 나타낸 것처럼, 회로 크기는 제안된 세그멘티드 Leap-ahead 구조가 기존 구조에 비해 약 2배 증가함을 알 수 있다. 그러나 동작 속도면에서, 제안된 구조는 32비트에서 5.

핵심어	질문	논문에서 추출한 답변
	Leap-ahead LFSR 구조는 무엇이며 어떤 단점을 가지는가?	Gu는 이러한 문제를 해결하기 위해 Leap-ahead LFSR 구조를 제안하였다[6]. 하나의 LFSR을 이용하여 하나의 사이클에 다중 비트의 난수를 생성한다. 그러나, 이 구조는 생성난수의 비트 수와 LFSR의 레지스터 크기 관계에 따라 생성되는 난수열의 주기가 크게 감소하는 단점이 있다.
	암호 분야에서 저전력 특징을 갖는 제한된 크기의 암호 회로제작을 위해 무엇을 사용하는가?	선형 궤환 쉬프트 레지스터는 데이터 스크램블, 에러 정정 코드, 데이터 암호화, 그리고 난수 발생기와 같은 다양한 어플리케이션에 사용되고 있다 [1-5]. 특히, 유비쿼터스 환경에서는 저전력 특징을 갖는 제한된 크기의 암호 회로가 필요하며, 대칭키 암호 방식에 비해 적은 면적과 저전력 특성을 갖는 스트림 암호 방식 그리고 LFSR을 이용한 난수 발생기가 주로 사용된다.
	LFSR이 의사 난수 발생기인 이유는?	이상적인 난수는 생성 방법이 결정되어 있지 않고, 다음에 생성될 난수 값이 전혀 예측할 수 없어야만 한다. LFSR 구조에서 생성되는 난수들은 일정한 절차에 의해 만들어지며 완전히 무작위적으로 생성 되지 않기 때문에 의사 난수 발생기 (PRNG, pseudo-random number generator)라 부른다. LFSR 구조는 쉬프트 레지스터에 입력되는 값이 이전 상태값의 선형 함수로 계산되는 구조를 가지고 있다.

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

연합인증

분할 구조를 갖는 Leap-Ahead 선형 궤환 쉬프트 레지스터 의사 난수 발생기
A Segmented Leap-Ahead LFSR Pseudo-Random Number Generator 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

성능/효과

질의응답

참고문헌 (7)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

연합인증

분할 구조를 갖는 Leap-Ahead 선형 궤환 쉬프트 레지스터 의사 난수 발생기 A Segmented Leap-Ahead LFSR Pseudo-Random Number Generator 원문보기

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

Abstract ▼ AI-Helper

주제어

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

문제 정의

제안 방법

성능/효과

질의응답

참고문헌 (7)

이 논문을 인용한 문헌

저자의 다른 논문 :

김상춘 (19) 이제훈 (19)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

분할 구조를 갖는 Leap-Ahead 선형 궤환 쉬프트 레지스터 의사 난수 발생기
A Segmented Leap-Ahead LFSR Pseudo-Random Number Generator 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper