RSA Crypto
In cryptography, RSA is an algorithm for public-key cryptography. It was the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys and the use of up-to-date implementations.
History
The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. Apocryphally , it was invented at a Passover Seder in Schenectady, N.Y.
Clifford Cocks, a British mathematician working for the UK intelligence agency GCHQ, described an equivalent system in an internal document in 1973, but given the relatively expensive computers needed to implement it at the time, it was mostly considered a curiosity and, as far as is publicly known, was never deployed. His discovery, however, was not revealed until 1997 due to its top-secret classification, and Rivest, Shamir, and Adleman devised RSA independently of Cocks' work.
MIT was granted US patent 4405829 for a "Cryptographic communications system and method" that used the algorithm in 1983. The patent expired on 21 September 2000. Since a paper describing the algorithm had been published in August 1977, prior to the December 1977 filing date of the patent application, regulations in much of the rest of the world precluded patents elsewhere and only the US patent was granted. Had Cocks' work been publicly known, a patent in the US would not have been possible either.
Padding schemes
When used in practice, RSA is generally combined with some padding scheme. The goal of the padding scheme is to prevent a number of attacks that potentially work against RSA without padding:
When encrypting with low encryption exponents (e.g., e = 3) and small values of the m, (i.e. m Because RSA encryption is a deterministic encryption algorithm – i.e., has no random component – an attacker can successfully launch a chosen plaintext attack against the cryptosystem, by encrypting likely plaintexts under the public key and test if they are equal to the ciphertext. A cryptosystem is called semantically secure if an attacker cannot distinguish two encryptions from each other even if the attacker knows (or has chosen) the corresponding plaintexts. As described above, RSA without padding is not semantically secure. RSA has the property that the product of two ciphertexts is equal to the encryption of the product of the respective plaintexts. That is Because of this multiplicatvive property a chosen-ciphertext attack is possible. E.g. an attacker, who wants to know the decryption of a ciphertext c=me mod n may ask the holder of the secret key to decrypt an unsuspiciously looking ciphertext cremod n for some value r chosen by the attacker. Because of the multiplicative property this is the encryption of mrmod n. Hence, if the attacker is successful with the attack, he will learn mrmod n from which he can derive the message m by multiplying mr with the modular inverse of r modulo n. To avoid these problems, practical RSA implementations typically embed some form of structured, randomized padding into the value m before encrypting it. This padding ensures that m does not fall into the range of insecure plaintexts, and that a given message, once padded, will encrypt to one of a large number of different possible ciphertexts. Standards such as PKCS have been carefully designed to securely pad messages prior to RSA encryption. Because these schemes pad the plaintext m with some number of additional bits, the size of the un-padded message M must be somewhat smaller. RSA padding schemes must be carefully designed so as to prevent sophisticated attacks which may be facilitated by a predictable message structure. Early versions of the PKCS standard (i.e. PKCS #1 up to version 1.5) used a construction that turned RSA into a semantically secure encryption scheme. This version was later found vulnerable to a practical adaptive chosen ciphertext attack. Later versions of the standard include Optimal Asymmetric Encryption Padding (OAEP), which prevents these attacks. The PKCS standard also incorporates processing schemes designed to provide additional security for RSA signatures, e.g., the Probabilistic Signature Scheme for RSA (RSA-PSS). Signing messages Suppose Alice uses Bob's public key to send him an encrypted message. In the message, she can claim to be Alice but Bob has no way of verifying that the message was actually from Alice since anyone can use Bob's public key to send him encrypted messages. So, in order to verify the origin of a message, RSA can also be used to sign a message. Suppose Alice wishes to send a signed message to Bob. She produces a hash value of the message, raises it to the power of d mod n (as she does when decrypting a message), and attaches it as a "signature" to the message. When Bob receives the signed message, he raises the signature to the power of e mod n (as he does when encrypting a message), and compares the resulting hash value with the message's actual hash value. If the two agree, he knows that the author of the message was in possession of Alice's secret key, and that the message has not been tampered with since. Note that secure padding schemes such as RSA-PSS are as essential for the security of message signing as they are for message encryption, and that the same key should never be used for both encryption and signing purposes. Security The security of the RSA cryptosystem is based on two mathematical problems: the problem of factoring large numbers and the RSA problem. Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems are hard, i.e., no efficient algorithm exists for solving them. Providing security against partial decryption may require the addition of a secure padding scheme. The RSA problem is defined as the task of taking eth roots modulo a composite n: recovering a value m such that c=me mod n, where (e, n) is an RSA public key and c is an RSA ciphertext. Currently the most promising approach to solving the RSA problem is to factor the modulus n. With the ability to recover prime factors, an attacker can compute the secret exponent d from a public key (e, n), then decrypt c using the standard procedure. To accomplish this, an attacker factors n into p and q, and computes (p-1)(q-1) which allows the determination of d from e. No polynomial-time method for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists. See integer factorization for a discussion of this problem. As of 2005, the largest number factored by a general-purpose factoring algorithm was 663 bits long, using a state-of-the-art distributed implementation. RSA keys are typically 1024–2048 bits long. Some experts believe that 1024-bit keys may become breakable in the near term (though this is disputed); few see any way that 4096-bit keys could be broken in the foreseeable future. Therefore, it is generally presumed that RSA is secure if n is sufficiently large. If n is 256 bits or shorter, it can be factored in a few hours on a personal computer, using software already freely available. If n is 512 bits or shorter, it can be factored by several hundred computers as of 1999. A theoretical hardware device named TWIRL and described by Shamir and Tromer in 2003 called into question the security of 1024 bit keys. It is currently recommended that n be at least 2048 bits long. In 1994, Peter Shor published Shor's algorithm, showing that a quantum computer could in principle perform the factorization in polynomial time. However, quantum computation is still in the early stages of development and may never prove to be practical. Key generation Finding the large primes p and q is usually done by testing random numbers of the right size with probabilistic primality tests which quickly eliminate virtually all non-primes. p and q should not be 'too close', lest the Fermat factorization for n be successful, if p-q, for instance is less than 2n1/4 (which for even small 1024-bit values of n is 3x1077) solving for p and q is ultra-trivial. Furthermore, if either p-1 or q-1 has only small prime factors, n can be factored quickly by Pollard's p-1 algorithm, and these values of p or q should therefore be discarded as well. One should not employ a prime search method which gives any information whatsoever about the primes to the attacker. In particular, a good random number generator for the start value needs to be employed. Note that the requirement here is both 'random' and 'unpredictable'. These are not the same criteria; a number may have been chosen by a random process (i.e., no pattern in the results), but if it is predictable in any manner (or even partially predictable), the method used will result in loss of security. For example, the random number table published by the Rand Corp in the 1950s might very well be truly random, but it has been published and thus can serve an attacker as well. If the attacker can guess half of the digits of p or q, he can quickly compute the other half (shown by Coppersmith in 1997). It is important that the secret key d be large enough. Michael J. Wiener showed in 1990 that if p is between q and 2q (which is quite typical) and d < n1/4/3, then d can be computed efficiently from n and e. There is no known attack against small public exponents such as e=3, provided that proper padding is used. However, when no padding is used or when the padding is improperly implemented then small public exponents have a greater risk of leading to an attack, such as for example the unpadded plaintext vulnerability listed above. 65537 is a commonly used value for e. This value can be regarded as a compromise between avoiding potential small exponent attacks and still allowing efficient encryptions (or signature verification). The NIST draft FIPS PUB 186-3 (March 2006) does not allow public exponents e smaller than 65537, but does not state a reason for this restriction. Speed RSA is much slower than DES and other symmetric cryptosystems. In practice, Bob typically encrypts a secret message with a symmetric algorithm, encrypts the (comparatively short) symmetric key with RSA, and transmits both the RSA-encrypted symmetric key and the symmetrically-encrypted message to Alice. This procedure raises additional security issues. For instance, it is of utmost importance to use a strong random number generator for the symmetric key, because otherwise Eve (an eavesdropper wanting to see what was sent) could bypass RSA by guessing the symmetric key. Key distribution As with all ciphers, how RSA public keys are distributed is important to security. Key distribution must be secured against a man-in-the-middle attack. Suppose Eve has some way to give Bob arbitrary keys and make him believe they belong to Alice. Suppose further that Eve can intercept transmissions between Alice and Bob. Eve sends Bob her own public key, which Bob believes to be Alice's. Eve can then intercept any ciphertext sent by Bob, decrypt it with her own secret key, keep a copy of the message, encrypt the message with Alice's public key, and send the new ciphertext to Alice. In principle, neither Alice nor Bob would be able to detect Eve's presence. Defenses against such attacks are often based on digital certificates or other components of a public key infrastructure. Timing attacks Kocher described a new attack on RSA in 1995: if the attacker Eve knows Alice's hardware in sufficient detail and is able to measure the decryption times for several known ciphertexts, she can deduce the decryption key d quickly. This attack can also be applied against the RSA signature scheme. In 2003, Boneh and Brumley demonstrated a more practical attack capable of recovering RSA factorizations over a network connection (e.g., from a Secure Socket Layer (SSL)-enabled webserver). This attack takes advantage of information leaked by the Chinese remainder theorem optimization used by many RSA implementations. One way to thwart these attacks is to ensure that the decryption operation takes a constant amount of time for every ciphertext. However, this approach can significantly reduce performance. Instead, most RSA implementations use an alternate technique known as cryptographic blinding. RSA blinding makes use of the multiplicative property of RSA. Instead of computing cd mod n, Alice first chooses a secret random value r and computes (rec)d mod n. The result of this computation is r m mod n and so the effect of r can be removed by multiplying by its inverse. A new value of r is chosen for each ciphertext. With blinding applied, the decryption time is no longer correlated to the value of the input ciphertext and so the timing attack fails. Adaptive chosen ciphertext attacks In 1998, Daniel Bleichenbacher described the first practical adaptive chosen ciphertext attack, against RSA-encrypted messages using the PKCS #1 v1 padding scheme (a padding scheme randomizes and adds structure to an RSA-encrypted message, so it is possible to determine whether a decrypted message is valid.) Due to flaws with the PKCS #1 scheme, Bleichenbacher was able to mount a practical attack against RSA implementations of the Secure Socket Layer protocol, and to recover session keys. As a result of this work, cryptographers now recommend the use of provably secure padding schemes such as Optimal Asymmetric Encryption Padding, and RSA Laboratories has released new versions of PKCS #1 that are not vulnerable to these attacks. Branch Prediction Analysis (BPA) attacks Many processors use a Branch predictor to determine whether a conditional branch in the instruction flow of a program is likely to be taken or not. Usually these processors also implement Simultaneous multithreading (SMT). Branch Prediction Analysis attacks use a spy process to discover (statistically) the private key when processed with these processors. Simple Branch Prediction Analysis (SBPA) claims to improve BPA in a non-statistical way. In their paper, "On the Power of Simple Branch Prediction Analysis", the authors of SBPA (Onur Aciicmez, Cetin Kaya Koc and Jean-Pierre Seifert) claim to have discovered 508 out of 512 bits of an RSA key in 10 iterations. The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977 [RIVE78]. The basic technique was first discovered in 1973 by Clifford Cocks [COCK73] of CESG (part of the British GCHQ) but this was a secret until 1997 - see The History of ID-PKC.
The RSA algorithm can be used for both public key encryption and digital signatures. Its security is based on the difficulty of factoring large integers.
Key Generation Algorithm Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length, e.g. 1024 bits. [See note 1].
Compute n = pq and (?) phi = (p-1)(q-1). Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1. [See note 2]. Compute the secret exponent d, 1 < d < phi, such that
ed ? 1 (mod phi). [See note 3]. The public key is (n, e) and the private key is (n, d). The values of p, q, and phi should also be kept secret. n is known as the modulus. e is known as the public exponent or encryption exponent. d is known as the secret exponent or decryption exponent. Encryption Sender A does the following:-
Obtains the recipient B's public key (n, e). Represents the plaintext message as a positive integer m [see note 4].
Computes the ciphertext c = m^e mod n. Sends the ciphertext c to B. Decryption Recipient B does the following:-
Uses his private key (n, d) to compute m = c^d mod n. Extracts the plaintext from the integer representative m. Digital signing Sender A does the following:-
Creates a message digest of the information to be sent. Represents this digest as an integer m between 0 and n-1. [See note 5]. Uses her private key (n, d) to compute the signature s = m^d mod n. Sends this signature s to the recipient, B. Signature verification Recipient B does the following:-
Uses sender A's public key (n, e) to compute integer v = s^e mod n. Extracts the message digest from this integer. Independently computes the message digest of the information that has been signed. If both message digests are identical, the signature is valid. Notes on practical applications To generate the primes p and q, generate a random number of bit length b/2 where b is the required bit length of n; set the low bit (this ensures the number is odd) and set the two highest bits (this ensures that the high bit of n is also set); check if prime (use the Rabin-Miller test); if not, increment the number by two and check again. This is p. Repeat for q starting with an integer of length b-b/2. If p To compute the value for d, use the Extended Euclidean Algorithm to calculate d = e^-1 mod phi (this is known as modular inversion).
When representing the plaintext octets as the representative integer m, it is usual to add random padding characters to make the size of the integer m large and less susceptible to certain types of attack. If m = 0 or 1 there is no security as the ciphertext has the same value. For more details on how to represent the plaintext octets as a suitable representative integer m, see [PKCS1]. It is important to make sure that m < n otherwise the algorithm will fail. This is usually done by making sure the first octet of m is equal to 0x00.
Decryption and signing are identical as far as the mathematics is concerned as both use the private key. Similarly, encryption and verification both use the same mathematical operation with the public key. That is, mathematically,
m = (m^e mod n)^d mod n = (m^d mod n)^e mod n, m < n However, note these important differences in implementation:-
The signature is derived from a message digest of the original information. The recipient will need to follow exactly the same process to derive the message digest, using an identical set of data.
The recommended methods for deriving the representative integers are different for encryption and signing (encryption involves random padding, but signing uses the same padding each time). Summary of RSA Computational Efficiency and the Chinese Remainder Theorem (CRT) Key generation is only carried out occasionally and so computational efficiency is less of an issue.
The calculation a = b^e mod n is known as modular exponentiation and one efficient method to carry this out on a computer is the binary left-to-right method. To solve y = x^e mod n let e be represented in base 2 as
e = e(k-1)e(k-2)...e(1)e(0) where e(k-1) is the most significant non-zero bit and bit e(0) the least. set y = x for bit j = k - 2 downto 0 beginSources
RSA Algorithm
end
return y
The time to carry out modular exponentation increases with the number of bits set to one in the exponent e. For encryption, an appropriate choice of e can reduce the computational effort required to carry out the computation of c = m^e mod n. Popular choices like 3, 17 and 65537 are all primes with only two bits set: 3 = 0011'B, 17 = 0x11, 65537 = 0x10001.
The bits in the decryption exponent d, however, will not be so convenient and so decryption using the standard method of modular exponentiation will take longer than encryption. An alternative method of representing the private key uses the Chinese Remainder Theorem (CRT). The private key is represented as a quintuple (p, q, dP, dQ, and qInv), where p and q are prime factors of n, dP and dQ are known as the CRT exponents, and qInv is the CRT coefficient. The CRT method of decryption is four times faster overall than calculating m = c^d mod n. For more details, see [PKCS1]. The extra values for the private key are:-
dP = (1/e) mod (p-1)
dQ = (1/e) mod (q-1)
qInv = (1/q) mod p where p > q
These are pre-computed and saved along with p and q as the private key. To compute the message m given c do the following:-
m1 = c^dP mod p
m2 = c^dQ mod q
h = qInv(m1 - m2) mod p
m = m2 + hq
Even though there are more steps in this procedure, the modular exponentation to be carried out uses much shorter exponents and so it is less expensive overall.
Theory and proof of the RSA algorithm
Every man and his dog seems to have a proof of the RSA algorithm out there, all requiring varying degrees of understanding of number theory. This is our version of a proof of the RSA algorithm, re-written October 2006 (PDF version) and some hints on understanding it.
A very simple example of RSA encryption
This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 can probably even do it by hand on paper).
Select primes p=11, q=3.
n = pq = 11.3 = 33
phi = (p-1)(q-1) = 10.2 = 20
Choose e=3
Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
and check gcd(e, q-1) = gcd(3, 2) = 1
therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
Compute d such that ed ? 1 (mod phi)
i.e. compute d = e^-1 mod phi = 3^-1 mod 20
i.e. find a value for d such that phi divides (ed-1)
i.e. find d such that 20 divides 3d-1.
Simple testing (d = 1, 2, ...) gives d = 7
Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.
Public key = (n, e) = (33, 3)
Private key = (n, d) = (33, 7).
This is actually the smallest possible value for the modulus n for which the RSA algorithm works.
Now say we want to encrypt the message m = 7,
c = m^e mod n = 7^3 mod 33 = 343 mod 33 = 13.
Hence the ciphertext c = 13.
To check decryption we compute
m' = c^d mod n = 13^7 mod 33 = 7.
Note that we don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that a = bc mod n = (b mod n).(c mod n) mod n so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value.
One way of calculating m' is as follows:-
m' = 13^7 mod 33 = 13^(3+3+1) mod 33 = 13^3.13^3.13 mod 33
= (13^3 mod 33).(13^3 mod 33).(13 mod 33) mod 33
= (2197 mod 33).(2197 mod 33).(13 mod 33) mod 33
= 19.19.13 mod 33 = 4693 mod 33
= 7.
Now if we calculate the ciphertext c for all the possible values of m (0 to 32), we get
m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
c 0 1 8 27 31 26 18 13 17 3 10 11 12 19 5 9 4
m 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
c 29 24 28 14 21 22 23 30 16 20 15 7 2 6 25 32
Note that all 33 values of m (0 to 32) map to a unique code c in the same range in a sort of random manner. In this case we have nine values of m that map to the same value of c - these are known as unconcealed messages. m = 0 and 1 will always do this for any N, no matter how large. But in practice, higher values shouldn't be a problem when we use large values for N.
If we wanted to use this system to keep secrets, we could let A=2, B=3, ..., Z=27. (We specifically avoid 0 and 1 here for the reason given above). Thus the plaintext message "HELLOWORLD" would be represented by the set of integers m1, m2, ...
{9,6,13,13,16,24,16,19,13,5}
Using our table above, we obtain ciphertext integers c1, c2, ...
{3,18,19,19,4,30,4,28,19,26}
Note that this example is no more secure than using a simple Caesar substitution cipher, but it serves to illustrate a simple example of the mechanics of RSA encryption.
Remember that calculating m^e mod n is easy, but calculating the inverse c^-e mod n is very difficult, well, for large n's anyway. However, if we can factor n into its prime factors p and q, the solution becomes easy again, even for large n's. Obviously, if we can get hold of the secret exponent d, the solution is easy, too.
A slightly less simple example of the RSA algorithm
This time, to make life slightly less easy for those who can crack simple Caesar substitution codes, we will group the characters into blocks of three and compute a message representative integer for each block.
ATTACKxATxSEVEN = ATT ACK XAT XSE VEN
In the same way that a decimal number can be represented as the sum of powers of ten, e.g.
135 = 1 x 10^2 + 3 x 10^1 + 5,
we could represent our blocks of three characters in base 26 using A=0, B=1, C=2, ..., Z=25
ATT = 0 x 26^2 + 19 x 26^1 + 19 = 513
ACK = 0 x 26^2 + 2 x 26^1 + 10 = 62
XAT = 23 x 26^2 + 0 x 26^1 + 19 = 15567
XSE = 23 x 26^2 + 18 x 26^1 + 4 = 16020
VEN = 21 x 26^2 + 4 x 26^1 + 13 = 14313
For this example, to keep things simple, we'll not worry about numbers and punctuation characters, or what happens with groups AAA or AAB.
In this system of encoding, the maximum value of a group (ZZZ) would be 26^3-1 = 17575, so we require a modulus n greater than this value.
We "generate" primes p=137 and q=131 (we cheat by looking for suitable primes around ?n)
n = pq = 137.131 = 17947
phi = (p-1)(q-1) = 136.130 = 17680
Select e = 3
check gcd(e, p-1) = gcd(3, 136) = 1, OK and
check gcd(e, q-1) = gcd(3, 130) = 1, OK.
Compute d = e^-1 mod phi = 3^-1 mod 17680 = 11787.
Hence public key, (n, e) = (17947, 3) and private key (n, d) = (17947, 11787).
Question: Why couldn't we use e=17 here?
To encrypt the first integer that represents "ATT", we have
c = m^e mod n = 513^3 mod 17947 = 8363.
We can verify that our private key is valid by decrypting
m' = c^d mod n = 8363^11787 mod 17947 = 513.
Overall, our plaintext is represented by the set of integers m
{513, 62, 15567, 16020, 14313}
We compute corresponding ciphertext integers c = m^e mod n, (which is still possible by using a calculator)
{8363, 5017, 11884, 9546, 13366}
You are welcome to compute the inverse of these ciphertext integers using m = c^d mod n to verify that the RSA algorithm still holds. However, this is now outside the realms of hand calculations unless you are very patient.
To help you carry out these modular arithmetic calculations, download our free modular arithmetic command line programs.
Note that this is still a very insecure example. Starting with the knowledge that the modulus 17947 is probably derived from two prime numbers close to its square root, a little testing of suitable candidates from a table of prime numbers would get you the answer pretty quickly. Or just work methodically through the table of prime numbers dividing n by each value until you get no remainder. You could also write a simple computer program to factor n that just divides by every odd number starting from 3 until it reaches a number greater than the square root of n.
A real example
In practice, we don't have a series of small integers to encrypt like we had in the above examples, we just have one big one. Also, rather than trying to represent the plaintext as an integer directly, we generate a random session key and use that to encrypt the plaintext with a conventional, much faster symmetrical algorithm like Triple DES. We then use the much slower public key encryption algorithm to encrypt just the session key.
The sender A then transmits a message to the recipient B in a format something like this:-
Encrypted session key = xxxx
Plaintext encrypted with session key = xxxxxxxxxxxxxxxxx
The recipient B would extract the encrypted session key and use his private key (n,d) to decrypt it. He would then use this session key with a conventional symmetrical decryption algorithm to decrypt the actual message. Typically the transmission would include in plaintext details of the encryption algorithms used, padding and encoding methods, initialisation vectors and other details required by the recipient. The only secret required to be kept, as always, should be the keys.
If Mallory intercepts the transmission, he can either try and crack the conventionally-encrypted plaintext directly, or he can try and decrypt the encryped session key and then use that in turn. Obviously, this system is as strong as its weakest link.
Key length
The key length for a secure RSA transmission is typically 1024 bits. 512 bits is now no longer considered secure. For more security or if you are paranoid, use 2048 or even 4096 bits. With the faster computers available today, the time taken to encrypt and decrypt even with a 4096-bit modulus really isn't an issue anymore. In practice, it is still effectively impossible for you or I to crack a message encrypted with a 512-bit key. An organisation like the NSA who has the latest supercomputers can probably crack it by brute force in a reasonable time, if they choose to put their resources to work on it. The longer your information is needed to be kept secure, the longer the key you should use. Keep up to date with the latest recommendations in the security journals.
No one is going to criticise you for using a key that is too long provided your software still performs adequately. However, in our opinion, the biggest danger in using a key that is too large is the false sense of security it provides to the implementers and users. "Oh, we have 4096-bit security in our system" may sound impressive in a marketing blurb, but the fact that your private key is not adequately protected or your random number generator is not random may mean that the total security is next to useless.
If we are encrypting the plaintext with a conventional symmetrical algorithm like DES, our session key is going to be 64 bits long. Triple DES will need 192 bits, and AES will need up to 256 bits. That gives us lots of security. Unlike our simple examples above where we had to deal with a series of integers, to encrypt a 256-bit key with a 1024-bit RSA modulus means we only need a single representative message integer. In fact, you need to pad the 256 bits to ensure that we have a large enough integer before we encrypt it with RSA. 1024 bits is 128 bytes long, so we have quite a handful of data to deal with.
Recommended Techniques
[PKCS1] describes the latest recommended techniques to encode the plaintext octets using RSA. Again, in our opinion, you and I will have perfectly adequate security using the older version 1.5 encoding techniques. If you are encrypting state secrets or bank codes for millions of dollars you should be following the latest recommendations.
ANSI standard X9.31 [AX931] recommends using strong primes and other restrictions on p and q to minimise the possibility of known techniques being used against the algorithm. There is much argument about this topic. It is probably better just to use a longer key length.
There is an excellent paper by Burt Kalinski of RSA Laboratories written in the early 1990s [KALI93] that describes in great detail everything you need to know about encrypting and encoding using RSA. There are full examples right down to listing out the bytes. OK, it uses MD2 and a 508-bit modulus and obviously doesn't deal with refinements built up over the last decade to deal with more subtle security threats, but it's an excellent introduction.
Implementation in C and VB
We use an example implementation of the RSA algorithm in C in our BigDigits package. It's not the most efficient way, nor is it cryptographically secure, but it shows the maths involved. See the BigDigits Test Functions.
There is an example in VB6/VBA code at RSA and Diffie-Hellman in Visual Basic.
For a professional implementation, see our CryptoSys PKI Toolkit which can be used with Visual Basic, VBA and C/C++ applications. There are examples using the `raw' RSA functions to carry out RSA Encryption and RSA Signing.
How the RSA Cipher Works
-
Table of Contents
- Preface: What is This?
- Introduction: The Idea of a Trapdoor Function
- Background, Part I: How to Calculate with Exponents
- Background, Part II: Modulus Arithmetic
- Background, Part III: The Fundamental Theorem of Arithmetic
- Background, Part IV: Relatively Prime Numbers
- Euler's Totient Function
- Euler's Totient Theorem
- Variations on a Theme
- The Plot Thickens
- Does This Really Work?
- Making a Pair of Keys
- An Example
- How to Crack RSA
- How to Make RSA Uncrackable
- Huge Exponents in Modulus Arithmetic
- Huge Factors in Modulus Arithmetic
- Safety in Numbers
- Summing Up
- References
Preface: What is This?
The RSA cipher is a fascinating example of how some of the most abstract mathematical subjects find applications in the real world. Few are the mathematicians who study creatures like the prime numbers with the hope or even desire for their discoveries to be useful outside of their own domain. But every now and then that is exactly what happens.
This text explains the mathematics behind RSA -- how and why it works. The intended audience is just about anyone who is interested in the topic and who can remember a few basic facts from algebra: what a variable is, the difference between a prime number and a composite number, and the like.
The most important mathematical facts necessary for understanding RSA's foundations are reviewed near the beginning. Even if you are familiar with everything covered in these sections, I would recommend that you at least skim through them.
In one or two places, I have specifically targeted an explanation to what I consider to be the average computer programmer, leveraging analogous concepts in programming and general mathematics.
Before getting started, I should make some observations on the mathematical notation used here.
For the most part, where notations for the same idea differ between standard mathematics and the common practices among computer programmers, I have stuck with the mathematicians. This is, after all, a mathematical subject. However, I have deviated in a few places where there was too much opportunity for confusion. I have used * to denote multiplication, and have completely avoided "implied" multiplication (i.e., using PQ as shorthand for P * Q). Since not all web browsers can display superscripts, I have used ^ to denote exponentiation. (This necessitates more parenthesizing than would normally be used.) The mathematician's three-bar congruency symbol is not available, so I have made do with = instead. Variables are always named with a single capital letter.
Finally, please note that throughout the text I use the word
Introduction: The Idea of a Trapdoor Function
What a mathematician refers to as a
| F(X) = 7 * X + 43. |
If X happens to be 3, then F(X) will be 64. So, "F(3)" is shorthand for "7 * 3 + 43".
The same function in a C program might look like:
int F(int x)
{
return 7 * x + 43;
}
Of course, in a computer program, functions are used to encapsulate all kinds of algorithms, and frequently make use of external variables and the like. In mathematics, however, a function is used solely for the number it returns. And, given a certain number as input, they will always return the same output. (Thus, rand() would not qualify as a mathematical function, unless it were written so that the seed value was passed in as an input parameter.)
Mathematicians often consider how to construct a function's
| G(X) = (X - 43) / 7. |
G(64) is equal to 3, and in general, G(F(X)) is equal to X. Therefore, G is F's inverse. Not all functions are invertible, of course. Clearly, the function:
| F(X) = X * 0 |
cannot be inverted. (Because how could G(F(X)) return X when F(X) is always zero?)
Usually, when you have a mathematical function for which an inverse does exist, constructing it is not too difficult. In fact, it is often transparent. Typically, you can just run through the steps backwards, subtracting where the original function adds, and so on. But can it be done for every invertible function?
To put the question in terms of programming, imagine that there are two functions:
int foo(int x);
int bar(int x);
foo() and bar() work like mathematical functions -- they do nothing but compute a return value, and given the same number for input, they will always produce the same output. (And pretend for the moment that this is on a machine where integers can be arbitrarily large.) Suppose you are told that bar() is the inverse of foo(). The statement:
x == bar(foo(x))
is always true, as long as x meets foo()'s requirements for a valid argument.
Now, imagine that you have the source code for foo(), but not for bar(). Can you write your own replacement for bar(), just by examining foo()?
It seems that you ought to be able to. There are no secrets as to what foo() does, after all. You can run foo() with different inputs as many times as you like. You already know that bar() exists, somewhere, so you know that it is possible to write. Is it guaranteed that you can reconstruct it?
Theoretically speaking, the answer is yes. Given such an function, it is always possible to construct its inverse. However, if we also throw in the tiny constraint that you have to finish before the heat-death of the universe, the answer subtly changes.
There are some special functions that, though what they do is simple
enough, and how they do what they do is utterly transparent, figuring
out how to undo what they do is a diabolical task. Such a creature is
a
In 1975, Whitfield Diffie, Martin E. Hellman, and Ralph Merkle realized that a trapdoor function could be the basis for an entirely new kind of cipher -- one in which the decoding method could remain secret even when the encoding method was public knowledge. Diffie and Hellman published a paper in 1976 that described this idea, and offered some examples of weak trapdoor functions. And in 1977, Ronald L. Rivest, Adi Shamir, and Leonard Adleman outlined, in an MIT technical memo, an excellent candidate that became the basis for the RSA cipher.
What follows is a description of that function.
Background, Part I: How to Calculate with Exponents
Here's a quick refresher on how to combine exponents. Recall that:
| N^2 | = N * N, | |
| N^3 | = N * N * N, | |
| N^4 | = N * N * N * N, |
and so on. For example:
| 2^7 = 2 * 2 * 2 * 2 * 2 * 2 * 2 = 128. |
If we fiddle with exponents for a bit, we will quickly realize that:
| N^E * N = N^(E + 1). |
So, for example:
| 2^7 * 2 = 128 * 2 = 256 = 2^8. |
Building upon this, we can also see that:
| N^E * N * N = N^(E + 2). |
But N * N can also be written as N^2:
| N^E * N^2 = N^(E + 2). |
We can extrapolate from this, and derive a more general rule -- namely:
| N^A * N^B = N^(A + B). |
And, if we repeated this process on the next level up, we would find that:
| (N^A)^B = N^(A * B). |
These two simple facts are very useful when handling exponent-laden formulas.
Background, Part II: Modulus Arithmetic
Most computer programmers are familiar with modulus as a "remainder" operator, usually denoted by "%", which gives the remainder of an integer division instead of the quotient. For example:
| 27 % 12 = 3. |
Though the idea is the same, the mechanics here are slightly different
from what mathematicians refer to as
| 27 = 3 (mod 12), |
or, in words:
| 27 is congruent to 3, modulo 12. |
(Though note that mathematicians actually use a three-barred version
of the equal sign to indicate congruency.) In this case, 12 is the
| 11 + 16 = 3 (mod 12) |
reads as:
| 11 plus 16 is congruent to 3, modulo 12. |
Modulus arithmetic is sometimes called
An important feature of modulus arithmetic is that you can replace the terms of an addition operation with congruent values, and still get the right answer:
| 16 = 4 (mod 12), therefore | |
| 11 + 16 = 11 + 4 = 3 (mod 12). |
Another example:
| 9835 = 7 (mod 12), and | |
| 1176 = 0 (mod 12), therefore | |
| 9835 + 1176 = 7 + 0 = 7 (mod 12). |
Even better, this trick also works with multiplication:
| 9835 * 1176 = 7 * 0 = 0 (mod 12) |
(and, if we check, we will see that, yes, 9835 * 1176 is 11565960, and 11565960 = 0 (mod 12)).
If our modulus was 10, then modulus arithmetic would be equivalent to ignoring all but the last digit in our numbers:
| 37 = 7 (mod 10), | |
| 287 + 482 = 9 (mod 10), and | |
| 895 * 9836 = 0 (mod 10). |
And, in a sense, a C program does all of its calculations in modulus arithmetic. Since integer calculations in C are permitted to overflow, the high bits silently falling off into the bit bucket, a C program using 32-bit integers is really doing all of its arithmetic modulo 2^32.
As you might imagine, some calculations that are time-consuming and produce huge numbers become trivial in modulus arithmetic. The ability to reduce values to their remainders before doing the actual calculation keeps the calculations from getting out of hand.
Background, Part III: The Fundamental Theorem of Arithmetic
The
| 1176 = 2 * 2 * 2 * 3 * 7 * 7, or | |
| 1176 = 2^3 * 3^1 * 7^2. |
It is guaranteed that there is no other way to break 1176 into prime factors. And, certainly, any time you take three 2s, two 7s, and a three, you're always going to get 1176 when you multiply them together. The Fundamental Theorem of Arithmetic assures us that both these things are true for every number.
(By the way, this is one of the reasons that 1 is not considered to be a prime number: if it were, then each number would have an infinite number of prime factorizations, all differing by how many 1s were included. Instead, 1 is considered to have no prime factors at all, and we say that a number is prime if it has exactly one prime factor -- namely itself.)
Put another way, the Fundamental Theorem of Arithmetic states that the set of all numbers and the set of all selections of prime numbers are "isomorphic" -- there is a perfect one-to-one mapping between the two. A number is therefore defined by its prime factorization.
Background, Part IV: Relatively Prime Numbers
The
| GCD(15, 10) = 5, | |
| GCD(18, 10) = 2, | |
| GCD(21, 10) = 1, and | |
| GCD(170, 102) = 34. |
Or, another way to look at it is to say that the GCD is the intersection of the two numbers' set of prime factors:
| GCD((2^3 * 3^1 * 7^2), (2^2 * 5^1 * 7^3)) = 2^2 * 7^2, so | |
| GCD(1176, 6860) = 196. |
When two numbers have no common factors, their GCD will be 1, and the
two numbers are said to be
Since a prime number has no factors besides itself, clearly a prime number is relatively prime to every other number (except for multiples of itself). And the same can be said of the number 1.
Okay. Enough background material. Let's get to the good stuff.
Euler's Totient Function
phi(N) = how many numbers between 1 and N - 1 which are relatively prime to N.
Thus:
| phi(4) | = 2 | (1 and 3 are relatively prime to 4), | |
| phi(5) | = 4 | (1, 2, 3, and 4 are relatively prime to 5), | |
| phi(6) | = 2 | (1 and 5 are relatively prime to 6), | |
| phi(7) | = 6 | (1, 2, 3, 4, 5, and 6 are relatively prime to 7), | |
| phi(8) | = 4 | (1, 3, 5, and 7 are relatively prime to 8), and | |
| phi(9) | = 6 | (1, 2, 4, 5, 7, and 8 are relatively prime to 9). |
Here is the same definition expressed as C code:
phi = 1;
for (i = 2 ; i < N ; ++i)
if (gcd(i, N) == 1)
++phi;
(By the way, notice that phi(1) is specially defined to be 1.)
It should be easy to see that phi(N) will be N - 1 whenever N is prime. Somewhat less obvious is the useful fact that phi(N) is also easy to calculate when N has exactly two different prime factors:
| phi(P * Q) = (P - 1) * (Q - 1), if P and Q are prime. |
(The proof of this fact is left as an exercise for the reader. It's actually not too hard.) Thus, for example:
| phi(15) = 2 * 4 = 8 | (1, 2, 4, 7, 8, 11, 13, and 14). |
The two prime factors cannot be the same number for this to work, and in fact you can see above that phi(9) does not equal 4.
Euler's Totient Theorem
This theorem is one of the important keys to the RSA algorithm:
If GCD(T, R) = 1 and T < R, then T^(phi(R)) = 1 (mod R).
Or, in words:
If T and R are relatively prime, with T being the smaller number, then when we multiply T with itself phi(R) times and divide the result by R, the remainder will always be 1.
We can test this theorem on some smaller numbers for which we have already calculated the totient. Using 5 for T and 6 for R, we get:
| phi(6) = (2 - 1) * (3 - 1) = 1 * 2 = 2, so | |
| 5^(phi(6)) = 5^2 = 25, and | |
| 25 = 24 + 1 = 6 * 4 + 1, therefore | |
| 25 = 1 (mod 6). |
Using 2 for T and 15 for R, we have:
| phi(15) = (3 - 1) * (5 - 1) = 2 * 4 = 8, so | |
| 2^(phi(15)) = 2^8 = 256, and | |
| 256 = 255 + 1 = 17 * 15 + 1, therefore | |
| 256 = 1 (mod 15). |
Variations on a Theme
Here again is the equation of Euler's Totient Theorem:
| T^(phi(R)) = 1 (mod R) |
(remembering that T < R, and T and R are relatively prime). Thanks to the way that modulus arithmetic works on multiplication, we can easily see that:
| T^(phi(R)) * T^(phi(R)) = 1 * 1 (mod R), |
which can be rewritten, using the laws of exponents, as:
| T^(phi(R) + phi(R)) = 1 * 1 (mod R), |
or:
| T^(2 * phi(R)) = 1 (mod R). |
If we ran through this sequence again, we would get:
| T^(3 * phi(R)) = 1 (mod R). |
Clearly, we could keep doing this as many times as we like. So, we can expand on Euler's Totient Theorem, and state a more general corollary:
If GCD(T, R) = 1 and T < R, then T^(K * phi(R)) = 1 (mod R), where K can be any number.
However, we can state this corrollary another way. Notice that if K can be any number, then K * phi(R) is just the set of numbers that are evenly divisible by phi(R). Or, in other words, the numbers that are congruent to zero, modulo phi(R). So:
If GCD(T, R) = 1 and T < R, then T^S = 1 (mod R) whenever S = 0 (mod phi(R)).
Now, let's tweak our equation further by multiplying both sides by T:
| T^S * T = 1 * T (mod R). |
Simplifying leaves us with:
| T^(S + 1) = T (mod R). |
If we repeat this, we will get:
| T^(S + 1) * T = T * T (mod R), |
or:
| T^(S + 2) = T^2 (mod R). |
Doing this yet again will give us:
| T^(S + 3) = T^3 (mod R), |
and so on. This pattern looks familiar, doesn't it?
What makes it interesting this time is that S is not a multiple of R, but of phi(R). In other words, we have the rather surprising rule:
| T^E = T^F (mod R) whenever E = F (mod phi(R)). |
(once again, only as long as T < R, and T and R are relatively prime).
The Plot Thickens
We are on the edge of something very important. Let's back up a bit and look at this equation more closely:
| T^(S + 1) = T (mod R). |
Notice what we have here. We take a number, T, and raise it to a power, and when we do the calculation in modulus arithmetic, we wind up with T again. In short, we have a recipe for a function that returns its own input (presuming that R has been chosen ahead of time, and that T is verified to be relatively prime to R).
If you're thinking to yourself, "What's so interesting about that?", then consider what we would have if we broke this function up into two separate steps. Specifically, let's imagine that we can find two new numbers P and Q such that:
| P * Q = S + 1, for one of the possible values of S. |
Or, more to the point:
| P * Q = 1 (mod phi(R)) |
Then we could write:
| T^(P * Q) = T (mod R), |
which is equivalent to:
| (T^P)^Q = T (mod R), |
and this is something that can be broken up into two steps:
| T^P = X (mod R), and then | |
| X^Q = T (mod R). |
Now, if you don't see the value in doing this, imagine now that the two steps are performed on separate computers. And that X is sent from the first computer to the second over an insecure phone line....
Does This Really Work?
T stands for the plaintext, the message that is to be sent. P, Q, and R together form the cipher's keys -- P and R make up the public key, and Q and R make up the private key. And X becomes the encrypted message.
Here, again, is the central equation that makes it work:
| P * Q = 1 (mod phi(R)) |
Note here that P and Q will both automatically be relatively prime to phi(R). (Why? Because if either P or Q had a factor in common with phi(R), then P * Q would also have that as a factor. But we know that P * Q divided by phi(R) leaves a remainder of one.) This is important.
Imagine a clockface, with just an hour hand, and imagine yourself placing the hour hand on midnight and then moving it forward by jumps, over and over, each jump covering N hours. If you pick a value for N that is divisible by 2 or 3 (the prime factors of 12), then you will find that you will only hit certain numbers before you return to midnight, and the sequence will then repeat. If N is 2, then the hour hand will visit 12, 2, 4, 6, 8, 10, 12, 2, 4, 6, 8, 10, 12 ...
If, however, your N is relatively prime with 12, then you will wind up hitting every number exactly once before finally returning to midnight 12 jumps later. For example, using 7 for your N, the itinerary would be: 12, 7, 2, 9, 4, 11, 6, 1, 8, 3, 10, 5, 12, ... In addition, the order in which you visit the numbers is entirely dependent on what value you pick for N.
In a similar vein, it is important that both P and Q be relatively prime to phi(R). Because of this, we know that every possible value for T, when raised to the power P modulo R, will land on a different number. (Remember that when doing exponents in modulus arithmetic, it is actually phi(R), and not R itself, that determines the length of the cycles.) If this weren't true -- if P, for example, shared a factor in common with phi(R) -- then some values for T could get mapped to the same value for X, and it would clearly be impossible to tell which was originally which. There could not be one value for Q that would correctly map X back to T every time.
The question of which T-values will wind up going to which X-values depends entirely on the value used for P -- and here's the rub for the would-be codebreaker: Just about every possible mapping of T-values to X-values does in fact exist. Somewhere out there is a P that will make that mapping.
If this:
| T^P = X | |
| X^Q = T |
was the cipher's scheme, there'd be no cipher. With P already being public knowledge, it would be trivial to take an X and compute backwards to T. But, instead, we have this:
| T^P = X (mod R) | |
| X^Q = T (mod R) |
as the cipher's scheme, and that changes everything. The modulus arithmetic erases too much information. There's no way to deduce how many times the hour hand needs to spin around the clockface when Q turns X back into T. Without knowing what Q is, a given X could wind up going to any of the possible values for T.
But what is really maddening to our would-be codebreaker is that even when T and P and X are all known, Q still can't be deduced! (Of course, it actually can -- but not necessarily within anyone's lifetime. But we're getting ahead of ourselves.)
So, let's see how to make this recipe work.
Making a Pair of Keys
To construct our own personal cipher keys, we need an appropriate value for R. So, we start by randomly picking two prime numbers, U and V, and multiplying them together:
| R = U * V. |
There are two good reasons for selecting a value for R that has exactly two prime factors. First of all, we have an easy formula for calculating phi(R):
| phi(R) = (U - 1) * (V - 1). |
Secondly, we want R to be hard to factor. The fewer factors a number has, the longer it takes to find them.
We then need to find values for P and Q such that:
| P * Q = 1 (mod phi(R)). |
When the numbers have been chosen, P and R together become the public key, and Q and R make up the private key. U and V are no longer needed, and can be forgotten.
An Example
In order to see all this in action, we want to stick with numbers that we can actually work with. So, for our example, we will select the primes 5 and 11 to be our U and V. This gives R a value of 55, and:
| phi(55) = (5 - 1) * (11 - 1) = 4 * 10 = 40. |
Now, we need to find numbers to fit the equation:
| P * Q = 1 (mod 40). |
There are, of course, an infinite number of pairs that will fit this equation. So, let's find one of them.
Our only initial constraint is that P and Q are both relatively prime to 40. So, we can't use numbers that are multiples of 2 and/or 5. We also don't want P and Q to be congruent mod 40, since that would turn our trapdoor cipher into a garden-variety symmetric cipher. Ideally, in fact, we'd prefer that P and Q be relatively prime to each other. Let's start with 7, which we'll assign to P:
| 7 * Q = 1 (mod 40). |
What would that make Q? If we rewrite this equation to get rid of the unfamiliar modulus arithmetic, we have:
| 7 * Q = K * 40 + 1, where K can be any number. |
The first value for Q that works is 23:
| 7 * 23 = 161 = 4 * 40 + 1. |
So we have 7 for P, our public key, and 23 for Q, our private key.
To make our cipher work, you may recall that the values we use for T must be less than R, and also relatively prime to R. We also don't want to use 1 for T, because 1 raised to any power whatsoever is going to remain 1. Finally, the same holds true for R - 1, because R - 1 is congruent to -1, modulo R.
So, we'll take what's left and create the following character set:
| 2 | 3 | 4 | 6 | 7 | 8 | 9 | 12 | 13 | 14 | 16 | 17 | 18 | |
| A | B | C | D | E | F | G | H | I | J | K | L | M | |
| 19 | 21 | 23 | 24 | 26 | 27 | 28 | 29 | 31 | 32 | 34 | 36 | 37 | |
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z | |
| 38 | 39 | 41 | 42 | 43 | 46 | 47 | 48 | 49 | 51 | 52 | 53 | ||
| sp | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | * |
The message we will encrypt is "VENIO" (Latin for "I come"):
| V | E | N | I | O | |
| 31 | 7 | 19 | 13 | 21 |
To encode it, we simply need to raise each number to the power of P modulo R.
| V: | 31^7 (mod 55) = | 27512614111 (mod 55) = | 26 | |
| E: | 7^7 (mod 55) = | 823543 (mod 55) = | 28 | |
| N: | 19^7 (mod 55) = | 893871739 (mod 55) = | 24 | |
| I: | 13^7 (mod 55) = | 62748517 (mod 55) = | 7 | |
| O: | 21^7 (mod 55) = | 1801088541 (mod 55) = | 21 |
So, our encrypted message is 26, 28, 24, 7, 21 -- or "RTQEO" in our personalized character set.
When the message "RTQEO" arrives on the other end of our insecure phone line, we can decrypt it simply by repeating the process -- this time using Q, our private key, in place of P.
| R: | 26^23 (mod 55) = | 350257144982200575261531309080576 (mod 55) = | 31 | |
| T: | 28^23 (mod 55) = | 1925904380037276068854119113162752 (mod 55) = | 7 | |
| Q: | 24^23 (mod 55) = | 55572324035428505185378394701824 (mod 55) = | 19 | |
| E: | 7^23 (mod 55) = | 27368747340080916343 (mod 55) = | 13 | |
| O: | 21^23 (mod 55) = | 2576580875108218291929075869661 (mod 55) = | 21 |
The result is 31, 7, 19, 13, 21 -- or "VENIO", our original message.
How to Crack RSA
Now, let's switch hats. Imagine that we've just managed to pluck the message "RTQEO" off of our wiretap. By looking up the message's destination in the public-key directory, we find that our message was encrypted with a value of 55 for R and 7 for P. How do we go about decrypting it when we don't know the value for Q?
Well, we know that that:
| P * Q = 1 (mod phi(R)), |
or, without the modulus arithmetic:
| P * Q = K * phi(R) + 1. |
We can divide both sides of the equation by P, which gives us a formula for Q:
| Q = (K * phi(R) + 1) / P. |
K is also unknown, though, so we will try plugging in different numbers for K, and look for values for Q that meet all the necessary constraints.
| (1 * 40 + 1) / 7 = | 41 / 7 | (doesn't divide evenly) | ||
| (2 * 40 + 1) / 7 = | 81 / 7 | (ditto) | ||
| (3 * 40 + 1) / 7 = | 121 / 7 | (ditto) | ||
| (4 * 40 + 1) / 7 = | 161 / 7 | = 23 | (this could be it!) |
Each time we find a candidate for Q, we can test it out on the message. We might get gibberish, in which case we can continue searching. If 23 hadn't worked and we needed to continue the search, it would be pretty obvious that we only needed to test every seventh number, since those are the only numbers which will give us a result that is evenly divisible by 7. Furthermore, we only need to test values up 39, thanks to the modulus arithmetic. So, even though this process involves a brute-force search, it is very simple and very fast.
Well then, so what's the catch? Simply that, in order to do any of this, we first need to know the value of phi(R). Of course, we already know that R has exactly two prime factors, so calculating phi(R) is a snap once we know what those factors are.
Famous last words.
How to Make RSA Uncrackable
Of course, in our case the factors of R can be found by consulting a times table. So it's not much of a challenge. (For that matter, since we're encrypting one character at a time, our coded messages would also be vulnerable to good old-fashioned cryptanalysis).
To make it less easy to find R's factors, we need to pick larger prime numbers for U and V to begin with. If, instead of 5 and 11, we had chosen 673 and 24971, we would have a value of 16805483 for R, and phi(R) would be 16779840. (This would also give us enough room to encrypt more than one byte at a time, which seriously reduces the vulnerability to cryptanalysis.) Looking for a P and Q pair is no longer something you want to do with pencil and paper, of course, but it took me less than three minutes to find the usable pair 397 and 211333 -- including the time it took to write and debug a Perl script.
On the other hand, it also took me less than three seconds to run "factor" on 16805483 to obtain 673 and 24971. Armed with those numbers, it wouldn't take much longer to derive 211333 from 397. So even these numbers aren't close to being large enough. We need really big numbers.
Well, we can certainly find huge values for R that are difficult to factor. But how far can we go before it becomes too difficult for us to use the number in the first place?
Huge Exponents in Modulus Arithmetic
The problem is this: The bigger R gets, the bigger P and Q will be, and P and Q are to be used as exponents! Even the relatively tame-looking
| 9^(9^9) |
produces a number over 350 million decimal digits long. How are we going to be able to encrypt anything without needing terabytes of storage?
The trick is that we only need to calculate these exponential values modulo R. As always, modulus arithmetic simplifies things a great deal.
Let's revisit our example, and look at how we could decrypt the number 28, remembering that R = 55 and Q = 23:
| 28^23 (mod 55) = ? |
To start with, we look at Q's binary representation. 23 in binary is 10111, which means that:
| 23 = 16 + 4 + 2 + 1, or | |
| 23 = 2^4 + 2^2 + 2^1 + 2^0. |
We can now break the exponential calculation apart into several smaller ones:
| 28^23 | = 28^(2^4 + 2^2 + 2^1 + 2^0) | |
| = 28^(2^4) * 28^(2^2) * 28^(2^1) * 28^(2^0) | ||
| = 28^(2 * 2 * 2 * 2) * 28^(2 * 2) * 28^2 * 28 | ||
| = (((28^2)^2)^2)^2 * (28^2)^2 * 28^2 * 28. |
This may look like anything but an improvement, at first. But on a closer examination, you'll see that we actually have many repeated subterms. This simplifies matters, particularly when we take advantage of the fact that we are calculating in modulo 55.
We compute the first square in modulus arithmetic:
| 28^2 = 784 = 14 (mod 55). |
By substituting this value into our equation:
| 28^23 = (((28^2)^2)^2)^2 * (28^2)^2 * 28^2 * 28 (mod 55), |
we get:
| 28^23 = ((14^2)^2)^2 * 14^2 * 14 * 28 (mod 55). |
Now by computing that square:
| 14^2 = 196 = 31 (mod 55), |
we will have:
| 28^23 = (31^2)^2 * 31 * 14 * 28 (mod 55). |
And, finally:
| 31^2 = 961 = 26 (mod 55), and | |
| 26^2 = 676 = 16 (mod 55); |
and so:
| 28^23 = 16 * 31 * 14 * 28 (mod 55). |
We can continue to take advantage of the modulus when we do the final multiplications:
| 28^23 | = 16 * 31 * 14 * 28 (mod 55) | |
| = 16 * 31 * 392 (mod 55) | ||
| = 16 * 31 * 7 (mod 55) | ||
| = 16 * 217 (mod 55) | ||
| = 16 * 52 (mod 55) | ||
| = 832 (mod 55) | ||
| = 7 (mod 55) |
Lo and behold: 7, the same result as when we did it the hard way.
This binary technique is really no different than how computers normally compute integer powers. However, the fact that we can break the process down to successive multiplications allows us to apply the modulus at every step of the way. This assures us that at no point will our algorithm have to handle a number larger than (R - 1)^2.
Huge Factors in Modulus Arithmetic
The magic of modulus arithmetic will also ensure that it's possible to find our P and Q pair. Remember that, after we've selected some humongous value for R, we need to find values to fit:
| P * Q = 1 (mod phi(R)), |
or, without the modulus arithmetic:
| P * Q = K * phi(R) + 1, where K is any number. |
After picking a likely value for P -- which probably will not be a conveniently small number like 7 -- we will need to find a matching Q. By rewriting the above as:
| P * Q - phi(R) * K = 1, |
with known values for P and phi(R), we have what is called a
Safety in Numbers
Okay. So we know that the whole process is still practical, even if R is immense. But all of this is still moot unless we can select an R in the first place. R has to be the product of two prime numbers, don't forget. If we want R to be so big that it can't be factored easily, how are we going to find those factors to begin with?
It turns out that there is an interesting little asymmetry here. Determining whether or not a number is prime happens to be a relatively cheap process.
One of the most famous methods for testing a number for primality uses
If P is prime, then N^(P - 1) = 1 (mod P) is true for every number N < P.
Does this seems suspiciously reminiscent of Euler's Totient Theorem? It should. Euler was the first person to publish a proof of Fermat's Little Theorem, and his Totient Theorem is a generalization of Fermat's. You can see this for yourself by remembering that phi(P) = P - 1 when P is prime.
Of course, as far as proofs go, this theorem is only useful for proving that a given number is composite. For example, it just so happens that:
| 4^14 (mod 15) = 268435456 (mod 15) = 1, |
even though 15 is no prime. Nonetheless, it is also true that:
| 3^14 (mod 15) = 4782969 (mod 15) = 9, and | |
| 5^14 (mod 15) = 6103515625 (mod 15) = 10. |
On the other hand, 17, which is prime, results in 1 every time:
| 3^16 (mod 17) = 43046721 (mod 17) = 1, | |
| 4^16 (mod 17) = 4294967296 (mod 17) = 1, | |
| 5^16 (mod 17) = 152587890625 (mod 17) = 1, and so on. |
So, if we want to know if a number is prime, we can run it through this test, using (say) 2 as the base. If anything besides 1 results, we know with certainty that the number is composite. If the answer is 1, however, we try the test again with 3, and then 4, and so on. If we keep getting back 1 as the result, it soon becomes rather unlikely that the number is anything but prime.
Unlikely, mind you, but not impossible. There are a handful of numbers
which pass this test for every base, but which are not prime. Called
Fortunately, there are other tests for primality which are more reliable. But they all have at least one thing in common with this test: When they reject a number, they tell us only that the number can be factored. The test results give us no information at all as to what the factors might be. How unfortunate!
Unfortunate for the mathematicians, that is. Very fortunate for us.
Summing Up
The basic truth is that, in order to find the factors of a composite
number, we're pretty much stuck with using brute force: Divide the
number by all the primes you can get your hands on until one of them
goes in evenly. There are plenty of ways to improve on this approach
(the
Nor is it likely that new approaches will, either! The real issue is that the encrypting and decrypting algorithms have a running time that is linear with respect to the length of R. That is to say, doubling the number of digits in R doubles the amount of time (roughly) needed to encrypt, decrypt, and to select the two primes to make a key with. But the algorithms for factoring R have a running time that is exponential with respect to the length of R. That is to say, the time (roughly) doubles with every few digits! (Because every digit added to R makes it ten times larger, and thus multiplies the number of potential candidates for its measly two factors.)
So if a new technique is suddenly found that makes it a trillion times faster to factor a number, all we have to do is increase the size of R we use by enough digits, and the situation will be right back where it started -- and all it means to us is that it takes a little bit longer to send and receive our messages. Already some people are using keys that, in order to factor with the Number Field Sieve, would require more energy than exists in the known universe.
An illustration: At the time of my writing, one of the largest general numbers that has been independently factored was the number used as the modulus for the RSA-140 challenge. (By "general numbers", I'm excluding creatures like Mersenne numbers and Fermat numbers, which have specialized factoring techniques that are inapplicable elsewhere.) It was completed on February 2, 1999. Now, the record previous to this was the RSA-130 number, and the process of factoring it was estimated as taking a total of 1000 MIPS-years of computer time. RSA-140, a number only 10 decimal digits longer, required twice that amount.
This, finally, is the heart of what makes RSA a trapdoor function: the gap between obtaining a number with two prime factors, and rediscovering the factors from the number itself. And the gap just keeps expanding as the numbers get larger.
The breakthrough that would completely destroy RSA's security would be an algorithm that actually produced a number's factors directly, instead of merely narrowing the search's scope. Such a thing has not been proven impossible, and it may well be that such a proof will never be found. But considering that prime numbers have been studied for thousands of years, and given the renewed attention that has been focused on this problem in the last few decades, the likelihood of the existence of such an algorithm appears very remote. Discovering one would change the face of number theory as much as RSA has changed the face of cryptography.
However -- if this were to happen, there are other trapdoor functions out there, waiting to be found. Whatever the future of RSA may be, the trapdoor cipher has certainly changed the face of cryptography forever.
RSA Vulnerability
A new vulnerability associated with RSA cryptography has been found, which works by spying the CPU internals with a spy program running on the same computer as the crypto application. Dedicated systems (like CAcert?s certificate generation) are not affected, only multi-tasking and multi-user systems are affected.
Romiz writes, “Branch Prediction Analysis is a recent attack vector against RSA public-key cryptography on personal computers that relies on timing measurements to get information on the bits in the private key. However, the method is not very practical because it requires many attempts to obtain meaningful information, and the current OpenSSL implementation now includes protections against those attacks. However, German cryptographer Jean-Pierre Seifert has announced [1]a new method called Simple Branch Prediction Analysis that is at the same time much more efficient that the previous ones, only needs a single attempt, successfully bypasses the OpenSSL protections, and should prove harder to avoid without a very large execution penalty.” From the article: “The successful extraction of almost all secret key bits by our SBPA attack against an openSSL RSA implementation proves that the often recommended blinding or so called randomization techniques to protect RSA against side-channel attacks are, in the context of SBPA attacks, totally useless.” [2]Le Monde interviewed Seifert (in French, but Babelfish works well) and claims that the details of the SBPA attack are being withheld; however, a PDF of the paper is linked from the [3]ePrint abstract.
1. http://eprint.iacr.org/2006/351
2. http://www.lemonde.fr/web/article/0,1-0@2-651865,36-835944@51-835781,0.html
3. http://eprint.iacr.org/2006/351
RSA Source Code
/**
* \file rsa.h
*/
#ifndef _RSA_H
#define _RSA_H
#ifdef __cplusplus
extern "C" {
#endif
#include "bignum.h"
#define ERR_RSA_BAD_INPUT_DATA 0x0300
#define ERR_RSA_INVALID_PADDING 0x0310
#define ERR_RSA_KEY_GEN_FAILED 0x0320
#define ERR_RSA_KEY_CHK_FAILED 0x0330
#define ERR_RSA_KEY_RD_FAILED 0x0340
#define ERR_RSA_KEY_WR_FAILED 0x0350
#define ERR_RSA_PUBLIC_FAILED 0x0360
#define ERR_RSA_PRIVATE_FAILED 0x0370
#define ERR_RSA_VERIFY_FAILED 0x0380
/*
* PKCS#1 stuff
*/
#define RSA_RAW 0
#define RSA_MD2 2
#define RSA_MD4 3
#define RSA_MD5 4
#define RSA_SHA1 5
#define RSA_SIGN 0x01
#define RSA_CRYPT 0x02
/*
* DigestInfo ::= SEQUENCE {
* digestAlgorithm DigestAlgorithmIdentifier,
* digest Digest }
*
* DigestAlgorithmIdentifier ::= AlgorithmIdentifier
*
* Digest ::= OCTET STRING
*/
#define ASN1_HASH_MDX \
"\x30\x20\x30\x0C\x06\x08\x2A\x86\x48" \
"\x86\xF7\x0D\x02\x00\x05\x00\x04\x10"
#define ASN1_HASH_SHA1 \
"\x30\x21\x30\x09\x06\x05\x2B\x0E\x03" \
"\x02\x1A\x05\x00\x04\x14"
typedef struct
{
int ver; /*!< should be 0 */
int len; /*!< size(N) in chars */
mpi N; /*!< public modulus */
mpi E; /*!< public exponent */
mpi D; /*!< private exponent */
mpi P; /*!< 1st prime factor */
mpi Q; /*!< 2nd prime factor */
mpi DP; /*!< D mod (P - 1) */
mpi DQ; /*!< D mod (Q - 1) */
mpi QP; /*!< inverse of Q % P */
mpi RN; /*!< cached R^2 mod N */
mpi RP; /*!< cached R^2 mod P */
mpi RQ; /*!< cached R^2 mod Q */
}
rsa_context;
/**
* \brief Generate an RSA keypair
*
* \param ctx RSA context to be initialized
* \param nbits size of the public key in bits
* \param exponent public exponent (e.g., 65537)
* \param rng_f points to the RNG function
* \param rng_d points to the RNG data
*
* \return 0 if successful, or an ERR_RSA_XXX error code
*/
int rsa_gen_key( rsa_context *ctx, int nbits, int exponent,
int (*rng_f)(void *), void *rng_d );
/**
* \brief Read the public key from a file
*
* \param ctx RSA context to be initialized
* \param f Handle of the source file
*
* \return 0 if successful, or an ERR_RSA_XXX error code
*/
int rsa_read_public( rsa_context *ctx, FILE *f );
/**
* \brief Read the private key from a file
*
* \param ctx RSA context to be initialized
* \param f Handle of the source file
*
* \return 0 if successful, or an ERR_RSA_XXX error code
*/
int rsa_read_private( rsa_context *ctx, FILE *f );
/**
* \brief Write the public key into a file
*
* \param ctx RSA context holding the key
* \param f Handle of the destination file
*
* \return 0 if successful, or an ERR_RSA_XXX error code
*/
int rsa_write_public( rsa_context *ctx, FILE *f );
/**
* \brief Write the private key into a file
*
* \param ctx RSA context holding the key
* \param f Handle of the destination file
*
* \return 0 if successful, or an ERR_RSA_XXX error code
*/
int rsa_write_private( rsa_context *ctx, FILE *f );
/**
* \brief Perform an RSA public key operation
*
* \return 0 if successful, or an ERR_RSA_XXX error code
*
* \note This function does not take care of message
* padding: both ilen and olen must be equal to
* the modulus size (ctx->len). Also, be sure
* to set input[0] = 0.
*/
int rsa_public( rsa_context *ctx,
unsigned char *input, int ilen,
unsigned char *output, int olen );
/**
* \brief Perform an RSA private key operation
*
* \return 0 if successful, or an ERR_RSA_XXX error code
*
* \note This function does not take care of message
* padding: both ilen and olen must be equal to
* the modulus size (ctx->len). Also, be sure
* to set input[0] = 0.
*/
int rsa_private( rsa_context *ctx,
unsigned char *input, int ilen,
unsigned char *output, int olen );
/**
* \brief Return 0 if the public key is valid,
* or ERR_RSA_KEY_CHECK_FAILED
*/
int rsa_check_pubkey( rsa_context *ctx );
/**
* \brief Return 0 if the private key is valid,
* or ERR_RSA_KEY_CHECK_FAILED
*/
int rsa_check_privkey( rsa_context *ctx );
/**
* \brief Add the PKCS#1 v1.5 padding and do a public RSA
*
* \param ctx RSA context
* \param input buffer holding the data to be encrypted
* \param ilen length of the plaintext; cannot be longer
* than the modulus, minus 3+8 for padding
* \param output buffer that will hold the ciphertext
* \param olen must be the same as the modulus size
* (for example, 128 if RSA-1024 is used)
*
* \return 0 if successful, or an ERR_RSA_XXX error code
*/
int rsa_pkcs1_encrypt( rsa_context *ctx,
unsigned char *input, int ilen,
unsigned char *output, int olen );
/**
* \brief Do a private RSA, removes the PKCS#1 v1.5 padding
*
* \param ctx RSA context
* \param input buffer holding the encrypted data
* \param ilen must be the same as the modulus size
* \param output buffer that will hold the plaintext
* \param olen size of output buffer, will be updated
* to contain the length of the plaintext
*
* \return 0 if successful, or an ERR_RSA_XXX error code
*/
int rsa_pkcs1_decrypt( rsa_context *ctx,
unsigned char *input, int ilen,
unsigned char *output, int *olen );
/**
* \brief Perform a private RSA to sign a message digest
*
* \param ctx RSA context
* \param alg_id RSA_RAW, RSA_MD2/4/5 or RSA_SHA1
* \param hash buffer holding the message digest
* \param hashlen message digest length
* \param sig buffer that will hold the ciphertext
* \param siglen must be the same as the modulus size
* (for example, 128 if RSA-1024 is used)
*
* \return 0 if the signing operation was successful,
* or an ERR_RSA_XXX error code
*/
int rsa_pkcs1_sign( rsa_context *ctx, int alg_id,
unsigned char *hash, int hashlen,
unsigned char *sig, int siglen );
/**
* \brief Perform a public RSA and check the message digest
*
* \param ctx points to an RSA public key
* \param alg_id RSA_RAW, RSA_MD2/4/5 or RSA_SHA1
* \param hash buffer holding the message digest
* \param hashlen message digest length
* \param sig buffer holding the ciphertext
* \param siglen must be the same as the modulus size
*
* \return 0 if the verify operation was successful,
* or an ERR_RSA_XXX error code
*/
int rsa_pkcs1_verify( rsa_context *ctx, int alg_id,
unsigned char *hash, int hashlen,
unsigned char *sig, int siglen );
/**
* \brief Free the components of an RSA key
*/
void rsa_free( rsa_context *ctx );
/**
* \brief Checkup routine
*
* \return 0 if successful, or 1 if the test failed
*/
int rsa_self_test( int verbose );
/*
* Example RSA-1024 keypair, for test purposes
*/
#define KEY_LEN 128
#define RSA_N "9292758453063D803DD603D5E777D788" \
"8ED1D5BF35786190FA2F23EBC0848AEA" \
"DDA92CA6C3D80B32C4D109BE0F36D6AE" \
"7130B9CED7ACDF54CFC7555AC14EEBAB" \
"93A89813FBF3C4F8066D2D800F7C38A8" \
"1AE31942917403FF4946B0A83D3D3E05" \
"EE57C6F5F5606FB5D4BC6CD34EE0801A" \
"5E94BB77B07507233A0BC7BAC8F90F79"
#define RSA_E "10001"
#define RSA_D "24BF6185468786FDD303083D25E64EFC" \
"66CA472BC44D253102F8B4A9D3BFA750" \
"91386C0077937FE33FA3252D28855837" \
"AE1B484A8A9A45F7EE8C0C634F99E8CD" \
"DF79C5CE07EE72C7F123142198164234" \
"CABB724CF78B8173B9F880FC86322407" \
"AF1FEDFDDE2BEB674CA15F3E81A1521E" \
"071513A1E85B5DFA031F21ECAE91A34D"
#define RSA_P "C36D0EB7FCD285223CFB5AABA5BDA3D8" \
"2C01CAD19EA484A87EA4377637E75500" \
"FCB2005C5C7DD6EC4AC023CDA285D796" \
"C3D9E75E1EFC42488BB4F1D13AC30A57"
#define RSA_Q "C000DF51A7C77AE8D7C7370C1FF55B69" \
"E211C2B9E5DB1ED0BF61D0D9899620F4" \
"910E4168387E3C30AA1E00C339A79508" \
"8452DD96A9A5EA5D9DCA68DA636032AF"
#define RSA_DP "C1ACF567564274FB07A0BBAD5D26E298" \
"3C94D22288ACD763FD8E5600ED4A702D" \
"F84198A5F06C2E72236AE490C93F07F8" \
"3CC559CD27BC2D1CA488811730BB5725"
#define RSA_DQ "4959CBF6F8FEF750AEE6977C155579C7" \
"D8AAEA56749EA28623272E4F7D0592AF" \
"7C1F1313CAC9471B5C523BFE592F517B" \
"407A1BD76C164B93DA2D32A383E58357"
#define RSA_QP "9AE7FBC99546432DF71896FC239EADAE" \
"F38D18D2B2F0E2DD275AA977E2BF4411" \
"F5A3B2A5D33605AEBBCCBA7FEB9F2D2F" \
"A74206CEC169D74BF5A8C50D6F48EA08"
#ifdef __cplusplus
}
#endif
#endif
/*
* The RSA Public-Key cryptosystem
*
* Copyright (C) 2006-2007 Christophe Devine
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License, version 2.1 as published by the Free Software Foundation.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301 USA
*/
/*
* RSA was designed by Ron Rivest, Adi Shamir and Len Adleman.
*
* http://theory.lcs.mit.edu/~rivest/rsapaper.pdf
* http://www.cacr.math.uwaterloo.ca/hac/about/chap8.pdf
*/
#ifndef _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_DEPRECATE 1
#endif
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "xyssl/rsa.h"
#if !defined(NO_GENPRIME)
/*
* Generate an RSA keypair
*/
int rsa_gen_key( rsa_context *ctx, int nbits, int exponent,
int (*rng_f)(void *), void *rng_d )
{
int ret;
mpi P1, Q1, H, G;
if( nbits < 128 || exponent < 3 || rng_f == NULL )
return( ERR_RSA_BAD_INPUT_DATA );
mpi_init( &P1, &Q1, &H, &G, NULL );
memset( ctx, 0, sizeof( rsa_context ) );
/*
* find primes P and Q with Q < P so that:
* GCD( E, (P-1)*(Q-1) ) == 1
*/
CHK( mpi_lset( &ctx->E, exponent ) );
nbits >>= 1;
do
{
CHK( mpi_gen_prime( &ctx->P, nbits, 0, rng_f, rng_d ) );
CHK( mpi_gen_prime( &ctx->Q, nbits, 0, rng_f, rng_d ) );
if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) < 0 )
mpi_swap( &ctx->P, &ctx->Q );
if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) == 0 )
continue;
CHK( mpi_mul_mpi( &ctx->N, &ctx->P, &ctx->Q ) );
CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
CHK( mpi_gcd( &G, &ctx->E, &H ) );
}
while( mpi_cmp_int( &G, 1 ) != 0 );
/*
* D = E^-1 mod ((P-1)*(Q-1))
* DP = D mod (P - 1)
* DQ = D mod (Q - 1)
* QP = Q^-1 mod P
*/
CHK( mpi_inv_mod( &ctx->D , &ctx->E, &H ) );
CHK( mpi_mod_mpi( &ctx->DP, &ctx->D, &P1 ) );
CHK( mpi_mod_mpi( &ctx->DQ, &ctx->D, &Q1 ) );
CHK( mpi_inv_mod( &ctx->QP, &ctx->Q, &ctx->P ) );
ctx->len = ( mpi_msb( &ctx->N ) + 7 ) >> 3;
cleanup:
mpi_free( &P1, &Q1, &H, &G, NULL );
if( ret != 0 )
{
rsa_free( ctx );
return( ERR_RSA_KEY_GEN_FAILED | ret );
}
return( 0 );
}
#endif
/*
* Read the public key from a file
*/
int rsa_read_public( rsa_context *ctx, FILE *f )
{
int ret;
memset( ctx, 0, sizeof( rsa_context ) );
CHK( mpi_read_file( &ctx->N, 16, f ) );
CHK( mpi_read_file( &ctx->E, 16, f ) );
ctx->len = ( mpi_msb( &ctx->N ) + 7 ) >> 3;
cleanup:
if( ret != 0 )
{
rsa_free( ctx );
return( ERR_RSA_KEY_RD_FAILED | ret );
}
return( 0 );
}
/*
* Read the private key from a file
*/
int rsa_read_private( rsa_context *ctx, FILE *f )
{
int ret;
memset( ctx, 0, sizeof( rsa_context ) );
CHK( mpi_read_file( &ctx->N , 16, f ) );
CHK( mpi_read_file( &ctx->E , 16, f ) );
CHK( mpi_read_file( &ctx->D , 16, f ) );
CHK( mpi_read_file( &ctx->P , 16, f ) );
CHK( mpi_read_file( &ctx->Q , 16, f ) );
CHK( mpi_read_file( &ctx->DP, 16, f ) );
CHK( mpi_read_file( &ctx->DQ, 16, f ) );
CHK( mpi_read_file( &ctx->QP, 16, f ) );
ctx->len = ( mpi_msb( &ctx->N ) + 7 ) >> 3;
cleanup:
if( ret != 0 )
{
rsa_free( ctx );
return( ERR_RSA_KEY_RD_FAILED | ret );
}
return( 0 );
}
/*
* Write the public key into a file
*/
int rsa_write_public( rsa_context *ctx, FILE *f )
{
int ret;
CHK( mpi_write_file( "N = ", &ctx->N, 16, f ) );
CHK( mpi_write_file( "E = ", &ctx->E, 16, f ) );
cleanup:
if( ret != 0 )
return( ERR_RSA_KEY_WR_FAILED | ret );
return( 0 );
}
/*
* Write the private key into a file
*/
int rsa_write_private( rsa_context *ctx, FILE *f )
{
int ret;
CHK( mpi_write_file( "N = " , &ctx->N , 16, f ) );
CHK( mpi_write_file( "E = " , &ctx->E , 16, f ) );
CHK( mpi_write_file( "D = " , &ctx->D , 16, f ) );
CHK( mpi_write_file( "P = " , &ctx->P , 16, f ) );
CHK( mpi_write_file( "Q = " , &ctx->Q , 16, f ) );
CHK( mpi_write_file( "DP = ", &ctx->DP, 16, f ) );
CHK( mpi_write_file( "DQ = ", &ctx->DQ, 16, f ) );
CHK( mpi_write_file( "QP = ", &ctx->QP, 16, f ) );
cleanup:
if( ret != 0 )
return( ERR_RSA_KEY_WR_FAILED | ret );
return( 0 );
}
/*
* Perform an RSA public key operation
*/
int rsa_public( rsa_context *ctx,
unsigned char *input, int ilen,
unsigned char *output, int olen )
{
int ret;
mpi T;
if( ilen != ctx->len || olen != ctx->len )
return( ERR_RSA_BAD_INPUT_DATA );
mpi_init( &T, NULL );
CHK( mpi_read_binary( &T, input, ilen ) );
if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
{
mpi_free( &T, NULL );
return( ERR_RSA_BAD_INPUT_DATA );
}
CHK( mpi_exp_mod( &T, &T, &ctx->E, &ctx->N, &ctx->RN ) );
CHK( mpi_write_binary( &T, output, &olen ) );
cleanup:
mpi_free( &T, NULL );
if( ret != 0 )
return( ERR_RSA_PUBLIC_FAILED | ret );
return( 0 );
}
/*
* Perform an RSA private key operation
*/
int rsa_private( rsa_context *ctx,
unsigned char *input, int ilen,
unsigned char *output, int olen )
{
int ret;
mpi T, T1, T2;
if( ilen != ctx->len || olen != ctx->len )
return( ERR_RSA_BAD_INPUT_DATA );
mpi_init( &T, &T1, &T2, NULL );
CHK( mpi_read_binary( &T, input, ilen ) );
if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
{
mpi_free( &T, NULL );
return( ERR_RSA_BAD_INPUT_DATA );
}
#if 0
CHK( mpi_exp_mod( &T, &T, &ctx->D, &ctx->N, &ctx->RN ) );
#else
/*
* faster decryption using the CRT
*
* T1 = input ^ dP mod P
* T2 = input ^ dQ mod Q
*/
CHK( mpi_exp_mod( &T1, &T, &ctx->DP, &ctx->P, &ctx->RP ) );
CHK( mpi_exp_mod( &T2, &T, &ctx->DQ, &ctx->Q, &ctx->RQ ) );
/*
* T = (T1 - T2) * (Q^-1 mod P) mod P
*/
CHK( mpi_sub_mpi( &T, &T1, &T2 ) );
CHK( mpi_mul_mpi( &T1, &T, &ctx->QP ) );
CHK( mpi_mod_mpi( &T, &T1, &ctx->P ) );
/*
* output = T2 + T * Q
*/
CHK( mpi_mul_mpi( &T1, &T, &ctx->Q ) );
CHK( mpi_add_mpi( &T, &T2, &T1 ) );
#endif
CHK( mpi_write_binary( &T, output, &olen ) );
cleanup:
mpi_free( &T, &T1, &T2, NULL );
if( ret != 0 )
return( ERR_RSA_PRIVATE_FAILED | ret );
return( 0 );
}
/*
* Check if the public key is valid
*/
int rsa_check_pubkey( rsa_context *ctx )
{
if( ( ctx->N.p[0] & 1 ) == 0 ||
( ctx->E.p[0] & 1 ) == 0 )
return( ERR_RSA_KEY_CHK_FAILED );
if( mpi_msb( &ctx->N ) < 128 ||
mpi_msb( &ctx->N ) > 4096 )
return( ERR_RSA_KEY_CHK_FAILED );
if( mpi_msb( &ctx->E ) < 2 ||
mpi_msb( &ctx->E ) > 64 )
return( ERR_RSA_KEY_CHK_FAILED );
return( 0 );
}
/*
* Check if the private key is valid
*/
int rsa_check_privkey( rsa_context *ctx )
{
int ret = 0;
mpi TN, P1, Q1, H, G;
mpi_init( &TN, &P1, &Q1, &H, &G, NULL );
CHK( mpi_mul_mpi( &TN, &ctx->P, &ctx->Q ) );
CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
CHK( mpi_gcd( &G, &ctx->E, &H ) );
if( mpi_cmp_mpi( &TN, &ctx->N ) == 0 &&
mpi_cmp_int( &G, 1 ) == 0 )
{
mpi_free( &TN, &P1, &Q1, &H, &G, NULL );
return( 0 );
}
cleanup:
mpi_free( &TN, &P1, &Q1, &H, &G, NULL );
return( ERR_RSA_KEY_CHK_FAILED | ret );
}
/*
* Add the PKCS#1 v1.5 padding and do a public RSA
*/
int rsa_pkcs1_encrypt( rsa_context *ctx,
unsigned char *input, int ilen,
unsigned char *output, int olen )
{
int nb_pad;
unsigned char *p = output;
if( olen != ctx->len || olen < ilen + 11 )
return( ERR_RSA_BAD_INPUT_DATA );
nb_pad = olen - 3 - ilen;
*p++ = 0;
*p++ = RSA_CRYPT;
while( nb_pad-- > 0 )
{
do { *p = rand(); } while( *p == 0 );
p++;
}
*p++ = 0;
memcpy( p, input, ilen );
return( rsa_public( ctx, output, olen, output, olen ) );
}
/*
* Do a private RSA, removes the PKCS#1 v1.5 padding
*/
int rsa_pkcs1_decrypt( rsa_context *ctx,
unsigned char *input, int ilen,
unsigned char *output, int *olen )
{
int ret;
unsigned char *p, buf[512];
if( ilen != ctx->len || ilen < 16 || ilen > 512 )
return( ERR_RSA_BAD_INPUT_DATA );
if( ( ret = rsa_private( ctx, input, ilen, buf, ilen ) ) != 0 )
return( ret );
p = buf;
if( *p++ != 0 || *p++ != RSA_CRYPT )
return( ERR_RSA_INVALID_PADDING );
while( *p != 0 )
{
if( p >= buf + ilen - 1 )
return( ERR_RSA_INVALID_PADDING );
p++;
}
p++;
if( *olen < ilen - (int)(p - buf) )
return( ERR_RSA_INVALID_PADDING );
*olen = ilen - (int)(p - buf);
memcpy( output, p, *olen );
return( 0 );
}
/*
* Perform a private RSA to sign a message digest
*/
int rsa_pkcs1_sign( rsa_context *ctx, int alg_id,
unsigned char *hash, int hashlen,
unsigned char *sig, int siglen )
{
int nb_pad;
unsigned char *p = sig;
if( siglen != ctx->len || siglen < 16 )
return( ERR_RSA_BAD_INPUT_DATA );
switch( alg_id )
{
case RSA_RAW:
nb_pad = siglen - 3 - hashlen;
break;
case RSA_MD2:
case RSA_MD4:
case RSA_MD5:
nb_pad = siglen - 3 - 34;
break;
case RSA_SHA1:
nb_pad = siglen - 3 - 35;
break;
default:
return( ERR_RSA_BAD_INPUT_DATA );
}
if( nb_pad < 8 )
return( ERR_RSA_BAD_INPUT_DATA );
*p++ = 0;
*p++ = RSA_SIGN;
memset( p, 0xFF, nb_pad );
p += nb_pad;
*p++ = 0;
switch( alg_id )
{
case RSA_RAW:
memcpy( p, hash, hashlen );
break;
case RSA_MD2:
memcpy( p, ASN1_HASH_MDX, 18 );
memcpy( p + 18, hash, 16 );
p[13] = 2; break;
case RSA_MD4:
memcpy( p, ASN1_HASH_MDX, 18 );
memcpy( p + 18, hash, 16 );
p[13] = 4; break;
case RSA_MD5:
memcpy( p, ASN1_HASH_MDX, 18 );
memcpy( p + 18, hash, 16 );
p[13] = 5; break;
case RSA_SHA1:
memcpy( p, ASN1_HASH_SHA1, 15 );
memcpy( p + 15, hash, 20 );
break;
default:
return( ERR_RSA_BAD_INPUT_DATA );
}
return( rsa_private( ctx, sig, siglen, sig, siglen ) );
}
/*
* Perform a public RSA and check the message digest
*/
int rsa_pkcs1_verify( rsa_context *ctx, int alg_id,
unsigned char *hash, int hashlen,
unsigned char *sig, int siglen )
{
int ret, len;
unsigned char *p, c, buf[512];
if( siglen != ctx->len || siglen < 16 || siglen > 512 )
return( ERR_RSA_BAD_INPUT_DATA );
if( ( ret = rsa_public( ctx, sig, siglen, buf, siglen ) ) != 0 )
return( ret );
p = buf;
if( *p++ != 0 || *p++ != RSA_SIGN )
return( ERR_RSA_INVALID_PADDING );
while( *p != 0 )
{
if( p >= buf + siglen - 1 || *p != 0xFF )
return( ERR_RSA_INVALID_PADDING );
p++;
}
p++;
len = siglen - (int)( p - buf );
if( len == 34 )
{
c = p[13];
p[13] = 0;
if( memcmp( p, ASN1_HASH_MDX, 18 ) != 0 )
return( ERR_RSA_VERIFY_FAILED );
if( ( c == 2 && alg_id == RSA_MD2 ) ||
( c == 4 && alg_id == RSA_MD4 ) ||
( c == 5 && alg_id == RSA_MD5 ) )
{
if( memcmp( p + 18, hash, 16 ) == 0 )
return( 0 );
else
return( ERR_RSA_VERIFY_FAILED );
}
}
if( len == 35 && alg_id == RSA_SHA1 )
{
if( memcmp( p, ASN1_HASH_SHA1, 15 ) == 0 &&
memcmp( p + 15, hash, 20 ) == 0 )
return( 0 );
else
return( ERR_RSA_VERIFY_FAILED );
}
if( len == hashlen && alg_id == RSA_RAW )
{
if( memcmp( p, hash, hashlen ) == 0 )
return( 0 );
else
return( ERR_RSA_VERIFY_FAILED );
}
return( ERR_RSA_INVALID_PADDING );
}
/*
* Free the components of an RSA key
*/
void rsa_free( rsa_context *ctx )
{
mpi_free( &ctx->N, &ctx->E, &ctx->D,
&ctx->P, &ctx->Q, &ctx->DP,
&ctx->DQ, &ctx->QP, &ctx->RN,
&ctx->RP, &ctx->RQ, NULL );
}
#if defined(SELF_TEST)
#include "xyssl/sha1.h"
#define PT_LEN 24
#define RSA_PT "\xAA\xBB\xCC\x03\x02\x01\x00\xFF\xFF\xFF\xFF\xFF" \
"\x11\x22\x33\x0A\x0B\x0C\xCC\xDD\xDD\xDD\xDD\xDD"
/*
* Checkup routine
*/
int rsa_self_test( int verbose )
{
int len;
rsa_context rsa;
unsigned char sha1sum[20];
unsigned char rsa_plaintext[PT_LEN];
unsigned char rsa_decrypted[PT_LEN];
unsigned char rsa_ciphertext[KEY_LEN];
memset( &rsa, 0, sizeof( rsa_context ) );
rsa.len = KEY_LEN;
mpi_read_string( &rsa.N , 16, RSA_N );
mpi_read_string( &rsa.E , 16, RSA_E );
mpi_read_string( &rsa.D , 16, RSA_D );
mpi_read_string( &rsa.P , 16, RSA_P );
mpi_read_string( &rsa.Q , 16, RSA_Q );
mpi_read_string( &rsa.DP, 16, RSA_DP );
mpi_read_string( &rsa.DQ, 16, RSA_DQ );
mpi_read_string( &rsa.QP, 16, RSA_QP );
if( verbose != 0 )
printf( " RSA key validation: " );
if( rsa_check_pubkey( &rsa ) != 0 ||
rsa_check_privkey( &rsa ) != 0 )
{
if( verbose != 0 )
printf( "failed\n" );
return( 1 );
}
if( verbose != 0 )
printf( "passed\n PKCS#1 encryption : " );
memcpy( rsa_plaintext, RSA_PT, PT_LEN );
if( rsa_pkcs1_encrypt( &rsa, rsa_plaintext, PT_LEN,
rsa_ciphertext, KEY_LEN ) != 0 )
{
if( verbose != 0 )
printf( "failed\n" );
return( 1 );
}
if( verbose != 0 )
printf( "passed\n PKCS#1 decryption : " );
len = sizeof( rsa_decrypted );
if( rsa_pkcs1_decrypt( &rsa, rsa_ciphertext, KEY_LEN,
rsa_decrypted, &len ) != 0 ||
memcmp( rsa_decrypted, rsa_plaintext, len ) != 0 )
{
if( verbose != 0 )
printf( "failed\n" );
return( 1 );
}
if( verbose != 0 )
printf( "passed\n PKCS#1 data sign : " );
sha1( rsa_plaintext, PT_LEN, sha1sum );
if( rsa_pkcs1_sign( &rsa, RSA_SHA1, sha1sum, 20,
rsa_ciphertext, KEY_LEN ) != 0 )
{
if( verbose != 0 )
printf( "failed\n" );
return( 1 );
}
if( verbose != 0 )
printf( "passed\n PKCS#1 sig. verify: " );
if( rsa_pkcs1_verify( &rsa, RSA_SHA1, sha1sum, 20,
rsa_ciphertext, KEY_LEN ) != 0 )
{
if( verbose != 0 )
printf( "failed\n" );
return( 1 );
}
if( verbose != 0 )
printf( "passed\n\n" );
rsa_free( &rsa );
return( 0 );
}
#else
int rsa_self_test( int verbose )
{
return( 0 );
}
#endif