Re: Why RSA?

First, the ViaCrypt version:  I realize that it is legal.
It's also very expensive when compared to the price of
email readers/composers that people normally use (often
weighing in at about $50 / seat).  A $200 add-on is not
likely to be universally accepted.  It's as if somebody
had patented car door locks and claimed that $40,000 was
a reasonable price to have them included on a $10,000
car.  I'm not complaining about the price; people can
charge whatever they want for their products.  However
it does seem kind of high, creating market pressure...
that market pressure surfaces in messages like this one
and hopefully someday competing products from somebody.

Perry Metzger:

> All are patented in so far as one of the patents covers ALL public key
> schemes. Some, like Rabin's scheme, have possible technical advantages
> over RSA.

I am just beginning to study the mathematics behind public
key crypto (got Simmons's _Contemporary Cryptology_ from
the library this morning), but I haven't seen anything
about what exactly this means (that is, I haven't been
able to "look it up").  I was under the impression that
many people participated in the development of P.K.Crypto...
how can somebody patent all of their work?  Don't these
kind of patents apply only to specific algorithms?  Begging
the indulgence of this list, two more questions:

* is there a reference I can read that covers the scope of
  public key crypto patents?

* 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?

Thanks!

derek

Derek Zahn says:
> I was under the impression that
> many people participated in the development of P.K.Crypto...
> how can somebody patent all of their work?

Three people essentially were involved -- Diffie, Helman, and Merkle.
Two of them (I forgot which) filed a patent on the idea itself.

> Don't these
> kind of patents apply only to specific algorithms?

It can be easily argued that at the time the patent was filed
algorithm patents were impermissable, and it can also be argued that
the patent was overbroad. However, no one has ever tried to challenge
the patent properly. It would be a very expensive proposition.

> * 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?

My interpretation is that there isn't anything you could do that
wouldn't be seen to violate the patents. Personally, I feel the
patents are invalid. Care to donate enough money to challenge them?

Perry

>> * is there a reference I can read that covers the scope of
>>   public key crypto patents?

One of the PKP patents (don't remember which) covers the concept of
the encryption and decryption keys being different.  The RSA algorithm
(covered under a separate patent) is one way to implement this idea.

>> * 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?

Write your code, sell it, wait for PKP to sue you, challenge them in
court, and win.

The problem here is that PKP has algorithmic patents (which many
people think should never have been valid in the first place) which
are very broad (covering pretty much all PKC) and cover ideas which
some people think are "obvious" (making them theoretical
unpatentable).  However, once a patent is granted, the only way to get
it thrown out is to challenge it in court.  This is very expensive.
So expensive that Uncle "Infinite Pockets" Sam himself didn't want to
try to free their own algorithm from PKP, and instead licensed it to
them exclusively (or so they claimed).

PKP's patents have never been tested in court.  This means that they
*may be* rotten to the core.  But before you try to sell your own
PKC-based system, make sure you have a bank account and an army of
lawyers as big as Jim's.

The other answer to this question is "leave the US".  This has nothing
to do with ITAR.  The PKP patents, for various reasons, only apply to
the US.

		Marc

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?

others have well addressed how patent issues are involved in this. but
this appears to be a simple technical question on one level. What does
it take to come up with a good public key system?

Answer: far more than you would think. RSA for example has gained its
current degree trust only after about a decade and a half of careful
and intense scrutiny in the literature,  with many new caveats and
modifications invented along the way. Furthermore, the mathematical &
computational journals are strewn with failed attempts at getting a
workable public key system by the most brilliant experts in the field
(actually, in many fields). In particular, there was a lot of
excitement about Knapsack cyphers, related to something called the
Subset Sum problem, and a flurry of papers proposed, broke, and refined
subsequent variations. Currently it appears to have really gotten a
stake through its heart from the last authoritative paper (who?). (I
would be curious for more details from the academically adept.)

The rewards to a public key system are enormous, but the obstacles are
tremendous as well. just getting a good *theoretical* model is very
difficult, as the above attests. Then, this theoretical model has to be
*efficient* when encoded in an algorithm -- another big stumbling
block. Then, in the real world of ugly litigation, it has to tiptoe
around the field of all the national and international patents, and,
ahem, byzantine export laws.

A very grim picture currently, in many ways, and to a large degree why
RSA--and PGP/PRZ-- are so celebrated. Hopefully the future holds
something less bleak.

note: the new sci.crypt FAQ will have a much-improved section on public
key cryptography. watch for it on the newsgroup or
rtfm.mit.edu:/pub/usenet/news-answers/cryptography-faq if you want it right away.