Lecture 2: Cryptographic Tools

Cryptography terminology คำศัพท์

• Plaintext, Cleartext
  • ข้อความ / ข้อมูลตัวเลข / … ที่ไม่ถูกเข้ารหัส
• Ciphertext: ข้อมูลที่เข้ารหัสแล้ว
• Key: ข้อมูลลับที่ใช้ในการแบ่งปันข้อมูล ระหว่างผู้ส่งกับผู้รับ
• Encryption (encipherment): เข้ารหัส Plaintext $\rArr$ Ciphertext
• Decryption (decipherment): ถอดรหัส Ciphertext $\rArr$ Plaintext
• Crptology: ศึกษาเกี่ยวกับการเข้ารหัสและถอดรหัส
  • Crptography: หาทางเข้ารหัส
  • Cryptanalysis: หาทางถอดรหัส (Code Breaking)
• Cryptologist: บุคคลที่พยายามแปลง Ciphertext กลับเป็น Plaintext
  • Cryptographer: เป็นคนดีฮะ 👌
  • Cryptanalyst: โจร 🦧

Cryptography Schema โครงสร้างของการเข้ารหัส

จะประกอบไปด้วย Plaintext, Encryption algorithm, Secret key, Ciphertext, Decryption algorithm ซึ่งจะสามารถแบ่งออกเป็นสามมิติได้

1. วิธีการเปลี่ยน Plaintext เป็น Ciphertext

   1. Substitution การเปลี่ยนตัวอักษรนึง ไปอีกตัวอักษรนึง ช่วยให้สับสน (Confusion)
   2. Transposition การสลับตำแหน่ง ช่วยให้เกิดการกระจาย (Diffusion)

2. จำนวน Key ที่ใช้

   • 1 Key
   • 2 Keys
   • ไม่มี Key

3. วิธีการที่ Plaintext ถูกเข้ารหัส

   1. Block Cipher การเข้ารหัสที่จะแบ่งเป็นก้อนๆ

      • Standard Electronic Codebook Mode (ECB) แบ่งข้อมูลออกเป็นก้อนๆ และเข้ารหัส แยกกัน

      • Cipher Block Chaining (CBC) นำผลลัพท์จากการเข้ารหัส ECB ไปเข้ารหัสร่วมกับก้อนต่อไป ทำอย่างนี้ไปเรื่อยๆ

        Cipher Block Chaining (CBC)

   2. Stream Cipher การเข้ารหัสแบบต่อเนื่อง

The Caesar Cipher และ Shift Cipher

• เป็นการเลื่อนตำแหน่งของตัวอักษรภาษาอังกฤษ ไป 3 ตัว
• Shift Cipher ที่ $k = 3$

Plaintext	A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Ciphertext	d e f h k i j k l m n o p q r s t u v w x y z a b c

Monoalphabetic Cipher

เป็นการสลับตัวอักษรแบบสุ่ม ไปอีกตัวนึง

Plaintext	a b c d e f g h i j k l m n o p q r s t u v w x y z
Ciphertext	D K V Q F I B J W P E S C X H T M Y A U O L R G Z N

Plaintext
Ciphertext	WI RF RWAJ UH YFTSDVF SFUUFYA

Culumnar Transpositions

สร้างตารางมาขนาด $5 \times ...$ แล้วแต่ข้อมูลในแนวนอน แต่อ่านในแนวตั้ง

Transpositions (Permutations/การสับเปลี่ยน)

• Digrams: เปลี่ยนสองตัวอักษรที่ติดกัน
  • เช่น -re, -th, -en, -ed, -on, -in, -an, …
• Trigrams: เปลี่ยนสามตัวอักษรที่ติดกัน
  • เช่น -ent, -ion, -ing, -ive, -for, -one, …

Product Ciphers

เป็นการผสม Substitution และ Transposition เพื่อให้เข้ารหัสให้ยากขึ้น เป็นการเข้าสู่ยุคของ Modern ciphers

Type of Attacks

• Ciphertext only attack
  • ผู้ร้ายรู้แค่ Ciphertext
  • ป้องกันง่ายที่สุด เพราะผู้ร้ายมีข้อมูลน้อยมาก
• Known plaintext attack
  • ผู้ร้ายรู้ทั้ง Plaintext และ Ciphertext
• Chosent plaintext attack
  • พยายามจะหา Ciphertext จาก Plaintext ที่ต้องการ
• Brute force attack
  • ลองทุกวิธีทุกหนทาง
  • ความเร็วจะขึ้นอยู่กับขนาดของ Key

Types of Cryptographic Functions

• Secret key (symmetric): ใช้ 1 key
• Public key (asymmetric): ใช้ 2 key (private & public key)
• Hash: ไม่ใช้ Key (0 key)

Symmetric Encryption (Secret key)

• ผู้ส่งและผู้รับ จะมี Key ร่วมกัน 1 key

Symmetric algorithms

	DES	Triple DES	AES
ขนาด Plaintext (bits)	64	64	128
ขนาด Ciphertext (bits)	64	64	128
ขนาด Key (bits)	56	112 หรือ 168	128, 192, หรือ 256

• Data Encryption Standard (DES)

  • ใช้เทคนิค Block cipher
  • นำข้อมูลขนาด 64 bits และทำการ Substitution และ Permutation ทั้งหมด 16 ครั้ง
  • DES ไม่เหมาะกับการใช้ใน อุสหกรรมหลัก ~1M USD หรือ อาวุธนิวเคียรของจีน แต่ยังพอรับได้กับ ระบบธนาคาร หรือ E-Biz payment เพราะค่าใช้จ่ายในการแกะรหัสก็ยังสูงอยู่

• Triple DES

  Triple DES

  ทำสามรอบแล้วดีสามเท่า??? แต่จริงๆ สามารถถูกโจมตีง่ายๆ ด้วยเทคนิค Meet-in-the-middle attack

  • Meet-in-the-middle attack

    $$T = E_{k1}[P] = D_{k2}[C]$$

    ถ้าเพียงรู้ $T$ ก็จะสามารถนำไปเปรียบเทียบในตาราง $K_1 \rightleftarrows T$ กับตาราง $T \rightleftarrows K_2$ ก็จะได้ keys $K_1$ และ $K_2$ ออกมา ซึ่งถ้าใช้ Meet-in-the-middle attack กับ 2DES จากการ Brute force $2^{112}$ keys ก็จะเหลือแค่ $2 * 2^{56} = 2^{57}$

• Advanced Encryption Standard (AES)

  AES เป็น algorithm แบบ private key ซึ่งจะใช้ secret key ร่วมกัน ซึ่งขนาดของ key สามารถใช้ได้ดังนี้

  • 128 bits ($= 3.4 \times 10^{38}$ keys) (10 รอบ)
  • 192 bits ($= 6.2 \times 10^{57}$ keys) (12 รอบ)
  • 256 bits ($= 1.1 \times 10^{77}$ keys) (14 รอบ)

  ถ้าเทียบกับ DES, DES ใช้เพียง 56-bit key หรือเท่ากับ $7.2 \times 10^{16}$ keys

Asymmetric Encryption (Public key)

Public key algorithms

• RSA (Rivest, Shamir, Adleman)

  1. เลือกจำนวนเฉพาะ (Prime number) มาสองตัวที่มีค่าเยอะมากๆ $p$ กับ $q$
  2. ให้ $n = p * q$
  3. ให้ $m = (p - 1)(q - 1)$ และ $...$

Public key authentication

เข้ารหัสด้วย Private key และถอดรหัสด้วย Public key จะสามารถบอกได้ว่า ส่งมาจากผู้ส่งที่ถูกต้องจริง แต่ว่าจะถูกเปิดอ่านระหว่างส่งได้!

Publick key encryption

เข้ารหัสด้วย Public key และถอดรหัสด้วย Private key จะสามารถป้องกันไม่ให้มีคนอ่านระหว่างส่งได้ โดยคนรับที่มี Private key จะสามารถอ่านได้คนเดียว แต่จะมั่นใจได้ไงว่าส่งมาจากผู้ส่งที่ถูกต้อง?

Secure authentication messages

จะทั้งปลอดภัยและยืนยันตัวผู้ส่งได้ (secret & authenticated) โดยจะ

Man-in-the-middles (MITM)

เป็นการโจมตีที่จะดักฟัง และแก้ไข keys ที่รับส่งกัน

Message authentication codes

จะสามารถตรวจสอบความ Original ของข้อความได้

Key management

• Key generation

• Key storing

• Key distribution

  • ต้องการ Trusted intermediary หรือ คนที่ไว้วางใจได้

    • Key distribution center (KDC) จะทำหน้าที่แจกจาย Symmetric key หรือ Secret key ซึ่งสำหรับ N hosts จะ ต้องใช้ $\dfrac{N(N - 1)}{2}$ keys แต่การทำแบบนี้จะมีปัญหาเรื่อง Scalibility ซึ่งจะสามารถแบ่งการทำงานออกเป็นย่อยๆ ได้ Global KDC $\rArr$ Local KDC

    Digital Envelopes

    Digital envelopes

    • Certification authority (CA) จะทำหน้าที่ตรวจสอบว่า Public key นั้นๆ เป็นของเจ้าของจริงหรือไม่? การตรวจสอบจะประกอบไปด้วย Public key และ User ID ที่เป็นจำของ

Digital Signature

จะสามารถยืนยันได้ว่าข้อความไม่ได้ถูกแก้ และ ส่งมาจากผู้ที่ถูกต้องจริงๆ

---