Elgamal encryption on general groups

The Elgamal cryptosystem can be defined on the multiplicative group mathbb{Z}_p^+ for p prime with primitive root a as follows:

  1. Alice chooses a random A<p as her private key, and publishes B=a^Apmod{p} as her public key.
  2. To send a message m<p to Alice, Bob first generates a random value k<p and sends the pair (c_1,c_2)=(a^k,B^km) (where all arithmetic is computed modulo p) to Alice.
  3. Alice decrypts the message using m=c_2c_1^{-A}.

This can be seen to work because

c_2c_1^{-A}=c_2a^{-Ak}=c_2B^{-k}=B^kmB^{-k}=m.

The security of this system comes from the discrete logarithm problem; in general, given a,p,B it is difficult to determine the value A for which B=a^Apmod{p}.

Here’s an example with very small values:

sage: p=next_prime(5432);p
  5437
sage: a=mod(primitive_root(p),p)
sage: a
  5
sage: A=randint(1,p);A
  5186
sage: B=a^A;B
  1254
sage: m=1000
sage: k=randint(1,p)
sage: c1=a^k
sage: c2=B^k*m
sage: (c1,c2)
  (2370, 4491)
sage: c2/c1^A
  1000

This system, though, is in fact much more general, and can be described in terms of any cyclic group G with generator g and order n:

  1. Alice chooses a random A<n as her private key, and publishes B=g^Apmod{p} as her public key. Note that A is an integer, but B is an element of G.
  2. To send a message min G to Alice, Bob first generates a random value k<n and sends the pair (c_1,c_2)=(g^k,B^km) (where all arithmetic is computed in G) to Alice.
  3. Alice decrypts the message using m=c_2c_1^{-A}.

To show the cryptosystem in this more general setting, let’s experiment with a cyclic subgroup of the symmetric group S_n. Any cyclic subgroup will be generated by an element g in S_n, and g can be written as disjoint cycles. The order of the element (and hence of the cyclic subgroup) will thus be the lowest common multiple of the lengths of the cycles.

In order to obtain an element with reasonably high order, the cycle lengths must be distinct primes or prime powers. Rather than choosing n first and finding an element with high order, we shall start by choosing a list of distinct primes and create a list of cycles with those lengths. For example:

sage: pp=primes_first_n(4);pp
  [2, 3, 5, 7]
sage: ps=[sum(pp[:i])+1 for i in range(len(pp))];ps
  [1, 3, 6, 11]
sage: L=[tuple(range(x,x+y)) for x,y in zip(ps,pp)];L
  [(1, 2), (3, 4, 5), (6, 7, 8, 9, 10), (11, 12, 13, 14, 15, 16, 17)]

We can now use L to generate a subgroup of S_{17} whose order will be 2times 3times 5times 7=210. This is the highest possible order of any element of S_{17}. To continue, Alice now creates private and public keys:

sage: n=17
sage: G=SymmetricGroup(n)
sage: g=G(L)
sage: N=prod(pp);N
  210
sage: A=randint(1,N);A
  44
sage: B=g^A;B
  (3,5,4)(6,10,9,8,7)(11,13,15,17,12,14,16)

Suppose Bob wishes to send m=g^{196} to Alice:

sage: m=g^196;m
  (3,4,5)(6,7,8,9,10)
sage: k=randint(1,N);k
  84
sage: c1=g^k
sage: c2=B^k*m
sage: c1;c2
  (6,10,9,8,7)
  (3,4,5)(6,8,10,7,9)

Now decryption is straightforward:

sage: m1=c2/c1^A;m1
  (3,4,5)(6,7,8,9,10)
sage: m1==m
  True

Although these examples use very small parameters, they can easily be done with parameters of arbitrary size.

Leave a Reply

Your email address will not be published. Required fields are marked *