[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

KR20130014003A - Non-linear binary random number generator using feedback carry shift register - Google Patents

Non-linear binary random number generator using feedback carry shift register Download PDF

Info

Publication number
KR20130014003A
KR20130014003A KR1020110075988A KR20110075988A KR20130014003A KR 20130014003 A KR20130014003 A KR 20130014003A KR 1020110075988 A KR1020110075988 A KR 1020110075988A KR 20110075988 A KR20110075988 A KR 20110075988A KR 20130014003 A KR20130014003 A KR 20130014003A
Authority
KR
South Korea
Prior art keywords
shift register
fcsr
random number
output
lfsr
Prior art date
Application number
KR1020110075988A
Other languages
Korean (ko)
Inventor
서창호
이규민
Original Assignee
공주대학교 산학협력단
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 공주대학교 산학협력단 filed Critical 공주대학교 산학협력단
Priority to KR1020110075988A priority Critical patent/KR20130014003A/en
Publication of KR20130014003A publication Critical patent/KR20130014003A/en

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/58Random or pseudo-random number generators
    • G06F7/582Pseudo-random number generators
    • G06F7/584Pseudo-random number generators using finite field arithmetic, e.g. using a linear feedback shift register
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F5/00Methods or arrangements for data conversion without changing the order or content of the data handled
    • G06F5/01Methods or arrangements for data conversion without changing the order or content of the data handled for shifting, e.g. justifying, scaling, normalising
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/483Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers
    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03KPULSE TECHNIQUE
    • H03K19/00Logic circuits, i.e. having at least two inputs acting on one output; Inverting circuits
    • H03K19/20Logic circuits, i.e. having at least two inputs acting on one output; Inverting circuits characterised by logic function, e.g. AND, OR, NOR, NOT circuits
    • H03K19/21EXCLUSIVE-OR circuits, i.e. giving output if input signal exists at only one input; COINCIDENCE circuits, i.e. giving output only if all input signals are identical

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Computing Systems (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Computational Mathematics (AREA)
  • Nonlinear Science (AREA)
  • Computer Hardware Design (AREA)
  • Mathematical Physics (AREA)
  • Complex Calculations (AREA)

Abstract

PURPOSE: A nonlinear binary random number generator using an FCSR(Feedback Carry Shift Register) which is suitable for a human body interesting area is provided to offer excellent statistics characteristics and to guarantee the maximum cycle of random numbers. CONSTITUTION: An LFSR(Linear Feedback Shift Register)(11) includes an LSR(Linear Shift Register) based on primitive polynomials. An FCSR(12) includes the LSR based on a 2-adic number system. An XOR calculation unit(13) generates a random number sequence by exclusively combining the output of the LFSR and the FCSR. The LFSR includes a shift register unit which comprises shift registers; a feedback number unit including a value which indicates a connection state of the shift register; and a linear feedback function unit which generates output by receiving the output of the shift register and the feedback number unit.

Description

인체 관심영역에 적합한 FCSR을 이용한 비선형 이진 난수 발생기{Non-linear binary random number generator using feedback carry shift register}Non-linear binary random number generator using feedback carry shift register}

본 발명은 핵 물리, 대기 체계(Quening) 이론에서의 컴퓨터 소프트웨어의 우수성 판정 등 과학적, 공학적인 분야에서 암호학적으로 안전한 비선형 랜덤수열을 발생하는 응용 가능한 이진 난수 발생기에 관한 것이다.
The present invention relates to a binary random number generator applicable to generating cryptographically safe nonlinear random sequences in scientific and engineering fields such as the determination of the superiority of computer software in nuclear physics and quenching theory.

더 상세하게는, 본 발명은, 고속으로 난수를 발생할 수 있고, 소프트웨어 구현이 용이하면서도 비도가 우수하며, 난수의 통계적 특성이 우수한 비선형 이진 난수 발생기 및 그 구성방법에 관한 것이다.
More specifically, the present invention relates to a non-linear binary random number generator that can generate random numbers at high speed, is easy to implement software, has excellent ratio, and has excellent statistical characteristics of random numbers, and a method of constructing the same.

종래, 예를 들면, 인체 관심영역 탐지엔진 시스템에서의 디지털 서명, 무결성, 신분확인 등을 비롯한 정보보호 서비스를 제공하는 환경에 사용되는 이진 난수 발생기는, 주로 원시 다항식(primitive polynomial)에 근거한 선형 시프트 레지스터(Linear Feedback Shift Register ; LFSR)를 이용하여 구성되어 있다.
Conventionally, for example, a binary random number generator used in an environment for providing information protection services including digital signature, integrity, identification, etc. in a human body area detection engine system is mainly a linear shift based on primitive polynomials. It is configured using a Linear Feedback Shift Register (LFSR).

여기서, LFSR이란, 시프트 레지스터의 일종으로, 레지스터에 입력되는 값이 이전 상태 값들의 선형함수로 계산되는 구조를 가지는 것이다.
Here, LFSR is a kind of shift register, in which a value input to the register is calculated as a linear function of previous state values.

또한, 이때 사용되는 선형 함수는 주로 배타적 논리합(XOR)이며, LFSR의 초기 비트 값은 시드(seed)라고 한다.
In addition, the linear function used at this time is mainly an exclusive OR (XOR), and the initial bit value of the LFSR is called a seed.

아울러, LFSR의 동작은 결정론적이므로, 즉, LFSR로 생성되는 값의 수열은 그 이전 값에 의해 결정된다.
In addition, since the operation of the LFSR is deterministic, that is, the sequence of values generated by the LFSR is determined by its previous value.

또한, 레지스터가 가질 수 있는 값의 개수는 유한하기 때문에, 이 수열은 특정한 주기에 의해 반복되나, 선형 함수를 잘 선택하면 주기가 길고 무작위적으로 보이는 수열을 생성할 수 있어, 의사 난수, 의사 난수 잡음(PRN), 빠른 디지털 카운터, 백지화 수열 등의 분야에서 사용된다.
In addition, because the number of values a register can have is finite, this sequence is repeated by a specific period, but if you choose a linear function well, you can generate a sequence that looks long and random, so that it is pseudo-random, pseudo-random. It is used in applications such as noise (PRN), fast digital counters, and blanking sequences.

아울러, 이러한 LFSR을 이용한 종래의 난수발생기의 예로서는, 예를 들면, 등록특허 제10-0480998호(2005.03.24. 등록)의 "디지털 하드웨어 시스템 보안 장치 및 방법"이 있다.
In addition, an example of a conventional random number generator using the LFSR is, for example, "Digital Hardware System Security Apparatus and Method" of Patent No. 10-0480998 (registered on March 24, 2005).

즉, 상기한 등록특허 제10-0480998호의 디지털 하드웨어 시스템 보안 장치 및 방법은, 하드웨어 시스템 버스의 클록 동기화를 위해 LFSR 및 비대칭키 암호 알고리즘을 사용하여 자신의 비밀키를 노출시키지 않는 상태에서 서로 안전하게 분배된 키값을 시프트 레지스터에 저장 및 출력시키는 유사 난수 발생기와, 유사 난수 발생기의 출력값과 하드웨어 시스템 버스를 통과하는 데이터에 대하여 모듈러-2 덧셈 연산(modular-2 addition)을 수행하여 고성능 시스템 버스와 입출력 버스를 암호화하는 배타적 이진 연산기와, 비대칭키 암호 알고리즘 기반 RSA 암호 알고리즘 및 타원곡선 암호 알고리즘을 사용하여 비대칭으로 암호화하는 비대칭키 암호 모듈을 포함하는 디지털 하드웨어 시스템 보안장치 및 방법이 개시되어 있다.
That is, the digital hardware system security apparatus and method of the above-mentioned Patent No. 10-0480998 securely distribute each other without exposing their secret keys using LFSR and asymmetric key cryptographic algorithm for clock synchronization of the hardware system bus. A pseudo-random number generator that stores and outputs the calculated key values in a shift register, and a modular-2 addition operation on the output of the pseudo-random number generator and data passing through the hardware system bus to perform a high performance system bus and an input / output bus. Disclosed is a digital hardware system security apparatus and method including an exclusive binary operator for encrypting asymmetric key, an asymmetric key cryptographic module for asymmetric encryption using an asymmetric key cryptographic algorithm based RSA cryptographic algorithm and an elliptic curve cryptographic algorithm.

또한, 종래의 일반적인 난수 발생기는, 일반적으로, 선형 합동법(Linear Congruential Method)을 주로 이용하여 난수를 발생하고 있다.
In addition, a conventional general random number generator generally generates a random number mainly using a linear congruential method.

그러나 이러한 방법들은, 난수의 통계적 특성은 우수하지만, 그 선형적인 성질 때문에 암호 수열로서는 사용이 불가능하다는 문제점이 있었다.
However, these methods have a problem that the statistical properties of random numbers are excellent, but they cannot be used as cipher sequences because of their linear nature.

이러한 문제점들을 해결하기 위해, 예를 들면, "FCSR 난수열의 암호학적 특성에 관한 연구", 서창호 외 3인, 한국정보처리학회 논문지 제8-C권 제1호 2001.02.에 개시된 바와 같이, FCSR(feedback carry shift register)을 이용한 난수 발생기에 대한 연구가 진행되고 있다.
In order to solve these problems, for example, "A Study on the Cryptographic Characteristics of FCSR Random Number Sequence", Seo Chang-ho et al., Journal of Korea Information Processing Society, Vol. 8-C No. 1, 2001.02. Research is being conducted on random number generators using a feedback carry shift register.

즉, 암호기술에서 응용 가능한 난수 발생기는, 암호학적으로 안전하고, 고속으로 난수 발생이 가능하여야 한다.
That is, the random number generator applicable to the encryption technology should be cryptographically secure and capable of generating random numbers at high speed.

따라서 암호기술의 분야에서 이용하기 적합한 난수 발생기를 제공하기 위하여는, 통계적 특성이 우수하면서도 암호학적으로 안전한 동시에, 고속으로 난수 발생이 가능한 비선형 이진 난수 발생기를 제공하는 것이 바람직하나, 아직까지 그러한 요구를 모두 만족시키는 장치나 방법은 제공되지 못하고 있는 실정이다.
Therefore, in order to provide a random number generator suitable for use in the field of cryptographic technology, it is desirable to provide a nonlinear binary random number generator that has excellent statistical characteristics, is cryptographically secure and capable of generating random numbers at high speed. There is no device or method that satisfies all of them.

본 발명은 상기한 바와 같은 종래기술의 문제점을 해결하고자 하는 것으로, 따라서 본 발명의 목적은, 대수적 체계가 다르고 서로 상반된 특성을 가지는 LFSR(Linear Feedback Shift Register)과 FCSR(Feedback Carry Shift Register)을 결합한 비선형 이진 난수 발생기 및 그 설계방법을 제공하고자 하는 것이다.
The present invention is to solve the problems of the prior art as described above, and therefore the object of the present invention is to combine a linear feedback shift register (LFSR) and a feedback carry shift register (FCSR) having different characteristics of algebraic systems and mutually opposite characteristics. A nonlinear binary random number generator and its design method are provided.

상기한 바와 같은 목적을 달성하기 위해, 본 발명에 따르면, 원시 다항식(primitive polynomial)에 근거한 선형 시프트 레지스터로 구성되는 LFSR(Linear Feedback Shift Register)와, 이진전개로 표현될 수 있는 수인 2-adic 수의 체계에 기반을 둔 선형 시프트 레지스터로 구성되는 FCSR(Feedback Carry Shift Register) 및 상기 LFSR의 출력 수열과 상기 FCSR의 출력 수열에 배타적인 논리합을 수행하여 난수열을 발생하는 XOR 연산부를 포함하는 것을 특징으로 하는 FCSR을 이용한 비선형 이진 난수 발생기가 제공된다.
In order to achieve the above object, according to the present invention, a linear feedback shift register (LFSR) consisting of a linear shift register based on a primitive polynomial, and a 2-adic number which is a number that can be represented by binary evolution. And a XOR operation unit configured to generate a random number sequence by performing an exclusive OR on the output sequence of the output sequence of the LFSR and the output sequence of the LFSR. A nonlinear binary random number generator using FCSR is provided.

여기서, 상기 LFSR은, n개의 시프트 레지스터로 구성되는 시프트 레지스터부와, 원시 다항식의 계수로서 0 또는 1의 값을 취하며, 상기 시프트 레지터부의 연결상태를 나타내는 값을 가지는 궤환 상수부 및 상기 시프트 레지스터부의 각 단을 S0, S1, ... Sn - 1라 하고, 각 단의 시프트 레지스터의 출력값을 s0, s1, ... sn - 1라 하며, 상기 시프트 레지터부의 연결상태를 나타내는 값을 Ci(C0 = 1, i = 1, 2,....)라 할 때, 상기 궤환 상수부와 상기 시프트 레지스터의 각 단의 출력을 입력받아 이하의 수식에 의해 출력 P를 생성하는 선형 궤환 함수부를 포함하는 것을 특징으로 한다.
Here, the LFSR is a shift register part consisting of n shift registers, a feedback constant part having a value of 0 or 1 as a coefficient of a primitive polynomial, and having a value indicating a connection state of the shift register part and the shift. Each stage of the register section is referred to as S 0 , S 1 , ... S n - 1 , and the output value of the shift register of each stage is referred to as s 0 , s 1 , ... s n - 1 , and the shift register section When the value indicating the connection state is C i (C 0 = 1, i = 1, 2, ...), the output of each stage of the feedback constant part and the shift register is inputted according to the following equation. It characterized in that it comprises a linear feedback function for generating an output P.

또한, 상기 LFSR은, 상기 선형 궤환 함수부에서 상기 출력 P = s0 + C1s1 + ... + Cn -1 sn -1을 구하고, 최하위 비트 s0를 출력하며, 레지스터의 내용들을 오른쪽으로 한 칸씩 이동하는 처리를 수행하는 것을 특징으로 한다.
In addition, the LFSR, the output P = s 0 in the linear feedback function unit + C 1 s 1 + ... + C n -1 s n -1 is calculated, the least significant bit s 0 is output, and the contents of the register are shifted one space to the right.

아울러, 상기 FCSR은, r(r은 양의 정수)개의 시프트 레지스터로 구성되는 시프트 레지스터부와, 상기 시프트 레지스터부의 연결상태를 나타내는 값(qi(q0 = 1, i= 1, 2, ...), 2가 아닌 소수 q에 대하여 q+1 = q12 + q222 + ... + qr2r, qi ∈ {0, 1})으로서 0 또는 1의 값을 가지는 연결정수부와, 입력 정보를 저장한 후 다음 단계에서 출력하는 메모리부 및 상기 연결 정수부와 상기 시프트 레지스터의 각 단의 출력을 입력받아 이하의 수식에 의해 출력 P를 생성하는 합산부를 포함하는 것을 특징으로 한다.
In addition, the FCSR includes a shift register section consisting of r (r is a positive integer) shift registers and a value (q i (q 0) indicating a connection state of the shift register section . = 1, i = 1, 2, ...), for prime q other than 2 q + 1 = q 1 2 + q 2 2 2 + ... + q r 2 r , q i ∈ {0, 1}), a connection constant having a value of 0 or 1, a memory unit for storing input information and outputting the output information in the next step, and receiving outputs of each stage of the connection constant unit and the shift register as follows. And an adder for generating the output P by the equation.

Figure pat00001

Figure pat00001

또한, 상기 FCSR은, 상기 메모리부의 선두를 0 또는 1로 초기화하고, 상기 합산부를 통하여 이하의 수식에 의해 정수합을 구하며,
In addition, the FCSR initializes the head of the memory unit to 0 or 1, obtains an integer sum through the summation unit by the following formula,

Figure pat00002

Figure pat00002

최하위 비트 s0를 출력하고, 레지스터의 내용들을 오른쪽으로 한 칸씩 이동하고, sr ≡ L(mod 2)를 시프트 레지스터의 최상위 셀(cell)에 대치시키며, 상기 메모리부를 (L- sr -1)/2로 변경하는 처리를 수행하는 것을 특징으로 한다.
Outputs the least significant bit s 0 , shifts the contents of the register one space to the right, replaces s r ≡ L (mod 2) with the most significant cell of the shift register, and stores the memory unit (L-s r -1). The process of changing to) / 2 is carried out.

상기한 바와 같이, 본 발명에 따르면, 난수의 최대 주기를 보장하면서도 비도 및 통계적 특성이 우수한 비선형 이진 난수 발생기를 제공할 수 있다.
As described above, according to the present invention, it is possible to provide a nonlinear binary random number generator that is excellent in the degree of non-binding and statistical properties while ensuring the maximum period of the random number.

또한, 본 발명에 따르면, 상기한 바와 같이 하여, 범용 신호처리 또는 전자문서 거래 시스템에서의 디지털 서명, 무결성, 신분확인 등을 포함하는 정보보호 서비스를 제공하는 환경에 효과적으로 사용될 수 있는 비선형 이진 난수 발생기를 제공할 수 있다.
Further, according to the present invention, as described above, a nonlinear binary random number generator that can be effectively used in an environment for providing an information protection service including digital signature, integrity, identification, etc. in a general purpose signal processing or electronic document transaction system. Can be provided.

도 1은 본 발명의 실시예에 따른 비선형 이진 난수 발생기의 구조를 개략적으로 나타내는 도면이다.
도 2는 도 1에 나타낸 본 발명의 실시예에 따른 비선형 이진 난수 발생기의 LFSR의 구성을 개략적으로 나타내는 도면이다.
도 3은 도 1에 나타낸 본 발명의 실시예에 따른 비선형 이진 난수 발생기의 FCSR의 구성을 개략적으로 나타내는 도면이다.
1 is a view schematically showing the structure of a nonlinear binary random number generator according to an embodiment of the present invention.
FIG. 2 is a diagram schematically illustrating a configuration of the LFSR of the nonlinear binary random number generator according to the embodiment of the present invention shown in FIG. 1.
3 is a diagram schematically showing the configuration of FCSR of the nonlinear binary random number generator according to the embodiment of the present invention shown in FIG.

이하, 상기한 바와 같은 본 발명에 따른 FCSR을 이용한 비선형 이진 난수 발생기의 상세한 내용에 대하여 설명한다.
Hereinafter, the details of the nonlinear binary random number generator using the FCSR according to the present invention as described above will be described.

여기서, 이하에 설명하는 내용은 본 발명을 실시하기 위한 하나의 실시예일 뿐이며, 본 발명은 이하에 설명하는 실시예의 내용으로만 한정되는 것은 아니라는 사실에 유념해야 한다.
Hereinafter, it is to be noted that the following description is only an embodiment for carrying out the present invention, and the present invention is not limited to the contents of the embodiments described below.

즉, 본 발명은, 후술하는 바와 같이, 대수적 체계가 다르고 서로 상반된 특성을 가지는 LFSR(Linear Feedback Shift Register)과 FCSR(Feedback Carry Shift Register)을 결합하여 비선형 이진 난수 발생기를 설계하는 방법을 제공하고자 하는 것이다.
That is, the present invention is to provide a method for designing a nonlinear binary random number generator by combining a linear feedback shift register (LFSR) and a feedback carry shift register (FCSR), which have different algebraic systems and have opposite characteristics. will be.

따라서 본 발명에 따르면, 난수의 최대 주기를 보장하며, 비도 및 통계적 특성이 우수한 비선형 이진 난수 발생기를 제공할 수 있으며, 그것에 의해, 범용 신호처리 또는 전자문서 거래 시스템에서의 디지털 서명, 무결성, 신분확인 등을 비롯한 정보보호 서비스를 제공하는 환경에 효과적으로 사용될 수 있다.
Therefore, according to the present invention, it is possible to provide a nonlinear binary random number generator which guarantees a maximum period of random numbers and is excellent in non-frequency and statistical characteristics, whereby digital signature, integrity, identification in a general purpose signal processing or electronic document transaction system It can be effectively used in an environment for providing information security services, including.

이하 첨부된 도면을 참조하여, 본 발명에 따른 FCSR을 이용한 비선형 이진 난수 발생기의 구체적인 실시예에 대하여 상세하게 설명한다.
Hereinafter, exemplary embodiments of a nonlinear binary random number generator using FCSR according to the present invention will be described in detail with reference to the accompanying drawings.

먼저, 도 1을 참조하면, 도 1은 본 발명의 실시예에 따른 비선형 이진 난수 발생기의 구성을 개략적으로 나타내는 도면이다.
First, referring to FIG. 1, FIG. 1 is a diagram schematically illustrating a configuration of a nonlinear binary random number generator according to an embodiment of the present invention.

즉, 도 1에 나타낸 바와 같이, 본 발명의 실시예에 따른 비선형 이진 난수 발생기(10)는, LFSR(11), FCSR(12) 및 XOR 연산부(13)를 포함하여 구성된다.
That is, as shown in FIG. 1, the nonlinear binary random number generator 10 according to the embodiment of the present invention includes the LFSR 11, the FCSR 12, and the XOR calculation unit 13.

여기서, LFSR(11)는, 원시 다항식에 근거한 선형 시프트 레지스터이며, FCSR(12)은, 2-adic 수(이진전개로 표현될 수 있는 수)의 체계에 기반을 둔 선형 시프트 레지스터이고, XOR 연산부(13)는, 배타적인 논리합으로서, LFSR(11)의 출력 수열(at)과 FCSR(12)의 출력 수열(bt)에 배타적인 논리합을 수행하여 난수열(ct = at XOR bt)을 발생한다.
Here, the LFSR 11 is a linear shift register based on a primitive polynomial, and the FCSR 12 is a linear shift register based on a system of 2-adic numbers (numbers that can be represented by binary evolution), and an XOR operation unit. 13 is an exclusive OR, the output sequence of a LFSR (11) (a t) and FCSR (12), the output sequence (b t) by performing an exclusive-OR-random number sequence (c t = a a t XOR b of t )

또한, 상기한 바와 같이 구성된 본 발명의 실시예에 따른 비선형 이진 난수 발생기(10)의 전체적인 난수 발생동작 과정은 다음과 같다.
In addition, the overall random number generation operation of the non-linear binary random number generator 10 according to the embodiment of the present invention configured as described above is as follows.

먼저, LFSR(11), FCSR(12)를 동작시켜 각각의 출력 수열을 발생시킨다.
First, the LFSR 11 and the FCSR 12 are operated to generate respective output sequences.

다음으로, XOR 연산부(13)를 통하여, 각각의 LFSR(11), FCSR(12)에서 발생시킨 난수열에 배타적 논리합을 수행하여 난수열(ct = at XOR bt)을 발생한다.
Next, an exclusive OR is performed on the random numbers generated by each of the LFSRs 11 and FCSR 12 through the XOR operator 13 to generate a random number sequence c t = a t XOR b t .

더 상세하게는, 도 2를 참조하면, 상기한 바와 같이 구성된 본 발명의 실시예에 따른 비선형 이진 난수 발생기(10)의 LFSR(11)의 구성을 개략적으로 나타내는 도면이다.
More specifically, referring to FIG. 2, a diagram schematically illustrating the configuration of the LFSR 11 of the nonlinear binary random number generator 10 according to the embodiment of the present invention configured as described above.

즉, 도 2에 나타낸 바와 같이, 본 발명의 실시예에 따른 비선형 이진 난수 발생기(10)의 LFSR(11)은, 시프트 레지스터부(21), 궤환 상수부(22), 선형 궤환 함수부(23)를 포함하여 구성된다.
That is, as shown in FIG. 2, the LFSR 11 of the nonlinear binary random number generator 10 according to the embodiment of the present invention includes a shift register 21, a feedback constant 22, and a linear feedback function 23. It is configured to include).

여기서, 시프트 레지스터부(21)는, n개의 시프트 레지스터로 구성되며, 각 단은 S0, S1, ... Sn - 1 로 표현되고, 각 단의 시프트 레지스터의 출력 값을 s0, s1, ... sn -1이라 한다.
Here, the shift register section 21 is composed of n shift registers, each stage is represented by S 0 , S 1 , ... S n - 1 , and the output value of the shift register of each stage is s 0 ,. s 1 , ... s n -1

또한, 궤환 상수부(22)는, 원시 다항식의 계수로서 0 또는 1의 값을 취하며, 시프트 레지터부(21)의 연결상태를 나타내는 Ci(C0 = 1, i = 1, 2,....)의 값이다.
In addition, the feedback constant portion 22 takes a value of 0 or 1 as a coefficient of the primitive polynomial, and represents C i (C 0 = 1, i = 1, 2, 2) indicating the connection state of the shift register portion 21. ...).

아울러, 선형 궤환 함수부(23)는, 궤환 상수부(22)와 각 단의 시프트 레지스터(21)의 출력을 입력받아 이하의 [수학식 1]에 의해 출력 P를 생성한다.
In addition, the linear feedback function unit 23 receives the outputs of the feedback constant unit 22 and the shift registers 21 of each stage, and generates an output P by the following Equation (1).

