Score:0

พารามิเตอร์โดเมนในรูปแบบการระบุ Schnorr

ธง gb
Jan

ฉันเพิ่งศึกษารูปแบบการระบุตัวตนของ Schnorr หนังสือ Cryptography: Theory and Practice โดย Stinson และ Paterson ระบุสิ่งต่อไปนี้เกี่ยวกับพารามิเตอร์โดเมนในแผนการระบุตัวตนของ Schnorr:

แบบแผนต้องการหน่วยงานที่เชื่อถือได้หรือ TA ซึ่งเป็นผู้เลือกพารามิเตอร์ระบบทั่วไป (พารามิเตอร์โดเมน) สำหรับแบบแผนดังต่อไปนี้:

  1. $p$ เป็นจำนวนเฉพาะมาก (กล่าวคือ $p\ประมาณ 2^{2048}$).

  2. $คิว$ เป็นตัวหารที่สำคัญมากของ $p-1$ (เช่น., $q\ประมาณ 2^{224}$).

  3. $\alpha \in \mathbb{Z}_p^*$ มีคำสั่ง $คิว$

  4. $t$ เป็นพารามิเตอร์ความปลอดภัยเช่นนั้น $q>2^t$. (พารามิเตอร์ความปลอดภัยคือพารามิเตอร์ที่สามารถเลือกค่าได้เพื่อให้ระดับความปลอดภัยที่ต้องการในรูปแบบที่กำหนด ในที่นี้ ความน่าจะเป็นของฝ่ายตรงข้ามในการหลอกลวงอลิซหรือบ็อบคือ $2^{-t}$, ดังนั้น $t=80$ จะให้ความปลอดภัยเพียงพอสำหรับการใช้งานจริงส่วนใหญ่)

คำถามของฉันคือเราจะหาสิ่งนั้นได้อย่างไร $p$, $คิว$, $\alpha$ และ $t$? และทำไมถึงต้องมี $p\ประมาณ 2^{2048}$, $q\ประมาณ 2^{224}$ และ $t=80$?

Score:1
ธง ru

เราจะต้องมีการทดสอบเบื้องต้นที่มีประสิทธิภาพในการผลิต $p$ และ $คิว$. หากคุณพอใจกับจำนวนเฉพาะที่เป็นไปได้แล้ว มิลเลอร์-ราบิน การทดสอบจะเพียงพอสำหรับวัตถุประสงค์ในทางปฏิบัติส่วนใหญ่เขียน IsPrime() สำหรับการทดสอบ

ประการแรกเลือก $t$ ตามข้อกำหนดด้านความปลอดภัยของโครงการของคุณ มีโอกาสที่จะ $2^{-t}$ ที่ผู้หลอกลวงสามารถล้มล้างโครงการได้โดยการสุ่ม ดังนั้นการเลือก $t=80$ หมายความว่าแม้ว่าผู้โจมตีของคุณจะพยายามหลอกลวงระบบของคุณโดยการสุ่ม $2^{80}$ โดยเฉลี่ยแล้วพวกเขาจะทำสำเร็จเพียงครั้งเดียวเท่านั้น ปล่อยให้ศัตรู $2^{80}$ ความพยายามที่จะปลอมแปลงระบบของคุณไม่น่าจะเป็นจริงได้ ดังนั้น $t=80$ ถือว่าโอเคในเรื่องนี้

ตอนนี้เราพบว่า $คิว$ควรมีขนาดใหญ่พอที่ฝ่ายตรงข้ามไม่สามารถแก้ลอการิทึมที่ไม่ต่อเนื่องในกลุ่มตามอำเภอใจของ $คิว$ องค์ประกอบ (เช่น การใช้ ขั้นตอนทารกขั้นตอนยักษ์ วิธีการ) และยังมีขนาดใหญ่กว่านั้น $2^t$. ถ้า $q\ประมาณ 2^{224}$ จากนั้นประมาณ $2^{112}$ การดำเนินการกลุ่มจะต้องใช้วิธีนี้และอย่างน้อยที่สุด $2^{112}$ จำเป็นต้องมีการดำเนินการทางคอมพิวเตอร์สำหรับ BS-GS หากต้องการค้นหา 224 บิต $คิว$ สร้างตัวเลข 223 บิตแบบสุ่ม $n$ และปล่อยให้ $q_0=2^{223}+n$. คำนวณ IsPrime($q_0$) และถ้าสำเร็จให้ $q=q_0$ มิฉะนั้นเพิ่มขึ้น $q_0$ ทีละ 1 และทำซ้ำจนกว่าเราจะประสบความสำเร็จ

ตอนนี้เราพบว่า $p$ควรมีขนาดใหญ่พอที่ฝ่ายตรงข้ามไม่สามารถแก้โมดูโลลอการิทึมแบบไม่ต่อเนื่องได้ $p$ (เช่น การใช้ ตะแกรงช่องตัวเลข). ถ้า $p\ประมาณ 2^{2048}$ หลักเกณฑ์ของ NIST แนะนำว่าอย่างน้อย $2^{112}$ จะต้องมีการดำเนินการคำนวณ หากต้องการค้นหา 2048 บิต $p$สร้างตัวเลข 1824 บิตแบบสุ่ม $m$ และปล่อยให้ $p_0=q(2^{1824}+m)$. คำนวณ IsPrime($p_0$) และถ้าสำเร็จให้ $p=p_0$ มิฉะนั้นเพิ่มขึ้น $p_0$ โดย $คิว$ และทำซ้ำจนกว่าเราจะประสบความสำเร็จ

ตอนนี้เราพบว่า $\alpha$. อนุญาต $r=(p-1)/q$ โปรดทราบว่า $r$ เป็นจำนวนเต็ม เริ่มกับ $g=2$. คำนวณ $\alpha_0\equiv g^r\pmod p$, ถ้า $\alpha_0\not\equiv 1\pmod p$ เอา $\alpha=\alpha_0$มิฉะนั้นจะเพิ่มขึ้น $g$ ทีละ 1 และทำซ้ำจนกว่าจะสำเร็จ

พารามิเตอร์ถูกเลือกเพื่อให้ความปลอดภัยในการคำนวณแบบดั้งเดิม 112 บิต พารามิเตอร์อื่น ๆ จะให้ระดับความปลอดภัยที่แตกต่างกัน เช่น $q\ประมาณ 2^{160}$ และ $p\ประมาณ 2^{1024}$ จะให้ความปลอดภัยการคำนวณแบบคลาสสิกประมาณ 80 บิตและ $q\ประมาณ 2^{256}$ และ $p\ประมาณ 2^{3072}$ จะให้ความปลอดภัยการคำนวณแบบคลาสสิกประมาณ 128 บิต

fgrieu avatar
ng flag
$t$ น่าสนใจจากมุมมองทางทฤษฎี แต่ในทางปฏิบัติ $t$ และ $q>2^t$ ไม่สำคัญ เนื่องจาก (ตามที่ระบุในคำตอบ) เราต้องการ $\sqrt q$ ให้ใหญ่พอที่จะทำลาย BSGS และรุ่นที่ใช้หน่วยความจำน้อยเช่น Pollard's rho

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา