อาร์เอสเอ

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

 การดำเนินการ 
 รูปแบบ 
 กำหนดจำนวนเฉพาะโดยให้  และ 
 ให้ 

  และ  กับ  ต้องไม่มีตัวประกอบร่วมกัน

 ให้  คือค่าที่ได้จากการ Hash function

 การเข้ารหัส 
คีย์สาธารณะ : 

 การถอดรหัส 
คีย์ส่วนตัว : 

 ตัวอย่าง 
 กำหนดจำนวนเฉพาะโดยให้  และ 
 ให้ 

  ;  และ ,  ต้องไม่มีตัวประกอบร่วมกัน
  ; 
 ให้  คือค่าที่ได้จากการ Hash function ; 

 การเข้ารหัส 
คีย์สาธารณะ : 
 ; 

 การถอดรหัส 
คีย์ส่วนตัว : 
 ; 

 ตัวอย่างโค้ดในภาษาไพทอน 
 โค้ดในส่วนของการสร้างคีย์ 
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

 อ้างอิง 

 อ่านเพิ่ม 



 แหล่งข้อมูลอื่น 
 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, .
 RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2

 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

หมวดหมู่:การเข้ารหัส