UM2 – LIRMM Létat de lart en implémentations en matériel de lalgorithme de Montgomery Doctorant: Daniel Mesquita Direction de thèse: Michel Robert / Lionel

UM2 – LIRMM

L’état de l’art en implémentations en matériel L’état de l’art en implémentations en matériel de l’algorithme de Montgomeryde l’algorithme de Montgomery

Doctorant: Daniel Mesquita

Direction de thèse: Michel Robert / Lionel Torres / Gilles Sassatelli

LIRMM - Université Montpellier II (France)

Boursier du Government brésilien dans la cadre du Accord de Coopération Internationel - CAPES/COFECUB (2002/2006)

mes

qu

ita@

lirm

m.f

r

Slide 2 / 21

UM2 – LIRMM

PlanPlan

• Introduction

• Méthodologie

• Travaux Réalisés

• Conclusions / Perspectives

• Introduction

• Méthodologie

• Travaux Réalisés

• Conclusions / Perspectives

mes

qu

ita@

lirm

m.f

r

Slide 3 / 21

UM2 – LIRMM

IntroductionIntroduction

• But de la thèse– Proposer une architecture pour la Cryptographie

– Hypothèses préliminaires:

– Les architectures à grain épais sont viables pour la cryptographie.

– La reconfiguration peut apporter quelque chose à des applications cryptographiques (flexibilité, securité, etc)

– L’adéquation algorithme-architecture peut tomber dans une proposte d’une nouvelle façon de représenter les grands nombres entiers.

mes

qu

ita@

lirm

m.f

r

Slide 4 / 21

UM2 – LIRMM


• Cryptographie à clé publique

– Exemples: RSA, ElGammal, Courbes Elliptiques

adversaire

Source des clés

chiffrage

texte en clairsource

dechiffrage

texte en clairdestination

Canal non-securisé

Alice Bernard

e

m m

c

d

Canal non-securiséc = me mod n m = cd mod n

mes

qu

ita@

lirm

m.f

r

Slide 5 / 21

UM2 – LIRMM

• Les opérateurs arithmetiques pour la cryptographie à clé publique

– Les algorithmes Mermle-Hellman(1978), RSA(1978), Pohlig-Hellman (1978), Rabin (1979), El Gammal (1984), Courbes Elliptiques (1985) et LUC (1993) utilisent l’arithmetique modulaire

– Les opérations en jeu sont:


Mxy

Mxmyx

Myx

Mx

y

mod

mod;mod)(

mod)(

mod

1

Réduction modulaire

Addition

Multiplication et exponentiation

Inversion

mes

qu

ita@

lirm

m.f

r

Slide 6 / 21

UM2 – LIRMM

• RSA

1. Clé publique:• Choisir p et q qui doivent être deux grands nombres premiers, et calculer le

produit:

• Choisir une clé de chiffrement aléatoire e telle que e et (p-1) (q-1) soient premiers entre eux.

2. Clé privée• Utiliser l’algorithme d’Euclide pour calculer la clé de dechiffrement d, tel que:

3. Chiffrement

4. Dechiffrement


qpn

11mod1 qped

nmc e mod

ncm d mod

mes

qu

ita@

lirm

m.f

r

Slide 7 / 21

UM2 – LIRMM

MéthodologieMéthodologie

A rb re d 'inve s tiga tion

N ive au B it N ive au M ot

A lg o rith m e d e M on tg om e ry B a rre t, B o o th , e tc ...

P ro d u it M o du la ire R é d uc tion , inve rsio n , e tc ...

Id é n tif ica tio n d esO p é ra te u rs A rith m étiq u es

A sym étriq ueR S A , E C C , e tc

S ym étriq ueA E S , B lo w fish , e tc

C ryp tog ra p h ie

S ys to lic R ing

G ra in é p a is

F P G A

G ra in f in

A rch itec tu res R e co n fig u ra b les

P a rtie " f ixe "P a rtie re con fig u ra b le

M e m o ireB us

S o C

D e n sité fon c tion e lleR é m a ne n ce

S u rfa ce , v itesse ,co n so m m a tio n , e tc.

M é triq u es

Adéquation AlgorithmeArchitectur

eSilicium


eSilicium

mes

qu

ita@

lirm

m.f

r

Slide 8 / 21

UM2 – LIRMM



eSilicium


eSilicium








C ryp tog ra p h ie

S ys to lic R ing

G ra in é p a is

F P G A

G ra in f in



M e m o ireB us

S o C



M é triq u es

mes

qu

ita@

lirm

m.f

r

Slide 9 / 21

UM2 – LIRMM



eSilicium


eSilicium








C ryp tog ra p h ie

S ys to lic R ing

G ra in é p a is

F P G A

G ra in f in



M e m o ireB us

S o C



M é triq u es

CRT, RNS, MRS

mes

qu

ita@

lirm

m.f

r

Slide 10 / 21

UM2 – LIRMM



eSilicium


eSilicium








C ryp tog ra p h ie

S ys to lic R ing

G ra in é p a is

F P G A

G ra in f in



M e m o ireB us

S o C



M é triq u es

CRT, RNS, MRS

mes

qu

ita@

lirm

m.f

r

Slide 11 / 21

UM2 – LIRMM

Travaux RéalisésTravaux Réalisés

• Implémentation de l’algorithme de Montgomery• GPP• DSP• ARGE (Systolic Ring)• FPGA (direction à distance)

• Développement des outils à l’aide à programmation du Systolic Ring

• L’État de l’Art

mes

qu

ita@

lirm

m.f

r

Slide 12 / 21

UM2 – LIRMM


• L’algorithme de Montgomery

Version Bit Version Mot

.

;Re

;

;

;mod

10

;0int

),,(

1000

end

Rturn

RR

MqBaRR

mbarq

ktoifor

R

MBAMont

i

i

.

;Re

;2

;2mod)(

10

;0int

),,(

00

end

Rturn

MqBaRR

barq

ntoifor

R

MBAMont

ii

ii

mes

qu

ita@

lirm

m.f

r

Slide 13 / 21

UM2 – LIRMM


• SRing (VLSI’03)Technologie : ARGE SRing

Fréquence : 200MHz

Taille Clé : 16 bits

Algorithme: Version bit

Data

Management code

Host

Processor

Operative Layer

RAM

Co

nfi

gu

rati

on

Lay

er

Configuration Sequencer

Confi guration Code

DnodeDnode

RAM

Systolic Ring

Data

Management code

Host

Processor

Operative Layer

RAM

Co

nfi

gu

rati

on

Lay

er

Configuration Sequencer

Confi guration Code

DnodeDnode

RAM

Systolic Ring

Dnode Dnode

Switch Switch

Dnode Dnode

Switch Switch

Dn

od

eD

no

de

Switch

Switch

Dn

od

eD

no

de

Switch

Switch

DnodeDnode

SwitchSwitch

DnodeDnode

SwitchSwitch

Dn

od

eD

no

de

Switc

hSw

itch

Dn

od

eD

no

de

Switc

hSw

itch

Bus

_Swi

tch

Bus_Switch

Bus_Switch

Bus_Switch

Operative layer

mes

qu

ita@

lirm

m.f

r

Slide 14 / 21

UM2 – LIRMM


• SRing (VLSI’03)

Dnode Dnode

Switch Switch

Dnode Dnode

Switch Switch

Dn

od

eD

no

de

Switch

Switch

Dn

od

eD

no

de

Switch

Switch

DnodeDnode

SwitchSwitch

DnodeDnode

SwitchSwitch

Dn

od

eD

no

de

Switc

hSw

itch

Dn

od

eD

no

de

Switc

hSw

itch

Bus

_Swi

tch

Bus_Switch

Bus_Switch

Bus_Switch

Operative layer

ALU + MULT

Reg FILE

MU

XM

UX

Reg0

Reg1

Reg2

Reg3

Reg4

Reg5

Reg6

Reg7

Se

lect

Se

lect

Contrôleur

In0

In7

In0

In7

Dnode_config

sel

Controller

Dnode local controller Dnode datapath

mes

qu

ita@

lirm

m.f

r

Slide 15 / 21

UM2 – LIRMM


• SRing (VLSI’03)

U = 0for i=0 to n-1

U = U + Ai.BU = (U +U0.N) >> 2

EndforIf Un > N then U = Un – N

else U = Un

1- R0 A AND R9

2- R1 B * R0

3- R15 R15 + R1

4- R14 R15 AND R9

5- R14 R14 * N6- R15 R15 + R14

7- R15 R15 >> 18- A A >> 1

MU

XM

UX

R0 A AND R9

R1 B * R0

R15 R15 + R1

R14 R15 AND R9

R14 R14 * M

R15 R15 + R14

R15 R15 >> 1

R10 R10 >> 1

Sel

ect

Sel

ect

Contrôleur

Dnode_config

sel

Controller

”000..01”Preloaded in registers

ALU

Reg File

mes

qu

ita@

lirm

m.f

r

Slide 16 / 21

UM2 – LIRMM


• SRing Web Tools

mes

qu

ita@

lirm

m.f

r

Slide 17 / 21

UM2 – LIRMM


• SRing Web Tools

Configurator

mes

qu

ita@

lirm

m.f

r

Slide 18 / 21

UM2 – LIRMM


• SRing Web ToolsAnalyzer

mes

qu

ita@

lirm

m.f

r

Slide 19 / 21

UM2 – LIRMM


AnnéeAnnée AuteurAuteur CibleCible AlgorithmeAlgorithme Taille cléTaille clé FréquenceFréquence CyclesCycles DébitDébit TempsTemps SurfaceSurface

1991 HAFNER ASIC DES 20Mbps

1993 BERTIN ARGE RSA/ Enc 512 40 MHZ 600Kbps

1993 ELDRIDGE ASIC MMM

1996 SOUSA DSP Exp Mod 1024 50 MHZ 25382 1,321ms

1997 ROYO ASIC MMM 768 50 MHZ 400 72.5Kbps 0,008ms 77 mm²

1999 BLUM FPGA EMM 1024 2101248 49.78ms 3786 CLB

1999 TAYLOR ARGE IDEA 128 100 MHZ 126.6Kbps

1999 BAILEY DSP RSA / Sig-Ver 1024 200 MHZ 11.7/1.2ms

2000 GROBSCHÄDL ASIC MMBarret 2x512 (CRT) 200 MHZ 227 2.5Mbps 70 mm²

2000 PHILLIPS SMART CARD

RSA /Sig 1024 (CRT) 25 MHZ 887ms

2001 TENCA ASIC MMM 1024 50 MHZ 0.11ms 16Kgates

2001 GOODMAN ASIC EMM+CRT 1024 50 MHZ 17ms 8.4 mm²

2001 NOZAKI ASIC RSA / Sig-Ver 2048 (CRT) 80 MHZ 29.2/8.9ms 6.9 mm²

2002 NEDJAH FPGA MMM 1024 50 MHZ 0.27ms 639 CLB

2002 DALY FPGA MMM 1024 120 MHZ 2047 0,017ms 87 CLB

2002 DESCHAMPS FPGA MMM 32 25 MHZ 0,000325ms 334 CLB

2003 ÖRS FPGA MMM 1024 100 MHZ 0,032 ms 2853 CLB

2003 SRing ARGE MMM 16 200 MHZ 0,004 ms 2 mm²

L’état de l’art – L’état de l’art – Raw Data

mes

qu

ita@

lirm

m.f

r

Slide 20 / 21

UM2 – LIRMM

ConclusionsConclusions

• Conclusions– Les ARGE ne semblent pas être bien adaptés à des applications

cryptographiques– L’opération la plus chronofage c’est aussi difficilement

parallélisable– Jusqu’à ce moment (et à ma connaissance), il n’y a aucune

implémetation des algorithmes de cryptographie que se sert de la reconfiguration (dynamique ou statique)

• Perspectives– Investiguer le RNS– Étudier plusieurs algorithmes de crypto– Découvrir à propos de la multicryptographie

• Conclusions– Les ARGE ne semblent pas être bien adaptés à des applications

cryptographiques– L’opération la plus chronofage c’est aussi difficilement

parallélisable– Jusqu’à ce moment (et à ma connaissance), il n’y a aucune

implémetation des algorithmes de cryptographie que se sert de la reconfiguration (dynamique ou statique)

• Perspectives– Investiguer le RNS– Étudier plusieurs algorithmes de crypto– Découvrir à propos de la multicryptographie

mes

qu

ita@

lirm

m.f

r

Slide 21 / 21

UM2 – LIRMM

ConclusionsConclusions

• Questions

• For further information– http://www.lirmm.fr/~mesquita – http://www.lirmm.fr/~w3mic/SRING/

• Questions

• For further information– http://www.lirmm.fr/~mesquita – http://www.lirmm.fr/~w3mic/SRING/

??

Documents

UM2 – LIRMM Létat de lart en implémentations en matériel de lalgorithme de Montgomery Doctorant: Daniel Mesquita Direction de thèse: Michel Robert / Lionel