Score:0

คุณสามารถกู้คืน $y$ ถ้าคุณมี $x$ ใน Pedersen hash?

ธง nz

(นี่อาจเป็นคำถามที่งี่เง่า)

แฮช Pedersen ทำงานในลักษณะต่อไปนี้: $(x, y) = กิโลกรัม$ ที่ไหน $k$ เป็นภาพก่อนและ $(x, y)$ เป็นแฮชผลลัพธ์

สมมติว่าเราซ่อนส่วนหนึ่งของแฮชเพื่อรักษาความเป็นส่วนตัว ผู้โจมตีสามารถได้รับ $y$ ถ้าพวกเขารู้เท่านั้น $x$ เนื่องจากไม่รู้ภาพพรีเวดดิ้ง?

กล่าวอีกนัยหนึ่งโดยรู้ $x$ ผู้โจมตีสามารถค้นหา $y$ แม้ว่าพวกเขาจะไม่รู้ก็ตาม $y$ ก็ไม่เช่นกัน $k$.

kelalaka avatar
in flag
อาจซ้ำกับ [รูทในช่องโมดูโล](https://crypto.stackexchange.com/q/20636/18298) และ [เป็นไปได้ไหมที่จะคำนวณพิกัด y ของจุดบน SECP256K1 โดยกำหนดเฉพาะ x- พิกัด](https://crypto.stackexchange.com/q/82027/18298)
nz flag
ขอขอบคุณ. แท้จริงแล้วคุณเพียงแค่ต้องรู้ว่า $y$ เป็นเลขคี่หรือคู่เท่านั้นจึงจะกู้คืนคู่ $(x, y)$ ได้ทั้งหมด
kelalaka avatar
in flag
สำหรับการค้นหาในอนาคต ใส่สิ่งนี้ลงในรายการของคุณ [SEC 2: พารามิเตอร์โดเมน Elliptic Curve ที่แนะนำ](https://www.secg.org/sec2-v2.pdf)
Score:1
ธง ru

เป็นไปได้ที่จะทำให้แคบลง $y$ ลงไปหนึ่งในสองค่าที่เป็นไปได้

ตัวเลข $x$ และ $y$ เป็นตัวแทนของพิกัดของ เส้นโค้งวงรี ในขอบเขตที่จำกัด ขึ้นอยู่กับเส้นโค้งที่เลือกสำหรับรูปแบบความมุ่งมั่นของคุณ จะมีสมการสำหรับเส้นโค้งและมักจะเป็นจำนวนเฉพาะ $p$ เหนือเส้นโค้งที่กำหนดไว้

ตัวอย่างเช่น เส้นโค้ง NIST P256 ที่ใช้กันอย่างแพร่หลายถูกกำหนดโดยใช้ไพรม์ $p=2^{256}-2^{224}+2^{192}+2^{96}-1$ และสมการ $$y^2\equiv x^3-3x+b\pmod p$$ ที่ไหน $ข$ คือหมายเลข 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b

ที่ให้ไว้ $x$ เราสามารถคำนวณได้ $y^2\mod p$ โดยใช้สมการนี้ จากนั้นควรมีสองรากที่เป็นไปได้ซึ่งเราสามารถคำนวณได้ $$y=\pm (x^3-3x+b)^{(p+1)/4}\mod p.$$

รูปแบบทั่วไปอื่นใช้เส้นโค้ง Ed25519 ซึ่งใช้จำนวนเฉพาะ $p=2^{255}-19$ และสมการ $$-x^2+y^2=1-\frac{121665}{121666}x^2y^2\pmod p.$$

อีกครั้งให้ $x$ หนึ่งสามารถจัดเรียงใหม่และแก้ไขได้สองอย่าง $y$ ค่า (แม้ว่าการคำนวณจะไม่สั้นเท่าที่จะจดไว้ข้างต้น)

ทั้งสองกรณี อย่างละ 2 $y$ ค่าต่างๆ เป็นไปได้ และไม่มีวิธีใดที่จะระบุได้ว่าค่าใดถูกต้องหากไม่มีข้อมูลเพิ่มเติม

nz flag
ว้าว. สิ่งนี้มีประโยชน์จริงๆ ขอบคุณ ดูเหมือนว่าค่า $y$ จะเพิ่มเอนโทรปีเพียง 1 บิตให้กับแฮชเท่านั้น

โพสต์คำตอบ

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