How to multiply scalar value with point on NIST P-256 curve?

help
1

Hello.

I need to implement the following "elliptic curve" calculation in Rust langauge, where w is a scalar and G is a point on the NIST P-256 curve:

L = w * G

Test vector is as follows:

w   = 0x44363d157f471221b1e75e596ff4714a712b9578301665d84ec17004952523a8
G.x = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
G.y = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5

Expected result:

L.x = 0xff69eb6086938b3cce2c9e64dcacea1a925918e75e8c17948d316322d370123f
L.y = 0x69132aed7398919e6e6614f7627b0a54060c5a8c0d93d2754166ab10fea6a8ff

For reference, here is my working implementation in Python:

from ecdsa.curves import NIST256p
from ecdsa.ellipticcurve import PointJacobi

scalar_w = bytes.fromhex("44363d157f471221b1e75e596ff4714a712b9578301665d84ec17004952523a8")
point_Gx = bytes.fromhex("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296")
point_Gy = bytes.fromhex("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5")

w = int.from_bytes(scalar_w, 'big')
G = PointJacobi.from_bytes(NIST256p.curve, b'\x04' + point_Gx + point_Gy)
L = w * G

print(f"L.x = 0x{L.x().to_bytes(32, 'big').hex()}")
print(f"L.y = 0x{L.y().to_bytes(32, 'big').hex()}")

But how to do this in Rust?

I have tried with the p256 package (from Rust Crypto), and this is what I got so far:

use p256::AffinePoint;
use p256::EncodedPoint;
use p256::FieldBytes;
use p256::NonZeroScalar;
use p256::ProjectivePoint;

#[allow(non_snake_case)]
fn main() {
    let scalar_w = hex::decode("44363d157f471221b1e75e596ff4714a712b9578301665d84ec17004952523a8").unwrap();
    let point_Gx = hex::decode("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296").unwrap();
    let point_Gy = hex::decode("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5").unwrap();

    let w = NonZeroScalar::from_repr(*FieldBytes::from_slice(&scalar_w[..])).unwrap();
    let G = EncodedPoint::from_bytes([&[ 0x04u8 ], &point_Gx[..], &point_Gy[..]].concat()).unwrap();

    /* let G = AffinePoint::try_from(G).unwrap();
    let G = ProjectivePoint::from(G); */

    println!("w: {:?}", w.to_string());
    println!("G: {:?}", G);

    // let L = w * G; <-- How to do this ????
}

But now I'm stuck and don't know how to do the multiplication :thinking:

Also, do I need to convert EncodedPoint to AffinePoint and/or ProjectivePoint first ???

(I think PointJacobi on Python is a sort of a projective point, though I'm not a math expert)

Any help would be much appreciated!

Thank you.

2

Let's skip past the "don't write your own cryptography", since nobody gets here without a good reason :wink:

"Jacobi point" is probably not this one - I'm guessing your python code example uses the Jacobian curve representation for it's implementation.

In practice, there's a whole bunch of implementations for "how to do this multiplication": Wikipedia alone lists 6 - from peeking into the guts of p256 it seems like it's done on an AffinePoint using VerifyPrimitive, which does a little cooking (a manual Galois multiplication maybe?) then disappears into some trait code so I can't follow; but mentions "reduction" which I'm assuming is Montgomery reduction from the last algorithm in that Wikipedia list of algorithms.

3

Let's skip past the "don't write your own cryptography", since nobody gets here without a good reason :wink:

That is exactly why we do not implement EC math on NIST P-256 curve ourselves, but use the existing EC crypto libraries, such as p256 crate in Rust :slightly_smiling_face:

In the meantime, I have been told that you cannot multiply a Scalar to an AffinePoint in Rust, but it works the other way around! Apparently the operation is commutative, so that's okay. Result will be a ProjectivePoint, but this has functions to convert back to an AffinePoint.

const G: AffinePoint = AffinePoint::GENERATOR;
const W_1: [u8; 32usize] = hex!("44363d157f471221b1e75e596ff4714a712b9578301665d84ec17004952523a8");

let value = FieldBytes::from_slice(&W_1[..]);
let w_1 = *NonZeroScalar::from_repr(*value).unwrap();

let l = G * w_1;
let l_affine = l.to_affine()

I'm no getting the result that matches the expected result for the test vector. So, problem solved.

4

Generally you would use it with the ecdsa crate as well and use the higher level methods they provide like DigestVerifier in signature - Rust though.

5

I don't use/implement ECDSA, though. I'm implemeting a different security protocol (from automotive sector) that uses EC operations on the NIST P-256 curve, but for which there is no ready-to-use "high level" implementation in RUST yet – just a specification that vendors have to implement. So, this will be implemented according to the official specification and it will be tested against the official test vectors. Of course, we want to re-use crypto primitives form the existing crypto libraries (which are already well tested) as much as possible, but someone has to do the work to splice it all together in order to implememt the "high level" protocol... :smiling_face:

6

Yep, that's (obviously) a good reason!