Linux - SecurityThis forum is for all security related questions.
Questions, tips, system compromises, firewalls, etc. are all included here.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

In the second paragraph the author states that two prime numbers are multiplied together to get a bigger prime number in order to make a key. Well it didn't take me long to do a double take on that sentence. How can the bigger number be prime if two smaller prime numbers were used to generate the the bigger prime number. i.e.

Two really small prime numbers. 5 and 3. According to the article you can make a bigger prime number by multiplying two smaller prime numbers.

5*3=15

15 isn't prime at all! 1*15=15 and 3*5=15

Can anyone clarify this apparent mathematical goofup.
No wonder it takes along time to find a prime number using this method.

This is absolute absurd, if you multiply pime numbers to get even bigger prime number it is guaranteed that this bigger prime number will be devisible by the primes it was created with - which defeats priminess of this even bigger prime number, I guess the author and the editor as well are not good in math nor encription, hence, they must be dreaming on ludes.
Mods: can you move this thread to general
LOL

My understanding of encryption is that you are picking two numbers that are so big that the product is <i>essentially</i> unfactorable. We are talking about numbers that are 200 digits or more in length. When you multiply them together, you get a 400 digit or more number. Even using the fastest factoring algorithms on the fastest supercomputers, it would still take tens of thousands of years to properly test a number of this size for primeness (is that a word?).

Yes, I understand that. But my point still stands. I heard this comparison once: in order to have all the possible factors of an RSA number on CDs, the total mass of the CDs would be something like 10 times greater than the mass that scientisits theorize is needed to form a black hole. So unless you can create a black hole 10 times over using only CDs, the RSA numbers are essentially unfactorable.

Perhaps someone with some more expertise could enter this conversation?

first, two primes multiplied together makes the product NOT prime. the strength of rsa is that you have a number that only has 2 non-trivial factors

i think what the author ment is that you take to large primes p and q and multiply them together to get n. this n is used as the moduls in rsa.

The strength of RSA is in the fact you can't factor n in a resonable amount of time. (remember it only has 2 non-trivial factors).

0h, and steve - the comment about 10,000 years assumes that you only have the current algorithms. its possible that a fastor way of factoring numbers doens't get discovered. also, there have been some recent developments (bernseins sieve) that suggest it might be possible to factor numbers in a more resonable time.

Last edited by tyler_durden; 08-13-2002 at 06:40 PM.

Originally posted by neo77777 I guess the author and the editor as well are not good in math nor encription, hence, they must be dreaming on ludes.
Mods: can you move this thread to general
LOL

_____________________________________
can you still get those?

For those who are interested in checking for prime numbers ,
here is an interesting news : A new algorithm of proving a prime
number prime in Polynomial time has been discovered (announced about a week ago)....for more: http://msn.com.com/2100-1104-949170.html?type=pt

& btw these guys are from my college , ahem ahem ....

Does anyone have a link to an article or articles on exactly how these numbers p and q are used? More specifically, how the public and private keys relate to the 2 numbers multiplied together. I understand that there's a really big number produced (usualy around 1024 bits) but I don't understand exactly how that number is used...

here, to understand why it works you prolly need to do a little brushing up on some math. specifically, (and this isn't spelled right) phi is oliers totent funcion or the number of prime numbers less then n (its more complicated, but thats the basic idea). (and ^ means to the power)

Select two primes p and q
Calculate n = p q
Calculate phi(n) = (p-1)(q-1)
Select e such that 1 < e < phi(n) and gcd(phi(n),e) = 1
Calculate d = e(^-1) mod phi(n)
Public key KU = {e,n}
Private key KR = {d,n}

to encrypt you take plaintext ^ (e) mod n, and to decrypt you take cryptext ^(d) mod n =>plaintext

given e, in order to find d you need phi, which is really hard to find without knowing p or q.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.