RSA Techniques

This is an updated extract from the CryptoSys PKI Toolkit Manual.

Important Note: Many examples of RSA encryption and signing given here use a 512-bit key. This is for convenience and speed in demonstration and testing. Using a 512-bit key is not recommended for production work. Use at least a 1024-bit key in practice, preferably 2048.

Raw RSA Techniques

The original intention of the CryptoSys PKI Toolkit was to provide a set of primitives to carry out S/MIME operations using relatively high-level "Cryptographic Message Syntax" functions. However, we get so many queries about using the "raw" RSA functions that we've added this section on techniques.

The functions RSA_RawPublic and RSA_RawPrivate just carry out the basic RSA encryption or decryption operation on a "raw" block of data. The block must be exactly the same length in bytes as the length of the RSA key modulus; it must obey certain mathematical properties (in practice, make sure the first byte is zero); and it should be formatted in a certain way to improve security and make it easier to pass to other systems (.NET's native cryptography functions hide this part of the process from you).

Encrypting and signing with RSA

Encryption and signing use the same RSA operations:

To encrypt, ciphertextblock = RSA(plaintextblock, public-key)
To decrypt, plaintextblock = RSA(ciphertextblock, private-key)
To sign, signatureblock = RSA(messageblock, private-key)
To verify, messageblock' = RSA(signatureblock, public-key).

Use the function RSA_EncodeMsg to encode or "pad" the message data you want to encryt or sign. Remember that Encoding is Not Encryption.

For more information on how the RSA key data is stored and how the various functions work together, see RSA Key Formats. For some examples in encryption and signing in C#, see Doing RSA Encryption and Signing with the C# code.

Examples in VB6

This sample code shows how to encrypt and decrypt a short message directly and suggests a simple pair of 'Encrypt' and 'Decrypt' functions (without any error handling).

Note that RSA is normally only used to encrypt a session key prior to using a much faster symmetric block cipher algorithm. Similarly it is usually used just to sign a hash of the message rather than the message itself. The size of the "message" in both cases is limited by the length of the RSA key less the padding bytes.

Public Function rsaEncryptBytes(abMessage() As Byte, strPublicKey As String) As Variant
' Uses RSA public key to encrypt a message using default PKCS-1-v1.5 encoding method
' Returns the resulting ciphertext as an array of bytes passed as a Variant, 
' or an empty value on error.
    Dim lngRet As Long
    Dim abDummy(0) As Byte
    Dim abBlock() As Byte
    ' All lengths are in octets (i.e. 8-bit bytes)
    Dim nkLen As Long   ' length, k, of RSA key modulus
    Dim nmLen As Long   ' length of message, M
        
    rsaEncryptBytes = abDummy
    
    ' Compute lengths
    nmLen = BytesLength(abMessage)
    nkLen = RSA_KeyBytes(strPublicKey)
    
    ' Encode using EME
    ReDim abBlock(nkLen - 1)
    lngRet = RSA_EncodeMsg(abBlock(0), nkLen, abMessage(0), nmLen, PKI_EME_DEFAULT)
    If lngRet <> 0 Then Exit Function
    
    ' Encrypt using RSA public key
    lngRet = RSA_RawPublic(abBlock(0), nkLen, strPublicKey, 0)
    If lngRet <> 0 Then Exit Function
    
    ' Return ciphertext block
    rsaEncryptBytes = abBlock
End Function

Public Function rsaDecryptBytes(abCipher() As Byte, strPrivateKey As String) As Variant
' Decrypts RSA-encrypted ciphertext using the RSA private key passed as a string.
' Returns the resulting message as an array of bytes passed as a Variant, 
' or an empty value on error.
    Dim abDummy(0) As Byte
    Dim abMessage() As Byte
    Dim lngRet As Long
    Dim abBlock() As Byte
    Dim nkLen As Long   ' length, k, of RSA key modulus
    Dim nmLen As Long   ' length of message, M
    
    rsaDecryptBytes = abDummy
    
    nkLen = BytesLength(abCipher)
    If nkLen <> RSA_KeyBytes(strPrivateKey) Then
        Exit Function
    End If
    abBlock = abCipher
    
    ' Decrypt
    lngRet = RSA_RawPrivate(abBlock(0), nkLen, strPrivateKey, 0)
    If lngRet <> 0 Then
        Exit Function
    End If
    
    ' Now we decode according to EME-PKCS-V1_5-DECODE
    nmLen = RSA_DecodeMsg(0, 0, abBlock(0), nkLen, PKI_EME_DEFAULT)
    If nmLen <= 0 Then Exit Function
    ReDim abMessage(nmLen - 1)
    nmLen = RSA_DecodeMsg(abMessage(0), nmLen, abBlock(0), nkLen, PKI_EME_DEFAULT)
    
    ' Output M.
    rsaDecryptBytes = abMessage

End Function

Private Function BytesLength(abBytes() As Byte) As Long
' General function to return length of byte array
    ' Trap error if array is empty
    On Error Resume Next
    BytesLength = UBound(abBytes) - LBound(abBytes) + 1
End Function


Public Function TestEncryptAndDecrypt()
    Dim abMessage() As Byte
    Dim abBlock() As Byte
    Dim strPublicKey As String
    Dim strPubKeyFile As String
    strPubKeyFile = "mykeypub.bin"

    ' Convert ANSI text to bytes
    abMessage = StrConv("Hello world!", vbFromUnicode)
    
    Debug.Print "M (ansi): " & StrConv(abMessage, vbUnicode)
    Debug.Print "M (hex):  " & cnvHexStrFromBytes(abMessage)
    
    ' Read in the public key from file
    strPublicKey = rsaReadPublicKey(strPubKeyFile)
    If Len(strPublicKey) = 0 Then
        MsgBox "Cannot read RSA public key file '" & strPubKeyFile & "'", vbCritical
        Exit Function
    End If
    
    ' Call encrypt function
    abBlock = rsaEncryptBytes(abMessage, strPublicKey)
    Debug.Print "CT: " & cnvHexStrFromBytes(abBlock)
    
    ' DECRYPTION
    Dim strPrivateKey As String
    Dim strPriKeyFile As String
    Dim abPlain() As Byte
    strPriKeyFile = "mykeypri.bin"
    
    ' Read in the private key from file
    strPrivateKey = rsaReadPrivateKey(strPriKeyFile, "password")
    If Len(strPrivateKey) = 0 Then
        MsgBox "Cannot read RSA private key file '" & strPriKeyFile & "'", vbCritical
        Exit Function
    End If
    
    ' Call decrypt function
    abPlain = rsaDecryptBytes(abBlock, strPrivateKey)
    Debug.Print "PT (hex) : " & cnvHexStrFromBytes(abPlain)
    Debug.Print "PT (ansi): " & StrConv(abPlain, vbUnicode)
    
End Function

This should produce results similar to this

M (ansi): Hello world!
M (hex):  48656C6C6F20776F726C6421
CT: 4866117CDA08F3E93B39230685BC02...
PT (hex) : 48656C6C6F20776F726C6421
PT (ansi): Hello world!

Note that the encoding for encryption includes random bytes so the resulting ciphertext will be different each time

The next example shows how to sign a message. Unlike the encryption example, the RSA_EncodeMsg function always creates a message digest hash of the original data when in "signing" mode. When verifying, you could use the RSA_DecodeMsg function to extract the message digest hash and then create a separate digest of the original text. But it's much simpler just to use the RSA_EncodeMsg function on the original data and compare the full blocks instead.

    Dim abMessage() As Byte
    Dim abCmpBlock() As Byte
    Dim strPublicKey As String
    Dim strPubKeyFile As String
    Dim strPrivateKey As String
    Dim strPriKeyFile As String
    Dim lngRet As Long
    Dim abBlock() As Byte
    Dim nkLen As Long   ' length, k, of RSA key modulus
    Dim nmLen As Long   ' length of message, M
    
    strPubKeyFile = "mykeypub.bin"
    strPriKeyFile = "mykeypri.bin"
    
    ' PART 1. Encode and sign a message using the private key
    
    ' Convert ANSI text to bytes
    abMessage = StrConv("Hello world!", vbFromUnicode)
    
    Debug.Print "M (ansi): " & StrConv(abMessage, vbUnicode)
    Debug.Print "M (hex):  " & cnvHexStrFromBytes(abMessage)
    
    ' Read in the private key from encrypted file
    strPrivateKey = rsaReadPrivateKey(strPriKeyFile, "password")
    If Len(strPrivateKey) = 0 Then
        MsgBox "Cannot read RSA key file '" & strPriKeyFile & "'", vbCritical
        Exit Function
    End If
    
    ' To sign: first encode the message, then "encrypt" with RSA
    ' Compute lengths
    nmLen = UBound(abMessage) - LBound(abMessage) + 1
    nkLen = RSA_KeyBytes(strPrivateKey)
    Debug.Print "Key is " & nkLen & " bytes long"
    Debug.Print "Message is " & nmLen & " bytes long"
    
    ' Encode for signature
    ReDim abBlock(nkLen - 1)
    lngRet = RSA_EncodeMsg(abBlock(0), nkLen, abMessage(0), nmLen, PKI_EMSIG_DEFAULT)
    Debug.Print "RSA_EncodeMsg returns " & lngRet & " (expected 0)"
    Debug.Print "EM: " & cnvHexStrFromBytes(abBlock)
    
    ' Sign using RSA private key
    lngRet = RSA_RawPrivate(abBlock(0), nkLen, strPrivateKey, 0)
    Debug.Print "SG: " & cnvHexStrFromBytes(abBlock)

    ' Clear the private key for security
    Call WIPE_String(strPrivateKey, Len(strPrivateKey))
    
    ' PART 2. Verify with public key
    
    ' Read in the public key from file
    strPublicKey = rsaReadPublicKey(strPubKeyFile)
    If Len(strPublicKey) = 0 Then
        MsgBox "Cannot read RSA key file '" & strPubKeyFile & "'", vbCritical
        Exit Function
    End If
    
    ' Check its length
    If RSA_KeyBytes(strPublicKey) <> nkLen Then
        MsgBox "Key lengths of private and public key don't match", vbCritical
        Exit Function
    End If
    
    ' Signed data is in abBlock, so "decrypt" it
    lngRet = RSA_RawPublic(abBlock(0), nkLen, strPublicKey, 0)
    
    If lngRet <> 0 Then
        MsgBox "Decryption error", vbCritical
        Exit Function
    End If
    
    Debug.Print "EM: " & cnvHexStrFromBytes(abBlock)
    
    ' We could use RSA_DecodeMsg here to extract the message digest,
    ' then compute the message digest independently of the message,
    ' and then compare the two hashes, but...
    ' it's simpler just to create another encoded block of the original message
    ' and compare the full blocks directly
    ReDim abCmpBlock(nkLen - 1)
    lngRet = RSA_EncodeMsg(abCmpBlock(0), nkLen, abMessage(0), nmLen, PKI_EMSIG_DEFAULT)
    Debug.Print "RSA_EncodeMsg returns " & lngRet & " (expected 0)"
    Debug.Print "EM':" & cnvHexStrFromBytes(abCmpBlock)
    
    If StrConv(abCmpBlock, vbUnicode) <> StrConv(abBlock, vbUnicode) Then
        MsgBox "Verification failed.", vbCritical
        Exit Function
    End If
    
    Debug.Print "Verification OK."

This should produce output like

M (ansi): Hello world!
M (hex):  48656C6C6F20776F726C6421
Key is 64 bytes long
Message is 12 bytes long
RSA_EncodeMsg returns 0 (expected 0)
EM: 0001FFFFFF...FFFFFF003021300906052B0E03021A
05000414D3486AE9136E7856BC42212385EA797094475802
SG: D3C6EC4860...
EM: 0001FFFFFF...
RSA_EncodeMsg returns 0 (expected 0)
EM':0001FFFFFF...
Verification OK.

More Techniques

For encryption in practice, except for very short messages, we generate a random session key, encrypt this key using RSA, and then encrypt the plaintext using a faster, symmetric block cipher like Triple DES or AES-128 (hint to implementors: do this in CBC mode, don't use ECB). This session key is sometimes referred to as the Content Encryption Key (CEK). You would then need to transmit a message to your recipient in the form

+----------------------+----+----------------------------------------------+
| CEK-encrypted-by-RSA | IV | Data-encrypted-by-symmetric-cipher-using-CEK |
+----------------------+----+----------------------------------------------+

where IV is the initialization Vector for the block cipher encryption, generated uniquely each time. To decrypt, parse the input into its three components, use the RSA private key (held separately) to decrypt the RSA block and hence get the CEK to use to decrypt the main body of data. This technique is as strong as its weakest link. Triple DES with a full 192-bit triple key is equivalent in security to a 2048-bit RSA key. AES-128 is equivalent to a 3072-bit RSA key. See [NIST80057] for more details.

For digital signing, unless the message is very short, we generate a message digest of the original message using a hash function, "encrypt" the digest using the RSA private key, and then send this block on to our recipient as a "digital signature", usually together with the message itself.

+---------------+------------------+---------------------+
|Hash algorithm | Original message | RSA Signature block |
+---------------+------------------+---------------------+

To verify, the recipient parses the input into its components and then "decrypts" the RSA block using the sender's public key to recover the message digest. She then independently computes the message digest hash of the received message and compares the two. If they are the same, then the signature has been verified.

Before you go designing your own stuff, remember that others have already designed a secure format to pass encrypted or signed messages using RSA. It's called the "Cryptographic Message Syntax" (also referred to as "PKCS#7"). The CryptoSys PKI Toolkit provides functions to create and read CMS objects (the document uses the word "enveloped" to mean what we'd call "encrypted"). See CMS_MakeEnvData and CMS_MakeSigData.

Key Security Considerations

The primitives in this toolkit allow you to do a lot of low-level operations with RSA keys. The original design only permitted private keys to be stored as a file in encrypted format. In response to many requests from users, we've added various functions that allow you to import and save private keys in a variety of unencrypted formats, including XML and OpenSSL-compatible PEM formats.

Use these functions in your tests by all means, but if you are using this toolkit to make an application to be used by less-experienced end users, follow the following guidelines:

Do not give your users the ability to save an unencrypted private key, ever. Just say no.
Never, ever save production private keys to disk in unencrypted format. That includes the "internal" format, too. Remember that's never, even when testing (especially when testing).
Use the WIPE_Data function to wipe the internal private key string as soon as you've finished using it.
Ditto for passwords.
If you have to save secret data as an intermediate file, use the WIPE_File function to erase it immediately afterwards. Make sure this happens even if an error condition occurs.
Never print out the "internal" string representation of a production private key. (We know we do in our examples, but that's to demonstrate how it works.) Likewise the password.
Do not hard code private key strings or passwords, ever. (Again, do as we say, not as we do in our examples.)
If you need a private key on a server to be used repeatedly in internal format, force the administrator to enter the password each time the server starts. Set up a hierarchy of keys and certificates in case the server key gets compromised.
Enforce a policy so that users are forced to use strong passwords for the private key. The higher up the chain the longer the password needs to be. Do not compromise on this, even when the client complains. It's good practice for really important passwords (say for a master signing key) to be so long that they have to written down. Keep the piece of paper in a safe.
And build in a function that detects when the user has stuck a Post-It note on their monitor with the private key password on it.

References

[NIST80057] NIST Special Publication 800-57, Recommendation for Key Management - Part 1: General (Revised), National Institute of Standards and Technology, March, 2007. <pdf-link>

Contact

For more information or to comment on this page, please send us a message.

This page last updated 15 June 2020