Recall hash puzzles from Lecture 10. In this question, we will see how they work in practice. This question requires pro
Posted: Sun May 15, 2022 1:36 pm
Recall hash puzzles from Lecture 10. In this question, we will
see how they work in practice. This question requires programming
in a language that has an implementation of SHA-256 hash function.
You could use Java to program, although, you are free to use any
other language with a library containing SHA-256, e.g., Python’s
hashlib (which maybe easier to implement). Create an integer s
containing all the digits in your student ID. For example, if my
student ID is 12345678, then s = 12345678. Let “str” denote the
string function, i.e., given any integer s, the function str(s)
casts it into a string. For example, s = 12345678 becomes str(s)
=“12345678”. Set the target t to: t = 2 256/40
Let H be the SHA-256 hash function. Let r be a counter starting
from 0. Finally, let “||” denote string concatenation.
(a) Implement a program that tries successive values of r, i.e.,
r = 1, 2, 3, . . ., computes H(str(s)||str(r)), compares it with t
and halts whenever H(str(s)||str(r)) < t, with the output r. You
need to provide the program and the output r.
(b) Let us call the program from part (a) as: PuzzleFinder(s,
t). Write a program that calls PuzzleFinder with successive inputs
(s + i, t), for i = 0 to 999, and records the output for each of
these 1,000 runs. What is the average number of attempts before you
found the target? You need to provide your program.
(c) If you drew random values between 0 and 2256 − 1 inclusive,
how many attempts on average it would take before you find a value
below the target? Compare this number to the answer obtained in
part (b). What does it tell you about SHA-256?
see how they work in practice. This question requires programming
in a language that has an implementation of SHA-256 hash function.
You could use Java to program, although, you are free to use any
other language with a library containing SHA-256, e.g., Python’s
hashlib (which maybe easier to implement). Create an integer s
containing all the digits in your student ID. For example, if my
student ID is 12345678, then s = 12345678. Let “str” denote the
string function, i.e., given any integer s, the function str(s)
casts it into a string. For example, s = 12345678 becomes str(s)
=“12345678”. Set the target t to: t = 2 256/40
Let H be the SHA-256 hash function. Let r be a counter starting
from 0. Finally, let “||” denote string concatenation.
(a) Implement a program that tries successive values of r, i.e.,
r = 1, 2, 3, . . ., computes H(str(s)||str(r)), compares it with t
and halts whenever H(str(s)||str(r)) < t, with the output r. You
need to provide the program and the output r.
(b) Let us call the program from part (a) as: PuzzleFinder(s,
t). Write a program that calls PuzzleFinder with successive inputs
(s + i, t), for i = 0 to 999, and records the output for each of
these 1,000 runs. What is the average number of attempts before you
found the target? You need to provide your program.
(c) If you drew random values between 0 and 2256 − 1 inclusive,
how many attempts on average it would take before you find a value
below the target? Compare this number to the answer obtained in
part (b). What does it tell you about SHA-256?