Five fundamental patents

Table 15.1 lists five basic cryptographic patents which are fundamental to current cryptographic practice, three involving basic ideas of public-key cryptography. These patents are discussed in chronological order.

Inventors

Patent #

Issue date

Ref.

Major claim or area

Ehrsam et al.

3,962,539

Jun. 08 1976

[363]

DES

Hellman-Diffie-Merkle

4,200,770

Apr. 29 1980

[551]

Diffie-Hellman agreement

Hellman-Merkle

4,218,582

Aug. 19 1980

[553]

public-key systems

Merkle

4,309,569

Jan. 05 1982

[848]

tree authentication

Rivest-Shamir-Adleman

4,405,829

Sep. 20 1983

[1059]

RSA system

Table 15.1: Five fundamental U.S. cryptographic patents.

(i) DES block cipher

The patent of Ehrsam et al. (3,962,539) covers the algorithm which later became well- known as DES (§7.4). Filed on February 24 1975 and now expired, the patent was assigned to the International Business Machines Corporation (IBM). Its background section comments briefly on 1974 product cipher patents of Feistel (3,798,359) and Smith (3,796,830), respectively filed June 30 1971 and November 2 1971. It notes that while the Feistel patent discloses a product cipher which combines key-dependent linear and nonlinear transformations, it fails to disclose specific details including precisely how key bits are used, regarding the nonlinear transformation within S-boxes, and regarding a particular permutation. In addition, the effect of key bits is limited by the particular grouping used. The background section comments further on the cipher of Smith’s patent, noting its inherently serial nature as a performance drawback, and that both it and that of Feistel have only two types of sub?stitution boxes, which are selected as a function of a single key bit. Thus, apparently, the need for a new cipher. The patent contains ten (10) claims.

(ii) Diffie-Hellman key agreement

The first public-key patent issued, on April 29 1980, was the Hellman-Diffie-Merkle patent (4,200,770). Filed on September 6 1977, it was assigned to Stanford University (Stanford, California). It is generally referred to as the Diffie-Hellman patent, as it covers Diffie- Hellman key agreement (§12.6.1). There are two major objects of the patent. The first is a method for communicating securely over an insecure channel without a priori shared keys; this can be done by Diffie-Hellman key agreement. The second is a method allowing authentication of an identity over insecure channels; this can be done using authentic, longterm Diffie-Hellman public keys secured in a public directory, with derivation and use of the resulting Diffie-Hellman secret keys providing the authentication. The patent contains eight (8) claims including the idea of establishing a session key by public-key distribution, e.g., using message exchanges as in two-pass Diffie-Hellman key agreement. Claim 8 is the most specific, specifying Diffie-Hellman using a prune modulus q and exponents x, and Xj in [I,? - 1].

(iii) Merkle-Hellman knapsacks and public-key systems

The Hellman-Merkle patent (4,218,582) was filed October 6 1977 and assigned to the Board of Trustees of the Leland Stanford Junior University (Stanford, California). It covers public-key cryptosystems based on the subset-sum problem, i.e., Merkle-Hellman trapdoor knapsacks (now known to be insecure - see §8.6.1), in addition to various claims on public- key encryption and public-key signatures. The objects of the invention are to allow private conversations over channels subject to interception by eavesdroppers; to allow authentication of a receiver’s identity (through its ability to use a key only it would be able to compute); and to allow data origin authentication without the threat of dispute (i.e., via public- key techniques, rather than a shared secret key). There are seventeen (17) claims, with Claims 1-6 broadly applying to public-key systems, and Claims 7-17 more narrowly focused on knapsack systems. The broad claims address aspects of general methods using public-private key pairs for public-key encryption, public-key signatures, and the use of public-key encryption to provide authentication of a receiver via the receiver transmitting back to the sender a representation of the enciphered message.

(iv) Tree authentication method of validating parameters

Merkle’s 1982 patent (4,309,569) covers tree authentication (§13.4.1). It was filed September 5 1979, and assigned to the Board of Trustees of the Leland Stanford Junior University (Stanford, California). The main motivation cited was to eliminate the large storage requirement inherent in prior one-time signature schemes, although the idea has wider application. The main ideas are to use a binary tree and a one-way hash function to allow authentication of leaf values Y, associated with each user i. Modifications cited include: use of a ternary or k-aiy tree in place of a binary tree; use of the tree for not only public values of one-time signatures, but for authenticating arbitrary public values for alternate purposes; and use of a distinct authentication tree for each user i, the root R, of which replaces Y, above, thereby allowing authentication of all values hi i’s tree, rather than just a single Yt . The epitome of conciseness, this patent contains a single figure and just over two pages of text including four (4) claims.

(v) RSA public-key encryption and signature system

The Rivest-Shamir-Adleman patent (4,405,829) was filed December 14 1977, and assigned to the Massachusetts Institute of Technology. It covers the RSA public-key encryption (§8.2.1) and digital signature method (§11.3.1). Also mentioned are generalizations, including: use of a modulus n which is a product of three or more prunes (not necessarily distinct); and using an encryption public key e to encrypt a message M to a ciphertext C by evaluating a polynomial ^i=0 aiMe mod n where e and 0 < г < t, are integers, and recovering the plaintext M by “utilizing conventional root-finding techniques, choosing which of any roots is the proper decoded version, for example, by the internal redundancy of the message”. Other variations mentioned include using RSA encipherment in CFB mode, or as a pseudorandom number generator to generate key pads; signing a compressed version of the message rather than the message itself; and using RSA encryption for key transfer, the key thereby transferred to be used in another encryption method. This patent has the distinction of a claims section, with forty (40) claims, which is longer than the remainder of the patent.

 
Source
< Prev   CONTENTS   Source   Next >