anonymous
  • anonymous
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 ?
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
freckles
  • freckles
can we use fermat's little theorem for the first question
ganeshie8
  • ganeshie8
Looks \(k\) is public key here which he needs to choose, not much to solve as such it seems..
freckles
  • freckles
also question b seems weird that question seems equivalent to evaluating 53 mod 91

Looking for something else?

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

More answers

freckles
  • freckles
you know since b is equivalent to a mod 91
freckles
  • freckles
a mod 91=b mod 91=53 mod 91
ganeshie8
  • ganeshie8
suppose we choose \(k=5\), then he needs to generate the cipher text by rising \(53\) to the power \(5\)
ganeshie8
  • ganeshie8
a = ciphertext b = plaintext
anonymous
  • anonymous
you are suppose to determin k which I got to 73 in somehow...
ganeshie8
  • ganeshie8
I am beginning to feel that question has something missing..
anonymous
  • anonymous
Cant a be all the relatively primes to under 91? phi(91)?
anonymous
  • anonymous
and the thing is I know b≡a mod 91 and need to show that b^k≡a mod 91
anonymous
  • anonymous
I mean proove it right?
ganeshie8
  • ganeshie8
could you take a screenshot of actual question and post if psble
anonymous
  • anonymous
its in swedish, and thats all there is...
anonymous
  • anonymous
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 ?
thomas5267
  • thomas5267
\[ \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}\)?
anonymous
  • anonymous
yes thomas thats what I did, but is that proof enough?
thomas5267
  • thomas5267
I guess so. If \(\gcd(b,91)=1\) then I think the proof is good enough.
anonymous
  • anonymous
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?
anonymous
  • anonymous
@ganeshie8 , @freckles
anonymous
  • anonymous
@thomas5267 and how do we know that GCD(b,91)=1?
thomas5267
  • thomas5267
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
thomas5267
  • thomas5267
@ganeshie8 is the number theory guy on this website so I will defer this to him. I need to cook an instant noodle now.
thomas5267
  • thomas5267
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.
thomas5267
  • thomas5267
Actually \(\gcd(a,91)=1\) has nothing to do with b and a having the same remainder when divided by 91.
anonymous
  • anonymous
So Thomas, how can we determine k from that? @thomas5267
thomas5267
  • thomas5267
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} \]
thomas5267
  • thomas5267
Now excuse me, I have to go make myself a instant noodle.

Looking for something else?

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