Sử dụng công nghệ cứng hóa FPGA trong mã hóa dữ liệu

I HC THÁI NGUYÊN

TRNG
I HC CÔNG NGH THÔNG TIN VÀ TRUYN THÔNG

NGUYN H NG NHANH

S

DNG CÔNG NGH CNG HÓA FPGA

TRONG MÃ HÓA D LIU

LUN VN THC S KHOA HC MÁY TÍNH

THÁI NGUYÊN, NM 2015

I HC THÁI NGUYÊN

TRNG
I HC CÔNG NGH THÔNG TIN VÀ TRUYN THÔNG

NGUYN H NG NHANH

S

DNG CÔNG NGH CNG HÓA FPGA

TRONG MÃ HÓA D LIU

Chuyên ngành : Khoa hc máy tính

Mã s : 60 48 01 01

LUN VN THC S KHOA HC MÁY TÍNH

HNG DN KHOA HC: TIN S H VN CANH

THÁI NGUYÊN, NM 2015

LI CAM
OAN

Tôi xin cam
oan, nhng ni dung liên quan ti
 tài
c trình bày

trong lun v n là do b

n thân t tìm hiu, nghiên c u di s hng dn khoa

hc ca Thy giáo Tin s H Vn Canh.

Các nhn xét, kt lun
c trích dn
y
 theo b

n gc.

Tôi xin chu trách nhim trc pháp lut li cam
oan ca mình.

Hc viên thc hin

Nguyn Hng Nhanh

LI CM N

Em xin gi li c

m n chân thành ti các Thy thuc Vin Công ngh

Thông tin/Vin Hàn lâm Khoa hc và Công ngh Vit Nam và Thy Cô giáo

ca Trng i hc Công ngh Thông tin và Truyn thông/i hc Thái

Nguyên
ã tn tình truyn
t cho em nhng kin th c quý báu trong sut quá

trình hc tp ti Trng.

Em cng xin gi li c

m n ti gia
ình, bn bè,
ng nghip và các

ng
i
ã thng xuyên
ng viên, khích l giúp
 em trong sut quá trình

hc tp cng nh hoàn thành lun v n ca mình.

c bit, em xin gi ti Thy giáo Tin s H Vn Canh - ngi
ã

giúp
, tn tình ch b

o, hng dn t m cho em trong quá trình làm
 tài

vi lòng bit n và li c

m n sâu s!c. Trong thi gian làm vic vi Thy, em

không nhng hc h"i
c nhiu kin th c b# ích v các phng pháp mã

hoá và tm quan trng ca mã hoá d liu trong thi
i ngày nay mà còn hc

c tinh thn làm vic, thái
nghiên c u khoa hc nghiêm túc ca thy.

Mc dù em
ã c g!ng hoàn thành
 tài vi t$t c

n% lc ca b

n thân

nhng ch!c ch!n s& không tránh kh"i nhng thiu sót. Em kính mong nhn

c s c

m thông và tn tình ch b

o ca Quý Thy Cô và các bn.

Mt ln na, em xin chân thành c

m n !

Thái Nguyên, tháng 10 n
m 2015

Nguyn Hng Nhanh

MC LC

Trang

LI CAM
OAN i

LI CM N ii

MC LC iii

DANH MC CH VIT T!T vi

DANH MC BNG vii

DANH MC HÌNH viii

M"
#U 1

Ch$%ng 1

T&NG QUAN V M'T S( H H MT MÃ HIN
I 4

1.1. C% s) khoa hc c*a h m+t mã 4

1.1.1. Yêu cu c b

n
i vi h mã hóa 5

1.1.2. Các thành phn c b

n ca h mã hóa 5

1.1.3. Vai trò ca mã hóa 6

1.2. H mã hoá khoá ,i x-ng 7

1.2.1. Chu'n mã hoá d liu DES 7

1.2.1.1. Lch s ra
i 7

1.2.1.2. T#ng quát 8

1.2.1.3. To khóa 10

1.2.1.4. Hoán v kh(i
u 12

1.2.1.5. Mã hóa chi tit mt vòng 12

1.2.1.6. Hoán v cui cùng 17

1.2.1.7. Gi

i mã DES 17

1.2.1.8.  an toàn ca thut toán 17

1.2.2. Chu'n mã hoá nâng cao AES 19

1.2.2.1. T#ng quan mã hóa AES 19

2.1.2.2. Phép bin
#i SubBytes và InvSubBytes 22

2.1.2.3. Phép bin
#i ShiftRows và InvShiftRows 24

2.1.2.4. Phép bin
#i MixColumns và InvMixColumns 25

2.1.2.5. Key scheduling 27

2.1.2.6. Quy trình gi

i mã 28

1.3. H mã hoá khoá công khai 29

1.3.1. H mã hóa RSA 30

1.3.1.1. Khái quát 30

1.3.1.2. Mô t

h mã hoá RSA 30

1.3.1.3. To khóa 31

1.3.1.4. Mã hóa 32

1.3.1.5. Gi

i mã 32

1.3.1.6. Mt s phng pháp t$n công 33

1.3.1.6.1. Phng pháp s d)ng *(n) 33

1.3.1.6.2. Áp d)ng thut toán phân tích ra th+a s 33

1.3.1.6.3. B, khóa da trên t$n công lp li 34

1.3.1.7. ánh giá chung 34

1.3.2. H mã hóa Elgamal 35

1.3.2.1. Quá trình to khoá, lp mã và gi

i mã 35

1.3.2.2. ánh giá
an toàn 36

1.4. Kt lu+n ch$%ng 37

Ch$%ng 2

T&NG QUAN V CÔNG NGH FPGA 39

2.1. C% s) khoa hc c*a các thit b. kh/ trình 39

2.2. Khái quát v0 m1t s công ngh c-ng hóa hin nay 40

2.2.1. Công ngh ASIC 40

2.2.2. Công ngh ASSP 41

2.2.3. Công ngh Configurable Processor 42

2.2.4. Công ngh DSP 42

2.2.5. Công ngh MCU 43

2.2.6. Công ngh RISC/GP 44

2.3. Công ngh FPGA

46

2.3.1. Gii thiu chung v FPGA 46

2.3.2. T#ng quan v FPGA 47

2.3.2.1. C$u trúc các FPGA 47

2.3.2.2. Các khi lôgic c$u hình (Configurable logic Block) 48

2.3.2.3. Các ngun kt ni (Routes) 48

2.3.2.4. Phân loi FPGA 48

2.3.3. Các công ngh lp trình FPGA 49

2.3.3.1. Công ngh lp trình dùng RAM t-nh 50

2.3.3.2. Các thit b lp trình cu chì nghch (Anti-fuse) 51

2.3.3.3. Công ngh lp trình dùng EPROM và EEROM 53

2.3.3. Các ng d)ng ca FPGA 54

2.3.3.1. FPGA s d)ng cho các mch tích hp có ng d)ng
c bit 55

2.3.3.2. FPGA dùng cho thit k mch ngu nhiên 55

2.3.3.3. FPGA thay th các chíp SSI trong mch ngu nhiên 55

2.3.3.4. FPGA ng d)ng cho ch to mu 55

2.3.3.5. FPGA ng d)ng cho ch to máy tính 55

2.3.3.6. FPGA ng d)ng trong các thit b tái c$u hình 56

2.3.4. Thit k và lp trình cho FPGA 56

2.3.5. T$n công
i vi FPGA 57

2.3.5.1. T$n công kiu hp
en 57

2.3.5.2. T$n công kiu
c li 58

2.3.5.3. T$n công kiu nhái li 58

2.3.5.4. T$n công kiu thám ngc thit k chu%i bít 58

2.3.5.5. T$n công vt lý 59

2.3.5.6. T$n công side channel 59

2.3.6. Nhn xét chung v FPGA 59

2.4. Kt lu+n ch$%ng 61

Ch$%ng 3

GII PHÁP TRI2N KHAI THUT TOÁN AES TRÊN NN FPGA 62

3.1. Gi/i pháp t3ng quát v0 tri4n khai thu+t toán AES trên n0n FPGA 62

3.1.1. Mô t

lu
 t#ng quát ca b mã hóa và gi

i mã AES 62

3.1.2. Khi Data ca b mã hóa 63

3.1.3. Khi KeyExpansion 64

3.1.4. Khi CPU và khi Data ca b gi

i mã 65

3.1.5. Thit k chi tit các khi ch c n ng ca b mã hóa 67

3.1.6. Thit k các khi ch c n ng ca b gi

i mã 70

3.1.7. Thit k chi tit cho khi KeyExpansion 72

3.1.8. Khi CPU -
iu khin b gi

i mã 73

3.1.9. Khi giao tip vi máy tính 75

3.1.10. S d)ng ch
cài
t ECB cho gi

i pháp 75

3.2. Các yêu cu c*a gi/i pháp và ,ánh giá 78

3.2.1. Tc
và tài nguyên 78

3.2.2. C$u trúc phn c ng FPGA
 thc hin AES 79

3.4. Ch$%ng trình DEMO thu+t toán mã hoá AES 82

567689:8;<+=8ch$%ng 83

KT LUN 84

TÀI LIU THAM KHO 86

PH LC

DANH M.C CH/ VI0T T1T

AES Advanced Encryption Standard

ARK AddRoundKey

ASIC Application-Specific Integrated Circuit

ASSP Application-Specific Standard Product

CLB Configurable Logic Block

DES Data Encryption Standard

DSP Digital Signal Processor

EEPROM Electrically Eraseable Programmable Read Only Memory

EPROM Eraseable Programmable Read Only Memory

FPGA Field-Programmable Gate Array

GF(28

) Trng Galois

GPP General Purpose Processor

HDL Hardware Description Language

IMC InvMixColumns

ISB InvSubBytes

ISR InvShiftRows

MC MixColumns

MCU Microcontroller

MPGA Mask-Programmable Gate Array

NIST Institute of Standards and Technology

PAL Programmable Array Logic

PLA Programmable Logic Array

PLD Programmable Logic Device

PROM Programmable read-only Memory

RISC Reduced Instruction Set Computer

SB SubBytes

SR ShiftRows

VHDL Verilog Hardware Description Language

DANH MC BNG

B/ng 1.1. Các giai
on mã hoá ca DES 8

B/ng 1.2. S bit
c loi b" khi
i qua PC1 11

B/ng 1.3. S bit dch chuyn 11

B/ng 1.4. PC2 (hoán v nén) 11

B/ng 1.5. B

ng hoán v kh(i
u IP 12

B/ng 1.6. Hp E 14

B/ng 1.7. Các hp S 15

B/ng 1.8. Hoán v cui cùng IP-1 17

B/ng 1.9. B

ng th s-box ca AES 24

B/ng 1.10. Tóm t!t các bc to khoá, mã hoá và gi

mã h Enganmal 36

B/ng 2.1. So sánh x lý tín hiu thi gian thc 45

B/ng 2.2. Các
c tính ca công ngh lp trình 54

DANH MC HÌNH

Hình 1.1. Mô hình mã hóa 6

Hình 1.2. Minh ho h mã hóa khoá
i x ng 7

Hình 1.3. S
 t#ng quát mã hóa DES 9

Hình 1.4. S
 to khóa 10

Hình 1.5. Biu di2n dãy 64 bit x chia thành 2 thành phn L0,R0 12

Hình 1.6. S
 chi tit mt vòng 13

Hình 1.7. S
 hot
ng ca hàm f 13

Hình 1.8. Hoán v m( rng 14

Hình 1.9. Lu
 c$u trúc lp ca thut toán mã hóa AES 20

Hình 1.10. Mô t

State trong thut toán mã hóa AES
c biu di2n dng ma

trn 4x4

20

>[email protected]53
367389:3;<3=>

>36736?3;@A=3B:3?85?3?CDA367389:3EFG 21

Hình 1.12. Lu
 thc hin SB và ISB 22

Hình 1.13. Bin
#i SubBytes
i vi m

ng trng thái 23

Hình 1.14. Lu
 thc hin SR 25

Hình 1.15. Quá trình x lý MixColumns 25

Hình 1.16. Mô t

bc trong Key scheduling 27

Hình 1.17. Mã hoá vi khóa mã và gi

i mã khác nhau 29

Hình 1.18. S
 thut toán RSA 31

Hình 2.1. Mô hình FPGA 47

Hình 2.2. Bn loi FPGA trên thc t 49

Hình 2.3. Công ngh lp trình RAM t-nh 50

Hình 2.4. Công ngh lp trình cu chì nghch PLICE 51

Hình 2.5. Công ngh lp trình cu chì nghch ViaLink 52

Hình 2.6. Công ngh lp trình EPROM transistor 53

Hình 2.7. Minh ha kh

n ng c$u hình li ca FPGA 60

Hình 3.1. S
 khi t#ng quát h thng AES 62

Hình 3.2. S
 thut toán khi data ca b mã hóa 63