อาร์เอสเอ

อาร์เอสเอ (อังกฤษ: Rivest–Shamir–Adleman: RSA) เป็นขั้นตอนวิธีสำหรับการเข้ารหัสลับแบบกุญแจอสมมาตร (public-key encryption) เป็นขั้นตอนวิธีแรกที่ทราบว่าเหมาะสำหรับลายเซ็นดิจิทัลรวมถึงการเข้ารหัส เป็นหนึ่งในความก้าวหน้าครั้งใหญ่ครั้งแรกในการเข้ารหัสแบบกุญแจสาธารณะ อาร์เอสเอยังคงใช้ในโพรโทคอลสำหรับการพาณิชย์อิเล็กทรอนิกส์ และเชื่อว่ามีความปลอดภัยถ้ามีคีย์ที่ยาวพอ

ประวัติ

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

คลิฟฟอร์ด ค็อกส์ (Clifford Cocks) นักคณิตศาสตร์ชาวอังกฤษที่ทำงานใน GCHQ ได้อธิบายระบบที่เหมือนกันในเอกสารภายใน เมื่อพ.ศ. 2516 เนื่องจากในตอนนั้น จะต้องใช้คอมพิวเตอร์ราคาแพงเพื่อนำไปใช้จริง จึงถือเป็นความแปลกใหม่ และเท่าที่ปรากฏต่อสาธารณะ ไม่เคยใช้งานจริง นอกจากนี้ การค้นพบครั้งนี้ ไม่ถูกเปิดเผยจนถึงพ.ศ. 2540 เนื่องจากได้จัดเป็นความลับ

ขั้นตอนวิธีนี้ได้จดสิทธิบัตรโดย MIT เมื่อพ.ศ. 2526 ในสหรัฐอเมริกา เป็น สิทธิบัตรหมายเลข 4,405,829 ซึ่งได้สิ้นสุดเมื่อ 21 กันยายน พ.ศ. 2543 เนื่องจากขั้นตอนวิธีได้พิมพ์แล้วก่อนที่จะจดสิทธิบัตร กฎหมายในส่วนอื่น ๆ ของโลกทำให้ไม่สามารถจดสิทธิบัตรที่อื่นได้ และในกรณีที่ผลงานของค็อกส์ได้เป็นที่รู้จักกันในสาธารณะ การจดสิทธิบัตรในสหรัฐฯก็ไม่สามารถจะกระทำได้เช่นกัน

การดำเนินการ

รูปแบบ

1. กำหนดจำนวนเฉพาะโดยให้ $p$ และ $q$
2. ให้ $n=p*q$
3. $z=(p-1)*(q-1)$
4. $e<z$ และ $e$ กับ $z$ ต้องไม่มีตัวประกอบร่วมกัน
5. $e*d\mod z=1$
6. ให้ $m$ คือค่าที่ได้จากการ Hash function

การเข้ารหัส

คีย์สาธารณะ : $(e,n)$

$c=m^{e}\mod n$

การถอดรหัส

คีย์ส่วนตัว : $(d,n)$

$m=c^{d}\mod n$

ตัวอย่าง

1. กำหนดจำนวนเฉพาะโดยให้ $p=29$ และ $q=31$
2. ให้ $n=29*31=899$
3. $z=(29-1)*(31-1)=840$
4. $e=17$ ; $0<e<z$ และ $e$, $z$ ต้องไม่มีตัวประกอบร่วมกัน
5. $17*d\mod 840=1$ ; $d=593$
6. ให้ $m$ คือค่าที่ได้จากการ Hash function ; $m=191$

การเข้ารหัส

คีย์สาธารณะ : $(e,n)=(17,899)$ $c=m^{e}\mod n$ ; $c=191^{17}\mod 899=800$

การถอดรหัส

คีย์ส่วนตัว : $(d,n)=(593,899)$ $m=c^{d}\mod n$ ; $m=800^{593}\mod 899=191$

ตัวอย่างโค้ดในภาษาไพทอน

โค้ดในส่วนของการสร้างคีย์

import random
def is_prime (num) :
    if num == 2:
        return True
    if num < 2 or num % 2 == 0:
        return False
    for n in range (3, int (num ** 0.5) + 2, 2) :
        if num % n == 0:
            return False
    return True

def gcd (a, b) :
    while b != 0:
        a, b = b, a % b
    return a
'''Euclid's extended algorithm for finding the multiplicative inverse of two numbers'''
def multiplicative_inverse (e, z) :
    d = 0
    x1 = 0
    x2 = 1
    y1 = 1
    temp_z = z

    while e > 0:
        temp1 = temp_z // e
        temp2 = temp_z - temp1 * e
        temp_z = e
        e = temp2

        x = x2 - temp1 * x1
        y = d - temp1 * y1

        x2 = x1
        x1 = x
        d = y1
        y1 = y

    if temp_z == 1:
        return d + z 

def generate_keypair (p, q) :
    if not (is_prime (p) and is_prime (q)) :
        raise ValueError ('Both numbers must be prime.')
    elif p == q:
        raise ValueError ('p and q cannot be equal')
    n = p * q
    z = (p - 1) * (q - 1)
    e = random.randrange (1, n)
    g = gcd (e, z)
    while g != 1:
        e = random.randrange (1, n)
        g = gcd (e, z)

    d = multiplicative_inverse (e, z)
    return (e,n), (d,n)

โค้ดในส่วนของการเข้ารหัส

def encrypt (key,plainText) :
    e, n = key
    cipherText = ""
    for i in range (len (plainText)) :
        cipherText += chr (((ord (plainText[i]) ** e) % n))
    return cipherText

โค้ดในส่วนของการถอดรหัส

def decrypt (key, cipherText) :
    d, n = key
    plainText = ""
    for i in range (len (cipherText)) :
        plainText += chr (((ord (cipherText[i]) ** d) % n))
    return plainText

อ่านเพิ่ม

• Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). Handbook of Applied Cryptography. CRC Press. ISBN 978-0-8493-8523-0.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 881–887. ISBN 978-0-262-03293-3.

แหล่งข้อมูลอื่น

• The Original RSA Patent as filed with the U.S. Patent Office by Rivest; Ronald L. (Belmont, MA), Shamir; Adi (Cambridge, MA), Adleman; Leonard M. (Arlington, MA), December 14, 1977, U.S. Patent 4,405,829.
• RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2
• Explanation of RSA using colored lamps ที่ยูทูบ
• Thorough walk through of RSA
• Prime Number Hide-And-Seek: How the RSA Cipher Works
• Onur Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: On the Power of Simple Branch Prediction Analysis