A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

RSA encryption For integers a and b, this is true b ≡ a (mod 91 ) and GCD (a, 91 ) = 1. a)Determine a positive integer k> 1 such that b ^ k ≡ a (mod 91 ) . b)What is a mod 91 for b = 53 ?

  • This Question is Closed
  1. freckles
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    can we use fermat's little theorem for the first question

  2. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Looks \(k\) is public key here which he needs to choose, not much to solve as such it seems..

  3. freckles
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    also question b seems weird that question seems equivalent to evaluating 53 mod 91

  4. freckles
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you know since b is equivalent to a mod 91

  5. freckles
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    a mod 91=b mod 91=53 mod 91

  6. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    suppose we choose \(k=5\), then he needs to generate the cipher text by rising \(53\) to the power \(5\)

  7. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    a = ciphertext b = plaintext

  8. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    you are suppose to determin k which I got to 73 in somehow...

  9. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I am beginning to feel that question has something missing..

  10. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Cant a be all the relatively primes to under 91? phi(91)?

  11. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    and the thing is I know b≡a mod 91 and need to show that b^k≡a mod 91

  12. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I mean proove it right?

  13. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    could you take a screenshot of actual question and post if psble

  14. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    its in swedish, and thats all there is...

  15. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    or maybe For integers a and b, applies to b ≡ a (mod 91 ) and gcd (a, 91 ) = 1. Determine a positive integer k> 1 such that b ^ k ≡ a (mod 91 ) . What is a mod 91 for b = 53 ?

  16. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    \[ \left(\gcd(a,91)=1\land a\equiv b\pmod{91}\right)\implies\gcd(b,91)=1? \] Since \(\phi(91)=72\), \(b^{72}=1\pmod{91}\) and \(b\equiv a \pmod {91}\), \(b^{73}\equiv b\equiv a\pmod{91}\)?

  17. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yes thomas thats what I did, but is that proof enough?

  18. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I guess so. If \(\gcd(b,91)=1\) then I think the proof is good enough.

  19. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    but if we know b≡ a(mod91) and we want to show b^k≡ a(mod91) we can write it as\[b*b ^{k-1}≡ a*1(\mod 91)\] right? and we want to show that \[b ^{k-1}≡ 1(\mod91)\] how we proove that? how does the actually proof looks like?

  20. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @ganeshie8 , @freckles

  21. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @thomas5267 and how do we know that GCD(b,91)=1?

  22. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Fermat's little theorem does not work here since 91 = 13 x 7. We have to use the Euler theorem. No idea how to prove it but the prove is in wikipedia. https://en.wikipedia.org/wiki/Euler's_theorem

  23. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @ganeshie8 is the number theory guy on this website so I will defer this to him. I need to cook an instant noodle now.

  24. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I guess we could do a Euclidean algorithm on \(\gcd(b,91)\)? \[ b=91q_{b0}+r_{b0}\\ \text{But }\gcd(a,91)=1\text{ and }{a\equiv b\pmod{91}}\\ \text{So }b=a+91n\text{ for some }n\in\mathbb{N}\\ \text{So }b\div 91\text{ must have the same remainder as }a\div91\\ r_{a0}=r_{b0}=r_0\\ \text{Consider the calculation of }\gcd(a,91)\text{ and }\gcd(b,91)\\ \begin{align*} a&=91q_{a0}+r_{0}&b&=91q_{b0}+r_{0}\\ 91&=q_{a1}r_0+r_{a1}&91&=q_{b1}r_0+r_{b1} \end{align*} \] We can see that in the second step of calculating \(\gcd(a,91)\) and \(\gcd(b,91)\) are the same. Therefore, so should the subsequent steps and the final result.

  25. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Actually \(\gcd(a,91)=1\) has nothing to do with b and a having the same remainder when divided by 91.

  26. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    So Thomas, how can we determine k from that? @thomas5267

  27. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Euler theorem states that: \[ a^{\varphi (n)} \equiv 1 \pmod{n} \] if \(\gcd(a,n)=1\) for a function \(\varphi\) named Euler's toitent function which I don't understand. Since \(\gcd(b,91)=1\), \[ b^{\varphi (91)} \equiv 1 \pmod{91}\\ \varphi(91)=72\quad\text{Wolfram|Alpha-ed the answer.}\\ b^{72} \equiv 1 \pmod{91}\\ b^{73}\equiv b \equiv a \pmod{91}\quad\text{since }b\equiv a \pmod{91} \]

  28. thomas5267
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Now excuse me, I have to go make myself a instant noodle.

  29. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.