EP1423786A2 - Dispositif et procede pour calculer le resultat d'une exponentiation modulaire - Google Patents

Dispositif et procede pour calculer le resultat d'une exponentiation modulaire

Info

Publication number
EP1423786A2
EP1423786A2 EP02797920A EP02797920A EP1423786A2 EP 1423786 A2 EP1423786 A2 EP 1423786A2 EP 02797920 A EP02797920 A EP 02797920A EP 02797920 A EP02797920 A EP 02797920A EP 1423786 A2 EP1423786 A2 EP 1423786A2
Authority
EP
European Patent Office
Prior art keywords
auxiliary variable
follows
mod
calculating
auxiliary
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP02797920A
Other languages
German (de)
English (en)
Inventor
Jean-Pierre Seifert
Joachim Velten
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Infineon Technologies AG
Original Assignee
Infineon Technologies AG
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Infineon Technologies AG filed Critical Infineon Technologies AG
Publication of EP1423786A2 publication Critical patent/EP1423786A2/fr
Withdrawn legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
    • G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
    • G06F7/723—Modular exponentiation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/002—Countermeasures against attacks on cryptographic mechanisms
    • H04L9/004—Countermeasures against attacks on cryptographic mechanisms for fault attacks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
    • G06F2207/7219—Countermeasures against side channel or fault attacks
    • G06F2207/7223—Randomisation as countermeasure against side channel attacks
    • G06F2207/7233—Masking, e.g. (A**e)+r mod n
    • G06F2207/7242—Exponent masking, i.e. key masking, e.g. A**(e+r) mod n; (k+r).P
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
    • G06F2207/7219—Countermeasures against side channel or fault attacks
    • G06F2207/7223—Randomisation as countermeasure against side channel attacks
    • G06F2207/7233—Masking, e.g. (A**e)+r mod n
    • G06F2207/7247—Modulo masking, e.g. A**e mod (n*r)
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/72—Indexing scheme relating to groups G06F7/72 - G06F7/729
    • G06F2207/7219—Countermeasures against side channel or fault attacks
    • G06F2207/7271—Fault verification, e.g. comparing two values which should be the same, unless a computational fault occurred

Definitions

  • a two-party communication system using symmetric key encryption can be described as follows.
  • the first party communicates its encryption key to the second party over a secure channel.
  • the first party then encrypts the secret message using the key and transmits the encrypted message to the second party via a public or unsecured channel.
  • the second party then decrypts the encrypted message using the symmetric key that has been communicated to the second party over the secure channel.
  • a major problem with such encryption systems is an efficient method for exchanging the secret keys, i. H. to find a safe channel.
  • asymmetrical encryption is carried out as follows. A party wishing to receive a secret message shares its public key with the other your party, that is, the party from which you want to receive a secret message. The public key is communicated via an unsecured channel, ie via a "public" channel.
  • the party wishing to send a secret message receives the public key of the other party, the message encrypted using the public key and sends the encrypted message again Ü "over a non-secure channel, ie via a public channel to the Party from which the public key originated: Only the party that generated the public key is able to provide a private key to decrypt the encrypted message, not even the party that uses the public key an encrypted message is able to decrypt the message.
  • An advantage of this concept is that no secure channel, ie no secret key exchange, is required between the two parties. The party who encrypted the message must and may the recipient's private key t know.
  • a physical analogue to the asymmetrical encryption concept or public key encryption concept is as follows. Consider a metal box, the lid of which is secured by a combination lock. The combination only knows the party who wants to receive an encrypted message. If the lock is left open and made publicly available, anyone who wants to send a secret message can put this message in the metal box and close the lid. However, only the person from whom the box comes knows the combination of the combination lock. Only he is able to decrypt the message, ie to open the metal box again. Even the one who put the message in the box is no longer able to get it out.
  • RSA cryptosystem Essential for asymmetrical or public key encryption concepts is the underlying mathematical problem, the solution of which is almost impossible to use using the public key for decryption, but whose solution is easily possible with knowledge of the private key.
  • One of the best known public key cryptosystems is the RSA cryptosystem.
  • the RSA cryptosystem is described in the "Handbook of Applied Cryptography", Menezes, van Oorschot, Vanstone, CRC Press 1997, pages 285-291.
  • FIG. 3 in order to represent the RSA algorithm.
  • the starting point is that one communication partner encrypts a message m, which the other communication partner must decrypt again.
  • the encrypting entity must first receive the public key (s, e) in a step 200 in order to be able to send the other party an encrypted message at all.
  • the encrypting entity must represent the message to be encrypted as an integer m in a step 210, where m must lie in the interval from 0 to n-1.
  • the encrypting entity In a step 220, which is the actual encryption step, the encrypting entity must calculate the following equation:
  • c is the encrypted message. This is then output in a step 230 and transmitted to the recipient of the encrypted message via a public channel, which is labeled 240 in FIG. 2.
  • the latter receives the encrypted message c in a step 250 and performs the following calculation in a step 260, which is the actual decryption step: mc d mod n.
  • the Chinese remainder of the sentence is described in the “Handbook of Applied Cryptography, which was mentioned earlier, on page 610 ff.
  • the Chinese remainder theorem, and particularly in its form, which is known as Garner 's algorithm, is based on splitting the modular exponentiation with the module n into two modular exponentiations of second sub-modules p, q, the sub-modules p, q being prime numbers and the product of which gives the module n.
  • a modular exponentiation with a long module is thus broken down into two modular exponentiations with shorter (typically half as long) sub-modules.
  • This method is advantageous in that only half as long arithmetic units are required or that, with the same length of an arithmetic unit, twice as long numbers can be used, which results in a more favorable ratio of security to chip area, that is generally in a better ratio of Performance at price results.
  • Mp c dp mod p.
  • Mq Another auxiliary variable Mq is calculated as follows:
  • the plain text message m is calculated as follows if c is the encrypted message:
  • the Chinese remainder set reduces the computing time efficiency or the chip area consumption of a security IC
  • the Chinese remainder set poses problems due to attacks on the cryptography system, such as B. so-called side-channel attacks, performance analyzes or
  • the object of the present invention is to provide a safe and efficient concept for calculating the modular exponentiation, which protects the RSA signature by means of CRT against error attacks.
  • the present invention is based on the knowledge that the security of the modular exponentiation, which is the basic operation for RSA encryption, can be increased even if the Chinese remainder theorem is used in order to be able to calculate the RSA exponentiation more efficiently.
  • Another advantage of the present invention is that existing crypto processors, with which the RSA exponentiation can be calculated using the CRT, do not have to be modified, but only the standard CRT parameters have to be modified, but not the central calculation steps for the calculation of the two modular exponents using the sub-modules. This means that all existing structures for key management of the RSA keys can continue to be used.
  • FIG. 1 shows a device for calculating the modular exposure according to a first exemplary embodiment of the present invention, in which the exponents of the auxiliary exponentiations are randomized;
  • FIG. 2a shows a section of a device for calculating the modular exponentiation according to a second
  • Embodiment of the present invention that can be used either alone or together with the first embodiment of the present invention, the sub-modules being randomized;
  • Fig. 3 is a schematic flow diagram of the RSA algorithm for encryption and decryption.
  • the input parameters are two prime numbers p, q, whose products result in the module n of the modular exponentiation.
  • Another input parameter is the key d.
  • the first exemplary embodiment of the present invention is illustrated using the decryption in the RSA algorithm.
  • An encrypted message c becomes private using the Key d the decrypted message m calculated according to the following equation:
  • the device according to the invention comprises a device 100 for calculating the first auxiliary variable dp according to the following equation:
  • Another device 102 for calculating a second auxiliary variable dq executes the following equation:
  • the device according to the invention for calculating a result of a modular exponentiation further comprises a device 104 for generating a random number IRND 104. This device is in turn followed by a device 106 in order to calculate a third auxiliary variable dp 'according to the following equation:
  • the third auxiliary variable dp ' is thus a randomized exponent of the first auxiliary exponentiation, which is calculated by means 110 for calculating the fifth auxiliary variable Mp, which is designed to carry out the following equation:
  • Mp c dp mod p.
  • a device 108 is provided to calculate a fourth auxiliary variable dq 'according to the following equation:
  • a means 112 calculates the sixth auxiliary variable Mq using the fourth auxiliary variable, which represents the randomized exponent of the second auxiliary exponentiation:
  • a device 114 finally calculates the result m, i.e. H. in the present example the decrypted message, according to the following equation:
  • a device according to a second exemplary embodiment of the present invention comprises a device 120 for generating a prime number T as a security parameter, which is preferably a relatively small prime number, so that the computing time advantage of the Chinese remaining sentence is not “sacrificed” too much in favor of security.
  • the result of the first auxiliary exponentiation Mp is then not used by the devices using the original auxiliary sub-modules p, q, but instead using the auxiliary sub-modules px T or qx T with the safety parameter 110 'or 112', the change in sub-modules p, q alone, ie without randomizing the
  • Auxiliary exponents dp 'and dq' provide increased security against cryptographic attacks.
  • the safest variant according to the present invention is to use both the randomization of the auxiliary exponents, as shown in FIG. 1, and the modified auxiliary modules, as shown in FIG. 2a.
  • the intermediate result check by the device 140 ensures that the algorithm is terminated even before a result is output if, for example, an error attack has been carried out on the security IC during the calculation of M p and / or M q .
  • This attack will fail because, in the event of such an attack, "CRT error" is generated by the device 140, so that no output is received and the error attack is therefore ineffective.
  • this protection by the intermediate result check is relatively inexpensive, since the parameter T is preferably a small prime number, so that the exponentiation in block 140 of FIG. 2b has a small exponent in comparison to the module.
  • 100 means for calculating a first auxiliary variable dp 102 means for calculating a second auxiliary variable dq 104 means for generating a random number IRND 106 means for generating a third auxiliary variable dp '108 means for generating a fourth auxiliary variable dq' 110 means for calculating a fifth auxiliary variable Mp 110 'means for generating the fifth auxiliary variable Mp using a modified sub-module 112 means for calculating a sixth auxiliary variable Mq 112' means for generating the sixth auxiliary variable Mq using a modified sub-module 114 means for calculating the result of the modular exponentiation 120 means for generating the Safety parameters T 140 device for calculating a seventh auxiliary variable H7 and an eighth auxiliary variable H8 142 device for confirming the correspondence of the seventh and eighth auxiliary variables 144 device for indicating an error in the CRT 200 Obtaining the public key 210 representing the message as a number 220 computing c 230 output c 240 channel

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Computing Systems (AREA)
  • Mathematical Analysis (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • Computational Mathematics (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Mathematical Physics (AREA)
  • General Engineering & Computer Science (AREA)
  • Storage Device Security (AREA)

Abstract

L'invention concerne un dispositif pour calculer le résultat d'une exponentiation modulaire, pour lequel on applique le théorème chinois des restes (CRT), selon lequel deux exponentiations auxiliaires sont calculées au moyen de deux exposants auxiliaires et de deux sous-modules. L'invention vise à augmenter la sécurité du calcul RSA-CRT face aux attaques cryptographiques. A cet effet, les exposants auxiliaires sont rendus aléatoires et/ou les sous-modules sont modifiés. Ainsi, le théorème chinois des restes, par l'efficacité de son temps de calcul, permet un décodage ou un codage RSA sûr.
EP02797920A 2001-09-06 2002-08-22 Dispositif et procede pour calculer le resultat d'une exponentiation modulaire Withdrawn EP1423786A2 (fr)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
DE10143728A DE10143728B4 (de) 2001-09-06 2001-09-06 Vorrichtung und Verfahren zum Berechnen eines Ergebnisses einer modularen Exponentiation
DE10143728 2001-09-06
PCT/EP2002/009405 WO2003023605A2 (fr) 2001-09-06 2002-08-22 Dispositif et procede pour calculer le resultat d'une exponentiation modulaire

Publications (1)

Publication Number Publication Date
EP1423786A2 true EP1423786A2 (fr) 2004-06-02

Family

ID=7697946

Family Applications (1)

Application Number Title Priority Date Filing Date
EP02797920A Withdrawn EP1423786A2 (fr) 2001-09-06 2002-08-22 Dispositif et procede pour calculer le resultat d'une exponentiation modulaire

Country Status (5)

Country Link
US (1) US7248700B2 (fr)
EP (1) EP1423786A2 (fr)
CN (1) CN1554047A (fr)
DE (1) DE10143728B4 (fr)
WO (1) WO2003023605A2 (fr)

Families Citing this family (21)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2830146B1 (fr) * 2001-09-24 2003-10-31 Gemplus Card Int Procede de mise en oeuvre, dans un composant electronique, d'un algorithme de cryptographie et composant correspondant
DE10222212A1 (de) 2002-05-16 2003-12-04 Giesecke & Devrient Gmbh Ausspähungsgeschützte modulare Inversion
CN1682484B (zh) * 2002-09-11 2012-03-21 德国捷德有限公司 受保护的密码计算
DE10304451B3 (de) * 2003-02-04 2004-09-02 Infineon Technologies Ag Modulare Exponentiation mit randomisiertem Exponenten
FR2858496B1 (fr) * 2003-07-31 2005-09-30 Gemplus Card Int Procede pour la mise en oeuvre securisee d'un algorithme de cryptographie de type rsa et composant correspondant
JP4626148B2 (ja) * 2004-01-07 2011-02-02 株式会社日立製作所 復号または署名作成におけるべき乗剰余算の計算方法
US7426749B2 (en) * 2004-01-20 2008-09-16 International Business Machines Corporation Distributed computation in untrusted computing environments using distractive computational units
FR2880148A1 (fr) * 2004-12-23 2006-06-30 Gemplus Sa Procede d'exponentiation securisee et compacte pour la cryptographie
FR2887351A1 (fr) * 2005-06-16 2006-12-22 St Microelectronics Sa Protection d'un calcul d'exponentiation modulaire effectue par un circuit integre
FR2888690A1 (fr) * 2005-07-13 2007-01-19 Gemplus Sa Procede cryptographique pour la mise en oeuvre securisee d'une exponentiation et composant associe
US9313027B2 (en) * 2005-12-29 2016-04-12 Proton World International N.V. Protection of a calculation performed by an integrated circuit
US8150029B2 (en) * 2005-12-29 2012-04-03 Proton World International N.V. Detection of a disturbance in a calculation performed by an integrated circuit
FR2898199A1 (fr) * 2006-03-02 2007-09-07 Gemplus Sa Procede de securisation de l'execution d'une suite d'etapes logiquement enchainees
US20080104402A1 (en) * 2006-09-28 2008-05-01 Shay Gueron Countermeasure against fault-based attack on RSA signature verification
US8280041B2 (en) * 2007-03-12 2012-10-02 Inside Secure Chinese remainder theorem-based computation method for cryptosystems
EP1998491A1 (fr) * 2007-05-31 2008-12-03 Thomson Licensing Procédé pour calculer des modules RSA compressés
FR2919739B1 (fr) * 2007-08-03 2009-12-04 Oberthur Card Syst Sa Procede de traitement de donnees protege contre les attaques par generation de fautes et dispositif associe
CN100576226C (zh) * 2008-07-10 2009-12-30 浙江工业大学 基于中国剩余定理的数据库加密方法
FR2977952A1 (fr) * 2011-07-13 2013-01-18 St Microelectronics Rousset Protection d'un calcul d'exponentiation modulaire par multiplication par une quantite aleatoire
CN103580869B (zh) * 2013-11-06 2016-09-21 北京华大信安科技有限公司 一种crt-rsa签名方法及装置
FR3112003B1 (fr) * 2020-06-26 2023-03-03 Idemia France Procede de traitement cryptographique, dispositif electronique et programme d'ordinateur associes

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CA1318027C (fr) * 1987-10-12 1993-05-18 Jun Takayama Methode et dispositif de codage et de decodage de donnees utilisant un systeme numerique a residus
GB2318892B (en) * 1996-10-31 2001-07-11 Motorola Ltd Co-processor for performing modular multiplication
US6282290B1 (en) * 1997-03-28 2001-08-28 Mykotronx, Inc. High speed modular exponentiator
US5991415A (en) * 1997-05-12 1999-11-23 Yeda Research And Development Co. Ltd. At The Weizmann Institute Of Science Method and apparatus for protecting public key schemes from timing and fault attacks
ATE325478T1 (de) * 1998-01-02 2006-06-15 Cryptography Res Inc Leckresistentes kryptographisches verfahren und vorrichtung
DE19811833A1 (de) * 1998-03-18 1999-09-30 Siemens Ag Schlüsselaustauschprotokoll
JP3551853B2 (ja) * 1999-08-27 2004-08-11 日本電気株式会社 αＹａ＋βＸｂ＋１＝０という形の定義方程式をもつ代数曲線暗号における安全なパラメータの生成装置、生成方法、および記録媒体

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO03023605A2 *

Also Published As

Publication number Publication date
US20040215685A1 (en) 2004-10-28
DE10143728A1 (de) 2003-04-03
DE10143728B4 (de) 2004-09-02
US7248700B2 (en) 2007-07-24
WO2003023605A2 (fr) 2003-03-20
CN1554047A (zh) 2004-12-08
WO2003023605A3 (fr) 2004-04-01

Similar Documents

Publication Publication Date Title
DE10143728B4 (de) Vorrichtung und Verfahren zum Berechnen eines Ergebnisses einer modularen Exponentiation
DE60001630T2 (de) Sichere gegenseitige Netzwerkauthenifizierung und Schlüselaustauschprotokoll
EP0472714B1 (fr) Procede d'authentification d'un utilisateur utilisant une station de donnees
DE3685987T2 (de) Verfahren zum vermindern der fuer eine rsa-verschluesselung benoetigten veraenderlichen speicherkapazitaet.
DE69935469T2 (de) Verfahren zur schnellen Ausführung einer Entschlüsselung oder einer Authentifizierung
EP1125395B1 (fr) Procede et systeme pour authentifier une premiere instance et une seconde instance
CH660822A5 (de) Zufallsprimzahlen-erzeugungsmittel in einer mit oeffentlichem schluessel arbeitenden daten-verschluesselungsanlage.
EP2656535B1 (fr) Procédé cryptographique
DE2843583A1 (de) Verfahren und vorrichtung zum entschluesseln verschluesselter nachrichten
EP1368929B1 (fr) Procédé d'authentification
DE10304451B3 (de) Modulare Exponentiation mit randomisiertem Exponenten
EP1346509B1 (fr) Procédé et dispositif pour déterminer une paire de clés et pour produire des clés RSA
EP3899845A1 (fr) Procédé pour obtenir une signature aveugle
WO2003034268A2 (fr) Procede et dispositif pour garantir un calcul d'exponentiation au moyen du theoreme des restes chinois (trc)
WO2003034649A2 (fr) Procede et dispositif pour garantir un calcul dans un algorithme cryptographique
EP4101118A1 (fr) Génération de clé et protocole pace avec protection contre des attaques par canal latéral
DE102019216203A1 (de) Auf Blockverschlüsselung basierender Proof-of-Work
DE10042234C2 (de) Verfahren und Vorrichtung zum Durchführen einer modularen Exponentiation in einem kryptographischen Prozessor
DE10162496C5 (de) Verfahren und Vorrichtung zum Absichern einer Berechnung in einem kryptographischen Algorithmus
EP2120391B1 (fr) Method et système de generation d'une clé asymmetrique et son utilisation pour la carte electronique pour la santé.
EP1062763B1 (fr) Procede d'echange de codes
DE102022002399A1 (de) Schlüsselgenerierung und PACE mit Sicherung gegen Seitenkanalangriffe
DE102007014971B4 (de) Versteckte Sicherheitsmerkmale in digitalen Signaturen
DE102004001659A1 (de) Vorrichtung und Verfahren zum Konvertieren einer ersten Nachricht in eine zweite Nachricht
DE102006012180A1 (de) Kryptographisches Verfahren

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20040223

AK Designated contracting states

Kind code of ref document: A2

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR IE IT LI LU MC NL PT SE SK TR

AX Request for extension of the european patent

Extension state: AL LT LV MK RO SI

17Q First examination report despatched

Effective date: 20040920

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 20050331