รูปแบบการเข้ารหัสแบบอสมมาตรพร้อมเอาต์พุตที่สั้นที่สุดสำหรับการเข้ารหัสข้อมูล 1 ไบต์

จากหัวของฉัน ฉันเสนอรูปแบบ EC-ElGamal นี้บน Elliptic Curve มาตรฐาน 256 บิต โดยใช้แฮชและ XOR สำหรับส่วนการเข้ารหัส (เกือบครึ่งหนึ่งของขนาดไซเฟอร์เท็กซ์เมื่อเทียบกับตำราเรียน EC-ElGamal) และการแลกเปลี่ยนงาน/พื้นที่อย่างง่าย -ปิด เพื่อบีบข้อความไซเฟอร์เท็กซ์ขนาด 32 ไบต์เพิ่มเติม $m$ ของ $ข$ บิตด้วยค่าคงที่ขนาดเล็ก $ข$ (เช่น. $b=8$).

• ใช้เส้นโค้งวงรีมาตรฐานบนฟิลด์ $\mathbb F_p$ ด้วยเครื่องกำเนิดไฟฟ้า $G$ ของการสั่งซื้อ $n$, กับ $p$ และ $n$ ไพรม์ 256 บิตและ (คาดเดา) ความปลอดภัย 128 บิต secp256r1 (หรือที่เรียกว่า NIST P-256) และ secp256k1 มีคุณสมบัติ ฉันอ้างถึง วินาที 1 ต่อ 2 สำหรับคณิตศาสตร์ ECC และสัญกรณ์
• การสร้างคีย์:
  • เลือกคีย์ส่วนตัว $d$ สุ่มในช่วงเวลา $[1,น)$
  • คำนวณรหัสสาธารณะ $Q\gets d\,G$
• การเข้ารหัสของ $ข$- ข้อความธรรมดาบิต $m$
  • เลือก $e$ สุ่มในช่วงเวลา $[1,2^{32})$
  • คำนวณ $F\gets e\,G$
  • เลือก $k$ สุ่มในช่วงเวลา $[1,น)$
  • คำนวณ $R\gets k\,G$
  • ในขณะที่ $R_x\not\equiv0\pmod{2^b}$
    • คำนวณ $R\ได้ R+F$ และ $k\ได้ k+e$ซึ่งรักษา $R=k\,G$
    • ถ้า $k\ge n$ RNG ที่เลือก $k$ มักจะหัก; ยกเลิกหรือเริ่มการเข้ารหัสใหม่
  • ถ้า $R_y$ เป็นชุดที่แปลก $R_y\ได้ p-R_y$ และ $k\gets n-k$ซึ่งรักษา $R=k\,G$
  • คำนวณ $S\gets k\,Q$ (จุดลับที่ใช้ร่วมกัน)
  • คำนวณ $u\gets \operatorname{SHA-256}(S_x)\bmod2^b$, ที่ไหน $S_x$ แสดงเป็นการทดสอบไบต์แบบ 32 ไบต์
  • คำนวณ $v\gets u\oบวก m$
  • เอาต์พุตไซเฟอร์เท็กซ์ 256 บิตประกอบด้วย $256-b$ บิตสำหรับ $R_x$ ด้วยลำดับที่ต่ำ $ข$ บิตถูกลบออก (มีค่าเป็นศูนย์โดยการก่อสร้าง) และ $ข$ บิตสำหรับ $v$
• ถอดรหัส:
  • จากสารสกัดไซเฟอร์เท็กซ์ $R_x$ (ใส่ $ข$ บิตลำดับต่ำที่ศูนย์) และ $v$
  • คำนวณ $R_y$ การจับคู่ $R_x$ (นั่นเป็นเทคนิคมาตรฐานในการเลิกทำการบีบอัดจุด ดู Sec1v2 §2.3.4, ขั้นตอนที่ 2.4.1); หากล้มเหลวให้ยกเลิกการถอดรหัส
  • ถ้า $R_y$ เป็นชุดที่แปลก $R_y\ได้ p-R_y$
  • คำนวณ $S\gets d\,R$ (จุดลับที่ใช้ร่วมกัน)
  • คำนวณ $u\gets \operatorname{SHA-256}(S_x)\bmod2^b$, ที่ไหน $S_x$ แสดงเป็นการทดสอบไบต์แบบ 32 ไบต์
  • คำนวณและส่งออกข้อความธรรมดาที่ถอดรหัสแล้ว $m\gets u\oplus v$

