Solved

Why are prime numbers so important in encryption?

Posted on 2007-03-28
8
2,683 Views
Last Modified: 2008-01-09
Why are prime numbers so important in encryption? Considering that there is many ways of finding these numbers, even very big ones and "paper and pencil" systems are extremely fast (all pure integer maths) with very big numbers, it seems odd.

Or have I got it wrong somehow?
0
Comment
Question by:Richard Quadling
  • 3
  • 3
  • 2
8 Comments
 
LVL 18

Accepted Solution

by:
PowerIT earned 300 total points
ID: 18806840
Prime numbers are used in assymetric encryption.
The complexity of some solving some mathematical problem in one direction as opposed to the simplicity of the operation in the other direction makes it suited for assymetric encryption.
The factoring of prime numbers is one of those complex problems. Others are
It's very easy to calculate two prime numbers and multiply them. Factoring that large number back to the two primes is extermely hard.
So, the public and privare keys are made up from a pair of large prime number.
As long as noone finds an easy way to factor into primes, then it stays safe. That may change in the future.
A practical algorithm using this is RSA. Have a look here how it is done: http://world.std.com/~franl/crypto/rsa-guts.html
Or more detailed: http://en.wikipedia.org/wiki/RSA

J.
0
 
LVL 18

Assisted Solution

by:PowerIT
PowerIT earned 300 total points
ID: 18806863
Been a bit to fast. Some typos above, my apology.
Other examples of such complex problems are the calculation of discrete logarithms in a finite field, elliptic curves and the knapsack algorithm.

J.
0
 
LVL 40

Author Comment

by:Richard Quadling
ID: 18807451
Aha! I see. I think.

Thanks.
0
Live: Real-Time Solutions, Start Here

Receive instant 1:1 support from technology experts, using our real-time conversation and whiteboard interface. Your first 5 minutes are always free.

 
LVL 3

Assisted Solution

by:hackman_3vilGuy
hackman_3vilGuy earned 200 total points
ID: 18825267
Prime numbers are very hard to find. Although you can find some with pen + pencil methods, when the numbers have hundreds of digits there is no known way to find them. It takes a huge amount of processing power to factorize them as it must be done through brute force
0
 
LVL 40

Author Comment

by:Richard Quadling
ID: 18834973
Hackman_3vilGuy, but there are lists of these numbers and a lookup on a list is pretty quick.

0
 
LVL 3

Assisted Solution

by:hackman_3vilGuy
hackman_3vilGuy earned 200 total points
ID: 18835242
The problem is that there are an infinite number of prime numbers in the universe so a list of all the primes at the sizes used by governments are completely infeasible. At 4096+ bits it is pretty impossible.
Remember the bank / government / whoever will generate 2 prime numbers p and q that can be as big as they want. They then multiply them and publish n which is p * q. So the attacker has p*q, but to decrypt the message needs to know what p and q are separately. There are methods that speed this up but they dont improve much over brute force. Not only is it hard to factorize them as there is no mathematical formula, it is hard to generate the primes to test with in the first place. RSA encryption (used online) relies on the difficulty of factorizing these gigantic prime numbers as well as another difficult problem (the RSA problem).

As of 2005, the largest number factored by a general-purpose factoring algorithm was 663 bits long, using a state-of-the-art distributed implementation. RSA keys are typically 1024–2048 bits long. Some experts believe that 1024-bit keys may become breakable in the near term (though this is disputed); few see any way that 4096-bit keys could be broken in the foreseeable future.
0
 
LVL 18

Assisted Solution

by:PowerIT
PowerIT earned 300 total points
ID: 18835259
R,

the complexity is not in finding primes, but in factoring TO primes of the multiplication of two primes.
So given a large number find the two originating primes.

J.
0
 
LVL 40

Author Comment

by:Richard Quadling
ID: 18835923
OK. Getting factors of a number is hard enough. Getting prime factors of the product of two large primes does sound sort of ridiculously hard. But not impossible.

Whilst brute force is slow, you would only need to run this once.

http://en.wikipedia.org/wiki/Largest_known_primee - the largest prime is just under 10 MILLION digits long!!!

Say the next one is 11million digits long.

The product is going to be over 20 million digits long.

Now find the factors and only the PRIME factors.

And that's why.

Ok.

Thanks for all of that.

I bet all those botnets out there could be useful if all they were doing was calculating primes rather than sending SPAM.

Thanks again all.

Richard.
0

Featured Post

Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Ransomware .crypt files... 9 150
Having login certificate problem 3 3,385
tools to determine hash type or possibly encryption/encoding 4 293
One drive and bitlocker policy help 1 134
Explore the encryption capabilities built into Google Apps and how these features can help you meet privacy policy and regulatory compliance, but are not a full solution. Understand and compare the most popular email encryption services for Google A…
There are many Password Managers (PM) out there to choose from. PM's can help with your password habits and routines, but they should not be a crutch you rely on too heavily. I also have an article for company/enterprise PM's.
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…
With Secure Portal Encryption, the recipient is sent a link to their email address directing them to the email laundry delivery page. From there, the recipient will be required to enter a user name and password to enter the page. Once the recipient …

808 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question