6.7.1 Cryptography and the U.S. Patent System

Patents applied to computer programs, frequently called software patents , are the subject of ongoing controversy in the computer industry and in parts of Congress. As the number of software patents issued has steadily grown each year, the U.S. Patent and Trademark Office has come under increasing attack for granting too many patents which are apparently neither new nor novel. There is also some underlying uncertainty whether patents on software are Constitutional, but no case has yet been tried in an appropriate court to definitively settle the matter.

Some of the earliest and most important software patents granted in the United States were in the field of public key cryptography. In particular, Stanford University was awarded two fundamental patents on the knapsack and Diffie-Hellman encryption systems, and MIT was awarded a patent on the RSA algorithm. Table 6.4 summarizes the various patents that have been awarded on public key cryptography.

Between 1989 and 1995, all of these patents were exclusively licensed to Public Key Partners, a small company based in Redwood City, California. As this book went to press, the partnership was dissolved, and the patents have apparently reverted to the partners, Cylink, Inc., of Sunnyvale, Calif., and RSA Data Security of Redwood City, Calif. Exactly what this change in status means for people wishing to practice the inventions has not yet been determined.

6.7.2 Cryptography and Export Controls

Under current U.S. law, cryptography is a munition, akin to nuclear materials and biological warfare agents. Thus, export of cryptographic machines (such as computer programs that implement cryptography) is covered by the Defense Trade Regulations (formerly known as the International Traffic in Arms Regulation - ITAR ). To export a program in machine-readable format that implements cryptography, you need a license from the Office of Defense Trade Controls ( DTC ) inside the U.S. State Department; publishing the same algorithm in a book or public paper is not controlled.

To get a license to export a program, you disclose the program to DTC , which then makes an evaluation. (In practice, these decisions are actually made by the National Security Agency.) Historically, programs that implement sufficiently weak cryptography are allowed to be exported; those with strong cryptography, such as DES , are denied export licenses.

A 1993 survey by the Software Publisher's Association, a U.S.-based industry advocacy group, found that encryption is widely available in overseas computer products and that availability is growing. They noted the existence of more than 250 products distributed overseas containing cryptography. Many of these products use technologies that are patented in the U.S. (At the time, you could literally buy high-quality programs that implement RSA encryption on the streets of Moscow, although Russia has since enacted stringent restrictions on the sale of cryptographic programs.)

Table 6.4: The Public Key Cryptography Patents

Patent #	Title	Covers Invention	Inventors	Assignee	Date Filed	Date Granted	Date Expires
4,200,770	Cryptographic Apparatus and Method	Diffie-Hellman key exchange	Martin E. Hellman, Bailey W. Diffie, Ralph C. Merkle,	Stanford University	September 6, 1977	April 29, 1980	April 29, 1997
4,218,582	Public Key Cryptographic Apparatus and Method	Knapsack, and possibly all of public key cryptography	Martin E. Hellman, Ralph C. Merkle	Stanford University	October 6, 1977	August 19, 1980	August 19, 1997
4,424,414	Exponentiation Cryptographic Apparatus and Method		Martin E. Hellman, Stephen C. Pohlig	Stanford University	May 1, 1978	January 3, 1984	January 3, 2001
4,405,829	Cryptographic Communications System and Method	RSA encryption	Ronald L. Rivest, Adi Shamir, Leonard M. Adleman	Massachusetts Institute of Technology	December 14, 1977	September 20, 1983	September 20, 2000

Most European countries used to have regulations regarding software similar to those in force in the U.S. Many were discarded in the early 1990s in favor of a more liberal policy, which allows mass-market software to be freely traded.

In 1992, the Software Publishers Association and the State Department reached an agreement which allows the export of programs containing RSA Data Security's RC2 and RC4 algorithms, but only when the key size is set to 40 bits or less. 40 bits is not very secure, and application of a distributed attack using standard workstations in a good-size lab can break these in at most a few days. This theory was demonstrated quite visibly in mid-1995 when two independent groups broke 40-bit keys used in the export version of the Netscape browser. Although the effort took many machines and days of effort, both were accomplished in fairly standard research environments similar to many others around the world.

Canada is an interesting case in the field of export control. Under current U.S. policy, any cryptographic software can be directly exported to Canada without the need of an export license. Canada has also liberalized its export policy, allowing any Canadian-made cryptographic software to be further exported abroad. But software that is exported to Canada cannot then be exported to a third country, thanks to Canada's Rule #5100, which honors U.S. export prohibitions on "all goods originating in the United States" unless they have been "further processed or manufactured outside the United States so as to result in a substantial change in value, form, or use of the goods or in the production of new goods."

Several companies are now avoiding the hassle of export controls by doing their software engineering overseas, and then importing the products back into the United States. We feel that current regulations only serve to hobble U.S. industry, and only play a minor role in slowing the spread of encryption use worldwide.