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 PDFInfo
- 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
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/58—Random or pseudo-random number generators
- G06F7/582—Pseudo-random number generators
- G06F7/584—Pseudo-random number generators using finite field arithmetic, e.g. using a linear feedback shift register
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F5/00—Methods or arrangements for data conversion without changing the order or content of the data handled
- G06F5/01—Methods or arrangements for data conversion without changing the order or content of the data handled for shifting, e.g. justifying, scaling, normalising
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods 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/483—Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03K—PULSE TECHNIQUE
- H03K19/00—Logic circuits, i.e. having at least two inputs acting on one output; Inverting circuits
- H03K19/20—Logic 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/21—EXCLUSIVE-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
Description
본 발명은 핵 물리, 대기 체계(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 =
또한, 상기 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,
최하위 비트 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
여기서, 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
먼저, 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
더 상세하게는, 도 2를 참조하면, 상기한 바와 같이 구성된 본 발명의 실시예에 따른 비선형 이진 난수 발생기(10)의 LFSR(11)의 구성을 개략적으로 나타내는 도면이다.
More specifically, referring to FIG. 2, a diagram schematically illustrating the configuration of the
즉, 도 2에 나타낸 바와 같이, 본 발명의 실시예에 따른 비선형 이진 난수 발생기(10)의 LFSR(11)은, 시프트 레지스터부(21), 궤환 상수부(22), 선형 궤환 함수부(23)를 포함하여 구성된다.
That is, as shown in FIG. 2, the
여기서, 시프트 레지스터부(21)는, n개의 시프트 레지스터로 구성되며, 각 단은 S0, S1, ... Sn - 1 로 표현되고, 각 단의 시프트 레지스터의 출력 값을 s0, s1, ... sn -1이라 한다.
Here, the
또한, 궤환 상수부(22)는, 원시 다항식의 계수로서 0 또는 1의 값을 취하며, 시프트 레지터부(21)의 연결상태를 나타내는 Ci(C0 = 1, i = 1, 2,....)의 값이다.
In addition, the feedback
아울러, 선형 궤환 함수부(23)는, 궤환 상수부(22)와 각 단의 시프트 레지스터(21)의 출력을 입력받아 이하의 [수학식 1]에 의해 출력 P를 생성한다.
In addition, the linear
또한, 상기한 바와 같은 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
다음으로, 최하위 비트 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
즉, 도 3에 나타낸 바와 같이, 본 발명의 실시예에 따른 비선형 이진 난수 발생기(10)의 FCSR(12)은, 시프트 레지스터부(31), 연결정수부(32), 메모리부(33), 합산부(34)를 포함하여 구성된다.
That is, as shown in FIG. 3, the
여기서, 연결 정수부(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
또한, 이는, 메모리부(33)의 1비트의 저장 정보량이며, 다음 단계의 저장 정보는, 합산부(34)의 몫에 해당한다.
In addition, this is the amount of storage information of one bit of the
또한, 합산부(34)는, 연결 정수부(32)와 각 단의 시프트 레지스터(31)의 출력을 입력받아 다음과 같은 [수학식 2]에 의해 출력 P를 생성한다.
In addition, the
계속해서, 상기한 바와 같이 구성된 FCSR(12)의 전체적인 동작 과정은 다음과 같다.
Subsequently, the overall operation of the
먼저, 메모리(33)의 선두를 0 또는 1로 초기화한다.
First, the head of the
다음으로, 합산부(34)를 통하여, 이하의 [수학식 3]과 같은 정수합을 구한다.
Next, the sum of integers as shown in the following [Equation 3] is obtained through the adding
그 후, 최하위 비트 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
상기한 바와 같은 과정을 통하여, 본 발명에 따른 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
21.
23. Linear
32. Connection constant 33. Memory
34. Summing up
Claims (5)
이진전개로 표현될 수 있는 수인 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.
상기 LFSR은,
n(n은 양의 정수)개의 시프트 레지스터로 구성되는 시프트 레지스터부와,
원시 다항식의 계수로서 0 또는 1의 값을 취하며, 상기 시프트 레지터부의 연결상태를 나타내는 값을 가지는 궤환 상수부 및
상기 시프트 레지스터부의 각 단을 S0, S1, ... Sn - 1라 하고, 각 단의 시프트 레지스터의 출력값을 s0, s1, ... sn - 1라 하며, 상기 시프트 레지터부의 연결상태를 나타내는 값을 Ci(C0 = 1, i = 1, 2,....)라 할 때, 상기 궤환 상수부와 상기 시프트 레지스터의 각 단의 출력을 입력받아 이하의 수식에 의해 출력 P를 생성하는 선형 궤환 함수부를 포함하는 것을 특징으로 하는 FCSR을 이용한 비선형 이진 난수 발생기.
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.
상기 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.
상기 FCSR은,
r(r은 양의 정수)개의 시프트 레지스터로 구성되는 시프트 레지스터부와,
상기 시프트 레지스터부의 연결상태를 나타내는 값(qi(q0 = 1, i= 1, 2, ...), 2가 아닌 소수 q에 대하여 q+1 = q12 + q222 + ... + qr2r, qi ∈ {0, 1})으로서 0 또는 1의 값을 가지는 연결정수부와,
입력 정보를 저장한 후 다음 단계에서 출력하는 메모리부 및
상기 연결 정수부와 상기 시프트 레지스터의 각 단의 출력을 입력받아 이하의 수식에 의해 출력 P를 생성하는 합산부를 포함하는 것을 특징으로 하는 FCSR을 이용한 비선형 이진 난수 발생기.
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.
상기 FCSR은,
상기 메모리부의 선두를 0 또는 1로 초기화하고, 상기 합산부를 통하여 이하의 수식에 의해 정수합을 구하며,
최하위 비트 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,
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.
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)
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 |
-
2011
- 2011-07-29 KR KR1020110075988A patent/KR20130014003A/en not_active Application Discontinuation
Cited By (4)
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 |