ความยากของการสร้างจำนวนเฉพาะ 1024 บิต

 (glitchcomet.com)
4 คะแนน โดย GN⁺ 2024-05-05 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เป็นการทดลองที่ สร้างจำนวนเฉพาะขนาดประมาณ 1024 บิตสองจำนวนด้วย Rust โดยตรง สำหรับใช้กับคีย์ RSA 2048 บิต โดยลงมือทำเองตั้งแต่การสร้างเลขสุ่มไปจนถึงการคำนวณจำนวนเต็มขนาดใหญ่โดยไม่พึ่งพาไลบรารีภายนอก
  • trial division แบบง่ายเพียงอย่างเดียวเพียงพอสำหรับ 16 บิตที่ใช้เวลาราว 40ms แต่แม้จะปรับแต่งแล้วก็ยังใช้เวลา 6.4 วินาทีใน 64 บิต ทำให้ขยายไปถึง 1024 บิตได้ยาก
  • การทดสอบแบบ Fermat เร็วก็จริง แต่ไม่สามารถกรอง pseudoprime ได้ทั้งหมด จึงใช้การทดสอบ Miller-Rabin ที่ k=10 สำหรับการตัดสินขั้นสุดท้าย
  • เพื่อก้าวข้ามข้อจำกัดของชนิดจำนวนเต็มพื้นฐาน จึงสร้าง BigInt ขึ้นมาเอง และเปลี่ยนโครงสร้างจากอาร์เรย์ bool เป็นอาร์เรย์ไบต์ แล้วต่อด้วยชังก์ u64 ทำให้เวลาสร้างจำนวนเฉพาะ 1024 บิตลดจากราว 32 นาทีเหลือระดับ 60~90 วินาที
  • เวอร์ชันสุดท้ายรวม BigInt แบบชังก์ u64, การหารแบบเร็ว, trial division ด้วยจำนวนเฉพาะขนาดเล็ก, การเพิ่มค่าผู้สมัครทีละ +2, และการประมวลผลขนาน 16 เธรด จนหาจำนวนเฉพาะ 1024 บิตได้เฉลี่ยราว 40ms แต่ยังไม่ใช่ไลบรารีเข้ารหัสที่ผ่านการตรวจสอบ

สร้างจำนวนเฉพาะ 1024 บิตสำหรับ RSA ด้วยตัวเอง

  • เป้าหมายคือการสร้าง จำนวนเฉพาะที่สามารถใช้สร้างคีย์ RSA ได้ ด้วยตัวเอง
    • คีย์ RSA 2048 บิตสร้างจากผลคูณของจำนวนเฉพาะสองจำนวน ดังนั้นแต่ละจำนวนจึงต้องมีขนาดประมาณ 1024 บิต
    • โจทย์ท้าทายจึงแคบลงมาเป็นการ สร้างจำนวนเฉพาะ 1024 บิต
  • การทดลองตั้งเงื่อนไขไว้ 3 ข้อ
    • เขียนโค้ดตั้งแต่ต้นและไม่ใช้ไลบรารีภายนอก
    • ใช้โน้ตบุ๊กที่มี CPU AMD Ryzen 7 และ RAM 16GB โดยไม่พึ่งฮาร์ดแวร์ภายนอกหรือคลาวด์
    • ต้องสร้างจำนวนเฉพาะให้ได้ภายใน “เวลาที่สมเหตุสมผล”
  • ภาษาโปรแกรมที่เลือกคือ Rust ซึ่งกำลังเรียนรู้อยู่ในช่วงนั้น
    • มองว่าใกล้กับแนวคิดระดับล่างพอที่จะจัดการเรื่องแบบนี้ได้ และก็ยังอยู่ในระดับสูงพอที่จะทำความเข้าใจโค้ดเป็นส่วน ๆ ได้ง่าย

