พารามิเตอร์ความปลอดภัย $1^\kappa$ คืออะไร

ช่างมันเถอะ $K$ อัลกอริทึมการสร้างคีย์ที่ใช้ $(ก,ง)$ เป็นอินพุตด้วย $k$ เป็นความยาวบิตสำหรับ $n=pq$ กับ $p,q \in \mathbb{P}$ และ $d=|p-q|$ เป็นระยะทางขั้นต่ำระหว่าง $p$ และ $คิว$ (อ.ส.).พารามิเตอร์ความปลอดภัยจะเป็นอย่างไร $1^\กัปปะ$?

มันจะเป็น $\kappa=k+d$ หรือเท่านั้น $\กัปปะ=k$ และถ้าเป็นกรณีนี้ขึ้นอยู่กับอะไร?

ฉันค้นหาลิงก์ต่อไปนี้และไม่พบคำตอบสำหรับคำถามของฉัน:

แสดงออกอย่างไร $1^n$ หมายถึงอาร์กิวเมนต์ของฟังก์ชันหรือไม่ เหตุใดการสร้างคีย์จึงใช้อินพุต $1^k$และฉันจะนำเสนอในทางปฏิบัติได้อย่างไร

ด้วยเหตุผลใน ความคิดเห็นของฉัน ฉันจะถือว่าเราเปลี่ยนคำถามเพื่อกำหนด $δ$ กับ $2^\delta<\lvert p-q\rvert$, และ $\kappa=k+\delta$. ม.ป.ป.186-4 ตัวอย่างเช่นการสร้างคีย์จะใช้ $k=3072$ และ $\delta=k/2-100=1436$.

ฉันไม่พบข้อมูลอ้างอิงใด ๆ ที่กล่าวถึงความปลอดภัย RSA แบบซีมโทติคด้วยสัญกรณ์ที่ชอบ $1^k$ ที่ระบุขั้นต่ำ $\lvert p-q\rvert$. นั่นเป็นเพราะ:

• ที่เพิ่มขึ้น $\เดลต้า$ เมื่อผ่านจุดใดจุดหนึ่งไป แสดงว่าความปลอดภัยลดลง เช่น. สำหรับ $k=3072$ (ซึ่งจะให้การรักษาความปลอดภัยแบบสมมาตรประมาณ 128 บิต) และ $δ=1912$ เราก็จะมี $\min(p,q)<2^{161}$ และ ECM ของ Lentra ก็น่าจะทำให้สามารถดึงตัวประกอบของ $n$.
• ข้อโต้แย้งง่ายๆที่เพิ่มขึ้น $\เดลต้า$ การปรับปรุงความปลอดภัยมีข้อบกพร่อง
• $\delta=0$ ก็เชื่อได้อยู่ดี
• เหตุผลทางประวัติศาสตร์ที่จะแนะนำขอบเขตล่างสำหรับ $\lvert p-q\rvert$ คือการแยกตัวประกอบของแฟร์มาต์มีค่าใช้จ่ายเกี่ยวกับสัดส่วน $(p-q)^2/n$ คูณพหุนามบางตัวใน $k$, ดังนั้น $\lvert p-q\rvert$ ต้องไม่เล็กเกินไป มันเพิ่มขึ้นจากข้อเท็จจริงนั้นไปสู่ข้อสรุปว่าจำเป็นต้องระบุขั้นต่ำที่ชัดเจน $\lvert p-q\rvert$แม้ว่าจะเห็นได้ชัดว่าเพียงพอที่จะระบุได้ว่า $p$ และ $คิว$ ถูกเลือกอย่างอิสระและสม่ำเสมอระหว่างจำนวนเฉพาะในบางช่วงเวลาเช่น $[2^{(k-1)/2},2^{k/2})$ เพื่อให้แน่ใจว่าการแยกตัวประกอบของแฟร์มาต์จะสิ้นหวังไม่ว่าเมื่อไรก็ตาม $k$ มีขนาดใหญ่พอที่จะต้านทานได้ จีเอ็นเอฟเอส (หรือ PPMPQSซึ่งเป็นที่รู้จักกันมานานในปี 1998 เมื่อมีการลงมติที่โต้แย้งใน ANS X9.31)

ตามที่ร้องขอใน ความคิดเห็น ฉันจะถือว่ามีเหตุผลบางอย่างที่จะระบุ $\เดลต้า$และที่เพิ่มขึ้น $\เดลต้า$ เพิ่มความปลอดภัยในบางโดเมน เพื่อไม่ให้ขัดแย้งกับข้อเท็จจริงในประเด็นแรกข้างต้น ฉันจะถือว่า $0\le\delta\le\alpha\,k+\beta$ สำหรับของจริง $\alpha$ และ $\เบต้า$ กับ $\alpha\in[0,1)$. ภายใต้สมมติฐานดังกล่าว มันสมเหตุสมผลที่จะกำหนด $\kappa=k+\delta$และใช้เป็นพารามิเตอร์ความปลอดภัย

เราสามารถกำหนดการสร้างคีย์ RSA สำหรับจำนวนเต็มคี่คงที่ $e>1$ เป็น: บนอินพุต $1^\กัปปะ$

1. ในเวลาพหุนาม ให้เลือกจำนวนเต็ม $k$ และ $\เดลต้า$ กับ $\kappa=k+\delta$ และ $0\le\delta\le\alpha k+\beta$ (ล้มเหลวหากเป็นไปไม่ได้); วิธีที่เหมาะสม ได้แก่ $\delta\gets\left\lfloor\frac\alpha2\kappa\right\rfloor$ และ $k\gets\kappa-\delta$.
2. เลือก $p$ สุ่มอย่างสม่ำเสมอระหว่างจำนวนเฉพาะ $p$ ใน $[2^{(k-1)/2},2^{k/2})$ กับ $\gcd(p-1,e)=1$
3. เลือก $คิว$ สุ่มอย่างสม่ำเสมอระหว่างจำนวนเฉพาะ $คิว$ ใน $[2^{(k-1)/2},2^{k/2})$ กับ $\gcd(q-1,e)=1$ และ $2^\delta<\lvert p-q\rvert$.
4. คำนวณ $n\gets p\,q$ และ $d\gets e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$, ออกคีย์สาธารณะ $(น,อี)$ และคีย์ส่วนตัว $(น,ง)$.

เชื่อได้ว่า: สำหรับตัวเลือกที่ถูกต้องของ $e$ ในอัลกอริทึมการสร้างคีย์นี้ สำหรับพหุนามใดๆ $พี$ไม่มีอัลกอริทึม Probabilistic Polynomial Time ที่จะเกิดขึ้นเมื่อใด $\กัปปะ$ การเติบโตทำลายการเข้ารหัส RSA ด้วยความน่าจะเป็นที่ไม่หายไปภายในเวลา $P(\กัปปะ)$.

การคาดคะเนที่เป็นไปได้นั้นแสดงให้เห็นโดยนัยโดยรูปแบบการคาดคะเน RSA ที่จัดขึ้นโดยทั่วไปและเรียบง่ายกว่าสำหรับเลขชี้กำลังสาธารณะคงที่/ขนาดเล็ก ซึ่งลบขั้นตอน (1.) แทนที่เงื่อนไข $2^\delta<\lvert p-q\rvert$ กับ $p\ne คิว$ ในขั้นตอนที่ (3.) และการนำไปใช้ $k$ ที่นั่น $\กัปปะ$. เราไม่มีข้อพิสูจน์ว่าการคาดเดานั้นเทียบเท่ากัน แต่ไม่มีเหตุผลบังคับให้เชื่ออย่างอื่น ดังนั้นผู้ปฏิบัติงานจำนวนมากและนักทฤษฎีส่วนใหญ่จึงใช้การคาดเดาที่ง่ายกว่า²

¹ ร่างหลักฐาน: เราถือว่ามีอยู่ $e$ และอัลกอริทึม $\คณิตศาสตร์ A$ ที่ทำลายการเข้ารหัส RSA ด้วยความน่าจะเป็นที่ไม่หายไปภายในเวลา $P(\กัปปะ)$ เมื่อใช้การสร้างคีย์ RSA กับ $2^\delta<\lvert p-q\rvert$. เราใช้ $\คณิตศาสตร์ A$ เพื่อสร้างอัลกอริทึม $\คณิตศาสตร์แคล A'$ วิงวอน $\คณิตศาสตร์ A$ เป็นโปรแกรมย่อยซึ่งเหมือนกัน $e$ ทำลายการเข้ารหัส RSA ด้วยความน่าจะเป็นภายในเวลาที่กำหนด $P'(k)$ เมื่อใช้การสร้างคีย์ RSA กับ $p\ne คิว$. ความน่าจะเป็นจะไม่หายไปเพราะ $p$ และ $คิว$ ตรงตามเงื่อนไขประกัน $\คณิตศาสตร์ A$ ทำงานด้วยความน่าจะเป็นที่เราจะลดขอบเขตและไม่หายไป เราสามารถจัดตั้ง $P'$ จาก $พี$, $\alpha$ และ $\เบต้า$และนั่น $P'$ ยังคงเป็นพหุนาม $\alpha<1$ เข้ามามีบทบาท

² มักจะเกิดภาวะ $p\ne คิว$ จะถูกลบออกด้วย ซึ่งทำให้เกิดความเป็นไปได้ที่การถอดรหัสล้มเหลวที่เกิดขึ้นสำหรับสัดส่วนที่หายไปของคีย์ที่สร้างขึ้น แต่คำจำกัดความบางอย่างของการเข้ารหัสไม่มีการยกเว้นสำหรับกรณีมุมดังกล่าว ซึ่งเป็นเหตุผลที่เราเก็บ $p\ne คิว$.