3
$\begingroup$

The RSA cryptosystem only works if certain constraints are applied to its input parameters. Some of those constraints are made to make it "hard" to determine the private key whereas other constraints are there to make the mathematics work. I want to understand the latter category of constraints and why they exist.

Here is what I have so far....

  • The public exponent $e$ and the modulus $n$ should be $e<\phi(n)$. It can be larger but there is no benefit because $e$ is congruent $\mod\phi(n)$.
  • There are no other restrictions on $n$ (the use of $n$ with prime factors $p$ and $q$ is just to make the problem "hard").
  • The public exponent $e$ must be $0<e<n$.
  • In practice and because of the above, $n>1$.
  • $e$ does not need to be prime but it should be coprime with $\phi(n)$ (see next point). It does not need to be coprime with $n$ but it doesn't matter if it is. It is usual for $e$ to be chosen from the Fermat Primes, usually $65537$ in real applications.
  • $e$ and $\phi(n)$ must be coprime to satisfy, for the private key $d$, that $ed\equiv 1\pmod{\phi(n)}$ if, by Euler's Totient Theorem and Bezout's Identity, $ed+k\phi(n)=1$ (where $k$ is a quotient of no relevance and can be any integer; $k$ and $d$ are computed from $e$ and $\phi(n)$ by the Extended Euclidean Algorithm).
  • The message $m$ (both the plaintext and the ciphertext) must be coprime with $n$ so that, by Euler's Totient Theorem, $m^{\phi(n)}\equiv 1\pmod n$. However, $m$ does not need to be coprime with $\phi(n)$ but it doesn't matter if it is.

I have read elsewhere that any $m$ should work, like this question explains, but that contradicts the last constraint and I've experienced that the algorithm somtimes fails without this.

I have a little program that evaluates the algorithm with some small numbers ($n$ < 20 bits). I find it breaks occasionally and, when it does, I find that $m$ and $n$ are not coprime.

I believe the minimum constraints are those that I've listed above. I'd like to understand whether I have it right or if I'm missing anything. If it should work for all $m$ there must be a reason why I find to the contrary.

Update

