SHI-3-kolliderare

Project Euler 59

Äntligen lite kryptoknäckning!

ciphertext = open( "cipher1.txt", "r" ).readline().split(',')

frequencies = [[0]*255,[0]*255,[0]*255] 

for char in range(0,len(ciphertext)):

   frequencies[char%3][int(ciphertext[char])] += 1

print sum(int(ciphertext[char]) ^ 32 ^ frequencies[char%3].index(max(frequencies[char%3])) for char in range(0, len(ciphertext)))

Sudo funkar när allt annat brister

Project Euler 26

SHI-3-kolliderare under körning

Väntar på att SHI-3 skall kollidera.

Project Euler 148

to A <3

def f(x):

   if x <= 6:

      return (x)*(x+1)/2

   else:

      k = 1

      r = 1

      while (7*k <= x):

         k *= 7

         r *= 28

return f(x/k)*r + (x/k+1)*f(x-k*int(x/k))

Använde identiteten att x^{7} + y^{7} = (x+y)^{7} (mod 7). Det är vetvärt att lösningen är alla ickenoll rutor i en Sierpinskitriangel.

Kollision hittad

Ur mitt exjobb:

Project Euler 202

Ja, det är ju inte världens vackraste kod och den tar dessutom ganska lång tid att exekvera (~10min på en MacBook), på grund av en dålig skriver GCD-algoritm. Det går helt klart att göra mer effektivt... 

Lösningen jag kom fram till var att istället för att spegla laserstrålen, så speglar vi rummet. Speglingen sker iterativt och blir ett rutnät med trianglar. När det är gjort drar vi en RAK linje genom hela rutnätet till en viss nivå i iterationen och finna ett hörn som är ingångpunkten. Dock måste vi se till att vi inte passerar några andra hörn på vägen, och det är just det vi använder GCD till!

int main() { 

unsigned long long m = 12017639147ull;

unsigned long long s, j, k, x ,y ,g;

if (m % 3 == 2) s = 2;

if (m % 3 == 1) s = 0;

if (m % 3 == 0) s = 1;

j = (m-1)/2 + 3;

unsigned long long count = 0;

k = s + 1;

while(1) {

x = j-k;

y = k-1;

while (x > 0){

g = x;

x = y % x;

y = g;

}

if (g == 1)

count += 1;

k += 3;

if (k > ((j-s)/2))

break;

if(count % 1000000 ==0)

printf("%d\n",count);

}

printf("%d", count*2);

}

SHI-2 vill inte kollidera

Sitter och går igenom kod för attack mot SHI-2. SHI-2 är SHI-1, men med icke-linjära funktioner. Med viss sannolikhet beter sig f_i(B,C,D) som XOR(B,C,D). Med en slump-algoritm gör jag försök för att hitta en felvektor som uppfyller XOR-beteende, men än så länge har jag inte påträffat någon kollision. Koden verkar korrekt...

Satt och roade mig med att lösa det här problemet som omväxling. Väldigt kul och givande, även om det slukade några timmar av min skoltid för att lösas!

Kod för att lösa en algebraisk ekvation över GF(2), den så kallade SHI-1.

%% Program for solving the linear equations of SHI1

basis = []

for n = 1:11

% Bit n must be 1

A = [zeros(1,80)];

b = [ zeros(75,1)];

A(1,n) = 1;

b(1,1) = 1;

% Must be an expansion of m

for i = 12:80

u = zeros(1,80);

u(i) = 1; u(i-3) = 1; u(i-8) = 1;

if (i - 14) > 0

u(i-14) = 1;

end

if (i - 16) > 0

u(i-16) = 1;

end

A = [A ; u];

end

% Last five bits must be zero

A = [A; zeros(5,75) eye(5)];

basis = [basis gflineq(A,b)];

end

% independent basis

gfrank(basis')

% check if match

for i = 17:80

if not (basis(i,1) == mod(basis(i-3,1) + basis(i-8,1) + basis(i-14,1) + basis(i-16,1), 2))

echo 'No match'

i

%break

end

end