ขณะนี้ฉันกำลังพยายามทำ ความท้าทายของการเข้ารหัสลับ 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 แต่ก็ไม่ได้ผลดีกว่า