Digital Certificates
September 20, 2006
After the Class Four of Computer Applications to Law class I became very intersted in the way the digital certificates work. I found a couple of relevant sites which explain the working of the most common encryption method, RSA. One of them is an article on Wikipedia about RSA, and the other is the RSA website.
The way in which the encryption works is as follows (as may be found in the class Wiki):
This system of encrytpion may allow for all three main aims set out above (The identity, as pointed out in other discussions, might have to be verified by an independed third party, such as Verisign or Thwarte).
The principle of RSA encryption algorithm is as follows:
-
Take two prime numbers, p and q. For encryption to be practically secure, these prime numbers have to be quite large.
-
Multiply numbers p and q to derive a new number n, called the modulus.
-
Choose a number e which conforms to 1 < e < (p-1)(q-1), and e and (p-1)(q-1) have no common prime factors between them.
-
Choose a number d so that (de – 1)mod ( (p – 1)(q – 1) )=0, i.e. that (de-1) is evenly divisible by (p-1)(q-1)
When these numbers are derived, the pair (e, n) becomes the public key, and pair (d, n) becomes the private key.
The encryption then follows the following formula: Represent the message with W, and then encrypt it using K=W^e mod (n). The derived message, K, is then sent to the owner of the private key holder. The message is then decrypted using formula W=K^d mod (n).
Due to the nature of the mod function, the calculation cannot be reversed using the values in the private key, and only the public key can decrypt the message.
So far, there had not been a way to mathematically calculate the way to decrypt the message from the public key, even though it seems that no matter how large the prime numbers are taken, it should be possible to obtain a limited number of possible solutions to the problem.
One question remains in my mind: what is the length of the strings that are being encrypted? are they encrypted character by character, or is the message subdivided into strings which are then encrypted string by string, or is the whole message encrypted at once? This would require further investigation, but to me the second variant is more likely. The first one would be easily broken, and essentially be same as assigning a number to a letter (eg A=1, B=2 etc), and the latter would be computationally intensive.
