Cryptography

Terminology

  • Cryptography - Study of methods of encoding text for purposes of privacy
  • Encryption - the process of encoding text
  • Decryption - the process of decoding text
  • Plaintext/cleartext unencoded text

oInformation before encryption or after decryption

  • Cipher – a code
  • Ciphertext coded text

oInformation that has been encrypted

EncryptionDecryption

  • Cryptosystem – a system that employs encryption and decryption

Conventional / Symmetric Key / Single Key Encryption

  • Simple algorithm is used to encrypt / decrypt (transform) the text
  • Same key is used in encryption and decryption
  • Secret is primarily in the key

An Example - Substitution cipher

  • Symmetric Key System
  • Simple algorithm is used to encrypt / decrypt (transform) the text

oEach letter is replaced with a different letter or symbol

  • Caesar’s method

oReplace every letter with letter 3 away in alphabet

A -> D

B -> E

C -> F

…

W -> Z

X -> A

Y -> B

Z -> C

Back to Symmetric Key / Single Key Encryption

  • Both parties need same key
  • How to send securely key to receiver

oSeparate messenger

oKey book

  • One-time pads

Public Key / Asymmetric Key Cryptosystems

  • Two keys are used- public and private
  • Distribute public key; keep private key…private (duh!)

A Bit on How This Could Work

  • What two numbers when multiplied produce 143?
  • Such numbers are called factors
  • Now multiply 13 and 23
  • Which process took longer? Why?
  • Similar to a one-way screw

oCan drive it in, but difficult to remove it

  • Also, a trap-door

oAgain, easy to go in, but difficult to come out

  • Idea is to have a function that is easy to calculate in one direction, but not the other

oEncryption uses the easy function

  • Involves using the public key

oDecryption requires the hard function

  • unless you have the private key
  • How to use it

oFreely distributepublic key

  • Put it on Web page, for example

oSomeone sending message encrypts with public key

  • Standard programs (see below) that accepts public key and message and perform the encryption

oReceiver uses private key to decrypt message

Digital Signatures

  • Public key systems also allow you to digitally sign your messages
  • The message is signed with your private key
  • You end up with a new message consisting of the original message and what appears to be an encoded version
  • To verify that the message is authentic, the receiver supplies your public key
  • The public key is applied to the signed message and checks that the original message and the encoded match
  • Any changes to the original message will cause a mismatch during the verification process

Digital Certificates

  • Solves the problem of public key authenticity
  • Public key is verified by a well-known entity that verifies the authenticity of the key

Well-known Public Key Systems

  • RSA - invented by Ron Rivest, Adi Shamir and Leonard Adleman
  • DSA - Digital Signature Algorithm by David Kravitz
  • Pretty Good Privacy - PGP - uses both conventional and public-key cryptography

The RSA Public Key System

  • RSA - invented by Ron Rivest, Adi Shamir and Leonard Adleman
  • Some symbols

oM – message (cleartext)

oC – ciphertext

oe – public exponent (power)

od – private exponent

on - very large (128 bits) number – product of two primes

  • Then:

oThe message is encrypted by …

  • C = M e % n

o… and decrypted by

  • M = C d % n
  • where n = p * q, p and q are prime numbers
  • Where d = e -1 mod ((p-1)*(q-1))
  • Notice that to decrypt you need to know d

od can be obtained from e, which is public. However

othe calculation is infeasible

  • must find all factors of n
  • determine which are prime
  • must try all pairs of primes to find p and q

PGP

  • Pretty Good Privacy
  • Sending message

oPGP compresses message

  • Increases security and reduces transmission time

oPGP creates session key to be used only once. Randomly created (uses keystrokes and randomly selected mouse movements)

oSession key is used to conventionally (symmetric key) encrypt message

oReceiver’s public key is used to encrypt session key

oEncrypted message and encrypted session key are sent to receiver

  • Receiving message

oPrivate key is used to decrypt session key

oSession key is used to decrypt message

oMessage is decompressed

  • Advantages

oConvention encryption is much faster than public key (10,000 times faster)

  • Only using public key on relatively small text (session key)

oOne time session key prevents trying to decode previous messages to break cipher