15th Annual Computer Security Applications Conference
December 6-10, 1999
Phoenix, Arizona

An Effective Defense Against First Party Attacks in Public-Key Algorithms

Stephen M. Matyas, Jr.
Allen Roginsky, roginsky@us.ibm.com
IBM Corporation
3039 Cornwallis Road
RTP, NC 27709

This paper describes a method for assuring that user-generated public and private key pairs are cryptographically strong. This assurance is achieved by limiting the number of attempts a user can make while generating the keys. Since it takes many billions of attempts to generate so-called "weak" keys, with any significant probability of success, our method precludes users from cheating.

The described method has a potential positive impact on several evolving cryptographic standards, where the strength of the keys used with public key cryptography are a matter of major concern. It has no negative impact on key generation performance. The method is simple and straightforward, and it can be easily performed with just a few computational steps.