Figure pat00003
Figure pat00003

또한, 상기한 바와 같은 LFSR(11)의 전체적인 동작 과정에 대하여 설명하면 다음과 같다.
In addition, the overall operation of the LFSR 11 as described above will be described.

먼저, 선형 궤환 함수부(23)에서 정수합 s0 + C1s1 + ... + Cn -1 sn -1 을 구한다.
First, the integer sum s 0 in the linear feedback function unit 23. + C 1 s 1 + ... + C n -1 s n -1

다음으로, 최하위 비트 s0를 출력하고, 레지스터의 내용들을 오른쪽으로 한 칸씩 이동한다.
Next, output the least significant bit s 0 , shifting the contents of the register one space to the right.

계속해서, 도 3을 참조하면, 도 3은 도 1에 나타낸 FCSR(12)의 전체적인 구성을 개략적으로 나타내는 도면이다.
3, FIG. 3 is a diagram schematically showing the overall configuration of the FCSR 12 shown in FIG.

즉, 도 3에 나타낸 바와 같이, 본 발명의 실시예에 따른 비선형 이진 난수 발생기(10)의 FCSR(12)은, 시프트 레지스터부(31), 연결정수부(32), 메모리부(33), 합산부(34)를 포함하여 구성된다.
That is, as shown in FIG. 3, the FCSR 12 of the nonlinear binary random number generator 10 according to the embodiment of the present invention includes a shift register 31, a connection constant 32, a memory 33, and a summation. It is comprised including the part 34.

여기서, 연결 정수부(302)는, 시프트 레지스터부(31)의 연결상태를 나타내는 qi(q0 = 1, i= 1, 2, ...)의 값으로, 2가 아닌 소수 q에 대하여 q+1 = q12 + q222 + ... + qr2r, qi ∈ {0, 1}과 같은 이진 전개로서 0 또는 1의 값을 가진다.
Here, the connection constant part 302 is a value of q i (q 0 = 1, i = 1, 2, ...) indicating the connection state of the shift register part 31, and q for a decimal number q that is not two. +1 = q 1 2 + q 2 2 2 + ... + q r 2 r , q i 전개 binary expansion, such as {0, 1}, with a value of 0 or 1.

또한, 이는, 메모리부(33)의 1비트의 저장 정보량이며, 다음 단계의 저장 정보는, 합산부(34)의 몫에 해당한다.
In addition, this is the amount of storage information of one bit of the memory unit 33, and the storage information of the next step corresponds to the share of the summing unit 34.

또한, 합산부(34)는, 연결 정수부(32)와 각 단의 시프트 레지스터(31)의 출력을 입력받아 다음과 같은 [수학식 2]에 의해 출력 P를 생성한다.
In addition, the adder 34 receives the outputs of the connection constant part 32 and the shift registers 31 of each stage, and generates an output P by the following [Equation 2].

Figure pat00004
Figure pat00004

계속해서, 상기한 바와 같이 구성된 FCSR(12)의 전체적인 동작 과정은 다음과 같다.
Subsequently, the overall operation of the FCSR 12 configured as described above is as follows.

먼저, 메모리(33)의 선두를 0 또는 1로 초기화한다.
First, the head of the memory 33 is initialized to zero or one.

다음으로, 합산부(34)를 통하여, 이하의 [수학식 3]과 같은 정수합을 구한다.
Next, the sum of integers as shown in the following [Equation 3] is obtained through the adding unit 34.

Figure pat00005
Figure pat00005

그 후, 최하위 비트 s0를 출력하고, 레지스터의 내용들을 오른쪽으로 한 칸씩 이동한다.
After that, it outputs the least significant bit s 0 and shifts the contents of the register one space to the right.

다음으로, sr ≡ L(mod 2)를 시프트 레지스터의 최상위 셀(cell)에 대치시킨다.
Next, replace s r ≡ L (mod 2) with the most significant cell of the shift register.

이어서, 메모리(33)를 (L- sr -1)/2로 변경한다.
Next, the memory 33 is changed to (L-s r -1 ) / 2.

상기한 바와 같은 과정을 통하여, 본 발명에 따른 LFSR과 FCSR을 결합한 비선형 이진 난수 발생기를 구현할 수 있다.
Through the above process, it is possible to implement a nonlinear binary random number generator combining the LFSR and FCSR according to the present invention.

따라서 본 발명에 따르면, 상기한 바와 같이 하여 난수의 최대 주기를 보장하며, 비도 및 통계적 특성이 우수한 LFSR과 FCSR을 결합한 비선형 이진 난수 발생기가 제공되므로, 범용 신호처리 또는 전자문서 거래 시스템에서의 디지털 서명, 무결성, 신분확인 등을 비롯한 정보보호 서비스를 제공하는 환경에 효과적으로 사용될 수 있다.
Therefore, according to the present invention, a nonlinear binary random number generator combining LFSR and FCSR, which guarantees a maximum period of random numbers as described above and has excellent degree of non-frequency and statistical characteristics, is provided. It can be effectively used in environments that provide information security services, including security, integrity, and identification.

