新生赛好玩

Cry_01.Twin Orbit / 双轨加密

题目： Cry_01.Twin Orbit / 双轨加密62 pts

Flag 格式：flag{…} ZeroG 空间站的两个轨道通信模块使用了同一个 RSA 模数 n。 工程师为了“安全隔离”，给两个模块设置了不同的公钥指数： e1 = 65537 e2 = 17 他们认为： “指数不同，密文不同，应该不会出问题。” 但 Fen 发现，两条通信轨道传输的是同一份核心指令。

请恢复明文，得到 flag。

两个 RSA 公钥使用了相同的 n。

如果 gcd(e1, e2) = 1，可以尝试扩展欧几里得。

注意处理负指数，可以使用模逆。

附件：

1
2
3
4
5
6
n = 78429219359517922271023478963814594552681246043944770910304760471867765174623304038843626799213010074714647155283331308571847776870166597053823412781788611608177305819593874012686298378748721435009046767613360191457980203020570462985478543330425482286818857391023923223033155751757576833456411434713984471383
e1 = 65537
e2 = 17
c1 = 71282312105868131740394478794008286284074152062907735987516077413351604126882776234623911447307962528308126218712123568701353026231889282844009867916343556840839139885445525543186695511199429927944296268193188530317628821728534582820389657490317666947095834711636160892093284048993666399747630728635978820198
c2 = 70751964066395185933408819650408191047287659276501425712138199434404000627978244880544478152411510337684996008892030606559772725285766060014956720285732207231186134371296910276169402781919701351782279058927891124229021162906608266092058475936622126108377526917909078829421351716554783863514592590874754685769

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from Crypto.Util.number import bytes_to_long

def encrypt_message(flag: bytes, n: int):
    m = bytes_to_long(flag)

    e1 = 65537
    e2 = 17

    c1 = pow(m, e1, n)
    c2 = pow(m, e2, n)

    return e1, e2, c1, c2

思路：

RSA共模攻击

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
import gmpy2
n = 78429219359517922271023478963814594552681246043944770910304760471867765174623304038843626799213010074714647155283331308571847776870166597053823412781788611608177305819593874012686298378748721435009046767613360191457980203020570462985478543330425482286818857391023923223033155751757576833456411434713984471383
e1 = 65537
e2 = 17
c1 = 71282312105868131740394478794008286284074152062907735987516077413351604126882776234623911447307962528308126218712123568701353026231889282844009867916343556840839139885445525543186695511199429927944296268193188530317628821728534582820389657490317666947095834711636160892093284048993666399747630728635978820198
c2 = 70751964066395185933408819650408191047287659276501425712138199434404000627978244880544478152411510337684996008892030606559772725285766060014956720285732207231186134371296910276169402781919701351782279058927891124229021162906608266092058475936622126108377526917909078829421351716554783863514592590874754685769

s,s1,s2=gmpy2.gcdext(e1,e2)
m=(pow(c1,s1,n)*pow(c2,s2,n)%n)
print(long_to_bytes(m))

flag{ZeroG_common_modulus_attack}

Cry_02.Lunar LCG / 月面伪随机

题目：

Flag 格式：flag{…} ZeroG 月面中继站使用一个轻量级伪随机数发生器生成通信密钥流。 开发人员说： “我们没有直接使用固定密钥，而是每次用随机数发生器生成密钥流，应该足够安全。” Fen 查看遥测日志后发现，中继站在加密前泄露了几次连续的 PRNG 状态。

请分析附件，恢复密钥流并解出 flag。

这是一个线性同余生成器 LCG。

如果知道连续的 state，可以恢复参数 a 和 c。

LCG 满足 state[i+1] = a * state[i] + c mod m。

附件：

1
2
3
4
5
6
7
8
9
10
11
m = 170141183460469231731687303715884105727
leak_states = [
    48077378362307815584689819960136019875,
    100310108693164117002347749113390493183,
    145646689101109657050476193569066602802,
    63949818470656288394594660187785964270,
    46314465195318558087862397882705709486,
    103138436636073932218183299598776830813,
]
ciphertext = 39fe07de62fdc9bf74bbbcbd7e202386ca9e40451b46c74968e30fff138a95

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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

class LunarLCG:
    def __init__(self, m, a, c, state):
        self.m = m
        self.a = a
        self.c = c
        self.state = state

    def next_state(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state

    def next_byte(self):
        """
        The relay station uses the lowest 8 bits of each new state
        as one byte of keystream.
        """
        return self.next_state() & 0xff

def xor_encrypt(data: bytes, prng: LunarLCG) -> bytes:
    out = bytearray()

    for b in data:
        k = prng.next_byte()
        out.append(b ^ k)

    return bytes(out)

思路：

中继站将每个新状态的最低8位作为一个字节的密钥流使用

LGC递推公式：

1
state_{n+1} = (a * state_n + c) % m
  • m 已知（梅森素数 2^127 - 1）
  • 有 6 个连续的泄露状态 leak_states
  • a 和 c 未知，

先求解a，c

1
2
s1 = a*s0 + c  (mod m)
s2 = a*s1 + c  (mod m)
1
2
3
s2 - s1 = a*(s1 - s0)  (mod m)
a = (s2 - s1) * inverse(s1 - s0, m)  (mod m)
c = s1 - a*s0  (mod m)

爆破获取seed，泄露的leak_states只有六个

EXP:

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
import gmpy2
m = 170141183460469231731687303715884105727
leak_states = [
    48077378362307815584689819960136019875,
    100310108693164117002347749113390493183,
    145646689101109657050476193569066602802,
    63949818470656288394594660187785964270,
    46314465195318558087862397882705709486,
    103138436636073932218183299598776830813,
]
ciphertext = bytes.fromhex(
    "39fe07de62fdc9bf74bbbcbd7e202386ca9e40451b46c74968e30fff138a95"
)

s0,s1,s2=leak_states[0],leak_states[1],leak_states[2]
#恢复a，c
a=(s1-s2)*gmpy2.invert(s0-s1,m)
c=(s1-a*s0)%m

#爆破seed
for i,seed in enumerate(leak_states):
    state=seed
    plain=bytearray()
    for b in ciphertext:
        state=(a*state+c)%m
        plain.append(b^(state&0xff))
    #判断是否可编译
    if all(0x20 <= x < 0x7f for x in plain):
        print(f"[+] flag (seed=leak[{i}]): {plain.decode()}")
        break
    else:
        print("no flag")

#flag (seed=leak[5]): flag{ZeroG_lcg_stream_recovery}

Cry_03.Phobos Padding / 火卫一填充

题目：

Flag 格式：flag{…} ZeroG 火卫一通信节点为了提高广播效率，将同一份核心指令发送给了三个不同的接收端。 每个接收端都有不同的 RSA 模数 n，但为了“加速加密”，工程师统一使用了很小的公钥指数： e = 3 工程师声称： “每个接收端的 n 都不同，所以同一条消息广播三次也没关系。” Fen 看到加密脚本后只说了一句： “没有 padding 的广播，就像没有隔热层的返回舱。”

请从附件中恢复明文，得到 flag。

相同明文被使用 e = 3 加密到了三个不同模数下。

尝试使用中国剩余定理合并三个密文。

如果 m^3 小于 n1 * n2 * n3，那么 CRT 后可以直接开整数三次方。

附件：

1
2
3
4
5
6
7
8
9
10
11
12
e = 3

n1 = 9203118261705868019110006623273896134322296004495934622126321588206198211590594608536574205500841860912183113474492528101942483463604127057100041845594123
c1 = 225326225723570437926892098700724301640108952320044616725184090895511961737080288471190011942447422341235122945729017303171992927231675218640713872178033

n2 = 8218974785294030613346971087108222043759818458429043768635262660088269400867661193359046399568686339887944628791712180696779799918022646158973494803220299
c2 = 3407676048044393024576659577470571794093695115844258472643168272782162860244002027327745232045383478691907846926814490953793141526176684717238078901972654

n3 = 8640442409248695297781745462901828098989267118787634310572918885729221856234292677073935037333836295724444289085611427540896246989248186559475612627680863
c3 = 6492260343134932927953198433174002823828534869771319070490239692685600132982822403083735209163800494671140850876058194194328293660168048521787716473266503


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
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from Crypto.Util.number import bytes_to_long

def encrypt(flag: bytes, public_keys):
    """
    public_keys:
        [
            (n1, e),
            (n2, e),
            (n3, e),
        ]

    Warning:
        This demo intentionally uses raw RSA without padding.
    """
    m = bytes_to_long(flag)

    result = []

    for n, e in public_keys:
        c = pow(m, e, n)
        result.append((n, e, c))

    return result

思路：

第一眼以为是小e攻击就可以但是没跑出来，就用广播攻击吧

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
import gmpy2
from Crypto.Util.number import *
e = 3

n1 = 9203118261705868019110006623273896134322296004495934622126321588206198211590594608536574205500841860912183113474492528101942483463604127057100041845594123
c1 = 225326225723570437926892098700724301640108952320044616725184090895511961737080288471190011942447422341235122945729017303171992927231675218640713872178033

n2 = 8218974785294030613346971087108222043759818458429043768635262660088269400867661193359046399568686339887944628791712180696779799918022646158973494803220299
c2 = 3407676048044393024576659577470571794093695115844258472643168272782162860244002027327745232045383478691907846926814490953793141526176684717238078901972654

n3 = 8640442409248695297781745462901828098989267118787634310572918885729221856234292677073935037333836295724444289085611427540896246989248186559475612627680863
c3 = 6492260343134932927953198433174002823828534869771319070490239692685600132982822403083735209163800494671140850876058194194328293660168048521787716473266503


def GCRT(mi,ai):
    assert(isinstance(mi,list)and isinstance(ai,list))
    curm,cura=mi[0],ai[0]
    for(m,a) in zip(mi[1:],ai[1:]):
        d=gmpy2.gcd(curm,m)
        c=a-cura
        assert(c%d==0)#不成立则不纯在解
        K=c//d*gmpy2.invert(curm//d,m//d)
        cura+=curm*K
        curm=curm*m//d
    return cura%curm

n=[n1,n2,n3]
c=[c1,c2,c3]

p=GCRT(n,c)
print(p)
m, t = gmpy2.iroot(int(p), e)
if t:
    print(m)
    print(long_to_bytes(int(m)))

flag{ZeroG_hastad_broadcast_attack}