# Find plaintext of RSA by solving extended euclidean algorith for two encrptions with two different exponents for same plaintext

This is my homework question (but I am not asking the answer to it):

Suppose two users Alice and Bob have the same RSA modulus n and suppose that their encryption exponents eA and eB are relatively prime (i.e. seA + teB = 1 for some integers s and t). Charles wants to send the message m to both Alice and Bob, so he encrypts and get cA = m^eA (mod N) and cB = m^eB (mod N).

1. Show how Eve can find m if she intercepts cA and cB. You need to compute s and t in equation seA + teB = 1 using extended Euclidean algorithm.

2. Consider the following and find the plaintext message m corresponding to the ciphertext c.

N: 136745826084894079896407801910110038124479691221364763961671283913316027446990472604166612638266533599236499833462893193203370069481216752405013210606536832449253647053485706549372755012732494721775959042565139073644140943011453312866103727053029250591408277684758918149145313790583917977714246616161591211867

eA = 7

eB = 11

cA: 96877134584306777318146328481686066222141330594741430174446869322397957214185808322840439483745941838089581856276435139923985154286304605247720570032111445774456843140029117473338511849604175899567577575869260936284515510510996731062938376853679783133818780455950141113597757693159944213099453748070224766330

cB: 23444046879417396807258781473983446335419912082084569500429331818137930632660557096072074135726913203064466954036513216225141761504938430253703707788298770147822214014349806771971766671953205102486778576265971021057237610662398273682920299760392069897739849342885155671199969974517817986247611249755737698500

My question is: I cannot understand what I get by solving extended euclidean algorithm for eA and eB. I know that if I solve E.E.A. for eA and phi of N, I get the decrption key.

I have tried many things including stupid ones but at this point I need help.

If you are able to compute $m^1 \pmod{N}$, then you have (obviously) recovered the message $m$. So, you should be able to use the extended Euclidean algorithm to express $m^1 \pmod{N}$ in terms of $c_A$ and $c_B$.