Questions about RSAEncryptionV1_5_Gadget

[hasinitg]

Hi Ahmed @akosba

I have studied the RSAEncryptionV1_5_Gadget and I would appreciate if you could please clarify the following two questions.

1. I found in the comments that the gadget assumes a hard coded public exponent of 0x10001. If I want to give public exponent as input to the gadget, where should I change the encryption logic? According to my understanding, following is the code snippet that is related with the encryption logic using the public exponent, however, I am not clear why it runs for only 16 iterations for the public exponent of 0x10001.

`LongElement s = paddedMsg;

    for (int i = 0; i < 16; i++) {
        s = s.mul(s);
        s = new LongIntegerModGadget(s, modulus, false).getRemainder();
    }
    s = s.mul(paddedMsg);
    s = new LongIntegerModGadget(s, modulus, true).getRemainder();`

2. RSA key length is given as input to the gadget, shouldn't it have any effect on the public exponent?

Thank you very much.

[akosba]

1. If you want to make the public exponent variable, you will have to change the loop you quoted. There are other examples in jsnark that can give you a hint about how to do this, e.g. the ECDH key exchange gadget (although the context there is entirely different). Note that if you make the public exponent variable, make sure to check the recommendations on its maximum value. For your confusion about the 16 iterations, note that you only need 16 square operations here, followed by a single multiplication in the end, which is done outside the loop.

2. As far as I am aware, the public exponent is typically chosen to be 0x10001 in practice. I am not currently aware of a particular attack/vulnerability that would motivate increasing the public exponent beyond that. Your circuit will be more expensive if you support variable exponents. You might find the following relevant: https://crypto.stanford.edu/~dabo/pubs/papers/RSA-survey.pdf (Section 4) and the constraints on the public exponent in these docs: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=61, https://csrc.nist.gov/CSRC/media/Publications/sp/800-56b/rev-2/draft/documents/sp800-56Br2-draft.pdf#page=47. (Note that the key size does not determine how e is chosen)

[hasinitg]

Thank you very much Ahmed @akosba for your detailed reply and for all the valuable pointers you have provided regarding RSA encryption. I appreciate it a lot. I too will stick with the existing public exponent.