ถอดรหัสข้อความเข้ารหัสในระบบเข้ารหัสของ ElGamal

ฉันเป็นนักศึกษาสาขาวิทยาการคอมพิวเตอร์ที่กำลังแก้ปัญหาเกี่ยวกับการเข้ารหัส (ปัญหาที่ใช้งานได้จริงแต่ติดอยู่ที่ส่วนคณิตศาสตร์)

โดยทั่วไป สมมติว่าเราได้รับข้อความที่เข้ารหัสโดยใช้ระบบเข้ารหัสลับของ ElGamal และเป้าหมายของเราคือถอดรหัสและกู้คืนข้อความทั้งหมด

ข้อความธรรมดาเริ่มต้นเป็นลำดับ $p_1p_2\ldots p_m$. เราได้รับรหัสสาธารณะ SHA256 เวอร์ชันแฮช$(g^s)$ (ดังนั้น $s$ เป็นคีย์ส่วนตัวและ $g^s$ ของประชาชน) สำหรับการเข้ารหัสกล่าวกันว่า $r_1$ ค่าจะถูกสุ่มตัวอย่างอย่างสม่ำเสมอและจากนั้นสำหรับค่าที่กำหนด $u\in\mathbb{Z}_q$, $r_i=u^{i-1}r_1$ สำหรับส่วนที่เหลือทั้งหมด $i$'s. ข้อความที่เป็นตัวเลขนั้น $c_i=(g^{r_i},p_ig^{r_is})_{i\in[m]}$.

โดยรวมแล้วเราได้รับ $p$, $คิว$, $g$, $u$กุญแจสาธารณะที่แฮช $H$ และข้อความเข้ารหัส $c_i$ เป็นทูเพิล

ปัญหาที่ฉันมีคือฉันไม่เห็นจริงๆ ว่าเราต้องทำการคำนวณอะไรบ้างเพื่อกู้คืนลำดับดั้งเดิมทั้งหมด ผู้ช่วยคนหนึ่งบอกให้ฉันไปหาบ้าง $p_i$'s แล้วใช้มันเพื่อถอดรหัสรหัส แต่ฉันไม่เห็นว่าสิ่งนั้นนำฉันไปที่ไหน เดอะ $r$ไม่เป็นที่รู้จักและแม้ว่าเราจะรู้ $g^{r_i}$เนื่องจากเราได้รับค่าที่ค่อนข้างมาก เราจึงไม่สามารถคำนวณบันทึกได้

พูดตามตรงฉันค่อนข้างหลงทางที่นี่ (ฉันไม่มีพื้นฐานด้านพีชคณิตมากนัก) ดังนั้นถ้าใครมีคำแนะนำเกี่ยวกับสิ่งที่ฉันควรทำ ฉันจะขอบคุณจริงๆ

ขอบคุณ :)

คุณควรพยายามหา $r_{1}$. สำหรับสิ่งนี้ลองดูว่ามีความสัมพันธ์ระหว่าง $c_{i}$ และ $c_{j}$โดยมากอยู่ระหว่าง $g^{r_{i}}$ และ $g^{r_{j}}$. บางทีคุณอาจพบ $ค$ ดังนั้น $g^{c}=g^{r_{i}}/g^{r_{j}}$. จากนั้นคุณสามารถคำนวณ $ก^{s}$