Private Key-d related Attack¶
d Leak Attack¶
Teori¶
- \(ed \equiv 1 \bmod φ(n)\)
- \(φ(n)|k=ed−1\)
- jelas \(k\) adalah genap
- dapat dibuat \(k=2^tr\),
- \(r\) ganjil
- \(t >= 1\).
- jadi untuk semua \(g\) yang relatif ke N, adalah
-
\(g^k \equiv 1 \bmod n\)
maka \(z=g^{k\over2}\) adalah akar kuadrat modulo \(N\),
kemudian ada
\[
\begin{align}
z^2 &\equiv 1 \bmod p \\
z^2 &\equiv 1 \bmod q
\end{align}
\]
persamaan diatas memiliki 4 solusi, 2 diantaranya :
Attention
kesalahan penulisan sumber
\[
\begin{align}
x \equiv \pm 1 N way \\
x \equiv \pm 1 \n way
\end{align}
\]
lalu 2 yang lainnya ±x, yang mana \(x\) memenuhi kondisi berikut :
Attention
kesalahan penulisan sumber
\[
\begin{align}
x &\equiv 1 pway \\
x &\equiv -1 q way
\end{align}
\]
jelas, \(z=g^{k\over2}\) memenuhi kondisi terakhir, dan kita dapat menghitung \(gcd(z−1,N)\) untuk menguraikan \(N\)
Tools¶
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/