Bằng chứng không có kiến thức: khái niệm cơ bản về đường cong elip

Tiêu đề gốc: "Chứng minh không có kiến thức - Cơ bản về đường cong Elliptic"
Nguồn gốc: Star Idea

Để học các đường cong elip, cá nhân tôi khuyên dùng liên kết sau , không Quá nhiều thuật ngữ, được giải thích rõ ràng.

https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

https://andrea.corbellini.name/2015/05/23/elliptic-curve- mật mã-hữu hạn-trường-và-rời rạc-logarit/

Bài viết này cũng là bài viết tóm tắt dựa trên link trên.

1. Đường cong elip trong trường số thực

 1.1 Định nghĩa

Có thể xem định nghĩa toán học của đường cong elip tại Wolfram MathWorld: http://mathworld.wolfram.com/EllipticCurve.html. Những người bạn không học chuyên ngành mật mã hoặc toán học sẽ cảm thấy khó hiểu. Để tạo điều kiện thuận lợi cho sự hiểu biết về kỹ thuật, đường cong elip là một chuỗi các điểm thỏa mãn phương trình sau:

và . Phương trình này được gọi là phương trình Weierstrass cho đường cong elip.

Sau đây là đường cong elip có b=1, a từ 2 đến -3:

Như có thể thấy từ phương trình, hình elip. Đường cong đối xứng qua tọa độ x. Ngoài các điểm của đường cong trên hệ tọa độ, đường cong elip xác định thêm một điểm (vô cực), được ghi là 0.

Nói cách khác, đường cong elip bao gồm các điểm sau:

1.2 Định nghĩa nhóm dựa trên đường cong elip

Trên cơ sở các đường cong elip, một nhóm cộng có thể được xác định:

*Tất cả các điểm trên đường cong elip đều là các phần tử trong nhóm này

*Đơn vị đơn vị là 0

*Phần tử nghịch đảo của điểm P là điểm đối xứng của điểm P so với tọa độ x

*Phép cộng được định nghĩa như sau: trên đường cong elip, ba điểm P, Q và R cắt một đường thẳng thì tổng trong ba điểm thỏa mãn . Nói cách khác, kết quả của việc cộng hai điểm trên đường cong elip vẫn nằm trên đường cong elip.

Kết hợp với định nghĩa của nhóm, có thể chứng minh rằng nhóm cộng được xác định là nhóm Abelian.

Tính khép kín: Vì tổng các điểm trên đường cong elip vẫn là một điểm trên đường cong elip.

Luật kết hợp:

Đơn vị đơn vị: Đơn vị đơn vị là 0

Phần tử nghịch đảo: trên đường cong elip Phần tử nghịch đảo của điểm P là điểm đối xứng so với tọa độ x

Luật giao hoán:

1.3 Phép tính cộng đường cong Elliptic

Bởi vì , tức là . Phương pháp tính tương đối trực quan: vẽ một đường thẳng nối P và Q, điểm còn lại nơi đường thẳng này cắt đường cong elip là R. Kết quả của là nghịch đảo của R.

Xem xét một số tình huống đặc biệt và "sửa" phép tính phép cộng:

* hoặc : Vì 0 được xác định là vô cực nên không thể vẽ đường dựa trên vô cực. Nhưng vì 0 được định nghĩa là phần tử nhận dạng nên và .

*: Vì hai điểm đối xứng nên đường thẳng vẽ dựa trên hai điểm này vuông góc với trục x và không còn cắt nhau ở các điểm khác. .

*: Nếu P và Q Nếu là cùng một điểm thì có nhiều đường thẳng đi qua "hai" điểm này. Nếu Q được coi là một quá trình gần P vô hạn thì có thể thấy rằng vật đi qua P và Q là đường tiếp tuyến của đường cong elip tại điểm P. Nếu điểm mà tiếp tuyến và đường cong elip giao nhau là R thì , .

*, và không có giao điểm thứ ba: Trường hợp này hơi giống trường hợp trước, tức là đường nối P/Q là tiếp tuyến của đường cong elip. Nếu điểm P là điểm tiếp tuyến thì . Tức là .

