วิธีพิสูจน์ความถูกต้องของสูตรการเข้ารหัสและถอดรหัส RSA สำหรับ $GCD(m_i,n)=1$ และ $GCD(m_i,n) \neq1$ โดยที่การเข้ารหัสถูกกำหนดเป็น $c_i = m_{i}^e$ mod n และการถอดรหัส $m_i = c_{i}^d$ สมัย.
ขอบคุณ @poncho ที่ให้คำแนะนำ ฉันเขียนหลักฐานต่อไปนี้:
จำได้ว่าจำนวนเต็ม $e > 0$ และ $k > 0$ ถูกเลือกเช่นนั้น $ เอ็ด = 1 + k(p â 1)(q â 1)$
ก็เพียงพอแล้วที่จะแสดงว่าทั้งสองสอดคล้องกัน
$(m^e)^d \equiv m\ \textrm{mod}\ p $ และ $(m^e)^d \equiv m\ \textrm{mod}\ q $ ถือ. p และ q เป็นจำนวนเฉพาะที่แตกต่างกัน ดังนั้น $gcd(p,q) = 1$ และความสอดคล้องกันข้างต้นบ่งบอกเป็นนัยว่า
$(m^e)^d \equiv m\ \textrm{mod}\ n $ โดยทฤษฎีบทส่วนที่เหลือของจีน ถ้า $m \equiv 0\ \textrm{mod}\ p $แล้วอย่างแน่นอน $(m^e)^d \equiv m\ \textrm{mod}\ p $. ถ้า $m \not\equiv 0\ \textrm{mod}\ p $, แล้ว $m^{p-1} \equiv 1\ \textrm{mod}\ p $ เนื่องจากทฤษฎีบทเล็กของแฟร์มาต์ ($a^{p-1} \equiv 1\ \textrm{mod}\ p $) เพราะฉะนั้น,
$$ (m^e)^d \equiv m^{1 + k(p - 1)(q - 1)} \equiv m(m^{p-1})^{k(q-1)} \ เทียบเท่า m 1^{k(q-1)} \equiv m\ \textrm{mod}\ p $$
ดังนั้น $(m^e)^d \equiv m\ \textrm{mod}\ p $ ถือสำหรับจำนวนเต็มทั้งหมด m การแทนที่ p ด้วย q ในอาร์กิวเมนต์ก่อนหน้าแสดงว่า $m \equiv (m^e)^d \textrm{mod}\ q $ ถือสำหรับจำนวนเต็มทั้งหมด m
ความคิดเห็นใด ๆ เกี่ยวกับความถูกต้องของหลักฐานของฉันได้รับการชื่นชม!
เห็นได้ชัดว่านี่เป็นโจทย์การบ้าน ดังนั้นฉันจะบอกเป็นนัยๆ เท่านั้น:
คุณพิสูจน์ได้ไหมว่าโมดูโล $p$ (ที่ไหน $p$ เป็นหนึ่งในปัจจัยสำคัญของ $n$)? นั่นคือคุณสามารถพิสูจน์ได้ว่า $(m^e \bmod p)^d \bmod p \equiv m \pmod p$สำหรับใด ๆ $m$?
หลักฐานเดียวกันจะอนุมัติโมดูโลด้วยหรือไม่ $คิว$?
จากสองข้อข้างต้น คุณจะแสดงได้อย่างไรว่าใช้โมดูโล $p \cdot q = n$?
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
