การเข้ารหัสแบบอสมมาตร

ในบทเรียนนี้เราจะมาดูการเข้ารหัสแบบอสมมาตร ซึ่งเป็นรากฐานของการสื่อสารเครือข่ายที่ปลอดภัยในปัจจุบัน

เมื่อจบบทเรียน เราจะได้ครอบคลุมหัวข้อต่อไปนี้:

• การเข้ารหัสแบบอสมมาตรคืออะไร
• การใช้งานการเข้ารหัสแบบอสมมาตร รวมถึงการแลกเปลี่ยนคีย์และลายเซ็นดิจิทัล
• ความปลอดภัยของการเข้ารหัสแบบอสมมาตรโดยทั่วไป
• รายละเอียดเพิ่มเติมเกี่ยวกับอัลกอริทึม RSA, DSA และ Elliptic Curves รวมถึงความปลอดภัย
• ตัวอย่างโค้ด Python ที่แสดงให้เห็นว่าอัลกอริทึมทำงานอย่างไรในทางปฏิบัติ
• ภัยคุกคามต่ออัลกอริทึมเหล่านี้จากทั้งคอมพิวเตอร์คลาสสิกและควอนตัม

บทนำสู่การเข้ารหัสแบบอสมมาตร

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

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

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

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

รูปที่ 1. การเข้ารหัสแบบอสมมาตร

AKC มีฟังก์ชันที่มีประโยชน์หลายอย่าง เช่น:

1. การเข้ารหัสและถอดรหัส เพื่อสร้าง ความลับ ในการสื่อสาร
2. ลายเซ็นดิจิทัล เพื่อรับรอง ความถูกต้อง, ความสมบูรณ์ และ non-repudiation
3. การแลกเปลี่ยนคีย์ที่ปลอดภัย เพื่ออำนวยความสะดวกในการใช้งาน cryptosystems แบบสมมาตรต่อไป

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

การแลกเปลี่ยนคีย์ด้วยการเข้ารหัสแบบอสมมาตร

หนึ่งในปัญหาพื้นฐานของคริปโตกราฟีคือการ แลกเปลี่ยนคีย์ อย่างปลอดภัย ตัวอย่างเช่น หากสองฝ่ายต้องการใช้การเข้ารหัสแบบสมมาตร ทั้งสองฝ่ายต้องมีคีย์เดียวกันในการเข้ารหัสและถอดรหัสข้อความ แต่พวกเขาจะแลกเปลี่ยนคีย์อย่างปลอดภัยได้อย่างไร การเข้ารหัสแบบอสมมาตรแก้ปัญหานี้ผ่านกลไกการแลกเปลี่ยนคีย์แบบ interactive และ non-interactive

การแลกเปลี่ยนคีย์แบบ interactive

โปรโตคอลการแลกเปลี่ยนคีย์ แบบ interactive หมายถึงวิธีที่สองฝ่ายร่วมกันสร้าง shared secret คีย์ผ่านช่องทางการสื่อสารที่ไม่ปลอดภัย คีย์ shared secret นี้จะนำไปใช้สำหรับงานเข้ารหัสและถอดรหัสแบบสมมาตรต่อไป

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

ระบบ cryptosystems สมัยใหม่ที่อิงจาก elliptic curve cryptography (ECC) ขยายแนวคิดนี้ด้วย elliptic curve Diffie-Hellman (ECDH) ซึ่งทำงานคล้ายกับ DH แต่ใช้คุณสมบัติของ elliptic curves ทำให้ได้ระบบที่ปลอดภัยและมีประสิทธิภาพยิ่งขึ้น

รูปที่ 2. โปรโตคอลการแลกเปลี่ยนคีย์

การแลกเปลี่ยนคีย์แบบ non-interactive

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

ข้อพิจารณาสำคัญในการแลกเปลี่ยนคีย์แบบ non-interactive เกี่ยวข้องกับความแตกต่างของความยาวบิตระหว่างคีย์สมมาตรที่ต้องการแลกเปลี่ยนกับขนาดข้อความที่แนะนำใน AKC โดยทั่วไปคีย์สมมาตรสมัยใหม่มีความยาว 128-256 บิต ในขณะที่ระบบ cryptosystems แบบอสมมาตรเช่น RSA ทำงานกับขนาดข้อความประมาณ 1024-4096 บิต ดังนั้นเมื่อใช้ AKC ส่งคีย์สมมาตร เพื่อความปลอดภัยจะต้องเข้ารหัสลงในข้อความที่ยาว 1024-4096 บิต ซึ่งทำได้สองวิธี:

• การแลกเปลี่ยนคีย์แบบ Padding: วิธีนี้สร้างคีย์สมมาตรสั้น (128-256 บิต) ก่อน จากนั้นใช้ padding scheme แบบกลับได้ที่ตกลงกันไว้ เช่น OAEP เพื่อฝังลงในข้อความที่ยาวขึ้น (1024-4096 บิต) ข้อความที่ยาวขึ้นนี้จะถูกเข้ารหัสด้วย AKC และประกาศออกไปในรูปแบบ ciphertext ผู้รับจะถอดรหัส ciphertext ก่อน แล้วจึงลบ padding ออกเพื่อดึงคีย์สมมาตรสั้นออกมา

• กลไก encapsulation คีย์ (KEMs): ด้วยการแลกเปลี่ยนคีย์แบบ KEM ข้อความ plain text แบบสุ่มและยาว (1024-4096 บิต) จะถูกสร้างขึ้นก่อน จากนั้นดึงคีย์สมมาตรสั้น (128-256 บิต) ออกมาโดยใช้ key derivation function (KDF) ที่ตกลงกันไว้ plain text ที่ยาวกว่าจะถูกเข้ารหัสด้วย AKC และส่งไปยังผู้รับในรูปแบบ ciphertext ผู้รับถอดรหัส ciphertext ด้วยคีย์ส่วนตัวของตน แล้วใช้ KDF ดึงคีย์สมมาตรสั้น (128-256 บิต) ออกมา ระบบ cryptosystems ยอดนิยมอย่าง RSA ซึ่งสามารถเข้ารหัสข้อมูลโดยตรงได้ สามารถนำมาใช้ implement KEMs ได้

รูปที่ 3. กลไก Key Encapsulation

ลายเซ็นดิจิทัลด้วยการเข้ารหัสแบบอสมมาตร

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

รูปที่ 4. ลายเซ็นดิจิทัลด้วยการเข้ารหัสแบบอสมมาตร

อัลกอริทึมลายเซ็นดิจิทัลเฉพาะทาง

ปัจจุบัน มาตรฐาน US Federal Information Processing Standard (FIPS) สำหรับลายเซ็นดิจิทัลคือรูปแบบเฉพาะที่ชื่อว่า Digital Signature Algorithm (DSA) ซึ่งมีลักษณะคล้ายกับโปรโตคอล Diffie-Hellman บ้าง โดย DSA ใช้คุณสมบัติพีชคณิตของ modular exponential และ multiplicative inverses สำหรับการสร้างและตรวจสอบลายเซ็น

elliptic curve digital signature algorithm (ECDSA) คือรูปแบบ ECC ของ DSA ที่ให้ฟังก์ชันเดียวกันแต่ใช้คีย์ที่สั้นกว่าอย่างมีนัยสำคัญ ส่งผลให้มีประสิทธิภาพที่ดีขึ้น ทำให้เป็นที่นิยมสำหรับระบบที่มี ข้อจำกัดด้านทรัพยากร

ทั้ง DSA และ ECDSA จะถูกอธิบายในรายละเอียดเพิ่มเติมในภายหลัง

รูปแบบลายเซ็นดิจิทัลที่ใช้ cryptosystems ทั่วไป

นอกจากอัลกอริทึมเฉพาะทาง ลายเซ็นดิจิทัลยังสามารถสร้างได้โดยใช้ cryptosystems แบบอสมมาตรทั่วไป เช่น RSA

RSA ซึ่งจะถูกกล่าวถึงในรายละเอียดในส่วนถัดไป ก็ใช้ modular multiplicative inverses และ modular exponentiation เป็นการดำเนินการพื้นฐานเช่นกัน แต่รวมกันในลำดับที่แตกต่างจาก DSA ใน RSA ผู้ลงนามมักจะสร้าง hash ของข้อความแล้วเข้ารหัส hash ด้วยคีย์ส่วนตัว ทำให้เกิดเป็นลายเซ็นดิจิทัล ทุกฝ่ายจึงสามารถตรวจสอบลายเซ็นนี้ได้โดยการถอดรหัสด้วยคีย์สาธารณะของผู้ลงนามและเปรียบเทียบกับข้อความที่ผ่าน hash แล้ว

การประยุกต์ใช้การเข้ารหัสแบบอสมมาตร

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

1. การสื่อสารทางอินเทอร์เน็ต: การสื่อสารที่ปลอดภัยผ่านอินเทอร์เน็ต เช่น HTTPS พึ่งพาการเข้ารหัสแบบอสมมาตรอย่างมาก Transport Layer Security (TLS) และรุ่นก่อนหน้า Secure Sockets Layer (SSL) ใช้การเข้ารหัสแบบอสมมาตรในกระบวนการ handshake เริ่มต้นเพื่อสร้างคีย์สมมาตร ซึ่งจากนั้นจะถูกใช้ตลอดการสื่อสาร

2. การรับรองตัวตน: การเข้ารหัสแบบอสมมาตรใช้สร้างลายเซ็นดิจิทัล ซึ่งช่วยให้หน่วยงานสามารถรับรองเอกสารดิจิทัลหรือข้อความว่ามาจากผู้ส่งรายนั้น ใช้ในสถานการณ์ต่างๆ ตั้งแต่การยืนยันการอัปเดตซอฟต์แวร์ไปจนถึงสัญญาดิจิทัลที่มีผลทางกฎหมาย

3. การเข้ารหัสอีเมล: โปรโตคอลการเข้ารหัสอีเมลอย่าง PGP (Pretty Good Privacy) และทางเลือกโอเพนซอร์ส GPG (GNU Privacy Guard) ใช้การเข้ารหัสแบบอสมมาตรเพื่อให้แน่ใจว่าเฉพาะผู้รับที่ต้องการเท่านั้นที่อ่านเนื้อหาอีเมลได้

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

5. VPN (virtual private network): การเข้ารหัสแบบอสมมาตรใช้สร้างการเชื่อมต่อที่ปลอดภัยใน VPN เพื่อให้การสื่อสารผ่านเครือข่ายสาธารณะมีความปลอดภัย

6. Blockchain และสกุลเงินดิจิทัล: เทคโนโลยี Blockchain รวมถึง Bitcoin และ Ethereum ใช้การเข้ารหัสแบบอสมมาตร ตัวอย่างเช่น ความเป็นเจ้าของ Bitcoin ถูกพิสูจน์ผ่านลายเซ็นดิจิทัลที่ใช้การเข้ารหัสแบบอสมมาตร

7. Certificate authorities: การเข้ารหัสแบบอสมมาตรถูกใช้โดย certificate authorities (CAs) ในการออกและลงนามใบรับรองดิจิทัล ซึ่งนำไปใช้ใน TLS, code signing, การเข้ารหัสอีเมล และอื่นๆ ใบรับรองดิจิทัลผูกคีย์สาธารณะกับหน่วยงานเฉพาะ (เช่น บุคคลหรือเซิร์ฟเวอร์)

รูปที่ 5. การออกและลงนามใบรับรองดิจิทัลโดยใช้การเข้ารหัสแบบอสมมาตร

ความปลอดภัยของการเข้ารหัสแบบอสมมาตร

แนวคิดคริปโตกราฟีหลายอย่างมารวมกันเพื่อให้การเข้ารหัสแบบอสมมาตรปลอดภัย ได้แก่:

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

ฟังก์ชัน Trapdoor ใน AKC การเข้ารหัสและถอดรหัสใช้คีย์เสริมที่แตกต่างกันจากคีย์คู่เดียวกัน Ciphertext ที่สร้างโดยการเข้ารหัสด้วยคีย์ใดคีย์หนึ่ง (เช่น คีย์สาธารณะ) ต้องอ่านไม่ออกสำหรับบุคคลที่สาม ในขณะที่ผู้ถือคีย์เสริม (ในกรณีนี้คือคีย์ส่วนตัว) สามารถถอดรหัสได้ง่าย กล่าวคือ การเข้ารหัสควรมีลักษณะเหมือน trapdoor one-way function เพื่อให้บุคคลที่สามไม่สามารถกลับการดำเนินการและกู้คืน plain text ได้ แต่คีย์ส่วนตัวให้ trapdoor ลับที่ช่วยให้กลับได้ง่าย อัลกอริทึม AKC ยอดนิยมใช้ modular exponentiation เพื่อสร้างพฤติกรรม trapdoor one-way function

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

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

โปรโตคอล	ขนาดคีย์ทั่วไป (บิต)	การประยุกต์ใช้
RSA	1024 (เลิกใช้), 2048, 3072, 4096	การเข้ารหัส, ลายเซ็นดิจิทัล
DSA	1024 (เลิกใช้), 2048, 3072	ลายเซ็นดิจิทัล
DH	2048, 3072, 4096	การแลกเปลี่ยนคีย์
ECDH	224, 256, 384, 521	การแลกเปลี่ยนคีย์
ECDSA	224, 256, 384, 521	ลายเซ็นดิจิทัล

