Ask Your Question
1

introduction to lattices help

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

mandooo gravatar image

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

1 Answer

Sort by ยป oldest newest most voted
1

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

Max Alekseyev gravatar image

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 more

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 gravatar imagemandooo ( 2023-09-17 23:03:18 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2023-09-17 11:17:03 +0200

Seen: 240 times

Last updated: Sep 17 '23