13,042,819 members (87,117 online)
alternative version

#### Stats

73K views
41 bookmarked
Posted 15 Jul 2012

# RSA Library with Private Key Encryption in C#

, 15 Jul 2012
 Rate this:
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 = PlainTextE ( 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 = CipherTextD ( 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 its 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 the 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

```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.

```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.

```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.

```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.

```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 RFC's [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, the results 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 : This is the first public version.

## Share

 India
No Biography provided

## You may also be interested in...

 Pro

 First PrevNext
 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 ? XmenWK9-Dec-14 5:07 XmenWK 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 N10K17-Oct-13 2:09 N10K 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 Member 1006774521-May-13 5:09 Member 10067745 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
 Problem alexandrvictor8818-Feb-13 2:01 alexandrvictor88 18-Feb-13 2:01
 Re: Problem (Solved) Arpan Jati19-Feb-13 13:00 Arpan Jati 19-Feb-13 13:00
 Why Do we get same EXPONENT value! GAnil15-Jan-13 20:39 GAnil 15-Jan-13 20:39
 Re: Why Do we get same EXPONENT value! Arpan Jati27-Jan-13 6:05 Arpan Jati 27-Jan-13 6:05
 Re: Why Do we get same EXPONENT value! GAnil14-Feb-13 19:18 GAnil 14-Feb-13 19:18
 Re: Why Do we get same EXPONENT value! Arpan Jati19-Feb-13 13:01 Arpan Jati 19-Feb-13 13:01
 Last Visit: 31-Dec-99 18:00     Last Update: 20-Jul-17 18:45 Refresh 12 Next »