0x0000 = 2^16?

Forum Attachments

0x0000 = 2^16?

calccrypto 30 Aug 2009 00:41

in the IDEA algorithm, the multiplication function has a special "condition" of a sort: Multiplication modulo 2^16+1, where the all-zero word (0x0000) is interpreted as 2^16. i dont get it. when i put that into my program, everything after the first part of the first output is wrong. what should i do? IDEA works with groups of 16 bits/4 hex chars, but having 2^16 as a possibility allows for a 17th bit to be introduced that can't be xored out

---

from http://www.ussrback.com/crypto/libraries/idea/idea-algorithm.txt
i think this is the part where the 0s become 2^16
can someone translate this into words?

u_int16 mul(u_int16 x, u_int16 y)
{
    u_int32 p=x*y;

    if (p == 0)
        x = 65537-x-y;
    else {
        x = p >> 16;
        y = p;
        x = y-x;

        if (y < x) x += 65537;
    }
    return x;
}

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 30 Aug 2009 05:42 by calccrypto Show more

Re: 0x0000 = 2^16?

DarkerLine 30 Aug 2009 05:39

Okay. Here is how it works.

First line takes the 32-bit product of x*y. Now we want to take this mod 2¹⁶ + 1…

…but first we have to take care of the case where x=0 or y=0 (in which case we multiplied by 0 when we should've been multiplying by -1). If this was the case, then the product p will be 0 — this is what the if statement checks for. In that case, 65537-x-y is the correct answer because (x+y) will be either 0+y=y, if x was 0, or x+0=x if y was 0, and 65537 minus that takes multiplies it by -1 or 2¹⁶ mod 2¹⁶+1.

Otherwise, we're fine to take the mod. x=p>>16 and y=p take the highest 16 bits and lowest 16 bits of p, respectively. Normally, subtracting these gives the correct answer of p mod 2¹⁶+1.

The problem occurs if there's a carry during the subtraction, for instance if x=y-x subtracted 17 from 3 which would become 2¹⁶-(17-3) = 65522. This is checked for by the line if (y<x), since this can only happen if there was a carry. The reason this is a problem is that the carry wraps around mod 2¹⁶, whereas we want things to wrap around mod 2¹⁶+1. This is fixed by adding 1 to x, which for some reason the author of that code wrote as adding 65537 to x: this doesn't make a difference, though, since 65537 is 0x10001 which gets truncated to 0x0001 anyway.

There's no special code to make sure that the case of x*y = 2¹⁶ (which needs to be written as 0x0000) gets treated correctly. But we don't need it. If we accept that we calculate p mod 2¹⁶+1 right, then if p mod 2¹⁶+1 = 2¹⁶, the correct answer will be 2¹⁶. But this is stored as 0x10000 in the 16-bit variable x, so it will get truncated to 0x0000.

Re: 0x0000 = 2^16?

calccrypto 30 Aug 2009 17:21

err…. ?
i typed up something that looks like the code, and the answers are all over the place, and completely wrong

go here, click IDEA (in the middle of the page, not the side), and go to the bottom with the java applet, and click "ok". the boxes are the intermediate answers. the last boxes are the pieces of the final answer.

key = 00010002000300040005000600070008
data = 0000000100020003
output = 11fbed2b01986de5

0000 0001 0002 0003
100d2 00d7 00e5 00ea
839fe76 83eff24 5368 5284c
62b78e27e3 49498 bbd1 a503b45
9412c1894df aa8db 060d 2940516d
1722d71a1478656 918b8e5 fc28 a500a0b0f56
22b41ff2dc0d7dfb54 45ca4 9f47 527ffdd82e2db
681bf7bc344f49bad18 ac7aaae 7160 1eefe0411222c8f

1a06e3e80f24c5523fe40ff 8de1a525 ed4c 1355d8d2bf2d124e3c5
this is wrong

this is right up to the line, without the code from above

0000 0001 0002 0003
00f0 00f5 010a 0105
222f 21b5 f45e e959
0f86 39be 8ee8 1173
57df ac58 c65b ba4d
8e81 ba9c f77f 3a4a
6942 9409 e21b 1c64
-------------------
6594 3bb2 4d90 7caf
0bb0 20bc 5756 def7

d7fb581621bcb3aa

however, when there are no 0s involved, the answers are all right

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 30 Aug 2009 17:22 by calccrypto Show more

Re: 0x0000 = 2^16?

DarkerLine 30 Aug 2009 17:37

What you typed up is probably wrong because you didn't take into account the variable types. Both x and y (and therefore the return value) are 16-bit, so the final result, as well as several intermediate results get truncated mod 2¹⁶ (which I personally think is a bit of a hacky way to go about doing things, but I didn't write that code). If you didn't specify the variable types in the same way as that code does, it won't work correctly.

Re: 0x0000 = 2^16?

calccrypto 30 Aug 2009 17:55

i used a,b, and p

wait… variable type? like list/number/string ?

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 30 Aug 2009 18:07 by calccrypto Show more

Re: 0x0000 = 2^16?

DarkerLine 30 Aug 2009 18:40

A bit more specific than number. "u_int16" refers to an unsigned 16-bit integer. This means that it can only store numbers between 0 and 2¹⁶-1, and will truncate everything else to fit in that range.

Re: 0x0000 = 2^16?

calccrypto 30 Aug 2009 20:13

oh… i dont think python has signed/unsigned numbers. if it does, i have no idea how to use them. and if the numbers get truncated, isnt that just modding by 2^16?

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: 0x0000 = 2^16?

DarkerLine 30 Aug 2009 21:41

Yes, but you have to do it yourself instead of letting the compiler (well, interpreter in the case of python) do it for you.

If you're not trying to work with specific bit sizes or optimize calculations, you could just do the obvious thing:

if (x == 0)
    x = 65536;
if (y == 0)
    y = 65536;

x = (x*y) % 65537;

if (x == 65536)
    x = 0;

return x;

Re: 0x0000 = 2^16?

calccrypto 30 Aug 2009 21:57

wow. i fail.

that did the trick

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: 0x0000 = 2^16?

simplethinker 31 Aug 2009 01:50

In Python, integers are 32-bit (31 for the number and 1 for the sign), long integers have unlimited precision. Information for floats is platform dependent, but using sys.float_info will give you the maximum values, and using sys.getsizeof() on a float should give you the size.