2.1 Unit 2: Number Theory and Cryptography

This is the beginning of Unit 2 in this Discrete Mathematics II course.

The material in this unit comprises 23% of the high-stakes assessment and includes such concepts as:

• Division algorithm
• Modular arithmetic and multiplication
• Congruence mod n
• Prime factorization, greatest common divisor (GCD), and least common multiple (LCM)
• Number representations
• Fast exponentiation

2.2 Module 4: Divisibility and Modular Arithmetic

This page marks the beginning of Module 4. This module contains three lessons:

• The division algorithm
• Modular arithmetic and multiplication
• Congruence modulo

Integer division

The first mathematical objects most people encounter are integers. Integers are a natural component of everyday life and easy to understand. Even so, some of the deepest mathematical mysteries are found in number theory, the branch of mathematics concerned with the study of integers. 

In integer division, the input and output values must always be integers. For example, when the number 9 is divided by 4, the answer is 2 with a remainder of 1, instead of 2.25. In this chapter, the term “number” refers to an integer as opposed to a real number.

Divides

Let x and y be two integers. Then x divides y (denoted x|y) if there is an integer k such that y = kx. “x does not divide y” is denoted by x ∤ y. If x divides y, then y is said to be a multiple of x, and x is a factor or divisor of y.

 A linear combination of two numbers is the sum of multiples of those numbers. For example, 3x – 7y and -2x + 4y are both linear combinations of x and y.

In most situations, the number in front of the variable, or the coefficient, can be any real number. 

Quotients and remainders

If x does not divide y, then there is a non-zero remainder when x is divided into y. The following theorem, called the Division Algorithm, states that the result of the division (the quotient) and the remainder are unique. 

Lesson summary

Now that you have completed this lesson you should be able to calculate the remainder of a given modulus and divisor using the division algorithm.
Take a moment to think about what you’ve learned in this lesson:

• The Division Algorithm is the result of the division of two integers. The quotient and the remainder are unique.
• The Division Algorithm works with positive integers only; if any of the inputs is negative, the quotient will be negative per the rules of division.
• The operations div and mod produce the quotient (q) and the remainder (r). The divisor is d.
  • The quotient is computed by n div d; q = n div d
  • The remainder is computed by n mod d; r = n mod d
• To compute the remainder using modular division, divide the quotient by n until the remainder is less than n. The remainder is the result. For example, to calculate 38 mod 5, calculate 38 ÷ 5. Five divides into 38 seven times with a remainder of 3. So the quotient is 7 and the remainder is 3. Therefore 38 mod 5 = 3.

Lesson introduction

In the previous lesson you learned the division algorithm for integers and the operations of div and mod. In this lesson, you will be expanding your knowledge of this concept by incorporating the processes of addition and multiplication.

Modulo addition and multiplication

If we select an integer n > 1, then mod n can be seen as a function that takes a single integer x as input and outputs x mod n, resulting in a number from the set {0, 1, 2, …, n-1}. For example, fix n = 5. The mod 5 operation maps 12 to 2 and -11 to 4.

The operation defined by adding two numbers and applying modulo n to the result is called addition modulo n. The operation defined by multiplying two numbers and applying modulo n to the result is called multiplication modulo n

Lesson summary

Now that you have completed this lesson you should be able to calculate the result of an expression with modular addition or multiplication.
Take a moment to think about what you’ve learned in this lesson:

• Addition and multiplication can occur even with modular operators.
  • To compute modular addition follow these steps: add the integers, then apply the modulo. For example, 3 mod 7 + 38 mod 7 = 41 mod 7 = 6.
  • To compute modular multiplication follow these steps: multiply the integers, then apply the modulo. For example, (10 mod 3) (7 mod 3) = 70 mod 3 = 1.
• The modular operation is completed as the last step in the process.

2.5 Lesson: Congruence modulo n

Lesson introduction

Do you remember the concept of coterminal angles from your trigonometry studies on the unit circle? For example, a 40∘ angle is coterminal with a 400∘ angle, and the two angles have the same measure. 

Congruence modulo n

For a fixed n, we can define an equivalence relation over the integers in which two integers x and y are equivalent if and only if x mod n = y mod n. The equivalence relation defined by equality modulo n has its own name and notation:

Congruence modulo n

Let n be an integer greater than 1. Let x and y be any two integers. Then x is congruent to y modulo n if x mod n = y mod n. The fact that x is congruent to y modulo n is denoted

x  ≡  y (mod n).

The theorem below provides an alternate way to determine if two numbers are congruent mod n.

Alternate characterization of congruence modulo n

Let n be an integer greater than 1. Let x and y be any two integers. Then x  ≡  y (mod n) if and only if n|(x – y).

The illustration below shows the equivalence classes modulo 5. Each integer is represented by a dot on the real line. Integers that are congruent modulo 5 are colored with the same color:

Arithmetic expressions modulo n

In computing arithmetic expressions modulo n, it is sometimes convenient to take intermediate results modulo n before the final result is obtained. For example, one way to compute the expression 13¹⁵⁹ mod 71 is to first compute 13¹⁵⁹ and then take the result modulo 71. 

Alternative notation for modular arithmetic.

Instead of using the notation x = y (mod n) we can state beforehand that our arithmetic will all be carried out modulo n by saying that we are doing the operations in Z_n. Typically, Z refers to the set of integers along with the usual arithmetic operations (+, -, ×, ÷), while Z_n refers to the set of integers {0, 1, 2,…, n – 1} along with the arithmetic operations mod n (+ mod n, – mod n, × mod n). Note that there is no ÷ mod n, but we will see in lesson 2.12 that is sometimes possible to find integers that multiply together to produce 1.

Lesson summary

Now that you have completed this lesson you should be able to analyze a set of integers for congruence using modulo arithmetic or multiplication.
Take a moment to think about what you’ve learned in this lesson:

• Two integers x and y are equivalent if and only if x mod n = y mod n.
• Congruence of two integers is denoted by x ≡ y (mod n) and is only true if n|(x − y). In otherwords, 17 and 92 are equivalent mod 5. 17 mod 5 = 2 and 92 mod 5 = 2. The difference between 92 and 17 is a multiple of 5, 75. In formal notation, 17 ≡ 92 (mod 5) is true if and only if 5|(92 − 17) or 5|75-which it does.
• Intermediate results can be useful in the computation of very large values. Therefore, the modular operation does not necessarily have to be performed after the multiplication or addition processes, but can be utilized throughout a computation without changing the final result.

2.6 Module 5: Prime Factorization, GCD, and Euclid’s Algorithm

This page marks the beginning of Module 5. This module contains six lessons:

• Prime factorization
• Greatest common denominators (GCD) and least common multiple (LCM)
• Factoring and primality testing
• Euclidean algorithm
• Extended Euclidean algorithm
• Multiplicative inverse and Euclidean algorithm

2.7 Lesson: Prime factorizations

Lesson introduction

Why should we care about very large (over 500 digits long) prime numbers? Well, all of our everyday encryption/decryption methods used in any website where you log in with a username and password rely on secure transfer of information using “keys,” which are hard-to- find prime numbers. 

Prime and composite numbers

A number p is prime if it is an integer greater than 1 and its only factors are 1 and p. A positive integer is composite if it has a factor other than 1 or itself. Note that every integer greater than 1 is either prime or composite.

Prime numbers are the basic building blocks of all integers. Every positive integer greater than one can be expressed as a product of primes called its prime factorization.

The fact that every integer greater than one has a unique prime factorization is central to number theory and is called The Fundamental Theorem of Arithmetic.

A non-decreasing sequence is a sequence in which each number is equal to or greater than the one that came before. 

The multiplicity of a prime factor p in a prime factorization is the number of times p appears in the product of primes. For example, in the prime factorization of 120 given above, the multiplicity of 2 is 3 and the multiplicity of 3 is 1. 

Lesson summary

Now that you have completed this lesson you should be able to determine the prime factorization of a given number using exponential notation.
Take a moment to think about what you’ve learned in this lesson:

• The fundamental theorem of arithmetic states that every positive integer greater than 1 can be expressed as a unique product of prime numbers.
• A non-decreasing sequence (e.g., 1, 1, 2, 3, 17) can have repeated values as long as the values to the right are larger or equal to the values on the left.
• Multiplicity is just a term referring to the number of times a value repeats itself in multiplication. For example, the prime factorization of 40 is 2 x 2 x 2 x 5. The factor 2 has a multiplicity of 3.

2.8 Lesson: Greatest common division and least common multiple

Lesson introduction

The previous lesson provided a refresher on prime factorization. Prime factorization is important because it is used to determine the greatest common divisor (GCD) and the least common multiple (LCM) of integers, which is also needed to develop encryption keys. Since it may have been awhile since you studied GCD and LCM, this lesson will serve as a refresher.

.

Greatest common divisors and least common multiples

The prime factorization can be used to determine the greatest common divisor and the least common multiple of two integers. These are defined below:

Greatest common divisor and least common multiple

The greatest common divisor (GCD) of non-zero integers x and y is the largest positive integer that is a factor of both x and y.

The least common multiple (LCM) of non-zero integers x and y is the smallest positive integer that is an integer multiple of both x and y.

Two numbers are said to be relatively prime if their greatest common divisor is 1.

Lesson summary

Now that you have completed this lesson you should be able to determine the GCD and LCM of two numbers.
Take a moment to think about what you’ve learned in this lesson:

• The GCD is the largest number that divides the given numbers. To determine the GCD:
  • Find the prime factors of each number, using prime factorization and exponents.
  • Write both values as the product of the same prime values.
    • Identify those prime factors that both numbers have in common.
    • To make a common set you may need to use an integer raised to the power 0, since it is equal to 1 and will not change the product of the prime factors.
  • Take the smallest exponent of each factor and multiply them.
• The LCM is the lowest common multiple of given numbers. To determine the LCM:
  • Find the prime factors of each number, using prime factorization and exponents.
  • Write both values as the product of the same prime values.
    • Identify those prime factors that both numbers have in common.
    • To make a common set you may need to use an integer raised to the power 0, since it is equal to 1 and will not change the product of the prime factors.
  • Take the maximum exponent of each factor and multiply them.

2.9 Lesson: Factoring and primality testing

Lesson introduction

In the previous lesson you learned how to use prime factorization to determine the GCD and LCM. If you had a very large number this would be a long and tedious task. For example, in cyber security 200 to 500 digit numbers are commonly used.

Primality testing

The integers considered so far are relatively small, which has made recognizing whether the integers are prime or composite easier.

A more precise description of the algorithm is given below. A brute force algorithm solves a problem by exhaustively searching all possible solutions without using an understanding of the mathematical structure in the problem to eliminate steps.

The next theorem, called the Prime Number Theorem, provides a much stronger statement. The Prime Number Theorem says how dense primes numbers are among the integers.

Lesson summary

Now that you have completed this lesson you should be able to find the number of primes between numeral one and a given number using the brute force algorithm or the prime number theorem.
Take a moment to think about what you’ve learned in this lesson:

• The brute force algorithm uses an exhaustive method of dividing the number by every number less than the number. Using this algorithm, start with 2|N. If 2|N yields a result, the N is composite. If not, then continue to test 3|N etc. Continue this process until either N is reached (N is prime) or an integer less than N is found (N is composite).
• To shorten the number of possible iterations of divisors, apply the small factors theorem. According to this theorem, if a number is composite, then the largest possible factor will be at most the square root of the number. For example, if you were searching for factors of 29, using the brute force method you would divide by 2, 3, 4, 5, 6, 7, 8, 9, . . . , 27, 28, before determining that 29 was prime. However, with the small factors theorem, using the square root of 29, ≈ 5.4, we would only need to divide by 2, 3, 4, and 5 before deciding 29 was prime.
• The prime number theorem addresses the issue of how likely finding a prime number value is out of a range of numbers and provides a formula for determining the density of prime numbers within a range of integers. For example, if you needed to know how likely it is that you will randomly find a prime number between 2 and 1,000,000, the prime number theorem states the likelihood will be 1/ln(1,000,000) ≈ 0.072 or about a 7.2% chance of finding a prime number between 2 and one million. (As a reminder, ln is the abbreviation for natural logarithm.)

2.10 Lesson: Euclidean algorithm

Lesson introduction

In the previous lesson you learned how to use brute force algorithm to compute the GCD of two integers without using prime factorization. But there is an even easier method that uses the concept of modular arithmetic which you learned in the previous module

Lesson summary

Now that you have completed this lesson you should be able to compute the GCD of two numbers using the Euclidean algorithm.
Take a moment to think about what you’ve learned in this lesson:

• The greatest common divisor theorem [GCD(x, y) = GCD(y mod x, x)], sometimes referred to as Euclid’s algorithm, shows that a number k is a factor of both x and y if and only if it is a factor of both x and (y mod x). This is an iterative process, where the variables are reassigned the smaller value results from a previous iteration until y mod x = 0. The point of this process is to divide the divisor by the remainder over and over again (iteratively) until the remainder is 0-the final divisor is the GCD.
• Using modular arithmetic makes the second value y much smaller, and since the result would be the same with either the original or the smaller modular value, the computation is less cumbersome.
  • For example: Find GCD (32, 48). By inspection you may notice the largest divisor of 32 and 48 is 16. We can verify this using Euclid’s algorithm.
    • First iteration: x = 32 and y = 48, find y mod x. 48 mod 32 ≡ 16 → answer not 0, so continue.
    • Second iteration: now x = 16 and y = 32. Again, find y mod x. 32 mod 16 ≡ 0, so stop the process. The last value of x, 16, is the GCD (32, 48). To verify: 16 x 2 does equal 32 and 16 x 3 does equal 48.

2.11 Lesson: Extended Euclidean algorithm(I still don’t get this)

Lesson introduction

In the previous lesson you learned how to find the GCD using either the brute force algorithm or Euclid’s algorithm. Although more efficient, both are still quite involved and are a rather long process. 

The extended Euclidean algorithm

The GCD of x and y can be expressed as a linear combination of x and y:

The values for s and t in the theorem above can be found by a series of substitutions using the equation from each iteration. The algorithm used to find the coefficients, s and t, such that GCD(x, y) = sx + ty, is called the Extended Euclidean Algorithm.

Lesson summary

Now that you have completed this lesson you should be able to perform the extended Euclidean algorithm on two given integers.
Take a moment to think about what you’ve learned in this lesson:

• The extended Euclidean algorithm is not really an “extended” process, it is an add-on process leading to some important ideas used in cryptography.
• The extended Euclidean algorithm states the GCD of x and y can be expressed as a linear combination of x and y [GCD(x, y) = sx + ty].
• To apply the extended Euclidean algorithm, find the GCD (x, y). Then show that there is an equation that exists where you can write x times some number s plus y times some number t that is equal to the GCD. For example, if x = 874 and y =2415, GCD (874, 2415) = s874 + t2415. To apply the extended Euclidean algorithm find s and t integers. To find the integers, solve the equation r = y – (y div x) x. Recall (y div x) is just the quotient d, so the equation can be written r= y – dx. In this example GCD is 23, s = 47 and t = -17. The equation for the GCD (874, 2415) is 23 = 47(874) – 17(2415).

2.12 Lesson: Multiplicative inverse and Euclidean algorithm(Again wtf)

Lesson introduction

Recall that in cryptography the biggest concern is how quickly an encryption can be decrypted. Some mathematical process used in decryption are similar to arithmetic inverse operations. 

The multiplicative inverse mod n

Multiplicative inverse mod n

A multiplicative inverse mod n (or just inverse mod n) of an integer x, is an integer s ∈ {1, 2, …, n-1} such that sx mod n = 1.

Alternatively, we could say that s is the multiplicative inverse of x in Z_n.

Lesson summary

Now that you have completed this lesson you should be able to compute the multiplicative inverse of the given integer in the modulus.
Take a moment to think about what you’ve learned in this lesson:

• In ordinary arithmetic the definition of a multiplicative inverse is the product of a number and its multiplicative inverse is always 1.
• In modular arithmetic, an integer x has a multiplicative inverse mod n, s. If the product of integer x and s equal 1 mod n, then x and s are multiplicative inverses.
• An interesting characteristic of multiplicative inverses mod n is that they must be relatively prime. It can be shown that not every integer has an inverse mod n. For example, 10 does not have an inverse using modulo 6, but it does using modulo 7. This gives a small hint into what lies in the upcoming lessons where we begin to put all this modular arithmetic together with the quest for large prime numbers.

2.13 Module 6: Number Representation in Other Bases

This page marks the beginning of Module 6. This module contains three lessons:

• Decimal and binary numbers
• Hexadecimal numbers
• Base b expansion

2.14 Lesson: Number representation- Decimal and binary numbers

Lesson introduction

Modern number systems use “place value;” that is, each digit has a value dependent upon its place in the number. 

Number representation

Our number system represents integers in decimal notation in which each number is represented as sequences of digits. 

A digit in binary notation is called a bit. In binary notation, each place value is a power of 2. For example, the binary number 1011 corresponds to the decimal number 1·2³ + 0·2² + 1·2¹ + 1·2⁰ = 11. In fact, any integer greater than 1 can be used as the base of a number representation system. Numbers represented in base b require b distinct symbols and each place value is a power of b. 

The representation of n base b is called the base b expansion of n and is denoted by (a_ka_k-1…a₁a₀)_b. The following animation shows how to convert the base b expansion of a number into its decimal expansion.

Lesson summary

Now that you have completed this lesson you should be able to find an equivalent binary or decimal number representation for a given decimal or binary number.
Take a moment to think about what you’ve learned in this lesson:

• The binary number system has only two digits, 0 and 1, and the digits are referred to as “bits.”
• Each place value is a power of 2.
• Numbers in base b require b distinct symbols and each place value is a power of b. The number representation theorem says that any number, n base b, can be uniquely written in a series or decimal expansion of each digit multiplied by its place value.
• For example, to convert a binary number (e.g., 10012 ) to a decimal number, follow these steps:
  • Work from left to right to determine the place value. The first digit has a base 2 place value of 23 , next is 22 , 21 , then 20 .
  • Multiply the digit by its base 2 place value. (1 x 23 + 0 x 22 + 0 x 21 + 1 x 20 = 1 x 8 + 0 x 4 + 0 x 2 + 1 x 1 = 910 )

2.15 Lesson: Number representation- Hexadecimal numbers

Lesson introduction

In the previous lesson you learned about binary numbers and how to convert from the binary number system (base 2) to the decimal system (base 10.) There is another important number representation system that is used in computer science: the hexadecimal system.

Hexadecimal numbers

In hexadecimal notation (or hex for short), numbers are represented base 16. The 16 digits in hex are the usual 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 along with A, B, C, D, E, F. The table below shows each hexadecimal digit, its decimal encoding, and its binary encoding. Leading zeroes are added to the binary encodings so that all the encodings have exactly 4 bits.

Lesson summary

Now that you have completed this lesson you should be able to find an equivalent hexadecimal or decimal number representation for a given number in the hexadecimal or decimal numeral system.
Take a moment to think about what you’ve learned in this lesson:

• The hexadecimal (hex) number system has sixteen digits 0-9 and A-F. Each digit in a hex number is a power of 16.
• A byte is 8 bits (binary digits). Each byte can be represented by a 2-digit hexadecimal number.
• To convert the hex number, 3AF16 to a decimal value multiply each digit by its place value: 3 x 162 + A x 161 + F x 160 = 3 x 162 + 10 x 161 + 15 x 160 = 3 x 256 + 10 x 16 + 15 x 1 = 94310

2.16 Lesson: Base b expansion

Lesson introduction

As you learned in the previous lessons, converting numbers from hexadecimal or binary to decimal is a fairly straight-forward process;

Lesson summary

Now that you have completed this lesson you should be able to find the number of digits to express a number using base b expansion.
Take a moment to think about what you’ve learned in this lesson:

• To convert a decimal value to a number n, base b requires an iterative process of the mod and div functions. The smallest valued digits (right-most digit in the iteration) is found using n mod b. The next digits are determined using n div b in the iteration. For example, let’s convert the decimal value 482 to a base 7 number.

2.18 Lesson: Fast exponentiation

Lesson introduction

Once again computer scientists are concerned with making the processing of an algorithm as efficient (fast) as possible. If exponentiation is part of the algorithm’s process, having the ability to exponentiate number values quickly is vital. 

Fast exponentiation

Suppose you wanted to compute x^y, for positive integers x and y. Computing exponents is, in fact, an important step in the RSA cryptosystem discussed later. 

A formal specification of the algorithm to compute x^y is given below. The caption describes the algorithm as an iterative algorithm for fast exponentiation. An iterative algorithm uses a loop to accomplish repeated operations in contrast with a recursive algorithm which uses recursion.

Lesson summary

Now that you have completed this lesson you should be able to analyze an iterative algorithm for fast Exponentiation.
Take a moment to think about what you’ve learned in this lesson:

• The number of loops in the algorithm is the number of bits in the binary representation of the exponent.
• Review the iterative algorithm for fast exponentiation in this lesson. Make sure you understand how the values change through each loop of the process.
• The following are the steps in fast integer exponentiation:
  • Create a binary expansion of the exponent.
  • Use this expansion as the new exponent of the base.

2.19 Lesson: Modular exponentiation

Lesson introduction

If you thought fast exponentiation was efficient, you are in for a treat.

Modular exponentiation

The variables s and p in the exponentiation algorithm could potentially become very large if the exponent y is a large number. In fact, s and p could become so large that their values exceed the maximum value that can be stored in a computer variable.

Lesson summary

Now that you have completed this lesson you should be able to compute modular exponentiation for a given number in a given base.
Take a moment to think about what you’ve learned in this lesson:

• Iterative fast exponentiation (modular exponentiation) applies intermediate modular arithmetic steps that keep the values within the iterative process smaller.
• The number of loops in the iterative algorithm is the number of bits in the binary representation of the exponent.
• Review the “Iterative Algorithm for Fast Exponentiation” example. Make sure you understand how the values change through each loop of the process.
• The Participation Activity 2.18.3, provides several examples of how to “analyze” the algorithm at various steps (iterations) in the process. Make sure you can follow the iterations and answer each of those questions correctly. Contact the course instructor if you need additional assistance.

2.20 Module 8: Mathematical Foundations of Encryption

This page marks the beginning of Module 8. This module contains four lessons:

• Introduction to cryptography
• Encryption and decryption
• RSA encryption
• RSA decryption

2.21 Lesson: Introduction to cryptography

Lesson introduction

In this lesson you will finally begin a brief study of cryptography and cryptographic systems. First, some important vocabulary needs to be explained and memorized.

Cryptography

Cryptography is the science of protecting and authenticating data and communication.

A cryptosystem is a system by which a sender sends a message to a receiver. The sender encrypts the message so that if an eavesdropper learns the transmitted message, she will be unable to recover the original message. The unencrypted message is called the plaintext and the encrypted message is called the ciphertext. The receiver must have a secret key that allows him to decrypt the ciphertext to obtain the original plaintext.

Lesson summary

Now that you have completed this lesson you should be able to explain the general process for encryption and decryption.
Take a moment to think about what you have learned in this lesson:

• Review the following terms and definitions:
  • Encrypt: the process of transforming information or data into a code to prevent unauthorized access
  • Decrypt: the process of transforming data that has been rendered unreadable through encryption back to its unencrypted form
  • ciphertext: an encrypted message
  • Plaintext: an unencrypted message
  • Key: an unpredictable (typically large and random) string of numbers to decrypt an encrypted message.
• The following is a description of a cryptosystem process:
  • A sender encrypts a plaintext message.
  • An eavesdropper on the encrypted message will not be able to read the ciphertext.
  • The receiver will read the ciphertext message after applying a secret key to decrypt the message back into plaintext.
• Cryptographers will use the name “Alice” to reference the sender, the name “Bob” to reference the receiver, and the name “Eve” to reference the eavesdropper.

2.22 Lesson: Encryption and decryption

Lesson introduction

At its most basic level cryptography, or “codes,” are messages whose text has been substituted for symbols, other text, or numbers. In modern day cryptographic systems messages are converted to integer values. In this course, integer m will represent the message “Alice” needs to send to “Bob.”

Encryption and decryption functions

Encrypting a plaintext message requires computing a mathematical function with the integer plaintext m as the input and the ciphertext c as the output. Decrypting the plaintext therefore is computing the inverse of the encryption process. 

The simple encryption scheme presented here is an example of symmetric key cryptography. In a symmetric key cryptosystem, Alice and Bob must meet in advance (or communicate over a reliably secure channel) to decide on the value of a shared secret key.

Lesson summary

Now that you have completed this lesson you should be able to determine a corresponding encrypted message (or decrypted message) from a given encryption (or decryption scheme) and a message to send (or an encrypted message).
Take a moment to think about what you’ve learned in this lesson:

• To accurately map plaintext (unencrypted message) to ciphertext (encrypted message) and then reverse the process (decryption) requires a mathematical function that is one-to- one. Each input maps to one and only one output, and each output maps back to one and only one input.
• One simple cryptosystem uses modular arithmetic to encode and decode a plaintext message. Specifically, ciphertext can be expressed as c = (m + k) mod N; where m is the plaintext message, N is an integer, and k is a secret value known only to the sender and receiver. Then the decryption function can be expressed as m = (c – k) mod N. Note that the addition/subtraction inverse operations use the secret value k.
• The systems used in this lesson are private key cryptosystems. In a private key system both Bob and Alice must meet to decide upon the value of the secret key-in our example the value of k-prior to sending encrypted messages.
• Pay attention to the prime number used in Participation Activity 2.22.4. The author chose N = 3391, which is a prime number. This will be important in upcoming lessons.

2.23 Lesson: RSA encryption

Lesson introduction

In the previous lesson you learned about the encryption and decryption process in a private key cryptosystem. However, private key cryptography, while perfectly secure, can be impractical in everyday use.

Public key cryptography

The simple cryptosystem described earlier uses symmetric key cryptography, where Alice and Bob need to meet either in person or communicate by a perfectly secure channel in order to agree on the value of a shared key for encryption and decryption.

In public key cryptography, Bob has an encryption key that he provides publicly so that anyone can use it to send him an encrypted message. Bob holds a matching decryption key that he keeps privately to decrypt messages.

RSA

We present now the most widely used public key cryptosystem developed by Rivest, Adelman, and Shamir in 1978, called the RSA cryptosystem after the initials of the inventors. 

RSA encryption

Now suppose that Alice would like to send a plaintext message m to Bob. The RSA scheme requires that m is an integer in Z_N and is not a multiple of p or q. Since p and q are primes with hundreds of digits, it is extremely unlikely that m is a multiple of primes p or q. Alice encrypts her plaintext using e and N to produce ciphertext c as follows:

Lesson summary

Now that you have completed this lesson you should be able to interpret an RSA encryption algorithm.
Take a moment to think about what you’ve learned in this lesson:

• To begin RSA encryption, two very large prime values are selected. The product of those numbers, N, and another value found through a GCD process, e, are the public encryption key. The private key used to decrypt the message, d, involves the multiplicative inverse process learned in the “Multiplicative Inverse and Euclidean Algorithm” lesson in this unit.
• Review “Preparation of public and private keys RSA” to ensure you understand all the steps required in the preparation of the values of N, e, and d for the public and private RSA keys.
• The RSA encryption process for a specific message involves the formula: �=�� mod � where m is the integer value of the message.

2.24 Lesson: RSA decryption

Lesson introduction

As previously mentioned, the formulas needed to encrypt and decrypt RSA encoded messages require large prime numbers to generate the public keys (values referred to as N and e) and private keys (the value d).

Lesson summary

Now that you have completed this lesson you should be able to interpret an RSA decryption algorithm.
Take a moment to think about what you’ve learned in this lesson:

• The RSA decryption process uses the formula: �=�� mod � to decrypt the ciphertext c, where d is the private key value and N is one of the public keys.
• Carefully review the end of lesson exercises. This exercise is very thorough in detailing the encryption/decryption process. For the decryption process, pay attention to step (e), which provides the intricate details involved in decrypting a very short 2-letter message.