複雑性の低い装置の認証及び機密性を提供する方法及び装置
安全な認証、機密性、及び匿名のための暗号プロトコルを提供する方法及び装置。一実施形態において、このプロトコルは、少数の論理ゲートで実現され、簡単な装置上ですばやく実行され、軍事グレードの安全性を提供するように設計される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号化及び認証に関し、特に、複雑性の低い装置の暗号化及び認証に関する。
【背景技術】
【０００２】
無線周波数識別（ＲＦＩＤ）タグが、広く普及してきている。これらは、製品の追跡及び他の目的で利用されている。一般に、ＲＦＩＤが照会を受けた時、ＲＦＩＤは、ＲＦＩＤが貼付されている物体に関するデータを検索するのに利用されるその識別情報を供給する。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、いくつかのエンティティは、第三者からの照会に対してＲＦＩＤデータを開示せずに、ＲＦＩＤの利用が可能であることを望んでいる。例えば、米国政府は、国境検問所での認証書類の処理の促進を進めるため、パスポートの書類又はクレジットサイズのカードの中にＲＦＩＤチップを組み込むことを望んでいる。
【０００４】
現在のＲＦＩＤソリューションは、４つの主たる脆弱性を有している。第１は、一般に、ＲＦＩＤは認証を提供しない。第２に、権限のない第三者が、装置に対して照会を行いＲＦＩＤチップ上のデータを知ることが可能である。パスポートの場合には、そのＲＦＩＤに、個人情報盗難を可能にするその所有者の個人情報に関する充分なデータを含んでいるかもしれない。第３に、攻撃者はそのようにして、装置の対話を盗聴し、ＲＦＩＤチップ上のそのデータを取得することができるかもしれない。最後に、攻撃者は、ＲＦＩＤチップの特定の識別子を使用して、ある個人を一貫して追跡することができるかもしれない。
【課題を解決するための手段】
【０００５】
安全な認証、機密性、及び匿名のための暗号プロトコルを提供する方法及び装置について、説明される。一実施形態において、このプロトコルは、少数の論理ゲートで実現され、簡単な装置上ですばやく実行され、軍事グレードの安全性を提供するように設計される。
【発明を実施するための最良の形態】
【０００６】
本発明は、一例として示され、添付した図面の形態及び類似要素に関する参照数字等に制限されるものではない。
【０００７】
記載された方法及び装置は、多くの機密保護の要求に向けた低電力装置の暗号プロトコルである。また、暗号プロトコルは、この用途のための実行特性を維持する。特に、この暗号プロトコルを含む装置は、標準的な技術を使用して比較的安価に構成することが可能である。実現するのに多くの論理ゲートを必要としないので、パッシブ型のＲＦＩＤチップなどの低電力装置上で実現可能である。最後に、このプロトコルは、数多くの装置が同時に照会されることを可能にする。
【０００８】
このプロトコルは、以下に示す暗号の特徴の１つ以上を提供する能力を有する。
・認証。このプロトコルは、タグの信憑性を暗号的に検査するための情報を含むことが可能である。
・機密性。このプロトコルは、権限のない第三者がタグの識別子を知ることができないように、そのタグの識別子を保護することができる。
・アントレーサビリティ／難読化。一実施形態のプロトコルは、まったく同じ値には戻らない。すなわち、タグの識別子を取得するためのキーをリーダが知らない場合、そのリーダは、同一のタグと通信していることを話すことすらできない。
【０００９】
一実施形態において、楕円曲線暗号システム（ＥＣＣ）、より具体的にはパブリック／プライベート・キー対を使用する楕円曲線暗号処理を通して認証が提供される。一実施形態において、機密性は、タグ識別子を暗号化することによって提供される。一実施形態において、暗号化は、タグ識別子の暗号化キーを導き出すためのデフィーヘルマン（Diffie-Helman）ベースの機構を使用し、このキーでタグ識別子を暗号化して行われる。一実施形態において、アントレーサビリティは、暗号化キーを生成するのに使用されそれぞれ交換される乱数を生成することによって提供される。
【００１０】
一実施形態において、このアプリケーションは、コンピュータを使用して素体（prime field）上で実現される。単純化のため、いくつかの例は、単に、楕円曲線暗号（ＥＣＣ）又は素体のデフィーヘルマン問題について説明する。しかし、当業者の一人は、両方の方法、または２つの方法の組み合わせが、本発明によって使用されることが可能であることを理解するであろう。
【００１１】
このアプリケーションの例は、無線周波数識別（ＲＦＩＤ）リーダ及びタグを使用して実現されるシステムについて述べているが、本発明は、複雑性の低いいかなる装置を利用してもよい。
【００１２】
図１は、本発明に関する暗号サービスのコンポーネントの一実施形態を示すネットワーク図である。一実施形態において、ＲＦＩＤシステム１２０は、１つ以上の暗号ＲＦＩＤタグ１１０Ａ，１１０Ｂ，１１０Ｃを読み取るリーダを備えている。一実施形態において、ＲＦＩＤシステム１２０は、複数のＲＦＩＤタグ１１０Ａ−Ｃを同時に読み取る能力を有している。別の実施形態において、各タグは、順番に質問される。一実施形態において、ＲＦＩＤシステム１２０は、暗号システムを備えている。別の実施形態において、ＲＦＩＤシステム１２０は、リーダと結びついて、ここで記述された暗号機能を実行するための暗号システムとリンクされている。
【００１３】
リーダ１２０は、暗号ＲＦＩＤタグ１１０ＡからタグＩＤを要求する。一実施形態において、この要求は呼び掛けを含む。リーダは、暗号化された応答を受け取る。暗号化された応答は、適当なキーを持つシステム１２０によって解読され得る。タグＩＤの要求を繰り返し送信しても、スプーファーシステム１３０は、一致した応答を受信できない（なぜなら、応答は暗号化され難読化されているからである）。したがって、スプーファーシステム１３０は、暗号ＲＦＩＤタグ１１０ＡのタグＩＤを識別することができない。したがって、ＲＦＩＤタグ１１０Ａに関するデータを検索することができない。
【００１４】
一実施形態において、タグの応答を解読してタグＩＤを取得した後、ＲＦＩＤシステム１２０はタグＩＤに関するパブリックキーを検索する。一実施形態において、パブリックキーの検索は、ネットワーク１５０を介してアクセス可能なリモートシステム１６０によって実行される。また、キー検索は、ローカルシステムまたはＲＦＩＤシステム１２０自体に組み込むことが可能である。一実施形態において、パブリックキー検索サーバ１６０は、ＲＦＩＤシステムに対してローカルである。一実施形態において、パブリックキー検索サーバ１６０は、パブリックからアクセスできないプライベートサーバである。
【００１５】
一実施形態において、データベース１７０内の各ＲＦＩＤタグの記録は、タグ識別子（タグＩＤ）及びタグパブリックキーＱを含む。一実施形態において、その記録は、ＲＦＩＤが生成された時を示すタイムスタンプもまた含む。したがって、このデータは、タグの外部に決して格納されることのないタグプライベートキーを含まない。
【００１６】
図２は、低処理電力システム（ＬＰＰＳ）及び通信システム関連の一実施形態を示すブロック図である。ＬＰＰＳはＲＦＩＤタグであり、一方、通信システムはＲＦＩＤリーダである。
【００１７】
ＲＦＩＤタグ１１０は、トランシーバ２５０、または代わりに個別の受信及び送信ロジックを含んでいる。一実施形態において、トランシーバ２５０は、ＲＦＩＤトランシーバである。一実施形態において、ＰＬＬＳ２１０は、システム２２０から受信する入力信号によってトランシーバ２５０が電力供給されるのに充分に低い電力で動く。
【００１８】
初期化の間、暗号ロジック２５５は、タグ１１０のプライベートキーを計算し、そのプライベートキーはメモリ２６０に格納される。本明細書におけるプライベートキーという用語は、楕円曲線上の１点、またはデフィーヘルマン問題で使用される大きな素数を表す。バブリックキーは、プライベートキーにキー対を提供する関数または値である。
【００１９】
ＲＦＩＤタグ１１０は、ＲＦＩＤシステム１２０から、パブリックキー、又は別の実施形態では複数のパブリックキーを受信する。また、ＲＦＩＤタグ１１０は、そのタグの識別子（タグＩＤ）をシステム１２０から受信し、それらをメモリ２６０内に格納する。一実施形態において、プライベートキーは、Ｅ（Ｆ）のオーダと同じ長さの値であり、無作為に生成される。タグ１１０内の暗号ロジック２５５は、さらに、タグのプライベートキーに基づいてＲＦＩＤタグのパブリックキーを計算する。一実施形態において、このパブリックキーは、認証機関によって署名され、ＬＰＰＳ２１０の認証で使用される。
【００２０】
メモリ２６０は、リーダのタグＩＤ及びパブリックキー（初期化中に受信される）とともに、プライベートキー（タグの中で生成された乱数ａ）を格納するのに使用される。プライベートキー、パブリックキー、及びタグＩＤを格納し、認証関数を計算するのに必要なゲートの数は、キーの長さに比例する。したがって、安全性を確保しつつキーサイズを最小化するのは、興味があることである。したがって、一実施形態において、このシステムは、２進フィールドにおける１６３から３進フィールドにおける１０７までワードサイズの削減（システムの安全性を減らすことなくワード長の約３５％の減少）が可能な、Ｆとして３進フィールドを使用する。すなわち、２進ロジックゲートの代わりに３進ロジックゲートを使用することにより、より少ないロジックゲートが必要となり、そのいくつかの動作（乗算など）はより速くなる。
【００２１】
一実施形態において、このシステムは、改ざんロジック２６５を含む。改ざんロジック２６５は、改ざん防止機能を提供する。一実施形態において、すべてのタグは改ざん防止機能を有している。別の実施形態において、メモリ２６０のみ、またはブライベートキーが格納されるメモリ領域に、改ざん防止機能を備えている。一実施形態において、改ざん防止機能は、メモリの読み取りやバスのハッキングなどをシステムが検知したとき、そのメモリを消去するロジックを含んでもよい。一実施形態において、これはヒューズを使用して実現できる。
【００２２】
認証の使用中、暗号ロジック２５５は、呼び掛けを受信し、呼び掛けへの応答を計算する。呼び掛けへの応答は暗号化され、認証化され、応答の難読化される。これは、同じ呼び掛けが繰り返し送信された場合であっても、ＲＦＩＤタグ１１０からの応答が常に異なることを確実にする。一実施形態において、計算は、選択された有限フィールド上の選択された楕円曲線上で行われる。上記のとおり、一実施形態におけるこのフィールドは周知の２進フィールドである。
【００２３】
ＲＦＩＤシステム２２０は、ＲＦＩＤリーダ２１０を含み、ＲＦＩＤタグ２１０へ呼び掛けを送信する。呼び掛けは、乱数ジェネレータ２１５により生成された乱数に基づいて、呼び掛け計算器２２０によって生成される。一実施形態において、乱数は、Ｅのオーダの大きさと同じオーダの数字である。
【００２４】
ＲＦＩＤタグ２１０が呼び掛けに応答するとき、その応答は、暗号化されたタグＩＤ及び呼び掛け応答を含む。暗号計算器２３０は、暗号化された応答を解読し、応答からタグＩＤを取得するのに使用される。パブリックキー検索ロジック２２５は、データベース内のそのタグのパブリックキーを検索するのにタグＩＤを使用する。前述のように、データベースは、ＲＦＩＤシステム１２０の一部、ローカル、または遠隔かつネットワークを介してアクセス可能であってもよい。
【００２５】
暗号計算器２３０は、乱数を取得し、パブリックキーを使用してパブリックキー値を計算する。パブリックキー値は、ＲＦＩＤタグによって返された呼び掛け応答と等しいはずである。したがって、比較ロジック２３５は、ＲＦＩＤタグ２１０によって返された呼び掛け応答と、計算の結果との比較を行う。もし、値が一致した場合、ＲＦＩＤシステム１２０は、ＲＦＩＤタグ２１０を証明する。一実施形態において、検証ロジック２４０は、ＲＦＩＤタグ１１０が正当であることを示す適切な情報を出力する。一実施形態において、ＲＦＩＤシステム１２０は、ＲＦＩＤタグ１１０が有効であることを示す出力機構を有する。
【００２６】
図３は、暗号プロトコルを利用する一実施形態を示す概略フローチャートである。処理は、初期化で始まる。
【００２７】
ブロック３１０において、共通データが、タグとリーダとの間で共有される。タグは、例えば無線周波数識別（ＲＦＩＤ）タグのような、複雑性の低い処理装置である。リーダは、ＲＦＩＤリーダのような、タグとインターフェイスするように設計された装置である。一実施形態において、用語“リーダ”は、暗号サービスを提供するシステムとともに、タグと対話するシステムを示す。しかし、一実施形態において、これらの機能は分離され、ネットワークコネクション又は他の方法を介して結合された別々の装置によって実行される。共通データは、必要な楕円曲線、フィールド、及び楕円暗号化のポイント、または従来の暗号化のジェネレータ及び大きな素数を画定する。用語“オリジネータ”は、この発明において、大きな素数のジェネレータ及び楕円曲線暗号化で使用される楕円フィールド内のポイントを示すものとして使用される。
【００２８】
ブロック３１５において、タグとリーダの間でキーが共有される。一実施形態において、キーは、楕円暗号化または従来の大きな素数の暗号化を利用する１つ以上のパブリック／プライベート・キー対を含む。一実施形態において、３組のキー対が生成され、それぞれ、認証、暗号化、及び難読化用である。一実施形態において、タグは、自分自身のキーを生成する。
【００２９】
適当なプライベートキー及びパブリックキーが、ブロック３２０で、格納されると、初期化は完了する。一実施形態において、タグは、リーダのパブリックキー及び自分自身のプライベートキー及び識別情報を格納し、リーダは、自分自身のプライベートキーを格納する。一実施形態において、タグのパブリックキー及び識別情報が、別々のパブリックキー・ディレクトリに格納される。
【００３０】
以下の処理は、識別を目的としたタグのパブリックキーを取得する部分である。以下の処理、認証されたタグＩＤの供給に加えて、タグＩＤを暗号化する手段でタグＩＤを提供し、その値を難読化する。これは、スプーフィング・リーダが、同じ呼び掛けを複数回送信することによって暗号化の認識を試みた場合に、リターンデータが一致しないことを保証する。
【００３１】
ブロック３２５において、リーダがタグの呼び掛けを計算する。呼び掛けは、リーダがそのタグのタグＩＤを確認することを可能にする情報を引き出すように設計される。一実施形態において、呼び掛けは、乱数である。一実施形態において、呼び掛けは、選択された有限フィールド上の楕円曲線に沿った乱数である。
【００３２】
ブロック３３０で、呼び掛けに対する応答をタグが計算する。一実施形態において、呼び掛けに対する応答は、タグのプライベートキー掛ける呼び掛けである。
【００３３】
ブロック３３５で、タグは、呼び掛けに対する応答と、暗号化用、認証用及び機密性用の３つのキーで暗号化された３つの乱数と、の組み合わせの返信データを計算する。一実施形態において、タグは、２つの乱数（ｓとｕ）を生成し、キー（それぞれ暗号化と難読化）に従ってそれぞれを暗号化する。認証キーは、リーダのパブリックキーで暗号化される。そして、タグは、４つの乱数すべてを含む連結値を返信する。一実施形態において、返信の値は、タグの識別子を含む。
【００３４】
ブロック３４０で、タグからリターンデータを受け取ったリーダは、リターンデータからのｎ(タグＩＤ)を計算するのに、そのプライベートキーを利用する。
【００３５】
ブロック３４５で、そのタグＩＤを使用して、リーダは、そのタグのパブリックキーを検索する。
【００３６】
ブロック３５０で、リーダは、署名された呼び掛け応答が含まれているリターンデータを確認する。ブロック３５５の確認で、リーダがそのタグＩＤ（ｎ）を知っていて、このＩＤが、呼び掛けに対する応答により信頼できることが証明された場合、リーダは、ブロック３６０で、他の活動を実行するためにそのタグＩＤを利用することができる。例えば、タグＩＤは、別のデータベース内のデータを検索したり、タグの承認を確認したりするのに使用される。そして、ブロック３６５で、処理が終了する。
【００３７】
図４Ａ及びＢは、本発明に関するリーダ及びタグの初期化の一実施形態を示す信号フロー図である。このシステムは、楕円曲線暗号（ＥＣＣ）、または従来のパブリックキー暗号パラメータを使用する。
【００３８】
ブロック４０５で、タグとリーダは、暗号パラメータで初期化される。使用される暗号システムが楕円曲線システムの場合、一実施形態において、以下の値が決定される。
１．（タグ）認証用の第１楕円曲線ＥA及び有限フィールドＦA
２．（タグ）認証用の第１楕円曲線ＥA（ＦA）上の第１ポイントＰA＝（ｘA，ｙA）
３．（タグＩＤ）暗号化用の第２楕円曲線ＥE及び有限フィールドＦE
４．（タグＩＤ）暗号化用の第２楕円曲線ＥE（ＦE）上の第２ポイントＰE＝（ｘE，ｙE）
５．（タグＩＤ）難読化用の第３楕円曲線ＥO及び有限フィールドＦO
６．（タグＩＤ）難読化用の第３楕円曲線ＥO（ＦO）上の第３ポイントＰO＝（ｘO，ｙO）
【００３９】
ポイントのそれぞれのために、ＰA/E/Oを整数で乗算することによって生成される全ポイントのセットは、フィールド上の楕円曲線上のポイントの総数と同じサイズであるべきである。より正式には、｛Ｐi｜∃ｘ such that Ｐ＝ＰＡx｝セットのオーダは、ＥA（ＦA）のオーダと同じでなければならない。
【００４０】
一実施形態において、認証、暗号化、及び難読化機構は、上述の個別の楕円曲線、有限フィールド、及び／又は楕円曲線上のポイントを利用する。別の実施形態において、決定されたフィールド、曲線、及び／又はポイントは同一かもしれない。一実施形態において、同じ楕円曲線、フィールド、及びポイントは、すべての３つの暗号アスペクト（認証、暗号化、及び難読化）として使用される。これらのアスペクト、ＥA，ＥE，ＥO，ＦA，ＦE，ＦO，及びＰA，ＰE，ＰOは、タグ及びリーダを初期化するのに使用される。ＥＣＣの一方向性関数は、ｆ（ａ，Ｂ）＝ａ・Ｂである（ここでドット演算子はポイント乗算を示す。）。例えば、ａ・Ｂは“ポイントＢ掛ける整数ａ”を意味する。
【００４１】
従来の暗号化方法、大きな素体上の計算を使用する暗号化のために、一実施形態において、以下の値が定義される。
１．（タグ）認証用の素数ＱAを選択する。
２．（タグ）認証用のジェネレータｇA∈［２，ＱA−１］を選択する。
３．（タグＩＤ）暗号化用の素数ＱEを選択する。
４．（タグＩＤ）暗号化用のジェネレータｇE∈［２，ＱE−１］を選択する。
５．（タグＩＤ）難読化用の素数ＱOを選択する。
６．（タグＩＤ）難読化用のジェネレータｇO∈［２，ＱO−１］を選択する。
【００４２】
一実施形態において、ジェネレータ及び素数は、それぞれの値（認証、暗号化、及び難読化）と同一とすることができる。素体上の計算用の一方向性関数は、
ｆ（ａ，Ｂ）＝Ｂa ｍｏｄ ｐである。
【００４３】
ジェネレータｇA/E/O及びポイントＰA/E/Oは、オリジネータＯA/E/Oとして集合的に参照される。
【００４４】
上述のように、これらの暗号ジェネレータは、タグ及びリーダを初期化するのに使用される。リーダ／タグは暗号化の一形態として使用されることを注意すべきである。ここで、大きな素体上の楕円暗号化及び計算を説明した。しかし、確実な暗号化及び解読キー対を生成する代替的な暗号関数を使用することも可能である。
【００４５】
初期化は、種々の手段で起きる。一実施形態において、合意が必要とされないように、すべてのシステムコンポーネントは、予め同じパラメータでプログラミングされる。別の実施形態において、それぞれのシステムコンポーネントは、どのパラメータが通信のために使用されるかという完全な説明を受信するであろう。さらに別の実施形態において、よく知られている名称のパラメータの標準的なセットから使用されるパラメータについての２つのサイドが簡単に特定されるであろう。例えば、ＲＦＣ４４９２の５．１．１節を参照のこと（http://www.faqs.org/rfcs/rfc4492.html）。これは、いくつかの標準的な楕円曲線及びフィールドの１６ビット識別子を特定する。別の実施形態において、２つのサイドが、同意済み又は予め決められたパラメータ・セットからパラメータを選択するであろう。両方のコンポーネントがこれらのパラメータを持つことを保証する他の方法が使用されてもよい。
【００４６】
ブロック４１０で、リーダは、その暗号化キーとして乱数ｒを抽出する。ブロック４１５で、リーダは、キー対（Ｒ，ｒ）を生成するために、暗号化キーｒについてのパブリックキーである適合キーＲ＝ｆ（ｒ，ＰE）を計算する。
【００４７】
ブロック４２０で、リーダは、難読化キーとして第２乱数ｊを抽出する。ブロック４３０で、Ｊ＝ｆ（ｊ，ＰO）を計算することにより、難読化キー対（Ｊ，ｊ）が計算される。このようにして、リーダは、暗号化用のキー対（Ｒ，ｒ）と、タグの識別の難読化用の第２キー対（Ｊ，ｊ）を生成する。一実施形態において、Ｒ＝Ｊ、及びｒ＝ｊである。ｒ及びｊの値は、リーダ内に格納される。
【００４８】
ブロック４４０で、リーダは、初期化するようにタグに伝えるため、タグＩＤ（ｎ）に沿ったパブリックキー（Ｒ及びＪ）をタグに送信する。一実施形態において、ＲＦＩＤシステムは、乱数であるｎを選択する。一実施形態において、タグＩＤ値ｎは、キー（Ｒ及びＪ）の長さより短くなるように選択される。一実施形態において、初期化処理は、多くのタグと一緒に実行されることができる。
【００４９】
ブロック４４５で、ｎ，Ｒ，及びＪの値が、タグの内部メモリに保存される。上述のように、一実施形態において、内部メモリは安全なメモリである。一実施形態において、タグを破壊することなく暗号処理を通さない限り、内部メモリにアクセスすることができない。
【００５０】
ブロック４５０で、プライベートキーとしてタグによって乱数ａが選択され、タグの内部メモリに保存される。一実施形態において、内部メモリは、安全なメモリである。一実施形態において、タグＩＤとタグのプライベートキーのみが安全なメモリに格納される。
【００５１】
ブロック４５５で、タグは、パブリックキーＱ＝ｆ（ａ，ＰA）を計算する。ブロック４６０で、値Ｑは、リーダ／システムに送信される。一実施形態において、リーダ／システムは、タグのパグリックキーをバブリックキーディレクトリへ転送する（ブロック４６５）。ブロック４７０で、バブリックキーディレクトリは、値ｎ（タグＩＤ）についての値Ｑの値を格納する。ブロック４７５で、バブリックキーディレクトリは、その値が正しく格納されたことを認める。
【００５２】
図５は、暗号化、認証、及び難読化のタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。この処理は、ＲＦＩＤシステムがタグからデータを取得しようとしたときに初期化される。一実施形態において、ＲＦＩＤシステムは、１つ以上のＲＦＩＤタグと並行して同じ処理を実行することができる。
【００５３】
ブロック５１０で、ＲＦＩＤシステムは、乱数ｃを抽出する。ブロック５１５で、ＲＦＩＤシステムは、呼び掛けＣ＝ｆ（ｃ，ＰA）を計算する。呼び掛けＣは、乱数ｃの対である。一実施形態において、暗号化関数Ｅは、暗号テキストを生成するために普通テキストとキーのＸＯＲをとる。メッセージのために、ｎ及びポイントＰi、これは
である。この暗号化関数の選択のために、解読は、同じ方法：
で働く。ブロック５２０で、システムは、タグＩＤと、呼び掛けに対するタグ応答を要求するメッセージを送信する。このメッセージは、呼び掛けＣを含む。
【００５４】
ブロック５２５で、タグは、Ａ＝ｆ（ａ，Ｃ）を計算する。値ａは、ＲＦＩＤタグのプライベートキーである。
【００５５】
ブロック５３０で、タグは、乱数ｓを生成する。一実施形態において、乱数ｓは、乱数ジェネレータを使用して生成される。別の実施形態において、それは、物理的クローン不可関数（ＰＵＦ）を使用して生成される。ブロック５３５で、一実施形態において、Ｓ＝ｆ（ｓ，ＰE）が計算される。前述のように、ＰE＝（ｘE，ｙE）は、（タグＩＤ）暗号化用の第２楕円曲線ＥE（ＦE）上のポイントである。
【００５６】
ブロック５４０で、システムは、値ｋE＝ｆ（ｓ，Ｒ）を計算する。Ｒは、ＲＦＩＤシステムのパブリックキーの１つであり、ｓは、上記で生成された乱数である。ブロック５４２で、ＲＦＩＤタグは、Ｂ＝Ｅ（ｎ，ｋE）を計算する。値ｎはタグＩＤであり、上記のとおりｋE＝ｆ（ｓ，Ｒ）である。
【００５７】
一実施形態において、ブロック５４５で、システムは、第２乱数ｕを抽出する。ブロック５５０で、タグはＵ＝ｆ（ｕ，ＰO）を計算する。上記のとおり、ＰO＝（ｘO，ｙO）は、（タグＩＤ）難読化用の第３楕円曲線ＥO（ＦO）上のポイントである。ブロック５５５で、システムは、ｋO＝ｆ（ｕ，Ｊ）を計算する。ここで、ｕは第２乱数、ＪはＲＦＩＤリーダの第２パブリックキーである。
【００５８】
ブロック５６５で、タグはＧ＝ｆ（Ａ，ｋO）を計算する。Ａ＝ｆ（ａ，Ｃ）は、タグのプライベートキー及び呼びかけの関数であり、ｋO＝ｆ（ｕ，Ｊ）である
【００５９】
ブロック５７０で、タグは、値Ｓ，Ｕ，Ｂ及びＧを返す。ここで、Ｓ＝ｆ（ｓ，ＰE），Ｕ＝ｆ（ｕ，ＰO），Ｂ＝Ｅ（ｎ，ｋE），Ｇ＝ｆ（Ａ，ｋO）である。一実施形態において、タグは、これらの値の連結を返す。このプロトコルの特性の１つは、毎回異なる応答をタグが返すことばかりでなく（したがって、タグは追跡されない）、キーホルダ（権限を有するリーダ）は、リターンデータに基づいてタグの識別情報を確認することができることである。
【００６０】
そして、リーダは、以下の計算を実行する。
（５７２）プライベートキーｒと与えられた値Ｓを使用してｋE＝ｆ（ｒ，Ｓ）を計算する。
（５７４）プライベートキーｊと与えられた値Ｕを使用してｋO＝ｆ（ｊ，Ｕ）を計算する。
（５７６）計算値ｋEと与えられた値Ｂを使用してｎ＝Ｄ（Ｂ，ｋE）を計算する。
【００６１】
値ｎは、タグＩＤであり、これはブロック５８０で、パブリックキーディレクトリからタグｎのパブリックキーを要求するのに使用される。ブロック５８５で、パブリックキーディレクトリは、タグのパブリックキーＱを返す。そして、リーダは、与えられた値Ｇ、計算値ｋOを使用して（５９０）Ａ＝Ｄ（Ｇ，ｋO）を計算し、Ａ＝ｆ（ｃ，Ｑ）＝ｆ（ａ，Ｃ）であることを確認する。確認の結果、正しければ、リーダは、タグが証明されたものであり、タグＩＤが正確であることを知り、種々の検索、証明、他の機能でタグＩＤを使用することができる。
【００６２】
この例は、楕円曲線上の関数を説明したが、説明した暗号プロトコルは、大きな素数を代わりに利用することが可能である。大きい素数のために、それぞれのｆ（ｘ，Ｐ）は、ｆ（ｘ，ｇ）で置き換えられる。ここで、ｇは大きい素数のジェネレータである。
【００６３】
図６は、暗号化及び難読化の短縮化されたタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。この短縮化された処理は、ポイントを同じ値に設定することによって、いくつかの計算を簡単にしたものである。ブロック６１０で、ＲＦＩＤシステムは、乱数ｃを抽出する。ブロック６１５で、ＲＦＩＤシステムは、呼び掛けＣ＝ｆ（ｃ，ＰA）を計算する。呼び掛けＣは、乱数ｃの対である。ブロック６２０で、システムは、呼び掛けＣを含むタグの識別情報を要求するメッセージを送信する。
【００６４】
ブロック６２５で、タグは、Ａ＝ｆ（ａ，Ｃ）を計算する。値ａは、ＲＦＩＤタグのプライベートキーである。
【００６５】
ブロック６３０で、タグは、乱数ｓを生成する。一実施形態において、乱数ｓは、乱数ジェネレータを使用して生成される。別の実施形態において、乱数ｓは、物理的クローン不可関数（ＰＵＦ）を使用して生成される。ブロック６３５で、Ｓ＝ｆ（ｓ，ＰE）が計算される。上述のように、ＰE＝（ｘE，ｙE）は、（タグＩＤ）暗号化用の第２楕円曲線ＥE（ＦE）上のポイントである。
【００６６】
ブロック６４０で、Ｔ＝ｆ（ｓ，Ｒ）が計算される。Ｒは、ＲＦＩＤシステムのパブリックキーの１つであり、ｓは、上記で生成された乱数である。ブロック６４５で、タグが、ｋE，ｋO＝ｇ（Ｔ）を計算する。関数ｇ（）は、ｎ｜ＡのＸＯＲに対して充分に長い列を計算する。関数ｇ：ｋ→ｋ1，ｋ2は、長さｌの入力から長さｌの２つの値を生成するのに使用される。一実施形態において、この値は、擬似乱数であり、関数ｇ（）として、暗号的に聞こえるものかなにかを使用するのがベストである。
【００６７】
ブロック６５０で、ＲＦＩＤタグは、Ｂ＝Ｅ（ｎ，ｋE）を計算する。値ｎは、タグＩＤである。ここで、上記のように、ｋE＝ｆ（ｓ，Ｒ）である。ブロック６５５で、タグは、Ｇ＝ｆ（Ａ，ｋO）を計算する。Ａ＝ｆ（ａ，Ｃ）は、タグのプライベートキーと呼び掛けの関数である。
【００６８】
ブロック６６０で、タグは、値Ｓ，Ｂ，及びＧを返す。一実施形態において、タグは、これらの値の連結を返す。Ｓ＝ｆ（ｓ，ＰE），Ｂ＝Ｅ（ｎ，ｋE），Ｇ＝ｆ（Ａ，ｋO）である。
【００６９】
そして、リーダは、以下の計算を実行する。
（６６２）プライベートキーｒと与えられた値Ｓを使用して、Ｔ＝ｆ（ｒ，Ｓ）を計算する。
（６６４）ｋE，ｋO＝ｇ（Ｔ）を計算する。
（６６６）計算値ｋEと与えられた値Ｂを使用して、ｎ＝Ｄ（Ｂ，ｋE）を計算する。
（６６８）与えられた値Ｇと計算値ｋOを使用して、Ａ＝Ｄ（Ｇ，ｋO）を計算する。
【００７０】
値ｎはタグＩＤであり、これは、ブロック６７０で、パブリックキーディレクトリからタグｎのパブリックキーを要求するのに使用される。ブロック６７５で、パブリックキーディレクトリは、タグのパブリックキーＱを返す。そして、ブロック６８０で、リーダは、Ａ＝ｆ（ｃ，Ｑ）＝ｆ（ａ，Ｃ）であることを確認する。そして、確認の結果が正しい場合は、リーダは、タグが証明されたものであり、タグＩＤが正確であることを知り、種々の検索、証明、他の機能でタグＩＤを使用することができる。
【００７１】
図７は、機密性及びアントレーサビリティの単純化されたタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。この暗号プロトコルは、機密性とアントレーサビリティを提供するが、認証は提供しない。ブロック７１０で、システムは、タグの識別情報を要求するメッセージを送信する。
【００７２】
ブロック７１５で、タグは、乱数ｓを選択する。
【００７３】
ブロック７２０で、タグは、Ｓ＝ｆ（ｓ，ＰE）を計算する。前述のように、ＰE＝（ｘE，ｙE）は、（タグＩＤ）暗号化用の第２楕円曲線ＥE（ＦE）上のポイントである。
【００７４】
ブロック７２５で、タグは、ｋE，＝ｆ（ｓ，Ｒ）を計算する。Ｒは、リーダのパブリックキーであり、ｓは乱数である。
【００７５】
ブロック７３０で、タグは、Ｂ＝Ｅ（ｎ，ｋE）を計算する。値ｎはタグＩＤであり、上述のようにｋE＝ｆ（ｓ，Ｒ）である。ブロック７３５で、タグは、値Ｓ及びＢをリーダへ返す。Ｓ及びＢはともに、少なくとも乱数ｓの関数の一部であるので、これらの値はそれぞれの応答と異なる。
【００７６】
そして、リーダは、以下の計算を実行する。
（７４０）ｋE＝ｆ（ｒ，Ｓ）。ここで、ｒはリーダのプライベートキーであり、Ｓはタグからの返信である。
（７４５）計算値ｋEと与えられた値Ｂを使用して、ｎ＝Ｄ（Ｂ，ｋE）を計算する。
【００７７】
値ｎは、タグＩＤであり、タグに関するオブジェクトについてのデータを検索するのに使用される。この処理は、タグの認証を提供しないことに注意すべきである。しかし、これは、アントレーサビリティと機密性を提供する。
【００７８】
図８は、本発明とともに使用されるコンピュータシステムの一実施形態を示すブロック図である。図８は、本発明とともに使用されるコンピュータシステムの一実施形態を示す。当業者にとっては明らかであろうが、種々のシステム構造の他の代替のシステムもまた、使用することが可能である。
【００７９】
図８に示されたデータ処理システムは、情報通信のためのバスまたは他の内部通信手段８１５と、情報処理のためのバス８１５に接続されたプロセッサ８１０とを備えている。このシステムは、さらに、プロセッサ８１０によって実行される命令と情報とを記憶するためのバス８１５に接続されたランダムアクセスメモリ（ＲＡＭ）または他の揮発性記憶装置８５０（メモリとして示した）を備えている。また、メインメモリ８５０は、プロセッサ８１０によって命令が実行されている間の一時的な可変または他の中間情報を記憶するために使用されるようにしてもよい。また、このシステムは、静的な情報及びプロセッサ８１０の命令を記憶するためのバス８１５に接続された読み出し専用メモリ（ＲＯＭ）及び／又は静的記憶装置８２０と、磁気ディスク又は光ディスク及びこれに関連するディスクドライブなどのデータ記憶装置８２５とを備えている。データ記憶装置８２５は、情報及び命令を格納するためにバス８１５に接続されている。
【００８０】
さらに、このシステムは、コンピュータユーザへ情報を表示するための、バス８６５を介してバス８１５に接続された、陰極線管（ＣＲＴ）又は液晶表示（ＬＣＤ）などの表示装置８７０に接続されるようにしてもよい。また、英数字及び他のキーを備えた英数字入力装置８７５が、情報通信及びプロセッサ８１０へのコマンド選択のために、バス８６５を介してバス８１５に接続されるようにしてもよい。追加のユーザ入力装置は、方向情報通信及びプロセッサ８１０へのコマンド選択のために、並びに表示装置８７０上のカーソル動作制御のために、バス８６５を介してバス８１５に接続された、マウス、トラックボール、スティラス、又はカーソルディレクションキーなどのカーソル制御装置８８０である。
【００８１】
コンピュータシステム８００に随意に接続される他の装置は、分散システムの他のノードにネットワークを介してアクセスするための通信装置８９０である。通信装置８９０は、イーサネット（登録商標）、トークンリング、インターネット、又は広帯域ネットワークに接続するために使用されるような商業的に利用可能な多くのネットワーク周辺装置を備えるようにしてもよい。さらに、通信装置８９０は、コンピュータシステム８００と外部世界との間の接続性を提供するヌルモデム接続、又は他の機構であってもよい。図８に示されたこのシステムのコンポーネント及び関連ハードウェアのいずれも、本発明の種々の実施形態において使用される可能性がある。
【００８２】
当業者にとっては当然のことながら、いずれのシステム構成も、特定の具体化手段により種々の目的に使用することができる。本発明を実現する制御ロジック又はソフトウェアは、局所的又は遠隔的にプロセッサ８１０のアクセスが可能な、メインメモリ８５０、大容量記憶装置８２５、又は他の記憶媒体に格納されることが可能である。
【００８３】
当業者にとっては明らかであるが、ここで述べたシステム、方法、及び処理は、メインメモリ８５０又は読み取り専用メモリ８２０に格納され、プロセッサ８１０によって実行されるソフトウェアとして具体化することができる。また、この制御ロジック又はソフトウェアは、コンピュータ読み取り可能なプログラムコードが組み込まれ、大容量記憶装置８２５が読み取り可能な、ここで述べた方法及び示唆によってプロセッサ８１０が動作するようにするための、量産されるコンピュータ読み取り可能媒体の物品に常駐することが可能である。
【００８４】
また、本発明は、上述のコンピュータハードウェアコンポーネントのサブセットを含むハンドヘルド又は携帯装置で具体化されてもよい。例えば、ハンドヘルド装置は、バス８１５、プロセッサ８１０、及びメモリ８５０及び／又は８２５のみを含むように構成してもよい。また、ハンドヘルド装置は、ユーザが利用可能なオプションから選択されるボタンセット又は入力信号コンポーネントを含むように構成してもよい。また、ハンドヘルド装置は、ハンドヘルド装置のユーザに情報を表示するための液晶表示（ＬＣＤ）又は表示要素マトリクスのような出力装置を含むように構成してもよい。このようなハンドヘルド装置を具体化するのに、従来の方法を使用することができる。このような装置の本発明の実現は、ここで提供された本発明の開示を受けた当業者の一人にとって明らかであろう。
【００８５】
また、本発明は、上述のコンピュータハードウェアコンポーネントのサブセットを含む特定目的の機器で具体化される。例えば、その機器は、プロセッサ８１０、データ記憶装置８２５、バス８１５、及びメモリ８５０、並びに装置による基本的な方法でユーザが通信することを可能にするスモールタッチスクリーンなどの未発達な通信機構を含んでもよい。一般に、装置がより特定目的になるほど、機能する装置のためにより少ない要素の存在が必要になる。いつくつかの装置において、ユーザとの通信は、タッチベーススクリーン又は同一機構を介するかもしれない。
【００８６】
当業者にとっては当然のことながら、いかなるシステム構成も、特定の実現手段に従って種々の目的に使用することができる。本発明を実現する制御ロジック又はソフトウェアは、局所的又は遠隔的に、プロセッサ８１０がアクセス可能に、機械読み取り可能媒体に格納され得る。機械読み取り可能媒体は、機械（例えば、コンピュータ）によって読み取り可能な形式で情報を格納又は伝送する機構を含む。例えば、機械読み取り可能媒体は、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、電気的、光学的、音響工学的、又は信号を伝播する他の形式（例えば、搬送波、赤外線信号、デジタル信号など）を含む。
【００８７】
以上、特定の実施例を示して本発明が説明された。しかし、添付されたクレームに示したように本発明の上位概念及び範囲から逸脱することなく種々の修正及び変更がなされることが明らかである。したがって、明細書及び図面は、限定的意味よりも実例として捉えられるべきである。
【図面の簡単な説明】
【００８８】
【図１】本発明に関する暗号サービスのコンポーネントの一実施形態を示すネットワーク図である。
【図２】本発明の暗号プロトコルを実現するサーバ及びクライアントの一実施形態を示すブロック図である。
【図３】暗号プロトコルを利用する一実施形態を示す概略フローチャートである。
【図４Ａ】本発明に関するリーダ及びタグの初期化の一実施形態を示す信号フロー図である。
【図４Ｂ】本発明に関するリーダ及びタグの初期化の一実施形態を示す信号フロー図である。
【図５】暗号化、認証及び機密性のタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。
【図６】暗号化及び機密性のタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。
【図７】機密性及びアントレーサビリティの単純化されたタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。
【図８】本発明とともに使用されるコンピュータシステムの一実施形態を示すブロック図である。
【技術分野】
【０００１】
本発明は暗号化及び認証に関し、特に、複雑性の低い装置の暗号化及び認証に関する。
【背景技術】
【０００２】
無線周波数識別（ＲＦＩＤ）タグが、広く普及してきている。これらは、製品の追跡及び他の目的で利用されている。一般に、ＲＦＩＤが照会を受けた時、ＲＦＩＤは、ＲＦＩＤが貼付されている物体に関するデータを検索するのに利用されるその識別情報を供給する。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、いくつかのエンティティは、第三者からの照会に対してＲＦＩＤデータを開示せずに、ＲＦＩＤの利用が可能であることを望んでいる。例えば、米国政府は、国境検問所での認証書類の処理の促進を進めるため、パスポートの書類又はクレジットサイズのカードの中にＲＦＩＤチップを組み込むことを望んでいる。
【０００４】
現在のＲＦＩＤソリューションは、４つの主たる脆弱性を有している。第１は、一般に、ＲＦＩＤは認証を提供しない。第２に、権限のない第三者が、装置に対して照会を行いＲＦＩＤチップ上のデータを知ることが可能である。パスポートの場合には、そのＲＦＩＤに、個人情報盗難を可能にするその所有者の個人情報に関する充分なデータを含んでいるかもしれない。第３に、攻撃者はそのようにして、装置の対話を盗聴し、ＲＦＩＤチップ上のそのデータを取得することができるかもしれない。最後に、攻撃者は、ＲＦＩＤチップの特定の識別子を使用して、ある個人を一貫して追跡することができるかもしれない。
【課題を解決するための手段】
【０００５】
安全な認証、機密性、及び匿名のための暗号プロトコルを提供する方法及び装置について、説明される。一実施形態において、このプロトコルは、少数の論理ゲートで実現され、簡単な装置上ですばやく実行され、軍事グレードの安全性を提供するように設計される。
【発明を実施するための最良の形態】
【０００６】
本発明は、一例として示され、添付した図面の形態及び類似要素に関する参照数字等に制限されるものではない。
【０００７】
記載された方法及び装置は、多くの機密保護の要求に向けた低電力装置の暗号プロトコルである。また、暗号プロトコルは、この用途のための実行特性を維持する。特に、この暗号プロトコルを含む装置は、標準的な技術を使用して比較的安価に構成することが可能である。実現するのに多くの論理ゲートを必要としないので、パッシブ型のＲＦＩＤチップなどの低電力装置上で実現可能である。最後に、このプロトコルは、数多くの装置が同時に照会されることを可能にする。
【０００８】
このプロトコルは、以下に示す暗号の特徴の１つ以上を提供する能力を有する。
・認証。このプロトコルは、タグの信憑性を暗号的に検査するための情報を含むことが可能である。
・機密性。このプロトコルは、権限のない第三者がタグの識別子を知ることができないように、そのタグの識別子を保護することができる。
・アントレーサビリティ／難読化。一実施形態のプロトコルは、まったく同じ値には戻らない。すなわち、タグの識別子を取得するためのキーをリーダが知らない場合、そのリーダは、同一のタグと通信していることを話すことすらできない。
【０００９】
一実施形態において、楕円曲線暗号システム（ＥＣＣ）、より具体的にはパブリック／プライベート・キー対を使用する楕円曲線暗号処理を通して認証が提供される。一実施形態において、機密性は、タグ識別子を暗号化することによって提供される。一実施形態において、暗号化は、タグ識別子の暗号化キーを導き出すためのデフィーヘルマン（Diffie-Helman）ベースの機構を使用し、このキーでタグ識別子を暗号化して行われる。一実施形態において、アントレーサビリティは、暗号化キーを生成するのに使用されそれぞれ交換される乱数を生成することによって提供される。
【００１０】
一実施形態において、このアプリケーションは、コンピュータを使用して素体（prime field）上で実現される。単純化のため、いくつかの例は、単に、楕円曲線暗号（ＥＣＣ）又は素体のデフィーヘルマン問題について説明する。しかし、当業者の一人は、両方の方法、または２つの方法の組み合わせが、本発明によって使用されることが可能であることを理解するであろう。
【００１１】
このアプリケーションの例は、無線周波数識別（ＲＦＩＤ）リーダ及びタグを使用して実現されるシステムについて述べているが、本発明は、複雑性の低いいかなる装置を利用してもよい。
【００１２】
図１は、本発明に関する暗号サービスのコンポーネントの一実施形態を示すネットワーク図である。一実施形態において、ＲＦＩＤシステム１２０は、１つ以上の暗号ＲＦＩＤタグ１１０Ａ，１１０Ｂ，１１０Ｃを読み取るリーダを備えている。一実施形態において、ＲＦＩＤシステム１２０は、複数のＲＦＩＤタグ１１０Ａ−Ｃを同時に読み取る能力を有している。別の実施形態において、各タグは、順番に質問される。一実施形態において、ＲＦＩＤシステム１２０は、暗号システムを備えている。別の実施形態において、ＲＦＩＤシステム１２０は、リーダと結びついて、ここで記述された暗号機能を実行するための暗号システムとリンクされている。
【００１３】
リーダ１２０は、暗号ＲＦＩＤタグ１１０ＡからタグＩＤを要求する。一実施形態において、この要求は呼び掛けを含む。リーダは、暗号化された応答を受け取る。暗号化された応答は、適当なキーを持つシステム１２０によって解読され得る。タグＩＤの要求を繰り返し送信しても、スプーファーシステム１３０は、一致した応答を受信できない（なぜなら、応答は暗号化され難読化されているからである）。したがって、スプーファーシステム１３０は、暗号ＲＦＩＤタグ１１０ＡのタグＩＤを識別することができない。したがって、ＲＦＩＤタグ１１０Ａに関するデータを検索することができない。
【００１４】
一実施形態において、タグの応答を解読してタグＩＤを取得した後、ＲＦＩＤシステム１２０はタグＩＤに関するパブリックキーを検索する。一実施形態において、パブリックキーの検索は、ネットワーク１５０を介してアクセス可能なリモートシステム１６０によって実行される。また、キー検索は、ローカルシステムまたはＲＦＩＤシステム１２０自体に組み込むことが可能である。一実施形態において、パブリックキー検索サーバ１６０は、ＲＦＩＤシステムに対してローカルである。一実施形態において、パブリックキー検索サーバ１６０は、パブリックからアクセスできないプライベートサーバである。
【００１５】
一実施形態において、データベース１７０内の各ＲＦＩＤタグの記録は、タグ識別子（タグＩＤ）及びタグパブリックキーＱを含む。一実施形態において、その記録は、ＲＦＩＤが生成された時を示すタイムスタンプもまた含む。したがって、このデータは、タグの外部に決して格納されることのないタグプライベートキーを含まない。
【００１６】
図２は、低処理電力システム（ＬＰＰＳ）及び通信システム関連の一実施形態を示すブロック図である。ＬＰＰＳはＲＦＩＤタグであり、一方、通信システムはＲＦＩＤリーダである。
【００１７】
ＲＦＩＤタグ１１０は、トランシーバ２５０、または代わりに個別の受信及び送信ロジックを含んでいる。一実施形態において、トランシーバ２５０は、ＲＦＩＤトランシーバである。一実施形態において、ＰＬＬＳ２１０は、システム２２０から受信する入力信号によってトランシーバ２５０が電力供給されるのに充分に低い電力で動く。
【００１８】
初期化の間、暗号ロジック２５５は、タグ１１０のプライベートキーを計算し、そのプライベートキーはメモリ２６０に格納される。本明細書におけるプライベートキーという用語は、楕円曲線上の１点、またはデフィーヘルマン問題で使用される大きな素数を表す。バブリックキーは、プライベートキーにキー対を提供する関数または値である。
【００１９】
ＲＦＩＤタグ１１０は、ＲＦＩＤシステム１２０から、パブリックキー、又は別の実施形態では複数のパブリックキーを受信する。また、ＲＦＩＤタグ１１０は、そのタグの識別子（タグＩＤ）をシステム１２０から受信し、それらをメモリ２６０内に格納する。一実施形態において、プライベートキーは、Ｅ（Ｆ）のオーダと同じ長さの値であり、無作為に生成される。タグ１１０内の暗号ロジック２５５は、さらに、タグのプライベートキーに基づいてＲＦＩＤタグのパブリックキーを計算する。一実施形態において、このパブリックキーは、認証機関によって署名され、ＬＰＰＳ２１０の認証で使用される。
【００２０】
メモリ２６０は、リーダのタグＩＤ及びパブリックキー（初期化中に受信される）とともに、プライベートキー（タグの中で生成された乱数ａ）を格納するのに使用される。プライベートキー、パブリックキー、及びタグＩＤを格納し、認証関数を計算するのに必要なゲートの数は、キーの長さに比例する。したがって、安全性を確保しつつキーサイズを最小化するのは、興味があることである。したがって、一実施形態において、このシステムは、２進フィールドにおける１６３から３進フィールドにおける１０７までワードサイズの削減（システムの安全性を減らすことなくワード長の約３５％の減少）が可能な、Ｆとして３進フィールドを使用する。すなわち、２進ロジックゲートの代わりに３進ロジックゲートを使用することにより、より少ないロジックゲートが必要となり、そのいくつかの動作（乗算など）はより速くなる。
【００２１】
一実施形態において、このシステムは、改ざんロジック２６５を含む。改ざんロジック２６５は、改ざん防止機能を提供する。一実施形態において、すべてのタグは改ざん防止機能を有している。別の実施形態において、メモリ２６０のみ、またはブライベートキーが格納されるメモリ領域に、改ざん防止機能を備えている。一実施形態において、改ざん防止機能は、メモリの読み取りやバスのハッキングなどをシステムが検知したとき、そのメモリを消去するロジックを含んでもよい。一実施形態において、これはヒューズを使用して実現できる。
【００２２】
認証の使用中、暗号ロジック２５５は、呼び掛けを受信し、呼び掛けへの応答を計算する。呼び掛けへの応答は暗号化され、認証化され、応答の難読化される。これは、同じ呼び掛けが繰り返し送信された場合であっても、ＲＦＩＤタグ１１０からの応答が常に異なることを確実にする。一実施形態において、計算は、選択された有限フィールド上の選択された楕円曲線上で行われる。上記のとおり、一実施形態におけるこのフィールドは周知の２進フィールドである。
【００２３】
ＲＦＩＤシステム２２０は、ＲＦＩＤリーダ２１０を含み、ＲＦＩＤタグ２１０へ呼び掛けを送信する。呼び掛けは、乱数ジェネレータ２１５により生成された乱数に基づいて、呼び掛け計算器２２０によって生成される。一実施形態において、乱数は、Ｅのオーダの大きさと同じオーダの数字である。
【００２４】
ＲＦＩＤタグ２１０が呼び掛けに応答するとき、その応答は、暗号化されたタグＩＤ及び呼び掛け応答を含む。暗号計算器２３０は、暗号化された応答を解読し、応答からタグＩＤを取得するのに使用される。パブリックキー検索ロジック２２５は、データベース内のそのタグのパブリックキーを検索するのにタグＩＤを使用する。前述のように、データベースは、ＲＦＩＤシステム１２０の一部、ローカル、または遠隔かつネットワークを介してアクセス可能であってもよい。
【００２５】
暗号計算器２３０は、乱数を取得し、パブリックキーを使用してパブリックキー値を計算する。パブリックキー値は、ＲＦＩＤタグによって返された呼び掛け応答と等しいはずである。したがって、比較ロジック２３５は、ＲＦＩＤタグ２１０によって返された呼び掛け応答と、計算の結果との比較を行う。もし、値が一致した場合、ＲＦＩＤシステム１２０は、ＲＦＩＤタグ２１０を証明する。一実施形態において、検証ロジック２４０は、ＲＦＩＤタグ１１０が正当であることを示す適切な情報を出力する。一実施形態において、ＲＦＩＤシステム１２０は、ＲＦＩＤタグ１１０が有効であることを示す出力機構を有する。
【００２６】
図３は、暗号プロトコルを利用する一実施形態を示す概略フローチャートである。処理は、初期化で始まる。
【００２７】
ブロック３１０において、共通データが、タグとリーダとの間で共有される。タグは、例えば無線周波数識別（ＲＦＩＤ）タグのような、複雑性の低い処理装置である。リーダは、ＲＦＩＤリーダのような、タグとインターフェイスするように設計された装置である。一実施形態において、用語“リーダ”は、暗号サービスを提供するシステムとともに、タグと対話するシステムを示す。しかし、一実施形態において、これらの機能は分離され、ネットワークコネクション又は他の方法を介して結合された別々の装置によって実行される。共通データは、必要な楕円曲線、フィールド、及び楕円暗号化のポイント、または従来の暗号化のジェネレータ及び大きな素数を画定する。用語“オリジネータ”は、この発明において、大きな素数のジェネレータ及び楕円曲線暗号化で使用される楕円フィールド内のポイントを示すものとして使用される。
【００２８】
ブロック３１５において、タグとリーダの間でキーが共有される。一実施形態において、キーは、楕円暗号化または従来の大きな素数の暗号化を利用する１つ以上のパブリック／プライベート・キー対を含む。一実施形態において、３組のキー対が生成され、それぞれ、認証、暗号化、及び難読化用である。一実施形態において、タグは、自分自身のキーを生成する。
【００２９】
適当なプライベートキー及びパブリックキーが、ブロック３２０で、格納されると、初期化は完了する。一実施形態において、タグは、リーダのパブリックキー及び自分自身のプライベートキー及び識別情報を格納し、リーダは、自分自身のプライベートキーを格納する。一実施形態において、タグのパブリックキー及び識別情報が、別々のパブリックキー・ディレクトリに格納される。
【００３０】
以下の処理は、識別を目的としたタグのパブリックキーを取得する部分である。以下の処理、認証されたタグＩＤの供給に加えて、タグＩＤを暗号化する手段でタグＩＤを提供し、その値を難読化する。これは、スプーフィング・リーダが、同じ呼び掛けを複数回送信することによって暗号化の認識を試みた場合に、リターンデータが一致しないことを保証する。
【００３１】
ブロック３２５において、リーダがタグの呼び掛けを計算する。呼び掛けは、リーダがそのタグのタグＩＤを確認することを可能にする情報を引き出すように設計される。一実施形態において、呼び掛けは、乱数である。一実施形態において、呼び掛けは、選択された有限フィールド上の楕円曲線に沿った乱数である。
【００３２】
ブロック３３０で、呼び掛けに対する応答をタグが計算する。一実施形態において、呼び掛けに対する応答は、タグのプライベートキー掛ける呼び掛けである。
【００３３】
ブロック３３５で、タグは、呼び掛けに対する応答と、暗号化用、認証用及び機密性用の３つのキーで暗号化された３つの乱数と、の組み合わせの返信データを計算する。一実施形態において、タグは、２つの乱数（ｓとｕ）を生成し、キー（それぞれ暗号化と難読化）に従ってそれぞれを暗号化する。認証キーは、リーダのパブリックキーで暗号化される。そして、タグは、４つの乱数すべてを含む連結値を返信する。一実施形態において、返信の値は、タグの識別子を含む。
【００３４】
ブロック３４０で、タグからリターンデータを受け取ったリーダは、リターンデータからのｎ(タグＩＤ)を計算するのに、そのプライベートキーを利用する。
【００３５】
ブロック３４５で、そのタグＩＤを使用して、リーダは、そのタグのパブリックキーを検索する。
【００３６】
ブロック３５０で、リーダは、署名された呼び掛け応答が含まれているリターンデータを確認する。ブロック３５５の確認で、リーダがそのタグＩＤ（ｎ）を知っていて、このＩＤが、呼び掛けに対する応答により信頼できることが証明された場合、リーダは、ブロック３６０で、他の活動を実行するためにそのタグＩＤを利用することができる。例えば、タグＩＤは、別のデータベース内のデータを検索したり、タグの承認を確認したりするのに使用される。そして、ブロック３６５で、処理が終了する。
【００３７】
図４Ａ及びＢは、本発明に関するリーダ及びタグの初期化の一実施形態を示す信号フロー図である。このシステムは、楕円曲線暗号（ＥＣＣ）、または従来のパブリックキー暗号パラメータを使用する。
【００３８】
ブロック４０５で、タグとリーダは、暗号パラメータで初期化される。使用される暗号システムが楕円曲線システムの場合、一実施形態において、以下の値が決定される。
１．（タグ）認証用の第１楕円曲線ＥA及び有限フィールドＦA
２．（タグ）認証用の第１楕円曲線ＥA（ＦA）上の第１ポイントＰA＝（ｘA，ｙA）
３．（タグＩＤ）暗号化用の第２楕円曲線ＥE及び有限フィールドＦE
４．（タグＩＤ）暗号化用の第２楕円曲線ＥE（ＦE）上の第２ポイントＰE＝（ｘE，ｙE）
５．（タグＩＤ）難読化用の第３楕円曲線ＥO及び有限フィールドＦO
６．（タグＩＤ）難読化用の第３楕円曲線ＥO（ＦO）上の第３ポイントＰO＝（ｘO，ｙO）
【００３９】
ポイントのそれぞれのために、ＰA/E/Oを整数で乗算することによって生成される全ポイントのセットは、フィールド上の楕円曲線上のポイントの総数と同じサイズであるべきである。より正式には、｛Ｐi｜∃ｘ such that Ｐ＝ＰＡx｝セットのオーダは、ＥA（ＦA）のオーダと同じでなければならない。
【００４０】
一実施形態において、認証、暗号化、及び難読化機構は、上述の個別の楕円曲線、有限フィールド、及び／又は楕円曲線上のポイントを利用する。別の実施形態において、決定されたフィールド、曲線、及び／又はポイントは同一かもしれない。一実施形態において、同じ楕円曲線、フィールド、及びポイントは、すべての３つの暗号アスペクト（認証、暗号化、及び難読化）として使用される。これらのアスペクト、ＥA，ＥE，ＥO，ＦA，ＦE，ＦO，及びＰA，ＰE，ＰOは、タグ及びリーダを初期化するのに使用される。ＥＣＣの一方向性関数は、ｆ（ａ，Ｂ）＝ａ・Ｂである（ここでドット演算子はポイント乗算を示す。）。例えば、ａ・Ｂは“ポイントＢ掛ける整数ａ”を意味する。
【００４１】
従来の暗号化方法、大きな素体上の計算を使用する暗号化のために、一実施形態において、以下の値が定義される。
１．（タグ）認証用の素数ＱAを選択する。
２．（タグ）認証用のジェネレータｇA∈［２，ＱA−１］を選択する。
３．（タグＩＤ）暗号化用の素数ＱEを選択する。
４．（タグＩＤ）暗号化用のジェネレータｇE∈［２，ＱE−１］を選択する。
５．（タグＩＤ）難読化用の素数ＱOを選択する。
６．（タグＩＤ）難読化用のジェネレータｇO∈［２，ＱO−１］を選択する。
【００４２】
一実施形態において、ジェネレータ及び素数は、それぞれの値（認証、暗号化、及び難読化）と同一とすることができる。素体上の計算用の一方向性関数は、
ｆ（ａ，Ｂ）＝Ｂa ｍｏｄ ｐである。
【００４３】
ジェネレータｇA/E/O及びポイントＰA/E/Oは、オリジネータＯA/E/Oとして集合的に参照される。
【００４４】
上述のように、これらの暗号ジェネレータは、タグ及びリーダを初期化するのに使用される。リーダ／タグは暗号化の一形態として使用されることを注意すべきである。ここで、大きな素体上の楕円暗号化及び計算を説明した。しかし、確実な暗号化及び解読キー対を生成する代替的な暗号関数を使用することも可能である。
【００４５】
初期化は、種々の手段で起きる。一実施形態において、合意が必要とされないように、すべてのシステムコンポーネントは、予め同じパラメータでプログラミングされる。別の実施形態において、それぞれのシステムコンポーネントは、どのパラメータが通信のために使用されるかという完全な説明を受信するであろう。さらに別の実施形態において、よく知られている名称のパラメータの標準的なセットから使用されるパラメータについての２つのサイドが簡単に特定されるであろう。例えば、ＲＦＣ４４９２の５．１．１節を参照のこと（http://www.faqs.org/rfcs/rfc4492.html）。これは、いくつかの標準的な楕円曲線及びフィールドの１６ビット識別子を特定する。別の実施形態において、２つのサイドが、同意済み又は予め決められたパラメータ・セットからパラメータを選択するであろう。両方のコンポーネントがこれらのパラメータを持つことを保証する他の方法が使用されてもよい。
【００４６】
ブロック４１０で、リーダは、その暗号化キーとして乱数ｒを抽出する。ブロック４１５で、リーダは、キー対（Ｒ，ｒ）を生成するために、暗号化キーｒについてのパブリックキーである適合キーＲ＝ｆ（ｒ，ＰE）を計算する。
【００４７】
ブロック４２０で、リーダは、難読化キーとして第２乱数ｊを抽出する。ブロック４３０で、Ｊ＝ｆ（ｊ，ＰO）を計算することにより、難読化キー対（Ｊ，ｊ）が計算される。このようにして、リーダは、暗号化用のキー対（Ｒ，ｒ）と、タグの識別の難読化用の第２キー対（Ｊ，ｊ）を生成する。一実施形態において、Ｒ＝Ｊ、及びｒ＝ｊである。ｒ及びｊの値は、リーダ内に格納される。
【００４８】
ブロック４４０で、リーダは、初期化するようにタグに伝えるため、タグＩＤ（ｎ）に沿ったパブリックキー（Ｒ及びＪ）をタグに送信する。一実施形態において、ＲＦＩＤシステムは、乱数であるｎを選択する。一実施形態において、タグＩＤ値ｎは、キー（Ｒ及びＪ）の長さより短くなるように選択される。一実施形態において、初期化処理は、多くのタグと一緒に実行されることができる。
【００４９】
ブロック４４５で、ｎ，Ｒ，及びＪの値が、タグの内部メモリに保存される。上述のように、一実施形態において、内部メモリは安全なメモリである。一実施形態において、タグを破壊することなく暗号処理を通さない限り、内部メモリにアクセスすることができない。
【００５０】
ブロック４５０で、プライベートキーとしてタグによって乱数ａが選択され、タグの内部メモリに保存される。一実施形態において、内部メモリは、安全なメモリである。一実施形態において、タグＩＤとタグのプライベートキーのみが安全なメモリに格納される。
【００５１】
ブロック４５５で、タグは、パブリックキーＱ＝ｆ（ａ，ＰA）を計算する。ブロック４６０で、値Ｑは、リーダ／システムに送信される。一実施形態において、リーダ／システムは、タグのパグリックキーをバブリックキーディレクトリへ転送する（ブロック４６５）。ブロック４７０で、バブリックキーディレクトリは、値ｎ（タグＩＤ）についての値Ｑの値を格納する。ブロック４７５で、バブリックキーディレクトリは、その値が正しく格納されたことを認める。
【００５２】
図５は、暗号化、認証、及び難読化のタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。この処理は、ＲＦＩＤシステムがタグからデータを取得しようとしたときに初期化される。一実施形態において、ＲＦＩＤシステムは、１つ以上のＲＦＩＤタグと並行して同じ処理を実行することができる。
【００５３】
ブロック５１０で、ＲＦＩＤシステムは、乱数ｃを抽出する。ブロック５１５で、ＲＦＩＤシステムは、呼び掛けＣ＝ｆ（ｃ，ＰA）を計算する。呼び掛けＣは、乱数ｃの対である。一実施形態において、暗号化関数Ｅは、暗号テキストを生成するために普通テキストとキーのＸＯＲをとる。メッセージのために、ｎ及びポイントＰi、これは
である。この暗号化関数の選択のために、解読は、同じ方法：
で働く。ブロック５２０で、システムは、タグＩＤと、呼び掛けに対するタグ応答を要求するメッセージを送信する。このメッセージは、呼び掛けＣを含む。
【００５４】
ブロック５２５で、タグは、Ａ＝ｆ（ａ，Ｃ）を計算する。値ａは、ＲＦＩＤタグのプライベートキーである。
【００５５】
ブロック５３０で、タグは、乱数ｓを生成する。一実施形態において、乱数ｓは、乱数ジェネレータを使用して生成される。別の実施形態において、それは、物理的クローン不可関数（ＰＵＦ）を使用して生成される。ブロック５３５で、一実施形態において、Ｓ＝ｆ（ｓ，ＰE）が計算される。前述のように、ＰE＝（ｘE，ｙE）は、（タグＩＤ）暗号化用の第２楕円曲線ＥE（ＦE）上のポイントである。
【００５６】
ブロック５４０で、システムは、値ｋE＝ｆ（ｓ，Ｒ）を計算する。Ｒは、ＲＦＩＤシステムのパブリックキーの１つであり、ｓは、上記で生成された乱数である。ブロック５４２で、ＲＦＩＤタグは、Ｂ＝Ｅ（ｎ，ｋE）を計算する。値ｎはタグＩＤであり、上記のとおりｋE＝ｆ（ｓ，Ｒ）である。
【００５７】
一実施形態において、ブロック５４５で、システムは、第２乱数ｕを抽出する。ブロック５５０で、タグはＵ＝ｆ（ｕ，ＰO）を計算する。上記のとおり、ＰO＝（ｘO，ｙO）は、（タグＩＤ）難読化用の第３楕円曲線ＥO（ＦO）上のポイントである。ブロック５５５で、システムは、ｋO＝ｆ（ｕ，Ｊ）を計算する。ここで、ｕは第２乱数、ＪはＲＦＩＤリーダの第２パブリックキーである。
【００５８】
ブロック５６５で、タグはＧ＝ｆ（Ａ，ｋO）を計算する。Ａ＝ｆ（ａ，Ｃ）は、タグのプライベートキー及び呼びかけの関数であり、ｋO＝ｆ（ｕ，Ｊ）である
【００５９】
ブロック５７０で、タグは、値Ｓ，Ｕ，Ｂ及びＧを返す。ここで、Ｓ＝ｆ（ｓ，ＰE），Ｕ＝ｆ（ｕ，ＰO），Ｂ＝Ｅ（ｎ，ｋE），Ｇ＝ｆ（Ａ，ｋO）である。一実施形態において、タグは、これらの値の連結を返す。このプロトコルの特性の１つは、毎回異なる応答をタグが返すことばかりでなく（したがって、タグは追跡されない）、キーホルダ（権限を有するリーダ）は、リターンデータに基づいてタグの識別情報を確認することができることである。
【００６０】
そして、リーダは、以下の計算を実行する。
（５７２）プライベートキーｒと与えられた値Ｓを使用してｋE＝ｆ（ｒ，Ｓ）を計算する。
（５７４）プライベートキーｊと与えられた値Ｕを使用してｋO＝ｆ（ｊ，Ｕ）を計算する。
（５７６）計算値ｋEと与えられた値Ｂを使用してｎ＝Ｄ（Ｂ，ｋE）を計算する。
【００６１】
値ｎは、タグＩＤであり、これはブロック５８０で、パブリックキーディレクトリからタグｎのパブリックキーを要求するのに使用される。ブロック５８５で、パブリックキーディレクトリは、タグのパブリックキーＱを返す。そして、リーダは、与えられた値Ｇ、計算値ｋOを使用して（５９０）Ａ＝Ｄ（Ｇ，ｋO）を計算し、Ａ＝ｆ（ｃ，Ｑ）＝ｆ（ａ，Ｃ）であることを確認する。確認の結果、正しければ、リーダは、タグが証明されたものであり、タグＩＤが正確であることを知り、種々の検索、証明、他の機能でタグＩＤを使用することができる。
【００６２】
この例は、楕円曲線上の関数を説明したが、説明した暗号プロトコルは、大きな素数を代わりに利用することが可能である。大きい素数のために、それぞれのｆ（ｘ，Ｐ）は、ｆ（ｘ，ｇ）で置き換えられる。ここで、ｇは大きい素数のジェネレータである。
【００６３】
図６は、暗号化及び難読化の短縮化されたタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。この短縮化された処理は、ポイントを同じ値に設定することによって、いくつかの計算を簡単にしたものである。ブロック６１０で、ＲＦＩＤシステムは、乱数ｃを抽出する。ブロック６１５で、ＲＦＩＤシステムは、呼び掛けＣ＝ｆ（ｃ，ＰA）を計算する。呼び掛けＣは、乱数ｃの対である。ブロック６２０で、システムは、呼び掛けＣを含むタグの識別情報を要求するメッセージを送信する。
【００６４】
ブロック６２５で、タグは、Ａ＝ｆ（ａ，Ｃ）を計算する。値ａは、ＲＦＩＤタグのプライベートキーである。
【００６５】
ブロック６３０で、タグは、乱数ｓを生成する。一実施形態において、乱数ｓは、乱数ジェネレータを使用して生成される。別の実施形態において、乱数ｓは、物理的クローン不可関数（ＰＵＦ）を使用して生成される。ブロック６３５で、Ｓ＝ｆ（ｓ，ＰE）が計算される。上述のように、ＰE＝（ｘE，ｙE）は、（タグＩＤ）暗号化用の第２楕円曲線ＥE（ＦE）上のポイントである。
【００６６】
ブロック６４０で、Ｔ＝ｆ（ｓ，Ｒ）が計算される。Ｒは、ＲＦＩＤシステムのパブリックキーの１つであり、ｓは、上記で生成された乱数である。ブロック６４５で、タグが、ｋE，ｋO＝ｇ（Ｔ）を計算する。関数ｇ（）は、ｎ｜ＡのＸＯＲに対して充分に長い列を計算する。関数ｇ：ｋ→ｋ1，ｋ2は、長さｌの入力から長さｌの２つの値を生成するのに使用される。一実施形態において、この値は、擬似乱数であり、関数ｇ（）として、暗号的に聞こえるものかなにかを使用するのがベストである。
【００６７】
ブロック６５０で、ＲＦＩＤタグは、Ｂ＝Ｅ（ｎ，ｋE）を計算する。値ｎは、タグＩＤである。ここで、上記のように、ｋE＝ｆ（ｓ，Ｒ）である。ブロック６５５で、タグは、Ｇ＝ｆ（Ａ，ｋO）を計算する。Ａ＝ｆ（ａ，Ｃ）は、タグのプライベートキーと呼び掛けの関数である。
【００６８】
ブロック６６０で、タグは、値Ｓ，Ｂ，及びＧを返す。一実施形態において、タグは、これらの値の連結を返す。Ｓ＝ｆ（ｓ，ＰE），Ｂ＝Ｅ（ｎ，ｋE），Ｇ＝ｆ（Ａ，ｋO）である。
【００６９】
そして、リーダは、以下の計算を実行する。
（６６２）プライベートキーｒと与えられた値Ｓを使用して、Ｔ＝ｆ（ｒ，Ｓ）を計算する。
（６６４）ｋE，ｋO＝ｇ（Ｔ）を計算する。
（６６６）計算値ｋEと与えられた値Ｂを使用して、ｎ＝Ｄ（Ｂ，ｋE）を計算する。
（６６８）与えられた値Ｇと計算値ｋOを使用して、Ａ＝Ｄ（Ｇ，ｋO）を計算する。
【００７０】
値ｎはタグＩＤであり、これは、ブロック６７０で、パブリックキーディレクトリからタグｎのパブリックキーを要求するのに使用される。ブロック６７５で、パブリックキーディレクトリは、タグのパブリックキーＱを返す。そして、ブロック６８０で、リーダは、Ａ＝ｆ（ｃ，Ｑ）＝ｆ（ａ，Ｃ）であることを確認する。そして、確認の結果が正しい場合は、リーダは、タグが証明されたものであり、タグＩＤが正確であることを知り、種々の検索、証明、他の機能でタグＩＤを使用することができる。
【００７１】
図７は、機密性及びアントレーサビリティの単純化されたタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。この暗号プロトコルは、機密性とアントレーサビリティを提供するが、認証は提供しない。ブロック７１０で、システムは、タグの識別情報を要求するメッセージを送信する。
【００７２】
ブロック７１５で、タグは、乱数ｓを選択する。
【００７３】
ブロック７２０で、タグは、Ｓ＝ｆ（ｓ，ＰE）を計算する。前述のように、ＰE＝（ｘE，ｙE）は、（タグＩＤ）暗号化用の第２楕円曲線ＥE（ＦE）上のポイントである。
【００７４】
ブロック７２５で、タグは、ｋE，＝ｆ（ｓ，Ｒ）を計算する。Ｒは、リーダのパブリックキーであり、ｓは乱数である。
【００７５】
ブロック７３０で、タグは、Ｂ＝Ｅ（ｎ，ｋE）を計算する。値ｎはタグＩＤであり、上述のようにｋE＝ｆ（ｓ，Ｒ）である。ブロック７３５で、タグは、値Ｓ及びＢをリーダへ返す。Ｓ及びＢはともに、少なくとも乱数ｓの関数の一部であるので、これらの値はそれぞれの応答と異なる。
【００７６】
そして、リーダは、以下の計算を実行する。
（７４０）ｋE＝ｆ（ｒ，Ｓ）。ここで、ｒはリーダのプライベートキーであり、Ｓはタグからの返信である。
（７４５）計算値ｋEと与えられた値Ｂを使用して、ｎ＝Ｄ（Ｂ，ｋE）を計算する。
【００７７】
値ｎは、タグＩＤであり、タグに関するオブジェクトについてのデータを検索するのに使用される。この処理は、タグの認証を提供しないことに注意すべきである。しかし、これは、アントレーサビリティと機密性を提供する。
【００７８】
図８は、本発明とともに使用されるコンピュータシステムの一実施形態を示すブロック図である。図８は、本発明とともに使用されるコンピュータシステムの一実施形態を示す。当業者にとっては明らかであろうが、種々のシステム構造の他の代替のシステムもまた、使用することが可能である。
【００７９】
図８に示されたデータ処理システムは、情報通信のためのバスまたは他の内部通信手段８１５と、情報処理のためのバス８１５に接続されたプロセッサ８１０とを備えている。このシステムは、さらに、プロセッサ８１０によって実行される命令と情報とを記憶するためのバス８１５に接続されたランダムアクセスメモリ（ＲＡＭ）または他の揮発性記憶装置８５０（メモリとして示した）を備えている。また、メインメモリ８５０は、プロセッサ８１０によって命令が実行されている間の一時的な可変または他の中間情報を記憶するために使用されるようにしてもよい。また、このシステムは、静的な情報及びプロセッサ８１０の命令を記憶するためのバス８１５に接続された読み出し専用メモリ（ＲＯＭ）及び／又は静的記憶装置８２０と、磁気ディスク又は光ディスク及びこれに関連するディスクドライブなどのデータ記憶装置８２５とを備えている。データ記憶装置８２５は、情報及び命令を格納するためにバス８１５に接続されている。
【００８０】
さらに、このシステムは、コンピュータユーザへ情報を表示するための、バス８６５を介してバス８１５に接続された、陰極線管（ＣＲＴ）又は液晶表示（ＬＣＤ）などの表示装置８７０に接続されるようにしてもよい。また、英数字及び他のキーを備えた英数字入力装置８７５が、情報通信及びプロセッサ８１０へのコマンド選択のために、バス８６５を介してバス８１５に接続されるようにしてもよい。追加のユーザ入力装置は、方向情報通信及びプロセッサ８１０へのコマンド選択のために、並びに表示装置８７０上のカーソル動作制御のために、バス８６５を介してバス８１５に接続された、マウス、トラックボール、スティラス、又はカーソルディレクションキーなどのカーソル制御装置８８０である。
【００８１】
コンピュータシステム８００に随意に接続される他の装置は、分散システムの他のノードにネットワークを介してアクセスするための通信装置８９０である。通信装置８９０は、イーサネット（登録商標）、トークンリング、インターネット、又は広帯域ネットワークに接続するために使用されるような商業的に利用可能な多くのネットワーク周辺装置を備えるようにしてもよい。さらに、通信装置８９０は、コンピュータシステム８００と外部世界との間の接続性を提供するヌルモデム接続、又は他の機構であってもよい。図８に示されたこのシステムのコンポーネント及び関連ハードウェアのいずれも、本発明の種々の実施形態において使用される可能性がある。
【００８２】
当業者にとっては当然のことながら、いずれのシステム構成も、特定の具体化手段により種々の目的に使用することができる。本発明を実現する制御ロジック又はソフトウェアは、局所的又は遠隔的にプロセッサ８１０のアクセスが可能な、メインメモリ８５０、大容量記憶装置８２５、又は他の記憶媒体に格納されることが可能である。
【００８３】
当業者にとっては明らかであるが、ここで述べたシステム、方法、及び処理は、メインメモリ８５０又は読み取り専用メモリ８２０に格納され、プロセッサ８１０によって実行されるソフトウェアとして具体化することができる。また、この制御ロジック又はソフトウェアは、コンピュータ読み取り可能なプログラムコードが組み込まれ、大容量記憶装置８２５が読み取り可能な、ここで述べた方法及び示唆によってプロセッサ８１０が動作するようにするための、量産されるコンピュータ読み取り可能媒体の物品に常駐することが可能である。
【００８４】
また、本発明は、上述のコンピュータハードウェアコンポーネントのサブセットを含むハンドヘルド又は携帯装置で具体化されてもよい。例えば、ハンドヘルド装置は、バス８１５、プロセッサ８１０、及びメモリ８５０及び／又は８２５のみを含むように構成してもよい。また、ハンドヘルド装置は、ユーザが利用可能なオプションから選択されるボタンセット又は入力信号コンポーネントを含むように構成してもよい。また、ハンドヘルド装置は、ハンドヘルド装置のユーザに情報を表示するための液晶表示（ＬＣＤ）又は表示要素マトリクスのような出力装置を含むように構成してもよい。このようなハンドヘルド装置を具体化するのに、従来の方法を使用することができる。このような装置の本発明の実現は、ここで提供された本発明の開示を受けた当業者の一人にとって明らかであろう。
【００８５】
また、本発明は、上述のコンピュータハードウェアコンポーネントのサブセットを含む特定目的の機器で具体化される。例えば、その機器は、プロセッサ８１０、データ記憶装置８２５、バス８１５、及びメモリ８５０、並びに装置による基本的な方法でユーザが通信することを可能にするスモールタッチスクリーンなどの未発達な通信機構を含んでもよい。一般に、装置がより特定目的になるほど、機能する装置のためにより少ない要素の存在が必要になる。いつくつかの装置において、ユーザとの通信は、タッチベーススクリーン又は同一機構を介するかもしれない。
【００８６】
当業者にとっては当然のことながら、いかなるシステム構成も、特定の実現手段に従って種々の目的に使用することができる。本発明を実現する制御ロジック又はソフトウェアは、局所的又は遠隔的に、プロセッサ８１０がアクセス可能に、機械読み取り可能媒体に格納され得る。機械読み取り可能媒体は、機械（例えば、コンピュータ）によって読み取り可能な形式で情報を格納又は伝送する機構を含む。例えば、機械読み取り可能媒体は、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリ装置、電気的、光学的、音響工学的、又は信号を伝播する他の形式（例えば、搬送波、赤外線信号、デジタル信号など）を含む。
【００８７】
以上、特定の実施例を示して本発明が説明された。しかし、添付されたクレームに示したように本発明の上位概念及び範囲から逸脱することなく種々の修正及び変更がなされることが明らかである。したがって、明細書及び図面は、限定的意味よりも実例として捉えられるべきである。
【図面の簡単な説明】
【００８８】
【図１】本発明に関する暗号サービスのコンポーネントの一実施形態を示すネットワーク図である。
【図２】本発明の暗号プロトコルを実現するサーバ及びクライアントの一実施形態を示すブロック図である。
【図３】暗号プロトコルを利用する一実施形態を示す概略フローチャートである。
【図４Ａ】本発明に関するリーダ及びタグの初期化の一実施形態を示す信号フロー図である。
【図４Ｂ】本発明に関するリーダ及びタグの初期化の一実施形態を示す信号フロー図である。
【図５】暗号化、認証及び機密性のタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。
【図６】暗号化及び機密性のタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。
【図７】機密性及びアントレーサビリティの単純化されたタグＩＤプロトコルを使用する一実施形態を示す信号フロー図である。
【図８】本発明とともに使用されるコンピュータシステムの一実施形態を示すブロック図である。
【特許請求の範囲】
【請求項１】
暗号プロトコルを提供する方法であって、
低処理電力システムのプライベートキーの使用に基づく認証と、
無権限者がタグの識別子を知ることができないように、前記タグの識別子を保護する機密性と、
呼び掛けに対する応答として異なる値が返され、リーダが前記応答によって前記低処理電力システムを識別することができないことを保証するアントレーサビリティと、を有することを特徴とする方法。
【請求項２】
請求項１において、
前記暗号プロトコルは、楕円曲線暗号を含むことを特徴とする方法。
【請求項３】
請求項１において、
前記認証は、前記低処理電力システムのプライベートキーを利用し、前記プライベートキーと受信した呼び掛けとの関数を前記低処理電力システムで計算することを特徴とする方法。
【請求項４】
請求項１において、
前記アントレーサビリティは、認証値と結合された追加の暗号値を提供することを特徴とする方法。
【請求項５】
請求項１において、
前記機密性は、リーダのパグリックキーで前記タグの識別子を暗号化することを特徴とする方法。
【請求項６】
請求項１において、
リーダと前記低処理電力システムとの間で初期パラメータを交換することを特徴とする方法。
【請求項７】
請求項６において、
前記初期パラメータは、前記認証、前記機密性、及び前記アントレーサビリティのための、タグの識別子と、楕円曲線と、前記楕円曲線上のポイントとを含むことを特徴とする方法。
【請求項８】
請求項７において、
前記楕円曲線及び前記ポイントは、前記認証、前記機密性、及び前記アントレーサビリティのために同一であることを特徴とする方法。
【請求項９】
請求項６において、
前記リーダは、前記初期パラメータを前記低処理電力システムに提供することを特徴とする方法。
【請求項１０】
ＲＦＩＤタグを利用する方法であって、
リーダから呼び掛けを受信し、
Ｓ＝ｆ（ｓ，ＯE），Ｕ＝ｆ（ｕ，ＯO），Ｂ＝Ｅ（ｎ，ｋE），Ｇ＝ｆ（Ａ，ｋO）を計算し、
ここで、Ａは、前記呼び掛け及び前記ＲＦＩＤタグのプライベートキーの関数、
ｓ及びｕは、前記ＲＦＩＤタグによって生成された乱数、
ｎは、前記タグの識別子、
ｋE及びｋOは、それぞれ前記リーダの第１パブリックキー及び第２パブリックキーの関数、及び
ＯE及びＯOは、前記リーダによって提供されるオリジネータであり、
Ｓ、Ｕ、Ｂ、及びＧを前記リーダに返信し、
前記返信データは、呼び掛け応答及び前記タグの識別子を含み、同一の呼び掛けに対して応答するときであっても、それぞれの応答で特有であることを特徴とする方法。
【請求項１１】
請求項１０において、
前記オリジネータＯE及びＯOは、楕円曲線上のポイントであることを特徴とする方法。
【請求項１２】
請求項１０において、
前記オリジネータＯE及びＯOは、大きい素数のジェネレータであることを特徴とする方法。
【請求項１３】
請求項１０において、
前記ＲＦＩＤタグの初期化を含み、
前記初期化は、機密性のための第１キー対の第１パブリックキーと、難読化のための第２キー対の第２パブリックキーと、タグの識別子とを、前記リーダから受信することを含むことを特徴とする方法。
【請求項１４】
請求項１３において、
前記初期化は、認証のための第３のキー対を選択し、前記第３キー対のパブリックキーを前記リーダへ送信することを含むことを特徴とする方法。
【請求項１５】
請求項１３において、
前記初期化は、認証のための第３キー対のプライベートキーを前記リーダから受信し、前記第３キー対の前記プライベートキーが前記ＲＦＩＤタグによってのみ格納されることを特徴とする方法。
【請求項１６】
データを送信及び受信するトランシーバと、
暗号計算を実行する暗号ロジックと、を有し
前記トランシーバは、リーダシステムから呼び掛けを受信し、
前記暗号ロジックは、Ｓ＝ｆ（ｓ，ＯE），Ｕ＝ｆ（ｕ，ＯO），Ｂ＝Ｅ（ｎ，ｋE），Ｇ＝ｆ（Ａ，ｋO）を計算し、
Ａは、前記呼び掛け及び前記低処理電力システムのプライベートキーの関数であり、
ｓ及びｕは、乱数であり、
ｎは、前記低処理電力システムの識別子であり、
ｋE及びｋOは、それぞれ前記リーダの第１パブリックキー及び第２パブリックキーの関数であり、
ＯE及びＯOは、前記リーダによって提供されるオリジネータであり、
前記トランシーバは、Ｓ，Ｕ，Ｂ，及びＧを前記リーダシステムに返信し、前記返信データは、呼び掛け応答及び前記タグの識別子を含み、同一の呼び掛けに対して応答するときであっても、それぞれの応答で特有であることを特徴とする低処理電力システム。
【請求項１７】
請求項１６において、
前記低処理電力システムのプライベートキーと、前記低処理電力システムの識別子とを格納する安全なメモリを有することを特徴とする低処理電力システム。
【請求項１８】
請求項１６において、
前記暗号ロジックは、乱数ｓ及びｕを生成することを特徴とする低処理電力システム。
【請求項１９】
請求項１６において、
前記リーダの前記パブリックキーと、前記タグの識別子とを含む初期化データを格納するメモリを有することを特徴とする低処理電力システム。
【請求項２０】
請求項１６において、
前記オリジネータＯE及びＯOは、楕円曲線上のポイントであり、
前記オリジネータＯE及びＯOは、同じ楕円曲線上の同じポイントであることを特徴とする低処理電力システム。
【請求項２１】
リーダシステムによって安全に質問されるように設計された低処理電力システムであって、
前記リーダシステムから呼び掛けを受信するトランシーバと、
前記呼び掛けに対する応答を計算する暗号ロジックと、を有し、
前記応答は、前記低処理電力システムのプライベートキーを含み、
前記暗号ロジックは、前記リーダシステムへ返信するための返信データを計算し、
前記返信データは、前記呼び掛けに対する応答と、暗号化キーと、認証キーと、難読化キーとの組み合わせであることを特徴とする低処理電力システム。
【請求項２２】
請求項２１において、
前記暗号化キーは、２つの乱数を生成するものであり、第１乱数を暗号化キーで暗号化し、第２乱数を難読化キーで暗号化し、認証キーを前記リーダシステムのパブリックキーで暗号化することを特徴とする低処理電力システム。
【請求項１】
暗号プロトコルを提供する方法であって、
低処理電力システムのプライベートキーの使用に基づく認証と、
無権限者がタグの識別子を知ることができないように、前記タグの識別子を保護する機密性と、
呼び掛けに対する応答として異なる値が返され、リーダが前記応答によって前記低処理電力システムを識別することができないことを保証するアントレーサビリティと、を有することを特徴とする方法。
【請求項２】
請求項１において、
前記暗号プロトコルは、楕円曲線暗号を含むことを特徴とする方法。
【請求項３】
請求項１において、
前記認証は、前記低処理電力システムのプライベートキーを利用し、前記プライベートキーと受信した呼び掛けとの関数を前記低処理電力システムで計算することを特徴とする方法。
【請求項４】
請求項１において、
前記アントレーサビリティは、認証値と結合された追加の暗号値を提供することを特徴とする方法。
【請求項５】
請求項１において、
前記機密性は、リーダのパグリックキーで前記タグの識別子を暗号化することを特徴とする方法。
【請求項６】
請求項１において、
リーダと前記低処理電力システムとの間で初期パラメータを交換することを特徴とする方法。
【請求項７】
請求項６において、
前記初期パラメータは、前記認証、前記機密性、及び前記アントレーサビリティのための、タグの識別子と、楕円曲線と、前記楕円曲線上のポイントとを含むことを特徴とする方法。
【請求項８】
請求項７において、
前記楕円曲線及び前記ポイントは、前記認証、前記機密性、及び前記アントレーサビリティのために同一であることを特徴とする方法。
【請求項９】
請求項６において、
前記リーダは、前記初期パラメータを前記低処理電力システムに提供することを特徴とする方法。
【請求項１０】
ＲＦＩＤタグを利用する方法であって、
リーダから呼び掛けを受信し、
Ｓ＝ｆ（ｓ，ＯE），Ｕ＝ｆ（ｕ，ＯO），Ｂ＝Ｅ（ｎ，ｋE），Ｇ＝ｆ（Ａ，ｋO）を計算し、
ここで、Ａは、前記呼び掛け及び前記ＲＦＩＤタグのプライベートキーの関数、
ｓ及びｕは、前記ＲＦＩＤタグによって生成された乱数、
ｎは、前記タグの識別子、
ｋE及びｋOは、それぞれ前記リーダの第１パブリックキー及び第２パブリックキーの関数、及び
ＯE及びＯOは、前記リーダによって提供されるオリジネータであり、
Ｓ、Ｕ、Ｂ、及びＧを前記リーダに返信し、
前記返信データは、呼び掛け応答及び前記タグの識別子を含み、同一の呼び掛けに対して応答するときであっても、それぞれの応答で特有であることを特徴とする方法。
【請求項１１】
請求項１０において、
前記オリジネータＯE及びＯOは、楕円曲線上のポイントであることを特徴とする方法。
【請求項１２】
請求項１０において、
前記オリジネータＯE及びＯOは、大きい素数のジェネレータであることを特徴とする方法。
【請求項１３】
請求項１０において、
前記ＲＦＩＤタグの初期化を含み、
前記初期化は、機密性のための第１キー対の第１パブリックキーと、難読化のための第２キー対の第２パブリックキーと、タグの識別子とを、前記リーダから受信することを含むことを特徴とする方法。
【請求項１４】
請求項１３において、
前記初期化は、認証のための第３のキー対を選択し、前記第３キー対のパブリックキーを前記リーダへ送信することを含むことを特徴とする方法。
【請求項１５】
請求項１３において、
前記初期化は、認証のための第３キー対のプライベートキーを前記リーダから受信し、前記第３キー対の前記プライベートキーが前記ＲＦＩＤタグによってのみ格納されることを特徴とする方法。
【請求項１６】
データを送信及び受信するトランシーバと、
暗号計算を実行する暗号ロジックと、を有し
前記トランシーバは、リーダシステムから呼び掛けを受信し、
前記暗号ロジックは、Ｓ＝ｆ（ｓ，ＯE），Ｕ＝ｆ（ｕ，ＯO），Ｂ＝Ｅ（ｎ，ｋE），Ｇ＝ｆ（Ａ，ｋO）を計算し、
Ａは、前記呼び掛け及び前記低処理電力システムのプライベートキーの関数であり、
ｓ及びｕは、乱数であり、
ｎは、前記低処理電力システムの識別子であり、
ｋE及びｋOは、それぞれ前記リーダの第１パブリックキー及び第２パブリックキーの関数であり、
ＯE及びＯOは、前記リーダによって提供されるオリジネータであり、
前記トランシーバは、Ｓ，Ｕ，Ｂ，及びＧを前記リーダシステムに返信し、前記返信データは、呼び掛け応答及び前記タグの識別子を含み、同一の呼び掛けに対して応答するときであっても、それぞれの応答で特有であることを特徴とする低処理電力システム。
【請求項１７】
請求項１６において、
前記低処理電力システムのプライベートキーと、前記低処理電力システムの識別子とを格納する安全なメモリを有することを特徴とする低処理電力システム。
【請求項１８】
請求項１６において、
前記暗号ロジックは、乱数ｓ及びｕを生成することを特徴とする低処理電力システム。
【請求項１９】
請求項１６において、
前記リーダの前記パブリックキーと、前記タグの識別子とを含む初期化データを格納するメモリを有することを特徴とする低処理電力システム。
【請求項２０】
請求項１６において、
前記オリジネータＯE及びＯOは、楕円曲線上のポイントであり、
前記オリジネータＯE及びＯOは、同じ楕円曲線上の同じポイントであることを特徴とする低処理電力システム。
【請求項２１】
リーダシステムによって安全に質問されるように設計された低処理電力システムであって、
前記リーダシステムから呼び掛けを受信するトランシーバと、
前記呼び掛けに対する応答を計算する暗号ロジックと、を有し、
前記応答は、前記低処理電力システムのプライベートキーを含み、
前記暗号ロジックは、前記リーダシステムへ返信するための返信データを計算し、
前記返信データは、前記呼び掛けに対する応答と、暗号化キーと、認証キーと、難読化キーとの組み合わせであることを特徴とする低処理電力システム。
【請求項２２】
請求項２１において、
前記暗号化キーは、２つの乱数を生成するものであり、第１乱数を暗号化キーで暗号化し、第２乱数を難読化キーで暗号化し、認証キーを前記リーダシステムのパブリックキーで暗号化することを特徴とする低処理電力システム。
【図１】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８】
【公表番号】特表２００９−５４０７０３（Ｐ２００９−５４０７０３Ａ）
【公表日】平成２１年１１月１９日（２００９．１１．１９）
【国際特許分類】
【出願番号】特願２００９−５１４５６７（Ｐ２００９−５１４５６７）
【出願日】平成１９年６月１１日（２００７．６．１１）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０７０９１６
【国際公開番号】ＷＯ２００８／０３３５９０
【国際公開日】平成２０年３月２０日（２００８．３．２０）
【出願人】（５００４２１３７０）ヴェリサイン インコーポレイテッド (2)
【Ｆターム（参考）】
【公表日】平成２１年１１月１９日（２００９．１１．１９）
【国際特許分類】
【出願日】平成１９年６月１１日（２００７．６．１１）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０７０９１６
【国際公開番号】ＷＯ２００８／０３３５９０
【国際公開日】平成２０年３月２０日（２００８．３．２０）
【出願人】（５００４２１３７０）ヴェリサイン インコーポレイテッド (2)
【Ｆターム（参考）】
[ Back to top ]