ทฤษฎีจำนวนเบื้องต้นกับรหัสลับและความปลอดภัย

ทฤษฎีจำนวนเบื้องต้น: กุญแจสู่โลกแห่งรหัสลับ

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

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

แนวคิดพื้นฐานในทฤษฎีจำนวนที่จำเป็นสำหรับรหัสลับ

การหารลงตัวและจำนวนเฉพาะ (Divisibility and Prime Numbers)

สิ่งแรกที่เราต้องเข้าใจคือการหารลงตัวครับ เมื่อเราพูดว่า $a$ หาร $b$ ลงตัว หรือ $a | b$ หมายความว่าเราสามารถเขียน $b$ ให้อยู่ในรูป $b = ak$ ได้ โดยที่ $k$ เป็นจำนวนเต็มครับ ตัวอย่างเช่น $3 | 12$ เพราะ $12 = 3 times 4$ ครับ

จากแนวคิดนี้ เราจะเจอพระเอกของเรานั่นคือ “จำนวนเฉพาะ” (Prime Numbers) ครับ จำนวนเฉพาะคือจำนวนเต็มบวกที่มากกว่า $1$ และมีตัวประกอบที่เป็นบวกแค่ $1$ กับตัวมันเองเท่านั้น เช่น $2, 3, 5, 7, 11, ldots$ ส่วนจำนวนเต็มบวกที่มากกว่า $1$ และไม่ใช่จำนวนเฉพาะ เราเรียกว่า “จำนวนประกอบ” (Composite Numbers) เช่น $4, 6, 8, 9, 10, ldots$

ความสำคัญต่อรหัสลับ: การที่จำนวนประกอบสามารถแยกตัวประกอบออกเป็นผลคูณของจำนวนเฉพาะได้เพียงชุดเดียว (ตามทฤษฎีบทหลักมูลของเลขคณิต – Fundamental Theorem of Arithmetic) ทำให้เกิดสิ่งที่เรียกว่า “ปัญหาการแยกตัวประกอบ” (Factoring Problem) ซึ่งเป็นรากฐานความปลอดภัยของรหัสลับหลายชนิด โดยเฉพาะ RSA ครับ การแยกตัวประกอบของจำนวนขนาดใหญ่มากๆ เป็นเรื่องที่ยากมากสำหรับคอมพิวเตอร์ในปัจจุบัน ทำให้ข้อมูลของเราปลอดภัยครับ

เลขคณิตมอดุลาร์ (Modular Arithmetic)

นี่คือหัวใจสำคัญที่เราจะเจอกันบ่อยที่สุดในเรื่องรหัสลับเลยครับ เลขคณิตมอดุลาร์ หรือที่บางคนเรียกว่า “เลขคณิตนาฬิกา” เป็นการคำนวณที่เกี่ยวข้องกับเศษเหลือจากการหารครับ เราจะใช้สัญลักษณ์ $a equiv b pmod{m}$ ซึ่งหมายความว่า $a$ และ $b$ มีเศษเหลือเท่ากันเมื่อถูกหารด้วย $m$ ครับ หรืออีกนัยหนึ่งคือ $m$ หาร $a-b$ ลงตัวครับ

ตัวอย่างง่ายๆ: ถ้าตอนนี้เป็นเวลา 10 โมงเช้า อีก 5 ชั่วโมงข้างหน้าจะเป็นเวลา 15 โมง หรือ 3 โมงเย็น นั่นคือ $10 + 5 = 15 equiv 3 pmod{12}$ ครับ

เลขคณิตมอดุลาร์มีคุณสมบัติเหมือนการบวก ลบ คูณ ในจำนวนเต็มทั่วไป เพียงแต่ผลลัพธ์จะถูก “วน” กลับมาอยู่ในช่วง $0$ ถึง $m-1$ เสมอครับ

ความสำคัญต่อรหัสลับ: การคำนวณมอดุลาร์เป็นพื้นฐานในการเข้ารหัสและถอดรหัสข้อมูลครับ โดยเฉพาะอย่างยิ่งการยกกำลังมอดุลาร์ $a^b pmod{m}$ ซึ่งง่ายต่อการคำนวณไปข้างหน้า แต่ยากที่จะย้อนกลับ (เรียกว่า Discrete Logarithm Problem) ทำให้เหมาะกับการสร้างฟังก์ชันทางเดียวที่ใช้ในรหัสลับครับ

ตัวหารร่วมมาก (GCD) และอัลกอริทึมยูคลิด (Euclidean Algorithm)

ตัวหารร่วมมาก หรือ ห.ร.ม. (GCD – Greatest Common Divisor) ของจำนวนเต็มสองจำนวน $a$ และ $b$ คือจำนวนเต็มบวกที่มากที่สุดที่หารทั้ง $a$ และ $b$ ได้ลงตัวครับ เราใช้สัญลักษณ์ $gcd(a,b)$ ครับ

ตัวอย่าง: $gcd(24, 18)=6$ ครับ

ในการหา GCD ของจำนวนขนาดใหญ่ เรามีเครื่องมือที่ทรงพลังและมีประสิทธิภาพมากๆ นั่นคือ “อัลกอริทึมยูคลิด” (Euclidean Algorithm) ครับ ซึ่งจะใช้วิธีการหารซ้ำๆ เพื่อหาเศษเหลือจนเป็นศูนย์ และ GCD คือเศษเหลือตัวสุดท้ายที่ไม่ใช่ศูนย์ครับ

ความสำคัญต่อรหัสลับ: อัลกอริทึมยูคลิดไม่ได้มีดีแค่หา GCD เท่านั้นครับ แต่เวอร์ชันที่เรียกว่า “อัลกอริทึมยูคลิดแบบขยาย” (Extended Euclidean Algorithm) ยังสามารถใช้หาอินเวอร์สการคูณมอดุลาร์ได้ด้วย ซึ่งสำคัญมากในการถอดรหัสครับ

อินเวอร์สการคูณมอดุลาร์ (Modular Multiplicative Inverse)

ในเลขคณิตธรรมดา ถ้าเรามี $3x = 1$ เราจะหา $x$ ได้ง่ายๆ คือ $x = 1/3$ ครับ แต่ในเลขคณิตมอดุลาร์ เราไม่มีเศษส่วนครับ เราจึงต้องหา “อินเวอร์สการคูณมอดุลาร์” แทน

อินเวอร์สการคูณมอดุลาร์ของ $a$ ภายใต้ $pmod{m}$ คือจำนวนเต็ม $x$ ที่ทำให้ $ax equiv 1 pmod{m}$ ครับ อินเวอร์สนี้จะหาได้ก็ต่อเมื่อ $gcd(a,m)=1$ เท่านั้นครับ

ตัวอย่าง: หาอินเวอร์สการคูณของ $3$ ภายใต้ $pmod{10}$ ครับ เราต้องการหา $x$ ที่ทำให้ $3x equiv 1 pmod{10}$ ลองแทนค่า $x$ ดูครับ

• $3 times 1 = 3$
• $3 times 2 = 6$
• $3 times 3 = 9$
• $3 times 4 = 12 equiv 2 pmod{10}$
• $3 times 7 = 21 equiv 1 pmod{10}$

ดังนั้น อินเวอร์สการคูณของ $3$ ภายใต้ $pmod{10}$ คือ $7$ ครับ

ความสำคัญต่อรหัสลับ: อินเวอร์สการคูณมอดุลาร์เป็นสิ่งจำเป็นอย่างยิ่งในการ “ถอดรหัส” ข้อมูลครับ ในระบบเข้ารหัสแบบกุญแจสาธารณะ (Public-Key Cryptography) อินเวอร์สนี้จะใช้ในการสร้างกุญแจส่วนตัว (Private Key) จากกุญแจสาธารณะ (Public Key) ครับ

ฟังก์ชัน Totient ของออยเลอร์ ($phi(n)$) และทฤษฎีบทของออยเลอร์ (Euler’s Totient Function and Euler’s Theorem)

ฟังก์ชัน Totient ของออยเลอร์ หรือ $phi(n)$ คือจำนวนเต็มบวก $x$ ที่น้อยกว่าหรือเท่ากับ $n$ และมี $gcd(x,n)=1$ ครับ ฟังดูซับซ้อนใช่ไหมครับ?

ตัวอย่าง: หา $phi(10)$ ครับ เราต้องการหาจำนวนเต็มบวกที่น้อยกว่าหรือเท่ากับ $10$ และมี $gcd$ เป็น $1$ กับ $10$ ได้แก่ $1, 3, 7, 9$ (เพราะ $gcd(1,10)=1$, $gcd(3,10)=1$, $gcd(7,10)=1$, $gcd(9,10)=1$) มีทั้งหมด $4$ จำนวน ดังนั้น $phi(10)=4$ ครับ

ทฤษฎีบทของออยเลอร์: เป็นทฤษฎีบทที่สำคัญมากครับ กล่าวว่า ถ้า $a$ และ $n$ เป็นจำนวนเต็มบวกที่ $gcd(a,n)=1$ แล้ว $a^{phi(n)} equiv 1 pmod{n}$ ครับ (ทฤษฎีบทเล็กของแฟร์มาต์ – Fermat’s Little Theorem เป็นกรณีพิเศษเมื่อ $n$ เป็นจำนวนเฉพาะ $p$ ครับ โดยที่ $phi(p) = p-1$ ดังนั้น $a^{phi(p-1)} equiv 1 pmod{p}$ เมื่อ $p nmid a$ ครับ)

ความสำคัญต่อรหัสลับ: ทฤษฎีบทของออยเลอร์เป็นรากฐานสำคัญที่ทำให้ระบบเข้ารหัส RSA สามารถทำงานได้ครับ โดยเฉพาะในการถอดรหัสข้อมูล เพราะช่วยให้เราสามารถย้อนกลับการยกกำลังมอดุลาร์ได้นั่นเองครับ

การประยุกต์ใช้ในรหัสลับและความปลอดภัย: RSA เป็นกรณีศึกษา

หลังจากที่เราเข้าใจแนวคิดพื้นฐานของทฤษฎีจำนวนกันแล้ว พี่กฤษณ์จะพาน้องๆ ไปดูว่าแนวคิดเหล่านี้ถูกนำไปใช้ในระบบรหัสลับจริงได้อย่างไร โดยจะยกตัวอย่างที่โดดเด่นที่สุดอย่างหนึ่งคือ “ระบบเข้ารหัส RSA” ครับ ซึ่งเป็นระบบเข้ารหัสแบบกุญแจสาธารณะ (Public-Key Cryptography) ที่ใช้กันอย่างแพร่หลายทั่วโลก

หลักการทำงานของ RSA พึ่งพิงแนวคิดเหล่านี้ครับ:

• การสร้างกุญแจ: เริ่มต้นด้วยการเลือกจำนวนเฉพาะขนาดใหญ่มากๆ สองจำนวน สมมติว่าเป็น $p$ และ $q$ ครับ (ซึ่งการหาจำนวนเฉพาะขนาดใหญ่แบบสุ่มเป็นสิ่งสำคัญมาก) จากนั้นคำนวณ $n=pq$ และคำนวณค่า $phi(n)=(p-1)(q-1)$ ครับ
• กุญแจสาธารณะ (Public Key): ประกอบด้วย $(e, n)$ โดยที่ $e$ คือจำนวนเต็มที่เลือกขึ้นมาให้มีคุณสมบัติว่า <math data-latex="1 < e 1 < e < ϕ ( n ) 1 < e < phi(n) และ $gcd(e, phi(n))=1$ ครับ กุญแจนี้สามารถเปิดเผยให้คนทั่วไปทราบได้ครับ
• กุญแจส่วนตัว (Private Key): คือ $d$ ซึ่งเป็นอินเวอร์สการคูณมอดุลาร์ของ $e$ ภายใต้ $pmod{phi(n)}$ นั่นคือ $ed equiv 1 pmod{phi(n)}$ ครับ กุญแจ $d$ นี้ต้องเก็บเป็นความลับสุดยอดครับ
• การเข้ารหัส (Encryption): ผู้ส่งที่ต้องการส่งข้อความ $M$ (แปลงเป็นตัวเลขแล้ว) จะใช้กุญแจสาธารณะ $(e, n)$ ในการเข้ารหัส โดยคำนวณ $C equiv M^e pmod{n}$ เพื่อได้ข้อความเข้ารหัส $C$ ครับ
• การถอดรหัส (Decryption): ผู้รับจะใช้กุญแจส่วนตัว $d$ ของตนเองในการถอดรหัสข้อความ $C$ โดยคำนวณ $M equiv C^d pmod{n}$ ก็จะได้ข้อความต้นฉบับ $M$ กลับมาครับ

