« Second hint for Challenge 7B | Main | A reader writes ..... »
December 04, 2005
Extended crib
For those of you working on Challenge 7B here is an extended crib I have worked out
The first eighteen characters of the cipher text are
SSODTUQOEBIEFKYJXM
The first eighteen characters of the plaintext are
COMRADESWEAREUNDER
You might even take a guess at the next six characters if you are feeling lucky, Anyway it gives you something more to check your calculations against.
Good luck,
Posted by Harry at December 4, 2005 09:44 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.
hmmm, a random person starts talking to me on msn and i find its a cipher challenge person lol they wouldnt let me pick their brains about challenge 8B :S
chidders
Posted by: chidders at December 6, 2005 10:53 PM
Thanks Chidders, makes sense when you think about it!
Posted by: Stephen Harris at December 6, 2005 10:31 PM
what my program does, for an ADFGVX cipher, is to brute force the keyword length for a transposition. Then it splits up the text into its different sections, and tries matching columns. The pair of columns with the highest ic is the correct one.
i no im rather vague, but at the end of the day i want to beat you :)
chidders
Posted by: chidders at December 6, 2005 07:22 PM
Phew, I was getting worried when people were preparing ADFGVX's and stuff... I mean, 8A was only a Vigenère last year! All I can say is I hope my 8B programs work :P or at least have thought of every possible trick they can throw :D
Still will take a long time to brute force the wiring mazes though :( Hopefully clues will be sufficient to speed it up.
Posted by: Ian at December 6, 2005 07:16 PM
Harry, will 8A be really hard?
[Hope not. Harry]
Posted by: Jess at December 6, 2005 04:29 PM
I've just remembered, you actually get the transpose of the matrix on the right hand side. but it still doesnt work
Posted by: me at December 6, 2005 03:28 PM
Has anyone tried cracking the matrix with an augmented matrix of the equations?
I think it's like this. Is p0 is the first plaintext char, and c0 is the first ciphertext (etc)
Augmented matrix =
p0 p1 p2 | c0 c1 c2
p3 p4 p5 | c3 c4 c5
p6 p7 p8 | c6 c7 c8
then reduce it to row echelon form (make the left side the identity matrix) with gaussian elimination and the right hand side becomes the encryption matrix. Now invert it. (or is it the decryption matrix anyway)
I'm having problems with this method. Maybe it's my code, or am I just barking up the wrong tree harry?
I must be getting something wrong, because I brute forced the 7b key ages ago, and my resulting matrix worked for decryption, but was un-invertible Mod 26;
Posted by: melkorme at December 6, 2005 03:26 PM
Chidders, or anyone for that matter, for an ADFGVX cipher how do you find the transposition part without having any plaintext to test it on?
Posted by: Stephen Harris at December 6, 2005 03:22 PM
noooooooo
it didnt work.....
Posted by: Insane (FHS) at December 5, 2005 11:15 PM
how do you create mod multiplication tables?
[Start out with an ordinary one and then replace each number with its mod 26 equivalent. I used Excel to do this. It has a command MOD(x,n) which takes a number x and replaces it with its mod 26 equivalent. So MOD(51,26) gives 25. Harry]
Posted by: Insane (FHS) at December 5, 2005 10:37 PM
umm ye thanx loads, really gr8, just wonderin, y is it on mine that the 1 in row 7 is in column 16?
[Ouch. Because I'm tired and I made a mistake! Sorry, I should have said 7*15=105=1 mod 26. I corrected the post. Harry]
Posted by: Insane (FHS) at December 5, 2005 10:27 PM
Wow, thanks Harry. I don't suppose you'll take the 'it's nearly Christmas' attitude towards Challenge 8... ;)
[I'm busy making the decorations now! Harry]
Posted by: Jess at December 5, 2005 10:22 PM
how does the table work?
It has 27 rows and 27 columns. The top row has a blank in the first column followed by the numbers 0..25, one in each column.
The first column has a blank in teh top row (yes, the same blank) then the numbers 0..25 one in each row.
To multiply x by y mod 26 look for x in the first column, y in the top row and find where the x row intersects the y column. This gives the answer.
So to find which number you multiply 7 by to get 1 (in other words to work out what 1/7 means mod 26) you look along the row labelled 7 until you find the 1. In this case it is in the column headed 15 telling you that 1/7 is 15 mod 26.
Does that help? Harry]
Posted by: Insane (FHS) at December 5, 2005 10:13 PM
if i have a sort of solution for 1 letter of the matrix like 7a=25 for example, how do i work out a?
or any other where i can't divide like in the previous exaple, divide both by 7 and u get a = wotevr, but that is sum randon load of decimal places etc
[Good question. If 7a=25 mod 26 then, since 15*7 is the same as 1 mod 26 we get
a=1*a=(15*7)*a=15*(7*a) = 15*25 mod 26. It follows that a=11.
This is a lot easier if you have a mod 26 multiplication table. Since it is nearly Christmas here is one I made in Excel, hope you can cut and paste it into Notepad or something and edit into a useable form. (I can't upload the spreadsheet itself tonight). Harry
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2 0 2 4 6 8 10 12 14 16 18 20 22 24 0 2 4 6 8 10 12 14 16 18 20 22 24
3 0 3 6 9 12 15 18 21 24 1 4 7 10 13 16 19 22 25 2 5 8 11 14 17 20 23
4 0 4 8 12 16 20 24 2 6 10 14 18 22 0 4 8 12 16 20 24 2 6 10 14 18 22
5 0 5 10 15 20 25 4 9 14 19 24 3 8 13 18 23 2 7 12 17 22 1 6 11 16 21
6 0 6 12 18 24 4 10 16 22 2 8 14 20 0 6 12 18 24 4 10 16 22 2 8 14 20
7 0 7 14 21 2 9 16 23 4 11 18 25 6 13 20 1 8 15 22 3 10 17 24 5 12 19
8 0 8 16 24 6 14 22 4 12 20 2 10 18 0 8 16 24 6 14 22 4 12 20 2 10 18
9 0 9 18 1 10 19 2 11 20 3 12 21 4 13 22 5 14 23 6 15 24 7 16 25 8 17
10 0 10 20 4 14 24 8 18 2 12 22 6 16 0 10 20 4 14 24 8 18 2 12 22 6 16
11 0 11 22 7 18 3 14 25 10 21 6 17 2 13 24 9 20 5 16 1 12 23 8 19 4 15
12 0 12 24 10 22 8 20 6 18 4 16 2 14 0 12 24 10 22 8 20 6 18 4 16 2 14
13 0 13 0 13 0 13 0 13 0 13 0 13 0 13 0 13 0 13 0 13 0 13 0 13 0 13
14 0 14 2 16 4 18 6 20 8 22 10 24 12 0 14 2 16 4 18 6 20 8 22 10 24 12
15 0 15 4 19 8 23 12 1 16 5 20 9 24 13 2 17 6 21 10 25 14 3 18 7 22 11
16 0 16 6 22 12 2 18 8 24 14 4 20 10 0 16 6 22 12 2 18 8 24 14 4 20 10
17 0 17 8 25 16 7 24 15 6 23 14 5 22 13 4 21 12 3 20 11 2 19 10 1 18 9
18 0 18 10 2 20 12 4 22 14 6 24 16 8 0 18 10 2 20 12 4 22 14 6 24 16 8
19 0 19 12 5 24 17 10 3 22 15 8 1 20 13 6 25 18 11 4 23 16 9 2 21 14 7
20 0 20 14 8 2 22 16 10 4 24 18 12 6 0 20 14 8 2 22 16 10 4 24 18 12 6
21 0 21 16 11 6 1 22 17 12 7 2 23 18 13 8 3 24 19 14 9 4 25 20 15 10 5
22 0 22 18 14 10 6 2 24 20 16 12 8 4 0 22 18 14 10 6 2 24 20 16 12 8 4
23 0 23 20 17 14 11 8 5 2 25 22 19 16 13 10 7 4 1 24 21 18 15 12 9 6 3
24 0 24 22 20 18 16 14 12 10 8 6 4 2 0 24 22 20 18 16 14 12 10 8 6 4 2
25 0 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Posted by: Insane (FHS) at December 5, 2005 09:45 PM
mmm... how can i save it as a CSV file? couldn't find it under "save as..."
[Save it as a text file then rename it as something.csv. Harry]
Posted by: Sam at December 5, 2005 08:46 PM
How does this work?
if i have say
2a+14b+12c what does that equal?
is it the first 3 letters?
Posted by: Insane (FHS) at December 5, 2005 07:58 PM
Oh no, I noticed another problem. I know the matric, but do i need to do inverse matric for 1098 characters?
[No! Harry]
Posted by: Sam at December 5, 2005 05:44 PM
harry, no offence, i already used this plaintext (i guessed and it was correct). and that's how i got my matrix. but you said it was wrong. and i dont know where i went wrong.
a little help, someone?
[No offence taken. I think the point was that your solutions work fine for the first few characters of the plaintext, but stop working after a while. That's because you found a solution to the equations which works for the first few but doesn't satisfy the equations given by the rest. You need to go back and solve them again to find a different solution that works for the crib I have now given you. Harry]
Posted by: laura at December 5, 2005 04:23 PM
thank you cecil. I solved equations at last! But how can i do the whole thing in excel? I got all the numbers in Word, how can i transfer all the numbers into excel with a number in each box? the solution is in front of me but i just donno how to apply it! please help.
[Make a Word document which contains the numbers and ensure that in each row of numbers the entries are separated by commas then save the document as a CSV file (comma separated values). Now import it into Excel as a CSV file. Each line becomes an Excel row. Harry]
Posted by: Sam at December 5, 2005 04:17 PM
Hi -
Though by all means go ahead with trying to solve the equations manually, it took me so long to do (and I got it wrong) that I followed some advice on here and brute-forced them. There aren't that many possibilities if you work three at a time...832 to be exact.
Kati
Posted by: Katriel Cohn-Gordon at December 5, 2005 08:16 AM
I was just thinking about guessing some more of that crib... if you've been following the story, you're more likely to get it..
Posted by: cecil at December 5, 2005 07:44 AM
Sam, have you got at least nine equations? If you use all the now-released crib, you should have eighteen equations (each set of three letters makes three equations). You solve equations with 3 unknowns in the same way as with 2. It may help if you've done this at school, but don't worry if you haven't. There are different ways of solving simultaneous equations: by elimination, substitution and by graphs. Others will probably say there are more but hey. It is not practical really to draw graphs when there are three unknowns unless you want to get out your big box so you can have three axes but this is neither practical nor accurate. Substitution is probably
possible but quite difficult. This leaves elimination. This is basically trying to get the same number of a thing
in two equations. eg. With two equations:
2x + 2y=6
4x + 3y=10
If you double the first equation, you get
4x + 4y=12
If you then take the second equation from the third you get
(4x-4x) + (4y-3y) = (12-10)
which gives you:
y = 2
If you then sunstitute the value of y into one of the top equations, you get x:
2x+2y = 6
2x+4 = 6
2x =2
x =1
The same applies to three unknowns. I'll give you a start with the values of the top row of the decrypt matrix.
I'm using wrong cribs with the wrong values of a,b,c,d etc., so I hope Harry won't mind.
19a+19b+15c = 3 (mod 26)
4a +20b+21c = 18(mod 26)
22a+19b+8c = 20(mod 26)
First one take the third one gives
(19a-22a) + (19b-19b) + (15c-8c) = 3-20 (mod 26)
this eliminates b, giving:
23a + 7c = 9 (mod 26)
If you do another equation like this with "a"s and "c"s, you can solve them like you would a two-unknown
equation.
I would recommend getting some sort of Maths textbook with worked examples or examples from the internet if you don't understand. Also, try and get some practice with two equations which are specifically made to be nice numbers before trying out these ones..
If you don't understand mod 26 arithmatic, give us a shout and I'll be back.
Hope that help ;p
Posted by: cecil at December 5, 2005 07:43 AM
At last. I understand what's going on...I have followed the hints and got i set of equations with 3 unknowns. But what should i do now? How am i going to solve them? I don't understand the other comments on the message board. Can you please help me?
Posted by: Sam at December 4, 2005 10:26 PM