Cyphers and Codes

Laterally Speaking · 2007-05-24 05:49:00

It is "common knowledge" among cryptographers that there is no such thing as a perfectly unbreakable cypher. However, I believe that this is not entirely true...

A onetime pad cypher is a polyalphabetic substitution cypher (for those who don't know what this is, I'll explain later). The key in a onetime pad is RANDOM (or as random as you can get). This is the basis of the system. This cypher is known to be unbreakable, because of the following:

The person intercepting the coded message does not know the key, so the best way for them to find out the message is to draw up a table of all the possible combinations of keys/messages that would give you the message that the person intercepted. Normally, the actual message would be easy to find, because the message and key would make sense (for longer messages, there would be 3 or 4 possibilities). However, since the key is RANDOM, the person cannot have any way of knowing which sensible message is the right one (for longer messages, there can be 70 or 80 possibilities, since the number of combinations of characters is, with ASCII, length of message^255).

Unfortunately, the trouble with this is getting the key to the recipient without being intercepted. This is where my idea comes in...

Laterally Speaking · 2007-05-24 05:59:40

There is another form of cypher which is completely different from a onetime pad (a symmetrical cypher, in which the key used to encrypt is the same as the one used to decrypt). This type of cypher is known as a public/private key cypher. The idea is that the key that is used to encrypt a message is different from the one used to decrypt it, and the latter CANNOT be deduced from the former. The encryption key is PUBLIC: it can be accessed by anyone. The decryption key is PRIVATE: it never, ever has to change hands.

My idea is that if you encrypt your message using a onetime pad, then string the key along to the end of the encrypted message, then send this whole string encrypted again with a public/private key cypher, the resulting cypher will be perfectly unbreakable: the onetime-pad-encrypted message followed by the key (which is always the exact same length as the message) is just as random as said key.

Therefore, when you encrypt the randomness with a normally breakable cypher that doesn't need to have its key transferred from sender to receiver, there shouldn't be any way of finding out whether what you decrypt is the right thing or not.

Laterally Speaking · 2007-05-24 06:27:30

Now for the promised explanation of a polyalphabetic cypher:

You need: a piece of graph paper, a message and a key that is the same length as the message.

First, make a table that is 26 * 26 big. now, fill it in, starting at the upper left corner with A, and going across and downwards with the alphabet. You should now have 1 column and 1 row filled in. Now fill in the rest of the table so that each row and column has the entire alphabet in it, such that, for example, row 1 starts with "A" and ends with "Z", row 2 starts with "B" and ends with "A", row 3 starts with "C" and ends with "B", etc.

In case you don't get this, you can ask for more details

Now that you have your table, you can start to encrypt. Take the first letter of the message, and find the row that starts with this letter. Now take the first letter of your key, and find the column that starts with it. Find the point where these lines cross, and write the letter that is there. Now do this for the other letters.

Laterally Speaking · 2007-05-24 06:55:37

Another way to do this process is to associate each character with a number (in ASCII, A=65, B=66, C=67, a=97, b=98, c=99...). Now you take the two numbers, corresponding to the first character of the message (m) and the first character of the key (k), and do the following: (k+m)mod 255 (for ASCII).

To decrypt this, the process is a bit more complicated to explain, but you basically do the opposite operation.

Laterally Speaking · 2007-05-25 21:01:29

Public/Private Key cyphers are generally hard to explain, but they usually involve:
-- HUGE random prime numbers
-- raising the message to the power of the public key, which is the product of the two HUGE primes.
-- sending: (message above raised) mod (a second part of the public key)
The private key is such that it can only be found using the two primes and that raising the encrypted message to the private key's power mod second part of public key gives you the message back.

Even the sender (and encrypter) of the message cannot decrypt it!

Laterally Speaking · 2007-05-25 21:09:17

Here's the relatively easy to understand math behind RSA public key encryption.

1. Find P and Q, two large (e.g., 1024-bit) prime numbers.
2. Choose E such that E is greater than 1, E is less than PQ, and E and (P-1)(Q-1) are relatively prime, which means they have no prime factors in common. E does not have to be prime, but it must be odd. (P-1)(Q-1) can't be prime because it's an even number.
3. Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). This can also be written as DE = 1 (mod (P-1)(Q-1)), and D is called the multiplicative inverse of E. This is easy to do -- simply find an integer X which causes D = (X(P-1)(Q-1) + 1)/E to be an integer, then use that value of D.
4. The encryption function is C = (T^E) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation. The message being encrypted, T, must be less than the modulus, PQ.
5. The decryption function is T = (C^D) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation.

