[go: up one dir, main page]

FR2885711B1 - Procede et materiel modulaire et aleatoire pour la reduction polynomiale - Google Patents

Procede et materiel modulaire et aleatoire pour la reduction polynomiale

Info

Publication number
FR2885711B1
FR2885711B1 FR0504779A FR0504779A FR2885711B1 FR 2885711 B1 FR2885711 B1 FR 2885711B1 FR 0504779 A FR0504779 A FR 0504779A FR 0504779 A FR0504779 A FR 0504779A FR 2885711 B1 FR2885711 B1 FR 2885711B1
Authority
FR
France
Prior art keywords
modular
polynomial reduction
random equipment
random
equipment
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.)
Expired - Fee Related
Application number
FR0504779A
Other languages
English (en)
Other versions
FR2885711A1 (fr
Inventor
Vincent Dupaquis
Michel Douguet
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.)
Rambus Inc
Original Assignee
Atmel Corp
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 Atmel Corp filed Critical Atmel Corp
Priority to FR0504779A priority Critical patent/FR2885711B1/fr
Priority to US11/203,939 priority patent/US7805480B2/en
Priority to EP06749987.1A priority patent/EP1889398B1/fr
Priority to CN2006800209415A priority patent/CN101194457B/zh
Priority to PCT/US2006/013795 priority patent/WO2006124160A2/fr
Priority to JP2008511127A priority patent/JP4875700B2/ja
Priority to KR1020077029023A priority patent/KR101252318B1/ko
Priority to TW095116180A priority patent/TWI386818B/zh
Publication of FR2885711A1 publication Critical patent/FR2885711A1/fr
Application granted granted Critical
Publication of FR2885711B1 publication Critical patent/FR2885711B1/fr
Priority to US12/887,361 priority patent/US20110016167A1/en
Anticipated expiration legal-status Critical
Expired - Fee Related 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/724—Finite field arithmetic
    • G06F7/726—Inversion; Reciprocal calculation; Division of elements of a finite field
    • 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/724—Finite field arithmetic
    • 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

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)
  • Complex Calculations (AREA)
  • Error Detection And Correction (AREA)
  • Navigation (AREA)
FR0504779A 2005-05-12 2005-05-12 Procede et materiel modulaire et aleatoire pour la reduction polynomiale Expired - Fee Related FR2885711B1 (fr)

Priority Applications (9)

Application Number Priority Date Filing Date Title
FR0504779A FR2885711B1 (fr) 2005-05-12 2005-05-12 Procede et materiel modulaire et aleatoire pour la reduction polynomiale
US11/203,939 US7805480B2 (en) 2005-05-12 2005-08-15 Randomized modular polynomial reduction method and hardware therefor
CN2006800209415A CN101194457B (zh) 2005-05-12 2006-04-12 随机模数化多项式约简方法及其硬件
PCT/US2006/013795 WO2006124160A2 (fr) 2005-05-12 2006-04-12 Methode de reduction polynomiale modulaire randomisee et materiel destine a la mise en oeuvre de ce procede
EP06749987.1A EP1889398B1 (fr) 2005-05-12 2006-04-12 Méthode de réduction polynomiale modulaire randomisée et matériel destiné à la mise en oeuvre de ce procédé
JP2008511127A JP4875700B2 (ja) 2005-05-12 2006-04-12 ランダム化されたモジュラー多項式のリダクション方法およびそのためのハードウェア
KR1020077029023A KR101252318B1 (ko) 2005-05-12 2006-04-12 랜덤화된 모듈러 다항식 약분 방법 및 그 방법을 위한하드웨어
TW095116180A TWI386818B (zh) 2005-05-12 2006-05-08 密碼安全模多項式簡化方法及執行該方法之計算硬體
US12/887,361 US20110016167A1 (en) 2005-05-12 2010-09-21 Randomized modular polynomial reduction method and hardware therefor

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
FR0504779A FR2885711B1 (fr) 2005-05-12 2005-05-12 Procede et materiel modulaire et aleatoire pour la reduction polynomiale

Publications (2)

Publication Number Publication Date
FR2885711A1 FR2885711A1 (fr) 2006-11-17
FR2885711B1 true FR2885711B1 (fr) 2007-07-06

Family

ID=35431948

Family Applications (1)

Application Number Title Priority Date Filing Date
FR0504779A Expired - Fee Related FR2885711B1 (fr) 2005-05-12 2005-05-12 Procede et materiel modulaire et aleatoire pour la reduction polynomiale

