# Re: Need some simple bijective mappings

*From*: Tran Ngoc Duong <tranngocduong@xxxxxxxxx>*Date*: Thu, 17 Jun 2010 00:13:27 -0700 (PDT)

On 17 Tháng Sáu, 12:21, Maaartin <grajc...@xxxxxxxxx> wrote:

On Jun 17, 5:45 am, Tran Ngoc Duong <tranngocdu...@xxxxxxxxx> wrote:And, on any architecture, if memory is not a very concern one may

On Jun 16, 7:59 pm, Maaartin <grajc...@xxxxxxxxx> wrote:

Right. Could you give me a reference in the literature?

I'm afraid I can't. Personally, I observed the group property myself

some time around 1994, when I was impressed by the "no S-boxes"

concept of the IDEA block cipher, and tried to "design" something like

it for 32-bit machines. The group property of 2*x*y + y + z came to me

first. When I found the isomorphism to the multiplicative group of odd

integers, generalization to (1<<m)*k*x*y + x + y followed easily. As

an undergraduate student without formal math-phys trainings, within my

(very limited) knowledge, I was not aware of such references in

literature. I'm not aware of that even now, too.

I ask only because I thought, there can be more information there. I

was impressed by IDEA, too, and I still wonder why it uses its

pseudomultiplication instead of something like 2*x*y+x+y, which can be

written as x + (2*x+1) * y, and executed using only 3 instructions on

x86 architectures using LEA.

precompute 2*x + 1 to save one instruction, as M. K. Shen has pointed

out.

I think Lai & Massey's decision for multiplication mod (2^n + 1),

rather than something like 2*x*y + x + y, was a right decision, after

balancing between implementation complication and mathematical

complexity (aka, level of "confusion").

Integer multiplication those days was very time-consuming in

comparison to addition and jumps, so from the implementation view the

two operations are, in essence, equally complicated. From the

mathematical view, on the other hand, multiplication mod (2^n +1) is

better since it is more "confusing". If my memory serves, Lai has

proved that the multiplication mod (2^16 + 1), unlike 2*x*y+x+y,

cannot be written as a polynomial over the ring Z(2^16). And maybe it

is superior to 2*x*y+x+y with respect to differential characteristics

(in relevant definitions of the "difference"), I think.

.

**Follow-Ups**:**Re: Need some simple bijective mappings***From:*Maaartin

**References**:**Need some simple bijective mappings***From:*Mok-Kong Shen

**Re: Need some simple bijective mappings***From:*Tran Ngoc Duong

**Re: Need some simple bijective mappings***From:*Maaartin

**Re: Need some simple bijective mappings***From:*Tran Ngoc Duong

**Re: Need some simple bijective mappings***From:*Mok-Kong Shen

**Re: Need some simple bijective mappings***From:*Tran Ngoc Duong

**Re: Need some simple bijective mappings***From:*Maaartin

**Re: Need some simple bijective mappings***From:*Tran Ngoc Duong

**Re: Need some simple bijective mappings***From:*Maaartin

- Prev by Date:
**Semiautomatic Hybrid Block_Stream Cipher** - Next by Date:
**Re: Need some simple bijective mappings** - Previous by thread:
**Re: Need some simple bijective mappings** - Next by thread:
**Re: Need some simple bijective mappings** - Index(es):