How to solve/crack this algorithm?
Lets say I got an encryption algorithm which consist of the following UNKNOWN
Two 4x4 matrices. Say M1 and M2.
Two vector. Say V1 and V2.
It will go through 2 rounds of encryption.
In round 1, a plaintext P1 is multiplied by the 4x4 matrix M1.... and followed by an addition of vector, V1. Which produces say R1.
( M1 x P1 ) + V1 = R1
In round 2, R1 is multiplied by another 4x4 matric, M2... and followed by an addition of vector, V2. Which end product is the encrypted text say C1.
( M2 x R1 ) + V2 = C1.
How do I solve for the unknowns?
Two 4x4 matrices. Say M1 and M2.
Two vector. Say V1 and V2.
It will go through 2 rounds of encryption.
In round 1, a plaintext P1 is multiplied by the 4x4 matrix M1.... and followed by an addition of vector, V1. Which produces say R1.
( M1 x P1 ) + V1 = R1
In round 2, R1 is multiplied by another 4x4 matric, M2... and followed by an addition of vector, V2. Which end product is the encrypted text say C1.
( M2 x R1 ) + V2 = C1.
How do I solve for the unknowns?
ASKER
Is there a "best" 10 pieces of text to use in this case?
Or any 10 pieces of text will do?
Probably I think some text need to be 0 so when it multiples it will end up having only 1 variable in it right?
Or any 10 pieces of text will do?
Probably I think some text need to be 0 so when it multiples it will end up having only 1 variable in it right?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
No, you don't need any zeros, you just need them to be different enough so that you don't get equations that are based on the other ones.
Like x = 2y and 2x = 4y
Since you won't be doing it by hand, the complexity isn't much of an issue.
Like x = 2y and 2x = 4y
Since you won't be doing it by hand, the complexity isn't much of an issue.
ASKER
Can the same method be applied on hexadecimal? Because most probably the input text will be in hexadecimal. And over galois field 2^8....
Yes. It doesn't matter. Any time you have a set of equations with N unknowns, you can solve it if you have N equations.
ASKER
I think I am not doing the right way.
You mentioned "Each encypted vector gives you 4 equations..."
Yes but I end up having 10 unknowns in each equations after I manually do those expansion!
4 equations with 10 unknown each.
You mentioned "Each encypted vector gives you 4 equations..."
Yes but I end up having 10 unknowns in each equations after I manually do those expansion!
4 equations with 10 unknown each.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Thanks, phoffric.
Exactly. Every equation technically has 40 unknowns, just some of them might not appear. But if it's using the same M1, M2, V1, and V2, then each equation has the SAME 40 unknowns. So if you collect enough equations you will be able to solve for all of them.
If you are using a different set of Ms and Vs for each piece of text, then you can't solve anything.
Exactly. Every equation technically has 40 unknowns, just some of them might not appear. But if it's using the same M1, M2, V1, and V2, then each equation has the SAME 40 unknowns. So if you collect enough equations you will be able to solve for all of them.
If you are using a different set of Ms and Vs for each piece of text, then you can't solve anything.
ASKER
Lets say if I have 8 unknowns in an equation.
Equation1: 2 * ( AB + CD + EF + GH ) = 102
Equation2: <something> * ( AB + CD + EF + GH ) = <something>
...
...
8 sets of equations. Knowing <something>, how do I find the value for A B C D E F G H ??
Equation1: 2 * ( AB + CD + EF + GH ) = 102
Equation2: <something> * ( AB + CD + EF + GH ) = <something>
...
...
8 sets of equations. Knowing <something>, how do I find the value for A B C D E F G H ??
If a variables are symmetric, then you cannot solve for them. You can only get a set of values that will work. For example 2*(AB+CD+EF+GH) = 102
This means that AB+CD+EF+GH = 51
In Equation2: 51*<something1> = <something2>
So you'll end up with the exact same thing as before.
If A never appears in anything other than AB and B only appears in AB, then A and B are symmetric variables (meaning you can swap them without changing anything) so you cannot solve for them indivudually. If Equation5 has A*B^2 or (2A+B) or something that separates them, then you can solve it. If AB shows up a lot though, you might be able to solve for it. Something like this
Say
W = AB
X = CD
Y = EF
Z = GH
Then take equations 1-4 and solve for W, X, Y, and Z.
Then take one equation from the first group and equation 5, plug in X,Y, and Z and solve for A and B
Then take eq 1 and eq 6, plug in W, Y, and Z and solve for C and D
Etc
This means that AB+CD+EF+GH = 51
In Equation2: 51*<something1> = <something2>
So you'll end up with the exact same thing as before.
If A never appears in anything other than AB and B only appears in AB, then A and B are symmetric variables (meaning you can swap them without changing anything) so you cannot solve for them indivudually. If Equation5 has A*B^2 or (2A+B) or something that separates them, then you can solve it. If AB shows up a lot though, you might be able to solve for it. Something like this
Say
W = AB
X = CD
Y = EF
Z = GH
Then take equations 1-4 and solve for W, X, Y, and Z.
Then take one equation from the first group and equation 5, plug in X,Y, and Z and solve for A and B
Then take eq 1 and eq 6, plug in W, Y, and Z and solve for C and D
Etc
ASKER
Solving these unknowns may be too tedious but is one of the way out..
Each encypted vector gives you 4 equations, so you would need to encrypt 10 pieces of text.