Skip to content

Instantly share code, notes, and snippets.

@Lohann

Lohann/rsa-example.py

Last active February 6, 2026 11:55
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Lohann/e49adaaed17a94144676b49c2a7c239a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Lohann/e49adaaed17a94144676b49c2a7c239a to your computer and use it in GitHub Desktop.
Download ZIP
Example of RSA encryption, digital signature and onion encryption
Raw
rsa-example.py
import random
import math
import hashlib
die = random.SystemRandom() # Secure random generator
##################
## Miller Rabin ##
##################
'''
Probabilistic primarly test
'''
def single_test(n, a):
exp = n - 1
while not exp & 1:
exp >>= 1
if pow(a, exp, n) == 1:
return True
while exp < n - 1:
if pow(a, exp, n) == n - 1:
return True
exp <<= 1
return False
def miller_rabin(n, k=40):
for i in range(k):
a = die.randrange(2, n-1)
if not single_test(n, a):
return False
return True
'''
Generate prime number randomly
'''
def gen_prime(bits=1024):
mask = (1 << (bits - 1)) | 1
while True:
p = die.getrandbits(bits)
p |= mask
if miller_rabin(p, 40):
return p
#########
## RSA ##
#########
'''
Ref: https://gist.github.com/JekaDeka/c9b0f5da16625e3c7bd1033356354579
​
Euclid's extended algorithm for finding the multiplicative inverse of two numbers
'''
def extended_euclidean_algorithm(a, b):
"""
Returns a three-tuple (gcd, x, y) such that
a * x + b * y == gcd, where gcd is the greatest
common divisor of a and b.
​
This function implements the extended Euclidean
algorithm and runs in O(log b) in the worst case.
"""
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = b, a
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
return old_r, old_s, old_t
def is_coprime(x, y):
"""
`x` is relative prime to `y` when `gcd(x, y) == 1`
"""
return math.gcd(x,y) == 1
class PrivateKey:
"""
Private Key
Used to decrypt messages and sign messages
"""
def __init__(self, d, n):
assert isinstance(d, int) and isinstance(n, int)
self.d = d # Private Key (decryption and signing)
self.n = n # Product of two big primes
def decrypt(self, encrypted):
if isinstance(encrypted, (bytes, bytearray)):
encrypted = int.from_bytes(encrypted, byteorder='big')
if encrypted >= self.n:
raise ValueError("message too big to decrypt")
return pow(encrypted, self.d, self.n)
def sign_message(self, message):
if isinstance(message, str):
message = message.encode("utf-8")
message_hash = hashlib.sha256(message).digest()
message_hash = int.from_bytes(message_hash) % self.n
return self.decrypt(message_hash)
class PublicKey:
"""
Public Key
Used to encrypt messages and verify signatures.
"""
def __init__(self, e, n):
assert isinstance(e, int) and isinstance(n, int)
self.e = e # Public Key (encryption or signature verification)
self.n = n # Product of two big primes
def encrypt(self, message):
if isinstance(message, (bytes, bytearray)):
message = int.from_bytes(message, byteorder='big')
if message >= self.n:
raise ValueError("message too big to encrypt")
return pow(message, self.e, self.n)
def verify_signature(self, message, signature):
if isinstance(message, str):
message = message.encode("utf-8")
message_hash = hashlib.sha256(message).digest()
message_hash = int.from_bytes(message_hash) % self.n
return self.encrypt(signature) == message_hash
'''
Create a new RSA Key Pair
'''
def new_keypair(bits = 1024):
# p and q are two big prime numbers generated randomly
p = gen_prime(bits)
q = gen_prime(bits)
# Compute the modulus by multipling two big primes
n = p * q
# Compute `qn` which is a quotient divisible by the order
# of all sub-groups in the form `x ** e in Zn`
qn = n - p - q + 1
# Find a value `e` greater than 3 and relative prime to `qn`.
e = 65537 # ref: https://en.wikipedia.org/wiki/65,537
while not is_coprime(e, qn):
e = die.randrange(3, qn - 1)
# Compute `d = 1/e mod qn`
(_, d, _) = extended_euclidean_algorithm(e, qn)
# Make sure `d` is positive
d = d % qn
# Create the assimetric key pair
private_key = PrivateKey(d, n)
public_key = PublicKey(e, n)
return (private_key, public_key)
####################
## Create Keypair ##
####################
(private_key, public_key) = new_keypair(256)
assert private_key.n == public_key.n
print(f"decryption key (d) = {hex(private_key.d)}")
print(f"encryption key (e) = {hex(public_key.e)}")
print(f" modulus (n) = {hex(private_key.n)}\n\n")
################
## Encryption ##
################
# Obs: only works when message is an integer such that `message < (n / 2)`
message = 0xDEADBEEF
# encrypted = message ** e % n
encrypted = public_key.encrypt(message)
# decrypted = encrypted ** d % n
decrypted = private_key.decrypt(encrypted)
print(f" message = {hex(message)}")
print(f" encrypted = {hex(encrypted)}")
print(f" decrypted = {hex(decrypted)}\n\n")
#######################
## Digital Signature ##
#######################
# 1. Only the `private_key` can generate a valid signature.
# 2. The `public_key` can verify if the signature is valid.
# 3. Messages of arbitrary size can be signed and verified.
message = "My super cool signed message"
message_hash = hashlib.sha256(message.encode('utf8')).hexdigest()
# signature = sha256(message) ** d % n
signature = private_key.sign_message(message)
# encrypted_signature = signature ** e % n
encrypted_signature = public_key.encrypt(signature)
# is_valid = (signature ** e % n) == sha256(message)
is_valid = public_key.verify_signature(message, signature)
print(f" message = {message}")
print(f" sha256(message) = 0x{message_hash}")
print(f" digital signature = {hex(signature)}")
print(f"encrypt(signature) = {hex(encrypted_signature)}")
print(f"is signature valid = {is_valid}\n")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment