### Author Topic: Break this cipher! (math)  (Read 2432 times)

0 Members and 1 Guest are viewing this topic.

#### nslay

• Hero Member
• Posts: 786
• Giraffe meat, mmm
##### Break this cipher! (math)
« on: August 26, 2010, 01:46:00 PM »
NOTE: \mathbf{} is broken ... I made vectors bold but they do not appear so.

I wandered into this cipher idea accidentally last night.  This cipher is very simple, but it does not appear trivial to break.
First off, the cipher operation is a linear transformation of the form

$\mathbf{c} = M \mathbf{x}$

where $\mathbf{c} \in \mathbb{R}^n$ is the cipher text, $\mathbf{x} \in \mathbb{R}^n$ is the input block of data and $M \in \mathbb{R}^{n \times n}$ of the form

$M = PZR$

Here $P,R$ are randomly generated invertible $n \times n$ matrices and $Z$ is an $n \times n$ singular matrix of the form

$Z = n I - \mathbf{1} \mathbf{1}^T \quad \text{where } \mathbf{1} = \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \\ \end{bmatrix}$

(Sorry, $\mathbf{1}$ vector should be bold)

As a consequence, the matrix $M$ is also singular and the factorization is not unique (beyond mere scalar factors!).  However, even though $M$ is not invertible, this linear transformation can still be reversed with additional information.
Denote $\mathbf{v} \in \mathbb{R}^n$ to be the secret key either shared in advance or generated by some key agreement protocol.  Now we require the matrix $R$ to be randomly generated so that $\mathbf{v} = R^T \mathbf{1}$ (again \mathbf{} is broken, $\mathbf{1}$ should be bolded as it is a vector).  In addition to the cipher text $\mathbf{c}$, the value $k = \mathbf{v}^T \mathbf{x}$ is also provided to invert $M$.

The matrix $Z$ has the property that rows and columns sum to $0$.  I call these types of matrices zero sum matrices and they can be used to easily solve problems with summation-based constraints as unconstrained problems (an alternative to Lagrange multipliers for example).  $Z$ projects $\mathbb{R}^n$ into $\{ \mathbf{x}\ :\ \mathbf{1}^T \mathbf{x} = 0,\ \mathbf{x} \in \mathbb{R}^n \}$, the space of vectors whose components sum to $0$.  Any linear transformation with $Z$ discards the summation information of $\mathbf{x}$.  However, if the component sum of $\mathbf{x}$ is known, then this linear transformation can be inverted.  In our particular problem

$\mathbf{x} = \frac{1}{n} ( Z \mathbf{x} + \mathbf{1} (\mathbf{1}^T \mathbf{x}) )$

(Sorry, $\mathbf{1}$ vector should be bold)

So, inverting $M$ works like this:
Given $P,R,\mathbf{c},k$

1) Solve $P \mathbf{y} = \mathbf{c}$
2) Compute $\mathbf{z} = \frac{1}{n} ( \mathbf{y} + \mathbf{1} k )$ (Sorry, $\mathbf{1}$ vector should be bold)
3) Solve $R \mathbf{x} = \mathbf{z}$ to recover $\mathbf{x}$

Here's the crypto scheme:
Bob wants to securely share $\mathbf{x} \in \mathbb{R}^n$ with Alice.  Bob and Alice both have the secret key $\mathbf{v}$.

 Alice Bob $\mathbf{v}$ $\mathbf{v},\mathbf{x}$

1) Alice randomly generates invertible $P,R \in \mathbb{R}^{n \times n}$ so that $\mathbf{v} = R^T \mathbf{1}$ (Sorry, $\mathbf{1}$ vector should be bold) and computes

$M = PZR$

Alice shares $M$ with Bob.

 Alice Bob $\mathbf{v},P,R,M$ $\mathbf{v},\mathbf{x},M$

2) Bob computes $\mathbf{c} = M \mathbf{x}$ and $k = \mathbf{v}^T \mathbf{x}$ and shares $\mathbf{c},k$ with Alice

 Alice Bob $\mathbf{v},P,R,M,\mathbf{c},k$ $\mathbf{v},\mathbf{x},M,\mathbf{c},k$

3) Alice solves

$P \mathbf{y} = \mathbf{c} \mathbf{z} = \frac{1}{n} ( \mathbf{y} + \mathbf{1} k ) R \mathbf{x} = \mathbf{z}$

(Sorry, $\mathbf{1}$ vector should be bold)

to recover $\mathbf{x}$.

 Alice Bob $\mathbf{v},P,R,M,\mathbf{c},k,\mathbf{x}$ $\mathbf{v},\mathbf{x},M,\mathbf{c},k$

Example Problem:
If you have the time and interest, I'd be curious if any of you could break the following example ciphertext:

$\mathbf{c} = \begin{bmatrix} 8856 \\ -16178 \\ 246 \\ 102128 \\ 50331 \\ 110304 \\ -6464 \\ -71322 \\ -13541 \\ -45762 \\ \end{bmatrix}$

$k = 17409$

Given

$M = \begin{pmatrix} -156 & 96 & -10 & 34 & 32 & 134 & -162 & 296 & 268 & -138 \\ 148 & -178 & -30 & 78 & 224 & -452 & -124 & -38 & -254 & 474 \\ 84 & 236 & 0 & -216 & 372 & 194 & 58 & -344 & 428 & 302 \\ 572 & 148 & 570 & 42 & 216 & 352 & 94 & 88 & 174 & 156 \\ 204 & 6 & 140 & 64 & 127 & 269 & 223 & -79 & 273 & 177 \\ 336 & -56 & 440 & 216 & -142 & 496 & 372 & 224 & -178 & 58 \\ -36 & 146 & -30 & 134 & 292 & -206 & 78 & -324 & 408 & -38 \\ -358 & -262 & -290 & -18 & 186 & -318 & -176 & -52 & 164 & 146 \\ 6 & 144 & 50 & -154 & 53 & 1 & -143 & -21 & 57 & -117 \\ -58 & -12 & -440 & -68 & -334 & -268 & 34 & -82 & -466 & 86 \\ \end{pmatrix}$

Copy and paste for matlab/octave input
Code: [Select]
c = [ 8856 -16178 246 102128 50331 110304 -6464 -71322 -13541 -45762 ]';k = 17409;M = [ -156 96 -10 34 32 134 -162 296 268 -138; 148 -178 -30 78 224 -452 -124 -38 -254 474; 84 236 0 -216 372 194 58 -344 428 302; 572 148 570 42 216 352 94 88 174 156; 204 6 140 64 127 269 223 -79 273 177; 336 -56 440 216 -142 496 372 224 -178 58; -36 146 -30 134 292 -206 78 -324 408 -38; -358 -262 -290 -18 186 -318 -176 -52 164 146; 6 144 50 -154 53 1 -143 -21 57 -117; -58 -12 -440 -68 -334 -268 34 -82 -466 86 ];

#### rabbit

• x86
• Hero Member
• Posts: 8098
• I speak for the entire clan (except Joe)
##### Re: Break this cipher! (math)
« Reply #1 on: August 26, 2010, 04:17:19 PM »
This looks very interesting, but it's been years since my Linear and Number Theory classes.

#### nslay

• Hero Member
• Posts: 786
• Giraffe meat, mmm
##### Re: Break this cipher! (math)
« Reply #2 on: August 26, 2010, 05:16:46 PM »
The pseudoinverse almost gives you the input vector $\mathbf{x}$ (2% relative error ... though the residual is quite large).  However, that's due to my poorly generated matrices $P,R$ which have low variance.  If $P,R$ have a large variance, then the relative error blows up.  So, $P,R$ must be generated with care, otherwise the pseudoinverse can almost decipher $\mathbf{c}$.

#### nslay

• Hero Member
• Posts: 786
• Giraffe meat, mmm
##### Re: Break this cipher! (math)
« Reply #3 on: August 27, 2010, 10:18:12 AM »
One can also allow $Z$ to be arbitrary where
$Z = \text{diag}(\mathbf{w}) - \frac{\mathbf{w} \mathbf{w}^T}{\mathbf{1}^T \mathbf{w}} \qquad \mathbf{w} \in \mathbb{R}^n$

The vector $\mathbf{w}$ is chosen so that $R^T \mathbf{w} = \mathbf{v}$.  This allows $R$ to be random without needing adjustment as in the first post.

The cipher still works the same way
$\mathbf{c} = M \mathbf{x} k = \mathbf{v}^T \mathbf{x}$

Deciphering is modified slightly
$P \mathbf{y} = \mathbf{c} \mathbf{z} = \text{diag}(\mathbf{w})^{-1} ( \mathbf{y} + \frac{k \mathbf{w}}{\mathbf{1}^T \mathbf{w}} ) R \mathbf{x} = \mathbf{z}$