Seemingly Simple Summation

calccrypto · 2010-06-19 08:53:08

given the values

#Values are in hex
c1                      124bcb676f4f39395d883fb0f19ea3c66        # i got this
c2                      1366165d05266af8cdb6aa27e1079e6d7        # i got this
# so, in this case, q = 2
r                       48443d0bb0d21109c89a100b5ce2c208         # given
m(r) mod (2^130 - 5)    1cfb6f98add6a0ea7c631de020225cc8b        # i am not getting this
AES_k(n)                83149c69b561dd88298a1798b10716ef         # i got this

and the equation

can someone please tell me what the output is?

a paper (http://cr.yp.to/mac/poly1305-20050329.pdf) is giving me problems with this. the answer is supposed to be 0ee1c16bb73f0f4fd19881753c01cdbe

Last edited by calccrypto (2010-06-19 09:08:25)

bobbym · 2010-06-19 10:15:47

Hi Cal;

Where is there a single example to demonstrate the algorithm in that paper?

He makes a strange statement inasmuch as when he mods certain values by 2^130 - 5 , he doesn't reduce down to the smallest remainder. Just a remainder that is small enough to continue the computation.

Example:

100 mod 23 = 8 but he can do something like this 100 - 23 = 77 - 23 = 54 - 23 = 31 stop. This mods the number by repeated subtraction but he stops at 31 because he deems it small enough to continue. This is just for an example but it is one problem to consider. Did he do that here? It shouldn't affect the final answer if you mod at the end...

m(r) mod (2^130 - 5) 1cfb6f98add6a0ea7c631de020225cc8b # i am not getting this

What do you do for m(r)?

calccrypto · 2010-06-19 13:25:53

Hi bobbym

the examples are at the very end of the paper, where the weird grid/tables are

and i have no idea why he doesnt reduce to the smallest number. i havent really read the analysis yet (maybe something with fitting the values into 4 32 bit registers?)

as for m(r), i just used the equation in the first post, since its the only equation that remotely makes sense to use

Last edited by calccrypto (2010-06-19 14:45:43)

bobbym · 2010-06-19 15:52:41

Hi calccrypto;

This is what I am getting:

What did you get?

calccrypto · 2010-06-19 16:14:30

im getting 43586ce55792075e53a953450d024f6d too. so what in the world is this guy talking about???

bobbym · 2010-06-19 16:29:35

Hi calccrypto;

I don't know, I wasn't too impressed with the paper. Do any of the other examples work?

calccrypto · 2010-06-19 17:30:09

c1                                         00000000000000000000000000001f6f3
r                                          85 1f c4 0c 34 67 ac 0b e0 5c c2 04 04 f3 f7 00
m(r) mod 2130 - 5                          321e58e25a69d7f8f27060770b3f8bb9c
k                                          ec 07 4c 83 55 80 74 17 01 42 5b 62 32 35 ad d6
n                                          fb 44 73 50 c4 e8 68 c5 2a c3 27 5c f9 d4 32 7e
AESk(n)                                    58 0b 3b 0f 94 47 bb 1e 69 d0 95 b5 92 8b 6d bc
Poly1305r(m; AESk(n))                      f4 c6 33 c3 04 4f c1 45 f8 4f 33 5c b8 19 53 de



c1                                         1d1944d37edcb4227341e7f4a721208ab
c2                                         1f0fa9144c0f2309881b3455d79b8c636
c3                                         167cb3431faa0e4c3b218808be4620c99
c4                                         001f91b5c0921cbc461d994c958e183fa
r                                          12 97 6a 08 c4 42 6d 0c e8 a8 24 07 c4 f4 82 07
m(r) mod 2130 - 5                          0c3c4f37c464bbd44306c9f8502ea5bd1
k                                          e1 a5 66 8a 4d 5b 66 a5 f6 8c c5 42 4e d5 98 2d
n                                          9a e8 31 e7 43 97 8d 3a 23 52 7c 71 28 14 9e 3a
AESk(n)                                    80 f8 c2 0a a7 12 02 d1 e2 91 79 cb cb 55 5a 57
Poly1305r(m; AESk(n))                      51 54 ad 0d 2c b2 6e 01 27 4f c5 11 48 49 1f 1b

bobbym · 2010-06-19 17:54:03

Hi;

I tried the one on the bottom with c1,c2,c3,c4 it didn't work either. I am beginning to think we are doing something wrong.

calccrypto · 2010-06-20 04:46:03

arrgghhh! why are crypto related papers so annoying????

bobbym · 2010-06-20 05:16:25

Hi calccrypto;

Do you notice how he has r represented?

r 12 97 6a 08 c4 42 6d 0c e8 a8 24 07 c4 f4 82 07

It is by byte. Does he want us to m(r) it byte by byte? Like this:

m(12) then m(97) etc. But what do we do with each one then?

calccrypto · 2010-06-20 05:20:03

ooohhh... maybe. i'll check

bobbym · 2010-06-20 05:25:00

I've have read it again, it seems to suggest that but I am the worst at understanding someone else's code. I always just rewrite it. Nothing clear in his bad explanations.

calccrypto · 2010-06-20 05:26:49

nope.
im looking at this other guy's code, and somehow he's getting the correct answer even though it looks like im doing the same thing as he is:

  tot = 0
  for i in range(q):
    sub = msg[i*16 : i*16+16] + "\x01"              # [backwards(0124bcb676f4f39395d883fb0f19ea3c66),  backwards( 01366165d05266af8cdb6aa27e1079e6d7)]
    sub += (17 - len(sub)) * "\x00"
    num = str2num_littleend(sub)          # c1       =  0x124bcb676f4f39395d883fb0f19ea3c66,            c2       =  0x1366165d05266af8cdb6aa27e1079e6d7
    tot = (tot + num) * rval                        # same as c1 * r^q + c2 * r^(q-1)+ ... cq*r right?
  tot = tot % mod1305

calccrypto · 2010-06-20 05:34:29

oh. whoops. i forgot to change r to little endian. wow. i fail

edit:

what an annoying person. this guy changes the values to little endian so many times its not even funny

Last edited by calccrypto (2010-06-20 05:37:20)

bobbym · 2010-06-20 05:42:13

I know that we are doing what the paper says to do. I don't understand how he is getting his answers.
There are supposed to be more examples on another page.

calccrypto · 2010-06-20 07:45:48

i finally figured it out:
change r to little endian
do the equation i put in the first post
add the little endian of AES_k(n) and mod 2^128
change to little endian

bobbym · 2010-06-20 14:31:52

Hi calccrypto;

Glad you got it. You understood the paper better than I did.

calccrypto · 2010-06-20 17:31:22

Thanks for your help bobbym

bobbym · 2010-06-20 17:34:11

Hi;

You did it by yourself, thanks for the info and the pdf!

Math Is Fun Forum

#1 2010-06-19 08:53:08

Seemingly Simple Summation

#2 2010-06-19 10:15:47

Re: Seemingly Simple Summation

#3 2010-06-19 13:25:53

Re: Seemingly Simple Summation

#4 2010-06-19 15:52:41

Re: Seemingly Simple Summation

#5 2010-06-19 16:14:30

Re: Seemingly Simple Summation

#6 2010-06-19 16:29:35

Re: Seemingly Simple Summation

#7 2010-06-19 17:30:09

Re: Seemingly Simple Summation

#8 2010-06-19 17:54:03

Re: Seemingly Simple Summation

#9 2010-06-20 04:46:03

Re: Seemingly Simple Summation

#10 2010-06-20 05:16:25

Re: Seemingly Simple Summation

#11 2010-06-20 05:20:03

Re: Seemingly Simple Summation

#12 2010-06-20 05:25:00

Re: Seemingly Simple Summation

#13 2010-06-20 05:26:49

Re: Seemingly Simple Summation

#14 2010-06-20 05:34:29

Re: Seemingly Simple Summation

#15 2010-06-20 05:42:13

Re: Seemingly Simple Summation

#16 2010-06-20 07:45:48

Re: Seemingly Simple Summation

#17 2010-06-20 14:31:52

Re: Seemingly Simple Summation

#18 2010-06-20 17:31:22

Re: Seemingly Simple Summation

#19 2010-06-20 17:34:11

Re: Seemingly Simple Summation

Board footer