## Introduction

In 1978, Ron Rivest, Adi Shamir, and Leonard Adleman developed an algorithm as a cryptographic algorithm, which was essentially to replace the less secure National Bureau of Standards (NBS) algorithm. Most importantly, RSA implements a public-key cryptosystem, as well as digital signatures or private key. Cryptosystem is way where a pair of key works together to data encrypt and decrypt.

## Background

It is based on the logic that it is easy to multiply large **prime** numbers, but factoring large numbers is very difficult. For example, it is easy to check that 31 and 37 multiply to 1147, but if you try to find the factor of 1147 then it will be horrible to calculate.

A computer can factor that number fairly quickly, but (although there are some tricks) it basically does it by trying most of the possible combinations. For any size number, the computer has to check something that is of the order of the size of the square-root of the number to be factored. In this case, that square-root is roughly 38000. Now it doesn’t take a computer long to try out 38000 possibilities, but what if the number to be factored is not ten digits, but rather 400 digits? The square-root of a number with 400 digits is a number with 200 digits. The lifetime of the universe is approximately 1018 seconds – an 18 digit number. Assuming a computer could test one million factorizations per second, in the lifetime of the universe it could check 1024 possibilities. But for a 400 digit product, there are 10200 possibilties. This means the computer would have to run for 10176 times the life of the universe to factor the large number. It is, however, not too hard to check to see if a number is prime—in other words to check to see that it cannot be factored. If it 4.

Now B knows enough to encode a message to Client.

Suppose, for this example, that the message is the number

M = 35. 5.

Server calculates the value of **C = Me (mod N)** = 357 (mod 943). 6. 357 = 64339296875 and 64339296875(mod 943) = 545. The number 545 is the encoding that server sends to client. 7. Now A wants to decode 545. To do so, he needs to find a number d such that ed = 1(mod (p − 1)(q − 1)), or in this case, such that 7d = 1(mod 880). A solution is d = 503, since 7 ∗ 503 = 3521 = 4(880) + 1 = 1(mod 880). 8. To find the decoding, A must calculate C d (mod N) = 545503(mod 943). This looks like it will be a horrible calculation, and at first it seems like it is, but notice that 503 = 256+128+64+32+16+4+2+1 (this is just the binary expansion of 503). So this means that 545503 = 545256+128+64+32+16+4+2+1 = 545256545128 · · · 5451 . But since we only care about the result (mod 943), we can calculate all the partial results in that modulus, and by repeated squaring of 545, we can get all the exponents that are powers of 2. For example, 5452 (mod 943) = 545 · 545 = 297025(mod 943) = 923. Then square again: 5454 (mod 943) = (5452 ) 2 (mod 943) = 923 · 923 = 851929(mod 943) = 400, and so on. We obtain the following table: 5451 (mod 943) = 545 5452 (mod 943) = 923 5454 (mod 943) = 400 5458 (mod 943) = 633 54516(mod 943) = 857 54532(mod 943) = 795 54564(mod 943) = 215 545128(mod 943) = 18 545256(mod 943) = 324 So the result we want is: 545503(mod 943) = 324 · 18 · 215 · 795 · 857 · 400 · 923 · 545(mod 943) = 35. Using this tedious (but simple for a computer) calculation, A can decode B’s message and obtain the original message N = 35.

## Using the code

The below code needs to add the System.Security.Cryptography; library. RSACryptoServiceProvider is .Net built function to encrypt RSA. You don’t need to worry about internal structure or algorithm to encrypt and decrypt. public RSACryptoServiceProvider rsa = new RSACryptoServiceProvider(); UTF8Encoding encoder = new UTF8Encoding(); //The RSAParameters can contain private and public key by using RSACryptoServiceProvider //class and method is ExportParameter. public RSAParameters privateKey; public RSAParameters publicKey; public Form1() { InitializeComponent(); } private void Form1_Load(object sender, EventArgs e) { this.GenerateKey(); } private void button1_Click(object sender, EventArgs e) { // Generated the private and public key. Public key will be distributed to //client to encrypt. var encryptedValue= this.Encrypt(encoder.GetBytes(txtPlainText.Text)); txt.Text = encoder.GetString(encryptedValue); RSADecrypt(encryptedValue); } public void GenerateKey() { rsa.PersistKeyInCsp = false; publicKey = rsa.ExportParameters(false); privateKey = rsa.ExportParameters(true); } public byte[] Encrypt(byte[] byteText) { try { byte[] encryptedData; //Create a new instance of RSACryptoServiceProvider. //Encrypt the passed byte array and specify OAEP padding. //OAEP padding is only available on Microsoft Windows XP or //later. encryptedData = rsa.Encrypt(byteText, RSAEncryptionPadding.Pkcs1); return encryptedData; } //Catch and display a CryptographicException //to the console. catch (CryptographicException e) { Console.WriteLine(e.Message); return null; } } public byte[] RSADecrypt(byte[] DataToDecrypt) { try { byte[] decryptedData; //Create a new instance of RSACryptoServiceProvider. //Import the RSA Key information. This needs //to include the private key information //Decrypt the passed byte array and specify OAEP padding. //OAEP padding is only available on Microsoft Windows XP or //later. decryptedData = rsa.Decrypt(DataToDecrypt,RSAEncryptionPadding.Pkcs1); txtDecryptedText.Text = encoder.GetString(decryptedData); return decryptedData; } //Catch and display a CryptographicException //to the console. catch (CryptographicException e) { Console.WriteLine(e.ToString()); return null; } }

## Points of Interest

Mainly for financial application use this kind of algorithm to protect data from network level. Eventually TLS 1.2 or secured socket layer do the same thing inside the network. But before sending or after receiving the data should be encrypted. In this case, someone steals the public key, he has nothing to do with encrypted data. Payment gateway or payment application vastly used this kind of algorithm.

## Reference

https://en.wikipedia.org/wiki/RSA_(cryptosystem)