Linux  Security This 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.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.

Introduction to Linux  A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free. 



08102002, 10:56 PM

#1

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



08102002, 11:53 PM

#2

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



08102002, 11:54 PM

#3

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; 08102002 at 11:56 PM.



08122002, 05:35 PM

#4

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



08122002, 05:47 PM

#5

Moderator
Registered: Jun 2001
Location: UK
Distribution: Gentoo, RHEL, Fedora, Centos
Posts: 43,414

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



08122002, 05:52 PM

#6

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.



08122002, 06:25 PM

#7

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?



08132002, 07:37 PM

#8

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 nontrivial 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 nontrivial 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; 08132002 at 07:40 PM.



08132002, 09:38 PM

#9

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?



08132002, 11:05 PM

#10

Member
Registered: Jun 2002
Location: Kanpur,India
Distribution: RH7.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/21001104949170.html?type=pt
& btw these guys are from my college , ahem ahem ....



08132002, 11:36 PM

#11

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.



08142002, 12:07 AM

#12

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



08142002, 12:27 PM

#13

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.



08142002, 12:57 PM

#14

Member
Registered: Jun 2002
Location: Kanpur,India
Distribution: RH7.0 , 7.3
Posts: 130
Rep:




08142002, 04:12 PM

#15

Member
Registered: May 2001
Posts: 125
Rep:

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) = (p1)(q1)
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.



Thread Tools 
Search this Thread 


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 07:49 AM.

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

Latest Threads
LQ News

