ในการเข้าถึง Oracle ของ Diffie Hellman

เราติดตั้งฟังก์ชันที่รับอินพุต 3 ตัว $\mathrm{CDH}(h,h^a,h^b)$ ที่กลับมา $h^{ab}$. เราเรียกมันว่าอินพุต $\mathrm{CDH}(g^x,g,g^{xy})$. ถ้าเราเขียน $a$ สำหรับ mod ของสารตกค้าง $p-1$ ดังนั้น $ax\equiv 1\pmod{p-1}$ เราจะเห็นว่าถ้าเรากำหนด $h$ เป็น $g^x\mod p$ แล้ว $h^a=g^{ax}=g\mod p$ และ $h^y=g^{xy}\mod p$. ดังนั้นสำหรับตัวเลือกนี้ $h$ เรามี $\mathrm{CDH}(g^x,g,g^{xy})=\mathrm{CDH}(h,h^a,h^y)=h^{ay}=g^{axy}=g ^y\mod p$.

มีริ้วรอยเล็กน้อยเมื่อ $x$ ไม่ใช่ mod ที่กลับด้านได้ $p-1$สำหรับในกรณีนี้ $y$ ไม่ได้ถูกกำหนดโดยเฉพาะโดย $ก^{xy}$. ถ้าพูดให้ถูกคือ $\mathrm{GCD}(x,p-1)=\ell$ จากนั้นค่าทั้งหมด $y'=y+k\ell$ สำหรับ $k=1,\ldots (p-1)/\ell$ ทุกคนจะมี $g^{xy}=g^{xy'}\mod p$ ดังนั้น $g^{y'}$ จะเป็นคำตอบที่ถูกต้องสำหรับข้อใดข้อหนึ่ง $y'$.

CDH oracle ของเราอาจถูกกำหนดในลักษณะที่ไม่ยอมรับ $g$ เป็นอาร์กิวเมนต์ที่สองในกรณีที่ $h=g^x$ และ $x$ มีปัจจัยร่วมกับ $p-1$, เพราะ $g$ ไม่นอนใน $\langle ชั่วโมง\range$. ในกรณีเช่นนี้ เราสามารถใช้โดยพลการ $\ell$รากของ $ก^x$ และ $ก^{xy}$ และใช้สิ่งเหล่านี้เป็นอาร์กิวเมนต์ที่สองและสามและดำเนินการตามเดิม แต่สังเกตคำตอบที่เป็นไปได้หลายข้อ

นอกเหนือจากเรื่องน่าขบขันแล้ว หากเรามีค่าสาธารณะและแบ่งปันความลับสำหรับการแลกเปลี่ยน Diffie-Hellman แต่ไม่รู้กำเนิด (เช่น เรารู้ $ก^x$, $g^y$ และ $ก^{xy}$ แต่ไม่ $g$) จากนั้นออราเคิลดังกล่าวสามารถกู้คืนได้ $g$ เนื่องจาก $\mathrm{CDH}(g^{xy},g^x,g^y)=g$.