Untersuchung des NTRU – Algorithmus für die Tauglichkeitzur Hardwareakzeleration von Kryptoverfahren im Bereich

skalierbarer Sicherheit

Danijel Vollstädt

0. zugrundeliegende Arbeiten 1 / 38

Fachbereich Informatik, Arbeitsbereich TAMS

S. Witt, P. Hartmann (Studienarbeit)Vergleichende Analyse und VHDL-basierte Implementation vonZufallsgeneratoren auf Chipkarten, Universität Hamburg, 2001

M. BöttgerKomplexitätsabschätzung von hardwareakzelerierten Attacken aufECC-Kryptoverfahren, Universität Hamburg, 2002

F. BohnsackUntersuchung von Elliptischen Kurven für die Tauglichkeit zurHardwareakzeleration von Kryptoverfahren, Universität Hamburg,1997

S. GorrKonzeption, Evaluierung und Implementation eines Akzelerators für Elliptische Kurven, Universität Hamburg, 2000

1. Motivation 2 / 38

Übersicht

1. Motivation

2. mathematische Grundlagen

3. intuitives Beispiel

4. binäres Beispiel

5. Komponenten

6. Syntheseergebnisse

7. Ergebnisse und Ausblick

1. Motivation 2 / 38

Übersicht

1. Motivation

2. mathematische Grundlagen

3. intuitives Beispiel

4. binäres Beispiel

5. Komponenten

6. Syntheseergebnisse

7. Ergebnisse und Ausblick

1. Motivation 3 / 38

Anwendungsgebiete

•Chipkarten

z.B. Schipaß, Fahrkarten, Parkhauskarten

•Dongle

z.B. Softwareschutz, Internetzugang

•Handy

z.B. Authentifizierung, Gesprächsverschlüsselung

Schickt den Kofferzum Empfänger

Schickt den Kofferzum Absender

Entfernt daseigene Schloß

Entfernt daseigene Schloß

1. Motivation 4 / 38

Prinzip des Diffie-Hellman-Schlüsselaustauschs

Absender Empfänger

1. Motivation 5 / 38

Schlüssellängenvergleich von RSA, ECC und NTRU

RSA – Rivest Shamir AdlemanECC – Elliptic Curve CryptographyNTRU – Number Theory Research Unit

100

1000

10000

20

00

20

05

20

10

20

15

20

20

20

25

20

30

Jahr

Sc

hlü

ss

elb

reit

e [

Bit

]

ECC

NTRU

RSA

1. Motivation 6 / 38

0

500

1000

1500

2000

2500

112 168 196 263 503 1024 2048

Bitbreite der Verschlüsselung

Ve

rsc

hlü

ss

elu

ng

sze

it (

ms

) ECC

NTRU

RSA

1

100

10000

112 168 196 263 503 1024 2048

Bitbreite der Verschlüsselung

Ve

rsc

hlü

ss

elu

ng

sze

it (

ms

)

ECC

NTRU

RSA

Die Verschlüsselungszeiten im Vergleich

1. Motivation 7 / 38

Die Entschlüsselungszeiten im Vergleich

0

50

100

150

200

250

300

350

112 168 196 263 503 1024 2048

Bitbreite der Entschlüsselung

En

tsc

hlü

ss

elu

ng

sze

it (

ms

)

ECC

NTRU

RSA

1

100

10000

112 168 196 263 503 1024 2048

Bitbreite der Entschlüsselung

En

tsc

hlü

ss

elu

ng

sze

it (

ms

)

ECC

NTRU

RSA

2. mathematische Grundlagen 8 / 38

Übersicht

1. Motivation

2. mathematische Grundlagen

3. intuitives Beispiel

4. binäres Beispiel

5. Komponenten

6. Syntheseergebnisse

7. Ergebnisse und Ausblick

Arithmetik in Polynomringen: Addition

;5N 32q

)()()()( 3232 1225520818 xxxxxxxbxa

(mod )q32 323323 xxx 223 x

23123 x

maximaler Polynomgrad: N-1maximaler Koeffizientengrad: q-1

(mod q)

2. mathematische Grundlagen 9 / 38

Arithmetik in Polynomringen: Multiplikation

;5N 32q

)()()()( 4323 159112633 xxxxxxxbxa (mod q)

)5432 1327149 xxxxx

39x 414x( )765 1327 xxx

(

2. mathematische Grundlagen 10 / 38

Arithmetik in Polynomringen: Multiplikation

;5N 32q

)()()()( 4323 159112633 xxxxxxxbxa (mod q)

432 2714913 xxxx

39x 414x( )765 1327 xxx

( )

2. mathematische Grundlagen 10 / 38

Arithmetik in Polynomringen: Multiplikation

;5N 32q

)()()()( 4323 159112633 xxxxxxxbxa (mod q)

432 2714913 xxxx

39x 414x( )765 1327 xxx

( )

2. mathematische Grundlagen 10 / 38

Arithmetik in Polynomringen: Multiplikation

;5N 32q

)()()()( 4323 159112633 xxxxxxxbxa (mod q)

432 2714913 xxxx

39x 414x(

( )213271 xx )

2. mathematische Grundlagen 10 / 38

Arithmetik in Polynomringen: Multiplikation

;5N 32q

)()()()( 4323 159112633 xxxxxxxbxa (mod q)

432 2714913 xxxx

39x 414x(

( )213271 xx )

)( 432 1381812 xxxx (mod q)

)( 432 198311820 xxxx

2. mathematische Grundlagen 10 / 38

Arithmetik in Polynomringen: Multiplikation

;5N 32q

)()()()( 4323 159112633 xxxxxxxbxa (mod q)

)( 432 198311820 xxxx

2. mathematische Grundlagen 10 / 38

Arithmetik in Polynomringen: Inversion

;7N 11q

642 323 xxxxa )(65432 2244242 xxxxxxxA )(

63 22222210 xxxxAxa )()( (mod q)1

Die Inverse zu a(x) ist A(x), bzw. A(x) ist invers zu a(x).N

qq xxZZRxaxA /])[/()(),(

2. mathematische Grundlagen 11 / 38

Definition (Körper) Ein Körper ist ein Tripel mit folgenden Regeln:• ist ein Ring• ist eine kommutative Gruppe

),,( K)},{\( 0K

),,( K

Ring, endlicher Körper, irreduzibles Polynom

Definition (Ring) Ein Ring ist ein Tripel für das folgende Regeln gelten:•(R,+) ist ein kommutative Gruppe• ist ein Halbgruppe•die Distributivgesetze gelten

),( R

),,( R

Ein Polynom mit Das Polynom f(x) heißt irreduzibel über F,Wenn es nicht als Produkt zweier Polynome aus F[x] mit positivemGrad dargestellt werden kann.

Definition (irreduzibles Polynom) Sei F ein endlicher Körper. Sei .)deg( 1f

][)( xFxf

2. mathematische Grundlagen 12 / 38

Satz F[x]/(f(x)) ist ein Körper, wenn f(x) ein irreduzibles Polynomüber F[x] ist. In diesem Fall kann das multiplikative Inverse mit dem erweiterten Euklidischen Algorithmus bestimmt werden.

Gibt es immer genau eine Inverse ?

Für jedes existiert genau einemultiplikative Inverse, wenn p prim und f(x) irreduzibel ist.

)(/])[/()( xfxZZRxb pp

)/(])[/()( 33 xxZZRxb p hat nicht immer eine Inverse.

)/(])[/()( 147 xxxZZRxb q hat immer eine Inverse.

2. mathematische Grundlagen 13 / 38

Übersicht

1. Motivation

2. mathematische Grundlagen

3. intuitives Beispiel

4. binäres Beispiel

5. Komponenten

6. Syntheseergebnisse

7. Ergebnisse und Ausblick

3. intuitives Beispiel 14 / 38

Bob erzeugt einen öffentlichen Schlüssel

öffentliche Parameter Bobs geheime Parameter

3N

)/(])[/( 33 xxZZRp

3p7q

)/(])[/( 37 xxZZRq

Bob wählt ein :)( pRxf

12 xxf )(

Dazu die Inversen:

222 xxxFp )(

443 2 xxxFq )(

Er wählt zufällig das Polynom:

xxg )(öffentlicher Schlüssel

344 2 xxxh )(Der öffentliche Schlüssel:

)()()( xgxFqxh mod(q)

344 2 xx

3. intuitives Beispiel 15 / 38

Susan verschlüsselt eine Nachricht

öffentliche ParameterSusans Verschlüsselung

3N

)/(])[/( 33 xxZZRp

3p7q

)/(])[/( 37 xxZZRq

öffentlicher Schlüssel

344 2 xxxh )(

Sie wählt zufällig das Polynom:xxr )(

Nachricht von Susan:binär: „111“, entspricht:

111 2 xxxm )(

12 xx

und berechnet den Cyphertext:

)()()()( xmxhxprxe mod(q)

3. intuitives Beispiel 16 / 38

Susan verschlüsselt eine Nachricht

öffentliche ParameterSusans Verschlüsselung

3N

)/(])[/( 33 xxZZRp

3p7q

)/(])[/( 37 xxZZRq

öffentlicher Schlüssel

344 2 xxxh )(

Sie wählt zufällig das Polynom:xxr )(

Nachricht von Susan:binär: „111“, entspricht:

111 2 xxxm )(

12 xx

und berechnet den Cyphertext:

)()()()( xmxhxprxe mod(q)

14 2 xx

3. intuitives Beispiel 16 / 38

Bob entschlüsselt Susans Nachricht

Susans Cyphertext Bobs Entschlüsselung

14 2 xxxe )(

)()()( xexfxa (mod q)

erste Entschlüsselungsgl.:

3. intuitives Beispiel 17 / 38

Bob entschlüsselt Susans Nachricht

Susans Cyphertext Bobs Entschlüsselung

14 2 xxxe )(

)()()( xexfxa (mod q)

erste Entschlüsselungsgl.:

255 2 xx

zweite Entschlüsselungsgl.:

)()()( xaxFxm p (mod p)

12 xx

Susans Nachricht war „111“

3. intuitives Beispiel 17 / 38

Verschlüsselung und Schlüsselerzeugung

mhrpe

gFqh

(mod q)

(mod q)

erste Entschlüsselungsgleichung

mfgrp

mfgrp

mfgrpFqf

mfgFqrpf

)(

)(

)(

1

efa

(mod q)

(mod q)

(mod q)

(mod q)(mod q)

zweite Entschlüsselungsgleichung

Fpam

m

mfFp

mfFpgrFpp

Fpmfgrp

)(

)(

(mod p)

(mod p)

(mod p)

(mod p)(mod p)

Warum funktioniert das Verfahren NTRU ?

3. intuitives Beispiel 18 / 38

Verschlüsselung und Schlüsselerzeugung

mhrpe

gFqh

(mod q)

(mod q)

erste Entschlüsselungsgleichung

mfgrp

mfgrp

mfgrpFqf

mfgFqrpf

)(

)(

)(

1

efa

(mod q)

(mod q)

(mod q)

(mod q)(mod q)

zweite Entschlüsselungsgleichung

Fpam

m

mfFp

mfFpgrFpp

Fpmfgrp

)(

)(

(mod p)

(mod p)

(mod p)

(mod p)(mod p)

Warum können r und g zufällig gewählt werden ?

Weil dieser Term als vielfachesvon p wegfällt.

3. intuitives Beispiel 18 / 38

Verschlüsselung und Schlüsselerzeugung

mhrpe

gFqh

(mod q)

(mod q)

erste Entschlüsselungsgleichung

mfgrp

mfgrp

mfgrpFqf

mfgFqrpf

)(

)(

)(

1

efa

(mod q)

(mod q)

(mod q)

(mod q)(mod q)

zweite Entschlüsselungsgleichung

Fpam

m

mfFp

mfFpgrFpp

Fpmfgrp

)(

)(

(mod p)

(mod p)

(mod p)

(mod p)(mod p)

Warum bleibt m beim Übergang von mod q zu p erhalten ?

Gilt die Gleichungfmgrpfmgrp (mod q)

nicht, kann ausfmgrp (mod p)

kein korrektes m resultieren.

Wählt man die Werte p, r, g, fund m aus einer Menge, die relativ zu q klein ist, so daß

4qmf und ,4

qgrp

gilt die Gleichung.

3. intuitives Beispiel 18 / 38

Verschlüsselung und Schlüsselerzeugung

mhrpe

gFqh

(mod q)

(mod q)

erste Entschlüsselungsgleichung

mfgrp

mfgrp

mfgrpFqf

mfgFqrpf

)(

)(

)(

1

efa

(mod q)

(mod q)

(mod q)

(mod q)(mod q)

zweite Entschlüsselungsgleichung

Fpam

m

mfFp

mfFpgrFpp

Fpmfgrp

)(

)(

(mod p)

(mod p)

(mod p)

(mod p)(mod p)

Zugrundeliegendes Problem (Trapdoorfunktion)

Polynomfaktorisierungsproblem

3. intuitives Beispiel 18 / 38

Übersicht

1. Motivation

2. mathematische Grundlagen

3. intuitives Beispiel

4. binäres Beispiel

5. Komponenten

6. Syntheseergebnisse

7. Ergebnisse und Ausblick

4. binäres Beispiel 19 / 38

Binäres Beispielöffentliche Parameter

)/(][ 1232 xxxZRp

)/(][ 162 xxxZRq

Bobs geheime Parameter2xf

1xFp145 xxFq

xg

Bob generiert den Public Key

gFh q (mod q) 15 x

Bob entschlüsselt Susans Nachricht

efa (mod q) xxxx 345

aFpm (mod p) xx 2

4. binäres Beispiel 20 / 38

mprhe (mod q) 1235 xxxx

Susan verschlüsselt Ihre Botschaft 12 xm

100001

010g

011pF

Binäres Beispielöffentliche Parameter Bobs geheime Parameter

)/(][ 11012 xZRp

)/(][ 10000112 xZRq

Bob generiert den Public Key

gFh q (mod q)

Susan verschlüsselt Ihre Botschaft

mprhe (mod q)

Bob entschlüsselt Susans Nachricht

efa (mod q)aFpm (mod p)

100f

110001qF

101111

111010101

4. binäres Beispiel 20 / 38

12 xm

Parameterwahlöffentliche Parameter

)/(][ 1232 xxxZRp

)/(][ 162 xxxZRq

Bobs geheime Parameter2xf

1xFp145 xxFq

xg

mfgrp (mod q)

xxxx

xxxxxx

mfgrp

345

2223 111 )()()(

Der und der müssen sein.

)( grpGrad )( mfGrad )(qGrad

Wählt man die Körper ist die Gleichung

immer erfüllt.

))(())(( xpGradxqGrad 3

Die Nachrichtenexpansion ist

.m3

4. binäres Beispiel 21 / 38

Übersicht

1. Motivation

2. mathematische Grundlagen

3. intuitives Beispiel

4. binäres Beispiel

5. Komponenten

6. Syntheseergebnisse

7. Ergebnisse und Ausblick

5. Komponenten 22 / 38

Die Komponenten von NTRU

•einen geeigneten Zufallsgenerator

•Verfahren zur Inversenberechnung

•arithmetische Operationen mod 2

•Multiplikation

5. Komponenten 23 / 38

Wahl des Zufallsgenerators

S. Witt, P. HartmannVergleichende Analyse und VHDL-basierte Implementation vonZufallsgeneratoren auf Chipkarten, Universität Hamburg

Rang Durchsatz Zellenbedarf Leistungsaufnahme

1 RC4 LFSR RC4

2 LFSR BBS LFSR

3 BBS RC4 BBS

4 EC EC EC

LSFR – Linear Feedback Shift Register

5. Komponenten 24 / 38

Wahlkriterien für LSFR

•linearer, geringer Zellenbedarf•Qualität der Zufallszahlen gering (Berlekamp-Massey Algorithmus)

5. Komponenten 25 / 38

Methoden zur Inversenberechnung

Intuitive Methode Jedes Element des Körpers wird geprüft, ob es das Inverse ist

)( NO 2

Erweiterter Euklidischer Berechnet die Inverse mithilfe des Algorithmus Euklidischen Algorithmus.

))(log( 22NO

Almost Inverse Berechnet die Inverse mithilfe des Algorithm Euklidischen Algorithmus.

Dazu werden nur Verschiebe- undAdditionsfunktion verwendet.

))(log( 22NO

5. Komponenten 26 / 38

modulo 2 Multiplizierer

G. Orlando, C.PaarA Super-Serial Galois Fields Multiplier For FPGAs And Ist ApplicationTo Public-Key Algorithms, Nappa Valley/CA

M. BöttgerKomplexitätsabschätzung von hardwareakzelerierten Attacken aufECC-Kryptoverfahren, Universität Hamburg

Takte Zellen

Serieller Mult. N

Superserieller Mult. 1

)(NO21)( NO

5. Komponenten 27 / 38

Software oder Hardwarerealisierung ?

Software Hardware

Schlüsselerzeugung

Invertierer

Multiplizierer

LSFR

--

Verschlüsselung --

Addierer

Multiplizierer

LSFR

Entschlüsselung --Multiplizierer

Reduzierer

5. Komponenten 28 / 38

Datenflußgraphder

Verschlüsselung

5. Komponenten 29 / 38

Datenflußgraphder

Entschlüsselung

5. Komponenten 30 / 38

Übersicht

1. Motivation

2. mathematische Grundlagen

3. intuitives Beispiel

4. binäres Beispiel

5. Komponenten

6. Syntheseergebnisse

7. Ergebnisse und Ausblick

6. Syntheseergebnisse 31 / 38

Zellenbedarf des Zufallsgenerators

0

500

1000

1500

2000

10 20 30 40 50 60

Bitbreite

Ze

llen

be

da

rf

6. Syntheseergebnisse 32 / 38

Zellenbedarf der Verschlüsselung

6. Syntheseergebnisse 33 / 38

0

5000

10000

15000

10 20 30 40 50 60

Bitbreite

Ze

llen

be

da

rf

ECC

NTRU

Zellenbedarf der Entschlüsselung

6. Syntheseergebnisse 34 / 38

0

5000

10000

15000

10 20 30 40 50 60

Bitbreite

Ze

llen

be

da

rf

NTRU

ECC

Übersicht

1. Motivation

2. mathematische Grundlagen

3. intuitives Beispiel

4. binäres Beispiel

5. Komponenten

6. Syntheseergebnisse

7. Ergebnisse und Ausblick

7. Ergebnisse und Ausblick 35 / 38

Ergebnisse

•Wählt man Körper und

,f(x) und g(x) irreduzibel

mit Grad(f(x)) > 3 Grad(g(x)), erhält man ein binäres NTRU.

•mit Grad(g(x)) > 1 ist das binäre NTRU bitweise skalierbar.

7. Ergebnisse und Ausblick 36 / 38

)(/])[/( xfxZZRf 2

)(/])[/( xgxZZRg 2

Ausblick

•Sicherheit von NTRU und binärem NTRU zu ECC und RSA

•Kann die Sicherheit duch die Verwendung von Ringenstatt Körpern erhöht werden ? (Inversenberechnung durch lin. Gleichungssysteme)

•Welchen Einfluß haben verschiedene irred. Polynome auf dieSicherheit von NTRU ?

7. Ergebnisse und Ausblick 37 / 38

Vielen Dank für Ihre Aufmerksamkeit !

7. Ergebnisse und Ausblick 38 / 38