อัลกอริทึม RSA: อะไรคือการล็อคที่เป็นไปได้สูงสุดที่เพื่อนของคุณสามารถมีได้ เพื่อที่เขา/เธอจะสามารถแบ่งปันสิ่งนั้นกับคุณอย่างลับๆ

คำเตือน: มีบางอย่างผิดปกติในคำถามซึ่งมีเหตุผลที่จะยกเลิก ดูส่วนที่สอง แต่ก่อนอื่นลองตอบราวกับว่าเราไม่ได้สังเกต

ในหนึ่งในคำจำกัดความที่แตกต่างกันเล็กน้อยของตำราเรียน RSA

• รหัสส่วนตัว (ใช้สำหรับการถอดรหัสโดยผู้ถือกุญแจ) คือ $(d,n)$
• รหัสสาธารณะ (ใช้สำหรับการเข้ารหัสโดยทุกคน) คือ $(จ,น)$,
• ข้อความธรรมดา $m$ และไซเฟอร์เท็กซ์ $ค$ เป็นจำนวนเต็มในช่วงเวลา $[0,n-1]$,
• $n$, $d$ และ $e$ ได้รับเลือกเช่นนั้นสำหรับทุกคน $m$ ในช่วงเวลาดังกล่าวเราสามารถคำนวณได้
  • $c:=m^e\bmod n$ สำหรับการเข้ารหัสแล้ว
  • $m':=c^d\bmod n$ สำหรับการถอดรหัส การยอมจำนน $m'=m$.

ในข้างต้น$\bmod$เป็นตัวดำเนินการที่มีสองอาร์กิวเมนต์ เช่น $x\bmod n$ เป็นจำนวนเต็มที่กำหนดไม่ซ้ำกัน $y$ กับ $0\le y<n$ และ $x-y$ หลายรายการ $n$. เมื่อไร $x\ge0$ และ $n>0$, นั่น $y$ คือส่วนที่เหลือของการหารแบบยุคลิดของ $x$ โดย $n$. ช่วงเวลา $[0,n-1]$ ในคำจำกัดความข้างต้นของ RSA เป็นเพราะเป็นช่วงของส่วนที่เหลือในการหารแบบยุคลิด

คำถามถามหาจำนวนเต็มสูงสุด $m$ ที่ให้ตัวเองเมื่อเข้ารหัสแล้วถอดรหัส คีย์ที่กำหนดแสดงว่า $n=27$; ดังนั้นคำตอบ (มากที่สุด) คือ $m=n-1=27-1=26$. มันสมเหตุสมผลแล้วที่จะยืนยันว่าสิ่งนี้ $m$ ได้รับการเข้ารหัสและถอดรหัสอย่างถูกต้องสำหรับคำถาม $d=5$ และ $e=13$ ตามคำจำกัดความข้างต้นของ RSA หลักฐานนั้นง่าย: เรามี $m\equiv-1\pmod n$, และ $e$ และ $d$ เป็นเรื่องแปลกดังนั้น $c\equiv(-1)^e\equiv-1\pmod n$, ดังนั้น $m'\equiv(-1)^d\equiv-1\pmod n$, ดังนั้น $m'=c=m=n-1$ เนื่องจากนั่นเป็นจำนวนเต็มเท่านั้น $y$ ใน $[0,n-1]$ กับ $y\equiv-1\pmod n$.

หมายเหตุ: ในข้างต้น $y\equiv x\pmod n$ วิธี: $x-y$ เป็นผลคูณที่ไม่ใช่ศูนย์ $n$. ในการใช้งานนี้$\bmod$ไม่ใช่โอเปอเรเตอร์ที่มีสองอาร์กิวเมนต์ ดังที่แสดงไว้ในวงเล็บซ้ายที่อยู่ทางซ้ายทันที ค่อนข้าง,$\pmod n$ มีคุณสมบัติ $\equiv$ เครื่องหมายทางด้านซ้าย ซึ่งก็คือ/เป็นโมดูโลสมมูล $n$.

มีปัญหาร้ายแรงอย่างน้อยหนึ่งข้อในคำถาม: จำนวนเต็มมากที่สุด $m$ ในช่วงเวลา $[0,26]$ จะถอดรหัสไม่ถูกต้องหลังจากเข้ารหัส! ถ้าใครสนใจที่จะลองเท่านั้น $0$, $1$ และ $26$ ทำเช่นนั้น (พวกเขาทำทุกอย่างที่แปลก $e$ และ $d$ เป็นผู้เลือก) นอกจากนี้ทั้งหมด $m$ หลายรายการ $3$ เข้ารหัสเหมือนกัน $ค=0$ดังนั้นในบรรดาสิ่งเหล่านี้ส่วนใหญ่สามารถถอดรหัสได้อย่างถูกต้อง

ประเด็นยังไม่หมดเพียงเท่านี้ $e$ และ $d$ ไม่ตรงกันสำหรับสิ่งนั้น $n$. ปัญหาคือเพื่อให้ RSA ทำงานได้ทั้งหมด $m$ อยู่ในช่วง $[0,n-1]$ มันจำเป็นที่ $n$ ไม่มีกำลังสองซึ่งไม่หารด้วยกำลังสองของจำนวนเฉพาะใดๆ กล่าวอีกนัยหนึ่ง จะต้องไม่มีจำนวนเฉพาะปรากฏขึ้นสองครั้งในการแยกตัวประกอบของ $n$. แต่ที่นี่ $27$ หารด้วย $3^2$. โดยไม่มีเงื่อนไขสี่เหลี่ยมจัตุรัสสำหรับคี่ $n$ก็ยังสามารถเลือกได้ $e$ และ $d$ การถอดรหัสนั้นใช้งานได้ส่วนใหญ่ $m$. แต่ในกรณีที่อยู่ในมือ $e$ และ $d$ ไม่ตรงกับเงื่อนไขสำหรับสิ่งนั้นด้วยซ้ำ ความเป็นไปได้ประการหนึ่งคือคำถามถูกถามในตอนแรก $n=51$ซึ่งทำให้ $d=5$, $e=13$ ทำงาน; แล้วเลินเล่อเปลี่ยนเป็น $n=27$.

มันเลวร้ายยิ่งกว่าการ $(d,n)$ และ $(จ,น)$ พารามิเตอร์ในคำถามไม่ถูกต้องสำหรับ RSA: ไม่อนุญาตให้ใช้พารามิเตอร์ RSA ใดๆ ที่มีขนาดใกล้เคียงกัน แอบ แบ่งปันอะไร

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

นอกจากนี้ "ระบบการเข้ารหัสลับที่ใช้ RSA" ยังระบุอย่างหลวมๆ ว่าสมมติว่าตำราเรียน RSA เหมือนในส่วนแรกนั้นเป็นการเก็งกำไรล้วนๆคำสั่งปัญหานั้นผิด!

¹ เงื่อนไขที่จำเป็นและเพียงพอสำหรับตำราเรียน RSA เพื่อถอดรหัสอย่างถูกต้องสำหรับจำนวนเต็มล้วนทั้งหมด $m$ ใน $[0,n-1]$ เมื่อไร $n$ เป็นแบบไม่มีสี่เหลี่ยมจัตุรัส และอย่างน้อยก็สำหรับสิ่งเหล่านี้ทั้งหมด $m$ โคไพร์มด้วย $n$ มิฉะนั้นคือ: $e\,d\equiv1\pmod{\lambda(n)}$, ที่ไหน $\แลมบ์ดา$ คือ ฟังก์ชันคาร์ไมเคิล. มักจะสอนหนึ่งในเงื่อนไขที่แตกต่างกันเล็กน้อย ซึ่งเพียงพอแต่ไม่จำเป็น ที่นิยมได้แก่ $e\,d\equiv1\pmod{\varphi(n)}$, ที่ไหน $\varphi$ เป็น โทเค็นของออยเลอร์; $d=e^{-1}\bmod{\varphi(n)}$, นอกจากนี้ความหมาย $0\le d<\varphi(n)$; $e=d^{-1}\bmod{\varphi(n)}$ที่ใช้ใน บทความ RSA ดั้งเดิม; $d=e^{-1}\bmod{\lambda(n)}$ซึ่งให้ผลบวกที่ถูกต้องน้อยที่สุด $d$ สำหรับที่กำหนด $e$.