JP2005003745A

JP2005003745A - Device, method, and program for generating random number, and cipher processor

Info

Publication number: JP2005003745A
Application number: JP2003164280A
Authority: JP
Inventors: Takashi Suzuki; 孝鈴木
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 2003-06-09
Filing date: 2003-06-09
Publication date: 2005-01-06

Abstract

<P>PROBLEM TO BE SOLVED: To provide a random number generation device of simple configuration capable of generating random numbers with reduced deviation in bit values or periodicity, a method and a program for the same, and a cipher processor equipped with the random number generation device. <P>SOLUTION: Random number data S1 generated in a physical random number generation section 1 based on the irregularity of physical phenomena is corrected in a correction section 2 based on inputted correction information S3. The corrected random number data S2 is outputted to the outside via an interface section 5 and successively stored in an FIFO 4. In a corrected information generation section S3, the number of bit data having the bit value of "1" contained in a series of random number data stored in the FIFO 4 is counted and, based on the result of comparison between the counted number and a prescribed threshold, new correction information S3 is successively generated. <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

【０００１】
【発明の属する技術分野】
本発明は、乱数生成装置とその方法、乱数生成手段を備えた暗号処理装置、および、乱数の生成に係る処理をコンピュータに実行させるプログラムに関するものである。
【０００２】
【従来の技術】
近年、インターネットを利用したデータ通信の普及に伴って、データ通信の安全性を高めることが重要な課題になっており、特に、データ通信の秘密性を確保する技術として暗号化技術が注目されている。
【０００３】
コンピュータ・ネットワークを利用したデータ通信における代表的な暗号化方式には、共通鍵暗号方式と公開鍵暗号方式がある。
共通鍵暗号方式は、暗号化と復号化とで同じ暗号鍵を使う方式であり、「秘密鍵暗号」、「対称鍵暗号」、「慣用暗号」とも呼ばれる。
一方、公開鍵暗号方式は、暗号化と復号化とで異なる暗号鍵を使う方式である。公開鍵暗号方式によると、一方の暗号鍵で暗号化したデータは、もう一方の鍵を使わないと復号することができない。このため、一方の鍵を秘密にしておくことにより、他方の鍵を公開しても暗号文の秘密性を保つことができる。
【０００４】
共通鍵暗号方式は、暗号化用と復号化用の鍵が同一であることから、通信相手に安全な方法で鍵を渡すことが難しく、鍵を共有するための手段が必要になる。これに対し、公開鍵暗号方式は、暗号化用と復号化用の鍵が異なるため、暗号化用の鍵を安全性が保証されない通信網で配送することが可能となり、通信相手に暗号鍵を渡すことが非常に楽である。
【０００５】
このように、公開鍵暗号方式は鍵の配送が非常に容易であるという利点があるものの、その一方で、共通鍵暗号方式に比べて処理時間が非常に長くなるという不利益がある。例えば、公開鍵暗号方式の代表的な方式であるＲＳＡ（ＲｉｖｅｓｔＳｈａｍｉｒＡｄｅｌｍａｎ）方式の処理速度は、暗号化、復号化とも共通鍵暗号方式に比べ１０００倍程度遅い。
【０００６】
このため、コンピュータ・ネットワークを利用したデータ通信において、高速な暗号システムを構成する場合、一般に、暗号化および復号化は共通鍵暗号を用い、その鍵を公開鍵暗号によって暗号化し、配送するという方式が用いられている。この方式を採用している暗号システムには、ＰＧＰ（ｐｒｅｔｔｙｇｏｏｄｐｒｉｖａｃｙ，商標）やＰＥＭ（ｐｒｉｖａｃｙｅｎｈａｎｃｅｍｅｎｔｍａｉｌ）などがある。
ＲＳＡ方式は、主としてこのような共通鍵の受け渡しや、比較的少量のデータ伝送に使われている。
【０００７】
以上の暗号化技術を利用すれば、電子マネーや、ネット上の音楽配信、携帯電話とＩＤカードを用いた個人向けのサービス等を実現する場合において、データの暗号化、および、本人認証に必要なデジタル署名の生成を行うことができる。
【０００８】
ところで、こうした暗号化技術を利用して安全なデータ通信を保証するためには、安全な乱数を生成することが不可欠である。乱数の主な用途として、例えばパスワードの作成や、暗号化に使用する鍵の作成、暗号文の生成、電子署名情報の生成などがある。このような用途の乱数が攻撃者に推測されてしまうと、暗号文が解読されてしまったり、署名が改竄されてしまうなどの危険性が高まる。したがって、攻撃者が容易に推測することができない乱数を生成することが非常に重要である。
【０００９】
乱数の生成方法には、物理現象の不規則性を利用して乱数を生成する方式と、数学的な演算処理によって長い周期の乱数列を生成する方式とがある。
【００１０】
物理現象の不規則性を利用して乱数を生成する方式には、例えば、抵抗体の熱雑音により乱数を生成する方式や、リングオシレータなどのアナログ出力からアナログ−デジタル変換（以降、Ａ／Ｄ変換と表記する）によって乱数を得る方式などがある。
しかしながら、これらの方式では、必ずしも全く偏りのない粗雑な乱数が得られるわけではなく、ビット単位の偏りや周期性が生じてしまうことがある。そうした乱数を公開鍵暗号方式の秘密鍵やデジタル署名用のセッションキーに使用した場合、安全性の低下が危惧される。
【００１１】
乱数の粗雑性の評価基準として、ＦＩＰＳ（ｆｅｄｅｒａｌｉｎｆｏｒｍａｔｉｏｎｐｒｏｃｅｓｓｉｎｇｓｔａｎｄａｒｄｓ）１４０−２に“ｓｔａｔｉｓｔｉｃａｌｒａｎｄｏｍｎｕｍｂｅｒｇｅｎｅｒａｔｏｒｔｅｓｔ”が定義されている。この評価基準では、２００００ビットの乱数を連続で生成させた時に、この２００００ビット中に含まれる‘１’の数によって乱数の粗雑性が評価される。
図１７は、あるアナログ乱数生成器によって生成した２００００ビットの乱数に含まれる‘１’の数を複数回にわたって検査した結果を示す図である。図の縦軸の値は２００００ビット中の‘１’の数を示し、横軸の値は各検査の番号を示す。
完全に粗雑な乱数であれば、‘０’と‘１’の発生確率がそれぞれ５０％であるため‘１’の数は１００００付近になる。しかしながら、図１７の例では、‘１’の発生確率が明らかに５０％より低くなっている。
【００１２】
このようなビット値の偏りに対処する方法として、擬似乱数を用いる方法がある（特許文献１〜４を参照）。
例えば、Ｍ系列発生回路などの線形回路を複数組み合わせた擬似乱数生成回路や、ＤＥＳ（ｄａｔａｅｎｃｒｙｐｔｉｏｎｓｔａｎｄａｒｄ）方式などの共通鍵暗号方式における暗号演算回路、ＳＨＡ−１（ＳｅｃｕｒｅＨａｓｈＡｌｇｏｒｉｔｈｍ −１）方式やＭＤ５（ｍｅｓｓａｇｅｄｉｇｅｓｔ５）方式などにおけるハッシュ演算回路に対して、上述した物理手段により生成される乱数をシードとして入力することにより、ビット値の偏りが少ない均一な擬似乱数を得る方法がある。
【００１３】
一般的な擬似乱数生成法では、与えられたシードに所定の乱数演算を繰り返すことにより擬似乱数を生成する。すなわち、乱数演算の関数をＦとした場合、シードとして初期値Ｒ（０）が与えられると、乱数列Ｒ（１），Ｒ（２），Ｒ（３），…は、“Ｒ（ｉ＋１）＝Ｆ（Ｒ（ｉ））”の式により順番に生成される。そして、乱数Ｒ（１），Ｒ（２），Ｒ（３），…を結合することにより、所望の長さの擬似乱数が生成される。
【００１４】
【特許文献１】
特開２０００−２４２４７０号公報
【特許文献２】
特開２００１−７５４７６号公報
【特許文献３】
特開２０００−４２２３号公報
【特許文献４】
特開２００１−３４４０９４号公報
【００１５】
【発明が解決しようとする課題】
この擬似乱数生成法は、特別なハードウェアを必要とせず、ソフトウェアによる実現が可能であり、マイクロコンピュータ上で利用できるという利点がある。しかしながら、上述したように、初期値を用いて所定の関数により乱数列が生成されるため、関数と初期値が決まると、全ての乱数列が決定される。このため、関数と初期値が知られてしまうと、同様の方法で乱数列を容易に生成することができるという不利益がある。
【００１６】
一例を挙げると、ＦＩＰＳ１８６におけるＳＨＡ−１方式を用いた擬似乱数生成方法においては、長さが１６０ビットのビット列ｔと、長さがｂビット（１６０≦ｂ≦５１２）のビット列ｃとをＳＨＡ−１演算器に与えて１６０ビットの乱数を生成する。この方法では、ＳＨＡ−１演算器が持つ５１２ビットの入力バッファにビット列ｃを格納した後で、この入力バッファの残りの格納領域に（５１２−ｂ）個の‘０’を格納するため、ビット列ｃが決まると、ビット列ｃの入力に対し、ＳＨＡ−１演算器の出力は常に一定となってしまう。
【００１７】
加えて、これらの擬似乱数生成法は、ハードウェアで実現した場合の回路規模が非常に大きくなり、ソフトウェアで実現する場合も多くのコード量と演算時間が必要になるという不利益がある。
【００１８】
本発明はかかる事情に鑑みてなされたものであり、その目的は、簡易な構成でありながら、ビット値の偏りや周期性の少ない乱数を生成することができる乱数生成装置とその方法を提供することにある。
また、本発明の他の目的は、ビット値の偏りや周期性の少ない乱数の生成に係る処理を、より簡易な手順でコンピュータに実行させることができるプログラムを提供することにある。
また、本発明の更に他の目的は、簡易な構成で、ビット値の偏りや周期性のない乱数を用いた安全性の高い暗号処理を実行することができる暗号処理装置を提供することにある。
【００１９】
【課題を解決するための手段】
上記の目的を達成するため、本発明の第１の観点の乱数生成装置は、乱数生成手段と、上記乱数生成手段において生成される乱数データを、入力される補正情報に基づいて補正する補正手段と、上記補正手段において補正された乱数データに所定のビット値を持つビットデータが出現する頻度に応じて上記補正情報を生成する補正情報生成手段と有する。
好適には、上記乱数生成手段は、物理現象の不規則性に基づいて乱数を生成する。
【００２０】
本発明の第１の観点によれば、上記乱数生成手段において物理現象の不規則性に基づいて生成される乱数データが、上記補正手段において、入力される補正情報に基づいて補正される。上記補正情報生成手段では、上記補正手段において補正された乱数データに所定のビット値を持つビットデータが出現する頻度に応じて、上記補正情報が生成される。
【００２１】
また、本発明の第１の観点は、上記補正手段において補正された乱数データを順に格納する複数のデータ格納手段を有しても良い。
この場合、上記補正情報生成手段は、上記データ格納手段に格納される複数の乱数データの中に上記所定のビット値を持つビットデータが存在する数を計数し、当該計数値と所定のしきい値との比較結果に基づいて上記補正情報を生成する。
【００２２】
また、上記補正情報生成手段は、入力される制御信号に応じて上記しきい値を変化させても良い。
【００２３】
本発明の第２の観点の乱数生成方法は、乱数生成手段において生成される乱数データを、与えられる補正情報に基づいて補正する第１の工程と、上記第１の工程において補正された乱数データに所定のビット値を持つビットデータが出現する頻度に応じて上記補正情報を新たに生成する第２の工程とを有する。
【００２４】
本発明の第２の観点によると、乱数生成手段において生成される乱数データが、上記第１の工程において、与えられる補正情報に基づいて補正される。上記第２の工程では、上記第１の工程において補正された乱数データに所定のビット値を持つビットデータが出現する頻度に応じて、上記補正情報が新たに生成される。
【００２５】
本発明の第３の観点のプログラムは、乱数生成手段において生成される乱数データを、与えられる補正情報に基づいて補正する第１のステップと、上記第１のステップにおいて補正された乱数データに所定のビット値を持つビットデータが出現する頻度に応じて上記補正情報を新たに生成する第２のステップと、を有する処理をコンピュータに実行させる。
【００２６】
本発明の第４の観点の暗号処理装置は、乱数生成手段と、上記乱数生成手段において生成される乱数データを、入力される補正情報に基づいて補正する補正手段と、上記補正手段において補正された乱数データに所定のビット値を持つビットデータが出現する頻度に応じて上記補正情報を生成する補正情報生成手段と、上記補正手段において補正された乱数データに応じて所定の暗号処理を実行する暗号処理手段とを有する。
【００２７】
【発明の実施の形態】
以下、本発明の３つの実施形態について、図面と関連付けて説明する。
【００２８】
＜第１の実施形態＞
図１は、本発明の第１の実施形態に係る暗号処理装置の構成の一例を示すブロック図である。
図１に示す暗号処理装置１００は、乱数生成装置の実施形態である乱数生成部１０と、暗号処理手段の実施形態である暗号処理部２０と、ＥＥＰＲＯＭ３０と、ＣＰＵ４０と、ＲＡＭ５０と、ＲＯＭ６０とを有する。
【００２９】
乱数生成部１０は、バスＢＳを介して入力されるＣＰＵ４０からの制御信号に応じて、乱数を生成する。例えば、ＣＰＵ４０からの制御信号に応じて乱数の生成を開始または停止する。
なお、乱数生成部１０の構成と動作については、後で更に詳細に説明する。
【００３０】
暗号処理部２０は、バスＢＳを介して入力されるＣＰＵ４０からの制御信号に応じて、所定の暗号処理を実行する。
例としてＲＳＡ方式の暗号処理を実行するものとすると、暗号処理部２０は、例えば、乱数生成部１０において生成される乱数に応じて公開鍵および秘密鍵のペアを生成する処理（鍵生成処理）や、通信相手の公開鍵によって平文を暗号化する処理（暗号化処理）、公開鍵によって暗号化された暗号文を当該公開鍵のペアとなる秘密鍵によって復号する処理（復号化処理）を行う。また、送信文に添付するデジタル署名を秘密鍵によって生成する処理（デジタル署名生成処理）や、受信文に添付されたデジタル署名を通信相手の公開鍵によって検証する処理（デジタル署名検証処理）なども行う。
【００３１】
ＥＥＰＲＯＭ３０は、電気的に消去可能なプログラマブルＲＯＭであり、バスＢＳを介して入力されるＣＰＵ４０からの制御信号に応じて、暗号処理に用いられる鍵のデータを格納する。
【００３２】
ＣＰＵ４０は、ＲＯＭ６０に格納されたプログラムに基づいて、暗号処理装置１００の全体動作に係わる種々の制御を行う。
例えば、上述した鍵生成処理、暗号化処理、復号化処理、デジタル署名の生成・検証処理などの暗号処理を、プログラムに基づいて暗号処理部２０に実行させる。
また、暗号処理部２０における鍵生成処理や、デジタル署名時のセッションキーを生成する場合など、プログラムの実行過程で乱数が必要な場合は、これを乱数生成部１０に生成させる。
また、暗号処理部２０において生成された鍵データをＥＥＰＲＯＭ３０に書き込む処理や、ＥＥＰＲＯＭ３０に格納された鍵データを読み出して暗号処理部２０に供給する処理をプログラムに基づいて実行する。
【００３３】
ＲＡＭ５０は、ＣＰＵ４０によるプログラムの実行過程で利用される一時的なデータを格納する。
ＲＯＭ６０は、ＣＰＵ４０において実行されるプログラムを格納する。
【００３４】
次に、上述した乱数生成部１０のより詳細な構成について述べる。
【００３５】
図２は、本発明の第１の実施形態に係る乱数生成部１０の構成の一例を示すブロック図である。
図２に示す乱数生成部１０は、乱数生成手段の実施形態である物理乱数生成部１と、補正手段の実施形態である補正部２と、補正情報生成手段の実施形態である補正情報生成部３と、複数のデータ格納手段の実施形態であるＦＩＦＯ４と、インターフェース部５とを有する。
【００３６】
物理乱数生成部１は、物理現象の不規則性に基づいて乱数を生成する。このような乱数生成方式としては、例えば、抵抗体の熱雑音に基づいて乱数を生成する方式や、リングオシレータなどのアナログカオス回路から出力されるカオス信号に基づいて乱数を生成する方式などが適用可能である。
また、物理乱数生成部１は、ＣＰＵ４０よりインターフェース部５を介して入力される制御信号に応じて、乱数の生成を開始または停止しても良い。これにより、乱数の生成が不要な場合に乱数の生成動作を停止させることが可能となり、無駄な消費電力が減少する。
【００３７】
補正部２は、物理乱数生成部１において生成される乱数データＳ１を、入力される補正情報Ｓ３に基づいて補正する。補正情報Ｓ３は、後述するように、乱数データＳ１の各ビットデータを‘１’に補正するか、‘０’に補正するか、または、そのままの値を保つかの指示を与える情報であり、補正部２は、この情報に基づいて各ビットデータを補正する。
【００３８】
補正情報生成部３は、補正部２において補正された乱数データＳ２に所定のビット値、例えば‘１’のビット値を持つビットデータが出現する頻度に応じて、補正情報Ｓ３を生成する。図２に示す例では、乱数データＳ２に‘１’のビットデータが出現する頻度を、ＦＩＦＯ４に格納される補正後の一連の乱数データに基づいて算出している。補正情報生成部３は、この算出した頻度に応じて、補正前の乱数データＳ１に対する補正情報Ｓ３を生成する。
また、補正情報生成部３は、ＣＰＵ４０よりインターフェース部５を介して入力される制御信号に応じて、補正情報の生成を開始または停止しても良い。これにより、乱数の生成が不要な場合に補正情報の生成動作を停止させることが可能となり、無駄な消費電力が減少する。
なお、補正情報生成部３の構成と動作については、後で更に詳細に説明する。
【００３９】
ＦＩＦＯ４は、補正部２において補正された乱数データＳ２を順に格納する。
ＦＩＦＯ４は、例えば、内部に所定データ長のデータを格納可能な所定数のデータ格納用のメモリを有しており、補正後の所定データ長の乱数データＳ２を、これらのメモリに順に格納する。全てのメモリに乱数データが格納されると、既に格納された乱数データ中で最も先に格納された乱数データを廃棄し、その空きメモリに新たな乱数データＳ２を格納する。このようなデータ格納動作が繰り返されることにより、ＦＩＦＯ４には、補正部２において補正された一連の乱数データが所定数格納される。
また、ＦＩＦＯ４は、ＣＰＵ４０よりインターフェース部５を介して入力される制御信号に応じて、上述した乱数データの格納動作を開始または停止しても良い。これにより、乱数の生成が不要な場合にデータ格納動作を停止させることが可能となり、無駄な消費電力が減少する。
【００４０】
なお、このＦＩＦＯ４は、補正部２において補正された乱数データＳ２のみ格納可能であり、さらに、補正情報生成部３からのみ格納データの読み出しが可能としても良い。これにより、バスＢＳからＦＩＦＯ４に直接アクセスすることが不可能となり、ＦＩＦＯ４に格納された乱数データの機密性が高まる。
【００４１】
インターフェース部５は、補正部２において補正された乱数データＳ２をバスＢＳに出力する。また、特に図示していないが、バスＢＳを介して伝送されるＣＰＵ４０からの制御信号を入力し、乱数生成部１０の各ユニットに供給する。
【００４２】
次に、上述した補正部２および補正情報生成部３のより詳細な構成について述べる。
【００４３】
図３は、補正部２および補正情報生成部３の構成の一例を示すブロック図である。
図３に示す補正情報生成部３は、計数部３−１と、計数値レジスタ３−２と、上限比較部３−３と、下限比較部３−４と、ＡＮＤマスク・レジスタ３−５と、ＯＲマスク・レジスタ３−６とを有する。
図３に示す補正部２は、ＡＮＤ演算部２−１と、ＯＲ演算部２−２とを有する。
【００４４】
計数部３−１は、ＦＩＦＯ４に格納される所定数の乱数データの中に‘１’のビット値を持つビットデータが存在する数を計数する。
例えば、計数部３−１は、ＦＩＦＯ４に格納される所定数の乱数データにおける同一桁のビットデータ中に‘１’のビットデータが存在する数を、それぞれの桁について計数する。すなわち、それぞれの桁における‘１’のビットデータの数を計数する。
【００４５】
計数値レジスタ３−２は、計数部３−１における各桁の‘１’の計数結果を格納する。
【００４６】
上限比較部３−３は、計数値レジスタ３−２に格納される各桁の計数結果と所定の上限しきい値とを比較する。この比較の結果、‘１’の計数結果が上限しきい値を超える桁を検出し、その桁のビット値を‘０’に設定するための補正情報として、ＡＮＤマスク・データを生成する。
【００４７】
下限比較部３−４は、計数値レジスタ３−２に格納される各桁の計数結果と所定の下限しきい値とを比較する。この比較の結果、‘１’の計数結果が下限しきい値を下回る桁を検出し、その桁のビット値を‘１’に設定するための補正情報として、ＯＲマスク・データを生成する。
【００４８】
ＡＮＤマスク・レジスタ３−５は、上限比較部３−３において生成されるＡＮＤマスク・データを格納する。
【００４９】
ＯＲマスク・レジスタ３−６は、下限比較部３−４において生成されるＯＲマスク・データを格納する。
【００５０】
ＡＮＤ演算部２−１は、物理乱数生成部１において生成される乱数データＳ１のビットデータと、ＡＮＤマスク・レジスタ３−５に格納されるＡＮＤマスク・データのビットデータとを、対応する桁同士で論理積演算する。
【００５１】
ＯＲ演算部２−２は、ＡＮＤ演算部２−１において補正された乱数データのビットデータと、ＯＲマスク・レジスタ３−６に格納されるＯＲマスク・データのビットデータとを、対応する桁同士で論理和演算する。
【００５２】
ここで、上述した構成を有する暗号処理装置１００の動作について、図４に示すフローチャートを参照して説明する。
【００５３】
ＲＯＭ６０に格納されたプログラムがＣＰＵ４０に読み込まれて実行されると、このプログラムに基づいて暗号処理部２０の処理が起動され、鍵データの生成処理や、平文の暗号化処理、暗号文の復号化処理、デジタル署名の生成・検証処理などの暗号処理が実行される。
鍵データの生成処理において生成された鍵データは、ＥＥＰＲＯＭ３０に格納される。デジタル署名の生成や復号化処理において用いられる秘密鍵のデータは、ＥＥＰＲＯＭ３０より読み出されて暗号処理部２０に供給される。
また、鍵データの生成処理やデジタル署名の生成処理において用いられる乱数は、乱数生成部１０において生成されて暗号処理部２０に供給される。
【００５４】
ＣＰＵ４０から乱数の生成命令が乱数生成部１０に与えられると、乱数生成部１０では、次に述べる初期化動作が実行される（ステップＳＴ１０１）。
【００５５】
まず、物理乱数生成部１が起動し、乱数の生成が開始される。初期化動作時では、補正部２による乱数の補正が行われず、物理乱数生成部１で生成された乱数データＳ１がそのまま乱数データＳ２としてＦＩＦＯ４に順次格納される。
以下の説明では、一例として、物理乱数生成部１において生成される乱数データが３２ビットのデータ長を有するものとする。またＦＩＦＯ４は、図５に示すように、３２ビットの乱数データをそれぞれ格納可能な３２ブロックのメモリを有するものとする。
【００５６】
３２ブロック分の乱数データＳ２がＦＩＦＯ４に格納されると、続いて、計数部３−１において、乱数データの各桁の‘１’が計数される。
すなわち、ＦＩＦＯ４に格納された乱数データにおける同一桁のビットデータ中に存在する‘１’のビットデータの数が、３２桁のそれぞれについて計数される。この計数結果は、計数値レジスタ３−２に初期値として格納される。
【００５７】
図６は、計数値レジスタ３−２に格納される各桁の計数値Ａ［０］〜Ａ［３１］を示す図である。図６の例において、計数値レジスタ３−２に格納される計数値のビット幅は８ビットである。
【００５８】
図８は、計数部３−１における‘１’の計数動作を説明するための図である。図８（Ａ）に示すように、乱数データのビット値が‘１’となる数が、ＦＩＦＯ４に格納される３２個の乱数データの各桁についてそれぞれ計数される。したがって、計数値の最小値は０であり、最大値は３２である。図８（Ｂ）は、この計数値Ａ［０］〜Ａ［３１］が計数値レジスタ３−２に格納される様子を図解している。
【００５９】
各桁の計数値Ａ［０］〜Ａ［３１］の初期値が計数値レジスタ３−２に初期値として格納されると、次に、これらの計数値は、上限比較部３−３において所定の上限しきい値と比較される。この比較の結果、計数値が上限しきい値を超える桁が検出されると、その桁のビット値を‘０’に補正するＡＮＤマスク・データが生成される。生成されたＡＮＤマスク・データは、初期値としてＡＮＤマスク・レジスタ３−５に格納される。
また、計数値レジスタ３−２の計数値は、下限比較部３−４において所定の下限しきい値と比較される。この比較の結果、計数値が下限しきい値を下回る桁が検出されると、その桁のビット値を‘１’に補正するＯＲマスク・データが生成される。生成されたＯＲマスク・データは、初期値としてＯＲマスク・レジスタ３−６に格納される。
【００６０】
図７は、ＡＮＤマスク・レジスタ３−５に格納されるＡＮＤマスク・データ、および、ＯＲマスク・レジスタ３−６に格納されるＯＲマスク・データを示す図である。図７の例に示すように、ＡＮＤマスク・データおよびＯＲマスク・データは、乱数データＳ１と同じ３２ビットのデータ長を有する。
【００６１】
図９は、計数値レジスタ３−２に格納される各桁の計数値Ａ［０］〜Ａ［３１］の一例を図解した図である。図の縦軸は計数値を示し、横軸は３２桁のそれぞれに対応する桁番号を示す。
例えば上限しきい値ＴＨが１７であるとすると、図９の例において、桁番号６の桁（最下位桁から数えて７番目の桁）が上限しきい値ＴＨを超えている。この場合、上限しきい値ＴＨを超える桁が他に存在しないものとすると、上限比較部３−３において生成されるＡＮＤマスク・データは、２進数で‘１…１０１１１１１１’、１６進数で‘ＦＦＦＦＦＦＢＦ’というデータになる。
また、下限しきい値ＴＬが１５であるとすると、図９の例において、桁番号８（最下位桁から数えて９番目の桁）が下限しきい値ＴＬを下回っている。この場合、下限しきい値ＴＬを下回る桁が他に存在しないものとすると、下限比較部３−４において生成されるＯＲマスク・データは、２進数で‘０…０１００００００００’、１６進数で‘０００００１００’というデータになる。
【００６２】
以上のような初期化動作によって、計数値レジスタ３−２、ＡＮＤマスク・レジスタ３−５、ＯＲマスク・レジスタ３−６に初期値が設定されると、次いで、物理乱数生成部１において乱数データＳ１が生成され、補正部２に入力される（ステップＳＴ１０２）。
【００６３】
補正部２のＡＮＤ演算部２−１では、物理乱数生成部１において生成される乱数データＳ１と、ＡＮＤマスク・レジスタ３−５に格納されるＡＮＤマスク・データとのビット単位の論理積が演算される（ステップＳＴ１０３）。
また、補正部２のＯＲ演算部２−２では、ＡＮＤ演算部２−１において補正された乱数データと、ＯＲマスク・レジスタ３−６に格納されるＯＲマスク・データとのビット単位の論理和が演算される（ステップＳＴ１０４）。
【００６４】
例えば図１０（Ａ）に示すように、ＡＮＤマスク・レジスタ３−５に格納されるＡＮＤマスク・データが１６進数で‘ＦＦＦＦＦＦＢＦ’という値を持ち、ＯＲマスク・レジスタ３−６に格納されるＯＲマスク・データが１６進数で‘０００００１００’という値を持つものとする。
この状態で、物理乱数生成部１から１６進数で‘３８７８Ｂ６Ｃ０’という値の乱数データＳ１が出力されると、この乱数データＳ１とＡＮＤマスク・データとの論理積によって最下位桁から７番目の桁のビットデータが‘０’に設定されるとともに、最下位桁から９番目の桁のビットデータが‘１’に設定される。その結果、‘３８７８Ｂ６Ｃ０’の乱数データＳ１は‘３８７８Ｂ７８０’の乱数データＳ２へ補正される。
【００６５】
このようにして、補正部２で補正された乱数データＳ２は、インターフェース部５を介して外部バスＢＳに出力される（ステップＳＴ１０５）。
【００６６】
また、補正部２で補正された乱数データＳ２は、ＦＩＦＯ４において最も先に格納された乱数データの代わりとして、新たにＦＩＦＯ４に格納される（ステップＳＴ１０６）。
【００６７】
ＦＩＦＯ４に補正後の乱数データが格納されることによって、ＦＩＦＯ４の内容が更新されると、これに応じて、計数部３−１における‘１’の計数値も更新され、この更新された計数値が新たに計数値レジスタ３−２に格納される（ステップＳＴ１０７）。
【００６８】
計数値レジスタ３ー２の計数値が更新されると、上限比較部３−３では、更新された計数値と上限しきい値との新たな比較が行われ、その結果として、ＡＮＤマスク・レジスタ３−５に格納されるＡＮＤマスク・データの値が更新される（ステップＳＴ１０８）。また、下限比較部３−４では、更新された計数値と下限しきい値との新たな比較が行われ、その結果として、ＯＲマスク・レジスタ３−６に格納されるＯＲマスク・データの値が更新される（ステップＳＴ１０９）。
【００６９】
次いでステップＳＴ１１０において、ＣＰＵ４０からの命令に基づいて、乱数の生成を終了するか否かの判断がなされ、さらに乱数の生成を行う場合には、再びステップＳＴ１０２の処理に戻り、上述した乱数データＳ１の補正と、各レジスタ（３−２、３−５、３−６）の格納データの更新が繰り返される。また、乱数生成の終了が判断された場合には、物理乱数生成部１における乱数の生成、補正情報生成部３における補正情報の生成、ＦＩＦＯにおける乱数データＳ２の格納動作が停止され（ステップＳＴ１１１）、乱数生成動作が終了する。
【００７０】
図１１は、上述した乱数生成部１０によって生成した２００００ビットの乱数に含まれる‘１’の数を複数回にわたって検査した結果の一例を示す図である。図の縦軸の値は２００００ビット中の‘１’の数を示し、横軸の値は各検査の番号を示す。
図１１の例に示すように、上述した乱数生成部１０において生成される乱数に‘１’が出現する確率は概ね５０％となり、図１７の例に示すようなアナログ乱数生成器をそのまま用いる場合に比べて、乱数に出現するビット値の偏りが低減している。
【００７１】
以上説明したように、図２に示す乱数生成部１０によれば、物理乱数生成部１の乱数データＳ１が補正情報Ｓ３に基づいて補正され、この補正された乱数データＳ２に所定のビット値（例えば‘１’）を持つビットデータが出現する頻度に応じて、新たな補正情報Ｓ３が生成される。したがって、補正部２において補正された乱数データＳ２に所定のビット値が出現する頻度を制御することが可能になり、これにより、生成した乱数に出現するビット値の偏りを低減することが可能になる。
【００７２】
また、物理乱数生成部１において、乱数データＳ１が物理現象の不規則性に基づいて生成されることから、擬似乱数のような周期性が無く、より安全性の高い乱数を生成することができる。
【００７３】
しかも、図２および図３の例に示す乱数生成部１０は、物理乱数生成部１に加えて、補正後の一連の乱数データを所定数だけ格納するＦＩＦＯ４と、このＦＩＦＯ４に格納される所定数の乱数データの中に所定のビット値のビットデータが存在する数を計数する計数部３−１と、この計数値と所定の上限しきい値および下限しきい値との比較結果に基づいて補正情報Ｓ３を生成する上限比較部３−３および下限比較部３−４と、生成された補正情報Ｓ３と乱数データＳ１との論理演算を行うユニット（２−１、２−３）とを有しているが、これらの構成は、ＤＥＳ方式やＳＨＡ−１方式等の従来の暗号演算回路を用いて擬似乱数を生成する場合に比べて明らかに簡易であり、このような従来の回路を用いる場合に比べて回路規模を大幅に縮小することができる。
【００７４】
したがって、図１に示す暗号処理装置１００によれば、偏りや周期性のない乱数を用いた安全性の高い暗号処理を実行することができるとともに、従来の高度な擬似乱数生成方式を用いる場合に比べて回路構成を簡易化することができる。
【００７５】
＜第２の実施形態＞
図１２は、本発明の第２の実施形態に係る乱数生成部１０Ａの構成の一例を示す図である。
【００７６】
第２の実施形態においては、乱数生成部の一部の機能が、プログラムに基づいて処理を実行するコンピュータ等の処理装置によって実現される。
例えば、図２に示す乱数生成部１０における補正部２および補正情報生成部３は、図１２に示す乱数生成部１０Ａにおいて、処理部６およびプログラムメモリ７に置き換えらる。
【００７７】
処理部６は、プログラムメモリ７に格納されるプログラムに基づいて、例えば既に述べた図４に示すフローチャートに示すような、乱数生成に係る処理を実行する。
すなわち、初期化動作（ステップＳＴ１０１）において補正情報Ｓ３の初期値を生成し、この初期値に基づいて、物理乱数生成部１において生成される乱数データＳ１を補正する（ステップＳＴ１０３およびＳＴ１０４）。そして、この補正した乱数データＳ２をインターフェース部５からバスＢＳに出力する（ステップＳＴ１０５）とともに、ＦＩＦＯ４に格納する（ステップＳＴ１０６）。次いで、補正した乱数データＳ２に所定のビット値を持つビットデータが出現する頻度として、例えば、ＦＩＦＯ４に格納された一連の所定数の乱数データ中に‘１’のビット値を持つビットデータが存在する数を新たに計数し（ステップＳＴ１０７）、この計数値に応じて、補正情報Ｓ３を更新する（ステップＳＴ１０８およびＳＴ１０９）。ＣＰＵ４０の命令に応じて、上述と同様な乱数データＳ１の補正と補正情報Ｓ３の更新を更に繰り返し、乱数データＳ２を生成する。
【００７８】
以上説明した乱数生成部１０Ａにおいても、図２に示す乱数生成部１０と同様に、偏りや周期性のない乱数を生成することができる。また、ＤＥＳ方式やＳＨＡ−１方式等の暗号アルゴリズムを用いた擬似乱数生成方法に比べて、処理手順が明らかに簡易であり、プログラムのコード量を削減できるとともに、処理の高速化を図ることができる。
【００７９】
＜第３の実施形態＞
図１３は、本発明の第３の実施形態に係るハードウェア・トークンの構成の一例を示すブロック図である。
【００８０】
ハードウェア・トークンは、所有者が確かに本人であることを証明する情報であって、他人に勝手に使われないよう秘匿すべき情報（例えば公開鍵暗号方式における秘密鍵など）を安全に保管することができる携帯性を有したデバイスである。本実施形態は、このようなハードウェア・トークンに本発明の乱数生成装置を適用したものである。
【００８１】
図１３に示すハードウェア・トークン１０１は、乱数生成装置の実施形態である乱数生成部１０と、暗号処理手段の実施形態であるＲＳＡ演算器２１およびＳＨＡ演算器２２と、ＥＥＰＲＯＭ３０と、ＣＰＵ４０と、ＲＡＭ５０と、ＲＯＭ６０と、ＥＣＣ部７０と、シリアル・インターフェース部８０とを有する。なお、図１と図１３の同一符号は同一の構成要素を示す。
【００８２】
ＲＳＡ演算器２１は、バスＢＳを介して入力されるＣＰＵ４０からの制御信号に応じて、ＲＳＡ方式の暗号処理に係わる演算を実行する。
例えば、公開鍵および秘密鍵のペアを生成する鍵生成処理や、公開鍵を使って平文を暗号化する暗号化処理、秘密鍵を使って暗号文を復号する復号化処理を行う。
【００８３】
ＳＨＡ演算器２２は、バスＢＳを介して入力されるＣＰＵ４０からの制御信号に応じて、与えられた平文に対するＳＨＡ方式のハッシュ値を演算する。
【００８４】
ＥＣＣ部７０は、シリアル・インターフェース部８０を介してコンピュータ２００から伝送される信号の誤り検出および訂正処理を行う。また、シリアル・インターフェース部８０を介してコンピュータ２００に送出する信号に所定の誤り訂正符号化処理を施す。
【００８５】
シリアル・インターフェース部８０は、例えばＵＳＢ（ｕｎｉｖｅｒｓａｌｓｅｒｉａｌｂｕｓ）方式やＵＡＲＴ（ｕｎｉｖｅｒｓａｌａｓｙｎｃｈｒｏｎｏｕｓｒｅｃｅｉｖｅｒ−ｔｒａｎｓｃｅｉｖｅｒ）方式などのシリアル通信方式によって、コンピュータ２００との間で信号の受け渡しを行う。
【００８６】
次に、上述した構成を有する図１３に示すハードウェア・トークン１０１の動作を説明する。
【００８７】
コンピュータ２００に導入されたソフトウェアが起動し、このソフトウェア上でユーザ認証に係わる処理が実行されると、これに応じた種々の命令がコンピュータ２００からハードウェア・トークン１０１へ入力される。ハードウェア・トークン１０１では、ＲＯＭ６０に格納されたプログラムに基づいて、コンピュータ２００からの命令に応じた暗号処理、例えば、ＲＳＡ方式の鍵ペアの生成処理や、ＥＣＤＳＡ（ｅｌｌｉｐｔｉｃｃｕｒｖｅｄｉｇｉｔａｌｓｉｇｎａｔｕｒｅａｌｇｏｒｉｔｈｍ）方式のデジタル署名の生成・検証処理が実行される。
【００８８】
図１４は、ＲＳＡ方式の鍵ペアの生成処理の一例を示すフローチャートである。
【００８９】
まず、乱数生成部１０において乱数Ｐの生成が実行され（ステップＳＴＳＴ２０１）、ＲＳＡ演算器２１に供給される。ＲＳＡ演算器２１では、供給された乱数Ｐが素数であるか否かの判定処理が実行され（ステップＳＴ２０２）、素数でない場合はステップＳＴ２０１に戻り、再び乱数Ｐの生成と素数判定が行われる。
乱数Ｐが素数であると判定された場合には、更に、乱数生成部１０において乱数Ｑの生成が実行され（ステップＳＴＳＴ２０３）、乱数Ｑが素数であるか否かの判定がＲＳＡ演算器２１において実行される（ステップＳＴ２０４）。素数でない場合はステップＳＴ２０３に戻り、再び乱数Ｑの生成と素数判定が行われる。
【００９０】
乱数生成部１０において生成された乱数から素数ＰおよびＱが得られると、ＲＳＡ演算器２１では、この素数ＰおよびＱに基づいて、次式に示す公開鍵Ｎが算出される（ステップＳＴ２０５）。
【００９１】
【数１】
Ｎ＝Ｐ×Ｑ … （１）
【００９２】
また秘密鍵ｄとしては、所定数ｅ（例えば４０９７）と素数ＰおよびＱとの間で次式を成立させるような数が算出される（ステップＳＴ２０６）。
【００９３】
【数２】
（ｄ×ｅ）ｍｏｄ（Ｐ−１）×（Ｑ−１）＝１ … （２）
【００９４】
このようにして算出された公開鍵Ｎおよび秘密鍵ｄは、ＥＥＰＲＯＭ３０に格納される。
【００９５】
図１５は、ＥＣＤＳＡ方式のデジタル署名生成処理の一例を示すフローチャートである。
【００９６】
まず、乱数生成部１０において、乱数ｕの生成が実行され（ステップＳＴ３０１）、生成された乱数ｕに基づいて、次式に示す署名ｃが生成される。
【００９７】
【数３】
ｃ＝（ｕ・Ｇ）_ｘｍｏｄｒ … （３）
【００９８】
ただし、式（３）における記号‘Ｇ’は楕円曲線のベースポイント座標を示し、記号‘ｒ’は楕円曲線の位数を示す。また、括弧で表す記号‘（）_ｘ’は、括弧内の演算によって求められる楕円曲線上の点のｘ座標を示す。
【００９９】
次いで、署名を行う平文ｍに対するＳＨＡ−１方式のハッシュ値ｆが、ＳＨＡ演算器２２において算出される（ステップＳＴ３０３）。この算出されたハッシュ値ｆと、署名ｃ、乱数ｕ、更には署名者の秘密鍵ｓに基づいて、署名ｄが次式により算出される（ステップＳＴ３０４）。
【０１００】
【数４】
ｄ＝ｃ^−１（ｆ＋ｓｃ）ｍｏｄｒ … （４）
【０１０１】
このようにして生成された署名ｃおよびｄが、平文ｍとともにコンピュータ２００へ送信される。
【０１０２】
図１６は、ＥＣＤＳＡ方式のデジタル署名検証処理の一例を示すフローチャートである。
【０１０３】
デジタル署名検証処理においては、コンピュータ２００から平文ｍとその署名ｃおよびｄが入力される。また、署名者の公開鍵座標Ｗもコンピュータ２００から入力される。
入力された平文ｍは、ＳＨＡ演算器２２に供給され、そのハッシュ値ｆが算出される（ステップＳＴ４０１）。次いで、算出されたハッシュ値ｆと、署名ｃおよびｄ、公開鍵座標Ｗに基づいて、次式に示す署名検証値ｖが演算される。
【０１０４】
【数５】
ｖ＝（（ｄ^−１ｆ）・Ｇ＋（ｃｄ^−１）・Ｗ）_ｘｍｏｄｒ …（５）
【０１０５】
演算された署名検証値ｖは、コンピュータ２００に送信される。コンピュータ２００のソフトウェアでは、署名検証値ｖが署名ｄと一致するか否かに応じて、署名ｄおよびｃが公開鍵座標Ｗの署名者によるものであるか否かの判定が行われる。
【０１０６】
以上説明したように、図１３に示すハードウェア・トークン１０１によれば、乱数生成部１０において生成されるビット値の偏りや周期性の少ない乱数を用いて、鍵データの生成処理やデジタル署名の生成処理などの暗号処理が実行されるため、より安全性の高い個人認証が可能となる。また、簡易な構成の乱数生成部１０を用いることにより、装置の小型化や低消費電力化を図ることができる。
【０１０７】
なお、本発明は上述した実施形態に限定されない。
例えば、図２における補正情報生成部３や図１２における処理部６は、ＣＰＵ４０などから入力される制御信号に応じて、上限しきい値および下限しきい値を変化させても良い。これにより、乱数における‘１’と‘０’の発生確率を任意に制御することが可能になる。
【０１０８】
また、上述した実施形態では、ＣＰＵ４０からの命令に応じて、乱数生成部における乱数生成動作の開始と停止が制御されているが、ＣＰＵ４０からの命令に係わらず、常に乱数生成動作を起動させた状態にしても良い。これにより、ＦＩＦＯ４の状態や各レジスタ（３−２、３−５、３−６）の状態が常に更新されるため、更に予測することが困難な乱数を生成させることができる。
【０１０９】
また、上述した実施形態では、ＦＩＦＯ４に格納される所定数の乱数データに含まれる‘１’の数を桁ごとに計数し、各桁の計数結果に応じて各桁の補正情報Ｓ３が生成されているが、本発明はこの例に限定されない。
例えば、ＦＩＦＯ４に格納される乱数データの全ビットデータにおける‘１’の数を計数し、その計数値としきい値との比較結果に基づいて、物理乱数生成部１から出力される乱数データＳ２を１ビットずつ補正しても良い。
この場合、ＦＩＦＯ４に格納される‘１’のビットデータの数は、例えば、ＦＩＦＯ４に入力されるビットデータの値と、その入力とともに廃棄されるビットデータの値とに応じて算出することができる。すなわち、ＦＩＦＯ４に‘１’のビットデータが格納される場合にインクリメントし、ＦＩＦＯ４から‘１’のビットデータが廃棄される場合にデクリメントするカウンタを設けることにより、そのカウント値から、ＦＩＦＯ４に含まれる‘１’のビットデータの数を求めることができる。
【０１１０】
また、上述した実施形態では、補正部２において補正された乱数データのうち、ＦＩＦＯ４に格納される前の乱数データがインターフェース部５を介して出力されているが、ＦＩＦＯ４に既に格納された乱数データを出力する構成としても良い。
【０１１１】
【発明の効果】
本発明の乱数生成装置によれば、簡易な構成でありながら、ビット値の偏りや周期性の少ない乱数を生成することができる。
また、本発明のプログラムによれば、ビット値の偏りや周期性の少ない乱数の生成に係る処理を、より簡易な手順でコンピュータに実行させることができる。
また、本発明の暗号処理装置によれば、簡単な構成でありながら、偏りや周期性のない乱数を用いた安全性の高い暗号処理を実行することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係る暗号処理装置の構成の一例を示すブロック図である。
【図２】本発明の第１の実施形態に係る乱数生成部の構成の一例を示すブロック図である。
【図３】図２に示す補正部および補正情報生成部の構成の一例を示すブロック図である。
【図４】本発明の第１の実施形態に係る乱数生成部の処理の一例を示すフローチャートである。
【図５】ＦＩＦＯのメモリ構成の一例を示す図である。
【図６】計数値レジスタに格納される各桁の計数値を示す図である。
【図７】ＡＮＤマスク・レジスタおよびＯＲマスク・レジスタに格納されるマスク・データの一例を示す図である。
【図８】計数部における‘１’の計数動作を説明するための図である。
【図９】計数値レジスタに格納される各桁の計数値の一例を図解した図である。
【図１０】補正部における乱数データの補正処理の具体例を示す図である。
【図１１】図２に示す乱数生成部によって生成した２００００ビットの乱数に含まれる‘１’の数を複数回にわたって検査した結果の一例を示す図である。
【図１２】本発明の第２の実施形態に係る乱数生成部の構成の一例を示す図である。
【図１３】本発明の第３の実施形態に係るハードウェア・トークンの構成の一例を示すブロック図である。
【図１４】図１３に示すハードウェア・トークンにおけるＲＳＡ方式の鍵ペアの生成処理の一例を示すフローチャートである。
【図１５】図１３に示すハードウェア・トークンにおけるＥＣＤＳＡ方式のデジタル署名生成処理の一例を示すフローチャートである。
【図１６】図１３に示すハードウェア・トークンにおけるＥＣＤＳＡ方式のデジタル署名検証処理の一例を示すフローチャートである。
【図１７】アナログ乱数生成器によって生成した２００００ビットの乱数に含まれる‘１’の数を複数回にわたって検査した結果を示す図である。
【符号の説明】
１…物理乱数生成部、２…補正部、２−１…ＡＮＤ演算部、２−２…ＯＲ演算部、３…補正情報生成部、３−１…計数部、３−２…計数値レジスタ、３−３…上限比較部、３−４…下限比較部、３−５…ＡＮＤマスク・レジスタ、３−６…ＯＲマスク・レジスタ、４…ＦＩＦＯ、５…インターフェース部、６…処理部、７…プログラムメモリ、１０，１０Ａ…乱数生成部、２０…暗号処理部、２１…ＲＳＡ演算器、２２…ＳＨＡ演算器、３０…ＥＥＰＲＯＭ、４０…ＣＰＵ、５０…ＲＡＭ、６０…ＲＯＭ、７０…ＥＣＣ部、８０…シリアル・インターフェース部、１００…暗号処理装置、１０１…ハードウェア・トークン、２００…コンピュータ[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a random number generation device and method, a cryptographic processing device including random number generation means, and a program that causes a computer to execute processing related to random number generation.
[0002]
[Prior art]
In recent years, with the spread of data communication using the Internet, it has become an important issue to increase the safety of data communication. In particular, encryption technology has attracted attention as a technology for ensuring the confidentiality of data communication. Yes.
[0003]
Typical encryption methods in data communication using a computer network include a common key encryption method and a public key encryption method.
The common key encryption method uses the same encryption key for encryption and decryption, and is also called “secret key encryption”, “symmetric key encryption”, and “conventional encryption”.
On the other hand, the public key cryptosystem uses a different encryption key for encryption and decryption. According to the public key cryptosystem, data encrypted with one encryption key cannot be decrypted without using the other key. For this reason, by keeping one key secret, the secret of the ciphertext can be maintained even if the other key is made public.
[0004]
In the common key cryptosystem, since the encryption key and the decryption key are the same, it is difficult to pass the key to the communication partner in a secure manner, and a means for sharing the key is required. In contrast, in the public key cryptosystem, the encryption key and the decryption key are different. Therefore, the encryption key can be distributed over a communication network whose security is not guaranteed, and the encryption key is transmitted to the communication partner. It is very easy to pass.
[0005]
As described above, the public key cryptosystem has an advantage that it is very easy to distribute the key, but on the other hand, there is a disadvantage that the processing time becomes very long as compared with the common key cryptosystem. For example, the processing speed of the RSA (Rivest Shamir Adelman) method, which is a representative public key encryption method, is about 1000 times slower than the common key encryption method for both encryption and decryption.
[0006]
Therefore, in the case of configuring a high-speed encryption system in data communication using a computer network, generally, encryption and decryption use a common key encryption, and the key is encrypted by public key encryption and distributed. Is used. Examples of cryptographic systems that employ this method include PGP (Pretty Good Privacy (trademark)) and PEM (Privacy Enhancement Mail).
The RSA system is mainly used for such a common key exchange and a relatively small amount of data transmission.
[0007]
If the above encryption technology is used, it is necessary for data encryption and personal authentication in order to realize electronic money, music distribution on the Internet, personal services using mobile phones and ID cards, etc. Digital signatures can be generated.
[0008]
By the way, in order to guarantee secure data communication using such an encryption technique, it is indispensable to generate a secure random number. The main uses of random numbers include, for example, creation of passwords, creation of keys used for encryption, generation of ciphertexts, generation of electronic signature information, and the like. If a random number for such an application is guessed by an attacker, the risk of the ciphertext being decrypted or the signature being tampered with increases. Therefore, it is very important to generate random numbers that cannot be easily guessed by an attacker.
[0009]
There are two methods for generating random numbers: a method of generating random numbers using irregularities of physical phenomena, and a method of generating a random number sequence having a long period by mathematical arithmetic processing.
[0010]
As a method of generating random numbers using irregularities of physical phenomena, for example, a method of generating random numbers by thermal noise of a resistor, or analog-digital conversion (hereinafter referred to as A / D) from analog output of a ring oscillator or the like. There is a method of obtaining a random number by a conversion).
However, these methods do not always provide a rough random number that is not biased at all, and may cause bit-wise bias or periodicity. If such a random number is used as a secret key for a public key cryptosystem or a session key for a digital signature, there is a concern that the security may be lowered.
[0011]
“Statistical random number generator test” is defined in FIPS (federal information processing standards) 140-2 as an evaluation standard of randomness roughness. According to this evaluation criterion, when random numbers of 20000 bits are continuously generated, the randomness of the random numbers is evaluated by the number of “1” included in the 20000 bits.
FIG. 17 is a diagram illustrating a result of checking the number of “1” included in a 20000-bit random number generated by an analog random number generator a plurality of times. The value on the vertical axis in the figure indicates the number of “1” in 20000 bits, and the value on the horizontal axis indicates the number of each test.
If the random number is completely coarse, the probability of occurrence of “0” and “1” is 50%, and the number of “1” is around 10,000. However, in the example of FIG. 17, the probability of occurrence of “1” is clearly lower than 50%.
[0012]
As a method for dealing with such a bias in bit values, there is a method using pseudo random numbers (see Patent Documents 1 to 4).
For example, a pseudo random number generation circuit combining a plurality of linear circuits such as an M-sequence generation circuit, a cryptographic operation circuit in a common key encryption system such as a DES (data encryption standard) system, a SHA-1 (Secure Hash Algorithm -1) system, There is a method of obtaining a uniform pseudo-random number with less bias in bit values by inputting a random number generated by the above-described physical means as a seed to a hash calculation circuit in the MD5 (message digest 5) method or the like.
[0013]
In a general pseudo random number generation method, a pseudo random number is generated by repeating a predetermined random number calculation for a given seed. That is, assuming that the random number calculation function is F, if an initial value R (0) is given as a seed, the random number sequence R (1), R (2), R (3),. = F (R (i)) ". Then, by combining the random numbers R (1), R (2), R (3),..., A pseudo random number having a desired length is generated.
[0014]
[Patent Document 1]
JP 2000-242470 A
[Patent Document 2]
JP 2001-75476 A
[Patent Document 3]
JP 2000-4223 A
[Patent Document 4]
JP 2001-344094 A
[0015]
[Problems to be solved by the invention]
This pseudo-random number generation method does not require special hardware, can be realized by software, and has an advantage that it can be used on a microcomputer. However, as described above, since the random number sequence is generated by a predetermined function using the initial value, when the function and the initial value are determined, all the random number sequences are determined. For this reason, if the function and the initial value are known, there is a disadvantage that a random number sequence can be easily generated by the same method.
[0016]
As an example, in the pseudorandom number generation method using the SHA-1 method in FIPS 186, a bit string t having a length of 160 bits and a bit string c having a length of b bits (160 ≦ b ≦ 512) are represented by SHA−. A random number of 160 bits is generated by giving to one arithmetic unit. In this method, after storing the bit string c in the 512-bit input buffer of the SHA-1 arithmetic unit, (512-b) pieces of “0” are stored in the remaining storage area of the input buffer. When c is determined, the output of the SHA-1 calculator is always constant with respect to the input of the bit string c.
[0017]
In addition, these pseudo-random number generation methods have the disadvantage that the circuit scale when implemented by hardware becomes very large, and that a large amount of code and computation time are required when implemented by software.
[0018]
The present invention has been made in view of such circumstances, and an object of the present invention is to provide a random number generation apparatus and method capable of generating a random number with a small bias and periodicity with a simple configuration. There is.
Another object of the present invention is to provide a program capable of causing a computer to execute processing related to generation of random numbers with little bias in bit values and periodicity in a simpler procedure.
Still another object of the present invention is to provide an encryption processing apparatus capable of executing highly secure encryption processing using random numbers having no bias in bit values or periodicity with a simple configuration. .
[0019]
[Means for Solving the Problems]
In order to achieve the above object, a random number generation device according to a first aspect of the present invention includes a random number generation unit and a correction unit that corrects random number data generated by the random number generation unit based on input correction information. And correction information generation means for generating the correction information according to the frequency of appearance of bit data having a predetermined bit value in the random number data corrected by the correction means.
Preferably, the random number generation means generates a random number based on irregularity of a physical phenomenon.
[0020]
According to the first aspect of the present invention, the random number data generated based on the irregularity of the physical phenomenon in the random number generation unit is corrected in the correction unit based on the input correction information. The correction information generation means generates the correction information according to the frequency of appearance of bit data having a predetermined bit value in the random number data corrected by the correction means.
[0021]
The first aspect of the present invention may have a plurality of data storage means for sequentially storing the random number data corrected by the correction means.
In this case, the correction information generation means counts the number of bit data having the predetermined bit value among the plurality of random number data stored in the data storage means, and the count value and the predetermined threshold are counted. The correction information is generated based on the comparison result with the value.
[0022]
Further, the correction information generation means may change the threshold value in accordance with an input control signal.
[0023]
The random number generation method according to the second aspect of the present invention includes a first step of correcting random number data generated by the random number generation means based on given correction information, and the random number data corrected in the first step. And a second step of newly generating the correction information in accordance with the frequency of appearance of bit data having a predetermined bit value.
[0024]
According to the second aspect of the present invention, random number data generated by the random number generation means is corrected based on the correction information provided in the first step. In the second step, the correction information is newly generated according to the frequency of appearance of bit data having a predetermined bit value in the random number data corrected in the first step.
[0025]
A program according to a third aspect of the present invention provides a first step of correcting random number data generated by a random number generation means based on given correction information, and a predetermined number of random number data corrected in the first step. A second step of newly generating the correction information in accordance with the frequency of appearance of bit data having a bit value of.
[0026]
According to a fourth aspect of the present invention, there is provided a cryptographic processing apparatus comprising: a random number generation unit; a correction unit that corrects random number data generated by the random number generation unit based on input correction information; and the correction unit corrects the random number data. Correction information generating means for generating the correction information in accordance with the frequency of occurrence of bit data having a predetermined bit value in the random number data, and executing predetermined encryption processing in accordance with the random data corrected in the correction means And cryptographic processing means.
[0027]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, three embodiments of the present invention will be described with reference to the drawings.
[0028]
<First Embodiment>
FIG. 1 is a block diagram showing an example of the configuration of a cryptographic processing apparatus according to the first embodiment of the present invention.
1 includes a random number generation unit 10 that is an embodiment of a random number generation device, an encryption processing unit 20 that is an embodiment of encryption processing means, an EEPROM 30, a CPU 40, a RAM 50, and a ROM 60. Have.
[0029]
The random number generation unit 10 generates a random number in response to a control signal from the CPU 40 input via the bus BS. For example, the generation of random numbers is started or stopped according to a control signal from the CPU 40.
The configuration and operation of the random number generation unit 10 will be described in more detail later.
[0030]
The cryptographic processing unit 20 executes predetermined cryptographic processing in accordance with a control signal from the CPU 40 input via the bus BS.
Assuming that RSA encryption processing is executed as an example, the cryptographic processing unit 20 generates, for example, a public key and private key pair according to the random number generated by the random number generation unit 10 (key generation processing). Also, processing for encrypting plaintext with the public key of the communication partner (encryption processing), processing for decrypting ciphertext encrypted with the public key with the private key that is the public key pair (decryption processing) . In addition, a process for generating a digital signature attached to a transmission sentence with a private key (digital signature generation process), a process for verifying a digital signature attached to a reception sentence with a public key of a communication partner (digital signature verification process), etc. Do.
[0031]
The EEPROM 30 is an electrically erasable programmable ROM, and stores key data used for encryption processing in accordance with a control signal from the CPU 40 input via the bus BS.
[0032]
The CPU 40 performs various controls related to the overall operation of the cryptographic processing apparatus 100 based on the program stored in the ROM 60.
For example, the cryptographic processing unit 20 is caused to execute cryptographic processing such as the above-described key generation processing, encryption processing, decryption processing, and digital signature generation / verification processing based on a program.
Further, if a random number is required in the course of executing the program, such as when generating a key in the cryptographic processing unit 20 or a session key for digital signature, the random number generating unit 10 generates it.
Further, processing for writing the key data generated in the cryptographic processing unit 20 into the EEPROM 30 and processing for reading out the key data stored in the EEPROM 30 and supplying it to the cryptographic processing unit 20 are executed based on the program.
[0033]
The RAM 50 stores temporary data used in the program execution process by the CPU 40.
The ROM 60 stores a program executed by the CPU 40.
[0034]
Next, a more detailed configuration of the random number generation unit 10 described above will be described.
[0035]
FIG. 2 is a block diagram showing an example of the configuration of the random number generation unit 10 according to the first embodiment of the present invention.
The random number generation unit 10 shown in FIG. 2 includes a physical random number generation unit 1 that is an embodiment of a random number generation unit, a correction unit 2 that is an embodiment of a correction unit, and a correction information generation unit that is an embodiment of a correction information generation unit. 3, a FIFO 4 as an embodiment of a plurality of data storage means, and an interface unit 5.
[0036]
The physical random number generator 1 generates a random number based on the irregularity of the physical phenomenon. As such a random number generation method, for example, a method for generating a random number based on thermal noise of a resistor, a method for generating a random number based on a chaos signal output from an analog chaos circuit such as a ring oscillator, or the like is applied. Is possible.
Further, the physical random number generation unit 1 may start or stop the generation of random numbers in accordance with a control signal input from the CPU 40 via the interface unit 5. As a result, the random number generation operation can be stopped when generation of random numbers is unnecessary, and wasteful power consumption is reduced.
[0037]
The correction unit 2 corrects the random number data S1 generated by the physical random number generation unit 1 based on the input correction information S3. As will be described later, the correction information S3 is information that gives an instruction to correct each bit data of the random number data S1 to '1', to '0', or to keep the value as it is. The correction unit 2 corrects each bit data based on this information.
[0038]
The correction information generation unit 3 generates the correction information S3 according to the frequency at which bit data having a predetermined bit value, for example, a bit value of “1” appears in the random number data S2 corrected by the correction unit 2. In the example shown in FIG. 2, the frequency at which the bit data “1” appears in the random number data S <b> 2 is calculated based on a series of corrected random number data stored in the FIFO 4. The correction information generation unit 3 generates correction information S3 for the random number data S1 before correction according to the calculated frequency.
Further, the correction information generation unit 3 may start or stop generating correction information in accordance with a control signal input from the CPU 40 via the interface unit 5. As a result, it is possible to stop the operation of generating correction information when random number generation is unnecessary, and wasteful power consumption is reduced.
The configuration and operation of the correction information generation unit 3 will be described in detail later.
[0039]
The FIFO 4 stores the random number data S2 corrected by the correction unit 2 in order.
The FIFO 4 has, for example, a predetermined number of data storage memories that can store data of a predetermined data length therein, and stores the corrected random number data S2 of the predetermined data length in these memories in order. When the random number data is stored in all the memories, the random number data stored first among the already stored random number data is discarded, and new random number data S2 is stored in the empty memory. By repeating such data storage operation, a predetermined number of a series of random number data corrected by the correction unit 2 is stored in the FIFO 4.
Further, the FIFO 4 may start or stop the random number data storage operation described above in accordance with a control signal input from the CPU 40 via the interface unit 5. As a result, the data storage operation can be stopped when generation of random numbers is unnecessary, and wasteful power consumption is reduced.
[0040]
The FIFO 4 can store only the random number data S2 corrected by the correction unit 2, and can read out stored data only from the correction information generation unit 3. This makes it impossible to directly access the FIFO 4 from the bus BS, and the confidentiality of the random number data stored in the FIFO 4 is increased.
[0041]
The interface unit 5 outputs the random number data S2 corrected by the correction unit 2 to the bus BS. Although not specifically shown, a control signal transmitted from the CPU 40 via the bus BS is input and supplied to each unit of the random number generation unit 10.
[0042]
Next, a more detailed configuration of the correction unit 2 and the correction information generation unit 3 described above will be described.
[0043]
FIG. 3 is a block diagram illustrating an example of the configuration of the correction unit 2 and the correction information generation unit 3.
The correction information generation unit 3 shown in FIG. 3 includes a counting unit 3-1, a count value register 3-2, an upper limit comparing unit 3-3, a lower limit comparing unit 3-4, and an AND mask register 3-5. OR mask register 3-6.
The correction unit 2 illustrated in FIG. 3 includes an AND operation unit 2-1 and an OR operation unit 2-2.
[0044]
The counting unit 3-1 counts the number of bit data having a bit value of “1” in a predetermined number of random number data stored in the FIFO 4.
For example, the counting unit 3-1 counts the number of bit data of “1” in the bit data of the same digit in a predetermined number of random number data stored in the FIFO 4 for each digit. That is, the number of bit data of “1” in each digit is counted.
[0045]
The count value register 3-2 stores a count result of “1” of each digit in the counting unit 3-1.
[0046]
The upper limit comparison unit 3-3 compares the count result of each digit stored in the count value register 3-2 with a predetermined upper limit threshold value. As a result of this comparison, a digit whose count result of “1” exceeds the upper threshold is detected, and AND mask data is generated as correction information for setting the bit value of that digit to “0”.
[0047]
The lower limit comparison unit 3-4 compares the count result of each digit stored in the count value register 3-2 with a predetermined lower limit threshold value. As a result of this comparison, a digit whose count result of “1” falls below the lower threshold is detected, and OR mask data is generated as correction information for setting the bit value of that digit to “1”.
[0048]
The AND mask register 3-5 stores AND mask data generated in the upper limit comparison unit 3-3.
[0049]
The OR mask register 3-6 stores the OR mask data generated by the lower limit comparison unit 3-4.
[0050]
The AND operation unit 2-1 converts the bit data of the random number data S1 generated by the physical random number generation unit 1 and the bit data of the AND mask data stored in the AND mask register 3-5 between corresponding digits. AND operation with.
[0051]
The OR operation unit 2-2 converts the bit data of the random number data corrected by the AND operation unit 2-1 and the bit data of the OR mask data stored in the OR mask register 3-6 between corresponding digits. Perform an OR operation with.
[0052]
Here, the operation of the cryptographic processing apparatus 100 having the above-described configuration will be described with reference to the flowchart shown in FIG.
[0053]
When the program stored in the ROM 60 is read and executed by the CPU 40, the processing of the encryption processing unit 20 is started based on this program, and key data generation processing, plaintext encryption processing, and ciphertext decryption are performed. Encryption processing such as processing and digital signature generation / verification processing is executed.
The key data generated in the key data generation process is stored in the EEPROM 30. Private key data used in digital signature generation and decryption processing is read from the EEPROM 30 and supplied to the encryption processing unit 20.
In addition, random numbers used in key data generation processing and digital signature generation processing are generated in the random number generation unit 10 and supplied to the encryption processing unit 20.
[0054]
When a random number generation command is given from the CPU 40 to the random number generation unit 10, the random number generation unit 10 executes an initialization operation described below (step ST101).
[0055]
First, the physical random number generation unit 1 is activated and generation of random numbers is started. During the initialization operation, random number correction by the correction unit 2 is not performed, and the random number data S1 generated by the physical random number generation unit 1 is sequentially stored in the FIFO 4 as random number data S2.
In the following description, as an example, it is assumed that the random number data generated in the physical random number generator 1 has a data length of 32 bits. Further, as shown in FIG. 5, the FIFO 4 has 32 blocks of memory each capable of storing 32-bit random number data.
[0056]
When the random number data S2 for 32 blocks is stored in the FIFO 4, the counting unit 3-1 subsequently counts “1” of each digit of the random number data.
That is, the number of “1” bit data present in the bit data of the same digit in the random number data stored in the FIFO 4 is counted for each of the 32 digits. The count result is stored in the count value register 3-2 as an initial value.
[0057]
FIG. 6 is a diagram illustrating the count values A [0] to A [31] of each digit stored in the count value register 3-2. In the example of FIG. 6, the bit width of the count value stored in the count value register 3-2 is 8 bits.
[0058]
FIG. 8 is a diagram for explaining the counting operation of “1” in the counting unit 3-1. As shown in FIG. 8 (A), the number at which the bit value of the random number data is “1” is counted for each digit of the 32 random number data stored in the FIFO 4. Therefore, the minimum value of the count value is 0 and the maximum value is 32. FIG. 8B illustrates how the count values A [0] to A [31] are stored in the count value register 3-2.
[0059]
When the initial values of the count values A [0] to A [31] of each digit are stored as initial values in the count value register 3-2, these count values are then predetermined by the upper limit comparing unit 3-3. Compared to the upper threshold of. As a result of this comparison, when a digit whose count value exceeds the upper threshold is detected, AND mask data for correcting the bit value of that digit to “0” is generated. The generated AND mask data is stored in the AND mask register 3-5 as an initial value.
Further, the count value of the count value register 3-2 is compared with a predetermined lower limit threshold value in the lower limit comparison unit 3-4. As a result of this comparison, when a digit whose count value falls below the lower threshold is detected, OR mask data for correcting the bit value of that digit to “1” is generated. The generated OR mask data is stored in the OR mask register 3-6 as an initial value.
[0060]
FIG. 7 is a diagram showing AND mask data stored in the AND mask register 3-5 and OR mask data stored in the OR mask register 3-6. As shown in the example of FIG. 7, the AND mask data and the OR mask data have the same 32-bit data length as the random number data S1.
[0061]
FIG. 9 is a diagram illustrating an example of the count values A [0] to A [31] of each digit stored in the count value register 3-2. In the figure, the vertical axis represents the count value, and the horizontal axis represents the digit number corresponding to each of the 32 digits.
For example, if the upper limit threshold value TH is 17, in the example of FIG. 9, the digit of digit number 6 (the seventh digit counted from the least significant digit) exceeds the upper limit threshold value TH. In this case, assuming that there is no other digit exceeding the upper limit threshold TH, the AND mask data generated in the upper limit comparison unit 3-3 is' 1 ... 10111111 'in binary number and' FFFFFFBF in hexadecimal number. The data becomes'.
If the lower limit threshold value TL is 15, the digit number 8 (the ninth digit counted from the least significant digit) is lower than the lower limit threshold value TL in the example of FIG. In this case, assuming that there are no other digits below the lower limit threshold TL, the OR mask data generated in the lower limit comparison unit 3-4 is '0 ... 01000000000000 in binary number and' 00000100 in hexadecimal number. The data becomes'.
[0062]
When initial values are set in the count value register 3-2, the AND mask register 3-5, and the OR mask register 3-6 by the initialization operation as described above, the physical random number generator 1 then selects random number data. S1 is generated and input to the correction unit 2 (step ST102).
[0063]
In the AND operation unit 2-1 of the correction unit 2, the logical product in bit units of the random number data S 1 generated in the physical random number generation unit 1 and the AND mask data stored in the AND mask register 3-5 is calculated. (Step ST103).
In addition, the OR operation unit 2-2 of the correction unit 2 performs a bitwise OR operation between the random number data corrected by the AND operation unit 2-1 and the OR mask data stored in the OR mask register 3-6. Is calculated (step ST104).
[0064]
For example, as shown in FIG. 10A, the AND mask data stored in the AND mask register 3-5 has a hexadecimal value “FFFFFFBF” and is stored in the OR mask register 3-6. It is assumed that the mask data has a value of “00000100” in hexadecimal.
In this state, when the random number data S1 having a value of '3878B6C0' is output from the physical random number generator 1 in hexadecimal, the seventh digit from the least significant digit is obtained by the logical product of the random number data S1 and the AND mask data. Is set to “0”, and the bit data of the ninth digit from the least significant digit is set to “1”. As a result, the random number data S1 of “3878B6C0” is corrected to the random number data S2 of “3878B780”.
[0065]
In this way, the random number data S2 corrected by the correction unit 2 is output to the external bus BS via the interface unit 5 (step ST105).
[0066]
Further, the random number data S2 corrected by the correction unit 2 is newly stored in the FIFO 4 in place of the random number data stored first in the FIFO 4 (step ST106).
[0067]
When the corrected random number data is stored in the FIFO 4 and the contents of the FIFO 4 are updated, the count value of “1” in the counting unit 3-1 is also updated accordingly, and the updated count value is updated. Is newly stored in the count value register 3-2 (step ST107).
[0068]
When the count value of the count value register 3-2 is updated, the upper limit comparison unit 3-3 performs a new comparison between the updated count value and the upper limit threshold value. As a result, the AND mask register The value of the AND mask data stored in 3-5 is updated (step ST108). In addition, the lower limit comparison unit 3-4 performs a new comparison between the updated count value and the lower limit threshold value, and as a result, the value of the OR mask data stored in the OR mask register 3-6. Is updated (step ST109).
[0069]
Next, in step ST110, it is determined whether or not to end generation of random numbers based on an instruction from the CPU 40. If further generation of random numbers is to be performed, the process returns to step ST102 again, and the random number data S1 described above is returned. And the update of the data stored in each register (3-2, 3-5, 3-6) are repeated. If the end of random number generation is determined, generation of random numbers in the physical random number generation unit 1, generation of correction information in the correction information generation unit 3, and storage operation of the random number data S2 in the FIFO are stopped (step ST111). The random number generation operation ends.
[0070]
FIG. 11 is a diagram illustrating an example of a result of examining the number of “1” included in the 20000-bit random number generated by the random number generation unit 10 described above a plurality of times. The value on the vertical axis in the figure indicates the number of “1” in 20000 bits, and the value on the horizontal axis indicates the number of each test.
As shown in the example of FIG. 11, the probability that “1” appears in the random number generated by the random number generation unit 10 described above is approximately 50%, and the analog random number generator as shown in the example of FIG. 17 is used as it is. Compared with, the bias of the bit value appearing in the random number is reduced.
[0071]
As described above, according to the random number generation unit 10 shown in FIG. 2, the random number data S1 of the physical random number generation unit 1 is corrected based on the correction information S3, and a predetermined bit value ( For example, new correction information S3 is generated according to the frequency of appearance of bit data having “1”). Therefore, it is possible to control the frequency at which the predetermined bit value appears in the random number data S2 corrected by the correction unit 2, and thereby it is possible to reduce the bias of the bit value appearing in the generated random number. Become.
[0072]
In addition, since the random number data S1 is generated based on the irregularity of the physical phenomenon in the physical random number generation unit 1, it is possible to generate a more secure random number without periodicity like a pseudo random number. .
[0073]
In addition to the physical random number generator 1, the random number generator 10 shown in the examples of FIGS. 2 and 3 includes a FIFO 4 that stores a predetermined number of corrected random number data, and a predetermined number stored in the FIFO 4. A counter 3-1 for counting the number of bit data having a predetermined bit value in the random number data and a correction based on a comparison result between the counted value and a predetermined upper threshold and lower threshold It has an upper limit comparison unit 3-3 and a lower limit comparison unit 3-4 that generate information S3, and units (2-1, 2-3) that perform a logical operation on the generated correction information S3 and random number data S1. However, these configurations are clearly simpler than the case where pseudorandom numbers are generated using a conventional cryptographic operation circuit such as the DES method or the SHA-1 method, and the case where such a conventional circuit is used. The circuit scale is significantly reduced compared to Rukoto can.
[0074]
Therefore, according to the cryptographic processing apparatus 100 shown in FIG. 1, it is possible to execute highly secure cryptographic processing using random numbers having no bias or periodicity, and when using a conventional advanced pseudo-random number generation method. In comparison, the circuit configuration can be simplified.
[0075]
<Second Embodiment>
FIG. 12 is a diagram illustrating an example of the configuration of the random number generation unit 10A according to the second embodiment of the present invention.
[0076]
In the second embodiment, some of the functions of the random number generation unit are realized by a processing device such as a computer that executes processing based on a program.
For example, the correction unit 2 and the correction information generation unit 3 in the random number generation unit 10 illustrated in FIG. 2 are replaced with the processing unit 6 and the program memory 7 in the random number generation unit 10A illustrated in FIG.
[0077]
Based on the program stored in the program memory 7, the processing unit 6 executes a process related to random number generation as shown in the flowchart shown in FIG.
That is, an initial value of the correction information S3 is generated in the initialization operation (step ST101), and the random number data S1 generated in the physical random number generator 1 is corrected based on the initial value (steps ST103 and ST104). Then, the corrected random number data S2 is output from the interface unit 5 to the bus BS (step ST105) and stored in the FIFO 4 (step ST106). Next, as the frequency of appearance of bit data having a predetermined bit value in the corrected random number data S2, for example, there is bit data having a bit value of '1' in a series of predetermined number of random data stored in the FIFO 4 The number to be updated is newly counted (step ST107), and the correction information S3 is updated according to the counted value (steps ST108 and ST109). In response to a command from the CPU 40, the correction of the random number data S1 and the update of the correction information S3 similar to those described above are further repeated to generate the random number data S2.
[0078]
Also in the random number generation unit 10A described above, random numbers having no bias or periodicity can be generated as in the random number generation unit 10 illustrated in FIG. In addition, the processing procedure is clearly simpler than that of a pseudorandom number generation method using a cryptographic algorithm such as the DES method or the SHA-1 method, the amount of program code can be reduced, and the processing speed can be increased. it can.
[0079]
<Third Embodiment>
FIG. 13 is a block diagram showing an example of the configuration of a hardware token according to the third embodiment of the present invention.
[0080]
A hardware token is information that proves the owner's identity, and securely stores information that should be kept secret from others (such as a private key in public key cryptography). It is a device having portability. In this embodiment, the random number generation device of the present invention is applied to such a hardware token.
[0081]
The hardware token 101 shown in FIG. 13 includes a random number generation unit 10 that is an embodiment of a random number generation device, an RSA arithmetic unit 21 and an SHA arithmetic unit 22 that are embodiments of cryptographic processing means, an EEPROM 30, a CPU 40, The RAM 50, the ROM 60, the ECC unit 70, and the serial interface unit 80 are included. 1 and FIG. 13 indicate the same components.
[0082]
The RSA computing unit 21 performs computations related to RSA encryption processing in accordance with a control signal from the CPU 40 input via the bus BS.
For example, a key generation process for generating a public / private key pair, an encryption process for encrypting plaintext using the public key, and a decryption process for decrypting the ciphertext using the private key are performed.
[0083]
The SHA calculator 22 calculates a SHA hash value for given plain text in accordance with a control signal from the CPU 40 input via the bus BS.
[0084]
The ECC unit 70 performs error detection and correction processing on a signal transmitted from the computer 200 via the serial interface unit 80. In addition, a predetermined error correction encoding process is performed on a signal transmitted to the computer 200 via the serial interface unit 80.
[0085]
The serial interface unit 80 exchanges signals with the computer 200 by a serial communication method such as a USB (universal serial bus) method or a UART (universal asynchronous receiver-transceiver) method.
[0086]
Next, the operation of the hardware token 101 having the above-described configuration shown in FIG. 13 will be described.
[0087]
When software installed in the computer 200 is activated and processing related to user authentication is executed on the software, various instructions corresponding to the software are input from the computer 200 to the hardware token 101. In the hardware token 101, based on a program stored in the ROM 60, encryption processing according to an instruction from the computer 200, for example, RSA key pair generation processing, ECDSA (elliptic curve digital signature algorithm) method, or the like. A digital signature generation / verification process is executed.
[0088]
FIG. 14 is a flowchart illustrating an example of RSA key pair generation processing.
[0089]
First, the random number generator 10 generates a random number P (step STST201) and supplies it to the RSA calculator 21. The RSA computing unit 21 determines whether or not the supplied random number P is a prime number (step ST202). If it is not a prime number, the process returns to step ST201, and generation of the random number P and prime number determination are performed again.
If it is determined that the random number P is a prime number, the random number generator 10 further generates a random number Q (step STST203), and the RSA calculator 21 determines whether the random number Q is a prime number. It is executed (step ST204). If it is not a prime number, the process returns to step ST203 to generate a random number Q and determine a prime number again.
[0090]
When the prime numbers P and Q are obtained from the random numbers generated by the random number generation unit 10, the RSA calculator 21 calculates the public key N shown in the following equation based on the prime numbers P and Q (step ST205).
[0091]
[Expression 1]
N = P × Q (1)
[0092]
As the secret key d, a number that satisfies the following equation is calculated between a predetermined number e (for example, 4097) and prime numbers P and Q (step ST206).
[0093]
[Expression 2]
(D × e) mod (P−1) × (Q−1) = 1 (2)
[0094]
The public key N and the secret key d calculated in this way are stored in the EEPROM 30.
[0095]
FIG. 15 is a flowchart illustrating an example of an ECDSA digital signature generation process.
[0096]
First, the random number generation unit 10 generates a random number u (step ST301), and a signature c shown in the following equation is generated based on the generated random number u.
[0097]
[Equation 3]
c = (u · G) _x mod r (3)
[0098]
However, the symbol “G” in Equation (3) indicates the base point coordinates of the elliptic curve, and the symbol “r” indicates the order of the elliptic curve. Also, the symbol '() _x 'Indicates the x coordinate of the point on the elliptic curve obtained by the calculation in parentheses.
[0099]
Then, the SHA calculator 22 calculates the SHA-1 hash value f for the plaintext m to be signed (step ST303). Based on the calculated hash value f, the signature c, the random number u, and the signer's private key s, the signature d is calculated by the following equation (step ST304).
[0100]
[Expression 4]
d = c ^-1 (F + sc) mod r (4)
[0101]
The signatures c and d generated in this way are transmitted to the computer 200 together with the plaintext m.
[0102]
FIG. 16 is a flowchart illustrating an example of an ECDSA digital signature verification process.
[0103]
In the digital signature verification process, a plain text m and its signatures c and d are input from the computer 200. The signer's public key coordinates W are also input from the computer 200.
The input plaintext m is supplied to the SHA calculator 22 and its hash value f is calculated (step ST401). Next, based on the calculated hash value f, signatures c and d, and public key coordinates W, a signature verification value v shown in the following equation is calculated.
[0104]
[Equation 5]
v = ((d ^-1 f) G + (cd ^-1 ) ・ W) _x mod r (5)
[0105]
The calculated signature verification value v is transmitted to the computer 200. In the software of the computer 200, whether or not the signatures d and c are from the signer of the public key coordinates W is determined according to whether or not the signature verification value v matches the signature d.
[0106]
As described above, according to the hardware token 101 shown in FIG. 13, the random number generation unit 10 generates random values with less bias and periodicity, and generates key data generation processing and digital signatures. Since cryptographic processing such as generation processing is executed, personal authentication with higher security becomes possible. Further, by using the random number generator 10 having a simple configuration, it is possible to reduce the size of the apparatus and reduce the power consumption.
[0107]
In addition, this invention is not limited to embodiment mentioned above.
For example, the correction information generation unit 3 in FIG. 2 or the processing unit 6 in FIG. 12 may change the upper threshold value and the lower threshold value according to a control signal input from the CPU 40 or the like. This makes it possible to arbitrarily control the occurrence probability of “1” and “0” in the random number.
[0108]
Further, in the above-described embodiment, the start and stop of the random number generation operation in the random number generation unit is controlled according to the command from the CPU 40, but the random number generation operation is always activated regardless of the command from the CPU 40. It may be in a state. Thereby, since the state of FIFO4 and the state of each register (3-2, 3-5, 3-6) are constantly updated, it is possible to generate a random number that is more difficult to predict.
[0109]
In the above-described embodiment, the number of “1” included in the predetermined number of random number data stored in the FIFO 4 is counted for each digit, and correction information S3 for each digit is generated according to the counting result of each digit. However, the present invention is not limited to this example.
For example, the number of '1's in all the bit data of the random number data stored in the FIFO 4 is counted, and the random number data S2 output from the physical random number generation unit 1 is calculated based on the comparison result between the counted value and the threshold value. You may correct | amend 1 bit at a time.
In this case, the number of “1” bit data stored in the FIFO 4 can be calculated according to, for example, the value of the bit data input to the FIFO 4 and the value of the bit data discarded along with the input. . That is, by providing a counter that increments when bit data “1” is stored in FIFO 4 and decrements when bit data “1” is discarded from FIFO 4, the count value is included in FIFO 4. The number of bit data of “1” can be obtained.
[0110]
In the above-described embodiment, among the random number data corrected by the correction unit 2, random number data before being stored in the FIFO 4 is output via the interface unit 5, but the random number data already stored in the FIFO 4 is output. May be configured to output.
[0111]
【The invention's effect】
According to the random number generation device of the present invention, it is possible to generate a random number with a small bit value deviation and periodicity with a simple configuration.
Further, according to the program of the present invention, it is possible to cause a computer to execute a process related to generation of random numbers with little bias in bit values and periodicity in a simpler procedure.
Further, according to the cryptographic processing apparatus of the present invention, it is possible to execute highly secure cryptographic processing using random numbers having no bias or periodicity, although it has a simple configuration.
[Brief description of the drawings]
FIG. 1 is a block diagram showing an example of the configuration of a cryptographic processing apparatus according to a first embodiment of the present invention.
FIG. 2 is a block diagram showing an example of a configuration of a random number generation unit according to the first embodiment of the present invention.
3 is a block diagram illustrating an example of a configuration of a correction unit and a correction information generation unit illustrated in FIG.
FIG. 4 is a flowchart showing an example of processing of a random number generation unit according to the first embodiment of the present invention.
FIG. 5 is a diagram illustrating an example of a FIFO memory configuration;
FIG. 6 is a diagram illustrating a count value of each digit stored in a count value register.
FIG. 7 is a diagram illustrating an example of mask data stored in an AND mask register and an OR mask register.
FIG. 8 is a diagram for explaining a counting operation of “1” in a counting unit;
FIG. 9 is a diagram illustrating an example of a count value of each digit stored in a count value register.
FIG. 10 is a diagram illustrating a specific example of random number data correction processing in a correction unit.
11 is a diagram illustrating an example of a result of examining the number of “1” included in a 20000-bit random number generated by the random number generation unit illustrated in FIG. 2 a plurality of times.
FIG. 12 is a diagram illustrating an example of a configuration of a random number generation unit according to the second embodiment of the present invention.
FIG. 13 is a block diagram showing an example of the configuration of a hardware token according to the third embodiment of the present invention.
FIG. 14 is a flowchart showing an example of RSA key pair generation processing in the hardware token shown in FIG. 13;
15 is a flowchart showing an example of an ECDSA digital signature generation process for the hardware token shown in FIG. 13;
16 is a flowchart showing an example of an ECDSA digital signature verification process in the hardware token shown in FIG. 13;
FIG. 17 is a diagram illustrating a result of examining the number of “1” included in a 20000-bit random number generated by an analog random number generator a plurality of times.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 1 ... Physical random number generation part, 2 ... Correction part, 2-1 ... AND operation part, 2-2 ... OR operation part, 3 ... Correction information generation part, 3-1 ... Count part, 3-2 ... Count value register, 3-3 ... Upper limit comparison unit, 3-4 ... Lower limit comparison unit, 3-5 ... AND mask register, 3-6 ... OR mask register, 4 ... FIFO, 5 ... Interface unit, 6 ... Processing unit, 7 ... Program memory, 10, 10A ... random number generation unit, 20 ... cryptographic processing unit, 21 ... RSA computing unit, 22 ... SHA computing unit, 30 ... EEPROM, 40 ... CPU, 50 ... RAM, 60 ... ROM, 70 ... ECC unit, 80 ... Serial interface unit, 100 ... Cryptographic processing device, 101 ... Hardware token, 200 ... Computer

Claims

Random number generation means;
Correction means for correcting random number data generated by the random number generation means based on input correction information;
Correction information generating means for generating the correction information according to the frequency of appearance of bit data having a predetermined bit value in the random number data corrected by the correction means;
Random number generator.

A plurality of data storage means for sequentially storing the random number data corrected in the correction means;
The correction information generation means counts the number of bit data having the predetermined bit value among a plurality of random number data stored in the data storage means, and calculates the count value and a predetermined threshold value. Generating the correction information based on the comparison result;
The random number generation device according to claim 1.

The correction information generating means counts, for each digit, the number of bit data having the predetermined bit value in bit data of the same digit in a plurality of random number data stored in the data storage means. Based on the comparison result between the count value and the predetermined threshold value, the correction information corresponding to each digit is generated,
The correction unit corrects the bit data of each digit of the random number data generated by the random number generation unit based on the correction information of each digit generated by the correction information generation unit.
The random number generation device according to claim 2.

The correction information generating means changes the threshold value according to an input control signal.
The random number generation device according to claim 2.

The random number generation means generates a random number based on the irregularity of a physical phenomenon.
The random number generation device according to claim 1.

A first step of correcting the random number data generated in the random number generation means based on the given correction information;
A second step of newly generating the correction information according to the frequency of occurrence of bit data having a predetermined bit value in the random number data corrected in the first step;
A random number generation method comprising:

A first step of correcting the random number data generated in the random number generation means based on the given correction information;
A second step of newly generating the correction information according to the frequency of appearance of bit data having a predetermined bit value in the random number data corrected in the first step;
A program for causing a computer to execute a process having

The second step counts the number of bit data having the predetermined bit value in a series of the predetermined number of random data corrected in the first step, and the count value and the predetermined value are counted. Based on the comparison result with the threshold value, the correction information is newly generated.
The program according to claim 7.

The second step counts, for each digit, the number of bit data having the predetermined bit value in the bit data of the same digit in the series of predetermined number of random number data corrected in the first step. Then, based on the comparison result between the count value of each digit and a predetermined threshold, new correction information corresponding to each digit is generated,
The first step corrects the bit data of each digit of the random number data generated by the random number generation means based on the correction information of each digit generated in the second step.
The program according to claim 8.

Random number generation means;
Correction means for correcting random number data generated by the random number generation means based on input correction information;
Correction information generating means for generating the correction information according to the frequency of appearance of bit data having a predetermined bit value in the random number data corrected by the correction means;
Encryption processing means for executing predetermined encryption processing in accordance with the random number data corrected by the correction means;
A cryptographic processing apparatus.

A plurality of data storage means for sequentially storing the random number data corrected in the correction means;
The correction information generation means counts the number of bit data having the predetermined bit value among a plurality of random number data stored in the data storage means, and calculates the count value and a predetermined threshold value. Generating the correction information based on the comparison result;
The cryptographic processing apparatus according to claim 10.

The data storage means can store only random number data corrected by the correction means, and can read stored data only from the correction information generation means.
The cryptographic processing apparatus according to claim 11.