Addition of an RSA validation optimization

[dangerousfood]

🧐 Motivation
I replaced my SolRsaVerify library with the OpenZeppelin library. After replacing it there was no optimization equivalent in the OpenZeppelin version. Could you add this feature to the OpenZeppelin library? The difference is ~2,300 gas units on a RSA-2048 signature validation.

https://github.com/adria0/SolRsaVerify/blob/master/src/RsaVerifyOptimized.sol

📝 Details
Add an additional method to the RSA.sol named pkcs1Sha256Optimized with an identical interface but optimized gas.

[ernestognw]

Hey @dangerousfood, thanks for sharing. I see you replaced it for your EMV Validator in colossus-credit/emv-validator#4 with the following gas impact:

validateUserOp: +2,340 gas (+1.83%)
Deployment: +105,717 gas (+10.83%)

I tried to replicate this difference with the following tests:

contract RSADeploymentMock {
    function validate(bytes memory data, bytes memory signature, bytes memory e, bytes memory n) public view returns (bool) {
        return RSA.pkcs1Sha256(sha256(data), signature, e, n);
    }
}

contract RSADeploymentOptimizedMock {
    function validate(bytes memory data, bytes memory signature, bytes memory e, bytes memory n) public view returns (bool) {
        return RsaVerifyOptimized.pkcs1Sha256(sha256(data), signature, e, n);
    }
}

contract RSATest is Test {
    bytes private constant e = hex"010001";
    bytes private constant n =
        hex"d62d80e0419beb12fdb19eaa0f82f99728e36129058a5f97084dbc5785b771c1826249369624794af1f5c88afbcda3bbb7cf5c6a35ff5cc86ccbfba0f8218439646bf9673a3295ce09cf2cb59deb26ab0d5bea14729735c30339d6f8a9e1e09100d5497b3a6e86fad96fc01e7431fb808d71b035064d64f0fb006c6ea6100771e51da0f643d56c1d6448f4525db772e3cee3cc96647b53f314625e93579380d30b9bcad02bc564410c3cdf57414978d829128f65c478ad49abee7517d04f873e4fe90ae8d3cb052abf056f89cb1792483b7dec70129a0d7d3f10e8bcbc911224cc1a639c065d0ddc84d536089a58d14036e5f9e560754451cee3b24eedeeef49";
    bytes private constant signature =
        hex"62d99b3d032c534d6c6838f29fea2cd97b00e866a03620b4d0e9866ce1f89eab71ef2a58b560203d51fd5c222c97ecf6af6a15632c4b47fafb5bb766a6e05c35508ecf847357e4bdcaab6ba1aaff5d433797a533365832253a5879b33451681902d4da935f55883c9796107c8ab63f11344a79877a82e00a74b4e1f53446b49b8eb3b3b38cfd883996278f23f6acb3b23b8087189e5982efc500e463d06cf7ca2421fb4fef24d36b96becdd49c9b51b554924590933cf1209f3a346514b8bccbd08692a9d11b3b3af4be7acfb473086a79f8c495aff98f691b4d5315ba608f34223ca6250eb1b44aff3be194e85dff4e07c6099216d5cc3d4367dbfa9c3c683d";
    bytes private constant data =
        abi.encodePacked(
            hex"6a031234567890abcdef123456780000000000010000034823120100000000000000000054455354303031004d45524348414e5430303132333400414351554952bc"
        );

    function testPkcs1Sha256Verification() public view {
        assertTrue(RSA.pkcs1Sha256(sha256(data), signature, e, n));
    }

    function testPkcs1Sha256OptimizedVerification() public view {
        assertTrue(RsaVerifyOptimized.pkcs1Sha256(sha256(data), signature, e, n));
    }

    function testPkcs1Sha256Deployment() public {
        new RSADeploymentMock();
    }

    function testPkcs1Sha256OptimizedDeployment() public {
        new RSADeploymentOptimizedMock();
    }
}

And got (with optimizer = true and 200 runs):

RSATest:testPkcs1Sha256Deployment() (gas: 344470)
RSATest:testPkcs1Sha256OptimizedDeployment() (gas: 211769)
RSATest:testPkcs1Sha256OptimizedVerification() (gas: 59143)
RSATest:testPkcs1Sha256Verification() (gas: 60254)

The difference would be 132,701 gas units on deployment and 1,111 gas units in runtime, which seems consistent with your results. I tried working on an optimized version that inlines every external library (assuming that EVM jumps between methods are probably increasing runtime costs), removes the _zeroBytes check in tryModExp and replaces some logic with assembly (note that the RsaVerifyOptimized library does assembly returns, which are very different from Solidity returns for internal functions!). The result was a difference of 60529 for deployment and 612 in runtime.

RSATest:testPkcs1Sha256Deployment() (gas: 283941)
RSATest:testPkcs1Sha256Verification() (gas: 59642)

The RsaVerifyOptimized library still costs 499 units less (i.e. 59642-59143) in runtime. I'm thinking that the majority of them must come from the following malleability check in the OZ version that's missing in the RsaVerifyOptimized library:

for (uint256 i = 0; i < length; i += 0x20) {
    // ...
    if (sp < np) break;
    else if (sp > np || p == length - 0x20) return false;
}

For a key of 2048 bits it would iterate 8 times, which I'm estimating that will produce around 400-500 gas units between jumps and arithmetic operations.

---

Although we can work on an optimized variant, we might be able to lower costs by around 500 gas in runtime. There are around 500 units that are still required if you want to keep the malleability check. We may consider just optimizing the current version for the next release.

For the deployment costs, I wouldn't bother too much since it's a 1 time cost (100,000 gas units at 1 gwei with ETH@3000 is 0.3 USD). If deploying an ERC-7579 module, the validation would cost only 1 time and can be reused by all accounts installing the module.