การเข้ารหัสแบบ RSA

การเข้ารหัสแบบ RSA เป็นอัลกอริธึมการเข้าหรัสแบบกุญแจอสมมาตร ในการเข้ารหัสโดยใช้ความรู้เรื่องเลขคณิตมอดุลาร์เข้ามาช่วยในการคำนวณ (modular arithmetic)

การเข้ารหัสแบบกุญแจอสมมาตร (Public-key cryptography) เป็นการเข้ารหัสที่นิยมใช้กันอย่างแพร่หลายในการทำธุรกรรมอิเล็กทรอนิคส์ เช่นการยืนยันตัวตนด้วยระบบลายเซ็นอิเล็กทรอนิคส์ (Digital signature) และการค้าผ่านอินเตอร์เน็ต (e-commerce) โดยการเข้ารหัสจะต้องมี public key และ private key ซึ่งสร้างจากตัวเลขที่สุ่มขึ้นมา และนำมาผ่านขั้นตอนของ RSA

โดย public key จะเป็นตัวที่สามารถเผยแพร่และใช้ร่วมกันได้ แต่ private key จะมีอยู่เฉพาะที่ผู้รับสารเท่านั้น หรือก็คือ การเข้ารหัสของแต่ละคนสามารถใช้ public key เดียวกันได้ แต่ในการถอดรหัสออกมาจะขึ้นอยู่กับ private key ของผู้รับสารที่จะถอดรหัส

ประวัติ

การเข้ารหัสแบบ RSA เป็นอัลกอลิธึมที่ถูกอธิบายเมื่อพ.ศ. 2520 โดย รอน ริเวสต์ ( Ron Rivest) , อาดี ชามีร์ ( Adi Shamir) และเล็น เอเดิลแมน ( Len Adleman) ที่ MIT โดยที่ RSA นั้นเป็นตัวย่อมาจากนามสกุลของทั้ง 3 คน (Rivest-Shamir-Adleman) การเข้ารหัสแบบ RSA ได้จดสิทธิบัตรโดยสถาบัน MIT ในสหรัฐอเมริกาเมื่อปี พ.ศ. 2526 และได้สิ้นสุดลงเมื่อปี พ.ศ. 2543 เพราะเป็นผลงานที่เคยถูกตีพิมพ์เผยแพร่แล้วก่อนที่จะจดสิทธิบัตร

การสร้าง public key

- ขั้นที่ 1

สุ่มตัวเลข 2 ตัว ที่เป็นจำนวนเฉพาะ กำหนดให้เป็น p และ q

- ขั้นที่ 2

หาค่า n โดยที่ n=pq

- ขั้นที่ 3

หาค่า

( ค่า totient)

- ขั้นที่ 4

เลือกจำนวนเต็ม e หนึ่งค่าโดยที่

1 < e < ; e เป็นจำนวนเฉพาะสัมพัทธ์กับ (ไม่มีตัวประกอบร่วมยกเว้น 1)

- ขั้นที่ 5

หาค่า d โดยที่

การเข้ารหัส

เมื่อได้ค่า d, e, n มาแล้ว ก็จะสามารถนำค่าเหล่านี้มาเข้ารหัสได้ดังต่อไปนี้

- ขั้นที่ 1

เมื่อให้ M เป็นข้อความที่ยังไม่ได้เข้ารหัส (plain text) ให้นำ M มาเปลี่ยนเป็นตัวเลข m

(อาจเปลี่ยนโดยวิธีการแทน a เป็น 1 b เป็น 2 ไปเรื่อยๆ) โดยที่ m < n

- ขั้นที่ 2

นำค่า m มาคำนวณในสมการ

โดยที่ c เป็นค่าหลังจากที่เข้ารหัสแล้ว

ตัวอย่างการเข้ารหัส

การสร้าง public key

- ขั้นที่ 1 สุ่มจำนวนเฉพาะ

ให้ p และ q เป็น 11 และ 23 ตามลำดับ

- ขั้นที่ 2 หาค่า n

n = pq

n = 11(23) = 253

- ขั้นที่ 3 หาค่า totient

- ขั้นที่ 4 เลือกค่า e

ให้ e = 3

- ขั้นที่ 5 หาค่า d

จะได้ d = 147

ตัวอย่างการเข้ารหัส

ให้ m = 97 (สมมุติว่าเปลี่ยนมาจากข้อความ M แล้ว)

นำไปคำนวณในสมการ

จะได้ c = 102

เพราะฉะนั้นจะได้ว่าข้อความที่เข้ารหัสแล้วจะมีค่าเป็นตัวเลขคือ 102

การถอดรหัส

การถอดรหัสจะมีขั้นตอนคล้ายกับการเข้ารหัส แต่จะมีการนำค่า d ที่หาไว้มาใช้ เมื่อได้ค่า d, e, n มาแล้ว ให้นำค่าเหล่านี้มาถอดรหัสได้ดังต่อไปนี้

- ขั้นที่ 1

นำค่า c ที่เป็นตัวเลขที่เข้ารหัสแล้วมาคำนวณในสมการ

โดยที่ m เป็นตัวเลขที่ยังไม่ได้เข้ารหัส

- ขั้นที่ 2

เมื่อได้ตัวเลข m มาแล้วให้นำไปเปลี่ยนเป็นตัวอักษร M เพื่อให้ได้ข้อความที่ยังไม่ได้เข้ารหัส (plain text)

ตัวอย่างการถอดรหัส

จากตัวอย่างการเข้ารหัสที่ได้กล่าวไว้แล้ว เราจะนำค่าตัวเลขที่เข้ารหัสไว้แล้วและค่า d, e, n ที่คำนวณไว้แล้ว มาถอดรหัสได้ด้วยวิธีการดังต่อไปนี้

นำค่า c=102 มาคำนวณในสมการ

จะได้ m=97

เมื่อถอดรหัสแล้วจะได้ค่า m =97 ซึ่งตรงกับค่าตัวเลขที่ยังไม่ได้เข้ารหัส

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

http://generalp.atwebpages.com/rsa

ป้ายกำกับ: RSA Cryptography การเข้ารหัส แ