0
$\begingroup$

I've studied Hill's theory where, in order to cypher a vector $p$ of dimension $n\times 1$, we use a squared matrix $A$. We would multiply $Ap$ and get the $n\times 1$ vector $c$, we would then make a modulo $m$ operation, where $m$ is the number of characters we're using to encipher, so this vector $c$ has now values $\in \{1,2,...,m\}^n$. In order to get the original vector we would do the inverse process, multiply ${A^{-1}}c$ (we would have to make sure $A$ has an inverse matrix first), the result modulo $m$ is the original vector $p$. My question is: Is there a Hill cypher where $A$ may not be square? if so, how would it work? if not, is there a proof?

$\endgroup$
  • $\begingroup$ I guess that in theory you only need the mapping $c\mapsto Ac$ to be injective. After all, there is no compelling need for all the vectors to be encrypted versions of a plaintext vector. $\endgroup$ – Jyrki Lahtonen Dec 1 '17 at 9:56
0
$\begingroup$

If $A$ is a $p \times q$-matrix then it transforms a $q \times 1$ vector to a $p \times 1$ vector (over $\mathbb{Z}_m$ in your case). This can only be bijective (invertible) iff $p=q$ because we map $\mathbb{Z}_m^q$ to $\mathbb{Z}_m^p$ and these sets have the same size iff $p=q$. So we need a square invertible matrix to get a valid encryption system with unique decryption.

$\endgroup$
  • $\begingroup$ I agree, but what about using SVD or some other method in order to calculate the pseudo inverse matrix. ¿Would it be possible to somehow find an inverse modulo $m$ matrix using this kind of methods? $\endgroup$ – D. Tiburcio Dec 1 '17 at 17:15
  • $\begingroup$ @D.Tiburcio An encryption system should be a bijection, right? Then we need a square matrix. $\endgroup$ – Henno Brandsma Dec 1 '17 at 18:38
  • $\begingroup$ Thank you, @Henno Brandsma¡ $\endgroup$ – D. Tiburcio Dec 4 '17 at 16:15
  • $\begingroup$ Hey @Henno Brandsma, I was thinking. That is true for a case where we want to map $\mathbb{Z}_{m}^{p}$ to $\mathbb{Z}_{m}^{q}$. But what about a case where we want to map $\mathbb{Z}_{a}^{p}$ to $\mathbb{Z}_{b}^{q}$, so that $ap = bq$. Would it be a way to make that work? $\endgroup$ – D. Tiburcio Dec 5 '17 at 18:26
  • $\begingroup$ @D.Tiburcio you mean $a^p = b^q$ perhaps? $\endgroup$ – Henno Brandsma Dec 5 '17 at 18:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.