JPH10222065A - 冪乗剰余演算方法及び装置 - Google Patents
冪乗剰余演算方法及び装置Info
- Publication number
- JPH10222065A JPH10222065A JP9020607A JP2060797A JPH10222065A JP H10222065 A JPH10222065 A JP H10222065A JP 9020607 A JP9020607 A JP 9020607A JP 2060797 A JP2060797 A JP 2060797A JP H10222065 A JPH10222065 A JP H10222065A
- Authority
- JP
- Japan
- Prior art keywords
- initial value
- random number
- modular exponentiation
- delay time
- unit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Abstract
(57)【要約】
【課題】 専用プロセッサを利用した冪乗演算を利用し
た公開鍵暗号の攻撃方法として、同じパラメータを利用
して秘密鍵を求めるようなタイミングアタックに対する
防御が可能な冪乗剰余演算方法及び装置を提供する。 【解決手段】 本発明は、冪乗剰余演算毎に伝搬遅延に
よるクリティカルパスの遅延時間を変化させる。そのた
めに、冪乗剰余の演算時間を変化させるための遅延情報
を入力し、入力された遅延時間に基づいて遅延時間を決
定し、決定された遅延時間に応じて演算に適用する遅延
時間を変化させて冪乗剰余演算を行う。
た公開鍵暗号の攻撃方法として、同じパラメータを利用
して秘密鍵を求めるようなタイミングアタックに対する
防御が可能な冪乗剰余演算方法及び装置を提供する。 【解決手段】 本発明は、冪乗剰余演算毎に伝搬遅延に
よるクリティカルパスの遅延時間を変化させる。そのた
めに、冪乗剰余の演算時間を変化させるための遅延情報
を入力し、入力された遅延時間に基づいて遅延時間を決
定し、決定された遅延時間に応じて演算に適用する遅延
時間を変化させて冪乗剰余演算を行う。
Description
【０００１】
【発明の属する技術分野】本発明は、冪乗剰余演算方法
及び装置に係り、特に、ＲＳＡ暗号等の公開鍵暗号の基
本演算である冪乗剰余演算において、演算時間から不正
に秘密鍵を推測されることを防止するための冪乗剰余演
算方法及び装置に関する。
及び装置に係り、特に、ＲＳＡ暗号等の公開鍵暗号の基
本演算である冪乗剰余演算において、演算時間から不正
に秘密鍵を推測されることを防止するための冪乗剰余演
算方法及び装置に関する。
【０００２】
【従来の技術】冪乗剰余演算は、公開鍵暗号の基本演算
として非常によく利用されるようになっている。ＲＳＡ
暗号を例にすると、復号演算及び署名演算をする場合、
冪指数を秘密とした冪乗剰余演算を行う。
として非常によく利用されるようになっている。ＲＳＡ
暗号を例にすると、復号演算及び署名演算をする場合、
冪指数を秘密とした冪乗剰余演算を行う。
【０００３】従来、公開鍵暗号の殆どが冪乗剰余演算を
利用している。冪乗剰余演算は、 ａb mod ｃ と表すことができる。署名演算あるいは、復号演算に関
して少なくとも１つのパラメータは秘密である。
利用している。冪乗剰余演算は、 ａb mod ｃ と表すことができる。署名演算あるいは、復号演算に関
して少なくとも１つのパラメータは秘密である。
【０００４】
【発明が解決しようとする課題】しかしながら、３つの
パラメータが全く同じ場合、当然同一の結果が得られ
る。また、専用プロセッサを用いて冪乗剰余演算を行う
場合には、動作周波数等の環境を一定にすれば、必ず同
一の演算結果が得られる。この特徴を利用して秘密鍵を
求めることができるという指摘が、“Paul C.Kohcer,"T
iming Attacks on Inplementations of Diffie-Hellma
n, RSA, DSS, and Other Systems", Advancesin Crypto
logy:Proceedings of Crypto 96,Plenum Press, 1996,p
p.104-113 ”で報告されている。この方法（タイミング
アタックと呼ぶことにする）は、多少時間がかかり容易
ではないが、数学的な特徴を利用して、秘密鍵を導出し
ようとしたり、秘密鍵の全数検索をしたりする方法より
は、はるかに簡単である。この方法は、より正確に時間
を計測できる環境である程、危険性が増す。また、並列
ジョブが少ないほど危険性が高い。
パラメータが全く同じ場合、当然同一の結果が得られ
る。また、専用プロセッサを用いて冪乗剰余演算を行う
場合には、動作周波数等の環境を一定にすれば、必ず同
一の演算結果が得られる。この特徴を利用して秘密鍵を
求めることができるという指摘が、“Paul C.Kohcer,"T
iming Attacks on Inplementations of Diffie-Hellma
n, RSA, DSS, and Other Systems", Advancesin Crypto
logy:Proceedings of Crypto 96,Plenum Press, 1996,p
p.104-113 ”で報告されている。この方法（タイミング
アタックと呼ぶことにする）は、多少時間がかかり容易
ではないが、数学的な特徴を利用して、秘密鍵を導出し
ようとしたり、秘密鍵の全数検索をしたりする方法より
は、はるかに簡単である。この方法は、より正確に時間
を計測できる環境である程、危険性が増す。また、並列
ジョブが少ないほど危険性が高い。
【０００５】このように、冪乗剰余演算等を利用する秘
密鍵演算は、全て同じパラメータを利用すれば、演算量
は同じである。この特徴を悪用され、秘密鍵を求めるこ
とができる場合がある。本発明は、上記の点に鑑みなさ
れたもので、専用プロセッサにおける冪乗演算を利用し
た公開鍵暗号の攻撃方法として、同じパラメータを利用
して秘密鍵を求めるようなタイミングアタックに対する
防御が可能な冪乗剰余演算方法及び装置を提供すること
を目的とする。
密鍵演算は、全て同じパラメータを利用すれば、演算量
は同じである。この特徴を悪用され、秘密鍵を求めるこ
とができる場合がある。本発明は、上記の点に鑑みなさ
れたもので、専用プロセッサにおける冪乗演算を利用し
た公開鍵暗号の攻撃方法として、同じパラメータを利用
して秘密鍵を求めるようなタイミングアタックに対する
防御が可能な冪乗剰余演算方法及び装置を提供すること
を目的とする。
【０００６】
【課題を解決するための手段】図１は、本発明の原理を
説明するための図である。本発明は、公開鍵暗号の基本
演算である冪乗剰余演算方法において、冪乗剰余演算毎
に伝搬遅延によるクリティカルパスの遅延時間を変化さ
せる。
説明するための図である。本発明は、公開鍵暗号の基本
演算である冪乗剰余演算方法において、冪乗剰余演算毎
に伝搬遅延によるクリティカルパスの遅延時間を変化さ
せる。
【０００７】本発明は、冪乗剰余の演算時間を変化させ
るための遅延情報を入力し（ステップ１）、入力された
遅延時間に基づいて遅延時間を決定し（ステップ２）、
決定された遅延時間に応じて、演算に適用する遅延時間
を変化させて冪乗剰余演算を行う（ステップ３）。
るための遅延情報を入力し（ステップ１）、入力された
遅延時間に基づいて遅延時間を決定し（ステップ２）、
決定された遅延時間に応じて、演算に適用する遅延時間
を変化させて冪乗剰余演算を行う（ステップ３）。
【０００８】また、上記のステップ１において、乱数を
生成するために必要な初期値を生成し、初期値に基づい
て乱数を生成し、生成した乱数から遅延時間を生成す
る。また、本発明は、乱数生成に用いる初期値を生成す
る際に、複数の初期値を生成し、生成された複数の初期
値から乱数を生成する。
生成するために必要な初期値を生成し、初期値に基づい
て乱数を生成し、生成した乱数から遅延時間を生成す
る。また、本発明は、乱数生成に用いる初期値を生成す
る際に、複数の初期値を生成し、生成された複数の初期
値から乱数を生成する。
【０００９】また、本発明は、乱数生成に用いる初期値
を生成する際に、冪乗剰余演算中に初期値を更新する。
また、本発明は、初期値を更新する際に、冪乗剰余演算
中の途中結果の一部または、全部を用いて、以降の乱数
の初期値を更新する。
を生成する際に、冪乗剰余演算中に初期値を更新する。
また、本発明は、初期値を更新する際に、冪乗剰余演算
中の途中結果の一部または、全部を用いて、以降の乱数
の初期値を更新する。
【００１０】図２は、本発明の原理構成図である。本発
明は、冪乗剰余演算を実行する冪乗剰余演算装置であっ
て、冪乗剰余の演算時間を変化させるための情報を入力
する変化情報入力手段１０と、変化情報入力手段１０に
より入力された変化情報に基づいて遅延時間を決定する
遅延時間決定手段２０と、遅延時間決定手段２０により
決定された遅延時間に基づいて冪乗剰余演算を行う冪乗
剰余演算手段３０とを有する。
明は、冪乗剰余演算を実行する冪乗剰余演算装置であっ
て、冪乗剰余の演算時間を変化させるための情報を入力
する変化情報入力手段１０と、変化情報入力手段１０に
より入力された変化情報に基づいて遅延時間を決定する
遅延時間決定手段２０と、遅延時間決定手段２０により
決定された遅延時間に基づいて冪乗剰余演算を行う冪乗
剰余演算手段３０とを有する。
【００１１】また、上記の変化情報入力手段１０は、乱
数を生成するために必要な初期値を入力する乱数初期値
入力手段１１と、乱数初期値入力手段により入力された
初期値に基づいて乱数を生成し、変化情報として遅延時
間決定手段に入力する乱数生成手段１２とを含み、遅延
時間決定手段２０は、乱数生成手段１２により入力され
た乱数に基づいて遅延時間を決定する手段を含む。
数を生成するために必要な初期値を入力する乱数初期値
入力手段１１と、乱数初期値入力手段により入力された
初期値に基づいて乱数を生成し、変化情報として遅延時
間決定手段に入力する乱数生成手段１２とを含み、遅延
時間決定手段２０は、乱数生成手段１２により入力され
た乱数に基づいて遅延時間を決定する手段を含む。
【００１２】また、上記の乱数初期値入力手段１１は、
乱数を生成するために必要な初期値を外部から入力する
第１の乱数初期値入力手段を含む。また、上記の乱数初
期値入力手段１１は、乱数を生成するための必要な初期
値を装置内部で生成する第２の乱数初期値入力手段を含
む。
乱数を生成するために必要な初期値を外部から入力する
第１の乱数初期値入力手段を含む。また、上記の乱数初
期値入力手段１１は、乱数を生成するための必要な初期
値を装置内部で生成する第２の乱数初期値入力手段を含
む。
【００１３】また、上記の乱数初期値入力手段１１は、
第１の乱数初期値入力手段により入力された初期値と、
第２の乱数初期値入力手段により入力された初期値とを
合成した値を乱数生成手段への入力とする初期値合成手
段を含む。また、上記の遅延時間決定手段２０は、冪乗
剰余演算手段３０の実行中に遅延時間を更新する遅延時
間更新手段を含む。
第１の乱数初期値入力手段により入力された初期値と、
第２の乱数初期値入力手段により入力された初期値とを
合成した値を乱数生成手段への入力とする初期値合成手
段を含む。また、上記の遅延時間決定手段２０は、冪乗
剰余演算手段３０の実行中に遅延時間を更新する遅延時
間更新手段を含む。
【００１４】また、上記の変化情報入力手段１０は、冪
乗剰余演算手段３０の実行中の演算結果を用いて、以降
の乱数生成手段１２の初期値を更新する演算結果循環型
初期値更新手段を含む。図３に、送信者端末が署名を演
算し、その結果を受信者に向けて送信する場合の基本的
な例を示す。
乗剰余演算手段３０の実行中の演算結果を用いて、以降
の乱数生成手段１２の初期値を更新する演算結果循環型
初期値更新手段を含む。図３に、送信者端末が署名を演
算し、その結果を受信者に向けて送信する場合の基本的
な例を示す。
【００１５】盗聴者１０１は、通信をモニタして解析
し、秘密鍵を推測しようとする。最も解析しやすい（危
険性の高い）順は、送信者端末の付近１０２、通信網１
０３、受信者端末の付近１０４である。この最大の理由
は、送信者の送信者端末１０２に近いほど、通信等に関
わる処理の関与が少ないからである。また、モニタしや
すいところは、公衆網（通信網）の部分である。
し、秘密鍵を推測しようとする。最も解析しやすい（危
険性の高い）順は、送信者端末の付近１０２、通信網１
０３、受信者端末の付近１０４である。この最大の理由
は、送信者の送信者端末１０２に近いほど、通信等に関
わる処理の関与が少ないからである。また、モニタしや
すいところは、公衆網（通信網）の部分である。
【００１６】最も解析しやすい場合の例を考える。即
ち、送信者端末１０２に冪乗剰余演算専用のプロセッサ
が搭載されていて、そのプロセッサの演算時間、公開鍵
等の公開情報、演算結果を得ることができると仮定す
る。それらの結果を複数蓄積し、演算に用いた秘密鍵を
推測することが目的となる。
ち、送信者端末１０２に冪乗剰余演算専用のプロセッサ
が搭載されていて、そのプロセッサの演算時間、公開鍵
等の公開情報、演算結果を得ることができると仮定す
る。それらの結果を複数蓄積し、演算に用いた秘密鍵を
推測することが目的となる。
【００１７】上記の環境が最も解析し易い最大の原因
は、同一入力であれば、同じ演算時間になり、専用プロ
セッサであるため他の処理に殆ど影響がないためであ
る。そこで、本発明は、専用プロセッサを用いた場合、
同一入力でも毎回異なる演算時間になるように、不確定
の遅延時間を持つ回路をプロセッサ内に設けるか、外部
からランダムな遅延時間を与えることにより、タイミン
グアタックに対する防御として大変有効である。
は、同一入力であれば、同じ演算時間になり、専用プロ
セッサであるため他の処理に殆ど影響がないためであ
る。そこで、本発明は、専用プロセッサを用いた場合、
同一入力でも毎回異なる演算時間になるように、不確定
の遅延時間を持つ回路をプロセッサ内に設けるか、外部
からランダムな遅延時間を与えることにより、タイミン
グアタックに対する防御として大変有効である。
【００１８】
【発明の実施の形態】図４は、本発明の冪乗剰余演算装
置の構成を示す。同図に示す冪乗剰余演算装置は、遅延
時間調整部２０２、遅延時間決定部２０３を有する冪乗
剰余演算部２０１、乱数発生部２０４、初期値合成部２
０５、初期値発生部２０７、演算結果フィードバック部
２０８から構成され、初期値合成部２０５には、外部初
期値入力部２０６が冪乗剰余演算装置の外部から接続さ
れる。
置の構成を示す。同図に示す冪乗剰余演算装置は、遅延
時間調整部２０２、遅延時間決定部２０３を有する冪乗
剰余演算部２０１、乱数発生部２０４、初期値合成部２
０５、初期値発生部２０７、演算結果フィードバック部
２０８から構成され、初期値合成部２０５には、外部初
期値入力部２０６が冪乗剰余演算装置の外部から接続さ
れる。
【００１９】通常の冪乗剰余演算部の多くのハードウェ
アの回路には、伝搬遅延によるクリティカルパスの遅延
時間を調整する回路があり、通常の設計では、遅延時間
調整回路を必要最小限にする。本発明では、この遅延時
間調整回路の遅延時間を冪乗演算毎に変化させることに
より、同一の値を用いた冪乗演算であっても演算時間が
異なるように設計する。
アの回路には、伝搬遅延によるクリティカルパスの遅延
時間を調整する回路があり、通常の設計では、遅延時間
調整回路を必要最小限にする。本発明では、この遅延時
間調整回路の遅延時間を冪乗演算毎に変化させることに
より、同一の値を用いた冪乗演算であっても演算時間が
異なるように設計する。
【００２０】冪乗剰余演算部２０１は、遅延時間調整部
２０２と遅延時間決定部２０３を有することにより、必
要最小限の遅延時間を遅延時間決定部２０３で決定した
遅延時間を遅延時間調整部２０２に与えて、演算時間を
変化させる。乱数発生部２０４は、遅延時間決定部２０
３で決定される遅延時間がランダムとなるように乱数を
発生させる。乱数発生部２０４で発生した乱数を遅延時
間決定部２０３に与える。その乱数発生部２０４で発生
する乱数は、初期値の入力によって決定される。その初
期値の生成方法として以下の３つに大別できる。
２０２と遅延時間決定部２０３を有することにより、必
要最小限の遅延時間を遅延時間決定部２０３で決定した
遅延時間を遅延時間調整部２０２に与えて、演算時間を
変化させる。乱数発生部２０４は、遅延時間決定部２０
３で決定される遅延時間がランダムとなるように乱数を
発生させる。乱数発生部２０４で発生した乱数を遅延時
間決定部２０３に与える。その乱数発生部２０４で発生
する乱数は、初期値の入力によって決定される。その初
期値の生成方法として以下の３つに大別できる。
【００２１】 冪乗剰余演算装置の外部に接続される
外部初期値入力部２０６から入力された値により生成す
る。 冪乗剰余演算装置内部の初期値発生部２０７で発生
した初期値により生成する。
外部初期値入力部２０６から入力された値により生成す
る。 冪乗剰余演算装置内部の初期値発生部２０７で発生
した初期値により生成する。
【００２２】 冪乗剰余演算装置内部の演算結果フィ
ードバック部２０８で以前の演算結果に基づいて生成す
る。初期値合成部２０５は、初期値の生成方法として、
外部初期値入力部２０６からの初期値、初期発生部２０
７で生成された初期値、演算結果フィードバック部２０
８からフィードバックされた演算結果を初期値とする
の、いずれか単独で用いてもよいが、それぞれの初期値
を合成する初期値合成部２０５を利用して、上記の、
、の方法を組み合わせることにより、より質のよい
乱数を生成することが可能となる。
ードバック部２０８で以前の演算結果に基づいて生成す
る。初期値合成部２０５は、初期値の生成方法として、
外部初期値入力部２０６からの初期値、初期発生部２０
７で生成された初期値、演算結果フィードバック部２０
８からフィードバックされた演算結果を初期値とする
の、いずれか単独で用いてもよいが、それぞれの初期値
を合成する初期値合成部２０５を利用して、上記の、
、の方法を組み合わせることにより、より質のよい
乱数を生成することが可能となる。
【００２３】
【実施例】以下に、本発明の実施例を図面と共に説明す
る。図５は、本発明の一実施例の冪乗剰余演算方法の一
連の動作を示すフローチャートである。
る。図５は、本発明の一実施例の冪乗剰余演算方法の一
連の動作を示すフローチャートである。
【００２４】図４の構成に基づいて図５のフローチャー
トを説明する。ステップ１０１） まず、初期値合成部
２０５は、外部初期値入力部２０６からの外部初期値の
入力があるかを判定する。外部入力がある場合には、ス
テップ１０２に移行する。外部初期値の入力がない場合
には、ステップ１０３に移行する。
トを説明する。ステップ１０１） まず、初期値合成部
２０５は、外部初期値入力部２０６からの外部初期値の
入力があるかを判定する。外部入力がある場合には、ス
テップ１０２に移行する。外部初期値の入力がない場合
には、ステップ１０３に移行する。
【００２５】ステップ１０２） 外部入力がある場合に
は、外部初期値入力部２０６から乱数発生のための初期
値が入力され、初期値合成部２０５は当該初期値を保持
する。ステップ１０３） 初期値合成部２０５は、初期
値発生部２０７からの内部初期値の生成があるかを判定
し、ある場合には、ステップ１０４に移行し、内部初期
値の生成がない場合には、ステップ１０５に移行する。
は、外部初期値入力部２０６から乱数発生のための初期
値が入力され、初期値合成部２０５は当該初期値を保持
する。ステップ１０３） 初期値合成部２０５は、初期
値発生部２０７からの内部初期値の生成があるかを判定
し、ある場合には、ステップ１０４に移行し、内部初期
値の生成がない場合には、ステップ１０５に移行する。
【００２６】ステップ１０４） 初期値発生部２０７か
らの内部初期値が生成された場合には、初期値合成部２
０５は、当該内部初期値を保持する。ステップ１０５）
冪乗剰余演算部２０１における演算結果を初期値とし
てフィードバックするかどうかを判定し、演算結果を初
期値としてフィードバックする場合は、ステップ１０６
に移行し、フィードバックしない場合には、ステップ１
０７に移行する。
らの内部初期値が生成された場合には、初期値合成部２
０５は、当該内部初期値を保持する。ステップ１０５）
冪乗剰余演算部２０１における演算結果を初期値とし
てフィードバックするかどうかを判定し、演算結果を初
期値としてフィードバックする場合は、ステップ１０６
に移行し、フィードバックしない場合には、ステップ１
０７に移行する。
【００２７】ステップ１０６） 演算結果をフィードバ
ックする場合には、フィードバック部２０８において、
演算結果を初期値としてフィードバックして、初期値合
成部２０５にフィードバックする。ステップ１０７）
初期値合成部２０５は、ステップ１０２、ステップ１０
４、ステップ１０６のいずれか、または、全てにおいて
入力された初期値を合成する。合成の方法は、本発明で
は特に限定しないが、次の乱数生成の初期値（シード）
として使用可能な値である必要がある。初期値合成部２
０５は、合成した初期値を乱数発生部２０４に転送す
る。
ックする場合には、フィードバック部２０８において、
演算結果を初期値としてフィードバックして、初期値合
成部２０５にフィードバックする。ステップ１０７）
初期値合成部２０５は、ステップ１０２、ステップ１０
４、ステップ１０６のいずれか、または、全てにおいて
入力された初期値を合成する。合成の方法は、本発明で
は特に限定しないが、次の乱数生成の初期値（シード）
として使用可能な値である必要がある。初期値合成部２
０５は、合成した初期値を乱数発生部２０４に転送す
る。
【００２８】ステップ１０８） 乱数発生部２０４は、
初期値合成部２０５から渡された初期値を用いて乱数を
生成し、冪乗剰余演算部２０１の遅延時間決定部２０３
に転送する。ステップ１０９） 冪乗剰余演算部２０１
の遅延時間決定部２０３は、取得した乱数から遅延時間
を決定し、遅延時間調整部２０２では、決定された遅延
時間に回路設計から決まる最低限必要な遅延時間を加
え、これを最終的な遅延時間とする。
初期値合成部２０５から渡された初期値を用いて乱数を
生成し、冪乗剰余演算部２０１の遅延時間決定部２０３
に転送する。ステップ１０９） 冪乗剰余演算部２０１
の遅延時間決定部２０３は、取得した乱数から遅延時間
を決定し、遅延時間調整部２０２では、決定された遅延
時間に回路設計から決まる最低限必要な遅延時間を加
え、これを最終的な遅延時間とする。
【００２９】なお、上記の一連の処理において、初期値
合成部２０５において、外部初期値入力部２０６、装置
内部の初期値発生部２０７または、演算結果フィードバ
ック部２０８から入力される値を初期値としているが、
初期値合成部２０５では、予め１つの初期値入力のみを
用いるようにしてもよいし、入力された全ての初期値を
用いるようにしてもよい。これらの選択を所定の周期で
変更する等の方法も考えられる。また、外部初期値入力
部２０６や、初期値発生部２０７または、演算結果フィ
ードバック部２０８をランダムに起動させることも可能
である。
合成部２０５において、外部初期値入力部２０６、装置
内部の初期値発生部２０７または、演算結果フィードバ
ック部２０８から入力される値を初期値としているが、
初期値合成部２０５では、予め１つの初期値入力のみを
用いるようにしてもよいし、入力された全ての初期値を
用いるようにしてもよい。これらの選択を所定の周期で
変更する等の方法も考えられる。また、外部初期値入力
部２０６や、初期値発生部２０７または、演算結果フィ
ードバック部２０８をランダムに起動させることも可能
である。
【００３０】上記の実施例に示したように、秘密鍵演算
である冪乗剰余演算において、全て同じパラメタを使用
しても、遅延時間を冪乗剰余演算毎に変化させることに
より、仮に、正確に演算時間を計測されたとしても秘密
鍵を導出することは困難である。
である冪乗剰余演算において、全て同じパラメタを使用
しても、遅延時間を冪乗剰余演算毎に変化させることに
より、仮に、正確に演算時間を計測されたとしても秘密
鍵を導出することは困難である。
【００３１】なお、本発明は、上記の実施例に限定され
ることなく、特許請求の範囲内において、冪乗剰余演算
毎に遅延時間を変化させる方法であればよい。
ることなく、特許請求の範囲内において、冪乗剰余演算
毎に遅延時間を変化させる方法であればよい。
【００３２】
【発明の効果】上述のように、本発明の冪乗剰余演算方
法及び装置によれば、冪乗剰余演算を利用した公開鍵暗
号の攻撃方法として、危険性が高かったタイミングアタ
ックに対する防御に有効である。特に、他の処理の影響
を殆ど受けることがない、専用プロセスを利用した場合
に効果的である。
法及び装置によれば、冪乗剰余演算を利用した公開鍵暗
号の攻撃方法として、危険性が高かったタイミングアタ
ックに対する防御に有効である。特に、他の処理の影響
を殆ど受けることがない、専用プロセスを利用した場合
に効果的である。
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】タイミングアタックが起こり得る場合の環境を
示した概念図である。
示した概念図である。
【図４】本発明の冪乗剰余演算装置の内部構成図であ
る。
る。
【図５】本発明の一実施例の冪乗剰余演算方法の一連の
動作を示すフローチャートである。
動作を示すフローチャートである。
１０ 変化情報入力手段 １１ 乱数初期値入力手段 １２ 乱数生成手段 ２０ 遅延時間決定手段 ３０ 冪乗剰余演算手段 １０１ 盗聴者 １０２ 送信者端末 １０３ 通信網 １０４ 受信者端末 ２０１ 冪乗剰余演算部 ２０２ 遅延時間調整部 ２０３ 遅延時間決定部 ２０４ 乱数発生部 ２０５ 初期値合成部 ２０６ 外部初期値入力部 ２０７ 初期値発生部 ２０８ 演算結果フィードバック部
───────────────────────────────────────────────────── フロントページの続き (72)発明者 大山 勝一 東京都武蔵野市吉祥寺本町一丁目14番５号 エヌティティエレクトロニクステクノロ ジー株式会社内
Claims (13)
- 【請求項１】 公開鍵暗号の基本演算である冪乗剰余演
算方法において、 冪乗剰余演算毎に伝搬遅延によるクリティカルパスの遅
延時間を変化させることを特徴とする冪乗演算方法。 - 【請求項２】 冪乗剰余の演算時間を変化させるための
遅延情報を入力し、 入力された前記遅延時間に基づいて遅延時間を決定し、 決定された遅延時間に応じて、演算に適用する遅延時間
を変化させて冪乗剰余演算を行う請求項１記載の冪乗剰
余演算方法。 - 【請求項３】 乱数を生成するために必要な初期値を生
成し、 前記初期値に基づいて乱数を生成し、 生成した前記乱数から前記遅延時間を生成する請求項２
記載の冪乗剰余演算方法。 - 【請求項４】 前記乱数生成に用いる前記初期値を生成
する際に、 複数の初期値を生成し、 生成された前記複数の初期値から乱数を生成する請求項
１、２及び３記載の冪乗剰余演算方法。 - 【請求項５】 前記乱数生成に用いる前記初期値を生成
する際に、 前記冪乗剰余演算中に前記初期値を更新する請求項１、
２、３及び４記載の冪乗剰余演算方法。 - 【請求項６】 前記初期値を更新する際に、 前記冪乗剰余演算中の途中結果の一部または、全部を用
いて、以降の乱数の初期値を更新する請求項５記載の冪
乗剰余演算方法。 - 【請求項７】 冪乗剰余演算を実行する冪乗剰余演算装
置であって、 冪乗剰余の演算時間を変化させるための情報を入力する
変化情報入力手段と、 前記変化情報入力手段により入力された前記変化情報に
基づいて遅延時間を決定する遅延時間決定手段と、 前記遅延時間決定手段により決定された前記遅延時間に
基づいて冪乗剰余演算を行う冪乗剰余演算手段とを有す
ることを特徴とする冪乗剰余演算装置。 - 【請求項８】 前記変化情報入力手段は、 乱数を生成するために必要な初期値を入力する乱数初期
値入力手段と、 前記乱数初期値入力手段により入力された前記初期値に
基づいて乱数を生成し、前記変化情報として前記遅延時
間決定手段に入力する乱数生成手段とを含み、 前記遅延時間決定手段は、 前記乱数生成手段により入力された前記乱数に基づいて
遅延時間を決定する手段を含む請求項７記載の冪乗剰余
演算装置。 - 【請求項９】 前記乱数初期値入力手段は、 乱数を生成するために必要な初期値を外部から入力する
第１の乱数初期値入力手段を含む請求項８記載の冪乗剰
余演算装置。 - 【請求項１０】 前記乱数初期値入力手段は、 乱数を生成するための必要な初期値を装置内部で生成す
る第２の乱数初期値入力手段を含む請求項８記載の冪乗
剰余演算装置。 - 【請求項１１】 前記乱数初期値入力手段は、 前記第１の乱数初期値入力手段により入力された前記初
期値と、前記第２の乱数初期値入力手段により入力され
た前記初期値とを合成した値を前記乱数生成手段への入
力とする初期値合成手段を含む請求項８、９及び１０記
載の冪乗剰余演算装置。 - 【請求項１２】 前記遅延時間決定手段は、 前記冪乗剰余演算手段の実行中に前記遅延時間を更新す
る遅延時間更新手段を含む請求項７記載の冪乗剰余演算
装置。 - 【請求項１３】 前記変化情報入力手段は、 前記冪乗剰余演算手段の実行中の演算結果を用いて、以
降の前記乱数生成手段の初期値を更新する演算結果循環
型初期値更新手段を含む請求項７記載の冪乗剰余演算装
置。
Priority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9020607A JPH10222065A (ja) | 1997-02-03 | 1997-02-03 | 冪乗剰余演算方法及び装置 |
| CA002228493A CA2228493C (en) | 1997-02-03 | 1998-02-02 | Scheme for carrying out modular calculations based on redundant binary calculation |
| US09/017,520 US6175850B1 (en) | 1997-02-03 | 1998-02-02 | Scheme for carrying out modular calculations based on redundant binary calculation |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9020607A JPH10222065A (ja) | 1997-02-03 | 1997-02-03 | 冪乗剰余演算方法及び装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH10222065A true JPH10222065A (ja) | 1998-08-21 |
Family
ID=12031960
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP9020607A Pending JPH10222065A (ja) | 1997-02-03 | 1997-02-03 | 冪乗剰余演算方法及び装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH10222065A (ja) |
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000305453A (ja) * | 1999-04-21 | 2000-11-02 | Nec Corp | 暗号化装置，復号装置，および暗号化・復号装置 |
| JP2001094550A (ja) * | 1999-09-17 | 2001-04-06 | Toshiba Corp | 信号処理装置 |
| JP2002525725A (ja) * | 1998-09-11 | 2002-08-13 | ギーゼッケ ウント デフリエント ゲーエムベーハー | アクセス保護型データ記憶媒体 |
| JP2002528771A (ja) * | 1998-10-28 | 2002-09-03 | サーティコム コーポレーション | 耐パワーシグニチャーアタック暗号法 |
| JP2003502905A (ja) * | 1999-06-11 | 2003-01-21 | ジェネラル・インストルメント・コーポレーション | 暗号演算に対するパワーアタックおよびタイミングアタックへの対策 |
| US7454016B2 (en) | 2002-09-26 | 2008-11-18 | Nec Corporation | Data encryption system and method |
| JP5136416B2 (ja) * | 2006-07-25 | 2013-02-06 | 日本電気株式会社 | 擬似乱数生成装置、ストリーム暗号処理装置及びプログラム |
| US11895230B2 (en) | 2019-01-24 | 2024-02-06 | Nec Corporation | Information processing apparatus, secure computation method, and program |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06342257A (ja) * | 1993-06-02 | 1994-12-13 | Matsushita Electric Ind Co Ltd | 逐次暗号方式 |
| JPH07239837A (ja) * | 1993-12-21 | 1995-09-12 | General Instr Corp Of Delaware | 秘密保護マイクロプロセッサのためのクロック周波数変調 |
-
1997
- 1997-02-03 JP JP9020607A patent/JPH10222065A/ja active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06342257A (ja) * | 1993-06-02 | 1994-12-13 | Matsushita Electric Ind Co Ltd | 逐次暗号方式 |
| JPH07239837A (ja) * | 1993-12-21 | 1995-09-12 | General Instr Corp Of Delaware | 秘密保護マイクロプロセッサのためのクロック周波数変調 |
Cited By (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2002525725A (ja) * | 1998-09-11 | 2002-08-13 | ギーゼッケ ウント デフリエント ゲーエムベーハー | アクセス保護型データ記憶媒体 |
| JP2002528771A (ja) * | 1998-10-28 | 2002-09-03 | サーティコム コーポレーション | 耐パワーシグニチャーアタック暗号法 |
| JP2000305453A (ja) * | 1999-04-21 | 2000-11-02 | Nec Corp | 暗号化装置，復号装置，および暗号化・復号装置 |
| US6970561B1 (en) | 1999-04-21 | 2005-11-29 | Nec Corporation | Encryption and decryption with endurance to cryptanalysis |
| JP2003502905A (ja) * | 1999-06-11 | 2003-01-21 | ジェネラル・インストルメント・コーポレーション | 暗号演算に対するパワーアタックおよびタイミングアタックへの対策 |
| JP2001094550A (ja) * | 1999-09-17 | 2001-04-06 | Toshiba Corp | 信号処理装置 |
| US7454016B2 (en) | 2002-09-26 | 2008-11-18 | Nec Corporation | Data encryption system and method |
| US8306227B2 (en) | 2002-09-26 | 2012-11-06 | Nec Corporation | Data encryption system and method |
| JP5136416B2 (ja) * | 2006-07-25 | 2013-02-06 | 日本電気株式会社 | 擬似乱数生成装置、ストリーム暗号処理装置及びプログラム |
| US11895230B2 (en) | 2019-01-24 | 2024-02-06 | Nec Corporation | Information processing apparatus, secure computation method, and program |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Aviram et al. | {DROWN}: breaking {TLS} using {SSLv2} | |
| US6876745B1 (en) | Method and apparatus for elliptic curve cryptography and recording medium therefore | |
| Potlapally et al. | Optimizing public-key encryption for wireless clients | |
| JP2006340347A (ja) | データに署名するための楕円曲線デジタル署名暗号プロセスを実行する認証システム | |
| Kounavis et al. | Encrypting the internet | |
| EP3698262B1 (en) | Protecting modular inversion operation from external monitoring attacks | |
| JP3507119B2 (ja) | 擬似乱数生成装置とそれを用いた通信装置 | |
| US7191333B1 (en) | Method and apparatus for calculating a multiplicative inverse of an element of a prime field | |
| US6175850B1 (en) | Scheme for carrying out modular calculations based on redundant binary calculation | |
| Braun et al. | Secure and compact full NTRU hardware implementation | |
| JPH10222065A (ja) | 冪乗剰余演算方法及び装置 | |
| Arunachalam et al. | FPGA implementation of time-area-efficient Elliptic Curve Cryptography for entity authentication | |
| Schindler | Optimized timing attacks against public key cryptosystems | |
| Pandey et al. | An RNS implementation of the elliptic curve cryptography for IoT security | |
| Bidmeshki et al. | Hardware-based attacks to compromise the cryptographic security of an election system | |
| Homma et al. | Electromagnetic information leakage for side-channel analysis of cryptographic modules | |
| Kaedi et al. | A new side-channel attack on reduction of RSA-CRT montgomery method based | |
| Potlapally et al. | Algorithm exploration for efficient public-key security processing on wireless handsets | |
| Hamilton et al. | Implementation of a secure TLS coprocessor on an FPGA | |
| Camacho-Ruiz et al. | A Simple Power Analysis of an FPGA implementation of a polynomial multiplier for the NTRU cryptosystem | |
| Beuchat | FPGA implementations of the RC6 block cipher | |
| Ziad et al. | Homomorphic data isolation for hardware trojan protection | |
| JPH0736672A (ja) | 乱数発生器、及びそれを用いた通信システム及びその方法 | |
| Al-Haija et al. | A systematic expository review of Schmidt-Samoa cryptosystem | |
| Ni et al. | Fpga bitstream fault injection attack and countermeasures on the sampling counter in crystals kyber |