1
$\begingroup$

Having an ElGamal encryption scheme with p=19 which value can not be assigned to g?

The answers were : 1,7,11,2

I think you can't assign value 1 to g.

$\endgroup$
11
  • $\begingroup$ What would happen to the public key if you use 1 as your g? How would your ciphertext look like? $\endgroup$
    – DrLecter
    Commented May 29, 2015 at 20:53
  • $\begingroup$ As far as I know. I have my p=19 and g=1; I choose a random value a(1,p-2) , 3 for example. i know compute: g^a mod p -> 1^3 mod 19 wich is 1. So my Public Key Pb(19,1,1) and Pv(19,1,3). For encryption I choose a random k value : 7 for example. c1= 1^7 mod 19 = 1; c2 is m(g^a)^k mod p . so c2 is m mod p. If m=2; 2 mod 19=2. So the encrypted message c is (1,2) $\endgroup$ Commented May 29, 2015 at 21:02
  • $\begingroup$ I am having a little bit trouble to understand why can't we use one of the values for generator g (1,7,11,2) and wich is the value or the values from these ones that we can't use $\endgroup$ Commented May 29, 2015 at 21:07
  • $\begingroup$ You agree if your public key is 1, then c2 will be the plaintext? $\endgroup$
    – DrLecter
    Commented May 29, 2015 at 21:09
  • $\begingroup$ @DrLecter: I agree with user3626136, I don't see the issue; with $g=1$, you can encrypt just fine, and decrypt just fine. There might be some minor security issuest; on the other hand, I don't see how any other value of $g$ would give significantly better security with $p=19$, so if we reject it on that basis, we'd have to reject all values of $g$ :-) $\endgroup$
    – poncho
    Commented May 29, 2015 at 21:12

1 Answer 1

1
$\begingroup$

We can choose a generator which is a primitive root. We can check that 1,7,11,12 are not primitive roots for p=19. So they cannot be chosen as a generator.Given any number we can check if it is a primitive root or not. (https://math.stackexchange.com/questions/124408/finding-a-primitive-root-of-a-prime-number).

$\endgroup$
1
  • 1
    $\begingroup$ Actually, it's 2, not 12, and 2 is a primitive root. That being said, El Gamal doesn't require us to select a value which is a primitive root; for security, we do want an element with an order with a large prime factor; in the p=19 case, that's not possible. $\endgroup$
    – poncho
    Commented Oct 28, 2015 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.