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.

Pick your own numbers to increase your learning!

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
    print(answer)
    ">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
    print(answer)
    ">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")
    answer = (hash_value**103)%143
    print(answer)
    ">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")
    answer = (hash_value**7)%143
    print(answer)
    ">55"

A clever math trick underpins public-key cryptography and allows many parts of our economy to function safely. Again, public-key algorithms use much more complexity, such as large prime numbers and padding, to ensure that attackers can not break the code and find the private key.