STARTER

忘记每道题保存了，就直接全部粘贴过来了

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
from gmpy2 import *
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

class Point:
    def __init__(self,x,y=None):
        if y is None:
            self.x = x[0]
            self.y = x[1]
        else:
            self.x = x
            self.y = y
    def set(self,po):
        self.x = po[0]
        self.y = po[1]
    
    
    def __eq__(self, other):
        if isinstance(other, Point):
            return self.x == other.x and self.y == other.y
        return False
    
    def mod(self,m):
        self.x = self.x % m
        self.y = self.y % m
        return self

    def __getitem__(self, index):
        if index == 0:
            return self.x
        elif index == 1:
            return self.y
        else:
            raise IndexError("Index out of range")
    def __str__(self):
        return str([self.x,self.y])
def PointAdd(P,Q):
    #点加实现
    if P==Point([0,0]):
        return Q.mod(mod)   
    elif Q==Point([0,0]):
        return P.mod(mod)
    else:
        if P[0]==Q[0]and P[1]==-Q[1]:
            return Point([0,0])
        if P==Q:
            lm=(3*pow(P[0],2,mod)+a)*gmpy2.invert(2*P[1]%mod,mod)%mod
        else:
            lm=(P[1]-Q[1])%mod*gmpy2.invert((P[0]-Q[0])%mod,mod)%mod
        x1=int((lm**2-P[0]-Q[0])%mod)
        y1=int((lm*(P[0]-x1)-P[1])%mod)
        return Point([x1,y1])

def num_mul(P,k):
    #标量乘法
    sum = Point(0,0)
    add=P
    
    for b in bin(k)[2:][::-1]:
        if b == '1':
            sum = PointAdd(sum, add)
        add= PointAdd(add, add)

    return sum

