跳转至

RSA attack

基本原理

加密原理

  1. 寻找两个大质数 p, q（p/q 之间的关系暂且不谈，不当的选取就会导致攻击漏洞）；
  2. n = pq; \(phi = \phi(n) = (p-1)(q-1)\) （欧拉函数）
  3. 寻找一个 e，使得：\(1<e<phi\) 且 gcd(e, phi) = 1
  4. m 为明文映射为的大数，则密文 \(c\equiv m^e\pmod{n}\)
  5. (e, n) 作为公钥公开。

解密原理

  1. 私钥为 \(d=e^{-1}\pmod{\phi(n)}\)
  2. \(c^d = m^{ed}\pmod{n} = m^{ed\pmod{\phi(n)}} =m\)

安全性保证

合理的 RSA 的安全性完全来自 n 的质数分解难度；不合理的是什么？看下面就知道了。

Exponential attack

Low public exponent attack（低加密指数攻击）

优先尝试 sagemath 的 m = Integer(c).nth_root(e)

e = 1

Question

cryptohack - Salty

cryptohack 上刚好有这么一个题：

Python
n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767                                                                  
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485
for i in range(123456789):
    pt = ct + i * n
    plaintext = bytes.fromhex(hex(pt)[2:])
    if b'crypto' in plaintext:
        print("i =", i, plaintext) # i = 0 b'crypto{saltstack_fell_for_this!}'
        break
    if i % 10000 == 0:
        print(i)
Flag

crypto{saltstack_fell_for_this!}

e = 2 (Rabin)

\(\phi=(p-1)(q-1)\) 且由于 p/q 为素数，所以 \(gcd(e, \phi)\neq 1\) ，那么怎么做？

回顾 \(c=m^e\pmod{n}\) ，现在就是 \(m^2=c\pmod{n}\) 。

如果 \(m^e < n\) ，那么甚至不用取模了，直接开根：

m^e < n
c = 42482525051044
e = 2
long_to_bytes(gmpy2.iroot(c, e)[0]) # b'ctf'

如果要取模呢？可以使用 Rabin 算法 转变为二次剩余问题。但是注意，这一切的前提是模数为素数；n 又不是素数，怎么做？

e = 2
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
e = 2
pt = "darctf{xxx}"
m = int(pt.encode().hex(), 16)
c = pow(m, e, n)
print(c) 
# 55804540899466191494822903355151119222813727476411593093741269550876471676261

作为练习，我使用了一个较小的 n ，可以很容易分解：

Text Only
n = 275127860351348928173285174381581152299 * 319576316814478949870590164193048041239
\[ m^2 \equiv c\pmod{n} \iff \begin{cases}m^2\equiv c\pmod{p}\\m^2\equiv c\pmod{q}\end{cases} \]

在 m 的解个数 中的结论，我们可以知道对于上方右侧的每个方程，都有 gcd(e, p-1) = 2 个解，分别记作[x1, x2] [y1, y2] 1。

rabin
n = 275127860351348928173285174381581152299 * 319576316814478949870590164193048041239
p, q = 275127860351348928173285174381581152299, 319576316814478949870590164193048041239

import gmpy2

def squareMod(c, mod):          # 模意义下开根，找到 x, 使得 x^2 % mod = c
    assert(mod % 4 == 3)
    res = gmpy2.powmod(c, (mod+1)//4, mod)
    return res, mod - res

def getPlaintext(x, y, p, q):   # 假设 m%p=x, m%q=y, 求明文
    res = x*q*gmpy2.invert(q, p) + y*p*gmpy2.invert(p, q)
    return res % (p*q)

def solve(c, p, q):             # 已知 p,q, 解密 c
    px = squareMod(c, p)
    py = squareMod(c, q)

    for x in px:
        for y in py:
            yield getPlaintext(x, y, p, q)

c = 55804540899466191494822903355151119222813727476411593093741269550876471676261
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239

for msg in solve(c, p, q):
    res = hex(msg)[2:]
    if len(res) % 2 == 1:
        res = '0' + res
    print(bytes.fromhex(res))

# b'r\xd8lq+g\xc8r\x84\x04\xe2\xc6i\xb4\\?\xb13\xa9_[\xa3\x8b\xcb\xbd\xbf\xe6\x95K)h\xe1'
# b'darctf{r@bln_a77@ck_e_2}'
# b'\xc2cj\xe5\xc3\xd8\xe4?\x9768\xa5\x8e(\x9f:+\xa9\x8a^\xde\x0f\xb4\x92\xe7\xb8\x94\x8a\x1a^\xfe`'
# b'O\x8a\xfet\x98q\x1b\xcdw\x92\xc8B\x98\xda\xbel\xba\xd8Mm\xe1\xcd_\xfej\\\x19T4\x94\xc7\xfc'

当然，sage 中应当是帮我们内置了这么一个算法，所以：

mod(c, p).sqrt(all=True)
from sage.all import *
c = 55804540899466191494822903355151119222813727476411593093741269550876471676261
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
sqrt_c_p = Mod(c, p).sqrt(all=True)
sqrt_c_q = Mod(c, q).sqrt(all=True)
for i in sqrt_c_p:
    for j in sqrt_c_q:
        m = crt([int(i), int(j)], [p, q])
        from Crypto.Util.number import long_to_bytes
        print(long_to_bytes(m))

e = 3

如果 \(m^e < n\) ，仍然可以直接开根；不然，可以由 \(m^e = kn+c\) ，尝试爆破 k 并尝试开 3 次根，能分解多半是可行解；但是一般来说花费时间有点久。

当然，sage 帮我们方便的实现了这个功能（下面的分解用时约 3min ，可见效率还是很低的，毕竟这里的 n 非常小了）：

e = 3
from sage.all import *
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
e = 3
pt = "darctf{r@bln_a77@ck_e_2}"
m = int(pt.encode().hex(), 16)
c = pow(m, e, n)
print(c) # 82453779934743057049976069612841272595880705095622841974484769483483076860419

from Crypto.Util.number import *
import gmpy2

c = 82453779934743057049976069612841272595880705095622841974484769483483076860419
m = Mod(c, n).nth_root(e)
print(long_to_bytes(m)) # b'darctf{r@bln_a77@ck_e_2}'
solution of m^e

Theorem

If \(gcd(e, p-1)=1\) and p is prime, the \(m^e \equiv c\pmod{p}\) has exactly one solution for m.

math.stackexchange 上的问答中较为靠下的一个回答给出更广泛的结论：

Theorem

If p is prime, \(p \nmid c\), then \(m^e \equiv c \pmod{p}\) has 0 or d = gcd(e, p-1) solutions, being the latter if \(c^{\frac{p-1}{d}}\equiv 1 \pmod{p}\).

证明略，其中最后一两步如果看不懂可以参考 group theory - Solution to \(x^n=a \pmod p\) where \(p\) is a prime .

gcd(e, phi) != 1

一般来说 \(gcd(e, \phi)=1\) 的，但要是 \(gcd(e, \phi)\neq 1\) ，那么怎么做？e=2/3/4 …… 等十分小的数时前面已经说明了，这里考虑比较一般的情况。

由于 \(gcd(e, \phi)\neq 1\)，正常意义下的私钥 d 是不存在的，但是考虑到欧拉扩展定理：

若 \(gcd(e, \phi) = b \neq 1\) ，则有 \(c = m^e = m^{ab}\pmod{n} = m^{ab \pmod{\phi}}\)；

gcd(a, phi)=1

取 \(d = a^{-1}\pmod{\phi}\)，则有 \(c^d = m^{abd\pmod{\phi}} = m^b\pmod{n}\)；所以只需要对 \(c^d\pmod{\phi}\) 开 b 次根就好。

当然，不难发现，哪怕 \(gcd(e, \phi)=1\) ，上述过程依然适用。

Python
from sage.all import *

p= 127577058764408216374028752283743628765651360507566484643526093715329608267323381565274095814069864692746147152580906850350743742856555229701448239882612922698102985146366639955081466129923966803267071097174222576416224094182123529282235807472362341680183683025490897702891081336913842652559163341223338641607
q= 156492273708587234539506501480609692085997989594717058472605523051244522493701609615085173280972894139427194976925940854142835807192417391269823151398439665817176522629246535810290194301862945052149450578938260979300632842291287807430486629994530805358742405299538986591596966945727494262182814875780600646003
e= 750
c= 7029383721249299532521086933490698266831518266762255492452526410777276825803657150303837084263410309063739203644435184397762022380085273363900423091223180151147964276354189658062571415744140073426572149093499560918765793389358300893454490774387180728097370701432534877005948330689495694820361726719418371072834639369078180094444137972424909816959445043108154884587947573054460257114169961823509538355580857411319157089278918107229480661280354242839678709689654304688727345294473487201644985815128413154870914132135222144633969959773621933444285994038028721862094040876152694240238708737727034258171506516394913692187

def get_m(n, e, c, phi=None):
    """
    Returns the private exponent for the given public exponent and modulus.
    """
    from sage.all import GCD, euler_phi, inverse_mod, power_mod, Integer, is_prime
    if is_prime(n):
        phi = n - 1
    elif phi is None:
        phi = euler_phi(n)
    b = GCD(e, phi)
    if b == 1:
        d = inverse_mod(e, phi)
    else:
        a = e // b
        assert a*b == e
        # print(a, b)
        d = inverse_mod(a, phi)
        mb = power_mod(c, d, n)
        m = Integer(mb).nth_root(b)
    return m

import sympy
n = p*q
phi = (p-1)*(q-1)
m = get_m(n, e, c, phi)
print(bytes.fromhex(hex(m)[2:]))
# b'flag{0e2f9add-31fd-4733-8f25-39297516f4e2}'

gcd(a, phi)!=1

如果 \(gcd(a, \phi) \neq 1\)，也就同样无法找到 a 的逆元 d；此时考虑递归求解：

Python
def get_mb(n, e, c, phi=None):
    """
    Returns the private exponent for the given public exponent and modulus.
    """
    from sage.all import GCD, euler_phi, inverse_mod, power_mod, is_prime
    if is_prime(n):
        phi = n - 1
    elif phi is None:
        phi = euler_phi(n)
    b = GCD(e, phi)
    if b == 1:
        d = inverse_mod(e, phi)
    else:
        a = e // b
        assert a*b == e
        # print(a, b)
        if GCD(a, phi) == 1:
            d = inverse_mod(a, phi)
            mb = power_mod(c, d, n)
        else:
            print("gcd(a, phi) != 1, a =", a)
            mb, b_ = get_mb(n, a, c, phi=phi)
            b *= b_
    return mb, b

from sage.all import Integer
mb, b = get_mb(n, e, c)
m = Integer(mb).nth_root(b)

如果最后一个 get_mb 中得到的 a = 1，那么毫无疑问 b = e，且 mb = c；那就好比直接开根，没有什么意义（如果能直接开，那就不需要这些东西）。

此时大概率是 \(e=2^{k}, k\in N\) 的情况；而这样我们可以一层一层开平方根（此时攻击条件与 e=2 相同），示例来自 cryptohack - Broken RSA：

broken rsa
from sage.all import *
from Crypto.Util.number import long_to_bytes
from sympy import sqrt_mod, legendre_symbol
n = 27772857409875257529415990911214211975844307184430241451899407838750503024323367895540981606586709985980003435082116995888017731426634845808624796292507989171497629109450825818587383112280639037484593490692935998202437639626747133650990603333094513531505209954273004473567193235535061942991750932725808679249964667090723480397916715320876867803719301313440005075056481203859010490836599717523664197112053206745235908610484907715210436413015546671034478367679465233737115549451849810421017181842615880836253875862101545582922437858358265964489786463923280312860843031914516061327752183283528015684588796400861331354873
e = 16
ct = 11303174761894431146735697569489134747234975144162172162401674567273034831391936916397234068346115459134602443963604063679379285919302225719050193590179240191429612072131629779948379821039610415099784351073443218911356328815458050694493726951231241096695626477586428880220528001269746547018741237131741255022371957489462380305100634600499204435763201371188769446054925748151987175656677342779043435047048130599123081581036362712208692748034620245590448762406543804069935873123161582756799517226666835316588896306926659321054276507714414876684738121421124177324568084533020088172040422767194971217814466953837590498718

################# m^16 = m^2^2^2^2
assert is_prime(n)

def debug_info(*args, **kwargs):
    DEBUG = False
    if DEBUG:
        print(*args, **kwargs)

def sqrt_mods(cs:list, n, debug=False):
    ms = []
    for c in cs:
        if legendre_symbol(int(c), int(n)) != 1:
            # 不是二次剩余，不可开根
            continue

        m_ = Mod(c, n).sqrt(all=True)
        debug_info("dealing c:", c)
        for m in m_:
            debug_info(long_to_bytes(int(m)))
        ms += m_

        # sympy 的 sqrt_mod 只分解得到其中一个结果，最终会漏掉
        # 详见 https://darstib.github.io/blog/CTF/Note/Crypto/RSA_attack/#m-%E7%9A%84%E8%A7%A3%E4%B8%AA%E6%95%B0
        # m = sqrt_mod(c, n)
        # debug_info(long_to_bytes(m))
        # ms.append(m)
    return ms


m16s = [ct]
m8s = sqrt_mods(m16s, n)
debug_info("m8s:", m8s)
m4s = sqrt_mods(m8s, n)
debug_info("m4s:", m4s)
m2s = sqrt_mods(m4s, n)
debug_info("m2s:", m2s)
ms = sqrt_mods(m2s, n, debug=True)
debug_info("ms:", ms)
for m in ms:
    print(long_to_bytes(int(m)))

# b"Hey, if you are reading this maybe I didn't mess up my code too much. Phew. I really should play more CryptoHack before rushing to code stuff from scratch again. Here's the flag: crypto{m0dul4r_squ4r3_r00t}"

Multi e&phi

攻击条件：gcd(e, phi) != 1，gcd(n1, n2) != 1

类似于模不互素，我们令 p = gcd(n1, n2) ，则 q1 = n1//p, q2 = n2//p，则有：

\[ \begin{cases} c_1^{d_1}=m^b\bmod q_1 \\ c_2^{d_2}=m^b\bmod q_2 \end{cases} \implies m^b = crt([c_{1}^{d_{1}}\%q_{1}, c_{2}^{d_{2}}\% q_{2}], [q_{1}, q_{2}]) \]

但是发现此时求得的 \(m^b\) 并不能直接开 b 次根 1；但换个角度看，这不也是我们在解决的 rsa 问题吗？现在新的密文是 2 \(c <= m^b, n <= q_{1}*q_{2}, e <= b\) ，这不是就解决了吗？

new gcd(e,phi)=1

如果在经过上面转变后，新的 gcd(e, phi)=1 ，那么我们就是正常的 rsa 了，且 n 已经分解好：

many_e_phi_1.py
"""
from Crypto.Util.number import *
import random
# from secret import flag
flag=''
table='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
pad=100-len(flag)
for i in range(pad):
    flag+=random.choice(table).encode()
e=343284449
m=bytes_to_long(flag)
assert m>(1<<512)
assert m<(1<<1024)
p=getPrime(512)
q=getPrime(512)
r=getPrime(512)
print('p=',p)
print('q=',q)
print('r=',r)
n1=p*q
n2=q*r
c1=pow(m,e,n1)
c2=pow(m,e,n2)
print('c1=',c1)
print('c2=',c2)
"""

from sage.all import *

e = 343284449
p = 11820891196647569262137841192985418014377132106496147254821784946481523526822939129065042819464351666077658751406165276121125571355594004514547517855730743
q = 10450390015864176713581330969519712299844487112687677452105216477861582967322473997670559995588440097951786576039009337782247912476227937589298529580432797
r = 9484954066160968219229920429258150817546418633451929876581842443665029377287119340232501682142185708534413073877473741393278935479791561681402673403009771

c1 = 69574855207460025252857869494766338442370688922127811393280455950372371842144946699073877876005649281006116543528211809466226185922844601714337317797534664683681334132261584497953105754257846471069875622054326463757746293958069752489458646460121725019594141157667480846709081917530190233900184428943585065316
c2 = 66183492015178047844987766781469734325646160179923242098082430373061510938987908656007752256556018402101435698352339429316390909525615464024332856855411414576031970267795270882896721069952171988506477519737923165566896609181813523905810373359029413963666924039857159685161563252396502381297700252749204993228

# 验证可行的必要条件
phi1 = (p - 1) * (q - 1)
phi2 = (q - 1) * (r - 1)
b1 = gcd(e, phi1)
b2 = gcd(e, phi2)
assert b1 == b2
a1 = e // b1
a2 = e // b2
b = b1 # 用 b 统一代替，b = 343284449 == e

# 求解
d1 = pow(a1, -1, phi1)
d2 = pow(a2, -1, phi2)
c = crt([pow(c1,d1,p), pow(c2,d2,r)], [p, r]) # == m^b
n = p * r # 新的 n

phi = (p - 1) * (r - 1)
d = pow(b, -1, phi)
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:])) # b'moectf{Th1s_iS_Chinese_rEm41nDeR_The0rEm_CRT!}YWMZSTyfRvhjTCJuQCwALQBcWHFCgTDIZWJaxRUzBPCmFOnbDTRBau'

Extra

当使用的 e 相同时，其实不难得到：\(\begin{cases}m^e =c_{1}\pmod{n_{1}}\\ m^e=c_{2}\pmod{n_{2}}\end{cases}\)，使用 sagemath 中的 CRT_list() 方法可以很快的求解到 \(m^e \pmod{p*q*r}\) ，可以验证这样获得值等于 \(pow(m,e,p*q*r)\)；但是模数太大了，难以分解；即使是很小的 e (e = 2) 我也没能分解出来。

new gcd(e, phi)!=1

要是新产生的 gcd(e,phi)!=1 ，就转变为了 一组 e, phi 的情况了：

many_e_phi_2.py
from sage.all import *
e1 = 14606334023791426
n1 = 15848477716099753229061105911923143022389100496585807518993837576102534462043194116619385857927748061397249782381439885030297281760313655984354167005661008888718357134674249156614681638863679015479391847068348113489701337473262927808261967350366795633795543505703845606067045115243249537229108546272131429244457163342256387732236996418260843007569149387213329951406657469770618225877026401261848714538526688419134479943104911077402172330808220738139303070470120465456908824191640348115644774893040473576807682731982391129182748695821091864850237701682483798458814537415464726492081290583865419431028569430363239973387 

c1 = 11402389955595766056824801105373550411371729054679429421548608725777586555536302409478824585455648944737304660137306241012321255955693234304201530700362069004620531537922710568821152217381257446478619320278993539785699090234418603086426252498046106436360959622415398647198014716351359752734123844386459925553497427680448633869522591650121047156082228109421246662020164222925272078687550896012363926358633323439494967417041681357707006545728719651494384317497942177993032739778398001952201667284323691607312819796036779374423837576479275454953999865750584684592993292347483309178232523897058253412878901324740104919248

e2 = 13813369129257838
n2 = 11445377519264375060023079150962157833890568553640391338775989472330549038258150532468931626590818889296627067314268489584599131270267459828529179275532395041458525655212071679524344189181556827177841274953525505205469905975591164796436528919538933755927696086719287398795598052871568671842946947271918760899756232697968504961711410196730301840362369205729432748105709812801671538869541242955495144296736011715597473451149699457286420032252438757033057264819071583173255215409033569426653382271461349576578652124917074830516189769868866985581229557115992762278225013198895683154925091608336698625404745349624865012491
c2 = 7984888899827615209197324489527982755561403577403539988687419233579203660429542197972867526015619223510964699107198708420785278262082902359114040327940253582108364104049849773108799812000586446829979564395322118616382603675257162995702363051699403525169767736410365076696890117813211614468971386159587698853722658492385717150691206731593509168262529568464496911821756352254486299361607604338523750318977620039669792468240086472218586697386948479265417452517073901655900118259488507311321060895347770921790483894095085039802955700146474474606794444308825840221205073230671387989412399673375520605000270180367035526919

""" solve """

p = gcd(n1, n2)
q1, q2 = n1 // p, n2 // p
phi1, phi2 = (p-1)*(q1-1), (p-1)*(q2-1)
b1 = gcd(e1, phi1)
assert b1==gcd(e2, phi2)

a1, a2 = e1 // b1, e2 // b1
d1, d2 = inverse_mod(a1, phi1), inverse_mod(a2, phi2)
c1d1, c2d2 = power_mod(c1, d1, q1), power_mod(c2, d2, q2)
m_b1 = crt([c1d1, c2d2], [q1, q2])

# 按照只有一组 e phi 的方法继续做，n = q1*q2, e = b1
n = q1 * q2
phi = (q1-1) * (q2-1)
b2 = gcd(b1, phi)
a = b1 // b2
d = inverse_mod(a, phi)
m_b2 = power_mod(m_b1, d, n)
m = Integer(m_b2).nth_root(b2)
print(bytes.fromhex(hex(m)[2:])) # b"flag{gcd_e&\xcf\x86_isn't_1}"

Modular attack

N ezFactor

Question

CryptoHack – RSA challenges Everything is Big

题目中给出了很大的 N，但是放到 factordb.com 中，分解一下就出来了；或者对于比较小的 N，sage math 的 factor 之类的都可以分解。

分解为 factors 如下：

Python
from Crypto.Util.number import *
e = 0x9ab58dbc8049b574c361573955f08ea69f97ecf37400f9626d8f5ac55ca087165ce5e1f459ef6fa5f158cc8e75cb400a7473e89dd38922ead221b33bc33d6d716fb0e4e127b0fc18a197daf856a7062b49fba7a86e3a138956af04f481b7a7d481994aeebc2672e500f3f6d8c581268c2cfad4845158f79c2ef28f242f4fa8f6e573b8723a752d96169c9d885ada59cdeb6dbe932de86a019a7e8fc8aeb07748cfb272bd36d94fe83351252187c2e0bc58bb7a0a0af154b63397e6c68af4314601e29b07caed301b6831cf34caa579eb42a8c8bf69898d04b495174b5d7de0f20cf2b8fc55ed35c6ad157d3e7009f16d6b61786ee40583850e67af13e9d25be3
c = 0x3f984ff5244f1836ed69361f29905ca1ae6b3dcf249133c398d7762f5e277919174694293989144c9d25e940d2f66058b2289c75d1b8d0729f9a7c4564404a5fd4313675f85f31b47156068878e236c5635156b0fa21e24346c2041ae42423078577a1413f41375a4d49296ab17910ae214b45155c4570f95ca874ccae9fa80433a1ab453cbb28d780c2f1f4dc7071c93aff3924d76c5b4068a0371dff82531313f281a8acadaa2bd5078d3ddcefcb981f37ff9b8b14c7d9bf1accffe7857160982a2c7d9ee01d3e82265eec9c7401ecc7f02581fd0d912684f42d1b71df87a1ca51515aab4e58fab4da96e154ea6cdfb573a71d81b2ea4a080a1066e1bc3474
factors = [134669927709128070756424801419548805501808076912262801434800605920827612464368906595661348393409080650056282638489243851059781971132159889896843018381187994628859917822755789986092763460463295405651440816348815008245093856412009397970192375577360567873185141159375280522236909060526334123001733587717969177157, 173121513995818161102245832683211062320154182361182024148671930683926870711405647497524667705258311163551127156955342410807842326402024536548989691926348678692995530897791794818646241971728281417961389048493180792474943296919266335463768525410560161755731138916915767148609523790355387780727531897114371948649]

phi = (factors[0] - 1) * (factors[1] - 1)
d = pow(e, -1, phi)
m = pow(c, d, N)
print(bytes.fromhex(hex(m)[2:]).decode()) # crypto{s0m3th1ng5_c4n_b3_t00_b1g}

Roll enc

类似于分组加密，分别解密之后恢复即可。

Python
from sage.all import *
from Crypto.Util.number import *

n=920139713
e=19
c=[704796792,752211152,274704164,18414022,368270835,483295235,263072905,459788476,483295235,459788476,663551792,475206804,459788476,428313374,475206804,459788476,425392137,704796792,458265677,341524652,483295235,534149509,425392137,428313374,425392137,341524652,458265677,263072905,483295235,828509797,341524652,425392137,475206804,428313374,483295235,475206804,459788476,306220148]

phi = euler_phi(n)
d = inverse_mod(e,phi)
flag=""
for i in c:
  m=long_to_bytes(pow(i,d,n))
  flag=flag+m.decode()#decode返回字符串
print(flag)

Modulars not coprime

模不互素是指：多次给出的 n 不互素，那么使用欧几里得算法求解公因数后两个都可以分解，从而被破解。

n=multi primes

n 能够分解为多个素数，那么分解难度相对较低，分解后求解欧拉函数即可。

Question

CryptoHack – RSA challenges Manyprime

可以使用下面的公式寻找 phi ：

manyPrime
def manyPrime(n):
    from sage.all import *
    n = Integer(n)
    factors = factor(n)
    phi=1
    for i in factors:
        phi *= (i[0]-1)*(i[0]**(i[1]-1))
    return phi

当然 sagemath 中内置了 euler_phi() 方法直接寻找。

Tip

有时使用 factordb 分解大数，发现能够分解出一些小数，但是剩下最大的那个数依旧不是质数。如果已经分解出来的部分的乘积大于 m，那么也够用了。

例如，当前已经分解 \(n = a*....*b * A\) 且 \(is\_prime(A)==False\)，那么我们记 \(a*\dots*b = k, \phi(k)\) 是不难计算的。如果 m < k，则有 \(m=c^{d_n}\pmod{n} = c^{d_{k}}\pmod{k}\) 其中 \(d_x\) 表示在模 x 的情况下 e 的逆元。

Same modulars

攻击条件：使用相同的 n，不同的 e 对同一段密文进行了两次加密且 gcd(e1, e2)=1。

若 gcd(e1, e2)=1，由扩展欧几里得算法得 s1e1+s2e2 = 1 (mod n)，故有

\[ \begin{cases} c_{1} = m^{e_{1}}\pmod{n} \\ c_{2} = m^{e_{2}}\pmod{n} \end{cases} \implies c_{1}^{s_{1}}*c_{2}^{s_{2}} = m^{s_{1}e_{1}+s_{2}e_{2}} = m \pmod{n} \]
same module problem
from sage.all import *
from Crypto.Util.number import *
pt = "darctf{D0n't_uS@_s4me_m_wlth_s@m3_n}"
m = bytes_to_long(pt.encode())
p = getPrime(512)
q = getPrime(512)
n = p*q
e1 = 0x10001
e2 = 0x10003
c1 = pow(m,e1,n)
c2 = pow(m,e2,n)
print(n, c1, c2)
same module solver
n, c1, c2 = 98579989110595409237121911373477535218782298101063142983736645609805239388519112976391020979766081600973756603466949088252537954226386662303812158399922085551030673235391122690690489614742213805086900032298294111577763523768897971988558981215342244298264282081994037439494627023764742694360182589392496394219, 72425280162325234030138440618893638248350200498036366062366806318799000892558826781676354721574015025260601419134051722219497286707335137576108567308732036645624100301827935632352883927544186998800800613763615685859542808865932240404766516153255982736474238236663712354416704416640104545540927957772848234809, 93315981548035764166225288143368979083298522822532493540407786336594222729430799616658596163211870306390452369608572159579771439267416866701746284141500177829084900908267884433644532039697396467417361020676970648165967089856122514452470159341424342038954503503377562938855963571013967607308287570236674707243
e1, e2 = 0x10001, 0x10003
s,s1,s2 = xgcd(e1,e2)
m = mod(power_mod(c1,s1,n)*power_mod(c2,s2,n), n)
print(long_to_bytes(int(m))) # b"darctf{D0n't_uS@_s4me_m_wlth_s@m3_n}"

Get p q if we know phi

\[\begin{cases}p+q=n-\varphi(n)+1\\p-q=\sqrt{\left(n-\varphi(n)+1\right)^2-4n}\end{cases}\]

Improper pq

small |p-q|

常见的情况有 q = next_prime(p) 或者 p, q = util.GeneratePrimePairByBitLength(bsize, gap) 导致二者非常接近，可以使用费马因式分解法。

Question

CryptoHack – RSA challenges Infinite Descent

small_p_min_q
from sage.all import *
n = ...
e = 65537
c = ...

def fermat_factor(n):
    # from sage.all import ceil, is_square
    # def nth_root(n, e):
    #     return pow(n, 1 / e)

    from libnum import nroot
    from math import ceil
    from gmpy2 import is_square

    a = ceil(nroot(n, 2))
    b = a**2 - n
    while not is_square(b):
        a += 1
        b = a**2 - n

    c = nroot(b, 2)
    return a - c, a + c

p, q = fermat_factor(n)
# print(p, q)
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)
m = power_mod(c, d, n)
from libnum import n2s
print(n2s(m)) # b'crypto{f3rm47_w45_4_g3n1u5}'

n&npnq

ZJUBUS 上有这么一个题，给我 e, n, c 之外，还给我 npnq，其中 n == p*q and npnq = next_prime(p)*next_prime(q)

我们记 \(npnq = np*nq\) ，则会发现：p*nq - q*np 很小！也就是说，我们可以利用上面讲的方法分解 n*npnq ，如果能够得到 \(p1 = p*nq\) ，则有 \(p = gcd(n, p_{1})\) ，这样 n 就分解出来了。

由于 \(n*npnq = p*q * np * nq = p * nq * q * np\) ，所以被分解为哪种情况并不能确保，我们可以选择多保留几组；当然，考虑到 \(|p*nq - q*np| < |np * nq - p*q|\)，所以一般来说第一个解应该是我们想要的。

fematFactorization
def fematFactorization(n, k=1) -> list:
    """n == p*q && |p-q| is small"""
    from gmpy2 import iroot, is_square
    from itertools import count

    factors_list = []
    a = iroot(n, 2)[0]
    b_2 = a**2 - n
    for a in count(a):
        b_2 = a**2 - n
        if b_2 < 0:
            continue
        b = iroot(b_2, 2)[0]
        if a ** 2 - b ** 2 == n:
            factors_list.append((a-b, a+b))
        if len(factors_list) == k:
            return factors_list

##### demo case #####
from sage.all import random_prime, next_prime, gcd, inverse_mod
m = int(b"darctf{_f3m4t_f4c70r1z4t10n_1s_s0_e4sy}".hex(), 16)
print(m)
p = random_prime(1 << 1024, lbound=1 << 1023)
q = random_prime(1 << 1024, lbound=1 << 1023)
n = p * q
npnq = next_prime(p) * next_prime(q)
e = 0x10001
c = pow(m, e, n)
print(c, n, npnq, sep='\n')
factors_list = fematFactorization(n * npnq, k=2) # 预防分解后对应结果为 n & npnq 而无效

for p1, q1 in factors_list:
    assert p1 * q1 == n * npnq
    p, q = gcd(p1, n), gcd(q1, n)
    assert p * q == n
    phi = (p - 1) * (q - 1)
    try:
        d = inverse_mod(e, phi)
        m = pow(c, d, n)
        print(bytes.fromhex(hex(m)[2:]))
    except Exception as error:
        print("Error:", error)

n&p.xor.q

在 Math.stackexchange 提出了一个问题：

Question

Given two unknown large primes p and q, can we efficiently factor n=pq if we additionally know p⊕q (bitwise XOR of the primes)?

下面的回答给出了算法思路，大致思路是逐比特判断 \(p[:k] \times q[:k] \equiv n[:k] \pmod{2^{k}}\) ，并从 0 开始逐步推导 p,q；但是显然每一步都有两种解，如此计算的复杂度依旧在 \(O(2^{\log n})=O(n)\)；而 \(p \oplus q = t\) 作为一个约束，可以达到剪枝的效果，提高了算法思路的可行性。

提出问题的人也实现了这个算法，并放在了 xor_factor 。但是疑似存在一些 bug，来看 zer0ptsCTF2022-AntiFermat：

chall.py
from Crypto.Util.number import isPrime, getStrongPrime
from gmpy import next_prime
from secret import flag

# Anti-Fermat Key Generation
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537

# Encryption
m = int.from_bytes(flag, 'big')
assert m < n
c = pow(m, e, n)

print('n = {}'.format(hex(n)))
print('c = {}'.format(hex(c)))
#n = 0x1ffc7dc6b9667b0dcd00d6ae92fb34ed0f3d84285364c73fbf6a572c9081931be0b0610464152de7e0468ca7452c738611656f1f9217a944e64ca2b3a89d889ffc06e6503cfec3ccb491e9b6176ec468687bf4763c6591f89e750bf1e4f9d6855752c19de4289d1a7cea33b077bdcda3c84f6f3762dc9d96d2853f94cc688b3c9d8e67386a147524a2b23b1092f0be1aa286f2aa13aafba62604435acbaa79f4e53dea93ae8a22655287f4d2fa95269877991c57da6fdeeb3d46270cd69b6bfa537bfd14c926cf39b94d0f06228313d21ec6be2311f526e6515069dbb1b06fe3cf1f62c0962da2bc98fa4808c201e4efe7a252f9f823e710d6ad2fb974949751
#c = 0x60160bfed79384048d0d46b807322e65c037fa90fac9fd08b512a3931b6dca2a745443a9b90de2fa47aaf8a250287e34563e6b1a6761dc0ccb99cb9d67ae1c9f49699651eafb71a74b097fc0def77cf287010f1e7bd614dccfb411cdccbb84c60830e515c05481769bd95e656d839337d430db66abcd3a869c6348616b78d06eb903f8abd121c851696bd4cb2a1a40a07eea17c4e33c6a1beafb79d881d595472ab6ce3c61d6d62c4ef6fa8903149435c844a3fab9286d212da72b2548f087e37105f4657d5a946afd12b1822ceb99c3b407bb40e21163c1466d116d67c16a2a3a79e5cc9d1f6a1054d6be6731e3cd19abbd9e9b23309f87bfe51a822410a62

只给出了 c, n，只能够从 p, q 的关系入手。依据素数分布定律，\(next\_prime(k)-k\) 应该远小于 k，因而

\[q = \text{next\_prime}(p \oplus((1\ll 1024) -1)) \approx p \oplus((1\ll 1024) -1) \implies p \oplus q \approx ((1\ll 1024) -1)\]

也即 \(t = p\oplus q\) 的高位全为 1；关于低位，我们需要得知具体有多少位不可确认；依据有关素数间隙的研究，我进行了简单的测试：

Python
def exp():
    """
    随机测试可以发现 p^q 的高 1004 位基本都是 1
    """
    for _ in range(10):
        p = getStrongPrime(1024)
        q = next_prime(p ^ ((1<<1024)-1))
        pxq = p^q
        print(pxq.bit_length(), bin(pxq))

观察多轮随机测试输出可以发现，pxq 的高位基本全为 1 符合猜想；第一个不为 0 的数为 14 位，因此只需要对低 14 位（或者保险一点使用 15 位）进行遍历填充，使用 xor_factor 算法即可。但是，在实际操作中发现没能成功分解；即便之后找答案拿到了 p, q，异或后依旧失败。检查信息后发现 bug：

Python
def factor(n, p_xor_q):
    ...
    PRIME_BITS = int(math.ceil(math.log(n, 2)/2))
    ...
    for k in range(2, PRIME_BITS+1):
    ...

在这里，\(PRIME\_BITS =\lceil \frac{\log(n)}{2} \rceil\) 是 k 的上限，也即 p, q 的位数；但是作者没有考虑到 p, q 位数差别较大的情况（大概也就是题目的 anti fermat 的含义），这里就是如此：p.bit_length() == 1022, q.bit_length() == 1024, n.bit_length() == 2045，这导致 PRIME_BITS == 1023，故而始终无法求解。最简单的方法：

Python
PRIME_BITS = int(math.ceil(math.log(n, 2)/2)) + 1

就可以解题了。考虑如何修改的更加鲁棒，例如修改为

Python
PRIME_BITS = p_xor_q.bit_length()

在本题中有效，但是如果 p, q 的高位都全为 1 显然会出问题，因而将他们结合起来好了：

Python
PRIME_BITS = max(p_xor_q.bit_length(), int(math.ceil(math.log(n, 2)/2)))

让 AI 封装了一下，预计之后加入 pyPack 中去：

xor_factor.py
"""Utilities for factoring RSA moduli when p ⊕ q is known.

The implementation follows the branching technique described in ``algo.md`` and
adds a robust bit-length heuristic so that the search is deep enough even when
p and q do not have identical bit lengths.  The core entry point is
``factor_from_xor`` which returns the two prime factors in ascending order.

modified from https://github.com/sliedes/xor_factor/blob/master/xor_factor.py
to xxx by @darstib
"""

import math
from typing import Iterable, Optional, Tuple

__all__ = ["factor_from_xor", "recover_plaintext"]


def _check_congruence(k: int, p: int, q: int, n: int, xored: Optional[int]) -> bool:
    """Check p·q ≡ n (mod 2ᵏ) and optionally p ⊕ q ≡ xored (mod 2ᵏ)."""
    kmask = (1 << k) - 1
    p &= kmask
    q &= kmask
    n &= kmask
    product = (p * q) & kmask
    if product != n:
        return False
    if xored is not None and (p ^ q) != (xored & kmask):
        return False
    return True


def _extend_candidates(k: int, prefix: int) -> Iterable[int]:
    """Yield prefix and prefix with the k-th bit set."""
    kbit = 1 << (k - 1)
    assert prefix < kbit
    yield prefix
    yield prefix | kbit


def _compute_prime_bits(n: int, p_xor_q: int) -> int:
    """Heuristic for the expected prime bit length.

    We combine the classical ceil(log₂(n)/2) estimate with the concrete bit
    length of the xor hint and take the maximum to avoid under-estimating the
    required depth in edge cases (e.g. p ≈ q).
    """
    estimate_from_n = int(math.ceil(math.log(n, 2) / 2)) + 1
    estimate_from_xor = p_xor_q.bit_length()
    return max(estimate_from_n, estimate_from_xor)


def factor_from_xor(n: int, p_xor_q: int) -> Tuple[int, int]:
    """Recover the prime factors (p, q) of n given the xor hint.

    Returns the two primes in ascending order.  Raises ``ValueError`` if the
    search exhausts all candidates without success, which usually indicates the
    xor hint is incorrect or inconsistent with ``n``.
    """
    tracked = {
        (p, q)
        for p in (0, 1)
        for q in (0, 1)
        if _check_congruence(1, p, q, n, p_xor_q)
    }

    max_prime_bits = _compute_prime_bits(n, p_xor_q)

    for k in range(2, max_prime_bits + 1):
        new_candidates = set()
        for prefix_p, prefix_q in tracked:
            for candidate_p in _extend_candidates(k, prefix_p):
                for candidate_q in _extend_candidates(k, prefix_q):
                    cand_p, cand_q = sorted((candidate_p, candidate_q))
                    if _check_congruence(k, cand_p, cand_q, n, p_xor_q):
                        new_candidates.add((cand_p, cand_q))
        tracked = new_candidates
        if not tracked:
            break

    for p, q in tracked:
        if p not in (0, 1) and p * q == n:
            return (p, q) if p <= q else (q, p)

    raise ValueError("Failed to recover RSA factors; check the xor hint.")


def crack_from_xor(n: int, e: int, c: int, p_xor_q: int) -> bytes:
    """Recover the RSA plaintext given n, e, ciphertext c, and p ⊕ q."""
    from Crypto.Util.number import inverse

    p, q = factor_from_xor(n, p_xor_q)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    m = pow(c, d, n)
    hex_str = hex(m)[2:]
    if len(hex_str) % 2:
        hex_str = "0" + hex_str
    return bytes.fromhex(hex_str)

def _check():
    from Crypto.Util.number import getStrongPrime
    p = getStrongPrime(1024)
    q = getStrongPrime(1024)
    print("gold truth:", p, q)
    pq = p ^ q
    n = p * q
    p_, q_ = factor_from_xor(n, pq)
    assert p_ * q_ == n
    print("pass")
    return (p, q)

完整解题代码：

exp.py
from Crypto.Util.number import inverse
from xor_factor import factor_from_xor

e = 65537
n = 0x1ffc7dc6b9667b0dcd00d6ae92fb34ed0f3d84285364c73fbf6a572c9081931be0b0610464152de7e0468ca7452c738611656f1f9217a944e64ca2b3a89d889ffc06e6503cfec3ccb491e9b6176ec468687bf4763c6591f89e750bf1e4f9d6855752c19de4289d1a7cea33b077bdcda3c84f6f3762dc9d96d2853f94cc688b3c9d8e67386a147524a2b23b1092f0be1aa286f2aa13aafba62604435acbaa79f4e53dea93ae8a22655287f4d2fa95269877991c57da6fdeeb3d46270cd69b6bfa537bfd14c926cf39b94d0f06228313d21ec6be2311f526e6515069dbb1b06fe3cf1f62c0962da2bc98fa4808c201e4efe7a252f9f823e710d6ad2fb974949751
c = 0x60160bfed79384048d0d46b807322e65c037fa90fac9fd08b512a3931b6dca2a745443a9b90de2fa47aaf8a250287e34563e6b1a6761dc0ccb99cb9d67ae1c9f49699651eafb71a74b097fc0def77cf287010f1e7bd614dccfb411cdccbb84c60830e515c05481769bd95e656d839337d430db66abcd3a869c6348616b78d06eb903f8abd121c851696bd4cb2a1a40a07eea17c4e33c6a1beafb79d881d595472ab6ce3c61d6d62c4ef6fa8903149435c844a3fab9286d212da72b2548f087e37105f4657d5a946afd12b1822ceb99c3b407bb40e21163c1466d116d67c16a2a3a79e5cc9d1f6a1054d6be6731e3cd19abbd9e9b23309f87bfe51a822410a62


def get_pq(n):
    shift = 13
    for lowbit in range(2 ** shift - 1, -1, -1):
        t = (((1 << (1024 - shift)) - 1) << shift) + lowbit
        assert t.bit_length() == 1024
        try:
            p, q = factor_from_xor(n, t)
        except ValueError:
            p = q = None
        if lowbit % (1 << (shift // 2)) == 0:
            print(f"trying lowbit:, {bin(lowbit >> (shift // 2))} => {p, q}")
        if p and q and p * q == n:
            return p, q, t

    assert False, 'factors were not in tracked set. Is your p^q correct?'

def get_msg():     
    p, q, hint = get_pq(n)
    print(p, p.bit_length())
    print(q, q.bit_length())
    phi = (p-1) * (q-1)
    d = inverse(e, phi)
    m = pow(c, d, n)
    hex_m = hex(m)[2:]
    if len(hex_m) % 2:
        hex_m = '0' + hex_m
    msg = bytes.fromhex(hex_m)
    return msg

msg = get_msg()
print(msg.decode())
# +-----------------------------------------------------------+
# | zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d} |
# +-----------------------------------------------------------+
当然我上面的求解大概是一个非预期解，官方题解的思路是

考虑 q = next_prime(p ^ ((1<<1024)-1)) ≈ p^((1<<1024)-1) = (1<<2024) -p -1，带入 \(n = p*q\)，解得

\[ p\approx\frac{(1\ll1024)+\sqrt{(1\ll1024)^2-4n}}2 \]

求解后只是近似值，取 next_prime(p)，即可得到 p。

part p.xor.q

但如果我们 \(t = p \oplus q\) 的未知部分不适合爆破呢？看 starctf2022 - ezRSA ：

https://github.com/sixstars/starctf2022/blob/main/crypto-ezRSA/chall.py
from Crypto.Util.number import getStrongPrime
from gmpy import next_prime
from random import getrandbits
from flag import flag

p=getStrongPrime(1024)
q=next_prime(p^((1<<900)-1)^getrandbits(300))
n=p*q
e=65537

m=int(flag.encode('hex'),16)
assert m<n
c=pow(m,e,n)

print(hex(n))
#0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3

print(hex(c))
#0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1

只给出了 c, n，同样只能够从 p, q 的关系入手：由于

Python
p=getStrongPrime(1024)
q=next_prime(p^((1<<900)-1)^getrandbits(300))

我们可以得到的消息有（注意 python 中 ^ 是异或）：

  • p, q 均为 1024 位
  • \(t = p \oplus q\)
    • t 的高 124 位全为 0，即 p, q 高位相同，可以通过对 n 开方求得；
    • t 的中间 600 位全为 1，即 p, q 中间相反，考虑探索剪枝；这里的剪枝参考了官方题解，即先按照符合约束的情况进行初始化，随后从高位开始，用 \(p*q \leq n\) 来决定是否都要进行 bit 翻转（不过这应该仅限于 \(p \oplus q\) 对应 bit 位为 1 才可以使用）
    • t 的低 300 位随机，没有信息，等待使用 Known High Bits Attack 攻击。
exp.py
import gmpy2
from sage.all import *
e=65537
c = 0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
# 用 n 的高 248 位来进行开根
top_bits = int(gmpy2.isqrt(n>>(2048-248)))
assert top_bits.bit_length() == 124
# print("top_bits:", hex(top_bits))
p_ = (top_bits << 900) + (1<<900) -1
q_ = (top_bits << 900)
assert p_.bit_length() == q_.bit_length() == 1024
for i in range(899, 301, -1):
    bit = 1 << i
    if (p_^bit)*(q_^bit) <= n:
        # swap p_ & q_ bit
        p_^=bit
        q_^=bit

# print("p:", hex(p))
# print("q:", hex(q))
# 0xf376c68d76f4ab9b4d247852ef07159a09eeac920ac89148a8dee4f3c359a291b6bf03ab9258ca64783c416fcfeade13cf3c18a7677c29283c7fc6bfcdbba1d6fecbe9e243cc2e3ef0fe60035e1dbc727f3522bfab2bc28d5e29bfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
# 0xf376c68d76f4ab9b4d247852ef071595f611536df5376eb757211b0c3ca65d6e4940fc546da7359b87c3be90301521ec30c3e7589883d6d7c380394032445e290134161dbc33d1c10f019ffca1e2438d80cadd4054d43d72a1d64000000000000000000000000000000000000000000000000000000000000000000000000000
shift = 450 # 这个 shift 还挺重要的，多了少了都解不出来
p_ = p_ >> shift << shift
def get_pq(p_high, n):
    # print(hex(p_high))
    x = Zmod(n)['x'].gen()
    # x = PolynomialRing(Zmod(n), "x").gen()
    f=x+p_high
    roots=f.small_roots(X=2**shift,beta=0.4)
    if roots:
        p=int(f(roots[0]))
        assert n%p==0
        q = n//p
        return (p, q)
    return None

p, q = get_pq(p_, n)
phi = (p-1) * (q-1)
d = inverse_mod(e, phi)
m = power_mod(c, d, n)
print(bytes.fromhex(hex(m)[2:]))
# b'*CTF{St.Diana_pls_take_me_with_you!}'

RSA backdoor (4p-1 method)

攻击条件：\(4p-1 = Ds^2\) 其中 Ds 参见 cm_factorization 。

Private key attack

d leak

当对应的 (e,d) 泄露后，我们就能够分解对应的 N 。具体原理可见 ctf-wiki 。

rsatool calculates RSA (p, q, n, d, e) and RSA-CRT (dP, dQ, qInv) parameters given either two primes (p, q) or modulus and private exponent (n, d).

Question

cryptohack - Crossed Wires

Python
# rsatool 分解得到
p  = 0xbf7a6a86c980cbc7ff358a92b7b0828106b6ad75122c42b9c05cfb0f1b08205903e54381a323b3c2dfc6a6adb0771dbdf61185405ec7e1de5614cdfa71c6b5cd320d0a6bc40379592088a794b0ead8cc012a38ca57daaed140c42c634736eee8fe268bac6ab814b1e769dc1bade805160da940b0813b145df9b7a97e7ca4e0eb

q = 0xe5f0c56af9d879da10d5b7f09153716469faced27adf10a8c69847e2460767d316048b95087bf1102278ca070e2fb81ac367aae538980ad0cbd438ffac3673c9b8898a24209d896723a9b08e919a6cbfff761cb8218df0d1f6f56414ba245ad17581d96bca6679b3fa7a2a7d2306ad99c1749864cd85b3390aaddef33e8c73b9

n = p*q
phi = (p-1)*(q-1)
c = 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
friends_key = [...]
phi = (p-1)*(q-1)
from Crypto.Util.number import inverse, long_to_bytes
for key in friends_key[::-1]:
    e = key[1]
    d = inverse(e, phi)
    c = pow(c, d, N)
long_to_bytes(c) # b'crypto{3ncrypt_y0ur_s3cr3t_w1th_y0ur_fr1end5_publ1c_k3y}'

dp || dq leak attack

Definition

\(dp \equiv d\pmod{p-1}, dq \equiv d\pmod{q-1}\)

攻击条件：直到 dp 或者 dq，完整的公钥 (n,e) 和密文 c。 攻击原理：\(p = \frac{edp-1}{i}+1, i \in[1, e]\) ，推导省略，只要 p 是整数且整除 n 即符合条件：

demo_dp_leak
from Crypto.Util.number import getPrime
m = int.from_bytes(b'darctf{wow_leaking_dp_breaks_rsa?}')
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 0x10001
c = pow(m,e,n)
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
dp = d % (p-1)
print(dp, n, e, c)

"""solve"""
def dp_attack(dp, n, e):
    for i in range(1,e):
        if (dp*e-1)%i==0 and n%(((dp*e-1)//i)+1)==0:
            return ((dp*e-1)//i)+1

p = dp_attack(dp, n, e)
q = n//p
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))

dp && dq leak attack

攻击条件：知道 dp, dp, p, q, c。 攻击原理：crt 求解 d。

dpq_leak
from sage.all import crt

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

def dpq_attack(p,q,dp,dq):
    return crt([dp,dq],[p-1,q-1])
d = dpq_attack(p,q,dp,dq)
n=p*q
m=pow(c,d,n)
bytes.fromhex(hex(m)[2:])

dp && dq && dr leak attack

攻击条件：

\[ n = p*q*r, \begin{cases} dp = d\pmod{(q-1)*(r-1)} \\ dq = d\pmod{(p-1)*(r-1)} \\ dr = d\pmod{(p-1)*(q-1)} \end{cases}, 且已知 p,q,r,dp,dq,dr \]

还是一样的 crt？中国剩余定理要求模数互质；扩展中国剩余定理可以一定程度上解决这一问题（并非一定可行）

chall.py
"""
import gmpy2
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
e = getPrime(32)
print(e)
n = p*q*r
phi = (p-1)*(q-1)*(r-1)
d = gmpy2.invert(e,phi)
dp = d%((q-1)*(r-1))
dq = d%((p-1)*(r-1))
dr = d%((p-1)*(q-1))
flag = 'flag{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}'
m = bytes_to_long(flag.encode())
c = pow(m,e,n)

print(p)
print(q)
print(r)
print(dp)
print(dq)
print(dr)
print(c)
"""

from sage.all import crt, CRT_list, gcd

p=12922128058767029848676385650461975663483632970994721128398090402671357430399910236576943902580268365115559040908171487273491136108931171215963673857907721
q=10395910293559541454979782434227114401257890224810826672485874938639616819909368963527556812339196570118998080877100587760101646884011742783881592586607483
r=8104533688439480164488403019957173637520526666352540480766865791142556044817828133446063428255474375204188144310967625626318466189746446739697284656837499
dp=73360412924315743410612858109886169233122608813546859531995431159702281180116580962235297605024326120716590757069707814371806343766956894408106019058184354279568525768909190843389534908163730972765221403797428735591146943727032277163147380538250142612444372315262195455266292156566943804557623319253942627829
dq=40011003982913118920477233564329052389422276107266243287367766124357736739027781899850422097218506350119257015460291153483339485727984512959771805645640899525080850525273304988145509506962755664208407488807873672040970416096459662677968243781070751482234692575943914243633982505045357475070019527351586080273
dr=21504040939112983125383942214187695383459556831904800061168077060846983552476434854825475457749096404504088696171780970907072305495623953811379179449789142049817703543458498244186699984858401903729236362439659600561895931051597248170420055792553353578915848063216831827095100173180270649367917678965552672673
c=220428832901130282093087304800127910055992783874826238869471313726515822196746908777026147887315019800546695346099376727742597231512404648514329911088048902389321230640565683145565701498095660019604419213310866468276943241155853029934366950674139215056682438149221374543291202295130547776549069333898123270448986380025937093195496539532193583979030254746589985556996040224572481200667498253900563663950531345601763949337787268884688982469744380006435119997310653

计算模数间两两之间最大公因数，作为新的模数求解中国剩余定理：

solve1.py
M1 = (q - 1)*(r -1)
M2 = (p -1)*(r -1)
M3 = (p -1)*(q -1)

G12 = gcd(M1, M2)
G13 = gcd(M1, M3)
G23 = gcd(M2, M3)

# 检查同余方程是否有解
if (dp - dq) % G12 != 0 or (dp - dr) % G13 != 0 or (dq - dr) % G23 != 0:
    print("同余方程无解")
else:
    d = crt([dp, dq, dr], [M1, M2, M3])
    m = pow(c, d, p * q * r)
    print(bytes.fromhex(hex(m)[2:]))

sagemath 中内置了 CRT_list 方法可以求解模数不互质的情况：

solver2.py
d = CRT_list([dp,dq,dr],[(q-1)*(r-1),(p-1)*(r-1),(p-1)*(q-1)])
m = pow(c,d,p*q*r)
bytes.fromhex(hex(m)[2:]) # b'DASCTF{8ec820e5251db6e7a1758543a1123824}'

Wiener's Attack

维纳攻击适用于：e 较大，\(d< \frac{1}{3}N^{1/4}, q<p<2q\) 。

原理简述：由于 \(ed \equiv 1\pmod{\phi(n)} \implies ed = k*\phi + 1\) ，当 n 较大时，\(ed \approx k*\phi \approx k*n\implies \frac{e}{n} \approx \frac{k}{d}\) ；利用连分数从两侧逼近于极限值的特点，找到真正的 d & k ；甚至我们求解 \(\phi\) 后能够分解出 p/q 。

Extra

Legendre's theorem

如果存在 \(\alpha \in Q\), \(c,d \in Z\): \(|a- \frac{c}{d}|< \frac{1}{2d^2}\)，那么 \(\frac{c}{d}\) 就是 \(\alpha\) 的一个有理近似。

\(ed = k*\phi + 1 \implies | \frac{e}{\phi}- \frac{k}{d}|= \frac{1}{d*\phi}\)

大部分情况下，构成 \(n=p*q\) 公式中，p 与 q 的二进制长度相同，即有 \(p < q < 2*p\) （p q 可互换位置）；由适当推导可以得到 \(d< \frac{1}{3}N^{1/4} \implies (3d)^4 < n\)

攻击代码可以使用 crypto-attacks/attacks/rsa/wiener_attack.py ，下面是一个使用示例：

wiener_attack.py
import os
import sys

from sage.all import ZZ
from sage.all import continued_fraction

path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))
if sys.path[1] != path:
    sys.path.insert(1, path)

from attacks.factorization import known_phi

def attack(N, e):
    """
    Recovers the prime factors of a modulus and the private exponent if the private exponent is too small.
    :param N: the modulus
    :param e: the public exponent
    :return: a tuple containing the prime factors and the private exponent, or None if the private exponent was not found
    """
    convergents = continued_fraction(ZZ(e) / ZZ(N)).convergents()
    for c in convergents:
        k = c.numerator()
        d = c.denominator()
        if pow(pow(2, e, N), d, N) != 2:
            continue

        phi = (e * d - 1) // k
        factors = known_phi.factorize(N, phi)
        if factors:
            return *factors, int(d)

# set the value we need to know
n = 10117654819914858266933329374955416887632623769133893090370644563766857602175135282123557069130319485164837923640109707980173187311717714731455048711732890650502393864146567993461691536083330111489342144526034765633893707639465391971659424271400604010051260552831236934617979897198594708643604050329358522040572553492557329327193918343289526476096522685686128709365882540965089876020772451339243051387630968483513100881164719486794479191020450727996212211201807165531274853014517030221518336293845148545671493267736094904720639061287350709209363413742534108909427583009442175135992281621755221466312230819838164838443
e = 9821176723459156737162590528498355378679103255669217165700920581299681706733929195884953659518540987340485400582895899813962495604183457377106880733695051072483080763292039235986138262683331839202120494074112671026731661652894069539798773005571447249078493499067926710777981456836165288713067372341722891618455469381820299718375899142104630769808052209736800306823537530231432735329122809506084509365041929994661643608897946882821172042151091436805833261237973879388223150132281413026451714557979869417700194664385291198650864896408143681530963859508908402067374010247738488460155501935400209160082801993945408813513
c = 838279327100183842450828959704405383407020841408916285706333834213457887909003957632210005175559669378601653437817015283864372967567045814324446631403131762020243676699045950634510503063630325940620012467503745448306616066932850616255337850567483377961974904557893440882626053258665407295455129124436515237709284339335286446533668177967589716697626618148973094630870394728363810896842456940427809475399274556698585866672673971202275767545143765482579343055060966723452080734906835537296838390574697520016738791840483248208135607782781572593502322902003706653541803004568389346187087997006034664608287414331955367370
p, q, d = attack(n, e)
m = pow(c, d, n)
print(m)
print(bytes.fromhex(hex(m)[2:])) # b"SKSEC{Do_y0u_Kn0w_Wi3n3r's_4ttack}"

Example

Boneh and Durfee attack

攻击条件：\(d<N^{0.292}\)

先来看 cryptohack 上的 Everything is Still Big

task.py
#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long, inverse
from random import getrandbits
from math import gcd

FLAG = b"crypto{?????????????????????????????????????}"

m = bytes_to_long(FLAG)

def get_huge_RSA():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p*q
    phi = (p-1)*(q-1)
    while True:
        d = getrandbits(512)
        if (3*d)**4 > N and gcd(d,phi) == 1:
            e = inverse(d, phi)
            break
    return N,e


N, e = get_huge_RSA()
c = pow(m, e, N)

print(f'N = {hex(N)}')
print(f'e = {hex(e)}')
print(f'c = {hex(c)}')

很特别的要求 (3*d)**4 > N ，把 Wiener-attack 禁用了；但是有更强的攻击 Boneh and Durfee attack (\(d<N^{0.292}\))

final.py
d = 4405001203086303853525638270840706181413309101774712363141310824943602913458674670435988275467396881342752245170076677567586495166847569659096584522419007
N = 0xb12746657c720a434861e9a4828b3c89a6b8d4a1bd921054e48d47124dbcc9cfcdcc39261c5e93817c167db818081613f57729e0039875c72a5ae1f0bc5ef7c933880c2ad528adbc9b1430003a491e460917b34c4590977df47772fab1ee0ab251f94065ab3004893fe1b2958008848b0124f22c4e75f60ed3889fb62e5ef4dcc247a3d6e23072641e62566cd96ee8114b227b8f498f9a578fc6f687d07acdbb523b6029c5bbeecd5efaf4c4d35304e5e6b5b95db0e89299529eb953f52ca3247d4cd03a15939e7d638b168fd00a1cb5b0cc5c2cc98175c1ad0b959c2ab2f17f917c0ccee8c3fe589b4cb441e817f75e575fc96a4fe7bfea897f57692b050d2b
c = 0xa3bce6e2e677d7855a1a7819eb1879779d1e1eefa21a1a6e205c8b46fdc020a2487fdd07dbae99274204fadda2ba69af73627bdddcb2c403118f507bca03cb0bad7a8cd03f70defc31fa904d71230aab98a10e155bf207da1b1cac1503f48cab3758024cc6e62afe99767e9e4c151b75f60d8f7989c152fdf4ff4b95ceed9a7065f38c68dee4dd0da503650d3246d463f504b36e1d6fafabb35d2390ecf0419b2bb67c4c647fb38511b34eb494d9289c872203fa70f4084d2fa2367a63a8881b74cc38730ad7584328de6a7d92e4ca18098a15119baee91237cea24975bdfc19bdbce7c1559899a88125935584cd37c8dd31f3f2b4517eefae84e7e588344fa5

m = pow(c, d, N)
print(bytes.fromhex(hex(m)[2:])) # b'crypto{bon3h5_4tt4ck_i5_sr0ng3r_th4n_w13n3r5}'

Coppersmith's relative attack

Håstad's broadcast attack

发送方将一份明文进行多份（份数 k > e）加密，每份使用不同的 n（如 \(n_{1}, n_{2}, \dots\)），显然可以使用中国剩余定理解出 \(c = m^e\pmod{n_{1}*n_{2}*\dots}\)；而显然 m < n1 & m < n2 & ... ，所以当 e 的值小于等于我们获得的密文数量，就会有 \(m^e \leq \Pi_{i=0}^{k}n_{i}\) ，此时直接开根就好了。一般来说，这个 e 等于 3。

broadcast attack
from sage.all import *
msg = [{'c':xxx, 'e':xxx, n:xxx}, ...] # 字典列表
# 提取所有的n和c
length = len(msg)
ns = [msg[i]["n"] for i in range(length)]
cs = [msg[i]["c"] for i in range(length)]

# 使用CRT求解m^length
m_power = crt(cs, ns)
m = int(m_power.nth_root(length))

flag = bytes.fromhex(hex(m)[2:]).decode()
print(flag)

如果是很多组 (n, e, c) 中，部分对应明文相同，可以改为下面的代码：

Python
from sage.all import *
from itertools import combinations
max_length = len(ns)
for l in range(e, max_length+1):
    for comb in combinations(range(max_length), l):
        ncs = [cs[i] for i in comb]
        nns = [ns[i] for i in comb]
        m_power = crt(ncs, nns)
        try:
            m = int(m_power.nth_root(e))
            pt = bytes.fromhex(hex(m)[2:])
            if b'flag' in pt:
                print(pt)
                print(comb)
        except:
            continue

攻击条件：使用同一公钥 (n, e) 线性填充加密同一密文 m 两次，获得两个密文 c1 c2:

related-message
class Challenge:
    def __init__(self):
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.N = self.p * self.q
        self.e = 11

    def pad(self, flag):
        m = bytes_to_long(flag)
        a = random.randint(2, self.N)
        b = random.randint(2, self.N)
        return (a, b), a * m + b

    def encrypt(self, flag):
        pad_var, pad_msg = self.pad(flag)
        encrypted = (pow(pad_msg, self.e, self.N), self.N)
        return pad_var, encrypted
\[ 构造两个多项式\begin{cases} p_1(x)=(a_1x+b_1)^e-c_1\quad\mathrm{mod~}N\\ p_2(x)=(a_2x+b_2)^e-c_2\quad\mathrm{mod~}N \end{cases} \]

不难发现二者都有 (x-m) 这一因式，提取出来后求解即可得到 m。

Question

cryptohack - Bespoke Padding

Coppersmith’s short-pad attack

[todo]

Known High Bits Attack

利用 sagemath 调用的 coppersmith 算法求解小根。

  • 攻击条件：已知 N 的一个素数 p/q 的高位或者是明文的高位；
  • 攻击方式：构造多项式，调用 sagemath 求解。
known_bits
from sage.all import *
from Crypto.Util.number import getPrime
m1 = int.from_bytes(b'darctf{p_high_bits_leak}')
m2 = int.from_bytes(b'darctf{m_high_bits_leak}')
e1 = 65537
e2 = 11
print(f"e2 = {e2}")
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c1 = pow(m1, e1, n)
c2 = pow(m2, e2, n)
print(f'n = {n}')
print(f"e = {e}")

""" Known High Bits Message Attack """
shift1 = 128
p_high = p >> shift1 << shift1
print(f"p_high = {p_high}")
print(f'c1 = {c1}')

""" Factoring with High Bits Known """
shift2 = 128
m_high = m2 >> 128 << 128
print(f"m_high = {m_high}\n{bytes.fromhex(hex(m_high)[2:])}")
print(f'c2 = {c2}')

"""solve"""
x = Zmod(n)['x'].gen()
""" part 1 """
# x1 = p-p_high => x1+p_higt % p == 0
f1 = x + p_high
root1 = f1.small_roots(X=2**shift1, beta=0.4)
for root in root1:
    root = int(root)
    if n % (root + p_high) == 0:
        p = root + p_high
        q = n // p
        break
d1 = pow(e1, -1, (p-1)*(q-1))
print(bytes.fromhex(hex(pow(c1, d1, n))[2:]))
""" part 2 """
# x2 = m-m_high => x2+m_high = m => (x2+m_high)^e - c2 == 0
f2 = (x + m_high)**e2 - c2
root2 = f2.small_roots(X=2**shift2, beta=0.4)
if root2:
    for root in root2:
        print(bytes.fromhex(hex(root+m_high)[2:]))
else:
    print("No root found")

Known Low Bits Attack

p/m low bits

known low bits
from sage.all import *
from Crypto.Util.number import getPrime
p, q = getPrime(1024), getPrime(1024)
n = p*q
print(f"n = {n}")

""" known p low bits """
m1 = int.from_bytes(b'darctf{p_low_bits_leak}')
shift1 = 128
p_low = p & ((1 << shift1)-1)
e1 = 0x10001
c1 = pow(m1, e1, n)
print(f"e1 = {e1}")
print(f"c1 = {c1}")
print(f"p_low = {p_low}")
len_p = len(bin(p))
print(f'len(bin(p)) = {len_p}')

""" known m low bits """
m2 = int.from_bytes(b'darctf{m_low_bits_leak}')
shift2 = 128
m_low = m2 & ((1 << shift2)-1)
e2 = 11
c2 = pow(m2, e2, n)
len_m = len(bin(m2))
print(f"e2 = {e2}")
print(f"c2 = {c2}")
print(f"len(bin(m2)) = {len_m}")
print(f'm_low = {m_low}')

""" solve """
x = PolynomialRing(Zmod(n), 'x', implementation="NTL").gen()
""" part p """
# x1* 1<<shift1 = p-p_lo2 => (x1**shift1 + p_low) % p == 0
f1 = (x*(1<<shift1) + p_low - n).monic()
root1 = f1.small_roots(X=2**(len_p-2-shift1), beta=0.4)
if root1:
    for root in root1:
        root = int(root*(1 << shift1))
        p = root + p_low
        q = n // p
        d1 = pow(e1, -1, (p-1)*(q-1))
        print(bytes.fromhex(hex(pow(c1, d1, n))[2:]))
        break
else:
    print('root1 not found')


""" part m """
# x2* 1<<shift2 = m-m_low => (x2**shift2 + m_low)**e - c == 0
f2 = (((1 << shift2) * x + m_low)**e2 - c2).monic()
root2 = f2.small_roots(X=2**(len_m-2-shift2), beta=0.5)
if root2:
    for root in root2:
        root = int(root*(1 << shift2))
        print(bytes.fromhex(hex(root + m_low)[2:]))
        break
else:
    print('root2 not found')

d low bits

一个复杂一些的例子是知道 d 的部分低位。 Boneh,Durfee,Frankel 指出：只要 \(e < \sqrt{ N }\) 并且给定了 d 的 \(\left\lceil \frac{d}{4} \right\rceil\) 的低位，就可以从中恢复出 d 。下面是一个例子：

baby-lifting
# https://ctf.xidian.edu.cn/training/10?challenge=147
from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 0x1001
d = inverse(e, (p-1)*(q-1))
bit_leak = 400
d_leak = d & ((1<<bit_leak)-1)
msg = bytes_to_long(flag)
cipher = pow(msg,e,n)
pk = (n, e)

with open('output.txt','w') as f:
    f.write(f"pk = {pk}\n")
    f.write(f"cipher = {cipher}\n")
    f.write(f"hint = {d_leak}\n")
    f.close()

# pk = (53282434320648520638797489235916411774754088938038649364676595382708882567582074768467750091758871986943425295325684397148357683679972957390367050797096129400800737430005406586421368399203345142990796139798355888856700153024507788780229752591276439736039630358687617540130010809829171308760432760545372777123, 4097)
# cipher = 14615370570055065930014711673507863471799103656443111041437374352195976523098242549568514149286911564703856030770733394303895224311305717058669800588144055600432004216871763513804811217695900972286301248213735105234803253084265599843829792871483051020532819945635641611821829176170902766901550045863639612054
# hint = 1550452349150409256147460237724995145109078733341405037037945312861833198753379389784394833566301246926188176937280242129

按照前面的思路，我们期望构造一个方程并求根；但是难点在于我们几乎无法利用已有信息直接构造一个只有 d 未知的方程；我们唯一知道的是 \(d*e \equiv 1 \pmod{\phi(n)}\)；但是同样困于 \(\phi(n)\) 未知。尝试过将 \(\phi(n) \approx n\) 直接求解，失败。

在这里解给出的思路是：考虑前面我们已知 p/m 的低位可以求解；能否从 d 的低位搞到 p 的低位？

我们知道 \(x^{2} - (p+q)x + p*q = 0\) 的根为 p 和 q，在取模的条件下依旧成立，\(pq = n\)，故而重点转向 \(p+q\)。

我们知道，\(\phi(n) = (p-1)(q-1) = n+1 - (p+q) \implies x^{2}-(n+1-\phi(n))x + n = 0\) 。

记 \(l = 2^{bit\_leak}\)，有

\[ \begin{align} &de = 1 + k \phi(n) \implies d_{l}e = 1 + k\phi(n)\pmod{t} \\ \implies &kx^{2} + (d_{l}e - 1 - k(n+1))x + kn = 0 \pmod{t} \end{align} \]

因为 \(d< \phi(n) \implies e > k\)，暴力搜索有：

Python
from sage.all import *
from Crypto.Util.number import *
n = 53282434320648520638797489235916411774754088938038649364676595382708882567582074768467750091758871986943425295325684397148357683679972957390367050797096129400800737430005406586421368399203345142990796139798355888856700153024507788780229752591276439736039630358687617540130010809829171308760432760545372777123
e = 4097
cipher = 14615370570055065930014711673507863471799103656443111041437374352195976523098242549568514149286911564703856030770733394303895224311305717058669800588144055600432004216871763513804811217695900972286301248213735105234803253084265599843829792871483051020532819945635641611821829176170902766901550045863639612054
d_l = 1550452349150409256147460237724995145109078733341405037037945312861833198753379389784394833566301246926188176937280242129
blk = 400

def get_p_lows(d_l, n, e):
    for k in range(645, e+1): # 理应从 1 开始，这里知道结果后才从 645 开始
        print(f"trying {k}/{e}")
        p = var('p')
        eq = (k* p**2 + (e*d_l - k*(n+1) - 1) * p + k * n == 0)
        p_l = solve_mod([eq], 1<<blk)
        if len(p_l) > 0:
            yield [int(pl[0]) for pl in p_l], k
    return None
Sagemath 9.3 + Python 3.9

尝试过使用多项式环上的 small_roots 直接求解方程，失败。

起初一直用的是较新版本的 sagemath 10.6 + python 3.11，这在执行 solve_mod 时会出现错误：

Text Only
OverflowError: Python int too large to convert to C long
Exception ignored in: 'sage.libs.singular.singular.sa2si_ZZmod'
Traceback (most recent call last):
  File ".../python3.11/site-packages/sage/symbolic/relation.py", line 1701, in <genexpr>
    ans = list(t for t in possibles if all(e(*t) == 0 for e in eqns_mod))
                                           ^^^^^
OverflowError: Python int too large to convert to C long

再用上面的已知 p 低位的思路求 p

Python
def get_full_p(p_low, n):
    p_h = PolynomialRing(Zmod(n), "p_h", implementation='NTL').gen()
    p = p_h * (1 << blk) + p_low
    f = (p-n).monic()
    phs = f.small_roots(X=(1 << (512//4)), beta=0.4)
    if phs:
        return int(p(phs[0]))
    return None

组合之下我们得到

solution.py
def get_full_d(d_l, n, e):
    for p_lows, k in get_p_lows(d_l, n, e):
        # print("p_lows:",p_lows)
        for low_p in p_lows:
            p = get_full_p(low_p, n)
            if p:
                print("p:", p)
                q = n // p

                if p * q == n:
                    d = inverse_mod(e, (p-1)*(q-1))
                    return d
                else:
                    print("p * q != n")
                    continue
    return None

d = get_full_d(d_l, n, e)
if d:
    print("d:", d)
    m = pow(cipher, d, n)
    print("flag:", long_to_bytes(int(m)))
else:
    print("d not found")

# trying 645/4097
# trying 646/4097
# trying 647/4097
# trying 648/4097
# trying 649/4097
# trying 650/4097
# p: 7458062461956620112301588229071392126780346788859113209375105494626101265308095322117111641306328357294968229324362505235806688414035133488417611167744319
# d: 8453400612258125070836799610286958177590958703862612176480299487127355057097473419454243973552176419700567840361653614387706247105682797730958892608765553970954948853164478455048360634740571200591660362044055606841746827568729277784053763456603113675706647429943809231549106428652993256853303236680813806033
# flag: b'moectf{7h3_st4rt_0f_c0pp3rsmith!}'

Return of Coppersmith's attack (ROCA)

攻击条件：fast primes

起源于 cryptohack 上的 "Fast Primes"，当然去搜 Fast Primes 也能找到这个攻击（方便和安全总是难以兼得的），具体下面的文章讲的很清楚了，推荐攻击脚本如下，自己有能力写一个更好。

Note

其他

Optimal asymmetric encryption padding (OAEP)

https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding

参考资料

  1. 可能是由于两次使用的 n 不同，m 所在的有限域不同导致的（猜测）。 ↩↩

  2. <= 表示的是赋值，并非 ≤ 。 ↩

评论