logo
+1-617-874-1011 (US)
+61-7-5641-0117 (AU)
+44-117-230-1145 (UK)
Live Chat

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)
`}
Improve Your Grades with Custom Writing Help
Homework Help
Writing Help
Editing Services
Plagiarism check
Proofreading services
Research Project help
Custom writing services
scanner
E learning blogs

Disclaimer : The study tools and academic assistance/guidance through online tutoring sessions provided by AssignmentHelp.Net is to help and enable students to compete academically. The website does not provide ghostwriting services and has ZERO TOLERANCE towards misuse of the services. In case any user is found misusing our services, the user's account will be immediately terminated.