ใช้ ElGamal แทน RSA ใน FDH

ในการลองสิ่งที่พยายาม เราต้องกำหนด $H$ พร้อมเอาต์พุตในชุดข้อความไซเฟอร์ ElGamal ทั้งหมด เป็นไปได้และฉันถือว่าสิ่งนี้ในย่อหน้าถัดไป

ตรงกันข้ามกับ RSA แบบเรียน การเข้ารหัส ElGamal ไม่ใช่ฟังก์ชัน: การเข้ารหัสข้อความธรรมดาที่กำหนดซ้ำๆ ดังนั้น เมื่อเราพยายามตรวจสอบลายเซ็นตามคำถาม จึงไม่มีเหตุผลใดที่การเข้ารหัสลายเซ็นจะให้แฮชดั้งเดิม และ (มีความเป็นไปได้สูง) การยืนยันลายเซ็นจะล้มเหลว ระบบลายเซ็นที่พิจารณาในคำถามไม่น่าเชื่อถือ

เพื่อความง่าย ให้พิจารณา ElGamal ใน โมดูโลกลุ่มคูณ $p$, ข้อสังเกต $\mathbb Z_p^*$, กับ $p$ และ $(p-1)/2$ นายกและ $G$ ดังนั้น $G^{(p-1)/2}\bmod p\,=\,p-1$:

• รหัสส่วนตัวเป็นความลับแบบสุ่ม $x\in[0,p-1)$กุญแจสาธารณะคือ $X:=G^x\bmod p\in[1,p)$.
• การเข้ารหัสข้อความธรรมดาโดยพลการ $M\in[1,p)$ ไป
  • สร้างความลับแบบสุ่มชั่วคราว $y\in[0,p-1)$
  • คำนวณ $Y:=G^y\bmod n$
  • คำนวณ $Z:=M\cdot X^y\bmod n$
  • เอาต์พุตไซเฟอร์เท็กซ์ $(ย,Z)$
• ถอดรหัสไซเฟอร์เท็กซ์โดยพลการ $(Y,Z)\in[1,p)\times[1,p)$ เอาต์พุต $M':=Y^{n-1-x}\cdot Z\bmod n$.

$M'=M$ ไม่ว่า $y$. คำใบ้พิสูจน์: ทฤษฎีบทเล็กของแฟร์มาต์.

ตรงกันข้ามกับหนังสือเรียน RSA ElGamal เวอร์ชันนี้เกือบจะเป็น IND-CPAแต่ก็ไม่เชิง คำใบ้พิสูจน์: พิจารณาความสัมพันธ์ระหว่าง สัญลักษณ์เลเจนเดร ของ $\left(\frac M p\right)$, $\left(\frac X p\right)$, $\left(\frac Y p\right)$. เราเพิกเฉยต่อปัญหาเล็กน้อยต่อไปนี้

หนึ่งในความพยายามที่ง่ายที่สุดในการแก้ไขปัญหาที่เกิดขึ้นในย่อหน้าที่สองของคำตอบนี้คือการแก้ไข $y=1$, ดังนั้น $Y=G$. รูปแบบลายเซ็นของคำถามสามารถใช้แฮชได้ $H$ ด้วยเอาต์พุต $H(ม)$ ในโดเมนแบบเต็ม $[1,p)$ เช่น $$H(m):=\big(\operatorname{SHAKE256}(m,b)\bmod p-1\big)+1\text{ กับ }b=64\left\lceil\log_2(p)/64 +2\right\rceil$$ แล้ว

• รหัสส่วนตัวและรหัสสาธารณะอยู่ในการเข้ารหัส
• ลายเซ็นของ $m$ เป็น $\sigma:=G^{n-1-x}\cdot H(m)\bmod n$
• ตรวจสอบการตรวจสอบ $\sigma\cdot X\bmod n=H(m)$.

อย่างน้อยที่สุด การตรวจสอบก็สำเร็จโดยไม่มีการแก้ไข ดังนั้นรูปแบบลายเซ็นนี้จึงฟังดูดี แต่ก็ไม่ปลอดภัยแม้ตามเกณฑ์ที่ง่ายที่สุด ยูเอฟ-โคอา.

ความพยายามง่ายๆ อื่น ๆ ก็ล้มเหลวเช่นกัน

• การทำ $y$ ความลับที่เพิ่มในคีย์ส่วนตัวด้วย $Y:=G^y\bmod n$ และ $Y':=X^y\bmod n$ เพิ่มไปยังรหัสสาธารณะ
• การทำ $y$ แฮชของข้อความ $m$
• การทำ $Y$ แฮชของข้อความ $m$
• เห็นได้ชัดว่า อะไรก็ตามที่ทำงานในกลุ่มตามอำเภอใจตามที่การเข้ารหัส ElGamal ใช้ และลายเซ็นเป็นองค์ประกอบกลุ่มเป็นเอาต์พุตการถอดรหัส ElGamal

แม้ว่าสิ่งนี้จะใช้ไม่ได้กับ ElGamal แต่ปัญหาอื่นเกิดขึ้นเมื่อพยายามสร้างลายเซ็นจากรูปแบบการเข้ารหัสคีย์สาธารณะทั่วไป และแฮชบนโดเมนข้อความเข้ารหัส: การถอดรหัสข้อความเข้ารหัสตามอำเภอใจอาจล้มเหลว (และใช้กับระบบที่ใช้งานได้จริงเช่น RSA-สศอ, RSAES-สศอ, RSAES-PKCS1-v1_5). นั่นเป็นคุณสมบัติที่น่าสนใจของ IND-CCA ความปลอดภัย.

ไม่มีวิธีทั่วไปในการสร้างลายเซ็นที่ปลอดภัยจากการเข้ารหัสคีย์สาธารณะที่ปลอดภัย. แม้แต่ลายเซ็น RSA-FDH ก็ยังใช้งานไม่ได้: มันสร้างลายเซ็นจากการเรียงสับเปลี่ยนทางเดียวและแฮชบนโดเมนของการเรียงสับเปลี่ยน