$(20$ pts$)$ Using the extended Euclidean algorithm,

a$.$ Find the multiplicative inverse of $97$mod$53$

b$.$ Compute the greatest common divisor and find integers s and t according to:

$s**144+t**233=gcd(144,233)$

$(10$ pts$)$ Using Fermat's theorem, find $7^{235}$mod$17.$

$(20$ pts$)$ In a public$-$key system using RSA, you intercept the ciphertext $C=45$ sent to a user whose public key is $e=5,n=91.$ What is the plaintext $M?$

$(15$ pts$)$ Computing modular exponentiation efficiently is inevitable for the practicability of RSA. Compute the following exponentiation $x^e$ mod m applying the square$-$and$-$multiply algorithm:

$x=7,e=123,m=143$

$(20$ pts$)$ Using the Diffie$-$Helman Key Exchange $($DHKE$)$ scheme with the parameters $p=541,=5,$ and private keys $a=310,b=218,$ compute the two public keys and the shared secret key. Show all steps of the protocol.

$(15$ pts$)$ Given an RSA signature scheme with the public key $(n=221,e=11),$ which of the following signatures are valid? Explain.

a$.$