This article will explain how does public key encryption work. Public key systems underlay the security that you use every day to browse the web. The https (TLS) secure web links you use every day use public key cryptography to be able to exchange encrypted information.
From the book Essential Software Development Career + Technical Guide.
This article intends to show you a simplified example of how the keys are created and how encryption and decryption are done at a basic level.
Traditional symmetric encryption requires a shared key that both parties that need to communicate know. If, let’s say, we took a stupid simple cipher of adding 1 to everything, then the person on the receiving side would need to know to subtract 1. That means 1 is your shared secret.
To share that private secret, you needed to give the other person that number securely, either in person or via some secure, trusted communication channel that you know would not be intercepted.
Public key works differently. There is no shared secret, which means two people don’t need to meet and don’t initially need a secure communication channel to exchange a shared secret. For each user, there is a private key used to decrypt things encrypted with that user’s public key.
Imagine users A and B:
A freely gives public key and posts it on the Internet for anyone to use.
B freely gives public key and posts it on the Internet for anyone to use.
A wants to send a message to B.
A encrypts a message with B’s public key.
B decrypts the message with B’s private key.
B wants to send a message to A.
B encrypts a message with A’s public key.
A decrypts the message with A’s private key.
So, in this case, public keys can be posted for anyone to use, and the only person who can read messages encrypted with the public key is the person who holds the private key.
This has been an incredible leap for secure communications, allowing the setup of a secure way to communicate with anyone without the need to share a private secret.
Luckily, math came to the rescue to create this for us. It’s really not too complicated for a lot of folks to understand.
The process:
Step 1: Choose prime numbers p and q
Step 2: n = p * q
Step 3: z = (p-1) * (q-1)
Step 4: Pick a random number e where 1 < e < z and e has no common factors with z
Step 5: Find d where ((e*d)-1) is evenly divisible by z
Note: In my testing, I also needed to add ( and e!=d )
Public key is (n,e)
Private Key is (n,d)
M = Message to encrypt
Step 6: Encrypted Message (EM) = M^e mod n (uses public key values to encrypt)
Step 7: Decrypted Message = (EM) ^d mod n (uses private key values to decrypt)
Example code below shows the relatively basic math that underlies public key systems that form the foundation of web security.
WARNING: To simplify the code to make it easier to understand, less than optimal algorithms were chosen, so this won’t work for a large prime. Also, for secure encryption, additional things are done to make the encryption harder to crack. This sample is just to show the core logic principles that make public/private key encryption work. Do not actually use this code as is for any encryption.
//Not suitable for actual encryption. Use crypto random.
Random random = new Random();
// Step1
//pick two prime numbers (obviously MUCH bigger than these for
//real use. Small numbers used to focus on the code.)
int p = 229, q = 107;
//Step 2: n= number to use with modulo operator
int n = p * q;
//Step 3: compute one higher than the limit of e (z=72)
int z = (p - 1) * (q - 1);
// Step 4: 1 < e < z Find an e (pick a random number that
// matches the criteria. Also has no common factors with
// z - I used IsPrime to enforce this but it really
// only needs to avoid common factors - Don’t ever use this
// random number generator for real encryption
// (use a cryptographic random number generator)
int e = random.Next(2, z - 1);
while (!IsPrime(e)) //This IsPrime is too slow for large prime’s ok for tiny
e=random.Next(2, z - 1);
// Step 5: find a good d where (e*d)-1 % z=0 (evenly divisible by z)
// This is probably not the best way to find a d that works
// But a quick dirty algo that seemed to work
// (Too slow for large prime’s don’t use)
// Some writeups say d < z
int d;
for (d=1; d < z; d++)
{
if ((((e * d) - 1) % z) == 0 && e!=d)
break; //d is good
}
//visualize our key pairs
var publicKey = (n, e);
var privateKey = (n, d);
//We will encrypt the letter A which is 65
BigInteger messageToEncrypt = ‘A’;
//Step 6: Encrypt our message (umm well character in this case)
BigInteger encryptedMessage = BigInteger.ModPow(message
ToEncrypt, publicKey.e, publicKey.n);
//Step 7: Decrypt our message - result will be 65 ‘A’
BigInteger decryptedMessage = BigInteger.ModPow(encrypted
Message, privateKey.d, privateKey.n);
//IsPrime(n) is from Wikipedia (Primality Test—Wikipedia, n.d.) https://en.wikipedia.org/wiki/Primality_test
Thanks to this website (One Big Fluke › Simplest Explanation of the Math behind Public Key Cryptography, n.d.) ( https://www.onebigfluke.com/2013/11/public-key-crypto-math-explained.html) for explaining the math.
Don’t use this code anywhere near production. It was just a quick and dirty way to demonstrate at a low level the basic math/variables needed for public key. It doesn’t use cryptographic random number generation or other items.
Also note that with low prime numbers like shown here in testing, overlap and have issues with encrypting values in the message were higher than those components.
Here is a simplified example of using more realistic APIs to do the encryption and decryption without worrying about the underlying math: (Note does not do proper dispose handling or store the key securely, so don’t copy this code for actual use either, provided as a simplified demonstration. This portion was not included in the book)
using System;
using System.Security.Cryptography;
using System.Text;
namespace PublicKeyCryptographyExample
{
class Program
{
static void Main(string[] args)
{
// Generate a public/private key pair for User B
RSACryptoServiceProvider rsaB = new RSACryptoServiceProvider();
string publicKeyB = rsaB.ToXmlString(false); // Only public key
string privateKeyB = rsaB.ToXmlString(true); // Both public and private key
// User A gets the public key of User B and encrypts a message
byte[] message = Encoding.UTF8.GetBytes("A"); // Message containing only the letter 'A'
byte[] encryptedMessage = Encrypt(message, publicKeyB); // Encrypt the message using User B's public key
Console.WriteLine("User A encrypted the message: " + Convert.ToBase64String(encryptedMessage));
// User B gets the encrypted message and decrypts it using their private key
byte[] decryptedMessage = Decrypt(encryptedMessage, privateKeyB); // Decrypt the message using User B's private key
Console.WriteLine("User B decrypted the message: " + Encoding.UTF8.GetString(decryptedMessage));
}
// Encrypt a byte array using a public key
public static byte[] Encrypt(byte[] data, string publicKey)
{
RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();
rsa.FromXmlString(publicKey); // Load the public key
return rsa.Encrypt(data, false); // Encrypt the data
}
// Decrypt a byte array using a private key
public static byte[] Decrypt(byte[] data, string privateKey)
{
RSACryptoServiceProvider rsa = new RSACryptoServiceProvider();
rsa.FromXmlString(privateKey); // Load the private key
return rsa.Decrypt(data, false); // Decrypt the data
}
}
}
This should give you a simplified understanding of how does public key encryption work with the math, and an understanding of usage.
Reference:
Essential Software Development Career + Technical Guide (Check out the book on Amazon)
Checkout our home page here for even more info.
(c)opyright 2023 Appjungle.net LLC