Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am trying to find the plain text for the following cipher text using a frequency analysis

vr pvst yqlp mq nvf

But for the letters above this is really difficult, as if I use the alphabetic substitution technique, where I assume that v corresponds to e as this occurs most in the english alphabet. What about p, this also occurs three times, does this mean it corresponds to e. Same for r,s,t,y,l,m,n,j,f which occur only once. Is there an algorithm which looks at such duplicated frequencies, or do I guess:

v and p corresponds to e q corresponds to t r to f correspond to a

?

even using the bigram method for something like this is difficult as a bigram of pv is found, if p = t and v = h that means p doesn't correspond to t anymore?

Thanks in advance!

share|improve this question
    
Cross-posted on CS.SE (where it got a very good answer). cs.stackexchange.com/q/19007/755 –  D.W. Dec 16 '13 at 1:54
add comment

1 Answer

Yes, if one letter is taken up that means it is no longer usable. Under the assumption that it is a simple substitution cipher. You can easily brute force it, if you can code at all it is very simple to create a small program to do this. Here is a python script I just found using google:

import random
from ngram_score import ngram_score
import re

fitness = ngram_score('quadgrams.txt') # load our quadgram model

# helper function, converts an integer 0-25 into a character
def i2a(i): return 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'[i%26]

# decipher a piece of text using the substitution cipher and a certain key    
def sub_decipher(text,key):
    invkey = [i2a(key.index(i)) for i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ']
    ret = ''      
    for c in text:
        if c.isalpha(): ret += invkey[ord(c.upper())-ord('A')]
        else: ret += c
    return ret

def break_simplesub(ctext,startkey=None):
    ''' perform hill-climbing with a single start. This function may have to be called many times
        to break a substitution cipher. '''
    # make sure ciphertext has all spacing/punc removed and is uppercase
    ctext = re.sub('[^A-Z]','',ctext.upper())
    parentkey,parentscore = startkey or list('ABCDEFGHIJKLMNOPQRSTUVWXYZ'),-99e99
    if not startkey: random.shuffle(parentkey)
    parentscore = fitness.score(sub_decipher(ctext,parentkey))
    count = 0
    while count < 1000:
        a = random.randint(0,25)
        b = random.randint(0,25)
        child = parentkey[:]
        # swap two characters in the child
        child[a],child[b] = child[b],child[a]
        score = fitness.score(sub_decipher(ctext,child))
        # if the child was better, replace the parent with it
        if score > parentscore:
            parentscore, parentkey = score, child[:]
            count = 0 # reset the counter
        count += 1
    return parentscore, parentkey

ctext = 'pmpafxaikkitprdsikcplifhwceigixkirradfeirdgkipgigudkcekiigpwrpucikceiginasikwduearrxiiqepcceindgmieinpwdfprduppcedoikiqiasafmfddfipfgmdafmfdteiki'

print "Substitution Cipher solver, you may have to wait several iterations"
print "for the correct result. Press ctrl+c to exit program."
# keep going until we are killed by the user
i = 0
maxscore = -99e99
while 1:
    i = i+1 # keep track of how many iterations we have done
    score, key = break_simplesub(ctext,list('ABCDEFGHIJKLMNOPQRSTUVWXYZ'))
    if score > maxscore:
        maxscore,maxkey = score,key[:]
        print '\nbest score so far:',maxscore,'on iteration',i
        print '    best key: '+''.join(maxkey)
        print '    plaintext: '+ sub_decipher(ctext,maxkey)

Source: http://practicalcryptography.com/media/cryptanalysis/files/break_simplesub_1.py

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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