[sci.crypt] Function needed.

siraj@endor.harvard.edu (Raad Siraj) (12/12/87)

I need a function that takes in any variable-length message M of m bits,
and a secret key K of k bits, and produces a fixed length bit pattern of
s bits.

Requirements:

1. Given any number of M's and their corresponding s bit patterns,
   it should be computationally difficult to compute the s bit pattern
   of any new message. (difficult enough to exhaust $200 before a solution
   is found)

2. The function should be simple to implement (much simpler and faster than
   RSA and DES).

Note:

This function could be called a hashing or compressed encoding function that
acts as a trapdoor or one-way function.


Any suggestions or pointers?

Ra'ad

tjt@ati.tis.llnl.gov (Tim Tessin) (12/15/87)

In article <3523@husc6.harvard.edu> siraj@endor.UUCP (Raad Siraj) writes:
> I need a function that takes in any variable-length message M of m bits,
> and a secret key K of k bits, and produces a fixed length bit pattern of
> s bits.

The best thing I have found so far is to use DES.  It really is not THAT
slow, but granted, slower than XOR based algorithms.

Procedure:  take a 64 bit random seed and feed it thru DES using
successive 56 bit chunks of the original message at each pass.  Use
the 64 bit random number as well as the 64 bit output from the DES
munching to create a 128 bit signature.  Use an XOR method to 
eliminate the need for passing twice thru DES to eliminate 
"meet-in-middle" attacks.  

Reference: "Digital Signatures ...", Communications of ACM, April 1984
Volume 27, Number 4

The DES algorithm routines were posted to the net a while back by
Phil Karn.

Tim Tessin - Lawrence Livermore National Laboratory
Phone: (415) 423-4560
Net:   tjt@ati.tis.llnl.gov (lll-tis.ARPA, lll-tis.UUCP)