2
$\begingroup$

I'm a first year Maths undergraduate and we have recently gone onto RSA. I understand the majority of the algorithm using Fermat's Theorem etc.

From the algorithm stated on Wikipedia:

4) Choose an integer $d$ such that $1 \lt d \lt φ(n)$ and $\gcd(d, φ(n)) = 1$; i.e., $d$ and $φ(n)$ are coprime.

5) Determine $e$ as $e ≡ d^{−1} \mod {φ(n)}$; i.e., $e$ is the modular multiplicative inverse of $d \mod {φ(n)}$.

I don't understand the importance of $1 < d < φ(n)$.

Also why must the message $M$ to be encrypted be an integer $m$ such that $0 ≤ m < n$ (here $n$ is the product of two distinct primes $p$ and $q$)?

$\endgroup$
  • $\begingroup$ Hi Alexander and welcome! I've changed the title to be more specific. You can use TeX formatting here to format the formulas. Note that you can configure Wikipedia to do the same (in the preferences -> appearance, after logging in). $\endgroup$ – Maarten Bodewes Mar 5 '16 at 14:33
2
$\begingroup$

From the algorithm stated on Wikipedia:

"4) Choose an integer d such that 1 < d < φ(n) and gcd(d, φ(n)) = 1; i.e., d and φ(n) are coprime. 5) Determine e as e ≡ d−1 (mod φ(n)); i.e., e is the modular multiplicative inverse of d (modulo φ(n))"

I don't understand the importance of 1 < d < φ(n).

You can use a d greater than φ(n), but it needs more computation time than a d less than φ(n).

Also, d and e in 4) and 5) should be swapped. You may see 8.2.1 Handbook of Applied Cryptography

Also why must the message M to be encrypted be an integer m such that 0 ≤ m < n

(Here n is the product of two distinct primes p and q)

If m is less than 0 or not less than n, you can not recover m; since decryption gives you a number(m') 0 ≤ m' < n.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I've also noticed that the distinct primes p and q must be approximately equal size, why is this? $\endgroup$ – Alexander Mar 6 '16 at 9:20
  • $\begingroup$ @Alexander That's because the limiting factor for security is the size of the smallest prime, while performance is based on the largest prime. Thus taking same-size primes gives you the best security/performance ratio. Making one prime bigger makes the computation slower without improving security. $\endgroup$ – Gilles 'SO- stop being evil' Jan 4 '18 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.