Source text, key size relationship for encryption/decryption in Go

Question

In the code below (also at http://play.golang.org/p/77fRvrDa4A but takes "too long to process" in the browser there) the 124 byte version of the sourceText won't encrypt because: "message too long for RSA public key size" of 1024. It, and the longer 124 byte sourceText version, work with 2048 bit key size.

My question is how does one exactly calculate the key size in rsa.GenerateKey given the byte length of the source text? (A small paragraph size of text takes nearly 10 seconds at 4096 key size, and I don't know the length of the sourceText until runtime.)

There's a very brief discussion of this at https://stackoverflow.com/a/11750658/3691075, but it's not clear to me as I'm not a crypto guy.

My goal is to encrypt, store in a DB and decrypt about 300-byte long JSON strings. I control both the sending and the receiving end. Text is encrypted once, and decrypted many times. Any hints of strategy would be appreciated.

package main

import (
    "crypto/md5"
    "crypto/rand"
    "crypto/rsa"
    "fmt"
    "hash"
    "log"
    "time"
)

func main() {
     startingTime := time.Now()
     var err error
     var privateKey *rsa.PrivateKey
     var publicKey *rsa.PublicKey
     var sourceText, encryptedText, decryptedText, label []byte

    // SHORT TEXT 92 bytes
     sourceText = []byte(`{347,7,3,8,7,0,7,5,6,4,1,6,5,6,7,3,7,7,7,6,5,3,5,3,3,5,4,3,2,10,3,7,5,6,65,350914,760415,33}`)
     fmt.Printf("\nsourceText byte length:\n%d\n", len(sourceText))

    // LONGER TEXT 124 bytes
    // sourceText = []byte(`{347,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,65,350914,760415,33}`)
    // fmt.Printf("\nsourceText byte length:\n%d\n", len(sourceText))

    if privateKey, err = rsa.GenerateKey(rand.Reader, 1024); err != nil {
         log.Fatal(err)
    }

    // fmt.Printf("\nprivateKey:\n%s\n", privateKey)

    privateKey.Precompute()

    if err = privateKey.Validate(); err != nil {
         log.Fatal(err)
    }

     publicKey = &privateKey.PublicKey

     encryptedText = encrypt(publicKey, sourceText, label)
     decryptedText = decrypt(privateKey, encryptedText, label)

     fmt.Printf("\nsourceText: \n%s\n", string(sourceText))
     fmt.Printf("\nencryptedText: \n%x\n", encryptedText)
     fmt.Printf("\ndecryptedText: \n%s\n", decryptedText)

     fmt.Printf("\nDone in %v.\n\n", time.Now().Sub(startingTime))
}

func encrypt(publicKey *rsa.PublicKey, sourceText, label []byte) (encryptedText []byte) {
     var err error
     var md5_hash hash.Hash
     md5_hash = md5.New()
     if encryptedText, err = rsa.EncryptOAEP(md5_hash, rand.Reader,           publicKey, sourceText, label); err != nil {
         log.Fatal(err)
     }
     return
}

func decrypt(privateKey *rsa.PrivateKey, encryptedText, label []byte) (decryptedText []byte) {
     var err error
     var md5_hash hash.Hash
     md5_hash = md5.New()
     if decryptedText, err = rsa.DecryptOAEP(md5_hash, rand.Reader, privateKey, encryptedText, label); err != nil {
         log.Fatal(err)
     }
     return
}

Answer 1

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 3]

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.