Encryption, continuedPublic Key encryptionEffective Public Key EncryptionIt all comes down to this:Rivest, Shamir, Adelman (RSA)Public Key encodingAn example:On a practical note: PGPIssuesDigital SignaturesDigital Signature basic techniquePublic key encryption with implied signatureDigital Signature Standard (DSS)Digital Signature - SHAEncryption summaryImportant methodsDigital signaturesLegal and ethical issuesEncryption, continuedPublic Key encryption and Digital SignaturesPublic Key encryption•Eliminates the need to deliver a key•Two keys: one for encoding, one for decoding•Known algorithm–security based on security of the decoding key•Essential element: –knowing the encoding key will not reveal the decoding keyEffective Public Key Encryption•Encoding method E and decoding method D are inverse functions on message M:–D(E(M)) = M•Computational cost of E, D reasonable•D cannot be determined from E, the algorithm, or any amount of plaintext attack with any computationally feasible technique•E cannot be broken without D (only D will accomplish the decoding)•Any method that meets these criteria is a valid Public Key Encryption techniqueIt all comes down to this:•key used for decoding is dependent upon the key used for encoding, but the relationship cannot be determined in any feasible computation or observation of transmitted dataRivest, Shamir, Adelman (RSA)•Choose 2 large prime numbers, p and q, each more than 100 digits•Compute n=p*q and z=(p-1)*(q-1)•Choose d, relatively prime to z•Find e, such that e*d=1 mod (z)–or e*d mod z = 1, if you prefer.•This produces e and d, the two keys that define the E and D methods.Public Key encoding•Convert M into a bit string•Break the bit string into blocks, P, of size k–k is the largest integer such that 2k<n–P corresponds to a binary value: 0<P<n•Encoding method –E = Compute C=Pe(mod n)•Decoding method–D = Compute P=Cd(mod n)•e and n are published (public key)•d is closely guarded and never needs to be disclosedAn example:•Given p=7; q=11•Compute n, z, d, e, k•n=77; z=60 d=13; e=37; k=6•Test message = CAT•Using A=1, etc and 5-bit representation:– 00011 00001 10100•Since k=6, regroup the bits (arrange right to left so that any padding needed will put 0's on the left and not change the value): –000000 110000 110100 (three leading zeros added to fill the block)•decimal equivalent: 0 48 52•Each of those raised to the power 37 (e) mod n: 0 27 24•Each of those values raised to the power 13 (d) mod n (convert back to the original): 0 48 52On a practical note: PGP•You can create your own real public and private keys using PGP (Pretty Good Privacy)•See the following Web sites for full information.•(MIT site - obsolete)•http://www.pgpi.org/products/pgp/versions/freeware/•http://www.freedownloadscenter.com/Utilities/Required_Files/PGP.htmlIssues•Intruder vulnerability–If an intruder intercepts a request from A for B’s public key, the intruder can masquerade as B and receive messages from B intended for A. The intruder can send those same or different messages to B, pretending to be A.–Prevention requires authentication of the public key to be used.•Computational expense–One approach is to use Public Key Encryption to send the Key for use in DES, then use the faster DES to transmit messagesDigital Signatures•Some messages do not need to be encrypted, but they do need to be authenticated: reliably associated with the real sender–Protect an individual against unauthorized access to resources or misrepresentation of the individual’s intentions–Protect the receiver against repudiation of a commitment by the originatorDigital Signature basic techniqueSender AReceiver BIntention to sendE(Random Number)where E is A’s public keyMessage and D(E(Random Number))= Random Number, decoded as only A could doPublic key encryption with implied signature•Add the requirement that E(D(M)) = M•Sender A has encoding key EA (private), decoding key DA (public), •Intended receiver has encoding (public) key EB.•A produces EB(DA(M))•Receiver calculates EA(DB(EB(DA(M))))–Result is M, but also establishes that only A could have encoded MDigital Signature Standard (DSS)•Verifies that the message came from the specified source and also that the message has not been modified•More complexity than simple encoding of a random number, but less than encrypting the entire message•Message is not encoded. An authentication code is appended to it.Digital Signature - SHAFIPS Pub 186 - Digital Signature Standard http://www.itl.nist.gov/fipspubs/fip186.htmEncryption summary•Problems–intruders can obtain sensitive information–intruder can interfere with correct information exchange•Solution–disguise messages so an intruder will not be able to obtain the contents or replace legitimate messages with othersImportant methods•DES–fast, reasonably good encryption–key distribution problem•Public Key Encryption–more secure•based on the difficulty of factoring very large numbers–no key distribution problem–computationally intenseDigital signatures•Authenticate messages so the sender cannot repudiate the message later•Protect messages from changes during transmission or at the receiver’s site•Useful when the contents do not need encryption, but the contents must be accurate and correctly associated with the senderLegal and ethical issues•People who work in these fields face problems with allowable exports, and are not always allowed to talk about their work.•Is it desirable to have government able to crack all codes?•What is the tradeoff between privacy of law abiding citizens vs. the ability of terrorists and drug traffickers to communicate in secret?–Brief discussion now–During the coming week, continue the discussion online. Use the WebCT discussion list. See assignment