search

dalek-cryptography / curve25519-dalek

A pure-Rust implementation of group operations on Ristretto and Curve25519
Other
850 stars 416 forks source link

How to check a VerifyingKey point is within the prime order subgroup #623

Closed randombit closed 4 months ago

randombit commented 5 months ago

Given a VerifyingKey that I've created from bytes sent to me by another party, how can I check that the point is within the prime order subgroup?

IIUC, I can check if it is contained entirely within the torsion subgroup using is_weak(), but to check that it is within the subgroup mod \ell the best I can find is

pk.to_montgomery().to_edwards(0).unwrap().is_torsion_free()

which seems quite contorted, not to mention pointlessly expensive.

Am I missing something that would make this easier/cheaper?

tarcieri commented 5 months ago

I guess one of the immediate concerns here is there is no From<VerifyingKey> for EdwardsPoint impl, or a to_edwards method, to get the EdwardsPoint out of a VerifyingKey, which seems like an oversight.

I believe this would be checked if we implemented NIST's "D.1.3.2. Full Public Key Validation": see https://github.com/dalek-cryptography/curve25519-dalek/issues/380#issuecomment-1487681764. Namely step 3:

  1. Verify that nQ = (0,1). Output REJECT if verification fails.
randombit commented 4 months ago

Opened a patch proposal in #624

randombit commented 4 months ago

Thank you for the fast review!