(57)【要約】  ｅ及びｎは公開情報、ｄは秘密情報である。電子署名は、ｅ×ｄ  ｍｏｄ  ｎの計算値に基づいて生成される。署名生成装置１００は、乱数生成部１０３、第１計算部１１１、第２計算部１１２、署名生成部１２１を備える。乱数生成部１０３は、乱数ｒを生成する。第１計算部１１１は、ｓ１＝ｒ×ｎを計算する。第２計算部１１２は、ｓ２＝ｓ１＋ｅを計算する。署名生成部１２１は、ｓ３＝ｓ２×ｄ  ｍｏｄ  ｎを計算し、ｓ３をｅ×ｄ  ｍｏｄ  ｎの計算値として出力する。これにより、署名生成装置１００は、差分電力攻撃に対して安全に上記電子署名を生成することができる。
2012086076.tif 000002
【特許請求の範囲】
【請求項１】
公開情報ｅと秘密情報ｄとの乗算を含む演算Ｃの結果に対して公開情報ｎを法とする剰余を計算することにより得られる電子署名を生成する署名生成装置において、
前記公開情報ｅ，ｎを入力する入力部と、
前記秘密情報ｄを予め格納する記憶装置から前記秘密情報ｄを読み取る読取部と、
新たな秘密情報ｒと前記入力部により入力された公開情報ｎとの乗算Ｍ１を処理装置により行う第１計算部と、
前記第１計算部により行われた乗算Ｍ１の結果と前記入力部により入力された公開情報ｅとの加算Ｍ２を処理装置により行う第２計算部と、
前記演算Ｃとして、前記第２計算部により行われた加算Ｍ２の結果と前記読取部により読み取られた秘密情報ｄとの乗算を含む演算Ｃ’を処理装置により行い、前記演算Ｃ’の結果に対して前記入力部により入力された公開情報ｎを法とする剰余を処理装置により計算することにより前記電子署名を生成する署名生成部と
を備えることを特徴とする署名生成装置。
【請求項２】
前記署名生成装置は、さらに、乱数ｒを生成する乱数生成部を備え、
前記第１計算部は、前記乱数生成部により生成された乱数ｒを前記新たな秘密情報ｒとして用いることを特徴とする請求項１の署名生成装置。
【請求項３】
前記第１計算部は、前記演算Ｃ’で用いられる情報を生成する過程で計算される値を前記新たな秘密情報ｒとして用いることを特徴とする請求項１の署名生成装置。
【請求項４】
前記署名生成装置は、さらに、乱数ｋを生成する乱数生成部を備え、
前記電子署名は、ＥＣ−Ｓｃｈｎｏｒｒ（Ｅｌｌｉｐｔｉｃ・Ｃｕｒｖｅ・Ｓｃｈｎｏｒｒ）署名であり、
前記入力部は、前記乱数生成部により生成された乱数ｋと楕円曲線上の生成元Ｇとのスカラー倍算値Ｐを計算し、前記電子署名が付与される対象となるメッセージＭと当該スカラー倍算値Ｐのｘ座標値とを連結してハッシュ値に変換し、当該ハッシュ値を前記公開情報ｅとして入力し、
前記署名生成部は、前記第２計算部により行われた加算Ｍ２の結果と前記読取部により読み取られた秘密情報ｄとの乗算Ｍ３を行い、当該乗算Ｍ３の結果と前記乱数生成部により生成された乱数ｋとの加算Ｍ４を行い、当該加算Ｍ４の結果を前記演算Ｃ’の結果として用いることを特徴とする請求項１の署名生成装置。
【請求項５】
前記乱数生成部は、前記乱数ｋとは別に乱数ｒを生成し、
前記第１計算部は、前記乱数生成部により生成された乱数ｒを前記新たな秘密情報ｒとして用いることを特徴とする請求項４の署名生成装置。
【請求項６】
前記第１計算部は、前記入力部により計算されたスカラー倍算値Ｐのｘ座標値とｙ座標値とのいずれかの少なくとも一部を前記新たな秘密情報ｒとして用いることを特徴とする請求項４の署名生成装置。
【請求項７】
前記第１計算部は、前記入力部により前記スカラー倍算値Ｐが計算される過程で得られる値を前記新たな秘密情報ｒとして用いることを特徴とする請求項４の署名生成装置。
【請求項８】
前記署名生成装置は、さらに、乱数ｋを生成する乱数生成部を備え、
前記電子署名は、ＥＣＤＳＡ（Ｅｌｌｉｐｔｉｃ・Ｃｕｒｖｅ・Ｄｉｇｉｔａｌ・Ｓｉｇｎａｔｕｒｅ・Ａｌｇｏｒｉｔｈｍ）署名であり、
前記入力部は、前記乱数生成部により生成された乱数ｋと楕円曲線上の生成元Ｇとのスカラー倍算値Ｐを計算し、当該スカラー倍算値Ｐのｘ座標値を前記公開情報ｅとして入力し、
前記署名生成部は、前記第２計算部により行われた加算Ｍ２の結果と前記読取部により読み取られた秘密情報ｄとの乗算Ｍ３を行い、当該乗算Ｍ３の結果と前記電子署名が付与される対象となるメッセージＭのハッシュ値ｈ（Ｍ）との加算Ｍ４を行い、当該加算Ｍ４の結果と前記乱数生成部により生成された乱数ｋの逆数ｋ−１との乗算Ｍ５を行い、当該乗算Ｍ５の結果を前記演算Ｃ’の結果として用いることを特徴とする請求項１の署名生成装置。
【請求項９】
前記乱数生成部は、前記乱数ｋとは別に乱数ｒを生成し、
前記第１計算部は、前記乱数生成部により生成された乱数ｒを前記新たな秘密情報ｒとして用いることを特徴とする請求項８の署名生成装置。
【請求項１０】
前記第１計算部は、前記入力部により計算されたスカラー倍算値Ｐのｘ座標値とｙ座標値とのいずれかの少なくとも一部を前記新たな秘密情報ｒとして用いることを特徴とする請求項８の署名生成装置。
【請求項１１】
前記第１計算部は、前記入力部により前記スカラー倍算値Ｐが計算される過程で得られる値を前記新たな秘密情報ｒとして用いることを特徴とする請求項８の署名生成装置。
【請求項１２】
公開情報ｅと秘密情報ｄとの乗算を含む演算Ｃの結果に対して公開情報ｎを法とする剰余を計算することにより得られる電子署名を生成する署名生成方法において、
前記公開情報ｅ，ｎを入力し、
前記秘密情報ｄを予め格納する記憶装置から前記秘密情報ｄを読み取り、
新たな秘密情報ｒと前記入力された公開情報ｎとの乗算Ｍ１を処理装置により行い、
前記乗算Ｍ１の結果と前記入力された公開情報ｅとの加算Ｍ２を処理装置により行い、
前記演算Ｃとして、前記加算Ｍ２の結果と前記読み取られた秘密情報ｄとの乗算を含む演算Ｃ’を処理装置により行い、前記演算Ｃ’の結果に対して前記入力された公開情報ｎを法とする剰余を処理装置により計算することにより前記電子署名を生成することを特徴とする署名生成方法。
【請求項１３】
公開情報ｅと秘密情報ｄとの乗算を含む演算Ｃの結果に対して公開情報ｎを法とする剰余を計算することにより得られる電子署名を生成するコンピュータを、
前記公開情報ｅ，ｎを入力する入力部と、
前記秘密情報ｄを予め格納する記憶装置から前記秘密情報ｄを読み取る読取部と、
新たな秘密情報ｒと前記入力部により入力された公開情報ｎとの乗算Ｍ１を処理装置により行う第１計算部と、
前記第１計算部により行われた乗算Ｍ１の結果と前記入力部により入力された公開情報ｅとの加算Ｍ２を処理装置により行う第２計算部と、
前記演算Ｃとして、前記第２計算部により行われた加算Ｍ２の結果と前記読取部により読み取られた秘密情報ｄとの乗算を含む演算Ｃ’を処理装置により行い、前記演算Ｃ’の結果に対して前記入力部により入力された公開情報ｎを法とする剰余を処理装置により計算することにより前記電子署名を生成する署名生成部
として機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、署名生成装置及び署名生成方法及び記録媒体に関するものである。
【背景技術】
【０００２】
電子署名は、署名者の秘密鍵を用いて生成される（非特許文献１参照）。秘密鍵は、署名者本人しか知らないデータである。秘密鍵が暴かれると、署名の偽造ができる。【０００３】
電子署名を計算する際には、公開情報と秘密情報（例えば、秘密鍵）との乗算を行うステップが発生する。公開情報を参照しながら、公開情報と秘密情報との乗算に対して差分電力解析を行うことで、秘密情報を求めることができる（非特許文献２参照）。【０００４】
例えば、ＥＣ−Ｓｃｈｎｏｒｒ署名アルゴリズム（Ｅｌｌｉｐｔｉｃ・Ｃｕｒｖｅ・Ｓｃｈｎｏｒｒ・Ｄｉｇｉｔａｌ・Ｓｉｇｎａｔｕｒｅ・Ａｌｇｏｒｉｔｈｍ）は以下の通りである。
ステップ０．Ｇを楕円曲線上の生成元、Ｇの位数をｎとおく。ｄを秘密鍵、Ｍを署名対象のメッセージ、ｈをハッシュ関数とする。
ステップ１．乱数ｋを生成する。ｋはｎ未満の自然数である。
ステップ２．Ｐ＝ｋＧを計算し、Ｐのｘ座標をＰｘとする。
ステップ３．ｅ＝ｈ（Ｍ｜｜Ｐｘ）を計算する。“｜｜”は連結を表す。
ステップ４．ｓ＝（ｅ×ｄ＋ｋ）  ｍｏｄ  ｎを計算する。
ステップ５．（ｅ，ｓ）がＭの電子署名となる。【０００５】
上記計算方法では、ステップ４でｅ×ｄの計算が行われている。ｅは公開情報なので、差分電力解析を行うことで、秘密鍵ｄを求めることができる。【０００６】
例えば、ＥＣ−ＤＳＡ（Ｅｌｌｉｐｔｉｃ・Ｃｕｒｖｅ・Ｄｉｇｉｔａｌ・Ｓｉｇｎａｔｕｒｅ・Ａｌｇｏｒｉｔｈｍ）は以下の通りである。
ステップ０．Ｇを楕円曲線上の生成元、Ｇの位数をｎとおく。ｄを秘密鍵、Ｍを署名対象のメッセージ、ｈをハッシュ関数とする。
ステップ１．乱数ｋを生成する。ｋはｎ未満の自然数である。
ステップ２．Ｐ＝ｋＧを計算し、Ｐのｘ座標をＰｘとする。
ステップ３．ｓ＝ｋ−１（Ｐｘ×ｄ＋ｈ（Ｍ））  ｍｏｄ  ｎを計算する。
ステップ４．（Ｐｘ，ｓ）がＭの電子署名となる。【０００７】
上記計算方法では、ステップ４でＰｘ×ｄの計算が行われている。Ｐｘは公開情報なので、差分電力解析を行うことで、秘密鍵ｄを求めることができる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】ＩＳＯ／ＩＥＣ  １４８８８−３：２００６／ＦＤＡＭ  １，  “Ｉｎｆｏｒｍａｔｉｏｎ  ｔｅｃｈｎｏｌｏｇｙ  −  Ｓｅｃｕｒｉｔｙ  ｔｅｃｈｎｉｑｕｅｓ  −  Ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅｓ  ｗｉｔｈ  ａｐｐｅｎｄｉｘ  −  Ｐａｒｔ  ３：  Ｄｉｓｃｒｅｔｅ  ｌｏｇａｒｉｔｈｍ  ｂａｓｅｄ  ｍｅｃｈａｎｉｓｍｓ  −  Ａｍｅｎｄｍｅｎｔ  １：  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｒｕｓｓｉａｎ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ，  Ｓｃｈｎｏｒｒ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ，  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｓｃｈｎｏｒｒ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ，  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｆｕｌｌ  Ｓｃｈｎｏｒｒ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ，”  ＩＳＯ／ＩＥＣ  ＪＴＣ  １／ＳＣ  ２７，  ２００９−１２−１５
【非特許文献２】Ｊｅａｎ−Ｓｅｂａｓｔｉｅｎ  Ｃｏｒｏｎ，  “Ｒｅｓｉｓｔａｎｃｅ  ａｇａｉｎｓｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ｆｏｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ，”  ＣＨＥＳ  ’９９，  ＬＮＣＳ  １７１７，  ｐｐ．  ２９２−３０２，  １９９９
【発明の概要】
【発明が解決しようとする課題】
【０００９】
前述した例において、ｄを知っている人は誰でも署名を作ることができる。即ち、他人に秘密鍵が渡ると、署名の偽造ができる。しかし、従来の計算方法では、差分電力解析を行うことで、容易に秘密鍵を入手することができる。ＥＣ−Ｓｃｈｎｏｒｒ署名、ＥＣ−ＤＳＡ署名だけでなく、Ｓｃｈｎｏｒｒ署名、ＤＳＡ（Ｄｉｇｉｔａｌ・Ｓｉｇｎａｔｕｒｅ・Ａｌｇｏｒｉｔｈｍ）署名といった電子署名の演算に対しても、同様に差分電力解析を行うことで、秘密鍵が暴かれると、署名の偽造ができる。【００１０】
本発明は、例えば、差分電力攻撃に対して安全に電子署名を生成することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の一の態様に係る署名生成装置は、
公開情報ｅと秘密情報ｄとの乗算を含む演算の結果に対して公開情報ｎを法とする剰余を計算することにより得られる電子署名を生成する署名生成装置であり、
前記公開情報ｅ，ｎを入力する入力部と、
前記秘密情報ｄを予め格納する記憶装置から前記秘密情報ｄを読み取る読取部と、
新たな秘密情報ｒと前記入力部により入力された公開情報ｎとの乗算Ｍ１を処理装置により行う第１計算部と、
前記第１計算部により行われた乗算Ｍ１の結果と前記入力部により入力された公開情報ｅとの加算Ｍ２を処理装置により行う第２計算部と、
前記演算として、前記第２計算部により行われた加算Ｍ２の結果と前記読取部により読み取られた秘密情報ｄとの乗算を含む演算Ｃを処理装置により行い、前記演算Ｃの結果に対して前記入力部により入力された公開情報ｎを法とする剰余を処理装置により計算することにより前記電子署名を生成する署名生成部とを備える。
【発明の効果】
【００１２】
本発明の一の態様によれば、差分電力攻撃に対して安全に、ＥＣ−Ｓｃｈｎｏｒｒ署名、Ｓｃｈｎｏｒｒ署名、ＥＣ−ＤＳＡ署名、ＤＳＡ署名といった電子署名の演算を行うことができる。
【図面の簡単な説明】
【００１３】
【図１】実施の形態１及び２に係る署名生成装置の構成を示すブロック図。
【図２】実施の形態１及び２に係る署名生成装置のハードウェア構成の一例を示す図。
【図３】実施の形態１に係る署名生成装置の動作を示すフローチャート。
【図４】実施の形態２に係る署名生成装置の動作を示すフローチャート。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について、図を用いて説明する。
【００１５】
実施の形態１．
本実施の形態は、公開情報ｅと秘密情報ｄとの乗算（即ち、ｅ×ｄ）を含む演算Ｃの結果ｔに対して公開情報ｎを法とする剰余（即ち、ｔ  ｍｏｄ  ｎ）を計算することにより得られる電子署名の生成に適用することができる。そのような電子署名としては、ＥＣ−Ｓｃｈｎｏｒｒ署名、Ｓｃｈｎｏｒｒ署名、ＥＣ−ＤＳＡ署名、ＤＳＡ署名等が挙げられる。本実施の形態では、そのような電子署名を生成する際に、公開情報ｅと秘密情報ｄとの乗算をそのまま行わないように、計算方法を工夫する。
【００１６】
図１は、本実施の形態に係る署名生成装置１００の構成を示すブロック図である。
【００１７】
図１において、署名生成装置１００は、入力部１０１、読取部１０２、乱数生成部１０３、第１計算部１１１、第２計算部１１２、署名生成部１２１を備える。署名生成装置１００の各部の動作については後述する。
【００１８】
署名生成装置１００は、処理装置１５１、記憶装置１５２、入力装置１５３、出力装置１５４といったハードウェアを備える。ハードウェアは署名生成装置１００の各部によって利用される。例えば、処理装置１５１は、署名生成装置１００の各部でデータや情報の演算、加工、読み取り、書き込み等を行うために利用される。記憶装置１５２は、そのデータや情報を記憶するために利用される。入力装置１５３は、そのデータや情報を入力するために利用される。出力装置１５４は、そのデータや情報を出力するために利用される。
【００１９】
図２は、署名生成装置１００のハードウェア構成の一例を示す図である。
【００２０】
図２において、署名生成装置１００は、コンピュータであり、ＬＣＤ９０１（Ｌｉｑｕｉｄ・Ｃｒｙｓｔａｌ・Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、ＣＤＤ９０５（Ｃｏｍｐａｃｔ・Ｄｉｓｃ・Ｄｒｉｖｅ）、プリンタ９０６といったハードウェアデバイスを備えている。これらのハードウェアデバイスはケーブルや信号線で接続されている。ＬＣＤ９０１の代わりに、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）、あるいは、その他の表示装置が用いられてもよい。マウス９０３の代わりに、タッチパネル、タッチパッド、トラックボール、ペンタブレット、あるいは、その他のポインティングデバイスが用いられてもよい。
【００２１】
署名生成装置１００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）を備えている。ＣＰＵ９１１は、処理装置１５１の一例である。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）、ＲＡＭ９１４（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）、通信ボード９１５、ＬＣＤ９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ９０６、ＨＤＤ９２０（Ｈａｒｄ・Ｄｉｓｋ・Ｄｒｉｖｅ）と接続され、これらのハードウェアデバイスを制御する。ＨＤＤ９２０の代わりに、フラッシュメモリ、光ディスク装置、メモリカードリーダライタ、あるいは、その他の記録媒体が用いられてもよい。
【００２２】
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、ＨＤＤ９２０は、不揮発性メモリの一例である。これらは、記憶装置１５２の一例である。通信ボード９１５、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５は、入力装置１５３の一例である。また、通信ボード９１５、ＬＣＤ９０１、プリンタ９０６は、出力装置１５４の一例である。
【００２３】
通信ボード９１５は、ＬＡＮ（Ｌｏｃａｌ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）等に接続されている。通信ボード９１５は、ＬＡＮに限らず、ＩＰ−ＶＰＮ（Ｉｎｔｅｒｎｅｔ・Ｐｒｏｔｏｃｏｌ・Ｖｉｒｔｕａｌ・Ｐｒｉｖａｔｅ・Ｎｅｔｗｏｒｋ）、広域ＬＡＮ、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ・Ｔｒａｎｓｆｅｒ・Ｍｏｄｅ）ネットワークといったＷＡＮ（Ｗｉｄｅ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）、あるいは、インターネットに接続されていても構わない。ＬＡＮ、ＷＡＮ、インターネットは、ネットワークの一例である。
【００２４】
ＨＤＤ９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。プログラム群９２３には、本実施の形態の説明において「〜部」として説明する機能を実行するプログラムが含まれている。プログラムは、ＣＰＵ９１１により読み出され実行される。ファイル群９２４には、本実施の形態の説明において、「〜データ」、「〜情報」、「〜ＩＤ（識別子）」、「〜フラグ」、「〜結果」として説明するデータや情報や信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」や「〜テーブル」の各項目として含まれている。「〜ファイル」や「〜データベース」や「〜テーブル」は、ＲＡＭ９１４やＨＤＤ９２０等の記録媒体に記憶される。ＲＡＭ９１４やＨＤＤ９２０等の記録媒体に記憶されたデータや情報や信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出、検索、参照、比較、演算、計算、制御、出力、印刷、表示といったＣＰＵ９１１の処理（動作）に用いられる。抽出、検索、参照、比較、演算、計算、制御、出力、印刷、表示といったＣＰＵ９１１の処理中、データや情報や信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００２５】
本実施の形態の説明において用いるブロック図やフローチャートの矢印の部分は主としてデータや信号の入出力を示す。データや信号は、ＲＡＭ９１４等のメモリ、ＦＤＤ９０４のフレキシブルディスク（ＦＤ）、ＣＤＤ９０５のコンパクトディスク（ＣＤ）、ＨＤＤ９２０の磁気ディスク、光ディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）、あるいは、その他の記録媒体に記録される。また、データや信号は、バス９１２、信号線、ケーブル、あるいは、その他の伝送媒体により伝送される。
【００２６】
本実施の形態の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜工程」、「〜手順」、「〜処理」であってもよい。即ち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。あるいは、「〜部」として説明するものは、ソフトウェアのみ、あるいは、素子、デバイス、基板、配線といったハードウェアのみで実現されていても構わない。あるいは、「〜部」として説明するものは、ソフトウェアとハードウェアとの組み合わせ、あるいは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実現されていても構わない。ファームウェアとソフトウェアは、プログラムとして、フレキシブルディスク、コンパクトディスク、磁気ディスク、光ディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。即ち、プログラムは、本実施の形態の説明で述べる「〜部」としてコンピュータを機能させるものである。あるいは、プログラムは、本実施の形態の説明で述べる「〜部」の手順や方法をコンピュータに実行させるものである。
【００２７】
図３は、署名生成装置１００の動作（即ち、本実施の形態に係る署名生成方法）を示すフローチャートである。
【００２８】
ステップＳ１０１において、入力部１０１は、公開情報ｎを入力する。例えば、入力部１０１は、記憶装置１５２から公開情報ｎを読み取り、読み取った公開情報ｎを入力する。入力部１０１は、公開情報ｎを入力装置１５３により署名生成装置１００の外部から受信し、受信した公開情報ｎを入力してもよい。あるいは、入力部１０１は、公開情報ｎを処理装置１５１により計算し、計算した公開情報ｎを入力してもよい。
【００２９】
ステップＳ１０２において、入力部１０１は、公開情報ｅを入力する。例えば、入力部１０１は、公開情報ｅを処理装置１５１により計算し、計算した公開情報ｅを入力する。入力部１０１は、記憶装置１５２から公開情報ｅを読み取り、読み取った公開情報ｅを入力してもよい。あるいは、入力部１０１は、公開情報ｅを入力装置１５３により署名生成装置１００の外部から受信し、受信した公開情報ｅを入力してもよい。
【００３０】
ステップＳ１０３において、読取部１０２は、記憶装置１５２から秘密情報ｄを読み取る。記憶装置１５２には、秘密情報ｄが予め格納されている。例えば、秘密情報ｄは、入力部１０１により入力され、記憶装置１５２に格納される。
【００３１】
ステップＳ１０４において、乱数生成部１０３は、新たな秘密情報ｒとして乱数ｒを生成する。
【００３２】
ステップＳ１０１〜Ｓ１０４を処理する順序及び／又はタイミングは適宜変更してよい。
【００３３】
ステップＳ１０５において、第１計算部１１１は、乱数生成部１０３により生成された乱数ｒと入力部１０１により入力された公開情報ｎとの乗算Ｍ１を処理装置１５１により行う。即ち、第１計算部１１１は、ｓ１＝ｒ×ｎを計算する。
【００３４】
ステップＳ１０６において、第２計算部１１２は、第１計算部１１１により行われた乗算Ｍ１の結果ｓ１と入力部１０１により入力された公開情報ｅとの加算Ｍ２を処理装置１５１により行う。即ち、第２計算部１１２は、ｓ２＝ｓ１＋ｅを計算する。
【００３５】
ステップＳ１０７において、署名生成部１２１は、前述した演算Ｃとして、第２計算部１１２により行われた加算Ｍ２の結果ｓ２と読取部１０２により読み取られた秘密情報ｄとの乗算（即ち、ｓ２×ｄ）を含む演算Ｃ’を処理装置１５１により行う。そして、署名生成部１２１は、演算Ｃ’の結果ｔ’に対して入力部１０１により入力された公開情報ｎを法とする剰余を処理装置１５１により計算する。即ち、署名生成部１２１は、ｓ３＝ｔ’  ｍｏｄ  ｎを計算する。ｓ３と、署名検証用の情報（例えば、公開情報ｅ）との組み合わせが電子署名となる。
【００３６】
ステップＳ１０８において、署名生成部１２１は、ステップＳ１０７で生成した電子署名を出力する。例えば、署名生成部１２１は、生成した電子署名を任意のアプリケーションプログラムに渡す。あるいは、例えば、署名生成部１２１は、生成した電子署名を出力装置１５４により署名生成装置１００の外部へ送信する。
【００３７】
ステップＳ１０７では、結果的に、演算Ｃ’の少なくとも一部として（ｒ×ｎ＋ｅ）×ｄの計算が行われる。演算Ｃのようにｅ×ｄの計算が出現しないため、差分電力解析により、ｄを求められることはない。したがって、差分電力攻撃に対して安全に電子署名を生成することができる。
【００３８】
本実施の形態を単純化すると、署名生成装置１００は、ｅ×ｄ  ｍｏｄ  ｎの演算を以下のように行っていることになる。
ステップ１．乱数ｒを生成する。
ステップ２．ｓ１＝ｒ×ｎを計算する。
ステップ３．ｓ２＝ｓ１＋ｅを計算する。
ステップ４．ｓ３＝ｓ２×ｄ  ｍｏｄ  ｎを計算する。
ステップ５．ｓ３をｅ×ｄ  ｍｏｄ  ｎの計算値として出力する。
【００３９】
上記計算方法では、ステップ４でｅ×ｄの計算の代わりに（ｒ×ｎ＋ｅ）×ｄの計算が行われている。しかし、ｒ×ｎの部分はｍｏｄ  ｎの計算において０と同等であるから、ｅ×ｄの計算と同じ結果が得られる。したがって、差分電力攻撃に対して安全にｅ×ｄ  ｍｏｄ  ｎの計算値が得られる。
【００４０】
以下、本実施の形態の第１適用例について、図３を用いて説明する。本例では、署名生成装置１００が電子署名としてＥＣ−Ｓｃｈｎｏｒｒ署名を生成する。
【００４１】
ステップＳ１０１において、入力部１０１は、公開情報ｎとして楕円曲線上の生成元Ｇの位数ｎを入力する。
【００４２】
本例では、ステップＳ１０２の前に、乱数生成部１０３が、乱数ｋを生成する。ｋはｎ未満の自然数である。
【００４３】
ステップＳ１０２において、入力部１０１は、乱数生成部１０３により生成された乱数ｋと楕円曲線上の生成元Ｇとのスカラー倍算値Ｐを処理装置１５１により計算する。即ち、入力部１０１は、Ｐ＝ｋＧを計算する。次に、入力部１０１は、電子署名が付与される対象となるメッセージＭと当該スカラー倍算値Ｐのｘ座標値（即ち、Ｐｘ）とを連結して処理装置１５１によりハッシュ値に変換する。そして、入力部１０１は、当該ハッシュ値を公開情報ｅとして入力する。即ち、入力部１０１は、ｅ＝ｈ（Ｍ｜｜Ｐｘ）を計算する。
【００４４】
ステップＳ１０３において、読取部１０２は、記憶装置１５２から秘密情報ｄとして秘密鍵ｄを読み取る。
【００４５】
ステップＳ１０４において、乱数生成部１０３は、乱数ｋとは別に乱数ｒを生成する。ｒは自然数である。
【００４６】
ステップＳ１０５において、第１計算部１１１は、乱数生成部１０３により生成された乱数ｒと入力部１０１により入力された位数ｎとの乗算Ｍ１を処理装置１５１により行う。即ち、第１計算部１１１は、ｓ１＝ｒ×ｎを計算する。
【００４７】
ステップＳ１０６において、第２計算部１１２は、第１計算部１１１により行われた乗算Ｍ１の結果ｓ１と入力部１０１により入力された公開情報ｅとの加算Ｍ２を処理装置１５１により行う。即ち、第２計算部１１２は、ｓ２＝ｓ１＋ｅを計算する。
【００４８】
ステップＳ１０７において、署名生成部１２１は、第２計算部１１２により行われた加算Ｍ２の結果ｓ２と読取部１０２により読み取られた秘密鍵ｄとの乗算Ｍ３を処理装置１５１により行う。そして、署名生成部１２１は、当該乗算Ｍ３の結果と乱数生成部１０３により生成された乱数ｋとの加算Ｍ４を処理装置１５１により行う。当該加算Ｍ４の結果が演算Ｃ’の結果ｔ’となる。即ち、署名生成部１２１は、ｔ’＝ｓ２×ｄ＋ｋを計算する。次に、署名生成部１２１は、演算Ｃ’の結果ｔ’に対して入力部１０１により入力された位数ｎを法とする剰余を処理装置１５１により計算する。即ち、署名生成部１２１は、ｓ３＝ｔ’  ｍｏｄ  ｎを計算する。ｓ３と公開情報ｅとの組み合わせが電子署名となる。即ち、（ｅ，ｓ３）がＭの電子署名となる。
【００４９】
ステップＳ１０７で、署名生成部１２１は、乗算Ｍ３の結果を加算Ｍ４に用いる前に、乗算Ｍ３の結果に対して位数ｎを法とする剰余を計算し、その剰余で乗算Ｍ３の結果を置き換えてもよい。即ち、署名生成部１２１は、ｔ’＝ｓ２×ｄ＋ｋの代わりに、（ｓ２×ｄ  ｍｏｄ  ｎ）＋ｋを計算してもよい。
【００５０】
ステップＳ１０８において、署名生成部１２１は、ステップＳ１０７で生成した電子署名を出力する。
【００５１】
ステップＳ１０７では、結果的に、演算Ｃ’として（ｒ×ｎ＋ｅ）×ｄ＋ｋの計算が行われる。演算Ｃのようにｅ×ｄの計算が出現しないため、差分電力解析により、ｄを求められることはない。したがって、差分電力攻撃に対して安全に電子署名を生成することができる。
【００５２】
本例において、署名生成装置１００は、ＥＣ−Ｓｃｈｎｏｒｒ署名アルゴリズムの説明で示したステップ４の（ｅ×ｄ＋ｋ）  ｍｏｄ  ｎの演算を以下のように行っている。
ステップ４−１．乱数ｒを生成する。
ステップ４−２．ｓ１＝ｒ×ｎを計算する。
ステップ４−３．ｓ２＝ｓ１＋ｅを計算する。
ステップ４−４．ｓ３＝（ｓ２×ｄ＋ｋ）  ｍｏｄ  ｎを計算する。
ステップ４−５．ｓ３を（ｅ×ｄ＋ｋ）  ｍｏｄ  ｎの計算値として出力する。
【００５３】
上記計算方法では、ステップ４−４でｅ×ｄの計算の代わりに（ｒ×ｎ＋ｅ）×ｄの計算が行われている。したがって、差分電力攻撃に対して安全に（ｅ×ｄ＋ｋ）  ｍｏｄ  ｎの計算値が得られる。Ｓｃｈｎｏｒｒ署名の演算にも上記同様の計算方法を用いることができる。
【００５４】
以下、本実施の形態の第２適用例について、図３を用いて説明する。本例では、署名生成装置１００が電子署名としてＥＣ−ＤＳＡ署名を生成する。
【００５５】
ステップＳ１０１において、入力部１０１は、公開情報ｎとして楕円曲線上の生成元Ｇの位数ｎを入力する。
【００５６】
本例では、ステップＳ１０２の前に、乱数生成部１０３が、乱数ｋを生成する。ｋはｎ未満の自然数である。
【００５７】
ステップＳ１０２において、入力部１０１は、乱数生成部１０３により生成された乱数ｋと楕円曲線上の生成元Ｇとのスカラー倍算値Ｐを処理装置１５１により計算する。即ち、入力部１０１は、Ｐ＝ｋＧを計算する。そして、入力部１０１は、当該スカラー倍算値Ｐのｘ座標値（即ち、Ｐｘ）を公開情報ｅとして入力する。
【００５８】
ステップＳ１０３において、読取部１０２は、記憶装置１５２から秘密情報ｄとして秘密鍵ｄを読み取る。
【００５９】
ステップＳ１０４において、乱数生成部１０３は、乱数ｋとは別に乱数ｒを生成する。ｒは自然数である。
【００６０】
ステップＳ１０５において、第１計算部１１１は、乱数生成部１０３により生成された乱数ｒと入力部１０１により入力された位数ｎとの乗算Ｍ１を処理装置１５１により行う。即ち、第１計算部１１１は、ｓ１＝ｒ×ｎを計算する。
【００６１】
ステップＳ１０６において、第２計算部１１２は、第１計算部１１１により行われた乗算Ｍ１の結果ｓ１と入力部１０１により入力されたＰｘとの加算Ｍ２を処理装置１５１により行う。即ち、第２計算部１１２は、ｓ２＝ｓ１＋Ｐｘを計算する。
【００６２】
ステップＳ１０７において、署名生成部１２１は、第２計算部１１２により行われた加算Ｍ２の結果ｓ２と読取部１０２により読み取られた秘密鍵ｄとの乗算Ｍ３を処理装置１５１により行う。署名生成部１２１は、当該乗算Ｍ３の結果と電子署名が付与される対象となるメッセージＭのハッシュ値ｈ（Ｍ）との加算Ｍ４を処理装置１５１により行う。そして、署名生成部１２１は、当該加算Ｍ４の結果と乱数生成部１０３により生成された乱数ｋの逆数ｋ−１との乗算Ｍ５を処理装置１５１により行う。当該乗算Ｍ５の結果が演算Ｃ’の結果ｔ’となる。即ち、署名生成部１２１は、ｔ’＝ｋ−１（ｓ２×ｄ＋ｈ（Ｍ））を計算する。次に、署名生成部１２１は、演算Ｃ’の結果ｔ’に対して入力部１０１により入力された位数ｎを法とする剰余を処理装置１５１により計算する。即ち、署名生成部１２１は、ｓ３＝ｔ’  ｍｏｄ  ｎを計算する。ｓ３とＰｘとの組み合わせが電子署名となる。即ち、（Ｐｘ，ｓ３）がＭの電子署名となる。
【００６３】
ステップＳ１０７で、署名生成部１２１は、乗算Ｍ３の結果を加算Ｍ４に用いる前に、乗算Ｍ３の結果に対して位数ｎを法とする剰余を計算し、その剰余で乗算Ｍ３の結果を置き換えてもよい。同様に、署名生成部１２１は、加算Ｍ４の結果を乗算Ｍ５に用いる前に、加算Ｍ４の結果に対して位数ｎを法とする剰余を計算し、その剰余で加算Ｍ４の結果を置き換えてもよい。即ち、署名生成部１２１は、ｔ’＝ｋ−１（ｓ２×ｄ＋ｈ（Ｍ））の代わりに、ｔ’＝ｋ−１（（ｓ２×ｄ  ｍｏｄ  ｎ）＋ｈ（Ｍ））、ｔ’＝ｋ−１（（ｓ２×ｄ＋ｈ（Ｍ））  ｍｏｄ  ｎ）、又は、ｔ’＝ｋ−１（（（ｓ２×ｄ  ｍｏｄ  ｎ）＋ｈ（Ｍ））  ｍｏｄ  ｎ）を計算してもよい。
【００６４】
ステップＳ１０８において、署名生成部１２１は、ステップＳ１０７で生成した電子署名を出力する。
【００６５】
ステップＳ１０７では、結果的に、演算Ｃ’としてｋ−１（（ｒ×ｎ＋Ｐｘ）×ｄ＋ｈ（Ｍ））の計算が行われる。演算ＣのようにＰｘ×ｄの計算が出現しないため、差分電力解析により、ｄを求められることはない。したがって、差分電力攻撃に対して安全に電子署名を生成することができる。
【００６６】
本例において、署名生成装置１００は、ＥＣ−ＤＳＡの説明で示したステップ４のｋ−１（Ｐｘ×ｄ＋ｈ（Ｍ））  ｍｏｄ  ｎの演算を以下のように行っている。
ステップ４−１．乱数ｒを生成する。
ステップ４−２．ｓ１＝ｒ×ｎを計算する。
ステップ４−３．ｓ２＝ｓ１＋Ｐｘを計算する。
ステップ４−４．ｓ３＝ｋ−１（ｓ２×ｄ＋ｈ（Ｍ））  ｍｏｄ  ｎを計算する。
ステップ４−５．ｓ３をｋ−１（Ｐｘ×ｄ＋ｈ（Ｍ））  ｍｏｄ  ｎの計算値として出力する。
【００６７】
上記計算方法では、ステップ４−４でＰｘ×ｄの計算の代わりに（ｒ×ｎ＋Ｐｘ）×ｄの計算が行われている。したがって、差分電力攻撃に対して安全にｋ−１（Ｐｘ×ｄ＋ｈ（Ｍ））  ｍｏｄ  ｎの計算値が得られる。ＤＳＡ署名の演算にも上記同様の計算方法を用いることができる。
【００６８】
実施の形態２．
本実施の形態について、主に実施の形態１との差異を説明する。
【００６９】
本実施の形態に係る署名生成装置１００の構成は、図１に示した実施の形態１のものと同様である。
【００７０】
図４は、署名生成装置１００の動作（即ち、本実施の形態に係る署名生成方法）を示すフローチャートである。
【００７１】
本実施の形態では、図３に示したステップＳ１０４が省略され、ステップＳ１０５がステップＳ１０５’に置き換えられている。ステップＳ１０５’において、第１計算部１１１は、演算Ｃ’で用いられる情報（例えば、公開情報ｅ）を生成する過程で計算される値を新たな秘密情報ｒとして用いる。
【００７２】
本実施の形態によれば、実施の形態１のステップＳ１０４のように、乱数ｒを生成する処理が不要となるため、処理時間を削減できる。
【００７３】
以下、本実施の形態の第１適用例について、図４を用いて説明する。本例では、実施の形態１の第１適用例と同様に、署名生成装置１００が電子署名としてＥＣ−Ｓｃｈｎｏｒｒ署名を生成する。
【００７４】
ステップＳ１０１〜Ｓ１０３は、実施の形態１の第１適用例のものと同様である。
【００７５】
ステップＳ１０５’において、第１計算部１１１は、入力部１０１により計算されたスカラー倍算値Ｐのｘ座標値（即ち、Ｐｘ）を新たな秘密情報ｒとして用いる。即ち、第１計算部１１１は、Ｐｘと入力部１０１により入力された位数ｎとの乗算Ｍ１を処理装置１５１により行う。
【００７６】
ステップＳ１０５’で、第１計算部１１１は、Ｐｘの一部のみを新たな秘密情報ｒとして用いてもよい。例えば、Ｐｘが１６０ビットのデータであれば、第１計算部１１１は、Ｐｘの上位１００ビットのデータのみ、下位２０ビットのデータのみ、又は、その他の任意ビットのデータのみを新たな秘密情報ｒとして用いてもよい。あるいは、第１計算部１１１は、入力部１０１により計算されたスカラー倍算値Ｐのｙ座標値（即ち、Ｐｙ）を新たな秘密情報ｒとして用いてもよい。第１計算部１１１は、Ｐｙの一部のみを新たな秘密情報ｒとして用いてもよい。第１計算部１１１は、ＰｘとＰｙとの両方を新たな秘密情報ｒとして用いてもよい。即ち、第１計算部１１１は、ＰｘとＰｙとのいずれかの少なくとも一部を新たな秘密情報ｒとして用いてもよい。あるいは、第１計算部１１１は、入力部１０１によりスカラー倍算値Ｐが計算される過程で得られる値を新たな秘密情報ｒとして用いてもよい。例えば、ステップＳ１０２で入力部１０１が楕円曲線上の生成元Ｇを加える演算をｋ回のループとして行うのであれば、第１計算部１１１は、ｊ回目（ｊ＜ｋ）のループで得られた任意の計算値を新たな秘密情報ｒとして用いてもよい。
【００７７】
ステップＳ１０６〜Ｓ１０８は、実施の形態１の第１適用例のものと同様である。
【００７８】
上記のように、本例では、実施の形態１の第１適用例における乱数ｒの代わりに、Ｐ又はＰの一部を用いている。ＰはＧの乱数ｋ倍なので、乱数とみなすことができる。Ｓｃｈｎｏｒｒ署名の演算にも上記同様の方法を用いることができる。
【００７９】
以下、本実施の形態の第２適用例について、図４を用いて説明する。本例では、実施の形態１の第２適用例と同様に、署名生成装置１００が電子署名としてＥＣ−ＤＳＡ署名を生成する。
【００８０】
ステップＳ１０１〜Ｓ１０３は、実施の形態１の第２適用例のものと同様である。
【００８１】
ステップＳ１０５’は、本実施の形態の第１適用例のものと同様である。
【００８２】
ステップＳ１０６〜Ｓ１０８は、実施の形態１の第２適用例のものと同様である。
【００８３】
上記のように、本例では、第１適用例と同様に、実施の形態１の第２適用例における乱数ｒの代わりに、Ｐ又はＰの一部を用いている。第１適用例と同様に、ＰはＧの乱数ｋ倍なので、乱数とみなすことができる。ＤＳＡ署名の演算にも上記同様の方法を用いることができる。
【符号の説明】
【００８４】
１００  署名生成装置、１０１  入力部、１０２  読取部、１０３  乱数生成部、１１１  第１計算部、１１２  第２計算部、１２１  署名生成部、１５１  処理装置、１５２  記憶装置、１５３  入力装置、１５４  出力装置、９０１  ＬＣＤ、９０２  キーボード、９０３  マウス、９０４  ＦＤＤ、９０５  ＣＤＤ、９０６  プリンタ、９１１  ＣＰＵ、９１２  バス、９１３  ＲＯＭ、９１４  ＲＡＭ、９１５  通信ボード、９２０  ＨＤＤ、９２１  オペレーティングシステム、９２２  ウィンドウシステム、９２３  プログラム群、９２４  ファイル群。
【図１】
2012086076.tif 000003
【図２】
2012086076.tif 000004
【図３】
2012086076.tif 000005
【図４】
2012086076.tif 000006
【国際調査報告】
2012086076.tif 000007
2012086076.tif 000008