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)

'2037171 keys exchanges'

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)

We would like to find Bezout coefficients of 306 and 237
That is x and y such that gcd(306, 237) = x*306+y*237
__________________________________________________
Initializing first equation: 306 = (1)*306 + (0)*237
Initializing  secod equation: 237 = (0)*237 + (1)*306
1st row -(1)*2nd row:----->  69 = (1)*306 + (-1)*237
2nd row -(3)*3th row:----->  30 = (-3)*306 + (4)*237
3th row -(2)*4th row:----->  9 = (7)*306 + (-9)*237
4th row -(3)*5th row:----->  3 = (-24)*306 + (31)*237
5th row -(3)*6th row:----->  0 = (79)*306 + (-102)*237
__________________________________________________

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)]

['0 mod 3 is 0',
 '1 mod 3 is 1',
 '2 mod 3 is 2',
 '3 mod 3 is 0',
 '4 mod 3 is 1',
 '5 mod 3 is 2',
 '6 mod 3 is 0',
 '7 mod 3 is 1',
 '8 mod 3 is 2',
 '9 mod 3 is 0',
 '10 mod 3 is 1',
 '11 mod 3 is 2',
 '12 mod 3 is 0',
 '13 mod 3 is 1',
 '14 mod 3 is 2',
 '15 mod 3 is 0']

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}$¶

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$ ?¶

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)]

CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 25 µs

kacst lecture encrypted to " rhjz gslj ayl "

['rhjz gslj ayl', 'sik ahtmkabzm', 'tjlabiunlbc n', 'ukmbcjvomcdao', 'vlncdkwpndebp', 'wmodelxqoefcq', 'xnpefmyrpfgdr', 'yoqfgnzsqghes', 'zprgho trhift', ' qshipausijgu', 'artijqbvtjkhv', 'bsujkrcwukliw', 'ctvklsdxvlmjx', 'duwlmteywmnky', 'evxmnufzxnolz', 'fwynovg yopm ', 'gxzopwhazpqna', 'hy pqxib qrob', 'izaqryjcarspc', 'j brszkdbstqd', 'kacst lecture', 'lbdtuamfduvsf', 'mceuvbngevwtg', 'ndfvwcohfwxuh', 'oegwxdpigxyvi', 'pfhxyeqjhyzwj', 'qgiyzfrkiz xk']
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 354 µs

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)

Yeled means in Hebrew a boy!.
"q#3s#��9��r�mx<y�'��q�!e�wl!

'Yeled means in Hebrew a boy!.'

How about two-time pad?

$$M_1 \oplus K$$$$M_2 \oplus K$$$$M_1 \oplus K \oplus M_2 \oplus K = M_1 \oplus M_2$$

XOR it with To get:

Also: then we will have:

But xor of two ciphers Will result

Images source: crypto.stackexchange

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)]

[(10, 1024, 19),
 (11, 2048, 38),
 (12, 4096, 9),
 (13, 8192, 18),
 (14, 16384, 36),
 (15, 32768, 5),
 (16, 65536, 10),
 (17, 131072, 20),
 (18, 262144, 40),
 (19, 524288, 13)]

Z1065629 = IntegerModRing(135312599)
five = Z1065629(5)
%time print power_mod(5, 190230839, 135312599) #5^(190230839) mod 135312599
print 
%time print discrete_log(119477953,five)

119477953
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 71 µs

54918241
CPU times: user 24 ms, sys: 4 ms, total: 28 ms
Wall time: 37.1 ms

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)]

[9, 14, 59, 62, 22, 64, 40, 25, 24, 15, 1, 9, 14]

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}$.

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)

Alice's public key: 57, Bob's public key 59
Alice's shared key: 22, Bob's shared key 22

A bit of history

Merkle, Hellman, Diffie

Gillman

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]

Bob's public key:	50
Bob's private key:	47

Alice's private key:	19
Alice's public key:	63
Alice wants to encrypt:	55
Alice sends:	(63, 8)
Bob will get after decryption:  55

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)

CPU times: user 52 ms, sys: 8 ms, total: 60 ms
Wall time: 60.7 ms
CPU times: user 56 ms, sys: 0 ns, total: 56 ms
Wall time: 56.2 ms
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 21.9 µs

4567605731036734160777249L

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()

Alice wants to send:  1010011001010010
Alice will subjects following bit to H gate [0, 5, 6, 9, 10, 11, 15]
Bob will subjects following bit to H gate [3, 6, 8, 11, 15]
So they both will consider bits with indices:  [1, 2, 4, 6, 7, 11, 12, 13, 14, 15]

Alice's message is:

What Bob has --^
Their shared key is:

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()

Alice want to send:	     1010011001010010
Eve changes the message to:  1110001000011010

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

Student project¶

Under CARE Crypt Analysis Research Enclave In which we are asked to create and test a customized AES s-box

Introduction to Crypto's enclave¶

Cryptosystems¶

The three main types of cryptographic functions¶

Why do we need public cryptosystem?¶

Number Theory¶

Definitions¶

Modular arithmetic¶

Defintion: $\mathbb{Z}/n\mathbb{Z} $¶

Definition $\mathbb{Z}/n\mathbb{Z} $¶

Arithmetic over $\mathbb{Z}/n\mathbb{Z} $¶

Divisibilty by three¶

Divisibilty by three¶

Example: prove that $167| (166)^{1993} + (167)^{2016}$¶

Example: prove that $167| (166)^{1993} + (167)^{2016}$¶

Example: prove that $167| (166)^{1993} + (167)^{2016}$¶

How to solve equations of the form $ax \equiv b \ mod \ n$ ?¶

How to solve equations of the form $ax \equiv b \ mod \ n$ ?¶

Some theorems:¶

Examples of ciphers¶

Ceaser cipher¶

One time pad¶

Encryption¶

Notes:¶

Public key schemes¶

Public key schemes¶

Diffie-Hellman¶

Man in the middle attack¶

Public key schemes:¶

Question¶

Quantum Computations: Very Short Introduction¶

Algebra of qbits¶

Examples of gates¶

No cloning theorem¶

Quantum algorithm for key exchange¶

Crypto@C4C: past, present, future¶

Past¶

Caesar competition¶

Trainings¶

present¶

Student project¶

Thank you¶

Any questions?¶