Алгоритм эллиптической кривой сжатия точки

Question

Я использую Javascript для генерации эллиптических кривых для использования в криптографических приложений обмена сообщениями на основе этого примера кода http://www-cs-students.stanford.edu/~tjw/jsbn/ecdh.html

Открытые ключи будут довольно большими, и я знаю, что это возможно, чтобы сжать их , но я не смог найти алгоритм Javascript или план, чтобы сделать это. Вот статья http://nmav.gnutls.org/2012/01/do-we-need-elliptic-curve-point.html, которая описывает математику.

Answer 1

Сжатие точек эллиптической кривой запатентовано Certicom, поэтому вы не должны использовать его без лицензии, как правило.

Обновление: патент Certicom был истек в 2014 году, в соответствии с комментарием denis bider ниже.

Answer 2

Было бы трудно запатентовать только математическую формулу. Использование квадратичного уравнения y = sqrt (x^3 + ax + b) нельзя запатентовать, и если это так, его нельзя защитить. Разумеется, можно утверждать, что из диофантов (200-298 гг. и работа над гипотезой Холла (около 1971 года) о наименьшей абсолютной разности между квадратом и кубом | y^2 - x^3 | редко меньше х. Перепишите его y^2 - x^3 = ax-b с x < b/a и заметите, что решения в модульных группах помогут уменьшить количество поиска грубой силы в целых числах.

Что запатентовано, это бит, который помогает определить знак y. Этот бит может использоваться для распознавания самого большого решения из (y и M-y) или положительного решения из (y, -y), в зависимости от стандартов, на которые вы смотрите.

Но, поскольку патент принят, вам необходимо обратиться за консультацией.

Как авторитетный криптограф хорошо разбирается в квалификации в данной области техники д-р Дана Бернштейн точек разумных (http://cr.yp.to/ecdh/patents.html), идея пересчета у из й упоминаются в 1986 Miller как тривиальности, чтобы уменьшить след эллиптических кривых в точках основанные на памяти.

Адвокат, специализирующийся на патентных претензиях, может помочь вам оценить, применяется ли патент, если вы не используете нормальный базис в качестве представления точечных координат или в случае ecc в gf (p), или если вы не используете бит для пересчета сжатого значения y, например при выборе случайности k, P1 (x1, y1) и вычислении P2 (x2, y2) = [k] P1 до тех пор, пока tr (y1) == tr (y2) не устранит неоднозначность (немного дорогостоящий процессор, но почему бы и нет?).

В качестве альтернативы вы можете указать, что разрешение квадратичной формулы, очевидно, более дорогостоящее, чем несколько бит, сохраненных на каналах связи, и этот патент не является полезным вообще и даже повреждает окружающую среду, предлагая замену 6 picowatts стоимости передачи на 2 миливата стоимости процессора (Чтобы быть приемлемым, подача патента должна быть новой, нетривиальной и полезной). Тогда вы найдете кривого адвоката, предпочтительно в Калифорнии, и, конечно же, будет местный судья, который присудит вам несколько миллиардов долларов за ущерб, нанесенный окружающей среде, за то, что вы испытываете трудности с вашими навыками программирования и вашим кошельком, учитывая возникающие задержки в выпуске вашего ценного приложения.

Else, как предлагается в другом сообщении, вы отправляетесь на лицензионное решение.

Если ваша заявка направлена ​​на правительство США, вам нужен другой адвокат, чтобы оценить, является ли этот патент и как вы его планируете использовать, уже является частью лицензий, приобретенных NSA в контексте «Suite B» алгоритмов , и в этом случае лицензия могла бы уже выплачиваться гражданами США.

Answer 3

Я предполагаю, что они будут повышенным интересом к решению для сжатия эллиптической кривой JavaScript, с поддержкой фильтрации WebCrypto в браузерах.
В качестве примера я использую кривые NIST, потому что это те, с которыми мне приходилось иметь дело при импорте сжатого открытого ключа в 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 

Эти простые числа всех удовлетворяют уравнению, р по модулю 4 === 3
Что это означает, что вы можете пропустить довольно сложную общую цель Tonelli-Shanks algorithm и использовать простую идентичность найти квадратные корни.

Во-первых, компрессионная часть «точечного сжатия» очень проста. Запишите знак Y, затем сбросьте значение 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; 
} 

Декомпрессия предполагает отрываясь квадратный корень, а затем исправляя в зависимости от бита четности Y. Эта функция зависит от JavaScript big integer library, которая предоставляет следующие функции: добавление, под, умножение, 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() 
    }; 
}