Full HTML for

Basic foilset Basic Mathematics of Security Systems

Given by Geoffrey C. Fox at CPS714 Computational Science Information Track on June 2 99. Foils prepared May 30 99
Outside Index Summary of Material

Note this material is not impacted by recent (Web) advances and so can be studied in "venerable" books such as:
Network Security: Private Communication in a Public World, Kaufman, Perlman and Speciner, Prentice Hall 1995
Web leads to important new applications of security mathematics and nifty pure mathematics is making progress in cracking longer and longer keys
We discuss Secret Key Technology and Public Key Technology with applications to
  • Transmission over insecure media
  • Digital signatures
  • Message Integrity

Table of Contents for full HTML of Basic Mathematics of Security Systems

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
1 Basic Mathematics of Security Systems CPS714 Summer 99 Lecture recorded May 30 99 for delivery June 2 99
2 Abstract of CPS714 Mathematics of Security Lecture
3 Introduction to Cryptography
4 Breaking an Encryption Scheme
5 Types of Cryptographic Function
6 Security Uses of Cryptography
7 Secret Key Cryptography
8 Uses of Secret Key Cryptography
9 Secret Key Authentication
10 Message Integrity with Secret Key Cryptography
11 Public Key Cryptography
12 Insecure Link Transmission with Public Key Cryptography
13 Authentication with public key Cryptography
14 Digital Signatures and Public Key Cryptography
15 Use of Digital Signatures with public key Cryptography
16 Hash and Message Digests in Detail
17 Some Math Behind Secret Key Cryptography
18 Some Math behind RSA Algorithm -I
19 Some Math behind RSA Algorithm -II
20 Combining Public and Secret Keys

Outside Index Summary of Material

HTML version of Basic Foils prepared May 30 99

Foil 1 Basic Mathematics of Security Systems CPS714 Summer 99 Lecture recorded May 30 99 for delivery June 2 99

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
Geoffrey Fox
Syracuse University
NPAC
111 College Place Syracuse NY 13244 4100
3154432163
HTML version of Basic Foils prepared May 30 99

Foil 2 Abstract of CPS714 Mathematics of Security Lecture

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
Note this material is not impacted by recent (Web) advances and so can be studied in "venerable" books such as:
Network Security: Private Communication in a Public World, Kaufman, Perlman and Speciner, Prentice Hall 1995
Web leads to important new applications of security mathematics and nifty pure mathematics is making progress in cracking longer and longer keys
We discuss Secret Key Technology and Public Key Technology with applications to
  • Transmission over insecure media
  • Digital signatures
  • Message Integrity
HTML version of Basic Foils prepared May 30 99

Foil 3 Introduction to Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
This is old technology first attributed to Julius Caesar who used the nifty cipher which replaced every letter with that three letters further in the alphabet
  • So A becomes D and Z becomes C (using cyclic wraparound)
Most ciphers involve an algorithm and a parameter (this is 3 in the above) where usually algorithm can be public but parameter is kept secret and is called a key
  • key needs to be quite big to be safe (say at least 40 bits long)
  • It is usually not possible to keep algorithm secret and in fact making it public can encourage experts to examine and comment on its reliability (i.e. ease of breaking)
HTML version of Basic Foils prepared May 30 99

Foil 4 Breaking an Encryption Scheme

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
It would be easy to break Caesar's cipher but in general it is hard and in fact exponentially hard as breaking cipher involves some sort of combinatorial (exhaustive) search combined with clever ideas
  • such as looking for common English words such as the
Note that encoding/decoding can be computationally expensive but much less so than code breaking
  • So as computers get faster, the code breaker's job gets easier for FIXED coding strategy but much harder for a coding strategy that takes a fixed time
Methods exist for three scenarios
  • You only have ciphertext gotten by eavesdropping insecure link
  • You have some matched (ciphertext,plaintext) combinations and wish to find plaintext corresponding to some new ciphertext
  • You have ability to get ciphertext for any plaintext of your (the code breaker's) choice
HTML version of Basic Foils prepared May 30 99

Foil 5 Types of Cryptographic Function

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
There are three major types of cryptographic function which differ in functionality and performance
Secret Key Cryptography is what we are most familiar with and has medium performance and functionality. It has one secret key
Public Key Cryptography is a remarkable idea with some very important and non-intuitive capabilities. It is computationally intense and requires some infrastructure to implement. It involves one secret (called private) and one public key known to everybody.
  • Based on computational infeasibility of factoring large numbers which can be found by multiplying two primes
Hash functions (or one way transformations) involve zero keys and encrypt in a way that cannot be decrypted. It is very fast
Methods are combined to produce hybrid approaches that combine necessary speed and functionality
HTML version of Basic Foils prepared May 30 99

Foil 6 Security Uses of Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
1)Transmitting over insecure channels
2)Storage on insecure media (essentially the same ideas as 1) but applied to a different need)
3)Authentication of computers or people at end of a message transmission. This includes digital signatures and password hashing
4)Integrity check that message delivered was the one sent (this is different from ensuring that nobody read information which is 1)). This is called message integrity
HTML version of Basic Foils prepared May 30 99

Foil 7 Secret Key Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
This involves a single secret key and standards are DES (Digital Encryption Standard) and IDEA (International Data Encryption Algorithm)
Commercial systems (used in SSL) are RC2 RC4 RC5
  • Note 40 bit RC2 takes a 64 MIP computer one year to break
HTML version of Basic Foils prepared May 30 99

Foil 8 Uses of Secret Key Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
There is the natural use for either transmission over an insecure network or for storage on an insecure media.
Strong Authentication implies that one can prove knowledge of a secret (key) without revealing the key and in particular without sending key between two individuals
This is effective authentication but requires as many secrets as pairs of people who need to communicate.
Public key version will only require one key for each individual wishing to be authenticated with anybody else and so is more practical for widespread deployment. N keys and not N2 as for secret key authentication.
Secret key authentication is however faster and much easier to implement for any sets of sites that wish to establish authenticated communication with a shared secret.
HTML version of Basic Foils prepared May 30 99

Foil 9 Secret Key Authentication

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
Each individual A and B picks a random number rA and rB which are only known to themselves and a fresh for session to be authenticated. There is shared key KAB which is not to be transmitted but A needs to know that B knows KAB and B needs to know that A knows KAB. The random numbers are known as challenges.
rA
Decrypt xA and see it gives rA
Encrypt rA to give xA
xA
rB
Encrypt rB to give xB
xB
Decrypt xB and see it gives rB
HTML version of Basic Foils prepared May 30 99

Foil 10 Message Integrity with Secret Key Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
Checksums are well known and a simple version can be gotten by dividing message into 32 bit groups and anding these groups together.
  • This is designed for fault tolerance and ensures that data was not garbled in transmission
Such checksums or hashes (designed properly) cannot be inverted and represent a unique fingerprint of original message.
A secret checksum combines this process with a secret key and produces a MIC (message integrity code) which can be decoded and checked
This can be used with either a ciphertext or plaintext message and guarantees that information is stored or transmitted faithfully
Note encrypting a message does not guarantee that it is not changed!
MIC with plaintext is used by bank electronic fund transfer
HTML version of Basic Foils prepared May 30 99

Foil 11 Public Key Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
This is much younger than other approaches and was first published in 1975. As we have discussed this has distinctive feature of only needing one key per individual/organization requiring encrypted authenticated messaging
It has nontrivial infrastructure to distribute the N public keys for N organizations but this is better than N2 keys for secret key cryptography
Roughly the public key is a very large number that is the product of two primes. The private key is (related to) one of these primes.
It is used differently in two cases which following foils do in detail
  • Transmission over insecure network where one encodes with public key of receiver (and receiver decodes with his or her private key)
  • Authentication where you encode your digital signature with your private key and receiver checks the signature with your public key -- only you can encode signature so it is correctly decoded with public key
HTML version of Basic Foils prepared May 30 99

Foil 12 Insecure Link Transmission with Public Key Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
Suppose A has (public key,private key) <eA,dA> and B keys <eB,dB>
A transmits a message mA to B encrypting it with B's public key eB
B decrypts this message and reads it using private key dB
Similarly B sends a message mB to A encrypting with eA which A decrypts with private key dA
Plaintext
Encryption
Public Key
Private Key
HTML version of Basic Foils prepared May 30 99

Foil 13 Authentication with public key Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
Here A chooses a challenge -- a random number r and can verify that B is at other end using solely public information!
A Sends x
Decrypt x with dB and send back challenge
A Encrypts r using eB to give x
Send r
Only B could have sent back r
Alice is A
Bob is B
eB is public key of B
dB is B's private key
HTML version of Basic Foils prepared May 30 99

Foil 14 Digital Signatures and Public Key Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
Digital Signatures reverse the use of public and private keys
You encrypt with the private and decrypt with the public key
Plaintext
Verification
Plaintext
Signing
Private Key
Public Key
HTML version of Basic Foils prepared May 30 99

Foil 15 Use of Digital Signatures with public key Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
Here B starts with a document that it is required to prove only could come from B
This could be a piece of software that we wish to know comes from a reputable source
We combine software with a "certificate" (a statement that B is Bob) and either encrypt this with dB or more normally encrypt a message digest (or hash that depends on both message and signature) with dB
This use of a message digest is done for performance as it is time consuming to use public key encryption on full message
Note this signature cannot be forged either by A or any other person pretending to be B.
  • In secret key version A shares B's secret key and can forge messages that purport to be from B
HTML version of Basic Foils prepared May 30 99

Foil 16 Hash and Message Digests in Detail

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
Given a message m, the hash h(m) must satisfy
  • It can be calculated relatively quickly
  • Given h(m), it cannot be be inverted (to find m) by any practical method
  • Even though many m's will be transformed to the same h(m), this will in practice never happen and it is impossible in practice to find two m's that give the same h(m)
As hash function is known, the security of a hash comes from the unknown message.
  • Messages can be made unknown by concatenating plaintext with a common secret key before applying h(m)
These are called one-way transformations as hashes cannot be inverted
  • Practical methods involve a strange combination of anding and permutations which ensures the cryptography safety of method
Message Digests (such as MD2 MD4 MD5 -- MD is Message Digest with 128 bit output -- or SHS -- Secure Hash Standard with 160 bit output output) are used in Public key Systems to reduce computational complexity of encryption (see previous foil)
HTML version of Basic Foils prepared May 30 99

Foil 17 Some Math Behind Secret Key Cryptography

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
Secret Key algorithms are based on elaborating a simple idea
Caesar rotated alphabet in his cipher. An obvious extension of this is use a 1<-ɭ permutation of a group of N bits
for DES N=64 and permutation is calculated from a 48 bit key
To make decoding harder, this is done 16 times with different keys extracted from an original 56 bit secret
  • Note secrets in real world are usually generated randomly
This strategy is combined with (ad-hoc) transformations to further obfuscate the process
The full message must be divided into blocks before applying this process and the method of running secret key cryptography on long messages is non trivial (but not very fundamental) as doing in 64 bit separate units would allow information to be freely shuffled!
HTML version of Basic Foils prepared May 30 99

Foil 18 Some Math behind RSA Algorithm -I

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
RSA stands for inventors: Rivest Shamir and Adleman
Take a number n = p * q where p and q are primes
Choose a "suitable" number e
Public key is <e,n> and basic encryption algorithm takes message m to be encrypted and forms
  • c = me mod(n)
Decryption involves private key d which is found so that
  • d * e = 1 mod((p-1)(q-1))
Then m = cd mod(n)
As factorization is computationally infeasible (for n of 512 bits in length or more), this encryption cannot be broken.
  • Maybe should increase this to n=1024 as recently much progress in nifty factorizations
HTML version of Basic Foils prepared May 30 99

Foil 19 Some Math behind RSA Algorithm -II

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
n,c,d are 512 bits; p,q are 256 bits; e could be small (3 or 65537); m must be less than or equal to bit length of n
lengths are doubled in recent implementations
As encoding is time consuming, we only use RSA for small messages anyway. However as in secret key methods, one must in general break longer messages into smaller sizes
  • Deployed schemes use secret key methods (with key exchanged using public key method) for large amounts of data (see discussion of SET)
PKCS (Public Key Encryption Standard) is a standard from RSA for encoding the information to be signed or encrypted through RSA. It incorporates "know-how" to make RSA work reliably.
Diffie-Hellman, El Gamal and DSS (Digital Signature Standard) are RSA like approaches aimed at digital signatures
HTML version of Basic Foils prepared May 30 99

Foil 20 Combining Public and Secret Keys

From Basic Mathematics of Security Systems CPS714 Computational Science Information Track -- June 2 99. *
Full HTML Index
So one can take advantage of both security approaches by using Public Key Infrastructure to initialize a session
  • One participant chooses a random secret key
  • This is encrypted using public key of recipient
  • recipient decodes this digital envelope with his or her private key
Thereby they have set up joint knowledge of a secret key without usual disadvantages
  • secret key is used for rest of session
Note secret key is only used for this session and so one must break in real time
© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Sun May 30 1999