�ݺ�ߣ

IT346 Information System Security
Week 3-1: Symmetric-Key Cryptography
อ.พงษ์ศกดิ์ ไผ่แดง
ั

Faculty of Information Technology

Page

1

Cryptography
 Cryptography หมายถึงวิทยาการรหัสลับ มาจากคาว่า crypto ที่แปลว่า

ซ่อน และคาว่า graph ที่แปลว่าการเขี ยนCryptography จึงมีความหมาย
ว่า “การเขี ยนเพื่อซ่อนข้อมูล”
 Cryptography ใช้ในการปองกันข้อมูลและสารสนเทศ โดยประกอบด้วย
้
3 เทคโนโลยีหลัก
‣ Symmetric Key Cryptography หรือ Secret Key Cryptographyคือการเข้ารหัส

ข้อมูลแบบ “สมมาตร”
‣ Asymmetric Key Cryptography หรือ Public Key Cryptographyคือการ
เข้ารหัสข้อมูลแบบ “อสมมาตร”
‣ Hash Function คือการสร้างตัวแทนข้อมูล


Page

Cryptography
 Cryptanalysis หมายถึ งการพยายามวิเคราะห์เพื่อศึ กษาประเด็ นต่างๆที่

เกี่ยวข้องกับ Cryptography
 Sensitive Data หมายถึ งข้อมูลสาคัญที่ถือว่าเป็ นความลับไม่สามารถ

แพร่งพรายออกสู่ภายนอกได้


Page

Symmetric-Key Cryptography
 Plaintext –ข้อมูลต้นฉบับ
 Encryption algorithm –ดาเนิ นการแทนที่ (substitutions) หรือ แปลงข้อมูล





(transformations) บน plaintext
Secret Key –ควบคุมการ substitutions/transformationsที่เกิดขึ้นใน
กระบวนการ encryption
Ciphertext – ข้อมูลที่ถกแปลงด้วย substitutions/transformationsแล้ว
ู
Decryption – กระบวนการย้อนกลับของ encryption
ความแข็งแกร่งของ encryption อยู่ที่การรักษาความลับของ keyที่ใช้

Plaintext

Key
Encryption
E(P,K)  C


Key

Ciphertext

Plaintext

Decryption
D(C,K)  P
Page

อัลกอริทึมมาตรฐานสาหรับการเข้ารหัส
 อัลกอริทึม DES (Data Encryption Standard)
‣ Key size 56 bits
 อัลกอริทึม 3-DES (Triple-DES)
 อัลกอริทึม IDEA (International Data Encryption Algorithm)
 อัลกอริทึม AES (Advanced Encryption Standard)
‣ Key size 128, 192, 256 bits


Page

5

DES Algorithm
 DES ย่อมาจาก Data Encryption Standard เป็ นการเข้ารหัส แบบบล็ อค

(Block cipher) ที่พฒนามาจากอัลกอริทึม Lucifer ของ IBM โดย
ั
Lucifer ได้รบการพัฒนาเพิ่มความสามารถและเปลี่ยนชื่อเป็ น DES แล้ว
ั
ได้รบการนาเสนอต่อ US NIST (US National Institute of Standards
ั
and Technology) ให้กลายเป็ นมาตรฐานการเข้ารหัส
 DES เป็ นอัลกอริทึมแบบบล็ อก (Block Cipher) ใช้ Key ขนาดความยาว

56 bits ดาเนิ นการบนบล็ อคข้อมูล (Data Block) ขนาด 64 bits


Page

6

DES Overview
64-bit Plaintext
…

64-bit Key

Initial Permutation

PC1

64 bit

Round 0
64 bit

Round 1

…

K1

48 bit

K2

48 bit

56 bit
PC2
PC2

Left Circular Shift
56 bit

64 bit

Round 15

56-bit Key

56-bit Key
Left Circular Shift
56-bit Key

K16

48 bit

PC2

56 bit

Left Circular Shift

64 bit

32-bit Swap
64 bit
Inverse Initial Permutation

…
64-bit Ciphertext

Page

7

DES Overview
 ขันตอนการทางานของ DES Algorithm บน Data Block โดยสังเขป
้
1) Data Block ขนาด 64 bits จะถูกสลับตาแหน่ ง (สลับบิต)เรียกขันตอนนี้ ว่า
้
Initial Permutation (IP)
2) Data Block ถูกดาเนิ นการอีก 16 รอบ แต่ละรอบมีการแทนที่บิต
(substitution) และการสลับบิต (permutation) โดยใช้ key ขนาด 48 bits
3) Data Block ถูกสลับครึ่งแรกของบล็อคกับครึ่งหลังของบล็ อค
4) Data Block ถูกสลับบิตแบบกลับทิศทางกับขันตอนแรก เรียกว่า Inverse
้
Initial Permutation
 ขันตอนการทางานของ DES Algorithm บน Key Block โดยสังเขป
้
a) Key Block ขนาด 64 bits จะถูกสลับบิตเรียกขันตอนนี้ ว่า Permutation
้
Choice 1 (PC1) โดยเลือก 56 bits ออกมาจาก 64 bits แล้วแบ่งครึ่งเป็ น
ครึ่งละ 28 bits
b) Key Block ถูกดาเนิ นการอีก 16 รอบ แต่ละรอบมีการวนบิตไปทางซ้ายแบบ
เป็ นวงกลม (Left Circular Shift) และการสลับบิต (permutation) เพื่อสร้าง
key ขนาด 48 bits สาหรับการดาเนิ นการบน Data Block ขัน 2)
้

Page

8

รอบการทางานบน Data Block
 การดาเนิ นงานบน Data Block แต่ละรอบใน 16 รอบ เป็ นดังนี้
64-bit
Round 0

L0 (32 bits)

R0 (32 bits)

f

K1

XOR

Round 1

L1=R0

R1=(L0 XOR f(R0,K1))

f

K2

XOR

L2=R3


R2=(L1 XOR f(R1,K2))

Page

9

แต่ละรอบของการทางาน (Round 0 – 15)
 ข้อมูลในส่วนทางขวา (Ri) 32 bits และคียย่อย K ของรอบนันๆ จะถูก
์
้
นามาดาเนิ นการผ่านฟั งก์ชน f ได้ผลลัพธ์เป็ น f(Ri,Ki-1)
ั่
 ผลลัพธ์ท่ีได้จากทังส่วนทางซ้าย (Li) และขวา f(Ri,Ki-1) จะถูกนามา
้
รวมกันแบบ XOR
 ผลลัพธ์ที่ได้จากการ XOR จะถูกใช้เป็ นข้อมูลส่วนทางขวาของรอบใหม่
(Ri+1) และข้อมูลของส่วนทางขวาเดิม (Ri) ก็จะกลายเป็ นข้อมูลส่วนซ้าย
ของวงรอบใหม่ (Li+1)


Page

10

ฟั งก์ชน f ทาหน้าที่ดงนี้
ั่
ั
 ฟั งก์ชน f ทาการขยายข้อมูลในส่วนทางขวา (Ri) 32 bitsให้กลายเป็ น
ั่
ข้อมูลขนาด 48 bits พร้อมทังเลื่ อนบิตของ Key ซึ่งมีเพียง 48 bits (จาก
้
เดิม 56 bits) จากนันจึงนาข้อมูลมารวมกับ key ด้วยการ XOR
้
 ผลลัพธ์ขนาด 48 bits ที่ได้จากการรวม จะถูกนาไปทาการแทนที่
(substitution) อีก 8 ครัง ผลลัพธ์จากการแทนที่จะเหลื อข้อมูลเพียง 32
้
bits เท่านัน
้
 ผลลัพธ์จากการแทนที่จะถูกสลับตาแหน่ ง (Permutation) อีกครัง
้
 หนึ่ งรอบของการทาฟั งก์ชน f จะประกอบด้วยขบวนการข้างต้นทังหมด 4
ั่
้
ครัง
้


Page

11

 โครงสร้างของฟั งก์ชน f ในรอบการทางาน
ั่
การทางานของฟั งก์ชน f ประกอบด้วย S-box ทังหมด
ั่
้
8 กล่อง แต่ละกล่องทาหน้าที่ map ข้อมูล 6 bits ไป
เป็ น 4 bits เช่น S(18 09 12 3d 11 17 38 39) =
5fd25e03


Page

12

ภาพรวม
รอบการทางานบน
Data Block


Page

13

รอบการทางานบน Key Block
 อี กด้านหนึ่ งของการทางานใน DES คือการสร้าง subkeys เพื่อใช้ในแต่ละ

รอบ ซึ่งประกอบด้วยขันตอน ต่อไปนี้
้
‣ การสลับบิตของ key ในขันต้น เรียกว่าเป็ น initial permutation
้

(Permutation Choice 1, PC1) ซึ่งทาการเลือก 56bits โดยแบ่งครึ่งเป็ น 2
ส่วน ครึ่งละ 28bit
‣ รอบ 16 รอบประกอบด้วย:
• หมุนส่วน 28 bit แต่ละส่วนโดยเลื่ อนบิตไป 1 หรื อ 2 ตาแหน่ ง ขึ้ นกับ key

rotation schedule
• เลื อก 24 bits จากแต่ละครึ่ ง แล้วสลับบิตด้วย PC2 จากนันจึ งนาไปใช้
้
ดาเนิ นการกับ data block ในรอบนันๆ
้


Page

14

DES Decryption
 โดยปกติแล้วการถอดรหัส (decryption) สาหรับ Block Cipher จะเป็ น

การย้อนการทางานของการเข้ารหัส (encryption)
 แต่ DES ถูกออกแบบมาอย่างดี ทาให้อลกอริทึมการถอดรหัส
ั
(decryption) เป็ นอัลกอริทึมเดียวกับการเข้ารหัส (encryption) มีลาดับ
การทางานเหมือนกัน เพียงแต่ใช้ subkeys (K1 … K16) ในลาดับกลับกัน
เท่านัน
้
 ดังนันในการ decryption เราสามารถใช้ Hardware ชุดเดียวกันกับการ
้
Encryption ได้โดยปอน subkeys ตามลาดับ K16 … K1
้
‣ สะดวกต่อการใช้งาน และประหยัดค่าใช้จ่าย


Page

15

DES Decryption
 DES decryption สามารถหักล้าง DES Encryption ได้ดงนี้
ั
‣ ขันตอน Initial Permutation ซึ่งเป็ นขันตอนแรกของการ decryption ลบล้าง
้
้
ขันตอน Inverse Initial Permutation ซึ่งเป็ นขันตอนสุดท้ายของการ
้
้
encryption
‣ Round 0 โดยใช้ K16 เป็ นการลบล้าง Round 15 ของ encryption
‣ ….
‣ Round 15 โดยใช้ K1 เป็ นการลบล้าง Round 0 ของ encryption
‣ ขันตอน Inverse Initial Permutation ซึ่งเป็ นขันตอนสุดท้ายของการ
้
้
decryption ลบล้างขันตอน Initial Permutation ซึ่งเป็ นขันตอนแรกของการ
้
้
encryption
‣ สุดท้าย จะได้ plaintext ขนาด 64 bits กลับคืนมา


Page

16

Avalanche Effect
 Avalanche Effect เป็ นคุณสมบัติท่ีเป็ นที่ตองการ สาหรับ encryption
้

algorithm
 เมื่อเปลี่ ยน input หรือ key ไปเพียง 1 bit ก็จะเปลี่ ยน bits ของ output
ไปประมาณครึ่งหนึ่ ง
 DES ให้ Avalanche Effect ที่ดี


Page

17

Strength of DES – Key Size
 Key ขนาด 56-bit ให้ค่าที่เป็ นไปได้ทงหมด 256 = 7.2 x 1016 ค่า
ั้
 การโจมตีแบบ brute force search เป็ นไปได้ยาก
 อย่างไรก็ตาม มีการค้นพบว่า การทา brute force search บน key ของ

DES Algorithm เป็ นไปได้
‣ ปี 1997 บริษท Distribution.net ใช้ระบบบน Internet สามารถทาได้ภายใน
ั

เวลา 41 วัน
‣ ปี 1998 บริษท EFF สร้าง hardware เฉพาะสาหรับแก้ปัญหานี้ ทาได้ภายใน
ั
่
เวลา 56 ชัวโมง
‣ ปี 1999 Distribution.net และบริษท EFF ก็จบมือกันและใช้คอมพิวเตอร์กว่า
ั
ั
่
่
100,000 เครื่องทัวโลกสามารถแคร็ก DES ได้ใน 22 ชัวโมง 15 นาที
 จึงต้องหาทางเลื อกในการ encryption ที่แข็ งแกร่งกว่า DES

Page

18

ทางเลือกที่แข็ งแกร่งกว่า DES
 การขยาย Key ของ DES จาก 64 bits ให้เป็ น 128 bits เพื่อจะได้ใช้เวลา

ในการ crack นานขึ้น
‣ ปั จจุบน DES แบ่งออกเป็ น DES 64 Bit และ DES 128 Bit
ั

 แต่ถึงแม้ว่าจะใช้ 128 bit ก็ตาม DES ก็ยงสามารถถูก crack ได้ จึงได้มี
ั

การพัฒนาให้มี Triple-DES (3DES) ที่มีความแข็ งแกร่งมากขึ้ น


Page

19

Triple-DES (3DES) with Two-Keys
 Triple-DES เป็ นการเข้ารหัสที่ถกสร้างมาเพื่อแก้ปัญหาความอ่อนแอของ
ู

DES โดย Triple-DES จะช่วยเสริมความปลอดภัยให้การเข้ารหัสมี
ปลอดภัยมากขึ้น
 ใช้อลกอริทึม DES เป็ นจานวน 3 ครังเพื่อทาการเข้ารหัส
ั
้
 ใช้ key เพียง 2 คียในการทา Encryption ด้วยลาดับ Encrypt-Decrypt์
Encrypt
C = EK1(DK2(EK1(P)))
‣ หาก K1 = K2 จะกลายเป็ น DES ธรรมดา

 ความแข็ งแกร่งนี้ จึงทาให้ Triple-DES เป็ นอี กหนึ่ งในมาตรฐานในการ

เข้ารหัสในปั จจุบน
ั

Page

20

Triple-DES (3DES) with Two-Keys
 กระบวนการ Encryption แบบ 3DES อาจใช้ Key เพียง 2 คีย ์
64-bit Plaintext

DES Encryption

Key 1

DES Decryption

Key 2

DES Encryption

Key 1

64-bit Ciphertext

Page

21

AES (Advance Encryption Standard)
 AES (Advance Encryption Standard) เป็ นการเข้ารหัสที่พฒนาขึ้ นมาเพื่อ
ั







ใช้ทดแทน DES หลังจากที่ DES ถูก break ได้ โครงการพัฒนา AES ได้
เริ่มต้นเมื่อปี 1997 โดย NIST
่
ในปี 1998 NIST ก็ให้นกวิทยาการหัสลับทัวโลกส่งอัลกอริทึมเข้ามาเพื่อ
ั
คัดเลือกโดยกาหนดให้ใช้ data block ขนาด 128 bit เป็ นมาตรฐาน
อัลกอริทึมต่างถูกคัดเลือกเข้ามาทังสิ้ น 15 อัลกอริทึม และมีอยู่ 5
้
อัลกอริทึมที่ผ่านเข้ารอบชิง
อัลกอริทึมของ Rijndael ชนะการคัดเลื อก เนื่ องจากเป็ นอัลกอริทึมที่เร็ว
กว่าและซับซ้อนน้อยกว่า แต่ได้ความปลอดภัยเท่ากัน
Rijndael Algorithm กลายเป็ น RFC 3826 และเมื่อปี 2004 ข้อกาหนดใน
มาตรฐานล่าสุดอนุญาตให้ใช้ AES เข้ารหัสข้อมูลโดยใช้ Key ทีมขนาดต่าง
่ ี
ๆ ได้ ซึ่งได้แก่ 128 Bit, 192 Bit และ 256 Bit


Page

22

การทางานของ AES
 AES เป็ นการดาเนิ นการบน Bytes จึงทาให้ง่ายในการพัฒนาระบบ และมี

ความรวดเร็วในการเข้าและถอดรหัส
 Data Block ขนาด 128 bits = 16 bytes
‣ มอง Data Block 16 bytes เป็ นตารางขนาด 4 x 4
‣ สถานะปั จจุบนของ bytes ในตาราง เรียกว่าเป็ น Current State
ั
‣ Current State (สถานะของตาราง bytes) จะถูกดาเนิ นการทังหมด 10 รอบ
้

ทาให้ค่าให้ตารางเปลี่ยนไป เมื่อสิ้นสุดการทางานตาราง Current State จะเก็บ
ciphertext ที่ได้จากการ encryption
in0 in4 in8 in12

s0,0 s0,1 s0,2 s0,3

s0,0 s0,1 s0,2 s0,3

out0 out4 out8 out12

in1 in5 in9 in13

s10 s1,1 s1,2 s1,3

s10 s1,1 s1,2 s1,3


in2 in6 in10 in14

s2,0 s2,1 s2,2 s2,3

s2,0 s2,1 s2,2 s2,3


in3 in7 in11 in15

s3,0 s3,1 s3,2 s3,3

s3,0 s3,1 s3,2 s3,3


input

State Array

output
Page

23

 Key Block ขนาด 128 bits = 16 bytes
‣ มอง Key Block 16 bytes เป็ นตาราง
ขนาด 4 x 4
‣ Key จะถูกขยาย (Key Expansion)
ให้เป็ นอาร์เรย์ของ word ขนาด 44 words
(1 word = 32 bits = 4 bytes)

k0

k4

k8 k12

k1

k5

k9 k13

k2

k6 k10 k14

k3

k7 k11 k15

w0 w1 w2 w3

แต่ละรอบของ
Key Expansion

f

+ + + +
w4 w5 w6 w7

Key Expansion
k0

k4

k8 k12

k1

k5

k9 k13

k2

k6 k10 k14

k3

k7 k11 k15


w0 w1

…

w43

Page

24

วงรอบการทางานของ AES แบ่งเป็ น 3 ส่วนหลักได้แก่
 รอบเริ่มต้น (Initial Round)
‣ ประกอบด้วยขันตอน AddRoundKey
้

 รอบระหว่างกลาง (Rounds) รวม 9 รอบ
‣ ประกอบด้วยขันตอน SubBytes, ShiftRows, MixColumns และ AddRoundKey
้
 รอบสุดท้าย (Final Rounds)
‣ ประกอบด้วยขันตอน SubBytes, ShiftRows และ AddRoundKey (ไม่มี
้
MixColumns)
 ทุกรอบมีการใช้ round key (sub-key จาก key expansion) ขนาด 4

words รวม 11 รอบ ใช้ทงหมด 11 sub-keys รวม 44 words
ั้

Page

25

AES

รอบเริ่มต้น
(Initial Round)

รอบระหว่างกลาง (Rounds)

รอบสุดท้าย (Final Round)
ไม่มี Mix Columns


Page

26

 กระบวนการ AddRoundKey
‣ เป็ นการเอาข้อมูลมา XOR กับ key
‣ ขันตอนนี้ มีอยู่ในทุก round ของการทางาน
้
ข้อมูล

Key ขนาด 4 words
= 16 bytes

w

Page

27

 กระบวนการ SubBytes
‣ เป็ น non-linear substitution ซึ่งแต่ละไบต์จะถูกแทนที่ดวยไบต์ท่ีได้จาก
้
lookup table
‣ ขันตอนนี้ มีอยู่ในรอบระหว่างกลาง และรอบสุดท้ายของการทางาน
้
ข้อมูล


Page

28

 กระบวนการ ShiftRows
‣ เป็ นการเลื่อนไบต์ในแต่ละแถว ซึ่งจะทาเฉพาะแถวที่ 2, 3 และ 4
‣ ขันตอนนี้ มีอยู่ในรอบระหว่างกลาง และรอบสุดท้ายของการทางาน
้
ข้อมูล


Page

29

 กระบวนการ MixColumns
‣ เป็ นการผสมรวม 4 ไบต์ภายในคอลัมน์ ผ่านการคูณเมตริกต์
‣ ขันตอนนี้ มีอยู่ในรอบระหว่างกลางของการทางาน เท่านัน
้
้

ข้อมูล


Page

30

�ݺ�ߣ

Information system security wk1-1

More Related Content

Information system security wk1-1