4
\$\begingroup\$

I have written a pair of programs in Python that can be used to encrypt, decrypt, and crack Caesar and Vigenere Ciphered text. I am fairly new to Python and I wrote these programs largely to try and test myself on what I had learned so far with a practical problem, although I cannot claim that every line of these programs is my own. I would appreciate feedback related to any aspect of my program: Efficiency of my algorithms, efficiency of my implementation, quality of my Python, overlooked features, bugs, etc.

I have included a sample of text I used for testing below.

vigenere.py

#!/usr/bin/python3

"""
    vigenere.py - Vigenere tool, can use statistical analysis to guess keys of varying length for enciphered text

    Options:
        --encrypt - enable encryption mode
        --decrypt - enable decryption mode
        --preserve-spacing - preserve the spacing of the input in the output
        --key - specify the encryption key
        --spacing - specify the output spacing
        --guess - attempt to guess the encryption key by statistical analysis

    Todo:
        - Implement n-gram analysis to improve accuracy of key guesses
        - Perform frequency analysis of deciphered text to improve accuracy of key guesses
    Future:
        - Add support for multiple languages
        - Include standard deviations for each letter frequency
        - Get better numbers for frequency analysis
"""

import argparse
import re
import string
from itertools import cycle

def buildSubStrings(string, seperation): # Build all substrings required to analyse the polyalphabetic cipher
    return [string[i::seperation] for i in range(seperation)]

def frequencyAnalysis(string): # Normalised frequency analysis
    freq = [0] * 26

    for c in string:
        freq[ord(c) - ord('A')] += 1

    total = sum(freq)

    for i in range(0, len(freq)):
        freq[i] /= (float(total) / 100)

    return freq

def initialiseParser():
    parser = argparse.ArgumentParser(description = "Encrypt or decrpyt a string using the Caesar Cipher")

    parser.add_argument("--encrypt", "--enc", "-e", help = "encryption mode (default)", action = "store_true")
    parser.add_argument("--decrypt", "--dec", "-d", help = "decryption mode", action = "store_true")
    parser.add_argument("--preserve-spacing", "--preserve", "-p", help = "use same spacing as the input text", action = "store_true", dest = "preserveSpacing")
    parser.add_argument("--key", "-k", help = "encryption key for vigenere cipher", type = str)
    parser.add_argument("--spacing", "-s", help = "specify the spacing in output", type = int)
    parser.add_argument("--guess", "-g", help = "Attempt to guess the most likely key value", action = "store_true")

    return parser

def scoreCalculator(frequencyAnalysis, shift): # Calculates a weighted score for a given shift value
    englishFrequencies = [  8.167, 1.492, 2.782,
                            4.253, 12.702, 2.228,
                            2.015, 6.094, 6.966,
                            0.153, 0.772, 4.025,
                            2.406, 6.749, 7.507,
                            1.929, 0.095, 5.987,
                            6.327, 9.056, 2.758,
                            0.978, 2.360, 0.150,
                            1.974, 0.074 ]

    score = 0

    for index in range(0, 26):
        shiftIndex = (index + shift) % 26
        score += abs(frequencyAnalysis[index] - englishFrequencies[shiftIndex])

    return score / 26

def shiftCalculator(frequencyAnalysis): # Calculates the most likely shift value for a substring by comparing weighted scores of different shift values
    bestGuess = ''
    bestGuessScore = float('inf')

    for shift in range(1, 27):
        score = scoreCalculator(frequencyAnalysis, shift)

        if score < bestGuessScore:
            bestGuessScore = score
            bestGuess = chr(ord('Z') - shift + 1)

    return bestGuess

def stringPrepare(string, preserveSpacing): # Strip all non alphabetic characters from a string and convert to upper case
    if preserveSpacing == True:
        regex = '[^A-Z\s]'
    else:
        regex = '[^A-Z]'

    return re.compile(regex).sub('', string).upper()

def vigenere(plaintext, key, encrypt):
    alphabet = string.ascii_uppercase
    output = ''
    shift = 1

    if encrypt == False:
        shift = -1

    for x, y in zip(stringPrepare(plaintext, False).upper(), cycle(key.upper())):
        output += alphabet[(alphabet.index(x) + alphabet.index(y) * shift) % 26]

    return output

def main():
    parser = initialiseParser()
    args = parser.parse_args()
    rawText = stringPrepare(str.upper(input('')), True)
    strippedText = stringPrepare(rawText, False)

    if args.decrypt or args.encrypt:
        if(args.key != None):
            output = vigenere(strippedText, args.key, args.encrypt)
        else:
            print("Error: No key given!")
    elif args.guess:
        maxGuess = 30 if len(strippedText) > 30 else len(strippedText)
        keyList = list()

        for guess in range(2, maxGuess):
            substringList = buildSubStrings(strippedText, guess)
            frequencyAnalysisList = list()
            key = ''

            for subString in substringList:
                frequencyAnalysisList.append(frequencyAnalysis(subString))

            for frequency in frequencyAnalysisList:
                key += shiftCalculator(frequency)

            keyList.append(key)

        bestGuess = ''
        bestGuessScore = float('inf')

        for key in keyList:
            score = scoreCalculator(frequencyAnalysis(str.upper(vigenere(strippedText, key, False))), 0)

            if score < bestGuessScore:
                bestGuessScore = score
                bestGuess = key

        print("Best key guess: %s\nAttepting decryption..." % bestGuess)
        output = vigenere(strippedText, bestGuess, False)

    if args.preserveSpacing:
        for x in range(0, len(rawText)):
            if rawText[x] == ' ':
                output = output[:x] + ' ' + output[x:] # Reinsert the stripped spaces back into the output
    elif args.spacing:
        if args.spacing > 0:
            output = ' '.join([output[i:i + args.spacing] for i in range(0, len(output), args.spacing)])

    print(output)

if __name__ == "__main__":
    main()

caesar.py

#!/usr/bin/python3

"""
    caesar.py - Caesar Cipher tool, can use statistical analysis to guess the shift value of Caesar Ciphered text

    Options:
        --bruteforce - attempt to bruteforce the shift value
        --encrypt - enable encryption mode
        --decrypt - enable decryption mode
        --preserve-spacing - preserve the spacing of the input in the output
        --shift - specify the shift value
        --spacing - specify the output spacing
        --guess - attempt to guess the shift value by statistical analysis

    Todo:
        - Implement n-gram analysis to improve accuracy of key guesses
    Future:
        - Add support for multiple languages
        - Include standard deviations for each letter frequency
        - Get better numbers for frequency analysis
"""

import argparse
import re

def caesar(string, shift):
    return "".join(chr(((ord(char) - 65 + shift) % 26) + 65) if not char.isspace() else " " for char in string)

def frequencyAnalysis(string): # Normalised frequency analysis
    freq = [0] * 26

    for c in string:
        if c.isalpha():
            freq[ord(c) - ord('A')] += 1

    total = sum(freq)

    for i in range(0, len(freq)):
        freq[i] /= (float(total) / 100)

    return freq

def initialiseParser():
    parser = argparse.ArgumentParser(description = "Encrypt or decrpyt a string using the Caesar Cipher")

    parser.add_argument("--bruteforce", "--brute", "-b", help = "bruteforce mode", action = "store_true")
    parser.add_argument("--encrypt", "--enc", "-e", help = "encryption mode (default)", action = "store_true")
    parser.add_argument("--decrypt", "--dec", "-d", help = "decryption mode", action = "store_true")
    parser.add_argument("--preserve-spacing", "--preserve", "-p", help = "use same spacing as original string", action = "store_true")
    parser.add_argument("--shift", "-s", help = "value for the Caesar shift", type = int, choices = range(1, 26))
    parser.add_argument("--spacing", "-x", help = "specify the spacing in output", type = int)
    parser.add_argument("--guess", "-g", help = "use statistical analysis to guess the most likely shift value", action = "store_true")

    return parser

def shiftScoreCalculator(frequencyAnalysis, shift): # Calculates a weighted score for a given shift value
    englishFrequencies = [  8.167, 1.492, 2.782,
                            4.253, 12.702, 2.228,
                            2.015, 6.094, 6.966,
                            0.153, 0.772, 4.025,
                            2.406, 6.749, 7.507,
                            1.929, 0.095, 5.987,
                            6.327, 9.056, 2.758,
                            0.978, 2.360, 0.150,
                            1.974, 0.074 ]

    score = 0

    for index in range(0, 26):
        shiftIndex = (index + shift) % 26
        score += abs(frequencyAnalysis[index] - englishFrequencies[shiftIndex])

    return score / 26

def shiftCalculator(frequencyAnalysis): # Calculates the most likely shift value for a substring by comparing weighted scores of different shift values
    bestGuess = ''
    bestGuessVal = float('inf')

    for shift in range(1, 27):
        score = shiftScoreCalculator(frequencyAnalysis, shift)

        if score < bestGuessVal:
            bestGuessVal = score
            bestGuess = 26 - shift

    return bestGuess

def main():
    parser = initialiseParser()
    args = parser.parse_args()

    if args.bruteforce:
        bruteforce = True
    else:
        bruteforce = False
        shift = args.shift

    if args.decrypt:
        shift = -shift

    if args.preserve_spacing: 
        regex = '[^A-Z\s]'
    else:
        regex = '[^A-Z]'

    string = re.compile(regex).sub('', input().upper())

    if args.spacing:
        string = ' '.join([string[i:i + args.spacing] for i in range(0, len(string), args.spacing)])

    if args.guess:
        shift = shiftCalculator(frequencyAnalysis(string))
        print("Best shift value guess: %d (%c)\nAttempting decryption...\n%s" % (shift, chr(shift + ord('A') - 1), caesar(string, -shift)))
        return

    if bruteforce:
        for shift in range(1, 26):
            print("%d:\t%s" %(shift, caesar(string, -shift)))
    else:
        print(caesar(string, shift))

if __name__ == "__main__":
    main()

rainbow-passage.txt

When the sunlight strikes raindrops in the air, they act as a prism and form a rainbow. The rainbow is a division of white light into many beautiful colors. These take the shape of a long round arch, with its path high above, and its two ends apparently beyond the horizon. There is , according to legend, a boiling pot of gold at one end. People look, but no one ever finds it. When a man looks for something beyond his reach, his friends say he is looking for the pot of gold at the end of the rainbow. Throughout the centuries people have explained the rainbow in various ways. Some have accepted it as a miracle without physical explanation. To the Hebrews it was a token that there would be no more universal floods. The Greeks used to imagine that it was a sign from the gods to foretell war or heavy rain. The Norsemen considered the rainbow as a bridge over which the gods passed from earth to their home in the sky. Others have tried to explain the phenomenon physically. Aristotle thought that the rainbow was caused by reflection of the sun’s rays by the rain. Since then physicists have found that it is not reflection, but refraction by the raindrops which causes the rainbows. Many complicated ideas about the rainbow have been formed. The difference in the rainbow depends considerably upon the size of the drops, and the width of the colored band increases as the size of the drops increases. The actual primary rainbow observed is said to be the effect of super-imposition of a number of bows. If the red of the second bow falls upon the green of the first, the result is to give a bow with an abnormally wide yellow band, since red and green light when mixed form yellow. This is a very common type of bow, one showing mainly red and yellow, with little or no green or blue

Example Vigenere Encryption

./vigenere.py -e -k RAINBOW < rainbow-passage.txt

Output

NHMAUVAJUVYJUDKSBEJYAJRIVORNFPAVOHDVAQEUVAPAKGBGWGRQFNOJUFWENONRIVOPKPYEZNJBXFWQFBREMIAVPBKWWPVUSHZGPGJBPFMIAZPARUBVGIHTOTBSGPYEARUOGVTPRTVWGEWSBZKEGZBVBZRRKUXWPYIBFQOPYHQTIOXFVMNOREKSBJPSJUSICQONVNBYZPAPOVQUVAYOZVACJKHMEFWORCKBSREEGBBMSCVNLNCCECIVTQCPFFOBMRWKOVRFBZGEWCMSHFOSOVHJFOVRFJAIFQAEGEKWPROOIRNTBPYOWOZFPAAKHQAHPAPOVQIWOIEIPIVEJFZVFBZJSILISEJLWBLWJXFWEUVAGOBBGUKCDIGUVAVNLBGHDVRIVOPKNTPEPICYOCGUVATEVGVFEVSXRPDHVHIIFSTGLIVOSZKHMEBWJSOEVOJWIIWHTKWPSABNSDRVMNDQAGTMQJHWJAUVSOYCEEVUVKLTXUZGETATRYDHRNIGJCJKOBUFVASRMJTWPNAANUCGVNBUBHPYEZRXCQCDJROCIFRMHOWRVRANMTHFOLFUVAXRMRLGQJELGPWIRGQAFHDRTQGXOORSQTOTNFMBUFUKUSBBGCNVTMYMKWIOZUFORPRIVOHDVNWETSIVNKBOGEUEZREHDVRIVOPKNAANCFEUGMBWSNNHQPIHDVGWQTDWJSMQGFKDEIEUVPFTPRJFDFMMVOHDVSSLPHDVRAUBJAKRQREHKVXXYBWJKHMCISJFMMAPBLYYAVDOHCYIEJGPFTTRUVKLGPGUVWKTPRSOEEBWJXOOTACFFRXPRMSMSYKIWAPTPYEAHOGNRYAOZHDVRIVOGEECMGISJGHGFJQEJTAUBJAWOCAEHDRTQGJGJFTZRGZATTQBOPQKRMSSOYKIWACMPYEZNJBZIOXFXVETHKNVGAJTPRSOEEBWJTAWEYKBNDHZCIGFREUEIFBPKLTBUFFWZNJBXVWMEJRFBBFRUREHDVDQSGSNVNKRJBPYEZNJBXFWLRQSJUSKBOGEUEZNCZULPWAUVAJIHRPTPYELEPDORNLGISSZDBUPTPYEKBMCNVDJNOREECZRBGAJAAGISOZZMBGHDVDZBQGEECZRBGAJTPRBQPLATCSWIRRGEBWJSOEBCGAIVMQJGORILGPPAKHMRGTATTWSTILVRQZQCOZTQBOCBRNCZCSNFFJBXGEWTPRSSZFFBUFGATOVQCCSWATYTILFNBUFUNVEVBGHDVFQETHPYEZRTIHKIAGPUEMEIOPKSZTPNOOXEOZZBZHPWQQFMACLWJCOJUSQADSNVDIAEUNVEVYJUDKWPROAEOELSPFIPETYPKPYIAVTORVRGPPAIFNBLQSKWBWJPBAJHWJJBCDAQAMMNVDIAEMACLWJXWPYLQGUZAFRVBHFAVNWECZQV

Example Vigenere Cracking

./vigenere -g < ciphertext.txt

Output

