Tag Archive for 'cryptography'

Stanford University Online Education Courses

Published on November 25, 2011 in Miscel. 0 Comments

This morning Madhu sent out a mail regarding few courses that Stanford University are offering. The courses are free of cost and start late in January. The duration is around 8 weeks. They’re perfect for self motivated people who are just interested in learning something new. The medium of discourse is obviously video lectures. One is supposed to go through them in their leisure time. Of course, one is expected to put in incremental effort every week instead of just revising the whole thing in the last week. There might be additional quizzes and assignments to be done. Also a mini-project is also a possibility. The emphasis is on learning.

Of late – after leaving Kharagpur to be more precise – I’ve had this appetite to learn something new. So the moment I saw this opportunity, I enrolled myself in 5 courses. The first one being Machine Learning by Prof. Andrew Ng. Here’s the link to the course – http://jan2012.ml-class.org/.I’ve been through his video lectures posted in Youtube, the first of which can be found at http://youtu.be/UzxYlbK2c7E. I’m taking this course to refresh my machine learning concepts. I expect this to be one of the better courses.

Another one I got myself enrolled into is the Game Theory course. Here is the link to the page - http://www.game-theory-class.org/. Everyne who has watched the movie – A Beautiful Mind – will agree to have been fascinated by the game theory concept. Shenoy and I tried to learn more about this by doing a mini-project in our third year, but I wouldn’t count that as a successful experience. Hopefully, this time the experience will be better.

The third course to interest me was the Cryptgraphy - http://www.crypto-class.org/. Once again, we had this in our third year but I never took it seriously enough even though the topic had always interested me. Lucky for me, my brother is doing a course in Cryptography this semester. So I’ll have someone close to talk to clear any specific doubts. There’s always the course forum otherwise.

The fourth one is Probabilistic Graphical Models - http://www.pgm-class.org/. The desire to take up the course arouse from the fact that it’ll be mathematically involved. Also I think the knowledge of models can supplement my Machine Learning fundamentals.

Lastly, I also got myself enrolled for the Natural Language Processing course - http://www.nlp-class.org/. Now this’ll be something entirely new – something I have absolutely no idea of. That is the exact reason why I want to study this subject. During my four years of engineering, I never picked up this course, but finally I have the chance to learn about this topic.

My expectation from the course is pretty simple – good lectures, good quizzes and assignments and a mini-project in each. At present I’m quite excited about getting started and I’ve convinced myself that I’ll definitely find time to study the subjects the right way this time. I hope I can do that. My goal is to know these 5 topics more in depth by the end of April – yeah, I expect to continue even after the course is done.

Popularity: 1% [?]

Project Euler : Frequency Analysis For Message Decryption

Published on October 22, 2011 in Problems. 0 Comments

Problem 59 of Project Euler brought back memories of Sherlock Holme’s Dancing Men. Holmes had to decrypt a series of messages – the characters of which were stick men figures in varying dancing positions. He computed the frequencies of each dancing figure. Then since ‘e’ is the most used letter in English, he replaced the most frequent dancing figure with ‘e’.

I did the same thing with a difference. The given text in the problem did not have any spaces. This meant that even the spaces had been encrypted. And the most frequent number occurred almost twice as much as the next one. So I replaced that with space. That’s it. The problem was solved.

The password used to encrypt the text is – ‘god’ and the following code decrypts the text and finds the answer in the count variable.


    private List<Distribution<Integer>> parseInputFile(String fileName) throws FileNotFoundException {
        List<Distribution<Integer>> frequencies = Lists.newArrayList(new Distribution<Integer>(), new Distribution<Integer>(), new Distribution<Integer>());

        Scanner scanner = new Scanner(new File(fileName)).useDelimiter(",");
        int count = 0;
        for(int i = 0;  scanner.hasNext(); i++) {
            int num = scanner.nextInt();
            frequencies.get(i % 3).add(num);

            if(i % 3 ==0) num ^= 103;
            else if(i%3 == 1) num ^= 111;
            else if(i%3 == 2) num ^= 100;
            count += num;
            System.out.printf("%c", num);
        }

        System.out.println("Sum = " + count);

        return frequencies;
    }

Popularity: 5% [?]

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. ]

Popularity: 1% [?]

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. ]

Popularity: 2% [?]

Electronic Code Book

Published on March 18, 2009 in Miscel. 0 Comments

[ 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. ]

Popularity: 1% [?]

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. ]

Popularity: 1% [?]