-2
$\begingroup$

Trapdoor functions are defined as that a secret key reverses the function. It seems to me more that it causes a cycle to repeat, similar to how $n^k \bmod k$, when $k$ is a prime number, equals $n$, and $n^k+1 \bmod k$ equals $n^2 \bmod k$, a cyclical pattern.

What is the reason $m^{ed}$ in RSA equals the original message? Is it in some way similar to $n^k \bmod k = n$ (when $k$ is a prime number)?

$\endgroup$
7
  • $\begingroup$ '$n^k+1 \bmod k$ equals $n^2$' - no, it doesn't. Perhaps you meant $n^{k+1} \bmod k$ maybe??? $\endgroup$
    – poncho
    Commented Apr 16, 2019 at 12:57
  • $\begingroup$ Fermat's little theorem $n^k \equiv n \pmod k$ holds when $k$ is prime. A more general statement is Euler's theorem: that $n^{\ell \cdot \phi(k) + 1} \equiv n \pmod k$ for any $k$ and $\ell$, where $\phi$ is Euler's totient function. As it happens, $e \cdot d = \ell \cdot \phi(k) + 1$ for some $\ell$, because by construction $e \cdot d \equiv 1 \pmod{\phi(k)}$. $\endgroup$ Commented Apr 16, 2019 at 14:53
  • $\begingroup$ Ok so Fermat's little theorem is just the observation that a^p mod p = a, the same observation I have made when trying to understand RSA. That explains a bit conceptually how it relates to the rest of what I have tried to learn. In what context did Fermat make the observation? $\endgroup$
    – grday
    Commented Apr 16, 2019 at 17:51
  • $\begingroup$ and is there also a mathematical pattern that a^n mod p = a^(p+n) mod p? $\endgroup$
    – grday
    Commented Apr 16, 2019 at 19:30
  • $\begingroup$ @grday No, but you're close: $a^{p + n} \equiv a^p a^n \equiv a a^n \equiv a^{1 + n} \pmod p$. You can think of exponents as integers mod $\phi(p) = p - 1$ in this case: if two exponents $n$ and $m$ have $n \equiv m \pmod{\phi(p)}$, then $a^n \equiv a^m \pmod p$. $\endgroup$ Commented Apr 17, 2019 at 17:29

1 Answer 1

1
$\begingroup$

Trapdoor functions are defined as that a secret key reverses the function. It seems to me more that it causes a cycle to repeat

I don't know if that's a useful way to think of trapdoor functions; one counterexample would be the trapdoors within multivariate public key cryptosystems; they certainly are trapdoor functions, however there isn't anything like a cycle going on. In fact, the only examples of trapdoor functions that act "in a cycle" would be RSA and related systems.

In any case, on to your real question:

What is the reason $m^{e^d}$ in RSA equals the original message? Is it in some way similar to $n^k \bmod k = n$ (when $k$ is a prime number)?

Actually, it's not only similar, it follows directly.

Modifying the variable names (to me, $p$ is a prime, $k$ is an arbitrary integer), we generalize $m^p \bmod p = m$ to more general statement $m^{1 + k(p-1)} \equiv m \pmod p$; this can be shown by the relations $m^1 \equiv m \pmod p$ (trivial) and $m^p \equiv m \pmod p$ (Fermat's Little Theorem) and induction.

In addition, we have $(m^e)^d$ is the same as $m^{e \cdot d}$.

And, we have selected $d, e$ so that $e \cdot d \equiv 1 \pmod{ p-1 }$ and $e \cdot d \equiv \pmod{q - 1}$ (where $p, q$ are the prime factors of $n$.

What $e \cdot d \equiv 1 \pmod{p-1}$ means is that there is an integer $k$ such that $e \cdot d = 1 + k(p-1)$. So, we have $m^{ed} = m^{1 + (p-1)}$, and so by the above logic, we know that is the same as $m$ modulo $p$

The same logic shows that $m^{ed} \equiv m \pmod q$.

Combining the above two with the Chinese Remainder Theorem (with $p, q$ being relatively prime), we get $m^{e \cdot d} \equiv m \pmod{n}$; if the original message is less than $n$ (the modulus size), we get $(m^e)^d \pmod n = m$, QED

$\endgroup$
4
  • $\begingroup$ Actually that may be my mistake (I edited the question) that it's written as ${m}^{{e}^{d}}$ instead of $m^{ed}$. $\endgroup$ Commented Apr 16, 2019 at 14:20
  • 1
    $\begingroup$ @AleksanderRas: actually, it's not (necessarily a mistake); encrypting a message $m$ is $m^e$ (modulo $n$), and so encrypting and then decrypting the message is $(m^e)^d$ (modulo $n$). Now, that's the same as $m^{e \cdot d}$, but writing the former is not a mistake $\endgroup$
    – poncho
    Commented Apr 16, 2019 at 15:05
  • $\begingroup$ Ah yes, of course, $e$ and $d$ are multiplied, not added. Forgot the basics of exponential math... $\endgroup$ Commented Apr 16, 2019 at 15:42
  • 1
    $\begingroup$ @AleksanderRas i had written m^e^d so not your mistake $\endgroup$
    – grday
    Commented Apr 16, 2019 at 22:09

Your Answer

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

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