Solved

How to solve/crack this algorithm?

Posted on 2011-09-13
12
421 Views
Last Modified: 2012-08-13
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?
0
Comment
Question by:humansg
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 5
12 Comments
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36530118
Well, you have 16 unknowns in each matrix and 4 in each vector so you have 40 unknowns. All you need is 40 equations and you can solve them (using linear algebra would be the easiest).

Each encypted vector gives you 4 equations, so you would need to encrypt 10 pieces of text.
0
 

Author Comment

by:humansg
ID: 36530148
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?
0
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 300 total points
ID: 36530150
This is how you would solve the equations.
http://www.occc.edu/maustin/matrix_solutions/matrix%20solution%20of%20linear%20systems.htm

Of course, many programs exist that will do this for you such as this one.
http://www.solvemymath.com/online_math_calculator/algebra_combinatorics/system_of_equations/index.php

If you have MATLAB or Maple you could do it even more easily because you could script the whole process to get the input in there.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36530160
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.
0
 

Author Comment

by:humansg
ID: 36530195
Can the same method be applied on hexadecimal? Because most probably the input text will be in hexadecimal. And over galois field 2^8....
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36532027
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.
0
 

Author Comment

by:humansg
ID: 36534132
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.
0
 
LVL 32

Assisted Solution

by:phoffric
phoffric earned 200 total points
ID: 36534229
>> Yes but I end up having 10 unknowns in each equations after I manually do those expansion!
Interesting. Where did the other unknowns go?

>> Two 4x4 matrices. Say M1 and M2.
M1 has 4x4 entries, all unknown. That is 16 unknowns right there.

Of course if your choose vectors with lots of 0's in it, some of the unknowns get removed (and that is usually a good thing). But, as Tommy indicated, with 40 unknowns, you need 40 equations.

Not every equation has to have all 40 unknowns in it. Here is a system of equations for 2 unknowns:
x   +     y = 1
3x + 0*y = 5     // the y is really there, but with a coefficient of 0

Hope that helps till Tommy gets back.

As Tommy indicated, you need to come up with more equations if you want to solve the problem.

Good Luck!
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36536779
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.
0
 

Author Comment

by:humansg
ID: 36548674
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 ??
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 36549763
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
0
 

Author Closing Comment

by:humansg
ID: 36575087
Solving these unknowns may be too tedious but is one of the way out..
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
Businesses who process credit card payments have to adhere to PCI Compliance standards. Here’s why that’s important.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

734 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question