When RSA Fails: Exploiting Prime Selection Vulnerabilities in Public Key Cryptography

• URL: http://arxiv.org/abs/2512.22720v1
• Date: Sat, 27 Dec 2025 22:58:35 GMT
• Title: When RSA Fails: Exploiting Prime Selection Vulnerabilities in Public Key Cryptography
• Abstract summary: This paper explores vulnerabilities in RSA cryptosystems that arise from improper prime number selection during key generation.<n>We examine two primary attack vectors: Fermat's factorization method, which exploits RSA keys generated with primes that are too close together, and the Greatest Common Divisor (GCD) attack, which exploits keys that share a common prime factor.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper explores vulnerabilities in RSA cryptosystems that arise from improper prime number selection during key generation. We examine two primary attack vectors: Fermat's factorization method, which exploits RSA keys generated with primes that are too close together, and the Greatest Common Divisor (GCD) attack, which exploits keys that share a common prime factor. Drawing from landmark research including Heninger et al.'s ``Mining Your Ps and Qs'' study, which discovered over 64,000 vulnerable TLS hosts, and B{ö}ck's 2023 analysis of Fermat factorization in deployed systems, we demonstrate that these vulnerabilities remain prevalent in real-world cryptographic implementations. Our analysis reveals that weak random number generation in embedded devices is the primary cause of these failures, and we discuss mitigation strategies including proper entropy collection and prime validation checks.

Related papers

• CryptanalysisBench: Can LLMs do Cryptanalysis? [76.79639292270497]
  We introduce CryptanalysisBench, 191 tasks across six families of cryptographic primitives.<n>Our benchmark consists of three tiers: (i) primitives with known practical breaks; (ii) primitives with no known practical break, evaluated both at full strength and as scaled-down variants.<n>Five frontier models break 65%-86% of Tier 1 schemes, 6-12 Tier-2 schemes at full strength, and 24-61 across all scaled-down variants.
  arXiv  Detail & Related papers  (2026-07-20T22:09:40Z)
• Public Key Encryption from High-Corruption Constraint Satisfaction Problems [6.201763450086127]
  We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs)<n>Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial.
  arXiv  Detail & Related papers  (2026-04-12T06:19:54Z)
• Exploiting Inaccurate Branch History in Side-Channel Attacks [54.218160467764086]
  This paper examines how resource sharing and contention affect two widely implemented but underdocumented features: Bias-Free Branch Prediction and Branch History Speculation.<n>We show that these features can inadvertently modify the Branch History Buffer (BHB) update behavior and create new primitives that trigger malicious mis-speculations.<n>We present three novel attack primitives: two Spectre attacks, namely Spectre-BSE and Spectre-BHS, and a cross-privilege control flow side-channel attack called BiasScope.
  arXiv  Detail & Related papers  (2025-06-08T19:46:43Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Quantum inspired factorization up to 100-bit RSA number in polynomial time [0.0]
  We attack the RSA factorization building on Schnorr's mathematical framework.<n>We factorize RSA numbers up to 256 bits encoding the optimization problem in quantum systems.<n>Results do not currently undermine the security of the present communication infrastructure.
  arXiv  Detail & Related papers  (2024-10-21T18:00:00Z)
• Homomorphic Polynomial Public Key Cryptography for Quantum-secure Digital Signature [0.7864304771129751]
  In their 2022 study, Kuang et al. introduced Multivariable Polynomial Public Key (MPPK) cryptography. They extended MPPK into Homomorphic Polynomial Public Key (HPPK), employing homomorphic encryption for large hidden ring operations.
  arXiv  Detail & Related papers  (2023-11-15T13:54:23Z)
• Notes on Small Private Key Attacks on Common Prime RSA [0.0]
  We point out critical deficiencies in lattice-based cryptanalysis of common prime RSA presented in this paper. We offer an illustration of small private key attacks on common prime RSA.
  arXiv  Detail & Related papers  (2023-10-19T08:27:18Z)
• Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH [5.398058794903461]
  The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves. We introduce a new quantum-time algorithm to solve IsERP for isogenies whose degrees are odd and have $O(loglog p)$ many prime factors.
  arXiv  Detail & Related papers  (2023-05-31T14:30:32Z)
• Spatial-Frequency Discriminability for Revealing Adversarial Perturbations [53.279716307171604]
  Vulnerability of deep neural networks to adversarial perturbations has been widely perceived in the computer vision community. Current algorithms typically detect adversarial patterns through discriminative decomposition for natural and adversarial data. We propose a discriminative detector relying on a spatial-frequency Krawtchouk decomposition.
  arXiv  Detail & Related papers  (2023-05-18T10:18:59Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• Failing gracefully: Decryption failures and the Fujisaki-Okamoto transform [3.437656066916039]
  We introduce two security games related to finding decryption failures. One captures the computationally hard task of using the public key to find a decryption failure. The other captures the statistically hard task of searching the random oracle for key-independent failures.
  arXiv  Detail & Related papers  (2022-03-18T22:39:08Z)
• Backflash Light as a Security Vulnerability in Quantum Key Distribution Systems [77.34726150561087]
  We review the security vulnerabilities of quantum key distribution (QKD) systems. We mainly focus on a particular effect known as backflash light, which can be a source of eavesdropping attacks.
  arXiv  Detail & Related papers  (2020-03-23T18:23:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.