This assignment consists of two programming exercises, we prefer to use Python or Java. In the

first exercise, you are required to learn how to design and implement RSA. For the second one, you

have to learn how to find a collision on a Hash Function.

Exercise $1$: Design and implement a simple package based on the RSA algorithm to provide

encrypting$/$decrypting and digital signature signing and verifying.

a$.$ Generate two prime numbers: $p$ and $q.$

b$.$ Miller Rabin: to test the prime number.

c$.$ Euclid's algorithm: to find the encryption key $($e$)$

d$.$ Extended Euclid's algorithm $($EEA$)$: to find the decryption key $($d$).$

e$.$ choose any hash function which is available as free source.

f$.$ A main method to show different usage of RSA including dialogues between two

parties $($Alice and Bob$)$ that reflect encrypting$/$decrypting and digital signature signing

and verifying.

g$.$ Combine all of the above in a GUI model to test the functions.

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:

$7148927503d75c8fa85bcd602828d93b061c90bf$

So$,($SHA$60$v$)$ should outputs $"7148927503d75c8.$

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.