[Top] [All Lists]

Re: X9.42 comments.

1999-05-24 10:44:00
Couple of additional comments all about section [note I've
retained the original X9.42 text even in places where I've claimed other
problems in a previous message].

Firstly the algorithm for calculating 'q' in step 4 will produce a value
of 'q' with lots of zero bits if m is not a multiple of 160. For example
if m=319 it will have 158 zero bits.

This can be readily fixed by setting 
m' = (m + 159)/160 
in step 3 and in step 5: 
q = U mod 2^m
initially and then set the most and least signinificant bits as before.

The second issue may not be a problem as such.

The use of SEED doesn't quite follow the FIPS-186 usage. Let me

At several points FIPS-186 uses SHA[(SEED+k)mod 2^g] for the generation
of prime number candidates. The way it uses it obeys two rules.

1. Each value of k is used only once.
2. The order of use is such that each value of k is used in sequence.

(1) may have some cryptographic reason to ensure the same pseudo random
data is not re-used.

(2) makes implementation particularly easy: an implementer only needs
retain a copy of SEED+k and increment it every time it is used. This
property is not immediately apparent because of the way FIPS-186 is
written but it goes something like this:

All this refers to Appendix 2.2 FIPS-186:

Step 2. first uses SEED. It makes use of SEED and SEED+1 to calculate U
(and ultimately a candidate q). 

If q is not prime a new SEED is tried otherwise p is constructed from:

Vk = SHA[(SEED + offset + k) mod 2^g ].

For values of k = 0,...,n, and offset initially is 2.

This means that SEED+2, SEED+3, ... SEED+n+2 are used to ultimately
build a candidate p. If this is not successful (n+1) is added to offset
making it n+3 and each Vk calculated again. As can be seen the value of
SEED is incremented on each use.

The generalisation in X9.42 obeys neither rule if m' > 1. In this case:

4. for i = 0 to m' - 1

U = U + SHA[SEED + i] XOR SHA[(SEED + m' + i) mod 2^160] * 2^(160 * i)

This ends up using SEED and SEED+m'+1 (which is compatible with FIPS186
if m'=1) however if m'=3 say this uses SEED, SEED+3, SEED+1, SEED+4,

Then when we get to step 9 we end up using SEED+2, SEED+3,... and so on.

This ends up re-using the same data and as is apparent this is not in

If the algorithm used is made to be compatible with something else then
not much can be done. If we do have some control over it and the same
rules as FIPS-186 are desired then these changes should work:

Step 4.

4. for i = 0 to m' - 1

U = U + SHA[SEED + 2*i] XOR SHA[(SEED + 2*i + 1) mod 2^160] * 2^(160 *

Step 8.

Let counter=0 and offset = 2*m'

Assuming I haven't made some stupid slip this should end up incrementing
SEED each time and only using each value once. As before this retains
compatability with FIPS-186 if m=160 (m'=1).

Dr Stephen N. Henson.
Personal Email: shenson(_at_)drh-consultancy(_dot_)demon(_dot_)co(_dot_)uk 
Senior crypto engineer, Celo Communications:
Core developer of the   OpenSSL project:
Business Email: drh(_at_)celocom(_dot_)com PGP key: via homepage.

<Prev in Thread] Current Thread [Next in Thread>
  • X9.42 comments., Dr Stephen Henson
    • Re: X9.42 comments., Dr Stephen Henson <=