1.4 Đạo hàm của phép tính cộng

Định nghĩa phép cộng đã hoàn tất. Trong trường hợp phổ biến nhất, một đường thẳng có thể đi qua ba điểm trên đường cong elip, đó là P và Q.

. Đường này có độ dốc:

Có thể suy ra:

hoặc

Tất nhiên, nếu P/Q bằng cùng một điểm thì công thức tính độ dốc sẽ khác nhau.

1.5 Phép nhân vô hướng (Phép nhân vô hướng)

Dựa trên phép cộng, phép nhân vô hướng được xác định, cộng cùng một điểm nhiều lần:

Cách đơn giản nhất để tính phép nhân vô hướng là cộng từng điểm P một. Nếu n là k bit thì độ phức tạp của thuật toán là: .

Có cách tính nhanh: nhân đôi rồi cộng. Giả sử n=151, biểu diễn nhị phân là: .

Vẫn sử dụng n=151 làm ví dụ:

"Double" chủ yếu được sử dụng để lấy các biến tương ứng với một số lượng nhất định bit theo thứ tự.kết quả. Nếu bit là 1, nó sẽ được thêm vào kết quả cuối cùng. Độ phức tạp của thuật toán này là: .

1.6 Bài toán logarit

Cho n và P, việc tính tương đối dễ dàng. Tuy nhiên, việc giải tìm n khi biết Q và P là rất khó và không có thuật toán giải thời gian đa thức.

2. Đường cong elip trên trường hữu hạn

Những gì được giới thiệu ở trên là các điểm của đường cong elip dựa trên số thực, có thể dựng nên một nhóm. Xét một trường hữu hạn có số đặc trưng là , là số nguyên tố. Trường hữu hạn này bao gồm các kết quả của module , ký hiệu là . Vì các phần tử trong trường hữu hạn có các phần tử nghịch đảo, tức là , rồi .

2.1 Định lý Euclid mở rộng

Cho hai số nguyên a và b, phải tồn tại các số nguyên x và y sao cho ax + by = gcd(a,b). gcd(a,b) là ước chung lớn nhất.

2.2 Nghịch đảo nhân trong phép toán modulo p

Giả sử phần tử a có phần tử nghịch đảo x trong hoạt động mô-đun. Hài lòng, . Nghĩa là,

.

Bằng cách mở rộng định lý Euclid, có thể tìm được x và y. x là nghịch đảo nhân của a.

2.3 Xác định đường cong elip trong F_p

Đường cong elip được xác định như sau trên :

Định nghĩa tương tự như định nghĩa số thực. Sau đây là , p là điểm của đường cong elip tương ứng với 19, 97, 127 và 487.

Đường cong elip có khoảng Đối xứng vì

Modulo p, hai phương trình này bằng nhau.

2,4 điểm cộng

Tương tự như phép cộng điểm của đường cong elip trên số thực, phép cộng ba điểm xác định trên một "đường thẳng" bằng 0:. Trên trường hữu hạn , một đường thẳng được xác định là: .

Hình trên là đường cong elip , trong đó . Chuỗi đường chéo màu vàng trong hình là các đường thẳng . R nằm trên một trong các đường chéo và -R là điểm đối xứng của R được đánh dấu trong hình, là kết quả của P+Q.

Thuộc tính dấu chấm cộng:

*

*, tức là -Q là điểm có cùng hoành độ nhưng có tọa độ ngược nhau, tức là p/2 tương đối Điểm đối xứng.

*

Tính cộng 2,5 điểm

Giả sử có ba điểm nằm trên một đường thẳng, , , . Nếu P và Q không giống nhau:

Do đó suy ra:

Dẫn xuất theo các điều kiện khác, liên quan Có rất nhiều công thức. Bạn bè quan tâm có thể tự suy luận.

2.6 Hình elip trên nhóm hữu hạn Có bao nhiêu đường cong có điểm?