Best key guess: RAINBOW Attepting decryption... WHENTHESUNLIGHTSTRIKESRAINDROPSINTHEAIRTHEYACTASAPRISMANDFORMARAINBOWTHERAINBOWISADIVISIONOFWHITELIGHTINTOMANYBEAUTIFULCOLORSTHESETAKETHESHAPEOFALONGROUNDARCHWITHITSPATHHIGHABOVEANDITSTWOENDSAPPARENTLYBEYONDTHEHORIZONTHEREISACCORDINGTOLEGENDABOILINGPOTOFGOLDATONEENDPEOPLELOOKBUTNOONEEVERFINDSITWHENAMANLOOKSFORSOMETHINGBEYONDHISREACHHISFRIENDSSAYHEISLOOKINGFORTHEPOTOFGOLDATTHEENDOFTHERAINBOWTHROUGHOUTTHECENTURIESPEOPLEHAVEEXPLAINEDTHERAINBOWINVARIOUSWAYSSOMEHAVEACCEPTEDITASAMIRACLEWITHOUTPHYSICALEXPLANATIONTOTHEHEBREWSITWASATOKENTHATTHEREWOULDBENOMOREUNIVERSALFLOODSTHEGREEKSUSEDTOIMAGINETHATITWASASIGNFROMTHEGODSTOFORETELLWARORHEAVYRAINTHENORSEMENCONSIDEREDTHERAINBOWASABRIDGEOVERWHICHTHEGODSPASSEDFROMEARTHTOTHEIRHOMEINTHESKYOTHERSHAVETRIEDTOEXPLAINTHEPHENOMENONPHYSICALLYARISTOTLETHOUGHTTHATTHERAINBOWWASCAUSEDBYREFLECTIONOFTHESUNSRAYSBYTHERAINSINCETHENPHYSICISTSHAVEFOUNDTHATITISNOTREFLECTIONBUTREFRACTIONBYTHERAINDROPSWHICHCAUSESTHERAINBOWSMANYCOMPLICATEDIDEASABOUTTHERAINBOWHAVEBEENFORMEDTHEDIFFERENCEINTHERAINBOWDEPENDSCONSIDERABLYUPONTHESIZEOFTHEDROPSANDTHEWIDTHOFTHECOLOREDBANDINCREASESASTHESIZEOFTHEDROPSINCREASESTHEACTUALPRIMARYRAINBOWOBSERVEDISSAIDTOBETHEEFFECTOFSUPERIMPOSITIONOFANUMBEROFBOWSIFTHEREDOFTHESECONDBOWFALLSUPONTHEGREENOFTHEFIRSTTHERESULTISTOGIVEABOWWITHANABNORMALLYWIDEYELLOWBANDSINCEREDANDGREENLIGHTWHENMIXEDFORMYELLOWTHISISAVERYCOMMONTYPEOFBOWONESHOWINGMAINLYREDANDYELLOWWITHLITTLEORNOGREENORBLUE

\$\endgroup\$
  • 1
    \$\begingroup\$ Off topic: have you heard of CryptoPals? If not, I encourage you to Google it \$\endgroup\$ – enedil Mar 9 at 1:43
  • \$\begingroup\$ @enedil No I haven't, I'll check it out, thanks \$\endgroup\$ – psychedelic_alex Mar 9 at 6:39
2
\$\begingroup\$

The first thing which strikes me is that the Caesar code is far too long. It's just a special case of Vigenère with a key that's one character long: I would expect that in caesar.py you can from vigenere import * and then just write a main method.


The second thing which strikes me is that it's good work for a newbie. There's a good docstring at the top; there's a __name__ == "__main__" check.


def buildSubStrings(string, seperation): # Build all substrings required to analyse the polyalphabetic cipher
    return [string[i::seperation] for i in range(seperation)]

Minor point: it's separation with two 'a's.


def frequencyAnalysis(string): # Normalised frequency analysis
    freq = [0] * 26

Magic number. For the time being I'd pull it out as a top-level constant. When you get round to handling other languages you'll need to consider passing it around, possibly implicitly (as the length of an alphabet object).

    for c in string:
        freq[ord(c) - ord('A')] += 1

There's a special class for that: Counter.

    total = sum(freq)

    for i in range(0, len(freq)):
        freq[i] /= (float(total) / 100)

    return freq

You shouldn't need the explicit coercion to float: float division will do that for you. Python 3 has a different operator (//) for integer division. Also, it's probably more Pythonic to use a comprehension:

    scale = sum(freq) / 100
    return [f / scale for f in freq]

def initialiseParser():
    parser = argparse.ArgumentParser(description = "Encrypt or decrpyt a string using the Caesar Cipher")

Typo in decrypt. Also, this is quoted from the Vigenère code, so looks like a copy-pasta error.


def scoreCalculator(frequencyAnalysis, shift): # Calculates a weighted score for a given shift value
    englishFrequencies = [  8.167, 1.492, 2.782,
                            4.253, 12.702, 2.228,
                            2.015, 6.094, 6.966,
                            0.153, 0.772, 4.025,
                            2.406, 6.749, 7.507,
                            1.929, 0.095, 5.987,
                            6.327, 9.056, 2.758,
                            0.978, 2.360, 0.150,
                            1.974, 0.074 ]

I'd like to see a comment giving the source for these frequencies.

    score = 0

    for index in range(0, 26):
        shiftIndex = (index + shift) % 26
        score += abs(frequencyAnalysis[index] - englishFrequencies[shiftIndex])

    return score / 26

See previous notes on the magic number and on using comprehensions.

Is the normalisation necessary? Surely you'll just be comparing scores against each other?


def shiftCalculator(frequencyAnalysis): # Calculates the most likely shift value for a substring by comparing weighted scores of different shift values
    bestGuess = ''
    bestGuessScore = float('inf')

    for shift in range(1, 27):
        score = scoreCalculator(frequencyAnalysis, shift)

        if score < bestGuessScore:
            bestGuessScore = score
            bestGuess = chr(ord('Z') - shift + 1)

    return bestGuess

There's a builtin max and tuples have implicit comparison, so this can be something like

    bestShift = max((scoreCalculator(frequencyAnalysis, shift), shift) for shift in range(1, 27))
    return chr(ord('Z') - bestShift[1] + 1)

    elif args.guess:
        maxGuess = 30 if len(strippedText) > 30 else len(strippedText)

What's the point of guessing len(strippedText)? I haven't seen anything which takes into account bigram frequencies, so I would think that the most plausible guess would be the key which decrypts the plaintext to EEE...EEE.


I've refactored the next section a bit to understand what it's doing:

        keyList = [
            ''.join(shiftCalculator(frequencyAnalysis(subString))
                for subString in buildSubStrings(strippedText, guess))
            for guess in range(2, maxGuess)
        ]

Given the granularity of a lot of the functions, I'm slightly surprised you didn't factor out a guessKey(text, guess).

        bestGuess = ''
        bestGuessScore = float('inf')

        for key in keyList:
            score = scoreCalculator(frequencyAnalysis(str.upper(vigenere(strippedText, key, False))), 0)

Is the str.upper necessary? If so, why not apply it to strippedText earlier and consider in which other functions it becomes unnecessary?


    if args.preserveSpacing:
        for x in range(0, len(rawText)):
            if rawText[x] == ' ':

The regex used \s, which catches a lot more than just ' ', so that looks like a bug to me.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot, this was really helpful! There was one part that I wasn't sure about, namely your comment on how I calculate maxGuess. I did it that way to ensure that the program didn't try and guess keys that were longer than the input text, and to limit how long a key could be for performance reasons. Is there a better way of achieving this? Am I missing something? \$\endgroup\$ – psychedelic_alex Mar 10 at 10:39
  • \$\begingroup\$ I think you've understood the opposite of what I intended to say. Certainly there's no point considering key lengths longer than the ciphertext, but my point was that there's not much point considering key lengths longer than, perhaps, a third of the length of the ciphertext. \$\endgroup\$ – Peter Taylor Mar 10 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.