(57)【要約】【課題】  スマートカード及び移動端末機のような通信システムの環境における高速の暗号化/復号化及び電子署名のためのモジュラー乗算装置を提供する。【解決手段】  本発明は、nビットの乗数(Ａ)と被乗数(Ｂ)を入力とし、(m+2)クロック(ここで、m=n/2)内でA・B・R-1modN(ここで、R=4m+2)を計算するためにモンゴメリー類型のモジュラー乗算を行う装置及び方法を提案し、このような提案による装置は、乗数のビットを順次的にシフトさせてシフトされたビット列を生成し、前記生成されたビット列の下位２ビットをブース記録(Booth recording)することを特徴とする。本発明によれば、モジュラー乗算装置が、少ないゲート数を持ち、低電力を消耗し、高速で動作できるようにする。【選択図】  図１
2004280103.tif 000002
【特許請求の範囲】
【請求項１】
第１キー(Ｂ)と第２キー(Ｎ)を利用して一つのメッセージ(Ａ)を暗号化/復号化するメッセージ暗号化/復号化技術において、
ｎビットの前記それぞれのメッセージ、第１キー、そして第２キーを格納するそれぞれの領域を持つ貯蔵所；
毎クロックごとに前記メッセージと第１キーを利用して第１ｎ＋４ビット信号を発生させる記録ロジック；
前記第１ｎ＋４ビット信号と２つの並列ｎ＋２ビット入力信号を利用して一つの桁上げ値と２つの和値とから構成される３ビット信号列を発生させる第１桁上げ保存加算器(ＣＳＡ１)；
前記３ビット信号列と一つの桁上げ値を利用してモジュラー減少倍数(modular reduction multiple)を決定するための３ビット決定子を生成する商ロジック；
前記第２キーと前記３ビット決定子を利用して第２ｎ＋４ビット信号を生成する選択器；
前記第２ｎ＋４ビット信号と前記第１桁上げ保存加算器から出力されるそれぞれの和と桁上げ項を利用して和と桁上げ値を出力する第２桁上げ保存加算器(ＣＳＡ)；及び、
前記対をなす和と桁上げ値とあらかじめ定められた回路桁上げ値に対して全加算演算を行って桁上げ入力値を出力する第１全加算器；からなるモジュラー乗算装置。
【請求項２】
前記それぞれの領域は、前記それぞれのメッセージ、第１キー、そして第２キーのためのシフトレジスタであることを特徴とする請求項１に記載の乗算装置。
【請求項３】
前記メッセージは、毎クロックごとに２ビットずつ右にシフトされることを特徴とする請求項１に記載の乗算装置。
【請求項４】
前記第１ｎ＋４ビット信号は、０、Ｂ、２Ｂ、−Ｂ、及び−２Ｂのうち一つであることを特徴とする請求項１に記載の乗算装置。
【請求項５】
前記第２ｎ＋４ビット信号は０、Ｎ、２Ｎ、−Ｎ、及び−２Ｎのうち一つであることを特徴とする請求項１に記載の乗算装置。
【請求項６】
前記記録ロジックは、
前記メッセージの下位２ビットに対してブース記録(Booth recording)を行うブース記録回路；
前記２つの下位ビットと前記第１キーを多重化して０、Ｂ、及び２Ｂの中から一つを出力する多重化器；及び、
前記２つの下位ビットに基づいて選択的に前記多重化器から出力されるn+１ビット信号に対して１の補数化演算を行い、０、Ｂ、２Ｂ、−Ｂ、及び−２Ｂのうち一つを生成する１の補数化演算器；を含むことを特徴とする請求項１に記載の乗算装置。
【請求項７】
前記第１桁上げ保存加算器は、前記２つの並列ｎ＋４入力信号のそれぞれの対応する和と桁上げビットと前記第１ｎ＋４ビット信号の対応するビットに全加算演算を行って３ビット信号列を生成するｎ＋４個の全加算器から構成されることを特徴とする請求項１に記載の乗算装置。
【請求項８】
前記２つの並列ｎ＋４ビット入力信号のうち一つは、前記２番目の桁上げ保存加算器出力の和項から上位ｎ＋２ビットを選択し、前記選択されたｎ＋２ビットの上位に２ビットを挿入して生成されることを特徴とする請求項７に記載の乗算装置。
【請求項９】
前記２つの上位ビットは０であることを特徴とする請求項８に記載の乗算装置。
【請求項１０】
前記２つの並列ｎ＋４ビット入力信号のうち他の一つは、前記第２桁上げ保存加算器の出力の上位ｎ＋３ビットを選択し、前記選択されたｎ＋２ビットの上位に１ビットを挿入して生成されることを特徴とする請求項８に記載の乗算装置。
【請求項１１】
前記上位１ビットは０であることを特徴とする請求項１０に記載の乗算装置。
【請求項１２】
前記商ロジックは、
前記第１全加算器からの桁上げ入力値を臨時格納するためのＤフリップフロップ(D flip-flop)；
前記桁上げ入力値と前記第１桁上げ保存加算器(ＣＳＡ)の最下位全加算器から出力される和値に対して全加算演算を行う第３全加算器；
前記第１桁上げ保存加算器の最下位全加算器から出力される桁上げ値と２番目の最下位全加算器から出力される和値、そしてあらかじめ定められた回路桁上げ値に対して排他的論理和演算を行う排他的論理和器；及び
前記３番目の全加算器と前記排他的論理和器の出力、そしてあらかじめ定められた入力ビット(ｎ１)に組合演算(combination operation)を行って前記３ビット決定子信号を出力する組合回路；を含むことを特徴とする請求項１に記載の乗算装置。
【請求項１３】
前記第２桁上げ保存加算器(ＣＳＡ)は、前記第１桁上げ保存加算器の最下位和ビットと最上位桁上げビットを除外した対応する和及び桁上げビットと前記２番目のｎ＋４ビット信号の対応ビットに対してそれぞれ全加算演算を行って対をなす和と桁上げ値を出力するｎ＋４個の第４全加算器から構成されることを特徴とする請求項１に記載の乗算装置。
【請求項１４】
前記第１全加算器は、前記第２桁上げ保存加算器の２番目の最下位全加算器から出力される和値と最下位全加算器から出力される桁上げ値、そしてあらかじめ定められた回路桁上げ値(cin)に対して全加算演算を行って前記桁上げ入力値を出力することを特徴とする請求項１に記載の乗算装置。
【請求項１５】
ｍ＋２クロック(ｍ＝ｎ/２)の後に前記第２桁上げ保存加算器から出力される和と桁上げ項に対して桁上げ伝播加算演算を行う桁上げ伝播加算器をさらに含むことを特徴とする請求項１に記載の乗算装置。
【請求項１６】
前記桁上げ伝播加算器の出力が負数である場合、前記桁上げ伝播加算演算結果にモジュラーＮ値を足すことを特徴とする請求項１５に記載の乗算装置。
【請求項１７】
第１キー(Ｂ)と第２キー(Ｎ)を利用して一つのメッセージ(Ａ)を暗号化/復号化するメッセージ暗号化/復号化技術において、
ｎビットの前記それぞれのメッセージ、第１キー、そして第２キーを格納するそれぞれの領域を持つ貯蔵所；
毎クロックごとに前記メッセージと第１キーを利用して第１ｎ＋３ビット信号を発生させる記録ロジック；
前記第１ｎ＋３ビット信号と２つの並列ｎ＋２ビット入力信号を利用して一つの桁上げ値と２つの和値から構成される３ビット信号列を発生させる第１桁上げ保存加算器(ＣＳＡ１)；
前記３ビット信号列と一つの桁上げ値を利用してモジュラー減少倍数(modular reduction multiple)を決定するための２ビット決定子を生成する商ロジック；
前記第２キーと前記２ビット決定子を利用して第２ｎ＋３ビット信号を生成する選択器；
前記第２ｎ＋３ビット信号と前記第１桁上げ保存加算器から出力されるそれぞれの和と桁上げ項に対して第２桁上げ保存加算演算を行って対をなす和と桁上げ値を出力する第２桁上げ保存加算器(ＣＳＡ２)；及び
前記対をなす和と桁上げ値に論理積演算を行うことによって桁上げ入力値を出力する論理積演算器；からなる乗算装置。
【請求項１８】
前記分離された領域は、前記それぞれのメッセージ、第１キー、及び第２キーのためのシフトレジスタであることを特徴とする請求項１７に記載の装置。
【請求項１９】
前記メッセージは毎クロックごとに２ビットずつ右にシフトされることを特徴とする請求項１８に記載の乗算装置。
【請求項２０】
前記第１ｎ＋３ビット信号は、０、Ｂ、２Ｂ、及び３Ｂのうち一つであることを特徴とする請求項１７に記載の乗算装置。
【請求項２１】
前記第２ｎ＋３ビット信号は、０、Ｎ、２Ｎ、及び３Ｎのうち一つであることを特徴とする請求項１７に記載の乗算装置。
【請求項２２】
前記記録ロジックは、前記メッセージの２つの最下位ビットと前記第１キーのｎビットを多重化して前記第１ｎ＋３ビット信号を出力する多重化器であることを特徴とする請求項１７に記載の乗算装置。
【請求項２３】
前記第１桁上げ保存加算器(ＣＳＡ１)は、前記２つの並列ｎ＋３入力信号のそれぞれの対応する和と桁上げビットと前記第１ｎ＋３ビット信号の対応するビットに全加算演算を行って３ビット信号列を生成するｎ＋３個の第１全加算器から構成されることを特徴とする請求項１２に記載の乗算装置。
【請求項２４】
前記２つの並列ｎ＋３ビット入力信号のうち一つは、前記第２桁上げ保存加算器出力の和項から上位ｎ＋１ビットを選択して前記選択されたｎ＋１ビットの上位に２ビットを挿入して生成されることを特徴とする請求項２３に記載の乗算装置。
【請求項２５】
前記２つの上位ビットは０であることを特徴とする請求項２４に記載の乗算装置。
【請求項２６】
前記２つの並列ｎ＋３ビット入力信号のうち他の一つは、前記第２桁上げ保存加算器出力の桁上げ項から上位ｎ＋２ビットを選択し、前記選択されたｎ＋２ビットの上位に１ビットを挿入して生成されることを特徴とする請求項２４に記載の乗算装置。
【請求項２７】
前記上位１ビットは０であることを特徴とする請求項２６に記載の乗算装置。
【請求項２８】
前記商ロジックは、
前記第１全加算器からの桁上げ入力値を臨時格納するためのＤフリップフロップ(D flip-flop)；
前記桁上げ入力値と前記第１桁上げ保存加算器(ＣＳＡ１)の最下位全加算器から出力される桁上げ値に対して半加算演算を行う半加算器；
前記第１桁上げ保存加算器の最下位全加算器から出力される桁上げ値と２番目の最下位全加算器から出力される和値、そして前記半加算器の出力に対して排他的論理和演算を行う排他的論理和器；及び、
前記半加算器の出力と前記バター的論理和器の出力、そしてあらかじめ定められた入力ビット(ｎ１)に組合演算(combination  operation)を行って前記２ビット決定子信号を出力する組合回路；を含むことを特徴とする請求項１７に記載の乗算装置。
【請求項２９】
前記第２桁上げ保存加算器(ＣＳＡ２)は、前記第１桁上げ保存加算器の最下位和ビットと最上位桁上げビットを除外した対応する和及び桁上げビットと前記２番目のｎ＋３ビット信号の対応ビットに対してそれぞれ全加算演算を行って対をなす和と桁上げ値を出力するｎ＋３個の第２全加算器から構成されることを特徴とする請求項１７に記載の乗算装置。
【請求項３０】
前記排他的論理和演算器は、前記第２桁上げ保存加算器の２番目の下位第２全加算器から出力される和値と前記第２桁上げ保存加算器の最下位第２全加算器から出力される桁上げ値に論理積演算を行って前記桁上げ入力値を出力することを特徴とする請求項１７に記載の乗算装置。
【請求項３１】
ｍ＋２クロック(ｍ＝ｎ/２)の後に前記第２桁上げ保存加算器から出力される和と桁上げ項に対して桁上げ伝播加算演算を行う桁上げ伝播加算器をさらに含むことを特徴とする請求項１７に記載の乗算装置。
【請求項３２】
第１キー(Ｂ)と第２キー(Ｎ)を利用して一つのメッセージ(Ａ)を暗号化/復号化するメッセージ暗号化/復号化技術において、
それぞれｎビットの前記メッセージ、第１キー、そして第２キーをそれぞれ格納し；
毎クロックごとに前記メッセージと前記第１キーを利用して第１ ｎ＋４ビット信号を生成し；
前記第１ｎ＋４ビット信号と２つの並列ｎ＋４ビット入力信号に対して第１桁上げ保存加算演算を行って一つの桁上げ値と２つの和値から構成される３ビット信号列を出力し；
前記３ビット信号列と一つの入力桁上げ値を利用して商演算を行ってモジュラー減少倍数を決定するための３ビット決定子を生成し；
前記第２キーと前記３ビット決定子を利用して第２ｎ＋４ビット信号を生成し；
前記第２ｎ＋４ビット信号、前記第１桁上げ保存加算演算から出力されるそれぞれの和項と桁上げ項に第２桁上げ保存加算演算を行って対をなす和及び桁上げ値を出力し；
前記前記第２桁上げ保存加算演算から出力される和と桁上げ値とあらかじめ定められた回路桁上げ値に全加算演算を行って桁上げ入力値を出力することを特徴とする乗算方法。
【請求項３３】
前記メッセージは毎クロックごとに２ビットずつ右にシフトされることを特徴とする請求項３２に記載の乗算方法。
【請求項３４】
前記第１ｎ＋４ビット信号を生成する過程は、
前記メッセージの２下位ビットに対してブース記録を行い；
前記２下位ビットによって０、Ｂ、２Ｂ、−Ｂ、及び−２Ｂの中からいずれか一つを選択的に生成することを含む請求項３２に記載の乗算方法。
【請求項３５】
前記２並列ｎ＋４ビット入力信号のうち一つは、前記第２桁上げ保存加算演算により出力された和項から上位ｎ＋２ビットを選択し、前記ｎ＋２ビットの上位に２ビットを挿入して生成されることを特徴とする請求項３２に記載の乗算方法。
【請求項３６】
前記挿入される２ビットは０であることを特徴とする請求項３２に記載の乗算方法。
【請求項３７】
前記２つの並列ｎ＋４ビット入力信号のうち他の一つは、前記第２桁上げ保存加算演算により出力された桁上げ項から上位ｎ＋３ビットを選択し、前記上位ｎ＋３ビットの上位ビットに１ビットを挿入して生成されることを特徴とする請求項３２に記載の乗算方法。
【請求項３８】
前記挿入される１ビットは０であることを特徴とする請求項３２に記載の乗算方法。
【請求項３９】
前記３ビット信号列は２つの和値と一つの桁上げ値からなることを特徴とする請求項３２に記載の乗算方法。
【請求項４０】
前記２和値は、前記第１桁上げ保存加算演算により出力された和項の最下位ビットと２番目の最下位ビットであることを特徴とする請求項３９に記載の乗算方法。
【請求項４１】
前記一つの桁上げ値は、前記第１桁上げ保存加算演算により出力される桁上げ項の最下位ビットであることを特徴とする請求項３９に記載の乗算方法。
【請求項４２】
前記一つの入力桁上げ値は前記全加算演算により生成されることを特徴とする請求項３２に記載の乗算方法。
【請求項４３】
前記第２ｎ＋４ビット信号は、前記３ビット決定子の２下位ビットによって０、Ｎ、−Ｎ、及び２Ｎの中から選択されることを特徴とする請求項３２に記載の乗算方法。
【請求項４４】
前記対をなす和と桁上げ値は、前記第２桁上げ保存加算演算により出力される和項の２番目の最下位ビットと桁上げ項の最下位ビットであることを特徴とする請求項３２に記載の乗算方法。
【請求項４５】
前記第１桁上げ保存加算演算により出力される和と桁上げ項の最上位ビットは無視されることを特徴とする請求項３２に記載の乗算方法。
【請求項４６】
ｍ＋２クロック(ｍ＝ｎ/２)の後に前記第２桁上げ保存加算演算により出力される和と桁上げ項に対して桁上げ伝播加算演算を行う過程をさらに含むことを特徴とする請求項３２に記載の乗算方法。
【請求項４７】
前記桁上げ伝播加算演算の結果値が負数なら、モジュラーＮ(modulus N)を足す過程をさらに含むことを特徴とする請求項４６に記載の乗算方法。
【請求項４８】
第１キー(Ｂ)と第２キー(Ｎ)を利用して一つのメッセージ(Ａ)を暗号化/復号化するメッセージ暗号化/復号化技術において、
それぞれｎビットの前記メッセージ、第１キー、そして第２キーをそれぞれ格納し；
毎クロックごとに前記メッセージと前記第１キーを利用して第１ｎ＋３ビット信号を生成し；
前記第１ｎ＋３ビット信号と２つの並列ｎ＋３ビット入力信号に対して第１桁上げ保存加算演算を行って一つの桁上げ値と２つの和値から構成される３ビット信号列を出力し；
前記３ビット信号列と一つの入力桁上げ値を利用して商演算を行ってモジュラー減少倍数を決定するための２ビット決定子を生成し；
前記第２キーと前記２ビット決定子を利用して第２ｎ＋３ビット信号を生成し；
前記第２ｎ＋３ビット信号、前記第１桁上げ保存加算演算により出力される和項と桁上げ項に第２桁上げ保存加算演算を行って対をなす和及び桁上げ値を出力し；
前記対をなす和と桁上げ値に論理積演算を行って桁上げ入力値を出力することを特徴とする乗算方法。
【請求項４９】
前記メッセージは、毎クロックごとに２ビットずつ右にシフトされることを特徴とする請求項４８に記載の乗算方法。
【請求項５０】
前記第１ｎ＋３ビット信号は、前記メッセージの２下位ビットと前記第１キーを構成するビットを多重化して生成されることを特徴とする請求項４８に記載の乗算方法。
【請求項５１】
前記第１ｎ＋３ビット信号は０、Ｂ、２Ｂ、及び３Ｂのうち一つであることを特徴とする請求項４８に記載の乗算方法。
【請求項５２】
前記２つの並列ｎ＋３ビット入力信号のうち一つは、前記第２桁上げ保存加算演算により出力される和項から上位ｎ＋１ビットを選択し、前記ｎ＋１ビットの上位に２ビットを挿入して生成されることを特徴とする請求項４８に記載の乗算方法。
【請求項５３】
前記挿入される上位２ビットは０であることを特徴とする請求項５２に記載の乗算方法。
【請求項５４】
前記２つの並列ｎ＋３ビット入力信号のうち他の一つは、前記第２桁上げ保存加算演算により出力される桁上げ項から上位ｎ＋２ビットを選択し、前記選択されたｎ＋２ビットの上位に１ビットを挿入して生成されることを特徴とする請求項５２に記載の乗算方法。
【請求項５５】
前記挿入される上位１ビットは０であることを特徴とする請求項５４に記載の乗算装置。
【請求項５６】
前記３ビット信号列は、２つの和値と一つの桁上げ値を含むことを特徴とする請求項４８に記載の乗算方法。
【請求項５７】
前記２和値は、前記第１桁上げ保存加算演算により出力される和項の最下位ビットと２番目の最下位ビットであることを特徴とする請求項５６に記載の乗算方法。
【請求項５８】
前記一つの桁上げ値は、前記第１桁上げ保存加算演算により出力される桁上げ項の最下位ビットであることを特徴とする請求項５６に記載の乗算方法。
【請求項５９】
前記一つの入力桁上げ値は、前記論理積演算により生成されることを特徴とする請求項４８に記載の乗算方法。
【請求項６０】
前記２ビット決定子によって前記第２ｎ＋３ビット信号は０、Ｎ、２Ｎ、及び３Ｎから選択されることを特徴とする請求項４８に記載の乗算方法。
【請求項６１】
前記対をなす和と桁上げ値は前記第２桁上げ保存加算演算により出力された和項の最下位和値と桁上げ項の２番目の最下位ビットであることを特徴とする請求項４８に記載の乗算方法。
【請求項６２】
前記第１桁上げ保存加算演算により出力される和と桁上げ項の最上位ビットは無視されることを特徴とする請求項４８に記載の乗算方法。
【請求項６３】
ｍ＋２クロックの後に前記第２桁上げ保存加算演算により出力される和と桁上げ項に対して桁上げ伝播加算演算を行う過程をさらに含むことを特徴とする請求項４８に記載の乗算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化技術に関し、特に、暗号化/復号化及びデジタル署名などに使用するためのモンゴメリー類型のモジュラー乗算装置及び方法に関する。
【背景技術】
【０００２】
電子商取り引きのためのスマートカード(smart card)及び電子貨幣、セルラー電話機のような移動通信機器(mobile device)、小型コンピュータ(small-sized computer)などを使用する通信システムにおいて、情報(電子的文書あるいはデータ)を暗号化/復号化したり、転送情報にデジタル署名を行って安全に転送することは好ましいことと言える。ここで、デジタル署名とは、情報の電子的な交換に際し、従来紙に自筆署名した機能と同一な機能を電子的文書に提供可能にする技術のことを意味する。特に、最近ではインターネットの使用人口が急激に増えつつあることに伴ってインターネットを介した個人情報などの転送も頻繁になり、したがって、安全でないチャンネルを通じたより安全な情報の転送が要求されている実情である。
【０００３】
公開キー方式などを利用した暗号化/復号化及びデジタル署名には、ＲＳＡ(Rivest-Shamir-Adleman)、ElGamal、Schnorrなど様々な提案されたアルゴリズムを使用することができる。前記アルゴリズムの国際標準には、ＲＳＡアルゴリズムに基盤したＩＳＯ(International Standard Organization)/ＩＥＣ(International Electrotechnical Commission)９７９６が採択され、米国ではElGamalの変形としてＤＳＡ(Digital Signature Standard)が採択され、ロシアではロシア連邦国家標準(GOSSTANDART；通常、GOSTという)に基づく方式が採択され、韓国ではＫＣ−ＤＳＡが採択されている。しかし、実際には様々な通信システムでは多くのＰＫＣＳ(Public Key Cryptography Standard)が具現されている実情である。これら様々なアルゴリズムのためにはモジュラー累乗のmemodN演算が要求されるが、このモジュラー累乗は、モジュラー乗算、A・BmodN演算の反復的な遂行を意味する。
【０００４】
ＲＳＡなど公開キー暗号に基盤したデジタル署名を生成及び検証する上で必須とされるモジュラー乗算を行うための多くのアルゴリズムが提案された。例えば、R. L. Rivest et al, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, Vol. 21, pp.１２０-126, 1978；P. L. Montgomery,“ Modular Multiplication without Trial Division,” Math. Of Comp., Vol. 44, No. 170, pp.519-521, 1985；S. R. Dusse and B. S. Kaliski Jr.,“ A cryptographic library for the Motorola DSP56000,” Proc. Eurocrypto’90, pp.230-244, 199.；Springer-Verlag, A. Bosselaers, R. Govaerts and J. Vandewalle,“ Comparison of three modular reduction functions,” Advances in Cryptology-CRYPTO’93, pp.175-186, 1993などの論文がある。前記アルゴリズムの中でモンゴメリー(Montgomery)アルゴリズムは、単純モジュラー乗算では難しい手続きを持っているが、多様な暗号アルゴリズムに必要なモジュラー累乗のためのモジュラー乗算には計算効率面から最も効率的であるという事実が、論文D. R. Stinson, Cryptography, CRC Press, 1995により明らかになった。米合衆国特許US Patent No. 6, 185, 596は前記モンゴメリーアルゴリズムにより具現した装置の一例を開示している。
【０００５】
前述したように公開キー暗号化/復号化及び電子署名のための多くのアルゴリズム及びアーキテクチャーが提案された。しかし、大部分の提案されたアルゴリズム及びアーキテクチャーに基づくモジュラー乗算装置は、高速の公開キー暗号化/復号化を目的とするものであるだけに、多数のゲート(Gate)を必要とし、多い電力を消耗するという欠点があった。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、本発明の目的は、スマートカード及び移動端末機のような通信システムの環境において高速の暗号化/復号化及び電子署名のためのモジュラー乗算装置が少ないゲート数を持つようにすることにある。
【０００７】
本発明の他の目的は、スマートカード及び移動端末機のような通信システムの環境において高速の暗号化/復号化及び電子署名のためのモジュラー乗算装置が低電力を消耗するようにすることにある。
【０００８】
本発明のさらに他の目的は、スマートカード及び移動端末機のような通信システムの環境において暗号化/復号化及び電子署名のためのモジュラー乗算装置が高速に動作するようにすることにある。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、本発明は、nビットの乗数(Ａ)と被乗数(Ｂ)を入力とし、(m+2)クロック(ここで、m=n/2)内でA・B・R-1modN(ここで、R=4m+2)を計算するためにモンゴメリー類型のモジュラー乗算を行う装置及び方法を提案し、このような提案による装置は乗数のビットを順次的にシフトさせてシフトされたビット列を生成し、前記生成されたビット列の下位２ビットをブース記録(Booth recording)することを特徴とする。
【００１０】
本発明の第１実施例によれば、モジュラー乗算装置の記録ロジックは、前記乗数のビットが順次的にシフトされて生成されたビット列の下位２ビットをブース記録(Booth recording)し、前記ブース記録された結果と被乗数を多重化して(n+4)ビットの符号付き二進数を出力する。第１桁上げ保存加算器(ＣＳＡ)は、(n+4)個の全加算器を備えており、(n+2)ビットの第１信号と、(n+3)ビットの第２信号と、前記記録ロジックからの(n+4)ビットの前記二進数を第３信号として入力し、前記第１信号の上位(n+2)番目のビットは前記全加算器のうち上位３個の全加算器に入力され、前記第２信号の上位(n+3)番目のビットは前記全加算器のうち上位２個の全加算器に入力され、前記(n+3)個の全加算器により(n+4)ビットの桁上げ値と和値を出力する。商ロジックは、前記第１ ＣＳＡからの前記(n+4)ビットの桁上げ値と和値の中から選択された下位２個の全加算器から出力される和値と下位１個の全加算器から出力される桁上げ値を入力し、モジュラー減少の倍数を決定するための３ビットの決定値を出力する。選択器は、前記決定値に基づいてあらかじめ定められたモジュロ数の集合のうち一つのモジュロ数を選択して出力する。第２桁上げ保存加算器(ＣＳＡ)は、(n+4)個の全加算器を具備し、前記選択器から選択された(n+4)ビットのモジュロ数を第１信号として入力し、前記第１ＣＳＡからの前記(n+4)ビットの桁上げ値のうち最上位桁上げ値を除外した残りの(n+3)ビットの桁上げ値を第２信号として入力し、前記(n+4)ビットの和値のうち最下位桁上げ値を除外した残りの(n+3)ビットの和値を第３信号として入力し、前記第１信号の(n+4)ビットは前記全加算器の最下位全加算器から順次入力され、前記第２信号の(n+3)ビットは前記全加算器のうち下位２番目の全加算器から順次入力され、前記第３信号の(n+3)ビットは前記全加算器の下位２番目の全加算器から順次入力され、前記(n+4)個の全加算器により(n+4)ビットの桁上げ値と和値を出力する。全加算器は前記第２ ＣＳＡの最下位全加算器から出力される桁上げ値と下位２番目の全加算器から出力される和値を全加算して桁上げ入力値として前記商ロジックに提供する。桁上げ伝播加算器(ＣＰＡ)は、前記第２ＣＳＡからの桁上げ値と和値を加算して出力する。
【００１１】
好ましくは、前記乗算装置は、前記乗数のビットを順次的にシフトさせて前記シフトされたビット列を生成するシフトレジスタと、前記被乗数を格納するためのレジスタとをさらに含む。
【００１２】
好ましくは、前記記録ロジックは、前記生成されたビット列の下位２ビットをブース記録する記録回路と、前記ブース記録された結果と前記被乗数を多重化する多重化器と、前記生成されたビット列の下位２ビットに基づいて前記多重化器の出力を選択的に１の補数化して前記(n+4)ビットの符号付き二進数を出力する補数化器を含む。
【００１３】
好ましくは、前記商ロジックは、前記桁上げ入力値と前記第１ＣＳＡの最下位全加算器から出力される和値を全加算する全加算器と、前記第１ＣＳＡの最下位全加算器から出力される桁上げ値と２番目の全加算器から出力される和値を排他的論理和する排他的論理和器と、前記全加算器と前記排他的論理和器の出力とあらかじめ設定された入力ビットを組合わせて前記３ビットの決定値として出力する組合回路とを含む。また、前記商ロジックは、前記桁上げ入力値を格納するためのＤフリップフロップをさらに含み、前記商ロジックの前記全加算器及び前記排他的論理和器にはあらかじめ設定された補正用桁上げ値が提供され、前記商ロジックの前記全加算器には前記被乗数の符号ビットが提供され、前記商ロジックの前記全加算器の出力は前記第２ ＣＳＡの最下位全加算器に提供される。
【００１４】
本発明の第２実施例によれば、モジュラー乗算装置の記録ロジックは、前記乗数のビットが順次的にシフトされて生成されたビット列の下位２ビットをブース記録(Booth recording)し、前記ブース記録された結果と被乗数を多重化して(n+3)ビットの二進数を出力する。第１桁上げ保存加算器(ＣＳＡ)は、(n+3)個の全加算器を備えており、(n+1)ビットの第１信号と、(n+2)ビットの第２信号と、前記記録ロジックからの(n+3)ビットの前記二進数を第３信号として入力し、前記第１信号の上位(n+1)番目のビットは前記全加算器のうち上位３番目の全加算器に入力され、前記第２信号の上位(n+2)番目のビットは前記全加算器のうち上位２番目の全加算器に入力され、前記全加算器のうち最上位全加算器に“０”レベルの前記第１信号が入力され、前記(n+3)個の全加算器により(n+3)ビットの桁上げ値と和値を出力する。商ロジックは、前記第１ＣＳＡからの前記(n+3)ビットの桁上げ値と和値の中から選択された下位２個の全加算器から出力される和値と下位１個の全加算器から出力される桁上げ値を入力し、モジュラー減少の倍数を決定するための２ビットの決定値を出力する。選択器は、前記決定値に基づいてあらかじめ定められたモジュロ数の集合のうち一つのモジュロ数を選択して出力する。
【００１５】
第２桁上げ保存加算器(ＣＳＡ)は、(n+3)個の全加算器を具備し、前記選択器から選択された(n+3)ビットのモジュロ数を第１信号として入力し、前記第１ＣＳＡからの前記(n+3)ビットの桁上げ値のうち最上位桁上げ値を除外した残りの(n+2)ビットの桁上げ値を第２信号として入力し、前記(n+3)ビットの和値のうち最下位桁上げ値を除外した残りの(n+2)ビットの和値を第３信号として入力し、前記第１信号の(n+3)ビットは前記全加算器の最下位全加算器から順次入力され、前記第２信号の(n+2)ビットは前記全加算器のうち下位２番目の全加算器から順次入力され、前記第３信号の(n+2)ビットは前記全加算器の下位２番目の全加算器から順次入力され、前記(n+3)個の全加算器により(n+4)ビットの桁上げ値と和値を出力する。論理積演算器は、前記第２ＣＳＡの最下位全加算器から出力される桁上げ値と下位２番目の全加算器から出力される和値を論理積演算して桁上げ入力値として前記商ロジックに提供する。桁上げ伝播加算器(ＣＰＡ)は、前記第２ＣＳＡからの桁上げ値と和値を加算して出力する。
【００１６】
好ましくは、前記乗算装置は、前記乗数のビットを順次的にシフトさせて前記シフトされたビット列を生成するシフトレジスタと、前記被乗数を格納するためのレジスタとをさらに含む。
【００１７】
好ましくは、前記記録ロジックは、前記生成されたビット列の下位２ビットに基づいて前記被乗数を多重化する多重化器である。
【００１８】
好ましくは、前記商ロジックは、前記桁上げ入力値と前記第１ＣＳＡの最下位全加算器から出力される和値を半加算する半加算器と、前記第１ＣＳＡの最下位全加算器から出力される桁上げ値と２番目の全加算器から出力される和値を排他的論理和する排他的論理和器と、前記全加算器と前記排他的論理和器の出力とあらかじめ設定された入力ビットを組合わせて前記２ビットの決定値として出力する組合回路とを含む。また、前記商ロジックは、前記桁上げ入力値を格納するためのＤフリップフロップをさらに含み、前記商ロジックの前記半加算器の出力は前記第２ ＣＳＡの最下位全加算器に提供される。
【００１９】
したがって、本発明は、暗号化/復号化及びデジタル署名を生成及び検証するのに応用することができる。つまり、本発明は、電子的文書あるいはデータを暗号化/復号化したり、その文書あるいはデータに署名機能を提供し得るデジタル署名を生成/検証する上で利用可能である。
【００２０】
前述した内容は、当該分野で通常の知識を持つ者が、後述される本発明の具体的な説明を通じてより理解できるようにするために本発明の特徴及び技術的な長所を多少広範囲に略述したものである。
【００２１】
本発明の請求範囲の主題を形成する本発明の追加的な特徴及び長所を述べるに先立って、当該技術分野で通常の知識を持つ者は、本発明の同一の目的を達成するために他の構造を変更したり、設計する基礎として発明の開示された概念及び具体的な実施例が容易に使用され得るという事実を認識する必要がある。また、当該技術分野で通常の知識を持つ者は、発明と均等な構造が本発明の最も広い形態の思想及び範囲を外れないという事実も認識されたい。
【発明の効果】
【００２２】
本発明は、A・B・2-(n+4)modNを計算する回路を記述したものであり、記述された回路を利用して一般のモジュラー乗算であるA・BmodNを計算できる。このような本発明に基づいて計算されたA・BmodNは、デジタル署名を生成及び検証するための機器に使用されるハードウェア的な装置に使用することができる。また、本発明は、ＩＣカードに基づく電子署名、認証、暗／復号化のハードウェア装置に使用することができる。また、本発明は、モジュラー乗算を行う電子署名機器によって暗号及び復号化する機器を提供することができる。また、本発明は、電子署名機器に基づいて、NIST-DSS、ＲＳＡ、ElGamal、Schnorr電子署名など既存の公開キー暗号システムを具現する上で利用することができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の好ましい実施例を添付図面を参照しつつ詳細に説明する。図面中、同一の構成要素にはな可能な限り同一の参照符号及び番号を共通使用するものとする。尚、以下に本発明を説明するにあたり、周知技術については適宜説明を省略するものとする。
【００２４】
Ａ．本発明の概要
以下に説明される本発明はそれぞれｎビットの、A = an-1・2n-1 + ・・・ +a1・2+a0、B = bn-1・2n-1 + ・・・ +b1・2+b0、N = nn-1・2n-1 + ・・・ +n1・2+n0についてモンゴメリー(Montgomery)アルゴリズムを利用してモジュラー乗算を行うための装置及びそれによる方法を提案している。この時、Ａは乗数、Ｂは被乗数、Ｎはモジュラー数を表し、これらのビット大きさは５１２あるいは１０２４のように大きな数になり得る。
【００２５】
前記モジュラー乗算動作A・BmodNの具現は、後述される２つの実施例による。各実施例はそれぞれｎビットのＡ、Ｂ、Ｎ(ここで、-N≦A,B<N)を入力として受けてm+2(ここで、m=n/2)クロック内にA・B・R-1modN(ここで、 R=4m+2)を計算するモジュラー乗算装置及び方法を提案する。このように提案されたモジュラー乗算装置による乗算結果を利用してA・BmodNが計算可能であり、また、ＲＳＡ演算遂行に必要なモジュラー累乗memodNになり得ることが説明されるはずである。図１ないし図６は、本発明の第１実施例に係るモジュラー乗算装置を構成する要素の構成を示す図であり、図７ないし図１３は本発明の第２実施例に係るモジュラー乗算装置を構成する要素の構成を示す図である。そして、図１４は本発明の実施例に係るモジュラー乗算装置が利用されるＩＣカードのブロック構成を示す図である。
【００２６】
後述する本発明の実施例に係るモジュラー乗算装置は、乗数のビットを順次的にシフトさせてシフトされたビット列を生成し、前記生成されたビット列の下位２ビットをブース記録(Booth recording)することを特徴とする。つまり、従来技術に係るモジュラー乗算装置が乗数のビットを順次的にシフトさせながら生成される下位１ビットだけを記録したことに比べ、本発明では記録の対象が下位２ビットになるように処理することによって乗算動作がより高速で行われるようにする。言い換えれば、本発明の実施例に係るモジュラー乗算装置は変形された記録ロジックを備えており、モジュラー乗算装置を構成する残りの他の要素は、前記変形された記録ロジックに対応する形態に構成されてモンゴメリーアルゴリズムに基づくモジュラー乗算動作を行う。
【００２７】
Ｂ．第１実施例
Ｂ−１．発明の構成
図１は、本発明の第１実施例に係るモジュラー乗算装置の構成を示す図である。
図１を参照すれば、前記モジュラー乗算装置は、記録ロジック(Recording Logic)１１０、第１桁上げ保存加算器(Carrier save Adder；以下“ＣＳＡ”と称する)１２０、商ロジック(Quotient Logic)１３０、選択器１４０、第２ＣＳＡ１５０、全加算器(ＦＡ；Full Adder)１６０から構成される。前記モジュラー乗算装置は、モンゴメリーアルゴリズムに基づいてそれぞれｎビットのＡ、Ｂ、Ｎ(ここで、-N≦A,B<N)を入力として受けてm+2(ここで、m=n/2)クロック内にA・B・R-1modN(ここで、R=4m+2)を計算するモジュラー乗算装置に対するハードウェア的な構成である。つまり、このモジュラー乗算装置はA・B・2-(n+4)modNを計算するための構成を持つ。
【００２８】
前記ＣＳＡ１２０、１５０はそれぞれ(n+4)個の全加算器が並列に構成されるものであり、３ビット入力でそれぞれ桁上げビットと和ビットを出力する。前記記録ロジック１１０は、乗数Ａを基盤にして変形されたブース記録(modified Booth recoding)動作を行い、(n+4)ビットの符号付き拡張(signed extension)ビットとして0、±B、±2B値の中で一つを出力する。前記商ロジック１３０は、前記ＣＳＡ１ １２０の最下位(ＬＳＢ:Least Significant Bit)桁上げ値C1,0、和ＬＳＢ ２ビットS1,1、S1,0とCarry-in、Ｂの符号ビットを入力とし、モジュラー減少(Modular reduction)の倍数を決定するための値である３ビットのq2q1q0を出力する。前記選択器１４０は、前記決定されたq値に基づいて0、±1、±2 の中で一つの値を選択して出力するためのものであり、多重化器(ＭＵＸ：Multiplexer)で具現可能である。前記全加算器１６０は、前記ＣＳＡ２ １５０の出力２ビットであるS2,1、C2,0と桁上げ値cinを入力して全加算動作を行い、その全加算結果値を桁上がり(Carry-in)信号として前記商ロジック１３０に提供する。
【００２９】
図１には示さなかったが、毎クロックごとに前記ＣＳＡ２ １５０の出力である桁上げ値と和値をそれぞれ格納するための臨時格納レジスタ(Ｃ)、レジスタ(Ｒ)が備えられ、また、前記臨時格納レジスタら(Ｃ、Ｒ)に格納された値を加算してモジュラー乗算結果として出力するための桁上げ伝播加算器 (Carry Propagation Adder)が具備されるという事実に留意する必要がある。
【００３０】
図２は、図１に示す記録ロジック１１０のより具体的な構成を示す図である。
図２に示すように、前記記録ロジック１１０は、乗数(Ａ)のビットが順次的にシフトされて生成されたビット列の下位２ビットをブース記録(Booth recording)し、前記ブース記録された結果と被乗数(Ｂ)を多重化して(n+4)ビットの符号付き二進数を出力する。すなわち、前記記録ロジック１１０の前段には前記乗数のビットを順次的にシフトさせて前記シフトされたビット列を生成するシフトレジスタ１０２と、前記被乗数を格納するためのレジスタ１０４が備えられる。前記記録ロジック１１０は、記録回路１１２と、多重化器(ＭＵＸ)１１４と、１の補数化器１１６とから構成される。前記記録回路１１２は、前記生成されたビット列の下位２ビットai+1、ai をブース記録(Booth recording)する。前記多重化器１１４は、前記ブース記録された結果(zi+1)と前記被乗数を多重化し、多重化結果として0、B、2Bを出力する。前記１の補数化器１１６は前記生成されたビット列の下位２ビットに基づいて前記多重化器１１４の出力を選択的に１の補数化し、前記(n+4)ビットの符号付き二進数を出力する。前述した前記記録ロジック１１０は乗数Ａを基盤にして変形されたブース記録(modified Booth recoding)を具現した回路であり、(n+4)ビットの符号付き拡張(signed extension)ビットを出力するが、この値は0、±B、±2B値のうち一つである。
【００３１】
図３は、図１に示すＣＳＡ１ １２０のより具体的な構成を示す図である。
図３を参照すれば、前記ＣＳＡ１ １２０は、(n+4)個の全加算器１２１〜１２５を備えており、(n+2)ビットの第１信号(S2,2 〜S2,n+3)と、(n+3)ビットの第２信号(C2,1〜C2,n+3)と、前記記録ロジック１１０からの(n+4)ビットの前記二進数を第３信号(B0〜Bn+3)として入力し、前記(n+4)個の全加算器１２１〜１２５により全加算して(n+4)ビットの桁上げ値(C1,0〜C1,n+3)と和値(S1,0〜S1,n+3)を出力する。この時、前記第１信号の上位(n+2)番目のビットS2,n+3は、前記全加算器のうち上位３個の全加算器１２３〜１２５に入力され、前記第２信号の上位(n+3)番目のビットC2,n+3は前記全加算器のうち上位２個の全加算器１２４、１２５に入力される。
【００３２】
図４は、図１に示す商ロジック１３０のより具体的な構成を示す図である。
図４を参照すれば、前記商ロジック１３０は、前記ＣＳＡ１ １２０からの前記(n+4)ビットの桁上げ値と和値の中から選択された下位２個の全加算器から出力される和値(S1,0、S1,1)と下位１個の全加算器から出力される桁上げ値(C1,0)を入力し、モジュラー減少の倍数を決定するための３ビットの決定値q2q1q0を出力する。前記商ロジック１３０は、ディー(D)フリップフロップ１３２と、全加算器１３４と、排他的論理和(XOR)器１３６と、組合回路１３８から構成される。前記Ｄフリップフロップ１３２は桁上げ入力値Carry-inを入力して一時的に格納する。前記全加算器１３４は、前記Ｄフリップフロップ１３２に格納された桁上げ入力値Carry-inと前記ＣＳＡ１ １２０の最下位全加算器１２１から出力される和値(S1,0)を全加算する。前記排他的論理和器１３６は、前記ＣＳＡ１ １２０の最下位全加算器１２１から出力される桁上げ値(C1,0)と２番目の全加算器１２２から出力される和値(S1,1)を排他的論理和する。前記全加算器１３４及び前記排他的論理和器１３６にはあらかじめ設定された補正用桁上げ値(cin)が提供され、また、前記全加算器１３４には被乗数の符号ビット(B sign)が提供される。前記組合回路１３８は、前記全加算器１３４の出力(SO)と前記排他的論理和器１３６の出力(S1)とあらかじめ設定された入力ビット(n1)を組合わせて３ビットの決定値(q2q1q0)として出力する。
【００３３】
図５は、図１に示すＣＳＡ２ １５０のより具体的な構成を示す図である。
図５を参照すれば、前記ＣＳＡ２ １５０は、(n+4)個の全加算器１５１〜１５６を備えている。前記ＣＳＡ２ １５０は前記選択器１４０から選択された(n+4)ビットのモジュロ数N(N0 - Nn+3)を第１信号として入力し、前記ＣＳＡ１ １２０からの(n+4)ビットの桁上げ値のうち最上位桁上げ値を除外した残りの(n+3)ビットの桁上げ値(C1,0〜C1,n+3)を第２信号として入力し、前記(n+4)ビットの和値の中で最下位桁上げ値を除外した残りの(n+3)ビットの和値(S1,1〜S1,n+3)を第３信号として入力し、前記(n+4)個の全加算器１５１〜１５６により(n+4)ビットの桁上げ値(C2,0〜C2,n+3)と和値(S2,0〜S2,n+3)を出力する。この時、前記第１信号の(n+4)ビットは前記全加算器の最下位全加算器１５１から順次入力され、前記第２信号の(n+3)ビットは前記全加算器のうち下位２番目の全加算器１５２から順次入力され、前記第３信号の(n+3)ビットは前記全加算器の下位２番目の全加算器１５２から順次入力される。前記全加算器のうち最下位全加算器１５１には前記商ロジック１３０の全加算器１３４からの出力(S0)と、q1,2と、モジュロ数(N)を表す最下位ビット(N0)が入力される。
【００３４】
図６は、図１に示す全加算器１６０のより具体的な構成を示す図である。
図６を参照すれば、前記全加算器１６０は、前記ＣＳＡ２ １５０の最下位全加算器１５１から出力される桁上げ値(C2,0)と下位２番目の全加算器１５２から出力される和値(S2,0)を全加算して桁上げ入力値(Carry-in)として出力する。また、前記全加算器１６０は全加算動作のためにあらかじめ設定された補正用桁上げ値(cin)を受け、その全加算結果として桁上げ入力値(Carry-in)を出力する。この桁上げ入力値(Carry-in)は前記商ロジック１３０に提供される。
【００３５】
Ｂ−２．発明の原理
本発明は、それぞれｎビットのＡ、Ｂ、Ｎ(ここで、-N≦A,B<N)を入力として受けてm+2(ここで、m=n/2)クロック内にA・B・R-1modN (ここで、R=4m+2)を計算する装置に関するものである。このような本発明の具現に適用される次の三つの原理が説明される。第一に、モジュラー乗算のための乗数(Ａ)及び被乗数(Ｂ)を表現する原理が説明される。第二に、モジュラー乗算のための乗数(Ａ)を記録する原理が説明される。第三に、本発明の記録原理を利用したモンゴメリーアルゴリズムに対する原理が説明される。
【００３６】
<Number Representation>
本発明ではモジュラー乗算のために乗数(Ａ)と被乗数(Ｂ)を符号付き二進数で表現(Signed binary representation)する。すなわち、それぞれｎビットのＡ、Ｂは符号付き動作(signed operation)のためにそれぞれ(n+4)ビットに変換されるが、このような変換過程中に値が負数である場合には１の補数形態に変換される。
【００３７】
<Booth's Recording>
本発明では、本発明が出願される前に当該分野で通常の知識を持つ者に周知されたブース記録(Booth Recording)方式を変形して変形されたブース記録(Modified Booth Recording)方式を使用することを特徴とする。このような本発明の特徴は、モジュラー乗算がより速い速度に行われるようにする効果を持つ。乗数Ａは前記変形されたブース記録方式により２ビットずつzi(ここで、0≦i≦m+1)として記録される。この時、an+4 = an+3, a-1 = 0と仮定する。下記表１に、本発明による変形されたブース記録の規則を示す。
【００３８】
【表１】
2004280103.tif 000003
【００３９】
<Booth's Recodingを利用したRadix-4 Montgomery Algorithm>
下記のアルゴリズムは、本発明がradix-4 モンゴメリーモジュラー乗算のために前記変形されたブース記録方式を利用していることを示している。元来モンゴメリーアルゴリズムでは、結果値とmodulus Nと比較して結果値がmodulus Nより大きければ一度減算をしなければならないが、下記に示すアルゴリズムではその手続きがないことがわかる。
【００４０】
【数１】
2004280103.tif 000004
【００４１】
上記の式(1)〜(7)に示したアルゴリズムで、(3)手続きのAiはブース記録された２ビットを意味し、-2< Ai<2の値を持つ。(4)手続きは、(5)手続きの結果値のＬＳＢ(Least Significant Bit)２ビットが‘0’になるようにする関数を意味する。前記(4)手続きでの結果値は入力ビットs1, s0, n1,n0に依存し、下記表２に示すように決定される。モジュラー減少(modular reduction)に使用される値qiのＭＳＢ(Most Significant Bit)のqi2は符号ビットであり、qiは集合{0、±1、2}元素のうち一つである。qiは下記の式（9）によって計算される。
【００４２】
【数２】
2004280103.tif 000005
【００４３】
【表２】
2004280103.tif 000006
【００４４】
Ｂ−３.発明の動作
本発明はそれぞれｎビットのＡ、Ｂ、Ｎ(ここで、-N≦A,B<N)を入力として受けてm+2 (ここで、m=n/2)クロック内にA・B・R-1modN(ここで、R=4m+2)を計算するためのものであり、図１に示すような装置によりその計算動作が行われる。
【００４５】
まず、図１に示す装置により A・B・R-1modN(ここで、R=4m+2)を計算する過程が説明される。下記のａ)段階は初期化段階であり、ｂ)〜ｈ)段階は毎クロックごとに行われる段階であり、ｉ)段階は、前記ｂ)〜ｈ)段階を(m+2)クロックを行った後に行われる段階である。
【００４６】
ａ)モジュラー乗算のために入力されるｎビットのＡ、Ｂ、Ｎがそれぞれのレジスタ(あるいはメモリ)に貯蔵される。本発明の装置によれば、入力Ａ、Ｂは、図２に示すレジスタ１０２、１０４に格納されるものとして示しており、Ｎを格納する別途のレジスタは示していないが、このようなレジスタが使用され得るという事実に留意すべきである。この時、Ａを格納するためのレジスタ１０２は毎クロックごとに右に２ビット単位に移動させるシフトレジスタである。便宜上、Ａを格納するためのレジスタはレジスタＡ、Ｂを格納するためのレジスタはレジスタＢで説明される。仮に、メモリである場合には１ワード単位に値を読み出す。図１のＣＳＡ２ １５０による計算結果を臨時的に格納するための臨時レジスタ(あるいはメモリ)ＣとＳ(図示せず)が０に初期化される。
【００４７】
ｂ)それぞれのレジスタら１０２、１０４に全てのデータらが入力された時、記録ロジック１１０のブース記録回路１１２はレジスタ１０２のＬＳＢ ２ビットを基盤にブース記録機能を行う。前記記録ロジック１１０のＭＵＸ１１４はレジスタ１０４に格納されたＢ値を入力し、レジスタ１０２のＬＳＢ ２ビットに基づいて0, ±B, ±2B値のうち一つを生成してＣＳＡ１ １２０の３個の入力のうち一つの入力として提供する。この時、前記記録ロジック１１０の１の補数化器１１６はレジスタ１０２のＬＳＢ ２ビットに基づいて0, ±B, ±2B値のうち一つの値を１の補数に変えた後、n+4ビット数で示してＣＳＡ１ １２０の３個の入力のうち一つの入力として提供される。
【００４８】
ｃ)ＣＳＡ１ １２０はn+4ビットの符号付き二進数(binary signed number)３個を入力として受けて加算動作を行う。前記ＣＳＡ１ １２０はn+4個の全加算器１２１〜１２５から構成される。この時、以前段階の全加算器から発生される桁上げは次の段階の全加算器に提供されるが、ＭＳＢの全加算器１２５から発生される桁上げは無視される。
【００４９】
ｄ)商ロジック１３０は、前記ＣＳＡ１ １２０の出力値S1,1, C1,0, S1,0 と、全加算器１６０から提供されるCarry-in信号と、被乗数Ｂの符号ビット(B sign)を入力し、全加算器１３４と排他的論理和器１３６によりそれぞれS1 、S0を計算して出力する。この時、前記全加算器１３４及び排他的論理和器１３６には一種の補正用桁上げ信号であるcinが入力される。この桁上げ信号cinは、２の補数を使用する既存のブース記録方式と違い本発明では１の補数を使用することによる両者の差を補正するための信号である。
【００５０】
ｅ)前記商ロジック１３０の組合回路１３８は、前記ｄ)段階で計算されたS1 ,S0を入力し、前記<表４>に示すような真理値表に基づいて３ビット値であるq値を決定する。たとえ前記<表４>に示した真理値表に基づいてq値を決定する回路に対する具体的な構成を示してはいないが、当該分野で通常の知識を持つ者ならこのような結果値を決定する回路を一般の論理組合回路により容易に具現できるわけである。
【００５１】
ｆ)ＣＳＡ２ １５０は、前記ｃ)段階で求めたＣＳＡ１ １２０の出力である桁上げ値と和値、前記ｅ)段階で求めたq値のＬＳＢ ２ビットに基づいて決定された0、±N、±2N値のうち一つの値を選択してn+4ビットの符号付き二陣数(binary signed number)を入力としてn+4ビット符号付き演算を行う。前記ＣＳＡ２ １５０は前記ＣＳＡ１ １２０と同様に、n+4個の全加算器１５１〜１５６から構成される。この時、前記全加算器１５１〜１５６は最下位の全加算器であるＬＳＢの全加算器１５１の桁上げ入力として前記ｅ)段階で計算されたq値のＭＳＢ値が入力される。
【００５２】
ｇ)全加算器１６０は、ＣＳＡ２ １５０の出力値のうちS2,1 ,C2,0 ビットと補正用桁上げ信号であるcinビットを入力し全加算してCarry-inビットを出力する。このような全加算動作は前述したように、２の補数を使用する既存のブース記録方式と違い本発明では１の補数を使用することによる両者の差を補正するためのものである。
【００５３】
ｈ)前記ＣＳＡ２ １５０の出力のうちＭＳＢからの(n+2)個の和値と(n+3)個の桁上げ値がＣＳＡ１ １２０の入力としてフィードバックされる。この時、前記ＣＳＡ２ １５０の最上位加算器１５６から出力される和値のＭＳＢであるS2,n+3を複写して前に２ビットを追加し、桁上げ値のＭＳＢであるC2,n+3を複写して１ビット追加してＣＳＡ１ １２０の入力値とする。すなわち、前記ＣＳＡ２ １５０の加算器１５６から出力される和値S2,n+3はＣＳＡ１ １２０の最上位から３個の加算器１２３〜１２５に提供され、桁上げ値C2,n+3はＣＳＡ１ １２０の最上位から２個の加算器１２４、１２５に提供される。
【００５４】
ｉ)(m+2)クロック中に前記ｂ)〜ｈ)段階が行われた後には次のような動作が行われる。すなわち、ＣＰＡ(Carry Propagation Adder)(図示せず)は、前記ＣＳＡ２ １５０の出力である桁上げ値と和値に対して加算動作を行う。この時、加算結果値が負数ならmodulus Nを足し、正数ならmodulus Nを足さない。
【００５５】
例えば、Ａ、Ｂ、Ｎがそれぞれ下記の式(10)のように１２ビットである時、前記手続きによるモンゴメリーモジュラーロシア演算結果は表３及び表４に示すとおりになる。
【００５６】
【数３】
2004280103.tif 000007
【００５７】
【表３】
2004280103.tif 000008
【００５８】
【表４】
2004280103.tif 000009
【００５９】
次に、前述したような本発明の装置による演算結果値を利用してモジュラー乗算A・BmodNを計算する手続きを説明する。これに対する具体的なハードウェア構成が省略されていることに留意すべきである。
【００６０】
１）あらかじめP =22(n+4)modNを計算する。
２）本発明の装置を利用してC=A・B・2-(n+4)modNを計算する。
３）P・C・2-(n+4)modN = A・BmodNを計算する。
その後、前述したような本発明の装置による演算結果値を利用してＲＳＡ演算に必要なモジュラー累乗memodNを計算する手続きを説明する。
【００６１】
１）指数ｅをレジスタ(あるいはメモリ)に格納する。
２）レジスタＣにmodulus Nを格納する。
３）臨時レジスタＣとＳを０に初期化する。
４）モンゴメリーモジュラー乗算m’=fm(m,P,N)=m・P・R-1modNを行う。但し、累乗演算の基数Ｐは上の手続きで定義したあらかじめ計算された値を表し、R=２ｎ＋４である。
５）m’をレジスタＢにローディングする。
６）レジスタＢにローディングした値を利用してモジュラー自乗演算を行う。この時、モンゴメリーモジュラー乗算に必要な乗数ＡはレジスタＢからローディングし、変形されたブース記録回路を利用して値を得る。
７）指数ｅを左にシフトする。
８）指数ｅのＭＳＢ(Most Significant Bit)１を無視し、次のビットから次の９)〜１０)段階を行う。
９）指数ｅの毎ビットが０または１に関らず段階４)〜５)を行いモジュラー自乗演算を行う。この時、自乗演算に必要な乗数はレジスタＡ、被乗数はレジスタＢに格納される。
１０)指数ｅの現在ビットが１の場合には段階９)を行った後、段階４)〜５)を行いモジュラー乗算を行う。この時、被乗数はレジスタＢの内容であり、乗数は累乗演算の基数m'である。
１１)指数ｅの全てのビットに対して段階８)〜１０)を行った後、段階４)を利用してモジュラー乗算をもう一度行う。この時、被乗数はレジスタＢの内容であり、乗数は１である。
【００６２】
前記段階１)〜１１)を行った後、レジスタＣとＳに残っている値に対してＣＰＡ(Carry Propagation Adder)を行った値が負数ならmodulus Nを足し、正数ならmodulus Nを足さない値が最終的な累乗値memodNとなる。
【００６３】
Ｂ−４．発明の効果
前述した如く、本発明は、A・B・2-(n+4)modNを計算する回路を記述したものであり、記述された回路を利用して上述した一般のモジュラー乗算であるA・BmodNを計算できる。このような本発明に基づいて計算されたA・BmodNは、デジタル署名を生成及び検証するための機器に使用されるハードウェア的な装置に使用することができる。また、本発明は、ＩＣカードに基づく電子署名、認証、暗／復号化のハードウェア装置に使用することができる。また、本発明は、モジュラー乗算を行う電子署名機器によって暗号及び復号化する機器を提供することができる。また、本発明は、電子署名機器に基づいて、NIST-DSS、ＲＳＡ、ElGamal、Schnorr電子署名など既存の公開キー暗号システムを具現する上で利用することができる。
【００６４】
Ｃ．第２実施例
Ｃ−１．発明の構成
図７は本発明の第２実施例に係るモジュラー乗算装置の構成を示す図である。
図７を参照すれば、前記モジュラー乗算装置は、記録ロジック(Recording Logic)２１０、第１桁上げ保存加算器(Carrier save Adder；以下“ＣＳＡ”と称する)２２０、商ロジック(Quotient Logic)２３０、選択器２４０、第２ＣＳＡ２５０、論理積算器(ＡＮＤ)２６０から構成される。前記モジュラー乗算装置は、モンゴメリーアルゴリズムに基づいてそれぞれｎビットのＡ、Ｂ、Ｎ(ここで、-N≦A,B<N)を入力として受けてm+2(ここで、m=n/2)クロック内にA・B・R-1modN(ここで、R=4m+2)を計算するモジュラー乗算装置に対するハードウェア的な構成である。つまり、このモジュラー乗算装置はA・B・2-(n+4)modNを計算するための構成を持つ。
【００６５】
前記ＣＳＡ２２０、２５０はそれぞれ(n+4)個の全加算器が並列に構成されるものであり、３ビット入力でそれぞれ桁上げビットと和ビットを出力する。前記記録ロジック２１０は、乗数Ａを基盤にして変形されたブース記録(modified Booth recoding)動作を行い、(n+3)ビットの0、B、2B、3B値の中で一つを選択出力する。前記商ロジック２３０は、前記ＣＳＡ１ ２２０の最下位(ＬＳＢ:Least Significant Bit)桁上げ値C1,0、和ＬＳＢ ２ビットS1,1、S1,0とCarry-in、Ｂの符号ビットを入力とし、モジュラー減少(Modular reduction)の倍数を決定するための値である２ビットのq2q1を出力する。前記選択器２４０は、前記決定されたq値に基づいて0、N、2N、3Nの中で一つの値を選択して出力するためのものであり、多重化器(ＭＵＸ：Multiplexer)で具現可能である。前記論理積演算器２６０は、前記ＣＳＡ２ ２５０の出力２ビットであるS2,1、C2,0を入力して論理積演算動作を行い、その演算結果値を桁上がり(Carry-in)信号として前記商ロジック２３０に提供する。
【００６６】
図７には示さなかったが、毎クロックごとに前記ＣＳＡ２ ２５０の出力である桁上げ値と和値をそれぞれ格納するための臨時格納レジスタ(Ｃ)、レジスタ(Ｒ)が備えられ、また、前記臨時格納レジスタら(Ｃ、Ｒ)に格納された値を加算してモジュラー乗算結果として出力するための桁上げ伝播加算器 (Carry Propagation Adder)が具備されるという事実に留意する必要がある。
【００６７】
図８は、図７に示す記録ロジック２１０のより具体的な構成を示す図である。
図８に示すように、前記記録ロジック２１０は、乗数(Ａ)のビットが順次的にシフトされて生成されたビット列の下位２ビットをブース記録(Booth recording)し、前記ブース記録された結果と被乗数(Ｂ)を多重化して(n+3)ビットの二進数を出力する。すなわち、前記記録ロジック２１０の前段には前記乗数のビットを順次的にシフトさせて前記シフトされたビット列を生成するシフトレジスタ２０２と、前記被乗数を格納するためのレジスタ２０４が備えられる。前記記録ロジック２１０は、多重化器(ＭＵＸ)２１２から構成される。前記多重化器２１２は、前記生成されたビット列の下位２ビット(ai+1,ai)と前記被乗数を多重化し、多重化結果として0、B、2B、3Bを出力する。前述した前記記録ロジック２１０は乗数Ａを基盤にして変形されたブース記録(modified Booth recoding)を具現した回路であり、(n+3)ビットの0、B、2B、3B値のうち一つを選択して出力する。
【００６８】
図９は、図７に示すＣＳＡ１ ２２０のより具体的な構成を示す図である。
図９を参照すれば、前記ＣＳＡ１ ２２０は、(n+4)個の全加算器２２１〜２２５を備えており、(n+1)ビットの第１信号(S2,2 〜S2,n+2)と、(n+2)ビットの第２信号(C2,1〜C2,n+2)と、前記記録ロジック２１０からの(n+3)ビットの前記二進数を第３信号(B0〜Bn+2)として入力し、前記(n+3)個の全加算器２２１〜２２５により全加算して(n+3)ビットの桁上げ値(C1,0〜C1,n+2)と和値(S1,0〜S1,n+2)を出力する。前記第１信号及び第２信号は、前記ＣＳＡ２ ２５０から提供される信号であり、第３信号は、前記記録ロジック２１０から提供される信号である。この時、前記第１信号の最上位ビットS2,n+2は、前記全加算器のうち上位３番目の全加算器２２３に入力され、前記第２信号の最上位ビットC2,n+2は前記全加算器のうち上位２番目の全加算器２２４に入力される。前記全加算器のうち最上位全加算器２２５には第１信号及び第２信号として“０”が提供され、２番目の全加算器２２４には第１信号として“０”が提供される。すなわち、前記ＣＳＡ１ ２２０を構成する最下位の全加算器２２１から(n+1)番目の全加算器２２３まで(n+1)ビットの第１信号Ｓが順次入力され、(n+2)番目の全加算器２２４及び(n+3)番目の全加算器２２５には“０”の第１信号が入力される。また、前記ＣＳＡ１ ２２０を構成する最下位の全加算器２２１から(n+2)番目の全加算器２２４まで(n+2)ビットの第２信号(C2,1〜C2,n+2)が順次入力され、(n+3)番目の全加算器２２５には“０”の第２信号が入力される。また、前記ＣＳＡ１ ２２０を構成する最下位の全加算器２２１から(n+1)番目の全加算器２２３まで(n+3)ビットの第３信号(B0〜Bn+2)が順次入力される。
【００６９】
図１０は、図７に示す商ロジック２３０のより具体的な構成を示す図である。
図１０を参照すれば、前記商ロジック２３０は、前記ＣＳＡ１ ２２０からの前記(n+3)ビットの桁上げ値と和値の中から選択された下位２個の全加算器から出力される和値(S1,0、S1,1)と下位１個の全加算器から出力される桁上げ値(C1,0)を入力し、モジュラー減少の倍数を決定するための２ビットの決定値q1q0を出力する。前記商ロジック２３０は、ディー(D)フリップフロップ２３２と、半加算器(ＨＡ：Half Adder)２３４と、排他的論理和(XOR)器２３６と、組合回路２３８から構成される。前記Ｄフリップフロップ２３２は論理積(ＡＮＤ)演算器２６０から桁上げ入力値Carry-inを入力して一時的に格納する。前記半加算器２３４は、前記Ｄフリップフロップ２３２に格納された桁上げ入力値Carry-inと前記ＣＳＡ１ ２２０の最下位全加算器２２１から出力される和値(S1,0)を半全加算する。前記排他的論理和器２３６は、前記ＣＳＡ１ ２２０の最下位全加算器２２１から出力される桁上げ値(C1,0)と２番目の全加算器２２２から出力される和値(S1,1)を排他的論理和する。前記組合回路２３８は、前記半加算器２３４の出力(SO)と前記排他的論理和器２３６の出力(S1)とあらかじめ設定された入力ビット(n1)を組合わせて２ビットの決定値(q1q0)として出力する。
【００７０】
図１１は、図７に示すＣＳＡ２ ２５０のより具体的な構成を示す図である。
図１１を参照すれば、前記ＣＳＡ２ ２５０は、(n+3)個の全加算器２５１〜２５６を備えている。前記ＣＳＡ２ ２５０は前記選択器２４０から選択された(n+3)ビットのモジュロ数N(N0 - Nn+2)を第１信号として入力し、前記ＣＳＡ１ ２２０からの(n+3)ビットの桁上げ値のうち最上位桁上げ値を除外した残りの(n+2)ビットの桁上げ値(C1,0〜C1,n+2)を第２信号として入力し、前記(n+3)ビットの和値の中で最下位桁上げ値を除外した残りの(n+2)ビットの和値(S1,1〜S1,n+2)を第３信号として入力し、前記(n+3)個の全加算器２５１〜２５６により(n+3)ビットの桁上げ値(C2,0〜C2,n+2)と和値(S2,0〜S2,n+2)を出力する。この時、前記第１信号の(n+3)ビットは前記全加算器の最下位全加算器２５１から順次入力され、前記第２信号の(n+2)ビットは前記全加算器のうち下位２番目の全加算器２５２から順次入力され、前記第３信号の(n+2)ビットは前記全加算器の下位２番目の全加算器２５２から順次入力される。前記全加算器のうち最下位全加算器２５１には前記商ロジック２３０の半加算器２３４からの出力(S0)と、論理積(ＡＮＤ)演算器２６０からの桁上げ入力値Carry-inが入力される。
【００７１】
図１２は、図７に示す論理積演算器２６０のより具体的な構成を示す図である。
図１２を参照すれば、前記論理積演算器２６０は、前記ＣＳＡ２ ２５０の最下位全加算器２５１から出力される桁上げ値(C2,0)と下位２番目の全加算器２５２から出力される和値(S2,1)を全加算して桁上げ入力値(Carry-in)として出力する。この桁上げ入力値(Carry-in)は前記商ロジック２３０に提供される。
【００７２】
Ｃ−２．発明の原理
本発明は、それぞれｎビットのＡ、Ｂ、Ｎ(ここで、-N≦A,B<N)を入力として受けてm+2(ここで、m=n/2)クロック内にA・B・R-1modN (ここで、R=4m+2)を計算する装置に関するものである。このような本発明の具現に適用される次の２つの原理が説明される。第一に、モジュラー乗算のための乗数(Ａ)及び被乗数(Ｂ)を表現する原理が説明される。第二に、本発明の記録原理を利用したモンゴメリーアルゴリズムに対する原理が説明される。
【００７３】
<2bit scanning>
本発明では乗数(Ａ)を各クロックにＬＳＢから２ビットずつスキャニング(scanning)(あるいはシフティング(shifting))して被乗数(Ｂ)とかけ、このような乗算結果をモンゴメリーアルゴリズムに利用する。したがって、毎ループから発生するaiは{0、1、2、3}の元素の中で一つであり、これを被乗数(Ｂ)とかけてＣＳＡ１ ２２０の入力として利用する。
【００７４】
<Radix-4 Montgomery algorithm>
下記の式(11)〜（17）に示すようなアルゴリズムは、本発明がradix-4モンゴメリーモジュラー乗算を利用することを示す。元来モンゴメリーアルゴリズムでは結果値とmodulus Nと比較し、結果値がmodulus Nより大きいと一度減算をしなければならないが、下記に示すアルゴリズムではその手続きがないことがわかる。
【００７５】
【数４】
2004280103.tif 000010
【００７６】
上記の式(11)〜(17)に示したアルゴリズムで、(13)手続きのAiは、Ａを２ビットずつスキャンした値を意味する。(14)手続きは、(15)手続きの結果値のＬＳＢ(Least Significant Bit)２ビットが‘０’になるようにする関数を意味する。前記(4)手続きでの結果値は入力ビットs1, s0, n1,n0に依存するが、モンゴメリーモジュラー乗算のためにはＮが奇数なのでこの時n0は常に１であり、したがって、実際に下記の表５に示すように決定される。モジュラー減少(modular reduction)に使用される値qiは集合{0、1、2、3}元素のうち一つである。qiは下記の式(18)によって計算される。
【００７７】
【数５】
2004280103.tif 000011
【００７８】
【表５】
2004280103.tif 000012
【００７９】
Ｃ−３．発明の動作
本発明はそれぞれｎビットのＡ、Ｂ、Ｎ(ここで、-N≦A,B<N)を入力として受けてm+2 (ここで、m=n/2)クロック内にA・B・R-1modN(ここで、R=4m+2)を計算するためのものであり、図７に示すような装置によりその計算動作が行われる。
【００８０】
まず、図７に示す装置により A・B・R-1modN(ここで、R=4m+2)を計算する過程が説明される。下記のａ)段階は初期化段階であり、ｂ)〜ｈ)段階は毎クロックごとに行われる段階であり、ｉ)段階は、前記ｂ)〜ｈ)段階を(m+2)クロックを行った後に行われる段階である。
【００８１】
ａ)モジュラー乗算のために入力されるｎビットのＡ、Ｂ、Ｎがそれぞれのレジスタ(あるいは、メモリ)に貯蔵される。また、n+2ビットの２Ｂ、３Ｂがそれぞれのレジスタ(あるいは、メモリ)に貯蔵される。本発明の装置によれば、入力されるビットＡ、Ｂは、図８に示すレジスタ２０２、２０４に格納されるものとして示しているし、２Ｂ及び３Ｂを格納する別途のレジスタは示してはいないが、このようなレジスタが使用可能であるという事実に留意すべきである。この時、Ａを格納するためのレジスタ２０２は毎クロックごとに右に２ビット単位に移動させるシフトレジスタである。便宜上、Ａを格納するためのレジスタはレジスタＡ、Ｂを格納するためのレジスタはレジスタＢで説明される。仮に、メモリである場合には１ワード単位に値を読み出す。図７のＣＳＡ２ ２５０による計算結果を臨時的に格納するための臨時レジスタ(あるいは、メモリ)ＣとＳ(図示せず)が０に初期化される。
【００８２】
ｂ)それぞれのレジスタら２０２、２０４に全てのデータらが入力された時、記録ロジック２１０ではレジスタ２０２のＬＳＢ ２ビットを基盤にブース記録機能を行う。前記記録ロジック２１０のＭＵＸ２１２はＢレジスタ２０４の値を入力し、Ａレジスタ２０２のＬＳＢ ２ビットに基づいて0, B, 2B，3B値のうち一つを選択してＣＳＡ１ ２２０の３個の入力のうち一つの入力として提供する。
【００８３】
ｃ)ＣＳＡ１ ２２０はn+3ビットの二進数(binary unsigned number)３個を入力として受けて加算動作を行う。前記ＣＳＡ１ ２２０はn+3個の全加算器２２１〜２２５から構成される。
【００８４】
ｄ)商ロジック２３０は、前記ＣＳＡ１ ２２０の出力値S1,1, C1,0, S1,0 と、論理積演算器２６０から提供されるCarry-in信号を入力し、半加算器２３４と排他的論理和器２３６によりそれぞれS1 、S0を計算して出力する。
【００８５】
ｅ)前記商ロジック２３０の組合回路２３８は、前記ｄ)段階で計算されたS1 ,S0を入力し、前記表５に示すような真理値表に基づいて２ビット値であるq値を決定する。たとえ前記表５に示した真理値表に基づいてq値を決定する回路に対する具体的な構成を示してはいないが、当該分野で通常の知識を持つ者ならこのような結果値を決定する回路を一般の論理組合回路により容易に具現できるわけである。
【００８６】
ｆ)ＣＳＡ２ ２５０は、前記ｃ)段階で求めたＣＳＡ１ ２２０の出力である桁上げ値と和値、前記ｅ)段階で求めたq値のＬＳＢ ２ビットに基づいて決定された0、N、2N、3N値のうち一つの値を選択してn+4ビットの二陣数を入力としてn+3ビット符号なし演算を行う。前記ＣＳＡ２ ２５０は前記ＣＳＡ１ ２２０と同様に、n+3個の全加算器２５１〜２５６から構成される。この時、前記全加算器２５１〜２５６は最下位の全加算器であるＬＳＢの全加算器２５１の桁上げ入力として前段のCarry-in信号が入力されることに留意すべきである。
【００８７】
ｇ)論理積演算器２６０は、ＣＳＡ２ ２５０の出力値のうちS2,1 ,C2,0 ビットを入力し論理積演算してCarry-inビットを出力する。
【００８８】
ｈ)前記ＣＳＡ２ ２５０の出力のうちＭＳＢからの(n+1)個の和値と(n+2)個の桁上げ値がＣＳＡ１ ２２０の入力としてフィードバックされる。この時、前記ＣＳＡ２ １５０の和値の上位２ビットと桁上げ値の上位１ビットには“０”入力し、２ビットが右にシフトされることによってＣＳＡ１ ２２０にフィードバックされる。すなわち、前記ＣＳＡ２ ２５０の加算器２５６から出力される和値S2,n+2はＣＳＡ１ ２２０の上位３番目の加算器２２３に提供され、最上位及び上位２番目の加算器２２４、２２５には“０”の和値が提供される。前記ＣＳＡ２ ２５０の加算器２５６から出力される桁上げ値C2,n+2はＣＳＡ１ ２２０の上位２番目の加算器２２４に提供され、最上位加算器２２５には“０”の桁上げ値が提供される。
【００８９】
ｉ)(m+2)クロック中に前記ｂ)〜ｈ)段階が行われた後には次のような動作が行われる。すなわち、ＣＰＡ(Carry Propagation Adder)(図示せず)は、前記ＣＳＡ２ ２５０の出力である桁上げ値と和値に対して加算動作を行う。
【００９０】
例えば、Ａ、Ｂ、Ｎがそれぞれ下記の式(19)のように１２ビットである時、前記手続きによるモンゴメリーモジュラーロシア演算結果は表６及び表７に示すとおりになる。
FinalResult:0111.1100.0111(0x7C7)+0010.1000.0000(0x280)+1=1010.0100.1000(0xA448)
【００９１】
【数６】
2004280103.tif 000013
【００９２】
【表６】
2004280103.tif 000014
【００９３】
【表７】
2004280103.tif 000015
【００９４】
次に、前述したような本発明の装置による演算結果値を利用してモジュラー乗算A・BmodNを計算する手続きを説明する。これに対する具体的なハードウェア構成が省略されていることに留意すべきである。
【００９５】
１）あらかじめP =22(n+4)modNを計算する。
２）本発明の装置を利用してC=A・B・2-(n+4)modNを計算する。
３）P・C・2-(n+4)modN = A・BmodNを計算する。
【００９６】
その後、前述したような本発明の装置による演算結果値を利用してＲＳＡ演算に必要なモジュラー累乗memodNを計算する手続きを説明する。
１）指数ｅをレジスタ(あるいはメモリ)に格納する。
２）レジスタＣにmodulus Nを格納する。
３）臨時レジスタＣとＳを０に初期化する。
４）モンゴメリーモジュラー乗算m’=fm(m,P,N)= m・P・R-1modNを行う。但し、累乗演算の基数Ｐは上の手続きで定義したあらかじめ計算された値を表し、R=２ｎ＋４である。
５）m’をレジスタＢにローディングする。
６）レジスタＢにローディングした値を利用してモジュラー自乗演算を行う。この時、モンゴメリーモジュラー乗算に必要な乗数ＡはレジスタＢからローディングし、radix-4 Recoding回路を利用して値を得る。
【００９７】
７）指数ｅを左にシフトする。
８）指数ｅのＭＳＢ(Most Significant Bit)１を無視し、次のビットから次の９)〜１０)段階を行う。
９）指数ｅの毎ビットが０または１に関らず段階４)〜５)を行いモジュラー自乗演算を行う。この時、自乗演算に必要な乗数はレジスタＡ、被乗数はレジスタＢに格納される。
１０)指数ｅの現在ビットが１の場合には段階９)を行った後、段階４)〜５)を行いモジュラー乗算を行う。この時、被乗数はレジスタＢの内容であり、乗数は累乗演算の基数m'である。
１１)指数ｅの全てのビットに対して段階８)〜１０)を行った後、段階４)を利用してモジュラー乗算をもう一度行う。この時、被乗数はレジスタＢの内容であり、乗数は１である。
前記段階１)〜１１)を行った後、レジスタＣとＳに残っている値に対してＣＰＡ(Carry Propagation Adder)を行った値が最終的な累乗値memodNとなる。
【００９８】
Ｃ−４．発明の効果
前述した如く、本発明は、A・B・2-(n+4)modNを計算する回路を記述したものであり、記述された回路を利用して上述した一般のモジュラー乗算であるA・BmodNを計算できる。このような本発明に基づいて計算されたA・BmodNは、デジタル署名を生成及び検証するための機器に使用されるハードウェア的な装置に使用することができる。また、本発明は、ＩＣカードに基づく電子署名、認証、暗／復号化のハードウェア装置に使用することができる。また、本発明は、モジュラー乗算を行う電子署名機器によって暗号及び復号化する機器を提供することができる。また、本発明は、電子署名機器に基づいて、NIST-DSS、ＲＳＡ、ElGamal、Schnorr電子署名など既存の公開キー暗号システムを具現する上で利用することができる。
【００９９】
Ｄ．発明の適用例
図１３は、本発明で具現した暗号補助装置を利用して暗号化及び電子署名ができるＩＣカードのブロック構成を表す図面である。
図１３において、中央処理処置(ＣＰＵ:Central Processing Unit)３１０は、暗号、認証及び電子署名を可能にする命令語を解読し、モジュラー演算プロセッサー(modular arithmetic coprocessor)３３０に必要な制御信号とデータを提供する。ＲＯＭ(Read Only Memory)３５０の内部には暗号化及び電子署名などに必要なキー(key)のように保護しなければならないデータのための保安モジュラー(security module)が存在する。
【０１００】
一方、本発明の詳細な説明では具体的な実施例に上げて説明したが、本発明の範囲を外れない限度内で様々な変形が可能であることはもちろんである。したがって、本発明の範囲は、説明された実施例によって定められてはいけなく、特許請求の範囲及び請求範囲と均等なものによって定められるべきである。
【図面の簡単な説明】
【０１０１】
【図１】本発明の第１実施例に係るモジュラー乗算装置の構成を示す図。
【図２】図１に示す記録ロジックのより具体的な構成を示す図。
【図３】図１に示す桁上げ保存加算器(ＣＳＡ)１のより具体的な構成を示す図。
【図４】図１に示す商ロジックのより具体的な構成を示す図。
【図５】図１に示すＣＳＡ２のより具体的な構成を示す図。
【図６】図１に示す全加算器(ＦＡ)のより具体的な構成を示す図。
【図７】本発明の第２実施例に係るモジュラー乗算装置の構成を示す図。
【図８】図７に示す記録ロジックのより具体的な構成を示す図。
【図９】図７に示すＣＳＡ１のより具体的な構成を示す図。
【図１０】図７に示す商ロジックのより具体的な構成を示す図。
【図１１】図７に示すＣＳＡ２のより具体的な構成を示す図。
【図１２】図７に示すＦＡのより具体的な構成を示す図。
【図１３】本発明の実施例に係るモジュラー乗算装置の適用例を示す図。
【符号の説明】
【０１０２】
１０２    シフトレジスタ
１０４    レジスタ
１１０    記録ロジック
１１２    記録回路
１１４    多重化器（ＭＵＸ）
１１６    補数化器
１２０    第１桁上げ保存加算器（ＣＳＡ）
１３０    商ロジック
１４０    選択器
１５０    第２ＣＳＡ
１６０    全加算器
【図１】
2004280103.tif 000016
【図２】
2004280103.tif 000017
【図３】
2004280103.tif 000018
【図４】
2004280103.tif 000019
【図５】
2004280103.tif 000020
【図６】
2004280103.tif 000021
【図７】
2004280103.tif 000022
【図８】
2004280103.tif 000023
【図９】
2004280103.tif 000024
【図１０】
2004280103.tif 000025
【図１１】
2004280103.tif 000026
【図１２】
2004280103.tif 000027
【図１３】
2004280103.tif 000028