Cryptography and Network Security

The extended euclidean algorithm Given two integers a and b, we often need to find other two integers s and t such that  s * a + t * b = gcd ( a, b ) The extended euclidean algorithm can calculate the gcd ( a, b ) and at the same time calculate the values of s and t. The algorithm uses three sets of variables r's, s's and t's. In each state r1, r2 and r have same value in the euclidean algorithm. The variables r1, r2 are initializes t the value of a and b respectively. The variables s1, s2 are initialized to 1 and 0 respectively. The variables t1 and t2 are initialized t 0 and 1 respectively.  r1 = a ; r2 = b ; ( Initialization) s1 ← 1 ; s2 ← 0 ; t1 ← 0 ; t2 ← 1 ;  while ( r2 > 0)  {    q = r1 / r2;    r = r1 - q * r2 ; (updating r )    r1 ← r2;  r2 ← r ;    s ← s1 - q * s2 ;    s1 ← s2 ; s2 ← s ; (updating S's)    t ← ...

Greatest common divisor One integer often needed in cryptography is the greatest common divisor of two positive integers. Two positive integer may have many common divisor but only one greatest common divisor. For example, the common divisor of 12 and 140 are 1, 2 and 4. However, 4 is the greatest common divisor.       The greatest common divisor of two integers is largest integer which can divide both given integers. The following block diagram illustrate the basic of the greatest common divisor of 12 and 140. " Euclidean Algorithm " Finding the greatest common divisor ( GCD ) of two positive integers by listing all common divisor is not practical, when the two number integers are large. Fortunately, more than 2000 years ago a mathematician named Euclid develop an algorithm that can find the greatest common divisor of two positive integers. The Euclidean algorithm is based on the following two facts: 1. gcd ( a, 0 ) = a 2. gcd ( a, b ...

In integer arithmetic, we use a set and few operations. We are familiar with this set and corresponding, but they are reviewed here to create a background for modular arithmetic. ( i ) Set of Integers : The set of integers, denoted by 'Z', contains all integral number ( with no fractions ) from negative infinity to positive infinity. Which is shown as follows Z = { -∞, ........, -2, -1, 0, 1, 2, ............., +∞ }. ( ii ) Binary operations : In cryptography, we are interested in three binary operations applied to the set of integers. The binary operation takes two integers and create one output. Three common binary operations defined for  integers are addition, subtraction and multiplication. Each of these operations takes two input ( a, b ) and creates one output ( c ) as shown in the following figure. The following shows the results of the three binary operations on two integers because each input can be either positive or negative, we can ...

There are two properties of group as follows (a) Identity element in a group is unique. Proof :             Let e be the identity element of a group ( G, O ), Then we have to show that 'e ' is unique. If possible let e' be an other identity element of the same group ( G, O ). ∵ e be the identity. ∴ a O e = e O a = a ∀ a ∊ G If a = e' then, e' O e = e O e' = e'  ∀ e' ∊ G     ➖ ➖ ➖ ➖ ➖ (i) Again, e' is the identity So, a O e' = e' O a = a ∀ a ∊ G e O e' = e' O e = e ∀ e ∊ G   ➖➖➖➖➖ (ii) from (i) and (ii) we get,  e = e' Hence, there is one and only one identity element is present in G. (b) Formation of Ring (Ring) Ring :   A non-empty set 'R' with two binary operation '+'  ( called ordinary addition ) and '*' ( called ordinary multiplication ) is said to be a ring ( R, +, * ) if ( R, + ) is an abelian group , ( R, * ) is a semi-group  and '*' is distribut...

"A group (G,O) is said to be an abelian group or a commutative group if (a O b) = (b O a)    a, b ᗴ G . "  OR "A non-empty set 'G' together with a binary operation 'O' is said to be a group, if the following laws holds for all the operations 'O'." Group holds the following given five laws :    (a)  Clouser Law   :  'G' is cloused under the binary operation 'O' that is ( a O b ) = ( b O a )  ∀ a, b ᗴ G . (b)  Associative Law :  The associative law for the operation holds that is  a O ( b O c ) = ( a O b ) O c  ∀ a, b, c ᗴ G. (c)  Existence of Identity Element :  The identity element exists in 'G' that is there exists an element e  ᗴ  G such that a  ᗴ   e = e  ᗴ  a = a  ∀ a  ᗴ G. (d)  Existence of Inverse Element :  The inverse element of all the elements of 'G' exists that is for every a  ᗴ G there exists an element b  ᗴ G su...

Algebraic System or Algebraic Strucure " A non-empty set 'G' together with a binary operation ' O' is called an algebraic system or algebraic structure and is denoted by (G,O), (N,+).  " Group "A non-empty set 'G' together with a binary operation 'O' is said to be a group, if the following laws holds for all the operations 'O'." Group holds the following given four laws :    (a) Clouser Law   : 'G' is cloused under the binary operation 'O' that is ( a O b ) = ( b O a )  ∀ a, b ᗴ G . (b) Associative Law : The associative law for the operation holds that is  a O ( b O c ) = ( a O b ) O c  ∀ a, b, c ᗴ G. (c) Existence of Identity Element :  The identity element exists in 'G' that is there exists an element e  ᗴ  G such that a  ᗴ   e = e  ᗴ  a = a  ∀ a  ᗴ G. (d) Existence of Inverse Element :  The inverse element of all the elements of 'G' exists that is for every a  ᗴ...

" A Binary operation or Binary composition 'o' for a set 'A' is a rule by which every ordered pair (a,b) is associated with a uniquely determined element of 'A', where a ᗴ A and b  ᗴ A. " Thus a Binary operation 'O' on the set 'A' is a mapping from the set A X A to the set A  i.e. O : A X A ➜ A. Example :  1.  Ordinary Addition   (+)   : Ordinary Addition for real number (R) is a binary operation, because  (a + b) ᗴ  R ; where a ᗴ R and b ᗴ R. 2.  Ordinary Subtraction   (-)  : Ordinary Subtraction for real number is a binary operation over real number (R); but it is not a binary operation over natural number (N), because  2 ᗴ N , 3 ᗴ N  but ( 2-3 ) ∉ N. 3.  Ordinary Multiplication (*)  :Ordinary Multiplication for integers (Z) is a binary operation over the set of integers, but it is not a binary operation over the set of negative integers, because the product of two negative i...