# RSA LSB Oracle Attack

Posted by JHSN on April 18, 2018

# RSA LSB Oracle Attack

• 若 $m\in [0, \frac{n}{2})$，则 $2m\in [0, n)$，则有 2m % n % 2 = 2m % 2 = 0
• 若 $m\in [\frac{n}{2}, n)$，则 $2m\in [n, 2n)$，则有 2m % n % 2 = (2m - n) % 2 = 1

• 若 $m\in [0, \frac{n}{4})$，则 $4m\in [0, n)$，则有 4m % n % 2 = 4m % 2 = 0
• 若 $m\in [\frac{n}{4}, \frac{n}{2})$，则 $4m\in [n, 2n)$，则有 4m % n % 2 = (4m - n) % 2 = 1

• 若 $m\in [\frac{n}{2}, \frac{3n}{4})$，则 $4m\in [2n, 3n)$，则有 4m % n % 2 = (4m - 2n) % 2 = 0
• 若 $m\in [\frac{3n}{4}, n)$，则 $4m\in [3n, 4n)$，则有 4m % n % 2 = (4m - 3n) % 2 = 1

$m$ $2^{k+1}m$ $2^{k+1} m$ % $n$ 奇偶性
$[L, M)$ $[2^{k+1}L,2^{k+1}L+n)$ $2^{k+1} m - 2^{k+1}L$
$[M, R)$ $[2^{k+1}L+n, 2^{k+1}L+2n]$ $2^{k+1} m - 2^{k+1}L - n$

Code：