(57)【特許請求の範囲】
【請求項１】
演算装置による冪乗演算で使用可能な記憶装置の記憶容量が予め決められている暗号化システムにおける、固定要素ｇとランダムに選択されたｎビット指数Ｒに対して羃乗演算ｇRを計算するための羃乗演算を含む暗号化方法において、
前記羃乗演算が、
（ａ）使用される記憶容量が前記使用可能な記憶装置の記憶容量を越えないよう選択され、更に前記演算装置での演算回数が少なくなるよう決定された、一次元の分割数ｈとビット数ａ及び二次元の分割数ｖとビット数ｂを使用して、
前記指数Ｒのビット列をビット数ａの所定数ｈのブロックに分割し、前記分割された各ブロックのビット列をビット数ｂの所定数ｖの副ブロックに分割し（ここで、ａは分数値ｎ／ｈより大きい最小整数、ｂは分数値ａ／ｖより大きい最小整数）、前記指数Ｒのビット列をｖ列およびｈ行からなるｈ×ｖの二次元配列に分割する指数分割過程と、
（ｂ）０より大きく２hより小さい全ての整数ｆ（ここで、ｆは二進数でｅh-1 ，ｅh-2 …ｅ1，ｅ0の形態で表わされる）、および０と同じか大きくｖより小さい全ての整数ｊに対して、次の値を整数ｆ，ｊを順次変化させながら計算して、整数ｆ，ｊに対応して読み出し可能に前記記憶装置に記憶する過程と、
【数１】
0003540852.tif 000044
ａは各ブロックに含まれるビット数、ｂは各副ブロックに含まれるビット数、
（ｃ）前記記憶された計算値を、整数ｆと整数ｊに相当するＩj,kに対応して前記記憶装置から順次読み出しながら、次式によりｇR を計算する過程と、
【数２】
0003540852.tif 000045
ここで、Ｉj,kは、ｊ番目の副ブロックに該当するビット列でｋ番目に位置するビットの、ｉが０からｈ−１までの全てのブロックに亙るｈビットの大きさのビット列からなる値、
を含むことを特徴とする暗号化システムにおける羃乗演算を含む暗号化方法。
【請求項２】
前記（ａ）過程では、前記副ブロック内に含まれるビットの数がほぼ同一になるように分割することを特徴とする請求項１記載の暗号化システムにおける羃乗演算を含む暗号化方法。
【請求項３】
前記（ａ）過程では、前記副ブロック内に含まれるビットの数が相異なるように分割することを特徴とする請求項１記載の暗号化システムにおける羃乗演算を含む暗号化方法。
【請求項４】
前記（ｃ）過程では、ｖが２つの整数ｐとｗの積（ｖ＝ｐｗ）で表わされる場合に、ｐ個のプロセッサを備え、ｉ（ｉ＝０，…，ｐ−１）番目のプロセッサが次式による演算を遂行して、
【数３】
0003540852.tif 000046
並列処理することを特徴とする請求項１記載の暗号化システムにおける羃乗演算を含む暗号化方法。
【請求項５】
演算装置による冪乗演算で使用可能な記憶装置の記憶容量が予め決められている暗号化システムにおける、固定要素ｇとランダムに選択されたｎビット指数Ｒに対して羃乗演算ｇR を計算するための羃乗演算部を含む暗号化装置において、
前記羃乗演算部が、
（ａ）使用される記憶容量が前記使用可能な記憶装置の記憶容量を越えないよう選択され、更に前記演算装置での演算回数が少なくなるよう決定された、一次元の分割数ｈとビット数ａ及び二次元の分割数ｖとビット数ｂを使用して、
入力された前記指数Ｒのビット列をビット数ａの所定数ｈのブロックに分割し、前記分割された各ブロックのビット列をビット数ｂの所定数ｖの副ブロックに分割することにより（ここで、ａは分数値ｎ／ｈより大きい最小整数、ｂは分数値ａ／ｖより大きい最小整数）、ｖ列およびｈ行からなるｈ×ｖの二次元配列とする指数分割手段と、
（ｂ）各副ブロックに含まれるビットの数をｂとした場合に、０より大きく２hより小さい全ての整数ｆ（ここで、ｆは二進数でｅh-1 ，ｅh-2 …ｅ1 ，ｅ0 の形態で表わされる）、および０と同じか大きくｖより小さい全ての整数ｊに対して、次の値を整数ｆ，ｊを順次変化させながら計算する事前計算手段と、
【数４】
0003540852.tif 000047
ａは各ブロックに含まれるビット数、ｂは各副ブロックに含まれるビット数、
（ｃ）前記事前計算手段で計算された値を、整数ｆ，ｊに対応して読み出し可能に前記記憶装置に記憶する記憶手段と、
（ｄ）前記記憶された計算値を利用して、整数ｆと整数ｊに相当するＩj,kに対応して前記記憶装置から順次読み出しながら、次式によりｇR を計算する羃乗計算手段と、
【数５】
0003540852.tif 000048
ここで、Ｉj,k は、ｊ番目の副ブロックに該当するビット列でｋ番目に位置するビットの、ｉが０からｈ−１までの全てのブロックに亙るｈビットの大きさのビット列からなる値、
を含むことを特徴とする暗号化システムにおける羃乗演算部を含む暗号化装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、暗号化システムにおいて、要求される固定した基本要素を基とするモジュラ羃乗演算をより速く遂行するための羃乗演算を含む暗号化方法及びその装置に係り、特に固定した基本要素に依存する事前計算テーブルを利用した羃乗演算を含む暗号化方法及びその装置に関する。
【０００２】
【従来の技術】
１９７６年に Diffie と Hellmanとにより初めて公開鍵暗号システムの概念が紹介されて以来、大部分の暗号プロトコルが公開鍵暗号方式に基づいて開発されてきた。公開鍵暗号システムは、数学的に非常に難しい問題の一方向性を利用して公開鍵と秘密鍵とを計算することにより、公開鍵が知られてもここから秘密鍵を導くのが計算上不可能である事実を利用している。
【０００３】
数学的に難しい問題の代表的な例が、有限グループでの離散的対数問題と合成数を素因数分解する問題とである。ところが、このような問題に基づいて設計された暗号システムは、適法な使用者にとっても、従来の暗号システムに比べて計算量が多くて速度が遅いという短所を有する。したがって、計算量を減らすためのアルゴリズムの開発が重要な研究分野となっている。
【０００４】
公開鍵暗号システムで要求される最も一般的な演算が、有限グループ（代表的に多く使用されるグループとしては、整数リングや有限体（Finite Field）上の掛け算群、有限体上で定義された楕円曲線上の足し算群などがある）での羃乗演算である。一般的に、羃乗演算とはグループのランダムな２つの要素ＸとＲとに対してＸR を計算することを言う。多くの暗号プロトコルでグループの固定した基本要素ｇを基にランダムな指数Ｒに対して羃乗ｇR を計算するのが必要である。その例として、離散的対数問題の難しさを利用する大部分のプロトコル、特に最も基本的な暗号プロトコルに属する識別およびディジタル署名方式がある。
【０００５】
与えられたグループ（普通ＺN 、ここで、Ｎは大きい素数又は２つの大きい素数の積）での速い羃乗演算の問題は、大部分の公開鍵暗号化システムの効率的な遂行に非常に重要である。以下では、便宜上計算がＺN に対して遂行されると仮定し、したがって掛け算は“multiplication mod Ｎ”を意味する。
以下の説明において、ｇはＺN の固定した要素、Ｒは［０，２n ）でのｎビットランダム指数として使用される。整数Ｓに対するＳのビット長さ又は集合Ｓに対するＳのカージナリティ（cardinality)は｜Ｓ｜で表記される。また、ｘより小さくない最小整数は「ｘ（例えば、「1.29＝２）、ｘより大きくない最大整数はｘ」（例えば、1.29」＝１）で表記される。
【０００６】
典型的な羃乗演算方法は、自乗と掛け算（square-and-multiply)方法として知られる二進アルゴリズムを使用する。５１２ビットの法（modulus)と指数に対して、該方法は平均７６６回の掛け算、最悪の場合に１０２２回の掛け算が必要である。符号二進アルゴリズムは、平均６８２回、最悪の場合でも７６８回にまで必要な掛け算の数を減らすことができる。
【０００７】
一方、中間値のための適度な記憶部を使用すると、その遂行能力をさらに相当向上させることができる。Ｄ．Ｅ．Ｋnuth“The art of computer programming ”，Vol. 2 : Seminumerical algorithms, second Edition, Addison-wesley, 1981 の５ウインドウアルゴリズムは、１６回の掛け算のオンライン事前計算を含めて、平均およそ６０９回の掛け算で羃乗演算ができる。
【０００８】
羃乗演算について知られたもののうち最も速いアルゴリズムは、アディションチェーン（addition chain）に基づくウインドウ方法であり、ここで“１０”のようにさらに大きいウインドウを使用することができるが、中間値のためのさらに多くの記憶部が要求される。最も短いアディションチェーンを捜すのが、ＮＰ完全問題（complete problem）であるが、発見的な解決法を適用して、およそ長さ６０５のアディションチェーンが計算され得ると報告されている。
【０００９】
このような一般的な方法は、ＲＳＡ（すなわち、R.L.Rivest, A.Shamir and L.Adleman “A method for obtaining digital signatures and public-key cryptosystems”, communication ACM, 21(2), 120-126, 1978 ）、およびElGamal （Ｔ．ElGamal “A public key cryptosystem and a signature scheme based on the discrete logarithm”, IEEE Transaction Information Theory 31(4),  469-472, 1985) のように羃乗演算を要求するいずれの暗号化システムにも使用され得る。
【００１０】
【発明が解決しようとする課題】
しかしながら、離散的対数問題に基づく多くの暗号プロトコルにおいては、固定した基数ｇおよびランダムに選択された指数Ｒに対するｇR を計算する必要がある。固定した基本要素により、要求される掛け算の数を減らすために事前計算テ−ブルを使用できるが、勿論事前計算値のための記憶部が必要である。
【００１１】
本発明の目的は、公開鍵暗号システムにおいて、固定した基本要素に依存する事前計算テ−ブルを利用して羃乗演算をより高速に行える羃乗演算を含む暗号化方法及びその装置を提供することである。本発明で提示した方法は、上記いずれのグループにでも適用が可能である。
【００１２】
【課題を解決するための手段】
前記目的を達成するために、本発明による暗号化システムにおける羃乗演算を含む暗号化方法は、演算装置による冪乗演算で使用可能な記憶装置の記憶容量が予め決められている暗号化システムにおける、固定要素ｇとランダムに選択されたｎビット指数Ｒに対して羃乗演算ｇRを計算するための羃乗演算を含む暗号化方法において、
前記羃乗演算が、
（ａ）使用される記憶容量が前記使用可能な記憶装置の記憶容量を越えないよう選択され、更に前記演算装置での演算回数が少なくなるよう決定された、一次元の分割数ｈとビット数ａ及び二次元の分割数ｖとビット数ｂを使用して、
前記指数Ｒのビット列をビット数ａの所定数ｈのブロックに分割し、前記分割された各ブロックのビット列をビット数ｂの所定数ｖの副ブロックに分割し（ここで、ａは分数値ｎ／ｈより大きい最小整数、ｂは分数値ａ／ｖより大きい最小整数）、前記指数Ｒのビット列をｖ列およびｈ行からなるｈ×ｖの二次元配列に分割する指数分割過程と、
（ｂ）０より大きく２hより小さい全ての整数ｆ（ここで、ｆは二進数でｅh-1 ，ｅh-2 …ｅ1，ｅ0の形態で表わされる）、および０と同じか大きくｖより小さい全ての整数ｊに対して、次の値を整数ｆ，ｊを順次変化させながら計算して、整数ｆ，ｊに対応して読み出し可能に前記記憶装置に記憶する過程と、
【００１３】
【数１２】
0003540852.tif 000002
ａは各ブロックに含まれるビット数、ｂは各副ブロックに含まれるビット数、
（ｃ）前記記憶された計算値を、整数ｆと整数ｊに相当するＩj,kに対応して前記記憶装置から順次読み出しながら、次式によりｇR を計算する過程と、
【００１４】
【数１３】
0003540852.tif 000003
ここで、Ｉj,k は、ｊ番目の副ブロックに該当するビット列でｋ番目に位置するビットの、ｉが０からｈ−１までの全てのブロックに亙るｈビットの大きさのビット列からなる値、
を含むことを特徴とする。
【００２４】
ここで、前記（ａ）過程では、前記副ブロック内に含まれるビットの数がほぼ同一になるように分割する。また、前記（ａ）過程では、前記副ブロック内に含まれるビットの数が相異なるように分割する。また、前記（ｃ）過程では、ｖが２つの整数ｐとｗの積（ｖ＝ｐｗ）で表わされる場合に、ｐ個のプロセッサを備え、ｉ（ｉ＝０，…，ｐ−１）番目のプロセッサが次式による演算を遂行して、
【００２５】
【数１８】
0003540852.tif 000004
【００２６】
並列処理する。
【００３０】
又、本発明による暗号化システムにおける羃乗演算部を含む暗号化装置は、演算装置による冪乗演算で使用可能な記憶装置の記憶容量が予め決められている暗号化システムにおける、固定要素ｇとランダムに選択されたｎビット指数Ｒに対して羃乗演算ｇR を計算するための羃乗演算部を含む暗号化装置において、
前記羃乗演算部が、
（ａ）使用される記憶容量が前記使用可能な記憶装置の記憶容量を越えないよう選択され、更に前記演算装置での演算回数が少なくなるよう決定された、一次元の分割数ｈとビット数ａ及び二次元の分割数ｖとビット数ｂを使用して、
入力された前記指数Ｒのビット列をビット数ａの所定数ｈのブロックに分割し、前記分割された各ブロックのビット列をビット数ｂの所定数ｖの副ブロックに分割することにより（ここで、ａは分数値ｎ／ｈより大きい最小整数、ｂは分数値ａ／ｖより大きい最小整数）、ｖ列およびｈ行からなるｈ×ｖの二次元配列とする指数分割手段と、
（ｂ）各副ブロックに含まれるビットの数をｂとした場合に、０より大きく２hより小さい全ての整数ｆ（ここで、ｆは二進数でｅh-1 ，ｅh-2 …ｅ1 ，ｅ0 の形態で表わされる）、および０と同じか大きくｖより小さい全ての整数ｊに対して、次の値を整数ｆ，ｊを順次変化させながら計算する事前計算手段と、
【００３１】
【数２１】
0003540852.tif 000005
ａは各ブロックに含まれるビット数、ｂは各副ブロックに含まれるビット数、
【００３２】
（ｃ）前記事前計算手段で計算された値を、整数ｆ，ｊに対応して読み出し可能に前記記憶装置に記憶する記憶手段と、
（ｄ）前記記憶された計算値を利用して、整数ｆと整数ｊに相当するＩj,kに対応して前記記憶装置から順次読み出しながら、次式によりｇR を計算する羃乗計算手段と、
【００３３】
【数２２】
0003540852.tif 000006
【００３４】
ここで、Ｉj,k は、ｊ番目の副ブロックに該当するビット列でｋ番目に位置するビットの、ｉが０からｈ−１までの全てのブロックに亙るｈビットの大きさのビット列からなる値、
を含むことを特徴とする。
【００３５】
【作用】
かかる構成により、事前計算による速い羃乗演算のための新しい方法が提示されたことにより、非常に簡単でありながらもＢＧＭＷ方法よりもさらに優れた演算性能を達成し得る。
【００３６】
【実施例】
以下、先ず従来のＢＧＭＷ（すなわち、E.F.Brickell, D.M.Gordon, K.S.McCurley and D.Wilson “Fast exponentiation with precomputation”, In Proc. Eurocrypt'92, Balatonfured, Hungary, 1992 ）方法について簡単に調べた後、本発明の実施例を詳細に説明し、更にこれらの方法による遂行能力を図面を利用して比較説明する。
【００３７】
＜ＢＧＭＷ方法＞
先ず、Eurocrypt ′92において、Brickell，Gordon，McCurley，Wilsonにより提案された従来の事前計算方法であるＢＧＭＷ方法を簡単に考察する。
Eurocrypt ′92において、BrickellなどはｇR の計算速度を向上させるための方法を提案した。かれらの基本戦略は、指数Ｒを基数ｂで次のように表現し、全ての羃乗
【００３８】
【数２３】
0003540852.tif 000007
【００３９】
を事前計算する。
Ｒ＝ｄt-1 ｂt-1 ＋…＋ｄ1 ｂ1 ＋ｄ0
但し、０≦ｄi ＜ｂ（０≦ｉ＜ｔ）
すると、ｇR は次の式により計算される。
【００４０】
【数２４】
0003540852.tif 000008
【００４１】
基数ｂに対する基本ディジットセットを使用して、要求される記憶容量が増加する反面、計算時間をさらに減少するように基本技法を拡張させ得る。
ＢＧＭＷ方法をさらに詳細に説明する。
もし、ある整数が集合Ｄからのディジットを使用して基数ｂで表わされるとすると、整数Ｄの集合は基数ｂに対する基本ディジット集合と称される。次の式(1) が基数ｂに対する基本ディジット集合となるように、乗数の集合Ｍおよびパラメータｈが選択できると仮定する。
【００４２】
Ｄ（Ｍ，ｈ）＝｛ｍｋ｜ｍ∈Ｍ，０≦ｋ≦ｈ｝     …(1)
すると、ｎビット指数Ｒは次の式(2) のように表わされる。
【００４３】
【数２５】
0003540852.tif 000009
【００４４】
このようなＲの表現で、ｇR は式(3) により計算される。
【００４５】
【数２６】
0003540852.tif 000010
【００４６】
したがって、もし［全てのｉ＜ｔおよびｍ∈Ｍ］に対して、羃乗
【００４７】
【数２７】
0003540852.tif 000011
【００４８】
を予め計算して記憶すると、ｇR は次のアルゴリズムにより約ｔ｜Ｍ｜の事前計算値を利用して、多くて（ｔ＋ｈ−２）回の掛け算で計算され得る。
【００４９】
【数２８】
0003540852.tif 000012
【００５０】
前記のアルゴリズムにより遂行される掛け算の数は、最悪の場合（ｔ＋ｈ−２）回、ｗ＝１，…，ｈに対して
【００５１】
【数２９】
0003540852.tif 000013
【００５２】
の形態の積を計算するための（ｔ−ｈ）回の掛け算、およびフォーループ（for-loop）のための（２ｈ−２）回の掛け算、であり、平均｛ｔ（ｂ−１) ／ｂ＋ｈ−２｝回（ランダムに選択された指数に対して、ｔ／ｂディジットは“０”と予想される）であることが容易に分かる。
Ｄに対する最も明らかな例は、基数ｂの数系（Ｍ＝｛１｝，ｈ＝ｂ−１，ｔ＝「logb(2n −1)）である。５１２ビット指数に対して、ｂ＝２６の選択は予想される掛け算の数を最小化する。このような基本的な技法は、平均１２７．８回、最悪の場合１３２回の掛け算および１０９個の事前計算値のための記憶部を要求する。さらに適切な基数の選択はｂ＝３２である。なぜならば、指数Ｒに対するディジットは１回に５ビットを抽出することにより、基数変換（radix conversion）なく計算され得るからである。この基数において要求される掛け算の数は、平均的な場合で只１つのみ増加し、最悪の場合にも変わらず維持される。
【００５３】
この基本技法が、可用な記憶部が小さい場合には明白な選択であるとしても、記憶部の数が１０９以下に下がるにつれ遂行能力が相当落ちる。これにより、ＢＧＭＷ方法は、可用な記憶部が非常に小さい場合に、その計算を遂行するための効率的な方法が提供できないことが分かる。
また、Brickellなどは、勿論事前計算値のためにさらに多くの記憶部を利用するが、要求される掛け算の数を減少させるために他の数系を利用するさまざまな技法を提供した。極端な例の１つは、集合Ｍを次の式のように選択する。
【００５４】
Ｍ2 ＝｛ｍ｜１≦ｍ＜ｂ，ｗ2(ｍ）＝０ ｍｏｄ ２｝
ここで、ｗp (m) はｍを割れるｐの最高羃乗である（例えば、ｗ2(４０）＝３。
すると、１≦ｄi ＜ｂにおいて、あるｍ∈Ｍ2 に対してｄi ＝ｍ又はｄi ＝２ｍとなる（すなわち、ｈ＝２）。このように、｜Ｍ2 ｜「log b (2n −1)個の値に対する記憶部を備えると、ｇR は平均ｔ回の掛け算、最悪の場合でもｔ（ｂ−１) ／ｂ回の掛け算で計算され得る。例えば、ｂ＝２５６（ｔ＝６４，｜Ｍ2 ｜＝１７０）を採用すると、平均１０８８０個の事前計算値で平均６３．７５回の掛け算となる。Brickellなどが提示した２つのテ−ブルを、本実施例の方法による結果と比較するために、図６の（Ａ），（Ｂ）に示す。
【００５５】
＜本実施例の羃乗演算方法＞
次いで、本実施例による事前計算テ−ブルを利用したｇR の速い計算のための羃乗演算方法を説明する。
本方法は、もしｎビット指数Ｒが２つの同一のブロック（すなわち、Ｒ＝Ｒ1 ×２n/2 ＋Ｒ0 ）で割られ、
【００５６】
【数３０】
0003540852.tif 000014
【００５７】
が事前に計算されると、ｇR を
【００５８】
【数３１】
0003540852.tif 000015
【００５９】
のように計算することにより、要求される掛け算の数をほぼ半分に減らせるという簡単な観察を一般化したものである。
ここで、二進アルゴリズムについてより詳細に説明する。ｎビット指数Ｒを２つの同一のブロックに分けると仮定すると、指数Ｒは次のようなＲ0 ，Ｒ1 で示すことができる。
【００６０】
【数３２】
0003540852.tif 000016
【００６１】
すると、ｇR は次のように表わされる。
【００６２】
【数３３】
0003540852.tif 000017
【００６３】
そして、ｇ2 ＝ｇ＊ｇ1 とすると、ｇR を求めるためのアルゴリズムは次の通りである。
【００６４】
【数３４】
0003540852.tif 000018
【００６５】
前記のアルゴリズムで要求される掛け算の回数は、最悪の場合で、２（ｋ−１）回、平均で７／４（ｋ−１）回になり、単にｇR を二進アルゴリズムで計算する時の掛け算の回数（最悪：２（ｎ−１），平均：３／２（ｎ−１））に比べてほぼ半分に減らせることが分かる。
後述されるように、本願で提案された方法は、ＢＧＭＷ方法に比べて、可用記憶容量が非常に小さいかあるいは大きい場合にさらに効率的であり、また広い範囲で時間−メモリのトレ−ドオフを与えるので、さらに融通性がよい。また、制限された記憶容量および計算能力を有するスマ−トカ−ドへの応用では、小さい記憶部を使用するのが非常に重要であるが、ＢＧＭＷ方法はこの場合にそれほど効率的でない。
【００６６】
本願で提案された方法の他の利点は、Schnorr の識別および署名技法やその変形（例えば、Brickell-McCurley 技法および Okamoto技法）の検証に必要なｇR ｙE （ここで、ｙは固定されず、Ｅの大きさはＲの大きさより一層小さい）を効率的に計算できる。このような種類の計算において、指数を非二進羃指数で表記するのは、オンライン計算の負荷を極めて増加させることに注目しなければならない。
【００６７】
最後に、提案された方法が並列処理にも又非常に適することを説明する。
＜指数の分割＞
先ず、ＲをｇR を計算するためのｎビット指数とする。図１のように、指数Ｒをｈ個のブロックＲi （０≦ｉ≦ｈ−１、ビット大きさａ＝「（ｎ／ｈ））に分割し、各Ｒi はさらに小さいｖ個の副ブロックＲi,j （０≦ｊ≦ｖ−１、ビット大きさｂ＝「（ａ／ｖ））に分割する。
【００６８】
ここで、図１は、グループの固定した基本要素ｇが与えられた場合、任意のｎビットランダム数Ｒに対して、本実施例による事前計算方法を利用して羃乗ｇR を計算するために、指数Ｒを分割する方法を示したものである。
＜分割ブロックによるｇR の表現＞
【００６９】
【数３５】
0003540852.tif 000019
【００７０】
と定義する。
すると、式(4) を利用してｇR を次のように表現できる。
【００７１】
【数３６】
0003540852.tif 000020
【００７２】
＜ｇR の二進表現＞
もし、Ｒi ＝ｅi,a-1 …ｅi,1 ｅi,0 がＲi （０≦ｉ＜ｈ）の二進表現とすると、Ｒi,j （０≦ｊ＜ｖ）は次のように二進で表記される。
【００７３】
【数３７】
0003540852.tif 000021
【００７４】
よって、式 (5)は次のように書き直せる。
【００７５】
【数３８】
0003540852.tif 000022
【００７６】
＜事前計算＞
次いで、次の値が全ての１≦ｉ＜２h および０≦ｊ＜ｖに対して事前計算されて記憶されると仮定する。
【００７７】
【数３９】
0003540852.tif 000023
【００７８】
ここで、ｆは、ｅh-1 …ｅ1 ｅ0 の十進値と等価である。
＜羃乗計算＞
図２のように事前計算値に対するテ−ブルが記憶されていると、式(6) は次のように書き直せる。
【００７９】
【数４０】
0003540852.tif 000024
【００８０】
ここで、Ｉj,k ＝ｅh-1,bj+k…ｅ1,bj+kｅ0,bj+k（０≦ｊ＜ｂ）である（Ｉj,k は、図１のｊ番目のブロック列のｋ番目のビットから成る行方向のｈビット列に対応する）。
次のような一般的な自乗と掛け算方法により、式(8) を使用してｇR を直接計算する。該アルゴリズムは、事前計算テ−ブルＧ［ｊ］［ｆ］を利用して、任意のｎビットランダム数Ｒに対してｇR を計算するものであり、ここで、Ｒは図１のように分割され、アルゴリズムに使用されるＩj,k は該Ｒの配列から読み出して使用する。
【００８１】
【数４１】
0003540852.tif 000025
【００８２】
＜羃乗演算の具体例＞
以上で説明された、本実施例による羃乗演算方法をさらに詳細に考察するために、具体的な例を通じて説明する。
具体例において、指数Ｒは３２ビットであり、二進数で表わされるＲの値は次のようであると仮定する。
【００８３】
Ｒ＝01100010101001111001000101011011(2)
ここで、指数Ｒは４（＝ｈ）つのブロックＲi （０≦ｉ≦３）に分割され、各Ｒi はさらに小さい３（＝ｖ）つの副ブロックＲi,j にさらに分割される。すると、各ブロックの大きさａおよび各副ブロックの大きさｂは次の通りである。
ａ＝「（ｎ／ｈ）＝「（３２／４）＝８ビット
ｂ＝「（ａ／ｖ）＝「（８／３）＝３ビット
図３は前述したように、本例で適用される３２ビットの指数Ｒに対する分割配置図を示すものである。図３を参照して、指数Ｒは式(4) により次のように表記され得る。
【００８４】
【数４２】
0003540852.tif 000026
【００８５】
そして、これを具体的に表記すれば次の通りである。
Ｒ0 ＝01011011(2) ＝01(2) ＊２6 ＋ 011(2) ＊２3 ＋ 011(2) ＊２0
Ｒ1 ＝10010001(2) ＝10(2) ＊２6 ＋ 010(2) ＊２3 ＋ 011(2) ＊２0
Ｒ2 ＝10100111(2) ＝10(2) ＊２6 ＋ 100(2) ＊２3 ＋ 111(2) ＊２0
Ｒ3 ＝01100010(2) ＝01(2) ＊２6 ＋ 100(2) ＊２3 ＋ 010(2) ＊２0
ｇ0 ＝ｇとし、ｇi を
【００８６】
【数４３】
0003540852.tif 000027
【００８７】
と定義する。
ｇ0 ＝ｇ，ｇ1 ＝（ｇ256)1 ，ｇ2 ＝（ｇ256)2 ，ｇ3 ＝（ｇ256)3
すると、式(5) によりｇR を次のように表現できる。
【００８８】
【数４４】
0003540852.tif 000028
【００８９】
また、Ｒi ＝ｅi,7 …ｅi,1 ｅi,0 がＲi （ｉ＝０，１，２，３）の二進表現なので、Ｒi,j （ｊ＝０，１，２）は次のように二進で表わされる。
Ｒi,j ＝ｅi,j3+2 ｅi,j3+1 ｅi,j3+0
したがって、ｇR は次のように書き直せる。
【００９０】
【数４５】
0003540852.tif 000029
【００９１】
次いで、次の値が全ての〔１≦ｆ＜２4 および０≦ｊ＜３〕に対して事前計算され記憶されると仮定する。
【００９２】
【数４６】
0003540852.tif 000030
【００９３】
ここで、ｆはｅ3 ｅ2 ｅ1 ｅ0 の十進値をいう。
すなわち、次の通りである。
Ｇ[0][1]＝ｇ30ｇ20ｇ10ｇ01
Ｇ[0][2]＝ｇ30ｇ20ｇ11ｇ00
Ｇ[0][3]＝ｇ30ｇ20ｇ11ｇ01
Ｇ[0][4]＝ｇ30ｇ21ｇ11ｇ01
・・・・・・・・・・・
Ｇ[0][14] ＝ｇ31ｇ21ｇ11ｇ00
Ｇ[0][15] ＝ｇ31ｇ21ｇ11ｇ01
そして、式(7) により、
【００９４】
【数４７】
0003540852.tif 000031
【００９５】
ここで、２3 ＝８，２j3＝８j である。
例えば、ｊ＝１に対して、
Ｇ[1][1]＝（Ｇ[0][1]）8
Ｇ[1][2]＝（Ｇ[0][2]）8
・・・・・・・・・・・
Ｇ[1][15] ＝（Ｇ[0][15] ）8
そして、ｊ＝２に対して、
Ｇ[2][1]＝（Ｇ[1][1]）8 ＝〔（Ｇ[0][1]）8 〕8 ＝（Ｇ[0][1]）64
Ｇ[2][2]＝（Ｇ[1][2]）8 ＝〔（Ｇ[0][2]）8 〕8 ＝（Ｇ[0][2]）64
・・・・・・・・・・・
Ｇ[2][15] ＝（Ｇ[1][15] ）8 ＝〔（Ｇ[0][15] )8〕8 ＝（Ｇ[0][15])64
次に示した図４は、前述したような方法により求められた事前計算値Ｇ[j][f]をメモリに記憶する配列形態、およびここに記憶される値を示す。
【００９６】
すると、ｇR は式(8) により次のように書き直せる。
【００９７】
【数４８】
0003540852.tif 000032
【００９８】
ここで、Ｉj,k ＝ｅ3,3j+kｅ2,3j+kｅ1,3j+kｅ0,3j+k（０≦ｊ＜３）である。
全てのｊおよびｋに対してＩj,k を計算すると次の通りである。
Ｉ0,0 ＝ｅ3,0 ｅ2,0 ｅ1,0 ｅ0,0 ＝０１１１(2) ＝７
Ｉ0,1 ＝ｅ3,1 ｅ2,1 ｅ1,1 ｅ0,1 ＝１１０１(2) ＝１３
Ｉ0,2 ＝ｅ3,2 ｅ2,2 ｅ1,2 ｅ0,2 ＝０１００(2) ＝４
Ｉ1,0 ＝ｅ3,3 ｅ2,3 ｅ1,3 ｅ0,3 ＝０００１(2) ＝１
Ｉ1,1 ＝ｅ3,4 ｅ2,4 ｅ1,4 ｅ0,4 ＝００１１(2) ＝３
Ｉ1,2 ＝ｅ3,5 ｅ2,5 ｅ1,5 ｅ0,5 ＝１１００(2) ＝１２
Ｉ2,0 ＝ｅ3,6 ｅ2,6 ｅ1,6 ｅ0,6 ＝１００１(2) ＝９
Ｉ2,1 ＝ｅ3,7 ｅ2,7 ｅ1,7 ｅ0,7 ＝０１１０(2) ＝６
式(8a)を利用してｇR を前述したアルゴリズムによって計算する。
【００９９】
先ずｋ＝２に対して、
【０１００】
【数４９】
0003540852.tif 000033
【０１０１】
ｋ＝１に対して、
【０１０２】
【数５０】
0003540852.tif 000034
【０１０３】
ｋ＝０に対して、
【０１０４】
【数５１】
0003540852.tif 000035
【０１０５】
したがって、
【０１０６】
【数５２】
0003540852.tif 000036
【０１０７】
ここで、２2 ＝４，２1 ＝２，２0 ＝１である。
以上で具体的な例を通じて事前計算テーブルを利用した羃乗演算方法を詳細に説明した。勿論指数Ｒの大きさは説明を簡単にするために３２ビットであると仮定したが、一般に５１２ビット又はそれ以上のビットの大きさを有するＲに対しても、同一の方法により本実施例の具体的例と同様に説明され得る。
【０１０８】
＜演算回数の評価＞
次に、前述したようなアルゴリズムにより要求される掛け算の回数を数える。図１の（ｖ−１）番目のブロックは、ｂビットで満たされないこともあることに注目しなければならない。事実上、それは（ｂｖ−ａ）ビットである。このように内部のフォーループ(for-loop)で共に乗じられる項の数は、一番目の（ｂｖ−ａ）ラウンドに対するｖ回、およびその余りの（ｂ−ｂｖ＋ａ）ラウンドに対する（ｖ＋１）回である。よって、要求される全体の掛け算の回数は、最悪の場合、多くて｛ｖ（ｂｖ−ａ）＋（ｖ＋１)(ｂ−ｂｖ＋ａ）−２｝＝（ａ＋ｂ−２）回である。Ｉj,k が“０”である確率が１／２h であり、前記アルゴリズムによりＩj,k が平均ａ回発生すると仮定できるために、平均的な掛け算の回数は｛ａ（２h −１）／２h ＋ｂ−２｝回で与えられる。もちろん、このような遂行能力は、（２h −１）ｖ個の事前計算値に対する記憶部を具備して達成される。
【０１０９】
＜分割方法の考察＞
前述したように、指数Ｒはほぼ同一の大きさの（ｈ×ｖ）ブロックに区分され、これらの（ｈ×ｖ）ブロックは（ｈ×ｖ）の四角形で配列されると仮定した。大部分の場合に、このような分割と配列とは、与えられた記憶容量に対して他のものよりさらに良い遂行能力を発揮するが、ある場合にはそうでないこともある。
【０１１０】
例えば、図５はほぼ同一の記憶部を要求する２つの相異なる構成を示したものであり、図５に示した２つの構成、すなわち５１２ビット指数が２つの相異なる方式に分割され配列された構成を考察する。
１番目の構成は（５×５）の構成で、前記において分析した場合に該当し、１５５個の値に対する記憶部を具備し、平均１１８．７８回の掛け算（最悪の場合１２２回）という遂行能力を示す。一方、２番目の構成は、（５×１｜６×２）の構成で１５７個の値に対する記憶部を使用して、平均１１７．１３回の掛け算（最悪の場合１１９回）で羃乗演算ができる。よって、２番目の構成の方がさらに良い選択であることが分かる。
【０１１１】
｛ｈ1 ×ｖ1 ｜ｈ2 ×ｖ2 （ｈ1 ＜ｈ2 ）｝型の構成で、最悪／平均の場合での遂行能力に対する一般的な公式を容易に引き出すことができる。ｂ1 およびｂ2 をそれぞれ（ｈ1 ×ｖ1 ）および（ｈ2 ×ｖ2 ）に区分されたブロックの大きさとする。さらに良い遂行能力のために、ｂ2 はｂ1 より大きいか等しくなければならないので、（ｈ×ｖ）構成でのｂのような方法により得られる。このように、ｂ1 およびｂ2 は次のように求められる。
【０１１２】
ｂ2 ＝「（ｎ／（ｈ1 ｖ1 ＋ｈ2 ｖ2 ））
ｂ1 ＝「（（ｎ−ｂ2 ｈ2 ｖ2 ）／ｈ1 ｖ1 ）
該構成で要求される最悪の場合の掛け算の回数は、（ｈ×ｖ）構成に対する公式からａを（ｈ1 ｖ1 ＋ｈ2 ｖ2 ）に、そしてｂをｂ2 にそれぞれ置換することにより直接求められる。これは最悪の場合、｛ｂ1 ｖ1 ＋ｂ2 （ｖ2 ＋１）−２｝回の掛け算という結果になる。同様に、平均的な掛け算の回数は次の式の通りである。
【０１１３】
【数５３】
0003540852.tif 000037
【０１１４】
このような遂行能力は、
【０１１５】
【数５４】
0003540852.tif 000038
【０１１６】
個の事前計算値に対する記憶部を具備して達成される。
２つの構成形態である（ｈ×ｖ）および｛ｈ1 ×ｖ1 ｜ｈ2 ×ｖ2 （ｈ2 ＝ｈ1 ＋１）｝と異なるいずれの構成も、与えられた記憶容量に対してより良い遂行能力が示せないことが容易に分かる。
＜ＢＧＭＷ方法と本方法との比較＞
ＢＧＭＷ方法と本実施例の方法による遂行能力を比較するために、５１２ビットの法に対する掛け算の回数および要求される記憶容量を、１６０ビットおよび５１２ビットの指数のそれぞれについて、ＢＧＭＷ方法を図６に、本実施例を図７，図８にそれぞれ示した。
【０１１７】
図６はＢＧＭＷ方法の遂行能力を説明するためのものであり、図６の（Ａ）は１６０ビットの指数について、そして、図６の（Ｂ）は５１２ビットの指数について、基数ｂ，乗数の集合Ｍ，パラメータｈ，事前計算値のための記憶容量および最悪の場合と平均的な場合の掛け算の回数を示している。
図７，図８は、提案された本実施例の遂行能力を説明するためのものであり、図７は１６０ビットの指数について、そして図８は５１２ビットの指数について、指数Ｒの構成，事前計算値のための記憶容量および最悪の場合と平均的な場合の掛け算の回数を示している。
【０１１８】
本実施例による方法は、ＢＧＭＷ方法に比べて、さらに簡単であるだけでなく、さらに優れた遂行能力を示すことに注目せねばならない。特に、広い記憶容量の範囲に対する効率性のために、本方法は可用な記憶容量に対応して多様なコンピュータ環境に融通性よく応用できる。
例えば、スマートカードによる計算速度を高めるために、（４×２）構成が選択できる。すると、５１２ビットの係数および指数に対して、ｇR の計算は１９２０バイト（ここで、１つの事前計算のための記憶容量は５１２ビット（６４バイト）が必要である）の記憶部により、平均１８２回の掛け算で行われる。反面、比較的に大きい記憶部が使用可能なら、約３２Ｋバイトの記憶部で平均９０．４２回の掛け算を遂行する、例えば（７×４）構成が選択できる。
【０１１９】
＜識別及び署名検証例＞
次に、識別および署名検証において、どのようにして計算速度を向上させ得るかについて説明する。
離散的対数問題に基づいて、多くの識別およびディジタル署名技法が開発されている。このような全ての技法で、些かのモジュラ掛け算と共に、証明者(prover)（又は署名者(signer)）はランダムＲに対するｇR を計算する必要があり、これは以上説明された方法により効率的に遂行され得る。
【０１２０】
一方、識別又は署名を確認するために、検証者（verifier）はｇR ｙE 形態の計算を遂行する必要がある（ここで、ｙは証明者（又は署名者）の公開鍵に該当し、よって、プロトコルの各ラン(run) で変わる）。Ｅの大きさは大体識別技法において２０と４０との間に置かれ、その対応する署名技法ではおよそ８０である。
【０１２１】
次に、ｇR ｙE を計算するために提案された方法の性能を調べる。
ｔをＥの大きさとする。もし、ｔ≦ｂなら、ｇR ｙE は最悪の場合に（ａ＋ｂ＋ｔ−２）回の掛け算で、平均｛ａ（２h −１）／２h ＋ｂ＋0.5t−２｝回の掛け算で計算され得ることは明らかである。ｔ＞ｂの場合には、上記のように進行したり、又はＥをさらに小さいブロックに区分した後、計算することもできる。
【０１２２】
１番目の場合は、最悪の場合に（ａ＋２ｔ−２）回の掛け算で、平均｛ａ（２h −１）／２h ＋1.5t−２｝回の掛け算で計算が遂行される。しかしながら、もしｔがｂより非常に大きいならば、Ｅをさらに小さいブロックに分けることにより、その遂行能力をさらに向上させ得る。
したがって、さらに一般的な公式のために、Ｅがほぼ同じ大きさのｕブロックに区分されると仮定する（ｇR ｙE を計算するための全体構成を（ｕ×１｜ｈ×ｖ）と考える）。
【０１２３】
ｃを区分されたブロックのビット長さとする（すなわち、ｃ＝「（ｔ／ｕ））。すると、先ずｋ＝１，２，…，ｕ−１に対する
【０１２４】
【数５５】
0003540852.tif 000039
【０１２５】
およびそれらの組合可能な各掛け算を計算しなければならず、これら全てでは｛（ｕ−１）ｃ＋２u −ｕ−１｝回の掛け算が必要である。注目のｔの範囲（すなわち、ｔ＝８０までの範囲）に対して、ｕは多くて３を採る。
もし、ｃ≦ｂなら、最悪の場合に最大ｃ回の掛け算の追加で十分である（平均｛ｃ（２u −１）／２u ｝回）。したがって、この場合に要求される掛け算の全体回数は次の通りである。
【０１２６】
最悪の場合：（ａ＋ｂ＋ｕｃ＋２u −ｕ−３）回
平均：［ａ（２h-１)/２h ＋ｂ＋ｃ（ｕ２u-１)/２u ＋２u −ｕ−３］回
同様に、ｃ＞ｂの場合に対して、掛け算の数は次の通りである。
最悪の場合：｛ａ＋（ｕ＋１）ｃ＋２u −ｕ−３｝回
平均：［ａ（２h-１)/２h ＋ｃ{(ｕ＋１）２u −１}/２u ＋２u −ｕ−３］回
本願で提案された方法により、Schnorr のような識別および／又は署名技法が、スマートカード上においてさらに実用的に実現される。例えば、５１２ビットの法，１６０ビットの指数およびｔ＝３０の場合、もし１９２０バイトの記憶部が使用可能なら（４×２構成）、検証状態は平均８０．５回の掛け算で検査される。同様に、ｔ＝８０の署名は、同じ記憶部を使用して、平均１４４．１３回の掛け算で検証される。
【０１２７】
ｔ＝３０に対して平均２４６．５回の掛け算、およびｔ＝８０に対して平均２５９．０回の掛け算を要求する二進方法と比べると、これは非常に小さい記憶部で相当な速度向上となる。
しかも、識別又は署名検証は、常に大きい容量のメモリが備えられるより強力なターミナルで遂行される。このような環境で、例えば（８×２）構成を採用する場合、３２Ｋバイトの記憶部を利用すれば、ｔ＝３０に対して平均６０．２回の掛け算で識別検証を、そしてｔ＝８０に対して平均１２６．６回の掛け算で署名検証が遂行できる。
【０１２８】
＜予備計算の伝送＞
次に、小さなコミュニケーションの追加で、ｇR ｙE を計算するための掛け算の回数をさらに相当数減少させ得ることを説明する。
すなわち、ｙは署名者に固定した数なので、もし署名者が、ｋ＝１，２，…，ｕ−１に対する
【０１２９】
【数５６】
0003540852.tif 000040
【０１３０】
を予め計算して記憶した後、署名と共に伝達すれば、検証者はこれらを準備するためのオンライン計算の負荷が節約できる。
例えば、ｔ＝８０の署名技法に対して、もし署名者がメッセージに対する署名と共に、追加的な５１２ビットのブロックｙ1 ，ｙ2 、ここで、
【０１３１】
【数５７】
0003540852.tif 000041
【０１３２】
を伝送すると、署名検証は（４×２）構成により平均９０．１３回の掛け算で行われる。したがって、単に１２８バイト情報の伝送の追加により５４回の掛け算が節約される。これは平均２５９回の掛け算を要求する二進方法に比べて、平均しておよそ３倍の速度向上に該当する。
ＢＧＭＷ方法は、前記考慮したいずれの場合でもｇR ｙE 形態の計算にそれほど効率的でないことが分かる。すなわち、伝送の追加がない場合、もし指数が非二進の羃乗基数で表記されれば、ｙE に対して要求されるオンライン事前計算を遂行するのに、さらに多くの計算が必要になる。一方、追加伝送が許容される場合は、小さい基数の使用のために、さらに多くの事前計算値が伝送されなければならない。
【０１３３】
事前計算および追加伝送を結合した前記本方法は、またアメリカのディジタル署名標準（ＤＳＳ；Digital Signature Standard）の検証の速度向上に使用され得る。ＤＳＳでは、｜Ｒ｜＝｜Ｅ｜＝１６０のｇR ｙE 形態の計算の遂行が必要であり、よって、追加伝送がなければ事前計算によって何の利点も得られない。しかしながら、もし署名者が３つの追加ブロック｛ｙ1 ，ｙ2 ，ｙ3 ｝、ここで、
【０１３４】
【数５８】
0003540852.tif 000042
【０１３５】
を送り、もし検証者が（４×２）構成を採用すると、署名は平均１２４回の掛け算で検証される。これは、５１２ビット法に対して平均２７９回の掛け算を要求する二進方法に比べて、単に１９２０バイトの記憶部および１９２バイトの追加伝送のみで、２倍以上の速度向上が得られることを意味する。
図９は、前述したように、署名者が署名と共に公開鍵に対する追加の３つの事前計算値を伝送するという仮定のもとで、３つの署名技法（Schnorr ，ＤＳＳおよび Brickell-McCurley）での署名生成および検証で要求される掛け算の回数を示している。ここでは、他のリダクションモッド  ｑ（reduction mod q ）およびマルチプリケーティブインバースモッド  ｑ（multiplicative inverse mod q）（ここで、ｑは約１６０ビットの大きさの素数である）のようにそれほど重要でない演算は無視し、単に羃乗演算に必要な掛け算の回数のみを考慮している。
【０１３６】
（４×２）および（８×２）の２つの構成が例として挙げられるが、これは前者はスマートカードの応用に適合し、後者は割合に大容量の記憶装置を備えた一般的な応用に適合するからである。比較のために、二進方法の遂行能力を共に示した。
＜並列処理例＞
次に、本願で提案された方法は、並列処理にも非常に適することが分かる。すなわち、ｊ番目のプロセッサを（ｈ×ｖ）構成（図１参照）のｊ番目列に割り当てることにより、ＢＧＭＷ方法よりさらに効率的に多重プロセッサによる並列化が実現される。
【０１３７】
もしｖ個のプロセッサが使用可能なら、ｊ番目のプロセッサは次の式(10)に含まれる式(9) を計算するために割り当てることができる。ここで、各プロセッサはローカルメモリ内に（２h −１）個の事前計算値を記憶すると仮定する。
【０１３８】
【数５９】
0003540852.tif 000043
【０１３９】
各プロセッサの計算は、最大２（ｂ−１）回の掛け算で完了する。その後、最終結果を求めるために追加で「（log2v ）回の掛け算が必要である。よって、掛け算の全体回数は、｛２（ｂ−１）＋「（log2v ）｝回である。
図１０は並列処理において、プロセッサの数およびプロセッサ当たり必要な記憶部により、１６０／５１２ビットの指数に対して要求される掛け算の回数を示す。ここで、ｎｐはプロセッサの数（ｖ）を、そしてｓｐはプロセッサ当たり記憶容量（２h −１）を意味する。
【０１４０】
図１０に示したように、小さい数のプロセッサでもその性能が非常に向上することが分かる。例えば、５１２ビットの法および指数に対しては、４つのプロセッサが使用可能であり、各プロセッサは２５５個の事前計算値のためのローカル記憶部（約１６Ｋバイト）を備える場合に、ｇR を３２回の掛け算で計算できる。例えば、１６個のようにさらに多いプロセッサによれば、羃乗演算は同じ記憶容量で１０回の掛け算により行われる。
【０１４１】
一方、前記では便宜上（ｈ×ｖ）構成に対してｖ個のプロセッサが使用可能な場合のみを考慮したが、より一般的にさらに小さい数のプロセッサで（ｈ×ｖ）構成を利用することもできる。もし、ｐ個のプロセッサが使用可能であり、ｖ＝ｐｗとする場合、各プロセッサがｗ個の列に該当するｈ×ｗを計算するように割り当てる。この場合、各プロセッサは、ローカル記憶部に｛（２h −１）ｗ｝個の事前計算値を記憶する必要がある。そして、この際に要求される掛け算の回数は、｛（ｗ＋１）ｂ＋「（log2p ）−２｝回になることが分かる。実際、大部分の場合、このように各プロセッサに多数の列を割り当てるのが、図１０で与えられた値より時間−記憶容量のトレードオフにおいてさらに有利である。
【０１４２】
【発明の効果】
前述したように、本発明により、公開鍵暗号システムにおいて、固定した基本要素に依存する事前計算テ−ブルを利用して羃乗演算をより高速に行える羃乗演算を含む暗号化方法及びその装置を提供できる。
すなわち、本発明によると、事前計算による速い羃乗演算のための新しい構成を提案することにより、非常に簡単でありながらもＢＧＭＷ方法よりもさらに良い遂行能力をなし得る。
また、本発明の方法は、広い範囲の時間−記憶容量のトレードオフにより、多様な計算環境に融通性よく応用可能である。
【０１４３】
特に、本発明の方法を使用して、非常に小さい記憶部を備えたスマートカードによる計算速度も相当向上させ得る。
また、本発明の方法は、ｇR ｙE （ｙは変数）形態の計算速度も向上させ得る。これは、Schnorr 型の識別および署名技法をさらに実用性よく実現する。なぜならば、証明者（署名者）だけでなく、検証者も適度な記憶容量により非常に大きい計算上の利点が得られるからである。
【０１４４】
最後に、本願で提案された本発明のアルゴリズムがどのように並列化され得るかを説明した。このような並列処理は、多重のプロセッサを備えた高性能のサーバ（server）装置で特に有用である。
【図面の簡単な説明】
【図１】本実施例により任意のｎビットランダム指数Ｒを分割配置する方法を示した図である。
【図２】図１に関連する事前計算値にテーブルを示した図である。
【図３】３２ビットの指数Ｒに対する分割配置図である。
【図４】図３と関連する事前計算値に対するテーブルを示した図である。
【図５】事前計算値テーブルでほぼ同一の記憶装置を要求する２つの相異なる構成を示す図である。
【図６】ＢＧＭＷ方法の遂行能力を説明するための図である。
【図７】本実施例による方法の遂行能力を説明するための図である。
【図８】本実施例による方法の遂行能力を説明するための図である。
【図９】署名者が追加情報を伝送する場合、さまざまな署名技法での署名生成および検証で要求される掛け算の数を示す図である。
【図１０】並列処理で要求される掛け算の数を示す図である。
【図１】
0003540852.tif 000049
【図２】
0003540852.tif 000050
【図３】
0003540852.tif 000051
【図４】
0003540852.tif 000052
【図５】
0003540852.tif 000053
【図６】
0003540852.tif 000054
【図７】
0003540852.tif 000055
【図８】
0003540852.tif 000056
【図９】
0003540852.tif 000057
【図１０】
0003540852.tif 000058