SXEOLF NHB FUBSWRJUDSKB (PUBLIC KEY CRYPTOGRAPHY)

Posted on November 13, 2011 by admin

The need to create secure codes is said to go back to Julius Caesar, who moved letters in his messages up by three through the alphabet. That is encoding. How would you decode such a message?

Modern day cryptography, which is the art of coding and decoding messages, has taken on a new relevance with computer transfer of information, and it retains its traditional relevance in military settings. It makes use of a public key, which does not require its users to share a key as this would, make their coded message susceptible to attack.

Traditional number theory has produced a number of means of securely coding messages, but “securely” is a relative term. Modern methods depend on the simple ability to multiply two large numbers together and the very difficult problem of finding those factors given only their product.

A little history

The history of cryptography began thousands of years ago. Until recent decades, it was the story of what might be called classic cryptography, that is, of methods of encryption that use pen and paper, or perhaps simple mechanical aids.

The earliest methods made use of substitution ciphers. This is a method of encryption by which units of plaintext are replaced with cipher text according to a regular system; the “units” may be single letters, pairs of letters, triplets of letters and so forth. The receiver deciphers the text by performing an inverse substitution. There are a number of different types of substitution cipher. If the cipher operates on single letters, it is termed a simple substitution cipher; a cipher that operates on larger groups of letters is termed polygraphic.

Julius Caesar is said to have encoded messages by moving each letter up by three in the alphabet. For example, ARRIVING FRIDAY becomes DUULYLQJ IULGDA. The inverse substitution is clearly just moving each letter back by three in the alphabet. If encryption is denoted by E and decryption by D, then E(FRIDAY) = IULGDA and D(IULGDA) = FRIDAY. We can write D=E^{-1}. Grouping letters disguises the plaintext a little: write the message as ARR IVI NGF RID AYX, so that E(ARR) = DUU, and so on.

This approach is very much improved by using a (modified) Vigenère cipher. Choose a 3-digit number, such as 427, and move the letters in each group of three up by 4, then 2, then 7, through the alphabet. Now we have E(ARR IVI) = ETX LXO. Breaking this code amounts to finding the key 427. When the key is as long as the original message, and is used only once, the code is considered unbreakable; in this case it is called a one-time pad.

In the early 20th century, the invention of complex mechanical and electromechanical machines, such as the Enigma rotor machine, provided more sophisticated and efficient means of encryption; and the subsequent introduction of electronics and computing has allowed elaborate schemes of still greater complexity, most of which are entirely unsuited to pen and paper.

The publication of the paper “New directions in cryptography” by Whitfield Diffie and Martin Hellman in 1976 was the most significant development. It introduced a radically new method of distributing cryptographic keys, which went far toward solving one of the fundamental problems of cryptography, namely, the need to keep keys secret when shared by a number of users. The article stimulated the almost immediate public development of a new class of enciphering algorithms, and led to vast improvements in techniques for the factorization of large numbers and the testing of large numbers for primality. These aspects of number theory were vital to the Diffie–Hellman key exchange.

Before describing the best known of these approaches, the RSA algorithm, we need to develop a result in number theory. It relies on a modest familiarity with the binomial theorem and modular arithmetic.

Proof of the formula t^{(p-1)(q-1)}\equiv1 (mod pq), for distinct primes p, q not dividing t

We begin with the formula for binomial coefficients:

    \[\binom pi=\frac{p!}{i!(p-i)!},\]

where, for our purposes, p and i are integers with 0 < i < p. Froom

    \[i!\binom pi= p(p-1)(p-2)\cdots(p-i+1),\]

it follows that p must be a divisor of \binom pi, since p divides the right-hand side but does not divide i!.

Then, for any integers A, B, C, by the binomial theorem,

    \[(A+B)^p=A^p+\binom p1 A^{p-1}B+\binom p2 A^{p-2}B^2+\cdots+B^p\equiv A^p+B^p \pmod p,\]

so

    \[(A+B+C)^p=((A+B)+C)^p\equiv(A+B)^p+C^p\equiv A^p+B^p+C^p \pmod p.\]

In this way, for any integers, A_1, A_2, …, A_t,

    \[(A_1+A_2+\cdots+A_t)^p\equiv A_1^p+A_2^p+\cdots+A_t^p \pmod p.\]

Now put A_1=A_2=\cdots=A_t=1 and we obtain

    \[t^p\equiv t \pmod p.\]

Since p does not divide t, it follows that

    \[t^{p-1}\equiv 1 \pmod p.\]

Now raise both sides of this congruence to the power q-1:

    \[t^{(p-1)(q-1)}\equiv 1 \pmod p.\]

By the same token,

    \[t^{(p-1)(q-1)}\equiv 1 \pmod q.\]

These say, respectively, that there are integers h and k such that

    \[t^{(p-1)(q-1)}=1+ph, \quad t^{(p-1)(q-1)}=1+qk,\]

so ph=qk. Then p divides k (since p and q are distinct primes), or k=pl, say, for some integer l. Now we have t^{(p-1)(q-1)}=1+pql, or

    \[t^{(p-1)(q-1)}\equiv1 \pmod {pq},\]

as required.

The RSA cryptosystem

RSA stands for Rivest, Shamir and Adleman, who first proposed this scheme in 1978. It works as follows.

First choose two distinct primes, p and q. Calculate N=pq and F=(p-1)(q-1). Choose an integer E at random between 3 and N-2, but such that E and F have no prime factors in common. The pair (N,E) is the public key, and is made known to all by the sender of the message to be encrypted. The private key D, which the sender will keep secret, is calculated as D\equiv E^{-1} (mod F), that is, the number such that DE\equiv1 (mod F). This is easily done using Euclid’s algorithm.

The message to be encrypted is taken to be a portion of the plaintext reported as an integer x, 0\le x<N. The simplest method for this is to replace each letter in the message by its numerical position in the alphabet: A, B, \ldots, Z become 01, 02, \ldots, 26. For example, ARR becomes 011818, or just 11818. (This requires N>262626.) Traditionally, it is Bob who is going to encrypt the message and send it to Alice for decryption. Alice has chosen p and q, calculated N and F, chosen E (and published (N,E)), and calculated~D. Bob encrypts x by calculating y\equiv x^E (mod N), 0<y<N, and sends y to Alice. Alice receives the message y and decrypts it by calculating x\equiv y^D \pmod{N}.

This works because DE=1+kF, for some integer k, and

    \[x^F=x^{(p-1)(q-1)}\equiv1 \pmod N\]

(as we showed above), and so

    \[y^D\equiv x^{DE}=x(x^F)^k\equiv x\cdot1^k=x \pmod N.\]

The reason that RSA is so effective lies in the choice of the primes p and q (by Alice). These should be very large, around 100 digits each, say. It is easy for Alice to calculate N and F and the private key D. But no one else can calculate F or then D because of the difficulty of factoring N to retrieve p and q. There are very quick methods of calculating y^D (mod~N), for example, even though D, usually, and N are huge numbers. The technique is called modular exponentiation.

How can Alice be sure that the message she has received came from Bob? The RSA system allows for signed messages by allowing Bob to have his own public and private keys. He encrypts a message exactly as described above but using his own keys (so the message is now signed), processes it again using Alice’s public key and sends it to Alice. She, in turn, applies her private key to this message to retrieve the signed message and then uses Bob’s public key to recover the original message. The principle is that the message must have come from Bob since only he knew his private key.

The Message

The message, in plaintext, is clear.

This entry was posted in English, Vignettes. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *