這個素數生成算法是否存在安全問題？

我面臨以下算法來生成RSA公鑰：

e = 0x10001

def generate_p():
   r := random odd 128-bit number
   p := (3*r^4 + 1)/4
   if is_prime(p) and gcd(p-1, e) = 1: 
       return p
   else:
       return generate_p()

def generate_q():
   r := random odd 128-bit number
   q := (11*r^4 + 1)/4
   if is_prime(q) and gcd(q-1, e) = 1:
       return q
   else:
       return generate_q()

p = generate_p()
q = generate_q()
N = p*q
d = modinv(e, (p-1)*(q-1))

所以本質上 $ s $ 和 $ t $ 是隨機的 128 位整數， $ 4p = 3s^4 + 1 $ 和 $ 4q = 11t^4 + 1 $ 和 $ p $ 和 $ q $ 主要。有沒有辦法 $ p $ 和 $ q $ 生成給我們幫助因素的資訊 $ N $ （大小為 1024 位）？

我認為Coppersmith 的攻擊是為了計算 $ s $ 和 $ t $ 作為小根 mod p/q，但它們不足以使算法適用。

這是最終讓我們考慮的方法 $ N $ 為比賽。我相信它完全打破了給定的方案。讓我們寫下公式 $ N $ :

$ N = pq = \frac{3s^4+1}{4}\cdot\frac{11t^4+1}{4} $ 對於一些 $ s, t \in [2^{128}, 2^{129}) $

經過一些重新安排：

$ \frac{16}{33}N = (st)^4 + \frac{1}{11}s^4 + \frac{1}{3}t^4 +\frac{1}{33} $

在我們的例子中，我們有 $ \frac{1}{11}s^4 + \frac{1}{3}t^4 +\frac{1}{33} < (st)^2 $ 因此在我們替換之後 $ x := (st)^2 $ :

$ x^2 \le \frac{16}{33}N < x^2 + x = x(x+1) < (x+1)^2 $

所以我們可以計算 $ x = \lfloor\sqrt{\frac{16}{33}N}\rfloor $ 然後因素 $ \sqrt x $ （只有 256 位）得到 $ s $ 和 $ t $ .

我覺得上述不等式通常成立，如果 $ s $ 和 $ t $ 有一些相似的價值，但我沒有試圖證明這一點。

看來， $ p-1 $ 因式分解方法可以適應具有非平凡機率的這種形式的因數。

我們有 $ 4n = (3r_p^4 + 1)q = (11r_q^4 + 1)p $ （在哪裡 $ r_p $ 是的價值 $ r $ 生成時選擇 $ p $ ， 和 $ r_q $ 是的價值 $ r $ 生成時選擇 $ q $ .

因此，如果任一 $ r_p $ 或者 $ r_q $ 沒有任何因子大於，比如說， $ 2^{40} $ （這將以非平凡的機率發生），那麼這種方法將考慮：

• 選擇任意奇數 $ g $ , 併計算 $ z := g^{3\cdot 11} \bmod 4n $
• 對於每個奇數素數 $ s $ 介於 3 和 $ 2^{40} $ （多次重複小素數），更新 $ z := z^{s^4} \bmod 4n $
• 計算 $ gcd(n, z-1) $

這可能可以簡化為模工作 $ n $ 而不是 $ 4n $ …

---

更新：再想一想，這種方法不太可能像我最初想像的那樣奏效；為了使其有效，需要平滑的相關值是 $ p-1 = 3(p_r^2 + 1)(p_r+1)(p_r-1)/4 $ , 或者 $ q-1 $ . 雖然有可能沒有 $ p_r^2 + 1 $ , $ p_r+1 $ , $ p_r-1 $ 將有一個很大的因素，它幾乎不像如果 $ p_r $ 僅需要平滑。

看起來所有三個值都沒有主要因素 $ > 2^{64} $ 機率約為 0.2%；因此 $ p-1 $ 方法將給出一個帶有 circa 的分解方法 $ O(2^{64}) $ 通過這種方法產生的大約 500 個模數中的一個會成功的工作。

引用自：https://crypto.stackexchange.com/questions/33301