ฉันคิดว่าฉันน่าจะพลาดคำๆ นี้ไปเพราะการค้นหาสิ่งนี้ได้ผลลัพธ์ที่ไม่แม่นยำนัก ฉันต้องการคำนวณความปลอดภัย n-bit ของ Paillier vs ElGamal กับ EC ElGamal เมื่อฉันใช้คีย์ x-bit
นี้ กระดาษระบุว่า "เพื่อให้ได้ระดับความปลอดภัย 128 บิต ปกติจะใช้ 4096 บิต p และ 256 บิต q ใน ElGamal ในขณะที่ใน Paillier ขนาด n จะถูกเลือกให้เป็น 4096 บิต"
ฉันจะคำนวณค่าที่จำเป็นสำหรับการรักษาความปลอดภัย 256 บิตได้อย่างไร มันแค่คูณสองที่นี่?
TLDR: ขนาดของกลุ่ม/เสียงเรียกเข้าถูกกำหนดโดยเร็วที่สุด เป็นที่รู้จักในปัจจุบัน การโจมตี (ตามที่อธิบายไว้ใน นี้ บทความวิกิพีเดีย).
รายละเอียด. สำหรับกรณีเข้าสู่ระบบแบบไม่ต่อเนื่อง $\mathbb{Z}_p^*$ และการแยกตัวประกอบ $\mathbb{Z}_N^*$อัลกอริทึมที่เร็วที่สุดในปัจจุบันคือ ตะแกรงฟิลด์ตัวเลขทั่วไป (ก.น.ฟ.). GNFS มีรันไทม์ (โดยประมาณ) $L_n(1/3,2)$, ที่ไหน $$L_n(\alpha,c):=e^{(c+o_n(1))n^\alpha\ln^{1-\alpha}(n)}$$ คือ $L$- สัญกรณ์ และ $n$ หมายถึงความยาวบิตของ (การแสดงมาตรฐานของ) $p$ หรือ $N$ (เช่น., $\lceil(\log(p)\rceil$ และ $\lceil(\log(N)\rceil$ตามลำดับ).$^*$ เนื่องจาก $ข$บิตความปลอดภัย สำหรับโครงร่างหมายความว่าควรใช้อัลกอริทึมใดๆ $2^b$ การดำเนินการเพื่อทำลายมันเพื่อคำนวณ $n$ สำหรับ $\mathbb{Z}_p^*$ และ $\mathbb{Z}_N^*$ ที่ประสบความสำเร็จ $128$ความปลอดภัย -bit หนึ่งต้องแก้ปัญหา $$2^{128}\ประมาณ e^{2n^{1/3}\ln^{2/3}(n)}\ซ้ายขวาลูกศร n\ln^2(n)\ประมาณ64^3.$$ สิ่งนี้จะให้ตัวเลขของ ball-park ว่าขนาดของโมดูลัสควรเป็นอย่างไร - ตามที่คำนวณ นี้ คำตอบนี้จะกลายเป็นประมาณ $3072$ บิต (หรือ $4096$ บิตที่จะอยู่ในด้านที่ปลอดภัยกว่า?) เนื่องจากเราไม่ทราบวิธีใดที่ดีกว่าในการแก้ปัญหา DDH/CDH (ปัญหาที่อยู่ภายใต้โครงร่างประเภท El-Gamal) มากกว่าการคำนวณบันทึกแยก El-Gamal ใน (อ้างอิง) $\mathbb{Z}_p^*$ ต้องปรับใช้กับจำนวนเฉพาะ $\ประมาณ3072/4096$ บิต
ในทำนองเดียวกันเนื่องจากเราไม่ทราบวิธีที่ดีกว่าในการแก้ปัญหา การตัดสินใจปัญหาเศษเหลือกำลังสอง ใน $\mathbb{Z}_{N^2}^*$ (ปัญหาที่อยู่ภายใต้ ระบบเข้ารหัสของ Paillier) กว่าจะแยกตัวประกอบ $N$ด้วยข้อโต้แย้งเดียวกันข้างต้น เราต้องทำงาน $N$ ขนาด $\ประมาณ 3072/4096$ บิต
สำหรับบันทึกไม่ต่อเนื่องในเส้นโค้งวงรี ฉันเชื่อว่าเราไม่รู้อะไรดีไปกว่าอัลกอริทึมบันทึกไม่ต่อเนื่องทั่วไป (เช่น โรของพอลลาร์ด) ซึ่งทำงานในไทม์สแควร์รูทขนาดของกลุ่ม ดังนั้นสำหรับ $128$- ความปลอดภัยของ EC-El-Gamal นั้นเพียงพอแล้วที่จะทำงานกับเส้นโค้งวงรีในฟิลด์ขนาด $2^{256}$. (นี่ก็หมายความว่า EC-El-Gamal มีประสิทธิภาพในการสื่อสารมากกว่า El-Gamal อย่างมากใน $\mathbb{Z}_p^*$.)
$^*$GNFS ดั้งเดิมเป็นแบบฮิวริสติก แต่ตามที่ @djao ชี้ให้เห็น (ดู นี้ ความคิดเห็น) มีตัวแปรที่พิสูจน์ได้ซึ่งทำงานใน $\ประมาณ L_n(1/3,3)$.
ความปลอดภัย n-บิตของอัลกอริทึมแต่ละรายการคำนวณผ่าน "วิธีการโจมตีที่ดีที่สุด" ตัวอย่างเช่น RSA ขึ้นอยู่กับปัญหาการแยกตัวประกอบและสามารถแก้ไขได้ด้วยอัลกอริทึม "Number Field Sieve" ดังนั้นเราจึงใช้ "ความซับซ้อนในการคำนวณ" ของ NFS เพื่อกำหนดระดับความปลอดภัย n-bit ของ RSA สำหรับฟังก์ชันแฮชการเข้ารหัส เราใช้ "การโจมตีวันเกิด" เพื่อคำนวณความปลอดภัยแบบ n-bit เป็นต้น
ไม่มีคำตอบเดียวง่ายๆ ความปลอดภัย n-bit หมายถึงลอการิทึมฐาน 2 (ปกติเขียนแค่ $\log$) ของจำนวน "การดำเนินการ" ที่จำเป็นในการทำลายสิ่งดั้งเดิม
สำหรับการเข้ารหัสแบบสมมาตร เช่น AES-128 โดยปกติแล้ว "การดำเนินการ" จะเป็นการเข้ารหัสหรือถอดรหัสแบบทดลอง ซึ่งมากกว่ารอบ CPU เดียว AES-128 โดยทั่วไปมีความปลอดภัย 128 บิตเนื่องจากมี $2^{128}$ คีย์ที่เป็นไปได้ และไม่มีการโจมตีทั่วไปใดที่เร็วกว่าการลองใช้คีย์ทั้งหมด และ $\log(2^{128})=128$.
ระบบอสมมาตรเช่น Paillier, ElGamal และ EC ElGamal ล้วนมีการโจมตีเร็วกว่าการลองใช้คีย์ที่เป็นไปได้ทั้งหมด ดังนั้นในการคำนวณ "การรักษาความปลอดภัยแบบสมมาตรที่เทียบเท่า" เป็นบิต คุณต้องคำนวณต้นทุนของการโจมตีที่รู้จักกันดีที่สุดเทียบกับพารามิเตอร์ที่ใช้
คุณต้องตัดสินใจด้วยว่าค่าใช้จ่ายของ "ปฏิบัติการ" ในการโจมตีดังกล่าวนั้นแตกต่างอย่างมากจาก "ปฏิบัติการ" ที่โจมตีรหัสสมมาตรที่คุณกำลังเปรียบเทียบหรือไม่ และถ้าเป็นเช่นนั้น ให้ปรับขนาดจำนวนปฏิบัติการของคุณอย่างเหมาะสมข้อพิจารณาประการสุดท้ายคือเหตุใดระบบอสมมาตรอย่าง ElGamal จึงมีความปลอดภัยเพียงครึ่งเดียวจากการโจมตีโดยคอมพิวเตอร์ควอนตัมที่แก้ไขข้อผิดพลาดเพื่อวัตถุประสงค์ทั่วไป เช่นเดียวกับที่ทำกับคอมพิวเตอร์ในปัจจุบัน
ฉันไม่คุ้นเคยกับความล้ำสมัยในการโจมตีระบบสามระบบดังกล่าวเป็นพิเศษ ดังนั้นฉันจึงไม่สามารถให้ตัวเลขที่สมบูรณ์ได้ นี่เป็นเพียงคำตอบบางส่วนสำหรับคำถามที่ถาม
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
