Scribd
Upload
16 views24 pages

Lecture 1

Ffhmfg. Hhh. H. Gg.

Uploaded by

hakizimana evariste
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
16 views24 pages

Lecture 1

Ffhmfg. Hhh. H. Gg.

Uploaded by

hakizimana evariste
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
CHAPTER I: INTRODUCTION TO CRYPTOGRAPHY 1.1. HISTORY OF CRYPTOGRAPHY ‘Computer data often travels from one computer to another, leaving the safety of its protected physical surroundings. Once the data is out of hand, people with bad intention could modify or forge your data, either for amusement or for their own benefit. Cryptography can reformat and transform our data, making it safer on its trip between computers. The technology is based on the essentials of secret codes, augmented by moder mathematies that protects our data in powerful ways. Cryptography is a subject that has been studied and applied since ancient Roman times, and research into better encryption methods continues to this day. Cryptography is the art of encoding and decoding messages so that messages can be securely transmitted from a sender to a receiver without fear of an outside party intercepting and reading or altering the message's contents, During the Middle Ages, cryptography started to progress. All of the Westem European governments used cryptography in one form or another, and codes started to become more popular. Ciphers were commonly used to keep in touch with ambassadors, The first major advances in cryptography were made in Italy. Venice created an elaborate organization in 1452 with the sole purpose of dealing with cryptography. They had three cipher secretaries who solved and created ciphers that were used by the government. The next major step was taken in 1518, by Trithemius, a German monk who had a deep interest in the occult. He wrote a series of six books called 'Polygraphia', and in the fifth book, devised a table that repeated the alphabet with each row a duplicate of the one above it, shifted over one letter. In 1553, Giovan Batista Belaso extended this technique by choosing a keyword that is written above the plaintext, in a letter to letter comespondence. The keyword is restarted at the beginning of each new plaintext word. The most famous cryptographer of the 16th century was Blaise de Vigenere (1523-1596). In 1585, he wrote "Tracte des Chiflres' in which he used a Trithemius table, but changed the way the key system worked, One of his techniques used the plaintext as i's own key. In 1628, a Frenchman named Antoine Rossignol helped his army defeat the Huguenots by decoding a captured message. After this victory, he was called upon many times to solve ciphers for the French government. He used two lists to solve his ciphers: "one in which the plain elements were in alphabetical order and the code elements randomized, and one to facilitate decoding in which the le elements stood in alphabetical or numerical order while their plain equivalents were disarranged." When Rossignol died in 1682, his son, and later his grandson, continued his work, By this time, there were many cryptographers employed by the French government. Together, they formed the "Cabinet Noit" (the "Black Chamber"). By the 1700's, "Black Chambers" were common in Europe, one of the most renown being that in Vienna, It was called ‘The Geheime Kabinets-Kanzlei and was directed by Baron Ignaz de Koch between 1749 and 1763. In 1817, Colonel Decius Wadsworth developed a set of two disks, one inside the other, where the outer disk had the 26 letters of the alphabet, and the numbers 2-8, and the inner disk had only the 26 letters. The disks were geared together at a ratio of 26:33. In 1844, the development of cryplography was dramatically altered by the invention of the telegraph. The 'Playfair! system, was invented by Charles Wheatstone and Lyon Playfair in 1854, and was the first system that used pairs of symbols for encryption, In 1859, Pliny Earle Chase, developed what is known as the fractionating or tomographic cipher. A two digit number was assigned to each character of plaintext by means of a table, Kasiski developed a cryptanalysis method in 1863 which broke almost every existing cipher of that time. The method was to find repetitions of strings of characters in the ciphertext. During the Civil War (1861-1865), ciphers were not very complex. Many techniques consisted merely of writing words in a different order and substituting code words for proper names and locations. In 1883, Auguste Kerckhofls wrote 'La Cryptographie Militaire’ in which he set forth six basic requirements of cryptography. We note that the easily remembered key is very amenable to attack, and that these rules, as all others, should be questioned before placing trust in them, In 1917, the Americans formed the cryptographic organization MI-8. It's director was Herbert Osbome Yardley. In 1929, Lester S. Hill published an article "Cryptography in an Algebraic Alphabet” in "The American Mathematical Monthly”. Fach phintext letter was given a numerical value. He then used polynomial equations to encipher plaintext, with values over 25 reduced modulo 26. In 1948, Shannon published "A Communications Theory of Secrecy Systems" . Shannon was one of the first moder cryptographers to attribute advanced mathematical techniques to the science of ciphers. 1.2, CRYPTOGRAPHY CONCEPTS Cryptography Cryptography refers to the art of protecting transmitted information from unauthorized Interception or tampering Cryptography is an interdisciplinary subject, Y Linguistics Y Mathematics: number theory, information theory, comput Y engineering nal complexity and statisties Network Security It refers to any activity designed to protect the usability and integrity of your network and data, It includes both hardware and software technologies ‘Computer Security - generic name for the collection of tools designed to protect data and to thwart hackers Internet Securit - measures to protect data during their transmission over a collection of interconnected networks Cryptanalysis The art and science of decrypting messages without knowing the key. Cryptology Itis the scientific study of cryptography and cryptanalysis Plaintext Itis an information a sender wishes to transmit to a receiver Intruder Itis a person who is not authorized to access on information Ciphertext Encoded message Plaintext Ciphertest Ciphertext Plaintext Alice Bob Cipher Ciphertext Eve An algorithm for transforming an intelligible message into one that is unintelligible by transposition and/or substitution methods. Encryption tis a process of changing plaintext into ciphertext, Decryption Itis a process of changing ciphertext into plaintext, Key Itis a secret information which is used to transform ciphertext to plaintext and vice versa. Notation for relating the plaintext, ciphertext, and the keys 'K(P) denotes that C is the encryption of the pla intext P using the key K 1K (C) denotes that P is the decryption of the ciphertext C using the key K ‘Then DK(EK(P))=P Stream cipher It operates on a single bit(byte or computer word) at a time Block cipher It encrypts one block of data at a time using the same key on each block. Cryptosystem 4 cryptosystem is a five-tuple (P+C,K,€,D) where the following conditions are satisfied: 1. Pisa finite set of possible plaintexts 2. C isa finite set of possible ciphertexts 3. K, the keyspace, isa finite set of possible keys 4. For each KK € KC, there xem encryption rte, © € and a corresponding decryption ral dic ED. roche ? P 4 Canaduc : C > P ave functions such that d,fe,(s)) =x for every planet t & P. Steganography Steganography is defined as "hiding information within a noise; a way to supplement (not replace) eneryption, to prevent the existence of encrypted data from being detected’, ‘Threat A potential for violation of security, which exists when there is a citeumstance, capability, action, or event that could breach security and cause harm. That is, a threat is a possible danger that might exploit vulnerability. Attack An assault on system security that derives from an intelligent threat that is an intelligent act that is a deliberate attempt (especially in the sense of a method or technique) to evade security services and violate the security policy of a system. Security Itis to make sure that nosy people camnot read or secretly modify messages intended for other recipients 1,3. SECURITY ATTACKS Attacks can be split into two wide groups: passive attacks and active attacks. A passive attack attempts to learn or make use of information from the system but does not affect system resources. An active attack attempts to aker system resources or affect their operation, Passive Attacks Passive attacks are in the nature of eavesdropping on, or monitoring of, transmissions. The goal of the opponent is to obtain information that is being transmitted. Two types of passive attacks are release of message contents and traffic analysis. Y The release of message contents is easily understood. A telephone conversation, an electroni¢ mail message, and a transferred file may contain sensitive or confidential information, We would like to prevent an opponent from learning the contents of these transmissions. Y A second type of passive attack, traffic analysis, is subtler. Suppose that we had a way of masking the contents of messages or other information traffic so that opponents, even if they captured the message, could not extract the information from the message. The common technique for masking contents is encryption. Passive attacks are very difficult to detect because they do not involve any alteration of the data. Typically, the message traffic is sent and received in an apparently normal fashion and neither the sender nor receiver is aware that a third party has read the messages or observed the traffic pattem, However, it is feasible to prevent the success of these attacks, usually by means of ceneryption. Thus, the emphasis in dealing with passive attacks is on prevention rather than detection. Active Attacks Active attacks involve some modification of the data stream or the creation of a false stream. An attack can take place on any of the communications links. For active attacks, the attacker needs to gain physical control of a portion of the link and be able to insert and capture transmissions. For a passive attack, the attacker merely needs to be able to observe transmissions. The communications links involved can be cable (telephone twisted pair, coaxial cable, or optical fiber), microwave links, or satellite channels, The active attacks can be subdivided imto four categories: masquerade, replay, modification of messages, and denial of service. ‘A masquerade takes place when one entity pretends to be a different entity. Replay involves the passive capture of a data unit and its subsequent retransmission to produce an unauthorized effect. Modification of messages simply means that some portion of a legitimate message is altered, or that messages are delayed or reordered, to produce an unauthorized effect. > The denial of service prevents or inhibits the normal use or management of communications facilities. This attack may have a specific target; for example, an entity may suppress all messages directed to a particular destination (e.g., the security audit service). Another form of service denial is the disruption of an entire network, either by disabling the network or by overloading it with messages so as to degrade performance vv v Active attacks present the opposite characteristics of passive attacks. Whereas passive attacks are difficult to detect, measures are available to prevent their success. On the other hand, itis quite difficult to prevent active attacks absolutely, because to do so would require physical protection of all communications facilities and paths at all times. Instead, the goal is to detect them and to recover from any disruption or delays caused by them. Because the detection has a deterrent effect, it may also contribute to prevention. 1.4. SECURITY SERVICES There are security services to prevent security attacks — authentication, data confidentiality, data integrity, non- repudiation and access control Authentication Verifying that a user, computer, or service (such as an application provided on a network server) is the entity that it claims to be, Authentication is an important part of identity ‘management, Users, computer network or, after logon, when they authenticate to a network service, are known collectively as principals, security principals, or digital idemtitics. , and services that can be authenticated when they log on to a Data confidentiality Confidentiality, keeping information secret from unauthorized access, is probably the most common aspect of information security: we need to protect confidential information. An organization needs to guard against those malicious actions that endanger the confidentia lity of its information. Data integrity Information needs to be changed constantly. In a bank, when a customer deposits or withdraws money, the bakince of their account needs to be changed, Inte grity means that changes should be done only by authorized users and through authorized mechanisms, Non- repudiation No repudiation prevents either sender or receiver from denying a transmitted message. Thus, when a message is sent, the receiver can prove that the alleged sender in fact sent the message. Similarly, when a message is received, the sender can prove that the alleged receiver in fact received the message. Access Control In the context of network security, access control is the ability to limit and control the access to host systems and applications via communications links. To achieve this, each entity trying to gain access must first be identified, or authenticated, so that access rights can be tailored to the individual. Availability Requires that computer system assets be available to authorized parties when needed. LS. TRADITIONAL CRYPTOGRAPHY ‘The fimdamental objective of cryptography is to enable two people, usually referred to as Alice and Bob, to communicate over an insecure channel in such a way that an opponent, Oscar, cannot understand what is being said. This channe| could be a telephone line or computer network, for example. The information that Alice wants to send to Bob, which we call —plaintext,! can be English text, numerical data, or anything at all — its structure is completely arbitrary. Alice encrypts the plaintext, using a predetermined key, and sends the resulting ciphertext over the channel, Oscar, upon seeing the ciphertext in the channel by eavesdropping, cannot determine what the plaintext was; but Bob, who knows the encryption key, can decrypt the ciphertext and reconstruct the plintext. Cryptographic systems are generically classified along three independent dimensions 1. The type of operations used for transforming plaintext to ciphertext. All encryption algorithms are based on two general principles: substitution, in which each element in the plaintext (bit, letter, group of bits or letters) is mapped into another element, and transposition, in which elements in the plaintext are rearranged. The fundamental requirement is that no information be lost (that is, that all operations be reversible). Most systems, referred to as product systems, involve multiple stages of substitutions and transpositions. the number of keys used. If both sender and receiver use the same key, the system is referred to as symmetric, single-key, seeret-key, or conventional encryption. Examples are the Data Encryption Standard (DES) and the Advanced Eneryption Standard (AES). If the sender and receiver each use a different key, the system is referred to as asymmetric, two-key, or public-key eneryption, In public key cryptology each party, actually, has a key that consists of two parts, a public and a secret (or private) part. The public part can be used to encrypt information, the corresponding secret part to decrypt. Alternatively, the secret key is used to sign a document, the corresponding public key to verify the resulting signature. Furthermore, a widely shared public key can be used to establish a common secret among two parties, for instance a key for a symmetric system. Examples of public key cryptosystems are the Diffie-Hellman key agreement protocol and the El-Gamal and RSA encryption and signature schemes. 3. The way in which the plaintext is processed. A block cipher processes the input one block of elements at a time, producing an output block for each input block. A stream cipher processes the input elements continuously, producing output one element at a time, as it goes along, The two basic building blocks of all encryption techniques are: > substitution and > transposition Transposition ‘The order of the letters in the plaintext is rearranged in some systematic way. The key is the permutation applied to the positions. Substitution Individual letters are replaced by different letters in a systematic way. This may be more complicated than just a single permutation; we may apply different permutations to the letters in different positions. The key is the sequence of applied permutations. 1.5.1. SUBSTITUTION TECHNIQUES Ls 1. Shift Cipher ‘The easiest known use of a substitution cipher and the simplest was by Julius Caesar. The Caesar cipher involves replacing each leter of the alphabet with the letter standing 3 places ‘ther down the alphabet 2. plain text: pay more money Cipher text: SDB PRUH PRQHB ‘Note thatthe alphabet is wrapped around, so that letter following 2" is a For each plaintext letter p, substiute the eipher text Ietere such that C= E(p) = (p+3) mod 26 A shift may be any amount, so that general Caesar algorithi is C=E()= (pH) mod 26 ‘Where k takep on a value in the range 1 to 25. The decryption algorithm is simply P=D(C)=(C-k) mod 26 Example: Plaintext: abe de [Link] w Ciphertext:. DEF GH... ZABC We call this a SHIFT CIPHER with shift (or key) 3 Let us assign a numerical equivalent to each letter: ABCDEFGHIJKLM 0123456789 ni NOpqRSTUVWXyZ 13 1415 16 17 18 19 20 21 222324 25 Exercise Suppose the key for a Shift Cipher is K'= 1, and the plaintext is we will meet at midnight. Find its ciphertext. Brute Force Attack A brute force attack is any type of attack that involves trying every possible combination of characters or data in order to find the key in order to decrypt an encrypted message. A brute force guarantees finding the key — it’s trying every possible combination and does not rely on. any potentially incomplete dictionaries or lists of possible keys. By definition, trying every possible value will result in finding the key. Unfortunately, Caesar ciphers have a small key space, and messages enerypted with Caesar ciphers can be easily broken by brute force if itis recognized that the message has been encrypted with a Caesar cipher. How many distinct Caesar ciphers are possible? Well, a shift of 0 would not make any sense; we would still have plaintext. Shifts of 1, 2, 3, ... 25 make sense. But, a shift of 26 would (because the alphabet returns to the beginning) be the same as a shift of 0, Similarly, a shift of 27 is the same as a shift of 1, a shift of 28 is the same as a shift of 2, ete. So, there are only 26 possible Caesar ciphers, and one of those is a shift of 0 which would provide no encryption at all Because of the small number of possible keys, a brute force attack is possible — we could try all possible keys and see which one yields plaintext. Here is a brute force ciphertext attack on a Caesar cipher. The following message is known to have been enerypted with a Caesar cipher: RZXFSEJ KEY PLAINTEXT 0 RZXFSE} 1 QYWERDI 2 PXVDQCH 3 OWUCPBG 4 NVTBOAF 5 MUSANZE, Frequency Analy: Frequency analysis is the study of letters or groups of letters contained in a ciphertext in an attempt to partially reveal the message, The English language (as well as most other languages) have certain letters and groups of letters appear in varying frequencies. This is a chart of the frequency distribution of letters in the English alphabet. As you can see, the letter ‘e’ is the most common, followed by ‘t’ and ‘a’, with *?, “q’, *x’, and ‘2’ being very uncommon. 0.14 0.02 abedetaghijkimnoparstuyvwxy2 Knowing the usual frequencies of letters in English communication, if the eneryption method does not effectively mask these frequencies it is possible to statistically determine parts of the plaintext from looking at the ciphertext alone. Let’s look at an example based on a plaintext encrypted with the Caesar Cipher — a cipher that provides no protection from frequency analysis. KBKXEUTK Let's break this down into some numbers we can work with. Let's get the letter frequencies (how often each letter appears) of this ciphertext. K:3, Bil, X:1, El U:LTs1 Okay, so we've found our frequencies. The first reaction here is to try K ~e, as the most common letter in the english alphabet and therefore our ciphertext is e. Since we know the cipher used is the Caesar cipher we know the letter shift from K to ¢ is 6, so we can try a shift of -6 and wwe have the key to deserypt the message Phintext is EVERYONE 1s. Atbash cipher The Atbash cipher is a substitution cipher with a specific key where the letters of the alphabet are reversed. Le. all 'A's are replaced with 'Z's, all 'B's are replaced with "Y's, and so on. It was originallly used for the Hebrew alphabet, but can be used for any alphabet The Atbash cipher is essentially a substitution cipher with a fixed key, if you know the cipher is Atbash, then no additional information is needed to decrypt the message. The substitution key is: ABCDEFGHIKLMNOPQRSTUVWXYZ ZYXWVUTSRQPONMLK JIHGFEDCBA [Link]. Playfair Cipher ‘The best known multiple letter encryption cipher is the playfair, which treats digrams in the plaintext as single units and translates these units into cipher text digrams. The playfair algorithm is based on the use of 5x5 matrix of letters constructed using a keyword. Let the keyword be ,monarchy". The matrix is constructed by filling in the letters of the keyword (minus duplicates) from left to right and from top to bottom, and then filling in the remainder of the matrix with the remaining letters in alphabetical order. The letter ,," and ,,/" count as one letter. Plaintext is encrypted two letters at a time According to the following rules: Repeating plaintext letters that would fall in the same pair are separated with a Filler letter such as ,x" Plaintext letters that fall in the same row of the matrix are each replaced by the letter to the right, with the first clement of the row following the last Plaintext letters that fall in the same column are replaced by the letter beneath, with the top element of the column following the last. Otherwise, each plaintext letter is replaced by the letter that lies in its own row And the column occupied by the other plaintext letter. M o N a R c TT Y B D E F G TT K TC P g 5 T U v W x Z Example Using "playfair example" as the key, the table becomes: P L A Y 1 R E x M B c D G H K N 0 Q S T U V W Z Plaintext = meet me at the school house Splitting two letters as a unit => me et me at th es ch 0 x ol ho us ex Corresponding cipher text => CL KL CL RS PD IL HY AV MP HF XL TU Strength of playfair cipher Playfair cipher is a great advance over simple mono alphabetic ciphers. Since there are 26 letters, 26x26 = 676 diagrams are possible, so identification of individual diagram is more difficult. 15.1.4. The Vigenére cipher Blaise de Vigenére, a French diplomat (born in 1523) first perfected the cipher we are about to consider. In 1586 he published his Treatise on Secret Writing (Traieté de Chiffies), but his work received little attention for two centuries. In 1854, Charles Babbage (born 1791) found a way of breaking the cipher (as did, independently, Friedrich Kasiki, in 1863), This cipher is well known because while it is easy to understand and implement, it often appears to beginners to be unbreakable; this eared it the moniker le chiffre indéchiffrable (French for ‘the unbreakable cipher’). Consequently, many people have tried to implement obfuscation or 1s, only to have them broken. encryption schemes that are essentially Vigenére ci ‘The Algorithm ‘The ‘key’ for a vigenere cipher is a key word. e.g. ‘FORTIFICATION’ ‘The Vigenere Cipher uses the following tableau (the ‘tabula recta’) to encipher the plaintext 3 The Modern Vigenére Tableau Table \p EH vite nexen seen seen ee>nsxrN exeNpxmnBKeNeuensurneurnexrNBunNe sJenvomsoz--uszz0ecuarae Buen To encipher a message, repeat the keyword above the plaintext: FORTIFICATIONFORTEFICATIONFO DEFENOTHEEASTHALLOFTHECASTLE Now we take the letter we will be encoding, 'D', and find it on the first column on the tableau. Then, we move along the 'D' row of the tableau until we come to the column with the 'F' at the top (The 'F' is the keyword letter for the first 'D’), the intersection is our ciphertext character, '. So, the ciphertext for the above plaintext is: FORTIFICATIONFORTIFICATIONFO DEFENDTHEEASTHALLOFTHECASTLE ‘TSNXVIB1EXIGGBOCEWKBIEVIGGOS To decrypt, pick a letter in the ciphertext and its corresponding letter in the keyword, use the keyword letter to find the corresponding row, and the letter heading of the column that contains the ciphertext letter is the needed plaintext letter, For example, to decrypt the first letter I in the ciphertext, we find the corresponding letter F in the keyword, Then, the row of F is used to find the corresponding letter I and the column that contains I provides the plaintext letter D (see the above figures). Example: For example, suppose that the plaintext to be encrypted is: ATTACKATDAWN ‘The person sending the message chooses a keyword and repeats it until it matches the length of the plaintext, for example, the keyword "LEMON" The first letter of the plaintext, A, is enciphered using the alphabet in row L, which is the first letter of the key. This is done by looking at the letter in row L and column A of the Vigenére square, namely L. Similarly, for the second letter of the plaintext, the second letter of the key is the letter at row E and column T is X. The rest of the plaintext is enciphered in a similar uses fashion: Plaintext ATTACKATDAWN Key: LEMONLEMONLE Ciphertext LXFOPVEFRNAR Decryption is performed by finding the position of the ciphertext letter in a row of the table, and then taking the label of the column in which it appears as the plaintext, For example, in row L, the ciphertext L appears in column A, which taken as the first plaintext letter. The second letter is decrypted by looking up X in row E of the tab plaintext letter. appears in column T, which is taken as the Vigenére can also be viewed algebraically. If the letters A-Z are taken to be the numbers 0-25, and addition is performed modulo 26, then Vigenére encryption can be written, CS(RAK:) mod 26 and decryption, (G-K) me 26 Strength and Limitation of Vigentre cipher ‘The Vigenére cipher is effective because it masks the characteristic letter frequencies of English plaintexts, but some patterns remain, The strength behind the Vigenére cipher is, like all polyalphabetic ciphers, to. make frequency analysis more difficult. Frequency analysis is the practice of decrypting a message by counting the frequency of ciphertext letters, and equating it to the letter frequency of normal text For instance if P occurred most in a ciphertext whose plaintext is in English one could suspect that P corresponded to E, because E is the most frequently used letter in English. Using the Vigenére cipher, E can be enciphered as any of several letters in the alphabet at different points in the message thus defeating simple frequency analysis. ‘The critical weakness in the Vigenére cipher is the relatively short and repeated nature of its key. If a eryptanalyst discovers the key’s length then the cipher text can be treated as a series of different Caesar ciphers, which individually are trivially broken. The Kasiski and Friedman tests help determine a ciphertext’s key length. Substitution in modern eryptography Substitution ciphers as discussed above, especially the older pencil-and-paper hand ciphers, are no longer in serious use. However, the cryptographic concept of substitution carries on even today. From a sufficiently abstract perspective, modem bit-oriented block ciphers (eg, DES, ot AES) can be viewed as substitution ciphers on an enormously large binary alphabet. In addition, block ciphers often include smaller substitution tables called S-boxes. 1.5.2. TRANSPOSITION TECHNIQUES All the techniques examined so far involve the substitution of a ciphertext symbol for a plaintext symbol. A very different kind of mapping is achieved by performing some sort of permutation on the plaintext letters. This technique is referred to as a transposition cipher. [Link]. RAIL FENCE CIPHER The simplest such cipher is the rail fence technique, in which the plaintext is written down as a sequence of diagonals and then read off as a sequence of rows. For example, to encipher the message —meet me after the toga party! with a rail fence of depth 2, we write the following: mematrhtgpry etefeteoaat The enerypted message is MEMATRHTGPRYETEFETEOAAT [Link]. COLUMNAR TRANSPOSITION CIPHER This sort of thing would be trivial to cryptanalyze. A more complex scheme is to write the message in a rectangle, row by row, and read the message off, column by column, but permute the order of the columns. The order of the columns then becomes the key to the algorithm. For example, Key: 4312567 Phintext; attack p ostpone duntilt woamx yz Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ A pure transposition cipher is easily recognized because it has the same letter frequencies as the original plaintext. For the type of columnar transposition just shown, cryptanalysis is fairly straightforward and involves laying out the ciphertext in a matrix and playing around with column positions. Digram and trigram frequency tables can be useful. The transposition cipher can be made significantly more secure by performing more than one stage of transposition. The result is a more complex permutation that is not easily reconstructed. Thus, if the foregoing message is re-encrypted using the same algorithm, Key 43 Input: tt 1 naapt mtswoao dwecixk niypet z Output: NSCYAUOPTTWLTMDNAOIEPAXTTOKZ To visualize the result of this double transposition, designate the letters in the original plaintext message by the mumbers designating their position. Thus, with 28 letters in the message. the original sequence of letters is 01 02 03 04 05.06 07 08 09 10 11 12 13 14 15 16 17 18 19 20.21 22 After the first transposition we have 03 10 17 24 04 11 18 25 02 09 16 23 01 08 15 22 05 12 19 26 06 13 20 2707 142128, which has a somewhat regular structure. But after the second transposition, we have 17 09.05 27 24 16 12.07 10 02 2220 03 25 15 13 0423 19 1411 01 2621 18 08 06 28 This is a much less structured permutation and is much more difficult to cryptanalyze. 1.53 HILL CIPHER + Invented by L. 8. Hill in 1929. + Inputs : String of English letters, A.B,....Z. An nxn matrix K, with entries drawn from 0,1,....25. (The matrix K serves as the secret key. ) * Divide the input string into blocks of size n. + Identify A=0, BI, C=2, ..., Z=25 + Encryption: Multiply each block by K and then reduce mod 26. * Decryption: multiply each block by the inverse of K, and reduce mod 26, + The decryption must be the inverse function of the eneryption function. + Itis required that K K =I, mod 26. How to compute K” 2 Compute det(K) © Check if ged(det(K), 26) =1 o If not, then K"! do not exist 9 Else K™ is (- "x, (- yew nd lan p- ia (-1) Ki, 2 cy K Example Using Hill cipher, encrypt Hello world if the key is, 241 Let A 4 304 Solution Message to encrypt = HELLO WORLD 4 ea aq 38 4 3 a osq 38 3 i St —_ =F 2 E § Soa OO OO = tt 5 g 8 g oe § 44 SN at BU NK z se — — ao z 8 2 3 g a a # © & z aS roe ee = = zZ & on to 8 wo On oe 2 b 3 ° &5 8k S243 7 te ge zoo a nr — — 8 HELLO WORLD has beenenerypted to SLHZY ATGZT. Find A-l 241 Let A [ 3 4 DetA=8-3=5 modular inverse of 5 for Mod 26 = 21 4-1 84-21 = ai| 4 2 | | % 2 | et 21] ,, 6 5 8 [ 3a 42 ] Moa as 4 c| Multiply Matrix by Vectors 6 5 18 108 + 55. 163 we 16 | * | 1 2704176 446 6 5 z 42+ 125 167 1s 16 | * | 25 105 4+ 400 BOS 6 5 2a 14440 aaa 1s 16 | * | o 36040 360 6 5 19 414430 aaa is i | * | 6 285 + 9G 381 6 5 23 150495 245 as 16} * | 19 B75 + 304 679 Convert to Mod 26 [ ae ] Mod 26 [ zi [28% ] soa 2s — [13 [Bg ]rwase- [48 [ 22¢ ] wea 20 = [22] [ 33 ] moa 26 [Ss] [2]-[#] [#1-. [#]-[#] (1-1 [3 1-(4] SLHZYATGZT has been decrypted to HELLO WORLD. Exercises 1. We use the Hill Cipher with P=C=Z26 and key [** J (a) Compute the encryption of June (b) Compute the decryption of ciphertext (6.7) 2. 1 Construct the Playfair matrix (5x5) using the keyword: Cryptography i) Encrypt the following words using the above matrix, ‘Telecommunication, football 3. Using Vigenere cipher. decrypt “VPXZTIQKTZWICVPS WFDMTETIGAHLH” if “cipher” is a key. [Link] cipher using frequency analysis. Decrypt the following i, *kbkxeutk” ii, “espntaspeskdmppymezvpy” [Link] Hill cipher, decrypt “LNSHDLEWMTRW” if the key is 17 17 5 = 2a As 2a z 2 19 6, Using frequency analysis, deerypt WKH SDVVZRUG LV VHYHQ GROW WHOO DQBRQH

You might also like