羊城杯

这次羊城杯的密码题很少也是侥幸ak了

瑞德的一生

from Crypto.Util.number import *

from gmpy2 import legendre

from secret import flag

m = bytes_to_long(flag)

p, q = getPrime(256), getPrime(256)

n = p * q

x = getRandomRange(0, n)

while legendre(x, p) != -1 or legendre(x, q) != -1:

  x = getRandomRange(0, n)

def encrypt(msg , n, x):

  y = getRandomRange(0, n) 

  enc = []

  while msg:

    bit = msg & 1

    msg >>= 1

    enc.append((pow(y, 2) * pow(x, bit)) % n)

    y += getRandomRange(1, 2**48)

  return enc

with open('output.txt', 'w') as file:

  file.write(f"n = {n}\n")

  file.write(f"x = {x}\n")

  file.write(f"enc = {encrypt(m, n, x)}\n")

先看题目条件

p, q = getPrime(256), getPrime(256)

n = p * q

x = getRandomRange(0, n)

while legendre(x, p) != -1 or legendre(x, q) != -1:

  x = getRandomRange(0, n)

首先给出了两个256bit的素数p,q,然后给出了它们的乘积n

接下来是判断p,q不是模x下的二次非剩余

加密方式：

def encrypt(msg, n, x):
    y = getRandomRange(0, n) 
    enc = []
    while msg:
        bit = msg & 1
        msg >>= 1
        enc.append((pow(y, 2) * pow(x, bit)) % n)
        y += getRandomRange(1, 2**48)
    return enc

这里题目先是逐位从低位到高位取出m的二进制位数

如果这里取到的m的二进制位是0的话，即bit = 0 c = y² mod  n 如果这里取到的m的二进制位是0的话，即bit = 1 c = y² * x mod  n 这里每加密一位后,y增加一位小随机数

然后就是题目给出了，n,x,enc

那么要如何解密呢，我们回过头来看加密等式 c_i = (y_i + d_i)² * x^b_i mod  n 这里b_i ∈ 0, 1是明文的二进制位

看到这样的结构，这就可以看出是HNP问题，想法是用格或者small_roots来恢复

这里我们有 $$ y_{i}^{2} = \frac{c_{i}}{x_{bi}} \bmod n $$

$$ (y_{i}+d_{i})^{2} = \frac{c_{i+1}}{x_{bi+1}} \bmod n $$

这里我们不妨令： $$ A = \frac{c_{i}}{x_{bi}} \bmod n $$

$$ B = \frac{c_{i+1}}{x_{bi+1}} \bmod n $$

那么这里可以得到 $$ B = ( y_i + d_i )^2 = y_i^2 + 2y_i d_i + d_i^2 \

这里把A代入 $$ 那么就有一个关于d的小根多项式了

所以 poly = （lhs − d²）² − 4d²A 我们这里假设m的第一个bit是1，那么就有 C₀ = y₀² * x mod  n

y₀² = C₀ * x⁻¹ (mod  n)

这里就可以反推出y₀²

如果是0也是同样的情况

这里只要小根有解说明了b_i推断正确继续则可以推出正确的明文

from sage.all import *

from Crypto.Util.number import long_to_bytes

from tqdm import tqdm

N = 

X = 

enc = []

Z = Zmod(N)

P.<d> = PolynomialRing(Z)

y_sq = inverse_mod(X, N) * enc[0] % N

bits = "1"

for cipher in tqdm(enc[1:]):

  matched = False

  for bit in [0, 1]:

​    lhs = (cipher * power_mod(X, -bit, N) - y_sq) % N

​    poly = (lhs - d**2)**2 - 4 * d**2 * y_sq

​    roots = poly.small_roots(epsilon=1/20)

​    if roots:

​      if matched:

​        print("[!] Warning: duplicate match detected")

​      bits = str(bit) + bits

​      matched = True

  if not matched:

​    print("[!] No valid root found for this block")

print(bits)

flag_int = int(bits, 2)

print(long_to_bytes(flag_int))

最后的最后，在赛中发现这个其实是个Goldwasser-Micali 密码系统，所以赛后一直寻找相关知识，但是，寻找的途中发现这个题的原题

DiceCTF @ HOPE - small-fortune

Ridiculous LFSR

from Crypto.Util.number import *

from random import *

from os import urandom

from secret import flag

flag = flag.strip(b"DASCTF{").strip(b"}")

m = bytes_to_long(flag)

LENGTH = m.bit_length()

class LFSR():

  def __init__(self,length):

​    self.seed = urandom(32)

​    self.length = length

​    seed(self.seed)

  def next(self):

​    return getrandbits(self.length)

def rotate(msg,l=1):

  temp = bin(msg)[2:].zfill(LENGTH)

  return int(temp[l:] + temp[:l],2)

lfsr = LFSR(LENGTH)

c = []

l = []

for i in range(200):

  temp = lfsr.next()

  c.append(temp ^ m)

  l.append(bin(temp)[2:].count("1"))

  m = rotate(m)

with open("output.txt","w") as f:

  f.write("LENGTH = " + str(LENGTH) + "\n")

  f.write("c = " + str(c) + "\n")

  f.write("l = " + str(l) + "\n")

线性规划求解器来打

from Crypto.Util.number import *

LENGTH = 295

c = 

l = 

def rotl(x, r, n=LENGTH):

  s = bin(x)[2:].zfill(n)

  r %= n

  return int(s[r:] + s[:r], 2)

def rotr(x, r, n=LENGTH):

  return rotl(x, n - (r % n), n)

t = [rotr(ci, i, LENGTH) for i, ci in enumerate(c)]

a = [ti.bit_count() for ti in t]

b = l[:]  

m, n = len(t), LENGTH

def bit_at(x, j):  

  return (x >> (n - 1 - j)) & 1

V = [[(1 if bit_at(t[i], j) else -1) for j in range(n)] for i in range(m)]

target = [a[i] - b[i] for i in range(m)]

z = [0] * n

r = [-target[i] for i in range(m)]  

def deltaE(j):

  sign = 1 if z[j] == 0 else -1

  col = [V[i][j] for i in range(m)]

  new = [r[i] + sign * col[i] for i in range(m)]

  return sum(v * v for v in new) - sum(v * v for v in r)

import random

random.seed(0)

E = sum(v * v for v in r)

for _ in range(20000):

  best, best_j = 0, None

  for _ in range(100):  

​    j = random.randrange(n)

​    dE = deltaE(j)

​    if dE < best:

​      best, best_j = dE, j

  if best_j is None:

​    

​    j = random.randrange(n)

​    best_j = j

  

  sign = 1 if z[best_j] == 0 else -1

  for i in range(m):

​    r[i] += sign * V[i][best_j]

  z[best_j] ^= 1

  E = sum(v * v for v in r)

  if E == 0:

​    break

m_int = 0

for j in range(n):

  m_int = (m_int << 1) | z[j]

flag = long_to_bytes(m_int)

print(flag)  

b’DASCTF{It’5_4_pr0bl3m_0f_L4ttice!_n0t_LFSR!!}’

看到这个flag预期应该是用格密码来做

线下赛

这个学校的绿化确实挺好的，感觉学校挺漂亮的

不过密码手来打这个综合渗透确实好牢，全程看队友

还有就是这周末有好多比赛都在一起进行了，看着队友们在XCTF上奋战，自己又没帮上什么忙，在外面赶车的心态都不是很好了

不过最后呢，还是成功跟SU的师傅们成功面基了，Win！(*´∀`)~♥