10. 난수 발생기 11. LFSR
12. FCSR 13. XOR 연산부
21. 시프트 레지스터부 22. 궤환 상수부
23. 선형 궤환 함수부 31. 시프트 레지스터부
32. 연결정수부 33. 메모리부
34. 합산부
10. Random Number Generator 11.LFS
12.FCSR 13. XOR calculation unit
21. Shift register section 22. Feedback constant section
23. Linear Feedback Function Unit 31. Shift Register Unit
32. Connection constant 33. Memory
34. Summing up

Claims (5)

원시 다항식(primitive polynomial)에 근거한 선형 시프트 레지스터로 구성되는 LFSR(Linear Feedback Shift Register)와,
이진전개로 표현될 수 있는 수인 2-adic 수의 체계에 기반을 둔 선형 시프트 레지스터로 구성되는 FCSR(Feedback Carry Shift Register) 및
상기 LFSR의 출력 수열과 상기 FCSR의 출력 수열에 배타적인 논리합을 수행하여 난수열을 발생하는 XOR 연산부를 포함하는 것을 특징으로 하는 FCSR을 이용한 비선형 이진 난수 발생기.
Linear Feedback Shift Register (LFSR) consisting of linear shift registers based on primitive polynomials,
Feedback Carry Shift Register (FCSR), consisting of a linear shift register based on a 2-adic number system, a number that can be represented as binary evolution, and
And an XOR operation unit configured to generate a random number sequence by performing an exclusive OR on the output sequence of the LFSR and the output sequence of the FCSR.
제 1항에 있어서,
상기 LFSR은,
n(n은 양의 정수)개의 시프트 레지스터로 구성되는 시프트 레지스터부와,
원시 다항식의 계수로서 0 또는 1의 값을 취하며, 상기 시프트 레지터부의 연결상태를 나타내는 값을 가지는 궤환 상수부 및
상기 시프트 레지스터부의 각 단을 S0, S1, ... Sn - 1라 하고, 각 단의 시프트 레지스터의 출력값을 s0, s1, ... sn - 1라 하며, 상기 시프트 레지터부의 연결상태를 나타내는 값을 Ci(C0 = 1, i = 1, 2,....)라 할 때, 상기 궤환 상수부와 상기 시프트 레지스터의 각 단의 출력을 입력받아 이하의 수식에 의해 출력 P를 생성하는 선형 궤환 함수부를 포함하는 것을 특징으로 하는 FCSR을 이용한 비선형 이진 난수 발생기.

Figure pat00006

The method of claim 1,
The LFSR is,
a shift register section composed of n (n is a positive integer) shift registers,
A feedback constant part having a value of 0 or 1 as a coefficient of the primitive polynomial and having a value representing a connection state of the shift register part;
Each stage of the shift register is referred to as S 0 , S 1 , ... S n - 1 , and an output value of the shift register of each stage is referred to as s 0 , s 1 , ... s n - 1 , and the shift register When the value indicating the connection state of the tab is C i (C 0 = 1, i = 1, 2, ...), the following equation is obtained by receiving the output of each stage of the feedback constant part and the shift register. Nonlinear binary random number generator using the FCSR, characterized in that it comprises a linear feedback function for generating an output P by.

Figure pat00006

제 2항에 있어서,
상기 LFSR은,
상기 선형 궤환 함수부에서 상기 출력 P = s0 + C1s1 + ... + Cn -1 sn -1을 구하고, 최하위 비트 s0를 출력하며, 레지스터의 내용들을 오른쪽으로 한 칸씩 이동하는 처리를 수행하는 것을 특징으로 하는 FCSR을 이용한 비선형 이진 난수 발생기.
The method of claim 2,
The LFSR is,
The output P = s 0 in the linear feedback function + C 1 s 1 + ... + C n -1 s A nonlinear binary random number generator using FCSR characterized by obtaining the n -1 , outputting the least significant bit s 0 , and shifting the contents of the register one space to the right.
제 1항에 있어서,
상기 FCSR은,
r(r은 양의 정수)개의 시프트 레지스터로 구성되는 시프트 레지스터부와,
상기 시프트 레지스터부의 연결상태를 나타내는 값(qi(q0 = 1, i= 1, 2, ...), 2가 아닌 소수 q에 대하여 q+1 = q12 + q222 + ... + qr2r, qi ∈ {0, 1})으로서 0 또는 1의 값을 가지는 연결정수부와,
입력 정보를 저장한 후 다음 단계에서 출력하는 메모리부 및
상기 연결 정수부와 상기 시프트 레지스터의 각 단의 출력을 입력받아 이하의 수식에 의해 출력 P를 생성하는 합산부를 포함하는 것을 특징으로 하는 FCSR을 이용한 비선형 이진 난수 발생기.

Figure pat00007

The method of claim 1,
The FCSR is,
a shift register section composed of r (r is a positive integer) shift registers,
A value representing the connection state of the shift register unit q i (q 0 = 1, i = 1, 2, ...), for prime q other than 2 q + 1 = q 1 2 + q 2 2 2 + ... + q r 2 r , q i 0 {0, 1}), a connection constant having a value of 0 or 1,
A memory unit which stores the input information and outputs it in the next step; and
And a summation unit for receiving an output of each stage of the connection integer unit and the shift register and generating an output P according to the following formula.

