特許

J-GLOBAL ID：200903007164458792

べき乗剰余演算軽減方法

発明者： 安齋 潤
出願人/特許権者： 株式会社高度移動通信セキュリティ技術研究所
代理人 (1件)： 役 昌明 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願平10-269028
公開番号（公開出願番号）：特開2000-089671
出願日： 1998年09月08日
公開日（公表日）： 2000年03月31日
要約：

【要約】【課題】 基地局のディジタル署名の検証を、端末が高速に行なえるようにするとともに、検証が正しいことを確認できるようにする。【解決手段】 基地局は、端末の代わりに、べき乗剰余演算gX mod pを、指数Xを分割して行ない、その結果(分割べき乗剰余値)を端末に送る。各端末側では、分割べき乗剰余値の一部のみを検査して、全ての分割べき乗剰余値を掛け合わせることにより、もとの指数Xより小さいべき乗剰余演算と数回の乗算でgX mod pを計算することができる。各端末は、分割べき乗剰余値の一部のみしか検査しないが、複数の端末が検査するので、トータルとして全ての分割べき乗剰余値に不正が無いことを確認できる。端末の演算量の削減効果と安全性は、指数の分割数と端末の総数が大きくなるほどよくなるので、端末数が多いシステムにおいてより効果を発揮する。端末の現在の負荷が大きければ小さな分割指数を演算し、負荷が小さければ大きな分割指数を演算することにより、各端末の負荷を平均化することができる。

請求項（抜粋）：

基地局と、前記基地局と接続されたN台(Nは2以上の整数)の端末からなる同報通信が可能な通信システムにおいて、前記基地局は、指数Xと元gおよび法pを記憶する第1の基地局側記憶部と、前記指数を分割する第1の基地局側計算部と、前記分割された指数(分割指数と呼ぶ)Xi(i=1,2,・・・,t)と前記第1の基地局側記憶部に記憶された前記法pおよび前記元gより分割べき乗剰余値Si=gXi mod p (i=1,2,・・・,t)を計算する第2の基地局側計算部と、前記分割指数Xiおよび前記分割べき乗剰余値Siを記憶する第2の基地局側記憶部とを備え、前記端末は、前記指数Xと前記元gおよび前記法pを記憶する第1の端末側記憶部と、基地局より送信された前記指数Xと前記分割指数Xiおよび前記分割べき乗剰余値Siを記憶する第2の端末側記憶部と、前記第2の端末側記憶部に記憶された前記指数Xと前記分割指数Xiの合計が等しいことを判定する第1の判定部と、前記分割指数Xiの中からf個の分割指数(選択分割指数と呼ぶ)Xdf(1≦f≦t)を選択する分割指数選択部と、前記選択分割指数Xdfと前記第1の記憶部に記憶された前記元gから選択べき乗剰余値Tk=gXdf mod p (1≦k≦f)を計算する第1の端末側計算部と、前記選択べき乗剰余値Tkとこれに対応する第1の端末側記憶部に記憶された分割べき乗剰余値Siが等しいことを判定する第2の判定部と、前記第2の端末側記憶部に記憶された前記分割べき乗剰余値Siを全て掛け合わせる第2の端末側計算部とを備え、(1)前記基地局は、前記第1の基地局側記憶部から前記指数Xを取り出し、前記第1の基地局側計算部において、X=X1+X2+・・・+Xtとなるように前記指数Xを分割して、前記第2の基地局側記憶部に分割指数Xiを記憶し、(2)前記基地局は、前記第1の基地局側記憶部から前記法pと前記元gおよび前記第2の基地局側記憶部から前記分割指数Xiを取り出し、前記第2の基地局側計算部において前記分割べき乗剰余値Si=gXi mod p (i=1,2,・・・,t)を計算し、前記分割べき乗剰余値Siを前記第2の基地局側記憶部に記憶し、(3)前記基地局は、前記第2の基地局記憶部から前記分割指数Xiおよび分割べき乗剰余値Siを取り出して全端末に一斉通知し、(4)全ての端末において、前記基地局の前記分割指数Xiおよび前記分割べき乗剰余値Siを受信し、前記分割べき乗剰余値Siを前記第2の端末側記憶部に記憶し、(5)全ての端末において、前記第1の端末側記憶部から前記指数Xおよび前記第2の端末側記憶部から前記分割指数Xiを取り出し、前記第1の判定部において前記指数Xと前記分割指数Xiから、X=X1+X2+・・・+Xtが成り立つことを確認し、(6)全ての端末において、前記第1の端末記憶部に記憶された前記分割指数Xiの中から前記分割指数選択部によりf個の選択分割指数Xdfを選び、前記第1の端末側記憶部の前記法pおよび前記元gから前記第1の端末側計算部において選択べき乗剰余値Tk=gXdk mod p (k=1,2,・・・,f)を計算し、(7)全ての端末において、前記選択べき乗剰余値Tkとこれに対応する前記第2の端末側記憶部の分割べき乗剰余値Siを第2の判定部において等しいことを確認し、(8)全ての端末において、前記第2の端末側記憶部の全ての分割べき乗剰余値Siを前記第2の端末側計算部において、gX=S1*S2*・・・*St mod pを計算してgX mod pを得ることを特徴とするべき乗剰余演算軽減方法。

IPC (5件)：

G09C 1/00 650 ,  G09C 1/00 640 ,  G06F 7/72 ,  H04L 9/30 ,  H04L 9/32

FI (6件)：

G09C 1/00 650 A ,  G09C 1/00 640 B ,  G06F 7/72 ,  H04L 9/00 663 A ,  H04L 9/00 675 B ,  H04L 9/00 675 D

Fターム (8件)：

5J104AA09 ,  5J104AA22 ,  5J104JA29 ,  5J104LA03 ,  5J104LA06 ,  5J104MA01 ,  5J104NA38 ,  5J104NA39