Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

An introduction to Modern Cryptography

No description
by

on 23 July 2014

Report abuse

Transcript of An introduction to Modern Cryptography

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
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:
Simple
Encryption and decryption your own file.
Uses less computer resources
Too many keys
Origin and authenticity of message cannot be guaranteed
Too many keys