WO2003038598A1

WO2003038598A1 - Improvements in and relating to cryptographic methods and apparatus in which an exponentiation is used

Info

Publication number: WO2003038598A1
Application number: PCT/GB2002/004939
Authority: WO
Inventors: Colin Walter
Original assignee: COMODO RESEARCH LAB Ltd
Current assignee: COMODO RESEARCH LAB Ltd
Priority date: 2001-11-02
Filing date: 2002-10-31
Publication date: 2003-05-08
Anticipated expiration: 2004-05-02
Also published as: GB0126317D0

Abstract

There is disclosed a cryptographic apparatus in which an exponentiation is used, the apparatus comprising an exponentiator arranged whereby the exponentiation is carried out using addition chains with at least one divisor, and the addition chain is selected randomly. A cryptographic method and corresponding apparatus and method for communication is also disclosed.

Description

Improvements In and Relating to Cryptographic Methods and Apparatus In which An Exponentiation is Used

Field of Invention

The present invention relates to cryptographic and communication methods and apparatus . In particular, but without limitation, it relates to methods and apparatus for making number- theoretic public-key schemes (including encryption schemes , signature schemes , authentication schemes , key exchange schemes , key management schemes etc . using modular integer arithmetic, finite field arithmetic, elliptic curve groups , etc . ) more resistant to attacks involving side channel leakage of data .

Background of Invention

Cryptographic systems are widely used in a variety of circumstances. Prominent amongst these in the public sector are the electronic transfer of cash between banks, the storage of unspent units in a telephone smartcard, the protection of private keys which allow access to TV channels via a set-top box, and the exchange of confidential material between different branches of an organisation via a public network. Some of these are required to work in a hostile environment where the data owner is not physically present to protect the information and a potential attacker has unrestricted access to the cryptographic device . Such devices may incorporate a variety of means to protect the data contained within them besides encryption, including physical shielding to reduce electro-magnetic radiation, capacitors to reduce power variation, random noise generators to obscure internal operations, limited life span before secret data is overwritten, and self-destruct mechanisms when tampering is detected.

Many crypto-systems, signature systems and authentication systems employ exponentiation in some multiplicative group as part or all of the encryption, decryption, signing or verification processes. This includes, but is not limited to, the use of RSA in modular arithmetic and over elliptic curves (see Rivest, Shamir and Adleman) , to Diffie-Hellman key exchange, to El Gamal encryption and to the Digital Signature Standard. Generally, the value of the exponent must be kept secret. However, if the same sequence of multiplications and squarings is used on every occasion to perform the exponentiation, then an attacker can average any information leaking from the device over a number of encryptions/decryptions in order to increase the signal to noise ratio. He may be able to do this sufficiently well to reduce the number of possible exponents to the point at which it is computationally feasible to deduce the secret exponent .

In particular, recent work has exposed fundamental weaknesses in externally powered embedded cryptographic devices. Methods called "simple power analysis" and "differential power analysis" sometimes enable secret keys to be obtained from such systems by measuring minute variations in execution time, current consumption or electro-magnetic radiation. Details of how this leakage can be used to recover secret keys has been further developed to show that very few exponentiations are required to determine the secret exponent if the same computational scheme is used repeatedly and appropriate monitoring equipment is available. Moreover, it may be possible to recover the secret exponent from a single exponentiation if a scheme is used in which the same multiplicands are used repeatedly.

These methods of attack have led to some work on secure implementations of the algorithms involved. Much of this involves modification of the inputs to the exponentiation. For example, US 5,991,415 describes how the exponent can be randomly changed, how the input for exponentiation may be randomly changed, and how the modulus might also be modified.

An efficient exponentiation mechanism is disclosed C D Walter, Exponentiation using Division Chains, IEEE Transactions on computers, 47, No. 7 July 1998, 757-765, the content of which is incorporated herein by reference.

It has been suggested that Walter's algorithm could be used to provide different exponentiation schemes for different smartcards by programming in an individual, pre- computed scheme at the personalisation stage, but there is no suggestion that it is possible to generate such schemes in real time for successive exponentiations: Walter's algorithm is computationally very expensive. The process of exponentiation can be described using a scheme which determines which partial results need to be multiplied together at any given time. In general, the exponentiation scheme is determined by an addition chain. For convenience in this exposition, an addition chain is represented more precisely here by a sequence of multiplication instructions which are written as triples of the form (i , j , k) . Here (i , j , k) means multiply the contents of registers i and j together and write the contents into register k. For example, (1,1,2), (2,2,2),

(1,2,1) defines an addition chain which could be presented as 1+1 = 2, 2+2 = 4, 1+4 = 5. If M is initially in register 1, then the first instruction is to compute M² =

M¹⁺¹ = M¹xM¹ and put the result M² in register 2, the second instruction overwrites this, putting M⁴ = M²⁺² = M²xM² into register 2, and the third instruction computes M⁵ = M¹⁺⁴ = M¹xM⁴ and writes the result into register 1. So this is an addition chain which defines one scheme for exponentiating to the power 5 using only two registers and determines how those registers are used. To complete the description, the requisite initialisation of the registers must be presented, and the output register determined. For the example just presented, this means initialising register 1 with M and reading the result from register 1.

Addition chains for the standard square-and-multiply and m-ary methods are easy to generate. For the m-ary method to compute a power of M, M^j is pre-computed and put into register j, say. Register 0 can be used to store the partial product, as it is created. It is initialised with 1. When m = 2¹ , the exponent is represented with base m, and it has i-bit digits. The addition chain then consists of a repetition i squarings given by (0,0,0) followed, if j is non-zero, by a multiplication (0,j,0) where j is the next exponent digit, starting with the most significant exponent digit.

More efficient addition chains can be found using the normal type Walter algorithm. This uses the theory of division chains. Suppose that exponentiation to the power E is required and that E can be expressed in the form E = FD+R. Then computing M^E can be reduced to computing M^D and M^R first and then computing M^E = (M^D)^FxM^R. Raising to the power F here is done recursively in the same way, perhaps using a different value for D, and the process is repeated until the problem is reduced to raising to the power 0. The corresponding iterative version of this exponentiation algorithm simply multiplies all the powers M^R together as they are formed, and replaces M by M^D as the number which requires to be exponentiated. For each step, D is called the "divisor" and R the "residue" . The sequence of pairs (D,R) which reduces E to 0 is called a "division chain". The Walter algorithm initially selects a large set of divisors which have efficient addition chains for computing M^R and M^D in parallel, and then generates a large number of addition chains for M^E by always selecting the few most efficient divisors for extending the most efficient partial division chains constructed so far. Out of these many division chains, the most efficient is selected to provide an addition chain for computing M^E. Efficiency here is defined as the one with the shortest addition chain. In detail, the algorithm for constructing one of these divisor chains can be presented in a suitable form for this invention using a Pascal-like pseudo-programming language as follows.

Relevant component from Walter's Algorithm adapted and suitably modified for the present purpose:

Inputs: E a non-negative integer;

M in the given multiplicative group; Output: ResultM = M⁸ in the multiplicative group; Variables: StartM and Resul tM in the given multiplicative group;

Re E, D and R non-negative integers; Begin

RemE <- E ; StartM <- M ;

ResultM - 1 ; While RemE > 0 do Begin

Choose the most efficient D and R ,- ResultM <- StartM^R x ResultM ;

StartM - StartM⁰ ;

RemE «- (RemE - R) /D ; { The choice of R must make this division exact }

{ Invariant: M^E = StartM^RemE x ResultM } End

End

In each iteration of the loop here, the final values of

StartM and ResultM are computed from the initial values using a single, fixed, optimal (i.e. shortest) addition chain which contains both D and R. In the discussion below, the addition chains for each divisor/residue pair (D,R) will be called addition "subchains" . When all of these are concatenated together they yield an addition chain which determines a scheme for computing any Eth power, as required. This complete addition chain, together with any relevant additional detail such as register locations, will be referred to as an "exponentiation scheme" .

An efficient choice for the divisor set tends to select divisors with few non-zero bits in their binary representations. The Walter algorithm provides {2, 3, 5, 17, 33, 49, 65, 97, 129, 257, 513, 1025} as an example of a small set from which to choose divisors and provides a deterministic method for selecting the divisor at each step. This divisor set is semi-successful at producing the very short addition chains required for efficient exponentiation. A much larger divisor set is better. This means that cryptographic devices do not generally have enough memory to use the Walter's algorithm to speed up exponentiation. Indeed, to obtain a relatively efficient chain, Walter has to generate a large number of addition chains by choosing several of the most efficient divisors at each iteration in order to extend the best partially completed addition chains. It is counterintuitive that the method will generate useful addition chains in this context. Summary of the Invention

According to the present invention in a first aspect, there is provided an encryption apparatus in which an exponentiation is used, the apparatus comprising an exponentiator arranged whereby the exponentiation is carried out using addition chains with at least one divisor, and the addition chain is selected randomly.

Suitably, the apparatus comprises a divisor selector arranged to select a divisor.

Suitably, the apparatus comprises a divisor set memory arranged to store divisor sets.

Sul.itably, the apparatus comprises an addition subchain selector arranged to select addition subchains. Suitably, the apparatus comprises an addition subchain memory from which addition subchains selector selects addition subchains.

Suitably, the apparatus comprises a register location selector arrange to select register locations for start variables.

Suitably, a division chain is used and the divisor is selected randomly from the set of positive integers. Suitably, the divisor is selected from a set of at least three numbers. Suitably, the divisor is selected from a set of numbers including 2 , 3 and 5.

The divisor may be selected from a relatively small set of numbers .

Suitably, there is a divisor and residue pair, and there is a plurality of additional chains for the divisor and residue pair from which plurality of addition chains a random selection is made.

Suitably, there is a divisor and residue pair in which the residue is non-minimal. That is the residue can be equal to or greater than the divisor.

Suitably, the divisor is selected from a set of divisors that exactly divide the remaining exponent .

Suitably, a different addition chain is generated for every one or more successive exponentiations.

Suitably, the exponentiation uses Walter's algorithm.

A new random selection need not be made for each exponentiation, provided it is changed regularly. Suitably, the exponent, modulus and/or method may be modified. Generally, this may use the techniques taught in US 5991415.

Suitably, in Walter' s algorithm each least non-negative residue is allowable for each divisor. Suitably, one minimal length addition chain is associated with each divisor/residue pair. Suitably, the residue powers are multiplied together sequentially.

Suitably, a plurality of divisors is selected.

Suitably, there is an addition chain for a divisor and residue pair which has non-minimal length.

Suitably, the divisors have more than two non-zero bits in their binary representations.

In the Walter algorithm, to raise M to exponent E:

i) a first variable RemE is initialised to E ii) a second variable StartM is initialised to M iii) a third variable ResultM is initialised to M iv) the following steps are carried out repeatedly until RemE = 0 : a) a divisor D is selected; b) a remainder R is determined from RemE modulo c) the third variable is updated ResultM<-StartM^R xResultM;

d) the second variable is updated StartM«-StartM^D;

e) the first variable is updated RemE <— RemE div D

in which the addition chains are used for the exponentiations StartM^R and StartM^D.

According to the present invention in a second aspect, there is provided a cryptographic method including an exponentiation, in which the exponentiation is carried out using addition chains with at least one divisor, and the addition chain is selected randomly.

According to the present invention in a third aspect , there is provided a communication apparatus comprising means for receiving an input signal and cryptographic apparatus according to the first aspect of the invention .

According to the present invention in a fourth aspect, there is provided a communication method comprising the steps of receiving an input signal and encrypting or decrypting the input signal according to the method of the second aspect of the present invention.

The expression "randomly" includes pseudo-random selection. Suitably, a division chain is used and the divisor is selected randomly from the set of positive integers. Suitably, the divisor is selected from a set of at least three numbers. Suitably, the divisor is selected from a set of numbers including 2 , 3 and 5.

The divisor may be selected from a relatively small set of numbers .

Suitably, the divisor is selected from a set of divisors that exactly divide the remaining exponent.

Suitably, the exponentiation uses Walter's algorithm.

Suitably, the exponent, modulus and/or method may be modified. Generally, this may use the techniques taught in US 5991415. Suitably, in Walter's algorithm each least non-negative residue is allowable for each divisor. Suitably, one minimal length addition chain is associated with each divisor/residue pair. Suitably, the residue powers are multiplied together sequentially.

Suitably, a plurality of divisors is selected.

A new random selection need not be made for each exponentiation, provided it is changed regularly.

Suitably, the divisors have more than two non-zero bits in their binary representations .

In the Walter algorithm, to raise M to exponent E:

i) a first variable RemE is initialised to E v) a second variable StartM is initialised to M vi) a third variable ResultM is initialised to M vii) the following steps are carried out repeatedly until RemE = 0: f) a divisor D is selected; g) a remainder R is determined from RemE modulo D; h) the third variable is updated ResultM<—StartM^R xResultM; i) the second variable is updated StartM<-StartM^D;

j) the first variable is updated RemE — RemE div D

Preferred embodiments of the present invention provide a secure or leak-resistant implementation of exponentiation, such as is required for many public-key algorithms and protocols, such as RSA encryption, ElGamal encryption, Diffie-Hellman key exchange and the Digital Signature Standard. An advantage of embodiments of the invention is that they provide an efficient mechanism for generating a different exponentiation scheme every time it is used and that each such scheme is itself efficient. This means, firstly, that attacks on the system which use differential power analysis are rendered much less harmful because little meaningful data can be extracted by averaging over a number of different exponentiations. Secondly, it means that the mechanism makes little difference to the overall time which the cryptographic device requires for its operation. However, thirdly, it should be noted that preferred embodiments of the present invention can be used in conjunction with all . currently known algorithms with the same purpose, because all of them involve modifying the inputs to the exponentiation whereas no such change is required for embodiments hereof .

The main technique is a means through which each time exponentiation to the power E is required, a new, randomly generated addition chain is constructed either before , or in parallel with, performing the exponentiation . No two such exponentiation schemes are usually the same , although the same scheme can be re-used if desired . No other pre- computation is involved for individual exponentiations . In the preferred embodiments , an addition scheme for the exponentiation scheme is generated using a novel modification of the divisor chain method of the Walter algorithm and a random number generator (RNG) box to help select the divisors .

The invention presented herein is applicable in the area of number- theoretic public-key schemes ( including encryption schemes , signature schemes , authentication schemes , key exchange schemes , key management schemes etc . using modular integer arithmetic , finite field arithmetic , el liptic curve groups , etc . ) where it is required to protect the secrecy of the private key in a hostile environment . The invention is applicable wherever exponentiation is used and provides an apparatus and system for performing the exponentiation which is resistant to attacks involving side channel leakage of data . Brief Description of the Drawings

The present invention will now be described, by way of example only, with reference to the Figures that follow; in which:

Figure 1 is a schematic illustration of an apparatus according to the present invention.

Figure 2 is a schematic illustration of the method and apparatus of the invention in one of its preferred embodiments .

Figure 3 is a schematic illustration of a communication apparatus according to the present invention.

Detailed Description of the Preferred Embodiments

This preferred embodiment contains a version of the exponentiation machine described in the "Background of Invention" section above, which is adapted from Walter's algorithm. Other embodiments may use equivalent variants of this in which, for example, the list of divisors is chosen before any exponentiation is performed rather than in parallel with it. Since the mathematical notation and programming code are unambiguous and well understood by those of skill in the art, no detailed description of same is deemed necessary for a full and precise understanding of the present invention by a person skilled in the art. Whilst the exemplar apparatus described below uses modular arithmetic in the context of the RSA cryptosystem, no such restrictions to the invention are so implied. For example, elliptic curve cryptography and Diffie-Hellman key exchange can also be protected in part by embodiments of this invention.

Referring to Figure 1 of the drawings that follow, there is shown a cryptographic apparatus 2 comprising a data input 4, a processor 6 (which includes associated memory) and an output 8. Data is input to the cryptographic apparatus 2 via data input 4 and encrypted by processor 6. Alternatively encrypted input data may be decrypted. The output may be the encrypted input data, or the processor may, additionally, make a determination based on the decrypted data and output the result of that determination.

The processor is arranged to carry out decryption (and optionally encryption) as described below.

The apparatus and method for computing one value of M^E at a time is illustrated in Figure 2. Figure 2 illustrates the functionality of processor 6. This is to be performed in the common mathematical structure referred to as a group, and this group will be written using multiplicative notation. In the context of the (integer) RSA cryptosystem or Diffie-Hellman key exchange with modulus N, the group is that of the integers mod N under multiplication. With this as the specified group, it is unnecessary to write the "mod N" explicitly. In the context of elliptic curve cryptography, the group is that of the points on the elliptic curve under what is normally referred to as addition. For uniformity with the integer cases, this group will be written multiplicatively as well. So, following normal mathematical practice, it should be understood that in all applicable contexts, the exponentiation is described with multiplication as the group operation.

Figure 2 shows the inputs M and E provided in inputs 10 and 21, and the required output 23. There are two main processes which may run interleaved or sequentially, or in some combination of these, using a single processor or multiple processors. These processes are i) the selection of the exponentiation scheme, which includes mainly the choice of addition chain (boxes 10 through 20 in Figure 2) , and ii) the application of the exponentiation scheme to perform an exponentiation (boxes 21 through 23 in Figure 2) .

During the process of selecting an exponentiation scheme, the exponent E is copied to Remaining Exponent (RemE) memory 11, where, for convenience, it may have a non- standard representation in order to make more efficient its division by any chosen divisor. After the divisor D is selected (step 13) by divisor selector 24, the new value for RemE and the residue R are computed (step 15) by computational means 25 from the formulae R — RemE mod D and RemE <- (RemE - R)/D. The value of RemE at 11 is updated, and the pair (D,R) is passed on to addition sub chain selector 26 at step 17 which obtains an addition subchain for the pair from addition subchain provider 16. Addition subchain selector 26 stores all this data and further choices ready for the exponentiation. The exponentiation may take place immediately in step 22 by exponentiator 27 or it may be performed later.

During the process of performing the exponentiation, a register location selector 28 in step 18 first determines the locations of StartM, ResultM and TempM. Then the initial value M from input 21 is loaded into StartM in exponentiator 27 and ResultM is initialised with 1 or M in exponentiator 27. Then (using the notation described above) the addition chain operation triples (i,j,k) are repeatedly obtained from addition subchain selector 26, modified by register location selector 28 if necessary, and applied to perform a multiplication and storing of the product. When the last triple has been processed, output 23 obtains the result M^E from ResultM in exponentiator 27. This embodiment uses just the three registers named in step 22. However, other embodiments may use more registers as desired.

In detail, the choice of exponentiation scheme is made as follows. A divisor set is chosen and provided in step 12 from divisor set memory 29. For the preferred embodiment, this set contains divisors 2, 3 and 5 only, but almost any choice of a set of positive integers can be made instead. Associated with each divisor D from this set, and integer R with 0 < R < D, an addition chain is chosen which includes R and D and has shortest length with this property. These addition chains are put an additional subchains memory 30 for step 16. This is the preferred method for initialising step 16, but alternative and additional addition chains can be placed in addition subchains memory 30. There may be several chains representing the same pair (D,R) and these chains do not need to be chosen with minimal length, although faster exponentiation is achieved when this is done. In particular, these subchains may or may not contain "useless" operations which have no effect on the computation and could have been omitted. Furthermore, the set of residues from which R is chosen need not be restricted in any way. Indeed, the set of residues associated with a divisor does not need to form a complete set of residues, nor do its elements need to be all non- negative, nor do they all need to be least non-negative. However, for each selectable pair (D,R) there must be at least one available addition chain placed in addition subchain memory 30. Moreover, sufficient residues must be available for there to be at least one selectable pair (D,R) when an exponentiation scheme is being generated.

Before operation, the exponentiation apparatus must also be provided with a divisor selector 24 which will select divisors in a random way. There are many different ways to construct such a divisor selector. One such suitable embodiment for this is the following exemplar apparatus which illustrates some of the possible enhancements more clearly. This suggested construction obtains input from a random number generator 20 in the interval [0,1] (RNG) and uses the data in the divisor set provided by driver set memory 12. It is written in the programming language Pascal.

D := 0 ;

If RNG < 7/8 then

If 0 = RemE mod 2 then D = 2 else If 0 = RemE mod 5 then D = 5 else If 0 = RemE mod 3 then D = 3 ; If D = 0 then Begin p := RΝG ;

If p < 6/8 then D := 2 else If p < 7/8 then D := 3 else

D := 5 ; End ;

Other embodiments may have random numbers supplied in a different interval, they may have different values replacing the occurrences of 7/8, 6/8 and 7/8, they may re-order some of the statements, or they may make other inconsequential changes as far as the functionality of the box is concerned. In the program segment, RemE refers to the remaining part of the exponent E which still has to be processed, and is stored in a remaining exponent RemE memory 11. in this construction no deterministic choice is made for any divisor. An alternative construction for divisor selector 24, which is useful for improving efficiency, is that a divisor which divides RemE is always chosen whenever possible. This could be implemented by omitting the line "If RΝG(x) < 7/8 then" in the above Pascal code. A further enhancement is to update this selection process regularly in a random way. One embodiment of this idea is for step 14 to update the values 7/8, 6/8 and 7/8 in the Pascal code for divisor selection at the start of each new exponentiation. A divisor selection process updater 31 (associated with step 14) is supplied with random numbers from RNG 20 to enable this process to take place. The new values are restricted to being probabilities in the range [0,1] and are usually selected strictly between 0.5 and 1. This updating process can_ be combined with a random number from RΝG 20 which is used to select unpredictable intervals between such updates. Consequently, this provides a mechanism for enabling updates to a randomly determined selection process to occur at unpredictable intervals.

When a divisor and residue pair (D,R) has been selected by computational means 25, an addition subchain must be selected by addtion subchain selector 26 from the list of such chains provided in addition subchains memory 30. If there is more than one addition subchain associated with (D,R), then the RΝG 20 is used to select one of them. Any selection process can be used for this, whether predictable or not. Normally a weighted, random selection is made to improve cryptographic strength or to improve efficiency, such as by making non-minimal length subchains less likely to be chosen. In the case of there being n subchains for^' the chosen pair (D,R) , a random number in the interval [0,1) from RNG 20 can be used to select the ith subchain when the random number lies in the sub- interval [i/n, (i+1) /n) .

When the addition chain has been selected by addition subchain selector 26, the register location selector 28 can be used to modify the default locations of variables used in the computation of M^E. Using input from the RNG 20, these locations can be chosen randomly from available RAM, but will normally just permute the locations within the space that the apparatus requires for storage of various powers of M. Then, when a new power of M is computed, it will be written into the random location determined by register location selector 28. For most embodiments, three registers are used, (these are called StartM, ResultM and TempM in box 22 of Figure 2) , and frequently only two values need to be kept (namely StartM and ResultM in this embodiment) . This leaves a third which is free to be overwritten. So a freshly computed product can overwrite either its previous value or, when available, any other value which is not going to be used subsequently.

The data for the addition chains and locations can be managed using the notation described in the background section: (i , j , k) means this: take the group elements in locations i and j, compute their product, and write the result into location k. A typical addition subchain for the divisor-residue pair (5,3) is stored in addition subchain memory 30 as the sequence of four triples (112, 121, 133, 121) where 1 denotes the register called StartM in exponeniator 27, 2 denotes the register TempM and 3 denotes the register called ResultM. Triple (133) illustrates the preferred means by which residue powers are multiplied together for this subchain. Rather than letting register locator selector 28 compute which register locations can be permuted, addition subchains memory 30 can be supplied with extra subchains representing alternative location choices. So subchain (112, 121, 133, 122) writes the last product into location 2 instead of the 1 used in the previous subchain. The random selection of locations for writing products to is therefore achieved via the random selection of an addition subchain from box 16 for the divisor/residue pair. Then register location selector 28 just needs to record that StartM will be in location 2, not 1, for the next subchain. Observe that the storing of such variables in random locations need not involve writing to a predetermined location and then copying from there to the random location.

This apparatus presented in the drawings can be built with any or all of the enhancements presented above and can be used for repeated exponentiations where the exponentiation scheme generated by the apparatus is changed with any desired frequency, whether regular or irregular.

Normally, each exponentiation would be performed with a freshly generated scheme, but it could also be changed at fixed, regular intervals or at randomly selected irregular intervals.

The Chinese Remainder Theorem (CRT) enables a large exponentiation to be re-expressed in terms of several smaller exponentiations . The invention here applies equally well to the component exponentiations, since it applies to any exponentiation . There are many other means of modifying the exponentiation for increased efficiency or increased security or for other purposes . Whenever such modifications require exponentiations to be performed, the present invention may be applied in a similar fashion. In particular, the teaching of US Patent 5991415 can be applied to the exponent and other inputs, providing a new exponentiation to which the present invention can also be applied.

The RNG 20 may be implemented in many different ways. Different methods may be used for the steps in Figure 2. Any method is acceptable here and all methods are covered by the invention. Normally, an RNG generates a so-called pseudo-random sequence. In the preferred embodiment, this RNG should be secure against side channel attack.

The exponent RemE of step 11 may be represented with any radix, as may be E in step 10. A multiple of the least common multiple (LCM) of the divisors in box 12 is preferred. For the choice {2,3,5}, a base of 30, 60, 120 or 240 is ideal when the word size used to hold RemE in memory is 5, 6, 7 or 8 bits respectively. Division of RemE and determination of residue R are then much easier: once divisor D is chosen (step 13) exponentiator 25 can determine R from the lowest digit of RemE, and the next value of RemE can be obtained by a multiplication and a shift down, in a manner well understood by those skilled in this art. For example, with an 8-bit processor, base 240 would be chosen and division by D would be performed using multiplication by 240/D and a shift down.

The most efficient method for combining the residue powers is to multiply them into a single variable, called ResultM in the above. However, several variables ResultMO,

ResultMl, ..., ResultMk might be set up, initialised, and the residue powers multiplied into a pre-determined or randomly chosen one of these. Their locations may be changed randomly, of course. The product of the contents of these registers must be calculated in order to obtain the required output, and this may be done by multiplications spread out over the whole exponentiation instead of at the end only.

Referring to Figure 3 of the drawings that follow, there is shown a communication apparatus 100 comprising a transmitter 102 and a receiver 104, in each of which a cryptographic apparatus 2 as shown in Figure 1 may be employed.

Many choices described in this preferred embodiment are practical ones, in order that the invention be described clearly. Sections of program code might be replaced by functionally equivalent code in any programming language. This includes re-ordering the execution of some statements. The choice of divisor set {2,3,5} is for illustration only, and any set is covered in this invention. Addition subchains which contain the pair (D,R) have not been given explicitly as these can be constructed easily by a practitioner skilled in the art.

Embodiments of the present invention could be used in a smart card, rechargeable telephone card, conditional access module for a set-top box or other similar VLSI chips . Advantageously, in preferred embodiments no deterministic choices of the divisor are made during construction of the addition chain.

The reader's attention is directed to all papers and documents which are filed concurrently with or previous to this specification in connection with this application and which are open to public inspection with this specification, and the contents of all such papers and documents are incorporated herein by reference .

All of the features disclosed in this specification (including any accompanying claims, abstract and drawings) , and/or all of the steps of any method or process so disclosed, may be combined in any combination, except combinations where at least some of such features and/or steps are mutually exclusive.

Each feature disclosed in this specification (including any accompanying claims, abstract and drawings) , may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise. Thus, unless expressly stated otherwise, each feature disclosed is one example only of a generic series of equivalent or similar features.

The invention is not restricted to the details of the foregoing embodiment (s) . The invention extends to any novel one, or any novel combination, of the features disclosed in this specification (including any accompanying claims, abstract and drawings) , or to any novel one, or any novel combination, of the steps of any method or process so disclosed.

Claims

Claims :

1. A cryptographic apparatus in which an exponentiation is used, the apparatus comprising an exponentiator arranged whereby the exponentiation is carried out using addition chains with at least one divisor, and the addition chain is selected randomly.

2. A cryptographic apparatus according to claim 1, in which the apparatus comprises a divisor selector arranged to select a divisor.

3. A cryptographic apparatus according to claim 1 and claim 2, in which the apparatus comprises a divisor set memory arranged to store divisor sets.

4. A cryptographic apparatus according to any preceding claim, in which the apparatus comprises an addition subchain selector arranged to select addition subchains .

5. A cryptographic apparatus according to claim 4, in which the apparatus comprises an addition subchain memory from which addition subchains selector selects addition subchains .

6. A cryptographic apparatus according to any preceding claim, in which the apparatus comprises a register location selector arrange to select register locations for start variables.

7. A cryptographic apparatus according to any preceding claim, in which a division chain is used and the divisor is selected randomly from the set of positive integers .

8. A cryptographic apparatus according to claim 7 , in which the divisor is selected from a set of at least three numbers .

9. A cryptographic apparatus according to claim 8 , in which the divisor is selected from a set of numbers including 2 , 3 and 5.

10. A cryptographic apparatus according to any preceding claim, in which there is a divisor and residue pair, and there is a plurality of additional chains for the divisor and residue pair from which plurality of addition chains a random selection is made.

11. A cryptographic apparatus according to any preceding claim, in which there is a divisor and residue pair in which the residue is non-minimal .

12. A cryptographic apparatus according to any preceding claim, in which the divisor is selected from a set of divisors that exactly divide the remaining exponent .

13. A cryptographic apparatus according to any preceding claim, in which a different addition chain is generated for every one or more successive exponentiations.

14. A cryptographic apparatus according to any preceding claim, in which the exponentiation uses Walter's algorithm.

15. A cryptographic apparatus according to claim 14, in which in Walter's algorithm each least non-negative residue is allowable for each divisor.

16. A cryptographic apparatus according to claim 15, in which one minimal length addition chain is associated with each divisor/residue pair.

17. A cryptographic apparatus according to claim 16, in which the residue powers are multiplied together sequentially.

18. A cryptographic apparatus according to any one of claims 15 to 17, in which a plurality of divisors is selected.

19. A cryptographic apparatus according to any one of claims 15 to 18, in which there is an addition chain for a divisor and residue pair which has non-minimal length.

20. A cryptographic apparatus according to any one of claims 15 to 19, in which the divisors have more than two noil-zero bits in their binary representations.

21. A cryptographic method including an exponentiation, in which the exponentiation is carried out using addition chains with at least one divisor, and the addition chain is selected randomly.

22. A cryptographic method according to claim 21, in which a division chain is used and the divisor is selected randomly from the set of positive integers .

23. A cryptographic method according to claim 21 or claim 22, in which the divisor is selected from a set of at least three numbers.

24. A cryptographic method according to claim 23, in which the divisor is selected from a set of numbers including 2 , 3 and 5.

25. A cryptographic method according to any one of claims 21 to 24, in which there is a divisor and residue pair, and there is a plurality of additional chains for the divisor and residue pair from which plurality of addition chains a random selection is made.

26. A cryptographic method according to any one of claims 21 to 25, in which there is a divisor and residue pair in which the residue is non-minimal.

27. A cryptographic method according to any one of claims 21 to 26, in which the divisor is selected from a set of divisors that exactly divide the remaining exponent .

28. A cryptographic method according to any one of claims 21 to 27, in which a different addition chain is generated for every one or more successive exponentiations .

29. A cryptographic method according to any one of claims 21 to 28, in which the exponentiation uses Walter's algorithm.

30. A cryptographic method according to claim 29, in which in Walter's algorithm each least non-negative residue is allowable for each divisor.

31. A cryptographic method according to claim 30, in which one minimal length addition chain is associated with each divisor/residue pair.

32. A cryptographic method according to claim 30 or claim 31, in which the residue powers are multiplied together sequentially.

33. A cryptographic method according to any one of claims 29 to 32, in which a plurality of divisors is selected.

34. A cryptographic method according to any one of claims 29 to 33, in which there is an addition chain for a divisor and residue pair which has non-minimal length.

35. A cryptographic method according to any one of claims 29 to 34, in which the divisors have more than two non-zero bits in their binary representations.

36. A communication apparatus comprising means for receiving an input signal and cryptographic apparatus according to any one of claims 1 to 20.

37. A communication method comprising the steps of receiving an input signal and encrypting or decrypting the input signal according to any one of claims 21 to 35.