Jumping's Second Law in RSA

$Sin(π ^ z) = Sin(π * z)$

即

$(π ^ z) \mod (2 * π) = (π * z) \mod (2 * π)$

那么在RSA中我们可以使用Jumping’s Second Law

将$e$模$\phi(n)$求逆元问题转换为$e$模$n$求逆元的问题

即

$c ≡ m ^ e \mod n ≡ m * e \mod n$

即我们可以通过求解$e$模$n$的逆元来求解明文

$m ≡ c * e ^ {-1} \mod n ≡ m * e * e ^ {-1} \mod n$

POC如下

import gmpy2

p = 2713
q = 3733
m = 8701623
e = 3163
n = p * q
c = pow(m, e, n)

# RSA Decrpytion

phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
m1 = pow(c, d, n)
print(m1)

# Jumping's Second Law in RSA

e_ = gmpy2.invert(e, n)
m2 = (c * e_) % n
print(m2)

"""
8701623
8701623
"""

---

上述内容在RSA中对于Jumping’s Second Law的使用并不是很严谨

这里给出一个更加严谨的使用

$π ^ z \mod 2 * π = π * z \mod 2 * π$

令$π$为$\frac{n}{2}$, $z$为$e$

则有

$(\frac{n}{2})^e \mod n = (\frac{n}{2}) * e \mod n$ – (1)

这里由于$n$为$p$, $q$两个素数之积，$\frac{n}{2}$不是整数

所以我们需要使用三素数RSA，令第三个素数$r$为2

$n = p * q * r = 2 * p * q$

则当$m = p * q = \frac{n}{2}$时

将$m = \frac{n}{2}$和$c ≡ m ^ e \mod n$带入式(1)可得

$c ≡ m ^ e \mod n ≡ m * e \mod n$

POC如下

import gmpy2
from Crypto.Util.number import *

p = getPrime(16)
q = getPrime(16)
e = getPrime(16)
r = 2
n = p * q * r
m = p * q
c = pow(m, e, n)
print(m)

# RSA Decryption

phi = (p - 1) * (q - 1) * (r - 1)
d = gmpy2.invert(e, phi)
m1 = pow(c, d, n)
print(m1)

# Jumping's Second Law in RSA Decryption

e_ = gmpy2.invert(e, n)
m2 = (c * e_) % n
print(m2)

"""
1854486911
1854486911
1854486911
"""

即在三素数RSA中有一个素数为2且$m$为其他两个素数之积时

可以使用Jumping’s Second Law对RSA算法进行攻击

将$m ^ e \mod n$转变为$m * e \mod n$

将分解$n$的时间复杂度$O(\sqrt{n})$

降到使用EEA计算$e$模$n$逆元的时间复杂度$O(\log_2 n)$

大大降低了RSA私钥的计算难度

---

考虑到$Sin$函数的对称性

则有

$π ^ z \mod 2 * π ≡ π - (π * z) \mod 2 * π$

即

$c ≡ m ^ e \mod n ≡ m * (1 - e) \mod n$

其中$n$为三素数之积且其中一个素数为2，$m$为其他两个素数之积

那么在这种情况下进行RSA解密则需要计算$1 -e$模$n$的逆元

即

$m ≡ c * (1-e)^{-1} \mod n$

但由于$n$和$1-e$均为偶数，无法求$(1-e)$模$n$的逆元

若e为偶数则在正常RSA解密中无法求$e$模$\phi(n)$的逆元

故这种情况下无解

EOF