The Magma implementation uses special optimisation techniques, if a
homomorphism with domain in the category GrpBrd has the additional
properties listed above. Compared to the general case, this results in
faster evaluation of such homomorphisms, in particular in the case e = 1.
- (1)
- The symmetric group on n letters is an epimorphic image of the braid
group on n strings, where for 0 < i < n the image of the Artin generator ai
is given by the transposition (i, i + 1).
We construct this homomorphism for the case n = 10.
> Bn := BraidGroup(10);
> Sn := Sym(10);
> f := hom< Bn->Sn | [ Sn!(i,i+1) : i in [1..Ngens(Bn)] ] >;
Of course, the image of
f is the full symmetric group.
> Image(f) eq Sn;
true
Now we compute the image of a pseudo-random element of
Bn under
f.
> f(Random(Bn));
(1, 5, 8)(2, 4, 9, 7, 6, 3)
- (2)
- (Key exchange as proposed in [KLC+00])
Consider a collection of l + r strings t
1, ..., t
l + r and the braid group
B acting on t
1, ..., t
l + r with Artin generators s
1, ..., s
l + r - 1 .
The subgroups of B fixing the
strings t
l + 1, ..., t
l + r and t
1, ..., t
l may be
identified with braid groups L on l strings and R on r strings,
respectively, with the Artin generators of L and R corresponding to s
1, ..., s
l - 1 and s
l + 1, ..., s
l + r - 1,
respectively.
We set up these groups for l = 6 and r = 7 using the BKL presentations.
> l := 6;
> r := 7;
> B := BraidGroup(l+r : Presentation := "BKL");
> L := BraidGroup(l : Presentation := "BKL");
> R := BraidGroup(r : Presentation := "BKL");
We now construct the embeddings f : L -> B and
g : R -> B.
> f := hom< L-> B | [ L.i -> B.i : i in [1..Ngens(L)] ] >;
> g := hom< R-> B | [ R.i -> B.(l+i) : i in [1..Ngens(R)] ] >;
To complete the preparatory steps, we choose a random element of B which
is not too short.
> x := Random(B, 15, 25);
The data constructed so far is assumed to be publicly available. Each
time two users A and B require a shared key, the following steps are performed.
- (a)
- A chooses a random secret element a∈L and sends the
normal form of y1 := xa to B.
- (b)
- B chooses a random secret element b∈R and sends the
normal form of y2 := xb to A.
- (c)
- A receives y2 and computes the normal form of y2a.
- (d)
- B receives y1 and computes the normal form of y1b.
Note the following.
- Transmitting y1 and y2 in normal form disguises
their structure as products a - 1xa and b - 1xb, provided the words
used are long enough and prevents simply reading off the conjugating elements
a and b.
- Since the subgroups L and R of B commute, we have
ab = ba, which implies y2a = xba = xab = y1b. Thus, the
normal forms computed by A and B in steps (c) and (d), respectively, must be
identical and can be used to extract a secret shared key.
We illustrate this, using the groups set up above. For step (a):
> a := Random(L, 15, 25);
> y1 := NormalForm(x^f(a));
Now for step (b):
> b := Random(R, 15, 25);
> y2 := NormalForm(x^g(b));
We now verify that A and B arrive at the same information in steps (c)
and (d).
> K_A := NormalForm(y2^f(a));
> K_B := NormalForm(y1^g(b));
> AreIdentical(K_A, K_B);
true
We see that the information computed by A and B in steps (c) and (d) is indeed
identical and hence can be used (in suitable form) as a common secret.
Note, however, that the number of strings and the lengths of the elements
used in the example above are much smaller than the values suggested for
real cryptographic purposes.
- (3)
- (Attack on key exchange)
We now show an attack on the key exchange outlined above using conjugacy
search based on ultra summit sets.
An eavesdropper can try to compute an element c conjugating x to y1.
While this is not guaranteed to reproduce the braid a, the chances for
a successful key recovery are quite good.
We decide to change to the Artin presentation of B and use the function
MyIsConjugate from Example H82E8 for
computing a conjugating element c as above.
> SetPresentation(~B, "Artin");
> time _, c := MyIsConjugate(x, y1);
42 elements computed
Time: 0.020
Finding a conjugating element is no problem at all.
Using the conjugating element, we can try to recover the shared secret.
In this example we are lucky.
> NormalForm(y2^c) eq K_A;
true
In the conjugacy search above, a conjugating element was found after computing
42 ultra summit elements. The ultra summit set itself is larger, but can
still be computed very easily.
> time Ux := UltraSummitSet(x);
Time: 3.150
> #Ux;
1584
The super summit set is, even in this small example, too large to be computed;
conjugacy search based on super summit sets would quite likely fail.
> time Sx := SuperSummitSet(x);
Current total memory usage: 4055.1MB
System error: Out of memory.
Finally, we show that the attack using conjugacy search based on
ultra summit sets is also applicable to larger examples.
We try to recover a key, which is generated using elements with canonical
lengths between 500 and 1000 in a braid group on 100 strings.
> l := 50;
> r := 50;
> B := BraidGroup(l+r);
> L := BraidGroup(l);
> R := BraidGroup(r);
>
> f := hom< L-> B | [ L.i -> B.i : i in [1..Ngens(L)] ] >;
> g := hom< R-> B | [ R.i -> B.(l+i) : i in [1..Ngens(R)] ] >;
>
> x := Random(B, 0, 1, 500, 1000);
>
> a := Random(L, 0, 1, 500, 1000);
> y1 := NormalForm(x^f(a));
>
> b := Random(R, 0, 1, 500, 1000);
> y2 := NormalForm(x^g(b));
>
> K_A := NormalForm(y2^f(a));
> K_B := NormalForm(y1^g(b));
> AreIdentical(K_A, K_B);
true
We again try to recover the key by computing an element conjugating x to
y1. This time, we use the built-in Magma function for efficiency
reasons.
> time _, c := IsConjugate(x, y1);
Time: 18.350
> K_A eq NormalForm(y2^c);
false
Bad luck. -- We managed to compute a conjugating element, but this failed to
recover the key.
We try with an element conjugating x to y2.
> time _, c := IsConjugate(x, y2);
Time: 3.800
> K_B eq NormalForm(y1^c);
true
Success! -- Good that we didn't use this key to encrypt our credit card
number!
This section describes the functions available for creating a number of
well known representations of braid groups.
Given a braid group B on n strings, return the natural epimorphism
from B onto the symmetric group on n points, induced by the action
of B on the strings by which B is defined.
Given a braid group B on n strings, return the Burau representation
of B as homomorphism from B to the matrix algebra of degree n over
the rational function field over the integers.
Given a braid group B on n strings and a prime p, return the
p-modular Burau representation of B as homomorphism from B to
the matrix algebra of degree n over the rational function field over
the field with p elements.
We construct the Burau representation of the braid group on 4 strings.
> B := BraidGroup(4);
> f := BurauRepresentation(B);
Its codomain is a matrix algebra of degree 4 over the rational function
field over the integers.
> A := Codomain(f);
> A;
GL(4, FunctionField(IntegerRing()))
> F := BaseRing(A);
> F;
Univariate rational function field over Integer Ring
Variables: $.1
To obtain nicer printing, we assign the name t to the generator of the
function field F.
> AssignNames(~F, ["t"]);
Now we can check easily whether we remembered the definition of the Burau
representation correctly.
> f(B.1);
[-t + 1 t 0 0]
[ 1 0 0 0]
[ 0 0 1 0]
[ 0 0 0 1]
> f(B.2);
[ 1 0 0 0]
[ 0 -t + 1 t 0]
[ 0 1 0 0]
[ 0 0 0 1]
> f(B.3);
[ 1 0 0 0]
[ 0 1 0 0]
[ 0 0 -t + 1 t]
[ 0 0 1 0]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]