ถอดรหัสลับ RSA: เมื่อตัวประกอบเฉพาะอยู่ใกล้กันเกินไป

ถอดรหัสลับ RSA: เมื่อตัวประกอบเฉพาะอยู่ใกล้กันเกินไป

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

แต่ถ้าเกิดว่า p และ q ไม่ได้ห่างไกลกันอย่างที่ควรจะเป็นล่ะ? ความลับที่ซ่อนอยู่ในสมการอาจถูกเปิดเผยได้ง่ายกว่าที่คิด

นี่คือเรื่องราวการเจาะระบบ RSA ที่ใช้หลักการทางคณิตศาสตร์ง่าย ๆ แต่ทรงพลัง

ความเปราะบางของ RSA: เมื่อตัวประกอบแฝดคู่อยู่ใกล้กัน

การทำงานของ RSA เริ่มต้นจากกุญแจสาธารณะ (public key) ที่ประกอบด้วย n (โมดูลัส) และ e (เลขชี้กำลังสาธารณะ) โดยที่ n คือผลคูณของจำนวนเฉพาะขนาดใหญ่สองตัวคือ p และ q ซึ่งเป็นความลับ และ c คือข้อมูลที่ถูกเข้ารหัสแล้ว

หัวใจของความปลอดภัยคือการที่ไม่มีใครสามารถหาค่า p และ q จาก n ได้ภายในเวลาที่เหมาะสม

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

ลองจินตนาการว่า p และ q เปรียบเหมือนฝาแฝดที่เดินคลอเคลียกัน แทนที่จะแยกย้ายไปคนละทิศละทาง

นั่นทำให้การค้นหาพวกมันง่ายขึ้นมาก

การโจมตีด้วยวิธี Fermat’s Factorization

เมื่อทราบว่า p และ q อยู่ใกล้กัน วิธี Fermat’s Factorization ก็กลายเป็นเครื่องมือสำคัญในการค้นหาพวกมัน หลักการพื้นฐานคือการแปลง n ให้อยู่ในรูปผลต่างของกำลังสอง (difference of two squares)

สมมติให้ n = x² – y²

เราสามารถจัดรูปใหม่เป็น n = (x – y)(x + y)

ซึ่งจากคุณสมบัติของ RSA เราก็ทราบอยู่แล้วว่า n = p * q

ดังนั้น p = x – y และ q = x + y นั่นเอง

แนวคิดคือการเริ่มต้นค้นหาค่า x จากจำนวนเต็มที่มากกว่าหรือเท่ากับ sqrt(n) เล็กน้อย แล้วค่อย ๆ เพิ่มค่า x ขึ้นไปทีละน้อย

ในแต่ละรอบที่เพิ่มค่า x ขึ้นมา จะคำนวณค่า x² – n

จากนั้นตรวจสอบว่า x² – n เป็นกำลังสองสมบูรณ์หรือไม่ ถ้าใช่ แสดงว่าเราเจอค่า y² แล้ว

เมื่อพบค่า y ก็จะได้ p = x – y และ q = x + y ในทันที

ขั้นตอนสู่การถอดรหัส

เมื่อได้ค่า p และ q มาแล้ว การถอดรหัส RSA ก็ไม่ใช่เรื่องยากอีกต่อไป ขั้นตอนดำเนินการมีดังนี้

อันดับแรก เมื่อมี p และ q ก็สามารถคำนวณค่า phi(n) หรือ Euler’s totient function ได้ทันที ซึ่งเท่ากับ (p – 1)(q – 1)

จากนั้น ต้องคำนวณหาค่า d ซึ่งเป็นเลขชี้กำลังส่วนตัว (private exponent) โดย d คือค่าผกผันโมดูลาร์ (modular inverse) ของ e ภายใต้โมดูลัส phi(n)

เมื่อได้ d มาครบสมบูรณ์ ขั้นตอนสุดท้ายคือการถอดรหัสข้อความ c ที่ถูกเข้ารหัสไว้

ทำได้โดยใช้สมการ m = c^d mod n ซึ่งจะทำให้ได้ข้อความต้นฉบับ m กลับคืนมา

เรื่องราวนี้ตอกย้ำความสำคัญของการเลือกค่า p และ q ในการสร้างกุญแจ RSA ว่าจะต้องสุ่มและมีค่าที่ห่างกันอย่างเหมาะสม เพื่อรักษาความแข็งแกร่งและป้องกันการโจมตีจากช่องโหว่ที่ดูเหมือนเล็กน้อยแต่ส่งผลมหาศาลเช่นนี้