[P1363:] Pseudo-random DP gen in P1363.2
Dear working group,
Here's more detail on the planned changes to
the P1363.2 draft D24.
At 04:53 PM 4/12/2006 -0700, D Jablon wrote:
>As a result of yesterday's teleconference,
>I'm planning these changes for P1363.2 D24:
>
>(1) Make the ECAPKAS-SRP5 key confirmation values
>to use octet hex(04) in the Client's message and
>hex(03) in the Server's, to align with all other
>schemes. This seems to have been an inadvertent
>minor discrepancy.
At 10:58 PM 4/12/2006 -0400, Yongge Wang wrote:
>> [...]
>> I feel your suggestions is good enough.. there is
>> no security implication there. Thus for compatible
purpose,
>> I think there is no reason to object that changes..
Thanks, Yongge.
I'll make those changes in D24.
>(2) Remove the A.16.13/14 methods for PRDPG/V.
This change is motivated by the fact that
several other different standard methods can
generate GF(p) primes, sufficient for
implementing any P1363.2 scheme, and it
doesn't seem appropriate to introduce yet
another method, or to provide yet-another
standard for an identical method.
However, several Annex sections referred to
the A.16.13 methods as ways to obtain primes
with extra constraints, which aren't explicitly
supported by the other standards.
So, to avoid making big changes to this
interlinked Annex discussion, I'd like to
replace the A.16.13-14 methods with a generic
method that shows how to use any of the other
standards, iteratively as needed, to find such
primes.
The proposed text is attached below.
-- David
__________________________________________________
David Jablon, Editor IEEE P1363.2
www.jablon.org
http://grouper.ieee.org/groups/1363/
==================================================
==================================================
A.16.13 Algorithm for generating verifiably
pseudo-random DL domain parameters p and r (prime
case)
Several standard methods exist that generate
verifiably pseudo-random (see NOTE 5) primes, suitable
for use as domain parameters for a DL prime field (see
NOTE 1). This method describes how to use such a
method (pGen) to produce domain parameter primes p and
r and associated SEED and counter output values, with
extra steps to ensure that k/2 is prime (see NOTE 3)
and/or that (r-1)/2 is prime (see NOTE 9). SEED and
counter can later be used to verify p and r using
A.16.14.
Input:
-- an integer L that specifies the size of desired
output p in bits (2^(L-1) < p < 2^L)
-- an integer M that specifies the size of desired
output r in bits (2^(M-1) < r < 2^M)
-- an indication of whether k/2 must be prime, where
p=kr+1
-- an indication of whether (r1)/2 must be prime
-- a method pGen(L', M') that produces a random octet
string SEED and associated pseudo-random values p, r,
and counter, where p is an L'-bit prime, r is an
M'-bit prime representing the order of a desired
subgroup of GF(p), and counter is an integer that may
be used to verify the pseudo-random construction of p
and r. (See NOTE 1.)
Output: Prime integers p and r and associated values
for octet string SEED and integer counter.
The method is defined as follows:
a) Use pGen(L, M) to generate p, r, SEED and counter.
b) If it is indicated that k/2 must be prime, perform
a robust primality test (see NOTE 4) on (p-1)/2r, and
if it is not prime, go to step a).
c) If it is indicated that (r-1)/2 must be prime,
perform a robust primality test on (r-1)/2, and if it
is not prime, go to step a).
d) Output the values p, r, SEED and counter.
NOTE 1— The FIPS 186-2 method in [B13] Appendix 2.2
generates “kosherized” primes for DSA, and similar
methods are described in ANSI X9.30.1-1997 [B2], ANSI
X9.42-2003 [B1] 7.1, IETF RFC 2631 [B44] 2.2.1, and
the proposed FIPS 186-3 [B14] A.1.1.2. (See IEEE
1363-2000 D.4.1.4 for more information.) The FIPS
186-2 method is limited to 1024 bit p=kr+1 with 160
bit subgroup order r (see NOTE 2) and does not impose
further constraints on the value of k. The X9.42 and
RFC 2631 method can can produce arbitrary sized p and
r, and it can further ensure that k=2 (by setting
L=M+1).
NOTE 2— In [B13], the letter “q” is used to denote the
desired subgroup order r.
NOTE 3— When k=2, or when k>r and k/2 is prime, the
only small order field elements of GF(p) are the
elements 1 and p-1, which may simplify testing for
acceptable public keys in various key agreement and
key retrieval schemes.
NOTE 4— Robust primality testing methods are described
in IEEE Std 1363-2000 A.15.3 and [B13].
NOTE 5— Meaning of “verifiably pseudo-random”.
Dependent on the strength of the selected hash
function and the length and source entropy of SEED, it
would be ideal if the generated values of p and r (in
the absence of SEED and counter values) were black
box-indistinguishable from randomly (or
pseudo-randomly) generated values of p and r that meet
the particular size, divisibility and primality
constraints. Strictly speaking, however, this goal is
not attainable; Unless SEED is chosen
deterministically (which would defeat randomness),
there is no way to enforce that the first chosen value
of SEED that yields acceptable values of p and r is
the one that is submitted for verification. Repeated
attempts could be made to generate values of p and r
that meet certain additional (perhaps undisclosed)
properties. Notably, the countermeasure to the
effectiveness of such attempts is the judicious use of
the (presumably computationally irreversible) hash
function within the generation and ver
ification algorithms. This is intended to make it
computationally infeasible to attain highly sparse
“trapdoor” properties in p and/or r (see NOTE 7). This
eliminates reliance on detection of perhaps unknown
trapdoor mechanisms by the verifier.
NOTE 6— It is not assumed that the generation source
is implicitly trusted by all relying parties. Relying
parties do not necessarily have to individually
implement verification, but rather can trust an
assignee, such as a particular certification
authority, to handle verification.
NOTE 7— The circumstances relative to what constitutes
an effective trapdoor can be dependent on the specific
application of p and r. For example, the method in
FIPS 186-2 effectively thwarts an attack of Vaudenay
against DSA [B49] that is based on constructing r such
that two messages hash to the same value modulo r.
This attack is different than the case of trapdoors
designed to shortcut the discrete log problem itself
for a system-wide p, such as pointed out by Lenstra
and Haber [B36] relative to the number field sieve,
which is also effectively thwarted by these methods.
NOTE 8— Algorithms to construct verifiably
pseudo-random elliptic curves are described in IEEE
1363-2000 A.12.4 (prime case) and A.12.6 (binary
case), [B13], and [B3].
NOTE 9— One of the suggested ways to reduce the threat
of SDHP attack in PKRS-1 as described in [B4] is to
ensure that the value of (r1)/2 is prime (see
D.5.5.3.6).
NOTE 10— A standard pGen method may be modified to
produce a faster method for generating primes with
extra constraints, by incorporating additional tests
between appropriate steps. One may need to be careful
to ensure that a modified generation method is
compatible with any desired standard verification
method.
A.16.14 Algorithm for verifying pseudo-random DL
domain parameters p and r (prime case)
This section describes a method to verify that prime
DL domain parameters p and r were generated by a
pseudo-random function of specific SEED and counter
values. This is compatible with the generation method
described in A.16.13 (see Notes).
Input:
-- an integer p'
-- an integer r'
-- an octet string SEED of seedLen octets
-- an integer counter
-- an indication of whether k/2 must be prime, where
p'=kr'+1
-- an indication of whether (r'-1)/2 must be prime
-- a method pVer(p, r, SEED, counter) that verifies
whether a pseudo-randomly generated DL field prime p
and subgroup order prime r were generated by the
values SEED and counter. (See NOTE 2)
Output: The message “verified” or “failed”.
a) Use pVer(p, r) to verify whether p and r are
generated by SEED and counter, and if the result is
not “verified”, output “failed” and stop.
b) If it is indicated that (r-1)/2 must be prime,
perform a robust primality test (see NOTE 4) on
(r-1)/2, and if it is not prime, output “failed” and
stop.
c) If it is indicated that k/2 must be prime, perform
a robust primality test on (p-1)/2r, and if it is not
prime, output “failed” and stop.
d) Output “verified”.
NOTE 1— See A.16.13 for the corresponding domain
parameter generation algorithm.
NOTE 2— Standard descriptions of pVer methods are in
ANSI X9.30.1-1997 [B2], ANSI X9.42-2003 [B1] 7.2, IETF
RFC 2631 [B44] 2.2.2 and the proposed FIPS 186-3 [B14]
A.1.1.1 and A.1.1.3.
NOTE 3— Algorithms to verify pseudo-random elliptic
curves are described in IEEE 1363-2000 A.12.5 (prime
case) and A.12.7 (binary case), [B13], and [B3].
NOTE 4— Robust primality testing methods are described
in IEEE Std 1363-2000 A.15.3 and [B13].
==================================================
==================================================
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
______________________________________________________________________
To unsubscribe, mail LISTSERV@LISTSERV.IEEE.ORG with
the body of the message containing: SIGNOFF STDS-P1363-DISCUSS
Send any concerns to STDS-P1363-DISCUSS-request@LISTSERV.IEEE.ORG,
or manage subscriptions at http://listserv.ieee.org/cgi-bin/wa
Visit IEEE P1363 on the web at: http://grouper.ieee.org/groups/1363
______________________________________________________________________