Modular exponentiation resistant against skipping attacks

An exponentiation method resistant against skipping attacks. A main idea of the present invention is to evaluate, in parallel with the exponentiation such as y=g d , a value based on the exponent, e.g. f=d·1. These evaluations are performed using the same exponentiation algorithm by “gluing” together the group operations underlying the computation of y and f so that a perturbation to one operation also perturbs the other. This makes it possible to verify that f indeed equals d before returning the result. Also provided are an apparatus and a computer program product.

Method for testing the security of an electronic device against an attack, and electronic device implementing countermeasures

A method of testing security of an electronic device against a combination of a side-channel attack and a fault-injection attack implemented during a method of cryptographic processing that includes: delivering a message signature based on a secret parameter and implementing a recombination of at least two intermediate values according to the Chinese remainder theorem; and verifying the signature on the basis of at least one public exponent. The method of testing includes: transmitting a plurality of messages to be signed by said electronic device; disturbing each message, including modifying the message by inserting an identical error for each message, before executing a step of determining one of the intermediate values; and analyzing physical measurements, obtained during the step of verifying the signature as a function of the message to be signed, the identical error for each message, and an assumption of a value of part of the secret parameter.

PROTECTION OF AN ITERATIVE CALCULATION AGAINST HORIZONTAL ATTACKS

An iterative calculation is performed on a first number and a second number, while protecting the iterative calculation against side-channel attacks. For each bit of the second number, successively, an iterative calculation routine of the bit of the second number is determined. The determination is made independent of a state of the bit. The determined iterative calculation routine of the bit is executed. A result of the iterative calculation is generated based on a result of the execution of the determined iterative calculation routine of a last bit of the second number. 1. A method , comprising: determining, independent of a state of the bit of the second number, an iterative calculation routine of the bit of the second number; and', 'executing the determined iterative calculation routine; and, 'executing, using an electronic circuit, an iterative calculation on a first number and a second number, the executing including protecting the iterative calculation against side-channel attacks by, successively for each bit of the second numbergenerating a result of the iterative calculation based on a result of the determined iterative calculation routine of a last bit of the second number.2. The method of wherein the iterative calculation routine is selected from a set of iterative calculation routines.3. The method of wherein the iterative calculation is a modular exponentiation claim 2 , the second number representing an exponent to be applied to the first number.4. The method of wherein the set of iterative calculation routines comprises:a square-and-multiple always routine; anda Montgomery multiplication routine.5. The method of wherein the determining the iterative calculation routine of a bit of the second number is performed randomly.6. The method of wherein steps of the iterative calculation routine vary according to the state of the bit of the second number.7. The method of claim 1 , comprising:initializing variables stored in a memory prior to executing the ...

System, Apparatus And Method For Performing A Plurality Of Cryptographic Operations

In one embodiment, an apparatus includes: a hardware accelerator to execute cryptography operations including a Rivest Shamir Adleman (RSA) operation and an elliptic curve cryptography (ECC) operation. The hardware accelerator may include: a multiplier circuit comprising a parallel combinatorial multiplier; and an ECC circuit coupled to the multiplier circuit to execute the ECC operation. The ECC circuit may compute a prime field multiplication using the multiplier circuit and reduce a result of the prime field multiplication in a plurality of addition and subtraction operations for a first type of prime modulus. The hardware accelerator may execute the RSA operation using the multiplier circuit. Other embodiments are described and claimed. 1. An apparatus comprising: a multiplier circuit comprising a parallel combinatorial multiplier; and', 'an ECC circuit coupled to the multiplier circuit to execute the ECC operation, the ECC circuit to compute a prime field multiplication using the multiplier circuit and to reduce a result of the prime field multiplication in a plurality of addition and subtraction operations for a first type of prime modulus, wherein the hardware accelerator is to execute the RSA operation using the multiplier circuit., 'a hardware accelerator to execute cryptography operations including a Rivest Shamir Adleman (RSA) operation and an elliptic curve cryptography (ECC) operation, the hardware accelerator comprising2. The apparatus of claim 1 , wherein the ECC circuit is to reduce a result of the prime field multiplication in a plurality of multiplication operations for a second type of prime modulus.3. The apparatus of claim 1 , wherein the multiplier circuit comprises a 27-bit×411-bit parallel combinatorial multiplier to multiply a first 384-bit value and a second 384-bit value in 16 clock cycles.4. The apparatus of claim 1 , wherein the hardware accelerator is to isolate first and second portions of first and second values and send the isolated ...

TESTING RESISTANCE OF A CIRCUIT TO A SIDE CHANNEL ANALYSIS

In a general aspect, a test method can include: acquiring a plurality of value sets, each comprising values of a physical quantity or of logic signals, linked to the activity of a circuit to be tested when executing distinct cryptographic operations applied to a same secret data, for each value set, counting occurrence numbers of the values of the set, for each operation and each of the possible values of a part of the secret data, computing a partial result of operation, computing sums of occurrence numbers, each sum being obtained by adding the occurrence numbers corresponding to the operations which when applied to a same possible value of the part of the secret data, provide a partial operation result having a same value, and analyzing the sums of occurrence numbers to determine the part of the secret data. 1. A test method comprising:acquiring a plurality of value sets, each value set comprising values of a physical quantity, or of logic signals linked to activity of a circuit to be tested when the circuit executes an operation of an operation set of distinct cryptographic operations applied to a same data to be discovered;for each value set, counting, by a processing unit, occurrence numbers of values transformed by a first surjective function applied to values of the value set, to form an occurrence number set for the value set;for each operation of the operation set, and each possible value of a part of the data to be discovered, computing, by the processing unit, results of at least two distinct partial operations;computing, by the processing unit, for each partial operation result, cumulative occurrence number sets, each cumulative occurrence number set being obtained by adding together the occurrence number sets corresponding to the operations of the operation set, which, when applied to a same value or equivalent value of the possible values of the part of the data to be discovered, provide a partial operation result having a same transformed value ...

PROTECTION OF A MODULAR EXPONENTIATION CALCULATION

A method of protecting a modular exponentiation calculation on a first number and an exponent, modulo a first modulo, executed by an electronic circuit using a first register or memory location and a second register or memory location, successively including, for each bit of the exponent: generating a random number; performing a modular multiplication of the content of the first register or memory location by that of the second register or memory location, and placing the result in one of the first and second registers or memory locations selected according to the state of the bit of the exponent; performing a modular squaring of the content of one of the first and second registers or memory locations selected according to the state of the exponent, and placing the result in this selected register or memory location, the multiplication and squaring operations being performed modulo the product of the first modulo by said random number. 1. A method , comprising:performing, using an electronic circuit, a modular exponentiation calculation on a first number and an exponent, modulo a first modulo by, for each bit of the exponent:generating a random number;performing a modular multiplication of content of a first memory location by content of a second memory location, and placing a result in one of the first and second memory locations selected according to a state of the bit of the exponent; andperforming a modular squaring of the content of one of the first and second memory locations selected according to the state of the exponent, and placing the result in this selected register or memory location,the multiplication and squaring operations being performed modulo a product of the first modulo and said random number.2. The method of wherein a result of the modular exponentiation calculation is contained in said first memory location.3. The method of claim 1 , comprising:initializing the first memory location to value 1; andinitializing the second memory location to a ...

VERIFICATION OF THE SENSITIVITY OF AN ELECTRONIC CIRCUIT EXECUTING A MODULAR EXPONENTIATION CALCULATION

A method of verifying the sensitivity of an electronic circuit executing a modular exponentiation calculation in a first register and a second register, successively including, for each bit of the exponent: a first step of multiplying the content of one of the registers, selected from among the first register and the second register according to the state of the bit of the exponent, by the content of the other one of the first and second registers, placing the result in said one of the registers; a second step of squaring the content of said other one of the registers by placing the result in this other register, wherein the content of that of the first and second registers which contains the multiplier of the operation of the first step is disturbed, for each bit of the exponent, during the execution of the first step. 1. A method , comprising:verifying a sensitivity of an electronic circuit executing a modular exponentiation calculation using a first register and a second register, wherein: multiplying content of one of the registers, selected from among the first register and the second register according to a state of a current bit of the exponent, by content of the other one of the first and second registers, and placing a result of the multiplication in said one of the first and second registers; and', 'squaring content of said other one of the first and second registers and placing a result of the squaring in the other of the first and second registers; and, 'the executing the modular exponentiation calculation includes, successively for each bit of an exponent of the calculation disturbing, for each bit of the exponent of the calculation, content of at least one of the first and second registers during the multiplying; and', 'determining the sensitivity of the electronic circuit based on disturbed results of the modular exponentiation calculation., 'the verifying includes2. The method of wherein the multiplying is implemented using a Montgomery ladder.3. The ...

Protection of a modular exponentiation calculation

A method of protecting a modular exponentiation calculation executed by an electronic circuit using a first register and a second register, successively comprising, for each bit of the exponent: a first step of multiplying the content of one of the registers, selected from among the first register and the second register according to the state of the bit of the exponent, by the content of the other one of the first and second registers, placing the result in said one of the registers; a second step of squaring the content of said other one of the registers by placing the result in this other register, wherein the content of said other one of the registers is stored in a third register before the first step and is restored in said other one of the registers before the second step.

METHOD TO SECURELY EXECUTE A MODULAR EXPONENTIATION

The present invention relates to a method to execute a modular exponentiation R=Xmod N, said method implementing several variable registers and an indicator register m and performing looped calculations. In the invention each loop includes at least two operations from values stored in variable registers, said operations depending on the value stored in m and on the value of the bit(s) of the exponent currently processed, m indicating if the calculation is completed for the current exponent bit at the end of the operations in the current loop. 2. Method according to claim 1 , wherein said termination step returns an error message when eis null and the value in m indicates the calculation is not completed for the current exponent bit claim 1 , returns the result of a last square operation of the current intermediate result if eis null and the value in m indicates the calculation is completed for the current exponent bit claim 1 , returns the result of a last square of the current intermediate result and a last multiplication of the current intermediate result by X if e=1 and the value if m indicates the calculation is completed for the current exponent bit claim 1 , returns the result of a last operation of multiplication of the current intermediate result by X if e=1 and the value in m indicates the calculation is not completed for the current exponent bit.3. Method according to claim 1 , wherein two variable registers Rand Rare used claim 1 , step a) including the initialization of Rand Rto 1 and X and step c) comprising performing the following operations:{'br': None, 'i': R', 'R', '·R', 'N;, 'sub': 0', '0', 'm, '<-mod'}{'br': None, 'i': R', 'R', '·R', 'N., 'sub': 0', '0', 'ei&', 'm, 'img': {'@id': 'CUSTOM-CHARACTER-00011', '@he': '2.46mm', '@wi': '1.78mm', '@file': 'US20160077806A1-20160317-P00001.TIF', '@alt': 'custom-character', '@img-content': 'character', '@img-format': 'tif'}, '<-mod'}4. Method according to claim 1 , wherein an additional register is used for ...

EXPONENT SPLITTING FOR CRYPTOGRAPHIC OPERATIONS

A first share value and a second share value may be received. A combination of the first share value and the second share value may correspond to an exponent value. The value of a first register is updated using a first equation that is based on the first and second share values and the value of a second register is updated using a second equation that is based on the second share value. One of the value of the first register or the value of the second register is selected based on a bit value of the second share value. 120-. (canceled)21. A method comprising:receiving a first share value and a second share value, wherein a combination of the first share value and the second share value corresponds to a value associated with a cryptographic operation;updating a first value of a first register by performing a first operation with the first and second share values;updating a second value of a second register by performing a second operation with the second share value;selecting, by a processing device, one of the first value of the first register or the second value of the second register based on a particular bit of the second share value; andperforming the cryptographic operation with the selected one of the first value of the first register or the second value of the second register.22. The method of claim 21 , wherein the particular bit corresponds to a least significant bit of the second share value.23. The method of claim 21 , wherein the particular bit corresponds to a most significant bit of the second share value.24. The method of claim 21 , wherein the cryptographic operation corresponds to a generation of a signature.25. The method of claim 21 , wherein the value associated with the cryptographic operation corresponds to an exponent value used in the cryptographic operation.26. The method of claim 21 , wherein the first operation and the second operation are each associated with power consumption to reduce susceptibility to a Differential Power Analysis ( ...

PROCESSING DEVICE, ACCELERATOR, AND METHOD FOR FEDERATED LEARNING

A processing device for federated learning, including: a modular exponentiation module including at least one modular exponentiation engine; a pre-processing module for providing operations corresponding to a plurality of operator modes; a montgomerization module for providing montgomerization operations; a confusion calculation module for providing modular multiplication operations in montgomery space; a montgomery reduction module for providing montgomery reduction operations; and a controller for determining, according to an input operator mode, whether to enable at least two modules out of the pre-processing module, the montgomerization module, the confusion calculation module, and the montgomery reduction module, so as for cooperatively performing the input operator mode together with the modular exponentiation module. 1. A processing device for federated learning comprising:a modular exponentiation module comprising at least one modular exponentiation engine;a pre-processing module configured for providing operations corresponding to a plurality of operator modes;a montgomerization module configured for providing montgomerization operations;a confusion calculation module configured for providing modular multiplication operations in montgomery space;a montgomery reduction module configured for providing montgomery reduction operations; anda controller for:determining, according to an input operator mode, whether to enable at least two modules out of the pre-processing module, the montgomerization module, the confusion calculation module, and the montgomery reduction module, so as for cooperatively performing the input operator mode together with the at least one modular exponentiation engine of the modular exponentiation module,wherein the input operator mode is one of the plurality of operator modes,wherein performing modular exponentiation operations by the modular exponentiation module comprises: shifting bit-by-bit from a highest non-zero bit to a lowest ...

ELECTRONIC CALCULATING DEVICE ARRANGED TO CALCULATE THE PRODUCT OF INTEGERS

An electronic calculating device () arranged to calculate the product of integers, the device comprising a storage () configured to store integers () in a multi-layer residue number system (RNS) representation, the multi-layer RNS representation having at least an upper layer RNS and a lower layer RNS, the upper layer RNS being a residue number system for a sequence of multiple upper moduli (M), the lower layer RNS being a residue number system for a sequence of multiple lower moduli (m), an integer (x) being represented in the storage by a sequence of multiple upper residues (x=(x)) modulo the sequence of upper moduli (M), upper residues (x) for at least one particular upper modulus (M) being further-represented in the storage by a sequence of multiple lower residues ((x)) of the upper residue (x) modulo the sequence of lower moduli (m), wherein at least one of the multiple lower moduli (m) does not divide a modulus of the multiple upper moduli (M). 1. An electronic calculating device arranged to calculate the product of integers , the device comprising{'sub': i', 'i', 'i', 'M', {'sub2': 'i'}, 'i', 'j', 'j', 'j', 'm', {'sub2': 'i'}, 'j', 'i', 'i', 'j, 'img': [{'@id': 'CUSTOM-CHARACTER-00053', '@he': '3.22mm', '@wi': '0.68mm', '@file': 'US20200097257A1-20200326-P00001.TIF', '@alt': 'custom-character', '@img-content': 'character', '@img-format': 'tif'}, {'@id': 'CUSTOM-CHARACTER-00054', '@he': '3.22mm', '@wi': '0.68mm', '@file': 'US20200097257A1-20200326-P00002.TIF', '@alt': 'custom-character', '@img-content': 'character', '@img-format': 'tif'}, {'@id': 'CUSTOM-CHARACTER-00055', '@he': '3.22mm', '@wi': '0.68mm', '@file': 'US20200097257A1-20200326-P00001.TIF', '@alt': 'custom-character', '@img-content': 'character', '@img-format': 'tif'}, {'@id': 'CUSTOM-CHARACTER-00056', '@he': '3.22mm', '@wi': '0.68mm', '@file': 'US20200097257A1-20200326-P00002.TIF', '@alt': 'custom-character', '@img-content': 'character', '@img-format': 'tif'}], 'a storage configured to store ...

System, Apparatus And Method For Performing A Plurality Of Cryptographic Operations

In one embodiment, an apparatus includes a hardware accelerator to execute cryptography operations including a Rivest Shamir Adleman (RSA) operation and an elliptic curve cryptography (ECC) operation. The hardware accelerator may include a multiplier circuit comprising a parallel combinatorial multiplier, and an ECC circuit coupled to the multiplier circuit to execute the ECC operation. The ECC circuit may compute a prime field multiplication using the multiplier circuit and reduce a result of the prime field multiplication in a plurality of addition and subtraction operations for a first type of prime modulus. The hardware accelerator may execute the RSA operation using the multiplier circuit. Other embodiments are described and claimed. 1. At least one computer readable storage medium having stored thereon instructions , which if performed by a machine cause the machine to perform a method comprising:receiving, in a controller of a hardware cryptographic circuit, a request to perform an elliptic curve cryptography (ECC) operation;in response to the request, causing, by the controller, a hardware multiplication circuit of the hardware cryptographic circuit to perform an integer multiplication on a first operand and a second operand to obtain a first result, wherein the first and second operands comprise first and second 384-bit values, respectively, and the multiplication circuit comprises a 27-bit×411-bit parallel combinatorial multiplier;determining whether a modulus reduction operation for the ECC operation is to be performed according to a National Institute of Standards and Technology (NIST) prime value; andin response to determining that the modulus reduction operation is to be performed according to the NIST prime value, performing the modulus reduction operation comprising a plurality of addition and subtraction operations, and without performing any multiplication or division operations.2. The at least one computer readable storage medium of claim 1 , ...

ASYMMETRICALLY MASKED MULTIPLICATION

Methods and systems for masking certain cryptographic operations in a manner designed to defeat side-channel attacks are disclosed herein. Squaring operations can be masked to make squaring operations indistinguishable or less distinguishable from multiplication operations. In general, squaring operations are converted into multiplication operations by masking them asymmetrically. Additional methods and systems are disclosed for defeating DPA, cross-correlation, and high-order DPA attacks against modular exponentiation. 132.-. (canceled)33. A system comprising:at least one processor; and receiving at least one input value;', 'defining a left-hand-side (LHS) parameter using at least one of the input values;', 'defining a right-hand-side (RHS) parameter using at least one of the input values;', 'calculating a plurality of intermediate values, including a first intermediate value based on the LHS parameter and a second intermediate value based on the RHS parameter, wherein at least one of the first intermediate value and the second intermediate value is calculated based on a mask value; and', 'applying a fix value to at least one of the plurality of intermediate values to generate an output value comprising a multiplication product of at least one unmasked value of the input value used to define the LHS parameter or the RHS parameter., 'a non-transitory computer-readable medium having instructions stored thereon that, when executed on the processor, asymmetrically masks a cryptographic operation to improve resistance to third party attacks by being configured to perform the steps of34. The system of claim 33 , wherein the input value used to define the LHS parameter is different from the input value used to define the RHS parameter claim 33 , andwherein the output value comprises a multiplication product of the input value used to define the LHS parameter and the input value used to define the RHS parameter.35. The system of claim 33 , the instructions further being ...

Modular Exponentiation Using Randomized Addition Chains

Various embodiments relate to a device for generating code which implements modular exponentiation, the device including: a memory used to store a lookup table; and a processor in communication with the memory, the processor configured to: receive information for a generated randomized addition chain; output code for implementing the modular exponentiation which loads elements from the lookup table including intermediate results which utilize the information for a generated randomized addition chain; and output code for implementing the modular exponentiation which uses the loaded elements to compute the next element.

Obfuscating cryptographic parameters used in elliptical curve cryptography, and related systems and devices

An obfuscation process is described for obfuscating a cryptographic parameter of cryptographic operations such as calculations used in elliptical curve cryptography and elliptical curve point multiplication. Such obfuscation processes may be used for obfuscating device characteristics that might otherwise disclose information about the cryptographic parameter, cryptographic operations or a cryptographic operations more generally, such as information sometimes gleaned from side channel attacks and lattice attacks.

Outsourcing Exponentiation in a Private Group

A method for outsourcing exponentiation in a private group includes executing a query instruction to retrieve a query element stored on an untrusted server by selecting a prime factorization of two or more prime numbers of a modulus associated with the query element stored on the server, obtaining a group element configured to generate a respective one of the prime numbers, generating a series of base values using the prime factorization and the group element, and transmitting the series of base values from the client device to the server. The server is configured to determine an exponentiation of the group element with an exponent stored on the server using the series of base values. The method also includes receiving a result from the server based on the exponentiation of the group element with the exponent. 1. A computer-implemented method when executed by data processing hardware of a server causes the data processing hardware to perform operations comprising:obtaining a positional base indicative of a numeral position system;determining a server-held exponent based on the positional base, the server-held exponent representative of a plurality of data blocks stored on memory hardware in communication with the data processing hardware;determining a positional count of the server-held exponent, the positional count indicative of a number of digits of the server-held exponent using the numeral position system indicated by the positional base;transmitting the positional count to a client device;receiving, from the client device, a series of base values, the series of base values based on the positional count and a group element representative of one of the plurality of data blocks;determining, using the series of base values and the server-held exponent, a result associated with the one of the plurality of data blocks without revealing an identity of the one of the plurality of data blocks to the server; andtransmitting the result to the client device.2. The method ...

Asymmetrically masked multiplication

Methods and systems for masking certain cryptographic operations in a manner designed to defeat side-channel attacks are disclosed herein. Squaring operations can be masked to make squaring operations indistinguishable or less distinguishable from multiplication operations. In general, squaring operations are converted into multiplication operations by masking them asymmetrically. Additional methods and systems are disclosed for defeating DPA, cross-correlation, and high-order DPA attacks against modular exponentiation.

Providing security against user collusion in data analytics using random group selection

Methods for secure random selection of t client devices from a set of N client devices and methods for secure computation of inputs of t client devices randomly selected from N client devices are described. Such random selection method may include determining an initial binary vector b of weight t by setting the first t bits to one: b=1, 1 ≤i≤t, and all further bits to zero: b=0, t Подробнее

Systems and Methods for Efficient Fixed-Base Multi-Precision Exponentiation

Systems and methods for efficient fixed-base multi-precision exponentiation are disclosed herein. An example method includes applying a multi-precision exponentiation algorithm to a base number, the multi-precision exponentiation algorithm comprises a pre-generated lookup table used to perform calculations on the base number, the pre-generated lookup table comprising pre-calculated exponentiated values of the base number. 1. A method , comprising: applying a multi-precision exponentiation algorithm to a base number , the multi-precision exponentiation algorithm comprising a pre-generated lookup table used to perform calculations on the base number , the pre-generated lookup table comprising pre-calculated exponentiated values of the base number.2. The method according to claim 1 , further comprising:identifying the base number as having a size that is more than 64 bits; anddetermining if a time required for using the multi-precision exponentiation algorithm is less than a time required to perform the calculations of the base number directly using exponents; andwherein the multi-precision exponentiation algorithm is used only when the time required for using the multi-precision exponentiation algorithm is less than the time required to perform the calculations of the base number directly using exponents.3. The method according to claim 1 , wherein the lookup table is pre-generated.4. The method according to claim 1 , further comprising determining that a base number has a size that exceeds a size threshold claim 1 , wherein the size threshold is greater than 64 bits.5. The method according to claim 1 , further comprising selecting the exponents that will be used to exponentiate the base number.6. The method according to claim 1 , further comprising converting the base number into a form suitable for use in an encryption algorithm.7. The method according to claim 1 , wherein determining if a time required for using the multi-precision exponentiation algorithm is less ...

Minimizing information leakage during modular exponentiation and elliptic curve point multiplication

Minimizing information leakage during modular exponentiation using random masks is disclosed Minimizing information leakage during elliptic curve point multiplication is disclosed with windowing by using point randomization is disclosed. Elliptic curve point multiplication with windowing calculates and stores multiple points based on the point being multiplied and then processes multiple bits of the multiplier at a time is also disclosed.

EXPONENT SPLITTING FOR CRYPTOGRAPHIC OPERATIONS

A first share value and a second share value may be received. A combination of the first share value and the second share value may correspond to an exponent value. The value of a first register is updated using a first equation that is based on the first and second share values and the value of a second register is updated using a second equation that is based on the second share value. One of the value of the first register or the value of the second register is selected based on a bit value of the second share value. 1. A method comprising:receiving a first share value and a second share value, wherein a combination of the first share value and the second share value corresponds to an exponent value;updating a value of a first register using a first equation that is based on the first and second share values;updating a value of a second register using a second equation that is based on the second share value; andselecting, by a processing device, one of the value of the first register or the value of the second register based on a bit value of the second share value.2. The method of claim 1 , wherein the combination of the first share value and the second share value that corresponds to the exponent value is a logical or arithmetic operation between the first share value and the second share value.3. The method of claim 1 , further comprising:performing a cryptographic operation based on the selected value of the first or second register.4. The method of claim 3 , wherein the selected value of the first or second register corresponds to a group exponentiation based on the exponent value that corresponds to the first share value and the second share value claim 3 , and wherein the cryptographic operation is further based on the group exponentiation.5. The method of claim 1 , wherein the bit value of the second share value is the least significant bit or the most significant bit of the second share value.6. The method of claim 1 , wherein the value of the first ...

SYSTEM AND METHOD FOR ONE-TIME CHINESE-REMAINDER-THEOREM EXPONENTIATION FOR CRYPTOGRAPHIC ALGORYTHMS

A system, method and computer-readable storage medium with instructions for protecting an electronic device against fault attack. The technology includes operating the electronic device to determine two half-size exponents, dp and dq, from the exponent d; to split the base m into two sub-bases mp and mq determined from the base m; and to iteratively compute a decryption result S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration I′. Other systems and methods are disclosed. 1. A method for operating a cryptography apparatus to perform a decryption operation having an exponentiation operation X , the method protecting the apparatus from revealing information in regard to the exponentiation operation X when the operation is exposed to a fault attack while being executed on the cryptography apparatus , the method comprising producing a result equivalent to the exponentiation by:{'sup': 'd', 'receiving, on the cryptography apparatus, a message m on which to perform a cryptographic operation equivalent to the exponentiation operation S=mmod n;'}determining two half-size exponents from the exponent d;splitting the base m into two sub-bases mp and mq determined from the base m;iteratively computing S by repeatedly multiplying an accumulator A by m, mp, mq or 1 depending on the values of the i-th bit of dp and dq for each iteration i;returning as the value S the final value of the accumulator A; and completing the cryptographic operation using the value S obtained from the operation.2. The method of wherein the two half-sized exponents are dp and dq such that dp=d mod (p−1) and dq=d mod (q−1) where p and q are prime numbers such that n=pq.3. The method of wherein:{'br': None, 'i': mp=', 'q*iq', 'm−', 'n, '1+*(1)mod ; and'}{'br': None, 'i': mq=', 'q*iq', 'm−', 'n, '1+(1−)*(1)mod wherein'}{'br': None, 'i': iq=q', 'p., 'sup': '−1', 'mod'}4. The method of wherein dp and dq have bits indexed from 0 ...

Method for electronic signing of a documen with a predetermined secret key

The present invention relates to a method for electronic signing of a document with a predetermined secret key (x), the method being characterized in that it comprises the implementation of steps of: (a) Drawing a pair formed by a first internal state (s 1 i ) and a white-box implementation (WB i ) of a modular arithmetic operation, from among a set of predetermined pairs ({(s 1 i ,WB i )} i∈[0,n-1] ) each for one nonce (k i ), said first internal state (s 1 i ) being a function of the nonce (k i ) and said modular arithmetic operation being a function of the first internal state (s 1 i ), of the nonce (k i ) and of the secret key (x); (b) Determining a second internal state (s 2 i ) by application of said drawn white-box implementation (WB i ) to a condensate of the document obtained via a given hash function; (c) Generating an electronic signature of the document from the first internal state (s 1 i ) of the drawn pair and from the second determined internal state (s 2 i ), and deleting the drawn pair of said set of pairs ({(s 1 i ,WB i )} i∈[0,n-1] ).

MULTIPLIER PIPELINING OPTIMIZATION WITH A BIT FOLDING CORRECTION

One embodiment provides a system. The system includes a register to store an operand; a multiplier; and optimizer logic to initiate a square/multiply stage to operate on the operand, initiate a reduction stage prior to completion of the square/multiply stage, and determine whether a carry propagation has occurred. 1. A system comprising:a register to store an operand;a multiplier; andoptimizer logic to initiate a square/multiply stage to operate on the operand, initiate a reduction stage prior to completion of the square/multiply stage, and determine whether a carry propagation has occurred.2. The system of claim 1 , wherein the optimizer logic is further to perform a bit folding correction of a result of the reduction stage if the carry propagation has occurred.3. The system of claim 1 , wherein the optimizer logic is further to reorder provision of a plurality of elements of the operand to the multiplier claim 1 , the reordering to reduce a likelihood that the carry propagation will occur.4. The system of claim 1 , wherein the multiplier is to perform a plurality of pipelined multiplications of a plurality of elements of the operand.5. The system of claim 1 , further comprising modular exponentiation (ME) logic and a parameter store claim 1 , the ME logic to precompute a constant parameter m′ and to store the constant parameter in the parameter store.6. The system of claim 1 , wherein the operand is related to modular exponentiation.7. The system of claim 1 , wherein the reduction stage is related to a modified Barrett reduction.8. A method comprising:initiating, by optimizer logic, a square/multiply stage to operate on an operand;initiating, by the optimizer logic, a reduction stage prior to completion of the square/multiply stage; anddetermining, by the optimizer logic, whether a carry propagation has occurred.9. The method of claim 8 , further comprising:performing, by the optimizer logic, a bit folding correction of a result of the reduction stage if the carry ...

Dynamic Channels in Secure Queries and Analytics

Systems and methods for end-to-end encryption and dynamic resizing and encoding into grouped byte channels are described herein. A query is homomorphically encrypted at a client using dynamic channel techniques. The encrypted query is sent without a private key to a server for evaluation over target data to generate encrypted response without decrypting the encrypted query. The result elements of the encrypted response are grouped, co-located, and dynamically resized and encoded into grouped byte channels using the dynamic channel techniques, without decrypting the encrypted query or the encrypted response. The encrypted response is sent to the client where the client uses the private key and channel extraction techniques associated with the dynamic channel techniques to decrypt and perform channel extraction on the encrypted response to obtain the results of the query without revealing the query or results to a target data owner, an observer, or an attacker.

System and method for providing defence to a cryptographic device against side-channel attacks targeting the extended euclidean algorithm during decryption operations

A system, method and computer-readable storage medium for decrypting a code c using a modified Extended Euclidean Algorithm (EEA) having an iteration loop independent of the Hamming weight of inputs to the EEA and performing a fixed number of operations regardless of the inputs to the EEA thereby protecting a cryptographic device performing the decryption from side-channel attacks.

A COMPUTATION DEVICE AND METHOD

Some embodiments are directed to an electronic computation device () arranged for obfuscated execution of a multiplication. The device comprises a storage () arranged for storing multiple variables used in the execution of an arithmetic operation, a variable (x: y; 2) of the multiple variables being represented as multiple multiplicative shares (X=(x, x, . . . , x); Y=(y, y, . . . , y); ), said multiplicative shares being represented in the storage as multiple additive shares (x=(x,x, . . . , x); Yi=(y,0,y, . . . , y); ). 1. An computation device arranged for obfuscated execution of a multiplication , comprising: wherein the memory circuit is arranged to store a plurality of variables,', {'sub': 0', '1', 'm−1', '0', '1', 'm−1, 'wherein each variable (x;y) of the plurality of variables are represented as one or more multiplicative shares (X=(x, x, . . . , x); Y=(y,y, . . . , y)),'}, {'sub': i', 'i,0', 'i,1', 'i,n−1', 'i', 'i,0', 'i,1', 'i,n−1, 'wherein the multiplicative shares are represented as a plurality of additive shares (X=(x, x, . . . , x); Y=(y, y, . . . , y))'}], 'a memory circuit,'}a processor circuit, wherein the processor circuit is configured to multiply a first variable of the plurality of variables with a second variable of the plurality of variables to obtain a multiplication result (z=xy), the multiplying comprising:{'sub': i', 'i', 'i', 'i', 'i, 'for each multiplicative share of the first variable, computing a convolution (Z=X*Y) of the additive shares representing the multiplicative share of the first variable (X) and the additive shares representing the corresponding multiplicative shares of the second variable (Y),'}{'sub': 'i', 'storing the result of the convolutions as a plurality of additive shares (Z) in the memory circuit as a representation in additive shares of at least one multiplicative share of the multiplication result (z).'}2. The computation device as in claim 1 , further comprising a communication interface claim 1 , wherein the ...

Exponent splitting for cryptographic operations

A first share value and a second share value may be received. A combination of the first share value and the second share value may correspond to an exponent value. The value of a first register is updated using a first equation that is based on the first and second share values and the value of a second register is updated using a second equation that is based on the second share value. One of the value of the first register or the value of the second register is selected based on a bit value of the second share value.

Rsa algorithm acceleration processors, methods, systems, and instructions

A processor includes a decode unit to decode an instruction. The instruction indicates a first 64-bit source operand having a first 64-bit value, indicates a second 64-bit source operand having a second 64-bit value, indicates a third 64-bit source operand having a third 64-bit value, and indicates a fourth 64-bit source operand having a fourth 64-bit value. An execution unit is coupled with the decode unit. The execution unit is operable, in response to the instruction, to store a result. The result includes the first 64-bit value multiplied by the second 64-bit value added to the third 64-bit value added to the fourth 64-bit value. The execution unit may store a 64-bit least significant half of the result in a first 64-bit destination operand indicated by the instruction, and store a 64-bit most significant half of the result in a second 64-bit destination operand indicated by the instruction.

SECURE COMPUTATION APPARATUS, SYSTEM, METHOD AND PROGRAM

A bit-decomposition secure computation apparatus uses r1, r2, and r3 satisfying w=r1+r2+r3 mod 2{circumflex over ( )}n as share information of (2, 3) threshold type RSS (Replicated Secret Sharing) stored in a share value storage apparatus, and includes an addition sharing part that sums two values out of the share information by modulo 2{circumflex over ( )}n arithmetic and distributes the sum using (2, 3) type RSS; and a full adder secure computation part that adds the value generated by the addition sharing part by distributing the sum of the two values to share information of one remaining value other than the two values used by the addition sharing part for each digit by using secure computation of a full adder. 1. A secure computation apparatus comprising:a share value storage apparatus that stores share values obtained by using (2, 3) threshold type RSS (Replicated Secret Sharing) with modulo 2 to the power of n;a decomposed share value storage apparatus that stores a sequence of share values obtained by using (2, 3) threshold type RSS with modulo 2; anda bit-decomposition secure computation apparatus including a processor and a memory storing program instructions executable by the first processor, whereinthe processor included in the bit-decomposition secure computation apparatus is configured towith respect to a value w, use r1, r2, and r3 satisfying w=r1+r2+r3 mod 2{circumflex over ( )}n (where mod is a modulo operation; n is an integer of 2 or more, and {circumflex over ( )} is a power operator), as share information of (2, 3) threshold type RSS stored in the share value storage apparatus, and execute:an addition sharing process that sums two values out of the share information by modulo 2{circumflex over ( )}n arithmetic and distributes the sum using (2, 3) threshold type RSS; anda full adder secure computation process that adds a share value of the sum of the two values generated by the addition sharing process to share information of one remaining value ...

APPARATUS AND METHOD FOR PERFORMING OPERATION BEING SECURE AGAINST SIDE CHANNEL ATTACK

An apparatus and method for performing operation being secure against side channel attack are provided. The apparatus and method generate values equal to values obtained through an exponentiation operation or a scalar multiplication operation of a point using values extracted from previously generated parameter candidate value sets and an operation secure against side-channel attack, thereby improving security against side-channel attack without degrading performance. 1. An apparatus comprising: a seed value generator configured to generate a seed value;', 'a divider configured to divide the seed value into a plurality of blocks;', 'a first extractor configured to extract a plurality of first parameter values from a first parameter candidate value set including a plurality of first parameter candidate values, each of the plurality of first parameter values respectively corresponding to one of the plurality of divided blocks;', 'a second extractor configured to extract a plurality of second parameter values from a second parameter candidate value set including a plurality of second parameter candidate values generated by using each of the plurality of first parameter candidate values included in the first parameter candidate value set, each of the plurality of second parameter values respectively corresponding to one of the plurality of divided blocks;', 'a third extractor configured to extract a plurality of third parameter values from a third parameter candidate value set including a plurality of third parameter candidate values generated by using each of the plurality of second parameter candidate values included in the second parameter candidate value set, each of the plurality of third parameter values respectively corresponding to one of the plurality of divided blocks; and', 'a calculator configured to generate a first random number based on the plurality of first parameter values, generate a second random number based on the plurality of second parameter ...

Cryptographic Accelerator

A cryptographic accelerator performs various modular arithmetic operations producing unreduced results bounded by the double of the modulus (i.e.: 2*M). In doing so, various processing elements of an ALU of the cryptographic accelerator can begin to process respective data word portions of a modular arithmetic operations before the entirety of one or more operands are loaded. Similarly, various processing elements may begin to store their respective data word portions of a modular arithmetic result before the entirety of the result is calculated.

QUANTUM RESOURCE ESTIMATES FOR COMPUTING ELLIPTIC CURVE DISCRETE LOGARITHMS

In this application, example methods for performing quantum Montgomery arithmetic are disclosed. Additionally, circuit implementations are disclosed for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. This application also shows that elliptic curve discrete logarithms on an elliptic curve defined over an n-bit prime field can be computed on a quantum computer with at most 9n+2 ┌log(n)┐+10 qubits using a quantum circuit of at most 512nlog(n)+3572nToffoli gates. 1. A computer-implemented method , comprising:inputting a prime number;generating reversible circuits for performing a modular arithmetic operation on the prime number, the modular arithmetic operation being one of addition, subtraction, multiplication, or division; andstoring the reversible circuits as quantum-computer executable instructions.2. The method of claim 1 , further comprising configuring a quantum computer to implement the reversible circuits using the quantum-computer executable instructions.3. The method of claim 1 , wherein the data on which the modular arithmetic operation acts is encoded using Montgomery encoding for the underlying prime number.4. The method of claim 1 , wherein the modular arithmetic operation performed is addition claim 1 , and wherein the addition operation is implemented using a quantum circuit for integer addition claim 1 , followed by a reversible circuit that tests for overflows and reduces an output modulo by the prime number if necessary.5. The method of claim 1 , wherein the modular arithmetic operation performed is subtraction claim 1 , and wherein the subtraction operation is implemented using a quantum circuit for integer addition claim 1 , followed by a reversible circuit that tests for overflows and reduces an output modulo by the prime number if necessary.6. The method of claim 1 , wherein the modular arithmetic operation performed is multiplication claim 1 , and ...

ENCRYPTING AND DECRYPTING UNIT FOR RSA CRYPTOGRAPHIC SYSTEM, RESISTANT TO FAULTS INJECTION

A digital encrypting and decrypting unit (PMEU) that operates according to a Rivest-Shamir-Adleman (RSA) cryptosystem based on Residue Numeral System (RNS) and Chinese Reminder Theorem (CRT). The unit includes two modular exponentiation calculating units (MES-, MES-) to process a two residual signals (X mod p; X mod q) to calculate a result of a modular exponentiation by a binary method. The calculating units have inputs (I-k[i], I-SM, I-MM) and outputs (O-k[i], O-SM, O-MM) for signals representing partial results of the modular exponentiation. A modular exponentiation controlling unit (MECU) is connected to the inputs and outputs of the calculating units to control flow of the signals representing the partial results of the modular exponentiation. 1a first modular exponentiation calculating unit configured to process a first residual signal to calculate a result of a modular exponentiation by a binary method;a second modular exponentiation calculating unit configured to process a second residual signal to calculate a result of a modular exponentiation by a binary method;wherein the first modular exponentiation calculating unit and the second modular exponentiation calculating unit have inputs and outputs for signals representing partial results of the modular exponentiation; when the clock signal has a first level, directing the signals representing the partial results of the modular exponentiation from the outputs of the first modular exponentiation calculating unit to the inputs of the second modular exponentiation calculating unit and directing the signals representing the partial results of the modular exponentiation from the outputs of the second modular exponentiation calculating unit to the inputs of the first modular exponentiation calculating unit; and', 'when the clock signal has a second level, directing the signals representing the partial results of the modular exponentiation from the outputs of the first modular exponentiation calculating unit to the ...

Outsourcing Exponentiation in a Private Group

A method for outsourcing exponentiation in a private group includes executing a query instruction to retrieve a query element stored on an untrusted server by selecting a prime factorization of two or more prime numbers of a modulus associated with the query element stored on the server, obtaining a group element configured to generate a respective one of the prime numbers, generating a series of base values using the prime factorization and the group element, and transmitting the series of base values from the client device to the server. The server is configured to determine an exponentiation of the group element with an exponent stored on the server using the series of base values. The method also includes receiving a result from the server based on the exponentiation of the group element with the exponent. 1. A method comprising: selecting a prime factorization of a modulus associated with the query element stored on the untrusted server, the prime factorization comprising two or more prime numbers;', 'obtaining a group element configured to generate a respective one of the two or more prime numbers of the prime factorization;', 'generating a series of base values using the prime factorization of the modulus and the group element; and', 'transmitting the series of base values from the client device to the untrusted server, the untrusted server configured to determine an exponentiation of the group element with an exponent stored on the untrusted server using the series of base values; and, 'executing, at data processing hardware of a client device, a query instruction to retrieve a query element stored on an untrusted server byreceiving, at the data processing hardware, a result from the untrusted server, the result based on the exponentiation of the group element with the exponent stored on the untrusted server.2. The method of claim 1 , wherein: generating a series of initial base values using the prime factorization of the modulus and the group element; and', ...

METHOD FOR DETERMINING A MODULAR INVERSE AND ASSOCIATED CRYPTOGRAPHIC PROCESSING DEVICE

In a method for determining the modular inverse of a number, successive iterations are applied to two pairs each including a first variable and a second variable, such that at the end of each iteration and for each pair, the product of the second variable and of the number is equal to the first variable modulo a given module. Each iteration includes at least one division by two of the first variable of a first pair or of a second pair, or a combination of the first variable of the first pair and of the first variable of the second pair by addition or subtraction. At least some of the iterations including a combination by addition or subtraction include a step of storing the result of the combination in the first variable of a pair determined randomly from among the first pair and the second pair. An associated cryptographic processing device is also described. 1. Method for determining a modular inverse of a number , wherein successive iterations are applied to two pairs each comprising a first variable and a second variable such that at the end of each iteration and for each pair , a product of the second variable and of said number is equal to the first variable modulo a given module , the two pairs comprising a first pair and a second pair ,each iteration including at least one division of the first variable of the first pair or of the second pair by two, or a combination of the first variable of the first pair and of the first variable of the second pair by addition or subtraction,wherein at least some of the iterations including a combination by addition or subtraction comprise a step of storing a result of said combination in the first variable of a pair determined randomly from among the first pair and the second pair.2. Method according to claim 1 , wherein claim 1 , when the number of iterations performed is greater than a threshold claim 1 , each iteration including a combination by addition or subtraction comprises a step of storing the result of said ...

PROTECTION OF AN ITERATIVE CALCULATION

The disclosure concerns a method of protecting a calculation on a first number and a second number, including the steps of: generating a third number including at least the bits of the second number, the number of bits of the third number being an integer multiple of a fourth number; dividing the third number into blocks each having the size of the fourth number; successively, for each block of the third number: performing a first operation with a first operator on the contents of a first register and of a second register, and then on the obtained intermediate result and the first number, and placing the result in a third register; and for each bit of the current block, performing a second operation by submitting the content of the third register to a second operator with a function of the rank of the current bit of the third number, and then to the first operator with the content of the first or of the second register according to state “0” or “1” of said bit, and placing the result in the first or second register. 1. A method , comprising:performing, using an electronic circuit, a calculation on a first number and a second number; andprotecting the performing of the calculation, wherein the method includes:generating a third number comprising at least the bits of the second number, a number of bits of the third number being an integer multiple of a fourth number;dividing the third number into blocks each having a size in bits of the fourth number; and performing a first function, the first function using a first operator and having as inputs: contents of a first register, contents of a second register and the first number, and placing a result of the first function in a third register; and', [ contents of the third register;', 'a rank of a current bit of the third number; and', 'the contents of a selected one of the first and the second register according to a state of said current bit; and, 'performing a second function, the second function using a second ...

Systems and methods for localizing and analyzing samples on a bio-sensor chip

Chips that include one or more particle manipulation mechanisms, or force transduction elements, provided at specific locations to manipulate and localize particles proximal the substrate surface. In one embodiment, individually addressable magnetic control mechanisms such as electric coils are provided at specific locations to create a magnetic field to attract magnetic particles, such a magnetic or magnetizable beads, to those specific locations. In another embodiment, electrostatic control mechanisms such as electrodes are provided to attract and manipulate electrically charged micro-particles. A location may include a crater or well formed in the substrate, or it may include an element on the surface of the substrate. In some embodiments, one or more sensors are located proximal specific locations, e.g., specific craters, so as to analyze specific conditions at each location. In other embodiments, multiple locations share one or more sensors.

Systems and methods for localizing and analyzing samples on a bio-sensor chip

Chips that include one or more particle manipulation mechanisms, or force transduction elements, provided at specific locations to manipulate and localize particles proximal the substrate surface. In one embodiment, individually addressable magnetic control mechanisms such as electric coils are provided at specific locations to create a magnetic field to attract magnetic particles, such a magnetic or magnetizable beads, to those specific locations. In another embodiment, electrostatic control mechanisms such as electrodes are provided to attract and manipulate electrically charged micro-particles. A location may include a crater or well formed in the substrate, or it may include an element on the surface of the substrate. In some embodiments, one or more sensors are located proximal specific locations, e.g. specific craters, so as to analyze specific conditions at each location. In other embodiments, multiple locations share one or more sensors.

Geschützte kryptographische berechnung

Bei einem Verfahren zum geschützten Ausführen einer kryptographischen Berechnung, bei der ein Schlüssel (12) mit mindestens zwei Schlüsselparametern (p, q, pinv, sp, dp, sq, dq) herangezogen wird, wird eine Integritätsüberprüfung (30, 34, 40, 54) des Schlüssels (12) durchgeführt, um einen kryptographischen Angriff zu verhindern, bei dem durch eine Verfälschung mindestens eines ersten Schlüsselparameters (p, q, pinv, sp, dp, sq, dq) Rückschlüsse auf mindestens einen zweiten Schlüsselparameter (p, q, pinv, sp, dp, sq, dq) gezogen werden. Ein weiteres Verfahren dient zum Bestimmen eines Schlüssels für eine kryptographische Berechnung mit mindestens zwei Schlüsselparametern (p, q, pinv, sp, dp, sq, dq), der zur Verwendung in dem erstgenannten Verfahren vorgesehen ist. Ein Computerprogrammprodukt und ein tragbarer Datenträger weisen entsprechende Merkmale auf. Die Erfindung ermöglicht einen besonders guten Schutz kryptographischer Berechnungen gegen Angriffe.

Use the Montgomery Algorithm of random addition chain

各种实施例涉及一种用于产生实施模幂运算的代码的装置，所述装置包括：用于存储查询表的存储器；以及与所述存储器通信的处理器，所述处理器被配置成：接收用于所生成的随机加法链的信息；输出用于实施所述模幂运算的代码，所述代码从包括中间结果的所述查询表载入要素，所述中间结果利用用于所生成的随机加法链的信息；以及输出用于实施所述模幂运算的代码，所述代码使用所述所载入的要素以计算下一要素。

Power-residue calculating unit using montgomery algorithm

멱승 잉여 연산 회로는 외부 버스와의 인터페이스인 I/F(인터페이스) 회로(101)와, 키 e를 유지하는 e 레지스터(102)와, 몽고메리 변환을 하는 승수(multiplier) Y를 유지하는 Y 레지스터(103)와, 키 N을 유지하는 N 레지스터(104)와, 몽고메리 변환의 연산 시에 실행하는 2B+N의 값을 유지하는 B2N 레지스터(105)와, 평문 X를 유지하는 X 레지스터(106)와, 암호화 및 복호화를 위한 연산을 실행하는 연산 회로(107)와, 연산 결과 P를 유지하는 P 레지스터(108)와, 멱승 잉여 연산 실행 시의 상태 머신(state machine)으로서 역할하는 멱승 잉여 제어 회로(109)와, 몽고메리 승산 잉여 연산과 잉여 연산 실행 시의 상태 머신으로서의 역할을 다 하는 몽고메리 승산 잉여·잉여 제어 회로(110)와, 가산 및 감산의 연산 제어를 실행하는 가산·감산 제어 회로(111)를 포함한다. The power surplus arithmetic circuit includes an I / F (interface) circuit 101, which is an interface to an external bus, an e register 102 holding a key e, and a Y register holding a multiplier Y for Montgomery conversion. 103, an N register 104 holding a key N, a B2N register 105 holding a value of 2B + N to be executed at the time of the Montgomery transform operation, an X register 106 holding a plain text X, and An arithmetic circuit 107 for performing operations for encryption and decryption, a P register 108 for holding a calculation result P, and a power surplus control circuit serving as a state machine at the time of performing a power surplus operation ( 109), the Montgomery multiplication surplus and surplus control circuit 110 serving as a state machine at the time of execution of the Montgomery multiplication surplus operation and the surplus operation, and the addition / subtraction control circuit 111 for executing calculation control of addition and subtraction. It includes.

Exponential remainder arithmetic unit, and computer-readable recording medium on which program for making computer execute exponential remainder arithmetic processing is recorded

(57)【要約】 指数剰余演算装置および指数剰余演算処理をコンピュー タに実行させるためのプログラムを記録したコンピュー タ読み取り可能な記録媒体 【課題】 形式ｂ e modｎの指数剰余演算を高速に演算 し、システム性能およびデータスループットへの影響を 最小にし、公開鍵暗号システムに応用して十分なレベル の通信セキュリティを提供する。 【解決手段】 指数剰余演算装置は、形式ｂ e modｎの指 数剰余演算の演算を導出するように適合されている。指 数剰余演算装置は、中国人剰余定理に従って与えられた 指数剰余演算を、もとの除数ｎの約半分の素数である除 数ｐおよびｑをそれぞれ有する第一および第二の部分に 分ける（１０４，１０５）。指数剰余演算の各部分は、 予め計算された累乗値を有するそれぞれの複数の小さい 指数剰余演算に分解される。次に、それぞれの複数の小 さい指数剰余演算を共に乗算処理して（１０２，１０ ３）、それぞれの中間値を演算する。次に、その中間値 を再合成処理して（１０６〜１１１）、指数剰余演算結 果を得る。

Portable data carrier with protection from unsanctioned access, provided due to separation of key on several portions

FIELD: data carriers. SUBSTANCE: data carrier is made in such a way, that for important data protection operations confidential data stored in chip memory or formed by it are separated on at least three portions, also provided is processor for calculation of random number and for dividing confidential data on such random number, while first portion of data is an integer result of such division, and third portion of data is the actual random number. EFFECT: higher quality of data protection. 3 cl, 1 dwg ÐÎÑÑÈÉÑÊÀß ÔÅÄÅÐÀÖÈß (19) RU (51) ÌÏÊ 7 (11) (13) 2 251 218 C2 H 04 L 9/30 ÔÅÄÅÐÀËÜÍÀß ÑËÓÆÁÀ ÏÎ ÈÍÒÅËËÅÊÒÓÀËÜÍÎÉ ÑÎÁÑÒÂÅÍÍÎÑÒÈ, ÏÀÒÅÍÒÀÌ È ÒÎÂÀÐÍÛÌ ÇÍÀÊÀÌ (12) ÎÏÈÑÀÍÈÅ ÈÇÎÁÐÅÒÅÍÈß Ê ÏÀÒÅÍÒÓ (21), (22) Çà âêà: 2002120476/09, 20.12.2000 (72) Àâòîð(û): Ãåðìàíí ÄÐÅÊÑËÅÐ (DE), Õàðàëüä ÔÀÒÅÐ (DE) (24) Äàòà íà÷àëà äåéñòâè ïàòåíòà: 20.12.2000 (30) Ïðèîðèòåò: 28.12.1999 DE 19963408.4 (73) Ïàòåíòîîáëàäàòåëü(ëè): ÃÈÇÅÊÅ ÓÍÄ ÄÅÂÐÈÅÍÒ ÃÌÁÕ (DE) R U (43) Äàòà ïóáëèêàöèè çà âêè: 20.01.2004 (45) Îïóáëèêîâàíî: 27.04.2005 Áþë. ¹ 12 2 2 5 1 2 1 8 (56) Ñïèñîê äîêóìåíòîâ, öèòèðîâàííûõ â îò÷åòå î ïîèñêå: WO 9935782, 15.07.1999. US 4799258, 17.01.1989. US 4932053, 05.06.1990. RU 96120771 À, 10.01.1999. (85) Äàòà ïåðåâîäà çà âêè PCT íà íàöèîíàëüíóþ ôàçó: 29.07.2002 (86) Çà âêà PCT: EP 00/13031 (20.12.2000) (54) ÏÎÐÒÀÒÈÂÍÛÉ ÍÎÑÈÒÅËÜ ÄÀÍÍÛÕ Ñ ÈÕ ÇÀÙÈÒÎÉ ÎÒ ÍÅÑÀÍÊÖÈÎÍÈÐÎÂÀÍÍÎÃÎ ÄÎÑÒÓÏÀ, ÎÁÅÑÏÅ×ÈÂÀÅÌÎÉ ÇÀ Ñ×ÅÒ ÐÀÇÄÅËÅÍÈß ÊËÞ×À ÍÀ ÍÅÑÊÎËÜÊÎ ×ÀÑÒÅÉ (57) Ðåôåðàò: Èçîáðåòåíèå îòíîñèòñ ê íîñèòåë ì äàííûõ. Òåõíè÷åñêèé ðåçóëüòàò çàêëþ÷àåòñ â ïîâûøåíèè çàùèòû äàííûõ. Ñîãëàñíî èçîáðåòåíèþ òàêîé íîñèòåëü äàííûõ âûïîëíåí òàêèì îáðàçîì, ÷òîáû äë âûïîëíåíè âàæíûõ äë çàùèòû äàííûõ îïåðàöèé ðàçäåë òü êîíôèäåíöèàëüíûå äàííûå, õðàí ùèåñ â ïàì òè ÷èïà èëè ôîðìèðóåìûå èì, ïî ìåíüøåé ìåðå íà òðè ÷àñòè, ïðè ýòîì ïðåäóñìîòðåí ïðîöåññîð äë âû÷èñëåíè ñëó÷àéíîãî ÷èñëà è äë äåëåíè êîíôèäåíöèàëüíûõ äàííûõ íà òàêîå ñëó÷àéíîå ÷èñëî, ïðè÷åì ïåðâà ÷àñòü äàííûõ ïðåäñòàâë åò ñîáîé öåëî÷èñëåííûé ðåçóëüòàò òàêîãî äåëåíè , âòîðà ...

Portable data carrier provided with access protection by dividing up codes

본 발명은 여러 명령어를 갖는 연산 프로그램이 저장된 적어도 하나의 메모리를 갖는 반도체 칩을 가지고, 각 명령어는 반도체 칩의 외부에서 탐지될 수 있는 신호를 발생시키는 데이터 저장 매체에 관한 것이다. 본 발명에 따르면, 데이터 저장 매체는, 임의값의 계산과 임의값을 나누기 위한 연산 장치를 포함하고, 보안 관련 또는 안전 관련 연산을 수행하기 위하여 반도체 칩내에 저장되어 있거나 이러한 반도체 칩에 의하여 발생되는 비밀 데이터를, 첫째 데이터 부분은 나눗셈 과정의 정수 결과이고, 둘째 데이터 부분은 나눗셈 과정의 나머지이며, 셋째 데이터 부분은 임의값 그 자체인, 적어도 세개의 데이터 부분으로 분리시키기 위하여 디자인된다.

RSA algorithm acceleration processors, methods, systems, and instructions

处理器包括对指令译码的译码单元。所述指令包含具有第一64位值的第一64位源操作数，指示具有第二64位值的第二64位源操作数，指示具有第三64位值的第三64位源操作数，以及指示具有第四64位值的第四64位源操作数。执行单元与译码单元耦合。执行单元响应于指令而可操作以存储结果。所述结果包含第一64位值乘以第二64位值加上第三64位值加上第四64位值。执行单元可以将结果的64位最低有效半数存储在由指令指示的第一64位目的地操作数中，并且将结果的64位最高有效半数存储在由指令指示的第二64位目的地操作数中。

Apparatus and method for modular multiplication using chhinese remainder theorem and carry save adder

본 발명은 중국인 나머지 정리(CRT)와 캐리 저장 가산 기반의 모듈러 곱셈 장치 및 방법에 관한 것으로, 더욱 상세하게는 데이터 암/복호화 등에 사용되는 RSA(Rivest-Shamir-Adleman) 공개키 암호를 구현하는데 필요한 고속의 모듈러 곱셈 방법과 이를 이용하여 중국인 나머지 정리(Chinese Remainder Theorem, CRT) 기법에 적용 가능한 모듈러 곱셈 장치 및 방법에 관한 것이다. 본 발명에 의한 모듈러 곱셈은 부스 부호화(Booth Encoding)기법을 이용하며 비트 최종 가산기를 사용하여 두 개의 n비트 입력 A, B에 대한 곱셈을 클롤 사이클만에 수행하고, 또한 캐리 저장 가산기를 기반으로 하나의 n 비트 모듈러 곱셈 연산과 두 개의 n/2 비트 모듈러 곱셈 연산을 선택적으로 처리할 수 있어 중국인 나머지 정리를 이용한 RSA 복호화 연산을 효율적으로 처리할 수 있는 효과가 있다. The present invention relates to a modular multiplication apparatus and method based on the Chinese Residual Theorem (CRT) and carry storage addition, and more particularly, to implement a Rivest-Shamir-Adleman (RSA) public key cryptography used for data encryption / decryption. The present invention relates to a fast modular multiplication method and a modular multiplication apparatus and method applicable to the Chinese Remainder Theorem (CRT) technique. Modular multiplication according to the present invention utilizes the Boot Encoding technique. Multiply two n-bit inputs A and B using the bit final adder It can perform in a crawl cycle only, and can optionally handle one n-bit modular multiplication operation and two n / 2-bit modular multiplication operations based on the carry storage adder to efficiently handle RSA decoding operations using the Chinese remainder theorem. It can work. 몽고메리 모듈러 곱셈, 캐리 저장 가산기, 부스 부호화, 중국인 나머지 정리 Montgomery Modular Multiplication, Carry Storage Adder, Booth Coding, Chinese Rest Theorem

Information processing system, enciphering/deciphering system, system LSI, and electronic apparatus

An information processing system that is configured in such a manner that computational processing is performed on input data in accordance with a processing sequence, for outputting data, comprises: a plurality of arithmetic units ( 7 - 1 to 7 -x), each computing at an arithmetic precision 2 m bits (where m is a natural number) based on the processing sequence; and a plurality of cascade connection terminals for cascading these arithmetic units each other. When the maximum arithmetic precision that is required during computational processing is 2 n bits (where n is a natural number and is fixed), x numbers of (where x is a natural number) the arithmetic units are cascaded in a manner such that the inequality x≧2 n /2 m is satisfied. When an arithmetic precision of 2 n1 bits (where n 1 ≦n, and n 1 is variable) is necessary during computational processing, x 1 numbers of the arithmetic units are cascaded in a manner such that the inequality x 1 ≧2 n1 /2 m (where x 1 is a natural number and is variable) is satisfied. This makes it possible to easily implement an information processing system for performing computations to any desired precision in a hardware manner, and also makes it possible to support a simple hardware-based method of expanding the arithmetic precision.

METHODS AND DEVICES FOR ACCELERATING THE CALCULATION TIME OF A MONTGOMERY PRODUCT BY MODULAR MULTIPLICATION AND EXPONENTIATION

The invention relates to a method for speeding up the time required to perform a Montgomery product calculation by applying the High-Radix Montgomery method on computing hardware. Said method comprises a loop of operations (72) consisting in repeating successive operations, i.e.: a first addition operation (76) involving the addition of a value of one of several first products, designated <o>ai</o>.<o>b</o>, and a value of one variable, designated u, according to a first relationship u:=u+<o>ai</o>.<o>b</o>; and a second addition operation (80) involving the addition of a value of one of several second products, designated m.n, and a value of variable u according to a second relationship u:=u+m.n. The inventive method is characterised in that at least said first and second addition operations are Carry-Save addition operations in order to speed up the time required to perform an addition.

PROTECTION OF A MODULAR EXPONENTIATION CALCULATION

L'invention concerne un procédé de protection d'un calcul d'exponentiation modulaire exécuté par un circuit électronique utilisant un premier registre (RO) et un deuxième registre (R1), comportant successivement, pour chaque bit de l'exposant (e) : une première étape (52, 54) de multiplication du contenu d'un des registres, choisi parmi le premier registre et le deuxième registre en fonction de l'état du bit de l'exposant, par le contenu de l'autre des premier et deuxième registres, en plaçant le résultat dans ledit un des registres ; une deuxième étape (53, 25) d'élévation au carré du contenu dudit autre des registres en plaçant le résultat dans cet autre registre, dans lequel le contenu dudit autre des registres est stocké dans un troisième registre (T) avant la première étape et est restitué dans ledit autre des registres avant la deuxième étape. The invention relates to a method for protecting a modular exponentiation calculation executed by an electronic circuit using a first register (RO) and a second register (R1), comprising successively, for each bit of the exponent (e): a first step (52, 54) of multiplying the content of one of the registers, selected from the first register and the second register according to the state of the exponent bit, by the content of the other of the first and second registers, placing the result in said one of the registers; a second step (53, 25) of squaring the contents of said other one of the registers by placing the result in this other register, wherein the contents of said other of the registers are stored in a third register (T) before the first step and is restored to said other register before the second step.

Modular exponentiation with partitioned and scattered storage of Montgomery multiplication results

描述用于边信道保护的模幂运算的技术和系统的实施例。在实施例中，在模幂运算计算期间，产生蒙哥马利乘法（“MM”）结果。将这些MM结果分散在表上以用于存储，以使这些值的存储不可导致私密指数值被间谍过程通过边信道攻击发现。可以执行该分散以便减少每次MM结果存储或检索期间执行的每结果的存储器操作的次数。在实施例中，可以在模幂运算中使用4的窗口大小，连同将MM结果分区成32位分区值，且将这些分区值按64个字节偏移来分散。在实施例中，虽然使用4的窗口大小可能导致模幂运算期间较其他窗口大小额外的MM计算，但是存储器操作的减少可以提供正面性能补偿。

PROTECTION OF A MODULAR EXPONENTIATION CALCULATION BY MULTIPLICATION BY A RANDOM QUANTITY

L'invention concerne un procédé de protection d'un calcul, par un circuit électronique, d'une exponentiation modulaire d'une quantité numérique (M) dans lequel : une première variable (T) est initialisée (24) avec une quantité aléatoire (r) ; au moins une deuxième variable (M) est initialisée (21) avec une valeur fonction de ladite quantité numérique ; au moins pour un bit (hi) valant 1 d'un exposant (h) de l'exponentiation modulaire la première variable est mise à jour par : a) le quotient (25) de son contenu par une puissance de ladite quantité aléatoire (r) ; et b) le produit (54) de son contenu par celui de la deuxième variable ; et une fois tous les bits de l'exposant traités (60), le contenu de ladite première variable est divisé (28) par ladite quantité aléatoire pour fournir (29) le résultat de l'exponentiation modulaire.

Device for performing a division.

Ce dispositif est conçu pour effectuer une division du nombre dividende A formé de "m" mots exprimant une base "b", par un diviseur D. Il comporte une mémoire vive (2), un organe de multiplication inclus dans une unité de calcul (8) muni d'une première entrée (xi ) pour "x" mots d'un multiplicande, d'une deuxième entrée (Ai ) pour "y" mots d'un multiplicateur. Il est prévu des moyens de cumul pour ajouter à des emplacements de la mémoire (2) un multiple d'une quantité dbk .bJ élaborée par ledit organe de multiplication, des moyens de test pour fournir une indication de la valeur nulle d'un séparateur S dans ledit emplacement et pour activer les moyens de cumuls jusqu'à ce que les moyens de test fournissent ladite indication et des moyens de décrémentation pour décrémenter la valeur J à chaque indication. Le reste de la division est contenu dans les derniers emplacements et le quotient dans les premiers. Application aux cryptages RSA. This device is designed to perform a division of the dividend number A formed of "m" words expressing a base "b", by a divider D. It comprises a random access memory (2), a multiplication unit included in a calculation unit ( 8) provided with a first entry (xi) for "x" words of a multiplicand, with a second entry (Ai) for "y" words of a multiplier. Accumulation means are provided for adding to locations of the memory (2) a multiple of a quantity dbk .bJ produced by said multiplication member, test means for providing an indication of the zero value of a separator S in said location and to activate the cumulative means until the test means provides said indication and decrementing means for decrementing the value J at each indication. The remainder of the division is contained in the last places and the quotient in the first. Application to RSA encryption.

SECURE METHOD OF PARALLEL REALIZATION OF A MODULAR EXPONENTIATION, CRYPTOGRAPHIC METHOD AND COMPUTING CIRCUIT THEREOF

CRYPTOGRAPHIC METHOD PROTECTED FROM CACHE-CHANNEL TYPE ATTACKS

L'invention concerne un procédé cryptographique sécurisé contre une attaque à canal caché.Selon l'invention, pour exécuter un bloc d'instructions choisi (Π j) en fonction d'une variable d'entrée (D i) parmi N blocs d'instructions prédéfinis (Π1 ,..., ΠN), on exécute un nombre prédéfini (L j) de fois un bloc élémentaire commun (Γ(k, s)) aux N blocs d'instructions prédéfinis (Π1 ,..., ΠN), le nombre prédéfini (L j) étant associé au bloc d'instructions choisi (Πj).

White-box implementation

A system (200) for enabling a device to compute an outcome of an exponentiation C x having a base C and/or an exponent x, the system comprising means for establishing a plurality of values .lambda.i; means (202) for establishing a plurality of values .omega.i satisfying .omega.i = C.lambda.i; means (204) for establishing a plurality of values .phi.i satisfying that the sum of the values .lambda.i.phi.i equals x; and an output for providing the device with the plurality of values .phi.i. A device (250) computes an outcome of the exponentiation C x. The device comprises means (252) for computing a product of the values .omega.i to the power of .phi.i. The device is arranged for using the product as a result of the exponentiation C x.

