(57)【要約】【課題】  暗号化処理ごとに行う乱数ｋと楕円曲線上の基点Ｇとの多倍算の処理時間が長い。【解決手段】  整数１，…，ｊとＧとの各多倍算Ｇ１，…，Ｇｊを予め求めて記憶しておき、ｋが取り得る最小値ｋmin 及び最大値ｋmax 、前回乱数ｋの初期値、前回乱数多倍算値Ｑの初期値Ｑ＝ｋＧ、Ｑの最小値Ｑmin ＝ｋmin ×Ｇを予め記憶しておく。暗号化処理ごとに、１〜ｊからランダムに選択し、これをｍとし（Ｓ３１）、前回ｋにｍを加算して、今回ｋとし（Ｓ３２）、ｋ＞ｋmax でなければ（Ｓ３３）、前回Ｑにｍと対応するＧｍを加算して今回Ｑとし（Ｓ３４）、ｋ＞ｋmax であれば、ｋmin 及びＱmin をそれぞれ今回ｋ及びＱとし、前回ｋ，Ｑを今回のそれに更新する。その後、今回Ｑを用いて、暗号化処理を行う（Ｓ３７）。【選択図】  図３
2005227459.tif 000002
【特許請求の範囲】
【請求項１】
前回用いた乱数ｋ、ｋの取り得る最小値ｋmin 及び最大値ｋmax ，Ｇ１＝１×Ｇ，Ｇ２＝２×Ｇ，…，Ｇｊ＝ｊ×Ｇ，Ｑmin ＝ｋmin ×Ｇ，前回用いたＧの乱数倍値Ｑ、予め決められた整数ｊが格納された記憶部と、Ｇは有限体Ｆq 上で定義された楕円曲線上の基点であり、
上記ｋmin ≦ｋ≦ｋmax を満す整数ｋの初期値を生成するｋ生成部と、
１，２，…，ｊのいずれかの値ｍを予め定められた選択方法により選択生成するｍ生成部と、
上記ｋと上記ｍを加算して新たなｋとして出力する加算部と、
上記新たなｋが上記ｋmax より大であるか否かを判定し、大でなければそのｋを出力し、大であれば上記ｋmin を新たなｋとし、上記Ｑmin を新たなＱとし、
新たなｋがｋmax より大でなければ上記ｍと対応する上記記憶部中のＧｍと、上記記憶部中のＱとを、上記楕円曲線上で加算し、その結果を新たなＱとして出力する判定加算部と、
上記新たなＱを用いて、楕円暗号化処理を行う暗号化処理部と、
上記新たなｋ及びＱにより上記記憶部中のｋ及びＱを更新する更新部と
を具備する楕円暗号化装置。
【請求項２】
上記ｊと上記基点Ｇが入力され、上記Ｇ１，…，Ｇj を生成する楕円多倍算部と、
上記ｋmin と上記基点Ｇが入力され、上記Ｑmin を生成するＱmin 生成部と、
上記ｋの初期値と上記基点Ｇが入力されｋ×Ｇを演算して上記Ｑの初期値を得るＱ生成部とを備える請求項１記載の楕円暗号化装置。
【請求項３】
請求項１又は２に記載した楕円暗号化装置としてコンピュータを機能させるためのプログラム。
【請求項４】
請求項３に記載したプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は楕円曲線上の演算処理により、平文を暗号文にする楕円暗号や文書などに対する楕円電子署名、楕円Ｄ−Ｈ鍵配送などの楕円暗号化処理を行う楕円暗号化装置に関する。
【背景技術】
【０００２】
従来の楕円暗号化処理の例として楕円署名（楕円ＤＳＡ型署名）を以下に説明する（例えば非特許文献１参照）。
パラメータとして、有限体Ｆq のサイズｑ、有限体Ｆq 上で定義された楕円曲線Ｅ、例えばｙ2 ＝ｘ3 ＋ａｘ＋ｂ、楕円曲線Ｅ上の基点Ｇ＝（ｘＧ，ｙＧ ）、基点Ｇの位数ｎが与えられ、また秘密鍵ｄが与えられている。
図５に示すように、１≦ｋ≦ｎ−１を満す整数ｋをランダムに選択し（Ｓ１）、基点Ｇをｋ倍する楕円多倍演算を行う（Ｓ２）。
【０００３】
この演算結果ｋ×Ｇ＝（ｘi ，ｙi ）中のｘi のｎに対する剰余ｒ＝ｘi modｎを演算し（Ｓ３）、この結果ｒと秘密鍵ｄとの剰余乗算ｒ×ｄmodｎを行う（Ｓ４）。ｋの逆数のｎに対する剰余ｋ-1modｎを演算する（Ｓ５）。
メッセージＭに対しハッシュ演算を施し、その結果ｅを得る（Ｓ６）。この結果ｅとｒ×ｄとを加算し、その加算結果にｋ-1を乗算してｎに対する剰余を演算してその結果ｓを得る（Ｓ７）。メッセージＭ、その署名（ｒ，ｓ）を出力する（Ｓ８）。
この処理を１つのメッセージに対する署名ごとに行う。
【非特許文献１】ＵＲＬ：http://citeseer.nj.nec.com/johnsonqqelliptic.html
【発明の開示】
【発明が解決しようとする課題】
【０００４】
楕円暗号化処理においては、図５中のステップＳ１及びＳ２に示したように、１回の処理ごとに乱数ｋを生成して、基点Ｇをｋ倍する楕円演算を行う必要があった。この乗算は楕円曲線上の多倍算処理により求めている。例えばｋ＝１１の場合２×Ｇ＋２×Ｇ＋２×Ｇ＋２×Ｇ＋２×Ｇ＋Ｇの演算を行って１１×Ｇを求める。この多倍算処理は処理時間が比較的長くなる。
このため例えばＩＣカードなどでは主な処理のためプロセッサの他に、楕円暗号演算の専用プロセッサ、いわゆるコプロセッサを備えて高速処理させるようにしたものもあるが、その場合でも楕円曲線上での多倍算処理に数百ミリ秒もの時間がかかる。楕円暗号演算のコプロセッサが設けられていなければ、もっと処理時間が長くなる。楕円暗号、楕円鍵配送においても、その都度、乱数の生成と、その乱数と基点Ｇとの楕円曲線上での乗算を行っており、同様の問題があった。
【課題を解決するための手段】
【０００５】
この発明によれば、整数ｋ、ｋの取り得る最小値ｋmin 及び最大値ｋmax ，Ｇ１＝１×Ｇ，Ｇ２＝２×Ｇ，…，Ｇj ＝ｊ×Ｇ，Ｑmin ＝ｋmin ×Ｇ，Ｑの初期値、予め決めた整数ｊが記憶部に記憶されてあり、ここでＧは有限体Ｆq 上で定義された楕円曲線上の基点であり、
ｋmin ≦ｋ≦ｋmax を満すｋがｋ生成部によりｋの初期値として生成され、ｍ生成部により１，…，ｊのいずれかの値ｍが予め決められた選択方法により選択され、ｋとｍが加算部で加算されて、新たなｋとされ、その新たなｋがｋmax より大であるか否かが判定加算部で判定され、ｋmax ≧ｋでなければ上記ｍと対応するＧｍとＱとが加算されて、新たなＱとされ、ｋmax ≧ｋであればｋmin が新たなｋとされ、またＱmin が新たなＱとされ、これら新たなｋ及びＱにより記憶部内のｋ及びＱが更新部により更新される。またこの新たなＱを用いて暗号化処理が暗号化処理部により行われる。
【発明の効果】
【０００６】
この構成によれば、楕円暗号化処理の都度ｍが選択され、ｍと対応するＧｍ＝ｍ×Ｇと、前回の処理に用いたＱ、つまり乱数と基点Ｇとの乗算結果とを楕円加算することによりｋ（＝ｋ＋ｍ）とＧとの楕円多倍算が得られる。つまり１，…，ｊの各整数とＧとの楕円乗算の結果Ｇ１，…，Ｇｊが記憶されてあり、これを利用することにより、暗号化処理ごとに従来行っていた多倍算の結果が、ＱとＧｍの１回の楕円曲線上の加算で済み、それだけ暗号化処理時間が短かくなる。少なくともｋ生成部及び加算部をＩＣカードのような耐タンパ性をもつ装置内に設けることにより、暗号化処理ごとに変る十分に大きな値ｋを第三者が推測することにより、暗号化処理の結果を偽造したりすることが不可能になる。
【発明を実施するための最良の形態】
【０００７】
この発明の実施形態を図１に示す。この例ではＩＣカードのような耐タンパ性装置に、この楕円暗号化装置１００が構成されている。この装置１００内の記憶部１１には、有限体Ｆq 上で定義された楕円曲線Ｅ上の基点Ｇを多倍算したｊ個の結果Ｇ１，Ｇ２，…，Ｇｊ、前回用いた乱数ｋ、前回用いた基点Ｇの乱数倍の値Ｑ（以下乱数多倍算値という）、ｋの取り得る最小値ｋmin 及び最大値ｋmax 、予め決められた整数ｊ、有限体の表現方法ＦＲ、楕円曲線Ｅの係数ａ，ｂ、基点Ｇの位数ｎ、秘密鍵ｄ、公開鍵Ｙが記憶部１１に記憶されている。楕円曲線Ｅは有限体Ｆq 上で定義されたものである。
【０００８】
整数ｊはこの楕円暗号化装置１００とデータの授受を行うことができる装置のキーボードなどにより、入力部１２から記憶部１１に入力記憶される。ｊの値は任意の数でよい。ｊを大きくする程、安全性が高くなるが、多倍算結果Ｇ１，…，Ｇｊの記憶量が大になる。ＩＣカードの場合ｊは例えば１００〜２００程度とする。ｋmin 及びｋmax も同様に設定入力してもよいし、この装置１００内で生成してもよい。つまり乱数を生成し、その乱数がｑ−１以下で予め決めた最低値との差が所定値以下であればｋmin とし、予め決めた最高値との差がｋmax としてもよい。ｋの値は安全性の点からｑ−１以下の大きな値であるが、ｋmin とｋmax との間、つまりｋが変化できる範囲は小さければｋが同一値を取る確率が高くなり安全性が低下する。ｋmin とｋmax との間（範囲）はビット数で例えば１００〜１７０程度である。またｋmin は安全性の点から大きい方がよく、例えば１６０ビット以上の数であり、ｑ−１以下である。
【０００９】
この楕円暗号化装置１００を動作させるためには予め用意しておく処理が必要である。この準備処理を図２も参照して説明する。まず前述した整数ｊ及び最低値ｋmin 及び最大値ｋmax が入力部１２より入力されると記憶部１１に記憶される（Ｓ２１，Ｓ２２）。多倍算部１４にｊと基点Ｇとが記憶部１１から読み出されて入力され、多倍算部１４で、１，２，…，ｊの各数とＧとの楕円曲線Ｅ上での乗算が順次行われ、その各乗算（楕円多倍算）結果Ｇ１，Ｇ２，…，Ｇｊが記憶部１１に記憶される（Ｓ２３）。
ｋ生成部１３にｋmin 及びｋmax が入力され、ｋmin ≦ｋ≦ｋmax を満す乱数ｋが生成される。つまり乱数が生成され、その乱数がｋmin 以上、ｋmax 以下であれば前回乱数ｋの初期値として記憶部１１に記憶される（Ｓ２４）。そのｋの初期値と基点Ｇとの楕円曲線Ｅ上での乗算（多倍算）がＱ生成部１５で行われ、その結果が前回の乱数多倍算値Ｑの初期値として記憶部１１に記憶される。
【００１０】
更に最低値ｋmin と基点Ｇとの楕円曲線Ｅ上の乗算（多倍算）がＱmin 生成部１６で行われ、その結果Ｑmin ＝ｋmin ×Ｇが記憶部１１に記憶される（Ｓ２６）。なおｋmin ，ｋmax を設定入力することなく、破線ブロックの範囲設定部１７で乱数を生成し、その乱数がプログラム上で設定されている最低値との差が所定値以下であればｋmin として、またその乱数がプログラム上で設定されている最大値との差が所定値以内であればｋmaxとしてそれぞれ記憶部１１に記憶するようにしてもよい。
以上により準備処理が終了し、その処理は１回だけである。その後楕円暗号化処理は、その処理要求があるごとに次のように行われる。その例を図１及び図３を参照して説明する。
【００１１】
まず記憶部１１から整数ｊが読み出されて、ｍ選択部２１に入力される。ｍ選択部２１では１〜ｊのいずれかの整数値ｍが予め決められた選択方法により選択される。この例では１〜ｊの整数がランダムに選択値ｍとして選択される（Ｓ３１）。
この選択値ｍは加算部２２で記憶部１１から読み出された前回乱数ｋと加算されて、新たなｋとして出される（Ｓ３２）。この新たなｋは判定・加算部２３に入力され、その判定部２３ａにより、新たなｋが記憶部１１から読み出されたｋmax より大であるか否かが判定される（Ｓ３３）。その判定結果がｋmax より大でなければ、楕円加算部２３ｂで、選択値ｍと対応する多倍算値Ｇｍ(＝ｍ×Ｇ)と記憶部１１から読み出された前回乱数多倍算値Ｑとの楕円曲線Ｅ上での加算が行われ、その加算結果が新たなＱとされる（Ｓ３４）。判定部２３ａの判定結果がｋ＞ｋmax であれば、記憶部１１から読み出されたｋmin 及びＱmin がそれぞれ新たなｋ及び新たなＱとされる（Ｓ３５）。
【００１２】
判定・加算部２３より出力される新たなｋ及びＱで更新部２４により記憶部１１内の前回乱数ｋ及び前回乱数多倍算値Ｑがそれぞれ更新される（Ｓ３６）。
この新たな乱数多倍算値Ｑを用いて暗号化処理乱部２５において暗号化処理が行われる（Ｓ３７）。暗号化処理の例として楕円ＤＳＡ型署名を述べる。新たなＱ＝（ｘi ，ｙi ）中のｘi についてｎに対する剰余演算ｒ＝ｘi modｎが剰余演算部２５ａで行われる（Ｓ３７ａ）。その結果ｒと記憶部１１から読み出された秘密鍵ｄとの剰余乗算が剰余乗算部２５ｂにより行われ（Ｓ３７ｂ）、また前記新たな乱数ｋの逆数の剰余が剰余逆数演算部２５ｃで行われる（Ｓ３７ｃ）。
【００１３】
外部から入力されたメッセージＭに対し、ハッシュ演算部２５ｄにおいてハッシュ演算ｅ＝Ｈ（Ｍ）が施される（Ｓ３７ｄ）。剰余加算乗算部２５ｅで、ｅとｄ×ｒとが加算され、その加算値とｋ-1との剰余乗算が行われてｓ＝ｋ-1（ｅ＋ｄ×ｒ）modｎが出力される（Ｓ３７ｅ）。メッセージＭに対する署名（ｓ，ｒ）が出力部２５ｆから出力される（Ｓ３７ｆ）。
以上の処理が、暗号化処理、この例では署名処理を行うごとに図３におけるステップＳ３１から実行される。新たな乱数ｋは前回の乱数ｋに対し、この例ではランダムに選択された値ｍが加算されたものであり、新たな乱数多倍算値Ｑはｍと対応するＧｍ（＝ｍ×Ｇ）と前回乱数多倍算値Ｑとを楕円曲線上で加算すれば、新たな乱数ｋと基点Ｇとの楕円曲線上での多倍算の結果が得られる。従って、従来よりも演算速度が著しく向上する。
【００１４】
ｍ選択部２１でのｍの選択は、例えば１，２，…，ｊを順次選択することを繰返してもよく、あるいは暗号化処理回数を変数とする１次又は２次関数値、暗号化処理要求が生じた時の時刻と対応する値などを１〜ｊから選択してもよい。前回乱数ｋ及び前回乱数多倍算値Ｑに対しては署名生成処理ごとに更新を行う点で、記憶部１１とは別の記憶部１１ａに格納してもよい。暗号化処理部２５で行う処理は平文を暗号文にする処理、鍵配送処理でもよい。例えば楕円ＥｌＧａｍａｌ暗号処理の場合新たなＱ（＝ｋＧ）とｋＹ＋ｍ（Ｙは秘密鍵ｄと対応する公開鍵、ｍは平文）とが暗号文となり、この処理が暗号化処理部２５で行われることになる。
【００１５】
図１に示した装置１００をコンピュータにより機能させてもよい。つまり図２及び図３に示した各処理過程を、コンピュータがプログラムを実行することにより行わせることもできる。この場合はそのコンピュータにより構成される装置１００は図１に示した機能をもつが、もう少し一般的に示すと、図４に示すようになる。即ち中央制御装置（ＣＰＵ）やプロセッサよりなる制御部３０に、各種パラメータが記憶される記憶部３１、ｋ生成部３２、ｍ選択部３３、加算部３４、判定部３５、楕円加算部３６、入力部３７、楕円多倍算部３８、プログラムメモリ３９が接続される。これらのうち図１中のものと名称が同一のものは互いに対応するものである。プログラムメモリ３９には図２及び図３に示した各過程をコンピュータに実行させるためのプログラムが格納されている。楕円多倍算部３８は、図１中の多倍算部１４、Ｑ生成部１５及びＱmin 生成部１６と対応する。楕円多倍算は楕円加算を繰り返すものであるから楕円加算部３６の機能を利用して、これらＧ１，…，Ｇｊ，Ｑ，Ｑmin の生成及びＧｍ＋Ｑの加算を行わせてもよい。ｋ生成部３２、ｍ選択部３３、加算部３４、判定部３５の一つ乃至複数（全部でもよい）は制御部３０自体で機能させてもよい。プログラムメモリ３９に格納するプログラムはＣＤ−ＲＯＭ、磁気ディスク、半導体メモリなどの記録媒体に記録されたものがメモリ３９にインストールされ、又は通信回線を通じてメモリ３９にダウンロードされる。
【図面の簡単な説明】
【００１６】
【図１】この発明による装置の機能構成例を示すブロック図。
【図２】この発明装置における準備処理の手順の例を示す流れ図。
【図３】この発明装置における暗号化処理の手順の例を示す流れ図。
【図４】この発明装置をコンピュータに機能させる場合の機能構成の例を示すブロック図。
【図５】従来の楕円ＤＳＡ型署名の手順を示す流れ図。
【図１】
2005227459.tif 000003
【図２】
2005227459.tif 000004
【図３】
2005227459.tif 000005
【図４】
2005227459.tif 000006
【図５】
2005227459.tif 000007