Số điểm trên đường cong elip được gọi là "thứ tự". Nếu bạn liệt kê 0~p-1 và kiểm tra số điểm thì điều đó không thực tế vì p là số nguyên tố rất lớn. Thuật toán của Schoof xác định thứ tự của các đường cong elip trong thời gian đa thức: https://en.wikipedia.org/wiki/Schoof%27 s_algorithm.

2.7 Phép nhân vô hướng

Giống như trong trường số thực, nó có thể được tính bằng phương pháp cộng kép và phép cộng tiếp theo. Trên các trường hữu hạn, có các thuộc tính bổ sung, ví dụ:

và điểm đã được biết. Kết quả của phép nhân vô hướng tại điểm P là tuần hoàn, chỉ có năm điểm.

…

Có thể dễ dàng nhận thấy điều đó trong bị giới hạn Kết quả của phép nhân vô hướng điểm trong đường cong elip trên một trường tạo thành một nhóm con tuần hoàn trong phép toán cộng. Tại các điểm trong nhóm con, kết quả của mọi phép cộng vẫn thuộc nhóm con. Hơn nữa, có một điểm tại đó lũy thừa (phép cộng) tạo ra tất cả các điểm trong nhóm con. Những điểm như vậy được gọi là "máy phát điện".

Đi trong một đường tròn lớn có nhiều nhóm con tuần hoàn trên đường cong elip trong trường hữu hạn. Các nhóm con dựa trên các hoạt động bổ sung.

2.8 Thứ tự của nhóm con tuần hoàn

Thuật toán của Schoof có thể xác định số điểm trên toàn bộ đường cong elip dựa trên trường hữu hạn, nhưng không thể xác định số lượng nhóm con tuần hoàn.

Định lý Lagrange phát biểu rằng với mọi nhóm hữu hạn G, thứ tự của mỗi nhóm con H của G (số phần tử) sẽ chia hết cho cấp G.

https://en.wikipedia.org/wiki/Lagrange%27 s_theorem_(group_theory)

Định lý này cho phép tìm kiếm chu kỳ Thứ tự n của nhóm con cung cấp một ý tưởng:

1/ Sử dụng thuật toán Schoof để tính thứ tự của toàn bộ đường cong elip

2/ Tìm tất cả các ước của nó

3/ Tìm ước số n nhỏ nhất thỏa mãn

2.9 Tìm máy phát điện

Thuật toán đường cong elip thường được sử dụng để trước tiên chọn một đường cong, tính thứ tự của đường cong elip và sau đó tìm nhóm con lớn nhất trên đường cong này. Tìm một nhóm con là tìm bộ sinh tương ứng với nhóm con đó.

Giả sử thứ tự của đường cong elip là N và thứ tự của nhóm con là n. Theo định lý Lagrange, .

Và bởi vì thứ tự của hình elip đường cong là N và P là các điểm ngẫu nhiên trên đường cong elip và có . Đó là .

Khi đó là phần tạo ra nhóm con.

2.10 Bài toán logarit rời rạc

Cho hai điểm P và Q thuộc nhóm con, việc giải là một bài toán rất khó. Hiện tại chưa có thuật toán giải thời gian đa thức cho bài toán này.

2.11 Đồng hình

Nếu thứ tự của nhóm con là r thì .

*Phép cộng đồng hình:

Tóm tắt:

Các đường cong elip trên trường hữu hạn là cơ sở của chứng minh không có kiến thức. Việc thực hiện kiến thức bằng không dựa trên bài toán logarit rời rạc. Từ quan điểm tính toán, F_p là một trường hữu hạn và các phép tính các điểm trên đường cong elip được thiết lập trên nó nằm trong phạm vi của trường này. Có nhiều nhóm con tuần hoàn F_r trên các đường cong elip trên các trường hữu hạn, chúng có các đặc tính đồng cấu cộng. Bài toán logarit rời rạc đề cập đến thực tế là hai điểm đã biết thuộc nhóm con tuần hoàn nhưng rất khó để biết được các đại lượng vô hướng của hai điểm đó.

Liên kết nguồn: weixin.qq.com

Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia