อัลกอริธึมของชอร์ (ยังเขียนไม่เสร็จ)

ส่วนที่เป็นคลาสสิคัล, ส่วนที่เป็นควอนตัม, ข้อควรระวัง, และรหัสลับหลังควอนตัม (post-quantum)


Kenji, meets Shor. Shor, meets Kenji.

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

ก่อนอื่นเลย อัลกอริธึมแยกตัวประกอบของชอร์เป็นอัลกอริธึมหาคาบ (period finding) ของฟังก์ชันประเภทหนึ่ง ดังนั้นเราต้องมาเข้าใจกันก่อนว่าปัญหาการทำลายระบบ RSA และการแยกตัวประกอบลดรูปไปเป็นการหาคาบได้อย่างไร ซึ่งความเข้าใจส่วนนี้ไม่เกี่ยวกับควอนตัมเลย เป็นทฤษฎีจำนวนล้วนๆ ตอนก่อนจะมาเรียนฟิสิกส์ผมเคยบอกเพื่อนภาคคณิตศาสตร์ว่าชีวิตนี้จะไม่แตะทฤษฎีจำนวนอีกแล้วแต่การคำนวณเชิงควอนตัมทำให้ผมต้องผิดคำพูด (แต่เดี๋ยวก็จะเห็นว่ามันเป็นทฤษฎีกรุ๊ปเสียส่วนใหญ่) ในส่วนแรกของโพสท์นี้เราจะลดรูปปัญหาทีละขั้นๆดังนี้

ทำลายระบบ RSA ≤ หา totient function ≤ แยกตัวประกอบ ≤ หารากที่สองที่ไม่ชัดของ 1 ≤ หาคาบ

โดย A ≤ B หมายความคร่าวๆว่าถ้าแก้ B ได้ก็แก้ A ได้ใน polynomial time

ทำลายระบบ RSA ด้วยการแยกตัวประกอบ

ในโพสท์ที่แล้วผมอธิบายการทำงานของรหัส RSA ไว้อย่างคร่าวๆ โดยไม่ใช้สมการ แต่ในโพสท์นี้ไม่ใช้ไม่ได้แล้ว ให้ \(m\) เป็นข้อความ (message), \(e\) เป็นกุญแจเข้ารหัสลับ (encryption key), และ \(d\) เป็นกุญแจถอดรหัส (decryption key) ระบบ RSA เข้ารหัสด้วยการเลือกจำนวนเต็ม \(N\) และคำนวณ \(m\) ยกกำลัง \(e\) ในเลขคณิตนาฬิกา \[ f(m) \equiv m^e \mod N \] ส่วนการถอดรหัสทำโดยยกกำลังอีกครั้งจนได้ข้อความเดิมกลับมา \[ (m^e)^d = m^{ed} \equiv m \mod N \] ในการเข้ารหัสด้วยกุญแจสาธารณะ (public key cryptography) ทุกๆคนมีสิทธิ์ที่จะรู้ \(e\) และ \(N\) แต่ผู้รับสาส์นเท่านั้นที่จะมีกุญแจถอดรหัส \(d\) เตรียมอยู่แล้ว ดังนั้นคำถามของนักแฮกก็คือเราจะคำนวณ \(d\) จาก \(e\) และ \(N\) ได้อย่างไร? 1

ปรากฏว่าถ้าเราแยกตัวประกอบได้ เราก็หาค่า \(M\) ที่ทำให้ \[ ed \equiv 1 \mod M \] ได้ ยกตัวอย่างเช่น เมื่อ \(N\) เป็นผลคูณของจำนวนเฉพาะแค่สองจำนวน \(N=pq\) ค่าของ \(M\) คือ \((p-1)(q-1)\) จากนั้นเราสามารถหาอินเวอร์สการคูณของ \(e\) ใน \(\text{mod}\,M\) ด้วยอัลกอริธึมของยูคลิด ได้กุญแจถอดรหัส \(d\) ออกมา ปัญหาการทำลายระบบ RSA จึงลดรูปเป็นปัญหาการแยกตัวประกอบได้ 2

ถ้าต้องการหาค่า \(M\) โดยทั่วไป มันคือ totient function \(\varphi(N)\) ของออยเลอร์ซึ่งผมแอบซ่อนรายละเอียดเอาไว้ด้านล่าง สามารถคลิกลูกศรเพื่อเปิดดูได้


การหาค่าของ \(M\): \(N\) เป็นจำนวนเฉพาะ

การคำนวณ totient function เป็น generalization ของทฤษฎีบทน้อยๆของแฟร์มา (Fermat’s little theorem): เมื่อ \(p\) เป็นจำนวนเฉพาะและ \(a\) กับ \(p\) เป็น coprime (ห.ร.ม.=1) \[ a^{p-1} \equiv 1 \mod p \] ทฤษฎีบทนี้พิสูจน์ ได้ด้วยทฤษฎีกรุ๊ป จำนวนใน \(\mathbb{Z}_p\) ที่มีอินเวอร์การคูณประกอบกันเป็น cyclic group \(\mathbb{Z}_p^*\) ซึ่งมีขนาด \(p-1\) (เพราะจำนวนทุกจำนวนที่เป็น coprime กับ \(p\) เป็น generators ของกรุ๊ปหมด เหลือแค่ \(p\) ตัวเดียวที่ไม่มีอินเวิร์ส) \(a^{p-1}\) จึงเท่ากับ 1 mod \(p\) ด้วยทฤษฎีบทของลากรานจ์ เพราะกรุ๊ปที่ generated โดย \(a\) เป็นซับกรุ๊ป (subgroup) ของ \(\mathbb{Z}_p^*\)

การหาค่าของ \(M\): \(N\) เป็นกำลังของจำนวนเฉพาะ

เมื่อ \(N\) เป็นกำลังของจำนวนเฉพาะ (prime power) \(N = p^r\), จำนวนที่ไม่เป็น coprime กับ \(p^r\) ใน \(\mathbb{Z}_{p^r}\) และไม่มากกว่า \(p^r\) คือ \(p,2p,\cdots,p^{r-1}p\) ซึ่งมี \(p^{r-1}\) จำนวน ดังนั้น \(\varphi(N) = p^r - p^{r-1}\)

การหาค่าของ \(M\): \(N\) ทั่วไป

เมื่อ \(N\) เป็นผลคูณของกำลังของจำนวนเฉพาะ \(N = p_1^{r_1} p_2^{r_2}\) เราสามารถพิสูจน์ได้ว่า totient function เป็นผลคูณ \(\varphi(p_1^{r_1}) \varphi(p_2^{r_2})\) หรือ \[ \varphi(p_1^{r_1}p_2^{r_2} \cdots p_k^{r_k}) = (p_1^{r_1}-p_1^{r_1-1}) (p_2^{r_2}-p_2^{r_2-1}) \cdots (p_k^{r_k}-p_k^{r_k-1}) \] นั่นเอง ทำให้ได้ว่า \[ \varphi(N) = (p-1)(q-1) \] เมื่อ \(N\) เป็นผลคูณของจำนวนเฉพาะสองจำนวน


การที่ RSA รักษาความปลอดภัยได้ก็เพราะไม่มีใครมีอัลกอริธึมคลาสสิคัลที่แยกตัวประกอบได้อย่างรวดเร็ว วิธีหนึ่งในการหาตัวประกอบของ \(N\) คือไล่หาร \(N\) ด้วยจำนวนเล็กๆไปเรื่อยๆจนกว่าจะเจอตัวหาร ซึ่งอาจจะต้องหารไปถึง \(\sqrt{N}\) ตัว ทำไมนี่ไม่ใช่อัลกอริธึม polynomial-time ล่ะ? เหตุผลก็คือเราต้องการแค่ \(\log N\) บิตในการบันทึกจำนวนเต็ม \(N\) ขนาดของอินพุตจึงไม่ใช่ \(N\) แต่เป็น \(n=\log N\) ต่างหาก อัลกอริธึมไล่หารโง่ๆจึงใช้เวลา \(2^{n/2}\) อัลกอริธึม Number Field Sieve ที่ดีสุด ก็ใช้เวลาประมาณ \(2^{n^{1/3}}\) ยังคงเป็นทวีคูณ (exponential) ในขนาดของอินพุต

แยกตัวประกอบด้วยการหาคาบ

สิ่งที่นักวิทยาศาสตร์คอมพิวเตอร์รู้มาก่อนชอร์แล้วก็คือถ้าเราสุ่มเอาจำนวน \(a\) มาหาคาบใน \(\text{mod}\,N\) เยอะๆ เราก็จะหาตัวประกอบของ \(N\) ได้ 3 คาบของ \(a\) คือคาบของฟังก์ชันยกกำลัง \(a^x\,\,\text{mod}\,N\) (modular exponentiation) ยกตัวอย่างเช่นถ้าเราจับ \(a=2\) ยกกำลังไปเรื่อยๆใน \(\text{mod}\,21\) ค่ามันก็จะวนซ้ำทุกๆ 6 ตัว

x 1 2 3 4 5 6 7 8 9 10 11
\(2^x\) 2 4 8 16 11 1 2 4 8 16 11

เราเรียกค่านี้ว่าคาบของ \(a\) คือจำนวน \(r\) ที่น้อยที่สุดที่ \[a^r \equiv 1 \mod N\] หาก \(N\) มี \(k\) ตัวประกอบ โอกาสที่จะสุ่มได้ \(a\) ที่ให้ตัวประกอบเมื่อนำมาหาคาบคือ \(1-1/2^{k-1}\) คือยังไงก็มีโอกาสไม่น้อยไปกว่าครึ่ง


รากที่สองที่ไม่ชัดของ 1 ให้ตัวประกอบ

ไอเดียก็คือถ้า \(r\) หารด้วย 2 ลงตัว \(a^{r/2}\) ก็จะเป็นรากที่สองของ 1 ใน \(\text{mod}\,N\) จากนั้นก็ใช้ไอเดียจากการทดสอบจำนวนเฉพาะของมิลเลอร์และราบิน (Miller-Rabin primality testing): รากที่สองของ 1 \[ b^2 \equiv 1 \mod N \] มีแน่ๆอยู่แล้วสองตัวคือ 1 และ \(-1 \equiv N-1\,\,\text{mod}\,N\) เรียกว่ารากที่สองที่ชัด (trivial) แต่ถ้าเมื่อไรมีรากที่สองมากไปกว่านี้ (nontrivial square root) \(N\) จะต้องเป็นจำนวนประกอบเพราะหาก \(b \not\equiv \pm 1\,\,\text{mod}\,N\) และ \[ b^2 -1 = (b+1)(b-1) \equiv 0 \mod N \] \(N\) จะต้องหาร \((b+1)(b-1)\) ลงตัว แต่ \(N\) หาร \(b+1\) หรือ \(b-1\) โดดๆไม่ลงตัว (เพราะ \(b \pm 1 \not\equiv 0\,\,\text{mod}\,N\)) \(N\) จึงต้องเป็นผลคูณของตัวประกอบที่แบ่งไปหาร \(b+1\) กับ \(b-1\) แยกกัน ด้วยเหตุนี้ ห.ร.ม.ของ \(b \pm 1\) และ \(N\) จึงเป็นตัวประกอบของ \(N\)

ความน่าจะเป็นที่ \(a\) จะให้รากที่สองที่ไม่ชัดของ 1

ยังไม่ได้เขียน


การแปลงฟูเรียร์

หาคาบด้วยอัลกอริธึมควอนตัม

ข้อควรระวังในการรันอัลกอริธึม

“Compiled Shor’s algorithm”

ความซับซ้อนของการแยกตัวประกอบ

Factoring อยู่ใน NP ∩ coNP เชื่อว่าไม่ NP-complete มิฉะนั้น PH จะยุบมาถึงระดับที่หนึ่ง (NP=coNP=PH)


  1. ถ้าไม่คิดอะไร เราอาจจะนึกว่า \(ed \equiv 1\,\,\text{mod}\,N\) คือคำตอบ แต่ \(a^{b\,\,\text{mod}\,N} \not\equiv a^b\,\,\text{mod}\,N\) เช่น \(2^5 \equiv 2^{1\,\,\text{mod}\,4}\) แต่ \(2^5 = 32 \equiv 0\,\,\text{mod}\,4\)

  2. จริงๆแล้วการแยกตัวประกอบก็ลดรูปเป็นปัญหาการทำลายระบบ RSA ได้ด้วย randomized polynomial-time algorithm จึงกล่าวได้ว่าทั้งสองปัญหาเป็นปัญหาเดียวกัน (Cristopher Moore และ Stephan Mertens, The Nature of Computation หน้า 895)

  3. หรือถ้าเช็คว่า \(a\) เป็นจำนวนเฉพาะ (ซึ่งทำได้ใน polynomial time) และโชคดี ห.ร.ม. ของ \(a\) กับ \(N\) ไม่ใช่ 1 ก็จบ ห.ร.ม.นั่นแหละคือตัวประกอบ



Archieves by date, by category, by tag.