Category: General
Jul 24, 2021
Public Key Cryptography Explained
INTRODUCTION
I put together this article initially as a note to myself. I have published it, hoping it may be helpful to others. It may also result in those who understand the topic offering corrections.
It is written so that anyone who wishes to learn how this type of cryptography works can understand. It makes no assumptions as to the reader's starting knowledge. It describes some mathematical calculations understandable for those without a math background.
What is RSA?
(Rivest–Shamir–Adleman) is an algorithm used to encrypt and decrypt messages. It is an asymmetric cryptographic algorithm. Asymmetric means that there are two different keys. It is also called public-key cryptography because one of the keys is publicly available.
When multiple users communicate using encrypted messages, at least one user has a pair of keys. The key pair is intrinsically linked. When more people are involved in the communication and multiple messages are exchanged, each person would have a unique key pair. One of the keys is called a public key and can be known to anyone. The other key is a secret or private key and, as the name implies, is a secret to the key pair owner. It should never be shared.
A key pair is derived from a mathematical formula that begins with selecting two huge prime numbers (typically hundreds of digits each) and, after the application of some algorithms described later, is converted into a string of seemingly random characters.
Examples of Keys
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUp
wmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ5
1s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQABAoGAFijko56+qGyN8M0RVyaRAXz++xTqHBLh
3tx4VgMtrQ+WEgCjhoTwo23KMBAuJGSYnRmoBZM3lMfTKevIkAidPExvYCdm5dYq3XToLkkLv5L2
pIIVOFMDG+KESnAFV7l2c+cnzRMW0+b6f8mR1CJzZuxVLL6Q02fvLi55/mbSYxECQQDeAw6fiIQX
GukBI4eMZZt4nscy2o12KyYner3VpoeE+Np2q+Z3pvAMd/aNzQ/W9WaI+NRfcxUJrmfPwIGm63il
AkEAxCL5HQb2bQr4ByorcMWm/hEP2MZzROV73yF41hPsRC9m66KrheO9HPTJuo3/9s5p+sqGxOlF
L0NDt4SkosjgGwJAFklyR1uZ/wPJjj611cdBcztlPdqoxssQGnh85BzCj/u3WqBpE2vjvyyvyI5k
X6zk7S0ljKtt2jny2+00VsBerQJBAJGC1Mg5Oydo5NwD6BiROrPxGo2bpTbu/fhrT8ebHkTz2epl
U9VQQSQzY1oZMVX8i1m5WUTLPz2yLJIBQVdXqhMCQBGoiuSoSjafUhV7i1cEGpb88h5NBYZzWXGZ
37sJ5QsW+sJyoNde3xH8vdXhzU7eT82D6X/scw9RZz+/6rCJ4p0=
-----END RSA PRIVATE KEY-----
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0
FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/
3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB
-----END PUBLIC KEY-----
How do I use this in practice?
John wants to send a message to Sally
In the example where John and Sally are communicating, John sends a message to Sally.
John has Public KeyA (known by anyone) and Private KeyA (this is John's secret key)
Sally has Public Key B (known by anyone) and Private KeyB (this is Sally's secret key)
1. John asks Sally for (or looks up in a directory) a copy of her public key and then encrypts the message using that key.
2. Sally uses her private key to decrypt the message. A message encrypted with a public key can only be decrypted using the associated private key.
3. If Sally wishes to reply securely to John's message, Sally has to use John's public key, which Sally then uses to encrypt the reply. John then uses his private key to decrypt the message.
If the message is intercepted, the eavesdropper cannot decrypt the message without the private key associated with the public key used for the encryption.
Note that if you have the matching key pair, either key can be used to encrypt with the other used to decrypt, i.e., I can encrypt using a private key and decrypt using the public key. So why might we want to encrypt a message with a private key, given that the key to decrypt is publicly available? It is used to create digital signatures. If you don't care who sees the encrypted message but needs to prove it came from you, encrypt using your private key, and if it can be successfully decrypted using the public key, then this is proof it came from the holder of the private key.
The Math Behind Encryption and Decryption Methods
RSA encryption and decryption require the use of three numbers. We will refer to them as follows
e - Combined with N for the public key
d - Combined with N for the private key
N - used by both public and private keys
The calculation of the numbers e, d, and N above will be described later in the article.
Example of the Encryption Process
In the following example, we will use small numbers. In real-world applications, they are typically hundreds of digits in length.
We will use
e = 5
d= 11
N = 14
John sends a message to Sally
John asks Sally for (or looks up in a directory) a copy of her public key and then encrypts the message using that key. The message prior to encryption for this example is simply the letter B.
If we wish to encrypt a message that contains just the letter B, we first convert that into a digit. Since this is the 2nd letter of the alphabet we will use B=2
The Encryption Algorithm is quite simple, B**e(modN)
A mod (short for modulo) function is often referred to as clock arithmetic. It returns the remainder after dividing one number by another, e.g., 5 mod 2 would return 1, as 5 divided by 2 = 2 remainder 1.
Let’s now use the numbers described earlier for our examples
2**5(mod14) = 32(mod14) = 4.
So, the encrypted text B that is sent to Sally is the 4th letter of the alphabet = D
Example of the Decryption Process
Sally uses her private key to decode the message. This private key is the only way to decrypt the message, which is why it must always be kept a secret.
The Decryption algorithm is
Value of encrypted text**d(modN)
= 4**11(mod14) = 4194304(mod14) = 2.
The result 2 is the second letter of the alphabet so the decrypted text = B which you can see is the original text that was encrypted.
If you wish to check the math, copy and paste the example into Wolfram Alpha.
How are N, e, and d calculated?
Start with the calculation of N
Pick 2 prime numbers, p, and q. For this example p=2 and q = 7
N = p*q = 14
Then calculate (e) using the following process
Calculate the Totient of N. For prime numbers this is a simple calculation.
Totient N = (p-1)*(q-1) = 6 (the Totient is described at the end of this article)
2 e is a number that satisfies the following conditions
1<e<Totient(N), so it is one of the following 2, 3, 4, 5
e is coprime of N and Totient(N). The only number that satisfies both conditions is 5, therefore e = 5.
A coprime is where both numbers have no common factor other than 1. In other words, there is no whole number that you can divide them both by without any remainder. In our example:
N = 14 and Totient N = 6.
The factors of N are 1, 2, 7 and 14
The Factors of Totient N are 1, 2, 3 and 6
Given that according to our rules, Totient N is either 2, 3, 4 or 5
e cannot = 2 as it shares a factor with N
e cannot = 3 as it shares a factor with Totient N
e cannot = 4 as it shares the factor 2 with N
e must = 5 as it shares no common factors with N or Totient N
Then calculate d where
d*e(mod Totient(N)) = 1
Therefore d*5(mod6) =1
There are multiple numbers that satisfy this condition, i.e., what number when multiplied by 5 and divided by 6 = 1. You simply choose one of the possibilities.
For this example, I chose 55(mod6) = 1, so 5*d = 55, so d=11
Why is this system considered secure?
A matching key is required to decrypt a message. If d is a private key and if it is never disclosed it cannot be derived from the public key because:
1. Computing p and q from N when using very large prime numbers for p and q is currently considered mathematical infeasible. It would take hundreds of years to brute force hack the values of p and q with current capabilities.
2. Calculating (N) is impossible without knowing p and q
3. If (N) is not known then d cannot be calculated
So knowing one key does not allow you to calculate the second key.
Note - What is a Totient?
From <https://en.wikipedia.org/wiki/Euler%27s_totient_function>
In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor, gcd, (n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.
For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, because gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since for n = 1 the only integer in the range from 1 to n is 1 itself, and gcd(1, 1) = 1.
INTRODUCTION
I put together this article initially as a note to myself. I have published it, hoping it may be helpful to others. It may also result in those who understand the topic offering corrections.
It is written so that anyone who wishes to learn how this type of cryptography works can understand. It makes no assumptions as to the reader's starting knowledge. It describes some mathematical calculations understandable for those without a math background.
What is RSA?
(Rivest–Shamir–Adleman) is an algorithm used to encrypt and decrypt messages. It is an asymmetric cryptographic algorithm. Asymmetric means that there are two different keys. It is also called public-key cryptography because one of the keys is publicly available.
When multiple users communicate using encrypted messages, at least one user has a pair of keys. The key pair is intrinsically linked. When more people are involved in the communication and multiple messages are exchanged, each person would have a unique key pair. One of the keys is called a public key and can be known to anyone. The other key is a secret or private key and, as the name implies, is a secret to the key pair owner. It should never be shared.
A key pair is derived from a mathematical formula that begins with selecting two huge prime numbers (typically hundreds of digits each) and, after the application of some algorithms described later, is converted into a string of seemingly random characters.
Examples of Keys
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUp
wmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ5
1s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQABAoGAFijko56+qGyN8M0RVyaRAXz++xTqHBLh
3tx4VgMtrQ+WEgCjhoTwo23KMBAuJGSYnRmoBZM3lMfTKevIkAidPExvYCdm5dYq3XToLkkLv5L2
pIIVOFMDG+KESnAFV7l2c+cnzRMW0+b6f8mR1CJzZuxVLL6Q02fvLi55/mbSYxECQQDeAw6fiIQX
GukBI4eMZZt4nscy2o12KyYner3VpoeE+Np2q+Z3pvAMd/aNzQ/W9WaI+NRfcxUJrmfPwIGm63il
AkEAxCL5HQb2bQr4ByorcMWm/hEP2MZzROV73yF41hPsRC9m66KrheO9HPTJuo3/9s5p+sqGxOlF
L0NDt4SkosjgGwJAFklyR1uZ/wPJjj611cdBcztlPdqoxssQGnh85BzCj/u3WqBpE2vjvyyvyI5k
X6zk7S0ljKtt2jny2+00VsBerQJBAJGC1Mg5Oydo5NwD6BiROrPxGo2bpTbu/fhrT8ebHkTz2epl
U9VQQSQzY1oZMVX8i1m5WUTLPz2yLJIBQVdXqhMCQBGoiuSoSjafUhV7i1cEGpb88h5NBYZzWXGZ
37sJ5QsW+sJyoNde3xH8vdXhzU7eT82D6X/scw9RZz+/6rCJ4p0=
-----END RSA PRIVATE KEY-----
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0
FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/
3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB
-----END PUBLIC KEY-----
How do I use this in practice?
John wants to send a message to Sally
In the example where John and Sally are communicating, John sends a message to Sally.
John has Public KeyA (known by anyone) and Private KeyA (this is John's secret key)
Sally has Public Key B (known by anyone) and Private KeyB (this is Sally's secret key)
1. John asks Sally for (or looks up in a directory) a copy of her public key and then encrypts the message using that key.
2. Sally uses her private key to decrypt the message. A message encrypted with a public key can only be decrypted using the associated private key.
3. If Sally wishes to reply securely to John's message, Sally has to use John's public key, which Sally then uses to encrypt the reply. John then uses his private key to decrypt the message.
If the message is intercepted, the eavesdropper cannot decrypt the message without the private key associated with the public key used for the encryption.
Note that if you have the matching key pair, either key can be used to encrypt with the other used to decrypt, i.e., I can encrypt using a private key and decrypt using the public key. So why might we want to encrypt a message with a private key, given that the key to decrypt is publicly available? It is used to create digital signatures. If you don't care who sees the encrypted message but needs to prove it came from you, encrypt using your private key, and if it can be successfully decrypted using the public key, then this is proof it came from the holder of the private key.
The Math Behind Encryption and Decryption Methods
RSA encryption and decryption require the use of three numbers. We will refer to them as follows
e - Combined with N for the public key
d - Combined with N for the private key
N - used by both public and private keys
The calculation of the numbers e, d, and N above will be described later in the article.
Example of the Encryption Process
In the following example, we will use small numbers. In real-world applications, they are typically hundreds of digits in length.
We will use
e = 5
d= 11
N = 14
John sends a message to Sally
John asks Sally for (or looks up in a directory) a copy of her public key and then encrypts the message using that key. The message prior to encryption for this example is simply the letter B.
If we wish to encrypt a message that contains just the letter B, we first convert that into a digit. Since this is the 2nd letter of the alphabet we will use B=2
The Encryption Algorithm is quite simple, B**e(modN)
A mod (short for modulo) function is often referred to as clock arithmetic. It returns the remainder after dividing one number by another, e.g., 5 mod 2 would return 1, as 5 divided by 2 = 2 remainder 1.
Let’s now use the numbers described earlier for our examples
2**5(mod14) = 32(mod14) = 4.
So, the encrypted text B that is sent to Sally is the 4th letter of the alphabet = D
Example of the Decryption Process
Sally uses her private key to decode the message. This private key is the only way to decrypt the message, which is why it must always be kept a secret.
The Decryption algorithm is
Value of encrypted text**d(modN)
= 4**11(mod14) = 4194304(mod14) = 2.
The result 2 is the second letter of the alphabet so the decrypted text = B which you can see is the original text that was encrypted.
If you wish to check the math, copy and paste the example into Wolfram Alpha.
How are N, e, and d calculated?
Start with the calculation of N
Pick 2 prime numbers, p, and q. For this example p=2 and q = 7
N = p*q = 14
Then calculate (e) using the following process
Calculate the Totient of N. For prime numbers this is a simple calculation.
Totient N = (p-1)*(q-1) = 6 (the Totient is described at the end of this article)
2 e is a number that satisfies the following conditions
1<e<Totient(N), so it is one of the following 2, 3, 4, 5
e is coprime of N and Totient(N). The only number that satisfies both conditions is 5, therefore e = 5.
A coprime is where both numbers have no common factor other than 1. In other words, there is no whole number that you can divide them both by without any remainder. In our example:
N = 14 and Totient N = 6.
The factors of N are 1, 2, 7 and 14
The Factors of Totient N are 1, 2, 3 and 6
Given that according to our rules, Totient N is either 2, 3, 4 or 5
e cannot = 2 as it shares a factor with N
e cannot = 3 as it shares a factor with Totient N
e cannot = 4 as it shares the factor 2 with N
e must = 5 as it shares no common factors with N or Totient N
Then calculate d where
d*e(mod Totient(N)) = 1
Therefore d*5(mod6) =1
There are multiple numbers that satisfy this condition, i.e., what number when multiplied by 5 and divided by 6 = 1. You simply choose one of the possibilities.
For this example, I chose 55(mod6) = 1, so 5*d = 55, so d=11
Why is this system considered secure?
A matching key is required to decrypt a message. If d is a private key and if it is never disclosed it cannot be derived from the public key because:
1. Computing p and q from N when using very large prime numbers for p and q is currently considered mathematical infeasible. It would take hundreds of years to brute force hack the values of p and q with current capabilities.
2. Calculating (N) is impossible without knowing p and q
3. If (N) is not known then d cannot be calculated
So knowing one key does not allow you to calculate the second key.
Note - What is a Totient?
From <https://en.wikipedia.org/wiki/Euler%27s_totient_function>
In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor, gcd, (n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.
For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, because gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since for n = 1 the only integer in the range from 1 to n is 1 itself, and gcd(1, 1) = 1.
INTRODUCTION
I put together this article initially as a note to myself. I have published it, hoping it may be helpful to others. It may also result in those who understand the topic offering corrections.
It is written so that anyone who wishes to learn how this type of cryptography works can understand. It makes no assumptions as to the reader's starting knowledge. It describes some mathematical calculations understandable for those without a math background.
What is RSA?
(Rivest–Shamir–Adleman) is an algorithm used to encrypt and decrypt messages. It is an asymmetric cryptographic algorithm. Asymmetric means that there are two different keys. It is also called public-key cryptography because one of the keys is publicly available.
When multiple users communicate using encrypted messages, at least one user has a pair of keys. The key pair is intrinsically linked. When more people are involved in the communication and multiple messages are exchanged, each person would have a unique key pair. One of the keys is called a public key and can be known to anyone. The other key is a secret or private key and, as the name implies, is a secret to the key pair owner. It should never be shared.
A key pair is derived from a mathematical formula that begins with selecting two huge prime numbers (typically hundreds of digits each) and, after the application of some algorithms described later, is converted into a string of seemingly random characters.
Examples of Keys
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUp
wmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ5
1s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQABAoGAFijko56+qGyN8M0RVyaRAXz++xTqHBLh
3tx4VgMtrQ+WEgCjhoTwo23KMBAuJGSYnRmoBZM3lMfTKevIkAidPExvYCdm5dYq3XToLkkLv5L2
pIIVOFMDG+KESnAFV7l2c+cnzRMW0+b6f8mR1CJzZuxVLL6Q02fvLi55/mbSYxECQQDeAw6fiIQX
GukBI4eMZZt4nscy2o12KyYner3VpoeE+Np2q+Z3pvAMd/aNzQ/W9WaI+NRfcxUJrmfPwIGm63il
AkEAxCL5HQb2bQr4ByorcMWm/hEP2MZzROV73yF41hPsRC9m66KrheO9HPTJuo3/9s5p+sqGxOlF
L0NDt4SkosjgGwJAFklyR1uZ/wPJjj611cdBcztlPdqoxssQGnh85BzCj/u3WqBpE2vjvyyvyI5k
X6zk7S0ljKtt2jny2+00VsBerQJBAJGC1Mg5Oydo5NwD6BiROrPxGo2bpTbu/fhrT8ebHkTz2epl
U9VQQSQzY1oZMVX8i1m5WUTLPz2yLJIBQVdXqhMCQBGoiuSoSjafUhV7i1cEGpb88h5NBYZzWXGZ
37sJ5QsW+sJyoNde3xH8vdXhzU7eT82D6X/scw9RZz+/6rCJ4p0=
-----END RSA PRIVATE KEY-----
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0
FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/
3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB
-----END PUBLIC KEY-----
How do I use this in practice?
John wants to send a message to Sally
In the example where John and Sally are communicating, John sends a message to Sally.
John has Public KeyA (known by anyone) and Private KeyA (this is John's secret key)
Sally has Public Key B (known by anyone) and Private KeyB (this is Sally's secret key)
1. John asks Sally for (or looks up in a directory) a copy of her public key and then encrypts the message using that key.
2. Sally uses her private key to decrypt the message. A message encrypted with a public key can only be decrypted using the associated private key.
3. If Sally wishes to reply securely to John's message, Sally has to use John's public key, which Sally then uses to encrypt the reply. John then uses his private key to decrypt the message.
If the message is intercepted, the eavesdropper cannot decrypt the message without the private key associated with the public key used for the encryption.
Note that if you have the matching key pair, either key can be used to encrypt with the other used to decrypt, i.e., I can encrypt using a private key and decrypt using the public key. So why might we want to encrypt a message with a private key, given that the key to decrypt is publicly available? It is used to create digital signatures. If you don't care who sees the encrypted message but needs to prove it came from you, encrypt using your private key, and if it can be successfully decrypted using the public key, then this is proof it came from the holder of the private key.
The Math Behind Encryption and Decryption Methods
RSA encryption and decryption require the use of three numbers. We will refer to them as follows
e - Combined with N for the public key
d - Combined with N for the private key
N - used by both public and private keys
The calculation of the numbers e, d, and N above will be described later in the article.
Example of the Encryption Process
In the following example, we will use small numbers. In real-world applications, they are typically hundreds of digits in length.
We will use
e = 5
d= 11
N = 14
John sends a message to Sally
John asks Sally for (or looks up in a directory) a copy of her public key and then encrypts the message using that key. The message prior to encryption for this example is simply the letter B.
If we wish to encrypt a message that contains just the letter B, we first convert that into a digit. Since this is the 2nd letter of the alphabet we will use B=2
The Encryption Algorithm is quite simple, B**e(modN)
A mod (short for modulo) function is often referred to as clock arithmetic. It returns the remainder after dividing one number by another, e.g., 5 mod 2 would return 1, as 5 divided by 2 = 2 remainder 1.
Let’s now use the numbers described earlier for our examples
2**5(mod14) = 32(mod14) = 4.
So, the encrypted text B that is sent to Sally is the 4th letter of the alphabet = D
Example of the Decryption Process
Sally uses her private key to decode the message. This private key is the only way to decrypt the message, which is why it must always be kept a secret.
The Decryption algorithm is
Value of encrypted text**d(modN)
= 4**11(mod14) = 4194304(mod14) = 2.
The result 2 is the second letter of the alphabet so the decrypted text = B which you can see is the original text that was encrypted.
If you wish to check the math, copy and paste the example into Wolfram Alpha.
How are N, e, and d calculated?
Start with the calculation of N
Pick 2 prime numbers, p, and q. For this example p=2 and q = 7
N = p*q = 14
Then calculate (e) using the following process
Calculate the Totient of N. For prime numbers this is a simple calculation.
Totient N = (p-1)*(q-1) = 6 (the Totient is described at the end of this article)
2 e is a number that satisfies the following conditions
1<e<Totient(N), so it is one of the following 2, 3, 4, 5
e is coprime of N and Totient(N). The only number that satisfies both conditions is 5, therefore e = 5.
A coprime is where both numbers have no common factor other than 1. In other words, there is no whole number that you can divide them both by without any remainder. In our example:
N = 14 and Totient N = 6.
The factors of N are 1, 2, 7 and 14
The Factors of Totient N are 1, 2, 3 and 6
Given that according to our rules, Totient N is either 2, 3, 4 or 5
e cannot = 2 as it shares a factor with N
e cannot = 3 as it shares a factor with Totient N
e cannot = 4 as it shares the factor 2 with N
e must = 5 as it shares no common factors with N or Totient N
Then calculate d where
d*e(mod Totient(N)) = 1
Therefore d*5(mod6) =1
There are multiple numbers that satisfy this condition, i.e., what number when multiplied by 5 and divided by 6 = 1. You simply choose one of the possibilities.
For this example, I chose 55(mod6) = 1, so 5*d = 55, so d=11
Why is this system considered secure?
A matching key is required to decrypt a message. If d is a private key and if it is never disclosed it cannot be derived from the public key because:
1. Computing p and q from N when using very large prime numbers for p and q is currently considered mathematical infeasible. It would take hundreds of years to brute force hack the values of p and q with current capabilities.
2. Calculating (N) is impossible without knowing p and q
3. If (N) is not known then d cannot be calculated
So knowing one key does not allow you to calculate the second key.
Note - What is a Totient?
From <https://en.wikipedia.org/wiki/Euler%27s_totient_function>
In number theory, Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor, gcd, (n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.
For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, because gcd(9, 3) = gcd(9, 6) = 3 and gcd(9, 9) = 9. Therefore, φ(9) = 6. As another example, φ(1) = 1 since for n = 1 the only integer in the range from 1 to n is 1 itself, and gcd(1, 1) = 1.
Jan 1, 1970
Why Every Business Needs a Generative AI Policy—Even If You're Not Using AI Yet
Generative artificial intelligence (AI) has emerged as a transformative force across industries. While some businesses are quick to adopt AI solutions, others may believe that if they're not actively using AI, they don't need to worry about it. However, even if you have no formal plans to integrate AI into your operations, having a generative AI policy is essential. Here's why.
Jan 1, 1970
Navigating the Consulting Maze: Best Practices for Hiring the Right Expert
Hiring a consultant can be a game-changer, bringing fresh perspectives and specialized expertise to your business. However, navigating the consulting landscape can be daunting. This guide provides essential steps to ensure a successful engagement:
Jan 1, 1970
The Consultant Conundrum: Why Finding the Right Fit Feels Like Searching for a Unicorn
Hiring a business consultant can feel like navigating a minefield of buzzwords, As a business owner or manager seeking external expertise, you face a daunting task – sifting through a sea of potential candidates to find the elusive unicorn: a consultant who genuinely understands your needs, delivers tangible results, and doesn't break the bank.
Jan 1, 1970
Why Every Business Needs a Generative AI Policy—Even If You're Not Using AI Yet
Generative artificial intelligence (AI) has emerged as a transformative force across industries. While some businesses are quick to adopt AI solutions, others may believe that if they're not actively using AI, they don't need to worry about it. However, even if you have no formal plans to integrate AI into your operations, having a generative AI policy is essential. Here's why.
Jan 1, 1970
Navigating the Consulting Maze: Best Practices for Hiring the Right Expert
Hiring a consultant can be a game-changer, bringing fresh perspectives and specialized expertise to your business. However, navigating the consulting landscape can be daunting. This guide provides essential steps to ensure a successful engagement:
Jan 1, 1970
Why Every Business Needs a Generative AI Policy—Even If You're Not Using AI Yet
Generative artificial intelligence (AI) has emerged as a transformative force across industries. While some businesses are quick to adopt AI solutions, others may believe that if they're not actively using AI, they don't need to worry about it. However, even if you have no formal plans to integrate AI into your operations, having a generative AI policy is essential. Here's why.
NeWTHISTle Consulting
DELIVERING CLARITY FROM COMPLEXITY
Copyright © 2024 NewThistle Consulting LLC. All Rights Reserved
NeWTHISTle Consulting
DELIVERING CLARITY FROM COMPLEXITY
Copyright © 2024 NewThistle Consulting LLC. All Rights Reserved
NeWTHISTle Consulting
DELIVERING CLARITY FROM COMPLEXITY
Copyright © 2024 NewThistle Consulting LLC. All Rights Reserved