Encoding system according to the so-called rsa method, by means of a microcontroller and arrangement implementing this system

Claim 1

Method for implementing an RSA encoding procedure using a microcontroller comprising performing a modulo-N exponentiation by e of a message M; N, e and M being integers contained in an n-bit format, according to which method the calculation of the modulo-N exponentiation is broken down into two successive operation, of which the first operation has the form: B.sub.i =a.sub.i.X+T.2.sup.m where B i and X are calculation variables which depend on M and N, where a i is an extract of a format restricted to m bits of a calculation variable A whose value results from a previous operation, which extract is taken in the decreasing order of weight of A, of rank i, and where T is a summing variable used for the calculation of the variable A, and the second operation comprises reducing the length of the variable B i by subtracting a predetermined multiple of the modulus N, and of obtaining a new value A 1 for the variable A, characterised in that the second operation is carried out by means of a modulo-N quasi-reduction obtained from the equation: A.sub.i =q.N'+R where N' is the twos-complement of N in an n-bit format, where q is an integer quotient in a p-bit fixed format, approximated by default, of the division B i /N, with p>m, and where R is a variable provided by the n least significant bits of the variable B i , the result A i of which operation can contain a multiple of the modulus N and can thus present a transgression of d most significant bits with respect to the n-bit format, in that a given number of successive operations is determined as is an approximation tolerance q so that the maximum number of bits d of the transgression accumulated during said successive operations is equal to p-m, and in that an additional modulo quasi-reduction is performed after said given number of operations, which generates a new value of the variable A strictly in the n-bit format.