Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?]

[Jeffrey Hutzelman <jhutz%cmu.edu@localhost>]

On Wed, 2014-03-12 at 22:24 +0100, Niels Möller wrote:
> nisse%lysator.liu.se@localhost (Niels Möller) writes:
> 
> > 3. The 8192-bit prime definitely seems a bit expensive to generate.
> 
> I've now ran the updated version of the program on a more high-end pc.
> For 8192 bits, it completed in about 52 minutes. Output:
> 
> p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aaac42dad33170d04507a33a85521abdf1cba64ecfb850458dbef0a8aea71575d060c7db3970f85a6e1e4c7abf5ae8cdb0933d71e8c94e04a25619dcee3d2261ad2ee6bf12ffa06d98a0864d87602733ec86a64521f2b18177b200cbbe117577a615d6c770988c0bad946e208e24fa074e5ab3143db5bfce0fd108e4b82d120a92108011a723c12a787e6d788719a10bdba5b2699c327186af4e23c1a946834b6150bda2583e9ca2ad44ce8dbbbc2db04de8ef92e8efc141fbecaa6287c59474e6bc05d99b2964fa090c3a2233ba186515be7ed1f612970cee2d7afb81bdd762170481cd0069127d5b05aa993b4ea988d8fddc186ffb!
 7d!
>  c90a6c08f4df435c93402849236c3fab4d27c7026c1d4dcb2602646dec9751e763dba37bdf8ff9406ad9e530ee5db382f413001aeb06a53ed9027d831179727b0865a8918da3edbebcf9b14ed44ce6cbaced4bb1bdb7f1447e6cc254b332051512bd7af426fb8f401378cd2bf5983ca01c64b92ecf032ea15d1721d03f482d7ce6e74fef6d55e702f46980c82b5a84031900b1c9e59e7c97fbec7e8f323a97a7e36cc88be0f1d45b7ff585ac54bd407b22b4154aacc8f6d7ebf48e1d814cc5ed20f8037e0a79715eef29be32806a1d58bb7c5da76f550aa3d8a1fbff0eb19ccb1a313d55cda56c9ec2ef29632387fe8d76e3c0468043e8f663f4860ee12bf2d5b0b7474d6e694f91e6dbe115974a3926f12fee5e438777cb6a932df8cd8bec4d073b931ba3bc832b68d9dd300741fa7bf8afc47ed2576f6936ba424663aab639c5ae4f5683423b4742bf1c978238f16cbe39d652de3fdb8befc848ad922222e04a4037c0713eb57a81a23f0c73473fc646cea306b4bcbc8862f8385ddfa9d4b7fa2c087e879683303ed5bdd3a062b3cf5b3a278a66d2a13f83f44f82ddf310ee074ab6a364597e899a0255dc164f31cc50846851df9ab48195ded7ea1b1d510bd7ee74d73faf36bc31ecfa268359046f4eb879f924009438b481c6cd7889a002ed5ee382bc9190da6fc026e479!
 55!
>  8e4475677e9aa9e3050e2765694dfc81f56e880b96e7160c980dd98edd3dff!
>  fffffffffffffff
> k = 4743157
> elapsed time 3133.28s
> 
> Which after a cursory look appears to agree with
> https://www.rfc-editor.org/rfc/rfc3526.txt (I guess the 47473157 vs
> 4743158 is an off-by-one error in my code. Does the spec's brackets in
> in "[2^8062 pi]" denote floor or round-to-nearest?

Neither 2412 nor 3526 says what they mean by that notation, but I'm
assuming floor.  However, in that case your result agrees with the spec.

The value given in the spec is

2^8192 - 2^8128 - 1 + 2^64 * { [2^8062 pi] + 4743158 }

This can be rewritten as:

2^8192 - 2^8128 + 2^64 * { [2^8062 pi] + 4743157 } + 2^64 - 1

The first two terms give the high-order 64 bits (all 1).
The next term gives the middle bits, and agrees with your result.
The last two terms give the low-order 64 bits.

-- Jeff