Cryptography (Not Encryption)
Key Exchange
We can use public key encryption to share a secret, such as a symmetric key.
We can also use a pre-agreed key if we have a previous secure connection.
Diffie-Hellman (DH) Key Exchange
This is based on the assumption that logarithm modulo $n$ is not feasible to compute (like RSA).
The protocol to share a secret between Alice and Bob:
- Alice and Bob publicly agree no a large prime number $p$ and a number $x$ such that $\text{ord}(x)=p-1)$ in $(\mathbb Z/p\mathbb Z)^*$.
- Alice privately generates a secret number $a$ and computes $x^a\mod p$.
- Bob privately generates a secret number $b$ and computes $x^b\mod p$.
- Alice publicly sends $x^a$ to Bob and Bob publicly sends $x^b$ to Alice.
- Alice computes $s=(x^b)^a\mod p$.
- Bob computes $s=(x^a)^b\mod p$.
$s$ is now known to Alice and bob because $(x^a)^b=(x^b)^a$.
Hashing
Hashing is a non-reversable function to make a key from a binary blob. Usual conditions on a hashing function $h:X\rightarrow Y$:
- Efficiency
- Given $x$, it is feasible to compute $h(x)$.
- Secrecy
- Given $y=h(x)$, it is not feasible to compute any $z$ such $h(z)=y$.
- Collision
- It is not feasible to find any $x_1\neq x_2$ such that $h(x_1)=h(x_2)$.
We don’t require correctness as we don’t want to recover $x$.
Non-cryptographic hashes don’t require secrecy or collision.
Hashing Size
For a hash function, there is no requirement that the output is at least as long as the input:
- This way a very large $x$ can be turned into a pretty short hash.
Hashing Uses
Hashing is mainly used for:
- Message integrity checks.
- Password hashing.
Password Hashing
To store passwords for comparison purposes, it is most secure to:
- Generate a salt that is unique per user and service (not necessarily secret).
- When a user sets their password compute $y=h(\text{pwd}+\text{salt})$ and store only $y$ and $\text{salt}$.
- When a user wants to login compute $y’=h(x+\text{salt})$. If $y=y’$ then the password is correct.
Salting requires that passwords can only be attacked one at a time. You can’t find what a password is from other leaked tables or by matching to other users.
Hashing must be completed server-side as the server must receive a password. If not an attacker could steal the database and it is no more secure than just storing plan-text passwords.
We can double hash to mitigate this and never have the plan-text password in flight.
Precedence
You can use hashes to show presidency. You could say:
I know what the outcome of tomorrows football match. I won’t spoil it but this is the hash of my prediction.
You can also accomplish this with signing.
Cryptocurrency
With a hash function, it is hard to find $x$ such that $h(x)=y$.
Finding an approximation that:
\[h(x)\approx 0\]is used as proof of work. This is also a difficult task to do.
Signing
We have the public key comprised of $e$ and the modulus $n$ and the private key $k$:
- To sign a message $x$ compute $s=x^k\mod n$
- Then post $x$ together with $s$.
- To verify the signature compute $s^e\mod n$. We now have $(x^k)^e=x\mod n$.
To sign faster we can compute a hash of the message. We can then sign this hash.
Authentication
By verifying the signature you can verify that the person who signed the message was in ownership of that private key.
You can also say that no-one has tampered with the document provided that they’re not in ownership of the private key.
Identity
You can prove your identity by signing a random message:
- You mustn’t sign a meaningful document if you only want to prove your identity.
We take the following method:
- Alice privately knows the private key $k$ and posts the public key $e,n$.
- Alice randomly generates a number $a$ and publicly sends it to bob.
- Bob randomly generates a number $b$ and publicly sends it to Bob.
- Alice computes $s=h(h(a)+h(b))^k\mod n$ and publicly sends it to Bob.
- Bob verifies that $s^e=h(h(a)+h(b))\mod n$.
Operating on Cipher-Text
Some operations are possible on the cipher-text without knowing the plain-text:
-
RSA allows multiplication modulo $n$:
Given cipher-text of $x,y$ we can compute $x\times y$ without knowing $x,y,k$.
This is why we need to hash the hashes of $a$ and $b$ for identity.