T H E IN S T IT U T E O F
C H A R TE R E D
A C C O U N TA N T S O F IN D IA
INFORMATION TECHNOLOGY TRAINING
SUBMITTED TO:
MR. ROHIT SHARMA
MR. SATISH KUMAR SUBMITTED BY:
ITT CENTRE AMRITSAR PARUL MEHRA
NRO0192077
A PROJEC T REPORT
O N C R YP T O G R A P H Y
W h a t is
C r yp to g r a p h y?
“hidden writing”
Until recently: military tool
Like any military technology: methods
change over time
Two sides: designing codes
breaking codes (cryptanalysis)
Computers have changed both
B r ie f H is t o r y o f
C r yp to g r a p h y
What is Cryptography?
Science of writing secret code
The first use of cryptography in 1900 B.C.
Used by Egyptian scribe
Some experts say it appeared right after writing
was invented
C r y p t o Te r m s
Cryptography – art/science relating to
encrypting, decrypting information
Cryptanalysis – art/science relating to
converting cipher text to plaintext without the
(secret) key
Link encryption – the individual application of
encryption to data on each link of network
End to end encryption – the encryption of data
from source system to end system
C r yp to g r a p h y B r o k e n
Down
Two kinds of cryptosystems:
Symmetric
Uses the same key (the secret key) to encrypt
and decrypt a message.
Asymmetric
Uses one key (the public key) to encrypt
a message and a different key (the private
key) to decrypt the message.
S y m m e t r ic
C r yp to s ys te m
The message:
The sender and receiver know and use
the same secret key.
The sender uses the secret key to encrypt
the message.
The receiver uses the same secret key to
decrypt the message.
S y m m e t r ic
C r yp to s ys te m
S y m m e t r ic C h a lle n g e
Main challenge:
Agreeing on the key while maintaining
secrecy.
Trusting a phone system or some
transmission medium.
The interceptor can read, modify, and forge
all messages
K e y Ma na g e me nt
The generation, transmission, and storage of
a key.
All cryptosystems must deal with key
management issues
Because all keys must remain secret there is
often difficulty providing secure key
management.
In t r o d u c t io n o f t h e P u b lic
Key
Created to solve key management
problems.
Created by Whitfield Diffie and Martin
Hellman in 1976.
Also called asymmetric system.
Encryption key: public key
P u b lic K e y
In f r a s t r u c t u r e
Id e a b e h in d P u b lic
Key
B publishes design specs for a padlock
A wants to send B a box
A builds a B padlock, locks the box
B unlocks box using his key
E intercepts box, knows design specs
Goal: E still can’t build a key
Padlock = trapdoor one-way function
P u b lic K e y
C r yp to g r a p h y
A wants to talk to B: computes key X
A sends B fB (X ) (B’s function)
B computes fB -1 (fB (X )) = X
Both A and B know X , use as key for
symmetric encryption
E knows fB (X ); can’t compute X
A symmetric encryption
C r y p t a n a l y s i s Te r m s
Clipertext – only attack – attacter-attempts to
decrypt cliphertext.
Known-plaintext attack – attacter-attempts to
decrypt cliphertext knowledge of some
plaintext.
Chosen-plaintext attack – attacter-attempts
obtains cliphertext corresponding to selected
plaintext.
C r yp to S ys te m
P r o p e r t ie s
Encryption/decryption transformations must be
efficient for all keys.
System must be easy to use.
The security of the system should depend
ONLY on the secrecy of the keys and not on
the secrecy of the encryption/decryption
transformation.
S e c r e c y R e q u ir e m e n t s
If cipher text and plaintext are known, it
should be computationally infeasible to
determine the deciphering algorithm.
It should be computationally infeasible to
systematically determine plaintext from
intercepted cipher text.
A u t h e n t ic it y
R e q u ir e m e n t s
If cipher text and plaintext are known, it
should be computationally infeasible to
determine the deciphering algorithm.
It should be computationally infeasible to
find valid cipher text.
D ig it a l E n c r y p t io n
S ta nd a rd ( D E S )
Developed by IBM in 1972.
Never approved for national security
applications
64-bit plain & cipher text block size.
56-bit true key plus 8 parity bits.
Single chip implementation.
16 rounds transpositions & substitutions.
Symmetric , private key.
A p p lic a t io n s o f D E S
Double DES
Effective key length of 112 bits.
Work factor about the same as single DES.
Triple DES
encrypt with first key.
decrypt with second key.
encrypt with first key.
very secure.
H o w d o We E n c r yp t?
Protocol, or scheme: method of encryption
Cryptovariable, or key: secret information
plaintext
protocol
ciphertext
cryptovariable
Symmetric encryption: decryption is the same
H o w c o u ld w e b r e a k
t h is ?
Case I: we don’t know the protocol
Hard problem in cryptanalysis
“Clark Kent” effect
Case II: we know the protocol
Need to guess the cryptovariable
Only 26 possibilities
S u b s t it u t io n
C ip h e r
Allow any permutation of the alphabet
Key = permutation; 26! possibilities
26! = 403,291,461,126,605,635,584,000,000
Roughly 288: checking 1 billion per second,
would take 12 billion years
Is there a better way?
Al-Kindi, ninth century: frequency analysis
Th e P e r fe c t
C r yp to s ys te m
One-time pad: encrypt each letter with its
own key
-Example: Caesar shift each letter
separately
Ci = Pi + Ki (mod 26)
To encrypt n bits, use n bits of key
This uses up lots of key bits; need to
prearrange
How do you generate key bits?
E n ig m a M a c h in e
German cryptosystem in World War II
Same idea: modify letters
Scrambler disks implement permutation
Rotate after each letter, so many different
permutations used
Additional permutation provided by plugboard
E n ig m a K e y
Key changed daily
3 scramblers in one of 6 orders
-In 1938: 3 of 5, so 60 arrangements
263 = 17,576 settings for scramblers
Billions of plug board settings
Alan Turing: bypassed plug board
Used known plaintext, exhausted over
space
M o d e r n S y m m e t r ic
C r yp to g r a p h y
Assume the protocol is known to the enemy
Only the key is secret
Encryption, cryptanalysis use computers
Operate on bits, rather than letters
DES, AES
Open standards; let everyone try to break it
Closed design often fails (cell phones)
K e y D is t r ib u t io n
Secure communication requires a key
How do you exchange keys securely?
Military: codebooks in field could fall into
enemy hands
Commerce: might not meet face-to-face
Seems to be a Catch-22
P a r a d ig m S h if t
A wants to mail B a letter securely
If they share a “key”, A locks, B unlocks
If not: A puts on padlock, sends box to B
B adds his padlock, sends box back to A
A removes her padlock, sends box to B
B unlocks box, reads letter
Problem: how to translate this to mathematics
A, B agree on information Y
A computes A(Y) B computes B(Y)
Mails it to B Mails it to A
Alcomputes A(B(Y)) B computes B(A(Y))
A(B(Y)) = B(A(Y)) = secret key
“E” knows Y, A(Y), B(Y), but can’t compute key
Problem: how do you make A(B(Y)) = B(A(Y))?
D if f ie -H e llm a n -M e r k le
( 19 7 6 )
Modular Arithmetic
Choose Y , modulus p
A’s function is Y A (mod p)
B’s function is Y B (mod p)
Key is Y A B ≡ Y B A (mod p)
E can’t compute Y A B from Y , Y A , Y B
We think (no one can prove it)
One problem: must communicate to get
O n e -w a y F u n c t io n s
Easy to compute, hard to reverse
Example: f (A ) = Y A (mod p)
f -1(Y A ) is called “discrete log”
Hard to compute (we think)
Could always do exhaustive search
Here, there are p-1 choices
C r y p t o g r a p h ic
P r im it iv e s
Building blocks for algorithms
-Example: one-way functions
Protocols built out of primitives
-Example: Diffie-Hellman-Merkle
Protocols built out of other protocols
-Example: Use Diffie-Hellman to exchange key
Tr a p d o o r O n e -W a y
F u n c t io n s
Another useful primitive
f (X ) is easy to compute
f -1(Y ) is hard for most people to compute
But: easy to compute if you know a secret
There are trapdoor one-way functions
Found by Rivest-Shamir-Adleman, 1977
Rely on difficulty of factoring large integers
D ig it a l S ig n a t u r e
S c he me
A wants to send B a message, sign it
A sends B X and S = fA -1 (X )
B checks that fA (S ) = X
Therefore B knows that S = fA -1 (X )
Only A can compute fA -1 (X ) easily, so A must
have sent the message
Same primitive, new protocol
D ig it a l S ig n a t u r e
P roc e s s
R e v o lu t io n
New ideas made cryptography an option for
commerce
PCs gave everyone computing power
Zimmerman’s PGP: gave everyone access
SSL in web browsers
Q ua ntum
C o m p u t a t io n
Computers revolutionized cryptographic
design and cryptanalysis
Quantum computers may one day do the
same
Quantum key exchange: guaranteed secure
A quantum computer could factor large
integers in polynomial time