METHOD OF ENCODING THE RSA METHOD BY A MICROCONTROLLER AND DEVICE USING THE SAME

Procédé consistant à transformer un message numérique M par une opération d'exponentiation de M par un nombre e, modulo N, tous ces nombres étant des entiers de grande longueur, à n bits, qui utilise une suite de deux opérations successives, la première de la forme: (CF DESSIN DANS BOPI) où Bi et X sont des variables de calcul, où ai est un extrait à m bits d'une autre variable de calcul A dont la valeur découle d'une étape d'opérations précédentes, extrait pris dans l'ordre décroissant des poids de A au rang i, et T une variable de totalisation servant dans le calcul de A, et la deuxième opération consistant à réduire la longueur de la variable Bi . Le procédé selon l'invention utilise une quasi-réduction modulo N puisqu'elle est approximative (à un petit multiple de N près), et peut être appliquée systématiquement et sans test de signe pendant un nombre donné d'opérations successives que l'on se fixe. Après quoi, on opère une réduction supplémentaire et systématique selon la même méthode. Un quotient q, approché par défaut, de Bi /N est utilisé, pour lequel on prévoit un format à p bits supérieur au format à m bits de ai . Application à des dispositifs de codage/décodage portatifs. Process consisting in transforming a digital message M by an operation of exponentiation of M by a number e, modulo N, all these numbers being integers of great length, with n bits, which uses a series of two successive operations, the first of the form: (CF DRAWING IN BOPI) where Bi and X are calculation variables, where ai is an m-bit extract of another calculation variable A whose value results from a step of previous operations, extract taken in decreasing order of the weights of A at rank i, and T a totalization variable used in the calculation of A, and the second operation consisting in reducing the length of the variable Bi. The method according to the invention uses a modulo N quasi-reduction since it is approximate (to within a small ...

Data processing method for securing Rivest Shamir Adleman cryptographic algorithms on chip card, involves testing relation between values by comparing values with neutral element of finite group based on internal rule of finite group

The method involves realizing double exponentiation of an element (m) of a finite group by exponents (d, b) for providing corresponding values (R0, R1), where one the exponents is equal to difference between the other exponent and an order or multiple of the finite group (vG). A relation between the values provided by the corresponding exponents is tested by comparing the values with a neutral element (1G) of the finite group based on internal rule of the finite group. An independent claim is also included for a data processing device comprising a double exponentiation calculation unit.

Cryptographic process for e.g. message encryption and decryption, involves scanning bits of preset value from left to right in loop, and calculating and storing partial updated result equal to exponentiation in accumulator

The process involves scanning bits of a preset value from left to right in a loop indicated by a preset integer varying in a predetermined range. A partial updated result equal to exponentiation is calculated and stored in an accumulator. Result of multiplication of content in the accumulator with a function number in a register is stored in the accumulator for realizing modular exponentiation.

Modular exponentiation method for public key cryptography applications, especially for chip card implementation, whereby the method is suitable for parallel processor use and employs multiplier and multiplicand registers

L'invention concerne un procédé de réalisation d'une exponentiation modulaire de type X^Y mod Z, à l'aide de deux processeurs pouvant fonctionner en parallèle, Y étant un exposant. Au cours du procédé, un premier processeur réalise l'étape ET1 suivante :ET1 : multiplication modulo Z (R/YJ.RYJ mod Z) du contenu d'un registre de multiplicateur (R/YJ) par le contenu d'un registre de multiplicande (RYJ), et mémorisation d'un résultat dans le registre de multiplicateur (R/YJ),Selon l'invention, en fonction d'un bit de rang J de l'exposant Y, on utilise :- un premier registre (R0) comme registre de multiplicateur (R/YJ) et un deuxième registre (R1) comme registre de multiplicande (RYJ), ou- le deuxième registre (R1) comme registre de multiplicateur (R/YJ) et le premier registre (R0) comme registre de multiplicande (RYJ).Applications à la cryptographie à clé publique.

METHOD AND CONTROLLER FOR CRYPTOGRAPHING A MESSAGE ACCORDING TO A PUBLIC KEY ALGORITHM

LE CONTROLEUR 1 COMPREND UNE UNITE CENTRALE 2, UNE MEMOIRE DE TRAVAIL DE TYPE RAM 4, UNE MEMOIRE DE PROGRAMME 4, ET UNE CELLULE DE CALCUL 5. LA MEMOIRE DE PROGRAMME MEMORISE UN SOUS-PROGRAMME POUR LE CRYPTAGE OU DECRYPTAGE DE MOTS NUMERIQUES DE MESSAGE PAR LE CALCUL D'UNE EXPONENTIATION MODULO N DE CHACUN DES MOTS NUMERIQUES DE MESSAGE, N ETANT UN ENTIER DE VALEUR ELEVEE PREDETERMINEE. L'EXPONENTIATION MODULO N D'UN MOT NUMERIQUE DE MESSAGE EST CALCULEE EN EFFECTUANT UNE SUITE D'OPERATIONS A.B MODULO N, OU A ET B SONT DES VARIABLES DE CALCUL DEPENDANTES DE LA VALEUR DU MOT NUMERIQUE DE MESSAGE. CHACUNE DES OPERATIONS A.B MODULO N EST EFFECTUEE PAR L'UNITE CENTRALE EN COOPERATION AVEC LA CELLULE DE CALCUL. LA CELLULE A ACCES A LA MEMOIRE RAM. ELLE EXECUTE POUR LE COMPTE DE L'UNITE CENTRALE DES CALCULS DE TYPE T Y.N OU T ET Y SONT DES VARIABLES DE CALCUL AYANT DES VALEURS ENTIERES. UN TEL CONTROLEUR EST REALISABLE SOUS LA FORME D'UNE UNIQUE PUCE DE FAIBLE ENCOMBREMENT. CONTROLLER 1 INCLUDES A CENTRAL UNIT 2, A RAM TYPE WORKING MEMORY 4, A PROGRAM MEMORY 4, AND A CALCULATION CELL 5. THE PROGRAM MEMORY STORES A SUB-PROGRAM FOR THE ENCRYPTION OR DECRYPTING OF DIGITAL MESSAGE WORDS BY CALCULATING A MODULO N EXPONENTIATION OF EACH OF THE NUMERIC WORDS OF MESSAGE, N BEING A PREDETERMINED HIGH VALUE INTEGER. THE MODULO N EXPONENTIATION OF A MESSAGE DIGITAL WORD IS CALCULATED BY PERFORMING A SUIT OF A.B MODULO N OPERATIONS, OR A AND B ARE CALCULATION VARIABLES DEPENDENT ON THE VALUE OF THE MESSAGE DIGITAL WORD. EACH OF THE A.B MODULO N OPERATIONS IS CARRIED OUT BY THE CENTRAL UNIT IN COOPERATION WITH THE COMPUTING CELL. THE CELL HAS ACCESS TO THE RAM MEMORY. IT EXECUTS ON BEHALF OF THE CENTRAL UNIT OF CALCULATIONS OF TYPE T Y.N OR T AND Y ARE CALCULATION VARIABLES WITH INTEGER VALUES. SUCH A CONTROLLER CAN BE REALIZED IN THE FORM OF A SINGLE SMALL CHIP.

FAT GENERATION ATTACKED DATA PROCESSING METHOD AND ASSOCIATED DEVICE

PROTECTION OF A MODULAR EXPONENTIATION CALCULATION CARRIED OUT BY AN INTEGRATED CIRCUIT

L'invention concerne un procédé et un circuit de protection d'une quantité numérique (d) contenue dans un circuit intégré (1) sur un premier nombre de bits (n), dans un calcul d'exponentiation modulaire d'une donnée (M) par ladite quantité numérique, consistant à : sélectionner au moins un deuxième nombre (j) compris entre l'unité et ledit premier nombre moins deux ; diviser ladite quantité numérique en au moins deux parties, une première partie (d(j-1, 0)) comprenant, depuis le bit de rang nul, un nombre de bits égal audit deuxième nombre, une deuxième partie (d(n-1, j)) comprenant les bits restants ; pour chaque partie de la quantité, calculer une première exponentiation modulaire (32, 33) de ladite donnée par la partie concernée et une deuxième exponentiation modulaire (36, 34) du résultat de la première par le chiffre 2 élevé à la puissance du rang du premier bit de la partie concernée ; et calculer (35) le produit des résultats des deuxièmes exponentiations modulaires. The invention relates to a method and a circuit for protecting a digital quantity (d) contained in an integrated circuit (1) on a first number of bits (n), in a modular exponentiation calculation of a datum (M ) by said digital quantity, comprising: selecting at least a second number (j) between the unit and said first number minus two; dividing said digital quantity into at least two parts, a first part (d (j-1, 0)) comprising, from the zero rank bit, a number of bits equal to said second number, a second part (d (n-1) , j)) comprising the remaining bits; for each part of the quantity, calculate a first modular exponentiation (32, 33) of said datum by the part concerned and a second modular exponentiation (36, 34) of the result of the first by the number 2 raised to the rank power of the first bit of the relevant part; and calculating (35) the product of the results of the second modular exponentiation.

DATA PROCESSING METHOD INVOLVING MODULAR EXPONENTIATION AND ASSOCIATED DEVICE

Method for testing resistor of integrated circuit arranged in smart card, involves performing statistical processing step for subset of lateral points using estimated value of physical parameters if general hypothesis is correct

The method involves dividing a set of physical parameters into subset of lateral points each corresponding to an elementary operation of an integrated circuit. A general hypothesis is formed for values corresponding to the subset of lateral points. A value of the physical parameters is estimated for the subset of lateral points. A statistical processing step is performed for the subset of lateral points using the estimated value of the physical parameters if the general hypothesis is correct. An independent claim is also included for a system for testing an integrated circuit.

COUNTERMEASURE METHOD AND DEVICES FOR ASYMMETRIC CRYPTOGRAPHY

Ce procédé de contre-mesure dans un composant électronique mettant en oeuvre un algorithme de cryptographie asymétrique à clé privée, comprend la génération (100) d'un paramètre de protection et le calcul (104), à l'aide d'une primitive, d'une donnée intermédiaire à partir du paramètre de protection.Il comprend en outre les étapes consistant à diviser (110) la représentation binaire de la clé privée en plusieurs blocs binaires, à transformer (112) chaque bloc binaire à l'aide du paramètre de protection et, pour chaque bloc binaire transformé, à effectuer (114) un calcul intermédiaire à l'aide de la primitive, et à calculer (106-122) une donnée de sortie par combinaison (116) de la donnée intermédiaire avec les calculs intermédiaires (114). This countermeasure method in an electronic component implementing an asymmetric private key cryptography algorithm, comprises the generation (100) of a protection parameter and the calculation (104), using a primitive, of an intermediate data from the protection parameter. It further comprises the steps of dividing (110) the binary representation of the private key into several binary blocks, transforming (112) each binary block using the parameter protection and, for each transformed binary block, to perform (114) an intermediate calculation using the primitive, and to calculate (106-122) an output datum by combining (116) of the intermediate datum with the calculations intermediaries (114).

VERIFYING THE SENSITIVITY OF AN ELECTRONIC CIRCUIT EXECUTING A MODULAR EXPONENTIATION CALCULATION

CRYPTOGRAPHY METHOD COMPRISING AN EXPONENTIATION OPERATION

L'invention concerne un procédé et un dispositif (DV1) protégé contre des attaques à canal caché, pour calculer le résultat de l'exponentiation d'une donnée m par un exposant d. Le procédé et le dispositif sont configurés pour n'exécuter que des multiplications de variables de grande taille identiques en décomposant toute multiplication de variables de grande taille différentes x, y en une combinaison de multiplications de variables de grande taille identiques. The invention relates to a method and a device (DV1) protected against concealed channel attacks, for calculating the result of the exponentiation of a data item m by an exponent d. The method and device are configured to execute only identical large-size multiplications by decomposing any multiplication of large variables x, y into a combination of identical large-size multiplications.

Integrated circuit for e.g. smart card, has multiplier executing successive multiplications of binary words by modifying order in which elementary steps of multiplication of components of words are executed, in pseudo-random/random manner

The circuit (CIC2) has a coprocessor (CP2) comprising a randomized multiplier (SMT2) for executing an operation of multiplication of two binary words in a set of elementary steps of multiplication of components of one of the binary words by components of the other binary word. The multiplier executes two successive multiplications of the binary words by modifying, in a random or pseudo-random manner, an order in which the elementary steps of multiplication of components of the former binary word and the components of the latter binary word are executed. Independent claims are also included for the following: (1) a device comprising an integrated circuit (2) a method for protecting an integrated circuit against a side channel analysis.

METHOD FOR IMPLEMENTING, IN AN ELECTRONIC COMPONENT, A CRYPTOGRAPHIC ALGORITHM AND CORRESPONDING COMPONENT

MODULAR EXPONENTIATION ALGORITHM IN AN ELECTRICAL COMPONENT USING A PUBLIC KEY ENCRYPTION ALGORITHM

Computation of secure power function for cryptographic algorithms, at least a bit or figure of an indexed x power number is iteratively processed

Secure method for an power function calculation of type y = xr, where x is part of a multiplication group and r is a predetermined number. At least a bit or figure (ri) of the number r is iteratively processed, an index (i) for the number being provided. At the end of each iteration the index is incremented or decremented according to the value of the indexed bit or figure (ri) and the bit or figure is reset to zero. At least two computation registers are used to carry out the power function calculation. The value of the indexed bit or figure is used to index at least one of the registers used in the corresponding iteration. The method is designed to be used in electronic devices carrying out calculations of the type with or without results in place. The method is applied to an power function algorithm according to a binary method or k-range with bit or figure number (ri) sweep from left to right. The indexed register is obtained from the value of the indexed bit or figure (ri). The bit sweep for the number r may be from right to left and the indexed register is obtained from the complement of the value of the indexed bit.

DATA PROCESSING METHOD, ELECTRONIC ENTITY, AND MICROCIRCUIT CARD, IN PARTICULAR FOR DECHIFTING OR SIGNING A SECURE MESSAGE

METHOD FOR SECURELY IMPLEMENTING AN RSA-TYPE CRYPTOGRAPHY ALGORITHM AND CORRESPONDING COMPONENT

FAT GENERATION ATTACKED DATA PROCESSING METHOD AND ASSOCIATED DEVICE

Un procédé de traitement de données comprend les étapes suivantes :- détermination d'une première donnée de résultat à partir d'une première donnée d'entrée et d'une première donnée secrète ;- obtention d'une première donnée compressée à partir de la première donnée de résultat ou de la première donnée d'entrée au moyen d'un algorithme de compression ;- détermination d'une seconde donnée de résultat à partir d'une seconde donnée d'entrée et d'une seconde donnée secrète ;- obtention d'une seconde donnée compressée à partir de la seconde donnée de résultat au moyen de l'algorithme de compression ;- comparaison de la première donnée compressée et de la seconde donnée compressée. A method of data processing comprises the following steps: determining a first result data from a first input data and a first secret data; obtaining a first data compressed from the first data item; first result data or the first input data by means of a compression algorithm; - determining a second result data from a second input data and a second secret data; a second compressed data from the second result data by means of the compression algorithm; - comparing the first compressed data and the second compressed data.

CRYPTOGRAPHIC PROCESSING PROCESS, ELECTRONIC DEVICE AND ASSOCIATED COMPUTER PROGRAM

Un procédé de traitement cryptographique comprend les étapes suivantes :- obtention (E32) d’un second nombre (d’’) déterminé en ajoutant à un premier nombre l’ordre d’un groupe fini ou un multiple de cet ordre ; - détermination (E34) d’un quotient (q) et d’un reste (r) en divisant le second nombre (d’’) par un nombre aléatoire (a) ;- obtention (E36) d’un troisième élément (I) égal à la combinaison d’éléments égaux à un premier élément du groupe fini et en nombre égal au produit du quotient (q) et du nombre aléatoire (a) ;- obtention (E38) d’un quatrième élément (J) égal à la combinaison d’éléments égaux au premier élément et en nombre égal au reste (r) ;- détermination (E40) d’un second élément (P) par combinaison du troisième élément (I) et du quatrième élément (J). Figure pour l’abrégé : Fig. 4

ELECTRONIC CIRCUIT FOR MODULAR CALCULATION IN A FINISHED BODY

METHOD FOR SECURING AN ELECTRONIC CRYPTOGRAPHY ASSEMBLY BASED ON MODULAR EXPONENTIATION AGAINST ATTACKS BY PHYSICAL ANALYSIS

METHOD OF SECURING THE EXECUTION OF A FOLLOWING LOGICALLY ENCHANCED STEPS

L'invention concerne un procédé de sécurisation de l'exécution d'une suite d'étapes logiquement enchaînées, au moins une étape déterminée ayant au moins une étape prédécesseur et devant utiliser pour son exécution des données secrètes.Ce procédé comprend les étapes consistant à :● préalablement à l'exécution de ladite étape déterminée, transformer les données secrètes à utiliser pour l'exécution de cette étape ;● lors de l'exécution de ladite au moins une étape prédécesseur, générer un paramètre de modification ;● lors de l'exécution de ladite étape déterminéeo modifier les données secrètes transformées en utilisant ledit paramètre de modification ;o exécuter l'étape déterminée en utilisant les données secrètes transformées et modifiées. The invention relates to a method for securing the execution of a series of logically linked steps, at least one determined step having at least one predecessor step and having to use secret data for its execution.This method comprises the steps of: : ● before executing said determined step, transform the secret data to be used for the execution of this step, ● when executing said at least one predecessor step, generating a modification parameter; executing said determined step modifying the transformed secret data using said modification parameter; performing the determined step using the transformed and modified secret data.

METHOD FOR SECURING AN ELECTRONIC CRYPTOGRAPHY ASSEMBLY BASED ON MODULAR EXPONENTIATION AGAINST ATTACKS BY PHYSICAL ANALYSIS

L'invention concerne un procédé de sécurisation d'un ensemble électronique mettant en oeuvre un processus de calcul cryptographique faisant intervenir une exponentiation modulaire d'une grandeur (x), ladite exponentiation modulaire utilisant un exposant secret (d), caractérisé en ce que l'on décompose ledit exposant secret en une pluralité de k valeurs imprévisibles (d1 , d2 , dk ) dont la somme est égale audit exposant secret. The invention relates to a method for securing an electronic assembly implementing a cryptographic calculation process involving a modular exponentiation of a quantity (x), said modular exponentiation using a secret exponent (d), characterized in that the 'said secret exponent is decomposed into a plurality of k unpredictable values (d1, d2, dk) the sum of which is equal to said secret exponent.

SECURE AND COMPACT EXPONENTIATION METHOD FOR CRYPTOGRAPHY

La présente invention concerne un procédé d'exponentiation sécurisée et compacte, avec application notamment dans le domaine de la cryptologie où l'on met en oeuvre des algorithmes cryptographiques dans des dispositifs électroniques tels que les cartes à puce. The present invention relates to a secure and compact exponentiation method, with application particularly in the field of cryptology where cryptographic algorithms are implemented in electronic devices such as smart cards.

METHOD FOR TESTING THE SAFETY OF AN ELECTRONIC DEVICE AGAINST AN ATTACK, AND AN ELECTRONIC DEVICE USING COUNTER-MEASUREMENTS

Il est proposé un procédé de test de sécurité d'un dispositif électronique vis-à-vis d'une combinaison d'une attaque par canaux auxiliaires et d'une attaque par injection de fautes qui est mise en oeuvre lors d'une exécution d'un procédé de traitement cryptographique comprenant une étape de signature d'un message à partir d'au moins un paramètre secret, ladite étape de signature mettant en oeuvre une recombinaison d'au moins deux valeurs intermédiaires selon le théorème des restes chinois, et une étape de vérification de ladite signature à partir d'au moins un exposant public. Le procédé de test est remarquable en ce qu'il comprend : - une étape de transmission d'une pluralité de messages à signer par ledit dispositif électronique ; - une étape de perturbation de chaque message, comprenant une modification dudit message par une introduction d'une erreur identique pour chaque message, avant l'exécution d'une étape de détermination d'une des valeurs intermédiaires ; - une étape d'analyse de mesures physiques obtenues pendant ladite étape de vérification de ladite signature en fonction dudit message à signer, de ladite erreur identique pour chaque message et d'une supposition d'une valeur d'une partie dudit au moins un paramètre secret. There is provided a method of testing the security of an electronic device with respect to a combination of an auxiliary channel attack and a fault injection attack which is implemented during a run of a cryptographic processing method comprising a step of signing a message from at least one secret parameter, said signature step implementing a recombination of at least two intermediate values according to the Chinese remains theorem, and a step of verifying said signature from at least one public exponent. The test method is remarkable in that it comprises: a step of transmitting a plurality of messages to be signed by said electronic device; a step of ...

MULTIPLIER OF BINARY NUMBERS WITH VERY LARGE NUMBER OF BITS

Integrated circuit card fraud resistant encryption algorithm having exponential operation U=VW modulo X where U,V and X are whole numbers and W random/masked and fractional number formed.

The encryption process produces an exponential operation of the type U=VW modulo X where U,V and W are whole numbers. W is formed as a masked parameter chosen randomly each execution period. The masking parameter is a fractional number.

METHOD FOR COUNTER-MEASUREMENT BY MASKING THE ACCUMULATOR IN AN ELECTRONIC COMPONENT USING A PUBLIC KEY CRYPTOGRAPHY ALGORITHM

COUNTERMEASURE METHOD IN AN ELECTRONIC COMPONENT USING A CRYPTOGRAPHIC ALGORITHM OF THE PUBLIC KEY TYPE

CRYPTOGRAPHIC PROCESSING METHOD, ELECTRONIC DEVICE AND ASSOCIATED COMPUTER PROGRAM

Un procédé de traitement cryptographique comprend les étapes suivantes :- obtention (E32) d’un second nombre (d’’) déterminé en ajoutant à un premier nombre l’ordre d’un groupe fini ou un multiple de cet ordre ; - détermination (E34) d’un quotient (q) et d’un reste (r) en divisant le second nombre (d’’) par un nombre aléatoire (a) ;- obtention (E36) d’un troisième élément (I) égal à la combinaison d’éléments égaux à un premier élément du groupe fini et en nombre égal au produit du quotient (q) et du nombre aléatoire (a) ;- obtention (E38) d’un quatrième élément (J) égal à la combinaison d’éléments égaux au premier élément et en nombre égal au reste (r) ;- détermination (E40) d’un second élément (P) par combinaison du troisième élément (I) et du quatrième élément (J). Figure pour l’abrégé : Fig. 4 A cryptographic processing method comprises the following steps:- obtaining (E32) a second number (of') determined by adding to a first number the order of a finite group or a multiple of this order; - determining (E34) a quotient (q) and a remainder (r) by dividing the second number (d'') by a random number (a); - obtaining (E36) a third element (I ) equal to the combination of elements equal to a first element of the finite group and in number equal to the product of the quotient (q) and the random number (a);- obtaining (E38) a fourth element (J) equal to the combination of elements equal to the first element and in number equal to the remainder (r);- determination (E40) of a second element (P) by combining the third element (I) and the fourth element (J). Figure for abstract: Fig. 4

Device for multiplying integers by many digits

Method of preventing fault-injection attacks on Chinese Remainder Theorem-Rivest Shamir Adleman cryptographic operations and recording medium for storing program implementing the same

Disclosed herein are a method of preventing fault-injection attacks on Chinese Remainder Theorem (CRT)-Rivest Shamir Adleman (RSA) cryptographic operations, and a recording medium for storing a program implementing the same. First, the method receives first and second primes, that is, different primes, and a randomly selected prime, that is, a random prime, which are used for CRT-RSA cryptographic operations. Thereafter, a cumulative value is calculated by performing an XOR (Exclusive OR) operation on the first prime, the second prime, and the random prime using a push function. Thereafter, the first prime, the second prime, and the random prime are loaded by performing an XOR operation on the cumulative value using a pop function corresponding to the push function. Finally, CRT-RSA operations are executed by computing modulo operations based on the first prime and the second prime.

Operation method and security chip

Embodiments of the present invention disclose an operation method. The method is applied to a security chip, the security chip includes an input/output interface, a decryption circuit, a microprocessor, and an arithmetic unit. The method includes: obtaining, by the input/output interface, an input ciphertext; performing, by the decryption circuit, a modular exponentiation operation according to the ciphertext and a preset operation parameter; and using, by the microprocessor, an operation result obtained after the modular exponentiation operation as a plaintext obtained after decryption. The performing, by the decryption circuit, a modular exponentiation operation according to the ciphertext and a preset operation parameter is specifically: breaking, by the decryption circuit, the modular exponentiation operation into multiple iterative first operations, where the first operation is a modular square operation or a modular multiplication operation; sending, by the decryption circuit, the ciphertext and the operation parameter to the arithmetic unit; and performing, by the arithmetic unit, the first operation according to the ciphertext and the operation parameter to obtain a modular square value or a modular multiplication value. Correspondingly, the embodiments of the present invention further disclose a security chip. According to the present invention, an SPA attack can be resisted and security can be improved.

Method and apparatus for implementing a decoding mechanism by calculating a standardized modular exponentiation to thwart timing attacks

(57)【要約】 暗号化しているべき乗モジュロＭは、モジュラ乗算X * YmodMによって逐行される。ここで、Ｍは、一時的には安定しているが、瞬間的には非均一な法である。この方法は、反復的に連続するステップから成る。各ステップは、１つまたは２つの第一乗算を実行して第一の結果を発生させ、一つ以上の第二乗算によって第一の結果のサイズを削減させて第二の結果を発生させる。この方法は、さらに、法の所定の多重度の下で、各ステップの最終結果を保つ特徴的な手段を採用している。特に、この方法は、測定に付随する法のいかなる減算も、モジュラべき乗の終端段階に、実質的に移行する。これは、方法に関係している一つ以上のパラメータを、適切な方法により、選択することによって可能となる。これは、更に全体の時相性能を維持する。

Apparatus and method for modular multiplication using chhinese remainder theorem and carry save adder

본 발명은 중국인 나머지 정리(CRT)와 캐리 저장 가산 기반의 모듈러 곱셈 장치 및 방법에 관한 것으로, 더욱 상세하게는 데이터 암/복호화 등에 사용되는 RSA(Rivest-Shamir-Adleman) 공개키 암호를 구현하는데 필요한 고속의 모듈러 곱셈 방법과 이를 이용하여 중국인 나머지 정리(Chinese Remainder Theorem, CRT) 기법에 적용 가능한 모듈러 곱셈 장치 및 방법에 관한 것이다. 본 발명에 의한 모듈러 곱셈은 부스 부호화(Booth Encoding)기법을 이용하며 비트 최종 가산기를 사용하여 두 개의 n비트 입력 A, B에 대한 곱셈을 클롤 사이클만에 수행하고, 또한 캐리 저장 가산기를 기반으로 하나의 n 비트 모듈러 곱셈 연산과 두 개의 n/2 비트 모듈러 곱셈 연산을 선택적으로 처리할 수 있어 중국인 나머지 정리를 이용한 RSA 복호화 연산을 효율적으로 처리할 수 있는 효과가 있다. 몽고메리 모듈러 곱셈, 캐리 저장 가산기, 부스 부호화, 중국인 나머지 정리

Method for performing cryptographic calculations in electronic component i.e. smart card, involves detecting occurrence of error carried out after exponentiation of element, and correcting result of exponentiation based on detection result

The method involves executing exponentiation of an element (201) pertaining to a group by traversing a set of bits of an exponent. Three registers are utilized to memorize values of the exponentiation. Occurrence of an error carried out after the exponentiation is detected (202). Result of the executed exponentiation is corrected (203) according to the result of detection of occurrence of error. Independent claims are also included for the following: (1) an electronic component (2) a computer program product comprising instructions for performing a method for performing cryptographic calculations in an electronic component (3) a computer readable storage medium comprising instructions for performing a method for performing cryptographic calculations in the electronic component.

Method for protecting electronic component executing cryptographic algorithm against current measurement attack, comprises factorization of exponential in algorithm and permutation of the factors

L'invention concerne un procédé de contre-mesure dans un composant électronique mettant en oeuvre un algorithme de cryptographie utilisant des moyens de calcul de multiplication modulaire par une puissance de x et/ ou de calcul d'exponentiation modulaire à la puissance x, x étant un nombre entier. Le nombre x étant décomposable en facteurs x1 , x2 ,..., x i , le procédé consiste à choisir une permutation aléatoire P, à considérer le nombre x sous la forme Xp (1) . Xp(2) ... Xp (i) , et à effectuer ledit calcul à partir de cette nouvelle forme de x.

Protected cryptographic calculation

本发明涉及一种用于受保护地执行密码计算的方法，其中，采用具有至少两个密钥参数(p，q，pinv，sp，dp，sq，dq)的密钥(12)，对该密钥(12)执行完整性检验(30，34，40，54)，以防止其中通过伪造至少一个第一密钥参数(p，q，pinv，sp，dp，sq，dq)推断出至少一个第二密钥参数(p，q，pinv，sp，dp，sq，dq)的密码攻击。另一种方法用于确定密码计算的、具有至少两个密钥参数(p，q，pinv，sp，dp，sq，dq)的密钥，该密钥用于上述第一种方法。计算机程序产品和便携式数据载体具有对应的特征。本发明使得可以特别有效地保护密码计算免受攻击。

Multiplier cell and method of computing

An integrated cryptographic system ( 24 ) executes a mathematical algorithm that computes equations for public-key cryptography. An arithmetic processor ( 22 ) receives data values stored in a temporary storage memory ( 14 ) and computes both the Rivest-Shamir-Adleman (RSA) and Elliptic Curve Cryptography (ECC) algorithms. Multiplication cells ( 270 and 280 ) have an INT/POLY terminal that selects a C-register ( 246 ) for computing RSA modular exponentiation or ECC elliptic curve point multiplication.

CRYPTOGRAPHIC CALCULATION METHOD RESISTANT TO MATERIAL FAILURES

Cryptography and equipment

Cryptographic system with modular randomization of exponentiation

Systems and/or methods that facilitate secure electronic communication of data are presented. A cryptographic component facilitates securing data associated with messages in accordance with a cryptographic protocol. The cryptographic component includes a randomized exponentiation component that facilitates decryption of data and generation of digital signatures by exponentiating exponents associated with messages. An exponent is divided into more than one subexponent at an exponent bit that corresponds to a random number. Exponentiation of the first subexponent can be performed based on a left-to-right-type of exponentiation algorithm, and exponentiation of the second subexponent can be performed based on a right-to-left square-and-multiply-type of exponentiation algorithm. The final value is based on the exponentiations of the subexponents and can be decrypted data or a digital signature, which can be provided as an output.