Algorithm cho nén điểm đường cong elliptic

Question

Tôi đang sử dụng Javascript để tạo đường cong elip để sử dụng trong một ứng dụng tin nhắn mã hóa dựa trên ví dụ này đang http://www-cs-students.stanford.edu/~tjw/jsbn/ecdh.html

Các phím nào sẽ là khá lớn và tôi biết nó có thể nén chúng , nhưng tôi đã không thể tìm thấy một thuật toán Javascript hoặc phác thảo để làm điều này. Đây là một bài báo http://nmav.gnutls.org/2012/01/do-we-need-elliptic-curve-point.html vạch ra các phép tính.

Answer 1

Nén các điểm cong elliptic được cấp bằng sáng chế bởi Certicom, vì vậy bạn không nên sử dụng nó mà không có giấy phép, nói chung.

Cập nhật: Bằng sáng chế của Certicom đã hết hạn vào năm 2014, theo nhận xét của denis bider bên dưới.

Answer 2

Thật khó để sáng chế một công thức độc lập một cách độc lập. Việc sử dụng một phương trình bậc hai y = sqrt (x^3 + ax + b) không thể được cấp bằng sáng chế, và nếu nó là, không thể được bảo vệ. Người ta chắc chắn có thể tuyên bố trước nghệ thuật từ Diophantes (200-298 AD). và công việc xung quanh phỏng đoán Hall (khoảng năm 1971) về sự khác biệt tuyệt đối nhỏ nhất giữa một hình vuông và một khối lập phương | y^2 - x^3 | hiếm khi nhỏ hơn x. Viết lại nó y^2 - x^3 = ax-b với x < b/a và nhận xét rằng các giải pháp trong các nhóm mô-đun sẽ giúp giảm lượng tìm kiếm bạo lực trong các số nguyên.

Bằng sáng chế là bit giúp tìm ra dấu hiệu của y. Bit này có thể được sử dụng để phân biệt đối xử lớn nhất của giải pháp từ (y và M-y), hoặc các giải pháp tích cực từ (y, -y), tùy thuộc vào các tiêu chuẩn bạn nhìn vào.

Nhưng vì bằng sáng chế đã được chấp nhận, bạn cần tìm tư vấn pháp lý.

