Public-Key Cryptography



Symmetric Versus Asymmetric Ciphers

Keep communication confidential and hidden from unintended recipients

Transform words, letters, bits into gibberish

Intended recipient must be able to transform the gibberish back to its original form

Eavesdropper can only get gibberish

Two types: Symmetric (secret key) ciphers and Asymmetric (public key) ciphers


Secret Key

Until the mid-1970s, the only way to send data confidentially

Have sender and recipient share some secret information for gibberish transformation

E.g. replace message with letter 13 places ahead in alphabet. A -> N, B -> O, Z -> M. The recipient transform back using N->A, O->B, etc.

The shared secret information (how the transformation to and from gibberish) is called a "key"

Transformation to gibberish is called encryption

Transformation back to the original text is called decryption

The original message is called plaintext, is encrypted to gibberish called ciphertext

The entrie confidentially mechanism (the encryption, decryption algo) is called cipher

Symmetric cipher: When the encryption key and the decryption key are idential OR one key is very easily derived from the other (the shifting character examples)

Data Encryption Standard (DES) is a 128 bit symmetric cipher


Symmetric Ciphers

Fast: Tens of megabytes per second or more


Need secret key exchange: sender and recipient needs to share secret key prior to transmission of the message

Scalability issues: in a community of 1000 users, a user needs 999 secret keys for others, and 1 for him/herself. So, the whole community needs close to half a million of "unique" secret keys.

n users may require up to n*n/2 unique secret keys

Unknown Entities communication is difficult: how does a user make sure the out-of-band secret key exchange is safe?

Some of the above problems could be solved by using a central server architecture with KDC (Key Distribution Center) which the centeral server is an introducer for entities that do not previously know each other

Significant signle point of failure and single point of attack


Asymmetric Ciphers

PK Cryptography is invented by Whitfield Diffie and Martin Hellman in mid-1970s

Asymmetric Ciphers: Key for encryption and the key for decryption were related but conspicuously different

Concept based on vector-matrix and inversion of matrix to generate keys

Known as the "trapdoor functions with high computational complexity"

Classic paper in 1976 from Diffie-Hellman broke the way to ever-increasing pace of PKI research


Public / Private Key Pair

Key pair: the keys are different that knowing one does not allow derivation or computation of the other

Public key is made available (telephone book, directories, open database)

Private key is kept privately (securely)

The keys in the key pair in PK cipher are different, but related. The relationship is mathematical and may reply on information known only to the creator of the key pair (e.g. factorization of a large integer, inverson of matrix, etc)

In theory, the private key can always be derived, but the amount of time, memory, or computing power necessary to do so in practice must be prohibitively high


PK Cryptography Services

Security between strangers

Idea: use public key to encrypt and corresponding private key to decrypt


Sender must trust the public key repository for download. In other words, the phone in the phone book must be correct

Sender must find a way to trust the information. Public repository may be untrusted, but the information it returns should be independently verified for correctness.

Public repositories cannot be trusted to return correct information, thus, the info itself must be independently verifiable. Need the use of public-key certificate.

Bring the KDC by means of reading hte data suffices to compromise the entire system

With public repository, the attracker must be able to explicitly manipulate the contained data in a totally undetectable way. (Much much harder ... )


PK cryptography is generally slower, so a two-step process for encryption is used

1. The data is encrypted using a randomly generated symmetric key (sometimes called section key)

2. The symmetric key is encrypted using the public key of the intended recipient of the data.

(Sender then sends the data to the recipient)

When the recipient receives the encrypted data, a corresponding two-step process takes place

1. The recipient obtains the symmetric key by decrypting the symmetric key using its private key

2. The symmetric key is then used to decrypt the actual data

Digital Signature

Analogous to hand-written signature

Entity "sign" the data, any number of entities can read the signature and verify its accuracy

Secure since it is virutally almost impossible to create sender's signature on some data

Think of as private-key operation on data (where the resulting value is the signature)

private key holder is the only one can sign

public-key operation is used to check the result corresponds to the original data

Data to be signed may be of any arbitrary size (e.g. cn or 10M file)

However, private-key operation takes a fixed-size input and computes a fixed-size output

So, cryptographic hash function is used. This type of functions has the property that maps an input of arbitrary size to a fixed-size ouput (which will be used by private-key operation).

Generally, two different hash inputs do not produce the same hash output

Signing operation:

1. Signer hashes the data to a fixed-size value

2. Signer subjects this value to a private-key operation


1. Verifier hashes the data to a fized-size value

2. The verifier then examines this value, the transmitted signature, the signing entity's public key (if the signature matches the key and the hash value, the signature verifies; otherwise, verification fails).

Data Integrity

Digitial signatures provide:

1. Data origin authentication (evidence as to who originated the data), AND

2. Data integrity (evidence that the data has not been altered in any way)

Since hashing diff data will not produce the same result. Any change (alteration) to the data will lead to a different hash value.

Key Establishment

Key exchange (aka Key establishment) could be done with PK cryptography

A protocol that use public and private key pairs to generate a share secret symmetric key between two unknown entities

Two ways of doing Key Establishment

1. One way key transfer: sender generates the symmetric key and sends it to the other entity. (Use public key to encrypt and private key to decrypt the key)

2. Joint key agreement: both entitie jointly contribute to the generation of the symmetric key. (E.g. Diffie-Hellman key establishment protocol)

Other services are in the works, XKMS, SAML, etc.



RSA (Ron Rivest, Adi Shamir, Len Adleman in 1978), one of the earliest and most versatile of the public-key algorithms.

DSA (Digital Signature Algorithm) is a Federal Information Processing Standard (FIPS) publication of the National Institute of Standards and Technology (NIST) of the US Department of Commerce. DSA is designed exclusively for signing, verification and use for data integrity.

DH: Whitefield Diffie and Martin Hellman. Simple and eleganant key establishment algo.

ECDSA and ECDH. The DSA and DH algorithms can be computed over the group of points defined by the solution to an equaton for an elliptic curve over a finite field defined. (Almost no one uses this today)

SHA-1: Secure Hash Algorithm is designed specifically for use with the DSA but can be used with RSA or other public-key signature algo as well. Its design principles are similar to those used in the MD2, MD4, and MD5 hash functions proposed by Ron Rivest.


Copyright 1996-2003 OpenLoop Computing. All rights reserved.