**An introduction to Modern Cryptography**

Comparison

Cryptography

Cryptography is the science of writing in secret code and is an ancient art.

The first documented use of cryptography in writing dates back to circa 1900 B.C.

That new forms of cryptography came soon after the widespread development of computer communications.

Cryptography is necessary when communicating over any untrusted medium

RSA

Basic Definitions

Plaintext :

A message that we can read and understand without the aid of any means especially complex.

Ciphertext:

The ciphertext is the result of the transformation of a clear message through the use of a mathematical function or algorithm.

Encryption:

The transformation process of a message that modifies it in substance and makes it illegible.

Decryption:

The inverse process of encryption that allows to obtain the message in clear from a ciphertext.

As we have mentioned in the previous sections, the key distribution problem was one of the main issues in symmetric cryptography. Two parties needed to share a secret key over an insecure channel.

How can two people who have never met, agree on a secret sharing key?

In 1976 Whitfield Diffie and Martin Hellman invented an amazing trick to do this. Their protocol for key distribution called Diffie-Hellman Key Exchange, allows two parties to agree a secret key over an insecure channel without having met before. Its security is based on the DLOG problem in a finite abelian group G.

There are, in general, three types of cryptographic schemes typically used to accomplish these goals:

Secret Key Cryptography (SKC)

: Uses a single key for both encryption and decryption

Public Key Cryptography (PKC)

: Uses one key for encryption and another for decryption

Hash Functions

: Uses a mathematical transformation to irreversibly "encrypt" information

Cryptography provides means to guarantee the following critical issues of information and communication:

Confidentiality

: A message should be protected from being read by non-legitimate persons .

Authentication

: The receiver should be able to identify the origin of a message.

Data Integrity

: The receiver should be able to examine whether a message was changed during transmission.

Liability (Non repudiation)

: A sender should not be able to deny having sent a message.

Examples:

Symmetric algorithms

:

DES (Data Encryption Standard)

Blowfish

IDEA

AES (Advanced Encryption Standard)

All historical ciphers

Public key algorithms

:

RSA

Diffie-Hellman

DSS (Digital Signature Standard)

Rabin

El Gamal

Elliptic curve cryptography

Historical ciphers (pre 1970):

Examples:

Shift Cipher

Substitution Cipher

Vigenere Cipher `

Vernam Cipher

Rotor Machines (Enigma)

Weaknesses of Historical Ciphers:

They do not successfully hide the underlying statistics of the language.

WI UB PO MO IL KB RE OS OK BO RE UB BO AS FT OK

a i ru ra n do do ku ri tsu do i tsu o wa ri

Working with letters which is not so many

Key exchange

Very long keys

No authentication

No data integrity

No libaility

Diffie-Hellman Key Exchange

The Invention of Public-key Cryptography

So we need a numerical procedure which is easy to one direction and hard in the other. This brings us to modular arithmetic and Discrete Logarithm Problem. This is what we call the One-Way function.

The basic message flows for the Diffie-Hellman protocol are given in the following diagram:

Eve

K=

What is Secret Sharing?

(t,n) secret sharing (threshold) scheme [Shamir 1979,Blackly 1979]:

A (t,w) threshold scheme is a method of sharing a key K among a set of w participants in such a way that any t participants together can compute the value of K, but no group of (t-1) participants can do so.

Lagrange Interpolation Polynomial Scheme:

Mathematical Definition (Shamir's Secret Sharing):

Initialization Phase:

ShareDistribution Phase: (Suppose the key is K)

Key Recovery Phase:

Initialization Phase:

Share Distribution Phase: (Suppose K=13)

Enigma; the most powerful historical cipher:

Some

unusual

property between old fashion codes.

W R Y A K A R I M

C A Q H C O M X C

In the German military machines, the total number of possible combinations for message encryptions comes to

158,962,555,217,826,360,000

.

The messages were transmitted over radio via Morse code.

Each month had its own settings, printed on code sheets in soluble ink that easily dissolved in

water

.

The

German navy

had a more complicated method of encoding than either the army or air force.

The

Polish

had developed a machine called the

Bombe

, which could decipher army and air force codes, but not navy.

This is why the

German

believed that they have an unbreakable cipher machine.

What Turing did?

Along with Gordon Welchman, developed his own version of the Bombe machine, which allowed him to break any version of the Enigma code in under 20 minutes.

DES (Data Encryption Standard) 1977:

The creation of a

public

encryption standard made a revolution in Cryptography.

Developed in the early

1970s

at

IBM

and based on an earlier design by

Horst Feistel

.

DES is a

block cipher

with block size of

64 bits

.

The key ostensibly consists of

64 bits

; however, only

56

of these are actually used by the algorithm.

Error detection

in key generation.

A

one way function

is used but you

don't need to reverse

the function to decrypt the cipher.

16

identical stages of processing, termed

rounds

.

16

48-bit subkeys — one for each round.

The Feistel Function:

Operates on half a block (32 bits) at a time and consists of four stages:

1)

Expansion

: The 32-bit half-block is expanded to 48 bits using the

expansion permutation.

2)

Key-mixing

: The result is combined with a subkey using an XOR operation. 16 48-bit subkeys — one for each round.

3)

Substitution

: After mixing in the subkey, the block is divided into eight 6-bit pieces before processing by the

S-boxes

, or substitution boxes. Each of the eight S-boxes replaces its

six

input bits with

four

output bits according to a

non-linear transformation .

4)

Permutation

: Finally, the 32 outputs from the S-boxes are

rearranged

according to a fixed permutation, the

P-box

.

Symmetric key Cryptography:

Advantages:

Simple

Encryption and decryption your own file.

Uses less computer resources

Prevents widespread message security compromise

Disadvantages:

Too many keys

Origin and authenticity of message cannot be guaranteed

Too many keys

Advantages:

Disadvantages:

Asymmetric key Cryptography:

Convenience

Provides for message authentication

Detection of tampering

Provide for non-repudiation

Public keys should/must be authenticated

Uses up more computer resources

Widespread security compromise is possible

Loss of private key may be irreparable

Question?

Thank You

**Wrya Karim**