พิธีสารชะอม-พีเดอร์เซิน

ฉันไม่รู้สึกว่าที่นี่เป็นสถานที่สอนทฤษฎีจำนวนเบื้องต้น ดังนั้นฉันจะพูดถึงแง่มุมที่เกี่ยวข้องกับคำถามของคุณในทันที

เมื่อเราเลือกนายกรัฐมนตรี $p$ และมีค่า $g$ (ที่ไม่ใช่ผลคูณของ $p$) ถ้าเราพิจารณาลำดับของค่า $g^0 \bmod p, g^1 \bmod p, g^2 \bmod p, ...$แล้วเราจะพบว่า ณ จุดหนึ่ง ลำดับจะกลับมาที่ 1 และหลังจากนั้น เริ่มต้นใหม่ เราเรียกคำสั่งของ $g$ จำนวนค่าที่เราผ่านก่อนที่เราจะถึง 1 นั่นคือ $g^q \bmod p = 1$และนั่นคือค่าที่น้อยที่สุดของ $q > 0$ ที่ตอบโจทย์นี้

ดังนั้นเมื่อสมาร์ทพูดอย่างนั้น $g$ และ $h$ มีลำดับเอกเหมือนกัน เขาว่าอย่างนั้น $g^q \bmod p = 1$, $h^q \bmod p = 1$ และ $คิว$ เป็นจำนวนเฉพาะ (และในทั้งสองกรณี ไม่มีค่าใดที่น้อยกว่าของ $คิว$).

คุณพบเช่น $g, h, q$? จริงๆแล้วมันไม่ใช่เรื่องยาก $คิว$ จะแบ่งเสมอ $p-1$ เท่า ๆ กัน; เราเลือกนายกได้ $p$ เพื่อหาค่าเฉพาะดังกล่าว $คิว$ ง่าย. นอกจากนี้หาก $คิว$ เป็นจำนวนเฉพาะ ดังนั้นสำหรับค่าใดๆ $u$ ปราศจาก $p$ เป็นปัจจัยค่า $j = u^{(p-1)/q} \bmod p$ จะเป็นอย่างใดอย่างหนึ่งหรือมีคำสั่ง $คิว$; ดังนั้นการหาค่า $g, h$ มันง่าย.

คุณขอตัวอย่าง ฉันจะให้ของเล่น - เราจะเลือก $p=23$ และ $q=11$ (โปรดทราบว่า $11$ แบ่ง $23-1$ เท่าๆ กัน) และ $g=4$ และ $h=9$ (ง่ายต่อการตรวจสอบว่าทั้งคู่มีลำดับที่ 11) นอกจากนี้เรายังเลือกค่าลับ $x$ (เราจะเลือก 6) และเผยแพร่ $y_1 = g^x \bmod p = 4^6 \bmod 23 = 2$ และ $y_2 = h^x \bmod p = 9^6 \bmod 23 = 3$

จากนั้นผู้พิสูจน์จะทำการสุ่ม $k$เราจะเลือกโดยพลการ $k=7$

จากนั้นผู้พิสูจน์จะคำนวณ $r_1 = g^k \bmod p = 4^7 \bmod 23 = 8$ และ $r_2 = h^k \bmod p = 9^7 \bmod 23 = 4$และส่งสิ่งเหล่านั้น โปรดทราบว่าเราได้ทำโมดูโลการคำนวณเหล่านี้ $p$ - ที่ไม่ชัดเจนในโปรโตคอล (การดำเนินการโมดูลัสดังกล่าวเป็นที่เข้าใจกันโดยทั่วไป)

ตอนนี้ผู้ท้าชิงเลือกมูลค่า $ค$; เราจะเลือก $4$; และส่งสิ่งนั้น

จากนั้นผู้พิสูจน์จะคำนวณ $s = (k - c \cdot x) \bmod q = (7 - 4 * 6) \bmod 11 = 5$ (หมายเหตุ: ในทางคณิตศาสตร์ การ $x \bmod q$ การดำเนินการจะคืนค่าระหว่างเสมอ $0$ และ $q-1$ ดังนั้น $x - (x \bmod q)$ เป็นทวีคูณของ $คิว$ - ภาษาคอมพิวเตอร์จำนวนมากไม่เป็นไปตามนั้น - ภาษาเหล่านั้นผิด) และส่งสิ่งนั้น

ผู้ตรวจสอบจะตรวจสอบสิ่งนั้น $r_1 = 8$ ก็เหมือนกับ $g^s \cdot y_1^c \bmod p = 4^5 \cdot 2^4 \bmod 23 = 8$ และ $r_2 = 4$ ก็เหมือนกับ $h^s \cdot y_2^c \bmod p = 9^5 \cdot 3^4 \bmod 23 = 4$; ทั้งเช็คเอาท์และผ่าน

คุณทำเช่นเดียวกันกับค่าที่มีความยาวหลายร้อยหลักเท่านั้น ไม่ใช่ตัวอย่างของเล่นที่ฉันให้