# Public-Key Cryptography Math and Code Tutorial

2021 June 15 Twitter See all posts

## Creating a Public Key/Private Key Pairing

Brett Slatkin's example of public-key cryptography is the basis for this tutorial.

My Public-Key Cryptography post is the counterpart to this tutorial.

This example is not secure for encrypting messages. Algorithms like RSA use large prime numbers that are not fit as an example.

Choose two prime numbers ("p" and "q") then multiply them together to find the product, "n".

``````    q = 11
p = 13
n = q * p
n = 143
``````

Calculate Euler's Totient (φ) for "n". Euler's Totient finds the number of relatively prime integers. Relatively prime numbers are also known as co-primes.

Co-primes are numbers that do not share a common divisor other than 1. For example, the Euler's Totient for six would be two because only the integers (1,5) do not share a divisor. 2 shares 2, 3 shares 3, and 4 shares 2.

Use this simplified equation to find φ for prime number products:

``````    φ(n) = (p - 1) * (q - 1)
φ(143) = (11 - 1) * (13 - 1) = 120
``````

We need a number known as "e". It must be a number such that 1 < number < φ(n). The number must also be a co-prime of φ(n). We will pick 7.

``````      e = 7
``````

The final number, "d", is computed from "e" and φ(n). "d" is known as the modular multiplicative inverse of "e".

``````    e ^ -1 = d (mod φ(n))
``````

The equation simplifies to:

``````    Modulo φ(n) of "e" * "d" - 1 = 0
``````

A value that works for our example is 103. Brute force iteration in a spreadsheet or the Python code listed below can solve for this number.

Brute force final result:

``````      7 * 103 - 1 = 720
Modulo 120 of 720 = 0
``````

Python:

``````    remainder = 1 #placeholder to start loop
d = 1
e = 7
while remainder > 0:
remainder = (e * d - 1) % 120
print(d, remainder)
d += 1
``````

These numbers and their relationships allow the creation of our public and private keys.

``````    public key = ("n", "e") = (143, 7)
private key = ("n", "d") = (143, 103)
``````

Let's put these keys to work.

## Encrypting and Decrypting a Message

Our friend is going to encrypt a secret number to send to us. The reason our example uses a number is that encryption algorithms like RSA only transport numbers and bytes. A plain text message requires conversion to a numerical format first.

The calculations may be challenging to do on a regular calculator or in a spreadsheet. I include the python code to calculate the answers.

Our friend will use our public key to encrypt the message.

``````    message = 33
c(message) = message ^ "e" modulo "n"
c(33) = 33^7 modulo 143
c = 110
``````

Python Code:

``````    answer = (33**7)%143
">110"
``````

Now we decode our friend's message:

``````    c = 110
message(c) = c ^ "d" modulo "n"
message(110) = 110^103 modulo 143
message = 33
``````

Python Code:

``````    answer = (110**103)%143
">33"
``````

Now you know how to encrypt and decrypt messages!

## Signing a Message and Verifying a Signature

Signing a message uses the hash of the message and our private key. Anyone receiving the message can use the associated public key to confirm the signature.

Note: This example uses Python's built-in hash function. By default, it adds a random number to prevent attackers from taking advantage of known collisions. Hashing the same phrase will not return the same value if you call the program at different times. When calling the python script in the command line, add PYTHONHASHSEED=0 before the command to disable this feature. Example: "PYTHONHASHSEED=0 python3 /users/austinvernon/desktop/scripts/python_hash_function.py"

The algorithm is:

``````    broadcast = "gingerale"
signature = hash(broadcast) ^ "d" modulo "n"
signature = 1513804153320053650 ^ 103 modulo 143
signature = 55
``````

Python Code:

``````    hash_value = hash("gingerale")
">55"
``````

Let us verify the signature:

``````    confirmation = hash(broadcast) ^ "e" modulo "n"
confirmation = 1513804153320053650 ^ 7 modulo 143
confirmation = 55
``````

Python Code:

``````    hash_value = hash("gingerale")