Exercise $2$: Finding a collision on hash function.

a$.$ Define a hash function $($SHA$60$v$)$ outputs the first $60$ bits $(15$ nibbles$)$ of SHA$-1.$ For

example, SHA$-1$ of $$CYS$406$ is:

$7148927503$d$75$c$8$fa$85$bcd$602828$d$93$b$061$c$90$bf

So$,($SHA$60$v$)$ should outputs $7148927503$d$75$c$8.$

b$.$ Find any collision in SHA$60$v$.$ You should find two different messages such that the Linux

command:

echo $-$n msg $|$ sha$1$sum $-|$ cut $-$c$1-15$

produces the same answer when msg is replaced by each message. To enable us to verify

your answer, please make sure the two messages are typable on a regular keyboard!

Hint: You should not write the code for SHA$-1$; you should use an existing library. Also,

it$$s a good idea to find shorter collisions first. For example, start off finding a collision for

the first $24$ bits $(6$ nibbles$)$; that$$s a lot easier. The challenge that $60$ bits gives you is that

you probably can$$t store all the intermediate hashes you generate in memory $($Read

about Floyd's algorithm$).$ Nevertheless, you should be able to write a program which

finds a $60-$bit collision in a few hours on a regular desktop or laptop computer