Là một nhà mật mã có uy tín cũng thông thạo kỹ năng của nghệ thuật Tiến sĩ Dan Bernstein điểm một cách khôn ngoan (http://cr.yp.to/ecdh/patents.html), ý tưởng tái xuất y từ x được đề cập trong Miller 1986 như là một tầm thường để giảm dấu chân của các đường cong elliptic hệ thống dựa trên bộ nhớ.

Một luật sư chuyên về khiếu nại bằng sáng chế có thể giúp bạn đánh giá xem bằng sáng chế vẫn áp dụng nếu bạn không sử dụng cơ sở bình thường như đại diện cho tọa độ điểm hoặc trong trường hợp ecc trong gf (p) hoặc bạn không sử dụng một chút để recode giá trị nén của y, ví dụ khi chọn ngẫu nhiên k, P1 (x1, y1) và tính P2 (x2, y2) = [k] P1 cho đến khi tr (y1) == tr (y2) loại bỏ sự mơ hồ (một chút CPU tốn kém, nhưng tại sao không?). Ngoài ra, bạn có thể chỉ ra rằng độ phân giải của công thức bậc hai rõ ràng là tốn kém hơn so với số bit được lưu trên một kênh truyền thông và bằng sáng chế này không hữu ích chút nào, và thậm chí gây tổn hại cho môi trường bằng cách đề xuất thay thế 6 picowatts của chi phí truyền dẫn bởi 2 miliwatts chi phí CPU (Để được chấp nhận, một bằng sáng chế trình phải được mới, không tầm thường và hữu ích). Sau đó, bạn tìm thấy một luật sư quanh co tốt nhất ở California và chắc chắn, sẽ có một thẩm phán địa phương trao cho bạn vài tỷ đô la cho những thiệt hại gây ra cho môi trường, vì sự phiền toái gây ra cho kỹ năng lập trình của bạn và ví của bạn. trong việc phát hành ứng dụng có giá trị của bạn.

Khác, như được đề xuất trong bài đăng khác, bạn sẽ tìm giải pháp cấp phép.

Nếu đơn đăng ký của bạn cho chính phủ Hoa Kỳ, bạn cần một luật sư khác để đánh giá liệu bằng sáng chế này và cách bạn dự định sử dụng nó đã là một phần của giấy phép được NSA mua trong bối cảnh của "Suite B" của thuật toán , trong trường hợp đó, giấy phép có thể đã được trả bởi người dân Hoa Kỳ.

Answer 3

Tôi tưởng tượng họ sẽ được tăng sự quan tâm đến giải pháp nén điểm cong hình elip của JavaScript, với WebCrypto lọc hỗ trợ vào trình duyệt.
Tôi sẽ sử dụng đường cong NIST làm ví dụ, vì đây là những đường tôi phải xử lý khi nhập khóa công khai nén vào WebCrypto.

Curves and their primes 
NIST P-256 (secp256r1) 2^256 - 2^224 + 2^192 + 2^96 - 1 
NIST P-384 (secp384r1) 2^384 - 2^128 - 2^96 + 2^32 - 1 
NIST P-521 (secp521r1) 2^521 - 1 

Những số nguyên tố tất cả thỏa mãn phương trình, p mod 4 === 3
Điều này có nghĩa là bạn có thể bỏ qua mục đích chung hơi phức tạp Tonelli-Shanks algorithm, và sử dụng một bản sắc đơn giản để tìm ra căn bậc hai.

Đầu tiên, phần nén của 'nén điểm' rất đơn giản. Ghi lại những dấu hiệu của Y, sau đó loại bỏ các giá trị của Y.

/** 
* Point compress elliptic curve key 
* @param {Uint8Array} x component 
* @param {Uint8Array} y component 
* @return {Uint8Array} Compressed representation 
*/ 
function ECPointCompress(x, y) 
{ 
    const out = new Uint8Array(x.length + 1); 

    out[0] = 2 + (y[ y.length-1 ] & 1); 
    out.set(x, 1); 

    return out; 
} 

nén bao gồm nhìn lên căn bậc hai, sau đó điều chỉnh tùy thuộc vào các bit chẵn lẻ Y. Chức năng này phụ thuộc vào JavaScript big integer library hiển thị các chức năng sau: thêm, phụ, nhân, pow, modPow.

// Consts for P256 curve. Adjust accordingly 
const two = new bigInt(2), 
// 115792089210356248762697446949407573530086143415290314195533631308867097853951 
prime = two.pow(256).sub(two.pow(224)).add(two.pow(192)).add(two.pow(96)).sub(1), 
b = new bigInt('41058363725152142129326129780047268409114441015993725554835256314039467401291'), 
// Pre-computed value, or literal 
pIdent = prime.add(1).divide(4); // 28948022302589062190674361737351893382521535853822578548883407827216774463488 


/** 
* Point decompress NIST curve 
* @param {Uint8Array} Compressed representation 
* @return {Object} Explicit x & y 
*/ 
function ECPointDecompress(comp) 
{ 
    const signY = comp[0] - 2, // This value must be 2 or 3. 4 indicates an uncompressed key, and anything else is invalid. 
    x = comp.subarray(1), 
    // Import x into bigInt library 
    xBig = new bigInt(x); 

    // y^2 = x^3 - 3x + b 
    var yBig = xBig.pow(3).sub(xBig.multiply(3)).add(b).modPow(pIdent, prime); 

    // If the parity doesn't match it's the *other* root 
    if(yBig.mod(2) !== signY) 
    { 
     // y = prime - y 
     yBig = prime.sub(yBig); 
    } 

    return { 
     x: x, 
     y: yBig.toUint8Array() 
    }; 
}