โครงสร้างพื้นฐานคีย์สาธารณะ: ใน AKC คีย์ส่วนตัวต้องถูกเก็บเป็นความลับโดยเจ้าของ ในขณะที่คีย์สาธารณะถูกแชร์ จำเป็นต้องมีกลไกที่ปลอดภัยในการจัดการและกระจายคีย์สาธารณะเหล่านี้ระหว่างผู้ใช้ Public key infrastructure (PKI) ให้วิธีทำสิ่งนี้โดยใช้ ใบรับรองดิจิทัล ใบรับรองดิจิทัลให้หลักฐานยืนยันตัวตนของเจ้าของคีย์สาธารณะและออกโดยหน่วยงานที่เชื่อถือได้เช่น certificate authority (ซึ่งเป็นส่วนหนึ่งของ PKI) PKI จึงเป็นส่วนสำคัญของความปลอดภัยของแอปพลิเคชันสมัยใหม่ที่ใช้ AKC โดยช่วยให้การจัดการคีย์ในขนาดใหญ่เป็นไปได้ (โดยการสร้าง จัดการ กระจาย และเพิกถอนใบรับรองดิจิทัล)

ความเสี่ยงด้านความปลอดภัยของการเข้ารหัสแบบอสมมาตร

ตามที่ระบุไว้ในตารางข้างต้น อัลกอริทึมแบบอสมมาตรสมัยใหม่อย่าง RSA มักใช้ขนาดคีย์ที่ใหญ่กว่าคู่ขนานแบบสมมาตรที่ใช้กันทั่วไปอย่าง AES-128 มาก แม้แต่โปรโตคอล ECC-based (ECDH และ ECDSA) ที่มีขนาดคีย์เล็กกว่าก็ยังใช้คีย์ขั้นต่ำอย่างน้อย 224 บิต สิ่งนี้หมายความว่าการโจมตีแบบ brute force ที่ค้นหาพื้นที่คีย์ส่วนตัวอย่างครบถ้วนเพื่อระบุคีย์ที่ถูกต้องนั้นไม่สามารถทำได้ในเชิงการคำนวณในอนาคตอันใกล้ สิ่งนี้ยังคงเป็นจริงแม้ว่าจะใช้คอมพิวเตอร์ควอนตัมสำหรับงานนี้ ดังนั้นการโจมตีต่อ AKC มักมุ่งเน้นไปที่การใช้ประโยชน์จากจุดอ่อนที่อาจเกิดขึ้นของ cryptosystems เฉพาะ รูปแบบการโจมตีที่มีการบันทึกไว้ดีบางส่วนมุ่งเป้าไปที่:

1. จุดอ่อนของอัลกอริทึม โดยใช้วิธีทางคณิตศาสตร์และการคำนวณที่ซับซ้อนเพื่อบ่อนทำลายสมมติฐานความยาก ที่ใช้ในการสร้างอัลกอริทึมแบบอสมมาตร ตัวอย่างเช่น ความปลอดภัยของ RSA ขึ้นอยู่กับความยากของการแยกตัวประกอบเฉพาะของจำนวนใหญ่ และความก้าวหน้าในการคำนวณล่าสุดได้ ทำให้สามารถแยกตัวประกอบคีย์ RSA ขนาด 829 บิตได้สำเร็จ ดังนั้น RSA ขนาด 1024 บิตจึงเลิกใช้แล้วในปัจจุบัน อย่างที่จะกล่าวถึงในภายหลัง ความเสี่ยงหลักที่คอมพิวเตอร์ควอนตัมมีต่อ AKC ก็อยู่ในหมวดนี้เช่นกัน

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

3. ข้อบกพร่องในการ implement เช่น ข้อผิดพลาดในการ implement อัลกอริทึมคริปโตกราฟีที่เปิดเผยข้อมูลเกี่ยวกับคีย์โดยไม่ตั้งใจ ตัวอย่างเช่น padding ที่ไม่ถูกต้องอาจเปิดเผยรายละเอียดเกี่ยวกับคีย์

4. Side channels ที่หมายถึงการรั่วไหลของข้อมูลจากระบบฟิสิกส์ที่ทำการเข้ารหัส การรั่วไหลดังกล่าวอาจอยู่ในรูปแบบข้อมูล timing, การใช้พลังงาน หรือแม้แต่เสียง ซึ่งสามารถถูกใช้ประโยชน์ใน side-channel attack ตัวอย่างเช่น การวิเคราะห์ระยะเวลาการดำเนินการคริปโตกราฟีอาจเปิดเผยจำนวน '1' ในคีย์ไบนารี การรั่วไหลที่ดูเหมือนไม่มีผลกระทบนี้ลดพื้นที่การค้นหาลงอย่างมาก ทำให้เห็นแนวทางแก้ปัญหาที่ดูเหมือนเป็นไปไม่ได้ในตอนแรก

5. การแลกเปลี่ยนคีย์ โดยการดักจับคีย์ระหว่างการแลกเปลี่ยน เช่น ใน man-in-the-middle attack (MITM) โปรโตคอล DH เสี่ยงต่อการโจมตีแบบ MITM หากไม่มีขั้นตอนการรับรองตัวตนเพิ่มเติม

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

การรักษาความปลอดภัย cryptosystems แบบอสมมาตรจากการโจมตีหลากหลายรูปแบบที่อาจเกิดขึ้นจึงเป็นงานที่ต้องพิจารณาทั้งในด้านคณิตศาสตร์ ฮาร์ดแวร์ ซอฟต์แวร์ ลอจิสติกส์ และกฎหมาย

RSA

อัลกอริทึม RSA (Rivest-Shamir-Adleman) เป็นหนึ่งในระบบ cryptosystems แบบคีย์สาธารณะระบบแรก และถูกใช้กันอย่างแพร่หลายสำหรับการส่งข้อมูลที่ปลอดภัย เป็น cryptosystem ที่หลากหลายในแง่ที่ให้การดำเนินการที่จำเป็นเพื่อรองรับการเข้ารหัส ถอดรหัส ลายเซ็นดิจิทัล และการแลกเปลี่ยนคีย์ภายใน framework เดียวกัน

ในส่วนนี้ เราจะแสดงการเข้ารหัสแบบอสมมาตร (AKC) โดยใช้ RSA ผ่านตัวอย่างง่ายๆ

เราจะใช้สถานการณ์มาตรฐานของสองฝ่าย คือ Alice และ Bob ที่ต้องการสื่อสารอย่างปลอดภัยโดยใช้ AKC

อัลกอริทึม RSA

อัลกอริทึม RSA พื้นฐานประกอบด้วยสี่การดำเนินการ: การสร้างคีย์ การกระจายคีย์ การเข้ารหัส และการถอดรหัส:

1. การสร้างคีย์:

   คีย์สาธารณะและส่วนตัวถูกสร้างขึ้นจากหลักการทางคณิตศาสตร์เกี่ยวกับจำนวนเฉพาะ โดยการคำนวณนั้นง่าย แต่การย้อนกลับนั้นยาก

   เราจะเรียกสิ่งเหล่านี้ว่า:

   • คีย์สาธารณะ: $(e, n)$
   • คีย์ส่วนตัว: $(d, n)$

   โปรดทราบว่า $n$ มีร่วมกันทั้งในคีย์สาธารณะและคีย์ส่วนตัว และเรียกว่า modulus เราจะต้องใช้สิ่งนี้ในภายหลัง

รายละเอียดทางคณิตศาสตร์

• เลือกจำนวนเฉพาะสองตัวที่แตกต่างกัน $p$ และ $q$
  • เลือกแบบสุ่ม (เพื่อความปลอดภัย)
  • ควรมีขนาดใกล้เคียงกัน แต่ต่างกันในความยาวไม่กี่หลัก เพื่อทำให้การแยกตัวประกอบยากขึ้น
  • สามารถเลือกจำนวนเฉพาะได้อย่างมีประสิทธิภาพโดยใช้ การทดสอบจำนวนเฉพาะ
• คำนวณ $n = p*q$
  • $n$ คือ modulus สำหรับทั้งคีย์สาธารณะและส่วนตัว
• คำนวณ totient $φ$$(n) = (p-1)*(q-1)$
  • totient ควรเก็บเป็นความลับและมักถูกทิ้งหลังการสร้างคีย์
• เลือกจำนวนเต็ม $e$ โดยที่ $1 < e <$$φ$$(n)$ และ $gcd$$(e,$$φ$$(n)) = 1$
  • กล่าวคือ $e$ และ $φ$$(n)$ ควรเป็น coprime
  • ตัวเลข $e$ นี้เป็น exponent ของคีย์สาธารณะและมักเลือกเป็นจำนวนน้อยเพื่อประสิทธิภาพการคำนวณ
  • จำนวนเฉพาะ $65537 = 2^{16} + 1$ มักถูกใช้
  • คำนวณ $d$ เพื่อตอบสนอง congruence relation $d*e ≡ 1 ($$mod$$φ$$(n))$
    • กล่าวคือ $d$ คือ multiplicative inverse ของ $e$ แบบ modulo $φ$$(n)$
    • สิ่งนี้คำนวณได้อย่างมีประสิทธิภาพยิ่งขึ้นโดยใช้ extended Euclidean algorithm
    • ตัวเลข $d$ นี้คือ exponent ของคีย์ส่วนตัว
• คีย์สาธารณะประกอบด้วย $(e, n)$ และคีย์ส่วนตัวคือ $(d, n)$

2. การกระจายคีย์:

   • คีย์สาธารณะ $(e, n)$ จะถูกเปิดเผยต่อสาธารณะสำหรับผู้ที่ต้องการส่งข้อความ
   • คีย์ส่วนตัว $(d, n)$ จะถูกเก็บเป็นความลับ

3. การเข้ารหัส:

   • Alice ต้องการส่งข้อความ $M$ ให้ Bob ในที่นี้คือจำนวนเต็มธรรมดา
   • Alice ใช้คีย์สาธารณะของ Bob $(e, n)$ เพื่อเข้ารหัสข้อความเป็น ciphertext $C$

   รายละเอียดทางคณิตศาสตร์

   • $M$ คือ จำนวนเต็ม $0 ≤ M < n$
   • $C ≡ M^e (mod n)$ โดยที่ $C$ คือ ciphertext

4. การถอดรหัส:

   • Bob ได้รับ ciphertext $C$
   • Bob ใช้คีย์ส่วนตัวของตน $(d, n)$ เพื่อถอดรหัสข้อความกลับเป็นข้อความ $M$

   รายละเอียดทางคณิตศาสตร์

   • $M ≡ C^d (mod n)$

นี่คือโครงร่างพื้นฐานของ RSA ในทางปฏิบัติ padding schemes ที่ซับซ้อนกว่า จะถูกนำมาใช้กับ plain text $M$ ก่อนการเข้ารหัส เพื่อให้แน่ใจว่า plain text ที่เหมือนกันจะให้ ciphertexts ที่แตกต่างกัน สิ่งนี้ป้องกันการโจมตีหลากหลายรูปแบบต่อการ implement RSA แบบธรรมดา และรองรับ semantic security

ตัวอย่างการ implement RSA ด้วย Python

ในเซลล์โค้ดต่อไปนี้ เราจะแสดงตัวอย่างง่ายๆ ของอัลกอริทึม RSA โดยใช้จำนวนเต็มขนาดเล็ก จากนั้นแสดงการประยุกต์ใช้งานจริงด้านการกระจายคีย์และลายเซ็นดิจิทัลโดยใช้ไลบรารี Python ที่ implement RSA

หมายเหตุ

หมายเหตุ: ในส่วนนี้เราจะแสดงการคำนวณทางคณิตศาสตร์โดยละเอียดเป็นส่วนหนึ่งของโค้ด Python

การสร้างคีย์ RSA

มาทำตามขั้นตอนง่ายๆ ของอัลกอริทึม RSA โดยใช้จำนวนเฉพาะขนาดเล็ก

เราจะต้องสามารถคำนวณ greatest common divisor ของจำนวนเต็มสองตัว เพราะจำเป็นต้องใช้ตรวจสอบว่าจำนวนเต็มสองตัวนั้นเป็น coprime หรือไม่

เราจะอธิบายวิธีคำนวณง่ายๆ หนึ่งวิธี แต่ประสิทธิภาพสูงกว่ามากสำหรับจำนวนเต็มขนาดใหญ่คือการใช้ฟังก์ชัน Python math.gcd

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

ขั้นตอนแรกของ workflow RSA คือการสร้างคีย์ เริ่มต้นด้วยการเลือกจำนวนเฉพาะสองตัว ซึ่งผู้สร้างคีย์ควรเก็บเป็นความลับ

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

ต่อไป คำนวณ modulus $n$ ซึ่งเป็นเพียงผลคูณของจำนวนเฉพาะสองตัวที่เลือก modulus นี้จะถูกประกาศเป็นส่วนหนึ่งของคีย์สาธารณะ

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

ฟังก์ชัน Euler totient $\varphi(n)$ จะถูกคำนวณต่อไป เพราะจำเป็นสำหรับการดำเนินการ modular multiplicative inverse ที่ใช้กำหนดคีย์ใน RSA และ $phi$ ก็ถูกเก็บเป็นความลับและมักถูกทิ้งหลังการสร้างคีย์

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

ตอนนี้เราพร้อมที่จะคำนวณคีย์สาธารณะและส่วนตัว ใน RSA แต่ละคีย์ถูกระบุโดย tuple ของจำนวนเต็มสองตัว รายการแรกในแต่ละ tuple เป็นจำนวนเต็มที่แตกต่างกัน และรายการที่สองคือ modulus $n$ ที่มีร่วมกันในทั้งสองคีย์

รายการแรกของคีย์สาธารณะสามารถเป็นจำนวนเต็มใดก็ได้ที่มากกว่า 1 และเป็น coprime กับ $phi$ จำนวนเต็มสองตัวเป็น coprime ถ้า greatest common divisor ของพวกมันเป็น 1 ดังนั้นเราจึงใช้ฟังก์ชัน math.gcd หาจำนวนเต็ม $e$ ที่เป็น coprime กับ $phi$

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

คีย์ส่วนตัวต้องการจำนวนเต็ม $d$ ซึ่งเป็น multiplicative inverse ของ $e$ แบบ modulo $phi$ กล่าวคือ ตอบสนอง congruency relation $d*e\equiv 1 \pmod{\varphi(n)}$ สำหรับตัวอย่างง่ายๆ นี้ที่เราจัดการกับจำนวนเต็มขนาดเล็ก เราสามารถวนซ้ำผ่านจำนวนเต็มบวกเพื่อหา $d$ ที่เหมาะสม ในการตั้งค่าจริง extended Euclidean algorithm ที่มีประสิทธิภาพในเชิงการคำนวณจะถูกใช้สำหรับวัตถุประสงค์นี้

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

ตอนนี้เราสร้าง tuples $(e, n), (d, n)$ ซึ่งประกอบเป็นคีย์สาธารณะและส่วนตัวตามลำดับ คีย์สาธารณะจะถูกประกาศ ในขณะที่คีย์ส่วนตัวถูกเก็บเป็นความลับ

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

การเข้ารหัสและถอดรหัสใน RSA ใช้ การดำเนินการ modular exponentiation นอกจากนี้ คีย์สาธารณะและส่วนตัวเป็นสิ่งเสริมกันในแง่ที่คีย์ใดก็ได้สามารถใช้เข้ารหัสข้อความที่อีกคีย์สามารถถอดรหัสได้

ที่นี่เราแสดงกรณีที่คีย์สาธารณะ $(e,n)$ ใช้สำหรับการเข้ารหัสและคีย์ส่วนตัว $(d, n)$ ใช้สำหรับการถอดรหัส โดยกำหนดฟังก์ชัน Python สำหรับแต่ละการดำเนินการ

จากนั้นเราเข้ารหัสและถอดรหัสข้อความจำนวนเต็ม $msg$

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

แม้ว่าจำนวนเต็มขนาดเล็กที่ใช้ข้างต้นจะมีประโยชน์ในการอธิบายแนวคิดหลักของอัลกอริทึม RSA ได้ง่าย ในแอปพลิเคชันจริง RSA ต้องใช้จำนวนเต็มขนาดใหญ่มาก ตัวอย่างเช่น RSA ขนาด 2048 บิตใช้ modulus $n$ ที่ยาว 2048 บิต ซึ่งเทียบเท่าเลขทศนิยมประมาณ 10$^{616}$ ตัวเลขขนาดมหึมาเหล่านี้จำเป็นสำหรับความปลอดภัยในทางปฏิบัติของ RSA

การแลกเปลี่ยนคีย์สมมาตรด้วย RSA

ตามที่กล่าวไว้ก่อนหน้านี้ AKC ช่วยให้สองฝ่ายที่ต้องการสื่อสารสามารถสร้าง shared secret ที่ปลอดภัยได้ ซึ่งสามารถนำไปใช้เป็น secret key สำหรับการเข้ารหัสสมมาตรของ plain text จำนวนมากต่อไป

ลองพิจารณาสถานการณ์ต่อไปนี้ Alice และ Bob ต้องการใช้ SKC ในการเข้ารหัสและถอดรหัสข้อความ อย่างไรก็ตาม ก่อนที่กระบวนการนี้จะเริ่มต้นได้ พวกเขาต้องตกลงกันเรื่อง secret key ร่วมกัน ทางเลือกหนึ่งคือให้ฝ่ายใดฝ่ายหนึ่ง ซึ่งก็คือ Alice สร้าง secret key แล้วส่งต่อไปยัง Bob อย่างปลอดภัย เพื่อให้การส่งต่อนี้ปลอดภัย Alice ตัดสินใจใช้ RSA เป็น key encapsulation mechanism (KEM)

ขั้นตอนที่ต้องทำมีดังนี้:

• ขั้นแรก Alice สร้าง symmetric key แบบสุ่ม ซึ่งเธอตั้งใจจะแชร์กับ Bob
• จากนั้น Bob สร้าง asymmetric key pair และทำให้คีย์สาธารณะของเขาสามารถเข้าถึงได้บนช่องทางที่เหมาะสม
• ต่อมา Alice ใช้คีย์สาธารณะของ Bob เพื่อเข้ารหัส symmetric key ทำให้ถูก encapsulate ในรูปแบบ ciphertext
• จากนั้น Alice ประกาศ ciphertext ผ่านช่องทางที่เชื่อถือได้แต่ไม่จำเป็นต้องปลอดภัย
• สุดท้าย Bob ได้รับ ciphertext และถอดรหัสด้วยคีย์ส่วนตัวของตน เขาจึงได้เข้าถึง symmetric key ที่ Alice สร้าง

รูปที่ 1. การแลกเปลี่ยนคีย์สมมาตรด้วย RSA

ตัวอย่างการแลกเปลี่ยนคีย์แบบ padding ด้วย Python

ตอนนี้เราจะแสดง workflow จริงที่ใช้ RSA สำหรับการแลกเปลี่ยนคีย์แบบ non-interactive ที่ใช้ padding โดยใช้ไลบรารี Python cryptography

นำเข้า modules ที่จำเป็นจากไลบรารี Python cryptography หากจำเป็นต้องติดตั้ง สามารถใช้คำสั่ง pip install cryptography

จากนั้น Alice สร้าง secret key แบบสุ่ม ซึ่งเธอตั้งใจจะส่งไปยัง Bob

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

โดยใช้ module rsa จากไลบรารี cryptography Bob สร้าง key pair แล้วประกาศคีย์สาธารณะของเขา ทุกคนสามารถดักจับคีย์สาธารณะและอ่านตัวเลขสาธารณะ $(e,n)$ ที่ประกอบเป็นคีย์ได้

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

ณ จุดนี้ เราสมมติว่า Alice ได้รับคีย์สาธารณะที่ Bob ประกาศมา symmetric_key ของ Alice ข้างต้นสามารถเข้ารหัสได้โดยใช้คีย์สาธารณะของ Bob เพื่อสร้าง ciphertext ในการตั้งค่าจริง Alice จะใช้วิธี padding เพิ่มเติมเช่น OAEP เพื่อให้ semantic security ในการสื่อสารกับ Bob

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

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

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

ณ จุดนี้ ทั้ง Alice และ Bob มีสิทธิ์เข้าถึง secret symmetric key ซึ่งพวกเขาสามารถนำไปใช้สำหรับแอปพลิเคชัน SKC

การจำลอง Key Encapsulation Mechanism ด้วย RSA ใน Python

ใน workflow ต่อไปนี้ เราจะแสดงการใช้ RSA จำลอง Key Encapsulation Mechanism (KEM) ซึ่ง secret message แบบสุ่มที่ยาวพอจะถูกแลกเปลี่ยนอย่างปลอดภัยและต่อมาแปลงเป็น shared-secret ที่มีความยาวเหมาะสมโดยใช้ KDF

อีกครั้ง Alice และ Bob ต้องการสร้าง shared secret แบบ non-interactive และ Alice เป็นฝ่ายที่ตัดสินใจว่าจะใช้ secret ใด

เราเริ่มต้นด้วยการนำเข้าไลบรารี Python ที่จำเป็น

Bob จากนั้นสร้าง RSA key pair ของตนและประกาศคีย์สาธารณะ

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice ก่อนอื่นสร้าง long secret แบบสุ่ม ซึ่ง shared secret จะถูกดึงมาในท้ายที่สุด ใน KEM แบบบริสุทธิ์ long secret จะเป็น random element จากโครงสร้างพีชคณิตที่อยู่เบื้องหลัง cryptosystem ในกรณีของ RSA ขนาด 2048 บิต นั่นจะเป็น random integer modulo RSA modulus ขนาด 2048 บิต เนื่องจาก KEM แบบบริสุทธิ์ดังกล่าวไม่ต้องการ padding เพิ่มเติม แต่ในตัวอย่างนี้เราเพียงจำลอง KEM โดยใช้ RSA และไลบรารี cryptography ต้องการการใช้ padding เมื่อเข้ารหัสด้วย RSA ดังนั้นเราจะใช้ long secret ที่สั้นกว่าแต่ก็ยังยาวกว่า AES key ขนาด 256 บิตมาก

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

ต่อมา Alice เข้ารหัส long secret โดยใช้คีย์สาธารณะของ Bob และ secret ที่เข้ารหัสแล้วจะถูกส่งไปยัง Bob

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob ถอดรหัส encrypted secret ที่ได้รับจาก Alice โดยใช้คีย์ส่วนตัวของตน

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

สุดท้าย ทั้ง Alice และ Bob ต่างนำ Key Derivation Function (KDF) ที่ตกลงกันไว้มาใช้กับ long secret แยกกัน เพื่อดึง symmetric key ออกมา

โปรดทราบว่ากระบวนการนี้เกี่ยวข้องกับโปรโตคอล hashing และการใช้ salt แบบสุ่ม ซึ่งช่วยให้มั่นใจถึงความเป็นเอกลักษณ์และความไม่สามารถทำนายได้ของ symmetric key ที่ใช้ร่วมกัน ในกรณีที่ long secret เคยถูกใช้ซ้ำ (ไม่แนะนำ) อย่างไรก็ตาม salt เองไม่จำเป็นต้องเป็นความลับ และเมื่อถูกสร้างแบบสุ่มแล้ว เช่น โดย Alice ในตัวอย่างนี้ ก็สามารถประกาศไปยัง Bob พร้อมกับ encrypted long secret ได้

เราจึงสมมติว่าทั้ง Alice และ Bob มีสิทธิ์เข้าถึง salt แบบสุ่มเดียวกัน

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

ลายเซ็นดิจิทัลด้วย RSA

ตอนนี้เราจะขยายสถานการณ์การสื่อสารที่เป็นความลับระหว่าง Alice และ Bob ให้รวมถึงการตรวจสอบความถูกต้องด้วยความช่วยเหลือของ ลายเซ็นดิจิทัล

เหมือนเดิม Alice จะส่งข้อความที่เป็นความลับซึ่ง encapsulate symmetric key ไปยัง Bob แต่เธอยังต้องการลงลายเซ็นดิจิทัลข้อความ เพื่อให้ Bob เมื่อได้รับข้อความแล้วสามารถยืนยันได้ว่า Alice เป็นผู้ส่ง และเนื้อหาของข้อความไม่ถูกดัดแปลงระหว่างการส่ง

โดยทั่วไปแล้ว เป็นที่ต้องการที่จะสามารถตรวจสอบความถูกต้องโดยไม่กระทบต่อความลับ โดยที่ฝ่ายที่สนใจใดๆ ก็สามารถยืนยัน ความสมบูรณ์, ความถูกต้อง และพิสูจน์ non-repudiation ของการสื่อสารที่กำหนดได้ แม้ว่าฝ่ายนั้นจะไม่มีสิทธิ์เข้าถึง plain text จริงๆ ก็ตาม

เราจะพิจารณาการตั้งค่าทั่วไปนี้ซึ่งประกอบด้วยขั้นตอนต่อไปนี้:

• ขั้นแรก ทั้ง Bob และ Alice ทำให้คีย์สาธารณะของตนสามารถเข้าถึงได้ผ่านช่องทางเปิด
• จากนั้น Alice เข้ารหัส plain text โดยใช้คีย์สาธารณะของ Bob สร้าง ciphertext
• ต่อมา Alice สร้าง hash ของ ciphertext ด้วย hash function และยังเข้ารหัส ciphertext ที่ผ่าน hash แล้วนี้โดยใช้คีย์ส่วนตัวของเธอ hash ที่เข้ารหัสแล้วนี้คือ signature
• จากนั้น Alice ส่งทั้ง ciphertext และ signature ผ่านช่องทางเปิด
• จากนั้น Bob ใช้คีย์สาธารณะของ Alice เพื่อถอดรหัส signature เผยให้เห็น ciphertext ที่ผ่าน hash แล้ว
• ต่อมา เนื่องจาก Bob ยังมีสิทธิ์เข้าถึง ciphertext ด้วยตัวเอง เขาใช้ hash function เดียวกับที่ Alice ใช้เพื่อสร้าง ciphertext ที่ผ่าน hash ขึ้นมาอีกครั้ง หากมันตรงกับที่ได้จากการถอดรหัส signature ของ Alice ข้อความก็ได้รับการตรวจสอบแล้ว แม้ว่า ciphertext ยังไม่ได้ถอดรหัสก็ตาม
• สุดท้าย Bob เมื่อตรวจสอบข้อความแล้ว จะถอดรหัส ciphertext โดยใช้คีย์ส่วนตัวของตัวเอง

รูปที่ 2. ลายเซ็นดิจิทัลด้วย RSA

ต่อไปจะแสดง workflow นี้สำหรับลายเซ็นดิจิทัล

เราจะนำเข้า modules ที่มีประโยชน์จากไลบรารี cryptography อีกครั้ง เหมือนเดิม Alice ตั้งใจจะส่ง symmetric key ไปยัง Bob อย่างปลอดภัย แต่เธอยังต้องการลงลายเซ็นดิจิทัลด้วย ในกรณีนี้ เราต้องการคีย์สาธารณะของทั้ง Alice และ Bob ดังนั้น ขั้นตอนแรกคือทั้ง Alice และ Bob สร้าง key pair ของตัวเองโดยใช้ RSA และประกาศคีย์สาธารณะของตนให้ทั่วโลกรับรู้

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

ในขั้นตอนถัดไป เหมือนเดิม Alice ใช้คีย์สาธารณะของ Bob เพื่อเข้ารหัส symmetric key และเตรียม ciphertext

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

ณ ขั้นตอนนี้ แทนที่จะแค่ประกาศ ciphertext Alice ตั้งใจจะแนบลายเซ็นดิจิทัลเพื่อพิสูจน์ให้ Bob ทราบว่าเธอเป็นผู้ส่ง ซึ่งทำได้สองขั้นตอน:

1. สร้าง hash ของ ciphertext โดยใช้ hashing algorithm
2. เข้ารหัส hash โดยใช้คีย์ส่วนตัวของ Alice ซึ่งเทียบเท่ากับลายเซ็น

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Alice จะประกาศ ciphertext และ signature ผ่านเครือข่ายเพื่อให้ Bob สามารถรับทั้งสองได้

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

ในฝั่งของ Bob งานแรกคือตรวจสอบ ความสมบูรณ์ และ ความถูกต้อง ของ ciphertext ในการทำเช่นนี้ Bob สร้าง hash ของ ciphertext ที่ได้รับโดยใช้ hashing algorithm เดียวกับที่ Alice ใช้

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

จากนั้น Bob ถอดรหัส signature ที่ได้รับโดยใช้คีย์สาธารณะของ Alice เนื่องจาก Alice ใช้คีย์ส่วนตัวของเธอสร้าง signature Bob จึงสามารถถอดรหัสได้โดยใช้คีย์สาธารณะของ Alice signature ที่ถอดรหัสแล้วไม่ใช่อะไรอื่นนอกจาก hash ของ ciphertext ที่สร้างโดย Alice หาก hash ที่ Bob สร้างตรงกับ signature ที่ถอดรหัสแล้ว Bob ก็ยืนยันได้ว่า ciphertext ที่เขาได้รับไม่ถูกดัดแปลงและเป็น Alice ที่ลงนาม ciphertext

ในโค้ด Python ด้านล่าง การดำเนินการเหล่านี้ถูกรวมเข้าเป็นฟังก์ชัน utility ที่มีประโยชน์ชื่อ verify ซึ่งจัดให้โดย object ที่เกี่ยวข้องกับคีย์สาธารณะของ Alice

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

เมื่อยืนยัน ความสมบูรณ์ และ ความถูกต้อง ของ ciphertext ที่ได้รับแล้ว Bob จึงสามารถถอดรหัส ciphertext โดยใช้คีย์ส่วนตัวของตน เพราะ Alice สร้าง ciphertext โดยใช้คีย์สาธารณะของ Bob

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

ในสถานการณ์ลายเซ็นดิจิทัลข้างต้น ทุกฝ่าย ไม่เฉพาะ Bob สามารถยืนยันได้ว่า Alice เป็นผู้ส่ง ciphertext เพราะทุกคนสามารถเข้าถึงคีย์สาธารณะของ Alice, ciphertext และลายเซ็นดิจิทัล นอกจากนี้ หลังจากส่ง ciphertext และ signature แล้ว Alice ไม่สามารถปฏิเสธในภายหลังได้ เพราะ signature สามารถถอดรหัสเป็น hash ที่มีความหมายได้โดยใช้คีย์สาธารณะของเธอเท่านั้น สิ่งนี้พิสูจน์ non-repudiation

ด้วยการช่วยให้การกระจายคีย์ที่ปลอดภัยและรองรับ non-repudiation การเข้ารหัสแบบคีย์สาธารณะจึงสร้างรากฐานที่มั่นคงสำหรับการสื่อสารดิจิทัลที่ปลอดภัย

การทำลาย RSA

ประโยชน์และความปลอดภัยของอัลกอริทึม RSA ที่อธิบายข้างต้นขึ้นอยู่กับสมมติฐานทางคณิตศาสตร์สองข้อ:

1. การหา modular multiplicative inverse $d$ โดยมีเพียงสิทธิ์เข้าถึง $(e, n)$ เท่านั้นนั้นไม่สามารถทำได้ในเชิงการคำนวณ

2. ในการตั้งค่า RSA การดำเนินการ modular exponentiation มีพฤติกรรมเหมือน one-way trapdoor function เมื่อใช้สำหรับการเข้ารหัส จะให้ ciphertext ที่อ่านไม่ออก และหากไม่มีสิทธิ์เข้าถึงคีย์ส่วนตัว การกลับการดำเนินการเพื่อกู้คืน plain text จาก ciphertext นั้นไม่สามารถทำได้ อย่างไรก็ตาม ด้วยสิทธิ์เข้าถึงคีย์ส่วนตัวซึ่งทำหน้าที่เป็น trapdoor การถอดรหัส ciphertext ทำได้ง่าย

การโจมตีที่โดดเด่นที่สุดต่ออัลกอริทึม RSA มุ่งเป้าไปที่การบ่อนทำลายสมมติฐานที่ 1 โดยการกู้คืนหมายเลขคีย์ส่วนตัว $d$ อย่างมีประสิทธิภาพผ่านการแยกตัวประกอบ modulus $n$ ดังที่จะแสดงด้านล่าง การกู้คืน $d$ นั้นง่ายหากมีสิทธิ์เข้าถึง ตัวประกอบเฉพาะ $p$ และ $q$ ของ $n$ หรือ totient $φ$$(n)$ ขอให้จำว่า $p$, $q$ และ $φ$$(n)$ ถูกเก็บเป็นความลับระหว่างการสร้างคีย์และถูกทิ้งหลังจากนั้น บุคคลที่สามที่กู้คืนข้อมูลนี้โดยใช้คอมพิวเตอร์คลาสสิกหรือควอนตัมจะเปิดเผยคีย์ส่วนตัวได้จริง ทำลาย RSA ดังนั้น การแยกตัวประกอบเฉพาะจึงเป็น computational primitive หลักที่จำเป็นสำหรับการทำลาย RSA

การคำนวณแบบคลาสสิกและ RSA

การแยกตัวประกอบเฉพาะของจำนวนเต็มขนาดใหญ่เป็นที่ทราบกันว่ามี scaling แบบ super-polynomial หรือ subexponential บนคอมพิวเตอร์คลาสสิก อัลกอริทึมคลาสสิกที่ดีที่สุดในการแยกตัวประกอบจำนวนเต็มที่ใหญ่กว่า $10^{100}$ คือ general number field sieve (GNFS)

รายละเอียดทางคณิตศาสตร์

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

เป็นฟังก์ชันของจำนวนเต็ม $n$ ที่ต้องแยกตัวประกอบ

Scaling นี้เป็น super-polynomial ในจำนวนบิตที่จำเป็นในการแทน $n$

ดังนั้น การแยกตัวประกอบเฉพาะจึงถือว่าไม่มีประสิทธิภาพบนคอมพิวเตอร์คลาสสิก

ในปัจจุบัน จำนวนเต็มที่ใหญ่ที่สุดที่แยกตัวประกอบได้บนฮาร์ดแวร์คลาสสิก อยู่ที่ประมาณ 829 บิต หรือ 250 หลักทศนิยม เมื่อพิจารณาจากการเติบโตแบบ exponential ของพลังคอมพิวเตอร์คลาสสิกที่เกิดขึ้นในช่วงหลายทศวรรษที่ผ่านมา RSA ขนาด 1024 บิตไม่ถือว่าปลอดภัยในระยะใกล้อีกต่อไปและถูกเลิกใช้แล้ว อย่างไรก็ตาม ในอนาคตอันใกล้ การแยกตัวประกอบจำนวนเต็ม 2048 บิตที่มีขนาดอยู่ในช่วง $10^{617}$ ยังคงถือว่าไม่สามารถทำได้บนระบบคลาสสิก แสดงให้เห็นถึงความยังคงใช้งานได้ต่อไป อย่างไรก็ตาม การมาถึงของคอมพิวเตอร์ควอนตัมทำให้การประเมินนี้ไม่ถูกต้องอีกต่อไป

อัลกอริทึมควอนตัม Shor และ RSA

อัลกอริทึมควอนตัมที่รู้จักกันดีที่สุดในปัจจุบันอาจเป็น อัลกอริทึม Shor สำหรับการหาตัวประกอบเฉพาะของจำนวนเต็ม เมื่อ Peter Shor แนะนำในปี 1994 มันถูกยอมรับว่าเป็นอัลกอริทึมควอนตัมตัวแรกที่ให้ super-polynomial speedup เมื่อเทียบกับอัลกอริทึมคลาสสิกในปัญหาที่มีความสำคัญในทางปฏิบัติอย่างยิ่ง นั่นคือการแยกตัวประกอบเฉพาะ

อัลกอริทึม Shor สามารถแยกตัวประกอบเฉพาะด้วย $O(n^2)$ โดยที่ $n$ คือจำนวนบิต

คำอธิบายทางคณิตศาสตร์ของอัลกอริทึม Shor

ในบริบทของ RSA, อัลกอริทึม Shor ทำงานโดยใช้ประโยชน์จาก ความเป็นคาบ ของ ฟังก์ชัน modular exponential $f(x) = a^x (mod~n)$ และให้ period-finding primitive แบบควอนตัมที่ช่วยให้แยกตัวประกอบเฉพาะของ modulus $n$ ได้อย่างมีประสิทธิภาพ

โครงร่างระดับสูงที่ง่ายขึ้นของแผนการโดยรวมของ Shor ในการทำลาย RSA มีดังนี้:

1. กำหนด modulus $n$ ที่ถูกประกาศเป็นส่วนหนึ่งของคีย์สาธารณะ เลือกตัวเลข $a$ ที่เป็น coprime กับ $n$ กล่าวคือ $gcd(a,n) = 1$ เนื่องจากเราทราบว่า $n = p*q$ มีตัวประกอบเฉพาะสองตัว $(p, q)$ เกือบทุกจำนวนที่น้อยกว่า $n$ ที่เราเลือกแบบสุ่มมีแนวโน้มจะเป็น coprime กับ $n$

2. เมื่อเลือก $a$ แล้ว ให้หา exponent $r$ โดยที่ $a^r \equiv 1 (mod~n)$ สิ่งนี้หมายความว่า $a^r - 1 \equiv 0 (mod~n)$ การมีอยู่ของ exponent $r$ โดยที่ congruence ข้างต้นเป็นจริง ได้รับการรับประกันจาก คุณสมบัติความเป็นคาบ ของ modular exponentiation

3. ถ้า $r$ เป็นเลขคู่ $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ สำหรับจำนวนเต็ม $\gamma$ บางตัว ด้านซ้ายของความเท่ากันนี้ต้องมี $p$ และ $q$ เป็นสองในตัวประกอบเฉพาะ เนื่องจากด้านขวามีตัวประกอบเหล่านั้น ถ้า $r$ เป็นเลขคี่ ให้กลับไปขั้นตอนที่ 1 และลองเลือก $a$ อื่น

4. ใช้ extended Euclid algorithm สำหรับการหา $gcd((a^{r/2} - 1), n)$ หรือ $gcd((a^{r/2} + 1), n)$ GCDที่คำนวณได้มีแนวโน้มสูงมากที่จะระบุตัวประกอบเฉพาะตัวหนึ่ง $p$ หรือ $q$ หาร $n$ ด้วยตัวประกอบเฉพาะที่พบแล้วเพื่อกู้คืนตัวอื่น

5. เมื่อทราบ $p, q$ แล้ว ให้ใช้ขั้นตอนจากอัลกอริทึม RSA ดั้งเดิมเพื่อสร้าง totient $\phi(n)$ ขึ้นมาใหม่ และสร้างหมายเลขคีย์ส่วนตัว $d$ เป็น modular inverse ของหมายเลขคีย์สาธารณะ $e$ ที่ทราบอยู่แล้ว

ในเดือนสิงหาคม 2023 Oded Regev ได้ประกาศการปรับปรุง จาก Shor ดั้งเดิมโดยใช้แนวทาง multi-dimensional ได้ผลลัพธ์ที่ $O(n^{1.5})$ ยังคงมีการวิจัยต่อเนื่องรวมถึงโดย Ragavan และ Vaikuntanathan ในพื้นที่นี้ซึ่งอาจปรับปรุงเวลา ต้นทุน หรือจำนวน qubits ที่จำเป็น แม้ว่าเราจะไม่สามารถบอกได้ว่าการรันอัลกอริทึมดังกล่าวกับการเข้ารหัส RSA จริงในโลกจริงจะเป็นไปได้จริงเมื่อใด แต่มันกำลังเข้าใกล้มากขึ้นทุกที

ตัวอย่าง Python แสดงการทำลายการเข้ารหัส RSA

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

หมายเหตุ

ในส่วนนี้เราจะแสดงการคำนวณทางคณิตศาสตร์โดยละเอียดเป็นส่วนหนึ่งของโค้ด Python

ในตัวอย่าง เรามีคีย์สาธารณะ $(5, 247)$ และเราจะกู้คืนคีย์ส่วนตัว

ขั้นตอนที่ 1: ขั้นตอนแรกคือการเลือกตัวเลขที่เป็น coprime กับ 247 เกือบทุกจำนวนที่เราเดาจะทำงานได้ ลองเลือก 6

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

ขั้นตอนที่ 2: ต่อมาเราต้องหา period $r$ โดยที่ $6^r \equiv 1 (mod~247)$ ในตัวอย่างนี้เราคำนวณ $r$ แบบคลาสสิกโดยใช้ brute force แต่เราก็สามารถใช้อัลกอริทึม Shor บนคอมพิวเตอร์ควอนตัมโดยใช้ Qiskit

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

ขั้นตอนที่ 3: เนื่องจาก period $r = 36$ เป็นเลขคู่ เราสามารถคำนวณ $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

ขั้นตอนที่ 4: หา GCD ของตัวประกอบใดตัวหนึ่งกับ $n$ เพียงหาร $n$ ด้วยตัวประกอบเฉพาะที่พบแล้วเพื่อได้ตัวประกอบเฉพาะตัวที่สอง

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

ขั้นตอนที่ 5: เมื่อกู้คืนตัวประกอบเฉพาะของ $n = 247$ เป็น $p_{found}=13$ และ $q_{found}=19$ แล้ว เราคำนวณ totient $\phi_{found} = (p_{found}-1)*(q_{found}-1)$

คีย์ส่วนตัวคือ modular inverse ของหมายเลขคีย์สาธารณะ $e=5$

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

ในแผนการข้างต้น ขั้นตอนที่ 2 คือการดำเนินการ period-finding ที่สำคัญ ซึ่ง อัลกอริทึม Shor ใช้ primitives ควอนตัมพื้นฐานสองอย่าง ได้แก่ quantum Fourier transform และ quantum phase estimation สำหรับคำอธิบายโดยละเอียดเกี่ยวกับด้านควอนตัมของอัลกอริทึม Shor ดูบทเรียน Phase estimation and factoring ใน Fundamentals of Quantum Algorithms ขั้นตอนที่ 1 และ 3 ถึง 5 เกี่ยวข้องกับการดำเนินการที่ค่อนข้างไม่แพงซึ่งสามารถดำเนินการบนคอมพิวเตอร์คลาสสิกได้ง่าย

ตัวเลือก นี่คือคำอธิบายภาพโดยละเอียดของการ implement อัลกอริทึม Shor

บนคอมพิวเตอร์ควอนตัม อัลกอริทึม Shor สามารถแสดง polylogarithmic scaling ที่ดีเท่ากับ $O((log~n)^2 (log~log~n))$ ในแง่ของ modulus $n$ หรือ polynomial scaling ในแง่ของจำนวนบิตที่จำเป็นในการแทน $n$ นี่คือ super-polynomial speedup เมื่อเทียบกับอัลกอริทึมคลาสสิก GNFS

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

การแลกเปลี่ยนคีย์ Diffie-Hellman และ Digital Signature Algorithm

ในส่วนก่อนหน้า เราได้กล่าวถึง RSA cryptosystem ซึ่งความปลอดภัยขึ้นอยู่กับความยากในการคำนวณของการแยกตัวประกอบเฉพาะ ที่นี่ เราจะกล่าวถึงโปรโตคอลคริปโตกราฟีแบบอสมมาตรยอดนิยมสองโปรโตคอล ได้แก่ Diffie-Hellman key exchange (DH) และ Digital Signature Algorithm (DSA) ซึ่งทั้งคู่ขึ้นอยู่กับปัญหาทางคณิตศาสตร์ที่แตกต่างกัน นั่นคือ discrete logarithm problem (DLP)

ปัญหา discrete logarithm

ในสมการต่อไปนี้เราต้องหา $a$ โดยให้เพียง $e$, $M$, $c$ เท่านั้น

$a^e$ $mod$ $M = c$

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

สิ่งนี้เรียกว่า discrete logarithm problem (DLP)

รายละเอียดทางคณิตศาสตร์ของ discrete logarithm problem

DLP มักถูกกำหนดในบริบทของ cyclic groups และระบุดังนี้

พิจารณา cyclic group $G$ ที่ถูกสร้างโดย group element $g \in G$ และกำหนด arbitrary element $h \in G$ หาจำนวนเต็ม $k$ โดยที่ $h = g^{k}$

ที่นี่จำนวนเต็ม $k \equiv log_{g}h$ คือ discrete logarithm คุณสมบัติ cyclic ของ $G$ รับประกันว่าสำหรับทุก $h$ จำนวนเต็ม $k$ ที่ถูกต้องมีอยู่

สำหรับคริปโตกราฟี DLP บน multiplicative group ของจำนวนเต็ม modulo จำนวนเฉพาะ $p$ ที่แทนด้วย $(\mathbb{Z}_p)^{\times}$ กลายเป็นสิ่งที่มีประโยชน์ องค์ประกอบของ $(\mathbb{Z}_p)^{\times}$ คือ congruence classes ที่ระบุด้วยจำนวนเต็ม modulo $p$ ที่เป็น coprime กับ $p$

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

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{and}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

การดำเนินการคูณ $(\times)$ บน groups เหล่านี้เป็นเพียงการคูณจำนวนเต็มธรรมดาตามด้วยการลดค่า modulo $p$ และการยกกำลังด้วยจำนวนเต็ม $k$ เป็นการคูณซ้ำ $k$ ครั้งและลดค่า modulo $p$

มาแสดงตัวอย่างของ DLP บน $(\mathbb{Z}_7)^{\times}$

multiplicative group นี้มี generators สองตัว ${[3],[5]}$ ที่เรียกอีกอย่างว่า primitive roots เราจะใช้ $[5]$ เป็น generator กล่าวคือ สร้างทุกองค์ประกอบของ $(\mathbb{Z}_7)^{\times}$ โดยใช้กำลังจำนวนเต็มที่ต่อเนื่องกันของ 5

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

เราเห็นว่าในเลขคณิต modulo 7 การยก 5 ขึ้นกำลังจำนวนเต็มที่ต่อเนื่องกันให้ทุกองค์ประกอบของ $(\mathbb{Z}_7)^{\times}$ ครั้งละหนึ่งครั้งก่อนที่วัฏจักรจะทำซ้ำอย่างไม่มีกำหนดด้วยรอบ $p-1 =6$

ดังนั้น DLP บน $(\mathbb{Z}_7)^{\times}$ ด้วย generator [5] คือ:

$\mathrm{Given}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, find~} k \mathrm{~such~that~} 5^{k} \equiv h~(mod~7)$

จาก output ของเซลล์ Python ข้างต้นเราเห็นว่า:

$h = 2 \implies k=4 \mathrm{~or~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~or~} 3 = log_5(6) (mod~7)$

ในเลขคณิตจำนวนจริงธรรมดา การยกกำลังเป็นฟังก์ชัน monotonic และการหา logarithm ของตัวเลขใดก็ได้ในฐานใดก็ได้นั้นง่ายในเชิงการคำนวณ ในทางตรงกันข้าม ตามที่เห็นได้จากตัวอย่าง $(\mathbb{Z}_7)^{\times}$ ง่ายๆ ข้างต้น modular exponentiation เป็น non-monotonic และแม้ว่ามันจะเป็นคาบด้วยรอบ $p-1$ แต่นอกจากนั้นก็ไม่ใช่เรื่องง่าย ดังนั้น การคำนวณ inverse ของมัน ซึ่งก็คือ discrete logarithm จึงไม่มีประสิทธิภาพสำหรับ $p$ ขนาดใหญ่บนคอมพิวเตอร์คลาสสิก

การสังเกตนี้เป็นพื้นฐานของทั้ง Diffie-Hellman (DH) key exchange และ Digital Signature Algorithm (DSA) ที่จะกล่าวถึงในส่วนถัดไป

DLP สามารถขยายไปยัง cyclic subgroups ได้ดังนี้:

• พิจารณา $(\mathbb{Z}_p)^{\times}$ ที่กำหนดข้างต้นและ element $g \in (\mathbb{Z}_p)^{\times}$ ที่มี prime order $r$ กล่าวคือ $g^r \equiv 1 (~mod~p)$
• เซตของกำลังจำนวนเต็มของ $g$: $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ เป็น cyclic subgroup ของ $(\mathbb{Z}_p)^{\times}$ ที่มี group order $r$
• DLP สามารถระบุบน $\langle g \rangle$ โดยการเลือก $h \in \\langle g \rangle$ และถามหา $1 \le a \le r$ โดยที่ $g^a~(mod~p) = h$

การแลกเปลี่ยนคีย์ Diffie-Hellman

ในปี 1976 Whitfield Diffie และ Martin Hellman ได้เสนอโปรโตคอลการแลกเปลี่ยนคีย์ เพื่อให้สามารถสร้าง shared secret key ผ่านช่องทางการสื่อสารที่ไม่ปลอดภัย secret key นี้สามารถนำไปใช้โดยฝ่ายที่แชร์มันเพื่อการเข้ารหัสแบบสมมาตร อัลกอริทึมนี้พึ่งพา DLP

รูปที่ 1. การแลกเปลี่ยนคีย์ Diffie-Hellman

รายละเอียดทางคณิตศาสตร์ของการแลกเปลี่ยนคีย์ Diffie-Hellman

โดยมี Alice และ Bob เป็นสองฝ่ายที่สื่อสาร โปรโตคอลทำงานดังนี้:

• ขั้นแรก Alice และ Bob ตกลงกันเรื่องจำนวนเฉพาะขนาดใหญ่ $p$ และ primitive root หรือ generator $a$
• จากนั้น Alice เลือก secret exponent $k_A$ แบบสุ่มโดยที่ $1 \le k_A \le p-2$ และคำนวณ $h_A = a^{k_A}~(mod~p)$ โดย $k_A, h_A$ เป็นคีย์ส่วนตัวและสาธารณะของ Alice ตามลำดับ
• ต่อมา Bob เลือก secret exponent $k_B$ แบบสุ่มโดยที่ $1 \le k_B \le p-2$ และคำนวณ $h_B = a^{k_B}~(mod~p)$ โดย $k_B, h_B$ เป็นคีย์ส่วนตัวและสาธารณะของ Bob ตามลำดับ
• จากนั้น Alice ส่ง $h_A$ ให้ Bob และ Bob ส่ง $h_B$ ให้ Alice ผ่านช่องทางที่เชื่อถือได้แต่ไม่จำเป็นต้องปลอดภัย
• จากนั้น Alice ใช้ $h_B$ ที่ได้รับเพื่อคำนวณ shared secret key $\kappa = h_B^{k_A}~(mod~p)$
• สุดท้าย Bob ใช้ $h_A$ ที่ได้รับเพื่อคำนวณ shared secret key $\kappa = h_A^{k_B}~(mod~p)$

ด้วยโปรโตคอลนี้:

• Alice และ Bob ได้รับการรับประกันว่าจะได้ secret key $\kappa$ เดียวกัน เพราะ $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$
• บุคคลที่สามที่ดักจับ $h_A$ หรือ $h_B$ ไม่สามารถสร้าง secret key $\kappa$ ได้ เพราะพวกเขาไม่มีสิทธิ์เข้าถึง $k_B$ หรือ $k_A$ ตามลำดับ
• การดึง $k_A$ หรือ $k_B$ โดยใช้ข้อมูลสาธารณะ $a$, $p$, $h_A$ และ $h_B$ นั้นยากในเชิงการคำนวณ เพราะเทียบเท่ากับการแก้ DLP บน $(\mathbb{Z}_p)^{\times}$

การแสดงโปรโตคอล Diffie-Hellman ด้วย Python

มาดูตัวอย่างง่ายๆ ของโปรโตคอล DH ด้วย Python โดยใช้จำนวนเฉพาะขนาดเล็ก:

หมายเหตุ

ในส่วนนี้เราจะแสดงการคำนวณทางคณิตศาสตร์โดยละเอียดเป็นส่วนหนึ่งของโค้ด Python

ขั้นตอนที่ 1: Alice และ Bob ตกลงกันเรื่อง prime $p$ และ primitive root $a$ เลือก $p=11, a=7$

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

ขั้นตอนที่ 2, 3: Alice เลือก secret exponent $k_A$ และคำนวณ $h_A = a^{k_A}~(mod~p)$ เช่นเดียวกัน Bob เลือก secret exponent $k_B$ และคำนวณ $h_B = a^{k_B}~(mod~p)$

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

ขั้นตอนที่ 4: ทั้งสองฝ่ายประกาศคีย์สาธารณะ $h_A$ และ $h_B$

ขั้นตอนที่ 5, 6: แต่ละฝ่ายรวมคีย์ส่วนตัวของตนกับคีย์สาธารณะของอีกฝ่ายเพื่อสร้าง shared secret key

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

ตอนนี้ Alice และ Bob สามารถใช้ shared secret key สำหรับการเข้ารหัสแบบสมมาตรได้

ความปลอดภัยของการแลกเปลี่ยนคีย์ Diffie-Hellman

ตามที่กล่าวไว้ข้างต้น ความปลอดภัยของ DH ขึ้นอยู่กับความยากในเชิงการคำนวณของการแก้ DLP ด้วย prime ขนาดใหญ่ $p$ ในการใช้งานทั่วไป NIST แนะนำ prime integer ขนาด 2048- หรือ 3072-บิตสำหรับการแลกเปลี่ยนคีย์ DH ซึ่งถือว่าปลอดภัยเพียงพอต่อความพยายามแก้ DLP โดยใช้คอมพิวเตอร์คลาสสิก

การโจมตีแบบ Man-in-the-middle (MITM): ความจริงที่ว่า DH เป็น scheme แบบ interactive โดย shared secret ขึ้นอยู่กับการรวมคีย์ส่วนตัวของฝ่ายหนึ่งกับคีย์สาธารณะของอีกฝ่าย ทำให้มันเสี่ยงต่อการโจมตีที่เรียกว่า Man-in-the-middle (MITM)

รายละเอียดทางคณิตศาสตร์ของความปลอดภัย DH และการโจมตี MITM

ในสถานการณ์นี้ บุคคลที่สาม เช่น Eve ดักจับคีย์สาธารณะ $h_A, h_B$ ระหว่างการส่ง และแทนที่ด้วยคีย์สาธารณะของตน $h_E$ สำหรับแต่ละ $h_A$ และ $h_B$ ก่อนที่จะส่งต่อไปยัง Bob และ Alice ตามลำดับ

จากนั้น แทนที่จะใช้ $h_B$ สร้าง shared secret ของตน Alice จะใช้ $h_E$ แม้ว่าเธอคิดว่าเธอกำลังใช้คีย์สาธารณะของ Bob เช่นเดียวกัน แทนที่จะใช้ $h_A$ สร้าง shared secret ของตน Bob จะใช้ $h_E$ แม้ว่าเขาคิดว่าเขากำลังใช้คีย์สาธารณะของ Alice

เนื่องจาก $h_E$ ถูกใช้สร้าง shared secret ของ Alice (Bob) plain text ที่เข้ารหัสโดย Alice (Bob) จึงสามารถถอดรหัสได้โดย Eve

ดังนั้น การแลกเปลี่ยนคีย์ DH มักถูกใช้ร่วมกับอัลกอริทึมลายเซ็นดิจิทัลเพื่อให้แน่ใจว่าแต่ละฝ่ายใช้คีย์สาธารณะที่ได้รับการรับรองตัวตนในการสร้าง shared secret

Digital Signature Algorithm (DSA)

แม้ว่า cryptosystems ทั่วไปเช่น RSA ให้ฟังก์ชันลายเซ็นดิจิทัล ในปี 1994 NIST ได้นำ scheme ลายเซ็นเฉพาะทางที่อิงจาก modular exponentiation และ discrete logarithm problem มาใช้เป็นมาตรฐานรัฐบาลกลางสำหรับลายเซ็นดิจิทัล scheme นี้ที่รู้จักกันง่ายๆ ว่า Digital Signature Algorithm (DSA) ประกอบด้วยสี่ขั้นตอนที่แตกต่างกัน:

1. การสร้างคีย์:

   คีย์ DSA สร้างจาก:

   • จำนวนเฉพาะ 2 ตัวที่ตอบสนองกฎบางอย่าง
     • $p$ - มักจะ 256 บิต (เราจะเรียกความยาวนี้ว่า $N$)
     • $q$ - มักจะ 3072 บิต (เราจะเรียกความยาวนี้ว่า $L$)
   • ฟังก์ชัน hash เชิงคริปโตกราฟีที่แปลงจาก strings ความยาว $L$ ไปยัง $N$
   • พารามิเตอร์เพิ่มเติม $g$ (ดูรายละเอียดด้านล่าง)

   จากสิ่งนี้เราเลือกตัวเลขสุ่ม $x$ เป็นคีย์ส่วนตัว และสามารถคำนวณคีย์สาธารณะ $y$ ได้

   รายละเอียดทางคณิตศาสตร์ของการสร้างคีย์

   • การสร้างพารามิเตอร์: ในเชิงคณิตศาสตร์ DSA เกี่ยวข้องกับ cyclic subgroup ของ $(\mathbb{Z}_p)^{\times}$ ที่สร้างโดย element $g$ ที่มี prime order q < p ขั้นตอนแรกใน DSA จึงคือการเลือกสอง prime p, q เพื่อตั้งค่าโครงสร้างทางคณิตศาสตร์ที่จำเป็น

     • เลือก prime $q$ ขนาด $N$-บิต
     • เลือก prime $p$ ขนาด $L$-บิต โดยที่ $p-1$ เป็นผลคูณของ $q$ การเลือก $p$ ระบุ group $(\mathbb{Z}_p)^{\times}$
     • เลือกจำนวนเต็ม $1 < h < p-1$ แบบสุ่มและคำนวณ $g = h^{(p-1)/q}~mod~p$ ถ้า $g=1$ ซึ่งเกิดขึ้นน้อยมาก ให้ลอง h อื่น
     • ยืนยันว่า $g^q~mod~p = 1$ โดย g เป็น generator ของ cyclic subgroup $\langle g \rangle$ ของ $(\mathbb{Z}_p)^{\times}$ ที่มี prime order q

     พารามิเตอร์ $(q, p, g)$ ระบุ instance ของอัลกอริทึมและเป็นข้อมูลสาธารณะ โดยทั่วไป $N \sim 256$ และ $L \sim 3072$ ในการใช้งานจริง

     โปรโตคอลยังต้องการฟังก์ชัน hash เชิงคริปโตกราฟี $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ ที่แปลง binary $L$-bit strings ไปยัง $N$-bit strings เช่น SHA-256

   • การสร้าง key-pair: ผู้ลงนามต้องสร้าง key pair ในฝั่งของตน

     • เลือก random secret integer $x \in \{1,2...q-1\}$ โดย $x$ คือคีย์ส่วนตัว
     • สร้าง $y = g^{x}~mod~p$ โดย $y$ คือคีย์สาธารณะของผู้ลงนาม

2. การกระจายคีย์:

   ข้อมูลต่อไปนี้จะถูกแชร์กับทุกคนที่ต้องการตรวจสอบลายเซ็น

   • พารามิเตอร์ที่ใช้ $(p,q,g)$ ซึ่งอธิบายอัลกอริทึม
   • ฟังก์ชัน hash $H$
   • คีย์สาธารณะ $y$

3. การลงนาม:

   • ผู้ลงนามสามารถลงนามข้อความ $m$ ได้ ลายเซ็นที่ได้คือ $(r,s)$
   • ข้อความและลายเซ็นทั้งสองตอนนี้ถูกส่งไปยังผู้รับ

   รายละเอียดทางคณิตศาสตร์ของการลงนามข้อความ

   ผู้ลงนามลงนามข้อความ $m$ ดังนี้:

   • เลือก secret integer k แบบสุ่มจาก $\{1,2...q-1\}$
   • คำนวณ $r = (g^k~mod~p)~mod~q$ ในกรณีที่หายากเมื่อ $r=0$ ให้ลอง random k อื่น
   • คำนวณ $s = (k^{-1} (H(m) + xr))~mod~q$ ในกรณีที่หายากถ้า $s=0$ ให้ลอง random k อื่น
   • ลายเซ็นคือ tuple $(r, s)$
   • ผู้ลงนามส่งข้อความ $m$ รวมถึงลายเซ็น $(r,s)$ ไปยังผู้ตรวจสอบ

   เนื่องจากทั้ง $r, s$ เป็นจำนวนเต็ม modulo $q$ ขนาดลายเซ็นจึงอยู่ในระดับ $N$-บิต ไม่ใช่ $L$-บิตที่ยาวกว่า

4. การตรวจสอบ:

   ผู้รับต้องการยืนยันความถูกต้องของผู้ส่ง พวกเขามีสิทธิ์เข้าถึงข้อมูลสาธารณะ $(q, p, g, H, y, (r,s), m)$ พวกเขาสามารถดำเนินการคำนวณที่พิสูจน์ว่าผู้ส่งมีสิทธิ์เข้าถึงคีย์ส่วนตัว $x$

   และพยายามยืนยันว่าผู้ลงนามคือบุคคลที่มีสิทธิ์เข้าถึงคีย์ส่วนตัว $x$

   รายละเอียดทางคณิตศาสตร์ของ DSA verification scheme

   • ยืนยันว่า $0 \lt r \lt q$ และ $0 \lt s \lt q$ กล่าวคือ $r, s$ เป็น valid modulo~q integers
   • คำนวณ $w = s^{-1}~mod~q$
   • คำนวณ $u_1 = H(m)w~mod~q$
   • คำนวณ $u_2 = rw~mod~q$
   • คำนวณ $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$
   • ลายเซ็นได้รับการยืนยันถ้า $v = r$

   สำหรับลายเซ็นที่ถูกต้อง ความถูกต้องของอัลกอริทึม DSA สามารถแสดงได้ง่ายดังนี้:

   • ในฝั่งผู้ลงนาม: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • พิจารณาด้านขวาของความเท่ากันหลัง ผู้ตรวจสอบสามารถคำนวณ $s^{-1}, H(m)$ เพราะ $s, q, m, H$ เป็นข้อมูลสาธารณะ
   • ดังนั้น ผู้ตรวจสอบคำนวณ $w = s^{-1}~mod~q$ และ $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$
   • ผู้ตรวจสอบยังคำนวณ $u_2 = rw~mod~q = rs^{-1}~mod~q$ เนื่องจาก $r$ ก็เป็นข้อมูลสาธารณะเช่นกัน
   • โปรดทราบว่า $k = (u_1 + xu_2)~mod~q$
   • อย่างไรก็ตาม ผู้ตรวจสอบไม่มีสิทธิ์เข้าถึง $x$ เพราะมันคือคีย์ส่วนตัวของผู้ลงนาม ดังนั้น $k$ เองจึงไม่สามารถคำนวณโดยตรงได้ - scheme แทนที่จะอาศัยความจริงที่ว่าแม้ผู้ตรวจสอบจะไม่สามารถคำนวณ $k$ ได้ ด้วยผู้ลงนามที่ถูกต้อง ผู้ตรวจสอบควรสามารถคำนวณ $(g^k~mod~p)~mod~q = r$ ขึ้นมาใหม่ได้ด้วยความช่วยเหลือของคีย์สาธารณะ $y = g^{x}~mod~p$ ของผู้ลงนาม
   • ดังนั้น ผู้ตรวจสอบคำนวณ $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$
   • ความเท่ากันสุดท้ายเป็นไปได้เพราะ $g$ มี order $q$ และพิสูจน์ $v = r$ สำหรับลายเซ็นที่ถูกต้อง

การแสดง DSA ด้วย Python

ในตัวอย่างนี้ เราจะใช้จำนวนเฉพาะขนาดเล็กเพื่อแสดงกระบวนการ DSA ในสถานการณ์ที่ Alice ส่งข้อความที่ลงนามแล้วให้ Bob เราจะใช้จำนวนเต็มขนาดเล็กในตัวอย่างนี้ สถานการณ์ในโลกจริงจะใช้จำนวนเฉพาะขนาดใหญ่กว่ามากในระดับ 2048-3072 บิต

หมายเหตุ

คุณสามารถลองรันตัวอย่างนี้ซ้ำด้วยค่าต่างๆ เพื่อดูว่าอัลกอริทึมทำงานอย่างไร แต่ให้แน่ใจว่าเริ่มต้นรันจากเซลล์แรกในส่วนนี้

เราเริ่มต้นด้วยการนำเข้าไลบรารีที่จำเป็นและเลือกพารามิเตอร์ของเรา พารามิเตอร์จำนวนเต็ม $p$, $q$, $g$ เป็นข้อมูลสาธารณะ และต้องตอบสนองกฎต่อไปนี้:

• $p$, $q$ ทั้งคู่เป็นจำนวนเฉพาะ
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

ต่อมาผู้ลงนาม Alice สร้างคีย์ส่วนตัวของตน

คีย์ส่วนตัว k (alice-private-key ในโค้ด python) ต้องตอบสนอง:

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alice เก็บคีย์ส่วนตัวของเธอเป็นความลับ

ต่อมา Alice คำนวณคีย์สาธารณะโดยใช้ modular exponentiation การกลับขั้นตอนนี้เพื่อกู้คืนคีย์ส่วนตัวเป็น instance ของ DLP จึงยากที่จะคำนวณบนคอมพิวเตอร์คลาสสิกเมื่อใช้ prime ขนาดใหญ่

จากคำอธิบายทางคณิตศาสตร์ข้างต้น เราทราบว่าสามารถคำนวณได้โดยใช้สูตร:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

เหมือนเดิม Alice ทำให้คีย์สาธารณะของเธอสามารถเข้าถึงได้ผ่านช่องทางที่ไม่จำเป็นต้องลับ

ตอนนี้ Alice สามารถลงนามข้อความได้

สำหรับ digital signature scheme เราต้องสร้าง hash $H(m)$ ของข้อความ $m$ ที่ต้องการลงนาม

สมมติว่า Alice และ Bob ตกลงใช้ hashing algorithm เฉพาะที่มีความยาว hash $N$ เท่ากับจำนวนบิตใน $q$ ในตัวอย่างง่ายๆ นี้ เราจะจำกัด outputs ของ mock hash function ของเราด้วย $q$ ฟังก์ชัน hash ที่นี่เป็นแบบ trivial เพียงสร้างจำนวนเต็มสุ่ม

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

ต่อมา Alice ต้องสร้าง random per-message secret number $k$ รวมถึง multiplicative inverse ของมัน modulo $q$ เพื่อคำนวณลายเซ็น

สามารถใช้อัลกอริทึม brute-force ง่ายๆ เพื่อคำนวณ modular inverse อย่างไรก็ตาม ดีกว่าที่จะใช้ฟังก์ชัน Python ในตัว pow ตามที่แสดงด้านล่าง

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

ตอนนี้ Alice สามารถคำนวณลายเซ็นได้

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

โปรดทราบว่ามีเงื่อนไขบางอย่างที่จะต้องให้เราเลือก $k$ ที่แตกต่างในกรณีที่ $r$ หรือ $s$ คำนวณออกมาเป็น $0$ ในกรณีนี้เราจะสร้างค่าใหม่และทำซ้ำ

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice ประกาศข้อความและลายเซ็นของเธอไปยังผู้รับหรือผู้ตรวจสอบซึ่งก็คือ Bob

Bob ได้รับคีย์สาธารณะของ Alice ก่อนหน้านี้และตอนนี้สามารถตรวจสอบลายเซ็นเพื่อรับรองตัวตนข้อความของเธอได้

เพื่อทำสิ่งนี้ เขาทำการตรวจสอบบางอย่าง จากนั้นสร้าง hash ของข้อความที่ Alice ประกาศขึ้นใหม่และคำนวณปริมาณเสริม $w, u_1, u_2$ และ $v$

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

สุดท้าย Bob ตรวจสอบว่า $v$ เท่ากับ $r$ หรือไม่ ถ้าเท่ากัน ลายเซ็นจะได้รับการยืนยัน

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

ความปลอดภัยของ DSA

ด้วยการคำนวณแบบคลาสสิก ความปลอดภัยของ DSA สามารถได้รับผลกระทบจากหลายปัจจัย:

1. ขนาดคีย์: เหมือนเสมอ ขนาดคีย์ให้การป้องกันพื้นฐานต่อการโจมตีแบบ brute force การใช้งานสมัยใหม่ที่ใช้ DSA ใช้ขนาดคีย์อย่างน้อย 2048 บิต

2. คุณภาพของ $k$: ใน DSA แต่ละลายเซ็นต้องการค่า $k$ ที่ไม่ซ้ำกัน สุ่ม และเป็นความลับ (ดูข้างต้น) ความเป็นเอกลักษณ์ entropy และความลับของ $k$ มีความสำคัญมาก และจุดอ่อนในด้านใดด้านหนึ่งอาจทำให้คีย์ส่วนตัว $x$ ถูกเปิดเผย ตัวสร้างเลขสุ่มที่ใช้สร้าง $k$ ต้องปลอดภัยด้วยตัวเอง

3. ความแข็งแกร่งของฟังก์ชัน hash: เนื่องจาก DSA ใช้ฟังก์ชัน hash เป็นส่วนหนึ่งของกระบวนการสร้างและตรวจสอบลายเซ็น ฟังก์ชัน hash ที่อ่อนแอจึงอาจส่งผลกระทบต่อความปลอดภัยของลายเซ็นดิจิทัล ตัวอย่างเช่น การใช้ SHA-1 กับ DSA ถูกเลิกใช้แล้ว และแนะนำให้ใช้ SHA-2 หรือสูงกว่า

นอกจากนี้ การ implement DSA ที่แข็งแกร่งควรป้องกันการโจมตีประเภทอื่นที่มุ่งเป้าไปที่การเข้ารหัสแบบอสมมาตรตามที่อธิบายไว้ก่อนหน้า

การแลกเปลี่ยนคีย์ที่รับรองตัวตนด้วย Diffie-Hellman และ DSA

โปรโตคอลความปลอดภัยเครือข่ายสมัยใหม่ เช่น Transport Layer Security (TLS) และอื่นๆ อีกมาก เกี่ยวข้องกับการรวมฟังก์ชันการแลกเปลี่ยนคีย์และการรับรองตัวตน ในบริบทของ Diffie-Hellman การรับรองตัวตนจำเป็นเพื่อป้องกันการโจมตีแบบ MITM ในเซลล์โค้ดต่อไปนี้ เราแสดงตัวอย่างที่ Alice และ Bob ทำการแลกเปลี่ยนคีย์ที่รับรองตัวตนโดยการรวมโปรโตคอล Diffie-Hellman และ DSA สำหรับสิ่งนี้ เราจะใช้ไลบรารี Python cryptography

รูปที่ 2. การแลกเปลี่ยนคีย์ที่รับรองตัวตนด้วย Diffie-Hellman และ DSA ขั้นแรก Alice และ Bob ตกลงกันเรื่องพารามิเตอร์ DH และสร้างชุด DH public-private key pairs

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

คีย์สาธารณะ DH จะถูกประกาศ ต่อมา ทั้ง Alice และ Bob ต่างสร้าง key pair แยกกันสำหรับใช้กับ DSA คีย์เหล่านี้จะถูกใช้เพื่อลงนามคีย์สาธารณะ DH ที่จะแลกเปลี่ยน

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice ลงนามคีย์สาธารณะ DH ของเธอโดยใช้คีย์ส่วนตัว DSA ของเธอ

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

เช่นเดียวกัน Bob ลงนามคีย์สาธารณะ DH ของเขาโดยใช้คีย์ส่วนตัว DSA ของเขา

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

คีย์สาธารณะ DH และลายเซ็นที่สอดคล้องกันตอนนี้ถูกประกาศโดยทั้ง Alice และ Bob เมื่อได้รับคีย์สาธารณะและลายเซ็นของคู่สนทนาแล้ว แต่ละฝ่ายจะตรวจสอบว่าลายเซ็นถูกต้อง วิธีนี้สามารถป้องกันการโจมตีแบบ MITM ได้ เพราะ Alice ยืนยันได้ว่าคีย์สาธารณะ DH ของ Bob ถูกลงนามโดย Bob จริงๆ และในทางกลับกัน

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

หลังจากตรวจสอบลายเซ็นแล้ว Alice และ Bob สร้าง shared secret ซึ่งทำให้การแลกเปลี่ยนคีย์เสร็จสมบูรณ์

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

ตัวเลือก เพื่อความปลอดภัยเพิ่มเติม Alice และ Bob สามารถใช้ key derivation function เฉพาะทางเช่น HKDF เพื่อสร้าง symmetric key ที่ปลอดภัยยิ่งขึ้นจาก shared secret โดยใช้เทคนิค key stretching

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

การทำลาย Diffie-Hellman และ DSA

ทั้งโปรโตคอล Diffie-Hellman (DH) และ DSA เกี่ยวข้องกับการสร้างคีย์สาธารณะในรูปแบบ $y = g^{x}~mod~p$ โดยที่คีย์ส่วนตัว $x$ คือ discrete logarithm

ผู้โจมตีที่สามารถแก้ instance ของ DLP ได้สามารถเปิดเผยคีย์ส่วนตัวของฝ่ายใดฝ่ายหนึ่ง และโดยการรวมกับคีย์สาธารณะของฝ่ายที่สอง สามารถเข้าถึง shared secret ได้ ในกรณีของ DSA ผู้โจมตีที่สามารถแก้ DLP สามารถกู้คืนคีย์ส่วนตัวของผู้ลงนาม ทำให้ premise พื้นฐานของลายเซ็นดิจิทัลเป็นโมฆะ

บนระบบคอมพิวเตอร์คลาสสิก เชื่อกันว่า DLP ไม่มีคำตอบ polynomial-time แต่ตามที่ Peter Shor แสดงใน paper ดั้งเดิมปี 1994 อัลกอริทึม Shor ยังแก้ DLP ใน polynomial-time บนคอมพิวเตอร์ควอนตัมด้วย

อัลกอริทึม Shor และ discrete logarithm problem

อัลกอริทึม Shor สามารถแก้ discrete logarithm problem ใน polynomial time ได้ มันบรรลุประสิทธิภาพนี้เป็นหลักโดยการใช้อัลกอริทึมควอนตัมที่สามารถหาคาบของฟังก์ชันที่ขึ้นอยู่กับ input ของปัญหา ซึ่งจากนั้นถูกรวมกับการดำเนินการทั่วไปที่มีประสิทธิภาพมากขึ้น

รายละเอียดทางคณิตศาสตร์ของอัลกอริทึม Shor

อัลกอริทึม Shor ให้คำตอบที่มีประสิทธิภาพสำหรับ DLP โดยการแมปมันไปยังปัญหาทั่วไปยิ่งขึ้นใน group theory ที่เรียกว่า hidden subgroup problem (HSP)

ใน HSP หนึ่งได้รับ algebraic group $G$ และฟังก์ชัน $f: G \rightarrow X$ จาก $G$ ไปยังเซต $X$ บางเซต โดยที่ $f$ คงที่บน coset แต่ละ coset ของ subgroup $H$ บางตัวของ $G$ (และแตกต่างกันบน cosets ที่ต่างกัน) จากนั้น งานคือการกำหนด $H$ เป็นที่ทราบกันว่าคอมพิวเตอร์ควอนตัมสามารถแก้ HSP บน finite Abelian groups ใน polynomial time ในแง่ $log~|G|$ โดยที่ $|G|$ คือ group order

ในกรณีของ integer DLP ที่กล่าวถึงในบทเรียนนี้ การแมปไปยัง HSP มีดังนี้:

• ให้ $p$ เป็นจำนวนเฉพาะและพิจารณา DLP ที่กำหนดโดย $y = g^r~mod~p$ โดยที่ $g$ เป็น generator ของ $(\mathbb{Z}_p)^{\times}$ เนื่องจาก $g^{p-1} \equiv 1~mod~p$ $g$ จึงมี order $p-1$
• เลือก $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ โดยที่ $\mathbb{Z}_{p-1}$ คือ group ของจำนวนเต็ม modulo $(p-1)$
• เลือก $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ ที่กำหนดเป็น $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$
• kernel ของ $f$ จึงเป็น subgroup $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$
• $f$ คงที่บน cosets $(\delta, 0) + H_0$ และ "ซ่อน" subgroup $H_0$ ตั้ง HSP ขึ้น

เมื่อกำหนดข้างต้นแล้ว อัลกอริทึมควอนตัม Shor สำหรับ integer DLP ใช้ quantum oracle เพื่อประเมินฟังก์ชัน $f$ บน state ที่แทน uniform superposition บน $G$ จากนั้นใช้ quantum Fourier transform และการวัดด้วย phase estimation เพื่อสร้าง quantum states ที่ช่วยให้ระบุ generator $(r, 1)$ ของ $H_0$ ได้ จากสิ่งนี้ $r$ ซึ่งเป็น discrete logarithm ที่สนใจ สามารถดึงออกมาได้

Paper ดั้งเดิมของ Shor มีคำอธิบายโดยละเอียดของอัลกอริทึม

Elliptic curve cryptography

