論文の概要: An Efficient All-to-All GCD Algorithm for Low Entropy RSA Key Factorization
- arxiv url: http://arxiv.org/abs/2405.03166v1
- Date: Mon, 6 May 2024 05:16:43 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-07 14:45:09.799620
- Title: An Efficient All-to-All GCD Algorithm for Low Entropy RSA Key Factorization
- Title（参考訳）: 低エントロピーRSA鍵分解のための効率的な全対全GCDアルゴリズム
- Authors: Elijah Pelofske,
- Abstract要約: 本研究は,現在最高のバッチGCDアルゴリズムよりも効率的である,新しい全対全バッチGCDアルゴリズムについて述べる。
実際には、提案したバイナリツリーバッチGCDアルゴリズムの実装は、標準の剰余木バッチGCD手法と比較して約6倍の高速化を実現している。
- 参考スコア（独自算出の注目度）: 1.0878040851638
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: RSA is an incredibly successful and useful asymmetric encryption algorithm. One of the types of implementation flaws in RSA is low entropy of the key generation, specifically the prime number creation stage. This can occur due to flawed usage of random prime number generator libraries, or on computers where there is a lack of a source of external entropy. These implementation flaws result in some RSA keys sharing prime factors, which means that the full factorization of the public modulus can be recovered incredibly efficiently by performing a computation GCD between the two public key moduli that share the prime factor. However, since one does not know which of the composite moduli share a prime factor a-priori, to determine if any such shared prime factors exist, an all-to-all GCD attack (also known as a batch GCD attack, or a bulk GCD attack) can be performed on the available public keys so as to recover any shared prime factors. This study describes a novel all-to-all batch GCD algorithm, which will be referred to as the binary tree batch GCD algorithm, that is more efficient than the current best batch GCD algorithm (the remainder tree batch GCD algorithm). A comparison against the best existing batch GCD method (which is a product tree followed by a remainder tree computation) is given using a dataset of random RSA moduli that are constructed such that some of the moduli share prime factors. This proposed binary tree batch GCD algorithm has better runtime than the existing remainder tree batch GCD algorithm, although asymptotically it has nearly identical scaling and its complexity is dependent on how many shared prime factors exist in the set of RSA keys. In practice, the implementation of the proposed binary tree batch GCD algorithm has a roughly 6x speedup compared to the standard remainder tree batch GCD approach.
- Abstract（参考訳）: RSAは驚くほど成功し、有用な非対称暗号化アルゴリズムである。
RSAにおける実装欠陥のタイプの一つは、鍵生成の低エントロピー、特に素数生成段階である。
これはランダム素数生成ライブラリの不足や、外部エントロピーの源がないコンピュータで発生する。
これらの実装欠陥により、いくつかのRSAキーが素因子を共有するため、素因子を共有する2つの公開鍵モジュラー間の計算GCDを実行することにより、公共率の完全因子化を極端に効率的に回収することができる。
しかし、複合モジュールのどれが素因子a-プリオリを共有しているかが分かっていないため、そのような共有素因子が存在するかどうかを判断するために、利用可能な公開鍵上で全対全GCD攻撃(バッチGCD攻撃またはバルクGCD攻撃)を行うことができる。
本研究は,従来の最良バッチGCDアルゴリズム(残りの木バッチGCDアルゴリズム)よりも効率的であるバイナリツリーバッチGCDアルゴリズムと呼ばれる新しい全対全バッチGCDアルゴリズムについて述べる。
既存の最良バッチGCD法との比較(積木に続く剰余木計算)は、いくつかのモジュライが素因子を共有するように構成されたランダムRSA変調のデータセットを用いて行われる。
この二分木バッチGCDアルゴリズムは、既存の残木バッチGCDアルゴリズムよりも実行時性がよいが、漸近的にほぼ同一のスケーリングを持ち、その複雑さはRSAキーの集合に共有された素因子の数に依存する。
実際には、提案したバイナリツリーバッチGCDアルゴリズムの実装は、標準の剰余木バッチGCD手法と比較して約6倍の高速化を実現している。
関連論文リスト
- Post-Quantum Security: Origin, Fundamentals, and Adoption [0.29465623430708915]
まず、離散対数とよく知られた2つの非対称なセキュリティスキーム、RSAと楕円曲線暗号の関係について述べる。
次に、量子アルゴリズムによる攻撃に対して安全と考えられるスキームの基盤である格子ベースの暗号の基礎を示す。
最後に、このような量子セーフな2つのアルゴリズム(KyberとDilithium)について詳しく説明する。
論文 参考訳（メタデータ） (2024-05-20T09:05:56Z) - Implementation of Entropically Secure Encryption: Securing Personal Health Data [0.704590071265998]
Entropically Secure Encryption (ESE) はOne-Time Padに短いキーで無条件のセキュリティを提供する。
バルク暗号のためのESEの実装について述べる。
論文 参考訳（メタデータ） (2024-04-04T12:07:33Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - SOCI^+: An Enhanced Toolkit for Secure OutsourcedComputation on Integers [50.608828039206365]
本稿では,SOCIの性能を大幅に向上させるSOCI+を提案する。
SOCI+は、暗号プリミティブとして、高速な暗号化と復号化を備えた(2, 2)ホールドのPaillier暗号システムを採用している。
実験の結果,SOCI+は計算効率が最大5.4倍,通信オーバヘッドが40%少ないことがわかった。
論文 参考訳（メタデータ） (2023-09-27T05:19:32Z) - A comment on "Factoring integers with sublinear resources on a
superconducting quantum processor" [0.0]
そこで我々はSchnorr's lattice-based integer factorizationアルゴリズムのオープンソース実装について述べる。
我々の実装は、シュノーラーの整数を70ビットまでしか持たないハイブリッド量子+古典版に対する主張された部分線型格子次元が示している。
我々は、我々の実装が、他のハイブリッド量子/古典的整数分解アルゴリズムのアイデアをテストするための、コミュニティの場として機能することを願っている。
論文 参考訳（メタデータ） (2023-07-18T21:46:54Z) - Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the
Cryptanalysis of pSIDH [5.398058794903461]
自己同型環問題(英語版)(IsERP)は、超特異曲線の間の同型写像の余領域の自己同型環を計算することを要求する。
次数が奇数で、多くの素因子が$O(loglog p)=$である等質性に対して、IsERPを解くための新しい量子時間アルゴリズムを導入する。
論文 参考訳（メタデータ） (2023-05-31T14:30:32Z) - Distributed Quantum-classical Hybrid Shor's Algorithm [1.7396274240172125]
ショアのアルゴリズムは、ノイズ中間量子時代の最も重要な量子アルゴリズムの1つであると考えられている。
Shorのアルゴリズムに必要なリソースを削減するために、我々は新しい分散量子古典ハイブリッド順序決定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-24T13:52:05Z) - Algorithms for Weighted Pushdown Automata [118.67634716230025]
重み付きプッシュダウンオートマトン(WPDA)は多くの自然言語処理タスクの中核にある。
WPDA上で直接動作する新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-13T10:21:31Z) - Scaling Gaussian Process Optimization by Evaluating a Few Unique
Candidates Multiple Times [119.41129787351092]
GPに基づく逐次ブラックボックス最適化は,複数の評価ステップの候補解に固執することで効率よく行うことができることを示す。
GP-UCB と GP-EI の2つのよく確立されたGP-Opt アルゴリズムを改良し,バッチ化された GP-Opt の規則を適応させる。
論文 参考訳（メタデータ） (2022-01-30T20:42:14Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。