$m$ does not need to be coprime with $n$ but $gcd(m,n)$ must be coprime with $n/(gcd(m,n)$ but I don't understand why this is the case.

Optimisations can be performed if the factors, $p$ and $q$, of $n$ are known. They aren't necessary but can help improve decryption performance where $d$ is large. They are:

  • The reduced totient $\lambda(n)$, or Carmichael Function, can be used instead of Euler's Totient so, in the above, $\phi(n)$ can be replaced with $\lambda(p,q)$. This gives a smaller value for $d$ (and demonstrates that there are multiple $d$ values for a given $e$).

  • It's possible to use the Chinese Remainder Theorem (CRT) to break the ciphertext into two smaller parts so that two smaller exponents can be computed instead of one based on a large $d$. A good explanation of this technique is here.

When generating the private key, the CRT coefficients $dp$, $dq$ and $qinv$ (the inverse of $q\mod p$) can be precomputed and would form part of the private key. They are then used in decryption instead of $d$.

I don't understand why $\lambda(p,q)$ works and I've found that CRT only works when $p>2$ and $q>2$. The reason for this isn't clear but I think it is because a CRT coefficients when $p$ or $q$ is 2 will be taken modulo 1 which is always zero.

$\endgroup$

1 Answer 1

4
$\begingroup$

One does not need ​ e < n .
One does not need $\;\; e\hspace{-0.03 in}\cdot \hspace{-0.03 in}d \: \equiv \: 1 \;\; \pmod{\phi(n)} \;\;\;\;\;$;
one just needs that congruence modulo λ(n).
(Being coprime with $\phi$(n) is equivalent to being coprime with λ(n).)
Neither the plaintext nor the ciphertext need to be coprime with n.
gcd(m,n) must be coprime with n/(gcd(m,n)).



That last condition will be automatic when n is square-free, since it's equivalent to
"If m≠0 then for every prime factor p of n, p's multiplicity as a
factor of m is either 0 or equal to p's multiplicity as a factor n.".
When the quote holds, for each maximal-prime-power factor q of n,
m's remainder mod q will be either 0 or a coprime to q.
When the former case applies, it will continue applying to all positive powers of m.
When the latter case applies:

By Fermat's Little Theorem, $\;\;\; m^{\hspace{.02 in}\phi(q)} \equiv 1 \: \pmod{q} \:\:\:\:$.
For all non-negative integers k,
$m^{(k\cdot \phi(q))\hspace{.02 in}+1} \: \equiv \: m^{\hspace{.02 in}k\cdot \phi(q)} \cdot m^1 \: = \: m^{\hspace{.02 in}\phi(q) \cdot k} \cdot m \: =$
$\left(\hspace{-0.03 in}m^{\hspace{.02 in}\phi(q)}\hspace{-0.06 in}\right)^k \cdot m \: \equiv \: 1^k \cdot m \: = \: 1\cdot m \: = \: m \;\;\; \pmod{q} \;\;\;\;\;\;\;\;$.
λ(n) is a positive integers multiple of $\phi$(q), so for all
non-negative integers $k$, $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{q} \:\:\:\:$.


Thus, when the quote holds, one will have $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{q}$
for each maximal-prime-power factor q of n and each non-negative integer k.
Therefore, by the Chinese Remainder Theorem, when the quote holds one
will have $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{n} \;\;\;$ for all non-negative integers k.

$\endgroup$
5
  • $\begingroup$ Thanks for the answer. About $e<n$, I should have said $\phi(n)$ and, yes, $e>\phi(n)$ is fine but, if I understand it right, $e$ is congruent $\mod\phi(n)$ so there's little point in $e>\phi(n)$. Also, $e\equiv 0\pmod{\phi(n)}$ won't work because $e$ and$\phi(n)$ wouldn't be coprime in that case. I know this isn't a real world scenario anyway! $\endgroup$
    – starfry
    Mar 19, 2016 at 20:25
  • $\begingroup$ Your point about $\lambda(n)$ is true indeed and I just tested to make sure that holds. I am not sure whether you'd ever have $ed\equiv 1\pmod{\lambda(n)}$ without also having $ed\equiv 1\pmod{\phi(n)}$ ? Is this just something to facilitate the implementation or is there more to it? $\endgroup$
    – starfry
    Mar 19, 2016 at 20:28
  • $\begingroup$ Regarding your point about $m$ and $n$ not needing to be coprime, yes this is true and the gcd coprime holds also. I've never seen that relationship before - do you know of anywhere there's a further explanation of this property? $\endgroup$
    – starfry
    Mar 19, 2016 at 20:34
  • $\begingroup$ $\langle n,\hspace{-0.02 in}e,\hspace{-0.02 in}d\rangle \: = \: \langle 391,\hspace{-0.02 in}3,59\rangle \;\;\;$ is an example in which $e\hspace{-0.04 in}\cdot \hspace{-0.04 in}d$ isn't congruent to $1$ mod $\phi(n)$. $\;\;\;\;\;\;\;\;$ This allows smaller $d$. $\;\;\;\;\;\;\;\;$ Wikipedia explains the relevant property, although I find the reason for that easier to grasp when considering the decomposition into prime powers rather than gcd(m,n) and n/(gcd(m,n)). $\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    Mar 19, 2016 at 22:57
  • $\begingroup$ Following your pointer to the CRT on Wikipedia, I've read that before but I couldn't understand it until I found this explanation and this video. I now get that and I've added some detail to my original question. But I still don't understand why $gcd(m,n)$ must be coprime with $n/(gcd(m,n)$. I am probably missing something obvious but I don't know what it is. Would you be able to add some detail to your answer about that? $\endgroup$
    – starfry
    Mar 23, 2016 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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