Figure pat00007

제 4항에 있어서,
상기 FCSR은,
상기 메모리부의 선두를 0 또는 1로 초기화하고, 상기 합산부를 통하여 이하의 수식에 의해 정수합을 구하며,

Figure pat00008


최하위 비트 s0를 출력하고, 레지스터의 내용들을 오른쪽으로 한 칸씩 이동하고, sr ≡ L(mod 2)를 시프트 레지스터의 최상위 셀(cell)에 대치시키며, 상기 메모리부를 (L- sr -1)/2로 변경하는 처리를 수행하는 것을 특징으로 하는 FCSR을 이용한 비선형 이진 난수 발생기.
5. The method of claim 4,
The FCSR is,
Initialize the head of the memory unit to 0 or 1, obtain an integer sum through the summation unit by the following formula,

Figure pat00008


Outputs the least significant bit s 0 , shifts the contents of the register one space to the right, replaces s r ≡ L (mod 2) with the most significant cell of the shift register, and stores the memory unit (L-s r -1). Nonlinear binary random number generator using FCSR, characterized in that to perform the processing to change to () / 2.
KR1020110075988A 2011-07-29 2011-07-29 Non-linear binary random number generator using feedback carry shift register KR20130014003A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020110075988A KR20130014003A (en) 2011-07-29 2011-07-29 Non-linear binary random number generator using feedback carry shift register

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020110075988A KR20130014003A (en) 2011-07-29 2011-07-29 Non-linear binary random number generator using feedback carry shift register

Publications (1)

Publication Number Publication Date
KR20130014003A true KR20130014003A (en) 2013-02-06

Family

ID=47894386

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020110075988A KR20130014003A (en) 2011-07-29 2011-07-29 Non-linear binary random number generator using feedback carry shift register

Country Status (1)

Country Link
KR (1) KR20130014003A (en)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104199635A (en) * 2014-09-23 2014-12-10 无锡华大国奇科技有限公司 Pseudo-random number generator integrating CRC (cyclic redundancy check) circuit
CN115714644A (en) * 2022-10-31 2023-02-24 北京海泰方圆科技股份有限公司 Random number generation method and device

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104199635A (en) * 2014-09-23 2014-12-10 无锡华大国奇科技有限公司 Pseudo-random number generator integrating CRC (cyclic redundancy check) circuit
CN104199635B (en) * 2014-09-23 2017-11-07 无锡华大国奇科技有限公司 The pseudorandom number generator of integrated CRC check circuit
CN115714644A (en) * 2022-10-31 2023-02-24 北京海泰方圆科技股份有限公司 Random number generation method and device
CN115714644B (en) * 2022-10-31 2023-08-15 北京海泰方圆科技股份有限公司 Random number generation method and device

Similar Documents

Publication Publication Date Title
Essaid et al. Image encryption scheme based on a new secure variant of Hill cipher and 1D chaotic maps
US8320557B2 (en) Cryptographic system including a mixed radix number generator with chosen statistical artifacts
Kanso et al. A novel image encryption algorithm based on a 3D chaotic map
US6961426B2 (en) Cascaded stream cipher
Ravichandran et al. Encrypted biography of biomedical image-a pentalayer cryptosystem on FPGA
Patnala et al. A modernistic way for KEY generation for highly secure data transfer in ASIC design flow
Kang et al. Fast image encryption algorithm based on (n, m, k)-PCMLCA
Paar et al. Stream ciphers
Pandit et al. Lwr-based quantum-safe pseudo-random number generator
AVAROĞLU et al. A novel S-box-based postprocessing method for true random number generation
Sowmya et al. Symmetric key image encryption scheme with key sequences derived from random sequence of cyclic elliptic curve points over GF (p)
KR20130014003A (en) Non-linear binary random number generator using feedback carry shift register
Reyad et al. Pseudo-random sequence generation from elliptic curves over a finite field of characteristic 2
Hafsa et al. Secure transmission of medical images using improved hybrid cryptosystem: authentication, confidentiality and integrity
Manucom et al. Security analysis of improved one-time pad cryptography using TRNG key generator
Gupta et al. Improved VLSI architecture of dual-CLCG for Pseudo-Random bit generator
Thamrin et al. An enhanced hardware-based hybrid random number generator for cryptosystem
Mostfa Kamal et al. The design trends of keystream generator for stream cipher for high immunity attacks
Deepthi et al. New stream ciphers based on elliptic curve point multiplication
Rahman et al. Design and security-mitigation of custom and configurable hardware cryptosystems
Pathirage et al. Multi-Prime RSA Verilog Implementation Using 4-Primes
Li et al. FPGA implementation of a coupled‐map‐lattice‐based cryptosystem
Lee et al. Uniform random number generator using leap-ahead LFSR architecture
Andreev et al. Effective quaternion and octonion cryptosystems and their FPGA implementation
BALRAJ A Provably Secure True Random Number Generator

Legal Events

Date Code Title Description
WITN Withdrawal due to no request for examination