US6510518B1 — Balanced cryptographic computational method and a…

Claim 1

Independent Claim 120 words

A method for using a secret key to cryptographically process a message, comprising: (a) receiving a message to be cryptographically processed; (b) in a hardware device, cryptographically processing said message by performing a plurality of cryptographic suboperations thereon, each said suboperation: (i) taking an input, via at least one intermediate, to an output, (ii) including a number of computational state transformations, said number being independent of said message and of said key, and (iii) characterized such that the Hamming weights of said message, said intermediate, and said output are independent of said message and of said key; and (c) outputting said cryptographically processed message; whereby external monitoring of said hardware device does not reveal useful information about said secret key.

Claim 2

Independent Claim 120 words

A method for using a secret key to cryptographically process a message, comprising: (a) receiving a message to be cryptographically processed; (b) in a hardware device, cryptographically processing said message by performing a plurality of cryptographic suboperations thereon, each said suboperation: (i) taking an input, via at least one intermediate, to an output, (ii) including a number of computational state transformations, said number being independent of said message and of said key, and (iii) characterized such that the Hamming weights of said message, said intermediate, and said output are independent of said message and of said key; and (c) outputting said cryptographically processed message; whereby external monitoring of said hardware device does not reveal useful information about said secret key.

Claim 3

Independent Claim 71 words

A method for performing a balanced cryptographic operation on input data, comprising: (a) representing said input data using a constant Hamming weight representation; and (b) using a secret key, manipulating said input data to produce output data by performing a balanced cryptographic operation thereon; thereby cryptographically processing said input data in a manner resistant to detection of said secret key by external monitoring of a hardware device performing said cryptographic operation.

Claim 4

Independent Claim 71 words

A method for performing a balanced cryptographic operation on input data, comprising: (a) representing said input data using a constant Hamming weight representation; and (b) using a secret key, manipulating said input data to produce output data by performing a balanced cryptographic operation thereon; thereby cryptographically processing said input data in a manner resistant to detection of said secret key by external monitoring of a hardware device performing said cryptographic operation.

Claim 5

Dependent Claim 33 words

The method of claim 2 wherein step (a) includes converting said input data from a non-constant Hamming weight representation, said method further comprising converting said output data to said non-constant Hamming weight representation.

Claim 6

Dependent Claim 29 words

The method of claim 2 wherein the number of state transitions performed during step (b) is balanced so as to be uncorrelated to the value of said secret key.

Claim 7

Independent Claim 101 words

A method for performing a balanced cryptographic operation on input data, comprising: (a) representing said input data using a first constant Hamming weight representation; (b) manipulating said input data to produce intermediate data in said first constant Hamming weight representation; (c) converting said intermediate data from said first constant Hamming weight representation to a second constant Hamming weight representation; and (d) manipulating said intermediate data to produce output data according to said cryptographic operation; thereby cryptographically processing said input data in a manner resistant to detection of said secret key by external monitoring of a hardware device performing said cryptographic operation.

Claim 8

Independent Claim 101 words

A method for performing a balanced cryptographic operation on input data, comprising: (a) representing said input data using a first constant Hamming weight representation; (b) manipulating said input data to produce intermediate data in said first constant Hamming weight representation; (c) converting said intermediate data from said first constant Hamming weight representation to a second constant Hamming weight representation; and (d) manipulating said intermediate data to produce output data according to said cryptographic operation; thereby cryptographically processing said input data in a manner resistant to detection of said secret key by external monitoring of a hardware device performing said cryptographic operation.

Claim 9

Dependent Claim 56 words

A balanced cryptographic processing device comprising: (a) a secret key; (b) an input interface for receiving data; (c) a conversion unit to convert said data into a constant Hamming weight representation; and (d) a processor configured to perform a cryptographic operation on said data by using said secret key while preserving said constant Hamming weight representation.

Claim 10

Dependent Claim 56 words

A balanced cryptographic processing device comprising: (a) a secret key; (b) an input interface for receiving data; (c) a conversion unit to convert said data into a constant Hamming weight representation; and (d) a processor configured to perform a cryptographic operation on said data by using said secret key while preserving said constant Hamming weight representation.

Claim 11

Independent Claim 103 words

A method for performing a balanced cryptographic operation using secret data, comprising: (a) performing a plurality of suboperations using said secret data and an operand; and (b) for each of said plurality of suboperations, simultaneously performing corresponding suboperations using (i) said operand and the complement of said secret data, (ii) said secret data and the complement of said operand, and (iii) the complement of said secret data and the complement of said operand; thereby cryptographically processing said operand and said secret data in a manner resistant to detection of said secret data by external monitoring of a hardware device performing said cryptographic operation.