Elliptic curve cryptography (ECC) ที่อิงจากคณิตศาสตร์ของ elliptic curves ให้แนวทางที่ทรงพลังสำหรับการเข้ารหัสแบบอสมมาตร ECC เป็นที่ทราบกันว่าให้ระดับความปลอดภัยที่คล้ายกับวิธีอื่นเช่น RSA แต่ด้วยคีย์ที่สั้นกว่า ทำให้มีประสิทธิภาพมากกว่าและเหมาะสมเป็นพิเศษสำหรับระบบที่มีทรัพยากรจำกัด เช่น embedded systems และอุปกรณ์มือถือ ซึ่ง ประหยัดพื้นที่จัดเก็บและการคำนวณจากขนาดคีย์ที่เล็กกว่า เป็นที่ต้องการอย่างมาก

หลักการพื้นฐานของ elliptic curve cryptography

elliptic curve โดยทั่วไปอยู่ในรูปแบบ $y^2 = x^3 + ax + b$ ด้วยคุณสมบัติที่น่าสนใจบางอย่าง

• มันสมมาตรในแนวนอน ดังนั้นสำหรับจุดใดๆ $(x,y)$ บนเส้นโค้ง การสะท้อน $(x,-y)$ ก็อยู่บนเส้นโค้งด้วย
• เส้นตรงที่ไม่แนวตั้งใดๆ จะตัดเส้นโค้งที่จุดไม่เกินสามจุด

รูปที่ 1. การดำเนินการบวกและ point doubling บน elliptic curve Facet 1 กำหนด P + Q = -R. Facet 2 แสดง point doubling 2Q = -P. Facet 3 กำหนด additive inverse ของจุดเป็นการสะท้อนผ่านแกน x กล่าวคือ P = -Q

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

หลักการทางคณิตศาสตร์ของ elliptic curve cryptography

elliptic curve บน algebraic field $K$ ถูกกำหนดโดยสมการคณิตศาสตร์ โดยทั่วไปในรูปแบบ $y^2 = x^3 + ax + b$ ด้วย coefficients $a, b \in K$ และอธิบายจุด $(x, y) \in K \otimes K$ โดยมีข้อกำหนดเพิ่มเติมว่าเส้นโค้งไม่มีจุดหักหรือตัดเอง

คุณสมบัติของ elliptic curves ช่วยให้สามารถกำหนดการดำเนินการ "บวก" และ "scalar multiplication" ที่เกี่ยวข้องกับจุดบนเส้นโค้งได้

การบวก: ถ้า $P$ และ $Q$ เป็นสองจุดบน elliptic curve แล้ว $P + Q$ อธิบายจุดที่สามที่ไม่ซ้ำกันที่ระบุดังนี้: วาดเส้นที่ตัดผ่าน $P$ และ $Q$ และหาจุดที่สาม $R$ ที่เส้นตัดเส้นโค้งอีกครั้ง จากนั้นเรากำหนด $P + Q = −R$ ซึ่งเป็นจุดตรงข้ามกับ $R$ สะท้อนผ่านแกน $x$ (ดูรูปด้านล่าง) เมื่อเส้นผ่าน $P, Q$ ไม่ตัดเส้นโค้งที่ $(x, y)$ ที่มีขอบเขต เราบอกว่ามันตัดเส้นโค้งที่จุดที่อนันต์ $\mathbf{O}$

Elliptic curve addition ตอบสนองคุณสมบัติ algebraic group โดยมีจุดที่อนันต์เป็น additive identity

Doubling และ scalar multiplication: การดำเนินการ point doubling ซึ่งสอดคล้องกับ scalar multiplication ด้วย $2$ ได้จากการตั้ง $P = Q$ ในการดำเนินการบวก และในเชิงกราฟิกเกี่ยวข้องกับ tangent line ที่ $P$ การ scalar multiplication ทั่วไปด้วยจำนวนเต็ม $n$ ที่กำหนดเป็น $nP = P + P + ...~n$ ครั้ง ได้จากการ doubling และบวกซ้ำกัน

Elliptic curve discrete logarithm problem

elliptic curve discrete logarithm problem (ECDLP) มีความคล้ายคลึงกับ discrete logarithm problem ที่กล่าวถึงก่อนหน้ามาก โดยอิงจากความท้าทายของการหาตัวประกอบ

การดำเนินการ scalar multiplication บน elliptic curves ช่วยให้สามารถกำหนด elliptic curve discrete logarithm problem ได้:

กำหนดจุด $P, Q$ บน elliptic curve โดยที่ $Q = nP$ หา $n$

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

คำอธิบายทางคณิตศาสตร์ของ ECDLP

Elliptic curve cryptography ส่วนใหญ่อิงจาก ECDLP ที่กำหนดบน algebraic finite fields บางชนิด ในปี 1999 NIST แนะนำ finite fields สิบชนิดสำหรับใช้ใน ECC ได้แก่:

• prime fields ห้าชนิด $\mathbb {F} _{p}$ สำหรับ primes $p$ ขนาด $\{192, 224, 256, 384, 521\}$ บิต
• binary fields ห้าชนิด $\mathbb {F} _{2^{n}}$ สำหรับ $n \in \{163, 233, 283, 409, 571\}$

ด้วยการตั้งค่าข้างต้น ECC-based asymmetric key cryptosystem ในกรณีของ prime fields อาจระบุได้ดังนี้:

• เลือก $p$ จากรายการที่ NIST แนะนำเพื่อระบุ $\mathbb {F} _{p}$

• เลือกพารามิเตอร์ $a, b$ ของ elliptic curve

• เลือก base point $G$ ที่ "สร้าง" cyclic subgroup บนเส้นโค้งที่มี order $n$ กล่าวคือ จำนวนเต็มที่น้อยที่สุดโดยที่ $nG = \mathbf{O}$

• คำนวณ cofactor $h = |E(\mathbb {F} _{p})|/n$ โดยที่ $|E(\mathbb {F} _{p})|$ คือจำนวนจุดบนเส้นโค้ง โดยทั่วไป $h$ เป็นจำนวนเต็มเล็กๆ

• domain parameters $(p, a, b, G, n, h)$ ช่วยให้สามารถระบุ asymmetric keys ได้ดังนี้:

  • คีย์ส่วนตัวคือจำนวนเต็ม $d$ ที่เลือกแบบสุ่ม ด้วยจำนวนบิตมากเท่ากับ prime $p$ ควรเก็บเป็นความลับ
  • คีย์สาธารณะคือผลของการ "คูณ" base point $G$ ด้วยคีย์ส่วนตัว $d$ มักแสดงเป็น $Q = dG$

การกู้คืน $d$ เทียบเท่ากับการแก้ ECDLP ซึ่งสมมติกันว่าแก้ได้ยากสำหรับ $d$ ขนาดใหญ่ ECDLP จึงเป็นพื้นฐานสำหรับ key exchange และ digital signature schemes ในแบบที่เทียบเคียงโดยตรงกับ Diffie-Hellman และ DSA schemes ที่กำหนดบน $(\mathbb{Z}_p)^{\times}$ ที่กล่าวถึงก่อนหน้า

การแลกเปลี่ยนคีย์ด้วย ECC

การใช้งานหลักอย่างหนึ่งของ ECC คือในโปรโตคอลการแลกเปลี่ยนคีย์ที่เรียกว่า elliptic curve Diffie-Hellman (ECDH) ใน ECDH แต่ละฝ่ายสร้าง private-public key pair แล้วแลกเปลี่ยนคีย์สาธารณะกัน แต่ละฝ่ายจากนั้นใช้คีย์ส่วนตัวของตนและคีย์สาธารณะของอีกฝ่ายเพื่อคำนวณ shared secret ซึ่งสามารถใช้เป็นคีย์สำหรับการเข้ารหัสแบบสมมาตรได้

แม้ว่าการดำเนินการบวกจุดบน elliptic curve และการดึงคีย์สาธารณะจากคีย์ส่วนตัวค่อนข้างง่าย แต่การย้อนกลับกระบวนการและดึงคีย์ส่วนตัวจากคีย์สาธารณะนั้นไม่สามารถทำได้ในเชิงการคำนวณ พฤติกรรม "one-way" นี้ให้ความปลอดภัยของการแลกเปลี่ยนคีย์ ECDH

ที่นี่ เราจะแสดงตัวอย่างวิธีที่อาจทำการแลกเปลี่ยนคีย์ ECDH โดยใช้ Python และไลบรารี cryptography

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

ลายเซ็นดิจิทัลด้วย ECC

ECC ยังสามารถใช้สร้างลายเซ็นดิจิทัลโดยใช้ Elliptic Curve Digital Signature Algorithm (ECDSA) ใน ECDSA ผู้ลงนามสร้างลายเซ็นโดยใช้คีย์ส่วนตัวของตน และคนอื่นสามารถตรวจสอบลายเซ็นโดยใช้คีย์สาธารณะของผู้ลงนาม เหมือนกับ ECDH ความปลอดภัยของ ECDSA ขึ้นอยู่กับ ECDLP ไม่สามารถทำได้ในเชิงการคำนวณสำหรับใครก็ตามที่จะปลอมแปลงลายเซ็นโดยไม่มีสิทธิ์เข้าถึงคีย์ส่วนตัวของผู้ลงนาม

ต่อไปนี้คือตัวอย่างธุรกรรม sign-and-verify ง่ายๆ โดยใช้ ECDSA กับ Python และ cryptography

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

ในโค้ดข้างต้น หากแก้ไขข้อความหลังจากที่ได้ลงนามแล้ว การตรวจสอบจะล้มเหลว ให้การรับประกันความถูกต้องและความสมบูรณ์ของข้อความ

การทำลาย ECDH และ ECDSA

ในทำนองเดียวกับ integer discrete logarithm problem ECDLP กลายเป็นปัญหายากบนคอมพิวเตอร์คลาสสิก แต่มีคำตอบที่มีประสิทธิภาพบนคอมพิวเตอร์ควอนตัมอีกครั้งผ่านอัลกอริทึม Shor เราแนะนำให้คุณอ่านวรรณกรรมล่าสุดสำหรับการอภิปรายที่เกี่ยวข้องกับ การทำให้อัลกอริทึม Shor เป็นกรณีทั่วไปสำหรับ ECDLP

สรุป

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

จากนั้นเราดู RSA cryptosystem ซึ่งตั้งแต่ทศวรรษ 1970 พิสูจน์ว่ามีคุณค่าอย่างมากในการรักษาความปลอดภัยการสื่อสารดิจิทัลสมัยใหม่โดยการรองรับการแลกเปลี่ยนคีย์และลายเซ็นดิจิทัลภายใน framework ที่ง่ายและหลากหลาย ความปลอดภัยเชิงคริปโตกราฟีของ RSA เมื่อเทียบกับการคำนวณคลาสสิกขึ้นอยู่กับความยากของการแยกตัวประกอบจำนวนเต็มขนาดใหญ่ และต้องการขนาดคีย์ในช่วง 2048 บิตเพื่อให้แน่ใจว่าจำนวนเต็มที่ใช้ในการใช้งานจริงมีขนาดใหญ่พอที่จะต้านทานการแยกตัวประกอบ

จากนั้นเราดู Diffie-Hellman (DH) key exchange และ Digital Signature Algorithm (DSA) ความปลอดภัยของ schemes เหล่านี้ขึ้นอยู่กับ integer discrete logarithm (DLP) problem ซึ่ง private key ยากที่จะดึงออกมาจาก public key ในเชิงการคำนวณ โดยไม่มีคำตอบ polynomial time บนคอมพิวเตอร์คลาสสิก การใช้คีย์แบบสุ่มและไม่ซ้ำกันให้ความปลอดภัยเพิ่มเติมจากการโจมตี ทั้งรูปแบบ integer finite field และ elliptic curve ของโปรโตคอล DH และ DSA ยังคงพบการใช้งานอย่างแพร่หลายในโปรโตคอลการสื่อสารดิจิทัลสมัยใหม่หลายอย่างเช่น TLS, SSH และอื่นๆ

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

อัลกอริทึมทั้งหมดเหล่านี้มีความเสี่ยงต่อการโจมตีจากอัลกอริทึมควอนตัม เนื่องจากสามารถพัฒนาคำตอบเพื่อแก้ปัญหาทางคณิตศาสตร์ที่เป็นพื้นฐานในการออกแบบของพวกมันได้ ตัวอย่างหนึ่งคืออัลกอริทึม Shor ดังนั้นพวกมันจึงจำเป็นต้องถูกแทนที่ด้วย asymmetric cryptosystems ที่ปลอดภัยจากควอนตัม ซึ่งทนทานต่อการโจมตีจากควอนตัมมากกว่า ในขณะที่ยังคงปลอดภัยจากอัลกอริทึมคลาสสิก ปัญหาทางคณิตศาสตร์ที่พวกมันพึ่งพาสามารถแก้ได้อย่างมีประสิทธิภาพโดยคอมพิวเตอร์ควอนตัม จึงจำเป็นต้องพัฒนา asymmetric cryptosystems ที่ปลอดภัยจากควอนตัมที่สามารถรับมือการโจมตีควอนตัมได้พร้อมรักษาความปลอดภัยคลาสสิก

บทเรียนในอนาคตจะดู quantum-safe cryptosystems และหารือเกี่ยวกับแนวทางที่จำเป็นในการรักษาความปลอดภัยเชิงคริปโตกราฟี