AGCD 问题

如果说我们知道 x₁, …, x_l 满足 x₁ = pq₁，x₂ = pq₂，…x_i = pq_i 那么我们可以发现各个数直接有一个最大公约数p，然后用gcd(x₁, x₂…x_i)然后就可以分解各个数 但如果此时我们加入误差e₁, e₂​将式子构造为形如 x₁ = pq₁ + e₁, x₂ = pq₂ + e₂ 那么此时我们就没办法通过求公约数来解决这个问题了 在e₁和e₂较小的情况下我们可以通过爆破e₁, e₂方式来求解gcd(x₁ − e₁, x₂ − e₂)，但是在$e_1和e_2较大时我们是无法解决的，这时就是需要用其他的解决方法了

丢番图近似 SDA 格攻击

对于我们已经有的样本x₁, x₂, x₃…x_i中，我们设x₀为一般样本(指的是一个普通、标准、未经特殊处理或修改的数据点。它代表了从正常数据分布中抽取的典型数据)。那么此时当很小的情况下（r₁, r₂, r₃…r_i都很小的情况下）,此时对于 1 ≤ t ≤ i我们有 那么我们就可以称他们为一对同步丢番图近似(来说) 此时我们就可以有如下的推导式

以 (x₀, x₁) 对为例，我们考虑 那么对于 i − 1 组，我们可以构建方程组（p+1表示误差的位数接近位数大小） 可以证明的是，解向量是格中的短向量。

生成代码

from Crypto.Util.number import getPrime, getRandomRange

def gen(k:int, gamma: int, eta: int, rho: int):#k是数据数量，gamma是q的长度，eta是p的长度，rho是噪声长度
    xs = []
    qs = []
    es = []
    p = getPrime(eta)
    for _ in range(k):
        q = getPrime(gamma - eta)
        e = getRandomRange(-pow(2, rho) + 1, pow(2, rho) - 1)
        qs.append(q)
        es.append(e)
        xs.append(p * q + e)
    return p, qs, es, xs

k = 5
eta = 768
gamma = 1024 + eta
rho = 256
p, qs, es, xs = gen(k, gamma, eta, rho)
print(f'{p = }')
print(f'{qs = }')
print(f'{es = }')
print(f'{xs = }')

解决

k = 5
rho = 256
xs = ...

A = ZZ(pow(2, rho + 1))
B = matrix(xs[1:])
C = matrix.diagonal([-xs[0]] * (k - 1))
M = matrix.block([[A, B], [ZZ(0), C]])
L = M.LLL()
q0 = ZZ(L[0, 0] / A).abs()
e0 = ZZ(xs[0] % q0)
p = ZZ((xs[0] - e0) / q0)
print(f'{e0 = }')
print(f'{q0 = }')
print(f'{p = }')

0penHarmony CTF-Simple LLL

具体的附件找不到了，就从别人的wp中的题目来进行分析学习AGCD问题

鸿蒙app，先改为zip后缀解压，然后用jadx-dev-all反汇编看大致的代码，加密逻辑在：

public Object #~@0>#runMixer(Object functionObject, Object newTarget, Index this) {

       obj = this.flag;

       if ((this.flag.length < 6 ? 1 : 0) != 0) {

           this.output = "Flag too short!";

           return null;

       }

       if (istrue(("flag{" != obj.substring(0, 5) ? 1 : 0)) != null || isfalse(("}" != obj[obj.length - 1] ? 1 : 0)) == null) {

           this.output = "Invalid flag, must starts with `flag{` and ends with `}`";

           return null;

       }

       substring = obj.substring(5, obj.length - 1);

       if ((0 != (substring.length % 3) ? 1 : 0) != 0) {

           this.output = "Invalid key length (must be multiple of 3)";

           return null;

       }

       i = 0;

       getPrime = this.getPrime(215);

       getPrime2 = this.getPrime(128);

       getPrime3 = this.getPrime(170);

       r36 = [Object];

       obj2 = getiterator("Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof.".substring(0, 50));

       obj3 = obj2.next;

       i2 = 0;

       while (true) {

           callthisN = obj3();

           throw.ifnotobject(callthisN);

           if (istrue(callthisN.done) != null) {

               break;

           }

           r362 = callthisN.value;

           try {

               bytesToLong = this.bytesToLong(substring[i] + substring[i + 1] + substring[i + 2]);
               i += 3;
               r362 = (i >= substring.length ? 1 : 0);
               if (r362 != 0) {
                   i = 0;
               }
               r36.push((this.getRandomBits(190) * getPrime) + ((this.modPow(getPrime2, bytesToLong, getPrime3) * BigInt(r362.charCodeAt(0))) % getPrime3));
           } catch (ExceptionI0 unused) {
               z = r362;
               if (istrue(i2) == null) {

                   i2 = 1;

                   obj4 = null;
                   r363 = hole;
                   try {
                       obj5 = obj2.return;
                       obj3 = obj5;
                       r363 = (0 == obj5 ? 1 : 0);
                   } catch (ExceptionI0 unused2) {
                   }
                   if (r363 == 0) {
                       obj4 = obj3();
                       throw(z);
                       throw.ifnotobject(obj4);
                   }
               }
               throw(z);

           }

       }

       this.output = "P: " + getPrime3 + ", G: " + getPrime2 + "\nEncrypted: [" + r36.join(", ") + "]";
       console.error("P: " + getPrime3 + "");
       console.error("G: " + getPrime2 + "");

核心加密逻辑

r36.push((this.getRandomBits(190) * getPrime) + ((this.modPow(getPrime2, bytesToLong, getPrime3) * BigInt(r362.charCodeAt(0))) % getPrime3));

对于flag的每一块m_i和密钥流的每个字节k_i，我们生成了密文c c = (q_i × p₀) + (G^m (mod  P) ⋅ k_i) (mod  P) 其中k_i为“Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof.”的前50字节的第一个字符的ASCII码值 q_i为一个随机的190位整数 P为170位的质数 G是128位的质数 p₀是215位的质数 x_i为flag分解为长度为3的若干字符串

上述式子可以被简写为下面的若干线性方程组 此时这里就是个AGCD问题，其中e_i为(G^m (mod  P) ⋅ k_i) (mod  P)此时我们就可以构造如下格 因此我们最后就可以从这个短向量中得到q₁，然后我们就可以恢复e₁，从而恢复p₀ 回到式子中，我们有 e_i ≡ (G^m (mod  P) ⋅ k_i) (mod  P) 然后转化为 G^m_i ≡ e_ik_i⁻¹ (mod  P) 然后就是解一个dlp问题了

#sage
from Crypto.Util.number import *
from tqdm import trange

P = 1105340037553808473854838067251286973932436127087387
G = 258698882868391024376029756014412783703
ct = [...]

x0 = ct[0]
x = ct[1:]

L = matrix(ZZ, len(x) + 1, len(x) + 1)

L[0, 0] = 2^171
for i in range(len(x)):
    L[0, i+1] = x[i]
    L[i+1, i+1] = -x0

res = L.LLL()
q0 = res[0, 0] // 2^171
r0 = ZZ(x0 % q0)
p = ZZ((x0 - r0) // q0)

R = GF(P)

text = "Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof."
flag = b""
for i in trange(len(ct)):
    b = ct[i] % p
    y = b * inverse(ord(text[i]), P) % P
    x = discrete_log(R(y), R(G))
    flag += long_to_bytes(x)

print(flag)

参考：

triode师傅的博客 初雪的小屋