Patent ID: 8331556

Claim:
A method for decrypting an encrypted message represented by a sequence C or applying an electronic signature of a sequence C, said sequence C consisting of data belonging to a finite field K=GF(q), where q>1, in which there are processed successive blocks each comprising (n·d) successive data items from the sequence C, where n and d are predetermined integers greater than 1, the processing of such a block comprising the following steps: applying a predetermined affine invertible transformation t −1 to said block; interpreting the resulting block as being formed of n successive elements (y 1 , y 2 ,. . ., y n ) of an extension E=GF(q d ) of the field K; calculating, using a processor of a device, an n-tuplet (x 1 , x 2 , . . . , x n ) of elements of the field E by solving a system f of n predetermined polynomials of the form y k = ∑ 1 ≤ i ≤ j ≤ n ⁢ ⁢ a k ( ij ) ⁢ x i q α i ⁢ x j q β j ⁢ + ∑ 1 ≤ i ≤ n ⁢ ⁢ b k i ⁢ x i q γ ⁢ ⁢ i + c k ⁡ ( 1 ≤ k ≤ n ) in which the coefficients a k (ij) , b k (i) , and c k belong to E and the exponents α i , β j , and γ i are positive or zero integers with at least one of these exponents being a positive integer; interpreting said n-tuplet (X 1 , x 2 , . . . , x n ) as being a new block formed of (n·d) successive elements from the field K; and applying a predetermined affine invertible transformation s −1 to said new block.