ความปลอดภัยของ RSA: ระบบ RSA ปลอดภัยก็เพราะการ “แยกตัวประกอบ” ของจำนวนเต็มขนาดใหญ่ $n$ ให้กลับไปเป็นจำนวนเฉพาะ $p$ และ $q$ นั้นทำได้ยากมากๆ สำหรับคอมพิวเตอร์ทั่วไป หากผู้ไม่หวังดีรู้แค่ $n$ กับ $e$ แต่ไม่รู้ $p$ และ $q$ พวกเขาจะไม่สามารถคำนวณหา $phi(n)$ และจากนั้นหา $d$ ซึ่งเป็นกุญแจส่วนตัวได้ครับ นี่คือความงดงามและความแข็งแกร่งของทฤษฎีจำนวนในการปกป้องข้อมูลของเราครับ

ข้อผิดพลาดที่พบบ่อยและสิ่งที่ควรระวังในการเรียนรู้

ในการศึกษาทฤษฎีจำนวนและการประยุกต์ใช้กับรหัสลับ มีบางจุดที่น้องๆ มักจะเข้าใจผิดหรือสับสนได้ครับ พี่กฤษณ์รวบรวมมาให้ดังนี้:

• สับสนระหว่างการหารลงตัวกับเศษเหลือ: การหารลงตัวหมายถึงได้เศษ $0$ ในขณะที่เลขคณิตมอดุลาร์เน้นที่ค่าของเศษเหลือที่อาจจะไม่ใช่ $0$ ครับ ต้องทำความเข้าใจความแตกต่างให้ชัดเจน
• คำนวณมอดุลาร์ผิดพลาด โดยเฉพาะกับการยกกำลัง: การยกกำลังมอดุลาร์ต้องทำทีละขั้นตอน หรือใช้เทคนิคที่เหมาะสมเพื่อลดขนาดตัวเลข ไม่ใช่ยกกำลังธรรมดาแล้วค่อยนำไปหารด้วยมอดุลัสทีเดียวครับ (เช่น $7^3 pmod{10}$ ควรคิด $7^2 = 49 equiv 9 pmod{10}$ แล้วค่อยเอา $9 times 7 = 63 equiv 3 pmod{10}$ ครับ)
• ไม่เข้าใจเงื่อนไขของการหาอินเวอร์สการคูณมอดุลาร์: ย้ำอีกครั้งว่าอินเวอร์สจะหาได้ก็ต่อเมื่อ $gcd(a,m)=1$ เท่านั้นครับ ถ้าเงื่อนไขนี้ไม่เป็นจริง ก็จะไม่มีอินเวอร์สครับ
• มองข้ามความสำคัญของจำนวนเฉพาะขนาดใหญ่: ในโลกแห่งรหัสลับ จำนวนเฉพาะยิ่งใหญ่ ยิ่งปลอดภัยครับ การทำความเข้าใจว่าทำไมการแยกตัวประกอบถึงยากเมื่อตัวเลขใหญ่ขึ้น เป็นหัวใจสำคัญของความปลอดภัยในยุคปัจจุบันครับ

สรุปแนวคิดสำคัญ

น้องๆ คงเห็นแล้วนะครับว่าทฤษฎีจำนวน ซึ่งดูเหมือนจะเป็นคณิตศาสตร์บริสุทธิ์ที่ห่างไกลตัว กลับกลายเป็นรากฐานที่แข็งแกร่งของระบบรหัสลับและความปลอดภัยทางไซเบอร์ที่อยู่รอบตัวเราในทุกวันนี้ ตั้งแต่แนวคิดพื้นฐานอย่างการหารลงตัว จำนวนเฉพาะ ไปจนถึงเลขคณิตมอดุลาร์ GCD อินเวอร์สการคูณ และฟังก์ชัน Totient ของออยเลอร์ ล้วนเป็นจิ๊กซอว์สำคัญที่ประกอบกันขึ้นเป็นเกราะป้องกันข้อมูลของเราครับ

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

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