Sunday, 29 January 2012

Cryptography

I realise that there's been a severe lack of music programming as of late.  This is mostly because of lack of free time - I've had a load of exams which I figured were more important.  It's all starting up again, but otherwise I've just been looking over bits and pieces.

Cryptography caught my interest for no real reason a while ago, but I didn't want to delve too deep and lose focus of the other stuff I'm doing.  I ended up buying "Crytography: A Very Short Introduction", which is a great read and really short.  It gave me a good enough insight into the processes used, while staying away from pretty much any maths and without getting too involved.  I'd definitely recommend it.  I'm not going to write about everything I found in the book, I'll just describe something that I thought was pretty interesting.

First a few definitions though: A cipher is something that processes plaintext and turns it into ciphertext - it scrambles the message so if someone intercepts it, it's rubbish to them.  It usually relies off an encryption key and a decryption key, where in some systems, the two keys are the same.  The decryption key should always remain secret to the user, while the encryption may be publicly available - which is where things called public key systems come from.  A bad cipher will scramble the text so that the interceptor can work out what the plaintext is from the ciphertext without the decryption key - through a process called cryptanalysis.  It sounds complicated, but could be as simple as looking at the frequency of letters and comparing it against known frequencies.  If two countries were at war then governments would throw everything they have at breaking the enemy's ciphers, which might involve some very clever techniques.

I thought the coolest thing in the "Short Introduction" was the fact there is a mathematically proved "unbreakable cipher", called the one-time pad.  The proof was done by a guy called Claude Shannon, who also made major developments in what is now called information theory, which is vital for things like compression and communications.  The one-time pad must have a key that is
  • At least as long as the plaintext message
  • Truely random
  • Only be used once.  
Break any of these golden rules and you have a system that could even be easily breakable!  The main difficulty comes from randomness.  Most methods of generating random numbers are in fact fairly predictable and show pattern.  For example, the rand() function in the C library would be nowhere near good enough for this kind of application.  If the interceptor knows how the random keys were generated, there's a good chance they can break the ciphertext.

The popular phrase as "only being as strong as the weakest link" also applies here.  How do you distribute the key, if it's basically the message itself?  If you're to send it electronically, then you'll have to encrypt the key with another cipher.  But the cipher won't be unbreakable, so you render the one-time pad system breakable.  The only way to distribute the key is physically.  These difficulties are why the one-time pad is pretty much exclusively used by governments and spies, for top confidential messages.  Breaking the one-time pad sounds unfeasible - at least to me.  Operation Venona is an instance where this happened, due to the Russians reusing their keys.

I haven't actually explained how the system works - you simply "add" the letter of the message and the corresponding key letter, and divide it modulo 26.  This essentially wraps the letter around.  Another thing is the same system could be done with bitstrings and just dividing modulo 2.  To decrypt, the process is repeated but with ciphertext and the key.  Another cool thing about the one-time pad is it was done physically by spies, with tiny books full of keys, and they manually produced the ciphertext.  Most other modern ciphers are far too complex for this to be feasible, but for the one-time pad, the unbreakable cipher, it's relatively straightforward.


Might need your glasses...


No comments:

Post a Comment