Public Key Encryption

Public Key Encryption is simple and elegant, and has only been available since the invention of high-speed computers. 

Here is an example of how it works:

Step 1:  Start with 3 prime numbers.  The first 2 should be at least 600 bits, but for the purpose of this example I will use 200 bits.  The 3rd one, E, is a much small prime number.

P=1140883410519441712101308447239692533460267445025643826644911
Q=1590414661111417186713343719727926429804586929133475957467297
E=65537

Step 2: Get the product of P and Q, N.  N is of course a composite number.  This number here is very easy to factorize, so in actuality, you would want a much larger number.

[N = P*Q]
N=18144777027089157444288630814623233810136 9120798594281236591088451242203923952225919 0523528489981610529038878164513975567

Step 3: Calculate the totient of N.

[F=(P-1)*(Q-1)]
F=18144777027089157444288630814623233810136 9120798594281236590815321435040838062344453 8356560871018345674664719044729863360

Step 4: Calculate the decryption key.  X in the formula here is any number that will work for integer division by E.  It must be discovered by trial and error.

[D =(F*X+1)/E]
X=34621
D=95852774074927707993761796761077098088217 3479281647406913958621426583845591735420805 994209285068375812175827975763196353

Step 5: Display the keys.  N is the same for both the public key and private key, so the real private key is D. Note that the encryption key is much shorter than the decryption key.

public key={E=65537, N=18144777027089157444288630814623233810136 9120798594281236591088451242203923952225919 0523528489981610529038878164513975567}

private key={D=9585277407492770799376179676 1077098088217347928164740691395862142658384 5591735420805994209285068375812175827975763
196353,
N=18144777027089157444288630814623233810136 9120798594281236591088451242203923952225919 0523528489981610529038878164513975567}

Step 6: Prepare the message.  To make this simple I will only allow upper case letters and use a 0 for a space, and then interpret as a Base 36 number.  It would be easy to just use the byte value instead.

MESSAGE="HELLO WORLD"
M=63637474127610289

Step 7: Encrypt the message.  This is M to the power of E, and then returning the Modulus of the result with N.

[Z=(M^E) mod N]
Z=13728116117865984092396572529148599991502 7809873508726974002483165839383589462390086 8382826983129627158084569236296982522

Step 8: Decrypt the message.  This is the same formula, with different inputs.

[A=(Z^D) mod N]
a=63637474127610289
message=hello0world

Conclusion: Simple and elegant.  It should be used more.

Update:  Even with a 400 bit product (121 digits), my verification program can't crack this after 20 minutes.  So I think this is sufficient for all practical purposes.  RSA uses a 2048 bit key.

Update2: I ran the verification program again. After 36 minutes, it only had a 92% chance that the smallest factor had at least 25 digits.  So I think 100 bit numbers should really be sufficient.