Tech Note #35: How Encryption and Digital Signatures Work
©
1999 Bionic Buffalo Corporation; All Rights Reserved.
19 May 1999
http://www.tatanka.com
Page
4 of 10
Conceptually, the whole process is a complex scrambling operation, although there is an
underlying mathematical rigour to the design. The reason DES encryption works is that there is
no known, simple way to unscramble a message without the key. To break the code, an attacker
would have to try large numbers of keys, even with known systematic attacks. It is the
computational difficulty of trying this which makes DES secure. (However, see the section
Comparing Different Cryptosystems, below.)
One characteristic of DES is typical of symmetric cryptosystems: the key size is fixed. Each
symmetric algorithm almost always has a single, fixed key size.
RSA: An Example of an Asymmetric Cryptosystem
One of the most common asymmetric cryptosystems is RSA, named for the initials of the
inventors (Rivest, Shamir, and Adleman). Like most asymmetric algorithms, RSA has variable
key sizes, and is based on mathematical problems instead of on fixed scrambling operations. Of
course, like all asymmetric algorithms, the encryption key is different from the decryption key.
RSA is based on prime numbers. Unlike DES, which is based on a complex scrambling
operation, RSA depends on simple scrambling. On the other hand, for the same encryption
strength, RSA uses much larger keys.
An RSA encryption key consists of a pair of numbers (N, E). To encrypt a message M, the
sender computes C = M
E
mod N; the result is the encrypted (ciphertext) message.
The receiver must decrypt by solving the equation C = M
E
mod N, for the value of M. If this
were easy, then anyone could decrypt the message and the cryptosystem would not be of much
use. Therefore, it must be difficult to be useful. In fact, it must be so difficult as to be infeasible
to anyone who did not have a clue about the solution.
To accomplish this, choose the values of E and N in the following way:
1.
Choose two large prime numbers, P and Q.
2.
Choose E, so that E<PQ and (P-1)(Q-1) have no common factors. (That is, they are
relatively prime.)
3.
Compute D=E
-1
(mod(P-1)(Q-1)), so that DE = 1 (mod (P-1)(Q-1)).
The number or clue D needed to solve the problem easily is known as the decryption key or
secret key, since only the intended recipient knows it. The value E is known as the encryption key
or public key, since anyone who needs to send a message can and must know it.
Without knowing D, if the values of P and Q are large enough, the equation C = M
E
mod N is
extremely difficult to solve for M. Some implementations of RSA use values so large that all of
the computers on earth, working together, could not compute the solution in less than billions
of years.