Public Key Cryptography - Villanova
11/13/14Chapter 22Outline Public key cryptography" Confidentiality" Authentication" Integrity" Non-repudiation Key Generation" DH (Diffie-Hellman)" RSA (Rivest-Shamir-Adleman) Public Key Certificates and PKI1
11/13/14Public key concept Confidentiality without a shared secret" Two parties must share a secret before they can exchange secret messagesusing symmetric �spublickey Sender, receiver do not share secret key Each uses a pair of related keys (private, public) Private decryption key known only to receiver Public encryption key known to allPublic Key Confidentiality Example" Alice wants to send a secret message to Bob0110111010010001 key KBob,public(Alice) The quick brown foxencrypt4f60ce544b43c13f1d(Bob) 4f60ce544b43c13f1ddecryptThe quick brown fox1001001100111010 key KBob,private2
11/13/14Public Key Authentication Example" Bob wants to authenticate the message as coming from Alice0110111010010001 key KAlice,private(Alice) The quick brown foxencrypt4f60ce544b43c13f1d(Bob) 4f60ce544b43c13f1ddecryptThe quick brown fox1001001100111010 key KAlice,public In reality, the hash of the message is encrypted with the private key to provide adigital signatureDigital Signatures(Alice) The quick brown fox.85d013f4 (digest)hash function0110111010010001 key KAlice, privateencrypt85d013f4The quick tynAutheticationdRepuNon-iation(send to Bob)0110111010010001 key KAlice, public(Bob extracts signature) a3ff369bThe quick brownred fox.fox.decrypthash function85d013f4 (digest)Bad!OKad917c7f85d013f43
11/13/14Enable unknown parties’ securecommunications Exchange messages to create a secret session key" Use Amazon’s public key to encrypt a secret key""Then switch to symmetric cryptographyFaster using symmetric key c KeyInfrastructureOutlineAmazon’spublickey Public key cryptography" Confidentiality" Authentication" Integrity" Non-repudiation Key Generation" DH (Diffie-Hellman)" RSA (Rivest-Shamir-Adleman) Public Key Certificates and PKI4
11/13/14Diffie-Hellman Protocol Invented by Diffie and Hellman in 1976 Alice and Bob have never met and share no secrets but need a shared key Public info: p and g"p is a large prime number, g is a power generator for the set Zp {1,2, p-1}µ ForanyxinZp,thereisasuchthatx ,andggbmodpSharedkeyk gabmodpComputek (gamodp)b gabmodpComputek (gbmodp)a gabmodp THE FOLLOWING IS AN ASSUMPTION (BELIEF)"Given gx mod p it is mathematically hard to extract xShared Key in Diffie-Hellman Protocol One-time generation of an appropriate prime p and power generator g, 2 g p 2 Perform the following steps each time Alice (A) and Bob (B) need a shared key" Alice (A) chooses a random secret a, 1 a p 2, and sends B the message gamod p, along with p and g" Bob (B) chooses a random secret b (as his private key), 1 b p 2, and sendsA the message gb mod p" B receives ga mod p and computes the shared key as k (ga mod p)b mod p" A receives gb mod p and computes the shared key as k (gb mod p)a mod p" k (ga mod p)b mod p gab mod p (gb mod p)a mod p Example p 7 and g 3:" Alice’s private key 5, Bob’s private key 4" Alice’s public key 35 mod 7 5, Bob’s public key 34 mod 7 4" Alice’s shared key 45 mod 7 2, Bob’s shared key 54 mod 7 25
11/13/14Man-in-the-middle attack The Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack"An opponent Eve intercepts Alice's public key and sends her own public key to Bobµ erownEandsendsittoAliceµ eonanothersharedkeyµ utbyAliceorBob,readsandmodifiesthembeforere- artySolution to man-in-the-middle attack The man-in-the-middle attack vulnerability is present because Diffie-Hellman keyexchange does not authenticate the parties The Station-to-Station (STS) protocol was developed by Diffie, van Oorschot, and Wiener in1992 to defeat the man-in-the-middle attack""Add digital signatures, signed by the private key, for both ga mod p and gb mod p in theexchange messagesEve cannot forge signatures without compromising both Alice's private key and Bob'sprivate key6
11/13/14 Public key cryptography" Confidentiality" Authentication" Integrity" Non-repudiationOutline Key Generation" DH (Diffie-Hellman)" RSA (Rivest-Shamir-Adleman) Public Key Certificates and PKIRSA Public Key Crypto Invented by Rivest, Shamir, Adleman in 1977 Key generation:" Generate large primes p, qµ typically1024bitsormoreinlength""Compute n pq and ϕ(n) (p-1)(q-1); n is about 2048 bits in lengthChoose small e, relatively prime to ϕ(n), and 1 e ϕ(n)""Compute unique d such that ed 1 mod ϕ(n) and 1 d ϕ(n)Public key (e, n); private key (d, n)µ Typically,e 216 1 65537orlarger Encryption of m: c me mod n Decryption of c:cdmod n m nmod n m(me)d7
11/13/14RSA Example Select primes: p 5, q 7 Calculaten pq 5 x 7 35ϕ(n) (p–1)(q-1) 4 x 6 24 Select e:gcd(e, 24) 1; choose e 5 Determine d: de 1 mod 24 and d 24 d 5 since 5 x 5 25 4 x 6 1 Public key (5, 35) and private key (5, 35) Calculate Given message m 9 ( 9 35)" Encryption:µ c 95mod35 59049mod35 4"Decryption:µ m 45mod35 1024mod35 9Public-Key Encryption Key generation:" Computationally feasible to generate a pair of (public key PK, private key SK)" Computationally infeasible to determine private key SK from public key PK The size of a key in the RSA algorithm typically refers to the size of the modulus n" The two primes, p and q, which compose the modulus, should be of roughly equallengthµ mesismuchsmallerthantheotherµ Ifonechoosestousea2048- mately1024bits8
11/13/14Disadvantages of RSA Public-Key Crypto Public key crypto computation is 3 orders of magnitude slower than symmetriccrypto""Modular exponentiation is an expensive computationTypical usage: use public-key cryptography to establish a shared secret, thenswitch to symmetric cryptoµ IPsec,SSL,PGP,etc. Keys are longer for the same strength" 2048 bits (RSA) rather than 128 bits (AES) Relies on unproven assumptions that factoring of p and q from given n iscomputationally infeasibleRSA ChallengeSponsored by RSASecurity Let n be an RSA Number There are primenumbers p and qsuch that n pqThe problem is tofind these twoprimes, given only nUse massively parallelsupercomputer to solvethe yRSA- ‐100RSA- ‐110330364April1991April1992RSA- ‐120RSA- ‐129RSA- ‐130RSA- ‐140397426430463 100USDJune1993April1994April1996February1999RSA- rmanJ.J.teRieleetal.KazumaroAokietal.RSA- ‐155512August1999RSA- ‐160530April2003RSA- ‐576576 10,000USDRSA- ‐640640 20,000USDRSA- ‐200663RSA- ‐704RSA- ‐768704768 30,000USD 50,000USDRSA- ‐1536RSA- ‐204815362048 150,000USD ry24,T.Kleinjungetal.,EPFLICLACAL2010openopen9
11/13/14RSA vs. DH RSA: DH:" Generates a pair of (public,private) keys" Provides encryption anddecryption" For key agreement" For signature" Generates one shared key" Does not provide encryption anddecryption (use with DES or AES)" For key agreement" Not for signatureElliptic Curve Cryptography (ECC) Elliptic curve (EC) cryptography is the next generation of public key cryptography Uses elliptic curves over finite fields (variables and coefficients are finite)" E.g. y2 x3 ax b Given an elliptic curve and points G and Q the curve, Q d*G" Q: public key" d: private key It is feasible to compute Q given d and G" But it is infeasible to find d given Q and G10
11/13/14ECC Applications Key Agreement" ECDH: Elliptic Curve Diffie-Hellmanµ AllowstwoparDes,eachhavinganellipDccurvepublic- securechannel[ Shared secret maybe directly used as a key, or to derive another key which willbe used to encrypt subsequent communication using a symmetric key cipher Digital Signatures" ECDSA: Elliptic Curve Digital Signature Algorithm Benefits" Primary benefit is a smaller key size, for example a 256-bit ECC public key shouldprovide comparable security to a 3072-bit RSA public key" Requires less computing powerµ Goodformobiledevices"Better securityOutline Public key cryptography" Confidentiality" Authentication" Integrity" Non-repudiation Key Generation" DH (Diffie-Hellman)" RSA (Rivest-Shamir-Adleman) Public Key Certificates and PKI11
11/13/14Root of Internet security: Public-Key Crypto Confidentiality without a shared secret" Two parties must share a secret before they can exchange secret messages usingsymmetric crypto Make sure that Alice’s public key is AUTHENTIC" Need a PUBLIC KEY INFRASTRUCTURE for authentication of public keyµ CerDficateauthority(CA)µ lickeyDistribution of Public Keys Public-key certificate" Signed statement specifying the key and identity PUBLIC KEY INFRASTRUCTURE" Certificate authority (CA)µ ResponsibleforcerDfyingpublickeyforAliceµ Re- ‐issuanceofcerDficateswhenitexpires""After Alice generates a private/public key pair, she proves her identity andknowledge of the private key to obtain the CA’s certificate for the public key(offline or online)Certificate: sigCA(“Alice”, PKAlice) “Alice” PKAliceEvery host is pre-configured with CA’s public key in a certificate"Every router/switch can be equipped with CA’s public key in a certificate as well"µ RootCAcerDficate12
11/13/14Public-Key Infrastructure and publickey,PKverisignCA:VerisignHash functionVerisign’sprivate rtificatesare installedby Microsoft,Apple,Firefox, etc.Verify Amazon’s certificateusing PKverisignClick here for security info13
11/13/14Unencrypted connectionEncrypted connection14
11/13/14TLS ECDHE RSA WITH AES 128 GCM SHA256 Amazon HTTPS servers use ECDHE RSA WITH AES 128 GCM SHA256" TLS (Transport Layer Security) is used to transfer data between client and server""""ECDHE (Elliptic Curve Diffie Hellman Ephemeral) is used to derive the secret key (128bits long) for data encryptionRSA is used to verify server’s identity. The server’s public key is then used to exchangethe shared ECDHE keyClient and server use the ECDHE shared key to encrypt data using AES-128 (AdvancedEncryption Standard) and encryption mode GCM (Galois Counter Mode)SHA256 is not needed for integrity here (AES provides integrity and confidentiality), butit may be used to provide integrity of the TLS handshake process.Certificate summary15
11/13/14X.509 Certificate formatCertificateVersionSerial NumberAlgorithm IDIssuerValidityNot BeforeNot AfterSubjectSubject Public Key InfoPublic Key AlgorithmSubject Public KeyIssuer Unique Identifier (Optional)Subject Unique Identifier (Optional)Extensions (Optional).Certificate Signature AlgorithmCertificate SignatureVersionSerial No.Signature AlgorithmIssuerValid periodSubjectSubject Public Key InfoExtensionsSignature Algo.Signature ValueCertificatedetailsVersionSerial No.Signature AlgorithmIssuerValid periodSubjectSubject Public Key InfoExtensionsSignature Algo.Signature Value16
11/13/14CertificatedetailsVersionSerial No.Signature AlgorithmIssuerValid periodSubjectSubject Public Key InfoExtensionsSignature Algo.Signature ValueSignedbyVerisignCertificates Classes VeriSign introduced the concept of classes of digital certificates:" Class 1: for individualsµ Foremail"Class 2: for organizations"Class 3: for server identity and software signing""Class 4: for online business transactions between companiesClass 5: for government securityµ ForproofofidenDtyµ gcerDficateauthority(CA)17
11/13/14Hierarchical Approach Trusted root authority" For example, Verisign" Every host must know the public key for verifying root authority’s signaturesµ dµ isinstalled"Multiple trusted root CAs Root authority signs certificates for lower-level authorities, lower-level authoritiessign certificates for individual users, and so on"Instead of a single root CA certificate, use a certificate chainµ ��,PKAlice)µ ificate chain, aka certification path Before a certificate is trusted, it must be verify that it comes from a trusted source" This verification process is called path validationµ unDlthecerDficaDonpathterminatesatatrusted,self- ‐signedcerDficate[ Typically, this is a root CA certificate18
11/13/14Certificate Revocation Reasons to revoke a certificate" Private key corresponding to the certified public key that has been compromised" Host/user/organization changes Certificate revocation list (CRL)" CA periodically issues a signed list of revoked certificatesµ creditcardnumbers""CA issues a “delta CRL” containing only updatesUnique serial number is used to check CRL A host/router/switch can be configured to check against lopment The Public-KeyCryptographyStandards (PKCS)are a set ofstandards for publickey cryptography,developed by RSALaboratories incooperation with aninformal consortium,originally includingApple, Microsoft,DEC, Lotus, Sun ie- schannel.Extended- ge).Private- ‐KeyThisstandarddescribessyntaxforprivate- orsomepublic- allysignedmessages,PKCS#8private- ‐keyinformation,andPKCS#10certificate- eycertificates,protectedwithapassword- ‐basedsymmetrickey.EllipticCurvePublic- yptographyStandard19
11/13/14 2 Public key concept Sender, receiver do not share secret key Each uses a pair of related keys (private, public) Private decryption key known only to receiver Public encryption key known to all �s(public(key( Confidentiality without a shared secret " Two parties must share a secret before they can exchange secret messages
VILLANOVA UNIVERSITY CATALOG (USPS348770) is published each year by Villanova University, Villanova, PA 19085. Second-class postage paid at Villanova, PA, and additional mailing offices. POSTMASTER: Send address changes to Villanova University Catalog, Tolentine 105, Villanova University, 800 Lancaster Avenue, Villanova, PA 19085.
christine.etheridge@villanova.edu Contact regarding: MBA Alumni Association SHANNON MARRERO Assistant Director Student Services 610-519-5455 shannon.marrero@villanova.edu Contact regarding: MBA Programs and Services Academic Advising - Last names A-L ANTHONY PENNA Assistant Dean Graduate Business Programs 610-519-6570 anthony.penna@villanova.edu
of public-key cryptography; providing hands-on experience with some of the most common encryption algorithms that are used on the internet today. Modern Cryptography Introduction Outline 1 Introduction 2 Historical Cryptography Caesar Cipher 3 Public{Key Cryptography
Villanova University Charles Widger School of Law Year 2004 The First Amendment, The Public-Private Distinction, and Nongovernmental Suppression of Wartime Political Debate Gregory P. Magarian Villanova University School of Law, magarian@law.villanova.edu This paper is posted at Villanova Un
Cryptography with DNA binary strands and so on. In terms of DNA algorithms, there are such results as A DNA-based, bimolecular cryptography design, Public-key system using DNA as a one-way function for key distribution, DNASC cryptography system and so on. However, DNA cryptography is an
students, Villanova stayed afloat because the Navy used Villanova's campus for training. To this day, only the Naval Academy surpasses Villanova as a producer of Marine Corps generals and Navy admirals. Recently-renovated Mendel Field is a popular campus location among students for fun and recreation. It hosts organized events such as orientation
University Shop. THE VILLANOVA MBA. 11. Program Basics. MBA Programs. Campus Locations. 12 The . Basics. Course Details. Class meeting days/times. 13 MBA Program Information. The Curriculum . . Villanova University is located on US Route 30/Lancaster Avenue at the intersection of Lancaster and Ithan Avenues in Villanova, PA 19085.
Tank Gauge) API 2350 categorizes storage tanks by the extent to which personnel are in attendance during receiving operations. The overfill prevention methodology is based upon the tank catagory. Category 1 Fully Attended Personnel must always be on site during the receipt of product, must monitor the receipt continuously during the first and last hours, and must verify receipt each hour .
