RationaleIn the twenty-first century, technological advancements has allowed us to purchase goods online from all over the world. Personally, I love online shopping and I am a frequent user of websites such as Amazon, Alibaba, Ebay and many more. Going through the process of typing my credit card number and making payments has become part and parcel of my life. However, I have always wondered about this process. What is so unique about the credit card numbers? How is it possible that a set of numbers can be so powerful in helping to make payments? What stops cyber thieves from intercepting the transmission and stealing these numbers? These burning questions soon intrigued me to do a math exploration on cryptography – analyse the mathematics behind encryption and decryption of codes in algorithms. IntroductionFirstly, I will explain what cryptography is. It is a technique of transmitting data in a particular form such that only those who are meant to receive the information will be able to receive and process it. There are a total of 3 main kinds of cryptographic methods – Secret Key Cryptography, Public Key Cryptography and Hash Functions. In my exploration, I will be investigating about Public Key Cryptography which is widely used in e-commerce and credit card transactions. I will be discussing about RSA algorithm, which is also known as public key cryptography. Public Key Cryptography uses prime numbers and works based on the concept that it is difficult to factor prime numbers. It consists of splitting a key into 2 different keys where the public key is for encryption ( which means encoding a message in a way that only authorized parties can access it ) and another private key for decryption (which means decoding an encrypted code). Since both keys are different, this type of cryptography is called asymmetric key encryption. When we enter our credit card numbers online, we are making use of RSA algorithm which was established by Ron Rivest, Adi Shamir and Leonard Adleman in 1977. RSA algorithm is used in Public Key Cryptography. This encryption system relies solely on prime numbers. The computer systems make use of our private data by transforming our message into another huge number which is obtained by multiplying two randomly selected prime number. By doing so, cyber thieves are not able to intercept and obtain our message as it will take years to prime factorise large numbers into its primes. Through encryption and decryption, the message is sent to only the intended party, without any cyber thieves from obtaining the message. After much research, I realised that payments through credit cards are successful because of RSA algorithm. RSA algorithm uses two formulas for the encryption and decryption of codes – cd mod (n) m and d =k?(n) +1e for decryption. These two formulas are derived using various theorems and mathematical concepts. This made me curious to explore the mathematics involved in RSA algorithm which includes the usage of Prime Numbers, Modular Arithmetics, Fermat’s Little Theorem and also Euler’s Totient Function for encryption and decryption of codes without cyberthieves eavesdropping. I will be using these concepts to show how the formulas for RSA algorithm are derived and how RSA works. Prime NumbersFirst and foremost, since RSA algorithm works mainly because of prime numbers and not any other number, it is crucial for me to define what prime numbers are. “Prime numbers are the genes of the number system: all other whole numbers can be expressed as a product of primes” says Mike Askew in All That Matters Mathematics. This means that prime numbers are the fundamental constituents to all the other numbers and can be only divided by 1 and itself, which means that the factors are 1 and the whole number itself. The factors are whole numbers that will divide exactly into another whole number without leaving a remainder.By Fundamental Theorem of Arithmetic, any number, even composite numbers, can be expressed as a unique product of prime numbers. For example 90 is a composite number. However, this number can be broken down to 90 = 2 325. 2,3,5 are all prime numbers. This is known as prime factorisation. This concept will be later applied to RSA algorithm.Prime numbers have another unique characteristic. Prime numbers can be represented on an Ulam Spiral where the numbers are arranged in spiral and this can go on and on to infinity. This was invented by a Scottish Mathematician, Stanislaw Ulam. Ulam noticed that the prime numbers in the Ulam Spiral had a pattern and tend to sit on diagonal lines as shown in the diagram below. Figure 1 – Prime numbers represented on an Ulam SpiralHowever, up till today, no mathematician has found out the pattern that predicts what the next prime number will be. With today’s technology, there is an option of using quantum computers to solve the factorisation of all numbers into its primes. However, as the characters in the prime numbers increases, the time taken for the computer to solve them increases as well. This problem is known as Time Complexity. For a number as large as 700 characters, by the time computers factorise these numbers, the universe will end. This time complexity allows prime factorisation of exceptionally large numbers to be hard to solve. This plays a crucial role in RSA algorithm. Many credit card transactions require encryption so that sensitive information about credit card numbers can be only authorised by the bank and the credit card users, securing the information transmitted from cyber thieves. Previously, encryption required two parties to share a secret number which can be also known as a lock. This type of encryption system is known as the symmetric encryption as the keys shared are identical. For example, let us take into the account of Maggie, Tim and Eve analogy where Maggie and Tim, assuming that they are far apart, have to share a secret code without Eve who is always eavesdropping from intercepting and obtaining the secret code. This can be done either by Maggie and Tim sharing the same key to unlock the lock to obtain the message. However, this would be too tedious if many people were involved as different types of keys will be involved which will be difficult to manage. Therefore, Whitfield Diffie devised a trick which can be explained through the use of colours. It is easy to mix 2 colours to give another colour but hard to separate them back to the original 2 colours. This is the basis for a lock whereby it is easy in one direction but complex in the other way. This suggests that locks are one-way functions. First, all three, Maggie, Eve and Tim, agree on a mutual colour, also known as the public colour. Let’s take this colour to be blue. Next, Maggie and Tim both randomly select two colours and mix them with blue. In this case, the colours they have randomly selected are known as their private colour. Maggie keeps her private colour and sends the colour that she mixed with blue and her private colour to Tim. Tim does the same as Maggie, sending his mixture of colours to Maggie, hiding his private colour. In this case, Eve is only able to obtain the 2 mixtures of colours and the initial public colour, blue, but not the 2 private colours. Maggie and Tim both add their private colours to the mixture to arrive at their secret colour. Since, Eve does not have any of the private colours, she is not able to discover the secret colour. In this case, keys are not exchanged. This is known as a one-way function as it is easy to mix the colours but hard to separate colours which are mixed into their original colours. This is known as asymmetric encryption.Credit card transactions work based on the same underlying concept as aforementioned. However, now we need a numerical equation so that information can be transferred safely, preventing cyber thieves from tapping into our mobile networks. This brings us to modular arithmetic. Modular Arithmetic and Modular Exponentiation9 + 6 = 3. This is definitely not true when adding the numbers traditionally. However, this can be proven to be true using Modular arithmetic. “Arithmetic is a branch of mathematics that deals with numerical computation using integers”. It consists of all the rules for combining two or more numbers – addition, subtraction, multiplication and division. More complex concepts in arithmetic includes modular arithmetic in Number Theory. In modular arithmetic, numbers “wrap around” when they reach a fixed quantity. This is also known as the modulus. This can be written in the form of for example “mod 7”. Since the numbers “wrap around” like the numbers on the clock, this can be known as clock arithmetic. A 12 – hour clock is a good example to show modular arithmetic. For instance, the time now is 9:00 now. 6 hours later, the time will be 3:00. Using the traditional addition operation, the time 6 hours later should be (9:00 + 6:00 = 15:00). However, this is not true as the clock time wraps around for every 12 hours and the hour number restarts once it reaches 12:00. Therefore, this is known as the arithmetic modulo 12. This means that 12 is not only congruent to itself but also to 0. Thus, the time “12:00” could be also “00:00” as 12 is congruent to 0 modulo 12. Therefore, instead of writing 9 + 6 = 3, mathematicians may choose to use a congruence symbol, , instead of an equal symbol, =. This is known as congruence relation.Congruence relations can be introduced on integers that are able to carry out the 4 traditional operations such as addition, subtraction, multiplication and division. TS=Q+R ——————————————————————————————– ( 1 )Where,T is the dividendS is the divisorQ is the quotient andR is the remainder.The equation shown above can be also written in modulus form as shown below.Tmod S=R ——————————————————————————————- (2)For example, let’s take 9 mod 2= ?, where 9 is T, 2 is S. This expression is proved using the diagram shown below: (similar to clock arithmetic) : 9 mod 2=1. Diagram 1: Modular Arithmetic of 9 mod 2 = 1 Modular arithmetic can be solved using a graphic display calculator (GDC). The steps are shown below. Let M = 2 and A = 9 in 9 (mod 2) = 1Step 1: Press Calculate on the GDC.Step 2: Press the button with a open book sign and press fPart.Step 3: Key in Mfpart (A/M) to get the modulus of A mod M. Relating this concept back to cryptography: Maggie and Tim agree publically on a generator and prime modulus. Next, Maggie selects a private random number and sends this result publicly to Tim. Tim does the same. Maggie takes Tim’s public result and raises it to the power of her private number which results in the secret that is shared amongst the 2. Tim does the same. He takes Maggie’s public results and raises it to the power of his private number to give the same secret message. This results in a general equation as both Maggie and Tim did the same calculations. The inverse of this equation is difficult to perform as Eve does not have the private numbers which were used by Tim and Maggie. Now, how do we get a mathematical equation from the given background information? We can do this using modular exponentiation. Modular exponentiation is a kind of exponentiation (a mathematical operation which can be denoted as an, where a is the base and n is the exponent) carried out over a modulus. The operation of modular exponentiation calculates the remainder when an integer a which is the base is raised to the nth power (the exponent), bn, and is divided by a positive integer m, the modulus. Given base a, exponent n, and modulus m, the modular exponentiation of c is: c ? an (mod m). Fermat’s Little TheoremThis is the background of modular arithmetic. Now to the next step, Fermat’s Little Theorem (Fermat’s Primality Test) can be used to prove whether a number is prime number or not. This theorem is relevant to RSA algorithm as the first step in RSA is to generate 2 prime numbers, p and q, such that n = pq. These 2 prime numbers should be large enough until it is impossible to prime factorise the number. To ensure that the randomly selected 2 numbers p and q are prime, we can use Fermat’s Primality Test to check if the numbers are prime. However, before we test if the numbers are prime, we need to prove Fermat’s Little Theorem. To do so, we can use modular arithmetic. The proof is shown below: Fermat’s little theorem was states that if p is a prime number, then for any integer a, the number a p ? a is an integer multiple of p.In modular arithmetic terms, the theorem can be denoted as:ap-a1=p———————————————————————————————- (3)a(ap-1-1)=p—————————————————————————————– (4)ap-1-1=pa——————————————————————————————— (5)This formula is similar to the form of TS=Q+R, where there is no remainder.ap-1=pa+1——————————————————————————————– (6)ap-11 (mod p)————————————————————————————— (7)Assuming that a is a positive integer and is not divisible by p, firstly, we have to write down the arithmetic sequence of numbers:a, 2a, 3a, 4a …. (p-1)a ————————————————————————— (8)Next, reduce each term by one modulo p, which means that divide all the values in the sequence by p. Hence, the resulting sequence turns out to be the remainder of the division of each number in the sequence. This results in a rearrangement of:1,2,3,…,( p – 1 )———————————————————————————– (9)From here, we can multiply the numbers in each sequence together:a2a 3a… (p-1) (a) 123…(p-1) (mod p)————————— (10)Grouping all the a terms together, we get: ap-1(p-1)! (p-1)! (mod p)——————————————————————– (11)ap-11 (mod p)————————————————————————————- (12)In step number (13), I have cancelled (p-1)!from both sides of the equation. However, is this valid? It is valid in some situations like the one stated above. Cancellation law suggests that if M, x, y are integers and M is not divisible by a prime number p, and ifMx My (mod p)———————————————————————————- (13) after cancelling M, we will get x y (mod p)—————————————————————————————- (14)The cancellation law used above is valid for the above proof in Fermat’s Little Theorem as the integers 1,2, …, p-1are not divisible by p, the prime number. This can be proven through the use of Euclid’s lemma, which says that if a prime number p, divides a product ab, where a and b are integers, p must divide a or b. This means that M (x-y) Mx -My. Since p is a prime number and does not divide M, Euclid’s lemma suggests that it must divide (x – y). This cancellation law is only applicable if p is prime in Fermat’s Little Theorem. Putting all the concepts in context, this is an example of how Modular Arithmetic can prove Fermat’s Little Theorem. Let a = 5 and p = 7. The arithmetic sequence will be :5, 10, 15, 20, 25, 30, where the common difference is 5 ——————————– (15)Reduce modulo 7 to each integer of the sequence. This can be shown in the table below:Integers in sequenceManuel Working (GDC can be used too)Integers in sequence when reduced by modulo 755 mod 7 = 551010 mod 7 = 331515 mod 7 = 112020 mod 7 = 662525 mod 7 = 333030 mod 7 = 22After reducing modulo 7 from each term in the above sequence, we will get the rearrangement of the terms as shown below: 1, 2, 3, 4, 5, 6 ————————————————————————————— (16)Multiplying equation 16 and 17 gives 5, 10, 15, 20, 25, 30 123456 (mod 7) —————————————- (17)5(52)(53)(54)(55)(56) 123456 (mod 7)———- (18)56(123456) (123456) (mod 7)———————————— (19)561 (mod 7)—————————————————————————————- (20) General form: ap-11 mod p, where a = 5 and p = 7 ———————————— (21)Therefore, modular arithmetic proves Fermat’s Little Theorem.When making money transactions, 2 very large prime numbers are chosen, p and q. However, since there are no particular pattern of prime numbers, how do we know that the particular two numbers that we have randomly selected are primes? This problem can be solved through the use of Fermat’s Primality Test. Primality testing using Fermat’s little theorem is called the Fermat primality test. “Fermat’s Primality Test is a probabilistic test to if a certain number is a probable prime.” As step 1 of RSA cryptography requires 2 prime numbers to be generated randomly, we can use Fermat’s Primality Test to conclude if the two numbers are prime. Now, if we want to test whether p is prime, we can pick random a’s not divisible by p and see whether this equality holds. If this equality is not true for a particular value of a, we can conclude that p is a composite number. However, this congruence is unlikely to hold for a random a if p is composite. Therefore, if the equality is applicable for one or more values of a, then we say that p is probably prime. However, for a 1 (mod p), the above congruence holds trivially. Moreover, it holds trivially if p is odd and a 1 (mod p). Therefore, choose a number a between the range 1< a < p-1.For instance, if we want to determine whether n = 6 is prime, we can carry out the following steps. Firstly, randomly pick a number value for a, 1 < a < 6, say a = 7 Checking the above equality, we find that it holds:an-1= 76-1 1 (mod 6)---------------------------------------------------------------------------- (22)This shows that 6 is a prime number. Let's try with another base,a. When a = 3an-1= 36-1 (mod 6)31---------------------------------------------------------------------- (23)However, when using a different base, it has come to my attention that 6 is a composite number as the remainder when 36-1divided by 6, is 3. However, Fermat's Little Theorem suggests that a number is only prime if a p-1when divided by p in the equation a p a (mod p), where p is the prime number, gives a remainder of 1. When cross referencing with trial division method, it shows that 6 is a composite number. Trial division is a method to see if an integer can be divided by each number in turn that is less than the integer itself. Two different methods shows two different answers to whether 6 is prime or not. It is more accurate that Fermat's Primality test but is extremely laborious and might take years. Since 6 is a small number, we can deduce the integer factorisation which is 1,2,3,6 are its factors. Since it has factors 2 and 3 other than 1 and 6, it is a composite number according to trial division. Therefore, we can see that Fermat's Little Theorem has some flaws.By Fermat's Primality Test, 6 is a prime number when in actual fact it is not. Therefore, for the base 7, 6 is a Fermat pseudoprime. Therefore, 6 passes the Fermat's Primality Test. Pseudoprimes are also known as carmichael number whereby a composite number satisfies the modular arithmetic congruence relation:ap-11 (mod p) ------------------------------------------------------------------------------------ (24)Therefore, when generating prime numbers, we can use Fermat's Primality Test to ensure if the 2 chosen numbers are prime. However, we should be aware of the presence of Carmichael numbers as they seem to be prime. Therefore, we should ensure that when carrying out the primality test, for the value of a, the base, substitute in different numbers to give 1 when ap-1is divided by p such that it will only give a remainder of 1. We can also ensure the primality of a number by using Trial Division method which is much more laborious.The second step after generating the prime numbers in RSA Algorithm is to multiply these two prime numbers to get the composite integer n. Fermat's Theorem is the generalisation of Euler's Theorem. Euler's Theorem states that if n and a are coprime positive integers, thena(n)1 (mod n) ------------------------------------------------------------------------------------ (25)where (n)is Euler's totient function.Phi function, which was discovered by Euler, measures the breakability of a number. For example, for a integer n, the Phi function outputs how many integers are less than or equal to n and does not share a factor with n. Calculating Phi is a difficult process except for prime numbers as prime numbers do not have any factors greater than 1. For example, the Phi of 7, which is a prime number, is 6 (2,3,4,5,6,7) excluding 1 as 7 does not have any factors greater than 1. Thus, the phi of prime numbers, p, is p - 1. Phi of any prime number is easy to compute and therefore this is the trapdoor function. Phi functions are multiplicative. (p q) = (p) (q), where p and q are prime numbers --------------------------- (26)Since n = pq ,(p q) =(p) (q) = (p - 1) (q - 1)------------------------------------------------ (27)The above equation is the trapdoor function. If we know the factorisation of n, then finding phi of n is easy. However, Maggie hides the (p - 1) and (q - 1) , making that as her private key. Therefore, n is the public key. Therefore, step 2 of RSA algorithm is to find the phi of n using Euler's Totient Theorem. Moving on, Clifford Cocks, a British mathematician, came up with a trapdoor one way function whereby it is easy to compute in one direction but difficult to reverse unless there is a presence of a function known as trapdoor. To find the trapdoor function, Cocks used modular exponentiation, or also known as clock arithmetic, whereby a number is taken and raised to some exponent which is divided by the modulus. In general term, it can be denoted as:me mod (n) c, where m,e,n,c are integers --------------------------------------------- (28)such that gcd (e, ? (p x q) ) = gcd ( e, (p ? 1) (q ? 1) ) = 1 ------------------------------ (29)The great common divisor (gcd) integers that are not all zero, is the largest positive integer that divides each of the integers. To find gcd (9, 84), we find the prime factorizations 9 = 2 · 3 and 84 = 22 · 3 · 7. There is an overlap of the factors as shown by the venn diagram below. Diagram 3: Venn diagram of the common factors of integers 9 and 84.Therefore, gcd (9, 84) = 3. Prime factorizations for large numbers takes far too long and is therefore not feasible.GCD can be calculated a graphic display calculator (GDC).Step 1: Press the calculator mode on the GDC. Step 2: Press menu and select Number and then press Greatest Common Divisor.Step 3: Enter the values of the integers you wish to find the greatest common divisor, adding a comma in between the two integers.