JP4668795B2 - 素数算出装置、鍵発行システム及び素数算出方法 - Google Patents
素数算出装置、鍵発行システム及び素数算出方法 Download PDFInfo
- Publication number
- JP4668795B2 JP4668795B2 JP2005516589A JP2005516589A JP4668795B2 JP 4668795 B2 JP4668795 B2 JP 4668795B2 JP 2005516589 A JP2005516589 A JP 2005516589A JP 2005516589 A JP2005516589 A JP 2005516589A JP 4668795 B2 JP4668795 B2 JP 4668795B2
- Authority
- JP
- Japan
- Prior art keywords
- prime number
- prime
- unit
- information
- key
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims description 179
- 238000003860 storage Methods 0.000 claims description 457
- 238000012795 verification Methods 0.000 claims description 151
- 238000004364 calculation method Methods 0.000 claims description 137
- 238000004590 computer program Methods 0.000 claims description 34
- 238000002347 injection Methods 0.000 claims description 30
- 239000007924 injection Substances 0.000 claims description 30
- 230000003252 repetitive effect Effects 0.000 claims 1
- 238000012790 confirmation Methods 0.000 description 129
- 230000006870 function Effects 0.000 description 84
- 238000012545 processing Methods 0.000 description 62
- 238000012550 audit Methods 0.000 description 53
- 238000007726 management method Methods 0.000 description 51
- 230000005540 biological transmission Effects 0.000 description 29
- 238000004891 communication Methods 0.000 description 27
- 238000012986 modification Methods 0.000 description 25
- 230000004048 modification Effects 0.000 description 25
- 238000010586 diagram Methods 0.000 description 17
- 230000014509 gene expression Effects 0.000 description 14
- 238000009826 distribution Methods 0.000 description 8
- 238000004519 manufacturing process Methods 0.000 description 7
- 230000008929 regeneration Effects 0.000 description 6
- 238000011069 regeneration method Methods 0.000 description 6
- 238000007796 conventional method Methods 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 3
- 230000001172 regenerating effect Effects 0.000 description 3
- 101001081533 Homo sapiens Isopentenyl-diphosphate Delta-isomerase 1 Proteins 0.000 description 2
- 101001036194 Homo sapiens Isopentenyl-diphosphate delta-isomerase 2 Proteins 0.000 description 2
- 102100027665 Isopentenyl-diphosphate Delta-isomerase 1 Human genes 0.000 description 2
- 102100039618 Isopentenyl-diphosphate delta-isomerase 2 Human genes 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 101001051777 Homo sapiens Protein kinase C alpha type Proteins 0.000 description 1
- 125000002066 L-histidyl group Chemical group [H]N1C([H])=NC(C([H])([H])[C@](C(=O)[*])([H])N([H])[H])=C1[H] 0.000 description 1
- 241000255777 Lepidoptera Species 0.000 description 1
- 102100024924 Protein kinase C alpha type Human genes 0.000 description 1
- 230000001419 dependent effect Effects 0.000 description 1
- 239000004065 semiconductor Substances 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
- H04L9/3033—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters details relating to pseudo-prime or prime number generation, e.g. primality test
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
- G06F2207/7204—Prime number generation or prime number testing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
- H04L2209/08—Randomization, e.g. dummy operations or using noise
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- Mathematical Optimization (AREA)
- Computational Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Analysis (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- General Engineering & Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Algebra (AREA)
- Databases & Information Systems (AREA)
- Software Systems (AREA)
- Storage Device Security (AREA)
Description
これらの秘密通信方式又はデジタル署名方式においては、公開鍵暗号方式とよばれる暗号方式が用いられる。公開鍵暗号方式を用いる秘密通信では、暗号化鍵と復号化鍵とが異なり、復号化鍵は秘密にするが、暗号化鍵は公開する。秘密にする復号化鍵を秘密鍵と呼び、公開する暗号化鍵を公開鍵と呼ぶ。通信相手が多数のとき、共通鍵暗号では通信相手間で鍵をもつ必要があるが、公開鍵暗号では通信相手が一つの固有の鍵をもつだけで通信可能になるため、通信相手が増えても、共通鍵暗号より鍵の数が少なくてよい。このように、公開鍵暗号は多数の通信相手と通信を行うのに適しており、不可欠な基盤技術である。
ここで、素因数分解問題を応用するRSA暗号方式について説明する。
(1)鍵の生成
次に示すようにして公開鍵及び秘密鍵を計算する。
・ランダムに大きい素数p,qを選択し、その積n=p×qを計算する。
・Lと互いに素でLより小さい自然数eをランダムに選ぶ。
1≦e≦L−1、GCD(e,L)=1
ここで、GCD(e,L)は、eとLの最大公約数を示している。
・e×d=1 mod Lを満たすdを計算する。GCD(e,L)=1より、このようなdは必ず存在する。このようにして、得られた整数e及び整数nが、公開鍵である。また、整数dが、秘密鍵である。ここで、x mod yは、xをyで割った余りを示す。
公開鍵である整数e及び整数nを用いて、平文mに暗号演算を施して暗号文cを計算する。
c=m^e mod n
なお、この明細書において、演算子^は、べき乗を示す。例えば、A^xは、x>0のときはAをx回乗じたものを示す。
秘密鍵である整数dを用いて、暗号文cに復号演算を施して復号文m’を計算する。
m’=c^d mod n
なお、
m’=c^d mod n
=(m^e )^d mod n
=m^(e×d mod L) mod n
=m^1 mod n
=m mod n
であるので、復号文m’は、平文mと一致する。
上記に示した素因数分解を応用したRSA暗号における公開鍵の生成のステップにおいて、素数生成が行われる。素数生成については、非特許文献3の145〜154ページに詳しく説明されている。素数生成方法には、確率的素数生成法と確定的素数生成方法がある。確率的素数生成法により生成される素数は、「素数である確率が高い」数であり、100%素数であるとは限らない。一方、確定的素数生成方法は、確実に素数である数を生成する。確率的素数生成方法及び確定的素数生成方法については、非特許文献2に詳しく説明されている。以下では、確定的素数生成方法について説明する。
確定的に素数を生成することができるMaurer法による確定的素数生成方法について説明する。ここで、Maurer法については、非特許文献3の152〜153ページに詳しく説明されている。
前記確定的素数生成方法では、次に示すステップを繰り返すことにより、素数を生成する。あらかじめビットサイズlenqの素数qが与えられている。
(ステップ2)数Nを以下の式により計算する。
N=2×q×R+1
(ステップ3)数Nが素数であるか否かを、次に示す第1判定及び第2判定がともに、成立する場合に、素数と判定する。他の場合に、素数でないと判定する。
(第2判定) GCD(2^(2R)−1、N)=1
素数であると判定される場合には、数Nを素数として出力する。素数でないと判定される場合には、ステップ1へ戻って、素数が出力されるまで、処理を繰り返す。
ステップ3で述べられている判定方法は、Pocklingtonの素数判定法とよばれ、非特許文献3の144ページに詳しく述べられている。Pocklingtonの素数判定法では、N=2×q×R+1のqが素数であり、第1判定及び第2判定の結果が真であれば、必ず、Nが素数になる。そのため、確定的に素数であることを判定でき、確定的な素数生成が可能になる。
(第3判定) 2^(2R)≠1 mod N
上記第3判定方法は、非特許文献4に詳しく述べられている。以降、こちらの判定方法を使用していく。
3.複数の鍵発行サーバをもつ鍵発行システム
公開鍵暗号の鍵発行システムでは、ユーザが鍵を生成する場合や、鍵発行サーバによりユーザに鍵を発行する場合がある。鍵発行サーバにより鍵を発行する場合、ユーザに鍵を発行するサーバは一台であることが多い。しかし、処理の負荷を軽減するために、鍵発行システムは、複数台の鍵管理サーバを備え、複数台の鍵管理サーバのそれぞれにおいて、鍵を発行することもある。
例えば、第3のユーザが、第1のユーザのための前記公開鍵を用いて、第1のユーザに対して、暗号文を生成して送付すると、第1のユーザは、当然、自身の秘密鍵を用いて、暗号文を復号できるが、第2のユーザも自身の秘密鍵を用いて、前記暗号文を復号できてしまう。
そこで、本発明は、素数の算出を行う際に、簡単な管理により重複を避けながら素数を算出する素数算出装置、鍵発行システム、素数算出方法及び素数算出プログラムを提供することを目的とする。
ここで、前記攪乱情報生成手段は、前記管理情報記憶手段から前記管理情報を読み出す読出部と、乱数rを算出する乱数算出部と、読み出した前記管理情報と生成した乱数rとを結合する結合部と、前記管理情報と乱数rとの結合体に基づいて、攪乱情報Rを算出する演算部とを含むとしてもよい。
ここで、前記演算部は、前記結合体に、単射の関数を施して攪乱情報Rを生成するとしてもよい。
ここで、前記単射の関数は、排他的論理和であり、前記演算部は、所定の鍵情報を予め記憶しており、前記鍵情報と前記結合体とに排他的論理和を施して攪乱情報Rを生成するとしてもよい。
ここで、前記素数算出装置は、素数qの2倍のビット長を有する素数候補Nを算出し、前記乱数算出部は、素数qのビット長から前記管理情報のビット長及び1を差し引いて得られるビット長の前記乱数rを算出するとしてもよい。
ここで、前記素数判定手段は、前記素数候補Nに対して、2N-1 =1 mod Nを満たすか否かを判定する第1判定部と、前記第1判定部により満たすと判定される場合に、さらに、素数候補N及び攪乱情報Rに対して、22R ≠1 mod Nを満たすか否かを判定し、満たすと判定する場合に、素数候補Nが素数であると決定する第2判定部とを含むとしてもよい。
ここで、前記素数判定手段は、前記素数候補Nに対して、2N-1 =1 mod Nを満たすか否かを判定する第1判定部と、前記第1判定部により満たすと判定される場合に、さらに、素数候補N及び攪乱情報Rに対して、GCD(22R −1、N)=1を満たすか否かを判定し、満たすと判定する場合に、素数候補Nが素数であると決定する第2判定部とを含むとしてもよい。
ここで、前記素数算出装置は、さらに、前記素数判定手段により素数であると判定されるまで、前記攪乱情報生成手段、前記候補算出手段及び前記素数判定手段に対して、攪乱情報Rの生成と、素数候補Nの算出と、前記判定とを繰り返すように制御する繰返制御手段を含むとしてもよい。
ここで、前記素数算出装置は、さらに、乱数R'を算出する次段乱数算出手段と、出力された前記素数N及び生成された前記乱数R'を用いて、N'=2×乱数R'×素数N+1により、素数候補N'を算出する次段候補算出手段と、算出された素数候補N'が素数であるか否かを判定する次段素数判定手段と、素数であると判定される場合に、算出された素数候補N'を素数として出力する次段出力手段と、前記次段素数判定手段により素数であると判定されるまで、前記次段乱数算出手段、前記次段候補算出手段及び前記次段素数判定手段に対して、乱数R'の生成と、素数候補N'の算出と、前記判定とを繰り返すように制御する次段繰返制御手段とを含むとしてもよい。
ここで、記素数算出装置は、さらに、所定の検証値を記憶している次段情報記憶手段と、乱数r’を生成する次段乱数生成手段と、前記管理情報に生成した前記乱数r’を乗じて攪乱情報R’を算出し、N’=2×攪乱情報R’×素数N+検証値により、素数候補N’を算出する次段候補算出手段とを含み、前記素数判定手段は、さらに、算出された素数候補N'が素数であるか否かを判定し、前記出力手段は、さらに、素数候補N'が素数であると判定される場合に、算出された素数候補N'を素数として出力するとしてもよい。
この構成によると、素数算出装置は、RSA暗号の公開鍵及び秘密鍵を生成する鍵生成装置とすることができ、素数算出装置は、算出された素数Nを用いて、公開鍵を生成し、生成した公開鍵を用いて、秘密鍵を生成することができる。
ここで、前記素数算出装置は、端末装置に対して、RSAの秘密鍵及び公開鍵を生成し、発行する鍵発行サーバ装置であり、前記素数算出装置は、さらに、生成した前記秘密鍵を、端末装置に対して出力する鍵出力手段と、生成した前記公開鍵を、公開する公開手段とを含むとしてもよい。
ここで、前記素数算出装置は、さらに、前記端末装置を一意に識別する端末装置識別子を取得する識別子取得手段と、取得した端末装置識別子を含む前記管理情報を生成する管理情報生成手段と、生成した前記管理情報を前記管理情報記憶手段に書き込む書込手段とを含むとしてもよい。
ここで、前記素数算出装置は、さらに、鍵発行サーバ装置としての当該素数算出装置を一意に識別するサーバ識別子を予め記憶しているサーバ識別子記憶手段を含み、前記管理情報生成手段は、さらに、前記サーバ識別子記憶手段から前記サーバ識別子を読み出し、読み出したサーバ識別子をさらに含む前記管理情報を生成するとしてもよい。
また、本発明は、既知の素数より大きい素数を算出する素数算出装置であって、既知の入力素数の2倍のビット長を有する出力素数を算出する素数算出手段と、既知の素数初期値を記憶している素数記憶手段と、前記素数算出手段に対して、算出を複数回繰り返すように制御する繰返制御手段とを備え、前記繰返制御手段は、前記繰返しにおける初回の算出において、前記素数記憶手段に記憶されている素数初期値を、前記入力素数として、前記素数算出手段に与え、前記繰返しの初回の算出以外の他の算出において、1つ前の回の算出においてされた出力素数を、当該他の算出における前記入力素数として、前記素数算出手段に与え、前記複数回の算出のいずれか1の算出において、前記素数算出手段は、素数の利用範囲における一意の管理情報を記憶している管理情報記憶部と、前記管理情報記憶部から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Rを生成する攪乱情報生成部と、前記入力素数qを受け取り、受け取った前記入力素数q及び生成された前記攪乱情報Rを用いて、N=2×攪乱情報R×素数q+1により、素数候補Nを算出する候補算出部と、算出された素数候補Nが素数であるか否かを判定する素数判定部と、素数であると判定される場合に、算出された素数候補Nを出力素数として出力する出力部と、前記素数判定部により素数であると判定されるまで、前記攪乱情報生成部、前記候補算出部及び前記素数判定部に対して、攪乱情報Rの生成と、素数候補Nの算出と、前記判定とを繰り返すように制御する繰返制御部とを含むことを特徴とする。
ここで、前記複数回の算出のうち、最終回の算出において、前記素数算出手段は、所定の検証値を記憶している情報記憶部と、乱数r'を生成する乱数生成部と、前記管理情報に生成した前記乱数r'を乗じて攪乱情報R'を算出し、N'=2×攪乱情報R'×1つ前の回において算出された出力素数+検証値により、素数候補N'を算出する候補算出部と、算出された素数候補N'が素数であるか否かを判定する素数判定部と、素数候補N'が素数であると判定される場合に、算出された素数候補N'を素数として出力する出力部と、前記素数判定部により素数であると判定されるまで、前記乱数生成部、前記候補算出部及び前記素数判定部に対して、乱数r'の生成と、素数候補N'の算出と、前記判定とを繰り返すように制御する繰返制御部とを含むとしてもよい。
本発明に係る第1の実施の形態としての鍵発行システム1について、説明する。
1.1 鍵発行システム1の概要
鍵発行システム1は、図1に示すように、鍵発行サーバ100、101、102と、証明書発行サーバ200と、端末装置300、301、・・・、302、303、・・・、304、305、・・・、306とから構成されている。端末装置の台数は、例えば1000台である。
なお、以下においては、鍵発行サーバ100、証明書発行サーバ200、及び端末装置300を用いて、鍵発行システム1の概要を説明する。
鍵発行サーバ100は、端末装置300より鍵の発行要求を受け取ると、RSA暗号における秘密鍵及び公開鍵を生成し、証明書発行サーバ200に対して、生成した公開鍵に対する公開鍵証明書の発行要求をする。なお、ここで、生成する各鍵の鍵長は、1024ビットとする。
鍵発行サーバ100は、証明書発行サーバ200より公開鍵証明書を受け取ると、受け取った公開鍵証明書と、生成した秘密鍵とを、端末装置300へ送信する。
端末装置300は、公開鍵証明書と、秘密鍵とを、鍵発行サーバ100より受け取ると、受け取った公開鍵証明書と、秘密鍵とを記憶する。
これにより、端末装置300と端末装置400との間では、安全にデータのやりとりができるようになる。
以降の説明において、各端末装置の代表として端末装置300を、各鍵発行サーバの代表として鍵発行サーバ100を用いる。
鍵発行サーバ100は、図2にて示すように、識別子格納部110、秘密鍵格納部111、公開鍵格納部112、証明書格納部113、制御部114、識別子生成部115、素数生成部116、鍵判定部117、鍵生成部118、情報取得部119、受信部120及び送信部121から構成されている。
(1)識別子格納部110
識別子格納部110は、ビットサイズが126ビット以下である発行識別子情報を記憶するための領域を有している。発行識別子情報のビットサイズは、例えば、64ビットである。
秘密鍵格納部111は、秘密鍵生成の際に用いられる2つの素数を記憶するための素数格納領域と、鍵生成部118にて生成された秘密鍵を記憶するための秘密鍵格納領域とを有している。
(3)公開鍵格納部112
公開鍵格納部112は、鍵生成部118にて生成された公開鍵を記憶するための領域を有している。
証明書格納部113は、証明書発行サーバにて発行された公開鍵証明書を記憶する領域を有している。
(5)制御部114
制御部114は、図2に示すように、サーバ識別子記憶領域130と、端末情報記憶領域131とを有している。
制御部114は、端末装置300から受信部120を介して、鍵の発行要求を示す鍵発行依頼情報と、端末装置300の端末識別子「TID」とを受け取ると、受け取った端末識別子「TID」を端末情報記憶領域131へ書き込む。制御部114は、発行識別子情報の生成命令と、受け取った端末識別子「TID」とを識別子生成部115へ出力する。
(6)識別子生成部115
識別子生成部115は、制御部114から発行識別子情報の生成命令と、端末識別子「TID」とを受け取ると、サーバ識別子記憶領域にて記憶されているサーバ識別子「SID」を取得する。
(7)素数生成部116
素数生成部116は、図3に示すように、繰返制御部132及び素数情報生成部133とを有している。
<繰返制御部132>
繰返制御部132は、8ビットからなる素数とその素数のビットサイズ(つまり「8」)とを予め記憶している初期値記憶領域と、素数情報生成部133から受け取った素数を一時的に記憶する一時記憶領域とを有している。
繰返制御部132は、図4に示す制御情報テーブルT100を有している。制御情報テーブルT100は、回数と制御情報とからなる組を1以上格納している。回数は、繰返カウンタ135の値に対応する。制御情報は、素数情報生成部133にて生成する素数の生成方法の種別を示す。
繰返制御部132は、識別子生成部115から素数の生成開始命令を受け取ると、繰返カウンタ135及び出力カウンタ136を、それぞれ「1」に設定する。
繰返制御部132は、素数情報生成部133から、素数を受け取ると、繰返カウンタ135の値に「1」を加算し、加算結果が、7であるか否かを判断する。
繰返制御部132は、素数の生成開始命令を受け取り、繰返カウンタ135及び出力カウンタ136のそれぞれの値に「1」を加算した後、素数情報生成部133から受け取った素数とそのビットサイズとを一時的に記憶した後、及び出力カウンタ136に「1」を加算し、且つ繰返カウンタ135の値を「1」に設定した後の何れかの場合において、繰返制御部132は、以下の動作を行う。
「情報C」であると判断する場合には、繰返制御部132は、読み出した素数及びそのビットサイズと、制御情報とからなる第1情報を生成し、生成した第1情報を、素数情報生成部133へ出力する。
<素数情報生成部133>
素数情報生成部133は、図5に示すように、情報制御部140、乱数生成部141、素数候補生成部142、第1素数判定部143及び第2素数判定部144から構成されている。
なお、以下の説明において、繰返制御部132から受け取る素数を素数「q」、そのビットサイズを「lenq」として、各構成要素について説明する。
情報制御部140は、第1情報及び第2情報を記憶するための情報記憶領域を有している。
情報制御部140は、証明書発行サーバ200により割り当てられ、且つ制御情報「情報A」に基づいて素数を生成する際に用いる第1検証値「c11」及び第2検証値「c12」を予め記憶している検証値記憶領域を有している。
情報制御部140は、繰返制御部132から、素数「q」と、素数のビットサイズ「lenq」と、制御情報と、発行識別子情報「IDI」と、そのビットサイズ「lenIDI」とからなる第2情報を受け取ると、受け取った第2情報を情報記憶領域へ書き込む。つまり、素数「q」と、素数のビットサイズ「lenq」と、制御情報、発行識別子情報「IDI」と、そのビットサイズ「lenIDI」とを書き込む。
情報制御部140は、第2素数判定部144より、素数を受け取ると、受け取った素数を繰返制御部132へ出力する。
情報制御部140は、素数候補生成部142から出力カウンタ136の値を読み出す旨の回数読出命令を受け取ると、繰返制御部132の出力カウンタ136の値を読み出す。情報制御部140は、読み出した値を、素数候補生成部142へ出力する。
乱数生成部141は、乱数の生成の指示を示す第1生成指示を、情報制御部140から受け取ると、情報制御部140の情報記憶領域にて記憶されている制御情報を読み出す。乱数生成部141は、読み出した制御情報が「情報C」であるか否かを判断する。
「情報C」であると判断する場合には、乱数生成部141は、情報制御部140の情報記憶領域にて記憶されている「lenq」を読み出し、(lenq−1)ビットからなる乱数「R1」を生成し、生成した乱数「R1」と読み出した制御情報とを素数候補生成部142へ出力する。ここで、乱数「R1」の最上位ビットは1とする。乱数生成方法は、非特許文献2が詳しい。
<素数候補生成部142>
素数候補生成部142は、生成された情報を記憶する生成情報記憶領域と、単射である関数「f」を予め記憶している関数記憶領域とを有している。ここで、関数「f」は、例えば、f(X||Y)=Enc(K、X||Y)である。Enc(K、X||Y)は鍵Xを用いたときの(X||Y)の共通鍵暗号による暗号文である。共通鍵暗号の暗号化関数は一般的に全単射である。また、記号「||」はビットまたはバイト連結である。暗号化関数「Enc(K、X||Y)」の一例は、「Enc(K、X||Y)=K XOR X||Y」である。なお、共通暗号の一例は、DESであり、DESを用いる場合には、鍵長は128ビットとなる。このとき、素数候補生成部142は、所定の鍵「K」を記憶している。
「情報C」であると判断する場合には、素数候補生成部142は、情報制御部140の情報記憶領域より素数「q」を読み出す。素数候補生成部142は、読み出した素数「q」と乱数生成部141より受け取った乱数「R1」とを用いて、数「N=2×R1×q+1」を生成する。このとき生成した数「N」が素数候補となる。
一致しないと判断する場合には、素数候補生成部142は、乱数生成部141より受け取った乱数「R1」に2を掛けて、その結果を「R1」として、再度、上記の動作を行い、数「N=2×R1×q+1」を生成する。
「情報B」であると判断する場合には、素数候補生成部142は、受け取った乱数「R1」と読み出した発行識別子情報「IDI」とから、結合値「IDI||R1」を生成し、生成した結合値「IDI||R1」と関数記憶領域にて記憶している関数「f」とを用いて、数「R=f(IDI||R1)」を生成する。素数候補生成部142は、生成した数「R」と読み出した素数「q」とを用いて、数「N=2×R×q+1」を生成する。このとき生成した数「N」が素数候補となる。
「2×lenq」であると判断する場合には、素数候補生成部142は、生成した数「N」を第1素数判定部143へ出力し、生成した数「R」を生成情報記憶領域に記憶する。
「情報B」でないと判断する場合には、素数候補生成部142は、受け取った乱数「R1」と読み出した発行識別子情報「IDI」とを用いて、数「R=IDI×R1」を生成する。素数候補生成部142は、回数読出命令を情報制御部140へ出力し、情報制御部140から、出力カウンタ136の値を受け取る。素数候補生成部142は、出力カウンタ136の値が「1」であるか否かを判断する。
出力回数が「1」でない、つまり「2」以上であると判断する場合には、素数候補生成部142は、情報制御部140の検証値記憶領域より第2検証値「c12」を読み出す。
なお、第1検証値「c11」を読み出した場合の動作と、第2検証値「c12」を読み出した場合の動作とは、同じであるため、以下においては、検証値「c」として説明する。
ここで、「w」は「2×w×q+1=c mod IDI、0≦w<IDI」を満たす数である。「w」は、「w=(c−1)×m mod IDI」を計算することにより求める。「m」は「(2×q)×m=1 mod IDI」を満たす数である。上述したように、発行識別子情報「IDI」が奇数、すなわち、「GCD(IDI、2)=1」であり、「IDI<q」であるため、「m」は計算可能である。計算方法については、非特許文献5が詳しい。なお、以降において、第1検証値「c11」を用いた場合の「w」を「w1」と表記、及び第2検証値を用いた場合の「w」を「w2」と表記する。
「2×lenq」であると判断する場合には、素数候補生成部142は、生成した数「N」を第1素数判定部143へ出力し、生成した数「R」を生成情報記憶領域に記憶する。
<第1素数判定部143>
第1素数判定部143は、数「N」を素数候補生成部142より受け取ると、受け取った数「N」を用いて、以下の式の成立を判定する。
ここで、2^(N−1)は、2のN−1乗を示している。
第1素数判定部143は、式(eq1)が成立していると判断する場合には、数「N」を第2素数判定部144へ出力する。
第1素数判定部143は、式(eq1)が成立していないと判断する場合には、乱数生成部141へ第2生成指示を出力する。
第2素数判定部144は、数「N」を第1素数判定部143より受け取ると、素数候補生成部142の生成情報記憶領域にて記憶されている数「R」を読み出す。
第2素数判定部144は、数「N」及び「R」とを用いて、以下の式の成立を判定する。
第2素数判定部144は、式(eq2)が成立していると判断する場合には、数「N」を素数「N」として、情報制御部140を介して、繰返制御部132へ出力する。
第2素数判定部144は、式(eq2)が成立していないと判断する場合には、乱数生成部141へ第2生成指示を出力する。
鍵判定部117は、素数生成部116より受け取った2つの素数「p1」及び「p2」を、記憶する素数記憶領域を有する。
鍵判定部117は、素数生成部116より素数「p1」及び「p2」を受け取ると、受け取った素数「p1」及び「p2」をそれぞれ素数記憶領域へ記憶する。
一致しないと判断する場合には、記憶している2つの素数「p1」及び「p2」を、秘密鍵格納部111の素数格納領域へ書き込み、鍵生成開始命令を鍵生成部118へ出力する。
鍵生成部118は、鍵判定部117より鍵生成命令を受け取ると、秘密鍵格納部111の素数格納領域にて記憶されている2つの素数「p1」及び「p2」を読み出し、読み出した素数「p1」と「p2」との積「n=p1×p2」を計算する。
鍵生成部118は、乱数「e」を生成し、算出した「n」と、生成した乱数「e」とからなる組「PK=(n、e)」を公開鍵として生成し、生成した公開鍵「PK」を公開鍵格納部112へ書き込む。ここで、乱数「e」は、従来と同様に、乱数「e」は、数「L」と互いに素であり、「1≦e≦L−1、GCD(e、L)=1」を満たす。ここで、GCD(e、L)は、eとLの最大公約数を示し、数「L」は、「L=LCM(p1−1、p2−1)」であり、LCM(p1−1、p2−1)は、「p1−1」と「p2−1」との最小公倍数を示す。
(10)情報取得部119
情報取得部119は、鍵生成部118から要求開始命令を受け取ると、識別子格納部110から発行識別子情報「IDI」と、公開鍵格納部112から公開鍵「PK」と、制御部114のサーバ識別子記憶領域130からサーバ識別子とを、それぞれ読み出す。情報取得部119は、読み出した発行識別子情報「IDI」と、公開鍵「PK」と、サーバ識別子と、公開鍵証明書の発行を依頼する証明書発行依頼情報とを送信部121を介して、証明書発行サーバ200へ送信する。
受信部120は、インターネットを介して、証明書発行サーバ200及び端末装置300より情報を受信し、受信した情報を、制御部114へ出力する。
(12)送信部121
送信部121は、情報取得部119より、発行識別子情報「IDI」と、公開鍵「PK」と、サーバ識別子と、証明書発行依頼情報とを受け取ると、受け取った各情報を証明書発行サーバ200へ送信する。
1.3 証明書発行サーバ200の構成
証明書発行サーバ200は、鍵発行サーバ100、101、及び102から証明書発行依頼情報を受け取ると、公開鍵証明書を発行し、発行した公開鍵証明書を発行依頼のあった鍵発行サーバへ送信する。
証明書発行サーバ200は、具体的には、マイクロプロセッサ、ROM、RAM、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記RAM又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、証明書発行サーバ200は、その機能を達成する。
(1)秘密鍵格納部210
秘密鍵格納部210は、証明書発行サーバ200のみが有する秘密鍵「SKCA」を予め記憶している。
(2)発行公開鍵格納部211
発行公開鍵格納部211は、鍵発行サーバ100より受け取った公開鍵「PK」を記憶する領域を有している。
発行識別子情報格納部212は、鍵発行サーバ100より受け取った発行識別子情報「IDI」を記憶する領域を有している。
(4)公開鍵証明書格納部213
公開鍵証明書格納部213は、発行した公開鍵証明書「Cert」を記憶する領域を有している。
発行公開鍵確認部214は、図6に示すように、サーバ情報記憶領域220及び確認情報記憶領域221を有している。
サーバ情報記憶領域220は、公開鍵証明書の発行依頼のあった鍵発行サーバを識別するサーバ識別子を記憶する領域を有している。
発行公開鍵確認部214は、受け取ったサーバ識別子を、サーバ情報記憶領域220に書き込む。
発行公開鍵確認部214は、受け取った公開鍵「PK」と発行識別子情報「IDI」とを用いて、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されたか否かを確認する。
発行公開鍵確認部214は、「n−(c11×c12)」が、「IDI」で割り切れると判断する場合には、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されたと判断し、「n−(c11×c12)」が、「IDI」で割り切れないと判断する場合には、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されていないと判断する。
発行公開鍵確認部214は、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されていないと判断する場合には、処理を終了する。
公開鍵証明書生成部215は、発行公開鍵確認部214より、公開鍵証明書の生成開始命令を受け取ると、秘密鍵格納部210より秘密鍵「SKCA」を、発行公開鍵格納部211より公開鍵「PK」を、発行識別子情報格納部212より発行識別子情報「IDI」を、それぞれ読み出す。
(7)証明書取得部216
証明書取得部216は、公開鍵証明書生成部215より、公開鍵証明書「Cert」の送信開始命令を受け取ると、公開鍵証明書格納部213から公開鍵証明書「Cert」を、サーバ情報記憶領域220からサーバ識別子を、それぞれ読み出し、読み出した公開鍵証明書「Cert」を、読み出したサーバ識別子に対応する鍵発行サーバ100へ送信部218を介して送信する。
受信部217は、鍵発行サーバ100より情報を受信し、受信した情報を、発行公開鍵確認部214へ出力する。
(9)送信部218
送信部218は、証明書取得部216より情報を受け取り、受け取った情報を鍵発行サーバ100へ送信する。
端末装置300は、図8にて示すように、秘密鍵格納部310、公開鍵証明書格納部311、制御部312、受付部313、無線部314、ベースバンド信号処理部315、スピーカー316、マイク317及び表示部318から構成されている。端末装置300の一例は、携帯電話機である。
また、端末装置301、・・・、302から鍵発行依頼情報と、端末識別子とを、鍵発行サーバ100へ送信した場合、端末装置303、・・・、304から鍵発行依頼情報と、端末識別子とを、鍵発行サーバ101へ送信した場合、及び端末装置305、・・・、306から鍵発行依頼情報と、端末識別子とを、鍵発行サーバ102へ送信した場合の動作は、端末装置300から鍵発行依頼情報と、端末識別子とを、鍵発行サーバ100へ送信した場合の動作と同じであるため、以降の説明では、鍵発行依頼情報と、端末識別子とを、鍵発行サーバ100へ送信した場合の動作について説明する。
秘密鍵格納部310は、鍵発行依頼情報を送信した鍵発行サーバ、ここでは、鍵発行サーバ100にて発行された秘密鍵「SK=(p1、p2、d)」を記憶する領域を有している。
(2)公開鍵証明書格納部311
公開鍵証明書格納部311は、鍵発行サーバ100にて発行された秘密鍵に対応する公開鍵の公開鍵証明書「Cert」を記憶する領域を有している。
制御部312は、図8にて示すように、端末識別子記憶領域320を有している。
制御部312は、暗号化された電子メールを記憶するメール記憶領域をも有している。
端末識別子記憶領域320は、当該装置を識別する端末識別子「TID」を予め記憶している。
制御部312は、鍵発行依頼情報と、読み出した端末識別子「TID」とを、鍵発行サーバ100へ、ベースバンド信号処理部315及び無線部314を介して送信する。
制御部312は、鍵発行サーバ100より、無線部314及びベースバンド信号処理部315を介して、秘密鍵「SK」及び公開鍵証明書「Cert」を受け取ると、受け取った秘密鍵「SK」を秘密鍵格納部310へ、公開鍵証明書「Cert」を公開鍵証明書格納部311へ、それぞれ書き込む。
制御部312は、受付部313より、暗号化された電子メールの表示命令を受け取ると、秘密鍵格納部310より秘密鍵「SK」を、メール記憶領域より暗号化された電子メールを、それぞれ読み出し、読み出した秘密鍵「SK」を用いて、暗号化された電子メールを復号し、復号された電子メール(以下、単に「電子メール」という。)を表示部318へ出力する。
受付部313は、ユーザの操作により、鍵発行要求の指示を受け付けると、受け付けた指示を制御部312へ出力する。
受付部313は、ユーザの操作により、暗号化された電子メールの表示の指示を受け付けると、表示命令を制御部312へ出力する。
無線部314は、アンテナ319を備えており、無線信号の送受信を行う。
(6)ベースバンド信号処理部315
ベースバンド信号処理部315は、無線部314より受け取った信号をスピーカー316へ出力するための信号処理や、マイク317より受け取った音声を無線部314へ出力するための信号処理を行う。
ベースバンド信号処理部315は、鍵発行サーバ100から秘密鍵及び公開鍵証明書とを、無線部314を介して受け取ると、受け取った秘密鍵及び公開鍵証明書を制御部312へ出力する。
ベースバンド信号処理部315は、端末装置400から暗号化された電子メールを、無線部314を介して受け取ると、受け取った暗号化された電子メールを制御部312へ出力する。
スピーカー316は、ベースバンド信号処理部315にて処理された信号を音声として出力する。
(8)マイク317
マイク317は、使用者の音声を受け付け、受け付けた音声をベースバンド信号処理部315へ出力する。
表示部318は、制御部312より受け取った電子メールを表示する。
1.5 鍵発行システム1の動作
ここでは、鍵発行システム1の動作について説明する。
(1)鍵発行システム1の動作概要
鍵発行システム1の動作概要を図9に示す流れ図を用いて、説明する。
端末装置300は、まず、鍵依頼処理にて、鍵発行依頼情報及び端末識別子「TID」を鍵発行サーバ100へ送信する(ステップS5)。
鍵発行サーバ100は、端末装置300より鍵発行依頼情報及び端末識別子「TID」を受信すると、鍵発行処理にて、発行識別子情報「IDI」、秘密鍵「SK=(p1、p2、d)」及び公開鍵「PK=(n、e)」を生成する。鍵発行サーバ100は、生成した発行識別子情報「IDI」及び公開鍵「PK」と、証明書発行依頼情報と、サーバ識別子「SID」とを、証明書発行サーバ200へ送信する(ステップS10)。
端末装置300は、鍵依頼処理にて、鍵発行サーバ100から秘密鍵「SK」と公開鍵証明書「Cert」とを受信すると、受信した秘密鍵「SK」、公開鍵証明書「Cert」を格納し、システムを終了する。
ここでは、図9に示す鍵依頼処理の動作について、図10に示す流れ図を用いて、説明する。なお、ここでは、端末装置300及び鍵発行サーバ100を用いて、鍵依頼処理の動作を説明する。
端末装置300の受付部313は、ユーザの操作により、鍵発行要求の指示を受け付ける(ステップS100)。
端末装置300の制御部312は、鍵発行依頼情報と、取得した端末識別子「TID」とを、鍵発行サーバ100へ、ベースバンド信号処理部315及び無線部314を介して送信する(ステップS110)。
制御部312は、受け取った秘密鍵「SK」を秘密鍵格納部310へ書き込み(ステップS120)、公開鍵証明書「Cert」を公開鍵証明書格納部311へ書き込む(ステップS125)。
ここでは、図9に示す鍵発行処理の動作について、図11、図12、図13及び図13に示す流れ図を用いて、説明する。
鍵発行サーバ100の制御部114は、端末装置300から受信部120を介して、鍵発行依頼情報と、端末装置300の端末識別子「TID」とを受け取ると(ステップS200)、受け取った端末識別子「TID」を端末情報記憶領域131へ書き込み、発行識別子情報の生成命令と、受け取った端末識別子「TID」とを識別子生成部115へ出力する(ステップS205)。
繰返制御部132は、繰返カウンタ135の値が、1であるか否かを判断する(ステップS220)。
「情報C」であると判断する場合には(ステップS240における「YES」)、繰返制御部132は、読み出した素数及びそのビットサイズと、制御情報とからなる第1情報を生成し、生成した第1情報を、素数情報生成部133へ出力する(ステップS245)。
繰返制御部132は、素数情報生成部133から、素数を受け取ると、繰返カウンタ135の値に「1」を加算し(ステップS260)、加算結果が、7であるか否かを判断する(ステップS265)。
加算結果が7であると判断する場合には(ステップS265における「YES」)、繰返制御部132は、出力カウンタ136の値が、1であるか否かを判断する(ステップS280)。
1でない、つまり2以上であると判断する場合には(ステップSNOにおける「NO」)、繰返制御部132は、受け取った素数を素数「p2」として、素数「p2」と判定開始命令を鍵判定部117へ出力する(ステップS300)。
情報取得部119は、鍵生成部118から要求開始命令を受け取ると、識別子格納部110から発行識別子情報「IDI」と、公開鍵格納部112から公開鍵「PK」と、制御部114のサーバ識別子記憶領域130からサーバ識別子とを、それぞれ読み出す(ステップS335)。情報取得部119は、読み出した発行識別子情報「IDI」と、公開鍵「PK」と、サーバ識別子と、公開鍵証明書の発行を依頼する証明書発行依頼情報とを送信部121を介して、証明書発行サーバ200へ送信する(ステップS340)。
情報取得部119は、制御部114から配布開始命令を受け取ると、秘密鍵格納部111にて記憶している秘密鍵「SK」と、証明書格納部113にて記憶している公開鍵証明書「Cert」と、制御部114の端末情報記憶領域にて記憶している端末識別子とを、それぞれ読み出し(ステップS350)、読み出した秘密鍵「SK」及び公開鍵証明書「Cert」を、読み出した端末識別子に対応する端末装置300へ送信部121を介して送信する(ステップS355)。
ここでは、図12に示す素数生成処理の動作について、図15に示す流れ図を用いて、説明する。
情報制御部140は、繰返制御部132から、素数「q」と、素数のビットサイズ「lenq」と、制御情報とからなる第1情報及び素数「q」と、素数のビットサイズ「lenq」と、制御情報と、発行識別子情報「IDI」と、そのビットサイズ「lenIDI」とからなる第2情報の何れかを受け取ると、受け取った情報を情報記憶領域へ書き込み、乱数の生成の指示を示す第1生成指示を、乱数生成部141へ出力する(ステップS400)。
「情報C」であると判断する場合には(ステップS410における「YES」)、乱数生成部141は、情報制御部140の情報記憶領域にて記憶されている「lenq」を読み出し(ステップS415)、(lenq−1)ビットからなる乱数「R1」を生成し、生成した乱数「R1」と読み出した制御情報とを素数候補生成部142へ出力する(ステップS420)。ここで、乱数「R1」の最上位ビットは1とする。乱数生成方法は、非特許文献2が詳しい。
第1素数判定部143は、数「N」を素数候補生成部142より受け取ると、受け取った数「N」を用いて、上述した式(eq1)が成立するか否かを判断する(ステップS440)。
第1素数判定部143は、式(eq1)が成立していないと判断する場合には、乱数生成部141へ第2生成指示を出力(ステップS440における「NO」)、第2素数判定部144は、式(eq2)が成立していないと判断する場合には、乱数生成部141へ第2生成指示を出力し(ステップS445における「NO」)、乱数生成部141は、第1素数判定部143及び第2素数判定部144の何れかから、再度乱数を生成する旨の第2生成指示を受け付けると、ステップS405に戻る。
ここでは、図15に示す素数候補生成処理の動作について、図16及び図17に示す流れ図を用いて、説明する。
素数候補生成部142は、乱数生成部141より、乱数「R1」と制御情報とを受け取ると(ステップS500)、受け取った制御情報が「情報C」であるか否かの判断をする(ステップS505)。
制御情報が「情報C」でないと判断する場合には(ステップS505における「NO」)、素数候補生成部142は、情報制御部140の情報記憶領域より素数「q」及び発行識別子情報「IDI」を読み出す(ステップS530)。素数候補生成部142は、制御情報が「情報B」であるか否かを判断する(ステップS535)。
「2×lenq」であると判断する場合には(ステップS550における「YES」)、素数候補生成部142は、生成した数「N」を第1素数判定部143へ出力し、生成した数「R」を生成情報記憶領域に記憶する(ステップS595)。
「情報B」でないと判断する場合には(ステップS535における「NO」)、素数候補生成部142は、受け取った乱数「R1」と読み出した発行識別子情報「IDI」とを用いて、数「R=IDI×R1」を生成する(ステップS560)。素数候補生成部142は、回数読出命令を情報制御部140へ出力し、情報制御部140から、出力カウンタ136の値を受け取る。素数候補生成部142は、受け取った値が「1」であるか否かを判断する(ステップS565)。
「2×lenq」であると判断する場合には(ステップS590における「YES」)、素数候補生成部142は、生成した数「N」を第1素数判定部143へ出力し、生成した数「R」を生成情報記憶領域に記憶する(ステップS595)。
(6)証明書発行処理
ここでは、図9に示す証明書発行処理の動作について、図18に示す流れ図を用いて、説明する。
発行公開鍵確認部214は、受け取ったサーバ識別子を、サーバ情報記憶領域220に書き込む(ステップS655)。
発行公開鍵確認部214は、読み出した第1検証値「c11」及び第2検証値「c12」と、受け取った公開鍵「PK」と、発行識別子情報「IDI」とを用いて、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されたか否かを確認する(ステップS660)。
公開鍵証明書生成部215は、発行公開鍵確認部214より、公開鍵証明書の生成開始命令を受け取ると、秘密鍵格納部210より秘密鍵「SKCA」を、発行公開鍵格納部211より公開鍵「PK」を、発行識別子情報格納部212より発行識別子情報「IDI」を、それぞれ読み出す(ステップS670)。
証明書取得部216は、公開鍵証明書生成部215より、公開鍵証明書「Cert」の送信開始命令を受け取ると、公開鍵証明書格納部213から公開鍵証明書「Cert」を、サーバ情報記憶領域220からサーバ識別子を、それぞれ読み出し、読み出した公開鍵証明書「Cert」を、読み出したサーバ識別子に対応する鍵発行サーバ100へ送信部218を介して送信する(ステップS680)。
素数情報生成部133の第1素数判定部143及び、第2素数判定部144は、Pocklington判定である。Pocklington判定は、非特許文献1の144ページ及び非特許文献4が詳しい。以下に、簡単に説明する。
Pocklington判定によると、「N=2×R×q+1」の「q」が素数であり
2^(N−1) = 1 mod N
2^(2R) ≠1 mod N
の両方が成り立つ場合、数「N」は素数となり、素数情報生成部133は、数「N」を素数として出力することができる。
(1)生成される鍵の一意性
ここでは、鍵発行サーバ100にて生成される鍵、つまり素数の一意性について説明する。
ここで、以下の命題を証明する。
まず、以下の補題を証明し、その補題を用いて、上記の命題を証明する。
(補題)二つの素数「p1=2×q1×R1+1」及び「p2=2×q2×R2+1」に対し、p1=p2であれば、q1=q2かつR1=R2となる。
(証明)p1=p2の場合、素数「q1」及び「q2」のビットサイズは、それぞれ256ビットであり、数「R1」及び「R2」のビットサイズは、それぞれ255ビットであるため、q1=q2となるのは明らか。また、q1=q2より、R1=R2も成り立つ(証明終)。
(2)生成された鍵の正当性
鍵発行サーバ100にて生成された素数「p1」に対して、「p1−c11」は必ず発行識別子情報「IDI」で割り切れる。
なぜなら、「p1−c11=2×q×(R+w1)+1−c11=2×q×(IDI×R1+w1)+1−c11=2×q×IDI×R1+2×q×w1+1−c11」であり、項「2×q×IDI×R」は、「IDI」で割り切れることが分かる。また、上述したように、「2×q×w1+1=c11 mod IDI」が成り立っているため、残りの項「2×q×w1+1−c11」も「IDI」で割り切れる。つまり、鍵発行サーバ100にて生成された素数「p1」に対して、「p1−c11」は必ず発行識別子情報「IDI」で割り切れる。したがって、生成された素数「p1」に対し、「p1−c11」が発行識別子情報「IDI」で割り切れるか否かで、鍵発行サーバ100を用いて素数が生成されたかを確認することができる。
したがって、「n−c11×c12」は「IDI」で割り切れるため、証明書発行サーバ200は、「n−c11×c12」が「IDI」で割り切れることを確認することで、素数「p1」、「p2」が正しく発行識別子情報「IDI」を用いて生成しているかを確認することができる。
n=p1×p2=(2×q1×IDI×R11+1)×(2×q2×IDI×R12+1)
=c11×c12 mod IDI
となる。そのため、証明書発行サーバ200は、「n−c11×c12」が「IDI」で割り切れるか否かを確認することにより、鍵発行サーバが正しく発行識別子情報IDIを用いて生成しているかを確認することができる。
上記実施の形態では、第1検証値及び第2検証値の2つの検証値を用いたが、ここでは、1つの検証値を用いた場合の素数の生成について、説明する。
上記実施の形態と異なる点は、鍵発行サーバにおける素数情報生成部と、証明書発行サーバにおける発行公開鍵確認部とが異なる。以下に、本変形例における素数情報生成部133A、及び発行公開鍵確認部214Aについて説明する。なお、他の構成要素については、第1の実施の形態にて示した構成要素を用いる。
素数情報生成部133Aは、図19に示すように、情報制御部140A、乱数生成部141A、素数候補生成部142A、第1素数判定部143A及び第2素数判定部144Aから構成されている。
素数情報生成部133Aは、繰返制御部132から受け取った素数のビットサイズが2倍のビットサイズからなる素数を生成する。
<情報制御部140A>
情報制御部140Aは、第1情報及び第2情報を記憶するための情報記憶領域を有している。
情報制御部140Aは、繰返制御部132から、素数「q」と、素数のビットサイズ「lenq」と、制御情報とからなる第1情報を受け取ると、受け取った第1情報を情報記憶領域へ書き込む。つまり、素数「q」と、素数のビットサイズ「lenq」と、制御情報(この場合、「情報C」)とを書き込む。
情報制御部140Aは、第2素数判定部144Aより、素数を受け取ると、受け取った素数を繰返制御部132へ出力する。
<乱数生成部141A>
乱数生成部141Aは、第1の実施の形態にて示す乱数生成部141Aと同様であるため、説明は省略する。
素数候補生成部142Aは、生成された情報を記憶する生成情報記憶領域と、単射である関数「f」を予め記憶している関数記憶領域とを有している。ここで、関数「f」は、例えば、f(X||Y)=Enc(K、X||Y)である。Enc(K、X||Y)は鍵Xを用いたときの(X||Y)の共通鍵暗号による暗号文である。共通鍵暗号の暗号化関数は一般的に全単射である。また、記号「||」はビットまたはバイト連結である。暗号化関数「Enc(K、X||Y)」の一例は、「Enc(K、X||Y)=K XOR X||Y」である。なお、共通暗号の一例は、DESであり、DESを用いる場合には、鍵長は128ビットとなる。
「情報C」であると判断する場合には、素数候補生成部142Aは、情報制御部140Aの情報記憶領域より素数「q」を読み出す。素数候補生成部142Aは、読み出した素数「q」と乱数生成部141Aより受け取った乱数「R1」とを用いて、数「N=2×R1×q+1」を生成する。素数候補生成部142Aは、生成した数「N」のビットサイズ「lenN」が「lenq」と一致するか否かを判断し、一致すると判断する場合には、素数候補生成部142Aは、生成した数「N」を第1素数判定部143Aへ出力し、受け取った乱数「R1」を、「R」として生成情報記憶領域に記憶する。
制御情報が「情報C」でないと判断する場合には、素数候補生成部142Aは、情報制御部140Aの情報記憶領域より素数「q」及び発行識別子情報「IDI」を読み出す。素数候補生成部142Aは、制御情報が「情報B」であるか否かを判断する。
「2×lenq」であると判断する場合には、素数候補生成部142Aは、生成した数「N」を第1素数判定部143Aへ出力し、生成した数「R」を生成情報記憶領域に記憶する。
「情報B」でないと判断する場合には、素数候補生成部142Aは、受け取った乱数「R1」と読み出した発行識別子情報「IDI」とを用いて、数「R=IDI×R1」を生成する。
素数候補生成部142Aは、読み出した素数「q」、発行識別子情報「IDI」、検証値「c1」及び生成した数「R」とを用いて、数「N=2×(R+w)×q+1」を生成する。
素数候補生成部142Aは、素数「q」のビットサイズ「lenq」を、情報制御部140Aの情報記憶領域より読み出し、生成した数「N」のビットサイズが「2×lenq」であるか否かを判断する。
「2×lenq」でないと判断する場合には、素数候補生成部142Aは、乱数生成部141Aより受け取った乱数「R1」に2を掛けて、その結果を「R1」として、再度、数「R」及び「N」を生成する。
第1素数判定部143Aは、第1の実施の形態にて示す第1素数判定部143と同様であるため、説明は省略する。
<第2素数判定部144A>
第2素数判定部144Aは、第1の実施の形態にて示す第2素数判定部144と同様であるため、説明は省略する。
発行公開鍵確認部214Aは、図示していないが、サーバ情報記憶領域220A及び確認情報記憶領域221Aを有している。
サーバ情報記憶領域220Aは、公開鍵証明書の発行依頼のあった鍵発行サーバを識別するサーバ識別子を記憶する領域を有している。
発行公開鍵確認部214Aは、受け取ったサーバ識別子を、サーバ情報記憶領域220Aに書き込む。
発行公開鍵確認部214Aは、受け取った公開鍵「PK」と発行識別子情報「IDI」とを用いて、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されたか否かを確認する。
発行公開鍵確認部214Aは、「n−(c1)^2」が、「IDI」で割り切れると判断する場合には、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されたと判断し、「n−(c1)^2」が、「IDI」で割り切れないと判断する場合には、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されていないと判断する。
発行公開鍵確認部214Aは、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されていないと判断する場合には、処理を終了する。
本変形例に係る素数候補生成処理について、第1実施の形態にて示した素数候補生成処理と異なる点のみ説明する。なお、鍵発行処理、及び素数生成処理の動作の流れは、第1の実施の形態と同様であるため、説明は省略する。
素数候補生成部142Aは、図16及び図17に示すステップS500からステップS560までを実行後、ステップS565を省略して、ステップS570にて、検証値「c1」を読み出す。素数候補生成部142Aは、ステップS575にて、数「N=2×(R+w)×q+1」を生成する。つまり、ステップS565、ステップS580及びステップS585を省略し、ステップS570及びステップS575を上記のように変更する。
つまり、本変形例に係る素数候補生成処理は、出力カウンタの値に関わらず、検証値「c1」と素数「q」と数「R」とを用いて、数「N」を生成することになる。
(4)証明書発行処理
本変形例に係る証明書発行処理について、第1実施の形態にて示した証明書発行処理と異なる点のみ説明する。
1.11 素数生成の変形例2
上記実施の形態では、第1検証値及び第2検証値の2つの検証値を用いたが、ここでは、1個の検証値であり、且つその検証値が固定値「1」である場合の素数の生成について、説明する。
(1)素数情報生成部133B
素数情報生成部133Bは、図21に示すように、情報制御部140B、乱数生成部141B、素数候補生成部142B、第1素数判定部143B及び第2素数判定部144Bから構成されている。
なお、以下の説明において、繰返制御部132から受け取る素数を素数「q」、そのビットサイズを「lenq」として、各構成要素について説明する。
<情報制御部140B>
情報制御部140Bは、第1情報及び第2情報を記憶するための情報記憶領域を有している。
情報制御部140Bは、繰返制御部132から、素数「q」と、素数のビットサイズ「lenq」と、制御情報とからなる第1情報を受け取ると、受け取った第1情報を情報記憶領域へ書き込む。つまり、素数「q」と、素数のビットサイズ「lenq」と、制御情報(この場合、「情報C」)とを書き込む。
情報制御部140Bは、第2素数判定部144Bより、素数を受け取ると、受け取った素数を繰返制御部132へ出力する。
<乱数生成部141B>
乱数生成部141Bは、第1の実施の形態にて示す乱数生成部141Bと同様であるため、説明は省略する。
素数候補生成部142Bは、生成された情報を記憶する生成情報記憶領域と、単射である関数「f」を予め記憶している関数記憶領域とを有している。
素数候補生成部142Bは、乱数生成部141Bより、乱数「R1」と制御情報とを受け取ると、受け取った制御情報が「情報C」であるか否かの判断をする。
制御情報が「情報C」でないと判断する場合には、素数候補生成部142Bは、情報制御部140Bの情報記憶領域より素数「q」及び発行識別子情報「IDI」を読み出す。素数候補生成部142Bは、制御情報が「情報B」であるか否かを判断する。
「2×lenq」であると判断する場合には、素数候補生成部142Bは、生成した数「N」を第1素数判定部143Bへ出力し、生成した数「R」を生成情報記憶領域に記憶する。
「情報B」でないと判断する場合には、素数候補生成部142Bは、受け取った乱数「R1」と読み出した発行識別子情報「IDI」とを用いて、数「R=IDI×R1」を生成する。
素数候補生成部142Bは、読み出した素数「q」、発行識別子情報「IDI」、検証値「1」及び生成した数「R」とを用いて、数「N=2×R×q+1」を生成する。ここで、最後の項の「1」が検証値である。
「2×lenq」であると判断する場合には、素数候補生成部142Bは、生成した数「N」を第1素数判定部143Bへ出力し、生成した数「R」を生成情報記憶領域に記憶する。
<第1素数判定部143B>
第1素数判定部143Bは、第1の実施の形態にて示す第1素数判定部143と同様であるため、説明は省略する。
第2素数判定部144Bは、第1の実施の形態にて示す第2素数判定部144と同様であるため、説明は省略する。
(2)発行公開鍵確認部214B
発行公開鍵確認部214Bは、図示していないが、サーバ情報記憶領域220B及び確認情報記憶領域221Bを有している。
確認情報記憶領域221Bは、固定値である検証値「1」を記憶している。
発行公開鍵確認部214Bは、鍵発行サーバ100から受信部217を介して、発行識別子情報「IDI」と、公開鍵「PK」と、サーバ識別子と、証明書発行依頼情報とを受け取る。
発行公開鍵確認部214Bは、検証値「1」を、確認情報記憶領域221Bから読み出す。
発行公開鍵確認部214Bは、受け取った公開鍵「PK」と発行識別子情報「IDI」とを用いて、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されたか否かを確認する。
発行公開鍵確認部214Bは、「n−1」が、「IDI」で割り切れると判断する場合には、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されたと判断し、「n−1」が、「IDI」で割り切れないと判断する場合には、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されていないと判断する。
発行公開鍵確認部214Bは、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されていないと判断する場合には、処理を終了する。
本変形例に係る素数候補生成処理について、第1実施の形態にて示した素数候補生成処理と異なる点のみ説明する。なお、鍵発行処理、及び素数生成処理の動作の流れは、第1の実施の形態と同様であるため、説明は省略する。
素数候補生成部142Bは、図16及び図17に示すステップS500からステップS560までを実行後、ステップS565を省略して、ステップS570にて、検証値「1」を読み出す。素数候補生成部142Bは、ステップS575にて、数「N=2×(R+w)×q+1」を生成する。つまり、ステップS565、ステップS580及びステップS585を省略し、ステップS570及びステップS575を上記のように変更する。なお、数「N」を算出する際の最後の項が検証値である。
つまり、本変形例に係る素数候補生成処理は、出力カウンタの値に関わらず、素数「q」と数「R」とを用いて、数「N」を生成することになる。
(4)証明書発行処理
本変形例に係る証明書発行処理について、第1実施の形態にて示した証明書発行処理と異なる点のみ説明する。
(5)確認方法の検証
上記に示した方法にて、証明書発行サーバは、鍵発行サーバが正しく発行識別子情報IDIを用いて生成しているかを確認することができる。
n=p1×p2=(2×q1×IDI×R11+1)×(2×q2×IDI×R12+1)
=IDI×(4×q1×q2×R11×R12×IDI+2×q1×R11+2×q2×R12)+1
となる。そのため、「n−1」は「IDI」で割り切れるため、「n−1」が「IDI」で割り切れることを確認することで、素数「p1」、「p2」が正しく発行識別子情報「IDI」を用いて生成しているかを確認することができる。
上記実施の形態では、256ビットの素数を生成する際に、単射関数を施して、生成する素数の一意性を満たし、512ビットの素数を生成する際に、生成する素数の正当性を確認するための要素を付加したが、ここでは、素数の一意性及び正当性を確認するための要素の付加を、1回の動作にて行う場合について、説明する。
また、ここでは、サーバ識別子のビットサイズを15ビット、端末装置の端末識別子のビットサイズを16ビットとし、発行識別子情報のビットサイズを32ビットする。
素数生成部116Cは、図22に示すように、繰返制御部132C及び素数情報生成部133Cとを有している。
素数生成部116Cは、8ビットの素数から512ビットの素数を生成し、生成した512ビットの素数を鍵判定部117へ出力する。
繰返制御部132Cは、8ビットからなる素数とその素数のビットサイズ(つまり「8」)とを予め記憶している初期値記憶領域と、素数情報生成部133Cから、受け取った素数を一時的に記憶する一時記憶領域とを有している。
繰返制御部132Cは、素数情報生成部133Cの動作の繰返回数をカウントする繰返カウンタ135Cと、鍵判定部117へ出力した素数の個数、つまり生成した512ビットの素数の出力回数をカウントする出力カウンタ136Cとを有している。なお、繰返カウンタ135C及び出力カウンタ136Cの初期値は、それぞれ「1」である。
繰返制御部132Cは、識別子生成部115から素数の生成開始命令を受け取ると、素数情報生成部133Cが素数を生成するよう制御する。素数情報生成部133Cから素数を受け取ると、繰返カウンタ135C及び出力カウンタ136Cのそれぞれの値に基づいて、再度、素数情報生成部133Cへ素数生成の命令、及び受け取った素数を鍵判定部117へ出力の何れかを行う。
繰返制御部132Cは、識別子生成部115から素数の生成開始命令を受け取ると、繰返カウンタ135C及び出力カウンタ136Cを、それぞれ「1」に設定する。
繰返制御部132Cは、素数情報生成部133Cから、素数を受け取ると、繰返カウンタ135Cの値に「1」を加算し、加算結果が、7であるか否かを判断する。
繰返制御部132Cは、素数の生成開始命令を受け取り、繰返カウンタ135C及び出力カウンタ136Cのそれぞれの値に「1」を加算した後、素数情報生成部133Cから受け取った素数とそのビットサイズとを一時的に記憶した後、及び出力カウンタ136Cに「1」を加算し、且つ繰返カウンタ135Cの値を「1」に設定した後の何れかの場合において、繰返制御部132Cは、以下の動作を行う。
「情報C」であると判断する場合には、繰返制御部132Cは、読み出した素数及びそのビットサイズと、制御情報とからなる第1情報を生成し、生成した第1情報を、素数情報生成部133Cへ出力する。
<素数情報生成部133C>
素数情報生成部133Cは、図24に示すように、情報制御部140C、乱数生成部141C、素数候補生成部142C、第1素数判定部143C及び第2素数判定部144Cから構成されている。
なお、以下の説明において、繰返制御部132Cから受け取る素数を素数「q」、そのビットサイズを「lenq」として、各構成要素について説明する。
情報制御部140Cは、第1情報及び第2情報を記憶するための情報記憶領域を有している。
情報制御部140Cは、証明書発行サーバ200により割り当てられ、且つ制御情報「情報AB」に基づいて素数を生成する際に用いる素数「qg」とそのビットサイズ「lenqg」とを予め記憶している割当素数記憶領域を有している。ここで、素数「qg」のビットサイズは、例えば、「64」ビットである。
情報制御部140Cは、繰返制御部132Cから、素数「q」と、素数のビットサイズ「lenq」と、制御情報と、発行識別子情報「IDI」と、そのビットサイズ「lenIDI」とからなる第2情報を受け取ると、受け取った第2情報を情報記憶領域へ書き込む。つまり、素数「q」と、素数のビットサイズ「lenq」と、制御情報、発行識別子情報「IDI」と、そのビットサイズ「lenIDI」とを書き込む。
情報制御部140Cは、第2素数判定部144Cより、素数を受け取ると、受け取った素数を繰返制御部132Cへ出力する。
情報制御部140Cは、素数候補生成部142Cから出力カウンタ136Cの値を読み出す旨の回数読出命令を受け取ると、繰返制御部132Cの出力カウンタ136Cの値を読み出す。情報制御部140Cは、読み出した値を、素数候補生成部142Cへ出力する。
乱数生成部141Cは、乱数の生成の指示を示す第1生成指示を、情報制御部140Cから受け取ると、情報制御部140Cの情報記憶領域にて記憶されている制御情報を読み出す。乱数生成部141Cは、読み出した制御情報が「情報C」であるか否かを判断する。
<素数候補生成部142C>
素数候補生成部142Cは、生成された情報を記憶する生成情報記憶領域と、発行識別子情報「IDI」と素数「qg」とから一意的に素数を生成する素数生成関数「gp」、及び単射である関数「f」を予め記憶している関数記憶領域とを有している。
先ず、「c=0」として、「2×qg×f(IDI||c)+1」が素数であるかを判定する。素数である場合は、「gp(IDI,qg)=2×qg×f(IDI||c)+1」とする。素数でなければ、「c」に「1」加算して、「2×qg×f(IDI||c)+1」が素数であるかを判定する。素数であれば、「gp(IDI,qg)=2×qg×f(IDI||c)+1」とする。素数でなければ、「c」に「1」加算して同様の判定を行い素数になるまで繰り返す。このように関数「gp」を定義するとき、関数「qg」と「f」とを保持していれば、発行識別子情報「IDI」に対して、素数候補生成部142Cは、何回素数生成関数により素数を生成しても、同じ素数を生成するができる。このとき、「IDI」のビットサイズ及び「qg」のビットサイズが、それぞれ「32」ビット及び「64」ビットである場合には、「gp(IDI、qg)」のビットサイズは、128ビットとなる。
「情報C」であると判断する場合には、素数候補生成部142Cは、情報制御部140Cの情報記憶領域より素数「q」を読み出す。素数候補生成部142Cは、読み出した素数「q」と乱数生成部141Cより受け取った乱数「R1」とを用いて、数「N=2×R1×q+1」を生成する。素数候補生成部142Cは、生成した数「N」のビットサイズ「lenN」が「lenq」と一致するか否かを判断し、一致すると判断する場合には、素数候補生成部142Cは、生成した数「N」を第1素数判定部143Cへ出力し、受け取った乱数「R1」を、「R」として生成情報記憶領域に記憶する。
制御情報が「情報C」でないと判断する場合、つまり制御情報が「情報AB」であると判断する場合には、素数候補生成部142Cは、情報制御部140Cの情報記憶領域より素数「q」及び発行識別子情報「IDI」を、割当素数記憶領域より素数「qg」を、それぞれ読み出す。
素数候補生成部142Cは、生成情報記憶領域にて記憶している素数「pIDI」を読み出し、読み出した素数「pIDI」と、受け取った乱数「R1」と、読み出した素数「q」とを用いて、数「N=2×R1×q×pIDI+1」を生成する。
「2×lenq」であると判断する場合には、素数候補生成部142Cは、生成した数「N」を第1素数判定部143Cへ出力し、受け取った乱数「R1」を「R」として生成情報記憶領域に記憶する。
<第1素数判定部143C>
第1素数判定部143Cは、第1の実施の形態にて示す第1素数判定部143と同様であるため、説明は省略する。
第2素数判定部144Cは、第1の実施の形態にて示す第1素数判定部144と同様であるため、説明は省略する。
(2)発行公開鍵確認部214C
発行公開鍵確認部214Cは、図示していないが、サーバ情報記憶領域220C及び確認情報記憶領域221Cを有している。
確認情報記憶領域221Cは、鍵発行サーバ100に割り当てた素数「qg」とそのビットサイズ「lenqg」と、鍵発行サーバ100にて記憶している素数生成関数及び単射関数のそれぞれと同様の関数「gp」及び「f」を予め記憶している。
発行公開鍵確認部214Cは、受け取ったサーバ識別子を、サーバ情報記憶領域220Cに書き込む。
以下に、確認方法を示す。先ず、発行公開鍵確認部214Cは、受け取った発行識別子情報「IDI」と、記憶している素数「qg」、関数「gp」及び「f」とを用いて、素数「gp(IDI、qg)」を生成し、生成した素数素数「gp(IDI、qg)」を確認情報記憶領域221Cへ書き込む。素数「gp(IDI、qg)」の生成方法は、上記に示す方法と同様であるため、説明は省略する。このとき、発行公開鍵確認部214Cにて生成される素数「gp(IDI、qg)」は、鍵発行サーバの素数候補生成部142Cにて生成される素数「pIDI」と同じであることが分かる。
発行公開鍵確認部214Cは、「n−1」が、素数「gp(IDI、qg)」で割り切れると判断する場合には、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されたと判断し、「n−1」が、素数「gp(IDI、qg)」で割り切れないと判断する場合には、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されていないと判断する。
発行公開鍵確認部214Cは、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されていないと判断する場合には、処理を終了する。
本変形例に係る素数生成処理について、第1実施の形態にて示した素数生成処理と異なる点のみ説明する。なお、鍵発行処理の動作の流れは、第1の実施の形態と同様であるため、説明は省略する。
図15に示す素数生成処理のステップS425において、乱数生成部141Cは、乱数生成部141Cは、情報制御部140Cの情報記憶領域にて記憶されている「lenq」を、割当素数記憶領域にて記憶されている「lenqg」を、それぞれ読み出すように変更する。次に、ステップS430において、乱数生成部141Cは、読み出した「lenq」及び「lenqg」を用いて、(lenq−2×lenqg−1)ビットからなる乱数「R1」を生成し、生成した乱数「R1」と読み出した制御情報とを素数候補生成部142Cへ出力するように変更する。ここで、乱数「R1」の最上位ビットは1とする。
本変形例に係る素数候補生成処理について、図25に示す流れ図を用いて説明する。
素数候補生成部142Cは、乱数生成部141Cより、乱数「R1」と制御情報とを受け取ると(ステップS700)、受け取った制御情報が「情報C」であるか否かの判断をする(ステップS705)。
制御情報が「情報C」でないと判断する場合(ステップS705における「NO」)、つまり制御情報が「情報AB」であると判断する場合には、素数候補生成部142Cは、情報制御部140Cの情報記憶領域より素数「q」及び発行識別子情報「IDI」を、割当素数記憶領域より素数「qg」を、それぞれ読み出す(ステップS730)。
素数候補生成部142Cは、生成情報記憶領域にて記憶している素数「pIDI」を読み出し、読み出した素数「pIDI」と、読み出した素数「q」と、生成した素数「pIDI」とを用いて、数「N=2×R1×q×pIDI+1」を生成する(ステップS740)。
「2×lenq」であると判断する場合には(ステップS745における「YES」)、素数候補生成部142Cは、生成した数「N」を第1素数判定部143Cへ出力し、乱数「R1」を「R」として生成情報記憶領域に記憶する(ステップS755)。
(5)証明書発行処理
本変形例に係る証明書発行処理について、第1実施の形態にて示した証明書発行処理と異なる点のみ説明する。
上記と同様の証明により、素数生成部116Cにて生成される素数の一意性は満たされる。つまり、端末装置ごとに、異なる発行識別子情報が生成されるため、素数生成に用いる関数「f」の単射の性質により、生成される素数も異なる。これにより、端末装置毎に、異なる秘密鍵及びそれに対応する公開鍵を割り当てることができる。
なぜなら、秘密鍵である素数「p1」、「p2」はそれぞれ、素数「q1」、「q2」、乱数「R11」、「R12」、及び素数「pIDI=gp(IDI、qg)」を用いて、「p1=2×q1×pIDI×R11+1」、「p2=2×q2×pIDI×R12+1」を満たすため、
n=p1×p2=(2×q1×pIDI×R11+1)×(2×q2×pIDI×R12+1)
=pIDI×(4×q1×q2×R11×R12×pIDI+2×q1×R11+2×q2×R12)+1
となる。そのため、「n−1」は「pIDI」で割り切れるため、「n−1」が「pIDI」で割り切れることを確認することで、素数「p1」、「p2」が正しく発行識別子情報「IDI」を用いて生成しているかを確認することができる。
本発明は、上記の実施の形態に限定されないのはもちろんである。以下のような場合も本発明に含まれる。
上記の変形例では、予め1個の素数「qg」を記憶しているとしたが、これに限定されない。鍵発行サーバは、予め2つの素数「qg1」、「qg2」を記憶しておき、素数「p1」を生成する場合に、素数「qg1」を用い、素数「p2」を生成する場合に、素数「qg2」を用いてもよい。
本発明に係る第2の実施の形態としての鍵発行システム2について、第1の実施の形態における鍵発行システム1と異なる点を中心に説明する。
2.1 鍵発行システム2の概要
鍵発行システム2は、図26に示すように、鍵発行サーバ1100、1101、1102と、鍵発行監査サーバ1200と、端末装置1300、1301、・・・、1302、1303、・・・、1304、1305、・・・、1306から構成されている。端末装置の台数は、例えば1000台である。
なお、以下においては、鍵発行サーバ1100、鍵発行監査サーバ1200、及び端末装置1300を用いて、鍵発行システム2の概要を説明する。
鍵発行サーバ1100は、端末装置1300より鍵の発行要求を受け取ると、RSA暗号における秘密鍵及び公開鍵を生成する。さらに、鍵発行サーバ1100は、生成した公開鍵に対する公開鍵証明書を生成し、生成した公開鍵証明書及び秘密鍵を、端末装置1300へ送信する。なお、ここで、生成する各鍵の鍵長は、1024ビットとする。
鍵発行監査サーバ1200は、鍵発行サーバ1100より発行済公開鍵情報を受け取ると、発行された公開鍵の正当性を監査し、監査結果を表示する。
以降、例えば、端末装置1400のユーザは、先ず、鍵発行サーバ1100より、端末装置1300の公開鍵証明書を入手、又は端末装置1300より公開鍵証明書を入手し、鍵発行サーバ1100が有し、公開鍵証明書の正当性を確認する際に用いる証明書用公開鍵「C_PK」を用いて、公開鍵証明書の正当性を確認し、正当な公開鍵証明書であると判断する場合に、入手した公開鍵証明書を、端末装置1400にて記憶する。端末装置1400は、記憶している公開鍵証明書に含まれる公開鍵を用いて、端末装置1300へ送信する電子メールを暗号化して、暗号化された電子メールを端末装置1300へ送信する。
これにより、端末装置1300と端末装置1400との間では、安全にデータのやりとりができるようになる。
以降の説明において、各端末装置の代表として端末装置1300を、各鍵発行サーバの代表として鍵発行サーバ1100を用いる。
鍵発行サーバ1100は、図27にて示すように、識別子格納部1110、秘密鍵格納部1111、公開鍵格納部1112、証明書格納部1113、制御部1114、識別子生成部1115、素数生成部1116、鍵判定部1117、鍵生成部1118、情報取得部1119、受信部1120、送信部1121、証明書生成部1122、証明書用秘密鍵格納部1123及び発行済鍵情報格納部1124から構成されている。
(1)識別子格納部1110
識別子格納部1110は、第1の実施の形態における識別子格納部1110と同様に、ビットサイズが126ビット以下である発行識別子情報を記憶するための領域を有している。発行識別子情報のビットサイズは、例えば、64ビットである。
秘密鍵格納部1111は、第1の実施の形態における秘密鍵格納部1111と同様に、素数格納領域と秘密鍵格納領域とを有している。
(3)公開鍵格納部1112
公開鍵格納部1112は、第1の実施の形態における公開鍵格納部112と同様に、公開鍵を記憶するための領域を有している。
証明書格納部1113は、当該サーバにて生成した証明書発行サーバにて発行された公開鍵証明書を記憶する領域を有している。
(5)証明書用秘密鍵格納部1123
証明書用秘密鍵格納部1123は、公開鍵証明書を生成する際に用いられる証明書用秘密鍵「C_SK」を、予め記憶している。
制御部1114は、図27に示すように、サーバ識別子記憶領域1130と、端末情報記憶領域1131とを有している。
サーバ識別子記憶領域1130は、当該サーバを識別するサーバ識別子を予め記憶している。例えば、鍵発行サーバ1100は、SIDAを、鍵発行サーバ1101は、SIDBを、鍵発行サーバ1102は、SIDCを記憶している。なお、以降では、鍵発行サーバ1100のサーバサーバ識別子を「SID」として説明する。ここでは、サーバ識別子のビットサイズを31ビットとする。
制御部1114は、端末装置1300から受信部1120を介して、鍵発行依頼情報と、端末装置1300の端末識別子「TID」とを受け取ると、受け取った端末識別子「TID」を端末情報記憶領域1131へ書き込む。制御部1114は、発行識別子情報の生成命令と、受け取った端末識別子「TID」とを識別子生成部1115へ出力する。
(7)識別子生成部1115
識別子生成部1115は、第1の実施の形態における識別子生成部115と同様であるため、説明は省略する。
素数生成部1116は、第1の実施の形態における素数生成部116の素数の生成方法と同様の方法にて、512ビットの素数を生成する。
(9)鍵判定部1117
鍵判定部1117は、第1の実施の形態における鍵判定部117と同様であるため、説明は省略する。
鍵生成部1118は、鍵判定部1117より鍵生成命令を受け取ると、秘密鍵格納部111の素数記憶領域にて記憶されている2つの素数「p1」及び「p2」を読み出し、読み出した素数「p1」と「p2」との積「n=p1×p2」を計算する。
鍵生成部118は、乱数「e」を生成し、算出した「n」と、生成した乱数「e」とからなる組「PK=(n、e)」を公開鍵として生成し、生成した公開鍵「PK」を公開鍵格納部112へ書き込む。ここで、乱数「e」は、従来と同様に、乱数「e」は、数「L」と互いに素であり、「1≦e≦L−1、GCD(e、L)=1」を満たす。ここで、GCD(e、L)は、eとLの最大公約数を示し、数「L」は、「L=LCM(p1−1、p2−1)」であり、LCM(p1−1、p2−1)は、「p1−1」と「p2−1」との最小公倍数を示す。
(11)証明書生成部1122
証明書生成部1122は、鍵生成部1118より公開鍵証明書の生成命令を受け取ると、証明書用秘密鍵格納部より証明書用秘密鍵「C_SK」を、公開鍵格納部1112より公開鍵「PK」を、識別子格納部1110より発行識別子情報「IDI」を、それぞれ読み出す。
(12)情報取得部1119
情報取得部1119は、証明書生成部1122から配布開始命令を受け取ると、秘密鍵格納部1111にて記憶している秘密鍵「SK」と、証明書格納部1113にて記憶している公開鍵証明書「Cert」と、制御部1114の端末情報記憶領域1131にて記憶している端末識別子とを、それぞれ読み出し、読み出した秘密鍵「SK」及び公開鍵証明書「Cert」を、読み出した端末識別子に対応する端末装置1300へ送信部1121を介して送信する。
発行済鍵情報格納部1124は、図28に示すように、発行済鍵情報テーブルT1100を有している。
発行済鍵情報テーブルT1100は、発行済公開鍵と、発行済識別子情報とからなる組を1以上記憶するための領域を有している。
上記により、鍵発行サーバ1100は、発行した公開鍵と、発行した発行識別子情報とを蓄積していくことができる。
(14)受信部1120
受信部1120は、鍵発行監査サーバ1200及び端末装置1300より情報を受信し、受信した情報を、制御部1114へ出力する。
送信部1121は、情報取得部1119より、秘密鍵「SK」及び公開鍵証明書「Cert」を受け取り、受け取った各情報を、端末装置1300に送信する。
送信部1121は、情報取得部1119より、1以上の発行済鍵情報とサーバ識別子とを受け取ると、受け取った1以上の発行済鍵情報とサーバ識別子とを鍵発行監査サーバ1200へ送信する。
鍵発行監査サーバ1200は、図29に示すように、確認情報格納部1210、発行済鍵情報格納部1211、制御部1212、発行公開鍵確認部1213、受付部1214、監査結果出力部1215、受信部1216及び送信部1217から構成されている。
鍵発行監査サーバ1200は、具体的には、マイクロプロセッサ、ROM、RAM、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記RAM又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、鍵発行監査サーバ1200は、その機能を達成する。
(1)確認情報格納部1210
確認情報格納部1210は、図30に示すように、検証値テーブルT1200を有している。検証値テーブルT1200は、サーバ識別子と、第1検証値と、第2検証値とからなる組を1以上記憶する領域を有している。サーバ識別子は、鍵発行サーバを識別する識別子であり、「SIDA」は、鍵発行サーバ1100を示し、「SIDB」は、鍵発行サーバ1101を示し、「SIDB」は、鍵発行サーバ1102を示す。第1検証値及び第2検証値は、対応付けられたサーバ識別子にて示される鍵発行サーバに割り当てた検証値である。なお、以降では、鍵発行サーバ1100のサーバ識別子を「SID」として説明する。
発行済鍵情報格納部1211は、鍵発行サーバ1100より送信された1以上の発行済鍵情報を記憶するための領域を有している。
(3)制御部1212
制御部1212は、図29に示すように、サーバ情報記憶領域1220を有している。
制御部1212は、受付部1214より、公開鍵の監査を開始する監査開始命令と、監査対象のサーバ識別子(ここでは、「SID」とする。)を受け付けると、発行済鍵依頼情報を、送信部1217を介してサーバ識別子に対応する鍵発行サーバ1100へ送信する。
制御部1212は、鍵発行サーバ1100から受信部217を介して、1以上の発行済鍵情報とサーバ識別子とを受け取る。
制御部1212は、受け取ったサーバ識別子と、サーバ情報記憶領域にて記憶しているサーバ識別子とが一致するか否かを判断する。
一致しないと判断する場合には、制御部1212は、処理を終了する。
(4)発行公開鍵確認部1213
発行公開鍵確認部1213は、制御部1212より監査開始命令とサーバ識別子とを受け取ると、受け取ったサーバ識別子を用いて、対応する第1検証値「c11」及び第2検証値「c12」を、確認情報格納部1210から読み出す。
発行公開鍵確認部1213は、読み出した発行済鍵情報に含まれる公開鍵「PK」と発行識別子情報「IDI」と、第1検証値「c11」及び第2検証値「c12」とを用いて、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されたか否かを確認する。
発行公開鍵確認部1213は、「n−(c11×c12)」が、「IDI」で割り切れると判断する場合には、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されたと判断し、「n−(c11×c12)」が、「IDI」で割り切れないと判断する場合には、公開鍵「PK」が、発行識別子情報「IDI」を用いて生成されていないと判断し、読み出した発行識別子情報「IDI」を一時的に記憶する。
一時的に記憶している発行識別子情報が存在すると判断する場合には、発行公開鍵確認部1213は、記憶されている全ての発行識別子を連結し、不正発行識別子情報群を生成し、生成した不正発行識別子情報群を監査結果出力部1215へ出力する。
(5)受付部1214
受付部1214は、ユーザの操作により、監査を開始する指示と、監査対象の鍵発行サーバのサーバ識別子とを受け付けると、監査開始命令と、サーバ識別子を制御部1212へ出力する。
監査結果出力部1215は、発行公開鍵確認部1213から不正発行識別子情報群を受け取ると、受け取った不正発行識別子情報群をモニタ1250へ出力する。
監査結果出力部1215は、発行公開鍵確認部1213から正当メッセージを受け取ると、受け取った正当メッセージをモニタ1250へ出力する。
(7)受信部1216
受信部1216は、鍵発行サーバ1100より、1以上の発行済鍵情報と、サーバ識別子とを受信すると、受信した1以上の発行済鍵情報と、サーバ識別子とを制御部1212へ出力する。
送信部1217は、制御部1212より、発行済鍵依頼情報を受け取ると、受け取った発行済鍵依頼情報を鍵発行サーバ1100へ送信する。
2.4 端末装置1300の構成
端末装置1300は、第1の実施の形態における端末装置300と同様であるため、説明は省略する。
2.5 鍵発行システム2の動作
ここでは、鍵発行システム2の動作について説明する。
(1)鍵発行システム2の動作概要
ここでは、鍵発行システム2の動作概要を説明する。
以降の説明において、1以上の発行済鍵情報を発行済鍵情報群として、記述する。
<鍵発行時の動作概要>
鍵発行時の動作概要を図31に示す流れ図を用いて、説明する。
鍵発行サーバ1100は、鍵発行依頼情報と、端末識別子「TID」とを、端末装置1300より受信すると、鍵発行処理にて秘密鍵及び公開鍵を生成し(ステップS1005)、証明書発行処理により、ステップS1005にて生成した公開鍵に対する公開鍵証明書を発行し、発行した公開鍵証明書と、ステップS1005にて生成した秘密鍵とを、端末装置1300へ送信する(ステップS1010)
端末装置1300は、鍵発行サーバ1100より、秘密鍵「SK」及び公開鍵証明書「Cert」を受信すると、受信した秘密鍵「SK」、及び公開鍵証明書「Cert」を記憶する(ステップS1015)。
鍵の監査時の動作概要を図32に示す流れ図を用いて、説明する。
鍵発行監査サーバ1200は、監査処理にて、発行済鍵依頼情報を鍵発行サーバ1100へ送信する(ステップS1050)。
鍵発行サーバ1100は、鍵情報取得処理にて取得した発行済鍵情報群と、サーバ識別子とを鍵発行監査サーバ1200へ送信する(ステップS1055)。
ここでは、図31に示す鍵発行処理の動作について、第1の実施の形態にて示す鍵発行処理との異なる点のみを、図11、図12、図13及び図14に示す流れ図を用いて、説明する。
本実施の形態に係る鍵発行処理は、図11、図12及び図13に示すステップS200からステップS325まで実行する。
本実施の形態に係る鍵発行処理は、変更後のステップS330を実行すると、処理を終了する。
ここでは、図31に示す鍵発行処理の動作について、図33に示す流れ図を用いて、説明する。
証明書生成部1122は、鍵生成部1118より公開鍵証明書の生成命令を受け取ると、証明書用秘密鍵格納部より証明書用秘密鍵「C_SK」を、公開鍵格納部1112より公開鍵「PK」を、識別子格納部1110より発行識別子情報「IDI」を、それぞれ読み出す(ステップS1100)。
情報取得部1119は、証明書生成部1122から配布開始命令を受け取ると、秘密鍵格納部1111にて記憶している秘密鍵「SK」と、証明書格納部1113にて記憶している公開鍵証明書「Cert」と、制御部1114の端末情報記憶領域にて記憶している端末識別子とを、それぞれ読み出し、読み出した秘密鍵「SK」及び公開鍵証明書「Cert」を、読み出した端末識別子に対応する端末装置1300へ送信部1121を介して送信する(ステップS1110)。
(4)鍵情報取得処理
ここでは、図32に示す鍵情報取得処理の動作について、図34に示す流れ図を用いて、説明する。
鍵発行サーバ1100の情報取得部1119は、制御部1114から鍵情報取得命令を受け取ると、発行済鍵情報格納部1124より、全ての発行済鍵情報を読み出す(ステップS1205)。
(5)監査処理
ここでは、図32に示す監査処理の動作について、図35に示す流れ図を用いて、説明する。
制御部1212は、受付部1214より、公開鍵の監査を開始する監査開始命令と、監査対象のサーバ識別子(ここでは、「SID」とする。)を受け付けると、発行済鍵依頼情報を、送信部1217を介してサーバ識別子に対応する鍵発行サーバ1100へ送信する(ステップS1305)。
制御部1212は、鍵発行サーバ1100から受信部217を介して、1以上の発行済鍵情報とサーバ識別子とを受け取る(ステップS1315)。
制御部1212は、受け取ったサーバ識別子と、サーバ情報記憶領域にて記憶しているサーバ識別子とが一致するか否かを判断する(ステップS1320)。
発行公開鍵確認部1213は、確認処理において、公開鍵の正当性の確認を行い、結果をモニタ1250にて表示する。
(6)確認処理
ここでは、図35に示す確認処理の動作について、図36に示す流れ図を用いて、説明する。
発行公開鍵確認部1213は、発行済鍵情報格納部1211から、未読の発行済鍵情報を1つ読み出す(ステップS1405)。
発行公開鍵確認部1213は、「n−(c11×c12)」が、「IDI」で割り切れると判断する場合、つまり公開鍵が正当であると判断する場合には(ステップS1410における「YES」)、ステップS1415を省略する。
未読の発行済鍵情報が存在しないと判断する場合には(ステップS1420における「NO」)、一時的に記憶している発行識別子情報が存在するか否かを判断する(ステップS1425)。
一時的に記憶している発行識別子情報が存在しないと判断する場合には(ステップS1425における「NO」)、発行公開鍵確認部1213は、全ての公開鍵の正当性が確認されたことを示す旨の正当メッセージを、監査結果出力部1215を介して、モニタ1250にて表示する(ステップS1435)。
上記の第1の実施の形態にて示す鍵発行サーバ100の素数生成部116の素数情報生成部133は、図37に示す動作を繰り返すことにより、8ビットの素数から512ビットの素数を生成する。
素数情報生成部133は、8ビットの素数から16ビットの素数を生成し(ステップS1700)、生成した16ビットの素数から32ビットの素数を生成し(ステップS1705)、以降順に、32ビットの素数から64ビットの素数、64ビットの素数から128ビットの素数、128ビットの素数から256ビットの素数を生成し(ステップS1710、S1715、及びS1720)、最後に、生成した256ビットの素数から516ビットの素数を生成する(ステップS1725)。
素数生成部116は、ステップS1720においては、制御情報「情報B」により、生成される素数が、発行識別子情報「IDI」に対して一意となるように、単射の関数「f」を用いて256ビットの素数を生成する。
これにより、鍵発行サーバ100は、単射関数「f」を用いることにより、端末装置毎に異なる秘密鍵及び公開鍵を生成することができる。また、鍵発行サーバ100にて、256ビットの素数から512ビットの素数を生成する際に、生成される素数に、発行識別子情報「IDI」が埋め込まれているため、証明書発行サーバ200は、生成された公開鍵と発行識別子情報とを用いて、公開鍵の正当性を確認することができる。
上記第1の実施の形態によると、鍵発行サーバ100が、生成する素数に発行識別子情報「IDI」を埋め込むことにより、証明書発行サーバ200は、正しく鍵発行しているかを発行識別子情報「IDI」で割り切れるかをチェックすることで確認できる。
3.1 変形例
本発明を上記の第1、第2実施の形態及び素数生成の変形例1、2、3に基づいて説明してきたが、本発明は、上記の実施の形態に限定されないのはもちろんである。以下のような場合も本発明に含まれる。
例えば、8ビットの素数から16ビットの素数を生成する際に、単射関数を施してもよい。または、16ビットの素数から32ビットの素数を生成する際に、単射関数を施してもよい。または、32ビットの素数から64ビットの素数を生成する際に、単射関数を施してもよい。または、64ビットの素数から128ビットの素数を生成する際に、単射関数を施してもよい。
(3)第1の実施の形態における素数生成部116を、1つの素数生成装置としてもよい。このとき、素数生成装置は、発行識別子情報「IDI」とそのビットサイズ「lenIDI」が与えられた場合、与えられた「IDI」及びそのビットサイズ「lenIDI」と、予め記憶されている8ビットの素数とから、512ビットの素数を生成する。
(4)第1の実施の形態における素数生成部116を、予め記憶している8ビットの素数から128ビットの素数を生成する第1素数生成部と、128ビットの素数から512ビットの素数を生成する第2素数生成部とからなるとしてもよい。また、第1素数生成部及び第2素数生成部を、それぞれ個別の素数生成装置としてもよい。
以下に、第2素数生成部の構成の一例を、図38に示す。ここでは、第2素数生成部を1つの素数生成装置2100として説明する。素数生成装置2100は、素数「q1」と、そのビットサイズ「lenq1」(ここでは、ビットサイズを128ビットとする。)と、発行識別子情報「IDI」と、そのビットサイズ「lenIDI」とが与えられた場合に、(4×lenq1)ビットからなる素数「N」を出力する。なお、ここで示す素数生成装置2100は、第1の実施の形態にて示す第1及び第2検証値を用いないで、素数「N」を生成する。
素数生成装置2100は、具体的には、マイクロプロセッサ、ROM、RAM、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記RAM又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、素数生成装置2100は、その機能を達成する。
受付情報記憶部2102は、素数「N」を生成する際に与えられた素数「q1」、素数「q1」のビットサイズ「lenq1」、発行識別子情報「IDI」及び発行識別子情報のビットサイズ「lenIDI」を記憶する領域を備えている。
<受付部2101>
受付部2101は、素数「q1」、素数「q1」のビットサイズ「lenq1(例えば、128ビット)」、発行識別子情報「IDI」及び発行識別子情報のビットサイズ「lenIDI」を、外部(例えば、上記に示す第1素数生成部)より受け付け、受け付けた素数「q1」、そのビットサイズ「lenq1」、発行識別子情報「IDI」及びそのビットサイズ「lenIDI」を受付情報記憶部2102へ書き込む。
<素数シード生成部2103>
素数シード生成部2103は、上記第1の実施の形態にて示す素数生成部116において、制御情報装が「情報B」の場合に行う動作と同様の動作を行うので、ここでの説明は省略する。なお、ここでは、128ビットの素数「q1」から256ビットの素数「q2」を生成するものとする。
<乱数生成部2104>
乱数生成部2104は、第1生成指示を、素数候補生成部2105から受け取ると、素数「q1」のビットサイズ「lenq1」と、発行識別子情報「IDI」のビットサイズ「lenIDI」とを、受付情報記憶部2102より読み出す。
乱数生成部2104は、生成した乱数「R1」を素数候補生成部2105へ出力する。
また、乱数生成部2104は、第1素数判定部2106及び第2素数判定部2107の何れかから、再度乱数を生成する旨の第2生成指示を受け付けると、各ビットサイズを読み出し、上記の動作を行う。
素数候補生成部2105は、生成された数を記憶する生成情報記憶領域とを有している。
素数候補生成部2105は、素数シード生成部2103より素数「q2」を受け取ると、第1生成指示を乱数生成部2104へ出力する。
素数候補生成部2105は、素数シード生成部2103より受け取った素数「q2」、受付情報記憶部2102より読み出した発行識別子情報「IDI」及び乱数生成部2104より受け取った乱数「R1」とを用いて、数「R=IDI×R1」と、数「N=2×R×q2+1」とを生成する。
「4×lenq1」であると判断する場合には、素数候補生成部2105は、生成した数「N」を第1素数判定部2106へ出力し、生成した数「R」を生成情報記憶領域に記憶する。
素数候補生成部2105は、数「N」のビットサイズが、「4×lenq1」となるまで、上記の動作を繰り返す。
第1素数判定部2106は、第1の実施の形態にて示す第1素数判定部143と同様の動作であるため、ここでの説明は省略する。
<第2素数判定部2107>
第2素数判定部2107は、第1の実施の形態にて示す第2素数判定部144と同様の動作であるため、ここでの説明は省略する。
<素数生成装置2100の動作>
以下に、素数生成装置2100の動作について説明する。
(素数生成処理)
ここでは、素数生成装置2100にて行われる素数生成処理について、図39に示す流れ図を用いて、説明する。
素数生成装置2100は、素数シード生成部2103において、ステップS2000にて受け付けた各情報を用いて、素数「q2」を生成する(ステップS2005)。
素数生成装置2100は、素数候補生成部2105において、ステップS2000にて受け付けられた発行識別子情報「IDI」、ステップS2005にて生成された素数「q2」及びステップS2010にて生成された乱数「R1」とを用いて、素数候補生成処理を施すことにより、数「R」及び「N」を生成する(ステップS2015)。素数生成装置2100は、第1素数判定部2106において、ステップS2015にて生成した数「N」を用いて、上記に示す式(eq1)が成立するか否かを判定する(ステップS2020)。
式(eq2)が成立していると判断する場合には(ステップS2025における「YES」)、素数生成装置2100は、数「N」を素数「N」として出力し、処理を終了する(ステップS2030)。
(素数候補生成処理)
ここでは、素数生成処理のステップS2015にて行われる素数候補生成処理について、図40に示す流れ図を用いて説明する。
素数候補生成部2105は、素数生成処理のステップS2005にて生成された素数「q2」と、ステップS2050にて生成された数「R」とを用いて、数「N」を生成する(ステップS2055)。ここで、数「N」は、「N=2×R×q2+1」である。
「4×lenq1」であると判断する場合には(ステップS2060における「YES」)、処理を終了する。「4×lenq1」でないと判断する場合には(ステップS2060における「NO」)、素数生成処理のステップS2010にて生成した乱数「R1」に2を掛けて、その結果を「R1」として、ステップS2050へ戻る(ステップS2065)。
ここでは、生成する秘密鍵である素数のビットサイズは512ビットとしているが、これに限定されない。1024ビットであっても、2048ビットであってもよい。また、上記の第1素数生成部で生成する素数も同様に128ビットに限らない。
(5)上記に示す素数シード生成部2103を1つの素数生成装置としてもよい。以下に、この場合の素数生成装置2200について、説明する。素数生成装置2200は、素数「q」と、そのビットサイズ「lenq」(ここでは、ビットサイズを128ビットとする。)と、発行識別子情報「IDI」と、そのビットサイズ「lenIDI」とが与えられた場合に、(2×lenq)ビットからなる素数「N」を出力する。
素数生成装置2200は、具体的には、マイクロプロセッサ、ROM、RAM、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記RAM又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、素数生成装置2200は、その機能を達成する。
受付情報記憶部2202は、素数「N」を生成する際に与えられた素数「q」、素数「q」のビットサイズ「lenq」、発行識別子情報「IDI」及び発行識別子情報のビットサイズ「lenIDI」を記憶する領域を備えている。
<受付部2201>
受付部2201は、素数「q」、素数「q」のビットサイズ「lenq」、発行識別子情報「IDI」及び発行識別子情報のビットサイズ「lenIDI」を、外部(例えば、上記に示す第1素数生成部)より受け付け、受付部2201は、受け付けた素数「q」、そのビットサイズ「lenq」、発行識別子情報「IDI」及びそのビットサイズ「lenIDI」を受付情報記憶部2202へ書き込む。
<乱数生成部2203>
乱数生成部2203は、乱数を生成する旨の第1生成指示を、素数候補生成部2204から受け取ると、素数「q」のビットサイズ「lenq」と、発行識別子情報「IDI」のビットサイズ「lenIDI」とを受付情報記憶部2202より読み出す。
乱数生成部2203は、生成した乱数「R1」を素数候補生成部2204へ出力する。
また、乱数生成部2203は、第1素数判定部2205及び第2素数判定部2206の何れかから、再度乱数を生成する旨の第2生成指示を受け付けると、各ビットサイズを読み出し、上記の動作を行う。
素数候補生成部2204は、単射である関数「f」を予め記憶している関数記憶領域と、関数「f」を用いて生成された数を記憶する生成情報記憶領域とを有している。
素数候補生成部2204は、受付部2201より開始指示を受け取ると、第1生成指示を乱数生成部2203へ出力する。
素数候補生成部2204は、関数記憶領域にて記憶している関数「f」と、読み出した素数「q」及び発行識別子情報「IDI」と、乱数生成部2203より受け取った乱数「R1」とを用いて、数「R=f(IDI||R1)」と、数「N=2×R×q+1」とを生成する。
「2×lenq」であると判断する場合には、素数候補生成部2204は、生成した数「N」を第1素数判定部2205へ出力し、生成した数「R」を生成情報記憶領域に記憶する。
素数候補生成部2204は、生成した数「N」のビットサイズが、「2×lenq」となるまで、上記の動作を繰り返す。
第1素数判定部2205は、第1の実施の形態にて示す第1素数判定部143と同様の動作であるため、ここでの説明は省略する。
<第2素数判定部2206>
第2素数判定部2206は、第1の実施の形態にて示す第2素数判定部144と同様の動作であるため、ここでの説明は省略する。
<素数生成装置2200の動作>
以下に、素数生成装置2200の動作について説明する。
(素数生成処理)
ここでは、素数生成装置2200にて行われる素数生成処理について、図39に示す流れ図を用いて、変更点のみ説明する。
素数生成装置2200は、上記のように変更されたステップS2000の実行後、ステップS2005を省略し、以下のように変更されたステップS2010を実行する。素数生成装置2200は、ステップS2010において、(lenq−lenIDI−1)ビットの乱数「R1」を生成するように変更する。
(素数候補生成処理)
ここでは、素数候補生成処理について、図40に示す流れ図を用いて、変更点のみ説明する。
先ず、ステップS2050を、数「R=f(IDI||R1)」を生成するように変更する。
以降の動作の流れは、図40と同様であるため、説明は省略する。
(6)素数生成変形例3における素数生成部116Cを、予め記憶している8ビットの素数から256ビットの素数を生成する第1素数生成部と、256ビットの素数から512ビットの素数を生成する第2素数生成部とからなるとしてもよい。また、第1素数生成部及び第2素数生成部を、それぞれ個別の素数生成装置としてもよい。
以下に、第2素数生成部の構成の一例を、図42に示す。ここでは、第2素数生成部を1つの素数生成装置2300として説明する。素数生成装置2300は、素数「q」と、そのビットサイズ「lenq」(ここでは、ビットサイズを128ビットとする。)と、発行識別子情報「IDI」と、そのビットサイズ「lenIDI」とが与えられた場合に、(2×lenq)ビットからなる素数「N」を出力する。なお、ここで示す素数生成装置2300は、第1の実施の形態にて示す第1及び第2検証値を用いないで、素数「N」を生成する。
素数生成装置2300は、具体的には、マイクロプロセッサ、ROM、RAM、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記RAM又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、素数生成装置2300は、その機能を達成する。
受付情報記憶部2302は、素数「N」を生成する際に与えられた素数「q」、素数「q」のビットサイズ「lenq」、発行識別子情報「IDI」及び発行識別子情報のビットサイズ「lenIDI」を記憶する領域を備えている。
<受付部2301>
受付部2301は、素数「q」、素数「q」のビットサイズ「lenq」、発行識別子情報「IDI」及び発行識別子情報のビットサイズ「lenIDI」を、外部(例えば、第1の素数生成部)より受け付け、受け付けた素数「q」、そのビットサイズ「lenq」、発行識別子情報「IDI」及びそのビットサイズ「lenIDI」を受付情報記憶部2302へ書き込む。
<識別子素数生成部2303>
識別子素数生成部2303は、素数「qg」及びそのビットサイズ「lenqg」を予め記憶している。
識別子素数生成部2303は、受付部2301より開始指示を受け取ると、発行識別子情報「IDI」を、受付情報記憶部2302より読み出す。
識別子素数生成部2303は、予め記憶している素数「qg」及び素数生成関数「gp」と、読み出した発行識別子情報「IDI」より、素数「pIDI=gp(IDI,qg)」を生成する。素数「pIDI」の生成方法は、素数生成の変形例3にて示す方法と同様であるため、説明は省略する。
<乱数生成部2304>
乱数生成部2304は、第1生成指示を、素数候補生成部2305から受け取ると、素数「q」のビットサイズ「lenq」を、受付情報記憶部2302より読み出し、素数「qg」のビットサイズ「lenqg」を識別子素数生成部2303より読み出す。
乱数生成部2304は、生成した乱数「R」を素数候補生成部2305へ出力する。
また、乱数生成部2304は、第1素数判定部2306及び第2素数判定部2307の何れかから、再度乱数を生成する旨の第2生成指示を受け付けると、各ビットサイズを読み出し、上記の動作を行う。
素数候補生成部2305は、識別子素数生成部2303より素数「pIDI」を受け取ると、第1生成指示を乱数生成部2304へ出力する。
素数候補生成部2305は、乱数生成部2304より、乱数「R」を受け取ると、受付情報記憶部2302にて記憶している素数「q」を読み出す。
素数候補生成部2305は、素数「q」のビットサイズ「lenq」を、受付情報記憶部2302より読み出し、生成した数「N」のビットサイズが「2×lenq」であるか否かを判断する。
「2×lenq」でないと判断する場合には、素数候補生成部2305は、乱数生成部2304より受け取った乱数「R」に2を掛けて、その結果を「R」として、再度、上記の動作を行い、数「N」を生成する。
<第1素数判定部2306>
第1素数判定部2306は、第1の実施の形態にて示す第1素数判定部143と同様の動作であるため、ここでの説明は省略する。
第2素数判定部2307は、第1の実施の形態にて示す第2素数判定部144と同様の動作であるため、ここでの説明は省略する。
なお、第2素数判定部2307は、判定により、生成した数「N」が素数であると判断する場合には、生成した数「N」を素数「N」として出力する。
以下に、素数生成装置2300の動作について説明する。
(素数生成処理)
ここでは、素数生成装置2300にて行われる素数生成処理について、図39に示す流れ図を用いて、変更点のみ説明する。
素数生成装置2300は、ステップS2005において、素数「pIDI」を生成するように変更する。
以降の動作の流れは、図39と同様であるため、説明は省略する。
(素数候補生成処理)
ここでは、素数候補生成処理について、図40に示す流れ図を用いて、変更点のみ説明する。
次に、ステップS2055を、数「N=2×R×q×pIDI+1」を生成するように変更する。
以降の動作の流れは、図40と同様であるため、説明は省略する。
<その他>
ここでは、生成する秘密鍵である素数のビットサイズは512ビットとしているが、これに限定されない。1024ビットであっても、2048ビットであってもよい。また、上記の第1素数生成部で生成する素数も同様に256ビットに限らない。
第1素数生成部は、従来と同様の方法にて、8ビットの素数から128ビットの素数を生成し、上記に示す素数生成装置2200を適用して、128ビットの素数から256ビットの素数を生成する。
素数生成装置2400は、具体的には、マイクロプロセッサ、ROM、RAM、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記RAM又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、素数生成装置2400は、その機能を達成する。
受付情報記憶部2402は、素数「N」を生成する際に与えられた素数「q」、素数「q」のビットサイズ「lenq」、発行識別子情報「IDI」及び発行識別子情報のビットサイズ「lenIDI」を記憶する領域を備えている。
<受付部2401>
受付部2401は、素数「q」、素数「q」のビットサイズ「lenq」、発行識別子情報「IDI」及び発行識別子情報のビットサイズ「lenIDI」を、外部(例えば、上記に示す第1素数生成部)より受け付け、受付部2401は、受け付けた素数「q」、そのビットサイズ「lenq」、発行識別子情報「IDI」及びそのビットサイズ「lenIDI」を受付情報記憶部2402へ書き込む。
<乱数生成部2403>
乱数生成部2403は、乱数を生成する旨の第1生成指示を、素数候補生成部2404から受け取ると、素数「q」のビットサイズ「lenq」と、発行識別子情報「IDI」のビットサイズ「lenIDI」とを受付情報記憶部2402より読み出す。
乱数生成部2403は、生成した乱数「R1」を素数候補生成部2404へ出力する。
また、乱数生成部2403は、第1素数判定部2405及び第2素数判定部2406の何れかから、再度乱数を生成する旨の第2生成指示を受け付けると、各ビットサイズを読み出し、上記の動作を行う。
素数候補生成部2404は、生成された数を記憶する生成情報記憶領域とを有している。
素数候補生成部2404は、受付部2401より開始指示を受け取ると、第1生成指示を乱数生成部2403へ出力する。
素数候補生成部2404は、読み出した素数「q」及び発行識別子情報「IDI」と、乱数生成部2403より受け取った乱数「R1」とを用いて、数「R=IDI×R1」と、数「N=2×R×q+1」とを生成する。
「2×lenq」であると判断する場合には、素数候補生成部2404は、生成した数「N」を第1素数判定部2405へ出力し、生成した数「R」を生成情報記憶領域に記憶する。
素数候補生成部2404は、生成した数「N」のビットサイズが、「2×lenq」となるまで、上記の動作を繰り返す。
第1素数判定部2405は、第1の実施の形態にて示す第1素数判定部143と同様の動作であるため、ここでの説明は省略する。
<第2素数判定部2406>
第2素数判定部2406は、第1の実施の形態にて示す第2素数判定部144と同様の動作であるため、ここでの説明は省略する。
<素数生成装置2400の動作>
以下に、素数生成装置2400の動作について説明する。
(素数生成処理)
ここでは、素数生成装置2400にて行われる素数生成処理について、図39に示す流れ図を用いて、変更点のみ説明する。
素数生成装置2400は、上記のように変更されたステップS2000の実行後、ステップS2005を省略し、以下のように変更されたステップS2010を実行する。素数生成装置2400は、ステップS2010において、(lenq−lenIDI−1)ビットの乱数「R1」を生成するように変更する。
(素数候補生成処理)
ここでは、素数候補生成処理について、図40に示す流れ図を用いて、変更点のみ説明する。
先ず、ステップS2050を、数「R=IDI×R1」を生成するように変更する。
以降の動作の流れは、図40と同様であるため、説明は省略する。
(8)第1の実施の形態における素数生成部116を、予め記憶している8ビットの素数から256ビットの素数を生成する第1素数生成部と、256ビットの素数から512ビットの素数を生成する第2素数生成部とからなるとしてもよい。また、第1素数生成部及び第2素数生成部を、それぞれ個別の素数生成装置としてもよい。
以下に、第2素数生成部の構成の一例を、図44に示す。ここでは、第2素数生成部を1つの素数生成装置2500として説明する。素数生成装置2500は、素数「q」と、そのビットサイズ「lenq」(ここでは、ビットサイズを256ビットとする。)と、発行識別子情報「IDI」と、そのビットサイズ「lenIDI」と、検証値「c」が与えられた場合に、(2×lenq)ビットからなる素数「N」を出力する。
素数生成装置2500は、具体的には、マイクロプロセッサ、ROM、RAM、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記RAM又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、素数生成装置2500は、その機能を達成する。
受付情報記憶部2502は、素数「N」を生成する際に与えられた素数「q」、素数「q」のビットサイズ「lenq」、発行識別子情報「IDI」、発行識別子情報のビットサイズ「lenIDI」及び検証値「c」を記憶する領域を備えている。
<受付部2501>
受付部2501は、素数「q」、素数「q」のビットサイズ「lenq」、発行識別子情報「IDI」、発行識別子情報のビットサイズ「lenIDI」及び検証値「c」を、外部(例えば、上記に示す第1素数生成部)より受け付け、受付部2501は、受け付けた素数「q」、そのビットサイズ「lenq」、発行識別子情報「IDI」、そのビットサイズ「lenIDI」及び検証値「c」を受付情報記憶部2502へ書き込む。
<乱数生成部2503>
乱数生成部2503は、乱数を生成する旨の第1生成指示を、素数候補生成部2504から受け取ると、素数「q」のビットサイズ「lenq」と、発行識別子情報「IDI」のビットサイズ「lenIDI」とを受付情報記憶部2502より読み出す。
乱数生成部2503は、生成した乱数「R1」を素数候補生成部2504へ出力する。
また、乱数生成部2503は、第1素数判定部2505及び第2素数判定部2506の何れかから、再度乱数を生成する旨の第2生成指示を受け付けると、各ビットサイズを読み出し、上記の動作を行う。
素数候補生成部2504は、生成された数を記憶する生成情報記憶領域とを有している。
素数候補生成部2504は、受付部2501より開始指示を受け取ると、第1生成指示を乱数生成部2503へ出力する。
素数候補生成部2504は、読み出した素数「q」、発行識別子情報「IDI」及び検証値「c」と、乱数生成部2503より受け取った乱数「R1」とを用いて、数「R=IDI×R1」と、数「N=2×(R+w)×q+1」とを生成する。
素数候補生成部2504は、生成した数「N」のビットサイズが「2×lenq」であるか否かを判断する。
「2×lenq」でないと判断する場合には、素数候補生成部2504は、乱数生成部2503より受け取った乱数「R1」に2を掛けて、その結果を「R1」として、再度、上記の動作を行い、数「R」及び「N」を生成する。
<第1素数判定部2505>
第1素数判定部2505は、第1の実施の形態にて示す第1素数判定部143と同様の動作であるため、ここでの説明は省略する。
第2素数判定部2506は、第1の実施の形態にて示す第2素数判定部144と同様の動作であるため、ここでの説明は省略する。
なお、第2素数判定部2506は、判定により、生成した数「N」が素数であると判断する場合には、生成した数「N」を素数「N」として出力する。
以下に、素数生成装置2400の動作について説明する。
(素数生成処理)
ここでは、素数生成装置2500にて行われる素数生成処理について、図39に示す流れ図を用いて、変更点のみ説明する。
素数生成装置2500は、上記のように変更されたステップS2000の実行後、ステップS2005を省略し、以下のように変更されたステップS2010を実行する。素数生成装置2500は、ステップS2010において、(lenq−lenIDI−1)ビットの乱数「R1」を生成するように変更する。
(素数候補生成処理)
ここでは、素数候補生成処理について、図40に示す流れ図を用いて、変更点のみ説明する。
先ず、ステップS2050を、数「R=IDI×R1」を生成するように変更する。
以降の動作の流れは、図40と同様であるため、説明は省略する。
(9)上記第1の実施の形態において、素数生成部116は、単射関数「f」を施し、その後、発行識別子情報「IDI」の埋め込みを行ったが、単射関数「f」を施すだけでもよいし、発行識別子情報「IDI」の埋め込みのみを行ってもよい。
発行識別子情報「IDI」の埋め込みのみを行う場合には、生成された素数の一意性は満たされないが、生成された鍵の正当性の確認は、「IDI」を用いて行うことができる。なお、発行識別子情報「IDI」の埋め込みのみを行う場合は、256ビットの素数から512ビットの素数を生成するタイミングに行う。
(10)上記第1及び第2の実施の形態において、制御情報が「情報B」である場合に、素数生成部116は、単射関数を施し、数「R=f(IDI||R1)」を生成したが、これに限定されない。
例えば、制御情報が「情報B」である場合に、素数生成部116は、数「R=f(R1||IDI)」を生成してもよいし、数「R=f(IDI)||R1」を生成してもよし、数「R=R1||f(IDI)」を生成してもよい。
また、発行識別子情報「IDI」のビット列に、乱数「R1」を構成する各ビットを埋め込み、埋め込んだ結果(以下、「IDI_R1」という。)に単射関数「f」を施して数「R」を生成してもよい。
また、発行識別子情報「IDI」と乱数「R1」とから、数「IDI_R1」を生成し、生成した数「IDI_R1」に単射関数「f」を施して数「R」を生成したが、これに限定されない。数「R」は、「R=IDI_R1」としてもよい。
例えば、鍵発行サーバ100と証明書発行サーバ200とだけが既知の秘密関数であり、且つ1対1の関数である「g」を用いた値であってもよい。このとき、「IDI」の代わりに埋め込む値は、「g(IDI)」である。
(12)上記第1の実施の形態において、鍵発行サーバ100と端末装置300との間に、安全な通信経路を確立して、鍵発行サーバ100から端末装置300へ、秘密鍵及び公開鍵の送付を行ったが、これに限定されない。
例えば、端末装置300の製造時に、鍵発行サーバ100と端末装置300とを、入出力装置を介して、秘密鍵及び公開鍵の送付を行ってもよい。
(13)上記第1及び第2の実施の形態において、端末装置の具体例として、携帯電話機としたが、これに限定されない。
暗号化されたデータをネットワークを介して受信し、復号できる端末装置であればよい。
(14)上記第1及び第2の実施の形態において、発行識別子情報「IDI」は、奇数であるとしたが、素数生成に検証値を用いない場合には、発行識別子情報「IDI」は、奇数でなくてもよい。
(15)第1及び第2の実施の形態にて、生成する秘密鍵である素数のビットサイズは512ビットに限らない。1024ビットであっても、2048ビットであってもよい。このとき、素数生成部116は、秘密鍵である素数のビットサイズ(ここでは、「lenN」とする。)に対して、(lenN/4)ビットからなる素数を、従来の素数の生成方法により生成し、その後、単射関数「f」を施して、(lenN/2)ビットからなる素数を生成し、最後に、発行識別子情報「IDI」を埋め込んだ「lenN」ビットからなる素数「N」を生成する。
また、単射関数「f」を施し、一意な素数を生成するのみの場合は、(lenN/2)ビットからなる素数を、従来の素数の生成方法により生成し、その後、単射関数「f」を施して、「lenN」ビットからなる素数を生成する。
また、上述したように、第1実施の形態における素数生成部116は、素数情報生成部133の代わりに、素数生成の変形例1、2及び3にて示す素数情報生成部133A、素数情報生成部133B及び素数情報生成部133Cの何れかを用いてもよい。
(18)鍵発行サーバは3台に限定されない。鍵発行サーバは1台以上であればよい。このとき、各鍵発行サーバにて行う素数の生成方法は、同一の方法を用いる。
(19)第1の実施の形態における第2素数判定部144は、素数の判定に用いる条件式は、上記に示す(eq2)に限定されない。
(20)第1の実施の形態において、鍵発行サーバ100は、端末装置300へ秘密鍵と公開鍵証明書を配布したが、これに限定されない。鍵発行サーバ100は、端末装置300へ秘密鍵のみを配布してもよい。このとき、鍵発行サーバ100は、公開鍵証明書を第三者に対して、公開する。または、鍵発行サーバ100は、公開鍵を第三者に対して、公開する。
鍵判定部117にて、受け取った素数の個数をカウントしてもよい。この場合の一例を、以下に示す。
素数生成部116は、識別子生成部115から素数の生成開始命令を受け取ると、素数「p1」を生成し、生成した素数「p1」を鍵判定部117へ出力する。素数生成部116は、鍵判定部117から次の素数の要求を受け取ると、素数「p2」を生成し、生成した素数「p2」を鍵判定部117へ出力する。なお、素数「p1」及び「p2」の生成は、第1の実施の形態と同様であるため、説明は省略する。
また、素数生成の変形例3において、素数「qg」のビットサイズを64ビットとしたが、これに限定されない。素数「qg」は、ビットサイズ「lenqg」が「(2×lenqg)<(lenq−1)」を満たす素数であればよい。このとき、発行識別子情報は、そのビットサイズが、素数「qg」のビットサイズより小さければよい。
検証方法の具体的な動作の流れを、図46に示す流れ図を用いて説明する。
次に、発行公開鍵確認部214は、「Q−IDI」を算出し、算出結果を、再度、「Q」とする(ステップS2505)。
発行公開鍵確認部214は、数「Q」が、発行識別子情報「IDI」より小さいか否かを判断する(ステップS2510)。
「0」であると判断する場合には(ステップS2515における「YES」)、検証結果「0」を出力する(ステップS2520)。「0」でないと判断する場合には(ステップS2515における「NO」)、検証結果「1」を出力する(ステップS2525)。
この動作により、公開鍵「PK=(n、e)」が、発行識別子情報「IDI」を用いて生成されたか否かを確認することができる。
発行公開鍵確認部214は、図18に示すステップS670にて、上記の検証処理を実行後、出力された検証結果が「0」である場合には、公開鍵「PK」は発行識別子情報「IDI」を用いて生成されたと判断し、検証結果が「1」である場合には、公開鍵「PK」は発行識別子情報「IDI」を用いて生成されていないと判断する。
素数候補生成部142は、生成された数「N」が、「lenN=2×lenq」を満たさない場合には、数「R1」のビット列を、左に1ビット分だけシフトする。このとき、末尾のビットには「0」が設定される。これにより、「R1=2×R1」とすることできる。
なぜなら、上記の実施の形態にて示した「w」及び「m」の条件式「w=(c−1)×m mod IDI」と、「(2×q)×m=1 mod IDI」とを用いると、「N=2×(R+w)×q+1」は、以下のように変形することができるからである。
=2×R×q+2×(c−1)×m×q+1
=2×R×q+2×(c−1)×(1/2q)×q+1
=2×R×q+(c−1)+1
=2×R×q+c
これにより、「N=2×(R+w)×q+1」の代わりに、「N=2×R×q+c」としてもよいことがわかる。
この場合における素数検証装置及び鍵発行サーバ100の動作について、以下に説明する。
素数検証装置は、証明書発行サーバと同様に、検証値テーブルを予め記憶している。
素数検証装置は、鍵発行サーバ100より、素数「p1」、発行識別子情報「IDI」及びサーバ識別子を受け取ると、受け取ったサーバ識別子に対応する第1検証値「c11」を読み出し、読み出した第1検証値「c11」を用いて、「p1−c11」を算出し、算出結果が、「IDI」で割り切れるか否かを判断する。割り切れると判断する場合には、素数検証装置は、素数「p1」の利用を許可する情報を鍵発行サーバ100へ出力する。割り切れないと判断する場合には、素数「p1」の利用を禁止する情報を鍵発行サーバ100へ出力する。
鍵発行サーバ100の素数生成部116は、素数検証装置から、素数「p1」の利用を許可する情報を受け取ると、生成した素数「p1」を鍵判定部117へ出力し、素数「p2」を生成する。素数生成部116は、生成した素数「p2」、発行識別子情報「IDI」及びサーバ識別子を、素数検証装置へ出力する。
鍵発行サーバ100の素数生成部116は、素数検証装置から、素数「p2」の利用を許可する情報を受け取ると、生成した素数「p2」と判定開始命令とを鍵判定部117へ出力する。
なお、素数生成部116は、鍵判定部117より再生成命令を受け取った場合には、再度素数「p2」を生成し、上記の動作を繰り返す。
(27)第1及び第2の実施の形態において、第1及び第2検証値は、鍵発行サーバ毎に割り当てたが、これに限定されない。
鍵発行サーバは、鍵発行の要求のあった端末装置に対応する第1及び第2検証値を用いて、素数「p1」及び「p2」を生成し、生成した「p1」及び「p2」を用いて、公開鍵及び秘密鍵を生成する。鍵発行サーバは、公開鍵証明書を要求する際には、公開鍵、発行識別子情報、サーバ識別子及び端末識別子を、証明書発行サーバへ送信する。
端末装置毎に、2つの検証値を割り当てることにより、公開鍵の一意性を保ちながら、端末装置毎に割り当てた公開鍵の正当性を検証することができる。
(28)第1及び第2の実施の形態において、端末装置と鍵発行サーバとを、それぞれ個別の装置としたが、端末装置にて鍵発行を行ってもよい。
端末装置は、識別子生成部を用いて、端末識別子と、数「1」とから発行識別子情報「IDI=TID||1」を生成し、生成した発行識別子情報を識別子格納部にて記憶する。
さらに、端末装置は、発行識別子情報と、公開鍵と、端末識別子と、証明書発行依頼情報とを、証明書発行サーバへ送信し、公開鍵証明書を、証明書発行サーバから受信する。
また、端末装置は、ICカードであってもよい。この場合、ICカードは、鍵の生成及び格納を行う。なお、発行識別子情報の生成及び格納をもICカードが行ってもよい。このとき、ICカードと、証明書発行サーバとの通信は、証明書発行サーバとネットワーク接続された装置に、ICカードを装着することにより行う。
端末識別子は、ユーザの生体科学的特徴を示すバイオメトリックス情報であってもよい。バイオメトリックス情報は、例えば、ユーザの指紋の特徴を示す指紋情報、ユーザの声紋の特徴を示す声紋情報、ユーザの虹彩の特徴を示す虹彩情報、ユーザの顔の輪郭の特徴を示す輪郭情報、ユーザのDNAの特徴を示すDNA情報又は、これら情報の組合せである。
また、端末識別子は、端末装置を管理する管理サーバにて発行され、管理サーバからネットワークによる通信によって、与えられるものとしてもよい。または、管理サーバにて発行された端末識別子を、SDカード等の記録媒体によって、与えられるとしてもよい。
(30)本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
また、本発明は、マイクロプロセッサとメモリとを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムに従って動作するとしてもよい。
(31)上記実施の形態及び上記変形例をそれぞれ組み合わせるとしてもよい。
100、101、102 鍵発行サーバ
110 識別子格納部
111 秘密鍵格納部
112 公開鍵格納部
113 証明書格納部
114 制御部
115 識別子生成部
116 素数生成部
117 鍵判定部
118 鍵生成部
119 情報取得部
120 受信部
121 送信部
130 サーバ識別子記憶領域
131 端末情報記憶領域
132 繰返制御部
133 素数情報生成部
135 繰返カウンタ
136 出力カウンタ
140 情報制御部
141 乱数生成部
142 素数候補生成部
143 第1素数判定部
144 第2素数判定部
200 証明書発行サーバ
210 秘密鍵格納部
211 発行公開鍵格納部
212 発行識別子情報格納部
213 公開鍵証明書格納部
214 発行公開鍵確認部
215 公開鍵証明書生成部
216 証明書取得部
217 受信部
218 送信部
220 サーバ情報記憶領域
221 確認情報記憶領域
300、301、302、303、304、305、306 端末装置
310 秘密鍵格納部
311 公開鍵証明書格納部
312 制御部
313 受付部
314 無線部
315 ベースバンド信号処理部
316 スピーカー
317 マイク
318 表示部
319 アンテナ
320 端末識別子記憶領域
400 端末装置
2 鍵発行システム
1100、1101、1102 鍵発行サーバ
1110 識別子格納部
1111 秘密鍵格納部
1112 公開鍵格納部
1113 証明書格納部
1114 制御部
1115 識別子生成部
1116 素数生成部
1117 鍵判定部
1118 鍵生成部
1119 情報取得部
1120 受信部
1121 送信部
1122 証明書生成部
1123 証明書用秘密鍵格納部
1124 発行済鍵情報格納部
1130 サーバ識別子記憶領域
1131 端末情報記憶領域
1200 鍵発行監査サーバ
1210 確認情報格納部
1211 発行済鍵情報格納部
1212 制御部
1213 発行公開鍵確認部
1214 受付部
1215 監査結果出力部
1216 受信部
1217 送信部
1220 サーバ情報記憶領域
1250 モニタ
1300、1301、1302、1303、1304、1305、1306 端末装置
1400 端末装置
2100 素数生成装置
2101 受付部
2102 受付情報記憶部
2103 素数シード生成部
2104 乱数生成部
2105 素数候補生成部
2106 素数判定部
2107 素数判定部
2200 素数生成装置
2201 受付部
2202 受付情報記憶部
2203 乱数生成部
2204 素数候補生成部
2205 素数判定部
2206 素数判定部
2300 素数生成装置
2301 受付部
2302 受付情報記憶部
2303 識別子素数生成部
2304 乱数生成部
2305 素数候補生成部
2306 素数判定部
2307 素数判定部
2400 素数生成装置
2401 受付部
2402 受付情報記憶部
2403 乱数生成部
2404 素数候補生成部
2405 素数判定部
2406 素数判定部
2500 素数生成装置
2501 受付部
2502 受付情報記憶部
2503 乱数生成部
2504 素数候補生成部
2505 素数判定部
2506 素数判定部
Claims (23)
- 既知の素数qより大きい素数候補Nを算出して素数判定する素数算出装置であって、
既知の素数qを記憶している素数記憶手段と、
素数の利用範囲における一意の管理情報を記憶している管理情報記憶手段と、
前記管理情報記憶手段から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Rを生成する攪乱情報生成手段と、
前記素数記憶手段から前記素数qを読み出し、読み出した前記素数q及び生成された前記攪乱情報Rを用いて、N=2×攪乱情報R×素数q+1により、素数候補Nを算出する候補算出手段と、
算出された素数候補Nが素数であるか否かを判定する素数判定手段と、
素数であると判定される場合に、算出された素数候補Nを素数として出力する出力手段と
を備えることを特徴とする素数算出装置。 - 前記攪乱情報生成手段は、
前記管理情報記憶手段から前記管理情報を読み出す読出部と、
乱数rを算出する乱数算出部と、
読み出した前記管理情報と生成した乱数rとを結合する結合部と、
前記管理情報と乱数rとの結合体に基づいて、攪乱情報Rを算出する演算部と
を含むことを特徴とする請求項1に記載の素数算出装置。 - 前記演算部は、前記結合体に、単射の関数を施して攪乱情報Rを生成する
ことを特徴とする請求項2に記載の素数算出装置。 - 前記単射の関数は、排他的論理和であり、
前記演算部は、所定の鍵情報を予め記憶しており、前記鍵情報と前記結合体とに排他的論理和を施して攪乱情報Rを生成する
ことを特徴とする請求項3に記載の素数算出装置。 - 前記素数算出装置は、素数qの2倍のビット長を有する素数候補Nを算出し、
前記乱数算出部は、素数qのビット長から前記管理情報のビット長及び1を差し引いて得られるビット長の前記乱数rを算出する
ことを特徴とする請求項3に記載の素数算出装置。 - 前記素数判定手段は、
前記素数候補Nに対して、2N-1 =1 mod Nを満たすか否かを判定する第1判定部と、
前記第1判定部により満たすと判定される場合に、さらに、素数候補N及び攪乱情報Rに対して、22R ≠1 mod Nを満たすか否かを判定し、満たすと判定する場合に、素数候補Nが素数であると決定する第2判定部と
を含むことを特徴とする請求項5に記載の素数算出装置。 - 前記素数判定手段は、
前記素数候補Nに対して、2N-1 =1 mod Nを満たすか否かを判定する第1判定部と、
前記第1判定部により満たすと判定される場合に、さらに、素数候補N及び攪乱情報Rに対して、GCD(22R −1、N)=1を満たすか否かを判定し、満たすと判定する場合に、素数候補Nが素数であると決定する第2判定部と
を含むことを特徴とする請求項5に記載の素数算出装置。 - 前記素数算出装置は、さらに、
前記素数判定手段により素数であると判定されるまで、前記攪乱情報生成手段、前記候補算出手段及び前記素数判定手段に対して、攪乱情報Rの生成と、素数候補Nの算出と、前記判定とを繰り返すように制御する繰返制御手段
を含むことを特徴とする請求項1に記載の素数算出装置。 - 前記素数算出装置は、さらに、
乱数R'を算出する次段乱数算出手段と、
出力された前記素数N及び生成された前記乱数R'を用いて、N'=2×乱数R'×素数N+1により、素数候補N'を算出する次段候補算出手段と、
算出された素数候補N'が素数であるか否かを判定する次段素数判定手段と、
素数であると判定される場合に、算出された素数候補N'を素数として出力する次段出力手段と、
前記次段素数判定手段により素数であると判定されるまで、前記次段乱数算出手段、前記次段候補算出手段及び前記次段素数判定手段に対して、乱数R'の生成と、素数候補N'の算出と、前記判定とを繰り返すように制御する次段繰返制御手段と
を含むことを特徴とする請求項8に記載の素数算出装置。 - 記素数算出装置は、さらに、
所定の検証値を記憶している次段情報記憶手段と、
乱数r'を生成する次段乱数生成手段と、
前記管理情報に生成した前記乱数r'を乗じて攪乱情報R'を算出し、N'=2×攪乱情報R'×素数N+検証値により、素数候補N'を算出する次段候補算出手段とを含み、
前記素数判定手段は、さらに、算出された素数候補N'が素数であるか否かを判定し、
前記出力手段は、さらに、素数候補N'が素数であると判定される場合に、算出された素数候補N'を素数として出力する
ことを特徴とする請求項8に記載の素数算出装置。 - 前記素数算出装置は、RSA暗号の公開鍵及び秘密鍵を生成する鍵生成装置であり、
前記素数算出装置は、さらに、
算出された素数Nを用いて、RSA暗号の公開鍵を生成する公開鍵生成手段と、
生成された公開鍵を用いて、RSA暗号の秘密鍵を生成する秘密鍵生成手段とを含む
ことを特徴とする請求項8に記載の素数算出装置。 - 前記公開鍵生成手段は、前記繰返制御手段に対して、新たに素数N'が得られるように指示し、前記素数N及び新たに得られた素数N'を用いて、n=素数N×素数N'により、数nを算出し、乱数eを生成し、
算出された数nと生成された乱数eとの組が前記公開鍵であり、
前記秘密鍵生成手段は、e×d=1 mod Lを満たすdを算出し、
Lは、素数N−1と素数N'−1との最小公倍数であり、
算出されたdが前記秘密鍵である
ことを特徴とする請求項11に記載の素数算出装置。 - 前記素数算出装置は、端末装置に対して、RSAの秘密鍵及び公開鍵を生成し、発行する鍵発行サーバ装置であり、
前記素数算出装置は、さらに、
生成した前記秘密鍵を、端末装置に対して出力する鍵出力手段と、
生成した前記公開鍵を、公開する公開手段とを含む
ことを特徴とする請求項11に記載の素数算出装置。 - 前記素数算出装置は、さらに、
前記端末装置を一意に識別する端末装置識別子を取得する識別子取得手段と、
取得した端末装置識別子を含む前記管理情報を生成する管理情報生成手段と、
生成した前記管理情報を前記管理情報記憶手段に書き込む書込手段とを
含むことを特徴とする請求項13に記載の素数算出装置。 - 前記素数算出装置は、さらに、
鍵発行サーバ装置としての当該素数算出装置を一意に識別するサーバ識別子を予め記憶しているサーバ識別子記憶手段を含み、
前記管理情報生成手段は、さらに、前記サーバ識別子記憶手段から前記サーバ識別子を読み出し、読み出したサーバ識別子をさらに含む前記管理情報を生成する
ことを特徴とする請求項14に記載の素数算出装置。 - 既知の素数より大きい素数を算出する素数算出装置であって、
既知の入力素数の2倍のビット長を有する出力素数を算出する素数算出手段と、
既知の素数初期値を記憶している素数記憶手段と、
前記素数算出手段に対して、算出を複数回繰り返すように制御する繰返制御手段とを備え、
前記繰返制御手段は、前記繰返しにおける初回の算出において、前記素数記憶手段に記憶されている素数初期値を、前記入力素数として、前記素数算出手段に与え、
前記繰返しの初回の算出以外の他の算出において、1つ前の回の算出においてされた出力素数を、当該他の算出における前記入力素数として、前記素数算出手段に与え、
前記複数回の算出のいずれか1の算出において、前記素数算出手段は、
素数の利用範囲における一意の管理情報を記憶している管理情報記憶部と、
前記管理情報記憶部から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Rを生成する攪乱情報生成部と、
前記入力素数qを受け取り、受け取った前記入力素数q及び生成された前記攪乱情報Rを用いて、N=2×攪乱情報R×素数q+1により、素数候補Nを算出する候補算出部と、
算出された素数候補Nが素数であるか否かを判定する素数判定部と、
素数であると判定される場合に、算出された素数候補Nを出力素数として出力する出力部と、
前記素数判定部により素数であると判定されるまで、前記攪乱情報生成部、前記候補算出部及び前記素数判定部に対して、攪乱情報Rの生成と、素数候補Nの算出と、前記判定とを繰り返すように制御する繰返制御部とを含む
ことを特徴とする素数算出装置。 - 前記複数回の算出のうち、最終回の算出において、前記素数算出手段は、
所定の検証値を記憶している情報記憶部と、
乱数r'を生成する乱数生成部と、
前記管理情報に生成した前記乱数r'を乗じて攪乱情報R'を算出し、N'=2×攪乱情報R'×1つ前の回において算出された出力素数+検証値により、素数候補N'を算出する候補算出部と、
算出された素数候補N'が素数であるか否かを判定する素数判定部と、
素数候補N'が素数であると判定される場合に、算出された素数候補N'を素数として出力する出力部と、
前記素数判定部により素数であると判定されるまで、前記乱数生成部、前記候補算出部及び前記素数判定部に対して、乱数r'の生成と、素数候補N'の算出と、前記判定とを繰り返すように制御する繰返制御部とを含む
ことを特徴とする請求項16に記載の素数算出装置。 - 端末装置に対してRSAの秘密鍵及び公開鍵を生成して発行する鍵発行サーバ装置と、前記端末装置とから構成される鍵発行システムであって、
鍵発行サーバ装置は、
既知の素数qより大きい素数Nを算出する素数算出手段と、
算出された素数Nを用いて、RSA暗号の公開鍵を生成する公開鍵生成手段と、
生成された公開鍵を用いて、RSA暗号の秘密鍵を生成する秘密鍵生成手段と、
生成された前記秘密鍵を、端末装置に対して出力する鍵出力手段と、
生成された前記公開鍵を公開する公開手段とを備え、
前記素数算出手段は、
既知の素数qを記憶している素数記憶部と、
一意の管理情報を記憶している管理情報記憶部と、
前記管理情報記憶部から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Rを生成する攪乱情報生成部と、
前記素数記憶部から前記素数qを読み出し、読み出した前記素数q及び生成された前記攪乱情報Rを用いて、N=2×攪乱情報R×素数q+1により、素数候補Nを算出する候補算出部と、
算出された素数候補Nが素数であるか否かを判定する素数判定部と、
素数であると判定される場合に、算出された素数候補Nを素数として出力する出力部と、
前記素数判定部により素数であると判定されるまで、前記攪乱情報生成部、前記候補算出部及び前記素数判定部に対して、攪乱情報Rの生成と、素数候補Nの算出と、前記判定とを繰り返すように制御する繰返制御部とを含み、
前記端末装置は、
前記秘密鍵を受け取る受信手段と、
受信した秘密鍵を記憶する鍵記憶手段と
を備えることを特徴とする鍵発行システム。 - 前記鍵発行システムは、さらに、証明書発行サーバ装置を含み、
前記鍵出力手段は、前記公開鍵を前記証明書発行サーバ装置へ出力し、
前記証明書発行サーバ装置は、
当該証明書発行サーバ装置の秘密鍵を記憶している記憶手段と、
前記公開鍵を取得する取得手段と、
前記証明書発行サーバ装置の秘密鍵を用いて、前記公開鍵を含む公開鍵情報に、デジタル署名を施して、署名データを生成し、少なくとも前記公開鍵及び生成した前記署名データを含む公開鍵証明書を生成する証明書生成手段と、
生成した公開鍵証明書を鍵発行サーバ装置へ出力する出力手段とを備える
ことを特徴とする請求項18に記載の鍵発行システム。 - 既知の素数qより大きい素数候補Nを算出して素数判定する素数算出装置で用いられる素数算出方法であって、
前記素数算出装置は、既知の素数qを記憶している素数記憶手段と、素数の利用範囲における一意の管理情報を記憶している管理情報記憶手段と、攪乱情報生成手段と、候補算出手段と、素数判定手段と、出力手段とを備え、
前記素数算出方法は、
前記攪乱情報生成手段が、前記管理情報記憶手段から前記管理情報を読み出し、読み出した前記管理情報に依存する攪乱情報Rを生成する乱数生成ステップと、
前記候補算出手段が、前記素数記憶手段から前記素数qを読み出し、読み出した前記素数q及び生成された前記攪乱情報Rを用いて、N=2×攪乱情報R×素数q+1により、素数候補Nを算出する候補算出ステップと、
前記素数判定手段が、算出された素数候補Nが素数であるか否かを判定する素数判定ステップと、
前記出力手段が、素数であると判定される場合に、算出された素数候補Nを素数として出力する出力ステップと
を含むことを特徴とする素数算出方法。 - 既知の素数qより大きい素数候補Nを算出して素数判定する素数算出装置で用いられる素数算出用のコンピュータプログラムであって、
前記素数算出装置は、既知の素数qを記憶している素数記憶手段と、素数の利用範囲における一意の管理情報を記憶している管理情報記憶手段と、攪乱情報生成手段と、候補算出手段と、素数判定手段と、出力手段とを備え、
前記素数算出用のコンピュータプログラムは、
前記攪乱情報生成手段に、前記管理情報記憶手段から前記管理情報を読み出させ、読み出させた前記管理情報に依存する攪乱情報Rを生成させる乱数生成ステップと、
前記候補算出手段に、前記素数記憶手段から前記素数qを読み出させ、読み出させた前記素数q及び生成された前記攪乱情報Rを用いて、N=2×攪乱情報R×素数q+1により、素数候補Nを算出させる候補算出ステップと、
前記素数判定手段に、算出された素数候補Nが素数であるか否かを判定させる素数判定ステップと、
前記出力手段に、素数であると判定される場合に、算出された素数候補Nを素数として出力させる出力ステップと
を含むことを特徴とするコンピュータプログラム。 - 前記コンピュータプログラムは、
コンピュータ読み取り可能な記録媒体に記録されている
ことを特徴とする請求項21に記載のコンピュータプログラム。 - 前記コンピュータプログラムは、
搬送波に乗せられて送信される
ことを特徴とする請求項21に記載のコンピュータプログラム。
Applications Claiming Priority (7)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2003433903 | 2003-12-26 | ||
JP2003433904 | 2003-12-26 | ||
JP2003433904 | 2003-12-26 | ||
JP2003433903 | 2003-12-26 | ||
JP2004023796 | 2004-01-30 | ||
JP2004023796 | 2004-01-30 | ||
PCT/JP2004/019108 WO2005064843A1 (ja) | 2003-12-26 | 2004-12-21 | 素数算出装置及び方法並びに鍵発行システム |
Publications (2)
Publication Number | Publication Date |
---|---|
JPWO2005064843A1 JPWO2005064843A1 (ja) | 2007-12-20 |
JP4668795B2 true JP4668795B2 (ja) | 2011-04-13 |
Family
ID=34743474
Family Applications (2)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP2005516591A Expired - Fee Related JP4668796B2 (ja) | 2003-12-26 | 2004-12-21 | 素数算出装置、鍵発行システム及び素数算出方法 |
JP2005516589A Active JP4668795B2 (ja) | 2003-12-26 | 2004-12-21 | 素数算出装置、鍵発行システム及び素数算出方法 |
Family Applications Before (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP2005516591A Expired - Fee Related JP4668796B2 (ja) | 2003-12-26 | 2004-12-21 | 素数算出装置、鍵発行システム及び素数算出方法 |
Country Status (6)
Country | Link |
---|---|
US (2) | US7634084B2 (ja) |
EP (2) | EP1699161A1 (ja) |
JP (2) | JP4668796B2 (ja) |
KR (2) | KR20060126705A (ja) |
TW (2) | TW200527925A (ja) |
WO (2) | WO2005064844A1 (ja) |
Families Citing this family (27)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
EP1741222B1 (en) * | 2004-04-30 | 2011-02-23 | Research In Motion Limited | System and method for securing data |
US7953978B2 (en) * | 2006-09-07 | 2011-05-31 | International Business Machines Corporation | Key generation and retrieval using key servers |
US8472620B2 (en) * | 2007-06-15 | 2013-06-25 | Sony Corporation | Generation of device dependent RSA key |
FR2946207A1 (fr) * | 2009-05-28 | 2010-12-03 | Proton World Internat Nv | Protection d'une generation de nombres premiers pour algorithme rsa |
US8971530B2 (en) * | 2009-06-24 | 2015-03-03 | Intel Corporation | Cryptographic key generation using a stored input value and a stored count value |
JP2011123356A (ja) * | 2009-12-11 | 2011-06-23 | Oki Semiconductor Co Ltd | 素数生成装置、素数生成方法、及び素数生成プログラム |
US20120297187A1 (en) * | 2011-05-17 | 2012-11-22 | Google Inc. | Trusted Mobile Device Based Security |
JP5848106B2 (ja) * | 2011-11-28 | 2016-01-27 | ルネサスエレクトロニクス株式会社 | 半導体装置及びicカード |
IN2014CN04637A (ja) * | 2011-12-15 | 2015-09-18 | Inside Secure | |
KR101493212B1 (ko) * | 2012-10-31 | 2015-02-23 | 삼성에스디에스 주식회사 | 아이디 기반 암호화, 복호화 방법 및 이를 수행하기 위한 장치 |
US8897450B2 (en) * | 2012-12-19 | 2014-11-25 | Verifyle, Inc. | System, processing device, computer program and method, to transparently encrypt and store data objects such that owners of the data object and permitted viewers are able to view decrypted data objects after entering user selected passwords |
US20140344319A1 (en) * | 2013-05-14 | 2014-11-20 | Daljit Singh Jandu | Algorithm for primality testing based on infinite, symmetric, convergent, continuous, convolution ring group |
US9860235B2 (en) * | 2013-10-17 | 2018-01-02 | Arm Ip Limited | Method of establishing a trusted identity for an agent device |
US9307405B2 (en) | 2013-10-17 | 2016-04-05 | Arm Ip Limited | Method for assigning an agent device from a first device registry to a second device registry |
US10069811B2 (en) | 2013-10-17 | 2018-09-04 | Arm Ip Limited | Registry apparatus, agent device, application providing apparatus and corresponding methods |
WO2015056009A1 (en) * | 2013-10-17 | 2015-04-23 | Arm Ip Limited | Method of establishing a trusted identity for an agent device |
CN103580858B (zh) * | 2013-11-06 | 2017-01-04 | 北京华大信安科技有限公司 | Rsa算法私钥元素获取方法及获取装置 |
GB2529838B (en) | 2014-09-03 | 2021-06-30 | Advanced Risc Mach Ltd | Bootstrap Mechanism For Endpoint Devices |
GB2530028B8 (en) | 2014-09-08 | 2021-08-04 | Advanced Risc Mach Ltd | Registry apparatus, agent device, application providing apparatus and corresponding methods |
GB2540987B (en) | 2015-08-03 | 2020-05-13 | Advanced Risc Mach Ltd | Bootstrapping without transferring private key |
GB2540989B (en) | 2015-08-03 | 2018-05-30 | Advanced Risc Mach Ltd | Server initiated remote device registration |
WO2018174112A1 (ja) * | 2017-03-21 | 2018-09-27 | 渡辺浩志 | ネットワーク上の装置認証技術 |
KR101918741B1 (ko) | 2017-08-21 | 2018-11-14 | 국방과학연구소 | 안전소수 판별 방법 |
GB2574613B (en) * | 2018-06-12 | 2020-07-22 | Advanced Risc Mach Ltd | Device, system, and method of generating and handling cryptographic parameters |
GB2579571B (en) | 2018-12-03 | 2021-05-12 | Advanced Risc Mach Ltd | Device bootstrapping |
US11475134B2 (en) | 2019-04-10 | 2022-10-18 | Arm Limited | Bootstrapping a device |
JP2020141425A (ja) * | 2020-06-10 | 2020-09-03 | エヌ・ティ・ティ・コミュニケーションズ株式会社 | 端末装置、鍵提供システム、鍵生成方法及びコンピュータプログラム |
Citations (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JPH07121107A (ja) * | 1993-10-28 | 1995-05-12 | Nec Corp | 鍵生成方法および装置 |
JPH1152853A (ja) * | 1997-07-30 | 1999-02-26 | Fujitsu Ltd | 素数生成装置,B−smooth性判定装置及び記録媒体 |
EP1026851A1 (en) * | 1999-02-03 | 2000-08-09 | Hewlett-Packard Company | Composite cryptographic keys |
JP2002510810A (ja) * | 1998-04-08 | 2002-04-09 | シティーバンク エヌ、エー、 | 所定部分を含むrsaの法の生成 |
Family Cites Families (8)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US6052467A (en) * | 1995-03-27 | 2000-04-18 | Brands; Stefanus A. | System for ensuring that the blinding of secret-key certificates is restricted, even if the issuing protocol is performed in parallel mode |
JP3518672B2 (ja) * | 1998-11-27 | 2004-04-12 | 村田機械株式会社 | 素数生成装置及び暗号システム |
US6687375B1 (en) * | 1999-06-02 | 2004-02-03 | International Business Machines Corporation | Generating user-dependent keys and random numbers |
US6940976B1 (en) * | 1999-06-02 | 2005-09-06 | International Business Machines Corporation | Generating user-dependent RSA keys |
JP2002207426A (ja) * | 2001-01-10 | 2002-07-26 | Sony Corp | 公開鍵証明書発行システム、公開鍵証明書発行方法、および電子認証装置、並びにプログラム記憶媒体 |
JP4102090B2 (ja) | 2001-04-17 | 2008-06-18 | 松下電器産業株式会社 | 情報セキュリティ装置、素数生成装置及び素数生成方法 |
TWI244610B (en) * | 2001-04-17 | 2005-12-01 | Matsushita Electric Ind Co Ltd | Information security device, prime number generation device, and prime number generation method |
GB2384403B (en) * | 2002-01-17 | 2004-04-28 | Toshiba Res Europ Ltd | Data transmission links |
-
2004
- 2004-12-21 KR KR1020067013868A patent/KR20060126705A/ko not_active Application Discontinuation
- 2004-12-21 JP JP2005516591A patent/JP4668796B2/ja not_active Expired - Fee Related
- 2004-12-21 WO PCT/JP2004/019110 patent/WO2005064844A1/ja active Application Filing
- 2004-12-21 WO PCT/JP2004/019108 patent/WO2005064843A1/ja active Application Filing
- 2004-12-21 EP EP04807467A patent/EP1699161A1/en not_active Withdrawn
- 2004-12-21 KR KR1020067014930A patent/KR20060129302A/ko not_active Application Discontinuation
- 2004-12-21 US US10/582,803 patent/US7634084B2/en active Active
- 2004-12-21 JP JP2005516589A patent/JP4668795B2/ja active Active
- 2004-12-21 EP EP04807465A patent/EP1699160A1/en not_active Withdrawn
- 2004-12-21 US US10/582,999 patent/US7706528B2/en active Active
- 2004-12-24 TW TW093140531A patent/TW200527925A/zh unknown
- 2004-12-24 TW TW093140530A patent/TW200531495A/zh unknown
Patent Citations (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JPH07121107A (ja) * | 1993-10-28 | 1995-05-12 | Nec Corp | 鍵生成方法および装置 |
JPH1152853A (ja) * | 1997-07-30 | 1999-02-26 | Fujitsu Ltd | 素数生成装置,B−smooth性判定装置及び記録媒体 |
JP2002510810A (ja) * | 1998-04-08 | 2002-04-09 | シティーバンク エヌ、エー、 | 所定部分を含むrsaの法の生成 |
EP1026851A1 (en) * | 1999-02-03 | 2000-08-09 | Hewlett-Packard Company | Composite cryptographic keys |
Also Published As
Publication number | Publication date |
---|---|
WO2005064843A1 (ja) | 2005-07-14 |
JPWO2005064843A1 (ja) | 2007-12-20 |
TW200531495A (en) | 2005-09-16 |
EP1699161A1 (en) | 2006-09-06 |
US20070143388A1 (en) | 2007-06-21 |
US20070121934A1 (en) | 2007-05-31 |
JP4668796B2 (ja) | 2011-04-13 |
TW200527925A (en) | 2005-08-16 |
JPWO2005064844A1 (ja) | 2007-12-20 |
US7706528B2 (en) | 2010-04-27 |
WO2005064844A1 (ja) | 2005-07-14 |
KR20060126705A (ko) | 2006-12-08 |
EP1699160A1 (en) | 2006-09-06 |
US7634084B2 (en) | 2009-12-15 |
KR20060129302A (ko) | 2006-12-15 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
JP4668795B2 (ja) | 素数算出装置、鍵発行システム及び素数算出方法 | |
Eastlake 3rd et al. | Randomness requirements for security | |
JP4741503B2 (ja) | 公開鍵を検証可能に生成する方法及び装置 | |
JP3339688B2 (ja) | 非決定論的ミクスチャー発生器ストリーム暗号化システム | |
US7020776B2 (en) | Cryptosystem based on a Jacobian of a curve | |
CN102013980A (zh) | 需要采用穷举法解密的随机加密方法 | |
KR20020091059A (ko) | 중매인의 사기 가능성을 감소시키면서 익명의 사용자를인증하는 방법 | |
TW201320700A (zh) | 署名驗證裝置、署名驗證方法、程式及記錄媒體 | |
US9680647B2 (en) | Method of using a token in cryptography | |
JP2014052588A (ja) | 情報処理装置、情報処理方法及びコンピュータプログラム | |
CN111512590B (zh) | 用于密码认证的同态加密 | |
JP6041864B2 (ja) | データの暗号化のための方法、コンピュータ・プログラム、および装置 | |
Cortez et al. | Cryptographic randomness test of the modified hashing function of SHA256 to address length extension attack | |
JP5171787B2 (ja) | サインクリプションシステムおよびサインクリプション生成方法 | |
JP2021072593A (ja) | 暗号処理システム及び暗号処理方法 | |
CN110266478B (zh) | 一种信息处理方法、电子设备 | |
Eastlake 3rd et al. | Rfc 4086: randomness requirements for security | |
Yang et al. | A provably secure and efficient strong designated verifier signature scheme | |
JP4102090B2 (ja) | 情報セキュリティ装置、素数生成装置及び素数生成方法 | |
JP2005003745A (ja) | 乱数生成装置とその方法、プログラム、および暗号処理装置 | |
Rahouma | Reviewing and applying security services with non-english letter coding to secure software applications in light of software trade-offs | |
JP3881273B2 (ja) | 暗号鍵生成装置、暗号鍵生成プログラムおよびそのプログラムを記録した記録媒体 | |
CN115606148A (zh) | 与椭圆曲线操作相关的信息泄漏减轻 | |
JPH1078864A (ja) | 乱数生成器 | |
JP2000200038A (ja) | 素数生成方法及び装置並びにrsa暗号化方法及び記録媒体 |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20071016 |
|
A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20101012 |
|
A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20101126 |
|
TRDD | Decision of grant or rejection written | ||
A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20101221 |
|
A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20110113 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140121 Year of fee payment: 3 |
|
R150 | Certificate of patent or registration of utility model |
Ref document number: 4668795 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |