ระบบการเข้ารหัส Rabinเป็นกลุ่มของ แผนการ เข้ารหัสแบบกุญแจสาธารณะที่ใช้ฟังก์ชันประตู กับดัก ซึ่งความปลอดภัย เช่นเดียวกับRSA นั้น เกี่ยวข้องกับความยากของ การแยก ตัวประกอบจำนวนเต็ม^{[ 1 ] [ 2 ]}

ฟังก์ชันกับดักของ Rabin มีข้อดีคือ การผกผันฟังก์ชันนี้ได้ รับการพิสูจน์ ทางคณิตศาสตร์แล้วว่ายากพอๆ กับการแยกตัวประกอบจำนวนเต็ม ในขณะที่ฟังก์ชันกับดัก RSA ไม่มีการพิสูจน์เช่นนั้น ข้อเสียคือ ผลลัพธ์แต่ละรายการของฟังก์ชัน Rabin สามารถสร้างขึ้นได้จากอินพุตที่เป็นไปได้สี่แบบ หากผลลัพธ์แต่ละรายการเป็นข้อความเข้ารหัส จะต้องใช้ความซับซ้อนเพิ่มเติมในการถอดรหัสเพื่อระบุว่าอินพุตใดในสี่อินพุตที่เป็นไปได้เป็นข้อความธรรมดาที่แท้จริง ความพยายามที่ไร้เดียงสาในการแก้ไขปัญหานี้มักจะทำให้เกิดการโจมตีข้อความเข้ารหัสที่เลือกเพื่อกู้คืนกุญแจลับ หรือโดยการเข้ารหัสความซ้ำซ้อนในพื้นที่ข้อความธรรมดา จะทำให้การพิสูจน์ความปลอดภัยเมื่อเทียบกับการแยกตัวประกอบเป็นโมฆะ^{[ 1 ]}

ระบบการเข้ารหัสแบบกุญแจสาธารณะที่ใช้ฟังก์ชัน Rabin trapdoor นั้นส่วนใหญ่ใช้เป็นตัวอย่างในตำราเรียน ในขณะที่ RSA เป็นพื้นฐานของระบบการเข้ารหัสแบบกุญแจสาธารณะมาตรฐาน เช่นRSAES-PKCS1-v1_5และRSAES-OAEPซึ่งใช้กันอย่างแพร่หลายในทางปฏิบัติ

ฟังก์ชันประตูหลุมพรางของ Rabin ได้รับการเผยแพร่ครั้งแรกในฐานะส่วนหนึ่งของ โครงการ ลายเซ็น Rabinในปี 1978 โดยMichael O. Rabin [ ^{3 ] [ 4 ] [ 5 ] โครงการ} ลายเซ็น Rabin เป็น โครงการ ลายเซ็นดิจิทัล โครงการแรก ที่สามารถพิสูจน์ได้ว่าการปลอมลายเซ็นนั้นยากพอๆ กับการแยกตัวประกอบ

ฟังก์ชันประตูกับดักถูกนำมาใช้ใหม่ในตำราเรียนในภายหลังในฐานะตัวอย่างของรูปแบบการเข้ารหัสแบบกุญแจสาธารณะ^{[ 6 ] [ 7 ] [ 1 ]} ซึ่งต่อมาเป็นที่รู้จักในชื่อระบบการเข้ารหัส Rabin แม้ว่า Rabin จะไม่เคยเผยแพร่มันในฐานะรูปแบบการเข้ารหัสก็ตาม

เช่นเดียวกับระบบการเข้ารหัสแบบไม่สมมาตรอื่นๆ ระบบ Rabin ใช้คู่กุญแจ: กุญแจสาธารณะสำหรับการเข้ารหัสและกุญแจส่วนตัวสำหรับการถอดรหัส กุญแจสาธารณะจะถูกเผยแพร่ให้ทุกคนสามารถใช้งานได้ ในขณะที่กุญแจส่วนตัวจะยังคงเป็นที่รู้จักเฉพาะผู้รับข้อความเท่านั้น

กุญแจสำหรับระบบเข้ารหัส Rabin ถูกสร้างขึ้นดังนี้:

1. เลือก จำนวนเฉพาะขนาด ใหญ่ที่แตกต่างกันสองจำนวนคือ และโดยที่และ${\displaystyle p}$${\displaystyle q}$${\displaystyle p\equiv 3{\bmod {4}}}$${\displaystyle q\equiv 3{\bmod {4}}}$
2. คำนวณ​${\displaystyle n=pq}$

โดยที่คือกุญแจสาธารณะ และคู่คือกุญแจส่วนตัว ${\displaystyle n}$${\displaystyle (p,q)}$

ข้อความสามารถเข้ารหัสได้โดยการแปลงข้อความนั้นให้เป็นตัวเลขก่อนโดยใช้การแมปแบบย้อนกลับได้ จากนั้นจึงคำนวณ ค่า ข้อความที่เข้ารหัส แล้ว คือ ${\displaystyle M}$${\displaystyle m<n}$${\displaystyle c=m^{2}{\bmod {n}}}$${\displaystyle c}$

สามารถกู้คืนข้อความ จากข้อความที่เข้ารหัสได้ โดยการหาค่ารากที่สองของข้อความนั้นแล้วหารด้วยค่าโมดูลัสดังนี้ ${\displaystyle m}$${\displaystyle c}$${\displaystyle n}$

1. คำนวณรากที่สองของโมดูลัสโดยใช้สูตรต่อไปนี้: ${\displaystyle c}$${\displaystyle p}$${\displaystyle q}$

   ${\displaystyle {\begin{aligned}m_{p}&=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}\\m_{q}&=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}\end{aligned}}}$

2. ใช้ขั้นตอนวิธีแบบยุคลิดขยายเพื่อหาค่าและที่ทำให้${\displaystyle y_{p}}$${\displaystyle y_{q}}$${\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}$
3. ใช้ทฤษฎีบทเศษเหลือของจีนเพื่อหาค่ารากที่สองทั้งสี่ของโมดูลัส: ${\displaystyle c}$${\displaystyle n}$

   ${\displaystyle {\begin{aligned}r_{1}&=\left(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{2}&=n-r_{1}\\r_{3}&=\left(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{4}&=n-r_{3}\end{aligned}}}$

หนึ่งในสี่ค่านี้คือข้อความต้นฉบับแต่ไม่สามารถระบุได้ว่าค่าใดในสี่ค่านี้ถูกต้องหากไม่มีข้อมูลเพิ่มเติม ${\displaystyle m}$

เราสามารถแสดงได้ว่าสูตรในขั้นตอนที่ 1 ข้างต้นนั้นสร้างรากที่สองของ ได้ดังนี้ สำหรับสูตรแรก เราต้องการพิสูจน์ว่าเนื่องจากเลขชี้กำลังเป็นจำนวนเต็ม การพิสูจน์นั้นง่ายมากหากดังนั้นเราอาจสมมติว่าไม่หาร ลงตัวโปรดทราบว่าหมายความว่าดังนั้น c เป็นเศษเหลือกำลังสองมอดูล แล้ว ${\displaystyle c}$${\displaystyle m_{p}^{2}\equiv c{\bmod {p}}}$${\displaystyle p\equiv 3{\bmod {4}},}$${\textstyle {\frac {1}{4}}(p+1)}$${\displaystyle c\equiv 0{\bmod {p}}}$${\displaystyle p}$${\displaystyle c}$${\displaystyle c\equiv m^{2}{\bmod {pq}}}$${\displaystyle c\equiv m^{2}{\bmod {p}}}$${\displaystyle p}$

${\displaystyle m_{p}^{2}\equiv c^{{\frac {1}{2}}(p+1)}\equiv c\cdot c^{{\frac {1}{2}}(p-1)}\equiv c\cdot 1\mod p}$

ขั้นตอนสุดท้ายนี้ได้รับการสนับสนุนโดยเกณฑ์ของออยเลอร์

ยกตัวอย่างเช่น ให้ใช้และจากนั้นจะได้ ให้ใช้เป็นข้อความต้นฉบับ ดังนั้น ข้อความที่เข้ารหัสแล้ว คือ ${\displaystyle p=7}$${\displaystyle q=11}$${\displaystyle n=77}$${\displaystyle m=20}$${\displaystyle c=m^{2}{\bmod {n}}=400{\bmod {77}}=15}$

ขั้นตอนการถอดรหัสมีดังนี้:

1. คำนวณและ.${\displaystyle m_{p}=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}=15^{2}{\bmod {7}}=1}$${\displaystyle m_{q}=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}=15^{3}{\bmod {11}}=9}$
2. ใช้ขั้นตอนวิธีแบบยุคลิดที่ขยายแล้วในการคำนวณและเราสามารถยืนยันได้ว่า${\displaystyle y_{p}=-3}$${\displaystyle y_{q}=2}$${\displaystyle y_{p}\cdot p+y_{q}\cdot q=(-3\cdot 7)+(2\cdot 11)=1}$
3. คำนวณหาตัวเลือกข้อความต้นฉบับทั้งสี่แบบ:

   ${\displaystyle {\begin{aligned}r_{1}&=(-3\cdot 7\cdot 9+2\cdot 11\cdot 1){\bmod {77}}=64\\r_{2}&=77-64=13\\r_{3}&=(-3\cdot 7\cdot 9-2\cdot 11\cdot 1){\bmod {77}}=\mathbf {20} \\r_{4}&=77-20=57\end{aligned}}}$

และเราจะเห็นว่านั่นคือข้อความต้นฉบับที่ต้องการ โปรดสังเกตว่าตัวเลือกทั้งสี่ตัวเป็นรากที่สองของ 15 mod 77 นั่นคือ สำหรับแต่ละตัวเลือกดังนั้นแต่ละตัวจะเข้ารหัสเป็นค่าเดียวกันคือ 15 ${\displaystyle r_{3}}$${\displaystyle r_{i}^{2}{\bmod {77}}=15}$${\displaystyle r_{i}}$

การถอดรหัสจะให้ผลลัพธ์ที่ผิดพลาดสามอย่างนอกเหนือจากผลลัพธ์ที่ถูกต้องหนึ่งอย่าง ดังนั้นผลลัพธ์ที่ถูกต้องจึงต้องเดาเอาเอง นี่คือข้อเสียเปรียบที่สำคัญของระบบการเข้ารหัสแบบราบิน และเป็นหนึ่งในปัจจัยที่ทำให้ระบบนี้ไม่ได้รับการใช้งานอย่างแพร่หลายในทางปฏิบัติ

หากข้อความต้นฉบับมีจุดประสงค์เพื่อแสดงข้อความตัวอักษร การเดาจะไม่ใช่เรื่องยาก อย่างไรก็ตาม หากข้อความต้นฉบับมีจุดประสงค์เพื่อแสดงค่าตัวเลข ปัญหานี้จะกลายเป็นปัญหาที่ต้องแก้ไขด้วยแผนการแยกความหมายบางอย่าง เป็นไปได้ที่จะเลือกข้อความต้นฉบับที่มีโครงสร้างพิเศษ หรือเพิ่มการเติมเพื่อขจัดปัญหานี้ วิธีการขจัดความกำกวมของการผกผันได้รับการเสนอแนะโดย Blum และ Williams: จำนวนเฉพาะสองตัวที่ใช้ถูกจำกัดให้เป็นจำนวนเฉพาะที่สอดคล้องกับ 3 มอดูล 4 และโดเมนของการยกกำลังสองถูกจำกัดให้เป็นเซตของเศษกำลังสอง ข้อจำกัดเหล่านี้ทำให้ฟังก์ชันการยกกำลังสองกลายเป็นการเรียงสับเปลี่ยนแบบ กับ ดัก ซึ่ง ขจัดความกำกวม^{[ 8 ]}

สำหรับการเข้ารหัส จะต้องคำนวณค่ากำลังสองโมดูลัสnซึ่งมีประสิทธิภาพมากกว่าRSAที่ต้องคำนวณอย่างน้อยค่ากำลังสาม

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

มีการพิสูจน์แล้วว่าอัลกอริทึมใดๆ ที่สามารถหาข้อความต้นฉบับที่เป็นไปได้หนึ่งข้อความสำหรับข้อความเข้ารหัสแบบ Rabin ทุกข้อความ สามารถนำมาใช้ในการแยกตัวประกอบของโมดูลัสได้ดังนั้น การถอดรหัสแบบ Rabin สำหรับข้อความต้นฉบับแบบสุ่มจึงมีความยากอย่างน้อยก็เท่ากับปัญหาการแยกตัวประกอบจำนวนเต็ม ซึ่งเป็นสิ่งที่ยังไม่ได้รับการพิสูจน์สำหรับ RSA โดยทั่วไปเชื่อกันว่าไม่มีอัลกอริทึมที่มีประสิทธิภาพในเวลาพหุนามสำหรับการแยกตัวประกอบ ซึ่งหมายความว่าไม่มีอัลกอริทึมที่มีประสิทธิภาพสำหรับการถอดรหัสค่าที่เข้ารหัสแบบ Rabin แบบสุ่มโดยไม่มีกุญแจส่วนตัว ${\displaystyle n}$${\displaystyle (p,q)}$

ระบบการเข้ารหัส Rabin ไม่สามารถป้องกันการปลอมแปลงโดยการเลือกข้อความต้นฉบับได้เนื่องจากกระบวนการเข้ารหัสเป็นแบบกำหนดได้ ผู้โจมตีสามารถตรวจสอบได้อย่างง่ายดายว่าข้อความที่เข้ารหัสแล้วนั้นเข้ารหัสข้อความต้นฉบับได้หรือไม่ (โดยการตรวจสอบว่าการเข้ารหัสข้อความต้นฉบับนั้นได้ข้อความที่เข้ารหัสแล้วหรือไม่)

ระบบการเข้ารหัส Rabin ไม่ปลอดภัยต่อการโจมตีด้วยการเลือกข้อความเข้ารหัส (แม้ว่าข้อความท้าทายจะถูกเลือกแบบสุ่มอย่างสม่ำเสมอจากพื้นที่ข้อความก็ตาม) ^{[ 6 ] : 214} โดยการเพิ่มความซ้ำซ้อน เช่น การทำซ้ำ 64 บิตสุดท้าย ระบบสามารถสร้างรากเดียวได้ ซึ่งจะขัดขวางการโจมตีด้วยการเลือกข้อความเข้ารหัสโดยเฉพาะนี้ เนื่องจากอัลกอริทึมการถอดรหัสจะสร้างรากที่ผู้โจมตีรู้อยู่แล้วเท่านั้น หากใช้วิธีการนี้ การพิสูจน์ความเท่าเทียมกันกับปัญหาการแยกตัวประกอบจะล้มเหลว ดังนั้นจึงไม่แน่ใจ ณ ปี 2004 ว่ารูปแบบนี้ปลอดภัยหรือไม่ อย่างไรก็ตาม หนังสือคู่มือการเข้ารหัสประยุกต์โดย Menezes, Oorschot และ Vanstone พิจารณาว่าความเท่าเทียมกันนี้น่าจะเป็นไปได้ ตราบใดที่การค้นหารากยังคงเป็นกระบวนการสองส่วน (1. รากและ2. การประยุกต์ใช้ทฤษฎีบทเศษเหลือของจีน) ${\displaystyle {\bmod {p}}}$${\displaystyle {\bmod {q}}}$

• หัวข้อต่างๆ ในด้านการเข้ารหัสลับ
• บลุม บลุม ชับ
• อัลกอริทึม Shanks–Tonelli
• ระบบการเข้ารหัส Schmidt–Samoa
• ระบบการเข้ารหัส Blum–Goldwasser

• Menezes, Oorschot, Vanstone, Scott: Handbook of Applied Cryptography (ดาวน์โหลดไฟล์ PDF ได้ฟรี) ดูบทที่ 8