RSA prime numbers?

Ionized · 08-14-2002, 03:43 PM

For the math side of this....does it matter what number e is as long as it's relatively prime to phi?

Also, I thought that to calculate d you use the formula (e*d - 1) (mod phi) = 0. I've been trying to figure this out using small prime numbers, but I can't quite figure it out...

TruckStuff · 08-14-2002, 07:44 PM

Quote:

Originally posted by tyler_durden

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.

Show off.....

tyler_durden · 08-14-2002, 10:50 PM

Quote:

Show off.....

yah, you can tell when i get bored at work. plus, it was better then posting rsasecurity.com

Quote:

does it matter what number e is as long as it's relatively prime to phi?

nope. alot of people use something like 2^32 +1 or something (i don't really remember) becuase its faster to do the calculations

Quote:

Also, I thought that to calculate d you use the formula (e*d - 1) (mod phi) = 0. I've been trying to figure this out using small prime numbers, but I can't quite figure it out...

i don't remember. i think you want to solve e*d = 1 (mod phi) using the euclidean, but i don't remember how.
if you drop me an email if you really want to know, i can look through my notes and remember how to do that. ouch, its been a while. it may take me a few days to get back to you.

mideast · 06-28-2008, 04:11 AM

hallo guys

could anybody find the prime numbers of the following number
376781096648655171476075046480384036003069767135878367046892404899787642486409
?

win32sux · 06-28-2008, 06:12 PM

Quote:

Originally Posted by mideast

hallo guys

could anybody find the prime numbers of the following number
376781096648655171476075046480384036003069767135878367046892404899787642486409
?

I'm closing this. Please do not resurrect dead threads. Maybe open a new thread for your question in the General forum. And I would suggest you make sure to provide some background about where your question is coming from unless you want to risk having your thread closed on the suspicion that it's a homework question.