gistfile1.py

import math


def find_inverse(a, mod):   # uses the euklid algorithm to calculate the
                            # modular inverse of a mod mod
    original_mod, before_mod = mod, mod
    qs = []
    while mod != 0:
        if mod != before_mod:  # skip 1st run
            qs.insert(0, int(math.floor(a / mod)))  # prepend rather than
                                                    # append so we can later
                                                    # just iterate over it
        before_mod = mod
        a, mod = mod, a % mod
    if before_mod != 1:     # gcd(a, mod) is not 1, thus there is no modular
                            # inverse
        raise ValueError

    s, t, qs = 0, 1, qs[1:]
    for q in qs:  # After the last run t is the solution
        s, t = t, s - (q * t)

    if t < 0:   # if t is < 0 add the modulo value to it so that it is in
                # the correct range
        t = original_mod + t

    return t


def decrypt(chiffrat, a, b):
    plaintext = ''
    for y in chiffrat:
        index = ord(y) - 65  # Offset to 0
        x_index = find_inverse(a, 26) * (index - b) % 26    # decrypt-algorithm
                                                            # for the affine
                                                            # cipher
        x_index += 65  # Get the ASCII-Index
        plaintext += chr(x_index)  # Append ASCII char to result

    return plaintext


if __name__ == "__main__":
    # Decrypt the string from 1.a
    print decrypt('GWDPCTLSDJWGJBNWJLKOJLJWEPBDBGEDJSHJBLCT', 5, 15)

    # Bruteforce for 1.b
    chiffrat = 'BLUWXTSBMSBZVXUWZMSRWLUAZMUXZKNARSZMNHBWWRABZMA'
    for a in range(26):
        for b in range(26):
            try:
                dec = decrypt(chiffrat, a, b)
                print "(%d, %d): %s" % (a, b, dec)  # Output the key and the
                                                    # decrypted value
            except ValueError:  # not a valid key-pair
                pass