Skip to content

Instantly share code, notes, and snippets.

@ErbaAitbayev
Created October 5, 2016 08:28
Show Gist options
  • Save ErbaAitbayev/8f491c04af5fc1874e2b0744965a732b to your computer and use it in GitHub Desktop.
Save ErbaAitbayev/8f491c04af5fc1874e2b0744965a732b to your computer and use it in GitHub Desktop.
Simple Python RSA for digital signature with hashing implementation. For hashing SHA-256 from hashlib library is used.
import random
from hashlib import sha256
def coprime(a, b):
while b != 0:
a, b = b, a % b
return a
def extended_gcd(aa, bb):
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
#Euclid's extended algorithm for finding the multiplicative inverse of two numbers
def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise Exception('Modular inverse does not exist')
return x % m
def is_prime(num):
if num == 2:
return True
if num < 2 or num % 2 == 0:
return False
for n in range(3, int(num**0.5)+2, 2):
if num % n == 0:
return False
return True
def generate_keypair(p, q):
if not (is_prime(p) and is_prime(q)):
raise ValueError('Both numbers must be prime.')
elif p == q:
raise ValueError('p and q cannot be equal')
n = p * q
#Phi is the totient of n
phi = (p-1) * (q-1)
#Choose an integer e such that e and phi(n) are coprime
e = random.randrange(1, phi)
#Use Euclid's Algorithm to verify that e and phi(n) are comprime
g = coprime(e, phi)
while g != 1:
e = random.randrange(1, phi)
g = coprime(e, phi)
#Use Extended Euclid's Algorithm to generate the private key
d = modinv(e, phi)
#Return public and private keypair
#Public key is (e, n) and private key is (d, n)
return ((e, n), (d, n))
def encrypt(privatek, plaintext):
#Unpack the key into it's components
key, n = privatek
#Convert each letter in the plaintext to numbers based on the character using a^b mod m
numberRepr = [ord(char) for char in plaintext]
print("Number representation before encryption: ", numberRepr)
cipher = [pow(ord(char),key,n) for char in plaintext]
#Return the array of bytes
return cipher
def decrypt(publick, ciphertext):
#Unpack the key into its components
key, n = publick
#Generate the plaintext based on the ciphertext and key using a^b mod m
numberRepr = [pow(char, key, n) for char in ciphertext]
plain = [chr(pow(char, key, n)) for char in ciphertext]
print("Decrypted number representation is: ", numberRepr)
#Return the array of bytes as a string
return ''.join(plain)
def hashFunction(message):
hashed = sha256(message.encode("UTF-8")).hexdigest()
return hashed
def verify(receivedHashed, message):
ourHashed = hashFunction(message)
if receivedHashed == ourHashed:
print("Verification successful: ", )
print(receivedHashed, " = ", ourHashed)
else:
print("Verification failed")
print(receivedHashed, " != ", ourHashed)
def main():
p = int(input("Enter a prime number (17, 19, 23, etc): "))
q = int(input("Enter another prime number (Not one you entered above): "))
#p = 17
#q=23
print("Generating your public/private keypairs now . . .")
public, private = generate_keypair(p, q)
print("Your public key is ", public ," and your private key is ", private)
message = input("Enter a message to encrypt with your private key: ")
print("")
hashed = hashFunction(message)
print("Encrypting message with private key ", private ," . . .")
encrypted_msg = encrypt(private, hashed)
print("Your encrypted hashed message is: ")
print(''.join(map(lambda x: str(x), encrypted_msg)))
#print(encrypted_msg)
print("")
print("Decrypting message with public key ", public ," . . .")
decrypted_msg = decrypt(public, encrypted_msg)
print("Your decrypted message is:")
print(decrypted_msg)
print("")
print("Verification process . . .")
verify(decrypted_msg, message)
main()
@YannickSF
Copy link

Hello,
This ghost is awesome Thanks for it.
I found an issue, when i choose primes pair number under '11' the verification fall in failed.
IDK if it's a numeric problem or what else.

@atsangcc
Copy link

atsangcc commented Aug 3, 2022

Hi ErbaAitbayev ,

Based on your work,I did a coding assignment :

and youtube demo :

This assignment is about : * Image Encryption , * Image Compression , * Huffman Coding & * RSA Algorithm .

Thank You.

Best Regards,
Albert T.

@Ricky610329
Copy link

Your code is awesome!!
It's easy to modify to meet up my needs!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment