(57)【特許請求の範囲】
【請求項１】
秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだ暗号演算装置であって、
前記秘密鍵ｐ及びｑよりも大きい値を有する任意の定数を暗号文Ｘと乗算する定数乗算部と、
前記定数乗算部の乗算結果に対して前記秘密鍵ｐおよびｑによる剰余演算を実行する剰余演算部と、
前記定数に基づいて補正演算を実行する補正演算部とをさらに備え、
前記剰余演算部の剰余演算結果に対して、前記べき乗剰余演算部が中国人剰余定理に基づいたべき乗剰余演算を実行し、そのべき乗剰余演算結果に前記補正演算部が前記補正演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とする暗号演算装置。
【請求項２】
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
前記秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有する定数Ｃを保存する定数記憶部と、
前記定数に基づいて算出される補正値Ｃ-dp、Ｃ-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存する補正値記憶部と、
前記暗号文Ｘと前記定数記憶部に保存されている前記定数Ｃとを乗算する定数乗算部と、
前記乗算による演算結果を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１）に示す剰余演算を実行する剰余演算部と、
【数１】
0004086503.tif 000009
前記剰余演算による演算結果Ｘp’及びＸq’を保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数２）に示す中国人剰余定理に基づいたべき乗剰余演算を行う中国人剰余ＲＳＡ処理部と、
【数２】
0004086503.tif 000010
前記べき乗剰余演算による演算結果Ｙp及びＹqを保存するべき乗剰余演算結果記憶部と、
前記べき乗剰余演算結果記憶部に保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、前記補正値記憶部に保存されている前記補正値Ｃ-dp又はＣ-dqを用いて、（数３）に示すような補正演算を行う補正処理部と、
【数３】
0004086503.tif 000011
前記補正演算による演算結果Ｙp’及びＹq’を保存する補正結果記憶部と、
前記補正結果記憶部に保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、（数４）に従って暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数４】
0004086503.tif 000012
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算装置。
【請求項３】
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
前記秘密鍵ｐ及びｑとの間にＣp＞ｐ、Ｃq＞ｑの関係を有する定数Ｃp及びＣqを保存する定数記憶部と、
前記定数に基づいて算出される補正値Ｃp-dp、Ｃq-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存する補正値記憶部と、
前記暗号文Ｘと前記定数記憶部に保存されている前記定数Ｃp又はＣqとを乗算する定数乗算部と、
前記乗算による演算結果を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数５）に示す剰余演算を実行する剰余演算部と、
【数５】
0004086503.tif 000013
前記剰余演算による演算結果Ｘp’及びＸq’を保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数６）に示す中国人剰余定理に基づいたべき乗剰余演算を行う中国人剰余ＲＳＡ処理部と、
【数６】
0004086503.tif 000014
前記べき乗剰余演算による演算結果Ｙp及びＹqを保存するべき乗剰余演算結果記憶部と、
前記べき乗剰余演算結果記憶部に保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、前記補正値記憶部に保存されている前記補正値Ｃp-dp又はＣq-dqを用いて、（数７）に示すような補正演算を行う補正処理部と、
【数７】
0004086503.tif 000015
前記補正演算による演算結果Ｙp’及びＹq’を保存する補正結果記憶部と、
前記補正結果記憶部に保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、（数８）に従って暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数８】
0004086503.tif 000016
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算装置。
【請求項４】
秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだ暗号演算装置であって、
前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを定数として、暗号文Ｘと乗算するモンゴメリパラメタ乗算部と、
前記モンゴメリパラメタ乗算部の乗算結果に対して前記秘密鍵ｐおよびｑによる剰余演算を実行する剰余演算部とをさらに備え、
前記べき乗剰余演算部が、前記剰余演算部の剰余演算結果に対して、モンゴメリべき乗剰余演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とする暗号演算装置。
【請求項５】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数９）に示すように定義されている場合において、
【数９】
0004086503.tif 000017
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
前記暗号文ＸとモンゴメリパラメタＲとを乗算するモンゴメリパラメタ乗算部と、
前記乗算による演算結果を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１０）に示す剰余演算を実行する剰余演算部と、
【数１０】
0004086503.tif 000018
前記剰余演算による演算結果Ｘp’及びＸq’を保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１１）に示すモンゴメリべき乗剰余演算を実行するモンゴメリべき乗剰余演算部と、
【数１１】
0004086503.tif 000019
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するモンゴメリべき乗剰余演算結果記憶部と、
前記モンゴメリべき乗剰余演算記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数１２）に示すように暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数１２】
0004086503.tif 000020
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算装置。
【請求項６】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１３）に示すように定義されている場合において、
【数１３】
0004086503.tif 000021
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
前記暗号文Ｘと前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqとを乗算するモンゴメリパラメタ乗算部と、
前記乗算による演算結果を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１４）に示す剰余演算を実行する剰余演算部と、
【数１４】
0004086503.tif 000022
前記剰余演算による演算結果Ｘp’及びＸq’を保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１５）に示すモンゴメリべき乗剰余演算を実行するモンゴメリべき乗剰余演算部と、
【数１５】
0004086503.tif 000023
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するモンゴメリべき乗剰余演算結果記憶部と、
前記モンゴメリべき乗剰余演算記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数１６）に示すように暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数１６】
0004086503.tif 000024
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算装置。
【請求項７】
秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだ暗号演算装置であって、
前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタに対して前記秘密鍵ｐ及びｑにより剰余演算を実行するモンゴメリパラメタ剰余演算部と、
前記モンゴメリパラメタ剰余演算部における演算結果を暗号文Ｘと乗算する剰余値乗算部と、
前記剰余値乗算部の乗算結果に対して前記秘密鍵ｐおよびｑによる剰余演算を実行する剰余演算部とを備え、
前記剰余演算部の剰余演算結果に対して前記べき乗剰余演算部がモンゴメリべき乗剰余演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とする暗号演算装置。
【請求項８】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１７）に示すように定義されている場合において、
【数１７】
0004086503.tif 000025
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
モンゴメリパラメタＲについて、（数１８）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を保存するモンゴメリパラメタ剰余演算結果記憶部と、
【数１８】
0004086503.tif 000026
前記モンゴメリパラメタ剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、（数１９）に示すように入力された暗号文Ｘを乗算する剰余値乗算部と、
【数１９】
0004086503.tif 000027
前記乗算による演算結果Ｘp’及びＸq’を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、（数２０）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する剰余演算部と、
【数２０】
0004086503.tif 000028
前記剰余演算による演算結果Ｘp及びＸqを保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、（数２１）に示すモンゴメリべき乗剰余演算を実行するモンゴメリべき乗剰余演算部と、
【数２１】
0004086503.tif 000029
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するモンゴメリべき乗剰余演算結果記憶部と、
前記モンゴメリべき乗剰余演算結果記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数２２）に示すように暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数２２】
0004086503.tif 000030
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算装置。
【請求項９】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２３）に示すように定義されている場合において、
【数２３】
0004086503.tif 000031
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqについて、（数２４）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を保存するモンゴメリパラメタ剰余演算結果記憶部と、
【数２４】
0004086503.tif 000032
前記モンゴメリパラメタ剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、（数２５）に示すように入力された暗号文Ｘを乗算する剰余値乗算部と、
【数２５】
0004086503.tif 000033
前記乗算による演算結果Ｘp’及びＸq’を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、（数２６）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する剰余演算部と、
【数２６】
0004086503.tif 000034
前記剰余演算による演算結果Ｘp及びＸqを保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、（数２７）に示すモンゴメリべき乗剰余演算を実行するモンゴメリべき乗剰余演算部と、
【数２７】
0004086503.tif 000035
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するモンゴメリべき乗剰余演算結果記憶部と、
前記モンゴメリべき乗剰余演算結果記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数２８）に示すように暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数２８】
0004086503.tif 000036
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算装置。
【請求項１０】
秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだ暗号演算装置によって暗号演算を行う方法であって、
前記暗号演算装置の定数乗算部が、前記秘密鍵ｐ及びｑよりも大きい値を有する任意の定数を暗号文Ｘと乗算し、
前記暗号演算装置の剰余演算部が、前記定数乗算部の乗算結果に対して前記秘密鍵ｐおよびｑによる剰余演算を実行し、
前記剰余演算部の剰余演算結果に対して、前記べき乗剰余演算部が中国人剰余定理に基づいたべき乗剰余演算を実行し、
前記暗号演算装置の剰余演算部が、前記べき乗剰余演算部のべき乗剰余演算結果に対して、前記定数に基づいて補正演算を実行することによって、暗号化される前の平文Ｙを算出することを特徴とする暗号演算方法。
【請求項１１】
暗号演算装置によって暗号演算を行う方法であって、
前記暗号演算装置の暗号文入力部が、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力し、
前記暗号演算装置の定数記憶部に、前記秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有する定数Ｃを保存し、
前記暗号演算装置の補正値記憶部に、前記定数に基づいて算出される補正値Ｃ-dp、Ｃ-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存し、
前記暗号演算装置の定数乗算部が、前記暗号文Ｘと前記定数記憶部に保存されている前記定数Ｃとを乗算し、
前記暗号演算装置の乗算結果記憶部に、前記乗算による演算結果を保存し、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、前記暗号演算装置の剰余演算部が、秘密鍵ｐ又はｑを剰余値とした（数２１８）に示す剰余演算を実行し、
【数２１８】
0004086503.tif 000037
前記暗号演算装置の剰余演算結果記憶部に、前記剰余演算による演算結果Ｘp’及びＸq’を保存し、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置の中国人剰余ＲＳＡ処理部が、（数２１９）に示す中国人剰余定理に基づいたべき乗剰余演算を行い、
【数２１９】
0004086503.tif 000038
前記べき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のべき乗剰余演算結果記憶部へ保存し、
前記べき乗剰余演算結果記憶部に保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、前記補正値記憶部に保存されている前記補正値Ｃ-dp又はＣ-dqを用いて、前記暗号演算装置の補正処理部が、（数２２０）に示すような補正演算を行い、
【数２２０】
0004086503.tif 000039
前記補正演算による演算結果Ｙp’及びＹq’を前記暗号演算装置の補正結果記憶部へ保存し、
前記補正結果記憶部に保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、前記暗号演算装置の平文出力部が、（数２２１）に従って暗号化される前の平文Ｙを算出することにより、
【数２２１】
0004086503.tif 000040
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算方法。
【請求項１２】
暗号演算装置によって暗号演算を行う方法であって、
前記暗号演算装置の暗号文入力部が、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力し、
前記暗号演算装置の定数記憶部に、前記秘密鍵ｐ及びｑとの間にＣp＞ｐ、Ｃq＞ｑの関係を有する定数Ｃp及びＣqを保存し、
前記暗号演算装置の補正値記憶部に、前記定数に基づいて算出される補正値Ｃp-dp、Ｃq-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存し、
前記暗号演算装置の定数乗算部が、前記暗号文Ｘと前記定数記憶部に保存されている前記定数Ｃp又はＣqとを乗算し、
前記暗号演算装置の乗算結果記憶部に、前記乗算による演算結果を保存し、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、前記暗号演算装置の剰余演算部が、秘密鍵ｐ又はｑを剰余値とした（数２２２）に示す剰余演算を実行し、
【数２２２】
0004086503.tif 000041
前記剰余演算による演算結果Ｘp’及びＸq’を前記暗号演算装置の剰余演算結果記憶部へ保存し、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置の中国人剰余ＲＳＡ処理部が、（数２２３）に示す中国人剰余定理に基づいたべき乗剰余演算を行い、
【数２２３】
0004086503.tif 000042
前記べき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のべき乗剰余演算結果記憶部へ保存し、
前記べき乗剰余演算結果記憶部に保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、前記補正値記憶部に保存されている前記補正値Ｃp-dp又はＣq-dqを用いて、前記暗号演算装置の補正処理部が、（数２２４）に示すような補正演算を行い、
【数２２４】
0004086503.tif 000043
前記補正演算による演算結果Ｙp’及びＹq’を前記暗号演算装置の補正結果記憶部へ保存し、
前記補正結果記憶部に保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、前記暗号演算装置の平文出力部が、（数２２５）に従って暗号化される前の平文Ｙを算出することにより、
【数２２５】
0004086503.tif 000044
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算方法。
【請求項１３】
秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだ暗号演算装置によって暗号演算を行う方法であって、
前記暗号演算装置のモンゴメリパラメタ乗算部が、前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを定数として暗号文Ｘと乗算し、
前記暗号演算装置の剰余演算部が、前記モンゴメリパラメタ乗算部の乗算結果に対して前記秘密鍵ｐおよびｑによる剰余演算を実行し、
前記べき乗剰余演算部が、前記剰余演算結果に対して、モンゴメリべき乗剰余演算を実行することによって、暗号化される前の平文Ｙを算出することを特徴とする暗号演算方法。
【請求項１４】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２２６）に示すように定義されている場合において、暗号演算装置によって暗号演算を行う方法であって、
【数２２６】
0004086503.tif 000045
前記暗号演算装置の暗号文入力部が、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力し、
前記暗号演算装置のモンゴメリパラメタ乗算部が、前記暗号文ＸとモンゴメリパラメタＲとを乗算し、
前記乗算による演算結果を前記暗号演算装置の乗算結果記憶部に保存し、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、前記暗号演算装置の剰余演算部が、秘密鍵ｐ又はｑを剰余値とした（数２２７）に示す剰余演算を実行し、
【数２２７】
0004086503.tif 000046
前記剰余演算による演算結果Ｘp’及びＸq’を前記暗号演算装置の剰余演算結果記憶部に保存し、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置のモンゴメリべき乗剰余演算部が、（数２２８）に示すモンゴメリべき乗剰余演算を実行し、
【数２２８】
0004086503.tif 000047
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のモンゴメリべき乗剰余演算結果記憶部へ保存し、
前記モンゴメリべき乗剰余演算記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、前記暗号演算装置の平文出力部が、（数２２９）に示すように暗号化される前の平文Ｙを算出することにより、
【数２２９】
0004086503.tif 000048
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算方法。
【請求項１５】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２３０）に示すように定義されている場合において、暗号演算装置によって暗号演算を行う方法であって、
【数２３０】
0004086503.tif 000049
前記暗号演算装置の暗号文入力部が、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力し、
前記暗号演算装置のモンゴメリパラメタ乗算部が、前記暗号文Ｘと前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqとを乗算し、
前記乗算による演算結果を前記暗号演算装置の乗算結果記憶部に保存し、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、前記暗号演算装置の剰余演算部が、秘密鍵ｐ又はｑを剰余値とした（数２３１）に示す剰余演算を実行し、
【数２３１】
0004086503.tif 000050
前記剰余演算による演算結果Ｘp’及びＸq’を前記暗号演算装置の剰余演算結果記憶部に保存し、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置のモンゴメリべき乗剰余演算部が、（数２３２）に示すモンゴメリべき乗剰余演算を実行し、
【数２３２】
0004086503.tif 000051
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のモンゴメリべき乗剰余演算結果記憶部に保存し、
前記モンゴメリべき乗剰余演算記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、前記暗号演算装置の平文出力部が、（数２３３）に示すように暗号化される前の平文Ｙを算出することにより、
【数２３３】
0004086503.tif 000052
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算方法。
【請求項１６】
秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだ暗号演算装置によって暗号演算を行う方法であって、
前記暗号演算装置のモンゴメリパラメタ剰余演算部が、前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタに対して前記秘密鍵ｐ及びｑにより剰余演算を実行し、
前記暗号演算装置の剰余値乗算部が、前記モンゴメリパラメタ剰余演算部における演算結果を暗号文Ｘと乗算し、
前記暗号演算装置の剰余演算部が、前記剰余値乗算部の乗算結果に対して前記秘密鍵ｐおよびｑによる剰余演算を実行し、
前記剰余演算部の剰余演算結果に対して前記べき乗剰余演算部がモンゴメリべき乗剰余演算を実行することによって、暗号化される前の平文Ｙを算出することを特徴とする暗号演算方法。
【請求項１７】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２３４）に示すように定義されている場合において、暗号演算装置によって暗号演算を行う方法であって、
【数２３４】
0004086503.tif 000053
前記暗号演算装置の暗号文入力部が、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力し、
モンゴメリパラメタＲについて、（数２３５）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を、前記暗号演算装置のモンゴメリパラメタ剰余演算結果記憶部に保存し、
【数２３５】
0004086503.tif 000054
前記モンゴメリパラメタ剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、前記暗号演算装置の剰余値乗算部が、（数２３６）に示すように入力された暗号文Ｘを乗算し、
【数２３６】
0004086503.tif 000055
前記乗算による演算結果Ｘp’及びＸq’を前記暗号演算装置の乗算結果記憶部に保存し、
前記乗算結果記憶部に保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置の剰余演算部が、（数２３７）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行し、
【数２３７】
0004086503.tif 000056
前記剰余演算による演算結果Ｘp及びＸqを前記暗号演算装置の剰余演算結果記憶部に保存し、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、前記暗号演算装置のモンゴメリべき乗剰余演算部が、（数２３８）に示すモンゴメリべき乗剰余演算を実行し、
【数２３８】
0004086503.tif 000057
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のモンゴメリべき乗剰余演算結果記憶部に保存し、
前記モンゴメリべき乗剰余演算結果記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、前記暗号演算装置の平文出力部が、（数２３９）に示すように暗号化される前の平文Ｙを算出することにより、
【数２３９】
0004086503.tif 000058
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算方法。
【請求項１８】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２４０）に示すように定義されている場合において、暗号演算装置によって暗号演算を行う方法であって、
【数２４０】
0004086503.tif 000059
前記暗号演算装置の暗号文入力部が、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力し、
前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqについて、（数２４１）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を前記暗号演算装置のモンゴメリパラメタ剰余演算結果記憶部に保存し、
【数２４１】
0004086503.tif 000060
前記モンゴメリパラメタ剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、前記暗号演算装置の剰余値乗算部が、（数２４２）に示すように入力された暗号文Ｘを乗算し、
【数２４２】
0004086503.tif 000061
前記乗算による演算結果Ｘp’及びＸq’を前記暗号演算装置の乗算結果記憶部に保存し、
前記乗算結果記憶部に保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置の剰余演算部が、（数２４３）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行し、
【数２４３】
0004086503.tif 000062
前記剰余演算による演算結果Ｘp及びＸqを前記暗号演算装置の剰余演算結果記憶部に保存し、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、前記暗号演算装置のモンゴメリべき乗剰余演算部が、（数２４４）に示すモンゴメリべき乗剰余演算を実行し、
【数２４４】
0004086503.tif 000063
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のモンゴメリべき乗剰余演算結果記憶部へ保存し、
前記モンゴメリべき乗剰余演算結果記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、前記暗号演算装置の平文出力部が、（数２４５）に示すように暗号化される前の平文Ｙを算出することにより、
【数２４５】
0004086503.tif 000064
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とする暗号演算方法。
【請求項１９】
秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだ暗号演算装置に暗号演算処理を実行させるための、コンピュータ実行可能なプログラムであって、
前記暗号演算装置の定数乗算部に、前記秘密鍵ｐ及びｑよりも大きい値を有する任意の定数を暗号文Ｘと乗算させ、
前記暗号演算装置の剰余演算部に、前記定数乗算部の乗算結果に対して前記秘密鍵ｐおよびｑによる剰余演算を実行させ、
前記剰余演算部の剰余演算結果に対して、前記べき乗剰余演算部に、中国人剰余定理に基づいたべき乗剰余演算を実行させ、
前記暗号演算装置の剰余演算部に、前記べき乗剰余演算部のべき乗剰余演算結果に対して、前記定数に基づいて補正演算を実行させることにより、暗号化される前の平文Ｙを算出させることを特徴とする、コンピュータ実行可能なプログラム。
【請求項２０】
暗号演算装置による暗号演算処理を実行させるための、コンピュータ実行可能なプログラムであって、
前記プログラムは、
前記暗号演算装置の暗号文入力部に、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力させ、
前記暗号演算装置の定数記憶部に、前記秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有する定数Ｃを保存させ、
前記暗号演算装置の補正値記憶部に、前記定数に基づいて算出される補正値Ｃ-dp、Ｃ-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存させ、
前記暗号演算装置の定数乗算部に、前記暗号文Ｘと前記定数記憶部に保存されている前記定数Ｃとを乗算させ、
前記暗号演算装置の乗算結果記憶部に、前記乗算による演算結果を保存させ、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、前記暗号演算装置の剰余演算部に、秘密鍵ｐ又はｑを剰余値とした（数２４６）に示す剰余演算を実行させ、
【数２４６】
0004086503.tif 000065
前記暗号演算装置の剰余演算結果記憶部に、前記剰余演算による演算結果Ｘp’及びＸq’を保存させ、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置の中国人剰余ＲＳＡ処理部に、（数２４７）に示す中国人剰余定理に基づいたべき乗剰余演算を行わせ、
【数２４７】
0004086503.tif 000066
前記べき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のべき乗剰余演算結果記憶部へ保存させ、
前記べき乗剰余演算結果記憶部に保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、前記補正値記憶部に保存されている前記補正値Ｃ-dp又はＣ-dqを用いて、前記暗号演算装置の補正処理部に、（数２４８）に示すような補正演算を行わせ、
【数２４８】
0004086503.tif 000067
前記補正演算による演算結果Ｙp’及びＹq’を前記暗号演算装置の補正結果記憶部へ保存させ、
前記補正結果記憶部に保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、前記暗号演算装置の平文出力部に、（数２４９）に従って暗号化される前の平文Ｙを算出させることを特徴とする、コンピュータ実行可能なプログラム。
【数２４９】
0004086503.tif 000068
ただし、ａ＝ｐ-1ｍｏｄ ｑ
【請求項２１】
暗号演算装置に暗号演算処理を実行させるための、コンピュータ実行可能なプログラムであって、
前記暗号演算装置の暗号文入力部に、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力させ、
前記暗号演算装置の定数記憶部に、前記秘密鍵ｐ及びｑとの間にＣp＞ｐ、Ｃq＞ｑの関係を有する定数Ｃp及びＣqを保存させ、
前記暗号演算装置の補正値記憶部に、前記定数に基づいて算出される補正値Ｃp-dp、Ｃq-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存させ、
前記暗号演算装置の定数乗算部に、前記暗号文Ｘと前記定数記憶部に保存されている前記定数Ｃp又はＣqとを乗算させ、
前記暗号演算装置の乗算結果記憶部に、前記乗算による演算結果を保存させ、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、前記暗号演算装置の剰余演算部に、秘密鍵ｐ又はｑを剰余値とした（数２５０）に示す剰余演算を実行させ、
【数２５０】
0004086503.tif 000069
前記剰余演算による演算結果Ｘp’及びＸq’を前記暗号演算装置の剰余演算結果記憶部へ保存させ、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置の中国人剰余ＲＳＡ処理部に、（数２５１）に示す中国人剰余定理に基づいたべき乗剰余演算を行わせ、
【数２５１】
0004086503.tif 000070
前記べき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のべき乗剰余演算結果記憶部へ保存させ、
前記べき乗剰余演算結果記憶部に保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、前記補正値記憶部に保存されている前記補正値Ｃp-dp又はＣq-dqを用いて、前記暗号演算装置の補正処理部に、（数２５２）に示すような補正演算を行わせ、
【数２５２】
0004086503.tif 000071
前記補正演算による演算結果Ｙp’及びＹq’を前記暗号演算装置の補正結果記憶部へ保存させ、
前記補正結果記憶部に保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、前記暗号演算装置の平文出力部に、（数２５３）に従って暗号化される前の平文Ｙを算出させることを特徴とする、コンピュータ実行可能なプログラム。
【数２５３】
0004086503.tif 000072
ただし、ａ＝ｐ-1ｍｏｄ ｑ
【請求項２２】
秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだ暗号演算装置に暗号演算処理を実行させるための、コンピュータ実行可能なプログラムであって、
前記暗号演算装置のモンゴメリパラメタ乗算部に、前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを定数として暗号文Ｘと乗算させ、
前記暗号演算装置の剰余演算部に、前記モンゴメリパラメタ乗算部の乗算結果に対して前記秘密鍵ｐおよびｑによる剰余演算を実行させ、
前記べき乗剰余演算部に、前記剰余演算結果に対して、モンゴメリべき乗剰余演算を実行することによって、暗号化される前の平文Ｙを算出させることを特徴とする、コンピュータ実行可能なプログラム。
【請求項２３】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２５４）に示すように定義されている場合において、暗号演算装置に暗号演算処理を実行させるための、コンピュータ実行可能なプログラムであって、
【数２５４】
0004086503.tif 000073
前記暗号演算装置の暗号文入力部に、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力させ、
前記暗号演算装置のモンゴメリパラメタ乗算部に、前記暗号文ＸとモンゴメリパラメタＲとを乗算させ、
前記乗算による演算結果を前記暗号演算装置の乗算結果記憶部に保存させ、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、前記暗号演算装置の剰余演算部に、秘密鍵ｐ又はｑを剰余値とした（数２５５）に示す剰余演算を実行させ、
【数２５５】
0004086503.tif 000074
前記剰余演算による演算結果Ｘp’及びＸq’を前記暗号演算装置の剰余演算結果記憶部に保存させ、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置のモンゴメリべき乗剰余演算部に、（数２５６）に示すモンゴメリべき乗剰余演算を実行させ、
【数２５６】
0004086503.tif 000075
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のモンゴメリべき乗剰余演算結果記憶部へ保存させ、
前記モンゴメリべき乗剰余演算記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、前記暗号演算装置の平文出力部に、（数２５７）に示すように暗号化される前の平文Ｙを算出させることを特徴とする、コンピュータ実行可能なプログラム。
【数２５７】
0004086503.tif 000076
ただし、ａ＝ｐ-1ｍｏｄ ｑ
【請求項２４】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２５８）に示すように定義されている場合において、暗号演算装置による暗号演算処理を実行させるための、コンピュータ実行可能なプログラムであって、
【数２５８】
0004086503.tif 000077
前記暗号演算装置の暗号文入力部に、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力させ、
前記暗号演算装置のモンゴメリパラメタ乗算部に、前記暗号文Ｘと前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqとを乗算させ、
前記乗算による演算結果を前記暗号演算装置の乗算結果記憶部に保存させ、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、前記暗号演算装置の剰余演算部に、秘密鍵ｐ又はｑを剰余値とした（数２５９）に示す剰余演算を実行させ、
【数２５９】
0004086503.tif 000078
前記剰余演算による演算結果Ｘp’及びＸq’を前記暗号演算装置の剰余演算結果記憶部に保存させ、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置のモンゴメリべき乗剰余演算部に、（数２６０）に示すモンゴメリべき乗剰余演算を実行させ、
【数２６０】
0004086503.tif 000079
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のモンゴメリべき乗剰余演算結果記憶部に保存させ、
前記モンゴメリべき乗剰余演算記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、前記暗号演算装置の平文出力部に、（数２６１）に示すように暗号化される前の平文Ｙを算出させることを特徴とする、コンピュータ実行可能なプログラム。
【数２６１】
0004086503.tif 000080
ただし、ａ＝ｐ-1ｍｏｄ ｑ
【請求項２５】
秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだ暗号演算装置に暗号演算処理を実行させるための、コンピュータ実行可能なプログラムであって、
前記暗号演算装置のモンゴメリパラメタ剰余演算部に、前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタに対して前記秘密鍵ｐ及びｑにより剰余演算を実行させ、
前記暗号演算装置の剰余値乗算部に、前記モンゴメリパラメタ剰余演算部における演算結果を暗号文Ｘと乗算させ、
前記暗号演算装置の剰余演算部に、前記剰余値乗算部の乗算結果に対して前記秘密鍵ｐおよびｑによる剰余演算を実行させ、
前記剰余演算部の剰余演算結果に対して、前記べき乗剰余演算部にモンゴメリべき乗剰余演算を実行させることによって、暗号化される前の平文Ｙを算出することを特徴とする、コンピュータ実行可能なプログラム。
【請求項２６】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２６２）に示すように定義されている場合において、暗号演算装置による暗号演算処理を実行させるための、コンピュータ実行可能なプログラムであって、
【数２６２】
0004086503.tif 000081
前記暗号演算装置の暗号文入力部に、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力させ、
モンゴメリパラメタＲについて、（数２６３）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を、前記暗号演算装置のモンゴメリパラメタ剰余演算結果記憶部に保存させ、
【数２６３】
0004086503.tif 000082
前記モンゴメリパラメタ剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、前記暗号演算装置の剰余値乗算部に、（数２６４）に示すように入力された暗号文Ｘを乗算させ、
【数２６４】
0004086503.tif 000083
前記乗算による演算結果Ｘp’及びＸq’を前記暗号演算装置の乗算結果記憶部に保存させ、
前記乗算結果記憶部に保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置の剰余演算部に、（数２６５）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行させ、
【数２６５】
0004086503.tif 000084
前記剰余演算による演算結果Ｘp及びＸqを前記暗号演算装置の剰余演算結果記憶部に保存させ、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、前記暗号演算装置のモンゴメリべき乗剰余演算部に、（数２６６）に示すモンゴメリべき乗剰余演算を実行させ、
【数２６６】
0004086503.tif 000085
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のモンゴメリべき乗剰余演算結果記憶部に保存させ、
前記モンゴメリべき乗剰余演算結果記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、前記暗号演算装置の平文出力部に、（数２６７）に示すように暗号化される前の平文Ｙを算出させることを特徴とする、コンピュータ実行可能なプログラム。
【数２６７】
0004086503.tif 000086
ただし、ａ＝ｐ-1ｍｏｄ ｑ
【請求項２７】
モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２６８）に示すように定義されている場合において、暗号演算装置による暗号演算処理を実行させるための、コンピュータ実行可能なプログラムであって、
【数２６８】
0004086503.tif 000087
前記暗号演算装置の暗号文入力部に、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力させ、
前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqについて、（数２６９）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を前記暗号演算装置のモンゴメリパラメタ剰余演算結果記憶部に保存させ、
【数２６９】
0004086503.tif 000088
前記モンゴメリパラメタ剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、前記暗号演算装置の剰余値乗算部に、（数２７０）に示すように入力された暗号文Ｘを乗算させ、
【数２７０】
0004086503.tif 000089
前記乗算による演算結果Ｘp’及びＸq’を前記暗号演算装置の乗算結果記憶部に保存させ、
前記乗算結果記憶部に保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、前記暗号演算装置の剰余演算部に、（数２７１）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行させ、
【数２７１】
0004086503.tif 000090
前記剰余演算による演算結果Ｘp及びＸqを前記暗号演算装置の剰余演算結果記憶部に保存させ、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、前記暗号演算装置のモンゴメリべき乗剰余演算部に、（数２７２）に示すモンゴメリべき乗剰余演算を実行させ、
【数２７２】
0004086503.tif 000091
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを前記暗号演算装置のモンゴメリべき乗剰余演算結果記憶部へ保存させ、
前記モンゴメリべき乗剰余演算結果記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、前記暗号演算装置の平文出力部に、（数２７３）に示すように暗号化される前の平文Ｙを算出させることを特徴とする、コンピュータ実行可能なプログラム。
【数２７３】
0004086503.tif 000092
ただし、ａ＝ｐ-1ｍｏｄ ｑ
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、サイドチャネルアタックを用いた暗号プロセッサ内部における秘密鍵の解析に対して安全であり、かつ復号化処理について高速に演算処理を実行できるサイドチャネルアタック耐性を有する暗号演算装置及び方法に関する。
【０００２】
【従来の技術】
近年のコンピュータネットワークの発達により、データベースの検索や電子メール、電子ニュース等の電子化された情報について、ネットワークを経由して送受する機会が急速に増加してきている。さらに、これらを利用して、オンラインショッピング等のサービスも提供されつつある。
【０００３】
しかし、これらの金銭授受を伴うサービスが拡大するにつれて、ネットワーク上の電子化されたデータを盗聴する、改ざんする、他人になりすましてサービスを享受する等のいわゆるネットワーク犯罪の増加という新たな問題点も指摘されている。特に無線を利用しているネットワーク環境においては、通信の傍受が容易であることから、特にこれらの行為を防止する対策が望まれている。
【０００４】
これらの問題に対して暗号技術（encryption technology）を応用した暗号化電子メールや電子署名を活用した利用者認証システム等が提案され、種々のネットワークにも導入されつつある。かかる観点から、コンピュータネットワーク環境において、暗号化技術あるいは電子署名生成技術は必要不可欠な技術の一つであると考えられる。
【０００５】
かかる暗号化技術あるいは電子署名生成技術の進展に伴い、それに対する攻撃方法についても急速に進展している。例えばサイドチャネルアタックは、暗号プロセッサの処理時間や電力消費量を測定し、それらが有する特徴に基づいて暗号の秘密鍵を解析するという攻撃方法であり、代表的なものとしてタイミングアタックとＳＰＡ（Simple Power Analysis）が良く知られている。
【０００６】
そして、剰余演算を含む暗号化方式に対してタイミングアタックやＳＰＡを使用すると、入力値と剰余数の値の大小関係を判別することができることから、入力値を操作して二分探索を行うことにより、剰余数の値、すなわち秘密鍵の値を知ることが可能となる。
【０００７】
すなわち、入力値によって剰余演算が実行されるか否かが決定し、実行される場合と実行されない場合とでは処理時間や電力消費量に大きな差が生じることから、処理にかかる時間の差に着目するタイミングアタックや、演算に要する電力消費量の差に着目するＳＰＡを行うことによって、入力値と剰余数の値の大小関係を判別することが可能となっている。
【０００８】
したがって、もし悪意ある第三者がこれらの攻撃方法を用いれば、入力値を操作しながら二分探索を繰り返すことによって、第三者にとって未知である剰余値を特定することが可能となる。このことは、例えば中国人剰余定理を使用したＲＳＡ暗号を使用している場合において、秘密鍵となっている剰余値を第三者が知り得ることを意味しており、暗号技術における安全性の観点からは致命的なものと考えられる。
【０００９】
上述したような攻撃方法は、電子署名の生成処理にも応用できる。すなわち、電子署名の生成時におけるキー情報が第三者によって解析されると、第三者が任意に電子署名を生成できることになり、本人以外の第三者によるいわゆる「なりすまし」を容易に行うことが可能となる。したがって、電子署名を導入したセキュリティの観点からも致命的なものと考えられる。
【００１０】
以下、暗号の復号化を例に挙げて、数式を用いながら具体的に説明する。まず、一般的な中国人剰余定理を使用したＲＳＡ暗号を用いた暗号を復号化する場合の処理は（数２９）のように表すことができる。
【００１１】
【数２９】
Ｘp＝Ｘ ｍｏｄ ｐ
Ｘq＝Ｘ ｍｏｄ ｑ
Ｙp＝Ｘpdpｍｏｄ ｐ
Ｙq＝Ｘqdqｍｏｄ ｑ
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
ｄｐ＝ｄ ｍｏｄ（ｐ−１）
ｄｑ＝ｄ ｍｏｄ（ｑ−１）
ここで（数２９）は、秘密鍵をｄ、ｐ、ｑとしており、暗号文Ｘに対応する平文Ｙを、Ｙ＝Ｘdｍｏｄ Ｎ（Ｎ＝ｐｑ）として求めるものである。（数２９）のようにべき乗剰余演算Ｙp及びＹqを用いることによって、直接Ｘdｍｏｄ Ｎを求めるよりも処理時間が全体として１／４程度にまで短縮されている。
【００１２】
そして、まず剰余値ｐに着目すると、（数２９）における第一式Ｘp＝Ｘ ｍｏｄ ｐに対して任意の入力Ｘを入力すると、Ｘとｐとの大小関係によって、剰余演算を行うか否かが定まってしまう。すなわちＸ≧ｐの場合にはＸ ｍｏｄ ｐの剰余演算を実行し、Ｘ＜ｐの場合には、剰余演算が行われないことになる。
【００１３】
したがって、タイミングアタックを用いる場合においては、演算時間の大小によってＸとｐとの大小関係が判明する。つまり、Ｘ≧ｐであるＸが入力された場合には剰余演算が実行されることから演算時間が長くなり、一方、Ｘ＜ｐであるＸが入力された場合には剰余演算が実行されないことから演算時間が短くなる。
【００１４】
そこで、演算時間が長い場合には、今回入力したＸよりも小さい値を再入力し、演算時間が短い場合にはＸよりも大きい値を入力し、再度演算時間を測定する。かかる処理を繰り返すことによって、最後には剰余値ｐと一致する入力値Ｘを得ることができ、秘密鍵ｐを特定することが可能となる。
【００１５】
また、ＳＰＡを用いる場合には、演算による電力消費量の波形の相違からＸとｐとの大小関係が判明する。すなわち、図１に示すように、剰余演算を伴わない演算Ａの電力消費量の波形を（ａ）、剰余演算を伴う演算Ｂの電力消費量の波形を（ｂ）とした場合において、測定された電力消費量の波形（ｃ）から、剰余演算を伴う演算Ｂが実行されたか否かを判別することができる。
【００１６】
したがって、図１（ｃ）に示すように剰余演算を伴う演算Ｂの電力消費量の波形が含まれている場合には、入力ＸがＸ≧ｐであると判断することができ、剰余演算を伴う演算Ｂの電力消費量の波形が含まれていない場合には、入力ＸがＸ＜ｐであると判断することができる。よって、タイミングアタックを用いる場合と同様に、剰余演算を伴う演算Ｂの電力消費量の波形が含まれている場合には、今回入力したＸよりも小さい値を再入力し、剰余演算を伴う演算Ｂの電力消費量の波形が含まれていない場合には、Ｘよりも大きい値を入力し、再度電力消費量の波形を観測する。かかる処理を繰り返すことによって、最後には剰余値ｐと一致する入力値Ｘを得ることができ、秘密鍵ｐを特定することが可能となる。
【００１７】
以上説明してきた攻撃方法を秘密鍵ｑに対しても同様に用いることで、剰余値ｑと一致する入力値Ｘを得ることができることから、秘密鍵ｑについても第三者が知ることが可能となってしまう。
【００１８】
そこで、これらの攻撃を防ぐ方法についても様々な技術が考えられている。その代表的な方法として、入力データと乱数との乗算を行ってから剰余演算を行うようにする方法が考えられている。このようにすることで、剰余演算の実行が入力データと剰余数との大小関係のみに依存することなく、乱数の大きさによって剰余演算を実行するか否かがランダムに定まることから、タイミングアタックを用いようと、あるいはＳＰＡを用いようと、剰余値ｐあるいはｑ、すなわち秘密鍵を特定することができないことになる。
【００１９】
【発明が解決しようとする課題】
しかしながら、上述したような乱数を乗算しただけの方法では、その補正を行うための演算に相当の時間を要するという新たな問題点が生じていた。すなわち、乱数を乗算したことに対する補正処理をするために、適切な補正値を導出する必要が生じるが、乱数を使用していることから、乱数を乗算するごとに補正値を導出する必要が生じてしまう。したがって、毎回補正値を導出する演算をしなければならず、全体として演算処理に時間がかかってしまうことになる。
【００２０】
例えば、（数２９）と同様に、乱数ｒを用いる場合の中国人剰余定理を使用したＲＳＡ暗号を用いた暗号文を平文へと復号化する場合の処理については（数３０）のように表すことができる。
【００２１】
【数３０】
Ｘp’＝Ｘ＊ｒ ｍｏｄ ｐ
Ｘq’＝Ｘ＊ｒ ｍｏｄ ｑ
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
Ｙp’＝Ｙp＊ｒ-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊ｒ-dqｍｏｄ ｑ
Ｙ’＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
ｄｐ＝ｄ ｍｏｄ（ｐ−１）
ｄｑ＝ｄ ｍｏｄ（ｑ−１）
なお、（数３０）においても秘密鍵をｄ、ｐ、ｑとしており、暗号文Ｘに対応する平文Ｙを、Ｙ＝Ｘdｍｏｄ Ｎ（Ｎ＝ｐｑ）として求めている。（数３０）に示すように、あらかじめ入力Ｘに乱数ｒを乗算することで、剰余演算をするか否かが入力値Ｘと剰余値ｐあるいはｑの大小関係に依存しないようにしている。反面、（数２９）とは異なり、剰余演算値に対して、乗算したおのおのの乱数ｒに対応した補正値ｒ-dpｍｏｄ ｐあるいはｒ-dqｍｏｄ ｑを乗算する必要があり、最終的に求めるＸdｍｏｄ Ｎに到達するまでに演算処理の回数が増えてしまうことになる。
【００２２】
本発明は、上記問題点を解決するために、タイミングアタックやＳＰＡに代表されるサイドチャネルアタックを用いた攻撃に対しても安全であり、かつ高速に演算可能なサイドチャネルアタック耐性を有する暗号演算装置及び方法を提供することを目的とする。
【００２３】
【課題を解決するための手段】
上記目的を達成するために本発明にかかるサイドチャネルアタック耐性を有する暗号演算装置は、秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだサイドチャネルアタック耐性を有する暗号演算装置であって、秘密鍵ｐ及びｑよりも大きい値を有する任意の定数を暗号文Ｘと乗算してからべき乗剰余演算を実行し、最後に定数に基づいて補正演算を実行する補正演算部を設けることによって暗号化される前の平文Ｙを算出することを特徴とする。
【００２４】
より具体的には、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有する定数Ｃを保存する定数記憶部と、定数に基づいて算出される補正値Ｃ-dp、Ｃ-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存する補正値記憶部と、暗号文Ｘと定数記憶部に保存されている定数Ｃとを乗算する定数乗算部と、乗算による演算結果を保存する乗算結果記憶部と、乗算結果記憶部に保存されている乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数３１）に示す剰余演算を実行する剰余演算部と、剰余演算による演算結果Ｘp’及びＸq’を保存する剰余演算結果記憶部と、剰余演算結果記憶部に保存されている剰余演算による演算結果Ｘp’及びＸq’に対して、（数３２）に示す中国人剰余定理に基づいたべき乗剰余演算を行う中国人剰余ＲＳＡ処理部と、べき乗剰余演算による演算結果Ｙp及びＹqを保存するべき乗剰余演算結果記憶部と、べき乗剰余演算結果記憶部に保存されているべき乗剰余演算による演算結果Ｙp及びＹqに対して、補正値記憶部に保存されている補正値Ｃ-dp又はＣ-dqを用いて、（数３３）に示すような補正演算を行う補正処理部と、補正演算による演算結果Ｙp’及びＹq’を保存する補正結果記憶部と、補正結果記憶部に保存されている補正演算による演算結果Ｙp’及びＹq’に基づいて、（数３４）に従って暗号化される前の平文Ｙを算出する平文出力部とを含み、いかなる暗号文Ｘが入力された場合であっても秘密鍵ｐ及びｑを特定することができないことを特徴とする。
【００２５】
【数３１】
Ｘp’＝Ｘ＊Ｃ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｃ ｍｏｄ ｑ
【００２６】
【数３２】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
【００２７】
【数３３】
Ｙp’＝Ｙp＊Ｃ-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊Ｃ-dqｍｏｄ ｑ
【００２８】
【数３４】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
かかる構成により、いかなる入力がなされた場合であっても、常に剰余演算が実行されることになることから、演算処理時間や電力消費量の波形等の相違によって入力値と秘密鍵ｐ又はｑとの大小関係を特定することができず、サイドチャネルアタックに対して安全性の高い復号化演算方法を提供することができる。また、定数Ｃに基づいて補正値を算出することから、補正値を求める演算は最初の１回で済み、全体としての演算処理負荷も小さくなることが期待できる。
【００２９】
次に、上記目的を達成するために本発明にかかるサイドチャネルアタック耐性を有する暗号演算装置は、秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだサイドチャネルアタック耐性を有する暗号演算装置であって、秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを定数として、暗号文Ｘと乗算してからべき乗剰余演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とする。
【００３０】
より具体的には、モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数３５）に示すように定義されている場合において、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、暗号文ＸとモンゴメリパラメタＲとを乗算するモンゴメリパラメタ乗算部と、乗算による演算結果を保存する乗算結果記憶部と、乗算結果記憶部に保存されている乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数３６）に示す剰余演算を実行する剰余演算部と、剰余演算による演算結果Ｘp’及びＸq’を保存する剰余演算結果記憶部と、剰余演算結果記憶部に保存されている剰余演算による演算結果Ｘp’及びＸq’に対して、（数３７）に示すモンゴメリべき乗剰余演算を実行するモンゴメリべき乗剰余演算部と、モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するモンゴメリべき乗剰余演算結果記憶部と、モンゴメリべき乗剰余演算記憶部に保存されているモンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数３８）に示すように暗号化される前の平文Ｙを算出する平文出力部とを含み、いかなる暗号文Ｘが入力された場合であっても秘密鍵ｐ及びｑを特定することができないことを特徴とする。
【００３１】
【数３５】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
【００３２】
【数３６】
Ｘp’＝Ｘ＊Ｒ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒ ｍｏｄ ｑ
【００３３】
【数３７】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
【００３４】
【数３８】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
かかる構成により、いかなる入力がなされた場合であっても、常に剰余演算が実行されることになることから、演算処理時間や電力消費量の波形等の相違によって入力値と秘密鍵ｐ又はｑとの大小関係を特定することができず、サイドチャネルアタックに対して安全性の高い復号化演算方法を提供することができる。また、補正演算を行う必要性が無いことから、全体としての演算処理負荷がより小さくなることが期待できる。
【００３５】
次に、上記目的を達成するために本発明にかかるサイドチャネルアタック耐性を有する暗号演算装置は、秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだサイドチャネルアタック耐性を有する暗号演算装置であって、秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを秘密鍵ｐ及びｑにより剰余演算を実行するモンゴメリパラメタ剰余演算部を含み、剰余演算部における演算結果を暗号文Ｘと乗算してからべき乗剰余演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とする。
【００３６】
より具体的には、モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数３９）に示すように定義されている場合において、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、モンゴメリパラメタＲについて、（数４０）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を保存するモンゴメリパラメタ剰余演算結果記憶部と、モンゴメリパラメタ剰余演算結果記憶部に保存されている剰余演算による演算結果Ｒp’又はＲq’に対して、（数４１）に示すように入力された暗号文Ｘを乗算する剰余値乗算部と、乗算による演算結果Ｘp’及びＸq’を保存する乗算結果記憶部と、乗算結果記憶部に保存されている乗算による演算結果Ｘp’及びＸq’に対して、（数４２）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する剰余演算部と、剰余演算による演算結果Ｘp及びＸqを保存する剰余演算結果記憶部と、剰余演算結果記憶部に保存されている剰余演算による演算結果Ｘp及びＸqに対して、（数４３）に示すモンゴメリべき乗剰余演算を実行するモンゴメリべき乗剰余演算部と、モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するモンゴメリべき乗剰余演算結果記憶部と、モンゴメリべき乗剰余演算結果記憶部に保存されているモンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数４４）に示すように暗号化される前の平文Ｙを算出する平文出力部とを含み、いかなる暗号文Ｘが入力された場合であっても秘密鍵ｐ及びｑを特定することができないことを特徴とする。
【００３７】
【数３９】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
【００３８】
【数４０】
Ｒp’＝Ｒ ｍｏｄ ｐ
Ｒq’＝Ｒ ｍｏｄ ｑ
【００３９】
【数４１】
Ｘp’＝Ｘ＊Ｒp’
Ｘq’＝Ｘ＊Ｒq’
【００４０】
【数４２】
Ｘp＝Ｘp’ｍｏｄ ｐ
Ｘq＝Ｘq’ｍｏｄ ｑ
【００４１】
【数４３】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
【００４２】
【数４４】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
かかる構成により、入力値とモンゴメリパラメタＲの剰余演算値との積の大小によって剰余演算が実行されるか否かが定まることから、演算処理時間や電力消費量の波形等の相違のみによっては、入力値と秘密鍵ｐ又はｑとの大小関係を特定することができず、サイドチャネルアタックに対して安全性の高い復号化演算方法を提供することができる。また、補正演算を行う必要性が無いことから、全体としての演算処理負荷がより小さくなることが期待できる。
【００４３】
また、本発明は、上記のようなサイドチャネルアタック耐性を有する暗号演算装置の機能をコンピュータの処理ステップとして実行するソフトウェアを特徴とするものであり、具体的には、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する工程と、秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有する定数Ｃを保存する工程と、定数に基づいて算出される補正値Ｃ-dp、Ｃ-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存する工程と、暗号文Ｘと保存されている定数Ｃとを乗算する工程と、乗算による演算結果を保存する工程と、保存されている乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数４５）に示す剰余演算を実行する工程と、剰余演算による演算結果Ｘp’及びＸq’を保存する工程と、保存されている剰余演算による演算結果Ｘp’及びＸq’に対して、（数４６）に示す中国人剰余定理に基づいたべき乗剰余演算を行う工程と、べき乗剰余演算による演算結果Ｙp及びＹqを保存する工程と、保存されているべき乗剰余演算による演算結果Ｙp及びＹqに対して、保存されている補正値Ｃ-dp又はＣ-dqを用いて、（数４７）に示すような補正演算を行う工程と、補正演算による演算結果Ｙp’及びＹq’を保存する工程と、保存されている補正演算による演算結果Ｙp’及びＹq’に基づいて、（数４８）に従って暗号化される前の平文Ｙを算出する工程とを含み、いかなる暗号文Ｘが入力された場合であっても秘密鍵ｐ及びｑを特定することができないサイドチャネルアタック耐性を有する暗号演算方法並びにそのような工程を具現化するコンピュータ実行可能なプログラムであることを特徴とする。
【００４４】
【数４５】
Ｘp’＝Ｘ＊Ｃ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｃ ｍｏｄ ｑ
【００４５】
【数４６】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
【００４６】
【数４７】
Ｙp’＝Ｙp＊Ｃ-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊Ｃ-dqｍｏｄ ｑ
【００４７】
【数４８】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
かかる構成により、コンピュータ上へ当該プログラムをロードさせ実行することで、いかなる入力がなされた場合であっても、常に剰余演算が実行されることになることから、演算処理時間や電力消費量の波形等の相違によって入力値と秘密鍵ｐ又はｑとの大小関係を特定することができず、サイドチャネルアタックに対して安全性の高い復号化演算方法を提供することができる。また、定数Ｃに基づいて補正値を算出することから、補正値を求める演算は最初の１回で済み、全体としての演算処理負荷も小さくなることが期待できるサイドチャネルアタック耐性を有する暗号演算装置を実現することが可能となる。
【００４８】
さらに本発明は、上記のようなサイドチャネルアタック耐性を有する暗号演算装置の機能をコンピュータの処理ステップとして実行するソフトウェアを特徴とするものであり、具体的には、モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数４９）に示すように定義されている場合において、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する工程と、暗号文ＸとモンゴメリパラメタＲとを乗算する工程と、乗算による演算結果を保存する工程と、保存されている乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数５０）に示す剰余演算を実行する工程と、剰余演算による演算結果Ｘp’及びＸq’を保存する工程と、保存されている剰余演算による演算結果Ｘp’及びＸq’に対して、（数５１）に示すモンゴメリべき乗剰余演算を実行する工程と、モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存する工程と、保存されているモンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数５２）に示すように暗号化される前の平文Ｙを算出する工程とを含み、いかなる暗号文Ｘが入力された場合であっても秘密鍵ｐ及びｑを特定することができないサイドチャネルアタック耐性を有する暗号演算方法並びにそのような工程を具現化するコンピュータ実行可能なプログラムであることを特徴とする。
【００４９】
【数４９】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
【００５０】
【数５０】
Ｘp’＝Ｘ＊Ｒ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒ ｍｏｄ ｑ
【００５１】
【数５１】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
【００５２】
【数５２】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
かかる構成により、コンピュータ上へ当該プログラムをロードさせ実行することで、いかなる入力がなされた場合であっても、常に剰余演算が実行されることになることから、演算処理時間や電力消費量の波形等の相違によって入力値と秘密鍵ｐ又はｑとの大小関係を特定することができず、サイドチャネルアタックに対して安全性の高い復号化演算方法を提供することができる。また、補正演算を行う必要性が無いことから、全体としての演算処理負荷がより小さくなることが期待できるサイドチャネルアタック耐性を有する暗号演算装置を実現することが可能となる。
【００５３】
また、本発明は、上記のようなサイドチャネルアタック耐性を有する暗号演算装置の機能をコンピュータの処理ステップとして実行するソフトウェアを特徴とするものであり、具体的には、モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数５３）に示すように定義されている場合において、秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する工程と、モンゴメリパラメタＲについて、（数５４）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を保存する工程と、保存されている剰余演算による演算結果Ｒp’又はＲq’に対して、（数５５）に示すように入力された暗号文Ｘを乗算する工程と、乗算による演算結果Ｘp’及びＸq’を保存する工程と、保存されている乗算による演算結果Ｘp’及びＸq’に対して、（数５６）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する工程と、剰余演算による演算結果Ｘp及びＸqを保存する工程と、保存されている剰余演算による演算結果Ｘp及びＸqに対して、（数５７）に示すモンゴメリべき乗剰余演算を実行する工程と、モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存する工程と、保存されているモンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数５８）に示すように暗号化される前の平文Ｙを算出する工程とを含み、いかなる暗号文Ｘが入力された場合であっても秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法並びにそのような工程を具現化するコンピュータ実行可能なプログラムであることを特徴とする。
【００５４】
【数５３】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
【００５５】
【数５４】
Ｒp’＝Ｒ ｍｏｄ ｐ
Ｒq’＝Ｒ ｍｏｄ ｑ
【００５６】
【数５５】
Ｘp’＝Ｘ＊Ｒp’
Ｘq’＝Ｘ＊Ｒq’
【００５７】
【数５６】
Ｘp＝Ｘp’ｍｏｄ ｐ
Ｘq＝Ｘq’ｍｏｄ ｑ
【００５８】
【数５７】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
【００５９】
【数５８】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
かかる構成により、コンピュータ上へ当該プログラムをロードさせ実行することで、入力値とモンゴメリパラメタＲの剰余演算値との積の大小によって剰余演算が実行されるか否かが定まることから、演算処理時間や電力消費量の波形等の相違のみによっては、入力値と秘密鍵ｐ又はｑとの大小関係を特定することができず、サイドチャネルアタックに対して安全性の高い復号化演算方法を提供することができる。また、補正演算を行う必要性が無いことから、全体としての演算処理負荷がより小さくなることが期待できるサイドチャネルアタック耐性を有する暗号演算装置を実現することが可能となる。
【００６０】
【発明の実施の形態】
（実施の形態１）
以下、本発明の実施の形態１にかかるサイドチャネルアタック耐性を有する暗号演算装置について、図面を参照しながら説明する。本実施の形態１においては、入力Ｘに対して、乱数ｒを乗算する代わりに、秘密鍵ｐあるいはｑのどちらよりも大きな定数Ｃを乗算する点に特徴を有する。
【００６１】
すなわち、入力Ｘに対して必ず秘密鍵ｐあるいはｑのどちらよりも大きな定数Ｃが乗算されていることから、Ｘ＊Ｃは常にｐあるいはｑよりも大きな値となる。したがって、剰余値ｐあるいはｑによる剰余演算が必ず実行されることから、タイミングアタックを用いる場合であっても、ＳＰＡを用いる場合であっても、剰余値ｐあるいはｑとの大小比較ができないことになる。
【００６２】
一方、Ｃは定数であることから、補正値Ｃ-dp、Ｃ-dqは一度計算しておけば足りることになる。したがって、剰余演算をするごとに補正値を導出する必要が無くなり、全体として演算処理負荷を軽減することができる。
【００６３】
このようにすることで、タイミングアタックやＳＰＡ等のサイドチャネルアタックに対して有効に保護することができると共に、演算処理負荷が増大することなく高速に演算処理を行うことが可能となる。
【００６４】
具体的な構成を図２に示す。図２は本発明の実施の形態１にかかるサイドチャネルアタック耐性を有する暗号演算装置の構成図である。なお、本実施の形態１においては、中国人剰余定理を用いたＲＳＡ処理における復号化処理を行う場合について説明する。
【００６５】
図２において、１は暗号文入力部を示しており、暗号化された暗号文Ｘを復号化するために入力するものである。タイミングアタックあるいはＳＰＡを行う第三者が、秘密鍵を特定するためにダミーの暗号文Ｘｄを入力するのも暗号文入力部１である。入力された暗号文ＸあるいはＸｄは、定数乗算部６へ渡される。
【００６６】
次に、２は定数入力部を示しており、定数乗算部６において、暗号文入力部１から入力された暗号文Ｘあるいはダミーの暗号文Ｘｄに掛け合わせる定数Ｃを入力するものである。なお定数Ｃは、秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有するものとする。入力された定数Ｃは定数記憶部３に保存される。
【００６７】
なお、定数入力部２を設けない構成も考えられる。すなわち、実装時において、あらかじめ秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有する定数Ｃを定数記憶部３に記憶させておき、ユーザに入力を要求しない構成である。実装時には定数Ｃを事前に定めておくことが考えられるからである。
【００６８】
また、４は補正値演算部を示しており、最終的に平文を求めるために必要となる補正値Ｃ-dp、Ｃ-dqを求めるものである。ここで、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）であり、Ｃが定数であることから、最終的に平文を求めるために必要となる補正値Ｃ-dp、Ｃ-dqについても一定値となる。算出された補正値Ｃ-dp、Ｃ-dqは、補正値記憶部５に保存される。
【００６９】
なお、定数入力部２と同様、補正値演算部４を設けない構成も考えられる。すなわち、実装時において、定数記憶部３に記憶されている定数Ｃに基づいて、事前に補正値Ｃ-dp、Ｃ-dqを算出して補正値記憶部５に記憶させておく構成である。こうすることで演算処理負荷を軽減することが期待できるからである。
【００７０】
そして、６は定数乗算部を示しており、定数記憶部３に保存されている定数Ｃと、暗号文入力部１で入力された暗号文Ｘあるいはダミーの暗号文Ｘｄとを乗算するものである。暗号文Ｘに対する乗算は（数５９）に示すようになる。（数５９）により乗算した結果Ｘ’については、乗算結果記憶部７に保存される。
【００７１】
【数５９】
Ｘ’＝Ｘ＊Ｃ
次に、８は剰余演算部を示しており、乗算結果記憶部７に保存されている乗算結果に対して、秘密鍵ｐ及びｑを剰余値とした剰余演算を、各々実行するものである。本実施の形態１においては、Ｃ＞ｐ及びＣ＞ｑの関係から、常にＸ＊Ｃ＞ｐ及びＸ＊Ｃ＞ｑが成立する。したがって、剰余演算部８においては、暗号文入力部１においてどのような入力がなされた場合であっても剰余演算を行うことになる。
【００７２】
本実施の形態１における剰余演算は（数６０）のように表すことができる。（数６０）により算出された剰余演算の結果であるＸp’及びＸq’は、剰余演算結果記憶部９に保存される。
【００７３】
【数６０】
Ｘp’＝Ｘ’ｍｏｄ ｐ
Ｘq’＝Ｘ’ｍｏｄ ｑ
また、１０は中国人剰余ＲＳＡ処理部を示しており、剰余演算結果記憶部９に保存されている剰余演算の結果に対して、中国人剰余定理に基づいたべき乗剰余演算を行うものである。ここでは、（数６１）に示すようなべき乗剰余演算が実行される。（数６１）に示すべき乗剰余演算の演算結果がＹp及びＹqは、べき乗剰余演算結果記憶部１１に保存される。
【００７４】
【数６１】
0004086503.tif 000002
そして、１２は補正処理部を示しており、事前に算出して補正値記憶部５に保存されている補正値Ｃ-dp及びＣ-dqを用いて、入力値ＸあるいはＸｄについて、べき乗剰余演算を行った場合における演算結果へと補正するものである。補正演算は（数６２）に示すような演算となる。なお、Ｃが定数であることから、補正値Ｃ-dp及びＣ-dqについても定数となっており、補正演算値Ｙp’及びＹq’を求める演算処理は一回行えば足りることになる。補正演算値Ｙp’及びＹq’については、補正結果記憶部１３に保存されることになる。
【００７５】
【数６２】
0004086503.tif 000003
最後に１４は平文出力部を示しており、補正処理部１２において補正され、補正結果記憶部１３に保存されている補正演算値Ｙp’及びＹq’に基づいて、（数６３）に示すように暗号化される前の平文Ｙを算出するものである。入力値がダミー暗号文Ｘｄの場合には誤った計算値を出力することになるが、サイドチャネルアタックにおいては、算出された値は問題とならない。
【００７６】
【数６３】
Ｙ’＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
以上のような構成とすることにより、秘密鍵ｐ及びｑを知っている正当なユーザは、通常の演算処理と大差ない演算処理負荷で平文Ｙを求めることができ、一方、不正に解読を試みる悪意ある第三者にとっては、サイドチャネルアタックによって秘密鍵を求めることができないことから、暗号としての安全性を確保することが可能となる。
【００７７】
次に、本発明の実施の形態１にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れについて説明する。図３に本発明の実施の形態１にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れ図を示す。
【００７８】
図３において、まず暗号化された暗号文Ｘを入力する（ステップＳ３０１）。なお、タイミングアタックあるいはＳＰＡを試みる悪意ある第三者が、秘密鍵を特定するためにダミーの暗号文Ｘｄを入力する場合も同様である。そして、入力された暗号文Ｘあるいはダミーの暗号文Ｘｄに掛け合わせる定数Ｃも入力する（ステップＳ３０２）。なお、定数Ｃは、秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有するものとする。
【００７９】
また、最終的に平文を求めるために必要となる補正値Ｃ-dp、Ｃ-dqを算出しておく（ステップＳ３０３）。ここで、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）であり、Ｃが定数であることから、最終的に平文を求めるために必要となる補正値Ｃ-dp、Ｃ-dqについても一定値となる。
【００８０】
そして、まず入力された定数Ｃと、暗号文Ｘあるいはダミーの暗号文Ｘｄとを乗算する（ステップＳ３０４）。次に、当該乗算結果に対して、（数６４）に示すような秘密鍵ｐ及びｑを剰余値とした剰余演算を実行する（ステップＳ３０５）。
【００８１】
【数６４】
Ｘp’＝Ｘ＊Ｃ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｃ ｍｏｄ ｑ
なお、本実施の形態１においては、Ｃ＞ｐ及びＣ＞ｑの関係から、常にＸ＊Ｃ＞ｐ及びＸ＊Ｃ＞ｑが成立していることから、どのような暗号文Ｘあるいはダミー暗号文Ｘｄが入力された場合であっても、当該剰余演算が実行されることになる。
【００８２】
次に、当該剰余演算の結果に対して、（数６５）に示すような中国人剰余定理に基づいたべき乗剰余演算を実行し（ステップＳ３０６）、事前に算出しておいた補正値Ｃ-dp及びＣ-dqを用いて、（数６６）に示すような補正演算を実行する（ステップＳ３０７）。
【００８３】
【数６５】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
【００８４】
【数６６】
Ｙp’＝Ｙp＊Ｃ-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊Ｃ-dqｍｏｄ ｑ
そして最後に、補正演算値Ｙp’及びＹq’に基づいて、暗号化される前の平文Ｙを（数６７）に従って算出することになる（ステップＳ３０８）。
【００８５】
【数６７】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
このように、Ｃ＞ｐ及びＣ＞ｑとなる定数Ｃを入力する暗号文Ｘに掛け合わせた演算結果について剰余演算及びべき乗剰余演算を実行してから補正することで、いかなる入力がなされた場合であっても必ず剰余演算が実行されるようになることから、演算処理時間の相違や電力消費量の波形の相違によって入力値と秘密鍵ｐ、ｑとの大小関係を求めることができない。したがって、タイミングアタックやＳＰＡに代表されるサイドチャネルアタックに対して強固な演算装置を提供することができる。
【００８６】
また、Ｃが定数であることから、補正値についても定数となり、乱数を用いた場合のように、乗算する値が変わるごとに補正値を算出する必要がない。したがって、復号化する演算処理が複雑になることなく、高速に演算処理を行うことが可能となる。
【００８７】
また、Ｃ＞ｐ及びＣ＞ｑを満足すれば良いことから、ｐとｑそれぞれについてＣp＞ｐ及びＣq＞ｑを満足する定数Ｃp及びＣqを定めるものであっても良い。すなわち、入力Ｘに対して必ず秘密鍵ｐより大きな定数Ｃp及び秘密鍵ｑより大きな定数Ｃqが乗算されていることから、Ｘ＊Ｃpは常にｐよりも、Ｘ＊Ｃqは常にｑよりも大きな値となる。したがって、剰余値ｐあるいはｑによる剰余演算が必ず実行されることから、タイミングアタックを用いる場合であっても、ＳＰＡを用いる場合であっても、剰余値ｐあるいはｑとの大小比較ができないことになる。
【００８８】
一方、Ｃp及びＣqは定数であることから、補正値Ｃp-dp、Ｃq-dqは一度計算しておけば足りることになる。したがって、剰余演算をするごとに補正値を導出する必要が無くなり、全体として演算処理負荷を軽減することができる。
【００８９】
このようにすることで、タイミングアタックやＳＰＡ等のサイドチャネルアタックに対して有効に保護することができると共に、演算処理負荷が増大することなく高速に演算処理を行うことが可能となる。
【００９０】
この場合のサイドチャネルアタック耐性を有する暗号演算装置の構成図は、図２と同様である。すなわち図２において、定数入力部２から秘密鍵ｐ及びｑとの間にＣp＞ｐ、Ｃq＞ｑの関係を有する定数Ｃp、Ｃqを入力することになる。入力された定数Ｃp、Ｃqは定数記憶部３に保存される。
【００９１】
なお、定数入力部２を設けない構成も考えられる。すなわち、実装時において、あらかじめ秘密鍵ｐ及びｑとの間にＣp＞ｐ、Ｃq＞ｑの関係を有する定数Ｃp、Ｃqを定数記憶部３に記憶させておき、ユーザに入力を要求しない構成である。実装時には定数Ｃp、Ｃqを事前に定めておくことも考えられるからである。
【００９２】
また、補正値演算部４においては、最終的に平文を求めるために必要となる補正値Ｃp-dp、ＣqＣ-dqを求める。ここで、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）であり、Ｃp及びＣqが定数であることから、最終的に平文を求めるために必要となる補正値Ｃp-dp、Ｃq-dqについても一定値となる。算出された補正値Ｃp-dp、Ｃq-dqは、補正値記憶部５に保存される。
【００９３】
なお、定数入力部２と同様、補正値演算部４を設けない構成も考えられる。すなわち、実装時において、定数記憶部３に記憶されている定数Ｃp及びＣqに基づいて、事前に補正値Ｃp-dp、Ｃq-dqを算出して補正値記憶部５に記憶させておく構成である。こうすることで演算処理負荷を軽減できることが期待できるからである。
【００９４】
そして、定数乗算部６において、定数記憶部３に保存されている定数Ｃp及びＣqと、暗号文入力部１で入力された暗号文Ｘあるいはダミーの暗号文Ｘｄとを乗算する。暗号文Ｘに対する乗算は（数６８）に示すようになる。（数６８）により乗算した結果Ｘp、Ｘqについては、乗算結果記憶部７に保存される。
【００９５】
【数６８】
Ｘp＝Ｘ＊Ｃp
Ｘq＝Ｘ＊Ｃq
次に、剰余演算部８において、乗算結果記憶部７に保存されている乗算結果に対して、（数６９）に示すような秘密鍵ｐ及びｑを剰余値とした剰余演算を、各々実行する。ここでは、Ｃp＞ｐ及びＣq＞ｑの関係から、常にＸ＊Ｃp＞ｐ及びＸ＊Ｃq＞ｑが成立する。したがって、剰余演算部８においては、暗号文入力部１においてどのような入力がなされた場合であっても剰余演算を行うことになる。（数６９）により算出された剰余演算の結果であるＸp’及びＸq’は、剰余演算結果記憶部９に保存される。
【００９６】
【数６９】
Ｘp’＝Ｘpｍｏｄ ｐ
Ｘq’＝Ｘqｍｏｄ ｑ
そして、中国人剰余ＲＳＡ処理部１０において、剰余演算結果記憶部９に保存されている剰余演算の結果に対して、（数７０）に示すような中国人剰余定理に基づいたべき乗剰余演算を行う。（数７０）に示すべき乗剰余演算の演算結果がＹp及びＹqは、べき乗剰余演算結果記憶部１１に保存される。
【００９７】
【数７０】
0004086503.tif 000004
そして、補正処理部１２において、事前に算出して補正値記憶部５に保存されている補正値Ｃp-dp及びＣq-dqを用いて、入力値ＸあるいはＸｄについて、べき乗剰余演算を行った場合における演算結果へと（数７１）に従って補正する。なお、Ｃp及びＣqが定数であることから、補正値Ｃp-dp及びＣq-dqについても定数となっており、補正演算値Ｙp’及びＹq’を求める演算処理は一回行えば足りることになる。補正演算値Ｙp’及びＹq’については、補正結果記憶部１３に保存されることになる。
【００９８】
【数７１】
0004086503.tif 000005
最後に平文出力部１４において、補正処理部１２において補正され、補正結果記憶部１３に保存されている補正演算値Ｙp’及びＹq’に基づいて、（数７２）に示すように暗号化される前の平文Ｙを算出することになる。
【００９９】
【数７２】
Ｙ’＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
以上のような構成とすることにより、定数Ｃを乗算した場合と同様に、秘密鍵ｐ及びｑを知っている正当なユーザは、通常の演算処理と大差ない演算処理負荷で平文Ｙを求めることができ、一方、不正に解読を試みる悪意ある第三者にとっては、サイドチャネルアタックによって秘密鍵を求めることができないことから、暗号としての安全性を確保することが可能となる。
【０１００】
次に、かかる場合におけるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れについて説明する。図４に、定数Ｃp及びＣqを用いた実施の形態１にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れ図を示す。
【０１０１】
図４において、まず暗号化された暗号文Ｘを入力する（ステップＳ４０１）。なお、タイミングアタックあるいはＳＰＡを試みる悪意ある第三者が、秘密鍵を特定するためにダミーの暗号文Ｘｄを入力する場合も同様である。そして、入力された暗号文Ｘあるいはダミーの暗号文Ｘｄに掛け合わせる定数Ｃp及びＣqも入力する（ステップＳ４０２）。なお、定数Ｃp及びＣqは、秘密鍵ｐ及びｑとの間にＣp＞ｐ、Ｃq＞ｑの関係を有するものとする。
【０１０２】
また、最終的に平文を求めるために必要となる補正値Ｃp-dp、Ｃq-dqを算出しておく（ステップＳ４０３）。ここで、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）であり、Ｃp及びＣpが定数であることから、最終的に平文を求めるために必要となる補正値Ｃp-dp、Ｃq-dqについても一定値となる。
【０１０３】
そして、まず入力された定数Ｃp及びＣqと、暗号文Ｘあるいはダミーの暗号文Ｘｄとを乗算する（ステップＳ４０４）。次に、当該乗算結果に対して、（数７３）に示すような秘密鍵ｐ及びｑを剰余値とした剰余演算を実行する（ステップＳ４０５）。
【０１０４】
【数７３】
Ｘp’＝Ｘ＊Ｃp ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｃq ｍｏｄ ｑ
なお、本実施例においては、Ｃp＞ｐ及びＣq＞ｑの関係から、常にＸ＊Ｃp＞ｐ及びＸ＊Ｃq＞ｑが成立していることから、どのような暗号文Ｘあるいはダミー暗号文Ｘｄが入力された場合であっても、当該剰余演算が実行されることになる。
【０１０５】
次に、当該剰余演算の結果に対して、（数７４）に示すような中国人剰余定理に基づいたべき乗剰余演算を実行し（ステップＳ４０６）、事前に算出しておいた補正値Ｃp-dp及びＣq-dqを用いて、（数７５）に示すような補正演算を実行する（ステップＳ４０７）。
【０１０６】
【数７４】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
【０１０７】
【数７５】
Ｙp’＝Ｙp＊Ｃp-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊Ｃq-dqｍｏｄ ｑ
そして最後に、補正演算値Ｙp’及びＹq’に基づいて、暗号化される前の平文Ｙを（数７６）に従って算出することになる（ステップＳ４０８）。
【０１０８】
【数７６】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
このように、Ｃp＞ｐ及びＣq＞ｑとなる定数Ｃp及びＣqを入力する暗号文Ｘに掛け合わせた演算結果について剰余演算及びべき乗剰余演算を実行してから補正することで、いかなる入力がなされた場合であっても必ず剰余演算が実行されるようになることから、演算処理時間の相違や電力消費量の波形の相違によって入力値と秘密鍵ｐ、ｑとの大小関係を求めることができない。したがって、タイミングアタックやＳＰＡに代表されるサイドチャネルアタックに対して強固な演算装置を提供することができる。
【０１０９】
また、Ｃp及びＣqが定数であることから、補正値についても定数となり、乱数を用いた場合のように、乗算する値が変わるごとに補正値を算出する必要がない。したがって、復号化する演算処理が複雑になることなく、高速に演算処理を行うことが可能となる。
【０１１０】
なお、ここまで本実施の形態１においては、Ｎ＝ｐ＊ｑのように、Ｎが互いに素である２つの数の乗算による場合について説明しているが、中国人剰余定理自体は、（数７７）に示すように、Ｎが互いに素である複数の数の乗算による場合にも成立する。
【０１１１】
【数７７】
Ｎ＝ｐ（０）α(0)＊ｐ（１）α(1)＊・・＊ｐ（ｎ）α(n)
ただし、ｎ≧２又はα（０）≧２
したがって、互いに素である複数の数にまで中国人剰余定理を拡張することによっても上述した演算と同様の関係が成立し、タイミングアタックやＳＰＡに代表されるサイドチャネルアタックに対して強固な演算装置を提供することが可能となる。
【０１１２】
また、（数６１）に示すような中国人剰余定理に基づいたべき乗剰余演算を行う場合には、べき数の各ビット値に基づいて算出するバイナリメソッドと、Ｋビットの事前計算テーブルを準備して処理を行うウィンドウメソッドとが良く知られているが、本実施の形態１においては、どちらの算出方法についても適用可能である。
【０１１３】
なお、本実施の形態１にかかる演算装置及び方法は、一般的なＲＳＡ方式の暗号文だけでなく、ＥＰＯＣ暗号やｅ−ｓｉｇｎ等、秘密情報を剰余数に使用してべき乗剰余演算を行う全ての方式に適用可能であり、その際の効果についても同じである。
【０１１４】
以上のように本実施の形態１によれば、コンピュータ上へ当該プログラムをロードさせ実行することで、いかなる入力がなされた場合であっても、常に剰余演算が実行されることになることから、演算処理時間や電力消費量の波形等の相違によって入力値と秘密鍵ｐ又はｑとの大小関係を特定することができず、サイドチャネルアタックに対して安全性の高い復号化演算方法を提供することができる。
【０１１５】
また、定数に基づいて補正値を算出することから、補正値を求める演算は最初の１回で済み、全体としての演算処理負荷も小さくなることが期待できる。
【０１１６】
（実施の形態２）
次に本発明の実施の形態２にかかるサイドチャネルアタック耐性を有する暗号演算装置について、図面を参照しながら説明する。実施の形態２においては、べき乗剰余演算にモンゴメリべき乗剰余演算を適用すると共に、実施の形態１における定数Ｃの代わりにモンゴメリパラメタＲを用いる点に特徴を有する。
【０１１７】
すなわち、モンゴメリべき乗剰余演算を行うための前提条件より、モンゴメリパラメタＲは必ず秘密鍵ｐあるいはｑのどちらよりも大きな値となっていることから、Ｘ＊Ｒは常にｐあるいはｑよりも大きな値となる。したがって、どのような入力Ｘがなされた場合であっても剰余値ｐあるいはｑによる剰余演算が必ず実行されることから、タイミングアタックを用いる場合であっても、ＳＰＡを用いる場合であっても、剰余値ｐあるいはｑとの大小比較ができないことになる。
【０１１８】
一方、実施の形態１とは異なり、本実施の形態２においては補正演算を不要とすることができる。すなわち、まず本実施の形態２において、剰余演算の次に実行するべき乗剰余演算として、関数ＭＯＮＴ＿ＥＸＰを（数７８）のように定める。
【０１１９】
【数７８】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
（数７８）において、入力ＸをＸＲ ｍｏｄ ｐとし、べき数をｄ、剰余数を一方の秘密鍵ｐとすると、（数７９）に示すように、直接べき乗剰余演算値Ｘd ｍｏｄ ｐを求めることができる。
【０１２０】
【数７９】
0004086503.tif 000006
他方の秘密鍵ｑについても同様の計算を行うことができることから、特に補正演算を実行することなく、直接べき乗剰余演算値を求めることが可能となる。したがって、補正値を導出したり、それを用いた補正演算を実行する必要が無くなることから、全体として演算処理負荷を軽減することが可能となる。
【０１２１】
また、モンゴメリべき乗剰余演算剰余を計算する場合には、べき数の各ビットの値に基づいて算出するバイナリメソッドと、Ｋビットの事前計算テーブルを準備して処理を行うウィンドウメソッドとが良く知られているが、本実施の形態２については、どちらの算出方法も適用することが可能である。
【０１２２】
このような演算方法とすることによって、タイミングアタックやＳＰＡ等のサイドチャネルアタックに対して有効に保護することができると共に、演算処理負荷が増大することなく高速に演算処理を行うことが可能となる。なお、モンゴメリパラメタＲとしては、２512あるいは２1024等が代表的なものとして考えられる。
【０１２３】
具体的な構成を図５に示す。図５は本発明の実施の形態２にかかるサイドチャネルアタック耐性を有する暗号演算装置の構成図である。なお、本実施の形態２においては、中国人剰余定理を用いたＲＳＡ処理における復号化処理を行う場合について説明する。
【０１２４】
図５において、１は、実施の形態１と同様に暗号文入力部を示しており、暗号化された暗号文Ｘを復号化するために入力するものである。タイミングアタックあるいはＳＰＡを行う第三者が、秘密鍵を特定するためにダミーの暗号文Ｘｄを入力するのも暗号文入力部１である。入力された暗号文ＸあるいはＸｄは、モンゴメリパラメタ乗算部２１へ渡される。
【０１２５】
次に、２１はモンゴメリパラメタ乗算部を示しており、暗号文入力部１から入力された暗号文Ｘあるいはダミーの暗号文Ｘｄに、モンゴメリパラメタＲを乗算するものである。なお、モンゴメリべき乗剰余演算の前提条件より、モンゴメリパラメタＲは、秘密鍵ｐ及びｑとの間にＲ＞ｐ、Ｒ＞ｑの関係を有することになる。したがって、本実施の形態２においても実施の形態１と同様に、常にＸ＊Ｒ＞ｐ及びＸ＊Ｒ＞ｑが成立する。暗号文Ｘに対する乗算は（数８０）に示すようになる。（数８０）により乗算した結果Ｘ’については、乗算結果記憶部２２に保存される。
【０１２６】
【数８０】
Ｘ’＝Ｘ＊Ｒ
次に、８は剰余演算部を示しており、乗算結果記憶部２２に保存されている乗算結果に対して、秘密鍵ｐ及びｑを剰余値とした剰余演算を、各々実行するものである。先述したように本実施の形態２においては、Ｒ＞ｐ及びＲ＞ｑの関係から、常にＸ＊Ｒ＞ｐ及びＸ＊Ｒ＞ｑが成立する。したがって、剰余演算部８においては、暗号文入力部１においてどのような入力がなされた場合であっても剰余演算を行うことになる。
【０１２７】
本実施の形態２における剰余演算は（数８１）のように表すことができる。（数８１）により算出された剰余演算の結果であるＸp’及びＸq’は、剰余演算結果記憶部９に保存される。
【０１２８】
【数８１】
Ｘp’＝Ｘ’ｍｏｄ ｐ
Ｘq’＝Ｘ’ｍｏｄ ｑ
また、２３はモンゴメリべき乗剰余演算部を示しており、剰余演算結果記憶部９に保存されている剰余演算の結果に対して、（数８２）に示すモンゴメリべき乗剰余演算を実行するものである。（数８２）に示すモンゴメリべき乗剰余演算の演算結果Ｙp及びＹqは、モンゴメリべき乗剰余演算結果記憶部２４に保存される。
【０１２９】
【数８２】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
なお、モンゴメリべき乗剰余演算を実行するための関数ＭＯＮＴ＿ＥＸＰについては（数８３）のように定義する。
【０１３０】
【数８３】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
そして、（数８２）におけるＹp及びＹqは、（数８４）に示すように、中国人剰余定理を用いて直接べき乗剰余演算を行った場合の結果と一致することになる。したがって、補正演算自体が不要となる。
【０１３１】
【数８４】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dpｍｏｄ ｑ
最後に１４は平文出力部を示しており、モンゴメリべき乗剰余演算部２３において算出され、モンゴメリべき乗剰余演算結果記憶部２４に保存されている演算値Ｙp及びＹqに基づいて、（数８５）に示すように暗号化される前の平文Ｙを算出するものである。入力値がダミー暗号文Ｘｄの場合には誤った計算値を出力することになるが、サイドチャネルアタックにおいては、算出された値は問題とならない。
【０１３２】
【数８５】
Ｙ＝（ａ（Ｙp−Ｙq）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
以上のような構成とすることにより、秘密鍵ｐ及びｑを知っている正当なユーザは、通常の演算処理と大差ない演算処理負荷で平文Ｙを求めることができ、一方、不正に解読を試みる悪意ある第三者にとっては、サイドチャネルアタックによって秘密鍵を求めることができないことから、暗号としての安全性を確保することが可能となる。
【０１３３】
次に、本発明の実施の形態２にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れについて説明する。図６に本発明の実施の形態２にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れ図を示す。
【０１３４】
図６において、まず暗号文Ｘを入力し（ステップＳ６０１）、モンゴメリパラメタＲを乗算する（ステップＳ６０２）。なお、モンゴメリべき乗剰余演算の前提条件より、モンゴメリパラメタＲは、秘密鍵ｐ及びｑとの間にＲ＞ｐ、Ｒ＞ｑの関係を有することになる。したがって、本実施の形態２においても実施の形態１と同様に、常にＸ＊Ｒ＞ｐ及びＸ＊Ｒ＞ｑが成立する。タイミングアタックあるいはＳＰＡを行う第三者が、秘密鍵を特定するためにダミーの暗号文Ｘｄを入力する場合も同様の処理となる。
【０１３５】
次に、暗号文ＸとモンゴメリパラメタＲとの乗算結果に対して、（数８６）に示すように秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する（ステップＳ６０３）。本実施の形態２においては、常にＸ＊Ｒ＞ｐ及びＸ＊Ｒ＞ｑが成立していることから、どのような暗号文Ｘが入力された場合であっても、剰余演算が実行されることになる。
【０１３６】
【数８６】
Ｘp’＝Ｘ＊Ｒ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒ ｍｏｄ ｑ
そして、剰余演算における演算結果を用いて、（数８７）に示すモンゴメリべき乗剰余演算を実行する（ステップＳ６０４）。なお、モンゴメリべき乗剰余演算に用いる関数ＭＯＮＴ＿ＥＸＰについては、（数８８）に定義されるものとなる。
【０１３７】
【数８７】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
【０１３８】
【数８８】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
そして、（数８７）におけるＹp及びＹqは、（数８９）に示すように、中国人剰余定理を用いて直接べき乗剰余演算を行った場合の結果と一致することになる。したがって、補正演算自体が不要となる。
【０１３９】
【数８９】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
最後に、モンゴメリべき乗剰余演算により算出された演算値Ｙp及びＹqに基づいて、（数９０）に示すように暗号化される前の平文Ｙを算出する（ステップＳ６０５）。
【０１４０】
【数９０】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
以上のような処理を実行することによって、秘密鍵ｐ及びｑを知っている正当なユーザは、通常の演算処理と大差ない演算処理負荷で平文Ｙを求めることができ、一方、不正に解読を試みる悪意ある第三者にとっては、サイドチャネルアタックによって秘密鍵を求めることができないことから、暗号としての安全性を確保することが可能となる。
【０１４１】
また、Ｒ＞ｐ及びＲ＞ｑを満足すれば良いことから、ｐとｑそれぞれについてＲp＞ｐ及びＲq＞ｑを満足するモンゴメリパラメタＲp及びＲqを用いるものであっても良い。すなわち、入力Ｘに対して必ず秘密鍵ｐより大きなモンゴメリパラメタＲp及び秘密鍵ｑより大きなモンゴメリパラメタＲqが乗算されていることから、Ｘ＊Ｒpは常にｐよりも、Ｘ＊Ｒqは常にｑよりも大きな値となる。したがって、剰余値ｐあるいはｑによる剰余演算が必ず実行されることから、タイミングアタックを用いる場合であっても、ＳＰＡを用いる場合であっても、剰余値ｐあるいはｑとの大小比較ができないことになる。
【０１４２】
この場合のサイドチャネルアタック耐性を有する暗号演算装置の構成図は図５と同様である。図５において、モンゴメリパラメタ乗算部２１では、暗号文入力部１から入力された暗号文Ｘあるいはダミーの暗号文Ｘｄに、モンゴメリパラメタＲp又はＲqを乗算することになる。なお、モンゴメリべき乗剰余演算の前提条件より、モンゴメリパラメタＲは、秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有することになる。したがって、本実施の形態２においても実施の形態１と同様に、常にＸ＊Ｒp＞ｐ及びＸ＊Ｒq＞ｑが成立する。暗号文Ｘに対する乗算は（数９１）に示すようになる。（数９１）により乗算した結果Ｘp及びＸqについては、乗算結果記憶部２２に保存される。
【０１４３】
【数９１】
Ｘp＝Ｘ＊Ｒp
Ｘq＝Ｘ＊Ｒq
次に、剰余演算部８において、乗算結果記憶部２２に保存されている乗算結果に対して、秘密鍵ｐ及びｑを剰余値とした剰余演算を、各々実行する。先述したように本実施の形態２においては、Ｒp＞ｐ及びＲq＞ｑの関係から、常にＸ＊Ｒp＞ｐ及びＸ＊Ｒq＞ｑが成立する。したがって、剰余演算部８においては、暗号文入力部１においてどのような入力がなされた場合であっても剰余演算を行うことになる。
【０１４４】
本実施の形態２における剰余演算は（数９２）のように表すことができる。（数９２）により算出された剰余演算の結果であるＸp’及びＸq’は、剰余演算結果記憶部９に保存される。
【０１４５】
【数９２】
Ｘp’＝Ｘpｍｏｄ ｐ
Ｘq’＝Ｘqｍｏｄ ｑ
次に、モンゴメリべき乗剰余演算部２３において、剰余演算結果記憶部９に保存されている剰余演算の結果に対して、（数９３）に示すモンゴメリべき乗剰余演算を実行する。（数９３）に示すモンゴメリべき乗剰余演算の演算結果Ｙp及びＹqは、モンゴメリべき乗剰余演算結果記憶部２４に保存される。
【０１４６】
【数９３】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒp，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒq，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
なお、モンゴメリべき乗剰余演算を実行するための関数ＭＯＮＴ＿ＥＸＰについては（数９４）のように定義する。
【０１４７】
【数９４】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
そして、（数９３）におけるＹp及びＹqは、（数９５）に示すように、中国人剰余定理を用いて直接べき乗剰余演算を行った場合の結果と一致することになる。したがって、補正演算自体が不要となる。
【０１４８】
【数９５】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dpｍｏｄ ｑ
最後に平文出力部１４において、モンゴメリべき乗剰余演算部２３において算出され、モンゴメリべき乗剰余演算結果記憶部２４に保存されている演算値Ｙp及びＹqに基づいて、（数９６）に示すように暗号化される前の平文Ｙを算出する。
【０１４９】
【数９６】
Ｙ＝（ａ（Ｙp−Ｙq）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
以上のような構成とすることにより、秘密鍵ｐ及びｑを知っている正当なユーザは、通常の演算処理と大差ない演算処理負荷で平文Ｙを求めることができ、一方、不正に解読を試みる悪意ある第三者にとっては、サイドチャネルアタックによって秘密鍵を求めることができないことから、暗号としての安全性を確保することが可能となる。
【０１５０】
次に、モンゴメリパラメタＲp及びＲpを用いた本実施の形態２にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れについて説明する。図７に本実施例にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れ図を示す。
【０１５１】
図７において、まず暗号文Ｘを入力し（ステップＳ７０１）、モンゴメリパラメタＲp又はＲqを乗算する（ステップＳ７０２）。なお、モンゴメリべき乗剰余演算の前提条件より、モンゴメリパラメタＲp及びＲqは、秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有することになる。したがって、本実施例においても、常にＸ＊Ｒp＞ｐ及びＸ＊Ｒq＞ｑが成立する。タイミングアタックあるいはＳＰＡを行う第三者が、秘密鍵を特定するためにダミーの暗号文Ｘｄを入力する場合も同様の処理となる。
【０１５２】
次に、暗号文ＸとモンゴメリパラメタＲとの乗算結果に対して、（数９７）に示すように秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する（ステップＳ７０３）。本実施の形態２においては、常にＸ＊Ｒp＞ｐ及びＸ＊Ｒq＞ｑが成立していることから、どのような暗号文Ｘが入力された場合であっても、剰余演算が実行されることになる。
【０１５３】
【数９７】
Ｘp’＝Ｘ＊Ｒp ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒq ｍｏｄ ｑ
そして、剰余演算における演算結果を用いて、（数９８）に示すモンゴメリべき乗剰余演算を実行する（ステップＳ７０４）。なお、モンゴメリべき乗剰余演算に用いる関数ＭＯＮＴ＿ＥＸＰについては、（数９９）に定義されるものとなる。
【０１５４】
【数９８】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒp，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒq，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
【０１５５】
【数９９】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
そして、（数９８）におけるＹp及びＹqは、（数１００）に示すように、中国人剰余定理を用いて直接べき乗剰余演算を行った場合の結果と一致することになる。したがって、補正演算自体が不要となる。
【０１５６】
【数１００】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
最後に、モンゴメリべき乗剰余演算により算出された演算値Ｙp及びＹqに基づいて、（数１０１）に示すように暗号化される前の平文Ｙを算出する（ステップＳ７０５）。
【０１５７】
【数１０１】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
なお、ここまで本実施の形態２においては、Ｎ＝ｐ＊ｑのように、Ｎが互いに素である２つの数の乗算による場合について説明しているが、中国人剰余定理自体は、（数１０２）に示すように、Ｎが互いに素である複数の数の乗算による場合にも成立する。
【０１５８】
【数１０２】
Ｎ＝ｐ（０）α(0)＊ｐ（１）α(1)＊・・＊ｐ（ｎ）α(n)
ただし、ｎ≧２又はα（０）≧２
したがって、互いに素である複数の数にまで中国人剰余定理を拡張することによっても上述した演算と同様の関係が成立し、タイミングアタックやＳＰＡに代表されるサイドチャネルアタックに対して強固な演算装置を提供することが可能となる。
【０１５９】
また、（数９８）に示すようなモンゴメリべき乗剰余演算を行う場合には、べき数の各ビット値に基づいて算出するバイナリメソッドと、Ｋビットの事前計算テーブルを準備して処理を行うウィンドウメソッドとが良く知られているが、本実施の形態２においては、どちらの算出方法についても適用可能である。
【０１６０】
なお、本実施の形態２にかかる演算装置及び方法は、一般的なＲＳＡ方式の暗号文だけでなく、ＥＰＯＣ暗号やｅ−ｓｉｇｎ等、秘密情報を剰余数に使用してべき乗剰余演算を行う全ての方式に適用可能であり、その際の効果についても同じである。
【０１６１】
以上のように本実施の形態２によれば、いかなる入力がなされた場合であっても、常に剰余演算が実行されることになることから、演算処理時間や電力消費量の波形等の相違によって入力値と秘密鍵ｐ又はｑとの大小関係を特定することができず、サイドチャネルアタックに対して安全性の高い復号化演算方法を提供することができる。
【０１６２】
また、補正演算を行う必要性が無いことから、全体としての演算処理負荷がより小さくなることが期待できる。
【０１６３】
（実施の形態３）
次に、本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置について、図面を参照しながら説明する。実施の形態３においては、べき乗剰余演算にモンゴメリべき乗剰余演算を適用すると共に、実施の形態１における定数Ｃ、あるいは実施の形態２におけるモンゴメリパラメタＲの代わりに、モンゴメリパラメタＲの剰余値ｐに対する剰余演算値Ｒp’＝Ｒ ｍｏｄ ｐ及びＲq’＝Ｒ ｍｏｄ ｑを用いる点に特徴を有する。
【０１６４】
すなわち、モンゴメリべき乗剰余演算を行うための前提条件より、モンゴメリパラメタＲは必ず秘密鍵ｐあるいはｑのどちらよりも大きな値となっている。しかしながら、Ｒp’又はＲq’については常にｐあるいはｑよりも大きな値となるとは限らないことから、Ｒp’又はＲq’の大きさによって剰余値ｐ又はｑによる剰余演算が実行されるか否かが決定する。
【０１６５】
ここで、Ｒp’又はＲq’については外部からの攻撃者にとっては未知の数であることから、剰余値ｐ又はｑを特定することができないことになる。すなわち、タイミングアタックを用いる場合であっても、ＳＰＡを用いる場合であっても、剰余値ｐあるいはｑの近傍にまでは接近できるものの、特定するまでには至らないことになる。
【０１６６】
一方、実施の形態２と同様に、本実施の形態３においては補正演算を不要とすることができる。すなわち、まず本実施の形態３において、剰余演算の次に実行するべき乗剰余演算として、関数ＭＯＮＴ＿ＥＸＰを（数１０３）のように定める。
【０１６７】
【数１０３】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
（数１０３）において、入力Ｘを（ＸＲp’）ｍｏｄ ｐとし、べき数をｄ、剰余数を一方の秘密鍵ｐとすると、（数１０４）に示すように、直接べき乗剰余演算値Ｘd ｍｏｄ ｐを求めることができる。
【０１６８】
【数１０４】
0004086503.tif 000007
他方の秘密鍵ｑについても同様の計算を行うことができることから、特に補正演算を実行することなく、直接べき乗剰余演算値を求めることが可能となる。したがって、補正値を導出したり、それを用いた補正演算を実行する必要が無くなることから、全体として演算処理負荷を軽減することが可能となる。
【０１６９】
また、実施の形態２と同様に、べき数の各ビットの値に基づいて算出するバイナリメソッドと、Ｋビットの事前計算テーブルを準備して処理を行うウィンドウメソッドとの、どちらの算出方法も適用することが可能である。
【０１７０】
このような演算方法とすることによって、タイミングアタックやＳＰＡ等のサイドチャネルアタックに対して有効に保護することができると共に、演算処理負荷が増大することなく高速に演算処理を行うことが可能となる。なお、モンゴメリパラメタＲとしては、２512あるいは２1024等が代表的なものとして考えられる。
【０１７１】
具体的な構成を図８に示す。図８は本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置の構成図である。なお、本実施の形態３においては、中国人剰余定理を用いたＲＳＡ処理における復号化処理を行う場合について説明する。
【０１７２】
図８において、１は、実施の形態１及び２と同様に暗号文入力部を示しており、暗号化された暗号文Ｘを復号化するために入力するものである。タイミングアタックあるいはＳＰＡを行う第三者が、秘密鍵を特定するためにダミーの暗号文Ｘｄを入力するのも暗号文入力部１である。入力された暗号文ＸあるいはＸｄは、モンゴメリパラメタ剰余演算部３１へ渡される。
【０１７３】
次に、３１はモンゴメリパラメタ剰余演算部を示しており、モンゴメリパラメタＲについて、剰余値ｐ又はｑに対する剰余演算を行うものである。かかる剰余演算は（数１０５）に示すようになる。（数１０５）により演算した結果Ｘ’については、モンゴメリパラメタ剰余演算結果記憶部３２に保存される。
【０１７４】
【数１０５】
Ｒp’＝Ｒ ｍｏｄ ｐ
Ｒq’＝Ｒ ｍｏｄ ｑ
次に、３３は剰余値乗算部を示しており、モンゴメリパラメタ剰余演算部３１において演算された剰余演算値に対して、暗号文入力部１から入力された暗号文Ｘあるいはダミーの暗号文Ｘｄを乗算するものである。暗号文Ｘに対する乗算は（数１０６）に示すようになる。（数１０６）により乗算した結果Ｘp’及びＸq’については、乗算結果記憶部３４に保存される。
【０１７５】
【数１０６】
Ｘp’＝Ｘ＊Ｒp’
Ｘq’＝Ｘ＊Ｒp’
次に、８は剰余演算部を示しており、乗算結果記憶部３４に保存されている乗算結果に対して、秘密鍵ｐ及びｑを剰余値とした剰余演算を、各々実行するものである。先述したように本実施の形態２においては、Ｒ＞ｐ及びＲ＞ｑの関係から、常にＸ＊Ｒ＞ｐ及びＸ＊Ｒ＞ｑが成立するが、本実施の形態３においては成立しない。剰余演算をするか否かは、Ｒp’又はＲp’の大きさに依存する。
【０１７６】
本実施の形態３における剰余演算は（数１０７）のように表すことができる。（数１０７）により算出された剰余演算の結果であるＸp及びＸqは、剰余演算結果記憶部９に保存される。
【０１７７】
【数１０７】
Ｘp＝Ｘp’ｍｏｄ ｐ
Ｘq＝Ｘq’ｍｏｄ ｑ
また、２３はモンゴメリべき乗剰余演算部を示しており、剰余演算結果記憶部９に保存されている剰余演算の結果に対して、（数１０８）に示すモンゴメリべき乗剰余演算を実行するものである。ここでは、（数１０８）に示すようなモンゴメリべき乗剰余演算が実行される。（数１０８）に示すモンゴメリべき乗剰余演算の演算結果Ｙp及びＹqは、モンゴメリべき乗剰余演算結果記憶部２４に保存される。
【０１７８】
【数１０８】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
そして、（数１０８）におけるＹp及びＹqは、（数１０９）に示すように、中国人剰余定理を用いて直接べき乗剰余演算を行った場合の結果と一致することになる。したがって、補正演算自体が不要となる。
【０１７９】
【数１０９】
Ｙp＝Ｘpdpｍｏｄ ｐ
Ｙq＝Ｘqdqｍｏｄ ｑ
最後に１４は平文出力部を示しており、モンゴメリべき乗剰余演算部２３において算出され、モンゴメリべき乗剰余演算結果記憶部２４に保存されている演算値Ｙp及びＹqに基づいて、（数１１０）に示すように暗号化される前の平文Ｙを算出するものである。入力値がダミー暗号文Ｘｄの場合には誤った計算値を出力することになるが、サイドチャネルアタックにおいては、算出された値は問題とならない。
【０１８０】
【数１１０】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
以上のような構成とすることにより、秘密鍵ｐ及びｑを知っている正当なユーザは、通常の演算処理と大差ない演算処理負荷で平文Ｙを求めることができ、一方、不正に解読を試みる悪意ある第三者にとっては、サイドチャネルアタックによって秘密鍵を求めることができないことから、暗号としての安全性を確保することが可能となる。
【０１８１】
次に、本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れについて説明する。図９に本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れ図を示す。
【０１８２】
図９において、まず暗号文Ｘを入力する（ステップＳ９０１）。タイミングアタックあるいはＳＰＡを行う第三者が、秘密鍵を特定するためにダミーの暗号文Ｘｄを入力する場合も同様の処理となる。
【０１８３】
そして、モンゴメリパラメタＲについて、剰余値ｐ又はｑについての剰余演算を実行し（ステップＳ９０２）、（数１１１）に示すように入力した暗号文Ｘと乗算する（ステップＳ９０３）。
【０１８４】
【数１１１】
Ｘp’＝Ｘ＊Ｒ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒ ｍｏｄ ｑ
次に、暗号文Ｘと剰余演算値との乗算結果Ｘp’及びＸq’に対して、（数１１２）に示すように秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する（ステップＳ９０４）。
【０１８５】
【数１１２】
Ｘp＝Ｘp’ ｍｏｄ ｐ
Ｘq＝Ｘq’ ｍｏｄ ｑ
そして、剰余演算における演算結果を用いて、（数１１３）に示すモンゴメリべき乗剰余演算を実行する（ステップＳ９０５）。なお、モンゴメリべき乗剰余演算に用いる関数ＭＯＮＴ＿ＥＸＰは、（数１１４）に定義されるものとする。
【０１８６】
【数１１３】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
【０１８７】
【数１１４】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
そして、（数１１３）におけるＹp及びＹqは、（数１１５）に示すように、中国人剰余定理を用いて直接べき乗剰余演算を行った場合の結果と一致することになる。したがって、補正演算自体が不要となる。
【０１８８】
【数１１５】
Ｙp＝Ｘpdpｍｏｄ ｐ
Ｙq＝Ｘqdqｍｏｄ ｑ
最後に、モンゴメリべき乗剰余演算により算出された演算値Ｙp及びＹqに基づいて、（数１１６）に示すように暗号化される前の平文Ｙを算出する（ステップＳ９０６）。
【０１８９】
【数１１６】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
以上のような処理を実行することによって、秘密鍵ｐ及びｑを知っている正当なユーザは、通常の演算処理と大差ない演算処理負荷で平文Ｙを求めることができ、一方、不正に解読を試みる悪意ある第三者にとっては、サイドチャネルアタックによって秘密鍵を求めることができないことから、暗号としての安全性を確保することが可能となる。
【０１９０】
また、実施の形態２と同様に、秘密鍵ｐ及びｑのそれぞれについてＲp＞ｐ及びＲq＞ｑを満足するモンゴメリパラメタＲp及びＲqを用いるものであっても良い。この場合も剰余値Ｒp’＝Ｒpｍｏｄ ｐ又はＲq’＝Ｒqｍｏｄ ｑについては常にｐあるいはｑよりも大きな値となるとは限らないことから、Ｒp’又はＲq’の大きさによって剰余値ｐ又はｑによる剰余演算が実行されるか否かが決定する。
【０１９１】
ここで、Ｒp’又はＲq’については外部からの攻撃者にとっては未知の数であることから、剰余値ｐ又はｑを特定することができないことになる。すなわち、タイミングアタックを用いる場合であっても、ＳＰＡを用いる場合であっても、剰余値ｐあるいはｑの近傍にまでは接近できるものの、特定するまでには至らないことになる。
【０１９２】
一方、モンゴメリパラメタＲを用いる場合と同様に、本実施例においても補正演算を不要とすることができる。すなわち、剰余演算の次に実行するべき乗剰余演算として、関数ＭＯＮＴ＿ＥＸＰを（数１１７）のように定める。
【０１９３】
【数１１７】
Ｒp＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒp，ｐ）＝（Ｘ＊Ｒp-1）dｍｏｄ ｐ
（数１１７）において、入力Ｘを（Ｘ＊Ｒp’）ｍｏｄ ｐとし、べき数をｄ、剰余数を一方の秘密鍵ｐとすると、（数１１８）に示すように、直接べき乗剰余演算値Ｘd ｍｏｄ ｐを求めることができる。
【０１９４】
【数１１８】
0004086503.tif 000008
他方の秘密鍵ｑについても同様の計算を行うことができることから、特に補正演算を実行することなく、直接べき乗剰余演算値を求めることが可能となる。したがって、補正値を導出したり、それを用いた補正演算を実行する必要が無くなることから、全体として演算処理負荷を軽減することが可能となる。
【０１９５】
また、実施の形態２と同様に、べき数の各ビットの値に基づいて算出するバイナリメソッドと、Ｋビットの事前計算テーブルを準備して処理を行うウィンドウメソッドとの、どちらの算出方法も適用することが可能である。
【０１９６】
このような演算方法とすることによって、タイミングアタックやＳＰＡ等のサイドチャネルアタックに対して有効に保護することができると共に、演算処理負荷が増大することなく高速に演算処理を行うことが可能となる。なお、モンゴメリパラメタＲpあるいはＲqとしては、２512あるいは２1024等が代表的なものとして考えられる。
【０１９７】
かかる場合におけるサイドチャネルアタック耐性を有する暗号演算装置の構成図は、図８と同様である。すなわち、図８に示すモンゴメリパラメタ剰余演算部３１において、モンゴメリパラメタＲp及びＲqについて、（数１１９）に示すように剰余値ｐ及びｑのそれぞれに対する剰余演算を行うことになる。（数１１９）により演算した結果Ｒp’及びＲq’については、モンゴメリパラメタ剰余演算結果記憶部３２に保存される。
【０１９８】
【数１１９】
Ｒp’＝Ｒp ｍｏｄ ｐ
Ｒq’＝Ｒq ｍｏｄ ｑ
次に、剰余値乗算部３３において、モンゴメリパラメタ剰余演算部３１において演算された剰余演算値に対して、（数１２０）に示すように暗号文入力部１から入力された暗号文Ｘあるいはダミーの暗号文Ｘｄを乗算する。（数１２０）により乗算した結果Ｘp’及びＸq’については、乗算結果記憶部３４に保存される。
【０１９９】
【数１２０】
Ｘp’＝Ｘ＊Ｒp’
Ｘq’＝Ｘ＊Ｒq’
そして、剰余演算部８において、乗算結果記憶部３４に保存されている乗算結果に対して、（数１２１）に示す秘密鍵ｐ及びｑを剰余値とした剰余演算を、各々実行することになる。先述したように本実施の形態３においては、剰余演算をするか否かは、Ｒp’又はＲp’の大きさに依存する。（数１２１）により算出された剰余演算の結果であるＸp及びＸqは、剰余演算結果記憶部９に保存される。
【０２００】
【数１２１】
Ｘp＝Ｘp’ｍｏｄ ｐ
Ｘq＝Ｘq’ｍｏｄ ｑ
次に、モンゴメリべき乗剰余演算部２３において、剰余演算結果記憶部９に保存されている剰余演算の結果に対して、（数１２２）に示すモンゴメリべき乗剰余演算を実行する。（数１２２）に示すモンゴメリべき乗剰余演算の演算結果Ｙp及びＹqは、モンゴメリべき乗剰余演算結果記憶部２４に保存される。
【０２０１】
【数１２２】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒp，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒq，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
そして、（数１２２）におけるＹp及びＹqは、（数１２３）に示すように、中国人剰余定理を用いて直接べき乗剰余演算を行った場合の結果と一致することになる。したがって、補正演算自体が不要となる。
【０２０２】
【数１２３】
Ｙp＝Ｘpdpｍｏｄ ｐ
Ｙq＝Ｘqdqｍｏｄ ｑ
最後に平文出力部１４において、モンゴメリべき乗剰余演算部２３において算出され、モンゴメリべき乗剰余演算結果記憶部２４に保存されている演算値Ｙp及びＹqに基づいて、（数１２４）に示すように暗号化される前の平文Ｙを算出することになる。
【０２０３】
【数１２４】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
以上のような構成とすることにより、モンゴメリパラメタが秘密鍵ｐとｑについて異なっている場合であっても、秘密鍵ｐ及びｑを知っている正当なユーザは、通常の演算処理と大差ない演算処理負荷で平文Ｙを求めることができ、一方、不正に解読を試みる悪意ある第三者にとっては、サイドチャネルアタックによって秘密鍵を求めることができないことから、暗号演算装置としての安全性を確保することが可能となる。
【０２０４】
次に、本実施例にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れについて説明する。図１０に本実施例にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムの処理の流れ図を示す。
【０２０５】
図１０において、まず暗号文Ｘを入力する（ステップＳ１００１）。タイミングアタックあるいはＳＰＡを行う第三者が、秘密鍵を特定するためにダミーの暗号文Ｘｄを入力する場合も同様の処理となる。
【０２０６】
そして、モンゴメリパラメタＲp及びＲqについて、剰余値ｐ又はｑについての剰余演算を実行し（ステップＳ１００２）、（数１２５）に示すように入力した暗号文Ｘと乗算する（ステップＳ１００３）。
【０２０７】
【数１２５】
Ｘp’＝Ｘ＊Ｒp ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒq ｍｏｄ ｑ
次に、暗号文Ｘと剰余演算値との乗算結果Ｘp’及びＸq’に対して、（数１２６）に示すように秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する（ステップＳ１００４）。
【０２０８】
【数１２６】
Ｘp＝Ｘp’ ｍｏｄ ｐ
Ｘq＝Ｘq’ ｍｏｄ ｑ
そして、剰余演算における演算結果を用いて、（数１２７）に示すモンゴメリべき乗剰余演算を実行する（ステップＳ１００５）。なお、モンゴメリべき乗剰余演算に用いる関数ＭＯＮＴ＿ＥＸＰは、（数１２８）に定義されるものとする。
【０２０９】
【数１２７】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒp，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒq，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
【０２１０】
【数１２８】
Ｒp＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒp，ｐ）＝（Ｘ＊Ｒp-1）dｍｏｄ ｐ
そして、（数１２７）におけるＹp及びＹqは、（数１２９）に示すように、中国人剰余定理を用いて直接べき乗剰余演算を行った場合の結果と一致することになる。したがって、補正演算自体が不要となる。
【０２１１】
【数１２９】
Ｙp＝Ｘpdpｍｏｄ ｐ
Ｙq＝Ｘqdqｍｏｄ ｑ
最後に、モンゴメリべき乗剰余演算により算出された演算値Ｙp及びＹqに基づいて、（数１３０）に示すように暗号化される前の平文Ｙを算出する（ステップＳ１００６）。
【０２１２】
【数１３０】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
以上のように本実施の形態３によれば、入力値とモンゴメリパラメタＲの剰余演算値との積の大小によって剰余演算が実行されるか否かが定まることから、演算処理時間や電力消費量の波形等の相違のみによっては、入力値と秘密鍵ｐ又はｑとの大小関係を特定することができず、サイドチャネルアタックに対して安全性の高い復号化演算方法を提供することができる。
【０２１３】
また、補正演算を行う必要性が無いことから、全体としての演算処理負荷がより小さくなることが期待できる。
【０２１４】
なお、ここまで本実施の形態３においては、Ｎ＝ｐ＊ｑのように、Ｎが互いに素である２つの数の乗算による場合について説明しているが、中国人剰余定理自体は、（数１３１）に示すように、Ｎが互いに素である複数の数の乗算による場合にも成立する。
【０２１５】
【数１３１】
Ｎ＝ｐ（０）α(0)＊ｐ（１）α(1)＊・・＊ｐ（ｎ）α(n)
ただし、ｎ≧２又はα（０）≧２
したがって、互いに素である複数の数にまで中国人剰余定理を拡張することによっても上述した演算と同様の関係が成立し、タイミングアタックやＳＰＡに代表されるサイドチャネルアタックに対して強固な演算装置を提供することが可能となる。
【０２１６】
また、（数１０８）に示すようなモンゴメリべき乗剰余演算を行う場合には、べき数の各ビット値に基づいて算出するバイナリメソッドと、Ｋビットの事前計算テーブルを準備して処理を行うウィンドウメソッドとが良く知られているが、本実施の形態３においては、どちらの算出方法についても適用可能である。
【０２１７】
なお、本実施の形態３にかかる演算装置及び方法は、一般的なＲＳＡ方式の暗号文だけでなく、ＥＰＯＣ暗号やｅ−ｓｉｇｎ等、秘密情報を剰余数に使用してべき乗剰余演算を行う全ての方式に適用可能であり、その際の効果についても同じである。
【０２１８】
以上のように、本実施の形態３においては、暗号化技術における復号化処理について説明している。ただし、本実施の形態にかかる処理は、電子署名の生成時においても同様の効果が期待できる。すなわち、暗号文Ｘの代わりに電子署名生成の対象となるデータを入力し、復号化される平文Ｙが生成される電子署名に該当することになる。この場合においても、サイドチャネルアタックに対して安全性を高く維持することができ、補正演算が１回で済む、あるいは条件によっては補正演算を行う必要性が全く無いことから、全体としての演算処理負荷がより小さくなることが期待できる。
【０２１９】
なお、本発明の実施の形態にかかるサイドチャネルアタック耐性を有する暗号演算装置を実現するプログラムは、図１１に示すように、ＣＤ−ＲＯＭ１１２−１やフレキシブルディスク１１２−２、あるいはＲＯＭカード（スマートメディア；スマートカード）１１２−３等の可搬型記録媒体１１２だけでなく、通信回線の先に備えられた他の記憶装置１１１や、コンピュータ１１３のハードディスクやＲＡＭ等の記録媒体１１４のいずれに記憶されるものであっても良く、プログラム実行時には、プログラムはローディングされ、主メモリ上で実行される。
【０２２０】
また、本発明の実施の形態にかかるサイドチャネルアタック耐性を有する暗号演算装置により生成された補正データ等についても、図１１に示すように、ＣＤ−ＲＯＭ１１２−１やフレキシブルディスク１１２−２、あるいはＲＯＭカード（スマートメディア；スマートカード）１１２−３等の可搬型記録媒体１１２だけでなく、通信回線の先に備えられた他の記憶装置１１１や、コンピュータ１１３のハードディスクやＲＡＭ等の記録媒体１１４のいずれに記憶されるものであっても良く、例えば本発明にかかるサイドチャネルアタック耐性を有する暗号演算装置を利用する際にコンピュータ１１３により読み取られる。
【０２２１】
【発明の効果】
以上のように本発明にかかるサイドチャネルアタック耐性を有する暗号演算装置によれば、いかなる入力がなされた場合であっても、常に剰余演算が実行されることになる、あるいは直接第三者が知ることができない数の大小に応じて剰余演算を実行するか否かが定まることから、演算処理時間や電力消費量の波形等の相違のみによっては入力値と秘密鍵ｐ又はｑとの大小関係を特定することができず、サイドチャネルアタックに対して安全性の高い復号化演算方法を提供することができる。
【０２２２】
また、本発明にかかるサイドチャネルアタック耐性を有する暗号演算装置によれば、補正演算が１回で済む、あるいは条件によっては補正演算を行う必要性が全く無いことから、全体としての演算処理負荷がより小さくなることが期待できる。
【０２２３】
（付記１）  秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだサイドチャネルアタック耐性を有する暗号演算装置であって、
前記秘密鍵ｐ及びｑよりも大きい値を有する任意の定数を暗号文Ｘと乗算してから前記べき乗剰余演算を実行し、最後に前記定数に基づいて補正演算を実行する補正演算部を設けることによって暗号化される前の平文Ｙを算出することを特徴とするサイドチャネルアタック耐性を有する暗号演算装置。
【０２２４】
（付記２）  秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
前記秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有する定数Ｃを保存する定数記憶部と、
前記定数に基づいて算出される補正値Ｃ-dp、Ｃ-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存する補正値記憶部と、
前記暗号文Ｘと前記定数記憶部に保存されている前記定数Ｃとを乗算する定数乗算部と、
前記乗算による演算結果を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１３２）に示す剰余演算を実行する剰余演算部と、
【数１３２】
Ｘp’＝Ｘ＊Ｃ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｃ ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１３３）に示す中国人剰余定理に基づいたべき乗剰余演算を行う中国人剰余ＲＳＡ処理部と、
【数１３３】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
前記べき乗剰余演算による演算結果Ｙp及びＹqを保存するべき乗剰余演算結果記憶部と、
前記べき乗剰余演算結果記憶部に保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、前記補正値記憶部に保存されている前記補正値Ｃ-dp又はＣ-dqを用いて、（数１３４）に示すような補正演算を行う補正処理部と、
【数１３４】
Ｙp’＝Ｙp＊Ｃ-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊Ｃ-dqｍｏｄ ｑ
前記補正演算による演算結果Ｙp’及びＹq’を保存する補正結果記憶部と、
前記補正結果記憶部に保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、（数１３５）に従って暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数１３５】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算装置。
【０２２５】
（付記３）  前記定数Ｃを入力する定数入力部をさらに含む付記２記載のサイドチャネルアタック耐性を有する暗号演算装置。
【０２２６】
（付記４）  前記定数Ｃに基づいて補正値Ｃ-dp、Ｃ-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を求める補正値演算部をさらに含む付記２又は３記載のサイドチャネルアタック耐性を有する暗号演算装置。
【０２２７】
（付記５）  秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
前記秘密鍵ｐ及びｑとの間にＣp＞ｐ、Ｃq＞ｑの関係を有する定数Ｃp及びＣqを保存する定数記憶部と、
前記定数に基づいて算出される補正値Ｃp-dp、Ｃq-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存する補正値記憶部と、
前記暗号文Ｘと前記定数記憶部に保存されている前記定数Ｃp又はＣqとを乗算する定数乗算部と、
前記乗算による演算結果を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１３６）に示す剰余演算を実行する剰余演算部と、
【数１３６】
Ｘp’＝Ｘ＊Ｃp ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｃq ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１３７）に示す中国人剰余定理に基づいたべき乗剰余演算を行う中国人剰余ＲＳＡ処理部と、
【数１３７】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
前記べき乗剰余演算による演算結果Ｙp及びＹqを保存するべき乗剰余演算結果記憶部と、
前記べき乗剰余演算結果記憶部に保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、前記補正値記憶部に保存されている前記補正値Ｃp-dp又はＣq-dqを用いて、（数１３８）に示すような補正演算を行う補正処理部と、
【数１３８】
Ｙp’＝Ｙp＊Ｃp-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊Ｃq-dqｍｏｄ ｑ
前記補正演算による演算結果Ｙp’及びＹq’を保存する補正結果記憶部と、
前記補正結果記憶部に保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、（数１３９）に従って暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数１３９】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算装置。
【０２２８】
（付記６）  前記定数Ｃp及びＣqを入力する定数入力部をさらに含む付記５記載のサイドチャネルアタック耐性を有する暗号演算装置。
【０２２９】
（付記７）  前記定数Ｃp及びＣqに基づいて補正値Ｃp-dp、Ｃq-dq（ｄｐ＝ｄｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を求める補正値演算部をさらに含む付記５又は６記載のサイドチャネルアタック耐性を有する暗号演算装置。
【０２３０】
（付記８）  秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだサイドチャネルアタック耐性を有する暗号演算装置であって、
前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを定数として、暗号文Ｘと乗算してから前記べき乗剰余演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とするサイドチャネルアタック耐性を有する暗号演算装置。
【０２３１】
（付記９）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１４０）に示すように定義されている場合において、
【数１４０】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
前記暗号文ＸとモンゴメリパラメタＲとを乗算するモンゴメリパラメタ乗算部と、
前記乗算による演算結果を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１４１）に示す剰余演算を実行する剰余演算部と、
【数１４１】
Ｘp’＝Ｘ＊Ｒ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒ ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１４２）に示すモンゴメリべき乗剰余演算を実行するモンゴメリべき乗剰余演算部と、
【数１４２】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するモンゴメリべき乗剰余演算結果記憶部と、
前記モンゴメリべき乗剰余演算記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数１４３）に示すように暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数１４３】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算装置。
【０２３２】
（付記１０）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１４４）に示すように定義されている場合において、
【数１４４】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
前記暗号文Ｘと前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqとを乗算するモンゴメリパラメタ乗算部と、
前記乗算による演算結果を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１４５）に示す剰余演算を実行する剰余演算部と、
【数１４５】
Ｘp’＝Ｘ＊Ｒp ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒq ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１４６）に示すモンゴメリべき乗剰余演算を実行するモンゴメリべき乗剰余演算部と、
【数１４６】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒp，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒq，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するモンゴメリべき乗剰余演算結果記憶部と、
前記モンゴメリべき乗剰余演算記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数１４７）に示すように暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数１４７】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算装置。
【０２３３】
（付記１１）  秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を実施するべき乗剰余演算部を含んだサイドチャネルアタック耐性を有する暗号演算装置であって、
前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを前記秘密鍵ｐ及びｑにより剰余演算を実行するモンゴメリパラメタ剰余演算部を含み、
前記剰余演算部における演算結果を暗号文Ｘと乗算してから前記べき乗剰余演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とするサイドチャネルアタック耐性を有する暗号演算装置。
【０２３４】
（付記１２）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１４８）に示すように定義されている場合において、
【数１４８】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
モンゴメリパラメタＲについて、（数１４９）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を保存するモンゴメリパラメタ剰余演算結果記憶部と、
【数１４９】
Ｒp’＝Ｒ ｍｏｄ ｐ
Ｒq’＝Ｒ ｍｏｄ ｑ
前記モンゴメリパラメタ剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、（数１５０）に示すように入力された暗号文Ｘを乗算する剰余値乗算部と、
【数１５０】
Ｘp’＝Ｘ＊Ｒp’
Ｘq’＝Ｘ＊Ｒq’
前記乗算による演算結果Ｘp’及びＸq’を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、（数１５１）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する剰余演算部と、
【数１５１】
Ｘp＝Ｘp’ｍｏｄ ｐ
Ｘq＝Ｘq’ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp及びＸqを保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、（数１５２）に示すモンゴメリべき乗剰余演算を実行するモンゴメリべき乗剰余演算部と、
【数１５２】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するモンゴメリべき乗剰余演算結果記憶部と、
前記モンゴメリべき乗剰余演算結果記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数１５３）に示すように暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数１５３】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算装置。
【０２３５】
（付記１３）  モンゴメリパラメタＲについて、（数１５４）に示すように剰余値ｐ又はｑに対する剰余演算を行うモンゴメリパラメタ剰余演算部をさらに含む付記１２記載のサイドチャネルアタック耐性を有する暗号演算装置。
【数１５４】
Ｒp’＝Ｒ ｍｏｄ ｐ
Ｒq’＝Ｒ ｍｏｄ ｑ
【０２３６】
（付記１４）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１５５）に示すように定義されている場合において、
【数１５５】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する暗号文入力部と、
前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqについて、（数１５６）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を保存するモンゴメリパラメタ剰余演算結果記憶部と、
【数１５６】
Ｒp’＝Ｒp ｍｏｄ ｐ
Ｒq’＝Ｒq ｍｏｄ ｑ
前記モンゴメリパラメタ剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、（数１５７）に示すように入力された暗号文Ｘを乗算する剰余値乗算部と、
【数１５７】
Ｘp’＝Ｘ＊Ｒp’
Ｘq’＝Ｘ＊Ｒq’
前記乗算による演算結果Ｘp’及びＸq’を保存する乗算結果記憶部と、
前記乗算結果記憶部に保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、（数１５８）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する剰余演算部と、
【数１５８】
Ｘp＝Ｘp’ｍｏｄ ｐ
Ｘq＝Ｘq’ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp及びＸqを保存する剰余演算結果記憶部と、
前記剰余演算結果記憶部に保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、（数１５９）に示すモンゴメリべき乗剰余演算を実行するモンゴメリべき乗剰余演算部と、
【数１５９】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒp，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒq，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するモンゴメリべき乗剰余演算結果記憶部と、
前記モンゴメリべき乗剰余演算結果記憶部に保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数１６０）に示すように暗号化される前の平文Ｙを算出する平文出力部とを含み、
【数１６０】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算装置。
【０２３７】
（付記１５）  前記モンゴメリパラメタＲp、Ｒqについて、（数１６１）に示すように剰余値ｐ又はｑに対する剰余演算を行うモンゴメリパラメタ剰余演算部をさらに含む請求項１４記載のサイドチャネルアタック耐性を有する暗号演算装置。
【数１６１】
Ｒp’＝Ｒp ｍｏｄ ｐ
Ｒq’＝Ｒq ｍｏｄ ｑ
【０２３８】
（付記１６）  秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を含んだサイドチャネルアタック耐性を有する暗号演算方法であって、
前記秘密鍵ｐ及びｑよりも大きい値を有する任意の定数を暗号文Ｘと乗算してから前記べき乗剰余演算を実行し、最後に前記定数に基づいて補正演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とするサイドチャネルアタック耐性を有する暗号演算方法。
【０２３９】
（付記１７）  秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する工程と、
前記秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有する定数Ｃを保存する工程と、
前記定数に基づいて算出される補正値Ｃ-dp、Ｃ-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存する工程と、
前記暗号文Ｘと保存されている前記定数Ｃとを乗算する工程と、
前記乗算による演算結果を保存する工程と、
保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１６２）に示す剰余演算を実行する工程と、
【数１６２】
Ｘp’＝Ｘ＊Ｃ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｃ ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存する工程と、
保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１６３）に示す中国人剰余定理に基づいたべき乗剰余演算を行う工程と、
【数１６３】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
前記べき乗剰余演算による演算結果Ｙp及びＹqを保存する工程と、
保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、保存されている前記補正値Ｃ-dp又はＣ-dqを用いて、（数１６４）に示すような補正演算を行う工程と、
【数１６４】
Ｙp’＝Ｙp＊Ｃ-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊Ｃ-dqｍｏｄ ｑ
前記補正演算による演算結果Ｙp’及びＹq’を保存する工程と、
保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、（数１６５）に従って暗号化される前の平文Ｙを算出する工程とを含み、
【数１６５】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法。
【０２４０】
（付記１８）  秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する工程と、
前記秘密鍵ｐ及びｑとの間にＣp＞ｐ、Ｃq＞ｑの関係を有する定数Ｃp及びＣqを保存する工程と、
前記定数に基づいて算出される補正値Ｃp-dp、Ｃq-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存する工程と、
前記暗号文Ｘと保存されている前記定数Ｃp又はＣqとを乗算する工程と、
前記乗算による演算結果を保存する工程と、
保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１６６）に示す剰余演算を実行する工程と、
【数１６６】
Ｘp’＝Ｘ＊Ｃp ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｃq ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存する工程と、
保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１６７）に示す中国人剰余定理に基づいたべき乗剰余演算を行う工程と、
【数１６７】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
前記べき乗剰余演算による演算結果Ｙp及びＹqを保存する工程と、
保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、保存されている前記補正値Ｃp-dp又はＣq-dqを用いて、（数１６８）に示すような補正演算を行う工程と、
【数１６８】
Ｙp’＝Ｙp＊Ｃp-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊Ｃq-dqｍｏｄ ｑ
前記補正演算による演算結果Ｙp’及びＹq’を保存する工程と、
保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、（数１６９）に従って暗号化される前の平文Ｙを算出する工程とを含み、
【数１６９】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法。
【０２４１】
（付記１９）  秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を含んだサイドチャネルアタック耐性を有する暗号演算方法であって、
前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを定数として、暗号文Ｘと乗算してから前記べき乗剰余演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とするサイドチャネルアタック耐性を有する暗号演算方法。
【０２４２】
（付記２０）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１７０）に示すように定義されている場合において、
【数１７０】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する工程と、
前記暗号文ＸとモンゴメリパラメタＲとを乗算する工程と、
前記乗算による演算結果を保存する工程と、
保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１７１）に示す剰余演算を実行する工程と、
【数１７１】
Ｘp’＝Ｘ＊Ｒ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒ ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存する工程と、
保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１７２）に示すモンゴメリべき乗剰余演算を実行する工程と、
【数１７２】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存する工程と、保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数１７３）に示すように暗号化される前の平文Ｙを算出する工程とを含み、
【数１７３】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法。
【０２４３】
（付記２１）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１７４）に示すように定義されている場合において、
【数１７４】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する工程と、
前記暗号文Ｘと前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqとを乗算する工程と、
前記乗算による演算結果を保存する工程と、
保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１７５）に示す剰余演算を実行する工程と、
【数１７５】
Ｘp’＝Ｘ＊Ｒp ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒq ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存する工程と、
保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１７６）に示すモンゴメリべき乗剰余演算を実行する工程と、
【数１７６】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒp，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒq，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存する工程と、保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数１７７）に示すように暗号化される前の平文Ｙを算出する工程とを含み、
【数１７７】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法。
【０２４４】
（付記２２）  秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を含んだサイドチャネルアタック耐性を有する暗号演算方法であって、
前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを前記秘密鍵ｐ及びｑにより剰余演算を実行する工程を含み、
前記剰余演算における演算結果を暗号文Ｘと乗算してから前記べき乗剰余演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とするサイドチャネルアタック耐性を有する暗号演算方法。
【０２４５】
（付記２３）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１７８）に示すように定義されている場合において、
【数１７８】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する工程と、
モンゴメリパラメタＲについて、（数１７９）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を保存する工程と、
【数１７９】
Ｒp’＝Ｒ ｍｏｄ ｐ
Ｒq’＝Ｒ ｍｏｄ ｑ
保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、（数１８０）に示すように入力された暗号文Ｘを乗算する工程と、
【数１８０】
Ｘp’＝Ｘ＊Ｒp’
Ｘq’＝Ｘ＊Ｒq’
前記乗算による演算結果Ｘp’及びＸq’を保存する工程と、
保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、（数１８１）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する工程と、
【数１８１】
Ｘp＝Ｘp’ｍｏｄ ｐ
Ｘq＝Ｘq’ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp及びＸqを保存する工程と、
保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、（数１８２）に示すモンゴメリべき乗剰余演算を実行する工程と、
【数１８２】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存する工程と、保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数１８３）に示すように暗号化される前の平文Ｙを算出する工程とを含み、
【数１８３】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法。
【０２４６】
（付記２４）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１８４）に示すように定義されている場合において、
【数１８４】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力する工程と、
前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqについて、（数１８５）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を保存する工程と、
【数１８５】
Ｒp’＝Ｒp ｍｏｄ ｐ
Ｒq’＝Ｒq ｍｏｄ ｑ
保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、（数１８６）に示すように入力された暗号文Ｘを乗算する工程と、
【数１８６】
Ｘp’＝Ｘ＊Ｒp’
Ｘq’＝Ｘ＊Ｒq’
前記乗算による演算結果Ｘp’及びＸq’を保存する工程と、
保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、（数１８７）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行する工程と、
【数１８７】
Ｘp＝Ｘp’ｍｏｄ ｐ
Ｘq＝Ｘq’ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp及びＸqを保存する工程と、
保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、（数１８８）に示すモンゴメリべき乗剰余演算を実行する工程と、
【数１８８】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒp，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒq，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存する工程と、保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数１８９）に示すように暗号化される前の平文Ｙを算出する工程とを含み、
【数１８９】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法。
【０２４７】
（付記２５）  秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を含んだサイドチャネルアタック耐性を有する暗号演算方法を具現化するコンピュータ実行可能なプログラムであって、
前記秘密鍵ｐ及びｑよりも大きい値を有する任意の定数を暗号文Ｘと乗算してから前記べき乗剰余演算を実行し、最後に前記定数に基づいて補正演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とするコンピュータ実行可能なプログラム。
【０２４８】
（付記２６）  秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力するステップと、
前記秘密鍵ｐ及びｑとの間にＣ＞ｐ、Ｃ＞ｑの関係を有する定数Ｃを保存するステップと、
前記定数に基づいて算出される補正値Ｃ-dp、Ｃ-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存するステップと、
前記暗号文Ｘと保存されている前記定数Ｃとを乗算するステップと、
前記乗算による演算結果を保存するステップと、
保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１９０）に示す剰余演算を実行するステップと、
【数１９０】
Ｘp’＝Ｘ＊Ｃ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｃ ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存するステップと、
保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１９１）に示す中国人剰余定理に基づいたべき乗剰余演算を行うステップと、
【数１９１】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
前記べき乗剰余演算による演算結果Ｙp及びＹqを保存するステップと、
保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、保存されている前記補正値Ｃ-dp又はＣ-dqを用いて、（数１９２）に示すような補正演算を行うステップと、
【数１９２】
Ｙp’＝Ｙp＊Ｃ-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊Ｃ-dqｍｏｄ ｑ
前記補正演算による演算結果Ｙp’及びＹq’を保存するステップと、
保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、（数１９３）に従って暗号化される前の平文Ｙを算出するステップとを含み、
【数１９３】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法を具現化するコンピュータ実行可能なプログラム。
【０２４９】
（付記２７）  秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力するステップと、
前記秘密鍵ｐ及びｑとの間にＣp＞ｐ、Ｃq＞ｑの関係を有する定数Ｃp及びＣqを保存するステップと、
前記定数に基づいて算出される補正値Ｃp-dp、Ｃq-dq（ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１））を保存するステップと、
前記暗号文Ｘと保存されている前記定数Ｃp又はＣqとを乗算するステップと、
前記乗算による演算結果を保存するステップと、
保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１９４）に示す剰余演算を実行するステップと、
【数１９４】
Ｘp’＝Ｘ＊Ｃp ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｃq ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存するステップと、
保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数１９５）に示す中国人剰余定理に基づいたべき乗剰余演算を行うステップと、
【数１９５】
Ｙp＝Ｘp’dpｍｏｄ ｐ
Ｙq＝Ｘq’dqｍｏｄ ｑ
前記べき乗剰余演算による演算結果Ｙp及びＹqを保存するステップと、
保存されている前記べき乗剰余演算による演算結果Ｙp及びＹqに対して、保存されている前記補正値Ｃp-dp又はＣq-dqを用いて、（数１９６）に示すような補正演算を行うステップと、
【数１９６】
Ｙp’＝Ｙp＊Ｃp-dpｍｏｄ ｐ
Ｙq’＝Ｙq＊Ｃq-dqｍｏｄ ｑ
前記補正演算による演算結果Ｙp’及びＹq’を保存するステップと、
保存されている前記補正演算による演算結果Ｙp’及びＹq’に基づいて、（数１９７）に従って暗号化される前の平文Ｙを算出するステップとを含み、
【数１９７】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法を具現化するコンピュータ実行可能なプログラム。
【０２５０】
（付記２８）  秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を含んだサイドチャネルアタック耐性を有する暗号演算方法を具現化するコンピュータ実行可能なプログラムであって、
前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを定数として、暗号文Ｘと乗算してから前記べき乗剰余演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とするコンピュータ実行可能なプログラム。
【０２５１】
（付記２９）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数１９８）に示すように定義されている場合において、
【数１９８】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力するステップと、
前記暗号文ＸとモンゴメリパラメタＲとを乗算するステップと、
前記乗算による演算結果を保存するステップと、
保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数１９９）に示す剰余演算を実行するステップと、
【数１９９】
Ｘp’＝Ｘ＊Ｒ ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒ ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存するステップと、
保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数２００）に示すモンゴメリべき乗剰余演算を実行するステップと、
【数２００】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するステップと、
保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数２０１）に示すように暗号化される前の平文Ｙを算出するステップとを含み、
【数２０１】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法を具現化するコンピュータ実行可能なプログラム。
【０２５２】
（付記３０）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２０２）に示すように定義されている場合において、
【数２０２】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力するステップと、
前記暗号文Ｘと前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqとを乗算するステップと、
前記乗算による演算結果を保存するステップと、
保存されている前記乗算による演算結果に対して、秘密鍵ｐ又はｑを剰余値とした（数２０３）に示す剰余演算を実行するステップと、
【数２０３】
Ｘp’＝Ｘ＊Ｒp ｍｏｄ ｐ
Ｘq’＝Ｘ＊Ｒq ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp’及びＸq’を保存するステップと、
保存されている前記剰余演算による演算結果Ｘp’及びＸq’に対して、（数２０４）に示すモンゴメリべき乗剰余演算を実行するステップと、
【数２０４】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp’，ｄｐ，Ｒp，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq’，ｄｑ，Ｒq，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するステップと、
保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数２０５）に示すように暗号化される前の平文Ｙを算出するステップとを含み、
【数２０５】
Ｙ＝（ａ（Ｙq’−Ｙp’）ｍｏｄ ｑ）ｐ＋Ｙp’
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法を具現化するコンピュータ実行可能なプログラム。
【０２５３】
（付記３１）  秘密鍵ｐ、ｑ、ｄを用いて復号可能な暗号文Ｘに対して、少なくともべき乗剰余演算を含んだサイドチャネルアタック耐性を有する暗号演算方法を具現化するコンピュータ実行可能なプログラムであって、
前記秘密鍵ｐ及びｑよりも大きい値を有するモンゴメリパラメタを前記秘密鍵ｐ及びｑにより剰余演算を実行するステップを含み、
前記剰余演算における演算結果を暗号文Ｘと乗算してから前記べき乗剰余演算を実行することによって暗号化される前の平文Ｙを算出することを特徴とするコンピュータ実行可能なプログラム。
【０２５４】
（付記３２）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２０６）に示すように定義されている場合において、
【数２０６】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力するステップと、
モンゴメリパラメタＲについて、（数２０７）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を保存するステップと、
【数２０７】
Ｒp’＝Ｒ ｍｏｄ ｐ
Ｒq’＝Ｒ ｍｏｄ ｑ
保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、（数２０８）に示すように入力された暗号文Ｘを乗算するステップと、
【数２０８】
Ｘp’＝Ｘ＊Ｒp’
Ｘq’＝Ｘ＊Ｒq’
前記乗算による演算結果Ｘp’及びＸq’を保存するステップと、
保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、（数２０９）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行するステップと、
【数２０９】
Ｘp＝Ｘp’ｍｏｄ ｐ
Ｘq＝Ｘq’ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp及びＸqを保存するステップと、
保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、（数２１０）に示すモンゴメリべき乗剰余演算を実行するステップと、
【数２１０】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒ，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒ，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するステップと、
保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数２１１）に示すように暗号化される前の平文Ｙを算出するステップとを含み、
【数２１１】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法を具現化するコンピュータ実行可能なプログラム。
【０２５５】
（付記３３）  モンゴメリべき乗剰余演算を実行する関数ＭＯＮＴ＿ＥＸＰが（数２１２）に示すように定義されている場合において、
【数２１２】
Ｒ＞ｐ
ＭＯＮＴ＿ＥＸＰ（Ｘ，ｄ，Ｒ，ｐ）＝（Ｘ＊Ｒ-1）dｍｏｄ ｐ
秘密鍵ｐ、ｑ、ｄを用いて復号できる暗号文Ｘを入力するステップと、
前記秘密鍵ｐ及びｑとの間にＲp＞ｐ、Ｒq＞ｑの関係を有するモンゴメリパラメタＲp又はＲqについて、（数２１３）に示すように剰余値ｐ又はｑに対する剰余演算を行った結果を保存するステップと、
【数２１３】
Ｒp’＝Ｒp ｍｏｄ ｐ
Ｒq’＝Ｒq ｍｏｄ ｑ
保存されている前記剰余演算による演算結果Ｒp’又はＲq’に対して、（数２１４）に示すように入力された暗号文Ｘを乗算するステップと、
【数２１４】
Ｘp’＝Ｘ＊Ｒp’
Ｘq’＝Ｘ＊Ｒq’
前記乗算による演算結果Ｘp’及びＸq’を保存するステップと、
保存されている前記乗算による演算結果Ｘp’及びＸq’に対して、（数２１５）に示すように、秘密鍵ｐ及びｑを剰余値とした剰余演算を各々実行するステップと、
【数２１５】
Ｘp＝Ｘp’ｍｏｄ ｐ
Ｘq＝Ｘq’ｍｏｄ ｑ
前記剰余演算による演算結果Ｘp及びＸqを保存するステップと、
保存されている前記剰余演算による演算結果Ｘp及びＸqに対して、（数２１６）に示すモンゴメリべき乗剰余演算を実行するステップと、
【数２１６】
Ｙp＝ＭＯＮＴ＿ＥＸＰ（Ｘp，ｄｐ，Ｒp，ｐ）
Ｙq＝ＭＯＮＴ＿ＥＸＰ（Ｘq，ｄｑ，Ｒq，ｑ）
ただし、ｄｐ＝ｄ ｍｏｄ（ｐ−１）、ｄｑ＝ｄ ｍｏｄ（ｑ−１）
前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqを保存するステップと、
保存されている前記モンゴメリべき乗剰余演算による演算結果Ｙp及びＹqに基づいて、（数２１７）に示すように暗号化される前の平文Ｙを算出するステップとを含み、
【数２１７】
Ｙ＝（ａ（Ｙq−Ｙp）ｍｏｄ ｑ）ｐ＋Ｙp
ただし、ａ＝ｐ-1ｍｏｄ ｑ
いかなる前記暗号文Ｘが入力された場合であっても前記秘密鍵ｐ及びｑを特定することができないことを特徴とするサイドチャネルアタック耐性を有する暗号演算方法を具現化するコンピュータ実行可能なプログラム。
【図面の簡単な説明】
【図１】  ＳＰＡにおける電力消費量の波形の例示図
【図２】  本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置の構成図
【図３】  本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置における処理の流れ図
【図４】  本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置における処理の流れ図
【図５】  本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置の構成図
【図６】  本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置における処理の流れ図
【図７】  本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置における処理の流れ図
【図８】  本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置の構成図
【図９】  本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置における処理の流れ図
【図１０】  本発明の実施の形態３にかかるサイドチャネルアタック耐性を有する暗号演算装置における処理の流れ図
【図１１】  コンピュータ環境の例示図
【符号の説明】
１  暗号文入力部
２  定数入力部
４  補正値演算部
５  補正値記憶部
６  定数乗算部
７、２２、３４  乗算結果記憶部
８  剰余演算部
９  剰余演算結果記憶部
１０  中国人剰余ＲＳＡ処理部
１１  べき乗剰余演算結果記憶部
１２  補正処理部
１３  補正結果記憶部
１４  平文出力部
２１  モンゴメリパラメタ乗算部
２３  モンゴメリべき乗剰余演算部
２４  モンゴメリべき乗剰余演算結果記憶部
３１  モンゴメリパラメタ剰余演算部
３２  モンゴメリパラメタ剰余演算結果記憶部
３３  剰余値乗算部
１１１  回線先の記憶装置
１１２  ＣＤ−ＲＯＭやフレキシブルディスク等の可搬型記録媒体
１１２−１  ＣＤ−ＲＯＭ
１１２−２  フレキシブルディスク
１１２−３  ＲＯＭカード（スマートメディア；スマートカード）
１１３  コンピュータ
１１４  コンピュータ上のＲＡＭ／ハードディスク等の記録媒体
【図１】
0004086503.tif 000093
【図２】
0004086503.tif 000094
【図３】
0004086503.tif 000095
【図４】
0004086503.tif 000096
【図５】
0004086503.tif 000097
【図６】
0004086503.tif 000098
【図７】
0004086503.tif 000099
【図８】
0004086503.tif 000100
【図９】
0004086503.tif 000101
【図１０】
0004086503.tif 000102
【図１１】
0004086503.tif 000103