# Implementation of the RSA algorithm in the client-server architecture

### Emergence of need

This article is devoted to one of the problems that I encountered when developing my own project. The project has a client-server architecture, and is a business application. Almost the first question after the implementation of data transmission over the network and building the frame, there was a need for encryption of the transmitted data. The first possible algorithm (plans to support several) was chosen RSA encryption algorithm.

The article will consider options for implementing the RSA algorithm on a client-server architecture, and an example of such an implementation in a real project.

### RSA Algorithm Concept

I will not describe the features of this algorithm here, but will talk specifically about how it can be used in client-server architecture.
A small introduction ... Actually, RSA (letter abbreviation from the names Rivest-Shamir-Adleman) is a public-key cryptographic algorithm. This means that the system generates two different keys - public and secret.
• The public key is transmitted over an open (insecure) channel, and is used to encrypt data.
• The secret key is stored only by the owner, and is used to decrypt any data encrypted with the public key.
Thus, we can transfer the public key to anyone, and receive messages encrypted with this key, which we can decrypt (using the secret key).

This concept is presented in figure 1, pictured above.

As you can see, the key after being generated by the blue character is transmitted to the green character through an unprotected channel in the clear. Anyone can intercept him, but with his help you can only encrypt the message.

Therefore, the green character easily receives the public key and encrypts his message with this key.

After that, he transmits the encrypted message to the blue character, who decrypts it using the private key.

Within two people, the scheme is quite simple. However, if it is necessary to organize such a system on a client-server architecture, a number of additional issues arise, which we will consider below.

### Client - Server

So, for a start we will decide on keys. As you recall, the recipient’s public key is required to encrypt messages. Accordingly, the server needs the public key of the client, and the client needs the public key of the server. Therefore, before starting the data transfer, it is necessary to exchange keys. How this happens, we will consider in figure No. 2, which presents the process of exchanging keys.

1. The client opens a connection to the server and generates a bunch of keys (open-secret); then he sends the packet to the server, in which he transfers his public key to him;
2. The server receives the packet, reads and saves the client’s public key, generates its own keychain; after that, he sends the packet to the client, in which he transfers his public key to him;
3. The client receives the packet, reads and saves the public key of the server;

The exchange is completed in three stages. Now both the server and the client have the public key of the interlocutor "on the other end of the line." However, here you must immediately choose one of two decisions about how the server will generate keys for its clients:

1. The server generates one key for all clients;
2. The server generates a new key for each individual client;

I think each of you knows that the larger the key, the greater its practical utility. However, in the case of the RSA algorithm, key generation is not such a simple task, since it represents the main computational complexity. In addition, the algorithm is designed in such a way that the larger the key, the more data will need to be transmitted.

For example, when transmitting a message with a length of 5 bytes, and using a key length of 512 bits, the encrypted message will "weigh" 64kbytes. This is due to the fact that the maximum amount of data that can be encrypted with such a key is 64-11 = 53 kB (11 kB is used for bit shifts). If you need to encrypt more - we break into blocks of 53 kB. And if you take the key = 4096 bits, then the minimum block will be equal to 512 kbytes, despite the fact that we encrypt only 5 bytes.

Therefore, it is necessary to decide :

1. Generate one large key for all clients, which will create excess traffic, use more processor resources (encrypting a message with a key of 4096 bits is much more difficult than with 512), but eat less memory and hours killed for development;
2. Alternatively, generate a small key for each client, and ensure that its usage period does not exceed the maximum allowable (cracking a 512-bit key has long been a reality; the recommended length is at least 1024 bits);

Everyone can have their own views on that account, which option to prefer, and much here depends on the product being developed. However, in this project, it was decided to use the second option .

### Generating and sending a key to the server

Our project uses a three-tier architecture : client-server-database. The server is written in Java, the client is in C #. Below I will describe the implementation of encryption both on the server side and on the client side. Let's start with the user - the client.

So, the connection to the server was successful, and it is ready to receive packets. To do this, we create a key using the .NET class RSACryptoServiceProvider (C #):

1. private RSACryptoServiceProvider m_Rsa;
2. private RSAParameters m_ExternKey;
3. private RSAParameters m_InternKey;
4.
5. public CryptoRsa ()
6. {
7.     m_Rsa = new RSACryptoServiceProvider (512);
8.     m_InternKey = m_Rsa.ExportParameters (true);
9. }

In this listing, we see the constructor of the CryptoRsa class, which automatically generates a 512-bit key and exports the key parameters (true indicates that it is necessary to export not only the public, but also the secret key) into the m_InternKey variable.

Next, you need to save the public key in byte format and send it to the server. To do this, you need to understand a little what constitutes RSA keys. In short, they consist of the so-called public and secret exponents and a single module for both keys. Accordingly, a public key is an open exponent and a module, a private key is a private exponent and a module. More details can be found here in the chapter "Algorithm for creating public and private keys."

We write the open exponent to the output buffer (C #):

1. // Write the length of the exponent -> exponent -> module
2. buf.Write ((Byte) m_InternKey.Exponent.Length);
3. buf.Write (m_InternKey.Exponent);
4. buf.Write (m_InternKey.Modulus);

In this case, we need the length of the exponent in order to know exactly where the exponent ends and the module begins (when reading data on the server). After recording, send data to the server.

After the server has received the packet with the key, you need to pick up the key from the packet and save it. We look (Java):

1. // exponent length
2. int expLength = packet.readByte ();
3.
4. // Get exponent bytes
5. byte [] exponent = new byte [expLength];
6. System.arraycopy (packet.Bytes, packet.Offset, exponent, 0, expLength);
7.
8. // Get the bytes of the module
9. byte [] modulus = new byte [1 + packet.Bytes.length - (packet.Offset + expLength)];
10. System.arraycopy (packet.Bytes, packet.Offset + expLength, modulus, 1, modulus.length - 1);
11.
12. // Voodoo magic
13. modulus [0] = 0;
14.
15. // Save The Key
16. RSAPublicKeySpec rsaPubKeySpec = new RSAPublicKeySpec (new BigInteger (modulus), new BigInteger (exponent));
17. m_ExternPublicKey = (RSAPublicKey) KeyFactory.getInstance ("RSA"). generatePublic (rsaPubKeySpec);

I think there is no need to particularly comment on the code here, except for a strange line called by me “voodoo magic” :), where we set the first byte of the module to zero. And here's the thing: for reasons unknown to me, RSA implementation in Java requires that the key module always start from scratch. Perhaps this is due to having a module> 0, because when I tried to implement RSA in Java myself using large numbers (BigInteger), when the first byte is not equal to zero, a negative number is obtained. I leave this question to you, gentlemen of Khabravchane, I will be very happy if someone explains this feature.

Next is the key generation by the server. Consider the following piece of code (Java):

1. // Get and initialize the key generator
2. KeyPairGenerator keyGen = KeyPairGenerator.getInstance ("RSA");
3. keyGen.initialize (Config.CRYPTO_KEY_NUM_BITS);
4.
5. // Generate a bunch
6. m_KeyPair = keyGen.genKeyPair ();
7.
8. // Get the public and private keys
9. m_InternPublicKey = (RSAPublicKey) KeyFactory.getInstance ("RSA"). generatePublic (
10. new X509EncodedKeySpec (m_KeyPair.getPublic (). getEncoded ()));
11.
12. m_InternPrivateKey = (RSAPrivateKey) KeyFactory.getInstance ("RSA"). generatePrivate (
13. new PKCS8EncodedKeySpec (m_KeyPair.getPrivate (). getEncoded ()));

I think everything is clear here. Although, of course, if you go deeper, you definitely need to google on the subject of creatures such as X509 and PKCS8 (X509EncodedKeySpec and PKCS8EncodedKeySpec).

The next step is to send the keys to the server. This is done in almost the same way as in the case of the client (Java):

1. // Write the length of the exponent -> exponent -> module
2. bao.write (exponent.length & 0xff); // write as byte
3. bao.write (exponent);
4. bao.write (modulus);

And finally, we get the key on the client side, read and save it (C #):

1. Byte expLength = packet.ReadByte ();
2.
3. byte [] exponent = new byte [expLength];
4. Buffer.BlockCopy (packet.Bytes, packet.Offset, exponent, 0, expLength);
5.
6. byte [] modulus = new byte [packet.Bytes.Length - (packet.Offset + expLength) - 1];
7. Buffer.BlockCopy (packet.Bytes, packet.Offset + expLength + 1, modulus, 0, modulus.Length);
8.
9. m_ExternKey = new RSAParameters ();
10. m_ExternKey.Exponent = exponent;
11. m_ExternKey.Modulus = modulus;

That, in fact, is all. Now the client has the public key of the server in the variable m_ExternKey, and the server has the public key of the client in the variable m_ExternPublicKey. It remains only to organize the data transfer itself. This is made even simpler (C #):

1. // Import the key
2. m_Rsa.ImportParameters (m_ExternKey);
3.
4. // Encrypt and write encrypted data to the buffer
5. buffer.Write (m_Rsa.Encrypt (bytesToEncrypt, false));

In the case of the server, a bit more complicated (Java):

1. byte [] cipherText = null;
2. Cipher cipher = Cipher.getInstance ("RSA / ECB / PKCS1Padding");
3. cipher.init (Cipher.ENCRYPT_MODE, m_ExternPublicKey);
4. cipherText = cipher.doFinal (tempBytes);
5.
6. bao.write (cipherText);

The encrypted message is ready to be sent and decrypted by the recipient using the private key. The only thing you should not forget is that the maximum message size that can be encrypted is equal to the key size minus 11 bytes. Therefore, when encrypting, it is necessary to divide the data into blocks and encrypt them in turn. Here is an example in C #:

1. m_Rsa.ImportParameters (m_ExternKey);
2. ByteBuffer buffer = new ByteBuffer ();
3.
4. int dataLength = bytesToEncrypt.Length;
5. int maxLength = (m_Rsa.KeySize / 8) - 12;
6. int iterations = (int) Math.Ceiling ((float) bytesToEncrypt.Length / maxLength);
7.
8. for (Int32 i = 0; i <iterations; i ++)
9. {
10.     byte [] tempBytes = new byte [
11.         (dataLength - maxLength * i> maxLength)? maxLength:
12.             dataLength - maxLength * i];
13.
14.     Buffer.BlockCopy (bytesToEncrypt, maxLength * i, tempBytes, 0,
15.               tempBytes.Length);
16.
17.     buffer.PutEnd (m_Rsa.Encrypt (tempBytes, false));
18. }
19.
20. return buffer.Array;

You implement it on Java yourself, there are a couple of lines of changes :)

Of course, within the framework of this article I will not be able to cover the entire scope of the implementation of this functionality, but, I think, now you definitely have an idea of ​​how to implement a secure channel for your clients using RSA algorithm.