# Elgamal encryption on general groups

The Elgamal cryptosystem can be defined on the multiplicative group for prime with primitive root as follows:

1. Alice chooses a random as her private key, and publishes as her public key.
2. To send a message to Alice, Bob first generates a random value and sends the pair (where all arithmetic is computed modulo ) to Alice.
3. Alice decrypts the message using .

This can be seen to work because

The security of this system comes from the discrete logarithm problem; in general, given it is difficult to determine the value for which ﻿﻿﻿.

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 with generator and order :

1. Alice chooses a random as her private key, and publishes as her public key. Note that is an integer, but is an element of .
2. To send a message to Alice, Bob first generates a random value and sends the pair (where all arithmetic is computed in ) to Alice.
3. Alice decrypts the message using .

To show the cryptosystem in this more general setting, let’s experiment with a cyclic subgroup of the symmetric group . Any cyclic subgroup will be generated by an element , and 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 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 whose order will be . This is the highest possible order of any element of . 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 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.