ABSTRACT
With
the rapid growth of the Internet and E-Commerce, there has come a widespread
need for strong encryption. RSA encryption has helped to fill that need by
providing an easy to understand implementation of public key encryption while
providing security that has stood the test of time.
This
paper deals with the generation of RSA keys and their security. It also touches
on how RSA encryption can be used for digital signatures and the new weaker
restrictions on encryption export to some countries. The paper then goes into
depth on how you can construct short RSA keys while still maintaining security.
These short RSA keys can be used to reduce the overall storage requirements of
keys for a group of users. Short RSA keys can also be used to store publicly
accessible information such as user ID’s, name, address, or any other short piece
of information you wish to be made publicly available.
Keywords
RSA, Public-key encryption, Security, Short RSA keys, Prime Numbers, Digital signatures
1. INTRODUCTION
In
the beginning, encryption started with algorithms that only used one key for
both encryption and decryption or keys where it is easy to derive the
decryption key from the encryption key. This type of encryption is called
conventional or symmetric encryption. Since there is only one key or it is easy
to derive the decryption key from the encryption key, it has the problem that
the key(s) must be distributed by a secure means.
Eventually someone came up with the idea of public key encryption or asymmetric encryption. In public key encryption, the encryption and decryption keys are different, and it is also difficult to obtain the decryption key from the
Permission is granted to make copies of this document for personal or classroom use. Copies are not to be made or distributed for profit or commercial purposes. To copy otherwise, or in any way publish this material, requires written permission.
encryption key. This allows you to make the encryption key (public key) public. This solves the problem of distributing the keys, however public key encryption does need an authentic channel. It needs an authentication channel so that you can ensure that you are encrypting the message with the correct public key. So you can be confident that someone is not trying to trick you into believing they are someone else.
The
RSA encryption algorithm is one implementation of public key encryption. Ronald Rivest, Adi Shamir, and Leonard
Adleman created the mathematical basis for RSA in 1977, and today it is used in
nearly one billion products shipped nationwide [4].
In
this paper I will first explain how to generate public and private keys for RSA
encryption, and how to encrypt and decrypt messages using RSA encryption. Next
I will explain why the RSA algorithm is secure against common security attacks
and how it can be used to digitally sign a document and why that is an
important feature of RSA. Then I will give you a brief update on the state of
the U.S. export restrictions on encryption.
Finally I will explain how you can derive short RSA keys, where you can
specify the first B bits of the public key and still maintain security and why
specifying the first B bits can be important.
2. RSA KEY
GENERATION
In
order to generate keys for RSA encryption you first start with two large prime
numbers p and q. Large usually means that p and q consist of hundreds of digits
[2]. The prime numbers p and q must be large because the security of RSA
encryption depends on not being able to readily factor p*q. Because of the fact
its security depends on not being able to factor p*q, the larger the numbers
are that you choose for p and q, theoretically the more secure the encryption
should be. N is defined to be p*q:
N= p*q
We
also define
T = (p-1)(q-1)
In
this paper I will use the example where p = 5 and q = 7 to help illustrate in
simple terms how RSA encryption works. The p and q are not large primes however
the math is the same for large primes and it is easier to explain using numbers
with fewer digits. Then if we use p = 5 and q = 7 this gives us:
N = 5*7 = 35
T = (5-1)(7-1) = 4*6 = 24.
Next
we must select a number E that has no common divisors with T besides 1.
According to Feil [1], you can usually select a suitable value for E in one or
two trials by blindly choosing a number and testing it to make sure that its
greatest common devisor with T is 1. For our example, we can select E = 11
since 11 and 24 have no common divisors besides 1. Then we find an integer D
such that:
E*D – 1 is divisible by T.
This
can be written as:
E*D = 1 mod T.
In
our example we can select D = 35 because:
11*35 – 1 = 384
384 / 24 = 16
So
11*35 – 1 is divisible by T. I realize that D and N are now equal. D and N are
not required to be equal and it is more secure if they are not equal. However,
it will suffice for our example because I am trying to keep it simple. If we were
to select a number for D that is not equal to N we would have had to select a
larger number. That would complicate the example further and it is easier to
understand with smaller numbers. Now p and q can be destroyed so that no one
inadvertently gets access to them, and D should be kept secret. If someone had
access to D, p and q it would allow him or her to derive the private key and
read any messages meant to only be read by the holder of the private key. The
public key for RSA encryption consists of E and N while the private key
consists of D and N.
To
encrypt a message you first retrieve the public key from the person you wish to
send the message to. Next the message is converted into a string of integers.
The message conversion is done character by character using the character’s
ASCII code for the integer representation of the character. The character(s)
ASCII number(s) can then be concatenated together into one integer. However it
must be assured that the resultant integer is less than N. If it is greater
than N, then you cannot concatenate all the characters together into one
integer. Instead they must be split up into multiple smaller integers denoted
by, m1, m2, … mi, where they are each smaller
than N [2]. Then compute
Ci = Encrypt(mi)
= miE mod N
Where
Ci is the cipher-text (encrypted text) and Encrypt is the public key
function used to encrypt the message. So if the integer representation of our
message in our example is 4 then we compute:
Ci = 4E
mod N
Ci = 411 mod 35
Ci = 4194304 mod 35
Ci = 9
To decrypt the
integer representation of our message the receiver uses his or her private key,
which is defined below:
mi
= Decrypt(Ci) = CiD mod N
Where
mi is the plain-text integer representation of our message and
Decrypt is the private key function used to decrypt the encrypted message Ci.
For our example, the cipher-text (encrypted text) was 9, which can be decrypted
as follows:
mi = 9D mod N
mi = 935 mod 35
mi =
2503155504993241601315571986085849 mod 35
mi = 4
3. RSA SECURITY
Every
encryption algorithm can be cracked, it is just a matter of the amount of time
and computing power it will require. A person can crack RSA encryption by
simply factoring N which will lead to the discovery of the “secret key” [2]. However, if N is sufficiently large 512 bits
to 2048 bits then it is impractical using current technology because of the
amount of computing power and time it would require. It takes at most the
square root of N operations or about 1050 operations to factor a
100-digit number [2]. This is an upper bound on the run time. However, even the
most powerful computers today have difficulty factoring a 512 bit number in a
reasonable amount of time. And factoring a 1024 bit number is computationally
impractical because of the time it would require. However, factoring N is much
more efficient than a brute force attack. A brute force attack by definition
means trying all possible values of D. Since D is at least 100 digits, that
means the work could require you to try up to 10100 different values
for D. It is possible that it would not require 10100 numbers to be
tried. However, probability wise you would on average need to try half of the
possible values before you would randomly select the correct value. Current
computers cannot try that many numbers in a reasonable amount of time; so the
algorithm is secure against a brute force attack. In addition, for a brute
force attack to work, one must be able to recognize the deciphered text if by
chance the correct value for D is tried. Having to be able to recognize the
deciphered text adds another complication to using a brute force attack.
4. DIGITAL
SIGNATURES
A
digital signature is the electronic equivalent of a manual signature on a
document [3]. It can be used to
transmit a statement of acceptance and the sender of the statement can be
verified because only the creator of the private key should have access to that
key. RSA encryption has the property that the normal roles of the public and
private keys can be reversed. Normally the public key is used to encrypt the
document and the private key is used to decrypt the document. Those roles are
reversed when it comes to digital signatures. In order to digitally sign a
document the person first adds some sort of statement of acceptance and then
encrypts that with his or her private key [3]. Because the private key is
private only he or she could have encrypted it. Then if you want the document
to be kept secret except for the desired recipient you must encrypt the
document again with the recipient’s public key. Otherwise since anyone has
access to your public key anyone could use your public key and decrypt the
message and read it. However if it is encrypted again with the receivers public
key, only the intended receiver will be able to read it. This is because only
they have access to their private key. When the recipient receives the document
he or she first decrypts the document with his or her private key. Then the
recipient decrypts the document using the sender’s public key. Since only the sender
could theoretically have access to the sender’s private key, then it can be
assured that the sender actually sent it.
5. EXPORT
REGULATIONS
The
U.S. restriction on encryption export has recently been reduced for certain
nations. On October 19th 2000, the U.S. Department of Commerce,
Bureau of Export Administration amended the Export Administrations Regulations.
It now allows the export of most encryption products to countries in the
European Union and to other trading partner countries such as Australia, Czech
Republic, Hungary, Japan, New Zealand, Norway, Poland, Switzerland, and Canada.
Also there is no longer a rule on the distinction between government and
non-government users for those countries. Restrictions on US citizens exporting
encryption to terrorist supporting or embargoed countries such as Cuba, Iraq,
Iran, Serbia, etc. are unchanged by this amendment. This amendment helps U.S.
companies by allowing them to compete in the encryption business. It makes it
easier for many companies that sell software that contain encryption because
they no longer need to make two versions of their software in order to export
it, unless they intend to export it to nations unaffected by this amendment.
Before this amendment, companies were required to make two versions of their
product, or settle for a version with weaker encryption. Before the amendment
if businesses wanted to sell their product that used strong encryption in the
U.S., and still export it to other countries they would need two versions. They
would need to create a version with strong encryption for sale in the U.S. and
a version with weak encryption for export. This amendment may also make
transactions in the U.S. more secure. This is because some companies before
opted for a single version of their product rather than spending additional
money on two versions. Now those companies may be able to create a single
version with stronger encryption and still be able to export it. So, it may
both benefit U.S. citizens and the citizens of other nations.
6.
SPECIFYING THE FIRST t BITS OF N
By
specifying the first t bits of the RSA encryption key you can reduce the amount
of time it takes to transfer the key for a group of users. It can also reduce
the storage requirements of a group of users by everyone in the group using the
same first t bits for their key. Since everyone in the group would have the
same first t bits, then those t bits would only need to be stored once. Those t bits would also not need to be
transferred to members in the group, because they would already know what the
first t bits are. In addition, the first t bits of data in the key could be
used to store the user ID or other information the user wants made public to
anyone who has access to your public key.
In
this section we have chosen N to be 30 bits so it is easier to explain the
concepts. N is quite small in this case, so you cannot specify very many bits,
and it would not provide much security. However, the same concept can be
applied to an N of arbitrary number of bits, as I will explain later in my
paper. If we let B be a fixed number of length t = 2*k bits and assume B
factors into f1*f2 where f1 and f2
are both k bits [5]. As was explained earlier in the paper, N = p*q. Because we
are working with N = 30 bits this means that p and q can each be 15 bits. When
p and q are multiplied together it results in an N of 30 bits. Then our primes
p and q can be of the form p = 215-k * f1+a1 and
q = 215-k * f2+a2, where a1 and a2
are numbers of length L bits [5]. This shows that p and q are both 15 bits
because the f’s are of length k and so when they are multiplied by 215-k they
yield a result of size 15 bits assuming a1 and a2 are
less than 15 bits (see Figure 1).
As
you can see from Figure 1, f1 is the leftmost or first bits in p and
the a1 bits are on the
right. Then when we multiply p*q together just like we did before to get N it
yields:
N = p*q = 230-2* k*f1*f2+215-k(f1*a2+f2*a1)+a1*a2
If the last two terms
in the sum are less than 30–2*k bits then the first 2*k bits are B
[5]. This is because f1*f2 = 2*k bits and since that
product is multiplied by 230-2*k this means that the product of the
f’s are going to be the first 2*k bits in the string. Of course this assumes
that nothing else is added or multiplied to the string that is large enough to
alter the beginning 2*k bits. To guarantee that the other two terms of the
equation are not large enough to alter the beginning 2*k bits we need to be
sure that:
15-k+k+L+2
< 30 – 2*k or L + 2*k < 13
In other words we
need to be sure that the second half of the equation is less than 30-2*k so it
does not mess with the first 2*k bits which are B.
In order to guarantee
security we need to make sure that given n, f1, and f2 it
is difficult to determine p and q, or essentially a1 and a2,
since a1 and a2 are the only pieces of p and q that are
not known [5]. This requires a1*a2
to be at least 15-k bits. A brute-force attack would require trying all
possible values of a1 and a2, until the corresponding
values of p and q when multiplied together yields N. In order to prevent this
type of attack we require an overlap between a1*a2 and
the 215-k(f1*a2 +f2*a1)
term to be at least 8 bits [5]. The 8 bits is derived from the run time of the
quadratic sieve algorithm which is esqrt(ln(N) * ln(ln(N))). The
quadratic sieve algorithm is an efficient algorithm used to factor numbers. So
if N is 30 in our case then:
esqrt(ln(N)
* ln(ln(N))) » 8
So we need:
2*L
> 15 – k+8 or 2*L+k > 23
The equation makes it
harder to derive a1 and a2 because they are large enough
so that it is more efficient to factor N than to try all possible combinations
of a1 and a2.
The two above
inequalities force the largest possible value for k of 1 bit and so t would be
a maximum of 2 bits. This also gives the maximum value for L to be 11 bits.
What this says is that we can specify the first 2 bits of N while not
compromising the security of our system [5]. So for an example we could specify
f1 = 1 and f2 = 1. The f’s don’t necessarily have to be
equal, it is just a coincidence. That would make B = 1 since B = f1*f2
, B could be our user ID for this example.
7. PRODUCING THE PRIMES
RSA encryption
requires both p and q to be primes. However working with short RSA keys
specifies that p is now of the form of p = 215-k*f1+a1
where f1 is of length k bits and a1 is of length L
bits [5]. Since we specify f1 to be some fixed value that we will
later determine, this means that the only thing we can alter to make p prime is
a1. According to Vanstone in his article on Short RSA Keys we should
choose random L bit numbers and test p = 215-k * f1+a1
to see if it is a prime or not [5]. If its not he says we should “return to choosing
suitable a’s.” However, I believe there is an easier way than choosing random
numbers. For starters you should start with an a1 that makes the
equation for p odd since the only even prime number is 2. Second, if the number
is not prime, instead of choosing another random number I think it would be
more efficient to just increment a1 by 2 and test it again. Doing
this I believe will allow you to find a suitable prime more quickly. This
process should be repeated for q using the equation q = 215-k * f2+a2
however, you should choose a different starting point for a2 to
insure that a1 is not equal to a2. In our example we can
select a1 = 1019:
P
= 215-k * f1+a1
17403
= 215-1 *1+1019
And we can select a2
= 929 which gives us:
q = 215-k *f2+a2
17313 = 215-1 * 1+929
So then our N
becomes:
N = p*q = 230-2* k*f1*f2+215-k(f1*a2+f2*a1)
+ a1*a2
301298139
=
230-2*1*1*1+215-k(1*929+1*1019) +1019*929
Now that we have
determined N we can use it to determine an acceptable E and D using the same methods
in the section on RSA key generation in this paper as we described previously
in this paper.
8. KEYS OF ARBITRARY SIZE
If you want N to be
some size other than 30 bits, say m bits then the following two inequalities
must hold [5]. If p and q are m/2 bits, so that N = p*q gives you a m bit
number, then:
L
+ 2*k < m/2 – 2 and 2*L + k > m/2 + E(N)
E(N) is the number of
bits of overlap that are required so that a brute force attack is less
effective than factoring N. According to Vanstone [5], we should choose E(N) so
that E(N) = esqrt(ln(n)*ln(ln(n))). Then if we use the two above
inequalities, we derive the maximum value that k can be and if we double that
it gives us the maximum size for B. If we plug k back into one of the equations
we can derive L which is the size of a1 and a2. Now we
can derive the primes just as we did before, only now p will be of the form p =
2m/2-k * f1+a1 and q will be q = 2m/2-k
* f2+a2
9. HOW TO CHOOSE B
In the section on
specifying the first t bits of N we specified that B is a number of length 2*k
bits that factors as f1*f2 for k bit numbers f1
and f2 [5]. B must be chosen so that it factors as f1*f2.
If B can be a random number there is no
problem. You just find two random numbers f1 and f2 of
length k bits and multiply them together to get the 2*k bit number B [5]. You
would most likely use a random number for B if you were using short RSA keys in
a group of users to reduce the storage and transfer requirements for the keys.
In this case everyone in the group of users would have the same beginning t
bits in their key. So the first t bits would only need to be stored once. In
addition, the t bits would not need to be transferred to each other user in the
group when retrieving another group users public key.
However, if you
wanted to use the first t bits of N to represent the user ID for the person or
to store some other information you wanted made publicly available finding f1
and f2 gets more difficult. For one reason, what you wish to specify
for B may or may not be the product of two numbers of equal size k bits [5]. We
can overcome this problem by leaving some random bits at the low end of B. By
doing this we can alter those random bits at the low end of B until B does
factor into two numbers of size k bits.
10. CONCLUSION
The vast growth of
the Internet and wireless communications has made a widespread need for secure
encryption. RSA encryption has been around since the 80’s however, it still
continues to be a practical implementation of public key encryption. With the
introduction of techniques such as creating short RSA keys and digital
signatures, the possibilities of what RSA encryption can do for E-Commerce and
other applications has just begun to be explored.
11. REFERENCES
[1] Feil, Todd, RSA Encryption. MapleTech,
Vol. 3, No. 3, 1996, pp. 50-52.
[2] Gove, Ronald A. An Overview of Modern
Cryptography. Information Systems Security. Vol. 16, No. 3, Fall 1997, pp.
55-68.
[3] Preneel, Bart. An Introduction to
Cryptography. Theory and Practice of Informatics. 1998 pp. 204-221.
[4] RSA Security: Behind the Patent. http://www.rsasecurity.com/developers/total-solution/index.html
[5] Vanstone, Stott A. and Zuccherato, Robert J. Short RSA Keys and Their Generation. Journal of Cryptology, Vol. 8, No. 2, Spring 1995, pp. 101-114.