public key cryptography

Two keys (passwords in a sense) are generated. One is your private key, kept nice and safe and not shared. One is you public key, given to everyone you meet. If someone wants to send something secret to you, they encrypt it with the public key. The trick is that only the private key can decrypt it. This is the basis of most online secure commerce and private email. Also used for digital signing.

See also private key cryptography.

Currently public-key cryptography, available from numerous sites around the world, essentially places 'governmental strength' encryption capability in the hands of private individuals and organizations. Using complex algorithms (and the inherent difficulty in factoring extremely large numbers), freeware like P.G.P. (Pretty Good Privacy), once downloaded and installed generates two keys for every user (Sue for this example): one to be freely distributed- for senders, who ever they may be, to encrypt messages they plan to send to Sue (this is her public key). This key can be attached to her own messages, posted on a trusted server, or copied to a potential correspondents' system. A second key, one kept undistributed and locked away in Sue's computer, decrypts incoming messages encoded with the public key. It is mathematically infeasible, even if a person were to have the public key, discover the plaintext of a message and see the encrypted ciphertext, to work backwards to discover the algorithm which generated the private key.

In this manner, a text can only be deciphered by obtaining control of the private key (through the system of the owner and the passwords put in place) or through 'brute force' cryptanalysis- that is trying every possible combination of keys. Since a 4096-bit key is essentially a REALLY big number (hence the 4096 bits to represent it) which is then used by the coding algorithm to encrypt and 'hash' a message, for a message enciphered at this strength, this is a technical impossibility. The reason encryption is so much easier to do with a set key than 'un-do' by brute force can be demonstrated by the difficulty of factoring large prime numbers. While it simple enough to generate a large prime number (multiplication on paper of any two randomly selected large numbers will get you an even larger, ostensibly random number), it is painfully difficult to work backwards from that 4096-digit N to arrive at the two specific factors which produced it; there are just far too many combinations of possible numbers to try. Nearly eighty years after many mathematicians first began to examine the factoring problem for algorithm that might serve as a short-cut, the consensus is it will continue to be an 'intractable' problem for the foreseeable future- which is why it is in essence the theoretical backbone of many cryptosystems.

Trying to 'brute force' unlock a 4096-bit private key in this way, it is estimated by computer scientists and cryptologists that there is insufficient computing power on the planet for the foreseeable future to complete such an operation before the Sun burns out. The term 'pretty good protection' coined by the software's designer Phillip Zimmermann is a healthy bit of understatement on his part and the security it offers is almost absurdly over-powered for most peoples' concerns or needs. Again however, it should be noted that while the current 56-bit Data Encryption Standard is viewed as 'weak', and a 4096-bit P.G.P. key is seen as ludicrously strong- there is no hard middle ground. As Matt Blaze, a well-known commercial cryptologist says, "it has been difficult to find a 'magic' key length that once satisfies the security needs of individual interests and the wiretapping needs of government, because no such key can exist. The threat models used by private interests and government are completely different."

Update: Vitally important quibble, should you be discussing this issue with people in the know: gn0sis says "the 56 bits of DES and 4096 of RSA are not comparable, since DES is symmetric and RSA isn't. Nonsymmetric keys have to be a lot longer to be safe." Also, ariels adds PGP uses symmetric key cryptography, or symmetric cipher, for encryption. The public key aspect is quite separate and solves the key distribution problem, which is quite different from encryption.

RESOURCES

1. Electronic Freedom Foundation web site with subject indexed privacy issues archive: www.eff.org
2. Government of Canada Public Key Infrastructure (PKI) White Paper. Canadian Communications Security Establishment, May 1997. http://www.cse-cst.gc.ca/cse/english/gov.htm & www.ewa-canada.com/toc.htm (Electronic Warfare Associates site) company responsible for building Canada's secure public-key infrastructure.
3. The Risks of Key Recovery, Key Escrow, and Trusted Third-Party Encryption: 1997 report of leading private sector cryptography experts in the U.S. : http://www.crypto.com/key_study/reports.htm
4. 1997 OECD Guidelines on Cryptography Policy : http://www.oecd.org/dsti/sti/it/secur/index.htm

How to do public key encryption.
First pick two primes. Normally, these are 2¹⁰²⁴ 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ⁿ becoming p^n-1*p-1
so:
7*11
becomes:
7⁰ * (7-1) * 11⁰ * (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⁷ then %77)
7=bin(111) or 1 + 2 + 4
40⁷ = 40¹ * 40² * 40⁴ therefore
(40¹%77)*(40²%77)*(40⁴%77)=40⁷%77

Table for 40
------------
40%77		= 40
402%77		= 60
404=602%77	= 58
-------------

(40*60*58)%77 = 40⁷%77 = 61

Repeat for 9,3,11,74
9⁷%77 = 37
3⁷%77 = 31
11⁷%77 = 11
74⁷%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¹⁰²⁴ 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⁴³%77
37⁴³%77
...
46⁴³%77
again, by a process such as
(61¹)*(61²)*(61⁸)*(61³²)=61⁴³
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⁴³%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.

Public key / private key cryptography can be a difficult system to understand. Here is a plain language description. Throughout this explanation we will be talking about three people:

• Bob - Sue's friend
• Sue - Bob's friend
• Eve - Nobody's friend

Bob and Sue want to have a discussion over email but are worried that Eve might intercept their communications, so they decide they need to use cryptography. Bob and Sue create their own public keys and private keys. For a good image think of the public key as an open lock and the private key as the key to the lock.

Bob and Sue then send their public keys to a public key server. Again for an image think of a locker with with a person's name on it, say Sue. When you open the locker (which is always open) you see a rack full with multiple replicas of the above mentioned open lock.

So Bob wants to send a secure message to Sue. He writes his message, gets Sue's public key, encrypts the message, then sends it to Sue. Again with an image - think of Bob writing out a letter by hand. He then goes to Sue's locker and grabs one of those open locks. He puts his letter into a special envelope so that once he attaches the lock it can't be opened by anyone or anything without the key for the lock. He then puts it in a mailbox - sending it on its way.

Now in comes Eve. She really wants to know what is going on between Bob and Sue, so she hacks into a mailserver somewhere on the route between Bob and Sue. She sees the message come in and grabs a copy. For an image just think that Eve happens to moonlight for the Post Office. She sees the letter come in and grabs it.

If Bob had not used any encryption Eve would be able to just read the mail, but Bob did. No matter what eve does she cannot read the mail. As such she just sends it on its way.

Sue gets the email message she has been waiting for. She decrypts the message and reads it - she takes out her key and unlocks the lock that kept the envelope sealed.

Source - Simon Singh's The Code Book