Topic: Public key cryptography you can do yourself on a napkin. Single-digit prime numbers = PGP keys
Anonymous A started this discussion 2 years ago#111,172
To use public-key math to encrypt a message using small single-digit prime numbers, you will need to follow the following steps:
Select two small single-digit prime numbers, say p and q, such that p is not equal to q. For example, we can choose p = 3 and q = 7.
Calculate the product of p and q, denoted by N. In our example, N = 3 x 7 = 21.
Calculate Euler's totient function of N, denoted by φ(N). For two prime numbers, φ(N) = (p-1) x (q-1). In our example, φ(N) = (3-1) x (7-1) = 12.
Choose a small odd number e that is coprime with φ(N), i.e., gcd(e, φ(N)) = 1. In our example, we can choose e = 5, as gcd(5, 12) = 1.
Calculate the modular multiplicative inverse of e modulo φ(N), denoted as d, such that e x d ≡ 1 (mod φ(N)). In our example, we can calculate d as d = 5^-1 mod 12 = 5.
Publish the values N and e as the public key, and keep the value d as the private key.
To encrypt a message M, convert it into a number between 0 and N-1. In our example, we can represent the message "HELLO" as 8 5 12 12 15, using the ASCII code.
Encrypt each number separately using the formula C = M^e mod N. In our example, we can calculate the encrypted values as follows:
C1 = 8^5 mod 21 = 2
C2 = 5^5 mod 21 = 2
C3 = 12^5 mod 21 = 6
C4 = 12^5 mod 21 = 6
C5 = 15^5 mod 21 = 18
The encrypted message is the sequence of encrypted values, in our example, it is: 2 2 6 6 18.
To decrypt the encrypted message, use the private key value d and the formula M = C^d mod N. In our example, if we decrypt the encrypted message, we get the original message "HELLO".
This type of PGP is better suited to people that don't have access to a computer.