ฉันคาดเดา IND-CCA1 (ดังนั้น IND-CPA) ความปลอดภัยถึงระดับ 128 บิตภายใต้สมมติฐานที่สมเหตุสมผล (ความแข็งของตัวแปรของปัญหา Diffie-Hellman ที่ตัดสินใจได้สำหรับ Elliptic Curve และ SHA-256 จำลองเป็นออราเคิลแบบสุ่ม) มีการโจมตีเล็กน้อยต่อ IND-CCA2 (ดังนั้น การเข้าถึง Oracle ถอดรหัสจะประนีประนอมความลับของข้อความที่ผ่านมา แม้ว่า Oracle ถอดรหัสจะขึ้นบัญชีดำข้อความไซเฟอร์ดั้งเดิม ซึ่งไม่ใช่ปัญหาในทางปฏิบัติ)

ระวังว่ารหัสจะอ่อนได้เล็กน้อย สิ่งนี้ทำให้ฝ่ายตรงข้ามสามารถพลิกบิตที่ต้องการในข้อความธรรมดาโดยแก้ไขบิตเหล่านี้ในข้อความไซเฟอร์ นี่อาจเป็นปัญหาในทางปฏิบัติ การลดระดับบางอย่างเป็นไปได้โดยการแทนที่ $u\oplus\ldots$ โดย รูปแบบการรักษาการเข้ารหัส ด้วยขนาดที่กว้างขึ้น $u$ เป็นกุญแจ; หรือ/และงานอื่นๆ หรือ/และพื้นที่

การวนลูปขณะเข้ารหัสเป็นการแลกเปลี่ยนเวลา/ช่องว่าง การค้นหา $k$ โดยการแจกแจงเพื่อให้เป็น $x$ ประสานงาน $R_x$ มี $ข$ บิตลำดับต่ำที่ศูนย์ซึ่งไม่จำเป็นต้องส่ง การค้นหาได้รับการปรับให้เหมาะสมกับความต้องการ $\ประมาณ2^b$ การเพิ่มจุด แต่สำหรับ $ข$ เริ่มประมาณ $8$ สิ่งนี้จะกลายเป็นความเจ็บปวด การใช้ที่เพิ่มขึ้นอย่างลับๆ $e$ และการจับคู่ $F=e\,G$ เป็นการดีที่ได้ผ่านเข้ารอบชิงชนะเลิศ $k$ เครื่องแบบมากกว่า (ดูหมายเหตุ) แต่ฉันรู้ว่าไม่มีการโจมตีถ้าเรารับ $e=1$ และด้วยเหตุนี้ $F=G$. การเพิ่มความลับอาจช่วยลดการโจมตีช่องทางด้านข้างได้

หากเราต้องการหลีกเลี่ยงการแลกเปลี่ยนเวลา/พื้นที่บางส่วนหรือทั้งหมด เราสามารถทำได้

• เพิ่มขนาดไซเฟอร์เท็กซ์เล็กน้อย
• หรือ/และร่วมสร้างเส้นโค้งแบบกำหนดเอง ด้วยขนาดบิตของ $n$ และ $p$ ลดลงสองสามบิตจาก 256 สำหรับทุกๆ 1 บิตของการรักษาความปลอดภัยที่เรายกเลิก เราจะได้ประมาณ 2 สำหรับ $n$ และ $p$ดังนั้นในบิตไซเฟอร์เท็กซ์ หรือการเดาน้อยลง 4 เท่าในลูป while และสำหรับ secp256r1 การโจมตีที่เป็นที่รู้จักดีที่สุดนั้นจำเป็นต้องมี $>2^{140}$ การดำเนินการบิต (ขึ้นอยู่กับการคาดคะเนแบบอนุรักษ์นิยมของสิ่งที่คล้ายกัน เรียกร้อง ของ $>2^{140}$ สำหรับ Ed25519)

