Tạo ngẫu nhiên một vô hướng hợp lệ trên đường cong đã chọn

Việc triển khai của tôi yêu cầu tôi tạo ngẫu nhiên một đại lượng vô hướng hợp lệ trên đường cong. Theo như tôi hiểu thì đó không phải là việc tạo số ngẫu nhiên mà là điều phức tạp hơn.

Tôi phải tạo các đại lượng như vậy trên máy chủ và phía máy khách theo sơ đồ sau:

Khách hàng:

X = x à G + w0 à M

ở đâu

• x - vô hướng được tạo!

• G - điểm cơ sở của đường cong

• w0 - một số được biểu thị bằng mảng 32 byte

• M - điểm không đổi trên đường cong

• X - điểm kết quả

Người phục vụ:

Y = y à G + w0 à N

ở đâu

• y - vô hướng được tạo ra!
• G - điểm cơ sở của đường cong
• w0 - một số được biểu thị bằng mảng 32 byte
• N - điểm không đổi trên đường cong
• Y - điểm kết quả

Sau đó, máy khách và máy chủ trao đổi điểm X và Y.

Và tính điểm Z như sau:

• Khách hàng: Z = x à (Y â w0 à N)
• Máy chủ: Z = y à (X â w0 à M)

Câu hỏi số 1: cơ chế tạo ngẫu nhiên vô hướng hợp lệ trên đường cong là gì?

Câu hỏi số 2: phép toán đằng sau phép trừ điểm là gì?

Vô hướng không "trên đường cong". Số vô hướng chỉ là số nguyên dương (kể cả số 0) nhỏ hơn thứ tự nhóm $\ell$ của bộ tạo đường cong. Ví dụ. đối với đường cong Ed25519, thứ tự nhóm $\ell$ Là $2^{252} + 27742317777372353535851937790883648493$.

Để tạo một đại lượng ngẫu nhiên không thiên vị, hãy sử dụng "lấy mẫu từ chối". Điều này có nghĩa là sử dụng một cơ chế để tạo một số nguyên ngẫu nhiên thống nhất một cách an toàn trong phạm vi ít nhất là lớn bằng $\ell$, và chỉ chấp nhận nó nếu nó nhỏ hơn $\ell$.

Tất cả các hoạt động vô hướng, bao gồm cộng, nhân và trừ được thực hiện $mod\ \ell$. Phân chia đạt được bằng cách tìm một thứ gọi là "nghịch đảo nhân mô-đun".

Các phép tính điểm, chẳng hạn như phép trừ điểm, sẽ do thư viện EC của bạn xử lý. Nhìn thấy đây để biết thêm.