Create RSA keys containing given strings

sillycerts.py

#!/usr/bin/env python

"""
  This script contains a function to create RSA key pairs whose base64
  representation contains a prescribed string. I can't claim originality of
  the idea behind this as I discovered it originally on /r/crypto some time
  ago. I wish I remembered who the original author was, so I could give credit
  where it is due: please let me know if you know about the original.

  The keys can then be embedded into X.509 certificates for use in SSL
  applications or whatever you want to use RSA keys for.

  NOTE: I have no clue if this practice is secure or not, so certainly do not
  use this for anything where security is important.
"""
from Crypto.PublicKey import RSA
import random
import re
import sys

sys.setrecursionlimit(2000)  # Increase this if you run into recursion issues


# Miller-Rabin primality test, error rate: 2^(-200)
# Implementation by someone on the internets
def is_prime(N):
    if N < 3:
        return N == 2
    s = 0
    d = N - 1
    while (d & 1) == 0:
        s += 1
        d >>= 1
    for i in xrange(100):
        a = random.randrange(1, N)
        if pow(a, d, N) != 1 and all(pow(a, d << r, N) != N - 1 for r in xrange(s)):
            return 0
    return 1


def nearest_prime(N):
    d = 1
    while 1:
        if is_prime(N + d):
            return N + d
        if is_prime(N - d):
            return N - d
        d += 1


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):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def create_silly_key(key_size, silly_string, offset=128):
    # Ensure that the result will be a bit like base64
    if not re.match("^[A-Za-z0-9/+]*$", silly_string):
        raise Exception('string should consist of only alphanumerics, +, and /.')

    # Generate a new key
    freshkey = RSA.generate(int(key_size))
    freshpub = freshkey.publickey()
    freshpubpem = freshpub.exportKey(format='PEM')

    # Create a nonsense 'modulus'. We replace the text that's on the third
    # line. No reason to do this in particular, so change it if you feel like
    # it, by changing the value of 'offset'. YMMV.
    freshpubpemstr = freshpubpem.replace('\n', '')
    freshpubpemstr = re.sub(r'-----(BEGIN|END) PUBLIC KEY-----', '', freshpubpemstr)
    badpubpemstr = re.sub(r'(?<=^.{%d})([\w\d+/]{%d})' % (offset, len(silly_string)), silly_string, freshpubpemstr)
    badpubpemstr = '\n'.join(badpubpemstr[i:i+64] for i in range(0, len(badpubpemstr), 64))
    badpubpem = '-----BEGIN PUBLIC KEY-----\n' + badpubpemstr + '\n-----END PUBLIC KEY-----'

    # Python doesn't care that this modulus is probably not even the product
    # of two primes
    badpubkey = RSA.importKey(badpubpem)

    # Create a new keypair with our old p, but find a new q so that p * q is
    # close to the n we want.
    almostq = int(badpubkey.n / freshkey.p)
    newq = nearest_prime(almostq)
    newn = freshkey.p * newq
    freshkey.q = newq
    freshkey.n = newn
    freshkey.d = modinv(freshkey.e, (freshkey.p-1)*(newq-1))
    freshkey.u = modinv(freshkey.p, newq)
    return freshkey.exportKey(format='PEM')


if __name__ == '__main__':
    if len(sys.argv) != 3:
        print "Error: Must be called with a key size (in bits) and a string argument. E.g.:"
        print "$ python sillycerts.py 4096 lol+silly+string"
        sys.exit()
    print create_silly_key(sys.argv[1], sys.argv[2])