Score:1

จะหาจุดจำนวนเต็มของเส้นโค้ง ec ในช่วงที่กำหนดได้อย่างไร?

ธง it

ฉันกำลังดูพื้นฐานของ ecc และพบตัวอย่างจากอินเทอร์เน็ตไม่ว่าจะใช้เส้นโค้งโดเมนต่อเนื่องหรือใช้จำนวนเฉพาะที่น้อยมาก หน้า เช่น 17 ในโดเมนแยกเพื่อแสดงคะแนน

ฉันอยากรู้จริงๆว่าถ้าฉันสามารถหาจุดที่มีขนาดใหญ่จริงๆ หน้า ในทางปฏิบัติ ตัวอย่างเช่น secp256k1 กำลังใช้ขนาดใหญ่มาก หน้า=2^256â2^32â977 ในโดเมน (p,a,b,G,n,h)

ด้านล่างนี้เป็นรหัสหลามที่ฉันใช้เพื่อหักจำนวนเต็มที่เป็นไปได้ของ y จากการแก้สมการด้วยช่วงของจำนวนเต็ม x. ฉันประหลาดใจที่ไม่มีการค้นหาแม้แต่ในช่วง 1 ล้าน!

ดังนั้นคำถามของฉันคือรหัสด้านล่างถูกต้องหรือไม่ และประการที่สอง หากถูกต้องหรือแก้ไขโดยผู้เชี่ยวชาญจริง ควรลองใช้ช่วงค่าใด

ป.ล. ฉันสงสัยว่าจุดกำเนิดเป็นอย่างไร ถูกเลือกด้วย แต่นั่นอาจต้องการความเข้าใจที่ลึกซึ้งยิ่งขึ้นในหัวข้อ

นำเข้าคณิตศาสตร์

#secp256k1
# y**2 = x**3 + 7 (mod p)
P = 2**256 - 2**32 - 977
เอ = 0
ข = 7

#nistP256
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
เอ = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291

def in_curve(x):
    เส้นโค้ง = x**3 + A*x + B
    y_float = math.sqrt (เส้นโค้ง)
    ถ้า abs(math.modf(y_float)[0]) < 0.0001 หรือ \
          (1 - abs(math.modf(y_float)[0]) < 0.0001):
        # พิมพ์ (y_float)
        # ข้อบกพร่อง: y_int = int(math.modf(y_float)[1])
        y_int = int (รอบ (y_float))
        ถ้า y_int * y_int == (เส้นโค้ง):
            พิมพ์ (y_int)
            ส่งคืน y_int
    กลับไม่มี
 
สำหรับ x ในช่วง (1, 1000000):
    y = in_curve(x)
    ถ้า y ไม่ใช่ไม่มี:
        พิมพ์(x, y)

อัพเดท 1

รหัสก่อนหน้านี้ผิด เนื่องจากทศนิยม sqrt() จะทำให้เกิดข้อผิดพลาดที่ยอมรับไม่ได้เมื่อแปลงกลับเป็นจำนวนเต็ม

แต่หลังจากเปลี่ยน คณิตศาสตร์ sqrt() ถึง คณิตศาสตร์.isqrt()มันยังไม่ทำให้สิ่งต่าง ๆ สมเหตุสมผล

อัปเดต 2

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

ประเด็นคือนอกจากใช้ % สำหรับการคูณและการบวกทั้งหมด I ควร ยังใช้รากที่สองแบบแยกส่วนเพื่อหาคำตอบ แทน จำนวนเต็ม สแควร์รูท พร้อมด้วย %. นั่นเป็นการใช้ในทางที่ผิดโดยสิ้นเชิง % แน่นอน

รหัสที่แก้ไขผ่านการทดสอบด้วยเวกเตอร์ทดสอบบางตัว

นำเข้าโมดูลาร์_sqrt
#  เช่น. ฉันใช้รหัสจาก https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python
# โปรดขออนุญาตหากการใช้งานอยู่นอกเหนือขอบเขตของงานอดิเรกเพื่อการศึกษา และระบุเครดิตว่าเป็นมนุษย์ที่ดีเสมอ ;-)

# nist P256 นำมาจาก https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
เอ = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286
G = 36134250956749795798585127919587881956611106672985015071877198253568414405109

def get_y_in_curve(x):
    y2 = x**3 + A*x + B
    y_int = modular_sqrt(y2, พี)
    ถ้า y_int และ ((y_int * y_int) % P) == (y2 % P):
        ส่งคืน y_int
    กลับไม่มี

ยืนยัน get_y_in_curve(Gx) == Gy
fgrieu avatar
ng flag
รหัสไม่ถูกต้อง ปัญหาหลักคือการเข้ารหัสแบบ Elliptic Curve ไม่ทำงานกับ $x$ และ $y$ ในชุดที่ไม่มีที่สิ้นสุด ใช้ [ฟิลด์จำกัด](https://en.wikipedia.org/wiki/Finite_field) secp256k1 ใช้ฟิลด์ $\mathbb F_p$ เช่นเดียวกับ [ring of integers modulo](https://en.wikipedia.org/w/index.php?title=Ring_of_integers_modulo_n) $p$ ดังนั้นรหัสควรคำนวณ `เส้นโค้ง` โมดูโลที่ลดลง `P` และคำนวณ (เมื่อมีอยู่) สแควร์รูทแบบโมดูลาร์ของสิ่งนั้น ดู [สิ่งนี้](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) สำหรับหนึ่งวิธี โปรดปรับปรุงหรือปิดคำถาม
Match Man avatar
it flag
@fgrieu ใช่ ฉันรู้ตัวว่าทำผิดทันทีหลังจากที่แดเนียลชี้ให้เห็น ตอนนี้คำถามได้รับการอัปเดตด้วยอัลกอริทึมที่แก้ไขแล้ว คุณต้องการให้ฉันปิดคำถามเพราะมัน *ผิด* ผิดไหม หรือเอาไว้เป็นตัวอย่างว่าควรทำอย่างไรกับ Finite space ของ ECC หรือแม้แต่สิ่งต่าง ๆ จะผิดพลาดได้อย่างไรเมื่อวนจาก "เส้นโค้ง" ของอวกาศที่ไม่มีที่สิ้นสุดไปยังอวกาศที่ จำกัด :)
fgrieu avatar
ng flag
คำถามที่อัปเดตแล้วตกลง เนื่องจากคำตอบช่วยได้ ฉันคิดว่าวิธีที่ดีที่สุดคือยอมรับมัน แล้วทุกอย่างจะเรียบร้อย หมายเหตุเกี่ยวกับโค้ดใหม่: การเปลี่ยนชื่อ `curve` เป็น `y2` จะสวยงามกว่า คำนวณเป็นโมดูโล `P` ก่อนหน้านี้ (เช่น `y2 = (x**3 + A*x + B) % P` หรือ `y2 = (pow(x, 3, P) + A*x + B) % P )` ; และนำกลับมาใช้ใหม่ใน `y_int = modular_sqrt(y2)` และ `if ((y_int * y_int) % P) == y2:` ยังไม่ชัดเจนว่า `modular_sqrt` ทำอะไรเมื่อล้มเหลว ใช้ `modular_sqrt` ของบุคคลอื่นในบริบทหรือไม่ นั่นคือส่วนที่เกี่ยวข้อง!
Match Man avatar
it flag
รหัสถูกปรับโครงสร้างใหม่ modular_sqrt จะคืนค่า 0 สำหรับความล้มเหลวและรหัสใหม่ยังเพิ่มการตรวจสอบนั้นด้วย ฉันไม่ได้ใช้โค้ดของ Eli โดยตรง แต่อ้างอิงโค้ดของเขาเป็นตัวอย่าง
Score:3
ธง ru

ฉันไม่ค่อยแน่ใจว่าคุณหมายถึงอะไร $p$ และฉันไม่แน่ใจว่าคุณหมายถึงอะไรเพื่อให้โค้ดพิมพ์ออกมา

อย่างไรก็ตาม ดูเหมือนว่าคุณกำลังพยายามหาจุดที่มีค่าเป็นจำนวนเต็มบนเส้นโค้งวงรี $y^2=x^3+7$ โดยหมดแรง $x$ ค่าและฉันไม่พบจุดบกพร่องนอกเหนือจากคำสั่งพิมพ์ แต่ซีเกลแสดงให้เห็นว่าโดยทั่วไปเส้นโค้งวงรีเหนือจำนวนตรรกยะจะมีจำนวนเต็มจำนวนจำกัดเท่านั้น และเราคาดว่าสิ่งเหล่านี้จะหายากมาก ในความเป็นจริงสำหรับ เส้นโค้งที่คุณเลือก ไม่มีจุดจำนวนเต็ม แต่อย่างใด

คุณอาจกำลังพยายามหาจำนวนเต็ม $x$ และ $y$ ดังนั้น $y^2\equiv x^3+7\pmod p$ สำหรับนายกใหญ่บางคน $p$. ในกรณีนี้คุณควรใช้ mod รากที่สอง $p$ มากกว่าจำนวนจริง สิ่งนี้ใช้ การคำนวณที่แตกต่างกัน. การเลือกนายกขนาดใหญ่ $p$ แล้วทำการใด ๆ $x$ มูลค่ามีโอกาสประมาณ 50% ในการค้นหาที่เหมาะสม $y$ โดยการหารากที่สองแบบโมดูลาร์ของ $x^3+17$.

Match Man avatar
it flag
ฉันเพิ่มความหมายของ `p` ที่เป็นปัญหา มันใหญ่มาก จนไม่ต้องมอดูเลตกับตัวเลขเล็กๆ อย่าง 1 พันล้าน... > ในความเป็นจริงสำหรับเส้นโค้งที่คุณเลือกไม่มีจุดจำนวนเต็ม แต่อย่างใด
Daniel S avatar
ru flag
อ้อเข้าใจแล้ว. ในกรณีนั้น หากคุณพยายามสร้างจุดโดยไม่ใช้เลขคณิตแบบโมดูลาร์ มันจะไม่ทำงาน เพราะจุดเหล่านั้นจะเป็นจุดรวมและไม่มีอยู่บนเส้นโค้งนี้ โปรดทราบว่าตัวเลข "ขนาดเล็ก" ที่ไม่ใช่กำลังสองสมบูรณ์ยังคงสามารถมีรากที่สอง mod $p$ ได้หากมีการเตรียมที่จะใช้เลขคณิตแบบโมดูลาร์
Match Man avatar
it flag
คุณหมายความว่าฉันควรเปลี่ยน if y_int * y_int == (x^3 + 7) เป็น if y_int * y_int == (x^3 + 7) % P โดยที่ P =2^256â2^32â 977? ความเข้าใจของฉันคือ secp256k1 ถูกกำหนดมากกว่า â¤p ดังนั้นการคำนวณทศนิยมก่อนหน้านี้จึงเป็นเพียงการค้นหาว่า y ใกล้เคียงพอที่จะเป็นจำนวนเต็มหรือไม่ มีผู้สมัครที่เป็นไปได้มากมายใน 1 ล้านคน แต่ไม่มีสักคนที่ใช่จริงๆ...
Daniel S avatar
ru flag
ไม่ ฉันหมายความว่า (โดยใช้ความจริงที่ว่า $p\equiv 3\pmod 4$) คุณควรแทนที่ y_float=math.sqrt(x^3+7) ด้วย y_int=pow(x^3+7,(p+ 1)/4,p) จากนั้นตรวจสอบว่า y_int*y_int==(x^3+7)%p สิ่งนี้จะไม่ให้ค่า $y$ เล็กน้อยแก่คุณ แต่ไม่มีวิธีแก้ปัญหาที่มีค่าทั้ง $x$ และ $y$ เพียงเล็กน้อย ตรวจสอบลิงก์เกี่ยวกับการคำนวณรากที่สอง mod $p$
Match Man avatar
it flag
เข้าใจแล้ว. คำถามได้รับการอัปเดตด้วยการดำเนินการที่ถูกต้องในขณะนี้ ขอบคุณ.

โพสต์คำตอบ

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