Doing it the hard way requires roughly 1.5 times key length number of modular multiplies (assuming about half the bits are ones and half zeroes) so if the shortcutted public key operation takes 17 units of time the non-shortcutted private key operation takes about 1500 (assuming a 1000 bit key). Each operation is a multiply followed by a reduction modulo the modulus, or roughly a division operation (followed by discard of the quotient and retention of the remainder). Since the data is as many bits as the modulus this usually requires a fairly sophisticated subroutine. The two schemes I've seen are to do it one bit at a time (which only requires one comparison to find out what to do) or the algorithm in the RSAREF package which extracts an entire word of the quotient at a time. Pretty neat.
Also consider: what happens in the future when you want to move to a 2048 or 4096 bit key? Do you have to wait for a more capable Java card to be marketed?
Watch out for elliptic curve because a "message" usually takes sending TWO group elements, instead of just one as for RSA. This makes the message length twice as long as you otherwise might imagine. If you're just coding a session key for the real data this increase is minimal, but for the kind of embedded computation you're thinking of this can be a real gotcha.
Erik Norgaard wrote:
Charles B Cranston wrote:
You should factor in the RSA speedups in your space estimates. Typically a public exponent of 2^16+1 is used so you need not pass this separately for a public key. However, the speedup for the private key operation involves all those other fields in a private key, which expands the space requirements needed considerably. While it is possible to do the private key operation with nothing other than the modulus and private exponent you should try to estimate how long the processor on the Java card would take (years? days? hours?).
My gut feeling is that you will not be able to get both a private key and the data to be encrypted into 245 bytes.
Thanks, well, for normal operations the private key to be applied would be stored on the card. But from my experience, I have learnt not to implement restrictions of valid choices unless there is a very good reason. Eliptic Curves may be supported in future cards and solve the space problem.
The amount of data that should be de-/encrypted is limited, for example the a symmetric key that is used to encrypt the actual message, or a digest to create a signature.
So, I guess this concludes that for the practical puposes, there is room enough :-) Do you know any performance difference for the private key encryption with all components vs. only modulus and exponent?
Cheers, Erik
-- "An Internet-connected Windows machine is tantamount to a toddler carrying a baggie of $100 bills down a city street..."
Charles B (Ben) Cranston mailto: [EMAIL PROTECTED] http://www.wam.umd.edu/~zben
______________________________________________________________________ OpenSSL Project http://www.openssl.org User Support Mailing List [email protected] Automated List Manager [EMAIL PROTECTED]
