Small secret key attack on Takagi's variant of RSA (part 1) (情報セキュリティ)
スポンサーリンク
概要
- 論文の詳細を見る
Takagiは,N=p^rqでed≡1 mod(p-1)(q-1)とする変形RSA暗号を提案している.ここで、φ(N)≠(p-1)(q-1)であることに注意せよ.この暗号に対して,秘密鍵dが,d<N^<(7-2√<7>/3(r+1)>をみたすとき,dを多項式時間で求めることを示す.特に,r=1のときには,Boneh-Durfeeによる通常のRSA暗号に対する結果と対応している.我々のアルゴリズムは,Coppersmithのアプローチに基づいている.まず,秘密鍵を求める問題を,y^rz=Nという制約付きの3変数方程式f(x,y,z)=x(y-1)(z-1)+1=0(mod e)の小さい解を求める問題に帰着させ,ついで,この問題を解くアルゴリズムを提案している.この問題を解くことができる条件を求めることにより,秘密鍵に対する条件を導出している.さらに,計算機実験を行い,我々のアルゴリズムの有効性を検証した.いずれの例でも,正しく解が得られることを確認した.
- 2007-11-14
著者
関連論文
- RSA暗号のSmall Secret Key Attackに対する簡単な証明とその拡張(セキュリティ関係,一般)
- 研究グループが脆弱性を発見した場合にとるべき行動についての法的考察(プロジェクトマネジメント関係,一般)
- Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
- 5. 素因数分解は,RSA暗号解読より真に難しいか?(素数)
- 暗号における理論と実装のギャップ : 置き換えアプローチの二面性(暗号理論入門(4))
- Small secret key attack on Takagi's variant of RSA (part 1) (オフィスインフォメーションシステム)
- Small secret key attack on Takagi's variant of RSA (part 1) (情報セキュリティ)
- APOPが破られた(オピニオン)
- 共通鍵ブロック暗号SC2000
- RSA暗号のSmall Secret Key Attackに対する簡単な証明とその拡張(セキュリティ関係,一般)
- RSA暗号のSmall Secret Key Attackに対する簡単な証明とその拡張(セキュリティ関係,一般)
- Bulk量子計算モデル上におけるGroverのアルゴリズムの繰返し回数について
- 物理的実現可能性に優れたNMR量子探索アルゴリズム(計算理論)
- A-7-11 MD4を用いたチャレンジ&レスポンス認証に対する現実的な攻撃(A-7.情報セキュリティ,一般セッション)
- CHES2003会議報告
- CHES 2002 会議報告
- CHES2002会議報告
- 素因数分解ハードウェアの研究・開発動向について(セキュリティ基盤技術,情報システムを支えるコンピュータセキュリティ技術の再考)
- Paillierの観点から見たディジタル署名の安全性の再考
- 双線形写像を用いた墨塗り署名方式の安全性について(セキュリティ基盤技術,ユビキタス社会を支えるコンピュータセキュリティ技術)
- NMR量子計算機を用いた効率的探索アルゴリズムの設計について
- Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
- Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
- AS-3-3 非線形ランプ型秘密分散(招待講演,AS-3.情報ハイディングの理論と技術,シンポジウム)
- 分散画像の回転を許す一般アクセス構造に対して複数の画像を隠す視覚復号型秘密分散法
- 確率的メータリング法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 確率的メータリング法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 確率的メータリング法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- Randomized Partial Checking Mix の一考察
- Randomized Partial Checking Mix の一考察
- Randomized Partial Checking Mix の一考察
- Randomized Partial Checking Mix の一考察
- Randomized Partial Checking Mix の一考察
- Randomized Partial Checking Mix の一考察
- 安全性を証明可能なハッシュ関数の設計論
- RSA暗号に対する格子理論に基づく攻撃(その2)
- 暗号学における双対性 : ゴールとシナリオの間には(チュートリアル)
- RSA暗号に対する格子理論に基づく攻撃
- 墨塗り・削除署名の拡張
- 墨塗り・削除署名の拡張
- 使い捨てIDを用いた処理負荷の少ない相手認証方式の提案(情報通信基礎サブソサイエティ合同研究会)
- ソフトウェアによるストリーム暗号の高速実装
- Modular LFSR 型 Filter Generator に対する Fast Correlation Attack
- ハッシュ関数(HAVAL)に対する衝突攻撃
- Multi-Collisionに関するバースデイパラドックスについて
- 高次SACのベクトル出力ブール関数への拡張
- MD5に対するコリジョンアタックの改良
- MD5に対するコリジョンアタックの改良
- MD4に対するコリジョンアタックの改良
- MD4に対するコリジョンアタックの改良
- 使い捨てIDを用いた処理負荷の少ない相手認証方式の提案(情報通信基礎サブソサイエティ合同研究会)
- 使い捨てIDを用いた処理負荷の少ない相手認証方式の提案(情報通信基礎サブソサイエティ合同研究会)
- Lower Bound on the Size of Shares of Nonperfect Secret Sharing Schemes
- Security of the Center in Key Distribution Schemes
- 境界要素法の変数変換型の自動数値積分法とその誤差解析
- ナップザック暗号における密度の再考(情報通信基礎サブソサイエティ合同研究会)
- ナップザック暗号における密度の再考(情報通信基礎サブソサイエティ合同研究会)
- ナップザック暗号における密度の再考(情報通信基礎サブソサイエティ合同研究会)
- ルーティングを用いた素因数分解回路について
- ルーティングを用いた素因数分解回路について
- クラウドにおけるデータ秘匿化および追跡技術(自律分散ネットワーク,P2Pネットワーク,オーバーレイネットワーク,マルチキャスト,セッション管理,インターネットトラヒック,コンテンツ配信,コンテンツ流通,コンテンツセキュリティ及び一般)
- 素因数分解ハードウェアの現状(ミニ素因数分解編) : 2006年秋(知的生産活動における情報アクセス制御技術及び一般)
- 素因数分解ハードウェアの現状(ミニ素因数分解編) : 2006年秋(知的生産活動における情報アクセス制御技術及び一般)
- CS-6-2 量子計算機による素因数分解の実現可能性(CS-6.量子ビットの現在、量子コンピューティングの将来,シンポジウム)
- 素因数分解ハードウェアの現状 : 関係式探索ステップ編 : 2006年夏
- 素因数分解ハードウェアの現状 : 関係式探索ステップ編 : 2006年夏
- 素因数分解ハードウェアの現状(関係式探索ステップ編) : 2006年夏
- PFDHに対するEUF-SACMAの最適安全性証明
- PFDHに対するEUF-SACMAの最適安全性証明
- 実用的"on the fly"認証の安全性(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 実用的"on the fly"認証の安全性(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 実用的"on the fly"認証の安全性(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 公開鍵暗号の数理, 森山大輔・西巻陵・岡本龍明著, 共立出版・日本応用数理学会監修, 2011年
- 科学通信 科学ニュース:暗号の米政府標準方式が危機に
- 国際会議ASIACRYPT 2011報告
- 近似GCD問題に対する改良アルゴリズム(セキュリティ,一般)
- 近似GCD問題に対する改良アルゴリズム(セキュリティ,一般)
- 近似GCD問題に対する改良アルゴリズム(セキュリティ,一般)
- 近似GCD問題に対する改良アルゴリズム(セキュリティ,一般)
- AI-1-1 計算能力の向上と暗号解読(AI-1.暗号研究の現状とブレークスルーに向けて,ソサイエティ企画)