Top > Search of Japanese Patents > RANDOM NUMBER GENERATOR AND METHOD OF MANUFACTURING RANDOM NUMBER GENERATOR

RANDOM NUMBER GENERATOR AND METHOD OF MANUFACTURING RANDOM NUMBER GENERATOR commons

Patent code P110004834
File No. 06-063JP00
Posted date Aug 18, 2011
Application number P2007-011347
Publication number P2008-176698A
Patent number P4982750
Date of filing Jan 22, 2007
Date of publication of application Jul 31, 2008
Date of registration May 11, 2012
Inventor
  • (In Japanese)渡部 信吾
  • (In Japanese)阿部 公輝
Applicant
  • (In Japanese)国立大学法人電気通信大学
Title RANDOM NUMBER GENERATOR AND METHOD OF MANUFACTURING RANDOM NUMBER GENERATOR commons
Abstract PROBLEM TO BE SOLVED: To provide a random number generator for generating true random numbers by introducing delay circuits comprising wiring resources to ring oscillators and utilizing jitter of the wring resources, and a method of manufacturing the random number generator.
SOLUTION: The random number generator includes: a plurality of ring oscillators each of which comprises a plurality of logic elements 23 and is provided with a delay circuit comprising at least one wiring resource (interconnect) 22 between some or all of the logic elements 23; an exclusive OR circuit 18 which is connected to outputs of the plurality of ring oscillators and generates an exclusive OR output of the plurality of ring oscillator; and a sampling circuit 12 which is connected to an output of the exclusive OR circuit 18 and samples a jitter output by a prescribed sampling frequency fs.
Outline of related art and contending technology (In Japanese)


モンテカルロ法などのシミュレーション分野や、暗号およびセキュリティー分野における鍵生成、鍵交換、回路のマスクなどでは、大量の乱数やよく散らばった,乱数性のよい乱数が必要とされることが多い。



乱数には大きく分けて真の乱数と疑似乱数がある。真の乱数とは、予測が不可能で再現性のない乱数のことである。通常は、熱雑音や核分裂などの本質的にランダムな物理的現象を基に乱数を生成し、離散化・符号化の後に後処理をする。このため、アナログ回路を必要とするので、外部回路を付加することが多い。外部に特別な回路が必要となることから、実装の高密度化や低消費電力化,耐タンパー性などの点で問題がある。そのため、外部回路によらず、FPGA(Field Programmable Gate Array)のみを用いて真の乱数を生成する試みがなされている。



例えば、アナログPLL(Phase locked Loop)を用いて乱数を生成する例では、アナログPLLを搭載しているある特定のFPGAのみでしか構成できない。



又、FPGAの外部に抵抗とコンデンサからなる外部回路を付加して乱数を生成する例では、FPGAの製造元やその種類に依存せず乱数を発生することができるが、乱数の生成が外部の回路に依存するため、付加回路が除去されれば乱数の生成が止まること、及び生成する乱数が外部からサンプリング可能であることから、セキュリティーの面で問題点がある。



一方、プログラマブルなデジタル回路であるFPGAを用い外部回路を要しない真の乱数の生成手法が提案されている(例えば、非特許文献1及び2参照。)。FPGAの内部で閉じた回路が構成できるので、耐タンパー性,コストの削減,IP(Intellectual Property)コアとしての回路の面で有用である。非特許文献1においては、デジタル回路のみを用い、複数のリングオシレータによるジッターを基にした乱数生成器を理論的な立場から検討している。非特許文献1においては、CPLD(Complex Programmable Logic Device)やFPGAも検討しているが実際の評価は行っていない。又、非特許文献2においては、特定の条件に限定した実装を行い評価を行っている。



一方、縦続接続された複数段の論理ゲート出力の一部を帰還抵抗を介して入力側に帰還させて発振する発振部を備え、論理ゲートには、所定の抵抗を介して電源電圧が供給され、所定の抵抗は絶縁層を介して信号線に積層されていることを特徴とする乱数発生集積回路については、既に開示されている(例えば、特許文献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

Field of industrial application (In Japanese)


本発明は、乱数発生器に関し、特にリングオシレータを基本構成とする真の乱数発生を可能とする乱数発生器及び乱数発生器の作成方法に関する。

Scope of claims (In Japanese)
【請求項1】
 
複数の論理素子で構成されるリングオシレータの当該論理素子間のいずれか又は全てに少なくとも一個以上の配線資源からなる遅延回路が設けられているリングオシレータと、
前記リングオシレータの出力に接続され、所定のサンプリング周波数でジッター出力を抽出するサンプリング回路とを備え、
前記論理素子は、プログラム可能な集積回路内に設けられるロジックエレメントで構成され、前記配線資源は、前記集積回路において、前記ロジックエレメント近傍に配置されるローカルインターコネクト、カラム方向に延伸するカラムインターコネクト、及び/又はロウ方向に延伸するロウインターコネクトで構成されることを特徴とする乱数発生器。

【請求項2】
 
複数の論理素子で構成されるリングオシレータの当該論理素子間のいずれか又は全てに少なくとも一個以上の配線資源からなる遅延回路が設けられている複数のリングオシレータと、
前記複数のリングオシレータの出力に接続され,前記複数のリングオシレータの排他的論理和出力を発生する排他的論理和回路と、
前記排他的論理和回路の出力に接続され,所定のサンプリング周波数でジッター出力を抽出するサンプリング回路とを備え、
前記論理素子は、プログラム可能な集積回路内に設けられるロジックエレメントで構成され、前記配線資源は、前記集積回路において、前記ロジックエレメント近傍に配置されるローカルインターコネクト、カラム方向に延伸するカラムインターコネクト、及び/又はロウ方向に延伸するロウインターコネクトで構成されることを特徴とする乱数発生器。

【請求項3】
 
前記サンプリング回路の出力に接続され,前記ジッター出力を加工処理する後処理回路を更に備えることを特徴とする請求項1又は請求項2に記載の乱数発生器。

【請求項4】
 
複数のロジックエレメントと,当該ロジックエレメントを電気的に接続する配線資源と、当該配線資源の交差点に設けられ、配線切り替えを行うスイッチング素子を少なくとも備えるプログラム可能な集積回路内に乱数発生器を設ける乱数発生器の作成方法において、
前記複数のロジックエレメントを用いて少なくとも一つのリングオシレータを形成するリングオシレータ形成ステップと、
前記リングオシレータを構成する一のロジックエレメントと他のロジックエレメントの間に、少なくとも一つ以上のスイッチング素子を含む一定長の配線資源を設けるジッター生成ステップと、
前記リングオシレータ形成ステップ及びジッター生成ステップにより生成された出力信号を所定のサンプリング周波数でサンプリング抽出するサンプリング抽出ステップと
を有する乱数発生器の作成方法。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2007011347thum.jpg
State of application right Registered


PAGE TOP

close
close
close
close
close
close
close