This was discussed some time back on the pgp developers' list, and at that time the suggestion was made to add a multiple of n to m so that it covered a fuller range of values. The recipient would then just take the exponent mod n and try that.
What I suggest is making the exponent (the encrypted session key) completely random over the length assigned to it, since that's visible, and just live with a slightly non-flat distribution of exponents mod n. It turns out that this can be made to work just fine.
Mathematically, call L the next multiple of 256 above n.
n is the modulus. Divide L by n to get L = t * n + s, s in [0,n). Assume x is random in [0,L). The entropy of x mod n is E = - s (t+1)/L log (t+1)/L - (N-s) t/L log t/L Rearranging, we get: (get out some paper, do the algebra) E = log L/t - s(t+1)/L log( 1 + 1/t ) This makes sense, since if s is zero, E = log n, which is just the entropy of the random distribution of [0,n). What is the smallest value of E? In other words, what's the upper bound of the randomness we can lose? It happens when when t = 1 and when n = L/2+1. This maximize the expression in t and maximizes s at n-2. This minimum value of E is E_min = log L - ( ln 2 - 2/L ln 2 ) In other words, the most entropy we can lose is two bits. That's right, only two bits. Since the entropy of the session key is the length of the modulus, for a 1000 bit key the entropy loss is negligible. Therefore, my recommendation is that the session key representation be chosen randomly over [0,2^k) and to use as an actual session key this value mod n. The effective entropy loss is small enough not to worry about. Eric