New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Special Topics

by: Alayna Veum
Alayna Veum

GPA 3.81


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 4803 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 80 views. For similar materials see /class/234146/cs-4803-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.

Similar to CS 4803 at

Popular in ComputerScienence


Reviews for Special Topics


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 11/02/15
troduction to odeling and mulation Heat Equation Cont d Wave and Advection Equations Review I Classification of PDEs 7 Elliptic equations 7 Parabolic equations 7 Hyperbolic equations 7 Examples of these different types I Diffusion equations 7 Derivation conservation law Fick s law 7 Method of lines 7 Stiffness of diffusion equations Outline I Heat equations cont d 7 CrankNicholson method 7 Lax equivalence theorem I Wave equation and advection equation 7 Derivation of wave equation 7 Relationship to advection equation 7 First attempt of solving advection equation 1 Method of Lines for Parabolic Eqs Consider 1D heat diffusion equation at am First discretize in space and leave continuous in time T This results in system of ODEs Solved resulting ODEs as initial value problems For heat equation introduce spatial mesh points iOm1 where AX1m1 and replace derivative uXX by finite difference approximation 3 ulxi1 2utxiutxi1 Ax2 uwtxi then we get system of ODEs 350fyi1t 2yit3540 Ax for i1 where ytzuXt Stiffness of Parabolic Equations l Semidiscrete system of ODEs yt 2yi1t 2 t y 1t Ax can be written in matrix form 2 1 0 0 1 2 1 0 0 1 2 0 A y W Z y y 0 0 1 2 l Jacobian matrixAhas eigenvalues between 4AX2 and O which makes ODE very stiff I If we use explicit Euler then stability limit is 4AtAX2lt2 or At lt05AX2 5 quot CrankNicholson Method I Applying trapezoid method k1 k k1 k u f t Hf forODEu fu h 2 to heat equation EM 22 Eff 1 2 yfff1 y 22 yfff 2y MEquot I In Matrix form we have 1 2r r 0 0 rg0tn g0tn1 1 20y of r 1 2r r 0 ryfk 1 20y ry k 0 r 1 2r 0 y rygquot 1 2mg ryff 0 0 r 1 2r ryif31lt1 2rgtyf rltg1ltrngt g1 ltth gtgt where r At2AX2 1 Properties of CrankNicholson Method I 2ndorder accurate in time and space I Unconditionally stable can be shown using Fourier analysis or von Neumann analysis I In comparison fonNard Euler in time is less unstable and firstorder accurate while backward Euler is unconditionally stable but only firstorder accurate I In one spatial dimension linearsystem is tridiagonal so it can be solved efficiently r Lax Equivalence Theorem I Consistency Local truncation error goes to zero I Stability approximate solution remains bounded at any fixed time I Convergence As At and Ah approaches zero we should get exact solution I Lax Equivalence Theorem for wellposed linear PDE consistency and stability are together necessary and sufficient conditions for convergence 1 HigherDimensional Generalization I For higher spatial dimensions heat equation becomes 2 at W um I CrankNicolson method still applies however the linear system is no longer banded I Iterative solvers are particularly suitable especially because one always has some suitable initial guess for the linear system Hyperbolic PDEs I Typically describe timedependent conservative physical problems such as convection that do not evolve toward steady state 7 Wave equations secondorder utt Czuxx 7 Advection equations firstorder at aux 0 10 troduotion to odeling anol mulation Classification of PDEs Diffusion Equations 39 Review Iterative Solvers I Relaxation methods Jacobi and GuassSeidel method Successive overrelaxation SOR I Conjugate gradient method a Only for symmetric positive definite matrices Relates to optimization methods I How do these different methods compare in performance Storage Format for Sparse Matrix How do we store sparse matrices Similar to data structure for sparse graphs In general store only nonzero entries along with indices to identify their locations in matrix Explicitly storing indices incurs additional storage overhead and makes accesses to nonzeros less efficient due to indirect addressing Data structure is worthwhile if matrix is sufficiently sparse which is often true for very large problems arising from PDEs and many other applications Reference Sparse Matrix Storage Formats J Dongarra 4 Compressed Row Storage Compressed row storage CR8 is most common storage format for sparse matrices l Stores subsequent nonzeros of matrix rows in contiguous memory using three vectors C val floating pointnumbers storing nonzero values D coliind column indices of nonzero entries D rowiptr starting indices of eac r w 39 Examp3993 0 3 u 0 1 41000 A 0 3 9 2 J 7i5 nzA13 6 0 n 53 u 0 3 8 9 The CR8 format ofAis val3141592653589 c017ind2512234145345 r0wptr13 58 11 14 Outline I Classification of PDEs Elliptic equations Parabolic equations Hyperbolic equations I Diffusion equations Derivation of heat equation Stiffness First attempt of solving diffusion equations 1 Partial Differential Equations PDE I Involve partial derivatives wrt more than one independent variable I Independent variables include one or more space dimensions and possible time dimension Eg two space dimensions or one space and one time dimension I Can have purely initial value problem pure boundary value problem or mixture 11 Secondorder PDEs I Some important secondorder PDEs El Heat equation Mt um l Wave equation u czuxx l Laplace equation um MW 2 0 I Classification of 2ndorder PDEs l Secondorder linear PDEs of form 6mm 9thy cuyy dux euy fu g 0 Circle 7 are classified by value of discriminant b24ac analogous to classification of conic sections Di b24acgt O hyperbolic eg wave equation El b24ac O parabolic eg heat equation El b24ac lt O elliptic eg Laplace equation 7 Hyperbola I Parabolic and hyperbolic are typedependent problems 7 r Parabolic Problems I Timede endent dissipative physical processes such as heat flow that evo ve toward steady state ll eg Poisson equation i l Diffusion problems heat equations I Relationship to elliptic problems f i Elliptic PDEs describe processes that have already reached steady state hence are timeindependent i i Example The following heat equation is parabolic 2 at V M f At steady state u 0 so we have Poisson equation Vzu f which is elliptic I Parabolic equations are timedependent and often require initial and boundary conditions I A plications of parabolic equations particle diffusion heat diffusion B ackSholes model in finance image smoothing etc quot1 Derivation of Diffusion Equation I Where did diffusion equation come from I Consider 1D derivation I Let u denote density then total mass petween two points X1 and X2 at time tis then leultx gtdx which can change due to flux or flow of particles I Let fdenote flux function and u f I Due to Fick s law in diffusion process fux Kux where KiS diffusion coefficient and hence at Cum I In heat transfer u is temperature and Fick s law is known as Fourier s law of heat conduction 9 JIIIIIII Finite Difference Solution of Heat Equation I Consider 1D heat diffusion equation it 2 KM where K1 in general KgtO KltO leads to illposed backward heat eq initial condition uOXsX OltXlt1 and boundary conditions ut0got ut1g1t tgtO I Basic idea 2 Introduce discrete grid with grid points x iOm1 and t Approximate derivatives using finite differences Solve for ux 2 I Should we solve for u at all times simultaneously Most methods do not in particular method of lines Some methods do spacetime methods 10 1 Method of Lines for Parabolic Eqs I Discretize in space and leave continuous in time i This is known as semidiscrete form Result is system of ODEs I Solved resulting ODEs as initial value problems I For heat equation introduce spatial mesh points iOm1 where AX1m1 and replace derivative uXX by finite difference approximation ulxi1 2utxiutxi1 u txi z My then we get system of ODEs W Lyme 2m mt AX for i1 where ytzuXt 11 troduction to odeling and mulation Advection Equations Application to Traffic Flow Review I Parabolic equations 7 Examples diffusion equation heat equation a CrankNicholson method Centereddifference in space and trapezoid rule in time Secondorder accurate in space and time Unconditionally stable Astable I Hyperbolic equations Wave equation secondorder Advection equation firstorder Wave and advection equations are closely related to each other Outline I Derivation of hyperbolic equations I Numerical solutions of hyperbolic equations First unsuccessful attempt using forward difference LaxWendroff scheme I Application to traffic flow 1 Derivation of Advection Equation Where did advection equation come from i r From conservation law Let u denote density then total mass between two points x1 and X2 at time tis then J xz uxtdx which can change due to flu or flow of particles Let f denote flux function and then uxtdx fux1t fMOCzJ therefore a a Jxg MXt dxJx2 fxJ dx 3 42 0 x1 at x1 ax For advection flux is fxau for some a and therefore at aux 0 NavierStokes equation most fundamental equation in computational fluid dynamics is derived from conservation of mass momentum and energy so system of advection equations F Solution of Advection Equation Now consider scalar advection equation at cmC 0 Its exact solution shifts object with speed c Using method of lines first consider semidiscrete form with centered difference in time a y t Ey1t y1t with first and last equations using periodicity In matrix form the system becomes 0 1 o 1 a o 1 o o A y 2m y y 1 o 1 0 whose eigenvalues are A Sin2 39ph forp 12 Note that different from parabolic equations these eigenvalues are 018 instead of 01h2 so advection equations are not stiff explicit methods K Forward Euler Time Disoretization I Disoretize using forward difference in time 01 i i i yj yj ayj1 yj l O r At 2M 01 2 i a A i i yj y 2mm yH I The method is stable only if 1 Vtl lSl where 7L is eigenvalue from previous slide I Since 7L is imaginary no matter how small At is the method is unstable I Must look for alternative methods 39 1 LaxWendroff Method I Big idea introduce artificial diffusionviscosity to solve equation ut aux 2 Sum for some small 8 8 as At decreases hopefully sOAt I How to obtain a I Consider Taylor series expansion ux t At uxt Atutxt At2u x 2 I Replace ut by auX and u by a2u we have XXI ux t At ux t Ataux x t At2a2uxx x t I Then applying centered differences we have i1 i m i 1 At a i i i y gty Ey 31y 31 2Ax2 y il2y y 31 39 Note Why Un a2uxx a2 a em a au a2 a a 12 2 8x a 8x a a ax 39 More General Case I For more general equation a a dF Bu F at x 0 8x u du ax where Fu is flux and dFdu is wave speed I LaxWendroff scheme is slightly more complex A A02 dF 817 dF 617 11 f Flt Fll y y 2mlt 1 1 1 2m du ax du ax 1e 1e At A02 z z z y 2 F11 FJ1 2 dF y3igty521 yygty z du 2 Ax du 2 Ax w 1 Properties of LaxWendroff Method I LaxWendroff scheme is secondorder accurate in time and space I It is stable if aAfAx 1 Known as CFL CourantFriedrichsLewy Condition necessary condition for explicit finite difference scheme for hyperbolic PDE to be stable is that for each mesh point domain of dependence of PDE must lie within domain of dependence of finite difference scheme I In fact it introduces minimum amount of artificial viscosity to stabilize the solution Application to Traffic Flow We have looked at traffic simulations using discrete event simulations now let us do continuous modeling of traffic flow Problem Analyze density of car with initial condition L4 lt x lt 0 0 otherwise Suppose light turns green at t0 and cars starts moving how would density of cars change over time pltxr0p0ltxpm Source Numerical Methods for Physics by A L Garcia 2000 10 Equation for Traffic Flow I Consider equation of mass conservation 8mm 2 a I For traffic flow velocity vdepends on density 0 W vm100m so at maximum density pm velocity becomes 0 and at density 0 it reaches maximum velocity vm I This leads to nonlinear PDE modeling density of cars as waves ai0x7 0106 0 x 11 Traffic Flow Cont d I LaxWendroff scheme gives At Ar2 FFQ F FC pg 11 I I I where F 9 E pvp d0v cltpgtz vma zppm dp n n pi1 pi Cii C 2 I Note that Cp is speed of wave not speed of cars 12 troduction to odeling and mulation Iterative Linear Solvers Review I Accuracy and stability of solution of BVPs a Different from finitedifference solutions to lVPs local truncation errors in general do not accumulate I Types of boundary conditions Dirichlet BC Newmann BC I Poisson equations Special case Laplace equation I How to solve linear systems resulted from finite difference methods Outline I Solution of sparse linear systems I Basic concepts and overview of direct methods Gaussian elimination I Iterative methods for linear systems Jacobi and GaussSeidel methods Successive overrelaxation SOR Conjugate gradient method 39 1 How to Solve Linear Systems Boundaryvalue problems yields systems of linear algebraic equations similarly for implicit methods for timedependent PDEs as we will discuss later Linear systems are in general sparse with relatively few nonzeros in matrix For nxn matrix direct solvers such as Gaussian elimination and Cholesky factorization require requires 0n2 stora e and 0n3 computation Covered in detail in numerica linear algebra Sparsity must be exploited to use much less storage and computation Sparse direct solvers which are more sophisticated and more accurate Sparse iterative solvers are simpler and often suffice for solving differential equations and therefore are our focus 1 Relaxation Methods I Split sparse matrix and then successively approximate 39 1 ui1j ui71j uij1uij71 4uij fogs yj gt 1 If 13139 Zui1jui71juij1uij71jfxi5 yj39 I For Laplace s equation each point is set to average of its neighbors I Jacobi method update each point using old values of neighbor points I GaussSeidel method modify Jacobi method to use new values as soon as available I Warning these methods are very simple but may not converge or converge very slowly 39 Jacobi Iteration I Formula W lltu kgt qu u ultkgt gt 2fltxyjgt Algorithr 4 for iterOmaxiter forj2m1 for i2m1 unewij O25ui1j ui1j uij1 uij1 hquot2 fij end end u unew end quot GaussSeidel Method I Formula 1 hz Zltu5 1 u1 u1gtgt 7an y I Algorithm for iterOmaxiter forj2m1 for i2m1 uij O25ui1j ui1j uij1 uij1 hAZ fij end end end MatrixSplitting I Jacobi and GaussSeidel are examples of matrixsplitting methods Matrix A is split into A M N I Then equation Auf can be written as Mu Nuf gt MuNuf and further Muk1 2 Nu f ufk 1 M INuquot M 1f I Matrix GM391N IS Iteration matrix I Method converges if absolute values of eigenvalues of G are lt1 ie its spectral radius plt1 I In particular Hemllz Spkllewllz quot1 Analysis of Jacobi and 38 I We split ADLU where L and U are lower and upper triangular matrices I For Jacobi method MD and NLU 39 For Poisson equation its spectral radius is approximately 1057t2h2 so if h is small it converges very slowly I For GaussSeidel method MDL NU 39 For Poisson equation its spectral radius is approximately 17t2h2 so it also converges very slowly I In general GaussSeidel converges twice as fast as Jacobi methods More Efficient Method I Successive overrelaxation SOR GS uk Mk1uk uk1hfxv m 4 141 HJ 12M 12H 4 l J MG u auGS uquot where oogt1 is some scalar If Dlt1 then it is called underrelaxation I In matrix form leDL NMDU a a I With a optimal choice of o spectral radius of GM391N is minimized to about 127th making it much more efficient than Jacobi or 38 I However determining optimal 03 requires solving for eigenvalues which is too costly 1o 39 Variance of GaussSeidel I Redblack order a Color nodes interleavineg into red and black Update red nodes using black nodes in one iteration and then update red nodes using black nodes next I Redblack order converges faster than Jacobi iterations and is amendable to parallelization I However it is still converge very slowly 11 More Efficient Method I Successive overrelaxation SOR 2 1 h GS k k1 k k1 u 4uz1 1 uw1 MA 4 fxquot m Mam Mac Muss 10 W 7 w w M M mquot 739 7 quot quot7 law where co is some scalar l If 0 gt1 it is called overrelaxation L V lf colt1 it is called underrelaxation I In matrix form MiD L N D U l m w an an a a I With a optimal choice of 0 spectral radius of GM391N is minimized to about 127th making it much more efficient than Jacobi or GS I However determining optimal 0 requires solving for eigenvalues which is too costly I Is there a simple and efficient algorithm F Conjugate Gradient Method If A is nxn symmetric positive definite matrix then quadratic function X XTAX XTb attains minimum precisely when Ax b Optimization methods have form Xk1 Xk ask where or is search parameter chosen to minimize objective function Xkask along sk For quadratic problem negative gradient is residual vector V Xb AXI Line search parameter can be determined analytically a rkTsk szsk 13 1 1 Conjugate Gradient Method Cont d l Using above properties we obtain CG method m0 2 initial guess To b 7 A380 30 To for k012 01k rgrksArAsk ackt wk aksk Tk1 Tk akAsk Bk1 r1rk1rn 3k1 W1 k13k quot1 Key Features of CG I Short recurrence determines search directions that are Aorthogonal conjugate I Error is minimal over space spanned by search directions generated so far I Minimum error implies exact solution reached in at most n steps since n linearly independent search directions must span whole space I In practice loss of orthogonality due to rounding error spoils finite termination property so method is used iteratively 15 1 More Advanced Topics for Iterative Linear Solvers I Preconditioning can substantially accelerated convergence rate of CG Apply CG algorithm to M39iA where M is chosen so that M39iA is better conditioned and systems of form Mzy are easily solved Example of preconditioner including Jacobi SSOR incomplete factorization etc I Generalization of CG to unsymmetric matrics GMRES BiCGSTAB I Multigrid methods 16 Comput Cost for kxkxk Grid method 2 D 3 D Dense Cholesky k6 k9 Jacobi k4 log k k5 log k Gauss Seidel k4 log k k5 log k Band Cholesky k4 k7 Optimal SOR k3 log k k log k Sparse Cholesky k3 k6 Conjugate Gradient 3 k4 Optimal SSOR k25 log k k35 log k Preconditioned CG 5 135 Optimal ADI k2log2k k3log2c Cyclic Reduction 1 log k k3 log k FFT k2 log k k3 log I Multigrid V cycle k2 log k k3 log k FACR k2 log log k k3 log log k 3 Full Multigrid k2 A I If problems are illconditioned then iterative solver may converge very slowly Chapter 2 A LOOK BACK In this chapter we take a quick look at some classical encryption techniques illustrating their weakness and using these examples to initiate questions about how to de ne privacy We then discuss Shannon s notion of perfect security 21 Substitution ciphers One of the earliest approaches to symmetric encryption is what is called a substitution cipher Say the plaintext is English text We can view this as a sequence of symbols each symbol being either a letter a blank or a punctuation mark Encryption substitutes each symbol a with another symbol 7ra The function 7r is the key and has to be a permutation meaning oneto one and onto so that decryption is possible Encryption of this form is quite natural and well known and indeed to many people it de nes how encryption is done We will later see many other and better ways to encrypt but it is worth beginning by exploring this one Let s begin by specifying the scheme a little more mathematically It may be valuable at this time to review the box in the Introduction that recalls the vocabulary of formal languages we will be talking of things like alphabets symbols and strings Let E be a nite alphabet whose members are called symbols In our examples 2 would contain the 26 letters of the English alphabet the blank symbol LI and punctuation symbols Let us refer to this henceforth as the English alphabet If x is a string over 2 then we denote by its i th symbol Recall that if x is a string then denotes the length of w meaning the number of symbols in it Let us also adopt the convention that if X is a set then X denotes its size The double use of the I 77 notation should not cause much problem since the type of object to which it is applied namely a set or a string will usually be quite clear A permutation on a set S is a map 7r S a S that is one to one and onto Such a map is invertible and we denote its inverse by 7r 1 The inverse is also a permutation and the map and its inverse are related by the fact that 7r 17rw w and 7r7r 1y y for all wy E S We let PermS denote the set of all permutations on set S Note that this set has size SI In the introduction we had discussed symmetric encryption schemes and said that any such scheme is speci ed as a triple SS 1C 5 D consisting ofa key generation algorithm an encryption 2 A LOOK BACK algorithm and a decryption algorithm A substitution cipher over alphabet E is a special kind of symmetric encryption scheme in which the output of the key generation algorithm 1C is always a permutation over 2 and the encryption and decryption algorithms are as follows Algorithm 7rM Algorithm D7r C Fori1Mdo Fori1Cdo e e 7r 1Ci Return C Return M Above the plaintext M is a string over 2 as is the ciphertext C The key is denoted 7r and is a permutation over 2 We will let KeysS denote the set of all keys that might be output by K There are many possible substitution ciphers over 2 depending on the set KeysS In the simplest case this is the set of all permutations over 2 and 1C is picking a permutation at random But one might consider schemes in which permutations are chosen from a much smaller set In our examples unless otherwise indicated the alphabet will be the English one de ned above namely 2 contains the 26 English letters the blank symbol LI and punctuation symbols We will for simplicity restrict attention to substitution ciphers that are punctuation respecting By this we mean that any key permutation 7r 6 KeysS leaves blanks and punctuation marks unchanged In specifying such a key we need only say how it transforms each of the 26 English letters Example 21 This is an example of how encryption is performed with a punctuation respecting substitution cipher An example key permutation 7r is depicted below a Wltagt Note every English letter appears once and exactly once in the second row of the table That s why 7r is called a permutation The inverse 7r 1 permutation is obtained by reading the table backwards Thus 7r 1D A and so on The encryption of the plaintext M HI THERE F T F C 7rH7rH7rI7rl7rT7rH7rE7rR7rE LA MLWXW I Now let SE IC D be an arbitrary substitution cipher We are interested in its security To assess this we think about what the adversary has and what it might want to do The adversary begins with the disadvantage of not being given the key 7r It is assumed however to come in possession of a ciphertext C The most basic goal that we can consider for it is that it wants to recover the plaintext M D7rC underlying C The adversary is always assumed to know the rules of the game77 Meaning it knows the algorithms IC D lt knows that a substitution cipher is being used and that it is punctuation respecting in our case The only thing it does not know a priori is the key for that is assumed to have been shared secretly and privately between the sender and receiver So the adversary sees some gibberish such as the text LA MLWXW One might imagine that in the absence of the key 7r it would have a tough time guring out that the message was HI THERE But in fact substitution ciphers are not so hard to cryptanalyze lndeed breaking a substitution cipher is a popular exercise in a Sunday newspaper or magazine and many of you may have done it The adversary can use its knowledge of the structure of English text to its advantage Often a Bellare and Rogaway 3 IJKLMND Figure 21 Cryptanalysis of Example 22 good way to begin is by making what is called a frequency table This table shows for ever letter 739 how often 739 occurs in the ciphertext Now it turns out that the most common letter in English text is typically E The next most common are the group T A D I N S H R These letters have roughly the same frequency somewhat lower than that of E but higher than other letters So if X is the most frequent ciphertext symbol a good guess would be that it represents E The guess is not necessarily true but one attempts to validate or refute it in further stages Another thing to do is look for words that have few letters Thus if the letter T occurs by itself in the ciphertext we conclude that it must represent A or I Two letter words give similar information And so on it is remarkable how quickly you actually usually can gure out the key Example 22 Let us try to decrypt the following ciphertext CDXBX TBX CVK CDGXR DI T GTI R ADHX VDXI 0X RDKQAU IKC RNXPQATCX VDXI 0X PTI C THHKBU DC TIU VDXI 0X PTI Here is our frequency table IAIBICIDIEIFIGIHIIIJIKILIMINIDIPIQIRISITIUIVIWIX IYIZI 337400239040018324083401300 The most common symbol being X we guess that 7r 1X E Now we see the word DX and assuming X represents E 0 must represent one of B H M W We also note that D has a pretty high frequency count namely 8 So my guess is that 0 falls in the second group of letters mentioned above But of the letters B H M and W only H is in this group so let s guess that 7r 1D H Now consider the rst word in the ciphertext namely CDXBX We read it as HEE This could be THERE or THESE I will guess that 7r 1C T keeping in mind that 7r 1B should be either R or S The letter T occurs on its own in the ciphertext so must represent A or I But the second ciphertext word can now be read as RE or SE depending on our guess for B discussed above We know that the which stands for the letter T in the ciphertext decodes to either A or I Even though a few choices yield English words my bet is the word is ARE so I will guess 7r 1T A and 7r 1B R The second row of the table in Fig 21 shows where we are Now let us write the ciphertext again this time indicating above different letters what we believe them to represent THERE ARE T T E A A E HE HE H T E ATE HE HE CDXBX TBX CVK CDGXR DI T GTI R ADHX VDXI 0X RDKQAU IKC RNXPQATCX VDXI UK A T A R T A HE HE A PTI C THHKBU DC TIU VDXI DX PTI 4 A LOOK BACK Since the last letter of the ciphertext word DC represents T the rst letter must represent A or I But we already have something representing A so we guess that 7r 1D I F rom the ciphertext word DI it follows that I must be either N T or S It can t be T because C already represents T But I is also the last letter of the ciphertext word VDXI and HEN is a more likely ending than HES so I will guess 7r 1I N To make sense of the ciphertext word VDXI I then guess that 7r 1V W The ciphertext word PTI C is now AN T and so surely 7r 1P C The second row of the table of Fig 21 shows where we are now and our text looks like THERE ARE TW TI E IN A AN I E WHEN HE H N T EC ATE WHEN HE CDXBX TBX CVK CDGXR DI T GTI R ADHX VDXI DX RDKQAU IKC RNXPQATCX VDXI DX CAN T A R IT AN WHEN HE CAN PTI C THHKBU DC TIU VDXI DX PTI At this point I can decrypt the rst 8 words of the ciphertext pretty easily THERE ARE TWD TIMES IN A MAN S LIFE The third row of the table of Fig 21 shows where we are after I put in the corresponding guesses Applying them our status is THERE ARE TWD TIMES IN A MAN S LIFE WHEN HE SHD L NDT S EC LATE WHEN HE CDXBX TBX CVK CDGXR DI T GTI R ADHX VDXI DX RDKQAU IKC RNXPQATCX VDXI DX CAN T AFFDR IT AN WHEN HE CAN PTI C THHKBU DC TIU VDXI DX PTI The rest is easy The decryption is THERE ARE TWD TIMES IN A MAN S LIFE WHEN HE SHOULD NOT SPECULATE WHEN HE CDXBX TBX CVK CDGXR DI T GTI R ADHX VDXI 0X RDKQAU IKC RNXPQATCX VDXI 0X CAN T AFFORD IT AND WHEN HE CAN PTI C THHKBU DC TIU VDXI DX PTI The third row of the table of Fig 21 shows our nal knowledge of the key 7r The text by the way is a quotation from Mark Twain I Some people argue that this type of cryptanalysis is not possible if the ciphertext is short and thus that substitution ciphers work ne if say one changes the key quite frequently Other people argue for other kinds of variants and extensions And in fact these types of systems have been the basis for encryption under relatively modern times We could spend a lot of time on this subject and many books do but we won t The reason is that as we will explain the idea of a substitution cipher is awed at a quite fundamental level and the aw remains in the various variations and enhancements proposed It will take some quite different ideas to get systems that deliver quality privacy To illustrate why the idea of a substitution cipher is awed at a fundamental level consider the following example usage of the scheme A polling station has a list of voters call them V1 V2 Vn Each voter casts a secret ballot which is a choice between two values You could think of them as YES or NO being votes on some Proposition or BUSH and KERRY In any case we represent them as letters the two choices are Y and N At the end of the day the polling station has a list 111 1 of 71 votes where 1 is Vs vote Each vote being a letter either Y or N we can think of the list of votes as a string 1 111 11 over the alphabet of English letters The polling station wants to transmit this string to a tally center encrypted in order to preserve anonymity of votes The polling station and tally center have agreed on a key 7r for a substitution cipher The polling Bellare and Rogaway 5 station encrypts the message string 1 to get a ciphertext string 0 111 7r11n and transmits this to the tally center Our question is is this secure It quickly becomes apparent that it is not There are only two letters in 1 namely Y and N This means that c also contains only two letters Let s give them names say A and B One of these is 7rY and the other is 7rN If the adversary knew which is which it would from the ciphertext know the votes of all voters But we claim that it is quite easy for the adversary to know which is which Consider for example that the adversary is one of the voters say V1 So it knows its own vote 111 Say this is Y It now looks at the rst symbol in the ciphertext If this is A then it knows that A 7rY and thus that B N and can now immediately recover all of 112 1 from the ciphertext If the rst symbol is B it is the other way around but again it recovers all votes This attack works even when the ciphertext is short that is when n is small The weakness is exhibits is in the very nature of the cipher namely that a particular letter is always encrypted in the same way and thus repetitions can be detected Pinpointing this weakness illustrates something of the types of mode of thought we need to develop in cryptography We need to be able to think about usage of application scenarios in which a scheme that otherwise seems good will be seen to be bad For example above we considered not only that the encrypted text is votes but that the adversary could be one of the voters We need to always ask what if77 We want symmetric encryption schemes that are not subject to the types of attacks above and in particular would provide security in an application such as the voting one Towards this end we now consider onetimepad encryption 22 Onetime pad encryption and perfect security The One Time Pad OTP scheme with key length m is the symmetric encryption scheme 55 1C 5 D whose algorithms are as follows The code for the key generation algorithm is Klti01m return K meaning a key is a random m bit string The encryption algorithm is de ned by KM K 69 M where the message M is an m bit binary string and EB denotes bitwise XOR The decryption algorithm is de ned by DKC K 69 C where C E 01m The correctness condition is met because DK KM K 69 K 69 M M for all M E 01m Let us go back to our voting example Represent Y by 1 and N by 0 and now encrypt the vote string 1 111 11 with the OTP scheme with key length n Thus the ciphertext is C K 69 1 This time weaknesses such as those we saw above are not present Say the adversary has the ciphertext C C1 On where C is the i th bit of 0 Say the adversary knows that 111 1 It can deduce that K1 the rst bit of K is 1 69 Cl But having K1 tells it nothing about the other bits of K and hence 112 1 remain hidden It turns out that the higher quality of privacy we see here is not con ned to this one application setting The scheme has a property called perfect security which we will de ne below and effec tively provides the best possible security We will also see that substitution ciphers do not have this property providing a more formal interpretation of the concrete weaknesses we have seen in them Before going on we remark that the perfect security of the OTP with key length m relies crucially on our encrypting only a single message of length m Were we to encrypt two or more messages privacy would be lost To see this suppose we encrypt M1 then M2 The adversary 6 A LOOK BACK obtains C1 K 69 M1 and C2 K 69 M2 XORing them together it obtains M1 69 M2 This however provides partial information about the data and in particular if the adversary would now happen to learn M1 it could deduce M2 which is not desirable The idea behind perfect security is to consider that one of two messages M1 or M2 is being encrypted The adversary is aware of this and all it wants to know is which of the two it is It has in hand the ciphertext C and now asks itself whether given C it can tell whether it was M1 or M2 that gave rise to it Perfect security says that the adversary cannot tell It asks that the probability that C arises as the ciphertext is the same whether M1 or M2 was chosen to be encrypted De nition 23 Perfect Security of a Symmetric Encryption Scheme Let SE IC D be a symmetric encryption scheme and assume we use it to encrypt just one message drawn from a set Plaintexts We say that 55 is perfectly secure if for any two messages M1 M2 6 Plaintexts and any C Pr KM1 C Pr KM2 C 21 In both cases the probability is over the random choice K lt1 C and over the coins tossed by 5 if any I Let us now show that a substitution cipher fails to have this property even if the ciphertext encrypted is very short say three letters Claim 24 Let SS IC D be a substitution cipher over the alphabet 2 consisting of the 26 English letters Assume that C picks a random permutation over 2 as the key That is its code is 7r lti Perm2 return 7r Let Plaintexts be the set of all three letter English words Assume we use 55 to encrypt a single message from Plaintexts Then 55 is not perfectly secure I lntuitively this is due to the weakness we saw above namely that if a letter appears twice in a plaintext it is encrypted the same way in the ciphertext and thus repetitions can be detected lf M1M2 are messages such that M1 contains repeated letters but M2 does not then if the adversary sees a ciphertext with repeated letters it knows that M1 was encrypted This means that this particular ciphertext has different probabilities of showing up in the two cases We now make all this formal Proof of Claim 24 We are asked to show that the condition of De nition 23 does not hold so the rst thing to do is refer to the de nition and right down what it means for the condition to not hold It is important here to be careful with the logic The contrapositive of for all M1 M2 C some condition holds is there exist M1M2C such that the condition does not hold Accordingly we need to show there exist M1M2 E Plaintexts and there exists C such that Pr 7rM1 C 7 Pr 7rM2 C 22 We have replaced K with 7r because the key here is a permutation We establish the above by picking M1M2C in a clever way Namely we set M1 to some three letter word that contains a repeated letter speci cally let us set it to FEE We set M2 to a three letter word that does not contain any repeated letter speci cally let us set it to FAR We set C to XYY a ciphertext that has the same pattern as FEE in the sense that the last two letters are the same and the rst is different from these Now we evaluate the probabilities in question Pr 7rM1C Pr swarm m Bellare and Rogaway 7 7r 6 Perm2 7rFEE XYY Perm2 7r 6 Perm2 7rF7rE7rE XYY Perm2 7 241 7 1 Recall that the probability is over the choice of key here 7r which is chosen at random from Perm2 and over the coins of 5 if any In this case 5 does not toss coins so the probability is over 7r alone The probability can be expressed as the ratio of the number of choices of 7r for which the stated event namely that 7rFEE XYY is true divided by the total number of possible choices of 7r namely the size of the set Perm2 from which 7r is drawn The second term is 261 For the rst we note that the condition means that 7rF X and 7rE Y but the value of 7r on any of the other 24 input letters may still be any value other than X or Y There are 241 different ways to assign distinct values to the remaining 24 inputs to 7r so this is the numerator above Now we proceed similarly for M2 Pr 7rM2 C Pr 57rFAR XYY 7r 6 Perm2 SAFAR XYY Perm2 7r 6 Perm2 7rF7rA7rR XYY Perm2 i 0 7 7 0 In this case the numerator asks us to count the number of permutations 7r with the property that 7rF X 7rA Y and 7rR Y But no permutation can have the same output Y on two different inputs So the number of permutations meeting this condition is zero In conclusion we have Equation 22 because the two probabilities we computed above are differ ent I Let us now show that the OTP scheme with key length m does have the perfect security property lntuitively the reason is as follows Say m 3 and consider two messages say M1 010 and M2 001 Say the adversary receives the ciphertext C 101 It asks itself whether it was M1 or M2 that was encrypted Well it reasons if it was M1 then the key must have been K M1 69 C 111 while if M2 was encrypted then the key must have been K M2 69 C 100 But either of these two was equally likely as the key so how do I know which of the two it was Here now is the formal statement and proof Claim 25 Let SE IC D be the OTP scheme with key length m 2 1 Assume we use it to encrypt a single message drawn from 01m Then 55 is perfectly secure I 8 A LOOK BACK Proof of Claim 25 As per De nition 23 for any M1M2 E 01m and any C we need to show that Equation 21 is true So let M1 M2 be any m bit strings We can assume C is also an m bit string since otherwise both sides of Equation 21 are zero and thus equal Now Pr KM1C PrKeaM1C K 01m KeM1C 071m 1 271 Above the probability is over the random choice of K from 01m with M1C xed We write the probability as the ratio of two terms the rst is the number of keys K for which K 69 M1 C and the second is the total possible number of keys The rst term is one because K can only be the string M1 69 C while the second term is 2m Similarly we have Pr KM2C PrK M2C K 01m KeM2C 071m 1 Tm In this case the numerator of the fraction is one because only the key K M2 69 C has the property that K 69 M2 C Now since the two probabilities we have computed above are equal Equation 21 is true and thus our proof is complete I Perfect security is great in terms of security but comes at a hefty price It turns out that in any perfectly secure scheme the length of the key must be at least the length of the single message encrypted This means that in practice a perfectly secure scheme like the OTP is prohibitively expensive requiring parties to exchange very long keys before they can communicate securely In practice we want parties to be able to hold a short key for example 128 bits and then be able to securely encrypt essentially any amount of data To achieve this we need to make a switch regarding what kinds of security attributes we seek As we discussed in the Introduction we will ask for security that is not perfect but good enough the latter interpreted in a computational sense Visualizing an adversary as someone running programs to break our system we will say something like yes in principle you can break my scheme but it would take more than 100 years running on the world s fastest computers to break it with a probability greater than 2 60 In practice this is good enough To get schemes like that we need some tools and this is what we turn to next 23 Problems Problem 21 Suppose that you want to encrypt a single message M 6 012 using a random shared key K 6 012 Suppose you do this by representing K and M using two bits 00 01 or 10 and then XORing the two representations Does this seem like a good protocol to you Explain I troduotion to odeling and mulation FiniteDifference Method for Boundary Value Problems Review I Boundaryvalue problems BVP a What is it and how do they differ from lVPs Give some example problems of BVP I Shooting method for BVP a How does it work a What are the limitations I Finitedifference method for BVP a How does it work Outline I Boundaryvalue problems in 1D 7 Example heat conduction on a rod 9 Types of boundary conditions I Generalization to two dimensions Steadystate heat conduction 39 1 A Concrete Example I Consider a rod has heat sources on both ends a and b Temperature would change until eventually it reaches a steady state I A steadystate problefm mm x W where KiS heat coefficient density of heat capacity and galsheat source sink if wlt0 or u x f x where fX 10XKX I We need two boundary conditions uaoc and ub3 I This is called a twopoint BVP F FiniteDifference Solution I Apply finitedifference method 1 Introduce mesh points x i01n1 with unknowns yfeux for i1n Replace u by centered difference approximation y 2y y J 1 112 11 fxj i We have linear system Ayf where 2 1 fx1 ah2 1 2 1 M A 1 72 1 r W h2 1 2 1 for 1 2 fag MW I This tridiagonal linear system can be easily solved I How accurate is the solution 39 Accuracy of Solution I Measure error by difference between y and exact solution 9 I From Taylor series expansion local truncation error 1 Tj uxjl 2MXjuxj1fxj h2u xj0h4 I Then A37 fr orAy I rso y A 1r I Smallest eigenvalue of A is bounded from below this is a stability condition so norm of error is 2ndorder accurate I Note that different from lVP local errors of BVP do NOT accumulate 39 1 Types of Boundary Conditions I The preceding problem has Dirichlet boundary condition 39 Value of u temperature is specified at boundary I Another common type is Neumann boundary condition First derivative u is specified at boundary I Note specifying Neumann BC on both ends would lead to illposed problem linear system is singular Eg specifying derivative to be 0 at boundary Solution for Neumann BC I Consider BC u ao and ub3 I If we use firstorder approximation of u solution would be only firstorder accurate I Introduce virtual point x1 and apply centered 1 finitedifference method we have glty1 2yoy1gtfltxogt I And linear system Ayf where ol mwmo h h 04 l y0y10kfxg 1 2 1 m2 h 2 Ai 1 72 1 r W h2 39 39 39 1 2 1 focm 1 2 fxn h2 1 Two Dimensional Generalization I Poisson equation uxx uyy f or V2u f 7 If fis 0 then called Laplace equation whose solutions are called harmonic functions I Consider Poisson equation on unit square with boundary conditions u1 for y1 uO elsewhere I Solution process Define discrete mesh in domain including boundaries We need to compute approximate solutions at interior grid points X yih jh for ij1 Assume square domain Basics of FiniteElement Method Outline I Collocation method I Weighted residual method I Galerkin method y Collocation Method Cont d I To determine vector of parameters X define set of n collocation points a t1lt n which approximate solution vt X is forced to satisfy ODE and boundary conditions Common choices of collocation points include equallyspaced points or Chebyshev points I Suitably smooth basis functions can be differentiated analytically so that approximate solution and its derivatives can be substituted into ODE and BC to obtain system of algebraic equations for unknown parameters X it Review I Hyperbolic equations 3 Derivation of advection equation 2 Descritization using LaxWendroff method Explicit secondrorder meiho I Artificial diffusionViscosity I Traffichow 2 Model density using advection equation iscretized using axWendroff met od nteresting features such as shocks and rarefaction fans Collocation Methods I Collocation method approximates solution to differential equations using linear combination of b 39 f tions asis unc I Example for twopoint BVP u ftuu 0lttlt1 with BC u0a u we seek approximate solution of form W vta 2 Mi 0 where are basis functions defined on 01 and a is rrvector of parameters to be determined a y Example of Collocation Method I Consider again twopoint BVP i 6 1th u 7 0lttlt1 W39 u00 u11 I To keep computation simple we use one interior point t 39 39 th 05 Including boundary points we have be able to determine three parameters As basis functions we use first three monomials so approximate solution as orm vra a0ar a2r2 I We have three39conditions two boundary conditions and second derivative and three unknowns a0 a a2 I ODE is satisfied exactly at grid points collocation poin squot t0 and t2 1 so we will


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.