-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$
  • $\begingroup$ '$n^k+1 \bmod k$ equals $n^2$' - no, it doesn't. Perhaps you meant $n^{k+1} \bmod k$ maybe??? $\endgroup$ – poncho Apr 16 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$ – Squeamish Ossifrage Apr 16 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 Apr 16 at 17:51
  • $\begingroup$ and is there also a mathematical pattern that a^n mod p = a^(p+n) mod p? $\endgroup$ – grday Apr 16 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$ – Squeamish Ossifrage Apr 17 at 17:29
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$
  • $\begingroup$ Actually that may be my mistake (I edited the question) that it's written as ${m}^{{e}^{d}}$ instead of $m^{ed}$. $\endgroup$ – AleksanderRas Apr 16 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 Apr 16 at 15:05
  • $\begingroup$ Ah yes, of course, $e$ and $d$ are multiplied, not added. Forgot the basics of exponential math... $\endgroup$ – AleksanderRas Apr 16 at 15:42
  • 1
    $\begingroup$ @AleksanderRas i had written m^e^d so not your mistake $\endgroup$ – grday Apr 16 at 22:09

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.