RSA verification circuit using halo2 library.

DO NOT USE THIS LIBRARY IN PRODUCTION. At this point, this is under development. It has known and unknown bugs and security flaws.

This library provides a RSA verification circuit compatible with the halo2 library developed by privacy-scaling-explorations team. It will allow halo2 developers to write circuits for verifying RSA-based cryptographic schemes such as RSA signature, RSA accumulator, and verifiable delay function. Specifically, our library provides the following two chips.

1. BigIntChip

The BigIntChip defines constraints for big integers, i.e. integers whose size is larger than that of the native field of the arithmetic circuit. You can perform various operations of the big integers, e.g. allocation, addition, subtraction, multiplication, modular operations, and comparison.

2. RSAChip

The RSAChip defines constraints for verifying the RSA relations. That is, for the integer x and RSA public key (n, e), it computes x^e mod n. Moreover, it also supports the verification of pkcs1v15 signatures.

We have completed the development of both chips. The BigIntChip and RSAChip is placed in the big_integer module and top module, respectively.

• rustc 1.65.0-nightly (0b79f758c 2022-08-18)
• cargo 1.65.0-nightly (9809f8ff3 2022-08-16)

You can install and build our library with the following commands.

git clone https://github.com/SoraSuegami/halo2_rsa.git
cd halo2_rsa
cargo build --release

You can open the API specification by executing the following command under the halo2_rsa directory.

cargo doc --open

You can run the tests by executing the following command under the halo2_rsa directory.

cargo test

• Sora Suegami

This project is licensed under the MIT License - see the LICENSE.md file for details

We have developed our library by reference to the circom-rsa-verify repository, which contains a circuit of pkcs1v15 signature verification in the circom language. It verifies signatures by first defining a circuit for modular multiplication of big integers and then using the circuit to perform modular exponentiation.

We implemented our circuit using a similar approach. In addition, the range check, the verification of whether a given integer is within a certain range, was optimized using a lookup table. This optimization allows the prover to prove that multiple integers are in the specified range in batch.