Software Engineering 3156AdministriviaA Note on OptimizationRequirements TweakingReq Bug FixesChat ChangeItems Have SendTextBit Flipping OperatorsBit FlippingRegular ExpressionsSimplest Form: wildcardsExpressions Can Be FancyCan Put The Two TogetherSpecialsRegexp notesMakeMake RulesExampleOther FeaturesAlsoCryptoP vs. NPP: Polynomial Time ProblemsNP: Verifiable in Polynomial TimeNP-CompleteSample NP ProblemsSo What?Key Security ConceptsPrivacyAuthenticationAuthorizationNon-RepudiabilitySymmetric/Asymmetric KeysPublic-key CryptoPublic-key continuedOne-way HashesSoftware Engineering 315631-Oct-01#17: Implementation and CryptoPhil Gross2Administrivia3A Note on OptimizationKnuth’s laws of OptimizationFirst Law: Don’t!Second Law (for experts only): Not Yet!Try to get the thing working before you do any optimization4Requirements Tweaking1.2 revisionAnother full iteration would be nice, but not happening5Req Bug FixesDamage now an intZapped a few IDREFsExKicked goneGetMapData deprecated, probably gone soonPortal now has ID, instead of IP/port6Chat ChangeAll chat start/ends now broadcast in the ever-fattening MapDelta7Items Have SendTextYou’ve got Gold!Should accompany most changes to character–Player Gold stat goes up by 10–Message says “You found Gold!”–Chest replaced with empty, scriptless chest.8Bit Flipping OperatorsBoolean tests and setting/clearing assignmentsisBitSet / isBitClearsetBit / clearBit9Bit FlippingFilter (Status, isBitSet, 13):if ((Status & (1 << 13)) != 0) {…isBitClear would have “== 0”Effect (Status, setBit, 13) isStatus |= (1 << 13);Clear bit 13:Status &= ~(1 << 13);10Regular Expressionshttp://www.perldoc.com/perl5.6/pod/perlre.html –Yikes!http://www.oreilly.com/catalog/regex/ –Double Yikes!We’ll use Gnu.regexp–http://www.softe.cs.columbia.edu/jars/gnu.regexp-1.1.4/docs/index.html11Simplest Form: wildcards* matches 0 or more of preceding expression? matches 0 or 1+ matches 1 or more–aa* = a+So a*b?c+ matches…–aaaabc, cc, bcccc, acBut not–aaaabbc, ab12Expressions Can Be FancyAb[xyz]c matches–Abxc, Abyc, and Abzc onlyAb[0-9]c matches–Ab3c, Ab8c, etc.Ab[a-zA-Z3]c matches–Abqc, AbLc, Ab3c–But not Ab6c or Abxxc13Can Put The Two TogetherAb[xyz]*c matches–Abxyzc, Abc, AbzzxcAb[0-9]?c matches–Abc, Ab8c, Ab3c14Specials‘.’ Matches any characterAb.c matches–Abac, Abzc, Ab8c, Ab!c, etc.Usually seen as .*–Foo.*bar matches any string that starts with Foo and ends with bar, regardless of length\. is literal ‘.’15Regexp notesShell has decent regexpGnu.regexp has sample appletThe curse of the Perl legacy–Ultimate regexp implementation–With that lovely Perl syntax–Arguably two languages in one–Debatable which is more complex–Now everyone else has Perl envy16Makehttp://www.gnu.org/manual/make-3.79.1/html_node/make_toc.html Java has it built in, so rarely seen in CS classesBunch of compilation rules17Make RulesTarget(s): prerequisitesCommandCommand…Target is file or patternPrerequisite is file on which Target dependsCommands are what to doTAB BEFORE COMMAND18Exampleedit : main.o kbd.o command.o display.o \ insert.o search.o files.o utils.o cc -o edit main.o kbd.o command.o display.o \ insert.o search.o files.o utils.omain.o : main.c defs.h cc -c main.c Etc.\ is continuation character19Other FeaturesImplicit rules: already knows how to make common types, e.g. .o from .cIs smart about timestampsCan have shell-like variablescc –M can generate makefilesAutomatic variables20AlsoAutoconf/configureAnt–Java/xml solutionJava’s auto-dependency calculation is still the slickest21CryptoFull semester topicWe’re only going to touch on some conceptsAn introduction for future study22P vs. NPNot PvPQ: What is a “fast” algorithm?A: Polynomial in the length of input–O(nk)Q: So what’s slow?A: Exponential–O(kn)23P: Polynomial Time ProblemsE.g. sorting a list of size nFinding an item in a listEtc.24NP: Verifiable in Polynomial TimeIf I give you the correct answer, you can verify that it’s correct in polynomial timeNonetheless, no one can figure out how to find the answer in polynomial timeE.g. factoring a number–If I give you the factors, just multiply them together to verify–If I give you a 500-digit number, how to find the factors?25NP-CompleteA large class of problems, all of which are NPIt has been proven that if any member of this class can be solved in polynomial time, then all NP problems can be solved in polynomial timeFame and fortune awaits…26Sample NP ProblemsTravelling salesmanFactoringKnapsackBin packingInteger programmingMany more…27So What?These are useful for cryptoEasy to check, difficult to findIf reading a message is dependent on factoring a number (or knapsack problem, or elliptical equations), I can just tell you the solution, and you can instantly decrypt–And be confident no one will be able to determine the solution by brute force before the heat-death of the universe28Key Security ConceptsPrivacyAuthenticationAuthorizationNon-repudiabilitySymmetric vs. Asymmetric keysKey managementOne-way hashes29PrivacyWhat we usually associate with cryptoScrambling plaintext so that it’s unreadableShould be resistant to attacks–Even if attacker has unlimited access to plaintext/encrypted text pairs–Even if (especially if) encryption algorithm is knownDo not try to invent one on your own–Rot-1330AuthenticationI am who I say I amPasswordsBiometricsRestricted access31AuthorizationGiven that I’m authenticated, controlling what I can doAccess Control ListsKerberos ticketsWin2K security system32Non-RepudiabilityInability to say “I didn’t send that. Someone else must have sent that pretending to be me”Symmetric keys are good for this33Symmetric/Asymmetric KeysSymmetric: single key to encrypt and decryptVery fast, Very secureBut if I can get the key to you securely, what do I need crypto for?Asymmetric: public and private keysIf encrypted with public, private will decrypt, and vice versa34Public-key CryptoSo I encrypt my message with my private key–You can decrypt with my public key–You know it must have come from meAnd then re-encrypt with your
View Full Document