Scribd
Upload
103 views13 pages

Coursera1 2 PDF

- Cryptography is concerned with ensuring secrecy of communication. Until the 1970s, it relied exclusively on secret keys shared between communicating parties, known as private-key or symmetric-key cryptography. - The shift cipher is an example of a private-key encryption scheme. It encrypts messages by shifting each letter by a fixed number of positions, but is insecure due to its small key space of only 26 possible keys. - Modern cryptography follows Kerckhoffs’s principle that the encryption scheme itself should not be secret, and the key space should be large enough to prevent brute-force attacks to discover the secret key.

Uploaded by

Salif Ndiaye
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
103 views13 pages

Coursera1 2 PDF

- Cryptography is concerned with ensuring secrecy of communication. Until the 1970s, it relied exclusively on secret keys shared between communicating parties, known as private-key or symmetric-key cryptography. - The shift cipher is an example of a private-key encryption scheme. It encrypts messages by shifting each letter by a fixed number of positions, but is insecure due to its small key space of only 26 possible keys. - Modern cryptography follows Kerckhoffs’s principle that the encryption scheme itself should not be secret, and the key space should be large enough to prevent brute-force attacks to discover the secret key.

Uploaded by

Salif Ndiaye
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 13

Cryptography

 
Introduc)on  
Classical  cryptography  
•  Un1l  the  1970s,    
–  exclusively  concerned  with  ensuring  secrecy  of  
communica1on  
 
Encryp)on  
Classical  cryptography  
•  Un1l  the  1970s,    
–  relied  exclusively  on  secret  informa1on  (a  key)  
shared  between  the  communica1ng  par1es    
 
Private-­‐key  cryptography    
–  AKA  secret-­‐key  /  shared-­‐key  /  symmetric-­‐key  
cryptography  
Private-­‐key  encryp1on  
key   key  
ciphertext  

c  
k   k  

m  
c  :=  Enck(m)   message/plaintext   m  :=  Deck(c)  

decryp1on  
encryp1on  
Private-­‐key  encryp1on  

k  
c  
m  
c  :=  Enck(m)  
c  
c  
k  

m  :=  Deck(c)  
Private-­‐key  encryp1on  
•  A  private-­‐key  encryp)on  scheme  is  defined  by  a  
message  space  M  and  algorithms  (Gen,  Enc,  Dec):    
–  Gen  (key-­‐genera1on  algorithm):  generates  k  
–  Enc  (encryp1on  algorithm):  takes  key  k  and  message    
m∈M  as  input;  outputs  ciphertext  c    
                                                             c  ←  Enck(m)  
–  Dec  (decryp1on  algorithm):  takes  key  k  and    
ciphertext  c  as  input;  outputs  m  or  “error”  
                         For  
             a
     ll  
     m  mM
       ∈    :=    aDnd  
eckk(c)  
 output  by  Gen,  
Deck(Enck(m))  =  m    
The  shiS  cipher  
•  Consider  encryp1ng  English  text  
•  Associate  a  with  0;    b  with  1;    …;    z  with  25  

•  k  ∈  {0,  …,  25}  


•  To  encrypt  using  key  k,  shiS  every  leZer  of  the  
plaintext  by  k  posi1ons  (with  wraparound)  
•  Decryp1on  just  dhelloworldz
oes  the  reverse  
ccccccccccc
jgnnqyqtnfb
Modular  arithme1c  
•  x  =  x’  mod  N  if  and  only  if  N  divides  x-­‐x’  
•  [x  mod  N]  =  The  remainder  when  x  is  divided  by  N  
–  I.e.,  The  unique  value  x’∈{0,  …,  N-­‐1}  such  that    
x  =  x’  mod  N  
 
•  25  =  35  mod  10  
•  25  ≠  [35  mod  10]  
•  5  =  [35  mod  10]      
The  shiS  cipher,  formally  
•  M  =  {strings  over  lowercase  English  alphabet}  
•  Gen:  choose  uniform  k∈{0,  …,  25}  
•  Enck(m1…mt):  output  c1…ct,  where  
                                             ci  :=  [mi  +  k  mod  26]  
•  Deck(c1…ct):  output  m1…mt,  where          
                                             mi  :=  [ci  -­‐  k  mod  26]  

•  Can  verify  that  correctness  holds…  


Is  the  shiS  cipher  secure?  
•  No  -­‐-­‐  only  26  possible  keys!  
–  Given  a  ciphertext,  try  decryp1ng  with  every  
possible  key  
–  If  ciphertext  is  long  enough  (and  plaintext  is  normal  
English),  only  one  possibility  will  “make  sense”  
Example  
•  Ciphertext  uryybjbeyq
•  Try  every  possible  key…  
–  tqxxaiadxp
–  spwwzhzcwo
–  …  
–  helloworld
Kerckhoffs’s  principle  
•  The  encryp)on  scheme  is  not  secret  
–  The  only  secret  is  the  key  
–  The  key  must  be  chosen  at  random,  kept  secret  

•  Some  arguments  in  favor  of  this  principle  


–  Easier  to  keep  secret  key  than  secret  algorithm  
–  Easier  to  change  key  than  to  change  algorithm  
–  Standardiza1on  
•  Ease  of  deployment  
•  Public  valida1on  
Sufficient  key  space  principle  
•  The  key  space  should  be  large  enough  to  
prevent  “brute-­‐force,”  exhaus1ve-­‐search  
aZacks  

You might also like