Abstract
We propose a new method for shared RSA signing between the user and the server so that: (a) the server alone is unable to create valid signatures; (b) having the client’s share, it is not possible to create a signature without the server; (c) the server detects cloned client’s shares and blocks the service; (d) having the password-encrypted client’s share, the dictionary attacks cannot be performed without alerting the server; (e) the composite RSA signature “looks like” an ordinary RSA signature and verifies with standard crypto-libraries. We use a modification of the four-prime RSA scheme of Damgård, Mikkelsen and Skeltved from 2015, where the client and the server have independent RSA private keys. As their scheme is vulnerable to dictionary attacks, in our scheme, the client’s RSA private exponent is additively shared between server and client. Our scheme has been deployed and has over 200,000 users.

The paper was published in proceedings of the conference ESORICS 2017, Oslo, Norway, September 11-15, 2017.

The paper contains several pages of cryptographic proofs. The RSA key generation involves “l-safe” primes, which is not a standard practice in generating RSA primes. This is worrisome, especially after it became known that the flaw in ID card was caused by other instance of nonstandard RSA prime generation.

Links:
https://link.springer.com/chapter/10.1007/978-3-319-66402-6_19