One does not usually calculate the RSA key size based on payload. One simply needs to select one RSA key size based on a compromise between security (bigger is better) and performance (smaller is better). If that is done, use hybrid encryption in conjunction with AES or another symmetric cipher to actually encrypt the data.
If the payload doesn't exceed 300 bytes and you're using OAEP (at least 42 bytes of padding), then you can easily calculate the minimum key size:
(300 + 42) * 8 = 2736 bit
That's already a reasonable size key. It provides good security according to today's norms and is fairly fast. There is no need to apply a hybrid encryption scheme for this.
Now, you may notice that the key size isn't a power of 2. This is not a problem. You should however use a key size that is a multiple of 64 bit, because processors use 32-bit and 64-bit primitives to do the actual calculation, so you can increase the security without a performance penalty. The next such key size would be:
ceil((300 + 42) * 8 / 64.0) * 64 = 2752 bit
Here are some experimental results what some languages/frameworks accept (not performance-wise) as the key size:
- Golang: multiple of 1 bit and >= 1001 (sic!) [used ideone.com]
- PyCrypto: multiple of 256 bit and >= 1024 [local install]
- C#: multiple of 16 bit and >= 512 [used ideone.com]
- Groovy: multiple of 1 bit and >= 512 [local install]
- Java: multiple of 1 bit and >= 512 [used ideone.com: Java & Java7]
- PHP/OpenSSL Ext: multiple of 128 bit and >= 640 [used ideone.com]
- Crypto++: multiple of 1 bit and >= 16 [local install with maximal validation toughness of
Before you decide to use some kind of specific key size, you should check that all frameworks support that size. As you see, there are vastly varying results.
I tried to write some performance tests of key generation, encryption and decryption with different key sizes: 512, 513, 514, 516, 520, 528, 544, 576. Since I don't know any go, it would be hard to get the timing right. So I settled for Java and Crypto++. The Crypto++ code is probably very buggy, because key generation for 520-bit and 528-bit keys is up to seven orders of magnitude faster than for the other key sizes which is more or less constant for the small key size window.
In Java the key generation was pretty clear in that the generation of a 513-bit key was 2-3 times slower than for a 512-bit key. Other than that the results are nearly linear. The graph is normalized and the numbers of iterations is 1000 for the full keygen-enc-dec cycle.
The decryption makes a little dip at 544-bit which is a multiple of 32-bit. Since it was executed on a 32-bit debian, this might mean that indeed there are some performance improvements, but on the other hand the encryption was slower for that key size.
Since this benchmark wasn't done in Go, I won't give any advice on how small the overhead can be.