อัลกอริทึมการเข้ารหัสอธิบายด้วยตัวอย่าง

การเข้ารหัสโดยพื้นฐานที่สุดคือศาสตร์แห่งการใช้รหัสและการเข้ารหัสเพื่อปกป้องข้อความ

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

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

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

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

Diffie-Hellman แก้ไขปัญหานี้โดยอนุญาตให้คนแปลกหน้าแลกเปลี่ยนข้อมูลผ่านช่องทางสาธารณะซึ่งสามารถใช้เพื่อสร้างคีย์ที่ใช้ร่วมกันได้ คีย์ที่แชร์ยากที่จะถอดรหัสแม้ว่าจะมีการตรวจสอบการสื่อสารทั้งหมด

Diffie-Hellman ทำงานอย่างไร?

Diffie-Hellman คือสิ่งที่เรียกว่าโปรโตคอลการแลกเปลี่ยนคีย์ นี่คือการใช้งานหลักสำหรับ Diffie-Hellman แม้ว่าจะสามารถใช้ในการเข้ารหัสได้เช่นกัน (โดยทั่วไปจะไม่ใช่เพราะการใช้ DH ในการแลกเปลี่ยนคีย์มีประสิทธิภาพมากกว่าจากนั้นเปลี่ยนไปใช้การเข้ารหัสแบบสมมาตร (เร็วกว่ามาก) สำหรับการส่งข้อมูล ).

วิธีการทำงานมีดังนี้:

โดยทั่วไปมีสองฝ่ายคืออลิซและบ็อบซึ่งเห็นด้วยกับสีเริ่มต้น (โดยพลการ แต่ต้องแตกต่างกันทุกครั้ง) พวกเขายังมีสีลับที่พวกเขาเก็บไว้กับตัวเอง จากนั้นพวกเขาผสมสีนี้กับสีที่ใช้ร่วมกันทำให้ได้สองสีที่แตกต่างกัน จากนั้นพวกเขาก็ส่งสีนี้ไปให้อีกฝ่ายซึ่งผสมกับสีลับของพวกเขาทำให้ได้สีลับในตอนจบเหมือนกัน

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

ตัวอย่างเช่น:

  1. บ็อบและอลิซเห็นด้วยกับสองจำนวนไพรม์ขนาดใหญ่ p = 29 และฐาน g = 5
  2. ตอนนี้ Bob เลือกหมายเลขลับ x (x = 4) และทำสิ่งต่อไปนี้: X = g ^ x% p (ในกรณีนี้% ระบุส่วนที่เหลือตัวอย่างเช่น 3% 2 คือ 3/2 โดยที่ส่วนที่เหลือคือ 1) . X = 5 ^ 4% 29 = 625% 29 = 16
  3. อลิซยังเลือกหมายเลขลับ y (y = 8) และทำสิ่งต่อไปนี้: Y = g ^ y% p Y = 5 ^ 8% 29 = 390,625% 29 = 24
  4. Bob ส่ง X ให้ Alice และ Alice ส่ง Y ให้ Bob
  5. จากนั้น Bob จะทำสิ่งต่อไปนี้: K = Y ^ x% p, K = 24 ^ 4% 29 = 331,776% 29 = 16
  6. จากนั้นอลิซทำสิ่งต่อไปนี้: K = X ^ y% p, K = 16 ^ 8% 29 = 4,294,967,296% 29 = 16

สิ่งที่ยิ่งใหญ่ (* อาจจะเป็นเวทมนตร์ *) เกี่ยวกับเรื่องนี้ก็คือทั้งบ็อบและอลิซมีหมายเลขเดียวกันคือ K และตอนนี้สามารถใช้สิ่งนี้เพื่อพูดคุยอย่างลับๆได้เพราะไม่มีใครรู้จักเค

ความปลอดภัยของโปรโตคอลนี้มีการระบุไว้ในบางสิ่ง:

  1. (ความจริง) มันค่อนข้างง่ายที่จะสร้างจำนวนเฉพาะแม้กระทั่งจำนวนเฉพาะจำนวนมาก (เช่น p)
  2. (Fact) การยกกำลังแบบโมดูลาร์ทำได้ง่าย กล่าวอีกนัยหนึ่งก็คือการคำนวณ X = g ^ x% p นั้นค่อนข้างง่าย
  3. (สมมติฐานตามกำลังการคำนวณและคณิตศาสตร์ในปัจจุบัน) การแยกรากแบบแยกส่วนโดยไม่มีปัจจัยเฉพาะนั้นยาก โดยพื้นฐานแล้วมันยากมากที่จะหา K โดยไม่รู้ x และ y แม้ว่าคุณจะสอดแนมการจราจรและสามารถดู p, g, X และ Y ได้

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

แม้ว่าผู้โจมตีสามารถประนีประนอมกับคีย์นี้ได้ แต่ Diffie-Hellman ก็ช่วยให้สามารถส่งต่อความลับได้สมบูรณ์

ความลับไปข้างหน้าที่สมบูรณ์แบบคืออะไร?

นี่เป็นแนวคิดที่ว่าหากคุณถอดรหัสการเข้ารหัสที่เซิร์ฟเวอร์ใช้สื่อสารอยู่ตอนนี้ไม่ได้หมายความว่าการสื่อสารทั้งหมดที่เซิร์ฟเวอร์เคยดำเนินการจะสามารถอ่านได้

กล่าวอีกนัยหนึ่งก็คืออนุญาตให้คุณเห็นการสื่อสารที่ใช้อยู่ในขณะนี้เท่านั้น เนื่องจากชุดการสื่อสารแต่ละชุดมีรหัสลับที่แตกต่างกันคุณจึงต้องแตกทั้งหมดแยกกัน

ซึ่งเป็นไปได้หากแต่ละเซสชันมีคีย์ชั่วคราวที่แตกต่างกันสำหรับแต่ละเซสชัน เนื่องจาก Diffie-Hellman ใช้ค่าสุ่มใหม่สำหรับแต่ละเซสชันเสมอ (ดังนั้นการสร้างคีย์ใหม่สำหรับแต่ละเซสชัน) จึงเรียกว่า Ephemeral Diffie Hellman (EDH หรือ DHE) ชุดการเข้ารหัสจำนวนมากใช้สิ่งนี้เพื่อให้ได้ความลับไปข้างหน้า

เนื่องจาก Diffie-Hellman ช่วยให้คุณสามารถแลกเปลี่ยนเนื้อหาหลักในรูปแบบข้อความธรรมดาได้โดยไม่ต้องกังวลเกี่ยวกับการล่วงล้ำความลับที่แชร์และคณิตศาสตร์นั้นซับซ้อนเกินไปสำหรับผู้โจมตีที่จะใช้กำลังดุร้ายผู้โจมตีจึงไม่สามารถรับรหัสเซสชันได้ (และแม้ว่าจะทำได้โดยใช้ คีย์ที่แตกต่างกันชั่วคราวสำหรับแต่ละเซสชันหมายความว่าพวกเขาสามารถสอดแนมเซสชันนี้ได้เท่านั้นไม่ใช่ในอดีตหรืออนาคต)

การส่งต่อความลับเปิดใช้งานกับการแลกเปลี่ยนคีย์ Diffie-Hellman ใด ๆ แต่มีเพียงการแลกเปลี่ยนคีย์ชั่วคราว (คีย์ที่แตกต่างกันสำหรับทุกเซสชัน) เท่านั้นที่ให้ความลับไปข้างหน้าได้อย่างสมบูรณ์แบบ

นี่คือโพสต์จาก Scott Helme ที่พูดถึงเรื่องนี้ในเชิงลึกมากขึ้นและอธิบายวิธีเปิดใช้งานสิ่งนี้บนเซิร์ฟเวอร์ของคุณ

ข้อ จำกัด ของ Diffie-Hellman คืออะไร?

ข้อ จำกัด ที่ใหญ่ที่สุดของ DH คือไม่มีการยืนยันตัวตน กล่าวอีกนัยหนึ่งคือทุกคนสามารถอ้างว่าเป็นอลิซหรือบ็อบได้และไม่มีกลไกในตัวในการยืนยันว่าคำพูดของพวกเขาเป็นความจริง

นอกจากนี้หากการนำไปใช้งานไม่ได้ดำเนินการอย่างปลอดภัยอัลกอริทึมอาจถูกถอดรหัสโดยมีทรัพยากรเฉพาะเพียงพอ (ไม่น่าจะเป็นไปได้ แต่เป็นไปได้สำหรับทีมวิชาการหรือนักแสดงของรัฐ)

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

นอกจากนี้ยังมีการโจมตีที่แสดงให้เห็นในปี 2015 ซึ่งแสดงให้เห็นว่าเมื่อเซิร์ฟเวอร์จำนวนมากใช้หมายเลขเฉพาะเดียวกันเป็นจุดเริ่มต้นของการแลกเปลี่ยนคีย์ความปลอดภัยโดยรวมของ Diffie-Hellman นั้นต่ำกว่าที่คาดไว้

โดยพื้นฐานแล้วผู้โจมตีสามารถคำนวณการโจมตีล่วงหน้าได้โดยเฉพาะทำให้ง่ายต่อการประนีประนอมเซสชันสำหรับเซิร์ฟเวอร์ใด ๆ ที่ใช้หมายเลขเฉพาะนั้น

สิ่งนี้เกิดขึ้นเนื่องจากเซิร์ฟเวอร์หลายล้านเครื่องใช้หมายเลขเฉพาะเดียวกันสำหรับการแลกเปลี่ยนคีย์ การคำนวณล่วงหน้าของการโจมตีประเภทนี้ยังคงต้องใช้ทรัพยากรในระดับวิชาการหรือระดับประเทศและไม่น่าจะส่งผลกระทบต่อคนส่วนใหญ่

อย่างไรก็ตามโชคดีสำหรับผู้ที่ต้องกังวลเกี่ยวกับผู้โจมตีของรัฐมีวิธีอื่นในการแลกเปลี่ยนคีย์ DH โดยใช้การเข้ารหัสเส้นโค้งรูปไข่ (ECDHE) นี่อยู่นอกขอบเขตของบทความนี้ แต่หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับคณิตศาสตร์ที่อยู่เบื้องหลังการแลกเปลี่ยนนี้โปรดอ่านบทความนี้

สำหรับรายละเอียดเพิ่มเติมเกี่ยวกับจุดอ่อนของ DH โปรดดูเอกสารไวท์เปเปอร์นี้และเว็บไซต์นี้

RSA

RSA ได้รับการตั้งชื่อตามผู้สร้าง - Rivest, Shamir, Adleman - และเป็นวิธีการสร้างคีย์สาธารณะและส่วนตัว

ในทางเทคนิคมีอัลกอริทึม RSA สองแบบ (อันหนึ่งใช้สำหรับลายเซ็นดิจิทัลและอีกอันหนึ่งใช้สำหรับการเข้ารหัสแบบไม่สมมาตร) - บทความนี้ครอบคลุมอัลกอริทึมการเข้ารหัสแบบอสมมาตร

สิ่งนี้ช่วยให้สามารถแลกเปลี่ยนคีย์ - คุณกำหนดแต่ละฝ่ายให้กับธุรกรรมคีย์สาธารณะ / ส่วนตัวก่อนจากนั้นคุณจะสร้างคีย์สมมาตรและสุดท้ายคุณใช้คู่คีย์สาธารณะ / ส่วนตัวเพื่อสื่อสารคีย์สมมาตรที่แชร์อย่างปลอดภัย

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

แล้วมันทำงานอย่างไร?

  1. เลือกจำนวนเฉพาะที่มีขนาดใหญ่มาก 2 ตัว (อย่างน้อย 512 บิตหรือ 155 หลักทศนิยมแต่ละหลัก) x และ y (ตัวเลขเหล่านี้ต้องเป็นความลับและเลือกแบบสุ่ม)
  2. ค้นหาผลิตภัณฑ์เช่น z = x * y
  3. เลือกจำนวนเต็มสาธารณะคี่ e ระหว่าง 3 ถึง n - 1 และไม่มีปัจจัยร่วม (นอกเหนือจาก 1) ด้วย (x-1) (y-1) (ดังนั้นจึงค่อนข้างเป็นไพรม์ถึง x - 1 และ y - 1 ).
  4. ค้นหาตัวคูณร่วมน้อยที่สุดของ x - 1 และ y - 1 และเรียกมันว่า L
  5. คำนวณเลขชี้กำลังส่วนตัว d จาก x, y และ e de = 1% L. d คือค่าผกผันของ e% L (คุณรู้ว่ามีผกผันอยู่เพราะ e ค่อนข้างเป็นไพรม์ถึง z - 1 และ y - 1) ระบบนี้ทำงานได้เนื่องจาก p = (p ^ e) ^ d% z
  6. เอาต์พุต (z, e) เป็นคีย์สาธารณะและ (z, d) เป็นคีย์ส่วนตัว

ตอนนี้ถ้า Bob ต้องการส่งข้อความถึง Alice เขาจะสร้าง ciphertext (C) จากข้อความธรรมดา (P) โดยใช้สูตรนี้:

C = P ^ e% z

ในการถอดรหัสข้อความนี้ Alice คำนวณสิ่งต่อไปนี้:

P = C ^ d% z

ความสัมพันธ์ระหว่าง d และ e ทำให้มั่นใจได้ว่าฟังก์ชันการเข้ารหัสและการถอดรหัสจะผกผัน นั่นหมายความว่าฟังก์ชันถอดรหัสสามารถกู้คืนข้อความต้นฉบับได้สำเร็จและค่อนข้างยากที่จะกู้คืนข้อความต้นฉบับโดยไม่ใช้คีย์ส่วนตัว (z, d) (หรือปัจจัยหลัก x และ y)

นอกจากนี้ยังหมายความว่าคุณสามารถทำให้ z และ e เป็นสาธารณะได้โดยไม่กระทบต่อความปลอดภัยของระบบทำให้ง่ายต่อการสื่อสารกับผู้อื่นที่คุณยังไม่มีรหัสลับที่ใช้ร่วมกัน

คุณยังสามารถใช้การดำเนินการย้อนกลับเพื่อรับลายเซ็นดิจิทัลของข้อความ ขั้นแรกให้คุณใช้การดำเนินการถอดรหัสบนข้อความธรรมดา ตัวอย่างเช่น s = SIGNATURE (p) = p ^ d% z

จากนั้นผู้รับสามารถตรวจสอบลายเซ็นดิจิทัลโดยใช้ฟังก์ชันการเข้ารหัสและเปรียบเทียบผลลัพธ์กับข้อความ ตัวอย่างเช่น m = VERIFY (s) = S ^ e% z

บ่อยครั้งเมื่อเสร็จสิ้นข้อความธรรมดาจะเป็นแฮชของข้อความซึ่งหมายความว่าคุณสามารถลงนามในข้อความ (โดยไม่คำนึงถึงความยาว) ด้วยการยกกำลังเพียงครั้งเดียว

ความปลอดภัยของระบบขึ้นอยู่กับบางสิ่ง:

  1. (ความจริง) มันค่อนข้างง่ายในการสร้างจำนวนเฉพาะแม้แต่จำนวนเฉพาะจำนวนมาก (เช่น x และ y)
  2. (Fact) การคูณเป็นเรื่องง่าย หา z ได้ง่ายมาก
  3. (สมมติฐานตามคณิตศาสตร์ปัจจุบัน) การแยกตัวประกอบเป็นเรื่องยาก เมื่อพิจารณาจาก z มันค่อนข้างยากที่จะกู้คืน x และ y สามารถทำได้ แต่ต้องใช้เวลาสักพักและมีราคาแพง

    การประมาณหนึ่งกล่าวว่าการกู้คืนปัจจัยสำคัญของตัวเลข 1024 บิตจะใช้เวลาหนึ่งปีสำหรับเครื่องที่มีราคา 10 ล้านเหรียญ การเพิ่มขนาดเป็นสองเท่าจะเพิ่มจำนวนงานที่ต้องการเป็นทวีคูณ (งานเพิ่มขึ้นหลายพันล้านเท่า)

    เนื่องจากเทคโนโลยีก้าวหน้าอย่างต่อเนื่องค่าใช้จ่ายเหล่านี้ (และงานที่ต้องใช้) จะลดลง แต่ ณ จุดนี้การเข้ารหัสประเภทนี้ซึ่งนำไปใช้อย่างถูกต้องเป็นแหล่งที่มาของการประนีประนอม

    โดยทั่วไปแฮกเกอร์เพียงคนเดียวที่มีเงินประเภทนี้และอุทิศให้กับเป้าหมายเดียวคือรัฐชาติ นอกจากนี้หากมีวิธีที่ง่ายกว่าในการประนีประนอมระบบ (ดูด้านล่าง) นั่นอาจเป็นตัวเลือกที่ดีกว่า

4. (Fact) การยกกำลังแบบโมดูลาร์ทำได้ง่าย กล่าวอีกนัยหนึ่งก็คือการคำนวณ c = p ^ e% z นั้นค่อนข้างง่าย

5. (Fact) การแยกรูทแบบโมดูลาร์ - ย้อนกลับกระบวนการข้างต้น - เป็นเรื่องง่ายถ้าคุณมีปัจจัยเฉพาะ (ถ้าคุณมี z, c, e และปัจจัยเฉพาะ x และ y จะหา p ได้ง่ายเช่นนั้น c = p ^ e% z)

6. (สมมติฐานขึ้นอยู่กับพลังการคำนวณและคณิตศาสตร์ในปัจจุบัน) การแยกรูทแบบโมดูลาร์โดยไม่มีปัจจัยเฉพาะนั้นยากมาก (ถ้าคุณมี z, c, e แต่ไม่ใช่ x และ y มันค่อนข้างยากที่จะหา p เช่นนั้น c = p ^ e% z โดยเฉพาะอย่างยิ่งถ้า a มีขนาดใหญ่เพียงพอ)

ต้องการเรียนรู้เพิ่มเติมเกี่ยวกับคณิตศาสตร์จากคนที่ฉลาดกว่านี้หรือไม่? ลองอ่านบทความนี้

เยี่ยมไหนดีกว่ากัน?

ขึ้นอยู่กับกรณีการใช้งานของคุณ มีความแตกต่างเล็กน้อยระหว่างสองอัลกอริทึม - ประการแรกความลับไปข้างหน้าที่สมบูรณ์แบบ (PFS) ซึ่งเราได้พูดถึงก่อนหน้านี้ในบริบทของ Diffie-Hellman แม้ว่าในทางเทคนิคคุณสามารถสร้างคู่คีย์ RSA ชั่วคราวและให้ความลับไปข้างหน้าอย่างสมบูรณ์แบบด้วย RSA แต่ค่าใช้จ่ายในการคำนวณนั้นสูงกว่า Diffie-Hellman มากซึ่งหมายความว่า Diffie-Hellman เป็นตัวเลือกที่ดีกว่าสำหรับการใช้งาน SSL / TLS ที่คุณต้องการความลับไปข้างหน้าอย่างสมบูรณ์แบบ .  

แม้ว่าจะมีความแตกต่างด้านประสิทธิภาพบางประการระหว่างอัลกอริทึมทั้งสอง (ในแง่ของการทำงานที่ต้องใช้จากเซิร์ฟเวอร์) ความแตกต่างของประสิทธิภาพโดยทั่วไปไม่มากพอที่จะสร้างความแตกต่างเมื่อเลือกอย่างใดอย่างหนึ่ง

โดยทั่วไปแล้วการพิจารณาหลักในการพิจารณาว่าข้อใดดีกว่านั้นขึ้นอยู่กับว่าข้อใดได้รับการสนับสนุนมากกว่าสำหรับกรณีการใช้งานของคุณ (ตัวอย่างเช่นเมื่อใช้ SSL คุณจะต้องการ Diffie Hellman เนื่องจากความลับไปข้างหน้าอย่างสมบูรณ์แบบ) หรือเป็นที่นิยมหรือเป็นที่ยอมรับมากกว่า เป็นมาตรฐานในอุตสาหกรรม

ตัวอย่างเช่นในขณะที่ Diffie-Hellman ได้รับการอนุมัติจากรัฐบาลสหรัฐฯและได้รับการสนับสนุนจากหน่วยงานของสถาบัน แต่ก็ไม่ได้มีการเผยแพร่มาตรฐานดังกล่าวในขณะที่ RSA (มาตรฐานโดยองค์กรเอกชน) ให้มาตรฐานฟรีซึ่งหมายความว่า RSA ได้รับความนิยมอย่างมากในหมู่องค์กรเอกชน

หากคุณสนใจที่จะอ่านเพิ่มเติมมีหัวข้อดีๆเกี่ยวกับความแตกต่างที่นี่

สนใจเรียนรู้วิธีการที่แฮกเกอร์ใช้การโจมตีด้วยการเข้ารหัสหรือไม่? ลองใช้ชุดความท้าทายนี้จาก Cryptopals

ยิ่งฉันเรียนรู้เกี่ยวกับการเข้ารหัสมากเท่าไหร่ฉันก็ยิ่งคิดว่าอลิซกับบ็อบน่าจะคุยกันด้วยตัวเองมากขึ้นเท่านั้น

- Paul Reinheimer (@preinheimer) วันที่ 13 มีนาคม 2017