# Tag Info

8

I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"? No way to say, it might be microseconds, and it might be large multiplies of the age of the universe. When we say that an algorithm runs in polynomial time, we're not saying anything about how fast the algorithm runs given ...

2

The rationale behind polynomial vs. exponential is in tweaking the size of the keys. We need to achieve mainly two goals: Encryption and decryption by legitimate users is reasonable fast. Decryption by adversary without private key knowledge is prohibitively slow. (One way for decrypting by adversary might be computing private key from public key and ...

1

The term you are looking for is Modular Arithmetic. In the case of 1535, if it is indeed a combination of 3 values ranging 0 to 25, you do the following: 1535 mod 26 = 1 (1535 - 1) / 26 = 59 59 mod 26 = 7 (59 - 7) / 26 = 2 The set of values that generated 1535 is 2,7,1 (c,h,b?), which can easily be verified.

1

I think the confusion lies in mixing two distinct hard problems. RSA is related to the difficulty of factoring large numbers. The scheme you link to in the paper is based on the difficulty of solving discrete logarithms. Since they are very different hard problems, you can't really compare the two in terms of what must be kept secret. For RSA, ...

1

To solve this equation you must know: the factorisation of the public modulus $n=p \times q$, either: the value of the Euler totient $\phi(n)=(p-1)\times (q-1)=n-(p+q)+1$ There are no other alternatives to solve this equation. This is linked by the structure of the ring $\mathbb{Z}_n \equiv \mathbb{F}_p \times \mathbb{F}_q$, which represents the ...

1

It isn't impossible. Otherwise, we wouldn't have to keep increasing key sizes of our RSA keys, see this for the history. As stated in a comment, it is believed to be computationally hard. Though, even that has never been proven.

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