【課題】乱数生成能力と素数判定能力とを有する情報処理装置において、より効率的に素数を生成する。
【解決手段】入力された数値が素数であるか否かを判定しかつ素数である場合に該数値を出力する複数の判定手段を備える。複数の乱数シードを取得し、１以上の判定手段が所属するそれぞれの判定グループに複数の乱数シードの何れかを対応付ける。乱数シードを用いて生成した乱数を、該乱数シードに対応付けられた判定グループに入力する。ここで、着目乱数シードを用いて、乱数を生成する乱数生成系列を初期化する。乱数生成系列を用いて乱数を生成する。乱数のビット列を所定ビット数のビット列へと分割する。分割によって得られたそれぞれのビット列が示す数値を、着目乱数シードに対応付けられた判定グループを構成する判定手段の何れかへと出力する。 （もっと読む）

【課題】乱数生成能力と素数判定能力とを有する情報処理システムにおいて、並列に行われる素数生成処理を効率化する。
【解決手段】生成ユニットは、乱数を生成し、かつ生成した乱数のビット列の少なくとも一部を、少なくとも１つの判定ユニットに送信する。判定ユニットは、少なくとも１つの生成ユニットから送信されたビット列を組み合わせて所定ビット数の数値を生成し、生成した数値が素数であるか否かを判定し、かつ素数であると判定された数値を出力する。制御手段は、生成ユニットが乱数を生成するのに要する時間と、判定ユニットが数値について素数であるか否かを判定するのに要する時間とが近くなるように、複数の処理ユニットの一部若しくは全部のそれぞれを生成ユニット又は判定ユニットとして動作させる制御を行う。 （もっと読む）

【課題】複数の演算ユニットを用いた並列処理において、より高速に素数を求める。
【解決手段】複数の演算ユニットのうち何れか１つを選択し、選択した演算ユニットに対してメモリに格納されているシードを用いた乱数発生処理の実行を指示する。複数の演算ユニットのそれぞれは、乱数発生処理の実行が指示されると、メモリに格納されているシードを用いて乱数を生成し、メモリに格納されているシードを生成した乱数で更新し、生成した乱数が素数であれば、該生成した乱数を出力する。乱数発生処理の実行を指示した演算ユニットによる更新処理が完了したことを検知すると、演算ユニットとは別の演算ユニット群のうち何れか１つを選択し、選択した演算ユニットに対してメモリに格納されているシードを用いた乱数発生処理の実行を指示する。 （もっと読む）

【課題】暗号プロトコルや公開鍵暗号に係る処理において計算負荷を減少させる。
【解決手段】公開鍵暗号方式において秘密鍵と公開鍵の生成に使用されるｐおよびｑを生成する方法。ｐ，ｑは素数であり、ｐは、素数であるｒか、ｑと同じ若しくはｑより大きな素数の合成数であるｒを用いて、式ｐ＝２ｑｒ＋１により計算されるセキュアー素数である。公開鍵暗号方式に使用するセキュリティパラメータをk，ｑのビット長をＮ，ａを０＜ａ＜２^ｋである奇数としたとき、ｑを、式ｑ＝２^２ｋ−ａもしくは式ｑ＝２^Ｎ−ａ、または、式ｑ＝２^２ｋ＋ａもしくは式ｑ＝２^Ｎ−１＋ａに基づいて生成する。ｐの所望のビット長をＬ，ｂを０＜ｂである奇数としたとき、ｑを、式ｑ＝２^２ｋ−ａもしくは式ｑ＝２^Ｎ−ａにより生成した場合は、ｒを、式ｒ＝２^{Ｌ−２ｋ−１}＋ｂもしくは式ｒ＝２^{Ｌ−Ｎ−１}＋ｂ、または、式ｒ＝２^Ｌ−２ｋ−ｂもしくは式ｒ＝２^Ｌ−Ｎ−ｂにより生成する。 （もっと読む）

【課題】離散対数の計算量と素因数分解の計算量の比を大きくする
【解決手段】本発明のパラメータ設定装置は、条件設定部、素数生成部、整数生成部を備える。条件設定部は、整数Ｎを素因数分解するための計算量が、数体篩法の方が楕円曲線法よりも少なくなるように、整数Ｎのサイズと素因数の数Ｒ（ただし、Ｒは２以上）を決める。素数生成部は、整数Ｎのサイズと素因数の数Ｒから、Ｒ個の素数ｐ_ｒ（ただし、ｒは１からＲの整数）を生成する。整数生成部は、素数ｐ_ｒから整数Ｎを求める。本発明の離散対数計算装置は、整数Ｎ、素数ｐ_１，…，ｐ_Ｒ、要素ｇ、要素ｙを入力として、ｙ＝ｇ^ｘを満たす整数ｘを求める。本発明の離散対数計算装置は、因子基底計算部と群要素計算部とを備える。 （もっと読む）