Your public key is the pair (PQ, E). Your private key is the number D (reveal it to no one). The product PQ is the modulus (often called N in the literature). E is the public exponent. D is the secret exponent.

Last edited by Laterally Speaking (2007-05-31 05:04:05)

Laterally Speaking · 2007-05-25 21:13:38

This entire system was discovered by Ron Rivest, Adi Shamir, and Leonard Adleman.

John E. Franklin · 2007-05-30 15:39:26

Very interesting, sir.
I enjoy coming up with codes.
It is fun to scramble the letters of the word up, prior to encoding it, just
to make decrypting more fun, like playing scrabble.
So when you decode the message, you still have rubbish.
Like "Christmas" could first be mixed up to "mathrisc" and duplicate letters like two s's could be reduced to one s.
Or if you like geometry, you can do something in 2 or 3 dimensions, and then utilize
projections, to reduce 3 dimensions to 2 dimensional views, etc. Currently I'm playing
around with something for fun with lots of colors in various positions for words!!
Hope you're having as much fun as I am!!

Laterally Speaking · 2007-05-31 04:37:17

I'm having plenty of fun.

I came up with an interesting one just now:

Find a keyword (try to keep it small) and write it out in BIG block letters on a piece of graph paper (each letter should take up 18*18 squares or 9*9). Now write out your message (encoded if you want) vertically inside the large block letters. now fill in the rest of the paper with relatively random stuff and erase the traces of the keyword letters.

This may take awhile, but it's fun to see if anyone can figure it out, even if the stuff isn't actually encoded.

Laterally Speaking · 2007-05-31 04:38:29

By the way, no need to call me "sir". I'm 13.

John E. Franklin · 2007-05-31 20:56:08

A really awesome code to know is Braille.
See this encoder tool on our site here.
http://www.mathsisfun.com/braille-translation.html

Laterally Speaking · 2007-06-01 06:35:20

It isn't really a code if millions of people have to know it, but it's a good way to get a message past someone who doesn't know it, which most people don't.

Laterally Speaking · 2007-06-13 06:45:01

Morse code isn't used much any more, so it's handy to know if you want to send a message to someone with relatively low chances of it being intercepted.

There is another form of cryptography that relies on single photons being sent, polarized in a specific direction.

I've gotta run now, so I'll explain (to myself, it seems) later.

Laterally Speaking · 2007-06-15 04:42:49

The idea of quantum cryptography was told to me in a book, The Code Book, by Simon Singh.

Basically, the idea is based upon the fact that a single photon, polarized using either an X scheme (where /=1 and \=0) and a + scheme (where |=1 and -=0), if it is intercepted, the interceptor cannot know which scheme it is on, and therefore has their best odds if they use a random scheme to attempt to decrypt it. If they get it right, they have a 100% chance of getting the right number. If they use the wrong one, they have a 50/50 chance of getting the right one (an X-polarized photon has that chance of getting through a +-filter), and either way, the person on the receiving end can tell, through a non-revealing check with the other person, whether somebody has tries to get the information. This whole process is used just as a Diffie-Hellman-Merkle key exchange, allowing the two correspondents to exchange a key for a symmetric cypher safely.

If you want more info, I suggest you read the book in question; it has a lot of information.

John E. Franklin · 2007-06-16 17:12:05

Polarized light, that has always intrigued me. Thanks for reminding me. Twist two polarized lens on top of one another and the light can't get through, and then it can at various angles. Thanks for the summary about the code book!

Laterally Speaking · 2007-06-16 21:23:32

Actually, The Code Book is sort of a history of cryptography, from ancient Egypt to the future, so I can't say that what I said is a summary.

One of the things about polarized light is this: if you have two Polaroid filters on top of each other, at a 45-degree angle between them, then approximately half of the photons which hit the assembly will get through to the other side. The others will be stopped by the second filter, which is at a 45-degree angle from their polarization.

John E. Franklin · 2007-06-18 14:43:26

