WO2004015559A3 - Procede pour accelerer des calculs en arithmetique modulaire - Google Patents

Procede pour accelerer des calculs en arithmetique modulaire Download PDF

Info

Publication number
WO2004015559A3
WO2004015559A3 PCT/FR2003/050022 FR0350022W WO2004015559A3 WO 2004015559 A3 WO2004015559 A3 WO 2004015559A3 FR 0350022 W FR0350022 W FR 0350022W WO 2004015559 A3 WO2004015559 A3 WO 2004015559A3
Authority
WO
WIPO (PCT)
Prior art keywords
words
stored
modulo
argument
entries
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.)
Ceased
Application number
PCT/FR2003/050022
Other languages
English (en)
Other versions
WO2004015559A2 (fr
Inventor
Jean-Luc Stehle
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.)
Everbee Networks SA
Original Assignee
Everbee Networks SA
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 Everbee Networks SA filed Critical Everbee Networks SA
Priority to EP03755658A priority Critical patent/EP1532519A2/fr
Priority to CA002494769A priority patent/CA2494769A1/fr
Priority to AU2003273500A priority patent/AU2003273500A1/en
Publication of WO2004015559A2 publication Critical patent/WO2004015559A2/fr
Publication of WO2004015559A3 publication Critical patent/WO2004015559A3/fr
Anticipated expiration legal-status Critical
Ceased 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/728—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 using Montgomery reduction

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • General Engineering & Computer Science (AREA)
  • Error Detection And Correction (AREA)
  • Power Sources (AREA)
  • Complex Calculations (AREA)

Abstract

L'invention concerne un procédé permettant d'accélérer les calculs d'exponentiation en arithmétique modulo un nombre N stocké sur q mots. Les exponentiations interviennent notamment dans des protocoles de cryptographie mis en œuvre à l'aide de ressources informatiques. Le procédé comporte : un premier algorithme ayant pour objet de remplacer un argument, stocké sur 2q mots, par un résultat qui est congru modulo N audit argument et dont les q mots de poids faibles sont nuls, un premier opérateur prenant deux entrées stockées chacune sur q mots et fournissant en sortie un nombre W, stocké sur q mots, dont le produit par R est congru modulo N au produit des deux entrées. R est une puissance de deux supérieure à N. Le procédé permet d'économiser de la puissance de calcul et de l'espace mémoire.
PCT/FR2003/050022 2002-08-05 2003-07-29 Procede pour accelerer des calculs en arithmetique modulaire Ceased WO2004015559A2 (fr)

Priority Applications (3)

Application Number Priority Date Filing Date Title
EP03755658A EP1532519A2 (fr) 2002-08-05 2003-07-29 Calcul cryptographique suivant la methode de montgomery
CA002494769A CA2494769A1 (fr) 2002-08-05 2003-07-29 Procede pour accelerer des calculs en arithmetique modulaire
AU2003273500A AU2003273500A1 (en) 2002-08-05 2003-07-29 Method for accelerating calculations in modular arithmetic

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0209942A FR2843211B1 (fr) 2002-08-05 2002-08-05 Procede pour accelerer des calculs en arithmetique modulaire
FR02/09942 2002-08-05

Publications (2)

Publication Number Publication Date
WO2004015559A2 WO2004015559A2 (fr) 2004-02-19
WO2004015559A3 true WO2004015559A3 (fr) 2004-05-13

Family

ID=30129691

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2003/050022 Ceased WO2004015559A2 (fr) 2002-08-05 2003-07-29 Procede pour accelerer des calculs en arithmetique modulaire

Country Status (5)

Country Link
EP (1) EP1532519A2 (fr)
AU (1) AU2003273500A1 (fr)
CA (1) CA2494769A1 (fr)
FR (1) FR2843211B1 (fr)
WO (1) WO2004015559A2 (fr)

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5499299A (en) * 1993-07-02 1996-03-12 Fujitsu Limited Modular arithmetic operation system
EP0939362A1 (fr) * 1998-02-26 1999-09-01 STMicroelectronics S.A. Coprocesseur d'arithmétique modulaire permettant de réaliser des opérations non modulaires rapidement

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5499299A (en) * 1993-07-02 1996-03-12 Fujitsu Limited Modular arithmetic operation system
EP0939362A1 (fr) * 1998-02-26 1999-09-01 STMicroelectronics S.A. Coprocesseur d'arithmétique modulaire permettant de réaliser des opérations non modulaires rapidement

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
ARAZI B: "DOUBLE-PRECISION MODULAR MULTIPLICATION BASED ON A SINGLE-PRECISIONMODULAR MULTIPLIER AND A STANDARD CPU", IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, IEEE INC. NEW YORK, US, vol. 11, no. 5, 1 June 1993 (1993-06-01), pages 761 - 769, XP000399844, ISSN: 0733-8716 *
DUSSE S R ET AL: "A CRYPTOGRAPHIC LIBRARY FOR THE MOTOROLA DSP56000", LECTURE NOTES IN COMPUTER SCIENCE. ADVANCES IN CRYPTOLOGY- EUROCRYPT '90, 21-24 MAY 1990, AARHUS, DK, 1991, Springer Verlag, BERLIN, DE, pages 230 - 244, XP000471664 *

Also Published As

Publication number Publication date
AU2003273500A1 (en) 2004-02-25
EP1532519A2 (fr) 2005-05-25
WO2004015559A2 (fr) 2004-02-19
FR2843211A1 (fr) 2004-02-06
FR2843211B1 (fr) 2005-05-20
CA2494769A1 (fr) 2004-02-19

Similar Documents

Publication Publication Date Title
US8345864B1 (en) Elliptic curve cryptography scalar multiplication with on demand acceleration table generation
US6212279B1 (en) Method of elliptic curve cryptographic key exchange using reduced base tau expansion in non-adjacent form
Uhsadel et al. Enabling full-size public-key algorithms on 8-bit sensor nodes
Eberle et al. A cryptographic processor for arbitrary elliptic curves over GF (2/sup m/)
CA2252078A1 (fr) Systeme cryptographique resistant aux attaques contre la signature de puissance
TW200500940A (en) Simd integer multiply high with round and shift
Yanık et al. Incomplete reduction in modular arithmetic
WO2005101190A3 (fr) Processeur d'operations paralleles de multiplication et de reduction vectorielles a semantiques sequentielles
WO2004103056A3 (fr) Unite de reduction de processeur permettant d'accumuler de multiples operandes avec ou sans saturation
KR20090006465A (ko) 타원 곡선 암호 시스템에 대한 부채널 공격에 대응하는방법
Zhao et al. Ultra high-speed SM2 ASIC implementation
Wenger et al. Exploring the design space of prime field vs. binary field ECC-hardware implementations
Bajard et al. Modular number systems: Beyond the Mersenne family
WO2003023605A3 (fr) Dispositif et procede pour calculer le resultat d'une exponentiation modulaire
JP5073669B2 (ja) 同時スカラー乗算方法
CN118312138A (zh) 蒙哥马利模乘的硬件加速器实现方法及硬件加速器
Moon et al. Fast VLSI arithmetic algorithms for high-security elliptic curve cryptographic applications
Loi et al. Flexible elliptic curve cryptography coprocessor using scalable finite field arithmetic blocks on FPGAs
WO2004015559A3 (fr) Procede pour accelerer des calculs en arithmetique modulaire
Weimerskirch et al. Generic GF (2m) arithmetic in software and its application to ECC
WO2023003737A3 (fr) Moteur cryptographique à voies multiples et ses opérations
CN101253473A (zh) 用于对椭圆弧上的点进行标量乘法的方法
Javeed et al. Efficient montgomery multiplier for pairing and elliptic curve based cryptography
Xiao et al. A High‐Speed Elliptic Curve Cryptography Processor for Teleoperated Systems Security
US9025766B2 (en) Efficient hardware architecture for a S1 S-box in a ZUC cipher

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A2

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KP KR KZ LC LK LR LS LT LU LV MA MD MG MK MN MW MX MZ NI NO NZ OM PH PL PT RO RU SC SD SE SG SK SL TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A2

Designated state(s): GH GM KE LS MW MZ SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LU MC NL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2003755658

Country of ref document: EP

ENP Entry into the national phase

Ref document number: 2494769

Country of ref document: CA

WWP Wipo information: published in national office

Ref document number: 2003755658

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: JP

WWW Wipo information: withdrawn in national office

Country of ref document: JP