(57)【要約】      （修正有）【課題】擬似的に公開鍵暗号系を安価に実現する方法およびシステムを提供する。【解決手段】秘密鍵暗号系と耐タンパ性のあるハードウェアを用い、擬似的に公開鍵暗号系を安価に実現する。各ユーザは、それぞれ以下のような同一な機能を持つハードウェアが装備された機器を用い通信を行う。すなわち、あるID と鍵の対応付けを持ち、ユーザからの要求によりID を発効、記憶し、そのID に対応付けられた鍵で復号およびMAC(メッセージ認証子) の生成を行う。また、任意のID を用いた暗号化およびMAC の検証はできるが、復号およびMAC の生成はできない。ユーザはそのID を公開しておく。メッセージの送り手は、メッセージの受け手の公開されたID を用い、同じ機能を持つハードウェアを用いてメッセージを暗号化する。第三者は、ハードウェア内のメカニズムを分析する以外にそのID を用いて復号を行うことはできないが、そのような行為に対してハードウェアは自己を破壊する。【選択図】図２
2006174356.tif 000002
【特許請求の範囲】
【請求項１】
ユーザからの要求に応じて、IDの発効、暗号化、認証を行う暗号化・認証部と、電圧変化または圧力変化を感知し、前記暗号化・認証部を電気的に破壊するタンパリング検出部を有する耐タンパ性ハードウェアを含む装置であって、前記暗号化・認証部が、
ユーザの要求に応じ、IDを発効し、前記IDを記憶部に記憶する、ID発効・登録部と、
IDに対応した鍵を１対１関数を用いて生成し出力する、鍵生成部と、
ユーザの複号あるいはメッセージ認証子生成の要求に応じて、入力IDとID記憶部に記憶されたIDを比較し、一致した場合、前記鍵生成部にIDを渡し、前記鍵生成部から生成された鍵を出力する、第１鍵取得部と、
ユーザの暗号化あるいはメッセージ認証子付メッセージ検証の要求に応じて、前記鍵生成部に入力IDを渡し、前記鍵生成部から生成された鍵を出力する、第２鍵取得部と、
入力IDを第１鍵取得部に渡し、前記第１鍵取得部から出力された鍵を用いて、入力されたメッセージのメッセージ認証子を計算し出力する、メッセージ認証子生成部と、
入力IDを第２鍵取得部に渡し、前記第２鍵取得部から出力された鍵を用いて、入力されたメッセージのメッセージ認証子を計算し、得られたメッセージ認証子と入力されたメッセージ認証子を比較し、一致した場合、検証が成功したこと表す情報をユーザに返す、メッセージ認証子検証部と、
入力IDを第２鍵取得部に渡し、前記第２鍵取得部から出力された鍵を用いて、入力された平文の暗号化を行い、結果をユーザに返す、暗号化部と、
入力IDを第１鍵取得部に渡し、前記第１鍵取得部から出力された鍵を用いて、入力された暗号文を復号して出力する、復号部と、
を有する、装置
【請求項２】
前記暗号化・認証部が、シード記憶部を有し、前記鍵生成部が前記シード記憶部に記憶されたシード及び前記ID記憶部に記憶されたIDを基に鍵を生成し出力する、請求項１記載の装置
【請求項３】
前記ID発効・登録部が、ID を発効する際に冗長な情報をIDに含ませることを特徴とする、請求項１記載の装置。
【請求項４】
前記暗号化・認証部が、さらに１回書込可能記憶領域を有し、前記IDを前記１回書込可能記憶領域に書き込むことによりIDを登録可能とする、請求項１記載の装置。
【請求項５】
前記IDの発効・登録を鍵生成機関のみが行うことを特徴とする、請求項１記載の装置。
【請求項６】
ユーザからの要求に応じて、IDの発効、暗号化、認証を行う暗号化・認証部と、電圧変化または圧力変化を感知し、前記暗号化・認証部を電気的に破壊するタンパリング検出部を有する耐タンパ性ハードウェアを含む装置を用いて擬似公開鍵暗号を行う方法であって、前記装置の前記暗号化・認証部が、
ユーザの要求に応じ、IDを発効し、前記IDを記憶部に記憶する、ID発効・登録部と、
IDに対応した鍵を１対１関数を用いて生成し出力する、鍵生成部と、
ユーザの複号あるいはメッセージ認証子生成の要求に応じて、入力IDとID記憶部に記憶されたIDを比較し、一致した場合、前記鍵生成部にIDを渡し、前記鍵生成部から生成された鍵を出力する、第１鍵取得部と、
ユーザの暗号化あるいはメッセージ認証子付メッセージ検証の要求に応じて、前記鍵生成部に入力IDを渡し、前記鍵生成部から生成された鍵を出力する、第２鍵取得部と、
入力IDを第１鍵取得部に渡し、前記第１鍵取得部から出力された鍵を用いて、入力されたメッセージのメッセージ認証子を計算し出力する、メッセージ認証子生成部と、
入力IDを第２鍵取得部に渡し、前記第２鍵取得部から出力された鍵を用いて、入力されたメッセージのメッセージ認証子を計算し、得られたメッセージ認証子と入力されたメッセージ認証子を比較し、一致した場合、検証が成功したこと表す情報をユーザに返す、メッセージ認証子検証部と、
入力IDを第２鍵取得部に渡し、前記第２鍵取得部から出力された鍵を用いて、入力された平文の暗号化を行い、結果をユーザに返す、暗号化部と、
入力IDを第１鍵取得部に渡し、前記第１鍵取得部から出力された鍵を用いて、入力された暗号文を復号して出力する、復号部と、
を有しており、
前記方法は、前記装置Ａ，Ｂを有する送信ユーザおよび受信ユーザ間でメッセージを送信するにあたり、
送信ユーザID公開のため、装置Ａが送信ユーザIDを選択、記憶し、送信ユーザに返す段階と、
受信ユーザID公開のため、装置Ｂが受信ユーザIDを選択、記憶し、受信ユーザに返す段階と、
装置Ａが送信ユーザIDに対応する鍵を取得し、メッセージ認証子を生成し、送信ユーザに返す段階と
送信ユーザからの暗号化の要求に応じて、装置Ａが受信ユーザIDに対応する鍵を取得し、メッセージとメッセージ認証子を暗号化し、送信ユーザに返す段階と、
受信ユーザの暗号の復号要求に応じて、装置Ｂが受信ユーザIDに対応する鍵を取得し、受信メッセージを復号し、受信ユーザに返す段階と、
受信ユーザのメッセージ認証子検証要求に応じて、装置Ｂが送信ユーザIDに対応する鍵を取得し、メッセージ認証子を検証し、その結果を受信ユーザに返す段階と
を有する、擬似公開鍵暗号方法。
【請求項７】
前記暗号化・認証部が、シード記憶部を有し、前記鍵生成部が前記シード記憶部に記憶されたシード及び前記ID記憶部に記憶されたIDを基に鍵を生成し出力する、請求項６記載の方法
【請求項８】
前記ID発効・登録部が、ID を発効する際に冗長な情報をIDに含ませることを特徴とする、請求項６記載の方法。
【請求項９】
前記暗号化・認証部が、さらに１回書込可能記憶領域を有し、前記IDを前記１回書込可能記憶領域に書き込むことによりIDを登録可能とする、請求項６記載の方法。
【請求項１０】
前記IDの発効・登録を鍵生成機関のみが行うことを特徴とする、請求項６記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号方法およびシステムに関し、特に擬似的に公開鍵暗号系を安価に実現する方法およびシステムに関する。
【背景技術】
【０００２】
今日の暗号化技術の中でも重要な公開鍵暗号方式は、暗号化、署名、認証などの用途に広く用いられている。公開鍵暗号系を実現するアルゴリズムは、一般的に、計算に必要なコストが非常に大きい。公開鍵暗号系を実現する実用的な方法の一つがRSA 暗号である。RSA では2 つの大きな素数の積であるn のオイラー関数値から得られる数（暗号化指数、復号指数）により平文または暗号文をべき乗し、n に対する剰余を求める演算が必要であり、この演算のコストは非常に高い。鍵の安全性を高めるためにはn のビット数を大きくする必要があるが、ビット数の大きいRSA 暗号では、計算にかかるコストが莫大になる。高速性を追求するために、演算を専用ハードウェアで行うなどの措置があるが、一方で、開発費、製造費、製品の柔軟性等に負荷を与えることになる。このような事情のため、公開鍵を用いた暗号系はコストが高く、安価に大量生産が行われるような装置への組み込みは難しい。
また、RSA に比べて少ないビット数で同等の強度を持つ楕円曲線暗号が知られている。しかし、暗号化に必要な演算（有限体上に定義された楕円曲線上の点のスカラー倍等）のコストはべき乗剰余と比べて低いものの、高価な演算を必要とする点は同様であり、安価に大量生産が行われるような装置への組み込みは依然として難しい。さらに、秘密鍵暗号系と耐タンパ性ハードウェアを使用し、公開鍵暗号系を実現する方法が提案されている。即ち、受信者は自身の秘密鍵を第三者機関の秘密鍵で暗号化し、公開する。送信者はそれを第三者機関の秘密鍵で復号し、得られた受信者の秘密鍵でメッセージを暗号化し、送信する。受信者はそれを自身の秘密鍵で復号する。第三者機関の秘密鍵による暗号化と、第三者機関の秘密鍵による復号および受信者の秘密鍵による暗号化は耐タンパ性ハードウェア内で行われるため、セキュリティは確保される。しかし、この方法は、送信者と受信者で異なるハードウェアを使用しなければならず、同一のハードウェアを使用するためには双方の秘密鍵を必要とする。ID を公開するという点では、ID-based cryptosystem などの、認証機関を通さずに公開鍵を配布する手法と類似点がある。この方法は、鍵生成機関がユーザに対する一意なID からそのユーザの私有鍵を生成し、誰でもユーザのID からそのユーザの公開鍵を生成できる。この方法は公開鍵の配布に関して便宜が図られているが、メッセージの暗号化・復号に関して、RSA 等における落し戸付き一方向関数の性質を利用しており、それらの処理に関するコストは一般の公開鍵暗号系と変わるところがない。
【０００３】
【特許文献１】特開２００４−７０７１２
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の解決しようとする課題は、擬似的に公開鍵暗号系を安価に実現する方法およびシステムを提供することである。
また別の課題は、公開鍵を用いた暗号化情報伝達および署名付きの情報伝達をより安価に実現できる方法およびシステムを提供することである。
また別の課題は、署名を頻繁に行い、処理に即時性が要求されるモバイル端末などの端末上で、高いセキュリティ保持して情報処理・伝達を可能とする方法およびシステムを提供することである。
また別の課題は、高価な演算を必要とする関数を擬似的に実現する方法およびシステムを提供することである。
【課題を解決するための手段】
【０００５】
本発明では、秘密鍵暗号系と耐タンパ性のあるハードウェアを用い、擬似的に公開鍵暗号系を安価に実現する。公開鍵暗号系の構成に不可欠とされる落し戸付き一方向関数は一般的に「高価」な演算を必要とするが、そのような関数を耐タンパ性のあるハードウェアを用いて事実上実現する。各ユーザは、それぞれ以下のような同一な機能を持つハードウェアが装備された機器を用い通信を行う。このハードウェアは、あるID と鍵の対応付けを持っており、ユーザからの要求によりID を発効、記憶し、そのID に対応付けられた鍵で復号およびメッセージ認証子(以降MAC:Message Authentication Codeと記載する) の生成を行うことができる。また、このハードウェアでは、任意のID を用いた暗号化およびMAC の検証はできるが、復号およびMAC の生成はできない。ユーザはそのID を公開しておく。暗号化の際は、メッセージの送り手は、メッセージの受け手の公開されたID を用い、同じ機能を持つハードウェアを用いてメッセージを暗号化する。第三者は、ハードウェア内のメカニズムを分析する以外にそのID を用いて復号を行うことはできないが、そのような行為に対してハードウェアは自己を破壊する機能を持っている。
対称な関数を用いる場合、基本的に、平文をP、暗号文をC、公開鍵をK1、私有鍵をK2 としたとき、K1 からK2 を導出することは困難である。
C =F(P) = H(P, K1)
P =F-1(C) = H(C, K2)
となる関数F で、K2 を知らないものにとってはF-1 の計算が事実上不可能となれば公開鍵暗号系が構成できる。本発明では、安価な演算による秘密鍵K の関数F を用意し、F の機能を耐タンパ性のあるハードウェア内に隠蔽する。また、一方で、K = G(ID) というハードウェア内に隠蔽された１対１関数を用意し、IDは秘密鍵の識別子として、
C = F(P) = H(P, G(ID))
P = F-1(C) = H(C, G(ID))
が成り立つようにする。このとき、ID を擬似的な公開鍵として公開し、暗号化またはMACの検証を行うときは、誰もがG(ID) を計算できるようにする。また復号またはMAC の生成を行うときは、そのID の正当な所有者のみがG(ID) を計算できるようにする。これによりハードウェアにより実現された落し戸付き一方向性関数F が構築され、擬似的に公開鍵暗号系が実現される。
【０００６】
本願の好適な装置としては、ユーザからの要求に応じて、IDの発効、暗号化、認証を行う暗号化・認証部と、電圧変化または圧力変化を感知し、前記暗号化・認証部を電気的に破壊するタンパリング検出部を有する耐タンパ性ハードウェアを含む装置を用いる。この装置で擬似公開鍵暗号を行う。前記装置の前記暗号化・認証部としては、ユーザの要求に応じ、IDを発効し、該IDを記憶部に記憶する、ID発効・登録部と、IDに対応した鍵を１対１関数を用いて生成し出力する、鍵生成部と、ユーザの複号あるいはメッセージ認証子生成の要求に応じて、入力IDとID記憶部に記憶されたIDを比較し、一致した場合、前記鍵生成部にIDを渡し、前記鍵生成部から生成された鍵を出力する、第１鍵取得部と、ユーザの暗号化あるいはメッセージ認証子付メッセージ検証の要求に応じて、前記鍵生成部に入力IDを渡し、前記鍵生成部から生成された鍵を出力する、第２鍵取得部と、入力IDを第１鍵取得部に渡し、前記第１鍵取得部から出力された鍵を用いて、入力されたメッセージのメッセージ認証子を計算し出力する、メッセージ認証子生成部と、入力IDを第２鍵取得部に渡し、前記第２鍵取得部から出力された鍵を用いて、入力されたメッセージのメッセージ認証子を計算し、得られたメッセージ認証子と入力されたメッセージ認証子を比較し、一致した場合、検証が成功したこと表す情報をユーザに返す、メッセージ認証子検証部と、入力IDを第２鍵取得部に渡し、前記第２鍵取得部から出力された鍵を用いて、入力された平文の暗号化を行い、結果をユーザに返す、暗号化部と、入力IDを第１鍵取得部に渡し、前記第１鍵取得部から出力された鍵を用いて、入力された暗号文を復号して出力する、復号部を有している。
【０００７】
この装置を用いて擬似公開鍵暗号を行う方法は以下の段階を有する。前記装置Ａ，Ｂを有する送信ユーザおよび受信ユーザ間でメッセージを送信するにあたり、送信ユーザID公開のため、装置Ａが送信ユーザIDを選択、記憶し、送信ユーザに返す段階と、受信ユーザID公開のため、装置Ｂが受信ユーザIDを選択、記憶し、受信ユーザに返す段階と、装置Ａが送信ユーザIDに対応する鍵を取得し、メッセージ認証子を生成し、送信ユーザに返す段階と、送信ユーザからの暗号化の要求に応じて、装置Ａが受信ユーザIDに対応する鍵を取得し、メッセージとメッセージ認証子を暗号化し、送信ユーザに返す段階と、受信ユーザの暗号の復号要求に応じて、装置Ｂが受信ユーザIDに対応する鍵を取得し、受信メッセージを復号し、受信ユーザに返す段階と、受信ユーザのメッセージ認証子検証要求に応じて、装置Ｂが送信ユーザIDに対応する鍵を取得し、メッセージ認証子を検証し、その結果を受信ユーザに返す段階とを有することを特徴とする。なお上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【０００８】
本発明により、公開鍵を用いた暗号化情報伝達および署名付きの情報伝達を安く実現できる。近年ますます用途が広がっているモバイル端末上や、特に廉価で、大量に流通し、署名を頻繁に行い、処理に即時性が要求される端末上に、本発明を実現することで、そのような端末上においても、高いセキュリティ管理が必要な情報処理・伝達を可能とすることができる。
【発明を実施するための最良の形態】
【０００９】
本発明のハードウェア構成図を図１に示す。システム１００は暗号化・認証部１０１とタンパリング検出部１０２を内蔵した本システム全体である。暗号化・認証部１０１は、ユーザからの要求に応じ、IDの発効、暗号化、認証等のサービスを行う。タンパリング検出部１０２は、ユーザがシステム１００の内部回路を解析しようとしたときに生じる電圧変化、圧力変化を感知し、暗号化・認証部１０１を電気的に破壊する。
図２は図１における暗号化・認証部１０１の詳細を表した図である。ID発効・登録部２０１は、ユーザの要求に応じてあるユニークなIDを発効し、これをID記憶部２０６に記憶させる。鍵生成部２１０は、入力となるID及びシード記憶部２０９に記憶されたシードを基に鍵を生成し出力する。第１鍵取得部２０７は、ユーザが複号あるいはMACの生成を行う場合に、入力となるIDとID記憶部２０６に記憶されたIDを比較し、これが同一であれば鍵生成部２１０にIDを渡し、鍵生成部２１０から返却された鍵を出力する。同一でない場合はエラーを返す。第２鍵取得部２０８は、ユーザが暗号化あるいはMAC付きメッセージの検証を行う場合に、鍵生成部２１０の入力となるIDを渡し、鍵生成部から返却された鍵を出力する。MAC生成部２０２は、メッセージとIDを入力とし、このIDを第１鍵取得部２０７に渡し鍵を得る。鍵取得部がエラーを返さなかった場合、この鍵を基にメッセージのMACを計算し出力する。鍵取得部がエラーを返した場合、ユーザにエラーを返す。MAC検証部２０４は、メッセージとMACとIDを入力とし、このIDを第２鍵取得部２０８に渡し鍵を得る。この鍵を基にメッセージのMACを計算し、得られたMACと入力されたMACを比較する。これらが同一の場合、検証が成功したこと表す情報をユーザに返す。そうでない場合、検証が失敗したこと表す情報をユーザに返す。暗号化部２０５は、平文とIDを入力とし、このIDを第２鍵取得部２０８に渡し鍵を得る。この鍵を基に平文の暗号化を行い、結果をユーザに返す。復号部２０３は、暗号文とIDを入力とし、このIDを第１鍵取得部２０７に渡し鍵を得る。鍵取得部がエラーを返さなかった場合、この鍵を基に暗号文を復号し、出力する。鍵取得部がエラーを返した場合、ユーザにエラーを返す。
上記の説明で理解されるように本発明のハードウェアは特定の鍵により暗号化・復号およびMAC の生成・検証を行う機能とハッキング操作に対する耐タンパ性を有している。またインターフェースとしては
・ユーザの要求により、鍵と対応付けられたID を発効・登録するインタフェース
・与えられたID により、そのID が登録されている場合に限りメッセージを復号するインタフェース
・復号されたメッセージからMAC を生成するインタフェース、
・与えられたID により、メッセージを暗号化するインタフェース
・メッセージのMAC を検証するインタフェース
を有している。
【００１０】
次に本発明における情報の交換方法について説明する。暗号化されたメッセージのやりとりは以下のように行われる。まず、メッセージの受信者は図１のシステム１００が組み込まれた装置に、ID を発効するよう要求し、システム１００はある鍵に対応付けされたID をユーザに渡し、登録する。受信者は受け取ったID を公開する。メッセージの送信者は、公開されたID を用い、同じ機能を持つシステム１００が組み込まれた装置を通して、送りたいメッセージを暗号化する。受信者は、事実上、自分だけがそのメッセージを復号できる。
MAC が付加されたメッセージのやりとりは以下のように行われる。まず、メッセージの送信者はシステム１００が組み込まれた装置に、ID を発効するよう要求し、システム１００はある鍵に対応付けされたID をユーザに渡し、登録する。送信者は、受け取ったID を用い、同じシステム１００を通して、送りたいメッセージに対してMAC を生成する。送信者は、事実上、自分だけがそのMAC を生成できる。送信者はメッセージ、MAC、ID を送る。メッセージの受信者は、受け取ったID を用い、同じ機能を持つシステム１００が組み込まれた装置を通し、受け取ったメッセージに対する受け取ったMAC を検証する。
【００１１】
本発明の安全性をさらに高める方法について説明する。公開鍵暗号における一般的な問題ではあるが、受信者だけがメッセージを復号できる、および送信者だけがMAC を生成できるために、同一のID を他人に悪用されないことが望ましい。このために以下のような方法をとる。
・２次符号化による鍵の稀釈。
ID を発効するときに、冗長な情報を含むことでエントロピーを高めて符号化する。これにより、同一のID がユーザに渡される可能性を非常に低くできる。また、符号化アルゴリズムに個々の装置ごとにバラツキを与え、逆符号化を難しくする。これにより、悪意のある者が公開されたID と、自分のシステム１００に登録されたID が同一であることを特定するのは非常に難しくなる。また、復号の不自然な失敗を不正行為とみなし、これを検出した場合に機能を停止することで、悪意のある者がID の同一性を確かめるために復号を行うことを事実上防止できる。例えば、ランダム値をパディングする方法でこの仕組みを実現する。オリジナルなIDの空間をX ビットとし、鍵を希釈するためにさらにY ビットの空間を追加する。この追加空間には、オリジナルなID を発効するとき、ランダムなY ビットの数を入れておく。そうしてできた (X + Y) ビットの情報をシャッフルして、公開すべきID とする。このシャッフルはシフトや入れ換えを組み合わせた単純なものでよいが、アルゴリズムは耐タンパ性システム１００内に隠蔽しておく。こうすると、X ビットの鍵をそのまま使う場合に比べて、同一の鍵が発効される確率を2^Y の1 にできる。公開された (X + Y)ビットの鍵からX ビットのオリジナルな鍵は、やはり耐タンパ性ハードウェア内に逆演算アルゴリズムを実装し、冗長に付加された空間を取り除くことで容易に実装できる。
・ID の登録。発効されたID を認証機関が有効化する。
認証機関がID の唯一性を保証することで、ID の不正使用を防止する。
・ID 発効の制限。同一ID が発効される事態の抑止手段として、発効回数の制限、または発効に対する課金等を行う。
・一度ID が発効された機器そのものを他人が使用することを防ぐため、機器は使用のために使用者の認証を必要とするようにする。
【００１２】
ID-based cryptosystem と組み合わせて本発明を実現する方法を説明する。本発明のID は「個人のID」ではなく「鍵のID」として機能している。従って、一般的には、本発明はID の公開のために、他の（ID-based ではない）公開鍵暗号系と同様に認証機関を必要とする。一方、ID-based cryptosystem の目的は、本発明の目的とは直交するため、お互いを組み合わせて用いることも可能である。これは、鍵生成機関がユーザの私有鍵を生成する際に、「個人のID」が「鍵のID」となるように工夫すればよい。そのためには、例えば、鍵生成機関だけが任意のID を発効・登録できるようにする。この場合、認証機関を通さずに公開鍵を知ることができ、さらに安価に暗号化等が行えるシステムが構築できる。
【実施例１】
【００１３】
システム１００に十分な数の鍵を格納できる場合の実施例（各インタフェース、送受信プロトコルを含む）を図３を使用して説明する。ユーザＡとユーザＢが図１のシステム１００（ハードウェアＡ、ハードウェアＢ）を使用し通信するとする。またシステム１００には十分な数の鍵が格納され、それぞれに固有のID が付与されているとする。ハードウェアが同一であればIDと鍵のマッピングはすべて同一となる。
ユーザＡはハードウェアＡにID を要求する（３１０）。ハードウェアＡはID 空間からランダムにID（以下、ID-A）を選択（３２０）し、ユーザＡに返す。また、ID 記憶部に格納する。ユーザＡはID-A を公開する。一方、ユーザＢも事前にユーザＡと同様の処理を行っておく。即ち、ユーザＢはハードウェアＢにID を要求する（３１０）。ハードウェアＢはID 空間からランダムにID（以下、ID-B）を選択し、ユーザＡに返す。また、ID 記憶部に格納する（３３０）。ユーザＢはID-B を公開する。ユーザＡがユーザＢにメッセージを送信するとする。メッセージにはまずユーザＡの鍵でMAC が付与され、次にユーザＢの鍵で暗号化が行われるとする。MAC や暗号化のアルゴリズムについては本願の構成を何ら変更することなく任意に選ぶことができる。例えば、HMAC-SHA1 やAESをを使用してもよい。
ユーザＡは次の手順で送信メッセージを作成する。ユーザＡはハードウェアＡにメッセージとID-A を渡し、MAC の生成を要求する。ハードウェアＡはID 記憶部にID-A が格納されているか確認する（３４０）。ID-A が格納されている場合は、鍵記憶部からID-A に対応する鍵を取得（３５０）し、MAC を生成（３６０）し、ユーザＡに返す。ID-A が格納されていない場合は、ユーザＡにエラーを返す。ユーザＡはハードウェアＡに (メッセージ | MAC) とID-B を渡し、暗号化を要求する。ハードウェアＡは鍵記憶部からID-B に対応する鍵を取得し、(メッセージ | MAC) を暗号化（３７０）し、ユーザＡに返す。
一方、ユーザＢは次の手順で受信メッセージを処理する。ユーザＢはハードウェアＢに受信メッセージとID-B を渡し、復号を要求する。ハードウェアＢはID 記憶部にID-B が格納されているか確認する（３４０）。ID-B が格納されている場合は、鍵記憶部からID-B に対応する鍵を取得（３５０）し、受信メッセージを復号（３８０）し、ユーザＢに返す。ID-B が格納されていない場合は、ユーザＢにエラーを返す。ユーザＢはハードウェアＢにメッセージ、MAC、ID-A を渡し、MAC の検証を要求する。ハードウェアＢは鍵記憶部からID-A に対応する鍵を取得し、MAC を検証（３９０）し、その結果をユーザＢに返す。
【実施例２】
【００１４】
実際上は十分な数の鍵を格納できるような記憶容量を仮定できないことが多い。システム１００に十分な数の鍵を格納できない場合の実施例を図４を使用して説明する。システム１００には１つの値（以下、シード）だけを格納し、鍵はシードとID から適宜生成するようにする。任意のハッシュアルゴリズム（例えば、SHA-1）を使用し、(ID | シード) のハッシュ値を鍵とする。このようにすると、ユーザＡが送信メッセージを作成する手順は次のようになる。
ユーザＡ、ＢがＩＤの要求を行いハードウェアがＩＤを選択し記憶し、各ユーザが公開するところまでは上記実施例と同じである。ユーザＡがユーザＢにメッセージを送信するとする。ユーザＡは送信メッセージを作成するにあたりハードウェアＡにメッセージとID-A を渡し、MAC の生成を要求する。ハードウェアＡはID 記憶部にID-A が格納されているか確認する（４４０）。ハードウェアＡはID-A が格納されている場合は、シードとID-A から鍵を生成（４５０）し、MAC を生成（４６０）し、ユーザＡに返す。ID-A が格納されていない場合は、ユーザＡにエラーを返す。ユーザＡはハードウェアＡに (メッセージ | MAC) とID-B を渡し、暗号化を要求する。ハードウェアＡはシードとID-B から鍵を生成し、(メッセージ | MAC) を暗号化（４７０）し、ユーザＡに返す。
一方、ユーザＢが受信メッセージを処理する手順は次のようになる。ユーザＢはハードウェアＢに受信メッセージとID-B を渡し、復号を要求する。ハードウェアＢはID 記憶部にID-B が格納されているか確認する（４４０）。ID-B が格納されている場合は、シードとID-B から鍵を生成（４５０）し、受信メッセージを復号（４８０）し、ユーザＢに返す。ID-B が格納されていない場合は、ユーザＢにエラーを返す。ユーザＢはハードウェアＢにメッセージ、MAC、ID-A を渡し、MAC の検証を要求する。ハードウェアＢはシードとID-A から鍵を生成し、MAC を検証（４９０）し、その結果をユーザＢに返す。
【実施例３】
【００１５】
上記２つに実施例ではID がランダムに選択される場合を示した。次に図５を使用して本発明をID-based cryptosystem に応用する例を示す。その場合、ユーザＡが事前に行っておく処理は次のようになる。ユーザＡはID格納機関５２０にハードウェアＡとID-A を渡し、ハードウェアへのID の格納を要求する（５１０）。ID格納機関はハードウェアＡにID-A を渡し、ID の格納を要求する。ハードウェアＡはID-A をID 記憶部に格納する。一方、ユーザＢが事前に行っておく処理も同様になる。即ち、ユーザＢはID格納機関５２０にハードウェアＢとID-B を渡し、ハードウェアへのID の格納を要求する（５１０）。ID格納機関はハードウェアＢにID-B を渡し、ID の格納を要求する。ハードウェアＢはID-B をID 記憶部に格納する。なお、ユーザＡが送信メッセージを作成する手順およびユーザＢが受信メッセージを処理する手順は実施例１または実施例２と同様である。
【実施例４】
【００１６】
実施例３では、ID-based cryptosystem における一般的な手順を示した。これを携帯電話に適用する場合を例にとり、IDの獲得と機器の受け渡しがより効率的な手順を図６に示す。ここでは、ID格納のメカニズムは、機器のメーカーが機器へのID格納の一回性を保障した上で小売店に販売を委託し、小売店がインフラの協力を得て妥当でユニークなIDを得て機器に格納し、ユーザに渡すことで実現されている。具体的には、まず、電話番号をID とする。機器のメーカーはステップ６１０でID（電話番号）から鍵を得るとなる１対１関数f を１つ決める。次にステップ６２０で、f(ID) を耐タンパ性のある装置に内蔵する。機器のメーカーは１回書込可能（write once）な記憶領域を前記装置内に用意しておく。最後にステップ６３０で小売店がそこにID を書き込んで機器に登録し、f(ID) の入力となるようにしておく。ここでは、実施例１または実施例２で示したのと同様、そのID が登録された機器のみでf(ID) によるメッセージの復号、MAC の生成が可能である。一方、ID が登録されてない機器では、メッセージのf(ID) による暗号化が可能である。また、MAC の検証が可能である。
メッセージのやり取りは次のようになる。ユーザA, B はそれぞれ携帯電話を購入し、ユニークな電話番号NA, NB をそれぞれ得る。暗号化の場合、ユーザA はf(NB) を鍵としてメッセージM を暗号化する。これをE(M) とし、ユーザB に送信する。ユーザB はf(NB) を用い、E(M) を復号する。f(NB) で復号を行えるのは、ユーザB のみである。一方、署名の場合、ユーザA はf(NA) を鍵としてメッセージM のMAC を生成し、M とMAC をユーザBに送信する。ここで、f(NA) を使い、M のMAC を生成できるのは、ユーザA だけである。ユーザB は送信されたメッセージM とMAC の検証を行い、ユーザA による署名を確認できる。なお、同様の仕組みにより、携帯電話以外にも適用できる。例えば情報家電がインターネットに接続される場合は、ID にはIP アドレスやホスト名等が使える。
【図面の簡単な説明】
【００１７】
【図１】本発明のハードウェア構成図である。
【図２】暗号化・認証部の詳細を表した図である。
【図３】本発明の送受信プロトコルを説明する図である。
【図４】本発明の別の送受信プロトコルを説明する図である。
【図５】本発明をID-based cryptosystem に応用例を示す図である。
【図６】本発明を携帯電話に適用する例を示す図である。
【符号の説明】
【００１８】
１００  システム
１０１  暗号化・認証部
１０２  タンパリング検出部
２０１  発効・登録部
２０６  記憶部
２１０  鍵生成部
２０９  シード記憶部
２０７  第１鍵取得部
２０８  第２鍵取得部
２０２  生成部
２０４  検証部
２０５  暗号化部
２０３  復号部
５２０  ID格納機関
【図１】
2006174356.tif 000003
【図２】
2006174356.tif 000004
【図３】
2006174356.tif 000005
【図４】
2006174356.tif 000006
【図５】
2006174356.tif 000007
【図６】
2006174356.tif 000008