Select two distinct primes each with 6 binary digits and use them to design an RSA cryptosystem.

Question

Describe how to design an RSA cryptosystem based on primes p = 13 and q = 7. That is, propose the public key and the private key. Encode the message 100101 and then decode it.

I'm mimicking my professor's work but I'm getting stuck on a few parts. Was wondering if someone could help me and let me know what exactly I'm missing here.

So here is what I have:

$p = 13$ , $q = 7$

$N = p*q \implies N=(7)(13) = 91$

$(N,e) = (p-1)(q-1) = (12)(6) = 72$

I picked $e$ so that $GCD(e, (N,e)) = 1$

So I let $e = 5 \therefore GCD(5,72) = 1$

Now I use the Extended Euclid Algorithm:

I end up with:

a | q | y

72| . | 29

5 | 14| 2

2 | 2 | 1

1 | 2 | 0

0 |

I end up with: $(2*1) + 0 = 2$

$(14*2) + 1 = 29$

but then I get $(5)(29) - (2)(72) = 1$ but for some reason my teacher gets $145 = 1( \mod 72)$ I don't understand where he gets the $145$ from ? Did he just say oh ok $145 - 72 = 73$ which is $73 \equiv 1 \mod 72$? Also did he mean to put $145 \equiv 1 (\mod 72)$ instead of $145 = 1 \mod 72$? I know that $5(29) = 145$ if that means anything.. I could very well be missing something very trivial here but I'm not sure.

Answer 1

$145 \equiv 1 \pmod{72}$ is equivalent by definition to $\exists k \in \mathbb{Z}\ ( 145 = 1 + 72k )$, which you have proven by finding $5 \times 29 - 2 \times 72 = 1$.