# Tag Info

## Hot answers tagged rsa

8

It doesn't become vulnerable; instead, it becomes impossible to decrypt uniquely. Let us take the example you give: $N=65$ and $e=3$. Then, if we encrypt the plaintext $2$, we get $2^3 \bmod 65 = 8$. However, if we encrypt the plaintext $57$, we get $57^3 \bmod 65 = 8$ Hence, if we get the ciphertext $8$, we have no way of determining whether that ...

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

No, it not possible to attack RSA (and practical modulus size) with a WalkSat derivative, as far as we know, or using the algorithm in the question. Problem with that algorithm is: in order to have a sizable/constant rate of success as $n$ increases, we have to repeat steps 2 and 3 not the stated $t\cdot m^2$ times, but rather $t\cdot 2^m$ times. That's ...

5

Yes, RSA is secure as we know it — although recommended key sizes are ever-increasing, as expected. Any seemingly-simple result that suggests a long-studied, well battle-hardened cryptosystem is insecure should throw up red flags. As an exercise, I wrote up your algorithm in simple C code: #include <stdio.h> #include <stdlib.h> int ...

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

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 ... 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 ... 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 The issue is that we use modular arithmetic. In modular arithmetic, you may view$m \bmod n$as the remainder of$m$when divided by$n$. So, for example,$7 \bmod 2 = 1$, also written as$7 \equiv 1 \pmod 2$, because$2(3) + 1 = 7$. Now consider what you're guaranteed by$m \equiv c^d \pmod n$, the decryption formula for plain RSA. You're guaranteed that ... 2 The current best way of decryption an RSA ciphertext (assuming good padding was used) is to factor$N$into its prime factors$p$and$q$, and from that, reconstruct the decryption exponent$d = e^{-1} \bmod lcm( p-1, q-1 )$The current record for factoring an RSA-type modulus (with large prime factors, and not of a special form) is 768 bits. It is likely ... 2 As long as you ensure that$n_1\leq n_2$is guaranteed, the value$r^em\pmod {n_1}$can be treated as an element in$Z_{n_2}$and the "outer blinding" and "outer unlinding" in$Z_{n_2}$does not change this value. Consequently, if you compute the "inner unblinding" in$Z_{n_1}$after the "outer unblinding" your proposal works. Remarks from the previous ... 2 The first byte is 0x00, because some standards allow RSA key sizes$8b+1, b \in \Bbb Z_+$. Such key would have 0x01 at the first bit, but it is possible for almost all other bits to be zero. Thus, 0x00 as the first byte allows interoperability with all possible RSA key sizes. NIST's recommendations and few other standards actually recommend only few ... 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 ...

1

No, exposing such a hash does not compromise the RSA private key, unless the hash function is sufficiently and severely broken. Of course, you don't need to hash the private exponent to identify the key. You can simply use the modulus or a hash over the (public) modulus to identify the key. This has the additional advantage that that ID will also match the ...

1

Yes, it does make sense to block them. Seeing you've asked this question in July, it's funny to think you might have had some kind of unintentional foresight of what meanwhile has become reality. Some hard facts: As raw computing power increases over time it becomes possible to factor or crack smaller sized RSA keys. Key sizes smaller than 1024 bits were ...

1

A signature scheme with message recovery is standardized as ISO/IEC 9796-2 (link to preview). Scheme 1 in this standard is commonly used in the Smart Card industry, despite its known weaknesses in a chosen-message setup. Example real-life uses include the EMV banking application (the free documents linked there include a description of an industry-standard ...

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