# How much can we compress RSA public keys?

I am wondering to what degree we can define an RSA variant, with a security argument that it is as safe as regular RSA with a given modulus size $m$ (e.g. $m=2048$), in which the public key has a compact representation of $k \ll m$ bits.

We can fix the public exponent to our favorite customary value, e.g. $e=2^{16}+1$ or $e=3$, thus need to store only the public modulus $n$. We need not store the leftmost bit of $n$, which is always set by definition; nor the rightmost bit, which is always set since $n$ is odd. With a little effort, we could save (very) few more bits noticing $n$ has no small divisors, but that will still be $k \sim m$ bits.

We can do better by forcing the $\lfloor m/2-log_2(m)-2\rfloor$ high bits of $n$ to some arbitrary constant such as $\lfloor\pi \cdot 2^{\lfloor m/2-log_2(m)-4\rfloor}\rfloor$. Observe that we can chose the smallest prime factor $p$ of $n$ just as we would do in regular RSA, then find the maximum integer interval $[q0,q1]$ such that any $q$ in that interval cause $n=p\cdot q$ to have the right high bits, then pick a random prime $q$ in that interval (most often there will be at least one, if not we try another $p$). Some of the security argument is that

• generating an RSA key $(p,q')$ using a regular method, with random huge primes in some appropriate range and no other criteria beside the number of bits in $n'=p\cdot q'$, and $p<q$;
• then deciding the high bits of $n$ from those in $n'$;
• then finding $[q0,q1]$, generating $q$ as a random prime in that interval, and setting $n=p\cdot q$;

demonstrably gives the same distribution of $(p,q)$ as said regular generation method, hence is as secure; then we remark that the high bits of $n$ are random (with some distribution not too far from uniform), and public, thus fixing it can't much help an attack (I think this can be made rigorous).

This is now $k \sim m/2+log_2(m)$ bits to express the public key. We can save a few more bits, each one at worse doubles the amount of work to generate the private key (we can repeat the generation process outlined above until we find a key with these bits equal to some public arbitrary constant; or equal to bits from a hash of the other bits if we want a tighter assurance that the scheme is not weakened).

Can we do better, and what's the practical limit?

Update: In RSA Moduli with a Predetermined Portion: Techniques and Applications, Marc Joye discuses this, and reaches $k \sim m/3$ (without claim of optimality). I'm worried that I do not see an argument that the manner in which $(p,q)$ are selected in Algorithm 3 does not weaken $n$ against a dedicated factoring algorithm.

-
Is the goal to reduce the number of bits that need to be made public in order to publish the public key for a given RSA-like scheme or is the goal to reduce the number of bits that must be securely stored to allow one to regenerate one's own public key from scratch? –  ByteCoin Jan 19 '12 at 3:12
@ByteCoin: I want to reduce the number of bits that need to be made public in order to use the public key. In some memory-tight contexts (e.g. Smart Cards), this is quite desirable. –  fgrieu Jan 19 '12 at 9:28
This would only save space while storing the public key. To use the public key to encrypt or verify signatures you'd probably be working in the Montgomery representation in which case the numbers are all the same size as the modulus and can't be compressed. If you're decrypting or signing on the smart card then you're probably exploiting the CRT and the Montgomery representation and using larger exponents so the compression is useless again. This is all rather academic as nobody would use RSA in a memory constrained system anyway! Or please enlighten me if I'm mistaken. –  ByteCoin Jan 19 '12 at 17:35
@ByteCoin: I want to save space when storing issuer/authority public keys in a Smart Card. Pushing things to the limit, it could be this modern device with just 2kB of EEPROM and twice as much RAM. Yes, one can do RSA or Rabin signature verification securely and plausibly fast on such a device with no RSA hardware. A secondary objective is to shorten certificates (embedding ID and Public Key using ISO 9796-2 signature with message recovery), keeping them within a 256 bytes block limit. –  fgrieu Jan 19 '12 at 18:48

Daniel J. Bernstein mentioned your way of compressing RSA public keys in his paper "A secure public-key signature system with extremely fast verification". The naive way you outline roughly doubles the work for each extra bit. If there were a better method which did not run very slowly then it could be repurposed as a factoring algorithm. So if it were possible to decompress arbitrary 104 to 128-bit strings into secure 2048-bit RSA public keys faster than factoring as David Schwartz suggests then that would be quite remarkable. Every time you ran the algorithm you'd effectively be finding the approximately equal sized factors of some 2048bit number of which you'd specified a lot of the bits. Although there's no theoretical reason I can think of why this should be impossible, nor would it render RSA necessarily insecure, it does strike me as rather unlikely.

As you hint, a further (impractical) way to reduce the storage of the unspecified low bits of the modulus would be to store their residues modulo various small primes and reconstruct using the CRT. In theory this should save between 3 to 4 bits for a 2048-bit modulus. You save the space because you can rely on the residues not being zero.

-
Kudos for the Bernstein reference. It traces the idea of fixing the high bits in $m$ to Guillou and Quisquater, in a 1990 paper on ISO 9796(-1); that must also be where I learned of it. However that 1990 reference does not randomize the fixed bits, which (later) turned out to be a bad idea because it might help NFS. –  fgrieu Jan 19 '12 at 8:45
I fail to follow "If there were a better method which did not run very slowly then it could be re-purposed as a factoring algorithm", and think it is disproved by the much improved bound in the reference now in the updated question. The best I can get is that if we can reach $k$ bits with a generation cost $X$, then we have a factoring algorithm of cost $X \cdot 2^k$. –  fgrieu Jan 20 '12 at 16:56

Actually, it appears that we can do a bit better by using an unbalanced RSA key; that is, one composed of two primes of different sizes.

For example, suppose we have a 512 bit p and a 1536 bit q; to generate a key, we can select a random 512 bit prime p, and then for q, we search for a prime in the range $(C/p, (C+2^k)/p)$ (where $C$ is our 2048 bit constant which includes the bits we want to force, and $k$ is the number of bits we're willing to vary). We expect about $2^k/p \times (1 / \log( C/p )) \approx 2^{k-512} / (\log(2) (2048-512))$ primes; if $k \approx 522$, then there would be 1 expected prime in the range. This would allow us to express a 2048 bit RSA key with only 522 bits.

Now, the obvious question is: what does this do to the security. I'm pretty sure that this algorithm generates an RSA modulus which is no easier to factor than a random modulus with the same sized factors, but that doesn't really answer the question. Now, we know that the time taken by NFS doesn't vary based on the size of the factors, but ECM does speed up if there are smaller factors. So, how small can we make $p$ before ECM becomes faster than NFS (and thus lowering our security level)? I don't know the answer to that one (or even if my example of a 512 bit factor would be already over the limit; it wouldn't surprise me if it was).

I believe this trick can be used to shrink RSA public keys to some extent, but I don't know how far you can take it. On the other hand, I do hope this is an academic exercise; if you're really interested in small public keys, it'd certainly be better to use an elliptic curve algorithm (which has small public keys without seeing how close we can get to the security edge).

-
I don't follow this. In what interval are we expecting to find just one prime? For 1536 bit numbers, roughly .1% are primes. –  ByteCoin Jan 19 '12 at 3:00
@ByteCoin: yes, roughly 0.1% of 1536 bit numbers are prime, hence if we make our interval of 1536 bit numbers be 1000 integers long, we have a decent probability that at least one of them actually will be prime. The size of that interval is $(C + 2^k)/p - C/p = 2^k/p$ and so $2^k \approx p * 1000$; that is, the number of bits that we need to publish (because they can't be assumed) is about 10 more than the size of the smaller prime –  poncho Jan 19 '12 at 3:58
As you point out, ECM factoring is made greatly more efficient. I thus see little hope to have a general, positive security argument that the scheme is as secure as balanced RSA. –  fgrieu Jan 19 '12 at 6:55
@fgrieu I seem to remember reading somewhere that the expected runtime of ECM and GNFS was roughly equal when the small factor was roughly 1/3 of the bitlength of the modulus. If we assume that the people on the $x^y+y^x$ factorization project allocate their effort optimally then we can see that their GNFS jobs often yield 50 digit factors of 150 digit numbers and the maximum factors found with ECM are about 56 digits. This lends credence to the idea that the factor size ratio should be no larger than 1:2, at least for numbers of this size. –  ByteCoin Jan 19 '12 at 14:43
@fgrieu You probably want to read "On the security of multi-prime RSA" by Hinek and some of the works it references such as CompaqMultiPrimeWP.pdf. Although your scheme onlt uses 2 prime some of the calculations trading off the difference in the difficulty of ECM and NFS should be relevant. In particular, as the size of n increases, it seems that the ratio between the sizes of the factors can safely increase. I believe that for a 2048-bit modulus having one of the primes 512 bits long should be fine. –  ByteCoin Jan 20 '12 at 0:16