Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Unsound RSA factorization example in Gnark playground #1267

Open
Merricx opened this issue Sep 4, 2024 · 1 comment
Open

Unsound RSA factorization example in Gnark playground #1267

Merricx opened this issue Sep 4, 2024 · 1 comment

Comments

@Merricx
Copy link

Merricx commented Sep 4, 2024

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.
@ivokub
Copy link
Collaborator

ivokub commented Sep 4, 2024

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants