Boats Log

November 26, 2005

Another thread

Just to give more room for comments.

Posted by Harry at November 26, 2005 05:20 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.

good luck to all those with mock exams tomorrow. lucky for me, i have another year till then ;)

chidders

Posted by: chidders at November 27, 2005 09:16 PM

Finally, it is done. Just in time for a little revision for my mock exams which start tomorrow(argh!).

Got a bit stuck on the multiple solutions for the simultanious equations, but managed to get through. I did it by spotting some longer words in the middle of the text which happened to be mostly correct and working with them to get a correct key. Also, why have to spend ages working out the matrix inversion when you can just look at the conversion from ciphertext to plaintext thereby obtaining the deciphering key straight away?

[You don't have to, it's just one way to think about it. Harry]

Posted by: Tony at November 27, 2005 07:15 PM

Are there two mistakes in 7B Harry? Towards the end?

But anyway, don't try to be too clever, just do it systematically! I spent a long time looking at modular simulatneous equations, but in the end i didn't need to do it, and i just used excel, so you don't need to be a programming guru to get the answers!!

[Yes. those Soviet radio operators were under stress. Harry]

Posted by: Josh at November 27, 2005 06:57 PM

What do i do after i know the keyword lenght of a vignere cipher?

Posted by: Sam at November 27, 2005 06:57 PM

Umm Harry. I've solved some of the equations to get one of the rows, but I've ended up with 4 possibilities which give the correct value for the three crib letters that I've got.
Is this OK?

[That is great, you have to try those possibilities out to see what makes sense eslewhere. Harry]

Posted by: Clever Code Cracker at November 27, 2005 06:46 PM

The other thing I did was not use the variable letter... I simply got out what I had with the known bits, spaced out with question marks, and then cribbed the rest of it. A lot easier (after a while), and I didn't have to program anything :P

[This is very good advice. Don;t try to be too clever. It really is easier to think in terms of solving a bunch of equations. Harry]

Posted by: Ian at November 27, 2005 05:57 PM

ohhhh... Do we need to know a-level maths to do 7B? Because i haven't got a clue of what people are taking about. furthermore, where do everyone learn to write a program?

Posted by: Jenny at November 27, 2005 05:43 PM

Thanks chidders! - I've just finished a program to find all the possible keyword numbers and have started it off with the unknown crib letter as 'A' - its been going over half an hour - and still hasn't finished!!! - I shall try your way though!!

Posted by: Stephen Harris at November 27, 2005 05:09 PM

I didn't use matrices at all, just simultaneous equations. I think Wikipedia made it sound harder than it actually was, I found:

http://www.math.sunysb.edu/~scott/papers/MSTP/crypto/8Hill_cipher

a bit clearer and more user-friendly.

Posted by: Ian at November 27, 2005 05:04 PM

Sophie, the singular of matrices is matrix and it's basically a grid of numbers. Try looking at http://en.wikipedia.org/wiki/Matrix_(mathematics) (from wikipedia)

Posted by: Ruth at November 27, 2005 05:02 PM

i can now do moduler arithmetic but i do not know what a matrice is.
Please help

Posted by: sophie at November 27, 2005 04:42 PM

Also what do you do if you have x mod 26 times y mod 26. And how do you add them? I may have confused ppl but if u can help gr8! I have all the equations I need - but on the right hand side the answer could be, say 2, 28, 54 etc etc. Could you write this as 2 mod 26? If so then how do you mix with simultaneous equations?

TIm

[If x is congruent to x' and y is congruent to y'then x*y is congruent to x'*y' and x+y is congruent to x'+y'. You can write 2, 28, 54 etc all as 2 mod 26. Hope this helps. Any other advice? Harry]

Posted by: Tim at November 27, 2005 04:39 PM

I don't know if Harry will let this through. But, if you're struggling with the Vignere cipher, take a look at Simon Singh's Black Chamber website. It explains the principle for cracking a Vignere cipher really well ***************

Posted by: Emily at November 27, 2005 04:29 PM

Vicky, assumptions are dangerous! Be careful...

Posted by: Jess at November 27, 2005 04:14 PM

This whole thing would be a lot easier if we had a 9 letter crib and a prime number of letters in the alphabet.

[True. I can't do much about the number of letters in the alphabet, but maybe next year I could give a nine letter crib and set this for Challenge 6B instead. Harry]

Posted by: Ruth at November 27, 2005 03:39 PM

[This is tough to follow unless you have already got a handle on this cipher, but some of you may find it helpful. Harry]

you dont actually need to know about solving modular equations to crack this.

although i roughly knew how, i wasnt sure about the matrices so i made a program working on the equations:

P1 = (c1 * a) + (c2 * b) + (c3 * c)
P2 = (c1 * d) + (c2 * e) + (c3 * f)
P3 = (c1 * g) + (c2 * h) + (c3 * i)

i would then give it two more sets of these equations, and it would brute force it, finding all the possible values of a,b,c,d,e,f,g,h,i

i didnt have to inverse the matrices then, or worry about solving modular equations or inverses.

It would then come up with about 60 possible texts, and give each one a score using 'log-weights'. These are basically scores for each letter on how frequently they should occur in a normal english text. It would give me the solution with the highest score, and that would be the answer.

so all i needed was three triagraphs, which i found using a crib.

i dont know if that made sense to anyone else, but it made sense to me. else i wouldnt of cracked it :)

chidders

Posted by: chidders at November 27, 2005 03:06 PM

Ummmm okay everyone's on about 7B, when my team haven't even got 7A lol...

Anyone have any hints? I'm trying a hand-written method of finding out if it's a Vigenere (making the BIG assumption that the first word is 'Harry', cos it has been the past few ciphers), as we don't get how the index of coincidence exactly helps...

Anyone have any helpful hints?! Would be very much obliged. :)

[Have you looked up Babbage Kasisiki deciphering? Harry]

Posted by: Vicky Bird at November 27, 2005 02:49 PM

I'd been putting off trying to solve 7A because it seems everyone's been saying it is hard, but I did it just now and it took me what? less than a minute...

Posted by: cecil at November 27, 2005 02:45 PM

evry1 is tlking lyk they no 8/9 of teh key, how do they no that, i have 8 letters plaintext, is that the key did harry mean?

[Could be! Harry]

Posted by: Insane (FHS) at November 27, 2005 01:58 PM

Harry, when you said that the first 8 letters of the plaintext are part of the key, did you mean that those letters are part of the key matrix?

[More like a crib. Harry]

Posted by: Jane at November 27, 2005 01:14 PM

I have worked out some possible values for the matrix but when i work out the inverse the fractions are ridiculous. I cant believe thats right. Is it??

[Seriously you shouldn't be thinking in terms of fractions really. If you look back at other posts you'll see for example that you should think of 1/5 as 21 and 1/3 as 9. Hope that helps. Harry]

Posted by: Alex at November 27, 2005 12:16 PM

by the way harry, are you going to give us another clue?

[Yes, from time to time. Harry]

Posted by: charlie at November 27, 2005 10:55 AM

on 7b i only have 1097 characters?

[Did you forget to take out the line endings before decoding the Morse? Harry]

Posted by: F at November 27, 2005 10:32 AM

do we need a keyword for A? if so how are we meant to know it?

[It is a Vigenere. You can find lots about cracking these on the web. Harry]

Posted by: F at November 27, 2005 10:06 AM

Hi Harry.
Sleep and a lot of equations has got me a long way but how do you solve
" x = [4(mod26)]/4"
ie when the denominator can't have an inverse in that mod?

[What you mean is 4x=4 mod 26, and that has at least one solution that I can see (in fact there are two possibilities). Harry]

Posted by: Clever Code Cracker at November 27, 2005 10:05 AM

ahhhh!!!
None of this maths is making any sense to me!?
Where is it explained and do you have to do the maths? I can't write a programme either..

Sophie

