2
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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$.

Hint: It will involve exponentiations and multiplications.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ok but what I get by solving E.E.A for eA and eB. Inverse of eA in mod eB ? $\endgroup$
    – Kaan
    Commented Nov 26, 2015 at 13:42
  • $\begingroup$ No, you get a pair of s and t such that seA + teB = 1 (as stated in your question prompt). $\endgroup$
    – klewi
    Commented Nov 27, 2015 at 15:34
0
$\begingroup$

I found my answer from a different question very similar to mine from this(crypto.stackexchange). Hope it helps.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.