We have used cyclic addition or multiplication to generate a pair of keys for encoding and decoding. However, in both cases, the decode key can be easily computed from the encode code, given some knowledge in math. Can raising power in the cyclic world make any improvement?
Raising power means multiplying a number by itself, a certain number of times:
In the cyclic world of modulo n, you can raise number a to power b, and then divide by n to have its remainder. Or, since raising to power is repeated multiplication, you can take the remainder for each multiplication, so that you never need to deal with numbers greater than n. The process is written as:
ab mod n, or a^b mod n
In the ordinary world, power-raising will get you very large numbers, and undoing that means to take roots (square-root, cube-root, etc.), which is an exceedingly tedious process.
In the cyclic world, power-raising will not give large numbers -- the result, being a remainder, is always less than the modulo. Just as there is no division in cyclic math, there is no root-taking in cyclic math. However, since we can undo cyclic addition by another addition, undo cyclic multiplication by another multiplication, perhaps we can undo cycle power-raising by another power-raising?
Back to table of content
The math of cyclic power-raising is quite complicated. In fact, given a modulo n, it is not always possible to undo power-raising by another power-raising. However, if the modulo n is a product of distinct primes, this undoing is always possible. This means that, there is a way to generate two powers d and e, such that:
Here, you can pick two primes p and q, the product pq will be the modulo. Press the button "Generate" will generate the pair of keys for encoding and decoding. Type in a message, and press the "RSA" button to see cyclic power-raising encoding in action.
You can verify the first step (from symbols to binary) by this ASCII converter.You can verify the calculations by this Modulo Power Calculator.
Back to table of content
With cyclic power encoding, when a number x is encoded, the coded number is: y = xe mod n.
To decode the number y, we compute: yd mod n = (xe)d mod n = x(e * d) mod n.
However, for the power-raising to undo each other, it is not that: e * d = 1 mod n.
Instead, from the Fermat-Euler theorem, the correct condition is:
e * d = 1 mod phi(n) for n = product of distinct primes
where the symbol phi(n) is called the Euler's phi-function of n: it counts how many numbers less than the modulo n are relatively prime to n.
If the modulo n is a bifactor, that is, n = pq, then phi(n) = phi(pq) = (p-1)(q-1).
Therefore, once two different primes p and q are chosen, we have a bifactor n = pq. Then we can compute m = phi(n) = (p-1)(q-1). Just as in the case of key-pair generation of cyclic multiply encoding, we can choose a number e which is relatively prime to m (that is, gcd(e, m) = 1) as the encode key. Then we can use the extended Euclidean algorithm to compute the decode key d, which is the inverse of e in modulo m (that is, e * d = 1 mod m, or e * d = 1 mod phi(n)).
Back to table of content
Cyclic power encryption, or RSA encryption, uses a pair of keys e and d derived from the modulo n=pq, a bifactor. The relationship between the keys e and d is: e * d = 1 mod phi(n), so you need to know phi(n) before you can apply standard math procedures to compute d from e.
Given a number n, the only known way to compute phi(n) is through its factorization. For example, if n = pq, then phi(n) = (p-1)(q-1).
The beauty of the RSA encryption is:
Indeed, RSA encryption is now the basis of several security protocols for message exchange over the Internet. In practical uses of RSA, primes more than 100-digits are routinely used.
Back to table of content
In the RSA scheme, it is very difficult to compute the decode key (d,n) even when the encode key (e,n) is known. Given this characteristics, this means that we can actually make the encode key public, and we just keep the decode key private. We can use the following terms:
You can make the public key public by:
Alternatively, if you have something important to tell your partner, or the world, you can encode the message by your private key. Anyone can read your message by decoding that using the public key. Moreover, everyone knows that the message must be from you: since only you holds the private key. This is called authentication.
The RSA encryption can be applied for any modulo n which is a product of distinct primes. Here, you can choose any modulo n, not restricted to a bifactor. In fact, you can put in a product of factors. Click the "Generate" button, and the modulo value will be computed, along with its phi-function value. Then a pair of keys will be generated, as before. You can press "Anthor Pair" button for other pairs of keys. Click the "RSA Again" button and scroll up to see how this pair does encoding/decoding. However, unless your modulo number is a product of distinct primes, you'll find that the encoding/decoding breaks down.
Back to table of content