gnark icon indicating copy to clipboard operation
gnark copied to clipboard

Unsound RSA factorization example in Gnark playground

Open Merricx opened this issue 1 year ago • 1 comments

RSA factorization example from the playground (https://play.gnark.io/?id=rsa) is insecure and unsound. As an official example, this can lead/motivate developer to mistakenly implement circuit this way which overflows the field scalar.

Possible Fix

Modify the example to use secure implementation or completely remove the example from the list.

Steps to Reproduce

  1. Go to https://play.gnark.io/?id=rsa (or select RSA from list of examples)
  2. Input p = 11 and q = 1911206752956283776164357558475291228069948176341344037444675585134493642681 in witness.json
  3. Proof should be valid, although they are not the intended factors.

Merricx avatar Sep 04 '24 08:09 Merricx

Indeed, the curve we use for the playground example has smaller scalar field than the RSA modulus. I think we need to either update the example to have smaller values (smaller RSA) or add an example which uses non-native arithmetic for the multiplication to ensure we don't overflow.

I'll create a tracking issue, thanks for reporting.

ivokub avatar Sep 04 '24 11:09 ivokub