Sunday, February 10, 2013

Public Key Encryption Simplified



I just realized that my simplified example still looks very complicated, so how about making this on the level of the average 10-year boy, who is looking for a better way of encoding secret messages for his club.

First. The message. Let's say that it says: "Come at once!".  Change it to a numeric code, where each letter is replaced by 2 numbers: A=01, B=02 and so on, with a space being 00, and ignoring punctuation.
MESSAGE="Come at once!"
M=03-15-13-05-00-01-20-00-15-14-03-05 
Second. Pick 2 secret numbers that are prime and are at least 7, and multiply them to get N. Also calculate F=(P-1)*(Q-1)
P=7
Q=13
N=91
F=72
Third. Choose a public key.  This doesn't seem to work with 3 or 5, so choose one that is at least 10, and different from the other secret numbers.
E = 11
Four. This is the difficult part.  You have to find the private key, and there is no formula that I know of.  Calculate C=F*X+1, where X is unknown.  Now divide C by E, and get the remainder R.  If R=0, then D = C / E.  Clear as mud? (How come there isn't  a MOD button on the calculator).  Make a table.
X=2. C=72*2+1=145.  145/11 = 13, R=2.
X=3. C=72*3+1=216.  216/11 = 19, R=7.
X=4. C=72*4+1=289.  289/11 = 26, R=3.
X=5. C=72*5+1=361.  361/11 = 32, R=9.
X=6. C=72*6+1=433.  433/11 = 39, R=4.
X=7. C=72*7+1=505.  505/11 = 45, R=10.
X=8. C=72*8+1=577.  577/11 = 52, R=5.
X=9. C=72*9+1=649.  649/11 = 59, R=0.
X=10. C=72*10+1=721.  721/11 = 65, R=6.
Since when X=9, there is no remainder, that is the number we want.  So D is 59.

Five.  Create the public key.  The public key is a piece of paper labeled "Public Key", with 2 lines on it.  Since this is public,  anyone in the world can see it.
Public Key
E = 11
N = 91
Six.  Create the private key.  The private key is a piece of paper labeled "Private Key", with 2 lines on it.  Keep this a secret.
Private Key
D = 59
N = 91
Seven. Encrypting the message.

For each number in the message, do a "modPow".  Take the number to the power of E, then divide by N and look at the remainder.  Mod means the remainder.

3 ^11 = 177147. 177147 / 91 = 1946, R= 61
15 ^11 = 8649755859375.  8649755859375 mod 91 = 85
13^11 = 1792160394037.   1792160394037 mod 91 = 13
5^11=48828125.  48828125 mod 91 = 73
0^11=0. 0 mod 91 = 0
1^11=1. 1 mod 91= 1
20^11=204800000000000. 204800000000000 mod 91=41
14^11=4049565169664.  4049565169664 mod 91 = 14

So the encrypted message is:
61-85-13-73-00-01-41-00-85-14-61-73

Eight. Decrypting the message.  For each number in the message, take it to the power of the private key, then take the modulus.

61^59=21600324005767115759376408595633588120004550881459347787343132618730052107
20658594516681367387267118667141. Mod 91=3.

85^59=68504108227613915851338841725869587262113791581136609591307701645105806293
6063652870188889210112392902374267578125. Mod 91=15.

13^59=528029013288053029092010246418774432656697756230566661880485125877. Mod 91=13.

73^59=8630754176796486219653818740309875739500665166109981555339055206805093884
5476042523463763625071783240442229337. Mod 91=5.

41^59=14264204169981570374628699119097319788627256011797881508445743294237955574
1469552243337676275961. Mod 91=20.

14^59=41836380575506903762323730288068277971802268708096296987159150198784. Mod 91=
14.

The decrypted message is:
3-15-13-5-00-01-20-00-15-14-03-05

Conclusion: Somehow I don't see kids flocking to this idea.  I've made it as simple as I can, yet the complexity still remains.  And the big problem with this is that it looks like you are doing a letter-for-letter substitution, and not even a good one at that, with some of the letters (0,1,13,14) remaining the same.  Yet I am forced to because N is not big enough to contain the message.

Maybe there is some middle ground, with slightly bigger numbers that still illustrates the concept.

No comments:

Post a Comment