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.