Cryptography: History And Simple Encryption Methods And .

Cryptography:History and Simple Encryption Methodsand Preliminaries1

CryptographyThe word cryptography comes from the Greekwords κρυπτός (hidden or secret) and γράφειν(writing).So historically cryptography has been the “art ofsecret writing.”Most of cryptography is currently well grounded inmathematics and it can be debated whetherthere’s still an “art” aspect to it.2

Cryptography can be used atdifferent levels Algorithms: encryption, signatures, hashing,Random Number Generator (RNG) Protocols (2 or more parties): key distribution,authentication, identification, login, payment, etc. Systems: electronic cash, secure filesystems,smartcards, VPNs, e-voting, etc. Attacks: on all the above3

Some Applications of Cryptography Network, operating system security Protect Internet, phone, space communication Electronic payments (e-commerce) Database security Software/content piracy protection Pay TV (e.g., satellite) Military communications Voting4

Open vs. Closed Design Model Open design: algorithm, protocol, system design(and even possible plaintext) are public information.Only key(s) are kept secret. Closed design: as much information as possible iskept secret.5

Core Issue in Network security : Howto Communicate Securely?AliceBobLooks simple But, the devil is in thedetailsNote: even storage is aform of communicationEve(sdropper)6

The Biggest “Headache” is that Good security must beEffectiveYetUnobtrusiveBecause security is not a service inand of itself, but a burden!7

Cryptography is Old Most sub-fields in CS are fairly new (20-30 years):– Graphics, compilers, software, OS, architecture And, a few are quite old (more than severaldecades):– Cryptography, database, networking8

Some History: Caesar’s CipherHomoHominemLupus!KrprKrplqhpOxsxv!9

Some History: Rosetta Stone10

Some History: EnigmaAlan Turing(1912-1954)11

Historical (Primitive) Ciphers Shift (e.g., Caesar): Enck(x) x k mod 26 Affine: Enck1,k2(x) k1 *x k2 mod 26 Substitution: Encperm(x) perm(x) Vigenere: EncK(x) ( X[0] K[0], X[1] K[1], ) Vernam: One-Time Pad (OTP)12

Shift (Caesar) CipherExample:K 11W E W I L L M E E T A T M I D N I G H T22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 197 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4H P H T WW X P P E L E X T O Y T R S E How many keys are there? How many trials are needed to find the key?13

Substitution CipherExample:A B CD E FGH I J K L MN OPQR S T UV WX Y ZX N Y A H POG Z QWB T S F L RCV MU E K J D IKEYW E W I L L M E E TA T M I D N I G H TK H K Z B B T H H M X M T Z A S Z O G M How many keys are there? How many trials are needed to find the key?14

Substitution CipherCryptanalysisProbabilities of 280.0240.022 0.020.015A0.06 TUVWX0.001Y15Z

Substitution CipherCryptanalysisFrequency of some common ONORRETHTI16

VERNAM One-Time Pad (OTP):World’s Best CipherPlaintext { p0 ,., pn -1}One - time pad stream {otp0 ,., otpn -1}Ciphertext {c0 ,., cn -1}where :ci pi Å otpi"0 i nC AÅ BCÅB A17

VERNAM One-Time Pad (OTP):World’s Best Cipher Vernam offers perfect information-theoreticsecurity,but: How long does the OTP keystream need to be? How do Alice and Bob exchange the keystream?18

Encryption Principles A cryptosystem has (at least) five ingredients:–––––PlaintextSecret KeyCiphertextEncryption AlgorithmDecryption Algorithm Security usually depends on the secrecy of thekey, not the secrecy of the algorithms19

Crypto Basics20

Average Time Required for ExhaustiveKey Search (for Brute Force Attacks)Key Size(bits)Number ofAlternative KeysTime required at 106Decr/µs32232 4.3 x 1092.15 milliseconds56256 7.2 x 101610 hours1282128 3.4 x 10385.4 x 1018 years1682168 3.7 x 10505.9 x 1030 years21

Types of Attainable Security Perfect, unconditional or “information theoretic”: the securityis evident free of any (computational/hardness) assumptions Reducible or “provable”: security can be shown to be based onsome common (often unproven) assumptions, e.g., theconjectured difficulty of factoring large integers Ad hoc: the security seems good often - “snake oil” Take a look at:http://www.ciphersbyritter.com/GLOSSARY.HTM22

Computational Security Encryption scheme is computationally secure if– cost of breaking it (via brute force) exceeds the value of the encryptedinformation; or– time required to break it exceeds useful lifetime of the encryptedinformation Most modern schemes we will see are consideredcomputationally secure– Usually rely on very large key-space, impregnable to brute force Most advanced schemes rely on lack of knowledge of effectivealgorithms for certain hard problems, not on a proveninexistence of such algorithms (reducible security)!– Such as: factorization, discrete logarithms, etc.23

