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.

$\endgroup$

2 Answers 2

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.

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

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .