Problem $3,$ Part $1$

Alice sends a message $($M$)$ to Bob, encrypted using the public RSA key to get C$1=14.$

Eve intercepts the encrypted ciphertext, and wants uncover m using a chosen ciphertext attack, based on the fact that RSA is homomorphic under multiplication.

If Eve performs a homomorphic multiplication of C$1$ by $5,$ what will be Eve's ciphertext $($c$2)?$

Write a function that performs a homomorphic multiplication of c by x$.$

PUB$\_$KEY $=(55,3)$

C$1=14$

# RSA Encryption

# @param m $[$Int$]$ plaintext

# @param key $[($Int$,$ Int$)]$ the public key

# @return $[$Int$]$ ciphertext

def encrypt$($m$,$ key$)$:

n$,$ e $=$ key

return m$**$e $\%$ n

# Performs homomorphic multiplication on encrypted ciphertext

# @param c $[$Int$]$ original ciphertext

# @param x $[$Int$]$ number to multiply by

# @param key $[($Int$,$ Int$)]$ the encryption key

# @return $[$Int$]$ new ciphertext

def homomorphic$\_$multiplication$($c$,$ x$,$ key$)$:

# PROBLEM $3$ PART $1$

YOUR WORK HERE

Problem $3,$ Part $2$: In a chosen ciphertext attack, the attacker chooses a ciphertext $($C$2)$ and gets its corresponding decrypted plaintext $($p$2).$

Write a function showing how Eve can uncover Alice's plaintext M from C$1.$

# Bob decrypts using private key

# @param c $[$Int$]$ ciphertext

# @return $[$Int$]$ plaintext

def decrypt$($c$)$:

d $=27$

return $($c$**$d$)\%$ PUB$\_$KEY$[0]$

# Eve can uncover Alice's plaintext using the chosen ciphertext

# @param x $[$Int$]$ the multiplier

# @param p $[$Int$]$ the decryption of ciphertext homomorphically multipled by x

# @param key $[($Int$,$ Int$)]$ the public key

# @return $[$Int$]$ the original plaintext

def eve$($x$,$ p$,$ key$)$:

# PROBLEM $3$ PART $2$

# YOUR WORK HERE

PROBLEM $3$ PART $3$: How can padding prevent this attack? Write a padding function.

P# Simple padding function for messages $0-9$

# @param m $[$Int$]$ plaintext

# @return $[$Int$]$ padded plaintext

def pad$($m$)$:

# PROBLEM $3$ PART $3$

# YOUR WORK HERE