Prev: CryptoAnalysis Game4: Crack the attack plan ! (+machines)
Next: CryptoAnalysis Game4: Crack the attack plan ! (Solution !)
From: Mok-Kong Shen on 24 Jan 2010 12:09
In numerical computations in the domain R, one knows that a system of
linear equations can not only be solved using the (in a sense exact)
Gaussian elimination but also be solved (under favourable convergence
conditions depending on the matrix) using iterative methods, among
which the Gauss-Seidel and the Gauss-Jordan method are most popularly
known (see e.g. [1]). Let's first try to consider applying the Gauss-
Seidel iteration to our equation M*C = P mod 26. Denoting the elements
of M by a_ij, with c_i(k) the value computed at the k-th iteration for
c_i, and with sum(j,u,v)[.....] denoting summation for the index j
running from u to v for the term in [.....], we would have the following
typical equation for computing the value of c_i(k):

a_ii*c_i(k) = p_i - sum(j,1,i-1)[a_ij*c_j(k)]
- sum(j,i+1,n)[a_ij*c_j(k-1)] mod 26

One would then compute c_i(k) = a_ii^(-1) * [right hand side of the
above].

Now, in common numerical computations, where such iterative methods are
employed, the goal is to obtain the exact solution or a satisfactorily
good approximate solution and to get that solution as soon (as
efficiently) as possible. For that reason there are in fact much
literatures devoted to the convergence issue of iterative processes
of solving systems of linear equations. However, in our case it turns
out that we need not unconditionally obtain an 'exact' solution of
M*C=P mod 26. For if we could 'somehow' obtain any arbitrary vector C',
such that from C' and M we can manage to compute P, then C' evidently
can serve the purpose of a ciphertext vector just as well as the vector
C. So, let's use, in deviation to the above, the following as the
typical equation in the k-th iteration:

c_i(k) = p_i - sum(j,1,i-1)[a_ij*c_j(k)] - (a_ii-1)*c_i(k-1)
- sum(j,i+1,n)[a_ij*c_j(k-1)] mod 26

Note that all values are known on the right side of the above when
c_i(k) is to be computed. In order to show that, if for any chosen g,
C' is defined as the vector c_i(g) (i=1..n), one can compute from C'
and M backwards to obtain P, it suffices to show that, given c_i(k),
one can obtain c_i(k-1) via the above equation. This is clearly seen to
be the case by multiplying the above equation with (a_ii-1)^(-1),
assuming that (a_ii-1)^(-1) mod 26 exists. So, with the only
restriction on the choice of M in the form that all diagonal elements
a_ii of M must be such that (a_ii-1) has an inverse in Z_26, one could
have quite some freedom (as compared to the original Hill cipher, which
requires a non-singular M) to choose an M, together with a total number
of iterations g, and define the ciphertext vector C' according to
c'_i = c_i(g). Since all odd numbers have inverse in Z_26, the
restriction stated above simply means that the diagonal elements of M
have all to be even.

Finally, it may be mentioned that, while in common numerical
computations the convergence and the rate of convergence of an
iteration process constitute a crucial issue, in our case that's of
absolutely no concern. Quite on the contrary, the worse the iterative
process diverges, the harder would it conceivably be for the analyst to
attempt to find M. Note further that, if desired, the last iteration
step need not be fully done but could stop at a user chosen value of i,
providing thus an unknown for the analyst.

M. K. Shen

---------------------------------------------------------------------
[1] V. N. Faddeeva, Computational Methods of Linear Algebra, Dover
Pub., 1959, p.131.

From: Mok-Kong Shen on 24 Jan 2010 15:28
Mok-Kong Shen wrote:
Since all odd numbers have inverse in Z_26, the
> restriction stated above simply means that the diagonal elements of M
> have all to be even.

Apology, this isn't correct. 13 has no inverse in Z_26.

Addendum: Hill cipher is, of course, not limited to an alphabet of
size 26. For applications on modern computers, one could advantageously
use mod 2^32 on 32-bit computers (or mod 2^64 on 64-bit computers).
With these moduli, all odd numbers have inverse, i.e. all diagonal
elements of M have to be even.

M. K. Shen

From: Mok-Kong Shen on 25 Jan 2010 15:16
Mok-Kong Shen wrote:
> Mok-Kong Shen wrote:
> Since all odd numbers have inverse in Z_26, the
>> restriction stated above simply means that the diagonal elements of M
>> have all to be even.
>
> Apology, this isn't correct. 13 has no inverse in Z_26.
>
> Addendum: Hill cipher is, of course, not limited to an alphabet of
> size 26. For applications on modern computers, one could advantageously
> use mod 2^32 on 32-bit computers (or mod 2^64 on 64-bit computers).
> With these moduli, all odd numbers have inverse, i.e. all diagonal
> elements of M have to be even.

Addendum 2: Larger size n of M is certainly favourable but involves
higher computational cost. An alternative is to use a number of smaller
matrices sequenced e.g. by a PRNG in the encryption process (analogous
to the process of the classical polyalphabetic substitution). It is
also viable to reduce some computation work by leaving out some terms
in the iteration equation, e.g. by limiting terms to those at a certain
user chosen distance left and right of the pivot (the term with the
indices ii). A conceivable variation is to replace some multiplications
and +/- with rotation of bits in words and XOR.

M. K. Shen



 | 
Pages: 1
Prev: CryptoAnalysis Game4: Crack the attack plan ! (+machines)
Next: CryptoAnalysis Game4: Crack the attack plan ! (Solution !)