What is a transposition cipher method?

- The transposition cipher method is one of the cryptography methods used for securing the communication from eavesdroppers. 

- This method of encryption shifts the positions of the units or letters of the plain text based up on some regular system so that a permutation of the plain text is generated. 

- This permuted plain text is termed as the cipher text. 

- Thus, the cipher text is generated by changing the order of the units. 

- Mathematically the following functions are used:

Ø  Bijective function: For encryption of the character’s position and

Ø  Inverse function: For decrypting the message

Now we shall see about some of the implementations of the transposition cipher:

1. Rail fence cipher: 

- This form of the transposition cipher has been named so because of the way that it follows for encoding.

- Here, the characters of the plain text are written on the successive rails in a downwards manner of some imagined fence.

- Then, we move upwards once getting to the bottom. 

- For reading the message, it is taken in rows.

2. Route cipher: 

- In this form of transposition cipher, a grid of given dimensions is taken on which the characters of the plain text are written out. 

- Then, the message is read based up on the pattern mentioned in the key. 

- For example, the pattern might be inwards spiral in clockwise direction starting from topmost right.

- The route ciphers may use many keys unlike the rail fence cipher. 

- In fact, the number of keys used for enumerating the messages of reasonable length by modern machinery might be too great. 

- Also, it is not necessary that all the keys might be good in equal terms. 

- Excessive chunks of the plain text might be left if bad routes are chosen. 

- Also, the plain text might be simply reversed, thus giving a clue to the crypt analysts about the routes. 

- The union route cipher is a variation of the traditional route cipher. 

- The difference between the two is that this one transposed the whole words unlike route cipher which transposed individual letters.

- But since transposing the whole words could expose them, they were first hidden by a code.

- The entire null words might be added for adding humor to the cipher text.

3. Columnar transposition: 

- In this form of transposition cipher, a fixed length is determined for the rows in which the message is written. 

- But for reading the message a column by column approach is followed where some scrambled order if followed for choosing the columns. 

- A keyword is chosen which is used for defining the permutation of the columns as well as the width of the rows. 

- The spare spaces might be filled with the null characters in case of the regular columnar transposition. 

- On the other hand, in these spaces are left as such in the irregular columnar transposition cipher. 

- The keyword specifies some order following which the message is read column - wise. 

- The column lengths have to be worked out by the recipient for deciphering the message. 

- This is done based up on division of the length of the message specified by the key length.

4. Double transposition: 

- A single columnar transposition is vulnerable to attacks since the possible lengths of the column and anagrams can be guessed. 

- Therefore, a stronger version of it i.e., the double transposition is followed. 

- This is a two-time application of the columnar transposition. 

- For both the transpositions, either the same key might be used or different keys.

- This was the most complicated cipher before the coming of the VIC cipher. 

- It offered reliable operation under difficult conditions. 

What is a substitution cipher method?

There are two classic methods for cryptography namely transposition cipher method and the substitution cipher method. In this article we shall discuss about the latter one i.e., the substitution cipher method. 

- This method of encoding involves replacement of the units or letters of the plain text with some other units or letters. 

- The encoded text is then called as the cipher text. 

- The replacement of the units is made based up on some regular system. 

- These units might be individual letters, pairs or triplets of letters and so on. 

- On the receiver’s side, an inverse substitution is required for deciphering the text. 

- We can make a comparison between the transposition ciphers and the substitution ciphers. 

- In the former ciphers, the plain text units are rearranged unlike in substitution cipher where units are replaced.

- The order of rearrangement in the transposition ciphers is somewhat more complex than what is followed by the substitution ciphers and the units are not changed.

- On the other side, the sequence of the units remains same in the substitution cipher but they are themselves altered. 

There are various types of substitution cipher as mentioned below:

Ø  Simple substitution ciphers: 

- This involves substitution of the single letters and thus has been termed as the simple substitution. 

- The alphabet can be written out in some order so as to represent the substitution.

- This alphabet is referred to as the substitution alphabet. 

- This alphabet might be revered or shifted or scrambled in some complex manner. 

- In such cases, it is termed as the deranged alphabet or the mixed alphabet. 

- The creation of the mixed alphabets involves writing out a keyword while removing the repeating letters and then rewriting the leftovers in the same sequence. 

- For avoiding the transmission errors, the cipher text is written in block form and the spaces and the punctuation are omitted. 

- This also helps in creating disguises for the boundaries between the words.

Ø Homophonic substitution: 

- This method is followed for increasing the difficulty for the frequency analysis attacks. 

- The frequencies of the letters of the plain text are disguised by homophony. 

- Here the letters of the plain text are mapped to many symbols of the cipher text. 

- Normally the plain text symbols with highest frequencies are mapped with more equivalents when compared to their low frequency counterparts. 

- This leads to the flattening of the frequency distribution which in turn raises the difficulty of frequency analysis. 

- For the invention of larger alphabets a number of solutions are employed. 

- The simplest of these solutions is using a numeric substitution alphabet. 

- Another method uses the variations of the existing alphabet i.e., writing it upside down, or in upper case and lower case etc. 

- Nomenclature is also a variant of the homophonic substitution. 

- The other two types of homophonic ciphers namely straddling checker board and book cipher.

Ø Polyalphabetic substitution: 

- It involves the use of the multiple cipher alphabets. 

- For the facilitation of the encryption process, these alphabets are written out in a big table which is referred to as the tableau. 

- The particular poly alphabetic cipher is defined by the method with which the tableau is filled and the alphabet is chosen. 

- Some types of the polyalphabetic ciphers are:

             1. Beaufort cipher

             2. Gronsfeld cipher

             3. Running key cipher

             4. Autokey cipher

Ø  Polygraphic substitution: 

Here the letters of the plain text are substituted in terms of large groups instead of individual letter substitution.

Ø Mechanical substitution ciphers: 

Some examples of this type of substitution ciphers are enigma, rotor cipher machines etc.

Ø The one-time pad: 

This one is a special substitution cipher which has been proven that it is unbreakable mathematically.

What are different methods of broadcasting a packet?

Without broadcasting, our information theory and telecommunications does not mean anything. 

- It is broadcasting that actually makes the transfer of data possible from one point to another. 

- Broadcasting can be defined as the method of transfer of a message to a number of recipients, all at the same time. 

- Broadcasting is often considered to be a sort of high – level operation in some programs while low level operation in some other programs. 

- For example, in message passing interface, broadcasting is a high level operation whereas in broadcasting on Ethernet, it is considered to be a low level operation in networking. 

We have many kinds of routing schemes suiting for various kinds of broadcasting requirements:

1. Anycast
2. Broadcast
3. Multicast
4. Unicast
5. Geocast

- Broadcasting is transmission of a packet to each and every device that is attached to the network. 

- However, the broadcasting is limited to transmission in the broadcast domain in practical applications. 

- Broadcasting can be contrasted with uni cast routing scheme in the sense that in uni cast, the datagrams are transmitted by one host and are received by another single host only. 

- This receiving host is identified with an IP address on the network that is unique to it. 

- All the technologies used in networking are not capable of supporting broadcasting. 

For example, the following do not have this capability:

Ø  X.25 relay

Ø  Frame relay

- The broadcast method cannot be implement with IPv6 i.e., the successor of the IPv4 (internet protocol version 4).

- This is for the avoidance of the disturbance to the nodes. 

- Also, there does not exist anything such as the internet wide broadcast. 

- Therefore, this limits the scope of the broadcasting to the LAN technologies such as token ring and Ethernet since here the impact of the broadcasting performance is small.

Categories of Broadcasting Methods

The broadcasting methods can be classified in to 4 major categories as per the IEEE 802.11 standard:

1. Simple flooding method: 

- In this method the packets are rebroadcast-ed by each of the nodes.

- A message is disseminated to all the neighboring nodes by a source node in the MANET. 

- If the neighboring nodes would have received this message already, then this time the message will be dropped.

- If not, they will re-disseminate the message to their neighbors simultaneously. 

- This process continues until all the nodes have received this message. 

- Only for a MANET this method proves to be reliable that too only if the nodes have low density as well as high mobility. 

- This method has a good potential for harming the network and make it unproductive. 

- This happens so because it will cause congestion in the network thereby exhausting the power of the battery.

2. Area based broadcasting method: 

- Here, we assume a transmission distance.

- Only if sufficient coverage area is detected, the node can rebroadcast otherwise not. 

- This method can be of two types namely location based scheme and the distance based scheme.

3. Probability tested: 

- Rebroadcasting is done by the nodes depending up on the network’s topology and probabilities assigned to them. 

- This somewhat resembles the flooding algorithm with the only exception that a predetermined probability is used for rebroadcasting by the nodes.

- The transmission coverage might be shared by the multiple nodes where the network is too dense.

4. Neighborhood based broadcasting method: 

- Neighborhood method is used for maintaining a state in the neighborhood and rebroadcasting is done with the help of the info obtained from the nodes in this neighboring area. 

- There are two types of this method namely self-pruning approach and ad hoc broadcasting approach.      

What are five key assumptions in dynamic channel allocation?

