Код: Выделить всё
##!/usr/bin/env python3
from fpylll import LLL, IntegerMatrix
from sympy import mod_inverse as inv
# Parameters
M = 0xFFFFFFDF
c = 0x08088405
pt = 2**64
n = 5
X = [0, 0x0E, 0xEE, 0x42, 0x88] # known X values (X[0] unused)
lsbs = [0x6F, 0xE3, 0x8F, 0xB0, 0x5B]
b = [pow(c, i, M) for i in range(n)] # b[i] = c^i mod M
def calc_S(i):
"""Compute S_i as in your original code (mod M)."""
S = 0
for j in range(1, i+1):
S += X[j] * pow(c, i-j+1, M)
for j in range(0, i):
S += pow(c, j, M)
return S % M
S = [0] + [calc_S(i) for i in range(1, n)]
def build_matrix(num_bits):
num_s = len(S) # = n
dim = num_s + 2 # matrix dimension
lattice = IntegerMatrix(dim, dim)
kbi = 2 ** num_bits
for i in range(num_s):
lattice[i, i] = int((2 * kbi * M) % pt)
inv_kbi = int(inv(kbi, M))
lattice[num_s, i] = int((2 * kbi * (inv_kbi * b[i] % M)))
diff = (lsbs[i] - S[i]) % M
lattice[num_s + 1, i] = int((2 * kbi * (inv_kbi * diff % M) + M))
lattice[num_s, num_s] = 1
lattice[num_s + 1, num_s + 1] = M
return lattice
def lattice_attack(known_bits):
lattice = build_matrix(known_bits)
print(lattice)
# apply LLL in-place
LLL.reduction(lattice)
dim = lattice.nrows
# iterate rows: make each row a python list for easy indexing
for r in range(dim):
row = [lattice[r, c] for c in range(dim)]
# second-to-last column index is num_s
num_s = dim - 2
b_val = row[num_s] % M
if b_val != 0:
cand1 = b_val % M
if (cand1 % 256) == lsbs[0]:
print("found cand1:", hex(cand1))
cand2 = (M - b_val) % M
if (cand2 % 256) == lsbs[0]:
print("found cand2:", hex(cand2))
if __name__ == "__main__":
lattice_attack(8)
print("done")
Код: Выделить всё
#include
#include
#include
#include
#include
#define M 0xFFFFFFDFu
#define C 0x08088405u
#define N 5
const uint32_t k5 = 0x12A20A72;
const uint64_t M64 = 0xFFFFFFFFFFFFFFFF;
uint32_t X[N] = {0x0, 0x0E, 0xEE, 0x42, 0x88};
uint32_t lsbs[N] = {0x6F, 0xE3, 0x8F, 0xB0, 0x5B};
uint32_t B[N];
uint32_t S[N];
// Compute modular inverse of a modulo M
uint32_t modinv(uint32_t a, uint32_t mod) {
int64_t t=0, newt=1, r=mod, newr=a;
while (newr != 0) {
int64_t q = r / newr;
int64_t tmp = t; t = newt; newt = tmp - q*newt;
tmp = r; r = newr; newr = tmp - q*newr;
}
if (r > 1) return 0; // not invertible
if (t < 0) t += mod;
return (uint32_t)t;
}
uint64_t power(uint64_t base, int exp) {
switch (exp) {
case 0:
return 1;
case 1:
return base %M64;
case 2:
return (base*base) %M64;
case 3:
return ((base*base)*base) %M64;
case 4:
return (((base*base)*base)*base) %M64;
}
return 0;
}
// Precompute S and b arrays
void calc_Sb() {
S[0] = 0;
for (int j = 1; j < N; j++) {
S[j] = ((S[j-1]*C) + (X[j]*C) + 1) %M;
}
B[0] = 1;
for (int a = 1; a < N; a++) {
B[a] = power(C,a) %M; // integer powers modulo M
}
}
// Build matrix dynamically
uint64_t ** build_matrix(int len, int num_bits) {
uint64_t **mat = malloc((len+2) * sizeof(uint64_t*));
for(int i=0;i
Подробнее здесь: [url]https://stackoverflow.com/questions/79800188/why-arithmetic-output-from-c-and-python-are-different[/url]