Điểm:2

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

lá cờ ma

Tôi đang sao chép một cuộc tấn công điểm không hợp lệ vào ECC bằng cách sử dụng các đường cong Weierstrass ngắn. Đối với điều này, tôi đã viết một triển khai "câm" không xác thực các điểm nằm trên đường cong trước khi đi vào phép nhân vô hướng. Đối với phác thảo của cuộc tấn công, tôi đang vay mượn rất nhiều từ mô tả xuất sắc của Samuel Neves mà anh ấy đã đưa ra ở đây: Hiểu Twist Security đối với các đường cong Weierstrass ngắn

Tôi có thể sao chép điều này mà không gặp vấn đề gì khi $d = -1$ là một không dư bậc hai trong $\mathbb{F}_p$, thì mọi thứ sẽ hoạt động vượt trội. Tuy nhiên, khi $p$ là như vậy $-1$ là dư lượng bậc hai và do đó tôi cần chọn một giá trị khác cho $d$, mọi thứ sụp đổ.

Để đơn giản, trong lần chạy đầu tiên tôi không sử dụng các đường cong trong $\mathbb{F}_{p^2}$ vì nhỏ $p$ liệt kê đầy đủ để tìm điểm thứ tự thấp không phải là một vấn đề.

Ví dụ, giả sử đường cong của tôi được xác định trên $\mathbb{F}_{101}$; đây, $-1$ là mod dư bậc hai $p$, từ $10 \cdot 10 = -1 \mod 101$. Đường cong của tôi được đưa ra bởi

$E: y^2 = x^3 + 13x + 29$

Và với $d = 2$, một mod không dư bậc hai 101,

$E^d: y^2 = x^3 + 52x + 30$

Lệnh của $E^d$$111 = 3 \cdot 37$. Tôi đã chọn hai điểm trên $E^d$ có thứ tự 3 và 37 tương ứng:

$P_1 = (28, 62)$

$P_2 = (8, 7)$