[Sophie, you need to know about matrices and modular arithmetic. Then you need to understand how to solve nine equations in nine unknowns to find them all. A computer would help because actually you will have nine equations in ten unknowns and you have to test the 26 possibilities for the tenth unknown. Sorry I can't say more at the moment. Harry]

Posted by: sophie at November 27, 2005 09:39 AM

i'm in y9 so dont understand any of this, i cant program and i think 13 variables is 2 many, but that comment a while ago about inverses should help a bit.
Is there any chance of next year, this board being possible to copy and paste because if u try it now, it selects the whole thing up from where u want (or maybe i just cant type either)
bit off topic but bascially, am i meant to know the key?
i know the first 8 letters o the plaintext, is that the key? (cept with 1 more of course)

[I still hope to integrate a proper forum next year which should make things easier for everyone (except possibly me). That is the key, and as you say it would be better (for you) if you knew the first nine letters, but perhaps that would be too easy! Harry]

Posted by: Insane (FHS) at November 27, 2005 07:51 AM

Harry are the numbers in the matrix whole or can they be fractions because i think i could of worked it out if they are??

[No they are not fractions I am afraid. Though in some cases you can pretend they are. Specifically if ax is congruent to bx mod 26 and x is not even and is not divisible by 13 then you can divide both sides by x to conclude that a is congruent to b. This is like multiplying by 1/x, but can fail if x is divisible by 2 or 13. So provided your fractions have denominators coprime to 26 you might be OK. Did it work? Harry]

Posted by: Alex at November 27, 2005 01:01 AM

Harry, sorry, you said "size of the block" will divide the cipher text, - do you mean the number in each column n or the total number in the matrix, ie n^2??

[n. Harry]

Posted by: Stephen Harris at November 26, 2005 11:40 PM

Harry, would it be "playing fair" at this stage to hint to the people who still don't know what kind of cipher this is? Thus:
Despite the suspicious use of the word "scale", it is not a Beaufort.
Despite the use of "steep", it is not a TEA.

[I planned to say outright what sort of cipher it is tomorrow. Harry]

Posted by: John at November 26, 2005 11:30 PM

Am I right in having * sets of * simultaneous equations, each with * unknowns?

Posted by: Ruth at November 26, 2005 10:26 PM

i made a program where you give it three thingygraphs ;) of cipher text and three thingygraphs of plain text and it will give you the whole solution.

did anyone go further and build a program which cracks the whole thing automatically?

chidders

Posted by: chidders at November 26, 2005 10:23 PM

Thanks harry much clearer now but what is congruence in modulo arithmetic.

PS. I'm doing In maths I've done C1,2&3 and M1 and P1. Should I know all this or will I get to it later?

[It is pretty straightforward, but is not in the A level.

As for conguence. x is congruent to y mod 26 if they have the same remainder when you divide by 26. So 1 is congruent to 27, 53, 79, 102 and so on, 2 is congruent to 28, 54, 80, 103 and so on. IN other words if you count round the face of a clock with 26 divisions two numbers are congruent if and only if they end at the same place on the clock face. Harry]

Posted by: Clever Code Cracker at November 26, 2005 09:34 PM

Umm what does inverse mean for mod. I presume it doesn't mean x^(-1)

[Actually it does in a wierd sort of way. When we write x^(-1) what we mean is "the number such that x^(-1)*x=1. When we are doing the ordinary sort of arithmetic this means 1/x. So the inverse of 2 is 1/2. Of course every number except 0 has an inverse in this sense.

When you are doing modular arithmetic mod 26 we make the same definition that the inverse of x is any integer y such that y*x is congruent to 1 mod 26. So in my examples in the last comment the inverse of 3 is 9 and the inverse of 5 is 21. Working mod 26 every odd number not divisiible by 13 has an inverse, but, just as 0 has no inverse in the ordinary sense, even numbers and numbers divisible by 13 have no inverse mod 26. Does this help? Harry]

Posted by: Clever Code Cracker at November 26, 2005 09:18 PM

I wrote a program to do it... I've actually since been searching the Internet to see if there are any good applets, and I didn't really find any that worked.

