(57)【要約】  【目的】情報セキュリテイ技術としての暗号技術に関するものであり，特に，有限群上の離散対数問題を用いて実現する鍵共有，暗号及びデジタル署名技術に関するものであり，有限群上の離散対数問題ベースの暗号技術に対する解読である．サイドチャネル攻撃に対して安全なべき演算を実現することにより，安全な有限群上の離散対数に基づく鍵共有，暗号，署名方法を提供することを目的とする.【構成】Step 1. 楕円曲線 E(Fq),E(Fq) の元 G とビット数nを入力Step 2. dとその二進表記d =d[n-1]2^(n-1)+ ・・・+ d[1]2 + d[0]を入力Step 3. E(Fq) の元R をとる．Step 4.  Z = G-R とする．Step ５.  Y = R, Z = G-R とする．Step ６から７までが第二の演算部に相当する．Step ６.  i = n-1 とする．Step ７.  i ≧ 0Step ８. Y = Y-R を計算Step ９. Y を出力する．  【効果】安全かつ高速性，メモリ性に関してフレキシブルなべき演算の構成方法を与える．【選択図】図６
2006078943.tif 000002
【特許請求の範囲】
【請求項１】
有限群をEとし，E上の群演算を加法的に表し，Eの元をG とし，nビットのデータdとその二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とするとき，
これら E, Gを第一のメモリ部に格納し，dとその二進表現を第二のメモリ部に格納し， 
乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと第一のメモリ部の元Gを入力してQ=G-Rを求め，初期値設定部に第一の演算部の出力Q，上記元Rを入力し，Q，R，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力であるQ, R, Y と第二のメモリ部に格納されているdの二進表現d[i]を入力し，i=n-1 から 0 まで以下の演算を順次行い，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法．
【請求項２】
請求項１記載のべき演算方法を適用したべき演算装置．
【請求項３】
請求項１記載の方法を実行するプログラムを記憶した記録媒体．
【請求項４】
請求項１記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式．
【請求項５】
請求項１記載のべき演算方法を，pを素数，r を正整数，qを q=p^r となる整数とし，q個の元をもつ有限体Fq上の楕円曲線E，E(Fq)上の元 G とnビットのデータdに対し，楕円曲線上のべき演算
dG の計算に利用することを特徴とするべき演算方法．
【請求項６】
請求項１記載のべき演算方法を，pを素数，r を正整数，qを q=p^r となる整数とし，q個の元をもつ有限体Fq上の超楕円曲線H，H(Fq)上の元 G とnビットのデータdに対し，超楕円曲線上のべき演算
dG の計算に利用することを特徴とするべき演算方法．
【請求項７】
有限群をEとし，E上の群演算を加法的に表し，Eの元をG とし，nビットのデータdとその二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とするとき，
これら E, Gを格納する第一のメモリ部と，
これら dとその二進表現を格納する第二のメモリ部とを有し
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと第一のメモリ部の元Gを入力としてQ=G-Rを求める第一の演算部と，
上記元Rと第一の演算部の出力Qを入力として，R, Q, Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力Y,R,Qと第二のメモリ部に格納されたdの二進表現｛d[i]｝を入力として，i=n-1 から 0 まで，以下の演算，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
を順次ループ処理する第二の演算部と
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置．
【請求項８】
有限群をEとし，E上の群演算を加法的に表し，Eの元をG とし， これら E, Gを第一のメモリ部に格納し，
第一の乱数発生部により，nビットのデータdを生成し，その二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とし，
第二の乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと第一のメモリ部の元Gを入力してQ=G-Rを求め，初期値設定部に第一の演算部の出力Q，上記元Rを入力し，Q，R，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力であるQ, R, Y と上記dの二進表現d[i]を入力し，i=n-1 から 0 まで以下の演算を順次行い，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法．
【請求項９】
請求項８記載のべき演算方法を適用したべき演算装置．
【請求項１０】
請求項８記載の方法を実行するプログラムを記憶した記録媒体．
【請求項１１】
請求項８記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式．
【請求項１２】
有限群をEとし，E上の群演算を加法的に表し，Eの元をG とし， 
これら E, Gを格納する第一のメモリ部と，
nビットのデータdを生成する第一の乱数発生部と，ここでdの二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とし，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと第一のメモリ部の元Gを入力としてQ=G-Rを求める第一の演算部と，
上記元Rと第一の演算部の出力Qを入力として，R, Q, Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力Y,R,Qと上記dの二進表現｛d[i]｝を入力として，i=n-1 から 0 まで，以下の演算，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
を順次ループ処理する第二の演算部と
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置．
【請求項１３】
有限群をEとし，E上の群演算を加法的に表し，Eを第一のメモリ部に格納し，
入力部にEの元Gを入力し， 
第一の乱数発生部により，nビットのデータdを生成し，その二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とし，
第二の乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと上記入力の元Gを入力してQ=G-Rを求め，初期値設定部に第一の演算部の出力Q，上記元Rを入力し，Q，R，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力であるQ, R, Y と上記dの二進表現d[i]を入力し，i=n-1 から 0 まで以下の演算を順次行い，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法．
【請求項１４】
請求項１３記載のべき演算方法を適用したべき演算装置．
【請求項１５】
請求項１３記載の方法を実行するプログラムを記憶した記録媒体．
【請求項１６】
請求項１３記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式．
【請求項１７】
有限群をEとし，E上の群演算を加法的に表し，Eを格納する第一のメモリ部と，
有限群Eの元Gを入力する入力部と，
nビットのデータdを生成する第一の乱数発生部と，ここでdの二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とし，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと上記入力元Gを入力としてQ=G-Rを求める第一の演算部と，
上記元Rと第一の演算部の出力Qを入力として，R, Q, Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力Y,R,Qと上記dの二進表現｛d[i]｝を入力として，i=n-1 から 0 まで，以下の演算，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
を順次ループ処理する第二の演算部と
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置．
【請求項１８】
有限群をEとし，E上の群演算を加法的に表し，nビットのデータdとその二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とするとき，
Eを第一のメモリ部に格納し，
dとその二進表現を第二のメモリ部に格納し， 
入力部にEの元Gを入力し，  
乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと上記入力の元Gを入力してQ=G-Rを求め，初期値設定部に第一の演算部の出力Q，上記元Rを入力し，Q，R，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力であるQ, R, Y と第二のメモリ部に格納されているdの二進表現d[i]を入力し，i=n-1 から 0 まで以下の演算を順次行い，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法．
【請求項１９】
請求項１８記載のべき演算方法を適用したべき演算装置．
【請求項２０】
請求項１８記載の方法を実行するプログラムを記憶した記録媒体．
【請求項２１】
請求項１８記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式．
【請求項２２】
有限群をEとし，E上の群演算を加法的に表し，nビットのデータdとその二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とするとき，
Eを格納する第一のメモリ部と，
dとその二進表現を格納する第二のメモリ部とを有し
有限群Eの元Gを入力する入力部と，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと上記入力元Gを入力としてQ=G-Rを求める第一の演算部と，
上記元Rと第一の演算部の出力Qを入力として，R, Q, Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力Y,R,Qと第二のメモリ部に格納されたdの二進表現｛d[i]｝を入力として，i=n-1 から 0 まで，以下の演算，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
を順次ループ処理する第二の演算部と
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置．
【請求項２３】
有限群をEとし，E上の群演算を加法的に表し，Eの元をG ，nビットのデータをd，分割数をt(<n), t とnとの最小公倍数をn’=kt とし，
d のn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+
d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
これらE，G，k，n，t，n’を第一のメモリ部に格納し， 
上記データdとその二進表現{d[i](i=0,..,2^n’-1)},
kビットのデータ{a[j](j=0, ..., t-1)} を第二のメモリ部に格納し，
乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと第一のメモリ部の元G, k を入力し，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]を用いて（各b[i]は0 か1），
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求め，
上記元{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}を出力し，
初期値設定部に第一の演算部の出力{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，
上記元Rを入力し，{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力である{G[0],…,G[t-1]}，{T[0],..,T[2^t-1]}, Y と第二のメモリ部に格納されているdの二進表現{d[i]}を入力し，
i=k-1 から
0 まで以下の演算を順次行い，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法．
【請求項２４】
請求項２３記載のべき演算方法を適用したべき演算装置．
【請求項２５】
請求項２３記載の方法を実行するプログラムを記憶した記録媒体．
【請求項２６】
請求項２３記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式．
【請求項２７】
請求項２３記載のべき演算方法を，pを素数，r を正整数，qを q=p^r となる整数とし，q個の元をもつ有限体Fq上の楕円曲線E，E(Fq)上の元 G とnビットのデータdに対し，楕円曲線上のべき演算
dG の計算に利用することを特徴とするべき演算方法．
【請求項２８】
請求項２３記載のべき演算方法を，pを素数，r を正整数，qを q=p^r となる整数とし，q個の元をもつ有限体Fq上の超楕円曲線H，H(Fq)上の元 G とnビットのデータdに対し，超楕円曲線上のべき演算
dG の計算に利用することを特徴とするべき演算方法．
【請求項２９】
有限群をEとし，E上の群演算を加法的に表し，Eの元 G とnビットのデータd，分割数をt(<n), t とnの最小公倍数をn’=kt とし，
d のn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+
d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・ +d[kj+1]・2+ d[kj]
と表記し，
これらE，G，k，n，t，n’を格納する第一のメモリ部と，
これらdとその二進表現，及びkビットのデータ{a[j]}を格納する第二のメモリ部を有し，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと第一のメモリ部の元G，kを入力として，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
次に上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]（各b[i]は0 か1）を用いて，
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求める第一の演算部と，
上記元Rと第一の演算部の出力{G[0],..,G[t-1]}と{T[0],..,T[2^t-1]}を入
力として，{G[0],..,G[t-1]}，{T[0],..,T[2^t-1]},
Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力{G[0],…,G[t-1]}，   {T[0],..,T[2^t-1]},
Y と第二のメモリ部に格納されているdの二進表現{d[i]}を入力として，
i=k-1 から 0 まで以下の演算，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1
を順次ループ処理する第二の演算部と，
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置．
【請求項３０】
有限群をEとし，E上の群演算を加法的に表し，Eの元をG，ビット数をn，分割数をt(<n), t とnとの最小公倍数をn’=kt とし，
これらE，G，k，n，t，n’を第一のメモリ部に格納し，
第一の乱数発生部により，nビットのデータdを生成し，そのn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+ d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
第二の乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと第一のメモリ部の元G, k を入力し，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]を用いて（各b[i]は0 か1），
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求め，
上記元{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}を出力し，
初期値設定部に第一の演算部の出力{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，
上記元Rを入力し，{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力である{G[0],…,G[t-1]}，{T[0],..,T[2^t-1]}, Y と上記dの二進表現{d[i]}を入力し，
i=k-1 から 0 まで以下の演算を順次行い，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法．
【請求項３１】
請求項３０記載のべき演算方法を適用したべき演算装置．
【請求項３２】
請求項３０記載の方法を実行するプログラムを記憶した記録媒体．
【請求項３３】
請求項３０記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式．
【請求項３４】
有限群をEとし，E上の群演算を加法的に表し，Eの元をG，ビット数をn，分割数をt(<n), t とnとの最小公倍数をn’=kt とし，
これらE，G，k，n，t，n’を格納する第一のメモリ部と，
nビットのデータdを生成する第一の乱数発生部と，ここでdのn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+ d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと第一のメモリ部の元G，kを入力として，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
次に上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]（各b[i]は0 か1）を用いて，
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求める第一の演算部と，
上記元Rと第一の演算部の出力{G[0],..,G[t-1]}と{T[0],..,T[2^t-1]}を入
力として，{G[0],..,G[t-1]}，{T[0],..,T[2^t-1]},
Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力{G[0],…,G[t-1]}，   {T[0],..,T[2^t-1]}, Y と上記dの二進表現{d[i]}を入力として，
i=k-1 から 0 まで以下の演算，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1
を順次ループ処理する第二の演算部と，
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置．
【請求項３５】
有限群をEとし，E上の群演算を加法的に表し，ビット数をn，分割数をt(<n), t とnとの最小公倍数をn’=kt とし，
これらE，k，n，t，n’を第一のメモリ部に格納し，
入力部にEの元Gを入力し， 
第一の乱数発生部により，nビットのデータdを生成し，そのn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+ d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
第二の乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと上記入力元Gと第一のメモリ部のk を入力し，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現
b = b[t-1]・2^(t-1) + ・・・+ b[0]を用いて（各b[i]は0
か1），
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求め，
上記元{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}を出力し，
初期値設定部に第一の演算部の出力{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，
上記元Rを入力し，{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力である{G[0],…,G[t-1]}，{T[0],..,T[2^t-1]}, Y と上記dの二進表現{d[i]}を入力し，
i=k-1 から 0 まで以下の演算を順次行い，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法．
【請求項３６】
請求項３５記載のべき演算方法を適用したべき演算装置．
【請求項３７】
請求項３５記載の方法を実行するプログラムを記憶した記録媒体．
【請求項３８】
請求項３５記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式．
【請求項３９】
有限群をEとし，E上の群演算を加法的に表し，ビット数をn，分割数をt(<n), t とnとの最小公倍数をn’=kt とし，
これらE，k，n，t，n’を入力として格納する第一のメモリ部と，
有限群Eの元Gを入力する入力部と，
nビットのデータdを生成する第一の乱数発生部と，ここでdのn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+ d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと上記入力元G，第一のメモリ部のkを入力として，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
次に上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]（各b[i]は0 か1）を用いて，
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求める第一の演算部と，
上記元Rと第一の演算部の出力{G[0],..,G[t-1]}と{T[0],..,T[2^t-1]}を入
力として，{G[0],..,G[t-1]}，{T[0],..,T[2^t-1]},
Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力{G[0],…,G[t-1]}，   {T[0],..,T[2^t-1]}, Y と上記dの二進表現{d[i]}を入力として，
i=k-1 から 0 まで以下の演算，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1
を順次ループ処理する第二の演算部と，
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置．
【請求項４０】
有限群をEとし，E上の群演算を加法的に表し，nビットのデータをd，分割数をt(<n), t とnとの最小公倍数をn’=kt とし，
d のn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+
d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
これらE，k，n，t，n’を第一のメモリ部に格納し， 
上記データdとその二進表現{d[i](i=0,..,2^n’-1)}, kビットのデータ{a[j](j=0, ..., t-1)} を第二のメモリ部に格納し， 
入力部にEの元Gを入力し， 
乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと上記入力元Gと第一のメモリ部のk を入力し，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現
b = b[t-1]・2^(t-1) + ・・・+ b[0]を用いて（各b[i]は0
か1），
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求め，
上記元{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}を出力し，
初期値設定部に第一の演算部の出力{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，
上記元Rを入力し，{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力である{G[0],…,G[t-1]}，{T[0],..,T[2^t-1]}, Y と第二のメモリ部に格納されている{d[i]}を入力し，
i=k-1 から 0 まで以下の演算を順次行い，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法．
【請求項４１】
請求項４０記載のべき演算方法を適用したべき演算装置．
【請求項４２】
請求項４０記載の方法を実行するプログラムを記憶した記録媒体．
【請求項４３】
請求項４０記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式．
【請求項４４】
有限群をEとし，E上の群演算を加法的に表し，nビットのデータd，分割数をt(<n), t とnの最小公倍数をn’=kt とし，
d のn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+
d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・ +d[kj+1]・2+ d[kj]
と表記し，
これらE，k，n，t，n’を入力として格納する第一のメモリ部と，
これらdとその二進表現，及びkビットのデータ{a[j]}を格納する第二のメモリ部を有し，
有限群Eの元Gを入力する入力部と，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと上記入力元G，第一のメモリ部のkを入力として，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
次に上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]（各b[i]は0 か1）を用いて，
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求める第一の演算部と，
上記元Rと第一の演算部の出力{G[0],..,G[t-1]}と{T[0],..,T[2^t-1]}を入
力として，{G[0],..,G[t-1]}，{T[0],..,T[2^t-1]},
Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力{G[0],…,G[t-1]}，   {T[0],..,T[2^t-1]}, Y と上記dの二進表現{d[i]}を入力として，
i=k-1 から 0 まで以下の演算，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1
を順次ループ処理する第二の演算部と，
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置．
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報セキュリテイ技術としての暗号技術に関するものであり，特に，楕円曲線，超楕円曲線上の離散対数問題を用いて実現する鍵共有，暗号及びデジタル署名技術に関するものである.
【背景技術】
【０００２】
秘密通信方式とは，特定の通信相手以外に通信内容を漏らすことなく通信を行なう技術である．またデジタル署名方式とは，通信相手に通信内容の正当性を証明する技術である．この応用として認証方式があり，これは通信相手(機器)に，正しいユーザあるいは機器であることを保証する技術である．これらの技術は，公開鍵暗号系とよばれる暗号方式で実現できる．公開鍵暗号は通信相手が多数の時，通信相手ごとに異なる暗号鍵を容易に管理するための方式であり，多数の通信相手と通信を行なうのに不可欠な基盤技術である.簡単に説明すると，これは暗号鍵と復号鍵が異なり，復号鍵は秘密にするが，暗号鍵を公開する方式である.この公開鍵暗号の安全性の根拠に用いられるものに有限群を利用した離散対数問題がある．離散対数問題が定義される有限群として，有限体，有限体上の楕円曲線，有限体上の超楕円曲線などがある．特に，よく利用されるのが有限体上の楕円曲線上の離散対数問題である.これはニイルコブリッツ著  ”ア  コウス  イン  ナンバア  セオリイ  アンド  クリプトグラヒイ”(Neal
Koblitz , " A Course in Number theory and 
Cryptography", Spinger-Verlag,1987)に詳しく述べられている.
楕円曲線上の離散対数問題（ECDLP）を以下に述べる.
【０００３】
ECDLP
E(Fp）を有限体 Fp 上定義された楕円曲線Eとし，Eの位数が大きな素数で割れる元Gをベースポイントとする.このとき，Eの与えられた元Ｙに対して，
Y=xG
となる整数xが存在するならばxを求めよ.
【０００４】
有限群上の離散対数問題を利用した技術に，公開鍵暗号，ディジタル署名，鍵共有などがある．ここでは簡単のために，有限群上の演算を加法で表記する．このときどの技術も，有限群の元Gと秘密のデータdとのべき演算，すなわち dG = G+ ・・・+G の演算を必要とし，さらにその安全性はdG 及び G の結果からd が容易に求められないことに帰着する．これがいわゆる離散対数問題である．一般に，離散対数問題の安全性は数学的問題であり，計算量的に多項式時間で解読するアルゴリズムが古くから研究されている．離散対数問題は，その研究の歴史にも関わらず，多項式時間のアルゴリズムが発見されていないことに高い安全性及び信頼性が置かれてきた．ところが，近年，dGを計算するICカードなどの消費電力を測ることにより，その軽微な情報を利用して，実際にdを求めるサイドチャネル攻撃が提案された．サイドチャネル攻撃は，消費電力の測定以外の特殊な機械を仮定せず，測定した消費電力を利用してアルゴリズム的に解読する攻撃であり，実質的な意味で脅威といえる．サイドチャネル攻撃は，離散対数問題に基づく方式の基本演算であるべき演算
dG の計算を IC カードで行うときに観測される消費電力を測定し，dの値を推測する攻撃である．べき演算は，加算 G+G と2倍算 2G の二つの演算の繰り返しで実現され，加算と
2 倍算の電力消費量の違いがサイドチャネル攻撃の大きな原因となる．サイドチャネル攻撃につては，以下の論文が詳しい．
J. Coron, "Resistance against differential power analysis for
elliptic curve cryptosystem", CHES'99, Lecture Notes in Computer Science,
1717(1999), Springer-Verlag, 292--302.
【０００５】
サイドチャネル攻撃は，単純消費電力解析(SPA), 差分消費電力解析(DPA)と呼ばれる２種類の攻撃からなる．SPA は，dG の処理が鍵 d に依存して消費電力の違いを生むことを利用する攻撃で，一回の消費電力の測定により鍵を推測する．一方，DPAは，攻撃者が適応的に異なる
G の値をICカードに入力し，その処理に掛かる消費電力量を測定し，その違いにより鍵を推測する．耐 SPA アルゴリズムとしては，鍵 d に依存せずにべき演算が実現される加算連鎖を構築すればよいが，低速となる問題がある．耐
DPA アルゴリズムとしては，dG の演算の度に異なる消費電力を出力するように加算連鎖を構築するとよいが，耐SPAアルゴリズムと同様，低速になるという問題をもつ．
これら耐SPA，DPAアルゴリズムに関しては以下の論文が詳しい．
M. Joye and C. Tymen, "Protections against Differential Analysis
for Elliptic Curve Cryptosystem", CHES2001, Lecture Notes in Computer
Science, 2162(2001), Springer-Verlag, 377--390.
【０００６】
2003年にDPA 攻撃を改良したゼロ値攻撃が提案された．これは，攻撃者が楕円曲線の点
G の x, y の2座標のどちらかが 0 になるように入力を操作し，ゼロ値の消費電力量が区別できることを利用した攻撃である．上記の2001年の論文で提案されている耐
DPA アルゴリズムは，ゼロ値を固定するため，ゼロ値攻撃には弱い．2004年に，ゼロ値攻撃に対して強力になるアルゴリズムが提案された．この方法は，dGを計算する際に，任意の楕円曲線の元Rを用い，Y=
dG + Rを最下位ビットから計算し，その結果から Y=Y-Rを求めることで，dGを求める方法である．任意のRがdGの計算の度に加えられるため，攻撃者がｄGの計算途中にゼロ値が生成されるように操作できない．この耐ゼロ値攻撃アルゴリズムについては以下の論文が詳しい．
K. Itoh, T. Izu, and M. Takenaka,  "Efficient countermeasures against power analysis for
elliptic curve cryptosystems", SCIS2004, 2004 (previous version).
【０００７】
以下に，上記の耐ゼロ値攻撃アルゴリズムを従来例としてあげる．
従来例１
図８
は従来例である耐ゼロ値攻撃アルゴリズムをしめすものである．以下同図を参照しながら従来例の手順を説明する．
Step1. 楕円曲線 E(Fq),
E(Fq) の元 G と n ビットの元ｄ を入力
有限体 FqとFq上の楕円曲線E，E(Fq)の元Gを入力する．
【０００８】
Step2. dの二進表記を
d = d[n-1]2^(n-1)+ ・・・+ d[1]2 + d[0] とする．
nビットのデータdを二進で表記する．このとき，各d[n-1],…,d[0]は0または1である．
【０００９】
Step3. E(Fq) の元R をとる．
【００１０】
Step4. Y = R, Z = G, U
= Oとする．
dG+Rを最下位ビット（LSB）より計算するために初期値Y=R,
Z=G, U=Oを設定する．ここで，Oは楕円曲線の零元である．
【００１１】
Step 5.  i = 0 とする．
dG+Rを最下位ビット（LSB）より計算するためのカウンタiを0に設定する．
【００１２】
Step 6.  i ≦ n-1
まず，U = Y+Z, Z=2Z を計算し，次にd[i]の値に応じて以下の演算，          Y=U
(d[i]=1のとき), Y=Y (d[i]=0のとき)，
を行い，iを１だけ増やし，step 6の判定を行う．
【００１３】
Step 7. Y = Y-R を計算
【００１４】
Step 8. Y を出力する．
Step 6 で dY+R
が求められ，step 7 でその結果からRを減算した結果がYに入力されるので，出力値のYはべき演算dGの結果となる．
【００１５】
上記従来例では，dG+R の計算を最下位ビット（LSB）から実現するため，必要となる中間変数の量が多くなる．特に，ICカードのような小メモリが要求される媒体では，実装に必要になる変数量は小さいことが望ましい．逆に，高速に実行したい場合，予備計算テーブルなどを利用し，実行速度の高速化を図る必要がある．しかしながら，従来例のように最下位ビットからのアルゴリズムでは，予備計算テーブルなどで高速化を図ることが困難であり，これ以上の高速化が見込めないという問題がある．
【非特許文献１】ニイルコブリッツ著  ”ア  コウス  イン  ナンバア  セオリイ  アンド  クリプトグラヒイ”(NealKoblitz , " A Course in Number theory and Cryptography",Spinger-Verlag,1987)に詳しく述べられている.
【非特許文献２】M. Joye and C. Tymen, "Protections againstDifferential Analysis for Elliptic Curve Cryptosystem", CHES2001, LectureNotes in Computer Science, 2162(2001), Springer-Verlag, 377--390.
【非特許文献３】K. Itoh, T. Izu, and M. Takenaka,  "Efficient countermeasures againstpower analysis for elliptic curve cryptosystems", SCIS2004, 2004.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
公開鍵暗号を用いた暗号方式，鍵共有方式，署名方式では，攻撃に対して，可能な限り強力に実現することが必須である．離散対数問題に基づく暗号は，その安全性を離散対数問題のベースとなる有限群E上の元をGとし，秘密のデータをdとするとき，dG とGの値からdを推測することが困難であることに帰着する．近年，ICカードなどの上でdGの実装をする際にその消費電力を測定することで，dの値を推測するサイドチャネル攻撃が大きな脅威となっている．特に，この演算は，暗号，鍵共有，署名の全てで利用されるため，その攻撃のインパクトは非常に大きい．このため，サイドチャネル攻撃に強力な実装方法は必須といえる．ICカードの上での実装において重要なのは，安全性とともに，メモリサイズ及び実行速度である．つまり，小メモリが要求される状況においては，小メモリで実現できる実装が，また高速性が要求される状況においては，高速に実現できる実装方法が必須といえる．
【００１７】
このことからも，サイドチャネル攻撃に対して強力かつ，メモリサイズ，実行速度に対してフレキシブルに実現できるべき演算アルゴリズムは必須といえる．しかし従来例にみるように，LSBからのべき演算の実装アルゴリズムでは，必要になる有限群Eの元を格納する中間変数の量が最低でも４つ必要となり，また，テーブルなどを利用した高速化ができない問題がある．
【００１８】
本発明は，この従来例における問題点を鑑みて行なわれたもので，サイドチャネル攻撃に強力なべき演算を，メモリサイズ及び実行速度に関してフレキシブルに実現することで，安全な有限群上の離散対数問題に基づく鍵共有，暗号，署名方式を提供することを目的とする.
【課題を解決するための手段】
【００１９】
本発明は上述の問題点を解決するため，
請求項１では，有限群をEとし，E上の群演算を加法的に表し，Eの元をG
とし，nビットのデータdとその二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とするとき，
これら E, Gを第一のメモリ部に格納し，dとその二進表現を第二のメモリ部に格納し， 
乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと第一のメモリ部の元Gを入力してQ=G-Rを求め，初期値設定部に第一の演算部の出力Q，上記元Rを入力し，Q，R，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力であるQ, R, Y と第二のメモリ部に格納されているdの二進表現d[i]を入力し，i=n-1 から 0 まで以下の演算を順次行い，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法としている．
【００２０】
請求項２では，請求項１記載のべき演算方法を適用したべき演算装置としている．
【００２１】
請求項３では，請求項１記載の方法を実行するプログラムを記憶した記録媒体としている．
【００２２】
請求項４では，請求項１記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式としている．
【００２３】
請求項５では，請求項１記載のべき演算方法を，pを素数，r を正整数，qを q=p^r となる整数とし，q個の元をもつ有限体Fq上の楕円曲線E，E(Fq)上の元 G とnビットのデータdに対し，楕円曲線上のべき演算
dG の計算に利用することを特徴とするべき演算方法としている．
【００２４】
請求項６では，請求項１記載のべき演算方法を，pを素数，r を正整数，qを
q=p^r となる整数とし，q個の元をもつ有限体Fq上の超楕円曲線H，H(Fq)上の元 G とnビットのデータdに対し，超楕円曲線上のべき演算 dG の計算に利用することを特徴とするべき演算方法としている．
【００２５】
請求項７では，有限群をEとし，E上の群演算を加法的に表し，Eの元をG とし，nビットのデータdとその二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とするとき，
これら E, Gを格納する第一のメモリ部と，
これら dとその二進表現を格納する第二のメモリ部とを有し
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと第一のメモリ部の元Gを入力としてQ=G-Rを求める第一の演算部と，
上記元Rと第一の演算部の出力Qを入力として，R, Q, Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力Y,R,Qと第二のメモリ部に格納されたdの二進表現｛d[i]｝を入力として，i=n-1 から 0 まで，以下の演算，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
を順次ループ処理する第二の演算部と
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置としている．
【００２６】
請求項８では，有限群をEとし，E上の群演算を加法的に表し，Eの元をG とし， これら E, Gを第一のメモリ部に格納し，
第一の乱数発生部により，nビットのデータdを生成し，その二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とし，
第二の乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと第一のメモリ部の元Gを入力してQ=G-Rを求め，初期値設定部に第一の演算部の出力Q，上記元Rを入力し，Q，R，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力であるQ, R, Y と上記dの二進表現d[i]を入力し，i=n-1 から 0 まで以下の演算を順次行い，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法としている．
【００２７】
請求項９では，請求項８記載のべき演算方法を適用したべき演算装置としている．
【００２８】
請求項１０では，請求項８記載の方法を実行するプログラムを記憶した記録媒体としている．
【００２９】
請求項１１では，請求項８記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式としている．
【００３０】
請求項１２では，有限群をEとし，E上の群演算を加法的に表し，Eの元をG とし， 
これら E, Gを格納する第一のメモリ部と，
nビットのデータdを生成する第一の乱数発生部と，ここでdの二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とし，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと第一のメモリ部の元Gを入力としてQ=G-Rを求める第一の演算部と，
上記元Rと第一の演算部の出力Qを入力として，R, Q, Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力Y,R,Qと上記dの二進表現｛d[i]｝を入力として，i=n-1 から 0 まで，以下の演算，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
を順次ループ処理する第二の演算部と
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置としている．
【００３１】
請求項１３では，有限群をEとし，E上の群演算を加法的に表し，Eを第一のメモリ部に格納し，
入力部にEの元Gを入力し， 
第一の乱数発生部により，nビットのデータdを生成し，その二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とし，
第二の乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと上記入力の元Gを入力してQ=G-Rを求め，初期値設定部に第一の演算部の出力Q，上記元Rを入力し，Q，R，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力であるQ, R, Y と上記dの二進表現d[i]を入力し，i=n-1 から 0 まで以下の演算を順次行い，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法としている．
【００３２】
請求項１４では，請求項１３記載のべき演算方法を適用したべき演算装置としている．
【００３３】
請求項１５では，請求項１３記載の方法を実行するプログラムを記憶した記録媒体としている．
【００３４】
請求項１６では，請求項１３記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式としている．
【００３５】
請求項１７では，有限群をEとし，E上の群演算を加法的に表し，Eを格納する第一のメモリ部と，
有限群Eの元Gを入力する入力部と，
nビットのデータdを生成する第一の乱数発生部と，ここでdの二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とし，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと上記入力元Gを入力としてQ=G-Rを求める第一の演算部と，
上記元Rと第一の演算部の出力Qを入力として，R, Q, Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力Y,R,Qと上記dの二進表現｛d[i]｝を入力として，i=n-1 から 0 まで，以下の演算，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
を順次ループ処理する第二の演算部と
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置としている．
【００３６】
請求項１８では，有限群をEとし，E上の群演算を加法的に表し，nビットのデータdとその二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とするとき，
Eを第一のメモリ部に格納し，
dとその二進表現を第二のメモリ部に格納し， 
入力部にEの元Gを入力し，  
乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと上記入力の元Gを入力してQ=G-Rを求め，初期値設定部に第一の演算部の出力Q，上記元Rを入力し，Q，R，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力であるQ, R, Y と第二のメモリ部に格納されているdの二進表現d[i]を入力し，i=n-1 から 0 まで以下の演算を順次行い，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法としている．
【００３７】
請求項１９では，請求項１８記載のべき演算方法を適用したべき演算装置としている．
【００３８】
請求項２０では，請求項１８記載の方法を実行するプログラムを記憶した記録媒体としている．
【００３９】
請求項２１では，請求項１８記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式としている．
【００４０】
請求項２２では，有限群をEとし，E上の群演算を加法的に表し，nビットのデータdとその二進表現を
d = d[n-1]・2^(n-1)+…+d[1]・2+d[0]
(各d[i]= 0または 1)
とするとき，
Eを格納する第一のメモリ部と，
dとその二進表現を格納する第二のメモリ部とを有し
有限群Eの元Gを入力する入力部と，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと上記入力元Gを入力としてQ=G-Rを求める第一の演算部と，
上記元Rと第一の演算部の出力Qを入力として，R, Q, Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力Y,R,Qと第二のメモリ部に格納されたdの二進表現｛d[i]｝を入力として，i=n-1 から 0 まで，以下の演算，
Y = 2Y + Q ( d[i] = 1 の時)，
Y = 2Y + (-R)  ( d[i] = 0 の時)，
i = i-1，
を順次ループ処理する第二の演算部と
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置としている．
【００４１】
請求項２３では，有限群をEとし，E上の群演算を加法的に表し，Eの元をG ，nビットのデータをd，分割数をt(<n), t とnとの最小公倍数をn’=kt とし，
d のn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+
d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
これらE，G，k，n，t，n’を第一のメモリ部に格納し， 
上記データdとその二進表現{d[i](i=0,..,2^n’-1)},
kビットのデータ{a[j](j=0, ..., t-1)} を第二のメモリ部に格納し，
乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと第一のメモリ部の元G, k を入力し，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]を用いて（各b[i]は0 か1），
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求め，
上記元{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}を出力し，
初期値設定部に第一の演算部の出力{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，
上記元Rを入力し，{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力である{G[0],…,G[t-1]}，     {T[0],..,T[2^t-1]},
Y と第二のメモリ部に格納されているdの二進表
現{d[i]}を入力し，
i=k-1 から
0 まで以下の演算を順次行い，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法としている．
【００４２】
請求項２４では，請求項２３記載のべき演算方法を適用したべき演算装置としている．
【００４３】
請求項２５では，請求項２３記載の方法を実行するプログラムを記憶した記録媒体としている．
【００４４】
請求項２６では，請求項２３記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式としている．
【００４５】
請求項２７では，請求項２３記載のべき演算方法を，pを素数，r を正整数，qを q=p^r となる整数とし，q個の元をもつ有限体Fq上の楕円曲線E，E(Fq)上の元 G とnビットのデータdに対し，楕円曲線上のべき演算
dG の計算に利用することを特徴とするべき演算方法としている．
【００４６】
請求項２８では，請求項２３記載のべき演算方法を，pを素数，r を正整数，qを q=p^r となる整数とし，q個の元をもつ有限体Fq上の超楕円曲線H，H(Fq)上の元 G とnビットのデータdに対し，超楕円曲線上のべき演算
dG の計算に利用することを特徴とするべき演算方法としている．
【００４７】
請求項２９では，有限群をEとし，E上の群演算を加法的に表し，Eの元 G とnビットのデータd，分割数をt(<n), t とnの最小公倍数をn’=kt とし，
d のn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+
d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・ +d[kj+1]・2+ d[kj]
と表記し，
これらE，G，k，n，t，n’を格納する第一のメモリ部と，
これらdとその二進表現，及びkビットのデータ{a[j]}を格納する第二のメモリ部を有し，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと第一のメモリ部の元G，kを入力として，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
次に上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]（各b[i]は0 か1）を用いて，
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求める第一の演算部と，
上記元Rと第一の演算部の出力{G[0],..,G[t-1]}と{T[0],..,T[2^t-1]}を入
力として，{G[0],..,G[t-1]}，{T[0],..,T[2^t-1]},
Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力{G[0],…,G[t-1]}，   {T[0],..,T[2^t-1]},
Y と第二のメモリ部に格納されているdの二進表現{d[i]}を入力として，
i=k-1 から 0 まで以下の演算，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1
を順次ループ処理する第二の演算部と，
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置としている．
【００４８】
請求項３０では，有限群をEとし，E上の群演算を加法的に表し，Eの元をG，ビット数をn，分割数をt(<n),
t とnとの最小公倍数をn’=kt とし，
これらE，G，k，n，t，n’を第一のメモリ部に格納し，
第一の乱数発生部により，nビットのデータdを生成し，そのn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+ d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
第二の乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと第一のメモリ部の元G, k を入力し，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]を用いて（各b[i]は0 か1），
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求め，
上記元{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}を出力し，
初期値設定部に第一の演算部の出力{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，
上記元Rを入力し，{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力である{G[0],…,G[t-1]}，     {T[0],..,T[2^t-1]},
Y と上記dの二進表現{d[i]}を入力し，
i=k-1 から 0 まで以下の演算を順次行い，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法としている．
【００４９】
請求項３１では，請求項３０記載のべき演算方法を適用したべき演算装置としている．
【００５０】
請求項３２では，請求項３０記載の方法を実行するプログラムを記憶した記録媒体としている．
【００５１】
請求項３３では，請求項３０記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式としている．
【００５２】
請求項３４では，有限群をEとし，E上の群演算を加法的に表し，Eの元をG，ビット数をn，分割数をt(<n),
t とnとの最小公倍数をn’=kt とし，
これらE，G，k，n，t，n’を格納する第一のメモリ部と，
nビットのデータdを生成する第一の乱数発生部と，ここでdのn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+ d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと第一のメモリ部の元G，kを入力として，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
次に上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]（各b[i]は0 か1）を用いて，
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求める第一の演算部と，
上記元Rと第一の演算部の出力{G[0],..,G[t-1]}と{T[0],..,T[2^t-1]}を入
力として，{G[0],..,G[t-1]}，{T[0],..,T[2^t-1]},
Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力{G[0],…,G[t-1]}，   {T[0],..,T[2^t-1]}, Y と上記dの二進表現{d[i]}を入力として，
i=k-1 から 0 まで以下の演算，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1
を順次ループ処理する第二の演算部と，
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置としている．
【００５３】
請求項３５では，有限群をEとし，E上の群演算を加法的に表し，ビット数をn，分割数をt(<n),
t とnとの最小公倍数をn’=kt とし，
これらE，k，n，t，n’を第一のメモリ部に格納し，
入力部にEの元Gを入力し，
第一の乱数発生部により，nビットのデータdを生成し，そのn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+ d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
第二の乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと上記入力元Gと第一のメモリ部のk を入力し，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]を用いて（各b[i]は0 か1），
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求め，
上記元{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}を出力し，
初期値設定部に第一の演算部の出力{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，
上記元Rを入力し，{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力である{G[0],…,G[t-1]}，     {T[0],..,T[2^t-1]},
Y と上記dの二進表現{d[i]}を入力し，
i=k-1 から 0 まで以下の演算を順次行い，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法としている．
【００５４】
請求項３６では，請求項３５記載のべき演算方法を適用したべき演算装置としている．
【００５５】
請求項３７では，請求項３５記載の方法を実行するプログラムを記憶した記録媒体としている．
【００５６】
請求項３８では，請求項３５記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式としている．
【００５７】
請求項３９では，有限群をEとし，E上の群演算を加法的に表し，ビット数をn，分割数をt(<n),
t とnとの最小公倍数をn’=kt とし，
これらE，k，n，t，n’を入力として格納する第一のメモリ部と，
有限群Eの元Gを入力する入力部と，
nビットのデータdを生成する第一の乱数発生部と，ここでdのn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+ d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと上記入力元G，第一のメモリ部のkを入力として，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
次に上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]（各b[i]は0 か1）を用いて，
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求める第一の演算部と，
上記元Rと第一の演算部の出力{G[0],..,G[t-1]}と{T[0],..,T[2^t-1]}を入
力として，{G[0],..,G[t-1]}，{T[0],..,T[2^t-1]},
Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力{G[0],…,G[t-1]}，   {T[0],..,T[2^t-1]}, Y と上記dの二進表現{d[i]}を入力として，
i=k-1 から 0 まで以下の演算，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1
を順次ループ処理する第二の演算部と，
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置としている．
【００５８】
請求項４０では，有限群をEとし，E上の群演算を加法的に表し，nビットのデータをd，分割数をt(<n), t とnとの最小公倍数をn’=kt とし，
d のn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+ d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・+ d[kj]
と表記し，
これらE，k，n，t，n’を第一のメモリ部に格納し， 
上記データdとその二進表現{d[i](i=0,..,2^n’-1)}, kビットのデータ{a[j](j=0, ..., t-1)} を第二のメモリ部に格納し，
入力部にEの元Gを入力し， 
乱数発生部により，有限群Eの任意の元Rを生成し，
第一の演算部に，上記元Rと上記入力元Gと第一のメモリ部のk を入力し，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]を用いて（各b[i]は0 か1），
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求め，
上記元{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}を出力し，
初期値設定部に第一の演算部の出力{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，
上記元Rを入力し，{G[0],…,G[t-1]}と{T[0],..,T[2^t-1]}，Y=Rを出力し，
第二の演算部に上記初期値設定部の出力である{G[0],…,G[t-1]}，     {T[0],..,T[2^t-1]},
Y と第二のメモリ部に格納されている{d[i]}を入力し，
i=k-1 から 0 まで以下の演算を順次行い，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1，
第三の演算部に，第二の演算部の出力であるYと上記元Rを入力してY=Y-Rを求め，
第三の演算部の出力であるYを出力部によりべき演算dGの値として出力することを特徴とする有限群Eのべき演算方法としている．
【００５９】
請求項４１では，請求項４０記載のべき演算方法を適用したべき演算装置としている．
【００６０】
請求項４２では，請求項４０記載の方法を実行するプログラムを記憶した記録媒体としている．
【００６１】
請求項４３では，請求項４０記載のべき演算方法を用いた署名，認証，秘密通信及び鍵共有方式としている．
【００６２】
請求項４４では，有限群をEとし，E上の群演算を加法的に表し，nビットのデータd，分割数をt(<n), t とnの最小公倍数をn’=kt とし，
d のn’ビットでの二進表現を
d=d[n’-1]・2^(n’-1)+…+d[n]・2^n+d[n-1]・2^(n-1)+…+
d[0]， 
(d[n’-1]=…=d[n]=0かつd[n-1],…,d[0]は0または1)
とし，上記dの二進表現を用いて，kビットのデータa[j]をj=0 からt-1 に対して，
a[j]= d[kj+(k-1)]・2^(k-1)
+・・・ +d[kj+1]・2+ d[kj]
と表記し，
これらE，k，n，t，n’を入力として格納する第一のメモリ部と，
これらdとその二進表現，及びkビットのデータ{a[j]}を格納する第二のメモリ部を有し，
有限群Eの元Gを入力する入力部と，
有限群Eの任意の元Rを生成する乱数発生部と，
上記元Rと上記入力元G，第一のメモリ部のkを入力として，
j=1 からt-1に対してG[j] = 2^(kj)G としてEの元
G[j]を求め，
G[0] = G と表し，
次に上記元G[j](j=0,..,t-1)と0≦ b ≦2^t-1の整数bとそのbの二進表現b
= b[t-1]・2^(t-1) + ・・・+ b[0]（各b[i]は0 か1）を用いて，
T[b] = b[t-1]・G[t-1] + ・・・+ b[0]・G[0]-Rとして，
2^t個のEの元{T[0],..,T[2^t-1]}を求める第一の演算部と，
上記元Rと第一の演算部の出力{G[0],..,G[t-1]}と{T[0],..,T[2^t-1]}を入
力として，{G[0],..,G[t-1]}，{T[0],..,T[2^t-1]},
Y=Rを第二の演算部の初期値として設定する初期値設定部と，
初期値設定部の出力{G[0],…,G[t-1]}，   {T[0],..,T[2^t-1]}, Y と上記dの二進表現{d[i]}を入力として，
i=k-1 から 0 まで以下の演算，
Y = 2Y +
T[d[i+k(t-1)]2^{(t-1)k}+ …+d[i+k]2^k + d[i]]
i = i-1
を順次ループ処理する第二の演算部と，
第二の演算部の出力であるYと上記元Rを入力として，Y=Y-Rを計算する第三の演算部を有し，
第三の演算部の出力Yをべき演算dGの値として出力する出力部を有することを特徴とする有限群Eのべき演算装置としている．
【発明の効果】
【００６３】
以上に説明したように，従来例では，サイドチャネル攻撃に対して安全にべき演算dGを求めるには，必要となる最小限の中間変数の量が多くなる問題と，予備計算テーブルなどを利用し，実行速度の高速化を図ることが困難であるという問題があった．
【００６４】
本発明は，この従来例における問題点を鑑みて行なわれたもので，サイドチャネル攻撃に強力なべき演算を，メモリサイズ及び実行速度に関してフレキシブルに実現することで，安全な有限群上の離散対数問題に基づく鍵共有，暗号，署名方式を提供することを目的とする．これにより，より高速でよりコンパクトなソフトあるいはハード実現が可能になり，携帯端末などにおいても容易に実現可能な離散対数問題を用いた鍵共有，暗号，署名方式の提供が可能になる．安全な鍵共有，暗号，署名方式などの公開鍵暗号系を高速かつコンパクトに実現できると，性能の低い機械上のアプリケーションのセキュリティを強化することもでき，その実用的価値は大きい.
【実施例１】
【００６５】
図１は，べき演算装置を示すものである．図６は，楕円曲線上のべき演算を実現する方法を時系列に示すものであり，図１の各部との対応も記載する．
以下，図１及び図６を参照しながら楕円曲線上のべき演算の方法を説明する．
【００６６】
Step 1. 楕円曲線 E(Fq),
E(Fq) の元 G とビット数nを入力
有限体 FqとFq上の楕円曲線E，E(Fq)の元G，ビット数nを入力する．
【００６７】
Step 2. dとその二進表記d =
d[n-1]2^(n-1)+ ・・・+ d[1]2 + d[0]を入力
nビットのデータdを二進で表記する．このとき，各d[n-1],…,d[0]は0または1である．
【００６８】
Step 3. E(Fq) の元R をとる．
【００６９】
Step 4.  Z = G-R とする．
dG+Rを最上位ビット（MSB）より計算するときに必要な元Z=G-Rを計算する．
【００７０】
Step ５.  Y = R, Z = G-R とする．
dG+Rを最上位ビット（MSB）より計算するために初期値Y=Rを設定する．
【００７１】
Step
６から７までが第二の演算部に相当する．
Step ６.  i = n-1 とする．
dG+Rを最上位ビット（MSB）より計算するためのカウンタiを0に設定する．
Step ７.  i ≧ 0
d[i]の値に応じて以下の演算，
Y=2Y+Z (d[i]=1のとき),
Y=2Y-R (d[i]=0のとき)，
を行い，iを１だけ減らし，step
７の判定を行う．
【００７２】
Step ８. Y = Y-R を計算
【００７３】
Step ９. Y を出力する．
Step ７ で dY+R
が求められ，step ８ でその結果からRを減算した結果がYに入力されるので，出力値のYはべき演算dGの結果となる．
【００７４】
上記実施例１は，請求項５に掛かる発明の一実施例である．上記実施例１は，入力の楕円曲線の元Gと秘密データdに対し，楕円べき演算dGを計算し出力する装置である．本装置では，その途中過程の消費電力が入力の度に異なり，また途中過程で楕円曲線の元が0座標，あるいは0レジスタを持つように入力Gを操作できない．このため，サイドチャネル攻撃に対して安全である．さらに，途中過程で必要になる楕円曲線の元を保持する中間変数の個数は３個であり，従来例により削減できる．
【００７５】
実施例１では，有限群として有限体上の楕円曲線を用いた場合のべき演算装置となっているが，実施例はこれに限定されない．例えば，請求項６にあるように，有限群として，有限体上の超楕円曲線を用いることもできる．さらに実施例１では，べき演算dGのd及びGがともにメモリに格納されている請求項１の場合を扱っているが，実施例はこれに限定されない．例えば，請求項８，１３，１８にあるように，dが乱数として生成されGがメモリに格納される場合，dが乱数として生成されGがユーザにより入力される場合，dがメモリに格納されGがユーザにより入力される場合もできる．なお，これらの実施例は，図２，３，４にそれぞれ対応する．
【００７６】
実施例１ではべき演算装置のみを表記しているが，離散対数問題を利用した暗号，署名，鍵共有，認証などで利用するべき演算を，本方法を用いて実現し，サイドチャネル攻撃に対して安全に実現した方式も含まれる．
【実施例２】
【００７７】
図５は，べき演算装置を示すものである．図７は，楕円曲線上のべき演算を実現する方法を時系列に示すものであり，図５の各部との対応も記載する．
以下，図５及び図７を参照しながら楕円曲線上のべき演算の方法を説明する．
を参照しながら楕円曲線上のべき演算の方法を説明する．
Step 1. 楕円曲線E(Fq),
E(Fq)の元G，ビット数n，分割数t，n’=ktを入力
有限体 FqとFq上の楕円曲線E，E(Fq)の元Gを入力する．
【００７８】
Step ２. dとn’ビットの二進表記d = d[n-1]2^(n-1)+ ・・・+ d[1]2 + d[0]と{a[j]}を入力
nビットのデータdを上位に0を付加することで，n’ビットに拡張し，２進で表記する．
d = d[n’-1]2^(n’-1)+…+d[n]2^n+d[n-1]2^(n-1)+…+ d[1]2 +
d[0] 
このとき，d[n’-1]=…=d[n]=0で，d[n-1],…,d[0]は0または1である．
次に，上記dの二進表現を用いて，kビットのデータa[j]を
j=0 からt-1 に対して，
a[j]=
d[kj+(k-1)]・2^(k-1) +・・・+ d[kj]
と表記する．
【００７９】
Step
３．E(Fq) の元R
をとる．
【００８０】
Step
４. G[i] = 2^ki G （i = 1,…, k-1) と予備計算テーブル{T[b]}の作成
まず，G[j] = 2^(kj)G （j= 1,…,k-1）として，
Eの元 G[j]を求め，G[0] = G と表す．
次に，0≦ b ≦2^t-1の任意のbとそのbの二進表現
b = b[t-1]2^(t-1) + ・・・+
b[0] （各b[i]は0 か1）
を用いて，
T[b] = b[t-1]G[t-1] + ・・・+
b[0]G[0] 
として2^t個のEの元{T[0],..,T[2^t-1]}を求める．
【００８１】
Step ５.  Y=Rとする．
dG+R = a[t-1]G[t-1]+…+a[0]G[0]を最上位ビット（MSB）より計算するために初期値Y=Rとする．
【００８２】
Step
６から７までが第二の演算部に相当する．
Step ６.  i = k-1 とする．
Step
７.   i ≧ 0
a[t-1][i],
…, a[0][i]を用いて，予備計算テーブルの元を索引し，
以下の演算，
Y = 2Y + T[d[i+k(t-1)]2^{(t-1)k}+
…+d[i+k]2^k + d[i]]
を行い，iを１だけ減らし，step 7
の判定を行う．
【００８３】
Step ８.  Y = Y-R を計算
【００８４】
Step ９. Y を出力する．
Step ７ で dY+R
が求められ，step ８ でその結果からRを減算した結果がYに入力されるので，出力値のYはべき演算Y=dGの結果となる．
【００８５】
上記実施例２は，請求項８に掛かる発明の一実施例である．上記実施例２は，入力の楕円曲線の元Gと秘密データdに対し，楕円べき演算dGを計算し出力する装置である．本装置では，その途中過程の消費電力が入力の度に異なり，また途中過程で楕円曲線の元が0座標，あるいは0レジスタを持つように入力Gを操作できない．このため，サイドチャネル攻撃に対して安全である．さらに，途中過程で必要になる楕円曲線の元を保持する中間変数をテーブルとして効率的に保持することで，高速なべき演算を提供できる．
【００８６】
実施例２では，有限群として有限体上の楕円曲線を用いた場合のべき演算装置となっているが，実施例はこれに限定されない．例えば，請求項２８にあるように，有限群として，有限体上の超楕円曲線を用いることもできる．さらに実施例２では，べき演算dGのd及びGがともにメモリに格納されている請求項１の場合を扱っているが，実施例はこれに限定されない．例えば，請求項３０，３５，４０にあるように，dが乱数として生成されGがメモリに格納される場合，dが乱数として生成されGがユーザにより入力される場合，dがメモリに格納されGがユーザにより入力される場合もできる．また言うまでもなく，本実施例ではべき演算装置のみを表記しているが，離散対数問題を利用した暗号，署名，鍵共有，認証などで利用するべき演算を，本方法を用いて実現し，サイドチャネル攻撃に対して安全に実現した方式も含まれる．
【産業上の利用可能性】
【００８７】
従来例及び実施例のメモリ量，計算量の比較を図９に表す．計算量に関しては，定義体Fqが160ビットの場合と1ビット当たりの計算量を表した．D，Aは楕円曲線上の2倍算，加算に掛かる計算量，M, Sは定義体Fq上の乗算，2倍算に掛かる計算量を表す．この表により，メモリ量の制限が非常に厳しい場合，実施例１を利用すると，最小のメモリ量で安全かつ高速なべき演算が実現できる．また，高速性が要求される場合には，実施例２において分割数tを変化させることで，高速なべき演算が実現できる．実際，分割数としてt=4をとると，約50％の実行時間でべき演算が実現でき，その鍵共有，暗号，署名方式などのアプリケーションにおけるインパクトは非常に大きい．産業上で利用するには，アプリケーション及びそのアプリケーションを実現するプラットフォームにより，要求される仕様条件が異なる．本発明は，メモリ及び高速性という異なる観点の要求仕様に対して，それぞれ最適かつ安全なべき演算を提供できる．また，本発明の実現するべき演算は，鍵共有，暗号，署名方式など広範囲のアプリケーションで利用される基本技術であり，その産業上の利用可能性は非常に高い．
【図面の簡単な説明】
【００８８】
【図１】請求項１の有限群Eのべき演算方法の構成図
【図２】請求項８の有限群Eのべき演算方法の構成図
【図３】請求項１３の有限群Eのべき演算方法の構成図
【図４】請求項１８の有限群Eのべき演算方法の構成図
【図５】請求項２３の有限群Eのべき演算方法の構成図
【図６】実施例１の楕円曲線のべき演算方法の構成図
【図７】実施例２の楕円曲線のべき演算方法の構成図
【図８】従来例１の楕円曲線のべき演算方法の構成図
【図９】従来例と実施例１，２との性能比較表
【図１】
2006078943.tif 000003
【図２】
2006078943.tif 000004
【図３】
2006078943.tif 000005
【図４】
2006078943.tif 000006
【図５】
2006078943.tif 000007
【図６】
2006078943.tif 000008
【図７】
2006078943.tif 000009
【図８】
2006078943.tif 000010
【図９】
2006078943.tif 000011