# Tag Info

6

As mikeazo notes in the comments, RSA operates on the ring $\mathbb Z / n\mathbb Z$ of integers modulo $n$, for a given modulus $n = pq$. In this ring, $$E(m) \cdot t^e \equiv m^e \cdot t^e \equiv (mt)^e \equiv E(mt)\ \pmod n.$$ In particular, for $n = 35$, $e = 23$, 17^{23} \cdot 2^{23} \equiv 33 \cdot 18 \equiv 594 \equiv 34 \equiv 34^{23}\ ...

5

You are correct in that knowing $\phi(n)$ it is trivial to get the private key back with a simple modular inversion. However, we are only given $e$ and $n$, and it turns out that computing $\phi(n)$ from $n$ alone is computationally equivalent to finding the factors of $n$. Namely, if you know $\phi(n) = (p-1)(q-1) = (p-1)(n/p - 1)$, you can recover $p$ by ...

4

In RSA encryption as practiced (that is, to encipher a message which is a short symmetric key), the message size after padding is fixed and equal to the modulus size. Thus the size of the message has no impact on performance. Calculating a modular inverse is performed only during key generation, that is seldom. Also, it has low cost compared to generating ...

3

The performance bottleneck with RSA is the modular exponentiation operation. On the other hand, if you are interested in public key encryption performance, perhaps RSA is not the correct tool. RSA is actually fairly fast during its encryption operation; however it is quite slow during the decryption. If you care about decryption performance, you may want ...

3

Short Answer: NO, it is not safe, do NOT do this. Longer Answer: You are true that you can use your RSA keypair for both operations. This approach is used in many applications and scenarios. There are Web Services or Single Sign-On implementations, which enforce you to use the same key pair for both operations. X.509 certificates do not allow you (by ...

3

Are you asking "given $e$ and $\phi(n)$, how do we find $d$ such that $de \equiv 1 \bmod \phi(n)$"? (which can also be written as $d = e^{-1} \bmod \phi(n)$ The standard way of find such a value is the Extended Euclidean Method; this is a relatively efficient method that results in $d$ given $e$ and $\phi(n)$ as inputs (assuming, of course, that $e$ and ...

3

The main misconception here is, what part of the RSA problem is actually hard to compute. Your statement is like this: We have $e$ and $n$. We know $ed=1$ mod $\phi(n)$. So we should be able to calculate $d$. Your reasoning is exactly what is happening in the key generation algorithm. Division in modular arithmetic behaves just the same as with ...

2

I just want to add some additional information to the answer of Ilmari. As Ilmari has already described in his answer, when using RSA you work in the ring of integers ${\mathbb Z}/{\mathbb Z}_n$, which is also called a residue class ring. This means that it consists of the set of residue classes $[i]$, where the $i$'th class is defined as the set $\{a ... 2 We don't say this can't happen, we just say it won't happen. The only value that will decrypt to$p_2$under$(e_2,n_2)$is$p_2^{d_2}$, which we can call$s_2$. So, your problem comes down to asking what is the probability that$s_1=s_2$? If we assume that they're random, and that the moduli are similar enough sizes that this is even a realistic ... 1 Many of the beginner explanations use very simple examples: like this It is still hard to factorize a small number by hand, compared to other operations. There is definitely a size of prime numbers where hand computation is still feasible, but hand factorizing isn't. Would you, for instance, even armed with a list of primes, be able to quickly tell me what ... 1 The private key$d$of RSA algorithm with public parameters$(N,e)$is such that:$ed \equiv 1\mod{\phi(N)}$. Since by definition$e$and$\phi(N)$are coprime then with extended euclidean algorithm you can find such$d$:$ed +k\phi(N)=1$Consider that to compute$\phi(N)$you should know how to factor$N$since$\phi(N)=\phi(p)\phi(q)=(p-1)(q-1)$To see ... 1 If you use the raw RSA operation ($M^d \bmod n$or$M^e \bmod n$), then no, it is unsafe to use the same key, because an attacker could trick the private key holder into signing a message$M$(i.e. generating$M^d$) which is actually an encrypted message ($M = P^e$), thus allowing the attacker to recover the original plaintext ($(P^e)^d = P\$). (The dual ...

Only top voted, non community-wiki answers of a minimum length are eligible