Public Key Encryption
We now define a formally what is a public key encryption
Formal definition of Public Key Encryption
We define a 3-tuple formed as follows: $(G, E, D)$ where
- $G$ is the generator for the private and public keys, from now on identified as $(pk, sk)$ (public key and secret key)
- $E(pk, m)$ the encryption algorithm, that takes the $pk$ and the message in input
- $D(sk, c)$ the decryption algorithm, that takes the $sk$ and the ciphertext in input.
Now is this definition useful? i don’t think so! We can’t create theorems for it, too general I suppose. Is it clear? yes! I think this is the usefulness of maths in many occasions, it delivers some complex information in a concise and understandable manner.
Some observations about Public Key Encryption
Semantic security to Eavesdropping
This is the same as explained in Advantage security explained in a previous section.
We defined the advantage as the ability of the attacker to distinguish the original message. This is still exactly the same, see that section. (the only difference is that here we use public key encryption)
Resistance against Many Time Pads
We know that in the symmetric context in Block Ciphers and OTP and Stream Ciphers, it is often not secure to use the symmetric key to many times. (This is clearly true when we are talking about the OTP cipher).
But in the context of Asymmetric keys this notion is not true as the key is public, this key can be used as many times as the attacker wants. So he can reuse the key, while the cipher should still remain secure!
Sharing a key
It’s easy to share a key using this encryption scheme. Just send the secret key with the public key of this cipher!
Trapdoor functions
Definition of Trapdoor functions
Trapdoor is generic function from $X \to Y$. This is a triple $G, F, F^{-1}$ very similar to the previous one (indeed it’s kinda the same definition) The only difference is that $F^{-1}$ is the inverse. This function is one-way, meaning it’s difficult to invert. And has a trapdoor meaning that by knowing the secret $sk$ it is easy to do so. $F(pk, \cdot)$ defines public encryption function, the other equivalent is the decryption.
Secure Trapdoor Functions🟩–
NOTE: direct use of $F$ and $F^{-1}$ to encrypt and decrypt using the created keys is not semantically secure. But I don’t know why.
A trapdoor is secure if it’s difficult to invert without the knowledge of $sk$. (It’s difficult to invert the $x$)
See image
Creating a PKE from Trapdoors🟨+
One Way Hash Algorithms
These are different from Hash tables which is a datastructure!
We can see that One-Way hashes are a trapdors with $pk = sk$. Usually it is a function that takes a input of arbitrary length and outputs a limited string with some important properties.
Properties of One Way Hash Algorithms🟩-
- Easy to Evaluate: The hashing algorithm should be fast
- Hard to Reverse: There is no feasible algorithm to “reverse” a hash value, That is, given any hash value $h$, it is computationally infeasible to find any document $m$ such that $H(m) = h$.
- Hard to find Collisions: There is no feasible algorithm to find two or more input documents which are hashed into the same condensed output, That is, it is computationally infeasible to find any two documents $m_{2}, m_{2}$ such that $H(m_{1})= H(m_{2})$. Although, theoretical requirements say there are many many collisions. But the difficult thing is tampering, that is add some strings, make some modifications of the original messages such that that hash matches with others.
- A small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value
RSA Cryptosystem
Definition of the trapdoor function
We define $F: \mathbb{Z}^{*}_{\mathbb{N}} \to \mathbb{Z}^{*}_{\mathbb{N}}$ as $RSA(x) = x^{e}$ where $e$ is the public key generated by the key generation function and $N = pq$ is the private key, where $p, q$ are big primes.
Then using Euler’s theorem we know how to compute $d$ such that $x^{ed} =x \mod N$ where $d$ is the inverse modulo that, this is how we decrypt. How do we compute $d$? We use euler’s theorem, and find this $e\cdot d = 1 \mod \varphi(N)$. and $e$ should be invertible with it is coprime with $N$ (true by construction).
RSA with trapdoors
A secure implementation of RSA uses trapdoor functions like this: $x \sim X$ this is the secret, we generate $y = RSA(x, e)$ with this, and encrypt the message with $k = H(x)$ and $c = H_{s}(k, m)$ and send $y$. The decryption step is similar to that presented to trapdoor functions.
Security Analysis of RSA
NOTE: normal RSA as defined above is not secure, the main reason is that it is deterministic, so we can have semantic security breaches.
Simple semantic security attack on RSA
I can get back to the original message with a small effort. The percentage of success is high enough not to be negligible. We have a $2^{40}$ attach on $2^{64}$ long messages.
#### Advantage notation for RSA
We want the possibility to compute the $e$ root modulo $N$ to be small, and using the notion of advantage developed in [OTP and Stream Ciphers#Security with advantage](/notes/otp-and-stream-ciphers#security-with-advantage) we write
$$
Pr\left[ A(N, e, y) = y ^{1/e} \right] < \varepsilon
$$
Where $\varepsilon$ is very small, **negligible** so to say, and $A$ is the $F$ trapdoor function used for RSA.
This is the problem of the discrete logarithm, usually true.
Wiener’s attack (non fatto)
This section is not useful for the exam, just for personal knowledge!
If the private keys have certain properties, there exists some attacks, one example is the Wiener’s attack, for example if the private key is too small.
The concept is that this makes the search space quite small.
Low public exponent attack 🟩
Usually minimum that is used is 3. If 2 then the inverse is not guaranteed because $mcd(2, (p - 1) ( q - 1)) \neq 1$ .
This is a stupid attack. Then the exponent is small enough, and it is not able to wrap the module, then the root is quite easy to achieve. This is why the recommended value is big, usually = $2^{16} + 1 = 65537$.
Usually this is used to speed up encryption, it easier to compute. Other variants, like Elgamal have almost same time to encrypt and decrypt.
The reduction problem
In order to prove that the best solution is to factor n we should prove that Efficient algorithm for e’th roots mod $N$ implies having efficient algorithm for factoring $N$. There is some evidence that says this reduction exists (BV'98) but it is still an open problem. But as far as we know this is actually a hard problem.
Comparison with symmetric keys
| AES key size | RSA modulus size |
|---|---|
| 80 bit | 1024 bits |
| 128 bits | 3072 bits |
| 256 bits | 15360 bits |
| We observe that RSA needs a lot more bits to ensure the same security! |
Side channel attacks
these attacks do not directly attack the cipher, but the infrastructure or computing that it uses.
Timing attack
Can leak $d$ secret key by tracking the compute time. (Kocher 1997)
Power attack
Can leak $d$ by tracking power usage. (Kocher 1999) Needs access to physical data.
Faults attack
Errors can leak $d$ somehow (don’t know!) (BDL 1997).
In questa fase viene leakato il valore di $p$ che permette di ricostruire la chiave privata.
Key generation
First when you startup the entropy of $p$ is not so much, so it happens if two different firewalls generate a key, they are probably the same. So if you take the GCD of these, it is probable that they are the same.
They factored 0.4% of all public https keys in this way. Which is a good number.
This says that it is **crucial to add randomness before generating keys**.
Variations
Elgamal🟨-
Find $g$ and $p$ such that $g$ is primitive root modulo $p$. Some strange properties here. This means that $\forall a, \exists k : g^{k} = a \mod p$. This is inspired from the Key Exchange protocols#Diffie-Hellman Protocol. Then the first person chooses $a \in \left[ 0, p - 2 \right]$ randomly and calculates $A = g^{a} \mod p$ and the tuple $(p , g, A)$ is then considered as the public key. The interesting thing is that this algo is randomized, if you want to communicate with someone, you choose a key randomly first.
- $B = g^{b} \mod p$
- $c = A^{b}m \mod p$
- Ciphertext is $(B, c)$
La decrittazione è diversa. Calcolo $x = p - 1 - a$ e poi posso usare questo per decrittare, facendo $m = B^{x}c \mod p$
Esiste anche una versione per fare l’exchange, ma di questa non ne abbiamo parlato
Notes on security -> Discrete log problem. Efficiency -> No, ciphertext needs that public key to be sent, which is usually long and expensive to calculate compared to AES.
Rabin cripto-system🟨
we create $p,q$ such that their modulus $4$ is 3, probably for some nice properties I don’t know of… The advantage is that his security is proved. Calculate $n = pq$ and this is the public key. When somebody wants to communicate, he just calculates
$$ c = m^{2} \mod n $$
And sends this, probably with this setting the properties of $p, q$ make that invertible, but not sure why.
If you are curious try to understand why is this valid.
It has some nice theoretical properties.
Its difficulty is proven to be the same as integer factorization, not known for RSA.
Digital signatures
The main idea is to cipher with the private key, so that it can be verifiable using the public. It was cited in Sicurezza delle reti times before. To overcome the burden to encrypt the whole text, usually only an hash is encrypted.
Advantages of Digital signatures
- Unforgeable
- Un-deniable by the signatory (if you have signed it, it was you!)
- Universally verifiable (everybody can verify it)
- Every doc’s signature is different, or very sensible to little changes.