Anyway. I quickly settled for Tom Wu’s Bigint and RSA library. It is, for the most part, pretty decent. However, it’s still somewhat bugged (a leading zero in BigIntegers is sometimes skipped, which makes messages unparseable), some functions simply make no sense (UTF-8 in the decryption function might be well meant, but is kinda useless if you have non-UTF-8 strings… like binary data) and it’s lacking functionality for messages longer than the key size. This blog post thankfully outlines how to add this functionality for encryption (I added similar functions for decryption, see the source).
For signing/verifying, I chose to ignore the RFCs (implementing another padding scheme in both PHP and JS would have taken too long) and just used swapped encrypt/decrypt functions.
Another limitation of Wu’s lib was the lack of a “proper” import function – I use a modified version (making use of Wu’s jsbn library) of Lapo Luchini’s ASN1 library plus some glue code to extract the actual key data.
For the PHP side, I use PHPSecLib, which works actually pretty well (I only replaced the user_error reporting with proper Exceptions). The only tricky part is that you need to liberally use hex2bin/bin2hex (I build a thin wrapper around it to do exactly that).
After only… oh, about five days of debugging, the libs work as far as I supposed them to work from the beginning. Project deadlines are overrated anyway.