# Tag Info

## Hot answers tagged rsa

10

Ricky's link answers your main question in the comments (that knowing the private key is equivalent to knowing the factorization of $N$). But your "attack" is unfortunately part of a class of properties which might appear insightful at first, but which eventually boil down to something like this: "find integers $(m,k)$ such that $m+kn$ is a perfect square" ...

7

I don't think idea 1 can be made to work at all. The main point is that in order to generate a correct secret decryption key, the key generator must know the order of $\mathbb Z^*_n$, i.e., the totient of the modulus $n$. The generator knows that $n=p \cdot q$, where it believes that $p$ and $q$ are primes, and so it believes that the totient is ...

5

This expands CodesInChaos's comment into an answer. Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and ...

4

You seem to have some misconception here. Obviously, you are investigating chosen ciphertext attacks (CCAs) on textbook RSA instead of chosen plaintext attacks (CPAs). To help you with your understanding I am discussing CPA on textbook RSA first. To analyse all these kinds of attacks we formally model the attack as a game between an adversary (trying to ...

3

The most effective trapdoor I could imagine an adversary building into an RSA key generation algorithm would be the following: Preparation The adversary generates a set of RSA keys of varying sizes. The public keys will be built into the malicious key generation code, the secret keys are kept by the adversary. Key generation algorithm The algorithm is ...

3

Feasible? Sure, there are lattice algorithms that are competitive in performance with RSA. However, there are drawbacks, like: They've been studied less than RSA or ECC, especially the individual algorithms. The most well studied system, NTRU, is patented. No generic proof that I know of that there isn't a quantum algorithm to solve them. The first one ...

3

If RSA keys in PGP format are fine, you can download them from any keyserver. Many keyservers, at least MIT, have a robots.txt that disallows automated downloads, so be sure to check that before attempting to bulk download anything. If you need a large collection, you could download a keyserver dump and filter out what you need.

3

Chris's answer is great. As it does not address how one would detect #2, I'll take a stab at it. Assume there is some watchdog looking at public keys in your system, trying to detect a problem. They can easily tell if two public keys share a prime by computing gcd. A gcd of anything other than 1 would identify bad keys. So, let's assume that once two ...

2

In both cases (the company name and the algorithm name), the letters “RSA” stand for the initials of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman… $R$ivest, $S$hamir, and $A$dleman. Wrapping it up in short: In 1977, they (Ron Rivest, Adi Shamir, and Leonard Adleman) first publicly described an algorithm which was named after them and is ...

2

You are correct; whoever put together the above proof typo'ed that point; we have $c \times d \equiv 1 \pmod {\phi(n)}$, or more accurately, $c \times d \equiv 1 \pmod {lcm(p-1, q-1)}$. On the other hand, the attacker isn't expected to be able to compute step 2 (he can't, he doesn't know the value of $lcm(p-1,q-1)$, and hence cannot compute $d$). Instead, ...

2

You will always need to have some way of identifying the other party, be it a pre-distributed key or out-of-band procedures as you are describing. There is no purely digital method that can do this without some kind of shared knowledge.

1

Simple, $r$ just needs to be co-prime to $n$. To test this check that $gcd(r,n)==1$. This is required since you need to "divide" by $r$, i.e., multiply by $r^{-1}$. $r$ is invertible iff $gcd(n,r)==1$.

1

The other answers tackle 2. very well, so I'll only look at 1. I think it can be made to work in some specific instances, namely if the key generator was part of a closed product with its own key storage or the private key used a format where only the modulus and exponents were stored. (Note that 2. is not common, because knowing the primes can be used ...

1

I don't think you will be able to "brute force" decrypt your data. The AES key and IV a probably chosen randomly to encrypt the actual data using some encryption mode. As there is an IV, as you state, it will not be ECB but probably CBC. To get the AES key and IV you need to know the RSA private key D. If the the RSA key pair is chosen carefully, you are ...

1

You're missing that key generation would occur inside the box (if there was one for RSA key agreement), like for $k_{pr,A}$ and $k_{pub,A}$ on page 343, rather than outside the box, as happened for $k_{pub,CA}$ on page 347.

1

I have figured out a way to use TLS with only a EC key by using DSA instead of RSA. I had not realized you could do DSA with a EC key. My mistake was trying to use RSA to sign the certificate. Now I can generate my certificate and self-sign it only with the EC key. The peer will simply check to make sure the certificate was signed by the appropriate node ID ...

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