JPH10307710A - 剰余系演算方法及びその装置 - Google Patents
剰余系演算方法及びその装置Info
- Publication number
- JPH10307710A JPH10307710A JP5199298A JP5199298A JPH10307710A JP H10307710 A JPH10307710 A JP H10307710A JP 5199298 A JP5199298 A JP 5199298A JP 5199298 A JP5199298 A JP 5199298A JP H10307710 A JPH10307710 A JP H10307710A
- Authority
- JP
- Japan
- Prior art keywords
- divisor
- remainder
- mod
- dividend
- digits
- 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
Landscapes
- Complex Calculations (AREA)
Abstract
(57)【要約】
【課題】 法のビット数より仮数のビット数が大きい場
合でも演算可能な剰余系演算方法及びその装置を提供す
ること。 【解決手段】 法（除数）ｃをそのレジスタの最上位ビ
ットが“１”となるまでビットシフトし、仮数（被除
数）ａをそのレジスタの最上位バイトに“１”が含まれ
るまでバイトシフトした上で剰余演算を、法と仮数との
ビットシフト量の差に対応する位まで行う。
合でも演算可能な剰余系演算方法及びその装置を提供す
ること。 【解決手段】 法（除数）ｃをそのレジスタの最上位ビ
ットが“１”となるまでビットシフトし、仮数（被除
数）ａをそのレジスタの最上位バイトに“１”が含まれ
るまでバイトシフトした上で剰余演算を、法と仮数との
ビットシフト量の差に対応する位まで行う。
Description
【０００１】
【発明の属する技術分野】本発明は、ＲＳＡ暗号等の公
開鍵暗号の基本演算及びその鍵生成に必要な剰余系の演
算を実行する方法及びその装置に関するものである。
開鍵暗号の基本演算及びその鍵生成に必要な剰余系の演
算を実行する方法及びその装置に関するものである。
【０００２】
【従来の技術】ＲＳＡ暗号等の公開鍵暗号の基本演算及
びその鍵生成には、羃乗剰余演算 abmod c 、乗剰余演
算 a×b mod c 、剰余演算a mod c 等の剰余系の演算が
必要となる。さらに、公開鍵暗号を利用した応用プロト
コルでは、前記剰余系の演算を組み合わせて利用する場
合が多い。そのため、ある剰余系の演算結果を次の演算
に用いることも頻繁にあり、発明者らは特願平６−２８
６８５３号（特開平８−１４７２６６号）において冗長
２進演算を用いた演算方法及びその装置を提案した。
びその鍵生成には、羃乗剰余演算 abmod c 、乗剰余演
算 a×b mod c 、剰余演算a mod c 等の剰余系の演算が
必要となる。さらに、公開鍵暗号を利用した応用プロト
コルでは、前記剰余系の演算を組み合わせて利用する場
合が多い。そのため、ある剰余系の演算結果を次の演算
に用いることも頻繁にあり、発明者らは特願平６−２８
６８５３号（特開平８−１４７２６６号）において冗長
２進演算を用いた演算方法及びその装置を提案した。
【０００３】
【発明が解決しようとする課題】しかしながら、前述し
た演算方法及び装置では、羃乗剰余演算 ab mod c 、剰
余演算a mod c において、｜ａ｜＞｜ｃ｜（以降、｜ｋ
｜をｋのビット数、羃乗剰余演算 ab mod c のａを仮数
（被除数）、ｂを羃指数、ｃを法（除数）と呼ぶことに
する。）の場合、演算ができないという問題があった。
た演算方法及び装置では、羃乗剰余演算 ab mod c 、剰
余演算a mod c において、｜ａ｜＞｜ｃ｜（以降、｜ｋ
｜をｋのビット数、羃乗剰余演算 ab mod c のａを仮数
（被除数）、ｂを羃指数、ｃを法（除数）と呼ぶことに
する。）の場合、演算ができないという問題があった。
【０００４】本来、冗長２進演算法は、除算時の除数の
２進数表現における最上位ビットが“１”でなければな
らないため、設計した除算器の除数のビット数と計算し
ようするビット数とが一致していなければならないとい
う制限があった。
２進数表現における最上位ビットが“１”でなければな
らないため、設計した除算器の除数のビット数と計算し
ようするビット数とが一致していなければならないとい
う制限があった。
【０００５】そこで、特願平６−２８６８５３号では、
（１）除数（法）の最上位ビットが“１”になるまで、
除数全体を上位にシフトする、（２）被除数（仮数）も
（１）のシフト分だけ全体を上位にシフトする、（３）
従来の冗長２進演算法を用いて演算を行う、（４）演算
結果を逆補正するため（１）で行った分下位にシフトす
る、ことにより法のビット数の制限をなくすようになし
た。
（１）除数（法）の最上位ビットが“１”になるまで、
除数全体を上位にシフトする、（２）被除数（仮数）も
（１）のシフト分だけ全体を上位にシフトする、（３）
従来の冗長２進演算法を用いて演算を行う、（４）演算
結果を逆補正するため（１）で行った分下位にシフトす
る、ことにより法のビット数の制限をなくすようになし
た。
【０００６】ところが、（２）において、仮数も法と同
じビット数、上位にシフトすることから、法のビット数
より仮数のビット数が大きい場合、桁あふれが生じてし
まうため、正確な演算ができなくなるという問題があっ
た。
じビット数、上位にシフトすることから、法のビット数
より仮数のビット数が大きい場合、桁あふれが生じてし
まうため、正確な演算ができなくなるという問題があっ
た。
【０００７】このような条件の場合のもとで、先願をＬ
ＳＩに応用した場合を考えると、予め仮数が法より小さ
くなっている場合は問題ないが、さまざまな応用プロト
コルに適用しようとした場合、不便である。乗剰余演算
a×b mod c の例では、通常、ａ＜ｃ，ｂ＜ｃである
が、一般的にａ、ｂの積ａ×ｂはｃよりも大きくなって
しまい、この演算はできない。
ＳＩに応用した場合を考えると、予め仮数が法より小さ
くなっている場合は問題ないが、さまざまな応用プロト
コルに適用しようとした場合、不便である。乗剰余演算
a×b mod c の例では、通常、ａ＜ｃ，ｂ＜ｃである
が、一般的にａ、ｂの積ａ×ｂはｃよりも大きくなって
しまい、この演算はできない。
【０００８】本発明の目的は、冗長２進演算を用いた剰
余系の演算において、法のビット数より仮数のビット数
が大きい場合であっても演算可能な方法及びその装置を
提供することにある。
余系の演算において、法のビット数より仮数のビット数
が大きい場合であっても演算可能な方法及びその装置を
提供することにある。
【０００９】
【課題を解決するための手段】本発明では、前記課題を
解決するため、ｈ進数の被除数をａ、除数をｃとした時
に剰余演算a mod c を行う剰余系演算方法及びその装置
において、被除数ａ及び除数ｃをレジスタに格納し、除
数ｃの桁数ｊが格納可能な桁数ｉ桁未満の時、除数ｃ全
体を（ｉ−ｊ）桁シフトし、ｈの−（ｉ−ｊ）乗の位ま
で剰余演算a mod c を行うことを特徴とする。
解決するため、ｈ進数の被除数をａ、除数をｃとした時
に剰余演算a mod c を行う剰余系演算方法及びその装置
において、被除数ａ及び除数ｃをレジスタに格納し、除
数ｃの桁数ｊが格納可能な桁数ｉ桁未満の時、除数ｃ全
体を（ｉ−ｊ）桁シフトし、ｈの−（ｉ−ｊ）乗の位ま
で剰余演算a mod c を行うことを特徴とする。
【００１０】また、本発明では、ｈ進数の被除数をａ、
除数をｃとした時に剰余演算a modc を行う剰余系演算
方法及びその装置において、被除数ａ及び除数ｃをレジ
スタに格納し、除数ｃの桁数ｊが格納可能な桁数ｉ桁未
満の時、除数ｃ全体を（ｉ−ｊ）桁シフトし、被除数ａ
の桁数ｌが格納可能な桁数ｋ（≧ｉ）桁未満の時、被除
数ａ全体を（ｋ−ｌ）桁シフトし、ｈの｛（ｋ−ｌ）−
（ｉ−ｊ）｝乗の位まで剰余演算a mod c を行い、得ら
れた剰余を（ｋ−ｌ）桁、逆にシフトし、これを剰余演
算結果とすることを特徴とする。
除数をｃとした時に剰余演算a modc を行う剰余系演算
方法及びその装置において、被除数ａ及び除数ｃをレジ
スタに格納し、除数ｃの桁数ｊが格納可能な桁数ｉ桁未
満の時、除数ｃ全体を（ｉ−ｊ）桁シフトし、被除数ａ
の桁数ｌが格納可能な桁数ｋ（≧ｉ）桁未満の時、被除
数ａ全体を（ｋ−ｌ）桁シフトし、ｈの｛（ｋ−ｌ）−
（ｉ−ｊ）｝乗の位まで剰余演算a mod c を行い、得ら
れた剰余を（ｋ−ｌ）桁、逆にシフトし、これを剰余演
算結果とすることを特徴とする。
【００１１】本発明によれば、除数及び被除数の桁数が
格納可能な桁数以下であれば、その大小に拘らず演算が
可能となり、冗長２進演算法の高速演算の長所を生か
し、かつ冗長２進演算法の短所である演算ビット数の制
限をなくすことができる。
格納可能な桁数以下であれば、その大小に拘らず演算が
可能となり、冗長２進演算法の高速演算の長所を生か
し、かつ冗長２進演算法の短所である演算ビット数の制
限をなくすことができる。
【００１２】また、前述した剰余演算方法及びその装置
を応用することにより、乗剰余演算、羃乗剰余演算を同
様に行うことができる。
を応用することにより、乗剰余演算、羃乗剰余演算を同
様に行うことができる。
【００１３】
【発明の実施の形態】図１は本発明の実施の形態の一例
を示す装置構成図である。図中、１０は冗長２進演算
部、２０はパラメタシフト部、３０はパラメタ保存用汎
用レジスタ部であり、これらが本発明を適用した剰余系
演算装置１００を構成する。この剰余系演算装置１００
を実現する最適な方法は１チップのＬＳＩである。
を示す装置構成図である。図中、１０は冗長２進演算
部、２０はパラメタシフト部、３０はパラメタ保存用汎
用レジスタ部であり、これらが本発明を適用した剰余系
演算装置１００を構成する。この剰余系演算装置１００
を実現する最適な方法は１チップのＬＳＩである。
【００１４】冗長２進演算部１０は冗長２進演算を実行
する。冗長２進演算部１０のパラメタ入出力部分に本発
明のパラメタシフト部２０が接続される。また、パラメ
タ保存用汎用レジスタ部３０はパラメタシフト部２０に
パラメタを保存することを目的としたレジスタであり、
剰余系演算装置１００の内部のバスと外部バスとのデー
タ入出力インタフェースを司る。
する。冗長２進演算部１０のパラメタ入出力部分に本発
明のパラメタシフト部２０が接続される。また、パラメ
タ保存用汎用レジスタ部３０はパラメタシフト部２０に
パラメタを保存することを目的としたレジスタであり、
剰余系演算装置１００の内部のバスと外部バスとのデー
タ入出力インタフェースを司る。
【００１５】
【a mod c 】最も簡単な例として、剰余演算a mod c を
例に挙げて説明する。
例に挙げて説明する。
【００１６】除算時の制限から、冗長２進演算器の設計
時の法ｃのレジスタのビット長ｋに等しいビットでなれ
ば演算できない。言い換えれば、法ｃのレジスタの最上
位ビットは必ず“１”でなければ演算ができない。
時の法ｃのレジスタのビット長ｋに等しいビットでなれ
ば演算できない。言い換えれば、法ｃのレジスタの最上
位ビットは必ず“１”でなければ演算ができない。
【００１７】そこで、以前、法ｃを格納するレジスタと
等しいビット数の法に変換するために、 a mod c ＝｛（ａ×２i ） mod（ｃ×２i ）｝／２i ……(1) を利用して、ｃ×２i がｋになるようにすることによ
り、前記の制限を補うようになした。
等しいビット数の法に変換するために、 a mod c ＝｛（ａ×２i ） mod（ｃ×２i ）｝／２i ……(1) を利用して、ｃ×２i がｋになるようにすることによ
り、前記の制限を補うようになした。
【００１８】汎用レジスタ構成にする場合、同じビット
長にするのが普通である。
長にするのが普通である。
【００１９】また、式(1) の右辺の剰余演算は、ａ＞ｃ
である時に演算する意味があるが、式(1) の左辺からわ
かるように、仮数も２i 倍されるので、仮数レジスタを
法レジスタと同じビット数にしたとすると、実際に式
(1) が利用できるのは、 ａ＞ｃ ……(2) ｜ａ｜＝｜ｃ｜ ……(3) が同時に成り立つ時のみであり、かなり限定された条件
となる。
である時に演算する意味があるが、式(1) の左辺からわ
かるように、仮数も２i 倍されるので、仮数レジスタを
法レジスタと同じビット数にしたとすると、実際に式
(1) が利用できるのは、 ａ＞ｃ ……(2) ｜ａ｜＝｜ｃ｜ ……(3) が同時に成り立つ時のみであり、かなり限定された条件
となる。
【００２０】そこで、本発明では、条件(3) の代わり
に、ａ，ｃはそれぞれのレジスタのビット長以内であれ
ば、 ｜ａ｜≧｜ｃ｜ ……(4) であっても演算ができるようにする。
に、ａ，ｃはそれぞれのレジスタのビット長以内であれ
ば、 ｜ａ｜≧｜ｃ｜ ……(4) であっても演算ができるようにする。
【００２１】解り易くするために、１０進数を利用した
場合の例を図２に示す。
場合の例を図２に示す。
【００２２】通常の除算は、図２(a) のように表され
る。ここでは、 ２４３÷１３＝１８余り９ の計算を行っている。
る。ここでは、 ２４３÷１３＝１８余り９ の計算を行っている。
【００２３】ここで、除数及び被除数のレジスタは１０
進数で４桁であるとする。この時、除数レジスタの最上
位桁が０以外でなければならないとする。この条件で演
算する方法を２つ挙げる。
進数で４桁であるとする。この時、除数レジスタの最上
位桁が０以外でなければならないとする。この条件で演
算する方法を２つ挙げる。
【００２４】・方法１（図２(b) ） ステップ１：除数を２桁分桁上げ（上位にシフト）する
ことにより、最上位桁が０でなくなる。 １３→１３００（２０１） ステップ２：２４３÷１３００を計算することになる
が、ステップ１で桁上げした分に対応する１０の−２乗
の位（小数点第２位）まで計算をする。 ２４３÷１３００＝０．１８余り９（２０２） ステップ３：余り９が求められる（２０３）。
ことにより、最上位桁が０でなくなる。 １３→１３００（２０１） ステップ２：２４３÷１３００を計算することになる
が、ステップ１で桁上げした分に対応する１０の−２乗
の位（小数点第２位）まで計算をする。 ２４３÷１３００＝０．１８余り９（２０２） ステップ３：余り９が求められる（２０３）。
【００２５】・方法２（図２(c) ） ステップ１：除数を２桁分桁上げ（上位にシフト）する
ことにより、最上位桁が０でなくなる。 １３→１３００（２１１） ステップ２：除数レジスタと同様に最上位桁が０以外に
なるように被除数を１桁分桁上げ（上位にシフト）する
ことにより、最上位桁が０でなくなる。 ２４３→２４３０（２１２） ステップ３：２４３０÷１３００を計算することになる
が、ステップ１及びステップ２で桁上げした分の差に対
応する１０の−１乗の位（小数点第１位）まで計算をす
る。 ２４３０÷１３００＝１．８余り９０（２１３） ステップ４：ステップ２で桁上げした分の１桁、余りを
下位にシフトする。 ９０→９（２１４）。
ことにより、最上位桁が０でなくなる。 １３→１３００（２１１） ステップ２：除数レジスタと同様に最上位桁が０以外に
なるように被除数を１桁分桁上げ（上位にシフト）する
ことにより、最上位桁が０でなくなる。 ２４３→２４３０（２１２） ステップ３：２４３０÷１３００を計算することになる
が、ステップ１及びステップ２で桁上げした分の差に対
応する１０の−１乗の位（小数点第１位）まで計算をす
る。 ２４３０÷１３００＝１．８余り９０（２１３） ステップ４：ステップ２で桁上げした分の１桁、余りを
下位にシフトする。 ９０→９（２１４）。
【００２６】方法１と方法２とでは、方法１の方がステ
ップ数が少ない。一方、方法１のステップ２と方法２の
ステップ３を比較すると、除算回数は、方法２の方が少
ない。従って、どちらが高速に演算を実行することがで
きるかは、回路の構成方法に依存する。
ップ数が少ない。一方、方法１のステップ２と方法２の
ステップ３を比較すると、除算回数は、方法２の方が少
ない。従って、どちらが高速に演算を実行することがで
きるかは、回路の構成方法に依存する。
【００２７】一般的には、データバス幅の桁シフト（複
数桁）と除算１回（１桁単位）が同じクロックを要する
ので、桁シフト（方法２）の方が効率が良い。
数桁）と除算１回（１桁単位）が同じクロックを要する
ので、桁シフト（方法２）の方が効率が良い。
【００２８】これらの方法を２進数に拡張すれば、冗長
２進数に適用することができる。その結果、｜ａ｜≧｜
ｃ｜であっても演算ができるようにすることができる。
２進数に適用することができる。その結果、｜ａ｜≧｜
ｃ｜であっても演算ができるようにすることができる。
【００２９】なお、図２(c) に示した方法２の場合にお
いて、除数の桁上げ分が被除数の桁上げ分より小さい時
は、一の位より上の位（十の位、百の位、……）までで
計算を止めることになる。
いて、除数の桁上げ分が被除数の桁上げ分より小さい時
は、一の位より上の位（十の位、百の位、……）までで
計算を止めることになる。
【００３０】図３は図１中のパラメタシフト部２０の具
体的構成の一例、ここでは図２(c)で説明した方法２に
従う演算を実行する構成を示すもので、図中、２１は除
数用左ビットシフト部、２２は被除数用左ビットシフト
部、２３は除数ビットシフト量記憶部、２４は被除数ビ
ットシフト量記憶部、２５は除算回数制御部、２６は剰
余用右ビットシフト部である。
体的構成の一例、ここでは図２(c)で説明した方法２に
従う演算を実行する構成を示すもので、図中、２１は除
数用左ビットシフト部、２２は被除数用左ビットシフト
部、２３は除数ビットシフト量記憶部、２４は被除数ビ
ットシフト量記憶部、２５は除算回数制御部、２６は剰
余用右ビットシフト部である。
【００３１】以下、a mod c ＝ｒの演算を例にとって動
作を説明するが、図２(c) 中の具体的な値も併せて示
す。
作を説明するが、図２(c) 中の具体的な値も併せて示
す。
【００３２】まず、除数用左ビットシフト部２１は、除
数（法）ｃをその最上位ビットが“１”になるまで上位
（左方向）にシフトする。この時のシフト量をｍ（図２
(c) では２桁）とすると、除数（法）ｃは２m 倍、即ち
ｃ×２m （３０１）となり、これが冗長２進演算部１０
に取り込まれる。また、シフト量ｍは除数ビットシフト
量記憶部２３に記憶される。
数（法）ｃをその最上位ビットが“１”になるまで上位
（左方向）にシフトする。この時のシフト量をｍ（図２
(c) では２桁）とすると、除数（法）ｃは２m 倍、即ち
ｃ×２m （３０１）となり、これが冗長２進演算部１０
に取り込まれる。また、シフト量ｍは除数ビットシフト
量記憶部２３に記憶される。
【００３３】また、被除数用左ビットシフト部２２も、
被除数（仮数）ａを上位（左方向）にシフトするが、除
算の回数を節約するためであり、被除数の場合、除数と
異なり、必ずしも最上位ビットが“１”となるまでシフ
トする必要はない。この時のシフト量をｎ（図２(c) で
は１桁）とすると、被除数（仮数）ａは２n 倍、即ちａ
×２n （３０２）となり、これが冗長２進演算部１０に
取り込まれる。また、シフト量ｎは被除数ビットシフト
量記憶部２４に記憶される。
被除数（仮数）ａを上位（左方向）にシフトするが、除
算の回数を節約するためであり、被除数の場合、除数と
異なり、必ずしも最上位ビットが“１”となるまでシフ
トする必要はない。この時のシフト量をｎ（図２(c) で
は１桁）とすると、被除数（仮数）ａは２n 倍、即ちａ
×２n （３０２）となり、これが冗長２進演算部１０に
取り込まれる。また、シフト量ｎは被除数ビットシフト
量記憶部２４に記憶される。
【００３４】次に、冗長２進演算部１０にて従来の冗長
２進演算法を用いた除算（剰余演算）が行われるが、こ
の時、除算回数制御部２５が２の（ｎ−ｍ）乗の位（図
２(c) では１０の−１乗の位であるから小数点第１位）
まで除算を行うよう制御する。
２進演算法を用いた除算（剰余演算）が行われるが、こ
の時、除算回数制御部２５が２の（ｎ−ｍ）乗の位（図
２(c) では１０の−１乗の位であるから小数点第１位）
まで除算を行うよう制御する。
【００３５】前述した除算の結果、冗長２進演算部１０
から剰余（余り）が出力されるが、この剰余は求める剰
余ｒの２n 倍（図２(c) では１桁分）、即ちｒ×２
n （３０３）（図２(c) では「９０」）である。そこ
で、剰余用右ビットシフト部２６では、被除数ビットシ
フト量記憶部２４に記憶されたシフト量ｎをもとに、得
られた剰余をｎビット（図２(c) では１桁分）だけ、下
位（右方向）にシフトする。
から剰余（余り）が出力されるが、この剰余は求める剰
余ｒの２n 倍（図２(c) では１桁分）、即ちｒ×２
n （３０３）（図２(c) では「９０」）である。そこ
で、剰余用右ビットシフト部２６では、被除数ビットシ
フト量記憶部２４に記憶されたシフト量ｎをもとに、得
られた剰余をｎビット（図２(c) では１桁分）だけ、下
位（右方向）にシフトする。
【００３６】このようにして得られた剰余ｒ（３０４）
（図２(c) では「９」）は、パラメタ保存用汎用レジス
タ部１０３に出力される。
（図２(c) では「９」）は、パラメタ保存用汎用レジス
タ部１０３に出力される。
【００３７】なお、被除数用左ビットシフト部２２及び
剰余用右ビットシフト部２６におけるシフト動作を停止
すれば、図２(b) で説明した方法１に従う演算も同様に
実行できる。
剰余用右ビットシフト部２６におけるシフト動作を停止
すれば、図２(b) で説明した方法１に従う演算も同様に
実行できる。
【００３８】
【 a×b mod c 】次に、乗剰余演算 a×b mod c を説明
する。乗剰余演算は、 ａ＜ｃ，ｂ＜ｃ ……(5) の時は、基本的な冗長２進演算器を用いることができ
る。しかし、 ｜ａ×ｂ｜＜｜ｃ｜ ……(6) の場合は剰余演算を直接演算することは不可能である。
する。乗剰余演算は、 ａ＜ｃ，ｂ＜ｃ ……(5) の時は、基本的な冗長２進演算器を用いることができ
る。しかし、 ｜ａ×ｂ｜＜｜ｃ｜ ……(6) の場合は剰余演算を直接演算することは不可能である。
【００３９】そこで、次に示すステップを行い、実行す
る。
る。
【００４０】ステップ１：ａ，ｃを入力し、剰余演算a
mod c と同様にして、仮数ａが法以下のａ´になるよう
にする。 ステップ２：ｂを入力し、剰余演算b mod c と同様にし
て、仮数ｂが法以下のｂ´になるようにする。 ステップ３：乗剰余演算a'×b' mod cの演算を行う。即
ち、 (a×b) mod c＝{(a mod c)×(b mod c)} mod c ＝（a'×b'） mod c が成り立つ。
mod c と同様にして、仮数ａが法以下のａ´になるよう
にする。 ステップ２：ｂを入力し、剰余演算b mod c と同様にし
て、仮数ｂが法以下のｂ´になるようにする。 ステップ３：乗剰余演算a'×b' mod cの演算を行う。即
ち、 (a×b) mod c＝{(a mod c)×(b mod c)} mod c ＝（a'×b'） mod c が成り立つ。
【００４１】以上によりレジスタに格納可能なビット数
以下であれば、それぞれのパラメタの大小に関わらず乗
剰余演算が可能になる。
以下であれば、それぞれのパラメタの大小に関わらず乗
剰余演算が可能になる。
【００４２】
【 ax mod c 】次に、羃乗剰余演算 ax mod c を説明す
る。羃乗剰余演算は、冗長２進演算器で羃乗剰余演算を
演算するために、乗剰余演算 a×b mod c の繰り返しで
実現している。
る。羃乗剰余演算は、冗長２進演算器で羃乗剰余演算を
演算するために、乗剰余演算 a×b mod c の繰り返しで
実現している。
【００４３】従って、乗剰余演算に帰着することができ
る。
る。
【００４４】
【２進演算への適用】２進数へ適用した時の具体例を図
４に示す。
４に示す。
【００４５】法ｃのレジスタの最上位ビットまでｃをビ
ットシフトし、ｃ´とする（図４では１２ビットシフト
している：４０１）。次に、仮数ａのレジスタの最上位
バイトに１が含まれるまでａをバイトシフトし、ａ´と
する（図４では１バイトシフトしている：４０２）。こ
うすることにより、冗長２進演算方式を適用することが
できるようになる。
ットシフトし、ｃ´とする（図４では１２ビットシフト
している：４０１）。次に、仮数ａのレジスタの最上位
バイトに１が含まれるまでａをバイトシフトし、ａ´と
する（図４では１バイトシフトしている：４０２）。こ
うすることにより、冗長２進演算方式を適用することが
できるようになる。
【００４６】次に、除算を開始する。但し、除算の終了
ビットは、法と仮数とのビットシフト量の差（図４の４
０３：４ビット）に対応する位である。答え、即ち剰余
は図４の４０４となる。
ビットは、法と仮数とのビットシフト量の差（図４の４
０３：４ビット）に対応する位である。答え、即ち剰余
は図４の４０４となる。
【００４７】
【発明の効果】以上説明したように、本発明によれば、
冗長２進演算法の高速演算の長所を生かし、かつ冗長２
進演算法の短所である演算ビット数の制限をなくすこと
ができる。
冗長２進演算法の高速演算の長所を生かし、かつ冗長２
進演算法の短所である演算ビット数の制限をなくすこと
ができる。
【図１】本発明の実施の形態の一例を示す装置構成図
【図２】本発明による剰余演算を１０進数に適用した場
合の演算例の説明図
合の演算例の説明図
【図３】図１中のパラメタシフト部の具体的構成の一例
を示す図
を示す図
【図４】本発明による剰余演算を冗長２進数に適用した
場合の演算例の説明図
場合の演算例の説明図
１００…剰余系演算装置、１０…冗長２進演算部、２０
…パラメタシフト部、３０…パラメタ保存用汎用レジス
タ部、２１…除数用左ビットシフト部、２２…被除数用
左ビットシフト部、２３…除数ビットシフト量記憶部、
２４…被除数ビットシフト量記憶部、２５…除算回数制
御部、２６…剰余用右ビットシフト部。
…パラメタシフト部、３０…パラメタ保存用汎用レジス
タ部、２１…除数用左ビットシフト部、２２…被除数用
左ビットシフト部、２３…除数ビットシフト量記憶部、
２４…被除数ビットシフト量記憶部、２５…除算回数制
御部、２６…剰余用右ビットシフト部。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 大山 勝一 東京都渋谷区桜丘町20番１号 エヌティテ ィエレクトロニクス株式会社内
Claims (10)
- 【請求項１】 ｈ進数の被除数をａ、除数をｃとした時
に剰余演算a mod c を行う剰余系演算方法において、 被除数ａ及び除数ｃをレジスタに格納し、 除数ｃの桁数ｊが格納可能な桁数ｉ桁未満の時、除数ｃ
全体を（ｉ−ｊ）桁シフトし、 ｈの−（ｉ−ｊ）乗の位まで剰余演算a mod c を行うこ
とを特徴とする剰余系演算方法。 - 【請求項２】 ｈ進数の被除数をａ、除数をｃとした時
に剰余演算a mod c を行う剰余系演算方法において、 被除数ａ及び除数ｃをレジスタに格納し、 除数ｃの桁数ｊが格納可能な桁数ｉ桁未満の時、除数ｃ
全体を（ｉ−ｊ）桁シフトし、 被除数ａの桁数ｌが格納可能な桁数ｋ（≧ｉ）桁未満の
時、被除数ａ全体を（ｋ−ｌ）桁シフトし、 ｈの｛（ｋ−ｌ）−（ｉ−ｊ）｝乗の位まで剰余演算a
mod c を行い、 得られた剰余を（ｋ−ｌ）桁、逆にシフトし、これを剰
余演算結果とすることを特徴とする剰余系演算方法。 - 【請求項３】 ｈ進数の被除数をａ及びｂ、除数をｃと
した時に乗剰余演算 a×b mod c を行う剰余系演算方法
において、 請求項１または２記載の方法を利用して剰余演算a mod
c ＝a'を行い、 請求項１または２記載の方法を利用して剰余演算b mod
c ＝b'を行い、 前記２つの結果同士の乗剰余演算a'×b' mod cを請求項
１または２記載の方法を利用して行うことを特徴とする
剰余系演算方法。 - 【請求項４】 ｈ進数の被除数をａ、羃指数をｂ、除数
をｃとした時に羃乗剰余演算 ab mod c を行う剰余系演
算方法において、 請求項３記載の方法を繰り返し利用して羃乗剰余演算 a
b mod c を行うことを特徴とする剰余系演算方法。 - 【請求項５】 請求項１乃至４いずれか記載の方法を２
進数で利用し、冗長２進演算法に適用したことを特徴と
する剰余系演算方法。 - 【請求項６】 ｈ進数の被除数をａ、除数をｃとした時
に剰余演算a mod c を行う剰余系演算装置において、 ｉ桁格納可能な除数格納手段と、 被除数格納手段と、 除数ｃの桁数ｊがｉ桁未満の時、除数ｃ全体を（ｉ−
ｊ）桁シフトする除数シフト手段と、 ｈの−（ｉ−ｊ）乗の位まで剰余演算a mod c を行う剰
余演算手段とを備えたことを特徴とする剰余系演算装
置。 - 【請求項７】 ｈ進数の被除数をａ、除数をｃとした時
に剰余演算a mod c を行う剰余系演算装置において、 ｉ桁格納可能な除数格納手段と、 ｋ（≧ｉ）桁格納可能な被除数格納手段と、 除数ｃの桁数ｊがｉ桁未満の時、除数ｃ全体を（ｉ−
ｊ）桁シフトする除数シフト手段と、 被除数ａの桁数ｌがｋ桁未満の時、被除数ａ全体を（ｋ
−ｌ）桁シフトする被除数シフト手段と、 ｈの｛（ｋ−ｌ）−（ｉ−ｊ）｝乗の位まで剰余演算a
mod c を行う剰余演算手段と、 得られた剰余を（ｋ−ｌ）桁、逆にシフトし、これを剰
余演算結果とする剰余逆シフト手段とを備えたことを特
徴とする剰余系演算装置。 - 【請求項８】 ｈ進数の被除数をａ及びｂ、除数をｃと
した時に乗剰余演算 a×b mod c を行う剰余系演算装置
において、 請求項６または７記載の装置を利用して剰余演算a mod
c ＝a'を行う剰余演算手段と、 請求項６または７記載の装置を利用して剰余演算b mod
c ＝b'を行う剰余演算手段と、 前記２つの結果同士の乗剰余演算a'×b' mod cを請求項
６または７記載の装置を利用して行う乗剰余演算手段と
を備えたことを特徴とする剰余系演算装置。 - 【請求項９】 ｈ進数の被除数をａ、羃指数をｂ、除数
をｃとした時に羃乗剰余演算 ab mod c を行う剰余系演
算装置において、 請求項８記載の装置を繰り返し利用して羃乗剰余演算 a
b mod c を行う羃乗剰余演算手段を備えたことを特徴と
する剰余系演算装置。 - 【請求項１０】 請求項６乃至９いずれか記載の装置を
２進数で利用し、冗長２進演算法に適用したことを特徴
とする剰余系演算装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5199298A JPH10307710A (ja) | 1997-03-05 | 1998-03-04 | 剰余系演算方法及びその装置 |
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9-50473 | 1997-03-05 | ||
| JP5047397 | 1997-03-05 | ||
| JP5199298A JPH10307710A (ja) | 1997-03-05 | 1998-03-04 | 剰余系演算方法及びその装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH10307710A true JPH10307710A (ja) | 1998-11-17 |
Family
ID=26390943
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5199298A Pending JPH10307710A (ja) | 1997-03-05 | 1998-03-04 | 剰余系演算方法及びその装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH10307710A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2010186076A (ja) * | 2009-02-12 | 2010-08-26 | Chugoku Electric Power Co Inc:The | 整数の暗号化及び復号化方法 |
| WO2011036746A1 (ja) * | 2009-09-24 | 2011-03-31 | 株式会社東芝 | 演算装置 |
| JP2011180390A (ja) * | 2010-03-01 | 2011-09-15 | Chugoku Electric Power Co Inc:The | 整数を暗号化及び復号化する方法、装置及びシステム |
-
1998
- 1998-03-04 JP JP5199298A patent/JPH10307710A/ja active Pending
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2010186076A (ja) * | 2009-02-12 | 2010-08-26 | Chugoku Electric Power Co Inc:The | 整数の暗号化及び復号化方法 |
| WO2011036746A1 (ja) * | 2009-09-24 | 2011-03-31 | 株式会社東芝 | 演算装置 |
| JP5175983B2 (ja) * | 2009-09-24 | 2013-04-03 | 株式会社東芝 | 演算装置 |
| US8909689B2 (en) | 2009-09-24 | 2014-12-09 | Kabushiki Kaisha Toshiba | Arithmetic device |
| JP2011180390A (ja) * | 2010-03-01 | 2011-09-15 | Chugoku Electric Power Co Inc:The | 整数を暗号化及び復号化する方法、装置及びシステム |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7805478B2 (en) | Montgomery modular multiplier | |
| US5448639A (en) | Digital signature device | |
| EP0801345B1 (en) | Circuit for modulo multiplication and exponentiation arithmetic | |
| JP4955182B2 (ja) | 整数の計算フィールド範囲の拡張 | |
| US7277540B1 (en) | Arithmetic method and apparatus and crypto processing apparatus for performing multiple types of cryptography | |
| US5274707A (en) | Modular exponentiation and reduction device and method | |
| Großschädl | A bit-serial unified multiplier architecture for finite fields GF (p) and GF (2m) | |
| JP4180024B2 (ja) | 乗算剰余演算器及び情報処理装置 | |
| US7831650B2 (en) | Method for modular multiplication | |
| US7046800B1 (en) | Scalable methods and apparatus for Montgomery multiplication | |
| US6917956B2 (en) | Apparatus and method for efficient modular exponentiation | |
| US7698357B2 (en) | Modular multiplication with parallel calculation of the look-ahead parameters | |
| JPH10307710A (ja) | 剰余系演算方法及びその装置 | |
| JP2001034167A (ja) | 演算装置及び暗号処理装置 | |
| Arazi et al. | On calculating multiplicative inverses modulo $2^{m} $ | |
| US20020114449A1 (en) | Modular multiplier and an encryption/decryption processor using the modular multiplier | |
| JP2002023999A (ja) | 乗算モジュール、乗法逆元演算回路、乗法逆元演算制御方式、該乗法逆元演算を用いる装置、暗号装置、誤り訂正復号器 | |
| JP2000207387A (ja) | 演算装置及び暗号処理装置 | |
| US20080114820A1 (en) | Apparatus and method for high-speed modulo multiplication and division | |
| EP1504338B1 (en) | "emod" a fast modulus calculation for computer systems | |
| KR100480997B1 (ko) | ＧＦ(ｐ)와 ＧＦ(2^ｍ)의 유한체 곱셈 연산 장치 | |
| TWI843313B (zh) | 模乘器、安全晶片、電子設備及加密方法 | |
| JP3913921B2 (ja) | 有限フィールドでの任意要素の逆数具現回路 | |
| TW202332229A (zh) | 用來進行功耗擾動操作以降低密碼系統功耗分析攻擊的成功率之方法、密碼系統處理電路及電子裝置 | |
| JP3210420B2 (ja) | 整数上の乗算回路 |