Question

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 ?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

you know since b is equivalent to a mod 91

Answer 5

a mod 91=b mod 91=53 mod 91

Answer 6

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

Answer 7

a = ciphertext
b = plaintext

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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

Answer 12

I mean proove it right?

Answer 13

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

Answer 14

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

Answer 15

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 ?

Answer 16

\[
\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}\)?

Answer 17

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

Answer 18

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

Answer 19

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?

Answer 20

@ganeshie8 , @freckles

Answer 21

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

Answer 22

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

Answer 23

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

Answer 24

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.

Answer 25

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

Answer 26

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

Answer 27

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}
\]

Answer 28

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