LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Linux Forums > Linux - Security
User Name
Password
Linux - Security This forum is for all security related questions.
Questions, tips, system compromises, firewalls, etc. are all included here.

Notices

Closed Thread
 
Search this Thread
Old 08-10-2002, 09:56 PM   #1
tarballedtux
Member
 
Registered: Aug 2001
Location: Off the coast of Madadascar
Posts: 498

Rep: Reputation: 30
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.
 
Old 08-10-2002, 10:53 PM   #2
Ionized
Member
 
Registered: Jul 2002
Location: Chicago Suburbs
Distribution: Slackware 8.0
Posts: 51

Rep: Reputation: 15
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...
 
Old 08-10-2002, 10:54 PM   #3
neo77777
LQ Addict
 
Registered: Dec 2001
Location: Brooklyn, NY
Distribution: *NIX
Posts: 3,704

Rep: Reputation: 55
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.
 
Old 08-12-2002, 04:35 PM   #4
TruckStuff
Member
 
Registered: Apr 2002
Posts: 498

Rep: Reputation: 30
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?).
 
Old 08-12-2002, 04:47 PM   #5
acid_kewpie
Moderator
 
Registered: Jun 2001
Location: UK
Distribution: Gentoo, RHEL, Fedora, Centos
Posts: 43,384

Rep: Reputation: 1963Reputation: 1963Reputation: 1963Reputation: 1963Reputation: 1963Reputation: 1963Reputation: 1963Reputation: 1963Reputation: 1963Reputation: 1963Reputation: 1963
i think the correct word is Primeosity.. or was it Primeositaciousness?
 
Old 08-12-2002, 04:52 PM   #6
neo77777
LQ Addict
 
Registered: Dec 2001
Location: Brooklyn, NY
Distribution: *NIX
Posts: 3,704

Rep: Reputation: 55
No what they are really refering to are relative prime numbers, which are the numbers tjhat have no factors in common besides 1.
 
Old 08-12-2002, 05:25 PM   #7
TruckStuff
Member
 
Registered: Apr 2002
Posts: 498

Rep: Reputation: 30
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?
 
Old 08-13-2002, 06:37 PM   #8
tyler_durden
Member
 
Registered: May 2001
Posts: 125

Rep: Reputation: 15
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.
 
Old 08-13-2002, 08:38 PM   #9
tied2
Member
 
Registered: Jun 2002
Location: Florida
Distribution: Redhat, FreeBSD, FC 6
Posts: 220

Rep: Reputation: 30
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?
 
Old 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: Reputation: 15
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 ....
 
Old 08-13-2002, 10:36 PM   #11
TruckStuff
Member
 
Registered: Apr 2002
Posts: 498

Rep: Reputation: 30
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.
 
Old 08-13-2002, 11:07 PM   #12
tyler_durden
Member
 
Registered: May 2001
Posts: 125

Rep: Reputation: 15
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
 
Old 08-14-2002, 11:27 AM   #13
Ionized
Member
 
Registered: Jul 2002
Location: Chicago Suburbs
Distribution: Slackware 8.0
Posts: 51

Rep: Reputation: 15
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.
 
Old 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: Reputation: 15
www.rsasecurity.com .......
 
Old 08-14-2002, 03:12 PM   #15
tyler_durden
Member
 
Registered: May 2001
Posts: 125

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


Closed Thread


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
C Prime Generator Chrax Programming 9 12-23-2004 01:02 AM
c++ prime numbers loop problem muddlnx Programming 6 08-31-2004 10:14 PM
Adding numbers, break on non-numbers... Cruger Programming 1 03-22-2004 09:18 AM
Algo for Relatively prime No. LinuxTiro Programming 5 11-17-2003 09:02 PM
mersenne prime number zetsui Linux - Software 3 08-23-2003 01:23 PM


All times are GMT -5. The time now is 09:19 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration