Make your own free website on Tripod.com

Background Information

Coding and cryptography is a topic which requires thorough understanding of the theories/basics. Here, we have summarized our research for readers to read through the different types of codes used in the past and the present and the applications of them in our daily life.

 

Definitions

Coding : The technique that is used to translate data (human language) into codes so that electronics/machines can understand them.

Cryptography : The art of encoding messages such that only authorised people can obtain the true message.
Cipher : individual letters are replaced with other letters or symbols
Plaintext : normal text
Ciphertext : coded text

 

Universal Product Code (UPC)

"UPC" stands for Universal Product Code .

The UPC on a product has two parts:

The following list shows which numbers are assigned to which products.

Standard UPC number 0
Reserved 1

Random-weight items 2
(fruits & vegetables, meats)

Pharmaceuticals 3

Codes used for only a that store 4
(A store can make its own codes, but other stores cannot use them.)

Coupons 5

Standard UPC number 6

Standard UPC number 7

Reserved 8

Reserved 9

 

International Standard Book Number

The ISBN consists of ten digits and is divided into four parts.

•  Country digits

•  Publisher digits

•  Title digits

•  Check digit

 

To calculate the check digit, first multiply the last digit of the number by 2. Then multiply the second last digit by 3, the third last digit by 4 and so on. Now, add the results. Then divide the sum by 11 and find the remainder. Lastly, subtract the remainder from 11 to get the check digit.

 

The ISBN is used for many things, which includes:

•  Stock-taking

•  Identifying a book among others easily

•  Bibliography

•  Letting book sellers check sales information

The Singapore NRIC Check Digit

The Singapore NRIC number is made up of 7 digits and a letter behind. The method used to calculate the check digit is similar to the one used to calculate the check digit for the ISBN Code.
The steps involved to obtain the check digit is

  1. Multiply every digit in the NRIC number by its weight and add them together.
  2. Divide the result by 11.
  3. Subtract the remainder from 11 to give the check digit.
  4. Check the digit against the table below to get the correct alphabet.

The following table shows the weight for the NRIC number in Singapore :

2

7

6

5

4

3

2

The following table is used to change the check digit into the corresponding alphabet.

Check Digit

1

2

3

4

5

6

7

8

9

10

11

Alphabet

A

B

C

D

E

F

G

H

I

Z

J

 

This system is used to prevent illegal workers from entering Singapore with a fake passport using a fake NRIC number.

 

A person has a NRIC number S1234567A

To find out if the NRIC number is valid, we need to use the method above.

2(weight)*1(NRIC number) + 7(weight)*2(NRIC number) + 6*3 + 5*4 + 4*5 + 3*6 + 2*7 = 106

106 MOD 11 = 7

11-7 = 4

 

Using the table above, if the check digit is 4, then the alphabet at the end of the NRIC number should be D. So, we can conclude that this NRIC number is invalid.

 

The Morse Code

 

Morse Code

International Code

A

* -

* -

B

- * * *

- * * *

C

* * *

- * - *

D

- * *

- * *

E

*

*

F

* - *

* * - *

G

- - *

- - *

H

* * * *

* * * *

I

* *

* *

J

- * - *

* - - -

K

- * -

- * -

L

- - - -

* - * *

M

- -

- -

N

- *

- *

O

* *

- - -

P

* * * * *

* - - *

Q

* * - *

- - * -

R

* * *

* - *

S

* * *

* * *

T

-

-

U

* * -

* * -

V

* * * -

* * * -

W

* - -

* - -

X

* - * *

- * * -

Y

* * * *

- * - -

Z

* * * *

- - * *

1

* - - *

* - - - -

2

* * - * *

* * - - -

3

* * * - *

* * * - -

4

* * * * -

* * * * -

5

- - -

* * * * *

6

* * * * * *

- * * * *

7

- - * *

- - * * *

8

- * * * *

- - - * *

9

- * * -

- - - - *

0

- - - - - -

- - - - -

.

* * - - * *

* - * - * -

,

* - * -

- - * * - -

?

- * * - *

* * - - * *

 

The word PARIS is used to measure the speed of transmitting. The DIT is the standard unit and one DAH is equal to three DITS. Each DIT and DAH in a letter is separated by the length of one DIT. Each letter in a word is separated by the length of three DITS and each word is separated by the length of seven DITS.

 

One interesting thing is that the famous help signal “SOS” is in International code, not in Morse Code.

 

The Binary Code

The Alphabet in Binary Code

Letter

Binary Code

 

Letter

Binary Code

A

01000001

a

01100001

B

01000010

b

01100010

C

01000011

c

01100011

D

01000100

d

01100100

E

01000101

e

01100101

F

01000110

f

01100110

G

01000111

g

01100111

H

01001000

h

01101000

I

01001001

i

01101001

J

01001010

j

01101010

K

01001011

k

01101011

L

01001100

l

01101100

M

01001101

m

01101101

N

01001110

n

01101110

O

01001111

o

01101111

P

01010000

p

01110000

Q

01010001

q

01110001

R

01010010

r

01110010

S

01010011

s

01110011

T

01010100

t

01110100

U

01010101

u

01110101

V

01010110

v

01110110

W

01010111

w

01110111

X

01011000

x

01111000

Y

01011001

y

01111001

Z

01011010

z

01111010

Caesar Substitution
Example:

PLAINTEXT abcdefghijklmnopqrstuvwxyz

CIPHERTEXT DEFGHIJKLMNOPQRSTUVWXYZABC

 

It is very easy to break this type of substitution code because there are only 26 alphabets. There are several methods available to crack this code. One of them is by frequency analysis. Another way is to just list out all the alphabets, as shown in the example below.

 

this is a simple cipher
VJKU KU C UKORNG EKRJGT

V J K U K U C U K O R N G E K R J G T
-------------------------------------
u i j t j t b t j n q m f d j q i f s
t h i s i s a s i m p l e c i p h e r
s g h r h r b r h l o k d b h o g d q

Playfair

The Playfair code is very easy to use. First, choose a key and then fill in a 5 x 5 square with your key. In the key, no letters must be repeated. If the key already contains the letter ‘S', then all the other ‘S's will be omitted. The letters 'i' and 'j' counts as one and letters that appeared twice in a row are separated with a ‘Z'. In this example, the key is “BAORONGBIRANTONYYONGSHENGZHIQIAN”.

B

A

O

R

N

G

I

T

Y

S

H

E

Z

Q

C

D

F

K

L

M

P

U

V

W

X

First, the message is split into bigrams of two letters each.

To encode the bigrams, look on the row of the first letter of the bigram that you are going to encode and find the letter that is directly above or below the second letter of that bigram. That is the encrypted letter. Repeat the procedure for the second letter, except that you look for the letter that appears directly above or below the first letter of that bigram.

Plaintext: th is is as im pl ec ip he rs to pz
Ciphertext: GZ is is NI SF WD ec GU he NY to VH

Now, you notice that some bigrams cannot be encrypted this way because the letters are either on the same row or the same column.

If both the letters are on the same row, then the one to the immediate right is used as the ciphertext. If it is at the right end of the row, then the one on the extreme left of the row is used. If both the letters are on the same column, then the one on the immediate bottom is used as the ciphertext. If it is at the bottom of the column, then the letter on the beginning of the column is used.

Plaintext: th is is as im pl ec ip he rs to pz
Ciphertext: GZ TG TG NI SF WD ZH GU EZ NY ZT VH

 

Double Transposition

First, choose a key. A grid is created below the key and the message to be encoded is written from left to right. Numbers are written above the grid. The numbers are random. Then the grid is arranged in the order of the numbers and read vertically down from left to right. The letter "Z" is used to fill in blank spaces in the grid.

The message "this is a simple cipher" after being encoded with double transposition. The key for the following example is "ENCODING".

E

N

C

O

D

I

N

G

8

2

3

5

4

7

1

6

T

H

I

S

I

S

A

S

I

M

P

L

E

C

I

P

H

E

R

Z

Z

Z

Z

Z


The message would read: AIZHMEIPRIEZSLZSPZSCZTIH

After this, repeat the method with another key (DECODING).

Note: The key does not have to be of the same length.

D

E

C

O

D

I

N

G

7

2

1

6

8

3

5

4

A

I

Z

H

M

E

I

P

R

I

E

Z

S

L

Z

S

P

Z

S

C

Z

T

I

H

And finally: ZESIIZELTPSHIZIHZCARPMSZ
To decipher this cipher, reverse the process.

Enigma

The Enigma machine was invented by Arthur Scherbius, a German Engineer in 1918. It has a keyboard that is connected to a lampboard by wires. Each letter has a connection to another letter.

However, this would only produce a monoalphabetical substitution code, which could easily be cracked by frequency analysis. An Enigma machine had three or four rotors, so that each letter was changed three or four times. The first rotor will rotate 1 position after a letter is typed, the second rotor rotates 1 position after the first rotor rotates 26 times and the third rotor rotates 1 position after the second rotor rotates 26 times. The machines also had a reflector, which reflected the electric current through the rotors again, encrypting the letter again.

The Frequency Analysis Table:

The frequency analysis method is used to crack simple substitution ciphers such as Caesar substitution. It works by checking how often a certain letter appears in a ciphertext and compares it to the frequency analysis table. For example, if the letter “h” appears very often in a ciphertext, then it is likely to be “e” or “a” in plaintext.

E

11.1067%

M

3.0129%

A

8.4966%

H

3.0034%

R

7.5809%

G

2.4705%

I

7.5448%

B

2.0720%

O

7.1635%

F

1.8121%

T

6.9509%

Y

1.7779%

N

6.6544%

W

1.2899%

S

5.7351%

K

1.1016%

L

5.4893%

V

1.0074%

C

4.5388%

X

0.2902%

U

3.6308%

Z

0.2722%

D

3.3844%

J

0.1965%

P

3.1671%

Q

0.1962%

 

The Unbreakable Cipher
The unbreakable cipher is called a one-time-pad cipher, and it was discovered in 1918, near the end of World War 1. It came from the Vigenère cipher, which used a poly-alphabetical substitution method. The Vigenère cipher could be broken because it only was encrypted by a more complex form of Caesar substitution with more than just 1 key.

A Vigenère SquareVigenère Cipher

The Vigenère cipher repeats the chosen key many times over the plaintext. Then, the text is encrypted, using a Vigenère square, according to the key that is written above it, similar to the way Caesar substitution is used.

 

 

 

 

 

To encrypt a message, write the code word above the message and repeat the code word if the message is too long. Now, look for the column that begins with the letter of the plaintext that you want to encrypt and draw a line down the column. Then look for the row that begins with the letter of the code word and draw a line across the row. The letter at the point where these two lines meet is the encrypted letter.

Example:

Key: CODECODECODECODECOD
Plaintext: THISISASIMPLECIPHER
Ciphertext: VVLWKGDWKASPGQLTJSU

Decryption:

Caesar Substitution:
Key: DDDDDDDDDDDDDDDDDDDDDDDDDD
Plaintext: ABCDEFGHIJKLMNOPQRSTUVWYXZ
Substitution using the key ‘D': DEFGHIJKLMNOPQRSTUVWXYZABC
Ciphertext: DEFGHIJKLMNOPQRSTUVWXYZABC

Vigenère:
Key: CODECODECODECODECODECODECO
Plaintext: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Substitution using the key ‘C': CDEFGHIJKLMNOPQRSTUVWXYZAB
Substitution using the key ‘O': OPQRSTUVWXYZABCDEFGHIJKLMN
Substitution using the key ‘D': DEFGHIJKLMNOPQRSTUVWXYZABC
Substitution using the key ‘E': EFGHIJKLMNOPQRSTUVWXYZABCD
Ciphertext: CPFHGTJLKXNPOBRTSFVXWJZBAN

From this, you can see that the Vigenère cipher is nothing more than a more complicated version of the Caesar shift cipher.

In the Caesar substitution method, every letter of the key is the same, so it is straight-forward. However, with the Vigenère cipher, more lines of substitution are used, so it complicates the decrypting. However, the message can still be deciphered easily.

First, scan the encrypted text for repeating segments of more than three words. Then find a common factor for all of them. This decides how long the key is, for example, five. Once you know how long the key is, you can take every fifth letter and decrypt it by using frequency analysis, as with normal substitution.

So, to break this code, a person needs to know how long the key is. Then, it can use frequency analysis to break the code accordingly. To prevent this, the key has to be as long as the message.

If the key is as long as the message and it is not repeated, then the Vigenère cipher would be unbreakable. Frequency analysis can't be used to break this code because it relied on the chance of having the same piece of plaintext being encrypted multiple times using the same part of the keyword, then establishing the length of the keyword from that. If the keyword was as long as the plaintext and no repeated segments of the keyword are used, then frequency analysis will fail.

The one-time-pad cipher meets the requirements of all of them. It uses a random key which is hundreds of letters long so as to be able to encrypt messages of all lengths. However, it can only be used once and a new key must be used for each message.

Because of this, the one-time-pad cipher was never used widely. Keys needed to be distributed to everyone. And you have to make sure that both persons are using the same key at a time. If not, the decrypted plaintext may be gibberish or if someone is very unlucky, it will decrypt into a totally different message. This is the most secure part of the one-time-pad cipher. Any group of words of the same length as the plaintext can be obtained if the key used is wrong.

Example:

Key: LFBWIJSDFKJ
Plaintext: codingisfun
Ciphertext: NTEEVPAVKEW

If a wrong key is used on the same ciphertext, it might generate a different plaintext:

Key: UMWMNXEEWRQ
Plaintext: thisiswrong
Ciphertext: NTEEVPAVKEW

Even though this cipher has been mathematically proven to be unbreakable, it is not widely used because it is very difficult to keep track of which keys are being used and which keys have been used. Millions of keys per minute would be needed if everyone uses this system to protect their messages. Also, distributing the keys would be even more difficult as everyone needed to know when to use them and which keys have been used.

So, this one-time-pad cipher is used only when someone really needs ultra-high security. For example, the hotline between American and Russian president is protected by a one-time-pad cipher.

In the future, quantum theory may be used to send the keys to other people without fear of the keys being intercepted. Then, the one-time-pad cipher is used to encrypt the messages, making it a truly unbreakable code.

 

Quantum Cryptography

Quantum Theory

Quantum theory is a very complex and weird theory. If a tiny object such as one single photon (particle) of light has a choice of passing through either the left hole or right hole of a paper with two holes, then it will be passing through both the holes. An experiment has been conducted and it showed light passing through both holes when only one photon of light was produced. Another example is of a cat, put in a box, which was fed with poison. The poison may or may not kill the cat. The box is covered. Is the cat dead or alive? The answer, according to quantum theory is that the cat is both dead and alive.

Quantum theory can be summarized into one sentence: if we do not know about what state an object is in when it has more than one state to be in, then it is said to be in both the states.

Quantum theory may seem strange, but it is the only theory which can explain how DNA works, how the sun shines, how to design the laser that reads CDs and even allow scientists to calculate the consequences of nuclear reactions in power stations.

Computers nowadays calculate by using binary numbers formed by particles. For example, if a particle is to the east, then it represents ‘1'. If it is to the west, it represents ‘0'. So, seven particles in the order “west, west, east, west, east, west, east, east” would represent 00101011 or 43. If we want to change it, then we can fire a beam of energy to the particles. If it is a strong one, then it will change the position of the particle to one that you want to change it to. If it is a weak beam, then it may or may not change the position. If we block ourselves from the particles so that we do not know which state (position) it is in, then, by applying quantum theory, it is in both states. By using just seven particles, it can represent 128 possibilities. Thus, it is able to make 128 calculations at one time, instead of only 1 calculation at a time. So, we can use them to break RSA and Pretty Good Privacy, which relies on the fact that it will take 12 million times the age of the universe to check every single digit from 1 to 10 308 to find out if the digit is a factor. If we use 10 particles, then the number of calculations we can make is 2 10 , which is 1024. If we use 100 particles, then the number would be 2 100 , which is 10 30 . 10 308 , the most secure version of RSA used for bank transactions, can be broken by 1024 particles.

According to our interview, quantum computers have been invented with 4 particles, which are able to calculate 2 4 or 16 calculations at a time, thus being able to factor numbers up to 16.