Cryptology

Diomidis Spinellis
Department of Management Science and Technology
Athens University of Economics and Business
Athens, Greece
dds@aueb.gr

Cryptology

Cryptography:
Generalized methods to hide (encrypt) and authenticate information
Cryptanalysis:
Generalized methods to expose and substitute information

Algorithm Uses and Properties

Algorithm Types

Algorithm applications

Maintaining Confidentiality

Transposition Ciphers

Example
1 2 3 4
T R A N
S P O T
I T I O
N X X X
Take-off as 2, 4, 3, 1: RPTXNTOXAOIXTSIN
Try RAYXPAIXYNSXCTLS

Transposition Cryptanalysis

Substitution Ciphers

Polyalphabetic Ciphers

Rotor Machines

The Enigma machine

The Playfair Cipher

Example:
A -> B
B -> I
O -> P
R -> U
T -> A
X -> V
L -> O
A -> I
N -> L
D -> G
I -> Y
N -> L
G -> H
X -> W

SP Networks

Example: 4 bit S-box design with a single permutation

The Data Encryption Standard (DES)

DES structure

The Advanced Encryption Standard (AES)

Hash Function Properties

Hash functions compress a n (abritrarily) large number of bits into a small number of bits (e.g. 512).

Properties

Common Hash Functions

Hash Function Applications

Asymmetric Ciphers

The Diffie-Hellman Protocol

Case Study: Public Key Cryptography

The following example is based on the OpenSSL (http://www.openssl.org/) open-source cryptography library and command-line tool.
#!/bin/sh

################
# Key generation

# Create Alice's key pair
openssl genrsa >alice.private
# Obtain Alice's public key
openssl rsa -pubout <alice.private >alice.public

# Create Bob's key pair
openssl genrsa >bob.private
# Obtain Bob's public key
openssl rsa -pubout <bob.private >bob.public

##########################################
# Alice sends a short confidential message

# Secret message Alice wants to send to Bob
echo "Alice loves you" >message.plain

# Alice encrypts the message using Bob's public key
openssl rsautl -encrypt -in message.plain -out message.encrypted -pubin -inkey bob.public

# Bob decrypts Alice's message using his private key
openssl rsautl -decrypt -in message.encrypted -out message.decrypted -inkey bob.private

##################################
# Bob sends a short signed message

# Message Bob wants to sign
echo "Will you marry me?" >message.plain

# Bob signs the message using his private key
openssl rsautl -sign -in message.plain -out message.signed -inkey bob.private

# Alice verifies Bob's message using his public key
openssl rsautl -verify -in message.signed -out message.verified -pubin -inkey bob.public


#####################################################
# Alice sends a large signed and confidential message

# Secret message Alice wants to send to Bob
cat  >message.plain <<EOF
                       Marital AGREEMENT

THIS AGREEMENT, made this thirteen day of June, 2004 is between Bob
and Alice

1. PURPOSE. The parties expect to be married to death do them part,
   and hear by enter into this agrement vouluntarily.

2. EFFECT OF AGREEMENT. The parties agree that if one or the other
   commits infidelity during the duration of the marriage, that the person
   guilty of said act shall in effect and wholey forsake all material
   property, assets and rights to act as a parent of any children.

3. DEFINITON OF INFEDELITY. Infedelity is defined as follows: Any
   socializing with the intent to establish a realtionship, and/or
   physical contact with other person.

4. JOINT PROPERTY, ETC. This Agreement does not restrict, prohibit
   or condition any conveyance or transfer by the parties, or either of
   them alone, of the Separate Property of either party into tenancy in
   common, joint tenancy, tenency by the entireties or any other form of
   concurrent and/or undivided estate or ownership between the parties,
   or the acquisition of any property in any such form of ownership by the
   parties. The incidents and attributes of ownership and other rights
   of the parties with respect to any property so conveyed, transferred
   or acquired shall be determined under State law and shall not be
   governed by or otherwise determined with reference to this Agreement.

5. SEPARATE PROPERTY. The parties agree that there is no seperate
   property.

6. WAIVER OF RIGHTS. Except as otherwise provided in this Agreement,
   each party hereby waives, releases and relinquishes any and all right,
   title or interest whatsoever, whether arising by common law or present
   or future statute of any jurisdiction or otherwise.

7. DISSOLUTION/SEPARATION/ANNULMENT. Except as otherwise provided in
   this Agreement, each party specifically agrees that neither shall make
   any claim for or be entitled to receive any money or property from
   the other as alimony, spousal support, or maintenance in the event
   of separation, annulment, dissolution or any other domestic relations
   proceeding of any kind or nature, and each of the parties waives and
   relinquishes any claim for alimony, spousal support or maintenance,
   including, but not limited to, any claims for services rendered,
   work performed, and labor expended by either of the parties during
   any period of cohabitation prior to the marriage and during the entire
   length of the marriage. The waiver of spousal support shall apply to
   claims both pre and post-judgment.

8. RIGHT TO CONTEST. Nothing contained herein shall limit the right
   of either party to contest any domestic relations suit between the
   parties or to file a countersuit against the other party; However,
   in any hearing on such suit, this Agreement shall be considered
   a full and complete settlement of all property rights between the
   parties. In such case, neither party shall maintain any claim or demand
   whatsoever against the other for property, suit money, attorney fees
   and costs which is either inconsistent with or not provided for in
   this Agreement.

9. INTEGRATION. This Agreement sets forth the entire agreement between
   the parties with regard to the subject matter hereof. All prior
   agreements, covenants, representations, and warranties, expressed or
   implied, oral or written, with respect to the subject matter hereof,
   are contained herein. All prior or contemporaneous conversations,
   negotiations, possible and alleged agreements, representations,
   covenants, and warranties, with respect to the subject matter hereof,
   are waived, merged, and superseded hereby. This is an integrated
   agreement.

10. BINDING ON SUCCESSORS. Each and every provision hereof shall
   inure to the benefit of and shall be binding upon the heirs, assigns,
   personal representatives, and all successors in the interest of
   the parties.

11. ACKNOWLEDGEMENTS. Each party acknowledges that he or she has
   had an adequate opportunity to read and study this Agreement, to
   consider it, to consult with attorneys individually selected by each
   party, without any form of coercion, duress or pressure. Each party
   acknowledges that he or she has examined the Agreement before signing
   it, and has been advised by independent legal counsel concerning the
   rights, liabilities and implications of this document.

12. STATE LAW. It is intended that this Agreement be valid and
   enforceable within the provisions of the State Law, and that Case
   Law that governs its interpretation. State law is considered to be
   that of California, USA.
EOF

# Alice generates a short random key to be used for encrypting the message
openssl rand 16 -out key.plain

# Alice encrypts the message with the short random key
openssl des3 -e -kfile key.plain -in message.plain -out message.encrypted

# Alice creates a message digest of the message to sign
openssl dgst -binary message.plain >message.digest

# Alice signs the digest using her private key
openssl rsautl -sign -in message.digest -out digest.signed -inkey alice.private

# Alice encrypts the random key using Bob's public key
openssl rsautl -encrypt -in key.plain -out key.encrypted -pubin -inkey bob.public

# Alice sends Bob:
# - the encrypted message
# - the encrypted key
# - the signed message digest


# Bob decrypts Alice's encrypted key using his private key
openssl rsautl -decrypt -in key.encrypted -out key.decrypted -inkey bob.private

# Bob decrypts the message using the decrypted key
openssl des3 -d -kfile key.decrypted -in message.encrypted -out message.decrypted

# Bob verifies the digest Alice has signed using her public key
openssl rsautl -verify -in digest.signed -out message.digest1 -pubin -inkey alice.public

# Bob calculates again a message digest of the message
openssl dgst -binary message.plain >message.digest2

# Bob compares the two message digests to verify Alice signed the agreement
# he has examined
diff message.digest1 message.digest2

A Simple Public Key System

  1. Create a graph with a known perfect code
  2. Simple example: fair coin tossing over the phone
  3. Public key encryption and decryption

Bibliography