DOC PREVIEW
Columbia COMS 3156 - Implementation and Crypto

This preview shows page 1-2-17-18-19-35-36 out of 36 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 OptimizationKnuth’s laws of OptimizationFirst Law: Don’t!Second Law (for experts only): Not Yet!Try to get the thing working before you do any optimization4Requirements Tweaking1.2 revisionAnother full iteration would be nice, but not happening5Req Bug FixesDamage now an intZapped a few IDREFsExKicked goneGetMapData deprecated, probably gone soonPortal now has ID, instead of IP/port6Chat ChangeAll chat start/ends now broadcast in the ever-fattening MapDelta7Items Have SendTextYou’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 OperatorsBoolean tests and setting/clearing assignmentsisBitSet / isBitClearsetBit / clearBit9Bit FlippingFilter (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 Expressionshttp://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, acBut not–aaaabbc, ab12Expressions Can Be FancyAb[xyz]c matches–Abxc, Abyc, and Abzc onlyAb[0-9]c matches–Ab3c, Ab8c, etc.Ab[a-zA-Z3]c matches–Abqc, AbLc, Ab3c–But not Ab6c or Abxxc13Can Put The Two TogetherAb[xyz]*c matches–Abxyzc, Abc, AbzzxcAb[0-9]?c matches–Abc, Ab8c, Ab3c14Specials‘.’ Matches any characterAb.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 notesShell has decent regexpGnu.regexp has sample appletThe 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 envy16Makehttp://www.gnu.org/manual/make-3.79.1/html_node/make_toc.html Java has it built in, so rarely seen in CS classesBunch of compilation rules17Make RulesTarget(s): prerequisitesCommandCommand…Target is file or patternPrerequisite is file on which Target dependsCommands are what to doTAB 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 FeaturesImplicit rules: already knows how to make common types, e.g. .o from .cIs smart about timestampsCan have shell-like variablescc –M can generate makefilesAutomatic variables20AlsoAutoconf/configureAnt–Java/xml solutionJava’s auto-dependency calculation is still the slickest21CryptoFull semester topicWe’re only going to touch on some conceptsAn introduction for future study22P vs. NPNot PvPQ: 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 ProblemsE.g. sorting a list of size nFinding an item in a listEtc.24NP: Verifiable in Polynomial TimeIf I give you the correct answer, you can verify that it’s correct in polynomial timeNonetheless, no one can figure out how to find the answer in polynomial timeE.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-CompleteA large class of problems, all of which are NPIt 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 timeFame and fortune awaits…26Sample NP ProblemsTravelling salesmanFactoringKnapsackBin packingInteger programmingMany more…27So What?These are useful for cryptoEasy to check, difficult to findIf 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 ConceptsPrivacyAuthenticationAuthorizationNon-repudiabilitySymmetric vs. Asymmetric keysKey managementOne-way hashes29PrivacyWhat we usually associate with cryptoScrambling plaintext so that it’s unreadableShould be resistant to attacks–Even if attacker has unlimited access to plaintext/encrypted text pairs–Even if (especially if) encryption algorithm is knownDo not try to invent one on your own–Rot-1330AuthenticationI am who I say I amPasswordsBiometricsRestricted access31AuthorizationGiven that I’m authenticated, controlling what I can doAccess Control ListsKerberos ticketsWin2K security system32Non-RepudiabilityInability to say “I didn’t send that. Someone else must have sent that pretending to be me”Symmetric keys are good for this33Symmetric/Asymmetric KeysSymmetric: single key to encrypt and decryptVery fast, Very secureBut if I can get the key to you securely, what do I need crypto for?Asymmetric: public and private keysIf encrypted with public, private will decrypt, and vice versa34Public-key CryptoSo I encrypt my message with my private key–You can decrypt with my public key–You know it must have come from meAnd then re-encrypt with your


View Full Document

Columbia COMS 3156 - Implementation and Crypto

Download Implementation and Crypto
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Implementation and Crypto and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Implementation and Crypto 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?