Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a list of inputs and outputs of what I believe is encoded with a matrix (similar to this method). I was wondering if its possible to reproduce the matrix used to transform the inputs into the outputs.

Example Data:

       in -> out
    62403 -> 74222
    62451 -> 74211
    44279 -> 74208

In case your wondering, I'm not trying to do anything illegal.

ps. It's highly possible the dataset I've provided doesn't map at all. It would still be interesting to see the process on a dataset does map.

share|improve this question
    
In your link, the input is a (bunch of) vector(s), and the output is a (bunch of) vector(s). In your example, the input is a single number, and the output is a single number. Doesn't look much like what's in the link. –  Gerry Myerson Jul 23 '12 at 23:57
add comment

2 Answers

This by the way is called the Hill Cipher from way back in 1929 which is very trivial by today's standard. Super easy to break because of its linearity. It is only used for elementary pedagogical purposes nowadays.

Usually we need to know the encryption scheme and then we attempt to figure out the specific key used. So in this case you believe that the hill cipher is being used and you have given us some ciphertext with its known plain text but we only have three pairs and there are still too many possibilities about the specific scheme without any more information about the scheme.

1.First, a number mapping to a number under this scheme doesn't make sense at all. It must be a vector mapping to the same size vector. And it is not the 1x1 case. So I will make an educated guess here that these are probably 5-vectors being mapped to 5-vectors because all of the numbers have 5 digits in them. This then forces the key-matrix to be a 5x5 matrix like this

$$\left[\begin{array} .a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{array}\right] \cdot \left[\begin{array} .6\\ 2\\ 4\\ 0\\ 3 \end{array}\right] = \left[\begin{array} .7\\ 4\\ 2\\ 2\\ 2 \end{array}\right] $$

2.We have no idea which number system the encryption is being done in. Usually with hill cipher (and many many others) in the English language we work mod 26 (or mod 29 because 29 is prime so it makes inversion easier by adding three more punctuation characters). Here it may be that you are working in the real numbers. But I can also interpret it as mod 26 (or mod 29).

3.Assuming that the key was 5x5, we need two more pairs and you only gave us two. The number of known ciphertext and plaintext pairs needed to break a Hill cipher depends on the matrix size which is always a square for invertibility. So for an $n\times n$ key-matrix we need $n$ pairs of vectors with each being of size $n$. Otherwise (depending on the number system) we may have infinite possibilities (like in the real case) or more than one but finitely many possibilities (like in the mod 26 or mod 29 case).

So just for the sake of answering your question I will assume that we are working in the real field and the key was 5x5. We already have three pairs and I will just make up two more pairs, let's say $10000 \rightarrow 11111$ and $11000 \rightarrow 22222$.

So now we have $$\left[\begin{array} .a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{array}\right] \cdot \left[\begin{array} .6\\ 2\\ 4\\ 0\\ 3 \end{array}\right] = \left[\begin{array} .7\\ 4\\ 2\\ 2\\ 2 \end{array}\right] $$

$$\left[\begin{array} .a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{array}\right] \cdot \left[\begin{array} .6\\ 2\\ 4\\ 5\\ 1 \end{array}\right] = \left[\begin{array} .7\\ 4\\ 2\\ 1\\ 1 \end{array}\right] $$

$$\left[\begin{array} .a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{array}\right] \cdot \left[\begin{array} .4\\ 4\\ 2\\ 7\\ 9 \end{array}\right] = \left[\begin{array} .7\\ 4\\ 2\\ 0\\ 8 \end{array}\right] $$

$$\left[\begin{array} .a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{array}\right] \cdot \left[\begin{array} .1\\ 0\\ 0\\ 0\\ 0 \end{array}\right] = \left[\begin{array} .1\\ 1\\ 1\\ 1\\ 1 \end{array}\right] $$

$$\left[\begin{array} .a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{array}\right] \cdot \left[\begin{array} .1\\ 1\\ 0\\ 0\\ 0 \end{array}\right] = \left[\begin{array} .2\\ 2\\ 2\\ 2\\ 2 \end{array}\right] $$

Putting the five together, we get

$$\left[\begin{array} .a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{array}\right] \cdot \left[\begin{array} .6&6&4&1&1\\ 2&2&4&0&1\\ 4&4&2&0&0\\ 0&5&7&0&0\\ 3&1&9&0&0 \end{array}\right] = \left[\begin{array} .7&7&7&1&2\\ 4&4&4&1&2\\ 2&2&2&1&2\\ 2&1&0&1&2\\ 2&1&8&1&2 \end{array}\right] $$

Then you just multiply the inverse of the plaintext matrix on the right on both sides and you have your key. Working in the real field, the inverse and hence the key is

$$\left[\begin{array} .a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{array}\right] = \left[\begin{array} .7&7&7&1&2\\ 4&4&4&1&2\\ 2&2&2&1&2\\ 2&1&0&1&2\\ 2&1&8&1&2 \end{array}\right] \cdot \left[\begin{array} .6&6&4&1&1\\ 2&2&4&0&1\\ 4&4&2&0&0\\ 0&5&7&0&0\\ 3&1&9&0&0 \end{array}\right]^{-1} $$

