5.7.2 解密指数

# 教学笔记

解密指数 ($a$) 若泄露, 则可分解 ($n$)，所以只更换一对新的 ($a,b$) 是不够的.

分解方法的思路是搜索 ($1$) 模 ($n$) 的一个非平凡平方根, 在这点上与 ($MR$) 素性测试极为相似.

设  ($ab-1=2^s r$),  对随机选取的  ($x$), 在 ($\mathbb{Z}_n$) 中计算 ($w=x^r$), 并考虑序列 
($$
w, w^2, w^{2^2}, \cdots, w^{2^s}=1.
$$)
在此序列中, 每个数都是其后继的平方根, 如果序列从一个非 ($\pm 1$) 的 ($w$) 出发, 不经过 ($-1$) 直接生成 ($1$), 则我们找到了 ($1$) 的一个非平凡平方根, 设为 ($y$), 有 
($$
y^2=1\pmod{n},
$$)
此时计算 ($(y\pm 1, n)$) 可分解 ($n$).

例子: 
\begin{align*}
n=&8561982470674355083495609209962630218105157492376985141720092947226015\\
&4082910265817171964443486887945476655536470437802833762066396085532140\\
&1942323281258726313836144217441011364684929804462426813318987395109699\\
&5648878903312014050522375924168711643900642242876453946761470783314578\\
&4162250163721788358471649521,\\
b= & 60728973.
\end{align*}
若泄露了解密指数
\begin{align*}
a=&5709696791605830376991778394572679416723290852325666399263733575505284\\
&6786411293931982217667813620637133253407422737696929964212322762505619\\
&2997046113009951531753295853031557466104612846144962739036944789651849\\
&2205865567793744231768592103798138368107664979159865771896469029733913\\
&229016210339352766250231877,
\end{align*}
则可计算出 ($ab-1=2^{10}r$), 其中
\begin{align*}
r= &3386172092730635738348764954550660105818793736738597480155219689316932\\
&5645167072618070429035437268913131915464663412472489667768956204213761\\
&3945316430436877883819868618357084194404447741298736291650201817707596\\
&0030964067462655888866997774605179125069086402465283702589109633809052\\
&86786394779551635721763323146555.
\end{align*}
随意选取一个 ($x$), 比如 ($x=2$), 计算出 ($w=x^r\pmod{n}$) 为
\begin{align*}
&6423237048757586231676268331329222436313751793515910054005067831990315\\
&5682509989584980506669423229019744304586250747862203430188990998821725\\
&1328746531103287227979380198319754004685229989273151324434759738275047\\
&6746301029337370253364038833530173134523769708955870937874996766409787\\
&3242869444965247343558268656.
\end{align*}
在 ($\mathbb{Z}_n$) 中计算序列 ($w, w^2, \big(w^2\big)^2, \cdots $) 可得
\begin{align*}
w^4=&4567766619375849390394835541476864309532478875754172808311688492961176\\
&2072739301808095754364634273099253425963764760215196048537952309697089\\
&5645530223362204929717118025760767445428730435770712624374351883876953\\
&0781029145670383844300271010556698689236167938362097507470831606387813\\
&9965148395377202919085774677,\\
w^8=&1\\
\end{align*}
计算 ($w^4+1$) 与 ($n$) 的公因子, 可得 ($n$) 的一个素因子 
\begin{align}
&7211128290154399888221820400551834616878327195018058432707791342350722\\
&5832430794242046855925145907882833692368775439302168725197515742972010\\
&02485185396577.
\end{align}
($n$) 的另一个素因子为
\begin{align*}
&1187329101101185873230813318074458449713211648756777308603810467306877\\
&7174325665692305720218775019872958464298136744615030362563990342998000\\
&812101902992273.
\end{align*}