Week1
RSA
基础的RSA题，题目也提示了整数分解，分解n得到p、q就能解了。
神秘的电话
一道令我无语的脑洞题。
附件：
encrypted_message:
5Yeg5Liq5pif5pyf5YmN77yM5oiR5Lus5pS25Yiw5LiA5Liq56We56eY55qE5raI5oGv44CC5L2G5piv6L+Z5Liq5raI5oGv6KKr6YeN6YeN5Yqg5a+G77yM5oiR5Lus5LiN55+l6YGT5a6D55qE55yf5q2j5ZCr5LmJ5piv5LuA5LmI44CC5ZSv5LiA55+l6YGT55qE5L+h5oGv5piv5YWz5LqO5a+G6ZKl55qE77ya4oCc5Y+q5pyJ5YCS552A57+76L+H5Y2B5YWr5bGC55qE56+x56yG5omN6IO95oq16L6+5YyX5qyn56We6K+d55qE57uI54K54oCd44CC
还有一段摩斯音频。
上面的密文能看出来是base64加密，解密得到：
⼏个星期前，我们收到⼀个神秘的消息。但是这个消息被重重加密，我们不知道它的真正含义是什
么。唯⼀知道的信息是关于密钥的：“只有倒着翻过⼗⼋层的篱笆才能抵达北欧神话的终点”。
这里我以为引号里的信息都是关于密钥的，没想到还涉及道密文的加密，属实被恶心了。
倒着：逆序加密；十八层的篱笆：W型栅栏（后面再说为什么是W型栅栏）；北欧神话的终点：密钥vidar，对应维吉尼亚密码（航电工作室的名称）
用Audacity打开摩斯音频，写下摩斯密码再去解密得到：
0223e_priibly__honwa_jmgh_fakcqaoqtmfr
发现其长度为38，按照普通栅栏的思路无法将每一组分为18个字符，故猜测是W型栅栏。
对密文先逆序，在栅栏，最后维吉尼亚得到flag。
Be Stream
题目：
from flag import flag
assert type(flag) == bytes
key = [int.from_bytes(b"Be water", 'big'), int.from_bytes(b"my friend", 'big')]
def stream(i):
if i==0:
return key[0]
elif i==1:
return key[1]
else:
return (stream(i-2)*7 + stream(i-1)*4)
enc = b""
for i in range(len(flag)):
water = stream((i//2)**6) % 256
enc += bytes([water ^ flag[i]])
print(enc)
# b'\x1a\x15\x05\t\x17\t\xf5\xa2-\x06\xec\xed\x01-\xc7\xcc2\x1eXA\x1c\x157[\x06\x13/!-\x0b\xd4\x91-\x06\x8b\xd4-\x1e+*\x15-pm\x1f\x17\x1bY'
进行分析可知，当i从4开始，代入到函数里进行递归，会变得非常复杂，这时就需要我们简化这个过程–利用矩阵解方程的思想。
首先通过函数我们可以得到递推式：$S_{i}=4S_{i-1}+7S_{i-2}$，用矩阵相乘的思想来将这个方程转化为矩阵相乘的样子（表述不太标准）。关于这个思想可以参考这篇文章：斐波那契数列 矩阵求法 优化 - 旭东的博客 - 博客园 (cnblogs.com)
递推式转为矩阵相乘后：$\begin{bmatrix} S_{i} & S_{i-1} \end{bmatrix}=\begin{bmatrix} S_{i-1} & S_{i-2} \end{bmatrix}\begin{bmatrix} 4 & 1 \ 7 & 0 \end{bmatrix}$，$\begin{bmatrix} S_{i-1} & S_{i-2} \end{bmatrix}$这部分初始值即为$\begin{bmatrix} key[1] & key[0] \end{bmatrix}$
代码实现：
import numpy
key = [int.from_bytes(b"Be water", 'big'), int.from_bytes(b"my friend", 'big')]
enc = b'\x1a\x15\x05\t\x17\t\xf5\xa2-\x06\xec\xed\x01-\xc7\xcc2\x1eXA\x1c\x157[\x06\x13/!-\x0b\xd4\x91-\x06\x8b\xd4-\x1e+*\x15-pm\x1f\x17\x1bY'
flag = b''
A = numpy.matrix([[4,1],[7,0]])
M = numpy.matrix([[key[1],key[0]]])
print(A)
print(M)
for i in range(len(enc)):
index = (i//2)**6
if index < 2:
water = key[index]%256
else:
S = M*A**(index-1)
print(S[0][0,0] % 256)
water = S[0][0,0] % 256
# print(S%256)
#print(water)
flag += bytes([water ^ enc[i]])
print(flag)
兔兔的车票
题目：
from PIL import Image
from Crypto.Util.number import *
from random import shuffle, randint, getrandbits
flagImg = Image.open('flag.png')
width = flagImg.width
height = flagImg.height
def makeSourceImg():
colors = long_to_bytes(getrandbits(width * height * 24))[::-1]
img = Image.new('RGB', (width, height))
x = 0
for i in range(height):
for j in range(width):
img.putpixel((j, i), (colors[x], colors[x + 1], colors[x + 2]))
x += 3
return img
def xorImg(keyImg, sourceImg):
img = Image.new('RGB', (width, height))
for i in range(height):
for j in range(width):
p1, p2 = keyImg.getpixel((j, i)), sourceImg.getpixel((j, i))
img.putpixel((j, i), tuple([(p1[k] ^ p2[k]) for k in range(3)]))
return img
"""
source文件夹下面的图片生成过程：
def makeImg():
colors = list(long_to_bytes(getrandbits(width * height * 23)).zfill(width * height * 24))
shuffle(colors)
colors = bytes(colors)
img = Image.new('RGB', (width, height))
x = 0
for i in range(height):
for j in range(width):
img.putpixel((j, i), (colors[x], colors[x + 1], colors[x + 2]))
x += 3
return img
for i in range(15):
im = makeImg()
im.save(f"./source/picture{i}.png")
"""
n1 = makeSourceImg()
n2 = makeSourceImg()
n3 = makeSourceImg()
nonce = [n1, n2, n3]
index = list(range(16))
shuffle(index)
e=0
"""
这里flag.png已经提前被保存在source文件夹下了，文件名也是picture{xx}.png
"""
for i in index:
im = Image.open(f"source/picture{i}.png")
key = nonce[randint(0, 2)]
encImg = xorImg(key, im)
encImg.save(f'pics/enc{e}.png')
e+=1
随机⽣成3张密钥图⽚作为nonce，然后把一张flag.png和15张picture{xx}.png打乱与nonce进⾏异或。因为只有三张nonce，⽽picture有15张，所以⼤概率有picture跟flag.png重⽤了同⼀张nonce。就可以⽤这两张加密图⽚进⾏XOR，得到：$flag.png ⊕picturex.png$，⽽再根据picture{x}.png的⽣成函数可以看到picture{xx}.png中有很多位等于0的点，那么就可以暴露出flag.png的特征。题⽬本⾝图⽚不多，可以进⾏爆破。
代码：
from PIL import Image
width = 379
height = 234
def xorImg(keyImg, sourceImg):
img = Image.new('RGB', (width, height))
for i in range(height):
for j in range(width):
p1, p2 = keyImg.getpixel((j, i)), sourceImg.getpixel((j, i))
img.putpixel((j, i), tuple([(p1[k] ^ p2[k]) for k in range(3)]))
return img
for i in range(16):
for j in range(16):
img1 = Image.open(f'pics/enc{i}.png')
img2 = Image.open(f'pics/enc{j}.png')
img = xorImg(img1, img2)
img.save(f'res/img_{i}_{j}.png')
Week2
Rabin
雷宾加密，套用解密模板就行。
RSA 大冒险1
四部分RSA加密。
part1:
from Crypto.Util.number import *
from challenges import chall1_secret
class RSAServe:
def __init__(self) -> None:
self.e = 65537
self.p = getPrime(128)
self.q = getPrime(100)
self.r = getPrime(100)
self.m = chall1_secret
def encrypt(self):
m_ = bytes_to_long(self.m)
c = pow(m_, self.e, self.p*self.q*self.r)
return hex(c)
def check(self, msg):
return msg == self.m
def pubkey(self):
return self.p*self.q*self.r, self.e, self.p
我看到n由三部分组成，直接用yafu工具去解，倒是能分解出来，然后就能直接解出来了。
官方wp里说到，p的位数为128位，q和r都是100位。可以合理猜测m <p，于是原先在ZN上的运算就可以直接转移到Zp上。解出来的答案确实这个意思，或许我误打误撞了。
part2和part4放一块，给自己提个醒，代码审计这块太不行了：
from Crypto.Util.number import *
from challenges import chall2_secret
class RSAServe:
def __init__(self) -> None:
self.p = getPrime(512)
self.q = getPrime(512)
self.e = 65537
self.m = chall2_secret
def encrypt(self):
m_ = bytes_to_long(self.m)
c = pow(m_ ,self.e, self.p*self.q)
self.q = getPrime(512)
return hex(c)
def check(self, msg):
return msg == self.m
def pubkey(self):
return self.p*self.q, self.e
from Crypto.Util.number import *
from challenges import chall4_secret
class RSAServe:
def __init__(self) -> None:
self.p = getPrime(512)
self.q = getPrime(512)
self.e = getPrime(17)
self.m = chall4_secret
def encrypt(self):
m_ = bytes_to_long(self.m)
c = pow(m_, self.e, self.p*self.q)
self.e = getPrime(17)
return hex(c)
def check(self, msg):
return msg == self.m
def pubkey(self):
return self.p*self.q, self.e
我压根就没注意到part2里的q和part4里的e每次都变化，导致我还在想到底是RSA里的哪种类型，蠢到家了。
part2因为q每次都变，p不变，所以获取两n，求gcd，p就出来了；part4里e每次变，导致c也每次变，但n不变，就是共模攻击了。对自己有点无语😶。
part3
from Crypto.Util.number import *
from challenges import chall3_secret
class RSAServe:
def __init__(self) -> None:
self.p = getPrime(512)
self.q = getPrime(512)
self.e = 3
self.m = chall3_secret
def encrypt(self):
m_ = bytes_to_long(self.m)
c = pow(m_, self.e, self.p*self.q)
return hex(c)
def check(self, msg):
return msg == self.m
def pubkey(self):
return self.p*self.q, self.e
e = 3，低解密指数攻击。
包里有什么
背包密码，题目：
from random import randint
from libnum import gcd, s2n
from secret import flag
plain = flag[6:-1]
assert flag == 'hgame{' + plain + '}'
v = bin(s2n(plain))[2:]
l = len(v)
a = [2 << i for i in range(l)]
m = randint(sum(a), 2 << l + 1)
w = randint(0, m)
assert gcd(w, m) == 1
b = [w * i % m for i in a]
c = 0
for i in range(l):
c += b[i] * int(v[i])
print(f'm = {m}')
print(f'b0 = {b[0]}')
print(f'c = {c}')
# m = 1528637222531038332958694965114330415773896571891017629493424
# b0 = 69356606533325456520968776034730214585110536932989313137926
# c = 93602062133487361151420753057739397161734651609786598765462162
第一次写遇到背包密码的题
代码分析：
v为二进制形式的明文，后面接了个切片[2:]是为了去掉开头的’0b’
print(bin(s2n('helloworld')))
#0b1101000011001010110110001101100011011110111011101101111011100100110110001100100
l为二进制明文的长度，a为私钥，b为公钥，m为模数（大于序列中的所有数的和），w是与m互素的数（小于m）。
因为第一次做背包密码，我开始以为要想办法逐一推出每一个v[i]出来，因为如果知道明文二进制的长度，公钥，私钥就都知道了。显然不现实，位数太长，且没办法推出每一个v[i]来，题目只给了所有部分的和c。
其实通过加密后密文的和c就能直接推出明文的和v，直接就能求flag了，整体解密和部分解密的方法是一样的，求出w的逆元就行，这样一来，公钥私钥都用不到。
代码如下：
from libnum import *
w = 34678303266662728260484388017365107292555268466494656568963
m = 1528637222531038332958694965114330415773896571891017629493424#模数
b0= 69356606533325456520968776034730214585110536932989313137926#公钥列表里的第一个数
c = 93602062133487361151420753057739397161734651609786598765462162#密文
#w_ni = invert(w,m)
w_ni = 277527593585833632092135078681588573398259359217914482475243
v = c * w_ni % m >> 1
print("hgame{"+long_to_bytes(int(bin(v)[2:][::-1],2)).decode()+"}")
Week3
ezDH
题目：
from sage.all import *
from Crypto.Util.number import *
from secret import Alice_secret, Bob_secret, FLAG
import random
f = open('output', 'w')
N=0x2be227c3c0e997310bc6dad4ccfeec793dca4359aef966217a88a27da31ffbcd6bb271780d8ba89e3cf202904efde03c59fef3e362b12e5af5afe8431cde31888211d72cc1a00f7c92cb6adb17ca909c3b84fcad66ac3be724fbcbe13d83bbd3ad50c41a79fcdf04c251be61c0749ea497e65e408dac4bbcb3148db4ad9ca0aa4ee032f2a4d6e6482093aa7133e5b1800001
g = 2
A = power_mod(g, Alice_secret, N)
f.write("Alice send to Bob: {{ 'g': {g}, 'A': {A} }}\n".format(g=g, A=hex(A)))
B = power_mod(g, Bob_secret, N)
f.write("Bob send to Alice: {{'B': {B} }}\n".format(B=hex(B)))
shared_secret = pow(A, Bob_secret, N)
p=6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
a=-3
b=1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984
E = EllipticCurve(GF(p), [a, b])
G = E.random_point()
Pa = shared_secret * G
f.write(f"Alice send to Bob: {{ 'E': {E}, 'G': {G.xy()}, 'Pa': {Pa.xy()} }}\n")
k = random.randint(2, p)
m = E.lift_x(Integer(bytes_to_long(FLAG)))
P1 = k * G
P2 = k * Pa
c = m + P2
f.write(f"Bob send to Alice: {{ {P1.xy()}, {c.xy()} }}\n")
涉及到Diffie-Hellman密钥交换算法，还未涉足，所以这道题单独拿出来说明。
RSA ⼤冒险2
Challenge 1
from Crypto.Util.number import *
from math import isqrt
from challenges import chall1_secret
class RSAServe:
def __init__(self) -> None:
def create_keypair(size):
while True:
p = getPrime(size // 2)
q = getPrime(size // 2)
if q < p < 2*q:
break
N = p*q
phi = (p-1)*(q-1)
max_d = isqrt(isqrt(N)) // 3
max_d_bits = max_d.bit_length() - 1
while True:
d = getRandomNBitInteger(max_d_bits)
try:
e = int(inverse(d, phi))
except ZeroDivisionError:
continue
if (e * d) % phi == 1:
break
return N, e, d
self.N, self.e, self.d = create_keypair(1024)
self.m = chall1_secret
def encrypt(self):
m_ = bytes_to_long(self.m)
c = pow(m_ ,self.e, self.N)
return hex(c)
def check(self, msg):
return msg == self.m
def pubkey(self):
return {"N":self.N, "e":self.e}
q < p < 2*q和max_d = isqrt(isqrt(N)) // 3，满足Wiener-attack的条件，套用Boneh_Durfee’s attack板子解出p和q来。
def factor_rsa_wiener(N, e):
N = Integer(N)
e = Integer(e)
cf = (e / N).continued_fraction().convergents()
for f in cf:
k = f.numer()
d = f.denom()
if k == 0:
continue
phi_N = ((e * d) - 1) / k
b = -(N - phi_N + 1)
dis = b ^ 2 - 4 * N
if dis.sign() == 1:
dis_sqrt = sqrt(dis)
p = (-b + dis_sqrt) / 2
q = (-b - dis_sqrt) / 2
if p.is_integer() and q.is_integer() and (p * q) % N == 0:
p = p % N
q = q % N
if p > q:
return (p, q)
else:
return (q, p)
N = ...
e = ...
c = ...
p, q = factor_rsa_wiener(N, e)
f = (p-1)*(q-1)
d = inverse_mod(e,f)
m = pow(c,d,N)
print(bytes.fromhex(hex(m)[2:]))
# b'wiener_attack_easily!!!'
参考：HGAME 2023 Week 3 | Lazzaro (lazzzaro.github.io)
Challenge 2
from Crypto.Util.number import *
from challenges import chall2_secret
def next_prime(p):
k=1
while True:
if isPrime(p+k):
return p+k
k+=1
class RSAServe:
def __init__(self) -> None:
def creat_keypair(nbits, beta):
p = getPrime(nbits // 2)
q = next_prime(p+getRandomNBitInteger(int(nbits*beta)))
N = p*q
phi = (p-1)*(q-1)
while True:
e = getRandomNBitInteger(16)
if GCD(e, phi) == 2:
break
d = inverse(e, phi)
return N, e, d
self.N, self.e, self.d = creat_keypair(1024, 0.25)
self.m = chall2_secret
def encrypt(self):
m_ = bytes_to_long(self.m)
c = pow(m_, self.e, self.N)
return hex(c)
def check(self, msg):
return msg == self.m
def pubkey(self):
return {"N":self.N, "e":self.e}
p = getPrime(nbits // 2)
q = next_prime(p+getRandomNBitInteger(int(nbitsbeta)))
由这两行可以知道p、q相近，在$p − q = N^{β}$ ，且β < 0.25的时候费⻢分解可以很有效的分解N（或者直接用yafu进行分解）。
from gmpy2 import *
from Crypto.Util.number import *
from sympy.ntheory.primetest import is_square
from math import isqrt
def factorize(N):
"""
Recovers the prime factors from a modulus using Fermat's factorization metho
:param N: the modulus
:return: a tuple containing the prime factors, or None if the factors were n
"""
a = isqrt(N)
b = a * a - N
while b < 0 or not is_square(b):
a += 1
b = a * a - N
p = a - isqrt(b)
q = N // p
if p * q == N:
return p, q
N= 68414473664421192639324860086304622601462638941429703900601142401666806262479832339441486761549640560858310048110541758196980937681745306684526118613694088585953109432823793467906611480953093877867597017269693809377188442523548160628479089952031515541299395812090799992365148053327937407652550818853770241959
p,q = factorize(N)
print(p,q)
还有一种思路是从已知p高位攻击入手，参考la佬的脚本（还搞不懂）：
import gmpy2
N = 68414473664421192639324860086304622601462638941429703900601142401666806262479832339441486761549640560858310048110541758196980937681745306684526118613694088585953109432823793467906611480953093877867597017269693809377188442523548160628479089952031515541299395812090799992365148053327937407652550818853770241959
e = 62830
c = 0x520ba82a569ea52f16b84c4415186cd616680131e3ac6eda886fea046b18b0e1326d4acbbfb8840dc8064211cd44c30b91148836048434a3f57dd4ec5a5cdaf005a0f8f2c95ee7d9a739505b01e407acd3441dd088f64a2a0c36e43c520e30bd90bb32ec1125e4bb1f4e7d522596898da22c9a7921ac5da96808ee39c98e131f
pbits = 512
find = 0
for i in range(10):
for j in range(2**i):
p4 = Integer(gmpy2.iroot(N,2)[0])>>256
p4 = (p4<<i) + j
kbits = pbits - p4.nbits()
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(N))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.5)
if roots:
p = p4+int(roots[0])
if N%p == 0:
print(p)
find = 1
break
if find == 1:
break
q = N // p
f = (p-1)*(q-1)
d = inverse_mod(e//2,f)
cc = pow(c,d,N)
P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^2-cc
mps=f.monic().roots()
P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
g=a^2-cc
mqs=g.monic().roots()
for mpp in mps:
x=mpp[0]
for mqq in mqs:
y=mqq[0]
solution = hex(CRT_list([int(x), int(y)], [p, q]))[2:]
if len(solution) % 2 == 0:
print(bytes.fromhex(solution))
接着是e和欧拉函数不互素的问题。
e = 62830
c = 0x520ba82a569ea52f16b84c4415186cd616680131e3ac6eda886fea046b18b0e1326d4acbbfb8840dc8064211cd44c30b91148836048434a3f57dd4ec5a5cdaf005a0f8f2c95ee7d9a739505b01e407acd3441dd088f64a2a0c36e43c520e30bd90bb32ec1125e4bb1f4e7d522596898da22c9a7921ac5da96808ee39c98e131f
e //= 2
d = invert(e,(p-1)*(q-1))
m = iroot(pow(c,d,N),2)[0]
print(long_to_bytes(m))
Challenge 3
from Crypto.Util.number import *
from challenges import chall3_secret
class RSAServe:
def __init__(self) -> None:
def create_keypair(nbits):
p = getPrime(nbits // 2)
q = getPrime(nbits // 2)
N = p*q
phi = (p-1)*(q-1)
e = 65537
d = inverse(e, phi)
leak = p >> 253
return N, e, d, leak
self.N, self.e, self.d, self.leak = create_keypair(1024)
self.m = chall3_secret
def encrypt(self):
m_ = bytes_to_long(self.m)
c = pow(m_, self.e, self.N)
return hex(c)
def check(self, msg):
return msg == self.m
def pubkey(self):
return {"N":self.N, "e":self.e, "leak":self.leak}
已知 p 高位攻击，但泄露位数过少，位爆破+调节参数扩大格范围（扩大运算域）。记录下la佬的脚本：
from tqdm import *
n = ...
pbits = 512
for i in trange(2**5):
p4 = 531320819410375258952658395582915285878636410772332266245849790153420724865787<<(253-248)
p4 = p4 + i
kbits = pbits - p4.nbits()
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
if roots:
p = p4+int(roots[0])
if n%p==0:
print(i,p)
break
q = n//p
e = 65537
c = ...
f = (p-1)*(q-1)
d = inverse_mod(e,f)
m = pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))
ezBlock
题目：
from secret import flag
def s_substitute(m):
c = 0
s_box = {0: 0x6, 1: 0x4, 2: 0xc, 3: 0x5, 4: 0x0, 5: 0x7, 6: 0x2, 7: 0xe, 8: 0x1, 9: 0xf, 10: 0x3, 11: 0xd, 12: 0x8,
13: 0xa, 14: 0x9, 15: 0xb}
for i in range(0, 16, 4):
t = (m >> i) & 0xf
t = s_box[t]
c += t << i
return c
def enc(m, key):
n = len(key)
t = m
for i in range(n - 1):
t = t ^ key[i]
t = s_substitute(t)
c = t ^ key[n - 1]
return c
f = flag[6:-1]
assert flag == 'hgame{' + f + '}'
key = [int(i, 16) for i in f.split('_')]
print(len(key))
m_list = [i * 0x1111 for i in range(16)]
c_list = [enc(m, key) for m in m_list]
print(c_list)
# 5
# [28590, 33943, 30267, 5412, 11529, 3089, 46924, 59533, 12915, 37743, 64090, 53680, 18933, 49378, 23512, 44742]
涉及到差分攻击，还是单独拿出来写篇Bold记录一下吧。
week4
实在太菜，暂时先把题目记着，强了再来。。。
1月18日贴的，今天4月29日，再整理博客的时候看到了这几个题，想着应该能写了吧？😭
LLLCG
from Crypto.Util.number import *
from random import randint
from sage.all import next_prime
from flag import flag
class LCG():
def __init__(self) -> None:
self.n = next_prime(2**360)
self.a = bytes_to_long(flag)
self.seed = randint(1, self.n-1)
def next(self):
self.seed = self.seed * self.a + randint(-2**340, 2**340) % self.n
return self.seed
lcg = LCG()
outputs = []
for i in range(40):
outputs.append(lcg.next())
with open('output.txt', 'w') as f:
f.write(str(outputs))
要求a（即flag），我还在想没n怎么算，看了佬们的wp后才知道代码存在问题，看到下面这句：
self.seed = self.seed * self.a + randint(-2**340, 2**340) % self.n
前面的部分并没有括起来，又$r < seed < n$，所以随机选取一组outputs进行整除就得到了a。
预期应该是用LLL算法，涉及到格，准备这几天学一学
LLLCG Revenge
>from Crypto.Util.number import *
from random import randint
>from sage.all import next_prime
from flag import flag
class LCG():
def __init__(self) -> None:
self.n = next_prime(2**360)
self.a = bytes_to_long(flag)
self.seed = randint(1, self.n-1)
def next(self):
self.seed = (self.seed * self.a + randint(-2**340, 2**340)) % self.n
return self.seed
lcg = LCG()
outputs = []
for i in range(40):
outputs.append(lcg.next())
with open('output.txt', 'w') as f:
f.write(str(outputs))
可以看到除了加了括号以外，其他部分和上面的题一样。
涉及到格的相关问题，准备这几天学一学。
ECRSA
from sage.all import *
from sage.all_cmdline import *
from Crypto.Util.number import *
from secret import flag
Nbits = 512
x = bytes_to_long(flag)
f = open('./output', 'w')
def gen_pubkey(Nbits):
p = getPrime(Nbits // 2)
q = getPrime(Nbits // 2)
n = p*q
while True:
a = getRandomInteger(Nbits // 2)
b = getRandomInteger(Nbits // 2)
if gcd(4*a**3 + 27*b**2, n) == 1:
break
E = EllipticCurve(Zmod(n), [a, b])
e = getPrime(64)
f.write(f"p={p}\nq={q}\n")
return n, E, e
n, E, e = gen_pubkey(Nbits)
pt = E.lift_x(Integer(x))
ct = pt * e
f.write(f"n = {n}\na = {E.a4()}\nb = {E.a6()}\ne = {e}\n")
f.write(f"ciphertext = {long_to_bytes(int(ct.xy()[0]))}\n")
我觉得这道题对于我学习ECC有很大的帮助，所以单独拿出去做记录了。（所以当时干什么去了？唉，太jier懒了，过了这么久没大长进。）
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com