Specification :(In Japanese)乱数発生器及び乱数発生器の作成方法

Country	(In Japanese)日本国特許庁(JP)
Gazette	(In Japanese)特許公報(B2)
Patent Number	P4982750
Publication number	P2008-176698A
Date of registration	May 11, 2012
Date of issue	Jul 25, 2012
Date of publication of application	Jul 31, 2008
Title of the invention, or title of the device	(In Japanese)乱数発生器及び乱数発生器の作成方法
IPC (International Patent Classification)	G06F   7/58        (2006.01) H03K   3/84        (2006.01) G09C   1/00        (2006.01)
FI (File Index)	G06F 7/58 A H03K 3/84 Z G09C 1/00 650B
Number of claims or invention	4
Total pages	17
Application Number	P2007-011347
Date of filing	Jan 22, 2007
Date of request for substantive examination	Jan 21, 2010
Patentee, or owner of utility model right	(In Japanese)【識別番号】504133110 【氏名又は名称】国立大学法人電気通信大学
Inventor, or creator of device	(In Japanese)【氏名】渡部 信吾 【氏名】阿部 公輝
Representative	(In Japanese)【識別番号】100083806、【弁理士】、【氏名又は名称】三好 秀和 【識別番号】100101247、【弁理士】、【氏名又は名称】高橋 俊一 【識別番号】100120455、【弁理士】、【氏名又は名称】勝 治人
Examiner	(In Japanese)【審査官】田中 友章
Document or reference	(In Japanese)Schellekens,D. et al.，“FPGA Vendor Agnostic True Random Number Generator”，International Conference on Field Programmable Logic and Applications, 2006. FPL'06.，2006年 8月30日，p.1-6 Suner,B. et al.，“A Provably Secure True Random Number Generator with Built-in Tolerance to Active Attacks”，IEEE Transactions on Computers，2007年 1月，Vol.56, No.1,，P.109-119 Kohlbrenner,P. et al.，“An Embedded True Random Number Gererator for FPGAs”，FPGA '04 Proceedings of the 2004 ACM/SIGDA 12th International Symposium on Field Programmable Gate Arrays，2004年，p.71-78
Field of search	Ｇ０６Ｆ ７／５８ Ｇ０９Ｃ １／００ Ｈ０３Ｋ ３／８４
Scope of claims	(In Japanese)【請求項1】 複数の論理素子で構成されるリングオシレータの当該論理素子間のいずれか又は全てに少なくとも一個以上の配線資源からなる遅延回路が設けられているリングオシレータと、 前記リングオシレータの出力に接続され、所定のサンプリング周波数でジッター出力を抽出するサンプリング回路とを備え、 前記論理素子は、プログラム可能な集積回路内に設けられるロジックエレメントで構成され、前記配線資源は、前記集積回路において、前記ロジックエレメント近傍に配置されるローカルインターコネクト、カラム方向に延伸するカラムインターコネクト、及び／又はロウ方向に延伸するロウインターコネクトで構成されることを特徴とする乱数発生器。 【請求項2】 複数の論理素子で構成されるリングオシレータの当該論理素子間のいずれか又は全てに少なくとも一個以上の配線資源からなる遅延回路が設けられている複数のリングオシレータと、 前記複数のリングオシレータの出力に接続され,前記複数のリングオシレータの排他的論理和出力を発生する排他的論理和回路と、 前記排他的論理和回路の出力に接続され,所定のサンプリング周波数でジッター出力を抽出するサンプリング回路とを備え、 前記論理素子は、プログラム可能な集積回路内に設けられるロジックエレメントで構成され、前記配線資源は、前記集積回路において、前記ロジックエレメント近傍に配置されるローカルインターコネクト、カラム方向に延伸するカラムインターコネクト、及び／又はロウ方向に延伸するロウインターコネクトで構成されることを特徴とする乱数発生器。 【請求項3】 前記サンプリング回路の出力に接続され,前記ジッター出力を加工処理する後処理回路を更に備えることを特徴とする請求項1又は請求項2に記載の乱数発生器。 【請求項4】 複数のロジックエレメントと，当該ロジックエレメントを電気的に接続する配線資源と、当該配線資源の交差点に設けられ、配線切り替えを行うスイッチング素子を少なくとも備えるプログラム可能な集積回路内に乱数発生器を設ける乱数発生器の作成方法において、 前記複数のロジックエレメントを用いて少なくとも一つのリングオシレータを形成するリングオシレータ形成ステップと、 前記リングオシレータを構成する一のロジックエレメントと他のロジックエレメントの間に、少なくとも一つ以上のスイッチング素子を含む一定長の配線資源を設けるジッター生成ステップと、 前記リングオシレータ形成ステップ及びジッター生成ステップにより生成された出力信号を所定のサンプリング周波数でサンプリング抽出するサンプリング抽出ステップと を有する乱数発生器の作成方法。
Detailed description of the invention	(In Japanese)【技術分野】 【0001】 本発明は、乱数発生器に関し、特にリングオシレータを基本構成とする真の乱数発生を可能とする乱数発生器及び乱数発生器の作成方法に関する。 【背景技術】 【0002】 モンテカルロ法などのシミュレーション分野や、暗号およびセキュリティー分野における鍵生成、鍵交換、回路のマスクなどでは、大量の乱数やよく散らばった，乱数性のよい乱数が必要とされることが多い。 【0003】 乱数には大きく分けて真の乱数と疑似乱数がある。真の乱数とは、予測が不可能で再現性のない乱数のことである。通常は、熱雑音や核分裂などの本質的にランダムな物理的現象を基に乱数を生成し、離散化・符号化の後に後処理をする。このため、アナログ回路を必要とするので、外部回路を付加することが多い。外部に特別な回路が必要となることから、実装の高密度化や低消費電力化，耐タンパー性などの点で問題がある。そのため、外部回路によらず、FPGA（Field Programmable Gate Array）のみを用いて真の乱数を生成する試みがなされている。 【0004】 例えば、アナログPLL（Phase locked Loop）を用いて乱数を生成する例では、アナログPLLを搭載しているある特定のFPGAのみでしか構成できない。 【0005】 又、FPGAの外部に抵抗とコンデンサからなる外部回路を付加して乱数を生成する例では、FPGAの製造元やその種類に依存せず乱数を発生することができるが、乱数の生成が外部の回路に依存するため、付加回路が除去されれば乱数の生成が止まること、及び生成する乱数が外部からサンプリング可能であることから、セキュリティーの面で問題点がある。 【0006】 一方、プログラマブルなデジタル回路であるFPGAを用い外部回路を要しない真の乱数の生成手法が提案されている（例えば、非特許文献1及び2参照。）。FPGAの内部で閉じた回路が構成できるので、耐タンパー性，コストの削減，IP(Intellectual Property)コアとしての回路の面で有用である。非特許文献1においては、デジタル回路のみを用い、複数のリングオシレータによるジッターを基にした乱数生成器を理論的な立場から検討している。非特許文献1においては、CPLD（Complex Programmable Logic Device）やFPGAも検討しているが実際の評価は行っていない。又、非特許文献2においては、特定の条件に限定した実装を行い評価を行っている。 【0007】 一方、縦続接続された複数段の論理ゲート出力の一部を帰還抵抗を介して入力側に帰還させて発振する発振部を備え、論理ゲートには、所定の抵抗を介して電源電圧が供給され、所定の抵抗は絶縁層を介して信号線に積層されていることを特徴とする乱数発生集積回路については、既に開示されている（例えば、特許文献1参照。）。 【特許文献1】特許第3650826号公報 【非特許文献1】ビー・スーナー，ダブリュー・ジェイ・マーティン，及びデイー・アール・スティンソン（B. Suner, W.J.Martin, and D.R.Stinson）著, “証明可能な安全性を有し攻撃耐性を内蔵する真の乱数生成器（A Provably Secure True Random Number Generator with Built-in Tolerance to Active Attacks）”, March 29, 2006,http://www.cacr.math.uwaterloo.ca/~dstinson/papers/rng-IEEE.pdf 【非特許文献2】ディー・シェレケンス,ビィー・プレニール，及びアイ・ベルボウヘーデ（D.Schellekens, B. Preneel, and I. Verbauwhede）著, “FPGAベンダーに依存しない真の乱数生成器（FPGA vendor agnostic True Random Number Generator）”, Proc. 16th International Conference on Field Programmable Logic and Applications (FPL 2006), August 28-30，セッションM3.A Cryptographic Applications ，http://www.cosic.esat.kuleuven.be/publications/article-790.pdf 【発明の開示】 【発明が解決しようとする課題】 【0008】 本発明は、積極的に配線資源による遅延回路 を導入し、配線資源のジッターも利用するリングオシレータによる真の乱数発生器及び乱数発生器の作成方法を提供することを目的とする。 【0009】 また本発明は、プログラム可能な集積回路において、積極的に配線資源による遅延回路 を導入し、配線資源のジッターも利用するリングオシレータによる真の乱数発生器及び乱数発生器の作成方法を提供することを目的とする。 【課題を解決するための手段】 【0010】 上記目的を達成するための本発明の請求項1に記載の乱数発生器は、 複数の論理素子で構成されるリングオシレータの当該論理素子間のいずれか又は全てに少なくとも一個以上の配線資源からなる遅延回路が設けられているリングオシレータと、前記リングオシレータの出力に接続され、所定のサンプリング周波数でジッター出力を抽出するサンプリング回路とを備え、前記論理素子は、プログラム可能な集積回路内に設けられるロジックエレメントで構成され、前記配線資源は、前記集積回路において、前記ロジックエレメント近傍に配置されるローカルインターコネクト、カラム方向に延伸するカラムインターコネクト、及び／又はロウ方向に延伸するロウインターコネクトで構成されることを特徴とする。 【0011】 本発明の請求項2に記載の乱数発生器は、複数の論理素子で構成されるリングオシレータの当該論理素子間のいずれか又は全てに少なくとも一個以上の配線資源からなる遅延回路が設けられている複数のリングオシレータと、前記複数のリングオシレータの出力に接続され,前記複数のリングオシレータの排他的論理和出力を発生する排他的論理和回路と、前記排他的論理和回路の出力に接続され,所定のサンプリング周波数でジッター出力を抽出するサンプリング回路とを備え、前記論理素子は、プログラム可能な集積回路内に設けられるロジックエレメントで構成され、前記配線資源は、前記集積回路において、前記ロジックエレメント近傍に配置されるローカルインターコネクト、カラム方向に延伸するカラムインターコネクト、及び／又はロウ方向に延伸するロウインターコネクトで構成されることを特徴とする。 【0013】 本発明の請求項3に記載の乱数発生器は、請求項1又は請求項2に記載の乱数発生器において、前記サンプリング回路の出力に接続され,前記ジッター出力を加工処理する後処理回路を更に備えることを特徴とする。 【0014】 本発明の請求項4に記載の乱数発生器の作成方法は、複数のロジックエレメントと，当該ロジックエレメントを電気的に接続する配線資源と，当該配線資源の交差点に設けられ，配線切り替えを行うスイッチング素子を少なくとも備えるプログラム可能な集積回路内に乱数発生器を設ける乱数発生器の作成方法において、前記複数のロジックエレメントを用いて少なくとも一つのリングオシレータを形成するリングオシレータ形成ステップと、前記リングオシレータを構成する一のロジックエレメントと他のロジックエレメントの間に、少なくとも一つ以上のスイッチング素子を含む一定長の配線資源を設けるジッター生成ステップと、前記リングオシレータ形成ステップ及びジッター生成ステップにより生成された出力信号を所定のサンプリング周波数でサンプリング抽出するサンプリング抽出ステップとを有する乱数発生器の作成方法。 【発明の効果】 【0015】 本発明の乱数発生器及び乱数発生器の作成方法によれば、真の乱数を発生することができる。 【発明を実施するための最良の形態】 【0016】 次に、図面を参照して、本発明の実施の形態を説明する。以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。ただし、図面は模式的なものであり、現実のものとは異なることに留意すべきである。又、図面相互間においても互いの寸法の関係や比率が異なる部分が含まれていることはもちろんである。 【0017】 また、以下に示す実施の形態は、この発明の技術的思想を具体化するための装置や方法を例示するものであって、この発明の技術的思想は、各構成部品の配置などを下記のものに特定するものでない。この発明の技術的思想は、特許請求の範囲において、種々の変更を加えることができる。 【0018】 [第1実施形態] 本発明の第1の実施の形態に係る乱数発生器は、複数の論理素子で構成されるリングオシレータの当該論理素子間のいずれか又は全てに少なくとも一個以上の配線資源からなる遅延回路が設けられているリングオシレータと、リングオシレータの出力に接続され、所定のサンプリング周波数でジッター出力を抽出するサンプリング回路とを備える。 【0019】 リングオシレータとは、複数のゲートをリング状につなぎ発振させる回路である。通常、奇数段のNOTゲートQ1, Q2,…，Q2n+1（ここで、nは、1以上の整数）を図1（a）のように構成する。リングオシレータによる発振器は温度や外部の状況などの影響を強く受け、水晶発振器などと比べると不安定であり、ジッターが大きい。 【0020】 本発明の第1の実施の形態に係る乱数発生器においては、図1（b）に示すように、奇数段のNOTゲートQ1, Q2,…，Q2n+1に加えて、このジッターの発生源として、積極的に配線資源による遅延回路Dn を導入し、乱数発生に利用する。 【0021】 本発明の第1の実施の形態に係るリングオシレータによる真の乱数発生回路は、図1（c）に示すように、ノイズソース部14とノイズソースの偏りやビットレートの調整などを行う後処理部16からなる。 【0022】 ノイズソース部14は、単位時間当たりのジッターの割合を増やすために複数のリングオシレータの出力を排他的論理和で束ねてもよく、そのため、図1（c）に示す構成例では、排他的論理和リングオシレータ10を備える。更に、一定時間間隔で乱数を発生するため、一定周波数で排他的論理和リングオシレータ10出力をサンプリングするためのサンプリング回路12を備える。複数のリングオシレータの代わりに、図1（b）に示すように、単一のリングオシレータを用いてもよい。 【0023】 図2は、リングオシレータによる真の乱数発生回路において、図1（a）に示すように、積極的に配線資源による遅延回路Dn を導入しない場合のリングオシレータ（タイプA：比較例）の発振波形と、図1（b）に示すように、積極的に配線資源による遅延回路Dn を導入した場合のリングオシレータ（タイプB：本発明）の発振波形との比較を模式的に示す。 【0024】 図2中には、サンプリング波形も示されている。本発明の第1の実施の形態に係るリングオシレータによる真の乱数発生回路においては、積極的に配線資源による遅延回路Dn を導入することによって、ジッター間隔を、j1＞j0と増大するとともに、発振周期もT1＞T0と増加し、発振周期に対するジッター間隔の割合も、j1／T1＞j0／T0となり増大する。 【0025】 図3は、本発明の第1の実施の形態に係る乱数発生器において、単位時間当たりのジッターの割合を増やすためにノイズソース部14において、3個のリングオシレータの出力を排他的論理和回路18で束ねて、全信号中のジッターの割合を増加する波形例を模式的に示す。図3（a）乃至図3（c）に示す個々のリングオシレータの出力を、排他的論理和回路18で束ねて図3（d）に示すように、ジッター間隔、ジッター割合の増大した出力波形を得ることができる。 【0026】 図4乃至図5は本発明の第1の実施の形態に係る乱数発生回路において、リングオシレータの構成の各種変形例を示す。 【0027】 図4（a）は、3段のNOTゲートQ1，Q2, Q3と遅延回路D1からなるリングオシレータを示す。図4（b）は、3段のNOTゲートQ1，Q2, Q3と遅延回路D1，D2からなるリングオシレータを示す。図4（c）も、3段のNOTゲートQ1，Q2, Q3と遅延回路D1，D2からなるリングオシレータを示し、遅延回路D1，D2の配置を変更した例を示す。 【0028】 図5（a）は、複数の奇数段のNOTゲート・・・Qn-1，Qn，Qn+1，・・・と各々のNOTゲートに対応する遅延回路・・・Dn-1，Dn，Dn+1，・・・からなるリングオシレータを示す。図5（b）は、図5（a）のNOTゲート・・・Qn-1，Qn，Qn+1，・・・の各々をpチャネルトランジスタQA、及びnチャネルトランジスタQBからなるCMOSインバータによって構成した例を示す。各々のCMOSインバータは電源電圧VDDと接地電位間に接続され、かつ各々のCMOSインバータ間には、遅延回路・・・Dn-1，Dn，Dn+1，・・・が接続されている。 【0029】 ここで、配線資源とは、集積回路内の配線のみならず、バッファ回路、NOTゲート間のルート選択により、中間に介在する複数の論理素子（ロジックエレメント）、スイッチ回路なども含まれる。 【0030】 又、NOTゲートQ1, Q2,…，Q2n+1は単なるインバータのみならず、ロジックアレイ内，ゲートアレイ内，プログラマブルゲートアレイ内，或いは図9乃至図16において詳述するFPGA内などの論理素子（ロジックエレメント）も含まれる。 【0031】 又、NOTゲートには、単純な1入力1出力のNOTゲート以外にも、2入力1出力のNANDゲートの入力をつなげて1入力として用いた場合なども含まれ、更に又、排他的論理和（XOR）ゲートなども利用可能である。 【0032】 従って、配線資源には、これらの集積回路内の配線のみならず、このようなロジックアレイ内，ゲートアレイ内，プログラマブルゲートアレイ内，或いはFPGA内などの論理素子（ロジックエレメント）間のルート選択により、中間に介在する複数のバッファ回路、複数の論理素子、スイッチ回路なども含まれる。 【0033】 従って、本発明の実施の形態に係る乱数発生器に適用されるリングオシレータは、単なるインバータチェーンのみならず、積極的に配線資源を介在し、ロジックアレイ内，ゲートアレイ内，プログラマブルゲートアレイ内，或いはFPGA内などの論理素子（ロジックエレメント）間をリング状に接続した回路構成も含まれる。 【0034】 本発明の第1の実施の形態に係る乱数発生器によれば、積極的に配線資源による遅延回路 を導入し、配線資源のジッターも利用するリングオシレータによる真の乱数発生器を提供することができる。 【0035】 [第2実施形態] 本発明の第2の実施の形態に係る乱数発生器は、複数の論理素子で構成されるリングオシレータの当該論理素子間のいずれか又は全てに少なくとも一個以上の配線資源からなる遅延回路が設けられている複数のリングオシレータと、複数のリングオシレータの出力に接続され,複数のリングオシレータの排他的論理和出力を発生する排他的論理和回路と、排他的論理和回路の出力に接続され,所定のサンプリング周波数でジッター出力を抽出するサンプリング回路とを備える。 【0036】 図6は、本発明の比較例に係る乱数発生器の模式的回路構成を示す。ノイズソース部について示されており、後処理部については、省略している。 【0037】 図6に示す比較例に係る乱数発生器では、図1（a）に示すリングオシレータの基本回路構成例を複数配置し、複数のリングオシレータの出力を排他的論理和回路18で束ねる。更に、排他的論理和回路18の出力信号を、Dタイプフリップフロップ回路（D－FF）20に入力し、一定時間間隔で乱数を発生させるため、一定の周波数でサンプリングし、乱数出力を得る。ここで、図6に示すように、リングオシレータの長さをl、リングオシレータの数をk、サンプリング周波数をfSと定義する。 【0038】 図7は、本発明の第2の実施の形態に係る乱数発生器の模式的回路構成を示す。ノイズソース部について示されており、後処理部については、省略している。 【0039】 図7に示す本発明の第2の実施の形態に係る乱数発生器では、図4（c）に示す本発明の第1の実施の形態に係る乱数発生器に適用したリングオシレータと同様の構成例をk個配置し、k個のリングオシレータの出力を排他的論理和回路18で束ねる。更に、排他的論理和回路18の出力信号を、Dタイプフリップフロップ回路（D－FF）20に入力し、一定時間間隔で乱数を発生させるため、サンプリング周波数fSでサンプリングし、乱数出力を得る。図7において、A1，A2，…，Ak、B1，B2，，Bk、及びC1，C2，…，Ckと表示する23は、いずれもNOTゲートを示す。ICと表示する22は、インターコネクトであり、配線資源を示す。 【0040】 図8は、本発明の第2の実施の形態の変形例に係る乱数発生器の模式的回路構成を示す。図8に示す例では、図5（a）に示す本発明の第1の実施の形態に係る乱数発生器に適用したリングオシレータと同様の構成例をk個配置し、k個のリングオシレータの出力を排他的論理和回路18で束ねる。更に、排他的論理和回路18の出力信号を、Dタイプフリップフロップ回路（D－FF）20に入力し、一定時間間隔で乱数を発生させるため、サンプリング周波数fSでサンプリングし、乱数出力を得る。図8において、N11，N21，…，Nk1、N12，N22，…，Nk2、…及びN1n，N2n，…，Nknと表示する23は、いずれもNOTゲートを示す。ICと表示する22は、インターコネクトであり、配線資源を示すことは図7と同様である。 【0041】 本発明の第2の実施の形態に係る乱数発生器によれば、積極的に配線資源による遅延回路 を導入し、配線資源のジッターも利用するリングオシレータを並列化構成して、ジッター量を増加した真の乱数発生器を提供することができる。 【0042】 [第3実施形態] （FPGA） 本発明の第3の実施の形態に係る乱数発生器は、FPGAのみを用いる例を示す。FPGAのみを用いて真の乱数を生成するには、第1の実施の形態に係る乱数発生器に示すように、リングオシレータを用いる。しかも、必要とされる乱数性を得るために多数のリングオシレータを必要とするが、回路コストの増加を抑制するために、本発明の第3の実施の形態に係る乱数発生器においては、リングオシレータの一部に、乱数の基となるジッターを発生させる配線資源（インターコネクト）による遅延回路を積極的に導入し、真の乱数発生に利用する。 【0043】 FPGAの資源はルックアップテーブルやレジスタを含む論理素子資源と配線資源からなる。例えば、FPGAの基本単位は、図9に示すように、最小の回路単位であるロジックエレメント（LE）24が10個まとまったロジックアレイブロック（LAB）25と、LAB25の周囲に配置されるローカルインターコネクト26と、ローカルインターコネクト26及びLAB25の周囲に配置され，カラム方向に延伸するカラムインターコネクト（CL）27と、同じくローカルインターコネクト26及びLAB25の周囲に配置され，ロウ方向に延伸するロウインターコネクト（RL）28とを備える。 【0044】 ローカルインターコネクト26、カラムインターコネクト（CL）27及びロウインターコネクト（RL）28によって、FPGAにおけるプログラマブルな配線を実現することができる。カラムインターコネクト（CL）27及びロウインターコネクト（RL）28の交点には、トランジスタによるスイッチが配置されており、そこにはジッターが存在し得る。 【0045】 本発明の第3の実施の形態に係る乱数発生器は、FPGAの最小の回路単位であるロジックエレメント（LE）24をNOTゲートとし、リングオシレータのNOTゲートの間に、ローカルインターコネクト26、カラムインターコネクト（CL）27及びロウインターコネクト（RL）28などによって構成される配線資源（インターコネクト）を挿入する。このように構成することで、発振波形のジッターを増加することができる。 【0046】 例えば、配線資源（インターコネクト）を積極的に導入しない場合には、LAB25内のLE24を個々のNOTゲートとして構成し、それぞれをリング状に接続したものを並列化することで、図6に示す比較例に係る乱数発生器と同様の乱数発生器を構成することができる。 【0047】 一方、配線資源（インターコネクト）を積極的に導入する場合には、例えば、図10に示すように、INV1、INV2、及びINV3で示される別々のLAB25内のLE24を個々のNOTゲートとして構成し、その間を点線及び実線で示すように、配線資源（インターコネクト）でリング状に接続したものを並列化することで、図7に示すに本発明の第2の実施の形態に係る乱数発生器と同様の乱数発生器をFPGA上において構成することができる。すなわち、図7に示すように、リングオシレータの長さl＝3とし、インターコネクト（IC）22を2箇所に挿入したリングオシレータを並列化した構成例を、FPGAを用いて実現することができる。FPGAは、図11に示すように、マトリックス状に配置された複数のLAB25と、カラム方向に延伸する複数のカラムインターコネクト…，CLi-4，CLi-3，CLi-2，CLi-1，CLi，CLi+1，CLi+2，…と、ロウ方向に延伸する複数のロウインターコネクト…，RLi-1，RLi，RLi+1，…を備える。従って、NOTゲート間の配線資源（インターコネクト）は、FPGA上のカラムインターコネクト、ロウインターコネクトの経路選択により任意に選定することができる。図11においては、ローカルインターコネクト26については省略されている。 【0048】 リングオシレータの数kは、例えば、配線資源（インターコネクト）による遅延回路を積極的に導入しない場合には、k＝110～210であるのに対して、配線資源（インターコネクト）による遅延回路を積極的に導入した場合には、例えば、k＝110よりも減少することができる。 【0049】 比較例に係る乱数発生器と配線資源（インターコネクト）を有効活用する本発明の第3の実施の形態に係る乱数発生器を比較する。 【0050】 比較例に係る乱数発生器は、図6に示すようにリングオシレータを構成し、各リングオシレータの長さをl＝3、リングオシレータの数をk＝20としたものである。20個のリングオシレータの出力の排他的論理和をサンプリング周波数fS＝50MHzでサンプリングし、乱数生成器の出力を得る。 【0051】 本発明の第3の実施の形態に係る乱数発生器の具体的な配置構成例を図12及び図13に示す。図13は、図12の経路選択を説明するために、FPGA上における詳細な配置構成例を示す。図12及び図13中のA，B，Cはそれぞれ1つのNOTゲートに対応し、Bをひとつだけ離すことで、A－B間、B－C間にインターコネクトを挿入している。 【0052】 図12及び図13の例では、A－B間に1．365nsの配線遅延をもつインターコネクトを、B－C間に1．334nsの配線遅延をもつインターコネクトを挿入している。この配線遅延は、図13に示すように、ロウインターコネクト3単位分、カラムインターコネクト3単位分の和に相当する。C－A間の配線遅延は、同一のLAB25内であることから、0．367nsと小さい。 【0053】 （乱数発生器の作成方法） 本発明の第3の実施の形態に係る乱数発生器の作成方法は、例えば、以下の通りである。 【0054】 複数のLE24と,当該LE24を電気的に接続する配線資源（インターコネクト）と，当該配線資源（インターコネクト）の交差点に設けられ，配線切り替えを行うスイッチング素子を少なくとも備えるプログラム可能な集積回路内に乱数発生器を設ける乱数発生器の作成方法において、（a）複数のLE24を用いて少なくとも一つのリングオシレータを形成するリングオシレータ形成ステップと、（b）リングオシレータを構成する一のLE24と他のLE24の間に、少なくとも一つ以上のスイッチング素子を含む一定長の配線資源を設けるジッター生成ステップと、（c）リングオシレータ形成ステップ及びジッター生成ステップにより生成された出力信号を所定のサンプリング周波数fSでサンプリング抽出するサンプリング抽出ステップとを有する。 【0055】 （乱数性評価の方法） 乱数発生器の評価は、回路面積や生成速度、生成される乱数の乱数性により行うことができる。回路面積は、FPGAの必要とされるLE24によって決定され、生成速度は、回路動作周波数によって決定される。乱数性は、種々の統計テストから評価される。 【0056】 本発明の第3の実施の形態に係る乱数発生器の評価においては、NISTSP800－22（http://csrc.nist.gov/publications/nistpubs/index.html: A Statistical Test Suite for Random and Pseudo-random Number Generators for Cryptographics Applications）に示される15種類の検定を行った。検定には、図6と同様に比較例の回路構成の場合と、 図7と同様に本発明の実施の形態に係る回路構成の場合を、それぞれについて1000サンプ（1サンプル当たり1，000，000ビット）で比較した。乱数テストで用いたパラメータは、図14に示すとおりである。パラメータl＝3，k＝20，fS＝50MHzは同一とした。 【0057】 通常、真の乱数生成器は、より乱数性のよい乱数を生成するために、図1（c）に示したように、後処理部16を用いるが、ここでは、配線資源（インターコネクト）を追加したことによる乱数性の違いを見るために、後処理部16を介さず、乱数生成出力をそのまま直接NISTSP800－22にかけ、統計的性質を調べた。 【0058】 （乱数性評価結果） 回路面積については、比較例に係る乱数発生器、本発明の第3の実施の形態に係る乱数発生器ともに、LE数67であった。生成速度については、比較例に係る乱数発生器、本発明の第3の実施の形態に係る乱数発生器ともに、サンプリング周波数fS＝50MHzより50Mbpsであった。 【0059】 乱数性の評価結果を図15に示す。図15はそれぞれの検定項目に対して有意確率（p-value）を計算し、その値の分布度合い（一様性）と検定合格率（比率）をまとめたものである。図15において、各検定につき、○は合格、×は不合格を意味する。Non-overlapping Template検定については、テンプレートサイズが9の時、148種のテンプレートに対して行った結果を合格、不合格の個数で表している。 【0060】 図15から明らかなように、比較例に係る乱数発生器、本発明の第3の実施の形態に係る乱数発生器ともに多くの検定に合格していない。これは前述のように、リングオシレータの個数kは20個であり、生成されるジッターの割合が少ないためである。しかしながら、配線資源（インターコネクト）を用いる本発明の第3の実施の形態に係る乱数発生器においては、明らかに比較例に係る乱数発生器よりも乱数性は増加していることがわかる。 【0061】 本発明の第3の実施の形態に係る乱数発生器において、Non-overlapping Template検定の結果の詳細は、図16に示すように表される。図16は、同検定の148種類のテンプレートの内、異なる検定結果をもたらす場合を抜き出したものである。図16から明らかなように、比較例に係る乱数発生器においては合格しなかった多くのテンプレート検定が、本発明の第3の実施の形態に係る乱数発生器においては合格していることがわかる。 【0062】 又、図16において、離散フーリエ変換（DFT：Discrete Fourier transform）やSerial 2の検定では、比較例に係る乱数発生器、本発明の第3の実施の形態に係る乱数発生器ともに合格しなかったが、本発明の第3の実施の形態に係る乱数発生器の合格比率（PROPORTION）は向上していることがわかる。 【0063】 アプリケーションによっては、FPGA上の配線資源（インターコネクト）に余剰が生ずる場合もある。このため、この余剰の配線資源（インターコネクト）を有効に活用することで、回路設計の自由度を向上することができる。 【0064】 本発明の第3の実施の形態に係る乱数発生器によれば、FPGA上において、配線資源（インターコネクト）を積極的に活用し、リングオシレータによる真の乱数発生器を構成することができる。 【0065】 [その他の実施の形態] 上記のように、本発明は第1乃至第3の実施の形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例及び運用技術が明らかとなろう。 【0066】 特に、本発明の第3の実施の形態に係る乱数発生器においては、FPGAを適用する例を開示しているが、FPGAに限定されるものではない。ゲートアレイ、ロジックアレイ、プログラマブルロジックアレイ或いはASICなどを用いても、同様に配線資源（インターコネクト）を積極的に活用することで、ジッターの増大した真の乱数発生器を構成することができる。 配線資源（インターコネクト）には、集積回路内の配線のみならず、NOTゲート間のルート選択により、中間に介在する複数の論理素子、スイッチ回路なども含まれる。又、NOTゲートは単なるインバータのみならず、ロジックアレイ内，ゲートアレイ内，或いはFPGA内のロジックエレメントなども含まれる。従って、配線資源（インターコネクト）には、これらの集積回路内の配線のみならず、このようなロジックアレイ内，ゲートアレイ内，或いはFPGA内のロジックエレメント間のルート選択により、中間に介在する複数の論理素子、スイッチ回路なども含まれる。 【0067】 従って、本発明の実施の形態に係る乱数発生器に適用されるリングオシレータは、単なるインバータチェーンのみならず、積極的に配線資源を介在し、ロジックアレイ内，ゲートアレイ内，或いはFPGA内のロジックエレメント間をリング状に接続した回路構成も含まれる。 【0068】 従って、所望の長さl、所定の個数k、所定のサンプリング周波数fSを有する本発明の実施の形態に係る真の乱数発生器を所望のASICとして構成することもできる。 【0069】 このように、本発明はここでは記載していない様々な実施の形態などを含むことは勿論である。したがって、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。 【0070】 [乱数発生器の使用方法] 本発明の実施の形態に係る乱数発生器は、例えば、鍵生成、鍵交換、回路のマスク、パチンコの確率変動等に用いることが可能である。これら鍵生成等に本乱数発生器を用いることにより、プログラム可能な集積回路の限られた資源を有効利用しつつ、真の乱数による鍵生成、鍵交換、回路のマスク、パチンコの確率変動等を行うことができる。 【0071】 又、本発明の実施の形態では乱数発生器として説明をしているが、この乱数発生器からサンプリング回路を除くことにより、単なるジッター発生器として利用することが可能である。この場合、本ジッター発生器は、ジッターを測定するジッター測定装置において、測定精度を検査するために用いるサンプル用のジッター発生器として用いることが可能である。 【図面の簡単な説明】 【0072】 【図1】（a）リングオシレータの基本回路構成例。（b）本発明の第1の実施の形態に係る乱数発生器を構成するリングオシレータの基本回路構成例。（c）本発明の第1の実施の形態に係る乱数発生器の模式的ブロック構成図。 【図2】リングオシレータによる真の乱数発生回路において、積極的に配線資源による遅延回路Dn を導入しない場合のリングオシレータ（タイプA：比較例）の発振波形図と、積極的に配線資源による遅延回路Dn を導入した場合のリングオシレータ（タイプB：本発明）の発振波形図、及びサンプリング波形図。 【図3】本発明の第1の実施の形態に係る乱数発生器において、単位時間当たりのジッターの割合を増やすためにノイズソース部において、3個のリングオシレータの出力を排他的論理和回路で束ねて、全信号中のジッターの割合を増加する波形例を模式的に示す図であって、図3（a）乃至図3（c）：個々のリングオシレータの出力波形図、図3（d）：排他的論理和回路出力波形図。 【図4】（a）本発明の第1の実施の形態に係る乱数発生器を構成するリングオシレータの別の構成例。（b）本発明の第1の実施の形態に係る乱数発生器を構成するリングオシレータの更に別の構成例。（c）本発明の第1の実施の形態に係る乱数発生器を構成する更に別のリングオシレータの構成例。 【図5】（a）本発明の第1の実施の形態に係る乱数発生器を構成する更に別のリングオシレータの構成例。（b）本発明の第1の実施の形態に係る乱数発生器を構成する更に別のリングオシレータの構成例。 【図6】本発明の比較例に係る乱数発生器の構成例。 【図7】本発明の第2の実施の形態に係る乱数発生器の構成例。 【図8】本発明の第2の実施の形態の変形例に係る乱数発生器の構成例。 【図9】本発明の第3の実施の形態に係る乱数発生器に適用するFPGAの内部回路構成図。 【図10】本発明の第3の実施の形態に係る乱数発生器に適用するFPGAの内部回路構成例。 【図11】本発明の第3の実施の形態に係る乱数発生器に適用するFPGAのLABの配置構成図。 【図12】本発明の第3の実施の形態に係る乱数発生器に適用するFPGAの中の回路位置図。 【図13】本発明の第3の実施の形態に係る乱数発生器に適用するFPGAの中の詳細回路位置図。 【図14】本発明の第3の実施の形態に係る乱数発生器において、NISTSP800－22の統計テストで用いるパラメータ。 【図15】本発明の第3の実施の形態に係る乱数発生器において、NISTSP800－22による検査結果。 【図16】本発明の第3の実施の形態に係る乱数発生器において、Non-overlapping Template検定の結果。 【符号の説明】 【0073】 10…排他的論理和リングオシレータ 12…サンプリング回路 14…ノイズソース部 16…後処理部 18…排他的論理和回路（XOR） 20…Dタイプフリップフロップ（D－FF） 22…インターコネクト（IC） 23…NOTゲート 24…ロジックエレメント（LE） 25…ロジックアレイブロック（LAB） 26…ローカルインターコネクト 27，…，CLi-4，CLi-3，CLi-2，CLi-1，CLi，CLi+1，CLi+2，……カラムインターコネクト 28，…，RLi-1，RLi，RLi+1，……ロウインターコネクト Q1，Q2,…，Qn-1，Qn，Qn+1，…，Q2n+1…、A1，A2，…，Ak、B1，B2，，Bk、及びC1，C2，…，Ck、N11，N21，…，Nk1、N12，N22，…，Nk2、…及びN1n，N2n，…，Nkn…NOTゲート QA…pチャネルMOSトランジスタ QB…nチャネルMOSトランジスタ D1，D2,…，Dn-1，Dn，Dn+1…遅延回路 τ1，τ2,…，τn-1，τn，τn+1…遅延時間 T0，T1…周期 j0，j1…ジッター間隔
Drawing	(In Japanese)【図1】 (In Japanese)【図2】 (In Japanese)【図3】 (In Japanese)【図4】 (In Japanese)【図5】 (In Japanese)【図6】 (In Japanese)【図7】 (In Japanese)【図8】 (In Japanese)【図9】 (In Japanese)【図10】 (In Japanese)【図11】 (In Japanese)【図12】 (In Japanese)【図13】 (In Japanese)【図14】 (In Japanese)【図15】 (In Japanese)【図16】