$$\left[\begin{array} .a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{array}\right] = \frac{1}{206} \left[\begin{array} .7&7&7&1&2\\ 4&4&4&1&2\\ 2&2&2&1&2\\ 2&1&0&1&2\\ 2&1&8&1&2 \end{array}\right] \cdot \left[\begin{array} .0& 0& 38& -34& 18\\ 0& 0& 21& 30& -28\\ 0& 0& -15& 8& 20\\ 206& -206& -236& 16& 40\\ 0& 206& -58& -24& -60 \end{array}\right] $$

$$\left[\begin{array} .a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y \end{array}\right] = \frac{1}{206} \left[\begin{array} .206& 206& -44& -4& -10&\\ 206& 206& -176& -16& -40&\\ 206& 206& -264& -24& -60&\\ 206& 206& -255& -70& -72&\\ 206& 206& -375& -6& 88& \end{array}\right]. $$

In a finite number system mod 26 or mod 29, the method is EXACTLY the same just that the computation like matrix/vector multiplications and then the matrix inverse will be different. Side note, in this case the system is breakable in all three cases; the real one (like I showed), mod 26, and mod 29 because the determinant of the plaintext matrix (which we are inverting) is 206 which is nonzero in all three systems.

And no we never assumed you were trying to do something illegal :-) because this method has absolutely zero security in the real world. No one actually uses the Hill cipher for anything useful/valuable. Are you trying to read your sister's diary?

share|improve this answer
add comment

if the solution matrix is

a b c
d e f
g h i

and we have initial elements 1i, 2i, 3i, 4i...
and resultant elements 1f, 2f, 3f, 4f...

then we know that

1f= 1i*a + 2i*b + 3i*c
4f= 4i*a + 5i*b + 6i*c
7f= 7i*a + 8i*b + 9i*c

gives us three equations and three unknowns which you can solve, which gives you the first row of the encryption (or resolution) matrix depending on which is what.

similarly, for the second row

2f= 1i*d + 2i*e + 3i*f
5f= 4i*d + 5i*e + 6i*f
8f= 7i*d + 8i*e + 9i*f

and row 3

3f= 1i*g + 2i*h + 3i*i
6f= 4i*g + 5i*h + 6i*i
9f= 7i*g + 8i*h + 9i*i

so basically you can crack a 3x3 matrix by intercepting 9 data pairs(15 to be sure)... not muy secure.

obviously you have to know how big the matrix is, or whether it's a matrix at all. best way to find out is through social engineering, such as using a reliable power supply, jumper cables and duct tape. maybe water.

what you could do is solve for multiple matrices. starting with 2x2, going up as high as you can (if you're convinced it's a matrix encryption.) for a 2x2 you'll need 4 data points, for 4x4 you'l need 16, 5x5 25, etc.

it's pretty easy to crack that since basically your smartphone has the processing power of a 1990's supercomputer. these are operations your GPU would love to do.

oh yeah before I forget, you might need to calculate the same matrix multiple time, if you don't know where the matrix starts. notice that for 3x3 you always have bundles (vectors) of size three. if you have data points a,b,c,d,e,f, [a b c] may not be a valid vector, but [b c d] might, so you might need to offset your series back and forth by a point or what and retry. fringepoints will then sadly be uncomputable.

the way to check if you have the right matrix is if you do try to figure the matrix with different data points in the same series. if you get the same matrix twice from two different sets of data you have a certain reason to believe that you've found the key. you can then (or even before) run your initial data points through your matrix in applicable sets of vectors (3x3, use sets of 3 vectors) and see if what you get matches what you got.

well then you can just take the inverse of your encryption or decryption matrix and get the encryption or decryption matrix, depending on how you went and approached this.

so yah happy cracking crappy cryptions lol.

cheers dude.

share|improve this answer
    
Your resultant elements each depend on three initial elements. OP's example data give resultant elements each depending on just one initial element. So how does your answer apply to OP's example data? –  Gerry Myerson Jul 24 '12 at 13:09
    
i don't see the problem. the output depends on the local input and the surrounding inputs. –  user35945 Jul 24 '12 at 13:31
    
Maybe so, but that's not how OP presents it. OP writes the output 74222 depends on the input 62403; OP doesn't write the output 74222 depends on the input 62403 and surrounding inputs. –  Gerry Myerson Jul 24 '12 at 23:55
    
[62403 62451 44279] -> [74222 74211 74208] :: also, i assumed that 'sample data' is a subset of the set of all data points, and that op has more of the same series. did I assume wrongly? –  user35945 Jul 25 '12 at 2:39
2  
I think it's an underspecified question, and I wish OP would come back here and dispel the confusion. Then I would have some solid grounds on which to evaluate your answer. –  Gerry Myerson Jul 25 '12 at 6:36
show 1 more 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.