0
$\begingroup$

I am a beginner in cryptography. I studied the Elgamal algorithm. I know that:

p = A big prime number
g = Generator of p
a = 0<a<p-1
B = g^a mod p
secret key= (p,g,a)
public key= (p,g,B)
Encryption= c1=(g^k mod p) , c2=(m.B^k mod p) // 0<k<p-1

Now, I want to solve an exercise.

pk =9789467
g =10895499
n =16777216

c1 =C763515DF26161E21BAB53C35CE2B3B12419B5F5835D1B7B2FE761C9DF5149F4734C149944EA0B4637BBA71EB163CBA99F87611915038DEBA37650E1D69E1380CE6310D7114FD58BC605F1AF334B7044B1

c2 =C57120363903E441B7C90BEB72AFC48AD13D48D5DBF440602DB5C54CE1B490E1604251A1FF47A1D969831C05FFF7D55EAEE120EE7AECDCB0BDF9C5C9B634CACC79EA34485DAC8449D19947E70F1A276EDD

If g is generator, what is pk and n? pk and n are not prime numbers!

$\endgroup$
  • $\begingroup$ The generator is public, not secret. The public key contains $B=g^a$ for a random $a$ between 1 and p - 1. (inclusive) The secret key contains $a$. $\endgroup$ – sel May 9 '17 at 11:07
  • 1
    $\begingroup$ The public key is $p,g,B$, and the secret key is just $a$. And the generator should be of prime order for some large prime $q$ (which divides $p-1$). You definately have to keep $a$ secret, you have it in both keys. And then: Exponentiation is done modulo $p$. Your numbers look like regular exponentiation - the result can not be larger than $p$. Also it doesn't help if your values $pk,g,n$ look like decimal, while the $c1,c2$ values look like hexadecimal encoded. Maybe state where the exercise is from? It looks quite strange. $\endgroup$ – tylo May 9 '17 at 11:12
  • $\begingroup$ Excuse me, I edited my post! Excercise in the internet:researchgate.net/post/… $\endgroup$ – user7747790 May 9 '17 at 12:46
1
$\begingroup$

The exercise is not about ElGamal in the slightest. I would even call it bogus:

  • "$n$" would be the modulus, which is clearly not prime, being divisible by $2$.
  • The values $pk,g,n$ seem to be in decimal, the values $c_1,c_2$ in hexadecimal - but nowhere stated what kind of encoding is used.
  • It looks like exponentiation in the integers was used, but $c_1$ isn't a power of $g$
  • Trying around in WolframAlpha how those values were generated I got nothing, but $c_1$ isn't divisible by $n,pk$ or $g$ when considering them as decimal or hexadecimal encoding.
  • Is it a coincidence, that if you want to do some WolframAlpha computations with these numbers in decimal, the input field is just not long enough? $c_1$ alone fits, but it leaves you just with 5 more input characters. Using all numbers in hex works, tho.

Since the source you quoted is another question how to interpret this, this is definitely not the author.

At this point I can only suggest looking for reliable sources, e.g. exercise material from universities, textbooks or examples on Wikipedia. Looking at any kind of material where you don't know the author and the background has the potential to actually damage your learning progress.

$\endgroup$
  • $\begingroup$ Thanks, so they are not any variables for Elgamal encryption, and I can not decrypt it just with c1, c2 and g. yes? $\endgroup$ – user7747790 May 9 '17 at 17:39
  • $\begingroup$ Yes. Whatever those numbers are, they are not an ElGamal encryption of anything. So it doesn't make sense to try the decryption algorithm. $\endgroup$ – tylo May 10 '17 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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