中国剰余定理におけるGaussのアルゴリズムに対する単純電力解析

• 小池, 正修

• 松本, 勉

書誌事項

タイトル別名

• チュウゴク ジョウヨ テイリ ニ オケル Gauss ノ アルゴリズム ニ タイスル タンジュン デンリョク カイセキ
• A Simple Power Analysis on Gauss's Algorithm for Chinese Remainder Theorem
• セキュリティ基盤技術

抄録

中国剰余定理（CRT）は多くの公開鍵暗号を高速に実装するために用いられる．本論文ではCRTにおけるGaussのアルゴリズムに対する単純電力解析（SPA）を提案する．提案解析手法は，2次元の場合のGaussのアルゴリズムに対し，消費電力波形から入力値を推測する．この手法を，剰余演算系（RNS）上のモンゴメリ乗算を利用したRSA-CRTに対して適用し，秘密素数pに関する部分情報を求めることができることを示す．さらに二分探索を応用することによりpを高確率で求めるアルゴリズムも提案する．

The Chinese Remainder Theorem (CRT) is used to optimize implementation of a lot of public-key cryptosystems. In this paper we propose a simple power analysis (SPA) on Gauss's algorithm for CRT. Our attack reveals input values of Gauss's algorithm in two-dimensional case using several power consumption traces. We apply this method to RSA-CRT implementation using Montgomery multiplication based on Residue Number Systems (RNS). Then we can deduce the partial information related to the secret prime p. Furthermore we show an algorithm to reveal p with high probability by modifying the binary search algorithm.

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 46 (8), 1860-1870, 2005-08-15

  東京 : 情報処理学会

キーワード

• 特集：多様な社会的責任を担うコンピュータセキュリティ技術

詳細情報

• CRID: 1050001337882632704
• NII論文ID: 110002769776
• NII書誌ID: AN00116647
• ISSN: 18827764
• ISSN: 03875806
• NDL書誌ID: 7464101
• Web Site: http://id.nii.ac.jp/1001/00010547/
• Web Site: http://id.ndl.go.jp/bib/7464101
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I7464101
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles
  • KAKEN