KR19990050425A - 에프씨에스알를 이용한 비선형 2진 난수 발생기 - Google Patents

Abstract

본 발명은 FCSR를 이용한 비선형 2진 난수 발생기에 관한 것으로, 특히 디지털 서명, 무결성, 신분인증 등을 비롯한 정보 보호 서비스의 핵심 요소로서 사용될 수 있을 뿐 아니라 범용 신호처리, 게임이론, 통계 데이터 처리, 확산 스펙트럼, 핵 물리, 대기이론(Queuing theory) 등에서 암호학적으로 안전한 비선형 랜덤수열을 발생하는 FCSR를 이용한 비선형 2진 난수 발생기에 관한 것이다. 본 발명의 목적은 고속으로 난수를 발생할 수 있고, 소프트웨어 및 하드웨어 구현이 용이하면서 안전성도 우수하고, 또 난수의 통계적 특성도 우수한 비선형 2진 난수 발생기를 제공하는 데에 있다. 본 발명의 정보 보호 서비스의 핵심요소로서 사용되는 FCSR를 이용한 비선형 2진 난수 발생기는 서로 다른 수열을 출력하는 복수개의 FCSR과, 상기 FCSR로부터 출력된 수열들을 부울함수에 입력하여 난수열을 발생하는 논리부로 구성된 것을 특징으로 한다.

Description

에프씨에스알를 이용한 비선형 2진 난수 발생기

본 발명은 FCSR(Feedback with Carry Shift Register)을 이용한 비선형 2진 난수 발생기에 관한 것으로, 특히 디지털 서명, 무결성(integrity check), 신분인증 등을 비롯한 정보 보호 서비스의 핵심 요소로서 사용될 수 있을 뿐 아니라 범용 신호처리, 게임이론, 통계 데이터 처리, 확산 스펙트럼, 핵 물리, 대기이론(Queuing theory) 등에서 암호학적으로 안전한 비선형 랜덤수열을 발생하는 FCSR를 이용한 비선형 2진 난수 발생기에 관한 것이다.

종래의 소프트웨어 난수 발생기들은 선형 합동법(Linear Congruential Method)을 주로 사용하고 있다. 또, 스트림 암호에 많이 사용하고 있는 원시 다항식(Primitive Polynomial)에 근거한 선형 궤환 쉬프트 레지스터(Linear Feedback Shift Register)를 이용한 난수 발생기도 많이 이용되고 있다.

정보 보호 기술에서 응용 가능한 2진 난수 발생기는 암호학적으로 안전하고, 고속으로 난수를 발생하는 가능을 가져야 한다. 따라서, 난수 발생기의 안전성 측면에서 고려해야 할 척도로는 긴 주기와 선형 복잡도를 대표적인 예로 들 수 있다.

또한, 최근에는 1993년 미국의 A. Klapper와 M. Goresky가 주기 수열을 생성할 수 있는 가장 짧은 FCSR의 길이를 의미하는 2진 복잡도라는 새로운 개념을 소개하여 난수 발생기가 가져야 할 새로운 척도로 추가되었다. 여기서, 주기는 동일한 출력 수열이 나오는 시기를 의미하고, 선형 복잡도는 주기를 갖는 출력 수열을 생성할 수 있는 가장 짧은 선형 궤환 쉬프트 레지스터의 길이를 의미한다.

종래의 기술은 LFSR과 LFSR 혹은 LFSR과 FCSR을 결합하는 방식에 대해서 제안했다.

먼저, n차 LFSR과 FCSR을 사용하는 결합 방법에 대하여 자세히 살펴보자.

n차 단순 선형 궤환 쉬프트 레지스터의 경우 주기는 최대 주기(2ⁿ-1)를 보장해 주지만 선형 복잡도가 n이기 때문에, 2⁸⁰의 선형 복잡도를 얻기 위해서는 2⁸⁰차 선형 궤환 쉬프트 레지스터를 사용해야 하므로 효율성 측면에서 우수하지 않다. 또한, LFSR만을 결합한 선형 궤환 쉬프트 레지스터 중에서 가장 우수한 BRM(Binary Rated Multiplier)가 n차 m-LFSR을 두 개 결합했을 경우의 주기는 (2ⁿ-1)(2ⁿ-1) 정도로 거의 최대 주기에 근접하나 선형 복잡도는 n(2ⁿ-1) 정도이다. 그리고, n차 FCSR을 단독으로 사용할 경우의 주기는 2ⁿ-1에 거의 근접하며 선형 복잡도 2ⁿ-1에 거의 근접한다. 그러나, 2진 복잡도에 의하면, 이 수열은 n정도의 복잡도만을 가지므로 안전한 난수 발생기로서는 부적합하다. 그리고, LFSR과 FCSR을 배타적 논리합으로 결합할 경우의 주기는 (2ⁿ-1)(2ⁿ-1) 정도로 우수하나 선형 복잡도는 (2ⁿ-1) 정도밖에 되지 않는 문제점이 있다.

또, 이러한 선형 합동법을 사용한 방법 난수의 통계적 특성은 우수하지만 선형적인 성질 때문에 정보 보호 분야에서 사용하는 것은 안전성 측면에서 부적합하다. 또한, 상기 선형 궤환 쉬프트 레지스터 자체는 선형 복잡도에 취약하여 단독으로 사용하기에는 부적합하므로, 몇 개의 선형 궤환 쉬프트 레지스터를 결합하여 난수 발생기를 설계해야 하는 문제점이 있다.

따라서, 상기의 문제점을 해결하기 위한 본 발명의 목적은 고속으로 난수를 발생할 수 있고, 소프트웨어 및 하드웨어 구현이 용이하면서 안전성도 우수하며, 또 난수의 통계적 특성도 우수한 FCSR를 이용한 비선형 2진 난수 발생기를 제공하는 데에 있다.

본 발명의 다른 목적은 작은 크기의 레지스터를 사용하여 수열을 쉽게 생성할 뿐만 아니라 적은 수의 레지스터만으로도 충분히 높은 안전성을 갖는 수열을 생성할 수 있는 FCSR를 이용한 비선형 2진 난수 발생기를 제공하는 데에 있다.

상기의 목적을 달성하기 위한 본 발명의 정보 보호 서비스의 핵심요소로서 사용되는 FCSR를 이용한 비선형 2진 난수 발생기는 서로 다른 수열을 출력하는 복수개의 FCSR과, 상기 FCSR로부터 출력된 수열들을 부울함수에 입력하여 난수열을 발생하는 논리부로 구성된 것을 특징으로 한다.

이 때, 상기 논리부는 상기 복수개의 FCSR로부터 출력된 수열을 곱하는 곱셈부와, 상기 복수개의 FCSR 중 임의의 하나의 출력수열을 상기의 곱셈부의 결과와 배타적 논리합으로 결합하는 결합부로 구성된다.

본 발명의 FCSR를 이용한 비선형 2진 난수 발생기는 제 1 FCSR의 출력수열이 0인 경우에, 제 2 FCSR은 상기 출력수열을 오른쪽으로 한 칸씩 이동시키고, 제 1 FCSR의 출력수열이 1인 경우에는 제 2 FCSR이 상기 출력수열을 오른쪽으로 두 칸씩 이동시키는 시간 조절 논리를 이용하여 구성된 것을 특징으로 한다.

도 1은 FCSR의 구성을 나타내는 블록도,

도 2는 본 발명에 따른 비선형 2진 난수 발생기를 나타내는 구조도,

도 3은 본 발명의 일 실시예에 따른 비선형 2진 난수 발생기를 나타내는 구조도,

도 4는 본 발명의 다른 실시예에 따른 비선형 2진 난수 발생기를 나타내는 구조도,

*도면의 주요부분에 대한 부호의 설명*

101, 201, 301: FCSR1 102, 202, 302: FCSR2

103: FCSRn 104, 203: 부울함수

401: 레지스터부 402: 연결정수부

403: 메모리부 404: 합산부

이하 첨부도면을 참조하여 본 발명의 일 실시예를 상세히 설명한다.

도 1은 FCSR의 구성을 나타내는 블록도이다.

여기서, FCSR은 쉬프트 레지스터부(101), 연결정수부(102), 메모리부(103), 합산부(104)로 구성된다. 이 연결 정수부(102)는 2가 아닌 소수 q에 대해서 q+1 = q₁2 + q₂2²+ ...... + q_r2^r, q_i{0, 1}과 같은 2진 전개로서 모두 0과 1의 값을 취하고, 이 0과 1은 쉬프트 레지스터부(101)의 연결상태를 나타내는 q_i(q₀= 1, I = 1, 2, ....)의 값이다. q_i는 메모리부(103)의 1 비트의 저장 정보량이다. 다음 단계의 저장 정보는 합산부(104)의 몫에 해당한다. 합산부(104)는 연결정수부(102)와 각 단의 쉬프트 레지스터(101)의 출력을 받아 출력 P를 다음과 같은 수학식 1로 생성한다.

다음에, FCSR의 동작에 대해서 설명한다.

먼저, 메모리(103)의 처음은 0 또는 1로 초기화한다. 다음에, 합산부(104)에서 수학식 2와 같은 정수합을 구한다.

그 다음, 최하위 비트 s₀을 출력하고, 레지스터의 내용들을 오른쪽으로 한 칸씩 이동한다.

다음에, s_r≡ L(mod 2)을 쉬프트 레지스터의 최상위 셀(cell)로 대치한다.

마지막으로, 메모리 M을 (L-s_r-1)/2로 바꾼다.

