195 lines
6.5 KiB
Python
Executable File
195 lines
6.5 KiB
Python
Executable File
#!/usr/bin/env python
|
||
# -*- coding: utf-8 -*-
|
||
#
|
||
# -------------------------------------
|
||
# RSA Key Generation, Encryption and Decryption example
|
||
# Copyright (C) 2014 Andrey Arapov
|
||
#
|
||
# This program is free software: you can redistribute it and/or modify
|
||
# it under the terms of the GNU General Public License as published by
|
||
# the Free Software Foundation, either version 3 of the License, or
|
||
# (at your option) any later version.
|
||
#
|
||
# This program is distributed in the hope that it will be useful,
|
||
# but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||
# GNU General Public License for more details.
|
||
#
|
||
# You should have received a copy of the GNU General Public License
|
||
# along with this program. If not, see <http://www.gnu.org/licenses/>.
|
||
# -------------------------------------
|
||
#
|
||
#
|
||
# Notes:
|
||
# - Based on the https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Key_generation
|
||
# - The parameters used here are artificially small
|
||
# - I've tried to apply KISS principle here
|
||
#
|
||
#
|
||
|
||
import random
|
||
from fractions import gcd
|
||
|
||
class bcolors:
|
||
RED = '\033[91m'
|
||
DRED = '\033[31m'
|
||
GREEN = '\033[92m'
|
||
YELLOW = '\033[93m'
|
||
BLUE = '\033[94m'
|
||
PURPLE = '\033[95m'
|
||
CYAN = '\033[96m'
|
||
ENDC = '\033[0m'
|
||
|
||
|
||
print "RSA Key Generation, Encryption and Decryption example\n"
|
||
|
||
# -----------------------------------------------------------------------------
|
||
# Generating the Public/Private keypair
|
||
# -----------------------------------------------------------------------------
|
||
|
||
|
||
# Primality test
|
||
# https://en.wikipedia.org/wiki/Primality_test#Python_implementation
|
||
|
||
def is_prime(num):
|
||
if num <= 3:
|
||
if num <= 1:
|
||
return False
|
||
return True
|
||
if not num % 2 or not num % 3:
|
||
return False
|
||
for i in range(5, int(num ** 0.5) + 1, 6):
|
||
if not num % i or not num % (i + 2):
|
||
return False
|
||
return True
|
||
|
||
|
||
# 1. Choose two distinct prime numbers p and q.
|
||
|
||
print "1. looking for two distinct prime numbers p and q in artificially small range..."
|
||
i = 0
|
||
while i < 2:
|
||
rand = random.randint(0x80, 0xff)
|
||
if is_prime(rand):
|
||
if i == 1:
|
||
q=rand
|
||
break
|
||
p=rand
|
||
i += 1
|
||
|
||
print "p =", bcolors.DRED, p, bcolors.ENDC, "\tprime?", is_prime(p), bcolors.YELLOW, "(prime1)", bcolors.ENDC
|
||
print "q =", bcolors.DRED, q, bcolors.ENDC, "\tprime?", is_prime(q), bcolors.YELLOW, "(prime2)", bcolors.ENDC
|
||
print
|
||
|
||
|
||
# 2. Compute n = pq.
|
||
|
||
print "2. computing the modulus n = pq ..."
|
||
n = p * q
|
||
print "n = p * q =", bcolors.DRED, p, bcolors.ENDC, "*", bcolors.DRED, q, bcolors.ENDC, "=", \
|
||
bcolors.BLUE, n, bcolors.ENDC, bcolors.YELLOW, "(modulus)", bcolors.ENDC
|
||
print
|
||
|
||
print "Private-Key will be "+bcolors.YELLOW+str(n.bit_length())+bcolors.ENDC+" bit long\n"
|
||
|
||
|
||
# 3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q - 1), where φ is Euler's totient function.
|
||
|
||
print "3. computing φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function ..."
|
||
f_n = n - (p + q - 1)
|
||
print "φ(n) =", bcolors.DRED, f_n, bcolors.ENDC
|
||
print
|
||
|
||
|
||
# 4. Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime.
|
||
|
||
print "4. looking for an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime ..."
|
||
print "Setting e = 2^16+1 (65537) as per recommendation in\n"+ \
|
||
"Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem - "+ \
|
||
"http://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf\n"
|
||
#e_gcd = 2
|
||
# TOFIX: add smth like --> while (e_gcd != 1) and (e > 3): as e should be > than 3
|
||
#while e_gcd != 1:
|
||
# e = random.randint(1, f_n)
|
||
# e_gcd = gcd(e, f_n)
|
||
|
||
e = 65537
|
||
print "e =", bcolors.CYAN, e, bcolors.ENDC, bcolors.YELLOW, "(publicExponent)", bcolors.ENDC
|
||
print
|
||
|
||
# 5. Determine d as d ≡ e^−1 (mod φ(n)); i.e., d is the multiplicative inverse of e (modulo φ(n)).
|
||
# http://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm#Modular_inverse
|
||
|
||
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):
|
||
gcd, x, y = egcd(a, m)
|
||
if gcd != 1:
|
||
return None # modular inverse does not exist
|
||
else:
|
||
return x % m
|
||
|
||
print "5. Determining d as d ≡ e^−1 (mod φ(n)); i.e., d is the multiplicative inverse of e (modulo φ(n)) ..."
|
||
d = modinv(e, f_n)
|
||
print "d =", bcolors.RED, d, bcolors.ENDC, bcolors.YELLOW, "(privateExponent)", bcolors.ENDC
|
||
print
|
||
|
||
print "Public key is modulus n =", bcolors.BLUE, n, bcolors.ENDC, "and the public (or encryption) exponent e =", \
|
||
bcolors.CYAN, e, bcolors.ENDC
|
||
print
|
||
print "Private key is modulus n =", bcolors.BLUE, n, bcolors.ENDC, "and the private (or decryption) exponent d =", \
|
||
bcolors.RED, d, bcolors.ENDC, "and it must be kept secret"
|
||
print bcolors.DRED+"p"+bcolors.ENDC+","+bcolors.DRED+" q"+bcolors.ENDC+", and"+bcolors.DRED+" φ(n) "+bcolors.ENDC+ \
|
||
"must also be kept secret because they can be used to calculate "+bcolors.RED+"d"+bcolors.ENDC+"."
|
||
print
|
||
|
||
|
||
|
||
# -----------------------------------------------------------------------------
|
||
# Encrypting: c = m^e (mod n)
|
||
# -----------------------------------------------------------------------------
|
||
|
||
print "To encrypt message m: c = m^e (mod n)"
|
||
|
||
#mstr = "hi"
|
||
cstr = ""
|
||
mstr = raw_input("Enter your message m: ")
|
||
for m in [elem.encode("hex") for elem in mstr]:
|
||
print ":: encrypting ", bcolors.YELLOW, '"'+chr(int(m, 16))+'"', \
|
||
int(m, 16), bcolors.ENDC, " >>>", bcolors.YELLOW, int(m, 16), \
|
||
bcolors.ENDC, "^", bcolors.CYAN, e, bcolors.ENDC, \
|
||
"( mod", bcolors.BLUE, n, bcolors.ENDC, ")", ">>> ",
|
||
c = ( int(m, 16) ** e ) % n
|
||
print bcolors.PURPLE, c, bcolors.ENDC
|
||
cstr += str(c)
|
||
cstr += ","
|
||
|
||
cstr = cstr[:-1]
|
||
print "Your encrypted message m is now a ciphertext c =", bcolors.YELLOW, cstr, bcolors.ENDC
|
||
print
|
||
|
||
|
||
# -----------------------------------------------------------------------------
|
||
# Decrypting: m = c^d (mod n)
|
||
# -----------------------------------------------------------------------------
|
||
|
||
print "To decrypt ciphertext c: m = c^d (mod n)"
|
||
mstr = ""
|
||
for c in cstr.split(","):
|
||
print ":: decrypting ", bcolors.PURPLE, c, bcolors.ENDC, " >>>", \
|
||
bcolors.PURPLE, int(c), "^", bcolors.ENDC, bcolors.RED, \
|
||
d, bcolors.ENDC, "( mod", bcolors.BLUE, n, bcolors.ENDC, ")", ">>>",
|
||
m = ( int(c) ** d ) % n
|
||
print bcolors.YELLOW, m, '"'+chr(m)+'"', bcolors.ENDC
|
||
mstr += chr(m)
|
||
|
||
print "Decrypted ciphertext is now m =", bcolors.YELLOW, mstr, bcolors.ENDC
|
||
print
|
||
|
||
|