-1
$\begingroup$

Okay so I wanted to know if my logic is correct for the approach of this practice problem that I'm doing in preparation for my final and see if I truly understand how the 3 pass protocol works so:

Alice wants to send a message to Bob using the 3-pass protocol. She decides to use the
prime p = 17, and picks her key, a = 11. Bob picks his key, b = 13.
(a) What are Alice and Bob’s decryption keys?

So the decryption function for Alice is $D_A \equiv C^{a^-1}(\mod p)$ and for Bob $D_B \equiv C^{b^-1}(\mod p)$ which I assume we use these functions to generate the keys correct? If we do how do we find C?

$\endgroup$
1
$\begingroup$

If $x \equiv y \space(mod \space\phi(p))$ then $n^x \equiv n^y \space(mod\space p)$ (1)

With encryption key $e$, decryption $d$, and message $m$, you have $E(m) = m^e \space(mod \space p)$.

For decryption you do $D(E(m)) \equiv E(m)^d \equiv (m^e)^d \equiv m^{ed} \space (mod \space p)$.

You want $m^{ed} \equiv m^1 \space (mod \space p)$ so from (1) you can determine you want to choose $d$ such that $de \equiv 1 \space (mod \space p-1)$.

(Note: $p$ is prime so $\phi(p) = p - 1$.)

Since $ed \equiv 1 \space (mod \space p-1)$, $e$ and $d$ are multiplicative inverses of each other mod $p - 1$. So if you can calculate the inverse, you can calculate one of the keys from the other.

I got 3 for Alice's decryption key and 5 for Bob's.

$11 * 3 \equiv 33 \equiv 1 \space(mod \space 17 - 1)$

$13 * 5 \equiv 65 \equiv 1 \space(mod \space 17 - 1)$

$\endgroup$
  • $\begingroup$ Thank you that makes complete sense! so you find the inverse of 11 and 13 which finds the numbers that make the condition true? $\endgroup$ – AceNinja1101 May 19 '18 at 21:18

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.