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
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
What's in store for DevOps in 2023? Hear from the experts in our "DZone 2023 Preview: DevOps Edition" on Fri, Jan 27!
Save your seat
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. RSA Numbers and Factoring

RSA Numbers and Factoring

RSA is perhaps the most widely-known acronym in the world of security and encryption. So, let's find out a little more about how it works in the post. Click here for more!

John Cook user avatar by
John Cook
·
Aug. 27, 18 · Presentation
Like (1)
Save
Tweet
Share
4.53K Views

Join the DZone community and get the full member experience.

Join For Free

It's much easier to multiply numbers together than to factor them apart. That's the basis of RSA encryption.

In particular, the RSA encryption scheme rests on the assumption that when given two large primes p and q, one can quickly find the product pq, but it is much harder to recover the factors p and q. For the size numbers, you'll see in math homework, say two or three digits, factoring is a little harder than multiplication. But, when you get into numbers that are hundreds of digits long, factoring in orders of magnitude becomes much more difficult. Or, so it seems. There's no proof that factoring has to be as difficult as it appears to be. And, sometimes products have a special structure that makes factoring easier, hence the need for so-called safe primes.

The ability to factor large products quickly is sufficient to break RSA, but we don't know whether it's necessary. Conceivably, there is an efficient algorithm for breaking RSA encryption that does not require factoring or that could be turned into an efficient algorithm for factoring. But, no such algorithm is publicly known, and people who use RSA are betting that such an algorithm doesn't exist.

Factoring Challenges

How hard is it to factor large products? We can get some idea from contest results. In 1991, RSA Laboratories published a list of factoring challenges, the so-called RSA numbers. The smallest of these, RSA-100, was a 100-digit number that was factored shortly after the challenge was announced.

Last week, Noblis, Inc. announced that their company had factored RSA-230, factoring a 230-digit number into two 115-digit primes. Because multiplication is so much easier than factoring, it's simple to verify the result even though it was hard to produce it.

RSA232 = 17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689
p = 4528450358010492026612439739120166758911246047493700040073956759261590397250033699357694507193523000343088601688589
q = 3968132623150957588532394439049887341769533966621957829426966084093049516953598120833228447171744337427374763106901

if RSA232 == p*q:
    print("Check!")


A slightly larger RSA challenge problem — RSA-232 had previously been factored. The RSA numbers larger than RSA-232 have not been factored at the time of writing this post.

(RSA-232 has 232 decimal digits. But, some RSA numbers are named after their length in bits, and some are named after their length in digits. For example, RSA-704 is smaller than RSA-230, because the former has 704 bits and the latter has 230 decimal digits.)

Number Field Sieve

The expected time required to factor a semiprime (product of two primes) using the general number field sieve is O( exp( c log( n) 1/3 log log( n) 2/3) ) where the value of c is a little elusive. Some sources say c = (64/9) 1/3 = 1.92, but as I understand it, that value is based on a heuristic and the smallest rigorously proven value is c = 2.77.

Using the more optimistic value of c, we estimate about 10 23 operations would be necessary to factor RSA-230.

Shor's Quantum Algorithm

In theory, Shor's algorithm could factor semiprimes very quickly using a quantum computer. At this time, the largest number that has been factored with Shor's algorithm is 21. So, it's not much of a threat to crypto security yet, but it has enormous potential. If a large-scale quantum computer were available, Shor's algorithm could factor primes in O( log( n)² log(log( n)) log(log(log( n))) ) time [1].

This means that Shor's algorithm could factor RSA-230 in about 3 million operations.

Related Posts

  • How long does it take to find large primes?
  • Elliptic curves over finite fields

[1] Obligatory old joke: What sound does a number theorist make when drowning? log log log ...

Factor (programming language) Algorithm

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 ChatGPT Is Revolutionizing the World of Natural Language Processing
  • ChatGPT vs. GPT3: The Ultimate Comparison
  • 5 Data Mesh Best Practices From 4 Data Leaders
  • Required Knowledge To Pass AWS Certified Data Analytics Specialty Exam

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: