(57)【要約】擬似乱数生成装置（１）は、第１線形フィードバックシフトレジスタ（２）、第２線形フィードバックシフトレジスタ（３）、初期値生成部（４）、多項式係数生成部（５）および擬似乱数出力部（６）を有する。初期値生成部（４）は、初期値を生成し、第１線形フィードバックシフトレジスタ（２）および第２線形フィードバックシフトレジスタ（３）へ供給する。多項式係数生成部（５）は、特性多項式の係数を生成して第２線形フィードバックシフトレジスタ（３）へ供給する。擬似乱数出力部（６）は、第１線形フィードバックシフトレジスタ（２）および第２線形フィードバックシフトレジスタ（３）から順次出力されるビット列を基に、各ビットの排他的論理和から擬似乱数列を生成、出力する。【特許請求の範囲】
【請求項１】
所定のビット長の擬似乱数列を生成する擬似乱数生成装置（１）であって、
ｍ段のシフトレジスタを有し、所定のビット長のビット列を出力する第１の線形フィードバックシフトレジスタ（２）と、
ｎ段のシフトレジスタを有し、所定のビット長のビット列を出力する第２の線形フィードバックシフトレジスタ（３）と、
所定の条件に従って、前記第１の線形フィードバックシフトレジスタ（２）および前記第２の線形フィードバックシフトレジスタ（３）を構成する各シフトレジスタの初期値を生成し、それぞれの当該初期値を前記第１の線形フィードバックシフトレジスタ（２）および前記第２の線形フィードバックシフトレジスタ（３）へ供給する初期値生成部（４）と、
所定の条件に従って、前記第２の線形フィードバックシフトレジスタ（３）の特性多項式の係数を生成し、前記第２の線形フィードバックシフトレジスタ（３）へ供給する多項式係数生成部（５）と、
前記第１の線形フィードバックシフトレジスタ（２）の特性多項式として原始多項式を、前記原始多項式を指定する識別情報と共に複数記憶する原始多項式記憶部（８）と、
所定の条件に従って、前記原始多項式記憶部（８）に記憶されている原始多項式を１つ選択し、その原始多項式の係数を特性多項式の係数として前記第１の線形フィードバックシフトレジスタ（２）へ供給する原始多項式選択部（７）と、
前記第１の線形フィードバックシフトレジスタ（２）から出力されるビット列と、前記第２の線形フィードバックシフトレジスタ（３）から出力されるビット列とに基づいて、各ビットの論理演算から所定のビット長の擬似乱数列を生成し、出力する擬似乱数出力部（６）と、
を備えることを特徴とする擬似乱数生成装置（１）。
【請求項２】
前記擬似乱数生成装置（１Ｃ）は、
前記原始多項式選択部（７）によって選択された前記原始多項式の識別情報、前記初期値生成部（４）によって生成された前記第１の線形フィードバックシフトレジスタ（２）および前記第２の線形フィードバックシフトレジスタ（３）を構成する各シフトレジスタの初期値、前記多項式係数生成部（５）によって生成された前記特性多項式の係数のそれぞれからなるイニシャルデータを生成し、当該イニシャルデータを他の擬似乱数生成装置（１Ｃ）へ送出し、当該イニシャルデータを他の擬似乱数生成装置（１Ｃ）から受信した場合は、当該イニシャルデータから前記第１のフィードバックシフトレジスタ（２）と前記第２のフィードバックシフトレジスタ（３）との各初期値を抽出して前記第１の線形フィードバックシフトレジスタ（２）と前記第２の線形フィードバックシフトレジスタ（３）に供給し、当該イニシャルデータから前記特性多項式の係数を抽出して前記第２の線形フィードバックシフトレジスタ（３）へ供給し、当該イニシャルデータから前記原始多項式の識別情報を抽出して前記原始多項式選択部（７）に供給する通信部（９）を備え、
前記原始多項式選択部（７）は、前記通信部（９）によって抽出された前記識別情報を基に、前記原始多項式記憶部（８）に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の線形フィードバックシフトレジスタ（２）へ供給することを特徴とする請求の範囲第１項に記載の擬似乱数生成装置。
【請求項３】
所定のビット長の擬似乱数列を生成するコンピュータによって実行される擬似乱数生成プログラムであって、
当該擬似乱数生成プログラムは、前記コンピュータを、
ｍ段のシフトレジスタを有し、所定のビット長のビット列を出力する第１の線形フィードバックシフトレジスタと、
ｎ段のシフトレジスタを有し、所定のビット長のビット列を出力する第２の線形フィードバックシフトレジスタと、
所定の条件に従って、前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタを構成する各シフトレジスタの初期値を生成し、それぞれの当該初期値を前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタへ供給する初期値生成手段と、
所定の条件に従って、前記第２の線形フィードバックシフトレジスタの特性多項式の係数を生成し、前記第２の線形フィードバックシフトレジスタへ供給する多項式係数生成手段と、
前記第１の線形フィードバックシフトレジスタの特性多項式として原始多項式を、前記原始多項式を指定する識別情報と共に複数記憶する原始多項式記憶手段と、
所定の条件に従って、前記原始多項式記憶手段に記憶されている原始多項式を１つ選択し、その原始多項式の係数を特性多項式の係数として前記第１の線形フィードバックシフトレジスタへ供給する原始多項式選択手段と、
前記第１の線形フィードバックシフトレジスタから出力されるビット列と、前記第２の線形フィードバックシフトレジスタから出力されるビット列とに基づいて、各ビットの論理演算から所定のビット長の擬似乱数列を生成し、出力する擬似乱数出力手段と、
して機能させることを特徴とする擬似乱数生成プログラム。
【請求項４】
前記擬似乱数生成プログラムは、前記コンピュータを、
前記原始多項式選択手段によって選択された前記原始多項式の識別情報、前記初期値生成手段によって生成された前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタを構成する各シフトレジスタの初期値、前記多項式係数生成手段によって生成された前記特性多項式の係数のそれぞれからなるイニシャルデータを生成し、当該イニシャルデータを他の擬似乱数生成装置へ送出し、当該イニシャルデータを他の擬似乱数生成装置から受信した場合は、当該イニシャルデータから前記第１のフィードバックシフトレジスタと前記第２のフィードバックシフトレジスタとの各初期値を抽出して前記第１の線形フィードバックシフトレジスタと前記第２の線形フィードバックシフトレジスタに供給し、当該イニシャルデータから前記特性多項式の係数を抽出して前記第２の線形フィードバックシフトレジスタへ供給し、当該イニシャルデータから前記原始多項式の識別情報を抽出して前記原始多項式選択手段に供給する通信手段としても機能させ、
前記原始多項式選択手段は、前記通信手段によって抽出された前記識別情報を基に、前記原始多項式記憶手段に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の線形フィードバックシフトレジスタへ供給する手段であることを特徴とする請求の範囲第３項に記載の擬似乱数生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、暗号通信に利用される擬似乱数を生成する擬似乱数生成装置および擬似乱数生成プログラムに関する。
【背景技術】
【０００２】  現在、電話や無線、インターネット等におけるデータ通信では、通信されるデータを第三者による盗聴や改ざんから保護するために、データの暗号化が行われている。データの送信側では、暗号鍵を用いて送信するデータを暗号化した後送信し、受信側では、その暗号化されたデータを受信すると、復号鍵を用いて復号化しデータを得ている。もしこの時、第三者がデータを傍受しても、正当な復号鍵を持たないため暗号化されたデータを復号することができず、また、意図したデータの改ざんを行うこともできない。【０００３】  このような暗号化の方式には、共通鍵暗号方式や公開鍵暗号方式があり、それぞれの特徴をいかして利用される条件に応じて選択される。いずれの方式であっても、暗号鍵によって通信されるデータの安全性が保障されており、その暗号鍵は容易に推測されないように擬似乱数を用いる方法が知られている。【０００４】  例えば、線形フィードバックシフトレジスタによる擬似乱数の生成方法では、乱数生成のための比較的短い初期値からデータ長の長い擬似乱数列を生成することができるため、複数の装置で同じ擬似乱数を生成しようとするとき、初期値を共有するだけで良い。また、一般に、特定の条件を満たす原始多項式を特性多項式とする複数の線形フィードバックシフトレジスタを組み合わせることで、生成される擬似乱数の予測が困難な擬似乱数生成装置を実現可能なことが知られている。さらに、初期値を共有しなくても、複数の線形フィードバックシフトレジスタの選択情報を共有化することで、同じ擬似乱数列を生成することも可能である（例えば、特開平１０−９１０６６号公報参照）。【０００５】  しかしながら、線形フィードバックシフトレジスタを用いた擬似乱数生成装置では、たとえ非線形な処理を組み合わせた方法であっても、ある特定のアルゴリズムで擬似乱数が生成されるため、初期値や生成される擬似乱数列の一部からその後生成される擬似乱数が推測される恐れがあった。【０００６】  また、複数の線形フィードバックシフトレジスタからいくつかのレジスタを選択して擬似乱数を生成する場合には、生成される擬似乱数列の推測は困難になるものの、任意の係数を特性多項式とする線形フィードバックシフトレジスタを組み合わせると、生成される擬似乱数列が必ずしもＭ系列（Ｍａｘｉｍｕｍ  ｌｅｎｇｔｈ  ｓｅｑｕｅｎｃｅｓ）とはならずに、短い周期で同じ擬似乱数列を繰り返し生成してしまうという問題があるため、予め特定の条件を満たす多項式を多数用意した中から選択して組み合わせる必要があった。これは実際の処理では、常に利用するわけではない線形フィードバックシフトレジスタを実装する必要があり効率的ではなかった。
【発明の開示】
【０００７】  本発明は、生成される擬似乱数列や送受信されるデータを観測されても、その後生成される擬似乱数列の推測が困難な暗号通信に好適な擬似乱数生成装置および擬似乱数生成プログラムを提供することを目的とする。
【０００８】  上記目的を達成するために、第１の態様に係る発明は、所定のビット長の擬似乱数列を生成する擬似乱数生成装置であって、ｍ段のシフトレジスタを有し、所定のビット長のビット列を出力する第１の線形フィードバックシフトレジスタと、ｎ段のシフトレジスタを有し、所定のビット長のビット列を出力する第２の線形フィードバックシフトレジスタと、所定の条件に従って、前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタを構成する各シフトレジスタの初期値を生成し、それぞれの当該初期値を前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタへ供給する初期値生成部と、所定の条件に従って、前記第２の線形フィードバックシフトレジスタの特性多項式の係数を生成し、前記第２の線形フィードバックシフトレジスタへ供給する多項式係数生成部と、前記第１の線形フィードバックシフトレジスタの特性多項式として原始多項式を、前記原始多項式を指定する識別情報と共に複数記憶する原始多項式記憶部と、所定の条件に従って、前記原始多項式記憶部に記憶されている原始多項式を１つ選択し、その原始多項式の係数を特性多項式の係数として前記第１の線形フィードバックシフトレジスタへ供給する原始多項式選択部と、前記第１の線形フィードバックシフトレジスタから出力されるビット列と、前記第２の線形フィードバックシフトレジスタから出力されるビット列とに基づいて、各ビットの論理演算から所定のビット長の擬似乱数列を生成し、出力する擬似乱数出力部と、を備える擬似乱数生成装置を要旨とする。
【０００９】  また、第２の態様に係る発明は、第１の態様に係る発明において、前記擬似乱数生成装置は、前記原始多項式選択部によって選択された前記原始多項式の識別情報、前記初期値生成部によって生成された前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタを構成する各シフトレジスタの初期値、前記多項式係数生成部によって生成された前記特性多項式の係数のそれぞれからなるイニシャルデータを生成し、当該イニシャルデータを他の擬似乱数生成装置へ送出し、当該イニシャルデータを他の擬似乱数生成装置から受信した場合は、当該イニシャルデータから前記第１のフィードバックシフトレジスタと前記第２のフィードバックシフトレジスタとの各初期値を抽出して前記第１の線形フィードバックシフトレジスタと前記第２の線形フィードバックシフトレジスタに供給し、当該イニシャルデータから前記特性多項式の係数を抽出して前記第２の線形フィードバックシフトレジスタへ供給し、当該イニシャルデータから前記原始多項式の識別情報を抽出して前記原始多項式選択部に供給する通信部を備え、前記原始多項式選択部は、前記通信部によって抽出された前記識別情報を基に、前記原始多項式記憶部に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の線形フィードバックシフトレジスタへ供給することを要旨とする。
【００１０】  また、上記目的を達成するために、第３の態様に係る発明は、所定のビット長の擬似乱数列を生成するコンピュータによって実行される擬似乱数生成プログラムであって、当該擬似乱数生成プログラムは、前記コンピュータを、ｍ段のシフトレジスタを有し、所定のビット長のビット列を出力する第１の線形フィードバックシフトレジスタと、ｎ段のシフトレジスタを有し、所定のビット長のビット列を出力する第２の線形フィードバックシフトレジスタと、所定の条件に従って、前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタを構成する各シフトレジスタの初期値を生成し、それぞれの当該初期値を前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタへ供給する初期値生成手段と、所定の条件に従って、前記第２の線形フィードバックシフトレジスタの特性多項式の係数を生成し、前記第２の線形フィードバックシフトレジスタへ供給する多項式係数生成手段と、前記第１の線形フィードバックシフトレジスタの特性多項式として原始多項式を、前記原始多項式を指定する識別情報と共に複数記憶する原始多項式記憶手段と、所定の条件に従って、前記原始多項式記憶手段に記憶されている原始多項式を１つ選択し、その原始多項式の係数を特性多項式の係数として前記第１の線形フィードバックシフトレジスタへ供給する原始多項式選択手段と、前記第１の線形フィードバックシフトレジスタから出力されるビット列と、前記第２の線形フィードバックシフトレジスタから出力されるビット列とに基づいて、各ビットの論理演算から所定のビット長の擬似乱数列を生成し、出力する擬似乱数出力手段として機能させる擬似乱数生成プログラムを要旨とする。
【００１１】  また、第４の態様に係る発明は、第３の態様に係る発明において、前記擬似乱数生成プログラムは、前記コンピュータを、前記原始多項式選択手段によって選択された前記原始多項式の識別情報、前記初期値生成手段によって生成された前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタを構成する各シフトレジスタの初期値、前記多項式係数生成手段によって生成された前記特性多項式の係数のそれぞれからなるイニシャルデータを生成し、当該イニシャルデータを他の擬似乱数生成装置へ送出し、当該イニシャルデータを他の擬似乱数生成装置から受信した場合は、当該イニシャルデータから前記第１のフィードバックシフトレジスタと前記第２のフィードバックシフトレジスタとの各初期値を抽出して前記第１の線形フィードバックシフトレジスタと前記第２の線形フィードバックシフトレジスタに供給し、当該イニシャルデータから前記特性多項式の係数を抽出して前記第２の線形フィードバックシフトレジスタへ供給し、当該イニシャルデータから前記原始多項式の識別情報を抽出して前記原始多項式選択手段に供給する通信手段としても機能させ、前記原始多項式選択手段は、前記通信手段によって抽出された前記識別情報を基に、前記原始多項式記憶手段に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の線形フィードバックシフトレジスタへ供給することを要旨とする。
【図面の簡単な説明】
【００１２】
【図１】図１は、第１の実施形態における擬似乱数生成装置の機能構成を示す図である。
【図２】図２は、第１線形フィードバックシフトレジスタの回路構成を示す図である。
【図３】図３は、第２線形フィードバックシフトレジスタの回路構成を示す図である。
【図４】図４は、第１の実施形態における擬似乱数生成の処理を示すフローチャートである。
【図５】図５は、第１線形フィードバックシフトレジスタと第２線形フィードバックシフトレジスタの値の遷移を示す図である。
【図６】図６は、第２の実施形態における擬似乱数生成装置の機能構成を示す図である。
【図７】図７は、第２の実施形態における擬似乱数生成の処理を示すフローチャートである。
【図８】図８は、第３の実施形態における擬似乱数生成装置の機能構成を示す図である。
【図９】図９は、第３の実施形態における擬似乱数生成の処理を示すフローチャートである。
【発明を実施するための最良の形態】
【００１３】  本発明の実施形態を、図１〜図９を用いて説明する。なお、擬似乱数生成装置１が生成する擬似乱数のビット長をｈ＋１とする。【００１４】＜第１の実施形態＞
第１の実施形態における擬似乱数生成装置１Ａは、図１に示すように、第１線形フィードバックシフトレジスタ２、第２線形フィードバックシフトレジスタ３、初期値生成部４、多項式係数生成部５、および擬似乱数出力部６を有する。【００１５】  第１線形フィードバックシフトレジスタ２は、ｍ次の線形フィードバックシフトレジスタであり、ｍ個のフリップフロップ回路を有する（詳細については後述）。また、第２線形フィードバックシフトレジスタ３は、ｎ次の線形フィードバックシフトレジスタであり、ｎ個のフリップフロップ回路を有する（詳細については後述）。【００１６】  初期値生成部４は、外部から入力される初期情報、あるいは予め定められた所定の条件、例えば、日時情報のように常に変化する情報や熱雑音等の物理現象を利用して得られる条件に従って、第１線形フィードバックシフトレジスタ２を構成する各フリップフロップの初期値ｉａ（ｉａｍ−１，ｉａｍ−２，…，ｉａ１，ｉａ０）を生成し、第１線形フィードバックシフトレジスタ２へ供給する機能と、第２線形フィードバックシフトレジスタ３を構成する各フリップフロップの初期値ｉｂ（ｉｂｎ−１，ｉｂｎ−２，…，ｉｂ１，ｉｂ０）を生成し、第２線形フィードバックシフトレジスタ３へ供給する機能を有する。ただし、第１線形フィードバックシフトレジスタ２からの出力が常に“０”にならないよう、少なくとも初期値ｉａｍ−１乃至ｉａ０のいずれか１つが値“１”であり、同様に、少なくとも初期値ｉｂｎ−１乃至ｉｂ０のいずれか１つが値“１”であることとする。【００１７】  また、多項式係数生成部５は、外部から入力される初期情報、あるいは予め定められた所定の条件、例えば、日時情報のように常に変化する情報や熱雑音等の物理現象を利用して得られる条件に従って、第２線形フィードバックシフトレジスタ３の特性多項式の係数ｓ（ｓｎ−１，ｓｎ−２，…，ｓ２，ｓ１）を生成し、第２線形フィードバックシフトレジスタ３へ供給する機能を有する。【００１８】  また、擬似乱数出力部６は、第１線形フィードバックシフトレジスタ２から順次出力されるビット列ｒａ（ｒａ０，ｒａ１，…，ｒａｈ−１，ｒａｈ）と、および第２線形フィードバックシフトレジスタ３から順次出力されるビット列ｒｂ（ｒｂ０，ｒｂ１，…，ｒｂｈ−１，ｒｂｈ）とに基づいて、各ビットの排他的論理和を求め所定のビット長の擬似乱数ｒ（ｒ０，ｒ１，…，ｒｈ−１，ｒｈ）を生成し、出力する機能を有する。【００１９】  第１線形フィードバックシフトレジスタ２は、図２に示すように、ｍ個のフリップフロップ回路とＡＮＤ回路、およびＸＯＲ回路から構成される。この第１線形フィードバックシフトレジスタ２の特性多項式は、予め定められた原始多項式ａｍｘｍ＋ａｍ−１ｘｍ−１＋ａｍ−２ｘｍ−２＋…＋ａ２ｘ２＋ａ１ｘ＋ａ０（ただし、ａｍ＝１及びａ０＝１）であり、ＡＮＤ回路それぞれに原始多項式の係数ａ（ａｍ−１，…，ａ１）が設定される。【００２０】  従って、ａｉ＝０（０＜ｉ＜ｍ）の時は、フリップフロップＦＡｉ−１（０＜ｉ＜ｍ）から出力される値に関係なくＡＮＤ回路からは“０”が出力され、ａｉ＝１（０＜ｉ＜ｍ）の時は、フリップフロップＦＡｉ−１（０＜ｉ＜ｍ）から出力される値が出力される。【００２１】  第２線形フィードバックシフトレジスタ３は、図３に示すように、ｎ個のフリップフロップ回路とＡＮＤ回路、およびＸＯＲ回路から構成される。この第２線形フィードバックシフトレジスタ３の特性多項式をｂｎｘｎ＋ｂｎ−１ｘｎ−１＋ｂｎ−２ｘｎ−２＋…＋ｂ２ｘ２＋ｂ１ｘ＋ｂ０とすると、ＡＮＤ回路それぞれに特性多項式の係数ｂ（ｂｎ−１，…，ｂ１＝係数ｓ）が設定される。【００２２】  従って、ｂｊ＝０（０＜ｊ＜ｎ）の時は、フリップフロップＦＢｊ−１（０＜ｊ＜ｎ）から出力される値に関係なくＡＮＤ回路からは“０”が出力され、ｂｊ＝１（０＜ｊ＜ｎ）の時は、フリップフロップＦＢｊ−１（０＜ｊ＜ｎ）から出力される値が出力される。【００２３】  次に、擬似乱数生成装置１Ａの動作について、図４のフローチャートに基づいて説明する。【００２４】  擬似乱数生成装置１Ａが擬似乱数生成の処理を開始すると、まず、初期値生成部４が、外部から入力される初期情報、あるいは予め定められた所定の条件に従って、初期値ｉａ（ｉａｍ−１，ｉａｍ−２，…，ｉａ１，ｉａ０）と初期値ｉｂ（ｉｂｎ−１，ｉｂｎ−２，…，ｉｂ１，ｉｂ０）を生成し（ステップＳ０１）、それぞれの初期値を第１線形フィードバックシフトレジスタ２と第２線形フィードバックシフトレジスタ３へ供給する。【００２５】  また、多項式係数生成部５が、外部から入力される初期情報、あるいは予め定められた所定の条件に従って、第２線形フィードバックシフトレジスタ３の特性多項式の係数ｓ（ｓｎ−１，ｓｎ−２，…，ｓ２，ｓ１）を生成し（ステップＳ０２）、第２線形フィードバックシフトレジスタ３へ供給する。【００２６】  第１線形フィードバックシフトレジスタ２と第２線形フィードバックシフトレジスタ３は、初期値生成部４と多項式係数生成部５から各初期値と係数が供給されると、各フリップフロップ回路とＡＮＤ回路に各初期値と係数を設定し、出力ビット数をカウントするカウンタｋの値をｋ＝０に設定する（ステップＳ０３）。第１線形フィードバックシフトレジスタ２の各フリップフロップ回路ＦＡｍ−１，ＦＡｍ−２，…，ＦＡ１，ＦＡ０には、初期値ｉａ（ｉａｍ−１，ｉａｍ−２，…，ｉａ１，ｉａ０）が設定され、各ＡＮＤ回路には、原始多項式の係数ａ（ａｍ−１，…，ａ１）が設定される。また、第２線形フィードバックシフトレジスタ３の各フリップフロップ回路ＦＢｎ−１，ＦＢｎ−２，…，ＦＢ１，ＦＢ０には、初期値ｉｂ（ｉｂｎ−１，ｉｂｎ−２，…，ｉｂ１，ｉｂ０）が設定され、各ＡＮＤ回路には、特性多項式の係数ｓ（ｓｎ−１，ｓｎ−２，…，ｓ２，ｓ１）が設定される。なお、図３の第２線形フィードバックシフトレジスタ３では、ｂｎ＝１，ｂ０＝１としているが、ｂｎおよびｂ０にＡＮＤ回路を設けて、他の係数と同様に任意の値を設定できるようにしてもよい。【００２７】  次に、第１線形フィードバックシフトレジスタ２にクロック信号を入力すると（ステップＳ０４）、第１線形フィードバックシフトレジスタ２は演算を行い、ビットｒａｋを出力する（ステップＳ０５）。同様に、第２線形フィードバックシフトレジスタ３にクロック信号を入力すると（ステップＳ０６���、第２線形フィードバックシフトレジスタ３は演算を行い、ビットｒｂｋを出力する（ステップＳ０７）。【００２８】  擬似乱数出力部６は、第１線形フィードバックシフトレジスタ２からビットｒａｋが出力され、第２線形フィードバックシフトレジスタ３からビットｒｂｋが出力されると、両ビット値の排他的論理和を求めビットｒｋを生成する（ステップＳ０８）。【００２９】  次に、第１線形フィードバックシフトレジスタ２と第２線形フィードバックシフトレジスタ３は、カウンタｋの値を１つインクリメント（ｋ←ｋ＋１）し（ステップＳ０９）、カウンタｋの値がｈの値を超えたかどうか判定する（ステップＳ１０）。カウンタｋの値がｈ以下の場合は、第１線形フィードバックシフトレジスタ２はステップＳ０４に戻ってビットｒａｋ＋１を出力し、第２線形フィードバックシフトレジスタ３はステップＳ０６に戻ってビットｒｂｋ−１を出力し、擬似乱数出力部６は、ビットｒｋ＋１を生成する。【００３０】  カウンタｋの値がｈより大きい場合は、擬似乱数生成装置１は擬似乱数生成処理を終了し、これまでに生成されたビットｒ０，ｒ１，…，ｒｈ−１，ｒｈが擬似乱数ｒ（ｒ０，ｒ１，…，ｒｈ−１，ｒｈ）として出力される（ステップＳ１１）。【００３１】  ここで、図５を用いて具体的に説明する。一例として、８ビットの擬似乱数ｒを出力するものとし、第１線形フィードバックシフトレジスタ２の原始多項式をｘ７＋ｘ３＋１とし、第１線形フィードバックシフトレジスタ２のフリップフロップ回路を７段構成として初期値ｉａ（ｉａ６，ｉａ５，…，ｉａ１，ｉａ０）＝（１，０，１，０，１，０，１）、第２線形フィードバックシフトレジスタ３のフリップフロップ回路を８段構成として初期値ｉｂ（ｉｂ７，ｉｂ６，…，ｉｂ１，ｉｂ０）＝（１，１，１，１，０，０，０，０）、第２線形フィードバックシフトレジスタ３の特性多項式の係数ｓ（ｓ７，ｓ６，…，ｓ２，ｓ１）＝（０，１，１，１，０，１，１）がそれぞれ設定されたとする。【００３２】  まず、１回目のクロック信号が入力されると、第１線形フィードバックシフトレジスタ２においては、ＦＡ０→ＦＡ１、ＦＡ１→ＦＡ２、…、ＦＡ５→ＦＡ６とビットがシフトして（ＦＡ６，ＦＡ５，ＦＡ４，ＦＡ３，ＦＡ２，ＦＡ１）＝（０，１，０，１，０，１）となる。第１線形フィードバックシフトレジスタ２の原始多項式をｘ７＋ｘ３＋１なので、ＦＡ６のビット“１”はＦＡ２からＦＡ３へ出力されるビット“１”との排他的論理和“０”をＦＡ０にフィードバックして図５の＋１の状態になり、第１線形フィードバックシフトレジスタ２は“０”をｒａ０として出力する。【００３３】  また、１回目のクロック信号が入力されると、第２線形フィードバックシフトレジスタ３においては、ＦＢ０→ＦＢ１、ＦＢ１→ＦＢ２、…、ＦＢ６→ＦＢ７とビットがシフトして（ＦＢ７，ＦＢ６，ＦＢ５，ＦＢ４，ＦＢ３，ＦＢ２，ＦＢ１）＝（１，１，１，０，０，０，０）となる。特性多項式の係数ｓ（ｓ７，ｓ６，…，ｓ２，ｓ１）＝（０，１，１，１，０，１，１）から、特性多項式はｘ８＋ｘ６＋ｘ５＋ｘ４＋ｘ２＋ｘ＋１なので、ＦＢ５からＦＢ６へ出力されるビット“１”と、ＦＢ３からＦＢ４へ出力さ���るビット“０”と、ＦＢ１からＦＢ２へ出力されるビット“０”と、ＦＢ０からＦＢ１へ出力されるビット“０”との排他的論理和“１”をＦＢ０にフィードバックして図５の＋１の状態になり、第２線形フィードバックシフトレジスタ３は“１”をｒｂ０として出力する。【００３４】  ２回目のクロック信号が入力されると、第１線形フィードバックシフトレジスタ２および第２線形フィードバックシフトレジスタ３は、同様にビットシフトを行い、原始多項式と特性多項式に基づいてフィードバックを行い、図５の＋２の状態となり、それぞれｒａ１＝０およびｒｂ１＝１を出力する。【００３５】  このように演算を繰り返すことによって、第１線形フィードバックシフトレジスタ２からは（ｒａ０，ｒａ１，…，ｒａ６，ｒａ７）＝（０，０，０，０，１，０，１，１）、第２線形フィードバックシフトレジスタ３からは（ｒｂ０，ｒｂ１，…，ｒｂ６，ｒｂ７）＝（１，１，１，１，１，０，０，１）が出力され、（ｒａ０，ｒａ１，…，ｒａ６，ｒａ７）＝（０，０，０，０，１，０，１，１）と（ｒｂ０，ｒｂ１，…，ｒｂ６，ｒｂ７）＝（１，１，１，１，１，０，０，１）との排他的論理和から擬似乱数ｒ（ｒ０，ｒ１，…，ｒ６，ｒ７）＝（１，１，１，１，０，０，１，０）が出力される。【００３６】＜第２の実施形態＞
第２の実施形態における擬似乱数生成装置１Ｂは、図６に示すように、第１線形フィードバックシフトレジスタ２、第２線形フィードバックシフトレジスタ３、初期値生成部４、多項式係数生成部５、擬似乱数出力部６、原始多項式選択部７、および原始多項式記憶部８を有する。なお、第１の実施形態と同じものについては、同じ番号を付し、その詳細な説明を省略する。【００３７】  原始多項式選択部７は、外部から入力される初期情報に従って、原始多項式記憶部８に記憶されている原始多項式を１つ選択し、特性多項式としてその原始多項式の係数ａ（ａｍ−１，…，ａ１）を第１線形フィードバックシフトレジスタ２へ供給する機能を有する。【００３８】  原始多項式記憶部８は、第１線形フィードバックシフトレジスタ２の各ＡＮＤ回路を設定するための原始多項式を識別情報と共に複数記憶する。なお、原始多項式を指定する識別情報としては番号を用いることができる。以下、識別番号と称する。この識別番号によって、原始多項式の係数より少ない情報量で各ＡＮＤ回路を設定することが可能であり、例えば、図６に示すように、ビット長を２ビットとすると、原始多項式記憶部８は、識別番号Ｎｏ．“００”はｘ７＋ｘ３＋１、識別番号Ｎｏ．“０１”はｘ７＋ｘ３＋ｘ２＋ｘ＋１、識別番号Ｎｏ．“１０”はｘ７＋ｘ４＋ｘ３＋ｘ２＋１、識別番号Ｎｏ．“１１”はｘ７＋ｘ６＋ｘ５＋ｘ４＋ｘ２＋ｘ＋１というような原始多項式を記憶する。【００３９】  次に、擬似乱数生成装置１Ｂの動作について、図７のフローチャートに基づいて説明する。【００４０】  擬似乱数生成装置１Ｂが擬似乱数生成の処理を開始すると、まず、原始多項式選択部７が、外部から入力される初期情報に従って、原始多項式記憶部８から原始多項式を１つ選択し（ステップＳ２１）、その選択した原始多項式の係数を特性多項式の係数ａ（ａｍ−１，…，ａ１）として第１線形フィードバックシフトレジスタ２へ供給する。【００４１】  また、初期値生成部４は、外部から入力される初期情報、あるいは予め定められた所定の条件に従って、初期値ｉａ（ｉａｍ−１，ｉａｍ−２，…，ｉａ１，ｉａ０）と初期値ｉｂ（ｉｂｎ−１，ｉｂｎ−２，…，ｉｂ１，ｉｂ０）を生成し（ステップＳ２２）、それぞれの初期値を第１線形フィードバックシフトレジスタ２と第２線形フィードバックシフトレジスタ３へ供給する。【００４２】  また、多項式係数生成部５が、外部から入力される初期情報、あるいは予め定められた所定の条件に従って、第２線形フィードバックシフトレジスタ３の特性多項式の係数ｓ（ｓｎ−１，ｓｎ−２，…，ｓ２，ｓ１）を生成し（ステップＳ２３）、第２線形フィードバックシフトレジスタ３へ供給する。【００４３】  第１線形フィードバックシフトレジスタ２と第２線形フィードバックシフトレジスタ３は、原始多項式選択部７、初期値生成部４、および多項式係数生成部５から各初期値と係数が供給されると、各フリップフロップ回路とＡＮＤ回路に各初期値と係数を設定し、出力ビット数をカウントするカウンタｋの値をｋ＝０に設定する（ステップＳ２４）。第１線形フィードバックシフトレジスタ２の各フリップフロップ回路ＦＡｍ−１，ＦＡｍ−２，…，ＦＡ１，ＦＡ０には、���期値ｉａ（ｉａｍ−１，ｉａｍ−２，…，ｉａ１，ｉａ０）が設定され、各ＡＮＤ回路には、原始多項式選択部７から供給された特性多項式の係数ａ（ａｍ−１，…，ａ１）が設定される。また、第２線形フィードバックシフトレジスタ３の各フリップフロップ回路ＦＢｎ−１，ＦＢｎ−２，…，ＦＢ１，ＦＢ０には、初期値ｉｂ（ｉｂｎ−１，ｉｂｎ−２，…，ｉｂ１，ｉｂ０）が設定され、各ＡＮＤ回路には、特性多項式の係数ｓ（ｓｎ−１，ｓｎ−２，…，ｓ２，ｓ１）が設定される。なお、図３の第２線形フィードバックシフトレジスタ３では、ｂｎ＝１，ｂ０＝１としているが、ｂｎおよびｂ０にＡＮＤ回路を設けて、他の係数と同様に任意の値を設定できるようにしてもよい。【００４４】  以降、第１の実施形態（ステップＳ０４〜ステップＳ１１）と同様の処理を行って擬似乱数ｒ（ｒ０，ｒ１，…，ｒｈ−１，ｒｈ）を出力する（ステップＳ２５〜ステップＳ３２）。【００４５】＜第３の実施形態＞
第３の実施形態として、２つの擬似乱数生成装置１、例えば送信装置側に設けられた擬似乱数生成装置１と受信装置側に設けられた擬似乱数生成装置１とで特性多項式の係数と初期値（イニシャルデータ）を共有して、同じ擬似乱数を生成する擬似乱数生成装置１Ｃを示す。【００４６】  第３の実施形態における擬似乱数生成装置１Ｃは、図８に示すように、第１線形フィードバックシフトレジスタ２、第２線形フィードバックシフトレジスタ３、初期値生成部４、多項式係数生成部５、擬似乱数出力部６、原始多項式選択部７、原始多項式記憶部８、および通信部９を有する。なお、第１の実施形態および第２の実施形態と同じものについては、同じ番号を付し、その詳細な説明を省略する。また、便宜的に、イニシャルデータ送信側の擬似乱数生成装置１の構成要件には“ｔ”の文字を、イニシャルデータ受信側の擬似乱数生成装置１の構成要件には“ｒ”の文字を付す。【００４７】  通信部９は、原始多項式選択部７が選択した原始多項式の識別番号、初期値生成部４が生成した初期値ｉａ（ｉａｍ−１，ｉａｍ−２，…，ｉａ１，ｉａ０）および初期値ｉｂ（ｉｂｎ−１，ｉｂｎ−２，…，ｉｂ１，ｉｂ０）、多項式係数生成部５が生成した特性多項式の係数ｓ（ｓｎ−１，ｓｎ−２，…，ｓ２，ｓ１）を基に、原始多項式の識別番号、特性多項式の係数の初期値、および各初期値のそれぞれのビット列からなるイニシャルデータを生成する機能、およびそのイニシャルデータを他の擬似乱数生成装置１と送受信する機能を有する。【００４８】  また、通信部９は、イニシャルデータを受信した場合は、イニシャルデータから初期値ｉｂ（ｉｂｎ−１，ｉｂｎ−２，…，ｉｂ１，ｉｂ０）と特性多項式の係数ｓ（ｓｎ−１，ｓｎ−２，…，ｓ２，ｓ１）とを抽出し、第２線形フィードバックシフトレジスタ３に供給する機能、イニシャルデータから初期値ｉａ（ｉａｍ−１，ｉａｍ−２，…，ｉａ１，ｉａ０）を抽出し、第１線形フィードバックシフトレジスタ２に供給する機能、イニシャルデータから原始多項式の識別番号を抽出し、原始多項式選択部７に供給する機能を有する。【００４９】  次に、２つの擬似乱数生成装置１Ｃで同じ擬似乱数を生成する際の動作について、図９のシーケンス図に基づいて説明する。【００５０】  擬似乱数生成装置１Ｃｔが擬似乱数生成の処理を開始すると、まず、原始多項式選択部７ｔが、外部から入力される初期情報に従って、原始多項式記憶部８ｔから原始多項式を１つ選択し（ステップＳ４１）、その選択した原始多項式の係数を特性多項式の係数ａ（ａｍ−１，…，ａ１）として第１線形フィードバックシフトレジスタ２ｔへ供給すると共に、通信部９ｔへ原始多項式の識別番号を供給する。【００５１】  また、初期値生成部４ｔは、外部から入力される初期情報、あるいは予め定められた所定の条件に従って、初期値ｉａ（ｉａｍ−１，ｉａｍ−２，…，ｉａ１，ｉａ０）と初期値ｉｂ（ｉｂｎ−１，ｉｂｎ−２，…，ｉｂ１，ｉｂ０）を生成し（ステップＳ４２）、それぞれの初期値を第１線形フィードバックシフトレジスタ２ｔ、第２線形フィードバックシフトレジスタ３ｔ、および通信部９ｔへ供給する。【００５２】  また、多項式係数生成部５ｔが、外部���ら入力される初期情報、あるいは予め定められた所定の条件に従って、第２線形フィードバックシフトレジスタ３ｔの特性多項式の係数ｓ（ｓｎ−１，ｓｎ−２，…，ｓ２，ｓ１）を生成し（ステップＳ４３）、第２線形フィードバックシフトレジスタ３ｔと通信部９ｔへ供給する。【００５３】  第１線形フィードバックシフトレジスタ２ｔと第２線形フィードバックシフトレジスタ３ｔは、原始多項式選択部７ｔ、初期値生成部４ｔ、および多項式係数生成部５ｔから各初期値と係数が供給されると、各フリップフロップ回路とＡＮＤ回路に各初期値と係数を設定し、出力ビット数をカウントするカウンタｋの値をｋ＝０に設定する（ステップＳ４４）。第１線形フィードバックシフトレジスタ２ｔの各フリップフロップ回路ＦＡｍ−１，ＦＡｍ−２，…，ＦＡ１，ＦＡ０には、初期値ｉａ（ｉａｍ−１，ｉａｍ−２，…，ｉａ１，ｉａ０）が設定され、各ＡＮＤ回路には、原始多項式選択部７ｔから供給された特性多項式の係数ａ（ａｍ−１，…，ａ１）が設定される。また、第２線形フィードバックシフトレジスタ３ｔの各フリップフロップ回路ＦＢｎ−１，ＦＢｎ−２，…，ＦＢ１，ＦＢ０には、初期値ｉｂ（ｉｂｎ−１，ｉｂｎ−２，…，ｉｂ１，ｉｂ０）が設定され、各ＡＮＤ回路には、特性多項式の係数ｓ（ｓｎ−１，ｓｎ−２，…，ｓ２，ｓ１）が設定される。なお、図３の第２線形フィードバックシフトレジスタ３ｔでは、ｂｎ＝１，ｂ０＝１としているが、ｂｎおよびｂ０にＡＮＤ回路を設けて、他の係数と同様に任意の値を設定できるようにしてもよい。【００５４】  また、通信部９ｔは、原始多項式の識別番号、特性多項式の係数、および各初期値のそれぞれのビット値からなるイニシャルデータを生成し擬似乱数生成装置１Ｃｒへ送信する（ステップＳ４５）。この時、通信部９ｔは、所定の暗号化方式でイニシャルデータを暗号化して送信しても良い。【００５５】  例えば、原始多項式の識別番号が２ビット（“１０”）、初期値ｉａが７ビット（“１０１０１０１”）、初期値ｉｂが８ビット（“１１１１００００”）、特性多項式の係数ｓが７ビット（“０１１１０１１”）であった場合、イニシャルデータは２４ビットのデータ列（識別番号｜初期値ｉａ｜初期値ｉｂ｜係数ｓ）＝（１０１０１０１０１１１１１０００００１１１０１１）となる。【００５６】  以降、擬似乱数生成装置１Ｃｔは、第１の実施形態（ステップＳ０４〜ステップＳ１１）と同様の処理を行って擬似乱数ｒ（ｒ０，ｒ１，…，ｒｈ−１，ｒｈ）を出力する（ステップＳ４６〜ステップＳ５１）。【００５７】  一方、擬似乱数生成装置１Ｃｒの通信部９ｒは、擬似乱数生成装置１Ｃｔからイニシャルデータを受信すると（ステップＳ５２）、イニシャルデータから初期値ｉｂ（ｉｂｎ−１，ｉｂｎ−２，…，ｉｂ１，ｉｂ０）と特性多項式の係数ｓ（ｓｎ−１，ｓｎ−２，…，ｓ２，ｓ１）とを抽出し、第２線形フィードバックシフトレジスタ３ｒに供給し、イニシャルデータから初期値ｉａ（ｉａｍ−１，ｉａｍ−２，…，ｉａ１，ｉａ０）を抽出し、第１線形フィードバックシフトレジスタ２ｒに供給し、イニシャルデータから原始多項式の識別番号を抽出し、原始多項式選択部７ｒに供給する。なお、受信したイニシャルデータが暗号化されている場合は、通信部９は、復号化してイニシャルデータを得る。【００５８】  原始多項式選択部７ｒは、原始多項式の識別番号が供給されると、その識別番号に該当する原始多項式を原始多項式記憶部８ｒから１つ選択し（ステップＳ５３）、その選択した原始多項式の係数を特性多項式の係数ａ（ａｍ−１，…，ａ１）として第１線形フィードバックシフトレジスタ２ｒへ供給する。【００５９】  また、第１線形フィードバックシフトレジスタ２ｒと第２線形フィードバックシフトレジスタ３ｒは、原始多項式選択部７ｒ、および通信部９ｒから各初期値と各係数が供給されると、各フリップフロップ回路とＡＮＤ回路に各初期値と係数を設定し、出力ビット数をカウントするカウンタｋの値をｋ＝０に設定する（ステップＳ５４）。【００６０】  以降、擬似乱数生成装置１Ｃｒは、第１の実施形態（ステップＳ０４〜ステップＳ１１）と同様の処理を行って擬似乱数ｒ（ｒ０，ｒ１，…，ｒｈ−１，ｒｈ）を出力する（ステップＳ５５〜ステップＳ６０）。【００６１】  このようにして、２つの擬似乱数生成装置１でイニシャルデータを共有することによって、同じ擬似乱数を生成することが可能となる。【００６２】  なお、擬似乱数生成装置１は、上記の機能を記述した擬似乱数生成プログラムを汎用コンピュータに実行させることによって実現させても良い。この擬似乱数生成プログラムは、記録媒体から読み取られて汎用コンピュータに実行されても良いし、ネットワークを介して外部から伝送されて汎用コンピュータに実行されても良い。
【産業上の利用可能性】
【００６３】  本発明によれば、常に所定のＭ系列より長い周期の擬似乱数列を生成することが可能となり、初期値だけでなく、特性多項式の係数も任意に設定できるため、生成された擬似乱数列を観測されてもその後生成される擬似乱数列を推測することは困難であり、生成される擬似乱数列の安全性を確保することができ、通信されるデータの安全性が保障される。識別情報と原始多項式との対応が分からなければ、通信されるデータの解読は困難である。【００６４】  また、第１の線形フィードバックシフトレジスタの特性多項式として設定される原始多項式の選択には、その識別情報を用いることにより、係数を送受信するより少ないデータ量で済む。つまり、識別情報を原始多項式より少ない情報量とすれば、情報量を少なくすることができる。
【図１】
2005073842.tif 000002
【図２】
2005073842.tif 000003
【図３】
2005073842.tif 000004
【図４】
2005073842.tif 000005
【図５】
2005073842.tif 000006
【図６】
2005073842.tif 000007
【図７】
2005073842.tif 000008
【図８】
2005073842.tif 000009
【図９】
2005073842.tif 000010
【手続補正書】
【提出日】平成17年11月30日(2005.11.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１
【補正方法】変更
【補正の内容】
【請求項１】（補正後）所定のビット長の擬似乱数列を生成する擬似乱数生成装置（１）であって、
ｍ段のシフトレジスタを有し、特定多項式として原始多項式を用い、前記ｍ段のシフトレジスタに第１の初期値と第１の係数を設定して所定のビット長のビット列を出力する第１の線形フィードバックシフトレジスタ（２）と、
ｎ段のシフトレジスタを有し、特定多項式を用い、前記ｎ段のシフトレジスタに第２の初期値と第２の係数を設定して所定のビット長のビット列を出力する第２の線形フィードバックシフトレジスタ（３）と、
所定の条件に従って、前記第１および第２の初期値を生成し、それぞれの当該初期値を前記第１の線形フィードバックシフトレジスタ（２）および前記第２の線形フィードバックシフトレジスタ（３）へ供給する初期値生成部（４）と、
所定の条件に従って、前記第２の線形フィードバックシフトレジスタ（３）で用いる前記第２の係数を生成し、前記第２の線形フィードバックシフトレジスタ（３）へ供給する多項式係数生成部（５）と、
前記第１の線形フィードバッグシフトレジスタ（２）で用いる原始多項式を、前記原始多項式を指定する識別情報と共に複数記憶する原始多項式記憶部（８）と、
所定の条件に従って、前記原始多項式記憶部（８）に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の係数として前記第１の線形フィードバックシフトレジスタ（２）へ供給する原始多項式選択部（７）と、
前記第１の線形フィードバックシフトレジスタ（２）から出力されるビット列と、前記第２の線形フィードバックシフトレジスタ（３）から出力されるビット列とに基づいて、各ビットの論理演算から所定のビット長の擬似乱数列を生成し、出力する擬似乱数出力部（６）と、
を備えることを特徴とする擬似乱数生成装置（１）。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２
【補正方法】変更
【補正の内容】
【請求項２】前記擬似乱数生成装置（１Ｃ）は、
前記原始多項式選択部（７）によって選択された前記原始多項式の識別情報、前記初期値生成部（４）によって生成された前記第１および第２の初期値、前記多項式係数生成部（５）によって生成された前記第２の係数のそれぞれからなるイニシャルデータを生成し、当該イニシャルデータを他の擬似乱数生成装置（１Ｃ）へ送出し、当該イニシャルデータを他の擬似乱数生成装置（１Ｃ）から受信した場合は、当該イニシャルデータから前記第１および第２の初期値を抽出して前記第１の線形フィードバックシフトレジスタ（２）と前記第２の線形フィードバックシフトレジスタ（３）に供給し、当該イニシャルデータから前記第２の係数を抽出して前記第２の線形フィードバックシフトレジスタ（３）へ供給し、当該イニシャルデータから前記原始多項式の識別情報を抽出して前記原始多項式選択部（７）に供給する通信部（９）を備え、
前記原始多項式選択部（７）は、前記通信部（９）によって抽出された前記識別情報を基に、前記原始多項式記憶部（８）に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の係数として前記第１の線形フィードバックシフトレジスタ（２）へ供給することを特徴とする請求の範囲第１項に記載の擬似乱数生成装置。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項３
【補正方法】変更
【補正の内容】
【請求項３】コンピュータによって所定のビット長の擬似乱数列を生成する処理を実行させる疑似乱数生成プログラムであって、
当該擬似乱数生成プログラムは、前記コンピュータを、
ｍ段のシフトレジスタを有し、特定多項式として原始多項式を用い、前記ｍ段のシフトレジスタに第１の初期値と第１の係数を設定して所定のビット長のビット列を出力する第１の線形フィードバックシフトレジスタと、
ｎ段のシフトレジスタを有し、特定多項式を用い、前記ｎ段のシフトレジスタに第２の初期値と第２の係数を設定して所定のビット長のビット列を出力する第２の線形フィードバックシフトレジスタと、
所定の条件に従って、前記第１および第２の初期値を生成し、それぞれの当該初期値を前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタへ供給する初期値生成手段と、
所定の条件に従って、前記第２の線形フィードバックシフトレジスタで用いる前記第２の係数を生成し、前記第２の線形フィードバックシフトレジスタへ供給する多項式係数生成手段と、
前記第１の線形フィードバックシフトレジスタで用いる原始多項式を、前記原始多項式を指定する識別情報と共に複数記憶する原始多項式記憶手段と、
所定の条件に従って、前記原始多項式記憶部に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の係数として前記第１の線形フィードバックシフトレジスタへ供給する原始多項式選択手段と、
前記第１の線形フィードバックシフトレジスタから出力されるビット列と、前記第２の線形フィードバックシフトレジスタから出力されるビット列とに基づいて、各ビットの論理演算から所定のビット長の擬似乱数列を生成し、出力する擬似乱数出力手段と、
して機能させることを特徴とする擬似乱数生成プログラム。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項４
【補正方法】変更
【補正の内容】
【請求項４】前記擬似乱数生成プログラムは、前記コンピュータを
前記原始多項式選択手段によって選択された前記原始多項式の識別情報、前記初期値生成手段によって生成された前記第１および第２の初期値、前記多項式係数生成手段によって生成された前記第２の係数のそれぞれからなるイニシャルデータを生成し、当該イニシャルデータを他の擬似乱数生成装置へ送出し、当該イニシャルデータを他の擬似乱数生成装置から受信した場合は、当該イニシャルデータから前記第１および第２の初期値を抽出して前記第１の線形フィードバックシフトレジスタと前記第２の線形フィードバックシフトレジスタに供給し、当該イニシャルデータから前記第２の係数を抽出して前記第２の線形フィードバックシフトレジスタへ供給し、当該イニシャルデータから前記原始多項式の識別情報を抽出して前記原始多項式選択手段に供給する通信手段としても機能させ、
前記原始多項式選択手段は、前記通信手段によって抽出された前記識別情報を基に、前記原始多項式記憶手段に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の係数として前記第１の線形フィードバックシフトレジスタへ供給する手段であることを特徴とする請求の範囲第３項に記載の擬似乱数生成プログラム。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０００２
【補正方法】変更
【補正の内容】
【０００２】
たとえ非線形な処理を組み合わせた方法であっても、ある特定のアルゴリズムで擬似乱数が生成されるため、初期値や生成される擬似乱数列の一部からその後生成される擬似乱数が推測される恐れがあった。
［０００６］  また、複数の線形フィードバックシフトレジスタからいくつかのレジスタを選択して擬似乱数を生成する場合には、生成される擬似乱数列の推測は困難になるものの、任意の係数を特性多項式とする線形フィードバックシフトレジスタを組み合わせると、生成される擬似乱数列が必ずしもＭ系列（Ｍａｘｉｍｕｍ  ｌｅｎｇｔｈ  ｓｅｑｕｅｎｃｅｓ）とはならずに、短い周期で同じ擬似乱数列を繰り返し生成してしまうという問題があるため、予め特定の条件を満たす多項式を多数用意した中から選択して組み合わせる必要があった。これは実際の処理では、常に利用するわけではない線形フィードバックシフトレジスタを実装する必要があり効率的ではなかった。
【発明の開示】
［０００７］  本発明は、生成される擬似乱数列や送受信されるデータを観測されても、その後生成される擬似乱数列の推測が困難な暗号通信に好適な擬似乱数生成装置および擬似乱数生成プログラムを提供することを目的とする。
［０００８］  上記目的を達成するため、第１の態様に係る発明は、所定のビット長の擬似乱数列を生成する擬似乱数生成装置であって、ｍ段のシフトレジスタを有し、特定多項式として原始多項式を用い、前記ｍ段のシフトレジスタに第１の初期値と第１の係数を設定して所定のビット長のビット列を出力する第１の線形フィードバックシフトレジスタと、ｎ段のシフトレジスタを有し、特定多項式を用い、前記ｎ段のシフトレジスタに第２の初期値と第２の係数を設定して所定のビット長のビット列を出力する第２の線形フィードバックシフトレジスタと、所定の条件に従って、前記第１および第２の初期値を生成し、それぞれの当該初期値を前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタへ供給する初期値生成部と、所定の条件に従って、前記第２の線形フィードバックシフトレジスタで用いる前記第２の係数を生成し、前記第２の線形フィードバックシフトレジスタへ供給する多項式係数生成部と、前記第１の線形フィードバックシフトレジスタで用いる原始多項式を、前記原始多項式を指定する識別情報と共に複数記憶する原始多項式記憶部と、
２
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０００３
【補正方法】変更
【補正の内容】
【０００３】
所定の条件に従って、前記原始多項式記憶部に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の係数として前記第１の線形フィードバックシフトレジスタへ供給する原始多項式選択部と、前記第１の線形フィードバックシフトレジスタから出力されるビット列と、前記第２の線形フィードバックシフトレジスタから出力されるビット列とに基づいて、各ビットの論理演算から所定のビット長の擬似乱数列を生成し、出力する擬似乱数出力部と、を備える擬似乱数生成装置を要旨とする。
［０００９］  また、第２の態様に係る発明は、第１の態様に係る発明において、前記疑似乱数生成装置は、前記原始多項式選択部によって選択された前記原始多項式の識別情報、前記初期値生成部によって生成された前記第１および第２の初期値、前記多項式係数生成部によって生成された前記第２の係数のそれぞれからなるイニシャルデータを生成し、当該イニシャルデータを他の擬似乱数生成装置へ送出し、当該イニシャルデータを他の擬似乱数生成装置から受信した場合は、当該イニシャルデータから前記第１および第２の初期値を抽出して前記第１の線形フィードバックシフトレジスタと前記第２の線形フィードバックシフトレジスタに供給し、当該イニシャルデータから前記第２の係数を抽出して前記第２の線形フィードバックシフトレジスタへ供給し、当該イニシャルデータから前記原始多項式の識別情報を抽出して前記原始多項式選択部に供給する通信部を備え、前記原始多項式選択部は、前記通信部によって抽出された前記識別情報を基に、前記原始多項式記憶部に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の係数として前記第１の線形フィードバックシフトレジスタへ供給することを要旨とする。
［００１０］  また、上記目的を達成するため、第３の態様に係る発明は、コンピュータによって所定のビット長の擬似乱数列を生成する処理を実行させる擬似乱数生成プログラムであって、当該擬似乱数生成プログラムは、前記コンピュータを、ｍ段のシフトレジスタを有し、特定多項式として原始多項式を用い、前記ｍ段のシフトレジスタに第１の初期値と第１の係数を設定して所定のビット長のビット列を出力する第１の線形フィードバックシフトレジスタと、ｎ段のシフトレジスタを有し、特定多項式を用い、前記ｎ段のシフトレジスタに第２の初期値と第２の係数を設定して所定のビット長のビ
３
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
ット列を出力する第２の線形フィードバックシフトレジスタと、所定の条件に従って、前記第１およぴ第２の初期値を生成し、それぞれの当該初期値を前記第１の線形フィードバックシフトレジスタおよび前記第２の線形フィードバックシフトレジスタへ供給する初期値生成手段と、所定の条件に従って、前記第２の線形フィードバックシフトレジスタで用いる前記第２の係数を生成し、前記第２の線形フィードバックシフトレジスタへ供給する多項式係数生成手段と、前記第１の線形フィードバックシフトレジスタで用いる原始多項式を、前記原始多項式を指定する識別情報と共に複数記憶する原始多項式記憶手段と、所定の条件に従って、前記原始多項式記憶部に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記第１の係数として前記第１の線形フィードバックシフトレジスタへ供給する原始多項式選択手段と、前記第１の線形フィードバックシフトレジスタから出力されるビット列と、前記第２の線形フィードバックシフトレジスタから出力されるビット列とに基づいて、各ビットの論理演算から所定のビット長の擬似乱数列を生成し、出力する擬似乱数出力手段として機能させる擬似乱数生成プログラムを要旨とする。
［００１１］  また、第４の態様に係る発明は、第３の態様に係る発明において、前記擬似乱数生成プログラムは、前記コンピュータを前記原始多項式選択手段によって選択された前記原始多項式の識別情報、前記初期値生成手段によって生成された前記第１および第２の初期値、前記多項式係数生成手段によって生成された前記第２の係数のそれぞれからなるイニシャルデータを生成し、当該イニシャルデータを他の擬似乱数生成装置へ送出し、当該イニシャルデータを他の擬似乱数生成装置から受信した場合は、当該イニシャルデータから前記第１および第２の初期値を抽出して前記第１の線形フィードバックシフトレジスタと前記第２の線形フィードバックシフトレジスタに供給し、当該イニシャルデータから前記第２の係数を抽出して前記第２の線形フィードバックシフトレジスタへ供給し、当該イニシャルデータから前記原始多項式の識別情報を抽出して前記原始多項式選択手段に供給する通信手段としても機能させ、前記原始多項式選択手段は、前記通信手段によって抽出された前記識別情報を基に、前記原始多項式記憶手段に記憶されている原始多項式を１つ選択し、その原始多項式の係数を前記
４
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
第１の係数として前記第１の線形フィードバックシフトレジスタへ供給することを要旨とする。
【図面の簡単な説明】
［００１２］［図１］図１は、第１の実施形態における擬似乱数生成装置の機能構成を示す図である。
［図２］図２は、第１線形フィードバックシフトレジスタの回路構成を示す図である。
［図３］図３は、第２線形フィードバックシフトレジスタの回路構成を示す図である。
［図４］図４は、第１の実施形態における擬似乱数生成の処理を示すフローチャートである。
［図５］図５は、第１線形フィードバックシフトレジスタと第２線形フィードバックシフトレジスタの値の遷移を示す図である。
［図６］図６は、第２の実施形態における擬似乱数生成装置の機能構成を示す図である。
［図７］図７は、第２の実施形態における擬似乱数生成の処理を示すフローチャートである。
［図８］図８は、第３の実施形態における擬似乱数生成装置の機能構成を示す図である。
［図９］図９は、第３の実施形態における擬似乱数生成の処理を示すフローチャートである。
【発明を実施するための最良の形態】
［００１３］  本発明の実施形態を、図１〜図９を用いて説明する。なお、擬似乱数生成装置１が生成する擬似乱数のビット長をｈ＋１とする。
［００１４］＜第１の実施形態＞
第１の実施形態における擬似乱数生成装置１Ａは、図１に示すように、第１線形フィードバックシフトレジスタ２、第２線形フィードバックシフトレジスタ３、初期値生成部４、多項式係数生成部５、および疑似乱数出力部６を有する。
［００１５］第１線形フィードバックシフトレジスタ２は、ｍ次の線形フィードバックシフトレジスタであり、ｍ個のフリップフロップ回路を有する（詳細については後述）。また、第２線形
５
【国際調査報告】
2005073842.tif 000011
2005073842.tif 000012