Cryptography-Research Digest #794

[Digestifier]

Cryptography-Research Digest #794, Volume #1     Tue, 23 Feb 99 19:13:07 EST

Contents:
  A New Public-Key Cryptosystem (Lowball61)

----------------------------------------------------------------------------

From: [EMAIL PROTECTED] (Lowball61)
Subject: A New Public-Key Cryptosystem
Date: 22 Feb 1999 21:32:55 -0800


                    A New Public Key System
 
     This brief paper discusses the possibility of extending the Hill cipher to
function as a public-key cryptosystem (PKC).  Since the public-key would be a
series of tables derived from a rectangular matrix, and since the encryption
process consists of selecting an entry from each of the tables and XORing the
selected entries together, a fundamental question arises as follows: given a
block of encrypted text and the public key, can one derive the entries that
were selected
and XOR'd together to produce the encrypted text at a reasonable cost in terms
of work factor. The author of this paper believes that, to accomplish the
decrypt in an unprohibited time span, a rectangular matrix similar to the
table-generating matrix must be derived first.  Even then, another fundamental
question remains: could the rows which were XOR'd together to produce the
selected entries be determined within a reasonable time span.
 
     What follows is a brief introduction to the extended Hill cipher, without
going into its details.
 
     The Hill cipher encrypts by multiples (mod i) the transform of a vector,
P', by a non-singular matrix M:
 
     P'M = C'
 
     The vector C' is decrypted by multiplying it by the inverse of M, N:
 
     C'N = P'
 
     Given M, N can be computed.
     If i=2 (so that adds are exclusive-ors and all multiplies are just row
selections or omissions) then M can be disguised by pre-adding all combinations
of a number of rows together. Then with a set of elements from P', performing a
series of table-lookups, the product P'M can be obtained by just adding
together the results of all the table-lookups because
 
     (((a+b)+c)+d)+... = (a+b)+(c+d)+...
 
where a+b is the results of the first table-lookup (or the product of the first
k elements of P' and the first k rows of M, and so forth.
 
     Although this disguises M to some extent, the basic for M can still be
computed, perhaps obtains M* instead of M.  From M*, N* could be computed and
C' could be decrypted by 
 
     C'N* = P'
 
     Now suppose M was not a square matrix but the product of a rectangular
matrix R of a special form and a non-singular, disguising  square matrix D.
 
     RD = M
 
     Further suppose that a non-linear transform J, interrelated with R, is
first performed on P'  to produce Q', an expanded vector which has as many
elements as M has rows.  Then Q' is encrypted by multiplying it and M together
 
     Q'M = C'
 
     The vector C' is decrypted by first multiplying it by a square matrix N
(the inverse of D)
 
     C'N = W'
 
to obtain W' on which the combination of the inverse of the non-linear
transform of J and inverse of the multiplication by R can be obtained
 
     (inverse of J and R)(W') = P'
     Now, from the nature of J and R, if their nature were widely known, one
might crack the code by generating some square matrix N*, which when multiplied
by M, products a matrix R* of the same general form as R
 
     MN* = R*
 
     Then C' might be decrypted by multiplying it by N* to product W*
 
     C'N* = W*
 
and performing the inverse operation
 
     (inverse of J* and R*)(W*) = P'
 
     However, suppose that M is disguised by pre-adding all combinations of a
number of rows together to produce a series of tables allowing table-lookups to
be performed, using a series of sets of elements of V', in such a manner that
the non-linear transform J was simultaneously accomplished.  Then suppose that
the results of the series of table-lookups could be added together to product
the same C' as generated previously.
     Suppose further that M is pre-multiplied by a "shuffle" matrix S (an
identity matrix I that has been "shuffled") to obtain M*
 
     SM = M*
 
from which the series of tables are generated.  This tactic effectively hides
those elements of P' are used in the series of table-lookups (that is, it hides
which elements of P' are used each of the table-lookups, from the perspective
of not being able to determine the characteristics of R ).
 
     In view of the foregoing, would such a cipher system be secure as a public
key (the series of tables being the public key) even if the general nature of
the non-linear transform J and the interrelated matrix R were known (but not
their particulars)?  Is there some general algebraic method of solving for P',
given C' and the series of tables?  If so, what is it?
 
Charles Larry Craig

------------------------------


** FOR YOUR REFERENCE **

The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:

    Internet: [EMAIL PROTECTED]

You can send mail to the entire list (and sci.crypt.research) via:

    Internet: [EMAIL PROTECTED]

End of Cryptography-Digest Digest
******************************