Originally my program was taking about an hour to do what I wanted (estimated), luckily I managed to get that down to about 30 seconds, but the point is that I still would have used the program if it took that long, because any progress is worth following. It doesn't really matter how long the program takes (within reason) as long as it works and is faster than you!

Posted by: Ian at November 26, 2005 09:09 PM

Harry, I'm pretty sure I know what the cipher is, but how many numbers are there in each column of the matrix?? - i've read somewhere that for n block of letters it will require an nXn matrices - but that would mean 64! - help!!

[The size of the block will divide the length of the ciphertext. Does that help? Harry]

Posted by: Stephen Harris at November 26, 2005 09:06 PM

Harry. How are we supposed to find solutions for our equations when everything is in modulo 26?

[You have a bunch of equations to solve. You do it by eliminating variables. You need to work out things like:

The inverse of 3 mod 26 is 9 since 3*9=27 which is the same as 1 mod 26.
The inverse of 5 mod 26 is 125 since 5*5=25 is -1 mod 26 so 5*125=(5*5)*(5*5) is congruent to 1 mod 26. (And of course 125 is congruent to 21 mod 26 so the inverse of 5 is also 21 mod 26).

So if you end up with an equation like 5x =17 mod 26 then you solve it by writing 21*5*x=21*17, or x=21*17 mod 26. Hope this helps. Later on I'll say a bit more about this. Harry]

Posted by: Clever Code Cracker at November 26, 2005 09:03 PM

How come my comments arent being shown??

[This one was! Harry]

Posted by: Alex at November 26, 2005 08:06 PM

I need some known plaintext to solve the cipher so any guesses any1? I can guess the first 1 but that gives me 1 letter too short and therefore i cannot solve the equations. Do i hav to guess it? If so there are millions of numbers and i have no idea how to solve that.

[You can use that to almost solve it. You will be left with one entry in the matrix which you don't know, but that doesn't leave many to try out (26 to be precise!) Harry]

Posted by: Alex at November 26, 2005 07:44 PM

This must really annoy you for people to keep asking you this but.... Roughly how many people have submitted successful entries so far?

Cheers, Tim

PS: Tis a tough slope for me! I don't get the mod!

[You'll find out when we publish the Honours Board. Harry]

Posted by: tim at November 26, 2005 07:25 PM

yess!!!
done 7a
am i supposed to have 1097 characters for part B?
or have i gone wrong?

[It is supposed to be 1098. Harry]

Posted by: laura at November 26, 2005 07:06 PM

ok, please, someone, i am totally stuck on 7A. i must be really dumb. or really busy. i feel so left out and slow and behid and annoyed. i lookeed at the wikipedia. i still need help. is it a vigenere again?

Posted by: laura at November 26, 2005 06:45 PM

Do a Google search on the name of the cipher and some useful pages come up. It may take some time though. It is taking me long enough! Patience, comrades, patience... ;-)

Posted by: Jess at November 26, 2005 06:17 PM

Just curious, how many people have cracked part B by hand? And how many people have cracked using a program they have written themselves?

Also, in challenge 8B, does it have to be cracked using a program, because I'm sure I remember somewhere in the rules that the top few competitors will be required to submit their programs, implying that it would need to be cracked using one.

[We will progressively reveal more and more of the key to Challenge 8B, so that by the end you could (in theory) decode it by hand. If you want to crack it early you will need to write a programme. Harry]

Posted by: Ned at November 26, 2005 06:14 PM

What is the leader board 0 showing now? It has changed since Friday afternoon.

[On Friday afternoon there was, very briefly, a development version of the leader board displayed. That may have been cached by some proxy servers in which case you might have seen it after it was taken down. It now shows the current leader board, as at the end of Challenge 6. Harry]

Posted by: Ben Caller at November 26, 2005 05:53 PM

i have found out the cipher (finally) but i cant crakc it, there are 2 many variables. How can i crack this code?
Any ideas much appreciated

Posted by: Insane (FHS) at November 26, 2005 05:41 PM