My program generates public private keys, encrypts, decrypts, signs and verifies, while using AES for the bulk of the data for speed, and encrypts the random key with RSA. Many operations were chosen for speed. This works out of the box on 3.6+ . Windows idle env disallows it from working there, but Linux and mac is ideal. I do call gzip which I know I can replace with a module. I almost want to do my own Huffman coding for it but I don't know where to draw the line.
The RSA and DSA portions are written from number theory and don't use the modules, that was the point. I don't know how to put this in the title without it being edited it out. The RSA and DSA portions are manual implementations of the mathematics. The prime finding algorithms are implementations of two theorems, applied in an order to achieve maximum sieving speed.I did away with my lucas test as doing a large number of Miller Rabin tests produces a probability of 1 of being prime.
I'm using this as an educational tool to force the unwilling learners to kinetically understand public and private key cryptography when passed on a USB etc. in a classroom setting. To see the clicks in peoples eyes when they understand signing or the like, that's why I'm sharing this code. I know there's much better ways to handle the data concatenation, but am happy that I'm processing the data at a binary level.
I love the prime number theorem and so should you.
#!/usr/bin/env python3
import os
import sys
import math
import re
import hashlib
import random
import base64
import string
import getpass
import multiprocessing as mp
from Crypto.Cipher import AES
from Crypto import Random
from Crypto.Protocol.KDF import PBKDF2
#Primality testing, extended greatest common divisor and least common multiple
def isprime(n):
if not n & 1: #check if first bit is 1
return False
for i in (3,5,7,11):
if divmod(n, i)[1] == 0:
return False
#Fermat
if (pow(2, n-1, n)) != 1:
return False
#MilRab, x**2 = 1 mod P - ERH
s = 0
d = n-1
while not d & 1:
d>>=1 #shifts binary rep of number right one place, same as dividing by 2^d
s+=1
assert(2**s * d == n-1) #Process to find s and d
def trial_composite(a):
if pow(a, d, n) == 1:
return False
for i in range(s):
if pow(a, 2**i * d, n) == n-1:
return False
return True
for i in range(100):#Number of Rabin Witness
a = random.randrange(2, n-1)
if trial_composite(a):
return False
return True
def get1prime(keysize):
while True:
p = random.randrange(1<<(keysize), 1<<(keysize+2))
if isprime(p):
return p
def modInverse(a, m) : #Euclid's Extended Algorithm
m0 = m
y = 0
x = 1
while (a > 1) :
q = a // m
t = m
m = divmod(a,m)[1]
a = t
t = y
y = x - q * y
x = t
if (x < 0) :
x = x + m0
return x
def lcm(x, y):
lcm = (x*y)//math.gcd(x,y)
return lcm
##AES256CHUNK
def get_private_key(password):
salt = b"We will know, we must know"
kdf = PBKDF2(password, salt, 64, 1000)
key = kdf[:32]
return key
def encryptaes(raw, password):
private_key = password
raw = pad(raw)
iv = Random.new().read(AES.block_size)
cipher = AES.new(private_key, AES.MODE_CBC, iv)
return base64.b64encode(iv + cipher.encrypt(raw))
def decryptaes(enc, password):
private_key = password
enc = base64.b64decode(enc)
iv = enc[:16]
cipher = AES.new(private_key, AES.MODE_CBC, iv)
return unpad(cipher.decrypt(enc[16:]))
BLOCK_SIZE = 128 #Block is 128 no matter what,this is multiple of 16
pad = lambda s: s + (BLOCK_SIZE - len(s) % BLOCK_SIZE) * chr(BLOCK_SIZE - len(s) % BLOCK_SIZE)
unpad = lambda s: s[:-ord(s[len(s) - 1:])]
#RSA
#Unique and Arbitrary Pub E, a prime.
e = 66047 # because I can
#e = 65537
def encryptit(e, n, thestring):#for sigining pass d as e
rbinlist = ['{0:08b}'.format(x) for x in thestring]
catstring = ''
catstring += rbinlist[0].lstrip('0')
del rbinlist[0]
for i in rbinlist:
catstring += str(i)
puttynumber = int(catstring,2)
cypherstring = str(pow(puttynumber, e, n))
return cypherstring
def decryptit(d, n, cynum):#for signing pass e as d
decryptmsg = ''
n = int(n)
d = int(d)
puttynum = pow(int(cynum), d, n)
puttynum = '{0:08b}'.format(puttynum)
while True:
if len(puttynum)%8 == 0:
break
puttynum = '0{0}'.format(puttynum)
locs = re.findall('[01]{8}', puttynum)
for x in locs:
letter = chr(int(x,2))
decryptmsg += letter
return decryptmsg
#Begin User Flow
choice = input("""
Welcome to Dan's Cryptography Concept Program.
Generate/Encrypt/Decrypt/Sign
RSA++/DSA++/AES/OTP/Double DH key exch w SHA
Choose:
A: Generate New Public/Private Key Pair
B: Encrypt a File
C: Decrypt a File
=> """)
if choice == 'A' or choice == 'a':
try:
keysize = (int(input("Enter a keysize: "))>>1)
except ValueError as a:
print('Enter a number\n\n')
sys.exit()
pubkeyname = input('Input desired public key name: ')
pkey = input('Input desired private key name: ')
pwkey = get_private_key(getpass.getpass(prompt='Password to protect your private key: ', stream=None))
print('Generating Keys...')
primes = []
plist = []
for i in range(mp.cpu_count()):
plist.append(keysize)
workpool = mp.Pool(processes=mp.cpu_count())
reslist = workpool.imap_unordered(get1prime, plist)
workpool.close()
for res in reslist:
if res:
primes.append(res)
workpool.terminate()
break
workpool.join()
#
workpool1 = mp.Pool(processes=mp.cpu_count())
reslist = workpool1.imap_unordered(get1prime, plist)
workpool1.close()
for res in reslist:
if res:
primes.append(res)
workpool1.terminate()
break
workpool1.join()
if primes[0] != primes[1]:
p, q = primes[0], primes[1]
else:
print('Supremely Unlucky Try Again')
exit()
n = p*q
cm = lcm(p-1, q-1)
print('Computing Private key ...')
d = modInverse(e, cm)
print('Private Key Size: {} bits'.format(keysize*2))
print('Functional Length of: {}'.format(len(bin((d)))))
keystring = encryptaes(str(d).encode('ascii', errors='ignore').decode('utf-8'),pwkey)
b64key = bytes.decode(base64.encodestring(bytes(str(hex(n)).encode())))
with open(pkey, 'w') as f1:
f1.write(str(n)+'\n')
f1.write(bytes.decode(keystring))
with open(pubkeyname, 'w') as f2:
f2.write(b64key)
print('Complete - {} and {} generated'.format(pubkeyname,pkey))
print('e exponent: {}'.format(str(e)))
print("""
-----BEGIN PUBLIC KEY-----
{}-----END PUBLIC KEY-----
""".format(b64key))
b64privkey = b64key = bytes.decode(base64.encodestring(bytes(str(hex(d)).encode())))
print("""
-----BEGIN PRIVATE KEY-----
{}-----END PRIVATE KEY-----
""".format(b64privkey))
if choice == 'B' or choice == 'b':
lineoutholder = []
pubkeyname = input('Enter PUBLIC key to encrypt with(recepient): ')
privkey = input('Enter your private KEY you wish to sign with(yours): ')
pwkey = get_private_key(getpass.getpass(prompt='Password for your private key: ', stream=None))
try:
with open(pubkeyname, 'r') as f1:
pubkey = f1.read()
except:
print('bad keyname')
exit()
uhaeskey = ''.join([random.choice(string.ascii_letters + string.digits) for n in range(32)])
n = int(bytes.decode(base64.decodestring(bytes(pubkey.encode()))), 16)
workfile = input('Enter the file to ENCRYPT: ')
outfile = input('Enter filename to WRITE out: ')
sha256_hash = hashlib.sha256()
try:
with open(workfile, 'rb') as f2:
wholefile = f2.read()
with open(workfile, 'rb') as f2:#open again to clear memory
for byte_block in iter(lambda: f2.read(4096),b""):
sha256_hash.update(byte_block)
HASH = sha256_hash.hexdigest()
with open(privkey) as f3:
priv = f3.readlines()
except Exception as x:
print(x)
exit()
d = int(bytes.decode(decryptaes(priv[1], pwkey)))
HASH = [ord(i) for i in HASH]
numhash = ''
for i in HASH:
numhash +=str(i)
signature = pow(int(numhash), d, int(priv[0]))
aeskey = get_private_key(uhaeskey)
plaintext = base64.encodestring(wholefile)
cyphertext = bytes.decode(encryptaes(plaintext.decode('ascii'), aeskey))
shippedpw = encryptit(e, n, uhaeskey.encode())
concat = str(str(signature)+'CUTcutCUTcutCUT'+shippedpw+'CUTcutCUTcutCUT'+cyphertext)
with open(outfile, 'w') as f3:
f3.write(concat)
os.system('gzip -9 {0};mv {0}.gz {0}'.format(outfile))
print('Wrote to {} ...'.format(outfile))
if choice == 'C' or choice == 'c':
dspubkeyname = input('Enter the PUBLIC key to verify the signature with(sender): ')
try:
with open(dspubkeyname, 'r') as f1:
pubkey = f1.read()
except:
print('bad keyname')
exit()
nsig = int(bytes.decode(base64.decodestring(bytes(pubkey.encode()))), 16)
privkey = input('YOUR private KEY filename to decrypt the data: ')
pwkey = get_private_key(getpass.getpass(prompt='Password for your private keyfile: ', stream=None))
workfile = input('Enter the file to DECRYPT: ')
outfile = input('Enter the filename to WRITE out: ')
print('DECRYPTING')
os.system('mv {0} {0}.gz;gzip -d {0}.gz'.format(workfile))
sha256_hash = hashlib.sha256()
try:
with open(workfile) as f1:
lineholder = f1.read().split('CUTcutCUTcutCUT')
signature, codedkey, cyphertext =lineholder[0], lineholder[1], lineholder[2]
except:
print('Bad file name or path')
exit()
try:
with open(privkey) as f2:
priv = f2.readlines()
except:
print('Bad private key location')
n = priv[0]
d = int(bytes.decode(decryptaes(priv[1], pwkey)))
sigdec = pow(int(signature), e, nsig)#Sig Verification step1
aeskey = decryptit(d, n, codedkey)
aeskey = get_private_key(aeskey)
decstr = bytes.decode(decryptaes(cyphertext, aeskey))
cleartext = base64.decodestring(bytes(decstr, 'ascii'))
with open(outfile, 'wb') as f1:
f1.write(cleartext)
with open(outfile, 'rb') as f2:
for byte_block in iter(lambda: f2.read(4096),b""):
sha256_hash.update(byte_block)
HASH = sha256_hash.hexdigest()
HASH = [ord(i) for i in HASH]
numhash = ''
for i in HASH:
numhash +=str(i)
if int(numhash) == int(sigdec):
print('Signature Verified')
else:
print('FAILURE, bad hash...')
print('Wrote out to {} '.format(outfile))
#, the syntax highlighter does not get confused by'in the comments. \$\endgroup\$