(57)【要約】【課題】楕円曲線暗号の暗号処理では、乗算及び除算が過半の時間を要する。乗算では次数が増えるため、最速と言われるＯＥＦ方式では、多項式積を取り、法多項式で余りを取るという２段階の演算を行うなど、高速化の壁になっている。【解決手段】拡大体ＧＦ（ｐm ）を用いる楕円曲線暗号の演算処理では、既約多項式ｆ( ｘ）と基底の選び方によって処理速度が大きく変わってくる。本発明では、楕円曲線暗号処理に、既約多項式      ｆ( ｘ )＝(x2m+1−1)/(x −1)＝ｘ2m＋ｘ2m-1＋…ｘ＋１      （４）を用い、その零点であるf （ω）＝０となるωにより、基底｛ω＋ω-1，ω2 ＋ω-2，…，ωm ＋ω-m｝を構成する。これにより任意の元が自己相反元で与えられるため、ＣＶＭＡ法を用いて乗算を定義することで演算量を削減でき高速化を可能にする。図２は、本発明による乗算装置のブロック図である。【選択図】図２
2005284111.tif 000002
【特許請求の範囲】
【請求項１】
標数ｐ、拡大次数ｍであるガロア拡大体ＧＦ（ｐm ）を定義体にもつ楕円曲線暗号の高速演算処理方法であって、
楕円曲線暗号処理に用いるガロア拡大体ＧＦ（ｐm ）は、その標数ｐが、ｎをワード長未満の値として
ｐ＝２n ±ｃ（log2ｃ≦n/2 ）の形式の素数であること、
また既約法多項式
ｆ( ｘ )＝(x2m+1−1)/(x −1)＝ｘ2m＋ｘ2m-1＋…ｘ＋１
を用い、その零点であるｆ（ω）＝０となるωにより、
｛ω＋ω-1，ω2 ＋ω-2，…，ωm ＋ω-m｝
を基底とすること、および２ｍ＋１は素数であること、
により定義されるものであることを特徴とする楕円曲線暗号の高速演算処理方法。
【請求項２】
上記拡大次数ｍは、２、３、５、６等の次数であることを特徴とする請求項１に記載の楕円曲線暗号の高速演算処理方法。
【請求項３】
上記標数ｐの対数値log2ｐが、計算機のワード長１６，３２，６４、１２８等の近傍の素数であることを特徴とする請求項１に記載の楕円曲線暗号の高速演算処理方法。
【請求項４】
ガロア拡大体ＧＦ（ｐm ）の任意の２元
Ａ＝ａ1 ω＋ａ2 ω2 ＋・・・ａm ωm ，ａi ∈ＧＦ（ｐ）
Ｂ＝ｂ1 ω＋ｂ2 ω2 ＋・・・ｂm ωm ，ｂi ∈ＧＦ（ｐ）  
について、その多項式積
Ａ×Ｂ＝ａ1 ｂ1 ω2 ＋（ａ1 ｂ2 ＋ａ2 ｂ1 ）ω3 ＋・・・                          ＋ａm ｂm ω2m
＝ｃ2 ω2 ＋ｃ3 ω3 ＋・・・＋ｃ2mω2m 
の演算を、ＣＶＭＡ法により行うことを特徴とする請求項１に記載の楕円曲線暗号の高速演算処理方法。
【請求項５】
標数ｐ、拡大次数ｍであるガロア拡大体ＧＦ（ｐm ）を定義体にもつ楕円曲線暗号の高速演算処理装置であって、
楕円曲線暗号処理に用いるガロア拡大体ＧＦ（ｐm ）は、その標数ｐが、
ｐ＝２n ±ｃ（log2ｃ≦n/2 ）の形式の素数であること、
また既約法多項式
ｆ( ｘ )＝(x2m+1−1)/(x −1)＝ｘ2m＋ｘ2m-1＋…ｘ＋１
を用い、その零点であるｆ（ω）＝０となるωにより、
｛ω＋ω-1，ω2 ＋ω-2，…，ωm ＋ω-m｝
を基底とすること、および２ｍ＋１は素数であること、
により定義される楕円曲線により暗号処理する手段を備えていることを特徴とする楕円曲線暗号の高速演算処理装置。
【請求項６】
上記拡大次数ｍは、２、３、５、６等の次数であることを特徴とする請求項５に記載の楕円曲線暗号の高速演算処理装置。
【請求項７】
暗号処理する手段は、ガロア拡大体ＧＦ（ｐm ）の任意の２元
Ａ＝ａ1 ω＋ａ2 ω2 ＋・・・＋ａm ωm ，ａi ∈ＧＦ（ｐ）
Ｂ＝ｂ1 ω＋ｂ2 ω2 ＋・・・＋ｂm ωm ，ｂi ∈ＧＦ（ｐ）
について、その多項式積
Ａ×Ｂ＝ａ1 ｂ1 ω2 ＋（ａ1 ｂ2 ＋ａ2 ｂ1 ）ω3 ＋・・・                          ＋ａm ｂm ω2m
＝ｃ2 ω2 ＋ｃ3 ω3 ＋・・・＋ｃ2mω2m 
の演算を、ＣＶＭＡ法により行う乗算装置を備えていることを特徴とする請求項５または請求項６に記載の楕円曲線暗号の高速演算処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報通信の秘匿や認証などの守秘機能に広く利用される公開鍵暗号に有用な楕円曲線暗号の高速演算処理方法および装置に関し、特にガロア拡大体を用いる楕円曲線暗号処理における二元の乗算を高速化するアルゴリズムに関する。
【０００２】
近年のインターネットの普及に伴い、オープンネットワークセキュリティの必要性が高まり、それを実現するための暗号技術は不可欠の基盤技術である。楕円曲線暗号は次世代の公開鍵暗号として、標準化・実装化研究が進められている。暗号処理では、四則演算の内、乗算及び除算に過半の時間を要する。特に除算における逆元の算出が課題である。本発明は、そのための１つの有効な解決手段を提供する。
【背景技術】
【０００３】
公開された通信網を用いて、重要な情報や有料の情報、プライベートな情報を秘匿したり、署名・認証により本人であることを確認する場合には、暗号が用いられる。特に多数の相手と通信を行なうのに暗号技術は不可欠となる。暗号化方式には、共通鍵暗号と公開鍵暗号の２方式がある。一般には、この２方式が組み合わせて用いられる。公開鍵暗号系の中でも、最近注目されている楕円曲線暗号は、従来の暗号（ＲＳＡ方式）に比べて、不法な解読に対する強度が格段に高く、ＲＳＡ方式の暗号では現実に解読を回避するのに1024ビットもの鍵長が必要とされているのに対して、楕円曲線暗号では、同等の暗号強度を確保するのに160 ビットで済むことから、楕円曲線暗号は国際標準になろうとしており、実装化の研究がさかんに進められている。
【０００４】
一般に暗号に用いられる楕円曲線は、ｙ2 ＝ｘ3 ＋ａｘ＋ｂ  で表され、曲線上の有限個の点（ｘ，ｙ）を用いて暗号処理がなされる。これまで曲線上の有限個の点の定義体には、標数が奇素数ｐの有限体ＧＦ（ｐ）や、２の拡大体ＧＦ（２m ）が用いられてきた。標数が２の拡大体ＧＦ（２m ）とは、ＧＦ（２）のｍ次元ベクトル空間をいい、各元は（0,1,0,0,・・・）のようにｍ個の０と１で表される。拡大体ＧＦ（２m ）は、コンピュータが基本的にデータを 2進法で表わすことと、従来からの誤り符号訂正技術の流れとから、これまで研究開発の主流となっていた。たとえばｍ＝160 とした拡大体ＧＦ（２160 ）においては、鍵長が160 ビットとなる。しかし、GF(pm ）の場合は32ビットワードを６ヶで構成できるので、ソフトウエアのマイコン実装容易性から、GF(pm ）の採用が有利である。
【０００５】
また最近、Baileyらによりソフトウエア実装可能な有力な拡大体としてＯＥＦ（ Optimal Extension Field) が提案された（非特許文献１参照）。ＯＥＦでは、法多項式を既約２項式とした多項式基底を用いることにより多項式剰余演算を容易にしており、その結果、高速な乗算を可能にする。また、ＯＥＦにおいて逆元演算を行う場合に、正規基底及びFrobenius 写像を用いる高速な方法が提案されている（非特許文献２，３参照）。
【０００６】
ＯＥＦでは、標数を擬メルセンヌ素数、法多項式を既約２項式として多項式剰余演算を行うことにより、まず任意元同士の高速な乗／算を可能とした。この高速乗算をもとに、伊東−辻井アルゴリズムを応用した高速な逆元算出法を導入することで、除算の高速化を実現している。
【０００７】
このようなことから、現在では、楕円曲線暗号が標準になろうとしており、上記ＯＥＦのほか本発明者等によるＡＯＰＦ( 非特許文献４参照) や、Lenstra 等によるＸＴＲ（非特許文献５参照）などのソフトウェア実装に関する研究が行われている。
【０００８】
次に、ＯＥＦの定義と乗算の仕組みについて説明する。
ＯＥＦの定義
ＯＥＦは、次の〔数１〕中の（ｉ），（ii），(iii) の３条件を満たす拡大体である。
【０００９】
【数１】
2005284111.tif 000003
【００１０】
（ｉ）及び（ii）は、素体ＧＦ（ｐ）上の乗算を高速に行うための標数ｐの選定条件であ
り、(iii) は拡大体ＧＦ（ｐm ）上の乗算を高速に行うための条件である。
【００１１】
ＯＥＦにおける乗算法
まず、ＯＥＦの任意元Ａ，Ｂ∈ＧＦ（p m ）が法多項式ｆ（ｘ）＝ｘm −ｓの零点αによる多項式基底：｛１，α，α2 ，・・・αm-1 ｝の線形結合の形で、次のように表現されているとする。
【００１２】
Ａ＝ａ0 ＋ａ1 α＋・・・ａm-1 αm-1 ，ａi ∈ＧＦ（ｐ）  （１）
Ｂ＝ｂ0 ＋ｂ1 α＋・・・ｂm-1 αm-1 ，ｂi ∈ＧＦ（ｐ）
Ａ，Ｂの積は以下２つのStepにより求められる。
【００１３】
〔Step１：多項式積〕
元Ａ，Ｂを、αを不定元とする多項式と考え、次のような多項式積を求める。
Ａ（α）×Ｂ（α）＝ａ0 ｂ0 ＋（ａ0 ｂ1 ＋ａ1 ｂ0 ）α＋・・・
＋ａm-1 ｂm-1 α2m-2
＝ｃ0 ＋ｃ1 α＋・・・＋ｃ2m-2α2m-2  （２）
上式（２）の係数ｃi （０≦ｉ≦２ｍ−２）を教科書法により計算した場合、ＧＦ（ｐ）上の乗算ｍ2 回と加算（ｍ−１2 ）回が必要である。Karatsuba 法を用いれば、加算回数は増加するものの、乗算回数については減らすことが可能である。
【００１４】
〔Step２：多項式剰余演算〕
ｆ( α )＝αm −ｓ＝０を式（２）に代入し、次の〔数２〕の式（３）を得る。
【００１５】
【数２】
2005284111.tif 000004
【００１６】
すなわち、式（３）から、多項式剰余演算は、素体ＧＦ（ｐ）における乗算ｍ−１回と加算ｍ−１回で実行される。
【００１７】
その他、本発明者らは、先に、楕円曲線暗号処理に、素体ＧＦ（ｐ）上のｍ次既約多項式  ｆ（ｘ）＝（ｘm+1 −１）／（ｘ−１）の零点ωによるｍ個の元の集合：  ｛ω，ω2 ，・・・ωm ｝  を基底とする拡大体ＧＦ（ｐm ）を用いることにより、２元の乗算および逆元演算の高速処理を可能にする方法および装置について特許出願を行っている（特許文献１参照）。
【非特許文献１】D.V.Bailey and C.Paar,"Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms,"  Proc.Asiacrypt2000, LNCS 1976,pp.248-258,(2000).
【非特許文献２】N.P Smart,"On the Performance of Hyperelliptic Cryptosystems,"Proc.Eurocrypt'99,Springer LNCS,vol.1592,pp.165-175,1999.
【非特許文献３】伊東利哉、辻井重男、”正規基底を用いた有限体における高速逆元算出アルゴリズム, ”，信学論(A），vol.J70-A,no.11,pp.1637-1645,1987.
【非特許文献４】野上保之、齋藤昭徳、森川良孝  “Finite Extension Field with Modulus ofAll-One Polynomial and Representation of its Elements for Fast Arithmetic Operations”,Trans.IEICE, vol.E86-A,no.9, p.2376-2387,(2003) .
【非特許文献５】A.Lenstra and E. Verheul, “The XTR Public Key System , ”Proc. Crypto 2000, LNCS 1880, 2000, pp.1-20 .
【特許文献１】特願２００１−２７２７５９（特開2003―84666 号公報）
【発明の開示】
【発明が解決しようとする課題】
【００１８】
上述したように、従来、楕円曲線暗号の演算処理の高速化には、Baileyらにより提案された拡大体のＯＥＦが有効であることが知られている。暗号処理では、四則演算の内、乗算及び除算が過半の時間を要する。乗算では次数が増えるため、最速と言われるＯＦＦ方式では、多項式積を取り、法多項式で余りを取るという２段階の演算を行っており、高速化の壁になっている。本発明は、その改善を図ることを目的としている。
【課題を解決するための手段】
【００１９】
拡大体ＧＦ（ｐm ）を用いる楕円曲線暗号の演算処理では、既約多項式ｆ( ｘ）と基底の選び方によって処理速度が大きく変わってくる。本発明では、楕円曲線暗号処理に、既約多項式
ｆ( ｘ )＝(x2m+1−1)/(x −1)＝ｘ2m＋ｘ2m-1＋…ｘ＋１      （４）
を用い、その零点であるf （ω）＝０となるωにより、ω2m+1＝１および  ω＋ω2 ＋・・・・＋ω2m＝−１  が成立するので、これを利用して基底
｛ω＋ω-1，ω2 ＋ω-2，…，ωm ＋ω-m｝
が構成される。
【００２０】
なお、２ｍ＋１は素数であり、標数ｐは、
ｐ＝２n ±ｃ（log2ｃ≦n/2 ）
の形となる素数である。また計算機への実装上、log2ｐは、ワード長の１６，３２，６４，１２８などの値の付近にあることが望ましい。
【００２１】
本発明で使用される上記の基底は、次のように導出される。まず既約多項式（４）には、次の関係式（５）が示すような性質がある。
【００２２】
f （ω）≡ω2m+1≡１≡ω＋ω2 ＋・・・ ＋ω2m          （５）
ここで、既約多項式の零点を用いた次のような基底を考える。
（ω，・・・ ，ωm ，ωm+1 ，・・・ ，ω2m）
この基底は、上記の関係式（５）を用いると、次のような基底と等価になる。
（ω，・・・ ，ωm ，ωm+1 ，・・・ ，ω2m）≡（ω，・・・ ，ωm ，ω-m ，・・・ ，ω-1）
ここで、βi ＝ωi ＋ω-i  なる元βi を用いて上記等価な基底を次のような基底として考えるものである。
【００２３】
（β1 ，β2 ，・・・ ，βm ）
本発明の暗号処理では、このような基底を用いる結果、任意の二つの元の積を求める際にＣＶＭＡ（Cyclic Vector Multi-plication Algorithm)と呼ばれる乗算方法が適用できるようになり、従来方法に比べて乗算と加算の回数が削減され、高速演算が可能となる。
【００２４】
ＣＶＭＡ法は、本発明方法においても成り立つ関係式
ωm+1 ＝１
ωm ＋ωm-1 ＋…＋ω＋１＝１
を効果的に用いた巡回畳み込み（Cyclic Convolution) により構成する乗算法である。ＣＶＭＡ法は、とくに自己相反元同士の乗算に対して、その演算量が従来のＯＥＦなどと比べて少なくなる特性をもっている（詳しくは前掲の〔非特許文献４〕を参照）。本発明方法では、任意の元が自己相反元で与えられるため、ＣＶＭＡ法を用いて乗算を定義することで演算量が少なくできる。
【００２５】
ここで、自己相反元について説明すると、次の拡大体の元Ａに対し、以下で与えられる元Ａ* をＡの相反元と呼ぶ。
Ａ＝（ａ1 ，ａ2 ，・・・ａm ）
Ａ* ＝（ａm ，ａm-1 ，・・・ａ1 ）
また、Ａ＝Ａ* のとき、その元Ａを自己相反元と呼ぶ。
【００２６】
次にＣＶＭＡ法を用いた乗算について説明する。拡大体の任意の二つの元Ａ，Ｂを次のように表わしたとき、
Ａ＝ａ1 （ω＋ω-1）＋ａ2 （ω2 ＋ω-2），…，＋ａm （ωm ＋ω-m），
ａi ∈ＧＦ（ｐ）
Ｂ＝ｂ1 （ω＋ω-1）＋ｂ2 （ω2 ＋ω-2），…，＋ｂm （ωm ＋ω-m），
ｂi ∈ＧＦ（ｐ）
その積Ｃ＝ｃ1 （ω＋ω-1）＋ｃ2 （ω2 ＋ω-2），…，＋ｃm （ωm ＋ω-m）
は、ＣＶＭＡ法に基づき、次の〔数３〕に示す計算式を用いて求められる。
【００２７】
【数３】
2005284111.tif 000005
【００２８】
本発明は、以下のように構成できる。
（１）  標数ｐ、拡大次数ｍであるガロア拡大体ＧＦ（ｐm ）を定義体にもつ楕円曲線暗号の高速演算処理方法であって、
楕円曲線暗号処理に用いるガロア拡大体ＧＦ（ｐm ）は、その標数ｐが、ｎをワード長未満の値として
ｐ＝２n ±ｃ（log2ｃ≦n/2 ）の形式の素数であること、
また既約法多項式
ｆ( ｘ )＝(x2m+1−1)/(x −1)＝ｘ2m＋ｘ2m-1＋…ｘ＋１
を用い、その零点であるｆ（ω）＝０となるωにより、
｛ω＋ω-1，ω2 ＋ω-2，…，ωm ＋ω-m｝
を基底とすること、および２ｍ＋１は素数であること、
により定義されるものであることを特徴とする楕円曲線暗号の高速演算処理方法の構成。
【００２９】
（２）  上記拡大次数ｍは、２、３、５、６等の次数であることを特徴とする前項（１）に記載の楕円曲線暗号の高速演算処理方法の構成。
【００３０】
（３）  上記標数ｐの対数値log2ｐが、計算機のワード長１６，３２，６４、１２８等の近傍の素数であることを特徴とする前項（１）に記載の楕円曲線暗号の高速演算処理方法の構成。
【００３１】
（４）  ガロア拡大体ＧＦ（ｐm ）の任意の２元
Ａ＝ａ1 ω＋ａ2 ω2 ＋・・・ａm ωm ，ａi ∈ＧＦ（ｐ）
Ｂ＝ｂ1 ω＋ｂ2 ω2 ＋・・・ｂm ωm ，ｂi ∈ＧＦ（ｐ）  
について、その多項式積
Ａ×Ｂ＝ａ1 ｂ1 ω2 ＋（ａ1 ｂ2 ＋ａ2 ｂ1 ）ω3 ＋・・・                          ＋ａm ｂm ω2m
＝ｃ2 ω2 ＋ｃ3 ω3 ＋・・・＋ｃ2mω2m 
の演算を、ＣＶＭＡ法により行うことを特徴とする前項（１）に記載の楕円曲線暗号の高速演算処理方法の構成。
【００３２】
（５）  標数ｐ、拡大次数ｍであるガロア拡大体ＧＦ（ｐm ）を定義体にもつ楕円曲線暗号の高速演算処理装置であって、
楕円曲線暗号処理に用いるガロア拡大体ＧＦ（ｐm ）は、その標数ｐが、
ｐ＝２n ±ｃ（log2ｃ≦n/2 ）の形式の素数であること、
また既約法多項式
ｆ( ｘ )＝(x2m+1−1)/(x −1)＝ｘ2m＋ｘ2m-1＋…ｘ＋１
を用い、その零点であるｆ（ω）＝０となるωにより、
｛ω＋ω-1，ω2 ＋ω-2，…，ωm ＋ω-m｝
を基底とすること、および２ｍ＋１は素数であること、
により定義される楕円曲線により暗号処理する手段を備えていることを特徴とする楕円曲線暗号の高速演算処理装置の構成。
【００３３】
（６）  上記拡大次数ｍは、２、３、５、６等の次数であることを特徴とする前項（５）に記載の楕円曲線暗号の高速演算処理装置の構成。
【００３４】
（７）  暗号処理する手段は、ガロア拡大体ＧＦ（ｐm ）の任意の２元
Ａ＝ａ1 ω＋ａ2 ω2 ＋・・・＋ａm ωm ，ａi ∈ＧＦ（ｐ）
Ｂ＝ｂ1 ω＋ｂ2 ω2 ＋・・・＋ｂm ωm ，ｂi ∈ＧＦ（ｐ）
について、その多項式積
Ａ×Ｂ＝ａ1 ｂ1 ω2 ＋（ａ1 ｂ2 ＋ａ2 ｂ1 ）ω3 ＋・・・                          ＋ａm ｂm ω2m
＝ｃ2 ω2 ＋ｃ3 ω3 ＋・・・＋ｃ2mω2m 
の演算を、ＣＶＭＡ法により行う乗算装置を備えていることを特徴とする前項（５）または（６）に記載の楕円曲線暗号の高速演算処理装置の構成。
【発明の効果】
【００３５】
本発明方法の採用により、楕円曲線暗号の演算処理における素体上での乗算や逆元演算において、乗算の演算速度が向上するため、暗号処理時間を短縮することが可能となる。たとえば、ＣＰＵとしてPentium(登録商標）(800MHz) を用い、マイコンを考慮し３２ビット以下の素数を採用し、一例として、ｐ＝２30＋３、ｍ＝５やｐ＝２28＋３、ｍ＝６で演算処理速度を比較したところ、最も時間を要する逆元算出において、ＯＥＦでは各々６．１５μｓ、６．５９μｓであったが、本発明方法では４．８４μｓ、５．４７μｓとなり、演算速度が約２割向上した。
【発明を実施するための最良の形態】
【００３６】
図１は、本発明を適用した暗号通信システムの概要図であり、ネットワーク１を介して結合された任意の通信装置２〜５の間で、暗号処理された通信が行われる。通信装置２〜５は、専用の通信装置である必要はなく、通信機能をもったパソコンなどの計算機であることができる。通信装置５にのみ示されている楕円曲線暗号処理装置６は、他の各通信装置２〜４にも同様に備えられており、公開鍵暗号によるメッセージの暗号化、復号化の暗号処理を行う。楕円曲線暗号処理装置６は、暗号処理に伴う乗算、除算の高速処理のために乗算装置７を持っている。乗算装置７は、本発明により定義される拡大体に基づくアルゴリズムにしたがって、ＣＶＭＡ法により２元乗算を実行する。乗算装置７は、プログラムにより、あるいは専用ハードウエア回路により構成することができる。
【００３７】
次に、ＣＶＭＡ法による２元の乗算Ａ・Ｂ＝Ｃを演算する乗算装置について説明する。ＣＶＭＡ法における乗算アルゴリズムは次のようなものである。
【００３８】
Ａ＝（ａ1 ，ａ2 ，…，ａm ）              
Ｂ＝（ｂ1 ，ｂ2 ，…，ｂm ）              
Ｃ＝（ｃ1 ，ｃ2 ，…，ｃm ）              
として、
ｃk ＝ｑ0 −ｑk     ｍ≧ｋ≧１
であり、一般にｑk は次の〔数４〕の式で与えられる。
【００３９】
【数４】
2005284111.tif 000006
【００４０】
ｍ＝４の場合は、
Ａ＝（ａ1 ，ａ2 ，ａ3 ，ａ4 ）                      
Ｂ＝（ｂ1 ，ｂ2 ，ｂ3 ，ｂ4 ）                      
Ｃ＝Ａ・Ｂ＝（ｃ1 ，ｃ2 ，ｃ3 ，ｃ4 ）
であり、乗算アルゴリズムは次式で与えられる。
【００４１】
ｑ0 ＝（ａ1 −ａ4 ）（ｂ1 −ｂ4 ）＋（ａ2 −ａ3 ）（ｂ2 −ｂ3 ）
ｃ1 ＝ｑ0 −（ａ2 −ａ4 ）（ｂ2 −ｂ4 ）−ａ1 ｂ1 
ｃ2 ＝ｑ0 −（ａ3 −ｂ4 ）（ｂ3 −ｂ4 ）−ａ2 ｂ2 
ｃ3 ＝ｑ0 −（ａ1 −ａ2 ）（ｂ1 −ｂ2 ）−ａ3 ｂ3 
ｃ4 ＝ｑ0 −（ａ1 −ａ3 ）（ｂ1 −ｂ3 ）−ａ4 ｂ4 
一方、本発明では、次のような基底が用いられる。
【００４２】
（β1 ，β2 ）≡（ω1 ，ω2 ，ω-2，ω-1）＝（ω1 ，ω2 ，ω3 ，ω4 ）
２ｍ＝４のとき、任意元は、ωの基底を用いて次のように表わされる。
Ａ＝（ａ1 ，ａ2 ，ａ2 ，ａ1 ）                      
Ｂ＝（ｂ1 ，ｂ2 ，ｂ2 ，ｂ1 ）                      
Ｃ＝Ａ・Ｂ＝（ｃ1 ，ｃ2 ，ｃ2 ，ｃ1 ）
これにより、乗算アルゴリズムは、
ｑ0 ＝（ａ1 −ａ1 ）（ｂ1 −ｂ1 ）＋（ａ2 −ａ2 ）（ｂ2 −ｂ2 ）＝０
ｃ1 ＝−（ａ2 −ａ1 ）（ｂ2 −ｂ1 ）−ａ1 ｂ1 
ｃ2 ＝− (ａ2 −ａ1 ）（ｂ2 −ｂ1 ）−ａ2 ｂ2 
ｃ2 ＝−（ａ1 −ａ2 ）（ｂ1 −ｂ2 ）−ａ2 ｂ2 
ｃ1 ＝−（ａ1 −ａ2 ）（ｂ1 −ｂ2 ）−ａ1 ｂ1 
となり、ｑ0 ＝０  になるとともに、ｃ1 ，ｃ2 ，ｃ3 ，ｃ4   を求める各式間に、〔（ａ2 −ａ1 ）（ｂ2 −ｂ1 ）〕や〔ａ1 ｂ1 〕、〔ａ2 ｂ2 〕などの多数の共通演算項が生まれるので、演算を簡単化できる。
【００４３】
図２は、本発明の基底を用いてＣＶＭＡ法による２元の乗算Ａ・Ｂ＝Ｃを演算する場合の、簡単化された乗算装置の実施例構成を示す。また、２元の入力データＡ，Ｂと乗算結果の出力データＣは、それぞれ１１，１２，１３で示される。
Ａ＝（ａ1 ，ａ2 ，ａ2 ，ａ1 ）                      
Ｂ＝（ｂ1 ，ｂ2 ，ｂ2 ，ｂ1 ）                      
Ｃ＝Ａ・Ｂ＝（ｃ1 ，ｃ2 ，ｃ2 ，ｃ1 ）
【００４４】
乗算装置１４は、上記の簡単化された乗算アルゴリズムに基づいて構成されており、ｃ1 〜ｃ4 の各要素を演算するｃ1 演算部１５、ｃ2 演算部１６、ｃ3 演算部１７、ｃ4 演算部１８と、演算結果の合成出力部１９が設けられている。また、ｃ1 〜ｃ4 の各演算部１５〜１８間には、共通の演算項目についての他の演算部による演算結果を共有するためのパスが設けられている。たとえば乗算装置１４がソフトウエアで構成されている場合には、たとえば、ｃ1 ，ｃ2 ，ｃ3 ，ｃ4 の順に演算の優先順序が定められてるものとすると、まずｃ1 演算部１５が（ａ2 −ａ1 ）（ｂ2 −ｂ1 ）と−ａ1 ｂ1 の演算項目を計算すると、それぞれの演算結果はメモリに保存され、他の演算部によって読み取り可能にする。同様に他の演算部においても、下位の演算に用いられる共通の演算項目について演算したときは、その演算結果をメモリに保存して他の演算部による読み取りを可能にする。また乗算装置１４がハードウエア回路で構成されている場合には、演算項目を共有する演算部同士間に、レジスタを介してのデータ転送バスが設けられる。
【００４５】
表１に、従来法と本発明方法の演算量の比較を示す。特に加算の演算回数の削減が行われていることが分かる。
【００４６】
【表１】
2005284111.tif 000007
【図面の簡単な説明】
【００４７】
【図１】本発明を適用した暗号通信システムの概要図である。
【図２】本発明の基底を用いてＣＶＭＡ法により簡単化された乗算装置の実施例構成図である。
【符号の説明】
【００４８】
１１：入力データＡ
１２：入力データＢ
１３：出力データＣ
１４：乗算装置
１５：ｃ1 演算部
１６：ｃ2 演算部
１７：ｃ3 演算部
１８：ｃ4 演算部
１９：合成出力部
【図１】
2005284111.tif 000008
【図２】
2005284111.tif 000009