This is a continuation of a previous post.
I subscribe to Scientific American, have for maybe 50 years. I saved this issue:
Yes, it’s all about corals. No, there’s an additional item:
Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing.
Today people may find this curious, but 40 years ago the prospect of e-mail was just looming on the horizon. For those not old enough to remember, what we had for e-mail in olden days was called the telegraph. If you wanted to send somebody a message you went to Western Union and gave them all the text, and they sent your message by wire. Or by radio link. Then somebody printed out the message on the other end, and a guy on a bicycle delivered it to your door. I have received one or more of those.
The hot new concept of e-mail was that a person could sit at his own computer at home or else at his boss’s computer at work, compose a message, enter the recipient’s e-mail address, and hit the send button. Not many people were doing that 38 years ago.
But suppose you want to keep your e-mail contents private. No problem. You just run your encryption program against your e-mail text, and you send the encrypted text. The recipient on the other end will run the proper decrypting program against the message to extract the clear text. If he has the proper cypher key. You have to give him the key.
Suppose giving your recipient the key were not a problem. Now you want to send e-mail to hundreds of people. You have to give each one of them the same cypher key. Even if there were a secure way of doing this, things would begin to get a little shaky. It only takes one loose cannon (just ask Edward Snowden) among your long list of recipients, and your plan for secure messaging is blown.
This is what Diffie and Hellman sought to fix. It works like this:
You have two processes for handling messages. One encrypts messages, and the other decrypts messages. Call the two processes E and D for encrypt and decrypt. Now have all participants come up with their own pair of E and D (no two alike supposedly). Everybody publishes for all the world to see his E. Now we have all these published encryption processes which we will call E1, E2, E3, etc. Everybody keeps his D to himself, a secret. How are you going to use this system?
No problem. If you want to send a message to number 2, you get yourself a copy of E2 and encrypt the message. Then you send the encrypted message to 2, who has no problem extracting the clear text, because he has the only copy of D2. This process is described using the following notation:
D2(E2(m)) = m
In this notation m is the clear text message. The parenthesis mean “apply the operator (D or E) to whatever is inside the parenthesis.
What Diffie and Hellman did not do in their 1976 paper was to describe a way to implement this. In 1978 Ronald Rivest, Adi Shamia and Len Adelman (RSA) published “A Method for Obtaining Digital Signatures and Public-Key Cryptosystsms.” They foolishly offered to send a copy of their paper to readers who requested one. I did not have e-mail at the time, but postal mail worked just fine:
An essential requirement of a public key system is that your everyday Edward Snowden should not be able to take E and derive D from it. The method described by RSA involves using pairs of very large prime numbers. Call a pair of these numbers p and q. Then
p x q = n.
The number n is not prime. It has only two factors, p and q. Now suppose each of p and q are 100 decimal digits long (or more). Then the length of n is 200 (or more). The RSA method uses p and q (and n) to produce e and d. Read the RSA paper, page 6. This involves some nice math, which I will not elaborate on here.
A user R can publish n and e, keeping d (and p and q) private. Somebody wanting to send R a message uses n and e to encrypt the message. R uses n and d to decrypt the message. Knowing n it is still very difficult to compute d, even if you know e. Computing d is tantamount to factoring n (into p and q). It is well known that the factoring problem is hard. Factoring n is only a bit less difficult than doing a search for p (or q), but it is not easy enough to make it feasible with present day computational facilities.
Practical cryptographic systems use keys many (>> 100) digits long and are considered to be secure. The RSA public key system is proposed as a method for securely distributing keys to users in the field. As of this writing the Wikipedia entry outlines some approaches to attacking the RSA public key system:
- When encrypting with low encryption exponents (e.g., e = 3) and small values of the m, (i.e., m < n1/e) the result of me is strictly less than the modulus n. In this case, ciphertexts can be easily decrypted by taking the eth root of the ciphertext over the integers.
- If the same clear text message is sent to e or more recipients in an encrypted way, and the receivers share the same exponent e, but different p, q, and therefore n, then it is easy to decrypt the original clear text message via the Chinese remainder theorem. Johan Håstad noticed that this attack is possible even if the cleartexts are not equal, but the attacker knows a linear relation between them. This attack was later improved by Don Coppersmith.
See also: Coppersmith’s Attack
- Because RSA encryption is a deterministic encryption algorithm (i.e., has no random component) an attacker can successfully launch a chosen plaintext attack against the cryptosystem, by encrypting likely plaintexts under the public key and test if they are equal to the ciphertext. A cryptosystem is called semantically secure if an attacker cannot distinguish two encryptions from each other even if the attacker knows (or has chosen) the corresponding plaintexts. As described above, RSA without padding is not semantically secure.
- RSA has the property that the product of two ciphertexts is equal to the encryption of the product of the respective plaintexts. That is m1em2e ≡ (m1m2)e (mod n). Because of this multiplicative property a chosen-ciphertext attack is possible. E.g., an attacker, who wants to know the decryption of a ciphertext c ≡ me (mod n) may ask the holder of the private key to decrypt an unsuspicious-looking ciphertext c′ ≡ cre (mod n) for some value r chosen by the attacker. Because of the multiplicative property c′ is the encryption of mr (mod n). Hence, if the attacker is successful with the attack, he will learn mr (mod n) from which he can derive the message m by multiplying mr with the modular inverse of r modulo n.
I have as yet not learned of any systematic way to attack the RSA key system. PGP stands for Pretty Good Privacy, and it incorporates public key technology:
While originally used primarily for encrypting the contents of e-mail messages and attachments from a desktop client, PGP products have been diversified since 2002 into a set of encryption applications which can be managed by an optional central policy server. PGP encryption applications include e-mail and attachments, digital signatures, laptop full disk encryption, file and folder security, protection for IM sessions, batch file transfer encryption, and protection for files and folders stored on network servers and, more recently, encrypted and/or signed HTTP request/responses by means of a client side (Enigform) and a server side (mod openpgp) module. There is also a WordPress plugin available, called wp-enigform-authentication, that takes advantage of the session management features of Enigform with mod_openpgp.
I have my copy of the RSA paper, and thanks to the remarkable progress the Internet has made since 1979 you can now get your own copy through the link I supplied above. I have scanned Hellman’s Scientific American article to a PDF, and I will send a copy to everybody who asks for one. By e-mail.