How to do public key encryption.
First pick two
primes. Normally, these are 2
1024 or more in length, but for our example, we'll use 7 and 11. For larger ones, the
Miller-Jaeshke test or the less accurate but slightly easier
pseudoprime test is used to search a region of numbers to find two random
primes.
These
primes are multiplied to generate a number.
77=7*11
Calculate the "
phi" of the number (
Euler's phi function, a generalization of
Fermat's little theorem).
phi(77)=60 phi is used in the congruency a
phi(77) % 77 = 1 and is defined by the
prime power decomposition where each term is p
n becoming p
n-1*p-1
so:
7*11
becomes:
7
0 * (7-1) * 11
0 * (11-1)
Pick encryption key so that that 60 (phi77) is relatively
prime to it.
gcd(60,e)=1 say e=7. This is easily done with small numbers. For large
primes, it is probably easier to simply pick a third
prime larger then the first two you picked.
The will be used for the public key which is sent to everyone. That value calculated further below in the decryption process. Those who receive it have no idea what values were used to create it.
The
private key is the values (77,7).
A message, using
Kyberneticist's ad-hoc encryption alphabet:
00=space
01-26=a-z
27-52=A-Z
53-62=0-9
63-72=!-)
74-76=.,"
N i c k .
40 09 03 11 74
Often the numbers would be joined, say 400 903 117 4 for added security.
In this case, since the encryption is being done for such a small mod (77),
this cannot be done (see note further down).
For real encryption number calculated is a bit too large to compute the mod directly. (say, 409
(insert a 300 digit number here) % (insert another 300 or so digit here))
Not in this case, but if it were, the solution is to break down the number.
An easy method is as follows (I explain more fully in my
pseudoprime node).
(77,7 is key, 40
7 then %77)
7=bin(111) or
1 + 2 + 4
40
7 = 40
1 * 40
2 * 40
4 therefore
(40
1%77)*(40
2%77)*(40
4%77)=40
7%77
Table for 40
------------
40%77 = 40
402%77 = 60
404=602%77 = 58
-------------
(40*60*58)%77 = 40
7%77 = 61
Repeat for 9,3,11,74
9
7%77 = 37
3
7%77 = 31
11
7%77 = 11
74
7%77 = 46
So the encrypted message is 6137311146 or 8KEku in my alphabet
BTW, due to
pigeonhole principle, the % values will be evenly distributed over the range 00-76 in a
random fashion (well, random to those who don't know factoring of the number being modded by).
The number you are modding by is normally much larger then the number you are encrypting. Say around 2
1024 in size.
But it MUST be larger then the numbers being encrypted, or
information is lost. In this case, no number larger then 76
could be encrypted.
To decrypt, you create decryption key from phi(60) and the factors of 77 (7 or 11).
Create a decryption key by solving the following equation:
X(e) + Y(phi(77)) = 1
for X (there are a lot of potential X's)
7X + 60Y=1
The solution uses the following
mechanical process to the above, which is known as a linear
Diophantine equation.
Process known as the
Euclidean Algorithm:
a)
60=
7*8 + 4
b)
7=
4*1 + 3
c)
4=
3*1 + 1
3=
1*3 + 0
reverse it...
1=4 - 3 (by c)
1=4 - (7-4) (by b)
1=2*4-7 (re-arrange)
1=2(60-7*8) - 7 (by a)
1=2*60-7*17 (re-arrange)
therefore 7(-17)+60(2)=1
X=-17. This is really the solution to the
congruency 7X % 60=1
Since this is a
congruency (just accept this :-)), 7(-17) % 60 = 1 is same as 7(-17+60) % 60=1
Positive keys are easier to work with then negative ones, so make X = 43 (-17+60)
This gives the
public key 77,43.
Take: 8KEku
convert: 6137311146
do 61
43%77
37
43%77
...
46
43%77
again, by a process such as
(61
1)*(61
2)*(61
8)*(61
32)=61
43
43=bin(101011) or 1+2+8+32
Table for 61
---------------
61%77=61 1
612%77=25 2
252%77=9 4
92%77=4 8
42%77=16 16
162%77=25 32
---------------
(25*4*25*61)%77=61
43%77=40
40=N - first letter decrypted.
Repeat for the rest.
Congratulations, you have successfully encrypted and decrypted using public key encryption.
Normally, this process, which is slow and requires expensive operations for a
computer to do, would be probably used to establish a
private key encryption connection.
Feel free to message me if anything is unclear or incorrect - I'll fix it.
- Regarding fixing. I managed to confuse what was being sent out (now corrected). The critical bit is that the
information given out cannot include the factorisation.
For private key, you need 77 + <a factor>.
For public key, you need 77 + <a number calculated from the relatively
prime value + factor> (factors are kept secret).
This allows the process to be non-reversible.
What the private key mods, the public key decrypts.
What the public key mods, the private key decrypts.