Cryptography - a Study

INTRODUCTION TO CRYPTOGRAPHY

INTRODUCTION

Cryptography is the branch of science that deals with data security relating to encryption and decryption. This science has been in existence about 4000 years ago with its initial and limited use by the Egyptians, to the twentieth century where it played a crucial role in the outcome of both world wars. Cryptography was used as a tool to protect national secrets and strategies. DES, the Data Encryption Standard, is an adoption with the Federal Information Processing Standard for encrypting unclassified information, is the most well-known cryptographic mechanism in the history. It remains the standard means for securing electronic commerce for many financial institutions around the world.

The two most basic terms related to cryptography are Encryption and Decryption. These terms play a crucial role in bringing up this topic, and have been discussed in detail. The other terms that are crucial related to this topic is Secret Keys and Ciphers (upon which our entire report is based).

ENCRYPTION AND DECRYPTION

As said earlier, Encryption and Decryption are the two most basic terms of Cryptography. Here, the secret is to convert the plain text, which is the usual text that we encounter daily, into a Cipher text which on sight looks just like a ordinary plain text but with a secret message hidden which can be only read by the person who knows the secret behind the new text.

The above situation can be termed as Encryption and Decryption. The term Encryption means to convert the plain text into the Cipher text and Decryption means to convert the Cipher text back to plain text. Both Encryption and Decryption are done using a secret key or symmetric key which is usually possessed only by the one who encrypts and by the one who decrypts. Figure 1-1 shows us the basic diagram of the encryption and decryption process.

Figure 1-2 shows the conventional encryption which even includes the secret key.

MODULAR ARITHMETIC

INTRODUCTION

This branch of mathematics is the most important link towards Mathematics and Computer Science. Modular Arithmetic has been used in various encryption techniques and a short detail about is given below.

EUCLID'S THEOREM

The Euclids theorem is the theorem that can be defined as the basis of Modular Arithmetic. This theorem states "Let a and b be two positive integers where a>b, if b divides a then gcd(a,b)=b . if b does not divide a, then we can find the gcd(a,b) using repeated division as follows.

a=bq0+r1, 0<r1<b

b=r1q1+r2, 0<r2<r1

r1=r2q2+r3, 0<r3<r2

r2=r3q3+r4, 0<r4<r3

.............. ............

rn-2=rn-1qn-1+rn, 0<rn<rn-1

rn-1=rnqn+0

here, r0, which is the last non zero remainder is the greatest common factor of the numbers a and b

Using Euclids theorem, the gcd of 1281 and 243 can be found as

1281=5*(243)+66

243=3*(66)+45

66=1*(45)+21

45=2*(21)+3

21=7*(3)+0

Therefore, gcd(1281,243)=3

MODULAR ARITHMETIC

If a is an integer and n is a positive integer greater than 1 , then we can define 'a mod b' to be remainder r when a is divided by n.

This can be written symbolically as

r = a mod n=a-[a/n]n.

To find the value of 154x≡22 (mod 803) can be done in the following manner

154x≡22 (mod 803) < == > 154x-803y=22

Using Euclid's Algorithm, we can find the gcd(154,803) as follows

803 = (154)*5 + 33

154 = (33)*4 + 22

33= (22)*1 + 11

Since gcd(154,803) = 11, and 22 is divisible by 11, the given equation can be solved. Rewriting the above equations

33=803-(154)*5

22=154-(33)*4

11=33-(22)*1

And on working backwards on the above equations, we land up with the equation

11= (803)*5 - (154)*26

Therefore, r ≡ -26 ≡ 777(mod 803) and hence there are 11 solutions altogether.

This concept,as already mentioned, has been discussed widely in various encryption techniques.

CIPHER

DEFINITION

Cipher can be defined as 'an algorithm for transforming an intelligible message into one that is unintelligible by transposition and/or substitution methods.

Generally in these ciphers, the encryption and decryption are written symbolically as

Encryption, C = E_(K) (P)

Decryption, P = E_(K)-1 (C)

E_(K) is chosen from a family of transformations known as a cryptographic system.

The parameter that selects the individual transformation is called the key K, selected from a keyspace K.

More formally a cryptographic system is a single parameter family of invertible transformations.

E_(K) ; K in K : P -> C

with the inverse algorithm

E_(K)-1 ; K in K : C  P

such that the inverse is unique.

Usually assume the cryptographic system is public, and only the key is secret information

CHARACTERIZATION