Complexity Reminder/Re-cap P: problems that can be solved in polynomial time, i.e., problems that can besolved/decided “efficiently” NP: broad set of problems that includes P; answers can be verified “efficiently” (in polynomial time); solutions cannot always be efficiently found (as far as we know). NP-complete: the believed-to-be-hard decision problems in NP, they appearto have no efficient solution; answers are efficiently verifiable, solution to oneis never much harder than a solution to another NP-hard: hardest; some of them may not be solved by a non-deterministicTM. Many computational version of NP-complete problems are NP-hard. Examples: Factoring, discrete log are in NP, not know if NP-complete or in P Primality testing was recently (2002) shown to be in P Knapsack is NP-completeFor more info, see: https://www.nist.gov/dads//24

P vs NP25

CryptosystemsClassified along three dimensions: Type of operations used for transforming plaintext intociphertext– Binary arithmetic: shifts, XORs, ANDs, etc. Typical for conventional encryption– Integer arithmetic Typical for public key encryption Number of keys used– Symmetric or conventional (single key used)– Asymmetric or public-key (2 keys: 1 to encrypt, 1 to decrypt) How plaintext is processed:– One bit at a time– A string of any length– A block of bits26

Conventional Encryption Principles27

Conventional (Symmetric) CryptographyK ABK ABplaintextmencryptionalgorithmciphertextK (m)decryptionalgorithmABplaintextm KAB(KAB (m) ) Alice and Bob share a key KAB which they somehow agreeupon (how?) key distribution / key management problem ciphertext is roughly as long as plaintext examples: Substitution, Vernam OTP, DES, AES28

Uses of Conventional Cryptography Message transmission (confidentiality): Communication over insecure channels Secure storage: crypt on Unix Strong authentication: proving knowledge of a secretwithout revealing it: See next slide Eve can obtain chosen plaintext, ciphertext pair Challenge should be chosen from a large pool Integrity checking: fixed-length checksum for message viasecret key cryptography Send MAC along with the message MAC H(m,K)29

Challenge-Response AuthenticationExampleK ABK ABchallengeraKAB(ra)rbchallenge replychallenge replychallengeKAB(rb)30

Conventional CryptographyØ Advantageslllhigh data throughputrelatively short key sizeprimitives to construct various cryptographicmechanismsØ Disadvantageslllkey must remain secret at both endskey must be distributed securely and efficientlyrelatively short key lifetime31

Public Key Cryptography Asymmetric cryptography Invented in 1974-1978 (Diffie-Hellman and Rivest-Shamir-Adleman) Two keys: private (SK), public (PK) Encryption: with public key; Decryption: with private key Digital Signatures: Signing by private key; Verification by public key. i.e.,“encrypt” message digest/hash -- h(m) -- with private key Authorship (authentication) Integrity: Similar to MAC Non-repudiation: can’t do with secret key cryptography Much slower than conventional cryptography Often used together with conventional cryptography, e.g., to encrypt session keys32

Public Key CryptographyBob’s public keyBob’s private keyPKBSKplaintextmessage, mencryptionalgorithmciphertextPK (m)BBdecryptionalgorithmplaintextmessagem SKB(PK (m))B33

Uses of Public Key Cryptography Data transmission (confidentiality): Alice encrypts ma using PKB, Bob decrypts it to obtain ma usingSKb. Secure Storage: encrypt with own public key, laterdecrypt with own private key Authentication: No need to store secrets, only need public keys. Secret key cryptography: need to share secret key for everyperson one communicates with Digital Signatures (authentication, integrity, nonrepudiation)34

Public Key CryptographyØ AdvantagesllllØonly the private key must be kept secretrelatively long life time of the keymore security servicesrelatively efficient digital signatures mechanismsDisadvantageslllllow data throughputmuch larger key sizesdistribution/revocation of public keyssecurity based on conjectured hardness of certaincomputational problems35

Comparison SummaryØPublic keylØConventionallØencryption, signatures (esp., non-repudiation) and keymanagementencryption and some data integrity applicationsKey sizeslKeys in public key crypto must be larger (e.g., 2048 bits for RSA)than those in conventional crypto (e.g., 112 bits for 3-DES or 256bits for AES) most attacks on “good” conventional cryptosystems are exhaustive keysearch (brute force) public key cryptosystems are subject to “short-cut” attacks (e.g.,factoring large numbers in RSA)36

Suggested Readings:Chapters 1 and 2 in KPS bookOptional: Ch 1 in StinsonDon't forget to check the website!Did you do it before this lecture?37

Most of cryptography is currently well grounded in mathematics and it can be debated whether there’sstill an “art” aspectto it. Cryptography. 3 Cryptography can be used at different levels Algorithms: encry