# How to sign a message using RSA?

Assuming I already have a D, P, Q, etc of an RSA key: How do I now sign a message? If it matters – the message is around 100 bits.

I don't know much about cryptography, but I can get these numbers generated by a computer. Unfortunately, in my scenario – I can't use the built-in functions to use these numbers.

-
Read PKCS#1, in particular don't ignore the part about padding. –  CodesInChaos Apr 25 '12 at 20:01
@CodeInChaos So you're saying it can't realistically be done in a simple manner (i.e. without spending a week studying cryptography), right? By the way, if you have some solution as to how I can create an activation key in a web hosting environment – where they have RSACryptoServiceProvider blocked – I'd be happy to hear about it. –  ispiro Apr 25 '12 at 20:14
Look into the relevant Mono classes. With a bit of work, many of them work on .net, and the license is permissive. –  CodesInChaos Apr 25 '12 at 20:23
@ispiro Realistically, you can't make any code that's secure without thoroughly understanding the characteristics of the primitives you are using. That's why, RSA is a bad choice as primitive. If, for example, you can pick OpenSSL's EVP layer as your primitive, you'll barely have to know much about RSA, except that it's an asymmetric cipher than can both sign and encrypt. –  David Schwartz Apr 25 '12 at 23:08

IMO implementing RSA yourself is a bad idea. While textbook signing is pretty easy, if you have access to a BigInteger class, you also need to get the padding right. In some use-cases timing attacks are also a problem.

But if you want to go that route, PKCS #1 is the standard you need to implement. It details how the padding should look like.

The text-book RSA signing operation is pretty easy, in principle. Just calculate $m^d \mod n$. Unfortunately without correct use of hashing and padding it's very insecure i.e. you can't use the actual message as $m$, but the padded hash of the message.

I'd look into mono's crypto code. They have purely managed implementations of most .net crypto classes. These should work even if you don't have access to the built in classes.

A few interesting looking classes:

They use the MIT X11 license, which is a permissive open source license.

-
There is another widely used standard for RSA signature, ISO/IEC 9796-2. It allows signature with message recovery, which allows extending the length of the signed message by little more than the size of the hash used (e.g. 22 bytes in the most common setup). Beware that mode 1 of this standard (by far the most common) is broken; the attack is impractical in most common setups. –  fgrieu Apr 26 '12 at 20:04
Thanks. As for BigInteger - See this in .NET 4.0. –  ispiro Apr 30 '12 at 14:36