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.
Public-Key Cryptography Math and Code Tutorial
2021 June 15 Twitter Substack See all postsCreating 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".
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:
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.
The final number, "d", is computed from "e" and φ(n). "d" is known as the modular multiplicative inverse of "e".
The equation simplifies to:
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:
Python:
These numbers and their relationships allow the creation of our public and private keys.
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.
Python Code:
Now we decode our friend's message:
Python Code:
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:
Python Code:
Let us verify the signature:
Python Code:
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.