Author: Minh Van Nguyen <nguyenminh2@gmail.com>
This tutorial uses Sage to study elementary number theory and the RSApublic key cryptosystem. A number of Sage commands will be presentedthat help us to perform basic number theoretic operations such asgreatest common divisor and Euler’s phi function. We then present theRSA cryptosystem and use Sage’s built-in commands to encrypt anddecrypt data via the RSA algorithm. Note that this tutorial on RSA isfor pedagogy purposes only. For further details on cryptography orthe security of various cryptosystems, consult specialized texts suchas[MenezesEtAl1996],[Stinson2006], and[TrappeWashington2006].
The algorithm can be used to encrypt or generate digital signatures. That digital signature can then be incorporated within a simple file, and some other metadata, to create what is an RSA certificate. The RSA algorithm is among the most widely used encryption and signature algorithms in the world, if not the most widely used. Jan 24, 2007 Simple explanation/example of RSA encryption? Hello, I am trying to understand how public key encryption works - I've looked through several websites, but I find them very confusing and if they do manage to provide an example I find myself quickly lost. Nov 04, 2014 The RSA Encryption Algorithm (1 of 2: Computing an Example). The RSA Encryption Algorithm (2 of 2: Generating the Keys) - Duration. How the RSA algorithm works, including how to select d, e. RSA algorithm is a public key encryption technique and is considered as the most secure way of encryption. It was invented by Rivest, Shamir and Adleman in year 1978 and hence name RSA algorithm. The RSA algorithm holds the following features − RSA algorithm is a popular exponentiation in a finite field over integers including prime numbers. RSA (Rivest–Shamir–Adleman) is an algorithm used by modern computers to encrypt and decrypt messages. It is an asymmetric cryptographic algorithm. Asymmetric means that there are two different keys. This is also called public key cryptography, because one of the keys can be given to anyone. The other key must be kept private.
Elementary number theory¶
We first review basic concepts from elementary number theory,including the notion of primes, greatest common divisors, congruencesand Euler’s phi function. The number theoretic concepts and Sagecommands introduced will be referred to in later sections when wepresent the RSA algorithm.
Prime numbers¶
Public key cryptography uses many fundamental concepts from numbertheory, such as prime numbers and greatest common divisors. Apositive integer (n > 1) is said to be prime if its factors areexclusively 1 and itself. In Sage, we can obtain the first 20 primenumbers using the command primes_first_n:
Greatest common divisors¶
Let (a) and (b) be integers, not both zero. Then the greatest commondivisor (GCD) of (a) and (b) is the largest positive integer which isa factor of both (a) and (b). We use (gcd(a,b)) to denote thislargest positive factor. One can extend this definition by setting(gcd(0,0) = 0). Sage uses gcd(a,b) to denote the GCD of (a)and (b). The GCD of any two distinct primes is 1, and the GCD of 18and 27 is 9.
If (gcd(a,b) = 1), we say that (a) is coprime (or relativelyprime) to (b). In particular, (gcd(3, 59) = 1) so 3 is coprime to 59and vice versa.
Congruences¶
When one integer is divided by a non-zero integer, we usually get aremainder. For example, upon dividing 23 by 5, we get a remainder of3; when 8 is divided by 5, the remainder is again 3. The notion ofcongruence helps us to describe the situation in which two integershave the same remainder upon division by a non-zero integer. Let(a,b,n in ZZ) such that (n neq 0). If (a) and (b) have thesame remainder upon division by (n), then we say that (a) iscongruent to (b) modulo (n) and denote this relationship by
This definition is equivalent to saying that (n) divides thedifference of (a) and (b), i.e. (n ;|; (a - b)). Thus(23 equiv 8 pmod{5}) because when both 23 and 8 are divided by 5, weend up with a remainder of 3. The command mod allows us tocompute such a remainder:
Euler’s phi function¶
Consider all the integers from 1 to 20, inclusive. List all thoseintegers that are coprime to 20. In other words, we want to findthose integers (n), where (1 leq n leq 20), such that(gcd(n,20) = 1). The latter task can be easily accomplished with alittle bit of Sage programming:
The above programming statements can be saved to a text file called,say, /home/mvngu/totient.sage, organizing it as follows to enhancereadability.
We refer to totient.sage as a Sage script, just as one would referto a file containing Python code as a Python script. We use 4 spaceindentations, which is a coding convention in Sage as well as Pythonprogramming, instead of tabs.
The command load can be used to read the file containing ourprogramming statements into Sage and, upon loading the content of thefile, have Sage execute those statements:
From the latter list, there are 8 integers in the closed interval([1, 20]) that are coprime to 20. Without explicitly generating thelist
how can we compute the number of integers in ([1, 20]) that arecoprime to 20? This is where Euler’s phi function comes in handy.Let (n in ZZ) be positive. Then Euler’s phi function counts thenumber of integers (a), with (1 leq a leq n), such that(gcd(a,n) = 1). This number is denoted by (varphi(n)). Euler’s phifunction is sometimes referred to as Euler’s totient function, hencethe name totient.sage for the above Sage script. The commandeuler_phi implements Euler’s phi function. To compute(varphi(20)) without explicitly generating the above list, we proceedas follows:
How to keep a secret?¶
Cryptography is the science (some might say art) of concealingdata. Imagine that we are composing a confidential email tosomeone. Having written the email, we can send it in one of two ways.The first, and usually convenient, way is to simply press the sendbutton and not care about how our email will be delivered. Sending anemail in this manner is similar to writing our confidential message ona postcard and post it without enclosing our postcard inside anenvelope. Anyone who can access our postcard can see our message.On the other hand, before sending our email, we can scramble theconfidential message and then press the send button. Scrambling ourmessage is similar to enclosing our postcard inside an envelope.While not 100% secure, at least we know that anyone wanting to readour postcard has to open the envelope.
In cryptography parlance, our message is called plaintext. Theprocess of scrambling our message is referred to as encryption.After encrypting our message, the scrambled version is calledciphertext. From the ciphertext, we can recover our originalunscrambled message via decryption. The following figureillustrates the processes of encryption and decryption. Acryptosystem is comprised of a pair of related encryption anddecryption processes.
The following table provides a very simple method of scrambling amessage written in English and using only upper case letters,excluding punctuation characters.
Formally, let
be the set of capital letters of the English alphabet. Furthermore,let
be the American Standard Code for Information Interchange (ASCII)encodings of the upper case English letters. Then the above tableexplicitly describes the mapping (f: Sigma longrightarrow Phi).(For those familiar with ASCII, (f) is actually a common process forencoding elements of (Sigma), rather than a cryptographic“scrambling” process per se.) To scramble a message written usingthe alphabet (Sigma), we simply replace each capital letter of themessage with its corresponding ASCII encoding. However, thescrambling process described in the above table provides,cryptographically speaking, very little to no security at all and westrongly discourage its use in practice.
Keeping a secret with two keys¶
The Rivest, Shamir, Adleman (RSA) cryptosystem is an example of apublic key cryptosystem. RSA uses a public key toencrypt messages and decryption is performed using a correspondingprivate key. We can distribute our public keys, but forsecurity reasons we should keep our private keys to ourselves. Theencryption and decryption processes draw upon techniques fromelementary number theory. The algorithm below is adapted from page165 of [TrappeWashington2006]. It outlines the RSA procedure forencryption and decryption.
- Choose two primes (p) and (q) and let (n = pq).
- Let (e in ZZ) be positive such that(gcd big( e, varphi(n) big) = 1).
- Compute a value for (d in ZZ) such that(de equiv 1 pmod{varphi(n)}).
- Our public key is the pair ((n, e)) and our private key is thetriple ((p,q,d)).
- For any non-zero integer (m < n), encrypt (m) using(c equiv m^e pmod{n}).
- Decrypt (c) using (m equiv c^d pmod{n}).
The next two sections will step through the RSA algorithm, usingSage to generate public and private keys, and perform encryptionand decryption based on those keys.
Generating public and private keys¶
Positive integers of the form (M_m = 2^m - 1) are calledMersenne numbers. If (p) is prime and (M_p = 2^p - 1) is alsoprime, then (M_p) is called a Mersenne prime. For example, 31is prime and (M_{31} = 2^{31} - 1) is a Mersenne prime, as can beverified using the command is_prime(p). This command returnsTrue if its argument p is precisely a prime number;otherwise it returns False. By definition, a prime must be apositive integer, hence is_prime(-2) returns Falsealthough we know that 2 is prime. Indeed, the number(M_{61} = 2^{61} - 1) is also a Mersenne prime. We can use(M_{31}) and (M_{61}) to work through step 1 in the RSA algorithm:
A word of warning is in order here. In the above code example, thechoice of (p) and (q) as Mersenne primes, and with so many digits farapart from each other, is a very bad choice in terms of cryptographicsecurity. However, we shall use the above chosen numeric values for(p) and (q) for the remainder of this tutorial, always bearing in mindthat they have been chosen for pedagogy purposes only. Refer to[MenezesEtAl1996],[Stinson2006], and[TrappeWashington2006]for in-depth discussions on the security of RSA, or consult otherspecialized texts.
For step 2, we need to find a positive integer that is coprime to(varphi(n)). The set of integers is implemented within the Sagemodule sage.rings.integer_ring. Various operations onintegers can be accessed via the ZZ.* family of functions.For instance, the command ZZ.random_element(n) returns apseudo-random integer uniformly distributed within the closed interval([0, n-1]).
We can compute the value (varphi(n)) by calling the sage functioneuler_phi(n), but for arbitrarily large prime numbers (p) and (q),this can take an enormous amount of time. Indeed, the private keycan be quickly deduced from the public key once you know (varphi(n)),so it is an important part of the security of the RSA cryptosystem that(varphi(n)) cannot be computed in a short time, if only (n) is known.On the other hand, if the private key is available, we can compute(varphi(n)=(p-1)(q-1)) in a very short time.
Using a simple programming loop, we can compute therequired value of (e) as follows:
As e is a pseudo-random integer, its numeric value changesafter each execution of e=ZZ.random_element(phi).
To calculate a value for d in step 3 of the RSA algorithm, we usethe extended Euclidean algorithm. By definition of congruence,(de equiv 1 pmod{varphi(n)}) is equivalent to
where (k in ZZ). From steps 1 and 2, we already know the numericvalues of (e) and (varphi(n)). The extended Euclidean algorithmallows us to compute (d) and (-k). In Sage, this can be accomplishedvia the command xgcd. Given two integers (x) and (y),xgcd(x,y) returns a 3-tuple (g,s,t) that satisfiesthe Bézout identity (g = gcd(x,y) = sx + ty). Having computed avalue for d, we then use the commandmod(d*e,phi) to check that d*e is indeed congruentto 1 modulo phi.
Rsa Key Generation Algorithm Explained Simply 4
Thus, our RSA public key is
and our corresponding private key is
Encryption and decryption¶
Suppose we want to scramble the message HELLOWORLD using RSAencryption. From the above ASCII table, our message maps to integersof the ASCII encodings as given below.
Concatenating all the integers in the last table, our message can berepresented by the integer
There are other more cryptographically secure means for representingour message as an integer. The above process is used fordemonstration purposes only and we strongly discourage its use inpractice. In Sage, we can obtain an integer representation of ourmessage as follows:
To encrypt our message, we raise (m) to the power of (e) and reducethe result modulo (n). The command mod(a^b,n) first computesa^b and then reduces the result modulo n. If the exponentb is a “large” integer, say with more than 20 digits, thenperforming modular exponentiation in this naive manner takes quitesome time. Brute force (or naive) modular exponentiation isinefficient and, when performed using a computer, can quicklyconsume a huge quantity of the computer’s memory or result in overflowmessages. For instance, if we perform naive modular exponentiationusing the command mod(m^e,n), where m, n and e are asgiven above, we would get an error message similar to the following:
There is a trick to efficiently perform modular exponentiation, calledthe method of repeated squaring, cf. page 879 of [CormenEtAl2001].Suppose we want to compute (a^b mod n). First, let(d mathrel{mathop:}= 1) and obtain the binary representation of (b),say ((b_1, b_2, dots, b_k)) where each (b_i in ZZ/2ZZ). For(i mathrel{mathop:}= 1, dots, k), let(d mathrel{mathop:}= d^2 mod n) and if (b_i = 1) then let(d mathrel{mathop:}= da mod n). This algorithm is implemented inthe function power_mod. We now use the function power_mod toencrypt our message:
Thus (c = 630913632577520058415521090) is the ciphertext. To recoverour plaintext, we raise c to the power of d and reduce theresult modulo n. Again, we use modular exponentiation viarepeated squaring in the decryption process:
Notice in the last output that the value 72697676798779827668 is thesame as the integer that represents our original message. Hence wehave recovered our plaintext.
Acknowledgements¶
- 2009-07-25: Ron Evans (Department of Mathematics, UCSD) reporteda typo in the definition of greatest common divisors. The reviseddefinition incorporates his suggestions.
- 2008-11-04: Martin Albrecht (Information Security Group, RoyalHolloway, University of London), John Cremona (MathematicsInstitute, University of Warwick) and William Stein (Department ofMathematics, University of Washington) reviewed this tutorial. Manyof their invaluable suggestions have been incorporated into thisdocument.
Bibliography¶
| [CormenEtAl2001] | T. H. Cormen, C. E. Leiserson, R. L. Rivest, andC. Stein. Introduction to Algorithms. The MIT Press, USA, 2ndedition, 2001. |
| [MenezesEtAl1996] | (1, 2) A. J. Menezes, P. C. van Oorschot, andS. A. Vanstone. Handbook of Applied Cryptography. CRC Press, BocaRaton, FL, USA, 1996. |
| [Stinson2006] | (1, 2) D. R. Stinson. Cryptography: Theory and Practice.Chapman & Hall/CRC, Boca Raton, USA, 3rd edition, 2006. |
| [TrappeWashington2006] | (1, 2, 3) W. Trappe and L. C. Washington. Introductionto Cryptography with Coding Theory. Pearson Prentice Hall, UpperSaddle River, New Jersey, USA, 2nd edition, 2006. |
The RSA Homonym
We are RSA®, the security company, also known as RSA Security, a Dell Technologies company. We offer software solutions to mitigate security risk in this ever-changing digital world and economy. We also organize one of the largest security conferences in the world: RSA Conference. Our 2020 edition is just about to start.
There is also RSA, the algorithm. It is used to encrypt and protect data in a wide range of applications, from data in transit to data at rest. The algorithm can be used to encrypt or generate digital signatures. That digital signature can then be incorporated within a simple file, and some other metadata, to create what is an RSA certificate. The RSA algorithm is among the most widely used encryption and signature algorithms in the world, if not the most widely used.
Did RSA – the company – invent RSA – the algorithm? No. Ron Rivest, Adi Shamir and Leonard Adleman invented the RSA algorithm in the late '70s while at Massachusetts Institute of Technology (MIT). The subsequent patent for the algorithm was issued to MIT on Sept. 20, 1983 and licensed exclusively to RSA Security. The patent expired in September 2000.
Over the years, there has been much confusion between RSA Security and RSA the algorithm, including claims that 'RSA certificates' or 'RSA keys' are vulnerable. It is important to clarify that vulnerability claims are not about RSA Security nor are they about the RSA certificates issued in RSA Security products, but rather about poorly implemented cryptography resulting in insecure fundamental elements of the RSA algorithm.
That confusion, between the 'RSAs', worries people. It's ok. We are here to help.
Randomness and the RSA Algorithm
Entropy is randomness used by cryptographic systems to generate cryptographic keys. Good entropy is necessary to generate strong keys.
A recent story highlights the results of using bad entropy on the RSA key generation itself. The report concludes that 'device manufacturers, website and network administrators, and the public at large [need] to consider security, and especially secure random number generation, as a paramount requirement of any connected system'. The fact of the matter is, this has been known for decades and is the foundation of secure cryptographic systems. However, the importance of good entropy and randomness in secure cryptographic systems to be explained.
The effectiveness of the RSA algorithm relies on, among other things, the ability to randomly select two large prime numbers that we call p and q.
A prime number is one that can only be divided evenly by 1 and itself, like 19.
But what exactly is a large number? Let's see...
A 32-bit number is a number represented using 32 binary digits. Its maximum value is (232 - 1) = 4294967295. That number contains 10 decimal digits.
A 2048-bit number is a number represented using 2048 bits. Its maximum value is (22048 - 1) = ~3.23e+616. That number is too long to be written here and contains 617 digits.
For the purpose of this example a 'large number' is a number that contains 617 digits.
If there are 50 Million known primes for a 10-digit number, how many primes are there for numbers made of 617 digits? I don't have the answer, but there are a lot of possibilities. Now, randomly pick two primes in this immense pool of prime numbers. These are your p and q. The probability of randomly picking the same p or q repeatedly is very unlikely, unless what you believed to be random is not actually random.
In computer programming, good randomness comes from algorithms known as Deterministic Random Bit Generators (DRBGs). These algorithms are thoroughly reviewed by security researchers, mathematicians, universities, etc., as well as the National Institute of Standards and Technology (NIST). NIST adds approved DRBGs to a whitelist, requiring US and Canadian Federal Agencies to use these whitelisted DRBGs.
DRBGs require input data, referred to as entropy seed, which comes from a source (or sources) generating events that don't present any sign of pattern similarity or predictability. If the source meets these simple criteria, it is known to be a 'good entropy source'. Easier said than done, though. We'll come back to that later. When using a good entropy source to seed a DRBG, the output produced by the DRBG can be considered cryptographically safe random. This cryptographically safe random can be used to generate encryption keys, or randomly selecting p and q. If the seed to your DRBG is always the same, p and q will always be the same, resulting in the same RSA key. If the seed to your DRBG can be predicted, then p and q can be predicted, making it easy to calculate your RSA key that ought to be kept private.
As said earlier, it is easier said than done to have a source that shows no signs of pattern similarity or predictability. When one million webcams are built the same way, with the same cheap components to keep the price down, how can one webcam be different enough from the next one and produce different entropy? If they can't produce different entropy, it means those webcams will seed the same predictable entropy data to the DRBG, generating the same output, hence generating identical and predictable random numbers. Actually, 'predictable numbers' leading to predictable or identical RSA keys is the topic of the recent article mentioned earlier.
The RSA Algorithm Requires Good Entropy; RSA Products Use Good Entropy
What is a good source of entropy then? As of today, a good source of entropy is one that will pass the NIST Entropy Assessment test. NIST built a test suite that will run statistical tests on your entropy source. The source code of this tool is available at https://github.com/usnistgov/SP800-90B_EntropyAssessment. If a source passes the test, it is considered a good source.
How about RSA Security products? What entropy sources do they use? This is a really good question. RSA Security products use a variety of cryptographic modules, including but not limited to RSA BSAFE® Crypto-C Micro Edition (Crypto-C ME) that has its entropy source tested against NIST's tests), and RSA BSAFE Crypto-J (Crypto-J) that relies on the Java Virtual Machine it runs in for entropy. As software cryptographic modules, the BSAFE toolkits must rely on what is available on the system to gather entropy. In Crypto-C ME, all noise sources are individually tested with NIST's tool. If a source does not generate enough entropy, we remove it. If we were to rely on a single source, this would become a single point of failure. Should this source become bad, or predictable, or compromised, the whole security falls apart. When multiple good entropy sources are combined and conditioned before being seeded to the DRBG, the risk of having your DRBG compromised is reduced. Crypto-C ME will not generate DRBG output unless sufficient entropy has been obtained to seed the DRBG fully. In other words, Crypto-C ME should never generate weak keys. Crypto-J will, by default, force a reseeding using the JVM's implementation-specific entropy source to ensure a random is created with sufficient entropy for the requested DRBG algorithm.
Rsa Algorithm Explained
Not only do BSAFE toolkits ensure they have good entropy on all supported platforms, they also provide DRBG algorithms that have been approved and validated by NIST. Application developers can have peace of mind when generating RSA keys, or any secure random number, when BSAFE toolkits are used correctly.
Rsa Key Generation Algorithm
Remember, RSA (the company) and RSA (the algorithm) are homonyms. Please don't get them confused.