RSA is a public/private key security method invented by Ronald Rivest, Adi Shamir, and Leonard Adleman in the 1970's.
RSA works by creating a private and public key pair. The public key can be shared with anyone. The private key resides on the target system where the key was generated. This could be a server. A secret message is created using the public key using an algorithm and then sent to the server or recipient. Only the private key can decrypt the message.
The private/public key pair is created by generating 2 very large prime numbers. From these prime numbers, a private key and a public key is created.
The prime numbers are used to create 3 values E, D and N, that represent the public and private key
The private key consisting of an D and an N value
The public key consisting of a E and an N value
While RSA-2048 uses very large prime numbers, for the purposes of showing an example, we shall use small prime numbers, such as 7 and 11.
P1 = 7, P2 = 11
N = P1 * P2
N = 7 * 11 = 77
A coprime value is calculated next
CP = (P1-1) * (P2-1)
CP = (7-1) * (11-1) = 6 * 10 = 60
A number, E, will be chosen between 1 and CP (60). In this example, E = 7
Next we apply the formula (D * E) % N. We now need to find a D value that makes the following statement true.
(D * E) % CP ---> (D * 7) % 60 = 1
When we iterate using various values of D to satify the equation (D * 7) % 60 = 1 , we will find that when D = 43, the modulus equals 1.
The private key is (D, N) = (43, 77)
The public key is (E, N) = (7, 77)
How to Encrypt a message?
The message must be between 0 and N (77). For example, lets send the secret of the universe (Douglas Adams reference), "42"
The formula to encrypt a message is..
EMSG = (M ^ E) % N ---> (42 ^ 7) % 77 ---> 230539333248 % 77 = 70
For Decryption, the formula uses the private key and the following formula
(EMSG ^ D) % N ---> (70 ^ 43) % 77 ---> 21838143759917965991093122527538323430000000
000000000000000000000000000000000000 % 77 = 42
By using 2 prime numbers and calculating the co-prime value and selecting an E value and calculation the D value, then every M (Message) value between 0 and N will have a unique EMSG (Encrypted Message) when using the formula EMSG = (M ^ E) % N
The Decryption formula is Original Message = (EMSG ^ D) % N
Likewise, every value of EMSG will have a unique decrypted message for every unique M (Message) value
| Message | Encryption | Decryption |
|---|---|---|
| 0 | (0^7)%77)=0 | (0^43)%77)=0 |
| 1 | (1^7)%77)=1 | (1^43)%77)=1 |
| 2 | (2^7)%77)=51 | (51^43)%77)=2 |
| 3 | (3^7)%77)=31 | (31^43)%77)=3 |
| 4 | (4^7)%77)=60 | (60^43)%77)=4 |
| 5 | (5^7)%77)=47 | (47^43)%77)=5 |
| 6 | (6^7)%77)=41 | (41^43)%77)=6 |
| 7 | (7^7)%77)=28 | (28^43)%77)=7 |
| 8 | (8^7)%77)=57 | (57^43)%77)=8 |
| 9 | (9^7)%77)=37 | (37^43)%77)=9 |
| 10 | (10^7)%77)=10 | (10^43)%77)=10 |
| 11 | (11^7)%77)=11 | (11^43)%77)=11 |
| 12 | (12^7)%77)=12 | (12^43)%77)=12 |
| 13 | (13^7)%77)=62 | (62^43)%77)=13 |
| 14 | (14^7)%77)=42 | (42^43)%77)=14 |
| 15 | (15^7)%77)=71 | (71^43)%77)=15 |
| 16 | (16^7)%77)=58 | (58^43)%77)=16 |
| 17 | (17^7)%77)=52 | (52^43)%77)=17 |
| 18 | (18^7)%77)=39 | (39^43)%77)=18 |
| 19 | (19^7)%77)=68 | (68^43)%77)=19 |
| 20 | (20^7)%77)=48 | (48^43)%77)=20 |
| 21 | (21^7)%77)=21 | (21^43)%77)=21 |
| 22 | (22^7)%77)=22 | (22^43)%77)=22 |
| 23 | (23^7)%77)=23 | (23^43)%77)=23 |
| 24 | (24^7)%77)=73 | (73^43)%77)=24 |
| 25 | (25^7)%77)=53 | (53^43)%77)=25 |
| 26 | (26^7)%77)=5 | (5^43)%77)=26 |
| 27 | (27^7)%77)=69 | (69^43)%77)=27 |
| 28 | (28^7)%77)=63 | (63^43)%77)=28 |
| 29 | (29^7)%77)=50 | (50^43)%77)=29 |
| 30 | (30^7)%77)=2 | (2^43)%77)=30 |
| 31 | (31^7)%77)=59 | (59^43)%77)=31 |
| 32 | (32^7)%77)=32 | (32^43)%77)=32 |
| 33 | (33^7)%77)=33 | (33^43)%77)=33 |
| 34 | (34^7)%77)=34 | (34^43)%77)=34 |
| 35 | (35^7)%77)=7 | (7^43)%77)=35 |
| 36 | (36^7)%77)=64 | (64^43)%77)=36 |
| 37 | (37^7)%77)=16 | (16^43)%77)=37 |
| 38 | (38^7)%77)=3 | (3^43)%77)=38 |
| 39 | (39^7)%77)=74 | (74^43)%77)=39 |
| 40 | (40^7)%77)=61 | (61^43)%77)=40 |
| 41 | (41^7)%77)=13 | (13^43)%77)=41 |
| 42 | (42^7)%77)=70 | (70^43)%77)=42 |
| 43 | (43^7)%77)=43 | (43^43)%77)=43 |
| 44 | (44^7)%77)=44 | (44^43)%77)=44 |
| 45 | (45^7)%77)=45 | (45^43)%77)=45 |
| 46 | (46^7)%77)=18 | (18^43)%77)=46 |
| 47 | (47^7)%77)=75 | (75^43)%77)=47 |
| 48 | (48^7)%77)=27 | (27^43)%77)=48 |
| 49 | (49^7)%77)=14 | (14^43)%77)=49 |
| 50 | (50^7)%77)=8 | (8^43)%77)=50 |
| 51 | (51^7)%77)=72 | (72^43)%77)=51 |
| 52 | (52^7)%77)=24 | (24^43)%77)=52 |
| 53 | (53^7)%77)=4 | (4^43)%77)=53 |
| 54 | (54^7)%77)=54 | (54^43)%77)=54 |
| 55 | (55^7)%77)=55 | (55^43)%77)=55 |
| 56 | (56^7)%77)=56 | (56^43)%77)=56 |
| 57 | (57^7)%77)=29 | (29^43)%77)=57 |
| 58 | (58^7)%77)=9 | (9^43)%77)=58 |
| 59 | (59^7)%77)=38 | (38^43)%77)=59 |
| 60 | (60^7)%77)=25 | (25^43)%77)=60 |
| 61 | (61^7)%77)=19 | (19^43)%77)=61 |
| 62 | (62^7)%77)=6 | (6^43)%77)=62 |
| 63 | (63^7)%77)=35 | (35^43)%77)=63 |
| 64 | (64^7)%77)=15 | (15^43)%77)=64 |
| 65 | (65^7)%77)=65 | (65^43)%77)=65 |
| 66 | (66^7)%77)=66 | (66^43)%77)=66 |
| 67 | (67^7)%77)=67 | (67^43)%77)=67 |
| 68 | (68^7)%77)=40 | (40^43)%77)=68 |
| 69 | (69^7)%77)=20 | (20^43)%77)=69 |
| 70 | (70^7)%77)=49 | (49^43)%77)=70 |
| 71 | (71^7)%77)=36 | (36^43)%77)=71 |
| 72 | (72^7)%77)=30 | (30^43)%77)=72 |
| 73 | (73^7)%77)=17 | (17^43)%77)=73 |
| 74 | (74^7)%77)=46 | (46^43)%77)=74 |
| 75 | (75^7)%77)=26 | (26^43)%77)=75 |
| 76 | (76^7)%77)=76 | (76^43)%77)=76 |
RSA-2048 use very large prime numbers. A private key and a public key is generated using these prime numbers. There are number of programs that generate RSA keys. OpenSSL is widely used to generate these keys.
There is a common function in many programs called powmod(A,B,M), which returns the modulus value A^B%M. Mathematically, the Modulus is the only part that the RSA equations require. The algorithms process this equation faster, by performing these equations by iterating one bit at a time and calculating the Modulus after every iteration and discarding the upper values
Each prime number used for RSA-2048 will be between 2^2047 2^2048. An estimated number of prime numbers between 2^2047 and 2^2048 is approximtely 10^613.
No. Not Possible.
To put the number 10^613 in perspective, here are some estimates of the number of atoms in objects
The number of atoms in a human hair: 10^6
The number of atoms in a person: 10^27
The number of atoms in the Earth: 10^50
The number of atoms in the Sun: 10^57
The number of atoms in the Milky Way Galaxy: 10^67
The number of atoms in the Universe: 10^80