Math and Computer & Web Security - Cryptography

A military commander wants some assurance that the information sent to field commanders does not fall into the hands of opponents. Hence, written communications which can be easily read if intercepted by an an enemy are dangerous. (Asking the messenger to memorize secret messages is not practical, and if one can believe the spy and counter-terrorism thrillers currently on TV, not secure.) Julius Caesar is often credited with one of the earlier attempts at using a cryptological system with a mathematical flavor to disguise messages. It is claimed that he used a system in which each letter of the alphabet in a "plaintext," the original message, is replaced by the next letter of the alphabet, with the last alphabet letter cycling around to be represented by the first letter of the alphabet. Thus, the phrase Caesar Cipher would be replaced by Dbftbs Djqifs. Coming across a message such as this, one is faced with the tremendous range of possible systems that might have been used to disguise the original message. It might confuse the "enemy" for a while. Within the range of what today have come to be called Caesar Ciphers, one could shift the replacement alphabet by r places, rather than 1 place (r =1) in the example above. When r = 5 the phrase Caesar Cipher becomes hfjxfw hnumjw.

However, if a decoder hits on the idea that the way the plaintext is being disguised is to shift each letter by the same number of positions, it is not very much work, with the English alphabet of 26 letters, to try them all. This simple example already shows the interesting connection between "complexity" issues and security, whether it be Internet use of cryptography or military use. In some situations slowing down one's opponent is good enough. If it takes an hour to decode a message whose information content is valueless after an hour, then the coding system has done its job. However, if a message is decoded, then the next time a similar message is intercepted, the time to recover the hidden information could go down from an hour to 3 minutes. Then I must keep finding ways to stay a step ahead of my "enemy." In this discussion I will use the words code and cipher and decode and decipher interchangeably. However, usually a cipher refers to replacing a symbol of a plaintext alphabet by another single symbol from some other alphabet or the same alphabet. By contrast, a code refers to replacing blocks of symbols in the plaintext, by another block of symbols.

There have been many developments in cryptography since the Caesar Cipher. One simple idea is not to use the same word lengths in the enciphered message as in the original. If the word "I" or "a" is left as a single letter in the "ciphertext," then it greatly simplifies the process of breaking the encryption system. Typically, the message is broken up into groups of 5 letters (disregarding spaces between words, and often punctuation) and replaced by 5 other letters. This has the effect of making the coded message look more "anonymous." If the length of the original message is not a multiple of five, then extra symbols, called nulls in the "trade," are added to fill out the needed positions.

Another simple idea is the use of a polyalphabetic cipher, where the alphabet used to encode the plaintext changes with each letter in accordance with some key. Using the key provides a way to change the alphabet used for the encoding as one matches a plaintext letter to a letter in the key. This idea was pioneered by Leone Alberti (1404-1472), who was also a pioneer of projective geometry. It is tempting to believe that such a "complex" system would be unbreakable. However, if the key length is short and there is lots of ciphertext available using the same system, then statistical methods can be used to break the cipher. If a key is used only once and is generated at random, the so-called one-time pad, then the cipher is not breakable. However, key exchange and generation of large amounts of random key present a significant problem for the volume of communications that we want to secure in modern times.

From: http://www.ams.org



Tumblr:
http://mathpost.tumblr.com/post/121011459280/math-and-computer-web-security-cryptography-a


Lofter:
http://mathdaily.lofter.com/post/1cc75b20_738efaf

The Fibonacci Sequence: Basic Things

The Fibonacci sequence: an introduction

The Fibonacci sequence is probably one of the most famous — and most widely written-about — number sequences in all of mathematics. So why write about it, if it’s been written about so much already? Well, because I can, and because it’s fun — there are good reasons it’s so popular! I plan to spend the next five posts (at least) talking about the Fibonacci sequence and its connections to other areas of mathematics.


The Fibonacci sequence is defined by the recurrence relation





In English, this says that the first two Fibonacci numbers are both equal to 1, and any Fibonacci number from the third onwards can be obtained by adding the previous two Fibonacci numbers. So the third Fibonacci number is 1 + 1 = 2; the fourth is 1 + 2 = 3; then 2 + 3 = 5; and so on. The first fifteen Fibonacci numbers are








As you can see, they get large fairly quickly. The 31st Fibonacci number is the first to exceed one million, and the 45th is already bigger than one billion.






The definition of the Fibonacci sequence is quite simple, but there’s a LOT more here than meets the eye, which I hope to expand on in subsequent posts. For now, we’ll start with this simple observation: what happens if you sum all the Fibonacci numbers up to a certain point? For example, let’s add up all the Fibonacci numbers up to 5: 1 + 1 + 2 + 3 + 5 = 12. Okay. How about going one further: 1 + 1 + 2 + 3 + 5 + 8 = 20. If we include 13 as well, we get 33. Do you see a pattern? (Hint: compare the sums we got (12,20,33) with the Fibonacci sequence itself.) Does this always work, and if so, can you show why (and if not, can you give an example where it doesn’t)? Feel free to post comments!






By Brent