Ggthjy

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 numbernn')

       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))

Here's a couple small points that aren't a full review, but might be helpful.

% exists instead of divmod for when you only care about the modulo.

In modInverse

   q = a // m

   t = m

   m = divmod(a,m)[1]

   a = t

   t = y

   y = x - q * y

   x = t

could be written more clearly as

   q = a // m

   t = m

   a, m = m, a%m

   x, y = y, x - q*y

For LCM computation, you should probably rewrite it as return x//math.gcd(x,y) * y as that will keep your numbers smaller, which is always nice (especially when x and y might both be big).

Also, you're RSA implementation isn't secure for details of why see textbook rsa flaws. If you care, the solution is to use something like PKCS which is a padding scheme to provide semantic security, and to fix some other problems.

Here is the padded improved code from the suggestions here:

#!/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

#Non builtins

from gmpy2 import is_prime as isprime

from gmpy2 import is_strong_bpsw_prp as ispprime

#Primality testing, extended greatest common divisor and least common multiple



def get1prime(keysize):

    while True:

        p = random.randrange(1<<(keysize), 1<<(keysize+2))

        if isprime(p):

            if ispprime(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):

   return (x*y)//math.gcd(x,y)



##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 = 64 #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

    thestring = pad(str(thestring)).encode()

    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 unpad(decryptmsg)[2:-1]



#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 numbernn')

        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:

        os.system('gzip -9 {0};mv {0}.gz {0}'.format(workfile))

        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};mv {1} {1}.gz;gzip -d {1}'.format(outfile, workfile))

    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...')

    os.system('mv {0} {0}.gz;gzip -d {0}.gz;rm {1}'.format(outfile, workfile))

    print('Wrote out to {} '.format(outfile))