Previous: 07-CryptoMath.html

“**The mantra of any good security engineer is:**

**Security is a not a product, but a process.**

**It’s more than designing strong cryptography into a
system;**

**it’s designing the entire system such that all security
measures,**

**including cryptography, work together.”**

- Bruce Schneier

https://en.wikipedia.org/wiki/Bruce_Schneier

https://www.schneier.com/

**Discussion question:**

Which parts of a computer system matter the most?

A system have high and low level parts.

Do the high or low level parts matter more?

Why?

Does any pattern always hold?

http://inventwithpython.com/cracking/ Chapter 24

Very good tutorial on RSA; read it!

http://doctrina.org/How-RSA-Works-With-Examples.html

Very good tutorial on RSA; read it!

http://doctrina.org/Why-RSA-Works-Three-Fundamental-Questions-Answered.html

- Password for the Vimeo videos is in Zulip chat.
- SP21: https://vimeo.com/513099345
- FS20: https://vimeo.com/460684770
- Tip: If anyone wants to speed up the lecture videos a little,
inspect the page, go to the browser console, and paste this in:
`document.querySelector('video').playbackRate = 1.2`

**Classification of Encryption Schemes**

* Symmetric vs. Asymmetric

* Computationally secure vs. Information theoretically secure

A significant distinction.

Also referred to as **private key encryption.**

There is one private or secret key, which is generally shared between
two parties.

Both encryption and decryption use the same key, and a similar
process.

Key agreement and exchange can be a very challenging problem.

Relies on making a big mess of the data, using the pre-exchanged key,
reversibly.

Generally computationally efficient to encrypt and decrypt (fast).

Examples of “modern” symmetric algorithms:

AES, DES, 3DES

Faster than asymmetric.

It is also referred as **public key encryption.**

It has two keys: one public and one private.

The encryption operation uses only the public key,

which is known to everyone.

The decryption operation uses only the private key,

which is known to one person.

Modern innovation (newer algorithms).

Relies on math tricks (one way functions).

Moderately computationally expensive,

both in key-generation and in encryption and decryption.

Examples of “modern” asymmetric algorithms: RSA, DSA, ElGamal,
NTRU.

Slower than asymmetric.

**+++++++++++++++++++++**

**Cahoot-08.1**

A computationally secure encryption scheme,

assumes the adversary has **limited** computing
power.

The adversary can be assumed to solve polynomially-bounded
problems,

but not to solve computationally infeasible NP-Complete, NP-hard, etc.
problems

Almost all practical encryption schemes,

e.g., AES and RSA, are computationally secure.

An information-theoretically secure encryption scheme,

assumes the adversary has **unlimited** computing
power.

The adversary can be assumed to solve any computational problems

NP-Complete and NP-hard could hypothetically be efficiently
solved,

and the scheme would still offer perfect security

Unconditional or perfect security.

One-time pad is information theoretically secure.

There are variants of the OTP,

but it’s the only one that fits this criteria.

Proposed by Diffie and Hellman in 1976 (quite recently!)

Based on mathematical one-way functions.

Q: What do we mean by one-way?

A: Those operations where the best algorithm to reverse them is a form
of brute force.

Asymmetric schemes use two separate keys:

**public key**

**private key**

Public key is made public for others to use.

**Plaintext**: Readable message or data that is fed into
the algorithm as input

**Encryption algorithm**: Performs transformations on the
plaintext

**Public and private key**: Pair of keys, one for
encryption, one for decryption

**Ciphertext**: Scrambled message produced as output

**Decryption key**: Produces the original plaintext.

Q: Why seemingly redundant definition?

A: either can decrypt or encrypt

**Decryption algorithm**: Accepts the ciphertext and the
matching key, and produces the original plaintext.

Should be:

* Computationally easy to create key pairs

* Computationally easy for sender, knowing public key, to encrypt
messages

* Computationally easy for receiver, knowing private key, to decrypt
ciphertext

* Computationally infeasible for opponent to determine private key from
public key

* Computationally infeasible for opponent to otherwise recover original
message

* Useful (but not required) if either key can be used for each
role

* Either key used for encryption with the other used for decryption
(optional)

Computationally easy for a party B to generate a pair,

(public key PU_{b}, private key PR_{b}).

Computationally easy for a sender A,

knowing the public key and the message to be encrypted, M,

to generate the corresponding ciphertext:

C = E(PU_{b} , M)

Computationally easy for the receiver B to decrypt the resulting
ciphertext,

using the private key to recover the original message:

M = D(PR_{b} ,C) = D[PR_{b}, E(PU_{b}, M)]

Computationally infeasible for an opponent,

knowing the public key, PU_{b},

to determine the private key, PR_{b}

Computationally infeasible for an opponent,

knowing the public key, PU_{b}, and a ciphertext, C,

to recover the original message, M.

Optionally, either of the two related keys can be used for
encryption,

with the other used for decryption.

M = D[PU_{b}, E(PR_{b}, M)] = D[PR_{b},
E(PU_{b}, M)]

This is a neat feature, that you will see exists in RSA!

Meet Alice and Bob (and sometimes evil Eve)!

https://en.wikipedia.org/wiki/Alice_and_Bob

http://cryptocouple.com/

Each user generates pair of related keys, public and private.

**ob** encrypts a message using **Alice**’s
public key.

Alice decrypts messages using her private key;

no other recipient can decrypt the message,

because only Alice knows Alice’s private key.

Go over this carefully:

Bottom half: switch key roles

User **encrypts** data using his or her own
**private** key.

Anyone who knows the corresponding **public** key will be
able to **decrypt** the message.

Used for authenticating both:

source identity, and data integrity.

Created by encrypting hash code with private key.

Does not provide confidentiality,

even in the case of complete encryption.

Message is safe from alteration, but not eavesdropping.

Encryption is provided independently.

**RSA (Rivest, Shamir, Adleman)**

Developed in 1977.

This is the most widely accepted and implemented approach to public-key
encryption.

Block cipher in which the plaintext and ciphertext are integers between
0 and n-1 for some n.

**Diffie-Hellman key exchange algorithm**

Enables two users to securely reach agreement about a shared
secret,

that can be used as a secret key for subsequent symmetric encryption of
messages.

Most widely accepted and implemented approach to key exchange.

Limited to the exchange of the keys, with no direct encryption.

**Digital Signature Standard (DSS)**

Provides only a digital signature function with SHA-1.

Cannot be used for encryption or key exchange.

**Elliptic curve cryptography (ECC)**

Security like RSA, but with much smaller keys for similar security.

Read Chapter 9 and all Appendices:

https://github.com/crypto101/crypto101.github.io/raw/master/Crypto101.pdf

https://en.wikipedia.org/wiki/RSA_(cryptosystem)

https://simple.wikipedia.org/wiki/RSA_algorithm

Video series detailing the algorithm:

https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/intro-to-rsa-encryption

Publically invented by Rivest, Shamir, and Adleman of MIT in
1977.

For a time, it was the best known, and widely used public-key
algorithm.

Uses exponentiation of integers, modulo some prime.

For a moment, let’s see the magic:

How?

Key generation involves multiple steps of repeated generate and
test.

Each key in the public key scheme is made of two numbers.

The public key will be two numbers, n and e.

The private key will be two numbers, n and d.

**The steps to create these numbers follow:**

Generate many random numbers,

until you find two that are distinct, very very large, and prime:

p and q

Multiply these two numbers,

p x q = n (n will then be the modulus for encryption).

Also, multiply these two numbers minus 1,

(p - 1) × (q - 1)

to get a number called \(\phi(n)\) (the
modulus for key generation).

Generate many more random numbers,

until you find another number, which we will call e,

which is relatively prime to n.

This is part of the public key.

Calculate the modular inverse of e, which we’ll call d.

This is part of the private key.

Side note:

In practice, e is often just chosen as 65537, or some other fixed
value…

Notice that the modulus, n, is used in both keys.

By convention, the d number must be kept secret,

as only it can decrypt messages encrypted to e,

which is pubic information.

More formally, generate

**numbers p and q**, where

where p and q are very very large primes, with roughly similar sizes,
and

n = p * q

The size of p **or** q needs to be at least 2,048
bits,

though 4096 is a practical current upper limit in most
implementations.

**Plaintext space:**

Z^{n}

**Ciphertext space:**

Z^{n}

