15,746,110 members
Articles / Security / Cryptography
Article
Posted 15 Jul 2012

153.6K views
53 bookmarked

RSA Library with Private Key Encryption in C#

Rate me:
RSA encryption library with full OAEP padding and private key encryption support

Introduction

RSA is one of the most important Public key cryptographic algorithms which is keeping the web alive. From secure transactions, secure mail to authentication and certificates, its use is universal.

The basic design of RSA is very simple and elegant and uses simple mathematical operations, yet it is very strong. If used properly, it is nearly impossible to break, given the mathematical complexity of the factoring problem.

The .NET Framework provides native support for RSA and it is pretty useful for most of the purposes. But, for certain cases like some signature schemes, we may require to perform 'private key encryption', which is not natively supported. So, for a project, I had to implement the RSA encryption and decryption from scratch. And, as without proper padding this scheme is vulnerable to attacks, I have also implemented OAEP and PKCS v1.5 padding schemes. This library (RSAx) is fully compatible with the .NET Framework's implementation of RSA.

The Features of the Library

• RSA Encryption and Decryption
• Private Key Encryption Support
• CRT-RSA for fast private key decryption
• Fully Compatible with .NET Cryptography Library
• Uses .NET BigInteger Library

Background

RSA being a public key crypto-system has two keys, the Public key and the Private key. The Encryption is done using one and the decryption is done using the other. Normally, the encryption is done using the Public key and the decryption is done using the Private key. The RSA modulus (explained below) length is called the key length of the cipher. The currently largest factored prime number had 768 bit. As the security of RSA depends on the factoring problem, using a modulus of 1024 bits is a bare minimum. It is recommended to use at least 2048 bits for good security. 4096 bit is pretty much unbreakable, anything beyond 4096 bits is over the top and would also be painfully slow.

Key Generation

1. Choose two large random prime numbers P and Q of similar length.
2. Compute N = P x Q. N is the modulus for both the Public and Private keys.
3. PSI = (P-1)(Q-1) , PSI is also called the Euler's totient function.
4. Choose an integer E, such that 1 < E < PSI, making sure that E and PSI are co-prime. E is the Public key exponent.
5. Calculate D = E-1 ( mod PSI ), normally using Extended Euclidean algorithm. D is the Private key exponent.

Encryption

1. Convert the data bytes to be encrypted, to a large integer called `PlainText`.
2. `CipherText = PlainText<sup>E</sup> ( mod N )`
3. Convert the integer, `CipherText` to a byte array, which is the result of the encryption operation.

Decryption

1. Convert encrypted data bytes to a large integer called `CipherText`.
2. `PlainText = CipherText<sup>D </sup>( mod N )`
3. Convert the integer, `PlainText` to a byte array, which is the result of the decryption operation.

Other Considerations

1. As its clear that exponents are very large, as a result, the large integers will easily overflow the normal 32 bit '`int`' and 64 bit '`long`'. To overcome this problem, we require to use a `BigInteger` library which can handle arbitrarily large numbers. In this case, I used the `BigInteger` library provided with the .NET Framework (`System.Numerics.BigInteger`).
2. The conversion from Byte array to integer and vice-versa are done in a specific format and we have to follow Big-Endian format, I have provided utility functions for conversions via `I2OSP()`, and `OS2IP()`.

The most critical part of the RSA encryption is the padding scheme. A padding scheme is normally used to increase the length of the plain-text in such a way, that a symmetric algorithm can use it. But, even though the RSA can work without a padding scheme, it is critical for the security of the data, as without proper padding, the cipher-text becomes vulnerable to many different attacks. The padding schemes also brings a randomness to the encrypted data. Every time the data is encrypted, the cipher-text is different, but after decryption, the plain-text remains the same.

There are two major padding schemes in general use, the PKCS and OAEP (Optimal Asymmetric Encryption Padding). PKCS is very simple and is still widely used being an older standard, but, is vulnerable to some newer attacks. OAEP was designed by Bellare and Rogaway to prevent these attacks and is currently recommended for use. But, OAEP is a little complex to implement. I will try to explain the OAEP padding scheme in some detail.

```                    +----------+---------+-------+
DB = |  pHash   |    PS   |   M   |
+----------+---------+-------+
|
+----------+              V
|   Seed   |--> MGF ---> XOR
+----------+              |
|                   |
+--+     V                   |
|00|    XOR <----- MGF <-----|
+--+     |                   |
|      |                   |
V      V                   V
+--+----------+----------------------------+
+--+----------+----------------------------+
```

Keywords