【課題】情報処理システムは、１以上の暗号化鍵を用いて情報を暗号化、復号化するが、これらの鍵が大きな鍵（例えば一対の２０４８ビットのＲＳＡ鍵）の場合、記憶装置に格納することでシステム当たりのコストを上昇させるため、１以上の固有の暗号化鍵を再生成する機能を提供して、コスト低減する。
【解決手段】格納されている入力値および格納されているカウント値を利用して暗号化鍵を生成する方法であって、プロセッサ１００は、入力値とカウント値とを格納する不揮発性記憶装置１４０と、格納されている入力値と格納されている第１のカウント値とに基づいて、暗号化鍵を生成するロジック１２２とを備え、暗号化鍵を生成する。 （もっと読む）

【課題】本発明は、電子署名を構成する要素の数を少なくし、電子署名長が短く、情報量及び通信量が少なく、また、検証時の計算量の少ない電子署名検証方法及び装置を提供することを目的とする。
【解決手段】本発明の電子署名検証システムは、登録装置と、電子署名装置と、検証装置からなる。電子署名装置は、乱数ｘ及びｙとＧ_１及びＧ_２それぞれの生成元ｇ_１及びｇ_２を用いて、Ｘ＝ｇ_２^ｘ、Ｙ＝ｇ_２^ｙを計算し、公開鍵ｐｋを生成する。ｇ_１、ｇ_２、乱数ｒ_ｉ、ｘ、ｙ及び平文ｍ_ｉを用いて、電子署名σを生成する。検証装置は、公開鍵ｐｋ、電子署名σ及び平文ｍ_ｉを用いて、改竄等が行われていないか検証する。 （もっと読む）

【課題】Waters偽造不可署名と同程度の効率を有する強偽造不可署名方式のスタンダードモデルおよび安全性と効率性とを有する三者間ＳＡＫＡＰのスタンダードモデルを提供する。
【解決手段】電子署名方式が、送信者が自分自身のlong-term private keyを知っているという事実を受信者が送信文書から検証することができるという基本的な属性を含む強偽造不可（定理１）であり、かつ、送信者の認証機能付き鍵合意プロトコルＳＡＫＡＰとして、キー生成、メッセージ生成、ベリフィケーション、キー・アグリーメントの４つのフェーズを有し、そのうち、前３つの各フェーズが、前記電子署名方式により構成され、かつ、如何なる送信者もshort-term secretを漏洩せず（定理２）、かつ、Known Key Security（定理３）、Perfect Forward Secrecy（定理４）、Key Compromise Impersonation Secure（定理５）の属性を満たす仕組みを実現する。 （もっと読む）

【課題】共通部分抽出に必要となる処理の並列化を可能とし、処理全体の効率化を図って処理時間を高速化することを課題とする。
【解決手段】共通アドレス抽出装置１０は、各バイトに対して篩処理一回目のログ加算処理を実施し、一回目のログ加算処理が終了した後の各バイトの値に対して、条件を満足するバイトのアドレスに付属するパリティビットをオンとする。続いて、共通アドレス抽出装置１０は、パリティビットの値を保持した状態のまま、各バイトに対して篩処理二回目のログ加算処理を実施する。そして、共通アドレス抽出装置１０は、二回目の篩処理が終了した後のバイトが保持する値それぞれに対して、条件を満足しないバイトのアドレスに付属するパリティビットをオフとする。その後、共通アドレス抽出装置１０は、対応するパリティビットの値が１であるバイトのアドレスを、条件を満足するメモリアドレスの共通部分として、抽出する。 （もっと読む）

暗号化データを他の電子装置と交換するための携帯電子装置（１０）が、プロセッサ（２２）と、該プロセッサと動作可能に結合されたメモリ（１６）と、該プロセッサ及びメモリと動作可能に結合された素数生成回路（１２ａ）とを含む。素数生成回路は電子装置内の一意の格納済みデータに基づいて少なくとも２つの素数を生成する論理回路を含むと共に、前記少なくとも２つの素数は常に同じ少なくとも２つの素数である。次いで、生成された素数は、電子装置（１０）内においてＲＳＡ公開キーと秘密キーとを生成するために用いることができる。
（もっと読む）

【課題】２のべき乗長以外の素数を確定的な素数判定（生成）手法を用いて効率的に生成すること。
【解決手段】所望の素数Ｐ_nのビット長の指定を受け付け、指定を受け付けた素数Ｐ_nのビット長に従って、素数｛Ｐ₁，…，Ｐ_n-1｝の各ビット長を事前に算出する。そして、算出された素数｛Ｐ₁，…，Ｐ_n-1｝の各ビット長に基づいて、素数Ｐ_i（１≦ｉ≦ｎ−１）と乱数ｒ_iとを利用して、素数Ｐ_iのビット長より長いビット長でかつ素数Ｐ_iより大きな値の素数Ｐ_i+1を順次生成することにより、最終的に所望の素数Ｐ_nを生成することができる。 （もっと読む）

少なくとも２つの係数を有するＲＳＡモジュラスの係数を所定の部分Ｎ_ｈにより生成する方法及び装置。第１素数ｐが生成され、モジュラスＮの一部を構成するＮ_ｈの値が取得され、ｐｑがＮ_ｈを共有するＲＳＡモジュラスとなるように、第２素数ｑがｐ及びＮ_ｈに依存した区間において生成され、モジュラスＮの計算を可能にする情報が出力される。
（もっと読む）

