* Exponentiation ciphers* are due to Pohlig and
Hellman [2]. They are less vulnerable to frequency analysis than
block ciphers. Here's the procedure.

1. Let p be a prime number, and let e be the *
exponent*, such that .

2. Encode the letters of the alphabet as

3. Group the letters in the message in blocks of m letters, where m is chosen so that

For example, suppose . Then you should use blocks of letters, because . And if , you should use blocks of letters, because . This stipulation merely ensures that the blocks are unique mod p.

4. Encode a block A using

The ciphertext C is an integer satisfying and this integer *is*
the ciphertext: You don't convert it to letters.

* Example.* Encode the plaintext "DEEP
YOGURT" using and exponential cipher with and .

I have . Note that .

I use blocks of letters, because

Take the plaintext and convert it to numbers:

Now encode the message:

The ciphertext is

How should you do these computations? The *best* way to do the
computations is to use software which can do large-integer
arithmetic. Most calculators can only accomodate 10--20 digit
integers. If you try to compute on a calculator, you'll find that
it's around .
Because these computations require modular arithmetic, you can't use
floating point --- you are losing significant digits.

So how do you do something like if all you have is a calculator? First, rewrite it:

Now I'll compute and reduce it mod 2621:

(I got the last result by finding . Subtract the integer part (2223) times 2621 from 5827396: .)

Therefore,

It should be clear how to proceed. Use the rules for exponents to reduce the product a little bit at a time, so that the intermediate results don't overflow your calculator.

Obviously, it is easier to use a computer!

To decode a message that has been encoded using an exponentation cipher,find d such that

This is possible (using the Euclidean algorithm), since by assumption. Equivalently, for some k,

Now suppose . Then

Note that A is less than (m 25's) because A came from a block of m letters. Since , it follows that , and Fermat's theorem implies that .

In other words, raising C to the d-th power recovers the plaintext from the ciphertext.

* Example.* Decode the block which was encoded using an
exponential cipher with and .

; apply the Extended Euclidean algorithm:

Hence, .

So to decode , raise it to the 1191-th power:

, which is the plaintext for this block.

In a * public-key cryptosystem*, there are
separate keys for encoding and decoding messages. One key is public,
so that anyone can send a message to me. But I'm the only one who
knows the private key, so I'm the only one who can read my messages.
Moreover, I can use my private key to *send* messages, which
can be decoded using the public key. Since I'm the only one who could
have encoded such a message, people know the message must have come
from me --- a * digital signature*.

The key is to come up with a * one-way function*:
roughly, something which is easy to compute, but whose inverse is
difficult to compute.

The * RSA* public-key cryptosystem is due to
Rivest, Shamir, and Adleman [3]. You'll see that it's essentially a
modified exponentiation cipher.

The *idea* of creating an asymmetric public-key system is due
to Whitfield Diffie and Martin Hellman [1]. But they didn't explain
how to implement the necessary one-way function. Clifford Cocks, a
mathematician at the British intelligence agency GCHQ, had described
in an internal document in 1973 a cryptographic scheme equivalent to
RSA. However, it did not come to light until 1997 due to its security
classification.

Actually implementing an RSA system for real-world use is tricky ---
lots of things can go wrong! So you should regard what follows as a
simplified description to get the main ideas across. (This is what's
known as "textbook RSA".) Take a look at some
*recent* books on cryptography to get an idea of the issues
involved with implementation.

The article by Robinson [4] is recommended for an account of the creation of RSA, and a general overview.

1. Let p and q be *large* prime numbers. For practical
applications, you'll need primes which are around 100 digits long.
Let . (n is called the * key*.)

2. Find an exponent e such that , and such that .

If n were prime, would be , and I'd have the setup for an exponentiation cipher. The condition guarantees that you can't recover the plaintext A by taking e-th roots. For if A is any block besides or , the result is when it's raised to the e-th power, so it changes when it's reduced mod n.

3. Encode the letters of the alphabet as

4. Group the letters in the message in blocks of m letters, where m is chosen so that

5. Encode a block A using

* Example.* Encode the message "CRAB
LEGS" using an RSA cipher with and .

Note that is relatively prime to 2520, and .

Since , I use blocks of two letters.

Take the plaintext and convert it to numbers:

Now encode the message:

The ciphertext is

When this system is used, e and n are made public so people can encipher messages. The security of this method depends on the difficulty of finding , since (as I'll show below) this is what you need to decode a message.

On the one hand, if you know p and q, then

Since p and q are known, so is .

On the other hand, suppose you know , you *don't* know p and q,
but you *do* know that n is a product of two primes p and q.
Then

Therefore,

Moreover,

The last two equations show that if you know (and n), then you can find , and from that you can find . But

Thus, you know p and q.

To summarize, knowing is equivalent to knowing p and q.

If p and q are 100-digit primes, then is around 200 digits. With present technology, it's hard to factor an arbitrary 200-digit number. It follows that finding --- and hence, breaking the code --- is difficult at the moment, which means the system is fairly secure.

Of course, *no* cipher is immune to human carelessness! If you
let someone discover your key, the cipher is worthless.

* Example.* The product of two prime numbers p
and q is , and . Without factoring
directly, find p and q. Show your work!

I have

Also

From and I get and .

Now here's how knowing allows you to decode a message. The idea is similar to that used in the exponentiation cipher.

Find d such that

This is possible (using the Euclidean algorithm), since by assumption. Equivalently, for some k. Now suppose . Then

is a consequence of Euler's theorem, and will be true provided . Now , so it's possible for this to fail if the plaintext A has either p or q as a prime factor. However, if p and q are each around 100 digits long, the probability that this will happen is around --- so it's nothing to worry about.

Just as in the exponentiation cipher, raising C to the d-th power recovers the plaintext from the ciphertext.

* Example.* Take and . Show that 2114 is *not*
an enciphered message by decoding it.

Recall that . Apply the Extended Euclidean algorithm:

Then

However, 80 can't be a block in a message, because it's greater than 25. Therefore, 2114 is not a ciphertext for this key.

[1] W. Diffie and M. Hellman, New directions in cryptography,
*IEEE Trans. Inf. Theory*, 22(1976), 644--654.

[2] S. Pohlig and M. Hellman, An improved algorithm for computing
logarithms over and its cryptographic
significance, *IEEE Trans. Inf. Theory*, 24(1978), 106--110.

[3] Rivest, R.; Shamir, A.; Adleman, L., A method for obtaining
digital signatures and public-key cryptosystems, *Communications
of the ACM*, 21(2)(1978), 120--126.

[4] S. Robinson, Still guarding secrets after years of attacks, RSA
earns accolades for its founders, *SIAM News*, 36(5)(2003).

Copyright 2019 by Bruce Ikenaga