RSA Algorithm Help

  1. Struggling to put a number through this as I keep getting my original number as the encrypted number too.

    A = 11
    p = 3 q = 5
    n = pq = 15
    z = (p-1)(q-1) = 2*4 = 8
    k = co-prime of z = 7

    So,

    A=11
    n=15
    z=8 (Public key)
    k=7(Public key)

    kj = 1 (mod z)
    7j = 1 (mod 8)

    for which I am getting j = 9/7 (private key)

    Start of encryption...

    A^k = E (mod n)
    11^7 = E (mod 15)

    19487171/15 = 1299144.733......

    1299144 * 15 = 19487160

    E = 19487171 - 19487160 = 11 (which is what I started with)


    Tried using the decrypting part anyway and got....

    E^j = A (mod n)

    11^(9/7) = A (mod 15)

    21.8239547419283/15 = 1.45493031612855

    1 * 15 = 15

    21.8239547419283 - 15 = 6.8239547419283 (which obviously isnt what I started with)

    Any help where I am going wrong would be appreciated, I assume it is where mod is brought in as I havent used that function before 2 hours ago but it may be somewhere else.

    Cheers
    james
     
    Last edited: Jul 10, 2009
  2. jcsd
  3. Borek

    Staff: Mentor

    Shouldn't all number involved be integers?
     
  4. I'm not sure. Thats where I think I have gone wrong though.

    Think I messed up at

    kj = 1 (mod z)
    7j = 1 (mod 8)

    trying to work out the private key as I have tried to teach myself how to do this from an example on a website without really knowing how to do it.

    James
     
  5. Can anyone help with this? Will ask my math/physics teacher tomorrow but wouldnt mind having another go at it first.

    Cheers
    James
     
  6. Borek

    Staff: Mentor

    I am sure these should be all integers, but I have not played with RSA for several years.
     
  7. I think you are right but I am getting fractions when the modulus function is introduced as I'm unsure how it works.

    James
     
  8. Borek

    Staff: Mentor

    mod never gives fractions, mod is about finding remainder.

    10 mod 3 = 1
    12 mod 5 = 2

    and so on.
     
  9. HallsofIvy

    HallsofIvy 40,241
    Staff Emeritus
    Science Advisor

    Just try some possibilities: 7(1)= 7, 7(2)= 14= 8+ 6, 7(3)= 21= 2(8)+ 5, 7(4)= 28= 3(8)+ 4, 7(5)= 35= 4(8)+ 7, 7(6)= 42= 5(8)+ 2, 7(7)= 49= 6(8)+ 1. 7j= 1 (mod 8) if and only if u= 7 (mod 8). I can't speak for "kj= 1 (mod z)" because I don't know what z is!

     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook