- #1

- 24

- 0

## Homework Statement

Given some ElGamal private key, and an encrypted message, decrypt it.

## Homework 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

## 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.