In order to discuss further properties of braid groups, it is necessary to introduce a representation that allows easier manipulation.
In the firdt work on braid groups, Emil Artin represented the n-braid group with n-1 generator (plus the identity e), denoted σi for i in [1,2,...,n-1], and the defining relationships:σi σj = σj σi with |i-j| > 1 (1)
σi σj σi = σj σi σj with |i-j| = 1 (2)The Artin generators, as they are now known, also have a very nice geometric interpretation. The generator σi is the braid formed by crossing strings i and (i+1). In this report, the convention will be to pass string i under string (i+1) for σi and to pass string i over string (i+1) for σi^-1.
Example:
w = σ1^-1 (the braid 1 pass over the braid 2).
Now we can expand the relationships (1) and (2) by inversion and some thought to include :σi^-1 σj^-1 = σj^-1 σi^-1 with |i-j| > 1
σi σj^-1 = σj^-1 σi with |i-j| > 1σi^-1 σj^-1 σi^-1 = σj^-1 σi^-1 σj^-1 with |i-j| = 1
σi^-1 σj σi = σj σi σj^-1 with |i-j| = 1
σi^-1 σj^-1 σi = σj σi^-1 σj^-1 with |i-j| = 1It is emmediately obvious that there are any ways to write the same braid using de Artin generators and the relation above.
Furthermore, it is not always obvious if two word written in the Artin generators represent the same braid or different braids (the word problem).The permutation braids lead to the notion of positive braids : a braid is said to be positive if it can be written as a product of the generator σi raised only the positive powers (there is no braid i pass over the braid i+1).
There is one very important positive braid known as fundamental n-braid noted ∆n.
So ∆n can be represented with n(n-1)/2 Artin generators.
Geometrically, the ∆n is obtained by lifting the bottom ends of the strings in a line. Filipping in the other direction gives ∆n-1.∆n braids will be use in the shared private key protocol.
The LBn and RBn groups represent two subgroups of Bn (with n = 2k and k > 1)
Geometrially, the LBn group is obtained by having all braids between n/2 + 1 and n parallel.
Symetrically, the RBn group is obtained by having all braids between 1 and n/2 parallel.Bibliography : Braid Group Cryptography Untangled, Andrew Bolstad
Entity authentication schemes using braid word reduction, Sibert, Dehornoy Girault
I.2. Public key exchange protocol
In this section we will see how to share a private key over an unsecured channel between Alice and Bob.
Alice chooses a braid a from LBn and a braid x from Bn.
Bob chooses a braid b from RBn.Alice compute ya and send to Bob (x, ya) (where ya = a x a-1)
Bob computes yb = b x b-1 and send yb to AliceAt this point Alice and Bob can compute the braid s = a b x a-1 b-1
For Alice s = a yb a-1
For Bob s = b ya b-1
II. Session Architecture
II.1. Shell Session Architecture
In the client side, the Transport and Encryption layers are managed by the class CSecureConnection class.
Symetricaly In the server side, the Transport and Encryption layers are managed by the CSecureSerever class.
The shell layer is owned in the client side by the CSessionShell class and the virtual shell layer in the server side is owned by the CVirtualTerm class used by the CSessionShell class.
II.2. XShell Session Architecture
In both sides client and server, the channels layer is managed by the same CChannelManager class.
The X11 layer in the client side is owned by CXConnection class and the Virtual X11 layer in the server side by the CXServer class.
II.3. FTP Session Architecture
The FTP layer in both sides is managed by the CSessionFTP class.
III. Session Protocol
When the client (knottty program) contact a server (knotttyd program) it receives two braids embbeded in the Transport layer. First is x in Bn group and second axa-1 with a in LBn group from the server.(n = 500 by default).
The client send bxb-1 with b in RBn group.
The encryption layer is available just when the SHA1(abxa-1b-1) digest received by the client are equals in both sides. At this time, the SHA1 digest is used to initialise the AES cypher.The client send the username and password session and the sessionMod = {SHELL, XSHELL, FTP} flag.
The server accept the session by sending AUTHENTICATED flag or close the connection by sending NOAUTHENTICATED flag.III.1. Shell Session Protocol
All shell input/output events are embeded in the Shell Layer.
In the client side, all input events in the standard input are sended to the server and redirect to the virtual Shell.
All output events from the virtual shell are sended to the client in the standard output.
III.2. XShell Session Protocol
In this session mod, the secured connection between client and server is used to embeded a lot of virtual channels.
The channel numbered 0 is reserved to the shell IO events. The others are used to transfert all X11 IO events.
In the server side, a virtual XServer listening on the port 6020 (by default) and catch all XConnection from a local program executed remotely by the client.
Then the server open a free channel and forward all IO events.
In the client side, when a Xchannel is open, the client open a connection to his own XServer and forward all IO events.
III.3. FTP Session Protocol
In this session mod, the client can choose by uploading or downloading a file.
- To Upload a file, the client send the UPLOAD flag, the file pathname where put the file and the file size to the server.
At this time the client send block by block the data of file and compute in real time the SHA1 Digest and send it when the transfert is terminated.
The server verify that the Digest are corresponding.
- To Download a file, the client send the DOWNLOAD flag, the file pathname where get the file and receive the filesize from the server.
At this time the client receive block by block the data of file and compute in real time the SHA1 Digest and receive the digest from the server when the transfert is terminated.
The client verify that the Digests are corresponding.
