Author : Brian Raiter
Page : 1 Next >>
Text written by Brian Raiter
Html code slightly adapted by BlackB
Nothing in the text has been changed
Table of Contents
-Preface: What is This?
-Introduction: The Idea of a Trapdoor Function
-Background, Part I: How to Calculate with Exponents
-Background, Part II: Modulus Arithmetic
-Background, Part III: The Fundamental Theorem of Algebra
-Background, Part IV: Relatively Prime Numbers
-Euler's Totient Function
-Euler's Totient Theorem
-Variations on a Theme
-The Plot Thickens
-Does This Really Work?
-Making a Pair of Keys
-An Example
-How to Cracck RSA
-How to Make RSA Uncrackable
-Huge Exponents in Modulus Arithmetic
-Safety in Numbers
-References
Preface: What is This?
The RSA cipher is a fascinating example of how some of the most abstract mathematical subjects find applications in the real world. Few are the mathematicians who study creatures like the prime numbers with the hope or even desire for their discoveries to be useful outside of their own domain. But every now and then that is exactly what happens.
This text explains the mathematics behind RSA -- how and why it works. The intended audience is just about anyone who is interested in the topic and who can remember a few basic facts from algebra: what a variable is, the difference between a prime number and a composite number, and the like.
The most important mathematical facts necessary for understanding RSA's foundations are reviewed near the beginning. Even if you are familiar with everything covered in these sections, I would recommend that you at least skim through them.
In one or two places, I have specifically targeted an explanation to what I consider to be the average computer programmer, leveraging analogous concepts in programming and general mathematics.
Before getting started, I should make some observations on the mathematical notation used here.
For the most part, where notations for the same idea differ between standard mathematics and the common practices among computer programmers, I have stuck with the mathematicians. This is, after all, a mathematical subject. However, I have deviated in a few places where there was too much opportunity for confusion. I have used * to denote multiplication, and have completely avoided "implied" multiplication (i.e., using PQ as shorthand for P * Q). Since not all web browsers can display superscripts, I have used ^ to denote exponentiation. (This necessitates more parenthesizing than would normally be used.) The mathematician's three-bar congruency symbol is not available, so I have made do with = instead. Variables are always named with a single capital letter.
Finally, please note that throughout the text I use the word number to refer specifically to a positive integer -- what are sometimes referred to as the natural numbers, or counting numbers.
Introduction: The Idea of a Trapdoor Function
What a mathematician refers to as a function is very similar to a function in computer programming. It is, in essence, an abbreviation. For example:
F(X) = 7 * X + 43.
If X happens to be 3, then F(X) will be 64. So, "F(3)" is shorthand for "7 * 3 + 43".
The same function in a C program might look like:
int F(int x)
{
return 7 * x + 43;
}
Of course, in a computer program, functions are used to encapsulate all kinds of algorithms, and frequently make use of external variables and the like. In mathematics, however, a function is used solely for the number it returns. And, given a certain number as input, they will always return the same output. (Thus, rand() would not qualify as a mathematical function, unless it were written so that the seed value was passed in as an input parameter.)
Mathematicians often consider how to construct a function's inverse -- taking a function and making a new one that "goes in the other direction", so to speak:
G(X) = (X - 43) / 7.
G(64) is equal to 3, and in general, G(F(X)) is equal to X. Therefore, G is F's inverse. Not all functions are invertible, of course. Clearly, the function:
F(X) = X * 0
cannot be inverted. (Because how could G(F(X)) return X when F(X) is always zero?)
Usually, when you have a mathematical function for which an inverse does exist, constructing it is not too difficult. In fact, it is often transparent. Typically, you can just run through the steps backwards, subtracting where the original function adds, and so on. But can it be done for every invertible function?
To put the question in terms of programming, imagine that there are two functions:
int foo(int x);
int bar(int x);
foo() and bar() work like mathematical functions -- they do nothing but compute a return value, and given the same number for input, they will always produce the same output. (And pretend for the moment that this is on a machine where integers can be arbitrarily large.) Suppose you are told that bar() is the inverse of foo(). The statement:
x == bar(foo(x))
is always true, as long as x meets foo()'s requirements for a valid argument.
Now, imagine that you have the source code for foo(), but not for bar(). Can you write your own replacement for bar(), just by examining foo()?
It seems that you ought to be able to. There are no secrets as to what foo() does, after all. You can run foo() with different inputs as many times as you like. You already know that bar() exists, somewhere, so you that it is possible to write. Is it guaranteed that you can reconstruct it?
Theoretically speaking, the answer is yes. Given such an function, it is always possible to construct its inverse. However, if we also throw in the tiny constraint that you have to finish before the heat-death of the universe, the answer subtly changes.
There are some special functions that, though what they do is simple enough, and how they do what they do is utterly transparent, figuring out how to undo what they do is a diabolical task. Such a creature is a trapdoor function. Anyone can fall through a trapdoor, but only those who know where the hidden lever is can climb back out again.
In 1975, Whitfield Diffie, Martin E. Hellman, and Ralph Merkle realized that a trapdoor function could be the basis for an entirely new kind of cipher -- one in which the decoding method could remain secret even when the encoding method was public knowledge. Diffie and Hellman published a paper in 1976 that described this idea, and offered some examples of weak trapdoor functions. And in 1977, Ronald L. Rivest, Adi Shamir, and Leonard Adleman outlined, in an MIT technical memo, an excellent candidate that became the basis for the RSA cipher.
What follows is a description of that function.
Background, Part I: How to Calculate with Exponents
Here's a quick refresher on how to combine exponents. Recall that:
N^2 = N * N,
N^3 = N * N * N,
N^4 = N * N * N * N,
and so on. For example:
2^7 = 2 * 2 * 2 * 2 * 2 * 2 * 2 = 128.
If we fiddle with exponents for a bit, we will quickly realize that:
N^E * N = N^(E + 1).
So, for example:
2^7 * 2 = 128 * 2 = 256 = 2^8.
Building upon this, we can also see that:
N^E * N * N = N^(E + 2).
But N * N can also be written as N^2:
N^E * N^2 = N^(E + 2).
We can extrapolate from this, and derive a more general rule -- namely:
N^A * N^B = N^(A + B).
And, if we repeated this process on the next level up, we would find that:
(N^A)^B = N^(A * B).
These two simple facts are very useful when handling exponent-laden formulas.
Background, Part II: Modulus Arithmetic
Most computer programmers are familiar with modulus as a "remainder" operator, usually denoted by "%", which gives the remainder of an integer division instead of the quotient. For example:
27 % 12 = 3.
Though the idea is the same, the mechanics here are slightly different from what mathematicians refer to as modulus arithmetic. In essence, modulus arithmetic consists of taking the infinitely long number-line and coiling it around a finite circle. All the numbers that land on the same point along the circle's edge are considered interchangeable, or congruent. Thus, the analogue to the above example
Page : 1 Next >>