【０００１】[0001]
【発明の属する技術分野】本発明は、簡易な構成でかつ
暗号に使用しても安全な乱数生成装置及び方法、その疑
似乱数生成器を用いた暗号化装置及び方法、復号装置及
び方法、並びにストリーム暗号システムに関する。BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an apparatus and method for generating a random number which has a simple configuration and is safe to use for encryption, an apparatus and method for encryption using the pseudo-random number generator, an apparatus and method for decryption, and Related to stream cipher systems.
【０００２】[0002]
【従来の技術】現在、暗号方式として様々なものが知ら
れているが、その１つに加算型ストリーム暗号がある。
加算型ストリーム暗号は、良く知られているように、暗
号側と復号側で同一または同一の論理構造の疑似乱数生
成器を持ち、暗号側では平文メッセージと共通鍵にて示
される初期状態にセットされた疑似乱数生成器から出力
される乱数系列（鍵系列）とをビット単位に足し込む
（排他的論理和が良く用いられる）ことで暗号化を行
い、復号側ではこの暗号化されたメッセージを入力とし
て暗号側と同一の手順を実行することにより復号化を行
うものである。2. Description of the Related Art At present, various encryption methods are known, and one of them is an addition type stream encryption.
As is well known, the addition type stream cipher has a pseudo-random number generator having the same or the same logical structure on the encryption side and the decryption side, and sets the encryption side to an initial state indicated by a plaintext message and a common key. The random number sequence (key sequence) output from the generated pseudo random number generator is added in bit units (exclusive OR is often used) to perform encryption, and the decryption side encrypts the encrypted message. The decryption is performed by executing the same procedure as the encryption side as an input.
【０００３】このような加算型ストリーム暗号のなかで
も、Ｍ系列を出力する線形フィードバックシフトレジス
タを疑似乱数生成器として利用する構成は、装置規模が
小さくなることもあり、良く用いられている。図１３に
線形フィードバックシフトレジスタの原理図を示す。図
中のＣ1 〜Ｃn は予め０または１に定められ、ｎ段のシ
フトレジスタＳi-k の値のうちＣk ＝１であるものの排
他的論理和が出力Ｓiになり、シフト動作においてこの
Ｓi がフィードバックされる。また、線形フィードバッ
クシフトレジスタをセットする初期状態が共通鍵とな
る。[0003] Among such addition type stream ciphers, a configuration in which a linear feedback shift register that outputs an M-sequence is used as a pseudo-random number generator is often used because the device scale can be reduced. FIG. 13 shows a principle diagram of the linear feedback shift register. In the figure, C1 to Cn are previously set to 0 or 1, and the exclusive OR of the value of Ck = 1 among the values of the n-stage shift register Sik becomes the output Si.Si is fed back. The initial state of setting the linear feedback shift register is a common key.
【０００４】しかしながら、線形フィードバックシフト
レジスタ自体は、レジスタ長の２倍の出力を観測するこ
とで、その構造と初期状態のすべてを特定することが可
能なので、加算型ストリーム暗号に用いる疑似乱数生成
器としては、安全性に関して問題がある。また、線形フ
ィードバックレジスタを疑似乱数生成器として用いるた
めに、レジスタ長を長くして安全性を高めようとするこ
とは、装置規模の点から問題がある。However, the linear feedback shift register itself can specify all of its structure and initial state by observing the output twice as long as the register length. As such, there is a problem with regard to safety. Further, in order to use the linear feedback register as a pseudo-random number generator, increasing the register length to enhance security has a problem in terms of the device scale.
【０００５】そこで、複数の線形フィードバックシフト
レジスタの出力を非線形コンバイナで結合する手法や、
線形フィードバックシフトレジスタの出力に非線形変換
を施す手法等が開発されている（例えば文献１「暗号理
論入門」、共立出版株式会社、岡本栄司著、１９９３年
発行などに詳しい）。Therefore, a method of combining the outputs of a plurality of linear feedback shift registers with a nonlinear combiner,
A method of performing non-linear conversion on the output of the linear feedback shift register has been developed (for example, see Reference 1 "Introduction to Cryptography", Kyoritsu Shuppan Co., Ltd., Eiji Okamoto, published in 1993).
【０００６】しかし、複数の線形フィードバックシフト
レジスタの出力を非線形コンバイナで結合する方式で
は、線形複雑度はたかだか各線形フィードバックシフト
レジスタのレジスタ長の積程度にしかならない。However, in a system in which the outputs of a plurality of linear feedback shift registers are combined by a non-linear combiner, the linear complexity is at most about the product of the register lengths of the respective linear feedback shift registers.
【０００７】ここで、線形複雑度は、疑似乱数生成器の
解読しずらさ、すなわち暗号学的な安全性を計るための
尺度として用いられる指標で、「ある初期値から始めれ
ば同じ出力と同じ周期をもつという意味で等価な線形フ
ィードバックシフトレジスタのレジスタ長」と定義され
る（文献１参照）。[0007] Here, the linear complexity is an index used as a measure for measuring the difficulty of deciphering a pseudo-random number generator, that is, a measure of cryptographic security. (Equivalent to the register length of the linear feedback shift register) (see Document 1).
【０００８】そこで、装置規模に比して線形複雑度が大
きくなる疑似乱数生成器があれば、経済的にも安全性の
観点からも非常に都合が良い。そのような疑似乱数生成
器の候補として、加算ジェネレータ（ｓｕｍｍａｔｉｏ
ｎ ｇｅｎｅｒａｔｏｒ；例えば文献２“ＡＰＰＬＩＤ
Ｅ ＣＲＹＰＴＯＧＲＡＰＨＹ”、Ｊｏｈｎ Ｗｉｌｅ
ｙ ＆ Ｓｏｎｓ，Ｉｎｃ．社、１９９６年発行、ｐ
ｐ．３８６〜３８７に詳しい）が提案された。図１４に
加算ジェネレータの一例を示す。この場合、シフトレジ
スタｂ1 とｂ2 とキャリアの和を２で割った剰余をシフ
トレジスタにフィードバックするとともに、ｂ1 とｂ2
とキャリアの和を２で割った商を新たなキャリアとして
保持する動作を繰り返す。Therefore, if there is a pseudorandom number generator whose linear complexity is larger than the scale of the apparatus, it is very convenient from the viewpoint of economy and security. As a candidate of such a pseudo-random number generator, an addition generator (summatio
n generator; for example, Reference 2 “APPLID
E CRYPTOGRAPHY ", John Wile
y & Sons, Inc. Sha, published in 1996, p
p. 386-387). FIG. 14 shows an example of the addition generator. In this case, the remainder obtained by dividing the sum of the shift registers b1 and b2 and the carrier by 2 is fed back to the shift register, and b1 and b2
The operation of holding the quotient obtained by dividing the sum of the data and the carrier by 2 as a new carrier is repeated.
【０００９】ところが、加算ジェネレータの線形複雑度
は線形フィードバックシフトレジスタのレジスタ長の指
数程度となることが知られているが、加算ジェネレータ
は既に解読されており、加算型ストリーム暗号に用いる
疑似乱数生成器としては、安全性に関して問題がある。However, it is known that the linear complexity of the addition generator is approximately equal to the exponent of the register length of the linear feedback shift register. As a container, there is a problem with respect to safety.
【００１０】[0010]
【発明が解決しようとする課題】以上説明したように、
従来、小さな装置規模で安全性の高いストリーム暗号を
実現し得る線形複雑度の大きな乱数生成装置は知られて
いなかった。本発明は、上記事情を考慮してなされたも
ので、装置規模に比して線形複雑度が大きく暗号的にも
安全な乱数生成装置及び方法、暗号化装置及び方法、復
号装置及び方法、並びにストリーム暗号システムを提供
することを目的とする。As described above,
Heretofore, there has been no known random number generation device having a large linear complexity that can realize a highly secure stream cipher with a small device scale. The present invention has been made in view of the above circumstances, and has a large linear complexity as compared to the device scale, and a cryptographically secure random number generation device and method, an encryption device and method, a decryption device and method, and It is an object to provide a stream cipher system.
【００１１】[0011]
【課題を解決するための手段】本発明（請求項１）に係
る乱数生成装置は、所定の初期状態をもとに第１の乱数
系列を生成する第１の乱数生成手段と、所定の初期状態
をもとに第２の乱数系列を生成する第２の乱数生成手段
と、生成された前記第１の乱数系列を、生成された前記
第２の乱数系列に基づいて順序変更する変換手段とを備
えたことを特徴とする。A random number generation device according to the present invention (claim 1) includes: a first random number generation means for generating a first random number sequence based on a predetermined initial state; Second random number generation means for generating a second random number sequence based on the state, and conversion means for changing the order of the generated first random number sequence based on the generated second random number sequence; It is characterized by having.
【００１２】本発明（請求項２）に係る乱数生成装置
は、所定の初期状態をもとに第１の乱数系列を所定のビ
ット長単位に生成する第１の線形フィードバックシフト
レジスタと、所定の初期状態をもとに第２の乱数系列を
所定のビット長単位に生成する第２の線形フィードバッ
クシフトレジスタと、前記第２の線形フィードバックシ
フトレジスタから与えられた前記所定のビット長の乱数
にて示されるアドレスに格納されている内容を出力した
後に、該アドレスに前記第１の線形フィードバックシフ
トレジスタから与えられた前記所定のビット長の乱数を
格納する記憶装置とを備えたことを特徴とする。[0012] A random number generation device according to the present invention (Claim 2) comprises: a first linear feedback shift register for generating a first random number sequence in predetermined bit length units based on a predetermined initial state; A second linear feedback shift register for generating a second random number sequence in predetermined bit length units based on the initial state, and a random number having the predetermined bit length given from the second linear feedback shift register After outputting the content stored at the indicated address, storing the random number having the predetermined bit length given from the first linear feedback shift register at the address. .
【００１３】なお、１つの線形フィードバックシフトレ
ジスタのみ設け、これを第１の線形フィードバックシフ
トレジスタおよび第２の線形フィードバックシフトレジ
スタとして用いても良い。It is to be noted that only one linear feedback shift register may be provided and used as the first linear feedback shift register and the second linear feedback shift register.
【００１４】また、一部または全部の線形フィードバッ
クシフトレジスタを、他の公知の乱数生成器に置き換え
ても良い。本発明（請求項３）に係る乱数生成装置は、
所定の初期状態をもとに２値乱数を順次出力する第１の
線形フィードバックシフトレジスタと、所定の初期状態
をもとに２値乱数を順次出力する第２の線形フィードバ
ックシフトレジスタと、前記第２の線形フィードバック
シフトレジスタから与えられた所定のビット長の乱数に
て示されるアドレスに格納されている内容を出力した後
に、該アドレスに前記第１の線形フィードバックシフト
レジスタから与えられた所定のビット長の乱数を格納す
る第１の記憶装置と、前記第１の線形フィードバックシ
フトレジスタから与えられた所定のビット長の乱数にて
示されるアドレスに格納されている内容を出力した後
に、該アドレスに前記第２の線形フィードバックシフト
レジスタから与えられた所定のビット長の乱数を格納す
る第２の記憶装置と、前記第１の記憶装置から出力され
た所定のビット長の乱数と前記第２の記憶装置から出力
された所定のビット長の乱数とを入力とする非線形変換
処理を行って所定のビット長の乱数を生成して出力する
非線形コンバイナとを備えたことを特徴とする。Further, some or all of the linear feedback shift registers may be replaced with other known random number generators. The random number generation device according to the present invention (claim 3)
A first linear feedback shift register that sequentially outputs binary random numbers based on a predetermined initial state, a second linear feedback shift register that sequentially outputs binary random numbers based on a predetermined initial state, After outputting the content stored in the address indicated by the random number having the predetermined bit length given from the second linear feedback shift register, the predetermined bit given from the first linear feedback shift register is stored in the address. A first storage device for storing a long random number, and after outputting the content stored at the address indicated by the random number having a predetermined bit length given from the first linear feedback shift register, A second storage device for storing a random number having a predetermined bit length given from the second linear feedback shift register; A non-linear conversion process is performed using a random number of a predetermined bit length output from the first storage device and a random number of a predetermined bit length output from the second storage device as input, and the random number of a predetermined bit length is performed. And a non-linear combiner for generating and outputting the same.
【００１５】なお、第１の線形フィードバックシフトレ
ジスタを記憶装置に格納するデータ用と記憶装置に与え
るアドレス用で共用する代わりに、データ専用とアドレ
ス専用の２つの線形フィードバックシフトレジスタを設
けても良い。同様に、第２の線形フィードバックシフト
レジスタも共用する代わりに、データ専用とアドレス専
用の２つの線形フィードバックシフトレジスタを設けて
も良い。Note that instead of sharing the first linear feedback shift register for data stored in the storage device and for the address given to the storage device, two linear feedback shift registers dedicated to data and dedicated to addresses may be provided. . Similarly, instead of sharing the second linear feedback shift register, two linear feedback shift registers dedicated to data and addresses may be provided.
【００１６】また、一部または全部の線形フィードバッ
クシフトレジスタを、他の公知の乱数生成器に置き換え
ても良い。本発明に係る乱数生成装置における一部また
は全部の線形フィードバックシフトレジスタを、本発明
に係る乱数生成装置自体で置き換えても良い。この置き
換えは、何階層に渡って行っても良い。Further, some or all of the linear feedback shift registers may be replaced by another known random number generator. Some or all of the linear feedback shift registers in the random number generation device according to the present invention may be replaced with the random number generation device itself according to the present invention. This replacement may be performed over any number of layers.
【００１７】本発明（請求項４）に係る乱数生成方法
は、所定の初期状態をもとに生成した第１の乱数系列
を、所定の初期状態をもとに生成した第２の乱数系列に
基づいて順序変更して出力することを特徴とする。In the random number generation method according to the present invention (claim 4), a first random number sequence generated based on a predetermined initial state is converted to a second random number sequence generated based on a predetermined initial state. It is characterized by changing the order based on the output.
【００１８】本発明（請求項５）に係る乱数生成方法
は、所定の初期状態をもとに第１の乱数系列を生成する
第１の線形フィードバックシフトレジスタにより所定の
ビット長の乱数を所定個数生成し、生成された前記乱数
夫々を、記憶装置の各アドレスの内容として格納し、所
定の初期状態をもとに第２の乱数系列を生成する第２の
線形フィードバックシフトレジスタにより生成された所
定のビット長の乱数にて示される前記記憶装置のアドレ
スに格納されている内容を乱数として出力し、この内容
を出力された前記記憶装置のアドレスに、前記第１の線
形フィードバックシフトレジスタにより生成された所定
のビット長の乱数を格納し、以降、前記記憶装置から出
力された乱数系列が所定の長さに達するまで、前記記憶
装置からの乱数の出力と前記記憶装置への乱数の格納を
繰り返し実行することを特徴とする。According to a fifth aspect of the present invention, there is provided a random number generating method according to the first aspect, wherein a first linear feedback shift register for generating a first random number sequence based on a predetermined initial state is used to generate a predetermined number of random numbers having a predetermined bit length. Each of the generated random numbers is stored as the contents of each address of the storage device, and the predetermined random number is generated by a second linear feedback shift register that generates a second random number sequence based on a predetermined initial state. The content stored at the address of the storage device indicated by a random number having a bit length of is output as a random number, and the content is generated by the first linear feedback shift register at the output address of the storage device. The random number having a predetermined bit length is stored, and thereafter, the random number is output from the storage device until the random number sequence output from the storage device reaches a predetermined length. Characterized by a run repeatedly stored random number to the storage device.
【００１９】本発明（請求項６）に係る乱数生成方法
は、所定の初期状態をもとに第１の乱数系列を生成する
第１の線形フィードバックシフトレジスタにより所定の
ビット長の乱数を所定個数生成し、生成された前記乱数
夫々を、第１の記憶装置の各アドレスの内容として格納
するとともに、所定の初期状態をもとに第２の乱数系列
を生成する第２の線形フィードバックシフトレジスタに
より所定のビット長の乱数を所定個数生成し、生成され
た前記乱数夫々を、第２の記憶装置の各アドレスの内容
として格納し、前記第２の線形フィードバックシフトレ
ジスタにより生成された所定のビット長の乱数にて示さ
れる前記第１の記憶装置のアドレスに格納されている内
容を出力して２入力１出力の非線形コンバイナに与える
とともに、前記第１の線形フィードバックシフトレジス
タにより生成された所定のビット長の乱数にて示される
前記第２の記憶装置のアドレスに格納されている内容を
出力して前記非線形コンバイナに与え、この非線形コン
バイナにより非線形変換処理を行って所定のビット長の
乱数を生成して出力し、前記第１の記憶装置の前記内容
の出力されたアドレスに、前記第１の線形フィードバッ
クシフトレジスタにより生成された所定のビット長の乱
数を格納するとともに、前記第２の記憶装置の前記内容
の出力されたアドレスに、前記第２の線形フィードバッ
クシフトレジスタにより生成された所定のビット長の乱
数を格納し、以降、前記非線形コンバイナから出力され
た乱数系列が所定の長さに達するまで、前記第１および
第２の記憶装置からの乱数の出力をもとにした非線形変
換処理と前記第１および第２の記憶装置への乱数の格納
を繰り返し実行することを特徴とする。According to the random number generation method of the present invention (claim 6), a first linear feedback shift register for generating a first random number sequence based on a predetermined initial state allows a predetermined number of random numbers of a predetermined bit length to be generated. Each of the generated random numbers is stored as the content of each address in the first storage device, and is generated by a second linear feedback shift register that generates a second random number sequence based on a predetermined initial state. A predetermined number of random numbers having a predetermined bit length are generated, and each of the generated random numbers is stored as the contents of each address of the second storage device, and the predetermined bit length generated by the second linear feedback shift register is generated. The content stored at the address of the first storage device indicated by the random number is output to be given to the two-input one-output nonlinear combiner, and the first The content stored in the address of the second storage device indicated by the random number having a predetermined bit length generated by the linear feedback shift register is output and given to the nonlinear combiner, and the nonlinear combiner performs nonlinear conversion processing. Then, a random number having a predetermined bit length is generated and output, and the random number having a predetermined bit length generated by the first linear feedback shift register is added to the output address of the content in the first storage device. At the same time, the random number having a predetermined bit length generated by the second linear feedback shift register is stored at the output address of the content in the second storage device, and thereafter, the random number is output from the nonlinear combiner. Until the random number sequence reaches a predetermined length, the output of the random numbers from the first and second storage devices is also performed. Characterized by non-linear transformation processing and repeatedly stored random number to said first and second storage device execute you.
【００２０】本発明（請求項７）に係る暗号処理装置
は、共通鍵により与えられる所定の初期状態をもとに生
成した第１の乱数系列を、共通鍵により与えられる所定
の初期状態をもとに生成した第２の乱数系列に基づいて
順序変更して、鍵系列として出力する乱数生成手段と、
平文および暗号文の一方の２値系列と前記鍵系列とをも
とに予め定められた論理演算を行って平文および暗号文
の他方の２値系列を生成する論理演算手段とを備えたこ
とを特徴とする。The cryptographic processing device according to the present invention (claim 7) converts the first random number sequence generated based on the predetermined initial state given by the common key to the predetermined initial state given by the common key. And a random number generating means for changing the order based on the second random number sequence generated and outputting as a key sequence;
A logical operation means for performing a predetermined logical operation based on one of the binary sequence of the plaintext and the ciphertext and the key sequence to generate the other binary sequence of the plaintext and the ciphertext. Features.
【００２１】本発明（請求項９）に係る暗号処理方法
は、共通鍵により与えられる所定の初期状態をもとに生
成した第１の乱数系列を、共通鍵により与えられる所定
の初期状態をもとに生成した第２の乱数系列に基づいて
順序変更して、鍵系列として出力し、平文および暗号文
の一方の２値系列と前記鍵系列とをもとに予め定められ
た論理演算を行って平文および暗号文の他方の２値系列
を生成することを特徴とする。[0021] In the encryption processing method according to the present invention (claim 9), a first random number sequence generated based on a predetermined initial state given by a common key is also converted to a predetermined initial state given by a common key. The order is changed based on the second random number sequence generated as above, output as a key sequence, and a predetermined logical operation is performed based on the binary sequence of one of plaintext and ciphertext and the key sequence. And generating the other binary sequence of the plaintext and the ciphertext.
【００２２】本発明（請求項１０）に係る暗号化装置
は、共通鍵により与えられる所定の初期状態をもとに生
成した第１の乱数系列を、共通鍵により与えられる所定
の初期状態をもとに生成した第２の乱数系列に基づいて
順序変更して、鍵系列として出力する乱数生成手段と、
平文の２値系列と前記鍵系列とをもとに予め定められた
論理演算を行って暗号文の２値系列を生成する論理演算
手段とを備えたことを特徴とする。[0022] The encryption device according to the present invention (claim 10) converts the first random number sequence generated based on the predetermined initial state given by the common key to the predetermined initial state given by the common key. And a random number generating means for changing the order based on the second random number sequence generated and outputting as a key sequence;
A logical operation means for performing a predetermined logical operation based on the binary sequence of the plaintext and the key sequence to generate a binary sequence of the ciphertext.
【００２３】本発明（請求項１１）に係る暗号化方法
は、共通鍵により与えられる所定の初期状態をもとに生
成した第１の乱数系列を、共通鍵により与えられる所定
の初期状態をもとに生成した第２の乱数系列に基づいて
順序変更して、鍵系列として出力し、平文の２値系列と
前記鍵系列とをもとに予め定められた論理演算を行って
暗号文の２値系列を生成することを特徴とする。[0023] In the encryption method according to the present invention (claim 11), the first random number sequence generated based on the predetermined initial state given by the common key may be converted to the predetermined initial state given by the common key. The order is changed based on the second random number sequence generated as above, is output as a key sequence, and a predetermined logical operation is performed based on the binary sequence of the plaintext and the key sequence to perform the encryption of the ciphertext. It is characterized by generating a value series.
【００２４】本発明（請求項１２）に係る復号装置は、
共通鍵により与えられる所定の初期状態をもとに生成し
た第１の乱数系列を、共通鍵により与えられる所定の初
期状態をもとに生成した第２の乱数系列に基づいて順序
変更して、鍵系列として出力する乱数生成手段と、暗号
文の２値系列と前記鍵系列とをもとに予め定められた論
理演算を行ってもとの平文の２値系列を生成する論理演
算手段とを備えたことを特徴とする。The decoding device according to the present invention (claim 12)
Changing the order of a first random number sequence generated based on a predetermined initial state given by a common key based on a second random number sequence generated based on a predetermined initial state given by a common key; Random number generating means for outputting as a key sequence, and logical operation means for generating a binary sequence of the original plain text by performing a predetermined logical operation based on the binary sequence of the cipher text and the key sequence. It is characterized by having.
【００２５】本発明（請求項１３）に係る復号方法は、
共通鍵により与えられる所定の初期状態をもとに生成し
た第１の乱数系列を、共通鍵により与えられる所定の初
期状態をもとに生成した第２の乱数系列に基づいて順序
変更して、鍵系列として出力し、暗号文の２値系列と前
記鍵系列とをもとに予め定められた論理演算を行っても
との平文の２値系列を生成することを特徴とする。The decoding method according to the present invention (claim 13)
Changing the order of a first random number sequence generated based on a predetermined initial state given by a common key based on a second random number sequence generated based on a predetermined initial state given by a common key; A key sequence is output, and a binary sequence of the original plaintext is generated by performing a predetermined logical operation based on the binary sequence of the ciphertext and the key sequence.
【００２６】本発明（請求項１４）は、所定の共通鍵を
もとに平文を暗号文に変換する暗号化装置と該所定の共
通鍵をもとに暗号文をもとの平文に変換する復号装置と
該暗号化装置から該復号装置へ暗号文を伝える所定の媒
体とを備えたストリーム暗号システムにおいて、前記暗
号化装置は、共通鍵により与えられる所定の初期状態を
もとに生成した第１の乱数系列を、共通鍵により与えら
れる所定の初期状態をもとに生成した第２の乱数系列に
基づいて順序変更して、鍵系列として出力する乱数生成
手段と、平文の２値系列と前記鍵系列とをもとに予め定
められた論理演算を行って暗号文の２値系列を生成する
論理演算手段とを備え、前記復号装置は、共通鍵により
与えられる所定の初期状態をもとに生成した第１の乱数
系列を、共通鍵により与えられる所定の初期状態をもと
に生成した第２の乱数系列に基づいて順序変更して、鍵
系列として出力する、前記乱数生成手段と同一の論理構
造を持つ乱数生成手段と、暗号文の２値系列と前記鍵系
列とをもとに前記論理演算と同一の論理演算を行っても
との平文の２値系列を生成する論理演算手段とを備えた
ことを特徴とする。According to the present invention (claim 14), an encryption device for converting a plaintext into a ciphertext based on a predetermined common key and a ciphertext based on the predetermined common key are converted into the original plaintext. In a stream cipher system including a decryption device and a predetermined medium for transmitting a ciphertext from the encryption device to the decryption device, the encryption device generates a second encryption key based on a predetermined initial state given by a common key. A random number generating means for changing the order of one random number sequence based on a second random number sequence generated based on a predetermined initial state given by a common key and outputting the same as a key sequence; Logical operation means for performing a predetermined logical operation on the basis of the key sequence to generate a binary sequence of ciphertexts, wherein the decryption device is configured to execute a predetermined initial state given by a common key. The first random number sequence generated in Random number generation means having the same logical structure as the random number generation means, which changes the order based on a second random number sequence generated based on a given initial state given and outputs the key sequence; A logical operation means for generating the original plaintext binary sequence by performing the same logical operation as the logical operation based on the binary sequence and the key sequence.
【００２７】本発明（請求項１５）は、一方の処理装置
にて所定の共通鍵をもとに平文を暗号文に変換し、該暗
号文を所定の媒体に出力し、他方の処理装置にて該暗号
文を該所定の媒体を通じて入力し、該所定の共通鍵をも
とに暗号文をもとの平文に変換するストリーム暗号シス
テムにおいて、前記処理装置は、共通鍵により与えられ
る所定の初期状態をもとに生成した第１の乱数系列を、
共通鍵により与えられる所定の初期状態をもとに生成し
た第２の乱数系列に基づいて順序変更して、鍵系列とし
て出力する乱数生成手段と、平文および暗号文の一方の
２値系列と前記鍵系列とをもとに予め定められた論理演
算を行って平文および暗号文の他方の２値系列を生成す
る論理演算手段とを備えたことを特徴とする。According to the present invention (claim 15), one processing device converts a plaintext into a ciphertext based on a predetermined common key, outputs the ciphertext to a predetermined medium, and outputs the ciphertext to the other processing device. In the stream cipher system for inputting the ciphertext through the predetermined medium and converting the ciphertext into the original plaintext based on the predetermined common key, the processing device includes a predetermined initial value given by the common key. The first random number sequence generated based on the state is
Random number generation means for changing the order based on a second random number sequence generated based on a predetermined initial state given by a common key and outputting the sequence as a key sequence, and a binary sequence of one of plaintext and ciphertext; A logical operation means for performing a predetermined logical operation based on the key sequence to generate the other binary sequence of the plaintext and the ciphertext.
【００２８】本発明における論理演算は、例えば、ビッ
ト単位の排他的論理和演算である。なお、本発明の暗号
処理、暗号装置、復号装置の乱数生成手段には、請求項
２の乱数生成装置や請求項３の乱数生成装置や上述した
ようにこれらを変形したものを適用することもできる。The logical operation in the present invention is, for example, an exclusive OR operation in bit units. Note that the random number generation means of the encryption processing, encryption device, and decryption device of the present invention may employ the random number generation device of claim 2, the random number generation device of claim 3, or a modified version of these. it can.
【００２９】本発明では、記憶装置を緩衝域として用
い、第１の線形フィードバックシフトレジスタＡの出力
を該記憶装置のアドレスとして入力し、該アドレスに記
憶されている内容を乱数として出力し、該アドレスに第
２の線形フィードバックシフトレジスタＢの出力をデー
タ入力として記憶することで、線形複雑度の大きな乱数
生成装置を実現することができる。In the present invention, the storage device is used as a buffer area, the output of the first linear feedback shift register A is input as the address of the storage device, and the content stored at the address is output as a random number. By storing the output of the second linear feedback shift register B as the data input at the address, it is possible to realize a random number generation device having high linear complexity.
【００３０】線形フィードバックシフトレジスタＡとＢ
のレジスタ長を各々ＬＡ，ＬＢとする。請求項２等に係
る発明のように記憶装置を緩衝域として用いる乱数生成
装置での線形複雑度は、ほぼＬＡ×２LBである。Linear feedback shift registers A and B
Are LA and LB, respectively. The linear complexity of the random number generation device using the storage device as a buffer area as in the invention according to claim 2 is approximately LA × 2LB.
【００３１】請求項３等に係る発明の２つの記憶装置を
互いの緩衝域として用いる乱数生成器での線形複雑度
は、ほぼ２LA×２LBである。また、乱数生成装置を用い
るストリーム暗号では、暗号の解読しずらさという意味
での安全性を計るための尺度として、線形複雑度が用い
られる。つまり、線形装置規模に比して線形複雑度が大
きいことは、安価に安全な暗号装置を構築できることを
意味する。The linear complexity of the random number generator using the two storage devices according to the third aspect of the present invention as a buffer for each other is approximately 2LA × 2LB. In a stream cipher using a random number generation device, linear complexity is used as a measure for measuring security in terms of the difficulty of decrypting the cipher. That is, the fact that the linear complexity is larger than the linear device scale means that a secure cryptographic device can be constructed at low cost.
【００３２】このように本発明によれば、少ない装置規
模で大きな線形複雑度を達成できるので、経済的に安全
な暗号を実現できる。なお、上記の発明は、相当する手
順あるいは手段をコンピュータに実行させるためのプロ
グラムを記録した機械読取り可能な媒体としても成立す
る。As described above, according to the present invention, a large linear complexity can be achieved with a small device scale, so that an economically secure encryption can be realized. The above-described invention is also realized as a machine-readable medium storing a program for causing a computer to execute the corresponding procedure or means.
【００３３】[0033]
【発明の実施の形態】以下、図面を参照しながら発明の
実施の形態を説明する。本発明に係る乱数生成装置およ
び方法は、装置規模に比して大きな線形複雑度を得るこ
とができるものであり、もちろん乱数を必要とする種々
の分野に適用可能であるが、特に、統計的性質だけでな
く予測可能性、端的に言えばアタックに対する安全性を
も問題とされる暗号、中でもストリーム暗号に好適なも
のである。Embodiments of the present invention will be described below with reference to the drawings. INDUSTRIAL APPLICABILITY The random number generation device and method according to the present invention can obtain a large linear complexity in comparison with the device scale, and can be applied to various fields that require random numbers. It is suitable for a cipher in which not only its properties but also its predictability, in short, security against attacks, are important, especially a stream cipher.
【００３４】最初に、本発明の乱数生成装置および方法
の基本的な考え方について説明する。図１に、本発明の
一実施形態に係る乱数生成装置の構成を示す。First, the basic concept of the random number generation device and method of the present invention will be described. FIG. 1 shows a configuration of a random number generation device according to an embodiment of the present invention.
【００３５】本乱数生成装置は、第１の乱数生成部２
と、第２の乱数生成部４と、乱数変換部６を備えてい
る。第１の乱数生成部２は、初期状態にセットされた
後、乱数系列（２値系列）ａを生成し出力していく。The present random number generation device includes a first random number generation unit 2
And a second random number generation unit 4 and a random number conversion unit 6. After being set to the initial state, the first random number generation unit 2 generates and outputs a random number sequence (binary sequence) a.
【００３６】同様に、第２の乱数生成部４は、初期状態
にセットされた後、乱数系列（２値系列）ｂを生成し出
力していく。なお、第１の乱数生成部２は、初期状態が
同一であれば、同一の乱数系列を生成する。第２の乱数
生成部４についても同様である。また、第１の乱数生成
部２や第２の乱数生成部４についての初期状態とは、例
えば内部変数あるいは各レジスタの保持する値の初期値
群であり、例えば線形フィードバックシフトレジスタに
おける各シフトレジスタの保持する初期値の組がこれに
該当する。Similarly, after being set to the initial state, the second random number generation section 4 generates and outputs a random number sequence (binary sequence) b. Note that the first random number generation unit 2 generates the same random number sequence if the initial states are the same. The same applies to the second random number generation unit 4. The initial state of the first random number generation unit 2 and the second random number generation unit 4 is, for example, an internal variable or an initial value group of values held in each register, and for example, each shift register in a linear feedback shift register. Corresponds to this.
【００３７】また、第１の乱数生成部２の初期状態と第
２の乱数生成部４の初期状態は独立のものであるが、第
１の乱数生成部２と第２の乱数生成部４が同様の構成の
場合に同一のものを使用しても構わない。Although the initial state of the first random number generator 2 and the initial state of the second random number generator 4 are independent, the first random number generator 2 and the second random number generator 4 In the case of a similar configuration, the same one may be used.
【００３８】乱数変換部６は、入力された２値系列の順
序を、別に入力された２値系列に基づいて入れ替えて出
力する。また、２値系列の順序の入れ替えは、連続する
所定のビット数（１ビットの場合を含む）を一纏まりと
して行われる。[0038] The random number conversion unit 6 rearranges the order of the input binary sequence based on the separately input binary sequence, and outputs it. In addition, the order of the binary sequence is interchanged with a predetermined number of consecutive bits (including the case of one bit).
【００３９】入れ替えの方法は、乱数変換部６は、入力
された２値系列ａの順序を、別に入力された２値系列ｂ
に基づいて入れ替えて出力する。２値系列ａの順序の入
れ替えは、連続する所定のビット数（１ビットの場合を
含む）を一纏まりとして行われる。例えば、連続する６
４ビットを一纏まりとする。The random number conversion unit 6 changes the order of the input binary sequence a to the binary sequence b
Output based on. The order of the binary sequence a is interchanged with a predetermined number of consecutive bits (including the case of one bit). For example, 6 consecutive
The four bits are grouped together.
【００４０】２値系列ａの順序の入れ替えの方法は、例
えば、上記の別に入力された２値系列ｂを連続するｎビ
ット（例えば８ビット）ごとに区切って得た２進数ｎビ
ットの情報の系列に従って、２値系列ａ中のある位置の
一纏まりを他の位置（結果的に同じ位置になる場合を含
む）に移す。The method of changing the order of the binary sequence a is, for example, a method of converting n-bit binary information obtained by dividing the separately input binary sequence b into continuous n bits (for example, 8 bits). According to the sequence, a group of a certain position in the binary sequence a is moved to another position (including a case where the same position results).
【００４１】２値系列ａが同一でも、２値系列ｂが相違
すれば、乱数変換部６の出力として得られる乱数系列は
相違するものとなる。また、第１の乱数生成部２の初期
状態と第２の乱数生成部４の初期状態の組が同一であれ
ば、乱数変換部６の出力として得られる乱数系列は同一
になる。Even if the binary sequence a is the same, if the binary sequence b is different, the random number sequence obtained as the output of the random number converter 6 will be different. If the set of the initial state of the first random number generation unit 2 and the initial state of the second random number generation unit 4 are the same, the random number sequence obtained as the output of the random number conversion unit 6 will be the same.
【００４２】詳しくは後述するが、この乱数変換部６
は、例えばＲＡＭなどの記憶装置を用いることにより実
現することが可能である。図１において、第１の乱数生
成部２から出力された乱数系列ａが乱数変換部６に入力
され、乱数変換部６では第２の乱数生成部４から出力さ
れた乱数系列ｂに基づいた手順または動作で、第１の乱
数生成部２から出力された乱数系列ａの順序を入れ替え
て出力する。As will be described in detail later, the random number conversion unit 6
Can be realized by using a storage device such as a RAM. In FIG. 1, a random number sequence a output from a first random number generation unit 2 is input to a random number conversion unit 6, and the random number conversion unit 6 performs a procedure based on the random number sequence b output from the second random number generation unit 4. Alternatively, in operation, the order of the random number sequence a output from the first random number generation unit 2 is changed and output.
【００４３】例えば、乱数系列ａがａ1 ，ａ2 ，ａ3 ，
ａ4 ，ａ5 ，ａ6 ，ａ7 ，ａ8 ，…（ａi は０または
１）で、乱数変換部６は連続する２ビットを一纏まりと
して順序の入れ替えを行う場合、乱数変換部６から出力
される乱数系列は、乱数系列ｂの内容に応じて、ａ3 ，
ａ4 ，ａ7 ，ａ8 ，ａ1 ，ａ2 ，…、あるいはａ5 ，ａ
6 ，ａ1 ，ａ2 ，ａ7 ，ａ8 ，…などとなる。For example, if the random number sequence a is a1 , a2 , a3 ,
a4 , a5 , a6 , a7 , a8 ,... (ai is 0 or 1), and the random number conversion unit 6 Are output according to the contents of the random number sequence b, a3 ,
a 4, a 7, a 8 , a 1, a 2, ..., or a5, a
6, a 1, a 2, a 7, a 8, ... and so on.
【００４４】なお、図１の乱数生成装置の他の例とし
て、第１の乱数生成部２と第２の乱数生成部４とを１つ
に共通化しても良い。この場合、第１の乱数生成部２と
して所定のビット数の乱数を生成する動作と、第２の乱
数生成部４として所定のビット数の乱数を生成する動作
とを交互に行えば良い。言い換えると、この共通化され
た乱数生成装置から出力される乱数系列を、上記の２値
系列ａ用と２値系列ｂ用に交互に使えば良い。As another example of the random number generation device of FIG. 1, the first random number generation unit 2 and the second random number generation unit 4 may be shared by one. In this case, an operation of generating a random number of a predetermined number of bits as the first random number generation unit 2 and an operation of generating a random number of a predetermined number of bits as the second random number generation unit 4 may be performed alternately. In other words, the random number sequence output from the common random number generation device may be used alternately for the binary sequence a and the binary sequence b.
【００４５】また、図１の乱数生成装置のさらに他の例
として、図１の乱数生成装置における第１の乱数生成部
２および第２の乱数生成部４の少なくとも一方を、図１
の乱数生成装置自体で置き換えた構成にしても良い。Further, as still another example of the random number generation device of FIG. 1, at least one of the first random number generation unit 2 and the second random number generation unit 4 in the random number generation device of FIG.
May be replaced by the random number generation device itself.
【００４６】次に、本発明の乱数生成装置をストリーム
暗号に適用する場合について説明する。ストリーム暗号
では、暗号側において、平文メッセージ（２値系列）と
所定の共通鍵に基づいて生成された鍵系列（２値系列）
にビット単位の所定の論理演算（一般的には排他的論理
和演算）を施して暗号文を生成し、復号側において、暗
号文（２値系列）と所定の共通鍵（暗号側で使用した鍵
と同一のもの）に基づいて生成された暗号側と同一の鍵
系列にビット単位の所定の論理演算（暗号側で使用した
演算と同一のもの）を施してもとの平文メッセージを得
る。Next, a case where the random number generation device of the present invention is applied to a stream cipher will be described. In the stream cipher, a key sequence (binary sequence) generated based on a plaintext message (binary sequence) and a predetermined common key on the encryption side.
Is subjected to a predetermined logical operation (generally, an exclusive OR operation) on a bit basis to generate a ciphertext, and the ciphertext (binary sequence) and a predetermined common key (used on the cipher A plaintext message is obtained by performing a predetermined logical operation in bit units (the same operation as used on the encryption side) on the same key sequence as the encryption side generated based on the same key as the encryption side.
【００４７】このようなストリーム暗号において、上記
の鍵系列を生成する装置として、前述したまたは後述す
る本実施形態の乱数生成装置を用いると効果的である。
この場合、乱数生成装置の初期状態は、共通鍵として与
えられるようにする。In such a stream cipher, it is effective to use the above-described or later-described random number generation device of the present embodiment as a device for generating the key sequence.
In this case, the initial state of the random number generation device is given as a common key.
【００４８】図２に、本発明の乱数生成装置をストリー
ム暗号に適用した暗号システムの構成例を示す。暗号側
（例えばデータを伝える媒体に通信路を用いる場合の送
信側）の暗号装置には、本実施形態の乱数生成装置１０
ａと、論理演算処理装置１２ａが備えられている。FIG. 2 shows a configuration example of an encryption system in which the random number generation device of the present invention is applied to a stream cipher. The encryption device on the encryption side (for example, the transmission side when a communication path is used as a medium for transmitting data) includes the random number generation device 10 of the present embodiment.
a and a logical operation processing device 12a.
【００４９】同様に、復号側（例えばデータを伝える媒
体に通信路を用いる場合の受信側）の復号装置には、本
実施形態の乱数生成装置１０ｂと、論理演算処理装置１
２ｂが備えられている。Similarly, a decoding device on the decoding side (for example, a receiving side when a communication path is used as a medium for transmitting data) includes a random number generation device 10b of this embodiment and a logical operation processing device 1
2b is provided.
【００５０】乱数生成装置１０ａと乱数生成装置１０ｂ
とは同一または同一の論理構造を持つものであり、論理
演算処理装置１２ａと論理演算処理装置１２ｂとは同一
または等価なものである。なお、ここでは、論理演算処
理装置１２ａと論理演算処理装置１２ｂは、ビット単位
の排他的論理和演算を行うものとして説明する。The random number generator 10a and the random number generator 10b
Have the same or the same logical structure, and the logical operation processing device 12a and the logical operation processing device 12b are the same or equivalent. Here, the description is given on the assumption that the logical operation processing device 12a and the logical operation processing device 12b perform an exclusive OR operation on a bit basis.
【００５１】図２において、暗号側と復号側との間で
は、何らかの公知の方法で共通鍵を共有しているものと
する。この共通鍵により、乱数生成装置１０ａおよび１
１の初期状態が与えられる。共通鍵の内容は、乱数生成
装置１０ａおよび１１の初期状態そのものであっても良
いし、初期状態を特定可能な識別子でも良い。In FIG. 2, it is assumed that a common key is shared between the encryption side and the decryption side by any known method. With this common key, the random number generation devices 10a and 10a
An initial state of 1 is provided. The content of the common key may be the initial state itself of the random number generation devices 10a and 11 or an identifier capable of specifying the initial state.
【００５２】そして、暗号側では、暗号化したい平文メ
ッセージと、所定の共通鍵により与えられる初期状態を
もとにした乱数生成装置１０ａの生成する乱数系列との
排他的論理和を取って、平文メッセージを暗号文に変換
し、通信路等を介して暗号側に伝える。On the encryption side, an exclusive OR of the plaintext message to be encrypted and the random number sequence generated by the random number generation device 10a based on the initial state given by the predetermined common key is calculated, and the plaintext message is obtained. The message is converted into a ciphertext and transmitted to the cipher via a communication path or the like.
【００５３】暗号文を取得した復号側では、この暗号文
と、前記共通鍵により与えられる初期状態をもとにした
乱数生成器１０ｂの生成する乱数系列との排他的論理和
を取ることにより、もとの平文メッセージを復元する。On the decryption side that has obtained the cipher text, the cipher text and the random number sequence generated by the random number generator 10b based on the initial state given by the common key are exclusive-ORed to obtain Restore the original plaintext message.
【００５４】たとえ不正な盗聴者がたとえ暗号文を入手
したとしても、共通鍵を知らないので、平文を復元する
ことはできない。なお、暗号側から復号側に暗号文を渡
すための手段はどのようなものであっても構わない。例
えば、両者をネットワークで接続する方法、無線通信に
より暗号文を伝送する方法、暗号文を可搬できる記憶媒
体に格納して受け渡す方法など種々のものが考えられ
る。なお、これらに対応する機能部分は、図２において
は省略されている。Even if an unauthorized eavesdropper obtains the ciphertext, the plaintext cannot be restored because he does not know the common key. Note that any means may be used to pass the ciphertext from the encryption side to the decryption side. For example, various methods are conceivable, such as a method of connecting the both via a network, a method of transmitting ciphertext by wireless communication, and a method of storing and transferring ciphertext in a portable storage medium. Note that the functional parts corresponding to these are omitted in FIG.
【００５５】また、暗号装置と復号装置で行う処理は実
質的に同じであるので、実際には、計算機などの処理装
置は、暗号装置と復号装置の両方の機能を持つことがで
きる。Further, since the processes performed by the encryption device and the decryption device are substantially the same, a processing device such as a computer can actually have both functions of the encryption device and the decryption device.
【００５６】以下では、本発明の実施の形態に係る乱数
生成装置についてより詳しく説明していく。図３に、本
発明の一実施形態に係る乱数生成装置の構成を示す。ま
た、図４に、本乱数生成装置の動作の流れを示す。Hereinafter, the random number generation device according to the embodiment of the present invention will be described in more detail. FIG. 3 shows a configuration of a random number generation device according to an embodiment of the present invention. FIG. 4 shows a flow of the operation of the random number generation device.
【００５７】本乱数生成装置は、第１の線形フィードバ
ックシフトレジスタ２０、第２の線形フィードバックシ
フトレジスタ２２、記憶装置２４を備えている。第１の
線形フィードバックシフトレジスタ２０および第２の線
形フィードバックシフトレジスタ２２夫々の内部基本構
成は、既に説明した図１３と同様のものを用いることが
できる。This random number generation device includes a first linear feedback shift register 20, a second linear feedback shift register 22, and a storage device 24. The internal basic configuration of each of the first linear feedback shift register 20 and the second linear feedback shift register 22 may be the same as that described above with reference to FIG.
【００５８】第１の線形フィードバックシフトレジスタ
２０と第２の線形フィードバックシフトレジスタ２２の
シフトレジスタ数は、独立に設定することができる。同
数でも良いし、異なる数でも良い。また、シフトレジス
タ数が同数である場合に、第１の線形フィードバックシ
フトレジスタ２０と第２の線形フィードバックシフトレ
ジスタ２２の内部構造は、独立に設定することができ、
同一構造でも異なる構造でも良い。The number of shift registers of the first linear feedback shift register 20 and the second linear feedback shift register 22 can be set independently. The number may be the same or different. Further, when the number of shift registers is the same, the internal structures of the first linear feedback shift register 20 and the second linear feedback shift register 22 can be set independently,
The same structure or different structures may be used.
【００５９】なお、線形フィードバックシフトレジスタ
２０，２２夫々の生成多項式は最大長系列を出力させる
ために既約多項式であることが望ましい。また、第１の
乱数生成部２にセットする初期状態と第２の乱数生成部
４にセットする初期状態は独立のものであるが、第１の
線形フィードバックシフトレジスタ２０と第２の線形フ
ィードバックシフトレジスタ２２のシフトレジスタ数が
同一の場合に、両者の初期状態を同一にしても構わな
い。The generator polynomials of the linear feedback shift registers 20 and 22 are preferably irreducible polynomials in order to output a maximum length sequence. Although the initial state set in the first random number generation unit 2 and the initial state set in the second random number generation unit 4 are independent, the first linear feedback shift register 20 and the second linear feedback shift When the number of shift registers of the register 22 is the same, the initial state of both may be the same.
【００６０】上記のような第１の線形フィードバックシ
フトレジスタ２０は、初期状態にセットされた後、乱数
系列（２値系列）Ｄを所定のビット単位（例えば６４ビ
ット単位）に生成し出力していく。この単位となるビッ
ト数をｕ１で表す。After being set to the initial state, the first linear feedback shift register 20 generates and outputs a random number sequence (binary sequence) D in a predetermined bit unit (for example, 64 bit units). Go. The number of bits as a unit is represented by u1.
【００６１】同様に、第２の乱数生成部４は、初期状態
にセットされた後、乱数系列（２値系列）Ａを所定のビ
ット単位（例えば８ビット単位）に生成し出力してい
く。この単位となるビット数をｕ２で表す。Similarly, after being set to the initial state, the second random number generation section 4 generates and outputs a random number sequence (binary sequence) A in a predetermined bit unit (for example, in 8-bit units). The unit number of bits is represented by u2.
【００６２】記憶装置２４は、例えばＲＡＭなどのよう
に指定したアドレスに対する書き込みおよび読み出しが
可能な記憶素子を用いて構成される。記憶装置２４は、
少なくとも２u2（＝ｍ）種類のアドレスの夫々にｕ１ビ
ットのデータを格納できる容量を持つものとする。ただ
し、記憶装置２４は、１つの記憶素子から構成されてい
ても複数の記憶素子から構成されていても構わない。The storage device 24 is configured using a storage element that can write and read data at a designated address, such as a RAM. The storage device 24
It is assumed that each of the at least 2u2 (= m) types of addresses has a capacity capable of storing u1 bit data. However, the storage device 24 may be composed of one storage element or a plurality of storage elements.
【００６３】第１の線形フィードバックシフトレジスタ
２０から逐次出力されるｕ１ビットの乱数は、記憶装置
２４にデータ入力として与えられる。一方、第２の線形
フィードバックシフトレジスタ２２から逐次出力される
ｕ２ビットの乱数は、記憶装置２４にアドレス入力とし
て与えられる。The u1-bit random number sequentially output from the first linear feedback shift register 20 is provided to the storage device 24 as a data input. On the other hand, the u2-bit random number sequentially output from the second linear feedback shift register 22 is provided to the storage device 24 as an address input.
【００６４】なお、第２の線形フィードバックシフトレ
ジスタ２２から出力されるｕ２ビットの乱数が直接、記
憶装置２４のアドレスを示すものとしても良いし、間接
的に、該乱数により記憶装置２４のアドレスが特定され
るようにしても良い。例えば、ｕ２＝４で乱数が“１０
０１”の場合に記憶装置２４のアドレス“１００１”が
示されるようにしても良いし、例えば定数＋乱数×４な
どのアドレス変換式あるいは予め設定されたアドレス変
換テーブルにより実際のアドレスが示されるものとして
も良い。Note that the u2-bit random number output from the second linear feedback shift register 22 may directly indicate the address of the storage device 24, or indirectly, the address of the storage device 24 may be determined by the random number. It may be specified. For example, if u2 = 4 and the random number is “10
In the case of "01", the address "1001" of the storage device 24 may be indicated, or an actual address is indicated by an address conversion formula such as a constant + random number x 4 or a preset address conversion table. It is good.
【００６５】なお、第２の線形フィードバックシフトレ
ジスタ２２から出力されるｕ２ビットの乱数により、間
接的に記憶装置２４のアドレスが特定されるようにする
場合における、乱数をアドレスに変換する機能部分につ
いては図示を省略した。In the case where the address of the storage device 24 is indirectly specified by the u2-bit random number output from the second linear feedback shift register 22, a function of converting the random number into an address will be described. Is not shown.
【００６６】次に、図４を参照しながら本乱数生成装置
の動作について説明する。まず、初期処理として、第１
の線形フィードバックシフトレジスタ２０および第２の
線形フィードバックシフトレジスタ２２夫々を所望の初
期状態にセットする（ステップＳ１）。Next, the operation of the random number generation device will be described with reference to FIG. First, as an initial process, the first
The first and second linear feedback shift registers 20 and 22 are set to desired initial states (step S1).
【００６７】そして、第１の線形フィードバックシフト
レジスタ２０によりｕ１ビットの乱数をｍ個生成し、こ
れらを記憶装置２４のｍ種類のアドレス（例えば０〜ｍ
−１番地）に夫々格納する（ステップＳ２）。Then, m random numbers of u1 bits are generated by the first linear feedback shift register 20, and these are stored in the memory device 24 with m kinds of addresses (for example, 0 to m).
-1) (step S2).
【００６８】ｍ個の乱数夫々をどのアドレスに格納する
かは種々の方法が考えられるが、例えば、生成された順
番に０番地〜ｍ−１番地へと格納していく。次に、第２
の線形フィードバックシフトレジスタ２２によりｕ２ビ
ットの乱数を１つ生成する（ステップＳ３）。Various methods can be considered for storing each of the m random numbers at which address. For example, the random numbers are stored in addresses 0 to m-1 in the order of generation. Next, the second
A single u2-bit random number is generated by the linear feedback shift register 22 (step S3).
【００６９】そして、記憶装置２４のアドレスのうち、
ステップＳ３で生成された乱数にて示されるアドレスの
内容（ｕ１ビットの２値データ）を出力する（ステップ
Ｓ４）。Then, of the addresses of the storage device 24,
The contents (u1 bit binary data) of the address indicated by the random number generated in step S3 are output (step S4).
【００７０】この時点で、生成すべき乱数系列のうち最
初のｕ１ビットのデータが得られたことになる。次に、
第１の線形フィードバックシフトレジスタ２０によりｕ
１ビットの乱数を１つ生成する（ステップＳ６）。At this point, the first u1 bit data of the random number sequence to be generated has been obtained. next,
The first linear feedback shift register 20 allows u
One one-bit random number is generated (step S6).
【００７１】そして、記憶装置２４のアドレスのうち、
ステップＳ４で内容の出力されたアドレスに、ステップ
Ｓ５で生成された乱数を格納する（ステップＳ７）。次
に、ステップＳ３に戻って第２の線形フィードバックシ
フトレジスタ２２によりｕ２ビットの乱数を１つ生成す
る（ステップＳ３）。Then, of the addresses of the storage device 24,
The random number generated in step S5 is stored in the address where the content was output in step S4 (step S7). Next, returning to step S3, one u2-bit random number is generated by the second linear feedback shift register 22 (step S3).
【００７２】そして、記憶装置２４のアドレスのうち、
ステップＳ３で生成された乱数にて示されるアドレスの
内容（ｕ１ビットの２値データ）を出力する（ステップ
Ｓ４）。Then, of the addresses of the storage device 24,
The contents (u1 bit binary data) of the address indicated by the random number generated in step S3 are output (step S4).
【００７３】この時点で、生成すべき乱数系列のうち２
番目のｕ１ビットのデータが得られたことになり、乱数
系列としては全部でｕ１×２ビットのデータが得られた
ことになる。At this point, 2 out of the random number sequence to be generated
This means that the first u1 bit data has been obtained, and that a total of u1 × 2 bit data has been obtained as a random number sequence.
【００７４】以降、ステップＳ６，Ｓ７，Ｓ３，Ｓ４の
処理ループを１回繰り返すごとに、順次、ｕ１ビットの
乱数が生成されていく。そして、ステップＳ４で必要な
長さの乱数系列が得られた場合に、ステップＳ５でルー
プを抜けて、処理を終了する。Thereafter, each time the processing loop of steps S6, S7, S3, S4 is repeated once, a u1-bit random number is sequentially generated. Then, when a random number sequence of a required length is obtained in step S4, the process exits the loop in step S5 and ends the process.
【００７５】以上により、第１の線形フィードバックシ
フトレジスタ２０により生成された乱数系列を、第２の
線形フィードバックシフトレジスタ２２により生成され
た乱数系列に基づいて順序変更したものが得られる。As described above, a sequence obtained by changing the order of the random number sequence generated by the first linear feedback shift register 20 based on the random number sequence generated by the second linear feedback shift register 22 is obtained.
【００７６】以下では、本乱数生成装置の動作について
具体例を用いて説明する。ここでは、ｕ２＝３とし、第
２の線形フィードバックシフトレジスタ２０により生成
された乱数が直接、記憶装置２４のアドレスを示すもの
とする。Hereinafter, the operation of the random number generation device will be described using a specific example. Here, u2 = 3, and the random number generated by the second linear feedback shift register 20 directly indicates the address of the storage device 24.
【００７７】また、第１の線形フィードバックシフトレ
ジスタ２０により、乱数系列“ＡＢＣＤＥＦＧＨＩＪＫ
ＬＭＮ…”が生成され、第２の線形フィードバックシフ
トレジスタ２２により、乱数系列“０１１００１０１１
１１１００００１０…”が生成されるものとする。Further, the first linear feedback shift register 20 generates a random number sequence “ABCDEFGHIJK”.
LMN... Are generated, and the second linear feedback shift register 22 generates a random number sequence “011001011”.
111000010... "Are generated.
【００７８】ここで、Ａ〜Ｎの各々は、２値の乱数系列
を先頭からｕ１ビット毎に区切って得たデータを表すも
のとする。ｕ２＝３とするので、図５に示すように第２
の線形フィードバックシフトレジスタ２０により生成さ
れた乱数系列を３ビットごとに区切って得られる“０１
１”、“００１”、“０１１”、“１１１”、“００
０”、“０１０”、…が、この順番に記憶装置２４にア
ドレス入力として与えられることになる。Here, each of A to N represents data obtained by dividing a binary random number sequence from the head for each u1 bit. Since u2 = 3, as shown in FIG.
Is obtained by dividing the random number sequence generated by the linear feedback shift register 20 of FIG.
1 "," 001 "," 011 "," 111 "," 00 "
0 "," 010 ",... Are given to the storage device 24 in this order as address inputs.
【００７９】動作前においては図６（ａ）のように記憶
装置２４のアドレス０００〜１１１には有効なデータが
格納されていない状態である。まず、ｍ＝２u2＝２3 ＝
８であるので、ステップＳ１において初期状態がセット
された後、ステップＳ２において、第１の線形フィード
バックシフトレジスタ２０により、乱数系列“ＡＢＣＤ
ＥＦＧＨ”が生成され、図６（ｂ）のように記憶装置２
４のアドレス０００〜１１１にされる。Before the operation, as shown in FIG. 6A, valid data is not stored in the addresses 000 to 111 of the storage device 24. First, m = 2u2 = 23 =
8, the initial state is set in step S1, and in step S2, the first linear feedback shift register 20 causes the random number sequence “ABCD”
EFGH "is generated, and as shown in FIG.
4 are set to addresses 000 to 111.
【００８０】次に、ステップＳ３にて第２の線形フィー
ドバックシフトレジスタ２２により“０１１”が生成さ
れ、ステップＳ４にて記憶装置２４のアドレス“０１
１”の内容Ｄが出力される。Next, "011" is generated by the second linear feedback shift register 22 in step S3, and the address "01" of the storage device 24 is generated in step S4.
The content D of "1" is output.
【００８１】そして、ステップＳ６にて第１の線形フィ
ードバックシフトレジスタ２０により“Ｉ”が生成さ
れ、これがステップＳ７にて記憶装置２４のアドレス
“０１１”に格納される。このときの記憶装置２４の各
アドレスの内容を図６（ｃ）に示す。Then, "I" is generated by the first linear feedback shift register 20 in step S6, and this is stored in the address "011" of the storage device 24 in step S7. FIG. 6C shows the contents of each address of the storage device 24 at this time.
【００８２】次に、ステップＳ３に戻り、第２の線形フ
ィードバックシフトレジスタ２２により“００１”が生
成され、ステップＳ４にて記憶装置２４のアドレス“０
０１”の内容Ｂが出力される。Next, returning to step S3, "001" is generated by the second linear feedback shift register 22, and at step S4, the address "0" of the storage device 24 is read.
01 "is output.
【００８３】そして、ステップＳ６にて第１の線形フィ
ードバックシフトレジスタ２０により“Ｊ”が生成さ
れ、これがステップＳ７にて記憶装置２４のアドレス
“００１”に格納される。このときの記憶装置２４の各
アドレスの内容を図６（ｄ）に示す。Then, "J" is generated by the first linear feedback shift register 20 in step S6, and this is stored in the storage device 24 at the address "001" in step S7. FIG. 6D shows the contents of each address of the storage device 24 at this time.
【００８４】さらに同様の処理を４回繰り返すと、乱数
系列“ＤＢＩＨＡＣ”が得られる。この間の記憶装置２
４の各アドレスの内容の遷移を図７（ａ）〜（ｄ）に示
す。When the same processing is further repeated four times, a random number sequence “DBIHAC” is obtained. Storage device 2 during this time
7 (a) to 7 (d) show the transition of the contents of each address of FIG.
【００８５】以上の処理を必要回数繰り返すことによ
り、所望の長さの乱数系列を得ることができる。ここ
で、図８（ａ）と（ｂ）に、第１の線形フィードバック
シフトレジスタ２０により生成された乱数系列と、本乱
数生成装置により生成された乱数系列を対象する形で示
す。By repeating the above process a required number of times, a random number sequence having a desired length can be obtained. Here, FIGS. 8A and 8B show a random number sequence generated by the first linear feedback shift register 20 and a random number sequence generated by the present random number generation device.
【００８６】図８に示されるように、第２の線形フィー
ドバックシフトレジスタ２２により生成された乱数系列
に基づいて、第１の線形フィードバックシフトレジスタ
２０により生成された乱数系列が、ｕ１ビット単位で順
序変更されて、本乱数生成装置から出力されていること
がわかる。As shown in FIG. 8, on the basis of the random number sequence generated by the second linear feedback shift register 22, the random number sequence generated by the first linear feedback shift register 20 is sequentially ordered in u1 bit units. It can be seen that it has been changed and output from the random number generation device.
【００８７】なお、本乱数生成装置は、図２を用いて説
明した暗号装置および復号装置における乱数系列（鍵系
列）を生成するための乱数生成装置として用いると効果
的である。この場合、線形フィードバックシフトレジス
タ２０の初期状態および線形フィードバックシフトレジ
スタ２２の初期状態の組そのものまたはこれらを特定可
能な識別子が共通鍵として用いられる。The present random number generation device is effective when used as a random number generation device for generating a random number sequence (key sequence) in the encryption device and the decryption device described with reference to FIG. In this case, a set of the initial state of the linear feedback shift register 20 and the initial state of the linear feedback shift register 22 or an identifier capable of specifying these sets is used as a common key.
【００８８】このような本実施形態によれば、記憶装置
を緩衝域として用いることで、装置規模に比して線形複
雑度が大きく、暗号的にも安全な乱数生成装置、あるい
はこれを有する加算型ストリーム暗号の暗号装置および
復号装置を実現することができる。According to the present embodiment, by using a storage device as a buffer area, a linearly-complexity-enhanced random number generation device as compared with the device size and a cryptographically secure random number generation device or an addition device having the same are provided. An encryption device and a decryption device of the type stream cipher can be realized.
【００８９】また、装置規模に比して線形複雑度が大き
いことは、安価に安全な暗号装置および復号装置を構築
できることを意味する。ここで、本実施形態の第１およ
び第２の線形フィードバックシフトレジスタのレジスタ
長を各々ＬＡ，ＬＢとすると、本乱数生成装置での線形
複雑度は、ほぼ ＬＡ×２LB である。Further, the fact that the linear complexity is large as compared with the device scale means that secure encryption and decryption devices can be constructed at low cost. Here, assuming that the register lengths of the first and second linear feedback shift registers of this embodiment are LA and LB, respectively, the linear complexity of the random number generation device is approximately LA × 2LB.
【００９０】なお、乱数生成装置の他の構成例として、
第１の線形フィードバックシフトレジスタ２０および第
２の線形フィードバックシフトレジスタ２２の少なくと
も一方を、他の公知の乱数生成装置（例えば、複数の線
形フィードバックシフトレジスタの出力を非線形コンバ
イナで結合するもの、線形フィードバックシフトレジス
タの出力に非線形変換を施すもの、あるいは加算ジェネ
レータ（ｓｕｍｍａｔｉｏｎ ｇｅｎｅｒａｔｏｒ）な
ど）に置き換えた構成も考えられる。これを図２の暗号
装置および復号装置に適用する場合にも、もちろん、置
き換えた乱数生成装置の初期状態そのものまたはこれを
特定可能な識別子が共通鍵として用いられる。As another configuration example of the random number generation device,
At least one of the first linear feedback shift register 20 and the second linear feedback shift register 22 is connected to another known random number generation device (for example, a device combining outputs of a plurality of linear feedback shift registers with a nonlinear combiner, a linear feedback shifter). A configuration in which a non-linear conversion is performed on the output of the shift register, or a configuration in which the output is replaced with an addition generator (summation generator or the like) is also conceivable. Even when this is applied to the encryption device and the decryption device of FIG. 2, the initial state itself of the replaced random number generation device or an identifier that can specify this is used as a common key.
【００９１】また、図９に示すように、乱数生成装置の
さらに他の構成例として、第１の線形フィードバックシ
フトレジスタ２０と第２の線形フィードバックシフトレ
ジスタ２２とを１つの線形フィードバックシフトレジス
タ２６として共通化しても良い。この場合、第１の線形
フィードバックシフトレジスタ２０としてｕ１ビットの
乱数を生成する動作と、第２の線形フィードバックシフ
トレジスタ２２としてｕ２ビットの乱数を生成する動作
とを交互に行えば良い。さらに、この場合においても、
線形フィードバックシフトレジスタ２６を、他の公知の
乱数生成装置に置き換えた構成も考えられる。Further, as shown in FIG. 9, as still another configuration example of the random number generation device, the first linear feedback shift register 20 and the second linear feedback shift register 22 are formed as one linear feedback shift register 26. It may be common. In this case, an operation of generating a u1-bit random number as the first linear feedback shift register 20 and an operation of generating a u2-bit random number as the second linear feedback shift register 22 may be performed alternately. Furthermore, in this case,
A configuration in which the linear feedback shift register 26 is replaced with another known random number generation device is also conceivable.
【００９２】また、線形フィードバックシフトレジスタ
から出力される乱数系列を単に並べ変えるだけであれ
ば、例えば、線形フィードバックシフトレジスタから出
力される乱数系列を適当な長さにきって、一旦バッファ
装置に蓄積し、この適当な長さの乱数系列をランダムに
並べ変えて出力する方法も考えられるが、この場合、線
形フィードバックシフトレジスタでの乱数生成と順番の
バッファ装置における並べ変えから出力までの各処理が
バッチ的に行われるので、遅延が生じる欠点がある。こ
れに対して、本実施形態によれば、線形フィードバック
シフトレジスタでの乱数生成とバッファ装置からの出力
が短いサイクルで繰り返し行われるので、遅延が生じな
いという効果を得ることもできる。If the random number sequence output from the linear feedback shift register is simply rearranged, for example, the random number sequence output from the linear feedback shift register is cut into an appropriate length and temporarily stored in the buffer device. Then, a method of randomly rearranging and outputting the random number sequence of an appropriate length is also conceivable, but in this case, the random number generation in the linear feedback shift register and the respective processes from rearrangement to output in the buffer device in order are performed. There is a disadvantage that a delay occurs because the operation is performed in a batch. On the other hand, according to the present embodiment, since the random number generation in the linear feedback shift register and the output from the buffer device are repeatedly performed in a short cycle, it is possible to obtain an effect that no delay occurs.
【００９３】図１０に、本発明の他の実施形態に係る乱
数生成装置の構成を示す。また、図１１に、本乱数生成
装置の動作の流れを示す。本乱数生成装置は、第１の線
形フィードバックシフトレジスタ３０、第２の線形フィ
ードバックシフトレジスタ３２、第１の記憶装置３４、
第１の記憶装置３６、非線形コンバイナ３８を備えてい
る。FIG. 10 shows the configuration of a random number generation device according to another embodiment of the present invention. FIG. 11 shows a flow of the operation of the random number generation device. The random number generation device includes a first linear feedback shift register 30, a second linear feedback shift register 32, a first storage device 34,
A first storage device 36 and a nonlinear combiner 38 are provided.
【００９４】本乱数生成装置は、先の実施形態で図３を
参照しながら説明した乱数生成装置を２組用意し、それ
らから得られる２つの乱数系列に非線形変換処理を施し
たものを出力するものに相当する。ただし、図１０で
は、線形フィードバックシフトレジスタを各機能専用に
４個すべて設けず、併用することで２個だけ設けたもの
となっている。This random number generation device prepares two sets of the random number generation devices described in the previous embodiment with reference to FIG. 3, and outputs a result of performing a non-linear conversion process on two random number sequences obtained from them. Equivalent to something. However, in FIG. 10, not all four linear feedback shift registers are provided exclusively for each function, but only two linear feedback shift registers are provided by using them together.
【００９５】すなわち、第１の線形フィードバックシフ
トレジスタ３０および第２の線形フィードバックシフト
レジスタ３２の基本的な構成は、先の実施形態で図３を
参照しながら説明した第１の線形フィードバックシフト
レジスタ２０および第２の線形フィードバックシフトレ
ジスタ２２と同様である。相違するのは、第１の線形フ
ィードバックシフトレジスタ３０を第１の記憶装置３４
へのデータ入力と第２の記憶装置３６へのアドレス入力
の両方に使用し、第２の線形フィードバックシフトレジ
スタ３２を第２の記憶装置３６へのデータ入力と第１の
記憶装置３４へのアドレス入力の両方に使用する点であ
る。That is, the basic configuration of the first linear feedback shift register 30 and the second linear feedback shift register 32 is the same as that of the first linear feedback shift register 20 described in the previous embodiment with reference to FIG. And the second linear feedback shift register 22. The difference is that the first linear feedback shift register 30 is stored in the first storage device 34.
The second linear feedback shift register 32 is used for both the data input to the second storage device 36 and the address input to the second storage device 36, and the data input to the second storage device 36 and the address to the first storage device 34 are performed. It is used for both inputs.
【００９６】本実施形態では、第１の線形フィードバッ
クシフトレジスタ３０により生成され第１の記憶装置３
４へのデータ入力となる乱数Ｄ１と、第２の線形フィー
ドバックシフトレジスタ３２により生成され第２の記憶
装置３６へのデータ入力となる乱数Ｄ２とは、同じビッ
ト長でも良いし、異なるビット長でも良い。In the present embodiment, the first storage device 3 generated by the first linear feedback shift register 30
4 and the random number D2 generated by the second linear feedback shift register 32 and input to the second storage device 36 may have the same bit length or different bit lengths. good.
【００９７】また、第１の線形フィードバックシフトレ
ジスタ３０により生成され第２の記憶装置３６へのアド
レス入力となる乱数Ａ１と、第２の線形フィードバック
シフトレジスタ３２により生成され第１の記憶装置３４
へのアドレス入力となる乱数Ａ２とは、同じビット長で
も良いし、異なるビット長でも良い。Further, a random number A1 generated by the first linear feedback shift register 30 and used as an address input to the second storage device 36, and a first storage device 34 generated by the second linear feedback shift register 32.
The random number A2 used as the address input to the address may have the same bit length or a different bit length.
【００９８】ようするに、本実施形態では、第１の線形
フィードバックシフトレジスタ３０は、初期処理のため
に第１の記憶装置３４に格納すべき必要個数の乱数を生
成した後は、第２の記憶装置３６へのアドレス入力とな
る乱数Ａ１と、第１の記憶装置３４へのデータ入力とな
る乱数Ｄ１とを交互に生成し、同様に、第２の線形フィ
ードバックシフトレジスタ３２は、初期処理のために第
２の記憶装置３６に格納すべき必要個数の乱数を生成し
た後は、第１の記憶装置３４へのアドレス入力となる乱
数Ａ２と、第２の記憶装置３６へのデータ入力となる乱
数Ｄ２とを交互に生成する。As described above, in the present embodiment, after the first linear feedback shift register 30 generates the required number of random numbers to be stored in the first storage device 34 for the initial processing, the first linear feedback shift register 30 A random number A1 serving as an address input to 36 and a random number D1 serving as a data input to the first storage device 34 are alternately generated. Similarly, the second linear feedback shift register 32 After generating the required number of random numbers to be stored in the second storage device 36, a random number A2 serving as an address input to the first storage device 34 and a random number D2 serving as a data input to the second storage device 36 Are generated alternately.
【００９９】第１の記憶装置３４および第２の記憶装置
３６の構成は、先の実施形態で図３を参照しながら説明
した記憶装置２４と同様である。非線形コンバイナ３８
の機能は、例えば、２入力１出力の非線形関数ｆであ
る。非線形コンバイナ３８としては、公知のものを使用
することができる（例えば文献１参照）。The configuration of the first storage device 34 and the second storage device 36 is the same as that of the storage device 24 described in the above embodiment with reference to FIG. Non-linear combiner 38
Is, for example, a two-input one-output nonlinear function f. As the nonlinear combiner 38, a known combiner can be used (for example, see Document 1).
【０１００】また、非線形コンバイナ３８は、２つの入
力データの各ビットの値をもとにした組み合わせ回路で
実現しても良い。なお、線形フィードバックシフトレジ
スタの初期状態や、記憶装置のアドレス入力となる乱数
と該乱数により示されるアドレスとの関係についても、
先に説明したものと同様である。The nonlinear combiner 38 may be realized by a combination circuit based on the value of each bit of two input data. Note that the initial state of the linear feedback shift register, and the relationship between a random number to be an address input of the storage device and the address indicated by the random number,
This is the same as that described above.
【０１０１】次に、図１１を参照しながら本乱数生成装
置の動作について説明する。まず、初期処理として、第
１の線形フィードバックシフトレジスタ２０および第２
の線形フィードバックシフトレジスタ２２夫々を所望の
初期状態にセットする（ステップＳ１１）。Next, the operation of the random number generation device will be described with reference to FIG. First, as an initial process, the first linear feedback shift register 20 and the second
Is set to a desired initial state (step S11).
【０１０２】そして、第１の線形フィードバックシフト
レジスタ３０により所定ビットの乱数を所定個数生成
し、これらを第１の記憶装置３４に格納するとともに、
第２の線形フィードバックシフトレジスタ３２により所
定ビットの乱数を所定個数生成し、これらを第２の記憶
装置３６に格納する（ステップＳ１２）。Then, a predetermined number of random numbers of predetermined bits are generated by the first linear feedback shift register 30 and stored in the first storage device 34.
A predetermined number of random numbers of predetermined bits are generated by the second linear feedback shift register 32, and these are stored in the second storage device 36 (step S12).
【０１０３】次に、第１の線形フィードバックシフトレ
ジスタ３０によりアドレス用の乱数Ａ１を１つ生成する
とともに、第２の線形フィードバックシフトレジスタ３
２によりアドレス用の乱数Ａ２を１つ生成する。（ステ
ップＳ１３）。Next, one random number A1 for the address is generated by the first linear feedback shift register 30, and the second linear feedback shift register 3
2, one random number A2 for the address is generated. (Step S13).
【０１０４】そして、第１の記憶装置３４のアドレスの
うち、ステップＳ１３で生成された乱数Ａ２にて示され
るアドレスの内容を出力するとともに、第２の記憶装置
３６のアドレスのうち、ステップＳ１３で生成された乱
数Ａ１にて示されるアドレスの内容を出力する（ステッ
プＳ１４）。Then, among the addresses of the first storage device 34, the contents of the address indicated by the random number A2 generated in step S13 are output, and the addresses of the second storage device 36 are output in step S13. The contents of the address indicated by the generated random number A1 are output (step S14).
【０１０５】さらに、非線形コンバイナ３８により、ス
テップＳ１４にて第１の記憶装置３４および第２の記憶
装置３６夫々から出力されたデータをもとにした所定の
被線形変換処理を実行して、得られたデータを出力する
（ステップＳ１５）。Further, at step S14, the nonlinear combiner 38 executes a predetermined linear conversion process based on the data output from the first storage device 34 and the data output from the second storage device 36, respectively. The obtained data is output (step S15).
【０１０６】この時点で、生成すべき乱数系列のうち最
初の所定ビット分のデータが得られたことになる。次
に、第１の線形フィードバックシフトレジスタ３０によ
りデータ用の乱数Ｄ１を１つ生成するとともに、第２の
線形フィードバックシフトレジスタ３２によりデータ用
の乱数Ｄ２を１つ生成する（ステップＳ１７）。At this point, data of the first predetermined bits of the random number sequence to be generated has been obtained. Next, one random number D1 for data is generated by the first linear feedback shift register 30, and one random number D2 for data is generated by the second linear feedback shift register 32 (step S17).
【０１０７】そして、第１の記憶装置３４のアドレスの
うち、ステップＳ１４で内容の出力されたアドレスに、
ステップＳ１７で生成された乱数Ｄ１を格納するととも
に、第２の記憶装置３６のアドレスのうち、ステップＳ
１４で内容の出力されたアドレスに、ステップＳ１７で
生成された乱数Ｄ２を格納する（ステップＳ１８）。Then, of the addresses in the first storage device 34, the addresses whose contents have been output in step S14 are
The random number D1 generated in step S17 is stored, and the address in the second storage device 36 is stored in step S17.
The random number D2 generated in step S17 is stored in the address where the content was output in step 14 (step S18).
【０１０８】次に、ステップＳ１３に戻って上記と同様
に乱数Ａ１とＡ２を生成し（ステップＳ１３）、各記憶
装置２４，２６において乱数Ａ２，Ａ１にて示されるア
ドレスの内容を夫々出力し（ステップＳ１４）、この２
つの出力をもとにした所定の被線形変換処理により得ら
れたデータを出力する（ステップＳ１５）。Next, returning to step S13, random numbers A1 and A2 are generated in the same manner as described above (step S13), and the contents of the addresses indicated by the random numbers A2 and A1 are output from the storage devices 24 and 26, respectively ( Step S14), this 2
The data obtained by the predetermined linear conversion process based on the two outputs is output (step S15).
【０１０９】この時点で、生成すべき乱数系列のうち２
番目の所定ビットのデータが得られたことになる。以
降、ステップＳ１７，Ｓ１８，Ｓ１３，Ｓ１４，Ｓ１５
の処理ループを１回繰り返すごとに、順次、所定ビット
の乱数が生成されていく。At this point, 2 out of the random number sequence to be generated
This means that the data of the predetermined bit is obtained. Hereinafter, steps S17, S18, S13, S14, S15
Each time this processing loop is repeated once, a random number of predetermined bits is sequentially generated.
【０１１０】そして、ステップＳ１５で必要な長さの乱
数系列が得られた場合に、ステップＳ１６でループを抜
けて、処理を終了する。なお、本乱数生成装置は、図２
を用いて説明した暗号装置および復号装置における乱数
系列（鍵系列）を生成するための乱数生成装置として用
いると効果的である。この場合、線形フィードバックシ
フトレジスタ３０の初期状態および線形フィードバック
シフトレジスタ３２の初期状態の組そのものまたはこれ
らを特定可能な識別子が共通鍵として用いられる。When a random number sequence having a required length is obtained in step S15, the process exits the loop in step S16 and ends the processing. Note that the random number generation device is configured as shown in FIG.
It is effective when used as a random number generation device for generating a random number sequence (key sequence) in the encryption device and the decryption device described using. In this case, a set of the initial state of the linear feedback shift register 30 and the initial state of the linear feedback shift register 32 itself or an identifier capable of specifying them is used as a common key.
【０１１１】このような本実施形態によれば、記憶装置
を緩衝域として用いることで、装置規模に比して線形複
雑度が大きく、暗号的にも安全な乱数生成装置、あるい
はこれを有する加算型ストリーム暗号の暗号装置および
復号装置を実現することができる。According to the present embodiment, by using a storage device as a buffer area, a linearly-complexity-enhanced random number generation device as compared with the device size, and a cryptographically secure random number generation device, or an addition device having the same. An encryption device and a decryption device of the type stream cipher can be realized.
【０１１２】また、装置規模に比して線形複雑度が大き
いことは、安価に安全な暗号装置および復号装置を構築
できることを意味する。ここで、本実施形態の第１およ
び第２の線形フィードバックシフトレジスタのレジスタ
長を各々ＬＡ，ＬＢとすると、本乱数生成装置での線形
複雑度は、ほぼ ２LA×２LB である。Further, the fact that the linear complexity is large as compared with the device scale means that a secure encryption device and decryption device can be constructed at low cost. Here, assuming that the register lengths of the first and second linear feedback shift registers of this embodiment are LA and LB, respectively, the linear complexity of the random number generation device is approximately 2LA × 2LB.
【０１１３】なお、乱数生成装置のさらに他の構成例と
して、第１の線形フィードバックシフトレジスタ３０と
第２の線形フィードバックシフトレジスタ３２とを１つ
の線形フィードバックシフトレジスタとして共通化して
も良い。As still another configuration example of the random number generation device, the first linear feedback shift register 30 and the second linear feedback shift register 32 may be shared as one linear feedback shift register.
【０１１４】あるいは、その逆に、第１の線形フィード
バックシフトレジスタ３０および第２の線形フィードバ
ックシフトレジスタ３２の少なくとも一方を、データ用
とアドレス用に分離し、装置全体として３つあるいは４
つの線形フィードバックシフトレジスタを設けた構成に
することも可能でる。Alternatively, conversely, at least one of the first linear feedback shift register 30 and the second linear feedback shift register 32 is separated for data and address, and three or four for the entire apparatus.
A configuration in which two linear feedback shift registers are provided is also possible.
【０１１５】また、上記した線形フィードバックシフト
レジスタを１、２、３、または４個備えた構成におい
て、少なくとも１つの線形フィードバックシフトレジス
タを、他の公知の乱数生成装置（例えば、複数の線形フ
ィードバックシフトレジスタの出力を非線形コンバイナ
で結合するもの、線形フィードバックシフトレジスタの
出力に非線形変換を施すもの、あるいは加算ジェネレー
タ（ｓｕｍｍａｔｉｏｎｇｅｎｅｒａｔｏｒ）など）に
置き換えた構成も考えられる。これを図２の暗号装置お
よび復号装置に適用する場合にも、もちろん、置き換え
た乱数生成装置の初期状態そのものまたはこれを特定可
能な識別子が共通鍵として用いられる。Further, in the configuration having one, two, three or four linear feedback shift registers, at least one linear feedback shift register is replaced with another known random number generation device (for example, a plurality of linear feedback shift registers). A configuration in which the outputs of the registers are combined by a non-linear combiner, a configuration in which the outputs of the linear feedback shift registers are subjected to non-linear conversion, or a configuration in which an addition generator (summation generator) or the like is replaced is also conceivable. Even when this is applied to the encryption device and the decryption device of FIG. 2, the initial state itself of the replaced random number generation device or an identifier that can specify this is used as a common key.
【０１１６】図１２に、本発明のさらに他の実施形態に
係る乱数生成装置の構成を示す。また、図１１に、本乱
数生成装置の動作の流れを示す。本実施形態は、図３の
線形フィードバックシフトレジスタの部分を、図３の乱
数生成装置自体で置き換えて、構成を階層化したもので
ある。FIG. 12 shows a configuration of a random number generation device according to still another embodiment of the present invention. FIG. 11 shows a flow of the operation of the random number generation device. In the present embodiment, the linear feedback shift register in FIG. 3 is replaced with the random number generation device itself in FIG. 3, and the configuration is hierarchized.
【０１１７】図１２の他にも、図１０の線形フィードバ
ックシフトレジスタの部分を、図１０の乱数生成装置自
体で置き換えた構成も考えられる。あるいは、図３の線
形フィードバックシフトレジスタの部分を、図１０の乱
数生成装置自体で置き換えた構成や、図１０の線形フィ
ードバックシフトレジスタの部分を、図３の乱数生成装
置自体で置き換えた構成も考えられる。In addition to FIG. 12, a configuration in which the linear feedback shift register of FIG. 10 is replaced by the random number generator itself of FIG. 10 can be considered. Alternatively, a configuration in which the linear feedback shift register in FIG. 3 is replaced by the random number generation device itself in FIG. 10 or a configuration in which the linear feedback shift register in FIG. 10 is replaced by the random number generation device itself in FIG. Can be
【０１１８】その他、種々の構成が考えられる。また、
図１２ように２階層の構造にとどまらず、３階層以上に
階層化した乱数生成装置、例えば図１２における線形フ
ィードバックシフトレジスタの部分を、さらに図３の乱
数生成装置あるいは図１２の乱数生成装置で置き換えた
構成など、種々のものが考えられる。In addition, various configurations are conceivable. Also,
As shown in FIG. 12, the random number generating device is not limited to the two-layer structure but is hierarchized into three or more layers, for example, the linear feedback shift register in FIG. Various configurations such as a replaced configuration are conceivable.
【０１１９】また、以上の各機能は、ソフトウェアとし
ても実現可能である。また、上記した各手順あるいは手
段をコンピュータに実行させるためのプログラムを記録
した機械読取り可能な媒体として実施することもでき
る。本発明は、上述した実施の形態に限定されるもので
はなく、その技術的範囲において種々変形して実施する
ことができる。Each of the above functions can be realized as software. Further, the present invention can be embodied as a machine-readable medium storing a program for causing a computer to execute the above-described procedures or means. The present invention is not limited to the above-described embodiment, and can be implemented with various modifications within the technical scope.
【０１２０】[0120]
【発明の効果】本発明に係る乱数生成装置や方法によれ
ば、記憶装置を緩衝域として用いることで、少ない装置
規模で大きな線形複雑度を達成することができる。従っ
て、本発明に係る乱数生成装置や方法を適用することに
より、経済的かつ安全なストリーム暗号を実現すること
ができる。According to the random number generation apparatus and method of the present invention, a large linear complexity can be achieved with a small apparatus scale by using a storage device as a buffer area. Therefore, by applying the random number generation device and method according to the present invention, an economical and secure stream cipher can be realized.
【図１】本発明の実施の形態に係る乱数生成装置の構成
を示す図FIG. 1 is a diagram showing a configuration of a random number generation device according to an embodiment of the present invention.
【図２】本発明の実施の形態に係る乱数生成装置を用い
た暗号システムの一例を示す図FIG. 2 is a diagram showing an example of an encryption system using a random number generation device according to an embodiment of the present invention.
【図３】本発明の一実施形態に係る乱数生成装置の構成
を示す図FIG. 3 is a diagram showing a configuration of a random number generation device according to an embodiment of the present invention.
【図４】同実施形態に係る乱数生成装置の動作を示すフ
ローチャートFIG. 4 is a flowchart showing the operation of the random number generation device according to the embodiment;
【図５】生成されたアドレス系列を示す図FIG. 5 is a diagram showing a generated address sequence;
【図６】記憶装置の内容の遷移を示す図FIG. 6 is a diagram showing transition of contents of a storage device;
【図７】記憶装置の内容の遷移を示す図FIG. 7 is a diagram showing transition of contents of a storage device;
【図８】変換前後の乱数系列を示す図FIG. 8 is a diagram showing a random number sequence before and after conversion.
【図９】同実施形態に係る乱数生成装置の変形例の構成
を示す図FIG. 9 is a diagram showing a configuration of a modification of the random number generation device according to the embodiment;
【図１０】本発明の他の実施形態に係る乱数生成装置の
構成を示す図FIG. 10 is a diagram showing a configuration of a random number generation device according to another embodiment of the present invention.
【図１１】同実施形態に係る乱数生成装置の動作を示す
フローチャートFIG. 11 is a flowchart showing the operation of the random number generation device according to the embodiment;
【図１２】本発明のさらに他の実施形態に係る乱数生成
装置の構成を示す図FIG. 12 is a diagram showing a configuration of a random number generation device according to still another embodiment of the present invention.
【図１３】線形フィードバックシフトレジスタの構成例
を示す図FIG. 13 is a diagram illustrating a configuration example of a linear feedback shift register.
【図１４】他の乱数生成装置の構成例を示す図FIG. 14 is a diagram illustrating a configuration example of another random number generation device.
２，４，４０，４２…乱数生成部 ６…乱数変換部 １０ａ，１０ｂ…乱数生成装置 １２ａ，１２ｂ…論理演算処理装置 ２０，２２，２６，３０，３２…線形フィードバックシ
フトレジスタ ２４，３４，３６…記憶装置 ３８…非線形コンバイナ2, 4, 40, 42 ... random number generator 6 ... random number converter 10a, 10b ... random number generator 12a, 12b ... logical operation processor 20, 22, 26, 30, 32 ... linear feedback shift register 24, 34, 36 … Storage device 38… Nonlinear combiner
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9045954AJPH10240500A (en) | 1997-02-28 | 1997-02-28 | Random number generation device and method, encryption device and method, decryption device and method, and stream encryption system |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9045954AJPH10240500A (en) | 1997-02-28 | 1997-02-28 | Random number generation device and method, encryption device and method, decryption device and method, and stream encryption system |
| Publication Number | Publication Date |
|---|---|
| JPH10240500Atrue JPH10240500A (en) | 1998-09-11 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP9045954APendingJPH10240500A (en) | 1997-02-28 | 1997-02-28 | Random number generation device and method, encryption device and method, decryption device and method, and stream encryption system |
| Country | Link |
|---|---|
| JP (1) | JPH10240500A (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2004032098A1 (en)* | 2002-10-07 | 2004-04-15 | Kobayashi, Akira | Pseudo-random number generation method and pseudo-random number generator |
| JP2005110222A (en)* | 2003-09-12 | 2005-04-21 | Victor Co Of Japan Ltd | Information transmission method, transmitter and receiver |
| JP2006285830A (en)* | 2005-04-04 | 2006-10-19 | National Institute Of Information & Communication Technology | Pseudorandom number generator strength evaluation device and encryption device |
| JP2007073012A (en)* | 2005-09-09 | 2007-03-22 | Iwate Univ | Random number generation system |
| US7257607B2 (en) | 2002-04-19 | 2007-08-14 | Nec Corporation | Random number generating apparatus, random number generating method, program for generating random numbers, audio decoder and audio decoding method |
| JP2007215166A (en)* | 2006-01-11 | 2007-08-23 | Matsushita Electric Ind Co Ltd | Data transmitting apparatus and data receiving apparatus |
| JP2007533225A (en)* | 2004-04-14 | 2007-11-15 | インターナショナル・ビジネス・マシーンズ・コーポレーション | Secure credit card employing pseudo-random bit sequence for authentication and authentication method thereof |
| JP2008165008A (en)* | 2006-12-28 | 2008-07-17 | Megachips Lsi Solutions Inc | Data processor and data processing method |
| WO2008102693A1 (en)* | 2007-02-19 | 2008-08-28 | National Institute Of Advanced Industrial Science And Technology | Authentication system using light-weight authentication protocol |
| JP2008245053A (en)* | 2007-03-28 | 2008-10-09 | Hitachi Information & Communication Engineering Ltd | Method and device for optical-communication quantum cryptographic communication |
| JP2010181789A (en)* | 2009-02-09 | 2010-08-19 | Mitsubishi Electric Corp | Information processing device, information processing method, and program |
| JP2011019219A (en)* | 2004-12-22 | 2011-01-27 | Qualcomm Inc | Method and apparatus for flexible hopping in multiple access communication network |
| WO2012141680A1 (en)* | 2011-04-11 | 2012-10-18 | Hewlett-Packard Development Company, L.P. | Mass serialization |
| JP2014516492A (en)* | 2011-04-15 | 2014-07-10 | ハンスキャン・アイピー・ベスローテン・フェンノートシャップ | System and method for remote biometric operation |
| US8798183B2 (en) | 2007-08-13 | 2014-08-05 | Qualcomm Incorporated | Feedback and rate adaptation for MIMO transmission in a time division duplexed (TDD) communication system |
| JP2014186180A (en)* | 2013-03-25 | 2014-10-02 | Mega Chips Corp | Stream cipher device |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7257607B2 (en) | 2002-04-19 | 2007-08-14 | Nec Corporation | Random number generating apparatus, random number generating method, program for generating random numbers, audio decoder and audio decoding method |
| WO2004032098A1 (en)* | 2002-10-07 | 2004-04-15 | Kobayashi, Akira | Pseudo-random number generation method and pseudo-random number generator |
| JP2005110222A (en)* | 2003-09-12 | 2005-04-21 | Victor Co Of Japan Ltd | Information transmission method, transmitter and receiver |
| JP2007533225A (en)* | 2004-04-14 | 2007-11-15 | インターナショナル・ビジネス・マシーンズ・コーポレーション | Secure credit card employing pseudo-random bit sequence for authentication and authentication method thereof |
| JP2011019219A (en)* | 2004-12-22 | 2011-01-27 | Qualcomm Inc | Method and apparatus for flexible hopping in multiple access communication network |
| JP2006285830A (en)* | 2005-04-04 | 2006-10-19 | National Institute Of Information & Communication Technology | Pseudorandom number generator strength evaluation device and encryption device |
| JP2007073012A (en)* | 2005-09-09 | 2007-03-22 | Iwate Univ | Random number generation system |
| JP2007215166A (en)* | 2006-01-11 | 2007-08-23 | Matsushita Electric Ind Co Ltd | Data transmitting apparatus and data receiving apparatus |
| JP2008165008A (en)* | 2006-12-28 | 2008-07-17 | Megachips Lsi Solutions Inc | Data processor and data processing method |
| WO2008102693A1 (en)* | 2007-02-19 | 2008-08-28 | National Institute Of Advanced Industrial Science And Technology | Authentication system using light-weight authentication protocol |
| JP2008205675A (en)* | 2007-02-19 | 2008-09-04 | National Institute Of Advanced Industrial & Technology | Authentication system with lightweight authentication protocol |
| JP2008245053A (en)* | 2007-03-28 | 2008-10-09 | Hitachi Information & Communication Engineering Ltd | Method and device for optical-communication quantum cryptographic communication |
| US8798183B2 (en) | 2007-08-13 | 2014-08-05 | Qualcomm Incorporated | Feedback and rate adaptation for MIMO transmission in a time division duplexed (TDD) communication system |
| JP2010181789A (en)* | 2009-02-09 | 2010-08-19 | Mitsubishi Electric Corp | Information processing device, information processing method, and program |
| WO2012141680A1 (en)* | 2011-04-11 | 2012-10-18 | Hewlett-Packard Development Company, L.P. | Mass serialization |
| US9344277B2 (en) | 2011-04-11 | 2016-05-17 | Hewlett-Packard Development Company, L.P. | Mass serialization analytics |
| JP2014516492A (en)* | 2011-04-15 | 2014-07-10 | ハンスキャン・アイピー・ベスローテン・フェンノートシャップ | System and method for remote biometric operation |
| JP2014186180A (en)* | 2013-03-25 | 2014-10-02 | Mega Chips Corp | Stream cipher device |
| Publication | Publication Date | Title |
|---|---|---|
| EP0839418B1 (en) | Cryptographic method and apparatus for non-linearly merging a data block and a key | |
| JP4828068B2 (en) | Computer efficient linear feedback shift register | |
| JP4127472B2 (en) | Data conversion apparatus, data conversion method and program for data conversion apparatus, and computer-readable recording medium | |
| JP4052480B2 (en) | Pseudorandom number generation method, pseudorandom number generator, and pseudorandom number generation program | |
| JP5551065B2 (en) | Encryption method and device for pseudo-random generation, data encryption, and message encryption hashing | |
| JP5000365B2 (en) | Hash value generation device, program, and hash value generation method | |
| JP5462636B2 (en) | Method and apparatus for encrypting plaintext messages | |
| JPH0863097A (en) | Method and system for symmetric encoding for encoding of data | |
| KR100800468B1 (en) | Hardware encryption / decryption device and method for low power high speed operation | |
| WO2001082524A1 (en) | Cryptographic system for data encryption standard | |
| KR20110004474A (en) | Galois Lung Cryptography System | |
| JPH10240500A (en) | Random number generation device and method, encryption device and method, decryption device and method, and stream encryption system | |
| JP4025722B2 (en) | Method and apparatus for data encryption | |
| JP2004363739A (en) | Tamper-detectable encryption / decryption device for common key encryption | |
| JP3180836B2 (en) | Cryptographic communication device | |
| JP2000066587A (en) | Data processing device, communication system, and recording medium | |
| JPH11298471A (en) | Method and device for enciphering block | |
| JP2950485B2 (en) | Stream cipher processor | |
| KR101131167B1 (en) | Method and apparatus for generating key stream for stream cipher, s-box for block cipher and method for substituting input vector using the s-box | |
| JP4857230B2 (en) | Pseudorandom number generator and encryption processing device using the same | |
| US20240097880A1 (en) | High-speed circuit combining aes and sm4 encryption and decryption | |
| RU2359415C2 (en) | Method for cryptographic transformation of digital data units | |
| JPS6281145A (en) | Data encryption method | |
| Labbi et al. | Symmetric encryption algorithm for RFID systems using a dynamic generation of key | |
| JP2005529365A (en) | AES mix column conversion |
| Date | Code | Title | Description |
|---|---|---|---|
| A02 | Decision of refusal | Free format text:JAPANESE INTERMEDIATE CODE: A02 Effective date:20040608 |