การออกแบบ DES และรหัสลับลูซิเฟอร์

ในปี 1971 Horst Feistel แห่ง IBM Research ได้พัฒนารหัสลับที่ชื่อ Lucifer ซึ่งเป็นส่วนหนึ่งของโครงการรักษาความปลอดภัยด้านการธนาคารสำหรับ Lloyd's of London Lucifer เป็นหนึ่งในรหัสลับบล็อกสมัยใหม่ยุคแรก ๆ โดยใช้คีย์ขนาด 128 บิตและบล็อกขนาด 128 บิต

Lucifer แสดงให้เห็นว่าสามารถสร้างรหัสลับบล็อกที่แข็งแกร่งได้ด้วยโครงสร้าง Feistel ซึ่งประกอบด้วยรอบของการแทนที่และการสับเปลี่ยนที่สลับกัน โดยใช้กับครึ่งบล็อก รหัสลับนี้เป็นต้นกำเนิดโดยตรงของ DES

DES ใช้โครงสร้าง Feistel 16 รอบกับบล็อกขนาด 64 บิต ในแต่ละรอบ บล็อกขนาด 64 บิตจะถูกแบ่งเป็นครึ่งละ 32 บิต ครึ่งขวาจะถูกขยายเป็น 48 บิต นำไปทำ XOR กับคีย์ย่อยขนาด 48 บิต ส่งผ่านกล่อง S แล้วสับเปลี่ยน ก่อนนำไปทำ XOR กับครึ่งซ้าย

จากนั้นครึ่งทั้งสองจะถูกสลับกันและทำกระบวนการซ้ำ หลังครบ 16 รอบ การสับเปลี่ยนขั้นสุดท้ายจะสร้างข้อความเข้ารหัสลับขนาด 64 บิต การถอดรหัสใช้โครงสร้างเดียวกัน โดยเรียงคีย์ย่อยย้อนกลับ

DES เข้ารหัสข้อมูลเป็นบล็อกขนาด 64 บิต (8 ไบต์) ขนาดบล็อกคงที่นี้เหมาะกับฮาร์ดแวร์ในปี 1977 แต่กลายเป็นข้อจำกัดด้านความปลอดภัยในเวลาต่อมา เมื่อมีข้อมูลมากพอ การชนกันตามปรากฏการณ์วันเกิดก็มีโอกาสเกิดขึ้นสูง

สำหรับบล็อกขนาด 64 บิต รูปแบบทางสถิติจะเริ่มปรากฏหลังจากประมาณ 2^32 บล็อก (ข้อมูลประมาณ 32GB ที่เข้ารหัสด้วยคีย์เดียวกัน) การโจมตีแบบ Sweet32 นี้ทำให้ 3DES ไม่ปลอดภัยสำหรับการรับส่งข้อมูลปริมาณมาก เช่น HTTPS

DES ใช้คีย์ขนาด 64 บิต แต่ 8 บิตเป็นบิตพาริตีที่ใช้ตรวจจับข้อผิดพลาด ไม่ได้ใช้สำหรับการเข้ารหัสลับ ดังนั้นความยาวคีย์ที่มีผลจริงจึงเหลือเพียง 56 บิต

นั่นหมายความว่ามีคีย์ DES ที่เป็นไปได้เพียง 2^56 ค่า (ประมาณ 72 พันล้านล้านค่า) ตามมาตรฐานในปี 1977 จำนวนนี้ถือว่าเพียงพอ แต่ในปี 1997 ก็พิสูจน์ได้ว่าสามารถถอดได้โดยผู้โจมตีที่มุ่งมั่น

DES เริ่มต้นด้วยการสับเปลี่ยนเริ่มต้น (IP) ซึ่งจัดเรียงบิตทั้ง 64 บิตของบล็อกข้อความธรรมดาใหม่ และจบด้วยการสับเปลี่ยนขั้นสุดท้าย (IP^-1) ซึ่งเป็นอินเวอร์สที่ตรงกันทุกประการ การสับเปลี่ยนเหล่านี้ไม่ได้เพิ่มความแข็งแกร่งทางการเข้ารหัสลับ

การสับเปลี่ยนเหล่านี้ออกแบบมาเพื่อประสิทธิภาพของฮาร์ดแวร์บนสถาปัตยกรรมชิปเฉพาะในยุคทศวรรษ 1970 ทำให้โหลดบิตลงในรีจิสเตอร์ได้เร็วขึ้น การวิเคราะห์สมัยใหม่ยืนยันว่าการสับเปลี่ยนเหล่านี้ไม่ได้ช่วยด้านความปลอดภัยแต่อย่างใด

กล่อง S ทั้งแปดกล่อง (กล่องแทนที่) เป็นหัวใจของความไม่เป็นเชิงเส้นใน DES กล่อง S แต่ละกล่องรับอินพุต 6 บิตและสร้างเอาต์พุต 4 บิตโดยใช้ตารางค้นหาคงที่ บิตด้านนอก 2 บิตใช้เลือกแถว และบิตด้านใน 4 บิตใช้เลือกคอลัมน์

หากไม่มีความไม่เป็นเชิงเส้นจากกล่อง S DES จะเป็นรหัสลับเชิงเส้นล้วน ๆ ที่ถอดได้โดยง่ายด้วยพีชคณิตเชิงเส้น การออกแบบกล่อง S ของ DES โดยเฉพาะช่วยต้านทานการวิเคราะห์การเข้ารหัสลับเชิงอนุพันธ์

หลังจากกล่อง S แล้ว DES จะใช้การสับเปลี่ยนด้วยกล่อง P เพื่อจัดเรียงบิตเอาต์พุตทั้ง 32 บิตจากกล่อง S ใหม่ การดำเนินการนี้ทำให้เกิดการแพร่กระจาย โดยกระจายเอาต์พุตของกล่อง S แต่ละกล่องไปให้ส่งผลต่อกล่อง S หลายกล่องในรอบถัดไป

กล่อง P ได้รับการออกแบบอย่างรอบคอบเพื่อเพิ่มการแพร่กระจายให้สูงสุด โดยบิตเอาต์พุตแต่ละบิตของกล่อง S หนึ่งกล่องจะส่งผลต่อกล่อง S ที่แตกต่างกันอย่างน้อยสองกล่องในรอบถัดไป ทำให้เกิดปรากฏการณ์หิมะถล่มได้อย่างรวดเร็ว

DES สร้างคีย์ย่อยขนาด 48 บิตที่แตกต่างกัน 16 ชุดจากคีย์หลักขนาด 56 บิต โดยมีหนึ่งชุดสำหรับแต่ละรอบ ตารางกำหนดคีย์เริ่มต้นด้วยการใช้การเลือกแบบสับเปลี่ยน (PC-1) เพื่อลบบิตพาริตีและจัดเรียงบิตของคีย์ใหม่

บิตทั้ง 56 บิตถูกแบ่งเป็นครึ่งละ 28 บิต แล้วหมุนไปทางซ้ายครั้งละ 1 หรือ 2 ตำแหน่งในแต่ละรอบ จากนั้นการเลือกแบบสับเปลี่ยน (PC-2) จะเลือก 48 บิตจากทั้งหมด 56 บิตเพื่อสร้างคีย์ย่อยของแต่ละรอบ

NSA ทำงานร่วมกับ IBM ในระหว่างการพัฒนา DES โดยลดความยาวคีย์จาก 128 บิตของรหัสลับลูซิเฟอร์เหลือ 56 บิต และปรับเปลี่ยนการออกแบบกล่อง S เรื่องนี้จุดชนวนข้อถกเถียงยาวนานหลายทศวรรษว่ามีการแอบใส่ประตูลับไว้หรือไม่

ในช่วงทศวรรษ 1990 เจ้าหน้าที่ของ NSA ยืนยันว่าได้เสริมความแข็งแกร่งให้กล่อง S เพื่อต้านทานการวิเคราะห์รหัสเชิงผลต่าง ซึ่งเป็นเทคนิคที่ IBM ค้นพบในปี 1974 NSA รู้จักการวิเคราะห์รหัสเชิงผลต่างมาหลายปีก่อนแวดวงวิชาการ จึงบ่งชี้ว่า NSA ทำให้ DES ทนทานต่อการโจมตีมากขึ้น ไม่ใช่อ่อนแอลง

DES ได้รับการประกาศใช้เป็นมาตรฐานการประมวลผลข้อมูลของรัฐบาลกลางหมายเลข 46 ในเดือนมกราคม 1977 หลังผ่านกระบวนการประเมินแบบแข่งขัน จึงกลายเป็นรหัสลับมาตรฐานสำหรับข้อมูลภาครัฐที่ไม่เป็นความลับ และได้รับการนำไปใช้อย่างแพร่หลายในภาคธนาคารและอุตสาหกรรม

การทำให้ DES เป็นมาตรฐานมีความสำคัญทางประวัติศาสตร์ เพราะเป็นอัลกอริทึมการเข้ารหัสลับที่เปิดให้สาธารณชนใช้งานและได้รับการรับรองจากรัฐบาลเป็นครั้งแรก ทั้งยังผลักดันการพัฒนาการใช้งานบนฮาร์ดแวร์ และวางแบบแผนสำหรับกระบวนการทำให้อัลกอริทึมเข้ารหัสลับในอนาคตเป็นมาตรฐาน

DES เองเป็นรหัสลับแบบบล็อกที่เข้ารหัสครั้งละ 64 บิตพอดี แต่ข้อความจริงมักยาวกว่านั้น รูปแบบการทำงานจึงกำหนดวิธีนำรหัสลับไปใช้กับหลายบล็อก รูปแบบที่ใช้กันทั่วไป ได้แก่ ECB (เข้ารหัสแต่ละบล็อกอย่างเป็นอิสระ), CBC (ใช้ XOR ระหว่างแต่ละบล็อกกับข้อความเข้ารหัสของบล็อกก่อนหน้าแล้วจึงเข้ารหัส), CFB, OFB และ CTR

ECB เป็นรูปแบบที่อ่อนแอที่สุด เพราะบล็อกข้อความธรรมดาที่เหมือนกันจะสร้างบล็อกข้อความเข้ารหัสที่เหมือนกัน ทำให้มองเห็นรูปแบบได้ รูปแบบ CBC และ CTR ขจัดจุดอ่อนนี้ และเป็นรูปแบบที่ต้องการสำหรับการใช้งาน DES และ DES สามชั้นจริง

โปรดทดสอบความรู้เกี่ยวกับค่ากำหนดการออกแบบ DES

DES พัฒนาจากรหัสลับลูซิเฟอร์ของ IBM จนเป็นรหัสลับแบบไฟสเทล 16 รอบที่ใช้บล็อกขนาด 64 บิตและคีย์ที่มีประสิทธิผลขนาด 56 บิต ความปลอดภัยของ DES มาจากกล่อง S แบบไม่เชิงเส้น 8 กล่องที่สร้างความสับสน กล่อง P ที่สร้างการแพร่กระจาย และการทำงาน 16 รอบที่ขยายผลแบบหิมะถล่ม

การมีส่วนร่วมของ NSA ในการออกแบบกล่อง S เป็นประเด็นถกเถียง แต่ท้ายที่สุดก็ช่วยเพิ่มความต้านทานต่อการวิเคราะห์รหัสเชิงผลต่าง คีย์ขนาด 56 บิตของ DES ซึ่งออกแบบให้เหมาะกับฮาร์ดแวร์ในปี 1977 พิสูจน์แล้วว่าไม่เพียงพอเมื่อเข้าสู่ช่วงปลายทศวรรษ 1990