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) `}
Subjects List
Database (48)
Accounting (39)
Economics (34)
Finance (54)
Programming (122)
Management (69)
Marketing (25)
Report Writing (52)
Engineering (79)
Statistics (39)
Business Studies(45)
Case Studies (15)
Networking (26)
UML (9)
Science (23)
Nursing (11)
MATLAB (17)
Psychology (6)
Math (20)
Data Structure (9)
Python (15)
HRM (25)
IT (21)
Computer Science (57)
Law (4)
Essay (3)
Data Analysis (2)
Big Data (3)
Philosophy (2)
History (1)