WO2003038598A1 - Ameliorations apportees a des methodes cryptographiques et appareil faisant appel a une exponentiation - Google Patents
Ameliorations apportees a des methodes cryptographiques et appareil faisant appel a une exponentiation Download PDFInfo
- Publication number
- WO2003038598A1 WO2003038598A1 PCT/GB2002/004939 GB0204939W WO03038598A1 WO 2003038598 A1 WO2003038598 A1 WO 2003038598A1 GB 0204939 W GB0204939 W GB 0204939W WO 03038598 A1 WO03038598 A1 WO 03038598A1
- Authority
- WO
- WIPO (PCT)
- Prior art keywords
- divisor
- cryptographic
- addition
- exponentiation
- residue
- Prior art date
Links
- 238000000034 method Methods 0.000 title claims abstract description 61
- 238000004891 communication Methods 0.000 claims abstract description 8
- 230000008569 process Effects 0.000 description 15
- 230000007246 mechanism Effects 0.000 description 5
- 238000010276 construction Methods 0.000 description 4
- 238000012986 modification Methods 0.000 description 3
- 230000004048 modification Effects 0.000 description 3
- 230000005670 electromagnetic radiation Effects 0.000 description 2
- 230000001788 irregular Effects 0.000 description 2
- 238000012935 Averaging Methods 0.000 description 1
- 230000008901 benefit Effects 0.000 description 1
- 239000003990 capacitor Substances 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000007689 inspection Methods 0.000 description 1
- 239000000463 material Substances 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
- 238000012546 transfer Methods 0.000 description 1
- 238000012795 verification Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/723—Modular exponentiation
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
- G06F2207/7219—Countermeasures against side channel or fault attacks
- G06F2207/7223—Randomisation as countermeasure against side channel attacks
- G06F2207/7252—Randomisation as countermeasure against side channel attacks of operation order, e.g. starting to treat the exponent at a random place, or in a randomly chosen direction
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
- G06F2207/7276—Additional details of aspects covered by group G06F7/723
- G06F2207/7295—Additional details of aspects covered by group G06F7/723 using an addition chain, or an addition-subtraction chain
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
- G06F7/725—Finite field arithmetic over elliptic curves
Definitions
- the present invention relates to cryptographic and communication methods and apparatus .
- 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 .
- 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.
- 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.
- the exponentiation scheme is determined by an addition chain.
- 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) .
- (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),
- Addition chains for the standard square-and-multiply and m-ary methods are easy to generate.
- 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.
- 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.
- 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.
- 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.
- 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.
- the addition chains for each divisor/residue pair (D,R) will be called addition “subchains” .
- addition chains 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” .
- 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.
- 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.
- the apparatus comprises a divisor selector arranged to select a divisor.
- the apparatus comprises a divisor set memory arranged to store divisor sets.
- the apparatus comprises an addition subchain selector arranged to select addition subchains.
- the apparatus comprises an addition subchain memory from which addition subchains selector selects addition subchains.
- the apparatus comprises a register location selector arrange to select register locations for start variables.
- a division chain is used and the divisor is selected randomly from the set of positive integers.
- the divisor is selected from a set of at least three numbers.
- 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 .
- the residue is non-minimal. That is the residue can be equal to or greater than the divisor.
- the divisor is selected from a set of divisors that exactly divide the remaining exponent .
- a different addition chain is generated for every one or more successive exponentiations.
- the exponentiation uses Walter's algorithm.
- each least non-negative residue is allowable for each divisor.
- one minimal length addition chain is associated with each divisor/residue pair.
- the residue powers are multiplied together sequentially.
- a plurality of divisors is selected.
- the divisors have more than two non-zero bits in their binary representations.
- 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.
- a communication apparatus comprising means for receiving an input signal and cryptographic apparatus according to the first aspect of the invention .
- 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.
- a division chain is used and the divisor is selected randomly from the set of positive integers.
- the divisor is selected from a set of at least three numbers.
- 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 .
- the residue is non-minimal. That is the residue can be equal to or greater than the divisor.
- the divisor is selected from a set of divisors that exactly divide the remaining exponent.
- a different addition chain is generated for every one or more successive exponentiations.
- the exponentiation uses Walter's algorithm.
- the exponent, modulus and/or method may be modified. Generally, this may use the techniques taught in US 5991415.
- each least non-negative residue is allowable for each divisor.
- one minimal length addition chain is associated with each divisor/residue pair.
- the residue powers are multiplied together sequentially.
- a plurality of divisors is selected.
- the divisors have more than two non-zero bits in their binary representations .
- 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.
- 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 .
- 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 .
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- the group 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.
- the group 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.
- 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.
- 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.
- 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.
- a divisor set is chosen and provided in step 12 from divisor set memory 29.
- this set contains divisors 2, 3 and 5 only, but almost any choice of a set of positive integers can be made instead.
- 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.
- the exponentiation apparatus Before operation, the exponentiation apparatus must also be provided with a divisor selector 24 which will select divisors in a random way.
- a divisor selector 24 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.
- 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.
- 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.
- addition subchain 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.
- 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) .
- 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.
- (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.
- 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.
- 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 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 .
- 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.
- LCM least common multiple
- 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.
- base 240 would be chosen and division by D would be performed using multiplication by 240/D and a shift down.
- 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.
- FIG. 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.
- 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 .
- no deterministic choices of the divisor are made during construction of the addition chain.
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- General Engineering & Computer Science (AREA)
- Storage Device Security (AREA)
Abstract
Applications Claiming Priority (2)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
GB0126317A GB0126317D0 (en) | 2001-11-02 | 2001-11-02 | Improvements in and relating to cryptographic methods and apparatus in which an exponentiation is used |
GB0126317.7 | 2001-11-02 |
Publications (1)
Publication Number | Publication Date |
---|---|
WO2003038598A1 true WO2003038598A1 (fr) | 2003-05-08 |
Family
ID=9925009
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
PCT/GB2002/004939 WO2003038598A1 (fr) | 2001-11-02 | 2002-10-31 | Ameliorations apportees a des methodes cryptographiques et appareil faisant appel a une exponentiation |
Country Status (2)
Country | Link |
---|---|
GB (1) | GB0126317D0 (fr) |
WO (1) | WO2003038598A1 (fr) |
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
EP3166013A1 (fr) * | 2015-11-04 | 2017-05-10 | Nxp B.V. | Exponentiation modulaire à l'aide de chaînes d'addition aléatoire |
Citations (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US5991415A (en) * | 1997-05-12 | 1999-11-23 | Yeda Research And Development Co. Ltd. At The Weizmann Institute Of Science | Method and apparatus for protecting public key schemes from timing and fault attacks |
WO2001031436A1 (fr) * | 1999-10-28 | 2001-05-03 | Bull Cp8 | Procede de securisation d'un ensemble electronique de cryptographie a base d'exponentiation modulaire contre les attaques par analyse physique |
WO2001048974A1 (fr) * | 1999-12-28 | 2001-07-05 | Giesecke & Devrient Gmbh | Support de donnees portatif a acces protege par repartition des codes |
-
2001
- 2001-11-02 GB GB0126317A patent/GB0126317D0/en not_active Ceased
-
2002
- 2002-10-31 WO PCT/GB2002/004939 patent/WO2003038598A1/fr not_active Application Discontinuation
Patent Citations (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US5991415A (en) * | 1997-05-12 | 1999-11-23 | Yeda Research And Development Co. Ltd. At The Weizmann Institute Of Science | Method and apparatus for protecting public key schemes from timing and fault attacks |
WO2001031436A1 (fr) * | 1999-10-28 | 2001-05-03 | Bull Cp8 | Procede de securisation d'un ensemble electronique de cryptographie a base d'exponentiation modulaire contre les attaques par analyse physique |
WO2001048974A1 (fr) * | 1999-12-28 | 2001-07-05 | Giesecke & Devrient Gmbh | Support de donnees portatif a acces protege par repartition des codes |
Non-Patent Citations (3)
Title |
---|
ROOIJ DE P: "EFFICIENT EXPONENTIATION USING PRECOMPUTATION AND VECTOR ADDITION CHAINS", LECTURE NOTES IN COMPUTER SCIENCE, SPRINGER VERLAG, NEW YORK, NY, US, vol. 950, 9 May 1994 (1994-05-09), pages 389 - 399, XP000573612, ISSN: 0302-9743 * |
WALTER C D: "EXPONENTIATION USING DIVISION CHAINS", IEEE TRANSACTIONS ON COMPUTERS, IEEE INC. NEW YORK, US, vol. 47, no. 7, 1 July 1998 (1998-07-01), pages 757 - 765, XP000782019, ISSN: 0018-9340 * |
WALTER C D: "MIST: AN EFFICIENT, RANDOMIZD EXPONENTIATION ALGORITHM FOR RESISTING POWER ANALYSIS", LECTURE NOTES IN COMPUTER SCIENCE, SPRINGER VERLAG, NEW YORK, NY, US, vol. 2271, 18 February 2002 (2002-02-18), pages 53 - 66, XP008004946, ISSN: 0302-9743 * |
Cited By (2)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
EP3166013A1 (fr) * | 2015-11-04 | 2017-05-10 | Nxp B.V. | Exponentiation modulaire à l'aide de chaînes d'addition aléatoire |
US9942038B2 (en) | 2015-11-04 | 2018-04-10 | Nxp B.V. | Modular exponentiation using randomized addition chains |
Also Published As
Publication number | Publication date |
---|---|
GB0126317D0 (en) | 2002-01-02 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
KR101255393B1 (ko) | 타원 곡선 점 곱셈 | |
US6986054B2 (en) | Attack-resistant implementation method | |
Eisenbarth et al. | MicroEliece: McEliece for embedded devices | |
US20170187529A1 (en) | Modular multiplication device and method | |
US20080240443A1 (en) | Method and apparatus for securely processing secret data | |
EP1552382B1 (fr) | Arithmetique efficace dans des corps de galois de caracteristiques impaires dans un materiel binaire | |
JP4086503B2 (ja) | 暗号演算装置及び方法並びにプログラム | |
WO2000067410A1 (fr) | Procede pour prevenir les attaques par analyse de puissance sur des ensembles microelectroniques | |
WO2004036822A1 (fr) | Cryptographie au moyen de champs finis de caracteristique impaire sur du materiel binaire | |
US20110170685A1 (en) | Countermeasure method and devices for asymmetric encryption with signature scheme | |
US11824986B2 (en) | Device and method for protecting execution of a cryptographic operation | |
US20050084098A1 (en) | Method of obscuring cryptographic computations | |
KR100442218B1 (ko) | 몽고메리의 알고리즘을 이용한 멱승 잉여 연산기 | |
RU2276465C2 (ru) | Криптографический способ и чип-карта для его осуществления | |
KR20100113130A (ko) | 비대칭 암호화를 위한 대응조치 방법 및 디바이스 | |
EP0938790B1 (fr) | Processus et dispositif pour l'execution d'un mecanisme de dechiffrement par calcul d'exponentiation modulaire standard pour empecher les attaques relatives a la synchronisation | |
JP2004304800A (ja) | データ処理装置におけるサイドチャネル攻撃防止 | |
EP1443699A1 (fr) | Dispositif de traitement d'informations et carte à puce | |
KR100737667B1 (ko) | 암호 체계의 개인 키 저장 및 복원 방법과 장치 | |
US11973866B2 (en) | Cryptographic processing method, related electronic device and computer program | |
US6609141B1 (en) | Method of performing modular inversion | |
US7983415B2 (en) | Method for performing iterative scalar multiplication which is protected against address bit attack | |
EP4297330A1 (fr) | Procédé et système de protection d'opérations cryptographiques contre des attaques par canaux auxiliaires | |
KR100564599B1 (ko) | 역원 계산 회로, 역원계산 방법 및 상기 역원계산 방법을실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수있는 기록매체 | |
WO2003038598A1 (fr) | Ameliorations apportees a des methodes cryptographiques et appareil faisant appel a une exponentiation |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
AK | Designated states |
Kind code of ref document: A1 Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NO NZ OM PH PL PT RO RU SD SE SG SI SK SL TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW |
|
AL | Designated countries for regional patents |
Kind code of ref document: A1 Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR IE IT LU MC NL PT SE SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG |
|
121 | Ep: the epo has been informed by wipo that ep was designated in this application | ||
122 | Ep: pct application non-entry in european phase | ||
NENP | Non-entry into the national phase |
Ref country code: JP |
|
WWW | Wipo information: withdrawn in national office |
Country of ref document: JP |