ข้อจำกัดของ trial division ที่เห็นชัดใน 16 บิตและ 64 บิต

  • กระบวนการพื้นฐานคือสร้างเลขสุ่มขนาด N บิตซ้ำ ๆ และจบเมื่อผ่านการทดสอบความเป็นจำนวนเฉพาะ
  • การสร้างเลขสุ่มทำโดยอ่าน /dev/urandom ของ Linux โดยตรงแทนการใช้ rand crate ของ Rust
    • /dev/urandom เป็นไฟล์อุปกรณ์เสมือนสำหรับเข้าถึง CSPRNG ของเคอร์เนล Linux
    • เคอร์เนลจะรวบรวมเอนโทรปีจากสภาพแวดล้อมผู้ใช้ แล้ว seed สตรีมไซเฟอร์เชิงกำหนดที่อิง ChaCha20 เป็นระยะ
  • สำหรับเลขสุ่ม 16 บิต จะตั้งบิตแรกและบิตสุดท้ายเป็น 1
    • บิตสุดท้ายเป็น 1 เพื่อให้แน่ใจว่าเป็นเลขคี่
    • บิตแรกเป็น 1 เพื่อให้ใช้ช่วงบิตตามขนาดที่ต้องการครบถ้วน
  • ใน 16 บิต การใช้เพียง trial division โดยหารตรวจจาก 3 ถึง sqrt(num) ก็หาจำนวนเฉพาะได้ในเวลาประมาณ 40ms
    • ตัวอย่างการรันได้ผลลัพธ์ Prime found: 44809 และใช้เวลาทั้งหมดประมาณ 0.038 วินาที
  • แต่เมื่อขยายไปเป็น 64 บิต trial division แบบตรงไปตรงมาใช้เวลาประมาณ 30 วินาที
    • หลังจากนั้นจึงปรับปรุงโดยตรวจเฉพาะค่าผู้สมัครในรูป 6k±1 และลองหารด้วยรายการจำนวนเฉพาะขนาดเล็กก่อน
    • หลังปรับปรุงแล้ว เวลาสร้างจำนวนเฉพาะ 64 บิตอยู่ที่ราว 6.414 วินาที
  • เมื่อแม้แต่ 64 บิตยังใช้เวลาระดับ 6 วินาที ก็เห็นชัดว่าวิธีนี้ไปไม่ถึง การสร้างจำนวนเฉพาะ 1024 บิต

เปลี่ยนไปใช้การทดสอบจำนวนเฉพาะแบบความน่าจะเป็น

  • มีการสำรวจอัลกอริทึมเชิงกำหนดอย่าง APR-CL และ ECPP แต่พบว่าซับซ้อนทางคณิตศาสตร์มาก และหาเอกสารอธิบายที่เข้าถึงได้ยาก จึงไม่เหมาะจะลงมือเขียนในครั้งนี้
  • หลังดูซอร์สโค้ดของ OpenSSL และคำแนะนำของ NIST ก็ยืนยันได้ว่าในงานใช้งานจริงรวมถึง RSA นิยมใช้ การทดสอบจำนวนเฉพาะแบบความน่าจะเป็น กันอย่างแพร่หลาย
  • จากนั้นแนวทางจึงเปลี่ยนจากการ “พิสูจน์ว่าเป็นจำนวนเฉพาะ” ไปเป็นการตัดสินว่าเป็น probable prime ด้วยระดับความแม่นยำที่กำหนด

  • การทดสอบแบบ Fermat

    • ทฤษฎีบทเล็กของแฟร์มาต์ใช้ความสัมพันธ์ที่ว่า ถ้า p เป็นจำนวนเฉพาะและ a ไม่หารด้วย p ลงตัว จะได้ว่า a^(p-1) = 1 mod p
    • การยกกำลังแบบธรรมดาทำให้เกิด overflow ใน u128 จึงต้องเขียน modular exponentiation ขึ้นมา
    • pow() รับเลขชี้กำลังเป็น u32 และหากยก u128 ด้วยเลขชี้กำลังที่ใหญ่กว่านั้นก็อาจ overflow ได้
    • แม้แต่การคูณเองก็อาจเกินขอบเขต u128 จึงใช้วิธีชั่วคราวด้วยการเก็บตัวเลข 64 บิตไว้ใน u128
    • การทดสอบแบบ Fermat ทำงานเร็ว แต่เพราะมี Fermat pseudoprime จึงอาจตัดสินจำนวนประกอบผิดว่าเป็นจำนวนเฉพาะได้
    • จำนวนประกอบลักษณะนี้แม้ไม่พบบ่อยแต่ก็มีมากพอ จึงไม่เหมาะจะเชื่อถือ Fermat เพียงอย่างเดียว

  • การทดสอบ Miller-Rabin

    • Miller-Rabin อิงหลักการเดียวกับ Fermat แต่เป็นอัลกอริทึมทดสอบจำนวนเฉพาะแบบความน่าจะเป็นที่แข็งแรงกว่า
    • การติดตั้งใช้งานคือแยก n-1 = 2^s × d ออกเป็นกำลังของ 2 แล้วตรวจหลายเงื่อนไข
    • a^d = 1 mod n
    • หรือมีบาง 0 <= r < s ที่ทำให้ a^(2^r × d) = n - 1 mod n
    • ในการทดลอง 128 บิต สามารถหาจำนวนเฉพาะได้ในเวลาประมาณ 0.042 วินาที ซึ่งใกล้เคียงกับ Fermat
    • ขอบเขตความผิดพลาดกรณีเลวร้ายที่สุดของ Miller-Rabin คือ 4^-k และสำหรับ n ขนาดใหญ่โดยเฉลี่ยอยู่ราว 8^-k
    • เมื่อ k=10 ความน่าจะเป็นผิดพลาดเฉลี่ยคำนวณได้เป็น 0.000000000931323%
    • มีการเปรียบเทียบว่าพอ ๆ กับความน่าจะเป็นที่โยนเหรียญ 30 ครั้งติดแล้วออกหัวทั้งหมด หรือ 2^-30
    • อย่างไรก็ตาม ในงานเข้ารหัสจริงยังต้องระวังเรื่องการเลือก base แบบสุ่มและเงื่อนไขเชิงปฏิปักษ์มากกว่านี้

