Private Key-d related Attack

d Leak Attack

Teori

$ed\equiv 1mod\phi (n)$

$\phi (n)|k=ed-1$

jelas $k$ adalah genap

dapat dibuat $k=2^{t}r$,

$r$ ganjil

$t>=1$.

jadi untuk semua $g$ yang relatif ke N, adalah

$g^k\equiv 1modn$

maka $z=g^{\frac{k}{2}}$ adalah akar kuadrat modulo $N$,

kemudian ada

$$\begin{array}{rl}{z}^2& \equiv 1modp\\ z^2& \equiv 1modq\end{array}$$

persamaan diatas memiliki 4 solusi, 2 diantaranya :

Attention

kesalahan penulisan sumber

$$\begin{array}{r}x\equiv \pm 1Nway\\ x\equiv \pm 1\text{n}way\end{array}$$

lalu 2 yang lainnya ±x, yang mana $x$ memenuhi kondisi berikut :

Attention

kesalahan penulisan sumber

$$\begin{array}{rl}x& \equiv 1pway\\ x& \equiv -1qway\end{array}$$

jelas, $z=g^{\frac{k}{2}}$ memenuhi kondisi terakhir, dan kita dapat menghitung $gcd(z-1,N)$ untuk menguraikan $N$

Tools

• rsatool.py

Weiner's Attack

Prasyarat

ketika d kecil $(d<\frac{1}{3}{N}^{\frac{1}{4}})$

Teori

• https://en.wikipedia.org/wiki/Wiener%27s_attack
• https://sagi.io/2016/04/crypto-classics-wieners-rsa-attack/

Tools

• https://github.com/pablocelayes/rsa-wiener-attack

Sumber

---

1. https://ctf-wiki.mahaloz.re/crypto/asymmetric/rsa/rsa_d_attack/ ↩