Prev: what is probability to create two equal hashes for md5 algorithm
Next: help needed
From: Joseph Ashwood on 3 Feb 2007 23:16
"Amit" <amitabh123(a)gmail.com> wrote in message
news:1170555205.040697.280290(a)h3g2000cwc.googlegroups.com...
[Scott: Make the prime smooth]
> Would someone who is using your "wrong" prime know there is a
> trapdoor ? Or you want to keep even this information secret?

That depends entirely on how smooth it was made, someone using 2^b+1 could
obviously detect that it is smooth, but for sufficiently large factors it is
difficult to tell without factoring p-1, which for sufficiently large
factors and p-1 is infeasible.

> If someone else finds out that p-1 is k-smooth, then he/she can also
> compute discrete logs.

If they have the factorization, then yes, but knowing it is smooth does not
necessarily lead directly to them being able to compute the discrete log.
They still need to perform the computations.
Joe


From: Peter Fairbrother on 4 Feb 2007 00:31
Joseph Ashwood wrote:

> "Amit" <amitabh123(a)gmail.com> wrote in message
> news:1170555205.040697.280290(a)h3g2000cwc.googlegroups.com...
> [Scott: Make the prime smooth]
>> Would someone who is using your "wrong" prime know there is a
>> trapdoor ? Or you want to keep even this information secret?
>
> That depends entirely on how smooth it was made, someone using 2^b+1 could
> obviously detect that it is smooth, but for sufficiently large factors it is
> difficult to tell without factoring p-1, which for sufficiently large
> factors and p-1 is infeasible.


Afaik there are no such large primes - any prime of the form 2^n + 1 must be
a Fermat prime, and there are only 4 known, the largest being 17 bits long.
I have considered primes of the form 3.2^n + 1 though.


Really, I was looking for another method than smooth primes - is there one?


--
Peter Fairbrother

From: Amit on 4 Feb 2007 00:47
On Feb 4, 4:31 pm, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote:
>
> Really, I was looking for another method than smooth primes - is there one?
>


I think this is a long standing open question. I recall that the chor-
rivest knapsack cryptosystem uses a scheme that requires computing DLs
using a trap-door but that requires hours of pre-computation.
See also the paper "Hidden Pairings and Trapdoor DDH Groups" (http://
www.isg.rhul.ac.uk/~alex/papers/trapdoor.pdf)

They also discuss a bit about Trapdoor DL groups.

From: Amit on 4 Feb 2007 04:12
On Feb 4, 4:31 pm, Peter Fairbrother <zenadsl6...(a)zen.co.uk> wrote:

>
> Really, I was looking for another method than smooth primes - is there one?
>
> --

Come to think about it, there IS a method for constructing a Trapdoor
DL group, namely a deterministic variant of the Paillier cryptosystem.
Please see the original paper here: http://www.gemplus.com/smart/rd/
publications/pdf/Pai99pai.pdf

In (non-deterministic) Paillier encryption, we have c = g^m.r^n mod
(n^2)

If we set r = 1, we obtain a deterministic variant. This variant,
however, has some subtleties:

1) We cannot set g=n+1 as is usually done
2) The deterministic variant is not semantically secure
3) It is possible that the deterministic variant may be insecure


From: Kristian Gj�steen on 4 Feb 2007 09:32
Peter Fairbrother <zenadsl6186(a)zen.co.uk> wrote:
>What's the best way to construct a large prime (plus a generator) so that it
>is easy to find discreet logs?
>
>If you were trying to backdoor a DLP-based system by choosing the wrong
>prime, how would you go about choosing it?

The best idea I've heard is to choose a non-prime. That obviously
requires those who use the prime to either not check that it is prime,
or use a primality test that in this context is defective.

For well-designed DLP-based systems, you verify that the parameters are
chosen in the prescribed manner (the prime really is a prime, the order
of the subgroup generator contains a large prime, and so on).

--
Kristian Gj�steen
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: what is probability to create two equal hashes for md5 algorithm
Next: help needed