Putting the available bandwidth in operation of the cellular telephone system to efficient use is an important problem to be considered for providing good service to the largest number of customers possible. The problem has gained a critical status owing to the rapid growth of the cellular telephones users. 

- A communication channel is nothing but a band of frequencies which a number of users can use simultaneously if they are residing far apart from each other. 

- There is a minimum distance at which no interference occurs between the users and it is known as the channel reuse constraint. 

- A cellular telephone system divides the service area in to a number of regions commonly known as the cells. 

- Each of the cells has its own base station for handling the calls concerned with that cell. 

- The bandwidth of the communication channel is partitioned in to many channels permanently. 

- The cells are then allocated these channels in such a way that the channel reuse constraint is not violated by the calls. 

- There are a number of ways for allocating the channels. 

- Few of them are better than the others when it comes to reliably making channels available to all the cells. 

Few examples of channel allocation methods are:

1. Fixed assignment method
2. Dynamic allocation method
3. Reinforcement learning method

About Dynamic Method Allocation

- One type of dynamic method allocation is the BDCL or the borrowing with directional channel locking. 

- Out of all the above mentioned channel allocation methods, the dynamic allocation is considered the best one according to some studies conducted. 

- It is somewhat of the heuristic kind. 

- In dynamic allocation, the channels are allocated in the same way as in the fixed assignment method but it permits borrowing channels from the other cells whenever required. 

- It then arranges those channels in a specific order in each of the cells and this ordering is used in determining the channels for borrowing and reassigning the calls dynamically within the cells.

- There are static allocation techniques also but those don’t seem to work as well as the dynamic allocation techniques. 

In dynamic channel allocation 5 assumptions are always made which we have discussed below:

Station model: 

- There are N independent stations in the model and one frame is generated by each of the stations one at a time. 

- It is blocked until the successful transmission of the previous frame. 

- This means a station cannot queue multiple frames for transmission. 

- For example, a transmission gap of 100 bits is required during the transmission of the consecutive frames.

Single channel assumption:  

- The same medium is shared by all the stations. 

- Through it all the stations can receive and transmit.

Collision assumption: 

- A collision occurs whenever at the same time two frames are transmitted. 

- The two frames that collide have to be re-transmitted.

Transmission model: 

- There are 2 types namely, the continuous time model and the slotted time model. 

- In the former type transmission can be started at any given time. 

- In the latter model, transmission starts with a time slot.

Carrier sense: 

- It can also be classified in to 2 categories namely carrier sense and no carrier sense. 

- Stations can know if a channel is occupied prior to using it. This is called carrier sense.

- In no carrier sense, the stations cannot know whether the channel is occupied or not before transmission.

- Also, it gets difficult for the dynamic allocation method for setting up the favorable usage patterns as the calls start saturating the system. 

Explain the methods for free space management? – Part 2

- Managing the free space is easy only when the space that has to be managed is divided in to units of fixed size. 

- If this is the case, the list of these fixed size units can be kept. 

- The first entry can be returned if it is requested by the client. 

- Managing free space gets difficult when the space to be managed consists of units of variable sizes. 

- This is the case with the memory allocation library at the user level. 

- This is also the case in the physical memory where the segmentation is used for the implementation of the virtual memory. 

- In such cases, external fragmentation is the main problem. 

- This leads to the splitting up of the disk space in to pieces of variable size. 

- The next coming requests might fail because of unavailability of contiguous free space. 

- For example, the request might fail even if 20 bytes are available and the request requires only 15 bytes because this 20 bytes space is non-contiguous. 

- Thus, the main problem is how the free space should be managed while satisfying the variable sized variables. 

How these strategies can manage free space while at the same time keeping the fragmentation in control.

Low level Mechanisms: 

- Most of the allocator use some common mechanisms as these: coalescing and splitting.

- Here, the free list consists of a set of elements describing about all the free spaces available in the heap. 

- Once a pointer to a space is handed over to the program, the determination of the pointers to this space becomes somewhat difficult. 

- These pointers are stored either in the registers or in the variables at some point of execution. 

- However, this is not the case of garbage collected and strongly typed languages as a measure for enabling compaction for combating fragmentation. - Suppose the program makes a request for a single byte of memory.

- In such a case the action performed by the allocator is called splitting. 

- Here a free memory chunk is searched for and split in to two. 

- The first one is returned to the calling request and the second one stays in the list itself. 

- This approach is used in the allocators where small requests are made requesting space that is of size smaller than the chunk. 

- Most of the allocators use a corollary mechanism called the coalescing of the free space. 

- Suppose a small heap is given and an application calls a function to obtain some memory. 

- This function returns the space available in the middle of the heap. 

- All these strategies are based up on simple policies. 

- An ideal allocator is the one that both minimizes fragmentation and is fast. 

- But since it is possible for the stream of free requests and allocation to be arbitrary, any strategy would go wrong if wrong inputs are given. 

- Thus, the best approach cannot be described. 

There are 4 major approaches in this regard:

1. Best fit: 

- Simplest and first searches the list for free chunks of memory that might be bigger than the size requested. 

- The smallest one in the searched ones is returned and this is known as the best fitting chunk or smallest fitting too. 

- One pass is enough for finding the appropriate block to be returned.

2. Worst fit: 

- This one is just the opposite of the best fit. 

- It looks for the largest chunk and returns the amount requested while keeping the remaining memory space.

3. First fit: 

- This one also looks for the first bigger block and out of it allocates the amount requested by the thread.

4. Next fit: 

- Here, one extra pointer is kept at the location where the last search was done. 

Explain the methods for free space management? – Part 1

- For efficient working of the programs and the entire operating system, it is important that the memory of the system should be managed. 

- When the files and programs are allocated memory space, some free space is left in the storage area. 

- It is required that these free spaces must be managed properly. 

- Since there is a limitation to the disk space, this same space has to be used again and again after deleting and creating new files. 

- A free space list is maintained by the operating system for keeping the track of the available free space. 

- All the free disk spaces are listed in free space list. 

- For the creation of a new file this free space list is searched in order to get the amount of space needed and then if the space is available, it is allocated to the file to be created. 

- In the case of deletion, after deleting the file, its space is added to the list of free spaces.

Methods for Free Space Management

There are 4 methods for the management of free space namely:

- Bit vector

- Linked list

- Grouping

- Counting

What is Bit Vector?

- Quite a many times, the free space list about which we mentioned above, is implemented as the bit vector (also known as the bitmap). 

- Here, 1 bit is used for representing each block. 

- If a particular block has been allocated to some file or program, its representative bit is set to 0 and when the block is available, the bit is set to one.

- Consider an example, suppose the following disk blocks are free and rest are allocated: 1, 2, 4, 5, 6, 7, 9, 10, 12, 13, 14, 18, 19, 21, 26, 27, 28. 

- Then for this allocation we have the following free – space bit map:

01101111011011100011010000111…

- This method of free space management is relatively simple and has good efficiency. 

- This method is known for its efficiency to locate the n consecutive free blocks or the first free block available in the storage area. 

- But this method can be inefficient if it is not kept in the main memory of the system. 

- Also, when required occasionally for the recovery needs, this map can also be written to the disk. 

- Keeping such maps in the physical memory is an easy thing if the system has a small memory but this is not always possible in the case of the systems with larger memories.

What is a Linked list?

- In this method, all the free spaces are linked together and the first block in this linked list is assigned a pointer which is stored in the cache memory. 

- Similarly, the pointer to the second block is stored in the first block.

What is Grouping?

- This method is a modified version of the free list approach and it stores the addresses of the all the free blocks in the first block that is free. 

- Here, actually the first n- 1 blocks only are free and the address of another n free blocks is stored in the last block. 

- This lets the system to find the addresses of a number of free blocks which is not possible in the case where the approach being used is the linked list approach.

What is Counting?

- This approach takes advantage of the simultaneous allocation or freeing of the contiguous blocks through clustering or by using contiguous allocation algorithm. 

- Thus, it requires only to keep the address of the first free block and the rest of the blocks follow it. 

Explain the various Disk Allocation methods? – Part 2

In this article we discuss about the non-contiguous disk allocation methods i.e., the linked allocation and the indexed allocation. 

What is a Linked Allocation?

- In linked allocation a single file might be stored all over the disk and these scattered parts are linked to each other just like a linked list. 

- Few bytes in the memory block are used for storing the address of the following linked block.

- This type of allocation has two major advantages mentioned below:

1. Simplicity and
2. Non – requirement of disk compaction

- Since the nature of the allocation method is non-contiguous, it does not lead to any external fragmentation of the disk space.

- And since all the memory blocks have been linked to each other, a memory block available anywhere in the memory can be used for satisfying the requests made by the processes. 

- Declaring the file size for the linked allocation is not required during its creation. 

- There are no issues even if the file continues to grow as long as free blocks are available and since the blocks can always be linked up. 

- As a consequence of all this, the need for disk compaction is eliminated. 

Disadvantages of Linked Allocation

But there are disadvantages of using linked allocation. They are:

Direct access to the disk blocks becomes slow: 