Country Status (5)

Country Link
US (2) US7805480B2 (fr)
JP (1) JP4875700B2 (fr)
CN (1) CN101194457B (fr)
FR (1) FR2885711B1 (fr)
TW (1) TWI386818B (fr)

Families Citing this family (24)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2862454A1 (fr) * 2003-11-18 2005-05-20 Atmel Corp Methode de reduction modulaire aleatoire et equipement associe
FR2885711B1 (fr) * 2005-05-12 2007-07-06 Atmel Corp Procede et materiel modulaire et aleatoire pour la reduction polynomiale
US7961877B2 (en) * 2006-12-14 2011-06-14 Intel Corporation Factoring based modular exponentiation
US8144864B2 (en) * 2007-12-28 2012-03-27 Intel Corporation Method for speeding up the computations for characteristic 2 elliptic curve cryptographic systems
TWI406548B (zh) * 2010-10-27 2013-08-21 Univ Southern Taiwan 橢圓曲線加密運算電路
US9778932B2 (en) 2013-01-23 2017-10-03 International Business Machines Corporation Vector generate mask instruction
US9715385B2 (en) 2013-01-23 2017-07-25 International Business Machines Corporation Vector exception code
US9471308B2 (en) 2013-01-23 2016-10-18 International Business Machines Corporation Vector floating point test data class immediate instruction
US9804840B2 (en) 2013-01-23 2017-10-31 International Business Machines Corporation Vector Galois Field Multiply Sum and Accumulate instruction
US9513906B2 (en) 2013-01-23 2016-12-06 International Business Machines Corporation Vector checksum instruction
US9823924B2 (en) 2013-01-23 2017-11-21 International Business Machines Corporation Vector element rotate and insert under mask instruction
CN103699357B (zh) * 2013-12-05 2016-11-23 西安交通大学 一种用于模乘和模平方的快速模约简算法电路
US9425961B2 (en) * 2014-03-24 2016-08-23 Stmicroelectronics S.R.L. Method for performing an encryption of an AES type, and corresponding system and computer program product
IL239880B (en) * 2015-07-09 2018-08-30 Kaluzhny Uri Simplified montgomery multiplication
CN106254059B (zh) * 2016-07-26 2020-03-20 华为技术有限公司 一种运算方法和安全芯片
JP6602276B2 (ja) * 2016-08-29 2019-11-06 キヤノン株式会社 情報処理装置、情報処理装置の制御方法及びプログラム
US10833868B2 (en) * 2017-12-06 2020-11-10 Intel Corporation Direct anonymous attestation-based apparatus and method
US10218494B1 (en) * 2018-02-23 2019-02-26 ISARA Corporation Performing block form reductions modulo non-Mersenne primes in cryptographic protocols
DE102018113475A1 (de) * 2018-06-06 2019-12-12 Infineon Technologies Ag Rechenwerk zum rechnen mit maskierten daten
WO2020145503A1 (fr) * 2019-01-10 2020-07-16 Crypto Lab Inc. Appareil de traitement de messages approximativement chiffrés et procédés associés
CN112506470B (zh) * 2020-12-21 2024-07-02 深圳比特微电子科技有限公司 芯片和计算系统
KR20220105495A (ko) * 2021-01-20 2022-07-27 삼성전자주식회사 부채널 공격에 내성이 있는 모듈라 곱셈을 위한 장치 및 방법
US11502819B2 (en) * 2021-01-21 2022-11-15 Nxp B.V. Efficient masked polynomial comparison
CN113253972A (zh) * 2021-05-13 2021-08-13 南京航空航天大学 一种lac中稀疏多项式乘法加速器的fpga实现方法

Family Cites Families (39)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4839896A (en) * 1987-02-10 1989-06-13 Data Systems Technology Corp. Fast remainder decoding for a Reed-Solomon code
KR19990024971A (ko) 1997-09-09 1999-04-06 정선종 모듈러 승산장치
US5144574A (en) 1989-01-30 1992-09-01 Nippon Telegraph And Telephone Corporation Modular multiplication method and the system for processing data
US5077793A (en) 1989-09-29 1991-12-31 The Boeing Company Residue number encryption and decryption system
EP0431629A3 (en) 1989-12-08 1993-07-21 Sony Corporation Mutual division circuit
US5210710A (en) 1990-10-17 1993-05-11 Cylink Corporation Modulo arithmetic processor chip
US5479511A (en) 1991-11-05 1995-12-26 Thomson Consumer Electronics S.A. Method, sender apparatus and receiver apparatus for modulo operation
US5373560A (en) 1991-12-06 1994-12-13 Schlafly; Roger Partial modular reduction method
US5513133A (en) 1992-11-30 1996-04-30 Fortress U&T Ltd. Compact microelectronic device for performing modular multiplication and exponentiation over large numbers
FR2726668B1 (fr) 1994-11-08 1997-01-10 Sgs Thomson Microelectronics Procede de mise en oeuvre de reduction modulaire selon la methode de montgomery
US5999627A (en) 1995-01-07 1999-12-07 Samsung Electronics Co., Ltd. Method for exponentiation in a public-key cryptosystem
US5724279A (en) 1995-08-25 1998-03-03 Microsoft Corporation Computer-implemented method and computer for performing modular reduction
JP3504050B2 (ja) 1996-01-26 2004-03-08 株式会社東芝 べき乗剰余演算方法及び装置
US6091819A (en) 1996-08-16 2000-07-18 Telcordia Technologies, Inc. Accelerating public-key cryptography by precomputing randomly generated pairs
US5793659A (en) 1996-10-15 1998-08-11 United Microelectronics Corporation Method of modular reduction and modular reduction circuit
GB9627069D0 (en) 1996-12-30 1997-02-19 Certicom Corp A method and apparatus for finite field multiplication
US6088453A (en) 1997-01-27 2000-07-11 Kabushiki Kaisha Toshiba Scheme for computing Montgomery division and Montgomery inverse realizing fast implementation
US6175850B1 (en) 1997-02-03 2001-01-16 Nippon Telegraph And Telephone Corporation Scheme for carrying out modular calculations based on redundant binary calculation
JP2001505325A (ja) 1997-09-16 2001-04-17 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ タイミング攻撃を阻止する標準化されたモジュラべき乗を計算することにより復号メカニズムを実行する方法と装置
DE69930334T2 (de) 1998-01-28 2006-11-09 Hitachi, Ltd. IC-Karte ausgerüstet mit einer Verarbeitungsanlage für Elliptische-Kurven-Verschlüsselung
FR2776445A1 (fr) 1998-03-17 1999-09-24 Schlumberger Ind Sa Procede de securisation de donnees mettant en oeuvre un algorithme cryptographique
CN1275748A (zh) * 1999-05-26 2000-12-06 朗迅科技公司 计算模数除法的余数的方法和装置
US20020055962A1 (en) 1999-11-12 2002-05-09 Richard Schroeppel Automatically solving equations in finite fields
DE19963407A1 (de) 1999-12-28 2001-07-12 Giesecke & Devrient Gmbh Tragbarer Datenträger mit Zugriffsschutz durch Nachrichtenverfremdung
US7072072B1 (en) * 2000-05-02 2006-07-04 Xerox Corporation Color rendering optimized for text and line art
DE60139401D1 (de) 2000-05-15 2009-09-10 Sandisk Il Ltd Erweiterung des bereichs rechnerischer körper von ganzen zahlen
US6917957B2 (en) 2000-08-28 2005-07-12 Sun Microsystems, Inc. Method and apparatus for performing modular division using counters
DE10107376A1 (de) 2001-02-16 2002-08-29 Infineon Technologies Ag Verfahren und Vorrichtung zum modularen Multiplizieren und Rechenwerk zum modularen Multiplizieren
WO2002073395A2 (fr) 2001-03-09 2002-09-19 The Athena Group, Inc. Procede et appareil de multiplication et/ou de reduction modulaire
US7164765B2 (en) 2001-04-11 2007-01-16 Hitachi, Ltd. Method of a public key encryption and a cypher communication both secure against a chosen-ciphertext attack
FR2829335A1 (fr) 2001-09-06 2003-03-07 St Microelectronics Sa Procede de brouillage d'un calcul a quantite secrete
US7461115B2 (en) 2002-05-01 2008-12-02 Sun Microsystems, Inc. Modular multiplier
US7627114B2 (en) * 2002-10-02 2009-12-01 International Business Machines Corporation Efficient modular reduction and modular multiplication
FR2853424B1 (fr) * 2003-04-04 2005-10-21 Atmel Corp Architecture de multiplicateurs polynomial et naturel combines
FR2856537B1 (fr) 2003-06-18 2005-11-04 Gemplus Card Int Procede de contre-mesure par masquage de l'accumulateur dans un composant electronique mettant en oeuvre un algorithme de cryptographie a cle publique
FR2862454A1 (fr) 2003-11-18 2005-05-20 Atmel Corp Methode de reduction modulaire aleatoire et equipement associe
WO2006124160A2 (fr) 2005-05-12 2006-11-23 Atmel Corporation Methode de reduction polynomiale modulaire randomisee et materiel destine a la mise en oeuvre de ce procede
FR2885711B1 (fr) * 2005-05-12 2007-07-06 Atmel Corp Procede et materiel modulaire et aleatoire pour la reduction polynomiale
US8024391B2 (en) * 2006-11-06 2011-09-20 Atmel Rousset S.A.S. Modular multiplication method with precomputation using one known operand

Also Published As

Publication number Publication date
FR2885711A1 (fr) 2006-11-17
US20100023572A1 (en) 2010-01-28
TWI386818B (zh) 2013-02-21
US20110016167A1 (en) 2011-01-20
TW200703037A (en) 2007-01-16
JP2008541166A (ja) 2008-11-20
JP4875700B2 (ja) 2012-02-15
US7805480B2 (en) 2010-09-28
CN101194457A (zh) 2008-06-04
CN101194457B (zh) 2011-06-01

Similar Documents

Publication Publication Date Title
FR2885711B1 (fr) Procede et materiel modulaire et aleatoire pour la reduction polynomiale
GB0605066D0 (en) Method and apparatus for monitoring structures
TWI340907B (en) Apparatus and method for changing web design
TWI367401B (en) Lithographic apparatus and lithographic apparatus cleaning method
GB2465536B (en) A method and apparatus for disinfecting enclosed spaces
EP2064916A4 (fr) Procédés et appareil de traitement des acouphènes
IL192860A0 (en) Surveillance apparatus and method
EP2051768A4 (fr) Appareil et procédé pour le traitement du fibrome
EP1948517A4 (fr) Procede et appareil de sterilisation
IL184315A0 (en) Method and apparatus for manufacturing products
GB0725060D0 (en) Multi-hop routing method and apparatus
GB0810770D0 (en) Method and apparatus for cleaning heat structures
IL193731A0 (en) Apparatus and method for inspecting circuit structures
FI20060400A0 (fi) Menetelmä ja laitteisto suihkutuslaitteistossa
EP1889398A4 (fr) Methode de reduction polynomiale modulaire randomisee et materiel destine a la mise en oeuvre de ce procede
FI20050880A0 (fi) Menetelmä ja laitteisto hitsausta varten
FI20040537L (fi) Menetelmä ja sovitelma rullien siirtämiseksi pakkauksen aikana
ITBO20040389A1 (it) Apparato e metodo per la formatura di scatole
DE602008002036D1 (de) Spurabweichungsverhinderungsvorrichtung und -verfahren
FI20060176A0 (fi) Laitteisto ja menetelmä liuoksen jäähdyttämiseksi
GB0526363D0 (en) Monitoring apparatus and method
FI20070363A0 (fi) Menetelmä ja laitteisto betonituotteiden valamiseksi
GB2425019B (en) Connection inhibition apparatus and method
NO20065893L (no) Framgangsmate og anordning for fjerning av elementer som er opplost i metallsmelte
FI20065184A0 (fi) Laitteisto ja menetelmä ilmanpoistossa massasulputusta

Legal Events

Date Code Title Description
TP Transmission of property
TP Transmission of property

Owner name: INSIDE SECURE, FR

Effective date: 20121115

CA Change of address

Effective date: 20131112

PLFP Fee payment

Year of fee payment: 12

PLFP Fee payment

Year of fee payment: 13

PLFP Fee payment

Year of fee payment: 14

PLFP Fee payment

Year of fee payment: 15

CD Change of name or company name

Owner name: VERIMATRIX, FR

Effective date: 20191119

CA Change of address

Effective date: 20191209

TP Transmission of property

Owner name: RAMBUS INC., US

Effective date: 20200402

PLFP Fee payment

Year of fee payment: 16

RG Lien (pledge) cancelled

Effective date: 20200828

GC Lien (pledge) constituted

Effective date: 20201105

PLFP Fee payment

Year of fee payment: 17

ST Notification of lapse

Effective date: 20230105