« Your wish is my command ... | Main | Extended crib »
December 02, 2005
Second hint for Challenge 7B
So far (if you have been following the comments, and you should have been) you know it is a Hill cipher. In this case given by a 3 x 3 matrix. That means there are nine numbers a,b,c,d,e,f,g,h,i so that if the first three letters are represented by numbers x,y,z (taken mod 26 so that a is represented by 0, b by 1 and so on) then the first three characters of the cipher text are represented by the numbers
ax+by+cz, dx+ey+fz, gx+hy+iz
where the numbers are again taken mod 26, so for example if ax+by+cz=27 then we regard that as 1, representing b (1 is the remainder when you divide 27 by 26) and if ax+by+cz=59 you regard it as 7 representing h.
Now looking at the ciphertext you see the first three letters are SSO, represented by the numbers 18, 18, 14, so you know that in fact
ax+by+cz=18
dx+ey+fz=18
gx+hy+iz=14
Now looking at previous challenges you can guess that the first three letters of the plain text are COM, so that gives you a guess for x,y,z and gives you
2a+14b+12c=18
2d+14e+12f=18
2g+14h+12i=14
That gets you started. Guessing the next three characters of the plaintext gives you another bit of information, and looking for other cribs (what is the most common triple of letters in english?) helps to give enough data to start cracking the cipher.
Good luck!
Posted by Harry at December 2, 2005 10:21 PM
Comments
If you wish to leave a comment please act responsibly. No personal or innapropriate comments should be made. Concerns about a comment should be emailed directly to us here. Hints about the challenges may be blocked or held back at our discretion. We reserve the right to refuse to publish comments without entering into a discussion about why, and to censor comments as we see fit. Please be patient if it takes a while for your comments to be approved.
Laura
To invert a number, say A, you calculate 1/A. To do this for a matrix the '1' becomes an identity matrix and you need to solve an equation of the form
¦A B C¦ . ¦a b c¦ . ¦1 0 0¦
¦D E F¦ x ¦d e f¦ = ¦0 1 0¦
¦G H I¦ . ¦g h i¦ . ¦0 0 1¦
where one of the left hand matrices is the one you know and the other is the inverse you are seeking. From this matrix equation you can generate a set of equations in the variables you are seeking, eg
Aa + Bd + Cg = 1
Ab + Be + Ch = 0
etc.
Of course you must remember that these are all mod-26 equations, so 1 could be 27, 53, etc. If you can't solve these equations you could resort to the brute force technique that others have mentioned. What they mean by brute force is trial and error, in other words choose a set of values for the unknown variables and see if they work. I wouldn't recommend doing this manually, but you could use Excel.
Hope this helps.
Posted by: Emily at December 4, 2005 10:05 PM
ohh... Are these all a-level maths? I tried my best to understand it.. still.... still...I AM STUCK!!
[This one is. Harry]
Posted by: Sam at December 4, 2005 09:32 PM
thank you everyone, i have the equations for encrypting, i just dont know how to decrypt.
i found out that the de... what ever it's called was 838, dont ask me why.
how do i change the matrix to be inverted?
i've tried so many times!
Posted by: laura at December 4, 2005 07:18 PM
I don't think we know quite yet the way the driving/pins/rotor advance/rings/ function yet do we? I have a cracker-like function and a Rotor class but i don't really have much to start with until after 8A.
Posted by: 3vil at December 4, 2005 06:55 PM
Hi Laura. U still stuck? my only suggestion without (hopefully) repeating what Harry's already told you or risk being asterisked out is to use what you know from previous challenges and get about 50 sheets of paper and juggle around a lot with equations. hope that helps. i had to think for ages before i got it and it was really tough. keep trying. anyway, read what Harry wrote after my I HATE MODULAR 26 comment, because that's what really inspired me. good luck.
Harry, I managed to work out the mistakes. i got 100%. i am sooooooooo happy. thanks for your help.
Posted by: lara at December 4, 2005 06:17 PM
Laura, for negative numbers, just take them off 26 (eg. -3=26-3=23mod26), and why would it be 838?
Posted by: Ruth at December 4, 2005 05:08 PM
i hope harry doesnt give any settings in part A - it will ruin it then because it will simply be a case of whose built a simulator instead of being a case of logical cryptanalysis.
what im hoping for is a crib or something in part A and the settings to be released slowly.
chidders
[I wouldn't bet on it. That would be like saying you are diappointed that I gave part of the deck order for the Solitaire cipher last year. This machine is designed to make ordinary cryptanalysis difficult. Giving some settings just cuts down the possibilities. Anyway who is to say there won't be a sting in the tail? Harry]
Posted by: chidders at December 4, 2005 03:51 PM
i did what you said, harry, but i am still so lost. please, a little help? sorry if i am badgering you all day.
[Sorry I've been busy today. Has anyone else got time to give a hint? Maybe I'll get a chance later. Harry]
Posted by: laura at December 4, 2005 03:08 PM
i thought that was the plugboard, melkrome. Does the fialka have ring settings - ie, do i have to bother?
chidders
Posted by: chidders at December 4, 2005 02:34 PM
to find the inverse, i get the original matrix, then do all those things inside it and end up with some crazy numbers in the negative, and then do i multiply it by 838? or 838*838?
i'm so confused, i've tried everything i can think of.
Posted by: laura at December 4, 2005 02:01 PM
harry, the inverse of the matrix is in decimal places. what should i do?
[Ah. we discussed this somewhere else. To divide by 3 as a Real number you multiply by 1/3. When you are doing modular arithmetic 1/3 isn't allowed. Instead. working mod 26 you use the fact that 9*3=27 which is 1 mod 26 to think of 9 as "1/3 mod 26". Similarly 1/5 is replaced by 125 (since 5*125 =5*5*5*5=25*25 which is the same as -1*-1=1 mod 26. So instead of multiplying by 1/5 you multiply by 125. Hope this helps. Harry]
Posted by: laura at December 4, 2005 11:31 AM
chidders:
the ring setting acts as a sort of shift on the internal rotor wiring of enigma. if the ring setting is on "A" (a "0" for the sake of programming) then the rotor wirings are as normal, but if it's on "B" then whatever the letter A connected to before, the letter B now connects to. or is it Z? I'm not sure, but i tested my enigma simulator against one I downloaded, and a bit of trial and error got me the same results.
I'm just worried that the 'fialka' in challenge 8 will have rotor blocking pins instead of notch-wise rotation.
Posted by: melkorme at December 4, 2005 11:22 AM
Hi Harry. i have done it!!!!!!!!!!!!!!!!!! i have cracked 7b and ITS SO AMAZING!!!!!!!!!!!!!!!! but a few tiny parts of it don't quite make sense. WHY?????
[Maybe you have made a mistake? try submitting and see what your score is. (Did you have the right number of characters? There was a discussion of this early on. You might have got the wrong Morse characters in some odd places if you didn't get rid of the line breaks before decoding.) Harry]
Posted by: lara at December 4, 2005 09:28 AM
harry, how do i find the inverse of the matrix used to encrypt?
[You should think of it as solving equations. There are lots of hints about this now in the comments. Have a good look and see what you can find. Harry]
Posted by: laura at December 4, 2005 09:03 AM
harry,
before i waste all my times, can matrices have double digit numbers in them, eg:
[23 24 25]
and can they have triple digits, eg:
[123 456 789]
etc.???
[Yes, but you should interpret these numbers mod 26. So 26 should be replaced by 0, 27 by 1, 28 by 2 and so on. Harry]
Posted by: laura at December 3, 2005 10:55 PM
Programming: I use Javascript as it integrates very well with HTML and I already know it ;). If you want to crack the Hill Cipher with a program you'll need a few subroutines:
1. Matrix multiplication
2. Equation brute force
3. Letter-number converter
4. Something to join them all together
Remember, if you don't know anything just brute force it :).
Kati
Posted by: Katriel Cohn-Gordon at December 3, 2005 10:50 PM
OMG!!!!!!!!!!!!!!!!
Harry, you are so amazing and so brilliant and so great at giving hints. YOU ARE A GENIUS THANK YOU SO MUCH!!!!!!!!!!!!!!!! i.e. because of your reply to my previous comment, i am now halfway through 7b and it is looking good.
Posted by: lara at December 3, 2005 09:55 PM
OK, I don't know quite what I did there, but I did solve it... and I kind of understand how the cipher works... be prepared to have lots of paper and excel spreadsheets to test the different possibilities lara was talking about and don't be put off if you have to start again several times... just remember that a=0 or you will go wrong...
A multiplication table can help with the modular arithmatic. In excel you might say "=Mod(B5,26)" for example...
Hope that helps...;) good luck to all you stuck people... just keep trawling through those comments and don't give up ... tempting though it may be...
Posted by: cecil at December 3, 2005 09:26 PM
Several answers to the equations... that's why all my decryptions were gobbledygook, I hadn't realised that.
Posted by: Ruth at December 3, 2005 09:09 PM
I HATE MODULAR 26!!!!!!!!!!!!!!!!!!!!!!! it is soooooooooooooooooooo frustrating!!!!!!!!!!!!!! the answer of the equation's there. THERE! and yet i still can't get to it because there is like nothing i'm allowed to divide by!!!!!!!!!!!!!!
anyone else had this problem? if so what did you do about it?
Any tips, Harry?
[Sometimes you can divide, but you can get more than one answer! Suppose you know that
2x=8 mod 26
Then you can divide throughout by 2 to get
x=4 mod 13
Notice that the modulus changes. Mod 26 this just tells you there are two possible solutions to the original equation, given by x= 4 and x=17 mod 26. (hope that makes sense)
So if you are having a problem not being able to divide by two that is why. So what you end up with is not one unique solution, but a family of possible solutions. These you have to test against the ciphertext to see which makes most sense.
Harry]
Posted by: lara at December 3, 2005 08:44 PM
I've made a "simulator", and from there a "cracker" is easy, just a big loop with a bit of maths at the end.
I haven't actually got round to testing it with a ciphertext/plaintext I know is right yet, so Thursday will be interesting!
Posted by: Ian at December 3, 2005 06:56 PM
thnx stephen, i understand now. im now starting my enigma simulator - is fialka much harder? i can only see one difference :S
chidders
Posted by: chidders at December 3, 2005 05:19 PM
how far have other people got? i only started today :S
whos made a simulator?
whos made a cracker?
just wondering,
chidders
Posted by: chidders at December 3, 2005 05:14 PM
The ring setting is the point at which one rotor kicks the next one forward. On the engima this was changable, but hopefully won't be on this cipher - my programme is looking weaker by the minute! Hopefully, they will also tell us which rotor moves first, - i may need to do a lot of changing to it otherwise.
Posted by: Stephen Harris at December 3, 2005 04:41 PM
could you please give clues for challenge 7A and especially da keyword! i am soo stuck
[The keyword? It has length five. Harry]
Posted by: Iz at December 3, 2005 04:33 PM
i have no problem copy and pasting from the grey part of the comments page, cecil :S
trying to practise by making a 2 rotor enigma cracker - not getting very far
Posted by: chidders at December 3, 2005 04:14 PM
I use C, basically i just searched "C programming tutorial" on google, did about 50 tutorials, and by that time you can make programs that are useful, occasionally i'd want to make a program but didn't know how, so I had to learn how (with google). And that's how I learnt C
Posted by: Captain Cool at December 3, 2005 04:13 PM
i recommend using javascript lara, its free and really easy to learn, i self tought myself :)
Posted by: martyn compton at December 3, 2005 04:03 PM
did you plan the crib "comrades" from the beginning? 8 letters, 1 shorter than nine...?
Posted by: cecil at December 3, 2005 03:10 PM
Alternatively, you can use exactly the same approach and derive the decryption matrix directly. Lots of for...next loops give you several hundred possibilities, decrypt the whole cipher text with each one and write the result to a file - one of them should be the plain text :-)
Posted by: Mark at December 3, 2005 01:52 PM
i was wondering whether anyone knows anything about the ring in the enigma. Methinks that is the only part i dont really get.
chidders
Posted by: chidders at December 3, 2005 01:22 PM
Hi, ppl. can anyone recommend any good ways of learning programming? what programmes does everyone use? i am insanely jealous every time someone posts a comment about how their wonderful programmes cracked the ciphers in about 30 seconds. So can anyone please recommend any good programmes and where they learnt it from, then maybe next year... i'll dream of the possibilities!!!!!!!!!!!!!!
Posted by: lara at December 3, 2005 01:09 PM
Wouldn't that give you the encryption matrix, which you then have to inverse, not the decryption matrix?
[Yep! How much help do you want me to give! It does at least make it easy to work out how popular triples like "and" and "the" would be encrypted which can help you get started. With a bit of luck you don't ever need to invert the whole matrix. Harry]
Posted by: Ruth at December 3, 2005 12:51 PM
Mark, why would you want to know the answer? Isn't the process of solving it and the sense of achievement when you have finished the main thing? And the fact you learn lots of interesting things on the way? It wouldn't be any fun if Harry just posted the answers... where's the challenge in being able to copy and paste the answer into the form?
(Actually, it might be a bit of a challenge since you can't seem to copy things from the grey part of the comments page... maybe you would have to type it all out again but then that's just seeing you has the most time and can be bothered to do that...)
Posted by: cecil at December 3, 2005 12:50 PM
Mark, Google "Hill Cipher" and see what it comes up with!
Posted by: Laura at December 3, 2005 11:26 AM
what was all that about Harry????? I still have no idea about how to solve this really annoying cipher! Please can i just have the answer so i can submit it now?
[Sure, the plaintext says "Comrades, W:Najkdfklakjbnavg;oklsnmdv;lkajnsdfgiou" Rats my keyboard seems to be broken. Sorry. Harry]
Posted by: Mark at December 3, 2005 08:54 AM