Title:RSA Public-Key Cryptography

Language:C++

Author:Philip J. Erdelsky pje@efgh.com http://www.alumni.caltech.edu/~pje/

Date:October 25, 2001 (revised August 22, 2002)

Usage:Public domain; no restrictions on use

Portability:Any C++ environment, but random number generator is specific to DOS and DOS sessions under Windows

Keywords:rsa, cryptography

Abstract:A C++ package to perform RSA Public-Key Cryptography

Public Key Cryptography

Public key cryptography is undoubtedly one of the major achievements of applied mathematics in the twentieth century. And the major support for it comes not from any mathematical breakthrough, but from mathematicians' failure to find any efficient solutions to certain problems.

In ordinary cryptography, which is also called single-key cryptography, a single number called the key is used for encryption and decryption. If Alice wants to send a message to Bob, they must first choose a key, which is to remain known only to them. Then Alice uses the key to encrypt the message, and Bob uses the same key to decrypt it. If the encryption method is secure, a third party, Carol, who has access to the encrypted message (and perhaps also to part of the original message) but not the key, cannot reconstruct the original message.

This method is secure if

It is reasonably easy to generate a key.

The key is long enough and random enough so nobody can guess what it is (perhaps by using every conceivable key to decrypt an intercepted message).

The encryption process scrambles the message so thoroughly that the original message cannot be recovered without the key, even if part of the original message is known.

The key is kept secret.

There are many kinds of single-key cryptography. Some are better than others, but they all have one shortcoming. If N persons want to send messages to each other, each pair has to have a key. That's N(N-1) keys in all. If N is large, generating and distributing all these keys can be quite a daunting task.

The concept of public-key cryptography is quite simple. Each person uses two keys, one for encryption and the other for decryption. One of them, which is called the public key, is revealed to the other N-1 persons, perhaps by publishing it in a directory. The other one, called the private key, is kept secret.

A public-key cryptography scheme must have the following features:

It is reasonably easy to generate a pair of keys.

The keys are long enough and random enough so nobody can guess what they are (perhaps by using every conceivable key to decrypt an intercepted message).

The encryption process scrambles the message so thoroughly that the original message cannot be recovered without the key.

It is not feasible to recover the private key if only the public key is known.

The private key is kept secret.

The usual protocol for sending a message from Alice to Bob with public-key cryptography is as follows:

Alice chooses a key for some method of single-key encryption at random. This key is called the session key.

Alice uses Bob's public key to encrypt the session key.

Alice sends the encrypted session key to Bob.

Alice uses the session key to encrypt the message and sends it to Bob.

Bob uses his private key to decrypt the session key.

Bob uses the decrypted session key to decrypt the message.

If all goes well, and Bob's private key has not been compromised, only Bob can read the message. If Carol intercepts the encrypted message, she can determine that Alice sent an encrypted message to Bob, but she cannot reconstruct the original message.

Notice that only Bob is required to have a pair of keys.

Bob, of course, has no assurance that the message came from Alice. To handle this, steps (2) and (5) are modified as follows:

2. Alice uses her private key to encrypt the session key, and then uses Bob's public key to encrypt it again (or vice-versa).

5. Bob uses his private key to decrypt the session key, and then uses Alice's public key to decrypt it again (or vice-versa).

If this protocol is followed, and Alice's private key has not been compromised, only Alice could have sent the message. Of course, this protocol can be used only when both Alice and Bob have pairs of keys.

At this point, most people wonder why Alice doesn't dispense with the session key and just encrypt the message directly with Bob's public key. There are two reasons why she doesn't do this:

Public-key encryption and decryption is much slower than single-key methods. Using the public key to encrypt the entire message would take too long, except for every short messages.

Carol probably knows some of the message. In fact, she may be ignorant of only a small part of the message, such as a credit card number. All she has to do is to use Bob's public key to encrypt all possible messages and compare them to the one she intercepted. When she finds a match, she knows the message.

All cryptographic protocols have weaknesses, and this one is no exception. The process by which Alice generates a "random" session key may not be truly random. In the first protocol, if Carol can restrict the possible session keys to some manageable number, she can use Bob's public key to encrypt every one of them and compare them to the one she intercepted. When she finds a match, she knows the session key and can decrypt the entire message. This is essentially the method that was used in a highly publicized and successful attempt to crack Netscape's encryption.

RSA Cryptography Explained

Let p and q be two different large primes. A large number p can be tested for primeness by applying Fermat's theorem, which states that if p is prime, then

ap-1 == 1 (mod p)

for every positive integer a not divsisible by p. (A double equal sign (==) is used instead of the usual symbol for congruence, which is not supported by all Web browsers.) A number p which passes this test for several hundred randomly selected values of a in the range (1, p-1) is almost surely prime.

Then find two large integers d and e, both less than (p-1)(q-1), such that

de == 1 (mod (p-1)(q-1)).

The easiest way to do this is to choose e at random and use the Euclidean algorithm to find gcd(e, (p-1)(q-1)) and integers d and s such that

de - s(p-1)(q-1) = gcd(e, (p-1)(q-1)).

If the right member is not 1, try again.

The public key is (e, pq) and private key is (d, pq), or vice-versa. The number e or d is called the exponent, and the number pq is called the modulus, for reasons to be made clear later. The modulus pq is published with the public key, but the separate values of p and q must be kept secret. In fact, they are not used for either encryption or decryption and may be discarded.

Let m be a message in the range [0, pq). It is encrypted to c in the range [0, pq) such that:

c == me (mod pq).

Decryption is similar:

m == cd (mod pq).

We must prove that encryption and decryption are inverse operations, i.e., that

(me)d = (md)e = mde == m (mod pq).

Because of the way d and e were constructed,

de = 1 + s(p-1)(q-1)

for some positive integer s.

If p does not divside m, then by Fermat's theorem

mp-1 == 1 (mod p).

Raising both sides to the s(q-1) power and multiplying by m shows that

mde = m1 + s(p-1)(q-1) == m (mod p),

which is obviously also true if p does divside m.

Similarly,

mde == m (mod q).

Hence both p and q divside mde - m. Since p and q are relatively prime, so does pq. Hence

mde == m (mod pq).

The RSA Public-Key Cryptography Package

RSA Public-Key Cryptography needs large integers for reasonable security. The 32-bit or 64-bit integers available on most machines just aren't big enough. Therefore, the RSA Public-Key Cryptography package uses another package, called the Multiple-Precision Unsigned Integer Arithmetic, to do its arithmetic. In this package, the number of bits can be any multiple of 16.

A 512-bit key is considered at least moderately secure; 1024 bits are preferred. The package will, in theory at least, handle any key size which is an even multiple of 16, up to the point where the computer runs out of memory. However, the computations for keys more than 1024 bits long are very slow, even on today's fastest computers.

The package resides in the following files:

EUCLID.CPP

EUCLID.H

MPUINT.CPP

MPUINT.H

RANDOM.CPP

RANDOM.H

RSA.CPP

RSA.H

for your convenience, these files have been combined into a single file RSA.TXT which you can download. Use a text editor to separate the files before compiling them.

When a random number is needed, the package asks the operator to type in a specified number of "random characters". It uses both the characters AND THE TIMES BETWEEN KEYSTROKES to generate a random number. The C library function rand() must NOT be used for this purpose because it produces pseudo-random values that can be reproduced by anyone with the same C compiler. (This function is used to generate test values for the prime test, because these values are not used in the generated keys.)

The random-number generation code is specific to DOS and DOS sessions under Windows.

The following function call generates a key pair. The variables d, e and n must be the same length, which must be an even multiple of 16 bits. One key is (d,n) and the other is (e,n).

GenerateKeys(d, e, n);

mpuint &d;

mpuint &e;

mpuint &n;

It takes several minutes to generate a pair of 512-bit keys, even on a fairly fast computer.

The value of the modulus n is always at least 0x4000..., with enough zeros to fill out all the bits.

The following function call (actually an inline call on a function defined in the Multiple-Precision Unsigned Integer Arithmetic Package) is used to encrypt (or decrypt) a message:

EncryptDecrypt(result, source, e, n);

mpuint &result;

const mpuint &source;

const mpuint &e;

const mpuint &n;

Here e and n are the exponent and modulus, respectively, of the key (either public or private).

The source must be less than the modulus n. If the function GenerateKeys() was used to generate the keys, it is sufficient if the two most significant bits of the source are zero. The result will also be less than the modulus n and can be decrypted without further restriction.

In the communication protocol described above, Alice uses her private key to encrypt the session key, and then uses Bob's public key to encrypt it again (or vice-versa). The order of encryption is important, because in every case the number to be encrypted must be less than the modulus of the key used to encrypt it. The first encryption poses no problem, because session keys are generally much smaller than public keys. However, the encrypted session key may be nearly as large as the modulus, and may be larger than the modulus of the second key. The easiest way to prevent this from happening is to use the key with the smaller modulus first.

The following function, which is used internally by the RSA package to generate random numbers, can also be used to generate a random session key:

Random(x);

mpuint &x;

It will ask the operator to type a specified number of "random characters". If this is not acceptable, you may have to use another method. But make sure the method produces truly random numbers that nobody else will be able to reproduce.

This package is designed to merely illustrate RSA public-key cryptography. Some additional steps are required to make it as secure as it can be. For example, it is desirable to check for "weak keys", special cases in which the product pq can be factored easily.

Reference Site : http://efgh.com/software/rsa.htm

원문 http://blog.naver.com/muse1472.do?Redirect=Log&logNo=120011494664