# Ten selected patents

Ten additional patents are discussed in this section, as listed in Table 15.3. These provide a selective sample of the wide array of existing cryptographic patents. ^{[1]}

Inventors |
Patent # |
Issue date |
Ref. |
Major claim or area |

Feistel |
3,798,359 |
Mar. 19 1974 |
[385] |
Lucifer cipher |

Smid-Branstad |
4,386,233 |
May 31 1983 |
[1154] |
key notarization |

Hellman-Pohlig |
4,424,414 |
Jan. 03 1984 |
[554] |
Pohlig-Hellman cipher |

Massey, Omura |
4,567,600 |
Jan.28 1986 |
[792, 956] |
normal basis arithmetic |

Hellman-Bach |
4,633,036 |
Dec. 30 1986 |
[550] |
generating strong primes |

Merkle |
4,881,264 |
Nov. 14 1989 |
[846] |
one-time signamres |

Goss |
4,956,863 |
Sep.11 1990 |
[519] |
Diffie-Hellman variation |

Merkle |
5,003,597 |
Mar. 26 1991 |
[847] |
Khufu, Khafre ciphers |

Micali et al. |
5,016,274 |
May 14 1991 |
[864] |
on-line/off-line signing |

Brickell et al. |
5,299,262 |
Mar. 29 1994 |
[203] |
exponentiation method |

**Table 15.3: ***Ten selected U.S. cryptographic patents.*

inherent speed.” The patent has 31 figures supporting (only) six pages of text plus one page of thirteen (13) claims.

(ii) Key notarization

The Smid-Branstad patent (4,386,233) addresses key notarization (§13.5.2). It was filed September 29 1980, with no assignee listed. A primary objective of key notarization is to prevent key substitution attacks. The patent contains twenty-one (21) claims.

(iii) Pohlig-Hellman exponentiation cipher

The Helhnan-Pohlig patent (4,424,414) was filed May 1 1978 (four and one-half months after the RS A patent), and assigned to the Board of Trustees of the Leland Stanford Junior University (Stanford, California). It covers the Pohlig-Hellman symmetric-key exponentiation cipher, wherein a prime *q* is chosen, along with a secret key *К*, 1 < *К < q* - 2, from which a second key *D,* 1 < *D < q* - 2, is computed such that *К I) =* 1 mod *(q* - 1). A message *M* is enciphered as *C = M ^{K}* mod

*q,*and the plaintext is recovered by computing

*C*mod

^{D}*q = M.*Two parties make use of this by arranging,

*о priori,*to share the symmetric-keys

*К*and

*D.*The patent contains two (2) claims, specifying a method and an apparatus for implementing this block cipher. Although of limited practical significance, this patent is often confused with the three well-known public-key patents of Table 15.1.

(iv) Arithmetic in F_{2}m using normal bases

Two patents of Massey and Omura are discussed here. The Omura-Massey patent (4,587,627) teaches a method for efficient multiplication of elements of a finite field F_{2}™ by exploiting normal bases representations. It was filed September 14 1982, with priority data November 30 1981 (European patent office), and was issued May 6 1986 with the assignee being OMNET Associates (Sunnyvale, California). The customary' method for representing a field element *0 **e* F_{2}m involves a polynomial basis 1, *x, x ^{2}, x^{3},... , *

*with*

**x**^{m}~,*0 = E?=~o*

^{la}i^{xt}>^{a}i^{€}{0,1} (see §2.6.3). Alternatively, using a normal basis

*x,x*,

^{2},x^{4},...*x*(with

^{2}"'*x*selected such that these are linearly independent) allows one to represent

*0*as

*в*=

*b,x*

^{2}',

*b*6 {0.1}. The inventors note that this representation “is unconventional, but results in much simpler logic circuitry”. For example, squaring in this representation is particularly efficient (noted already by Magleby in 1963) - it requires simply a rotation of the coordinate representation from [fr

_{t}_{m}_i...

*bibo]*to [6„,_

_{2}... bibo&m_i]. This follows since

*x*=

^{2}’"*x*and squaring in F

_{2}>-> is a linear operation in the sense that

*(B+C)*furthermore,!) =

^{2}= B^{2}+C^{2}*В*x

*C*implies

*D*From this, the main object of the patent follows directly: to multiply two elements

^{2}= B^{2}xC^{2}.*В*and

*C*to yield

*D = В*x

*C*= [cf

_{TO}_i

*.. .dido],*the same method used for computing c?

