Underlying group order, and member representation size.

From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: 02/17/04


Date: Tue, 17 Feb 2004 22:11:45 +0000


(no, it's got nothing to do with !)

It is often necessary (for eg ia semantic security reasons) to use an
underlying subgroup of prime order of the representational group in PK
situations. For instance, in DH or El Gamal in a representational Z_p of
size 1024 bits it is usual to use a subgroup of prime order q of size 160
bits.

Operations are carried out within the 160-bit group, and if for example we
could number the members, and convert the numbers to the member (and
vice-versa) we could get away with only using 160 bits to store and transfer
keys etc. There would be no need to transmit 1024 bits to denote the member.

Put another way, there are only 2^160 possible values of interest, but it
takes 1024 bits to specify a value. There are "impossible values", by which
I mean values that are representable but which are not members of the
underlying operative group.

You could convert the 1024-bit representation of a member of a 160-bit group
to a 160-bit number, and transmit those 160 bits instead of 1024 bits - but
it's hard to convert back.

You can also do it the other way round, ie 160->1024 is easy but 1024->160
is hard. I don't know how to do it so that translation is easy both ways.

My question:

DH/El Gamal can be implemented in many groups other than a subgroup of prime
order of Z_p, but are there any such where the order of the underlying group
is equal to the size of the space used to specify a member? With no
"impossible values"? A group that has p members, and each can be defined as
a number <= p?

If so, is it a group in which eg DLP is hard, and that does not have
problems like eg anomalous groups in ECC? Tom mentioned something about such
in another thread recently.

-- Peter Fairbrother

The new moon is shining the angels are washing their windows
Above the years whose jumble sale goes spinning on below



Relevant Pages

  • Underlying group order, and member representation size.
    ... underlying subgroup of prime order of the representational group in PK ... I mean values that are representable but which are not members of the ...
    (sci.crypt)
  • Re: Diffie-Hellman key exchange
    ... currently practice is to pick a base that generates a subgroup ... of large prime order. ... Now if the result of the D-H is a square, Alice knows that Bob ...
    (sci.crypt)
  • Re: Diffie-Hellman key exchange
    ... of large prime order. ... When the modulus is safe prime 'p', ... is a reason to prefer using the prime-order subgroup. ... Now if the result of the D-H is a square, Alice knows that Bob ...
    (sci.crypt)
  • Re: SSL/TLS DHE suites and short exponents
    ... the group needs to have one large subgroup; ... > usually that is chosen so that q (the prime order of the subgroup) ... The recipient has to know q and check it for primality in order to ...
    (sci.crypt)
  • Re: How to check whether a number belongs to a group?
    ... operations + and * that God gave to the integers, ... only finite cyclic group of integers of prime order is ... members of a group with a different operation. ... positive integer could be considered as a member of the group. ...
    (sci.math)