- Any computer with Python 3.

`python3 -m pip install pycryptodome`

How large are p and q? Well, they can't both be larger than the square root of n, or they'd be larger than n when multiplied together.

Start Python 3 in interactive mode with this command:

Execute these commands:`python3`

The square root prints out, as shown below.

import math n = 10142789312725007 print(math.sqrt(n))

A good way to do this is to calculate n mod c, where c is a candidate. If c is a factor of n, the result will be zero.

We can test the first 20 candidates with a for loop.

Execute these commands:

Press Enter twice after the last command to terminate the loop.

c = 100711413 for i in range(c, c-40, -2): print(i, n%i)

The third candidate is the winner, with a remainder of zero, as shown below.

Execute these commands:

The calculation worked, so the last value is zero, as shown below.

p = 100711409 q = int(n / p) print(p, q, n, p*q, n - p*q)

The parameters print out, as shown below.

phin = (p-1) * (q-1) print(p, q, n, phin)

d is the "multiplicative inverse" of e.(d * e) mod phin = 1

We know that e = 5 from the Problem Statement.

It's not obvious how to find d, but there's a simple way to do it in Python, using the "pycryptodome" library.

In the Terminal window running python, execute these commands.

We get the value of d, and, to verify it, we see that d*e %phin is indeed 1, as shown below.

e = 5 from Crypto.Util.number import inverse d = inverse(e, phin) print(d, e, d*e %phin)

We can only send numbers. Let's convert that message to three bytes of ASCII and then interpret it as a 24-bit binary value.

Hi!

In the Terminal window running python, execute these commands.

We get the value of x, as shown below.

x1 = ord('H') x2 = ord('i') x3 = ord('!') x = x1*256*256 + x2*256 + x3 print(x)

Execute these commands:

The encrypted message appears, as shown below.

y = x ** e % n print(y)

Python freezes. It's going to take forever to calculate a number that large.

xx = y ** d % n

Press **Ctrl+C** to stop the computation.

To compute such a number, we must use the pow() function. Execute this command:

It works, showing our original message in numerical form.

xx = pow(y, d, n) print(xx)

Now it works, showing the original message in readable form, as shown below.

x1 = int(xx / (256*256)) x2 = int((xx - 256*256*x1) / 256) x3 = int(xx - 256*256*x1 - 256*x2) msg = chr(x1) + chr(x2) + chr(x3) print(x1, x2, x3, msg)

## C 402.1: Encrypt "WOW" (10 pts)

Execute these commands to load the same keys used above:Using those keys, encrypt this message:n = 10142789312725007 p = 100711409 q = int(n / p) phin = (p-1) * (q-1) e = 5 from Crypto.Util.number import inverse d = inverse(e, phin)WOWHint 1: The message, converted to a decimal number, is 7 digits long and ends in 43.

Hint 2: The encrypted message is 16 digits long and ends in 66.The flag is the encrypted message.

## C 402.2: Encrypt "OBEY!" (10 pts)

Using the same keys, encrypt this message:OBEY!Hint 1: The message, converted to a decimal number, is 12 digits long and ends in 41.

Hint 2: The encrypted message is 16 digits long and ends in 81.The flag is the encrypted message.

## C 402.3: Message to Cueball (15 pts)

Cueball's public key is:Meghan sends this message to Cueball. Decrypt it.(111036975342601848755221, 13)The flag is the decrypted message.80564890594461648564443

## C 402.4: Message to Rob (15 pts)

Rob public key is:Meghan sends this message to Rob. Decrypt it.(1234592592962967901296297037045679133590224789902207663928489902170626521926687, 5557)272495530567010327943798078794037733865151017104532777645776936985235709526002Hint: Make square root calculations more precise.The flag is the decrypted message.

Prime Numbers Generator and Checker

Arbitrary precision of square roots

Upgraded to Python 3 7-8-2020

Extra credit points specified 9-10-20

Converted to use pycryptodome instead of sympy 3-16-21