Obviousness — US Patent 7020281

Obviousness Analysis under 35 U.S.C. § 103

Under United States patent law, an invention is not patentable if "the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains." This analysis evaluates whether the independent claims of US patent 7,020,281 would have been obvious to a person of ordinary skill in the art (PHOSITA) at the time of the invention.

For the purpose of this analysis, a PHOSITA would be a computer scientist, mathematician, or electrical engineer with several years of experience in the field of applied cryptography. This individual would possess a strong understanding of public-key cryptosystems like RSA and Elliptic Curve Cryptography (ECC), the common algorithms used for their implementation (e.g., square-and-multiply, double-and-add), and the security vulnerabilities associated with physical implementations, specifically side-channel attacks like timing analysis.

Analysis of Independent Claim 1

Claim 1 describes a method for performing a cryptographic operation where each bit of a secret binary vector is processed with "similar operations" to create a constant-time execution flow. This is achieved through a state-based method where for each bit, a primary group operation (e.g., a square or double) is performed, followed by a secondary operation involving either a group element or its inverse, depending on the state.

The claim would be obvious in light of the combination of Paul C. Kocher's 1996 paper, US Patent 5,991,415, and common knowledge in the art.

Motivation to Solve the Problem: The foundational 1996 paper by Paul C. Kocher ("Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and other systems") is cited by the patent and was widely known at the time of the invention. This paper established the vulnerability of cryptographic implementations where the execution time varies based on the value of secret key bits. This disclosure would have provided a strong motivation for a PHOSITA to develop methods that eliminate these timing variations.
Teaching the Core Solution: US Patent 5,991,415 ('415 patent) directly teaches the fundamental solution to the problem identified by Kocher. The '415 patent discloses making the exponentiation process uniform by "perform[ing] a modular multiplication at each step of the square-and-multiply loop, regardless of whether the corresponding key bit is a zero or a one." This concept of executing a fixed sequence of operations for every bit—what Claim 1 of the '281 patent calls "similar operations"—is the core principle for preventing timing attacks. US Patent 6,366,673 teaches a nearly identical approach.
Obviousness of the Implementation: Claim 1's specific implementation involves using an inverse element (e.g., subtraction in an additive group or division in a multiplicative group) for one bit value and the element itself for the other. A PHOSITA, taught by the '415 patent to always perform two operations per bit (e.g., square and multiply), would find it an obvious design choice to substitute a dummy multiplication with a meaningful inverse operation. In the context of ECC (an additive group explicitly mentioned in the '281 patent's background), adding the inverse of a point (-P) is computationally identical in time and complexity to adding the point (P). A PHOSITA would recognize that using an addition or a subtraction for every bit of the scalar achieves the constant-time goal of the '415 patent. The use of a state machine as described in Claim 1 is a standard and straightforward programming technique for implementing such a loop.

Therefore, a PHOSITA, motivated by Kocher to create a constant-time algorithm and taught by the '415 patent to do so by performing a fixed number of operations per bit, would have found it obvious to implement this solution by using an element or its computationally equivalent inverse for the second operation in the loop. This constitutes the invention claimed in Claim 1.

Analysis of Independent Claim 6

Claim 6 describes a method where a scalar, represented as a binary vector, is first "recoded... to produce a signed digit representation of plus one and minus one digits." Subsequently, the cryptographic operation proceeds by either adding or subtracting a group element based on the value of each signed digit.

The claim would be obvious in light of US Patent 6,175,850 ('850 patent) in view of the Kocher paper.

Motivation: As with Claim 1, the Kocher paper provides the motivation for a PHOSITA to find a method of performing scalar multiplication or exponentiation that is resistant to timing analysis by regularizing the process.
Direct Teaching of the Method: US Patent 6,175,850 ('850 patent) directly teaches the central, non-obvious element of Claim 6. The '850 patent describes a method for modular exponentiation using a "redundant binary representation" for the exponent, where digits can be {-1, 0, 1}. This is synonymous with the "signed digit representation of plus one and minus one digits" claimed in Claim 6. The '850 patent discloses this recoding as a method for performing the calculation.
Motivation to Combine: A PHOSITA, tasked with solving the timing attack problem from Kocher, would have looked for known mathematical techniques to make the exponentiation process more uniform. The signed-digit recoding method from the '850 patent is one such technique. A PHOSITA would have immediately recognized that an algorithm based on a signed-digit representation—which replaces a variable sequence of multiplies with a more regular sequence of additions and subtractions—is inherently more resistant to simple timing attacks. The motivation to apply the known recoding technique from the '850 patent to solve the well-known timing problem from Kocher would have been clear, and there would have been a reasonable expectation of success.

In summary, the '850 patent discloses the key technique of recoding a binary number into a signed-digit representation for cryptographic computation. Applying this known technique to solve the widely understood problem of timing attacks would have been an obvious step for a person of ordinary skill in the art.