ดูต้นฉบับสำหรับ อาร์เอสเอ

{{ต้องการอ้างอิง}}
{{ลิงก์ไปภาษาอื่น}}

'''อาร์เอสเอ''' ({{langx|en|RSA}}) คือ[[ขั้นตอนวิธี]]สำหรับ[[การเข้ารหัสลับแบบกุญแจอสมมาตร]] (public-key encryption)  เป็นขั้นตอนวิธีแรกที่ทราบว่าเหมาะสำหรับ[[ลายเซ็นดิจิทัล]]รวมถึง[[การเข้ารหัส]] เป็นหนึ่งในความก้าวหน้าครั้งใหญ่ครั้งแรกในการเข้ารหัสแบบกุญแจสาธารณะ อาร์เอสเอยังคงใช้ในโพรโทคอลสำหรับ[[การพาณิชย์อิเล็กทรอนิกส์]] และเชื่อว่ามีความปลอดภัยถ้ามีคีย์ที่ยาวพอ

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

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

ขั้นตอนวิธีนี้ได้จดสิทธิบัตรโดย [[Massachusetts Institute of Technology|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) 

<math>c \equiv m^e mod n</math>

=== Decryption ===
Private Key : (d,n)

<math>m \equiv c^d mod n</math>

=== ตัวอย่าง ===

# กำหนดจำนวน เฉพาะ p= 29 และ q=31
# ให้ n = 29*31 = 899
# z = (29-1)*(31-1) = 840
# e= 17 ; 0<e<z และ e, z ต้องไม่มีตัวประกอบร่วมกัน
# 17*d mod 840 =1 ; d = 593
# ให้ 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 ==
โค้ดในส่วนของการสร้างคีย์<syntaxhighlight lang="python3" line="1">
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)
</syntaxhighlight>โค้ดในส่วนของการเข้ารหัส<syntaxhighlight lang="python3" line="1">
def encrypt(key,plainText):
    e, n = key
    cipherText = ""
    for i in range(len(plainText)):
        cipherText += chr(((ord(plainText[i]) ** e) % n))
    return cipherText
</syntaxhighlight>โค้ดในส่วนของการถอดรหัส<syntaxhighlight lang="python3" line="1">
def decrypt(key, cipherText):
    d, n = key
    plainText = ""
    for i in range(len(cipherText)):
        plainText += chr(((ord(cipherText[i]) ** d) % n))
    return plainText
</syntaxhighlight>
[[หมวดหมู่:การเข้ารหัส]]
{{โครงเทคโนโลยี}}