Re: the public key minefield

[smb@research.att.com]

	 >  derek@cs.wisc.edu (Derek Zahn)
	 > >* in broad terms, what would I have to do to develop an
	 > >  algorithm that works from a user's perspective like
	 > >  p.k.c. (ie public/private keys, the central functional
	 > >  point of all the wonderful schemes based on pkc) but
	 > >  doesn't violate patents?
	 L. Detweiler writes:
	 > others have well addressed how patent issues are involved in this. b
	ut
	 > this appears to be a simple technical question on one level. What do
	es
	 > it take to come up with a good public key system?

	 How about a poor public key system?  What is the simplest public key
	 system you can invent, if you didn't care that it is trivial to break?
	 If the NSA can crack RSA, does that change the fact that it is a pkc?

	 message=99

	 public_key= 1/3
	 private_key= 3

	 encrypted_message= message * public_key
	 message= encrypted_message * private_key

	 Would PKP reading of their patent claims cover this pkc?  Seems overbr
	oad!


No, because of the language in the patent which requires that it be
infeasible to find the deciphering key from the enciphering key.  Here's
the claim, from patent 4218582, that covers all of public key cryptography:

1. In a method of communicating securely over an insecure communication
channel of the type which communicates a message from a transmitter to
a receiver, the improvement characterized by:
  providing random numbers at the receiver;
  generating from said random numbers a public enciphering key at the
    receiver;
  generating from said random numbers a secret deciphering key at the
    receiver such that the secret deciphering key is directly related to
    and computationally infeasible to generate from the public enciphering
    key;
  communicating the public enciphering key from the receiver to the
    transmitter;
  processing the message and the public enciphering key at the
    transmitter and generating an enciphered message by an enciphering
    transformation, such that the enciphering transformation is easy to
    effect but computationally infeasible to invert without the secret
    deciphering key;
  transmitting the enciphered message from the transmitter to the
    receiver; and
  processing the enciphered message and the secret deciphering key at
    the receiver to transform the enciphered message with the secret
    deciphering key to generate the message.