Function needed.

Thread View: sci.crypt

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Raad Siraj Fri, 11 Dec 1987 21:12

#3900

Author: Raad Siraj
Date: Fri, 11 Dec 1987 21:12

24 lines
970 bytes

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

Re: Function needed.

#3902

Author: Tim Tessin
Date: Mon, 14 Dec 1987 18:50

24 lines
1457 bytes

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)

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads