Common question: How to encrypt using RSA
This is very popular question in the newsgroups. Many people answers it without a full comprehension of the (non) problem. So it seems to stay a mysterious subject for many people.
Problem: People try to encrypt using RSA and face a limit of 117 bytes.
Why ? Here's a simple explaination...
RSA is all about mathematics - it's a simple equation with big numbers (as opposed to a complex equation with small numbers ;-). What you are encrypting is only a value in the equation. Because, by default the framework, RSA uses 1024 bits keypair your value must have 128 bytes (1024 bits / 8 bits/byte).
Next comes the padding. Raw encryption, without padding, is not secure because your (128 bytes) number could be very small. Raw encryption isn't possible using the Microsoft .NET framework - EncryptValue and DecryptValue thrown an UnsupportedException (but is supported with Mono::). This is a restriction of CryptoAPI used in RSACryptoServiceProvider.
The most common padding mechanism (for asymmetric keys) is PKCS#1 version 1.5. Without describing the padding, look at PKCS#1 specification or Mono's source code if you want the details, let's say that the PKCS#1 padding length is 11 bytes. So the theoratical maximum of 128 bytes minus the 11 bytes of padding gives you a maximum of 117 bytes for encryption.
A newer padding mechanism is OAEP. It's not much used in standards right now but the padding algorithm has been proven secure (warning: this may not means to you the same thing that it does to a cryptographer ;-). CryptoAPI supports OAEP only for Windows XP and later operating systems - the documentation talks about Windows 2000 with the high encryption pack but I was unable to make it work. As Mono doesn't use CryptoAPI it doesn't have this restriction, so OAEP is available anywhere Mono works :-).
Next question: Could someone iterate the encryption process for every 117 bytes (PKCS#1) ? The anwser is yes but that would be a very slow process - and I wouldn't recommand it as there is a much better alternative.
Now the implied question - which is, much of the time, unanwsered on the newsgroups: Knowing the limitation about encrypting with RSA, what should I do ?
A key exchange. Why ?
First, RSA is slow and symmetric algorithms, like AES, are fast. So encrypting all the data using a symmetric algorithm make sense - performance wise. It also make sense "security wise" because a 128 bits symmetric key is more secure than a 1024 bits asymmetric keypair (at least for RSA) - so we aren't weakening the total security of the encryption.
Second, symmetric key size are much smaller (e.g. AES 256 bits == 32 bytes) than the 117 bytes limits of PKCS#1. So it's easy to encrypt a symmetric key using the RSA public key.
Third, symmetric key management is complex so we don't want to do that. Using password to derive keys is possible (but that's another often misundertood subject) but less secure. Anyway we already have a solution because we can concatenate the results of 1 (encrypted data) and 2 (encrypted key).
This means that the receiver must first decrypt the symmetric key using it's private key. Once he have the symmetric key he can decrypt the whole document. This is much faster than using only RSA, less complex than handling secret keys between many people, and more secure than using password to derive keys. PKCS#7 describes a, ASN.1 based, data format that support encryption (and signature). The new v2 framework will include a namespace, System.Security.Cryptography.Pkcs to handle such structures.
I like to think that I'm better at C# than in english so here a little code to illustrate the concept:
I also wrote a little and very simple tool using the same source code (i.e. it's not meant for production, or even personnal, use). Here is how to use the tool:
crypt /k "keypair"
- Create a new keypair. The file "keypair".key contains both the private and public keys and you should it really private (it's not encrypted). The file "keypair".pub only contains the public key and can be shared with your friends.
crypt /e "file" "keypair"
- This will encrypt the file "file" using the public key contained in the file "keypair".
crypt /d "file" "keypair"
- This will decrypt the file "file" using the private key contained in the file "keypair".
Here's how to test the tool:
> crypt /k poupou
CRYPT sample CRYPT sample for educational use only
Copyright 2003 Motus Technologies. All rights reserved. Released under MIT X.11
Created private file poupou.key
Created public file poupou.pub
> crypt /e crypt.txt poupou
> crypt /d crypt.txt.enc poupou
You could use this tool to exchange documents with friends - assuming you have their public key. (Oh no, not again) But how would they send their public key to you ? by email ? how would you trust that this is really their public key or even their email ? hmmm... you had better sent a wireless brick - if you had one ;-).
Note: Yeah yeah I know this is exactly what we do with Mono's CVS using SSH.
11/1/2003 13:51:19 | Comments
The views expressed on this website/weblog are mine alone and do not necessarily reflect the views of my employer.