Cryptography

To insure the privacy of transmitted messages, the data can be encrypted.

Cryptography:

The study of methods to encrypt data.

Cryptanalysis:

The study of methods to decode encrypted data.

Conventional (or Single Key or symmetric) Encryption:

A simple algorithm is used to transform the data.

Substitution Cipher:

Each data element is substituted with a different data element (or symbol).

Example: Ceasar's method: replace every letter in the alphabet with the letter 3 away

A - > D

B - > E

C - > F

. . .

X - > A

Y - > B

Z - > C

Other substitution ciphers assign random substitutions, so they are a bit harder to crack.

  1. So, the sender uses the encryption to encrypt the message
  2. the sender transmits the message to the receiver
  3. the receiver decodes the message

How does the receiver decode the message?

Answer: The sender needs to send the key to the receiver.

Another Example:

IUUJ IU JNIN66N/ KJ C2I ?95U6 JAU IK23U J6UUL

A substitution code key (pg 612):

A->H / F->7 / K->A / P->5 / U->E / Z->? / 5->D / / ->W
B->C / G->0 / L->. / Q->F / V->S / 1->X / 6->R / .->Q
C->4 / H->B / M->V / 4->1 / W->Z / 2->P / 7->K / !->G
D->I / I->M / N->0 / S->! / X->J / 3->L / 8->Y / ?->U
E->6 / J->T / 0->3 / T->9 / Y->24 / 4->8 / 9->N

MEET ME T0MORROW AT 4PM UNDER THE MAPLE TREE.

encoding (or encrypting) - Creating a coded message

decoding (or decrypting) – unscrambling a coded message using a key

symmetric encryption - When the same key is used for both encoding and decoding

symmetric Encryption:

Encoding:

JUNE 1993 + KEY -> TE06 XNNL

Decoding:

TE06 XNNL + KEY -> JUNE 1993

Problem of ensuring key security. If a code breaker can somehow steal the key for a code, the code is broken.

symmetric faster, but if really need security – like credit card information, etc…Solution –asymmetric (public key) encryption (double key encryption).

A shared (private) key is used by a "symmetric key" system.

A system that used different keys for encrypting and decrypting (like PGP) is an "asymmetric key" encryption.

Asymmetric (Public-key) encryption:

  • Uses two keys: a public key and a private key.
  • The receiver publishes itspublic key which is used by the sender to encrypt the message.
  • The receiver uses the second (and different)private key (known only to the receiver) which is used to decrypt the message.

What is the relationship between the two keys?

It should be computationally infeasible to obtain the private key from the knowledge of the public key and the transmitted message.

These methods are based on the fact that it is computationally easy to multiply two large numbers, but it is quite difficult to factor a large number if it has very few factors, especially if the factors are large prime numbers. Example: Try to factor 3233. See how long it takes to find the prime factors, 53 and 61.

Advantage of asymmetric cryptography:

Only the public key is distributed.

Sample public-key systems:

  • RSA
  • DSA
  • PGP - Pretty Good Privacy - uses both conventional and public-key cryptography

PGP

Encoding Method:

  1. compress the message
  2. Create a session key that is used only once during this session. The key is created randomly from mouse movements and keystrokes.
  3. Session key is used to conventionally encrypt the message.
  4. The receiver's public key is used to encrypt the session key.
  5. The encrypted message and encrypted session key are sent to the receiver.

Decoding Method:

  1. The receiver uses its private key to decrypt session key
  2. The session key is used to decrypt the message.
  3. The data is decompressed.
  4. The session key is discarded.

Advantages:

  • Only a very small content (the session key) is publicly encrypted
  • The session key is used just once
  • Conventional encryption (symmetric) is ~10,000 times faster than asymmetric encryption.

PGP uses the RSA asymmetric encryption scheme:

PGP Method: (RSA)

M = the message

C - the encrypted message

e = the public exponent (public key)

d = the private exponent (private key)

n = a very large integer

Encryption Method:

C = Me mod n

Decryption Method:

M = Cd mod n

where

n = p * q

p and q are prime numbers
d = e-1 mod((p-1)*(q-1))

If n is a large number (128 bits or 256 bits), it is computationally infeasible to find p and q. Why?

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

*********************************************************************

An Example of the RSA Algorithm

P = 61 <- first prime number (destroy this after computing E and D)

Q = 53 <- second prime number (destroy this after computing E and D)

PQ = 3233 <- modulus (give this to others)

E = 17 <- public exponent (give this to others)

D = 2753 <- private exponent (keep this secret!)

Your public key is (E,PQ).

Your private key is D.

The encryption function is:

encrypt(T) = (T^E) mod PQ

= (T^17) mod 3233

The decryption function is:

decrypt(C) = (C^D) mod PQ

= (C^2753) mod 3233

To encrypt the plaintext value 123, do this:

encrypt(123) = (123^17) mod 3233

= 337587917446653715596592958817679803 mod 3233

= 855

To decrypt the ciphertext value 855, do this:

decrypt(855) = (855^2753) mod 3233

= 123

1

Cis10_14