Prev: What do I need to know to design a cryptosystem?
Next: Is this construct a MAC ?
From: NoXenu on 11 May 2010 06:36
On May 10, 7:43 pm, stevenvh <steven.ne...(a)gmail.com> wrote:
> Hi,
> let the one-way function be (a ^ b) mod m. What are typical ranges for
> a, b and m? I guess a can be small ( 10^1 ?) since (a ^ b) becomes
> rather large very quickly.
> TIA
> Steven

The most important thing is for a to generate the entire group.
Whether it is small or not is not very relevant to security or
efficiency.


From: Scott Fluhrer on 11 May 2010 09:24

"Ertugrul S�ylemez" <es(a)ertes.de> wrote in message
news:20100511145833.133816ab(a)tritium.streitmacht.eu...
> NoXenu <amitabh123(a)gmail.com> wrote:
> > On May 10, 7:43 pm, stevenvh <steven.ne...(a)gmail.com> wrote:
> > > Hi,
> > > let the one-way function be (a ^ b) mod m. What are typical ranges for
> > > a, b and m? I guess a can be small ( 10^1 ?) since (a ^ b) becomes
> > > rather large very quickly.
> >
> > The most important thing is for a to generate the entire group.
> > Whether it is small or not is not very relevant to security or
> > efficiency.
>
> No. There are more important things. In fact, it's fine if 'a' just
> generates a large subgroup.

Actually, not; for an obvious counterexample, consider a group whose size
just happens to be 2^N for a large N; in that subgroup, you can solve the
discrete log problem in polynomial time.

It's also important if the size of that subgroup contains a large prime
factor (and in general, it's considered best if the size of the subgroup
just be a large prime).

For the OP: I second the recommendation of RFC 3526; DH groups involve some
nonobvious issues; if you are not familiar with the issues (and, by your
question, I assume you aren't), you'd be better off not going off on your
own.

--
poncho


From: Bryan on 12 May 2010 05:08
Ertugrul Söylemez wrote:
> And the properties of 'm' are what count here.  If 'm' is a safe prime,
> then you're not dealing with such a group.  In fact, if 'm' is a safe
> prime, then there are only two bad choices for 'a', namely 1 and -1.
> Every other choice will lead to a large subgroup covering either all or
> half of all elements.

Right, and for the confused: A "safe prime" is prime positive integer,
call it 'p', such that (p-1)/2=q is also prime. q is a called a
"Sophie Germain prime". The Diffie-Hellman moduli in RFC 3526 are such
a safe primes, though the RFC does not directly state the fact.

> The order of the largest subgroup, i.e. the whole group, is not a prime.

True. For any prime 'p', the multiplicative group mod p is of order
p-1. Thus the order is even and (with the exception of un-safe prime
p=3) not prime.

> In general, it's considered best to pick the largest subgroup.

No, currently practice is to pick a base that generates a subgroup of
large prime order. When the modulus is safe prime 'p', cryptographers
tend to choose a base that generates a subgroup of prime order q=(p-1)/
2. That said, I don't know of any security problem with your advice to
pick a safe prime and a generator of the entire group.


--
--Bryan
From: Greg Rose on 12 May 2010 12:08
In article <d5be07db-9929-4c15-8415-f0185fea33bd(a)e34g2000pra.googlegroups.com>,
Bryan <bryanjugglercryptographer(a)yahoo.com> wrote:
>Ertugrul S�ylemez wrote:
>> And the properties of 'm' are what count here. �If 'm' is a safe prime,
>> then you're not dealing with such a group. �In fact, if 'm' is a safe
>> prime, then there are only two bad choices for 'a', namely 1 and -1.
>> Every other choice will lead to a large subgroup covering either all or
>> half of all elements.
>
>Right, and for the confused: A "safe prime" is prime positive integer,
>call it 'p', such that (p-1)/2=q is also prime. q is a called a
>"Sophie Germain prime". The Diffie-Hellman moduli in RFC 3526 are such
>a safe primes, though the RFC does not directly state the fact.
>
>> The order of the largest subgroup, i.e. the whole group, is not a prime.
>
>True. For any prime 'p', the multiplicative group mod p is of order
>p-1. Thus the order is even and (with the exception of un-safe prime
>p=3) not prime.

Wot about 2? It's prime, but not safe either, and p-1 is odd! :-)

>> In general, it's considered best to pick the largest subgroup.
>
>No, currently practice is to pick a base that generates a subgroup of
>large prime order. When the modulus is safe prime 'p', cryptographers
>tend to choose a base that generates a subgroup of prime order q=(p-1)/
>2. That said, I don't know of any security problem with your advice to
>pick a safe prime and a generator of the entire group.

I guess it depends what you want to do with the
answer, and I don't think the OP actually said. If
it is for Diffie-Hellman, though, there is a
reason to prefer using the prime-order subgroup.
Note that it's straightforward to figure out which
subgroups a group element is in, and that for a
safe prime the order q subgroup is exactly
elements that are squares. Suppose you use a
generator of the entire group, in general. Alice
intentionally chooses a square, and does D-H with
Bob. Now if the result of the D-H is a square,
Alice knows that Bob chose a square too; otherwise
he didn't. This is one bit of information that
Alice shouldn't have, and can't be concealed.
Worse, if the D-H is in the clear, anyone can tell
that one bit of information about both Alice and
Bob's choices.

If it isn't a safe prime, the participants need to
be aware of, and check for, the "small subgroup
attack", which I'm not going to elucidate here.

Basically, it's always safest to use the
large-prime-order subgroup in this and most other
contexts.

Greg.
--
From: Greg Rose on 12 May 2010 12:14
Sleepy and imprecise below... see correction.

In article <hsejq7$qea$1(a)ihnp4.ucsd.edu>, Greg Rose <ggr(a)nope.ucsd.edu> wrote:
>In article <d5be07db-9929-4c15-8415-f0185fea33bd(a)e34g2000pra.googlegroups.com>,
>Bryan <bryanjugglercryptographer(a)yahoo.com> wrote:
>>Ertugrul S�ylemez wrote:
>>> And the properties of 'm' are what count here. �If 'm' is a safe prime,
>>> then you're not dealing with such a group. �In fact, if 'm' is a safe
>>> prime, then there are only two bad choices for 'a', namely 1 and -1.
>>> Every other choice will lead to a large subgroup covering either all or
>>> half of all elements.
>>
>>Right, and for the confused: A "safe prime" is prime positive integer,
>>call it 'p', such that (p-1)/2=q is also prime. q is a called a
>>"Sophie Germain prime". The Diffie-Hellman moduli in RFC 3526 are such
>>a safe primes, though the RFC does not directly state the fact.
>>
>>> The order of the largest subgroup, i.e. the whole group, is not a prime.
>>
>>True. For any prime 'p', the multiplicative group mod p is of order
>>p-1. Thus the order is even and (with the exception of un-safe prime
>>p=3) not prime.
>
>Wot about 2? It's prime, but not safe either, and p-1 is odd! :-)
>
>>> In general, it's considered best to pick the largest subgroup.
>>
>>No, currently practice is to pick a base that generates a subgroup of
>>large prime order. When the modulus is safe prime 'p', cryptographers
>>tend to choose a base that generates a subgroup of prime order q=(p-1)/
>>2. That said, I don't know of any security problem with your advice to
>>pick a safe prime and a generator of the entire group.
>
>I guess it depends what you want to do with the
>answer, and I don't think the OP actually said. If
>it is for Diffie-Hellman, though, there is a
>reason to prefer using the prime-order subgroup.
>Note that it's straightforward to figure out which
>subgroups a group element is in, and that for a
>safe prime the order q subgroup is exactly
>elements that are squares. Suppose you use a
>generator of the entire group, in general. Alice
>intentionally chooses a square, and does D-H with
>Bob.

First goof. What I meant was, Alice chooses (for her
secret exponent) an even integer; thus her public
key is a square.

>Now if the result of the D-H is a square,
>Alice knows that Bob chose a square too;

That is, Bob's secret exponent is even.

>otherwise
>he didn't. This is one bit of information that
>Alice shouldn't have, and can't be concealed.
>Worse, if the D-H is in the clear, anyone can tell
>that one bit of information about both Alice and
>Bob's choices.

.... of their secret exponents.

>If it isn't a safe prime, the participants need to
>be aware of, and check for, the "small subgroup
>attack", which I'm not going to elucidate here.
>
>Basically, it's always safest to use the
>large-prime-order subgroup in this and most other
>contexts.

Greg.


--
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: What do I need to know to design a cryptosystem?
Next: Is this construct a MAC ?