rsa
RSA-2048 signature verification via multi-channel RNS arithmetic.
Verifies s^{65537} ≡ m (mod n) for a 2048-bit RSA modulus n without native 2048-bit arithmetic. Integers are represented in a Residue Number System (RNS) defined by 11 pairwise coprime ~384-bit primes p_1, …, p_{11}.
Each modular reduction a·b = q·n + r in the exponentiation chain is verified by evaluating chunk polynomials at α_i = (2^{96})^4 mod p_i via Horner’s method and checking a(α_i)·b(α_i) - q(α_i)·n(α_i) - r(α_i) = 0 for all i.
The CRT exactness theorem guarantees that if all 11 channel checks pass and ∏ p_i exceeds the maximum deviation |a·b - q·n - r|, then the integer relation holds exactly.
Fully qualified path: garaga::signatures::rsa
Free functions
| is_valid_rsa2048_signature_assuming_encoded_message | Verify an RSA-2048 signature assuming the message is already encoded. Given public key n and signature data (s, m, 17 reduction witnesses), verifies s^{65537} ≡ m (mod n) by: 1…. |
| is_valid_rsa2048_sha256_signature | Verify an RSA-2048 signature against a raw message using SHA-256. Computes SHA-256(message) on-chain, constructs the PKCS#1 v1.5 encoding,… |