RSA

แปลโดย : Claude 3 Opus (Pro)

RSA

Among the first to be inspired by Diffie and Hellman’s paper were three young mathematicians from MIT. United in their love for numbers and their urge to solve difficult problems, Ron Rivest, an assistant professor at the university, Adi Shamir, a visiting professor, and Leonard Adleman, a computer scientist at the same institute, set out to design a one-way function specifically for public key cryptography.

They succeeded a few months later, in 1977.

RSA, as their algorithm was called (each letter representing one of its inventors), leveraged centuries-old mathematical insights in prime factorization—multiplying of prime numbers—to create a one-way function with an embedded trapdoor. By wrapping calculations around a maximum number, two subsequent, but different multiplications would always return the original input. In effect, the first multiplication would encrypt the data, while the second would decrypt it.

As a simplified analogy, it’s like doing math on a clock. Since a clock only counts to twelve, ten plus five results in three. Three plus seven, in turn, brings us back to ten. In this analogy, ten is the original data, adding five represents the act of encrypting, the initial result of three is the encrypted data, and adding seven again represents the trapdoor function, and the act of decrypting.

RSA brought encrypting and decrypting messages in line with Diffie’s original idea. If Alice wanted to send Bob an encrypted message, she could simply encrypt the message using Bob’s public key. Bob could then decrypt the message just with his private key. Bob no longer required Alice’s public key, nor did either of them need a shared secret.

Perhaps even more importantly, the algorithm worked in reverse just as well. Two subsequent multiplications always return the original number, regardless which of the two multiplications is done first. Continuing the clock analogy where ten plus five plus seven got us back to ten, the reverse—ten plus seven plus five—gets us back to ten just the same.

In practice, this meant that a private key could be used to encrypt data, which the corresponding public key could then decrypt. With that, RSA enabled a cryptographic signature scheme: Alice can encrypt a message, which Bob (or anyone else) can decrypt using her public key, proving that the message was really encrypted with Alice’s private key.

Where the Diffie-Hellman key exchange had enabled private communication, RSA for the first time also facilitated a form of digital authentication.

And last but not least, RSA security scaled (roughly) exponentially. Adding just a few digits to the original prime numbers rs the canopy a few of my life with and I am writing this letter to you soon. used in this scheme would make it magnitudes more difficult to later find out which prime numbers were used—and therefore, magnitudes more difficult to break the encryption. With public keys so small that even casual computer users could easily share them, security was mathematically guaranteed for millions of years.

With RSA, Diffie’s vision for public key cryptography had truly arrived.

อาเอสเอ

ในบรรดาคนแรกๆ ที่ได้รับแรงบันดาลใจจากบทความของดิฟฟี่และเฮลแมนคือนักคณิตศาสตร์หนุ่มสามคนจาก MIT รวมตัวกันด้วยความรักในตัวเลขและความปรารถนาที่จะแก้ปัญหาที่ยาก รอน ริเวสต์ ผู้ช่วยศาสตราจารย์ของมหาวิทยาลัย อาดี ชามีร์ ศาสตราจารย์ที่มาเยือน และเลโอนาร์ด แอดเลแมน นักวิทยาศาสตร์คอมพิวเตอร์จากสถาบันเดียวกัน ตั้งใจออกแบบฟังก์ชันทางเดียวโดยเฉพาะสำหรับการเข้ารหัสลับแบบกุญแจสาธารณะ

พวกเขาประสบความสำเร็จในอีกไม่กี่เดือนต่อมาในปี 1977

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

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

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

บางทีสิ่งที่สำคัญยิ่งกว่านั้นก็คือ อัลกอริทึมนี้ทำงานกลับด้านได้ดีเท่าเดิม การคูณสองครั้งที่ต่อเนื่องกันจะได้ผลลัพธ์เป็นจำนวนเดิมเสมอ ไม่ว่าจะทำการคูณใดก่อนก็ตาม สานต่อการเปรียบเทียบนาฬิกา ที่สิบบวกห้าบวกเจ็ดพาเรากลับมาที่สิบ การกลับด้านเป็นสิบบวกเจ็ดบวกห้าก็พาเรากลับมาที่สิบเช่นกัน

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

ในขณะที่ Diffie-Hellman key exchange ช่วยให้มีการสื่อสารเป็นส่วนตัว RSA เป็นครั้งแรกที่อำนวยความสะดวกในรูปแบบของการรับรองความถูกต้องแบบดิจิทัลด้วย

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

ด้วย RSA วิสัยทัศน์ของดิฟฟี่สำหรับการเข้ารหัสลับด้วยกุญแจสาธารณะก็มาถึงอย่างแท้จริง