Skip to content

Instantly share code, notes, and snippets.

@fuglede
Last active August 29, 2015 14:27
Show Gist options
  • Save fuglede/f91f7914e2d7bd368f81 to your computer and use it in GitHub Desktop.
Save fuglede/f91f7914e2d7bd368f81 to your computer and use it in GitHub Desktop.
Create RSA keys containing given strings
#!/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])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment