Polynomial finite fields; ElGamal decryption

  • Thread starter LANS
  • Start date
  • #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.
 

Answers and Replies

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

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.
 
  • #3
24
0
Thanks, that helps.

Yes, I do know Fermat's little theorem, I feel silly now for not thinking of it.
 

Related Threads on Polynomial finite fields; ElGamal decryption

Replies
12
Views
5K
Replies
0
Views
1K
Replies
2
Views
5K
Replies
7
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
8
Views
1K
Replies
3
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
888
Top