View the Most Wanted LQ Wiki articles.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org RSA prime numbers?
 Linux - Security This forum is for all security related questions. Questions, tips, system compromises, firewalls, etc. are all included here.

Notices

 08-10-2002, 09:56 PM #1 tarballedtux Member   Registered: Aug 2001 Location: Off the coast of Madadascar Posts: 498 Rep: RSA prime numbers? 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.
 08-10-2002, 10:53 PM #2 Ionized Member   Registered: Jul 2002 Location: Chicago Suburbs Distribution: Slackware 8.0 Posts: 51 Rep: 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...
 08-10-2002, 10:54 PM #3 neo77777 LQ Addict   Registered: Dec 2001 Location: Brooklyn, NY Distribution: *NIX Posts: 3,704 Rep: 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 Last edited by neo77777; 08-10-2002 at 10:56 PM.
 08-12-2002, 04:35 PM #4 TruckStuff Member   Registered: Apr 2002 Posts: 498 Rep: My understanding of encryption is that you are picking two numbers that are so big that the product is essentially 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?).
 08-12-2002, 04:47 PM #5 acid_kewpie Moderator   Registered: Jun 2001 Location: UK Distribution: Gentoo, RHEL, Fedora, Centos Posts: 43,394 Rep: i think the correct word is Primeosity.. or was it Primeositaciousness?
 08-12-2002, 04:52 PM #6 neo77777 LQ Addict   Registered: Dec 2001 Location: Brooklyn, NY Distribution: *NIX Posts: 3,704 Rep: No what they are really refering to are relative prime numbers, which are the numbers tjhat have no factors in common besides 1.
 08-12-2002, 05:25 PM #7 TruckStuff Member   Registered: Apr 2002 Posts: 498 Rep: 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?
 08-13-2002, 06:37 PM #8 tyler_durden Member   Registered: May 2001 Posts: 125 Rep: 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.
08-13-2002, 08:38 PM   #9
tied2
Member

Registered: Jun 2002
Location: Florida
Distribution: Redhat, FreeBSD, FC 6
Posts: 220

Rep:
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?

 08-13-2002, 10:05 PM #10 A-dummy Member   Registered: Jun 2002 Location: Kanpur,India Distribution: RH-7.0 , 7.3 Posts: 130 Rep: 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 ....
08-13-2002, 10:36 PM   #11
TruckStuff
Member

Registered: Apr 2002
Posts: 498

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

08-13-2002, 11:07 PM   #12
tyler_durden
Member

Registered: May 2001
Posts: 125

Rep:
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

 08-14-2002, 11:27 AM #13 Ionized Member   Registered: Jul 2002 Location: Chicago Suburbs Distribution: Slackware 8.0 Posts: 51 Rep: 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.
 08-14-2002, 11:57 AM #14 A-dummy Member   Registered: Jun 2002 Location: Kanpur,India Distribution: RH-7.0 , 7.3 Posts: 130 Rep: www.rsasecurity.com .......
08-14-2002, 03:12 PM   #15
tyler_durden
Member

Registered: May 2001
Posts: 125

Rep:
Quote:
 www.rsasecurity.com .......

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.