ฉันกำลังติดตามการสนทนาใน Koblitz ในย่อหน้าที่สองในส่วน RSA (หน้า 94 ในฉบับของฉัน) เป้าหมายคือเพื่อแสดงความรู้เกี่ยวกับจำนวนเต็ม $d$ ดังนั้น $$m^{ed}\equiv m \mod n$$ สำหรับทุกอย่าง $m$ กับ $(m,n)=1$ แบ่ง RSA ปัญหาคือฉันไม่ใช่นักคณิตศาสตร์และฉันต้องการความช่วยเหลือเพื่อคลี่คลายตัวเองในจุดต่างๆ
ก่อนอื่นเขากล่าวว่าสิ่งนี้เทียบเท่ากับ $k=เอ็ด-1$ เป็นตัวคูณร่วมน้อยของ $p-1$ และ $q-1$. ทำไมถึง #1? ความพยายามของฉัน: ฉันรู้ว่าโดยทฤษฎีบทของออยเลอร์ $m^{\varphi(n)}\equiv 1\mod n$ และนั่น $\varphi(n)=(p-1)(q-1)$ เนื่องจาก $(m,n)=1$. นอกจากนี้ตั้งแต่ $(m,n)=1$ เราสามารถหารสมการของเราด้วย $m$ และได้รับ $m^k\equiv 1\mod n$. ฉันคิดว่าฉันพลาดขั้นตอนสุดท้าย ...
เขาคิดต่อไปว่า $m^k\equiv 1\mod n$ สำหรับทุกอย่าง $m$ นายกรัฐมนตรีถึง $n$. $k$ ต้องเป็นเลขคู่ เพราะสมการนี้ควรมีค่าสำหรับ $m=-1$. เพื่อให้เราตรวจสอบได้ว่า $m^{k/2}\equiv 1\mod n$ เช่นกันสำหรับทุกคน $m$ ไพรม์ถึง n นั่นคือสำหรับทั้งหมด $m$ ใน $\mathbb Z_n^*$. หากมีอย่างใดอย่างหนึ่ง $m$ ดังนั้น $m^{k/2}\not\equiv 1\mod n$แล้วเช่นเดียวกันกับอย่างน้อยครึ่งหนึ่งของ $m$อยู่ใน $\mathbb Z_n^*$. ทำไมต้อง #2? ความพยายามของฉัน: นี่ควรเป็นผลมาจากความจริงที่ว่าถ้า $m_0$ เป็นองค์ประกอบดังกล่าวแล้วให้ $m_1\in \mathbb Z_n^*$ ผลิตภัณฑ์ $m_0m_1$ ก็เป็นเช่นนั้นเช่นกัน $$(m_0m_1)^{k/2}=m_0^{k/2}m_1^{k/2}\not\equiv1\mod n, $$ แต่ฉันไม่แน่ใจว่าเหตุใดจึงหมายความว่าองค์ประกอบอย่างน้อยครึ่งหนึ่งแบ่งปันคุณสมบัตินี้
ส่งผลให้ถ้าเราทดสอบหลายๆ $m$และมักจะพบ $m^{k/2}\equiv 1\mod n$แล้วเป็นไปได้มากว่าความสอดคล้องกันมีไว้สำหรับองค์ประกอบทั้งหมดของ $\mathbb Z_n^*$ ดังนั้นเราจึงสามารถแทนที่ได้ $k$ โดย $k/2$. เราทำซ้ำจนกระทั่งสิ่งนี้ไม่เป็นความจริงอีกต่อไป: จากนั้นเราก็ไม่สามารถมีได้ $k/2\equiv 0\mod (p-1)$ เช่นเดียวกับ $k/2\equiv 0\mod (q-1)$. ทำไมต้อง #3? ความพยายามของฉัน: นี่ควรเป็นเพียงเพราะหากทั้งสองสอดคล้องกัน $k/2$ เป็นทวีคูณของทั้งคู่ $p-1$ และ $q-1$ และด้วยเหตุนี้ $\phi(n)$และด้วยทฤษฎีบทของออยเลอร์ $m^{k/2}$ ควรจะเป็น $1$ $\mod n$ สำหรับทุกอย่าง $m\in \mathbb Z_n^*$ กับสมมติฐานของเรา
ดังนั้น ความสอดคล้องอย่างใดอย่างหนึ่งเหล่านี้ถือและไม่สอดคล้องกัน (ตัวอย่างเช่น $k/2\equiv 0\mod p-1$ แต่ $k/2\not\equiv 0\mod q-1$) หรือไม่ถือครอง ในกรณีแรก $m^{k/2}$ ตลอดเวลา $\equiv 1\mod p$ แต่อย่างแน่นอน $50\%$ ตรงกับเวลาที่ $-1$ โมดูโล $คิว$. ทำไม #4? ความพยายามของฉัน: ฉันค่อนข้างสับสนกับสิ่งนี้ ฉันคิดว่า $m^{k/2}\equiv 1\mod p$ อีกครั้งโดยทฤษฎีบทของออยเลอร์ เช่น $k/2$ เป็นผลคูณของ $p-1$นั่นคือผลคูณของ $\phi(p)$. แต่ฉันไม่เห็นว่าทำไม $m^{k/2}$ สอดคล้องกับ $-1$ โมดูโล $คิว$ อย่างแน่นอน $50\%$ ของเวลา...
กรณีที่สองควรจะคล้ายคลึงกับกรณีแรก ดังนั้นฉันจะสำรองคำถามที่ห้าไว้ให้คุณ จะมีใครอดทนเพื่ออธิบายประเด็นทั้งสี่นี้ให้ฉันฟังได้ไหม?
เป็นเรื่องแปลกเล็กน้อยที่จะพูดว่า "ทำลาย RSA" เพราะแน่นอนว่าการรู้รหัสลับทำให้คุณสามารถถอดรหัสข้อความได้ - นี่คือสิ่งที่คุณจะทำในกรณีที่ตรงไปตรงมาเมื่อถอดรหัสข้อความของคุณเอง
ก่อนอื่นเขากล่าวว่าสิ่งนี้เทียบเท่ากับ $k=เอ็ด-1$ เป็นตัวคูณร่วมน้อยของ $p-1$ และ $q-1$. ทำไมถึง #1? ความพยายามของฉัน: ฉันรู้ว่าโดยทฤษฎีบทของออยเลอร์ $m^{\varphi(n)}\equiv 1\mod n$ และนั่น $\varphi(n)=(p-1)(q-1)$ เนื่องจาก $(m,n)=1$. นอกจากนี้ตั้งแต่ $(m,n)=1$ เราสามารถหารสมการของเราด้วย $m$ และได้รับ $m^k\equiv 1\mod n$. ฉันคิดว่าฉันพลาดขั้นตอนสุดท้าย ...
คุณมาถูกทางแล้ว เพราะ $m^{\varphi(n)}\equiv 1\pmod n$นี่ก็หมายความว่าถ้าเราหา $d$ ดังนั้น $ed = r\varphi(n) + 1$ สำหรับบางคน $r$, แล้ว $$m^{ed}\equiv m^{r\varphi(n) + 1} \equiv (m^{\varphi(n)})^r \cdot m^1 \equiv 1^r \cdot m \ เทียบเท่า m\pmod n$$
ดังนั้นสำหรับคีย์เข้ารหัสที่กำหนด $e$คีย์ถอดรหัสที่เกี่ยวข้อง $d$ เป็นเพียงคุณค่าเช่นนั้น $ed = r\varphi(n) + 1$. ในคำถามของคุณ $k = r\varphi(n)$.
$k$ จะเป็นด้วยซ้ำเพราะ $\varphi(n)$ จะเป็นแม้กระทั่งในกรณีนี้ - $p, q$ เป็นจำนวนเฉพาะที่แตกต่างกันทั้งคู่ และจำนวนเฉพาะทั้งหมดยกเว้น 2 เป็นจำนวนคี่ ดังนั้นอย่างน้อยหนึ่งจำนวน $(p-1)$, $(q-1)$ ต้องเป็นเลขคู่ (และอาจจะเป็นทั้งคู่ เพราะจำนวนเฉพาะ $2$ จะไม่ถูกนำมาใช้ใน RSA
หากมีอย่างใดอย่างหนึ่ง $m$ ดังนั้น $m^{k/2}\not\equiv 1\mod n$แล้วเช่นเดียวกันกับอย่างน้อยครึ่งหนึ่งของ $m$อยู่ใน $\mathbb Z_n^*$. ทำไมต้อง #2? ความพยายามของฉัน: นี่ควรเป็นผลมาจากความจริงที่ว่าถ้า $m_0$ เป็นธาตุนั้นให้แล้ว $m_1\in \mathbb Z_n^*$ ผลิตภัณฑ์ $m_0m_1$ ก็เป็นเช่นนั้นเช่นกัน $$(m_0m_1)^{k/2}=m_0^{k/2}m_1^{k/2}\not\equiv1\mod n, $$ แต่ฉันไม่แน่ใจว่าเหตุใดจึงหมายความว่าองค์ประกอบอย่างน้อยครึ่งหนึ่งแบ่งปันคุณสมบัตินี้
พิจารณาก $m_0$ ดังนั้น $m_0^{k/2} \not\equiv 1 \pmod{n}$. ทุกพลังที่แปลกประหลาด $m_0^{2j + 1}$ ของ $m_0$ จะมีปัญหาเดียวกันเพราะ $$(m_0^{2j+1})^{k/2} \equiv (m_0^{k/2})^{2j}\cdot m_0^{k/2} \equiv (m_0^k)^j \cdot m_0^{k/2} \equiv 1 \cdot m_0^{k/2} \not\equiv 1 \pmod{n}$$ เพราะ $m_0^k \equiv 1 \pmod{n}$. พลังคี่ทุกตัวไม่ทำงาน แต่พลังคู่ทุกตัวทำงานได้ ดังนั้นเราจึงมี 50/50
แล้วเราไม่สามารถมี $k/2\equiv 0\mod (p-1)$ เช่นเดียวกับ $k/2\equiv 0\mod (q-1)$. ทำไมต้อง #3? ความพยายามของฉัน: นี่ควรเป็นเพียงเพราะหากทั้งสองสอดคล้องกัน $k/2$ เป็นทวีคูณของทั้งคู่ $p-1$ และ $q-1$ และด้วยเหตุนี้ $\phi(n)$และด้วยทฤษฎีบทของออยเลอร์ $m^{k/2}$ ควรจะเป็น $1$ $\mod n$ สำหรับทุกอย่าง $m\in \mathbb Z_n^*$ กับสมมติฐานของเรา
ถูกต้อง.
ดังนั้น ความสอดคล้องอย่างใดอย่างหนึ่งเหล่านี้ถือและไม่สอดคล้องกัน (ตัวอย่างเช่น $k/2\equiv 0\mod p-1$ แต่ $k/2\not\equiv 0\mod q-1$) หรือไม่ถือครอง ในกรณีแรก $m^{k/2}$ ตลอดเวลา $\equiv 1\mod p$ แต่อย่างแน่นอน $50\%$ ตรงกับเวลาที่ $-1$ โมดูโล $คิว$. ทำไม #4? ความพยายามของฉัน: ฉันค่อนข้างสับสนกับสิ่งนี้ ฉันคิดว่า $m^{k/2}\equiv 1\mod p$ อีกครั้งโดยทฤษฎีบทของออยเลอร์ เช่น $k/2$ เป็นผลคูณของ $p-1$นั่นคือผลคูณของ $\phi(p)$. แต่ฉันไม่เห็นว่าทำไม $m^{k/2}$ สอดคล้องกับ $-1$ โมดูโล $คิว$ อย่างแน่นอน $50\%$ ของเวลา...
พิจารณา $(m^{k/2})^2 \pmod n$. นี่คือ $m^{k} \equiv 1 \pmod{n}$. แต่เพราะว่า $(m^{k/2}) \equiv 1 \pmod{p}$, แล้ว $(m^{k/2}) \equiv \pm 1 \pmod{q}$มิฉะนั้นจะไม่ยกกำลังสอง $1$. อาร์กิวเมนต์คล้ายกับด้านบนเพื่อแสดงว่าเราได้รับแต่ละกรณี 50% ของเวลา (เนื่องจากตอนนี้เรารับประกันแล้วว่าจะไม่สอดคล้องกับ 1 ทุกครั้ง)
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
