(57)【特許請求の範囲】
【請求項１】
ＣＰＵを有するスマートカードが実行する暗号化計算ステップを有する暗号化方法であって、
前記スマートカードによりタスクを実行するステップと、
少なくとも１つの予備計算ステップと、
を更に有し、
前記予備計算ステップは、前記スマートカード自身により、前記スマートカードにより実行されるタスクに関係する前記ＣＰＵの入出力待機期間に実行され、前記タスクは前記予備計算ステップに対し優先し、
前記予備計算は中間的計算を複数ステップで実行することにより実行され、ステップｍ−１における前記中間的計算の結果は、スマートカードに記憶され、スマートカードにより実行されるタスクにより予備計算が中断される場合にステップｍで使用されることを特徴とする暗号化方法。
【請求項２】
前記方法は離散対数計算に基づくアルゴリズムを実行することを特徴とする請求項１記載の暗号化方法。
【請求項３】
前記予備計算が指数計算を含むことを特徴とする請求項１又は請求項２記載の暗号化方法。
【請求項４】
入出力インターフェース（Ｉ）を介して外部装置と通信することのできるスマートカード用の超小型回路であって、
ＣＰＵ（ＵＣ）と、
メモリ（Ｍ３）と、
少なくとも１つの予備計算ステップを実行する計算タスク（ＰＣ）を含むタスク実行手段（ＥＴ）と、
タスク実行管理手段（ＧＥ）と、を有し、
前記タスク実行管理手段（ＧＥ）が、前記超小型回路によって実行される他のタスクに関係する前記ＣＰＵ（ＵＣ）の入出力待機期間中、計算タスク（ＰＣ）を動作化する手段（ＡＰＣ）を有し、前記タスクは前記計算タスクに対し優先し、
前記予備計算は中間的計算を複数ステップで実行することにより前記タスク実行手段によって実行され、ステップｍ−１における前記中間的計算の結果は、前記超小型回路のメモリに記憶され、前記超小型回路により実行されるタスクにより予備計算が中断される場合にステップｍで使用されることを特徴とする超小型回路。
【請求項５】
前記タスク実行手段（ＥＴ）が、マイクロプロセッサ（ＵＣ）、タスク実行管理プログラムを持つプログラム・メモリ（Ｍ１）及び、1つ又は２以上のアプリケーション・プログラムの形で実行可能なタスクを持つアプリケーション・プログラム・メモリ（Ｍ３）を有することを特徴とする請求項４記載の超小型回路。
【請求項６】
前記タスク実行手段（ＥＴ）が暗号化計算回路（ＣＰ）を更に有することを特徴とする請求項５記載の超小型回路。
【請求項７】
前記タスク実行手段（ＥＴ）は指数計算を行うことができることを特徴とする請求項４〜６のいずれか1項記載の超小型回路。
【請求項８】
前記計算タスク動作化手段（ＡＰＣ）は、カードの入出力のスケジューリング回路（０）を含み、前記カードは、前記スケジューリング回路（０）が入力又は出力の待機時に前記タスク実行手段（ＥＴ）を動作化できることを特徴とする請求項４〜７のいずれか１項記載の超小型回路。
【請求項９】
計算結果の記憶手段（Ｍ３）を有することを特徴とする請求項４〜８のいずれか1項記載の超小型回路。
【請求項１０】
請求項４〜９のいずれか１項記載の超小型回路を含むことを特徴とする、非接触型超小型回路カード。
【請求項１１】
請求項４〜９のいずれか１項記載の超小型回路を含むことを特徴とする、接触型超小型回路カード。
【請求項１２】
請求項４〜９のいずれか１項記載の超小型回路を含むことを特徴とする、非接触モード又は接触モードで機能する超小型回路カード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、CPUを含むスマートカードにおける暗号化方法及び前処理計算を実行する方法に関する。又、本発明は、入出力インターフェースをして外部装置を通信を行うことができるスマートカードのための超小型回路（microcircuit）に関する。前記超小型回路は、計算タスクを含めタスクの実行のための手段及び、タスクの実行を管理する手段を有する。
【背景技術】
【０００２】
本発明は、接触型スマートカード又は非接触型スマートカード及びコンビネーション・カード（即ち、接触動作及び非接触動作の２つのモードを有するカード）に応用することができる。
スマートカードCは、図１に示す超小型回路MC、実質的には入出力インターフェース、マイクロプロセッサUC、オペレーティング・プログラム・メモリM1（例えば、ROM）、アプリケーション・プログラム・メモリM3（例えば、EEPROM）、ワーキング・メモリM２（例えば、RAM）を有している。
【０００３】
接触型スマートカードの場合は、入出力インターフェースが非同期送受信ユニットUART及び一般的にカードと同一平面レベルの８個の接点ゾーンを有するカードコネクタCNから形成される。
非接触型スマートカードの場合は、この入出力インターフェースは非同期ユニットUART及びアンテナを有する無線送受信機装置RFから形成されている。
コンビネーション・カードの場合は、このインターフェースは、勿論無線部分RFと接触部分CNを有している。
【０００４】
本発明の技術分野は、ｇｘと表記し、モジュロ（modulo）ｎの計算をする指数計算の結果を使うスマートカードの技術分野である。これら計算は、特にサイン又はメッセージの認証を行う数多くの応用分野で行われる。
現在使われている最も実際的で信頼の置ける認証又はサインのスキームは公開キー・アルゴリズムである。これらの内一番良く知られて、一番広く使われているものはRSAアルゴリズム（発明者のR.Rivest、A.Shamir及びL.Adlemanに因んで名づけられた）であるが、計算時間の点でコストがかかる。離散対数（discrete logarithm）に基づくスキームは昔から知られており、特に時間を費やす指数計算に関する前処理計算（precomputation）に適合しているので有利であった。
本発明は、数学の構造の如何に拘わらず、離散対数を使用し、公開キー・暗号化アルゴリズムを使う超小型回路カードに応用することができる。その構造として、特に、モジュロｎの数の環（リング、但しｎは集合ｚｎに属する。但し、ｚｎはｎより小さい正の整数の集合）、有限体GF（ｑ）（但しG(ｑ)はエレメントの数がｑで、ｑは素数又は素数の冪である）のような構造であっても良い。指数ｇｘはこれら構造体全てをカバーする。
このような計算を実行する手段の例は、特許出願FR No．FR 2 ７１６ 058に開示されている。
【０００５】
ｚｎの場合、及び、数ｂ、ｘ及びｎが通常長さ７６８から１０２４ビットを持つ数であって、モジュラー指数タイプ（即ちbx modulo n）の計算を要求する本実施例の場合、処理時間は５００−３００ｍｓの範囲である。この処理時間は、乗法とモジュロｎ計算の高速演算を行う“暗号化プロセッサー(crypto-processors)”を用いると８ビットのマイクロプロセッサで達成される。１６ビット又は３２ビットマイクロプロセッサを使えば、暗号化プロセッサのような特別な計算装置によらず、それ自身の性能で上記性能へ到達することができる。
【０００６】
これら性能では満足できない場合もある。公共輸送サービスにコンビネーション・カードを使用した例を紹介する。
地下鉄の駅、バスに入る時に、非接触モードで使うカードは、端末が切符を認証したり、割引のタイプを検査したり、及び／又は電子マネーによる支払い（PME）を受領する等を可能にする。この種の取引に対し、一般的にPMEタイプの取引に対して、公開キー暗号化アルゴリズムは、キー管理、標準に対するコンプライアンス、そして最終的にセキュリティーの観点から使用される。
【０００７】
このタイプの取引は１５０ｍｓ以内で実行される必要がある。これはユーザが、自然な動作で、改札に組み込んだ端末又はバスの乗り口に設置された端末でカードを通さなければならない時間である。この１５０ｍｓは、暗号化計算のみならず、メッセージの入出力、又暗号化計算以外の処理（それがカードの側であろうと端末の側であろうと）に必要な全時間をカバーしなければならない。端末側の処理及びカード側の処理は並列的には行われない。というのは予め定められたプロトコールに従った順序で処理が進むからである。実際に、端末で必要とされる計算時間を考慮すると、カード側の暗号化処理は大体３０ｍｓ以内に行う必要がある。
【０００８】
現在、この処理速度を達成できるICカード部品は存在しない。その上、非接触モードで動作するカードは、端末から放射するエネルギーをアンテナで集め電源とするもので、消費電力は制限され、処理能力も制限されている。
接触モードの時は、これら制限はさほど厳しくは無い。例えば電子財布による支払いに、顧客は、支払い場所で数秒以上待つ必要はない。しかし、ある種の処理では取引が短く、１秒のオーダが要求される。
【０００９】
公開キー暗号化アルゴリズムが行う処理の詳細について、特許FR No. 2 716 058を参照することができる。そこには、離散対数を使ったデジタルサイン及びメッセージ認証が紹介されている。前記特許に記載された方法を要約すると以下の通りである。
【００１０】
図２ａに示される予備フェーズの後にサイン処理が行われる。
銀行又は輸送会社等の事業者Aは公開キーＰＡ、秘密キーＳＡを持ち、数ｎ（ｎは素数又は素数の合成数）、ｇ（ｎより小さい、一般的にはかなり小さい整数）及びハッシュ関数ｈを選び、ＰＡ、ｎ、ｇとｈを、メッセージにサインをする存在Ｓ（例えば支払額を確認するカード）並びに、サインを検査しなければならない存在Ｖ（例えば商人が顧客に対して使う端末）に送る。
存在Ｓは、秘密キーｘを選択し、公開キー ｙ＝ｇ−ｘ  mod ｎ を計算し、事業者Aに送る。すると、事業者Aは、サインの秘密キーSAから作成された証明書Certを存在Sに送り返す。
【００１１】
データｎ、ｇ、ｘ、ｙ、Certは、存在Sのパーマネントデータである。
この予備段階が完了すると、メッセージMにサインする処理が開始する。即ち、図２ｂに示すSが、Vが示した支払額にサインすることである。メッセージMには特に、支払額ｍ及びこの支払いを要求する端末Vの識別情報が含まれている。
このサイン処理のステップは次の通りである。
ａ）  Ｓはランダムにｋを選ぶ。
ｂ）  証拠要素（witness element）：ｒ＝ｇｋ mod ｎ を計算する。
ｃ）  A、S及びVについての既知のハッシュ関数ｈを使ってｃ＝ｈ（ｒ,M）を計算する。
ｄ）最後にｓ＝ｋ＋ｃｘを計算する。
ｅ）  ＳはＶにこれらの情報（ｙ、Ｃｅｒｔ，Ｍ、ｃ、Ｓ）を送る。
Ｖは、ＰＡを使ってＣｅｒｔを検査し、ｕ＝ｙｃｇｓ mod ｎを計算し、ｃ＝ｈ（ｕ、Ｍ）を確かめる。もしこれが正しければ、Ｍのサインは認証される。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
この方法の手順の１つに、各取引における証拠ｒの計算がある。これには指数計算（例えば、ｒ＝ｇｋ mod ｎ）が必要である。この処理にはかなりの時間がかかる。そのため、しばしば、これら証拠の予備計算が考えられる。しかし、これら予備計算は外部装置で行われ、次に、対（ｋ、ｒ）はカードの記憶領域（例えば、M3）に書き込まれれる。このことが、問題になる。
それは、これら証拠要素を計算するのに必要なデータを知ることと、証拠要素自身について知ることとにより、暗号化秘密キーを見つけることが可能になるからである。確かに、ｒとｋを知ることによりｃ＝ｈ（ｒ、M）が導かれ、ｓ＝ｋ＋ｃｘ、ｋとｃを知れば、ｘが分かる。従って、秘密はそれを保持すると見なされた存在と、大きな信頼を寄せるべきこの外部装置との間で共有されることになる。
又、対（ｋ、ｒ）をカードに送ったり、書き込んだりするトータル・セキュリティを確保することが必要である。
又、もしカードがもはや対（ｋ、ｒ）を持たないとしたら、再入力する必要がある。このためには特別な端末をネットワークに接続せねばならない。
【課題を解決するための手段】
【００１３】
本発明の目的はこれらの問題を解決し、カードが対（ｋ、ｒ）を取引時間内に問題なく計算できるようにすることである。
本発明は、スマートカードのマイクロプロセッサ（即ちコンピュータ）において、処理時間の大半が外部事象の待機に使用されているという事実をベースに、考えられたものである。この待機時間に、即ち、カードが端末からの新たな制御信号を待っている間、又はカードが長いメッセージを入出力ポートで送受信している間に、対（r,k）の記憶領域が満杯でなければ、マイクロプロセッサは証拠要素ｒを計算することができる。
【００１４】
図３で示すケースにおいて、この待機時間に焦点を当てることにする。図３では、通信又はコンピュータ・ネットワークRを介して金融会社Fの再チャージ・サーバにつながっている装置Pを使ってコンビネーション・カード型の電子財布（PME）の再チャージを行っている。この装置は、通常のSIMカード（Subscriber Identity Module）に加えPMEような他のカードを受け入れることのできるミニテル（Minitel）端末又はコンピュータ又は携帯電話bi-fent（カード用２スロット付き）であってよい。
装置PにカードPMEを挿入すると、カードは接触モードで動作し、装置Pは、カードPMEに対しカード自身を認証する事を要求する。PMEのサインは、カードPMEに再チャージされる金額と共に、PによりRを介してFに送られる。この送信の開始から、装置Pに挿入されたカードPMEは待機状態になる。
【００１５】
ネットワークを介してFのサーバへの送信には５〜１０秒要する。FのサーバがPMEのサインを認証し、Fが再チャージ額にサインするには、約２秒かかる。同様に、サインされた再チャージのメッセージをネットワークRを介してFからPへ送信するには、また、５〜１０秒要する。従って、カードの待機時間は１５秒になる。
Pによる受信及び再チャージ・メッセージのカードPMEによる受信の後、後者はFのサインを検証する。その後、認証が成功裏に終わった場合、カードPMEはその貸方をアップデートする。
この例において、カードが、予備計算を行うのに充分な待機時間を持っていることが分かる。
【００１６】
この発明は、スマートカードの暗号化方法を対象とする。該カードはｃｐｕを持ち、前記方法は予備計算を行うもので、該予備計算がスマートカードにより実行され、又該予備計算がｃｐｕの入出力待機時間に行われる事を特徴とするものである。
本方法は、場合によっては、離散対数の計算に基づくアルゴリズムを実行しても良い。
１つの特徴に従って、前記予備計算は指数計算を含んでも良い。
予備計算は、中間的な計算を行ってステップ毎に実行し、この中間的計算結果をスマートカードに記憶すると有利である。
【００１７】
本発明のもう１つの対象は、入出力インターフェースＩを介して外部と通信でき、計算タスクＰＣを含むタスク実行手段ＥＴとタスク実行の管理手段ＧＥとを有し、該管理手段ＧＥが、超小型回路上で動作中のタスクの待機時間中の計算タスクＰＣの起動（activation）のための手段ＡＰＣを含むことを特徴とするスマートカードのための超小型回路である。
本発明の特徴によると、タスク実行手段ＥＴは、マイクロプロセッサＵＣ、タスク実行管理プログラムをもつプログラムメモリＭ１及び、アプリケーション・プログラムの形の実行可能なタスクを含むアプリケーション・プログラムメモリＭ３から構成される。
タスク実行手段ＥＴは、更に暗号化計算回路ＣＰを有する。
【００１８】
本発明の他の特徴によると、タスク実行手段ＥＴは指数計算を実行することができる。
本発明による他の実施例によると、計算タスク動作化手段ＡＰＣは、カードの、入出力スケジューリングの為の回路０を含む。該カードは、前記スケジューリング回路０が入出力を待つ間に、タスク実行手段ＥＴを動作させることができる。
超小型回路が前記計算結果を記憶する手段Ｍ３を有することが、好ましい。
本発明の対象は、前記した超小型回路を含む、無接点型及び／又は接点型の超小型回路カードである。
【図面の簡単な説明】
【００１９】
【図１】スマートカードの回路の全体図である。
【図２ａ】サイン方法を使用する前の予備的認証フェーズのフローの概略図である。
【図２ｂ】サイン方法のサイン・フェーズのフローの概略図である。
【図３】電子財布の再チャージ取引のフローの概略図である。
【図４】動作化手段ＡＰＣの機能を示すフローチャートである。
【図５】本発明に従う予備計算の一例のフローチャートである。
【発明を実施するための形態】
【００２０】
発明の他の特徴と効果は、以下の図面に基づき、実施例を用いて、明確に説明する。なお、実施例は一例であって、これに限定されるものではない。
本発明で考えたようなスマートカードの超小型回路は、バスで接続された種々の要素から構成される。これら要素の中で最も重要なものを図１に示す。
中央制御装置ＵＣ、即ち超小型回路は、ＲＯＭタイプの非揮発性メモリＭ１に記憶されるプログラムのインストラクションを実行する。従来技術に従うと、この中央制御装置ＵＣはクロック信号Ｈ及びインターフェースＩを介してリセット信号Ｒを受信する。カードが接触モードで動作すると、クロック信号Ｈ及びリセット信号Ｒが接点からやってくる。一方、カードが非接触モードで動作すると、これら信号は、無線受信装置ＲＦを介して受信される無線信号で与えられる。
【００２１】
この中央制御装置ＵＣは、しばしば指数計算modulo nの高速処理を専門に行う暗号化プロセッサＣＰの協力を得て処理を行う。
メモリＭ１は、タスクの実行管理手段ＧＥを含む。該手段は、ある場合にはＣＯＳ（“Chip or Card Operating System”超小型回路又はカードのオペレーティング・システム）に含まれる。ＣＯＳの機能は、入出力の管理を行い、メモリを整理・管理し、アクセスの許可（秘密コード）の管理を行い、リセット信号に対し応答を行い、カードのカスタム化を行う時又は、カードを使用する間、特定のサブプログラムのローディングを実行することである。メモリＭ１は、又、しばしばアプリケーション・プログラムを持つ。
【００２２】
メモリＭ１のプログラムは、ＲＡＭタイプのワーキング・メモリＭ２又は、レジスタ並びに、回路の電源が切られても消してはならない永久データのためにＥＥＰＲＯＭタイプの永久メモリＭ３を使用する。アプリケーション・プログラムは、しばしばこれらのメモリに蓄積される。
超小型回路は、外部と、数バイトのブロックの形式でメッセージのやりとりを行う非同期送受信ユニットＵＡＲＴを介して通信を行う。この非同期ユニットＵＡＲＴは、インターフェースＩを介して、入出力シリーズ・リンクＥＳと通信を行う。接触タイプのカードの場合は、メッセージは接触領域を通って通信し、無接点タイプの場合は、メッセージは無線装置ＲＦを通る。
【００２３】
超小型回路は、インターフェースＩとVss（Vss=０ボルト）に設定されたアース電位により電力の供給を受ける。なお、該インターフェースは、Ｖｃｃ（Vcc＝５ボルト）に設定された供給電圧で電力供給を受けている。接触モードでは、インターフェースIは接触により電力が供給されるが、非接触モードでは無線装置RFから来る無線信号により電力が供給される。
本発明によると、メモリM1に格納されたオペレーティング・システムCOSにおいて、タスクET及び各種アプリケーションを構成する他のタスクの管理手段GEが備えられる。これらタスクの中に、計算タスクPCがある。該計算タスクは、他のタスクに対応する待機時間の間に管理手段GEによって実行させられる。この待機時間はこうして予備計算を行い、計算結果をメモリM3に格納して、有利に使用されることになる。
このために、管理手段GEは、予備計算タスクPCの動作化手段APCを有する。この動作化手段APCはプログラムから構成されており、スケジューリング回路０に組み込まれている。
【００２４】
図４に示される動作化手段APCの動作の説明をする。図において、タスク“証拠要素の計算”は実行されている、即ち、証拠要素はステップＩで進行している。
外部事象があるとき、言い換えれば、タスク“証拠要素の計算”が計算を実行するために使う待機時間が終了した時（ステップII）で、もし、カードに対する電力供給がカットオフされない（ステップIII ）なら、手段APCは、権利があるものの手伝いをする。
【００２５】
外部事象が、UARTによる新たなNバイトのメッセージの受信に対応するならば、手段APCはこのメッセージを待っていたタスク（例えば、タスクｔ１）を手助けする（ステップIV）。
外部事象が、UARTによるN’バイトのメッセージの送信終了に対応するならば、手段APCはこのメッセージを送信したタスク（例えばタスクｔ２）を手助けする（ステップIV）。
手段ＡＰＣが手助けしたタスクｔｉ（例示したｔ１またはｔ２）が終了するか、外部事象が発生し（ステップＶ）、待機を引き起こす時に、手段ＡＰＣはこの待機期間にこのタスク“証拠要素の計算”が終わる（証拠要素の記憶領域が満杯になる）まで、又は、外部事象が現れて（ステップＶ）、初期状態に戻るまで、タスク“証拠要素の計算”に手助けを行う。
【００２６】
手段ＡＰＣは、タスク間のプライオリティ、アプリケーション・タスクを管理する。アプリケーション・タスクは、“証拠要素の計算”タスクに対して常にプライオリティが高い。
証拠要素の計算には、時間がかかる。例えば、数１００ｍｓかかる。この計算が、優先的なタスクである他のタスクにより、又は電源カットにより割り込まれる時、この計算はステップ毎に行われる。中間結果は記憶領域にセーブされる。この例ではＭ３である。このように、ＡＰＣ手段がこの“証拠要素の計算”タスクを再び手助けする時には、開始して完了していない計算は、消失しないので、最初から計算をやり直すことなく、再開することができる。即ち、ＡＰＣ手段が再び、前記タスクをまた手助けする時、もしタスクがステップｍの間に割り込むと、ステップｍ−１の結果はセーブされて、計算はステップｍから再開される。
【００２７】
もし、予め決められたループ数がカウントされていたなら、ステップそれ自体は、基礎的なループ及び、セービング動作を開始するのに使うループカウンタから形成される。具体的には、もしｋが３００ビットだとすると、計算は各々３０ループの１０ステップで行う。
【００２８】
図５に示すフローチャートの例を使って、証拠要素ｒを、公式ｒ＝ｇｋ ｍｏｄ ｎに従って計算する前記プロセスを説明する。
予備的ステップＩは計算に先行する：このステップは、セーブされたパラメータ値又はデフォールト値と共に、ｋを選択し、その後使うパラメータを初期化する手順を含む。計算は、比較、計算、セービング又は記憶動作からなるステップII乃至VIを含むループで行われる。
【００２９】
カードが待機期間中にこれら証拠要素の計算を行ってしまうので、取引中に最初にしたサイン方法のステップａ）とｂ）（ｋの選択とｒの計算）に換え、“記憶領域（この記憶領域は、前記した方法と均等な方法に従って満たされている。）から対（ｋ、ｒ）を読み出す”を行う事を可能にする。
カードにより実行される他の残りの計算は単純で高速な計算である。カード側で行う暗号化計算には少なくとも約１０ｍｓかかるが、必要な性能レベルを容易に達成できる。
【００３０】
更に、メモリスペースの節約を可能にする。
実際、ｋが再生可能な擬似ランダム信号発生器により発生されるならば、ｋはセーブされる必要は無い。発生器の入力パラメータがセーブされると、メモリスペースの節約になる。
同様に、対（ｋ、ｒ）全体を記憶する必要は無い。ｇｋ mod nのわずかなビット数を記憶するだけで充分である。その例は特許No．FR 2 752 122に記載されている。
【図１】
0005174256.tif 000002
【図２ａ】
0005174256.tif 000003
【図２ｂ】
0005174256.tif 000004
【図３】
0005174256.tif 000005
【図４】
0005174256.tif 000006
【図５】
0005174256.tif 000007