Gần đây tôi đã cố gắng lặp lại kết quả của câu hỏi mà Ruggero đã hỏi và câu hỏi mà Samuel Neves đã trả lời tại đây: Hiểu Twist Security đối với các đường cong Weierstrass ngắn
Trong nỗ lực tái tạo điều này, tôi thấy rằng cuộc tấn công không hoạt động ở một số điểm. Ban đầu giả định của tôi là điều này là do hệ số xoắn $d$ trong trường hợp của tôi không phải là $-1 \mod p$. Do đó, tôi đã hỏi câu hỏi này: Tấn công điểm không hợp lệ trên xoắn bậc hai của Đường cong Elliptic khi -1 là dư lượng bậc hai. Tuy nhiên, khi tôi khám phá thêm, tôi thấy rõ rằng đây không phải là lý do khiến cuộc tấn công không hoạt động. Thay vào đó, với chính mã của câu trả lời ban đầu, tôi cũng có thể chứng minh một cách đáng tin cậy rằng việc triển khai thực tế thang chỉ X hoạt động đối với các điểm có thứ tự 100+, nhưng không (đáng tin cậy) hoạt động đối với các điểm có thứ tự thấp hơn.
Tôi đã sửa đổi tập lệnh của Samuel ở đây để hiển thị một cách xác định hành vi này cho một điểm theo thứ tự 7:
# Trường thiết lập
p = 2^127-1
d = -1 # không vuông trong trường
K = GF(p)
K2.<z> = GF(p^2)
# đường cong này có bậc nguyên tố, nhưng xoắn trơn 2^44
một = -3
b = 2045
E = EllipticCurve(K, [a, b])
Et = EllipticCurve(K, [d^2*a, d^3*b])
E2 = Đường cong elip(K2, [a, b])
# tính toán trước đơn hàng
in (E.order().factor());
in (Et.order().factor());
in (E2.order().factor());
# tạo logarit rời rạc để giải
s = 123456789123456789123456789
P = E([0, 26743016104147931148362869907315104519])
Q = s * P
P_ = E2.lift_x(K(163965092228135290549051973720749297665))
thực tế = 7
P_ *= Et.order() // sự thật
in(P_)
Q_ = s * P_ # truy vấn -- giả sử điều này được thực hiện với bậc thang chỉ x
# giải quyết nhật ký trực tiếp trên E2
x1 = P_[0]
in("x1_p2", x1)
x2 = Q_[0]
s_ = E2.lift_x(x1).discrete_log(E2.lift_x(x2))
# ánh xạ tới Et (tùy chọn) và giải quyết
x1 = d * P_[0]
in("x1_t", x1)
x2 = d * Q_[0]
s__ = Et.lift_x(x1).discrete_log(Et.lift_x(x2))
cho kết quả trong [ 153050600407045353908344231774077597412, 109343643823296263382915152331234715795 ]:
cho x trong [ K(kết quả), K(kết quả) * d ]:
cho c trong [ Et, E2 ] :
cố gắng:
P = c.lift_x(x)
ngoại trừ ValueError như e:
in(e)
tiếp tục
in(P, P.thứ tự())
in (s% thực tế)
print (s_, -s_ % fact) # cái này hay cái kia
in (s__, -s__ % fact) # cái này hay cái kia
Các giá trị 15305... và 1093... là những giá trị mà việc triển khai bậc thang chỉ có X đưa ra khi được cung cấp tọa độ x1_p1 hoặc x1_t.
Lưu ý rằng mã này và triển khai thang chỉ X của tôi hoạt động hoàn hảo cho tất cả các điểm có thứ tự 73 trở lên. Nó chỉ không hoạt động đối với các đơn đặt hàng 3 hoặc 7. Đây là đầu ra của tập lệnh:
170141183460469231713519983870624230867
3 * 7^2 * 73 * 207464639 * 4221589732069 * 18102941371909
3 * 7^2 * 73 * 207464639 * 4221589732069 * 18102941371909 * 170141183460469231713519983870624230867
(31638283026303721859929793126783073834 : 8180858091114185696092778095200036260*z + 4090429045557092848046389047600018130 : 1)
x1_p2 31638283026303721859929793126783073834
x1_t 138502900434165509871757510589101031893
No point with x-coordinate 153050600407045353908344231774077597412 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(153050600407045353908344231774077597412 : 120638375417041763806996747829917991029*z + 145389779438755497769342025772901048378 : 1) 56713727820156410583284874520381326863
(17090583053423877823343071941806508315 : 41244633631159509998704366741778119200 : 1) 56713727820156410583284874520381326863
(17090583053423877823343071941806508315 : 28961826547573943769330362324255518848 : 1) 170141183460469231713519983870624230867
No point with x-coordinate 109343643823296263382915152331234715795 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(109343643823296263382915152331234715795 : 127120934962706688155967022405858199927 : 1) 170141183460469231713519983870624230867
No point with x-coordinate 60797539637172968348772151384649389932 on Elliptic Curve defined by y^2 = x^3 + 170141183460469231731687303715884105724*x + 170141183460469231731687303715884103682 over Finite Field of size 170141183460469231731687303715884105727
(60797539637172968348772151384649389932 : 17145369941110587676988010143957064222 : 1) 170141183460469231713519983870624230867
1
1 6
1 6
Tại sao cuộc tấn công này hoạt động trên lý thuyết (như phép nhân Q_ = s * P_ mô phỏng) nhưng chỉ hoạt động trong thực tế đối với các điểm có thứ tự cao hợp lý?
