Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By Deveno
  • 1 Post By Deveno

Math Help - RSA cipher problem

  1. #1
    Junior Member
    Joined
    May 2014
    From
    UK
    Posts
    38

    RSA cipher problem

    Here is part a:

    First applying the division algorithm repeatedly :

    160 = 2 x 77 + 6
    77 = 12 x 6 + 5
    6 = 1 x 5 + 1

    Now eliminating multiples of 5 and 6 :

    1 = 6 -1 x 5
    = 6 -1(77 - 12 x 6)
    = (1 x 6) - (1 x 77) + (12 x 6)
    = -1 x 77 + 13 x 6
    = -(1 x 77) + 13(160 - 2 x 77)
    = -(1 x 77) + (13 x 160) - (26 x 77)
    = -27 x 77 + 13 x 160

    Hence :

    -27 x 77 = -13 x 160 + 1

    and -27 is congruent to 133(mod 160)

    Thus the multiplicative inverse of 77 in Z160 is 133.

    Now an RSA cipher is defined on Z205 by R77 (m) congruentm77 (mod 205)

    b) write down the deciphering rule for this cipher justifying your answer to reference to part (a)

    From part (a) we know that (R77)^-1 = R133


    A message is coded numerically using the correspondence A = 1, B=2, ..., Z=26. It is then enciphered using the RSA cipher above to give the cipher text <1, 115>.

    c) By using the repeated squaring technique decipher the cipher text and recover the message.

    Now we need to find the R133(1) and R133(115)

    R133(1) = 1 = 1 (mod 133) = 1

    R133(115) = 115^1 = 115 (mod 133) = 115
    = 115^2 = 13225 (mod133) = 58
    = 115^4 = 58^2 = 3364 (mod 133) = 39
    = 115^8 = 39^2 = 1521 (mod 133) = 58

    From here the sequence repeats alternating between 39 and 58.

    Then I used R133(115) = 115^128 x 115^4 x 115^1 = 58 x 39 x 115 = 260130 = 115 (mod 133)

    Which for me looks totally wrong since there is no letter correspondet to the value of 115.

    Hope my notations is not too messy. I really need to understand where I went wrong.

    xxx

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: RSA cipher problem

    OK, this is my understanding of RSA-style encryption:

    First, one picks two distinct primes, $p$ and $q$. The message is then encoded using a modulus $n = pq$.

    The encryption key $e$ is then chosen to be an integer $1 < e < \varphi(n)$, where $\varphi$ is the Euler totient function.

    The message $m$ (which is an integer) is then turned into the ciphertext $c = m^e\text{ (mod }n)$.

    Together, $(e,n)$ make up the public key.

    The private key (which must be kept secret) is $(d,n)$, where $d = e^{-1}\text{ (mod }\varphi(n))$

    The message $c$ is sent to the holder of the private key.

    To recover the plaintext $m$, one computes:

    $c^d = (m^e)^d = m^{ed} = m^{ee^{-1}} = m\text{ (mod }\varphi(n))$

    ***************************

    I am unfamiliar with your notation, so what follows here is just a guess:

    $p = 5, q = 41$, so that $n = 205$ and $\varphi(n) = \varphi(5)\varphi(41) = (4)(40) = 160$.

    Presumably, we have "two messages" encoded, $c_1 = 1$ and $c_2 = 115$

    Presumably the encryption key is $77$.

    To find the decryption key, we compute $(77)^{-1}\text{ (mod }160)$, which we have previously found to be $133$.

    Next, we calculate $1^{133}$ and $115^{133}$ modulo $205$.

    The first one is easy, it will be $1$. The second one is a bit more involved. I do not know what this "method of repeated squaring" is, but it may be similar to what I have done below (and my calculations may be off).

    Working mod 205, we have:

    $(155)^{133} = (115)((155)^2)^{66}$. As $115^2 = 13225 = 13120 + 105 = 64*205 + 105$, this is:

    $= (115)(105)^{66} = (115)((105)^2)^{33}$. Now $105^2 = 11025 = 10856 + 160 = 53*205 + 160$, so:

    $= (115)(160)^{33} = (115)(160)(160)^{32}$. Dealing with the left first, we have $(115)(160) = 18400 = 18245 + 155 = 89*205 + 155$, so we have:

    $= (155)(160)^{32} = (155)((160)^2)^{16}$. So (whew, this tires me out) $160^2 = 25600 = 25420 + 180 = 124*205 + 180$, and:

    $= (155)(180)^{16} = (155)((180)^2)^8$. Same process: $180^2 = 32400 = 32390 + 10 = 158*205 + 10$, thus:

    $= (155)(10)^8 = (155)(100)^4 = (155)(100^2)^2$. Here, $100^2 = 10000 = 9840 + 160 = 48*205 + 160$, and we get:

    $ = (155)(160)^2 = (155)(180)$ (we calculated $160^2$ earlier). As $(155)(180) = 27900 = 27880 + 20 = 136*205 + 20$, we finally arrive at:

    $= 20$.

    So the decrypted numerical message is: <1,20>, that is the text message is: <A,T>.

    ***************************

    The above has a lot of guesswork on my part, and my calculations may be wrong.
    Thanks from michele
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2014
    From
    UK
    Posts
    38

    Re: RSA cipher problem

    Thanks again Deveno your guesses are right and I could follow your work till the point she you calculated 1 ^133 and 115 ^133 modulo 205.
    Why do you used modulo 205? On mine calculation I used modulo 133 since (77)−1 (mod 160) = 133.

    I'm not saying you are wrong just wanna understand the reasons specially because with the modulo 205 you come to a result and with the modulo 133 I got stuck.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: RSA cipher problem

    The encryption and decryption takes place mod 205.

    The exponents we use ($d$ and $e$) are calculated using mod $\varphi(205)$ = mod 160.

    The reason we do this is that if $\text{gcd}(a,n) = 1$,

    $a^{\varphi(n)} = 1\text{ (mod }n)$ <---this is often called Euler's theorem.

    So if $u = v\text{ (mod }n)$ we have:

    $a^u = a^{v + k\varphi(n)} = a^v\cdot a^{\varphi(n)} = a^v\cdot 1 = a^v \text{ (mod }n)$

    That is, when working mod n, and working with exponents, we work mod $\varphi(n)$ in the exponents.

    Since our encryption exponent is 77, we need to find the inverse of 77 mod 160, which "undoes" the encryption when we exponentiate by it.

    But both the encryption and decryption take place mod 205. The 133 is just the $d$ we need to exponentiate by to decrypt, just like 77 is the $e$ we use to encrypt.
    Thanks from michele
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    May 2014
    From
    UK
    Posts
    38

    Re: RSA cipher problem

    Deveno I finally could understand it and by using my method I was able to arrive to the same result that you pointed out of 1 and 20.
    Thank you so much for all your help and attention.

    xxx
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: January 24th 2013, 10:13 AM
  2. A little cipher I could use help on.
    Posted in the Algebra Forum
    Replies: 0
    Last Post: November 13th 2012, 02:53 PM
  3. Cipher using Mod
    Posted in the Math Puzzles Forum
    Replies: 6
    Last Post: April 26th 2012, 06:13 PM
  4. A cipher problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 30th 2009, 11:55 AM
  5. Hill Cipher Problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 10th 2006, 11:58 AM

Search Tags


/mathhelpforum @mathhelpforum