- Any computer with Python 2.7. If you are using a Mac or Linux machine, Python is already installed. If you are using Windows, follow these instructions to install Python 2.7.

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 in interactive mode. On a Mac or Linux box, you can do that by typing this command into a Terminal window:

Execute these commands:`python`

The square root prints out, as shown below.

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

Execute this command:

Now more decimal places appear, as shown below.

print repr(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 = 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

Open a **new Terminal window**, not the one
running Python, and execute this command to
download and install a few dependencies and gmpy:

One student said "pip" did not work. so he did this:

brew install gmp mpfr mpc pip install gmpy

And thereafter used "python2.7" in place of "python".

brew install python

apt install python-gmpy

In a Web browser, go to:

**
https://code.google.com/archive/p/gmpy/downloads?page=8**

Download **gmpy-1.12.win32-py2.7.exe**,
as shown below. Double-click this file and install
it with the default options.

If you are using a later version of Windows, you might need a more recent version of gmpy from this page . These downloads are "wheel" files, and must be installed from a command prompt with the "pip install" command.

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 "gmpy" 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 import gmpy d = gmpy.invert(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 crashes, as shown below. It cannot handle such large numbers. (On Windows, you see a different error message saying "outrageous exponent". Execute the

xx = y ** d % n

Execute these commands to restart python and restore all the values we calculated previously:

Your screen should look like the image below. Let's try that decryption again with the pow() function. Execute these commands:

python n = 10142789312725007 p = 100711409 q = 100711423 phin = (p-1) * (q-1) e = 5 import gmpy d = gmpy.invert(e, phin) x1 = ord('H') x2 = ord('i') x3 = ord('!') x = x1*256*256 + x2*256 + x3 y = x ** e % n

Now 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.

xx1 = xx / (256*256) xx2 = (xx - 256*256*xx1) / 256 xx3 = xx - 256*256*xx1 - 256*xx2 msg = chr(xx1) + chr(xx2) + chr(xx3) print xx1, xx2, xx3, msg

WOW

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

Use the form
below to put your name on the
**WINNERS PAGE**.

OBEY!

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

Use the form
below to put your name on the
**WINNERS PAGE**.

Meghan sends this message to Cueball. Decrypt it.(111036975342601848755221, 13)

Use the form below to put your name on the80564890594461648564443

Meghan sends this message to Rob. Decrypt it.(1234592592962967901296297037045679133590224789902207663928489902170626521926687, 5557)

272495530567010327943798078794037733865151017104532777645776936985235709526002

Use the form
below to put your name on the
**WINNERS PAGE**.

Prime Numbers Generator and Checker

Arbitrary precision of square roots

Posted 3-31-16 by Sam Bowne

Winners pages added 8-6-16

Attack server name updated 4-4-17

Added challenge and all renumbered 6-11-17

Added email and screen cap instructions 9-9-17

Added brew install 9-25-17

Pts fixed 10-3-17

Mac tip added 10-6-17

Added to Crypto Hero 4-15-18 9:27 pm