HackingCrypto

RSA Systems

Math

1. RSA Cryptosystem

Key Generation
1) Choose two distinct prime numbers $p$ and $q$, $\quad N = p \cdot q$
2) Choose $e$ s.t $gcd(e, \varphi(N)) = 1$
3) $d$ : private key. s.t $ed \equiv 1 \mod \varphi(N)$

Encryption
1) $n$, $e$ : public key
2) $C \equiv M^e \mod N$

Decryption
$C^d \equiv (M^e)^d \equiv M^{ed} \equiv M^{\varphi(N)\cdot k + 1} \equiv M \mod N$

2. RSA Chosen Ciphertext Attack Scenario

Alice ————(C) ————> Eve ———-(C’)————> Bob

Eve choose $x$ s.t $gcd(x, n) = 1$
$C’ \equiv C\cdot x^e \mod N$

Bob’s decryption. (Bob does not know the meaning of the decrypted message)
$(C’)^d \equiv (C \cdot x^e)^d \equiv C^d \cdot x^{ed} \equiv M \cdot x \equiv M’ \mod N$

and send M’ to Eve.

Eve can decrypt M’
$(M’)\cdot x^{-1} \equiv M \mod N$

Set $e=3$ and let $ \left\langle N,e\right\rangle $ be an RSA public key.
Let $M_{1}\neq M_{2}\in {\mathbb {Z}}_{n}^{*}$ s.t $M_1 \equiv f(M_2) \mod n$
for $f(x) = ax + b \in {\mathbb {Z}}_{n}[x]$ with $b \ne 0$

Then, given $\left\langle n, e, C_1, C_2, f \right\rangle $, Eve can recover $M_1, M_2$ in time quadratic in $log_2n$

Let $g_1(x) \equiv x^3 - C_2 \mod n$ and $g_2(x) \equiv (ax + b)^3 - C_1 \mod n$
$\Rightarrow (x - M_2) \mid g_1(x)$ and $(x - M_2) \mid g_2(x)$

we can calculate $gcd(g_1(x), g_2(x))$
so, we can get $M_2$.

4. RSA Digital Signature

RSA Digital Signature
$\left\langle n, e \right\rangle$ : public key
$d$ : private key

Signing
$S \equiv M^d \mod n$

Verifying
Check $S^e \mod n$ and $M$ are equal.

5. RSA Signature - Known message attack

Alice ———($M_1, S_1$)———> Bob
Alice ———($M_2, S_2$)———> Bob

Eve : $S_1S_2 \equiv (M_1M_2)^d \mod n$
($S_1S_2$ : signature of $M_1M_2$)

6. RSA Signature - Chosen message attack

Eve : choose $M_1$ and $M_2$ s.t $M = M_1M_2$
Eve can ask Alice to sign $M_1$ and $M_2$

Eve : $S_1S_2 \equiv (M_1M_2)^d \mod n$
($S_1S_2$ : signature of $M_1M_2$)

Share