説明

スカラー倍計算装置、暗号化装置、復号化装置、署名生成装置、署名検証装置、鍵交換装置、スカラー倍計算方法およびプログラム

【課題】リソースが限られた環境で、安全性を低下させることなく、τ−NAFなどのKoblitz曲線上での従来のスカラー倍計算より高速であり、かつKoblitz曲線上の最小な加算回数と最小なフロベニウス写像の回数で処理可能なKoblitz曲線演算技術を実現することを目的とする。
【解決手段】τ−NAF表現の符号列と、このτ−NAF表現の符号列と同値であり、かつ予め最小な加算回数で処理でき、かつ最小なフロベニウス写像の回数で処理可能なτ−MLF表現の符号列と、を対応付けて格納している変換テーブル36(36a)を記憶部に有しており、入力されたスカラー値をτ−NAF表現の符号列に変換した後、前記変換テーブル36(36a)に従って、前記τ−NAF表現の符号列を前記τ−MLF表現の符号列へ変換することを特徴とする。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、Koblitz曲線のスカラー倍計算におけるスカラー倍計算装置、暗号化装置、復号化装置、署名生成装置、署名検証装置、鍵交換装置、スカラー倍計算方法およびプログラムの技術に関する。
【背景技術】
【0002】
楕円曲線暗号はN. Koblitz、V. S. Millerにより提案された公開鍵暗号の一種である。公開鍵暗号には、公開鍵(Public Key)と呼ばれる一般に公開してよい情報と、秘密鍵(Private Key)と呼ばれる秘匿しなければならない秘密情報がある。そして、与えられたメッセージの暗号化や署名の検証には公開鍵を用い、与えられたメッセージの復号化や署名の生成には秘密鍵を用いる。
【0003】
楕円曲線暗号における秘密鍵はスカラー値を用いる。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Pとそのスカラー倍の点dPが与えられた時、スカラー値dを求める問題である。楕円曲線上の点とは、楕円曲線の定義方程式を満たす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法(または加算)が定義される。そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の2倍算という。
【0004】
楕円曲線上の2点の加法は次のようにして計算される。2点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とx軸に関して対称な点を、加法を行った結果の点とする。
例えば、有限体F上に定義されたワイエルシュトラス型楕円曲線(以後、楕円曲線Eと呼ぶ。)の場合には、点(x,y)と点(x,y)とを加算した結果の点(x,y)((x,y)=(x,y)+(x,y))は、以下の式(1)〜(3)を計算することにより得られる。
【0005】
=λ+λ+x+x+a ・・・ 式(1)
=(x+x)λ+x+y ・・・ 式(2)
λ=(y+y)/(x+x) ・・・ 式(3)
【0006】
ここで、楕円曲線E/Fの定義方程式は、以下の式(4)で与えられる。
【0007】
+xy=x+ax+b,(a,bはともに有限体Fの元) ・・・ 式(4)
【0008】
なお、式(1)〜(3)における点(x,y)と点(x,y)と点(x,y)はいずれも楕円曲線E上の点である。すなわち、式(4)のx,yに各々x,y(i=1,2,3)を代入しても、式(4)の等式が成り立つ。
また、有限体Fは式(4)で与えられる楕円曲線Eの定義体と呼ばれる。ここで、rは正の整数である。
以後、正の整数rは、r=1とする。
【0009】
また、以後、楕円曲線暗号に用いる可換群としてE(F)を考える。ただし、E(F)は、式(4)の定義方程式で与えられる楕円曲線であり、楕円曲線上の各点P=(x,y)に対して、x,yがともにFの元であることを意味し、mは拡大次数と呼ばれる自然数である。以後、mは、E(F)の要素数#E(F)=h×n(h:小さな整数、n:大きな素数)を満たすような奇素数とする。
【0010】
楕円曲線上の点の2倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の一点において交わる。その交わった点とx座標に関して対称な点を、2倍算を行った結果の点とする。例えば、楕円曲線Eの場合には、点(x,y)の2倍算を行った結果の点(x,y)((x,y)=2(x,y)=(x,y)+(x,y))は、以下の式(5)〜(7)を計算することにより得られる。
【0011】
=λ+λ+a ・・・ 式(5)
=x+λx+x ・・・ 式(6)
λ=x+y/x ・・・ 式(7)
【0012】
しかしながら、式(5)〜(7)の計算では、処理負荷の高い乗算が3回使用され、さらに乗算より処理負荷の高い除算が1回使用されている。
このような処理負荷の軽減のために、Koblitz曲線と呼ばれる楕円曲線E上の点に対して、フロベニウス写像τと呼ばれる自己準同型写像を施すことが可能である。
点(x,y)に対してフロベニウス写像τを施すとは、以下の式(8)を計算することである。
【0013】
τ(x,y)=(x,y) ・・・ 式(8)
【0014】
式(8)によれば、乗算を2回までに軽減することが可能である。
また、以下の式(9)が成り立つことが知られている。
【0015】
(x,x)+2(x,y)=t(x,y) ・・・ 式(9)
【0016】
そして、式(9)の性質によりτを、以下の式(10)を満たす複素数と考えることができる。
【0017】
τ+2=μτ ・・・ 式(10)
【0018】
ここで、式(9)のtは式(4)で与えられるKoblitz曲線Eのトレースと呼ばれる整数であり、式(4)の係数aを用いてμ=(−1)1−aと書けることが知られている(例えば、非特許文献1参照)。
【0019】
楕円曲線E上の点(x,y)に対してフロベニウス写像τを施した点τ(x,y)=(x,y)もKoblitz曲線E上の点であることが知られている。
前記したように、ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果の点をスカラー倍点、その回数のことをスカラー値という。
楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の生成、および、その検証は、楕円曲線演算を用いて行う。その中で楕円曲線上のスカラー倍の計算は、前記の暗号化、復号化などの各処理において最も処理時間を要する計算である。そのため、楕円曲線暗号を高速に実行するためには、楕円曲線上のスカラー倍計算を高速に行う必要がある。特に、楕円曲線暗号において、スカラー値はおよび2160といったオーダとなり、計算時間の高速化の必要性が高い。
【0020】
最も基本的な楕円曲線のスカラー倍計算方法であるバイナリ法では、スカラー値の2進展開を左から右に向けて(または右から左に向けて)各桁を見て、零でない(非零)場合に楕円曲線上の加算を行い、桁をずらすことで楕円曲線上の2倍算を行う。
【0021】
これに対し、フロベニウス写像を実行することができる楕円曲線上のスカラー倍計算では、桁をずらすために楕円曲線上の2倍算を行う代わりにフロベニウス写像を用いることができることが知られている。フロベニウス写像は、楕円曲線暗号実装の際に、楕円曲線上の点を、正規基底を用いて実装した場合、シフト演算のみを用いて計算でき、2倍算に比べて処理が高速である(多項式基底、および、正規基底については、例えば、非特許文献1参照)。
【0022】
従って、楕円曲線暗号実装の際に楕円曲線として、フロベニウス写像を持つ楕円曲線を採用し、フロベニウス写像を用いた展開(フロベニウス展開)を用いればスカラー倍計算の高速化が可能となる。
この性質を利用して、楕円曲線上のスカラー倍計算を高速に計算できる曲線の一つとしてKoblitz曲線が知られている(例えば、非特許文献1参照)。
また、2倍算を減らすだけでなく、スカラー倍計算の際に必要な楕円曲線上の加算回数自体を低減することにより、スカラー倍計算を高速化できる。楕円曲線上のスカラー倍計算では、前記したように、非零の場合に加算が行われるため、非零濃度を最小とすることにより、高速化する方法がある。ここで、非零濃度とは、(非零桁の個数)/(展開の桁長)の漸近的な値を指す。一般に、与えられたスカラー値に対して、ある展開における非零濃度が最小のとき、その展開を用いたスカラー倍計算は、スカラー倍計算に関して高速化されることは、前記のように知られている。
【0023】
この性質を利用して楕円曲線上のスカラー倍計算を高速に行う手法の一つとして、与えられたスカラー値に対して、予め定められた整数を用いてエンコードした場合のスカラー値の非零濃度が最小となる展開(NAF(Non-Adjacent Form))を行うことにより、楕円曲線上のスカラー倍計算の高速化を図る方法がある(例えば、非特許文献2参照)。
さらに、前記したフロベニウス展開と小さな非零濃度をもつ展開を同時に実現することにより、さらなる高速化を図る方法としてKoblitz曲線におけるτ−NAFが知られている(非特許文献1参照)。また、このτ−NAFは非零濃度が最小であることが知られている(非特許文献3参照)。
また、与えられたスカラー値のビット表現からτ-NAFにエンコードする処理には比較的重い処理が含まれているため、τ−NAFにエンコードする際に比較的重い処理を排除するエンコード方法がある(例えば、特許文献1および非特許文献2参照)。
【先行技術文献】
【特許文献】
【0024】
【特許文献1】米国特許出願公開第2004/0119614号明細書
【非特許文献】
【0025】
【非特許文献1】J. A. Solinas, Efficient Arithmetic on Koblitz Curves, Designs, Codes and Cryptography, Vol.19, No.2-3, Kluwer Academic Publishers, pp. 195 - 249, 2000.
【非特許文献2】M. Joye, and C. Tymen, Compact Encoding of Non-Adjacent Forms with Applications to Elliptic Curve Cryptography, In 4th International Workshop on Practice and Theory in Public Key Cryptography(PKC 2001), Vol.1992 of Lecture Notes in Computer Science, pp. 353 - 364, Springer-Verlag, 2001.
【非特許文献3】R. M. Avanzi, C. Heuberger, and H. Prodinger, Minimality of the Hamming Weight of the τ-NAF for Koblitz Curves and Improved Combination with Point Halving, In Selected Areas in Cryptography - SAC 2005, Vol.3897 of Lecture Notes in Computer Science, pp. 332 - 344, Springer-Verlag, 2006.
【発明の概要】
【発明が解決しようとする課題】
【0026】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証の為に暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度やメモリ使用量などがある。しかし、一般に安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、すべての要件を満たすことは難しい。
一般に、暗号に用いられる鍵の長さ(鍵長)は安全性の指標とされ、長いほど安全性が高くなることが知られている。しかしながら、鍵長が長いほど処理に時間がかかる。
【0027】
楕円曲線上の離散対数問題の求解の困難性は素因数分解の困難性に比べて高いため、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号は鍵長を比較的短くすることができる。従って、楕円曲線暗号によれば、計算能力、メモリ容量などのリソースが比較的少なくても、素因数分解問題の困難性を利用する暗号処理と同等の安全性を有する暗号処理を短時間の処理、すなわち、リソースへの負担が少ない処理で実現することが可能である。
【0028】
最近では、スマートカード(IC(Integrated Circuit)カードともいう)など、利用可能なリソースがかなり限られている環境においても、安全性の高い暗号処理の必要性が高まっている。スマートカードのようなリソースの少ない環境では、限られたリソース内で暗号処理の最適化を図る必要がり、安全性を高めるために鍵長を長くすると処理負担の増大が大きくなるため、さらにリソースへの負担の少ない高速な処理が求められている。
非特許文献1には、入力された整数を、最小な非零濃度をもつフロベニウス展開τ−NAFに変換し、このτ−NAFを用いたKoblitz曲線におけるスカラー倍計算方法が記載されている。しかし、一回のフロベニウス写像は高速に処理できるが、τ−NAFの展開の長さの低減まで考慮されていない。
【0029】
また、特許文献1および非特許文献2には、入力された整数を、予め定められた変換テーブルを利用して最小な非零濃度をもつフロベニウス展開τ−NAFに変換し、このτ−NAFを用いたKoblitz曲線におけるスカラー倍計算方法が記載されている。しかし、一回のフロベニウス写像は高速に処理できるが、τ−NAFの展開の長さの低減まで考慮されていない。
すなわち、Koblitz曲線上での従来のスカラー倍計算においては、Koblitz曲線上の加算回数の最小化は実現されているが、フロベニウス写像の回数の最小化を実現することが可能なものはない。
【0030】
このような背景に鑑みて本発明がなされたのであり、本発明は、リソースが限られた環境で、安全性を低下させることなく、τ−NAFなどのKoblitz曲線上での従来のスカラー倍計算より高速であり、かつKoblitz曲線上の最小な加算回数と最小なフロベニウス写像の回数で処理可能なKoblitz曲線演算技術を実現することを目的とする。
【課題を解決するための手段】
【0031】
前記課題を解決するため、本発明は、第1の符号列と、この第1の符号列と同値であり、かつ予め最小な加算回数で処理でき、かつ最小なフロベニウス写像の回数で処理可能な第2の符号列と、を対応付けて格納している変換情報を記憶部に有しており、入力されたスカラー値を第1の符号列に変換した後、前記変換情報に従って、前記第1の符号列を前記第2の符号列へ変換することを特徴とする。
その他の解決手段については、実施形態中で適宜説明する。
【発明の効果】
【0032】
本発明によれば、リソースが限られた環境で、安全性を低下させることなく、τ−NAFなどのKoblitz曲線上での従来のスカラー倍計算より高速であり、かつKoblitz曲線上の最小な加算回数と最小なフロベニウス写像の回数で処理可能な楕円曲線演算技術を実現することができる。
【図面の簡単な説明】
【0033】
【図1】本実施形態の暗号通信システムのシステム構成図である。
【図2】本実施形態に係るスカラー倍計算部の構成例を示す図である。
【図3】第1実施形態に係る変換テーブルの構成を示す図である。
【図4】第1実施形態に係るメッセージ暗号化処理について説明するタイミングチャートである。
【図5】第1実施形態に係るメッセージ復号化処理について説明するタイミングチャートである。
【図6】第1実施形態に係るエンコード処理の流れを示すフローチャートである。
【図7】第1実施形態に係る実計算処理の流れを示すフローチャートである。
【図8】第2実施形態に係る変換テーブルの構成例を示す図である。
【図9】第2実施形態に係るエンコード処理の流れを示すフローチャートである。
【図10】第3実施形態に係るスカラー倍計算部の構成例を示す図である。
【図11】第3実施形態に係る変換テーブルの構成例である。
【図12】第3実施形態に係るエンコード処理の流れを示すフローチャートである(その1)。
【図13】第3実施形態に係るエンコード処理の流れを示すフローチャートである(その2)。
【図14】第4実施形態に係る署名検証システムのシステム構成図である。
【図15】第4実施形態に係るメッセージの署名生成処理について説明するタイミングチャートである(その1)。
【図16】第4実施形態に係るメッセージの署名検証処理について説明するタイミングチャートである(その2)。
【図17】第5実施形態に係る鍵交換システムの構成例を示す図である。
【図18】第5実施形態に係る鍵交換処理について説明するタイミングチャートである。
【発明を実施するための形態】
【0034】
次に、本発明を実施するための形態(「実施形態」という)について、適宜図面を参照しながら詳細に説明する。なお、各図において、同様の構成要素に対しては同一の符号を付して説明を省略することとする。
本実施形態における計算方法は、スカラー値のτ−NAF表現を、非零濃度を変えることなく長さが最小となるエンコード方法であり、以下、このエンコード方法をτ−MLF(τ-adic Minimal Length Form)と称し、τ−MLFによる数値列をτ−MLF表現の数値列と称することとする。
【0035】
《第1実施形態》
まず、図1〜図7を参照して、本発明に係る第1実施形態を説明する。
【0036】
(システム構成)
図1は、本実施形態の暗号通信システムのシステム構成図である。
暗号通信システムAは、ネットワーク6により接続された暗号化コンピュータ1Aおよび復号化コンピュータ1Bとを備える。
【0037】
本実施形態の暗号通信システムAにおいては、暗号化コンピュータ1AでメッセージPの暗号化を行い、復号化コンピュータ1Bで暗号メッセージの復号を行う。ここで、暗号化コンピュータ1Aおよび復号化コンピュータ1Bは、それぞれ専用のコンピュータという意味ではなく、実行されるプログラムによるものである。つまり、実行されるプログラムによっては、暗号化コンピュータ1Aが復号化コンピュータ1Bにもなり得るし、復号化コンピュータ1Bが暗号化コンピュータ1Aにもなり得る。
【0038】
図1において、暗号化コンピュータ1Aおよび復号化コンピュータ1Bは、CPU(Central Processing Unit)21A,21Bやコプロセッサ22A,22Bなどの演算装置(処理部2A,2B)、RAM(Random Access Mmory)31A,31B、ROM(Read Only Memory)34A,34Bや外部記憶装置35A,35Bなどの記憶装置(記憶部3A(3),3B(3))、コンピュータ外部とのデータ入出力を行う入出力インタフェース(入力部)4A,4Bを有している。さらに、暗号化コンピュータ1Aおよび復号化コンピュータ1Bは、外部にユーザが操作するためのキーボード6A,6Bおよびディスプレイ5A,5B、着脱可能な可搬型記憶媒体の読書装置(図示せず)などが接続されている。
【0039】
さらに、暗号化コンピュータ1Aでは、外部記憶装置35Aに格納されているデータ処理部32Aや、スカラー倍計算部33A(33)のプログラムがRAM31Aに展開され、CPU21Aやコプロセッサ22Aなどの演算装置によって実行されている。
データ処理部32Aは、第1実施形態〜第3実施形態においては、暗号化処理部として機能し、入力されたメッセージの暗号化を行う。
スカラー倍計算部33Aは、データ処理部32Aで暗号化を行うのに必要なパラメタを計算する。スカラー倍計算部33Aの詳細な構成は図2を参照して説明する。
なお、暗号化コンピュータ1Aの外部記憶装置35Aには、図3、図8、図11を参照して後記する変換テーブル(変換情報)36A(36)や、秘密情報37A(例えば、秘密鍵)や、定数38A(例えば、公開鍵や、Koblitz曲線の定義式や、Koblitz曲線上の定点)などが格納されている。
【0040】
kは乱数、dは秘密鍵を示す定数、QはKoblitz曲線上の定点、dQは公開鍵を示す点とすると、暗号化コンピュータ1Aは、P+k(dQ)およびkQを計算して出力する機能を有している。そして、復号化コンピュータ1Bは、秘密鍵d、および、kQより−d(kQ)を計算し、式(11)を計算して出力する機能を有している。
【0041】
(P+k(dQ))-d(kQ) ・・・ 式(11)
【0042】
ここで、メッセージPを復元するためには、kdQ、すなわちkQのd倍を計算する必要がある。ところが、暗号通信システムAのネットワーク6には、P+k(dQ)、kQのみ送信され、秘密鍵dは送信されないため、秘密鍵dを保持しているものだけが、Pを復元できることになる。
【0043】
また、復号化コンピュータ1Bでは、外部記憶装置35Bに記憶されているデータ処理部32Bや、スカラー倍計算部33B(33)のプログラムがRAM31Bに展開され、CPU21Bやコプロセッサ22Bなどの演算装置によって実行されている。
データ処理部32Bは、復号化コンピュータ1Bにおいては、復号化処理部として機能し、暗号化されたメッセージである暗号メッセージの復号を行う。
スカラー倍計算部33Bは、データ処理部32Bで復号化を行うのに必要なパラメタを計算する。スカラー倍計算部33Bの詳細な構成は図2を参照して説明する。
なお、暗号化コンピュータ1Bの外部記憶装置35Bには、図3、図8、図11を参照して後記する変換テーブル36B(36)や、秘密情報37B(例えば、秘密鍵)や、定数38B(例えば、公開鍵や、使用するKoblitz曲線の定義式やKoblitz曲線上の定点)などが格納などが記憶されている。
なお、定数38Aおよび定数38Bには、共通のKoblitz曲線上の定点Qが格納されている。
【0044】
なお、データ処理部32A,32Bや、スカラー倍計算部33A,33Bのプログラムは、予めコンピュータ内の外部記憶装置35A,35Bや、図示しないフラッシュメモリなどに格納されていてもよいし、必要な時に、入出力インタフェース4A,4Bおよび各コンピュータが利用可能な媒体を介して、他の装置から外部記憶装置35A,35Bに記憶されてもよい。ここで、媒体とは、例えば、入出力インタフェース4A,4Bに着脱可能な記憶媒体、または通信媒体(すなわち、ネットワーク6またはネットワーク6を伝搬する搬送波)を指す。
【0045】
(スカラー倍計算部構成)
図2は、本実施形態に係るスカラー倍計算部の構成例を示す図である。なお、図2に示す構成は、図1における暗号化コンピュータ1Aおよび復号化コンピュータ1Bにおいて、共通の構成である。
スカラー倍計算部33は、スカラー値およびKoblitz曲線上の定点を入力とし、スカラー倍点を出力するものであり、エンコード部300と、実計算部350とを備える。
そして、エンコード部300は、τ−NAF計算部301、τ−NAF長計算部302、格納部303、δ剰余計算部304、条件判定部305、τ−MLF計算部306を備える。また、実計算部350は、加算部351、τ倍算部352、繰り返し判定部353、数値判定部354を有する。各部301〜306,351〜354の機能については、処理の説明において後記する。
【0046】
(変換テーブル)
図3は、第1実施形態に係る変換テーブルの構成を示す図である。
変換テーブル36a(36)は、左から変換前の数値列(τ−NAF表現の数値列:第1の符号列)、変換後の数値列(τ−MLF表現の数値列:第2の符号列)、変換後の桁数を示している。
【0047】
図3の変換テーブル36aの1列目には、6桁のτ−NAF表現の数値列(en−1,en−2,en−3,en−4,en−5,en−6τのすべてのパターンが記載されている。ここで対象となる数値列は、スカラー値をτ−NAF変換した数値列のうち、上位6桁が対象となるものである。
2列目には、1列目の同一行に記載されている6桁のτ−NAF表現の数値列(en−1,en−2,en−3,en−4,en−5,en−6τに対応するτ−MLFの数値列(gm−1,・・・,gn−6τが記載されている。
そして、3列目には、1列目の同一行に記載されている6桁のτ−NAF表現(en−1,en−2,en−3,en−4,en−5,en−6τを2列目の同一行に記載されているτ−MLF(gm−1,・・・,gn−6τに変換した場合の桁数mの値が記載されている。3列目におけるnは、τ−NAF表現の数値列の全桁数である。
【0048】
例えば、符号401の数値列などは無変換である。つまり、桁数を減ずることはできない。しかしながら、例えば符号402の数値列は、数値列が示す数値を保ったまま、2桁減ずることができる。
【0049】
ここで、図3の変換テーブル36aに記載されているμは式(10)を満たす整数である。図3の変換テーブル36aを用いて6桁のτ−NAF表現の数値列(en−1,en−2,en−3,en−4,en−5,en−6τからτ−MLF(gm−1,・・・,gn−6τへ変換する方法を説明する。例えば、行402に示されている6桁のτ−NAF表現の数値列(±μ,0,0,±1,0,0)τを変換する場合、エンコード部300(図2)は以下の変換を行う。
【0050】
【数1】

【0051】
この場合、6桁のτ−NAF表現をτ−MLFに変換すると、2桁分短くなっているので、τ−MLFの長さm=n−2となる。
【0052】
なお、τ−MLFの長さmは2列目のτ−MLFから計算することが可能なので、3列目を変換テーブル36aに記載しなくてもよい。また、3列目のmがn=mであれば同一行に記載されている6桁のτ−NAF表現とτ−MLF表現は一致するため、n=mを満たす6桁のτ−NAF表現とτ−MLF表現は変換テーブル36aに記載せず、mがn−3≦m≦n−1の場合のみの数値の対を変換テーブル36aに記載するようにしてもよい。また、変換テーブル36aにおいて、mがn−3≦m≦n−1となるτ−NAF表現とτ−MLF表現の対をすべて記載する必要はなく、少なくとも一つ以上を変換テーブル36aに記載し、後記するステップS205において、変換テーブル36aに記載されている6桁のτ−NAF表現の数値列のみを、τ−MLF表現の数値列に変換するようにしてもよい。
【0053】
(情報の送受信)
次に、図1および図2を参照しつつ、図4および図5に沿ってメッセージの暗号化処理および復号化処理の概要を説明する。
図4および図5は、メッセージの暗号化処理および復号化処理を行う場合における暗号化コンピュータ1Aおよび復号化コンピュータ1B内の情報の送受信について説明するタイミングチャートである。
まず、暗号化コンピュータ1Aが、入力されたメッセージを暗号化する場合の動作について図4を参照して説明する。メッセージはディジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。
まず、データ処理部32Aは、入出力インタフェース4Aを介して、平文メッセージ(入力メッセージ)を取得する(S101)。
そして、データ処理部32Aは、入力された平文メッセージのビット長があらかじめ定めたビット長か否かを判断する。平文メッセージのビット長が、予め定めたビット長よりも長い場合、データ処理部32Aは、予め定めたビット長となるように平文メッセージを区切り、部分メッセージを生成する(S102)。以下、メッセージとは、所定のビット長に区切られている部分メッセージであるものとして説明する。
【0054】
次に、データ処理部32Aは、メッセージのビット列によって表される数値をx座標(x)に持つKoblitz曲線上の定点Pのy座標(y)の値を計算する(S103)。
ここで、使用する楕円曲線をKoblitz曲線とすると、Koblitz曲線は、aを定数とするとき、式(12)で表されるので、データ処理部32Aは、この式(12)よりy座標の値を求めることができる。
【0055】
+xy=x+ax+1 ・・・ 式(12)
【0056】
次に、データ処理部32Aは、乱数kを生成する(S104)。そして、データ処理部32Aは、記憶部3A(具体的には外部記憶装置35A)に格納されている定数38Aから公開鍵dQと、Koblitz曲線上の定点Qのx座標とを取得する(S105)。
そして、データ処理部32Aは、読み出した公開鍵dQとQのx座標と、求めたy座標の値(Koblitz曲線上の定点)と、乱数k(スカラー値)とをスカラー倍計算部33Aへ送る(S106)。
スカラー倍計算部33Aのエンコード部300(図2)が、kのτ−MLF表現の数値列を計算するエンコード処理を行い(S107)、実計算部350が、kのτ−MLF表現の数値列を使用して、Qのx座標、y座標の値、乱数kによるスカラー倍点(xd1,yd1)=kQと、公開鍵dQのx座標、y座標の値、乱数kによるスカラー倍点(xd2,yd2)=k(dQ)とを計算する実計算処理を行い(S108)、スカラー倍計算部33Aは、計算したスカラー倍点をデータ処理部32Aへ送る(S109)。エンコード処理は、図6、図9、図12および図13で後記する処理が行われる。また、実計算処理は、図7で後記する処理が行われる。
【0057】
データ処理部32Aは、受け取ったスカラー倍点を用いて、暗号化処理を行う(S110)。Koblitz曲線の場合、P+k(dQ)を計算するすなわち、データ処理部32Aは、以下の式(13),(14)を計算し、暗号化されたメッセージxe1,xe2を得る。
【0058】
e1=((yd1+y)/(xd1+x))+((yd1+y)/(xd1+x))+x+xd1+a ・・・ 式(13)
e2=xd2 ・・・ 式(14)
【0059】
そして、データ処理部32Aは、1つ以上の部分メッセージから暗号化された出力メッセージを組み立て、この出力メッセージをデータとして入出力インタフェース4Aから出力する(S111)。出力メッセージは、ネットワーク6を介して復号化コンピュータ1Bへ転送される。
【0060】
なお、図4において記憶部3Aからの情報の読み出し(S105)は、スカラー倍計算部33Aへ、当該情報を送る処理(S106)の前であればよい。例えば、入力メッセージを受け付ける(S101)の前であってもよい。
【0061】
次に、復号化コンピュータ1Bが、暗号化されたメッセージである出力メッセージを復号化する場合の動作について、図5を用いて説明する。
復号化コンピュータ1Bのデータ処理部32Bは、入出力インタフェース4Bを介して、暗号化コンピュータ1Aによって暗号化されたメッセージを入力メッセージとして入力を受け付けると(S201)、入力メッセージのデータ141のビット長が予め定められているビット長か否かを判断する。予め定めたビット長よりも長い場合、データ処理部32Bは、予め定めたビット長となるように暗号化されたデータを区切ることによって部分メッセージを生成する(S202)。以下、メッセージは、所定のビット長に区切られている部分データ(単にデータともいう)であるものとして説明する。
【0062】
次に、データ処理部32Bは、データ141のビット列によって表される数値をx座標にもつKoblitz曲線上のy座標の値を計算する(S203)。
暗号化されたメッセージがxe1,xe2のビット列であり、Koblitz曲線の場合、y座標の値(ye1)は、以下の式(15)(ただし、aは式(12)と同じ定数である。)から得ることができる。
【0063】
e1+xe1e1=xe1+axe1+1 ・・・ 式(15)
【0064】
続いて、データ処理部32Bは、記憶部3B(具体的には、外部記憶装置35B)に格納されている秘密情報37Bから秘密鍵dを読み出す(S204)。
そして、データ処理部32Bは、読み出した秘密鍵d(スカラー値)と、Koblitz曲線上の定点としてのx座標、y座標の値(xe2,ye2)を、スカラー倍計算部33Bへ送る(S205)。
スカラー倍計算部33Bのエンコード部300は、秘密鍵dのτ−MLF表現の数値列を計算するエンコード処理を行い(S206)、秘密鍵dのτ−MLF表現の数値列を用いて、Koblitz曲線上の定点のx座標、y座標の値、秘密情報37B(秘密鍵d)のスカラー倍点(xd3,yd3)=d(xe2,ye2)を計算する実計算処理を行う(S207)。
その後、スカラー倍計算部33Bは、計算されたスカラー倍点をデータ処理部32Bへ送る(S208)。データ処理部32Bは、送られたスカラー倍点を用いて、復号化処理を行う(S209)。
【0065】
例えば、暗号化されたメッセージが、xe1,xe2のビット列であり、Koblitz曲線の場合、データ処理部32Bが、以下の式(16)を計算することにより復号化を達成できる。
【0066】
(P+k(dQ))-d(kQ)=(xe1,ye1)−(xd3,yd3) 式(16)
【0067】
すなわち、データ処理部32Bは以下の式(17)を計算し、暗号化される前の部分メッセージxに相当するxf1を得る。
【0068】
f1=((ye1+yd3)/(xe1−xd3))+((ye1+yd3)/(xe1−xd3))+xe1+xd3+a ・・・ 式(17)
【0069】
復号化コンピュータ1Bは、データ処理部32Bで復号された部分メッセージから平文メッセージを組み立て、入出力インタフェース4Bを介して、ディスプレイ5Bなどから出力メッセージとしての平文メッセージを出力する(S210)。
【0070】
ここで、第1実施形態によるスカラー倍演算処理の詳細な説明に入る前に、スカラー倍計算部33が、スカラー値dとKoblitz曲線上の定点Pとから、Koblitz曲線におけるスカラー倍点dPを計算する第1の計算方法の概略を説明する。
【0071】
本実施形態におけるスカラー倍計算処理は、Koblitz曲線上の定点とスカラー値とからスカラー倍点を計算するにあたり、スカラー値を第1の数値列(第1の符号列)にエンコードした後、さらに、第1の数値列とは異なる第2の数値列(第2の符号列)に、変換テーブル36に従って変換し、第2の数値列を用いてスカラー倍点を計算する。このとき、第1の数値列は、τ−NAF表現の数値列であり、第2の数値列は、τ−NAF表現の数値列(第1の数値列)の上位6桁を予め定められた規則に従って変換した数値列(τ−MLF表現の数値列)である。図3の変換テーブル36aで説明したように、第1の数値列の一部は、より数値列の長さが短い第2の数値列に変換することができる。
【0072】
スカラー倍計算部33は、この第2の数値列であるτ−MLF表現の数値列とKoblitz曲線上の定点とを用いてスカラー倍計算を実行することにより、高速化を実現する。
第1実施形態のスカラー倍計算処理全体の概要は以下の通りである。
スカラー倍計算部33がデータ処理部32A,32Bからスカラー値dとKoblitz曲線上の定点Pとを受け取ると、エンコード部300は、入力されたスカラー値dを数値列pにエンコードする。すなわち、式(18),(19)を満たすpに、スカラー値dを変換する。
【0073】
dc=p+pτ+pτ+…+pq−1τq−1 ・・・ 式(18)
−1≦p≦1 ・・・ 式(19)
【0074】
ここで、式(18)の長さqは前記した拡大次数mを用いて以下の式(20)を満たす正整数である。
【0075】
q≦m+2 ・・・ 式(20)
【0076】
また、dc=r+rτは以下の式(21)を満たす複素数δに対して、式(22)を満たす複素数であり、Qは複素数である。
【0077】
δ=(τ−1)/(τ−1) ・・・ 式(21)
d=δQ+dc ・・・ 式(22)
【0078】
このとき、本実施形態では、0≦i≦q−7なる各iについて、隣り合う数値の対(pi+1,p)は以下の式(23)を満たす。
【0079】
i+1=0 ・・・ 式(23)
【0080】
そして、q−6≦i≦q−1のとき、数値列(pq−1,pq−2,pq−3,pq−4,pq−5,pq−6τは、図3の変換テーブル36aにおける(gm−1,・・・,gn−6τのいずれか一つと等しい。
ここで、(pq−1,pq−2,pq−3,pq−4,pq−5,pq−6τは、以下の式(24)を意味する。
【0081】
(pq−1,pq−2,pq−3,pq−4,pq−5,pq−6τ=pn−6+pn−5τ+pn−4τ+pn−3τ+pn−2τ+pn−1τ ・・・ 式(24)
【0082】
実計算部350は、後に記載するエンコード処理によって、τ−MLF表現にエンコードされたスカラー値d=(gm−1,gm−2,…,g,gτとKoblitz曲線上の定点Pとを用いてスカラー倍点dPを計算する。
【0083】
(エンコード処理)
次に、図2および図3を参照しつつ、図6および図7に沿ってスカラー倍計算処理時のエンコード部300、実計算部350の行う各処理について詳細に説明する。
図6は、第1実施形態に係るエンコード処理(図4のステップS107)の流れを示すフローチャートである。なお、図5のステップS206のエンコード処理も同様の処理手順である。
ここでは、スカラー値を第1の数値列(τ−NAF表現の数値列)にエンコードし、さらに、第1の数値列を第2の数値列(τ−MLF表現の数値列)にエンコードする処理を行う。
まず、エンコード部300が、スカラー値dの入力を受け付ける(S301)。
次に、δ剰余計算部304が、入力されたスカラー値dに対して、式(25)を満たす整数dを計算する(S302)。ここで、式(25)におけるδは式(21)により算出される値である。
【0084】
=d mod δ ・・・ 式(25)
【0085】
そして、τ−NAF計算部301とτ−NAF長計算部302は、整数dを、式(26)〜(28)を満たすτ−NAF表現の数値列に変換する(S303)。
【0086】
=e+eτ+…+en−1τn−1 ・・・ 式(26)
|e|≦1 ・・・ 式(27)
i+1=0 ・・・ 式(28)
【0087】
ここで、式(26)のen−1はen−1≠0を満たす。
スカラー値dから式(25)を満たす整数dを計算する方法、および、整数dを式(26)〜(28)を満たすように展開する方法は、非特許文献1に記載されている。
なお、式(26)のnと前記した拡大次数mの間に、以下の式(29)を満たす関係があることは、例えば、「D. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, Vol.27, No.1, pp.129-146, 1998.」に記載されている。
【0088】
n≦m+2 ・・・ 式(29)
【0089】
次に、エンコード部300は、ステップS304〜S307の処理でτ−NAF表現の数値列(en−1,en−2,…,eτから、τ−MLF表現の数値列(gm−1,gm−2,・・・,gτを生成する。
まず、条件判定部305は、n≧6であるか否かを判定する(S304)。
ステップS304の結果、n≧6が成立する場合(S304→Yes)、τ−MLF計算部306は、図3の変換テーブル36aに従ってτ−NAF表現の数値列の上位6桁を変換する(S305)。
具体的には、τ−MLF計算部306はτ−NAF表現の数値列の上位6桁(en−1,en−2,en−3,en−4,en−5,en−6τを、図3の変換テーブル36aに従って(gm−1,・・・,gn−6τに変換する。そして、τ−MLF計算部306は、τ−NAF表現の数値列の下位n−6桁(en−7,en−8,…,eτを無変換の状態で(gm−7,gm−8,…,gτに代入する。
ステップS305の結果、図3の行402のように桁の減少が可能な数値列は、桁数を減少することができる。
【0090】
ステップS304の結果、n≧6が成立しない場合(S304→No)、τ−MLF計算部306は、(en−1,en−2,…,eτを、無変換の状態で(gm−1,gm−2,…,gτに代入する無変換処理を行う(S306)。つまり、τ−MLF計算部306は、τ−NAF表現の数値列を、そのままτ−MLF表現の数値列とする。
ステップS305またはステップS306の後、エンコード部300は、τ−MLF表現の数値列(gm−1,gm−2,…,gτを出力する(S307)。
【0091】
(実計算処理)
図7は、第1実施形態に係る実計算処理(図4のステップS108)の流れを示すフローチャートである。なお、図5のステップS207の実計算処理も同様の処理手順である。
ここでは、エンコード部300により得られたτ−MLF表現の数値列としてエンコードされたスカラー値d=(gm−1,gm−2,…,gτと、Koblitz曲線上の定点Pとから、スカラー倍点dPを計算する。なお、図7に示す処理は公知の処理である。
まず、実計算部350は、τ−MLF表現の数値列としてエンコードされたスカラー値d=(gm−1,gm−2,…,gτと、記憶部3からKoblitz曲線上の定点Pの入力を受け付ける(S401)。
次に、加算部351は、Qに無限遠点Oを代入する(S402)。
そして、繰り返し判定部353は、iにm−1を代入し(S403)、i≧0であるか否かを判定する(S404)。
ステップS404の結果、i≧0でない場合(S404→No)、実計算部350は、Qを出力する(S405)。
【0092】
ステップS404の結果、i≧0である場合(S404→Yes)、τ倍算部352は、τ(Q)を計算し、計算の結果をQに代入する(S406)。ここで、Koblitz曲線上の定点QをQ=(x,y)と表すと、τ(Q)は式(8)の定義を満たす。
そして、数値判定部354が、g≠0であるか否かを判定する(S407)。
ステップS407の結果、g≠0である場合(S407→Yes)、加算部351は、Q+sign(g)Pを計算し、計算結果をQに代入する(S408)。ここで、「sign」は、非零整数xに対し、x>0のときsign(x)=1、x<0のときsign(x)=−1なる非零整数全体の集合から集合{±1}への写像である。
【0093】
ステップS407の結果、i≧0ではない場合(S407→No)、またはステップS408の結果、繰り返し判定部353は、iにi−1を代入し(S409)、ステップS404へ処理を戻す
【0094】
以上説明したように、エンコード部300から出力されるgは、式(18)を満たす。この理由は次の通りである。
まず、図6のステップS303で計算したτ−NAF表現の数値列(en−1,en−2,…,eτとdが等しい理由は非特許文献1に記載されている。τ−NAF表現の数値列とτ−MLF表現の数値列(gm−1,gm−2,…,gτが等しい理由は、ステップS205とステップS206のいずれの場合も(en−7,en−8,…,eτ=(gm−1,gm−2,…,gτが成り立つこと、および図3の変換テーブル36aの1列目の6桁τ−NAF表現と、対となっている2列目のτ−MLF表現が数値として等しいことによる。さらに、gが式(19)を満たす理由は式(18)を満たす理由と同様である。mが式(20)を満たす理由は、式(29)と図3の変換テーブル36aの3列目による。
【0095】
実計算部350が出力する点Qはスカラー倍点dPに等しい。この理由は次の通りである。実計算部350が出力する点Qは、以下の式(30)を満たし、dは式(22)を満たす。
【0096】
Q=dP ・・・ 式(30)
【0097】
また、Koblitz曲線上では、δPは無限遠点となることが知られている。従って実計算部350が出力する点Qは点dPに等しい。
エンコード部300が出力するτ−MLF表現の数値列は、その各桁gが式(18)を満たすτ進展開のうち、非零濃度が最小である。この理由も式(18)を満たす理由と同様である。
【0098】
以上よりτ−MLF表現の数値列は、その各桁が式(18)を満たすτ進展開のうち、非零濃度が最小であるといえる。
また、エンコード部300が出力するτ−MLF表現は、その各桁gが式(18)を満たす非零濃度が最小なτ進展開のうち、長さが最小である。この理由は、τ−MLF表現より短い長さを持つような式(18)を満たす非零濃度が最小なτ進展開が存在すると仮定することにより矛盾を導いて証明できる。
【0099】
第1実施形態では、スカラー値をτ−NAF表現の数値列(第1の符号列)に変換し、さらにτ−NAF表現の数値列をτ−MLF表現の数値列(第2の符号列)に変換した後、このτ−MLF表現の数値列を用いてスカラー倍点を計算する方法を説明したが、τ−MLF表現の数値列の計算に合わせてスカラー倍点を計算するon the fly法を用いてスカラー倍点を計算してもよい。
また、本実施形態では、暗号化コンピュータ1Aおよび復号化コンピュータ1Bにおいて、PC(Personal Computer)を想定しているが、これに限らず、少なくともどちらか一方が、スマートカードのような演算装置を有する可搬型小型記憶媒体でもよい。
【0100】
(第1実施形態の効果)
以上のように、第1実施形態のスカラー倍計算方法によれば、τ−NAF表現の数値列から、桁数の減少が可能な数値列に関して桁数を減少させτ−MLF表現の数値列をスカラー値の数値列として出力することができる。これにより、リソースが限られた環境で、安全性を低下させることなく、最小な加算回数と最小なフロベニウス写像の回数によって、高速計算可能が可能となる。。
すなわち、本実施形態によれば、Koblitz曲線が持つ高い安全性とリソース利用効率の良さを保ちつつ、高速性に優れたメッセージ処理が可能になる。
【0101】
《第2実施形態》
次に、図8および図9を参照して、本発明に係る第2実施形態について説明する。
第2実施形態において、第1実施形態と異なるのは変換テーブル36の構成およびエンコード処理であるため、ここではこれらの説明を記載し、それ以外の構成および処理は図示および説明を省略することとする。
なお、第2実施形態におけるスカラー倍計算部33は、図2のτ−NAF計算部301、τ−NAF長計算部302は備えていなくてもよい。
【0102】
第2実施形態では、スカラー倍計算部33がスカラー値dとKoblitz曲線上の定点Pから、Koblitz曲線におけるスカラー倍点dPを計算する第2の計算方法を説明する。
【0103】
詳細な説明を行う前に、ここで第2実施形態の概要を説明する。
第1実施形態では、スカラー値dから式(26)、式(27)、式(28)を満たすτ−NAF表現の数値列にエンコードした後、変換テーブル36a(図3)に従って、さらに、τ−NAF表現の数値列とは異なるτ−MLF表現の数値列にエンコードし、このτ−MLF表現の数値列を用いてスカラー倍点を計算した。これに対し、第2実施形態は、スカラー値dから式(26)、式(27)、式(28)を満たすτ−NAF表現の数値列を計算することなく、τ−MLF表現の数値列を直接計算し、このτ−MLF表現の数値列を用いてスカラー倍点を計算することを特徴とする。
そして、実計算部350が、このτ−MLF表現の数値列と、Koblitz曲線上の定点とを用いてスカラー倍計算を実行することにより高速化を実現する。以下、この計算方法を具体的に説明する。
【0104】
(変換テーブル)
図8は、第2実施形態に係る変換テーブルの構成例を示す図である。
変換テーブル36b(36)の1列目には、後記する図9のステップS402で算出され、ステップS505,S507,S509で更新されるτ進複素数表現r+rτの値が記載されている。ここで、r+rτ=±3、±4、±5は、r=±3、±4、±5、かつr=0を意味する。
2列目には、1列目の同一行に記載されているr+rτに対応するgに代入する値(第3の符号列)が記載されている。
そして、3列目には、1列目の同一行に記載されているr+rτに対応するhの計算方法が記載されている。hの意味については、図9において後記する。
そして、4列目と5列目には、1列目の同一行に記載されているr+rτに対応するrとrの更新値が記載されている。ここでは、すべて「0」に更新される。
【0105】
なお、hは2列目のgの個数を用いて計算することが可能なので、3列目を変換テーブル36bに記載しなくてもよい。また、変換テーブル36bに記載されているすべてのr+rτを記載する必要はなく、少なくとも一つ以上を変換テーブル36bに記載し、後記するステップS405では、変換テーブル36bに記載されているr+rτのみを、変換するようにしてもよい。
【0106】
(エンコード処理)
次に、図2および図8を参照しつつ、図9に沿って第2実施形態に係るエンコード処理の説明を行う。
図9は、第2実施形態に係るエンコード処理(図4のステップS107)の流れを示すフローチャートである。なお、図5のステップS206のエンコード処理も同様の処理手順である。
図9の処理では、スカラー値をτ−MLF表現の数値列にエンコードする処理を行う。
まず、エンコード部300は、スカラー値dの入力を受け付ける(S501)。
次に、δ剰余計算部304は、入力されたスカラー値dに対して、式(25)を満たす整数d=r+rτ=d mod δ(τ進複素数表現)を計算し、hに0を代入する(S502)。なお、hは現在計算している桁を示す変数である。
次に、条件判定部305はr≠0またはr≠0であるか否かを判定する(S503)。
【0107】
ステップS503の結果、r≠0またはr≠0である場合(S503→Yes)、条件判定部305は条件Z1が満たされているか否かを判定する(S504)。
ここで、条件Z1とは、r+rτ(τ進複素数表現)が図8の変換テーブル36bの1列目に登録されていることである。
すなわち、ステップS504において、条件判定部305は、ステップS502で計算されたτ進複素数表現が下記のいずれかであるか否かを判定する。
【0108】
【数2】

【0109】
ステップS504の結果、条件Z1を満たす場合(S504→Yes)、τ−MLF計算部306は変換テーブル36bから、該当するg(第3の符号列)h、、r、rを取得する(S505)。このとき、h、r、rの値は更新される。そして、エンコード部300はステップS503へ処理を戻す。
【0110】
ステップS504の結果、条件Z1を満たさない場合(S504→No)、条件判定部305はrが奇数であるか否かを判定する(S506)。
ステップS506の結果、rが奇数である場合(S506→Yes)τ−MLF計算部306はg(第4の符号列)に2−(r−2r mod 4)を代入し、rにr−gを代入して(S507)、ステップS509へ処理を進める。
ステップS506の結果、rが奇数ではない場合(S506→N0)、τ−MLF計算部306はg(第4の符号列)に0を代入して(S508)、ステップS509へ処理を進める。
ステップS507,S508の後、τ−MLF計算部306はtにrを、rにr+μr/2を、rにr−t/2を、hにh+1をそれぞれ代入し(S509)、エンコード部300はステップS503へ処理を戻す。
【0111】
ステップS503の結果、rおよびrが0であった場合(S503→No)、エンコード部300は、(gh−1,gh−2,…,gτをτ−MLF表現の数値列(第5の符号列)として出力する(S510)。
なお、図9の処理において、第1の方法であるステップS507およびステップSS509は、一般的に周知であるτ−NAFの演算処理である。
そして、実計算部350の行う処理は、図7と同様であるため、前記したように説明を省略する。
【0112】
以上説明したように、エンコード部300から出力されるτ−MLF表現の数値列におけるgは、式(18)を満たす。この理由は第1実施形態と同様である。
また、実計算部350が出力する点Qはスカラー倍点dPに等しい。この理由は第1実施形態と同様である。
そして、Koblitz曲線上では、δPは無限遠点となることが知られている。従って実計算部350が出力する点Qは点dPに等しい。
さらに、エンコード部300が出力するτ−MLF表現の数値列(第2の数値列)は、その各桁の数値gが式(18)を満たすτ進展開のうち、非零濃度が最小である。この理由は第1実施形態と同様である。
また、エンコード部300が出力するτ−MLF表現の数値列は、その各桁gが式(18)を満たす非零濃度が最小なτ進展開のうち、長さが最小である。この理由も第1実施形態と同様である。
【0113】
なお、第2実施形態でも、スカラー値dをτ−MLF表現の数値列に変換し、このτ−MLF表現を用いてスカラー倍点を計算するが、τ−MLF表現の計算に合わせてスカラー倍点を計算するon the fly法を用いてスカラー倍点を計算してもよい。
【0114】
(第2実施形態の効果)
以上のように、第2実施形態のスカラー倍計算方法によれば、第1実施形態と同様にリソースが限られた環境で、安全性を低下させることなく、最小な加算回数と最小なフロベニウス写像の回数によって、高速計算可能が可能となる。
すなわち、第2実施形態によれば、第1実施形態と同様に楕円曲線暗号が持つ高い安全性とリソース利用効率の良さを保ちつつ、高速性に優れたメッセージ処理が可能になる。
さらに、第2実施形態によれば、第1実施形態のように1度τ−NAF表現による数値列を算出することなく、直接τ−MLFを算出するため、第1実施形態より処理の高速化・低負荷化が可能である。
【0115】
《第3実施形態》
次に、図10〜図13を参照して、本発明に係る第3の実施形態について説明する。
第3実施形態において、第1実施形態と異なるのはスカラー倍計算部33の構成、変換テーブル36の構成およびエンコード処理であるため、ここではこれらの説明を記載し、それ以外の構成および処理は図示および説明を省略することとする。
【0116】
(スカラー倍計算部構成)
図10は、第3実施形態に係るスカラー倍計算部の構成例を示す図である。
図10のスカラー倍計算部33aのエンコード部300aにおいて、図2と異なる点は、τ−NAF計算部301、τ−NAF長計算部302が、桁対計算部311、長さ判定部312にそれぞれ置き換わっている点である。これらの機能については、処理の説明において後記する。
【0117】
第3実施形態では、スカラー倍計算部33Aが2進表現(em+2,em+1,…,e)とKoblitz曲線上の定点Pとから、Koblitz曲線におけるスカラー倍点dPを計算する第3の計算方法を説明する。
【0118】
詳細な説明を行う前に、ここで第3実施形態の概要を説明する。
第1実施形態および第2の実施形態では、スカラー値dからτ−MLF表現の数値列にエンコードし、このτ−MLF表現の数値列を用いてスカラー倍点を計算した。このとき、スカラー値dからd=d mod δを計算する手続きを必ず実施する(d mod δをδ剰余計算と呼ぶ)。このδ剰余計算は比較的重い処理である。
これに対し、入力された2進表現(em+2,em+1,…,e)(コンピュータにおいて、入力される数値はdのような数値ではなく、これを2進表現にした数値列が入力される)から、δ剰余計算を計算することなくτ−NAF表現d=(ym+1,y,…,yτを計算し、このτ−NAF表現d=(ym+1,y,…,yτを用いてスカラー倍点dPを計算する手法が非特許文献2に記載されている。
【0119】
非特許文献2では、比較的重い処理であるδ剰余計算を実施することなく、入力された2進表現(em+2,em+1,…,e)からτ−NAF表現の数値列を計算している。
第3の実施形態でも、比較的重い処理であるδ剰余計算を実施することなく、入力された2進表現(em+2,em+1,…,e)からτ−MLF表現の数値列d=(gm+1,g,…,gτを計算し、このτ−MLF表現の数値列d=(gm+1,g,…,gτを用いてスカラー倍点dPを計算する。ここで、同一の2進表現em+2m+1…eに対し、非特許文献2に記載の方法で計算したスカラー値d=(ym+1,y,…,yτと、第3実施形態の方法で計算したスカラー値d=(gm+1,g,…,gτにはdP=dPなる関係がある。
【0120】
第3実施形態では、このτ−MLF表現とこのKoblitz曲線上の定点とを用いてスカラー倍計算を実行することにより、第1実施形態および第2実施形態より高速な処理を実現することを目的とする。
【0121】
(変換テーブル)
図11は、第3実施形態に係る変換テーブルの構成例である。
変換テーブル36cの1列目には、入力された2値のビット列(e,ej−1,ej−2,ej−3,ej−4,ej−5,ej−6)(第6の符号列)の値が記載されている。2列目には、1列目の同一行に記載されている(e,ej−1,ej−2,ej−3,ej−4,ej−5,ej−6)に対応する数値列(g,gj−1,gj−2,gj−3,gj−4,gj−5)(第7の符号列)が記載されている。
先頭の「0」は、その桁における数値がないことを示す。例えば、符号501の2列目における(0,0,0、−1,−μ,1)は、実質的には3桁である。
ここで、1列目と2列目を比較すると、一部の行で2列目の数値列の桁数が減少していることが分かる(例えば、符号501)。これにより、数値列の桁数の減少が可能となる。
【0122】
なお、変換テーブル36cにおいてすべての(e,ej−1,ej−2,ej−3,ej−4,ej−5,ej−6)を記載する必要はなく、少なくとも一つ以上を変換テーブル36cに記載し、後記する図13のステップS619では、変換テーブル36cに記載されている(e,ej−1,ej−2,ej−3,ej−4,ej−5,ej−6)のみを、変換するようにしてもよい。
【0123】
(エンコード処理)
次に、図10および図11を参照しつつ、図12および図13に沿って第3実施形態に係るエンコード処理の説明を行う。
図12および図13は、第3実施形態に係るエンコード処理(図4のステップS107)の流れを示すフローチャートである。なお、図5のステップS206のエンコード処理も同様の処理手順である。
図12および図13では、スカラー値を数値列(τ−MLF)にエンコードする処理を行う。
まず、エンコード部300aは、m+3ビットのビット列である2進表現(em+2,em+1,…,e)の入力を受ける(S601)。ここで入力される(em+2,m+1,…,e)は図6のステップS301や、図9のステップS501で入力されるdを2進表現したビット列である。
桁対計算部311は、em+3に0を代入し、長さ判定部312は、受け取った2進表現(em+2,em+1,…,e)に対して、e≠0なる最大のkを計算する(S602)。ここで、kはビット列の桁数となる。これは、例えば(0,0,1,0,1)のようなビット列が入力されるのを想定しているためであり、このビット列例のkは3となる。
【0124】
次に、条件判定部305は、iに0を代入する(S603)。iは、現在処理していているビット列の桁数となる。
そして、条件判定部305はkが6以上であるか否かを判定する(S604)。
ステップS604の結果、kが6以上でない場合(S604→No)、エンコード部300aは図13のステップS612へ処理を進める。ステップS612以降の処理は後記して説明する。
ステップS604の結果、kが6以上である場合(S604→Yes)、条件判定部305は、iがk−6以下であるか否かを判定する(S605)。
ステップS605の結果、iがk−6以下でない場合(S605→No)、エンコード部300aは図13はステップS612へ処理を進める。ステップS612以降の処理は後記して説明する。
【0125】
ステップS605の結果、iがk−6以下である場合(S605→Yes)、条件判定部305は、eが1であるか否かを判定する(S606)。
ステップS606の結果、eが1でない場合(S606→No)、τ−MLF計算部306はg(第8の符号列)に0を代入し、iにi+1を代入した(S607)後、エンコード部300aはステップS605へ処理を戻す。
ステップS606の結果、eが1である場合(S606→Yes)、条件判定部305は、ei+1が1であるか否かを判定する(S608)。
ステップS608の結果、ei+1が1である場合(S608→Yes)τ−MLF計算部306は、gi+1(第8の符号列)に0を代入し、g(第8の符号列)に−1を代入した(S609)後、エンコード部300aはステップS611へ処理を進める。
ステップS608の結果、ei+1が1でない場合(S608→No)、τ−MLF計算部306は、gi+1(第8の符号列)に0を代入し、g(第8の符号列)に1を代入した(S610)後、エンコード部300aはステップS611へ処理を進める。
ステップS609,S610の処理後、条件判定部305は、iにi+2を代入し(S611)、エンコード部300aはステップS605へ処理を戻す。
なお、本処理のステップS606〜S611が第3の方法である。また、ステップS606〜S611の処理は非特許文献2に記載の処理方法である。
【0126】
ステップS604の結果、kが6以上ではない場合(S604→No)、またはステップS605の結果、iがk−6以下ではない場合(S605→No)、条件判定部305は、xに(a−1) mod 2を代入する(図13のS612)。ここで、aは式(12)の定数であり、a=0またはa=1である。また、a=0のときx=(a−1) mod 2=−1 mod 2=1、a=1のときx=(a−1) mod 2=0 mod 2 =0となるので、x=0またはx=1である。
次に、条件判定部305は、iがk−6であるか否かを判定する(S613)。
ステップS613の結果、iがk−6である場合(S613→Yes)、条件判定部305は、jにkを代入し(S614)、エンコード部300aはステップS618へ処理を進める。
ステップS613の結果、iがk−6ではない場合(S613→No)、条件判定部305は、iがk−5であるか否かを判定する(S615)。
ステップS615の結果、iがk−5である場合(S615→Yes)、条件判定部305は、ek+1に0を代入し、jにk+1を代入し(S616)、エンコード部300aはステップS618へ処理を進める。
ステップS615の結果、iがk−5でない場合(S615→No)、条件判定部305は、jに6を代入し(S617)、エンコード部300aは図13のステップS618へ処理を進める。
【0127】
ステップS614、S616,S617の処理後、条件判定部305は、条件Z2が満たされるか否かを判定する(S618)。ここで、条件Z2は、(e,ej−1,…,ej−5)において、第2の方法である所定の方法で符号が変換された数値列(第9の符号列)が、図11の変換テーブル36cの1列目に登録されている数値列のいずれか1つと一致することである。ここで、所定の方法(第2の方法)とは、変換テーブル36cの1列目におけるa,xの位置に従って、(e,ej−1,…,ej−5)の符号を置き換えるものである。
ステップS618の結果、条件Z2が満たされない場合(S618→No)、すなわち、第2の方法で変換された(e,ej−1,…,ej−5)が、図11の変換テーブル36cの1列目に登録されている(e,ej−1,…,ej−5)のいずれとも一致しない場合、エンコード部300aはステップS623へ処理を進める。ステップS623以降の処理は後記して説明する。
【0128】
ステップS618の結果、条件Z2を満たす場合(S618→Yes)、すなわち、第2の方法で変換された(e,ej−1,…,ej−5)が、図11の変換テーブル36cの1列目に登録されている(e,ej−1,…,ej−5)のいずれか一つと一致する場合、τ−MLF計算部306は図11の変換テーブル36cから、(e,ej−1,…,ej−5)に対応する(g,・・・,gj−5τを取得する(S619)。
そして、条件判定部305はiにj+1を代入し(S620)、iがm+3以下ならば、τ−MLF計算部306は、gm+3,gm+2,…,gにそれぞれ0を代入する(S621)。
そして、エンコード部300aは、d=(gm+1,g,…,gτ(第10の符号列)をτ−MLF表現の数値列として出力する(S622)。
【0129】
一方、ステップS618の結果、条件Z2が満たされない場合(S618→No)、条件判定部305は、iがk以下であるか否かを判定する(S623)。
ステップS623の結果、iがk以下ではない場合(S623→No)、エンコード部300aはステップS621へ処理を進める。ステップS621以降の処理は前記したため、ここでの説明は省略する。
ステップS623の結果、iがk以下である場合(S623→Yes)、条件判定部305は、eが1であるか否かを判定する(S624)。
ステップS624の結果、eが1でない場合(S624→No)、τ−MLF計算部306は、g(第8の符号列)に0を代入し、条件判定部305はiにi+1を代入し(S625)、エンコード部300aはステップS623へ処理を戻す。
【0130】
ステップS624の結果、eが1である場合(S624→Yes)、条件判定部305は、ei+1が1であるか否かを判定する(S626)。
ステップS626の結果、ei+1が1である場合(S626→Yes)、τ−MLF計算部306は、gi+1(第8の符号列)に0を代入し、g(第8の符号列)に−1を代入し(S627)、エンコード部300aはステップS629へ処理を進める。
ステップS626の結果、ei+1が1でない場合(S626→No)、τ−MLF計算部306は、gi+1(第8の符号列)に0を代入し、g(第8の符号列)に1を代入し(S628)、エンコード部300aはステップS629へ処理を進める。
ステップS627、S628の処理後、条件判定部305は、iにi+2を代入し(S629)、エンコード部300aはステップS623へ処理を戻す。
なお、本処理におけるステップS623〜S629は第4の方法である。また、ステップS623〜S629の処理は非特許文献2に記載の処理方法である。
なお、ステップS601〜S611およびステップS621〜S629の処理は、特許文献1に記載の処理と同様の処理である。
以降、実計算部350が図7と同様の処理を行い、スカラー倍点を計算する。
【0131】
以上説明したように、ステップS601で入力される2進表現(em+2m+1…e)に対し、エンコード部300aから出力される(gm+1,g,…,gτと非特許文献2に記載の方法で計算したスカラー値(ym+1,y,…,yτは、(gm+1,g,…,gτ=(ym+1,y,…,yτを満たす。この理由は明らかである。
そして、実計算部350が出力する点Qはスカラー倍点dPに等しい。この理由は第1実施形態、および第2の実施形態と同様である。
【0132】
(第3実施形態の効果)
以上のように、第3実施形態のスカラー倍計算方法によれば、リソースが限られた環境で、安全性を低下させることなく、最小な加算回数と最小なフロベニウス写像の回数によって、高速計算可能が可能となる。
すなわち、第3実施形態によれば、Koblitz曲線が持つ高い安全性とリソース利用効率の良さを保ちつつ、高速性に優れたメッセージ処理が可能になる。
さらに、第3実施形態によれば、比較的重い処理であるδ剰余計算を実施することなく、入力された2進表現(em+2,em+1,…,e)からτ−MLF表現の数値列を計算しているため、第1実施形態および第2実施形態より、処理の高速化・低負荷化が可能である。 なお、δ剰余計算を実施することなく、入力された2進表現(em+2,em+1,…,e)からτ−NAF表現の数値列を計算している非特許文献2の技術とは異なり、τ−MLF表現の数値列を計算するため、非特許文献2の技術よりも、リソースが限られた環境で、安全性を低下させることなく、最小な加算回数と最小なフロベニウス写像の回数によって、高速計算可能が可能な数値列を出力することができる。。
【0133】
《第4実施形態:署名検証システム》
次に、図14〜図16を参照して第1実施形態〜第3実施形態を適用した署名検証システムBを第4実施形態として説明する。
【0134】
(署名検証システムの構成図)
図14は、第4実施形態に係る署名検証システムのシステム構成図である。
署名検証システムBは、スマートカード(署名生成装置、可搬型小型記憶媒体)1Cと署名検証処理を行うコンピュータ(署名検証装置)1Dとを有する。
スマートカード1Cは、第1実施形態〜第3の実施形態の図1の暗号化コンピュータ101と類似の構成を備える。すなわち、スマートカード1Cにおける符号2C,4C,21C,22C,31C,33C,34C,36C〜38Cは、それぞれ図1における符号2A,4A,21A,22A,31A,33A,34A,36A〜38Aと同様の構成要素である。
ここで、スマートカード1Cと、図1の暗号化コンピュータ1Aとの差異は以下の通りである。まず、図1におけるデータ処理部32Aが署名生成処理部32Cに置き換わっている。また、図1における外部記憶装置35A、ディスプレイ5A、キーボード6Bを備えていない。
そして、変換テーブル36C(36)、秘密情報37Cおよび定数38Cが、ROM34Cに格納されている。
【0135】
一方、コンピュータ1Dは、復号化コンピュータ1Bと同様の構成を備える。すなわち、コンピュータ1Dにおける2D〜6D,21D,22D,31D,33D〜38Dは、図1の復号化コンピュータ1Bにおける2B〜6B,21B,22B,31B,33B〜38Bと同様の構成要素である。
コンピュータ1Dと、図1の暗号化コンピュータ1Bとの差異は、データ処理部32Bの代わりに署名検証処理部32Dを有している点である。
【0136】
なお、署名生成処理部32Cおよび署名検証処理部32Dは、ROM34Cや、外部記憶装置35Dや、図示しないフラッシュメモリなどに格納されたプログラムが、RAM31C,31Dに展開され、CPU21C,21Dによって実行されることによって具現化する。
また、スカラー倍計算部33C,33Dは、図2または図10に示す構成を有しているため、図示および説明を省略する。
なお、定数38Cおよび定数38Dには、共通のKoblitz曲線上の定点Qが格納されている。
【0137】
第4実施形態においても、前記した実施形態同様、コンピュータ1D内の各プログラムは、予め、コンピュータ1D内のROM34Dや外部記憶装置35Dに格納されていてもよいし、必要なときに、コンピュータ1Dが利用可能な媒体を介して、他の装置からROM34Dや外部記憶装置35Dに格納してもよい。
さらに、スマートカード1C内の各プログラムは、予め、スマートカード1C内のROM34Cに格納されていてもよいし、必要なときに、入出力インタフェース4Cを介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して、RAM31Cに展開されてもよい。ここで、媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体(すなわちネットワークまたはネットワークを伝搬する搬送波)を指す。
【0138】
次に、第4実施形態の署名検証システムBにおける署名生成処理と署名検証処理を、図14を参照しつつ、図15および図16に沿って説明する。
離散対数問題に基づくディジタル署名方法を楕円曲線上の離散対数問題に基づく方法に対応させて構成する楕円曲線ディジタル署名アルゴリズム(ECDSA:Elliptic Curve Digital Signature Algorithm)という署名方法がある。ECDSA署名については、例えば、D. Johnson, A. Menezes, The Elliptic Curve Digital Signature Algorithm (ECDSA), Technical Report CORR 99-34, Department of Combinatorics and Optimization, University of Waterloo, Canada.(http://www.cacr.math.uwaterloo.ca/techreports/1999/corr99-34.pdf)に記載されている。
【0139】
(情報の送受信)
まず、図15を参照して、第4実施形態に係る署名生成処理を説明する。
図15および図16は、第4実施形態に係るメッセージの署名生成処理および署名検証処理を行う場合におけるスマートカード1Cおよびコンピュータ1D内の情報の送受信について説明するタイミングチャートである。
まず、コンピュータ1Dは、ランダムに選んだ数値をチャレンジコードとして、インタフェース4Cを介してスマートカード1Cに転送する。
そして、スマートカード1Cの署名生成処理部32Cは、チャレンジコードを入力メッセージとして受け付け(S701)、チャレンジコードのハッシュ値をとり、所定のビット長の数値fに変換する。
そして、署名生成処理部32Cは、乱数uを生成し(S702)、記憶部3C(具体的にはROM34C)に格納されている秘密情報37Cから秘密鍵dを読み出し、定数38CからKoblitz曲線上の定点Qを読み出す(S703)。生成した乱数u(スカラー値)を読み出したKoblitz曲線上の定点Qとともにスカラー倍計算部33Cへ送る(S704)。
スカラー倍計算部33Cのエンコード部300(図2)あるいはエンコード部300a(図10)は、第1実施形態〜第3実施形態のうちいずれかのエンコード処理を行うことによって(S705)、乱数uのτ−MLF表現の数値列を計算する。
そして、実計算部350は、乱数uのτ−MLF表現の数値列を使用して、定点Qのスカラー倍点uQ=(x,y)を計算する実計算処理(図7)を行う(S706)。
そして、スカラー倍計算部33Cは、計算されたスカラー倍点を署名生成処理部32Cへ送る(S707)。
署名生成処理部32Cは、送られたスカラー倍点を用いて署名生成処理を行う(S708)。例えば、前記したECDSA署名であれば、署名生成処理部32Cは、以下の式(31),(32)を計算することにより、チャレンジコードに対応する署名(s,t)を得る。
【0140】
s=x mod q ・・・式(31)
t=u−1(f+ds) mod q ・・・式(32)
【0141】
ここで、qは定点Qの位数、すなわち、定点Qのq倍点qQが無限遠点になり、qより小さな数値mに対する定点Qのm倍点mQは無限遠点にはならない、という数値のことである。
署名生成処理部32Cは、生成した署名を出力メッセージとして入出力インタフェース4Cを介して出力し(S709)、インタフェース4Dを介してコンピュータ1Dへ転送する。
【0142】
次に、図16を参照してコンピュータ1Dにおける署名検証処理を説明する。
コンピュータ1Dの署名検証処理部32Dは、スマートカード1Cから署名が入力メッセージとして入力されると(S801)、署名の数値s,tが適切な範囲内すなわち1≦s,t<qであるかを調べる署名範囲検証処理を行う(S802)。
数値s,tがこの範囲内になければチャレンジコードに対する署名の検証結果として「無効」を出力し、スマートカード1Cを拒絶する(図示せず)。
【0143】
一方、数値s,tがこの範囲内にあれば、署名検証処理部32Dは、以下の式(33)〜(35)を計算する。
【0144】
h=t−1 mod q ・・・ 式(33)
=fh mod q ・・・ 式(34)
=sh mod q ・・・ 式(35)
【0145】
署名検証処理部32Dは、記憶部3D(具体的には外部記憶装置35D)に格納されている定数38Dから公開鍵dQおよびKoblitz曲線上の定点Qを読み出す(S803)。なお、公開鍵dQは、スカラー倍計算部33Dによって第1実施形態〜第3実施形態のいずれかの方法で予め計算され、記憶部3Dに格納されている。そして、読み出した公開鍵dQおよび定点Q(いずれもKoblitz曲線上の定点)と、計算したh,h(スカラー値)とを、スカラー倍計算部33Dへ送る(S804)。
スカラー倍計算部33Dのエンコード部300(図2)またはエンコード部300a(図10)は、第1実施形態〜第3実施形態のうち、いずれかのエンコード処理を行う(S805)ことによって、hおよびhのτ−MLF表現の数値列を計算する。
そして、実計算部350(図2)が、定点Qとhとによるスカラー倍点hQと、公開鍵dQとhとによるスカラー倍点hdQとを計算する実計算処理(図7)を行う(S806)。
そして、スカラー倍計算部33Dは、出力された定点Qとhとによるスカラー倍点hQと、公開鍵dQとhとによるスカラー倍点hdQとを署名検証処理部32Dへ送る(S807)。
【0146】
署名検証処理部32Dは、送られたスカラー倍点を用いて署名検証処理を行う(S808)。
例えば、ECDSAの署名検証であれば、署名検証処理部32Dは、点Rを以下の式(36)により計算する。
【0147】
R=hQ+hdQ ・・・ 式(36)
【0148】
そして、そのx座標をxとしたとき、署名検証処理部32Dは、以下の式(37)を計算する。
【0149】
=x mod q ・・・ 式(37)
【0150】
=sであれば、署名検証処理部32Dは、チャレンジコード1142に対する署名の検証結果(出力メッセージ)として「有効」をディスプレイ5Dに出力し(S809)、スマートカード1Cを認証する。
一方、s=sでなければ、署名検証処理部32Dは、チャレンジコード1142に対する署名の検証結果(出力メッセージ)として「無効」をディスプレイ5Dに出力し(S809)、スマートカード1Cを拒絶する。
【0151】
(第4実施形態の効果)
このように、第4実施形態では署名生成処理および署名検証処理において、スカラー倍点を計算する。従って、署名生成および署名検証におけるスカラー倍計算を行う際に、第1実施形態、第2実施形態または第3実施形態のスカラー倍計算方法を用いることが可能である。これらの実施形態のスカラー倍計算方法を用いることにより、スマートカード1Cといったリソースが限られた環境においても、高い安全性と高速な処理とを実現することができる。
【0152】
なお、第4実施形態では、スマートカード1Cを用いたが、演算装置を有している可搬型小型記憶媒体であればよく、例えば演算装置を有しているUSB(Universal Serial Bus)メモリなどを用いてもよい。また、例えばRFID(Radio Frequency Identification)に秘密情報37Cと、定数38Cを格納しておき、ライタが署名生成処理部32C、スカラー倍計算部33C、変換テーブル36Cを有し、ライタが署名の生成を行ってもよい。
【0153】
なお、本実施形態では、署名生成をスマートカード1Cが行い、署名検証をコンピュータ1Dが行ったが、これに限らず、署名生成をコンピュータが行い、署名検証をスマートカードが行ってもよいし、署名生成・署名検証の双方をコンピュータが行ってもよい。
【0154】
《第5実施形態:鍵交換システム》
次に、本発明をKoblitz曲線を用いた楕円Diffie−Hellman鍵共有スキームに適用して実現する鍵交換システムCを第5実施形態として説明する。
図17は、第5実施形態に係る鍵交換システムの構成例を示す図である。
本実施形態の鍵交換システムCのシステム構成は、図1と同様である。ただし、図1のデータ処理部32A,32Bは、本実施形態においては、それぞれコンピュータ1E,1Fの鍵交換処理部32E,32Fとして機能する。
図17の符号2E〜6E,21E,22E,31E,33E〜38Eは、図1の符号2A〜6A,21A,22A,31A,33A〜38Aと同様の構成要素である。
また、図17の符号2F〜6F,21F,22F,31F,33F〜38Fは、図1の符号2B〜6B,21B,22B,31B,33B〜38Bと同様の構成要素である。
なお、定数38Eおよび定数38Fには、共通のKoblitz曲線上の定点Qが格納されている。
【0155】
鍵交換処理部32E,32Fは、外部記憶装置35E,35Fや、ROM34E,34Fや、図示しないフラッシュメモリなどに格納されているプログラムがRAM31E,31Fに展開され、CPU21E、21Fやコプロセッサ22E,22Fなどの演算装置によって実行されている。
【0156】
(情報の送受信)
次に、第5実施形態の鍵交換システムCのコンピュータ1Eおよびコンピュータ1Fが、入力されたデータから共有情報の導出を行う場合の動作について図17を参照しつつ、図18に沿って説明する。
図18は、第5実施形態に係る鍵交換処理を行う場合におけるコンピュータ1Eおよびコンピュータ1F内の情報の送受信について説明するタイミングチャートである。
【0157】
コンピュータ1Eの鍵交換処理部32Eは、コンピュータ1Fが出力した公開鍵bQのデータを入力メッセージとして受け付ける(S901)。ここで、公開鍵bQはKoblitz曲線上の定点である。
そして、鍵交換処理部32Eは、記憶部3E(具体的には、外部記憶装置35E)の秘密情報37Eからコンピュータ1Eの秘密鍵dを読み出し(S902)、秘密鍵d(スカラー値)とコンピュータ1Fが出力した公開鍵bQ(Koblitz曲線上の定点)とをスカラー倍計算部33Eへ送る(S903)。
【0158】
スカラー倍計算部33Eのエンコード部300(図2)またはエンコード部300a(図10)は、第1実施形態〜第3実施形態のうち、いずれかのエンコード処理を行う(S904)ことによって、秘密鍵dのτ−MLF表現の数値列を計算する。
そして、実計算部350(図2)が、秘密鍵dのτ−MLF表現の数値列を用いて、公開鍵bQによるスカラー倍点dbQを計算する実計算処理(図7)を行う(S905)。
そして、スカラー倍計算部33Eは、計算したスカラー倍点dbQと秘密鍵dとを鍵交換処理部32Eへ送る(S906)。
鍵交換処理部32Eは、送られたスカラー倍点dbQを用いて共有情報の導出を行い(S907)、記憶部3E(具体的には外部記憶装置35E)に秘密情報37Eとして格納する(S908)。ステップS907において、鍵交換処理部32Eは、例えば、スカラー倍点dbQのx座標を共有情報とする。
【0159】
コンピュータ1Eの鍵交換処理部32Eおよびスカラー倍計算部33Eは、記憶部3Eの秘密情報37Eから秘密鍵dを読み出し(S909)、定数37EからKoblitz曲線上の定点Qを読み出し、コンピュータ1Eの公開鍵dQを計算する(S910)。具体的には、鍵交換処理部32Eは、スカラー値としての秘密鍵dと、Koblitz曲線上の定点Qをスカラー倍計算部33Eへ送り、スカラー倍計算部33Eは第1実施形態〜第3実施形態のいずれかの方法でスカラー倍点dQを計算する。そして、スカラー倍計算部33Eは、計算したスカラー倍点dQを鍵交換処理部32Eへ送る。
【0160】
そして、鍵交換処理部32Eは、ネットワーク6を介して、計算した公開鍵dQを出力メッセージとしてコンピュータ1Fに転送する(S911)。
【0161】
次に、コンピュータ1Fが、入力されたデータから共有情報の導出を行う場合の動作について同じく図18を参照して説明する。
コンピュータ1Fの鍵交換処理部32Fは、コンピュータ1Eの公開鍵dQを、入力メッセージとして受け付ける(S901)。
そして、鍵交換処理部32Fは、記憶部3F(具体的には外部記憶装置35F)の秘密情報37Fからコンピュータ1Fの秘密鍵bを読み出し(S902)、読み出した秘密鍵b(スカラー値)とコンピュータ1Eから受信した公開鍵dQ(Koblitz曲線上の定点)とをスカラー倍計算部33Fへ送る(S903)。
【0162】
スカラー倍計算部33Fのエンコード部300(図2)またはエンコード部300a(図10)は、第1実施形態〜第3実施形態のうち、いずれかのエンコード処理を行う(S904)ことにより、秘密鍵bのτ−MLF表現の数値列を計算する。
そして、実計算部350(図2)が、秘密鍵bのτ−MLF表現の数値列を用いて公開鍵dQによるスカラー倍点bdQを計算する実計算処理(図7)を行う(S905)。
そして、スカラー倍計算部33Fは、計算されたスカラー倍点bdQと秘密鍵bとを鍵交換処理部32Fへ送る(S906)。
鍵交換処理部32Fは、送られたスカラー倍点を用いて共有情報の導出を行い(S907)、記憶部3F(具体的には外部記憶装置35F)に秘密情報37Fとして格納する(S908)ステップS907において、鍵交換処理部32Fは、例えば、スカラー倍点bdQのx座標を共有情報とする。
コンピュータ1Fの鍵交換処理部32Fおよびスカラー倍計算部33Fは、記憶部3Fの秘密情報37Fから秘密鍵bを読み出し、定数38FからKoblitz曲線上の定点Qを読み出し、コンピュータ1Fの公開鍵bQを計算する(S909)。
具体的には、鍵交換処理部32Fは、スカラー値としての秘密鍵bと、Koblitz曲線上の定点Qをスカラー倍計算部33Fへ送り、スカラー倍計算部33Fは第1実施形態〜第3実施形態のいずれかの方法でスカラー倍点bQを計算する。そして、スカラー倍計算部33Fは、計算したスカラー倍点bQを鍵交換処理部32Fへ送る。
【0163】
そして、鍵交換処理部32Fは、ネットワーク6を介して、公開鍵bQを出力メッセージとしてコンピュータ1Eに転送する(S909)。
【0164】
例えば、スカラー倍点bdQのx座標を共有情報とする。ここで、数dbと数bdとは数値として同じなので、点dbQと点bdQとは同じ点となり、同じ情報が導出されたことになる。
【0165】
ネットワーク6には、Koblitz曲線上の定点dQと点bQが送信される。しかし、点dbQ(もしくは点bdQ)を計算するためには、秘密鍵dもしくは秘密鍵bが必要である。すなわち、秘密鍵dもしくは秘密鍵bを知らなければ、共有情報を得ることはできない。従って、これらの方法で得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
【0166】
なお、第5実施形態ではコンピュータ1E,1FとしてPCを想定しているが、これに限らず、どちらか一方がスマートカードのような演算装置を有する可搬型小型記憶媒体でもよい。
【0167】
(第5実施形態の効果)
第5実施形態の鍵交換システムCでは、受け取った点のスカラー倍点を計算する。従って、鍵交換を行う際に、第1実施形態〜第3実施形態のうちのいずれかのスカラー倍計算方法を用いることが可能である。これらの実施形態のスカラー倍計算方法を用いることにより、高い安全性と高速な処理とを実現することができる。
【0168】
なお、前記した各実施形態では、データ処理部32A,32B、署名生成処理部32C、署名検証処理部32D、鍵交換処理部32E,32Fを、ソフトウェアで実現するものとして説明したが、専用のハードウェアを用いて実現してもよい。また、スカラー倍計算部33A〜33Fをコプロセッサ22A〜22Fまたはそれ以外の専用ハードウェアで実現してもよい。また、1台のコンピュータが、データ処理部32A,32B、署名生成処理部32C、署名検証処理部32D、鍵交換処理部32E,32Fのうち、任意の一つ以上の処理を行うことができるよう構成してもよい。
【符号の説明】
【0169】
1A 暗号化コンピュータ(スカラー倍計算装置,暗号化装置)
1B 復号化コンピュータ(スカラー倍計算装置,復号化装置)
1C スマートカード(署名生成装置、可搬型小型記憶媒体)
1D コンピュータ(署名検証装置)
1E,1F コンピュータ(鍵交換装置)
2A〜2F 処理部
3A〜3F 記憶部
4A〜4F 入出力インタフェース(入力部)
5A,5B,5D〜5F ディスプレイ
6A,6B,6D〜6F キーボード
21A〜21F CPU
22A〜22F コプロセッサ
31A〜31F RAM
32A,32B データ処理部
32C 署名生成処理部
32D 署名検証処理部
32E,32F 鍵交換処理部
33,33A,33A〜33F スカラー倍計算部
34A〜34F ROM
35A,35B,35D〜35F 外部記憶装置
36,36A〜36F,36a〜36c 変換テーブル(変換情報)
37,37A〜37F 秘密情報
38A〜38F 定数
300,300a エンコード部
301 τ−NAF計算部
302 τ−NAF長計算部
303 格納部
304 δ剰余計算部
305 条件判定部
306 τ−MLF計算部
311 桁対計算部
312 長さ判定部
350 実計算部
351 加算部
352 τ倍算部
353 繰り返し判定部
354 数値判定部
A 暗号通信システム
B 署名検証システム
C 鍵交換システム

【特許請求の範囲】
【請求項1】
入力部を介して入力されたKoblitz曲線上の点の座標およびスカラー値を基に、前記Koblitz曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置であって、
τ−NAF変換された第1の符号列と、第1の符号列より短い符号長を有し、かつτ−NAF表現において前記第1の符号列と同一の値を有する第2の符号列と、を有している変換情報を格納している記憶部と、
情報を処理する処理部と、を有し、
前記処理部が、
入力された前記スカラー値を前記第1の符号列に変換し、
前記変換情報を基に、前記第1の符号列に対応する第2の符号列を取得し、
前記取得した第2の符号列を前記スカラー値の符号列として出力し、
前記出力された第2の符号列と、前記入力されたKoblitz曲線上の点の座標と、を基に、前記Koblitz曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算装置。
【請求項2】
前記第1の符号列のうち、変換対象の符号列は、符号列の内、上位6桁の符号列である
ことを特徴とする請求項1に記載のスカラー倍計算装置。
【請求項3】
前記第1の符号列と、前記第2の符号列の対応は、以下の関係である
ことを特徴とする請求項2に記載のスカラー倍計算装置。
【数3】


なお、前記関係において、左側の各符号列が前記第1の符号列であり、右側の各符号列が前記第2の符号列であり、μ=(−1)1−a(aは前記Koblitz曲線の係数)であり、前記した第1の符号列以外の符号列は、変換されずに前記第2の符号列となる。
【請求項4】
入力部を介して入力されたKoblitz曲線上の点の座標およびスカラー値を基に、前記Koblitz曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置であって、
所定の符号列をτ進複素数表現した値と、前記τ進複素数表現に対応している第3の符号列と、を有している変換情報を格納している記憶部と、
情報を処理する処理部と、を有し、
前記処理部が、
(a1)前記入力されたスカラー値を前記τ進複素数表現にした値へ変換し、
(a2)前記変換されたτ進複素数表現が、前記変換情報に格納されていない場合、第4の符号列にτ−NAF変換した符号を1つ追加し、
(a3)前記τ進複素数表現の実部および虚部の値を予め設定されている第1の方法に従って更新し、
(a4)前記変換されたτ進複素数表現が、前記変換情報に格納されている場合、前記変換情報から、前記τ進複素数表現に対応する前記第3の符号列を取得し、前記前記τ進複素数表現の実部および虚部の値に、0を代入し
(a5)前記更新された前記τ進複素数表現の実部および虚部の値が、共に0となるまで、前記(a2)〜(a4)の処理を繰り返し、
(a6)前記τ進複素数表現の実部および虚部の値が、共に0となった場合、前記第4の符号列の上位の桁に、前記第3の符号列を追加した第5の符号列を、前記スカラー値の符号列として出力し、
前記出力された第5の符号列と、前記入力されたKoblitz曲線上の点の座標と、を基に、前記Koblitz曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算装置。
【請求項5】
前記τ進複素数表現の値と、前記第3の符号列の関係は、以下の関係である
ことを特徴とする請求項4に記載のスカラー倍計算装置。
【数4】


なお、当該関係において、左側の各式が前記τ進複素数表現の値であり、右側の各符号列が前記第3の符号列であり、μ=(−1)1−a(aは前記Koblitz曲線の係数)である。
【請求項6】
入力部を介して入力されたKoblitz曲線上の点の座標およびスカラー値を基に、前記Koblitz曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置であって、
前記入力部を介して入力された前記スカラー値を2進表現でビット列を、予め設定されている第2の方法で変換した第6の符号列と、前記第6の符号列に対応している第7の符号列と、を有している変換情報を格納している記憶部と、
情報を処理する処理部と、を有し、
前記処理部が、
(b1)前記スカラー値が2進表現のビット列として入力され、
(b2)前記ビット列の最大桁数が6桁以上であり、かつ現在計算している桁が上位6桁以外である場合、予め設定されている第3の方法に従って(1,0、−1)の3値のうちのいずれかの符号を生成し、当該生成した符号を第8の符号列に追加し、現在計算している桁が上位6桁以内となるまで、前記(b2)の処理を繰り返し、
(b3)前記ビット列の最大桁数が6桁未満である、または現在計算している桁が上位6桁以内である場合、前記ビット列のうち、現在している桁以下7桁の符号列を、前記第2の方法で変換した第9の符号列が、前記変換情報に格納されている第6の符号列のいずれかと一致するか否かを判定し、
(b4)前記判定の結果、前記第9の符号列が、前記変換情報に格納されている第6の符号列のうちのいずれとも一致しない場合、予め設定されている第4の方法に従って(1,0、−1)の3値のうちのいずれかの符号を生成し、当該生成した符号を第8の符号列に追加し、現在計算している桁が前記ビット列の最大桁数より大きくなるまで、前記(b4)の処理を繰り返し、
(b5)前記判定の結果、前記第9の符号列が、前記変換情報に格納されている第6の符号列のいずれかと一致する場合、前記変換情報から、前記第9の符号列に対応する前記第7の符号列を取得し、前記第8の符号列の上位の桁に前記第7の符号列を追加した第10の符号列を、前記スカラー値の符号列として出力し、
前記出力された第10の符号列と、前記入力されたKoblitz曲線上の点の座標と、を基に、前記Koblitz曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算装置。
【請求項7】
前記処理部は、
前記第6の符号列と、前記第7の符号列の関係は、以下の関係であることを特徴とする請求項6に記載のスカラー倍計算装置。
(x、1,0,0,1,0,0)→(0,0,−μ,−1,0,0)τ
(a,1,0,1,1,0,0)→(0,0,μ,1,0,0)τ
(x、1,0,0,1,0,1)→(0,0,−μ,−1,0,1)τ
(a,1,0,1,1,1,1)→(0,0,μ,1,0,−1)τ
(x,1,0,0,1,1,1)→(0,0,0,−1,μ,1)τ
(a,1,0,1,1,0,1)→(0,0,0,1,−μ,−1)τ
(x,1,x、1,0,0,0)→(0,1,−μ,0,0,0)τ
(a,1,a,1,0,0,0)→(0,−1,μ,0,0,0)τ
(x,1,x,1,0,0,1)→(0,1,−μ,0,0,1)τ
(a,1,a,1,0,1,1)→(0,−1,μ,0,0,−1)τ
(x,1,x,1,0,1,1)→(0,0,0,−1,μ,1)τ
(a,1,a,1,0,0,1)→(0,0,0,1,μ,−1)τ
(x,1,x,1,x,1,0)→(0,1,−μ,0,μ,0)τ
(a,1,a,1,a,1,0)→(0,−1,μ,0,−μ,0)τ
(x,1,x,1,a,1,0)→(0,1,−μ,0,−μ,0)τ
(a,1,a,1,x,1,0)→(0,−1,μ,0,μ,0)τ
ただし、当該関係において、左側の各符号列が前記第6の符号列であり、右側の各符号列が前記第7の符号列であり、aはKoblitz曲線の係数であり、xはx=(a−1)mod2であり、μ=(−1)1−a(aは前記Koblitz曲線の係数)である。
【請求項8】
入力部を介して、入力されたデータから暗号化データを生成する暗号化装置であって、
前記入力されたデータと、Koblitz曲線のスカラー倍点を用いて暗号化データを生成する暗号部と、前記スカラー倍点を計算するスカラー倍計算部と、
を有し、
前記スカラー倍計算部は、請求項1から請求項7のいずれか一項に記載のスカラー倍計算装置であることを特徴とする暗号化装置。
【請求項9】
入力部を介して、入力された暗号化データから復号化データを生成する復号化装置であって、
前記入力された暗号化データと、Koblitz曲線のスカラー倍点を用いて前記復号化データを生成する復号部と、
前記スカラー倍点を計算するスカラー倍計算部と、
を有し、
前記スカラー倍計算部は、請求項1から請求項7のいずれか一項に記載のスカラー倍計算装置であることを特徴とする復号化装置。
【請求項10】
入力部を介して、入力されたデータから署名データを生成する署名生成装置であって、
前記入力されたデータと、Koblitz曲線のスカラー倍点を用いて前記署名データを生成する署名生成処理部と、
前記スカラー倍点を計算するスカラー倍計算部と、
を有し、
前記スカラー倍計算部は、請求項1から請求項7のいずれか一項に記載のスカラー倍計算装置であることを特徴とする署名生成装置。
【請求項11】
前記署名生成装置は、演算装置を備える可搬型小型記憶媒体である
ことを特徴とする請求項10に記載の署名生成装置。
【請求項12】
入力された署名データを検証する署名検証装置であって、
前記入力された署名データと、Koblitz曲線のスカラー倍点を用いて前記署名データの検証を行う署名検証処理部と、
前記スカラー倍点を計算するスカラー倍計算部と、
を有し、
前記スカラー倍計算部は、請求項1から請求項7のいずれか一項に記載のスカラー倍計算装置であることを特徴とする署名検証装置。
【請求項13】
楕円Diffie−Hellman鍵共有スキームを用いて、公開鍵の生成および送信を行う鍵交換装置であって、
請求項1から請求項7のいずれか一項に記載のスカラー倍計算装置であるスカラー倍計算部を有し、
前記スカラー倍計算部は、記憶部に格納されている秘密鍵と、Koblitz曲線上の点と、のスカラー倍点である第1のスカラー倍点を算出し、当該第1のスカラー倍点を公開鍵とし、
前記公開鍵を外部から取得すると、記憶部に格納されている秘密鍵と、前記取得した公開鍵と、のスカラー倍点である第2のスカラー倍点を算出し、当該第2のスカラー倍点から共有情報を取得する
ことを特徴とする鍵交換装置。
【請求項14】
入力部を介して入力されたKoblitz曲線上の点の座標およびスカラー値を基に、前記Koblitz曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置によるスカラー倍計算方法であって、
前記スカラー倍計算装置は、
記憶部と、処理部と、を有し、
前記記憶部は、
τ−NAF変換された第1の符号列と、第1の符号列より短い符号長を有し、かつτ−NAF表現において前記第1の符号列と同一の値を有する第2の符号列と、を有している変換情報を格納しており、
前記処理部が、
入力された前記スカラー値を前記第1の符号列に変換し、
前記変換情報を基に、前記第1の符号列に対応する第2の符号列を取得し、
前記取得した第2の符号列を前記スカラー値の符号列として出力し、
前記出力された第2の符号列と、前記入力されたKoblitz曲線上の点の座標と、を基に、前記Koblitz曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算方法。
【請求項15】
入力部を介して入力されたKoblitz曲線上の点の座標およびスカラー値を基に、前記Koblitz曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置によるスカラー倍計算方法であって、
前記スカラー倍計算装置は、
記憶部と、処理部と、を有し、
前記記憶部は、
所定の符号列をτ進複素数表現した値と、前記τ進複素数表現に対応している第3の符号列と、を有している変換情報を格納しており、
前記処理部が、
(a1)前記入力されたスカラー値を前記τ進複素数表現にした値へ変換し、
(a2)前記変換されたτ進複素数表現が、前記変換情報に格納されていない場合、第4の符号列にτ−NAF変換した符号を1つ追加し、
(a3)前記τ進複素数表現の実部および虚部の値を予め設定されている第1の方法に従って更新し、
(a4)前記変換されたτ進複素数表現が、前記変換情報に格納されている場合、前記変換情報から、前記τ進複素数表現に対応する前記第3の符号列を取得し、前記前記τ進複素数表現の実部および虚部の値に、0を代入し、
(a5)前記更新された前記τ進複素数表現の実部および虚部の値が、共に0となるまで、前記(a2)〜(a4)の処理を繰り返し、
(a6)前記τ進複素数表現の実部および虚部の値が、共に0となった場合、前記第4の符号列の上位の桁に、前記第3の符号列を追加した第5の符号列を、前記スカラー値の符号列として出力し、
前記出力された第5の符号列と、前記入力されたKoblitz曲線上の点の座標と、を基に、前記Koblitz曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算方法。
【請求項16】
入力部を介して入力されたKoblitz曲線上の点の座標およびスカラー値を基に、前記Koblitz曲線上におけるスカラー倍点の座標を算出するスカラー倍計算装置によるスカラー倍計算方法であって、
前記スカラー倍計算装置は、
記憶部と、処理部と、を有し、
前記記憶部は、
前記入力部を介して入力された前記スカラー値を2進表現でビット列を、予め設定されている第2の方法で変換した第6の符号列と、前記第6の符号列に対応している第7の符号列と、を有している変換情報を格納しており、
前記処理部が、
(b1)前記スカラー値が2進表現のビット列として入力され、
(b2)前記ビット列の最大桁数が6桁以上であり、かつ現在計算している桁が上位6桁以外である場合、予め設定されている第3の方法に従って(1,0、−1)の3値のうちのいずれかの符号を生成し、当該生成した符号を第8の符号列に追加し、現在計算している桁が上位6桁以内となるまで、前記(b2)の処理を繰り返し、
(b3)前記ビット列の最大桁数が6桁未満である、または現在計算している桁が上位6桁以内である場合、前記ビット列のうち、現在している桁以下7桁の符号列を、前記第2の方法で変換した第9の符号列が、前記変換情報に格納されている第6の符号列のいずれかと一致するか否かを判定し、
(b4)前記判定の結果、前記第9の符号列が、前記変換情報に格納されている第6の符号列のうちのいずれとも一致しない場合、予め設定されている第4の方法に従って(1,0、−1)の3値のうちのいずれかの符号を生成し、当該生成した符号を第8の符号列に追加し、現在計算している桁が前記ビット列の最大桁数より大きくなるまで、前記(b4)の処理を繰り返し、
(b5)前記判定の結果、前記第9の符号列が、前記変換情報に格納されている第6の符号列のいずれかと一致する場合、前記変換情報から、前記第9の符号列に対応する前記第7の符号列を取得し、前記第8の符号列の上位の桁に前記第7の符号列を追加した第10の符号列を、前記スカラー値の符号列として出力し、
前記出力された第10の符号列と、前記入力されたKoblitz曲線上の点の座標と、を基に、前記Koblitz曲線上の点を前記スカラー値の値でスカラー倍した前記スカラー倍点の座標を算出する
ことを特徴とするスカラー倍計算方法。
【請求項17】
請求項14から請求項16のいずれか一項に記載のスカラー倍計算方法をコンピュータに実行させることを特徴とするプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate


【公開番号】特開2011−81147(P2011−81147A)
【公開日】平成23年4月21日(2011.4.21)
【国際特許分類】
【出願番号】特願2009−232697(P2009−232697)
【出願日】平成21年10月6日(2009.10.6)
【出願人】(000005108)株式会社日立製作所 (27,607)
【Fターム(参考)】