DZone
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
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones AWS Cloud
by AWS Developer Relations
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Partner Zones
AWS Cloud
by AWS Developer Relations

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 · Tutorial
Like (1)
Save
Tweet
Share
4.77K 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

  • Distributed Tracing: A Full Guide
  • How Elasticsearch Works
  • Create a CLI Chatbot With the ChatGPT API and Node.js
  • Use AWS Controllers for Kubernetes To Deploy a Serverless Data Processing Solution With SQS, Lambda, and DynamoDB

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • 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: