QCry1

The adventures of Alice, Bob & Eve in the Quantumland: 

The adventures of Alice, Bob & Eve in the Quantumland Stefano Mancini University of Camerino, Italy

A typical scenario in secret communications : 

A typical scenario in secret communications Alice Bob Eavesdropper

A short dictionary: 

A short dictionary To exchange sensitive info people has always desired secure communications Legitimate users, sender, recipient (Alice & Bob) Eavesdroppers, enemies, third parties (Eve) Cryptology, Cryptography & Cryptoanalysis (steganography) Message (plain-text), cryptogram (cipher-text) Enciphering, deciphering, keys

Outline: 

Outline Part 1: A survey of classical cryptology Part 2: A quantum leap into the future: Quantum Key Distribution (QKD) Part 3: QKD protocols and security Part 4: Beyond QKD

Outline (part 1): 

Outline (part 1) Ancient techniques A historical overview The history of “Enigma” An unbreakable cipher The public key cryptography

Scytale: 

Scytale Permutation of characters 400 BC SPARTA

Ceaser cipher: 

Ceaser cipher ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC ABCDEFGHIJKLMNOPQRSTUVWXYZ ABCDEFGHIJKLMNOPQRSTUVWXYZ 50 BC ROME

Typical Techniques: 

Typical Techniques PERMUTATIONS e.g. Scytale (400 BC) SUBSTITUTIONS e.g. Caesar cipher (50 BC) PERMUTATIONS + SUBSTITUTIONS

Origin of Cryptoanalysis: 

Origin of Cryptoanalysis Baghdad, al-Kindi (800-873) On Deciphering Cryptographic Messages

Typical attack: 

Typical attack Frequency of letters in a typical English text

Counterexamples-Lipograms: 

Counterexamples-Lipograms First lipogram: Lasus of Achaia (600 BC) That's right - this is a lipogram - a book, paragraph or similar thing in writing that fails to contain a symbol, particularly that symbol fifth in rank out of 26 (amidst 'd' and 'f') and which stands for a vocalic sound such as that in 'kiwi'. I won't bring it up right now, to avoid spoiling it… The most famous lipogram: Georges Perec, La Disparition (1969), 85 000 words without the letter e Tout avait l'air normal, mais tout s'affirmait faux. Tout avait l'air normal, d'abord, puis surgissait l'inhumain, l'affolant. Il aurait voulu savoir où s'articulait l'association qui l'unissait au roman : sur son tapis, assaillant à tout instant son imagination, … English translator, Gilbert Adair, in A Void, succeeded in avoiding the letter e as well

From monoalphabethic cipher to polialphabetic cipher: 

From monoalphabethic cipher to polialphabetic cipher The Vigenère cipher (1586) Babbage breaks the Vigenère cipher (1854) a b c d e f g hi j k l m n o p q r s t u v w x y z 1 B C D E F G H I J K L M N O P Q R S T U V W X Y Z A 2 C D E F G H I J K L M N O P Q R S T U V W X Y Z A B 3 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 4 E F G H I J K L M N O P Q R S T U V W X Y Z A B C D ……………. ……………. 26 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Plain

Even more complex ciphers can be broken…..: 

Even more complex ciphers can be broken….. ENIGMA… …and the man who broke it! First computers were constructed to break ENIGMA codes Scrambler’s initial setting represents the key

Code-makers vs Code-breakers: 

Code-makers vs Code-breakers Is there a perfect cipher?

Where the math comes into: 

Where the math comes into Text Message (M) Integers (P) Encryption C=E(P) Decryption P=E -1(C) Integers (P) Text Message (M)

One Time Pad (Vernam Cipher, 1917): 

One Time Pad (Vernam Cipher, 1917) Alice and Bob possess a quantity of secret key material (random numbers) as large as the message to be transmitted If Alice has P={p1,….,pn} She uses K={k1,….,kn} To get the cryptogram C={c1,….,cn}; ci=pi+ki (mod N) Bob receives C, then he subtracts K (mod N) and recovers P One time pad is unbreakable provided the key material is truly random and used only once (Shannon). Drawbacks: trusted channel for key distribution, huge amount of key, generation of truly random numbers.

Slide17: 

One-time pad plaintext KEY cryptogram KEY cryptogram plaintext

…key distribution problem: 

…key distribution problem ? Before they can exchange a secret they must already share a secret !

Possible solutions: 

Possible solutions Public key cryptosystems mathematical, security based on computational complexity (use of one-way functions) Can be broken by quantum computers! Quantum cryptography Physical, security based on fundamental principles of quantum mechanics

The symmetric cryptosystems: 

The symmetric cryptosystems + + + = + = = = Publicly agree the yellow color key key secret color secret color

The Diffie-Hellmann scheme (1976): 

The Diffie-Hellmann scheme (1976) Alice chooses a number A, and keeps it secret. Alice calculates YA mod N= Alice and Bob publicly agree the values for Y and N Alice and Bob publicly exchange the values for  and  Bob chooses a number B, and keeps it secret. Bob calculates YB mod N= Alice calculates A mod N Bob calculates  B mod N The used function is one-way, so whereas it was easy for Alice, Bob to turn A, B into ,  (mod exp) it is very difficult for Eve to reverse the process (discrete log), especially for large numbers

Example: 

Example Alice chooses a number 3, and keeps it secret. Alice calculates 73 mod 11=343 mod 11=2 Alice and Bob publicly agree the values Y=7 and N=11 Alice and Bob publicly exchange the values for 2 and 4 Bob chooses a number 6, and keeps it secret. Bob calculates 76 mod 11=117649 mod 11=4 Alice calculates 43 mod 11=64 mod 11=9 Bob calculates 26 mod 11=64 mod 11=9

The asymmetric cryptosystems: 

The asymmetric cryptosystems Public key locks the box Private key unlocks the box

RSA cryptosystem (1978): 

RSA cryptosystem (1978) Pick up two large prime numbers p,q and compute the product n=pq Notice that (p-1)(q-1)=(n) as p and q are primes Pick up a random integer e [1<e<(n)] coprime with  Compute the inverse d of e mod  [e d=1 mod  ] (Euclid’s algorithm) Create the public key with {e,n} and broadcast it Create the private key with {d,n}

Slide25: 

Represent the message to be transmitted as a sequence of integers {Pi} each in the range 1 to n Encrypt each Pi using the public key: Ei = (Pi)e mod n The receiver decrypts the message using the private key: (Ei)d mod n = Pi Convert {Pi} back to the original message

Example: 

Example

Breaking RSA: 

Breaking RSA Eve needs to know {d,n}. If she could find two factors of n, that is p,q, she easily compute (n) and knowing e could compute d. Thus the security of RSA relies on the assumption that factoring large numbers is computationally hard. In 1977 a challenge was made in Scientific American: break RSA-129. The time needed was estimated in 1016 years! Nevertheless, in 1994 factorization was achieved, but with a cluster of 103 workstations working for 8 months. Shor’s algorithm would factor RSA-129 in few seconds running on a quantum computer at the speed of a desktop PC!

Crypto for fun: the “Bible Code”: 

Crypto for fun: the “Bible Code” In 1997 M. Drosnin claimed that the Bible contains hidden messages which could be discovered by searching for equidistant letter sequences (EDLS). According to this code the Bible contains predictions about the assasination of Kennedy, Sadat….. B. McKay demonstrated the weakness of EDLS by finding in Moby Dick statements about the assassinations of Trotsky, Gandhi…..