ช่วยทำลาย ECDSA ด้วย nonce ที่มีอคติ

ขณะนี้ฉันกำลังพยายามทำ ความท้าทายของการเข้ารหัสลับ 62, ทำลาย ECDSA ด้วย nonce ที่มีอคติด้วยความช่วยเหลือจากทั้งสองลิงก์ (1 2) ที่อธิบายการโจมตีได้อย่างถูกต้อง อย่างไรก็ตาม หลังจากผ่านไปประมาณ 15 ชั่วโมง ฉันก็ยังไม่สามารถใช้งานได้ และฉันก็ไม่รู้ว่าฉันทำผิดตรงไหน

นี่คือวิธีที่ฉันทำ (โดยใช้ Python 3.6): ขั้นแรก เพื่อสร้างลายเซ็นด้วย nonces ที่ผิดพลาด (ฉันใช้โมเดลเดียวกันกับที่ลิงก์เหล่านั้นใช้ ดังนั้น 8 บิต LSB จึงเป็นศูนย์):

ecdsa นำเข้า
จากการแรนดอมนำเข้าแบบสุ่ม

gen = ecdsa.SECP256k1.เครื่องกำเนิดไฟฟ้า
คำสั่ง = gen.order()
d = randint(1, คำสั่ง)

ผับ = ecdsa.ecdsa.Public_key(gen, gen*d)
priv = ecdsa.ecdsa.Private_key(ผับ, ง)

ร = []
ส = []

สำหรับฉันในช่วง (100):
    nonce = randint (1, คำสั่ง)
    โนเซ่ ^= (โนเน่ & 0xff)
    ลงชื่อ = priv.sign (h, nonce)
    R.append (ลงนาม.r)
    S.append(ลงนาม.s)

จากนั้นการโจมตีจริงซึ่งค่อนข้างสั้น: เราคำนวณตัวเลขสองสามตัว สร้างเมทริกซ์กับพวกมัน เรียกอัลกอริทึม LLL และเราควรหาค่าพื้นฐานที่ลดลง -d*ct ถัดจากก ลูกบาศ์ก หนึ่งตามลิงค์:

การสร้างเมทริกซ์:

ชั่วโมง = 1337
N_SIGNATURE = 100

M = [[0 สำหรับ i ในช่วง(N_SIGNATURE + 2)] สำหรับ j ในช่วง(N_SIGNATURE + 2)]

สำหรับฉันในช่วง (N_SIGNATURE):
    M[i][i] = คำสั่ง

ct = gmpy2.invert(256, คำสั่ง) # 2**l กับ l = บิตที่รู้จัก
cu = สั่งซื้อ * กะรัต
M[-2][-2] = int(กะรัต)
M[-1][-1] = int(ลูกบาศ์ก)

สำหรับฉันในช่วง (N_SIGNATURE):
    M[-2][i] = int(R[i] * gmpy2.invert(S[i] * 256, สั่งซื้อ)) % สั่งซื้อ # t_i
    M[-1][i] = int( -h * gmpy2.invert(S[i] * 256, สั่งซื้อ)) % สั่งซื้อ # u_i

ใช้งานได้อย่างมีประสิทธิภาพมาก fplll lib (ส่วนนี้ค่อนข้างเกะกะและจะเขียนใหม่โดยใช้ Sage แต่ใช้งานได้ ที่นี่ ฉันจัดรูปแบบบนเมทริกซ์เป็นหลักเพื่อให้สามารถป้อนค่า fplll ได้ และแปลงเอาต์พุตกลับเป็นเมทริกซ์):

str_M = str(M).replace(",","")
os.system("echo " + str_M + " | fplll -a lll -m พิสูจน์แล้ว -f mpfr > result.txt")

new_matrix = [[0 สำหรับ i ในช่วง(N_SIGNATURE+2)] สำหรับ j ในช่วง(N_SIGNATURE+2)]

ด้วย open("result.txt", "r") เป็น myfile:
    เนื้อหา = myfile.read()
    เนื้อหา = contents.replace("[", "").replace("]", "").replace("\n", "").split(" ")
    contents = contents[:-1] # มีหนึ่งบรรทัดว่างในตอนท้าย

    ยืนยัน (len (เนื้อหา) == ธาร (N_SIGNATURE + 2, 2))

    ฉัน = 0
    เจ = 0
    สำหรับ v ในเนื้อหา:
        new_matrix[i][j] = int(โวลต์)
        เจ += 1
        ถ้า j == N_SIGNATURE + 2:
            เจ = 0
            ฉัน += 1

รับ d:

สำหรับแถวใน new_matrix:
    ถ้า (แถว [-1] == cu):
        d2 = (-row[-2] * gmpy2.invert(ct, ลำดับ)) % ลำดับ
        
        ถ้า (d2 == ง):
            พิมพ์ ("กู้คืนรหัสลับ")

อย่างไรก็ตาม ไม่ว่าฉันจะปรับตัวแปรกี่ตัวและลองอะไรไปก็ไม่ได้รับผลลัพธ์ ฉันยังลองสแกนเมทริกซ์ทั้งหมดแทนองค์ประกอบสุดท้าย โดยไม่ประสบความสำเร็จ ฉันทำผิดโง่ๆ ที่ไม่ได้สังเกต หรือมีบางอย่างผิดปกติในโค้ดของฉันหรือเปล่า

หมายเหตุ: บรรทัดต่อไปนี้ในลิงค์ 2:

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

ดึงดูดความสนใจของฉัน แต่ mpfr อาร์กิวเมนต์ของ fplll ควรเหมาะสมกับสิ่งที่จำเป็นที่นี่และในกรณีที่ไม่เป็นเช่นนั้น ฉันก็ลองใช้ Sage matrix ที่กำหนดผ่าน QQ แต่ก็ไม่ได้ผลดีกว่า