ทำซ้ำการคำนวณลายเซ็น RSA 1024 บิตใน 3 วัน 22 ชั่วโมง มนุษย์เป็นผู้อนุมัติ

เอกสาร working paper ของกูเกิล ดีปไมด์ระบุว่า งานนี้เป็นการทดลองทำซ้ำกรณี RSA 1024 บิตที่มีการศึกษาก่อนหน้า เอเจนต์กำกับดูแลรับผิดชอบการออกแบบ การจัดสรรงบประมาณการคำนวณ และตรวจสอบผลในแต่ละขั้น ส่วนเอเจนต์ปฏิบัติการเขียนโค้ด ทำงานแบบกระจาย และแก้ไขข้อผิดพลาด นอกจากนี้ยังมีเอเจนต์ช่วยงานอีกตัวในขั้นตอนหนึ่งของการคำนวณพีชคณิตเชิงเส้น

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

เอเจนต์เขียนโค้ดใหม่ประมาณ 33,500 บรรทัด และทำการทดลองแบบกระจาย 336 ครั้ง งานนี้ใช้ CPU ได้สูงสุดประมาณ 300,000 คอร์ และ GPU 16 ตัว

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

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

งานวิจัยก่อนหน้าที่ใช้เปรียบเทียบระบุว่า การคำนวณรากแรกของกรณี 1024 บิตเดียวกันใช้เวลา 1,380 CPU core-years ขณะที่งานของดีปไมด์รายงานการใช้งาน 391 CPU core-years

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

งานวิจัยก่อนหน้าใช้เวลาประมาณ 5 เดือน ส่วนการทดลองของดีปไมด์ใช้เวลา 3 วัน 22 ชั่วโมงตั้งแต่การออกแบบจนถึงการตรวจสอบผล และใช้เวลา 3.2 วันนับจากเริ่มงานคัดกรองขนาดใหญ่ เอกสารระบุว่าสาเหตุหลักที่ระยะเวลาต่างกันคือการทำงานแบบขนาน โดย CPU core-years วัดปริมาณการคำนวณรวม ส่วนเวลาที่ผ่านไปจริงขึ้นอยู่กับการแบ่งงานให้ทำพร้อมกันมากน้อยเพียงใด

ตัวเลข 391 CPU core-years ที่รายงานไม่รวมงานพีชคณิตเชิงเส้นบน GPU และการทดลองเบื้องต้นกับการซ้อม ซึ่งใช้เพิ่มอีก 7.5 CPU core-years ทีมวิจัยระบุว่า หากแปลงงาน GPU เป็นต้นทุน CPU ตามงานก่อนหน้า ความแตกต่างจะอยู่ที่ 3.4 เท่า และหากรวมงานเบื้องต้นด้วยจะอยู่ที่ 3.3 เท่า การคำนวณทั้งสองงานใช้ฮาร์ดแวร์ต่างชนิดกัน

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

เอกสารระบุว่าผลการทดลองนี้ไม่เป็นภัยต่อความปลอดภัยของระบบปัจจุบันที่ใช้ RSA-2048 หรือสูงกว่า

การทดลองนี้ไม่ได้ทดสอบลายเซ็นของบิตคอยน์ (BTC) ไลบรารี libsecp256k1 จากโครงการพัฒนา Bitcoin รองรับลายเซ็น ECDSA และ Schnorr ที่อิงกับเส้นโค้ง secp256k1 การคำนวณ RSA กับการคำนวณลายเซ็นของบิตคอยน์เป็นคนละปัญหากัน