CA2259089C - Method and apparatus for masking cryptographic operations - Google Patents
Method and apparatus for masking cryptographic operations Download PDFInfo
- Publication number
- CA2259089C CA2259089C CA 2259089 CA2259089A CA2259089C CA 2259089 C CA2259089 C CA 2259089C CA 2259089 CA2259089 CA 2259089 CA 2259089 A CA2259089 A CA 2259089A CA 2259089 C CA2259089 C CA 2259089C
- Authority
- CA
- Canada
- Prior art keywords
- private key
- parts
- term private
- value
- long term
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
- G06F7/725—Finite field arithmetic over elliptic curves
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06K—GRAPHICAL DATA READING; PRESENTATION OF DATA; RECORD CARRIERS; HANDLING RECORD CARRIERS
- G06K19/00—Record carriers for use with machines and with at least a part designed to carry digital markings
- G06K19/06—Record carriers for use with machines and with at least a part designed to carry digital markings characterised by the kind of the digital marking, e.g. shape, nature, code
- G06K19/067—Record carriers with conductive marks, printed circuits or semiconductor circuit elements, e.g. credit or identity cards also with resonating or responding marks without active components
- G06K19/07—Record carriers with conductive marks, printed circuits or semiconductor circuit elements, e.g. credit or identity cards also with resonating or responding marks without active components with integrated circuit chips
- G06K19/073—Special arrangements for circuits, e.g. for protecting identification code in memory
- G06K19/07309—Means for preventing undesired reading or writing from or onto record carriers
- G06K19/07363—Means for preventing undesired reading or writing from or onto record carriers by preventing analysis of the circuit, e.g. dynamic or static power analysis or current analysis
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/002—Countermeasures against attacks on cryptographic mechanisms
- H04L9/003—Countermeasures against attacks on cryptographic mechanisms for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
- H04L9/3013—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3066—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
- G06F2207/7219—Countermeasures against side channel or fault attacks
- G06F2207/7223—Randomisation as countermeasure against side channel attacks
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
- G06F2207/7219—Countermeasures against side channel or fault attacks
- G06F2207/7223—Randomisation as countermeasure against side channel attacks
- G06F2207/7233—Masking, e.g. (A**e)+r mod n
- G06F2207/7242—Exponent masking, i.e. key masking, e.g. A**(e+r) mod n; (k+r).P
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Computer Security & Cryptography (AREA)
- Physics & Mathematics (AREA)
- Computing Systems (AREA)
- Mathematical Analysis (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Computer Hardware Design (AREA)
- Mathematical Physics (AREA)
- Microelectronics & Electronic Packaging (AREA)
- Algebra (AREA)
- Storage Device Security (AREA)
Abstract
A method of masking a cryptographic operation using a secret value, comprising the steps of dividing the secret value into a plurality of parts; combining with each part a random value to derive a new part such that the new parts when combined are equivalent to the original secret value; and utilizing each of the individual parts in the operation.
Description
METHOD AND APPARATUS FOR MASKING CRYPTOGRAPHIC OPERATIONS
This invention relates to cryptographic systems and in particular to a method and apparatus for minimizing successful power analysis attacks on processors.
BACKGROUND OF THE INVENTION
Cryptographic systems generally owe their security to the fact that a particular piece of information is kept secret, without which it is almost impossible to break the scheme. This secret information must generally be stored within a secure boundary, making it difficult for an attacker to get at it directly however, various schemes or attacks have been attempted in order to obtain the secret information. Of particular risk are portable cryptographic tokens, including smart cards and the like. Of the more recent attacks performed on these particularly vulnerable devices are simple power analysis, differential power analysis, higher order differential power analysis and other related techniques. These technically sophisticated and extremely powerful analysis tools can be used by an attacker to extract secret keys from cryptographic devices. It has been shown that these attacks can be mounted quickly and can be implemented using readily available hardware. The amount of time required for these attacks depends on the type of attack and varies somewhat by device. For example it has been shown that a simple power attack (SPA) typically take a few seconds per card, while the differential power attacks (DPA) can take several hours.
Cryptographic operations are performed in a processor operating in a sequential manner by performing a sequence of fundamental operations, each of which generates a distinct timing pattern. Laborious but careful analysis of end-to-end power waveforms can decompose the order of these fundamental operations performed on each bit of a secret key and thus be, analyzed to find the entire secret key, compromising the system.
In the simple power analysis (SPA) attacks on smart cards and other secure tokens, an attacker directly measures the token's power consumption changes over time.
The amount of power consumed varies depending on the executed microprocessor instructions. A
large calculation such as elliptic curve (EC) additions in a loop and DES rounds, etc, may be identified, since the operations performed with a microprocessor vary significantly during different parts of these operations. By sampling the current and voltage at a higher rate, i.e., higher resolution, individual instructions can be differentiated.
The differential power analysis attack (DPA) is a more powerful attack than the SPA
and is much more difficult to prevent. Primarily, the DPA uses statistical analysis and error correction techniques to extract information which may be correlated to secret keys, while the SPA attacks use primarily visual inspection to identify relevant power fluctuations. The DPA
attack is performed in two steps. The first step is recording data that reflects the change in power consumed by the card during execution of cryptographic routines. In the second step, the collected data is statistically analyzed to extract information correlated to secret keys. A
detailed analysis of these attacks is described in the paper entitled "Introduction to Differential Power Analysis and Related Attacks" by Paul Kocher et al.
Various techniques for addressing these power attacks have been attempted to date.
These include hardware solutions such as providing well-filtered power supplies and physical shielding of processor elements. However, in the case of smart cards and other secure tokens, this is unfeasible. The DPA vulnerabilities result from transistor and circuit electrical behaviors that propagate to expose logic gates, microprocessor operation and ultimately the software implementations.
Accordingly, there is a need for a system for reducing the risk of a successful power analysis attacks and which is particularly applicable to current hardware environments.
SUMMARY OF THE INVENTION
It is an object of this invention to provide a method for minimizing power analysis attacks on processors.
In accordance with this invention there is provided a method of masking a cryptographic operation using a secret value, comprising the steps of:
(a) dividing said secret value into a plurality of parts;
(b) combining with each part a random value to derive a new part such that the new parts when combined are equivalent to the original secret value; and (c) utilizing each of the individual parts in said operation.
This invention relates to cryptographic systems and in particular to a method and apparatus for minimizing successful power analysis attacks on processors.
BACKGROUND OF THE INVENTION
Cryptographic systems generally owe their security to the fact that a particular piece of information is kept secret, without which it is almost impossible to break the scheme. This secret information must generally be stored within a secure boundary, making it difficult for an attacker to get at it directly however, various schemes or attacks have been attempted in order to obtain the secret information. Of particular risk are portable cryptographic tokens, including smart cards and the like. Of the more recent attacks performed on these particularly vulnerable devices are simple power analysis, differential power analysis, higher order differential power analysis and other related techniques. These technically sophisticated and extremely powerful analysis tools can be used by an attacker to extract secret keys from cryptographic devices. It has been shown that these attacks can be mounted quickly and can be implemented using readily available hardware. The amount of time required for these attacks depends on the type of attack and varies somewhat by device. For example it has been shown that a simple power attack (SPA) typically take a few seconds per card, while the differential power attacks (DPA) can take several hours.
Cryptographic operations are performed in a processor operating in a sequential manner by performing a sequence of fundamental operations, each of which generates a distinct timing pattern. Laborious but careful analysis of end-to-end power waveforms can decompose the order of these fundamental operations performed on each bit of a secret key and thus be, analyzed to find the entire secret key, compromising the system.
In the simple power analysis (SPA) attacks on smart cards and other secure tokens, an attacker directly measures the token's power consumption changes over time.
The amount of power consumed varies depending on the executed microprocessor instructions. A
large calculation such as elliptic curve (EC) additions in a loop and DES rounds, etc, may be identified, since the operations performed with a microprocessor vary significantly during different parts of these operations. By sampling the current and voltage at a higher rate, i.e., higher resolution, individual instructions can be differentiated.
The differential power analysis attack (DPA) is a more powerful attack than the SPA
and is much more difficult to prevent. Primarily, the DPA uses statistical analysis and error correction techniques to extract information which may be correlated to secret keys, while the SPA attacks use primarily visual inspection to identify relevant power fluctuations. The DPA
attack is performed in two steps. The first step is recording data that reflects the change in power consumed by the card during execution of cryptographic routines. In the second step, the collected data is statistically analyzed to extract information correlated to secret keys. A
detailed analysis of these attacks is described in the paper entitled "Introduction to Differential Power Analysis and Related Attacks" by Paul Kocher et al.
Various techniques for addressing these power attacks have been attempted to date.
These include hardware solutions such as providing well-filtered power supplies and physical shielding of processor elements. However, in the case of smart cards and other secure tokens, this is unfeasible. The DPA vulnerabilities result from transistor and circuit electrical behaviors that propagate to expose logic gates, microprocessor operation and ultimately the software implementations.
Accordingly, there is a need for a system for reducing the risk of a successful power analysis attacks and which is particularly applicable to current hardware environments.
SUMMARY OF THE INVENTION
It is an object of this invention to provide a method for minimizing power analysis attacks on processors.
In accordance with this invention there is provided a method of masking a cryptographic operation using a secret value, comprising the steps of:
(a) dividing said secret value into a plurality of parts;
(b) combining with each part a random value to derive a new part such that the new parts when combined are equivalent to the original secret value; and (c) utilizing each of the individual parts in said operation.
2 BRIEF DESCRIPTION OF THE DRAWINGS
These and other features of the preferred embodiments of the invention will become more apparent in the following detailed description in which reference is made to the appended drawings wherein:
Figure 1 is a schematic diagram of a communication system; and Figure 2 is a flow diagram illustrating an embodiment of the invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Referring to figure 1, a communication system having at least a pair of corespondents is shown generally by numeral 10. It is assumed that the correspondents 12 and incorporate cryptographic units 16 and 18 respectively. For convenience, the first correspondent will be referred to as the sender and the second correspondent will be referred to as the receiver. Generally, a plain text message is processed by the encryption unit of the sender and transmitted as cyphertext along a communication channel to the receiver where the encryption message is decrypted by the cryptographic unit 18 to recover the original message.
The above system provides a typical environment for application of the invention as will be described below.
Referring to figure 2 a method for masking a private key or secret value used in a cryptographic operation is shown generally by numeral 200. The method comprises the steps of dividing a secret value into a plurality of parts and combining with each part a random value modulo n (where n is the number of points on the elliptic curve) to derive a new part such that the new parts are combined to be equivalent to the original secret value and utilizing each of the individual parts in the operation. Typically, the secret value is a private key, which is used to compute a public key, and more frequently used in signatures, decryption and possibly key exchange protocols, such as Diffie-Hellman key exchange.
For illustrative purposes, we will in the following discussion assume an EC
scheme, where P is a point on the elliptic curve. The secret key d is normally combined with the point P to derive dP, the public key. However, the private key may also be used more frequently in various other cryptographic operations as described above. The cryptographic processor is
These and other features of the preferred embodiments of the invention will become more apparent in the following detailed description in which reference is made to the appended drawings wherein:
Figure 1 is a schematic diagram of a communication system; and Figure 2 is a flow diagram illustrating an embodiment of the invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Referring to figure 1, a communication system having at least a pair of corespondents is shown generally by numeral 10. It is assumed that the correspondents 12 and incorporate cryptographic units 16 and 18 respectively. For convenience, the first correspondent will be referred to as the sender and the second correspondent will be referred to as the receiver. Generally, a plain text message is processed by the encryption unit of the sender and transmitted as cyphertext along a communication channel to the receiver where the encryption message is decrypted by the cryptographic unit 18 to recover the original message.
The above system provides a typical environment for application of the invention as will be described below.
Referring to figure 2 a method for masking a private key or secret value used in a cryptographic operation is shown generally by numeral 200. The method comprises the steps of dividing a secret value into a plurality of parts and combining with each part a random value modulo n (where n is the number of points on the elliptic curve) to derive a new part such that the new parts are combined to be equivalent to the original secret value and utilizing each of the individual parts in the operation. Typically, the secret value is a private key, which is used to compute a public key, and more frequently used in signatures, decryption and possibly key exchange protocols, such as Diffie-Hellman key exchange.
For illustrative purposes, we will in the following discussion assume an EC
scheme, where P is a point on the elliptic curve. The secret key d is normally combined with the point P to derive dP, the public key. However, the private key may also be used more frequently in various other cryptographic operations as described above. The cryptographic processor is
3 generally initialized at manufacture time with the public key or secret value d. Initially, the valued may be divided into a number of parts, e.g. d - bia + bxo.
In,a first step :the bi's are initialized to bi - btaand bz such that d = b10 + b20.
These initial, i+itlues: cif hi and b2 are stored instead of d. Alternatively the d value may also be stored if so, desired; however in the case of a smart card' where memory is limited this may not be desir~bTc_ Typically when, a computation using the value disrequired. At a next step, a random number n is generated and the values b I and b2 are: Updated as follows:
b1: b, + .7r mod n b2 b2 n mod n The updated values of b, and b2 are stored. Computation is then performed on.
the point P usingthe:coaiponents b, and b2 as follows.
dP wo b3P + b2P
where, P is apoint on the curve which is a predefined parameter of the system.
'T'hus assuming the value n is randomly :generated for each session, then an attacker is unlikely tq':ohstrue a predictable power signatuic;
In a. typical application of the present invention a signature component s has the form:-s n ae + yk (mod n) where:
k Is a random ;integer selected as a short terra private or session key;
R kP J. the corresponding short team public key;
r~l?, x .component o.fR
a is, the. long to nl private key of the sender;
Q:,al is the senders corresponding public key;
e is a secure hash, such as the SI3A-I hash function, of a message m and the short terra public ;key R( or possibly a short message itself); and, n is, the order of the curve.
The sender sends to the recipient a message including m, s, and r and the signature is vcri Pied by coznpudng'the value R'- (sP-eQ) which should correspond to R. If the:computed
In,a first step :the bi's are initialized to bi - btaand bz such that d = b10 + b20.
These initial, i+itlues: cif hi and b2 are stored instead of d. Alternatively the d value may also be stored if so, desired; however in the case of a smart card' where memory is limited this may not be desir~bTc_ Typically when, a computation using the value disrequired. At a next step, a random number n is generated and the values b I and b2 are: Updated as follows:
b1: b, + .7r mod n b2 b2 n mod n The updated values of b, and b2 are stored. Computation is then performed on.
the point P usingthe:coaiponents b, and b2 as follows.
dP wo b3P + b2P
where, P is apoint on the curve which is a predefined parameter of the system.
'T'hus assuming the value n is randomly :generated for each session, then an attacker is unlikely tq':ohstrue a predictable power signatuic;
In a. typical application of the present invention a signature component s has the form:-s n ae + yk (mod n) where:
k Is a random ;integer selected as a short terra private or session key;
R kP J. the corresponding short team public key;
r~l?, x .component o.fR
a is, the. long to nl private key of the sender;
Q:,al is the senders corresponding public key;
e is a secure hash, such as the SI3A-I hash function, of a message m and the short terra public ;key R( or possibly a short message itself); and, n is, the order of the curve.
The sender sends to the recipient a message including m, s, and r and the signature is vcri Pied by coznpudng'the value R'- (sP-eQ) which should correspond to R. If the:computed
4 Y
values correspond then the signature is verified. Both the secret keys in the above example may be masked using the method of the present invention.
Specifically referring back to the above example, calculation of the product ae may reveal some information on some platforms in some environments. To minimise this, the present invention is applied. The product ae is computed as ae = (bo + b1)e for (bo + b1) =a;
where bo, b1 sum to a. The components bo , b1 are updated periodically as described above.
This updating of the components can be made on every new signature operation.
In the above embodiments the secret value was divided into two components bo , b1, however this may be generalized to a plurality of components b0....bri_1.
Furthermore the above signature scheme is used for illustrative purposes and other schemes and operations may equally well be applied using the present invention.
Although the invention has been described with reference to certain specific embodiments, various modifications thereof will be apparent to those skilled in the art without departing from the spirit and scope of the invention as outlined in the claims appended hereto.
values correspond then the signature is verified. Both the secret keys in the above example may be masked using the method of the present invention.
Specifically referring back to the above example, calculation of the product ae may reveal some information on some platforms in some environments. To minimise this, the present invention is applied. The product ae is computed as ae = (bo + b1)e for (bo + b1) =a;
where bo, b1 sum to a. The components bo , b1 are updated periodically as described above.
This updating of the components can be made on every new signature operation.
In the above embodiments the secret value was divided into two components bo , b1, however this may be generalized to a plurality of components b0....bri_1.
Furthermore the above signature scheme is used for illustrative purposes and other schemes and operations may equally well be applied using the present invention.
Although the invention has been described with reference to certain specific embodiments, various modifications thereof will be apparent to those skilled in the art without departing from the spirit and scope of the invention as outlined in the claims appended hereto.
5
Claims (49)
1. A method of masking ai private key used in a cryptographic operation, said method comprising the steps of:
applying a masking value, said masking value comprising a random value modulo n where n is a n, umber of points on an elliptic curve, to said private key during at least a portion of said cryptographic operation to produce a result, said result corresponding to that obtained without application of said masking value whereby observation of 6t least said private key is inhibited by said masking value during at least a portion of said cryptographic operation.
applying a masking value, said masking value comprising a random value modulo n where n is a n, umber of points on an elliptic curve, to said private key during at least a portion of said cryptographic operation to produce a result, said result corresponding to that obtained without application of said masking value whereby observation of 6t least said private key is inhibited by said masking value during at least a portion of said cryptographic operation.
2. The method of claim 1 wherein said random value is randomly generated for each session of said cryptographic operation.
3. The method of claim 2 wherein before applying said masking value, said method further comprising:
dividing said private key into a plurality of parts, and wherein applying said masking value comprises applying said masking value to each of said plurality of parts to generate a plurality of new parts, said plurality of new parts stored such that said plurality of new parts are updated with said random value each session.
dividing said private key into a plurality of parts, and wherein applying said masking value comprises applying said masking value to each of said plurality of parts to generate a plurality of new parts, said plurality of new parts stored such that said plurality of new parts are updated with said random value each session.
4. The method according to any one of claims 1 to 3 wherein said cryptographic operation is according to :an elliptic curve (EC) cryptographic scheme.
5. The method according, to claim 4 wherein said cryptographic operation comprises generation of a first signature component.
6. The method according to claim 5 wherein said private key comprises a short term private key, said method further comprising applying said short term private key to a point on an elliptic curve utilized by said EC scheme to obtain a short term public key.
7. The method according to claim 6 further comprising using said short term public key to generate a second signature component.
8. The method according to claim 5 wherein said private key comprises. a long term private key, said method further comprising applying said long term private key to a point on said elliptic curve to obtain a long term public key.
9. The method according to claim 5 wherein said private key comprises a short term private key and a long term private key and wherein said first signature component has the form: s = ae + k (mod n), wherein s is said first signature component, a is said long term private key, e is a value obtained using a hash function, k is said short term private key.
10. The method according to claim 9 wherein e is computed using a value computed using said short term private key.
11. The method according to claim 9 wherein a first masking value is applied to said long term private key and a second masking value different from said first masking value is applied to said short term private key.
12. The method according to claim 11 wherein said masking values change after each cryptographic operation.
13. The method according to claim 9 wherein at least one of said short term private key and said long term private key is split into component parts and a masking value applied to each of said parts.
14. The method according to claim 13 wherein said masking value is applied in a complementary manner to each of said parts, such that, when said parts are combined, the value of said at least one of said short term private key and said long term private key is obtained.
15. The method; according to claim 13 or claim 14 wherein said masking value is added to one of said component parts and said masking value is subtracted from another of said component parts.
16. A computer readable medium comprising computer executable instructions for causing a processor to perform the method according to any one of claims 1 to 15.
17. A cryptographic unit comprising said processor and said computer readable medium according to claim 16.
18. A method for generating a public key in an elliptic curve (EC) cryptographic scheme, said method comprising the steps of:
obtaining a private key; splitting said private key into a plurality of components;
combining, with each of said components, a random value modulo n, where n is a number of points on an elliptic curve, to derive a plurality of new parts such that said plurality of new parts when combined are equivalent to said private key;
combining each of said new parts with a point on said elliptic curve to obtain a plurality of point multiples; and, combining said plurality of point multiples to obtain said public key.
obtaining a private key; splitting said private key into a plurality of components;
combining, with each of said components, a random value modulo n, where n is a number of points on an elliptic curve, to derive a plurality of new parts such that said plurality of new parts when combined are equivalent to said private key;
combining each of said new parts with a point on said elliptic curve to obtain a plurality of point multiples; and, combining said plurality of point multiples to obtain said public key.
19. The method according to claim 18 further comprising generating a new random value and storing updated values for said new parts for each session of said cryptographic operation.
20. The method according to claim 18 or claim 19 wherein combining comprises adding said random value to a one of said components and subtracting said random value from another of said components.
21, The method according to any one of claims 18 to 20 further comprising using said public key in a further cryptographic operation.
22. The method according to claim 21 wherein said further cryptographic operation is computing a signature.
23. A computer readable medium comprising computer executable instructions for causing a processor to perform the method according to any one of claims to 22.
24. A cryptographic unit comprising said processor and said computer readable medium according to claim 23.
26. A method of masking a private key used in a cryptographic operation comprising the steps of:
(a) dividing said private key into a plurality of parts;
(b) combining with each part a random value modulo n, where n is a number of points on an elliptic curve, to derive a new part such that the new parts when combined are equivalent to the original private key; and (c) utilizing each of the individual parts in said cryptographic operation.
(a) dividing said private key into a plurality of parts;
(b) combining with each part a random value modulo n, where n is a number of points on an elliptic curve, to derive a new part such that the new parts when combined are equivalent to the original private key; and (c) utilizing each of the individual parts in said cryptographic operation.
26. A method according to claim 25, comprising generating said random value for each session of said cryptographic operation.
27.A method according to claim 25, said operation being an elliptic curve cryptographic operation.
28.A method according to claim 26 wherein said new parts are stored such that said new parts are updated with said random value for each session.
29.A method according to Claim 25 wherein said private key is used to compute a public key by combining said plurality of parts with a point P of said elliptic curve.
30.A method according to claim 25 wherein said cryptographic operation comprises generating a signature component using said private key.
31. A method according to claim 30 wherein said private key is a short term private key and a long term private key, each generated according to steps (a) and (b) and said signature component is generated using said short term private key and said long term private key.
32.A method according to claim 25 wherein said plurality of parts is a pair of values b1 and b2 and said random value is a value .pi., said plurality of parts and said random value combined as follows: b1 = h1 + .pi. mod n and b2 = b2 - .pi. mod n.
33.A method according to claim 32 wherein computation is then performed on a point P
using said values b1 and b2 as follows: dP = b1 P+ b2P; wherein dP is a public key.
using said values b1 and b2 as follows: dP = b1 P+ b2P; wherein dP is a public key.
34. A method according to claim 25 wherein said cryptographic operation is generating a signature component s = ae + k (mod n) to be used in verifying a signature on a message m, e being a secure hash of said message m, a being a long term private key and is said private key and k being a short term private key, and said long term private key being divided into a pair of values b1 and b2 which are combined with said random, value modulo n by adding said random value modulo n to b1 and subtracting said random value modulo n from b2.
35.A computer readable medium comprising computer readable program code embodied thereon for causing a cryptographic processor to perform the method of any one of claims 25 to 34.
36. A cryptographic unit comprising said processor and said computer readable medium according to claim 35.
37. A method of masking a cryptographic operation performed in a discrete logarithm public key cryptographic system, a processor of said system having a long term private key and a short term private key, the processor performing said cryptographic operation using a generator G, said method comprising:
a) dividing one of said long term private key and said short term private key into a plurality of parts;
b) generating a separate random value for association with said plurality of parts;
c) combining each of said plurality of parts with said random value to derive a plurality of new values such that said new values when combined are equivalent to said one of said long term private key and said short term private key; and d) using each of said new values in said cryptographic operation to obtain components and subsequently combining said components to obtain a value corresponding to a combination of said one of said long term private key and said short term private key and said generator.
a) dividing one of said long term private key and said short term private key into a plurality of parts;
b) generating a separate random value for association with said plurality of parts;
c) combining each of said plurality of parts with said random value to derive a plurality of new values such that said new values when combined are equivalent to said one of said long term private key and said short term private key; and d) using each of said new values in said cryptographic operation to obtain components and subsequently combining said components to obtain a value corresponding to a combination of said one of said long term private key and said short term private key and said generator.
38. The method of claim 37, wherein said one of said long term private key and said short term private key is updated by a new random value after said cryptographic operation is performed, for use in a subsequent operation.
39. The method of claim 37, wherein said one of said long term private key and said short term private key, when divided into first and second parts, has said random value added to said first part and subtracted from said second part such that the sum of said first and second parts and said associated random value is equivalent to said one of said long term private key and said short term private key.
40. The method of claim 37, wherein said cryptographic operation is an elliptic curve digital signature algorithm.
41. The method of claim 40 wherein a signature component s has the form s =
ae+k where a is said long term private key, e is a bit string derived from a message m and k is said short term private key, and said private key a is represented as a pair of components, b0, b1, such that b0 +b1=a and wherein said component b0 has said random value added and said component b1 has said random value subtracted.
ae+k where a is said long term private key, e is a bit string derived from a message m and k is said short term private key, and said private key a is represented as a pair of components, b0, b1, such that b0 +b1=a and wherein said component b0 has said random value added and said component b1 has said random value subtracted.
42. The method of claim 37 wherein said operation is performed in an additive group.
43. The method of claim 37 wherein said operation is performed in a multiplicative group.
44. The method of claim 38 wherein said new values are stored after said cryptographic operation and said new random value is combined with said stored values, for use in a subsequent operation.
46. The method of claim 1 wherein said one of said long term private key and said short term private key is used to generate a corresponding public key, said method comprising performing said group operation on each of said plurality of parts to generate a plurality of public keys and utilizing each of said public keys in said operation.
46. The method of claim 37 wherein said cryptographic operation includes the generation of a signature component utilizing said long term and short term private keys combined with additional information, said method comprising combining each of said plurality of parts with said additional information and subsequently combining results thereof to form said signature component.
47. A computer readable storage medium having stored thereon computer executable instructions configured to cause a processor to perform the method of any one of claims 37 to 46.
48. A processor configured to perform the method of any one of claims 37 to 46.
49. A cryptographic unit comprising said processor of claim 48 configured by said computer readable medium of claim 47.
Priority Applications (10)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CA 2259089 CA2259089C (en) | 1999-01-15 | 1999-01-15 | Method and apparatus for masking cryptographic operations |
| PCT/CA2000/000030 WO2000042733A1 (en) | 1999-01-15 | 2000-01-14 | Method and apparatus for masking cryptographic operations |
| AU30281/00A AU3028100A (en) | 1999-01-15 | 2000-01-14 | Method and apparatus for masking cryptographic operations |
| US09/900,959 US7092523B2 (en) | 1999-01-11 | 2001-07-10 | Method and apparatus for minimizing differential power attacks on processors |
| US10/119,803 US7599491B2 (en) | 1999-01-11 | 2002-04-11 | Method for strengthening the implementation of ECDSA against power analysis |
| US11/483,553 US8666070B2 (en) | 1999-01-11 | 2006-07-11 | Method and apparatus for minimizing differential power attacks on processors |
| US12/495,429 US8280048B2 (en) | 1999-01-11 | 2009-06-30 | Method for strengthening the implementation of ECDSA against power analysis |
| US12/837,268 US8666063B2 (en) | 1999-01-11 | 2010-07-15 | Method and apparatus for minimizing differential power attacks on processors |
| US13/619,557 US8621239B2 (en) | 1999-01-11 | 2012-09-14 | Method for strengthening the implementation of ECDSA against power analysis |
| US13/621,021 US8660264B2 (en) | 1999-01-11 | 2012-09-15 | Method and apparatus for minimizing differential power attacks on processors |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CA 2259089 CA2259089C (en) | 1999-01-15 | 1999-01-15 | Method and apparatus for masking cryptographic operations |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CA2259089A1 CA2259089A1 (en) | 2000-07-15 |
| CA2259089C true CA2259089C (en) | 2013-03-12 |
Family
ID=4163193
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CA 2259089 Expired - Lifetime CA2259089C (en) | 1999-01-11 | 1999-01-15 | Method and apparatus for masking cryptographic operations |
Country Status (3)
| Country | Link |
|---|---|
| AU (1) | AU3028100A (en) |
| CA (1) | CA2259089C (en) |
| WO (1) | WO2000042733A1 (en) |
Families Citing this family (15)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7092523B2 (en) | 1999-01-11 | 2006-08-15 | Certicom Corp. | Method and apparatus for minimizing differential power attacks on processors |
| US7599491B2 (en) | 1999-01-11 | 2009-10-06 | Certicom Corp. | Method for strengthening the implementation of ECDSA against power analysis |
| JP3926532B2 (en) * | 2000-03-16 | 2007-06-06 | 株式会社日立製作所 | Information processing apparatus, information processing method, and card member |
| AU2001280735A1 (en) * | 2000-07-24 | 2002-02-05 | David Chaum | Transparent-coin electronic money system |
| GB0204620D0 (en) * | 2002-02-28 | 2002-04-10 | Europay Internat N V | Chip authentication programme |
| US8909557B2 (en) | 2002-02-28 | 2014-12-09 | Mastercard International Incorporated | Authentication arrangement and method for use with financial transaction |
| DE10222212A1 (en) | 2002-05-16 | 2003-12-04 | Giesecke & Devrient Gmbh | Spying-proof modular inversion |
| AU2004252824B2 (en) * | 2003-06-04 | 2011-03-17 | Mastercard International Incorporated | Customer authentication in e-commerce transactions |
| US8467535B2 (en) | 2005-01-18 | 2013-06-18 | Certicom Corp. | Accelerated verification of digital signatures and public keys |
| EP2395424B1 (en) | 2005-01-18 | 2013-07-31 | Certicom Corp. | Accelerated verification of digital signatures and public keys |
| US8027466B2 (en) | 2007-03-07 | 2011-09-27 | Research In Motion Limited | Power analysis attack countermeasure for the ECDSA |
| ATE527776T1 (en) * | 2007-03-06 | 2011-10-15 | Research In Motion Ltd | METHOD AND DEVICE FOR PERFORMING A SCALAR MULTIPLICATION ON AN ELLIPTICAL CURVE USING DIVISION |
| US8160245B2 (en) | 2007-03-07 | 2012-04-17 | Research In Motion Limited | Methods and apparatus for performing an elliptic curve scalar multiplication operation using splitting |
| US9123316B2 (en) | 2010-12-27 | 2015-09-01 | Microsoft Technology Licensing, Llc | Interactive content creation |
| US8745376B2 (en) | 2011-10-14 | 2014-06-03 | Certicom Corp. | Verifying implicit certificates and digital signatures |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2672402B1 (en) * | 1991-02-05 | 1995-01-27 | Gemplus Card Int | METHOD AND DEVICE FOR THE GENERATION OF UNIQUE PSEUDO-RANDOM NUMBERS. |
| US5991415A (en) * | 1997-05-12 | 1999-11-23 | Yeda Research And Development Co. Ltd. At The Weizmann Institute Of Science | Method and apparatus for protecting public key schemes from timing and fault attacks |
-
1999
- 1999-01-15 CA CA 2259089 patent/CA2259089C/en not_active Expired - Lifetime
-
2000
- 2000-01-14 AU AU30281/00A patent/AU3028100A/en not_active Abandoned
- 2000-01-14 WO PCT/CA2000/000030 patent/WO2000042733A1/en not_active Ceased
Also Published As
| Publication number | Publication date |
|---|---|
| CA2259089A1 (en) | 2000-07-15 |
| WO2000042733A1 (en) | 2000-07-20 |
| AU3028100A (en) | 2000-08-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7599491B2 (en) | Method for strengthening the implementation of ECDSA against power analysis | |
| US8666063B2 (en) | Method and apparatus for minimizing differential power attacks on processors | |
| US7899190B2 (en) | Security countermeasures for power analysis attacks | |
| CA2259089C (en) | Method and apparatus for masking cryptographic operations | |
| US7020281B2 (en) | Timing attack resistant cryptographic system | |
| US7864951B2 (en) | Scalar multiplication method with inherent countermeasures | |
| US20100254532A1 (en) | Method of obscuring cryptographic computations | |
| JP7123959B2 (en) | Elliptic curve point multiplication device and method | |
| JP2008252299A (en) | Cryptographic processing system and cryptographic processing method | |
| US7227947B2 (en) | Cryptographic method and cryptographic device | |
| EP3698262B1 (en) | Protecting modular inversion operation from external monitoring attacks | |
| EP2401734B1 (en) | System and method for performing exponentiation in a cryptographic system | |
| US11973866B2 (en) | Cryptographic processing method, related electronic device and computer program | |
| Smart | Physical side‐channel attacks on cryptographic systems | |
| US20050152539A1 (en) | Method of protecting cryptographic operations from side channel attacks | |
| KR100954844B1 (en) | Digital Signature Method Using the Crt-Rss Modular Exponential Algorithm Secure Against Error Injection Attacks, Apparatus and Recording Media Recording the Same | |
| KR20090080842A (en) | Digital Signature Method using Crt-Rssa Modular Exponential Algorithm, Apparatus and Its Computer-readable Storage Media Recording the Same | |
| Giraud et al. | Fault attacks on a cloud-assisted ECDSA white-box based on the residue number system | |
| EP2293488B1 (en) | Method for cryptographic processing of data units | |
| JP2024540262A (en) | White-box processing for encoding large integer values | |
| Shukla et al. | A Comparative analysis of the attacks on public key RSA cryptosystem | |
| Esau | Assignment 7/Data Security | |
| Qing-hua et al. | Applying two channels to vector space secret sharing based multi-signature scheme |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EEER | Examination request | ||
| MKEX | Expiry |
Effective date: 20190115 |