Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?

[Mouse <mouse%Rodents-Montreal.ORG@localhost>]

>> I'd encourage you to do the derivation again: compute

>> 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }

>> and verify that it's prime.

Or, at least, that it's probably prime.

> That assumes that (a) my calculation of that (what on earth is "{
> [2^1918 pi] + 124476 }", for example?)

Take pi, multiply by the 1918th power of two, discard the fractional
part, and add 124476.  Or, at least, that's what I'd read it as.

This means computing pi to nearly two thousand bits of precision (or
finding a reference value you trust enough), but that's really the only
hard part.

> will be correct, and (b) my overall calculations will also be
> correct, which is more or less the thing I'm trying to avoid: I'd
> like an independent check on the values so that if I've messed up
> anywhere, I can detect it.

Well, if you get the same thing the RFC specifies, that's reasonable
confirmation you've done the calculation correctly.

> Getting a hash of the byte string seems to be the easiest way to do
> this.

Not just computing it and comparing it against the value in RFC3526?

> Speaking of doing the derivation again, do we know if anyone's
> actually tried to reproduce the values given in the RFC?  I'm
> assuming it came from something like Mathematica which I don't have
> directly available, and Mathics gives me, for '2^2048 - 2^1984 - 1 +
> 2^64 * ((2^1918 * pi) + 124476)' the not terribly helpful:

Few general-purpose calculator programs will actually compute pi to the
necessary number of places.  I know of someone who tried such a thing
and got a wrong result which turned out to match the value resulting
from using the irrational number in question (pi, sqrt(2), whatever it
was) truncated to IEEE double precision.

> [...]
> which if fed to bc as:
> [...]+[...]*(124476+[...]*pi)
> is reported to be:
> [...]
> which is:
> 0xffffffffffffffff000000000000000000000000000000000000000
> 000
> 000000000000000000000000000000000000000000000000000000000000000000000000000000
> 000000000000000000000000000000000000000000000000000000000000000000000000000000
> 000000000000000000000000000000000000000000000000000000000000000000000000000000
> 000000000000000000000000000000000000000000000000000000000000000000000000000000
> 000000000000000000000000000000000000000000000000000000000000000000000000000000
> 00000000000000000000000001e63bffffffffffffffff

> which isn't right.

However, if you add 18 more 0s to the long string of them (which the
formatting makes it look likely got dropped in whatever produced the
weird line breaks above - if I add 18 more 0s and paste the first two
lines together, the result is exactly as long as the next five lines),
that _is_ 2^2048 - 2^1984 - 1 + (2^64 * 124476).  That is, it's what
you get if you take pi to be 0.  I suspect your bc didn't recognize the
character string "pi" and treated it as an unset variable or some such,
effectively replacing it with 0.

I have a calculator program capable of working with numbers of this
size.  I told it to compute pi in hex to 500 places; truncating the
result to 1918 fraction bits gives (still in hex, linebreaks added for
email consumption)

3.243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c
89452821e638d01377be5466cf34e90c6cc0ac29b7c97c50dd3f84d5b5b54709
179216d5d98979fb1bd1310ba698dfb5ac2ffd72dbd01adfb7b8e1afed6a267e
96ba7c9045f12c7f9924a19947b3916cf70801f2e2858efc16636920d871574e
69a458fea3f4933d7e0d95748f728eb658718bcd5882154aee7b54a41dc25a59
b59c30d5392af26013c5d1b023286085f0ca417918b8db38ef8e79dcb0603a18
0e6c9e0e8bb01e8a3ed71577c1bd314b2778af2fda55605c60e65525f3aa55ab
945748986263e8144055ca396a2aab10b4

Setting pi to this value and telling it to compute (still working in
hex, hence the #d prefixes all over and the cvt() call because it
doesn't like mixed-base arithmetic)

pow(2,#d2048)-pow(2,#d1984)-1+(pow(2,#d64)*((pi*pow(2,#d1918))+cvt(#d124476,#d16)))

I get (again, line breaks added for email)

ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74
020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f1437
4fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7ed
ee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf05
98da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb
9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3b
e39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf695581718
3995497cea956ae515d2261898fa051015728e5a8aacaa68ffffffffffffffff

which is the value in RFC3526 (after case conversion and whitespace
fixup, the two text strings are identical).

I haven't done anything about checking it for primality.

If anyone would like to look at the calculator program in question, git
clone git://git.rodents-montreal.org/Mouse/calc and look at calc.c.  It
might even build for you, though not with the Makefile from the git
repo unless you pick up
ftp.rodents-montreal.org:/mouse/local/src/makefiles/makefiles-20100906/local-prog
and maybe not even then.  (icalc.c is ignorable - known broken.)

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		mouse%rodents-montreal.org@localhost
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B