# Tag Info

5

Well, I went and solved the puzzle using brute force and Maple. I won't spoil the actual answer, but here are some tips that ought to make the process a bit more quicker. Solving the linear system modulo 2 gives you the parity of the second and third letters of the unknown plaintext. Note that all vowels in the English alphabet map to even numbers using ...

4

There are 18 plaintext and ciphertext letters $p_j$ and $c_j$, $0\le j<18$ (with $j<6$ for the "first plaintext"), all of which are known except $p_7..p_{17}$. Let $M=\pmatrix{m_{0,0}&m_{0,1}&m_{0,2}\\m_{1,0}&m_{1,1}&m_{1,2}\\m_{2,0}&m_{2,1}&m_{2,2}}$ be the key matrix (unknown, except that it is invertible). We have 18 linear ...

4

Your reasoning is correct. However, there is still some information to be exploited: as you know already, the matrix used to encrypt (the secret key) need to be invertible in order to allow decryption. Since you basically know (say) the first column and the second column of the secret key from your plaintext/ciphertext, you derive from the invertibility of ...

3

No, because matrix inversion can be done efficiently. Namely, if encryption is multiplication by a matrix $A$, then you can define decryption with $A$ as first computing the inverse of $A$ and then multiplying. An essential property of public-key cryptosystems is that it should not be possible to efficiently derive the (private) decryption key from the (...

3

One possibility for what you might be missing: normally the same key (the same matrix) is re-used to encrypt many messages. So now try counting the total entropy in $M$ length-$N$ messages, and the entropy in a $N\times N$ matrix, and compare what happens when $M$ gets large.... Another possibility you might be missing is the consequences of the fact that ...

3

This can be broken. The exact nature of the attack will depend what modulus you use for the Hill cipher: are you working modulo a prime number, or working modulo 26? Working modulo a prime $p$ A simple attack, with no fancy mathematics needed. One simple attack is to start by requesting the encryption of the 26 messages AAAA, BBBB, CCCC, DDDD, ..., ZZZZ. ...

3

Sure. Assuming that you're using the encoding $A = 0$, $B = 1$, etc., just choose your plaintext messages to be the one-block strings: $$BA \dots A \\ AB \dots A \\ \vdots \\ AA \dots B$$ The encryptions of these strings will then directly give you the columns of your key matrix.

3

Maybe the impossibility of solving the equation system uniquely was meant to strengthen the cipher. :D If everything was done correctly, there'll be multiple solutions. When you have some idea of how the plaintext may look like, it should be easy to determine it uniquely. During the computation you have to divide something by 62 modulo 26, which is (as ...

2

Expand the equation system corresponding to the matrix multiplication: $c_j = \sum_{i=0}^{n-1}k_{i,j}p_i$ In other words, each element of the cipher text corresponds to the sum of the cipher text elements of an OTP encryption of the input plain text. If the matrix is never reused, it should be fairly easy to go from here. You are basically using $n$ one ...

2

One time pad is definitely both easy to do and has perfect secrecy, but key management is a pain and can compromise security. Basically a VigenĂ¨re cipher with a key as long as the the message should be secure, because different keys can create ALL possible messages with equal probabilities. Again, it's a one time pad, so no KPA, CPA, or CCA security. ...

2

Well, I'll assume that we'll use the same mapping between letters and integers both to translate the plaintext into integers (to be matrix multipled), and the integers (after the matrix multiply) back into ciphertext. And, we don't know that mapping, the key matrix $K$, and possibly the value of $n$. If so, the obvious place to start is to attempt to solve ...

2

Since it's a linear cipher, you should be wary about a guessable padding, otherwise if your last block is only one char long, you will reveal almost your whole matrix on this last block. If you're too afraid of mangling the last word, use something like 'Z'+(random chars). But I really would not use any predictable padding with such a cipher.

2

You would need (at least) 3 pairs of vectors in order to determine the 3*3 matrix.

2

Let $k=\left(\begin{array}{cc}k_0 & k_1\\k_2 & k_3\end{array}\right)$ be the key. And I'll assume the transformation $a=0$, $b=1$, and so on. So you know $k\left(\begin{array}{c}0\\1\end{array}\right)=\left(\begin{array}{c}c_0\\c_1\end{array}\right)$ where you know $c_0$ and $c_1$. Thus $c_0=0k_0+1k_1$ and $c_1=0k_2+1k_3$. So that is two equations, ...

1

Indeed. If the matrix is $n$ by $n$, and you have $n$ many known plaintext blocks with corresponding ciphertext, you get $n^2$ linear equations in $n^2$ unknowns (the matrix elements) (modulo the alphabet size), which very often can be solved uniquely.

1

Updated answer The question was changed, so here is my updated answer. This scheme is not secure against known-plaintext attacks. It is no better than an ordinary Hill cipher. If you iterate the recurrence relation you listed, we find that $$x_k = Bx_0 - Cx_{-1}$$ and $$x_{k-1} = Cx_0 - Dx_{-1}$$ where $B,C,D$ are matrices given by $B=f(A)$, $C=g(A)$,...

1

Both representations are essentially equivalent. If $$\begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix} = \begin{bmatrix} k_{11} & k_{12} & k_{13} \\ k_{21} & k_{22} & k_{23} \\ k_{31} & k_{32} & k_{33} \end{bmatrix} \cdot \begin{bmatrix} p_1 \\ p_2 \\ p_3 \end{bmatrix},$$ then, equivalently  \begin{bmatrix} p_1 & p_2 & ...

1

You don't. You just decrypt it. I can't think of a language that uses more than 36 letters apart from the Chinese family but then again I'm not a linguist. Decrypt to a reasonable $n$ and then use the character frequencies to infer the language (and hence the modulo). Some trial and error may be required untill you get it right but for values of $n$ less ...

1

Linearizing should work fine. You'll have to make a minor adjustment to deal with the fact that we are working modulo 26, but either of the following two simple tweaks should work fine: You could use generalized Gaussian elimination, generalized to work over $\mathbb{Z}/26\mathbb{Z}$ (standard Gaussian elimination assumes we are working over a field, but ...

Only top voted, non community-wiki answers of a minimum length are eligible