Introduction to Crypto's enclave¶
Cryptosystems¶
A cytposystem consists of the following parts:
- A set $\mathcal{P}$ called the set of plaintext units.
- A set $\mathcal{C}$ called the set of ciphertext units.
- A set $\mathcal{K}$ called the set of key space
- For every $k \in \mathcal{K}$, an encryption map $Enc_k:\mathcal{P}\rightarrow \mathcal{C}$
- For every $k \in \mathcal{K}$, an decryption map $Dec_k:\mathcal{C}\rightarrow \mathcal{P}$
- A map $Priv: \mathcal{K} \rightarrow \mathcal{K}$ such that: $$Dec_{Priv(k)} \circ Enc_k = id_{\mathcal{K}}, \ \ \ \forall k \in \mathcal{K} $$
The three main types of cryptographic functions¶
- Symmetric Key Encryption
- Public Key Encryption
- Hash Function
Why do we need public cryptosystem?¶
from ipywidgets import interact, interactive, fixed
from IPython.display import clear_output, display, HTML
def numberOfKeyExchange(n):
return str(n*(n-1)/2)+" keys exchanges"
w = interactive(numberOfKeyExchange, n=(int(1), int(3000)))
display(w)
In general we need $\binom{n}{2}$ keys
from sage.all import *
from random import randint
Number Theory¶
- Definitions
- Review
- Theorems
- Practice
- Modular arithmetic
- Applying previous tools in modular arithmetic
- Natural numbers are denoted symbolically as $\mathbb{N}=\{1, 2, 3, \dots \}$
- Integers are denoted symbolically as $\mathbb{Z}=\{\dots, -3, -2, -1, 0, 1, 2, 3, \dots \}$
- Motivation: solving all equations of the form $a+x = b$
- Note: Some authors refer to $\mathbb{N}$ as $\mathbb{Z^+}$
- Rational numbers are denoted symbolically as $\mathbb{Q} = \{ \frac{a}{b}: a, b \in \mathbb{Z} \wedge b \neq 0 \}$
- Motivation: solving all equations of the form $a\cdot x = b$
Let $a$ and $b$ in $\mathbb{Z}$, we say $b$ is divisible by $a$ if and only if there is exists $c\in\mathbb{Z}$ such that $b = a\cdot c$.
Notation: If $a$ divides $b$ we shall write it as $a|b$
Example: $30=6\cdot5$ If $b$ is NOT divisible by $a$ then $b = a \cdot k + r$ we call $k$ the quotient
Definitions¶
GCD: Greatest Common Divisor of two integers $a$ and $b$ is the largest positive number that divides both of them or equivalently:
- $\ d|a \ , d|b$
- If $c|a \ , c|b \Rightarrow c|d$
LCM: Least Common Mmultiple of two integers $a$ and $b$ is the least positive number that divisible by both $a$ and $b$:
- $\ a|l \ , b|l$
- If $a|c \ , b|c \Rightarrow l|c$
Lemma: Let $a, b \in \mathbb{Z}$, by long division we have $b = a \cdot k + r$ where $r Euclidean Algorithm is just applying this lemma iteratively. Example: $gcd(50,3)$ Example: $gcd(55,34)$
primes = [i for i in range(50) if is_prime(i)]
Prime numbers: are those that are only divisible by themself and one
Example: All primes less than 50 are [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
The number of primes less than $n$ is approximately $\frac{n}{ln(n)}$
Prime numbers have nice properties, for instance:
For any $a\in \mathbb{Z} $ and any prime $p$ we have
$$gcd(a,p) = \left\{ \begin{array}{ll} 1 & \mbox{if } p \not | a \\ p & \mbox{if } p | a \end{array} \right. $$Lemma: Let $p$ be a prime number then $gcd(a, p) = 1$ for all $1\leq a < p$
Fundamental theorem of arithmetic: Any $b \in \mathbb{N}$ can be written uniquely as product of positve powers of primes. $$n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\dots p_k^{\alpha_k}, \ \ where \ p_1 < p_2 < \dots < p_K, \ 1 \leq \alpha_i$$
One can use fundemental theorem of arithmetic to find $gcd$ and $lcm$
Excercise
Bezout theorem: For any $a, b \in \mathbb{Z}$ there are two integers $x$ and $y$ such that $$gcd(a, b) = x\cdot a + y \cdot b$$
from time import sleep
def printNumber(i):
if i%10 == 1:
return str(i)+ "st row"
elif i%10 == 2:
return str(i)+ "nd row"
else:
return str(i)+"th row"
def bezout(a, b, i=1, first = True, a_1 = 0, b_1=0):
if first == True:
a_1 = a
b_1 = b
print ("We would like to find Bezout coefficients of %d and %d")%(a, b)
print("That is x and y such that gcd(%d, %d) = x*%d+y*%d")%(a,b,a,b)
print ("__________________________________________________")
print "Initializing first equation:", "%d = (1)*%d + (0)*%d"%(a,a,b)
print "Initializing secod equation:", "%d = (0)*%d + (1)*%d"%(b,b,a)
#a = (a, 1, 0)
#then
a = (a, 1, 0)
b = (b, 0, 1)
if b[0] == 0:
print ("__________________________________________________")
return
quotient = a[0]//b[0]
a = (a[0]%b[0], a[1] - quotient*b[1],a[2] - quotient*b[2])
#sleep(2)
print printNumber(i)+" -(%d)*"%quotient +printNumber(i+1)+":-----> " + \
"%d = (%d)*%d + (%d)*%d"%(a[0],a[1],a_1, a[2],b_1)
return bezout(b,a, i+1, False, a_1, b_1)
Bezout = interactive(bezout, a = (2, 500), b = (2, 500), i = fixed(1),a_1 = fixed(0),b_1 = fixed(0), first=fixed(True) )
display(Bezout)
Modular arithmetic¶
Defintion: $\mathbb{Z}/n\mathbb{Z} $¶
For integers $a$ and $b$ we say $a \equiv b \ mod \ n \Leftrightarrow n| (a-b)$
Equivalently, take $a \in \mathbb{Z}$ and write $a = k\cdot b + r$ then $a \equiv r \ mod \ n$
In any mod $n$ there are only finite number of remainders, namely $\{0, 1, 2, \dots, n-1\}$
Definition $\mathbb{Z}/n\mathbb{Z} $¶
Let $a,\ b\ $ integers and m a positive integer: $$a \equiv b \ mod \ m \Leftrightarrow m| (a-b)$$
Equivalently, take $a \in \mathbb{Z}$, by euclidean algorithm:
$$\begin{alignat}{2} \Leftrightarrow && a &= qm +r \\ \Leftrightarrow && a-r &= qm \\ \Leftrightarrow && m &|(a-r) \\ \Leftrightarrow && a &\equiv b \ mod \ m \end{alignat}$$["%d mod 3 is "%i +str(i%3) for i in range(16)]
Arithmetic over $\mathbb{Z}/n\mathbb{Z} $¶
is very similar to arithmetic over usuall integers with the exception that we have many zeros, that are any multiple of $n$.
Actually it is possible to do the following, although not efficient:
- Compute $a+b \in \mathbb{Z}$
- Compute $a\cdot b \in \mathbb{Z}$
- Reduce them modulo $n$
Divisibilty by three¶
It is well known that a number $a=a_k10^k+ a_{k-1}10^{k-1}\dots+ a_0$ is divisible by three iff $3|a_k+a_{k-1}+\dots+ a_0$ Example: 357 , 3|3+5+7=15
In modular arithmetic this fact can be proved easily!
Divisibilty by three¶
We can write: $$\begin{align*} n = 10^m \cdot b_m + \dots + 10^2 \cdot b_2 + 10^1 \cdot b_1 + 10^0 \cdot b_0 \end{align*}$$
But: $$\begin{align*} &&10 &\equiv 1 \ mod \ 3 \\ &&\Rightarrow 10^2 &\equiv 1^2 \equiv 1 \ mod \ 3 \\ &&\Rightarrow &\dots \\ &&\Rightarrow 10^m &\equiv 1 mod \ 3 \end{align*}$$
Therefore, $n \equiv b_m + \dots + b_2 + b_1 + b_0 \ mod \ 3$
In particular
$3|n \Leftrightarrow n \equiv 0\ mod \ \Leftrightarrow 3 | (b_m + \dots + b_2 + b_1 + b_0 )$
Note: Same idea applies to divisibility by 9
Digression, read Simple Divisibility Rules for the 1st 1000 Prime Numbers
Example: prove that $167| (166)^{1993} + (167)^{2016}$¶
Example: prove that $167| (166)^{1993} + (167)^{2016}$¶
Well, read it mod 167 then we've got $166 \equiv -1 \ mod\ 167$ and $167 \equiv -1 \ mod\ 167$
Example: prove that $167| (166)^{1993} + (167)^{2016}$¶
Well, read it mod 167 then we've got $166 \equiv -1 \ mod\ 167$ and $167 \equiv -1 \ mod\ 167$
Combining both of them:
$$(-1)^{1993} + (1)^{2016} \equiv 0 \ mod\ 167$$How to solve equations of the form $ax \equiv b \ mod \ n$ ?¶
How to solve equations of the form $ax \equiv b \ mod \ n$ ?¶
Since $ax \equiv b \ mod \ n$ is same as $ax + kn = b $ then we can use Bezout.
Some theorems:¶
- $ax \equiv 1 \ mod \ n$ has a solutuin if and only if $gcd(a, n) = 1$ ($a$ and n are relatively prime)
- Special case when n is a prime then 1, 2, 3, …, p-1 are relatively prime with n
- Notation: It is convenient to write $x \equiv a^{-1} \ mod \ n$, since $a\cdot a^{-1} \equiv 1 \ mod \ n$
Examples of ciphers¶
One to one correspondence Between alphabet with space and elements of $\mathbb{Z}_{27}$
| 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 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
Ceaser cipher¶
- Assume that you have a message: $$[x_1, x_2, ..., x_n], x_i \in \{A, B, \dots, Z\}$$
- Chose a random key $k \in \mathbb{Z}_{26}$ #### Encryption
- $Enc_K ([x_1, x_2, ..., x_n])\\ = [x_1 + k \ mod \ 26 , x_2 + k \ mod \ 26 , ..., x_n + k \ mod \ 26 ]$ #### Decryption
- $Enc_K ([x_1, x_2, ..., x_n])\\ = [x_1 - k \ mod \ 26 , x_2 - k \ mod \ 26 , ..., x_n -k \ mod \ 26 ]$
def ceaserCipher(text, key):
"""Shift given message according to given key"""
alphabet = ['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', ' ']
return ''.join([alphabet[(alphabet.index(t) +key)%27] for t in text.lower()])
%time m = ceaserCipher("kacst lecture", 7)
print
print "kacst lecture encrypted to \"", m, '"'
print
#For each key try to decrypt the ciphertext. The key that gives meaningful message is probably the right one.
%time print [ceaserCipher(m, i) for i in range(27)]
One time pad¶
Assume that you have a message: $$[x_1, x_2, ..., x_n], x_i \in \{A, B, \dots, Z\}$$
Chose a random key K which has same length as the message $$K = [k_1, k_2, ..., k_n], k_i \in \{A, B, \dots, Z\}$$
Encryption¶
- $Enc_K ([x_1, x_2, ..., x_n])\\ = [x_1 + k_1 \ mod \ 26 , x_2 + k_2 \ mod \ 26 , ..., x_n + k_n \ mod \ 26 ]$
Notes:¶
Since computers use binary system, addition in one time pad is XOR (
mod 2)How to exchange the key?
If you have 1TB hard-disk you need another 1TB to store the key.
Achieves the ultimate security, if you use each key one time, and the key is completely random.
message = "Yeled means in Hebrew a boy!."
def encode(message):
"""We assume that we have 90 character, that is letters, numbers,
and symbols. In this list the minimum Ascii number is 32(space)"""
x = Integer(0)
for ind, letter in enumerate(message): x += 90**ind*(ord(letter)-32)
return x
def decode(number):
message = ""
while number:
message += chr(number%90+32)
number //= 90
return message
def encrypt(message, key):
m = [ord(i) -32 for i in message]
k = [ord(i) -32 for i in key]
return ''.join(chr((x^y%90)+32) for x, y in zip(m, k))
randKey = ''.join(chr(randint(32, 122)) for i in message) #Not really random
print message
print encrypt(message, randKey)
encrypt(encrypt(message, randKey), randKey)
How about two-time pad?
XOR it with
To get:
Also:
then we will have:
But xor of two ciphers
Will result
Images source: crypto.stackexchange
Public key schemes¶
Public key schemes¶
- Diffie-Hellman key exchange
$3^1=3, \ 3^2=9, \ 3^3=27, \ 3^4=81, \ 3^5=243, \ 3^6=729, \ 3^7=2187, \ 3^8=6561, \\ 3^9=19683, \ 3^{10}=59049$
$3^1\equiv 3 \ mod 128, \ 3^2\equiv 9 \ mod 128, \ 3^3\equiv 27 \ mod 128, \ 3^4\equiv 81 \ mod 128,\\ 3^5\equiv 115 \ mod 128, \ 3^6\equiv 89 \ mod 128, \ 3^7\equiv 11 \ mod 128, \ 3^8\equiv 33 \ mod 128, \\ 3^9\equiv 99 \ mod 128, \ 3^{10}\equiv 41 \ mod 128$
Discrete logarithm problem (DLP):
Given $a,b \in \mathbb{Z}_n$ such that $a \equiv b^x \ mod \ n$, how can we find $x$
from sage.all import IntegerModRing
Z67 = IntegerModRing(67)
b = Z67(2)
[(i,2**i, b**i) for i in range(10, 20)]
Z1065629 = IntegerModRing(135312599)
five = Z1065629(5)
%time print power_mod(5, 190230839, 135312599) #5^(190230839) mod 135312599
print
%time print discrete_log(119477953,five)
Generator of $\mathbb{Z}_n$ (primitive element): We say g is a generator of $\mathbb{Z}_n$ if $\{g^0=1, g^1, g^2, g^3, \dots , g^{n-1}\} = \mathbb{Z}_{n} ^ * $ where $\mathbb{Z}_{n} ^ * = \mathbb{Z}_{n} - \{0\}$
a = Z67(5)
[(i, Z67(i).multiplicative_order()) for i in range(1, 67)]
generatedByNine = [Z67(9)**i for i in range(1,14)]
print generatedByNine
#[(i, Z67(i).multiplicative_order()) for i in range(1, 67)]
#[Z67(2)**i for i in range(1,67)]
Diffie-Hellman¶
This is a very widely used algorithm that allows two programs A and B that communicate over an unsecured channel to agree on a shared secret. Here's how it works.
- Step 1. A and B agree on a prime number $p$ and a number $g$ modulo $p$.
- Step 2. A generates a random number $a
- Step 3. B generates a random number $b
- Step 4. A computes the shared secret $s = (g^{\alpha})^{\beta}\pmod{p}$.
- Step 5. B computes the shared secret $s = (g^{\beta})^{\alpha}\pmod{p}$.
- Step 3. B generates a random number $b
A and B agree on the same secret because $(g^{\alpha})^{\beta} = g^{ab} = (g^{\beta})^{\alpha}$.
Slide source: William Stein's lecture with slight modification
Diffie-Hellman key exchange
| Alice | Bob |
|---|---|
| Chose a large prime p and a generator $g \in \mathbb{Z}_p$ | Waiting |
| sends p,g | |
| Picks a secret key $\alpha$ | Picks a secret key $\beta$ |
| Sends $g^\alpha$ | Sends $g^\alpha$ |
| Computes $(g^\beta)^\alpha = g^{ \beta \alpha} \ mod \ p$ | Computes $(g^\alpha)^\beta = g^{ \alpha \beta } \ mod \ p$ |
| Her key is $g^{ \beta \alpha} \ mod \ p$ | His key is $g^{ \alpha \beta } \ mod \ p$ |
Can $g$ be any number (except 0 and 1)?
p = IntegerModRing(67)
g = p(31)
#g^alpha
AlicePub = g**(53)
BobPub = g**(12)
print "Alice's public key: %d, Bob's public key %d" %(AlicePub, BobPub)
#Shared Key
AliceShared = BobPub**53 #BobPub^alpha
BobShared = AlicePub**12
print "Alice's shared key: %d, Bob's shared key %d" % (AliceShared, BobShared)
A bit of history
Diffie Hellman problem (DHP):
Given $g^a,g^b \in \mathbb{Z}_n$, how can we find $g^{ab}$? Is DHP equivalent to DLP
Man in the middle attack¶
Man in the middle attack:
Public key schemes:¶
- Elgamal's scheme
Elgamal's algoritm:
| Bob | Alice |
|---|---|
| Chose a large prime p and a generator $g \in \mathbb{Z}_p$ | Waiting |
| Picks a secret key $\alpha$ | |
| sends $p,\ g,\ g^\alpha$ | |
| Choose text and a random secret key k | |
| Computes $(g^k \ mod \ p,\ (g^\alpha)^k \cdot m \ mod \ p)$ | |
| Computes $((g^k)^\alpha ) ^{-1}$ | |
| $\begin{align*}(g^{-k \alpha }) (g^{k \alpha)} \cdot &m \\ &\equiv (g^{-k \alpha + k \alpha)} \cdot m \equiv 1 \cdot m \ mod \ p \end{align*} $ |
from random import randint
p = IntegerModRing(67) ; g = p(31); alpha = randint(2,66) #random secret key
BobPub = g**alpha #g^alpha where alpha = 28
print "Bob's public key:\t", BobPub; print "Bob's private key:\t", alpha; print
#Key initialization
key = p(randint(2, 66)); print "Alice's private key:\t", key
print "Alice's public key:\t", g**key
m = p(55); print "Alice wants to encrypt:\t", m
#send (g^key, (g^alpha)^key)
send = (g**key, m*BobPub**key);
print "Alice sends:\t", send
#Decryption
inv_key = (send[0]**-alpha)
print "Bob will get after decryption: ", inv_key*send[1]
Question¶
If Alice used same random number k for the two massages $m_1, m_2$, and Eve found $m_1$ (Something like "Dear Sir/Madam").
Can Eve decrypt the message?
Answer: Yes!
Alice's message is $(g^k \ mod \ p, g^{k\alpha} m_1 \ mod \ p) $ Since Eve has $m_1$, she computes $g^{k\alpha}m_1 m_1^{-1} \equiv g^{k\alpha} \ mod \ p $, then computes $g^{-k\alpha} \ mod \ p $, multiply both equations: $$ g^{-k\alpha}g^{k\alpha}m_2 \equiv m_2 \ mod \ p $$
- If we have an oracle that takes $(g^a, g^b)$, returns $g^{ab}$ can we break ElGamal?
- Also, if we have an oracle that take inputs $(g^\alpha, g^k, g^{\alpha k} m)$, returns m. Can we solve Diffie-Hellman problem?
If we have an oracle that takes $(g^a, g^b)$ and returns $g^{ab}$ can we break Elgamal's algorithm? Also, if we have an oracle that takes $(g^\alpha, g^k, g^{\alpha k} m)$ and returns m. Can we solve Diffie-Hellman problem?
from sympy import FF
prime = 4846894651448415683484959
F = FF(prime)
%time F(7)**4984878
%time F(7)**4984878 #%time F(4241409341529989453281522328479441842243016761087729606646874360412179223922190310563269994787463984608952391920285585674782507167967272599977507805479462160551656395507857905459599452377006903872296165156156342718377660480260378681683746474619739910898399099207081429288009291421955276018029828961499751112865258851245053636260989277329253884466654561231745979009870663793165120800336500954381402402011007507655987813848277789274381728266939235092558097619805371161849885165616060010413760865328271162777559631408924641356662399400914743176913181558078010364806980917711903758731846562671893735748054291104600674201657138183569657138446745088925947117397794477908366395252609492419291791834442466466490625246544538283335422396839635678639861179698267337999287488438717799057143037045424829615376015326282033410964645188954384281072213383359466092661397574503820242042150190227456992923426050346004152977656012399539513529924150012993982947147158916803435513817650816052429203542641694937194095771834')
%time power_mod(7, 4984878, prime)
Fast exponentiation.
We taught in school that $g^a = \underbrace{g\cdot g \dots g }_{a \ times}$. However it would require $a$ multiplication. A widely used method known as Fast exponentiation would reduce it to roughly $log(a)$ squaring and $log(a)$ multiplication.
Fortunately, it is easy to apply fast exponentiation. Write $a = (a_na_{n-1}\dots a_2a_1a_0)_2$ then $$g^a = \left(\left(g^a_n \right)^2\cdot g^a_{n-1})^2 \cdot g^{a_{n-1}\right)$$
Quantum Computations: Very Short Introduction¶
The quantum analogue of bit ($0$ or $1$) is called qbit. Single qbit can be $|0\rangle$, $\ |1\rangle\ $, or $\alpha_0 |0\rangle +\alpha_1 |1\rangle $ where $\alpha_0^2+\alpha_1^2 =1, \alpha_0,\alpha_1 \in \mathbb{C} $
Algebra of qbits¶
$|x_0x_1\dots x_n \rangle|x_{n+1}x_{n+2}\dots x_m \rangle = |x_0 x_1 \dots x_m \rangle$
$\langle \psi | | \phi \rangle = \langle \psi | \phi \rangle = c \in \mathbb{C} $
Any action on qbits is linear $F (\alpha |x_0 \dots x_n\rangle + \beta \alpha |y_0 \dots y_n\rangle) =F \alpha |x_0 \dots x_n\rangle + F\beta \alpha |y_0 \dots y_n\rangle $
- Hence squaring is not premitted function.
$| 0 \rangle =\begin{bmatrix} 1\\ 0\end{bmatrix}$ and $| 1 \rangle =\begin{bmatrix} 0\\ 1\end{bmatrix}$
Example $|6\rangle = \begin{bmatrix}0\\ 0\\ 0\\ 0\\ 0\\ 1_{6th\ row}\\ 0\\ \end{bmatrix}$
Examples of gates¶
- $X$ gate flips qbit, i.e $X|0\rangle = |1\rangle$ and $X|0\rangle = |1\rangle$
- $H$ Hadamard's gate, $H|0\rangle = \frac{1}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$, and $H|1\rangle = \frac{1}{\sqrt{2}}|0\rangle - \frac{1}{\sqrt{2}}|1\rangle$
A common trick in quantum computation is to apply Hadamard on each qbit before processing
Due to linearity any function, $f: |x_0 \dots x_n\rangle \rightarrow |x_0 \dots x_n\rangle$, acts on qbits must be reversible.
Computer scietists (or phyisicsts) came up with an idea which is, essentially, add qbits to store the result.
$$f\underbrace{|x_0x_1 \dots x_n \rangle}_{input} \underbrace{|y_0 \dots y_n \rangle }_{output}= \underbrace{|x_0x_1 \dots x_n \rangle}_{input} \underbrace{|y_0 \dots y_n \oplus f(x_0x_1 \dots x_n )\rangle}_{output} $$Apply it again $$ f\underbrace{|x_0x_1 \dots x_n \rangle}_{input} \underbrace{|y_0 \dots y_n \oplus f(x_0x_1 \dots x_n )\rangle}_{output} = \underbrace{|x_0x_1 \dots x_n \rangle}_{input} \underbrace{|y_0 \dots y_n \rangle }_{output} $$
A common trick in quantum computation is apply Hadamard on each qbit before processing them. This would allow us to process all possible combinations at once. The only pitfall, we are able to see one of them only.
from sympy.physics.quantum.gate import HadamardGate
from IPython.display import display, Math, Latex
from sympy import Matrix, sqrt, exp, pi, latex, evalf, var
from sympy.physics.quantum import qapply #Applying gates
from sympy.physics.quantum.gate import HadamardGate
from sympy.physics.quantum.qubit import Qubit, matrix_to_qubit, qubit_to_matrix, represent #Our basic set of tools
def printing(expression):
display(Math(latex(expression)))
def n_fold_Hadamard(n):
H = HadamardGate(0)
for i in range(n-1):
H *= HadamardGate(i+1)
return H
zero_state = Qubit("000")
printing(qapply(n_fold_Hadamard(3)*zero_state))
No cloning theorem¶
There is no unitary transformation U$|\psi\rangle |0\dots0\rangle = |\psi\rangle|\psi\rangle$
Quantum algorithm for key exchange¶
| Alice | Bob | |
|---|---|---|
| Prepares a random $ | x_1 x_2 \dots x_m \rangle$ | Waiting |
| Randomly choose $ | x_i \rangle$ | Waiting |
| Send it through insecure channel to send it through H gate | ||
| Waiting | Receives $ | x'_1 x'_2 \dots x'_m \rangle$ |
| Waiting | Randomly choose $ | x'_i \rangle$ to send it through H gate |
| Alice | Bob |
|---|---|
| Tell Bob using same channel which qbit was subject to H gate | Listening |
| Waiting | Discard any qbit that that has been sent to H gate if it has NOT been sent to H gate by Alice. Does the same for each qbit has been sent directly to measurement device. |
| Listening | Tell Alice using same channel which qbit was subject to H gate |
def printOutput():
from IPython.display import Math, display
from random import randint
message = "1010011001010010"
#message = ''.join([str(randint(0,1)) for i in range(16)])
#print "Alice want to send: ", message
def applyHRand(string, indices):
"""Applying measurement aftet H gate according to indices, where 0
means don't apply H and 1 apply, to get a random result.
Notice: while H gat is inversible this one is NOT"""
result = list(string)
for ind, char in enumerate(indices):
if char == 1:
result[ind] = str(randint(0,1))
return ''.join(result)
AliceP = [randint(0,1) for i in message] #Alice decides to apply H according to this list
BobP = [randint(0,1) for i in message]
#print "Alice will subject following bit to H gate", [i for i in range(16) if AliceP[i] == 1]
#print "Bob will subject following bit to H gate", [i for i in range(16) if BobP[i] == 1]
#print "So they both will consider bits with indices: ", [i for i in range(16) if (AliceP[i] == BobP[i])]
def findDifferences(lis1, m1, lis2, m2, eve=[]):
result1 = ""
result2 = ""
resultAlice = ""
resultBob = ""
for ind, char in enumerate(lis1):
#print lis1[ind], lis2[ind], lis1[ind] == lis2[ind]
if lis1[ind] == lis2[ind]:
#print "I am in if"
result1 += m1[ind]
if eve:
result2 += eve[ind]
resultBob += eve[ind]
resultAlice += m1[ind]
else:
result2 += m1[ind]
resultAlice += m1[ind]
resultBob += m1[ind]
elif lis1[ind] != lis2[ind]:
#print "I am in elif"
#print result1
result1 += r"\color{red}{"+ m1[ind] + r"}"
result2 += r"\color{red}{"+ m2[ind] + r"}"
#print result1
else:
pass
return (r"|"+result1+r"\rangle",r"|"+result2+r"\rangle",r"|"\
+resultAlice+r"\rangle", r"|" + resultBob + r"\rangle")
BobMessage = applyHRand(message,BobP)
after_communication = findDifferences(AliceP, message, BobP, BobMessage)
print "Alice wants to send: ", message
print "Alice will subjects following bit to H gate", [i for i in range(16) if AliceP[i] == 1]
print "Bob will subjects following bit to H gate", [i for i in range(16) if BobP[i] == 1]
#print "So they both will consider bits with indices: ", [i for i in range(16) if (AliceP[i] == BobP[i])]
print
print "Alice's message is: "
display(Math(after_communication[0]))
display(Math(after_communication[1]))
#print "What Bob has --^"
#print "Their shared key is: ",
display(Math(r"Alice's\ shared\ key\ "+after_communication[2]))
display(Math(r"Bob's\ shared\ key\ "+after_communication[3]))
def printOutput():
from IPython.display import Math, display
from random import randint
#message = ''.join([str(randint(0,1)) for i in range(16)])
message = "1010011001010010"
#print "Alice want to send: ", message
def applyHRand(string, indices):
"""Applying measurement aftet H gate according to indices, where 0
means don't apply H and 1 apply, to get a random result.
Notice: while H gat is inversible this one is NOT"""
result = list(string)
for ind, char in enumerate(indices):
if char == 1:
result[ind] = str(randint(0,1))
return ''.join(result)
AliceP = [randint(0,1) for i in message] #Alice decides to apply H according to this list
BobP = [randint(0,1) for i in message]
#print "Alice will subject following bit to H gate", [i for i in range(16) if AliceP[i] == 1]
#print "Bob will subject following bit to H gate", [i for i in range(16) if BobP[i] == 1]
#print "So they both will consider bits with indices: ", [i for i in range(16) if (AliceP[i] == BobP[i])]
def findDifferences(lis1, m1, lis2, m2, eve=[]):
result1 = ""
result2 = ""
resultAlice = ""
resultBob = ""
for ind, char in enumerate(lis1):
#print lis1[ind], lis2[ind], lis1[ind] == lis2[ind]
if lis1[ind] == lis2[ind]:
#print "I am in if"
result1 += m1[ind]
if eve:
result2 += eve[ind]
resultBob += eve[ind]
resultAlice += m1[ind]
else:
result2 += m1[ind]
resultAlice += m1[ind]
resultBob += m1[ind]
elif lis1[ind] != lis2[ind]:
#print "I am in elif"
#print result1
result1 += r"\color{red}{"+ m1[ind] + r"}"
result2 += r"\color{red}{"+ m2[ind] + r"}"
#print result1
else:
pass
return (r"|"+result1+r"\rangle",r"|"+result2+r"\rangle",r"|"\
+resultAlice+r"\rangle", r"|" + resultBob + r"\rangle")
BobMessage = applyHRand(message,BobP)
after_communication = findDifferences(AliceP, message, BobP, BobMessage)
print "Alice wants to send: ", message
print "Alice will subjects following bit to H gate", [i for i in range(16) if AliceP[i] == 1]
print "Bob will subjects following bit to H gate", [i for i in range(16) if BobP[i] == 1]
print "So they both will consider bits with indices: ", [i for i in range(16) if (AliceP[i] == BobP[i])]
print
print "Alice's message is: "
display(Math(after_communication[0]))
display(Math(after_communication[1]))
print "What Bob has --^"
print "Their shared key is: ",
display(Math(r"Alice's\ shared\ key\ "+after_communication[2]))
display(Math(r"Bob's\ shared\ key\ "+after_communication[3]))
printOutput()
- On average half of qbits are discarded.
- What if there is an adversary?
- How can Bob verify the message has not been manipulated?
def printOutput2():
from IPython.display import Math, display
from random import randint
message = "1010011001010010"
#message = ''.join([str(randint(0,1)) for i in range(16)])
#print "Alice want to send: ", message
def applyHRand(string, indices):
"""Applying measurement aftet H gate according to indices, where 0
means don't apply H and 1 apply, to get a random result.
Notice: while H gat is inversible this one is NOT"""
result = list(string)
for ind, char in enumerate(indices):
if char == 1:
result[ind] = str(randint(0,1))
return ''.join(result)
AliceP = [randint(0,1) for i in message] #Alice decides to apply H according to this list
BobP = [randint(0,1) for i in message]
#print "Alice will subject following bit to H gate", [i for i in range(16) if AliceP[i] == 1]
#print "Bob will subject following bit to H gate", [i for i in range(16) if BobP[i] == 1]
#print "So they both will consider bits with indices: ", [i for i in range(16) if (AliceP[i] == BobP[i])]
def findDifferences(lis1, m1, lis2, m2, eve=[]):
result1 = ""
result2 = ""
resultAlice = ""
resultBob = ""
for ind, char in enumerate(lis1):
#print lis1[ind], lis2[ind], lis1[ind] == lis2[ind]
if lis1[ind] == lis2[ind]:
#print "I am in if"
result1 += m1[ind]
if eve:
result2 += eve[ind]
resultBob += eve[ind]
resultAlice += m1[ind]
else:
result2 += m1[ind]
resultAlice += m1[ind]
resultBob += m1[ind]
elif lis1[ind] != lis2[ind]:
#print "I am in elif"
#print result1
result1 += r"\color{red}{"+ m1[ind] + r"}"
result2 += r"\color{red}{"+ m2[ind] + r"}"
#print result1
else:
pass
return (r"|"+result1+r"\rangle",r"|"+result2+r"\rangle",r"|"\
+resultAlice+r"\rangle", r"|" + resultBob + r"\rangle")
#BobMessage = applyHRand(message,BobP)
#after_communication = findDifferences(AliceP, message, BobP, BobMessage)
print "Alice want to send:\t ", message
def altering_message(lis1, m1, lis2, m2):
result1 = ""
result2 = ""
# result3 = ""
for ind, char in enumerate(lis1):
#print lis1[ind], lis2[ind], lis1[ind] == lis2[ind]
if lis1[ind] == lis2[ind]:
#print "I am in if"
result1 += m1[ind]
result2 += m1[ind]
#result3 += m1[ind]
elif lis1[ind] != lis2[ind]:
#print "I am in elif"
#print result1
result1 += m1[ind]
result2 += m2[ind]
#print result1
else:
pass
return (result1, result3)
EveP = [randint(0,1) for i in message] #Eve applies H gate according to this list
EveMessage = applyHRand(message,EveP)
BobMessage = applyHRand(EveMessage, BobP)
print "Eve changes the message to: ", BobMessage
altered_message = findDifferences(AliceP, message, BobP, BobMessage,EveMessage)
display(Math(altered_message[0]))
display(Math(altered_message[1]))
display(Math(r"Alice\ thinks\ the\ shared\ key\ is:\ " + altered_message[2]))
display(Math(r"Bob\ thinks\ the\ shared\ key\ is:\ " + altered_message[3]))
printOutput2()
- The best the adversary can do is to imitate Bob, but she will change state of half of the qbits
- If Bob want to check the key, he will take a sample and contact Alice in insecure channel, then ask her about values of corresponding qbit .
Crypto@C4C: past, present, future¶
Past¶
Caesar competition¶
Authenticated encryption: Dr. Basel, Ahmed Mohammed, Abdulrahman.
Trainings¶
- Crash course on cryptography in which the instructor was Andrey Bogdanov
- Crash course on side channel attakcs
- Summer school Discrete mathematics and its applications
present¶
- CyberLab
- Devices
- Oscilscope: 20Gh sampling frequency
- Pineata board
- Software
- An open source software for side channel provided by Riscure
- Various open source software that can be found on the internet
- Devices
Student project¶
Under CARE Crypt Analysis Research Enclave In which we are asked to create and test a customized AES s-box