Patent Document ID: 20170279600
Application ID: 15078869
Patent Flag: 0

Claim One:
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).