有這個問題嗎從p從pmathbb{Z}_p真的很難？
我只想知道是否有明顯的東西使這個難題變得毫無用處。不是一個完整的密碼分析系統。歡迎任何暗示。
我們將與 Ring 合作 $ \mathbb{Z}_{p} $ , $ p $ 主要。
現在，我們定義一個函式 $ f:\mathbb{Z}{p}\times\mathbb{Z}{p}\mapsto\mathbb{Z}{p} $ ， 作為 $ f\left(a,b\right)=\frac{-a,b+a+b+z}{a+b-1} $ , $ z\in\mathbb{Z}{p} $ , $ z $ 是一個公共常數值。
接下來，我們定義一個系列如下：
$ a,b\in\mathbb{Z}{p},\ s{0}=a,\ s_{1}=b,\ s_{n}=f\left(s_{n-2},\ s_{n-1}\right) $
對於系列的給定元素， $ s_{n} $ ， 一個值 $ r_{n}=f\left(s_{n},a\right) $
問題是，考慮到函式 $ f $ 不聯想，有多難，知道 $ b $ 和 $ r_{n} $ ，恢復秘密的價值 $ a $ . 作為尺寸的一個例子，讓我們說 $ n=256,\ p\sim2^{256} $ .
此問題導致此處描述的公鑰密碼系統：
https://drive.google.com/open?id=1OeKh_ZJF-i7_KzWFRv8jodk3YkXe2qyv
丹尼爾·納格 - daniel.nager@gmail.com
TL;DR：不，這個問題並不難。
簡介：重新映射後 $ \Bbb Z_p $ 通過對合 $ x\to\overline x $ ， 功能 $ (x,y)\to\overline{-f(\overline x,\overline y)} $ 主要是聯想。我們把它按摩成一個阿貝爾有限群 $ (\mathcal S,\boxplus) $ . 這使得 $ \overline{r_n} $ 的線性函式 $ \overline a $ 和 $ \overline b $ 具有已知的標量係數，可以有效地解決問題的問題。
定義 $ \delta $ 和 $ \hat z $ 在 $ \Bbb Z_p $ 和 $ \delta=(p+1)/2 $ 和 $ \hat z=(-3,\delta^2-z)\bmod p $ . 原因稍後會很明顯，現在考慮 $ \hat z $ 作為任意固定的公共元素 $ \Bbb Z_p $ .
定義 $ l $ 作為勒讓德符號 $ l=\displaystyle\biggl(\frac{\hat z}p\biggr) $ , 並定義 $ m=p-l $ .
什麼時候 $ l=+1 $ ， 定義 $ \omega $ 作為一個特殊的解決方案 $ \omega^2=a $ 在 $ \Bbb Z_p $ ，例如範圍內的奇數 $ [1,p) $ .
定義集合 $ \mathcal S $ 作為： $$ \mathcal S=\begin{cases} {\infty}\cup\Bbb Z_p&\text{when }l=-1\ {\infty}\cup\Bbb Z_p-{0}&\text{when }l=0\ {\infty}\cup\Bbb Z_p-{\omega,p-\omega}&\text{when }l=+1 \end{cases} $$
定義內部法 $ \boxplus $ 在 $ \mathcal S $ 作為： $$ x\boxplus y=\begin{cases} y&\text{when }x=\infty\ x&\text{when }x\ne\infty\text{ and }y=\infty\ \infty&\text{when }x\ne\infty\text{ and }y=-x\ (x+y)^{-1}(x,y+\hat z)&\text{otherwise} \end{cases} $$
$ (\mathcal S,\boxplus) $ 是¹ , ² , ⁶ 的有限阿貝爾群 $ m $ 中性元素 $ \infty $ . 隨著公約 $ -\infty=\infty $ ，相反 $ -x $ 的 $ x $ 在小組中 $ (\mathcal S,\boxplus) $ is² 計算如下 $ (\Bbb Z_p,+) $ 什麼時候 $ x\ne\infty $ .
定義標量乘法 $ \boxtimes: \Bbb Z\times\mathcal S\mapsto \mathcal S $ 作為： $$ k\boxtimes x=\begin{cases} \infty&\text{when }k=0\ (-k)\boxtimes(-x)&\text{when }k<0\ \bigl((k-1)\boxtimes x\bigr)\boxplus x&\text{otherwise} \end{cases} $$ 並為所有人 $ x $ 在 $ \mathcal S $ 和整數 $ k $ , $ k’ $ ，它持有²： $$ \begin{align} (k\boxtimes x),\boxplus,(k’\boxtimes x)&=(k+k’)\boxtimes x&\text{and}\ k\boxtimes (k’\boxtimes x)&=(k,k’)\boxtimes x&\text{and}\ k\boxtimes x&=(k\bmod m)\boxtimes x \end{align} $$
為了 $ x $ 在 $ {\infty}\cup\Bbb Z_p $ 定義 $ \overline x=\begin{cases} \infty&\text{when }x=\infty\ \delta-x&\text{otherwise}\ \end{cases} $ .
定義 $ \hat{\mathcal S} $ 作為一組 $ \overline x $ 對所有人 $ x $ 在 $ \mathcal S $ . 它擁有 $ \hat{\mathcal S}=\mathcal S\iff l=-1 $ .
一個函式 $ f:\hat{\mathcal S}\times\hat{\mathcal S}\mapsto\hat{\mathcal S} $ 與問題的兼容⁴ $ f $ can² , ⁵ 現在定義為： $$ f(x,y)=\overline{-(\overline x\boxplus\overline y)} $$
«限制交換性»³ 屬性 $ f\bigl(f(x,y),f(y’,z)\bigr)=f\bigl(f(x,y’),f(y,z)\bigr) $ 是結合性和交換性的結果 $ \boxplus $ ，以及所有人的事實 $ x $ 在 $ \mathcal S $ 它擁有 $ \overline{(\overline x)}=x $ .
定義： $$ \begin{align} \hat s_0&=\overline a\ \hat s_1&=\overline b\ \hat s_n&=-(\hat s_{n-2}\boxplus\hat s_{n-1})\text{ when }n>1\ \hat r_n&=-(\hat s_n\boxplus\hat s_0)\ \end{align} $$ 並為所有人 $ n $ 它擁有²： $ \hat s_n=\overline{s_n} $ 和 $ \hat r_n=\overline{r_n} $ .
由此我們可以有效地計算²整數 $ u_n $ 和 $ v_n $ 在 $ \Bbb Z_m $ 這樣： $$ \overline{r_n}=(u_n\boxtimes\overline a),\boxplus,(v_n\boxtimes\overline b) $$
這允許²解決 $ a $ 給定 $ b $ 和 $ r_n $ , 知道參數 $ p $ , $ z $ , $ n $ . 這比離散對數問題要容易得多。什麼時候 $ \gcd(u_n,m)=1 $ ，唯一解是$$ a=\overline{(u_n^{-1}\bmod m)\boxtimes(\overline{r_n},\boxplus,(-v_n\boxtimes\overline b))} $$
筆記：
¹ : 特別是， $ \boxplus $ is² 關聯！
² ：證明留給讀者作為練習。
³ ：請參閱問題中連結的文件。
⁴ : 當 $ l\ne-1 $ 的輸入之一 $ f $ 可以排除在外 $ S $ ; 將其同化為 $ \infty $ .
⁵ : $ \delta $ 和 $ \hat z $ 選擇使得 $ \overline{(x+y-1)^{-1}(-x,y+x+y+z)}=-(\overline x\boxplus\overline y) $ .
⁶ ：如果沒有命名，該組已在那裡確定。