def getY(x,p):
    if pow(x**3+497*x+1768,(p-1)//2,p)==1:
        return pow(x**3+497*x+1768,(p+1)//4,p)
    else:
        print("no y")

mod=9739
a=497
b=1768
G=Point(1804,5368)
n=6534
x=4726

y=getY(x,mod)
s=num_mul(Point(x,y),n)
print(s)

"""
P = Point(815, 3190)
Q=num_mul(P, 1829)
print(Q)

x=str(Q[0])
sha1=hashlib.sha1()
sha1.update(x.encode())
print(sha1.hexdigest())"""


还有题目给出的解密代码。

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.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib


def is_pkcs7_padded(message):
    """
    检查给定的消息是否使用PKCS#7填充。
    参数:
    message: 要检查的字节字符串消息。
    返回值:
    如果消息是使用PKCS#7填充的 则返回True 否则返回False。
    """
    padding = message[-message[-1]:]  # 从消息末尾提取填充字符
    return all(padding[i] == len(padding) for i in range(0, len(padding)))


def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
    """
    使用提供的共享密钥、初始化向量和密文解密标志
    参数:
    shared_secret: 用于生成AES密钥的共享密钥。
    iv: 加密时使用的初始化向量（字符串，十六进制表示）。
    ciphertext: 要解密的密文（字符串，十六进制表示）。
    返回值:
    解密后的明文字符串。如果明文使用PKCS#7填充 则移除填充；否则原样返回。
    """
    # 从共享密钥生成AES密钥
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]  # 取SHA1摘要的前16字节作为AES密钥

    # 解密密文
    ciphertext = bytes.fromhex(ciphertext)  # 将十六进制密文转换为字节
    iv = bytes.fromhex(iv)  # 将十六进制初始化向量转换为字节
    cipher = AES.new(key, AES.MODE_CBC, iv)  # 创建AES解密器
    plaintext = cipher.decrypt(ciphertext)  # 解密密文
    
    # 检查并处理填充
    if is_pkcs7_padded(plaintext):
        return unpad(plaintext, 16).decode('ascii')  # 如果使用了填充，则移除填充并返回明文
    else:
        return plaintext.decode('ascii')  # 如果未使用填充，则直接返回明文

shared_secret = 1791
iv = "cd9da9f1c60925922377ea952afc212c"
ciphertext = "febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8"   

print(decrypt_flag(shared_secret, iv, ciphertext))

PARAMETER CHOICE

Smooth Criminal

我花了一上午的时间阅读 ECC，现在我准备开始加密我的消息了。今天向 Bob 发送了一个flag，但你永远不能看到。

阅读题目代码，没有发现漏洞，查询后发现使用了光滑素数，直接求解离散对数得到n即可。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
Point = namedtuple("Point", "x y")

O = 'Origin'
FLAG = b'crypto{??????????????????????????????}'

def check_point(P: tuple):
    """
    检查给定点P是否在椭圆曲线上。
    
    参数:
    P - 一个表示点的元组 (x, y)
    
    返回值:
    如果点P在椭圆曲线上则返回True 否则返回False。
    """
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p


def point_inverse(P: tuple):
    """
    计算给定点P关于椭圆曲线的逆元。
    
    参数:
    P - 一个表示点的元组 (x, y)
    
    返回值:
    P的逆元点。
    """
    if P == O:
        return P
    return Point(P.x, -P.y % p)


def point_addition(P: tuple, Q: tuple):
    """
    在椭圆曲线上计算点P和Q的和。
    
    参数:
    P, Q - 分别表示两个点的元组 (x, y)
    
    返回值:
    点P和Q的和。
    """
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a)*inverse(2*P.y, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * inverse((Q.x - P.x), p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    assert check_point(R)
    return R

def double_and_add(P: tuple, n: int):
    """
    使用“双倍加法”算法在椭圆曲线上计算点P的n倍。
    参数:
    P - 一个表示点的元组 (x, y)
    n - 一个整数表示要计算的倍数
    
    返回值:
    点P的n倍。
    """
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q)
        Q = point_addition(Q, Q)
        n = n // 2
    assert check_point(R)
    return R

def gen_shared_secret(Q: tuple, n: int):
    """
    生成与给定公钥Q关联的共享密钥。
    参数:
    Q - 一个表示点的元组 (x, y)，作为对方的公钥
    n - 我方的秘密整数
    
    返回值:
    共享密钥的整数表示。
    """
    S = double_and_add(Q, n)
    return S.x


def encrypt_flag(shared_secret: int):
    """
    使用共享密钥加密旗标。
    参数:
    shared_secret - 一个整数，作为加密的密钥
    返回值:
    包含加密旗标信息的字典。
    """
    # 从共享密钥派生AES密钥
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    # 加密旗标
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # 准备发送的数据
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data
    
# 定义椭圆曲线参数
p = 310717010502520989590157367261876774703
a = 2
b = 3

# 椭圆曲线的生成器点
g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G = Point(g_x, g_y)
# 我方的秘密整数，每次不同！
n = randint(1, p)

# 发送给Bob的公钥
public = double_and_add(G, n)
print(public)

# Bob的公钥
b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)

# 计算共享密钥
shared_secret = gen_shared_secret(B, n)

# 发送给Bob的加密信息
ciphertext = encrypt_flag(shared_secret)
print(ciphertext)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#sage
p = 310717010502520989590157367261876774703
a = 2
b = 3
F=GF(p)
E=EllipticCurve(F,[a,b])

g_x = 179210853392303317793440285562762725654
g_y = 105268671499942631758568591033409611165
G=E(g_x,g_y)

x=280810182131414898730378982766101210916
y=291506490768054478159835604632710368904
NG=E(x,y)


n = discrete_log(NG, G, operation='+')
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def decrypto_flag(iv, encrypted_flag,):
    sha1 = hashlib.sha1()
    sha1.update(str(shared_secret).encode('ascii'))
    key = sha1.digest()[:16]
    iv = bytes.fromhex(iv)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = unpad(cipher.decrypt(bytes.fromhex(encrypted_flag)), 16)
    return plaintext
    
b_x = 272640099140026426377756188075937988094
b_y = 51062462309521034358726608268084433317
B = Point(b_x, b_y)

iv='07e2628b590095a5e332d397b8a59aa7'
encrypted_flag='8220b7c47b36777a737f5ef9caa2814cf20c1c1ef496ec21a9b4833da24a008d0870d3ac3a6ad80065c138a2ed6136af'

n = 47836431801801373761601790722388100620
shared_secret = gen_shared_secret(B, n)

print(decrypto_flag(iv, encrypted_flag))

运行后顺利的得到flag。

Exceptional Curves

从错误中吸取教训…这次我的曲线符合素数顺序。这个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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
"""HOMEWRITEUPSMISCABOUT
EXCEPTIONAL CURVES
An elliptic curve 
 defined over 
 whose cardinality (or order) is also 
 is an anomalous curve, and the discrete logarithm becomes trivial. We can employ Smart's attack, which allows us to perform the discrete log of the curve in linear time. 

This paper by Novotney goes over the details of why the attack works. At the time of writing, I wish I understand what's in the paper - some very topics into group theory. This Crypto StackExchange post provides implementation for this particular attack. 

The choice of the challenge name leads to some other unrelated(?) attack, and I have to dig a bit through the Cryptohack Discord to find a clue for this challenge. Kudos to ariana for having some discussions about this attack, after that I got some better keywords to search for on Google! Also, great props to this writeup by Awesome10billion that initially provided me a script to solve this challenge."""

#sage
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from random import randint
import hashlib

def shared_secret(public_key, private_key):
    S = public_key * private_key
    return S.xy()[0]

# Curve params
p = 0xa15c4fb663a578d8b2496d3151a946119ee42695e18e13e90600192b1d0abdbb6f787f90c8d102ff88e284dd4526f5f6b6c980bf88f1d0490714b67e8a2a2b77
a = 0x5e009506fcc7eff573bc960d88638fe25e76a9b6c7caeea072a27dcd1fa46abb15b7b6210cf90caba982893ee2779669bac06e267013486b22ff3e24abae2d42
b = 0x2ce7d1ca4493b0977f088f6d30d9241f8048fdea112cc385b793bce953998caae680864a7d3aa437ea3ffd1441ca3fb352b0b710bb3f053e980e503be9a7fece

# Define curve
E = EllipticCurve(GF(p), [a, b])

G_x, G_y = (3034712809375537908102988750113382444008758539448972750581525810900634243392172703684905257490982543775233630011707375189041302436945106395617312498769005, 4986645098582616415690074082237817624424333339074969364527548107042876175480894132576399611027847402879885574130125050842710052291870268101817275410204850)
G = E(G_x, G_y)

b_x = 0x7f0489e4efe6905f039476db54f9b6eac654c780342169155344abc5ac90167adc6b8dabacec643cbe420abffe9760cbc3e8a2b508d24779461c19b20e242a38
b_y = 0xdd04134e747354e5b9618d8cb3f60e03a74a709d4956641b234daa8a65d43df34e18d00a59c070801178d198e8905ef670118c15b0906d3a00a662d3a2736bf
B = E(b_x, b_y)

a_x, a_y = (4748198372895404866752111766626421927481971519483471383813044005699388317650395315193922226704604937454742608233124831870493636003725200307683939875286865, 2421873309002279841021791369884483308051497215798017509805302041102468310636822060707350789776065212606890489706597369526562336256272258544226688832663757)
A = E(a_x, a_y)

# From Crypto StackExchange code
def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

# Obtain the secret nA
nA = SmartAttack(G, A, p)

secret = shared_secret(B, nA)
sha1 = hashlib.sha1()
sha1.update(str(secret).encode('ascii'))
key = sha1.digest()[:16]
iv = bytes.fromhex('719700b2470525781cc844db1febd994')
ct = bytes.fromhex('335470f413c225b705db2e930b9d460d3947b3836059fb890b044e46cbb343f0') 
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = unpad(cipher.decrypt(ct), 16)

print(flag.decode())