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 AU2003273500A priority Critical patent/AU2003273500A1/en
Priority to CA002494769A priority patent/CA2494769A1/fr
Priority to EP03755658A priority patent/EP1532519A2/fr
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)
  • Complex Calculations (AREA)
  • Power Sources (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
AU2003273500A AU2003273500A1 (en) 2002-08-05 2003-07-29 Method for accelerating calculations in modular arithmetic
CA002494769A CA2494769A1 (fr) 2002-08-05 2003-07-29 Procede pour accelerer des calculs en arithmetique modulaire
EP03755658A EP1532519A2 (fr) 2002-08-05 2003-07-29 Calcul cryptographique suivant la methode de montgomery

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
FR2843211B1 (fr) 2005-05-20
AU2003273500A1 (en) 2004-02-25
CA2494769A1 (fr) 2004-02-19
EP1532519A2 (fr) 2005-05-25
FR2843211A1 (fr) 2004-02-06
WO2004015559A2 (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
TW200500940A (en) Simd integer multiply high with round and shift
Yanık et al. Incomplete reduction in modular arithmetic
WO2003038645A3 (fr) Architecture de traitement evolutive
WO2004103056A3 (fr) Unite de reduction de processeur permettant d'accumuler de multiples operandes avec ou sans saturation
KR20090006465A (ko) 타원 곡선 암호 시스템에 대한 부채널 공격에 대응하는방법
EP1160661A3 (fr) Procédé pour la multiplication scalaire sur une courbe elliptique et dispositif correspondant
Wenger et al. Exploring the design space of prime field vs. binary field ECC-hardware implementations
Zhao et al. Ultra high-speed SM2 ASIC implementation
Hossain et al. High-performance FPGA implementation of modular inversion over F_256 for elliptic curve cryptography
WO2003023605A3 (fr) Dispositif et procede pour calculer le resultat d'une exponentiation modulaire
Adikari et al. Hybrid binary-ternary number system for elliptic curve cryptosystems
Ghosh et al. Core based architecture to speed up optimal ate pairing on FPGA platform
JP5073669B2 (ja) 同時スカラー乗算方法
CN118312138A (zh) 蒙哥马利模乘的硬件加速器实现方法及硬件加速器
AU2002353282A8 (en) Pipelined core in montgomery multiplier
WO2004015559A3 (fr) Procede pour accelerer des calculs en arithmetique modulaire
Aoki et al. Efficient word size modular multiplication over signed integers
Weimerskirch et al. Generic GF (2m) arithmetic in software and its application to ECC
Adikari et al. Towards faster and greener cryptoprocessor for eta pairing on supersingular elliptic curve over
WO2023003737A3 (fr) Moteur cryptographique à voies multiples et ses opérations
Javeed et al. Efficient montgomery multiplier for pairing and elliptic curve based cryptography
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