論文の概要: An Efficient All-to-All GCD Algorithm for Low Entropy RSA Key Factorization
- arxiv url: http://arxiv.org/abs/2405.03166v2
- Date: Thu, 30 May 2024 17:36:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-31 20:15:18.500154
- 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倍の高速化を実現している。
関連論文リスト
- Factoring integers via Schnorr's algorithm assisted with VQE [0.0937465283958018]
現在の非対称暗号は、古典的コンピュータは効率よく大きな整数を乗算できるが、逆演算、因子化ははるかに複雑である、という原理に基づいている。
十分に大きな整数の場合、この分解プロセスは古典的なコンピュータで何百年、何千年もかかる。
この研究は、この論文を分析し、彼らが行った実験を再現するが、異なる量子法(VQE)で番号を1961年に分解できる。
論文 参考訳（メタデータ） (2024-11-25T18:11:10Z) - Quantum inspired factorization up to 100-bit RSA number in polynomial time [0.0]
我々はシュノーアの数学的枠組みに基づくRSA因子化ビルディングを攻撃した。
我々は、量子システムにおける最適化問題を符号化する最大256ビットのRSA数を分解する。
結果は現在の通信インフラのセキュリティを損なうものではない。
論文 参考訳（メタデータ） (2024-10-21T18:00:00Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。