**Public key:**

n, e, where,

e is an integer relatively prime to \(\phi(n)\)

**Private key:**

d where

\(ed \equiv 1 \mod \phi(n)\)

Each done in sequence, in either direction, will cancel the other out!

Encryption: E(x, n, e) = x^{e} mod n

Decryption: D(c, n, d) = c^{d} mod n

= x^{ed} mod n

= x^{1}

The above formulation is an over-simplification of the real
proof,

but illustrates a key theoretical point.

Iteratively, pick two primes:

p = 11

q = 17

Multiply (p - 1) × (q - 1):

n = 11 * 17 = 187

\(\phi(n)\) = 10 * 16 = 160

Iteratively with GCD Euclidean,

pick a relative prime to \(\phi(n)\):

e = 3

Using Extended Euclidean,

compute the inverse of e mod \(\phi(n)\):

d = 107

Write your hypothetical message:

Plaintext character encoded here as x = 10

Encrypt, producing ciphertext:

c = 10^{3} mod 187 = 65

To decrypt C,

compute: D(c, e):

65^{107} mod 187 = 10

Some are public.

Some are secret.

n - the modulus

e - the public exponent

c - the cipher text

p - the prime factor of n

q - the other prime factor of n

\(\phi(n)\) - Euler’s totient of
n

d - the private exponent

**+++++++++++++++++++++**

**Cahoot-08.2**

**Brute force:**

Involves trying all possible private keys.

**Mathematical attacks:**

There are several approaches,

all equivalent in effort to factoring the product of two primes.

**Timing attacks:**

These extract statistics based on on analyzing the running time of the
decryption algorithm.

**Chosen cipehrtext attacks:**

This type of attack exploits properties of the RSA algorithm,

given some oracle,

which can produce arbitrary encrypted data for the attacker.

The easiest way we know how to break RSA is to factor n back into p *
q,

which is a prime factorization…

After that, given p and q, the attacker could just repeat the analytical
process,

that the legitimate owner of the key does during key generation,

in order to compute the private exponent d.

Fortunately, we don’t have an algorithm that can factor such large
numbers in reasonable time.

Unfortunately, we also haven’t proven it doesn’t exist.

Even more unfortunately, is that there is a theoretical algorithm,
called Shor’s algorithm,

that would be able to factor such a number in reasonable time on a
quantum computer.

There is another memristive solution (non-Turing),

implemented in application-specific hardware,

that can factor primes in polynomial resources (energy).

Right now, quantum and memristive solutions are far from
practical,

but it does appear that, if someone in the future manages to build one
sufficiently large,

that RSA becomes ineffective.

Ask and discuss:

Does this just break RSA, or other algorithms too?

RSA Labs (http://www.rsasecurity.com/rsalabs/) sponsored a challenge to factor some large n:

https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

**Progress in Factorization:**

What is a modern size?

How much bigger and better is it?

https://en.wikipedia.org/wiki/Integer_factorization_records

**+++++++++++++++++++++**

**Cahoot-08.3**

Read on your own:

08-AsymmetricEncryption/cryptomath.py

08-AsymmetricEncryption/primeNum.py

Trace the important parts briefly in class:

08-AsymmetricEncryption/makePublicPrivateKeys.py

08-AsymmetricEncryption/publicKeyCipher.py

**Ask:**

What line does the encryption?

**Hint:**

`$ python3`

`>>> help(pow)`

~~~

pow(x, y, z=None)

Equivalent to x**y (with two arguments)
or x**y % z (with three arguments).

Some types, such as ints,

are able to use a more efficient algorithm,

when invoked using the three argument form.

~~~

Ask and discuss:

How do you take a string like `'Hello RSA`

’ to a power??

In order to encrypt text or data,

it must be turned into a number.

A method with blocks is used above.

How the text is turned into a number differs by implementation,

and is conceptually independent of the core RSA algorithm,

though it impacts the security!

To make textbook RSA actually secure,

padding on the encoded plaintext must be used:

https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding

If your RSA key is compromised,

what happens to past communications?

Should you keep using the key?

Forward secrecy protects the past…

This is something of a misnomer.

https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

https://en.m.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n

https://en.wikipedia.org/wiki/Discrete_logarithm_problem

https://en.m.wikipedia.org/wiki/Primitive_root_modulo_n

https://en.m.wikipedia.org/wiki/Generating_set_of_a_group

In modular arithmetic,

some number g, is a primitive root modulo n,

if every number, a, co-prime to n,

is congruent to a power of g modulo n.

That is, g is a primitive root modulo n,

if for every integer, a, co-prime to n,

there is an integer, k,

such that \(g^k \equiv a \mod n\).

For example, g = 3, mod 7:

Here we see that the period of 3^{k} modulo 7 is 6.

The remainders in the period,

which are 3, 2, 6, 4, 5, 1,

form a rearrangement of all nonzero remainders modulo 7,

implying that g = 3 is indeed a primitive root modulo 7.

It was the first published public-key algorithm,

by Diffie and Hellman in 1976.

They first explained public key concepts.

It is used in a number of applications.

It is a practical method to exchange a secret key securely,

that can then be used for subsequent encryption of messages.

Security relies on difficulty of computing discrete logarithms.

**Mention:**

We previewed this “baby Diffie-Hellman idea before,

using nothing but exponents and log:

07-CryptoMath.html

Two people, Alice (A) annd Bob (B).

**Example Public Parameters:**

Prime number: q = 353

Primitive root of q: \(\alpha = 3\)

**Example Private Parameters:**

Alice randomly selects X_{A} = 97

Bob randomly selects X_{B} = 233

**Alice and Bob each compute their public keys:**

Alice computes Y_{A} = 3^{97} mod 353 = 40

Bob computes Y_{B} = 3^{233} mod 353 = 248

**Then exchange the public keys and compute secret
key:**

Alice:

\(K = (Y_B)^{X_A} \mod 353 = 248^{97} \mod 353
= 160\)

Bob:

\(K = (Y_A)^{X_B} \mod 353 = 40^{233} \mod 353
= 160\)

160 is the shared secret they both possess.

Diffie-Hellman Key Exchange, Generation and Computation

Diffie-Hellman Key Exchange

red = secret

blue = public

(against DH, RSA, or any other of these algorithms)

https://en.wikipedia.org/wiki/Man-in-the-middle_attack

Example of evil Eve in the middle:

1. Alice transmits Y_{A} to Bob.

2. Eve generates private keys X_{D1} and X_{D2}, and
their public keys Y_{D1} and Y_{D2}

3. Eve intercepts Y_{A} and transmits Y_{D1} to
Bob.

4. Eve also calculates \(K2 =
(Y_A)^{X_{D2}}\)

5. Bob receives Y_{D1} and calculates \(K1 = (Y_{D1})^{X_B}\)

6. Bob transmits Y_{B} to Alice

7. Eve intercepts Y_{B} and transmits Y_{D2} to
Alice

8. Eve calculates \(K1 =
(Y_B)^{X_{D1}}\)

9. Alice receives Y_{D2} and calculates \(K2 = (Y_{D2})^{X_A}\)

If Alice and Bob were using these DH secrets as single-session
private keys,

which communications are compromised, past, present, or future?

**+++++++++++++++++++++**

**Cahoot-08.4**

When setting up your web server:

Use DH-* with TLS for this nice feature:

https://en.wikipedia.org/wiki/Transport_Layer_Security#Key_exchange_or_key_agreement

More to come later.

- FIPS PUB 186
- Makes use of SHA-1 and the Digital Signature Algorithm (DSA)
- Originally proposed in 1991, revised in 1993 due to security concerns, and another minor revision in 1996
- Cannot be used for encryption or key exchange
- Uses an algorithm that is designed to provide only the digital signature function

- Equal security for smaller bit size than RSA
- Seen in standards such as IEEE P1363
- Confidence level in ECC is not yet as high as that in RSA
- Based on a mathematical construct known as the elliptic curve

Using something like super-Turing solutions:

Which algorithms would primarily be directly vulnerable,

symmetric or asymmetric?

Even if both are not, does it matter?

If you are interested:

https://www.youtube.com/watch?v=lvTqbM5Dq4Q

https://aip.scitation.org/doi/abs/10.1063/1.4975761

https://arxiv.org/pdf/1512.05064.pdf

Next: 09-ModernSymmetric.html