Cracking a password with a known structure.

gistfile1.py

import random
import string
import itertools

def random_capitalize(start):
    out = ''
    for char in start:
        out += char.upper() if random.randrange(2) else char.lower()
    return out

def gen_capitalize(start):
    valid_indices = {i for i in range(len(start)) if start[i] in string.ascii_lowercase}
    for num_cap in range(len(start) + 1):
        for indices in itertools.combinations(valid_indices, num_cap):
            startlist = list(start)
            for index in indices:
                startlist[index] = startlist[index].upper()
            yield ''.join(startlist)

def random_insert(start, alphabet, num):
    ret = start
    for i in range(num):
        letter = alphabet[random.randrange(len(alphabet))]
        index = random.randrange(len(ret) + 1)
        ret = ret[:index] + letter + ret[index:]
    return ret

def gen_random_insert(start, alphabet, num):
    for indices in itertools.combinations(range(len(start)+num), num):
        for chars in itertools.product(alphabet, repeat=num):
            startlist = list(start)
            for i in range(num):
                startlist.insert(indices[i], chars[i])
            yield ''.join(startlist)

def random_insert(start, alphabet, num):
    ret = start
    for i in range(num):
        letter = alphabet[random.randrange(len(alphabet))]
        index = random.randrange(len(ret) + 1)
        ret = ret[:index] + letter + ret[index:]
    return ret

def random_password_and_known():
    password = random_insert("", string.ascii_lowercase, 6)
    password = random_insert(password, string.digits, 2)
    known = password
    password = random_capitalize(password)
    password = random_insert(password, string.punctuation, 2)
    return (password, known)

def crack(known, oracle):
    i = 0
    for start in gen_capitalize(known):
        for andpunc in gen_random_insert(start, string.punctuation, 2):
            i += 1
            if oracle(andpunc):
                ret = andpunc
                print("Found", ret, "at index", i)
    print("Ultimately", i)
    return ret

def test():
    password, known = random_password_and_known()
    print("The real password:", password)
    print("The known component:", known)
    def oracle(candidate):
        return candidate == password
    crack(known, oracle)