iscc2024 钢铁侠

Posted on Edited on

题目给了一张图片和一个文档

1
2
3
4
5
N = 14333611673783142269533986072221892120042043537656734360856590164188122242725003914350459078347531255332508629469837960098772139271345723909824739672964835254762978904635416440402619070985645389389404927628520300563003721921925991789638218429597072053352316704656855913499811263742752562137683270151792361591681078161140269916896950693743947015425843446590958629225545563635366985228666863861856912727775048741305004192164068930881720463095045582233773945480224557678337152700769274051268380831948998464841302024749660091030851843867128275500525355379659601067910067304244120384025022313676471378733553918638120029697
e = 52595
a=1
[message]iscc
[message]good

图片可以使用 工具获取到密文

1
2
C1: 4251903765968182205638908124165687238668595287571695511358978749873732873567860053619635513706860629805773126702224204954306825755589324527464790716772532623787179556779775087369588999862023585439168942061748409955378083217107531514314050827416670183525480868721628196105159997017084027522785400780651513529661262069204074033252051284855308622003846532448135219496999884685163059589703767874228257837954982643722710776540927585288400564462843552764511294609144617545553527647537299951955033541729951576068083284279065679857225030596781834329220650727813085463111501010998877779379864147619708358818420859785907336293
C2: 8652219787553412127601941528212017576098133196802085027604475060672278379988273545329405203612107212771733843136763932156007146129306573507760169626091904302095339258863341911835040303242423006614835350839679118200861479940083644832881720989339738452547780463280352261286061553665126797236780242329554823680909487948300712962538437221930008085724150453712710185732400735474076046701955231528898382329666595016341771130260269344935757268710436239067282393248741660212602429247531170428187411577043376629797117349461201639740465095162144118572609292823960045382400389323999257936694442545038913004649289710891071782719

之后，我们可以通过顿悟编写脚本得到flag

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from Crypto.Util.number import *
import sys

n = 14333611673783142269533986072221892120042043537656734360856590164188122242725003914350459078347531255332508629469837960098772139271345723909824739672964835254762978904635416440402619070985645389389404927628520300563003721921925991789638218429597072053352316704656855913499811263742752562137683270151792361591681078161140269916896950693743947015425843446590958629225545563635366985228666863861856912727775048741305004192164068930881720463095045582233773945480224557678337152700769274051268380831948998464841302024749660091030851843867128275500525355379659601067910067304244120384025022313676471378733553918638120029697
e = 52595
c1 = 4251903765968182205638908124165687238668595287571695511358978749873732873567860053619635513706860629805773126702224204954306825755589324527464790716772532623787179556779775087369588999862023585439168942061748409955378083217107531514314050827416670183525480868721628196105159997017084027522785400780651513529661262069204074033252051284855308622003846532448135219496999884685163059589703767874228257837954982643722710776540927585288400564462843552764511294609144617545553527647537299951955033541729951576068083284279065679857225030596781834329220650727813085463111501010998877779379864147619708358818420859785907336293
c2 = 8652219787553412127601941528212017576098133196802085027604475060672278379988273545329405203612107212771733843136763932156007146129306573507760169626091904302095339258863341911835040303242423006614835350839679118200861479940083644832881720989339738452547780463280352261286061553665126797236780242329554823680909487948300712962538437221930008085724150453712710185732400735474076046701955231528898382329666595016341771130260269344935757268710436239067282393248741660212602429247531170428187411577043376629797117349461201639740465095162144118572609292823960045382400389323999257936694442545038913004649289710891071782719
m1 = bytes_to_long("iscc".encode())
m2 = bytes_to_long("good".encode())
P.<x> = PolynomialRing(Zmod(n))

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

sys.setrecursionlimit(500000)
f = (x + m1)^e - c1
g = (x + m2)^e - c2
res = GCD(f, g)
print(long_to_bytes(int(-res.monic().coefficients()[0])))

reference：

[网上脚本1][https://github.com/rkm0959/rkm0959_implements/blob/main/Half_GCD/code.sage]

[网上脚本2][https://github.com/ValarDragon/CTF-Crypto/blob/master/RSA/FranklinReiter.sage]

[P19.sage Franklin-Reiter攻击脚本][https://note.shenghuo2.top/01RSA%E5%9F%BA%E7%A1%80%E7%AF%87/P19.Franklin-Reiter%E6%94%BB%E5%87%BB%E8%84%9A%E6%9C%AC/]

[Franklin-Reiter相关消息攻击][https://blog.csdn.net/XiongSiqi_blog/article/details/130978226]

[相关信息攻击-Franklin-Reiter][https://blog.csdn.net/m0_74345946/article/details/132888197]