DZone
Security Zone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
  • Refcardz
  • Trend Reports
  • Webinars
  • Zones
  • |
    • Agile
    • AI
    • Big Data
    • Cloud
    • Database
    • DevOps
    • Integration
    • IoT
    • Java
    • Microservices
    • Open Source
    • Performance
    • Security
    • Web Dev
DZone > Security Zone > RSA Duplication Flaws: Prime, Exponent, and Modulus

RSA Duplication Flaws: Prime, Exponent, and Modulus

Implementation flaws in RSA encryption make it less secure in practice than in theory.

John Cook user avatar by
John Cook
·
Feb. 19, 19 · Security Zone · Tutorial
Like (1)
Save
Tweet
4.46K Views

Join the DZone community and get the full member experience.

Join For Free

Implementation flaws in RSA encryption make it less secure in practice than in theory.

RSA encryption depends on five numbers:

  • Large primes p and q
  • The modulus n = pq
  • Encryption key e
  • Decryption key d

The numbers p, q, and d are kept secret, and the numbers e and n are made public. The encryption method relies on the assumption that, in practice, one cannot factor n into p and q.

All five numbers should be chosen anew for each certificate [1], but in practice, numbers are sometimes reused.

Duplicate Primes

The numbers p and q should be unique to each use of the method, but in practice, there have been instances of duplicate primes, where two instances may have one of their two primes in common, which lets you factor the modulus using the Euclidean algorithm.

Duplicate Encryption Keys

The encryption key e does not need to be unique, or so we thought. In practice, the encryption exponent e is usually 65537, i.e. 216 + 1, because this makes implementation faster. One study found that this exponent was used 99.5 percent of the time. However, this allows an attack on RSA encryption if any of the bits of p or q can be recovered from computer memory. More on this here.

Duplicate Moduli

The author of this post found several instances of certificates with shared moduli. One way this could happen is if a negligent certificate authority recycles p, q, and n, only generating new e and d pairs for each user. If you and someone else share a modulus n, you can use your (e, d) pair to factor n, and from knowing their public key e, you can recover their private key d.

Duplicate moduli cannot happen by chance. As described here, the probability of having one shared prime due to random selection is roughly the probability of winning the Powerball jackpot 40 times in a row. The probability of having two shared primes due to random selection is inconceivably small.

Related Posts

  • Factoring RSA numbers
  • Economics, power laws, and password cracking

[1] Everyone agrees that p, q, and hence n should be unique. This also means that d will be unique. But there is disagreement over whether the exponent e should be unique, though reusing e does lead to a possible attack as described here.

PRIME (PLC) Modulus (algebraic number theory)

Published at DZone with permission of John Cook, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • How Low Code Demands More Creativity From Developers
  • When Writing Code Isn't Enough: Citizen Development and the Developer Experience
  • Top 7 Features in Jakarta EE 10 Release
  • Modern Application Security Requires Defense in Depth

Comments

Security Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • MVB Program
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends:

DZone.com is powered by 

AnswerHub logo