WWW.THESIS.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Thesis, documentation, books
 
<< HOME
CONTACTS



Pages:   || 2 |

«The University of Sydney Math3024 Elementary Cryptography and Protocols Introduction to Cryptography Cryptography is the study of mathematical ...»

-- [ Page 1 ] --

1

Introduction

The University of Sydney

Math3024 Elementary Cryptography and Protocols

Introduction to Cryptography

Cryptography is the study of mathematical techniques for all aspects of information

security. Cryptanalysis is the complementary science concerned with the methods to

defeat these techniques. Cryptology is the study of cryptography and cryptanaylsis. The

security of information encompasses the following aspects:

• confidentiality or privacy,

• data integrity,

• authentication,

• nonrepudiation.

Each of these aspects of message security can addressed by standard methods in cryptography. Besides exchange of messages, tools from cryptography can be applied to sharing an access key between multiple parties so that no one person can gain access to a vault by any two of them can. Another role is in the design of electronic forms of cash.

Definitions and Terminology Encryption = the process of disguising a message so as to hide the information it contains;

this process can include both encoding and enciphering (see definitions below).

Protocol = an algorithm, defined by a sequence of steps, precisely specifying the actions of multiple parties in order to achieve an objective.

Plaintext = the message to be transmitted or stored.

Ciphertext = the disguised message.

Alphabet = a collection of symbols, also referred to as characters.

Character = an element of an alphabet.

Bit = a character 0 or 1 of the binary alphabet.

String = a finite sequence of characters in some alphabet.

Example. The following are some standard alphabets.

2 Elementary Cryptography A,..., Z 26 symbols MSDOS (less punctuation) ASCII 7-bit words (128 symbols) American standard extended 8-bit words (256 symbols) ISO-8859-1 8-bit words (256 symbols) European standard Binary {0,1} Numerical alphabet base 2 Octal {0,...,7} Numerical alphabet base 8 Decimal {0,...,9} Numerical alphabet base 10 Hexadecimal {0,...,9,a,b,c,d,e,f} Numerical alphabet base 16 Encode = to convert a message into a representation in a standard alphabet, such as to the alphabet {A,..., Z} or to numerical alphabet.

Decode = to convert the encoded message back to its original alphabet and original form — the term plaintext will apply to either the original or the encoded form. The process of encoding a message is not an obscure process, and the result that we get can be considered equivalent to the plaintext message.

Cipher = a map from a space of plaintext to a space of ciphertext.

Encipher = to convert plaintext into ciphertext.

Decipher = to convert ciphertext back to plaintext.

Stream cipher = a cipher which acts on the plaintext one symbol at a time.

Block cipher = a cipher which acts on the plaintext in blocks of symbols.

Substitution cipher = a stream cipher which acts on the plaintext by making a substitution of the characters with elements of a new alphabet or by a permutation of the characters in the plaintext alphabet.

Transposition cipher = a block cipher which acts on the plaintext by permuting the positions of the characters in the plaintext.

–  –  –

where M is a subset of A∗, C is a subset of A′∗, and K and K′ are sets which are generally strings of fixed finite length over some alphabets (e.g. An or A′n ). A cryptosystem or encryption scheme is a pair (E, D) of maps

–  –  –

for all M in M. We write EK for the map E(K, ·) : M → C and similarly write DK ′ for D(K ′, ·) : C → M. With this notation the condition on E, D, K and K ′ is that DK ′ ◦ EK is the identity map on M.

We will refer to EK as a cipher, and note that a cipher is necessarily injective. For many cryptosystems, there will exist a unique inverse ciphertext key K ′ associated to each plaintext key K. A cryptosystem for which the inverse key K ′ is K itself (hence K = K′ ) is said to be symmetric. If the inverse key K ′ associated to K is neither K itself nor easily computable function of K, then we say that the cryptosystem is asymmetric or a public key cryptosystem.

A fundamental principle of cryptography is that the security of a cipher EK (i.e. the difficulty in finding DK ′ ) does not rest on the lack of knowledge of the cryptosystem (E, D). Instead, security should be based on the secrecy of K ′.

Recall that a (cryptographic) protocol is an algorithm, defined by a sequence of steps, precisely specifying the actions of multiple parties in order to achieve a (security) objective. An example of a cryptographic protocol, we describe the steps for message exchange using a symmetric key cryptosystem.

–  –  –

The difficulty of step 2.a) was one of the fundamental obstructions to cryptography before the advent of public key cryptography. Asymmetric cryptography provides an elegant solution to the problem of distribution of private keys.

–  –  –

Throughout the course we will denote the plaintext alphabet by A and the ciphertext alphabet by A′. We write EK for the enciphering map and DK ′ for the deciphering map, where K and K ′ are enciphering and deciphering keys.





–  –  –

We identify four different types of substitution ciphers.

A. Simple substitution ciphers. In this cryptosystem, the algorithm is a characterby-character substitution, with the key being the list of substitutions under the ordering of the alphabet. In other words, a simple substitution cipher is defined by a map A → A′.

Suppose that we first encode a message by purging all nonalphabetic characters (e.g.

numbers, spaces, and punctuation) and changing all characters to uppercase. Then the key size, which bounds the security of the system, is 26 alphabetic characters. Therefore the total number of keys is 26!, an enormous number. Nevertheless, we will see that simple substitution is very susceptible to cryptanalytic attacks.

Example. Consider this paragraph, encoded in this way, to obtain the plaintext:

SUPPOSETHATWEFIRSTENCODEAMESSAGEBYPURGINGALLNONALPHABETI

CCHARACTERSEGNUMBERSSPACESANDPUNCTUATIONANDCHANGINGALLCH

ARACTERSTOUPPERCASETHENTHEKEYSIZEWHICHBOUNDSTHESECURITYO

FTHESYSTEMISALPHABETICCHARACTERSTHEREFORETHETOTALNUMBERO

FKEYSISOFENORMOUSSIZENEVERTHELESSWEWILLSEETHATSIMPLESUBS

TITUTIONISVERYSUSCEPTIBLETOCRYPTANALYTICATTACKS

then using the enciphering key UVLOIDTGKXYCRHBPMZJQVWNFSAE, we encipher the plaintext

to obtain ciphertext:

QWMMPQDVKUVFDTXJQVDBOPIDUHDQQUGDLAMWJGXBGURRBPBURMKULDVX

OOKUJUOVDJQDGBWHLDJQQMUODQUBIMWBOVWUVXPBUBIOKUBGXBGURROK

UJUOVDJQVPWMMDJOUQDVKDBVKDCDAQXEDFKXOKLPWBIQVKDQDOWJXVAP

TVKDQAQVDHXQURMKULDVXOOKUJUOVDJQVKDJDTPJDVKDVPVURBWHLDJP

TCDAQXQPTDBPJHPWQQXEDBDNDJVKDRDQQFDFXRRQDDVKUVQXHMRDQWLQ

VXVWVXPBXQNDJAQWQODMVXLRDVPOJAMVUBURAVXOUVVUOCQ

Simple substitution ciphers can be easily broken because the cipher does not change the frequencies of the symbols of the plaintext.

Affine ciphers. A special case of simple substitution ciphers are the affine ciphers. If we numerically encode the alphabet {A, B..., Z} as the elements {0, 1,..., 25} of Z/26Z then we can operate on the letters by transformations of the form x → ax + b, for any a for which GCD(a, 26) = 1. What happens if a is not coprime to 26?

Classical Cryptography An affine cipher for which a = 1 is called a translation cipher. Enciphering in a translation cipher is achieved by the performing b cyclic shift operations (A → B, B → C, etc.) on the underlying alphabet.

A classical instance of a translation cipher is the Caesar cipher, used by Julius Caesar, which is the translation cipher with the enciphering key b = 3. Using Caesar’s enciphering key, we obtain the map A → D, B → E,..., Z → C.

Thought Exercise. Consider the number of possible keys for the affine ciphers. Is this sufficient to have a secure cryptosystem?

B. Homophonic substitution ciphers. In this cryptosystem the deciphering is a function from a larger alphabet A′ to the alphabet A, but an enciphering of the plaintext can take a character to any one of the elements in the preimage.

One way to realize a homophonic cipher is to begin with m different substitution keys, and with each substitution, make a random choice of which key to use. For instance, suppose we take A to be own standard 26 character alphabet, and let the cipher alphabet A′ be the set of character pairs. Suppose now that we the pair of substitution keys in the

ciphertext alphabet:

–  –  –

Then each of the following strings are valid ciphertext:

LVRKYHLVABZVRKHOHOVRHOXPWTLXQOMJNUYHFTNBTCFVYHJNQOHOMCZABQMCSH

UDZAYHUDQKZVZAHOXODSXOMJTCLXSHMJRNBQFTNBWTZVBQXPQOHOIGZABQMCSH

LVRKYHUDQKZVRKXOXODSHOXPTCLXQOPYRNBQEZNBTCFVBQXPSHHOIGZAYHMCSH

LVZABMUDABFVRKHOHODSHOXPWTLXQOPYRNBQEZNBTCZVBQXPQOXOIGZABQMCQO

Moreover, each uniquely deciphers back to the original plaintext.

–  –  –

ciphers are periodic substitution ciphers, which substitutes the (mj + i)-th plaintext character using the i-th key, where 1 ≤ i ≤ m. The number m is called the period.

Vigen`re cipher. The Vigen`re cipher is a polyalphabetic translation cipher, that is, e e each of the m keys specifies an affine translation.

Suppose that we take our standard alphabet {A, B,..., Z} with the bijection with

Z/26Z = {0, 1,..., 25}. Then beginning with the message:

–  –  –

This gives the encoded plaintext:

HUMANSALVATIONLIESINTHEHANDSOFTHECREATIVELYMALADJUSTED

The with the enciphering key UVLOID, the Vigen`re enciphering is given by performing e

the column additions:

HUMANS ALVATI ONLIES INTHEH ANDSOF THECRE ATIVEL YMALAD JUSTED

UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID UVLOID

-------------------------------------------------------------BPXOVV UGGOBL IIWWMV CIEVMK UIOGWI NCPQZH UOTJMO SHLZIG DPDHMG Recall that the addition is to be carried out in Z/26Z, with the bijection defined by the

following table:

ABCDEFGHIJ K L M N O P Q R S T U V W X Y Z

D. Polygram substitution ciphers. A polygram substitution cipher is a cryptosystem in which blocks of characters are substituted in groups. For instance (for a particular key) AA could map to NO, AB to IR, JU to AQ, etc. These cryptosystems make cryptanalysis harder by destroying the single character frequencies, preserved under simple substitution ciphers.

General affine ciphers. An affine cipher can be generalised to polygram ciphers. Rather than a map m → c = ma + b, we can apply a linear transformation of vectors

–  –  –

Recall that a substitution cipher permutes the characters of the plaintext alphabet, or may, more generally, map the plaintext characters into a different ciphertext alphabet. In a transposition cipher, the symbols of the plaintext remain the same unchanged, but their order is permuted by a permutation of the index positions. Unlike substitution ciphers, transposition ciphers are block ciphers.

The relation between substitution ciphers and transposition ciphers is illustrated below. The characters and their positions of the plaintext string ACATINTHEHAT appear in a graph with a character axis c and a position index i for the 12 character block 1 ≤ i ≤ n.

We represented as a graph a substitution cipher (with equal plaintext and ciphertext alphabets) is realised as a permutation of the rows of the array, while a transposition cipher is realised by permuting the columns in fixed size blocks, in this case 12.

–  –  –

The symmetric group Sn is the set of all bijective maps from the set {1,..., n} to itself, and we call an elements π of Sn a permutation. We denote the n-th composition of π with itself by π n. As a function write π on the right, so that the image of j is (j)π.

Exercise. Show that for every π in Sn, there exists an positive integer m, such that π m is the identity map, and such that m divides n!. The smallest such m is called the order of π.

–  –  –

The map (j)π = ij can be denoted by [i1,..., in ]. This is the way, in effect, that we have described a key for a substitution cipher — we list the sequence of characters in the image of A, B, C, etc. Although these permutations act on the set of the characters A,..., Z rather than the integers 1,..., n, the principle is identical.

An element of Sn is called a transposition if and only if it exhanges exactly two elements, leaving all others fixed.

Exercise. How many transpositions exist in Sn ? Describe the elements of order 2 in Sn.

How many are there?

Exercise. Show that every element of Sn can be expressed as the composition of at most n transpositions.

–  –  –

refers to a disjoint union, that is, ik is not equal to (iℓ )π j for any j where the symbol unless k = ℓ. The sets {(ik )π j : j ∈ Z} are called the orbits of π, and the cycle lengths of π are the sizes d1,..., dt of the orbits.

Asociated to any orbit decomposition we can express an element π as

–  –  –

Note that if dk = 1, then we omit this term, and the identity permutation can be written just as 1. This notation gives more information about the permutation π and is more compact for simple permutations such as transpositions.



Pages:   || 2 |


Similar works:

«Technical Support Document (TSD) for Carbon Pollution Emission Guidelines for Existing Stationary Sources: Electric Utility Generating Units Docket ID No. EPA-HQ-OAR-2013-0602 Projecting EGU CO2 Emission Performance in State Plans U.S. Environmental Protection Agency Office of Air and Radiation June 2014 Table of Contents Introduction I. Analytic Approaches for Projecting CO2 Emissions from Affected EGUs.6 II. A. Electricity System Modeling Approaches for Projecting EGU CO2 Emissions.6 B....»

«EASO SPECIAL SUPPORT PLAN TO ITALY Phase 2 Valletta Harbour and Rome, 11 March 2015 Hereby the Executive Director of EASO and the Head of the Department for Civil Liberties and Immigration of the Italian Ministry of Interior agree on the EASO Special Support Plan (Phase 2) for the provision of technical and operational assistance to Italy. Valletta Harbour and Rome, 11 March 2015 The Executive Director The Head of the Department for Civil Liberties and of the European Asylum Immigration Support...»

«Robust reliability or reliable robustness? Integrated consideration of robustnessand reliability-aspects Dipl.-Ing. S. Kemmler, Institute of Machine Components (IMA), University of Stuttgart; Dipl.-Wirtsch.-Ing. T. Eifler, Department of Mechanical Engineering, Technical University of Denmark (DTU); Prof. Dr.-Ing. B. Bertsche, Institute of Machine Components (IMA), University of Stuttgart; Associate Professor, MEng PHD T.J. Howard, Department of Mechanical Engineering, Technical University of...»

«Available online at www.sciencedirect.com ScienceDirect Procedia Social and Behavioral Sciences 119 (2014) 278 – 287 27th IPMA World Congress What is project efficiency and effectiveness? Erik Sundqvista*, Fredrik Backlunda, Diana Chronéera a Luleå University of Technology, Industrial Engineering and Management, Sweden Abstract The concepts of efficiency and effectiveness are commonly used when evaluating different processes. As project management can be described by different kinds of...»

«The orientational order/disorder transition in buckminsterfullerene (C60): an experiment using the NCNR Disk Chopper Spectrometer Summer School on Methods and Applications of Neutron Spectroscopy NIST Center for Neutron Research June 20-24, 2005 Craig Brown, John Copley and Yiming Qiu Abstract Time-of-flight neutron spectroscopy will be used to examine the orientational order/disorder transition in buckminsterfullerene. This experiment not only illustrates the important technique known as...»

«c 2006 Society for Industrial and Applied Mathematics SIAM J. APPL. MATH. Vol. 66, No. 4, pp. 1321–1338 MULTIPLE EQUILIBRIA IN COMPLEX CHEMICAL REACTION NETWORKS: II. THE SPECIES-REACTION GRAPH∗ GHEORGHE CRACIUN† AND MARTIN FEINBERG‡ Abstract. For mass action kinetics, the capacity for multiple equilibria in an isothermal homogeneous continuous flow stirred tank reactor is determined by the structure of the underlying network of chemical reactions. We suggest a new graph-theoretical...»

«Examiner’s report F5 Performance Management September 2015 General Comments There were two sections to the examination paper and all questions were compulsory. Section A consisted of 20 multiple choice questions (two marks each) which covered a broad range of syllabus topics. Section B had three shorter questions (worth 10 marks each) and two longer questions (worth 15 marks each). These questions covered all of the main syllabus areas. On the whole, candidates scored better in Section A than...»

«BIS ANALYSIS PAPER 04 Estimating the effect of UK direct public support for innovation NOVEMBER 2014 BIS ANALYSIS PAPER NUMBER 04 Estimating The Effect Of UK Direct Public Support For Innovation NOVEMBER 2014 Acknowledgments This paper was developed by Mike King and Edward Woolley. We are grateful for the contributions of GO-Science, the National Physical Laboratory and Her Majesty’s Treasury (HMT) which have made this paper possible. The authors particularly would like to thank Professor...»

«El Cuarto De Atras Where the interview is to recruit only owed, no hotel that these grid thumb download may take the climate at fuel and start unless the that a human expenditure excels damaged and able others want distributed. Create my problematic likely rate to have a service market as you have to bring. For they want technical but pay an associated property, those form on the link accumulates cheaper for a bureau. That repayment, you can not succeed making more of a online of your decision...»

«UNDERPRICING IN TURKEY: A COMPARISON OF THE IPO METHODS Guray KUCUKKOCAOGLU* Abstract This paper addresses the question of what kind of selling and underwriting procedure might be preferred for controlling the amount and volatility of underpricing in the Istanbul Stock Exchange (ISE). Using 1993-2005 firm and issue data, we compare the three substantially different IPO methods available in the ISE. One is very similar to the book building mechanism used in the U.S., another is the fixed price...»

«Controlling for Consensus: Commemorating Apartheid in South Africa Chana Teeger Harvard University Vered Vinitzky-Seroussi Hebrew University of Jerusalem According to the literature, commemorations of difficult pasts can be categorized into two main types, fragmented and multivocal—both of which serve to express, if not to enhance, social conflicts. Our analysis of the first apartheid museum in South Africa, however, points to a commemorative type that aims at agreement, not through...»

«A Manifesto for the Equifinality Thesis Keith Beven Lancaster University, UK Abstract This essay discusses some of the issues involved in the identification and predictions of hydrological models given some calibration data. The reasons for the incompleteness of traditional calibration methods are discussed. The argument is made that the potential for multiple acceptable models as representations of hydrological and other environmental systems (the equifinality thesis) should be given more...»





 
<<  HOME   |    CONTACTS
2016 www.thesis.xlibx.info - Thesis, documentation, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.