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
40^{2}%77 = 60
40^{4}=60^{2}%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
61^{2}%77=25 2
25^{2}%77=9 4
9^{2}%77=4 8
4^{2}%77=16 16
16^{2}%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.