0
$\begingroup$

Let $A$ be a randomly generated matrix. Let $I$ be the identity matrix. $\times$ is the matrix multiplication operation, $/$ is matrix division (multiplying the first matrix by the inverse of the second). $$ I \times A \times A = B $$

Provide $B$ and $I$ to the recipient. To create encrypted message $E$ from unencrypted message $M$: $$ E = M \times A \times A $$

Send $E$ to the recipient. The recipient will solve for $M$ using: $$ M = E / ( B / I) $$ My question is:

  1. Will the recipient be able to decode the message?

  2. If an attacker knows $E$ and $I$, can they efficiently solve for $M$?

  3. Is there a simple way to make it nonlinear?

I accepted an answer but am still waiting for #3.

$\endgroup$
  • 1
    $\begingroup$ What is your message $M$? If $M$ is an $n$-vector, and $A$ is an $n\times n$ matrix, then you've just invented an even less efficient one-time pad. $\endgroup$ – jmite Dec 19 '16 at 3:00
  • $\begingroup$ Okay. But can the encryption only be used once? Does it become easier to crack if multiple Es are known? $\endgroup$ – user63358 Dec 19 '16 at 3:04
  • 3
    $\begingroup$ I don't understand why you are using $I$... I mean: multiplying by $I$ does nothing, moreover the attacker already knows $I$ (he simply has to see the dimension of the matrix...). So your scheme is simply: let $B = A^2$ encode via $M \times B$ and decode via $E \times B^{-1}$. Or am I missing something? Also: in the first step are you assuming that the attacker is unable to eavesdrop the value of $B$? $\endgroup$ – Bakuriu Dec 19 '16 at 8:46
  • $\begingroup$ That's correct. If the attacker has b then E can be decrypted. The I is supposed to just add an extra step. $\endgroup$ – user63358 Dec 19 '16 at 8:50
  • 1
    $\begingroup$ I would like to point that we discourage multiple questions per post. If $I$ is identity then it is superflous... Maybe you could read comments, address them and consider once more the choice of the accepted answer, because the presented "decent scheme" is not exactly decent. $\endgroup$ – Evil Dec 19 '16 at 18:26
15
$\begingroup$

This is not a secure encryption scheme. It is similar to a Hill cipher, and vulnerable to similar attacks. For instance, it is vulnerable to known-plaintext attacks: an attacker who observes a ciphertext E and knows the corresponding message M can recover the secret key and thus decrypt all other messages that were encrypted with the same key.

The recipient will be able to decrypt if A is invertible. If A is not invertible, then the recipient won't be able to decrypt.

See also the questions about the Hill cipher on Crypto.SE.

$\endgroup$
  • $\begingroup$ Is there any simple way to make it nonlinear? $\endgroup$ – user63358 Dec 19 '16 at 3:10
  • 6
    $\begingroup$ @Jsam, probably not; instead, your best bet is probably to use some existing, well-vetted, widely-accepted encryption algorithm. $\endgroup$ – D.W. Dec 19 '16 at 5:12
10
$\begingroup$

Cryptosystems which are algebraic in nature are amenable to algebraic cryptanalysis.

If you are trying to design a secure cryptosystem for actual use, there is one important maxim that you should keep in mind:

Don't design your own cryptosystem!

It is easy to design weak cryptosystems. Off-the-shelf cryptosystems have withstood breaking attempts by the community, and are better than an obscure cryptosystem designed by an amateur.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy