I've been looking over Shamir's secret sharing polynomial scheme that Schneier describes in section 23.2 of AC2. The basic equation for a (3,n) threshold scheme is (ax^2+bx+M) mod p. I understand that the coefficients need to be randomly generated for each message but is it OK to reuse the same prime p over and over? If the message M is always a 160-bit SHA hash, could I just find the first 161-bit prime and hard-code it into my application and then just generate new 160-bit coefficients for each new message?

Yes, as long as the message can never be more than 160 bits this would be fine, the co-efficients must be true random for the security to be perfect. Indeed using the same prime is an advantage as you suggest because it does not alter the security but increases the ease of implementing the system. Datacomms Technologies web authoring and data security Paul Bradley, Paul@fatmans.demon.co.uk Paul@crypto.uk.eu.org, Paul@cryptography.uk.eu.org Http://www.cryptography.home.ml.org/ Email for PGP public key, ID: 5BBFAEB1 "Don`t forget to mount a scratch monkey"