ทรีพาสโปรโตคอลเมจิก

ในระหว่างการวิจัยล่าสุดของฉัน ฉันพบโปรโตคอลการเข้ารหัสที่ดีชื่อ: “ โปรโตคอลสามผ่าน ” ซึ่งเดิมพัฒนาโดย Adi Shamir

ในโพสต์นี้ ฉันจะสาธิตรูปแบบพื้นฐานของโปรโตคอลนี้ (มีการพัฒนาและวิวัฒนาการเพิ่มเติมสำหรับโปรโตคอลนี้ โปรดตรวจสอบลิงก์ Wikipedia ด้านบน)

สำหรับการนำอัลกอริทึมไปใช้ ฉันใช้ Python กับ Google Colaboratory ที่นี่

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

ลองนึกภาพสถานการณ์ต่อไปนี้:
อลิซและบ็อบเป็นนักเรียนที่นั่งอยู่ในห้องเรียนเดียวกัน นี่คือห้องเรียนของนักศึกษาต่างคณะ(ซึ่งหลายคนไม่รู้จักกัน)
อลิซต้องการส่งข้อความลับถึงบ็อบซึ่งนั่งอยู่อีกด้านหนึ่งของชั้นเรียน
อลิซเขียนข้อความลับของเธอลงในโน้ต ใส่โน้ตลงในกล่องเล็กๆ และล็อกกล่องด้วยแม่กุญแจ
เธอเขียนว่า “ถึงบ๊อบ” บนกล่องและขอให้นักเรียนคนอื่นๆ ส่งกล่องให้บ๊อบ
เมื่อบ็อบได้รับกล่อง เขาคล้องแม่กุญแจที่กล่อง เขียนว่า “ถึงอลิซ” และขอให้นักเรียนส่งกล่องคืนให้อลิซ
จากนั้นอลิซก็รับกล่อง ถอดแม่กุญแจออก เขียนบนกล่องว่า “ถึงบ๊อบ” และให้นักเรียนส่งกล่องอีกครั้ง
ณ จุดนี้ เมื่อ Bob ได้รับกล่อง เขาก็ถอดแม่กุญแจออก เปิดกล่อง และอ่านข้อความลับ

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

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

เย็น!

ka : คีย์เข้ารหัสของ Alice
dka : คีย์ถอดรหัสของ Alice
kb : คีย์เข้ารหัสของ Bob
m : ข้อความ
E : การเข้ารหัส
D : ถอดรหัส

D(dka, E(kb, E(ka, m))) = E(kb, m)

สิ่งนี้เป็นไปได้ด้วยการเข้ารหัสแบบสับเปลี่ยน ซึ่งเป็นการเข้ารหัสที่ไม่ขึ้นกับลำดับ

E(ka, E(kb, m)) = E(kb, E(ka, m))

แล้ว:

D(dka, E(kb, E(ka, m))) = D(dka, E(ka, E(kb, m))) = E(kb, m)

โปรโตคอล Three-Pass ใช้ผกผันการคูณแบบโมดูลาร์เพื่อลบคีย์

ให้ทำตามขั้นตอนของอัลกอริทึม:

รหัสลับที่ใช้ร่วมกัน: ks
กุญแจของอลิซ: ka , ka⁻¹
กุญแจของ Bob: kb , kb⁻¹

1. กำหนดความยาวบิตของตัวเลข (เช่น 128 บิต)
2. ทุกคนเห็นด้วยกับจำนวนเฉพาะpเป็นกุญแจสาธารณะ
3. ผู้ใช้แต่ละคนเลือกหมายเลขสุ่มkซึ่งเป็น coprime ถึงp-1

4. ผู้ใช้แต่ละคนคำนวณk⁻¹ , อินเวอร์สการคูณแบบโมดูลาร์ของk ของพวกเขา

k⁻¹k ≅ 1(mod p-1)

กุญแจของอลิซ: ka, ka⁻¹
กุญแจของ Bob: kb kb⁻¹

5. อลิซเลือกรหัสลับที่ใช้ร่วมกันksเพื่อแบ่งปันกับบ๊อบ

6. อลิซเข้ารหัสข้อความโดยใช้ความลับที่ใช้ร่วมกัน:

7. อลิซส่งสิ่งต่อไปนี้ให้บ็อบ:

8. Bob ส่งสิ่งต่อไปนี้ให้ Alice:

9. อลิซส่งสิ่งต่อไปนี้ ให้บ็อบ:

10. Bob คำนวณสิ่งต่อไปนี้:

11. ตรวจสอบว่ารหัสลับที่ใช้ร่วมกันของ Bob และ Alice เหมือนกัน:

ยืนยัน ks' == ks

12. Bob ถอดรหัสข้อความที่เข้ารหัสของ Alice โดยใช้รหัสลับที่ใช้ร่วมกันที่เขาคำนวณ:

m'= D(ks', ค)

13. ตรวจสอบว่าข้อความต้นฉบับและข้อความที่ได้รับตรงกัน:

ยืนยัน m' == ม

การดำเนินการโค้ดของอัลกอริทึมในสมุดบันทึก colabจะสร้างผลลัพธ์ต่อไปนี้ (คุณจะได้รับตัวเลขที่สร้างขึ้นแตกต่างกัน):