หมายเหตุ: ในตำรา Diffie-Hellman หรือ ElGamal เราเลือก $k$ เข้าไว้ด้วยกัน $[0,น)$. ตัวแปรของเราจำกัดไว้ที่ $k$ กับ $k\,G$ มี $x$ ประสานกับลำดับต่ำ $ข$ บิตที่ศูนย์ โดยโต้แย้งทางสถิติมีประมาณ $n/2^b$ เช่น $k$. เราอยากจะเลือก $k$ อย่างสม่ำเสมอในชุดย่อยนี้ $[0,น)$. วิธีที่ง่ายที่สุดคือการทำซ้ำแบบสุ่ม $k$แต่นั่นมีค่าใช้จ่ายในการคำนวณที่ห้ามปรามสำหรับการคูณจุด $R\gets k\,G$. เราประหยัดสิ่งนี้ด้วยการย้ายจากผู้สมัครคนเดียว $k$ ถัดไปโดยเพิ่มขึ้นคงที่ $e$อนุญาตให้ปรับปรุง $R$ โดยการเพิ่มจุดเดียว $R\ได้ R+F$.

ถ้าเราใช้คง $e=1$แล้ว $k$ ที่เลือกโดยลูป while จะมีคุณสมบัติที่แตกต่าง (สำหรับคนที่รู้ $k$): ความน่าจะเป็นที่ก $k$ ถูกเลือกเป็นสัดส่วนกับ $เจ$ คำนวณได้จาก $k$ มีขนาดเล็กที่สุด $j>0$ ดังนั้น $k-j$ อยู่ในเซตย่อย (หรือ $k+1$ หากไม่มีสิ่งนั้น $เจ$ซึ่งเกิดขึ้นสำหรับหนึ่งเดียว $k$ ในชุดย่อย) ปัญหาคล้ายกับการเลือกจำนวนเฉพาะที่ไม่สม่ำเสมอซึ่งได้จากการเลือกจุดเริ่มต้นแบบสุ่มและค้นหาจำนวนเฉพาะถัดไป

การเลือกสาธารณะคงที่ $e$ ไม่ได้แก้ปัญหาเพราะคำจำกัดความของ $เจ$ สามารถนำไปปรับใช้กับ $k-e\,j$ ในชุดย่อย อย่างไรก็ตามการเลือกความลับแบบสุ่ม $e$ สำหรับแต่ละทางเลือกของ $k$ ทำ. เทคนิคที่คล้ายกันนี้ถูกใช้ในเครื่องกำเนิดไพรม์แบบสุ่มสำหรับ RSA ฉันไม่มีการอ้างอิง แต่ข้อโต้แย้งคือศัตรูไม่รู้ $e$ ไม่ทราบว่าอะไร $e$ ใช้สำหรับการทดสอบ พวกเขาสามารถทดสอบได้ทั้งหมด $e$ และรวมผลลัพธ์เข้าด้วยกัน แต่แล้วการทดสอบของพวกเขาก็เต็มไปด้วยเสียงรบกวน

ฉันเลือกขีดจำกัดบนของช่วงเวลา $[1,2^{32})$ สำหรับ $e$ เพื่อให้การคำนวณ $F\gets e\,G$ มีต้นทุนที่คาดไว้เล็กน้อยเมื่อเทียบกับ $R\gets k\,G$. ฉันมั่นใจ (โดยไม่มีหลักฐานหรือการอ้างอิง) นี้มากเกินพอที่จะทำให้มีอคติในการเลือก $k$ ไม่สามารถตรวจจับได้ในทางปฏิบัติแม้แต่ฝ่ายตรงข้ามที่สมมุติฐานก็รู้ $k$; และศัตรูที่แท้จริงเท่านั้นที่จะได้รับ $k$ ผ่านช่องทางด้านข้าง

ความคิดสุดท้าย: เราสามารถหน่วงความกลัวใด ๆ ที่เกณฑ์ $R_x\equiv0\pmod{2^b}$ สร้างจุดอ่อนโดยปรับให้เป็น: ต่ำ $ข$ บิตของ $R_x$ เป็นฟังก์ชั่นบางอย่าง (มีการกระจายแบบสม่ำเสมอ) ของบิตอื่น ๆ $R_x$. ก $ข$-bit CRC จะทำ เครื่องรับสามารถสร้างบิตลำดับต่ำที่จำเป็นขึ้นมาใหม่ได้ $R_x$ โดยใช้ฟังก์ชันนี้