RSA-2048 PKCS#1 v1.5 Verification — Primitives

The RSA chiplet proves that a signature verifies under RSA-2048 PKCS#1 v1.5 with SHA-256 and the public exponent 65537, with the modulus public and the signature and the message in the witness.

§ What the proof states

Pkcs1Statement proves s^65537 mod N = EM, where EM is the EMSA-PKCS1-v1_5 encoding of RFC 8017 §9.2 applied to the SHA-256 digest of the message. N is a public 2048-bit input; the signature s and the message are witness, and the digest is chained over committed block words.

§ How the tables split the work

The host table chains SHA-256 one block per row and requests two chiplets over the LogUp bus: modular exponentiation from hekate-gadgets and compression from the SHA-256 chiplet. On the last block row it compares the modexp output with the encoding, limbs 0 to 7 against the digest words and limbs 8 to 63 against the encoding constants. All 56 constant limbs are pinned.

§ Outside the proof

Message padding. FIPS 180-4 §5.1.1 padding is left to the caller.
RSASSA-PSS.
Other moduli and exponents. The statement fixes a 2048-bit modulus and e = 65537.
Signing.

§ Examples

hekate/examples/rsa_pkcs1.rs runs RSA-2048 PKCS#1 v1.5 with SHA-256 end to end on a fixed RSA-2048 key and its signature over the 200-byte message 0, 1, …, 199, both generated with CPython. From a hekate checkout:

bash

just example rsa_pkcs1 public

public builds the variable-time table-math prover that the README's measurements use. Without it the recipe builds the constant-time prover, the one to use when the witness is private.

The program below drives the crate the same way, at two rounds per row and 512-row tables, in two files: src/key.rs holds the example's modulus N and signature S as 64 limbs of 32 bits each, and src/main.rs builds the statement with Pkcs1Statement, proves and verifies. Start from the crates in Installation and add hekate-rsa, hekate-sha2 and rand.

src/key.rssrc/main.rs

rust

1pub const N: [u32; 64] = [
2    0x3a4cd3af, 0x66d45f4b, 0x3f3be64e, 0xb2e418a0, 0x742ea128, 0x27e345b9, 0xb108f0a3, 0xa6f8429a,
3    0xc72689b4, 0x4f8f7e38, 0xce80a527, 0x87411f36, 0xcd98948c, 0x519ea53b, 0x22687894, 0x0d4d92f2,
4    0xf08075d6, 0xcaf97b9b, 0xdce5fffe, 0x4acd311e, 0x99604ca5, 0xf033bd1e, 0x7bd5b173, 0x62685cef,
5    0x7a14f624, 0x8124d7ad, 0xd86c706c, 0x3c5cf329, 0x0326fe04, 0xa25d9739, 0xb32f3618, 0x62616eef,
6    0x0be6d55d, 0x798e6118, 0x7c955161, 0x96e68b02, 0x9c992aa1, 0xe26db0b1, 0xabcb78c9, 0x8902c9c6,
7    0xc69ebade, 0x34836040, 0xb993f3f6, 0x61c9132d, 0x36f6db51, 0x513061eb, 0xd14ee03a, 0x730ec5b8,
8    0x2416eb11, 0x6103a696, 0xf50eccc4, 0x52d8f47f, 0xbd54d737, 0x8933ec2a, 0x052eeb80, 0x86caea5c,
9    0x042752d0, 0x75c552d8, 0x5646de60, 0xf0c63af4, 0xde43815a, 0x4823c34e, 0x7e65c266, 0xd116244d,
10];
11
12pub const S: [u32; 64] = [
13    0x7897deff, 0x54c0389d, 0x6369e349, 0x1d7ff0df, 0x41b31683, 0x993e97c4, 0x5fe7fabc, 0x2ae01b48,
14    0xbcce59d5, 0xe7e1adcb, 0xd5bd2f3a, 0xf1b9a348, 0xd4919224, 0xe507d801, 0x60fcca30, 0x459ba412,
15    0x206c7dcd, 0xae3fb65d, 0x607ae10d, 0x0ef5293c, 0x1b9f6745, 0x3a114648, 0x671f96db, 0xb341eab5,
16    0x98cd1f12, 0x8960b317, 0x0c67d850, 0x0dfc05c8, 0x531c86be, 0xe8ccea73, 0xff2f2e3a, 0x5aef901c,
17    0xd99089a1, 0xd2ffe09c, 0x78aaf7aa, 0x40a51646, 0x9cd6c6e1, 0x5a8cd9a3, 0xc2b15955, 0xcbb79a47,
18    0x1837ca53, 0xaf04db30, 0xf580b968, 0xfc839ed3, 0x3061abc2, 0x84475224, 0x7218c6fb, 0x1fabca0e,
19    0x58467859, 0x726b3d7f, 0xc33b246f, 0xc660be0d, 0x230dd49c, 0x25e755a6, 0xca114abf, 0x5cdc2d7e,
20    0x0e97d198, 0x77101fcc, 0xcf5a2b1f, 0x53e60c09, 0x5e0682b7, 0x1ed8bd9b, 0x6c7f6532, 0x9f1e9450,
21];

1mod key;
2
3use hekate_core::config::Config;
4use hekate_crypto::DefaultHasher;
5use hekate_crypto::transcript::Transcript;
6use hekate_math::Block128;
7use hekate_program::digest::program_id;
8use hekate_prover_sys::prove;
9use hekate_rsa::Pkcs1Statement;
10use hekate_sdk::preflight;
11use hekate_sha2::pad_message;
12use hekate_verifier::HekateVerifier;
13use key::{N, S};
14use rand::{TryRng, rngs::SysRng};
15use std::error::Error;
16
17const LABEL: &[u8] = b"rsa-pkcs1";
18const ROUNDS_PER_ROW: usize = 2;
19const SHA_ROWS: usize = 512;
20const CPU_ROWS: usize = 512;
21
22type F = Block128;
23
24fn main() -> Result<(), Box<dyn Error>> {
25    let message: Vec<u8> = (0..200).collect();
26    let num_blocks = pad_message(&message).len();
27
28    let config = Config::default();
29    let statement = Pkcs1Statement::new(num_blocks, ROUNDS_PER_ROW, SHA_ROWS, CPU_ROWS)?;
30    let program = statement.program();
31
32    let instance = statement.instance(&N);
33    let witness = statement.witness(&message, &N, &S)?;
34
35    let report = preflight(program, &instance, &witness)?;
36
37    if !report.is_clean() {
38        eprintln!("{report}");
39
40        return Err("the trace fails preflight".into());
41    }
42
43    let mut seed = [0; 32];
44    SysRng.try_fill_bytes(&mut seed)?;
45
46    let proof = prove(LABEL, program, &instance, &witness, &config, seed, None)?;
47
48    let id = program_id::<F, _>(program)?;
49    let mut transcript = Transcript::<DefaultHasher>::new(LABEL);
50
51    let valid = HekateVerifier::<F, DefaultHasher>::verify(
52        &id,
53        program,
54        &instance,
55        &proof,
56        &mut transcript,
57        &config,
58    )?;
59
60    if !valid {
61        return Err("the verifier rejects the signature".into());
62    }
63
64    println!("the verifier accepts the signature");
65
66    Ok(())
67}

N is the only public input; the message, its digest and the signature stay in the witness. The statement pins no SHA-256 padding: the proof shows that the prover holds a four-block message with a valid signature under N, and the message length is not fixed.

§ Performance

Zero-knowledge proofs, measured on Apple M3 Max, 16 cores. Build: --release, std parallel blake3 table-math public. Best of three on an otherwise idle machine. The Benchmarks page has the base-protocol figures and the command for each run.

Workload	Input	Proving	Verify	Proof size	Peak memory
RSA-2048 PKCS#1 v1.5	RFC 8017	209 ms	8.0 ms	1,813 KiB	401 MiB

§ Security

The crate has not been audited and may contain bugs and security flaws, as its README states. Hekate proves 100 bits of soundness.

§ License

hekate-rsa is AGPL-3.0-only. Commercial licenses are available from Oumuamua Labs at info@oumuamua.dev. The README's Usage section builds the statement for one RSA-2048 signature, and the API reference is on docs.rs.