Tag Archive for 'iit'

Lull After The Storm

Published on April 12, 2009 in Anu. 0 Comments

Yabba Dabba doo !!! My Grand Viva is finally over. And I cannot express my happiness over it in any definite words. This is the one time professors get to mock at their students, though I must add a few are very helpful, and try their best to point the students to the right answers. Although I did not do as well as I was hoping to, but no regrets over there. As it is, I have never cared for my CG. Marks are for the lesser mortals :D .

So now with the grand viva out of the way, it is time to resume working on my BTP. But not without a well deserved break for the weekend. Yeah, a well deserved one, really. Only the BTP presentation is between me and my graduation :D .

The last 40 days at Kharagpur ! I am glad to be leaving this place. Not because I got bored of it, but because I want to start a new chapter of my life – a different story, a different person, a different place. I am eager to move into Bangalore, and start afresh. There was a lot I could have done at Kharagpur itself, but my introversion prevented that. It shall not any more. I am determined to present a new picture of myself, a changed self. I am deviating from the topic.

Well, to sum up, now with the grand viva over, things have really calmed down. There is not much to do, except BTP and chilling out with friends. Its time to make the last few days at Kharagpur memorable. There shall come a day when I’ll feel nostalgic, and wish these days – the best of my life – never went away, but it is not that day yet. Today is the time for party.

Tags: , , , .

A Day That Should Not Have Been

Published on March 23, 2009 in Miscel. 0 Comments

Today was indeed one of the worst days of my 4 years stay at the Indian Institute of Technology, Kharagpur. A Sunday marred by the shocking and tragic loss of a fellow KGPian, all because of the negligent behaviour of the in-campus hospital doctors and authorities.

Students once again showed their unity by staging a protest in front of the Director’s house as soon as the news broke out. It spread like a viral, and soon enough a mob gathered at the Directors house. The destruction of property was uncalled for, and irresponsible on part of the students. Yet, it was the Directors fault not improving the already degrading standards of the B.C. Roy Hospital. The unfortunate death was only the tipping point.

This is not a first-off incidence. The hospital has been in news earlier too. The Campus Newsletter, The Scholars’ Avenue, published an article which exposed the malpractices there. The report team was suspended for almost 6 months for this. The negligence continues to this day. The whole campus could testify against the hospital.

In news earlier were reports of A.P.J. Abdul Kalam inaugurating a B.C. Roy Multi speciality Research Facility (news at KGPian), but I do not know what happened to that project.

Needless to say, the student community is enraged at the incidence. The Director had to resign immediately. An Open House meeting with the students was scheduled for later in the night. Appropriate action is what we expect from the IIT authorities. Our demand for better basic amenities is not unjustified.

You can read more in this article in The Scholar’s Avenue -

Student Dies En Route From B C Roy Hospital To Kolkata

Tags: , , , .

Output Feedback Mode

Published on March 18, 2009 in Miscel. 0 Comments

[ Sometime the LATEX does not render properly. Just refresh the page and it should do. ]

OFB Encryption

OFB Encryption

OFB Decryption

OFB Decryption

Output feedback mode is similar to CFB mode except that the quantity XORed with each plain text block is generated  independently of both the plain text and cipher text. An initialization vector s_0 is used as a seed for a sequence of data blocks s_i, and each data block s_i is derived from the encryption of the previous data block s_{i-1}. The encryption of a plain text block is derived by taking the XOR of the plain text block with the relevant data block.

It is essential for security that the initial value is chosen randomly and independently from the previous ones. This prevents almost with certainty that the same initial value s_0 is used for more than one encryption.

A transmission bit error in block c_i only affects the decryption of that block. The block recovered from c_i has bit errors precisely where c_i did. However, the output feedback mode will not recover from a lost cipher text block – all following cipher text blocks will be decrypted incorrectly.

The speed of encryption is identical to that of the block cipher. Even though the process cannot easily be parallelized, time can be saved by generating the key stream before the data is available for encryption.

The output feedback mode is implemented by the following algorithm

Algorithm:

bitStream ofbEncrypt(bitStream m, s_0)

divide m into m_0m_1...m_l

for i \gets 1 to l do

c_i \gets m_i \oplus {msb_r}{({E_K}({s_i}))}

x_i \gets {E_k}({s_i})

return c_1c_2...c_l

[ This is a part of a series of post on Modes Of Encryption. I had to scribe a lecture as a requirement of a course on the Foundations Of Cryptology at the Indian Institute Of Technology. The scribe has been broken into smaller chunks so that it is easily readable. ]

Tags: , , , , .

Cipher Block Chaining

Published on March 18, 2009 in Miscel. 0 Comments

[ Sometimes the LATEX does not render properly. Just refresh the page and it should do. ]

In the cipher block chaining mode, each block of plain text is XORed with the previous cipher text block before being  encrypted. This was, each cipher text block is dependent on all the plain text blocks that have been processed up to  that point. Also to make each message unique, an initialization vector must be used in the first block.

CBC Encryption

CBC Encryption

CBC Decryption

CBC Decryption

CBC mode is as secure as the underlying block cipher against standard attacks. In addition any patterns in the plain text are concealed by the XORing of the previous cipher text blocks with the plain text block. Note also that the plain text cannot be directly manipulated except by removal of blocks from the beginning or the end of the cipher text. The initialization vector should be different for any two messages encrypted with the same key and is preferably randomly chosen. It does not have to be encrypted and it can be transmitted with (or considered as the first part of)  the cipher text.

If the first block has index 1, the mathematical formula for CBC encryption is

C_i = E_K(P_i \oplus C_{i-1}), C_0 = IV
while the mathematical formula for CBC decryption is
P_i = D_K(C_i) \oplus C_{i-1}, C_0 = IV

Choosing the initial value c_0 at random prevents almost with certainty that the  same initial value c_0 is used for more than one encryption. This is important for security. Suppose for a moment that the same c_0 is used for two messages m and  m^` . Then, an eavesdropper can immediately detect whether the first l blocks of m and m^` coincide, because in this case the first l ciphertext blocks are the same.

The speed of encryption is identical to that of the block cipher, but the encryption process cannot be easily parallelized, although the decryption process can be.

In this mode, we have r = n. Encryption in the cipher-block chaining mode is implemented by the following algorithm

Algorithm:

bitStream cbcEncrypt(bitStream m)

select c_0 \in \{0, 1\}^n at random

divide m into m_1m_2...m_l

for i \gets 1 to l do

c_i \gets E_k(m_i \oplus c_{i-1})

return c_0c_1c_2..c_l

Decryption in cipher-block chaining mode is implemented by the following algorithm

Algorithm:

bitStream cbcDecrypt(bitStream c)

divide c into c_0c_1c_2...c_l

for i \gets 1 to l do

m_i \gets {E_k}^{-1}(c_i) \oplus c_{i-1}

return m_1m_2...m_l

A transmission bit error in block c_i affects the decryption of the blocks c_i and c_{i+1}. The block recovered from c_i will appear random (here we assume that even a small change in the input of a block cipher will produce a random looking output), while the plaintext recovered from c_{i+1} has bit errors precisely where c_i did. The block c_{i+2} is decrypted correctly. The cipher block chaining mode is self synchronizing, even if one or more entire blocks are lost. A lost ciphertext block results in the loss of the corresponding plaintext block and errors in the next plaintext block.

In both the electronic codebook mode and cipher block chaining mode, {E_k}^{-1} is applied for decryption. Hence, both modes are also applicable with public key encryption methods, where the computation of {E_k}^{-1} requires the recipient’s secret, while E_k can be easily computed by everyone.

[ This is a part of a series of post on Modes Of Encryption. I had to scribe a lecture as a requirement of a course on the Foundations Of Cryptology at the Indian Institute Of Technology. The scribe has been broken into smaller chunks so that it is easily readable. ]

Tags: , , , , .

Electronic Code Book

Published on March 18, 2009 in Miscel. 1 Comment

[ Sometimes the LATEX does not render properly. Just refresh the page and it should do. ]

The simplest of all the encryption modes is the electronic codebook mode. The message is divided into blocks and each block is encrypted separately.

ECB Encryption

ECB Encryption

ECB Decryption

ECB Decryption

ECB is as secure as the underlying block cipher. However, plaintext patterns are not concealed. Each identical block of plaintext gives an identical block of ciphertext. The plaintext can be easily manipulated by removing, repeating or interchanging blocks. As the encryption is deterministic, it is not CPA secure.

The speed of each encryption is identical to that of the block cipher. ECB allows easy parallelization to yield higher performance. Unfortunately, no processing is possible before a block is seen.

In this mode we have r = n. The ECB is implemented by the following algorithm

Algorithm:

bitStream ecbEncrypt(bitStream m)

divide m into m_1m_2...m_l

for i \gets 1 to l do

c_i = E_k(m_i)

return c_1c_2...c_l

For decryption the same algorithm can be used with the decryption function {E_k}^{-1} instead of E_k.

If we encrypt many blocks, partial information about the plain text is revealed. Therefor other modes are preferable.

[ This is a part of a series of post on Modes Of Encryption. I had to scribe a lecture as a requirement of a course on the Foundations Of Cryptology at the Indian Institute Of Technology. The scribe has been broken into smaller chunks so that it is easily readable. ]

Tags: , , , , .

Modes Of Encryption

Published on March 18, 2009 in Miscel. 0 Comments

[ Sometimes the LATEX does not render properly. Just refresh the page and it should do. ]

Often the length of message exceeds the block length. So, the block ciphers need some extension. Consider a block cipher of length n. We fix a key k, and denote the encryption function with this key as

E_k\colon \{0, 1\}^n \to \{0, 1\}^n

To encrypt a message m that is longer than n, the message is decomposed into blocks of fixed size r, m = m_1m_2...m_l. The individual blocks are encrypted iteratively.

The message block size r need not equal n. In few modes of encryption, r is smaller than n.

Also if the length of message m is not an integral multiple of r, then we have to complete the last block. The last block of the message can be padded out with some bits and encrypted. After decryption, the receiver must remove the padding. Therefore he must know how many bits were padded. This can be achieved, for exmple, by storing the number of padded bits in the last byte of the last block.

[ This is a part of a series of post on Modes Of Encryption. I had to scribe a lecture as a requirement of a course on the Foundations Of Cryptology at the Indian Institute Of Technology. The scribe has been broken into smaller chunks so that it is easily readable. ]

Tags: , , , , .

Bitwise 2009 Engima Answers

Published on February 22, 2009 in Miscel. 10 Comments
BSOD

BSOD

I know its too late for this, but then my blog received a visitor who got here searching for answers. Also, the forum has become dead now, and its a pain to go back searching for all the answers. So here it is, all the answers are given below. Only the answers are here. You may play the enigma at Enigma-Bitwise09. A few of the answers have comments in []. They are not part of the answer.

  1. Enigma [A change from the traditional BITWISE answer]
  2. Server
  3. Java
  4. Super Computer
  5. Handshake [We spent lots of classes last year in networks course studying HANDSHAKE]
  6. Multimedia
  7. Deadlock
  8. Oracle
  9. BSOD [The easiest of them all, pretty obvious. Any windows user will know about the BSOD :D ]
  10. Gateway
  11. Segmentation Fault [Haven't ever managed to complete a program without getting stuck with this error :( . I have made a signal handler to catch seg fault ;) ]
  12. Garbage Collector [Loved this one. One of my favourites.]
  13. Terminal
  14. Facebook
  15. Memory Leak
  16. Multitasking
  17. Data Mining
  18. Overclock
  19. Infinite Loop
  20. Nibble
  21. Paging [The question with the weirdest logic.]
  22. Brainfuck [Try this language. Even the HELLO WORLD is a difficult program to code !!]
  23. Password
  24. LISP [One of Mallu's evil questions.]
  25. Sun [Another of Mallu's almost-impossible-to-guess question]
  26. Cipher
  27. HP [Hail the lord of Mortals - Mallu da. None in the department could figure this one out :P :P ]
  28. Rete Algorithm
  29. Opera

Hehe … I am not giving away the last answer. Look back at the 29 answers and try to think this one by yourself. Lets see if you can reason out like us :P   .

PS: Mallu is Vinu Rajshekhar

PS: Though a lot of people poured in the questions, the most notable were those of Tharki (Arpit Kumar). Each was a bigger PJ than the other !!

Reblog this post [with Zemanta]
Tags: , , , , .

And Then The Coding Begins

Published on February 20, 2009 in Anu. 0 Comments

As I mentioned yesterday, I have finally managed to complete (read: almost complete) the analytical component of my BTP. Now I need to implement the algorithm and get the results.

It has been a great night out. I have already written ~450 lines of code in C. I have tried the modular approach, breaking things into functions. This way, I test each function individually and am sure that they will work when used together.

Also I have added a new feature in my code this time. Learning from my troubles the last time I coded such a complex algorithm, I realised that a log file proves to be handy. It clearly defines the flow of control, the manipulations and the decisions taken within a loop. Everytime I enter a function, I make a note of it in the log file. Whenever I leave the function, it is noted into the log. All that occurs within the function is properly indented. At the present though I have used a rather brute force method for indenting the log file. I print spaces in the log file using the for loop. I need to find a better way.

Below is the log file that I generated running the incomplete algorithm.

  Number of Processors : 1
  Number of Tasks : 4
  Frame Size : 10
  Number of Groups : 1

  Task   1: e =  18 p =  30 wt = 0.60
  Task   2: e =  18 p =  90 wt = 0.20
  Task   3: e =  18 p = 150 wt = 0.12
  Task   4: e =  18 p = 225 wt = 0.08

  Proc   1: cap =  10

      <<>>naf: 0

      <<>>shr: 6

    Task 1, Frame 0, Share 6

      Frame 0 inserted after -1
      Task 1 inserted into bucket 5 first

      <<>>naf: 0

      <<>>shr: 2

    Task 2, Frame 0, Share 2

      Task 2 inserted into bucket 1 first

      <<>>naf: 0

      <<>>shr: 1

    Task 3, Frame 0, Share 1

      Task 3 inserted into bucket 0 first

      <<>>naf: 1

      <<>>shr: 1

    Task 4, Frame 1, Share 1

      Frame 1 inserted after 0
      Task 4 inserted into bucket 0 first

    <<>>leastFrame: 1
Tags: , , , , .

Getting Started With My BTP

Published on February 19, 2009 in Anu. 0 Comments

It’s high time now that I start coding for my BTP so as to arrive at some result by the next month. However, I am yet to resolve all the analytical issues related to my problem. The biggest of my worries being a mathematical bound over the under-allocation that a task could suffer when scheduled using the algorithm I am working on.

Let me start from the beginning. I have taken up as my BTech project the topic of scheduling tasks on multi-processor system. PPC alloted me to Mr. Arnab Sarkar (Arnab da I call him). I have been working with him for the past few months to arrive at an optimised solution to our problem.

The problem that we are tackling is that there exists an algorithm called ER-Fair which schedules tasks proportionately on a multi-processor system. Arnab da in his research improved the time complexity by using frames. He divided the time into frames, of equal sizes and then alloted the tasks to these frames. Inside the frame, ER-Fair scheduling can be used to arrive at fair scheduling. The drawback was that ER-Fair requires a higher time complexity than a simple Round Robin algorithm. So the motivation was to replace the ER-Fair algorithm by an O(1) round robin algorithm without compromising on the fairness.

VTRR is one such algorithm. But then I was not able to derive any mathematical bounds for the maximum under-allocation that a task can suffer when scheduled using the VTRR algorithm, and by definition VTRR does not guarentee against under-allocation. So we could be losing fairness if we used just the VTRR algorithm. One pathological case where this happens is when there are 4 tasks to be scheduled and they have weights of 9, 1, 1, 1. The VTRR algo then schedules Task A, B, C, D and only then returns back to again schedule A. But by this time A has been under-allocated. Now consider a system where there are many more tasks than just 4, this boundary case implies a huge deviation from the required fairness.

We found a way around this by using groups within frames. Tasks are divided into groups on the basis of their shares. This ensures that all tasks of similar weights are put into the same group, therby avoiding the occurance of any case as mentioned above. The weight of the group would be the combined weight of all the tasks. To the external scheduler, a group would appear as a single task which needs to be scheduled. Since we shall be creating fixed number of groups, using ER-Fair algorithm for scheduling the groups should take only O(1) time.

The tasks within a single group can be scheduled using VTRR algorithm. But I met with the smae problem once again, that of deriving the bounds for the under-allocation. This very evening though, Arnab da found another interesting algorithm. It is a slight modification of the VTRR algorithm and performs better in the same complexity range. This one works with ensuring that the error (defined as the amount of work received less what the task should have been serviced) never exceeds 1. If it does, then either the first or the next task is selected on the basis of which task has lesser error. Being a simple round robin algorithm, it is O(1) and easier to implement than the VTRR. Also I have managed to come up with a few equations to bound the under-allocation. I am not getting my hopes high yet, not until Arnab da checks it and finds it right.

Also we met PPC today. It was mostly Arnab da and him discussing the problem and the solution, I was just a third person observer. PPC said the idea is good and told me to come up with some analytical result as to what would be the optimal way of putting the tasks into groups. Also, he said if we code the algorithm and if the observation of under-allocations vs. number of groups comes out as a rectangular hyperbola, dipping quickly as the number of groups increases, then it could be a successful experiment. The reason is that if the number of groups is 1, then the system is equivalent to VTRR which does not have  bounded under-allocation, and if the number of groups equals the number of tasks, then the system is effectively being scheduled using just the ER-Fair algorithm which is not O(1). So if we can show that the idea of a few groups can schedule the system in O(1), it’ll be successful work.

Tags: , , , , .

A Fun Bitwise

Published on February 9, 2009 in Anu. 0 Comments

So here it is, now that the Bitwise 2k9 is over, everyone feels so relieved and obviously happy. Everything went smoothly and happily. There was no hitch (well, compared to what are generally expected, we had the minimal of all the problems). And all the while when the contestants were busy cracking the questions, we were having fun in our own way.

Not just in India, but anywhere in the world, you’ll never find an event start on time. So why should we be an exception [:P].  Now since Bitwise is an international competition in which participants from all over the world take part, I put up a timer on the right hand sidebar, displaying the server time. This time would be used by the contestants to synchonise their watches. The event was to be begin at 1220 hours IST. And I was prepared, in the event of us getting delayed, to slightly change the server time – not that we finally needed it. The event started right on time. Actually we were all ready for the launch ten minutes earlier. The countdown began and just when the timer showed 1220 on our site, we released the problems.

The response was enormous !! The server was heavily overloaded. Many complaints started pouring in about the site not loading up. But in a matter of few anxious minutes, these complaints died down, and we took a sigh of relief.

Just when we were all getting into our new roles of maintaining the system and responding to all the queries, the first shock hit us ! No, it was no fault, no breakdown of system and certainly not of the server going offline. A team had actually solved a question, easiest though, and scored full. We couldn’t believe it. Naresh (Shenoy K) actually pulled out the file from the system, compiled it manually and checked with the test cases himself to make sure that the evaluator had not made an error. The problems team were bewildered. They wondered if their problems were not as good enough as they thought earlier. There were a few nervous smiles, trying to defend their claim that the questions are indeed though.

We convinced ourselves that this was just  one-off instance and that not all the teams will find the same question this easy to solve, that perhaps it was more by luck that talent that this team had cracked the first question in ten minutes. This we did only to be proved wrong in another quater of an hour. Submissions for the same question started pouring in and there were quite a good number of teams with full scores. We just kept our fingers crossed.

But then that did remain a one-off question. Apparently the second question had been changed just hours before the question. The original question was too tough to be solved in such short  time, and the problems team decided to put up a modified version which was easier, evident by the fact that the score was halved. The second question, the one to be solved first, carried just 75 marks, while the other questions were rated for 200s and 300s.

India vs. Sri Lanka cricket match was being aired the same time. We got busy watching the match while at the same time answering the doubts of the contestants. Ghoda (Birendar S Tiwana) had this brainwave the previous day of letting the teams add us on their gtalk id and contacting us over the IM in case of any doubts. The idea was a hit considering the number of queries I had to answer. I was asked all sort of things – from being pestered for hints, to suggestions that the questions were too tough to be solved by a final year student of engineering, to being told of that the sample cases we provided were wrong !

There were a few highlights of chatting that I would like to mention. A girl came online – nita..sharma.niit (obviously name changed to protect identity). She mentioned that the Enigma quiz was a great idea, and that she was enjoying it. Immediately Tharki (Arpit Kumar) got working. He told her that the whole of enigma was his brainchild (he mentioned it was of Arpit’s as a third person), and proceeded to give her his email id so that she could contact him to thank him personally. And she did !!! Her next message was – thanks for the id. I have added him on  GTalk. Tharki left the station and returned to his computer to attend to more pressing business [:P]. Apparently they have become good friends.

We had lots of fun answering the queries and chatting away. We dealt sternly with a few guys, having to tell them that we provide no hints and loved talking to a few who challenged our problem makers – a few of them really made Sudip (Roy) and co. ponder over the boundary conditions. Only a minor changes were made to one or two questions.

Aritro (Aritra Sen) was the server admin making all the changes to the webpages. Tension clearly showed when he occasionally lashed out at anybody suggesting he was slow in updating the  webpage (which he was not). Mallu Da (Vinu Rajshekhar) was the busy man firing away sql queries when we had to sometimes manually check if the file submitted contained malicious code. Naresh and Mallu were our goto guys when in doubt. Akshit (Sharma) and KT (Kaustabh Tripathi) ensured that none of us were hungry. They arranged for snacks and lunch, half of which they ate themselves. Shashi (Narayan) took charge of the feedback. Ghoda was the responsible person, always reminding us that we should not toy/abuse/insult/behave irresponsibly with people while chatting, that we should seriously answer their queries and never mislead them – this suggestion was too hard to follow. Karishma (Kapadia), Nisha (Kiran) and Chuski (Varun Sharma) were there as well, taking rounds in helping everybody out. The problem team members Anvesh (Komuravelli), Ashish (V), Bhuyan (Pramit K), Sumeet (Singal), Ruteesh (K) were obviously present to help us answer the queries.

In all, it was a great day. Everyone was tired by the end. I actually dozed off six hours after the start of the competition. Arindam (Sharma) had come in the evening afer his GATE exam. It was one of the best days of my stay in Kharagpur. Not having slept for almost 40 hours, I bid them goodbye and left for my room.

Tags: , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , .
Theme Tweaker by Unreal