TOP > 国内特許検索 > 楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置

楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置

国内特許コード P07A012827
整理番号 PA15-052
掲載日 2008年1月18日
出願番号 特願2003-381344
公開番号 特開2005-148141
登録番号 特許第4193176号
出願日 平成15年11月11日(2003.11.11)
公開日 平成17年6月9日(2005.6.9)
登録日 平成20年10月3日(2008.10.3)
発明者
  • 林 彬
出願人
  • 金沢工業大学
発明の名称 楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置
発明の概要 【課題】 楕円曲線暗号は安全性が高く、鍵の桁数を小さくできるため、公開鍵暗号として有望視されているが、有限体における演算に時間がかかる。
【解決手段】 入出力部10は、楕円曲線上の点Pの座標、および整数倍算の倍数を与える整数kの入力を受け付ける。s進展開部28は、複数の基数s毎に整数kのs進展開を求める。コスト評価部30は、各s進展開の非零桁の個数に基づいてs進法によりk倍算を行った場合の計算コストを求める。選択部32は、最も計算コストが小さいh進法を選択する。予備計算部34は、点Pについて(h-1)倍以下の整数倍点をあらかじめ計算して記憶する。h進法演算部35は、h倍算演算部36による点Pのh倍算と、加算演算部38による点Pの(h-1)倍以下の整数倍点の加算を組み合わせたh進法により、点Pのk倍算を計算する。
【選択図】 図1
従来技術、競合技術の概要 【背景技術】公開鍵暗号の一方式として、楕円曲線暗号(あるいは楕円暗号)がある。楕円曲線暗号は1985年頃、KoblitzとMillerがほぼ同時期に独立に提案し、RSA暗号に代わる次世代の公開鍵暗号と目されている有望な暗号である。この楕円曲線暗号は同じ安全性規準で比較すると、RSA暗号に比して鍵の大きさは数分の一でよい、という特徴がある。しかしそれでも秘密鍵暗号に比べて計算に時間がかかり低速である、という問題点は解決されていない。そこで高速化の方法が種々の方面から検討されている。楕円曲線暗号は有限体上で定義された楕円曲線上の点の間に適当な加法を定義すると、これら点たちが群をなすことを利用する。楕円曲線の上に基準となる1点Pを定め、これをk倍した点をQ=kPとすると、Qを与えられても、これからkを求めることは計算量的に難しい。これを楕円曲線上の離散対数問題の困難性という。楕円曲線暗号はこの性質を利用する暗号であり、楕円曲線暗号を利用するには、点のk倍算が必要になる。従来のk倍算の方法は、2倍算と加算の組合せ(いわゆる“double-and-add”)による2進法である。この方法ではlogk回の2倍算と平均(1/2)logk回の加算が必要となる。これの改良法としてm進法がある。ただしmは2のべき2である。さらに加法と減法を併用する符号付き法、移動窓法などがある(たとえば、非特許文献1参照)。
【非特許文献1】イアン・F・ブラケ,ガディエル・セロッシ,ナイジェル・P・スマート著,鈴木治郎訳,「楕円曲線暗号」,初版,株式会社ピアソン・エデュケーション,2001年12月20日
産業上の利用分野 この発明は楕円曲線暗号技術に関し、特に楕円曲線上の点の整数倍演算を行う楕円曲線整数倍演算装置、ならびにその装置を利用可能な鍵生成装置、暗号化装置および復号装置に関する。
特許請求の範囲 【請求項1】 楕円曲線上の任意の点Pの整数倍演算kPを行う楕円曲線整数倍演算装置であって、 整数kについて複数の基数sによるs進展開を求めるs進展開部と、 前記複数の基数sのそれぞれについて、前記点Pのk倍点Qをs倍算と加算の組み合わせにより算出するs進法の計算コストを評価するコスト評価部と、 前記計算コストに基づき、前記複数の基数sの中から一つの基数hを選択する選択部と、 選択された前記基数hによる前記整数kのh進展開に基づき、前記点Pのk倍点Qをh倍算と加算の組み合わせにより算出するh進法演算部とを含むことを特徴とする楕円曲線整数倍演算装置。
【請求項2】 前記h進法演算部における前記h進法の演算に必要な前記点Pの(h-1)倍以下の整数倍点をあらかじめ計算する予備計算部と、 前記予備計算部により計算された前記(h-1)倍以下の整数倍点を記憶する記憶部とをさらに含み、 前記h進法演算部は、前記記憶部に記憶された前記(h-1)倍以下の整数倍点を加算の際に利用することを特徴とする請求項1に記載の楕円曲線整数倍演算装置。
【請求項3】 前記コスト評価部は、前記s進展開における非零桁の個数を用いた評価式に基づいて、各s進法の計算コストを比較することを特徴とする請求項1または2に記載の楕円曲線整数倍演算装置。
【請求項4】 前記コスト評価部は、前記s進展開における非零桁の個数をs進桁数で除算した相対重みを用いた評価式に基づいて、各s進法の計算コストを比較することを特徴とする請求項1または2に記載の楕円曲線整数倍演算装置。
【請求項5】 前記コスト評価部は、前記s進法における逆元算と乗算の計算コストの比の見積もり値を用いた評価式に基づいて、各s進法の計算コストを比較することを特徴とする請求項3または4に記載の楕円曲線整数倍演算装置。
【請求項6】 楕円曲線上の基点Gとその位数nの入力を受け付ける入力部と、 0<d<nを満たす乱数dを生成する乱数生成部と、 前記基点Gのd倍点Qを算出する整数倍演算部と、 前記乱数dを秘密鍵、前記d倍点Qを公開鍵として生成する鍵生成部とを含み、 前記整数倍演算部は、楕円曲線上の任意の点Pの整数倍演算kPを行うものであって、 整数kについて複数の基数sによるs進展開を求めるs進展開部と、 前記複数の基数sのそれぞれについて、前記点Pのk倍点Qをs倍算と加算の組み合わせにより算出するs進法の計算コストを評価するコスト評価部と、 前記計算コストに基づき、前記複数の基数sの中から一つの基数hを選択する選択部と、 選択された前記基数hによる前記整数kのh進展開に基づき、前記点Pのk倍点Qをh倍算と加算の組み合わせにより算出するh進法演算部とを含むことを特徴とする鍵生成装置。
【請求項7】 楕円曲線上の基点Gとその位数n、公開鍵Q、および平文Mの入力を受け付ける入力部と、 0<r<nを満たす乱数rを生成する乱数生成部と、 前記基点Gのr倍点rGと、前記公開鍵Qのr倍点rQを算出する整数倍演算部と、 前記整数倍演算部による算出結果を用いて、第1暗号C1=rGと第2暗号C2=rQ+Mを計算し、暗号文(C1、C2)を生成する暗号文生成部とを含み、 前記整数倍演算部は、楕円曲線上の任意の点Pの整数倍演算kPを行うものであって、 整数kについて複数の基数sによるs進展開を求めるs進展開部と、 前記複数の基数sのそれぞれについて、前記点Pのk倍点Qをs倍算と加算の組み合わせにより算出するs進法の計算コストを評価するコスト評価部と、 前記計算コストに基づき、前記複数の基数sの中から一つの基数hを選択する選択部と、 選択された前記基数hによる前記整数kのh進展開に基づき、前記点Pのk倍点Qをh倍算と加算の組み合わせにより算出するh進法演算部とを含むことを特徴とする暗号化装置。
【請求項8】 楕円曲線上の基点Gとその位数n、公開鍵Q、および平文Mに対して、0<r<nを満たす乱数rを定めて、前記基点Gのr倍点rGと前記公開鍵Qのr倍点rQを算出し、その算出結果を用いて、第1暗号C1=rGと第2暗号C2=rQ+Mを計算することで生成された暗号文(C1、C2)と、秘密鍵dの入力を受け付ける入力部と、 前記第1暗号C1のd倍点dC1を算出する整数倍演算部と、 前記整数倍演算部による算出結果を用いて、前記第2暗号C2から前記第1暗号C1のd倍点dC1を減算することにより、復号された平文Mを生成する平文生成部とを含み、 前記整数倍演算部は、楕円曲線上の任意の点Pの整数倍演算kPを行うものであって、 整数kについて複数の基数sによるs進展開を求めるs進展開部と、 前記複数の基数sのそれぞれについて、前記点Pのk倍点Qをs倍算と加算の組み合わせにより算出するs進法の計算コストを評価するコスト評価部と、 前記計算コストに基づき、前記複数の基数sの中から一つの基数hを選択する選択部と、 選択された前記基数hによる前記整数kのh進展開に基づき、前記点Pのk倍点Qをh倍算と加算の組み合わせにより算出するh進法演算部とを含むことを特徴とする復号装置。
産業区分
  • その他通信
国際特許分類(IPC)
Fターム
出願権利状態 権利存続中
ライセンスをご希望の方、特許の内容に興味を持たれた方は、「問合せ先」まで直接お問合せ下さい。


PAGE TOP

close
close
close
close
close
close
close