1 08-AsymmetricEncryption

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

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?
Does any pattern always hold?

1.1 Reading

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

Very good tutorial on RSA; read it!

Very good tutorial on RSA; read it!

1.2 Screencasts

1.3 Modern cryptography

1.3.1 Types of Encryption Schemes

Classification of Encryption Schemes
* Symmetric vs. Asymmetric
* Computationally secure vs. Information theoretically secure Symmetric vs. Asymmetric

A significant distinction. Symmetric Key Encryption

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:
Faster than asymmetric. Asymmetric Key Encryption

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 Computational vs. Information Theoretic Computationally Secure

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. Information Theoretically 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.

1.4 Asymmetric key encryption

1.4.1 Asymmetric-Key Encryption Structure

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.

1.4.2 Asymmetric key terminology

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.

1.4.3 Requirements for asymmetric-Key Cryptosystems

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)

1.4.4 Requirements for asymmetric-Key Cryptosystems (more formal)

Computationally easy for a party B to generate a pair,
(public key PUb, ­private key PRb).

Computationally easy for a sender A,
knowing the public key and the ­message to be encrypted, M,
to generate the corresponding ciphertext:
C = E(PUb , M)

Computationally easy for the receiver B to decrypt the resulting ciphertext,
using the private key to recover the original message:
M = D(PRb ,C) = D[PRb, E(PUb, M)]

Computationally infeasible for an opponent,
knowing the public key, PUb,
to determine the private key, PRb

Computationally infeasible for an opponent,
knowing the public key, PUb, 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[PUb, E(PRb, M)] = D[PRb, E(PUb, M)]
This is a neat feature, that you will see exists in RSA!

1.4.5 Applications

Meet Alice and Bob (and sometimes evil Eve)!
http://cryptocouple.com/ Encryption (top image below)

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:
08-AsymmetricEncryption/f6-crop-b.png Digital signatures (bottom image above)

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. Applications for various public-Key cryptosystems


1.4.6 Asymmetric Encryption Algorithms

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.

1.5 Textbook RSA

Read Chapter 9 and all Appendices:


Video series detailing the algorithm:

1.5.1 RSA Public-Key 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. Example of RSA

For a moment, let’s see the magic:


1.5.2 RSA Algorithm

Key generation involves multiple steps of repeated generate and test.

1.5.3 Key Generation

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:

Ciphertext space:

Public key:
n, e, where,
e is an integer relatively prime to \(\phi(n)\)

Private key:
d where
\(ed \equiv 1 \mod \phi(n)\)

1.5.4 Encryption and Decryption Operations

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

Encryption: E(x, n, e) = xe mod n

Decryption: D(c, n, d) = cd mod n
= xed mod n
= x1

The above formulation is an over-simplification of the real proof,
but illustrates a key theoretical point. Example

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 = 103 mod 187 = 65

To decrypt C,
compute: D(c, e):
65107 mod 187 = 10

1.5.5 Components

Some are public.
Some are secret. Public

n - the modulus
e - the public exponent
c - the cipher text Secret

p - the prime factor of n
q - the other prime factor of n
\(\phi(n)\) - Euler’s totient of n
d - the private exponent


1.5.6 Security Guarantee of RSA

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. Breaking RSA

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? Factorization of large integers

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


Progress in Factorization:
What is a modern size?
How much bigger and better is it?



1.5.7 Code

Read on your own:

Trace the important parts briefly in class:

What line does the encryption?

$ python3
>>> help(pow)
pow(x, y, z=None)
Equivalent to xy (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!

1.5.8 Textbook RSA

To make textbook RSA actually secure,
padding on the encoded plaintext must be used:

1.5.9 Key compromise?

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.

1.6 Diffie-Hellman


1.6.1 Background: “Primitive root”


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 3k 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.

1.6.2 Diffie-Hellman and Key Exchange

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.

We previewed this “baby Diffie-Hellman idea before,
using nothing but exponents and log:

1.6.3 Algorithm

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 XA = 97
Bob randomly selects XB = 233

Alice and Bob each compute their public keys:
Alice computes YA = 397 mod 353 = 40
Bob computes YB = 3233 mod 353 = 248

Then exchange the public keys and compute secret key:

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

\(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
08-AsymmetricEncryption/f8-crop.png What is secret?

red = secret
blue = public

1.6.4 Man-in-the-Middle Attack (MITM)

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

Example of evil Eve in the middle:
1. Alice transmits YA to Bob.
2. Eve generates private keys XD1 and XD2, and their public keys YD1 and YD2
3. Eve intercepts YA and transmits YD1 to Bob.
4. Eve also calculates \(K2 = (Y_A)^{X_{D2}}\)
5. Bob receives YD1 and calculates \(K1 = (Y_{D1})^{X_B}\)
6. Bob transmits YB to Alice
7. Eve intercepts YB and transmits YD2 to Alice
8. Eve calculates \(K1 = (Y_B)^{X_{D1}}\)
9. Alice receives YD2 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?


When setting up your web server:
Use DH-* with TLS for this nice feature:
More to come later.

1.7 Other Public-Key Algorithms

1.7.1 Digital Signature Standard (DSS)

1.7.2 Elliptic-Curve Cryptography (ECC)

1.8 Cracking prime-based cryptography

Using something like super-Turing solutions:

1.8.1 Shor’s algorithm

Which algorithms would primarily be directly vulnerable,
symmetric or asymmetric?
Even if both are not, does it matter?
If you are interested:

1.8.2 Memristive solution


Next: 09-ModernSymmetric.html