Showing posts with label cryptography. Show all posts
Showing posts with label cryptography. Show all posts

14 Jun 2013

Prize Maths Quiz: A Number Puzzle Within a Code (PMQ23)


Vvw nhrehawa X(p) uadrw wg lpr rwatme sh dgavxkjw qaxguwzf xjol iei tsdigmxsdg cvkaw bb r. Ril iasvvwz jea, wl qf xjs fczfgf gn vrvsymew o, kzmei 1 ≤ o ≤ b, kcpl vvsb glg uul(a,q)=1. Hcj mkeoddm, G(10) = {1, 3, 7, 9} = 4.

Gczucyevs L(30) iah V(43) ofl uipqw nvrf H(55470).

You may even be able to answer the question without fully decrypting it!

Enjoy!




13 Jun 2013

RSA Public-Key Encryption: Upper Secondary Mathematics


The idea behind every encryption system is to make communication between two parties secure and secret. The systems we have looked at this week involve a method, or algorithm, and a key; sometimes the encryption and decryption keys are the same, sometimes different. The task of anybody trying to intercept the communication is to try to discover both the algorithm and the encryption/decryption keys.

In 1977 a counter-intuitive discovery was published: that it was possible to devise a system where the encryption key was made public with only the decryption key kept private. This became known as RSA Public-Key Encryption and is still in use today.

Rather than thinking about it in terms of keys, imagine we have a lock-and-key system. Zeta receives all her communication via a courier system that places every message inside a box, locks it and then sends it to her. Zeta has created many copies of her private lock and distributes them throughout the world. Anybody who wishes to communicate with her places their message in a courier box, finds one of Zeta’s special locks and then closes the box securely using that lock. Anybody can do this, but only Zeta holds the key that unlocks the box! The encryption locks are public but the decryption key is private.

The mathematics behind this system involves knowledge of prime numbers and modular arithmetic. Let me go through one example, then you can try a similar question.

12 Jun 2013

The Undecipherable Cipher: Middle Secondary Mathematics


The weakness of the substitution ciphers used in the first two questions is that the distribution of letter frequencies remains intact. However, there is a very simple yet powerful method that changes the distribution of letters, thereby making the ciphertext much harder to crack.

The most common letters in the English language form the sequence ETAON RISHD; the most common double letters are TH and HE; and the most common first letter of a word is T. If blank spaces are encoded, then the ”space” becomes the most popular symbol (for example, in Unicode the “space” is encoded as U+2420). All this statistical information is used to crack simple substitution ciphers. However, what would happen if we used a sequence of different substitutions? A 16th century French diplomat, Blaise de Vigenère, perfected just such an encryption method that now bears his name.

Imagine that instead of one alphabet disk we have a sequence of them. Both the plaintext and ciphertext letters are in alphabetical order. Now, imagine picking a keyword, let’s start with something simple such as BYTE. Set the first wheel so that the plaintext letter A is encoded into the letter B; then set the second wheel so that A encodes into Y; then set the third and fourth wheels to T and E. No further wheels are needed in this case. Now, take your plaintext and encode the first letter using the first wheel, encode the second letter using the second wheel, and so on. Once you reach the end of your keyword start from the beginning again; in this way the fifth letter of the plaintext will be encoded using the first wheel again. This very simple method destroys the frequency distribution of the letters in the plaintext.

Without computers, the Vigenère Cipher is extremely difficult to crack. Indeed, if the keyword is very long - say, a whole poem - or at least longer than the actual message, then it is impossible to crack! It became so famous as to be called the Undecipherable Cipher. However, using some brute force computing and a fairly short keyword, some new statistical patterns emerge.

11 Jun 2013

Cracking Codes: Lower Secondary Mathematics

This week is dedicated to a topic that is perhaps the most widely untaught part of mathematics: cryptography. It does not appear in school maths, nor has it made an appearance in maths competitions; I suspect the latter is true because problems tend to be either very simple or very tough! However, the ubiquitous use of encryption in communication devices means that the mathematics of cryptography should be more widely taught; outside the pages of puzzle books and well before university.

As a student, I first came across it as a teenager attending the Mathematics Masterclasses at the Royal Institution. I later taught a similar course at a Gifted Summer School. Indeed, it makes a great project for gifted maths clubs, summer schools and any other form of extension to the standard curriculum.

The first puzzle was a simple substitution cipher often called the Caesar Shift Cipher or rot-N, where N denotes the number of letters by which the alphabet has been shifted, or rotated when using an alphabet wheel.

The problem with merely shifting the alphabet is that there are very few ways to encode a message; if you get one letter correct, the whole message appears! Assuming a 26-letter alphabet, the simple shift cipher has only 25 settings - the 26th setting is the original plaintext. However, if we substitute the letters randomly, we have 26! possible permutations and that’s over 4x1026 potential ciphertexts – over 40,000,000,000,000,000,000,000,000 in longhand.

This Substitution Cracking Tool from Simon Singh, and its frequency analysis, will help you bring such a large number down to size.

Ciphertext 1

CJZTB OIXTT LJQJKRX XTCHKRX SAKVCABL MJOI LJYTL TUHRK OA OIALT AG R XJCIO RBCKTY OXJRBCKT OITB OIT RXTR AG OIT KRXCTLO SAKVCAB JL TUHRK OA OIT LHQ AG OIT RXTRL AG OIT OMA LQRKKTX ABTL

Related Posts Plugin for WordPress, Blogger...