Re: general question how to choose parameters

From: Johanna Bernstein (johanna.bernstein_nospam_at_yahoo.com)
Date: 07/19/05 

Date: Tue, 19 Jul 2005 13:22:57 +0200

Hello,

> You could do this, but there are potential attacks
> with the discrete-log systems in general if you
> do. These are often called "small subgroup
> attacks". Basically, the multiplicative group mod
> P will have many subgroups, of the order of the
> prime powers of P-1; if the attacker can choose
> (or get you to choose) a parameter such that you
> get stuck in one of the small subgroups, he might
> be able to break the system. So the countermeasure
What do you mean with "a parameter"?

For example, look the following 2 examples:
1.) ElGamal: Let g be a generator of the multiplicative group Z_p^* and
p a large prime. To encrypt a plaintext m \in Z_p I can then do the
following:
C=(g^r,y^r*m), where y =g^s mod p is the public key.
I found this definition of elgamal in the handbook of applied
cryptography, so I suppose it's correct.
2.) Pedersen-Commitment: g is an element of order q (q|p-1) in Z_p^* and
h is an element generated by g. Then I can commit to a value m in
calculating:
g^{m}*h^r mod p.
So what is now the difference of the both cases? Why can't I just choose
  in 2.) like in the ElGamal-case g as a generator of Z_p^*? Why it has
to be an element of order q? If an attack is possible in 2.) why then
the attack isn't possible in 1.), cause if I could calculate the
discrete log of g^r then surely I could break the ElGamal scheme.

Btw. a somehow unrelated question to the above: Why can't I just commit
to a value m in calculating g^m mod p (g is a generator of Z_p^*)? Why
do I have to multiply by h^r?

> is to do all the calculations in a subgroup that
> is large enough for security; then the only
> failure cases are easy to check for (like the
> answer will be 1...). Otherwise you'd need to
> check that the order of all intermediate results
> was still large enough for security.
So is it an efficiency reason? Is this loss in efficiency very problematic?

Relevant Pages

  • [REVS] Cryptanalysis of the Random Number Generator of the Windows Operating System
    ... Get your security news from a reliable source. ... Cryptanalysis of the Random Number Generator of the Windows Operating ... of the algorithm and found a non-trivial attack: ... WRNG design. ...
    (Securiteam)
  • Re: algebraic question
    ... >that g is a generator of the multiplicative group of the ring Z_p. ... Somehow I misinterpreted G to be the multiplicative group of the ring ...
    (sci.math)
  • Re: Irreducible
    ... I think Mr. Montgomery refers about degree of alpha as ... No, your proof is the same as the flawed proof I posted yesterday, and ... generator of the multiplicative group of k. ...
    (sci.math)
  • Re: writing a basic chess game
    ... Pretend the target square has a piece of ... Trying to put all this stuff into a legal move generator adds too many complications to the code. ... For attack detection, it doesn't matter whether the attacker can legally move there. ... But for basic attack detection, it doesn't matter whether that piece can move because we are only concerned about the square being attacked, not how its being attacked. ...
    (rec.games.chess.computer)
  • ID revisited ... ( Yet another reason for abandoning numerical simulation)
    ... Windows random number generator is so not random ... observation with our attack is that learning a single state may reveal ... which can then be used to predict all random values, such as SSL keys, ...
    (talk.origins)
Quantcast