Results 1 to 1 of 1

Math Help - Chinese Remainder Theorem -- Rabin Cryptosystem... how to decrypt?!

  1. #1
    Newbie
    Joined
    Jun 2009
    Posts
    1

    Chinese Remainder Theorem -- Rabin Cryptosystem... how to decrypt?!

    there are too many websites that use tons of jargons and tons of copy and pasted stuff without showing any workings or useful examples, so here i am.

    this is what i understand of the Rabin Cryptosystem. do correct me if im wrong.

    p and q are primes.
    p = 11, q = 13
    n = pq = 143

    To encrypt a message m = 15, the cipher c:

    c = 15^2 mod 143
    = 82 mod 143

    To decrypt the message, i will need

    mp = sqrt(c) mod p
    = sqrt(82) mod 11

    mq = sqrt(c) mod p
    = sqrt(82) mod 13

    how do i get the values of mp and mq where they must be integers?

    at the moment, im brute forcing the numbers by calculating (x = c + mod + mod + ...) until i find that sqrt(x) is an integer. is there an algorithm that does this in a more efficient manner?
    Last edited by theChameleon; June 2nd 2009 at 01:42 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 21st 2011, 06:47 AM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 10th 2010, 01:24 PM
  3. CRT(chinese remainder theorem)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 19th 2009, 09:01 PM
  4. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: July 31st 2009, 07:34 AM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 6th 2008, 06:07 AM

Search Tags


/mathhelpforum @mathhelpforum