QKD = Quantum Key Distribution
Alice Flarend, Bellwood-Antis High School
Bob Hilborn, University of Maryland
SLIDESMANIA.COM
SLIDESMANIA.COM
Agenda
SLIDESMANIA.COM
SLIDESMANIA.COM
News Alert:
Quantum Computers can break internet security
SLIDESMANIA.COM
What is Cryptography
Image: https://bjc.edc.org/Aug2016/bjc-r/cur/programming/3-lists/6-encryption/2-secret-keys.html?topic=nyc_bjc%2F3-lists.topic&course=bjc4nyc.html&novideo&noassignment
SLIDESMANIA.COM
SLIDESMANIA.COM
Engage: Cryptograms – examples of cryptography
https://www.word-game-world.com/easy-cryptograms.html
Try to solve this riddle about weather:
CIPHER:
ANLE VK L EJOXLGJ'K PLZJOVEM ULQM?
EAVKEMO
KEY Hint: A = W E = T
SLIDESMANIA.COM
Discuss: What was your strategy for solving these?�
SLIDESMANIA.COM
How to break a cipher - frequency analysis
Frequency of letters in English
There’s a PATTERN!!
SLIDESMANIA.COM
Historical Connection: Enigma machine from WWII
There was a PATTERN!!
SLIDESMANIA.COM
Traditional Cryptography�The KEY is the key to breaking the cipher
SLIDESMANIA.COM
RSA Cryptography
Riverst, Shamir, and Adleman – 1977
A purely classical algorithm – no quantum
SLIDESMANIA.COM
RSA
Alice and Bob set up an encryption code that they make public. (public encryption, asymmetric code – one code used for encryption, another code for unencryption)
They keep private some additional information that is needed to unencrypt a message.
SLIDESMANIA.COM
Number Theory (Positive Integers)
Prime Numbers
A number is a prime number if it is evenly divisible only by 1 and the number itself.
Which of the following numbers are prime?
SLIDESMANIA.COM
Number Theory (Positive Integers)
Prime Factors
Create a number that is the product of two prime numbers: N = pq.
The Fundamental Theorem of Arithmetic asserts that those prime factors are unique.
Greatest Common Divisor
What are the prime factors of 77?
GCD of 15 and 12?
GCD of 14 and 15?
SLIDESMANIA.COM
Number Theory (Positive Integers)
Cryptography
Use two relatively large prime numbers to create a product that is a very large number.
Use that number and its prime factors to create cryptographic scheme that is difficult to break.
SLIDESMANIA.COM
Number Theory (Positive Integers)
The mod function
quotient
remainder
divisor
dividend
What time is it?
SLIDESMANIA.COM
Mod Examples
SLIDESMANIA.COM
Modular Exponentiation
What does this look like as a function of b?
SLIDESMANIA.COM
Modular Exponentiation
What is r for this example?
a = 5
On the web:
Power Mod Calculator
Modular Exponentiation Calculator
SLIDESMANIA.COM
RSA Algorithm
and sends c to Alice.
Modular Inverse
Mod Expon.
Mod Expon.
GCD(K,y) in Excel
SLIDESMANIA.COM
RSA Algorithm Example
and sends c to Alice. Bob chooses m = 73.
K and (p-1)(q-1) must be “co-prime.”
Modular exponentiation
The Modular Inverse
(Extended Euclid method)
Modular exponentiation
Greatest common divisor
(Euclid method)
SLIDESMANIA.COM
RSA Cryptography
To crack the RSA encryption, you would need to find the prime factors of N =pq.
For large N (more than 1000 bits), impossible to do in a reasonable amount of time with traditional computers.
The Shor algorithm shows how to use some quantum “tricks” to find those factors.
SLIDESMANIA.COM
The Shor Algorithm
How to use the properties of quantum states to find the prime factors of large numbers. Once you know those prime factors, you can unencrypt the coded messages.
Set b = 0
If you can find the period r, then you get p and q.
How to find the period: Quantum Fourier Transform makes use of superposition to speed up finding the period.
If r is even
SLIDESMANIA.COM
The Shor Algorithm
If the Shor Algorithm can be implemented with enough qubits, then encryption codes which depend on knowing prime factors will be vulnerable.
Better idea: Devise a way to detect if anyone has been eavesdropping on your communications channel.
SLIDESMANIA.COM
Quantum Cryptography with polarized photons
SLIDESMANIA.COM
Picket Fence Analogy:
Wave Model
But what about polarization at an angle?
SLIDESMANIA.COM
Classical Explanation – Vector Components
https://www.sciencefacts.net/malus-law.html
http://www.physicshandbook.com/laws/maluslaw.htm
I = Io cos θ
SLIDESMANIA.COM
Light Polarization can also be explained using Quantum and Photons!
SLIDESMANIA.COM
Quickest introduction to quantum mechanics EVER Thanks to IQC
If a particle can be “here” or “there”…
quantum physics allows it to be “here” AND “there”
AND
Rule #1 works… as long as you don’t look!
If you measure it, you can change it
OR
SLIDESMANIA.COM
Rule #1 Superposition BEFORE measurement
SLIDESMANIA.COM
Rule #2 Measurement
SLIDESMANIA.COM
Photons & Polarizers https://quantumatlas.umd.edu/entry/measuring-polarization/�Superposition depends on measurement basis
SLIDESMANIA.COM
Sending a message with binary using polarized photons
What if basis and photon do not match? Ex with + basis SUPERPOSITION
Randomly (flip a coin) determine bit
SLIDESMANIA.COM
BB84 Protocol with polarized photons
SLIDESMANIA.COM
SLIDESMANIA.COM
St. Andrews QuVis site
SLIDESMANIA.COM
WHY do Alice & Bob only keep the bits where the basis is the same?
with a + basis versus a X basis.
Can you explain using a
Golden Rule?
Rule #1
Superposition
A photon can behave�as if it is both
“here” AND “there”
Rule #2
Measurement uncertainty
When asked, the photon will be found either “here” OR “there”
SLIDESMANIA.COM
Why is the key made only when preparation and measurement basis are the same?
SLIDESMANIA.COM
Steps for quantum cryptography
37
Alice chooses bits for key
Bob chooses basis to measure Alice’s photons
Alice chooses basis to encode bits
Alice generates photons using bits and basis
Detector generates bits for Bob from Alice’s photons & Bob’s basis
Alice & Bob compare basis and keep only those bits where they match as the key
SLIDESMANIA.COM
Try it with spreadsheets��Player chooses first ten then the next 90 are generated randomly
SLIDESMANIA.COM
Alice Chooses Bits, Base and generates photons��https://bit.ly/OPTYCSQKD
SLIDESMANIA.COM
Bob chooses measuring Bases
SLIDESMANIA.COM
Key Generation: Alice and Bob PUBLICLY share basis
SLIDESMANIA.COM
Why is this unbreakable?
SLIDESMANIA.COM
What comes next after choosing key?
Use the key & XOR to encrypt a message
Then Bob uses key and XOR to decrypt
0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0
SLIDESMANIA.COM
SLIDESMANIA.COM
There is another advantage
You can catch an eavesdropper
This Photo by Unknown Author is licensed under CC BY-NC-ND
SLIDESMANIA.COM
SLIDESMANIA.COM
Eve Intercepts the photons from Alice
Discuss: What if Eve’s basis is different from Alice’s?
SLIDESMANIA.COM
Golden Rule
Rule 1: Superposition Principle
Rule 2: Measurement Principle
46
SLIDESMANIA.COM
Eve can change the photon
If Eve’s basis does not match Alice’s basis,
The photon is in a state of superposition
There is a 50% chance of reading a different bit
Eve will transmit a photon in her different basis
50% chance Eve will transmit a photon representing a different bit
47
SLIDESMANIA.COM
How is EVE caught?
Alice and Bob publicly share subset of their KEY bits and check that they match
IF they don’t match = EAVESDROPPING
Note: those shared bits are then NOT part of the key
48
SLIDESMANIA.COM
Overview with St. Andrews Quvis website��
SLIDESMANIA.COM
Detecting Eve:
50
SLIDESMANIA.COM
Detecting Eavesdropping -Comparing part of the key
51
Alice & Bob have the same bases
But they have different bits
someone “listened” (measured) who changed the photon
SLIDESMANIA.COM
Sometimes Eve gets away with it!!
52
Alice & Bob compare many bits, but still a small part of the overall key which is millions of bits
Eve is caught
Eve succeeds
SLIDESMANIA.COM
SLIDESMANIA.COM
Department of Shameless Commerce
SLIDESMANIA.COM
SLIDESMANIA.COM