Selected Topics CIS 400
Popular in Course
Popular in Computer & Information Science
This 19 page Class Notes was uploaded by Sam Rau on Wednesday October 21, 2015. The Class Notes belongs to CIS 400 at Syracuse University taught by Staff in Fall. Since its upload, it has received 33 views. For similar materials see /class/225601/cis-400-syracuse-university in Computer & Information Science at Syracuse University.
Reviews for Selected Topics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/21/15
Proofs from the Board 018 400628 Spring 2005 Theorem 11 a if dia and ail then dib By the de nition of 377171 9 a dm and b na b ndm dnm 7 dib D b d a ltgt 1 7 a First7 Assume 1 7 a By defn7 3n 9 7a dn a 7dn a d7n d a Now for lt Assume dia By defn7 3m 9 a dm 7a 7dm 7a d7m 1 7 a D f if a 7 0 and dia then d g M By defn7 a bd iai ibdi W W a a 7 07 so I 7 0 w 2 1 iai W W Z 1 idi W j if dia and dib then Mam by for arbitrary 71 6 Z By defn7 a md and b nd for some mm 6 Z axbymdmndydmmny D Division Algorithm Suppose 011 6 Z and b gt 0 Then 3 unique q and r such that a q I r and 0 g r lt b De neS a7zblmEZanda7mb20 Show that S is not empty choose z 7a We know a b E Z from the theorem statement so m 7a E Z a7xba77al b aa b alalb2alal bgt0 alal20 ifa 0alal0ifagt0ala2a So a 7 ml 2 O and so it is in S ie S is not empty Notice by defn that S Q N ie all elements of S are greater than or equal to 0 Therefore if 0 E S then 0 is the smallest element lf 0 is not in S then the Well Ordering Axiom assures us that there is some least member of S Call this smallest element whether 0 or not r Then by the defn of S Sq such that a 7 qb r and a qb r This is the proper form but we must still show three things 1 T Z 0 2 r lt b 3 q r are a unique solution 1 r E S and as all elements of S are in N r 2 O 2 proof by contradiction Assume r 2 I Then T 7 b 2 0 and r 7 b a 7 qb 7 b q7 q1b so r71 6 S see the de nition of S and substitute q 1 for m This contradicts r being the least element of S r lt b 3 Suppose there is another representation such that a qlb n then bq 7 bqq T1 7 r W 7 611 r1 7 r lbq7q1l Mid blq7q1 7177 From steps 1 and 2 we know that 0 g r lt b and blq 7 qll lt b However for integers the only way this inequality can hold is if q7 qll O or equivalently q ql But if q ql then r 71 as well D Theorem 13 For a b 6 24 if gcda 1 exists it is unique Proof by contradiction Assume there are two integers m and n that are each a gcda 1 Then by de nition mia mib nia nib The defn of gcd says ciaampcib cid m is a gcda b so nia nib nim Symmetrically n is a gcda b so mia mib min So both min and nim From Theorem 11 i if aib and bia then a ib so m in But the de nition of gcd says it must be positive so m 71 D Theorem 14 Proof of Claim 1 dia and dib Recall that d is the least element of S From the diVision algorithm Sq r such that a qd i r and 0 g r lt d We can rewrite a qd r as r q 7 gal a7 qaz1 byl a7 goal 7 qbyl a17 qm1b7qy1 This is the proper form to be in S if r gt 0 But r lt 1 so if r E S then this contradicts 1 being the least member of S r 0 and thus a qd so dia We can do the same demonstration for b so dib Proof of Claim 2 cia amp cib cid Assume cia amp cib then 3mm 6 Z such that a cm and b on So 1 an i byl cmml cnyl Cmml nyl so cid Towards a GCD Algorithm Why 1 Why does the induction hypothesis make 1 gcdbr By the induction hypothesis 1 gcdb r because r lt b so r is found in A1A2 Ab71 the induction hypothesis assumes that Va far gcda r so fb r gcdbr Why 2 Given a qb i r Why does digcdab7 By the defn of gcd dib 3mg such that b md amp r nd So a qmd nd dqm i Thus dia By the second part of the gcd defn dia and dib digcda b Why 3 Why does gcdabld7 gcdab is the smallest positive integer express as a linear combi nation of a and b By the corollary to Theorem 14 any linear combination of a and b is a multiple of gcda b d was expressed as a linear combination of a and b so gcda bld Why 4 Why is d gcdab By Theorem 11 i if all and bla then a ib But both 1 and gcda b are positive so 1 gcda 1 Theorem 15 Vab E Z a b 7 O p is a positive prime plab pla or plb Proof by contradiction assume p la Then gcdap 1 p is prime so its only factors are i1 and ip if p la then the only possible positive common divisor is 1 1 am 1 pg by theorem 14 so multiply both sides by b yielding b ham 1 bpy abzpby Theorem 11 states that ifdla and dlb then dlamby for arbitrary m y E Z As stated in the theorem plab and obviously plp so p divides the linear combination abm pby which is the same as saying plb We can use the same reasoning to show that if we start assuming p lb then pla Theorem 16 Proof by induction Let Sn be the statement if plalag an then plai for at least one i 1 g i g 71 Base case 51 if plal then plal A tautology and obviously true lnduction hypothesis Assume Sk is true Show Sk 1 is true as well We are given pla1a2 akak1 Note that a1a2 akak1 a1a2 akak1 From theorem 15 if plzy then either plx or ply So either plak1 or pla1a2 ak The former case obviously satis es the requirement and by the induction hypothesis the latter case does as well KEY AGREEMENT PROTOCOLS CIS 400628 Spring 2005 Introduction to Cryptography This is based on Chapter 13 of Trappe and Washington DIFFIEHELLMAN KEY EXCHANGE Alice amp Bob want to exchange a ton of data using the nice amp fast AES cryptosystem But first they have to agree on a key DiffieHellman Setup p a large prime Public and 04 a prim elem of Z Public Alice Chooses as E Z111 Private and sends of mod p to Bob Bob ran Chooses y E Z111 Private and sends ay mod p to Alice Alice Computes k ay 393 2 awy mod p Bob Computes k 06 3 awy mod p Eve Knows of mod p and my mod p Wants ax39y mod p 1 THE MANlNTHEMIDDLE ATTACK Alice lt gt Eve lt gt Bob Eve ran Chooses z E ZZ1 Intercepts 049 and ay Sends of to Alice and Bob Eve computes kAE 04z and kBE 06 Alice believes she has exchanged a key with Bob Bob believes he has exchanged a key with Alice Eve reads everything amp sends whatever she wants spoofing Alice amp Bob We need to fix this 2 STATION TO STATION STS PROTOCOL Use signatures amp a trusted authority Trent to defend against maninthemiddle Setup Each user U has sigU a signature algorithm verU a verification algorithm established by Trent p a prime 04 a prim elem of z Alice ran Chooses a E ZZ1 and computes 04 mod p Bob 21 Chooses y rem Z1 and computes ay mod p More STATION TO STATION CONTINUED Alice Sends of to Bob Bob Computes k 06 3 amp say AES Sends ay and EKsigBay 0573 to Alice Alice Computes K OH Decrypts EKsigBay 0573 and obtains sigBay of Asks Trent to verify that verB is Bob s verification alg Uses verB to verify Bob s signature Sends EKsigAof ay to Bob Bob Decrypts EKsigAoz 393 ay amp obtains sigAo 3 ay Asks Trent to verify that verA is A s verification alg Uses verA to verify Alice s sig What is Eve to do 4 KEY PREDISTRIBUTION Key Distribution A TA Trent and I1 users a secure channel between TA and each User TA sends K to n users securely Key Agreement Two users a public network The users interact to agree on a key K Key PreDistribution TA and n users a public network a secure channel between TA and each User For each pair of users U V U 75 V The TA constructs a key KUV 2 KVU and sends it to U and V securely messages too many each user stores n 1 keys too many 5 BLOM S DISTRIBUTION SCHEME gt p prime with p gt n of users gt Keys chosen from Zp SETUP TA Chooses p as above public For each user U chooses TU E Zp public U75V gt TU 75 Tv Chooses a b c r n Zp private For each user U the TA computes ay 2 a b TU mod p private by b c TU mod p private and sends them securely to U Each user U Constructs gUac 2 cm by ac When Alice amp Bob want to communicate Alice computes KAB gArB and Bob computes KBA gBrA CLAIM KAB KBA proof on board BREAKING BLOM S SCHEME I Eve wants to determine a b and 0 She knows LE 2 a b o TE 1 b C TE Two equations three unknowns no dice Eve also wants to determine KAB She knows KAB ab TA I BC TA I B LE 2 a b o TE 1 b C TE Three equations four unknowns a b c and KAB Fact For every possible value of KAB there is a solution for a b and 0 But what if Eve has a friend 7 Alice Chooses k and sends it to securely to Bob TRANSPORT PROTOCOLS OR Trent The TA acts as a key server Alice wants to talk to Bob She tells Trent amp Trent issues a key to Alice and Bob for the session Shamir s Three Pass Protocol Alice Alice Bob Alice Bob Alice Bob Here Trent Alice Publishes a prime p with a hard disc log problem Chooses a 1 Z111 a L E a L modp 1 Chooses b 1 Z111 b lL Sends K1 2 K mod p to Bob Sends K2 2 K mod p 10 mod p to Alice Sends K3 2 K371 mod p 2 Kb mod p to Bob E b1modp 1 Computes K 2 K51 mod p Maninthemiddle problems 9 KERBEROS I Clients users processes Servers gateways The Dramatis Personae Cliff a client Serge a server Trent a TA authentication server Grant a ticket granting server Before Cliff and Serge share no secret data After Serge will have verified Cliff s ID A session key for Cliff and Serge will have been established Background The following is all symmetric key cryptography 1 2 3 KERBEROS l See drawing on board Cliff gt Trent Requests ticket to ticketgranting server Cliff supplies his name and Grant s name Trent gt Cliff Checks out Cliff and if OK Generates KCG Sends Cliff T de eKCKCG KC Cliff s secret key Constructs TGT def Grant s ID eKGCliff s ID timestamp1KCG Sends Cliff TGT Cliff gt Grant Decrypts T to obtain ch Constructs AuthCG def eKCGCIiff s lDtimestamp2 Sends TGT and AuthCG to Grant KG Grants s secret key KERBEROS III See drawing on board 4 Grant gt Cliff Grant decrypts TGT and obtains Cliff s ID ch and timestamp1 Decrypts AuthCG and obtains Cliff s ID and timestamp2 Checks that the two versions of Cliff s ID match Checks that the two timestamps are suff close If OK Grant generates K05 the CliffSerge session key Generates ServeTicket def eKSCIiff s ID timestampg ExpTime K05 Sends ServTicket and eKCGKCS to Cliff ExpTime how long K05 is good for KS Serge s secret key KERBEROS IV 5 Cliff gt Serge Cliff decrypts eKCGKCS and obtains K03 Cliff constructs Authcs def eKCSCIiff s ID timestamp4 Cliff sends Authcs and ServTicket to Serge Serge Decrypts ServTicket to obtain Cliff s ID timestampg ExpTime and K03 Using K05 decrypts Authcs to obtain Cliff s ID timestamp4 Checks that the two versions of Cliff s ID match Checks that timestamp4 g timestamp3 ExpTime If OK Cliff and Serge can chat using K03 PUBLIC KEY INFRASTRUCTURES PKIS Public Key Infrastructure A set of protocols for publishing and certifying keys Certificate Some information signed by its publisher a certification authority gt identity certification id email address public keys gt credential certification access rights See 144 of TampW for more detail This is a possible final paper topic NEXT INFORMATION THEORY