Contents

[toc]

# winner poorf

\begin{aligned} &N = q\times p\\ &\phi(n)=(p-1)\times (q-1)\\ &phi(n)\approx n\\ &ed =1 +k\phi(n)\\ &同除d\phi(n)得\\ &\frac{e}{\phi(n)}=\frac{1}{d\phi(n)}+\frac{k}{d}\\ &因为 \phi(n)\approx\;n\\ &\frac{e}{N}=\frac{1}{d\phi(n)}+\frac{k}{d}得到\frac{k}{d}的近似值\\ &利用求根公式或者以下步骤验证\\ &ed=k(p-1)(q-1)+1\\ &[\frac{ed}{k}]=(p-1)(q-1)\\ &\frac{pq-(p-1)(q-1)1+1}{2}=\frac{p+q}{2}\\ &(\frac{p+q}{2})^2-pq=(\frac{p-q}{2})^2 \end{aligned}
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  from sage.all import continued_fraction, Integer def wiener(e, n): m = 12345 c = pow(m, e, n) list1 = continued_fraction(Integer(e)/Integer(n)) conv = list1.convergents() for i in conv: d = int(i.denominator()) # 分母 m1 = pow(c, d, n) if m1 == m: return d n, e = pubkey print wiener(e, n) 

$\frac{e}{N}=\frac{1}{d\phi(n)}+\frac{k}{d}得到\frac{k}{d}$

# weird x-unca

e的取值范围为：

$$$$\begin{split} &e = \frac{y}{x} \cdot ((p+1)(q+1) \pm \frac{(p-q)\cdot N^{0.21}}{3(p+q)})\\ &\frac{e}{n}=\frac{y}{x}(1+\frac{p+q+1}{n}\pm\frac{p-q}{3(p+q)N^{0.79}})\\ &约等于\frac{e}{n}=\frac{y}{x}+0 \end{split}$$$$
 1 2 3 4 5 6 7  x = getrandbits(512) y = getrandbits(512) for yx in continued_fraction(e/N).convergents(): y = yx.numerator() x = yx.denominator() if 505 < int(y).bit_length() < 512: print(y, x) 

# ASIS Finals CTF 2017- Gracias Writeup

paper

Andrej Dujella说分母不仅可以得到d，d还可以写成$d=tqi+sq_{i-1}$

qi为第i次的分母

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27  from sage.all import continued_fraction, Integer from Crypto.Util.number import * def wiener(e, n): m = 12345 c = pow(m, e, n) q0 = 1 list1 = continued_fraction(Integer(e)/Integer(n)) conv = list1.convergents() for i in conv: k = i.numerator() # 分子 qi = i.denominator() # 分母 for r in range(20): for s in range(20): d = r*qi + s*qi_1 m1 = pow(c, d, n) if m1 == m: return d qi_1 = qi n, e = pubkey c1, c2 = c d = wiener(e, n) 

# 西湖论剑-2020-Wake me up until May ends-task

 1 2 3 4 5 6  limit1 = (3 * n) // (2 * (int(iroot(n, 4)[0]) + 3 * (p + q))) x * y < limit1 limit2 = (abs(p-q) * int(iroot(n, 4)[0]) * y) // (6 * (max(p, q))) z = e * x - y * _phi abs(z) < limit2 

limit1 $xy<\frac{3n}{2n^{\frac{1}{4}}+3(p+q)}$

limit2 (assume q>p) $z=ex-y\phi(n)>\frac{(p-q)n^{\frac{1}{4}}y}{6q}$ 由于e是一个一个减下去的，可以近似看为等号

$e = (\frac{(p-q)n^{\frac{1}{4}}}{6q}+\phi(n))\frac{y}{x}$ $\frac{e}{n} = (\frac{(p-q)n^{\frac{1}{4}}}{6qn}+\frac{\phi(n)}{n})\frac{y}{x}\approx\frac{y}{x}$