# Tag Info

13

The Hill cipher is vulnerable to known-plaintext attack. Once the attacker gets $n$ plaintext/ciphertext pair it can break the cipher by solving a system of linear equations. Consider AES, it is not proved but considered secure against known-plaintext attack, see this question for details. And, also, key size itself doesn't represent the security. High key ...

7

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 (...

4

Actually it seems to me that you are using the wrong basis and got the key for the other way around: Suppose you have the plain text $x_1 = \pmatrix{5\\17}$ and $x_2= \pmatrix{8\\3 \\}$ and the corresponding ciphertexts $y_1=\pmatrix{15 \\16}$ and $y_2=\pmatrix{2\\5}$ and please note how I represent those as vectors and not line matrices, then everything ...

4

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 ...

4

The project Cryptool does some if not all of what you want. I have not used it extensively, but it seems quite well documented. Below from the webpage: CrypTool 1 (CT1) was the first version of CrypTool. It was released in 1998 and allows to experiment with different cryptographic algorithms. CT1 runs under Windows and has two successors: CT2 and JCT. ...

3

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

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

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, ...

2

In the Hill cipher, like in any symmetric cipher, it is assumed that both parties have the same secret key already. Securely exchanging a key is not part of the symmetric algorithm, neither is it its job. That a separate protocol that needs to be done beforehand.

2

These modular equations are not uniquely solvable: $$\begin{bmatrix}7&2\\ 10& 20\end{bmatrix}, \begin{bmatrix}7&2\\ 23& 7\end{bmatrix}, \begin{bmatrix}20&15\\ 10& 20\end{bmatrix}, \begin{bmatrix}20&15\\ 23& 7\end{bmatrix}$$ are all the $2 \times 2$ matrices over $\mathbb{Z}_{26}$ would transform 'monday' to IKTIWM, the ...

1

Two independent ideas: In the Hill cipher, elements of matrices are in the ring of integers modulo the number of characters in the alphabet used, usually $n=26$. Therefore, as long as the denominator of a fraction is coprime with $n$ (that is, for $n=26$, if the denominator is divisible neither by $2$ not by $13$), that fraction reduces to an integer modulo ...

1

The other answer about CrypTool led me after some links to the freeware CryptoCrack, which seems to be a great tool. Here is how to use it on a simple example (taken from the documentation): Paste LZXLDCRX FEVLZK XVJJSRCI LGZ XDCLRCZCLK BRIJVLZ DOZJ LGZ ZVJLG’K KNJMVXZ V MZP RCXGZK FZJ SZVJ, VWDNL LGZ KVBZ KFZZY LGVL V MRCIZJCVRE IJDPK. in the Cipher text ...

1

Yes, you can convert the Hill Cipher into almost any mode of operation. For simplicity, assume that $M$ represent the key matrix and $P$ represent the plaintext vector and $C$ is the corresponding ciphertext vector with $C = M\cdot P \pmod{26}$. For simplicity, we omit $\bmod 26$ for the rest. ECB mode: we can assume that Hill cipher is already in ECB mode. ...

1

More standard is that we multiply a column with a plain text vector to get the cipher text vector so the known plain text equation (the first two pairs) yield $$KP=C = K\begin{bmatrix}5 & 8\\17 & 3\end{bmatrix} = \begin{bmatrix}15 & 2\\16 & 5\end{bmatrix}$$ so I get $P=\begin{bmatrix}5 & 8\\17 & 3\end{bmatrix}$ which is invertible as ...

1

"KEYWORD" is a weird format for a Hill cipher, aren't you confused with the Playfair cipher? There you work with a 5x5 matrix where I and J are often conflated into I (as 26 is one too big) and the key-square is filled with a key word. This is what you seem to be describing. In the Hill cipher, the key is a 2x2 matrix over some $\mathbb{Z}_n$, often with $... 1 It's indeed standard to add pre-agreed padding characters at the end to make the plain text a multiple of$n$when we use an$n \times n$encryption matrix. So your encoded plain text could be $$\begin{bmatrix} \operatorname{enc}(A)\\ \operatorname{enc}(T) \\ \operatorname{enc}(T) \end{bmatrix} \begin{bmatrix} \operatorname{enc}(A)\\ \operatorname{enc}(C) ... 1 To make the plaintext matrices equal, you could use padding with a null character, such as using "X". For example with "ATTACKS", you would get the following vectors:$$ \begin{bmatrix}A\\T\\T\end{bmatrix}\ \begin{bmatrix}A\\C\\K\end{bmatrix}\ \begin{bmatrix}S\\X\\X\end{bmatrix}\ $$1 Assuming that 2\times2 matrix is used, and the encryption starts from the first letter of the plaintext, the key can be found by just calculating the "encryption" with size of 4 plain- and cryptotext block. For example, for CONV \rightarrow SQZH, it would go as follows:$$\begin{pmatrix} 2 & 14 \\ 13 & 21 \end{pmatrix}\begin{pmatrix} a &... 1 The key is 4 long, so should be a$2 \times 2$matrix. In members of$\mathbb{Z}_{26}$CFDG becomes$2, 5, 3, 6$in the usual A becomes$0$, Z becomes 25 encoding. After some experimenting I found that we make this into the encryption matrix $$K = \begin{bmatrix} 2 & 5\\ 3 & 6 \end{bmatrix}$$ where encrypting is done by multiplying a row of ... 1 The key is 4 characters long, therefore it must be in a 2 × 2 matrix. The numbers in this matrix must be the inverse of the encryption key matrix, and there are various methods to work this out (see this link). Once the matrix inversion has been calculated, you multiple it through each part of the cipher text in their respective 2 × 1 matrices 1 This is a standard problem in modern cryptography (eg for CBC-mode). The standard solution is to use Padding or some other agreed-upon mechanism to encode variable-length messages as a multiple of the blocksize. The most common padding is PKCS#7 padding: If one byte is left, append 0x01, if two are left append 0x02 0x02 and so on. Note that this requires ... 1 I suppose (as you use a length$4$crib) that your encryption matrix$C$is of the form $$\begin{bmatrix} k_{11} & k_{12}\\ k_{21} & k_{22}\\ \end{bmatrix}$$ and so assuming word$(w_1, w_2, w_3, w_4)$at a certain position$m$gives two systems of equations $$\begin{bmatrix} k_{11} & k_{12}\\ k_{21} & k_{22}\\ \end{bmatrix} \begin{bmatrix} ... 1 Over any (commutative unitary) ring R, the inverse of$$E=\begin{bmatrix} a&b\\c&d\end{bmatrix}, a,b,c,d \in R$$(if it exists), can be found by first computing the determinant f:=ad-bc. The inverse exists iff D is an invertible element in R, so iff \exists f' \in R with ff'=1. Then$$E^{-1} = \begin{bmatrix} df'&-bf'\\ -cf'& af'... 1 I think the adjugate matrix is the transpose of the cofactor matrix. (Btw, I do not think this is a crypto question.) 1 In general case, let$A\cdot X=B $. Then: $${(A^T\cdot A)^{-1}}\cdot A^T\cdot A \cdot X={(A^T\cdot A)^{-1}}\cdot A^T \cdot B$$ So $$X={(A^T\cdot A)^{-1}}\cdot A^T \cdot B.$$ Edit: Another way to solve this problem is solving bellow equations which are derived from matrix multiplication law( when$A^T\cdot A$is not invertible, this method is useful): $$... 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 ...

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