Introductions :- When we send secret messagesthere are three types of participants. The sender, theintended recipient or receiver, and possibly the interceptor or `badguy’. The act of disguising your message is known as en-cryption, and theoriginal message is called the plaintext.
The encrypted plaintextis known as the ciphertext (or cryptogram), andthe act of turning the ciphertext back into original plaintext is description. Steganography is theact of physically hiding your message; in ancient times you might write yourmessage on the shell of a boiled egg using special ink that would soak throughthe porous outer shell. When the egg wascracked and peeled, your secret message would be found written on the eggwhite. In the 20th century, agents involved in espionage would usethe microdot, shrinking their entire message smaller than could be seen by thenaked eye. In comparison, ciphers work onthe level of the individual letters of your message. Ciphers may replace lettersin a message with other letters, or numbers, or symbols. For example, if `a’becomes 0, `b’ becomes 1, ‘c’ becomes 2and so on, then a word like `secret’ becomes `18 4 2 17 4 19′.
(Note, countingfrom `a’ as zero is a necessary convention that we will continue to use lateron). This provides a much greater exibility in our messages, and it will beciphers that we will be dealing with during this course Ciphers comes in two parts: The first part is the algorithm; this issimply the method of encryption. The second part is the key.
Theidea is these work together like a lock-and-key and, for the code breaker, havingone without the other is just half the problem. The key may change frequentlymeaning the greater the number of keys the more di_cult the cipher becomesbreak by brute force (an exhaustive check of all Possible Key ). Secretwriting has always been a constant struggle between the code maker and the codebreaker. Cryptography is the study of making secret messages,whereas cryptanalysis is the study of breaking those secretmessages. Cryptology is the collective name forboth cryptography and cryptanalysis; the word cryptology comingfrom the Greek words kryptos meaning hidden and logos meaningword. 1-1 The Caesar Shift:- The simplest possiblesubstitution cipher is the Caesar cipher , reportedly used by Julius Caesarduring the Gallic Wars. Each letter is shifted a fixed number of places to theright. (Caesar normally used a shift of three places).
We regard the alphabetas a cycle, so that the letter following Z is A. Thus, for example, the tablebelow shows a right shift of 5 places. 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 F G H I J K L M N O P Q R S T U V W X Y Z A B C D E The message “Send a hundredslaves as tribute to Rome” would be enciphered as Xjsi f mzsiwji xqfajx fxywngzyj yt Wtrj. The key is simply the number of places that the letters areshifted, and the cipher is decrypted by applying the shift in the opposite direction(five places back). Some practical details make thecipher harder to read.
In particular, it would be sensible to ignore thedistinction between capital and lower case letters, and also to ignore thespaces between words, breaking the text up into blocks of standard size, forexample XJSIF MZSIW JIXQF AJXFX YWNGZ YJYTW TRJXX (We have filled up the last blockwith padding.) The Caesar cipher is not difficult to break. There are only 26possible keys, and we can try them all.
In this case we would have XJSIF MZSIW JIXQF AJXFX YWNGZ YJYTW TRJXX YKTJG NATJX KJYRG BKYGY ZXOHA ZKZUX USKYYZLUKH OBUKY LKZSH CLZHZ AYPIB ALAVY VTLZZ……..SENDA HUNDR EDSLA VESAS TRIBU TETOR OMESS 1.
2 Modular Arithmetic :- Manycomplex cryptographic algorithms are actually based on fairly simple modulararithmetic. In modular arithmetic, the numbers we are dealing with are justintegers and the operations used are addition, subtraction, multiplication anddivision. The only difference between modular arithmetic and the arithmetic youlearned in school is that in modular arithmetic all operations are performedregarding a positive integer, i.e. the modulus.
Thedivision theorem tells us that for two integers a and b where b? 0, there always exists unique integers q and r suchthat a = qb + r and 0 ? r < |b|.For example: a = 17, b=3, we can find q =5 and r = 2 so that 17 = 3*5+2. a is calledthe dividend, b is called the divisor, q iscalled the quotient and r is called the remainder.
If r = 0, then we say b divides a or a is divisible by b.This establishes a natural congruence relation on the integers. For a positiveinteger n, two integers a and b aresaid to be congruent modulo n (or a iscongruent to b modulo n), if a and b havethe same remainder when divided by n (or equivalently if a? b is divisible by n ).
It can be expressed as a? b mod n. n is called the modulus. For example: Two odd numbers are congruent modulo 2 because all odd numbers can be written as 2n+1; Two even numbers are congruent modulo 2 because all even numbers can be written as 2n+0; 38 ? 23 mod 15 because 38 = 15*2 + 8 and 23 = 15 +8; -1 ? 1 mod 2 because -1 = -1*2+1 and 1 = 0*2+1; 8 ? 3 mod 5 because 8 = 5+3 and 3 = 0*5+3; -8 ? 2 mod 5 because -8 = -2*5+2 and 2 = 0*5+2; 8 ? -8 mod 5 because 8 = 5+3 and -8 = -2*5+2. The remainders 3 and 2 are not the same.Youneed to be careful with negative numbers.
They are usually not congruent totheir positive counter parts, as you can see in the above examples. Congruenceis an equivalence relation, if a and b arecongruent modulo n, then they have no difference in modulararithmetic under modulo n. Because of this, in modular n arithmeticwe usually use only n numbers 0, 1, 2, …, n-1.All the other numbers can be found congruent to one of the n numbers.
· to perform arithmeticoperations :-For addition, subtraction and multiplication,it is quite simple: calculate as in ordinary arithmetic and reduce the resultto the smallest positive reminder by dividing the modulus. For example: 12+9 ? 21 ? 1 mod 5 12-9 ? 3 mod 5 12+3 ? 15 ? 0 mod 5 15-23 ? -8 ? 2 mod 5 35*7 ? 245 ? 0 mod 5 -47*(5+1) ? -282 ? 3 mod 5 373 ? 50653 ? 3 mod 5 (exponentiation is just a shorthand for repeated multiplication)Sometimesthe calculation can be simplified because for any integer a1, b1, a2 andb2,if we know that a1 ? b1 mod n and a2 ?b2 mod n then the following always holds: a1+a2 ? b1+b2 mod n a1-a2 ? b1-b2 mod n a1*a2 ? b1*b2 mod nForexample, 35 ? 0 mod 5 therefore 35*7 ? 0*7 ? 0 mod 5. Also 37 ? 2 mod 5so 373 ? 23 ? 8 ? 3 mod 5.Butfor division That means that it is not always possible to performdivision in modular arithmetic. First of all, as in ordinary arithmetic,division by zero is not defined so 0 cannot be the divisor. The tricky bit isthat the multiples of the modulus are congruent to 0.
For example, 6, -6, 12,-12, …
are all congruent to 0 when the modulus is 6. So not only 4/0 is notallowed, 4/12 is also not allowed when the modulus is 6. Secondly, going backto the very basics: what does “division” mean in ordinary arithmetic?When we say 12 divided by 4 equals 3, we mean that there is a number 3 suchthat 3*4 = 12. So division is defined through multiplication. But you run intoproblems extending this to modular arithmetic.
let’s have a look at thefollowing table:Multiplication modulo 6 * 1 2 3 4 5 1 1 2 3 4 5 2 2 4 0 2 4 3 3 0 3 0 3 4 4 2 0 4 2 5 5 4 3 2 1 Supposeyou are working in mod 6 and want to compute 4/5. As we said before, youactually need to find x such that 5*x ? 4 mod 6.From the above table, we can find that 2 and only 2 satisfies this equation.That means 4/5 ? 2 mod 6.
Now suppose you want to compute 4/2 ? ? mod 6. Itseems easy because 2*2 ? 4 mod 6. However, there is another possibility: 2*5 ?4 mod 6. This time division is not uniquely defined, because there are twonumbers that can multiply by 2 to give 4. In such cases, division is notallowed.Thenwhen modular division is defined? When the multiplicative inverse (orjust inverse) of the divisor exists. The inverse of an integer a undermodulus n is an integer b such that a*b ?1 mod n.
An integer can have either one or no inverse. The inverseof a can be another integer or a itself. Inthe above table, we can see that 1 has an inverse, which is itself and 5 alsohas an inverse which is also itself. But 2, 3 and 4 do not have inverses.
Whether an integer has the inverse or not depends on the integer itself andalso the modulus. Compare the follwing table to table 1:Multiplication modulo 5 * 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1 Youcan see that when the modulus is 6, 2 has no inverse. But when the modulus is5, the inverse of 2 is 3. The rule is that the inverse of an integer aexistsiff a and the modulus n are coprime.That is, the only positive integer which divides both a and n is1. In particular, when n is prime, then everyinteger except 0 and the multiples of n is coprime to n,so every number except 0 has a corresponding inverse under modulo n.You can verify this rule with table 1 and 2.
Sometimesit is easy to determine whether two integers are coprime. But most of the timeit is not easy. For example, are 357 and 63 coprime? You may not be able toanswer immediately. Fortunately, we can use the Euclidean algorithm tofind out. The Euclidean algorithm describes how to find what is calledthe greatest common divisor (gcd) of two positive integers. Ofcourse, if the gcd of two integers is 1, they are coprime. Let me show you byan example.Westart with two positive integers 357 and 63.
The first step of theEuclidean algorithm is to divide the bigger integer by the smaller one, sowe have: 357÷63, quotient = 5 remainder = 42Then dividethe divisor in last step by the remainder: 63÷42, quotient =1 remainder=21Continueto divide the previous divisors by the remainders, until the remainder is 0: 42÷21, quotient =2 remainder =0Thedivisor in the last step is the gcd of the two input integers. To see why the algorithm works, we follow thedivision steps backwards. From the last step, we know that 21 divides 42. Inthe step before, we have 63 = 1*42 +21. Because 21 divides both 42 and 21, itmust also divide 63.
In the first step, we have 357 = 5*63 +42, again 21divides both 63 and 42 so it must also divide 357. Since 21 divides both 63 and357, it is indeed a common divisor of those two integers. Now we need to provethat it is the greatest.
The proof is based on a theorem which says: For any non-negative integers a and b, and any integers x and y, c = x*a + y*b must be a multiple of the gcd of a and b.Whatwe want to show is that 21 =x*357 + y*63 for some x and y. If this is true,then 21 must be the gcd (why? Figuring this out is left to you as an exercise).Now let’s start: From step 1, we have 357-5*63=42 From step 2. we have 63-42=21 Substitutes 42 with 357 -5*63, now we have 21 = 63-357+5*63 = -1*357+6*63Sothe Euclidean algorithm indeed outputs the gcd. If the gcd is 1, we canconclude a and b are coprime.
Knowingthat an integer a and a modulus n are coprimeis not enough. How can we find the multiplicative inverse of a?Well, since the gcd of a and n is 1, we knowwe can find a pair (x,y) such that 1 = x*a+y*n.Then x*a = -y*n+1. That means x*a ? 1mod n, in other words, x is the multiplicativeinverse of a under modulo n. This can be done byrunning an extended version of Euclidean algorithm which tracks x whencomputing the gcd.
In the extended Euclidean algorithm, we firstinitialise x1 =0 and x2 =1, then inthe following steps, compute xi = xi-2 -xi-1qi-2 where qi-2 isthe quotient computed in stepi-2. When the remainder becomes 0, continuethe calculation of x for one more round. The final x is theinverse. Here is an example that shows how to find the inverse of 15 when themodulus is 26: step 1: 26÷15, quotient q1= 1, remainder = 11, x1 = 0 step 2: 15÷11, quotient q2 = 1, remainder = 4, x2 = 1 step 3: 11÷4, quotient q3 = 2, remainder = 3, x3 = x1-x2q1 = 0- 1*1 = -1 step 4: 4÷3, quotient q4 = 1, remainder = 1, x4 = x2-x3q2 = 1- (-1)*1 = 2 step 5: 3÷1, quotient q5 = 3, remainder = 0, x5 = x3-x4q3 = -1- 2*2 = -5 step 6: x6 = x4-x5q4 = 2- (-5)*1 = 7Toverify, 15*7 = 105 = 4*26+1, so 15*7 ? 1 mod 26, which means 7 is themultiplicative inverse of 15 under modulo 26.