อาร์เอสเอ

อาร์เอสเอ (อังกฤษ: 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 เนื่องจากขั้นตอนวิธีได้พิมพ์แล้วก่อนที่จะจดสิทธิบัตร กฎหมายในส่วนอื่น ๆ ของโลกทำให้ไม่สามารถจดสิทธิบัตรที่อื่นได้ และในกรณีที่ผลงานของค็อกส์ได้เป็นที่รู้จักกันในสาธารณะ การจดสิทธิบัตรในสหรัฐฯก็ไม่สามารถจะกระทำได้เช่นกัน

Operation

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

Encryption

Public Key : (e,n)

$c\equiv m^{e}modn$

Decryption

Private Key : (d,n)

$m\equiv c^{d}modn$

ตัวอย่าง

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

Public Key : (e,n)=(17,899)

c = m^e mod n ; c =191^17 mod 899 = 800

Private Key : (d,n)=(593,899)

m = c^d mod n ; m =800^593 mod 899 = 191

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

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

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