【課題】 各素数候補の試行割算後の本格的素数判定に関し、高速化を図る。
【解決手段】 本格的素数判定に用いられる「ミラー-ラビンテスト」は、１つの底における素数判定が合格の場合、素数である可能性が高い。言い換えると、不合格の場合には、１つの底における素数判定で不合格となる傾向がある。従って、１つの底における「ミラー-ラビンテスト」、一般的には「pの本格的素数判定（途中まで）」を先に行う構成にすることにより、「ミラー-ラビンテスト（１つの底におけるテスト）（ＳＴ４）」、一般的には「pの本格的素数判定（途中まで）（ＳＴ４’）」が不合格となる場合に、以後の処理（ステップＳＴ５〜ＳＴ９または、ステップＳＴ５’〜ＳＴ９’）を実行せずに済む。このため、各素数候補の試行割算後の本格的素数判定に関し、以後の処理（ＳＴ５〜ＳＴ９または、ステップＳＴ５’〜ＳＴ９’）の分だけ高速化を図ることができる。 （もっと読む）

【課題】セーフプライム形の素数に限定されず、第１素数の多項式の形をもつ第２素数を高速に生成する。
【解決手段】第１素数ｐと、この第１素数ｐから算出可能で定数項（ａ₀）が０ではない多項式ｆ（ｐ）（＝ａ_n・ｐⁿ ＋ ａ_n-1・ｐ^n-1 ＋ … ＋ ａ₂・ｐ² ＋ ａ₁・ｐ ＋ ａ₀）の形をもつ第２素数ｆ（ｐ）とを生成する構成により、セーフプライム形の素数（２ｐ＋１）に限定されず、第１素数ｐの多項式の形をもつ第２素数ｆ（ｐ）を生成できる。これに加え、高速に計算可能な試行割算を先に行った後に、フェルマーの小定理を含む本格的な素数判定法を行う構成により、時間のかかる本格的な素数判定法の実行割合を減少できるので、前述した第１及び第２素数ｐ，ｆ（ｐ）を高速に生成できる。 （もっと読む）

【課題】離散対数問題に難読性の根拠を置く暗号の強度を向上させる。また、ＲＳＡ暗号の鍵を高速に作成する。
【解決手段】同じ因数が重複して含まれる合成数を法としても１と合同になる一般化されたフェルマーの小定理を導出し、これを利用する。また、因数に関する関係式を用いて、最大公約数からも秘密鍵と公開鍵の逆数の関係にある２数を計算する。 また、離散対数問題の強度の向上については、複素数、または行列の離散対数問題を利用する。 （もっと読む）

本発明は、電子装置における特定の暗号アルゴリズムのための鍵を生成する方法に関し、電子装置に素数Ｐを格納し、少なくとも一つの秘密の素数を生成する。第１のステップ（ａ）では、和が数ｐ’に等しい二つの整数ｐ_１’及びｐ_２’を無作為に選択する（１１）。第２のステップ（ｂ）では、前記数ｐ’の秘密を維持するために、格納された素数Ｐと数ｐ_１’及びｐ_２’との組合せに基づき、数ｐ’が素数であるかどうかを判定する（１２）。第３のステップ（ｃ）では、もし数ｐ’が素数であると判定されれば、数ｐ_１’及びｐ_２’を電子装置に格納し（１４）、そうでなければ、ステップ（ａ）と（ｂ）を繰り返す。
（もっと読む）

素数の算出を行う際に、簡単な管理により重複を避けながら素数を算出する素数算出装置を提供する。 素数算出装置は、既知の素数ｑと、素数の利用範囲における一意の管理情報を記憶している。素数算出装置は、管理情報を読み出し、読み出した管理情報に依存する攪乱情報Ｒを生成し、素数ｑを読み出し、読み出した素数ｑと生成した攪乱情報Ｒとを用いて、数Ｎ＝２×攪乱情報Ｒ×素数ｑ＋１により、素数候補Ｎを算出し、算出された素数候補Ｎが素数であるか否かを判定し、素数であると判定された場合に、算出された素数候補Ｎを素数として出力する。これにより、素数算出装置は、一意の管理情報から、重複を避けながら素数候補を算出することができる。 （もっと読む）

正当に生成されたものであるか否かを確認できる素数を算出する素数算出装置を提供する。 素数算出装置は、乱数を生成し、管理識別子に前記乱数を乗じて乗算値Ｒを算出し、２×ｗ×素数ｑ＋１＝検証値 （ｍｏｄ 管理情報）を満たすｗについて、Ｎ＝２×（乗算値Ｒ＋ｗ）×素数ｑ＋１により、素数候補Ｎを算出する。次に、算出された素数候補Ｎが素数であるか否かを判定し、素数であると判定される場合に、算出された素数候補Ｎを素数として出力する。 （もっと読む）