도 2는 본 발명에 따른 비선형 2진 난수 발생기의 구성을 나타낸다.

이 비선형 2진 난수 발생기는 FCSR1(201), FCSR2(202), … FCSRn(203) 및 부울함수 F(204)로 구성된다. FCSR1(201), FCSR2(202), … FCSRn(203)은 2진 수의 체계에 근거한 쉬프트 레지스터이고, 부울함수 F(203)는 FCSR1(201)의 출력수열(a_t)과 FCSR2의 출력수열(b_t)을 부울함수 F에 적용시켜서 난수열((c_t= F(a_t, b_t))을 발생한다.

이하, 난수 발생 동작에 대해서 설명한다.

우선, FCSR1(201), FCSR2(202), … FCSRn(203)을 각각 동작시킨다.

다음에, 부울 함수 F(203)는 상기 과정에서 발생시킨 난수열을 발생한다.

도 3은 본 발명의 일 실시예에 따른 비선형 2진 난수 발생기를 나타낸다.

이 비선형 2진 난수 발생기는 두 개의 FCSR을 결합한 방식으로서, FCSR1(301)과 FCSR2(302)를 부울함수로 결합하였다. 그 동작은 FCSR1과 FCSR2를 각각 동작시켜서 발생된 수열을 F함수에 입력하여 출력수열을 얻는 것이다.

도 4는 본 발명의 다른 실시예에 따른 비선형 2진 난수 발생기를 나타낸다.

시간조절 논리를 사용한 비선형 2진 난수 발생기는 FCSR1(401)의 출력수열이 0인 경우, FCSR2(402)를 1회 동작하고, FCSR1의 출력수열이 1인 경우, FCSR2를 2회 동작하는 방식이다. 즉, FCSR1의 출력 수열에 따라 FCSR2의 동작 횟수를 결정하는 방식이다.

이와 같이, 2개의 FCSR을 비선형 결합하였을 경우, 주기, 선형 복잡도, 2진 복잡도들은 모두 (2ⁿ-1)(2ⁿ-1)에 근접함으로, 본 발명의 비선형 2진 난수 발생기는 종래의 방식에 비하여 안전성에서 매우 우수한 성질을 갖는다. 즉, 적은 수의 쉬프트 레지스터만을 이용하더라도 원하는 안전성을 얻을 수 있다.

예를 들어 두 개의 레지스터를 사용하여 2⁸⁰의 안전성을 얻기 위해 사용되는 레지스터의 개수를 종래의 것과 비교하면 표 1과 같다.

즉, 종래의 방법에 비하여, 1/2 정도의 레지스터만으로 원하는 안전성을 갖는 2진 난수를 발생할 수 있다.

또한, FCSR 자체의 통계적 특성이 우수하므로, 부울함수 F를 특별히 좋지 않은 것을 사용하지 않는 한, 본 발명의 통계적 특성 또한 우수하다. 또한, 주기는 난수의 최대 주기에 근접하여 주기에 의한 공격에도 안전하다.

상술한 바와 같이, 본 발명에 따르면, 여러 개의 FCSR을 다양하게 비선형 결합하여 효율적이며 안전한 2진 난수 발생기를 제공할 수 있다.

또한, 본 발명의 비선형 2진 난수 발생기는 전자 문서 거래 시스템에서의 디지털 서명, 무결성, 신분확인 등을 비롯한 정보 보호 서비스를 제공하는 환경에 효과적으로 사용될 수 있다는 데에 그 효과가 있다.

Claims (3)

1. 정보 보호 서비스의 핵심요소로서 사용되는 FCSR를 이용한 비선형 2진 난수 발생기에 있어서,

   서로 다른 수열을 출력하는 복수개의 FCSR과,

   상기 FCSR로부터 출력된 수열들을 부울함수에 입력하여 난수열을 발생하는 논리부로 구성된 것을 특징으로 하는 FCSR를 이용한 비선형 2진 난수 발생기.
2. 제 1항에 있어서,

   상기 논리부는 상기 복수개의 FCSR로부터 출력된 수열을 곱하는 곱셈부와, 상기 복수개의 FCSR 중 임의의 하나의 출력수열을 상기의 곱셈부의 결과와 배타적 논리합으로 결합하는 결합부로 구성된 것을 특징으로 하는 FCSR를 이용한 비선형 2진 난수 발생기.
3. 제 1 FCSR의 출력수열이 0인 경우에, 제 2 FCSR은 상기 출력수열을 오른쪽으로 한 칸씩 이동시키고, 제 1 FCSR의 출력수열이 1인 경우에는 제 2 FCSR이 상기 출력수열을 오른쪽으로 두 칸씩 이동시키는 시간 조절 논리를 이용하여 구성된 것을 특징으로 하는 FCSR를 이용한 비선형 2진 난수 발생기.