Khi tôi chạy các giá trị này thông qua phép nhân vô hướng mà không cần xác thực điểm (đối với khóa riêng tư $d = 58$, tôi nhận được đầu ra sau:

$S_1 = (94, 53)$

$S_2 = (32, 14)$

Không $S_1$ cũng không $S_2$ là một điểm trên đường xoắn bậc hai $E^d$. Tôi có thể nâng tọa độ X trong $E^d$, nhưng sau đó thứ tự của các điểm là sai.

Đây là mã ví dụ của tôi:

Fp = GF(101)
D = Fp(2)
    
print(D, "là hình vuông?", D.is_square())
(a, b) = (13, 29)

E = EllipticCurve(Fp, [a, b])
Et = EllipticCurve(Fp, [ a*D^2, b*D^3 ])

print("Et.order()", factor(Et.order()))

điểm tấn công = [
    Và (28, 62),
    Và (8, 7),
]
in(E)
in(và)
cho P trong attack_points:
    in(P, P.thứ tự())

# khóa riêng d = 58
mul_results = [ 
    Và (94, 53), 
    Và (32, 14), 
]
#print(Et.lift_x(94).order())
#print(Et.lift_x(32).order())

Đầu ra nào:

2 là hình vuông? Sai
Et.order() 3 * 37
Đường cong elip được xác định bởi y^2 = x^3 + 13*x + 29 trên Trường hữu hạn có kích thước 101
Đường cong elip được xác định bởi y^2 = x^3 + 52*x + 30 trên Trường hữu hạn có kích thước 101
(28 : 62 : 1) 3
(8 : 7 : 1) 37
TypeError: Tọa độ [94, 53, 1] không xác định điểm trên Đường cong Elliptic được xác định bởi y^2 = x^3 + 52*x + 30 trên Trường hữu hạn có kích thước 101

Làm cách nào tôi có thể thực hiện cuộc tấn công này cho một bước ngoặt bậc hai trong đó $d \neq -1$?

kelalaka avatar
lá cờ in
Nó có thể không phải là vấn đề của bạn. Mã ban đầu cũng không hoạt động trên SageMath nữa. Rất có thể có một sự thay đổi trong thư viện ngăn các phép tính như vậy ...
lá cờ ma
Tôi không có đủ danh tiếng để nhận xét trong bài đăng khác, nhưng giải pháp của Neves hoạt động, không có gì khó hiểu: Các câu lệnh in cần có dấu ngoặc đơn và các lệnh gọi .lift_x(randint(...)) cần được thay thế bởi .lift_x(K(randint(...))), thì mọi thứ sẽ hoạt động như một bùa mê. Tôi có thể tái tạo nó một cách hoàn hảo với d = -1, nhưng như tôi đã viết -1 là dư lượng bậc hai trong một số trường (như GF(101), như được hiển thị ở đây).
kelalaka avatar
lá cờ in
Tôi đã sửa đổi câu trả lời, bạn cũng có thể kiểm tra điều đó không?
lá cờ ma
Cảm ơn, mã ở đó hiện đang hoạt động, nhưng vẫn không giải quyết được câu hỏi của tôi (nghĩa là nó sử dụng rõ ràng d = -1) - bạn có biết làm cách nào để mã chạy với một d khác không?
kelalaka avatar
lá cờ in
Vâng tôi biết. Hình học đại số (các đường cong elip là một phần của nó) nên được thực hiện trên bao đóng đại số. Câu trả lời của Samuel Neves, như bạn có thể thấy, hoạt động khi đóng cửa, bạn thì không.
kelalaka avatar
lá cờ in
Xem Curve25519'paper về tấn công nhóm nhỏ.
Ruggero avatar
lá cờ kr
Tôi cho rằng với d!=-1 bạn cần chuyển đổi điểm của mình từ $E$ và $E^{d}$ và bạn không thể chỉ sử dụng tọa độ x đơn giản. Sẽ rất hữu ích nếu bạn có thể đăng một tập lệnh hiền triết cho phép nhân vô hướng của mình vì việc sử dụng $y$ làm tôi bối rối, tại sao không thực hiện một cuộc tấn công đường cong không hợp lệ (không bận tâm đến vòng xoắn)?
lá cờ ma
@kelalaka Ví dụ tôi đưa ra ở đây chỉ để đơn giản - anh ấy làm việc trên trường mở rộng bậc hai, nhưng điều đó cũng không hoạt động cho d != -1 nếu bạn sửa đổi tập lệnh của anh ấy để sử dụng các tham số miền khác. Tức là, tôi e rằng đó không phải là nguyên nhân cốt lõi của vấn đề. Tôi chỉ bỏ qua nó ở đây cho ngắn gọn để có một ví dụ tối thiểu chứng minh vấn đề.
lá cờ ma
@Ruggero Tôi đã bỏ qua thời gian nghỉ ngơi của bạn. Có, tôi tin rằng một số chuyển đổi là cần thiết, nhưng tôi không thể tìm ra cách thực hiện: Trước khi đặt nó làm đầu vào cho bậc thang hoặc sau đầu ra của bậc thang (hoặc có thể là cả hai). Một số chuyển đổi chắc chắn là cần thiết nhất và cũng lưu ý rằng -1^2 = 1, tức là nếu một lũy thừa chẵn được nhân/chia cho, chúng ta sẽ không bao giờ biết được trong trường hợp d=-1. Nhận xét của bạn về thang chỉ X là chính xác. Trong sự tuyệt vọng của mình, tôi đã thử tất cả: Multi-and-add đơn giản (cũng hoạt động với d=-1!), Thang chữ X Brier/Joye và thang chỉ chữ X phụ gia. Tất cả đều tính toán chính xác, vì vậy tôi chắc chắn thiếu chuyển đổi.
Điểm:0
lá cờ ma

Đây không phải là vấn đề d là QNR không phải là -1.

Thay vào đó, nó là một vấn đề của các mô đun nhỏ. Tôi có thể chứng minh điều này một cách đáng tin cậy bằng cách sử dụng một kịch bản đã sửa đổi của Samuel Neves: Tấn công điểm không hợp lệ mang lại kết quả sai cho các điểm có thứ tự thấp

Điều này không trả lời ở tất cả tại sao nó không hoạt động, nhưng ít nhất điều này chứng tỏ rằng $d \neq -1$ không phải là nguyên nhân gốc rễ của vấn đề của tôi.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.