(57)【要約】一方向関数に適用される少なくとも２つの反復ステップを含む反復処理により疑似乱数を生成する方法であって、スタート値と鍵とに基づく一方向関数によって疑似乱数の一部を生成し、反復処理をランダムなスタート値とランダムな鍵とで初期化し、かつ各反復ステップでは、ある反復ステップに対するスタート値と鍵との双方を、前の反復ステップにて一方向関数を用いて決定した疑似乱数の一部から決定する。
2009512930.tif 000002
【特許請求の範囲】
【請求項１】
一方向関数に適用される少なくとも２つの反復ステップを含む反復処理により疑似乱数を生成する方法であって、スタート値と鍵とに基づく前記一方向関数によって疑似乱数の一部を生成し、前記反復処理をランダムなスタート値とランダムな鍵とで初期化する、疑似乱数の生成方法において、各反復ステップでは、ある反復ステップに対するスタート値と鍵との双方を、前の反復ステップにて一方向関数を用いて決定した疑似乱数の一部から決定することを特徴とする疑似乱数の生成方法。
【請求項２】
それぞれの前の反復ステップにて一方向関数を用いて決定した疑似乱数の一部を２つの部分に分け、一方の部分は、ある反復ステップに対するスタート値と鍵との双方を決定するのに用い、他方の部分は、前の反復ステップの疑似乱数の一部とすること特徴とする、請求項１に記載の方法。
【請求項３】
前記疑似乱数の生成が、
−  ランダムなスタート値とランダムな鍵とを規定する第１ステップと、
−  あるスタート値と鍵とに基づく一方向関数を用いて疑似乱数の一部を決定する第２ステップであって、第１の反復ステップでは、スタート値を第１ステップのランダムなスタート値に対応させ、かつ鍵を第１ステップからのランダムな鍵に対応させる第２ステップと、
−  第２ステップで決定した疑似乱数の一部を、２つの部分に分ける第３ステップと、
−  第３ステップで決定した２つの部分の一方から、新規のスタート値と新規の鍵との双方を決定し、第３ステップで決定した２つの部分のもう一方を疑似乱数の一部とする第４ステップと、
−  予定した繰り返し回数に達するまで、第２ステップから第４ステップまでを繰り返すステップと、
を含むことを特徴とする、請求項２に記載の方法。
【請求項４】
前記第４ステップでは、第３ステップで決定した２つの部分の一方を２つのサブ部分に分け、前記新規のスタート値を第１のサブ部分とし、前記新規の鍵を第２のサブ部分とすることを特徴とする、請求項３に記載の方法。
【請求項５】
前記新規のスタート値を前記第２のサブ部分とし、前記新規の鍵を前記第１のサブ部分とすることを特徴とする、請求項４に記載の方法。
【請求項６】
各場合に、前記決定したサブ部分のランダムに選択した部分のみを用いて前記鍵およびスタート値を決定することを特徴とする、請求項５に記載の方法。
【請求項７】
前記第４ステップでは、前記第３ステップで決定した２つの部分のうちの、他方のランダムに選択した部分のみを、前記疑似乱数の一部とすることを特徴とする、請求項６に記載の方法。
【請求項８】
多数のステップで合成疑似乱数を生成する方法において、まず、１つのステップにて請求項１〜７のいずれか１項に記載の疑似乱数の生成方法を実行し、かつ各ステップを、新規のランダムなスタート値と新規のランダムな鍵とで初期化する、合成疑似乱数の生成方法。
【請求項９】
コンピュータにロードされると、請求項１〜８のいずれか１項に記載の方法を実行するプログラムコードを含むデータ担体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一方向関数を反復適用することにより疑似乱数を生成する方法であって、スタート値と鍵とに基づく一方向関数によって疑似乱数を生成し、かつ反復処理がランダムなスタート値とランダムな鍵とで開始する、疑似乱数の生成方法、および対応するプログラムコードを含むデータ担体にも関する。
【背景技術】
【０００２】
疑似乱数を生成するための既知の概念は、セキュアな一方向関数ｆ（ｋ，ｓ）を用いる疑似乱数生成器から成っており、ここに、ｋは暗号鍵であり、ｓはランダムに選択したスタート値である。このような鍵ｋは、予定した分布に従って選択され、疑似乱数生成器による疑似乱数の生成中に用いられる。鍵ｋは、全生成過程の期間中同じままである。ひとたびスタート値ｓを選択すれば、以下の規則に従って、疑似乱数ｘｉは反復的に生成される。
ｘ１＝ｆ（ｋ，ｓ）
ｘｉ＝ｆ（ｋ，ｘｉ−１）  ここでｉ＞１とする。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
通常、このようにして生成される疑似乱数の長さは限られたものとなる。ひとたび予定した限界長さに達すると、スタート値ｓを再選択して、疑似乱数生成器を再初期化する。鍵ｋは、そのまま同じとする。
【０００４】
このように実施する欠点のひとつは、暗号鍵ｋを知る攻撃者が、次の初期化に対する最後の初期化から全ての乱数を算出できるということにある。したがって、このような特性は、この種類の疑似乱数生成器をかなり抑制することになる。
【０００５】
さらに、ＷＯ２００５／０２９３１５Ａ１から、疑似乱数生成器の初期化の際に、新規のスタート値ｓに加えて新規の暗号鍵ｋを用いることも既知である。さらに、個々の疑似乱数を算出する際には、この暗号鍵ｋを、毎回スタート値ｓから算出し直す。この方法の欠点は、各場合における次のスタート値ｓ＋１を、乱数の計算中に、途中で不揮発性メモリに格納することにある。したがって、攻撃者は、例えば、どうにかして不揮発性メモリからそれぞれの次のスタート値ｓ＋１を読み取れば、疑似乱数生成器の内部状態を権限のない者に洩らしたり、それを操作したりすることさえできる。
【０００６】
本発明の目的は、上述した欠点を少なくとも部分的に回避する、疑似乱数の生成方法を提供することにある。
【課題を解決するための手段】
【０００７】
この目的は、請求項１に記載の方法によって、そして請求項９に記載のデータ担体によって達成される。更に好適に発展させたものは、従属請求項に記載した通りのものである。
【０００８】
本発明は、一方向関数に適用される少なくとも２つの反復ステップを含む反復処理により疑似乱数を生成する方法であって、スタート値と鍵とに基づく一方向関数によって疑似乱数の一部を生成し、反復処理をランダムなスタート値とランダムな鍵とで初期化し、かつ各反復ステップでは、ある反復ステップに対するスタート値と鍵との双方を、前の反復ステップにて一方向関数を用いて決定した疑似乱数の一部から決定する疑似乱数の生成方法を提供する。
【０００９】
反復ステップに必要なスタート値および鍵は、前の反復ステップの疑似乱数の一部から直に生成するのであって、スタート値および鍵を途中で格納することはない。したがって、これらの値を、攻撃者が読み出したり改変したりすることはできない。
【００１０】
他の実施例では、それぞれの前の反復ステップにて一方向関数を用いて決定した疑似乱数の一部を２つの部分に分け、一方の部分は、ある反復ステップに対するスタート値と鍵との双方を決定するのに用い、もう一方の部分は、前の反復ステップの疑似乱数の一部とする。
【００１１】
疑似乱数を生成する方法は、
−  ランダムなスタート値とランダムな鍵とを規定する第１ステップと、
−  あるスタート値と鍵とに基づく一方向関数を用いて疑似乱数の一部を決定する第２ステップであって、第１の反復ステップでは、スタート値を第１ステップのランダムなスタート値に対応させ、かつ鍵を第１ステップからのランダムな鍵に対応させる第２ステップと、
−  第２ステップで決定した疑似乱数の一部を、２つの部分に分ける第３ステップと、
−  第３ステップで決定した２つの部分の一方から、新規のスタート値と新規の鍵との双方を決定し、第３ステップで決定した２つの部分のもう一方を疑似乱数の一部とする第４ステップと、
−  予定した繰り返し回数に達するまで、第２ステップから第４ステップまでを繰り返すステップとを含む。
【００１２】
第４ステップでは、第３ステップで決定した２つの部分の一方を２つのサブ部分に分け、新規のスタート値を第１のサブ部分とし、新規の鍵を第２のサブ部分とする。新規のスタート値を第２のサブ部分とし、新規の鍵を第１のサブ部分とすることもできる。
【００１３】
他の実施例では、各場合に、決定したサブ部分のランダムに選択した部分のみを用いて鍵およびスタート値を決定する。
【００１４】
これは、決定したサブ部分の選択した部分が各反復ステップと共に変化するため、有利である。もはや、鍵およびスタート値から、ランダムに選択された部分を逆算することはできない。
【００１５】
第４ステップでは、第３ステップで決定した２つの部分のうちの、他方のランダムに選択した部分のみを、疑似乱数の一部とする。この場合も、疑似乱数の一部から、ランダムに選択された部分を逆算することはできない。
【００１６】
多数のステップで合成疑似乱数を生成する方法において、１つのステップにて疑似乱数の生成方法を実行し、かつ各ステップを、新規のランダムなスタート値と新規のランダムな鍵とで初期化する疑似乱数の生成方法も提供する。
【００１７】
ひとたび予め規定した制限に達すると、疑似乱数を生成する方法を反復して適用することにより、疑似乱数の生成を延長することができる。
【００１８】
本発明の方法による疑似乱数を生成するコンピュータプログラムを含むデータ担体も提供する。
【００１９】
このように、本発明は、各乱数を決定した後に、次の反復ステップに対する一方向関数のスタート値および鍵を初期化し直し、スタート値および鍵を、それぞれ前に決定した乱数から直に決定する、疑似乱数の反復生成方法を提供する。スタート値および鍵は、どの時点でも途中で格納することはないため、そして、乱数の決定はそれぞれ前もって決定した乱数のランダムな要素から決定するため、攻撃者がスタート値または鍵を読み取ったり操作したり、あるいは２つの連続する乱数の対から一方向関数を解析して、その解析結果から鍵を決定したりすることはできない。
【００２０】
このように、本発明は、攻撃者が疑似乱数生成器の情報を漏洩させて、これにより、すでに生成したか、または生成しようとする乱数を取得することを極めて困難にする、疑似乱数生成器による疑似乱数の生成方法を提供する。
【００２１】
以下、図面に示す実施例を参照して本発明をさらに説明するが、本発明は、これに限定されるものではない。
【発明を実施するための最良の形態】
【００２２】
疑似乱数生成器は、予定数の乱数を生成する。疑似乱数生成器は、スタート値ｓ０と鍵ｋ０とで初期化される。以下、鍵ｋは暗号鍵とする。
【００２３】
疑似乱数生成器は、所定数の実行後に、その出力値が周期的になるという特性がある。これは、ある期間の終わりに達した後に、以前と同じ乱数が再び生成されることを意味する。これを回避するために、本発明による疑似乱数生成器は、新規の鍵ｋと新規のスタート値ｓとの双方で初期化する。鍵ｋおよびスタート値ｓは、この場合、ランダムに選択する。
【００２４】
図１は、本発明による方法の概観を示す。疑似乱数生成器は、一方向関数ｆを反復的に適用することによって、一組の乱数を生成する。一方向関数ｆとしては、例えば３ＤＥＳ（トリプルＤＥＳ−Data Encryption Standard）もしくはＡＥＳ（Advanced Encryption Standard）のような対称的な一方向関数か、例えばＲＳＡ関数（Rivest, Shamir, Adlemanによる）または有限群の離散対数のような非対称的な一方向関数のいずれかを用いることができる。一方向関数ｆは、スタート値ｓおよび鍵ｋにも適用される。
【００２５】
反復処理は、多数の反復ステップを含む。図１において、ステップ１０、２０および３０は第１の反復ステップを成し、また、ステップ４０、５０および６０は第２の反復ステップを成す。疑似乱数生成器は、必要に応じて、各場合において、多数の反復ステップから成る多数回の反復処理を行う。１回の反復処理内にて、各反復ステップは、同様にスタート値ｓと鍵ｋとで初期化する。それぞれの反復処理の第１の反復ステップの期間中、当該反復ステップのスタート値ｓは疑似乱数生成器のスタート値ｓ０に対応し、当該反復ステップの鍵ｋは疑似乱数生成器の鍵ｋ０に対応する。以下、反復処理の第１のスタート値および第１の鍵を、ｓ０およびｋ０と記す。
【００２６】
第１の反復ステップ１０では、疑似乱数生成器が、スタート値ｓ０を受け取る。それから、鍵ｋ０を算出する。他の実施例では、疑似乱数生成器が第１の反復ステップ１０で鍵ｋ０も受け取るようにする。次の反復ステップ２０では、スタート値ｓ０および鍵ｋ０に一方向関数ｆを適用する。この場合の関数ｆ（ｋ０，ｓ０）の結果を、反復ステップ３０にて利用できる。このステップ３０での３つの値（ｓ１，ｋ１，ｒ１）は、最初に生成された乱数を示す。この乱数を、２つの部分ｔ１とｒ１とに分ける。第２の反復ステップ４０〜６０に対するスタート値ｓ１および鍵ｋ１は、ｔ１から決定する。要素ｒ1は、当該反復処理による疑似乱数の第１の部分とする。
【００２７】
それぞれの次の反復ステップに対するスタート値ｓｉおよび鍵ｋｉは、以下のように決定する。
【００２８】
それぞれの次の反復ステップのために必要な値ｓｉおよびｋｉは、それぞれの現在の反復ステップiの乱数の一部分ｔｉから決定する。この部分ｔｉを２つのサブ部分に分け、スタート値ｓｉはｔｉの第１の部分とし、鍵ｋｉはｔｉの第２の部分とする。ｓｉをｔｉの第２の部分とし、鍵ｋｉをｔｉの第１の部分とすることもできる。乱数の残りの部分ｒｉは、当該反復処理の疑似乱数の一部を成す。
【００２９】
特に好適な実施例では、乱数の一部分ｔｉを２つのサブ部分に分割し、各場合において、そのランダムに選択した部分だけを、次の反復ステップに対するスタート値ｓｉおよび鍵ｋｉとして用いる。その場合、ｒｉの部分だけを、当該反復処理の疑似乱数全体の一部として用いるのが好適である。この実施例の利点は、攻撃者が一方向関数ｆを分析して、その分析から鍵ｋを決定することを可能にするような乱数のいかなる対（ｒｉ−１，ｒｉ）を疑似乱数生成器が生成しないことにある。
【００３０】
図１の第２の反復ステップでは、ステップ４０でスタート値ｓ１を、ステップ５０で鍵ｋ１を用いて、これらから、第２の乱数（ｓ２，ｋ２，ｒ２）を算出する。この乱数も、上述したように、２つの部分に分け、その一方の部分から、次の反復ステップ（図示せず）に対する鍵およびスタート値を決定し、他の部分から、当該反復処理による疑似乱数の他の部分を決定する。
【００３１】
ひとたび反復処理が予定限度回数に達すると、反復処理はステップ１０でのスタートから再び開始し、ここでは新規なランダムのスタート値ｓ０と新規なランダムの鍵ｋ０とを用いる。このようにして、合成疑似乱数が生成される。
【００３２】
図２は、２つの反復ステップに基づく、本発明による方法を示す。第１の反復ステップはステップ１０１で開始し、このステップでは、疑似乱数生成器を鍵ｋ０とスタート値ｓ０とで初期化する。次に、ステップ１０２にて、一方向関数ｆに基づいて乱数（ｋ１，ｓ１，ｒ１）を決定する。要素ｒ１（例えば３２５６）は、第１の反復ステップの出力１０４を成す。要素（ｋ１，ｓ１）は、第２の反復ステップに対する入力１０３を成す。第１の反復ステップと同様に、第２の反復ステップは初期化ステップ１０５で開始する。しかしながら、この場合における値ｋ１およびｓ１は、第１の反復ステップの乱数決定結果１０２から決定する。それから、ステップ１０６にて、一方向関数ｆに基づいて乱数（ｋ２，ｓ２，ｒ２）を決定する。要素ｒ２（例えば７１５８）は、第２の反復ステップの出力１０８を成す。要素（ｋ２，ｓ２）は、更なる反復ステップに対する入力１０７として作用し得る。２つの反復ステップの後に、要素ｒ１とｒ２から成る生成疑似乱数は、３２５６７１５８と読めるようになる。
【００３３】
図３は、本発明による方法のフローチャートを示す。第１のステップ２０１では、疑似乱数生成器を初期化するために、ランダムなスタート値およびランダムな鍵を決定する。これら２つの値を用いて、次のステップ２０２にて、乱数の一部を決定する。この乱数の一部を、ステップ２０３にて２つの部分に分ける。一方の部分は、次のステップ２０４にて、新規のスタート値および新規の鍵を決定するのに用いる。他の部分は、疑似乱数全体の一部とする。
【００３４】
ステップ２０５では、疑似乱数の長さが予定限界値に達したか否かを確認するチェックを行う。まだ到達していない場合には、ステップ２０２〜２０４を繰り返し、ステップ２０４で決定した新規の値を用いて、ステップ２０２にて乱数の一部を決定する。ひとたび反復周期の終わりに達すると、本方法はステップ２０６に続き、このステップでは、合成疑似乱数が完全に生成されたか否かを確認するチェックを行う。合成疑似乱数がまだ完全に生成されていない場合には、本方法は再びステップ２０１にて開始し、このステップ２０１にて新規のランダムなスタート値および新規のランダムな鍵を決定する。合成疑似乱数が完全に生成された場合に、本方法は終了する。
【００３５】
この場合に、本発明による方法にて得られる疑似乱数は、ステップ２０４にて決定される要素から成る疑似乱数である。
【００３６】
図４は、合成疑似乱数である。この合成疑似乱数は６つの部分３０５から成り、最初の３つの部分は第１の反復処理３０３の３つの反復ステップによって生成され、そして最後の３つの部分は第２の反復処理３０４の３つの反復ステップによって生成されたものである。
【００３７】
第１の反復処理３０３は、ランダム値（ｓｚ１，ｋｚ１）３０１で初期化し、そして第２の反復処理３０４は、ランダム値（ｓｚ２，ｋｚ２）３０２で初期化したものである。ここで、ｓｚｉはランダムなスタート値であり、ｋｚｉは反復処理ｉのランダムな鍵である。
【００３８】
反復ステップＩｉ，ｊ３０５は、各場合において、前の反復ステップＩｉ，ｊ−１から決定した値（ｓｊ−１，ｋｊ−１）３０６で初期化し、ここでＩｉ，ｊは反復処理ｉの反復ステップｊであり、ｊ＞０である。反復処理ｉのそれぞれの第１の反復ステップＩｉ，０は、値（ｓｚｉ，ｋｚｉ）で初期化する。
【図面の簡単な説明】
【００３９】
【図１】本発明による方法の概観を示す図である。
【図２】本発明による２つの反復ステップを用いる方法を示す図である。
【図３】本発明による方法のフローチャートである。
【図４】合成疑似乱数の構成を示す図である。
【符号の説明】
【００４０】
１０，２０，３０  第１の反復ステップ
４０，５０，６０  第２の反復ステップ
１０１  初期化（第１の反復ステップ）
１０２  結果（第１の反復ステップ）
１０３  第２の反復ステップに対する入力（第１の反復ステップ）
１０４  出力（第１の反復ステップ）
１０５  初期化（第２の反復ステップ）
１０６  結果（第２の反復ステップ）
１０７  更なる反復ステップに対する入力（第２の反復ステップ）
１０８  出力（第２の反復ステップ）
２０１  ランダムなスタート値およびランダムな鍵の規定（第１のステップ）
２０２  疑似乱数の決定（第２のステップ）
２０３  疑似乱数の分割（第３のステップ）
２０４  新規のスタート値および新規の鍵の決定（第４のステップ）
２０５，２０６  問合せステップ
３０１，３０２  反復処理のランダムなスタート値およびランダムな鍵
３０３，３０４  反復処理
３０５  反復処理の反復ステップ
３０６  反復ステップのスタート値および鍵
【図１】
2009512930.tif 000003
【図２】
2009512930.tif 000004
【図３】
2009512930.tif 000005
【図４】
2009512930.tif 000006
【国際調査報告】
2009512930.tif 000007
2009512930.tif 000008
2009512930.tif 000009