การเข้ารหัสทุกหมายเลขแยกกันโดยใช้ RSA ปลอดภัยหรือไม่

สมมติว่า RSA ถือเป็นวิธี "ปลอดภัย" สำหรับการเข้ารหัส RSA หมายถึงการเข้ารหัสลำดับของฐานจำนวนเต็ม $27$. ถ้าเราใช้ $n=pq$ ซึ่งแยกตัวประกอบได้ยาก จะยังปลอดภัยหรือไม่หากเราเข้ารหัสทุกจำนวนเต็ม (ตัวอักษร) แยกกัน แทนที่จะเข้ารหัสทั้งวลีเพียงครั้งเดียว

แก้ไข: ฉันไม่ได้คาดหวังว่าจะได้รับคำตอบที่ยอดเยี่ยมเช่นนี้ ขอบคุณทุกคน!

ด้วยการเติมที่เหมาะสม (เช่น สกอ) การใช้ RSA เพื่อเข้ารหัสแต่ละไบต์หรืออักขระหรือแม้แต่บิตนั้นปลอดภัยแน่นอน* แน่นอนว่ามันยังสิ้นเปลืองอย่างเหลือเชื่อ เนื่องจากคุณกำลังเปลี่ยนข้อความธรรมดาทุก ๆ 8 บิตให้กลายเป็นรหัสไซเฟอร์เท็กซ์ 2048 บิตขึ้นไป และใช้เวลา CPU มากในกระบวนการ แต่ความไร้ประสิทธิภาพไม่ใช่ปัญหาด้านความปลอดภัย (ปกติ)

ปราศจาก อย่างไรก็ตามการเติมข้อมูลโดยใช้ RSA เพื่อเข้ารหัส ทั้ง อักขระเดี่ยวหรือข้อความสั้นไม่ปลอดภัย เนื่องจากการเข้ารหัส "แบบเรียน RSA" ดังกล่าวมีความเสี่ยงต่อการโจมตีหลายครั้ง ทำให้สามารถถอดรหัสข้อความได้โดยไม่ต้องใช้คีย์ส่วนตัว บางส่วนของการโจมตีเหล่านี้รวมถึง:

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

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

• เดอะ $e$การโจมตีรูทครั้งที่: หากโมดูลัสสาธารณะ $e$ มีขนาดเล็ก (เช่น $e = 3$) และข้อความธรรมดา $m$ (หลังจากเข้ารหัสเป็นตัวเลขแล้ว) ก็มีขนาดเล็กนั่นเอง $m^e < n$จากนั้นการเข้ารหัส RSA แบบเรียนสามารถเอาชนะได้ง่ายๆโดยการคำนวณ $e$-th รากของไซเฟอร์เท็กซ์ $c = m^e \bmod n$. รูปแบบต่างๆ ของการโจมตีนี้ยังสามารถทำงานได้หาก $m^e < kn$ สำหรับจำนวนเต็มเล็กน้อย $k$ (พูดน้อยกว่าล้านล้าน) ง่าย ๆ โดยการทดสอบกำลังดุร้ายหากว่า $e$-th รากของ $c + jn$ เป็นจำนวนเต็มสำหรับทั้งหมด $เจ$ จาก $0$ จนถึง $k$. แม้ว่าการโจมตีนี้จะหลีกเลี่ยงได้ง่าย (เช่นโดยใช้การเติมการเข้ารหัสที่เหมาะสม และ/หรือโดยใช้เลขชี้กำลังสาธารณะที่ใหญ่กว่า เช่นเดียวกับทั่วไป $e = 2^{16} + 1 = 65537$) แผนการ RSA ที่ไร้เดียงสาจำนวนมากอย่างน่าประหลาดใจที่คิดค้นโดยมือสมัครเล่น (หรือออกแบบมาให้จงใจทำลาย เช่น ใน CTF) สามารถตกหล่นได้

^{*) ในแง่ของการให้ความลับและ ความปลอดภัยทางความหมาย ต่อผู้โจมตีดักฟังแบบพาสซีฟ สมมติว่าคีย์ RSA ถูกสร้างขึ้นอย่างถูกต้องและนานพอที่จะต้านทานการโจมตีแบบแฟคตอริ่ง เครื่องสร้างตัวเลขสุ่มที่ใช้สำหรับ OAEP จะไม่ถูกบุกรุกและไม่มีข้อผิดพลาดในการดำเนินการที่ชัดเจนอื่นๆ และการมีอยู่และ ความยาวของข้อความไม่เป็นความลับ ถึงกระนั้น รูปแบบรูปแบบ "ECB" ใดก็ตามที่เข้ารหัสข้อความทีละอักขระก็แน่นอนว่ามีความอ่อนไหวสูงและเสี่ยงต่อการถูกควบคุมโดยผู้โจมตีที่ใช้งานอยู่}

แม้ว่า RSA จะไม่ได้มีไว้สำหรับการเข้ารหัส แต่ก็สามารถใช้ RSA สำหรับการเข้ารหัสได้ หากใครใช้ TextBook RSA ก็จะไม่ปลอดภัยเนื่องจากการเข้ารหัสนั้นฟรี ดังนั้นผู้โจมตีจะสามารถตรวจสอบค่าได้ เราเรียกสิ่งนี้ว่าการเข้ารหัสของออราเคิล และไม่มีให้ใช้ในระบบคีย์สาธารณะ

ง่ายๆ ออราเคิลเข้ารหัส RSA เกม...

def Ind_CPA_RSA(ฝ่ายตรงข้าม, เป้าหมาย):
    (e,n,d,...) = create_RSA_key() // ส่วนคีย์เจน

    def RSA_encryption_oracle_PKCS#1_v1.5(ข้อความธรรมดา): //เข้ารหัส oracle
        EM = PKCS#1_v1.5_padding(ข้อความธรรมดา)
        ciphertext = EM^e ม็อด n
        ส่งคืนข้อความรหัส

    สำหรับแต่ละ m ใน possible_message_space: //queries
        c = RSA_encryption_oracle_PKCS#1_v1.5(ม)
        ถ้า c == เป้าหมาย
            พิมพ์(เป้าหมาย)
            คืนความสำเร็จ
    กลับล้มเหลว

ดังนั้น ฝ่ายตรงข้ามจึงพยายามส่งข้อความที่เป็นไปได้ทั้งหมดตราบเท่าที่พวกเขาทำได้ เพื่อดูความเสมอภาคที่จะชนะ

ในตำรา RSA ถ้าเลขชี้กำลังสาธารณะ $e=3$ แล้ว การโจมตีรากลูกบาศก์ ใช้งานได้กับข้อความทั้งหมดเช่นนั้น $len(m) < \sqrt[3]{n}$.

สำหรับการโจมตีอื่นๆ บทความของ Dan Boneh เป็นจุดเริ่มต้นที่ดี

• 1999, ยี่สิบปีแห่งการโจมตีระบบเข้ารหัส RSA, แดน โบเนห์.

$$\textbf{อย่าใช้ Text Book RSA ตราบใดที่คุณรู้ว่าคุณทำอะไร!}$$

เพื่อความปลอดภัยเราต้องใช้การเข้ารหัส RSA พร้อมช่องว่างภายในที่เหมาะสม PKCS#1 v1.5 (RSAES-PKCS1-v1_5) หรือ สกอ (RSAES-OAEP) ช่องว่างภายใน ช่องว่างเหล่านี้เพิ่มการสุ่มเพื่อให้ได้การเข้ารหัสที่น่าจะเป็น

แต่ละรายการใช้การเข้ารหัสพิเศษเพื่อให้ได้สิ่งนี้ เช่น การเติม PKCS#1 v1.5;

EM = 0x00 || 0x02 || ปล.|| 0x00 || ม.

ม เป็นข้อความ เดอะ ปล ประกอบด้วยส่วนการสุ่ม

สร้างสตริงออคเต็ต PS ที่มีความยาว k - mLen - 3 ประกอบด้วยออคเต็ตที่ไม่ใช่ศูนย์ที่สร้างขึ้นแบบสุ่มหลอก ความยาวของ PS จะเป็นแปดออคเต็ตเป็นอย่างน้อย

ตัวอย่างเช่น สำหรับ RSA 2048 บิต; $k = 256$, $mLen=4$ แล้ว ปล ความยาวคือการสุ่ม 249 ไบต์สำหรับข้อความขนาดตัวอักษรหนึ่งข้อความ ดังนั้นผู้โจมตีจึงไม่สามารถทดสอบค่าด้วยออราเคิลเข้ารหัสได้ ส่วนที่เหลือกำลังโจมตี ปัญหา RSA.

ในทำนองเดียวกัน OAEP มีการสุ่มและ OAEP ได้รับการพิสูจน์แล้วว่ามีการรักษาความปลอดภัย IND-CCA1 เลือกใช้ OAEP เป็น PKCS#1 v1.5 เนื่องจากมีการโจมตีจำนวนมากเนื่องจากการใช้งานที่ไม่เหมาะสม

หากใครต้องการบทความทางวิชาการเกี่ยวกับเมตริกของการเข้ารหัส RSA นี่คือบทความเพย์วอลล์

• 2020, ความเหมาะสมของ RSA สำหรับการเข้ารหัสข้อมูลจำนวนมาก, ปรัชญ์ สู้ภัย et. อัล

หากอักขระแต่ละตัวถูกเข้ารหัสแยกจากกัน ทุกครั้งที่อักขระ 'a' ปรากฏในข้อความธรรมดา อักขระนั้นจะจับคู่กับโทเค็นเฉพาะที่เหมือนกันไม่ว่าจะมีความยาวเท่าใดก็ตาม (เช่น 0x157a05c8) และในทางกลับกัน เมื่อใดก็ตามที่คุณเห็น 0x157a05c8 ในไซเฟอร์เท็กซ์ จะต้องจับคู่กับ 'a' ในเพลนเท็กซ์ สุดท้าย ไม่ว่าโทเค็นเอาต์พุตจะยาวเท่าใด หากอินพุตได้รับการเข้ารหัสครั้งละหนึ่งไบต์ (8 บิต) จะมีเอาต์พุตโทเค็นเพียง 256 รายการเท่านั้น ซึ่งเท่ากับจำนวนโทเค็นอินพุตที่เป็นไปได้

นั่นไม่ใช่ RSA อีกต่อไป มันคือ รหัสแทนและสิ่งเหล่านี้สามารถแตกได้เล็กน้อยโดยใช้เทคนิคง่ายๆ หลายอย่าง คุณไม่ได้ใช้ RSA เป็นอัลกอริทึมการเข้ารหัส แต่เป็น a ฟังก์ชันการได้มาของคีย์. แต่นั่นไม่ได้ทำให้รหัสการแทนที่แข็งแกร่งขึ้น