RSA公開鍵における情報埋め込みサイズの上限に関する考察

• 北原, 基貴

• 安田, 貴徳

• 西出, 隆志

• 櫻井, 幸一

書誌事項

タイトル別名

• Limit of Embeddable Information Size for RSA public key

抄録

RSA暗号において，公開鍵Nの中に効率的に情報を埋め込む手法がLenstraにより提案された．それ以来，Lenstraの提案した埋め込みアルゴリズムを用いて鍵供託を行ったり，公開鍵をより使いやすいものに変える手法が提案されてきた．しかし，Lenstraは埋め込み情報量の上限について公開鍵長の半分程度まで効率的に埋め込むことができると主張していたが，具体的なビット数に関しては言及していなかった．本研究ではLenstraアルゴリズムを用いた場合の効率的に埋め込みのできるビット長の限界を見積り，また埋め込むビット長と公開鍵Nからアルゴリズムの成功確率を見積もる式を理論解析と実験により算出した．

In RSA encryption, Lenstra proposed method that information can be embed in the public key N efficiently. Since then, many methods have proposed, such as additional key escrow function and a public key becoming visible. Lenstra make an assertion that embeddable size is up to half of the length of a public key, but he did not mention the strict length. In this paper, we examined Lenstra algorithm both in theoretical analysis and in implementation analysis, and calculated the limit of the length of embeddable information efficiently.

収録刊行物

• コンピュータセキュリティシンポジウム2012論文集

  コンピュータセキュリティシンポジウム2012論文集 2012 (3), 501-508, 2012-10-23

キーワード

• 公開鍵長，RSA，情報埋め込み，解析

詳細情報

• CRID: 1050574047131419392
• NII論文ID: 170000072727
• Web Site: http://id.nii.ac.jp/1001/00086687/
• 本文言語コード: ja
• 資料種別: conference paper
• データソース種別:
  • IRDB
  • CiNii Articles