2
$\begingroup$

In Khan Academy's RSA Encryption 2 video, I can't understand how they have got from

$$m^e\bmod N\equiv c$$ to $$c^d\bmod N\equiv m\,.$$

The transcript says,

01:39 some piece of information that makes it
01:41 easy to reverse the encryption
01:44 we need to raise $c$ to some other exponent, say $d$,
01:48 which will undo the original operation applied to $m$
01:51 and return the original message $m$.
01:54 So both operations together, is the same as
01:57 $m^e$ all raised to the power of $d$,
02:01 which is the same as $m^{e\times d}$.

The person says if we want to reverse the function to give us $m$ (the encrypted message), we simply have to raise $d$ to another exponent, $d$, and this reverses it.

Although I know this video isn't supposed to fully explain everything I don't understand how this is done. How can you just raise $c$ to some power and get the original message $m$. Is there some sort of proof or can someone explain it in more detail perhaps? By the way, I pretty much know nothing about encryption/ cryptography. I study CS at college (UK) AND was just watching due to curiousity.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! We prefer that you not use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe the relevant text and mathematics. Note that you can use LaTeX. $\endgroup$ – D.W. Feb 3 '17 at 4:46
  • $\begingroup$ I've not seen the video but it appears that it's saying, "We encrypted the message by raising it to some power. Hey, wouldn't it be nice if we could decrypt it by raising the cyphertext to some power. Let's pretend for a moment that we can do that, and spend a few moments exploring the consequences. [consequences] OK, now that we've done that, we'd better check that we really can decrypt in that way." My guess is that the answer to your question is a few more minutes into the video. $\endgroup$ – David Richerby Feb 3 '17 at 9:06
1
$\begingroup$

What you have (after generating the keys):

$$ \gcd(p, q) = 1 $$ $$ N = pq $$ and a number $e$ and it's inverse $d$, modulo $\phi(N)$. That is: $$ ed \equiv 1 \pmod{\phi(N)}$$


Encryption: $$ c \equiv m^e \pmod{N}$$ Decryption: $$ m^\prime \equiv c^d \pmod{N} $$ $$ m^\prime \equiv (m^e)^d \equiv m^{ed} \pmod{N} $$

We don't yet if $m^\prime \equiv m$.

Well... you can use Euler's Theorem: $$ a^{\phi(N)} \equiv 1 \pmod{N}, \text{ if } \gcd(a,N) = 1. $$

Write $ed = 1 + k~\phi(N)$: $$ m^\prime \equiv m^{1+k\phi(N)} \pmod{N}$$ $$ m^\prime \equiv m\cdot m^{k\phi(N)} \pmod{N}$$ $$ m^\prime \equiv m\cdot \underbrace{m^{k\phi(N)}}_{1} \pmod{N}$$

So $m^\prime \equiv m \pmod{N}$.

$\endgroup$
  • $\begingroup$ I don't understand what you're saying in the first section of your answer. Sorry for sounding stupid but I can't follow. Of course the first bit makes sense but I don't get how you reach " ...and a number e and it's inverse d, modulo N. That is: ed≡1(modϕ(N)) $\endgroup$ – User22 Feb 3 '17 at 16:16
  • $\begingroup$ There was a typo on this line. Also, as David pointed out in the comments, it seems the answer is given later in the video. $\endgroup$ – Aristu Feb 3 '17 at 17:11
  • $\begingroup$ Also, there are some more complete lectures on youtube. $\endgroup$ – Aristu Feb 4 '17 at 14:27

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.