Python Implementation of RSA, Digital Signature and Certificates
Implementation of RSA, Digital Signature and Certificates without divining too deep into the Mathematics; then list out key math principles for further reference. In this way, one can understand *what* and *how* as a context before drilling into *why*.
- Introduction
- Rivest, Shamir and Adleman (RSA) Cryptosystem
- Digital Signature
- Certificate
- Reference
Introduction
Information is power. However, to transmit info is tricky. At least 2 issues need to be solved in information transmission: Security and Integrity.
- Security (RSA)
No one can see the naked message other than the one intended.
- Integrity (Digital Signature)
No one shall replace the message with another dummy one in the middle of transimission;
If it happened, however, intended message receiver shall be able to find out.
@MITimport random
import base64
from hashlib import sha256
def check_prime(num):
"""Check if num is prime
"""
# prime numbers are greater than 1
if num > 1:
# check for factors
# TODO: refactoring to parallel
for i in range(2, num):
if (num % i) == 0:
return False
else:
return True
# if input number is less than
# or equal to 1, it is not prime
else:
return False
# https://stackoverflow.com/a/9758173/3317548
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception("modular inverse does not exist")
else:
aa = x % m
bb = int((1 - a * aa) / m)
return aa, bb
# https://stackoverflow.com/q/2068372/3317548
def find_prime(n):
""" Returns a list of primes < n """
sieve = [True] * (n // 2)
for i in range(3, int(n ** 0.5) + 1, 2):
if sieve[i // 2]:
sieve[i * i // 2 :: i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
return [2] + [2 * i + 1 for i in range(1, n // 2) if sieve[i]]
Encryption & Decryption Process
- Receiver (Richael) generate a pair of keys: public & private
- She keeps private key to herself confidentially
- She sends multiple copies of public key to every of her friends who need to send her message
- Any one got Richael's public key can send her message now. For instance, Stephen:
- Stephen'd like to send the original message: "Hello Richael. Let's meet at 6:25 pm tomorrow at the airport Gate5, Terminal 2 :)", to Richael.
- Stephen'd encrypt the message with Richaels public key into something looks random, e.g. "MHgxNTMzCjB4MmFmNgoweGFiOA...YWE0CjB4MWZlMwoweDIzMGY="
- Stephen'd send that "random" stuff to Richael.
- After receiving the "random" stuff from Stephen, Richael uses her own private key to decrypt it into orignal message "Hello Richael. How are you?!"
- Only with Richael's private key, the "random" stuff, produced with Richael's public key, can be decrpted. Unless Richael shares her private key, which she shall never do, no one other than Richael herself can obtain the original message "Hello Richael. Let's meet at 6:25 pm tomorrow at the airport Gate5, Terminal 2 :)"
- If Richael'd like to answer to Stephen, she must obtain Stephen's public key.
Key Pair: Public & Private (Richael's Task)
- Randomly pick 2 prime numbers (larger the better): p & q
- Got their muliplication: n=pxq
- Got the Euler number: phi=(p-1)x(q-1)
- Randomly find a prime number in the range of 1 to phi (larger the better): e
- Find the Modular Multiplicative Inverse of e relative to phi: k
- public key is: (n, e)
- private key is: (n, k)
p = random.choice(list(find_prime(1024)))
q = random.choice(list(find_prime(1024)))
assert check_prime(p)
assert check_prime(q)
n = p * q
p, q, n, len(bin(n)), bin(n)
phi = (p - 1) * (q - 1)
phi
e = random.choice(find_prime(phi))
assert check_prime(e)
e
k = modinv(e, phi)[0]
k
public_key, private_key = (n, e), (n, k)
public_key, private_key
# unicode
msg = [ord(i) for i in "Hello Richael. Let's meet at 6:25 pm tomorrow at the airport Gate5, Terminal 2 --Stephen :)"]
msg
# encrption
[(val ** public_key[1]) % public_key[0] for val in msg]
encry_msg = '\n'.join([hex((val ** public_key[1]) % public_key[0]) for val in msg])
encry_msg
encry_msg = base64.b64encode(encry_msg.encode('utf8'))
encry_msg
# base64 decode and hex decode
[int(i, 16) for i in base64.b64decode(encry_msg).decode('utf8').split('\n')]
decry_msg = [
int(i, 16) ** private_key[1] % private_key[0]
for i in base64.b64decode(encry_msg).decode("utf8").split("\n")
]
print(decry_msg)
print("".join([chr(i) for i in decry_msg]))
Why is this secure?
@Euler
He changed the world and he is now everywhere; Remeber Euler and everything about him, otherwise you'd fail at some stage of your life, some math exams for sure.
- If another friend of Richael, say Tom, would like to know what Stephen sent to Richael, without asking Stephen or Richael.
- Another guy, say Joseph, was eavesdropping the network communication.
- Either Tom or Joseph would already have access to information of:
- n and e from public key because Richael broadcast it on the network to her friends.
- msg_encrypt because Stephen put it on the network for Richael to retrieve.
- In order to decrypt msg_encrypt, they need private key (n, k);
- They already have n so only need to figure out k.
- k was generated with e and phi.
- They know e. So they only need to know phi.
- They need p and q to know phi
- They know n which is the multiplication of prime numbers p and q
- Tom or Joseph need to do Prime Factorization as n=pxq
- Given n is large enough (1024 bits in nowadays common sense), Tom and Joseph would had been long gone before a modern computer, even they have access to Fugaku, could manage to figure out which 2 prime numebrs Richael picked at the first place, let along about by "6:25 pm tomrrow".
- Richael may choose to update her key pairs frequently (change to different p and q) for the next message; this means Tom and Joseph can never catch up without a Quantum Computer on their hands.
Investigate and Understand Your Computer
Now if go to ~/.ssh, you shall identify a number of different key files. Some of them are private key whilst others are public key; some are generated by OpenSSH whilst others by OpenSSL. They are also encoded by ASN.1 format among some variates.
- You can convert it into
*.PEMfile via:
ssh-keygen -f YOUR_KEY.pub -e -m pem > YOUR_KEY.pub.pem
- Then inspect the content via:
from Crypto.PublicKey import RSA
from base64 import b64decode
pem_key = b"MII<DO NOT SHARE PRIVATE KEY>="
key = b64decode(pem_key)
keyPriv = RSA.importKey(key)
# key now has all the components of the private
print(keyPriv.keydata)
print(keyPriv.n, keyPriv.e, keyPriv.d, keyPriv.p, keyPriv.q, keyPriv.u)
assert keyPriv.p * keyPriv.q == keyPriv.n
For public key *.pub.pem, it has only keyPriv.n and keyPriv.e.
See: https://www.dlitz.net/software/pycrypto/api/2.6/Crypto.PublicKey.RSA-module.html
- Similarly, if you check
less ~/.ssh/known_hosts, you shall see a number of lines of records, composing of:
<domain_name,ip_address> <algorithm, e.g. ssh-rsa> <public_key>
You can convert those public_key into *.pem like above and use the code snippet to check its content. You shall got n and e. When you send message to those servers, your message is encrypted with those n and e, and those server will use their private key to decrypt your message.
Digital Signature
What if Joseph pretends to be Stephen, and sends Richael another message encrypted with Richaels public key, saying "Hello Richael. Let's meet at 6:25 am the day after tomorrow at the train station Gate 1 :)". How does Richael know the message is truly from Stephen, or being pretended by Joseph?
Another case would be Joseph intercepted Stephen's msg_encrypt, then modified/deleted/added some characters in that random stuff ("MHgxNTMzCjB4MmFmNgoweGFiO>B<...YWE0CjB4MWZlMwoweDIzMGY="), before sending to Rachael for decryption? Even though he cannot decrypt the message without Richael's private key, he can still alter it. For example, hiding some information about location:
encry_msg_alter = base64.b64encode(
"\n".join(base64.b64decode(encry_msg).decode("utf8").split("\n")[:33]).encode(
"utf8"
)
)
encry_msg_alter
decry_msg = [
int(i, 16) ** private_key[1] % private_key[0]
for i in base64.b64decode(encry_msg_alter).decode("utf8").split("\n")
]
print(decry_msg)
print("".join([chr(i) for i in decry_msg]))
p = random.choice(list(find_prime(1024)))
q = random.choice(list(find_prime(1024)))
assert check_prime(p)
assert check_prime(q)
n = p * q
p, q, n, len(bin(n)), bin(n)
# Euler number
phi = (p - 1) * (q - 1)
phi
e = random.choice(find_prime(phi))
assert check_prime(e)
e
k = modinv(e, phi)[0]
k
public_key_stephen, private_key_stephen = (n, e), (n, k)
public_key_stephen, private_key_stephen
signature = sha256(b"Hello Richael. Let's meet at 6:25 pm tomorrow at the airport Gate5, Terminal 2 --Stephen :)").hexdigest()
signature
Now Stephen will encrypt this abstract with his private key:
encry_sig = "\n".join(
[
hex((ord(val) ** private_key_stephen[1]) % private_key_stephen[0])
for val in signature
]
)
# base64 encode
encry_sig = base64.b64encode(encry_sig.encode("utf8"))
encry_sig
Finally, the message ready to be shipped to Richael by Stephen becomes:
message_to_Richael = {"msg": encry_msg, "signature": encry_sig}
message_to_Richael
Richael's Verification
Now, what Richael will do is:
- Use her own private key to decrypt msg
- Use Stephen's public key to decrypt signature
- SHA256 Hash the decrypted msg to reproduce the signature
- Compare the 2 signatures and see if they match:
- if they do, the message is from Stephen and it is intact.
- if not, something dodgy happened.
decry_msg = [
int(i, 16) ** private_key[1] % private_key[0]
for i in base64.b64decode(message_to_Richael["msg"]).decode("utf8").split("\n")
]
decry_msg = "".join([chr(i) for i in decry_msg])
print(decry_msg)
decry_sig = [
int(i, 16) ** public_key_stephen[1] % public_key_stephen[0]
for i in base64.b64decode(message_to_Richael["signature"]).decode("utf8").split("\n")
]
print(decry_sig)
print("".join([chr(i) for i in decry_sig]))
sha256(decry_msg.encode("utf8")).hexdigest() == "".join([chr(i) for i in decry_sig])
assert sha256(b"Hello Richael. Let's meet at 6:25").hexdigest() == "".join(
[chr(i) for i in decry_sig]
), "[Attention]: Dodgy thing happened with this message! Be CAREFULL!"
For Joseph, he can also have Stephen's public key, intercept and decrypt the signature. However, if now he wants to alter the message ("random" stuff) without being found out, he must alter the Hash ("22edc929d9211d1102f7af88b85ea472c9e64629074985cba94607526dff3029") as well and make sure they match. Without decrypting the original message, it is infeasible to generated its Hash. Therefore Joseph has 2 options: alter the message and being found out, or leave message as is.
encry_sig_alter = "\n".join(
[
hex((ord(val) ** private_key_stephen[1]) % private_key_stephen[0])
for val in signature[:10]
]
)
# base64 encode
encry_sig_alter = base64.b64encode(encry_sig_alter.encode("utf8"))
encry_sig_alter
decry_sig_alter = [
int(i, 16) ** public_key_stephen[1] % public_key_stephen[0]
for i in base64.b64decode(encry_sig_alter).decode("utf8").split("\n")
]
print(decry_sig_alter)
print("".join([chr(i) for i in decry_sig_alter]))
Certificate
How to Trust Public Keys?
Last issue: How do we trust those public keys received from different identities?
Joseph could totally generate his own key pair and pretend to be Richael. When Richael's friends receive the public key, how do they know it truly comes from Richael, rather than Joseph?
Joseph could also generate another pair of keys, sent the public key to Richael and claming it is from Stephen. How does Richael know the public key is truly from Stephen?
Without verification, Joseph hijacks the information transmission between Richael and Stephen.
Certificate Authority (CA)
CA is similar to the driving license issuer, e.g. Police Station or Government. They will verify identity of servers sharing their public key to other people and make sure it's genuine. For example:
- Stephen, to avoid being pretended by any other indiviudal like Joseph, must visit CA and show all his proof to convence CA that he is the real Stephen.
- Once convenced, CA will take over Stephen's public key plus other personal information, e.g., name, birthday, address, etc, encrypt them with CA's private key, and issue back to Stephen. This is called Certificate.
- When sending message to Richael, Stephen actually sends 3 things:
- Certificate Issued by CA
- Message encrypted by Richael's public key
- Message Signature encrypted by Stephen's private key
- When receiving message from Stephen, Richael does:
- Download the public key of CA and use it to decrypt Certificate included by Stephen. She will obtain Stephen's public key along with other identity information, for example, name, birthday, address, etc.
- Only if she verified those information and confirm it's Stephen, this decrypted Stephen's public key is used to decrypt the signature.
- Decrypt the message with her own private key, and Hash it to reproduce the signature.
- Compare the 2 signaure and see if they match.
p = random.choice(list(find_prime(1024)))
q = random.choice(list(find_prime(1024)))
assert check_prime(p)
assert check_prime(q)
n = p * q
p, q, n, len(bin(n)), bin(n)
# Euler number
phi = (p - 1) * (q - 1)
phi
e = random.choice(find_prime(phi))
assert check_prime(e)
e
k = modinv(e, phi)[0]
k
public_key_CA, private_key_CA = (n, e), (n, k)
public_key_CA, private_key_CA
stephen_info = {"pub_key": str(public_key_stephen), "name": "Stephen"}
str(stephen_info)
certificate = {}
certificate["pub_key"] = base64.b64encode(
"\n".join(
[
hex((ord(val) ** private_key_CA[1]) % private_key_CA[0])
for val in stephen_info["pub_key"]
]
).encode("utf8")
)
certificate["name"] = base64.b64encode(
"\n".join(
[
hex((ord(val) ** private_key_CA[1]) % private_key_CA[0])
for val in stephen_info["name"]
]
).encode("utf8")
)
certificate
message_to_Richael = {"cert": certificate, "msg": encry_msg, "signature": encry_sig}
message_to_Richael
# Step 1: download CA's public key
print("CA Public Key: ", public_key_CA)
# Step 2: verify Stephen's certificate with CA's public key
public_key_st = [
int(i, 16) ** public_key_CA[1] % public_key_CA[0]
for i in base64.b64decode(message_to_Richael["cert"]["pub_key"])
.decode("utf8")
.split("\n")
]
public_key_st = eval("".join([chr(i) for i in public_key_st]))
print("Stepen Public Key: ", public_key_st)
name = [
int(i, 16) ** public_key_CA[1] % public_key_CA[0]
for i in base64.b64decode(message_to_Richael["cert"]["name"])
.decode("utf8")
.split("\n")
]
print("".join([chr(i) for i in name]))
# RSA decode msg with Richael's private key
decry_msg = [
int(i, 16) ** private_key[1] % private_key[0]
for i in base64.b64decode(message_to_Richael["msg"]).decode("utf8").split("\n")
]
decry_msg = "".join([chr(i) for i in decry_msg])
print(decry_msg)
decry_sig = [
int(i, 16) ** public_key_st[1] % public_key_st[0]
for i in base64.b64decode(message_to_Richael["signature"]).decode("utf8").split("\n")
]
print("".join([chr(i) for i in decry_sig]))
sha256(decry_msg.encode("utf8")).hexdigest() == "".join([chr(i) for i in decry_sig])
Now as to Joseph, if still wants to pretend to be Stephen, would have 3 ways to go:
- Go to CA and try to convence them that he is the real Stephen, to have his fake public key certified, or
- Manage to have access to CA's private key, so he can certify himself, or
- Become a CA.
Well...