Hill Cipher Attack: Eve Can Crack Alice's Message

  • MHB
  • Thread starter Mathick
  • Start date
  • Tags
    Hill
In summary, the conversation discusses a situation where Alice uses a Hill cipher to send a message consisting of 100 'A's. If Eve intercepts the message and knows the matrix used, she can potentially find the plaintext and complete key. However, the problem statement seems to be incomplete and the conversation discusses possible solutions but also mentions the possibility that the problem cannot be proven.
  • #1
Mathick
23
0
Suppose that we are in the situation that Alice is using a Hill cipher consisting of a $2 \times 2$ matrix $M$ to send her message, which is $100$ ‘A’s. If Eve intercepts this message and knows that plaintext contained only one letter, and she also knows anyone of the entries of the matrix $M$, then prove that Eve can use this information to find the plaintext and the complete key.

So I tried writing a matrix $M$ as $M = \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix}$ and assuming that Eve saw messages $c_1$ and $c_2$, I got

$\begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} \begin{bmatrix} x \\ x \\ \end{bmatrix} = \begin{bmatrix} c_1 \\ c_2 \\ \end{bmatrix}$ which implies $x \begin{bmatrix} a + b \\ c + d \\ \end{bmatrix} = \begin{bmatrix} c_1 \\ c_2 \\ \end{bmatrix}$ where $x$ is a letter that Eve wants to find.

But I don't know how to conclude from this that she can do it. I tried assuming that, for example, she knows the entry $a$ or any other and proceed but it led me nowhere.If you could help or give me some hint, I would appreciate it very much.
 
Mathematics news on Phys.org
  • #2
Hi Mathick,

We also have that the matrix must be invertible.
That is, $ad-bc\not\equiv 0 \pmod{\text n}$, where $n$ is the number of letters.

Either way, it seems to me that the problem statement is incomplete.
Is it possible that we only use the letters 'A' and 'B'?
Because then we can indeed prove what is requested.
 
  • #3
Klaas van Aarsen said:
Hi Mathick,

We also have that the matrix must be invertible.
That is, $ad-bc\not\equiv 0 \pmod{\text n}$, where $n$ is the number of letters.

Either way, it seems to me that the problem statement is incomplete.
Is it possible that we only use the letters 'A' and 'B'?
Because then we can indeed prove the what is requested.

Hi, thanks for your reply!

That is what I thought - that this problem is incomplete. It says that we use a full alphabet (26 letters) and I also came to the conclusion that the statement can't be proven. I will try to find out where the typo is and come back.
 

Related to Hill Cipher Attack: Eve Can Crack Alice's Message

1. What is a Hill Cipher Attack?

A Hill Cipher Attack is a method used to crack a message that has been encrypted using the Hill Cipher algorithm. This attack involves using mathematical techniques to analyze the encrypted message and determine the key used for encryption.

2. How does Eve crack Alice's message using the Hill Cipher Attack?

Eve, the attacker, uses a known plaintext-ciphertext pair to determine the key used in the Hill Cipher algorithm. This can be done by solving a system of linear equations, which is made possible by the structure of the Hill Cipher algorithm.

3. Is the Hill Cipher Attack effective against all messages encrypted with the Hill Cipher algorithm?

No, the Hill Cipher Attack is only effective if the attacker has access to a known plaintext-ciphertext pair. If the attacker does not have this information, the Hill Cipher is considered secure.

4. How can Alice protect her messages from being cracked by Eve using the Hill Cipher Attack?

Alice can protect her messages by using a longer key length and ensuring that the key is randomly generated. She can also use a different encryption algorithm that is not vulnerable to the Hill Cipher Attack.

5. Are there any real-world examples of the Hill Cipher Attack being used?

Yes, the Hill Cipher Attack has been used in various historical and modern examples. One notable example is the cryptanalysis of the Japanese PURPLE cipher during World War II, which was based on the Hill Cipher algorithm.

Similar threads

Replies
24
Views
1K
  • Differential Equations
Replies
2
Views
2K
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
652
  • Calculus and Beyond Homework Help
Replies
12
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
8
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
2K
Replies
2
Views
1K
Back
Top