_{m}_i can be used to sequentially produce

*du m*— 2 <

*i <*0, by applying it to one-bit rotations of the representations of

*В*and

*C.*Alternatively,

*m*such identical processes can be used to compute the

*m*components

*d,*in parallel. The patent makes twenty-four (24) claims.

The closely related Massey-Omura patent (4,567,600) includes claims on exponentiation in F_{2}m using normal bases. It was likewise filed September 14 1982 and assigned to OMNET Associates (Sunnyvale, California), with priority date February' 2 1982 (European patent office). Its foundation is the observation that using a normal basis representation allows efficient exponentiation in F_{2}™ (Claim 16), since the cost of squaring (see above) in the customary square-and-multiply exponentiation technique is eliminated. A second subject is the implementation of Shamir’s three-pass protocol (Protocol 12.22) using modular exponentiation in F_{2}m as the ciphering operation along with a normal basis representation for elements; and subsequently employing a shared key, established by this method, as the key in an F_{2}m exponentiation cipher (cf. Hellman-Pohlig patent) again using noimal bases. A

^{1}

further object is a method for computing pairs of integers e, *d* such that *ed =* 1 mod 2^{m} -1. Whereas customarily e is selected and, from it, *d* is computed via the extended Euclidean algorithm (which involves division), the new technique selects a group element Я of high order, then chooses a random integer *R* in [1,2^{m} - 2], and computes e = *H ^{R}, d = H~^{R}. *The patent includes twenty-six (26) claims in total.

(v) Generation of strong primes

The Hellman-Bach patent (4,633,036) covers a method for generating RSA primes *p* and *q *and an RSA modulus *n = pq* satisfying certain conditions such that factoring *n* is believed to be computationally infeasible. The patent was filed May 31 1984 and assigned to Martin E. Heilman. The standard strong prime conditions (Definition 4.52) are embedded: *p —* 1 requiring a large prime factor r; *p +* 1 requiring a large prime factor *s;* and *r* - 1 requiring a large prime factor *r'.* A new requirement according to the invention was that s — 1 have a large prime factor *s',* with cited justification that the (then) best known factoring methods exploiting small *s'* required *s'* operations. The patent includes twenty-four (24) claims, but is now apparently of historical interest only, as the best-known factoring techniques no longer depend on the cited properties (cf. §4.4.2).

(vi) Efficient one-time signatures using expanding trees

Merkle’s 1989 patent (4,881,264), filed July 30 1987 with no assignee listed on the issued patent, teaches how to construct authentication trees which may be expanded arbitrarily, without requiring a large computation when a new tree is constructed (or expanded). The primary cited use of such a tree is for making available public values *у* (corresponding to secret values *x)* of a user *A* in a one-time signature scheme (several of which are summarized). In such schemes, additional public values are continually needed over time. The key idea is to associate with each node in the tree three vectors of public information, each of which contains sufficient public values to allow one one-time signature; call these the LEFT, RIGHT, and MESSAGE vectors. The combined hash value *H,* of all three of these vectors serves as the hash value of the node *i.* The root hash value *Hi* is made widely available, as per the root value of ordinary authentication trees (§13.4.1). A new message *M* may be signed by selecting a previously unused node of the tree (e.g., *Hi),* using the associated MESSAGE vector for a one-time signature thereon. The tree may be expanded downward from node *i* (e.g., *i* = 1), to provide additional (verifiably authentic) public values hi a new left sub-node 2*i* or a right sub-node 2г + 1, by respectively using the LEFT and RIGHT vectors at node *i* to (one-time) sign the hashes Я_{2г} and Я_{2г+}х of the newly created public values in the respective new nodes. Full details are given in the patent; there are nine (9) claims.

The one-time signatures themselves are based on a symmetric cipher such as DES; the associated one-way function Я of a private value *x* may be created by computing *у* = *F(x)* = *DES _{X}(*0), i.e., encrypting a constant value using

*x*as key; and a hash function for the authentication tree may also be constructed using DES. Storage requirements on user

*A*for its own tree are further reduced by noting that only

*x*values need be stored; and that these may be pseudorandomly generated, for example, letting

*J*=0,1,2 denote the LEFT, RIGHT, and MESSAGE vectors, and assuming that

*К*public values are needed per onetime signature, the

*K*value

^{th}*x*in a vector of public values at node

*I*may be defined as

*x[I,*

*J, K] =*DESk

_{a}(IJK), where

*K*is ,4’s secret key and “||” denotes concatenation.

_{A}(vii) Goss variation of Diffie-Hellman

The patent of Goss (4,956,863) covers a variation of Diffie-Hellman key agreement essentially the same as Protocol 12.53. It was filed April 17 1989 and assigned to TRW Inc. (Redondo Beach, California). The primary application cited is an authenticated key establishment technique, completely transparent to end-users, for facsimile (FAX) machines on existing telephone networks. At the tune of manufacture, a unique device identifier and a signed certificate binding this to a long-term Diffie-Hellman public key (public exponential) is embedded in each device. The identity in the certificate, upon verification, may be used as the basis on which to accept or terminate communications channels. Such a protocol allows new session keys for each FAX call, while basing authentication on long-term certified keys (cf. Remark 12.48; but regarding security, see also Note 12.54). The patent makes sixteen (16) claims.

(viii) Khufu and Khafre block ciphers

Merkle’s 1991 patent (5,003,597) covers two symmetric-key block ciphers named Khufu and Khafre (see §7.7.3). These were designed specifically as fast software-oriented alternatives to DES, which itself was designed with hardware performance in mind. The patent was filed December 21 1989 and assigned to the Xerox Corporation. Khufu and Khafre have block size 64 bits and a user-selectable number of rounds. Khufu has key bitlength up to 512 bits, and S-boxes derived from the input key; it encrypts 64-bit blocks faster than Khafre. Khafre has fixed S-boxes, and a key of selectable size (with no upper bound), though larger keys impact throughput. The majority of the patent consists of C-code listings specifying the ciphers. The patent contains twenty-seven (27) claims.

(ix) On-line/off-line digital signatures

The Micali-Goldreich-Even patent (5,016,274) teaches on-line/off-line digital signature schemes. The patent was filed November 8 1988, with no assignee listed. The basic idea is to cany out a precomputation to reduce real-time requirements for signing a particular message *m.* The pre-computation, executed during idle time and independent of *m,* involves generation of matching one-tune public and private keying material for a fast (one-time) first signature scheme, and using a second underlying signature scheme to create a signature s2 over the one-time public key. This key from the first scheme is then used to create a signature si on *m.* The overall signature on *m* is (si, .S2). Appropriate hash functions can be used as usual to allow signing of a hash value *h* (m) rather than *m.* In the exemplary method, Rabin’s scheme is the underlying signature scheme, and DES is used both to build a one-time signature scheme and for hashing. Regarding security of the overall scheme, a one-time scheme, if secure, is presumed secure against chosen-text attack (since it is used only once); the underlying scheme is secure against chosen-text attack because it signs only strings independent of a message *m.* The method thus may convert any signature scheme into one secure against chosen-text attacks (should this be a concern), or convert any underlying signature scheme to one with smaller real-tune requirements. The patent contains thirty-three (33) claims.

(x) Efficient exponentiation for fixed base

The Brickell-Gordon-McCurley patent (5,299,262) teaches a method for fast exponentiation for the case where a fixed base is re-used; see also page 633. This has application in systems such as the ElGamal, Schnorr, and DSA signature schemes. The patent was filed August 13 1992, issued March 29 1994, and assigned to “The United States of America as represented by the United States Department of Energy, Washington, D.C.” The method is presented in Algorithm 14.109. The patent contains nine (9) claims.

# Ordering and acquiring patents

Any American patent may be ordered by patent number from the U.S. Patent and Trademark Office (PTO). Written requests should be posted to: PTO, Washington, D.C., 20231, USA. Telephone requests may also be made at +703-305-4350, with payment by credit card. A nominal fee applies (e.g., US$3 for patents returned by postal mail; or US$6 for returns by fax, usually the same day). For on-line information on recent patents, consult URL http: //www. micropatent. com (e.g., specifying patent class code 380 for cryptography).

- [1] Lucifer cipher Feistel’s patent (3,798,359) is of historical interest. Filed June 30 1971 and assigned to theIBM Corporation, it has now expired. The background section cites a number of earliercipher patents including ciphering wheel devices and key stream generators. Tire patentdiscloses a block cipher, more specifically a product cipher noted as being under the controlof subscriber keys, and designed to resist cryptanalysis “not withstanding ... knowledgeof the structure of the system” (see Chapter 7 notes on §7.4). It is positioned as distinctfrom prior art systems, none of which “utilized the advantages of a digital processor and its