[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} $$

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}$

的近似值后sagemath可以自行输出分子分母

weird x-unca #

e的取值范围为：

$$ \begin{equation}\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}\end{equation} $$

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次的分母

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 #

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}$