Implementing the RSA algorithm in the client-server architecture

Emergence of need

This article is devoted to one of the problems that I encountered while 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 the construction of the framework, it became necessary to encrypt the transmitted data. The first possible algorithm (planning support for several) was chosen as the RSA encryption algorithm.

The article will discuss the 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 here the features of this algorithm, but I will tell you exactly how it can be used in the client-server architecture.
A small introduction ... Actually, RSA (a literal abbreviation of the surnames 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 (unprotected) channel, and is used to encrypt data.
• The secret key is stored only with 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 only we can decrypt (using the private key).



This concept is presented in Figure 1, shown above.

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

Therefore, the green character easily obtains the public key and encrypts its message with this key.

After that, he sends an encrypted message to the blue character , which decrypts using the private key.

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

Client - server

So, for a start we will define keys. As you remember, the recipient’s public key is required to encrypt messages. Accordingly, the server requires 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 consider the figure number 2, which presents the process of key exchange.



1. The client opens a connection to the server and generates a keychain (public-secret); then it sends the packet to the server , in which it sends it its public key;
2. The server accepts the packet, reads and stores the public key of the client , generates its own keychain; after that, it sends the packet to the client , in which it sends it its public key;
3. The client accepts the packet, reads and stores 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 "at the other end of the line". However, you immediately need to choose one of two solutions 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 every one of you knows that the bigger 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 basic 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 sending a message with a length of 5 bytes, and using a key with a length of 512 bits, the encrypted message will “weigh” 64 kbytes. 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 divide them into blocks of 53 KB each. And if you take the key = 4096 bits, then the minimum block will be equal to 512K bytes, despite the fact that we encrypt only 5 bytes.


Therefore, it is necessary to solve :

1. Generate one big key for all clients that will generate extra traffic, use more processor resources (encrypting a message with a key of 4096 bits is much more difficult than out of 512), but eating less memory and hours killed for development;
2. Alternatively, generate a small key for each client and ensure that the period of its use does not exceed the maximum allowable (breaking a key of 512 bits in length has long become a reality; the recommended length is at least 1024 bits);

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

Generating and sending the key to the server

Our project uses a three-tier architecture : client-server-database. The server is written in Java, the client - 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 - client.

So, the connection to the server was successful, and it is ready to accept 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 ;
5. public CryptoRsa ( )
6. {
7. m_Rsa = new RSACryptoServiceProvider ( 512 ) ;
8. m_InternKey = m_Rsa. ExportParameters ( true ) ;
9. }

In this listing, we see the CryptoRsa class constructor , which automatically generates a key with a length of 512 bits and exports key parameters (true indicates that it is necessary to export not only the public but also the secret key) to 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 RSA keys consist of. In short, they consist of so-called open and secret exhibitors and a single module for both keys. Accordingly, the public key is a public exponent and a module, the private key is a private exponent and a module. More details can be found here in the chapter "The algorithm for creating public and secret keys."

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, the length of the exponent is needed in order to know exactly where the exponent ends and the module begins (when reading data on the server). After recording, send the data to the server.

After the server has received a packet with a 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 ( ) ;
4. // Get the exponent bytes
5. byte [ ] exponent = new byte [ expLength ] ;
6. System . arraycopy ( packet. Bytes , packet. Offset , exponent, 0 , expLength ) ;
8. // Get the module bytes
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 ) ;
12. // Voodoo Magic
13. modulus [ 0 ] = 0 ;
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 that there is no need to comment on the code, except for a strange line, which I called "voodoo magic" :), where we set the first byte of the module to zero. But the point is this - for reasons unknown to me, the RSA implementation in Java requires that the key module always start from scratch. Perhaps this is due to having a module> 0, since when I tried to implement RSA in Java myself using large numbers (BigInteger), when the first byte was not equal to zero, it turned out to be a negative number. I leave this question to you, gentlemen Habravchane, I will be very happy if someone explains this feature.

Next comes 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 ) ;
5. // Generate a bundle
6. m_KeyPair = keyGen. genKeyPair ( ) ;
8. // Get public and private keys
9. m_InternPublicKey = ( RSAPublicKey ) KeyFactory . getInstance ( "RSA" ) . generatePublic (
10. new X509EncodedKeySpec ( m_KeyPair. getPublic ( ) . getEncoded ( ) ) ) ;
12. m_InternPrivateKey = ( RSAPrivateKey ) KeyFactory . getInstance ( "RSA" ) . generatePrivate (
13. new PKCS8EncodedKeySpec ( m_KeyPair. getPrivate ( ) . getEncoded ( ) ) ) ;

I think everything is clear. 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 a 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 it and save it (C #):

1. Byte expLength = packet. ReadByte ( ) ;
3. byte [ ] exponent = new byte [ expLength ] ;
4. Buffer BlockCopy ( packet. Bytes , packet. Offset , exponent, 0 , expLength ) ;
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 ) ;
9. m_ExternKey = new RSAParameters ( ) ;
10. m_ExternKey. Exponent = exponent ;
11. m_ExternKey. Modulus = modulus ;

That's all. The client now has the server's public key in the m_ExternKey variable, and the server has the client's public key in the m_ExternPublicKey variable. It remains only to organize the transfer of data. It becomes even simpler (C #):

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

In the case of the server a little 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 ) ;
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 one by one. Here is an example in C #:

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

In Java, implement it yourself, there are changes - a couple of lines :)

Of course, within the framework of this article I will not be able to cover the entire volume 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 the RSA algorithm.