1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

RSA Algorithm Help

  1. Jul 10, 2009 #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. Jul 10, 2009 #2

    Borek

    User Avatar

    Staff: Mentor

    Shouldn't all number involved be integers?
     
  4. Jul 10, 2009 #3
    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. Jul 12, 2009 #4
    Can anyone help with this? Will ask my math/physics teacher tomorrow but wouldnt mind having another go at it first.

    Cheers
    James
     
  6. Jul 12, 2009 #5

    Borek

    User Avatar

    Staff: Mentor

    I am sure these should be all integers, but I have not played with RSA for several years.
     
  7. Jul 12, 2009 #6
    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. Jul 12, 2009 #7

    Borek

    User Avatar

    Staff: Mentor

    mod never gives fractions, mod is about finding remainder.

    10 mod 3 = 1
    12 mod 5 = 2

    and so on.
     
  9. Jul 12, 2009 #8

    HallsofIvy

    User Avatar
    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!

     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...