In this paper we present a modification of the DSA which allows signatures with message recovery. The new public key signature scheme is then applied to create (a) an identity-based public key system without restrictions in trust and (b) a one-pass key exchange protocol with mutual authentication.

Conditions are derived which guarantee that products of linear recurring sequences attain maximum linear complexity. It is shown that the product of any number of maximum-length GF(q)sequences has maximum linear complexity, provided only the degrees of the corresponding minimal polynomials are distinct and greater than two. It is also shown that if the roots of any number of (not necessarily irreducible) minimal polynomials are simple and lie in extension fields of pairwise relatively prime degrees, then the product of the corresponding GF(q)sequences attains maximum linear complexity, provided only that no two roots of any minimal polynomial are linearly dependent over the groundfield GF(q)(which is automatically satisfied whenq = 2). The results obtained for products are extended to arbitrary linear combinations of product sequences.