Understanding RSA Encryption: What Stops Attackers from Calculating d?

[Yankel]

Hello guys,

I need your help in understanding something about the RSA encryption.

You start with two primes, p and q, from which you get n and phi(n)

then you choose a number e such that it is larger than 1 but smaller than phi(n) and co-prime of phi(n)

then you use Euclid's algorithm to find d for the decryption process.

the public key is (e,n) and the private is (d,n)

What I want to know, is what is stopping the ones who want to break the encryption from calculating d just like the one who encrypted it did ?

all I see in Euclid's algorithm is the use of e and n, which are given as a public key. so what stops one from finding d, even when he doesn't have it initially ?

what am I missing here ?

I thought that the point was to give n, but to be able to do decryption only if you know p and q, when it's very hard to break n into p and q. but I can't see it coming in the algorithm.

thanks !

 

[chisigma]

Hello guys,

I need your help in understanding something about the RSA encryption.

You start with two primes, p and q, from which you get n and phi(n)

then you choose a number e such that it is larger than 1 but smaller than phi(n) and co-prime of phi(n)

then you use Euclid's algorithm to find d for the decryption process.

the public key is (e,n) and the private is (d,n)

What I want to know, is what is stopping the ones who want to break the encryption from calculating d just like the one who encrypted it did ?

all I see in Euclid's algorithm is the use of e and n, which are given as a public key. so what stops one from finding d, even when he doesn't have it initially ?

what am I missing here ?

I thought that the point was to give n, but to be able to do decryption only if you know p and q, when it's very hard to break n into p and q. but I can't see it coming in the algorithm.

thanks !

The phases in which Bob sends Alice a message encrypted with RSA are as follows ...

a) Alice chooses two primes p and q and computes their product n = p q ...

b) Alice computes $\displaystyle \varphi (n) = (p-1)\ (q-1)$...

c) Alice chooses a number e such that $\displaystyle 1 < e < \varphi(n)$ and $\displaystyle \text{gcd}\ [e,\varphi(n)] = 1$ ...

d) Alice communicates in clear at Bob e and n ...

e) Bob communicates to Alice the message m encrypted as $\displaystyle c = e^{m}\ \text{mod}\ n$...

f) Alice computes $\displaystyle d = e^{-1}\ \text{mod}\ \varphi (n)$...

g) Alice decrypts the message to Bob by computing $\displaystyle m = c^{d}\ \text{mod}\ n$...

The system security is guaranteed by the fact that Alice only and no one else [even Bob ...] knows p and q then only she can perform the steps b), f) and g). One way to break the code is to obtain p and q by n, knowing that n = p q. This operation is called 'factorization of n' and if n is 'very large' it is a very difficult task. Another way to breack the code is to compute'directly' $\displaystyle m = \log_{e} c\ \text{mod}\ n$ but also that way for n 'very large'is a difficult task...

Kind regards

$\chi$ $\sigma$

 

[Deveno]

Hello guys,

I need your help in understanding something about the RSA encryption.

You start with two primes, p and q, from which you get n and phi(n)

then you choose a number e such that it is larger than 1 but smaller than phi(n) and co-prime of phi(n)

then you use Euclid's algorithm to find d for the decryption process.

the public key is (e,n) and the private is (d,n)

What I want to know, is what is stopping the ones who want to break the encryption from calculating d just like the one who encrypted it did ?

all I see in Euclid's algorithm is the use of e and n, which are given as a public key. so what stops one from finding d, even when he doesn't have it initially ?

what am I missing here ?

I thought that the point was to give n, but to be able to do decryption only if you know p and q, when it's very hard to break n into p and q. but I can't see it coming in the algorithm.

thanks !

Just to make it real, here is my public key:

$n = 2022479561$

$e = 43$

I have sent an 4-letter plaintext encoded with a simple 2-digits-per-letter numerical substitution cipher. The plaintext has then been encoded using my known public key. This plaintext is the password to a top-secret government installation computer workstation (which is not, oddly enough, case-sensitive).

You have intercepted this ciphertext with full knowledge of my encryption methods:

$39828349$

Your mission, should you decide to accept it, is to decode the English password within 24 hours, before national security protocols demand it be changed.

(And please hope my encryption machine is working right...after the power outage, it started behaving...oddly).

 

[I like Serena]

It's a good thing we have W|M, who cracked it in seconds (I wouldn't like to do it by hand).
I see where the inspiration was coming from.

 

[Deveno]

I purposely created this example so that it could be done with the aid of a calculator, or internet web sites. The encryption is considerably weaker than a 1024-bit encryption would be. W|A easily factors fairly large integers. I just hoped to give the original poster a sense of how much work is involved.

 

[I like Serena]

Here's another one.

e=31 and n=15241578753238836751577503665157706318489955952973821.
The message is 5757802897340642176360685760439519225010273635388724.

It's a starred problem from a course in abstract algebra.

Interestingly, W|M cracks this one in seconds as well.
Hmm... I'm starting to wonder how big n has to be before W|M cannot crack it anymore within 24 hours...

 

[Nono713]

Here's another one.

e=31 and n=15241578753238836751577503665157706318489955952973821.
The message is 5757802897340642176360685760439519225010273635388724.

It's a starred problem from a course in abstract algebra.

Interestingly, W|M cracks this one in seconds as well.
Hmm... I'm starting to wonder how big n has to be before W|M cannot crack it anymore within 24 hours...

I think the limit for an individual is around a 400/500-bit semiprime modulus. For reference, msieve can factor RSA-100 (100 digits, i.e. 330 bits) in under a day on conventional hardware. Last time I checked a couple years ago it took about 20 hours on my old laptop on a single core, I would hope it can do it much faster nowadays. And your n is only 160 bits long. Basically, factoring is hard :p

It depends on the prime factorization, though, of course. Semiprimes are the hardest, if your modulus has a prime factor smaller than 30-40 digits it will instantly succumb to ECM, after that the quadratic and number field sieves take over and basically crunch at your number until they succeed.

To answer OP's question, the point is that to calculate $d$ you need to know $\varphi(n)$. Which requires factoring $n$. Which is believed to be hard given sufficiently large $n$ (say, 1024-2048 bits). Of course, breaking RSA is not known to require factoring $n$ (it is an open problem whether it is the only way to break it in general) but factoring $n$ definitely amounts to breaking RSA, as like you said, in that case anyone could compute $d$ from $e$ and $n$ and defeat the encryption scheme.

 

[Deveno]

As might be apparent, the chief appeal of RSA is its "cost-effectiveness", the encryption scheme and decryption routines are easy to code, and for a sufficiently large key-length, the time it takes to crack it may well be longer than the life-time of the utility of the information encrypted.

However, it *is* susceptible to concerted brute-force attacks, and is therefore not appropriate for highly sensitive and enduring information.

As with any kind of coded message, someone has to possesses the knowledge of how to "de-code" it, and often the simplest method to "crack a code" is to simply steal this information from whoever possesses it. A secret is only as safe as the person keeping it, no matter how sophisticated their methods.

 

[Yankel]

Very interesting and enlightening, thanks guys !