Tuesday, April 24, 2018

letsencrypt wildcard ssl certificate on Amazon Linux + Apache

mkdir certbot
cd certbot
chmod a+x certbot-auto
sudo ./certbot-auto certonly  --server https://acme-v02.api.letsencrypt.org/directory  --manual --preferred-challenges dns  -d *.domainname.com

For putting TXT record in NameCheap:
In HostName, put _acme-challenge, in value put the string given on the command line.

Then in httpd.conf:

<VirtualHost *:443>
    DocumentRoot "/var/www/html/somepath"
    ServerName other.domainname.com
    ServerAlias *. domainname .com
    SSLCertificateFile /etc/letsencrypt/live/ domainname .com-0001/cert.pem
    SSLCertificateKeyFile /etc/letsencrypt/live/ domainname .com-0001/privkey.pem
    SSLCertificateChainFile /etc/letsencrypt/live/ domainname .com-0001/fullchain.pem
    ErrorLog logs/ domainname -error_log
    CustomLog logs/ domainname -access_log common

    <Directory "/var/www/html/somepath">
        Options Indexes FollowSymLinks
        AllowOverride All
        Order allow,deny
        Allow from all
    </Directory>
</VirtualHost>


Monday, April 23, 2018

Extracting directory name from file paths (after find,grep)

awk -F/  '{print $2}' | uniq

Friday, March 23, 2018

Convolutional neural network course Coursera - Week 1

Edge detection with convolutional filter.
Image is nxn, fxf filter (f is usually odd).

Valid convolution when you don't pad the original image which is nxn, with fxf filter you get n-f+1 x n-f+1 output image which tells where are the edges.
Same convolution when you pad the original image so that every pixel gets equal opportunity to participate in the final output => (n + 2p -f)/s + 1 = n

Strided convolution - when you do the convolution while making a stride. Output image size will be (n + 2p -f)/s + 1.

Convolutions over 3D volumes:

For e.g. RGB image.
Image is 6x6x3 and filter 3x3x3, then you get 4x4 output. First 9 numbers will detect edges in red channel and so on..

Multiple Filters
What if you want to use multiple filters at the same time? For e.g. detect Vertical/Horizontal edges together? Or detect edges at various angles?
In the above example if you apply 2 3x3x3 filters, you will get output as 4x4x2.
Which is n -f + 1 x n - f + 1 x (number of filters).

How to tune parameters
But for now, maybe one thing to take away from this is that as you go deeper in a neural network, typically you start off with larger images, 39 by 39. And then the height and width will stay the same for a while and gradually trend down as you go deeper in the neural network. It's gone from 39 to 37 to 17 to 14. Excuse me, it's gone from 39 to 37 to 17 to 7. Whereas the number of channels will generally increase. It's gone from 3 to 10 to 20 to 40, and you see this general trend in a lot of other convolutional neural networks as well.

Similar to convolutional layer, there is pooling layer:
for e.g. Max pooling - if a feature is detected anywhere - preserve it.
It has some hyperparameters but no parameters(to learn for gradient descent)
Hyperparameters -> f,s (filter size, stride)

Similarly, average pooling:

Tuesday, January 30, 2018

Cryptography course week 6

Public key encryption

Trapdoor function(TDF)
Secure TDF - G,F,F-1 is secure if F(pk, .) is a "one-way" function: can be evaluated but can't be inverted without sk(secret key). pk is public key. 
Secret key is the trapdoor.

Public key encryption from TDFs

Encryption
1. Choose a random x
2. k <= H(x) where H is a hasher
3. y = F(pk, x) where G,F,F-1 is a secure TDF and pk,sk are generated from G
4. c <= E(k,m) where E,D is symmetric auth. encryption defined over (K,M,C)
5. Output is y,c

Decryption
1. x <= F-1(sk,y)
2. k = H(x)
3. m = D(k,c)

If we apply F directly to m, it becomes deterministic. There is no randomness (which was provided by X).

The RSA Trapdoor permutation
Review: arithmetic mod composites
Let N = p.q where p,q are primes and roughly same size => p,q are almost equal to sqrt(N)
Z_N = (0,1,2...N-1) and Z_N* = set of invertible elements in Z_N
x E Z_N is invertible if gcd(x,N) = 1
number of invertible elements = phi(N) = (p-1)(q-1) = N -p -q +1 ~= N - 2.sqrt(N) ~= N since N is very large(for e.g. 600 digits, so sqrt will be like 300 digits)
So Z_N* ~= Z_N => almost every element in Z_N will be invertible.

Euler's thm For all x E Z_N * => x ^ phi(N) = 1

How RSA works
0. choose random primes p,q roughly 1024 bits, set N = p*q
1. choose e,d s.t. e*d = 1 mod phi(N)
2. pk = (N,e), sk = (N,d) where e is encryption exponent and d is decryption exponent
3. for x E Z_N*, F(pk,x) is RSA(x), RSA(x) = x^e in Z_N
4. to decrypt
5. RSA_1(y) = y^d = (RSA(x))^d = (x^e)^d = x^(e*d), now e*d = 1 mod phi(N) means e*d = k*phi(N) + 1 where k is some integer
6. RSA_1(y)  = x^(k*phi(N) + 1) = x^(k*phi(N))*x, from Euler's thm. x^(phi(N)) = 1 since x E Z_N* => RSA_1(y) = x

Textbook RSA is insecure
Encrypt C = m^e
Decrypt C^d = m

PKCS1
Uses RSA. Insecure since attacker could check if MSB of a cipher text's original message == 2. And could decode the entire message in this way. It's used in HTTPS so they fixed it by reverting to a random 46 byte string in case of erroneous message, so that attacker doesn't get any information about the message.

PKCS2 - OAEP (Optimal Asymmetric Encryption Padding)
Improvement over PKCS1

Public key encryption built from Diffie Hellman Protocol
ElGamal
IDH - Interactive Diffie Hellman
Twin ElGamal


Saturday, January 13, 2018

speed test results

Primary router - TP-Link Archer C60 AC1350 - Dual band
Repeater(bridge) - tp link wr841n
ISP: ACT Broadband
Device: MI A1

Format
ping time, download speed, upload speed

5g - primary
1, 43.92, 34.93
1, 60.44, 48.84
1, 65.8, 51.82
1, 56.5, 48.67
1, 60.67, 51.61

2.4g - primary
1, 32.63, 32.53
1, 49.3, 33.92
1, 44.85, 23.27
1, 40.19, 33.38
1, 58.69, 30.95
1, 37.07, 32.14

2.4g- bridge
1, 39.21, 22.05
1, 31.09, 21.7
1, 22.55, 20.02

Sunday, January 7, 2018

Cryptography course - Basic key exchange

Online Trusted third party(TTP)
If A,B want to communicate, Eavesdropper sees E (K_a, "A,B" || K_ab) and E (K_b, "A,B" || K_ab)
Similar mechanism is basis of Kerberos system.
It's only safe against evaesdropping attacks not against an active attacker.
TTP should always be online.

Active attack
 - If a money transaction is taking place, what if the attacker just replays the request? Since the key is still the same, another transaction would take place.

Key question
 - can we design key exchange protocols without online TTPs?
- Yes! Public key cryptography.

Merkle puzzles
- Quadratic gap between participants and attackers (2^32 vs 2^64)
 - This looks like the best we can achieve from symmetric block ciphers

Diffie Hellman protocol
 - exponential gap
- Fix a large prime p (e.g. 600 digits), Fix an integer g in {1,...,p}
- Alice: choose random a in {1,...,p-1}
- Bob: choose random b in {1,...,p-1}
- A <- g^a mod p
- B <- g^b mod p
- Alice sends A to Bob and she sends B back
- Now the shared key is : g^ab mod p since both of them can compute it.

How hard is DH function mod p?
- suppose Prime p is n bits long
- best known algo (GNFS): run time exp (O(n^1/3)), so exponential in cube root of n.
- to achieve same security as AES 256 bits, we need modulus size 15360 bits in DH
- but only 512 bits if we use Elliptic curves in place of mod p
- as a result there is slow transition away from (mod p) to elliptic curves

The way we have defined it so far it's insecure against MiTM
Public key encryption

Intro. to Number theory
Z_N = {1,2...N-1} a ring where addition and multiplication mod N can be done.
x.(y+z) = x.y + x.z
For all ints x,y there exist ints a,b s.t. a.x + b.y = gcd(x,y) and a,b can be found efficiently using the extended Euclid alg. For e.g. 2.12 - 1.18 = 6 = gcd(12,18)

If gcd(x,y)=1 we say that x and y are relatively prime.

Modular inversion
Over the rationals, inverse of 2 is 1/2. 
Def: The inverse of x in Z_N is an element y in Z_N s.t. x.y = 1 in Z_N

Lemma: x in Z_N has an inverse iff gcd(x,N) = 1 so Z_N* = set of invertible elements in Z_N = all x s.t. gcd(x,N) = 1

Solving modular linear equations
Solve a.x + b= 0 in Z_N
=> a.x = -b
=> x = -b.a^-1
Find a^-1 in Z_N using extended Euclid. Run time: O(log^2 N)

Fermat's theorem
Let p be a prime. For all x in (Z_p)*: x^(p-1) = 1 in Z_p
Example p=5. 3^4 = 81 = 1 in Z_5

This gives us another way to compute inverses, but less efficient than Euclid
x e (Z_p)* => x.x^(p-2) = 1 => x^(-1) =x x^(p-2) in Z_p

but it doesn't work for non primes.
Run time O(log^3 N)
So, less general and less efficient.

Application of Fermat's theorem - Generating random primes
Let's say we want to generate a large random prime
say, prime p of length 1024 bits (i.e. p ~ 2^1024)

Step 1: choose a random integer p e [2^1024, 2^1025 -1]
Step 2: test if 2^(p-1) = 1 in Z_p
If so, output p and stop. Else goto Step 1.

For 1024 bits prime Pr[p not prime] < 2^-60

We can also get False primes through this method.

Structure of (Z_p)*
It's a cyclic group, there exists g e (Z_p)* {1,g,g^2,...g^p-2} = (Z_p)*

g is called a generator of (Z_p)*
Not every element is a generator.

Lagrange theorem: ord_p(g) always divides p-1
ord_p(g) = |<g>| = generated group of g

Euler's generalization of Fermat
phi(N) = |(Z_N)*|
phi(12) = |{1,5,7,11}| = 4
Phi(p) = p - 1 where p is prime.

If N = p.q where p,q are prime then phi(N) = N-p-q+1  = (p-1)(q-1)

Euler's theorem - For all x in (Z_N)* x^phi(N) = 1 in Z_N - basis of RSA

Example : 5^phi(12) = 5^4 = 625 = 1 in Z_12

Practice questions:
2^10001 % 11 = 1 (Fermat), since gcd(2,11) = 1 and 11 is prime => 2^(11-1) = 2^10 % 11 = 1 => 2^10001 % 11 = 2^1 % 11 = 2
2^245 % 35 = 1 (Euler's generalization) since gcd(35,2) =1 and 35 is not prime, N = 35 = 7.5, so |phi(N)| = 7-1.5-1 = 24 => 2^24 % 35 = 1 => 2^245 % 35 = 2^5 = 32


Modular e'th root
When does the root exist?

e=2, square roots
x, -x => x^2
If p is an odd prime then gcd(2, p-1) !- 1
In Z_11 * , (1)^2 = 1 (-1)^2 = 1 where -1 = 10 (since mod 11)
similarly 2 and 9 map to 4, 3,8 map to 9 and so on.

x in Z_p is a quadratic residue if it has a square root in Z_p.
p odd prime => the number of Q.R. (Quadratic Residue) in Z_p is (p-1)/2 + 1 , extra 1 is for 0.

Euler's theorem about when does a number have a Q.R.
This theorem is not constructive, i.e. it tells us about existence but not how to construct it.

Arithmetic algorithms
Addition,subraction - linear in n (input size)
Division O(n^2)
Multiplication is naively O(n^2) if inputs are n-bits. Karatsuba's algorithm O(n^1.585)
Best(asymptotic) algo: On(n.logn).but is practical on very large numbers.
But Karatsuba's more practical and most crypto libraries use it.

Modular exponentiation is O(n^3).

Some hard problems
District log base 2 mod p for (1) (Z_p)* for large p, (2) Elliptic curve groups mod p
An application: collision resistance
If H(x,y) = g^x.h^y where g,h are generators of G where G = (Z_p)* for large p the finding collisions of H is as difficult as DLog problem.

Now look at some difficult problems modulo composites(above is modulo prime)






Blog Archive