5
$\begingroup$

You may already have noticed that most smart cards ship with 2048-bit RSA support and 320-bit ECC over GF(p) support. You may have already asked yourself "why exactly 320-bit?". Now I remember having read a while ago (I can't find the reference sorry), that you can use the 2048-bit RSA to somehow hack together 320-bit ECC.

Now my question is:
Is there actually any relation between maximal RSA and ECC key length and if so how can you get 320-bit ECC from 2048-bit RSA and why is it limited to 320-bits when the RSA engine can do 2048-bit?

Please note: I'm pretty sure they are not paired because of equivalent security, because they provide vastly different security.
320-bit ECC provides roughly 160-bit security and RSA-2048 provides roughly 112-bit security, so this can't be the reason.
I'm suspecting this to be related to the functional large (RSA) integer units of the smart cards which are somehow used to do 320-bit ECC, however the interesting part here would be "why not 512-bit or 1024-bit ECC?" and it should be some technical limitation because it's shared across many different smart card manufacturers.

$\endgroup$
  • $\begingroup$ Possible duplicate of ECC vs RSA: how to compare key sizes? $\endgroup$ – Biv Jan 2 '16 at 15:40
  • $\begingroup$ @Biv, no. The linked question asks about "what RSA key length is comparable in terms of security to what ECC key length?". My question is asking about "Why is 2048-bit RSA always paired with 320-bit ECC on smart cards?" and especially the technical aspect. I know that strength(320-bit ECC) > strength(2048-bit RSA). $\endgroup$ – SEJPM Jan 2 '16 at 15:43
5
$\begingroup$

As far as I know, there is no mathematical trick to put hardware doing a full modexp engine (with modulus register meaningfully sized for RSA) to good use for ECC; an hypothetical such engine is bound to get very much under-utilized with the typically much smaller modulus used for ECC.

However, in Smart Cards, hardware support for RSA does not use such engine; rather it is used a dedicated a co-processor with some moderately wide wordsize $w$ bits, matching multiplier, and a small RAM with wide databus. Arguments are split into $w$-bit chunks just as is done on regular CPUs. RSA and ECC are built on top of that using microcode for that coprocessor, and software in the main CPU. Up to some limit for $w$, processing time decreases as $2^{-2w}$. Public details are scant, but consistently $w$ is many times below the width of an RSA secret prime (typically 512-bit at the very least), and at least often below the width of the public modulus for the group on which the ECC curve is built (typically 160-bit at the very least).

So my guess on what limits the RSA and ECC key size supported by Smart Card RSA and ECC accelerators are:

  1. The size of the RAM accessible by the coprocessor, which at least sometime is dedicated and uses a sizable portion of the silicon. That might sometime answer the question. The RAM size accessible by the coprocessor is closely tied to the upper bound for RSA; it also defines a different bound for ECC; and that later bound is much lower because point multiplication requires a much larger number of intermediate values the size of the base group.
  2. What's achievable at decent speed given word width $w$ of the coprocessor. Going to the next number of chunks might be impractical even if there is enough RAM, as time is proportional to roughly the cube of the number of chunks (for ECC: to the square of the number of chunks times hash width, but since the number of chunks is lower, going to the next number of chunks creates an even wider gap).
  3. Market demand: standard key sizes are few, which combines with 2 to make the upper size commercially supported rather arbitrary.

Note: I'm not confirming the numbers in 2048-bit RSA always paired with 320-bit ECC. In fact, most modern Smart Card ICs I see around support higher limits, substantially so for RSA.

$\endgroup$
5
$\begingroup$

As far as I've understood it's purely about how much RAM is reserved for the operations. High end smart card chips generally have something like 8 to 12 KiB of transient memory available. Top size is about 32 KiB but those chips are both expensive and contact only.

The higher the bit range, the more memory needs to be reserved for cryptographic operations. Any high end processor I know ships with a multiplier implementation that can handle 521 bit curves (to be able to use NIST curve P-521). These higher bit ranges are usually in the data sheets of the processors.

RSA uses less efficient modular exponentiation because of the size of the modulus. ECC operations are however more complex and may require more intermediate state. I.e. the efficiency of ECC may not directly translate into lower memory usage for the computations.

Note that (S)RAM is extremely expensive with regards to die size. Many smart card chips are still manufactured using relatively large node size (e.g. 90 - 180 nm), so every transistor counts.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.