| Public Key Cryptography |
| Article Index |
|---|
| Public Key Cryptography |
| Page 2 |
| Page 3 |
| Page 4 |
| Page 5 |
| Page 6 |
Figure 12.1. RSA Identity.
This states that for a given key (E), there exists a matching key (D) which, when one is raised to the power of the other is equivalent to 1 with respect to base N. To put that in PHP terms:
pow($E, $D) % $N == 1
What this means for cryptography is that for any given value of $T that is less than $N, the following two equations are simultaneously true:
$C == pow($T, $E) % $N;
$T == pow($C, $D) % $N;
In other words, an unencrypted (plain text) value of $T, raised to $E (encryption key) and reduced by the base $N, becomes an encrypted value (ciphertext) of $C. That value can then be decrypted by applying the same equation, this time with the decryption key $D returning to the unencrypted value of $T.
An important side note here is that it doesn't matter which of the two paired values we use for $E during encryption, so long as we use the opposite value during decryption for $D. But wait, where do all these values come from?
First we start with two very large prime numbers. How large is going to depend on how secure you want your data to be. What's effectively unbreakable by today's computers may take only a week to decrypt on cutting-edge hardware five years from now. However large you choose them, they must be unique. Using the same prime number twice is completely ineffective.
We'll call these numbers P and Q. The first number in our (E, D, N) set we can determine immediately:
N = P * Q
This is going to make N an extremely large number (as many digits as P and Q have put together). Next we're going to calculate a temporary variable F.
F = (P-1)(Q-1)
At this point we can pick any one of several values for E so long as it is greater than 1, less than N, and relatively prime with F. Relatively prime means that E and F share no prime factors in common. E is allowed to be prime, but it's not required by the algorithm.
Now that we've collected our encryption key and our modulus, we need only to come up with a suitable decryption key. As it happens, this is very easy to do so long as we also know the value of F. All we have to do is find an integer value for D less than N, such that
DE mod F = 1
| Users' Comments (0) |
|
No comment posted
