# how to iteratively calculate a^emod n with modulus n sized 4096 bits

In most sites the exponent of the RSA public key is 24 bits. But the modulus can get to 4096 bits size. I have an accelerator that can get max. 2112 bit size modulus. It calculates a^e mod n.

Is there a way to separate $n$ (maybe bit wise) and use the accelerator in several iterations to calculate the wanted a^e mod n?

-
You might be able to use CRT together with multi-prime RSA. –  CodesInChaos Oct 1 '13 at 14:14
Accelerating public key operations sees a bit unusual. Typically it's the private key operation that needs acceleration since it's 100x as expensive. If performance of public key operations is really an issue, I'd consider using e=3 –  CodesInChaos Oct 1 '13 at 14:17
@CodesInChaos: I believe he is getting the public keys from somewhere else, hence they are not under his control –  poncho Oct 1 '13 at 14:20
@CodesInChaos wouldn't there be some security concerns for e=3? –  owlstead Oct 2 '13 at 15:21
Actually, the exponent is normally 17 bits (65537 or 0x010001) in an unsigned representation, but it is normally padded to 24 bits to fit into an N number of bytes. –  owlstead Oct 2 '13 at 15:23
show 1 more comment

I am not aware of any method that would let one make good use of a black box or API computing $f(a,e,n)=a^e\bmod n$ for $n$ of up to $2112$ bits, to efficiently compute $f(a,e,n)=a^e\bmod n$ with $n$ above that bound (like $4096$ bits), unless that bigger $n$ has known factorization into terms of at most $2112$ bits (in which case the usual CRT technique applies and significantly helps).

That issue is encountered when one wants to compute the RSA public key function for 4096-bit key on top of software (or API to hardware) limited to $2048$-bits-and-then some.

Especially if $e$ is small (like $65537$, $17$, $3$, or $2$), it is sometime possible to do a fast-enough software-only implementation in assembly language (which typically beats C by a decimal order of magnitude, and interpreted bytecode much more so). And for the purpose of signature verification, this is unquestionably safe.

But even if $e$ is small, if the context is a JavaCard Smart Card without any way to evade the JavaCard Virtual Machine, I'm afraid there is no practical solution, unless execution time is not an issue.

-
Usually, RSA operations with the public exponent are fast, precisely because the public exponent is short. Hardware accelerators are meant to speed up operations with the private key, which are in much bigger need of it. In particular, hardware accelerators do not need to be "full width" because private key operations use the private key, which contains the factors $p$ and $q$, and allow for doing most of the work modulo $p$ and modulo $q$, both of which being twice shorter than the modulus $n$ (what the CRT is about).