5.7.2 解密指数
- 章节名: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*}
zxl对本书的所有笔记 · · · · · ·
-
5.4 素性检测
# 教学笔记 p193 定义 5.1 对一个判定问题的一个偏是的 Monte Carlo 算法......我们说一个偏...
-
5.7.3 Wiener 的低解密指数攻击
# 教学笔记 试图从 ($ab=1 \pmod{\varphi(n)}$), 中恢复出解密指数 ($a$). 设 ($ab=1+t\varph...
-
5.7.2 解密指数
-
因子分解:p-1 方法和椭圆曲线方法
#教学笔记 设 ($p$) 为 ($n$) 的一个素因子, 考虑 ($\mathbb{Z}_n^*$) 到 ($\mathbb{Z}_p$) ...
-
CRT-RAS 的差分差错攻击
#教学笔记 这是早期差分差错攻击的典范例子。CRT 方法可以提高 RSA 解密和签名的速度,以签...
说明 · · · · · ·
表示其中内容是对原文的摘抄