• `DB` - Data block to be encrypted, consists of pHash, PS and M.
• `pHash` - Hash of a predefined parameter list in the form of a byte array. It is used to make sure that the parameters at the encryption side and decryption side are the same, but, in most implementations, it's ignored and is optional. In that case, the Hash of an empty byte array is used instead.
• `PS` - A string of '0's followed by a 1. Used to fill the unused space in case, the message is shorter than the maximum allowed message length.
• `M` - Actual message to be encrypted.
• `Seed` - A random array of bytes, the length being equal to the length of hash function being used.
• `MGF` - Mask Generation Function, it is used to generate a variable length hash from a given input random input.
• `XOR` - Bit-wise Ex-OR operation.
• `maskedSeed` - The masked seed, which is part of the padded text. It is later (while decoding) used to get the Seed in conjunction with the MGF output of the `maskedDB`.
• `maskedDB` - The masked Data Block. It is later (while decoding) used to feed the MGF function which is used to obtain the Seed. It is also used to obtain the DB, by using the MGF output of the Seed.

Encoding Prelims

Before encoding, the Hash and the parameter array has to be fixed. For most purposes, the parameter `string` is an empty byte array. Normally, three different types of hashes are defined by the standard. SHA1, SHA256 and SHA512. SHA1 is default hashing algorithm. Its important that the parameter array and hash algorithm remains same during decoding, otherwise the decoding should fail.

Consider:

• `hLen` = Length of hash function output in bytes
• `k` = Length of Modulus in octets
• `PS_Len` = k - MessageLength - 2 * hLen - 2

OAEP Encoding

1. Calculate `pHash` = HASH(`Parameter<code>_`Array).
2. Create an array `PS` filled with '0' of length `PS_Len` .
3. Create `DB` = `pHash` || `PS` || 0x01 || `M` , || means append operation.
4. Generate a random octet string `Seed` of length `hLen`.
5. Expand the `Seed` using the MGF (explained later) function using the `Seed` as the input randomness and e output length of (`k` - `hLen` - 1) to get `dbMask`.
6. `maskedDB` = `DB` XOR `dbMask`
7. `seedMask` = MGF(`maskedDB`, `hLen`)
8. `maskedSeed` = `Seed` XOR `seedMask`.
9. `EncodedMessage` = 0x00 || `maskedSeed` || `maskedDB`.

That's all. The encoded message is simply encrypted using RSA.

OAEP Decoding

The decoding process is just the opposite of the encoding. Because, the length of the `maskedSeed` is known, we can easily separate the `maskedSeed` and `maskedDB`.

`seedMask` is generated from `maskedDB` using MGF, the generated `seedMask` is XORed with the `maskedSeed` to get the `Seed`.

The `Seed` is expanded using MGF to get `dbMask`.

`dbMask` and `maskedDB` are XORed together to get the DB.

We can easily obtain `pHash` and `M` from `DB`, because the length of `pHash` is known and the `M` starts after a sequence of '`0`'s followed by a `1`.

If `pHash` matches with the Hash of the parameter array during decryption, the `M` is returned as the result. Otherwise, the process fails.

It is important that the decoding algorithm does not allow the user to know the exact nature of the error, otherwise some attacks can be mounted.

The whole point of the OAEP scheme is to make sure that even 1 bit error in decryption renders the complete packet worthless. This is made sure by the hashes, as even a single bit change causes a complete change in the output bits.

MGF Function

Inputs

1. `Z` = Initial pseudo-random seed
2. `L` = Required length of output

Algorithm

C#
```for(int loop = 0 ; loop <= Loops ; loop++  )
{
X = Z || (loop in octets array of size 4, BigEndian)
MgfOut += HASH (X);
}
```

Return first `L` octets from `MgfOut`

Screenshots

Screenshot 1: Main Window

Showing a test Application for the RSAx library. Any combination of encryption and decryption is allowed, using both Public and Private keys. I have tested the library with keys up to 8192 bits in length. Make sure that different keys (Public and Private) is used for different (Encryption and Decryption) operations, otherwise the decryption will not work properly. While using OAEP, make sure to use the same Hash Algorithm in case of a single Encryption and Decryption. Make sure to Perform File->'Generate Key Pair' after changing the modulus size, for the program to work properly.

Screenshot 2: Test and Performance Window

I've implemented a basic test bench to verify the functioning of the library. It simply encrypts and decrypts random data and verifies the outcome with the expected result. It uses the settings from the previous tab.

Using the Code

Using the library is pretty straightforward.

C#
```string PlainText = "Encrypt Me";
string KeyInfo = ".....";
RSAx rsa = new RSAx(KeyInfo, 1024);
byte[] CTX = rsax.Encrypt(Encoding.UTF8.GetBytes(PlainText), true);
string CipherText = Convert.ToBase64String(CTX);

byte[] ETX = Convert.FromBase64String(CipherText);
byte[] PTX = rsax.Decrypt(ETX, true);
string DecryptedString = Encoding.UTF8.GetString(PTX);

// PlainText and DecryptedString should be equal.
```

The RSAx class can be created from an XML string similar to the native .NET counterpart. It can also be created by using a `RSAxParameters` class which allows to manually specify the public and the private key parts.

C#
```byte [] Modulus = ......
byte [] E = ......
byte [] D = .......
RSAxParameters rsaxParams = new RSAxParameters(Modulus, E, D, 1024);
RSAx rsax = new RSAx(rsaxParams);
// Use it normally
```

It can also be created from a `System.Security.Cryptography.RSAParameters` structure.

C#
```RSA rs = new RSACryptoServiceProvider(1024);
RSAParameters rsa_params =  rs.ExportParameters(true);
RSAxParameters rsax_params = new RSAxParameters(rsa_params, 1024);
RSAx rsax = new RSAx(rsax_params);
// Use rsax normally
```

Private key encryption and Public key decryption can be done as follows:

C#
```string PlainText = "Encrypt Me";
string KeyInfo = ".....";
RSAx rsa = new RSAx(KeyInfo, 1024);
// Private key encryption
byte[] CTX = rsax.Encrypt(Encoding.UTF8.GetBytes(PlainText), true, true);
// Public key decryption
byte[] PTX = rsax.Decrypt(CTX, false, true);
string DecryptedString = Encoding.UTF8.GetString(PTX);
```

Points of Interest

Writing the code was pretty straightforward. One interesting thing I found out was that there's a `GetNonZeroBytes()` function provided in the `<code>System.Security.Cryptography.`RNGCryptoServiceProvider class, pretty neat! I was just wondering about the internal implementation; if the resultant byte array contains of all non-zero bytes, won't there be some bias in the randomness?

Another thing I realized is that sometimes the RFCs [http://tools.ietf.org/html/rfc3447] are the only source of information about some protocol or algorithm and we have to keep reading it again and again until we understand the whole thing in its entirety.

Sometimes, after the last step of CRT-RSA, the result in the `BigInteger` was coming negative. And, this negative result plays havoc on the decrypted result. To fix this, I applied a simple hack. Whenever the result is negative, simply add the Modulus N to the result, in order to bring the result back to positive. This is trivial, but it fixed the problem completely.

History

• Version 1.0: First public version

Written By
India
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

 First PrevNext
 there is a bug line 388 if (DecodedDataIndex < (EM.Length - 1)) skyyear4-Aug-22 19:51 skyyear 4-Aug-22 19:51
 Re: there is a bug line 388 if (DecodedDataIndex < (EM.Length - 1)) OriginalGriff4-Aug-22 19:52 OriginalGriff 4-Aug-22 19:52
 My vote of 5 1514199837-Aug-20 16:49 151419983 7-Aug-20 16:49
 I want to do RSA to LSB steganography project for undergraduate project . Sasubcom1-Jun-20 17:57 Sasubcom 1-Jun-20 17:57
 Decrpytion is not working properly? Member 1315781427-Jan-19 20:18 Member 13157814 27-Jan-19 20:18
 Having problem with the encryption Lukhipolito6-Nov-18 2:59 Lukhipolito 6-Nov-18 2:59
 Encrypt long message d.barile28-Nov-15 4:30 d.barile 28-Nov-15 4:30
 Private Key Encrypt and Public key Decrypt calvin5602239-Dec-14 20:40 calvin560223 9-Dec-14 20:40
 Support for framework 2.0 ? Xmen Real 9-Dec-14 5:07 Xmen Real 9-Dec-14 5:07
 Thank you! Member 1084362225-May-14 21:34 Member 10843622 25-May-14 21:34
 Exception: Exception while decoding: OAEP Decode Error Member 835820110-Jan-14 5:54 Member 8358201 10-Jan-14 5:54
 Re: Exception: Exception while decoding: OAEP Decode Error Arpan Jati9-Apr-14 5:22 Arpan Jati 9-Apr-14 5:22
 Decryption not working kurle.nitin17-Oct-13 2:09 kurle.nitin 17-Oct-13 2:09
 Re: Decryption not working Arpan Jati18-Oct-13 4:24 Arpan Jati 18-Oct-13 4:24
 Can i decrypt using the public key only (without exposing the private key) rbg723-Jul-13 0:15 rbg7 23-Jul-13 0:15
 Re: Can i decrypt using the public key only (without exposing the private key) Arpan Jati26-Jul-13 7:09 Arpan Jati 26-Jul-13 7:09
 Re: Can i decrypt using the public key only (without exposing the private key) scefiro210-Oct-13 7:05 scefiro2 10-Oct-13 7:05
 Re: Can i decrypt using the public key only (without exposing the private key) Arpan Jati18-Oct-13 4:39 Arpan Jati 18-Oct-13 4:39
 Problem with RSA Encryption without padding Xatigid21-May-13 5:09 Xatigid 21-May-13 5:09
 Great job, buddy sprants17-May-13 3:23 sprants 17-May-13 3:23
 Re: Great job, buddy Arpan Jati18-Oct-13 4:15 Arpan Jati 18-Oct-13 4:15
 My vote of 5 Paulo Zemek30-Mar-13 7:13 Paulo Zemek 30-Mar-13 7:13
 Re: My vote of 5 Arpan Jati26-Jul-13 7:12 Arpan Jati 26-Jul-13 7:12
 Last Visit: 31-Dec-99 18:00     Last Update: 29-Sep-23 7:44 Refresh 12 Next ᐅ