RSA prime numbers?

tarballedtux · 08-10-2002, 09:56 PM

When cruising LinuxSecurity.com I came across a link about RSA prime number calculations.

http://zdnet.com.com/2100-1104-949170.html

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.

Ionized · 08-10-2002, 10:53 PM

Yes, you'd be correct, 2 primes multiplied together don't make another prime. Is this just a missprint? I too am wondering what's going on...

neo77777 · 08-10-2002, 10:54 PM

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

TruckStuff · 08-12-2002, 04:35 PM

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?).

acid_kewpie · 08-12-2002, 04:47 PM

i think the correct word is Primeosity.. or was it Primeositaciousness?

neo77777 · 08-12-2002, 04:52 PM

No what they are really refering to are relative prime numbers, which are the numbers tjhat have no factors in common besides 1.

TruckStuff · 08-12-2002, 05:25 PM

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?

tyler_durden · 08-13-2002, 06:37 PM

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.

tied2 · 08-13-2002, 08:38 PM

Quote:

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?

A-dummy · 08-13-2002, 10:05 PM

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

....

TruckStuff · 08-13-2002, 10:36 PM

Quote:

The strength of RSA is in the fact you can't factor n in a resonable amount of time.

Holy crap, you mean I was almost sort of right??

I never really understood that myself until I started talking to the likes of you Dan.

And thanks for chiming in. I was hoping that you would so that we could get some answers.

tyler_durden · 08-13-2002, 11:07 PM

Quote:

I never really understood that myself until I started talking to the likes of you Dan.

i knew i would turn you into a nerd one of these days. hehe

Ionized · 08-14-2002, 11:27 AM

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...

Thanks.

A-dummy · 08-14-2002, 11:57 AM

www.rsasecurity.com .......

tyler_durden · 08-14-2002, 03:12 PM

Quote:

www.rsasecurity.com .......

thats helpful.

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.