The clock has 12 hours because Egyptians counted on their knuckles.
3 knuckles on each finger times 4 fingers is 12.

Laterally Speaking · 2007-06-19 03:43:11

Oh, is that why? Why are seconds as long as they are? Why are minutes 60 seconds? Why are hours 60 minutes? Why are there 24 hours in a day?

Laterally Speaking · 2007-06-26 23:21:37

In any case, I have written a program with Visual Basic 5.0 to do onetime pad encryption (and decryption) automatically; you simply type the stuff into the appropriate text boxes, press the right buttons, and it (usually) gives you what you want.

I might post a link to it somewhere around the forum.

Zach · 2007-06-26 23:35:49

The day is not 24 hours. It's 23 hours and 57 minutes, more or less. That's why you have a leap year every four years. It's to do with the earth's rotation; which isn't exactly 24 hours.

mathsyperson · 2007-06-27 01:12:09

The Earth takes around 23 hours and 57 minutes to fully rotate, but we see it as 24 hours because it also moves around the sun a little bit. It technically spins ~366 times in a year, but one of those is cancelled by the orbit around the sun.

Leap years aren't to do with that though. They exist just because there aren't an integer amount of days in a year and so some years need to be leapy to balance it out.

Laterally Speaking · 2007-06-27 06:34:02

Yes, there are about 365.25 days in a year, thus the leap year every four years.

I seem to have a problem, partly for you (I should be able to give you the solution around mid-summer.

I wrote a program in VB that take a binary number and turns it into a seemingly random (but repeatable) string. Normally, I would be able to simply look at the VB code and find the algorithm I used, but I had to uninstall VB to make room on the drive. I was wondering whether any of you people could figure it out from the .EXE that I made of it before uninstalling VB. It's probably not possible, but hey!

I might post the algorithm once I get VB reinstalled (perhaps just the code I used).

Last edited by Laterally Speaking (2007-07-22 04:01:50)

Laterally Speaking · 2007-06-27 06:42:25

In any case, this is the program in question.

Laterally Speaking · 2007-06-27 08:22:53

I have posted links to two programs I created. Using the two of them together, you should be able to figure this one out.

Enter this into the "encrypted" section of the onetime pad program: ¡Ëh·¶¹Õ«ÒY%Ù? ~wDâÜ¡N±°éá^{{[Nt-z,§ÆÁ&ããñýü&%ä9)ôÑ
Enter this into the small text box of the program above: 1000010111011101101010100100001001010111010101101010111101

Math Is Fun Forum

#1 2007-05-24 05:49:00

Cyphers and Codes

#2 2007-05-24 05:59:40

Re: Cyphers and Codes

#3 2007-05-24 06:27:30

Re: Cyphers and Codes

#4 2007-05-24 06:55:37

Re: Cyphers and Codes

#5 2007-05-25 21:01:29

Re: Cyphers and Codes

#6 2007-05-25 21:09:17

Re: Cyphers and Codes

#7 2007-05-25 21:13:38

Re: Cyphers and Codes

#8 2007-05-30 15:39:26

Re: Cyphers and Codes

#9 2007-05-31 04:37:17

Re: Cyphers and Codes

#10 2007-05-31 04:38:29

Re: Cyphers and Codes

#11 2007-05-31 20:56:08

Re: Cyphers and Codes

#12 2007-06-01 06:35:20

Re: Cyphers and Codes

#13 2007-06-13 06:45:01

Re: Cyphers and Codes

#14 2007-06-15 04:42:49

Re: Cyphers and Codes

#15 2007-06-16 17:12:05

Re: Cyphers and Codes

#16 2007-06-16 21:23:32

Re: Cyphers and Codes

#17 2007-06-18 14:43:26

Re: Cyphers and Codes

#18 2007-06-19 03:43:11

Re: Cyphers and Codes

#19 2007-06-26 23:21:37

Re: Cyphers and Codes

#20 2007-06-26 23:35:49

Re: Cyphers and Codes

#21 2007-06-27 01:12:09

Re: Cyphers and Codes

#22 2007-06-27 06:34:02

Re: Cyphers and Codes

#23 2007-06-27 06:42:25

Re: Cyphers and Codes

#24 2007-06-27 08:22:53

Re: Cyphers and Codes

Board footer