hash function assignment question
{` For Part A, we introduce the Chaum-van Heijst-P_tzmann hash. Given an integer t, a prime number p of size t bits, and two integers , in [1;], this hash function takes a positive integer n < 22t2 and returns a value (called digest or hash) in the range [1; p-1], according to the following principles: 1. Split n into two (t -1)-bit integers n1 and n2 such that the binary representation of n is the concate-nation of the binary representations of n1 and of n2. 2. Return alpha^n1 beta^n2 (mod p) Ultimately, you will need to implement a function that takes a string and returns a number that is in [1; p-1] expressed in hexadecimal notation. Note that, we will use the C notation starting with pre_x 0x. **********************************/ /* Part A - Hash Function */ /**********************************/ /**********************************/ /* Predefined Functions */ /**********************************/ \\convert a string of characters to a decimal number based on 7 bit ASCII representation of a character {StringToDecimal(S) = local(T, V, i, j, tmp); T = ""; V = []; for(i = 1, length(S), for(j = 32, 127, U = Strchr(j); tmp = concat(T, U); if(S < tmp, V = concat(V, j - 1);T = concat(T, Strchr(j - 1)); break))); return(subst(Pol(V),x,128))} \\list of symbols used for hexadecimal notation symbol = ["0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F","_"]; \\convert a decimal number to hexadecimal notation {DecimalToHexa(nb) = local(t, w, i); if(nb == 0, return(x0), w = ""; t = nb; while( t != 0, i = t%16; t = (t - i)/16; w = concat(symbol[i+1], w); ); return(concat("0x",w)); ); } /**********************************/ /* Setup */ /**********************************/ t = 56 p = 44910251253799199 alpha = 31265873465631644 beta = 13634408797649160 /**********************************/ /* Task 1. [15 marks] */ /**********************************/ What is the digest of "ULChwtzP8Wj0" using the hash function defined with the parameters above? /**********************************/ /* Task 2. [25 marks] */ /**********************************/ Find a password whose digest is equal to "0x5E636E5B93C88C" using the hash function defined with the parameters above /**********************************/ /* Task 3. [5 marks] */ /**********************************/ Find a collision (i.e. two different integers < 2^(2*t-2) which evaluate to the same value) for the hash function defined with the following parameters: t = 32 p = 3146217623 alpha = 1393526168 beta = 2230386161 /**********************************/ /* Task 4. [5 marks] */ /**********************************/ Find a collision (i.e. two different integers < 2^(2*t-2) which evaluate to the same value) for the hash function defined with the following parameters: t = 56 p = 44910251253799199 alpha = 31265873465631644 beta = 13634408797649160 /**********************************/ /* Part B - Elliptic Curve Crypto */ /**********************************/ /**********************************/ /* Setup */ /**********************************/ p = 591906931561661 a = 53530791695143 b = 103773580651240 E is defined by: y^2 = x^3 + a*x + b (mod p) P = [43888214552398, 340551161412751] is a point on E of order 3146217623 Alice's private key: nA = 138584342383592 Alice's public key : PA = nA*P = [441673626742891, 393658091332851] Bob's private key: nB = ? Bob's public key : PB = nB*P = [323099168153182, 109984849726896] Charlie's private key: nC = ? Charlie's public key : PC = nC*P = [509822071995978, 565954369616828] /**********************************/ /* Task 5. [15 marks] */ /**********************************/ Find the point Q with smallest possible x-coordinate > 0 and with corresponding y coordinate < p/2 Find the point R with largest possible positive x-coordinate < p and with corresponding y coordinate > p/2 Compute Q + R /**********************************/ /* Task 6. [25 marks] */ /**********************************/ Bob encrypted his birthday and sent it to Alice in the form of the following point C = [534952379604280, 583330303810087] What is Bob's birthday? /**********************************/ /* Task 7. [5 marks] */ /**********************************/ Retrieve Bob's private key /**********************************/ /* Task 8. [5 marks] */ /**********************************/ Retrieve Charlie's private key Hint for Task 2 A possible password is of length 8 and its first characters are: su This only affects Task 8 The order of the point P is not 3146217623 The order of P is 591906960330667 This can be verified by computing ellorder(E, P) `}
Improve Your Grades with Custom Writing Help
Homework Help
Writing Help
Editing Services
Plagiarism check
Proofreading services
Research Project help
Custom writing services