公開鍵暗号のための多倍長整数計算アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
公開鍵暗号方式は、500~2000ビット程度の長さの整数計算を利用すると、実際上解読不可能な程度の難しさとなる。しかし、そのように長い整数の計算には、秘密情報を知っての暗号化/復号化にも、かなりの計算時間がかかる。特に、多倍長整数乗算の速度が全体の性能を決めることになるため、その高速化は重要である。多倍長整数乗算のアルゴリズムとして、単純な二乗時間のアルゴリズム、そのKaratsubaの方法による高速化、高速フーリエ変換による対数時間のアルゴリズム等が知られており、計算量のオーダーとしては後者ほど勝れているが、公開鍵暗号方式に必要な程度の長さの場合には、その差は微妙なものとなる。そこで、最近の一般的なCPU上での実際のインプリメンテーションに関して、各種アルゴリズムの速度を比較、検討してみる。最近のCPUでは、レジスタ間での加算や乗算は高速であり、条件判断やデータの転送のほうに多くの時間をとられていることに注意する必要がある。最近のCPUでは、各実行サイクルで、浮動小数点加算、浮動小数点乗算、を同時に実行できる。これに比べて整数の乗算は極めて遅いため、多倍長のデータは、適当なビット数に区切って複数の浮動小数点数にわけ、浮動小数点演算回路を利用して計算するのが効率的である。演算と並行して、さらに、浮動小数点のロードも各サイクルにl回実行できる。しかし、浮動小数点のストアに関しては、演算とは並行できるものの、ロードとは並行せずに2サイクルに1回しか行えないのが普通である。さらに多重度の大きなCPUでも、この演算とロード/ストアの性能の比率はほぼ同様である。高速化のためにはレジスタを活用し、ロード/ストアを減らすことが重要である。公開鍵暗号のための多倍長整数計算ではそれほど大きなデータ量を扱わないので、すべてのデータは一次キャッシュに入ると考えてよい。本稿では、こうした要因を考慮しつつ、公開鍵暗号のための多倍長整数計算アルゴリズムの高速なインプリメンテーションについて、クロック速度99MHz理論最大性能198MFLOPSのHP9000/755上で、640ビット、2000ビットの二つの桁数について、各種方法を比較考察する。一つの浮動小数点レジスタには20ビットを格納することとする。
- 一般社団法人情報処理学会の論文
- 1995-09-20
著者
関連論文
- 新世代ネットワークプロトコルIP--の設計(パラレル,インターネットと情報倫理教育,一般)
- 国会審議のインターネット配信とフェアユース(知的財産関係,一般)
- 日本でのインターネット放送事始
- 無線LANでのMake-Before-Breakハンドオーバーの他方式比較とフィールド実証(移動通信ワークショップ)
- End-to-endマルチホームを考慮した階層的なアドレス自動割当手法(Future Internet,一般,Future Internet,一般)
- エンドツーエンドNAT(インターネット運用技術,一般,インターネット運用・管理,一般)
- Y-00 is Broken
- 公正競争を目的としたPONのアンバンドル化(フォトニックネットワーク/制御,光制御(波長変換・スイッチング等),光波/量子通信,GMPLS,一般)
- GF(p)上の楕円曲線暗号における剰余乗算の高速化に関する研究
- End-to-endマルチホームを考慮した階層的なアドレス自動割当と経路制御プロトコルとの連繋(システム理論,インターネットと情報倫理教育,一般)
- 多数のファイバが引かれたマルチファイバWDMネットワークの呼損率 : 複数径路選択可能な場合
- 超低遅延無線IPパケット伝送において時間選択性フェージングがパケット誤り率特性に与える影響(QoS,モバイルネットワーク,高速パケット伝送信号処理・伝送技術,無線通信一般)
- B-5-183 時間選択性フェージングが超低遅延無線IPパケット伝送特性に与える影響(B-5.無線通信システムB(ワイヤレスアクセス),一般講演)
- B-5-182 超低遅延無線IPパケット伝送におけるパケット誤り率の解析的導出法(B-5.無線通信システムB(ワイヤレスアクセス),一般講演)
- 超低遅延モバイルネットワークのための適応SR-SW-ARQ/FECの実験的評価(移動通信ワークショップ)
- 量子化と包摂
- End-to-endマルチホームを考慮した階層的なアドレス自動割当と経路制御プロトコルとの連繋(システム理論,インターネットと情報倫理教育,一般)
- 日本でのインターネット放送事始
- 日本でのインターネット放送事始
- ATM網上でのInternet資源予約プロトコルの設計と実装について
- VODとインターネットの統合について
- VODとインターネットの統合について
- High Performnce Routing over Massively Parallel Routers
- 超高速ネットワークの目指すもの : 未来開拓プロジェクト「高度マルチメディア応用システム構築のための先進的ネットワークアーキテクチャの研究」総括
- MISプロトコルとPDMAによる高速ハンドオーバー(移動通信ワークショップ)
- MISプロトコルとPDMAによる高速ハンドオーバー(移動通信ワークショップ)
- MIS プロトコルと PDMA による高速ハンドオーバー(移動通信ワークショップ)
- MIS プロトコルと PDMA による高速ハンドオーバー(移動通信ワークショップ)
- MISプロトコルとPDMAによる高速ハンドオーバー(移動通信ワークショップ)
- 階層的なロケータ自動番号割当プロトコルHANAとDNSとの連携
- 階層的なロケータ自動番号割当プロトコルHANAの設計と実装(インターネット運用・管理,一般)
- 送信者アドレス情報のみでの経路制禦を行うIPv6マルチホームの提案(インターネットの運用・管理技術及び一般 II,インターネット運用・管理技術及び一般)
- 送信者アドレス情報のみでの経路制禦を行うIPv6マルチホームの提案(インターネットの運用・管理技術及び一般 II,インターネット運用・管理技術及び一般)
- 送信者アドレス情報のみでの経路制禦を行うIPv6マルチホームの提案(インターネットの運用・管理技術及び一般 II,インターネット運用・管理技術及び一般)
- 無線インターネットサービスに必要なセキュリティを提供する高速認証システム
- エンドツーエンドスムーズ光パスマイグレーション(フォトニックNWシステム・デバイス,フォトニック結晶・ファイバとその応用,光集積回路,光導波路素子,光スイッチング,導波路解析,及び一般)
- エンドツーエンドスムーズ光パスマイグレーション(フォトニックNWシステム・デバイス,フォトニック結晶・ファイバとその応用,光集積回路,光導波路素子,光スイッチング,導波路解析,及び一般)
- エンドツーエンドスムーズ光パスマイグレーション(フォトニックNWシステム・デバイス,フォトニック結晶・ファイバとその応用,光集積回路,光導波路素子,光スイッチング,導波路解析,及び一般)
- 日本の加入者線におけるADSL適用可能性の検討
- IP@home:放送サービス用ミドルウェア
- エニキャストを用いた自動車のための地域別緊急通報システムの実現(アドホックネットワーク, ユビキタスITSとモバイルアプリケーション)
- エニキャストを用いた位置依存グループウェアの設計と実装
- ユビキタス環境を活用した位置に基づくグループウェア
- ユビキタス環境を活用した位置に基づくグループウェア
- IP@home:ホームネットワークとインターネットの融合アーキテキチャ
- 2010年のIPオーバフォトニックネットワーク像(3) : フォトニックアクセスネットワークの先端技術
- IP@home:IP over IEEE1394のQoS
- インターネットから制御可能なTV品質のVODシステムの構築について
- B-7-83 IP over Glassの新伝送方式
- 動的帯域割当を実現するシグナリング方式について
- 動的帯域割当を実現するシグナリング方式について
- 動的帯域割当を実現するシグナリング方式について
- 動的帯域割当を実現するシグナリング方式について
- ネットワークを用いた疎結合型並列ルータアーキテクチャ(次世代のインターネット/分散システムの構築・運用技術)
- QoSルーティングプロトコルにおけるクランクバックを不要とする広告メッセージ削減手法(インターネットアーキテクチャ,一般,インターネットセキュリティ,一般)
- QoSルーティングプロトコルにおけるクランクバックを不要とする広告メッセージ削減手法(インターネットアーキテクチャ,一般,インターネットセキュリティ,一般)
- 多数の並行光ファイバ間の光パケットスイッチング(フォトニックネットワーク関連技術,一般)
- 新世代ネットワークプロトコルIP--の設計(パラレル,インターネットと情報倫理教育,一般)
- 新世代ネットワークプロトコルIP--の設計(パラレル,インターネットと情報倫理教育,一般)
- エンドツーエンドスムーズ光パスマイグレーション
- ノード間に複数本の光ファイバがある場合の光パス予約呼損率の評価(フォトニックネットワークシステム,光ルーティング,ブロードバンドアプリケーション,一般)
- ドメイン間光パス経路制御における階層的なQoS情報の広告手法(IPバックボーンネットワーク,MPLS,GMPLS,フォトニックネットワーク,トラヒック制御・解析及び一般)
- ATMインターネット環境における網間接続アーキテクチャ
- 超並列計算機向け多段光超高速内部接続(HPC-11 : 通信I)
- 光ファイバ遅延線バッファでの絶対的優先度制御(IPバックボーンネットワーク,MPLS,GMPLS,フォトニックネットワーク,トラヒック制御・解析及び一般)
- BS-10-7 超並列ペタFlops計算機のための多波長光パケット相互接続(BS-10.光スイッチング・光インターコネクション・光LAN技術〜ラック間・ボード間・チップ間光ネットワークへ〜,シンポジウムセッション)
- 階層化QoSルーティング・シグナリングプロトコルのインタードメイン光パスルーティングへの適用
- アドレス自動割付も同時に行う階層化QoSルーティングプロトコルの考察(インターネット運用・管理技術,一般,インターネット運用・管理技術,一般)
- 超高速光パケットスイッチのためのデバイス及び周辺技術
- 超高速光パケットスイッチのためのデバイス及び周辺技術(フォトニックNW・デバイス,フォトニック結晶・ファイバとその応用,光集積回路,光導波路素子光スイッチング,導波路解析,および一般)
- 超高速光パケットスイッチのためのデバイス及び周辺技術(フォトニックNW・デバイス,フォトニック結晶・ファイバとその応用,光集積回路,光導波路素子光スイッチング,導波路解析,および一般)
- 超高速光パケットスイッチのためのデバイス及び周辺技術(フォトニックNW・デバイス,フォトニック結晶・ファイバとその応用,光集積回路,光導波路素子,光スイッチング,導波路解析,および一般)
- モンゴメリ乗算法の高速化
- ポリシング付き優先度キュー(PPQ)方式によるQoS保証可能なルータ装置
- ポリシング付き優先度キュー(PPQ)方式によるQoS保証可能なルータ装置
- ポリシング付き優先度キュー(PPQ)方式によるQoS保証可能なルータ装置
- ポリシング付き優先度キュー(PPQ)方式によるQoS保証可能なルータ装置
- インターネット上のマルチメディア機器制御プロトコル(マルチメディア通信プロトコル)
- 4P-5 M/D/1/K待ち行列モデルを用いた通信品質保証の要件に関する考察
- 4P-4 階層化されたQoSルーティングの考案
- エニキャストを用いた緊急通信(セッション5B:システム)(ユビキタスモバイルサービス)
- エニキャストを用いた緊急通信(セッション5B : システム)(ユビキタスモバイルサービス)
- エニキャストを用いた位置依存グループウェアの実装
- 位置と目的情報に基づくコミュニケーショングループウェアの設計(モバイルコンピューティング・一般)
- 公開鍵暗号のための多倍長整数計算アルゴリズム
- 多倍長計算のHPC技術
- スペクトラムパターンを利用した聴覚障害者コミュニケーション支援の研究
- 最近のワークステーションアーキテクチャと行列乗算性能について
- 容量型光スイッチの高速駆動と高頻度スイッチされる光スイッチの電力消費
- 国会審議のインターネット配信とフェアユース(知的財産関係,一般)
- 太田乗算法にレジスタブロッキングやキャリーセーブ手法の適用に関する研究
- 省電力IPモビリティ(セッション4)(テーマ:モバイルコンピューティング,ITS,放送コンピューティング)
- 超低遅延モバイルネットワークのための適応的な誤り制御手法(ブロードバンド無線アクセス技術, 無線通信一般, 信号処理)
- 超低遅延モバイルネットワークの実現性に関する検討(ブロードバンド無線アクセス技術, 無線通信一般, 信号処理)
- パケット順序入れ替えを許す実時間光バッファの制御方式
- 階層化経路制御プロトコルの為の階層的なロケータ番号自動割振プロトコルHANAの拡張(ネットワークセキュリティ,インターネットセキュリティ,一般)
- 階層化経路制御プロトコルの為の階層的なロケータ番号自動割振プロトコルHANAの拡張(ネットワークセキュリティ,インターネットセキュリティ,一般)
- 省電力IPモビリティ(モバイルとインターネットの融合, 及び一般)
- 省電力IPモビリティ(モバイルとインターネットの融合, 及び一般)
- アドレス自動割付も同時に行う階層化QoSルーティングプロトコルの考察