(p.632) Mathematics Appendix
(p.632) Mathematics Appendix
In this appendix, we look at the basic mathematical concepts underlying some of the material in the book. We stress that study of this appendix is not required in order to read this book. The explanation of these ideas assumes little or no prior knowledge.
The topics covered in this appendix are:
• Decimal, binary, and hex;
• XOR;
• Modular arithmetic;
• Primes, coprimes, and greatest common divisors;
• Modular inverses;
• Why RSA works;
• Primitive elements; and
• Why ElGamal works.
A.1 Decimal, binary, and hex
Everyone is familiar with decimal numbers. These are the numbers we use every day and are the numbers we normally write and perform calculations with. Representing numbers in decimal is just one possible way of writing a number. There are many other ways of writing a number (for example, Roman numbers and Chinese characters). This section introduces two other ways of writing numbers: binary and hex. Binary and hex are particularly useful in digital communication. In fact, at the most fundamental level, binary numbers are the basis of all computing.
In this section, we make extensive use of the notation for exponentiation, as discussed in Section 1.6.1. For example, if we write 10^{7} (10 to the power 7), then we mean 10 multiplied by itself seven times:
Note that it is standard mathematical convention to say that any number raised to the power 0 is 1. Thus, for example, ${10}^{0}=1$.
(p.633) A.1.1 Decimal
Before explaining binary or hex, it is first necessary to understand some of the principles behind the more familiar decimal numbers.
Writing a Number in Decimal
Consider the number 359. What do each of 3, 5, and 9 actually represent? Observe that:
All we have done in these last three lines is to rewrite the number 359 in a form which shows how it can be represented as a sum of multiples of powers of ten. This is why our most familiar numbers are often referred to as decimal numbers: the digits we use to write them indicate the multiples of powers of ten which are added together to make up the number. Observe two things:
1. The digits of a decimal number can take any of the values from 0 up to 9.
2. Every digit in a decimal number will be multiplied by some power of 10. The powers of 10 start with 0 (the furthest digit to the right) and then increase from right to left.
Decimal numbers are sometimes also referred to as base 10 numbers. This is because the representation of the number in digits is ‘based’ on the powers of 10, as we have just seen. We normally do not bother indicating that a number is written in base 10, since this tends to be assumed by default. However, because we will be changing numbers from one base into another, we will often need to indicate the base being used. To indicate that the number 359 is a decimal number, we will thus sometimes write it as 359_{10}.
Leading Zeros
As a last remark about decimal (indeed, any number base), any number of 0’s can be put in front of a decimal number without changing its value. These are called leading zeros. For example,
(p.634) This is consistent with our previous way of expressing decimal numbers since:
Of course, when writing numbers in decimal, we do not normally use any leading zeros.
A.1.2 Binary
Writing a Number in Binary
Binary numbers are numbers written in base 2. Binary numbers follow very similar rules to decimal numbers. In fact, the only real change is that the role of the number 10 in writing a decimal number is replaced by the number 2. Thus, the new rules are:
1. The digits of a binary number can take the value 0 or 1.
2. Every digit in a binary number will be multiplied by some power of 2. The powers of 2 start with 0 (the furthest digit to the right) and then increase from right to left.
Consider the binary number 1101_{2} (note that we have used the subscript 2 just to make it clear that we mean the number 1101 in binary and not the decimal number one thousand one hundred and one, which we would have written 1101_{10}). Using the above rules (and comparing them with the explanation of decimal numbers), we see that each binary number is a sum of multiples of powers of 2:
Similarly, the number 110010_{2} is the sum of multiples of powers of 2 expressed by:
Every binary number has a decimal equivalent, and every decimal number has a binary equivalent. We now explain how to convert from one to the other.
Converting Binary to Decimal
Converting from binary to decimal is easy. Simply express the binary number as its sum of multiples of powers of 2, and then add them up. So, what is 1101_{2} in decimal? We know that:
So what we are saying is that the number 1101 in binary is the same as the number 13 in decimal; in other words ${1101}_{2}={13}_{10}$.
Converting Decimal to Binary
Converting a decimal number into binary is essentially just the reverse of the process for converting binary into decimal. Recall that a binary number such as 1101_{2} specifies a sum of multiples of powers of 2. These multiples can only take the values 0 or 1, so a binary number really specifies a sum of some of the powers of 2. More precisely:
• if the multiple is 0, then the corresponding power of 2 is not included in the sum; and
• if the multiple is 1, then the corresponding power of 2 is included in the sum.
In fact, any number can be uniquely expressed as a sum of powers of 2. So the question of how to convert a given decimal number into binary is equivalent to asking precisely which of the powers of 2 add up to this decimal number.
For a small number such as 14, we can easily determine this by trial and error. It does not take very long to work out that the powers of 2 adding up to 14 are 8, 4, and 2. Thus, by reversing the binary to decimal process, we see that:
In general, and in particular to convert large decimal numbers into binary, we need some kind of algorithm (system) for working out the binary equivalent of a decimal number. For simplicity, we will illustrate this process using a small number, namely, 25_{10}.
1. Find the highest power of 2 smaller than 25. Clearly, it is not possible for a power of 2 larger than 25 to be part of the sum of powers of 2 adding up to 25, so we find the largest power of 2 less than 25. This is 16. Thus, 25_{10} can be expressed as a sum of powers of 2 which are all less than or equal to 16. In other words:
$$\begin{array}{r}{25}_{10}=(?\times 16)+(?\times 8)+(?\times 4)+(?\times 2)+(?\times 1).\end{array}$$(p.636) 2. Determine whether each of the ? symbols is 0 or 1. Consider the ? coefficient next to 16. All of the remaining powers of 2 (8, 4, 2, and 1) only add up to 15. Thus, we must have 16 in our sum of powers of 2 adding up to 25, otherwise we could only sum to 15. Hence, the coefficient of 16 must be 1. So:
$$\begin{array}{r}{25}_{10}=(1\times 16)+(?\times 8)+(?\times 4)+(?\times 2)+(?\times 1).\end{array}$$Now, the remaining four powers of 2 must add to $25-16=9$. Consider the ? coefficient next to 8. All of the remaining powers of 2 (4, 2, and 1) only add up to 7. Thus, we must have 8 in our sum of powers of 2 adding up to 25, otherwise we could only sum to $16+7=23$. Hence, the coefficient of 8 must be 1. Thus:
$$\begin{array}{r}{25}_{10}=(1\times 16)+(1\times 8)+(?\times 4)+(?\times 2)+(?\times 1).\end{array}$$Now, the remaining three powers of 2 must add to $25-16-8=1$. Consider the ? coefficient next to 4. If 4 was included in our sum of powers of 2, then our sum of powers of 2 would be greater than 25, since $16+8+4=28$. Hence, the coefficient of 4 must be 0. Thus:
$$\begin{array}{r}{25}_{10}=(1\times 16)+(1\times 8)+(0\times 4)+(?\times 2)+(?\times 1).\end{array}$$Now, the remaining two powers of 2 must add to $25-16-8=1$. Consider the ? coefficient next to 2. If 2 was included in our sum of powers of 2, then our sum of powers of 2 would be greater than 25, since $16+8+2=26$. Hence, the coefficient of 2 must be 0. Thus:
$$\begin{array}{r}{25}_{10}=(1\times 16)+(1\times 8)+(0\times 4)+(0\times 2)+(?\times 1).\end{array}$$Now, the remaining power of 2 must add to $25-16-8=1$. Consider the ? coefficient next to 1. Clearly, in order to complete our sum the coefficient of 1 must be 1. So:
$$\begin{array}{r}{25}_{10}=(1\times 16)+(1\times 8)+(0\times 4)+(0\times 2)+(1\times 1).\end{array}$$Thus, we have determined all the coefficients and so:
$$\begin{array}{r}{25}_{10}={11001}_{2}.\end{array}$$
This is a simple algorithm, although a bit awkward to perform by hand. It should be clear, however, that this conversion algorithm is very easily performed on a computer.
The 3.3 Trick
We tend to have an intuitive feel for decimal numbers because we use them every day without thought or question. In cryptography, we often represent keys in binary. For example, an AES key can be 128 bits long, which means it consists of 128 binary bits. This means there are 2^{128} possible keys in the keyspace, but what (p.637) does this mean in terms of our more familiar decimal numbers? Fortunately, there is a quick and easy way to get a fairly rough, but good, approximation to this relationship. It is known as the 3.3 trick:
• To change a power of 2 into a power of 10, divide the power of 2 by 3.3.
• To change a power of 10 into a power of 2, multiply the power of 10 by 3.3.
Thus, knowing there are 2^{128} possible AES keys, we need to divide 128 by 3.3. The answer is close to 39, so 2^{128} is approximately 10^{39}.
Similarly, if we want to know how many bits long a symmetric key should be in order to guarantee a keyspace of at least one million, we need to determine what power of 2 is approximately equal to 10^{6}. We thus need to multiply 6 by 3.3, which is almost 20, so 10^{6} is approximately 2^{20}. Thus, around 20 bits will suffice.
Of course, this is not really a trick at all. Note that ${2}^{3}=8$ and ${2}^{4}=16$. We can in fact write any number between 8 and 16 as a power of 2, where the ‘power’ will be a number between 3 and 4 (the details are easily found from any wider introduction to exponentiation). The number 3.3 arises because 2^{3.3} is a close approximation to 10.
A.1.3 XOR
Now that we are familiar with binary numbers, it is worth mentioning a very important way of combining two binary numbers, which is commonly used in cryptography. This is the function exclusive or, better known as XOR, and usually denoted by the symbol ⊕.
When used to combine single binary digits, XOR takes two bits as input, and results in a third bit. The result is calculated according to the following rules:
In other words, the result of the XOR of two bits is 1 if the two inputs are different, and the result is 0 if the two inputs are the same.
When the XOR function is applied to binary numbers more than one bit long, the XOR of the two binary numbers is the result of the XOR of each individual bit. For example:
This follows because:
(p.638) We can also XOR two binary numbers of different lengths by first padding the smaller of the two numbers with leading zeros until it is the same length as the larger number. The two numbers can then be XORed in the normal way. For example, to compute $11010\oplus 101$, we first pad out 101 to 00101 and then compute:
A.1.4 Hex
The other base we need is hexadecimal, better known as hex, which is base 16. The main reason we need hex is that it provides a compact way of representing binary numbers. This is particularly helpful for cryptographic keys, which are often very long when represented in binary.
Writing a Number in Hex
For hex numbers, we use the base number 16 instead of 10 in decimal (and 2 in binary). Thus:
1. The digits of a hex number can, in theory, take any of the values between 0 and 15.
2. Every digit in a hex number will be multiplied by some power of 16. The powers of 16 start with 0 (the furthest digit to the right) and then increase from right to left.
The first requirement causes a slight problem, since it will be hard to determine whether 12 means the digit 1 followed by the digit 2, or whether we mean the hex ‘digit’ 12. Thus, we replace the hex digits 10, 11, 12, 13, 14, and 15 by A, B, C, D, E, and F, respectively. So, in practice, the digits of a hex number take any of the values between 0 and 9, and between A and F.
Converting Hex to Decimal
Converting from hex to decimal follows the same principles as binary to decimal, except that now we are using multiples and powers of 16. Consider the hex number B_{5}F_{16}. It follows that:
Thus, B_{5}F in hex is 2911 in decimal.
(p.639) Converting Between Binary and Hex
A useful feature of hex is that there is a very simple way of converting between binary and hex (which does not work for converting either of them to, or from, decimal). This uses Table A.1, which displays the binary equivalents of the 16 hex digits.
Table A.1 Decimal and binary equivalents of hex digits.
Decimal |
Binary |
Hex |
---|---|---|
0 |
0000 |
0 |
1 |
0001 |
1 |
2 |
0010 |
2 |
3 |
0011 |
3 |
4 |
0100 |
4 |
5 |
0101 |
5 |
6 |
0110 |
6 |
7 |
0111 |
7 |
8 |
1000 |
8 |
9 |
1001 |
9 |
10 |
1010 |
A |
11 |
1011 |
B |
12 |
1100 |
C |
13 |
1101 |
D |
14 |
1110 |
E |
15 |
1111 |
F |
Converting from hex to binary simply involves replacing each hex digit with its binary equivalent from Table A.1. For example, to convert B_{5}F_{16} into binary, we first make the substitutions:
from Table A.1 to get:
(p.640) Converting from binary to hex is just substituting the other way. For example, to convert 11000111_{2} into hex, we make the substitutions:
from Table A.1, to get:
In the case where the binary number cannot be neatly divided into groups of four bits, we add leading zeros until it can. Thus, to convert 1110011111_{2} into hex we first add two leading zeros:
We now make the substitutions:
from Table A.1 to get:
A.1.5 ASCII
Although computers process binary numbers, the majority of data we exchange does not consist of binary numbers themselves, but rather consists of alphanumeric symbols, punctuation, and other keyboard characters. Thus, there needs to be a standard convention for converting these items into binary, before they can be processed by digital devices.
The American Standard Code for Information Interchange (ASCII) is the convention most computers use to conduct this conversion. ASCII specifies an 8-bit binary number for each keyboard character. These are numbered 000 up to 127 in decimal (hence, strictly, only 7 binary digits are needed). Each of these can thus also be represented as two hex digits. Some sources give ASCII values between 128 and 255, but these have not been agreed as a standard and are strictly ASCII extensions.
As an example, the ‘greater than’ symbol > appears in position 62 of the full ASCII table. To find out the ASCII binary representation, we just convert 62_{10} into binary and then pad out to 8 bits using leading zeros, if necessary. In other words:
A.2 Modular arithmetic
This section introduces modular arithmetic. Modular arithmetic is used in many different cryptographic primitives, particularly public-key algorithms such as RSA.
(p.641) A.2.1 Motivation
Modular arithmetic is a familiar idea, dressed in mathematical terminology. This is best illustrated by several examples from everyday use.
Days of the Week
When we work out what day of the week something will happen on, we often (unconsciously) make mental calculations such as ‘two days after Tuesday is Thursday’. We could write this in a pseudo-mathematical way as follows:
When such a calculation takes us beyond the end of a particular week, then we will make statements such as ‘three days after Friday is Monday’. Although this is actually Monday of the following week, this does not cause us any problem since we are treating all Mondays as ‘the same’ for this purpose. So:
Similarly, we can make statements such as:
and
We can restate this simple idea by now replacing the days of the week, starting with Monday, by the numbers 0 to 6 (so Monday is 0, Tuesday is 1, and Sunday is 6). It is now possible to write all our previous pseudo-mathematical equations as mathematical equations. In other words:
Computing the days of the week in this manner is an example of modulo 7 (often abbreviated to mod 7) arithmetic. It is just like normal arithmetic except we ‘wrap back around’ when we reach the number 7 by treating 7 as beginning again at 0.
Months of the Year
Another example of modular arithmetic is when we calculate the months of the year. When we try to work out in what month of the year an event will occur, we (p.642) often make calculations such as ‘three months after January is April’. We can write this as:
Similarly, ‘four months after October is February’ is:
By replacing January to December with the numbers 0 to 11, we can write these calculations as:
This is modulo 12 arithmetic. There are many other examples of this type of ‘unconscious’ use of modular arithmetic. For example, the 24-hour clock provides an example of modulo 24 arithmetic.
A.2.2 Modular numbers
We can perform modular arithmetic using any positive integer as the modulus, where by positive integer we mean a whole number bigger than 0 (in other words, a number such as 2, 18, 754, etc.). When working modulo n (mod n), where n is some positive integer which we call the modulus, the only numbers we deal with are:
Thus, instead of having numbers that go on forever, when working modulo n we only have n different numbers to work with. For example, mod 6 arithmetic only uses the numbers 0, 1, 2, 3, 4, and 5, and mod 359 arithmetic only uses the numbers 0, 1, 2, 3, …, 355, 356, 357, 358. Using modular arithmetic, we will later see that we can add, subtract, and multiply numbers. So long as the answer is less than the modulus, these operations are just the same as if there was no modulus being used. For example, when working modulo 358, $57+101=158$. However, we need to consider what happens when the answer takes us beyond the modulus value.
Adding Multiples of the Modulus
First, let us consider what happens if we add two numbers modulo n and end up with n itself. For example, when working modulo 7, what happens when we compute 3 + 4? We know $3+4=7$, but in modulo 7 arithmetic there is no number 7.
(p.643) Recall the example based on days of the week. When working modulo 7, we see that asking ‘what is 3 + 4?’ in modulo 7 arithmetic is equivalent to asking ‘what day comes four days after Thursday?’. The answer is Monday, which is day 0, so:
The ‘mod 7’ at the end of the line indicates that we are performing the calculation modulo 7. Unless it is clear from the context, it is important to include this indicator, since the answer to ‘what is 3 + 4?’ depends very much on what modulus we are working with.
The important lesson is that when working modulo n, adding n to a number will not change it. Again, thinking of the days of the week example, seven days after Tuesday it is Tuesday again:
In fact, 14 days after Tuesday it is Tuesday again:
Also, seven days before Tuesday is also Tuesday:
Thus, in modulo n arithmetic, the number n behaves just like 0 does for the numbers we normally use. This is an important principle of modular arithmetic.
One Number Modulo Another
Consider two numbers a and n, where a and n are both positive integers. Although a is a positive integer, suppose we want to know what value a would take if we considered it as a number modulo n. This question is often phrased as ‘what is the value of a modulo n’?
It is important to recognise there will be an answer to this question. This is because any number can be expressed uniquely modulo any other number. Since we have just seen that in modulo n arithmetic all multiples of n are 0, the answer to our question is that a will take the value which is the remainder when we divide a by n.
To see a simple example, let $a=6$ and $n=5$. We know 5 is the same as 0 in modulo 5 arithmetic. Since 6 is just one more than 5, it follows that 6 will be the same as 1 in modulo 5 arithmetic. This is just another way of saying that when we divide 6 by 5, we get a remainder of 1. Thus 6, is equal to 1 when 6 is considered as a number modulo 5. In other words,
(p.644) Similarly, let $a=5417$ and $n=7$. We can divide 5417 by 7 using traditional arithmetic to discover that:
Since we know $7=0$ when we are working modulo 7, it follows that $(773\times 7)$ will also be 0. Thus, 5417 is equal to 6 when we work modulo 7, which we write:
Returning to our analogy, if we ask ‘what day of the week is it 5417 days after Wednesday?’ we now know that in 5417 days it will be 6 days after Wednesday, so it will be Tuesday!
We will also need the following idea later. Suppose we know that a positive integer a takes the value r modulo n. In other words, we know that when we divide a by n, we get the remainder r. This tells us it is possible to write a as:
for some number k. We do not necessarily know what k is, but there must be a k for which this is true. Returning to our previous example, knowing 5417 takes the value 6 modulo 7 allows us to claim that:
for some number k (in fact, it is easy to work out, in this case, that $k=773$).
Terminology and Notation
We have kept our terminology as simple as possible. However, other texts may explain modular arithmetic in a slightly different language. For example, the process of calculating one number modulo another is sometimes called modular reduction. Thus, we might say that 5417 reduces to 6 modulo 7. Also, just to make sure it is recognised a modular reduction has taken place, often the symbol ≡ is used instead of =. Thus, we would write $5417\equiv 6\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}7$ rather than $5417=6\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}7$. This idea is often expressed by stating 5417 is congruent to 6 modulo 7.
Note that while 5417 is congruent to 6 mod 7, it is also congruent to 13 mod 7, and 20 mod 7. In fact, it is congruent to any multiple of 7 with 6 added. However, when asked ‘what number is congruent to 5417 mod 7?’, there will only be one answer lying between 0 and 6. This is the default answer, and usually the most useful one.
Negative Modular Numbers
We can also work with negative numbers in modular arithmetic. These behave in almost the same way. To start with, we can regard any negative multiple of the modulus n as being equal to 0 modulo n. In other words, − 7 and − 14 are both equal to 0 modulo 7. More generally, any negative integer can be uniquely expressed (p.645) as a number modulo n. For example, suppose we wish to compute −17 mod 10. We divide − 17 by 10 and take the remainder. When we do this, we need to have a positive remainder because our answer modulo 10 must be one of the numbers between 0 and 9. Thus, we see that:
In other words:
A.2.3 Modular arithmetic operations
Addition, Subtraction, and Multiplication
The good news is that the basic arithmetic operations of addition, subtraction, and multiplication behave just as we would expect them to. In other words, we can add numbers, subtract them, or multiply them, just as we would ‘normal’ numbers. We just need to remember to reduce the answer modulo n. Thus, for example:
Importantly, division is intentionally left out of this list because it does not work in quite the same way as it does for normal numbers. There is a way to deal with division, but we discuss this later.
Modular Reduction: Before or After?
One issue worth clarifying when doing a calculation such as 15 + 20 mod 6 is whether we should reduce 15 and 20 modulo 6 before, or after, they have been added together. Fortunately, it does not matter, since will still get the same answer. This is best seen by example:
1. Add then reduce: We first compute $15+20=35$ and then note $35=5\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}6$. So $15+20=5\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}6$.
2. Reduce then add: We first compute $15=3\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}6$, and then $20=2\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}6$. Now we add the answers, in other words $15+20=3+2=5\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}6$.
(p.646) A.3 The mathematics of RSA
This section contains the remaining mathematical tools we need in order to understand the RSA cryptosystem.
A.3.1 Primes and coprimes
Before we learn how to ‘divide’ in modular arithmetic, we need to explore the concept of division in a bit more detail.
Primes
A divisor of a number is any number which divides into it ‘neatly’ with no remainder left over. For example, 3 is a divisor of 6, 5 is a divisor of 145, and 17 is a divisor of 187. Note also that 46 is a divisor of 46, and 1 is a divisor of 10023. Indeed, every number has at least two divisors, namely, the number itself and 1. Most numbers have more divisors than this.
A prime is a number with no divisors other than itself and 1. For example, 17 is prime because 17 and 1 are the only numbers dividing into 17. Also, 2 is a prime, so is 3, and 5, and 7. On the other hand, 18 is not prime because 2, 3, 6, and 9 are also divisors of 18. Primes have many special mathematical properties, which is why they form the basis for so many different cryptographic algorithms.
Greatest Common Divisors
The greatest common divisor (usually abbreviated to gcd) of two numbers is the largest whole number dividing neatly into both numbers without leaving a remainder. In other words, the gcd of a and b is the largest number which is a divisor of both a and b.
For example, the gcd of 14 and 21 is 7, since 7 is the largest divisor of both 14 and 21. We normally write this as:
Similarly, $\text{gcd}(6,8)=2$, since 2 is the largest divisor of both 6 and 8.
Every pair of numbers has a greatest common divisor. Since 1 is a divisor of every number, it follows there is always at least one common divisor. In some cases 1, is the greatest common divisor, but for many pairs of numbers there is a larger common divisor than 1.
(p.647) Coprimes
We say two numbers are coprime if their greatest common divisor is 1. In other words, two numbers are coprime if the only divisor they have in common is the number 1. Or, using our gcd notation, two numbers a and b are coprime if gcd$(a,b)=1$. For example, 42 and 55 are coprime. But 42 and 56 are not coprime, since 2 divides into 42 and 56 (as do many other numbers).
Primality and coprimality are different concepts. Primality is a measure applied to a single number on its own. Coprimality is a measure applied to two numbers to compare them with one another. However, it is true that two different primes are always coprime to one another.
A.3.2 Multiplicative inverses
Before considering division in modular arithmetic, we need to reconsider what division means in normal arithmetic.
Definition of Multiplicative Inverse
The multiplicative inverse of a chosen number is the number we multiply the chosen number by to get 1. In other words:
So what is the multiplicative inverse of 3 in our normal number system? The answer is one third, since:
In a similar way, the multiplicative inverse of 127 is $\frac{1}{127}$. The multiplicative inverse of a number is indicated by writing the number to the power − 1. Thus, for example:
An important issue is that not every number has a multiplicative inverse. For example, in our normal number system, the number 0 does not have a multiplicative inverse, since there is no number which, when multiplied by 0, results in the answer 1.
Division Using Multiplicative Inverses
Division by a number can thus be described as the process of multiplying a number by its multiplicative inverse. For example, dividing by 10 is just the same as multiplying by $\frac{1}{10}$, the multiplicative inverse of 10. In other words, division by 10 is the same as multiplying by 10^{−1}. Similarly, division by 127 is the same as multiplying by ${127}^{-1}=\frac{1}{127}$.
(p.648) This might sound like we are just playing with words, but we are not. Considering division as multiplication by multiplicative inverses is very helpful when we return to the problem of how to divide in modular arithmetic.
Modular Inverses
We now consider the multiplicative inverse of one number modulo another, sometimes referred to as a modular inverse. We will see that, in contrast to our normal number system:
• many numbers other than 0 do not have a multiplicative inverse modulo another number; and
• there exist numbers other than 1 which are their own multiplicative inverse modulo another number.
We begin with an example. Let us try to find the multiplicative inverse of 2 modulo 7. In other words, we need to find a number which, when multiplied by 2, results in 1 mod 7. Recall that when working mod 7, the only numbers are 0, 1, 2, 3, 4, 5, and 6, so $\frac{1}{2}$ cannot be the answer.
It is not obvious what the answer is, or indeed if there is an answer at all. One rather crude way of finding a solution is to try out all of the numbers mod 7 until we find out if there is an answer:
So the modular inverse of 2 is 4. In other words, ${2}^{-1}=4\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}7$. We can also search for the multiplicative inverse of 6 modulo 10:
(p.649) So, there is no multiple of 6 equal to 1 mod 10. Thus, 6 does not have an inverse mod 10. In other words, the modular inverse 6^{‒1} mod 10 does not exist.
The previous examples raise the interesting question: when does a number have a multiplicative inverse modulo another number? This is essentially the question: when can we divide in modular arithmetic? It turns out that a number has an inverse modulo another number precisely when the two numbers are coprime. Thus, for example, gcd$(2,7)=1$, which means 2 and 7 are coprime, and thus ${2}^{-1}\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}7$ exists. Similarly, gcd$(5,17)=1$, which means 5 and 17 are coprime, and thus ${5}^{-1}\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}17$ exists. On the other hand, gcd$(6,10)=2$, which means 6 and 10 are not coprime, and thus ${6}^{-1}\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}10$ does not exist.
The Extended Euclidean Algorithm
We need to be able to find modular inverses in order to set up key pairs for the RSA cryptosystem. RSA works with modular numbers which are very large, so the idea of exhaustively trying out all the possible numbers less than our modulus is not going to be a practical method of finding modular inverses.
Fortunately, there is a process, known as the Extended Euclidean Algorithm which can be used to calculate modular inverses. The Extended Euclidean Algorithm is not complicated, but neither is it simple to explain in a few paragraphs. We thus refer the interested reader elsewhere and choose to accept that we can find modular inverses easily, whenever we need them, using the Extended Euclidean Algorithm.
A.3.3 RSA key pair setup
We now explain how all the simple ideas we have just discussed come together in the RSA cryptosystem.
There are four basic steps involved in setting up an RSA public and private key pair. Although we covered this material in Section 5.2, we provide a reminder here using the mathematical terms just explained:
1. Generating the modulus. Choose two primes p and q, and let $n=p\times q$.
2. Generating e. Choose e to be a number smaller than $(p-1)\times (q-1)$ coprime to $(p-1)\times (q-1)$. The reason we require this is because we want e to have a modular inverse.
(p.650) 3. Forming the public key. Let the public key be (n, e).
4. Generating the private key. The private key d is the unique modular inverse of e modulo $(p-1)\times (q-1)$. This number d can be calculated using the Extended Euclidean Algorithm by anyone who knows p and q.
An example of this process was given in Section 5.2.1.
A.3.4 Why RSA works
We now explain why RSA works. This section contains simple mathematical arguments based on information we have just described. However, there is no need to concern yourself with the detailed discussion in this section unless you want to know exactly why RSA works. If you simply want to understand the main mathematical ‘mechanics’ behind RSA, then this has already been done.
We know from Section 5.2.2 that RSA encryption consists of taking a plaintext P and computing $C={P}^{e}\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}n$, while decryption is given by $P={C}^{d}\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}n$. We now provide an explanation for why these two operations ‘reverse’ one another.
We will assume (n, e) is an RSA public key and d is the corresponding private key. We will sometimes use the notation ab to mean a × b, just as we did in Section 5.2. We will also use a mathematical result attributed to Fermat, which states that for any number B satisfying gcd$(B,n)=1$, it follows that:
Now, expressing the RSA decryption formula mathematically, we have:
Remember that because d is the modular inverse of e, we have that $ed=1\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}(p-1)(q-1)$. This means there is some positive integer k for which it is true that:
Thus, by replacing this in our above expression for the decryption function:
Now all we do is rewrite this expression by rearranging the powers of P. There are no mathematical tricks here; we just follow the rules describing how powers of a number behave. So:
(p.651) The result due to Fermat quoted at the start can now be used. Writing P instead of B, we see that (so long as the greatest common divisor of P and n is 1) this result says:
Thus, we see that:
which is what we hoped decryption would achieve.
The only case we have not covered is when gcd(P, n) is not equal to 1. Note that this is an extremely rare case and only happens in the highly unlikely event either $P=up$, for some $u<q$, or $P=vq$, for some $v<p$. If $P=up$, then $P=0\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$ and so ${P}^{ed}=0\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$. In other words, ${P}^{ed}=P=0\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$. Since P is a multiple of p, in this case it cannot be a multiple of q as well, and so the greatest common divisor of P and q is 1. Thus, we can apply Fermat’s result and the above RSA argument to see that ${P}^{ed}=P\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q$. We have now shown ${P}^{ed}=P\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$ and ${P}^{ed}=P\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}q$. It follows by a simple number theory result that ${P}^{ed}=P\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}n$. If $P=vq$, then we apply a similar argument to show the same result.
A.4 The mathematics of ElGamal
The version of the ElGamal cryptosystem described in Section 5.3 also relies on modular arithmetic. We only need to explain one further concept in order to understand the basic mathematics behind ElGamal.
A.4.1 ElGamal public keys
Recall from Section 5.3.1 that each ElGamal public key involves three numbers. The first is a prime p, while the second number g has the special property that it is a primitive element. We now explain the significance of this.
Primitive Elements
Let p be a prime. A number g between 1 and p − 1 is said to be primitive (or is a primitive element) modulo p if the numbers:
are all different. If this is the case then, since there are p − 1 of them, they must consist of $1,2,3,\dots ,p-1$ in some order.
(p.652) Table A.2 indicates the powers of 11 modulo 23. The first and third rows indicate the powers 11 is being raised to, while the rows beneath show the result of computing 11 raised to each power, modulo 23. For example, ${11}^{2}=121=6\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}23$, so 6 appears below 11^{2} in Table A.2.
Table A.2 Powers of 11 modulo 23.
11^{1} |
11^{2} |
11^{3} |
11^{4} |
11^{5} |
11^{6} |
11^{7} |
11^{8} |
11^{9} |
11^{10} |
11^{11} |
11 |
6 |
20 |
13 |
5 |
9 |
7 |
8 |
19 |
2 |
22 |
11^{12} |
11^{13} |
11^{14} |
11^{15} |
11^{16} |
11^{17} |
11^{18} |
11^{19} |
11^{20} |
11^{21} |
11^{22} |
12 |
17 |
3 |
10 |
18 |
14 |
16 |
15 |
4 |
21 |
1 |
We can see from inspecting Table A.2 that 11 is a primitive element modulo 23. Note, however, that not every number between 1 and p − 1 is primitive modulo p. Table A.3 indicates the powers of 2 modulo 23. In this case, not all the numbers 1, 2, 3, …, 22 appear among the second and fourth rows of Table A.3 (in fact, only half of them do), and so 2 is not a primitive element modulo 23.
Table A.3 Powers of 2 modulo 23.
2^{1} |
2^{2} |
2^{3} |
2^{4} |
2^{5} |
2^{6} |
2^{7} |
2^{8} |
2^{9} |
2^{10} |
2^{11} |
2 |
4 |
8 |
16 |
9 |
18 |
13 |
3 |
6 |
12 |
1 |
2^{12} |
2^{13} |
2^{14} |
2^{15} |
2^{16} |
2^{17} |
2^{18} |
2^{19} |
2^{20} |
2^{21} |
2^{22} |
2 |
4 |
8 |
16 |
9 |
18 |
13 |
3 |
6 |
12 |
1 |
Importance of Primitive Elements to ElGamal
The ElGamal public-key component g must be a primitive element modulo p. The main reason this restriction is made is in order to make sure that when we raise g to different powers, which we do when computing the third component y of an ElGamal public key as well as during the encryption process itself, the result can be any number modulo p. If g is not primitive, then the security of ElGamal is greatly reduced.
For example, if the non-primitive element $g=2$ is used as part of an ElGamal public key alongside $p=23$, then we can see from Table A.3 that g^{k} can only take half of the possible values. An attacker who tries to decrypt a ciphertext by exhaustively searching for the value k used when forming ${C}_{1}={g}^{k}$ will have a much easier job than if we had used a primitive element for g, since there are two different values of k which will work, halving the effort required.
(p.653) A.4.2 Why ElGamal works
Recall that an ElGamal public key is of the form (p, g, y), where x is the corresponding private key and $y={g}^{x}$. In Section 5.3.2, we also learnt that ElGamal encryption consists of randomly generating a value k and then computing ${C}_{1}={g}^{k}$ and ${C}_{2}=P{y}^{k}$, where P is the plaintext. We then observed that decryption consists of dividing C_{2} by the answer to $({C}_{1}{)}^{x}\phantom{\rule{12mu}{0ex}}\mathrm{m}\mathrm{o}\mathrm{d}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}p$. We now explain why this works.
Suppose Bob receives the ciphertext (C_{1}, C_{2}). Bob begins by using his private key x to transform C_{1} into something more useful. He thus computes:
This follows because it does not matter in which order the two exponentiations are computed. Thus, raising g to the power k and then to the power x is the same as raising g to the power x and then to the power k.
Bob now divides this value into C_{2}. Of course, we now know such ‘division’ is done by multiplying by the modular inverse. Thus, Bob needs to find the modular inverse of y^{k} modulo p, which we denote by $({y}^{k}{)}^{-1}$. Bob can find this using the Extended Euclidean Algorithm. Then Bob computes:
which is what we require.
A.5 Further reading
Several of the recommended existing cryptography books, such as Menezes, van Oorschot, and Vanstone [150], Mel and Baker [149] and Stinson [231], also include explanations of some the basic mathematics we have discussed, although these vary in the level of detail and degree of assumed knowledge. For further details of basic number theory, there are a number of good options, of which Tattersall [236] is one of the more accessible. (p.654)