Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3447 > unrolled thread

A block encryption processing idea taken from linear algebra

Back to article view | Back to comp.programming

Contents

  A block encryption processing idea taken from linear algebra Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-06-17 09:41 +0200
    Re: A block encryption processing idea taken from linear algebra JJ <duh@nah.meh> - 2013-06-17 17:13 +0700
      Re: A block encryption processing idea taken from linear algebra Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-06-17 16:01 +0200
        Re: A block encryption processing idea taken from linear algebra JJ <duh@nah.meh> - 2013-06-18 13:03 +0700
          Re: A block encryption processing idea taken from linear algebra Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-06-18 08:43 +0200
            Re: A block encryption processing idea taken from linear algebra JJ <duh@nah.meh> - 2013-06-18 18:12 +0700
              Re: A block encryption processing idea taken from linear algebra Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-06-18 15:08 +0200
                Re: A block encryption processing idea taken from linear algebra JJ <duh@nah.meh> - 2013-06-19 15:53 +0700

#3447 — A block encryption processing idea taken from linear algebra

The iterative solution of a system of n linear equations can be
formulated as follows:

x1 := a11*x1 + a12*x2 + ... + a1n*xn + b1
x2 := a21*x1 + a22*x2 + ... + a2n*xn + b2
    .....................
xn := an1*x1 + an2*x2 + ... + ann*xn + bn

where (in the so-called single-step method) the assignments are
performed sequentially. See V. N. Faddeeva, Computational Methods of
Linear Algebra, p.117, Dover Publ., 1959. (Note that many textbooks
of linear algebra present however a different, in fact less general,
formulation.)

Using this as a hint, we propose to do for block encryption processing
of n blocks, x1, x2, ... xn, the follwoing, where the f's are
invertible non-linear functions, the r's are pseudo-random numbers and
the assignments are performed sequentially (the f's and the r's are
(secret) key-dependent and different for different rounds, if more
then one rounds are used):

x1 := f1(x1 + x2 ... + xn + r1)
x2 := f2(x1 + x2 ... + xn + r2)
    ................
xn := fn(x1 + x2 ... + xn + rn)

Note that we have left out the multiplication with a's, which is
deemed a justifiable simplicity since the f's are non-linear and
further the r's are pseudo-random. Note also that the effect of
block-chaining in the use of the common block ciphers is intrinsically
present in our scheme. A viable variant of the scheme is to employ
^r instead of +r.

M. K. Shen

[toc] | [next] | [standalone]

#3448

On Mon, 17 Jun 2013 09:41:14 +0200, Mok-Kong Shen wrote:
> Using this as a hint, we propose to do for block encryption processing
> of n blocks, x1, x2, ... xn, the follwoing, where the f's are
> invertible non-linear functions, the r's are pseudo-random numbers and
> the assignments are performed sequentially (the f's and the r's are
> (secret) key-dependent and different for different rounds, if more
> then one rounds are used):
> 
> x1 := f1(x1 + x2 ... + xn + r1)
> x2 := f2(x1 + x2 ... + xn + r2)
>     ................
> xn := fn(x1 + x2 ... + xn + rn)

I'm lost. If n is the number of blocks, then xn is the block number n,
right?

But this:
x1 + x2 ... + xn + r1
suggest to add one block with another then add them with a random number.

How can a block of data be, I assume, arithmetically be added by another
block and added with a number?

Also... with that information alone, the encryption doesn't seem to be
decryptable.

[toc] | [prev] | [next] | [standalone]

#3449

Am 17.06.2013 12:13, schrieb JJ:
> On Mon, 17 Jun 2013 09:41:14 +0200, Mok-Kong Shen wrote:
>> Using this as a hint, we propose to do for block encryption processing
>> of n blocks, x1, x2, ... xn, the follwoing, where the f's are
>> invertible non-linear functions, the r's are pseudo-random numbers and
>> the assignments are performed sequentially (the f's and the r's are
>> (secret) key-dependent and different for different rounds, if more
>> then one rounds are used):
>>
>> x1 := f1(x1 + x2 ... + xn + r1)
>> x2 := f2(x1 + x2 ... + xn + r2)
>>      ................
>> xn := fn(x1 + x2 ... + xn + rn)
>
> I'm lost. If n is the number of blocks, then xn is the block number n,
> right?
>
> But this:
> x1 + x2 ... + xn + r1
> suggest to add one block with another then add them with a random number.
>
> How can a block of data be, I assume, arithmetically be added by another
> block and added with a number?
>
> Also... with that information alone, the encryption doesn't seem to be
> decryptable.

If the block size is m bits, then the arithmetics is mod 2**m. If the
f's are invertible, then decryption is evidently without problems,
just like each step of the iterative solution of a system of linear
equations could be reversed (though one of course never does that in
practice).

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#3450

On Mon, 17 Jun 2013 16:01:09 +0200, Mok-Kong Shen wrote:
> Am 17.06.2013 12:13, schrieb JJ:
>> On Mon, 17 Jun 2013 09:41:14 +0200, Mok-Kong Shen wrote:
>>> Using this as a hint, we propose to do for block encryption processing
>>> of n blocks, x1, x2, ... xn, the follwoing, where the f's are
>>> invertible non-linear functions, the r's are pseudo-random numbers and
>>> the assignments are performed sequentially (the f's and the r's are
>>> (secret) key-dependent and different for different rounds, if more
>>> then one rounds are used):
>>>
>>> x1 := f1(x1 + x2 ... + xn + r1)
>>> x2 := f2(x1 + x2 ... + xn + r2)
>>>      ................
>>> xn := fn(x1 + x2 ... + xn + rn)
>>
>> I'm lost. If n is the number of blocks, then xn is the block number n,
>> right?
>>
>> But this:
>> x1 + x2 ... + xn + r1
>> suggest to add one block with another then add them with a random number.
>>
>> How can a block of data be, I assume, arithmetically be added by another
>> block and added with a number?
>>
>> Also... with that information alone, the encryption doesn't seem to be
>> decryptable.
> 
> If the block size is m bits, then the arithmetics is mod 2**m. If the
> f's are invertible, then decryption is evidently without problems,
> just like each step of the iterative solution of a system of linear
> equations could be reversed (though one of course never does that in
> practice).

Assuming I take out the r1, r2, etc. (the salt) from the equation, the
result would be:

x1 := f1(x1 + x2 ... + xn)
x2 := f2(x1 + x2 ... + xn)
     ................
xn := fn(x1 + x2 ... + xn)

It would make all block data to be same as the first block. It'll destroy
the data and keep only the first block.

Something is definitely missing here.

[toc] | [prev] | [next] | [standalone]

#3451

Am 18.06.2013 08:03, schrieb JJ:
> On Mon, 17 Jun 2013 16:01:09 +0200, Mok-Kong Shen wrote:
>> Am 17.06.2013 12:13, schrieb JJ:
>>> On Mon, 17 Jun 2013 09:41:14 +0200, Mok-Kong Shen wrote:
>>>> Using this as a hint, we propose to do for block encryption processing
>>>> of n blocks, x1, x2, ... xn, the follwoing, where the f's are
>>>> invertible non-linear functions, the r's are pseudo-random numbers and
>>>> the assignments are performed sequentially (the f's and the r's are
>>>> (secret) key-dependent and different for different rounds, if more
>>>> then one rounds are used):
>>>>
>>>> x1 := f1(x1 + x2 ... + xn + r1)
>>>> x2 := f2(x1 + x2 ... + xn + r2)
>>>>       ................
>>>> xn := fn(x1 + x2 ... + xn + rn)
>>>
>>> I'm lost. If n is the number of blocks, then xn is the block number n,
>>> right?
>>>
>>> But this:
>>> x1 + x2 ... + xn + r1
>>> suggest to add one block with another then add them with a random number.
>>>
>>> How can a block of data be, I assume, arithmetically be added by another
>>> block and added with a number?
>>>
>>> Also... with that information alone, the encryption doesn't seem to be
>>> decryptable.
>>
>> If the block size is m bits, then the arithmetics is mod 2**m. If the
>> f's are invertible, then decryption is evidently without problems,
>> just like each step of the iterative solution of a system of linear
>> equations could be reversed (though one of course never does that in
>> practice).
>
> Assuming I take out the r1, r2, etc. (the salt) from the equation, the
> result would be:
>
> x1 := f1(x1 + x2 ... + xn)
> x2 := f2(x1 + x2 ... + xn)
>       ................
> xn := fn(x1 + x2 ... + xn)
>
> It would make all block data to be same as the first block. It'll destroy
> the data and keep only the first block.
>
> Something is definitely missing here.

Why would it make all blocks the same? Note that the assigments
are done "sequentially". (Cf. what is generally known as the
Gauss-Seidel (or single-step) method of iterative solutions
of systems of linear equations.) For example, for the 2nd assignment
the x1 in f2() is already the "new" value determined by the 1st
assignment.

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#3452

On Tue, 18 Jun 2013 08:43:10 +0200, Mok-Kong Shen wrote:

> Am 18.06.2013 08:03, schrieb JJ:
>> On Mon, 17 Jun 2013 16:01:09 +0200, Mok-Kong Shen wrote:
>>> Am 17.06.2013 12:13, schrieb JJ:
>>>> On Mon, 17 Jun 2013 09:41:14 +0200, Mok-Kong Shen wrote:
>>>>> Using this as a hint, we propose to do for block encryption processing
>>>>> of n blocks, x1, x2, ... xn, the follwoing, where the f's are
>>>>> invertible non-linear functions, the r's are pseudo-random numbers and
>>>>> the assignments are performed sequentially (the f's and the r's are
>>>>> (secret) key-dependent and different for different rounds, if more
>>>>> then one rounds are used):
>>>>>
>>>>> x1 := f1(x1 + x2 ... + xn + r1)
>>>>> x2 := f2(x1 + x2 ... + xn + r2)
>>>>>       ................
>>>>> xn := fn(x1 + x2 ... + xn + rn)
>>>>
>>>> I'm lost. If n is the number of blocks, then xn is the block number n,
>>>> right?
>>>>
>>>> But this:
>>>> x1 + x2 ... + xn + r1
>>>> suggest to add one block with another then add them with a random number.
>>>>
>>>> How can a block of data be, I assume, arithmetically be added by another
>>>> block and added with a number?
>>>>
>>>> Also... with that information alone, the encryption doesn't seem to be
>>>> decryptable.
>>>
>>> If the block size is m bits, then the arithmetics is mod 2**m. If the
>>> f's are invertible, then decryption is evidently without problems,
>>> just like each step of the iterative solution of a system of linear
>>> equations could be reversed (though one of course never does that in
>>> practice).
>>
>> Assuming I take out the r1, r2, etc. (the salt) from the equation, the
>> result would be:
>>
>> x1 := f1(x1 + x2 ... + xn)
>> x2 := f2(x1 + x2 ... + xn)
>>       ................
>> xn := fn(x1 + x2 ... + xn)
>>
>> It would make all block data to be same as the first block. It'll destroy
>> the data and keep only the first block.
>>
>> Something is definitely missing here.
> 
> Why would it make all blocks the same? Note that the assigments
> are done "sequentially". (Cf. what is generally known as the
> Gauss-Seidel (or single-step) method of iterative solutions
> of systems of linear equations.) For example, for the 2nd assignment
> the x1 in f2() is already the "new" value determined by the 1st
> assignment.

OK, step by step, using live data. Assume:

fx(x) = x XOR 0xFF
x1 = 0x01
x2 = 0x02

Encryption step 1:
x1 = fx(x1 + x2)
   = fx(0x01 + 0x02)
   = fx(0x03)
   = 0x03 XOR 0xFF
   = 0xFC

Encryption step 2:
x2 = fx(x1 + x2)
   = fx(0xFC + 0x02)
   = fx(0xFE)
   = 0xFE XOR 0xFF
   = 0x01

Encryption result:
x1 = 0xFC
x2 = 0x01

Decryption step 1:
x1 = fx(x1 + x2)
   = fx(0xFC + 0x01)
   = fx(0xFD)
   = 0xFD XOR 0xFF
   = 0x02

Decryption step 2:
x2 = fx(x1 + x2)
   = fx(0x02 + 0x01)
   = fx(0x03)
   = 0x03 XOR 0xFF
   = 0xFC

Decryption result:
x1 = 0x02
x2 = 0xFC

So...?

[toc] | [prev] | [next] | [standalone]

#3453

Am 18.06.2013 13:12, schrieb JJ:
> On Tue, 18 Jun 2013 08:43:10 +0200, Mok-Kong Shen wrote:
>
>> Am 18.06.2013 08:03, schrieb JJ:
>>> On Mon, 17 Jun 2013 16:01:09 +0200, Mok-Kong Shen wrote:
>>>> Am 17.06.2013 12:13, schrieb JJ:
>>>>> On Mon, 17 Jun 2013 09:41:14 +0200, Mok-Kong Shen wrote:
>>>>>> Using this as a hint, we propose to do for block encryption processing
>>>>>> of n blocks, x1, x2, ... xn, the follwoing, where the f's are
>>>>>> invertible non-linear functions, the r's are pseudo-random numbers and
>>>>>> the assignments are performed sequentially (the f's and the r's are
>>>>>> (secret) key-dependent and different for different rounds, if more
>>>>>> then one rounds are used):
>>>>>>
>>>>>> x1 := f1(x1 + x2 ... + xn + r1)
>>>>>> x2 := f2(x1 + x2 ... + xn + r2)
>>>>>>        ................
>>>>>> xn := fn(x1 + x2 ... + xn + rn)
>>>>>
>>>>> I'm lost. If n is the number of blocks, then xn is the block number n,
>>>>> right?
>>>>>
>>>>> But this:
>>>>> x1 + x2 ... + xn + r1
>>>>> suggest to add one block with another then add them with a random number.
>>>>>
>>>>> How can a block of data be, I assume, arithmetically be added by another
>>>>> block and added with a number?
>>>>>
>>>>> Also... with that information alone, the encryption doesn't seem to be
>>>>> decryptable.
>>>>
>>>> If the block size is m bits, then the arithmetics is mod 2**m. If the
>>>> f's are invertible, then decryption is evidently without problems,
>>>> just like each step of the iterative solution of a system of linear
>>>> equations could be reversed (though one of course never does that in
>>>> practice).
>>>
>>> Assuming I take out the r1, r2, etc. (the salt) from the equation, the
>>> result would be:
>>>
>>> x1 := f1(x1 + x2 ... + xn)
>>> x2 := f2(x1 + x2 ... + xn)
>>>        ................
>>> xn := fn(x1 + x2 ... + xn)
>>>
>>> It would make all block data to be same as the first block. It'll destroy
>>> the data and keep only the first block.
>>>
>>> Something is definitely missing here.
>>
>> Why would it make all blocks the same? Note that the assigments
>> are done "sequentially". (Cf. what is generally known as the
>> Gauss-Seidel (or single-step) method of iterative solutions
>> of systems of linear equations.) For example, for the 2nd assignment
>> the x1 in f2() is already the "new" value determined by the 1st
>> assignment.
>
> OK, step by step, using live data. Assume:
>
> fx(x) = x XOR 0xFF
> x1 = 0x01
> x2 = 0x02
>
> Encryption step 1:
> x1 = fx(x1 + x2)
>     = fx(0x01 + 0x02)
>     = fx(0x03)
>     = 0x03 XOR 0xFF
>     = 0xFC
>
> Encryption step 2:
> x2 = fx(x1 + x2)
>     = fx(0xFC + 0x02)
>     = fx(0xFE)
>     = 0xFE XOR 0xFF
>     = 0x01
>
> Encryption result:
> x1 = 0xFC
> x2 = 0x01
>
> Decryption step 1:
> x1 = fx(x1 + x2)
>     = fx(0xFC + 0x01)
>     = fx(0xFD)
>     = 0xFD XOR 0xFF
>     = 0x02
>
> Decryption step 2:
> x2 = fx(x1 + x2)
>     = fx(0x02 + 0x01)
>     = fx(0x03)
>     = 0x03 XOR 0xFF
>     = 0xFC
>
> Decryption result:
> x1 = 0x02
> x2 = 0xFC
>
> So...?
>

Ah, if you have really understood the iterative processing, you
would know that reversing it must be done in such a way that the
"entire" processing is exactly reversed "step by step". That means
on decryption in your example you have to first reverse the 2nd
assignment and then the first assignment. So:

Decryption step 1:
x2  = fx(x1 + x2)
     = fx(0xFC + 0x01)
     = fx(0xFD)
     = 0xFD XOR 0xFF
     = 0x02

Decryption step 2:
x1 = fx(x1 + x2)
    = fx(0xFC + 0x02)
    = fx(0xFE)
    = 0xFE XOR 0xFF
    = 0x01

Decryption result:
x1 = 0x01
x2 = 0x02

OK?

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#3463

On Tue, 18 Jun 2013 15:08:06 +0200, Mok-Kong Shen wrote:
>> OK, step by step, using live data. Assume:
>>
>> fx(x) = x XOR 0xFF
>> x1 = 0x01
>> x2 = 0x02
>>
>> Encryption step 1:
>> x1 = fx(x1 + x2)
>>     = fx(0x01 + 0x02)
>>     = fx(0x03)
>>     = 0x03 XOR 0xFF
>>     = 0xFC
>>
>> Encryption step 2:
>> x2 = fx(x1 + x2)
>>     = fx(0xFC + 0x02)
>>     = fx(0xFE)
>>     = 0xFE XOR 0xFF
>>     = 0x01
>>
>> Encryption result:
>> x1 = 0xFC
>> x2 = 0x01
>>
>> Decryption step 1:
>> x1 = fx(x1 + x2)
>>     = fx(0xFC + 0x01)
>>     = fx(0xFD)
>>     = 0xFD XOR 0xFF
>>     = 0x02
>>
>> Decryption step 2:
>> x2 = fx(x1 + x2)
>>     = fx(0x02 + 0x01)
>>     = fx(0x03)
>>     = 0x03 XOR 0xFF
>>     = 0xFC
>>
>> Decryption result:
>> x1 = 0x02
>> x2 = 0xFC
>>
>> So...?
>>
> 
> Ah, if you have really understood the iterative processing, you
> would know that reversing it must be done in such a way that the
> "entire" processing is exactly reversed "step by step". That means
> on decryption in your example you have to first reverse the 2nd
> assignment and then the first assignment. So:
> 
> Decryption step 1:
> x2  = fx(x1 + x2)
>      = fx(0xFC + 0x01)
>      = fx(0xFD)
>      = 0xFD XOR 0xFF
>      = 0x02
> 
> Decryption step 2:
> x1 = fx(x1 + x2)
>     = fx(0xFC + 0x02)
>     = fx(0xFE)
>     = 0xFE XOR 0xFF
>     = 0x01
> 
> Decryption result:
> x1 = 0x01
> x2 = 0x02
> 
> OK?

OK, I see now. That's pretty uncommon. Most decryptions/decompressions don't
do it backwards when undoing the process.

I might have figure it out earlier if I'm not suck at math. -_-

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web