Home › Forums › Student Help Forum › How do I ...? with Maple (Student)

maple

Posted on 2008-10-22 19:32 By me85 (6)
Categories:

The text below was encrypted with a substitution cipher. Only the letters (both
upper-case and lower-case) were substituted, leaving punctuation and spaces alone.
Can any on help me to figure out what the original message was using maple procedures.
“wA’r aBeD WUeK AP XNaB NM U rALKNP USUeAJBMA NM zUM
nPrB ZNAW U JUM ZWP’r XBUeMNMO AP SXUD AWB aNPXNM.”
yWUA’r ZWUArWBAPXK AWB SPXNCB ZWBMrWBWUMKBK AWBJ
AWB BJSAD eBaPXaBe.
lNCWUeK heULANOUM, “yWB zCUeXUAAN yNXA”

I have no clue...

Thanks a lot

‹ expand fourier in maple trying to find a minimum of this expression..but ›
acer's picture

ok

Comment on 2008-10-23 01:17 from acer (Maple Rating 4 1410)

Start off with a character mapping that does nothing, and which maps abc...XYZ to itself. Make small changes to this, to get going with it. A single letter following an apostrophe is very likely an "s". The sequences "rWB" and "AWB" are likely "she" and "the", but you have to guess which. Single letter words are likely "a" or "I". Words of just two letters are likely "on", "in", "to", "of", "is", "be" or "at". If you're lucky then some of these easier short word guesses can be considered together. Just keep refining the mapping with guesses, and back out any guess that undoes something you're already confident about. Eventually you can guess whole words and thus deduce the remaining letters.

S := "wA'r aBeD WUeK AP XNaB NM U rALK\
NP USUeAJBMA NM zUM nPrB ZNAW U JUM ZW\
P'r XBUeMNMO AP SXUD AWB aNPXNM. yWUA'\
r ZWUA rWB APXK AWB SPXNCB ZWBM rWB WU\
MKBK AWBJ AWB BJSAD eBaPXaBe. lNCWUeK heULANOUM, yWB zCUeXUAAN yNXA";
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyz","abcdefghijklmnopqrstuvwxyz",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzA","abcdefghijklmnopqsstuvIxyzt",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAU","abcdefghijklmnopqsstuvIxyzta",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUP","abcdefghijklmnopqsstuvIxyztao",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMN","abcdefghijklmnopqsstuvIxyztaono",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMN","abcdefghijklmnopqsstuvIxyztaono",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMN","hbcdefghijklmeopqsstuvIxytttoeb",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMN","hbcdefghijklmeopqsstuvIxytthoeb",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWB","hbcdefghijklmeopqsstuvIxytthoebot",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWB","hbcdefghijklmeopqsstuvIxytthoebhe",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWB","hbcdefghijklmeopqsstuvIxstthoebhe",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWB","tbcdefghijklmeopqsstuvIxstthoebhe",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJ","tbcdefghijklmeopqsstuvIxstthoebhem",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJ","tbcdefghijklmeopqsstuvIxsttaoebhem",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJ","tbcdefghijklmeopqsstuvIxtttaoebhem",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJ","tbcdnfghijklmeopqsstuvIxtttaoebhem",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJ","tbcdefghijklmeopqsstuvIxtttaonohem",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJB","tbcdrfghijklmeopqsstuvIxtttaonoheme",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZ","tbcdrfghijklmeopqsstuvIxtttaonohemeb",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZK","tbcdrfghijklmeopqsstuvIxtttaonohemebd",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKX","tbcdrfghijklmeopqsstuvIxtttaonohemebde",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXD","vbcdrfghijklmeopqsstuvIxtttaonohemebdey",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXD","vbcdmfghijklmeopqsstuvIxtttaonohemebdey",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXD","vbcdrfghijklmeopqsstuvIxtttaonohemebdey",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXD","vbcdmfghijklmeopqsstuvIxbttaonohemebdey",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXD","vbcdmfghijklmeopqssbuvIxtttaonohemebdey",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXD","vbcdrfghijklmeopqssbuvIxtttaonohemebdey",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXD","vbcdrfghijklmeopqIsbuvIxtttaonohemebdey",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDS","vbcdrfghijklmeopqssbuvIxtttaonohemebdeyp",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDS","vbcdrfghijklmeopqssbuvIxtttaenohemebdeyp",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDS","vbcdofghijklmeopqssbuvIxtttaenohemebdeyp",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDS","vbcdrfghijklmeopqssbuvIxtttaenohemebdeyp",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXD","vbcdrfghijklmeopqssbuvIxtttaonohemebdey",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDS","vbcdrfghijklmeopqssbuvIxtttaonohemebdeyp",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDS","vbcdrfghijklmeopqssbuvIxtttaonohemebdlyp",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSO","vbcdrfghijklmeipqssbuvIxtttaonohemebdlypg",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSO","vbcdrfghijklmeopqssbuvIxtttaonghemebdlypg",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSO","vbcdrfghijklmeopqssbuvIxtttaonihemebdlypg",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSOL","vbcdrfghijklmeopqssbuvIxtttaonihemebdlypgu",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSOL","vbcdrfghijklmeopqsswuvIxtttaonihemebdlypgu",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSOL","vbcdrfghijklmeopqssbuvIxtttaonihemebdlypgu",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSOL","vbcdrfghijklmeopqssbuvIxtttaonihemewdlypgu",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSOL","vbcdrfghijklmeopqssbuvIxtntaonihemewdlypgu",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSOL","vbcdrfghijklmeopqssbuvIxtntaonihemewdlypgu",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSOL","vbcdrfghijklmeopqssbuvIxtstaonihemewdlypgu",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSOL","vbcdrfghijklmJopqssbuvIxtStaonihemewdlypgu",S);
StringTools:-CharacterMap("abcdefghijklmnopqrstuvwxyzAUPMNWBJBZKXDSOLC","vbcdrfghijklmJopqssbuvIxtStaonihemewdlypguc",S);

And finally, if you get bored, feed key bits of what you have into google (it's clearly a  quotation), 

S := "wA'r aBeD WUeK AP XNaB NM U rALK\
NP USUeAJBMA NM zUM nPrB ZNAW U JUM ZW\
P'r XBUeMNMO AP SXUD AWB aNPXNM. yWUA'\
r ZWUA rWB APXK AWB SPXNCB ZWBM rWB WU\
MKBK AWBJ AWB BJSAD eBaPXaBe. lNCWUeK heULANOUM, yWB zCUeXUAAN yNXA";

StringTools:-CharacterMap("abcdefghijk\
lmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVW\
XYZ","vbcdrfgBijkRmJopqssbuvIxTStecyEFGHImdunigoQRpTaVhlYw",S);

"It's very hard to live in a studio apartment in San Jose with a man who's \
    learning to play the violin. That's what she told the police when she h\
    anded them the empty revolver. Richard Brautigan, The Scarlatti Tilt"

acer

relative frequency

Comment on 2008-10-23 01:31 from Joe Riel (Maple Rating 4 1260)

Standard technique for a substitution cipher is to compare the relative frequencies in the message to that of the target language, English.  You can use StringTools:-CharacterFrequencies to do that.  Here I'll create a string that has the characters sorted in terms of their relative frequency (assume S is assigned the ciper):

with(StringTools):
relorder := cat(map(lhs,sort([CharacterFrequencies(S)], (a,b)->(rhs(a)>rhs(b))))[]);
                  " ABUWNMeXPrKaZSJyDC'zOL."wnlh,"

For English, not including punctuation, the expectation is "etaonisrh..."

For this short a message we don't expect a particularly good match, but, because Acer has already given us the key, we can see that the actual order of the translated characters in the plain text is

         " teahinrlosdvwpmTyc'Sgu."IJRB,"
acer's picture

relative frequencies

Comment on 2008-10-23 02:40 from acer (Maple Rating 4 1410)

I find it interesting that it can be difficult to apply relative frequency analysis alone and gain insight on such short (substitution) enciphered messages.

For this example, generating and apply all permutations of maps of the first handful of usually-most-frequent letters would produce a too large number of candidate "decrypted" messages. The best of those may not even have many actual full valid English words in it, so filtering them by dictionary matching  may also be involved.

For short messages, some combination of deduction, inspired guesswork, and relative frequency analysis might be a good all round approach. I notice that, after guessing the encrypted "r" and "w", the next that I obtained by inspired deduction were "AUPMNWB"  which also happen to comprise quite a bit of the most frequent encrypted letters "ABUWNM".

acer

Can we do this shorter way

Comment on 2008-10-23 10:36 from me85 (6)

Can we do this shorter way for example something like in this problem

t:="Ajfal; B fla;fj l;ajCf!";
aa1:=[seq(a1[i],i=1..length(a1))];
a2:=[seq(a1[i],i=1..length(a1))];
for i from 1 to nops(aa1) do
if (aa1[i]="A") then a2[i]:="a";
else if (aa1[i]="B") then a2[i]:="b";
else if (aa1[i]="C") then a2[i]:="c";
else if (aa1[i]="D") then a2[i]:="d";
else a2[i]:="-";
fi;fi;fi;fi;
od;
newt:=CharacterMap(a1,cat(op(a2)),t);

But then how do I know that letter corresponds to what?

acer's picture

difficult

Comment on 2008-10-23 11:29 from acer (Maple Rating 4 1410)

Suppose you (somehow!) knew what the 10 top frequencies were in the decrypted message. Suppose that you knew that they were "teahinrlos".

> relorder := cat(map(lhs,sort([Characte\
> rFrequencies(S)], (a,b)->(rhs(a)>rhs(b))))[]);
                  relorder := " ABUWNMeXPrKaZSJyDC'zOL.wnlh,"

> CharacterMap(Take(relorder,11),cat(" ","teahinrlos"),S);
"wt's aerD harK to liae in a stLKio aSartJent in zan nose Zith a Jan Zho's \
    learninO to SlaD the aiolin. yhat's Zhat she tolK the SoliCe Zhen she h\
    anKeK theJ the eJStD reaolaer. liCharK hraLtiOan, yhe zCarlatti yilt"

There's still quite a bit to figure out, even there. But the problem is that there's no easy way to figure out the frequencies of letters in the decrypted message. That sequence "teahinrlos" is not the usual sequence that Joe mentioned as usually occurring for long messages. So how could you find it? Even if you focused on just the six most frequent letters, how would you figure out that they were "teahin" rather than "etaoni"? I don't see how frequency analysis (alone) helps solve this problem.

acer

acer's picture

Hamming distance

Comment on 2008-10-24 17:59 from acer (Maple Rating 4 1410)

Ok, it's Friday evening, and time to relax with a little coding. I think that something can be done here using StringTools:-HammingDistance, random permutations of the (usual) most frequent English letters, some fixed-length wordlists, a mix of frequency analysis and a little early deduction (eg, recognition of apostrophe-s and single-letter "a", etc).

acer

consonant-line

Comment on 2008-10-24 18:56 from Joe Riel (Maple Rating 4 1260)

A useful technique for a simple-substitution cipher, particularly those of the difficult puzzle variety (aristocrats), is the "consonant-line" method, which identifies a small group of consonants.  This is described in chapter X (by George Lamb) of Helen Fouche Gaines classic text, Cryptanalysis.  This was the first book that I special-ordered (from a book store); I was 13 at the time. It is now available on Google books.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}