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!

Homework Help: Polynomial finite fields; ElGamal decryption

  1. Dec 15, 2012 #1
    1. The problem statement, all variables and given/known data
    Given some ElGamal private key, and an encrypted message, decrypt it.

    2. Relevant equations
    Public key (F_q, g, b)
    Private key a such that b=g^a

    Message m encrypted so that r=g^k, t=mb^k

    Decrypt: tr^-a = m

    3. The attempt at a solution

    My problem is finding r^-a. I don't quite get polynomial finite fields, and I can't figure out how to get x such that r^x = r^-a in F_q.

    I have an example from the textbook:
    Public key (F_23, 7, 4), private key a=6, encrypted message r=21, t=11

    The textbook then does 11*21^-6 = 11*21^16 = 11*2^16 = 11*9 = 7

    I understand why 11*2^16 = 7 in F_23, but I don't get how 21^-6 = 21^16 and how 21^16 = 2^16.

    Any help is appreciated.
  2. jcsd
  3. Dec 15, 2012 #2
    Since 23 is a prime number, the field F23 is essentially just the set {0,1,2,...,22} with addition and multiplication carried out modulo 23.

    Do you know Fermat's Little Theorem? It says that for any prime p and and any integer a, we have ap-1 ≡ 1 (mod p), which you can use to show 21-6 = 2116 in F23.

    Also, since addition in F23 is done modulo 23, you have x = 23 - x for all x ∈ F23, which gives you 2116 = 216.
  4. Dec 15, 2012 #3
    Thanks, that helps.

    Yes, I do know Fermat's little theorem, I feel silly now for not thinking of it.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook