This is my assignment in the file.It has 2 parts. I also have uploaded a solution to this assignment as well. Only thing you have to do is to solve it again using my student id and make a report. My student id is 1427755. Please make sure the answers are correct.
BIT112 Mathematics for IT Assignment 2 Task: Explore how Public Key Cryptography works. Using your Student ID, generate two primes and encrypt your student ID with your own Private Key. Send this to a recipient with a Public Key and recover your original Student ID. Use the Wiener attack to break your private key and is this way steal your identity by using your private key to encode another number and masquerade as you. (1) Making your own Keys: (i) Explore how Public Key Cryptography works and summarise this in your own words with particular attention to how the method generates these keys. (ii) From your exploration above, generate Private and Public Keys using your student ID. (iii) Using your student ID, determine how bits the number part can be represented with. (iv) For a particular number of binary bits determine the number of prime numbers available in that bit range. (v) (a) Using the Wolframalpha “nextprime” function and your student ID create two prime numbers which are of the form 4x+1. Such that P1=4x 1+1 and P2=4x 2+1. (b) Check that they have the same number of binary bits. (vi) (a) Using the Wolframalpha “nextprime” function and your student ID create two prime numbers which are of the form 4x+3. Such that P3=4x 3+3 and P4=4x 4+3. (b) Check that they have the same number of binary bits. (vii) (a) Use P1 and P2 to generate your private keys and encrypt your student ID. (b) Use P3 and P4 to generate your private keys and encrypt your student ID. Create a public key and use this to decrypt and recover your student ID. (2) Breaking the Keys: (i) Express P1 and P2 as the sum of two squares (for example . (ii) Draw these as two right angle triangles (a,b,c). Note that , (iii) (a) Using the equations below: Let P1=C1 and P2=C2 and let the smallest value of the two squares be express the sides of each triangle as: (b) Test that both your triangle solutions meet the condition that: . Represent this geometrically. (c) Multiply P1 and P2 together: P1 P2. Can be expressed as the sum of two squares? Does this correspond to part 2(iii)(a). (d) Using Euler’s factorization method, show how the original prime numbers can be recovered using the sum of squares method. (iv) Can P3 and P4 be represented as the sum of two squares? (v) Can P3 P4 be expressed as the sum of two squares as in (iii)(c)? Can Euler’s Factorization now be used? Why? (vi) For Primes, P1 and P2 , subtract 1 and multiply these together: (vii) Show that if are known, that the original primes P1 and P2 can be recovered. (viii) Using your public key, show how your private keys can be recovered using the Wiener attack by recovering P1 and P2. (ix) As the villain, armed with this information and masquerading as you, send a different encrypted Student ID (not yours) encrypted with the recovered key. Use the same public key as earlier to recover the masquerading Student ID. (3) Final Report: Your final report is a professional representation of parts (1) and (2) above, drawing on the relevant literature (including journals) where relevant and properly referencing these. You should also look at linkages between parts (1) and (2) and explore the structures of primes with particular attention to why primes of the type 4x+1 are weaker than 4x+3. Dr. Anthony Overmars FACS 25/06/2018 1 Major Assignment Maths Major Assignment Student ID = 1444198 Using the student ID number we have to generate the Private and Public Keys. Then, Using nextprime function two prime numbers of form 4n+1 are generated The two numbers hence obtained are, P1=1444213 and P2=1444217 Then, ∅ (N) = (P1-1) (P2-1) = 1444212 * 1444216 = 2085762977792 N = P1 * P2 = 1444213 * 1444217 = 2085756966221 Using the formula, ed=1Mod(∅ (N)) we get the value of, e = 834301631117 d = 5 Therefore, Public Key (Pu) = (N,e)= (2085756966221, 834301631117) Private Key (Pr) = (N,d)=( 2085756966221, 5) Then, from the formula, C= Pe mod N = 1444198^834301631117 mod 2085756966221 = 1025561663108 Then, using the formula, P= Cd mod N = 1025561663108 ^ 5 mod 2085756966221 = 1444198 The value of P is 1444198 which is the required original student ID number. Breaking the keys: P1= 1444213 P2= 1444217 The numbers P1 and P2 are then represented as the sum of two squares. (1182)2 + (217)2 = 1444213 (629)2 + (1024)2 = 1444217 Then, two right angled triangles are drawn, So, For the 1st triangle √1444213 217 1182 C = n2 + (2m + n - 1)2 = 2172 + (2m + 217 - 1)2 (1182)2 = (2m + 217 - 1)2 2m = 1182 – 216 m = 483 So, (m1, n1) = (483, 217) For 2nd triangle, √1444217 629 1024 C = n2 + (2m + n - 1)2 = 6292 + (2m + 629 - 1)2 (1024)2 = (2m + 629 - 1)2 2m = 1024 – 628 m = 198 So, (m2, n2) = (198, 629) Now, Let P1 = C1 and P2 = C2 and let the smallest value of the two squares be n For the 1st triangle, c1 a1 b1 a = (2m - 1)(2m + 2n - 1) = (966 -1) (966 + 434 - 1) = 1350035 b = 2n (n + 2n -1) = 434 (217 + 434 -1) = 282100 C = n2 + (2m + n - 1)2 = 47089 + (966 + 217 - 1)2 = 1444213 For the 2nd triangle, c2 a2 b2 a = (2m - 1)(2m + 2n - 1) = (396 - 1)(396 + 1256 -1) = 652145 b = 2n (n + 2n -1) = 1256 (628 + 1256 -1) = 2365048 C = n2 + (2m + n - 1)2 = 395641 + 1048576 = 1444217 Now, N = P1 * P2 = 1444213 * 1444217 = 2085756966221 5212702 + 13468612 = 2085756966221 9656862 + 10738752 = 2085756966221 Then, 5212702 + 13468612 = 9656862 + 10738752 9656862 – 5212702 = 13468612 - 10738752 Comparing with a2 – b2 = (a + b) (a - b) (1486956) (444416) = (2420736) (272986) A B C D A = 1486956 B = 444416 C = 2420736 D = 272986 gcd (A,C) = gcd (1486956, 2420736) = 2364 gcd (B,D) = gcd (444416, 272986) = 434 gcd (B,C) = gcd (444416, 2420736) = 2048 gcd (A,D) = gcd (1486956, 272986) = 1258 According to Euler's Factorization Method, = (11822 + 2172) (10242 + 6292) = (1444213) (1444217) Hence, these are the same prime numbers obtained by next prime function. We have to show that if ∅ (N) and N are known then the original primes P1 and P2 can be recovered. N = P1 * P2 = 1444213 * 1444217 = 2085756966221 ∅ (N) = (P1-1) (P2-1) = (1444213 - 1) (1444217 - 1) = 2085754077792 We have, ∅ (N) = (P1-1) (P2-1) ∅ (N) = P1P2 – P1 – P2 + 1 ∅ (N) = N – P1 – P2 + 1 P1 + P2 = N - ∅ (N) +1 Then, P2 = N - ∅ (N) +1 – P1 P1 = N - ∅ (N) +1 – P2 So, N = P1 (N - ∅ (N) +1 – P1) = P1N – P1∅ (N) + P1- P12 0 = P12 + P1 (∅ (N) – N - 1) + N Comparing with the equation ax2 + bx + c = 0, a = 1 b = ∅ (N) – N – 1 = -2888430 c = 2085756966221 Then, putting the values of a, b and c in the equation, For negative sign, x = 1444213 = P1 For positive sign, x = 1444217 = P2 Weiner Attack e = 834301631117 N = 2085756966221 Then, Its continued fraction is, Continued Fraction [0; 2, 1, 1, 72210, 5, 2, 1, 32822, 2, 1, 3] Therefore, k = 2 and d = 5 Now, = 2085754077792 We have, ∅ (N) = (P1-1) (P2-1) ∅ (N) = P1P2 – P1 – P2 + 1 ∅ (N) = N – P1 – P2 + 1 P1 + P2 = N - ∅ (N) +1 Then, P2 = N - ∅ (N) +1 – P1 P1 = N - ∅ (N) +1 – P2 So, N = P1 (N - ∅ (N) +1 – P1) = P1N – P1∅ (N) + P1- P12 0 = P12 + P1 (∅ (N) – N - 1) + N Comparing with the equation ax2 + bx + c = 0, a = 1 b = ∅ (N) – N – 1 = -2888430 c = 2085756966221 Then, For negative sign, x = 1444213 = P1 For positive sign, x = 1444217 = P2