Claim 12

Independent Claim 103 words

A method for performing a balanced cryptographic operation using secret data, comprising: (a) performing a plurality of suboperations using said secret data and an operand; and (b) for each of said plurality of suboperations, simultaneously performing corresponding suboperations using (i) said operand and the complement of said secret data, (ii) said secret data and the complement of said operand, and (iii) the complement of said secret data and the complement of said operand; thereby cryptographically processing said operand and said secret data in a manner resistant to detection of said secret data by external monitoring of a hardware device performing said cryptographic operation.

Claim 13

Independent Claim 208 words

A method for performing a balanced computational process comprising: (a) receiving a first and a second input variable, each input variable having N bits; (b) creating a value of a first intermediate variable having 2N bits, each of a first half of said 2N bits being equal to a corresponding bit of said first input variable, each of a second half of said 2N bits being equal to the complement of a corresponding bit of said first input variable; (c) creating a value of a second intermediate variable having 2N bits, each of a first half of said 2N bits corresponding to a bit of said second input variable, each of a second half of said 2N bits being equal to a corresponding bit of said first half of said 2N bits; (d) creating a value of a third intermediate having 2N bits, each bit being the result of a bitwise logical operation on a corresponding bit of said first intermediate variable and a corresponding bit of said second intermediate variable; and (e) extracting a result of said computational process from said third intermediate variable; thereby cryptographically processing said input variables in a manner resistant to detection by external monitoring of a hardware device performing said computational process.

Claim 14

Independent Claim 208 words

A method for performing a balanced computational process comprising: (a) receiving a first and a second input variable, each input variable having N bits; (b) creating a value of a first intermediate variable having 2N bits, each of a first half of said 2N bits being equal to a corresponding bit of said first input variable, each of a second half of said 2N bits being equal to the complement of a corresponding bit of said first input variable; (c) creating a value of a second intermediate variable having 2N bits, each of a first half of said 2N bits corresponding to a bit of said second input variable, each of a second half of said 2N bits being equal to a corresponding bit of said first half of said 2N bits; (d) creating a value of a third intermediate having 2N bits, each bit being the result of a bitwise logical operation on a corresponding bit of said first intermediate variable and a corresponding bit of said second intermediate variable; and (e) extracting a result of said computational process from said third intermediate variable; thereby cryptographically processing said input variables in a manner resistant to detection by external monitoring of a hardware device performing said computational process.

Claim 15

Dependent Claim 42 words

The method of claim 8 wherein said first and second input variables are represented in a constant Hamming code representation, wherein said method further comprises transforming said third intermediate variable such that said result is represented in said constant Hamming code representation.

Claim 16

Dependent Claim 17 words

The method of claim 9 wherein said step of transforming includes a constant number of state transitions.

Claim 17

Dependent Claim 188 words

A balanced cryptographic processing device comprising: (a) an input interface for receiving a first and a second input variable to be used as inputs to a computation, each input variable represented by at least a first bit and a second bit, where said representation has a constant Hamming weight; (b) a first computational unit for performing a bitwise logical operation on said first bit of said first input variable and said first bit of said second input variable; (c) a second computational unit for performing said bitwise logical operation on said first bit of said first input variable and said second bit of said second input variable; (d) a third computational unit for performing said bitwise logical operation on said second bit of said first input variable and said first bit of said second input variable; and (e) a fourth computational unit for performing said bitwise logical operation on said second bit of said first input variable and said second bit of said second input variable; thereby cryptographically processing said input variables in a manner resistant to detection by external monitoring of a hardware device performing said operations.

Claim 18

Dependent Claim 188 words

A balanced cryptographic processing device comprising: (a) an input interface for receiving a first and a second input variable to be used as inputs to a computation, each input variable represented by at least a first bit and a second bit, where said representation has a constant Hamming weight; (b) a first computational unit for performing a bitwise logical operation on said first bit of said first input variable and said first bit of said second input variable; (c) a second computational unit for performing said bitwise logical operation on said first bit of said first input variable and said second bit of said second input variable; (d) a third computational unit for performing said bitwise logical operation on said second bit of said first input variable and said first bit of said second input variable; and (e) a fourth computational unit for performing said bitwise logical operation on said second bit of said first input variable and said second bit of said second input variable; thereby cryptographically processing said input variables in a manner resistant to detection by external monitoring of a hardware device performing said operations.

Claim 19

Dependent Claim 33 words

The device of claim 11 further comprising a first load including an output interface for outputting an output of said computation, said output interface connected to an output of said first computational unit.

Claim 20

Dependent Claim 63 words

The device of claim 12 further comprising a second load connected to an output of said second computational unit, a third load connected to an output of said third computational unit, and a fourth load connected to an output of said fourth computational unit, each of said second, third, and fourth loads having an impedance matched to the impedance of said first load.

Claim 21

Dependent Claim 18 words

The device of claim 13 wherein said first, second, third, and fourth computational units have identical design parameters.

Claim 22

Dependent Claim 68 words

An electronic circuit configured to perform a computation on input data represented in a balanced Hamming weight format, said computation comprising: (a) receiving said input data through an input interface; (b) producing from said input data an intermediate variable represented in said balanced Hamming weight format; (c) deriving a result from said intermediate variable; and (d) transmitting at least a portion of said result to a receiving circuit.

Claim 23

Dependent Claim 68 words

An electronic circuit configured to perform a computation on input data represented in a balanced Hamming weight format, said computation comprising: (a) receiving said input data through an input interface; (b) producing from said input data an intermediate variable represented in said balanced Hamming weight format; (c) deriving a result from said intermediate variable; and (d) transmitting at least a portion of said result to a receiving circuit.

Claim 24

Independent Claim 157 words

A method for reducing the amount of information available for detection through monitoring of the power consumption of a device during a digital cryptographic computation comprising: (a) receiving input data represented by a plurality of sets of data bits in a representation format wherein: (i) each data bit can have one of two values, (ii) each set of data bits includes at least two data bits; (iii) the value of each set of data bits can be encoded as at least two functionally-equivalent combinations of values of said data bits; (b) processing said input data through a series of substeps, wherein (i) said substeps combine said input data to compute intermediate data represented in said format, and (ii) by balancing at least one characteristic of said computation, the amount of power consumed at each substep is made not detectably correlated to the value of said intermediate data; and (c) producing an output result from said intermediate data.

Claim 25

Independent Claim 157 words

A method for reducing the amount of information available for detection through monitoring of the power consumption of a device during a digital cryptographic computation comprising: (a) receiving input data represented by a plurality of sets of data bits in a representation format wherein: (i) each data bit can have one of two values, (ii) each set of data bits includes at least two data bits; (iii) the value of each set of data bits can be encoded as at least two functionally-equivalent combinations of values of said data bits; (b) processing said input data through a series of substeps, wherein (i) said substeps combine said input data to compute intermediate data represented in said format, and (ii) by balancing at least one characteristic of said computation, the amount of power consumed at each substep is made not detectably correlated to the value of said intermediate data; and (c) producing an output result from said intermediate data.

Claim 26

Dependent Claim 33 words

The method of claim 16 wherein a plurality of said processing substeps include transforming said intermediate data from a first representation to a second representation, said first and second representation being functionally equivalent.

Claim 27

Dependent Claim 27 words

The method of claim 16 wherein the at least one characteristic balanced in step (b)(ii) includes the total Hamming weight of the representation of said intermediate data.

Claim 28

Dependent Claim 41 words

The method of claim 16 wherein the at least one characteristic balanced in step (b)(ii) includes the number of state transitions that occur during at least one of said substeps that are a function of the representation of said intermediate data.

Claim 29

Dependent Claim 32 words

The method of claim 16 wherein a plurality of said substeps of step(b) include computing a representation of said intermediate data from the XOR of two data bits of said input data.

Claim 30

Dependent Claim 16 words

The method of claim 16 wherein said computation is performed using a circuit of hard-wired transistors.

Claim 31

Dependent Claim 12 words

The method of claim 16 wherein said computation is implemented in microcode.

Claim 32

Dependent Claim 22 words

The method of claim 16 wherein said computation is implemented in software as part of a cryptographic process using a secret key.

Claim 33

Dependent Claim 14 words

The method of claim 23 wherein said cryptographic algorithm is a symmetric block cipher.

Claim 34

Independent Claim 114 words

A method for converting a definition of a computational device capable of performing cryptographic operations using a secret key into a definition of a digital circuit, comprising: (a) receiving a machine-readable definition of said computational device; (b) using a processor to compile at least a portion of a process for said operation by (i) converting said process into a sequence including a plurality of logic operations, and (ii) converting said plurality of logic operations into a plurality of operations for which the power consumption is balanced; (c) writing an output file representing said plurality of balanced logic operations; and (d) transmitting said output file to a third party for fabrication into said digital circuit.

Claim 35

Independent Claim 114 words

A method for converting a definition of a computational device capable of performing cryptographic operations using a secret key into a definition of a digital circuit, comprising: (a) receiving a machine-readable definition of said computational device; (b) using a processor to compile at least a portion of a process for said operation by (i) converting said process into a sequence including a plurality of logic operations, and (ii) converting said plurality of logic operations into a plurality of operations for which the power consumption is balanced; (c) writing an output file representing said plurality of balanced logic operations; and (d) transmitting said output file to a third party for fabrication into said digital circuit.

Claim 36

Dependent Claim 49 words

The method of claim 25 wherein each of a first plurality of bits represented in said machine-readable definition is represented in said output file by a second plurality of bits, wherein the Hamming weight of said second plurality of bits is independent of the individual values of said bits.

Claim 37

Dependent Claim 32 words

The method of claim 25 wherein said cryptographic operation comprises a block cipher, and said digital circuit is balanced to reduce a correlation between power consumption and a cryptographic processing intermediate variable.

Claim 38

Dependent Claim 12 words

The method of claim 25 wherein said digital circuit includes a multiplier.

Claim 39

Independent Claim 102 words

A method for converting a definition of a computational process into a definition of software whose power consumption is balanced, comprising the steps of: (a) receiving a machine-readable definition of said computational process; (b) using a processor to compile at least a portion of said process by (i) converting said process into a sequence of operations including a plurality of logic operations, and (ii) converting said plurality of logic operations into a plurality of operations for which the power consumption is balanced; and (c) writing an output file representing said plurality of balanced logic operations expressed as a sequence of executable instructions.

Claim 40

Independent Claim 102 words

A method for converting a definition of a computational process into a definition of software whose power consumption is balanced, comprising the steps of: (a) receiving a machine-readable definition of said computational process; (b) using a processor to compile at least a portion of said process by (i) converting said process into a sequence of operations including a plurality of logic operations, and (ii) converting said plurality of logic operations into a plurality of operations for which the power consumption is balanced; and (c) writing an output file representing said plurality of balanced logic operations expressed as a sequence of executable instructions.

Claim 41

Dependent Claim 13 words

The method of claim 29 wherein said computational process comprises a block cipher.

Claim 42

Dependent Claim 136 words

A cryptographic processing device for securely performing a cryptographic processing operation in a manner resistant to the discovery of a secret by external monitoring, comprising: (a) an input interface for receiving a quantity to be cryptographically processed and for converting said quantity into an expanded balanced representation; and (b) a processing circuit operatively connected to said input interface and including: (i) a plurality of main logic subunits configured to in compute the result of said cryptographic processing operation; and (ii) a plurality of additional logic subunits of composition similar to said main logic units which operate simultaneously with said main logic units to balance the power consumption of the computation performed by said main logic units; and (c) an output interface operatively connected to said processing circuit for outputting said result of said cryptographic processing operation.

Claim 43

Dependent Claim 136 words

A cryptographic processing device for securely performing a cryptographic processing operation in a manner resistant to the discovery of a secret by external monitoring, comprising: (a) an input interface for receiving a quantity to be cryptographically processed and for converting said quantity into an expanded balanced representation; and (b) a processing circuit operatively connected to said input interface and including: (i) a plurality of main logic subunits configured to in compute the result of said cryptographic processing operation; and (ii) a plurality of additional logic subunits of composition similar to said main logic units which operate simultaneously with said main logic units to balance the power consumption of the computation performed by said main logic units; and (c) an output interface operatively connected to said processing circuit for outputting said result of said cryptographic processing operation.

Claim 44

Dependent Claim 14 words

The method of claim 31 wherein said cryptographic processing operation comprises a block cipher.

Claim 45

Dependent Claim 49 words

The method of claim 1 , 2 , 3 , 4 , 5 , 7 , 8 , 9 , 10 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 31 , or 32 implemented in an ISO 7816-compliant smart card.

Claim 46

Dependent Claim 19 words

The device of claim 6 , 11 , or 13 where said device comprises an ISO 7816-compliant smart card.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2006-01-20	2006-07-22	2007-01-21	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2010-01-20	2010-07-22	2011-01-21	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2014-01-20	2014-07-22	2015-01-21	$7700.00	Window Closed / Lapsed

Balanced cryptographic computational method and apparatus for leak minimizational in smartcards and other cryptosystems

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag