ในหลักสูตรวิทยานิพนธ์ของฉัน ฉันได้รับแบบฝึกหัดต่อไปนี้:
ElGamal เสนอโครงร่างลายเซ็นดิจิทัลต่อไปนี้โดยใช้ลอการิทึมที่ไม่ต่อเนื่องบนฟิลด์ $\mathbb{F}_p$, ที่ไหน $p$ เป็นนายกขนาดใหญ่
ขั้นตอนที่ 1) ทุกคนเห็นด้วยกับนายก $p$ และเครื่องกำเนิดไฟฟ้า $g$ สำหรับ $\mathbb{F}_p^*$.
ขั้นตอนที่ 2) A (และการใช้งานอื่นๆ ทั้งหมด) เลือกเลขชี้กำลังลับ $d_A$และเผยแพร่สู่สาธารณะ $e_A\equiv g^{d_A}\mod p$ (เช่นเดียวกับใน ElGamal cryptosystem)
ขั้นตอนที่ 3) ในการเซ็นข้อความ เข้ารหัสเป็นจำนวนเต็ม $m$ กับ $0\le ม\le p-1$, A เลือกจำนวนเต็มแบบสุ่ม $k$ ค่อนข้างดี $p-1$ (เช่น. $\gcd(k,p-1)=1$). จากนั้นคำนวณ $r\equiv g^k \mod p$ และแก้สมการ $g^m\equiv e_A^r r^s \mod p$ ในที่ไม่รู้จัก $s$. เผื่อ $s=0$ (ไม่น่าเป็นไปได้ทีเดียว) เธอเริ่มต้นใหม่อีกครั้งด้วยสิ่งที่แตกต่างออกไป $k$. สุดท้าย A ส่งข้อความถึง B $m$ ร่วมกับคู่ $(ร,ส)$ซึ่งเป็นลายเซ็นของเธอสำหรับข้อความนั้น
ขั้นตอนที่ 4) Beatriz ตรวจสอบสิ่งนั้น $g^m \equiv e_A^r r^s \mod p$. หากถือได้ว่า B ยอมรับว่าลายเซ็น $(ร,ส)$ เป็นของอ.จริงๆ
ก) ตรวจสอบว่า Ana รู้ทุกอย่างที่เธอต้องคำนวณ $s$.
b) ตรวจสอบว่า C ไม่สามารถแสร้งทำเป็น A โดยไม่รู้ตัว $d_A$นั่นคือไม่สามารถแก้ปัญหาลอการิทึมแบบไม่ต่อเนื่องได้ และดังนั้น $B$ ก็มั่นใจได้ว่าข้อความมาจากอ.จริงๆ
ค) ทำไมต้องทิ้ง $k$ ถ้าปรากฎว่า $s=0$?
นี่คือสิ่งที่ฉันมี:
ก) ตั้งแต่ $r\equiv g^k\mod p$ และ $e_A=g^{d_A}\mod p$ แล้ว: $$g^m\equiv e_A^rr^s\equiv (g^{d_A})^{r}(g^k)^s=g^{d_Ar+ks}\mod p$$ และทฤษฎีบทเล็กของแฟร์มาต์บอกเป็นนัยว่า $m\equiv d_Ar+ks\mod p-1\ลูกศรขวา ks\equiv m-d_Ar\mod p-1$. ดังนั้นตั้งแต่ $\gcd(k,p-1)=1$ เรามีสิ่งนั้น $k$ กลับด้านได้ $\mathbb{F}^*_p$ และอื่น ๆ $s\equiv k^{-1}(m-d_Ar)\mod p-1$. เป็นอันว่าจบกันเพราะแอนนารู้ $p,k,m,d_A$ และ $r$.
ข) ถ้า $C$ อยากจะแสร้งทำเป็น $A$มันต้องส่ง $m$ และ $(ร,ส)$ ดังนั้น $g^m\equiv e_A^rr^s\mod p$. แต่ $s$ ขึ้นอยู่กับ $d_A$ ดังที่เราได้เห็นใน $ก)$. เราจึงสร้างไม่ได้ $s$ โดยไม่รู้ตัว $d_A$และอื่น ๆ ถ้า $C$ อยากจะแสร้งทำเป็น $B$มันจำเป็นต้องค้นหา $d_A$. แต่นั่นเป็นเรื่องยากเนื่องจากสิ่งเดียวที่เรารู้ $d_A$ (ถ้าเราไม่ใช่ $A$) คือว่า $e_A\equiv g^{d_A}\mod p$ และแสร้งทำเป็นว่า $A$ เทียบเท่ากับการแก้ปัญหาลอการิทึมแบบไม่ต่อเนื่อง
ค) ถ้า $s=0$ แล้ว $g^m\equiv e_A^r\equiv g^{d_Ar}\mod p$ และอื่น ๆ $m\equiv d_Ar\mod p-1$. จากที่นี่ฉันติดอยู่เนื่องจากนี่เป็นข้อมูลเดียวที่ฉันมี แต่ฉันไม่เห็นว่าสิ่งนี้ช่วยให้เราสร้างลายเซ็นโดยไม่รู้ได้อย่างไร $d_A$. แน่นอนเราแก้ได้ $m\equiv d_Ar\mod p-1$ซึ่งจะมี $\gcd(r,p-1)$ เฉลยแล้วตรวจสอบว่าข้อใดถูกต้อง $d_A$, แต่ $\gcd(r,p-1)$ สามารถใกล้ชิดกับ $p-1$ ถ้าเราโชคร้าย และนั่นหมายความว่าโพรเซสนี้เป็นเวลาเอกซ์โปเนนเชียล และมันก็ไม่ได้ดีไปกว่าการแก้ลอการิทึมที่ไม่ต่อเนื่อง
หากคุณสามารถตรวจสอบได้ว่า a) และ b) ถูกต้องหรือไม่ และให้คำแนะนำเกี่ยวกับ c) ฉันจะขอบคุณมาก
ทางออกที่มอบให้ ก ไม่เป็นไร
ความพยายามพิสูจน์สำหรับ ข ผิด: เป็นไปได้ที่ C âsend $m$ และ $(ร,ส)$ ดังนั้น $g^m\equiv(e_A)^r\,r^s\pmod p$.
วิธีหนึ่งที่ทำได้แม้ว่า A จะไม่มีประโยชน์ก็ตาม $d_A$ เกินกว่าขั้นตอนที่ 1: C เลือก $r=s=(p-1)/2$และคอมพิวเตอร์ $(e_A)^r\,r^s\bmod p$. นั่นคืออย่างใดอย่างหนึ่ง $p-1$ หรือ $1$. C เลือกตามลําดับ $m=(p-1)/2$ หรือ $m=0$และตอนนี้มี $m$ และ $(ร,ส)$ ที่ผ่านการตรวจสอบขั้นตอนที่ 4 นี่คือการปลอมแปลงที่มีอยู่จริง (มี คนอื่น ที่นำไปสู่การดูสุ่ม $m$). การผ่อนปรนในระดับหนึ่งสามารถทำได้โดยกำหนดให้ในขั้นตอนที่ 4 B ยอมรับเฉพาะที่มีความหมายเท่านั้น $m$ สำหรับคำนิยามความหมายบางอย่าง หรือเปลี่ยนสมการการตรวจสอบเป็น $g^{H(m)}\equiv(e_A)^r\,r^s\pmod p$.
แต่แล้วก็มีปัญหาที่ซีสามารถจับตัวเอได้ $m$ และ $(ร,ส)$ จัดทำโดย A ในการดำเนินการขั้นตอนที่ 3 ก่อนหน้า และส่งสิ่งนั้นไปยัง B นี่เป็นการโจมตีซ้ำบนโปรโตคอลที่ระบุไว้ใน ข. วิธีหนึ่งในการบล็อกสิ่งเหล่านี้คือให้ B เลือก $m$ ก่อนการดำเนินการตามขั้นตอนที่ 3 แต่ละครั้ง
แต่จากนั้น C สามารถส่งต่อไปยัง A อะไรก็ตามที่ C ได้รับจาก B และไปยัง B อะไรก็ตามที่ C ได้รับจาก A นี่เป็นการโจมตีแบบรีเลย์บนโปรโตคอลที่ระบุไว้ใน ข. คำตอบสำหรับคำถามนั้นในขอบเขตของคำถามนั้นค่อนข้างจำกัด: ตัดสินใจว่านั่นไม่ใช่ปัญหา หรือตั้งสมมติฐานว่า A นั้นแยกออกจากการโต้ตอบระหว่าง B และ C
หากคำถามถ่ายทอดคำชี้แจงปัญหาได้ถูกต้อง คำถามต่อมาจึงถือว่าผิด! หากเพียงชี้ว่าถือว่ามีความเสี่ยง ฉันขอแนะนำให้ใช้ถ้อยคำใหม่ตามระเบียบการที่ระบุไว้ใน ข เป็น: สมมติ $m$ ถูกเลือกโดยการสุ่มใน $[0,p-1)$ โดย B ก่อนขั้นตอนที่ 3 และ A ไม่เกี่ยวข้องกับการแลกเปลี่ยนระหว่าง B และ C จากตัวเลือกนั้น $m$ จนจบขั้นตอนที่ 4 พิสูจน์ว่าหาก C สามารถผ่านการทดสอบขั้นตอนที่ 4 ด้วยความน่าจะเป็นที่ไม่เป็นศูนย์ ดังนั้น C จะสามารถหา $d_A$ ด้วยความน่าจะเป็นเหมือนกัน ฉันหวังว่า (ไม่แน่ใจ) จะมีวิธีแก้ปัญหาที่ค่อนข้างง่ายสำหรับการกำหนดใหม่นั้น
คำแนะนำสำหรับ ค: สันนิษฐานไว้ก่อน $(p-1)/2$ เป็นไพรม์ (ข้อกำหนดทั่วไปเพื่อช่วยให้ DLP ยาก) และผู้ดักฟังจะจับได้ $m$ และ $(r,s=0)$ ผ่านการทดสอบของ 4 และ $m\not\equiv0\pmod{(p-1)/2}$. พิสูจน์ว่าเครื่องดักฟังนี้สามารถหาได้ $d_A$แล้วปลอมตัวเป็นอ.
แม้ว่าเดิมทีข้อความแจ้งปัญหาจะไม่เป็นเช่นนั้น ฉันขอแนะนำให้ใช้สัญลักษณ์มาตรฐานสำหรับ$\bmod$:
$a\equiv b\pmod q$, หมายความว่า $q\ne0$ และ $b-a$ เป็นทวีคูณของ $คิว$โดยไม่มีข้อผูกมัด $a$. มีวงเล็บเปิดอยู่ข้างหน้าทันที$\bmod$หมายความว่าไม่มีตัวถูกดำเนินการเหลืออยู่ เดอะ$\bmod$และเป็นตัวถูกดำเนินการที่เหมาะสมก่อนหน้านี้ $\equiv$ เข้าสู่ระบบ. สามารถมีได้หลายอย่างเช่นใน $a\equiv b\equiv c\pmod q$.$a=b\bสมัย q$) หมายความว่า $0\le ก<q$ และ $b-a$ เป็นทวีคูณของ $คิว$. ในสำนวนนี้$\bmod$เป็นตัวดำเนินการสองอาร์กิวเมนต์ ใช้กับตัวถูกดำเนินการด้านซ้าย $ข$ และตัวถูกดำเนินการ $คิว$. ไม่มี $\equiv$ ลงชื่อ และไม่มีวงเล็บทันทีก่อน$\bmod$. เราก็เขียนได้เหมือนกัน $a=(b\bmod q)$, $(b\bmod q)=a$, หรือ $b\bmod q=a$.
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
