introduction to lattices help

asked 2023-09-17 11:19:00 +0200

mandooo
11 ●3

Hi im doing a problem from the Chapter Lightweight Introduction to Lattices in "Learning and Experiencing Cryptography with CrypTool and SageMath"

I'm curious if my implementation is wrong since I'm trying to measure a solution as a whole number as opposed to fraction. I've tried searching for common leetspeak words like 1337 or 5463 as the example gave in the question but couldn't find much. I'll attach my code and an image of the question. I'm also using sage to do this to improve. I'd appreciate any help. Thanks Update i can't send an image because i don't have enough points so here's the question

Alice and Bob established an interesting (but insecure) encryption scheme. Alice creates n equations with n variables and sends them to Bob over an insecure channel using two packets. The first packet consists of all the coefficients used in the equations in form of a matrix without any changes. However, the second packet consists of all the right sides of the equations in scrambled order. Their shared secret key consists of the original indexes of the scrambled right sides of the equations. Having the secret key, Bob can unscramble the right sides of the equations and recover the unknown variables. Then, he multiplies all the recovered variables and the final number is the decrypted message. They were using leet language to create or read the final number. For example, the word sage in leet language is 5463.

from itertools import permutations

P1 = matrix([[33,79,29,41,47],[79,27,39,79,44],[90,83,58,1,90],[38,32,13,15,96],[72,82,88,83,23]])
print(P1) 

numbers = [73300,167887,243754,254984,458756]
combinations = permutations(numbers, len(numbers)) 

for i, combo in enumerate(combinations, 1):
    P2 = Matrix([[combo[0]], [combo[1]], [combo[2]], [combo[3]], [combo[4]]])
    #print(P2,"\n")
    solution = P1.solve_right(P2) 
    #print(solution) 
    flag = 1
    for s in solution: 
        flag *= s
        #print(f"flag: {flag}")
        if isinstance(flag, int): 
            print(f"flag found, {flag}, {i}")

edit retag flag offensive close merge delete

add a comment

answered 2023-09-17 18:08:15 +0200

Max Alekseyev

5778 ●7 ●37 ●123

updated 2023-09-17 18:24:54 +0200

The question amounts to determining whether the obtained solution is composed of integers. There are multiple ways to do so. Perhaps, the simplest one is to check whether denominators of all elements of a solution equal to 1 - like this:

from itertools import permutations

P1 = matrix([[33,79,29,41,47],[79,27,39,79,44],[90,83,58,1,90],[38,32,13,15,96],[72,82,88,83,23]])

numbers = [73300,167887,243754,254984,458756]
combinations = permutations(numbers, len(numbers)) 

for i, combo in enumerate(combinations, 1):
    P2 = Matrix([[combo[0]], [combo[1]], [combo[2]], [combo[3]], [combo[4]]])
    solution = P1.solve_right(P2) 
    if all(t.denominator()==1 for t in solution):
        print(solution)

edit flag offensive delete link

Comments

Hey that worked! Thanks you and much appreciated. I'm glad to know that my approach was working but I just needed the last little bit. I'll remember to utilize the .denominator in the future.

Thanks! :)

mandooo ( 2023-09-17 23:03:18 +0200 )edit

add a comment

introduction to lattices help

1 Answer

Comments

Your Answer

Question Tools

Stats

introduction to lattices help edit

1 Answer

Comments

Your Answer

Question Tools

Stats

introduction to lattices help