สร้าง BigInt ขึ้นมาเอง

  • ชนิดจำนวนเต็มพื้นฐานของ Rust ไม่พอสำหรับการจัดการตัวเลขที่ใหญ่เกิน 64 บิต จึงจำเป็นต้องมี จำนวนเต็มความแม่นยำตามต้องการ (BigInt)
  • เนื่องจากตั้งเงื่อนไขว่าจะไม่ใช้ bigint crate ภายนอก จึงต้องเขียน BigInt เองด้วย

  • ความพยายามที่ 1: อาร์เรย์หลักของตัวเลข

    • ตอนแรกลองเก็บจำนวนขนาดใหญ่เป็นอาร์เรย์ของหลักเลขฐาน 10
    • การบวกและคูณทำได้คล้ายการคำนวณด้วยมือ แต่ไปต่อไม่ไหวตรงการหาร จึงเลิกแนวทางนี้

  • ความพยายามที่ 2: อาร์เรย์ไบนารีแบบ bool

    • วิธีที่สองคือเก็บตัวเลขเป็นอาร์เรย์ของ 0 และ 1
    • BigInt ใช้อาร์เรย์ [bool; 2048]
    • เพราะการคูณเลข 1024 บิตสองตัวอาจต้องใช้พื้นที่สูงสุด 2048 บิต จึงเตรียมไว้ 2048 บิต
    • การบวกและลบเขียนด้วยแนวทาง full adder
    • การคูณใช้วิธี shift-and-add ตามคุณสมบัติของเลขฐานสอง
    • การหารใช้ binary long division
    • ด้วยการติดตั้งใช้งานนี้ สามารถหาจำนวนเฉพาะ 1024 บิตตัวแรกได้สำเร็จ แต่ใช้เวลาประมาณ 32 นาที 44.90 วินาที
    • ในเชิงเทคนิคถือว่าบรรลุเป้าหมายแล้ว แต่ยังไม่ตรงเงื่อนไขเรื่อง “เวลาที่สมเหตุสมผล”

  • ความพยายามที่ 3: ชังก์แบบไบต์

    • มีการสังเกตว่า bool แต่ละตัวในอาร์เรย์ bool ไม่ได้กิน 1 บิต แต่กิน 1 ไบต์
    • นั่นหมายความว่า [bool; 2048] ใช้ 2048 ไบต์ ไม่ใช่ 2048 บิต
    • จากนั้นจึงเปลี่ยนไปเก็บ 2048 บิตในอาร์เรย์ขนาด 256 ไบต์
    • การบวก ลบ คูณ ยังทำงานได้แทบไม่ต้องเปลี่ยนมาก ส่วนการหารก็ปรับให้มองชังก์ไบต์เหมือนรายการบิต
    • วิธีนี้ลดเวลาสร้างจำนวนเฉพาะ 1024 บิตลงเหลือ 4 นาที 43 วินาที

  • ความพยายามที่ 4: ชังก์ u64

    • วิธีชังก์ไบต์จริง ๆ แล้วคือ BigInt แบบใช้ “หลักเลข” ที่มีฐานสูงขึ้น
    • ขั้นถัดไปคือเก็บ 2048 บิตเป็นชังก์ u64 จำนวน 32 ตัว
    • แต่ละชังก์ทำหน้าที่เหมือน “หลัก” หนึ่งหลัก
    • ใช้ u128 เพื่อเก็บผลลัพธ์จากการคูณชังก์ u64 สองตัว
    • ในโครงสร้างนี้ ตัวเลข 1024 บิตสามารถแทนได้ด้วยชังก์ u64 16 ตัว แทนที่จะเป็นเลขฐาน 10 ยาว 309 หลัก
    • เวลาสร้างจำนวนเฉพาะ 1024 บิตดีขึ้นเป็น 60~90 วินาที

การปรับแต่งคอขวด

  • ใน benchmark แบบง่าย ๆ ความแตกต่างระหว่างการติดตั้งใช้งานแบบไบนารีกับแบบชังก์ u64 เห็นได้ชัดมาก
    • a + b และ a - b: 5537.35ns → 123.57ns
    • a * b: 1292283.14ns → 842.32ns
    • a / b และ a % b: 733446.76ns → 44440.12ns
    • a < b และ a > b: 2506.02ns → 58.91ns
  • หลังจากนั้นการปรับแต่งจึงโฟกัสหลัก ๆ ที่การหาร การคูณ การคำนวณภายใน Miller-Rabin และตรรกะการสร้างค่าผู้สมัคร

  • การหาร

    • คอขวดที่ใหญ่ที่สุดคือ การหาร
    • แม้ใช้โครงสร้างแบบชังก์ u64 แล้ว การหารเดิมก็ยังทำ long division ทีละบิตอยู่ดี
    • จึงอ้างอิงอัลกอริทึมในหน้า 598 ของ Handbook of Applied Cryptography เพื่อเขียน long division แบบอิง radix
    • วิธีนี้ประมาณค่า “หลัก” ปัจจุบันของ quotient จาก “หลัก” 3 ตัวแรกของ dividend และ “หลัก” 2 ตัวแรกของ divisor
    • การติดตั้งใช้งานนี้ช่วยประหยัดเวลาการหารได้ประมาณ 40,000ns ต่อครั้ง
    • หาก divisor มีเพียงชังก์ u64 เดียว ก็มีการทำกรณีพิเศษให้ใช้ u128 ทำ long division แบบตรงไปตรงมามากขึ้น
    • กรณีนี้เกิดบ่อยใน Miller-Rabin

  • การคูณ

    • การคูณเร็วขึ้นราว 2 เท่า จากการจัดลำดับลูปใหม่เพื่อตัด BigInt สำหรับเก็บผลลัพธ์กลางออกไป
    • มีการคำนวณจำนวนชังก์ที่ถูกใช้งานจริง แล้ววนลูปเฉพาะชังก์ที่ไม่เป็นศูนย์
    • เนื่องจาก BigInt ส่วนใหญ่มักเก็บค่าที่ไม่เกิน 1024 บิต ทำให้พื้นที่ 2048 บิตครึ่งหนึ่งว่างอยู่บ่อยครั้ง
    • แม้จะพิจารณา Karatsuba หรือการคูณแบบ FFT ด้วย แต่เห็นว่าซับซ้อนเกินไปสำหรับการเขียนเอง และการคูณปัจจุบันก็เร็วพอแล้ว

  • การปรับแต่งภายใน Miller-Rabin

    • ใน Miller-Rabin จะเน้นลดจำนวนงานที่มีต้นทุนสูง
    • แทน x = mod_exp(x, 2, n) ด้วย x = (x * x) % n โดยตรง
    • mod_exp() ตัวแรกถูกแทนด้วยเวอร์ชัน inline ที่ลดรูปลง เพื่อลด overhead จากการเรียกฟังก์ชัน
    • เพิ่ม num.is_even() สำหรับตรวจเลขคู่แทนการคำนวณ % 2
    • เปลี่ยน d / 2 เป็น d >>= 1
    • += 1, -= 1 ถูกทำกรณีพิเศษเป็น increase() และ decrease()
    • โดยเฉพาะ is_even() และ d >>= 1 ให้ผลประหยัดเวลาราว 70,000ns ต่ออย่าง
    • ใน benchmark สุดท้าย เวอร์ชันปรับแต่งแบบชังก์ u64 เร็วขึ้นมาก
    • a * b: 842.32ns → 295.04ns
    • a / b และ a % b: 44440.12ns → 831.77ns
    • a / 2: 75121.58ns → 60.89ns
    • a % 2 == 0: 78400.87ns → 21.65ns
    • a - 1: 103.15ns → 67.54ns

ตัวสร้างจำนวนเฉพาะ 1024 บิตเวอร์ชันสุดท้าย

  • ฟังก์ชันสุดท้ายจะเริ่มจากอ่านเลขสุ่ม 1024 บิตจาก /dev/urandom
    • เปิดบิตสูงสุดเพื่อรับประกันว่ามีขนาด 1024 บิต
    • เปิดบิตต่ำสุดเพื่อรับประกันว่าเป็นเลขคี่
  • หลังจากนั้นจะไม่อ่านเลขสุ่มใหม่ทุกครั้ง แต่เพิ่มค่าผู้สมัครทีละ 2 เพื่อเลื่อนไปยังเลขคี่ถัดไป
    • increase_by_2() ส่วนใหญ่มักเป็นเพียงการบวกในชังก์ u64 ตัวเดียว
  • ก่อนทำ Miller-Rabin จะลองหารด้วยรายการจำนวนเฉพาะขนาดเล็กก่อน
    • ในโค้ดสุดท้ายใช้จำนวนเฉพาะขนาดเล็ก 1000 ตัวแรก
    • จำนวนเฉพาะเล็กเหล่านี้อยู่ในชังก์ u64 เดียว จึงใช้ประโยชน์จากกรณีพิเศษของการหารแบบชังก์เดียวที่เร็วกว่าได้
  • ปัญหานี้จัดอยู่ในประเภท embarrassingly parallel เพราะไม่ต้องใช้หน่วยความจำร่วมกันหรือซิงก์ระหว่างเธรด
    • เธรด CPU 16 ตัวจะต่างคนต่างค้นหาจำนวนเฉพาะ แล้วใช้ค่าจากเธรดที่ส่งผลลัพธ์มาได้ก่อน
  • ตัวอย่างการรันสุดท้ายบันทึกเวลา elapsed ไว้ประมาณ 0.086 วินาที
    • มีการแสดงการใช้ CPU ที่ 690%
  • ค่าเฉลี่ยจากการรัน 100 ครั้งคือ 0.04109 ± 0.00307 วินาที
    • โดยเฉลี่ยแล้วหาจำนวนเฉพาะ 1024 บิตได้ในราว 40ms
    • การเรียก prime_1024bit() แต่ละครั้งอาจแกว่งตั้งแต่ประมาณ 8ms ถึงราว 800ms ตามความสุ่ม
    • การทำงานแบบขนานช่วยลดความผันผวนด้วยการเลือกผลลัพธ์ที่เร็วที่สุด

