BigInteger subtraction in JavaCard

2019-05-26 13:22发布

问题:

I am attempting a proof of concept under very constrained technological conditions. My question is: how to efficiently subtract big integers (represented as byte arrays) in a Java Card?.

Now, the details are what make the task tricky. I have access to one smart card. The model is Feitian JavaCOS A22 and runs Java Card 2.2. For full detail, Java Card enables the usage of a very restricted subset of the Java API (namely, no int, no char, and naturally, no BigInteger), but it does support a series of cryptographic primitives that can be detailed on this list.

In particular, my task is to implement classic ElGamal on card. I found two relevant replies so far. In the first one, Maarten points out that ElGamal is not on the standard, and therefore the functionality would need to be implemented. In this answer, thotheolh shares a link to an implementation of DiffieHellman in Java Card 2.2 based on the same principle: since it is not natively supported, it leverages on the functionality of RSA.

The logic is seamless: RSA, ElGamal and DiffieHellman rely on the same basic operation $a^b mod c$. Based on thotheolh's code, I have managed to achieve key generation. Encryption occurs out of the card so it is not my concern. But decryption requires a particular variant. For decryption $b=p-1-x$, where both $p$ and $x$ are BigIntegers. This is the point where I get stuck: how to calculate efficiently $p-1-x$?

回答1:

Well, in fact there is no such thing like native real BigInteger support for JavaCard. There is BigNumber, but I don't think it will fit your requirements.

However, there is a way to undertake this limitation.

There is some JavaCard library that should allow you to deal with arbitrary long big integers - the problem is that your applet could run out of memory. Sources of library are here, and here is the prebuilt .jar.

This approach might work but also likely to be drastically slow on real card. However this isn't an issue, if you run such code in simulator just for PoC.

I've no idea what is your IDE but this is how you can add this library for IntelliJ.


However, as Maarten Bodewes pointed out, you might be better focus on bytes substraction, just because of probable inefficency of any BigInteger JavaCard library.


Hope this helps.

UPD

BigNumber is guaranteed to be at least 8 bytes, but as far, as I tried it, it allows exactly 8 bytes, which is way to small to hold some security-robust parameters. Say, it cat not contain safe prime p that equals to 57896044618658097711785492504343953926634992332820282019728792003956564821041.

You can try this yourself with method getMaxBytesSupported() just to ensure the fact.

So, as you can see, BigNumber is relatively big for JavaCard, but still smaller, than most crypto protocols needs.