# Thread: Math Behind RSA Encrytion/Decryption

1. ## Math Behind RSA Encrytion/Decryption

I am trying to solve a question for my Number Theory / Intro To Cryptography class. I have been given a question to decrypt a message encoded with the RSA scheme. The encryption with done with a provided n, and e. I am told to compute the d, and to decrypt the message.

In order to compute d I need to compute
$\displaystyle ed \equiv 1 \mod(\phi$ (n))

My issue is that to compute $\displaystyle \phi(n)$ I need to factor n into its original two primes. But this is very hard when n is large (which it is). Is there an easier way to compute $\displaystyle \phi(n)$?

Thanks

2. Originally Posted by apsis
I am trying to solve a question for my Number Theory / Intro To Cryptography class. I have been given a question to decrypt a message encoded with the RSA scheme. The encryption with done with a provided n, and e. I am told to compute the d, and to decrypt the message.

In order to compute d I need to compute
$\displaystyle ed \equiv 1 \mod(\phi$ (n))

My issue is that to compute $\displaystyle \phi(n)$ I need to factor n into its original two primes. But this is very hard when n is large (which it is). Is there an easier way to compute $\displaystyle \phi(n)$?

Thanks
Isn't the difficulty in factoring $\displaystyle n$ the whole point of the encryption system?

If there was an easy way to compute $\displaystyle \varphi (n)$ then the cipher would not be secure.

CB

3. what is your $\displaystyle n$ and $\displaystyle e$?

4. Thats what I figured ... Its okay I just wrote a computer program to factor the n which is relatively small... and then it was easy to calculate everything else out as e is provided!

I just wanted to know if there is some other approach besides the brute force factoring .. which there isn't!

5. Originally Posted by apsis
Thats what I figured ... Its okay I just wrote a computer program to factor the n which is relatively small... and then it was easy to calculate everything else out as e is provided!

I just wanted to know if there is some other approach besides the brute force factoring .. which there isn't!
I programmed a co-prime finder as well. The link is in my sig, if you're interested.

6. Originally Posted by apsis
Thats what I figured ... Its okay I just wrote a computer program to factor the n which is relatively small... and then it was easy to calculate everything else out as e is provided!

I just wanted to know if there is some other approach besides the brute force factoring .. which there isn't!
Or at least that is what NSA/GCHQ want you to beleive

CB