โค้ดและข้อจำกัด

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

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-05-05
ความคิดเห็นจาก Hacker News

  • เคยมีคริปโตเคอร์เรนซีอยู่ไม่กี่ตัวที่ใช้การหาจำนวนเฉพาะขนาดใหญ่เป็นส่วนหนึ่งของฟังก์ชัน proof of work และเมื่อราว 8 ปีก่อน แค่มี implementation ของ การทดสอบความเป็นจำนวนเฉพาะ ที่เร็วมากก็ทำเงินได้พอสมควรแล้ว
    ผมเคยเป็นผู้เขียนและผู้ดูแลซอฟต์แวร์ขุด riecoin อยู่พักหนึ่ง ไม่ค่อยแน่ใจว่าทำไมเหมือนกัน คงเพราะแค่ชอบจำนวนเฉพาะ
    บทความนี้ตกหล่น Montgomery multiplication ซึ่งเป็นการปรับแต่งอันดับหนึ่งสำหรับการทดสอบจำนวนเฉพาะให้เร็ว: https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
    สิ่งนี้เป็นพื้นฐานของ implementation การยกกำลังโมดูลาร์ความเร็วสูงที่ใช้งานได้จริง
    Niall Emmart ซึ่งตอนนั้นอยู่ในแวดวงวิชาการ และเท่าที่รู้ตอนนี้อยู่ที่ Nvidia ได้เปิดเผยไลบรารี big integer บน GPU ที่เร็วสุด ๆ ชื่อ CGBN: https://github.com/NVlabs/CGBN
    จนถึงตอนนี้ก็ยังเป็น implementation การยกกำลังโมดูลาร์แบบ batch ที่เร็วที่สุดเท่าที่ผมรู้จัก และถ้าขอชื่นชมแบบเนิร์ด ๆ สักหน่อย มันน่าทึ่งจนแทบลืมหายใจ
    สักวันคงต้องเขียนเรื่องที่ผมใช้สิ่งนี้ครอบงำการผลิตคริปโตเคอร์เรนซีตัวเล็ก ๆ อยู่ราว 5 ปี และใน Python ก็มีการยกกำลังโมดูลาร์ที่ค่อนข้างดีสำหรับคำนวณ x^y % m ผ่านรูปแบบสามอาร์กิวเมนต์ของ pow(x, y, m)
    ใช้สิ่งนี้แล้วจะสร้างการทดสอบจำนวนเฉพาะแบบ Fermat หรือ Miller-Rabin ได้ง่ายมากหากอยาก implement เอง และก็สนุกดีพอสมควร ถ้าไม่อยากทำเอง mpz_probab_prime() ในไลบรารี gmp ก็ใช้ได้ดี แน่นอนว่า gmp เร็วกว่า แต่เวลาลองเล่นกับจำนวนเฉพาะขนาดใหญ่ ความสนุกของ Fermat test สองบรรทัดก็เอาชนะได้ยาก

    • Niall ยังมีส่วนร่วมในผลงานที่ชนะรางวัล ZPrize ชิ้นหนึ่งเกี่ยวกับ multi-scalar multiplication ความเร็วสูงด้วย
      มันใกล้เคียงกับการยกกำลังโมดูลาร์แบบ batch มาก ต่างกันตรงที่ทำงานบน elliptic curve ไม่ใช่โมดูโลจำนวนเฉพาะ ผมมองว่าเป็นผลสืบเนื่องจากงาน CGBN
      ปีที่แล้วเขาได้บรรยายดี ๆ ในสัมมนามื้อกลางวันด้านวิทยาการเข้ารหัสของ Stanford และมีทั้งสไลด์กับวิดีโอบันทึกออนไลน์
      https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...
      https://www.youtube.com/watch?v=KAWlySN7Hm8
    • สงสัยว่าทำไมคริปโตเคอร์เรนซีพวกนั้นถึงใช้ฟังก์ชัน proof of work แบบออกแบบเฉพาะ แบบนั้น
      อยากรู้ว่าเป็นแค่ความคิดคลุมเครือว่า cryptography ยังไงก็ใช้จำนวนเฉพาะอยู่แล้ว แต่ไม่รู้ว่าใช้เมื่อไรและทำไม หรือมีเหตุผลที่ลึกกว่านั้น
    • ผมย้ายจาก Perl มา Python ก็เพราะ pow(x,e,mod) นี่แหละ

  • ถ้ามีขอบเขตค่าสูงสุดที่กำหนดไว้ การทำให้ Miller-Rabin กลายเป็นแบบ deterministic ในทางปฏิบัตินั้นทำได้ง่าย
    แค่เลือกฐานที่พิสูจน์แล้วว่าสามารถคัดกรอง pseudoprime ทั้งหมดภายในช่วงนั้นออกไปพร้อมกันได้
    รายการก็ไม่ได้ยาวขึ้นด้วย Miller-Rabin ทรงพลังจริง ๆ

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

  • แค่ inline assembly หนึ่งบรรทัดก็ทำให้การคูณ big integer แบบประถมง่ายขึ้น: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...
    ถ้าย้อนเวลากลับไปเปลี่ยนภาษา C ได้อย่างเดียว ผมอยากใส่แนวคิด extended multiplication เข้าไป น่าเสียดายที่ Rust ก็ไม่มีเหมือนกัน ทั้งที่ฮาร์ดแวร์รองรับแทบทุกที่ Cortex M0 ไม่มีแม้แต่การหาร แต่มี extended multiplication
    โค้ดนี้มาจาก implementation RSA ของเล่นที่เขียนไว้นานแล้วและหน้าตาแย่มาก: https://github.com/jcalvinowens/toy-rsa
    เหตุผลที่แค่ Fermat test ก็เอาอยู่คือ ถ้าจำนวนเฉพาะเหล่านั้นไม่ได้เป็นจำนวนเฉพาะจริง อัลกอริทึมก็จะไม่ทำงาน Fermat test เร็ว และการเข้ารหัส/ถอดรหัสหนึ่งครั้งก็จะกำจัดความเป็นไปได้ที่เล็กสุด ๆ ว่าตัวใดตัวหนึ่งเป็น Fermat liar ได้
    อย่างไรก็ตาม ผมไม่รู้ว่าจะพิสูจน์ได้ไหมว่าไม่มีคีย์คู่ RSA ที่สามารถเข้ารหัส/ถอดรหัสข้อความได้สำเร็จด้วยค่า P/Q ที่ไม่ใช่จำนวนเฉพาะ ใน implementation จริงย่อมไม่ใช่วิธีมาตรฐานแน่นอน แต่ผมไม่เคยหาคำตอบได้

    • น่าสนใจที่ตอนนี้ C มี big integer แล้ว
      ใน C23 มีการเพิ่มชนิด _BitInt(N) และเช่นสามารถใช้ _BitInt(1024) เป็นชนิดขนาด 128 ไบต์ได้
      แต่การรองรับของคอมไพเลอร์ยังจำกัด ใน Clang ถ้าจะอนุญาตให้ N มากกว่า 128 ให้ส่งแฟล็ก -fexperimental-max-bitint-width=N ได้ ถ้า N มากกว่า 128 แล้วหาร _BitInt(N) คอมไพเลอร์จะ crash ไปเลย แต่ +, -, * ทำงานตามคาด
    • ใน Zig สิ่งนี้ค่อนข้างง่าย
      มี builtin @mulWithOverflow ที่คืนค่าผลลัพธ์พร้อมบิต overflow และจำนวนเต็มมีถึง (u|i)65535
      ขึ้นอยู่กับงานที่ทำ คุณอาจตรวจจับ overflow แล้วเลื่อนขึ้นเป็นชนิดที่ใหญ่กว่า หรือเลื่อนขึ้นก่อนแล้วค่อยตัดออกแบบเลือกได้
      อีกทั้งยังรองรับ saturating multiplication ด้วยตัวดำเนินการแยก *| และ wrapping multiplication ด้วย *% ใช้ได้เมื่อต้องการ semantics แบบนี้ ส่วน overflow อื่น ๆ ถือเป็น undefined behavior ที่อยู่ภายใต้ safety check ดังนั้นในโหมด build แบบ Debug และ ReleaseSafe จะเกิด panic
    • ถ้า p และ q เป็น Carmichael number ที่เป็น coprime กัน RSA ก็ยังสามารถเข้ารหัสและถอดรหัสข้อความได้สำเร็จ
      แต่ p*q จะมี prime factor ที่เล็กกว่า ทำให้แยกตัวประกอบได้ง่ายขึ้น ความปลอดภัยจึงลดลง
    • เท่าที่ผมรู้ ในคอมไพเลอร์ C ส่วนใหญ่และ Rust ถ้า cast เป็นชนิดที่ใหญ่กว่าก่อนแล้วคูณ ก็จะสร้าง คำสั่งภาษาเครื่อง ตรงตามที่ต้องการพอดี
    • Pretty Good Privacy(PGP) ต้นฉบับของ Philip Zimmermann ในปี 1994 ใช้เพียง sieve ที่หารด้วยจำนวนเฉพาะ 16 บิตทั้งหมดที่รู้จัก และตารางนั้นสร้างด้วย sieve of Eratosthenes จากนั้นจึงใช้ Fermat test

  • สงสัยว่างานนี้ใช้เวลานานแค่ไหน
    ตอนเป็นโปรเจกต์วิจัยปริญญาตรี ผมเคยทำการคูณจำนวนเต็มขนาดใหญ่ ซึ่งใช้เวลาเกือบสองเทอม ผม implement ทั้ง Karatsuba, Toom-Cook, FFT เชิงซ้อน, NTT หลายแบบ และ Schonhage-Strassen
    จำนวนเฉพาะแทบจะเหมือนเวทมนตร์ทางคณิตศาสตร์ สำหรับคนที่สนใจ A Friendly Introduction to Number Theory ของ Silverman เป็นหนังสือคณิตศาสตร์ที่ยอดเยี่ยม
    อนึ่ง ลิงก์ในหน้าดูเหมือนจะเป็น 4025051 ไม่ใช่ 40250519

  • เป็นบทความที่ดี ผมเองก็เพิ่งเขียน โค้ด big integer เองอยู่บ้างสำหรับเวอร์ชันแรก ๆ ของ [0] และยังจำได้ว่าการแปลงคำอธิบายระดับสูงใน论文คณิตศาสตร์ให้กลายเป็นการคำนวณจริงนั้นน่าหงุดหงิดแค่ไหน
    แต่มีข้อท้วงเล็กน้อย
    ถ้าใช้ช่วงทั้งหมดของ u64 ตัวเลขจะไม่ได้อยู่ในฐาน 2^64-1 แต่เป็น ฐาน 2^64 แต่ละ word มีช่วงตั้งแต่ 0 ถึง 2^64-1 เหมือนกับที่แต่ละหลักของเลขฐานสิบมีค่าตั้งแต่ 0 ถึง 9
    [0] https://github.com/LegionMammal978/bigfoot-sim

  • ถ้าเหมือน optimization สุดท้าย คือเมื่อเจอความล้มเหลวแล้วไม่สร้างเลขสุ่มใหม่ แต่เพิ่มค่าตัวเลขทีละ 2 จะทำให้ความปลอดภัยเสียไปเล็กน้อย
    เพราะจำนวนเฉพาะไม่ได้กระจายตัวอย่างสม่ำเสมอ จึงจะมี bias ไปทางจำนวนเฉพาะที่อยู่ถัดจาก ช่องว่างระหว่างจำนวนเฉพาะ ขนาดใหญ่

    • ผมอ่านเรื่องนั้นตอนค้นข้อมูลแล้ว
      มันเป็นการแลกระหว่างความเร็วในการรันกับความสุ่มของจำนวนเฉพาะ และผมเลือกความเร็ว โดยเห็นว่าถ้าให้ 16 เธรดเริ่มจากเลขสุ่มของตัวเองแล้วแข่งกันหาจำนวนเฉพาะ ก็น่าจะเพิ่มความสุ่มได้เพียงพอ
      ถ้าต้องการความสุ่มมากกว่าความเร็ว การเปลี่ยน +=2 เป็นการเรียก rng() ก็เป็นการแก้ที่ง่าย

  • เป็นบทความที่ดีและเขียนได้ดี
    ผู้เขียนน่าจะหมายถึง base-256 ไม่ใช่ base-255

  • ตัวเลขขนาด 1–2KB เพียงไม่กี่ตัวน่าจะใส่ใน L1 cache ได้สบาย และต่อให้ไม่พอ ก็ยังมี L2 cache ขนาดระดับเมกะไบต์ขึ้นไปที่มีเวลาเข้าถึงราว 3ns
    ในบทความบอกว่าน่าจะต้องรอการอ่าน/เขียน RAM เพราะ L1 cache miss แต่หลังจากนั้นก็ไม่ได้กลับมาพูดถึงประเด็นนี้อีก
    อีกอย่าง นี่ครอบคลุมแค่การสร้างจำนวนเฉพาะ จึงหลบกับดักส่วนใหญ่ของ RSA ไปได้ และ urandom ก็ควรปลอดภัย ถ้าโค้ดทำงานถูกต้อง ก็ไม่ได้มีจุดที่จะผิดพลาดใหญ่ ๆ มากนัก
    RSA มีประเด็นเกี่ยวกับ จำนวนเฉพาะอ่อนแอ ที่ควรหลีกเลี่ยงอยู่บ้าง แต่ผมไม่รู้ว่ามันพบบ่อยพอจะเป็นปัญหาจริงในที่นี้หรือไม่

  • ทำให้นึกถึงโปรเจกต์ตอนปีหนึ่งมหาวิทยาลัยเมื่อหลายสิบปีก่อน
    เพื่อนที่เป็นพาร์ตเนอร์โปรเจกต์ของผม ซึ่งต่อมากลายเป็นตัวแทนผู้สำเร็จการศึกษา เป็นคนเสนอไอเดียและ implement คณิตศาสตร์หลัก ๆ เป้าหมายคือสร้าง การเข้ารหัส RSA 4096 บิต
    ผมจำได้ว่าการสร้างจำนวนเฉพาะใน implementation สุดท้ายนั้นช้ามาก ใช้เวลาสร้างประมาณ 20 นาทีบนเวิร์กสเตชัน PA-RISC
    เพื่อนคนนี้เป็นสายคณิตศาสตร์ตัวจริง และหลังจบโปรเจกต์ก็ยังปรับแต่งโค้ดต่อ ผมยังจำภาพที่เขาอ่าน论文เรื่องการทดสอบจำนวนเฉพาะและการ implement คณิตศาสตร์ big integer ได้
    เช่น มีการปรับปรุงครั้งใหญ่มากเมื่อในขั้นตอนการคูณประกอบ ถ้าค่าใดค่าหนึ่งเป็น 0 ก็ข้ามการคูณแล้วให้ผลลัพธ์เป็น 0 ไปเลย

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

  • เข้าใจว่าทำไมต้องตั้งบิตต่ำสุดเป็น 1 เพราะเลขคู่ไม่มีทางเป็นจำนวนเฉพาะ แน่นอนว่ายกเว้น 2
    แต่ไม่เข้าใจว่าทำไมต้องตั้งบิตสูงสุดเป็น 1 ด้วย ผมไม่ได้รู้เรื่องจำนวนเฉพาะหรือการเข้ารหัสดีนัก แต่มันดูเหมือนยอมทิ้ง เอนโทรปี 1 บิต โดยไม่จำเป็น ผมพลาดอะไรไปหรือเปล่า?

    • ถ้าบิตสูงสุดถูกตั้งไว้เสมอ และ encode จำนวนเฉพาะโดยรวมบิตนั้นด้วย จำนวนเฉพาะก็จะถูก encode ด้วยจำนวนไบต์เท่ากันเสมอ
      การ encode ไบต์แบบความยาวแปรผันอาจสร้างปัญหาในการแลกเปลี่ยนข้อมูลระหว่างซอฟต์แวร์ต่าง ๆ ได้ ถ้าสเปกไม่ชัดเจนมากและไม่ได้ทดสอบมาดี
      ดูปัญหาที่เกิดกับ DHE แบบอิง RSA ตอน public key ของเซิร์ฟเวอร์มี 0 นำหน้าได้
    • เหมือนกับการสร้างตัวเลขสองหลัก
      ถ้าหลักแรกเป็น 0 ก็ไม่ใช่ตัวเลขสองหลัก
    • การตั้งบิตแรกเป็น 1 ทำให้เสียเอนโทรปี 1 บิต แต่รับประกันได้ว่าจำนวนเฉพาะนั้นใหญ่พอ
      ขอเสริมอีกอย่าง ใน RSA เราคูณจำนวนเฉพาะสองตัว ถ้าตัวหนึ่งเป็น 1024 บิต อีกตัวถ้าจำไม่ผิดเป็นราว 200 บิตก็อาจถึงจำนวนบิตเอนโทรปีที่คีย์ต้องการแล้ว
      ดังนั้นการให้จำนวนเฉพาะทั้งสองตัวเป็น 1024 บิต ก็ยังมี margin เพิ่มอีกเล็กน้อย
    • ใช่ เป็นการยอมทิ้งเอนโทรปี 1 บิต แต่ก็ยังเหลือ 1022 บิต
      แบบนี้น่าจะปลอดภัยกว่าการที่มีคนขอจำนวนเฉพาะ 1024 บิต แล้วต้องมาคิดว่าจำนวนเฉพาะ 1020 บิตพอใช้ได้ไหม เหมือนปกติเราไม่ถือว่า 00042 เป็นตัวเลข 5 หลัก
      ในทางเทคนิค ตัวเลือกที่เหมาะที่สุดอาจต่างกันตามว่าจะเอาไปใช้ตรงไหน แต่แนวทางในบทความดูเป็นค่าเริ่มต้นที่ปลอดภัยกว่า
    • ดูเหมือนเป็นการแลกเปลี่ยนที่สมเหตุสมผลมาก ที่ยอมเสียเอนโทรปี 1 บิตเพื่อให้แน่ใจว่าจะไม่ได้จำนวนเฉพาะที่มีแค่ 50 บิต