SYSTEM AND METHOD FOR PROVIDING DEFENCE TO A CRYPTOGRAPHIC DEVICE AGAINST SIDE-CHANNEL ATTACKS TARGETING THE EXTENDED EUCLIDEAN ALGORITHM DURING DECRYPTION OPERATIONS

Abstract

A system, method and computer-readable storage medium for decrypting a code c using a modified Extended Euclidean Algorithm (EEA) having an iteration loop independent of the Hamming weight of inputs to the EEA and performing a fixed number of operations regardless of the inputs to the EEA thereby protecting a cryptographic device performing the decryption from side-channel attacks.

Claims

1. A method for protecting a cryptography device performing decryption according to a specified encryption scheme, the decryption method using an Extended Euclidean Algorithm, the method protecting the cryptographic device against side-channel attack by decrypting a code using a modified Extended Euclidean Algorithm, the cryptography device comprising a processor and memory, the method comprising: receiving by the processor a code c, wherein c is a function of a key pair (having a public key and a secret key) and an error e; decrypting by the processor the code c by deriving the error e by: computing a polynomial syndrome S(z) which is a univariate polynomial deduced from c, but depending only on e, using a modified Extended Euclidean Algorithm having inputs a(z), b(z), and d, where a(z) and b(z) are polynomials and d is a public parameter of the encryption scheme to compute an error locator polynomial σ(z), by: iteratively performing a computation L a number of times defined by the parameter d, the computation L performing a fixed number of arithmetic operations regardless of Hamming weight of inputs a(z) and b(z), the arithmetic operations performing polynomial subtraction operations resulting in a result related to the result of a standard Extended Euclidean Algorithm, finding by the processor roots of σ(z); and inferring by the processor the error e from the roots of σ(z).

2. The method for protecting a cryptography device performing decryption using an Extended Euclidean Algorithm against side-channel attack of claim 1 wherein the modified Extended Euclidean Algorithm produces a result related to the Extended Euclidean Algorithm formulated as follows: Extended Euclidean Algorithm (EEA): TABLE-US-00009 Input:  a(z), b(z), deg(a) ≧ deg(b), d.sub.fin Output:  u(z), r(z) with b(z)u(z) = r(z)  mod a(z) and deg(r) ≦ d.sub.fin  1: r.sub.−1(z) ← a(z), r.sub.0(z) ← b(z),u.sub.−1(z) ← 1, u.sub.0(z) ← 0,  2: i ← 0  3: while deg(r.sub.i(z)) > d.sub.fin do  4:  i ← i + 1  5:  q.sub.i ← r.sub.i−2(z)/r.sub.i−1(z)  6:  r.sub.i ← r.sub.i−2(z) − q.sub.i(z)r.sub.i−1(z)  7:  u.sub.i ← u.sub.i−2(z) − q.sub.i(z)u.sub.i−1(z)  8: end while  9: N ← i 10: return u.sub.N(z), r.sub.N(z) wherein d.sub.fin=½ d, i.e., d.sub.fin equals to ½ the public parameter d of the encryption scheme, and the computation L is related to the while loop in the Extended Euclidean Algorithm such that polynomials u.sub.n(z) and r.sub.n(z) may be derived from the outputs of the modified Extended Euclidean Algorithm.

3. The method for protecting a cryptography device performing decryption using an Extended Euclidean Algorithm against side-channel attack of claim 2 wherein the operation L has the form: TABLE-US-00010     1: {circumflex over (R)}.sub.−1(z) ← a(z), {circumflex over (R)}.sub.0(z) ← zb(z),   2: .Math..sub.−1(z) ← 1, .Math..sub.0(z) ← 0, $\begin{array}{cc}.Math.3.Math.\text{:}& \delta \leftarrow -1.\\ .Math.4.Math.\text{:}& \mathrm{for}.Math..Math.j=1,\mathrm{.Math.}.Math.,d.Math..Math.\mathrm{do}\\ .Math.5.Math.\text{:}& .Math.{\alpha }_j\leftarrow {\hat{R}}_{j-1,d},{\beta }_j\leftarrow {\hat{R}}_{j-2,d}.\\ .Math.6.Math.\text{:}& .Math.{\mathrm{temp}}_R\left(z\right)\leftarrow z\left({\alpha }_j.Math.{\hat{R}}_{j-2}\left(z\right)-{\beta }_j.Math.{\hat{R}}_{j-1}\left(z\right)\right).\\ .Math.7.Math.\text{:}& .Math.{\mathrm{temp}}_U\left(z\right)\leftarrow z\left({\alpha }_j.Math.{\hat{U}}_{j-2}\left(z\right)-{\beta }_j.Math.{\hat{U}}_{j-1}\left(z\right)\right).\\ .Math.8.Math.\text{:}& .Math.\mathrm{if}.Math..Math.{\alpha }_j=0.Math..Math.\left(\mathrm{ie}.Math..Math.\mathrm{deg}\left({\hat{R}}_{j-1}\right)<\mathrm{deg}\left({\hat{R}}_{j-2}\right)\right).Math..Math.\mathrm{then}\\ .Math.9.Math.\text{:}& .Math.\delta \leftarrow \delta +1.\\ 10.Math.\text{:}& .Math.\mathrm{else}\\ 11.Math.\text{:}& .Math.\delta \leftarrow \delta -1.\\ 12.Math.\text{:}& .Math.\mathrm{end}.Math..Math.\mathrm{if}\\ 13.Math.\text{:}& .Math.\mathrm{if}.Math..Math.\delta <0.Math..Math.\mathrm{then}\\ 14.Math.\text{:}& .Math.\left({\hat{R}}_j\left(z\right),{\hat{R}}_{j-1}\left(z\right)\right)\leftarrow \left({\hat{R}}_{j-1}\left(z\right),{\mathrm{temp}}_R\right)\\ 15.Math.\text{:}& .Math.\left({\hat{U}}_j\left(z\right),{\hat{U}}_{j-1}\left(z\right)\right)\leftarrow \left({\hat{U}}_{j-1}\left(z\right),{\mathrm{temp}}_U\right)\\ 16.Math.\text{:}& .Math.\delta \leftarrow 0.\\ 17.Math.\text{:}& .Math.\mathrm{else}\\ 18.Math.\text{:}& .Math.\left({\hat{R}}_j\left(z\right),{\hat{R}}_{j-1}\left(z\right)\right)\leftarrow \left({\mathrm{temp}}_R,{\hat{R}}_{j-2}\left(z\right)\right)\\ 19.Math.\text{:}& .Math.\left({\hat{U}}_j\left(z\right),{\hat{U}}_{j-1}\left(z\right)\right)\leftarrow \left({\mathrm{temp}}_U,{\hat{U}}_{j-2}\left(z\right)\right)\\ 20.Math.\text{:}& .Math.\delta \leftarrow \delta .\\ 21.Math.\text{:}& .Math.\mathrm{end}.Math..Math.\mathrm{if}\\ 22.Math.\text{:}& \mathrm{end}.Math..Math.\mathrm{for}\end{array}\}.Math..Math.L$  23: return .Math..sub.d(z), {circumflex over (R)}.sub.d(z).

4. The method for protecting a cryptography device performing decryption using an Extended Euclidean Algorithm against side-channel attack of claim 3 wherein r.sub.N(z), and u.sub.N(z), are related to {circumflex over (R)}.sub.d (z) and .Math..sub.d(z) as follows:
{circumflex over (R)}.sub.d(z)=μz.sup.d−w(e)+1r.sub.N(z)
.Math..sub.d(z)=μz.sup.d−w(e)+1u.sub.N(z)

5. The method for protecting a cryptography device performing decryption using an Extended Euclidean Algorithm against side-channel attack of claim 1 wherein the EEA is used in an Alternant decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial a(z) is z.sup.2t and the polynomial b(z) is S(z), and d is 2t.s

6. The method for protecting a cryptography device performing decryption using an Extended Euclidean Algorithm against side-channel attack of claim 1 wherein the EEA is used in a Patterson algorithm decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial a(z) is g(z) and the polynomial b(z) is τ, d=t, τ=√{square root over (S(z).sup.−1+1)} mod g(z), and g(z) is a generator function from which the public key is generated.

7. A cryptographic device protected against side-channel attacks, comprising: a processor; a memory connected to the processor and comprising instructions executable by the processor, the instructions including instructions to cause the processor to: receiving by the processor a code c, wherein c is a function of a key pair (having a public key and a secret key) and an error e; decrypting by the processor the code c by deriving the error e by: computing a polynomial syndrome S(z) which is a univariate polynomial deduced from c, but depending only on e, using a modified Extended Euclidean Algorithm having inputs a(z), b(z), and d, where a(z) and b(z) are polynomials and d is a public parameter of the encryption scheme to compute an error locator polynomial σ(z), by: iteratively performing a computation L a number of times defined by the termination criteria d, the computation L performing a fixed number of arithmetic operations regardless of Hamming weight of inputs a(z) and b(z), the arithmetic operations performing polynomial subtraction operations resulting in a result related to the result of a standard Extended Euclidean Algorithm, finding by the processor roots of σ(z); and inferring by the processor the error e from the roots of σ(z).

8. The cryptographic device protected against side-channel attacks of claim 7 wherein the modified Extended Euclidean Algorithm produces a result related to the Extended Euclidean Algorithm formulated as follows: Extended Euclidean Algorithm (EEA): TABLE-US-00011 Input:  a(z), b(z), deg(a) ≧ deg(b), d.sub.fin Output:  u(z), r(z) with b(z)u(z) = r(z)  mod a(z) and deg(r) ≦ d.sub.fin  1: r.sub.−1(z) ← a(z), r.sub.0(z) ← b(z),u.sub.−1(z) ← 1, u.sub.0(z) ← 0,  2: i ← 0  3: while deg(r.sub.i(z)) > d.sub.fin do  4:  i ← i + 1  5:  q.sub.i ← r.sub.i−2(z)/r.sub.i−1(z)  6:  r.sub.i ← r.sub.i−2(z) − q.sub.i(z)r.sub.i−1(z)  7:  u.sub.i ← u.sub.i−2(z) − q.sub.i(z)u.sub.i−1(z)  8: end while  9: N ← i 10: return u.sub.N(z), r.sub.N(z) and the computation L is related to the while loop in the Extended Euclidean Algorithm such that polynomials u.sub.n(z) and r.sub.n(z) may be derived from the outputs of the modified Extended Euclidean Algorithm.

9. The cryptographic device protected against side-channel attacks of claim 8 wherein the operation L has the form: TABLE-US-00012     1: {circumflex over (R)}.sub.−1(z) ← a(z), {circumflex over (R)}.sub.0(z) ← zb(z),   2: .Math..sub.−1(z) ← 1, .Math..sub.0(z) ← 0, $\begin{array}{cc}.Math.3.Math.\text{:}& \delta \leftarrow -1.\\ .Math.4.Math.\text{:}& \mathrm{for}.Math..Math.j=1,\mathrm{.Math.}.Math.,d.Math..Math.\mathrm{do}\\ .Math.5.Math.\text{:}& .Math.{\alpha }_j\leftarrow {\hat{R}}_{j-1,d},{\beta }_j\leftarrow {\hat{R}}_{j-2,d}.\\ .Math.6.Math.\text{:}& .Math.{\mathrm{temp}}_R\left(z\right)\leftarrow z\left({\alpha }_j.Math.{\hat{R}}_{j-2}\left(z\right)-{\beta }_j.Math.{\hat{R}}_{j-1}\left(z\right)\right).\\ .Math.7.Math.\text{:}& .Math.{\mathrm{temp}}_U\left(z\right)\leftarrow z\left({\alpha }_j.Math.{\hat{U}}_{j-2}\left(z\right)-{\beta }_j.Math.{\hat{U}}_{j-1}\left(z\right)\right).\\ .Math.8.Math.\text{:}& .Math.\mathrm{if}.Math..Math.{\alpha }_j=0.Math..Math.\left(\mathrm{ie}.Math..Math.\mathrm{deg}\left({\hat{R}}_{j-1}\right)<\mathrm{deg}\left({\hat{R}}_{j-2}\right)\right).Math..Math.\mathrm{then}\\ .Math.9.Math.\text{:}& .Math.\delta \leftarrow \delta +1.\\ 10.Math.\text{:}& .Math.\mathrm{else}\\ 11.Math.\text{:}& .Math.\delta \leftarrow \delta -1.\\ 12.Math.\text{:}& .Math.\mathrm{end}.Math..Math.\mathrm{if}\\ 13.Math.\text{:}& .Math.\mathrm{if}.Math..Math.\delta <0.Math..Math.\mathrm{then}\\ 14.Math.\text{:}& .Math.\left({\hat{R}}_j\left(z\right),{\hat{R}}_{j-1}\left(z\right)\right)\leftarrow \left({\hat{R}}_{j-1}\left(z\right),{\mathrm{temp}}_R\right)\\ 15.Math.\text{:}& .Math.\left({\hat{U}}_j\left(z\right),{\hat{U}}_{j-1}\left(z\right)\right)\leftarrow \left({\hat{U}}_{j-1}\left(z\right),{\mathrm{temp}}_U\right)\\ 16.Math.\text{:}& .Math.\delta \leftarrow 0.\\ 17.Math.\text{:}& .Math.\mathrm{else}\\ 18.Math.\text{:}& .Math.\left({\hat{R}}_j\left(z\right),{\hat{R}}_{j-1}\left(z\right)\right)\leftarrow \left({\mathrm{temp}}_R,{\hat{R}}_{j-2}\left(z\right)\right)\\ 19.Math.\text{:}& .Math.\left({\hat{U}}_j\left(z\right),{\hat{U}}_{j-1}\left(z\right)\right)\leftarrow \left({\mathrm{temp}}_U,{\hat{U}}_{j-2}\left(z\right)\right)\\ 20.Math.\text{:}& .Math.\delta \leftarrow \delta .\\ 21.Math.\text{:}& .Math.\mathrm{end}.Math..Math.\mathrm{if}\\ 22.Math.\text{:}& \mathrm{end}.Math..Math.\mathrm{for}\end{array}\}.Math..Math.L$  23: return .Math..sub.d(z), {circumflex over (R)}.sub.d(z).

10. The cryptographic device protected against side-channel attacks of claim 8 wherein r.sub.n(z), and u.sub.n(z), are related to {circumflex over (R)}.sub.d(z) and .Math..sub.d(z) as follows:
{circumflex over (R)}.sub.d(z)=μz.sup.d−w(e)+1r.sub.N(z)
.Math..sub.d(z)=μz.sup.d−w(e)+1u.sub.N(z)

11. The cryptographic device protected against side-channel attacks of claim 7 wherein the EEA is used in an Alternant decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial σ(z) is z.sup.2t, the polynomial b(z) is S(z), and d is 2t.

12. The cryptographic device protected against side-channel attacks of claim 7 wherein the EEA is used in a Patterson algorithm decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial a(z) is g(z) and the polynomial b(z) is τ, d is t, √{square root over (τ=S(z).sup.−1+1)} mod g(z), and g(z) is a generator function from which the public key is generated.

13. The cryptographic device protected against side-channel attacks of claim 7 wherein the cryptographic device is a smart card.

14. The cryptographic device protected against side-channel attacks of claim 7 wherein the cryptographic device is a mobile device.

15. A computer readable storage medium storing instructions operable to cause a processor of a cryptographic device, when loaded onto and executed by the processor of the cryptographic device, to: receive a code c, wherein c is a function of a key pair (having a public key and a secret key) and an error e; decrypt the code c by deriving the error e by: computing a polynomial syndrome S(z) which is a univariate polynomial deduced from c, but depending only on e, using a modified Extended Euclidean Algorithm having inputs a(z), b(z), and d, where a(z) and b(z) are polynomials and d is a public parameter of the encryption scheme to compute an error locator polynomial σ(z), by: iteratively performing a computation L a number of times defined by the termination criteria d, the computation L performing a fixed number of arithmetic operations regardless of Hamming weight of inputs a(z) and b(z), the arithmetic operations performing polynomial subtraction operations resulting in a result related to the result of a standard Extended Euclidean Algorithm, finding by the processor roots of σ(z); and inferring by the processor the error e from the roots of σ(z).

16. The computer readable storage medium of claim 15 wherein the modified Extended Euclidean Algorithm produces a result related to the Extended Euclidean Algorithm formulated as follows: Extended Euclidean Algorithm (EEA): TABLE-US-00013 Input:  a(z), b(z), deg(a) ≧ deg(b), d.sub.fin Output:  u(z), r(z) with b(z)u(z) = r(z)  mod a(z) and deg(r) ≦ d.sub.fin  1: r.sub.−1(z) ← a(z), r.sub.0(z) ← b(z),u.sub.−1(z) ← 1, u.sub.0(z) ← 0,  2: i ← 0  3: while deg(r.sub.i(z)) > d.sub.fin do  4:  i ← i + 1  5:  q.sub.i ← r.sub.i−2(z)/r.sub.i−1(z)  6:  r.sub.i ← r.sub.i−2(z) − q.sub.i(z)r.sub.i−1(z)  7:  u.sub.i ← u.sub.i−2(z) − q.sub.i(z)u.sub.i−1(z)  8: end while  9: N ← i 10: return u.sub.N(z), r.sub.N(z) and the computation L is equivalent to the while loop in the Extended Euclidean Algorithm such that polynomials u.sub.n (z) and r.sub.n(z) may be derived from the outputs of the modified Extended Euclidean Algorithm.

17. The computer readable storage medium of claim 16 wherein the operation L has the form: TABLE-US-00014     1: {circumflex over (R)}.sub.−1(z) ← a(z), {circumflex over (R)}.sub.0(z) ← zb(z),   2: .Math..sub.−1(z) ← 1, .Math..sub.0(z) ← 0, $\begin{array}{cc}.Math.3.Math.\text{:}& \delta \leftarrow -1.\\ .Math.4.Math.\text{:}& \mathrm{for}.Math..Math.j=1,\mathrm{.Math.}.Math.,d.Math..Math.\mathrm{do}\\ .Math.5.Math.\text{:}& .Math.{\alpha }_j\leftarrow {\hat{R}}_{j-1,d},{\beta }_j\leftarrow {\hat{R}}_{j-2,d}.\\ .Math.6.Math.\text{:}& .Math.{\mathrm{temp}}_R\left(z\right)\leftarrow z\left({\alpha }_j.Math.{\hat{R}}_{j-2}\left(z\right)-{\beta }_j.Math.{\hat{R}}_{j-1}\left(z\right)\right).\\ .Math.7.Math.\text{:}& .Math.{\mathrm{temp}}_U\left(z\right)\leftarrow z\left({\alpha }_j.Math.{\hat{U}}_{j-2}\left(z\right)-{\beta }_j.Math.{\hat{U}}_{j-1}\left(z\right)\right).\\ .Math.8.Math.\text{:}& .Math.\mathrm{if}.Math..Math.{\alpha }_j=0.Math..Math.\left(\mathrm{ie}.Math..Math.\mathrm{deg}\left({\hat{R}}_{j-1}\right)<\mathrm{deg}\left({\hat{R}}_{j-2}\right)\right).Math..Math.\mathrm{then}\\ .Math.9.Math.\text{:}& .Math.\delta \leftarrow \delta +1.\\ 10.Math.\text{:}& .Math.\mathrm{else}\\ 11.Math.\text{:}& .Math.\delta \leftarrow \delta -1.\\ 12.Math.\text{:}& .Math.\mathrm{end}.Math..Math.\mathrm{if}\\ 13.Math.\text{:}& .Math.\mathrm{if}.Math..Math.\delta <0.Math..Math.\mathrm{then}\\ 14.Math.\text{:}& .Math.\left({\hat{R}}_j\left(z\right),{\hat{R}}_{j-1}\left(z\right)\right)\leftarrow \left({\hat{R}}_{j-1}\left(z\right),{\mathrm{temp}}_R\right)\\ 15.Math.\text{:}& .Math.\left({\hat{U}}_j\left(z\right),{\hat{U}}_{j-1}\left(z\right)\right)\leftarrow \left({\hat{U}}_{j-1}\left(z\right),{\mathrm{temp}}_U\right)\\ 16.Math.\text{:}& .Math.\delta \leftarrow 0.\\ 17.Math.\text{:}& .Math.\mathrm{else}\\ 18.Math.\text{:}& .Math.\left({\hat{R}}_j\left(z\right),{\hat{R}}_{j-1}\left(z\right)\right)\leftarrow \left({\mathrm{temp}}_R,{\hat{R}}_{j-2}\left(z\right)\right)\\ 19.Math.\text{:}& .Math.\left({\hat{U}}_j\left(z\right),{\hat{U}}_{j-1}\left(z\right)\right)\leftarrow \left({\mathrm{temp}}_U,{\hat{U}}_{j-2}\left(z\right)\right)\\ 20.Math.\text{:}& .Math.\delta \leftarrow \delta .\\ 21.Math.\text{:}& .Math.\mathrm{end}.Math..Math.\mathrm{if}\\ 22.Math.\text{:}& \mathrm{end}.Math..Math.\mathrm{for}\end{array}\}.Math..Math.L$  23: return .Math..sub.d(z), {circumflex over (R)}.sub.d(z).

18. The computer readable storage medium of claim 16 wherein r.sub.n(z), and u.sub.n(z), are related to {circumflex over (R)}.sub.d (z) and .Math..sub.d (z) as follows:
{circumflex over (R)}.sub.d(z)=μz.sup.d−w(e)+1r.sub.N(z)
.Math..sub.d(z)=μz.sup.d−w(e)+1u.sub.N(z)

19. The computer readable storage medium of claim 15 wherein the EEA is used in an Alternant decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial a(z) is z.sup.2t, the polynomial b(z) is S(z), and d=2t.

20. The computer readable storage medium of claim 15 wherein the EEA is used in a Patterson algorithm decoder and the EEA is used to compute the error locator polynomial σ(z), wherein the polynomial a(z) is g(z) and the polynomial b(z) is τ; d is t and wherein τ=√{square root over (S(z).sup.−1+1)} mod g(z) and g(z) is a generator function from which the public key is generated.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0019] FIG. 1 is a schematic illustration of a host computer with a portable security device, e.g., a smart card, connected thereto for performing cryptographic services through connection over a network to one or more servers.

[0020] FIG. 2 is a schematic illustration of a portable security device.

[0021] FIG. 3 is a schematic illustration of programs stored in a memory of the portable security device of FIG. 2.

[0022] FIG. 4 is a schematic illustration illustrating the encryption and corresponding decryption of a message according to the McEliece cryptography system.

[0023] FIG. 5 illustrates the steps involved in decrypting a message encrypted using the McEliece cryptography system.

[0024] FIG. 6 is a pseudocode section illustrating the standard method for performing an Extended Euclidean Algorithm as may be employed in decryption of a message in the McEliece cryptography system

[0025] FIG. 7 is a pseudocode section illustrating a modified Extended Euclidean Algorithm (EEA) that when employed by a cryptography device implementing the McEliece cryptography system renders the cryptography device less prone to side-channel attack targeting the EEA.

DETAILED DESCRIPTION OF THE INVENTION

[0026] In the following detailed description, reference is made to the accompanying drawings that show, by way of illustration, specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention. It is to be understood that the various embodiments of the invention, although different, are not necessarily mutually exclusive. For example, a particular feature, structure, or characteristic described herein in connection with one embodiment may be implemented within other embodiments without departing from the spirit and scope of the invention. In addition, it is to be understood that the location or arrangement of individual elements within each disclosed embodiment may be modified without departing from the spirit and scope of the invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims, appropriately interpreted, along with the full range of equivalents to which the claims are entitled. In the drawings, like numerals refer to the same or similar functionality throughout the several views.

[0027] In an embodiment of the invention, a technology is provided that enables the use of smart cards, or other portable security devices, to be used to digitally sign documents or to decrypt encrypted documents or messages using private keys stored on the smart cards in a manner that efficiently reduces the risk of differential power analysis attacks.

[0028] Smart cards are plastic cards with an embedded microprocessor and a secure storage. They are portable, secure, and tamper-resistant. Smart cards provide security services in many domains including telecommunication, banking, commerce, and citizen identity. Smart cards can take different forms, such as credit card shaped cards with electrical connectors to connect the smart card to a smart card reader, USB tokens with embedded smart cards, and SIM cards for use in mobile telephones and tablet devices. Smart cards are used herein as examples of portable security devices that may be used in implementations of the technology described herein. Other examples of portable security devices include smart memory cards, flash memory, etc. In a preferred embodiment, the portable security device has a processor, a memory for storing programs and data, and some security features to make the device relatively tamper-proof. Smart cards are used herein as examples of such devices.

[0029] While the mechanism for masking a cryptographic calculation described herein may be used advantageously in smart cards and other portable security tokens used for performing cryptographic calculations, the same mechanisms may also be used with other cryptographic processors. Thus, smart cards are used herein for illustrative purposes only.

[0030] Cryptographic operations, such as encryption and decryption, are examples of functions that smart cards provide. The smart card stores private or shared secret keys in its secure storage and performs cryptographic operations to generate a digital signature for a given input or to decrypt a given input. A smart card works with a host device, such as a personal computer (PC), cell phone, tablet device or banking terminal. A PC application, such as an email client or a web browser, typically works with a smart card to sign, encrypt, or decrypt a document. The cryptographic operation may be part of a challenge-response mechanism for user authentication. The PC application and the smart card interact through some cryptographic API called middleware, which is designed to communicate with the smart card. In this scenario, the smart card provides services locally to the PC.

[0031] FIG. 1 is a schematic illustration of a network 111 connecting a host computer 103 with a portable security device 109, e.g., a smart card, connected thereto, to one or more remote servers 113. The host computer 103 is operated by a user 101 who interacts with one of the servers 113 via a web browser window 105 of a web browser. In the example scenario illustrated in FIG. 1, the smart card 109 provides the cryptographic operations on behalf of the user 101, e.g., to cryptographically sign documents, to decrypt messages received from the relying party 113, or to perform a cryptographic operation as part of a challenge-response authentication mechanism.

[0032] While FIG. 1 provides an illustration of a scenario in which cryptography may play an important role, there are many other important uses for cryptography. Thus, the technology described herein is not limited in its application to the example of use, which is illustrated in FIG. 1.

[0033] FIG. 2 is a schematic illustration of a portable security device 109, for example, a smart card. The portable security device 109 may include a processor 201 connected via a bus 202 to a random access memory (RAM) 203, a read-only memory (ROM) 204, and a non-volatile memory (NVM) 205. The portable security device 109 further includes an input/output interface 207 for connecting the processor 201, again typically via the bus 202, to a connector 211 by which the portable security device 109 may be connected to the host computer 103.

[0034] In alternative embodiments, the connection between the host computer 103 and the portable security device 109 is wireless, for example, using near-field communication (NFC) or other radio or microwave communication technologies.

[0035] The NVM 205 and/or ROM 204 may include computer programs 301 as is illustrated in FIG. 3. While it is here depicted that the computer programs 301 are all co-located in the ROM 204 or the NVM 205, in actual practice there is no such restriction as programs may be spread out over multiple memories and even temporarily installed in RAM 203. Furthermore, the portable security device 109 may include multiple ROMs or NVMs. The programs 301 include operating system programs as well as application programs loaded onto the portable security device 109. The NVM 205 or ROM 204 may also contain private data, such as a private key 209 or a shared secret key 210, stored either in its basic form or in derived quantities.

[0036] The portable security device 109 programs 301 may include a cryptography module 213, a user authentication module 215, a communications module 217, and the operating system OS 219.

[0037] Thus, the portable security device 109 may receive a document or message via the connector 211. The processor 201, by executing instructions of the cryptography module 213, may digitally sign the document/message or may decrypt the document/message using the private key 209 or shared secret key 210. Using functionality provided through the communications module 217, the processor 201 may receive and transmit communications with the host computer 103.

[0038] The technology presented herein is useful for protecting cryptographic devices that employ the Extended Euclidean Algorithm during decryption operations of messages encrypted using cryptography systems based on coding theory, for example, in the manner of the McEliece cryptosystem. The primary purpose of coding theory is not the encryption of message. Rather, it is useful in transmitting messages accurately over communications channel that are not 100% perfect. In summary, a message may be encoded in such a way that even if the message is not received perfectly, the recipient may decode the message. Additional information is attached to each message that allows a recipient to correct a message if some of the bits are incorrectly received. One example of such an error-correcting coding system used for cryptography is the McEliece coding system introduced in 1978 [McEliece]. The McEliece cryptosystem is described very well in [Au] and in [Georgieva].

[0039] FIG. 4 is a flow-chart illustrating flow from the encryption of a plaintext message m into a code c followed by the decryption of the code c back into the plaintext message m, for example, using the McEliece cryptosystem.

[0040] Algorithm 1, below, describes the McEliece cryptosystem instantiated with a binary Goppa code, i.e., q=2. (Details of the McEliece cryptosystem are beyond the scope of this document; the reader is referred to [McEliece], [Georgieva] and [Au] for additional description.) The public key is G, a k×n matrix over a field .sub.q of size q whose rows generate a Goppa code of length n and dimension k. G is described by secret elements Xε.sub.q.sub.m.sup.n and a polynomial g(z) ε.sub.q.sub.m[z] of degree t wherein m and t are parameters such that n−mt≦0.

TABLE-US-00001 Algorithm 1 McEliece Cryptosystem PARAMETERS : Field size q, code length n and dimension k, parameters m,i such that n − mt ≦ 0. Plaintext space:    .sub.q.sup.k. Ciphertext space:   .sub.q.sup.m. KEYGEN : Pick a support x ∈   .sub.q.sup.m.sup.n, a polynominal g ∈   .sub.q.sup.m(x) of degree t, G a generator matrix of   (x,g), PUBLIC KEY : G.sub.pub = SGP, t the correction capacity of the code  (x,g). PRIVATE KEY : T.sub.i a t-decoder for   (x,g) , S a random full rank (n − k) × (n − k) matrix , P a random n × n permutation matrix. ENCRYPT : DECRYPT :  1: Input m ∈   .sub.q.sup.k.  1: Input c ∈   .sub.q.sup.n.  2: Generate random e ∈   .sub.q.sup.n with  2: Compute {circumflex over (m)} = T.sub.i(cP.sup.−1)),   w.sub.H(e) = t.  3: If decoding succeeds, output S.sup.−1 {circumflex over (m)}, else  3: Output c = mG.sub.pub + e.   output ⊥.

[0041] In a key generation step 401, a public key G.sub.pub is generated. The public key G.sub.pub is generated from a random full rank (n−k)×(n−k) matrix S, a random n×n permutation matrix and a generator matrix of g(x, g), such that G.sub.pub=SGP. The corresponding private key is T.sub.t a t-decoder for g(x, g), S, and P.

[0042] A plaintext message m 403ε.sub.q.sup.k is encrypted, step 405, by generating a random error e ε.sub.q.sup.k having a Hamming weight t. The output encrypted message 408 cε.sub.q.sup.n has the value c=mG.sub.pub+e.

[0043] The encrypted message c 408 is transmitted over a transmission channel, e.g., a network 407, to a recipient. The “transmission” may be the storage of the encrypted message c in a storage medium where the recipient may retrieve it, e.g., on a portable security device 109, which may be a mass storage device or a smart card, for example.

[0044] Decrypting, step 409, the message c 408 back into a plaintext message 411 is illustrated in FIG. 5.

[0045] A cryptographic device, e.g., the portable security device 109, receives or retrieves the encrypted message c 408. A decryption module 501 of the cryptography module 213 decrypts the message c 408. There are several possible decoders T.sub.t for a binary Goppa code. Suppose one wants to decode an encoded message mε.sub.q.sup.k with errors e: c=mG+e, where the Hamming weight of e (denoted herein as w.sub.H(e)) satisfies w.sub.H≦t. e may be written as

e=( . . . ,0,e.sub.i.sub.1,0, . . . ,0,e.sub.i.sub.1w,0, . . . ).

[0046] There are several approaches to decrypting a message c 408 that has been encrypted using the McEliece cryptography system. One such method uses the fact that Goppa codes belong to the larger class of alternant codes. That method is referred to herein as the Alternant Decoder. Another one, called the Patterson Algorithm is specific to binary Goppa codes. Common to both are the following high-level steps: [0047] Compute a polynomial syndrome S(z), Step 503. S(z) is a univariate polynomial deduced from c, but depending solely on e. [0048] Use the Extended Euclidean Algorithm (EEA) to compute an error locator polynomial σ(z), Step 505. The roots of the error locator polynomial σ(z) are related to the support elements x.sub.ij in the error positions ij. [0049] Determine the roots of σ(z) and deduce the error e therefrom. Step 507. eε.sub.2.sup.n from which it follows that e.sub.ij≠0 implies that e.sub.ij=1.

[0050] The polynomial syndromes, key equations and their resolutions are specific to each method. Table I, below, summarize for the Alternant Decoder and the Patterson Decoder:

TABLE-US-00002 TABLE I Alternant Decoder and Patterson Decoder Alternant Decoder Patterson Decoder Polynomial syndrome Polynominal syndrome [00001]$S_{\mathrm{Alt},e}\left(z\right)={.Math.}_{=0}^{2.Math.t-1}.Math.\left({.Math.}_{i=0}^{n-1}.Math.c_i.Math.{g\left(x_i\right)}^{-2}.Math.x_i^{}\right).Math.z^{}.$ [00002]$S_{\mathrm{Gop},e}\left(z\right)={.Math.}_{i=0}^{n-1}.Math.\frac{c_i}{z-x_i}.Math..Math.\mathrm{mod}.Math..Math.g\left(z\right).$ Polynomials to be recovered Polynomials to be recovered [00003]${\sigma }_{\mathrm{inv},e}\left(z\right)=\underset{j=1}{\overset{w}{.Math.}}.Math.\left(1-{\mathrm{zx}}_{i_j}\right),.Math.{\omega }_{\mathrm{inv},e}\left(z\right)=\underset{j=1}{\overset{w}{.Math.}}.Math.e_{i_j}.Math.{g\left(x_{i_j}\right)}^{-1}.Math.\underset{\underset{s\ne j}{s=1}}{\overset{w}{.Math.}}.Math.\left(1-{\mathrm{zx}}_{i_s}\right).$ [00004]${\sigma }_e\left(z\right)=\underset{j=1}{\overset{w}{.Math.}}.Math.\left(z-x_{i_j}\right),.Math.{\omega }_e\left(z\right)=\underset{j=1}{\overset{w}{.Math.}}.Math.\underset{\underset{s\ne j}{s=1}}{\overset{w}{.Math.}}.Math.\left(z-x_{i_s}\right)..Math.$ Key equation Key equation (σ.sub.inv,e , ω.sub.inv,e) unique solution of (σ.sub.1, σ.sub.2) unique solution of [00005]$\hspace{1em}\{\begin{array}{c}{\omega }_{\mathrm{inv},e}\left(z\right)={\sigma }_{\mathrm{inv}}\left(z\right).Math.S_{\mathrm{Alt},e}\left(z\right).Math..Math.\mathrm{mod}.Math..Math.z^{2.Math.t},\\ \mathrm{deg}\left({\sigma }_{\mathrm{inv}}\right).Math.t/2.Math.,\mathrm{deg}\left({\omega }_{\mathrm{inv}}\right)<.Math.t/2.Math..\end{array}$ [00006]$\hspace{1em}\{\begin{array}{c}\tau \left(z\right).Math.{\sigma }_2\left(z\right)={\sigma }_1\left(z\right).Math..Math.\mathrm{mod}.Math..Math.g\left(z\right),\\ \mathrm{deg}\left({\sigma }_1\right).Math.t/2.Math.,\mathrm{deg}\left({\sigma }_2\right)<.Math.t/2.Math.,\end{array}.Math..Math.\tau \left(z\right)=\sqrt{{S_{\mathrm{Gop},e}\left(z\right)}^{-1}+z}.Math..Math.\mathrm{mod}.Math..Math.g\left(z\right).$ Resolution Resolution EEA(z.sup.2t, S.sub.Alt,e, t) outputs 1. EEA(g(z), S.sub.Gop,.sub.e(z), 0) (μσ.sub.inv, (−1).sup.N μω.sub.inv), μ ∈   , N   0. outputs (S.sub.Gop,e.sup.-1 mod g), 2. EEA(g(z), τ, └t/2┘) outputs (σ.sub.1, σ.sub.2). Error recovery Error recovery σ.sub.e(z) = z.sup.wσ.sub.inv(1/z). σ.sub.e(z) = σ.sub.1(z).sup.2 + zσ.sub.2(z).sup.2, Find the roots of σ.sub.e. ω.sub.e = σ.sub.eS.sub.e mod g. Find the roots of σ.sub.e.

[0051] Thus, in both the Alternate Decoder and in the Patterson Algorithm, the Extended Euclidean Algorithm plays an important role in determining the error e.

[0052] FIG. 6 is a pseudo code 601 of the standard Extended Euclidean Algorithm, also set forth in Table II, below:

TABLE-US-00003 TABLE II Standard Extended Euclidean Algorithm Input:  a(z), b(z), deg(a) ≧ deg(b), d.sub.fin Output:  u(z), r(z) with b(z)u(z) = r(z)  mod a(z) and deg(r) ≦ d.sub.fin  1: r.sub.−1(z) ← a(z), r.sub.0(z) ← b(z),u.sub.−1(z) ← 1, u.sub.0(z) ← 0,  2: i ← 0  3: while deg(r.sub.i(z)) > d.sub.fin do  4:  i ← i + 1  5:  q.sub.i ← r.sub.i−2(z)/r.sub.i−1(z)  6:  r.sub.i ← r.sub.i−2(z) − q.sub.i(z)r.sub.i−1(z)  7:  u.sub.i ← u.sub.i−2(z) − q.sub.i(z)u.sub.i−1(z)  8: end while  9: N ← i 10: return u.sub.N(z), r.sub.N(z)

[0053] Inputs to the Extended Euclidean Algorithm (EEA) are the polynomials a(z), b(z), where deg(a)≧deg (b), and d.sub.fin, the polynomial degree at which a particular invocation of the EEA terminates.

[0054] Generally speaking, the EEA produces two polynomials u(z) and r(z) such that b(z)u(z)=r(z) mod a(z) with the deg(r)≦d.sub.fin.

[0055] It should be noted that in the standard EEA consists of a while loop in which successive polynomial divisions are performed. The number of iterations of the while loop depends on the inputs a(z) and b(z). Furthermore, the complexity of the EEA is (deg(a).sup.2). For these reasons, the standard form EEA, with a while loop as in Table II, is an attractive target for side-channel attack, because implicit in the above is that decryption is strongly influenced by the error vector.

[0056] According to a preferred embodiment, the EEA is performed using an algorithm that avoids the potential of side-channel leakages due to computation flow dependent on the inputs a(z) and b(z). FIG. 7 and Table III present a pseudocode 701 for such an algorithm.

TABLE-US-00004 TABLE III An Extended Euclidean Algorithm with execution flow independent of input polynomials Input: a(z) = z.sup.2t, b(z) = S.sub.e(z), d = 2t Output: .Math..sub.d(z) = μz.sup.d−w.sup.U.sup.(e)+1 σ.sub.inv(z), {circumflex over (R)}.sub.d(z) = μz.sup.d−w.sup.U.sup.(e)+1 ω.sub.e(z) for some μ ∈  .sub.q.sub.m*.   1: {circumflex over (R)}.sub.−1(z) ← a(z), {circumflex over (R)}.sub.0(z) ← zb(z),   2: .Math..sub.−1(z) ← 1, .Math..sub.0(z) ← 0, [00007]$\begin{array}{cc}.Math.3.Math.\text{:}& \delta \leftarrow -1.\\ .Math.4.Math.\text{:}& \mathrm{for}.Math..Math.j=1,\mathrm{.Math.}.Math.,d.Math..Math.\mathrm{do}\\ .Math.5.Math.\text{:}& .Math.{\alpha }_j\leftarrow {\hat{R}}_{j-1,d},{\beta }_j\leftarrow {\hat{R}}_{j-2,d}.\\ .Math.6.Math.\text{:}& .Math.{\mathrm{temp}}_R\left(z\right)\leftarrow z\left({\alpha }_j.Math.{\hat{R}}_{j-2}\left(z\right)-{\beta }_j.Math.{\hat{R}}_{j-1}\left(z\right)\right).\\ .Math.7.Math.\text{:}& .Math.{\mathrm{temp}}_U\left(z\right)\leftarrow z\left({\alpha }_j.Math.{\hat{U}}_{j-2}\left(z\right)-{\beta }_j.Math.{\hat{U}}_{j-1}\left(z\right)\right).\\ .Math.8.Math.\text{:}& .Math.\mathrm{if}.Math..Math.{\alpha }_j=0.Math..Math.\left(\mathrm{ie}.Math..Math.\mathrm{deg}\left({\hat{R}}_{j-1}\right)<\mathrm{deg}\left({\hat{R}}_{j-2}\right)\right).Math..Math.\mathrm{then}\\ .Math.9.Math.\text{:}& .Math.\delta \leftarrow \delta +1.\\ 10.Math.\text{:}& .Math.\mathrm{else}\\ 11.Math.\text{:}& .Math.\delta \leftarrow \delta -1.\\ 12.Math.\text{:}& .Math.\mathrm{end}.Math..Math.\mathrm{if}\\ 13.Math.\text{:}& .Math.\mathrm{if}.Math..Math.\delta <0.Math..Math.\mathrm{then}\\ 14.Math.\text{:}& .Math.\left({\hat{R}}_j\left(z\right),{\hat{R}}_{j-1}\left(z\right)\right)\leftarrow \left({\hat{R}}_{j-1}\left(z\right),{\mathrm{temp}}_R\right)\\ 15.Math.\text{:}& .Math.\left({\hat{U}}_j\left(z\right),{\hat{U}}_{j-1}\left(z\right)\right)\leftarrow \left({\hat{U}}_{j-1}\left(z\right),{\mathrm{temp}}_U\right)\\ 16.Math.\text{:}& .Math.\delta \leftarrow 0.\\ 17.Math.\text{:}& .Math.\mathrm{else}\\ 18.Math.\text{:}& .Math.\left({\hat{R}}_j\left(z\right),{\hat{R}}_{j-1}\left(z\right)\right)\leftarrow \left({\mathrm{temp}}_R,{\hat{R}}_{j-2}\left(z\right)\right)\\ 19.Math.\text{:}& .Math.\left({\hat{U}}_j\left(z\right),{\hat{U}}_{j-1}\left(z\right)\right)\leftarrow \left({\mathrm{temp}}_U,{\hat{U}}_{j-2}\left(z\right)\right)\\ 20.Math.\text{:}& .Math.\delta \leftarrow \delta .\\ 21.Math.\text{:}& .Math.\mathrm{end}.Math..Math.\mathrm{if}\\ 22.Math.\text{:}& \mathrm{end}.Math..Math.\mathrm{for}\end{array}\}.Math..Math.L$  23: return .Math..sub.d(z), {circumflex over (R)}.sub.d(z)

[0057] In the EEA with regular execution flow as illustrated in FIG. 7 (Table III), the while loop from the standard EEA of FIG. 6 (Table II) has been replaced with a for loop that depends solely on the degree of the higher degree input polynomial. Furthermore, regardless of input, the same number and kind of operations are performed. Therefore, the regular flow EEA is less prone to side-channel attack.

[0058] As with the standard EEA algorithm (FIG. 6), the modified regular flow EEA algorithm (FIG. 7) accepts three inputs, a first polynomial σ(z), a second polynomial b(z), and an iteration parameter d. The parameter d is a publically known parameter for the underlying decryption scheme. For example, for the alternant decoder for McEliece codes, the parameter d is 2t. Conversely, for the second EEA computation for the Patterson algorithm, the parameter d is [t/2].

[0059] In the pseudocode of FIG. 7 (and Table III), the regular flow EEA is adapted for the Alternant Decoder. Thus, the first input polynomial is z.sup.2t and the corresponding termination parameter d is set to 2t, i.e., 2t is the number of iterations in the for loop as compared to in the standard EEA, in which the max number of executions of the while loop is 2t. The second input polynomial is the polynomial syndrome S.sub.e (z) corresponding to the code c, i.e.,

S.sub.e(z)=Σ.sub.l=0.sup.2t-1(Σ.sub.i=0.sup.n-1c.sub.ig(x.sub.i).sup.−2x.sub.i.sup.l)z.sup.l.

[0060] The for loop is executed 2t times, regardless of the weight of either input polynomial and, thus, is not dependent on the weight of the input polynomials whereas for the standard EEA with a while loop the number of executions of the while loop depends on the inputs a(z) and b(z).

[0061] The modified EEA of FIG. 7 may also be used for the second EEA computation of the Patterson algorithm, i.e.,

[00008]$\mathrm{EEA}\left(\left(z\right),\tau ,.Math.\frac{t}{2}.Math.\right).$

[0062] The section below entitled Derivation of the Regular Flow EEA illustrates the derivation of the regular flow EEA from the standard EEA and that it is analogous to the standard EEA. As noted there, the output from the standard EEA and the regular flow EEA are related as follows, for some με.sub.q.sub.m*:

{circumflex over (R)}.sub.d(z)=μz.sup.d−w(e)+1r.sub.N(z)

.Math..sub.d(z)=μz.sup.d−w(e)+1u.sub.N(z)

where w(e) is the Hamming weight of the error e. The above relationship between the outputs of the regular flow EEA of FIG. 7 and the standard EEA is proved in [Georgieva], incorporated herein by reference.

[0063] The coefficient μ exists, which is a fact that is sufficient to proceed with the McEliece decryption using the Alternant Decoder or for the second EEA computation of the Patterson Algorithm because these decoders are only concerned by the roots of the error locator polynomial σ.sub.e(z) (and the roots of the output of EEA may be used to determine the roots of the error locator polynomial σ.sub.e(z)).

[0064] Considering the relationship

.Math..sub.d(z)=μz.sup.d−w(e)+1r.sub.N(z)

if 0 is not an element of the support x (the case for the Alternant Decoder or for the second EEA computation of the Patterson Algorithm), then the roots (≠0) of .Math..sub.d (z) are exactly the same as the roots of u.sub.N(z)=σ.sub.inv(z) and the roots can therefore be computed from the output of the regular flow modified EEA of FIG. 7.

[0065] For example, in the Alternant Decoder, the final step is:

σ.sub.e(z)=z.sup.ωσ.sub.inv(1/z)

[0066] Therefore, the output from the regular flow EEA of FIG. 7 may be used to compute the roots of σ.sub.e(z) and then to proceed with the decoding operation to determine the error e.

[0067] Derivation of the Regular Flow EEA from the Standard EEA.

[0068] Here, we transform smoothly the standard EEA (Alg. 1) into successive version gaining in regularity (Step. 1 and Step. 2). We end up with Alg. 2, which is simpler and more regular than all the previous ones.

[0069] Alg. 1 (Standard EEA):

TABLE-US-00005 Input:  a(z), b(z), deg(a) ≧ deg(b), d.sub.fin Output:  u(z), r(z) with b(z)u(z) = r(z)  mod a(z) and deg(r) ≦ d.sub.fin  1: r.sub.−1(z) ← a(z),r.sub.0(z) ← b(z),u.sub.−1(z) ← 1, u.sub.0(z) ← 0,  2: i ← 0  3: while deg(r.sub.i(z)) > d.sub.fin do  4:  i ← i + 1  5:  q.sub.i ← r.sub.i−2(z)/r.sub.i−1(z)  6:  r.sub.i ← r.sub.i−2(z) − q.sub.i(z)r.sub.i−1(z)  7:  u.sub.i ← u.sub.i−2(z) − q.sub.i(z)u.sub.i−1(z)  8: end while  9: N ← i 10: return u.sub.N(z), r.sub.N(z)

[0070] Step 1 (Unrolling Euclidean Division).

[0071] We decompose each Euclidian division into a number of polynomial subtractions. The idea is to kill the highest degree term without performing field division depending only on δ.sub.i=deg(q.sub.i(z))=deg(r.sub.i−2)−deg(r.sub.i−1). We explicit the intermediate values of the Euclidean division of R.sub.i−2(z) by R.sub.i−1(z), that we denote by R.sub.i.sup.(0)(z), R.sub.i.sup.(δi+1)(z). To do so, we eliminate in each R.sub.i.sup.(j)(z) (for 0≦j≦δ.sub.i+1) the term z.sup.d.sup.i−2.sup.−j, whether the associated coefficient is zero or not. This is why we perform the Euclidean divisions in a way to avoid the divisions by field elements. Consequently, the outputs are multiple of the outputs of Alg. 1 with the same inputs and Δ.sub.i=deg(R.sub.i−2)−deg(R.sub.i−1)=deg(r.sub.i−2)−deg(r.sub.i−1)=δ.sub.i

Alg. 2 (Euclidean division in left and step 1 (number of polynomial subtractions) in right):

TABLE-US-00006 1: while deg(r.sub.i(z)) > d.sub.fin do  1: while deg(R.sub.i(z)) > d.sub.fin do 2:  i ← i + 1  2:  i ← i + 1 3:  q.sub.i ← r.sub.i−2(z)/r.sub.i−1(z)  3:  R.sub.i−2.sup.(0)(z) ← R.sub.i−2(z), β.sub.i ← LC 4:  r.sub.i ← r.sub.i−2(z) − q.sub.i(z)r.sub.i−1(z)    (R.sub.i−1(z)) 5: end while  4:  Δ.sub.i ← deg(R.sub.i−2) − deg(R.sub.i−1)  5:  for j = 0,...,Δ.sub.i do  6:   α.sub.i,j ← R.sub.i,d.sub.j−2−j′.sup.(j)  7:   R.sub.i−2.sup.(j+1)(z) ← β.sub.iR.sub.i−2.sup.(j)(z) −      α.sub.i,jz.sup.Δ.sub.i−jR.sub.i−1(z)  8:  end for  9:  R.sub.i(z) ← R.sub.i−2.sup.(Δ.sub.i+1)(z), 10: end while

[0072] Proposition 1: (Comparison of Alg. 1 and 2). Let a(z) and b(z) be two polynomials with deg(a(z))≧deg(a(z)) and d a non-negative integer. u.sub.i(z), v.sub.i,(z), r.sub.i(z),q.sub.i(z) are intermediate values in Alg. 1, and. U.sub.i(z), V.sub.i,(z), R.sub.i(z), are intermediate values in Alg. 2. It holds that, for all i=−1, . . . , N, there exists λ.sub.i ε.sub.q.sub.m* such that:

R.sub.i(z)=λ.sub.ir.sub.i(z),

U.sub.i(z)=λ.sub.iu.sub.i(z)

[0073] As a consequence,

Δ.sub.i=deg(R.sub.i−2)−deg(R.sub.i−1)=deg(r.sub.i−2)−deg(r.sub.i−1)=δ.sub.i for all i

[0074] There are two problems with Step 1. The first problem is that the inner for loop has a variable length, and contains a multiplication z.sup.δ.sup.i.sup.−(j−1)R.sub.i(z), which depends on the iteration (we can kill accidentally not only the higher degree term but also terms of lower degree, which should be retained), which will produce a recognizable pattern. The second problem is that the while loop leads to a variable number of operations according to the input. It is not realizable because it requires that EEA has already been executed and observed. However, it is useful as an intermediate step leading to Step 2, described below.

[0075] Step 2 (Regular Polynomial Shift Pattern)

[0076] We perform the Euclidean division in such way that we only multiply the operand by z at each for iteration. This can be done by splitting each Euclidean division into two phases. The first phase L1 “re-aligns” the operands {tilde over (R)}.sub.i−2 and {tilde over (R)}.sub.i−1 so that they both have same degree d=deg (R.sub.−1(z))(=2t). Doing so, the second phase L2 computes the polynomial subtractions (corresponding to Steps 1 and perform a shift “re-aligning” of the operands. A consequence is that the polynomials {tilde over (R)}.sub.i(z) are of the form z.sup.ki R.sub.i(z) and the degrees d.sub.i are lost. N is the number of iterations in the while loop of EEA and Δ.sub.i is the value of deg(R.sub.i−2)−deg(R.sub.i−1) during the execution of EEA with step 1.

[0077] Step 2 (Pseudocode):

TABLE-US-00007  1: for i = 1,...,N do  2:  {tilde over (R)}.sub.i−2.sup.(0)(z) ← {tilde over (R)}.sub.i−2(z),  3:  for i = 1,...,Δ.sub.i − 1 do  4:   {tilde over (R)}.sub.i−1(z) ← z{tilde over (R)}.sub.i−1(z) {close oversize brace} L.sub.1  5:  end for  6:  for j = 0,...,Δ.sub.i do  7:   {tilde over (α)}.sub.i,j ← {tilde over (R)}.sub.i,d.sup.(j), {tilde over (β)}.sub.i ← {tilde over (R)}.sub.i−1,d.  8:   {tilde over (R)}.sub.i−2.sup.(j+1)(z) ←      z ({tilde over (β)}.sub.i{tilde over (R)}.sub.i−2.sup.(j)(z) − {tilde over (α)}.sub.i,j{tilde over (R)}.sub.i−1(z))  9:  end for {close oversize brace} L.sub.2 10:  {tilde over (R)}.sub.i(z) ← {tilde over (R)}.sub.i−2.sup.(Δ.sub.i+1)(z), 11: end for
Example of polynomial subtractions (Step 1) and multiplication of the operand by z (Step 2):

[00009]$z^4=\left({\alpha }^4.Math.z^2+z+{\alpha }^{13}\right).Math.\left({\alpha }^{11}.Math.z^2+{\alpha }^7.Math.z+{\alpha }^{11}\right)+\left({\alpha }^3.Math.z+{\alpha }^9\right)$$\frac{\begin{array}{c}{z}^4.Math..Math.{\alpha }^{11}.Math.z^2+{\alpha }^7.Math.z+{\alpha }^{11}\\ {\alpha }^{11}\left(z^4\right)-z^2\left({\alpha }^{11}.Math.z^2+{\alpha }^7.Math.z+{\alpha }^{11}\right)\end{array}}{{\alpha }^7.Math.z^3+{\alpha }^{11}.Math.z^2}$$\frac{{\alpha }^{11}\left({\alpha }^7.Math.z^3+{\alpha }^{11}.Math.z^2\right)-{\alpha }^7.Math.z\left({\alpha }^{11}.Math.z^2+{\alpha }^7.Math.z+{\alpha }^{11}\right)}{\alpha .Math..Math.z^2+{\alpha }^3.Math.z}$$\frac{{\alpha }^{11}\left(\alpha .Math..Math.z^2+{\alpha }^3.Math.z\right)-\alpha \left({\alpha }^{11}.Math.z^2+{\alpha }^7.Math.z+{\alpha }^{11}\right)}{{\alpha }^6.Math.z+{\alpha }^{12}}$$\frac{\begin{array}{c}{z}^4.Math..Math.{\alpha }^{11}.Math.z^2+{\alpha }^7.Math.z+{\alpha }^{11}\\ z(0.Math.\text{/}.Math.\left(z^4\right)-1\times \left({\alpha }^{11}.Math.z^2+{\alpha }^7.Math.z+{\alpha }^{11}\right)\end{array}}{{\alpha }^{11}.Math.z^5+{\alpha }^7.Math.z^2+{\alpha }^{11}.Math.z^1}$$\frac{z\left(0\times \left(z^4\right)-1\times \left({\alpha }^{11}.Math.z^3+{\alpha }^7.Math.z^2+{\alpha }^{11}.Math.z^1\right)\right)}{{\alpha }^{11}.Math.z^4+{\alpha }^7.Math.z^3+{\alpha }^{11}.Math.z^2}$$\frac{z\left({\alpha }^{11}\left(z^4\right)-1\times \left({\alpha }^{11}.Math.z^4+{\alpha }^7.Math.z^3+{\alpha }^{11}.Math.z^2\right)\right)}{{\alpha }^7.Math.z^4+{\alpha }^{11}.Math.z^3}$$\frac{z\left({\alpha }^7\left({\alpha }^{11}.Math.z^4+{\alpha }^7.Math.z^3+{\alpha }^{11}.Math.z^2\right)-{\alpha }^{11}\left({\alpha }^7.Math.z^4+{\alpha }^{11}.Math.z^3\right)\right)}{\alpha .Math..Math.z^4+{\alpha }^3.Math.z^3}$$\frac{z\left(\alpha \left({\alpha }^{11}.Math.z^4+{\alpha }^7.Math.z^3+{\alpha }^{11}.Math.z^2\right)-{\alpha }^{11}\left(\alpha .Math..Math.z^4+{\alpha }^3.Math.z^3\right)\right)}{{\alpha }^6.Math.z^4+{\alpha }^{12}.Math.z^3}$

[0078] Complete Regular Flow EEA.

[0079] To design a real constant flow algorithm, we merge the loops L1 and L2 in a common pattern so as to be indistinguishable (Steps 5 to 7 of Alg. 3). They differentiate by the assignments, which are performed in Steps 14-15 and 18-19. To know when polynomials subtractions have to be stopped, we collect in a counter δ the number of shifts necessary to re-align the operands. To design an algorithm with regular pattern we use the fact that Σ.sub.i.sup.Nδ.sub.i=w(e)−1, therefore, the number of iterations can be safely set to the maximum value (i.e., 2t to decode the errors with w(e)=t)), and the while loop is replaced by a for loop.

[0080] Complete Regular Flow Extended Euclidean Algorithm (Alg. 3):

TABLE-US-00008 Input: a(z) = z.sup.2t, b(z) = S.sub.e(z), d = 2t Output: .Math..sub.d(z) = μz.sup.d−w.sup.U.sup.(e)+1 σ.sub.inv(z), {circumflex over (R)}.sub.d(z) = μz.sup.d−w.sup.U.sup.(e)+1 ω.sub.e(z) for some μ ∈  .sub.q.sub.m*.   1: {circumflex over (R)}.sub.−1(z) ← a(z), {circumflex over (R)}.sub.0(z) ← zb(z),   2: .Math..sub.−1(z) ← 1, .Math..sub.0(z) ← 0, [00010]$\begin{array}{cc}.Math.3.Math.\text{:}& \delta \leftarrow -1.\\ .Math.4.Math.\text{:}& \mathrm{for}.Math..Math.j=1,\mathrm{.Math.}.Math.,d.Math..Math.\mathrm{do}\\ .Math.5.Math.\text{:}& .Math.{\alpha }_j\leftarrow {\hat{R}}_{j-1,d},{\beta }_j\leftarrow {\hat{R}}_{j-2,d}.\\ .Math.6.Math.\text{:}& .Math.{\mathrm{temp}}_R\left(z\right)\leftarrow z\left({\alpha }_j.Math.{\hat{R}}_{j-2}\left(z\right)-{\beta }_j.Math.{\hat{R}}_{j-1}\left(z\right)\right).\\ .Math.7.Math.\text{:}& .Math.{\mathrm{temp}}_U\left(z\right)\leftarrow z\left({\alpha }_j.Math.{\hat{U}}_{j-2}\left(z\right)-{\beta }_j.Math.{\hat{U}}_{j-1}\left(z\right)\right).\\ .Math.8.Math.\text{:}& .Math.\mathrm{if}.Math..Math.{\alpha }_j=0.Math..Math.\left(\mathrm{ie}.Math..Math.\mathrm{deg}\left({\hat{R}}_{j-1}\right)<\mathrm{deg}\left({\hat{R}}_{j-2}\right)\right).Math..Math.\mathrm{then}\\ .Math.9.Math.\text{:}& .Math.\delta \leftarrow \delta +1.\\ 10.Math.\text{:}& .Math.\mathrm{else}\\ 11.Math.\text{:}& .Math.\delta \leftarrow \delta -1.\\ 12.Math.\text{:}& .Math.\mathrm{end}.Math..Math.\mathrm{if}\\ 13.Math.\text{:}& .Math.\mathrm{if}.Math..Math.\delta <0.Math..Math.\mathrm{then}\\ 14.Math.\text{:}& .Math.\left({\hat{R}}_j\left(z\right),{\hat{R}}_{j-1}\left(z\right)\right)\leftarrow \left({\hat{R}}_{j-1}\left(z\right),{\mathrm{temp}}_R\right)\\ 15.Math.\text{:}& .Math.\left({\hat{U}}_j\left(z\right),{\hat{U}}_{j-1}\left(z\right)\right)\leftarrow \left({\hat{U}}_{j-1}\left(z\right),{\mathrm{temp}}_U\right)\\ 16.Math.\text{:}& .Math.\delta \leftarrow 0.\\ 17.Math.\text{:}& .Math.\mathrm{else}\\ 18.Math.\text{:}& .Math.\left({\hat{R}}_j\left(z\right),{\hat{R}}_{j-1}\left(z\right)\right)\leftarrow \left({\mathrm{temp}}_R,{\hat{R}}_{j-2}\left(z\right)\right)\\ 19.Math.\text{:}& .Math.\left({\hat{U}}_j\left(z\right),{\hat{U}}_{j-1}\left(z\right)\right)\leftarrow \left({\mathrm{temp}}_U,{\hat{U}}_{j-2}\left(z\right)\right)\\ 20.Math.\text{:}& .Math.\delta \leftarrow \delta .\\ 21.Math.\text{:}& .Math.\mathrm{end}.Math..Math.\mathrm{if}\\ 22.Math.\text{:}& \mathrm{end}.Math..Math.\mathrm{for}\end{array}\}.Math..Math.L$  23: return .Math..sub.d(z), {circumflex over (R)}.sub.d(z)

[0081] Proposition 2. (Comparison of standard EEA and modified regular flow EEA). For each I=1, . . . , N, after step 21 (FIG. 7), it holds that:

{circumflex over (R)}.sub.2(δ.sub.1+ . . . +δ.sub.i)=z.sup.d−d.sup.i−1R.sub.i(z)

.Math..sub.2(δ.sub.1+ . . . +δ.sub.i)=z.sup.d−d.sup.i−1U.sub.i(z)

[0082] The outputs of Alg. 1 and Alg. 3 are related such as:

{circumflex over (R)}.sub.d(z)=μz.sup.d−w(e)+1r.sub.N(z)

.Math..sub.d(z)=μz.sup.d−w(e)+1u.sub.N(z)

wherein w(e) is the Hamming weight of the error.

[0083] Therefore, provided 0 is not an element of the support x, then the algorithm allows to recover the error positions without ambiguity. Transposing this result to Patterson decoding requires adapting both EEA's. The adaptation of the second one is straightforward. For the first one (syndrome inversion), a problem arises: z can be multiplier of the output, and we found no way of determining when z is a factor of S.sup.−1(z) mod g.

CONCLUDING REMARKS

[0084] A technology has been presented which delinks the computation flow of the EEA algorithm from the inputs to the EEA algorithm as may be required in certain code based cryptography systems, e.g., the McEliece cryptosystem. EEA computation is, for example, required in the decryption of McEliece codes. By utilizing such a regular flow EEA computation in a cryptography device, for example, a secure portable device, the cryptography device is less vulnerable to side-channel attack and, therefore, more secure when performing McEliece decryption.

[0085] Although specific embodiments of the invention have been described and illustrated, the invention is not to be limited to the specific forms or arrangements of parts so described and illustrated. The invention is limited only by the claims.