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 < 22t􀀀2 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