[back]
Python RSA Public Private Key Encryption SSH using ssh-keyen
modified: 2015-03-22 04:22:15

This will read a public key file and a non-encrypted private key file generated by ssh-keygen and encrypt and decrypt some data. Also, of use is two functions which convert from base 256 to integer. The toi256 converts from little-endian format, and the toi256r converts from big-endian.

    '''
        ssh-keygen -t rsa -b 4096
        ssh-keygen -t rsa -b 8192
    '''
    import random
    import math
    import base64
    import struct
    
    def __gen_prime(N=10**8, bases=range(2,20000)):
        p = 1
        while any(pow(base, p-1, p) != 1 for base in bases):
            p = random.SystemRandom().randrange(N)
        return p
    
    def __multinv(modulus, value):
        '''Multiplicative inverse in a given modulus
    
            >>> multinv(191, 138)
            18
            >>> 18 * 138 % 191
            1
            http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
        '''
        x, lastx = 0, 1
        a, b = modulus, value
        while b:
            a, q, b = b, a // b, a % b
            x, lastx = lastx - q * x, x
        result = (1 - lastx * modulus) // value
        return result + modulus if result < 0 else result
    
    def keygen(N):
        '''Generate public and private keys from primes up to N.
    
            >>> pubkey, privkey = keygen(2**64)
            >>> msg = 123456789012345
            >>> coded = pow(msg, 65537, pubkey)
            >>> plain = pow(coded, privkey, pubkey)
            >>> assert msg == plain
            http://en.wikipedia.org/wiki/RSA
        '''
        prime1 = __gen_prime(N)
        prime2 = __gen_prime(N)
        totient = (prime1 - 1) * (prime2 - 1)
        return prime1 * prime2, __multinv(totient, 65537)
    
    '''
        This function expects bytes not str.
    '''
    def toi256(data):
        t = 0
        n = 1
        for b in data:
            b = b
            t = t + (b * n)
            n = n * 256
        return t
    
    def toi256r(data):
        t = 0
        n = 1
        i = len(data) - 1
        while i > -1:
            b = data[i]
            t = t + (b * n)
            n = n * 256
            i = i - 1
        return t
    
    def fromi256(i):
        o = []
        m = 1
        while m < i:
            m = m * 256
        if m > i:
            m = divmod(m, 256)[0]
        while i > 0:
            r = divmod(i, m)[0]
            o.insert(0, r)
            i = i - (r * m)
            m = m >> 8
        return bytes(o)
    
    def crypt(data, key):
        exp = toi256(key[0])
        pubkey = toi256(key[1])
    
        data = toi256(data)
    
        # value, exponent, modulus
    
        data = pow(data, exp, pubkey)
        return fromi256(data)
    
    def decrypt(data, key):
        prikey = toi256(key[0])
        pubkey = toi256(key[1])
    
        data = toi256(data)
        data = pow(data, prikey, pubkey)
        return fromi256(data)
    
    def readKeyFile(path):
        fd = open(path, 'r')
        lines = fd.readlines()
        fd.close()
    
        out = []
        for line in lines:
            line = line.strip()
            if line.find(':') < 0 and line.find('-') < 0:
                out.append(line)
    
        out = ''.join(out)
    
        return base64.b64decode(bytes(out, 'utf8'))
    
    def readSSHPublicKey(path):
        '''
            do not ask me.. had lots of trouble digging through openssh
            source.. building it.. producing different results... LOL..
                i just gave up and hacked this together
        '''
        fd = open(path, 'rb')
        data = fd.read()
        fd.close()
        data = data.split(b' ')
        data = data[1]
    
        data = base64.b64decode(data)
    
        sz = struct.unpack_from('>I', data)[0]
        data = data[4:]
        type = data[0:sz]
        data = data[sz:]
    
        sz = struct.unpack_from('>I', data)[0]
        data = data[4:]
        exp = data[0:sz]
        data = data[sz:]
    
        sz = struct.unpack_from('>I', data)[0]
        data = data[4:]
        mod = data[0:sz]
    
        return (exp, mod)
    
    def readSSHPrivateKey(path):
        data = readKeyFile(path)
    
        fields = []
    
        data = data[4:]
        ndx = 0
    
        while len(data) > 0:
            type = data[0]
            data = data[1:]
    
            sz = data[0]
            data = data[1:]
    
            if sz == 0x82:
                sz = data[0] << 8 | data[1]
                data = data[2:]
    
            # create field
            field = (type, data[0:sz])
            # drop used data
            data = data[sz:]
    
            # add field
            fields.append(field)
            fields[ndx] = field
            ndx = ndx + 1
    
        return (fields[3][1], fields[1][1])
    
        pub = pubcrypt.readSSHPublicKey('id_rsa.pub')
        # this contains the public key and private key
        pri = pubcrypt.readSSHPrivateKey('id_rsa')
    
        # pub[0] == exponent
        # pub[1] == public key
        # pri[0] == public key
        # pri[1] == private key
    
        '''
            Well, this is a big oops. You see I started converting between
            Python large integers and byte form with a little endian format,
            but SSH keys are stored using a big endian. So here I am just
            converting from big-endian to little-endian.
    
            Now, you may ask WHY?? Well, I *finally* got the code working and
            I am tired of messing with it. So I am leaving it like this and
            hopefully one day I will go back in and fix this by making all
            my functions work with big endian...
    
            Anyway.. for gods sake it finally works!!!
        '''
        keypub = (pubcrypt.fromi256(pubcrypt.toi256r(pub[0])), pubcrypt.fromi256(pubcrypt.toi256r(pub[1])))
        keypri = (pubcrypt.fromi256(pubcrypt.toi256r(pri[0])), pubcrypt.fromi256(pubcrypt.toi256r(pri[1])))
    
        data = pubcrypt.crypt(data, keypub)
        data = pubcrypt.decrypt(data, keypri)