Skip to main content
Tweeted twitter.com/#!/StackCrypto/status/203126672852123650
formatting fixes
Source Link
Paŭlo Ebermann
  • 23k
  • 7
  • 83
  • 121

Just to establish notation with respect to the RSA protocol, let $n = pq$ be the product of two large primes and let $e$ and $d$ be the public and private exponents, respectively ($e$ is the inverse of $d$ mod $\varphi(n)$$d \bmod \varphi(n)$). Given a plaintext message $m$, we obtain the ciphertext $c = m^e$ (mod $n$)$c = m^e \bmod n$; we subsequently decrypt the ciphertext by calculating $c^d (mod $n$)$c^d \bmod n$.

Suppose I'm trying to implement RSA on a device with low computational power, and these exponentiations take too long. I decide to make my implementation run faster by choosing small values for $e$ and $d$ (e.g. in the tens or hundreds).

Are there efficient attacks against such an implementation?

Are there efficient attacks against such an implementation?

Just to establish notation with respect to the RSA protocol, let $n = pq$ be the product of two large primes and let $e$ and $d$ be the public and private exponents, respectively ($e$ is the inverse of $d$ mod $\varphi(n)$). Given a plaintext message $m$, we obtain the ciphertext $c = m^e$ (mod $n$); we subsequently decrypt the ciphertext by calculating $c^d (mod $n$).

Suppose I'm trying to implement RSA on a device with low computational power, and these exponentiations take too long. I decide to make my implementation run faster by choosing small values for $e$ and $d$ (e.g. in the tens or hundreds).

Are there efficient attacks against such an implementation?

Just to establish notation with respect to the RSA protocol, let $n = pq$ be the product of two large primes and let $e$ and $d$ be the public and private exponents, respectively ($e$ is the inverse of $d \bmod \varphi(n)$). Given a plaintext message $m$, we obtain the ciphertext $c = m^e \bmod n$; we subsequently decrypt the ciphertext by calculating $c^d \bmod n$.

Suppose I'm trying to implement RSA on a device with low computational power, and these exponentiations take too long. I decide to make my implementation run faster by choosing small values for $e$ and $d$ (e.g. in the tens or hundreds).

Are there efficient attacks against such an implementation?

edited tags
Link
ir01
  • 4.1k
  • 3
  • 23
  • 31
Source Link
Elliott
  • 1.7k
  • 3
  • 15
  • 9

RSA with small exponents?

Just to establish notation with respect to the RSA protocol, let $n = pq$ be the product of two large primes and let $e$ and $d$ be the public and private exponents, respectively ($e$ is the inverse of $d$ mod $\varphi(n)$). Given a plaintext message $m$, we obtain the ciphertext $c = m^e$ (mod $n$); we subsequently decrypt the ciphertext by calculating $c^d (mod $n$).

Suppose I'm trying to implement RSA on a device with low computational power, and these exponentiations take too long. I decide to make my implementation run faster by choosing small values for $e$ and $d$ (e.g. in the tens or hundreds).

Are there efficient attacks against such an implementation?