For finding a particular block of the file, the search has to begin at the starting point of the file and the successive pointers have to be followed till the destination block is reached.

Space required by the pointers: 

- Suppose out of 512 words of a memory block, 2 are required for storing the pointers, then we have 39 percent of the total disk being used by the pointers rather than for data. 

- This adds to the space requirement of the file blocks.

Reliability: 

- Because of all the blocks being linked via the pointers, even if one pointer gets damaged or wrong, the successive blocks can become inaccessible. 

- This problem is quite common and thus most of the operating systems avoid this problem by keeping redundant copies of these pointers in a special file. 

- The basic idea here is to keep the list of the pointers in the physical memory of the system. 

- This also allows for the faster access to the disk blocks.

What is Indexed allocation?

- The linked allocation method does not provide support for the direct access and this problem is solved by the indexed allocation method. 

- In this method, all the pointers are placed over an index. 

- Thus, these pointers together form the index block. 

- The address of this address block is then stored in the directory. 

- The pointer at the nth number in the index block points to the nth block of the associated file. 

- The purpose of the index blocks is somewhat similar to that of the page map tables; however both of these are implemented in a different way.
- First level index is used for searching the index of second level and the second one is used for searching the third one and the process may continue till the fourth level. 

- But in most of the cases the indexes of the first two levels are sufficient. 

- With this method, second level index blocks (128 x 128) can be easily addressed and files of size of up to 8mb can be supported. 

- Assuming the same thing, files of size up to 1 gb can be addressed.

Advantages and Disadvantage of Indexed Allocation

- The major advantage of this allocation technique is that it does not give rise to external fragmentation and offers a high level of efficiency in random accessing. 

- Also, using this technique mapping can be done around the disk blocks that are known to be bad. 

-Bit mapping can be used for indexing the free space. 

The biggest disadvantage of this allocation technique is the large number disk accesses required for the retrieval of the address of the destination block in the memory. 

Explain the various Disk Allocation methods? – Part 1

Management of space of the secondary data storage devices is one of the most necessary functions of the file system. This includes tracking which blocks of memory or disk are being allocated to the files and which blocks are free to be allocated. 

There are two main problems faced by the system during allocation of the space to different files. Firstly, the access to the files has to be fast and secondly, the disk space has to be effectively utilized. Both of these combine to form the big problem of disk management. These two problems are more common with the physical memory of the system. 

However, the secondary storage of the system also introduces 2 additional problems which are long disk access time and blocks of larger size to deal with. In spite of all these problems, there are considerations that are common for both the storage such as the non – contiguous and contiguous space allocation. 

Types of Disk Allocation Methods

The following are the 3 widely used allocation techniques:

Ø  Contiguous

Ø  Linked

Ø  Indexed

- The linked and the indexed allocation techniques fall under the category of the non-contiguous space allocation. 

- All the methods have their own pros and cons.

- It is in the term of blocks that all the input and output operations are carried out on the disk. 

- Software is responsible for converting from the logical record to physical storage blocks.

Contiguous Allocation: 

- This allocation technique assigns only the contiguous memory blocks to the files. 

- The size of the memory required is mentioned by the user in advance for the holding the file. 

- The file is then created only if that much amount of memory is available otherwise not. 

- It is the advantage of the contiguous memory allocation technique that all the successive file records are saved adjacent to each other physically. 

- This causes an increase on the disk access time of the files. 

- This can be concluded from the fact that if the files are scattered all about the disk, then it takes a lot more time to access them. 

- Accessing files when they have been organized in a proper order is quite easy.

- To access the files sequentially, the system uses the address of the last memory block and if required moves to the next one. 

- Both direct and sequential accesses are supported by the contiguous memory allocation technique. 

- The problem with this allocation method is that every time a new contiguous space cannot be found for the new files if a majority of the memory is already in use and if the file size is larger than the available memory.  

Non–Contiguous Memory Allocation: 

- It happens a lot of time that the files grow or shrink in size with usage and time. 

- Therefore, it becomes difficult to determine the exact space required for the files since the users do not have any advance knowledge about the growing size of their files. 

- This is why the systems using the contiguous memory allocation techniques are being replaced by the ones with the non-contiguous storage allocation which is more practical and dynamic in nature. 

- The linked allocation technique mentioned above in the article, is a disk – based implementation of the linked list. 

- Each file is considered to be a list of the disk blocks linked to each other. 

- It does not matter whether the blocks are scattered about the disk. 

- In each block, few bytes are reserved for storing the address of the next block in chain.

- The pointer to the first and the last block of the file is stored in the directory.