Commutativity

Homomorphism (kind of)

Used in chosen-ciphertext attack $$E(xy) = E(x)E(y)$$ allows for blind signatures.

What if there is some creature who loves to give signatures? You can make it sign whatever you want!

Here is how: you obviously know $(d, n)$ that is public. You create the following $$x z^d$$ where $z^d$ is a blinding factor. And after the signature is finished $$x^e z$$ and because $z$ was chosen so that it has a multiplicative inverse$\mod n$ it is easy.

Small e

Known $\varphi(n)$

We get the following system which we can solve $$n = pq$$ $$\varphi(n) = (p-1)(q-1)$$

Wiener

when $$d < \frac{1}{3}n^{1/4}$$ it is possible to calculate it from $e$ with the continued fraction method.

How it works? This is interesting but not that simple. But the idea is quite easy. If attacker got $\varphi(n), e$ we lost. Attacker knows $$\frac{e}{N}$$ and with this he can approximate $$\frac{e}{\varphi(n)}$$ so that when $d$ is small enough he can recover it.

Randomized algorithms for calculating $\varphi(n)$

Meet in the middle

Similar messages

Given $c = m^e, c' = (m+\delta)^e$ and not that large $e$ we can recover $m$. Note that $m$ is a root of the following polynomials. $$p(x) = m^e - c, q(x) = (m+\delta)^e - c'$$

There is a good chance that $$gcd(p,q)$$ is linear. If that is the case we won.

Partially known messages

All we need to know is to guess unknown bits. Untrivial.

Similar $p, q$

Let $$q = p + 2d$$ then $$n = p^2 + 2pd$$

This is similar to $$(p+d)^2 = p^2 + 2pd + d^2$$ $d$ is guessable.

Chosen-ciphertext attack

Suppose the attacker wants to know the message $$m^e$$ but can’t decrypt it. Sometimes the victim will decrypt messages which look unsuspicious. The attacker can then ask the victim to decrypt $$m^{e}r^e$$ if she chose $r \in \mathbb{Z}^*_n$ she can then recover $m$ like $$m = m r r^{-1}$$

Chosen-plaintext attack

RSA without padding is not semantically secure. It is attackable by the chosen-plaintext attack, but this is impractical.

The same message but different moduly

We can use CRT. For $e = 3$ for example $$x^3 =a_1 \mod{n_1}$$ $$x^3 =a_2 \mod{n_2}$$ $$x^3 =a_3 \mod{n_3}$$ This is solvable and we can obtain $$x^3 \in \mathbb{Z_n}$$ finding the root is then easy.

Miscalculation

When using CRT it is possible to leak one of the primes if encrypting the same message multiple times. WTLOG when there is a mistake in calculating $\text{remainder} \mod p$, it gives out the multiple of $q$ from the following $$gcd(\text{result} - x^e \mod{n}, n)$$

Jacobi symbol leak

Jacoby symbol is defined with Legendre symbol for $a$ integer and $n$ odd integer: $$\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{e_1} \cdot ... \cdot \left(\frac{a}{p_k}\right)^{e_k}$$ where the primes are from the factorization of $n$.

It has some interesting properties similar to the Legendre symbol. For example $$\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right) \left(\frac{b}{n}\right)$$ Some other properties $$\left(\frac{a}{nm}\right) = \left(\frac{a}{n}\right) \left(\frac{a}{m}\right)$$ And when $a$ is a quadratic residue the Jacobi symbol is also $1$. But not necessarily the other way around. This holds because when $a$ is a quadratic residue in $n$ it must also be QR in all it’s prime factors.

Parity and half

if we knew how to compute parity or half function from encrypted message (had oracle for it) we would be able to decrypt.

Half and parity are equivalent because.