Solved

Why are prime numbers so important in encryption?

Posted on 2007-03-28
8
2,652 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:RQuadling
  • 3
  • 3
  • 2
8 Comments
 
LVL 18

Accepted Solution

by:
PowerIT earned 300 total points
Comment Utility
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
Comment Utility
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:RQuadling
Comment Utility
Aha! I see. I think.

Thanks.
0
 
LVL 3

Assisted Solution

by:hackman_3vilGuy
hackman_3vilGuy earned 200 total points
Comment Utility
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 40

Author Comment

by:RQuadling
Comment Utility
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
Comment Utility
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
Comment Utility
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:RQuadling
Comment Utility
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

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

Join & Write a Comment

If you are on a Windows computer and decide to protect a file with sensitive data, you can encrypt the file, password protect it or rely on steganography (hiding a file in an image). This technique is especially useful because unless someone knows t…
Envision that you are chipping away at another e-business site with a team of pundit developers and designers. Everything seems, by all accounts, to be going easily.
Polish reports in Access so they look terrific. Take yourself to another level. Equations, Back Color, Alternate Back Color. Write easy VBA Code. Tighten space to use less pages. Launch report from a menu, considering criteria only when it is filled…
This tutorial demonstrates a quick way of adding group price to multiple Magento products.

743 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now